Random Permutations

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.

Jeff Kahn, Bhargav Narayanan, Sophie Spirkl, and I have just uploaded to the arxiv our note On symmetric intersecting families of vectors. We are interested in problems in extremal set theory with symmetry constraints. Often in extremal set theory it is useful to “compress”, which you can think of as trying to reduce your arbitrary system to a simpler system, one that may be easier to understand. With symmetry constraints, the added challenge is that your compression method should also satisfy those symmetry constraints.

Our particular focus is symmetric intersecting families. A family ${\mathcal{A} \subset 2^{[n]}}$ of subsets ${A \subset [n]}$ (where ${[n] = \{1, \dots, n\}}$ ) is termed intersecting if for any ${A, B \in \mathcal{A}}$ , we have ${A \cap B \neq \emptyset}$ . More generally ${\mathcal{A}}$ is termed ${r}$ -wise intersecting if for any ${A_1, \dots, A_r \in \mathcal{A}}$ we have ${A_1 \cap A_2 \cap \cdots \cap A_r \neq \emptyset}$ . How large can an ${r}$ -wise intersecting family ${\mathcal{A} \subset 2^{[n]}}$ be? Trivially, it can be as large as ${2^{n-1}}$ : just take all sets containing some point ${1 \in [n]}$ . But what if we demand that ${\mathcal{A}}$ have a transitive symmetry group? If ${r=2}$ we can just take the family of all sets of size greater than ${n/2}$ , but if ${r \geq 3}$ the situation is unclear. This question was answered by Frankl in 1981 for ${r \geq 4}$ , and answered for ${r = 3}$ only recently by Ellis and Narayanan.

The Ellis–Narayanan proof can be understood, at least if you squint, as a compression argument. Define the ${p}$ -biased measure ${\mu_p}$ on ${2^{[n]}}$ by

$\displaystyle \mu_p(\{A\}) = p^{|A|} (1-p)^{n-|A|}.$

Put another way, ${\mu_p(\mathcal{A})}$ is the probability that ${A \in \mathcal{A}}$ if ${A}$ is chosen randomly by flipping ${n}$ independent ${p}$ -biased coins. We want to show that ${\mu_{1/2}(\mathcal{A}) = o(1)}$ under the assumption that ${\mathcal{A}}$ is ${3}$ -wise intersecting and symmetric. This is not obvious, but what is obvious is that

$\displaystyle \mu_{2/3}(\mathcal{A}) \leq 2/3.$

This is a bit like the basic observation that an intersecting family can have density at most ${1/2}$ , because for each set ${A}$ you can have only either ${A}$ or ${A^c}$ . For the above inequality, define three sets ${A_1, A_2, A_3}$ by independently selecting two of them for each ${x \in [n]}$ and including ${x}$ in those two sets. Then ${A_1, A_2, A_3}$ are coupled random variables, each individually having the ${\mu_{2/3}}$ distribution, such that ${A_1 \cap A_2 \cap A_3 = \emptyset}$ . The above inequality follows. Now although it is difficult to compress ${\mathcal{A}}$ while preserving symmetry, we can “compress our counting method” ${\mu_{1/2}}$ up to ${\mu_{2/3}}$ . A sharp threshold theorem of Friedgut and Kalai (relying on the BKKKL theorem, from the analysis of boolean functions) implies that, under symmetry, the function ${p \mapsto \mu_p(\mathcal{A})}$ has a sharp threshold: it changes from ${\varepsilon}$ to ${1-\varepsilon}$ over an interval of length ${O(\log \varepsilon^{-1} / \log n)}$ . Since ${\mu_{2/3}(\mathcal{A}) \leq 2/3}$ , this implies that ${\mu_{1/2}(\mathcal{A})}$ must be small; in fact ${\mu_{1/2}(\mathcal{A}) \leq n^{-c}}$ for some constant ${c>0}$ .

In our new paper we looked at a further variant of this problem. Suppose ${\mathcal{A}}$ is a subset of ${[3]^n}$ which is intersecting (just ${2}$ -wise now) in the sense that for any two vectors ${x, y \in \mathcal{A}}$ there is an ${i\in [n]}$ such that ${x_i = y_i}$ . Again, assume that ${\mathcal{A}}$ has a transitive group of symmetries. Must it be the case that ${\mathcal{A}}$ has size ${o(3^n)}$ ? The problem is that there is no obvious ${p}$ -biased measure to move around this time, but we got around this problem with the following cute device: Embed ${[3]}$ into

$\displaystyle W = \{\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}\}$

in the obvious way, and replace ${\mathcal{A}}$ with its up-closure in ${W^n}$ . Let ${\mu_0}$ be the uniform measure on the bottom level and ${\mu_1}$ the uniform measure on the top level. Then ${\mu_0(\mathcal{A})}$ is the thing we are interested in, and ${\mu_{1/2}}$ is the uniform measure on ${W^n}$ . Again it is obvious that ${\mu_{1/2}(\mathcal{A}) \leq 1/2}$ , so we are done if we can prove a sharp threshold theorem for ${\mu_p(\mathcal{A})}$ , and that’s what we did. We again get a bound of the form ${n^{-c}}$ .

That bound ${n^{-c}}$ is a little unsatisfying actually. We expect the truth to look like ${\exp(-cn^\delta)}$ for some ${\delta > 0}$ . Going back to the problem of ${r}$ -wise intersecting families in ${[2]^n}$ , this was proved by Cameron, Frankl, and Kantor for ${r\geq 4}$ , and there are plenty of examples to show you can’t do better for any ${r \geq 3}$ , but the upper bound for ${r=3}$ remains mysterious. But at least the new proofs tell us where to look: we want a ${3}$ -wise intersecting family with small total influence, or we want to prove that that’s impossible.