Problem 38

Erdős Problem #38: declared status 'proved'. Formalized: yes. Does there exist $B\subset\mathbb{N}$ which is not an additive basis, but is such that for every set $A\subseteq\mathbb{N}$ of Schnirelmann density $\alpha$ and every $N$ there exists $b\in B$ such that$$\lvert (A\cup (A+b))\cap \{1,\ldots,N\}\rvert\geq (\alpha+f(\alpha))N$$where $f(\alpha)>0$ for $0<\alpha <1$? The Schnirelmann density is defined by$$d_s(A) = \inf_{N\geq 1}\frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N}.$$ Current best: Erd\H{o}s [Er36c] proved that if $B$ is an additive basis of order $k$ then, for any set $A$ of Schnirelmann density $\alpha$, for every $N$ there exists some integer $b\in B$ such that$$\lvert (A\cup (A+b))\cap \{1,\ldots,N\}\rvert\geq \left(\alpha+\frac{\alpha(1-\alpha)}{2k}\right)N.$$It seems an interesting question (not one that Erd\H{o}s appears to have asked directly, although see [35]) to improve the lower bound here, even in the case $B=\mathbb{N}$. Prize: no. Tags: number theory.