Possible Sizes of Sumsets

Let \(A\) be a set of \(n\) integers. If we write the elements of \(A\) in increasing order as \(a_1,a_2,\dots,a_n\), then the sequence \(a_1+a_1,a_1+a_2,\dots,a_1+a_n,a_2+a_n,\dots,a_n+a_n\) is strictly increasing, and therefore the sumset \(A+A\) has size at least \(2n-1\). It is an easy exercise to prove that equality holds if and only if \(A\) is an arithmetic progression. In the other direction, since \(a_i+a_j=a_j+a_i\) for every \(i\) and \(j\), \(A+A\) has size at most \(n(n+1)/2\), and equality holds for any suitably dissociated set: for example, it holds if \(a_i=3^i\) for each \(i\).

Erdős and Szemerédi noted that one could use appropriate mixtures of these two extreme constructions to show that all sumset sizes between \(2n-1\) and \(n(n+1)/2\) could be achieved, an observation that led Nathanson to ask what happens for higher sumsets. That is, he defined \(\mathcal{R}(h,k)\) to be the set of all possible values of \(|hA|\), where \(A\) is a set of \(k\) integers and \(hA\) denotes the \(h\)-fold sumset of \(A\), and he asked what \(\mathcal{R}(h,k)\) is for general \(h\) and \(k\).

The analogues of the two extreme bounds just mentioned for \(h=2\) are \(hk-h+1\) and \(\binom{h+k-1}{h}\), again achieved by arithmetic progressions at one end and dissociated sets at the other. However, what goes on in between is more subtle, since it is not true that every cardinality in between can be achieved. In particular, Tang-Xing and Schinina independently identified an interval of missing cardinalities for each \(h,k\geq 3\), and Tang-Xing identified a second and third interval. This paper shows that there is a sequence of missing intervals \(I_1,\dots,I_r\) that form a Freiman-homomorphic image of a triangle, in the sense that the left end-points and right end-points of the \(I_j\) form arithmetic progressions and the lengths of the \(I_j\) decrease from \(r\) to \(1\), and the author conjectures that every missing cardinality belongs to one of these intervals whenever \(k>h\). (The statement is not true in general if \(k\leq h\).)

The main result of the paper is that for each fixed \(h\), this conjecture holds for sufficiently large \(k\). As when \(h=2\), the proof works by combining dense and sparse sets, but the way this is done is far subtler and less obvious than it is when \(h=2\).

As well as asking about the possible cardinalities of \(hA\), one can also ask about the sets that achieve those cardinalities. For example, define \(N(h,k)\) to be the smallest integer \(N\) such that every cardinality in \(\mathcal R(h,k)\) can be achieved by a set \(A\) of diameter at most \(N\). What can one say about the dependence of \(N(h,k)\) on \(h\) and \(k\)?

A consequence of the results in the paper is that for each fixed \(h\), \(N(h,k)\) grows at most exponentially in \(k\), a result that was previously obtained by different methods by Nathanson. This was recently improved to a polynomial dependence by ChatGPT 5.5 Pro, making heavy use of the ideas in this paper but adding some new ideas of its own. More details about ChatGPT’s result can be found in a blog post co-written by the author and Timothy Gowers (who suggested the problem to ChatGPT).