Induction for finite groups

This page is a survey article about a proof method or constellation of methods commonly used in group theory. The method is sufficiently vague that it cannot be classed as a "fact" or abstracted into a "theorem" but sufficiently precise that we can still make reasonably unambiguous identifications of proofs that use the method. It builds on the paradigm of the principle of mathematical induction.
View other survey articles about proof methods|View survey articles about proof methods that build on the principle of mathematical induction

YOU MAY ALSO BE INTERESTED IN: Induction for groups of prime power order, induction for subgroups of finite groups, induction for finite solvable groups

Induction for finite groups is a general method, or collection of methods, aimed to prove that a certain result holds true for all finite groups (or for an infinite collection of finite groups). While this uses the same principle of mathematical induction that characterizes the usual application of induction, the way the principle is applied is somewhat difference.

The method we describe here, which we call the minimal counterexample method, is the most convenient way of formulating an induction argument for finite groups.

Avoid proofs by induction

Indication that a proof by induction may be needed

Proofs by induction should generally be used only as a last resort, after all direct reasoning has failed. Some indicators that a proof by induction might be needed:

The statement itself uses the language of finiteness, by talking about the orders and indices, or about divisors of these numbers.
There is no intrinsic or direct proof.
The result fails for infinite groups, and does not seem to have an obvious analogue for infinite groups.
The result requires one or more constructive choices.

Before starting on the induction

Before starting a proof by induction, it is good to attempt a number of easy cases through direct proofs. This helps in two ways:

In some situations, it turns out that a proof by induction is unnecessary.
In other situations, the easy cases suggest an appropriate parameter of induction.

After succeeding in the proof

After completing the proof by induction, it is good to review the proof to see if induction can be eliminated from it. In some cases, this may require proving other results that are not naturally suggested initially. Those results may in turn use induction, but in a less noticeable way.

The minimal counterexample approach: getting started

The meaning of minimal

When proving results for finite groups by induction, we usually start by assuming a minimal counterexample. The term minimal needs to be qualified here:

In its most naive interpretation, it means a counterexample of minimum possible order.
A somewhat more sophisticated interpretation is: a counterexample such that no proper subgroup (resp. quotient group or subquotient) is a counterexample. In other words, the counterexample is minimal even though it may not have the minimum possible order. Of course, any counterexample of minimum possible order is minimal in this sense.

Since we often do not a priori know whether we'd be required to induct using subgroups, quotients, or subquotients, it makes sense to use the naive interpretation when attempting a proof.

More refined choices of minimal

There are situations where we may use other numerical invariants associated with groups as the parameter for induction, and accordingly, change the definition of minimal. Here are some possibilities:

exponent: This is the least common multiple of the orders of all elements in the group.
Number of prime divisors of the order.
Nilpotence class for a nilpotent group, or solvable length for a solvable group.
Frattini length: The length of the Frattini series.
Composition length: The length of the composition series.

Many of the proofs that induct on these, however, can also be written in the form of a proof that inducts on order, because we usually apply the induction hypothesis only for proper subgroups and quotients of the group, which have smaller order.

=Placing constraints

For proving a tautology

Having assumed the existence of a minimal counterexample, we try to derive a contradiction. We need to use the fact that every group of strictly smaller order is not a counterexample, i.e., it satisfies the hypotheses.

Here is a typical setup. Suppose we need to show that a group property $p$ is satisfied by all finite groups. We check the following:

Suppose $p$ is extension-closed i.e., that the extension of any group with property $p$ also has property $p$ . Then, it is clear that any minimal counterexample must be a simple group (because otherwise, we'd have a normal subgroup and a quotient group, both satisfying property $p$ , and we'd be done). This significantly restricts the possibilities for the minimal counterexample, and we can now use techniques and strategies specifically suited to simple groups.

