Random generation of finite and profinite groups and group enumeration

Abstract

We 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 we prove that if $G$ is a $d$-generated linear group of dimension $n$ then $cd+\log n$ random generators suffice.

Changing perspective we investigate profinite groups $F$ which can be generated by a bounded number of elements with positive probability. In response to a question of Shalev we characterize such groups in terms of certain finite quotients with a transparent structure. As a consequence we settle several problems of Lucchini, Lubotzky, Mann and Segal.

As a byproduct of our techniques we obtain that the number of $r$-relator groups of order $n$ is at most $n^{cr}$ as conjectured by Mann.