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