Some additive applications of the isoperimetric approach

Hamidoune, Yahya O.

doi:10.5802/aif.2404

Some additive applications of the isoperimetric approach
[Quelques applications additives de la méthode isopérimétrique]

Hamidoune, Yahya O.¹

¹ Université Paris 06 UPMC E. Combinatoire 4, place Jussieu 75005 Paris (France)

Annales de l'Institut Fourier, Tome 58 (2008) no. 6, pp. 2007-2036.

Résumé
Abstract

Soient $G$ un groupe et $X$ un sous-ensemble fini de $G$ . La méthode isopérimétrique étudie la fonction objective $| (X B) ∖ X |$ , définie sur les parties $X$ telles que $| X | \geq k$ et $| G ∖ (X B) | \geq k$ , où $X B$ est le produit de $X$ par $B$ . Les inégalités additives découlent de la structure des ensembles où cette fonction atteint sa valeur minimale.

Nous présentons dans ce mémoire les bases de cette méthode et certaines de ses applications. Nous obtenons quelques nouveaux résultats et des courtes preuves de résultats connus.

Certains des résultats obtenus dans ce travail seront appliqués dans un futur mémoire afin d’améliorer les théorèmes de structure de Kempermann.

Let $G$ be a group and let $X$ be a finite subset. The isoperimetric method investigates the objective function $| (X B) ∖ X |$ , defined on the subsets $X$ with $| X | \geq k$ and $| G ∖ (X B) | \geq k$ , where $X B$ is the product of $X$ by $B$ .

In this paper we present all the basic facts about the isoperimetric method. We improve some of our previous results and obtain generalizations and short proofs for several known results. We also give some new applications.

Some of the results obtained here will be used in coming papers to improve Kempermann structure Theory.

MR Zbl

DOI : 10.5802/aif.2404

Classification : 05C25, 20D60, 11B75, 05C40
Keywords: Addition theorem, Cayley graph, inverse additive theory
Mot clés : somme de Minkowski, graphe de Cayley, problème inverse

Affiliations des auteurs :

Hamidoune, Yahya O. ¹

¹ Université Paris 06 UPMC E. Combinatoire 4, place Jussieu 75005 Paris (France)

@article{AIF_2008__58_6_2007_0,
     author = {Hamidoune, Yahya O.},
     title = {Some additive applications of the isoperimetric approach},
     journal = {Annales de l'Institut Fourier},
     pages = {2007--2036},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {58},
     number = {6},
     year = {2008},
     doi = {10.5802/aif.2404},
     mrnumber = {2473627},
     zbl = {1173.05019},
     language = {en},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.2404/}
}

TY  - JOUR
AU  - Hamidoune, Yahya O.
TI  - Some additive applications of the isoperimetric approach
JO  - Annales de l'Institut Fourier
PY  - 2008
SP  - 2007
EP  - 2036
VL  - 58
IS  - 6
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.2404/
DO  - 10.5802/aif.2404
LA  - en
ID  - AIF_2008__58_6_2007_0
ER  -

%0 Journal Article
%A Hamidoune, Yahya O.
%T Some additive applications of the isoperimetric approach
%J Annales de l'Institut Fourier
%D 2008
%P 2007-2036
%V 58
%N 6
%I Association des Annales de l’institut Fourier
%U https://aif.centre-mersenne.org/articles/10.5802/aif.2404/
%R 10.5802/aif.2404
%G en
%F AIF_2008__58_6_2007_0

Hamidoune, Yahya O. Some additive applications of the isoperimetric approach. Annales de l'Institut Fourier, Tome 58 (2008) no. 6, pp. 2007-2036. doi : 10.5802/aif.2404. https://aif.centre-mersenne.org/articles/10.5802/aif.2404/

Bibliographie
Cité par

[1] Arad, Z.; Muzychuk, M. Order evaluation of products of subsets in finite groups and its applications. II., Trans. Amer. Math. Soc., Volume 349 (1997) no. 11, pp. 4401-4414 | DOI | MR | Zbl

[2] Balandraud, E. Un nouveau point de vue isopérimétrique appliqué au théorème de Kneser, 2005 (Preprint)

[3] Brailowski, L. V.; Freiman, G. A. On a product of finite subsets in a torsion free group, J. Algebra, Volume 130 (1990), pp. 462-476 | DOI | MR | Zbl

[4] Cauchy, A. Recherches sur les nombres, J. École polytechnique, Volume 9 (1813), pp. 99-116

[5] Chowla, S. A theorem on the addition of residue classes: applications to the number $Γ (k)$ in Waring’s problem, Proc. Indian Acad. Sc., Volume 2 (1935), pp. 242-243

[6] Davenport, H. On the addition of residue classes, J. London Math. Soc., Volume 10 (1935), pp. 30-32 | DOI

