Polynomial growth of sumsets in abelian semigroups
Journal de théorie des nombres de Bordeaux, Volume 14 (2002) no. 2, p. 553-560

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 |hA| 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(t) such that |hA|=p(h) for all sufficiently large h. Lattice point counting is also used to prove that sumsets of the form h 1 A 1 ++h r A r have multivariate polynomial growth.

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 |hA| son cardinal. On montre, par des arguments élémentaires de comptage de points dans les réseaux, qu’il existe un polynôme p(t) tel que pour tout entier h assez grand |hA|=p(h). Plus généralement, on étend ce résultat aux ensembles h 1 A 1 ×+h r A r en obtenant la croissance polynomiale du cardinal en termes des variables h 1 ,h 2 ,,h r .

@article{JTNB_2002__14_2_553_0,
     author = {Nathanson, Melvyn B. and Ruzsa, Imre Z.},
     title = {Polynomial growth of sumsets in abelian semigroups},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {14},
     number = {2},
     year = {2002},
     pages = {553-560},
     zbl = {1077.11014},
     mrnumber = {2040693},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2002__14_2_553_0}
}
Nathanson, Melvyn B.; Ruzsa, Imre Z. Polynomial growth of sumsets in abelian semigroups. Journal de théorie des nombres de Bordeaux, Volume 14 (2002) no. 2, pp. 553-560. http://www.numdam.org/item/JTNB_2002__14_2_553_0/

[1] D. Cox, J. Little, D. O'Shea, Ideals, Varieties, and Algorithms. Springer-Verlag, New York, 2nd edition, 1997. | MR 1417938 | Zbl 0861.13012

[2] S. Han, C. Kirfel, M.B. Nathanson, Linear forms in finite sets of integers. Ramanujan J. 2 (1998), 271-281. | MR 1642882 | Zbl 0911.11008

[3] A.G. Khovanskii, Newton polyhedron, Hilbert polynomial, and sums of finite sets. Functional. Anal. Appl. 26 (1992), 276-281. | MR 1209944 | Zbl 0809.13012

[4] A.G. Khovanskii, Sums of finite sets, orbits of commutative semigroups, and Hilbert functions. Functional. Anal. Appl. 29 (1995), 102-112. | MR 1340302 | Zbl 0855.13011

[5] M.B. Nathanson, Sums of finite sets of integers. Amer. Math. Monthly 79 (1972), 1010-1012. | MR 304305 | Zbl 0251.10002

[6] M.B. Nathanson, Growth of sumsets in abelian semigroups. Semigroup Forum 61 (2000), 149-153. | MR 1839220 | Zbl 0959.20055