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 $A$ be a subset of an Abelian group. The $n$-fold sumset $nA$ of $A$ is the set $\{a_1+\dots+a_n:a_1,\dots,a_n\in 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 $f_A(n)=|nA|$ be like? For example, Plünnecke’s theorem, which has many applications, includes the result that if $|2A|=C|A|$, then $|nA|\leq C^n|A|$ for every $n$.

This paper concerns a remarkable theorem of Khovanskii that asserts that $f_A(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=\bigcup_{r=0}^n\{rm,rm+1,\dots,rm+n\}$. When $n<m$ this has cardinality $(n+1)^2$, but when $n\geq m$ the union is no longer disjoint and $nA$ is simply the set $\{0,1,\dots,(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=\{a_1,\dots,a_m\}$. Then $nA$ is the set of sums $\sum_{i=1}^mx_ia_i$ such that each $x_i$ is a non-negative integer and $x_1+\dots+x_m=n$. If $x=(x_1,\dots,x_m)$ is a sequence of non-negative integers, define its rank $r(x)$ to be $\sum_ix_i$. Let us also write $\phi_A(x)$ for $\sum_ix_ia_i$.

Let $\prec$ be the lexicographical ordering on the $m$-tuples of non-negative integers. Then say that $x$ is unnecessary if there exists $y\prec x$ such that $r(y)=r(x)$ and $\phi_A(y)=\phi_A(x)$, and otherwise that $x$ is useful. Then $nA$ is the number of useful vectors of rank $n$.

Let $\leq$ 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\leq y$, then $y$ is also unnecessary: indeed, if $x'\prec x$ and $\phi_A(x')=\phi_A(x)$, then $y+x'-x\prec y$ and $\phi_A(y+x'-x)=\phi_A(y)$. Thus, for every unnecessary vector $y$ there is a minimal unnecessary vector $x$ such that $x\leq y$.

Let $X$ be the set of minimal unnecessary vectors with respect to the partial order $\leq$. Then $X$ is finite. (To see this, suppose that $X$ is infinite and that $x\in X$. Then for every $y\in X$ there exists some $i$ such that $y_i\leq x_i$, 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\in X$ of the number of vectors $y$ of rank $n$ such that $x\leq y$. For each $x$ this number depends polynomially on $n$ for $n\geq 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 $f_A$ 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\subset\mathbb Z^d$ of size $d+2$ such that $A-A$ generates $\mathbb Z^d$ 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\subset\mathbb Z^d$, showing that polynomial behaviour starts by the time $n$ reaches $(2|A|.\text{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.