Random generation of the special linear group

Eberhard, Sean; Virchow, Stefan-C.

doi:10.1090/tran/8009

Random generation of the special linear group
HTML articles powered by AMS MathViewer

by Sean Eberhard and Stefan-C. Virchow PDF

Trans. Amer. Math. Soc. 373 (2020), 3995-4011 Request permission

Abstract:

It is well known that the proportion of pairs of elements of $\operatorname {SL}(n,q)$ which generate the group tends to $1$ as $q^n\to \infty$. This was proved by Kantor and Lubotzky using the classification of finite simple groups. We give a proof of this theorem which does not depend on the classification.

An essential step in our proof is an estimate for the average of $(\operatorname {ord} g)^{-1}$ when $g$ ranges over $\operatorname {GL} (n,q)$, which may be of independent interest. We prove that this average is \[ \exp (-(2-o(1)) \sqrt {n \log n \log q}). \]

References

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
Emmanuel Breuillard, Ben Green, Robert Guralnick, and Terence Tao, Expansion in finite simple groups of Lie type, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 6, 1367–1434. MR 3353804, DOI 10.4171/JEMS/533
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
J. D. Bovey, The probability that some power of a permutation has small degree, Bull. London Math. Soc. 12 (1980), no. 1, 47–51. MR 565483, DOI 10.1112/blms/12.1.47
John Bovey and Alan Williamson, The probability of generating the symmetric group, Bull. London Math. Soc. 10 (1978), no. 1, 91–96. MR 485756, DOI 10.1112/blms/10.1.91
P. J. Cameron and W. M. Kantor, $2$-transitive and antiflag transitive collineation groups of finite projective spaces, J. Algebra 60 (1979), no. 2, 384–422. MR 549937, DOI 10.1016/0021-8693(79)90090-5
Charles W. Curtis and Irving Reiner, Methods of representation theory. Vol. I, Wiley Classics Library, John Wiley & Sons, Inc., New York, 1990. With applications to finite groups and orders; Reprint of the 1981 original; A Wiley-Interscience Publication. MR 1038525
John D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199–205. MR 251758, DOI 10.1007/BF01110210
Sean Eberhard and Stefan-Christoph Virchow, The probability of generating the symmetric group, Combinatorica 39 (2019), no. 2, 273–288. MR 3962902, DOI 10.1007/s00493-017-3629-5
Jason Fulman and Robert Guralnick, Bounds on the number and sizes of conjugacy classes in finite Chevalley groups with applications to derangements, Trans. Amer. Math. Soc. 364 (2012), no. 6, 3023–3070. MR 2888238, DOI 10.1090/S0002-9947-2012-05427-4
G. H. Hardy and S. Ramanujan, Asymptotic formulæin combinatory analysis [Proc. London Math. Soc. (2) 17 (1918), 75–115], Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI, 2000, pp. 276–309. MR 2280879
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
G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, 5th ed., The Clarendon Press, Oxford University Press, New York, 1979. MR 568909
William M. Kantor, Some topics in asymptotic group theory, Groups, combinatorics & geometry (Durham, 1990) London Math. Soc. Lecture Note Ser., vol. 165, Cambridge Univ. Press, Cambridge, 1992, pp. 403–421. MR 1200278, DOI 10.1017/CBO9780511629259.036
William M. Kantor, Antiflag Transitive Collineation Groups, ArXiv e-prints, June 2018.
William M. Kantor and Alexander Lubotzky, The probability of generating a finite classical group, Geom. Dedicata 36 (1990), no. 1, 67–87. MR 1065213, DOI 10.1007/BF00181465
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
Martin W. Liebeck and Aner Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), no. 1, 103–113. MR 1338320, DOI 10.1007/BF01263616
Martin W. Liebeck and Aner Shalev, Simple groups, permutation groups, and probability, J. Amer. Math. Soc. 12 (1999), no. 2, 497–520. MR 1639620, DOI 10.1090/S0894-0347-99-00288-X
Michael Larsen, Aner Shalev, and Pham Huu Tiep, The Waring problem for finite simple groups, Ann. of Math. (2) 174 (2011), no. 3, 1885–1950. MR 2846493, DOI 10.4007/annals.2011.174.3.10
Will Sawin, Surjectivity of norm map on subspaces of finite fields, MathOverflow, 2018. https://mathoverflow.net/q/306085 (version: 2018-07-16).
Eric Schmutz, The order of a typical matrix with entries in a finite field, Israel J. Math. 91 (1995), no. 1-3, 349–371. MR 1348322, DOI 10.1007/BF02761656
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
Richard Stong, The average order of a matrix, J. Combin. Theory Ser. A 64 (1993), no. 2, 337–343. MR 1245166, DOI 10.1016/0097-3165(93)90102-E
Michio Suzuki, Group theory. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 247, Springer-Verlag, Berlin-New York, 1982. Translated from the Japanese by the author. MR 648772, DOI 10.1007/978-3-642-61804-8