Hovanskii's theorem

This note concerns a remarkable result of Hovanskii on set addition in commutative groups. Fix some abelian group $G$ - not necessarily finite itself, but when we mention subsets $A\subset G$ these will always be finite subsets. Hovanskii's result concerns the size of iterated sumsets $$ nA = \{ a_1+\cdots +a_n: a_1,\ldots,a_n\in A\},$$ for a fixed finite set $A$, as a function of $n$. Since we can describe an element of $nA$ by saying how many times each element $a\in A$ appears in the sum, the size of $nA$ is trivially at most $n^{\lvert A\rvert}$ (it is almost as trivial to prove the upper bound $\ll_{\lvert A\rvert}n^{\lvert A\rvert-1}$). In particular, for fixed $A$, the size of $nA$ is bounded above by some polynomial in $n$. The remarkable result of Hovanskii, which I did not believe at all when I first heard it, is that there is some polynomial $f(n)$ which agrees exactly with $\lvert nA\rvert$ for all sufficiently large $n$. This is, of course, a much stronger fact.

A Proof

An alternative proof of Hovanskii's theorem was given by Nathanson and Ruzsa [NaRu], who in fact proved a multivariable generalisation. We present the Nathanson and Ruzsa proof, in the one variable case, taken from the exposition of Ruzsa [Ru].

Let $A=\{a_1,\ldots,a_m\}$. Every element of $nA$ can be described by a vector $(x_1,\ldots,x_m)$ where each $x_i\geq 0$ and $\sum x_i=n$, identifying this vector with $\sum x_ia_i$. For brevity, let the set of such vectors in $\mathbb{N}^m$ be denoted by $V_n$. The complication, of course, is that several vectors can identify the same element of $nA$ - indeed, this must happen quite frequently, or else the size of $nA$ would grow exponentially in $n$. We note that the size of $V_n$ is $\binom{n+m-1}{m-1}$, which is a polynomial in $n$. The challenge for Hovanskii's theorem is to somehow show that the 'correction' to this polynomial, required by the fact that many vectors in $V_n$ are redundant in describing $nA$, is itself a polynomial.

The first task is to somehow select a representative vector from each equivalence class of vectors. We will do so using a total ordering on the set of integer vectors, and then choosing the minimum element of each equivalence class. One obvious ordering on integer vectors is that $\mathbf{x}\leq \mathbf{y}$ if and only if $x_i\leq y_i$ for all $1\leq i\leq m$. This is not a total ordering, which makes it inadequate for our purposes. It will shortly be important, however, that our total ordering $\prec$ satisfy \[\mathbf{y}\prec \mathbf{x}\textrm{ and }0\leq \mathbf{z}\textrm{ implies }\mathbf{y}+\mathbf{z} \prec \mathbf{x}+\mathbf{z}.\] One such total ordering is the lexicographic ordering: $\mathbf{x}\prec \mathbf{y}$ means that there is some $1\leq i\leq m$ such that $x_j=y_j$ for all $j < i$ and $x_i < y_i$.

From each equivalence class select the vector which comes first in this ordering, which we will call a useful vector. A useless vector is one which is not useful - that is, $\mathbf{x}\in V_n$ is useless if there is another $\mathbf{y}\in V_n$ such that $\mathbf{y}\prec\mathbf{x}$ which induces the same element of $nA$. A crucial observation is that being useless is 'hereditary', in that if $\mathbf{x}$ is useless and $\mathbf{x}\leq \mathbf{x}'$ then $\mathbf{x}'$ is also useless. This holds since if $\mathbf{y}\prec\mathbf{x}$ but induces the same sum then $\mathbf{y}+\mathbf{x}'-\mathbf{x}$ induces the same sum as $\mathbf{x}'$ (note that this makes essential use of the commutativity of $G$), and $\mathbf{y}+\mathbf{x}'-\mathbf{x}\prec \mathbf{x}'$.

This leads to the definition of a primitive useless vector: a useless vector $\mathbf{z}$ such that if $\mathbf{x}<\mathbf{z}$ then $\mathbf{x}$ is not useless. Let the set of primitive useless vectors be $Z$. We have shown that a vector is useless if and only if there is some $\mathbf{z}\in Z$ such that $\mathbf{z}\leq \mathbf{x}$.

We want to count the size of $nA$, or equivalently, the number of useful vectors in $V_n$. Thanks to the above observations, we can do this by inclusion-exclusion. That is, we begin with all vectors $\mathbf{x}\in V_n$, discard those which have at least one $\mathbf{z}\in Z$ preceding it, put back those which have at least two, and so on. This gives the following formula: \[\lvert nA\rvert = \sum_{W\subset Z}(-1)^{\lvert W\rvert} \sum_{\mathbf{x}\in V_n}\prod_{\mathbf{z}\in W}1_{\mathbf{z}\leq \mathbf{x}}.\]

