The expected number of random elements to generate a finite group. (Q1858260): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 05:57, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The expected number of random elements to generate a finite group. |
scientific article |
Statements
The expected number of random elements to generate a finite group. (English)
0 references
12 February 2003
0 references
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.
0 references
finite groups
0 references
numbers of generators
0 references
randomly chosen elements
0 references
subgroups of finite index
0 references