[7] Deshouillers, J. M.; Freiman, G. A. A step beyond Kneser’s Theorem, Proc. London Math. Soc., Volume 86 (2003) no. 3, pp. 1-28 | DOI | Zbl

[8] Diderrich, G. T. On Kneser’s addition theorem in groups, Proc. Amer. Math. Soc. (1973), pp. 443-451 | Zbl

[9] Dirac, G. A. Extensions of Menger’s theorem, J. Lond. Math. Soc., Volume 38 (1963), pp. 148161 | DOI | Zbl

[10] Dixmier, J. Proof of a conjecture by Erdös, Graham concerning the problem of Frobenius, J. number Theory, Volume 34 (1990), pp. 198-209 | DOI | MR | Zbl

[11] Dyson, F. J. A theorem on the densities of sets of integers, J. London Math. Soc., Volume 20 (1945), pp. 8-14 | DOI | MR | Zbl

[12] Erdős, P.; Heilbronn, H. On the Addition of residue classes mod $p$ , Acta Arith., Volume 9 (1964), pp. 149-159 | MR | Zbl

[13] Green, B.; Ruzsa, I. Z. Sets with small sumset and rectification, Bull. London Math. Soc., Volume 38 (2006) no. 1, pp. 43-52 | DOI | MR

[14] Hamidoune, Y. O. Beyond Kemperman’s Structure Theory: The isoperimetric approach (In preparation)

[15] Hamidoune, Y. O. Sur les atomes d’un graphe orienté, C.R. Acad. Sc. Paris A, Volume 284 (1977), pp. 1253-1256 | Zbl

[16] Hamidoune, Y. O. An application of connectivity theory in graphs to factorizations of elements in groups, Europ. J. of Combinatorics, Volume 2 (1981), pp. 349-355 | MR | Zbl

[17] Hamidoune, Y. O. Quelques problèmes de connexité dans les graphes orientés, J. Comb. Theory, Volume B 30 (1981), pp. 1-10 | MR | Zbl

[18] Hamidoune, Y. O. On the connectivity of Cayley digraphs, Europ. J. Combinatorics, Volume 5 (1984), pp. 309-312 | MR | Zbl

[19] Hamidoune, Y. O. On a subgroup contained in words with a bounded length, Discrete Math., Volume 103 (1992), pp. 171-176 | DOI | MR | Zbl

[20] Hamidoune, Y. O. An isoperimetric method in additive theory, J. Algebra, Volume 179 (1996) no. 2, pp. 622-630 | DOI | MR | Zbl

[21] Hamidoune, Y. O. On subsets with a small sum in abelian groups I: The Vosper property, Europ. J. of Combinatorics, Volume 18 (1997), pp. 541-556 | DOI | MR | Zbl

[22] Hamidoune, Y. O. On small subset product in a group. Structure Theory of set-addition, Astérisque, Volume 258 (1999), pp. 281-308 (xiv-xv) | MR | Zbl

[23] Hamidoune, Y. O. Some results in Additive number Theory I: The critical pair Theory, Acta Arith., Volume 96 (2000) no. 2, pp. 97-119 | DOI | MR | Zbl

[24] Hamidoune, Y. O. Hyper-atoms and the Kemperman’s critical pair Theory, 2007 (Preprint)

[25] Hamidoune, Y. O.; Rødseth, Ø. J. On bases for $σ$ -finite groups, Math. Sc., Volume 78 (1996) no. 2, pp. 246-254 | MR | Zbl

[26] Hamidoune, Y. O.; Rødseth, Ø. J. An inverse theorem modulo $p$ , Acta Arithmetica, Volume 92 (2000), pp. 251-262 | MR | Zbl

[27] Hamidoune, Y. O.; Serra, O.; Zémor, G. On the critical pair theory in Abelian groups: Beyond Chowla’s Theorem, 2006 (Preprint)

[28] Hamidoune, Y. O.; Serra, O.; Zémor, G. On the critical pair theory in $ℤ / p ℤ$ , Acta Arith., Volume 121 (2006) no. 2, pp. 99-115 | DOI | MR

[29] Hegyvári, N. On iterated difference sets in groups, Period. Math. Hungar., Volume 43 (2001) no. 1-2, pp. 105-110 | MR | Zbl

[30] Jin, R. Solution to the inverse problem for upper asymptotic density, J. Reine Angew. Math., Volume 595 (2006), pp. 121-165 | DOI | MR | Zbl

[31] Jungić, V.; Licht, J.; Mahdian, M.; Nešetřil, J.; Jaroslav, R.; Radoičić, R. Rainbow arithmetic progressions and anti-Ramsey results. Special issue on Ramsey theory, Combin. Probab. Comput., Volume 12 (2003) no. 5-6, pp. 599-620 | DOI | MR | Zbl

