---

Claim. Let $B\subset\mathbb{N}$, let $S=\{p+b : p \text{ prime}, b\in B\}$, and write $B(x)$ and $S(x)$ for the counting functions. Theorem 2 of Ruzsa's paper states that if

$$x-S(x)\le x^{1-\log\log\log x/\log\log x}$$

for all large $x$, and so in particular if $S$ contains all but finitely many natural numbers, then

$$\liminf_{x\to\infty}\frac{B(x)}{\log x}\ge e^{\gamma},$$

with $\gamma$ the Euler--Mascheroni constant, so the limit inferior is at least $1.781\ldots$. A set $A$ as in Problem 32, one for which every large integer is $p+a$ with $p$ prime and $a\in A$, is exactly a set whose $S$ is cofinite, so

$$\liminf_{N\to\infty}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}\ge e^{\gamma}>1,$$

which answers the third question of the problem yes. Ruzsa proves the theorem in a quantitative form (Section 3 of the paper): if $\alpha<e^{\gamma}$ and $B\subset[1,x]$ has at most $\alpha\log x$ elements, then for some $c<1$ and all large $x$ at least $x^{1-c\log\log\log x/\log\log x}$ integers up to $x$ are not of the form $p+b$. The same paper's Theorem 1 constructs complements covering most integers rather than every large integer: of size $O(\log x)$ with sumset of lower density above $1-\varepsilon$ for any $\varepsilon>0$, and of size $O(\omega(x)\log x)$ with sumset of density $1$; those results bear on the second question without answering it.

Covers. The third question (the part liminf), answered yes with the bound $e^{\gamma}$. Not covered: whether a set $A$ with $\lvert A\cap\{1,\ldots,N\}\rvert=o((\log N)^2)$ exists (the part existence) and whether $O(\log N)$ can be achieved (the part log); a lower bound on the liminf decides neither.

Depends on. Nothing in this wiki; the claim rests on the cited paper.

Acceptance. Refereed: I. Z. Ruzsa, On the additive completion of primes, Acta Arith. 86 (1998), no. 3, 269--275, the paper link. The site's curator records the bound in the problem's remarks as the answer to the third question, but the site labels the problem OPEN, so that remark is not acceptance of the problem and the page lists no reviewed evidence. The paper's proof is not compiled in this corpus.

Dating. The page is dated by the publication year; the issue record gives no day, and the day in the page name is a placeholder.