Random generation of finite and profinite groups and group enumeration. (English) Zbl 1234.20042

The authors obtain a surprisingly explicit formula for the number of random elements needed to generate a finite \(d\)-generator group with high probability. As a corollary they prove that if \(G\) is a \(d\)-generated linear group of dimension \(n\) then \(cd+\log n\) random generators suffice.
Changing perspective they investigate profinite groups which can be generated by a bounded number of elements with positive probability (PFG groups). In response to a question of Shalev they characterize such groups in terms of certain finite quotients with a transparent structure. Let \(L\) be a finite group with a non-Abelian unique minimal normal subgroup \(M\). A crown-based power \(L(k)\) of \(L\) is defined as the subdirect product subgroup of the direct power \(L^k\) containing \(M^k\) such that \(L(k)/M^k\) is isomorphic to the diagonal subgroup of \((L/M)^k\). The authors give the following semi-structural characterization of groups that are PFG. Let \(G\) be a finitely generated profinite group. Then \(G\) is PFG if and only if for any \(L\) as above if \(L(k)\) is a quotient of \(G\) then \(k\leq l(M)^c\) for some constant \(c\), \(l(M)\) being the minimal degree of a faithful transitive permutation representation of \(M\).
The previous theorem is used by the authors to settle several open problems in the area. For example, it subsumes a conjecture of the reviewer according to which non-PFG groups have quotients which are crown-based powers of unbounded size. They can also answer a question of Lubotzky and Segal proving that finitely generated profinite groups of polynomial index growth are PFG. Moreover this theorem gives an easy proof that all previously known examples of PFG groups are indeed PFG. In fact groups which are not PFG are rather “large”: a finitely generated profinite group \(G\) is PFG if and only if there exists a constant \(c\) such that for any almost simple group \(R\), any open subgroup \(H\) of \(G\) has at most \(l(R)^{c|G:H|}\) quotients isomorphic to \(R\). This immediately implies a positive solution of a well-known open problem of Mann: if \(H\) is an open subgroup in a PFG group, then \(H\) is also a PFG group. The proofs of these results are based on a new approach to counting permutation groups and permutation representations. The main technical result is the following: the number of conjugacy classes of \(d\)-generated primitive subgroups of \(\text{Sym}(n)\) is at most \(n^{cd}\) for some constant \(c\).
As a byproduct of their techniques, the authors obtain that the number of \(r\)-relator groups of order \(n\) is at most \(n^{cr}\) as conjectured by Mann.


20F05 Generators, relations, and presentations of groups
20P05 Probabilistic methods in group theory
20E18 Limits, profinite groups
20B15 Primitive groups
20E07 Subgroup theorems; subgroup growth
20D60 Arithmetic and combinatorial problems involving abstract finite groups
20E26 Residual properties and generalizations; residually finite groups
Full Text: DOI


