Mathematical handwriting

I was once told in no uncertain terms to stop using the letter $\xi$ in my talks. I disagree. I think it’s a great letter, especially in scrabble.

I just stumbled acrossed this great page by John Kerl, which contains numerous tips for handwriting in mathematics. I think I differ in one or two places, but I couldn’t agree more with taking a moment to think about it. Maths is communication for the most part, starting with one’s own handwritten notes.

On the subject of excellent references about mathematical communication, I also really enjoyed reading The Grammar According to West, which is something of a Strunk and White for maths papers.

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.