Problem #1103: Let $A$ be an infinite sequence of integers such that every...

---

Progress

Erdős notes there exists such a sequence which grows exponentially, but does not expect such a sequence of polynomial growth.

In [Er81h] he asked whether there is an infinite sequence of integers $A$ such that, for every $a\in A$ and prime $p$, if\[a\equiv t\pmod{p^2}\]then $1\leq t<p^2/2$. He noted that such a sequence has the property that every $n\in A+A$ is squarefree. He wrote 'I am doubtful if such a sequence exists. I formulated this problem while writing these lines and must ask the indulgence of the reader if it turns out to be trivial.'

Indeed, there are trivially at most finitely many such $a$, since there cannot be any primes $p\in (a^{1/2},(2a)^{1/2}]$, but there exist primes in $(x,\sqrt{2}x)$ for all large $x$.

If $A=\{a_1<a_2<\cdots\}$ is such a sequence then van Doorn and Tao [vDTa25] have shown that $a_j > 0.24j^{4/3}$ for all $j$, and further that there exists such a sequence (furthermore with squarefree terms) such that\[a_j < \exp(5j/\log j)\]for all large $j$. A superior lower bound of $a_j \gg j^{15/11-o(1)}$ had earlier been found by Konyagin [Ko04] when considering the finite case [1109].

They also obtain further results for the generalisation from squarefree to $k$-free integers, and also replacing $A+A$ with $A\cup (A+A)\cup(A+A+A)$.

See also [1109] for the finite analogue of this problem.