Finite simple groups

The blog Gödel’s Last Letter and P=NP is always worth reading. The two bloggers, RJ Lipton and KW Regan, are computer scientists, but they have interesting things to say about developments in mathematics, and other areas too. For example, last year they reported about Shinichi Mochizuki’s claimed proof of the ABC conjecture.

They make end-of-year predictions, and are not afraid to stick their necks out (sometimes resorting to the technique of predicting two apparently contradictory things, such as the appearance of strong evidence both for and against P=NP).

One of this year’s twelve predictions reads:

4. A new simple group will be discovered. By the classification theorem, such a group should be infinite, but will not be.

A good opportunity for me to say a word or two about the finite simple groups and their classification.

The finite simple groups

I expect that most people reading this know what a group is. A subgroup is a subset of a group which is a group in its own right; it is a normal subgroup if its left and right cosets coincide.

I don’t actually think that is the right definition of a normal subgroup. You can’t do algebra without the notion of a homomorphism, a map between structures which preserves the operations which give them their structure. So a group homomorphism is a map between groups that preserves the group operation. Now its kernel is the set of elements of the source group which map to the identity in the target group. A normal subgroup is the kernel of a homomorphism. (You need to prove that it really is a subgroup!

The Cayley table of a group is a Latin square. If the first k rows and columns of the Cayley table of a group form a Latin square in their own right, then the first k elements of the group form a subgroup. If the stronger condition holds that, when the square is partitioned into k×k subsquares, then each of them is a Latin square, then we have a normal subgroup.

This observation makes clear that a group with a normal subgroup is “built up” out of the subgroup and the factor group, where we replace each of the k×k subsquares by a single symbol, depending on which symbols occur in the subsquare.

This focuses attention on the simple groups, those which don’t have any normal subgroups except the trivial ones (the whole group and the singleton containing the identity element).

The cyclic group of prime order is simple (an easy consequence of Lagrange’s Theorem). If there were no others, then group theory would be an easier subject: all groups would be soluble. And the theory of polynomial equations would be an easier subject: any equation would be soluble by radicals. But it isn’t so, of course.

A classification

We would like to have a list of all the finite simple groups, containing each simple group (up to isomorphism) just once. What should such a list look like?

First let us observe that there is no logical objection to producing such a list. In principle, a computer could check all the n×n Cayley tables, to decide which of them are groups, and which of these groups are simple. This will generate a list. Thus, the finite simple groups (coded in some way) are recursive.

But there is no logical reason why there should be a human-friendly list. If there is, what might it look like?

Consider the (much easier) classification problem of indecomposable root systems with all roots of the same length, which I have discussed at length in a series of posts. There are two infinite families, An and Dn. and three “sporadic” examples, E6, E7 and E8. Similarly, the classification of the finite rotation groups in three dimensions yields two infinite families (cyclic and dihedral groups) and three “sporadic” examples, the rotation groups of the tetrahedron, octahedron and icosahedron. These problems turn out to be very closely connected!

So maybe the simple groups fall into a number of infinite families (each member of a family characterised by some parameters) and a number of sporadic examples. Of course, even with this pattern, there is no guarantee that there are only finitely many sporadic groups: maybe there are larger and larger groups, each depending on a collection of group-theoretic or number-theoretic accidents, and each requiring a separate construction.

The classification theorem

Fortunately, that is not how things turned out.

The Classification of Finite Simple Groups (CFSG to its friends) asserts that a finite simple group is one of the following:

  • A cyclic group of prime order.
  • An alternating group An for n ≥ 5, the group of even permutations of {1,2,…n}.
  • A group of Lie type; these are more-or-less matrix groups, and fall into a finite number of families. Some of the families require a dimension and a field order to be given to specify the group (for example, the group PSL(n,q) consists of the n×n matrices over the field of order q modulo scalar matrices); the others require just a field order, which is itself sometimes restricted (for example, Sz(q), the Suzuki group, where q must be an odd power of 2).
  • One of twenty-six sporadic groups.

The theorem has a chequered history. The mastermind behind the project to classify the finite simple groups was Daniel Gorenstein; he announced in the early 1980s that the project was complete apart from a small amount of tidying up (proving the uniqueness of J4, and showing that “groups of Ree type” were actually Ree groups). These details were indeed completed soon afterwards.

But there was a more serious problem. The last big step in the proof was the classification of “quasithin groups”, which was supposed to have been done by Geoff Mason. It turned out that Mason hadn’t finished the job, and had gone on to other things and was unwilling to be lured back. By this time, it was also clear that the precise definition of “quasithin groups” had been changed slightly, and the classification had to be done with the new definition.

After some time, Michael Aschbacher and Steve Smith stepped up to the plate, and in the mid-2000s published two substantial volumes classifying the quasithin groups. Job done.

But it might be wrong

After Gorenstein’s announcement, it was widely reported that John Conway had said, “If you find a new finite simple group, keep it in your desk drawer until the papers are published, and then bring it out”.

Of course the papers took a quarter of a century to appear; but in the five years or so since then, nobody has brought out a new simple group.

Of course a new simple group would be disastrous for CFSG. But in my view there is a much more likely disaster which could occur. The proof we have certainly contains mistakes. It could happen in the future that some mathematician needing a part of this huge argument looks closely at one small part, and finds a mistake which neither she nor anyone else can put right, since the incredible expertise of Michael Aschbacher and others has been lost.

This could happen if, indeed, now that we have CFSG, everyone who had worked on the programme left to do something else.

Fortunately that has not been the case.

CFSG is a very useful theorem, but applying it is a completely different skill from proving it, so the army of mathematicians using it will not contribute much to fixing the hole (though they might well include the people that find it). But there are two camps of people still working on CFSG:

  • The “revisionists”, trying to find a better proof, for example replacing some of the original arguments by others based on amalgam techniques.
  • Researchers on groups of finite Morley rank. Simple groups of this type are conjectured to be algebraic groups over algebraically closed fields, with no “sporadic” groups; but the techniques used in trying to prove this conjecture can be characterized, crudely, as taking techniques from the proof of CFSG and adapting them to the new situation.

These groups should at least provide some expertise if a mistake is found in the proof of CFSG in the not-too-distant future.

Finally …

The result which first suggested that the classification of the finite simple groups might be doable was probably the Feit–Thompson Theorem, or Odd Order Theorem, which says in effect that no finite simple group can have odd order, apart from cyclic groups of prime order. The proof, published in 1963, was 255 pages long, and took an entire issue of the Pacific Journal of Mathematics. Remarkably, last year saw the announcement of a computer-based verification of the theorem by Georges Gonthier and colleagues at Microsoft Research, using the Coq proof assistant.

The proof of CFSG is between one and two orders of magnitude bigger than the Odd Order Theorem. It is entirely possible that before too long we will have a computer-based verification of CFSG.

Would I bet against Lipton and Regan? Yes, I would; I think the discovery of a serious mistake in the proof is on the cards, but a new group is relatively unlikely.

About these ads

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , . Bookmark the permalink.

2 Responses to Finite simple groups

  1. Walter Bruce Sinclair says:

    This is an intriguing point of view. And just what would be the probability that you actually have a proof in place? Then set against that the probability that a counterexample will ever be found. As the poet could have said: between theorem and proof, there falls a shadow.

  2. rjlipton says:

    Thanks for kind comments about our blog.

    On Feit-Thompson I have had a long dream that I still think could happen. The dream is that computer theory could lead to an alternative proof. The idea is: Suppose there is an odd simple group. Then use that to show that certain circuits exists that we believe should not—this involves constant depth circuits. Then prove a complexity lower bound that this is a contradiction. I can say more, but it remains a distant dream.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s