Random Permutations

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.

Huseyin Acan, Charles Burnette, Eric Schmutz, James Thomas, and I have just uploaded our paper Permutations With Equal Orders to the arXiv.

The motivating question is one that was discussed previously on this blog: what is the probability that two random permutations ${\pi}$ and ${\pi'}$ have the same order? Equivalently, what is the “collision entropy” of the random variable ${\textup{ord}\, \pi}$ ? If ${\pi}$ and ${\pi'}$ happen to be conjugate, say if they are both ${n}$ -cycles, then of course they have the same order, which leads to the lower bound

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \geq \mathbf{P}(\pi \sim \pi') \sim \frac{\Delta}{n^2},$

where ${\Delta \approx 4.26}$ is an explicit constant determined by Flajolet, Fusy, Gourdon, Panario, and Pouyanne. It is natural to guess, based on this as well as numerical evidence, that

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \sim \frac{\Delta'}{n^2}$

for some other constant ${\Delta'}$ . This guess turns out to be wrong, but only narrowly so. We prove in our paper that

$\displaystyle \limsup \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2 = \infty,$

but that

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \leq n^{-2+o(1)}.$

This is certainly not a complete picture, however, and the project is ongoing. Among the things I expect to be true and hope to prove are the following:

${\liminf \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ is finite.
${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ is bounded by a very slowly growing function of ${n}$ , perhaps even ${\log^* n}$ .
The value of ${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ depends sensitively on the arithmetic of ${n}$ . In particular, ${\mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') \cdot n^2}$ converges along any sequence of the form ${n = m! + \text{constant}}$ .

The proof of the bound

$\displaystyle \mathbf{P}(\textup{ord}\, \pi = \textup{ord}\, \pi') = n^{-2+o(1)}$

requires a lemma that may be interesting more generally. We prove that all except ${n^{-1+\epsilon}}$ permutations ${\pi}$ have order which is divisible by ${\Omega_\epsilon(\log n)}$ primes ${p > n^{\Omega_\epsilon(1)}}$ . In particular, all except ${n^{-1+\epsilon}}$ permutations have order at least ${e^{\Omega_\epsilon(\log^2 n)}}$ . This is a sort of tail bound related to the famous result of Erdős and Turán that ${\log \textup{ord}\, \pi}$ is approximately normal with mean ${\frac12 \log^2 n}$ and variance ${\frac13 \log^3 n}$ . It might be interesting to try to pin this down more exactly: Estimate the probability that ${\textup{ord}\, \pi \leq e^{x \log^2 n}}$ for any given constant ${x>0}$ . The result should be of the form ${n^{-1 + f(x) + o(1)}}$ for some function ${f(x)}$ which tends to zero with ${x}$ .

Incidentally, in terms of arXiv mechanics, we decided to upload our paper as an update to an earlier paper of the other four authors, so this paper might not have appeared in your usual feed. The overlap of this version with the previous one is virtually empty, however, apart from having the same motivating question.

Finally, I’m happy to report that my Erdős number has now fallen to ${2}$ , presumably its final value.

Happy new year everyone.