Problem 791

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}$ ?

Source: erdosproblems.com/791

Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

Open, the site's label. The best source-supported bounds are

(2.181\ldots+o(1))\,n\ \le\ g(n)^2\ \le\ (3.458\ldots+o(1))\,n,

the upper bound from Kohonen's equation (1) [Ko17] (J. Number Theory 174 (2017), refereed; result page), $\liminf n(k)/k^2\ge85/294$ , and the lower bound from Yu's $\limsup n(k)/k^2\le0.4585$ [Yu15] (J. Number Theory 156 (2015), refereed, not held; quoted from [Ko17], p. 1, and the site), converted on this page; each is an accepted partial claim on its claim page (Kohonen, Yu). The site's "in particular" question is answered in the negative. The first refutation in print is Hämmerer and Hofmeister's [HH76] (J. Reine Angew. Math. 1976), $n(2,k)>\frac5{18}k^2$ with $k$ counting the positive elements, so $g(n)^2\le(\frac{18}5+o(1))n$ ; it is an accepted partial claim on its claim page (Hämmerer and Hofmeister, 1976). Mrose's construction, received in April 1975 and the one the site credits, gives the stronger $g(n)^2\le\frac72n$ [Mr79] (equation (3), printed p. 118; result page; it is the $\liminf n(k)/k^2\ge2/7$ that [Ko17], p. 1, quotes for Mrose), and Kohonen's theorem gives $g(n)^2\le(3.459+o(1))n<4n$ directly, so $g(n)\le(1.860+o(1))\sqrt n$ and $g(n)\sim2\sqrt n$ is false; Mrose's refutation is also an accepted partial claim on its claim page (Mrose, 1979). Read on this page, the label concerns the estimate: the wording is a compound of an estimate, which has no truth value, and a displayed particular guess whose negative answer is recorded on the claim pages. Rohrbach's original bounds, the site's $(2+c)n\le g(n)^2\le4n$ [Ro37], are these: Satz 3 (printed p. 5), $g(n)<2\sqrt n$ for $n>1$ , by the explicit basis (6) (result page); the Folgerung to Satz 6 (p. 15), $n\le k^2/2$ for every $2$ -basis of $k$ elements for $n$ , so $g(n)^2\ge2n$ ; and inequality (47) (p. 18), $n<0.4992\,k^2$ for every such basis once $k$ is large, so $g(n)^2>(2.0032\ldots)n$ for large $n$ , the " $(2+c)n$ " with $c=0.0032$ (result page); these are an accepted partial claim on its claim page (Rohrbach, 1937), and the proofs of §§ 3--5 behind the lower bounds were not checked. No result determining the constant was found in the search whose scope the Current assessment records; for the estimate this is a bounded negative finding, not a certificate of openness.

Er73: Erdős, P., Problems and results on combinatorial number theory. A survey of combinatorial theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) (1973), 117--138; Section 9, printed pp. 130--131. Library home: Erdos 1973.
Ro37: Rohrbach, H., Ein Beitrag zur additiven Zahlentheorie. Math. Z. 42 (1937), no. 1, 1--30, DOI 10.1007/BF01160061 (Crossref record read); received 9 April 1936. The problem and its inverse formulation $n_2(k)$ , printed p. 4; Satz 2 with (6)--(9) and Satz 3, p. 5, and the proof of Satz 3, p. 6; the conjecture $n_2(k)=k^2/4+O(k)$ , p. 9; Satz 6, p. 11, and its Folgerung, pp. 14--15; Satz 7 and inequality (47), p. 18. Library home: Rohrbach 1937.
Mr79: Mrose, A., Untere Schranken für die Reichweiten von Extremalbasen fester Ordnung. Abh. Math. Sem. Univ. Hamburg 48 (1979), no. 1, 118--124, DOI 10.1007/BF02941296 (Crossref); received 25 April 1975. Definitions and equation (3), printed p. 118; the order-2 basis $B_2$ , p. 121; the parameters deriving (3) and Satz 2, p. 123. Library home: Mrose 1979.
HH76: Hämmerer, N. and Hofmeister, G., Zu einer Vermutung von Rohrbach. J. Reine Angew. Math. 286/287 (1976), 239--247, DOI 10.1515/crll.1976.286-287.239 (Crossref: issued 1976-11-01; Zbl 0332.10032). Definitions, p. 239; Rohrbach's conjecture as the paper states it, p. 240; inequality (1), printed p. 241. Not cited by the site.
Yu15: Yu, G., A new upper bound for finite additive $h$ -bases. J. Number Theory 156 (2015), 95--104, DOI 10.1016/j.jnt.2015.04.007 (Crossref record read; the site's reference text gives no volume). Not held; quoted from [Ko17], p. 1, and the site.
Ko17: Kohonen, J., An improved lower bound for finite additive 2-bases. arXiv:1606.04770v2 (10 January 2017, "Author's final version"), 6 pp.; J. Number Theory 174 (2017), 518--524, DOI 10.1016/j.jnt.2016.11.011 (Crossref record read; not compared). Equation (1) and the definitions, p. 1. Library home: Kohonen 2017.
OEIS: Sequence A066063 (J. W. Layman, 2001; revision 29, last modified 31 May 2026), "Size of the smallest subset $S$ of $T=\{0,1,2,\ldots,n\}$ such that each element of $T$ is the sum of two elements of $S$ ": $1,2,2,3,3,4,4,4,4,5,\ldots$ for $n\ge0$ , with the comment that $\binom{a(n)+1}2\ge n+1$ ; JSON record read. Its links include Nathanson, M. B., Problems in additive number theory, VII: The structure of additive $h$ -bases for $n$ , arXiv:2605.26425 (2026), not held.
WZ26: Weltge, S. and Zyhalko, K., On the number of finite additive 2-bases. arXiv:2605.19449v2 (May 2026); the exponential count of finite additive 2-bases, per its abstract (arXiv API). Context.

Problem 791

Status

Proof claims

Discussion