Additive complements to the primes and large gaps between Romanoff numbers

Abstract

We prove that every set $\mathcal{B}\subseteq {\mathbb{Z}}_{\ge 0}$ for which $\mathbb{P}+\mathcal{B}$ contains all sufficiently large integers satisfies $B(X)\gg \log X\log \log X$, where $B(X)=\#(\mathcal{B}\cap [0,X])$ and the implied constant is absolute. This proves a quantitative form of Ruzsa's Conjecture 2 and gives a negative answer to the $O(\log X)$ question in Erdős Problem 32. The bound follows from a more general result: for an arbitrary set $\mathcal{B}\subseteq {\mathbb{Z}}_{\ge 0}$ and sufficiently large $X$, we construct a block of $\lfloor c\log X\log \log X/(B(X)+1)\rfloor$ consecutive integers in $[X/2,X]$ outside $\mathbb{P}+\mathcal{B}$, provided this length is positive. As an application, we obtain $G_{\mathcal{R}}(X)\gg \log \log X$ for the longest block in $[1,X]$ containing no Romanoff number $p+2^n$, improving the bound $G_{\mathcal{R}}(X)\gg \log \log X/\log \log \log X$ of Kalmynin and Konyagin. The argument also applies to $p+a^n$ for every fixed integer $a\ge 2$. The key step is a lemma on large shifts, proved using truncated products of divisor sums and the removal of auxiliary primes dividing differences of shifts.

arXiv comment32 pages. Substantially revised and expanded version of "A lower bound for additive complements to the primes", with a new title. Includes a detailed proof of a large-shift lemma and new results on gaps between Romanoff numbers