Random generation with cycle type restrictions

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 {m} is it true that two random elements of {S_n} of order {m} almost surely generate at least {A_n}? This was known to be true for all bounded {m > 2} by work of Liebeck and Shalev (the case {m=2} is immediately ruled out because any two elements of order {2} generate a dihedral group). On the other hand, it is easy to come up with large {m}, for example {m = p} for some prime {p \sim 3n/4}, for which almost surely two elements of order {m} 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 {\mathcal{C}} and {\mathcal{C}'} is it true that random elements {\pi\in\mathcal{C}} and {\pi'\in\mathcal{C}'} almost surely generate at least {A_n}?

As already indicated, it is critical that {\pi} and {\pi'} together have few fixed points, as otherwise (after one of them is replaced by a random conjugate) it is likely that {\langle \pi, \pi'\rangle} will have a fixed point. Specifically, we require that {c_1 c'_1} is small compared to {n}, where {c_1} and {c'_1} count the fixed points in {\pi} and {\pi'} respectively. It turns out that {2}-cycles are also critical: if {c_2} and {c'_2} count {2}-cycles, then we need {c_2 c'_2} to be small compared to {n^2}. Indeed, if {c_2} and {c'_2} are both comparable to {n}, then there is a positive probability that, after random conjugation, {\pi} and {\pi'} will have a common {2}-cycle.

In fact, more is true. It was a surprise to us to discover that, if {c_2} and {c'_2} are both {n/2 - o(n)} (so that {\pi} and {\pi'} are nearly of cycle type {2^{n/2}}) then in fact {\langle \pi, \pi'\rangle} is almost surely intransitive. To see this, let {N_k} be the number of orbits {X} of {\langle \pi, \pi'\rangle} of size {2k} such that {\pi|_{X}} and {\pi'|_X} both consist only of {2}-cycles, and let {N} be the sum of {N_k} as {k} ranges between {1} and {n^{1/3}}, say. Then

\displaystyle  \mathbf{E} N_k = \binom{n}{2k}^{-1} \binom{c_2}{k} \binom{c_2'}{k} p(k),

where {p(k)} is the probability that two random elements {\sigma, \sigma' \in S_{2k}}, each of cycle type {2^k}, generate a transitive subgroup. It turns out that {p(k) \asymp k^{-1/2}}, and hence using Stirling’s approximation we have

\displaystyle  \mathbf{E} N_k \asymp \left(\frac{4 c_2 c'_2}{n}\right)^k \frac1k.

Hence if {c_2, c'_2 = n/2 - o(n)}, then by the divergence of the harmonic series we have {\mathbf{E} N = \omega(1)}. Combined with a second moment bound, this proves that {N > 0} 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 {c_1, c'_1 = o(n^{2/3})}. Then

  1. {\langle \pi, \pi'\rangle} is at least {A_n} with probability {1-o(1)} if and only if {(c_1 + c_2^{1/2}) (c'_1 + {c'_2}^{1/2}) = o(n)};
  2. {\langle \pi, \pi'\rangle} is at least {A_n} with probability bounded away from {0} if and only if {(c_1 + c_2^{1/2}) (c'_1 + {c'_2}^{1/2}) = O(n)} and {c_2 + c'_2 = n - \Omega(n)}.

The requirement that {c_1, c'_1 = o(n^{2/3})} is technical, and a little unnatural. We could relax it a bit, but we do appear to need some a priori bound on {c_1, c'_1} in order to have some such if-and-only-if theorem. For example, suppose {\pi} is an {n}-cycle and {\pi'} is a transposition. Then {c_1 = c_2 = 0}, so our “natural” hypotheses are trivially satisfied. After random conjugation we have, up to relabelling, {\pi = (12 \cdots n)} and {\pi' = (xn)}, where {x} is drawn uniformly from {\{1, \dots, n-1\}}. The group {\langle \pi, \pi'\rangle} is determined by {\gcd(x, n)}: if {\gcd(x,n) > 1} then {\langle \pi, \pi'\rangle} is imprimitive, while if {\gcd(x, n) = 1} then {G = S_n}. Hence {\langle \pi, \pi'\rangle \geq A_n} with probability exactly {\varphi(n) / n}, which can be small or large depending on the arithmetic of {n}.

In any case, armed with our theorem, we managed to answer our original question for a huge swathe of possible orders {m}. Among other things, we proved that if {m} has any divisor {d} in the range {2 < d < o(n^{1/2})} then indeed two random elements of order {m} will almost surely generate at least {A_n}. See our paper for some other positive results, as well as several more examples which limit what you can expect to be true.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s