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).

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 )

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