Problem Statement
Let $A\subset\mathbb{N}$ be such that every large integer can be written as $n^2+a$ for some $a\in A$ and $n\geq 0$. What is the smallest possible value of\[\limsup \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}?\]Is\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>1?\]
Categories:
Number Theory Additive Basis
Progress
Such a set $A$ is called an additive complement of the set of squares. Erdős observed that there exist $A$ for which the $\limsup$ is finite and $>1$. Moser [Mo65] proved that, for any such $A$,\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>1.06.\]The best-known lower bound is\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}\geq\frac{4}{\pi}\approx 1.273\]proved by Cilleruelo [Ci93], Habsieger [Ha95], and Balasubramanian and Ramana [BaRa01].The problem of minimising the $\limsup$ appears to have been much less studied. van Doorn has a construction of such an $A$ in which, for all $N$,\[\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}< 2\phi^{5/2}\approx 6.66,\]where $\phi=\frac{1+\sqrt{5}}{2}$ is the golden ratio.
Source: erdosproblems.com/33 | Last verified: January 13, 2026