Can a set where no member divides the sum of two larger members have divergent reciprocal sum? (Erdős #12)
Statement
Let $A\subseteq\mathbb{N}$ be an infinite set containing no three distinct elements $a,b,c$ with $b,c>a$ and $a\mid(b+c)$. Erdős and Sárközy asked three questions about how large such an $A$ can be. (i) Can $A$ satisfy $$\liminf_{N\to\infty}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>0?$$ (ii) Is there an absolute constant $c>0$ such that every such $A$ has $\lvert A\cap\{1,\ldots,N\}\rvert<N^{1-c}$ for infinitely many $N$? (iii) Must every such $A$ satisfy $$\sum_{n\in A}\frac1n<\infty?$$ The remaining open kernel is question (iii): can an infinite $A$ with this divisibility-avoidance property have a divergent reciprocal sum?
Acceptance. FULLY RESOLVES (the open question (iii)): EITHER exhibit an infinite $A\subseteq\mathbb{N}$ with no distinct $a,b,c$ ($b,c>a$) satisfying $a\mid(b+c)$ and with $\sum_{n\in A}1/n=\infty$ — giving an explicit description of $A$, a proof it avoids the divisibility relation, and a proof the reciprocal sum diverges — OR a complete proof that every such $A$ has $\sum_{n\in A}1/n<\infty$ (Lean/Coq-checkable preferred, else a full written proof). ADVANCES: improve the best-known lower bound on $\lvert A\cap\{1,\ldots,N\}\rvert$ for such sets strictly beyond the density $N/(\log N)^{O(\log\log\log N)}$ stated in the background, with proof; OR improve the pairwise-coprime upper bound strictly below Baier's $\ll N^{2/3}/\log N$, with proof; OR construct an explicit near-optimal such $A$ and compute certified reciprocal-sum partial sums that quantify progress toward divergence. Deliver the construction plus proofs, or the improved-bound proof.
Background
Introduced by Erdős and Sárközy [ErSa70], who proved every such $A$ has density $0$, and that this is essentially best possible: for any $f(x)\to\infty$ there is such an $A$ with $\lvert A\cap\{1,\ldots,N\}\rvert>N/f(N)$ for infinitely many $N$ (their construction takes the integers in $(y_i,\tfrac32 y_i)$ that are $\equiv 1\pmod{(2y_{i-1})!}$ for a fast-growing $y_i$). A clean example achieving $\liminf \lvert A\cap\{1,\ldots,N\}\rvert\,(\log N)/N^{1/2}>0$ is the set of $p^2$ with $p\equiv 3\pmod 4$ prime. Elsholtz and Planitzer [ElPl17] constructed such an $A$ with $\lvert A\cap\{1,\ldots,N\}\rvert\gg N^{1/2}/((\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2)$. Under pairwise coprimality Schoen [Sc01] proved $\lvert A\cap\{1,\ldots,N\}\rvert\ll N^{2/3}$ for infinitely many $N$, improved by Baier [Ba04] to $\ll N^{2/3}/\log N$. Recently a construction (attributed on the site to DeepMind and then simplified and improved in the site comments) answered question (ii) NO — and hence question (i) YES — producing such an $A$ with $\lvert A\cap\{1,\ldots,N\}\rvert\ge N/(\log N)^{O(\log\log\log N)}$ for all large $N$. Question (iii) remains open: it is unknown whether any such $A$ can have $\sum_{n\in A}1/n=\infty$. The finite analogue is Erdős #13 (erdosproblems.com/13). The problem carries no cash prize. A Lean formalisation exists in the Google DeepMind Formal Conjectures project. Listed as open on erdosproblems.com/12 (fetched 2026-07-13, status 'open', tagged 'number theory'). Attacker's tool: explicit density-optimal constructions with computed reciprocal-sum partial sums, plus sieve and probabilistic arguments — either build an $A$ obeying the no-$a\mid(b+c)$ rule whose reciprocal sum diverges, or prove every such $A$ has convergent reciprocal sum.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #12 (T. F. Bloom) | website |
| REF-02 | Lean formalisation — Erdős #12 (Google DeepMind Formal Conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.