Problem Statement
Let $A\subseteq \{1,\ldots,n\}$ with $\lvert A\rvert \leq n^{1/2}$. Must there exist some $B\subset\mathbb{Z}$ with $\lvert B\rvert=o(n^{1/2})$ such that $A\subseteq B+B$?
Categories:
Additive Combinatorics
Progress
A problem of Erdős and Newman [ErNe77], who proved that there exist $A$ with $\lvert A\rvert\asymp n^{1/2}$ such that if $A\subseteq B+B$ then\[\lvert B\rvert \gg \frac{\log\log n}{\log n}n^{1/2}.\]Resolved by Alon, Bukh, and Sudakov [ABS09], who proved that for any $A\subseteq \{1,\ldots,n\}$ with $\lvert A\rvert \leq n^{1/2}$ there exists some $B$ such that $A\subseteq B+B$ and\[\lvert B\rvert \ll \frac{\log\log n}{\log n}n^{1/2}.\]See also [333].Source: erdosproblems.com/806 | Last verified: January 16, 2026