Sets of integers with few sums

Question

Let $S$ be a finite set of integers. Denote by $S^{\leq k}$ the set $\{a_1+\dots+a_\ell : \ell\leq k, a_1,\dots,a_\ell\in S\}$ of sums of at most $k$ elements from $S$. What are best/worst cases for the size of $S^{\leq k}$ in function of $|S|$ and $k$? A trivial upper bound on this number is $|S|^k$. But we can do exponentially better: if $S$ is an arithmetic progression, then we have $|S^{\leq k}| = O(k^2 |S|)$. What other kinds of bounds can we achieve asymptotically? Can we achieve something that is linear in $k$ and $|S|$?

Answer 1

The lower bound is attained by arithmetic progressions containing $0$, which have $|S^{\le k}| = k(|S|-1)+1$. Moreover, any set attaining this lower bound must be an arithmetic progression.

Freiman's theorem, one of the highlights of additive combinatorics, gives stability for this result, saying that any set $S $ with $|S + S| \le C|S|$ must be close to a generalised arithmetic progression. This means that, in some sense, being similar to an arithmetic progression is the only reason a set should have only a linear number of sums.

For the upper bound, note that commutativity of addition implies that the order within the $k$-tuple of summands doesn't matter. Hence the number of sums is at most the number of selections of at most $k $ elements from $S $ with repetition, which is $\binom {|S|+k}{k} $.

As observed by D Poole, you can construct sets attaining this bound (that is, without any nontrivial relations between the sums) by taking, $S = \{ 1, b, b^2, b^3, ..., b^{|S|-1} \} $, where $b\ge k $. Writing the sums in base-$b $, we find that the choice of summands is uniquely determined by the digits of the sum.

Here of course the set $S$ depends on $k $. If we instead think of $S$ as being fixed and $k$ large, then note that $S^{\le k} \subseteq [\min (0,k \min S), \max (0, k \max S)]$, so that gives an alternative upper bound that is linear in $k $ (rather than the previous one, which is polynomial (with degree $|S|$)).