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.

Leave a Reply

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

WordPress.com Logo

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

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s