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

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

Random generation with cycle type restrictions

Published by Sean Eberhard

Leave a comment Cancel reply

Share this:

Related

Published by Sean Eberhard

Leave a comment Cancel reply