# Khovanskii's theorem on iterated sumsets

I was watching Gowers video lectures "Introduction to Additive Combinatorics" (my question is about the statement he made at the 21st minute) and came across wonderful theorem due to Khovanskii.

Theorem. Let $$A$$ be an additive set of an abelian group. Let $$f_A(n)=|nA|$$ for each $$n\in \mathbb{N}$$. Then there exist $$n_A\in \mathbb{N}$$ and a polynomial $$p_A$$ such that $$f_A(n)=p_A(n)$$ for all $$n>n_A$$.

I understood the proof very well except only one moment which does not look obvious to me. So I'll give the sketch of the proof and formulate my question in the end.

Sketch of Proof. Assume $$A=\{a_1,\dots,a_r\}$$ and let $$\mathbb{N_0}:=\mathbb{N}\cup \{0\}$$. For each $$x=(x_1,\dots,x_r)\in \mathbb{N}^r_0$$ we write $$\sigma(x)=\sum_{i=1}^{r}x_i$$ and $$\alpha(x)=\sum_{i=1}^{r}a_ix_i$$.

Let $$\prec$$ is a lexicographical order on $$\mathbb{N}^r_0$$: $$x\prec y$$ iff $$\exists i\in [r] \ \forall j, where $$[r]:=\{1,\dots,r\}$$.

Definition. We say that $$x$$ is useless if $$\exists x'\prec x \ (\sigma(x')=\sigma(x) \land \alpha(x')=\alpha(x))$$. Otherwise, $$x$$ is useful.

By definition of $$n$$-fold sumset, we have $$nA=\{\alpha(x): x\in \mathbb{N}^r_0, \sigma(x)=n\}$$. It is not difficult to see that $$nA=\{x\in \mathbb{N}^r_0: x \ \text{is useful}, \ \sigma(x)=n\}$$.

Let $$\leq$$ be the following partial order on $$\mathbb{N}^r_0$$: $$x\leq y$$ iff $$\forall i\in [r] \ (x_i\leq y_i)$$.

Lemma 1. Let $$x'\leq x$$. If $$x'$$ is useless, then $$x$$ is useless.

Proof of Lemma 1. Since $$x$$ is useless, then $$\exists x'\prec x$$ with $$\sigma(x')=\sigma(x)$$ and $$\alpha(x')=\alpha(x)$$. Let $$y'=y+x'-x$$ and this equals $$y-x+x'$$. Hence $$y'\in \mathbb{N}^r_0$$. Also we notice that $$y'\prec y$$. From the linearity of $$\sigma$$ and $$\alpha$$ it follows that $$\sigma(y')=\sigma(y)$$ and $$\alpha(y')=\alpha(y)$$.

Lemma 2 (Dickson's lemma). Let $$U\subset \mathbb{N}^r_0$$. Then the set of minimal elements of $$U$$ is finite.

Remark: Let $$X:=\{x'\in \mathbb{N}^r_0: x' \ \text{is minimal (with respect to the partial order} \leq),\ x' \ \text{is useless}\}.$$ It follows from the lemma that an element $$x\in \mathbb{N}_0^r$$ is useless if and only if there is an element $$x'\in X$$ such that $$x'\leq x$$.

Lemma 3. Let $$x'\in \mathbb{N}^r_0$$ and $$\sigma(x')\leq n$$. If $$C(x',n):=\{x\in \mathbb{N}^r_0: \sigma(x)=n,\ x'\leq x\}$$, then $$|C(x',n)|=\binom{n-\sigma(x')+r-1}{r-1}$$.

Using remark we see that $$nA=C(0,n)\setminus \cup_{x'\in X}C(x',n)$$ and hence $$|nA|=|C(0,n)|-|\cup_{x'\in X}C(x',n)|.$$

By inclusion-exclusion we can write $$|nA|=\underbrace{|C(0,n)|}_{=\binom{n+r-1}{r-1}}+\sum_{\substack{Y\subset X \\ Y\neq \varnothing}}(-1)^{|Y|}\left|\bigcap\limits_{x'\in Y} \mathcal{C}(x',n) \right|.$$

But $$\cap_{x'\in Y} \mathcal{C}(x',n) =\mathcal{C}(\max_{x'\in Y}{x'},n)$$, where $$\max_{x'\in Y}{x'}\in \mathbb{N}^r_0$$ such that its $$i$$th coordinate is $$\max_{x'\in Y} x'_i$$ for each $$i\in [r]$$. Therefore, each inclusion-exclusion term depends polynomially on $$n$$ once $$n\geq \sigma\big(\max_{x'\in X} x'\big)$$. QED.

So now let me ask my question please.

Question: In the remark I wrote the following statement:

$$x\in \mathbb{N}_0^r$$ is useless if and only if there is an element $$x'\in X$$ such that $$x'\leq x$$.

The $$\Leftarrow$$ part follows from Lemma 1.

What about $$\Rightarrow$$ part? It is not so obvious to me. However, this is what I've tried so far. If $$x$$ is minimal (wrt $$\leq$$ order), then one can take $$x':=x$$. If $$x$$ is not minimal, then after finitely many steps we reach minimal element $$y$$ such that $$y\leq x$$ and $$y\neq x$$. How to show that $$y$$ is useless? This is what we need in order to show that $$y\in X$$.

• Looks like the relevant video is: youtube.com/watch?v=anQbHNIVPQ4. Not sure about your detailed proof, but it feels to me like you should also be able to prove this in an abstract way using the Hilbert series/Hilbert polynomial of a graded algebra (see en.wikipedia.org/wiki/Hilbert_series_and_Hilbert_polynomial ) Commented Aug 8, 2023 at 1:41
• @SamHopkins, I think one can prove it in a more direct way than using abstract machinery. This theorem can be found on Bloom's webpage(thomasbloom.org/notes/hovanskii.html) and in Ruzsa's book (math.cmu.edu/users/af1p/Teaching/AdditiveCombinatorics/…). None of them use something abstract.
– RFZ
Commented Aug 8, 2023 at 2:31
• Ah, but on the other hand I just looked up the original paper by Khovanskii, and he indeed uses graded modules and Hilbert polynomials. Commented Aug 8, 2023 at 2:41
• @Sam Hopkins, yes indeed, but the proof which I wrote above is elementary and is different than the proof in the Khovanskii’s original paper.
– RFZ
Commented Aug 8, 2023 at 3:01
• if the vide in the comments is the one you referred to please put a link to it in the question Commented Aug 8, 2023 at 4:00

## 1 Answer

Your idea is essentially correct. Suppose $$x\in\mathbb N_0^r$$ is useless. Then either there does not exist any useless $$x_1\in\mathbb N_0^r$$ satisfying $$x_1\le x$$, in which case $$x\in X$$ and trivially $$x\le x$$ so we are done; or there does exist useless $$x_1\in\mathbb N_0^r$$ satisfying $$x_1\le x$$. If $$x_1\in X$$ we are done, otherwise we repeat the argument (using the crucial fact that $$x_1$$ is useless by hypothesis), ending with a chain $$x_n\le\dots\le x_1\le x$$ of finite length (since $$\mathbb N_0^r$$ is well-ordered with respect to $$\le$$) where each $$x_i$$ is useless. Now since there does not exist useless $$y\le x_n$$, it follows that $$x_n\in X$$ with $$x_n\le x$$, proving the implication.

• Thank you very much! Now it makes sense to me. +1
– RFZ
Commented May 3 at 19:37