Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Growth in groups: ideas and perspectives


Author: Harald A. Helfgott
Journal: Bull. Amer. Math. Soc. 52 (2015), 357-413
MSC (2010): Primary 20F69; Secondary 20D60, 11B30, 20B05
DOI: https://doi.org/10.1090/S0273-0979-2015-01475-8
Published electronically: February 11, 2015
MathSciNet review: 3348442
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This is a survey of methods developed in the last few years to prove results on growth in non-commutative groups. These techniques have their roots in both additive combinatorics and group theory, as well as other fields. We discuss linear algebraic groups, with $ \mathrm {SL}_2(\mathbb{Z}/p\mathbb{Z})$ as the basic example, as well as permutation groups. The emphasis will lie on the ideas behind the methods.


References [Enhancements On Off] (What's this?)

  • [AS00] N. Alon and J. H. Spencer, The probabilistic method, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley & Sons], New York, 2000. With an appendix on the life and work of Paul Erdős. MR 1885388 (2003f:60003)
  • [Bab86] L. Babai, On the length of subgroup chains in the symmetric group, Comm. Algebra 14 (1986), no. 9, 1729-1736. MR 860123 (87m:20005), https://doi.org/10.1080/00927878608823393
  • [Bab06] L. Babai, On the diameter of Eulerian orientations of graphs, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2006, pp. 822-831. MR 2368881, https://doi.org/10.1145/1109557.1109648
  • [Bab82] L. Babai, On the order of doubly transitive permutation groups, Invent. Math. 65 (1981/82), no. 3, 473-484. MR 643565 (83g:20003), https://doi.org/10.1007/BF01396631
  • [Bas72] H. Bass, The degree of polynomial growth of finitely generated nilpotent groups, Proc. London Math. Soc. (3) 25 (1972), 603-614. MR 0379672 (52 #577)
  • [BBS04] L. Babai, R. Beals, and Á. Seress, On the diameter of the symmetric group: polynomial bounds, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2004, pp. 1108-1112 (electronic). MR 2291003
  • [BD92] D. Bayer and P. Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Probab. 2 (1992), no. 2, 294-313. MR 1161056 (93d:60014)
  • [BG08a] J. Bourgain and A. Gamburd, Expansion and random walks in $ {\rm SL}_d(\mathbb{Z}/p^n\mathbb{Z})$. I, J. Eur. Math. Soc. (JEMS) 10 (2008), no. 4, 987-1011. MR 2443926 (2010a:05093), https://doi.org/10.4171/JEMS/137
  • [BG08b] J. Bourgain and A. Gamburd, On the spectral gap for finitely-generated subgroups of $ \rm SU(2)$, Invent. Math. 171 (2008), no. 1, 83-121. MR 2358056 (2009g:22018), https://doi.org/10.1007/s00222-007-0072-z
  • [BG08c] J. Bourgain and A. Gamburd, Uniform expansion bounds for Cayley graphs of $ {\rm SL}_2(\mathbb{F}_p)$, Ann. of Math. (2) 167 (2008), no. 2, 625-642. MR 2415383 (2010b:20070), https://doi.org/10.4007/annals.2008.167.625
  • [BG09] J. Bourgain and A. Gamburd, Expansion and random walks in $ {\rm SL}_d(\mathbb{Z}/p^n\mathbb{Z})$. II, J. Eur. Math. Soc. (JEMS) 11 (2009), no. 5, 1057-1103. With an appendix by Bourgain. MR 2538500 (2011a:60021), https://doi.org/10.4171/JEMS/175
  • [BG10] E. Breuillard and A. Gamburd, Strong uniform expansion in $ {\rm SL}(2,p)$, Geom. Funct. Anal. 20 (2010), no. 5, 1201-1209. MR 2746951 (2011m:20111), https://doi.org/10.1007/s00039-010-0094-3
  • [BG11a] E. Breuillard and B. Green, Approximate groups. I: The torsion-free nilpotent case, J. Inst. Math. Jussieu 10 (2011), no. 1, 37-57. MR 2749571 (2012b:11014), https://doi.org/10.1017/S1474748010000150
  • [BG11b] E. Breuillard and B. Green, Approximate groups, II: The solvable linear case, Q. J. Math. 62 (2011), no. 3, 513-521. MR 2825469, https://doi.org/10.1093/qmath/haq011
  • [BG12] E. Breuillard and B. Green, Approximate groups III: the unitary case, Turkish J. Math. 36 (2012), no. 2, 199-215. MR 2912036
  • [BGGT] E. Breuillard, B. Green, R. Guralnick, and T. Tao.
    Expansion in finite simple groups of Lie type.
    Available as arxiv.org:1309.1975.
  • [BGH$^+$14] J. Bamberg, N. Gill, T. P. Hayes, H. A. Helfgott, Á. Seress, and P. Spiga, Bounds on the diameter of Cayley graphs of the symmetric group, J. Algebraic Combin. 40 (2014), no. 1, 1-22. MR 3226815, https://doi.org/10.1007/s10801-013-0476-3
  • [BGK06] J. Bourgain, A. A. Glibichuk, and S. V. Konyagin, Estimates for the number of sums and products and for exponential sums in fields of prime order, J. London Math. Soc. (2) 73 (2006), no. 2, 380-398. MR 2225493 (2007e:11092), https://doi.org/10.1112/S0024610706022721
  • [BGS10] J. Bourgain, A. Gamburd, and P. Sarnak, Affine linear sieve, expanders, and sum-product, Invent. Math. 179 (2010), no. 3, 559-644. MR 2587341 (2011d:11018), https://doi.org/10.1007/s00222-009-0225-3
  • [BGS11] J. Bourgain, A. Gamburd, and P. Sarnak, Generalization of Selberg's $ \frac {3}{16}$ theorem and affine sieve, Acta Math. 207 (2011), no. 2, 255-290. MR 2892611, https://doi.org/10.1007/s11511-012-0070-x
  • [BGT11] E. Breuillard, B. Green, and T. Tao, Approximate subgroups of linear groups, Geom. Funct. Anal. 21 (2011), no. 4, 774-819. MR 2827010, https://doi.org/10.1007/s00039-011-0122-y
  • [BGT12] E. Breuillard, B. Green, and T. Tao, The structure of approximate groups, Publ. Math. Inst. Hautes Études Sci. 116 (2012), 115-221. MR 3090256, https://doi.org/10.1007/s10240-012-0043-9
  • [BH92] L. Babai and G. L. Hetyei, On the diameter of random Cayley graphs of the symmetric group, Combin. Probab. Comput. 1 (1992), no. 3, 201-208. MR 1208801 (94b:05095), https://doi.org/10.1017/S0963548300000237
  • [BH05] L. Babai and T. P. Hayes, Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2005, pp. 1057-1066 (electronic). MR 2298365
  • [BIW06] B. Barak, R. Impagliazzo, and A. Wigderson, Extracting randomness using few independent sources, SIAM J. Comput. 36 (2006), no. 4, 1095-1118 (electronic). MR 2272272 (2007j:68048), https://doi.org/10.1137/S0097539705447141
  • [BKL89] L. Babai, W. M. Kantor, and A. Lubotsky, Small-diameter Cayley graphs for finite simple groups, European J. Combin. 10 (1989), no. 6, 507-522. MR 1022771 (91a:20038), https://doi.org/10.1016/S0195-6698(89)80067-8
  • [BKT04] J. Bourgain, N. Katz, and T. Tao, A sum-product estimate in finite fields, and applications, Geom. Funct. Anal. 14 (2004), no. 1, 27-57. MR 2053599 (2005d:11028), https://doi.org/10.1007/s00039-004-0451-1
  • [BLS87] L. Babai, E. M. Luks, and Á. Seress.
    Permutation groups in NC.
    In Proceedings of the Nineteenth Annual ACM Symposium on the Theory of Computing, pages 409-420, New York, 1987. ACM.
  • [BNP08] L. Babai, N. Nikolov, and L. Pyber, Product growth and mixing in finite groups, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2008, pp. 248-257. MR 2485310
  • [Bou72] N. Bourbaki, Éléments de mathématique. Fasc. XXXVII. Groupes et algèbres de Lie. Chapitre II: Algèbres de Lie libres. Chapitre III: Groupes de Lie, Hermann, Paris, 1972. Actualités Scientifiques et Industrielles, No. 1349. MR 0573068 (58 #28083a)
  • [BRD] J. Button and C. Roney-Dougal, An explicit upper bound for the Helfgott delta in $ \mathrm {SL}(2,p)$, J. Algebra 421 (2015), 493-511. MR 3272393
  • [Bro86] R. Brooks, The spectral geometry of a tower of coverings, J. Differential Geom. 23 (1986), no. 1, 97-107. MR 840402 (87j:58095)
  • [Bro87] R. Brooks, On the angles between certain arithmetically defined subspaces of $ {\bf C}^n$, Ann. Inst. Fourier (Grenoble) 37 (1987), no. 1, 175-185 (English, with French summary). MR 894565 (89h:11022)
  • [BS87a] L. Babai and Á. Seress, On the degree of transitivity of permutation groups: a short proof, J. Combin. Theory Ser. A 45 (1987), no. 2, 310-315. MR 894827 (88h:20002), https://doi.org/10.1016/0097-3165(87)90023-9
  • [BS87b] A. Broder and E. Shamir.
    On the second eigenvalue of random regular graphs.
    In 28th Annual Symposium on the Foundations of Computer Science (FOCS 1987), 1987.
  • [BS88] L. Babai and Á. Seress, On the diameter of Cayley graphs of the symmetric group, J. Combin. Theory Ser. A 49 (1988), no. 1, 175-179. MR 957215 (89i:05141), https://doi.org/10.1016/0097-3165(88)90033-7
  • [BS92] L. Babai and Á. Seress, On the diameter of permutation groups, European J. Combin. 13 (1992), no. 4, 231-243. MR 1179520 (93h:20001), https://doi.org/10.1016/S0195-6698(05)80029-0
  • [BS94] A. Balog and E. Szemerédi, A statistical theorem of set addition, Combinatorica 14 (1994), no. 3, 263-268. MR 1305895 (95m:11019), https://doi.org/10.1007/BF01212974
  • [Bur86] M. Burger.
    Petites valeurs propres du Laplacien et topologie de Fell.
    PhD thesis, Université de Lausanne, 1986.
  • [Bus78] P. Buser, Cubic graphs and the first eigenvalue of a Riemann surface, Math. Z. 162 (1978), no. 1, 87-99. MR 505920 (80b:58061), https://doi.org/10.1007/BF01437826
  • [BV12] J. Bourgain and P. P. Varjú, Expansion in $ SL_d({\bf Z}/q{\bf Z}),\,q$ arbitrary, Invent. Math. 188 (2012), no. 1, 151-173. MR 2897695, https://doi.org/10.1007/s00222-011-0345-4
  • [Cha02] M.-C. Chang, A polynomial bound in Freiman's theorem, Duke Math. J. 113 (2002), no. 3, 399-419. MR 1909605 (2003d:11151), https://doi.org/10.1215/S0012-7094-02-11331-3
  • [Cha08] M.-C. Chang, Product theorems in $ {\rm SL}_2$ and $ {\rm SL}_3$, J. Inst. Math. Jussieu 7 (2008), no. 1, 1-25. MR 2398145 (2009d:20112), https://doi.org/10.1017/S1474748007000126
  • [CS10] E. Croot and O. Sisask, A probabilistic technique for finding almost-periods of convolutions, Geom. Funct. Anal. 20 (2010), no. 6, 1367-1396. MR 2738997 (2012d:11019), https://doi.org/10.1007/s00039-010-0101-8
  • [Din06] O. Dinai, Poly-log diameter bounds for some families of finite groups, Proc. Amer. Math. Soc. 134 (2006), no. 11, 3137-3142 (electronic). MR 2231895 (2007j:05097), https://doi.org/10.1090/S0002-9939-06-08384-5
  • [Din11] O. Dinai, Growth in $ {\rm SL}_2$ over finite fields, J. Group Theory 14 (2011), no. 2, 273-297. MR 2788087 (2012c:20134), https://doi.org/10.1515/JGT.2010.056
  • [Dix69] J. D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199-205. MR 0251758 (40 #4985)
  • [DM96] J. D. Dixon and B. Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812 (98m:20003)
  • [DS81] P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159-179. MR 626813 (82h:60024), https://doi.org/10.1007/BF00535487
  • [DS98] V. I. Danilov and V. V. Shokurov, Algebraic curves, algebraic manifolds and schemes, Springer-Verlag, Berlin, 1998. Translated from the 1988 Russian original by D. Coray and V. N. Shokurov; Translation edited and with an introduction by I. R. Shafarevich; Reprint of the original English edition from the series Encyclopaedia of Mathematical Sciences [Algebraic geometry. I, Encyclopaedia Math. Sci., 23, Springer, Berlin, 1994; MR1287418 (95b:14001)]. MR 1658464 (99g:14001)
  • [DSC93] P. Diaconis and L. Saloff-Coste, Comparison techniques for random walk on finite groups, Ann. Probab. 21 (1993), no. 4, 2131-2156. MR 1245303 (95a:60009)
  • [DSV03] G. Davidoff, P. Sarnak, and A. Valette, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, 2003. MR 1989434 (2004f:11001)
  • [EHK12] J. S. Ellenberg, C. Hall, and E. Kowalski, Expander graphs, gonality, and variation of Galois representations, Duke Math. J. 161 (2012), no. 7, 1233-1275. MR 2922374, https://doi.org/10.1215/00127094-1593272
  • [EK01] G. Elekes and Z. Király, On the combinatorics of projective mappings, J. Algebraic Combin. 14 (2001), no. 3, 183-197. MR 1869409 (2003e:52034), https://doi.org/10.1023/A:1012799318591
  • [Ele97] G. Elekes, On the number of sums and products, Acta Arith. 81 (1997), no. 4, 365-367. MR 1472816 (98h:11026)
  • [EM03] G. A. Edgar and C. Miller, Borel subrings of the reals, Proc. Amer. Math. Soc. 131 (2003), no. 4, 1121-1129 (electronic). MR 1948103 (2004d:28017), https://doi.org/10.1090/S0002-9939-02-06653-4
  • [EMO05] A. Eskin, S. Mozes, and H. Oh, On uniform exponential growth for linear groups, Invent. Math. 160 (2005), no. 1, 1-30. MR 2129706 (2006a:20081), https://doi.org/10.1007/s00222-004-0378-z
  • [ES83] P. Erdős and E. Szemerédi, On sums and products of integers, Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 213-218. MR 820223 (86m:11011)
  • [FH91] W. Fulton and J. Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR 1153249 (93a:20069)
  • [Fiz] G. Fiz Pontiveros, Sums of dilates in $ \mathbb{Z}_p$, Combin. Probab. Comput. 22 (2013), no. 2, 282-293. MR 3021335, https://doi.org/10.1017/S0963548312000466
  • [FKP10] D. Fisher, N. H. Katz, and I. Peng, Approximate multiplicative groups in nilpotent Lie groups, Proc. Amer. Math. Soc. 138 (2010), no. 5, 1575-1580. MR 2587441 (2011e:11164), https://doi.org/10.1090/S0002-9939-10-10078-1
  • [Fre73] G. A. Freĭman, Foundations of a structural theory of set addition, American Mathematical Society, Providence, R. I., 1973. Translated from the Russian; Translations of Mathematical Monographs, Vol 37. MR 0360496 (50 #12944)
  • [Fur77] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204-256. MR 0498471 (58 #16583)
  • [Gam02] A. Gamburd, On the spectral gap for infinite index ``congruence'' subgroups of $ {\rm SL}_2(\mathbf {Z})$, Israel J. Math. 127 (2002), 157-200. MR 1900698 (2003b:11050), https://doi.org/10.1007/BF02784530
  • [GH] N. Gill and H. Helfgott, Growth in solvable subgroups of $ {\mathrm {GL}_r(\mathbb{Z}/p\mathbb{Z})}$, Math. Annalen 360 (2014), no. 1-2, 157-208. MR 3263161
  • [GH11] N. Gill and H. A. Helfgott, Growth of small generating sets in $ {\rm SL}_n(\mathbb{Z}/p\mathbb{Z})$, Int. Math. Res. Not. IMRN 18 (2011), 4226-4251. MR 2836020
  • [GHR] N. Gill, H. Helfgott, and M. Rudnev.
    On growth in an abstract plane.
    To appear in Proc. Amer. Math. Soc. Available as arxiv:1212.5056.
  • [GK07] A. A. Glibichuk and S. V. Konyagin, Additive properties of product sets in fields of prime order, Additive combinatorics, CRM Proc. Lecture Notes, vol. 43, Amer. Math. Soc., Providence, RI, 2007, pp. 279-286. MR 2359478 (2009a:11054)
  • [Gow98] W. T. Gowers, A new proof of Szemerédi's theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), no. 3, 529-551. MR 1631259 (2000d:11019), https://doi.org/10.1007/s000390050065
  • [Gow01] W. T. Gowers, A new proof of Szemerédi's theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465-588. MR 1844079 (2002k:11014), https://doi.org/10.1007/s00039-001-0332-9
  • [Gow08] W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363-387. MR 2410393 (2009f:20105), https://doi.org/10.1017/S0963548307008826
  • [GR05] B. Green and I. Z. Ruzsa, Sum-free sets in abelian groups, Israel J. Math. 147 (2005), 157-188. MR 2166359 (2006e:11030), https://doi.org/10.1007/BF02785363
  • [Gra] A. Granville.
    Additive combinatorics.
    Unpublished notes.
  • [Gro81] M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53-73. MR 623534 (83b:53041)
  • [GS04] A. Gamburd and M. Shahshahani, Uniform diameter bounds for some families of Cayley graphs, Int. Math. Res. Not. 71 (2004), 3813-3824. MR 2104475 (2005m:05111), https://doi.org/10.1155/S1073792804140579
  • [GT08] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481-547. MR 2415379 (2009e:11181), https://doi.org/10.4007/annals.2008.167.481
  • [Gui73] Y. Guivarc'h, Croissance polynomiale et périodes des fonctions harmoniques, Bull. Soc. Math. France 101 (1973), 333-379 (French). MR 0369608 (51 #5841)
  • [GV12] A. S. Golsefidy and P. P. Varjú, Expansion in perfect groups, Geom. Funct. Anal. 22 (2012), no. 6, 1832-1891. MR 3000503, https://doi.org/10.1007/s00039-012-0190-7
  • [Hel08] H. A. Helfgott, Growth and generation in $ {\rm SL}_2(\mathbb{Z}/p\mathbb{Z})$, Ann. of Math. (2) 167 (2008), no. 2, 601-623. MR 2415382 (2009i:20094), https://doi.org/10.4007/annals.2008.167.601
  • [Hel11] H. A. Helfgott, Growth in $ {\rm SL}_3(\mathbb{Z}/p\mathbb{Z})$, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 3, 761-851. MR 2781932, https://doi.org/10.4171/JEMS/267
  • [HK05] B. Host and B. Kra, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2) 161 (2005), no. 1, 397-488. MR 2150389 (2007b:37004), https://doi.org/10.4007/annals.2005.161.397
  • [HP95] E. Hrushovski and A. Pillay, Definable subgroups of algebraic groups over finite fields, J. Reine Angew. Math. 462 (1995), 69-91. MR 1329903 (97f:20059)
  • [Hru12] E. Hrushovski, Stable group theory and approximate subgroups, J. Amer. Math. Soc. 25 (2012), no. 1, 189-243. MR 2833482 (2012h:03104), https://doi.org/10.1090/S0894-0347-2011-00708-X
  • [HS14] H. A. Helfgott and Á. Seress, On the diameter of permutation groups, Ann. of Math. (2) 179 (2014), no. 2, 611-658. MR 3152942, https://doi.org/10.4007/annals.2014.179.2.4
  • [HSZ] H. Helfgott, Á. Seress, and A. Zuk, Random generators of the symmetric group: diameter, mixing time and spectral gap, J. Algebra 421 (2015), 349-368. MR 3272386
  • [HW08] E. Hrushovski and F. Wagner, Counting and dimensions, Model theory with applications to algebra and analysis. Vol. 2, London Math. Soc. Lecture Note Ser., vol. 350, Cambridge Univ. Press, Cambridge, 2008, pp. 161-176. MR 2436141 (2009k:03042), https://doi.org/10.1017/CBO9780511735219.005
  • [Kas07] M. Kassabov, Symmetric groups and expander graphs, Invent. Math. 170 (2007), no. 2, 327-354. MR 2342639 (2008g:20009), https://doi.org/10.1007/s00222-007-0065-y
  • [Kaž67] D. A. Každan, On the connection of the dual space of a group with the structure of its closed subgroups, Funkcional. Anal. i Priložen. 1 (1967), 71-74 (Russian). MR 0209390 (35 #288)
  • [Kes59] H. Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336-354. MR 0109367 (22 #253)
  • [KMS84] D. Kornhauser, G. Miller, and P. Spirakis.
    Coordinating pebble motion on graphs, the diameter of permutation groups, and applications.
    In Proceedings of the 25th IEEE Symposium on Foundations of Computer Science, pages 241-250, Singer Island, FL, 1984. IEEE Computer Society Press.
  • [Kon92] S. V. Konyagin, Estimates for Gaussian sums and Waring's problem modulo a prime, Trudy Mat. Inst. Steklov. 198 (1992), 111-124 (Russian); English transl., Proc. Steklov Inst. Math. 1 (198) (1994), 105-117. MR 1289921 (96e:11122)
  • [Kowa] E. Kowalski.
    Expander graphs.
    Course notes available at http://www.math.ethz.ch/~kowalski/expander-graphs.pdf.
  • [Kowb] E. Kowalski.
    Sieve in expansion.
    Séminaire Bourbaki, 63ème année, 2010-2011, no. 1028.
  • [Kow13] E. Kowalski, Explicit growth and expansion for $ {\rm SL}_2$, Int. Math. Res. Not. IMRN 24 (2013), 5645-5708. MR 3144176
  • [Lar03] M. Larsen, Navigating the Cayley graph of $ {\rm SL}_2(\mathbb{F}_p)$, Int. Math. Res. Not. 27 (2003), 1465-1471. MR 1976231 (2004e:22013), https://doi.org/10.1155/S1073792803130383
  • [Lor12] O. Lorscheid, Algebraic groups over the field with one element, Math. Z. 271 (2012), no. 1-2, 117-138. MR 2917136, https://doi.org/10.1007/s00209-011-0855-1
  • [Lov96] L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud., vol. 2, János Bolyai Math. Soc., Budapest, 1996, pp. 353-397. MR 1395866 (97a:60097)
  • [LP11] M. J. Larsen and R. Pink, Finite subgroups of algebraic groups, J. Amer. Math. Soc. 24 (2011), no. 4, 1105-1158. MR 2813339 (2012f:20148), https://doi.org/10.1090/S0894-0347-2011-00695-4
  • [LPS88] A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261-277. MR 963118 (89m:05099), https://doi.org/10.1007/BF02126799
  • [LPW09] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. MR 2466937 (2010c:60209)
  • [LR92] J. D. Lafferty and D. Rockmore, Fast Fourier analysis for $ {\rm SL}_2$ over a finite field and related numerical experiments, Experiment. Math. 1 (1992), no. 2, 115-139. MR 1203870 (94f:11131)
  • [LS74] V. Landazuri and G. M. Seitz, On the minimal degrees of projective representations of the finite Chevalley groups, J. Algebra 32 (1974), 418-443. MR 0360852 (50 #13299)
  • [Lub12] A. Lubotzky, Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc. (N.S.) 49 (2012), no. 1, 113-162. MR 2869010 (2012m:05003), https://doi.org/10.1090/S0273-0979-2011-01359-3
  • [LW54] S. Lang and A. Weil, Number of points of varieties in finite fields, Amer. J. Math. 76 (1954), 819-827. MR 0065218 (16,398d)
  • [LW93] A. Lubotzky and B. Weiss, Groups and expanders, Expanding graphs (Princeton, NJ, 1992) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 10, Amer. Math. Soc., Providence, RI, 1993, pp. 95-109. MR 1235570 (95b:05097)
  • [McK84] P. McKenzie, Permutations of bounded degree generate groups of polynomial diameter, Inform. Process. Lett. 19 (1984), no. 5, 253-254. MR 777808 (86h:68077), https://doi.org/10.1016/0020-0190(84)90062-0
  • [Mil68] J. Milnor, Growth of finitely generated solvable groups, J. Differential Geometry 2 (1968), 447-449. MR 0244899 (39 #6212)
  • [MV00] F. Martin and A. Valette, Markov operators on the solvable Baumslag-Solitar groups, Experiment. Math. 9 (2000), no. 2, 291-300. MR 1780213 (2002a:37005)
  • [MVW84] C. R. Matthews, L. N. Vaserstein, and B. Weisfeiler, Congruence properties of Zariski-dense subgroups. I, Proc. London Math. Soc. (3) 48 (1984), no. 3, 514-532. MR 735226 (85d:20040), https://doi.org/10.1112/plms/s3-48.3.514
  • [NC00] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. MR 1796805 (2003j:81038)
  • [Nor87] M. V. Nori, On subgroups of $ {\rm GL}_n({\bf F}_p)$, Invent. Math. 88 (1987), no. 2, 257-275. MR 880952 (88d:20068), https://doi.org/10.1007/BF01388909
  • [NP11] N. Nikolov and L. Pyber, Product decompositions of quasirandom groups and a Jordan type theorem, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 4, 1063-1077. MR 2800484 (2012h:20054), https://doi.org/10.4171/JEMS/275
  • [Pet12] G. Petridis, New proofs of Plünnecke-type estimates for product sets in groups, Combinatorica 32 (2012), no. 6, 721-733. MR 3063158, https://doi.org/10.1007/s00493-012-2818-5
  • [Plü70] H. Plünnecke, Eine zahlentheoretische Anwendung der Graphentheorie, J. Reine Angew. Math. 243 (1970), 171-183 (German). MR 0266892 (42 #1794)
  • [PPSS12] C. E. Praeger, L. Pyber, P. Spiga, and E. Szabó, Graphs with automorphism groups admitting composition factors of bounded rank, Proc. Amer. Math. Soc. 140 (2012), no. 7, 2307-2318. MR 2898694, https://doi.org/10.1090/S0002-9939-2011-11100-6
  • [PSa] L. Pyber and E. Szabó.
    Growth in finite simple groups of Lie type of bounded rank.
    Submitted. Available at arxiv.org:1005.1881.
  • [PSb] L. Pyber and E. Szabó, Growth in linear groups: thin groups and superstrong approximation, Math. Res. Sci. Inst. Publ., vol. 61, Cambridge University Press, Cambridge, 2014. MR 3220893
  • [Pyb93] L. Pyber, On the orders of doubly transitive permutation groups, elementary estimates, J. Combin. Theory Ser. A 62 (1993), no. 2, 361-366. MR 1207742 (94d:20005), https://doi.org/10.1016/0097-3165(93)90053-B
  • [Raz14] A. A. Razborov, A product theorem in free groups, Ann. of Math. (2) 179 (2014), no. 2, 405-429. MR 3152939, https://doi.org/10.4007/annals.2014.179.2.1
  • [Rok63] V. A. Rohlin, Generators in ergodic theory, Vestnik Leningrad. Univ. 18 (1963), no. 1, 26-32 (Russian, with English summary). MR 0193206 (33 #1427)
  • [Rot53] K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104-109. MR 0051853 (14,536g)
  • [RT85] I. Z. Ruzsa and S. Turjányi, A note on additive bases of integers, Publ. Math. Debrecen 32 (1985), no. 1-2, 101-104. MR 810596 (87a:11014)
  • [Ruz89] I. Z. Ruzsa, An application of graph theory to additive number theory, Sci. Ser. A Math. Sci. (N.S.) 3 (1989), 97-109. MR 2314377
  • [Ruz91] I. Z. Ruzsa, Arithmetic progressions in sumsets, Acta Arith. 60 (1991), no. 2, 191-202. MR 1139055 (92k:11009)
  • [Ruz94] I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379-388. MR 1281447 (95k:11011), https://doi.org/10.1007/BF01876039
  • [Ruz99] I. Z. Ruzsa, An analog of Freiman's theorem in groups, Astérisque 258 (1999), xv, 323-326 (English, with English and French summaries). Structure theory of set addition. MR 1701207 (2000h:11111)
  • [San12] T. Sanders, On the Bogolyubov-Ruzsa lemma, Anal. PDE 5 (2012), no. 3, 627-655. MR 2994508, https://doi.org/10.2140/apde.2012.5.627
  • [Sel65] A. Selberg, On the estimation of Fourier coefficients of modular forms, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp. 1-15. MR 0182610 (32 #93)
  • [Ser03] Á. Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241 (2004c:20008)
  • [Sha97] Y. Shalom, Expanding graphs and invariant means, Combinatorica 17 (1997), no. 4, 555-575. MR 1645694 (99h:05057), https://doi.org/10.1007/BF01195004
  • [Sha99] Y. Shalom, Expander graphs and amenable quotients, Emerging applications of number theory (Minneapolis, MN, 1996) IMA Vol. Math. Appl., vol. 109, Springer, New York, 1999, pp. 571-581. MR 1691549 (2000h:20059), https://doi.org/10.1007/978-1-4612-1544-8_23
  • [Sim70] C. C. Sims, Computational methods in the study of permutation groups, Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) Pergamon, Oxford, 1970, pp. 169-183. MR 0257203 (41 #1856)
  • [Sim71] C. C. Sims.
    Computation with permutation groups.
    In Proc. Second Symposium on Symbolic and Algebraic Maniupulation, pages 23-28. ACM Press, New York, NY, 1971.
  • [Sol09] J. Solymosi, Bounding multiplicative energy by the sumset, Adv. Math. 222 (2009), no. 2, 402-408. MR 2538014 (2010h:11014), https://doi.org/10.1016/j.aim.2009.04.006
  • [SP12] J.-C. Schlage-Puchta, Applications of character estimates to statistical problems for the symmetric group, Combinatorica 32 (2012), no. 3, 309-323. MR 2965280, https://doi.org/10.1007/s00493-012-2502-9
  • [Spi12] P. Spiga, Two local conditions on the vertex stabiliser of arc-transitive graphs and their effect on the Sylow subgroups, J. Group Theory 15 (2012), no. 1, 23-35. MR 2876252, https://doi.org/10.1515/JGT.2011.097
  • [Spr86] T. A. Springer, Conjugacy classes in algebraic groups, Group theory, Beijing 1984, Lecture Notes in Math., vol. 1185, Springer, Berlin, 1986, pp. 175-209. MR 842444 (87i:20082), https://doi.org/10.1007/BFb0076175
  • [SSV05] B. Sudakov, E. Szemerédi, and V. H. Vu, On a question of Erdős and Moser, Duke Math. J. 129 (2005), no. 1, 129-155. MR 2155059 (2006c:11118), https://doi.org/10.1215/S0012-7094-04-12915-X
  • [ST83] E. Szemerédi and W. T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), no. 3-4, 381-392. MR 729791 (85j:52014), https://doi.org/10.1007/BF02579194
  • [SX91] P. Sarnak and X. X. Xue, Bounds for multiplicities of automorphic representations, Duke Math. J. 64 (1991), no. 1, 207-227. MR 1131400 (92h:22026), https://doi.org/10.1215/S0012-7094-91-06410-0
  • [Sze] B. Szegedy.
    On higher order Fourier analysis.
    Available as arxiv.org:1203.2260.
  • [Sze69] E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89-104. MR 0245555 (39 #6861)
  • [Tao] T. Tao.
    Course notes.
    Available at http://www.math.ucla.edu/~tao/254b.1.12w/.
  • [Tao08] T. Tao, Product set estimates for non-commutative groups, Combinatorica 28 (2008), no. 5, 547-594. MR 2501249 (2010b:11017), https://doi.org/10.1007/s00493-008-2271-7
  • [Tao10] T. Tao, Freiman's theorem for solvable groups, Contrib. Discrete Math. 5 (2010), no. 2, 137-184. MR 2791295 (2012e:05063)
  • [Tit57] J. Tits, Sur les analogues algébriques des groupes semi-simples complexes, Colloque d'algèbre supérieure, tenu à Bruxelles du 19 au 22 décembre 1956, Centre Belge de Recherches Mathématiques, Établissements Ceuterick, Louvain; Librairie Gauthier-Villars, Paris, 1957, pp. 261-289 (French). MR 0108765 (21 #7477)
  • [Tit72] J. Tits, Free subgroups in linear groups, J. Algebra 20 (1972), 250-270. MR 0286898 (44 #4105)
  • [Toi] M. Tointon.
    Freiman's theorem in an arbitrary nilpotent group.
    Submitted. Available as arxiv:1211.3989.
  • [TV06] T. Tao and V. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012 (2008a:11002)
  • [Var] P. P. Varjú, Random walks in compact groups, Doc. Math. 18 (2013), 1137-1175. MR 3138842
  • [Var12] P. P. Varjú, Expansion in $ SL_d(\mathcal {O}_K/I)$, $ I$ square-free, J. Eur. Math. Soc. (JEMS) 14 (2012), no. 1, 273-305. MR 2862040, https://doi.org/10.4171/JEMS/302
  • [Wei84] B. Weisfeiler, Strong approximation for Zariski-dense subgroups of semisimple algebraic groups, Ann. of Math. (2) 120 (1984), no. 2, 271-315. MR 763908 (86m:20053), https://doi.org/10.2307/2006943
  • [Wie64] H. Wielandt, Finite permutation groups, Translated from the German by R. Bercov, Academic Press, New York-London, 1964. MR 0183775 (32 #1252)
  • [Wol68] J. A. Wolf, Growth of finitely generated solvable groups and curvature of Riemanniann manifolds, J. Differential Geometry 2 (1968), 421-446. MR 0248688 (40 #1939)
  • [Zie07] T. Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc. 20 (2007), no. 1, 53-97 (electronic). MR 2257397 (2007j:37004), https://doi.org/10.1090/S0894-0347-06-00532-7

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 20F69, 20D60, 11B30, 20B05

Retrieve articles in all journals with MSC (2010): 20F69, 20D60, 11B30, 20B05


Additional Information

Harald A. Helfgott
Affiliation: École Normale Supérieure, Département de Mathématiques, 45 rue d’Ulm, F-75230 Paris, France
Email: harald.helfgott@ens.fr

DOI: https://doi.org/10.1090/S0273-0979-2015-01475-8
Received by editor(s): March 11, 2013
Received by editor(s) in revised form: September 24, 2013, and July 30, 2014
Published electronically: February 11, 2015
Dedicated: In memory of Ákos Seress (1958–2013)
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society