The expected number of random elements to generate a finite group. (English) Zbl 1383.20041
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.\) 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 W. M. Kantor and 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, A. Lubotzky [J. Algebra 257, No. 2, 452–459 (2002; Zbl 1042.20047)] and 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\).
\[ 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\).
Reviewer: Fiorenza Morini (Parma)
MSC:
20P05 | Probabilistic methods in group theory |
20B30 | Symmetric groups |
20F05 | Generators, relations, and presentations of groups |
20D05 | Finite simple groups and their classification |
20E18 | Limits, profinite groups |
Software:
GAPReferences:
[1] | Crestani, E., De Franceschi, G., Lucchini, A.: Probability and bias in generating supersoluble groups. Proc. Edinb. Math. Soc. (To appear) · Zbl 1387.20058 |
[2] | Detomi, E., Lucchini, A.: Crowns and factorization of the probabilistic zeta function of a finite group. J. Algebra 265, 651-668 (2003) · Zbl 1072.20031 · doi:10.1016/S0021-8693(03)00275-8 |
[3] | Detomi, E., Lucchini, A.: Some generalizations of the probabilistic zeta function. In: Ischia Group Theory 2006, pp. 56-72. World Scientific Publishing, Hackensack (2007) · Zbl 1167.20040 |
[4] | Dixon, J.D.: The probability of generating the symmetric group. Math. Z. 110, 199-205 (1969) · Zbl 0176.29901 · doi:10.1007/BF01110210 |
[5] | Finch, S.: Mathematical Constants. Encyclopedia of Mathematics and its Applications, vol. 94. Cambridge University Press, Cambridge (2003) · Zbl 1222.20003 |
[6] | The GAP Group, GAP: Groups, algorithms, and programming, Version 4.7.7 (2015). http://www.gap-system.org · Zbl 0877.20017 |
[7] | Hall, P.: The Eulerian functions of a group. Q. J. Math. 7, 134-151 (1936) · Zbl 0014.10402 · doi:10.1093/qmath/os-7.1.134 |
[8] | Kantor, W.M., Lubotzky, A.: The probability of generating a finite classical group. Geom. Dedic. 36, 67-87 (1990) · Zbl 0718.20011 · doi:10.1007/BF00181465 |
[9] | Liebeck, M.W., Shalev, A.: The probability of generating a finite simple group. Geom. Dedic. 56, 103-113 (1995) · Zbl 0836.20068 · doi:10.1007/BF01263616 |
[10] | Lubotzky, A., Segal. D.: Subgroup Growth. Progress in Mathematics, vol. 212. Birkhäuser, Basel (2003) · Zbl 1071.20033 |
[11] | Lubotzky, A.: The expected number of random elements to generate a finite group. J. Algebra 257, 452-459 (2002) · Zbl 1042.20047 · doi:10.1016/S0021-8693(02)00528-8 |
[12] | Lucchini, A.: The \[X\] X-Dirichlet polynomial of a finite group. J. Group Theory 8, 171-188 (2005) · Zbl 1090.20038 · doi:10.1515/jgth.2005.8.2.171 |
[13] | Mann, A.: Positively finitely generated groups. Forum Math. 8, 429-459 (1996) · Zbl 0852.20019 · doi:10.1515/form.1996.8.429 |
[14] | Mann, A., Shalev, A.: Simple groups, maximal subgroups, and probabilistic aspects of profinite groups. Isr. J. Math. 96, 449-468 (1996) · Zbl 0877.20017 · doi:10.1007/BF02937317 |
[15] | Maróti, A., Tamburini, M.C.: Bounds for the probability of generating the symmetric and alternating groups. Arch. Math. 96, 115-121 (2011) · Zbl 1222.20003 · doi:10.1007/s00013-010-0216-z |
[16] | Menezes, N.E., Quick, M., Roney-Dougal, C.M.: The probability of generating a finite simple group. Isr. J. Math. 198(1), 371-392 (2013) · Zbl 1291.20068 · doi:10.1007/s11856-013-0034-7 |
[17] | Morigi, M.: On the probability of generating free prosoluble groups of small rank. Isr. J. Math. 155, 117-123 (2006) · Zbl 1139.20025 · doi:10.1007/BF02773951 |
[18] | Pfeiffer, G.: The subgroups of \[M_{24},\] M24, or how to compute the table of marks of a finite group. Exp. Math. 6, 247-270 (1997) · Zbl 0895.20017 · doi:10.1080/10586458.1997.10504613 |
[19] | Pomerance, C.: The expected number of random elements to generate a finite abelian group. Period. Math. Hung. 43, 191-198 (2001) · Zbl 0980.20079 |
[20] | Weigel, T.: On the probabilistic \[\zeta\] ζ-function of pro(finite-soluble) groups. Forum Math. 17, 669-698 (2005) · Zbl 1084.20020 · doi:10.1515/form.2005.17.4.669 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.