Induction for finite groups

This is a survey article related to:finite groups
View other survey articles about finite 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.

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

=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 ⟹ 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, then that's good.

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.