Minimal and random generation of permutation and matrix groups. (Q2438897): Difference between revisions

Let \(G\) be a finite group and \(\varepsilon>0\). Then \(d(G)\) denotes the size of the smallest generating set and \(d^\varepsilon(G)\) denotes the least integer \(k\) such that a list of \(k\) random elements from \(G\) generates \(G\) with probability \(>1-\varepsilon\). \textit{A. Lubotzky} [J. Algebra 257, No. 2, 452-459 (2002; Zbl 1042.20047)] has shown that \(d(G)\leq d^\varepsilon(G)\leq d(G)+2\log\log|G|+t+2\) when the value of the Riemann zeta function \(\zeta(t)\leq 1+\varepsilon\) (except where noted, all logarithms in this review are to base \(2\)). With applications to computations in mind, the authors are interested in obtaining upper bounds on \(d(G)\) (and hence on \(d^\varepsilon(G)\)) with explicit constants for various classes of permutation groups and linear groups. Here are some examples. (Theorem 1.1) If \(H\) is a subnormal subgroup of a primitive permutation group of degree \(n>3\), then \(d(H)\leq\log n\). (Theorem 1.2) If \(G\) is a finite completely reducible linear group of degree \(n\) over a field \(F\) which does not contain a primitive \(4\)-th root of \(1\), then \(d(G)\leq n\). (Theorem 1.3) If \(G\) is a finite quasiprimitive linear group of degree \(n\), then \(d(G)\leq 1+\lceil(2\log_32)\log n\rceil\). Exampes show that these bounds are close to best possible. Proofs depend heavily on the classification of finite simple groups and often require a case-by-case examination.