Polynomial growth of sumsets in abelian semigroups

Nathanson, Melvyn B.; Ruzsa, Imre Z.

Nathanson, Melvyn B. ; Ruzsa, Imre Z.

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

Résumé
Abstract

Soit $S$ un semi-groupe abélien et $A$ un sous-ensemble fini de $S$ . On désigne par $h A$ l’ensemble de toutes les sommes de $h$ éléments de $A$ , et par $| h A |$ 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 $| h A | = p (h)$ . Plus généralement, on étend ce résultat aux ensembles $h_{1} A_{1} \times \dots + h_{r} A_{r}$ en obtenant la croissance polynomiale du cardinal en termes des variables $h_{1}, h_{2}, \dots, h_{r}$ .

Let $S$ be an abelian semigroup, and $A$ a finite subset of $S$ . The sumset $h A$ consists of all sums of $h$ elements of $A$ , with repetitions allowed. Let $| h A |$ denote the cardinality of $h A$ . 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 $| h A | = p (h)$ for all sufficiently large $h$ . Lattice point counting is also used to prove that sumsets of the form $h_{1} A_{1} + \dots + h_{r} A_{r}$ have multivariate polynomial growth.

EuDML MR Zbl

@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},
     pages = {553--560},
     publisher = {Universit\'e Bordeaux I},
     volume = {14},
     number = {2},
     year = {2002},
     mrnumber = {2040693},
     zbl = {1077.11014},
     language = {en},
     url = {http://archive.numdam.org/item/JTNB_2002__14_2_553_0/}
}

TY  - JOUR
AU  - Nathanson, Melvyn B.
AU  - Ruzsa, Imre Z.
TI  - Polynomial growth of sumsets in abelian semigroups
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2002
SP  - 553
EP  - 560
VL  - 14
IS  - 2
PB  - Université Bordeaux I
UR  - http://archive.numdam.org/item/JTNB_2002__14_2_553_0/
LA  - en
ID  - JTNB_2002__14_2_553_0
ER  -

%0 Journal Article
%A Nathanson, Melvyn B.
%A Ruzsa, Imre Z.
%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 http://archive.numdam.org/item/JTNB_2002__14_2_553_0/
%G en
%F 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, Tome 14 (2002) no. 2, pp. 553-560. http://archive.numdam.org/item/JTNB_2002__14_2_553_0/

Bibliographie
Cité par

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

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

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

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

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

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