Invariable generation of classical groups

Elements {g_1, \dots, g_k} in a group {G} invariably generate if they still generate after an adversary replaces them by conjugates. This is a function of conjugacy classes: we could say that conjugacy classes {\mathcal{C}_1, \dots, \mathcal{C}_k} in a group {G} invariably generate if {\langle g_1, \dots, g_k\rangle = G} whenever {g_i \in \mathcal{C}_i} for each {i}. This concept was invented by Dixon to quantify expected running time of the most standard algorithm for computing Galois groups: reduce modulo various primes {p}, get your Frobenius element {g_p}, and then try to infer what your Galois group is from the information that it contains {g_p} (which is defined only up to conjugacy) for each {p}. If {\textup{Gal}(f)} is secretly {G}, and you somehow know a priori that {\textup{Gal}(f) \leq G}, then the number of primes you need on average to prove that {\textup{Gal}(f) = G} is the expected number of elements it takes to invariably generate {G}.

For example, if {G = S_n}, then we know that four random elements invariably generate with positive probability, while three random elements almost surely (as {n\to\infty}) do not invariably generate. Therefore if {\textup{Gal}(f) = S_n} then it typically takes four primes to prove it.

A few days ago Eilidh McKemmie posted a paper on the arxiv which extends this result to finite classical groups: e.g., if {G} is {\textup{SL}_n(q)} then, for large enough constant {q} and {n\to\infty}, four random elements invariably generate with positive probability, but three do not. (The bounded-rank case is rather different in character, and I think two elements suffice.) The proof is pretty cool: invariable generation in {G} is related to invariable generation in the Weyl group, which is either {S_n} or {C_2 \wr S_n}, and we already understand invariable generation for these groups (using a small trick for the latter).

I believe the restriction to large enough constant {q} is a technical rather than essential problem. Assuming it can be overcome, we will be able to deduce the following rather clean statement: If {G} is a finite simple group then four random elements invariably generate {G} with probability bounded away from zero. Moreover, if the rank of {G} is unbounded then three random elements do not.

2 thoughts on “Invariable generation of classical groups

  1. Hi, can we distinguish S_n and A_n here? i.e., how many random elements invariably generate with positive probability for A_n?


    1. The answer is the same for A_n: four suffice, three do not. The “three do not” part is implied by the S_n result. The “four suffice” part is not immediate, but the proof is exactly the same. These events are dominated by what happens with small cycles, and the distribution of small cycles is asymptotically independent from the sign of the permutation.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s