Problem 32

Erdős Problem #32: declared status 'open'. Formalized: yes. Is there a set $A\subset\mathbb{N}$ such that$$\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)$$and such that every large integer can be written as $p+a$ for some prime $p$ and $a\in A$? Can the bound $O(\log N)$ be achieved? Must such an $A$ satisfy$$\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?$$ Current best: Erd\H{o}s [Er54] proved that such a set $A$ exists with $\lvert A\cap\{1,\ldots,N\}\rvert\ll (\log N)^2$ (improving a previous result of Lorentz [Lo54] who achieved $\ll (\log N)^3$). Prize: no. Tags: additive basis, number theory.