Generating direct powers of a simple group

Question: What is the largest {h} such that the direct product

\displaystyle  A_n^{\times h} = A_n \times \cdots \times A_n

of {h} copies of the alternating group {A_n} is {2}-generated?

This is the sort of question which somebody with little experience of nonabelian groups might get very wrong: such a person might guess {h=2} by analogy with linear algebra. Here’s a rough-and-ready construction that shows how wrong that logic is. Assume {n} is odd, for simplicity, and write {p_1, p_2, \dots} for the odd primes less than {n}. Let {\sigma \in A_n} be some {n}-cycle, for each {i} let {\tau_i} be a {p}-cycle, and let

\displaystyle  \begin{array}{rcl}  x &=& (\sigma, \sigma, \dots),\\ y &=& (\tau_1, \tau_2, \dots). \end{array}

Then for each {i} there is some {k_i > 0} such that

\displaystyle  y^{k_i} = (e, \dots, e, \tau_i, e, \dots).

Clearly then {\langle x, y^{k_i}\rangle} is a subgroup of

\displaystyle  \langle \sigma\rangle \times \cdots \times \langle \sigma\rangle \times A_n \times \langle \sigma \rangle \times \cdots,

surjecting onto the {A_n} factor. Since {A_n} is perfect (meaning {[A_n, A_n] = A_n}) we can now use commutators to isolate the {A_n} factor, and generation is proved. This shows that the answer to our initial question is at least {\pi(n-1)}.

In fact this construction is horribly inefficient, and it is possible to give a surprisingly exact answer. Though it is news to me in 2018, it was observed by Philip Hall in 1936.

Theorem 1 Let {G} be a finite group, let {h_d(G)} be the largest {h} such that {G^h} is {d}-generated, and let {\phi_d(G)} be the number of {d}-tuples {(g_1, \dots, g_d)\in G^d} such that {\langle g_1, \dots, g_d\rangle = G}. If {G} is nonabelian simple then

\displaystyle  h_d(G) = \frac{\phi_d(G)}{|\textup{Aut}\, G|}.

The notation {\phi_d(G)} is Hall’s, motivated by the connection with Euler’s phi function {\varphi(n)} from number theory:

\displaystyle  \varphi(n) = \phi_1(C_n).

For this reason, {\phi_d} is occasionally referred to as the Euler–Hall function of {G}. Like {\varphi(n)}, {\phi_d(G)} has summatory rule:

\displaystyle  |G|^d = \sum_{H\leq G} \phi_d(H).

This can be used to calculate {\phi_d(G)} for any group {G} whose subgroup lattice is well understood.

On the other hand, a probablistic group theorist like me is more likely to think

\displaystyle  \phi_d(G) / |G|^d = \mathbf{P}(\langle g_1, \dots, g_d\rangle = G),

expecting this to be close to {1} whenever {d>1}. This is the case for {A_n}, for example. Since {\textup{Aut}\, A_n \cong S_n} for {n>6}, we have our answer to our initial question:

\displaystyle  h_2(A_n) \sim \frac{|A_n|^2}{|S_n|} = \frac14 n!.

Compared to our earlier lower bound of {\pi(n-1)}, this is monstrous!

The proof of Theorem 1 is not hard, but it requires a little mental gymnastics. Write {\Phi_d(G)} for the set of generating {d}-tuples, so that {\phi_d(G) = |\Phi_d(G)|}. There is an obvious action of {\textup{Aut}\, G} on {\Phi_d(G)}, and a moment’s thought reveals that this action is fixed-point-free (if an automorphism fixes a set of generators then clearly it fixes everything). On the other hand we can think of {\Phi_d(G)} as the set of surjections {F_d \to G} from the free group {F_d} to {G}. In this view, the action of {\textup{Aut}\, G} is that of post-composition.

Lemma 2 Let {F} and {G} be groups, and let {f_1, f_2: F \to G} be surjections. Then the following are equivalent:

  1. There is an automorphism {\alpha \in \textup{Aut}\, G} such that {f_1 = \alpha f_2}.
  2. {\ker f_1 = \ker f_2}.

Proof: Obviously 1 implies 2. If 2 holds then {f_1, f_2} descend to isomorphisms {F/K \to G}, where {K} is the common kernel, and {\alpha} is readily obtained. \Box

