Problem Statement
Let $A\subseteq \mathbb{N}$ be a set of density zero. Does there exist a $B$ such that $A\subseteq B+B$ and\[\lvert B\cap \{1,\ldots,N\}\rvert =o(N^{1/2})\]for all large $N$?
Categories:
Number Theory Additive Basis
Progress
Erdős and Newman [ErNe77] have proved this is true when $A$ is the set of squares. In fact, Theorem 2 of [ErNe77] already implies a negative answer to this problem, but this seems to have been overlooked by Erdős and Graham.See also [806].
Source: erdosproblems.com/333 | Last verified: January 14, 2026