Iterated sumsets and Hilbert functions

Abstract

Let A be a finite subset of an abelian group (G,+). For h∈N, let hA=A+…+A denote the h-fold iterated sumset of A. If |A|≥2, understanding the behavior of the sequence of cardinalities |hA| is a fundamental problem in additive combinatorics. For instance, if |hA| is known, what can one say about |(h−1)A| and |(h+1)A|? The current classical answer is given by |(h−1)A|≥|hA|(h−1)/h, a consequence of Plünnecke's inequality based on graph theory. We tackle here this problem with a completely new approach, namely by invoking Macaulay's classical 1927 theorem on the growth of Hilbert functions of standard graded algebras. With it, we first obtain demonstrably strong bounds on |hA| as h grows. Then, using a recent condensed version of Macaulay's theorem, we derive the above Plünnecke-based estimate and significantly improve it in the form |(h−1)A|≥θ(x,h)|hA|(h−1)/h for h≥2 and some explicit factor θ(x,h)>1, where x∈R satisfies x≥h and |hA|=(xh). Equivalently and more simply, |(h−1)A|≥[Formula presented]|hA|. We show that θ(x,h) often exceeds 1.5 and even 2, and asymptotically tends to e≈2.718 as x grows and h lies in a suitable range depending on x.