Additive complements of the primes: is density $O(\log N)$ enough to cover every large integer? (Erdős #32)
Statement
Call $A\subset\mathbb{N}$ an additive complement to the primes if every sufficiently large integer can be written as $p+a$ for some prime $p$ and some $a\in A$. Is there an additive complement to the primes with $$\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)?$$ Can the stronger bound $\lvert A\cap\{1,\ldots,N\}\rvert=O(\log N)$ be achieved? Must every such $A$ satisfy $$\liminf_{N\to\infty} \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?$$ (The third question is known to have an affirmative answer — see background — so the live content is the first two.)
Acceptance. FULLY RESOLVES: (a) a construction (explicit or probabilistic, with a complete proof of the covering property and the density bound) of an additive complement to the primes with $\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)$ — additionally determining whether $O(\log N)$ is achievable settles Erdős's $50 question — OR (b) a proof that every additive complement to the primes satisfies $\limsup \lvert A\cap[1,N]\rvert/(\log N)^2>0$. Machine-checkable (Lean 4; the formal statement exists) preferred, else a complete written proof with all steps. ADVANCES: (a) a proven improvement of the exact-covering record $\ll(\log N)^2$ stated in the background, e.g. a complement with $\ll(\log N)^{2-\delta}$ for an explicit $\delta>0$; (b) a proven improvement of Ruzsa's liminf constant $e^\gamma$ stated in the background; (c) closing the almost-all gap: a complement covering almost all integers with counting function strictly better than the $\omega(N)\log N$ bound stated in the background, with proof. Deliver the construction + proof, or the impossibility proof.
Background
Posed by Erdős repeatedly from the 1950s onwards ([Er56, p.132], [Er57, p.295], [Er59, p.117], [Er61, p.229], [Er65b, p.227], [Er73, p.133], [Er77c, p.62]; see also [Va99, 1.9]); listed as open on erdosproblems.com/32 (fetched 2026-07-13, status 'open'), and discussed as problem E1 of Guy's collection [Gu04], where it is recorded that Erdős offered $50 for determining whether $O(\log N)$ is achievable. Counting shows $O(\log N)$ would be optimal: since only $\pi(N)\sim N/\log N$ primes lie below $N$, any complement must satisfy $\lvert A\cap[1,N]\rvert\gg N/\pi(N)\sim\log N$. The frontier: Lorentz [Lo54] constructed a complement with $\lvert A\cap[1,N]\rvert\ll(\log N)^3$; Erdős [Er54] improved this to $\ll(\log N)^2$, which remains the record for covering ALL large integers. If one asks only that almost all integers be representable, much sparser complements exist: Wolke [Wo96] achieved $\ll(\log N)^{1+o(1)}$, Kolountzakis [Ko96] improved this to $\ll(\log N)(\log\log N)$, and Ruzsa [Ru98c] to $\ll\omega(N)\log N$ for any function $\omega\to\infty$. For the third question, Ruzsa [Ru98c] proved that every additive complement to the primes satisfies $\liminf \lvert A\cap[1,N]\rvert/\log N\ge e^\gamma\approx 1.781$, answering it affirmatively and superseding the constant $1$. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tool: this is proof-shaped — a solver would bring a new probabilistic or greedy covering construction with a complete proof (sieve/large-values input on primes in progressions is the standard machinery), or a proof that exact covering forces $\gg(\log N)^2$; numerical experiments with greedy complements can guide constructions but cannot certify them.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #32 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #32 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.