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