[32] Károlyi, G. Cauchy-Davenport theorem in group extensions, Enseign. Math., Volume (2)51 (2005) no. 3-4, pp. 239-254 | MR | Zbl

[33] Kemperman, J. H. B. On complexes in a semigroup, Nederl. Akad. Wetensch. Proc. Ser. A, Volume 59 (1956) no. 18, pp. 247-254 (Indag. Math.) | MR | Zbl

[34] Kemperman, J. H. B. On small sumsets in Abelian groups, Acta Math., Volume 103 (1960), pp. 66-88 | DOI | MR | Zbl

[35] Kneser, M. Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z., Volume 58 (1953), pp. 459-484 | DOI | MR | Zbl

[36] Kneser, M. Summenmengen in lokalkompakten abelesche Gruppen, Math. Zeit., Volume 66 (1956), pp. 88-110 | DOI | MR | Zbl

[37] Mann, H. B. An addition theorem for sets of elements of an Abelian group, Proc. Amer. Math. Soc., Volume 4 (1953), pp. 423 | MR | Zbl

[38] Mann, H. B. Addition Theorems, R.E. Krieger, New York, 1976 | MR

[39] Menger, K. Zur allgemeinen Kurventhoerie, Fund. Math., Volume 10 Karl (1927), pp. 96-115

[40] Nathanson, M. B.; Springer Additive Number Theory. Inverse problems and the geometry of sumsets, Grad. Texts in Math., Volume 165 (1996) | MR | Zbl

[41] Nikolov, N.; Segal, D. On finitely generated profinite groups. I. Strong completeness and uniform bounds, Ann. of Math., Volume (2) 165 (2007) no. 1, pp. 171-238 | DOI | MR | Zbl

[42] Nikolov, N.; Segal, D. On finitely generated profinite groups. II. Products in quasisimple groups, Ann. of Math., Volume (2) 165 (2007) no. 1, pp. 239-273 | DOI | MR | Zbl

[43] Olson, J. E. Sums of sets of group elements, Acta Arith., Volume 28 (1975/76) no. 2, pp. 147-156 | MR | Zbl

[44] Olson, J. E. On the sum of two sets in a group, J. Number Theory, Volume 18 (1984), pp. 110-120 | DOI | MR | Zbl

[45] Olson, J. E. On the symmetric difference of two sets in a group, Europ. J. Combinatorics (1986), pp. 43-54 | MR | Zbl

[46] Plagne, A. $(k, l)$ -free sets in $ℤ / p ℤ$ are arithmetic progressions, Bull. Austral. Math. Soc., Volume 65 (2002) no. 1, pp. 137-144 | DOI | MR | Zbl

[47] Pyber, L. Bounded generation and subgroup growth, Bull. London Math. Soc., Volume 34 (2002) no. 1, pp. 55-60 | DOI | MR | Zbl

[48] Rødseth, Ø. J. Two remarks on linear forms in non-negative integers, Math. Scand., Volume 51 (1982), pp. 193-198 | MR | Zbl

[49] Ruzsa, I. An application of graph theory to additive number theory, Scientia, Ser. A, Volume 3 (1989), pp. 97109 | MR | Zbl

[50] Serra, O. An isoperimetric method for the small sumset problem, Surveys in combinatorics (London Math. Soc. Lecture Note Ser.), Volume 327, Cambridge Univ. Press, Cambridge, 2005, pp. 119-152 | MR

[51] Serra, O.; Zémor, G. On a generalization of a theorem by Vosper, Integers, 2000 0, A10, (electronic) | MR | Zbl

[52] Shepherdson, J. C. On the addition of elements of a sequence, J. London Math Soc., Volume 22 (1947), pp. 85-88 | DOI | MR | Zbl

[53] Szemerédi, E. On a conjecture of Erdös and Heilbronn, Acta Arithmetica, Volume 17 (1970), pp. 227-229 | MR | Zbl

[54] Tao, T.; Vu, V. H. Additive Combinatorics, Cambridge Studies in Advanced Mathematics, Volume 105, Cambridge University Press, 2006 | MR | Zbl

[55] Vosper, G. Addendum to: The critical pairs of subsets of a group of prime order, J. London Math. Soc., Volume 31 (1956), pp. 280-282 | DOI | MR | Zbl

[56] Vosper, G. The critical pairs of subsets of a group of prime order, J. London Math. Soc., Volume 31 (1956), pp. 200-205 | DOI | MR | Zbl

[57] Zémor, G. On positive and negative atoms of Cayley digraphs, Discrete Appl. Math., Volume 23 (1989) no. 2, pp. 193-195 | DOI | MR | Zbl

Cité par Sources :

ANNALES DE L'INSTITUT FOURIER

ARTICLES À PARAÎTRE

FEUILLETER

PRESENTATION

COMITÉ DE RÉDACTION

SOUMETTRE UN ARTICLE

ABONNEMENT