Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)

 
 

 

Growth in finite simple groups of Lie type


Authors: László Pyber and Endre Szabó
Journal: J. Amer. Math. Soc. 29 (2016), 95-146
MSC (2010): Primary 20F69; Secondary 20G15, 20D06
DOI: https://doi.org/10.1090/S0894-0347-2014-00821-3
Published electronically: October 31, 2014
MathSciNet review: 3402696
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that if $ L$ is a finite simple group of Lie type and $ A$ a set of generators of $ L$, then either $ A$ grows, i.e., $ \vert A^3\vert > \vert A\vert^{1+\varepsilon }$ where $ \varepsilon $ depends only on the Lie rank of $ L$, or $ A^3=L$. This implies that for simple groups of Lie type of bounded rank a well-known conjecture of Babai holds, i.e., the diameter of any Cayley graph is polylogarithmic. We also obtain new families of expanders.

A generalization of our proof yields the following. Let $ A$ be a finite subset of $ SL(n,\mathbb{F})$, $ \mathbb{F}$ an arbitrary field, satisfying $ \big \vert A^3\big \vert\le \mathcal {K}\vert A\vert$. Then $ A$ can be covered by $ \mathcal {K}^m$, i.e., polynomially many, cosets of a virtually soluble subgroup of $ SL(n,\mathbb{F})$ which is normalized by $ A$, where $ m$ depends on $ n$.


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

  • [1] Fred Annexstein and Marc Baumslag, On the diameter and bisector size of Cayley graphs, Math. Systems Theory 26 (1993), no. 3, 271-291. MR 1209998 (94c:05036), https://doi.org/10.1007/BF01371728
  • [2] L. Babai, W. M. Kantor, and A. Lubotsky, Small-diameter Cayley graphs for finite simple groups, Eur. J. Combin. 10 (1989), no. 6, 507-522. MR 1022771 (91a:20038), https://doi.org/10.1016/S0195-6698(89)80067-8
  • [3] László Babai and Ákos Seress, On the diameter of permutation groups, Eur. J. Combin. 13 (1992), no. 4, 231-243. MR 1179520 (93h:20001), https://doi.org/10.1016/S0195-6698(05)80029-0
  • [4] Cristina Blanco, Gabriela Jeronimo, and Pablo Solernó, Computing generators of the ideal of a smooth affine algebraic variety, J. Symbolic Comput. 38 (2004), no. 1, 843-872. MR 2094559 (2006c:14085), https://doi.org/10.1016/j.jsc.2004.02.002
  • [5] Jean Bourgain and Alex Gamburd, Uniform expansion bounds for Cayley graphs of $ {\rm SL}_2(\mathbb{F}_p)$, Ann. Math. (2) 167 (2008), no. 2, 625-642. MR 2415383 (2010b:20070), https://doi.org/10.4007/annals.2008.167.625
  • [6] Jean Bourgain and Alex 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
  • [7] Jean Bourgain, Alex Gamburd, and Peter 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
  • [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 (2005d:11028), https://doi.org/10.1007/s00039-004-0451-1
  • [9] Emmanuel Breuillard, Ben Green, and Terence Tao, Linear approximate groups, Electron. Res. Announc. Math. Sci. 17 (2010), 57-67. MR 2718104 (2011g:11018), https://doi.org/10.3934/era.2010.17.57
  • [10] Emmanuel Breuillard, Ben Green, and Terence 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
  • [11] Emmanuel Breuillard and Ben 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
  • [12] Roger W. Carter, Simple groups of Lie type, Pure and Applied Mathematics, Vol. 28, John Wiley & Sons, London-New York-Sydney, 1972. MR 0407163 (53 #10946)
  • [13] Roger W. Carter, Finite groups of Lie type, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1985. Conjugacy classes and complex characters; A Wiley-Interscience Publication. MR 794307 (87d:20060)
  • [14] Arjeh M. Cohen and Gary M. Seitz, The $ r$-rank of the groups of exceptional Lie type, Nederl. Akad. Wetensch. Indag. Math. 49 (1987), no. 3, 251-259. MR 914084 (88k:20062)
  • [15] Claude Chevalley, Classification des groupes algébriques semi-simples, Springer-Verlag, Berlin, 2005 (French). Collected works. Vol. 3; Edited and with a preface by P. Cartier; With the collaboration of Cartier, A. Grothendieck, and M. Lazard. MR 2124841 (2006b:20068)
  • [16] Oren 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
  • [17] Klaus Doerk and Trevor Hawkes, Finite soluble groups, de Gruyter Expositions in Mathematics, vol. 4, Walter de Gruyter & Co., Berlin, 1992. MR 1169099 (93k:20033)
  • [18] 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 (2003e:52034), https://doi.org/10.1023/A:1012799318591
  • [19] Walter Feit and Jacques Tits, Projective representations of minimum degree of group extensions, Canad. J. Math. 30 (1978), no. 5, 1092-1102. MR 0498824 (58 #16861)
  • [20] G. A. Freĭman, Groups and the inverse problems of additive number theory, Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian), Kalinin. Gos. Univ., Moscow, 1973, pp. 175-183 (Russian). MR 0435006 (55 #7968)
  • [21] Gregory A. Freiman, On finite subsets of nonabelian groups with small doubling, Proc. Amer. Math. Soc. 140 (2012), no. 9, 2997-3002. MR 2917072, https://doi.org/10.1090/S0002-9939-2012-11156-6
  • [22] William Fulton, Intersection theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 2, Springer-Verlag, Berlin, 1984. MR 732620 (85k:14004)
  • [23] Nick Gill and Harald Andrés 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
  • [24] Alireza Salehi Golsefidy and Peter Sarnak, The affine sieve, J. Amer. Math. Soc. 26 (2013), no. 4, 1085-1105. MR 3073885, https://doi.org/10.1090/S0894-0347-2013-00764-X
  • [25] W. T. Gowers, Quasirandom groups, Combin. Probab. Comput. 17 (2008), no. 3, 363-387. MR 2410393 (2009f:20105), https://doi.org/10.1017/S0963548307008826
  • [26] Robin Hartshorne, Algebraic geometry, Springer-Verlag, New York-Heidelberg, 1977. Graduate Texts in Mathematics, No. 52. MR 0463157 (57 #3116)
  • [27] H. A. Helfgott, Growth and generation in $ {\rm SL}_2(\mathbb{Z}/p\mathbb{Z})$, Ann. Math. (2) 167 (2008), no. 2, 601-623. MR 2415382 (2009i:20094), https://doi.org/10.4007/annals.2008.167.601
  • [28] 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
  • [29] H. A. Helfgott, Growth in groups: ideas and perspectives, preprint, arXiv:1303.0239
  • [30] E. Hrushovski, The elementary theory of the Frobenius automorphisms. preprint, arXiv:math.LO/0406514
  • [31] Ehud 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
  • [32] 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)
  • [33] James E. Humphreys, Linear algebraic groups, Graduate Texts in Mathematics, NO. 21, Springer-Verlag, New York-Heidelberg, 1975. MR 0396773 (53 #633)
  • [34] James E. Humphreys, Conjugacy classes in semisimple algebraic groups, Mathematical Surveys and Monographs, vol. 43, American Mathematical Society, Providence, RI, 1995. MR 1343976 (97i:20057)
  • [35] I. Martin Isaacs, Character theory of finite groups, AMS Chelsea Publishing, Providence, RI, 2006. Corrected reprint of the 1976 original [Academic Press, New York; MR0460423]. MR 2270898
  • [36] E. I. Khukhro, Ant. A. Klyachko, N. Yu. Makarenko, and Yu. B. Melnikova, Automorphism invariance and identities, Bull. Lond. Math. Soc. 41 (2009), no. 5, 804-816. MR 2557461 (2010k:20050), https://doi.org/10.1112/blms/bdp056
  • [37] Peter Kleidman and Martin Liebeck, The subgroup structure of the finite classical groups, London Mathematical Society Lecture Note Series, vol. 129, Cambridge University Press, Cambridge, 1990. MR 1057341 (91g:20001)
  • [38] 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, https://doi.org/10.1215/00127094-1593272
  • [39] Michael Larsen, Exponential generation and largeness for compact $ p$-adic Lie groups, Algebra Number Theory 4 (2010), no. 8, 1029-1038. MR 2832632, https://doi.org/10.2140/ant.2010.4.1029
  • [40] 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 0360852 (50 #13299)
  • [41] Martin W. Liebeck and Gary M. Seitz, On the subgroup structure of exceptional groups of Lie type, Trans. Amer. Math. Soc. 350 (1998), no. 9, 3409-3482. MR 1458329 (99j:20055), https://doi.org/10.1090/S0002-9947-98-02121-7
  • [42] Alexander 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
  • [43] David Mumford, Varieties defined by quadratic equations, Questions on Algebraic Varieties (C.I.M.E., III Ciclo, Varenna, 1969) Edizioni Cremonese, Rome, 1970, pp. 29-100. MR 0282975 (44 #209)
  • [44] Madhav 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
  • [45] 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
  • [46] Nikolay Nikolov and Dan Segal, On finitely generated profinite groups. I. Strong completeness and uniform bounds, Ann. Math. (2) 165 (2007), no. 1, 171-238. MR 2276769 (2008f:20052), https://doi.org/10.4007/annals.2007.165.171
  • [47] John E. Olson, On the sum of two sets in a group, J. Number Theory 18 (1984), no. 1, 110-120. MR 734442 (85j:20021), https://doi.org/10.1016/0022-314X(84)90047-7
  • [48] L. Pyber, E. Szabó, Growth in finite simple groups of Lie type. announcement: arXiv:1001.4556
  • [49] L. Pyber, E. Szabó, Growth in finite simple groups of Lie type of bounded rank, 2010, preprint, arXiv:1005.1858
  • [50] L. Pyber, E. Szabó, Growth in linear groups, in preparation
  • [51] László Pyber, Asymptotic results for permutation groups, Groups and computation (New Brunswick, NJ, 1991) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 11, Amer. Math. Soc., Providence, RI, 1993, pp. 197-219. MR 1235804 (94g:20003)
  • [52] 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)
  • [53] Terence 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
  • [54] Péter 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

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC (2010): 20F69, 20G15, 20D06

Retrieve articles in all journals with MSC (2010): 20F69, 20G15, 20D06


Additional Information

László Pyber
Affiliation: A. Rényi Institute of Mathematics, Hungarian Academy of Sciences, P.O. Box 127, H-1364 Budapest, Hungary
Email: pyber.laszlo@renyi.mta.hu

Endre Szabó
Affiliation: A. Rényi Institute of Mathematics, Hungarian Academy of Sciences, P.O. Box 127, H-1364 Budapest, Hungary
Email: szabo.endre@renyi.mta.hu

DOI: https://doi.org/10.1090/S0894-0347-2014-00821-3
Keywords: Growth, finite simple groups, algebraic groups
Received by editor(s): June 11, 2014
Received by editor(s) in revised form: September 15, 2014
Published electronically: October 31, 2014
Additional Notes: The first author is supported in part by OTKA 78439 and K84233
The second author is supported in part by OTKA NK81203, K84233 and by the MTA Rényi “Lendület” Groups and Graphs Research Group
Article copyright: © Copyright 2014 American Mathematical Society

American Mathematical Society