PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.
Is it true that, for any $x$, if $A\subset [x,\infty)$ is a primitive set of integers (so that no distinct elements of $A$ divide each other) then\[\sum_{a\in A}\frac{1}{a\log a}< 1+o(1),\]where the $o(1)$ term $\to 0$ as $x\to \infty$?
A conjecture of Erdős, Sárközy, and Szemerédi. Lichtman [Li23] has proved that\[\sum_{a\in A}\frac{1}{a\log a}< e^{\gamma}\frac{\pi}{4}+o(1)\approx 1.399+o(1).\]This was solved by GPT-5.4 Pro (prompted by Price), which proved that for any primitive set $A\subset \mathbb{N}$\[\sum_{\substack{a\in A\\ a>x}}\frac{1}{a\log a}\leq 1+O\left(\frac{1}{\log x}\right).\]See the comment section for further refinements and discussion. An account of this proof and the method is given by Alexeev, Barreto, Li, Lichtman, Price, Shah, Tang, and Tao [ABLLPSTT26].
Lichtman [Li20] proved that if $A$ is the set of all integers with exactly $k$ prime factors (so that $A\subset [2^k,\infty)$ and $A$ is a primitive set) then\[\sum_{a\in A}\frac{1}{a\log a}\geq 1+O(k^{-1/2+o(1)}),\]and suggested that the true rate of decay may be $O(2^{-k})$. Gorodetsky, Lichtman, and Wong [GLW24] have proved that\[\sum_{a\in A}\frac{1}{a\log a}= 1-(c+o(1))k^22^{-k}\]where $c\approx 0.0656$ is an explicit constant.
See also [164] for the case $x=1$.
This page was last edited 12 May 2026. View history
External data from the database - you can help update this
Formalised statement?
Yes
Related OEIS sequences:
Possible
Additional thanks to: Liam Price
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1196, https://www.erdosproblems.com/1196, accessed 2026-06-30
Order by oldest first or newest first. (The most recent comments are highlighted in a red border.)
-
Just saw Math, Inc. has formalized the GPT-5.4 Pro solution!
-
The anticipated paper on this problem by Alexeev, Barreto, Li, Lichtman, Price, Shah, Tang, and Tao is now on arXiv!
-
A possible relative-capacity application of the coprime-modulus variant
I have been trying to understand whether the new von Mangoldt flow / cut-capacity method gives sharp constants not only for the full divisibility poset, but also for natural local arithmetic subuniverses.
Let me write, provisionally,\[
\operatorname{Cap}(S)
:=
\limsup_{x\to\infty}\
\sup_{\substack{A\subset S\cap[x,\infty)\\ A\ {\rm primitive}}}
\sum_{a\in A}\frac1{a\log a}.
\]Thus \(\operatorname{Cap}(\mathbb N)=1\) in the sense of #1196.Fix an odd prime \(\ell\). Let \(U_\ell\) be the set of positive integers \(N\) such that \(\ell\) divides each of\[
\varphi(N),\quad \lambda(N),\quad \psi(N),\quad
J_t(N)\ (t\geq 1),\quad
\sigma_t(N)\ (t\geq 0),
\]where \(\psi\) denotes the Dedekind psi function.The non-\(\sigma\) conditions seem to be soft from the capacity point of view. For instance, failure of the \(\varphi,\lambda,J_t\) gates forces avoidance of primes \(p\equiv 1\pmod\ell\), except for the irrelevant escape \(v_\ell(N)\geq 2\), and failure of the Dedekind-\(\psi\) gate similarly forces avoidance of primes \(p\equiv -1\pmod\ell\). Such residue-class avoidance should have zero relative capacity by the coprime-to-modulus variant.
The interesting part is therefore the local \(\sigma_t\) condition. Put \(m=\ell-1\). For \(p\neq \ell\) and \(e\geq 0\), define\[
Z_\ell(p,e)
:=
\left\{
t\in \mathbb Z/m\mathbb Z:
1+p^t+\cdots+p^{et}\equiv 0\pmod\ell
\right\},
\]where the class \(t=0\) is to be interpreted as the positive class \(t\equiv 0\pmod m\). This also handles \(\sigma_0\), since for \(p\neq\ell\) the condition at \(t=0\) is just \(e+1\equiv0\pmod\ell\). The prime \(p=\ell\) does not help with this positive class, since\[
1+\ell^t+\cdots+\ell^{et}\equiv 1\pmod\ell
\qquad (t\geq 1).
\]The soft \(\sigma\)-classes are those \(t\) for which \(x^t=-1\) is solvable in \(\mathbb F_\ell^\times\), i.e.\[
\gcd(t,m)\mid m/2.
\]For such a class, an exponent-one prime in a suitable nonempty residue class already kills \(\sigma_t\), so failure should again have zero capacity. Thus the genuinely finite gates are\[
\operatorname{Hard}_\ell
:=
\left\{
t\in \mathbb Z/m\mathbb Z:
\gcd(t,m)\nmid m/2
\right\}.
\]This leads to the candidate formula\[
\operatorname{Cap}(U_\ell)
=
\mathbb P\left(
\operatorname{Hard}_\ell
\subset
\bigcup_{p\neq \ell} Z_\ell(p,V_p)
\right),
\]where the \(V_p\) are independent geometric valuations\[
\mathbb P(V_p=e)=\frac{1-1/p}{p^e}
\qquad (e\geq0).
\]For example, when \(\ell=3\), one has \(\operatorname{Hard}_3=\{0\}\), so this gives\[
\operatorname{Cap}(U_3)
=
1-\prod_{p\neq3}
\left(1-\frac1{p^2+p+1}\right).
\]Similarly, for \(\ell=5\),\[
\operatorname{Cap}(U_5)
=
1-\prod_{p\neq5}
\left(1-\frac1{p^4+p^3+p^2+p+1}\right).
\]The first genuinely coupled case is \(\ell=7\), where\[
\operatorname{Hard}_7=\{0,2,4\}.
\]The one-gate collapse seems to occur exactly when \(\ell-1\) is a power of \(2\).The proof route I have in mind is:
1. classify the local gates for \(\varphi,\lambda,\psi,J_t,\sigma_t\);
2. discard the residue-class avoidance failures and the soft \(\sigma\)-failures as zero-capacity sets;
3. use the coprime-to-fixed-modulus variant to evaluate finite exact valuation atoms, namely\[
\operatorname{Cap}\{n:v_p(n)=e_p\ {\rm for}\ p\in P\}
=
\prod_{p\in P}\frac{1-1/p}{p^{e_p}}
\]for each finite set of primes \(P\), up to the harmless fixed logarithmic shift from dividing out \(\prod_{p\in P}p^{e_p}\);
4. pass from finite \(P\) to all primes using the convergent \(p^{-2}\)-type tails for the hard gates.My main question is about step 3. Is the exact finite-valuation atom statement really an immediate corollary of the coprime-to-fixed-modulus/cut-capacity inequality, after dividing out the fixed prime powers, or is there some obstruction from the fact that an exact valuation atom is not divisor-closed under the downward flow?
-
A feature of this solution that seems worth emphasizing is that it is not merely a Markov-chain trick, but a dual certificate for the divisibility poset.
The cleanest way I now understand the proof is as follows. Put a weighted directed edge\[
nq\to n,\qquad
w(nq,n)=\frac{\Lambda(q)}{nq\log^2(nq)}.
\]Then the von Mangoldt identity gives the exact outflow\[
\operatorname{Out}(n)
=
\frac{1}{n\log n},
\]while Mertens' theorem gives the asymptotic inflow\[
\operatorname{In}(n)
=
\sum_q\frac{\Lambda(q)}{nq\log^2(nq)}
=
\frac{1}{n\log n}
+
O\!\left(\frac{1}{n\log^2 n}\right).
\]Thus the flow is almost divergence-free on the tail \(n\ge x\), with total divergence\[
\sum_{n\ge x}|\operatorname{div}(n)|
\ll
\frac1{\log x}.
\]Now take\[
\Omega=\{d\ge x:\ d\mid a \text{ for some } a\in A\}.
\]The primitivity of \(A\) is used in exactly one decisive place: every edge entering \(a\in A\) comes from outside \(\Omega\), because if \(aq\in\Omega\), then \(a\mid aq\mid b\) for some \(b\in A\), forcing \(a=b\), impossible for \(q>1\). Hence the inflow into \(\Omega\) sees\[
\sum_{a\in A}\frac1{a\log a}
\]up to the \(O(1/\log x)\) error. On the other hand, every edge leaving \(\Omega\) must cross below \(x\), and the same Mertens computation gives boundary outflow\[
1+O\!\left(\frac1{\log x}\right).
\]The discrete divergence theorem then immediately gives\[
\sum_{a\in A}\frac1{a\log a}
\le
1+O\!\left(\frac1{\log x}\right).
\]This formulation makes the role of \(\Lambda\) especially transparent. It is doing two independent jobs at once: locally, it gives the exact divisor identity\[
\sum_{q\mid n}\Lambda(q)=\log n,
\]and globally, it gives the correct Mertens normalization at the boundary. That combination is precisely what removes the extra constants appearing in earlier approaches.In this form, the proof feels like a weighted LYM/Sperner certificate for the divisibility lattice: construct a nearly divergence-free flow whose chains are divisibility chains, observe that an antichain can be crossed only once, and compute the boundary mass. It would be very interesting to know how far this flow-certificate viewpoint extends, especially to restricted prime supports, \(k\)-almost-prime layers, and Banks--Martin type extremal questions.
-
We have built what one might call the von Mangoldt downward process $n \mapsto n/q$ (with transition probability $\Lambda(q)/\log n$), the von Mangoldt measure $\nu$, and the von Mangoldt upward process $n \mapsto qn$ (with transition probability $\Lambda(q) \nu(nq) / \nu(n) \log (nq)$, all powered by the basic identity $\sum_{q|n} \Lambda(q) = \log n$. But this process can "jump" over primes due to the fact that the support of $\Lambda$ contains prime powers in addition to just primes.
But suppose we take the fundamental theorem of arithmetic identity $\sum_{p|n} v_p(n) \log p = \log n$ instead, where $v_p(n)$ is the number of times $p$ divides $n$. This then gives a "downward prime process" in which $n$ transitions to $n/p$ with probability $v_p(n) \log p / \log n$, and then should give a "prime measure" $\tilde \nu$ that is invariant under this process and asymptotic to $1/n \log n$, as well as an "upward prime process" in which $n$ transitions to $np$ with probability $v_p(np) \log p \tilde \nu(np) / \log(np) \tilde \nu(n)$. This should be very similar to the von Mangoldt processes, but now the inequality $\sum_{a \in A} \tilde \nu(a) \leq 1$ should be an identity in the case $A$ is the set of products of $k$ primes (possibly repeated), because this process does not jump over primes. (This is similar to the modification of $\nu$ proposed by Will, but has a slight difference, in that when repeated primes occur in the factorization, Will often factors them out consecutively in the downward process, whereas in this process they will be factored out at random times.)
Given how nice the formula for $\nu$ was - basically the Laplace transform of $1/\zeta$ - perhaps one can hope that there is a similarly clean formula for $\tilde \nu$? Among other things, this should lead to an improvement of the $1/\log x$ type error term (indeed, one might now hope to not just improve the constant, but get better asymptotic decay of the error term than just one power of the logarithm).
A variant question: suppose we restrict the von Mangoldt downward process $n \mapsto n/q$ to squarefree numbers (note that the property of being squarefree is preserved by the flow). What is the new canonical measure $\nu_{sf}$ attached to this restricted process? My initial guess is that it will have to do with the Laplace transform of $\zeta(2s)/\zeta(s)$.
All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.