Khovanskii’s theorem and effective results on sumset structure
Khovanskii’s theorem and effective results on sumset structure, Discrete Analysis 2021:27, 25 pp.
Let be a subset of an Abelian group. The -fold sumset of is the set . Much of additive combinatorics is concerned, either directly or indirectly, with the behaviour of the cardinality of and how it relates to the structure of . In particular, a source of many interesting problems is the following very general question: what can the function be like? For example, Plünnecke’s theorem, which has many applications, includes the result that if , then for every .
This paper concerns a remarkable theorem of Khovanskii that asserts that depends polynomially on when is large enough. To get a feel for the statement, and in particular to see why needs to be large, consider the example where . Then . When this has cardinality , but when the union is no longer disjoint and is simply the set , so it has cardinality .
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 . Then is the set of sums such that each is a non-negative integer and . If is a sequence of non-negative integers, define its rank to be . Let us also write for .
Let be the lexicographical ordering on the -tuples of non-negative integers. Then say that is unnecessary if there exists such that and , and otherwise that is useful. Then is the number of useful vectors of rank .
Let be the usual partial order on the -tuples of non-negative integers. It is not hard to check that if is unnecessary and , then is also unnecessary: indeed, if and , then and . Thus, for every unnecessary vector there is a minimal unnecessary vector such that .
Let be the set of minimal unnecessary vectors with respect to the partial order . Then is finite. (To see this, suppose that is infinite and that . Then for every there exists some such that , and by the pigeonhole principle we can therefore find infinitely many that agree in some coordinate and apply induction to reach a contradiction.) Therefore, the number of unnecessary vectors of rank is the union over all of the number of vectors of rank such that . For each this number depends polynomially on for , as does the number of vectors of rank , 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 and the polynomial that eventually agrees with, the structure of the sumsets for large , and how large 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 of size such that generates additively. In addition, if the convex hull of 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 , showing that polynomial behaviour starts by the time reaches . 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 times the volume of the convex hull of : 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.