Thus the orbits of {\textup{Aut}\, G} on {\Phi_d(G)} are in bijection with the subgroups {K \leq F_d} such that {F_d / K \cong G}. Therefore the number of such subgroups is precisely {\phi_d(G) / |\textup{Aut}\, G|}.

Let {\mathcal{K}} be the set of all such subgroups {K}. Clearly we have an injection

\displaystyle  F_d / \bigcap\mathcal{K} \to \prod_{K \in \mathcal{K}} F_d/K \cong G^{|\mathcal{K}|}.

If {f:F_d \to G^h} is a surjection, then {\ker f} contains {\bigcap \mathcal{K}}, so {f} factors through {F_d / \bigcap\mathcal{K}}, so {h \leq |\mathcal{K}|}. The proof is therefore concluded by the following lemma.

Lemma 3 Assume {G} is nonabelian simple. Then the map

\displaystyle  F / \bigcap \mathcal{K} \to \prod_{K\in \mathcal{K}} F/K

is surjective.

Proof: Write {\mathcal{K} = \{K_1, K_2, \dots\}}. We will prove by induction on {m} that

\displaystyle  F / (K_1 \cap \cdots \cap K_m) \to F / K_1 \times \cdots \times F/K_m

is surjective. The case {m=1} is trivial. The case {m=2} follows easily from Goursat’s lemma. For {m>2}, we know by induction that for all

\displaystyle  g_3, g_4, \dots, g'_3, g'_4, \dots \in G

the image in {F/K_1 \times \cdots F/K_m} contains points of the form

\displaystyle  (1, ?, g_3, g_4, \dots),\quad (?, 1, h_3, h_4, \dots).

Taking commutators and using {[G,G]=G}, we see that the image contains the subgroup {1^2 \times G^{m-2}}. Similarly, the image contains {G^{m-2} \times 1^2}. Therefore the image is {G^m}. \Box

Let’s close with a simple puzzle. In Theorem 1 we assumed that {G} is simple. What about, say, {S_n}? Prove that {h_2(S_n) = 2}.

Later edit: It seems that Kantor and Lubotzky found an easier way of thinking about this, or at least an equivalent way that involes less mental gymnastics. (See KL, Proposition 6.)

Theorem 4 (Kantor–Lubotzky) Let {T} be a nonabelian simple group, and let {s_1, \dots, s_d \in T^k} be candidate generators of {G = T^k}. Write {s_i = (t_{i1}, \dots, t_{ik})} for each {i}, and consider the matrix {d \times k} matrix

\displaystyle  \left(\begin{array}{ccc} t_{11} & \cdots & t_{1k} \\ \vdots & \ddots & \vdots \\ t_{d1} & \cdots & t_{dk}. \end{array}\right)

Then {s_1, \dots, s_d} generate {G} if and only if

  1. {\langle t_{1j}, \dots, t_{dj}\rangle = T} for each {j}, and
  2. {(t_{1j}, \dots, t_{dj})} are in different {\textup{Aut}\, T}-orbits for each {j}.

