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.

Stefan Virchow and I have just uploaded our paper Random generation of the special linear group to the arXiv. In this paper we study random generation of ${\textup{SL}(n,q)}$ by two random elements, asymptotically as either ${n\to\infty}$ or ${q\to\infty}$ . It was proved by Kantor and Lubotzky some years ago that two random elements almost surely generate the group: indeed, they proved this for all classical finite simple groups of Lie type ${G}$ , as ${|G|\to\infty}$ . Our big innovation is a proof, in the special case ${G = \textup{SL}(n,q)}$ , that does not depend on the classification of finite simple groups.

Our method is an adaptation of one we used in our previous paper, The probability of generating the symmetric group (journal link: Combinatorica 2018). In that paper we proved, also without the classification, that two random elements of ${S_n}$ generate at least ${A_n}$ with probability ${1-1/n + 1/n^{2+o(1)}}$ . Briefly, the idea is that if ${\pi, \sigma}$ are random elements, then the ${N}$ elements ${\pi, \pi\sigma, \dots, \pi\sigma^{N-1}}$ are pairwise approximately independent (more precisely, approximately equidistributed with respect to rectangles in ${G \times G}$ ). Thus we can leverage the second moment method to show, given our favourite set ${S \subset G}$ , that there is almost surely some ${i}$ such that ${\pi\sigma^i \in S}$ . If we apply this with a couple of judiciously chosen sets ${S}$ then we should be able to deduce that ${\langle \pi, \sigma\rangle = G}$ . Additionally, if the sets ${S}$ are chosen to be conjugation-invariant then we can express the variance in terms of character sums, and apply known character estimates (due to Larsen, Shalev, and Tiep) to conclude.

One particularly interesting thing we learned is a connection between this method, for a general group ${G}$ , and the average inverse order

$\displaystyle \eta_G = \frac1{|G|} \sum_{g \in G} \frac1{\textup{ord}\, g}.$

For example, it is not too hard to see that ${\eta_{S_n} = n^{-2+o(1)}}$ , the main contribution coming from ${n}$ -cycles, and this is fundamentally why our previous paper was limited to ${n^{-2+o(1)}}$ . One of the essential steps in the present paper is an estimation of ${\eta_{\textup{SL}(n,q)}}$ . We prove that

$\displaystyle \eta_{\textup{SL}(n,q)} = \exp(-(2+o(1)) \sqrt{n \log n \log q}),$

(the lower bound only if ${n}$ is large compared to ${q}$ ). In other words, the harmonic mean of the orders of the elements of ${\textup{SL}(n,q)}$ is

$\displaystyle \exp((2+o(1)) \sqrt{n \log n \log q}).$

By contrast, it was proved by Stong and Schmutz, respectively, that the mean order is ${q^n/n^{1+o(1)}}$ and the typical order is ${q^{n - (\log n)^{2+o(1)}}}$ .

That there should be any connection between these problems is fascinating, but if I’m honest I think it’s an artifact of the method rather than an essential connection. To go further, we need to elaborate on the “ ${\pi\sigma^i}$ trick” in a way that remains tractable but overcomes the ${\eta_G}$ obstruction.