The expected number of random elements to generate a finite group

DOI10.1007/S00605-015-0789-5MaRDI QIDQ314490zbMATH OpenOpenAlexFDO

Authors Andrea Lucchini

Publication date 16 September 2016

Published in Monatshefte für Mathematik (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/11577/3210788

zbMATH Keywords

groups generationpermutations groupsprofinite groupswaiting time

Mathematics Subject Classification ID

Symmetric groups (20B30) Finite simple groups and their classification (20D05) Limits, profinite groups (20E18) Generators, relations, and presentations of groups (20F05) Probabilistic methods in group theory (20P05)

Review text

For a finite group \(G\), the probability that \(n\) randomly chosen elements of \(G\) generate \(G\) is denoted by \(P_G(n)\), that is, \[ P_G(n)= \frac{|\{(g_1,\dots,g_n)\in G^n: \langle g_1,\dots,g_n\rangle=G\}|}{| G|^n}. \] Let \(x=(x_n)_{n\in \mathbb{N}}\) be a sequence of independent, uniformly distributed G-valued random variables. One may define a random variable \(\tau_G\) (a waiting time) by \(\tau_G=\min\{n\geq 1\mid \langle x_1,\dots,x_n\rangle =G\}\), then \(P(\tau_G>n)=1-P_G(n)\). Let \(e_1(G)\) be the expectation \(E(\tau_G)\) of this random variable, then \(e_1(G)\) is the expected number of elements of G which have to be drawn at random, with replacement, before a set of generators is found. Then, \(e_1(G)=\sum_{n\geq1}nP(\tau_G=n)=\sum_{n\geq0}(1-P_G(n))\). Clearly, \(e_1(G)\geq d(G)\), where \(d(G)\) denotes the minimum number of elements required to generate \(G\). The quantity \(\text{ex}(G)=e_1(G)-d(G)\) is called the excess of G. Moreover, \(e_2(G)\) denotes the second moment \(E(\tau^2(G))\), from which the variance of \(\tau_G\) can be obtained as \(\text{Var}(\tau_G)=e_2(G)-e_1(G)^2.\) \textit{C. Pomerance} [Period. Math. Hung. 43, No. 1--2, 191--198 (2001; Zbl 0980.20079)] computed the excess of every finite abelian group. As was shown by \textit{W. M. Kantor} and \textit{A. Lubotzky} [Geom. Dedicata 36, No. 1, 67--87 (1990; Zbl 0718.20011)], the excess of groups is not bounded in general. However, answering a conjecture of Pak, \textit{A. Lubotzky} [J. Algebra 257, No. 2, 452--459 (2002; Zbl 1042.20047)] and \textit{E. Detomi} and the author [J. Algebra 265, No. 2, 651--668 (2003; Zbl 1072.20031)] showed that \[ \mathrm{ex}(G)\leq (e-1)d(G)+O(\log\log|G|). \] In this paper, the author uses a different approach to the study of \(e_1(G)\) and \(\mathrm{ex}(G)\). Precisely, he uses the theory of Möbius functions of subgroup lattices of groups to obtain formulas for \(e_1(G)\), \(e_2(G)\) and \(\mathrm{ex}(G)\), for instance, \[ e_1(G)=-\sum_{H< G}\frac{\mu_G(H)|G|}{|G|-|H|} \] \[ e_2(G)=-\sum_{H< G}\frac{\mu_G(H)|G|(|G|+|H|)}{(|G|-|H|)^2} \] \[ \mathrm{ex}(G)=-\sum_{H< G}\frac{\mu_G(H)}{[G:H]^{d(G)}} \frac{|G|}{|G|-|H|} \] Using such formulas, the author obtains some bounds for \(e_1(G)\) and \(e_2(G)\) when \(G\) is a nonabelian finite simple group or a finite symmetric group. Finally, the author proves that for any finite group \(G\), \(\mathrm{ex}(G)\leq \lceil 2\log_2\log_2|G|\rceil +5\).

Recommendations

• The expected number of random elements to generate a finite Abelian group
• scientific article; zbMATH DE number 908573
• Some new results in probabilistic group theory
• The probability of randomly generating finite Abelian groups.
• scientific article; zbMATH DE number 2114353
• When do random subsets decompose a finite group?
• Strongly generating elements in finite and profinite groups

Cites work

• Bounds for the probability of generating the symmetric and alternating groups.
• Crowns and factorization of the probabilistic zeta function of a finite group.
• scientific article; zbMATH DE number 5532013 (Why is no real title available?)
• On the probabilistic ζ-function of pro(finite-soluble) groups
• On the probability of generating free prosoluble groups of small rank.
• Positively finitely generated groups
• Probability and bias in generating supersoluble groups
• Simple groups, maximal subgroups, and probabilistic aspects of profinite groups
• Subgroup growth.
• THE EULERIAN FUNCTIONS OF A GROUP
• The expected number of random elements to generate a finite Abelian group
• The expected number of random elements to generate a finite group.
• The probability of generating a finite classical group
• The probability of generating a finite simple group
• The probability of generating a finite simple group.
• The probability of generating the symmetric group
• The Subgroups of M₂₄, or How to Compute the Table of Marks of a Finite Group
• The X-Dirichlet polynomial of a finite group

Cited in

(9)

• The expected number of elements to generate a finite group with \(d\)-generated Sylow subgroups
• A bound on the expected number of random elements to generate a finite group all of whose Sylow subgroups are \(d\)-generated
• Strongly generating elements in finite and profinite groups
• scientific article; zbMATH DE number 908573 (Why is no real title available?)
• scientific article; zbMATH DE number 7359829 (Why is no real title available?)
• Comparing the expected number of random elements from the symmetric and the alternating groups needed to generate a transitive subgroup
• The expected number of random elements to generate a finite Abelian group
• Minimal generating sequences of \(\mathfrak{F}\)-subgroups
• The Chebotarev invariant for direct products of nonabelian finite simple groups

Describes a project that uses

Uses Software

• GAP

This page was built for publication: The expected number of random elements to generate a finite group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q314490)