Random generation of finite and profinite groups and group enumeration. (Q640754): Difference between revisions

The authors obtain a surprisingly explicit formula for the number of random elements needed to generate a finite \(d\)-generator group with high probability. As a corollary they prove that if \(G\) is a \(d\)-generated linear group of dimension \(n\) then \(cd+\log n\) random generators suffice. Changing perspective they investigate profinite groups which can be generated by a bounded number of elements with positive probability (PFG groups). In response to a question of Shalev they characterize such groups in terms of certain finite quotients with a transparent structure. Let \(L\) be a finite group with a non-Abelian unique minimal normal subgroup \(M\). A crown-based power \(L(k)\) of \(L\) is defined as the subdirect product subgroup of the direct power \(L^k\) containing \(M^k\) such that \(L(k)/M^k\) is isomorphic to the diagonal subgroup of \((L/M)^k\). The authors give the following semi-structural characterization of groups that are PFG. Let \(G\) be a finitely generated profinite group. Then \(G\) is PFG if and only if for any \(L\) as above if \(L(k)\) is a quotient of \(G\) then \(k\leq l(M)^c\) for some constant \(c\), \(l(M)\) being the minimal degree of a faithful transitive permutation representation of \(M\). The previous theorem is used by the authors to settle several open problems in the area. For example, it subsumes a conjecture of the reviewer according to which non-PFG groups have quotients which are crown-based powers of unbounded size. They can also answer a question of Lubotzky and Segal proving that finitely generated profinite groups of polynomial index growth are PFG. Moreover this theorem gives an easy proof that all previously known examples of PFG groups are indeed PFG. In fact groups which are not PFG are rather ``large'': a finitely generated profinite group \(G\) is PFG if and only if there exists a constant \(c\) such that for any almost simple group \(R\), any open subgroup \(H\) of \(G\) has at most \(l(R)^{c|G:H|}\) quotients isomorphic to \(R\). This immediately implies a positive solution of a well-known open problem of Mann: if \(H\) is an open subgroup in a PFG group, then \(H\) is also a PFG group. The proofs of these results are based on a new approach to counting permutation groups and permutation representations. The main technical result is the following: the number of conjugacy classes of \(d\)-generated primitive subgroups of \(\text{Sym}(n)\) is at most \(n^{cd}\) for some constant \(c\). As a byproduct of their techniques, the authors obtain that the number of \(r\)-relator groups of order \(n\) is at most \(n^{cr}\) as conjectured by Mann.