How many elements are needed to generate a finite group with good probability?
For a finite group \(G\), let \(d(G)\) denote the least number of elements required to generate \(G\), and \(\lambda(G)\) be the length of a composition series of \(G\). For each real \(\alpha\) with \(0<\alpha<1\), the authors define \(d_\alpha(G)\) to be the least integer \(t\) such that \(t\) elements chosen at random from \(G\) generate \(G\) with probability at least \(\alpha\). Examples show that \(d_\alpha(G)\) cannot be bounded by a function depending only on \(d(G)\). The authors prove that for each \(\alpha\) there exists a constant \(c_\alpha\) such that \[ d_\alpha(G)\leq d(G)+c_\alpha\log\lambda(G)\log\log\lambda(G)\leq d(G)+c_\alpha\log\log|G|\log\log\log|G| \] whenever \(\lambda(G)\geq 4\) (all logarithms are base 2). For \(\lambda(G)<4\) the corresponding bound is \(d(G)+c_\alpha\). As they note, this bound is close to one conjectured by I. Pak (unpublished). As a corollary they prove: if \(\beta>\tfrac 12\) and \(0<\alpha<1\) then there exists \(n_0\) such that \(d_\alpha(G)\leq\beta n\) for every permutation group \(G\) of degree \(n\geq n_0\). A similar result (with \(\beta>\tfrac 32\)) is proved for completely reducible linear groups of degree \(n\). Since this paper was published, stronger theorems proving the full conjecture of Pak have been obtained by \textit{A. Lubotzky} [J. Algebra 257, No. 2, 452-459 (2002; Zbl 1042.20047)].
scientific article; zbMATH DE number 1874386
scientific article