Problem Statement
Let $g(n)$ be minimal such that there exists $A\subseteq \{0,\ldots,n\}$ of size $g(n)$ with $\{0,\ldots,n\}\subseteq A+A$. Estimate $g(n)$. In particular is it true that $g(n)\sim 2n^{1/2}$?
Categories:
Additive Combinatorics
Progress
Such a set is often called a finite additive $2$-basis. A problem of Rohrbach, who proved in [Ro37]\[(2+c)n \leq g(n)^2 \leq 4n\]for some small constant $c>0$. The current best-known bounds are\[(2.181\cdots+o(1))n\leq g(n)^2 \leq (3.458\cdots+o(1))n.\]The lower bound is due to Yu [Yu15], and the upper bound is due to Kohonen [Ko17]. (The disproof of $g(n)\sim 2n^{1/2}$ was accomplished by Mrose [Mr79], who gave a construction implying $g(n)^2 \leq \frac{7}{2}n$.)Source: erdosproblems.com/791 | Last verified: January 16, 2026