Problem Statement
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?\]
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?\]
Categories:
Number Theory Additive Basis
Progress
Such a set is called an additive complement to the primes.Erdő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$).
Wolke [Wo96] has shown that such a bound is almost true, in that we can achieve $\ll (\log N)^{1+o(1)}$ if we only ask for almost all integers to be representable. Kolountzakis [Ko96] improved this to $\ll (\log N)(\log\log N)$, and Ruzsa [Ru98c] further improved this to $\ll \omega(N)\log N$ for any $\omega\to \infty$.
The answer to the third question is yes: Ruzsa [Ru98c] has shown that we must have\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}\geq e^\gamma\approx 1.781.\]This is discussed in problem E1 of Guy's collection [Gu04], where it is stated that Erdős offered \$50 for determining whether $O(\log N)$ can be achieved.
Source: erdosproblems.com/32 | Last verified: January 13, 2026