The expected number of random elements to generate a finite group.
type: Item
instance of: scholarly article
title: The expected number of random elements to generate a finite group.
zbMATH Open document ID: 1042.20047
DOI: 10.1016/S0021-8693(02)00528-8
published in: Journal of Algebra
publication date: 2003-02-12T00:00:00Z
review text: Let \(G\) be a finite group and let \(d(G)\) be the minimal number of generators it requires. The author considers the related functions \({\mathcal E}(G)\), \({\mathcal V}(G)\) and \({\mathcal M}(G)\) defined as follows: \({\mathcal E}(G)\) is the expected number of elements chosen at random from \(G\) until a set of generators is obtained; \({\mathcal V}(G)\) is the least integer \(k\) such that \(k\) random elements from \(G\) generate \(G\) with probability at least \(1/e\); and \({\mathcal M}(G)\) is the smallest real number \(\mu\) such that, for each \(n\), the number of maximal subgroups of index \(n\) in \(G\) is bounded above by \(n^\mu\). When \(G\) is Abelian, \textit{C. Pomerance} [Period. Math. Hung. 43, No. 1-2, 191-198 (2001; Zbl 0980.20079)] has shown that \(d(G)\leq{\mathcal E}(G)\leq d(G)+\sigma\) where \(\sigma=2.118\dots\) and, for any finite group, \textit{I. Pak} [On probability of generating a finite group, preprint (1999)] has given an elementary proof that \(e^{-1}{\mathcal E}(G)\leq{\mathcal V}(G)\leq e{\mathcal E}(G)/(e-1)\). A number of authors, beginning with \textit{A. Mann} [Forum Math. 8, No. 4, 429-459 (1996; Zbl 0852.20019)] have studied the function \({\mathcal M}(G)\). In the present paper the author proves the following inequalities for an arbitrary finite group (all logarithms are base 2): (1) \({\mathcal V}(G)\leq d(G)+2\log\log|G|+4.02\) and hence \({\mathcal E}(G)\leq ed(G)+2e\log\log|G|+11\); (2) \({\mathcal V}(G)-{\mathcal M}(G)\) lies between \(-3.5\) and \(2.02\); and (3) \({\mathcal M}(G)\leq d(G)+2\log\log|G|+2\). The first of these results proves a strong form of a conjecture of Pak. In a note at the end of the paper, the author adds that a different proof of Pak's conjecture has been obtained independently by E. Detoni and A. Lucchini.
reviewed by: John D. Dixon
Mathematics Subject Classification ID: 20P05
Mathematics Subject Classification ID: 20F05
zbMATH DE Number: 1868071
zbMATH Keywords: finite groups
zbMATH Keywords: numbers of generators
zbMATH Keywords: randomly chosen elements
zbMATH Keywords: subgroups of finite index
author: Alexander Lubotzky
MaRDI profile type: Publication
cites work: Maximal subgroups of finite groups
cites work: Maximal subgroups in finite and profinite groups
cites work: How many elements are needed to generate a finite group with good probability?
cites work: Q4882944
cites work: Q3253828
cites work: The probability of generating a finite classical group
cites work: Positively finitely generated groups
cites work: Simple groups, maximal subgroups, and probabilistic aspects of profinite groups
cites work: The expected number of random elements to generate a finite Abelian group
Recommended article: The expected number of random elements to generate a finite Abelian group
Recommended article: Q4993631
Recommended article: Strongly generating elements in finite and profinite groups
Recommended article: Minimal and random generation of permutation and matrix groups.
Recommended article: Generation and random generation: from simple groups to maximal subgroups.
Recommended article: Bounds on the number of maximal subgroups of finite groups
Recommended article: A probabilistic version of a theorem of lászló kovács and hyo-seob sim
Recommended article: The number of maximal subgroups and probabilistic generation of‎ ‎finite groups
Recommended article: The probability of generating a permutation group.
Recommended article: How many elements are needed to generate a finite group with good probability?
description: scientific article; zbMATH DE number 1868071