Erdős Problem #791

declared status 'open'. Formalized: no. 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}$? Current best: 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$.) References [Ko17] Kohonen, Jukka, An improved lower bound for finite additive 2-bases. [Yu15] Yu, Gang, A new upper bound for finite additive {$h$}-bases. Prize: no. OEIS: A066063. Tags: additive combinatorics.

Notation is rendered from the stored source. The pinned checkout remains the exact record.