[1] M. Aschbacher, Finite Group Theory, Cambridge: Cambridge Univ. Press, 1986, vol. 10. · Zbl 0583.20001
[2] M. Aschbacher and L. Scott, ”Maximal subgroups of finite groups,” J. Algebra, vol. 92, iss. 1, pp. 44-80, 1985. · Zbl 0549.20011
[3] L. Babai, ”The probability of generating the symmetric group,” J. Combin. Theory Ser. A, vol. 52, iss. 1, pp. 148-153, 1989. · Zbl 0685.60012
[4] L. Babai, B. Beals, and Á. Seress, ”Polynomial time theory of matrix groups,” in Proc. 41st ACM Symposium on Theory of Computing (STOC ’09), ACM Press, 2009, pp. 55-64. · Zbl 1304.68065
[5] L. Babai, P. J. Cameron, and P. P. Pálfy, ”On the orders of primitive groups with restricted nonabelian composition factors,” J. Algebra, vol. 79, iss. 1, pp. 161-168, 1982. · Zbl 0493.20001
[6] A. Balog, L. Pyber, and A. Mann, ”Polynomial index growth groups,” Internat. J. Algebra Comput., vol. 10, iss. 6, pp. 773-782, 2000. · Zbl 0986.20032
[7] M. Bhattacharjee, ”The probability of generating certain profinite groups by two elements,” Israel J. Math., vol. 86, iss. 1-3, pp. 311-329, 1994. · Zbl 0810.20020
[8] A. V. Borovik, L. Pyber, and A. Shalev, ”Maximal subgroups in finite and profinite groups,” Trans. Amer. Math. Soc., vol. 348, iss. 9, pp. 3745-3761, 1996. · Zbl 0866.20018
[9] F. Celler, C. R. Leedham-Green, S. H. Murray, A. C. Niemeyer, and E. A. O’Brien, ”Generating random elements of a finite group,” Comm. Algebra, vol. 23, iss. 13, pp. 4931-4948, 1995. · Zbl 0836.20094
[10] F. Dalla Volta and A. Lucchini, ”Finite groups that need more generators than any proper quotient,” J. Austral. Math. Soc. Ser. A, vol. 64, iss. 1, pp. 82-91, 1998. · Zbl 0902.20013
[11] E. Detomi and A. Lucchini, ”Crowns and factorization of the probabilistic zeta function of a finite group,” J. Algebra, vol. 265, iss. 2, pp. 651-668, 2003. · Zbl 1072.20031
[12] J. D. Dixon, ”The probability of generating the symmetric group,” Math. Z., vol. 110, pp. 199-205, 1969. · Zbl 0176.29901
[13] J. D. Dixon, M. P. F. du Sautoy, A. Mann, and D. Segal, Analytic pro-\(p\) groups, Second ed., Cambridge: Cambridge Univ. Press, 1999. · Zbl 0934.20001
[14] P. Diaconis and L. Saloff-Coste, ”Walks on generating sets of groups,” Invent. Math., vol. 134, iss. 2, pp. 251-299, 1998. · Zbl 0921.60003
[15] R. K. Fisher, ”The number of non-solvable sections in linear groups,” J. London Math. Soc., vol. 9, pp. 80-86, 1974/75. · Zbl 0298.20038
[16] M. D. Fried and M. Jarden, Field Arithmetic, New York: Springer-Verlag, 1986, vol. 11. · Zbl 0625.12001
[17] M. D. Fried and M. Jarden, Field Arithmetic, Second ed., New York: Springer-Verlag, 2005, vol. 11. · Zbl 1055.12003
[18] R. Guralnick and L. Pyber, Normalizers of primitive permutation groups, in preparation. · Zbl 1414.20002
[19] H. A. Helfgott, ”Growth and generation in \({ SL}_2(\mathbb Z/p\mathbb Z)\),” Ann. of Math., vol. 167, iss. 2, pp. 601-623, 2008. · Zbl 1213.20045
[20] N. S. Hughes, ”The structure and order of the group of central automorphisms of a finite group,” Proc. London Math. Soc., vol. 52, pp. 377-385, 1951. · Zbl 0042.02301
[21] A. Jaikin-Zapirain, Representation growth of pro-\(p\) groups, unpublished. · Zbl 1158.20012
[22] W. M. Kantor and A. Lubotzky, ”The probability of generating a finite classical group,” Geom. Dedicata, vol. 36, iss. 1, pp. 67-87, 1990. · Zbl 0718.20011
[23] P. Kleidman and M. Liebeck, The Subgroup Structure of the Finite Classical Groups, Cambridge: Cambridge Univ. Press, 1990, vol. 129. · Zbl 0697.20004
[24] B. Klopsch, ”Enumerating finite groups without abelian composition factors,” Israel J. Math., vol. 137, pp. 265-284, 2003. · Zbl 1128.20306
[25] M. W. Liebeck and A. Shalev, ”The probability of generating a finite simple group,” Geom. Dedicata, vol. 56, iss. 1, pp. 103-113, 1995. · Zbl 0836.20068
[26] M. W. Liebeck and A. Shalev, ”Simple groups, permutation groups, and probability,” J. Amer. Math. Soc., vol. 12, iss. 2, pp. 497-520, 1999. · Zbl 0916.20003
[27] M. W. Liebeck and A. Shalev, ”Bases of primitive linear groups,” J. Algebra, vol. 252, iss. 1, pp. 95-113, 2002. · Zbl 1034.20001
[28] A. Lubotzky and D. Segal, Subgroup Growth, Basel: Birkhäuser, 2003, vol. 212. · Zbl 1071.20033
[29] A. Lubotzky, ”Subgroup growth and congruence subgroups,” Invent. Math., vol. 119, iss. 2, pp. 267-295, 1995. · Zbl 0848.20036
[30] A. Lubotzky, ”The expected number of random elements to generate a finite group,” J. Algebra, vol. 257, iss. 2, pp. 452-459, 2002. · Zbl 1042.20047
[31] A. Lubotzky, ”Enumerating boundedly generated finite groups,” J. Algebra, vol. 238, iss. 1, pp. 194-199, 2001. · Zbl 1052.20017
[32] A. Lubotzky and B. Martin, ”Polynomial representation growth and the congruence subgroup problem,” Israel J. Math., vol. 144, pp. 293-316, 2004. · Zbl 1134.20056
[33] A. Lubotzky and I. Pak, ”The product replacement algorithm and Kazhdan’s property (T),” J. Amer. Math. Soc., vol. 14, iss. 2, pp. 347-363, 2001. · Zbl 0980.20078
[34] A. Lucchini, ”A 2-generated just-infinite profinite group which is not positively generated,” Israel J. Math., vol. 141, pp. 119-123, 2004. · Zbl 1074.20024
[35] A. Lucchini, F. Menegazzo, and M. Morigi, ”Asymptotic results for primitive permutation groups and irreducible linear groups,” J. Algebra, vol. 223, iss. 1, pp. 154-170, 2000. · Zbl 1063.20501
[36] A. Mann, ”Positively finitely generated groups,” Forum Math., vol. 8, iss. 4, pp. 429-459, 1996. · Zbl 0852.20019
[37] A. Mann, ”Enumerating finite groups and their defining relations. II,” J. Algebra, vol. 302, iss. 2, pp. 586-592, 2006. · Zbl 1116.20017
[38] A. Mann and D. Segal, ”Subgroup growth: some current developments,” in Infinite Groups, Berlin: Walter de Gruyter, 1996, pp. 179-197. · Zbl 0867.20023
[39] A. Mann and A. Shalev, ”Simple groups, maximal subgroups, and probabilistic aspects of profinite groups,” Israel J. Math., vol. 96, iss. , part B, pp. 449-468, 1996. · Zbl 0877.20017
[40] A. McIver and P. M. Neumann, ”Enumerating finite groups,” Quart. J. Math. Oxford Ser., vol. 38, iss. 152, pp. 473-488, 1987. · Zbl 0627.20014
[41] E. Netto, Substitutionentheorie und ihre Anwendungen auf die Algebra, Leipzig: Teubner, 1882. · JFM 14.0090.01
[42] P. M. Neumann, ”An enumeration theorem for finite groups,” Quart. J. Math. Oxford Ser., vol. 20, pp. 395-401, 1969. · Zbl 0204.34701
[43] N. Nikolov, ”On subgroups of finite index in positively finitely generated groups,” Bull. London Math. Soc., vol. 37, iss. 6, pp. 873-877, 2005. · Zbl 1097.20028
[44] N. Nikolov and D. Segal, ”On finitely generated profinite groups. I. Strong completeness and uniform bounds,” Ann. of Math., vol. 165, iss. 1, pp. 171-238, 2007. · Zbl 1126.20018
[45] I. Pak, On probability of generating a finite group, preprint, 2009.
[46] I. Pak, ”What do we know about the product replacement algorithm?,” in Groups and Computation, III, Berlin: Walter de Gruyter, 2001, vol. 8, pp. 301-347. · Zbl 0986.68172
[47] C. E. Praeger and J. Saxl, ”On the orders of primitive permutation groups,” Bull. London Math. Soc., vol. 12, iss. 4, pp. 303-307, 1980. · Zbl 0443.20001
[48] L. Pyber, ”Enumerating finite groups of given order,” Ann. of Math., vol. 137, iss. 1, pp. 203-220, 1993. · Zbl 0778.20012
[49] L. Pyber and A. Shalev, ”Groups with super-exponential subgroup growth,” Combinatorica, vol. 16, iss. 4, pp. 527-533, 1996. · Zbl 0880.20019
[50] L. Pyber and A. Shalev, ”Asymptotic results for primitive permutation groups,” J. Algebra, vol. 188, iss. 1, pp. 103-124, 1997. · Zbl 0877.20004
[51] L. Pyber and A. Shalev, ”Residual properties of groups and probabilistic methods,” C. R. Acad. Sci. Paris Sér. I Math., vol. 333, iss. 4, pp. 275-278, 2001. · Zbl 0991.20026
[52] M. Quick, ”Probabilistic generation of wreath products of non-abelian finite simple groups. II,” Internat. J. Algebra Comput., vol. 16, iss. 3, pp. 493-503, 2006. · Zbl 1103.20066
[53] J. S. Rose, ”Automorphism groups of groups with trivial centre,” Proc. London Math. Soc., vol. 31, iss. 2, pp. 167-193, 1975. · Zbl 0315.20021
[54] A. Shalev, ”Simple groups, permutation groups, and probability,” in Proc. Int. Congr. Math., Vol. II, 1998, pp. 129-137. · Zbl 0898.20005
[55] A. Shalev, ”Asymptotic group theory,” Notices Amer. Math. Soc., vol. 48, iss. 4, pp. 383-389, 2001. · Zbl 1048.20027
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.