The conditions are clearly necessary: 1 is necessary lest the projection {\pi_j} of {\langle s_1, \dots, s_d\rangle} onto the {j}th factor not be surjective, and 2 is necessary lest {\langle s_1, \dots, s_d\rangle} be trapped in the subgroup of {T^k} defined by {\pi_j = \alpha \pi_{j'}} for some {j,j'} and some {\alpha \in \textup{Aut}\, T}.

The proof of sufficiency is much like that of Lemma 3 above. Use induction on {k}, using Goursat’s lemma for the case {k=2}.

Armed with Theorem 4, Theorem 1 is quite obvious.

There is also a nice variant for invariable generation. Cheers to Daniele Garzoni for pointing this out to me. Recall that elements {g_1, \dots, g_d} of a group {G} are said to invariably generate if {g_1', \dots, g'_d} generate whenever {g_i'} is conjugate to {g_i} for each {i}. (So invariable generation is really better thought of as a property of conjugacy classes rather than elements.) Then, with the setup as in Theorem 4, {s_1, \dots, s_d} invariably generate {G} if and only if

  1. {t_{1j}, \dots, t_{dj}} invariably generate {T} for each {j}, and
  2. {(t_{1j}^G, \dots, t_{dj}^G)} are in different {\textup{Aut}\, T}-orbits for each {j}.

Note that {\textup{Aut}\, T} really does act on the set of conjugacy classes, so point 2 makes sense. It follows that the largest {h} such that {T^h} is invariably {d}-generated is equal to the number of {\textup{Aut}\, T}-orbits of {d}-tuples of invariably generating conjugacy classes. But sadly this doesn’t lead to as nice a formula as in Theorem 1, because this action is not fixed-point-free (it is possible for an automorphism to preserve the conjugacy class of each generator without preserving all conjugacy classes).

Probability that two permutations have the same order

What is the probability {p(n)} that two random permutations {\pi_1, \pi_2 \in S_n} have the same order? That is the question asked by this MathOverflow question from 2016, and considered again in this paper of Acan, Burnette, Schmutz, and Thomas from last month. It’s an innocuous-sounding question that turns out to encapsulate some rather subtle analytic combinatorics.

You haven’t got started until you realize {p(n) \geq 1/n^2}: this is the probability that both {\pi_1} and {\pi_2} are {n}-cycles. In fact since {\pi_1} and {\pi_2} have the same order whenever they are conjugate, we can say

\displaystyle  \mathbf{P}(\textup{ord}(\pi_1) = \textup{ord}(\pi_2)) \geq \mathbf{P}(\pi_1 \sim \pi_2).

This latter probability gets a significant contribution from every conjugacy class {\mathfrak{c}} which is a nearly an {n}-cycle, specifically which contains an {(n-k)}-cycle for {k=O(1)}. Suppose {\mathfrak{c}} consists of an {(n-k)}-cycle as well as {c_j} cycles of length {j} for each {j\geq 0}, where {\sum j c_j = k}. Then the probability that {\pi_1, \pi_2 \in \mathfrak{c}} is

\displaystyle  \frac1{(n-k)^2} \prod_{j\geq 0} \left( \frac1{j^{c_j} c_j!} \right)^2 \sim \frac1{n^2} \prod_{j\geq 0} \left( \frac1{j^{c_j} c_j!}\right)^2.

If we sum this over all choices of {k} and {(c_j)}, we get {\Delta / n^2}, where

\displaystyle  \Delta = \exp \sum_{j \geq 0} \frac1{j^{2c} c!^2} = 4.26\dots,

and it’s not too hard to see that all other conjugacy classes contribute negligibly. As far as I know this asymptotic was original observed by Flajolet, Fusy, Gourdon, Panario, and Pouyanne (see Proposition 4).

This isn’t the full story for {p(n)}, since there are pairs of different conjugacy classes which contribute significantly, such as the cycle types {(n-2, 2)} and {(n-2, 1, 1)} if {n} is even, or {(n-3, 2, 1)} and {(n-3, 1, 1, 1)} if {n} is odd. It’s also clear from this example that the arithmetic of {n} is now relevant. But at least a natural approach is suggested.

Assume that the main contribution comes from conjugacy classes of the shape {(n-k, \lambda)}, where {k=O(1)} and {\lambda} is a partition of {k}. The order is given by

\displaystyle  \textup{lcm}(n-k, \textup{lcm}(\lambda)) = \frac{\textup{lcm}(\lambda)}{\textup{gcd}(\textup{lcm}(\lambda), n-k)} \times (n-k).

Now as long as {k} is bounded, the only way we can get a collision between two of these is if the two factors separated by {\times} collide separately. If we sum over such colliding pairs, we should get a rather complicated arithmetical almost-periodic function of {n}, but at least one we can try to understand with a computer.

But if you do this, a rather strange picture develops. Counting only those conjugacy classes with {k\leq 50}, we get the following picture.

Notice the drop at exactly {n=50}, where we arbitrarily decided to limit {k}. What this is saying is that our assumption, that the main contribution comes from {k=O(1)}, was faulty.

After thinking further along these lines I contributed an answer to the MO question which proves that {p(n)} is infinitely often at least roughly {\log^*(n)/n^2}, and in particular {\limsup p(n) n^2 = \infty}. But it really looks like there is more to understand here. Even though the {n} in my MO answer are very particular, and the lower bound very weak, I’m still tempted to conjecture that {\liminf p(n) n^2 = \infty}. And it would be nice to know the true order of magnitude!

In case anybody wants to reproduce or extend my calculations, here is my colab notebook.