Random generation of finite and profinite groups and group enumeration

Abstract

We 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 we prove that if $G$ is a $d$-generated linear group of dimension $n$ then $cd+\log n$ random generators suffice.

Changing perspective we investigate profinite groups $F$ which can be generated by a bounded number of elements with positive probability. In response to a question of Shalev we characterize such groups in terms of certain finite quotients with a transparent structure. As a consequence we settle several problems of Lucchini, Lubotzky, Mann and Segal.

As a byproduct of our techniques we obtain that the number of $r$-relator groups of order $n$ is at most $n^{cr}$ as conjectured by Mann.

  • [Asc] M. Aschbacher, Finite Group Theory, Cambridge: Cambridge Univ. Press, 1986, vol. 10.
    @book {Asc, MRKEY = {0895134},
      AUTHOR = {Aschbacher, Michael},
      TITLE = {Finite Group Theory},
      SERIES = {Cambridge Studies Adv. Math.},
      VOLUME = {10},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1986},
      PAGES = {x+274},
      ISBN = {0-521-30341-9},
      MRCLASS = {20-01 (20B05 20C05 20D05)},
      MRNUMBER = {0895134},
      MRREVIEWER = {Stephen D. Smith},
      ZBLNUMBER = {0583.20001},
      }
  • [AS] Go to document M. Aschbacher and L. Scott, "Maximal subgroups of finite groups," J. Algebra, vol. 92, iss. 1, pp. 44-80, 1985.
    @article {AS, MRKEY = {0772471},
      AUTHOR = {Aschbacher, Michael and Scott, L.},
      TITLE = {Maximal subgroups of finite groups},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {92},
      YEAR = {1985},
      NUMBER = {1},
      PAGES = {44--80},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20D25},
      MRNUMBER = {0772471},
      MRREVIEWER = {Koichiro Harada},
      DOI = {10.1016/0021-8693(85)90145-0},
      ZBLNUMBER = {0549.20011},
      }
  • [Ba] Go to document L. Babai, "The probability of generating the symmetric group," J. Combin. Theory Ser. A, vol. 52, iss. 1, pp. 148-153, 1989.
    @article {Ba, MRKEY = {1008166},
      AUTHOR = {Babai, L{á}szl{ó}},
      TITLE = {The probability of generating the symmetric group},
      JOURNAL = {J. Combin. Theory Ser. A},
      FJOURNAL = {Journal of Combinatorial Theory. Series A},
      VOLUME = {52},
      YEAR = {1989},
      NUMBER = {1},
      PAGES = {148--153},
      ISSN = {0097-3165},
      CODEN = {JCBTA7},
      MRCLASS = {20B35 (11N45 20P05)},
      MRNUMBER = {1008166},
      MRREVIEWER = {Michael Szalay},
      DOI = {10.1016/0097-3165(89)90068-X},
      ZBLNUMBER = {0685.60012},
      }
  • [BBS] Go to document 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.
    @incollection{BBS,
      author= {Babai, L{á}szl{ó} and Beals, B. and Seress, {\'{A}}},
      TITLE={Polynomial time theory of matrix groups},
      BOOKTITLE={Proc. 41st {\rm ACM} Symposium on Theory of Computing {\rm (STOC '09)}},
      YEAR={2009},
      PUBLISHER={ACM Press},
      PAGES={55--64},
      DOI= {10.1145/1536414.1536425},
      }
  • [BCP] Go to document 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.
    @article {BCP, MRKEY = {0679977},
      AUTHOR = {Babai, L{á}szl{ó} and Cameron, P. J. and P{á}lfy, P. P.},
      TITLE = {On the orders of primitive groups with restricted nonabelian composition factors},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {79},
      YEAR = {1982},
      NUMBER = {1},
      PAGES = {161--168},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20B05 (05C25 05C99 68E10)},
      MRNUMBER = {0679977},
      MRREVIEWER = {Cheryl E. Praeger},
      DOI = {10.1016/0021-8693(82)90323-4},
      ZBLNUMBER = {0493.20001},
      }
  • [BMP] Go to document A. Balog, L. Pyber, and A. Mann, "Polynomial index growth groups," Internat. J. Algebra Comput., vol. 10, iss. 6, pp. 773-782, 2000.
    @article {BMP, MRKEY = {1809384},
      AUTHOR = {Balog, Antal and Pyber, L{á}szl{ó} and Mann, Avinoam},
      TITLE = {Polynomial index growth groups},
      JOURNAL = {Internat. J. Algebra Comput.},
      FJOURNAL = {International Journal of Algebra and Computation},
      VOLUME = {10},
      YEAR = {2000},
      NUMBER = {6},
      PAGES = {773--782},
      ISSN = {0218-1967},
      MRCLASS = {20E07 (20E18)},
      MRNUMBER = {1809384},
      MRREVIEWER = {Daniel Segal},
      DOI = {10.1142/S0218196700000364},
      ZBLNUMBER = {0986.20032},
      }
  • [Bh] Go to document M. Bhattacharjee, "The probability of generating certain profinite groups by two elements," Israel J. Math., vol. 86, iss. 1-3, pp. 311-329, 1994.
    @article {Bh, MRKEY = {1276141},
      AUTHOR = {Bhattacharjee, Meenaxi},
      TITLE = {The probability of generating certain profinite groups by two elements},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {86},
      YEAR = {1994},
      NUMBER = {1-3},
      PAGES = {311--329},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {20E18 (20E28 20P05)},
      MRNUMBER = {1276141},
      MRREVIEWER = {Thomas Weigel},
      DOI = {10.1007/BF02773684},
      ZBLNUMBER = {0810.20020},
      }
  • [BPS] Go to document 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.
    @article {BPS, MRKEY = {1360222},
      AUTHOR = {Borovik, Alexandre V. and Pyber, Laszlo and Shalev, Aner},
      TITLE = {Maximal subgroups in finite and profinite groups},
      JOURNAL = {Trans. Amer. Math. Soc.},
      FJOURNAL = {Transactions of the American Mathematical Society},
      VOLUME = {348},
      YEAR = {1996},
      NUMBER = {9},
      PAGES = {3745--3761},
      ISSN = {0002-9947},
      CODEN = {TAMTAM},
      MRCLASS = {20E18 (20B30)},
      MRNUMBER = {1360222},
      MRREVIEWER = {L. Ribes},
      DOI = {10.1090/S0002-9947-96-01665-0},
      ZBLNUMBER = {0866.20018},
      }
  • [CLMNO] Go to document 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.
    @article {CLMNO, MRKEY = {1356111},
      AUTHOR = {Celler, Frank and Leedham-Green, Charles R. and Murray, Scott H. and Niemeyer, Alice C. and O'Brien, E. A.},
      TITLE = {Generating random elements of a finite group},
      JOURNAL = {Comm. Algebra},
      FJOURNAL = {Communications in Algebra},
      VOLUME = {23},
      YEAR = {1995},
      NUMBER = {13},
      PAGES = {4931--4948},
      ISSN = {0092-7872},
      CODEN = {COALDM},
      MRCLASS = {20P05 (20D99 68Q20)},
      MRNUMBER = {1356111},
      MRREVIEWER = {P. P. P{á}lfy},
      DOI = {10.1080/00927879508825509},
      ZBLNUMBER = {0836.20094},
      }
  • [DVL] Go to document 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.
    @article {DVL, MRKEY = {1490148},
      AUTHOR = {Dalla Volta, Francesca and Lucchini, Andrea},
      TITLE = {Finite groups that need more generators than any proper quotient},
      JOURNAL = {J. Austral. Math. Soc. Ser. A},
      FJOURNAL = {Australian Mathematical Society. Journal. Series A. Pure Mathematics and Statistics},
      VOLUME = {64},
      YEAR = {1998},
      NUMBER = {1},
      PAGES = {82--91},
      ISSN = {0263-6115},
      CODEN = {JAMADS},
      MRCLASS = {20F05 (20D99)},
      MRNUMBER = {1490148},
      MRREVIEWER = {Alberto Delgado},
      ZBLNUMBER = {0902.20013},
      DOI = {10.1017/S1446788700001312},
      }
  • [DL] Go to document 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.
    @article {DL, MRKEY = {1987022},
      AUTHOR = {Detomi, E. and Lucchini, A.},
      TITLE = {Crowns and factorization of the probabilistic zeta function of a finite group},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {265},
      YEAR = {2003},
      NUMBER = {2},
      PAGES = {651--668},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20P05},
      MRNUMBER = {1987022},
      MRREVIEWER = {Nikolay V. Nikolov},
      DOI = {10.1016/S0021-8693(03)00275-8},
      ZBLNUMBER = {1072.20031},
      }
  • [Di] Go to document J. D. Dixon, "The probability of generating the symmetric group," Math. Z., vol. 110, pp. 199-205, 1969.
    @article {Di, MRKEY = {0251758},
      AUTHOR = {Dixon, John D.},
      TITLE = {The probability of generating the symmetric group},
      JOURNAL = {Math. Z.},
      FJOURNAL = {Mathematische Zeitschrift},
      VOLUME = {110},
      YEAR = {1969},
      PAGES = {199--205},
      ISSN = {0025-5874},
      MRCLASS = {60.10 (20.00)},
      MRNUMBER = {0251758},
      MRREVIEWER = {R. A. Gangolli},
      DOI = {10.1007/BF01110210},
      ZBLNUMBER = {0176.29901},
      }
  • [DDMS] Go to document J. D. Dixon, M. P. F. du Sautoy, A. Mann, and D. Segal, Analytic pro-$p$ groups, Second ed., Cambridge: Cambridge Univ. Press, 1999.
    @book {DDMS, MRKEY = {1720368},
      AUTHOR = {Dixon, J. D. and du Sautoy, M. P. F. and Mann, A. and Segal, D.},
      TITLE = {Analytic pro-{$p$} groups},
      SERIES = {Cambridge Studies Adv. Math.},
      NUMBER = {61},
      EDITION = {Second},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1999},
      PAGES = {xviii+368},
      ISBN = {0-521-65011-9},
      MRCLASS = {20E18 (20G30)},
      MRNUMBER = {1720368},
      MRREVIEWER = {Alexander Lubotzky},
      DOI = {10.1017/CBO9780511470882},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {0934.20001},
      ZBLNUMBER = {0744.20002},
      }
  • [DS] Go to document P. Diaconis and L. Saloff-Coste, "Walks on generating sets of groups," Invent. Math., vol. 134, iss. 2, pp. 251-299, 1998.
    @article {DS, MRKEY = {1650316},
      AUTHOR = {Diaconis, P. and Saloff-Coste, L.},
      TITLE = {Walks on generating sets of groups},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {134},
      YEAR = {1998},
      NUMBER = {2},
      PAGES = {251--299},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {60B15 (60C05 60J10)},
      MRNUMBER = {1650316},
      DOI = {10.1007/s002220050265},
      ZBLNUMBER = {0921.60003},
      }
  • [Fi] Go to document R. K. Fisher, "The number of non-solvable sections in linear groups," J. London Math. Soc., vol. 9, pp. 80-86, 1974/75.
    @article {Fi, MRKEY = {0360853},
      AUTHOR = {Fisher, R. K.},
      TITLE = {The number of non-solvable sections in linear groups},
      JOURNAL = {J. London Math. Soc.},
      FJOURNAL = {Journal of the London Mathematical Society. Second Series},
      VOLUME = {9},
      YEAR = {1974/75},
      PAGES = {80--86},
      ISSN = {0024-6107},
      MRCLASS = {20G15},
      MRNUMBER = {0360853},
      MRREVIEWER = {B. A. F. Wehrfritz},
      DOI = {10.1112/jlms/s2-9.1.80},
      ZBLCOMMENT = {BIBPROC: YEAR doesn't match found ZBLNUMBER},
      ZBLNUMBER = {0298.20038},
      }
  • [FJ] M. D. Fried and M. Jarden, Field Arithmetic, New York: Springer-Verlag, 1986, vol. 11.
    @book {FJ, MRKEY = {0868860},
      AUTHOR = {Fried, Michael D. and Jarden, Moshe},
      TITLE = {Field Arithmetic},
      SERIES = {Ergeb. Math. Grenzgeb.},
      VOLUME= {11},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {1986},
      PAGES = {xviii+458},
      ISBN = {3-540-16640-8},
      MRCLASS = {12Lxx (03B25 03C10 03C60 03H05)},
      MRNUMBER = {0868860},
      MRREVIEWER = {R. Weissauer},
      ZBLNUMBER = {0625.12001},
      }
  • [FJ2] M. D. Fried and M. Jarden, Field Arithmetic, Second ed., New York: Springer-Verlag, 2005, vol. 11.
    @book {FJ2, MRKEY = {2102046},
      AUTHOR = {Fried, Michael D. and Jarden, Moshe},
      TITLE = {Field Arithmetic},
      SERIES = {Ergeb. Math. Grenzgeb.},
      VOLUME = {11},
      EDITION = {{S}econd},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2005},
      PAGES = {xxiv+780},
      ISBN = {3-540-22811-X},
      MRCLASS = {12E30 (03B25 03C10 03C60 03H05)},
      MRNUMBER = {2102046},
      MRREVIEWER = {Ido Efrat},
      ZBLNUMBER = {1055.12003},
      }
  • [GuPy] R. Guralnick and L. Pyber, Normalizers of primitive permutation groups, in preparation.
    @misc{GuPy,
      author={Guralnick, R. and Pyber, L.},
      TITLE={Normalizers of primitive permutation groups, in preparation},
      }
  • [Hel] Go to document H. A. Helfgott, "Growth and generation in ${ SL}_2(\Bbb Z/p\Bbb Z)$," Ann. of Math., vol. 167, iss. 2, pp. 601-623, 2008.
    @article {Hel, MRKEY = {2415382},
      AUTHOR = {Helfgott, H. A.},
      TITLE = {Growth and generation in {${\rm SL}\sb 2(\Bbb Z/p\Bbb Z)$}},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {167},
      YEAR = {2008},
      NUMBER = {2},
      PAGES = {601--623},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {20G40 (05C25 20F69)},
      MRNUMBER = {2415382},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.4007/annals.2008.167.601},
      ZBL = {pre05578700},
      }
  • [Hu] Go to document 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.
    @article {Hu, MRKEY = {0041129},
      AUTHOR = {Hughes, NJ S.},
      TITLE = {The structure and order of the group of central automorphisms of a finite group},
      JOURNAL = {Proc. London Math. Soc.},
      FJOURNAL = {Proceedings of the London Mathematical Society. Second Series},
      VOLUME = {52},
      YEAR = {1951},
      PAGES = {377--385},
      ISSN = {0024-6115},
      MRCLASS = {20.0X},
      MRNUMBER = {0041129},
      MRREVIEWER = {D. C. Murdoch},
      DOI = {10.1112/plms/s2-52.5.377},
      ZBLNUMBER = {0042.02301},
      }
  • [Ja] A. Jaikin-Zapirain, Representation growth of pro-$p$ groups, unpublished.
    @misc{Ja,
      author={Jaikin-Zapirain, A.},
      TITLE={Representation growth of pro-$p$ groups, unpublished},
      }
  • [KaLu] Go to document W. M. Kantor and A. Lubotzky, "The probability of generating a finite classical group," Geom. Dedicata, vol. 36, iss. 1, pp. 67-87, 1990.
    @article {KaLu, MRKEY = {1065213},
      AUTHOR = {Kantor, William M. and Lubotzky, Alexander},
      TITLE = {The probability of generating a finite classical group},
      JOURNAL = {Geom. Dedicata},
      FJOURNAL = {Geometriae Dedicata},
      VOLUME = {36},
      YEAR = {1990},
      NUMBER = {1},
      PAGES = {67--87},
      ISSN = {0046-5755},
      CODEN = {GEMDAT},
      MRCLASS = {20D06 (20E18 20P05)},
      MRNUMBER = {1065213},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.1007/BF00181465},
      ZBLNUMBER = {0718.20011},
      }
  • [KL] Go to document P. Kleidman and M. Liebeck, The Subgroup Structure of the Finite Classical Groups, Cambridge: Cambridge Univ. Press, 1990, vol. 129.
    @book {KL, MRKEY = {1057341},
      AUTHOR = {Kleidman, Peter and Liebeck, Martin},
      TITLE = {The Subgroup Structure of the Finite Classical Groups},
      SERIES = {London Math. Soc. Lect. Note Series},
      VOLUME = {129},
      PUBLISHER = {Cambridge Univ. Press},
      ADDRESS = {Cambridge},
      YEAR = {1990},
      PAGES = {x+303},
      ISBN = {0-521-35949-X},
      MRCLASS = {20-02 (20D06 20G40)},
      MRNUMBER = {1057341},
      MRREVIEWER = {R. W. Carter},
      DOI = {10.1017/CBO9780511629235},
      ZBLNUMBER = {0697.20004},
      }
  • [Klop] Go to document B. Klopsch, "Enumerating finite groups without abelian composition factors," Israel J. Math., vol. 137, pp. 265-284, 2003.
    @article {Klop, MRKEY = {2013359},
      AUTHOR = {Klopsch, Benjamin},
      TITLE = {Enumerating finite groups without abelian composition factors},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {137},
      YEAR = {2003},
      PAGES = {265--284},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {20D30},
      MRNUMBER = {2013359},
      MRREVIEWER = {Federico Menegazzo},
      DOI = {10.1007/BF02785965},
      ZBLNUMBER = {1128.20306},
      }
  • [LiSh2] Go to document M. W. Liebeck and A. Shalev, "The probability of generating a finite simple group," Geom. Dedicata, vol. 56, iss. 1, pp. 103-113, 1995.
    @article {LiSh2, MRKEY = {1338320},
      AUTHOR = {Liebeck, Martin W. and Shalev, Aner},
      TITLE = {The probability of generating a finite simple group},
      JOURNAL = {Geom. Dedicata},
      FJOURNAL = {Geometriae Dedicata},
      VOLUME = {56},
      YEAR = {1995},
      NUMBER = {1},
      PAGES = {103--113},
      ISSN = {0046-5755},
      CODEN = {GEMDAT},
      MRCLASS = {20P05 (20D06 20E18 20G40)},
      MRNUMBER = {1338320},
      MRREVIEWER = {Michael Szalay},
      DOI = {10.1007/BF01263616},
      ZBLNUMBER = {0836.20068},
      }
  • [LiSh3] Go to document M. W. Liebeck and A. Shalev, "Simple groups, permutation groups, and probability," J. Amer. Math. Soc., vol. 12, iss. 2, pp. 497-520, 1999.
    @article {LiSh3, MRKEY = {1639620},
      AUTHOR = {Liebeck, Martin W. and Shalev, Aner},
      TITLE = {Simple groups, permutation groups, and probability},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {12},
      YEAR = {1999},
      NUMBER = {2},
      PAGES = {497--520},
      ISSN = {0894-0347},
      MRCLASS = {20B15 (14H30 20D06 20G40 20P05)},
      MRNUMBER = {1639620},
      MRREVIEWER = {Robert M. Guralnick},
      DOI = {10.1090/S0894-0347-99-00288-X},
      ZBLNUMBER = {0916.20003},
      }
  • [LiSh] Go to document M. W. Liebeck and A. Shalev, "Bases of primitive linear groups," J. Algebra, vol. 252, iss. 1, pp. 95-113, 2002.
    @article {LiSh, MRKEY = {1922387},
      AUTHOR = {Liebeck, Martin W. and Shalev, Aner},
      TITLE = {Bases of primitive linear groups},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {252},
      YEAR = {2002},
      NUMBER = {1},
      PAGES = {95--113},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20B15},
      MRNUMBER = {1922387},
      MRREVIEWER = {David Gluck},
      DOI = {10.1016/S0021-8693(02)00001-7},
      ZBLNUMBER = {1034.20001},
      }
  • [LuSe] A. Lubotzky and D. Segal, Subgroup Growth, Basel: Birkhäuser, 2003, vol. 212.
    @book {LuSe, MRKEY = {1978431},
      AUTHOR = {Lubotzky, Alexander and Segal, Dan},
      TITLE = {Subgroup Growth},
      SERIES = {Progr. Math.},
      VOLUME= {212},
      PUBLISHER = {Birkhäuser},
      ADDRESS = {Basel},
      YEAR = {2003},
      PAGES = {xxii+453},
      ISBN = {3-7643-6989-2},
      MRCLASS = {20E07 (20E18 20E26 20F69)},
      MRNUMBER = {1978431},
      MRREVIEWER = {Avinoam Mann},
      ZBLNUMBER = {1071.20033},
      }
  • [Lu3] Go to document A. Lubotzky, "Subgroup growth and congruence subgroups," Invent. Math., vol. 119, iss. 2, pp. 267-295, 1995.
    @article {Lu3, MRKEY = {1312501},
      AUTHOR = {Lubotzky, Alexander},
      TITLE = {Subgroup growth and congruence subgroups},
      JOURNAL = {Invent. Math.},
      FJOURNAL = {Inventiones Mathematicae},
      VOLUME = {119},
      YEAR = {1995},
      NUMBER = {2},
      PAGES = {267--295},
      ISSN = {0020-9910},
      CODEN = {INVMBH},
      MRCLASS = {20H05 (20G30)},
      MRNUMBER = {1312501},
      MRREVIEWER = {H. Bass},
      DOI = {10.1007/BF01245183},
      ZBLNUMBER = {0848.20036},
      }
  • [Lu1] Go to document A. Lubotzky, "The expected number of random elements to generate a finite group," J. Algebra, vol. 257, iss. 2, pp. 452-459, 2002.
    @article {Lu1, MRKEY = {1947971},
      AUTHOR = {Lubotzky, Alexander},
      TITLE = {The expected number of random elements to generate a finite group},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {257},
      YEAR = {2002},
      NUMBER = {2},
      PAGES = {452--459},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20P05 (20D99 20F05)},
      MRNUMBER = {1947971},
      MRREVIEWER = {Fiorenza Morini},
      DOI = {10.1016/S0021-8693(02)00528-8},
      ZBLNUMBER = {1042.20047},
      }
  • [Lu2] Go to document A. Lubotzky, "Enumerating boundedly generated finite groups," J. Algebra, vol. 238, iss. 1, pp. 194-199, 2001.
    @article {Lu2, MRKEY = {1822189},
      AUTHOR = {Lubotzky, Alexander},
      TITLE = {Enumerating boundedly generated finite groups},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {238},
      YEAR = {2001},
      NUMBER = {1},
      PAGES = {194--199},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20D60},
      MRNUMBER = {1822189},
      MRREVIEWER = {L{á}szl{ó} Pyber},
      DOI = {10.1006/jabr.2000.8650},
      ZBLNUMBER = {1052.20017},
      }
  • [LuMa] Go to document A. Lubotzky and B. Martin, "Polynomial representation growth and the congruence subgroup problem," Israel J. Math., vol. 144, pp. 293-316, 2004.
    @article {LuMa, MRKEY = {2121543},
      AUTHOR = {Lubotzky, Alexander and Martin, Benjamin},
      TITLE = {Polynomial representation growth and the congruence subgroup problem},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {144},
      YEAR = {2004},
      PAGES = {293--316},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {20G05 (20G35 20H05)},
      MRNUMBER = {2121543},
      MRREVIEWER = {Jasbir Singh Chahal},
      DOI = {10.1007/BF02916715},
      ZBLNUMBER = {1134.20056},
      }
  • [LP] Go to document 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.
    @article {LP, MRKEY = {1815215},
      AUTHOR = {Lubotzky, Alexander and Pak, Igor},
      TITLE = {The product replacement algorithm and {K}azhdan's property ({T})},
      JOURNAL = {J. Amer. Math. Soc.},
      FJOURNAL = {Journal of the American Mathematical Society},
      VOLUME = {14},
      YEAR = {2001},
      NUMBER = {2},
      PAGES = {347--363},
      ISSN = {0894-0347},
      MRCLASS = {60B15 (05C25 22D10 60J10)},
      MRNUMBER = {1815215},
      MRREVIEWER = {Piotr Graczyk},
      DOI = {10.1090/S0894-0347-00-00356-8},
      ZBLNUMBER = {0980.20078},
      }
  • [Luc] Go to document A. Lucchini, "A 2-generated just-infinite profinite group which is not positively generated," Israel J. Math., vol. 141, pp. 119-123, 2004.
    @article {Luc, MRKEY = {2063028},
      AUTHOR = {Lucchini, Andrea},
      TITLE = {A 2-generated just-infinite profinite group which is not positively generated},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {141},
      YEAR = {2004},
      PAGES = {119--123},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {20E18 (20B05 20P05)},
      MRNUMBER = {2063028},
      MRREVIEWER = {Benjamin Klopsch},
      DOI = {10.1007/BF02772214},
      ZBLNUMBER = {1074.20024},
      }
  • [LMM] Go to document 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.
    @article {LMM, MRKEY = {1738257},
      AUTHOR = {Lucchini, Andrea and Menegazzo, F. and Morigi, M.},
      TITLE = {Asymptotic results for primitive permutation groups and irreducible linear groups},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {223},
      YEAR = {2000},
      NUMBER = {1},
      PAGES = {154--170},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20B15 (20G40)},
      MRNUMBER = {1738257},
      MRREVIEWER = {Ulrich Dempwolff},
      DOI = {10.1006/jabr.1999.8081},
      ZBLNUMBER = {1063.20501},
      }
  • [Mn1] Go to document A. Mann, "Positively finitely generated groups," Forum Math., vol. 8, iss. 4, pp. 429-459, 1996.
    @article {Mn1, MRKEY = {1393323},
      AUTHOR = {Mann, Avinoam},
      TITLE = {Positively finitely generated groups},
      JOURNAL = {Forum Math.},
      FJOURNAL = {Forum Mathematicum},
      VOLUME = {8},
      YEAR = {1996},
      NUMBER = {4},
      PAGES = {429--459},
      ISSN = {0933-7741},
      CODEN = {FOMAEF},
      MRCLASS = {20E18},
      MRNUMBER = {1393323},
      MRREVIEWER = {Daniel Segal},
      DOI = {10.1515/form.1996.8.429},
      ZBLNUMBER = {0852.20019},
      }
  • [Mann] Go to document A. Mann, "Enumerating finite groups and their defining relations. II," J. Algebra, vol. 302, iss. 2, pp. 586-592, 2006.
    @article {Mann, MRKEY = {2293772},
      AUTHOR = {Mann, Avinoam},
      TITLE = {Enumerating finite groups and their defining relations. {II}},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {302},
      YEAR = {2006},
      NUMBER = {2},
      PAGES = {586--592},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20D60 (05A16 20P05)},
      MRNUMBER = {2293772},
      MRREVIEWER = {L{á}szl{ó} Pyber},
      DOI = {10.1016/j.jalgebra.2004.02.003},
      ZBLNUMBER = {1116.20017},
      }
  • [MSe] A. Mann and D. Segal, "Subgroup growth: some current developments," in Infinite Groups, Berlin: Walter de Gruyter, 1996, pp. 179-197.
    @incollection {MSe, MRKEY = {1477175},
      AUTHOR = {Mann, Avinoam and Segal, Dan},
      TITLE = {Subgroup growth: some current developments},
      BOOKTITLE = {Infinite Groups},
      VENUE={{R}avello, 1994 },
      PAGES = {179--197},
      PUBLISHER = {Walter de Gruyter},
      ADDRESS = {Berlin},
      YEAR = {1996},
      MRCLASS = {20E26},
      MRNUMBER = {1477175},
      MRREVIEWER = {Marcus du Sautoy},
      ZBLNUMBER = {0867.20023},
      }
  • [MS] Go to document 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.
    @article {MS, MRKEY = {1433701},
      AUTHOR = {Mann, Avinoam and Shalev, Aner},
      TITLE = {Simple groups, maximal subgroups, and probabilistic aspects of profinite groups},
      JOURNAL = {Israel J. Math.},
      FJOURNAL = {Israel Journal of Mathematics},
      VOLUME = {96},
      YEAR = {1996},
      NUMBER = {, part B},
      PAGES = {449--468},
      ISSN = {0021-2172},
      CODEN = {ISJMAP},
      MRCLASS = {20E18 (20E28)},
      MRNUMBER = {1433701},
      MRREVIEWER = {Martin W. Liebeck},
      DOI = {10.1007/BF02785528},
      ZBLNUMBER = {0877.20017},
      }
  • [MN] A. McIver and P. M. Neumann, "Enumerating finite groups," Quart. J. Math. Oxford Ser., vol. 38, iss. 152, pp. 473-488, 1987.
    @article {MN, MRKEY = {0916229},
      AUTHOR = {McIver, Annabelle and Neumann, Peter M.},
      TITLE = {Enumerating finite groups},
      JOURNAL = {Quart. J. Math. Oxford Ser.},
      FJOURNAL = {The Quarterly Journal of Mathematics. Oxford. Second Series},
      VOLUME = {38},
      YEAR = {1987},
      NUMBER = {152},
      PAGES = {473--488},
      ISSN = {0033-5606},
      CODEN = {QJMAAT},
      MRCLASS = {11N45 (11N56 20D60)},
      MRNUMBER = {0916229},
      MRREVIEWER = {M. Ram Murty},
      ZBLNUMBER = {0627.20014},
      }
  • [Net] E. Netto, Substitutionentheorie und ihre Anwendungen auf die Algebra, Leipzig: Teubner, 1882.
    @book{Net,
      author={Netto, E.},
      TITLE={Substitutionentheorie und ihre {A}nwendungen auf die {A}lgebra},
      YEAR={1882},
      PUBLISHER={Teubner},
      ADDRESS={Leipzig},
      NOTE={English transl. 1892, second edition, {C}helsea, {N}ew {Y}ork, 1964},
      JFMNUMBER = {14.0090.01},
      MRNUMBER = {0175908},
      }
  • [Ne] P. M. Neumann, "An enumeration theorem for finite groups," Quart. J. Math. Oxford Ser., vol. 20, pp. 395-401, 1969.
    @article {Ne, MRKEY = {0254134},
      AUTHOR = {Neumann, Peter M.},
      TITLE = {An enumeration theorem for finite groups},
      JOURNAL = {Quart. J. Math. Oxford Ser.},
      FJOURNAL = {The Quarterly Journal of Mathematics. Oxford. Second Series},
      VOLUME = {20},
      YEAR = {1969},
      PAGES = {395--401},
      ISSN = {0033-5606},
      MRCLASS = {20.25},
      MRNUMBER = {0254134},
      MRREVIEWER = {M. E. Harris},
      ZBLNUMBER = {0204.34701},
      }
  • [Nik] Go to document N. Nikolov, "On subgroups of finite index in positively finitely generated groups," Bull. London Math. Soc., vol. 37, iss. 6, pp. 873-877, 2005.
    @article {Nik, MRKEY = {2186720},
      AUTHOR = {Nikolov, Nikolay},
      TITLE = {On subgroups of finite index in positively finitely generated groups},
      JOURNAL = {Bull. London Math. Soc.},
      FJOURNAL = {The Bulletin of the London Mathematical Society},
      VOLUME = {37},
      YEAR = {2005},
      NUMBER = {6},
      PAGES = {873--877},
      ISSN = {0024-6093},
      CODEN = {LMSBBT},
      MRCLASS = {20E07 (20E18)},
      MRNUMBER = {2186720},
      MRREVIEWER = {Marius T{\u{a}}rn{\u{a}}uceanu},
      DOI = {10.1112/S0024609305004947},
      ZBLNUMBER = {1097.20028},
      }
  • [NS] Go to document 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.
    @article {NS, MRKEY = {2276769},
      AUTHOR = {Nikolov, Nikolay and Segal, Dan},
      TITLE = {On finitely generated profinite groups. {I}. {S}trong completeness and uniform bounds},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {165},
      YEAR = {2007},
      NUMBER = {1},
      PAGES = {171--238},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {20E18 (20E32 20F12)},
      MRNUMBER = {2276769},
      MRREVIEWER = {Benjamin Klopsch},
      DOI = {10.4007/annals.2007.165.171},
      ZBLNUMBER = {1126.20018},
      }
  • [Pa] I. Pak, On probability of generating a finite group, preprint, 2009.
    @misc{Pa,
      author={Pak, I.},
      TITLE={On probability of generating a finite group, preprint},
      YEAR={2009},
      }
  • [Pa1] 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.
    @incollection {Pa1, MRKEY = {1829489},
      AUTHOR = {Pak, Igor},
      TITLE = {What do we know about the product replacement algorithm?},
      BOOKTITLE = {Groups and Computation, {\rm III}},
      VENUE={{C}olumbus, {OH},
      1999},
      SERIES = {Ohio State Univ. Math. Res. Inst. Publ.},
      VOLUME= {8},
      PAGES = {301--347},
      PUBLISHER = {Walter de Gruyter},
      ADDRESS = {Berlin},
      YEAR = {2001},
      MRCLASS = {20P05 (20F69 68W30)},
      MRNUMBER = {1829489},
      MRREVIEWER = {Tatiana Smirnova-Nagnibeda},
      ZBLNUMBER = {0986.68172},
      }
  • [PrS] Go to document 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.
    @article {PrS, MRKEY = {0576980},
      AUTHOR = {Praeger, Cheryl E. and Saxl, Jan},
      TITLE = {On the orders of primitive permutation groups},
      JOURNAL = {Bull. London Math. Soc.},
      FJOURNAL = {The Bulletin of the London Mathematical Society},
      VOLUME = {12},
      YEAR = {1980},
      NUMBER = {4},
      PAGES = {303--307},
      ISSN = {0024-6093},
      CODEN = {LMSBBT},
      MRCLASS = {20B20},
      MRNUMBER = {0576980},
      MRREVIEWER = {Peter Rowlinson},
      DOI = {10.1112/blms/12.4.303},
      ZBLNUMBER = {0443.20001},
      }
  • [Py] Go to document L. Pyber, "Enumerating finite groups of given order," Ann. of Math., vol. 137, iss. 1, pp. 203-220, 1993.
    @article {Py, MRKEY = {1200081},
      AUTHOR = {Pyber, L.},
      TITLE = {Enumerating finite groups of given order},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {137},
      YEAR = {1993},
      NUMBER = {1},
      PAGES = {203--220},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {11N45 (20D60)},
      MRNUMBER = {1200081},
      MRREVIEWER = {Robert M. Guralnick},
      DOI = {10.2307/2946623},
      ZBLNUMBER = {0778.20012},
      }
  • [PS96] Go to document L. Pyber and A. Shalev, "Groups with super-exponential subgroup growth," Combinatorica, vol. 16, iss. 4, pp. 527-533, 1996.
    @article {PS96, MRKEY = {1433640},
      AUTHOR = {Pyber, L. and Shalev, A.},
      TITLE = {Groups with super-exponential subgroup growth},
      JOURNAL = {Combinatorica},
      FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      VOLUME = {16},
      YEAR = {1996},
      NUMBER = {4},
      PAGES = {527--533},
      ISSN = {0209-9683},
      CODEN = {COMBDI},
      MRCLASS = {20E26 (20B35 20E18)},
      MRNUMBER = {1433640},
      MRREVIEWER = {Daniel Segal},
      DOI = {10.1007/BF01271271},
      ZBLNUMBER = {0880.20019},
      }
  • [PS97] Go to document L. Pyber and A. Shalev, "Asymptotic results for primitive permutation groups," J. Algebra, vol. 188, iss. 1, pp. 103-124, 1997.
    @article {PS97, MRKEY = {1432350},
      AUTHOR = {Pyber, L{á}szl{ó} and Shalev, Aner},
      TITLE = {Asymptotic results for primitive permutation groups},
      JOURNAL = {J. Algebra},
      FJOURNAL = {Journal of Algebra},
      VOLUME = {188},
      YEAR = {1997},
      NUMBER = {1},
      PAGES = {103--124},
      ISSN = {0021-8693},
      CODEN = {JALGA4},
      MRCLASS = {20B15},
      MRNUMBER = {1432350},
      MRREVIEWER = {Ulrich Dempwolff},
      DOI = {10.1006/jabr.1996.6818},
      ZBLNUMBER = {0877.20004},
      }
  • [PS01] Go to document 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.
    @article {PS01, MRKEY = {1854764},
      AUTHOR = {Pyber, L{á}szl{ó} and Shalev, Aner},
      TITLE = {Residual properties of groups and probabilistic methods},
      JOURNAL = {C. R. Acad. Sci. Paris Sér. I Math.},
      FJOURNAL = {Comptes Rendus de l'Académie des Sciences. Série I. Mathématique},
      VOLUME = {333},
      YEAR = {2001},
      NUMBER = {4},
      PAGES = {275--278},
      ISSN = {0764-4442},
      CODEN = {CASMEI},
      MRCLASS = {20P05 (20E26)},
      MRNUMBER = {1854764},
      DOI = {10.1016/S0764-4442(01)02044-4},
      ZBLNUMBER = {0991.20026},
      }
  • [Qu] Go to document 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.
    @article {Qu, MRKEY = {2241619},
      AUTHOR = {Quick, Martyn},
      TITLE = {Probabilistic generation of wreath products of non-abelian finite simple groups. {\rm {II}}},
      JOURNAL = {Internat. J. Algebra Comput.},
      FJOURNAL = {International Journal of Algebra and Computation},
      VOLUME = {16},
      YEAR = {2006},
      NUMBER = {3},
      PAGES = {493--503},
      ISSN = {0218-1967},
      MRCLASS = {20F05 (20E18 20E22)},
      MRNUMBER = {2241619},
      MRREVIEWER = {Nikolay V. Nikolov},
      DOI = {10.1142/S0218196706003074},
      ZBLNUMBER = {1103.20066},
      }
  • [Ro] Go to document J. S. Rose, "Automorphism groups of groups with trivial centre," Proc. London Math. Soc., vol. 31, iss. 2, pp. 167-193, 1975.
    @article {Ro, MRKEY = {0419601},
      AUTHOR = {Rose, John S.},
      TITLE = {Automorphism groups of groups with trivial centre},
      JOURNAL = {Proc. London Math. Soc.},
      FJOURNAL = {Proceedings of the London Mathematical Society. Third Series},
      VOLUME = {31},
      YEAR = {1975},
      NUMBER = {2},
      PAGES = {167--193},
      ISSN = {0024-6115},
      MRCLASS = {20D45},
      MRNUMBER = {0419601},
      MRREVIEWER = {Fletcher Gross},
      DOI = {10.1112/plms/s3-31.2.167},
      ZBLNUMBER = {0315.20021},
      }
  • [ShICM] A. Shalev, "Simple groups, permutation groups, and probability," in Proc. Int. Congr. Math., Vol. II, 1998, pp. 129-137.
    @inproceedings {ShICM, MRKEY = {1648063},
      AUTHOR = {Shalev, Aner},
      TITLE = {Simple groups, permutation groups, and probability},
      BOOKTITLE = {Proc. {I}nt. {C}ongr. {M}ath., {V}ol. {{\rm II}}},
      VENUE={{B}erlin, 1998},
      JOURNAL = {Doc. Math.},
      FJOURNAL = {Documenta Mathematica},
      YEAR = {1998},
      VOLUME = {{E}xtra {V}ol. II},
      PAGES = {129--137},
      ISSN = {1431-0635},
      MRCLASS = {20D06 (20B15 20P05)},
      MRNUMBER = {1648063},
      MRREVIEWER = {Robert M. Guralnick},
      ZBLNUMBER = {0898.20005},
      }
  • [Shnot] A. Shalev, "Asymptotic group theory," Notices Amer. Math. Soc., vol. 48, iss. 4, pp. 383-389, 2001.
    @article {Shnot, MRKEY = {1816298},
      AUTHOR = {Shalev, Aner},
      TITLE = {Asymptotic group theory},
      JOURNAL = {Notices Amer. Math. Soc.},
      FJOURNAL = {Notices of the American Mathematical Society},
      VOLUME = {48},
      YEAR = {2001},
      NUMBER = {4},
      PAGES = {383--389},
      ISSN = {0002-9920},
      CODEN = {AMNOAN},
      MRCLASS = {20F69 (20E07 20P05)},
      MRNUMBER = {1816298},
      MRREVIEWER = {Martin W. Liebeck},
      ZBLNUMBER = {1048.20027},
      }

Authors

Andrei Jaikin-Zapirain

Departamento de Matemáticas
Universidad Autónoma de Madrid
Spain

and

Instituto de Ciencias Matemáticas
CSIC-UAM-UC3M-UCM

László Pyber

Alfréd Rényi Institute of Mathematics
Hungarian Academy of Sciences
Budapest
Hungary