Polynomial growth of sumsets in abelian semigroups

Nathanson, Melvyn B.  ; Ruzsa, Imre Z. 

Journal de théorie des nombres de Bordeaux, Tome 14 (2002) no. 2, pp. 553-560

Abstract (VO)

Let $S$ be an abelian semigroup, and $A$ a finite subset of $S$. The sumset $hA$ consists of all sums of $h$ elements of $A$, with repetitions allowed. Let $\left|hA\right|$ denote the cardinality of $hA$. Elementary lattice point arguments are used to prove that an arbitrary abelian semigroup has polynomial growth, that is, there exists a polynomial $p\left(t\right)$ such that $\left|hA\right|=p\left(h\right)$ for all sufficiently large $h$. Lattice point counting is also used to prove that sumsets of the form $h_1{A}_1+\cdots +h_r{A}_r$ have multivariate polynomial growth.

Résumé

Soit $S$ un semi-groupe abélien et $A$ un sous-ensemble fini de $S$. On désigne par $hA$ l’ensemble de toutes les sommes de $h$ éléments de $A$, et par $\left|hA\right|$ son cardinal. On montre, par des arguments élémentaires de comptage de points dans les réseaux, qu’il existe un polynôme $p\left(t\right)$ tel que pour tout entier $h$ assez grand $\left|hA\right|=p\left(h\right)$. Plus généralement, on étend ce résultat aux ensembles $h_1{A}_1\times \cdots +h_r{A}_r$ en obtenant la croissance polynomiale du cardinal en termes des variables $h_1,h_2,\cdots ,h_r$.