Erdős Problem #32 — Growth of complementary sequences to the primes

Let $a_1<a_2<\cdots$ be an infinite sequence of integers. Straus and I conjectured that there is a sequence of density $0$, $b_1<b_2<\cdots$, such that every integer is of the form $a_i+b_j$. Lorentz [1954] proved this conjecture. We call $b_1<b_2<\cdots$ a complementary sequence to $a_1<a_2<\cdots$.

When the $a_i$ are the primes, Lorentz observed that (12.1) gives $B(x)<c(\log x)^3$, and Erdős [1954] proved the improvement $B(x)<c(\log x)^2$. Clearly every complementary sequence to the primes must satisfy

$$\liminf \frac{B(x)}{\log x}\ge 1. \tag{12.2}$$

Erdős stated that he expected (12.2) could be improved, but could not prove even

$$\limsup \frac{B(x)}{\log x}>1.$$

He also could not find a complementary sequence to the primes satisfying $B(x)=o((\log x)^2)$, and could not decide whether there is a complementary sequence to the primes $b_1<b_2<\cdots$ for which the number of solutions of $n=p+b_i$ is bounded.