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