Khovanskii’s theorem and effective results on sumset structure
- Mathematical Institute, University of Oxford
- More about Michael J. Curran
- Mathematics and Statistics, Williams College
- More about Leo Goldmakher
Editorial introduction
Khovanskii’s theorem and effective results on sumset structure, Discrete Analysis 2021:27, 25 pp.
Let A be a subset of an Abelian group. The n-fold sumset nA of A is the set {a1+⋯+an:a1,…,an∈A}. Much of additive combinatorics is concerned, either directly or indirectly, with the behaviour of the cardinality of nA and how it relates to the structure of A. In particular, a source of many interesting problems is the following very general question: what can the function fA(n)=|nA| be like? For example, Plünnecke’s theorem, which has many applications, includes the result that if |2A|=C|A|, then |nA|≤Cn|A| for every n.
This paper concerns a remarkable theorem of Khovanskii that asserts that fA(n) depends polynomially on n when n is large enough. To get a feel for the statement, and in particular to see why n needs to be large, consider the example where A={0,1,m,m+1}. Then nA=⋃nr=0{rm,rm+1,…,rm+n}. When n<m this has cardinality (n+1)2, but when n≥m the union is no longer disjoint and nA is simply the set {0,1,…,(n+1)m}, so it has cardinality (n+1)m+1.
Khovanskii’s theorem has a number of different proofs. The following combinatorial proof, which we briefly sketch, is due to Melvyn Nathanson and Imre Ruzsa.
Let A={a1,…,am}. Then nA is the set of sums ∑mi=1xiai such that each xi is a non-negative integer and x1+⋯+xm=n. If x=(x1,…,xm) is a sequence of non-negative integers, define its rank r(x) to be ∑ixi. Let us also write ϕA(x) for ∑ixiai.
Let ≺ be the lexicographical ordering on the m-tuples of non-negative integers. Then say that x is unnecessary if there exists y≺x such that r(y)=r(x) and ϕA(y)=ϕA(x), and otherwise that x is useful. Then nA is the number of useful vectors of rank n.
Let ≤ be the usual partial order on the m-tuples of non-negative integers. It is not hard to check that if x is unnecessary and x≤y, then y is also unnecessary: indeed, if x′≺x and ϕA(x′)=ϕA(x), then y+x′−x≺y and ϕA(y+x′−x)=ϕA(y). Thus, for every unnecessary vector y there is a minimal unnecessary vector x such that x≤y.
Let X be the set of minimal unnecessary vectors with respect to the partial order ≤. Then X is finite. (To see this, suppose that X is infinite and that x∈X. Then for every y∈X there exists some i such that yi≤xi, and by the pigeonhole principle we can therefore find infinitely many y that agree in some coordinate and apply induction to reach a contradiction.) Therefore, the number of unnecessary vectors y of rank n is the union over all x∈X of the number of vectors y of rank n such that x≤y. For each x this number depends polynomially on n for n≥r(x), as does the number of vectors of rank n, and therefore by the inclusion-exclusion formula the theorem follows.
The above argument is ineffective, as was the original proof of Khovanskii, and it has been an interesting challenge to understand the relationship between A and the polynomial that fA eventually agrees with, the structure of the sumsets nA for large n, and how large n needs to be for the polynomial growth and structure to appear.
This paper contains several important new results concerning these questions, proved in a conceptually neat way. The methods are geometric, and have a strong connection with previous work on Ehrhart theory, but this is the first instance where they have been applied to obtain effective bounds on sumsets.
Their results are essentially the final word on small sets – that is, sets A⊂Zd of size d+2 such that A−A generates Zd additively. In addition, if the convex hull of A is a simplex, the authors give a concrete description of how the sumsets behave eventually, with effective bounds on when this transition occurs. Although the bounds obtained are probably not sharp, they are not too far off.
These results are proved by considering the d+1 dimensional cone that contains all sumsets simultaneously, and then explicitly calculating and bounding various aspects of this cone (in particular how it is generated by points of low height). The methods are likely to be of lasting value to the field.
In a subsequent development, Andrew Granville, George Shakan and Aled Walker have obtained an effective version of Khovanskii’s theorem for all sets A⊂Zd, showing that polynomial behaviour starts by the time n reaches (2|A|.width(A))(d+4)|A|. However, this is not yet the end of the story, as the true bound is likely to be significantly smaller. One possibility (which Granville, Shakan and Walker hesitate to call a conjecture) is an upper bound of d! times the volume of the convex hull of A: there are examples that get close to this bound, but no known examples that exceed it.
This video is of a talk by one of the authors about the results in the paper.