Daniele Garzoni and I have just uploaded to the arxiv our paper Random generation with cycle type restrictions. The motivating question for this project was: For which is it true that two random elements of of order almost surely generate at least ? This was known to be true for all bounded by work of Liebeck and Shalev (the case is immediately ruled out because any two elements of order generate a dihedral group). On the other hand, it is easy to come up with large , for example for some prime , for which almost surely two elements of order have many common fixed points. It rapidly comes into focus that the critical thing is cycle type, so we decided to try to answer the following more general question: For which conjugacy classes and is it true that random elements and almost surely generate at least ?
As already indicated, it is critical that and together have few fixed points, as otherwise (after one of them is replaced by a random conjugate) it is likely that will have a fixed point. Specifically, we require that is small compared to , where and count the fixed points in and respectively. It turns out that -cycles are also critical: if and count -cycles, then we need to be small compared to . Indeed, if and are both comparable to , then there is a positive probability that, after random conjugation, and will have a common -cycle.
In fact, more is true. It was a surprise to us to discover that, if and are both (so that and are nearly of cycle type ) then in fact is almost surely intransitive. To see this, let be the number of orbits of of size such that and both consist only of -cycles, and let be the sum of as ranges between and , say. Then
where is the probability that two random elements , each of cycle type , generate a transitive subgroup. It turns out that , and hence using Stirling’s approximation we have
Hence if , then by the divergence of the harmonic series we have . Combined with a second moment bound, this proves that almost surely.
In our paper we give several other examples like this to indicate what the required hypotheses should be, and we prove the following theorem.
Theorem 1 Assume that . Then
- is at least with probability if and only if ;
- is at least with probability bounded away from if and only if and .
The requirement that is technical, and a little unnatural. We could relax it a bit, but we do appear to need some a priori bound on in order to have some such if-and-only-if theorem. For example, suppose is an -cycle and is a transposition. Then , so our “natural” hypotheses are trivially satisfied. After random conjugation we have, up to relabelling, and , where is drawn uniformly from . The group is determined by : if then is imprimitive, while if then . Hence with probability exactly , which can be small or large depending on the arithmetic of .
In any case, armed with our theorem, we managed to answer our original question for a huge swathe of possible orders . Among other things, we proved that if has any divisor in the range then indeed two random elements of order will almost surely generate at least . See our paper for some other positive results, as well as several more examples which limit what you can expect to be true.