Some additive applications of the isoperimetric approach

Hamidoune, Yahya O.

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

Hamidoune, Yahya O.

Annales de l'Institut Fourier, Tome 58 (2008), p. 2007-2036 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2008-01-01

MR 2473627 | Zbl 1173.05019

DOI : https://doi.org/10.5802/aif.2404
Classification: 05C25, 20D60, 11B75, 05C40
Mots clés: somme de Minkowski, graphe de Cayley, problème inverse

@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},
     volume = {58},
     year = {2008},
     pages = {2007-2036},
     doi = {10.5802/aif.2404},
     zbl = {1173.05019},
     mrnumber = {2473627},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_2008__58_6_2007_0}
}

Hamidoune, Yahya O. Some additive applications of the isoperimetric approach. Annales de l'Institut Fourier, Tome 58 (2008) pp. 2007-2036. doi : 10.5802/aif.2404. http://gdmltest.u-ga.fr/item/AIF_2008__58_6_2007_0/

Bibliographie

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

[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, Tome 130 (1990), pp. 462-476 | Article | MR 1051314 | Zbl 0697.20019

[4] Cauchy, A. Recherches sur les nombres, J. École polytechnique, Tome 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., Tome 2 (1935), p. 242-243

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

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

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

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

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

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

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

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

[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, Tome 284 (1977), pp. 1253-1256 | Zbl 0352.05035

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

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

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

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

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

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

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

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

[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., Tome 78 (1996) no. 2, pp. 246-254 | MR 1414651 | Zbl 0877.11007

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

[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., Tome 121 (2006) no. 2, pp. 99-115 | Article | MR 2216136 | Zbl pre05024060

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

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

[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., Tome 12 (2003) no. 5-6, pp. 599-620 | Article | MR 2037073 | Zbl 1128.11305

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

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

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

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

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

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

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

[39] Menger, K. Zur allgemeinen Kurventhoerie, Fund. Math., Tome 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., Tome 165 (1996) | MR 1477155 | Zbl 0859.11003

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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