Growth in groups: ideas and perspectives

Helfgott, Harald

doi:10.1090/S0273-0979-2015-01475-8

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