Suppose $p$ is a finite normal join-closed i.e. any finite join of normal subgroups satisfying property $p$ , also satisfies property $p$ . Then, any minimal counterexample cannot be generated by smaller normal subgroups. This tells us that the group is a one-headed group: it has a unique maximal normal subgroup. The condition isn't as restrictive as being simple, but is still fairly strong.

In other words, we use the group metaproperties satisfied by $p$ to place constraints on the nature of a minimal counterexample.

For proving an implication

We may need to prove an implication between two group properties, say $q\implies p$ , where $p$ and $q$ are properties that can be evaluated for finite groups. The idea here is similar to the previous one, but now we ned to take into account the group metaproperties of both $p$ and $q$ . For instance:

Suppose $q$ is closed under taking subgroups and quotients, and $p$ is extension-closed. Then any minimal counterexample is simple.

This is a typical approach in induction for finite solvable groups. For instance, to prove that any odd-order group is solvable, we observe that the property of having odd order is closed under taking subquotients, and the property of being solvable is closed under taking extensions, so any minimal counterexample must be simple.

Suppose $p$ is extension-closed. Then, we may be able to make do with something weaker than saying that $q$ is closed under taking subgroups and quotients. Namely, all we need to do is to show that for any group with property $q$ , there exists a normal subgroup such that both the subgroup and the quotient have property $q$ . This may be much more achievable than showing that every subgroup and quotient of a group with property $q$ has property $q$ . This approach is used in proving the famous Hall's theorem which asserts that the existence of a normal p-complement for every prime divisor of the order of the group, implies that the group is solvable.

Deriving the contradiction

Once we have an initial set of constraints on a minimal counterexample, the further work is largely to keep deriving more and more constraints, making the minimal counterexample more and more unlikely. This often requires a study of the internal structure of a minimal counterexample, and may require the development of a lot of theory and language. This, for instance, is how Feit and Thompson proved the celebrated odd-order theorem.

Avoiding contradiction: a direct proof method

In some cases, we can prove without using the language of minimal counterexamples: we assume that all subquotients satisfy the property, and use this to show that the group satisfies the property. However, starting out with the minimal counterexample method does not hurt because any proof that can be obtained avoiding the minimal counterexample method, can also be obtained with it. If, after completing the proof, one realizes that one can present it in a direct manner, the presentation of the proof can be accordingly altered.

However, many of the intricate statements about group theory, like the odd-order theorem, do require a fairly intricate study and understanding of the minimal counterexamples which do not exist. Proceeding forward does not yield the same freedom and creativity that one can use once one assumes a minimal counterexample.

Pivotal results for an induction

One of the key skills in proofs by induction is to identify key facts that could form both either the induction base or help in the induction step. This section discusses possibilities in that direction.

Small normal subgroups and inducting by passing to the quotient

There may be results of the form: there exists a nontrivial normal subgroup satisfying certain conditions, and these results might help kickstart the proof by induction, by allowing us to examine the normal subgroup and the quotient group and use the induction hypothesis. Here are some examples:

For a nilpotent group, specifically a group of prime power order, the center is nontrivial. Statements about groups of prime power order are often proved using the center: we use the fact that the result holds for the quotient by the center to prove that the result holds for the whole group. This amounts to an induction based on nilpotence class.
For a solvable group, there are many different starting points. For results of an arithmetic nature, a typical starting point is that there exists an elementary Abelian normal subgroup: in particular, this normal subgroup is a $p$ -subgroup. For other results, it may be helpful to use that there exists an Abelian characteristic subgroup, or an elementary Abelian characteristic subgroup.
For a supersolvable group, the fact that there exists an Abelian normal subgroup properly containing the center is a useful starting point. Actually, more is true: maximal among Abelian normal implies self-centralizing in supersolvable.

Huge subgroups

There may be results of the form: there exists a proper subgroup satisfying certain conditions, and these results might help kickstart the induction, by allowing us to prove the result for the whole group using the assumed result for the subgroup by the induction hypothesis.