Khovanskii's theorem and effective results on sumset structure

Abstract

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