How small can "spanning sumsets" of $[n]$ be?

Question

Let $[n]$ denote the natural numbers $1$ through $n$. Let's say a subset $X \subset [n]$ is a spanning sumset if $\{x+y: x,y \in X\} = [n] \setminus \{1\}$. I'm interested in studying spanning sumsets of minimal possible size. In particular, is there either an asymptotic or exact expression for the minimal size of a spanning sumset? Is there an algorithm which can be used to find them? Or, in general, some sort of characterization?

One simple observation is that $\{x+y: x,y \in X\}$ has at most $\frac{|X|(|X|+1)}{2}$ distinct sums, and if $\frac{|X|(|X|+1)}{2} \geq n-1$, then $|X| = \Omega(\sqrt{n})$. Can this lower bound be attained, however? That is to say, for general $n$ can we find a spanning sumset of size $\Theta(\sqrt{n})$? Or even just $o(n)$?

Answer 1

Let $S_k=\{1,2,3,...,k,2k,3k,4k,...,(k-1)k\}$.

Then $S_k$ is a spanning set for $[k^2]$.

For a given $n$ if we let $k=\lceil \sqrt{n} \rceil$, then $S_k$ will be a spanning set of $[n]$ with size $2k-2\approx 2\sqrt{n}$.

Answer 2

You are looking for finite additive bases. The maximum $n$ for given basis size is A001212, where you will find pointers to literature. One algorithm for finding such bases is by Challis (1993).

Exact expressions are not known (except for small instances), but there are asymptotic upper and lower bounds. Yu showed in 2015 that asymptotically $n/k^2 \le 0.4585$ (where $k$ is the basis cardinality), and I showed in 2017 that there are arbitrarily large bases with $n/k^2 \ge 0.2891$. So the truth is somewhere between Yu and me.

Bibliography

Challis, M. F., Two new techniques for computing extremal (h)-bases (A_ k), Comput. J. 36, No. 2, 117-126 (1993). ZBL0774.11008.

Kohonen, Jukka, An improved lower bound for finite additive 2-bases, J. Number Theory 174, 518-524 (2017). ZBL1359.11013.

Yu, Gang, A new upper bound for finite additive (h)-bases, J. Number Theory 156, 95-104 (2015). ZBL1395.11028.