The expected number of random elements to generate a finite group (Q314490): Difference between revisions

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\).