Polynomial growth of sumsets in abelian semigroups
Journal de Théorie des Nombres de Bordeaux, Volume 14 (2002) no. 2, pp. 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\left(t\right)$ such that $|hA|=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.

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\left(t\right)$ tel que pour tout entier $h$ assez grand $|hA|=p\left(h\right)$. Plus généralement, on étend ce résultat aux ensembles ${h}_{1}{A}_{1}×\cdots +{h}_{r}{A}_{r}$ en obtenant la croissance polynomiale du cardinal en termes des variables ${h}_{1},{h}_{2},\cdots ,{h}_{r}$.

@article{JTNB_2002__14_2_553_0,
author = {Melvyn B. Nathanson and Imre Z. Ruzsa},
title = {Polynomial growth of sumsets in abelian semigroups},
journal = {Journal de Th\'eorie des Nombres de Bordeaux},
pages = {553--560},
publisher = {Universit\'e Bordeaux I},
volume = {14},
number = {2},
year = {2002},
doi = {10.5802/jtnb.374},
zbl = {1077.11014},
mrnumber = {2040693},
language = {en},
url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.374/}
}
TY  - JOUR
TI  - Polynomial growth of sumsets in abelian semigroups
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2002
DA  - 2002///
SP  - 553
EP  - 560
VL  - 14
IS  - 2
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.374/
UR  - https://zbmath.org/?q=an%3A1077.11014
UR  - https://www.ams.org/mathscinet-getitem?mr=2040693
UR  - https://doi.org/10.5802/jtnb.374
DO  - 10.5802/jtnb.374
LA  - en
ID  - JTNB_2002__14_2_553_0
ER  - 
%0 Journal Article
%T Polynomial growth of sumsets in abelian semigroups
%J Journal de Théorie des Nombres de Bordeaux
%D 2002
%P 553-560
%V 14
%N 2
%I Université Bordeaux I
%U https://doi.org/10.5802/jtnb.374
%R 10.5802/jtnb.374
%G en
%F JTNB_2002__14_2_553_0
Melvyn B. Nathanson; Imre Z. Ruzsa. Polynomial growth of sumsets in abelian semigroups. Journal de Théorie des Nombres de Bordeaux, Volume 14 (2002) no. 2, pp. 553-560. doi : 10.5802/jtnb.374. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.374/

[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

Cited by Sources: