Khovanskii's theorem on iterated sumsets

Question

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<i \ (x_j=y_j \ \land \ x_i<y_i )$, 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$.

Answer 1

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.