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:

There is an automorphism ${\alpha \in \textup{Aut}\, G}$ such that ${f_1 = \alpha f_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

${\langle t_{1j}, \dots, t_{dj}\rangle = T}$ for each ${j}$ , and
${(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

${t_{1j}, \dots, t_{dj}}$ invariably generate ${T}$ for each ${j}$ , and
${(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).

Generating direct powers of a simple group

Published by Sean Eberhard

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Sean Eberhard

Leave a Reply Cancel reply