OPEN
This is open, and cannot be resolved with a finite computation.
- $50
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?\]
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.
View the LaTeX source
This page was last edited 08 December 2025.
Additional thanks to: Mark Sellke and Wouter van Doorn
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #32, https://www.erdosproblems.com/32, accessed 2026-01-16
