Growth in groups: ideas and perspectives
HTML articles powered by AMS MathViewer
- by Harald A. Helfgott PDF
- Bull. Amer. Math. Soc. 52 (2015), 357-413 Request permission
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
- Noga Alon and Joel 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, DOI 10.1002/0471722154
- László Babai, On the length of subgroup chains in the symmetric group, Comm. Algebra 14 (1986), no. 9, 1729–1736. MR 860123, DOI 10.1080/00927878608823393
- László 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, DOI 10.1145/1109557.1109648
- László Babai, On the order of doubly transitive permutation groups, Invent. Math. 65 (1981/82), no. 3, 473–484. MR 643565, DOI 10.1007/BF01396631
- H. Bass, The degree of polynomial growth of finitely generated nilpotent groups, Proc. London Math. Soc. (3) 25 (1972), 603–614. MR 379672, DOI 10.1112/plms/s3-25.4.603
- László Babai, Robert Beals, and Ákos 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. MR 2291003
- Dave Bayer and Persi Diaconis, Trailing the dovetail shuffle to its lair, Ann. Appl. Probab. 2 (1992), no. 2, 294–313. MR 1161056
- Jean Bourgain and Alex Gamburd, Expansion and random walks in $\textrm {SL}_d(\Bbb Z/p^n\Bbb Z)$. I, J. Eur. Math. Soc. (JEMS) 10 (2008), no. 4, 987–1011. MR 2443926, DOI 10.4171/JEMS/137
- Jean Bourgain and Alex Gamburd, On the spectral gap for finitely-generated subgroups of $\rm SU(2)$, Invent. Math. 171 (2008), no. 1, 83–121. MR 2358056, DOI 10.1007/s00222-007-0072-z
- Jean Bourgain and Alex Gamburd, Uniform expansion bounds for Cayley graphs of $\textrm {SL}_2(\Bbb F_p)$, Ann. of Math. (2) 167 (2008), no. 2, 625–642. MR 2415383, DOI 10.4007/annals.2008.167.625
- Jean Bourgain and Alex Gamburd, Expansion and random walks in $\textrm {SL}_d(\Bbb Z/p^n\Bbb Z)$. II, J. Eur. Math. Soc. (JEMS) 11 (2009), no. 5, 1057–1103. With an appendix by Bourgain. MR 2538500, DOI 10.4171/JEMS/175
- Emmanuel Breuillard and Alex Gamburd, Strong uniform expansion in $\textrm {SL}(2,p)$, Geom. Funct. Anal. 20 (2010), no. 5, 1201–1209. MR 2746951, DOI 10.1007/s00039-010-0094-3
- Emmanuel Breuillard and Ben Green, Approximate groups. I: The torsion-free nilpotent case, J. Inst. Math. Jussieu 10 (2011), no. 1, 37–57. MR 2749571, DOI 10.1017/S1474748010000150
- Emmanuel Breuillard and Ben Green, Approximate groups, II: The solvable linear case, Q. J. Math. 62 (2011), no. 3, 513–521. MR 2825469, DOI 10.1093/qmath/haq011
- Emmanuel Breuillard and Ben Green, Approximate groups III: the unitary case, Turkish J. Math. 36 (2012), no. 2, 199–215. MR 2912036
- E. Breuillard, B. Green, R. Guralnick, and T. Tao. Expansion in finite simple groups of Lie type. Available as arxiv.org:1309.1975.
- John Bamberg, Nick Gill, Thomas P. Hayes, Harald A. Helfgott, Ákos Seress, and Pablo Spiga, Bounds on the diameter of Cayley graphs of the symmetric group, J. Algebraic Combin. 40 (2014), no. 1, 1–22. MR 3226815, DOI 10.1007/s10801-013-0476-3
- 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, DOI 10.1112/S0024610706022721
- Jean Bourgain, Alex Gamburd, and Peter Sarnak, Affine linear sieve, expanders, and sum-product, Invent. Math. 179 (2010), no. 3, 559–644. MR 2587341, DOI 10.1007/s00222-009-0225-3
- Jean Bourgain, Alex Gamburd, and Peter Sarnak, Generalization of Selberg’s $\frac {3}{16}$ theorem and affine sieve, Acta Math. 207 (2011), no. 2, 255–290. MR 2892611, DOI 10.1007/s11511-012-0070-x
- Emmanuel Breuillard, Ben Green, and Terence Tao, Approximate subgroups of linear groups, Geom. Funct. Anal. 21 (2011), no. 4, 774–819. MR 2827010, DOI 10.1007/s00039-011-0122-y
- Emmanuel Breuillard, Ben Green, and Terence Tao, The structure of approximate groups, Publ. Math. Inst. Hautes Études Sci. 116 (2012), 115–221. MR 3090256, DOI 10.1007/s10240-012-0043-9
- 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, DOI 10.1017/S0963548300000237
- László Babai and Thomas 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. MR 2298365
- Boaz Barak, Russell Impagliazzo, and Avi Wigderson, Extracting randomness using few independent sources, SIAM J. Comput. 36 (2006), no. 4, 1095–1118. MR 2272272, DOI 10.1137/S0097539705447141
- 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, DOI 10.1016/S0195-6698(89)80067-8
- 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, DOI 10.1007/s00039-004-0451-1
- 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.
- László Babai, Nikolay Nikolov, and László 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
- 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, Actualités Scientifiques et Industrielles [Current Scientific and Industrial Topics], No. 1349, Hermann, Paris, 1972. MR 0573068
- Jack Button and Colva M. Roney-Dougal, An explicit upper bound for the Helfgott delta in $\textrm {SL}(2,p)$, J. Algebra 421 (2015), 493–511. MR 3272393, DOI 10.1016/j.jalgebra.2014.09.001
- Robert Brooks, The spectral geometry of a tower of coverings, J. Differential Geom. 23 (1986), no. 1, 97–107. MR 840402
- Robert Brooks, On the angles between certain arithmetically defined subspaces of $\textbf {C}^n$, Ann. Inst. Fourier (Grenoble) 37 (1987), no. 1, 175–185 (English, with French summary). MR 894565
- László Babai and Ákos 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, DOI 10.1016/0097-3165(87)90023-9
- 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.
- László Babai and Ákos Seress, On the diameter of Cayley graphs of the symmetric group, J. Combin. Theory Ser. A 49 (1988), no. 1, 175–179. MR 957215, DOI 10.1016/0097-3165(88)90033-7
- László Babai and Ákos Seress, On the diameter of permutation groups, European J. Combin. 13 (1992), no. 4, 231–243. MR 1179520, DOI 10.1016/S0195-6698(05)80029-0
- Antal Balog and Endre Szemerédi, A statistical theorem of set addition, Combinatorica 14 (1994), no. 3, 263–268. MR 1305895, DOI 10.1007/BF01212974
- M. Burger. Petites valeurs propres du Laplacien et topologie de Fell. PhD thesis, Université de Lausanne, 1986.
- Peter Buser, Cubic graphs and the first eigenvalue of a Riemann surface, Math. Z. 162 (1978), no. 1, 87–99. MR 505920, DOI 10.1007/BF01437826
- Jean Bourgain and Péter P. Varjú, Expansion in $SL_d(\textbf {Z}/q\textbf {Z}),\,q$ arbitrary, Invent. Math. 188 (2012), no. 1, 151–173. MR 2897695, DOI 10.1007/s00222-011-0345-4
- Mei-Chu Chang, A polynomial bound in Freiman’s theorem, Duke Math. J. 113 (2002), no. 3, 399–419. MR 1909605, DOI 10.1215/S0012-7094-02-11331-3
- Mei-Chu Chang, Product theorems in $\textrm {SL}_2$ and $\textrm {SL}_3$, J. Inst. Math. Jussieu 7 (2008), no. 1, 1–25. MR 2398145, DOI 10.1017/S1474748007000126
- Ernie Croot and Olof Sisask, A probabilistic technique for finding almost-periods of convolutions, Geom. Funct. Anal. 20 (2010), no. 6, 1367–1396. MR 2738997, DOI 10.1007/s00039-010-0101-8
- Oren Dinai, Poly-log diameter bounds for some families of finite groups, Proc. Amer. Math. Soc. 134 (2006), no. 11, 3137–3142. MR 2231895, DOI 10.1090/S0002-9939-06-08384-5
- Oren Dinai, Growth in $\textrm {SL}_2$ over finite fields, J. Group Theory 14 (2011), no. 2, 273–297. MR 2788087, DOI 10.1515/JGT.2010.056
- John D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199–205. MR 251758, DOI 10.1007/BF01110210
- John D. Dixon and Brian Mortimer, Permutation groups, Graduate Texts in Mathematics, vol. 163, Springer-Verlag, New York, 1996. MR 1409812, DOI 10.1007/978-1-4612-0731-3
- Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813, DOI 10.1007/BF00535487
- 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
- Persi Diaconis and Laurent Saloff-Coste, Comparison techniques for random walk on finite groups, Ann. Probab. 21 (1993), no. 4, 2131–2156. MR 1245303
- Giuliana Davidoff, Peter Sarnak, and Alain Valette, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts, vol. 55, Cambridge University Press, Cambridge, 2003. MR 1989434, DOI 10.1017/CBO9780511615825
- Jordan S. Ellenberg, Chris Hall, and Emmanuel Kowalski, Expander graphs, gonality, and variation of Galois representations, Duke Math. J. 161 (2012), no. 7, 1233–1275. MR 2922374, DOI 10.1215/00127094-1593272
- György Elekes and Zoltán Király, On the combinatorics of projective mappings, J. Algebraic Combin. 14 (2001), no. 3, 183–197. MR 1869409, DOI 10.1023/A:1012799318591
- György Elekes, On the number of sums and products, Acta Arith. 81 (1997), no. 4, 365–367. MR 1472816, DOI 10.4064/aa-81-4-365-367
- G. A. Edgar and Chris Miller, Borel subrings of the reals, Proc. Amer. Math. Soc. 131 (2003), no. 4, 1121–1129. MR 1948103, DOI 10.1090/S0002-9939-02-06653-4
- Alex Eskin, Shahar Mozes, and Hee Oh, On uniform exponential growth for linear groups, Invent. Math. 160 (2005), no. 1, 1–30. MR 2129706, DOI 10.1007/s00222-004-0378-z
- 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
- William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR 1153249, DOI 10.1007/978-1-4612-0979-9
- Gonzalo Fiz Pontiveros, Sums of dilates in $\Bbb Z_p$, Combin. Probab. Comput. 22 (2013), no. 2, 282–293. MR 3021335, DOI 10.1017/S0963548312000466
- David Fisher, Nets Hawk Katz, and Irine Peng, Approximate multiplicative groups in nilpotent Lie groups, Proc. Amer. Math. Soc. 138 (2010), no. 5, 1575–1580. MR 2587441, DOI 10.1090/S0002-9939-10-10078-1
- G. A. Freĭman, Foundations of a structural theory of set addition, Translations of Mathematical Monographs, Vol 37, American Mathematical Society, Providence, R.I., 1973. Translated from the Russian. MR 0360496
- Harry Furstenberg, Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions, J. Analyse Math. 31 (1977), 204–256. MR 498471, DOI 10.1007/BF02813304
- Alex Gamburd, On the spectral gap for infinite index “congruence” subgroups of $\textrm {SL}_2(\mathbf Z)$, Israel J. Math. 127 (2002), 157–200. MR 1900698, DOI 10.1007/BF02784530
- Nick Gill and Harald Andrés Helfgott, Growth in solvable subgroups of $\textrm {GL}_r(\Bbb Z/p\Bbb Z)$, Math. Ann. 360 (2014), no. 1-2, 157–208. MR 3263161, DOI 10.1007/s00208-014-1008-8
- Nick Gill and Harald Andrés Helfgott, Growth of small generating sets in $\textrm {SL}_n(\Bbb Z/p\Bbb Z)$, Int. Math. Res. Not. IMRN 18 (2011), 4226–4251. MR 2836020
- 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.
- 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, DOI 10.1090/crmp/043/15
- 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, DOI 10.1007/s000390050065
- W. T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), no. 3, 465–588. MR 1844079, DOI 10.1007/s00039-001-0332-9
- W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363–387. MR 2410393, DOI 10.1017/S0963548307008826
- Ben Green and Imre Z. Ruzsa, Sum-free sets in abelian groups, Israel J. Math. 147 (2005), 157–188. MR 2166359, DOI 10.1007/BF02785363
- A. Granville. Additive combinatorics. Unpublished notes.
- Mikhael Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math. 53 (1981), 53–73. MR 623534
- Alex Gamburd and Mehrdad Shahshahani, Uniform diameter bounds for some families of Cayley graphs, Int. Math. Res. Not. 71 (2004), 3813–3824. MR 2104475, DOI 10.1155/S1073792804140579
- Ben Green and Terence Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481–547. MR 2415379, DOI 10.4007/annals.2008.167.481
- Yves Guivarc’h, Croissance polynomiale et périodes des fonctions harmoniques, Bull. Soc. Math. France 101 (1973), 333–379 (French). MR 369608
- A. Salehi Golsefidy and Péter P. Varjú, Expansion in perfect groups, Geom. Funct. Anal. 22 (2012), no. 6, 1832–1891. MR 3000503, DOI 10.1007/s00039-012-0190-7
- H. A. Helfgott, Growth and generation in $\textrm {SL}_2(\Bbb Z/p\Bbb Z)$, Ann. of Math. (2) 167 (2008), no. 2, 601–623. MR 2415382, DOI 10.4007/annals.2008.167.601
- H. A. Helfgott, Growth in $\textrm {SL}_3(\Bbb Z/p\Bbb Z)$, J. Eur. Math. Soc. (JEMS) 13 (2011), no. 3, 761–851. MR 2781932, DOI 10.4171/JEMS/267
- Bernard Host and Bryna Kra, Nonconventional ergodic averages and nilmanifolds, Ann. of Math. (2) 161 (2005), no. 1, 397–488. MR 2150389, DOI 10.4007/annals.2005.161.397
- E. Hrushovski and A. Pillay, Definable subgroups of algebraic groups over finite fields, J. Reine Angew. Math. 462 (1995), 69–91. MR 1329903
- Ehud Hrushovski, Stable group theory and approximate subgroups, J. Amer. Math. Soc. 25 (2012), no. 1, 189–243. MR 2833482, DOI 10.1090/S0894-0347-2011-00708-X
- Harald A. Helfgott and Ákos Seress, On the diameter of permutation groups, Ann. of Math. (2) 179 (2014), no. 2, 611–658. MR 3152942, DOI 10.4007/annals.2014.179.2.4
- Harald A. Helfgott, Ákos Seress, and Andrzej Zuk, Random generators of the symmetric group: diameter, mixing time and spectral gap, J. Algebra 421 (2015), 349–368. MR 3272386, DOI 10.1016/j.jalgebra.2014.08.033
- Ehud Hrushovski and Frank 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, DOI 10.1017/CBO9780511735219.005
- Martin Kassabov, Symmetric groups and expander graphs, Invent. Math. 170 (2007), no. 2, 327–354. MR 2342639, DOI 10.1007/s00222-007-0065-y
- 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
- Harry Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336–354. MR 109367, DOI 10.1090/S0002-9947-1959-0109367-6
- 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.
- 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
- E. Kowalski. Expander graphs. Course notes available at http://www.math.ethz.ch/~kowalski/expander-graphs.pdf.
- E. Kowalski. Sieve in expansion. Séminaire Bourbaki, 63ème année, 2010-2011, no. 1028.
- Emmanuel Kowalski, Explicit growth and expansion for $\textrm {SL}_2$, Int. Math. Res. Not. IMRN 24 (2013), 5645–5708. MR 3144176, DOI 10.1093/imrn/rns214
- Michael Larsen, Navigating the Cayley graph of $\textrm {SL}_2(\Bbb F_p)$, Int. Math. Res. Not. 27 (2003), 1465–1471. MR 1976231, DOI 10.1155/S1073792803130383
- Oliver Lorscheid, Algebraic groups over the field with one element, Math. Z. 271 (2012), no. 1-2, 117–138. MR 2917136, DOI 10.1007/s00209-011-0855-1
- 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
- Michael J. Larsen and Richard Pink, Finite subgroups of algebraic groups, J. Amer. Math. Soc. 24 (2011), no. 4, 1105–1158. MR 2813339, DOI 10.1090/S0894-0347-2011-00695-4
- A. Lubotzky, R. Phillips, and P. Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118, DOI 10.1007/BF02126799
- David A. Levin, Yuval Peres, and Elizabeth 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, DOI 10.1090/mbk/058
- John D. Lafferty and Daniel Rockmore, Fast Fourier analysis for $\textrm {SL}_2$ over a finite field and related numerical experiments, Experiment. Math. 1 (1992), no. 2, 115–139. MR 1203870
- Vicente Landazuri and Gary M. Seitz, On the minimal degrees of projective representations of the finite Chevalley groups, J. Algebra 32 (1974), 418–443. MR 360852, DOI 10.1016/0021-8693(74)90150-1
- Alexander Lubotzky, Expander graphs in pure and applied mathematics, Bull. Amer. Math. Soc. (N.S.) 49 (2012), no. 1, 113–162. MR 2869010, DOI 10.1090/S0273-0979-2011-01359-3
- Serge Lang and André Weil, Number of points of varieties in finite fields, Amer. J. Math. 76 (1954), 819–827. MR 65218, DOI 10.2307/2372655
- 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, DOI 10.1090/dimacs/010/08
- Pierre McKenzie, Permutations of bounded degree generate groups of polynomial diameter, Inform. Process. Lett. 19 (1984), no. 5, 253–254. MR 777808, DOI 10.1016/0020-0190(84)90062-0
- John Milnor, Growth of finitely generated solvable groups, J. Differential Geometry 2 (1968), 447–449. MR 244899
- Florian Martin and Alain Valette, Markov operators on the solvable Baumslag-Solitar groups, Experiment. Math. 9 (2000), no. 2, 291–300. MR 1780213
- 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, DOI 10.1112/plms/s3-48.3.514
- Michael A. Nielsen and Isaac L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000. MR 1796805
- Madhav V. Nori, On subgroups of $\textrm {GL}_n(\textbf {F}_p)$, Invent. Math. 88 (1987), no. 2, 257–275. MR 880952, DOI 10.1007/BF01388909
- 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, DOI 10.4171/JEMS/275
- Giorgis Petridis, New proofs of Plünnecke-type estimates for product sets in groups, Combinatorica 32 (2012), no. 6, 721–733. MR 3063158, DOI 10.1007/s00493-012-2818-5
- Helmut Plünnecke, Eine zahlentheoretische Anwendung der Graphentheorie, J. Reine Angew. Math. 243 (1970), 171–183 (German). MR 266892, DOI 10.1515/crll.1970.243.171
- Cheryl E. Praeger, Laszló Pyber, Pablo Spiga, and Endre Szabó, Graphs with automorphism groups admitting composition factors of bounded rank, Proc. Amer. Math. Soc. 140 (2012), no. 7, 2307–2318. MR 2898694, DOI 10.1090/S0002-9939-2011-11100-6
- L. Pyber and E. Szabó. Growth in finite simple groups of Lie type of bounded rank. Submitted. Available at arxiv.org:1005.1881.
- László Pyber and Endre Szabó, Growth in linear groups, Thin groups and superstrong approximation, Math. Sci. Res. Inst. Publ., vol. 61, Cambridge Univ. Press, Cambridge, 2014, pp. 253–268. MR 3220893
- 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, DOI 10.1016/0097-3165(93)90053-B
- Alexander A. Razborov, A product theorem in free groups, Ann. of Math. (2) 179 (2014), no. 2, 405–429. MR 3152939, DOI 10.4007/annals.2014.179.2.1
- V. A. Rohlin, Generators in ergodic theory, Vestnik Leningrad. Univ. 18 (1963), no. 1, 26–32 (Russian, with English summary). MR 0193206
- K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 104–109. MR 51853, DOI 10.1112/jlms/s1-28.1.104
- 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
- Imre Z. Ruzsa, An application of graph theory to additive number theory, Sci. Ser. A Math. Sci. (N.S.) 3 (1989), 97–109. MR 2314377
- Imre Z. Ruzsa, Arithmetic progressions in sumsets, Acta Arith. 60 (1991), no. 2, 191–202. MR 1139055, DOI 10.4064/aa-60-2-191-202
- I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379–388. MR 1281447, DOI 10.1007/BF01876039
- Imre 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
- Tom Sanders, On the Bogolyubov-Ruzsa lemma, Anal. PDE 5 (2012), no. 3, 627–655. MR 2994508, DOI 10.2140/apde.2012.5.627
- Atle 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
- Ákos Seress, Permutation group algorithms, Cambridge Tracts in Mathematics, vol. 152, Cambridge University Press, Cambridge, 2003. MR 1970241, DOI 10.1017/CBO9780511546549
- Yehuda Shalom, Expanding graphs and invariant means, Combinatorica 17 (1997), no. 4, 555–575. MR 1645694, DOI 10.1007/BF01195004
- Yehuda 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, DOI 10.1007/978-1-4612-1544-8_{2}3
- Charles 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
- 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.
- József Solymosi, Bounding multiplicative energy by the sumset, Adv. Math. 222 (2009), no. 2, 402–408. MR 2538014, DOI 10.1016/j.aim.2009.04.006
- Jan-Christoph Schlage-Puchta, Applications of character estimates to statistical problems for the symmetric group, Combinatorica 32 (2012), no. 3, 309–323. MR 2965280, DOI 10.1007/s00493-012-2502-9
- Pablo 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, DOI 10.1515/JGT.2011.097
- 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, DOI 10.1007/BFb0076175
- 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, DOI 10.1215/S0012-7094-04-12915-X
- Endre Szemerédi and William T. Trotter Jr., Extremal problems in discrete geometry, Combinatorica 3 (1983), no. 3-4, 381–392. MR 729791, DOI 10.1007/BF02579194
- Peter Sarnak and Xiao Xi Xue, Bounds for multiplicities of automorphic representations, Duke Math. J. 64 (1991), no. 1, 207–227. MR 1131400, DOI 10.1215/S0012-7094-91-06410-0
- B. Szegedy. On higher order Fourier analysis. Available as arxiv.org:1203.2260.
- E. Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89–104. MR 245555, DOI 10.1007/BF01894569
- T. Tao. Course notes. Available at http://www.math.ucla.edu/~tao/254b.1.12w/.
- Terence Tao, Product set estimates for non-commutative groups, Combinatorica 28 (2008), no. 5, 547–594. MR 2501249, DOI 10.1007/s00493-008-2271-7
- Terence Tao, Freiman’s theorem for solvable groups, Contrib. Discrete Math. 5 (2010), no. 2, 137–184. MR 2791295
- 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
- J. Tits, Free subgroups in linear groups, J. Algebra 20 (1972), 250–270. MR 286898, DOI 10.1016/0021-8693(72)90058-0
- M. Tointon. Freiman’s theorem in an arbitrary nilpotent group. Submitted. Available as arxiv:1211.3989.
- Terence Tao and Van Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012, DOI 10.1017/CBO9780511755149
- Péter Pál Varjú, Random walks in compact groups, Doc. Math. 18 (2013), 1137–1175. MR 3138842
- Péter P. Varjú, Expansion in $SL_d(\scr O_K/I)$, $I$ square-free, J. Eur. Math. Soc. (JEMS) 14 (2012), no. 1, 273–305. MR 2862040, DOI 10.4171/JEMS/302
- Boris Weisfeiler, Strong approximation for Zariski-dense subgroups of semisimple algebraic groups, Ann. of Math. (2) 120 (1984), no. 2, 271–315. MR 763908, DOI 10.2307/2006943
- Helmut Wielandt, Finite permutation groups, Academic Press, New York-London, 1964. Translated from the German by R. Bercov. MR 0183775
- Joseph A. Wolf, Growth of finitely generated solvable groups and curvature of Riemannian manifolds, J. Differential Geometry 2 (1968), 421–446. MR 248688
- Tamar Ziegler, Universal characteristic factors and Furstenberg averages, J. Amer. Math. Soc. 20 (2007), no. 1, 53–97. MR 2257397, DOI 10.1090/S0894-0347-06-00532-7
Additional Information
- Harald A. Helfgott
- Affiliation: École Normale Supérieure, Département de Mathématiques, 45 rue d’Ulm, F-75230 Paris, France
- MR Author ID: 644718
- Email: harald.helfgott@ens.fr
- 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
- © Copyright 2015 American Mathematical Society
- 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
- MathSciNet review: 3348442
Dedicated: In memory of Ákos Seress (1958–2013)