Random Permutations

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

${\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)}$ ;
${\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.