The condition $\prod_{\mathbf{z}\in W}1_{\mathbf{z}\leq \mathbf{x}}$ can be summarised by the single inequality $\mathbf{z}_W\leq \mathbf{x}$, where $\mathbf{z}_W$ is formed by taking the maximum in each coordinate. If $t_W$ is the sum of these coordinates, then the inner sum over $\mathbf{x}$ is exactly the size of $V_{n-t_W}$. As mentioned above, this is a fixed polynomial in $n$ depending only on $t_W$ (at least, assuming $n\geq t_W$, or else it is identically $0$). If we take $n$ large enough so that it is larger than $t_W$ for all such $W\subset Z$, then we have shown that \[\lvert nA\rvert = \sum_{W\subset Z}(-1)^{\lvert W\rvert} \binom{n-t_W+m-1}{m-1},\] which is a polynomial in $n$.

The proof is almost complete, but we have glossed over an important point so far - we need to establish that $Z$ is finite, for of course an infinite sum of finite polynomials need not be a polynomial itself. This is a classical result, however, since the elements of $Z$ are incomparable by definition under the $\leq$ ordering. We now invoke Dickson's lemma: there is no infinite set of vectors in $\mathbb{N}^m$ which are incomparable under this ordering. We give a proof of this lemma below. Dickson's lemma provides no bounds for the size of this set, however, so we have no knowledge even about the size of $Z$, let alone its inner structure. This is the reason that the polynomial provided by Hovanskii's theorem is so mysterious.

Discussion

• Hovanskii's original paper in fact proved a similar result for $\lvert B+nA\rvert$ for any fixed set $B$. The proof above can be easily modified to take this into account.
• If $G$ has no elements of finite order then we can describe the degree and leading coefficient of $f(n)$. The degree of $f(n)$ is given by the 'rank of $A$', defined as the $d$ such that \[\left\{\sum_{a\in A}n_aa: n_a\in \mathbb{Z}\textrm{ and }\sum n_a=0\right\} \cong \mathbb{Z}^d.\] The leading coefficient of $f(n)$ is $\textrm{Vol}(N_A)$ where $N_A\subset \mathbb{R}^d$ is the reduced Newton polyhedron of $A$, the convex hull in $\mathbb{Z}^d$ of the image of $A-a$ for some $a\in A$.
• The original proof of Hovanskii in [Ho] seems to me, at a fundamental level, to be the same as the proof of Nathanson and Ruzsa given above; at least in that the fundamental source of the explicit control in Hovanskii's proof comes from invoking Hilbert's basis theorem, which is equivalent to Dickson's lemma used in the Nathanson and Ruzsa proof.
• This theorem trivially fails if $G$ is not commutative, since then the size of $nA$ can grow eternally exponentially with $n$. Ruzsa gives the following as an open problem, however: if $\lvert nA\rvert$ is bounded above by some polynomial in $n$, must it eventually agree exactly with some polynomial in $n$?

Proof of Dickson's lemma

We use induction on $m$. The case $m=1$ is obvious, since $\leq$ is actually a total ordering on $\mathbb{N}$. Let $m\geq 2$ and assume the lemma holds for $m-1$, and suppose that $Z\subset \mathbb{N}^m$ is a set of incomparable vectors. Let $$ Z' = \{ \mathbf{x}\in \mathbb{N}^{m-1} : (\mathbf{x},x)\in Z\textrm{ for some }x\in\mathbb{N}\}.$$ Notice that each $\mathbf{x}\in Z'$ can be extended uniquely to an element of $Z$, otherwise we'd have two comparable vectors. $Z'$ itself may not be incomparable, so let \[Z''=\{\mathbb{x}\in Z' : \textrm{ there is no }\mathbf{y}\in Z'\textrm{ such that }\mathbf{y}< \mathbf{x}\}\] which is incomparable, and hence finite, say $Z''=\{\mathbf{x}_1,\ldots,\mathbf{x}_s\}$. Note that, since there cannot be an infinitely decreasing chain in the $\leq$ ordering, for any $\mathbf{x}\in Z'$ there exists $\mathbf{y}\in Z''$ such that $\mathbf{y}\leq \mathbf{x}$. For each $1\leq i\leq s$ there is $x_i\geq 0$ such that $(\mathbf{x}_i,x_i)\in Z$. Let $z=\max(x_1,\ldots,x_s)$. We now note that $z$ must in fact be an upper bound for the final coordinate of each element of $Z$ - for otherwise, if $(\mathbf{y},y)\in Z$ with $y > z$ and $\mathbf{x}_i\in Z''$ is such that $\mathbf{x}_i\leq \mathbf{y}$ then $(\mathbf{y},y) > (\mathbf{x}_i,x_i)$, which contradicts the incomparability of $Z$.

The lemma now follows, for if we fix the last coefficient of the vector the corresponding fibre of $Z$ is an incomparable subset of $\mathbb{N}^{m-1}$, and hence finite. As a subset of a finite union of finite sets, $Z$ itself must be finite.