2025/10/27 by Isaac Rajagopal, Rajagopal, Isaac · 2 citations
#Limits and Structures in Graph Theory #Analytic Number Theory Research #Advanced Mathematical Identities
paper · pdf · doi:10.19086/da.165102
Let A be a set of n integers. If we write the elements of A in increasing order as a1,a2,…,an, then the sequence a1+a1,a1+a2,…,a1+an,a2+an,…,an+an 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 ai+aj=aj+ai 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 ai=3i 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 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 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 \binomh+k-1h, 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≥ 3, and Tang-Xing identified a second and third interval. This paper shows that there is a sequence of missing intervals I1,…,Ir that form a Freiman-homomorphic image of a triangle, in the sense that the left end-points and right end-points of the Ij form arithmetic progressions and the lengths of the Ij 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≤ 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](https://gowers.wordpress.com/2026/05/08/a-recent-experience-with-chatgpt-5-5-pro/#more-6666) co-written by the author and Timothy Gowers (who suggested the problem to ChatGPT).