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$.

DeepMind has provided a construction that shows the answer to the second question is no (and hence the answer to the first question is yes). This construction has been simplified and improved in the comments; it is now known that there exists an $A$ with this property such that, for all large $N$,\[\lvert A\cap \{1,\ldots,N\}\rvert \geq \frac{N}{(\log N)^{O(\log\log\log N)}}.\]It is unknown whether there exists such an $A$ with $\sum_{n\in A}\frac{1}{n}=\infty$.

For the finite version see [13].

View the LaTeX source

This page was last edited 08 April 2026. View history