Problem 33

Erdős Problem #33: declared status 'open'. Formalized: yes. 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?$$ Current best: 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]. Prize: no. Tags: additive basis, number theory.