= Polynomial growth of iterated sumsets
{title2=$|\ell A|\leq K^2\binom{\ell+q-2}{q-1}|A|,\quad q\leq K^5$}
For a finite nonempty subset of an <abelian group> with <doubling constant> at most $K$, the <Plünnecke-Ruzsa inequality> gives $|3A-2A|\leq K^5|A|$. Applying the <Ruzsa covering lemma> to $2(A-A)$ using $A$ gives $2T\subseteq D+T$ for $T=A-A$ and $|D|=q\leq K^5$. Thus $\ell T\subseteq(\ell-1)D+T$, and counting multiplicities in the finite set $D$ proves the displayed polynomial bound. For fixed $K>1$, it is eventually at most $K^{\epsilon\ell}|A|$ for every $\epsilon>0$.
Back to article page
