**Question:** What is the largest such that the direct product

of copies of the alternating group is -generated?

This is the sort of question which somebody with little experience of nonabelian groups might get very wrong: such a person might guess by analogy with linear algebra. Here’s a rough-and-ready construction that shows how wrong that logic is. Assume is odd, for simplicity, and write for the odd primes less than . Let be some -cycle, for each let be a -cycle, and let

Then for each there is some such that

Clearly then is a subgroup of

surjecting onto the factor. Since is perfect (meaning ) we can now use commutators to isolate the factor, and generation is proved. This shows that the answer to our initial question is at least .

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 be a finite group, let be the largest such that is -generated, and let be the number of -tuples such that . If is nonabelian simple then *

*
** *

The notation is Hall’s, motivated by the connection with Euler’s phi function from number theory:

For this reason, is occasionally referred to as the *Euler–Hall* function of . Like , has summatory rule:

This can be used to calculate for any group whose subgroup lattice is well understood.

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

expecting this to be close to whenever . This is the case for , for example. Since for , we have our answer to our initial question:

Compared to our earlier lower bound of , this is monstrous!

The proof of Theorem 1 is not hard, but it requires a little mental gymnastics. Write for the set of generating -tuples, so that . There is an obvious action of on , 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 as the set of surjections from the free group to . In this view, the action of is that of post-composition.

**Lemma 2** * Let and be groups, and let be surjections. Then the following are equivalent: *

*
*
- There is an automorphism such that .
- .

* *

*Proof:* Obviously 1 implies 2. If 2 holds then descend to isomorphisms , where is the common kernel, and is readily obtained.

Thus the orbits of on are in bijection with the subgroups such that . Therefore the number of such subgroups is precisely .

Let be the set of all such subgroups . Clearly we have an injection

If is a surjection, then contains , so factors through , so . The proof is therefore concluded by the following lemma.

**Lemma 3** * Assume is nonabelian simple. Then the map *

*
** is surjective. *

*Proof:* Write . We will prove by induction on that

is surjective. The case is trivial. The case follows easily from Goursat’s lemma. For , we know by induction that for all

the image in contains points of the form

Taking commutators and using , we see that the image contains the subgroup . Similarly, the image contains . Therefore the image is .

Let’s close with a simple puzzle. In Theorem 1 we assumed that is simple. What about, say, ? Prove that .

**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 be a nonabelian simple group, and let be candidate generators of . Write for each , and consider the matrix matrix *

*
* Then generate if and only if

- for each , and
- are in different -orbits for each .

* *

The conditions are clearly necessary: 1 is necessary lest the projection of onto the th factor not be surjective, and 2 is necessary lest be trapped in the subgroup of defined by for some and some .

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

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 of a group are said to *invariably generate* if generate whenever is conjugate to for each . (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, invariably generate if and only if

- invariably generate for each , and
- are in different -orbits for each .

Note that really does act on the set of conjugacy classes, so point 2 makes sense. It follows that the largest such that is invariably -generated is equal to the number of -orbits of -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).