Random generation of finite and profinite groups and group enumeration

Andrei Jaikin-Zapirain; László Pyber

doi:http://doi.org/10.4007/annals.2011.173.2.4

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.

Show/hide bibliography for this article

[Asc] M. Aschbacher, Finite Group Theory, Cambridge: Cambridge Univ. Press, 1986, vol. 10.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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.

Show bibtex

@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}, }

Random generation of finite and profinite groups and group enumeration

Abstract

Authors