Random generation of the special linear group

Uncategorized

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.

Published by Sean Eberhard

Published

One thought on “Random generation of the special linear group”

  1. Pingback: Babai’s conjecture for (at least three) random generators – Random Permutations

Leave a comment