The minimal order of growth of an additive complement of the primes

An additive complement of the set of primes $P$ is a set $A\subset\mathbb{N}$ such that every sufficiently large integer $n$ is of the form $n=p+a$ with $p$ prime and $a\in A$, where $A(N)=|A\cap\{1,\ldots,N\}|$ denotes the counting function. In 1954 Erdős proved, by a probabilistic construction, that such a complement exists with $A(N)\ll(\log N)^{2}$, improving the $(\log N)^{3}$ that follows from Lorentz's general theorem; the trivial lower bound is $A(N)\gg\log N$, and Ruzsa (1998) proved that any such complement must satisfy $\liminf A(N)/\log N\geq e^{\gamma}\approx 1.781$. The open problem is the true minimal order of growth of an additive complement of the primes: can the $(\log N)^{2}$ upper bound be improved, ideally to $O(\log N)$, or conversely can one prove that every complement satisfies $A(N)\geq c(\log N)^{2}$ for some absolute $c>0$? This is the principal surviving open question from the closing problems of Erdős's 1954 paper 'Some results on additive number theory' (the companion powers-of-2 question posed there is now solved); Erdős attached a $50 prize to it, and it is listed as open in the curated Erdős-problems database (Problem #32).

Background

Two sets of nonnegative integers have sumset $S+B=\{s+b:s\in S,b\in B\}$; $B$ is an additive complement of $S$ when $S+B$ contains every sufficiently large integer, and $S(x)=|S\cap[1,x]|$ denotes the counting function. (Throughout, $f\ll g$ and $g\gg f$ mean $f\le Cg$ for an absolute constant $C$, and $O(\cdot)$, $o(\cdot)$ carry their standard meanings.) Additive complements measure how efficiently a fixed sparse set can be 'completed' to a basis of order 2 for the large integers — a set $C$ such that every sufficiently large integer is a sum of two of its elements: since each $b\le x$ contributes only $S(x)$ sums $s+b\le x$, one needs at least about $x/S(x)$ complement elements, but exact minimal orders are known only in special cases.

Lorentz (Proc. Amer. Math. Soc. 5 (1954), 838-841), proving a conjecture of Erdős and Straus, showed that every infinite set $S$ admits a complement $B$ of density zero, with the quantitative bound $B(n)<c\,\sum_{k\le n}\log S(k)/S(k)$. Erdős's companion paper 'Some results on additive number theory' (Proc. Amer. Math. Soc. 5 (1954), 847-853) sharpened this in two directions. First (his Theorem 1), for the set of primes $P$, whose counting function is $\pi(x)\sim x/\log x$ by the prime number theorem, he constructed a complement $B$ with $B(n)\ll(\log n)^{2}$, improving the $(\log n)^{3}$ that follows from Lorentz's general theorem; the construction is probabilistic (a random choice of complement elements, shown by a second-moment/probabilistic argument to cover every large integer) and rests on estimates for the distribution of primes in short intervals. Second, he showed the $(\log n)^{2}$ order cannot be improved in general for dense sequences: there exists a sequence of positive lower density (indeed with liminf density $1/14$) every complement of which has counting function $>c(\log n)^{2}$. (The paper also answered, negatively, a question of Volkmann on pseudorational sequences — sequences approximable, up to a set of arbitrarily small density, by finite unions of arithmetic progressions — by exhibiting two pseudorational sequences whose sumset is not pseudorational, and gave an $O(x^{1/2})$ complement for the squares; those parts of the paper's legacy are either resolved or dormant.)

The subsequent literature on the prime-complement question is as follows. Wolke (J. Number Theory 59 (1996), 209-213) and Kolountzakis (Acta Arith. 77 (1996), 1-8) showed that for almost complements (representing almost all integers as $p+b$) one can achieve $(\log N)^{1+o(1)}$ and then $O(\log N\log\log N)$; Ruzsa (Acta Arith. 86 (1998), 269-275) improved this to $O(\omega(N)\log N)$ for any function $\omega(N)\to\infty$ and, in the opposite direction, proved that any genuine complement satisfies $\liminf A(N)/\log N\geq e^{\gamma}$, where $\gamma$ is the Euler-Mascheroni constant. Vu (Integers 2 (2002), A12) proved that $P$ has an additive complement of order 2 with $A(x)=O(\log x)$ (every large $n=a_1+a_2+p$ with $a_1,a_2\in A$), and Dai and Pan (Acta Arith. 162 (2014), 209-221) refined this to complements drawn from the primes themselves. Erdős attached a $50 prize to the order-1 question; it is discussed as problem E1 of Guy's 'Unsolved Problems in Number Theory' (3rd ed., 2004) and listed as open, with the $50 prize, in the curated Erdős-problems database (Problem #32), whose three formulations — $o((\log N)^{2})$? $O(\log N)$? $\liminf A(N)/\log N>1$? — record that the third was answered affirmatively by Ruzsa's $e^{\gamma}$ bound.

Problem Statement

Let $P$ be the set of primes and let $A\subset\mathbb{N}$ be an additive complement of $P$, i.e. every sufficiently large integer $n$ can be written as $n=p+a$ with $p\in P$ and $a\in A$. Writing $A(N)=|A\cap\{1,\ldots,N\}|$, Erdős proved that such a complement exists with $A(N)\ll(\log N)^{2}$, while any such complement satisfies $A(N)\gg\log N$ and, more precisely (Ruzsa), $\liminf_{N\to\infty}A(N)/\log N\geq e^{\gamma}$. Determine the true minimal order of growth of an additive complement of the primes. Specifically: (i) does there exist such an $A$ with $A(N)=o((\log N)^{2})$, in particular with $A(N)=O(\log N)$? (ii) or, conversely, does there exist an absolute constant $c>0$ such that every additive complement of the primes satisfies $A(N)\geq c(\log N)^{2}$ for all sufficiently large $N$? (The weaker lower-bound question, whether every complement must satisfy $\liminf_{N\to\infty}A(N)/\log N>1$, is already settled affirmatively by Ruzsa's bound $e^{\gamma}\approx 1.781$; no improvement of this constant — nor any lower bound of larger order than $\log N$ — is known for arbitrary complements of the primes, so the open lower-bound content is (ii).) The problem asks for the infimum over all additive complements $A$ of the primes of the order of growth of $A(N)$.

References

1. P. Erdős, Some results on additive number theory, Proc. Amer. Math. Soc. 5 (1954), 847-853. DOI 10.1090/S0002-9939-1954-0064798-9, https://doi.org/10.1090/S0002-9939-1954-0064798-9 (source paper)
2. G. G. Lorentz, On a problem of additive number theory, Proc. Amer. Math. Soc. 5 (1954), 838-841. DOI 10.1090/S0002-9939-1954-0063389-3, https://doi.org/10.1090/S0002-9939-1954-0063389-3
3. H. Ostmann, Review of P. Erdős, 'Some results on additive number theory', Zentralblatt für Mathematik und ihre Grenzgebiete, Zbl 0056.27001. https://zbmath.org/?q=an%3A0056.27001
4. I. Ruzsa, Jr., On a problem of P. Erdős, Canad. Math. Bull. 15 (1972), no. 2, 309-310. DOI 10.4153/CMB-1972-058-2, https://doi.org/10.4153/CMB-1972-058-2
5. Dieter Wolke, On a problem of Erdős in additive number theory, J. Number Theory 59 (1996), no. 2, 209-213. DOI 10.1006/jnth.1996.0094, https://doi.org/10.1006/jnth.1996.0094
6. Mihail N. Kolountzakis, On the additive complements of the primes and sets of similar growth, Acta Arith. 77 (1996), no. 1, 1-8. DOI 10.4064/aa-77-1-1-8, https://doi.org/10.4064/aa-77-1-1-8
7. Imre Z. Ruzsa, On the additive completion of primes, Acta Arith. 86 (1998), no. 3, 269-275. DOI 10.4064/aa-86-3-269-275, https://doi.org/10.4064/aa-86-3-269-275
8. Imre Z. Ruzsa, Additive completion of lacunary sequences, Combinatorica 21 (2001), no. 2, 279-291. DOI 10.1007/s004930100025, https://doi.org/10.1007/s004930100025
9. Van H. Vu, High order complementary bases of primes, Integers 2 (2002), A12, 5 pp. (electronic). DOI 10.5281/zenodo.7589264, https://doi.org/10.5281/zenodo.7589264 (journal volume listing: https://math.colgate.edu/~integers/vol2.html)
10. Li-Xia Dai and Hao Pan, The additive complements of primes and Goldbach's problem, Acta Arith. 162 (2014), no. 3, 209-221. DOI 10.4064/aa162-3-1, https://doi.org/10.4064/aa162-3-1 (preprint arXiv:1101.1653, posted on arXiv under the title 'Note on the additive complements of primes', https://arxiv.org/abs/1101.1653)
11. Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004, xviii+438 pp. (problem E1 discusses the additive complement of the primes and Erdős's $50 prize). DOI 10.1007/978-0-387-26677-0, ISBN 978-0-387-20860-2, https://link.springer.com/book/10.1007/978-0-387-26677-0
12. T. F. Bloom (ed.), Erdős Problems Database, Problem #32 (additive complement of the primes; OPEN, $50 prize), https://www.erdosproblems.com/32 (curated problem record citing Erdős 1954, Lorentz 1954, Wolke 1996, Kolountzakis 1996, Ruzsa 1998, Guy 2004)
13. T. F. Bloom (ed.), Erdős Problems Database, Problem #221 (additive complement of the powers of 2; PROVED), https://www.erdosproblems.com/221
14. Yuchen Ding, Ben Krause, Csaba Sándor, Yu-Chen Sun and Zihan Zhang, Cross representations of additive complements of $r$-th powers, arXiv:2512.15407 (2025/2026 preprint), https://arxiv.org/abs/2512.15407
15. Bodo Volkmann, Zwei Bemerkungen über pseudorationale Mengen, J. Reine Angew. Math. 193 (1954), 126-128. DOI 10.1515/crll.1954.193.126, https://doi.org/10.1515/crll.1954.193.126