The Probability of Generating a Permutation Group
by
Fiorenza Morini
Universita' di Brescia
Coauthors: Andrea Lucchini (Universita' di Brescia)

It is well known that a permutation group of degree n can be generated by n-1 elements. A deeper result follows from the classification of finite simple groups: any subgroup G of Sym(n) can be generated by [n+1/2] elements. This motivates the following question: given a costant b how many [bn]-uples of elements of G generate G itself? Does the proportion of the [bn]-bases of G increase with n? We answer the question from an asymptotic point of view. If n is large enough, then the probability of generating G with [n/2] elements is at least 1/4. On the other hand if b > 1/2 and n is large enough, then [bn] randomly chosen elements of G almost certainly generate G.

Lucchini, Menegazzo, Morigi (2000) proved that a transitive group G of degree n can be generated by cn/(log n)^1/2 for a suitable constant c. A stronger result is true: if d > c then the probability of generating G with [dn/(log n)^1/2] elements tends to 1 as n tends to infinity.

Similar results are proved for completely irreducible linear groups over a finite field.

Date received: April 2, 2001

Copyright © 2001 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cage-22.