×

Random generation of the special linear group. (English) Zbl 1445.20044

In [Math. Z. 110, 199–205 (1969; Zbl 0176.29901)], the reviewer proved a longstanding conjecture of Netto that the probability \(\Pr(\left\langle \pi,\sigma\right\rangle =A_{n})\) that two random permutations of the alternating group generate all of \(A_{n}\) tends to \(1\) as \(n\rightarrow\infty\). He also raised the question of whether the same was true for the other families of simple groups. Over the next two decades other mathematicians answered the latter question in the affirmative (see [W. M. Kantor and A. Lubotzky, Geom. Dedicata 36, No. 1, 67–87 (1990; Zbl 0718.20011); M. W. Liebeck and A. Shalev, Geom. Dedicata 56, No. 1, 103–113 (1995; Zbl 0836.20068)]). For most infinite families of finite simple groups these proofs depend on the classification of finite simple groups (CFSG) and it is not known whether there are more elementary proofs. For example a closely related result, also based on CFSG, states that for random elements \(\pi,\sigma\) of \(\mathrm{SL}(n,q)\) we have \(\Pr(\left\langle \pi,\sigma\right\rangle \neq \mathrm{SL}(n,q))=2q^{-n}+O(q^{-7(n-1)/6})\) (see [W. M. Kantor, Lond. Math. Soc. Lect. Note Ser. 165, 403–421 (1992; Zbl 0830.20033)]). In the present paper, the authors give a elementary proof (avoiding CFSG) of a weaker result: \(\Pr(\left\langle \pi,\sigma\right\rangle \neq \mathrm{SL}(n,q))\leq\exp(-c\sqrt{n}\log q)+\exp (-(2-o(1))\sqrt{n\log n\log q}\) for some absolute constant \(c>0\). A crucial lemma which is used in the proof may be of independent interest: \(\eta_{G}:=\left\vert G\right\vert ^{-1}\sum_{g\in G}1/ord(g)\leq\exp (-(2-o(1))\sqrt{n\log n\log q})\) whenever \(G=GL(n,q), \mathrm{PGL}(n,q),\mathrm{SL}(n,q)\) or \(\mathrm{PSL}(n,q)\) (note that \(1/\eta_{G}\) is the harmonic mean of the orders of the elements of \(G\)).

MSC:

20G40 Linear algebraic groups over finite fields
20F05 Generators, relations, and presentations of groups
20P05 Probabilistic methods in group theory
20D06 Simple groups: alternating groups and groups of Lie type

Software:

MathOverflow

References:

[1] Babai, L\'{a}szl\'{o}; Beals, Robert; Seress, \'{A}kos, On the diameter of the symmetric group: polynomial bounds. Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1108-1112 (2004), ACM, New York · Zbl 1318.20002
[2] Breuillard, Emmanuel; Green, Ben; Guralnick, Robert; Tao, Terence, Expansion in finite simple groups of Lie type, J. Eur. Math. Soc. (JEMS), 17, 6, 1367-1434 (2015) · Zbl 1331.20060 · doi:10.4171/JEMS/533
[3] Babai, L\'{a}szl\'{o}; Hayes, Thomas P., 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, 1057-1066 (2005), ACM, New York · Zbl 1297.68080
[4] Bovey, J. D., The probability that some power of a permutation has small degree, Bull. London Math. Soc., 12, 1, 47-51 (1980) · Zbl 0436.20002 · doi:10.1112/blms/12.1.47
[5] Bovey, John; Williamson, Alan, The probability of generating the symmetric group, Bull. London Math. Soc., 10, 1, 91-96 (1978) · Zbl 0384.20003 · doi:10.1112/blms/10.1.91
[6] Cameron, P. J.; Kantor, W. M., \(2\)-transitive and antiflag transitive collineation groups of finite projective spaces, J. Algebra, 60, 2, 384-422 (1979) · Zbl 0417.20044 · doi:10.1016/0021-8693(79)90090-5
[7] Curtis, Charles W.; Reiner, Irving, Methods of representation theory. Vol. I, Wiley Classics Library, xxiv+819 pp. (1990), John Wiley & Sons, Inc., New York · Zbl 0698.20001
[8] Dixon, John D., The probability of generating the symmetric group, Math. Z., 110, 199-205 (1969) · Zbl 0176.29901 · doi:10.1007/BF01110210
[9] Eberhard, Sean; Virchow, Stefan-Christoph, The probability of generating the symmetric group, Combinatorica, 39, 2, 273-288 (2019) · Zbl 1438.20003 · doi:10.1007/s00493-017-3629-5
[10] Fulman, Jason; Guralnick, Robert, Bounds on the number and sizes of conjugacy classes in finite Chevalley groups with applications to derangements, Trans. Amer. Math. Soc., 364, 6, 3023-3070 (2012) · Zbl 1256.20048 · doi:10.1090/S0002-9947-2012-05427-4
[11] Hardy, G. H.; Ramanujan, S., Asymptotic formul\ae in combinatory analysis [Proc. London Math. Soc. (2) {\bf17} (1918), 75-115]. Collected papers of Srinivasa Ramanujan, 276-309 (2000), AMS Chelsea Publ., Providence, RI · JFM 46.0198.04
[12] Helfgott, Harald A.; Seress, \'{A}kos; Zuk, Andrzej, Random generators of the symmetric group: diameter, mixing time and spectral gap, J. Algebra, 421, 349-368 (2015) · Zbl 1310.20003 · doi:10.1016/j.jalgebra.2014.08.033
[13] Hardy, G. H.; Wright, E. M., An introduction to the theory of numbers, xvi+426 pp. (1979), The Clarendon Press, Oxford University Press, New York · Zbl 0423.10001
[14] Kantor, William M., Some topics in asymptotic group theory. Groups, combinatorics & geometry, Durham, 1990, London Math. Soc. Lecture Note Ser. 165, 403-421 (1992), Cambridge Univ. Press, Cambridge · Zbl 0830.20033 · doi:10.1017/CBO9780511629259.036
[15] William M.Kantor, Antiflag Transitive Collineation Groups, ArXiv e-prints, June 2018.
[16] Kantor, William M.; Lubotzky, Alexander, The probability of generating a finite classical group, Geom. Dedicata, 36, 1, 67-87 (1990) · Zbl 0718.20011 · doi:10.1007/BF00181465
[17] Larsen, Michael J.; Pink, Richard, Finite subgroups of algebraic groups, J. Amer. Math. Soc., 24, 4, 1105-1158 (2011) · Zbl 1241.20054 · doi:10.1090/S0894-0347-2011-00695-4
[18] Liebeck, Martin W.; Shalev, Aner, The probability of generating a finite simple group, Geom. Dedicata, 56, 1, 103-113 (1995) · Zbl 0836.20068 · doi:10.1007/BF01263616
[19] Liebeck, Martin W.; Shalev, Aner, Simple groups, permutation groups, and probability, J. Amer. Math. Soc., 12, 2, 497-520 (1999) · Zbl 0916.20003 · doi:10.1090/S0894-0347-99-00288-X
[20] Larsen, Michael; Shalev, Aner; Tiep, Pham Huu, The Waring problem for finite simple groups, Ann. of Math. (2), 174, 3, 1885-1950 (2011) · Zbl 1283.20008 · doi:10.4007/annals.2011.174.3.10
[21] Will Sawin, Surjectivity of norm map on subspaces of finite fields, MathOverflow, 2018. https://mathoverflow.net/q/306085 (version: 2018-07-16).
[22] Schmutz, Eric, The order of a typical matrix with entries in a finite field, Israel J. Math., 91, 1-3, 349-371 (1995) · Zbl 0840.15016 · doi:10.1007/BF02761656
[23] Schlage-Puchta, Jan-Christoph, Applications of character estimates to statistical problems for the symmetric group, Combinatorica, 32, 3, 309-323 (2012) · Zbl 1299.05166 · doi:10.1007/s00493-012-2502-9
[24] Stong, Richard, The average order of a matrix, J. Combin. Theory Ser. A, 64, 2, 337-343 (1993) · Zbl 0790.05019 · doi:10.1016/0097-3165(93)90102-E
[25] Suzuki, Michio, Group theory. I, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 247, xiv+434 pp. (1982), Springer-Verlag, Berlin-New York · Zbl 0472.20001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.