Problem Statement
Let $A$ be an infinite set such that there are no distinct $a,b,c\in A$ such that $a\mid (b+c)$ and $b,c>a$. Is there such an $A$ with\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>0?\]Does there exist some absolute constant $c>0$ such that there are always infinitely many $N$ with\[\lvert A\cap\{1,\ldots,N\}\rvert<N^{1-c}?\]Is it true that\[\sum_{n\in A}\frac{1}{n}<\infty?\]
Categories:
Number Theory
Progress
Asked by Erdős and Sárközy [ErSa70], who proved that $A$ must have density $0$. They also prove that this is essentially best possible, in that given any function $f(x)\to \infty$ as $x\to \infty$ there exists a set $A$ with this property and infinitely many $N$ such that\[\lvert A\cap\{1,\ldots,N\}\rvert>\frac{N}{f(N)}.\](Their example is given by all integers in $(y_i,\frac{3}{2}y_i)$ congruent to $1$ modulo $(2y_{i-1})!$, where $y_i$ is some sufficiently quickly growing sequence.)An example of an $A$ with this property where\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\log N>0\]is given by the set of $p^2$, where $p\equiv 3\pmod{4}$ is prime.
Elsholtz and Planitzer [ElPl17] have constructed such an $A$ with\[\lvert A\cap\{1,\ldots,N\}\rvert\gg \frac{N^{1/2}}{(\log N)^{1/2}(\log\log N)^2(\log\log\log N)^2}.\]Schoen [Sc01] proved that if all elements in $A$ are pairwise coprime then\[\lvert A\cap\{1,\ldots,N\}\rvert \ll N^{2/3}\]for infinitely many $N$. Baier [Ba04] has improved this to $\ll N^{2/3}/\log N$.
For the finite version see [13].
This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.
Source: erdosproblems.com/12 | Last verified: January 13, 2026