Sylow’s Theorem, from the book

The most important theorems of elementary group theory are those of Lagrange and Sylow. I want to describe here what I consider the most beautiful proof of the first part of Sylow’s Theorem, actually based on Sylow’s original proof. But first, some preliminaries.

Lagrange’s Theorem states that the order of a subgroup of the group G divides the order of G. This is closely connected with the theory of group actions, which is crucial to the modern way of looking at these results. If H is a subgroup of G, then G acts transitively on the set of right cosets of H by right multiplication, and every transitive action of G is of this form. So all that is required is to observe that all right cosets of H have the same cardinality, which is true because the map taking h to hx is a bijection from H to Hx. We learn additionally that the quotient |G|/|H| is equal to the size of a set on which G acts transitively.

The converse of this theorem is usually taken to be the assertion that, if n and m are positive integers such that m divides n, then a group of order n has a subgroup of order m. Of course things are not so simple. The smallest counterexample is the alternating group on 4 letters, which has order 12 but has no subgroup of order 6.

Sylow showed that this converse does hold in a special case, namely that when m is a prime power. His theorem is traditionally stated with four parts. Suppose that G is a finite group, and p a prime. We call a subgroup H of G a Sylow p-subgroup if the order of H is the p-part of the order of G, that is, the largest power of p dividing |G|. Now Sylow’s theorem states that Sylow subgroups exist for all choices of G and p; that they are all conjugate in G; that the number of Sylow p-subgroups is congruent to 1 (mod p); and that any subgroup of G of p-power order is contained in a Sylow p-subgroup. A very satisfactory state of affairs!

There are several very different proofs of the first part of the theorem; I will give my favourite shortly. But the other three parts are proved by very similar arguments, and almost no alternative approach to them is known. I outline the proof. It depends on the following claim:

Let P be a Sylow p-subgroup of G, and Q a p-subgroup normalising P. Then Q is contained in P.

For the assumption implies that PQ is a subgroup; its order is |P|.|Q|/|PQ| by a standard formula, so it is a p-group. By Lagrange’s Theorem its order is equal to that of P, so it is equal to P, and the claim is proved.

Now, assuming that Sylow p-subgroups exist, we prove the remaining parts of Sylow’s Theorem by considering the action of G on the set of all Sylow p-subgroups by conjugation.

We restrict the action to P. It clearly fixes itself, but by the above claim it does not fix any other Sylow p-subgroup. So all the orbits except for {P} have size divisible by p (using our observation on the connectiion between Lagrange’s Theorem and group actions). This shows that the number of Sylow p-subgroups is congruent to 1 (mod p). Moreover, the size of the G-orbit containing P is congruent to 1 (mod p), and the sizes of any other orbits are congruent to 0 (mod p). If Q is any other Sylow subgroup, then Q also lies in the (unique) orbit of size congruent to 1 (mod p); so P and Q are in the same orbit, and so are conjugate. (Incidentally, at this point we know that there is just one orbit.) Finally, if H is any p-subgroup, then restrict the action to H; it must fix a point, that is, normalise a Sylow p-subgroup R (say), and by our claim it is contained in R.

So to the first part of the theorem, the existence of Sylow p-subgroups.

Some time ago, I supervised the MSc project of a student who wanted to read and expound Sylow’s original proof of his theorem. This was non-trivial since three kinds of translation were required:

  • from French to English;
  • from the leisurely 19th century style to the terser modern style;
  • from the language of cosets and double cosets to that of group actions.

On the last point, I mentioned in connection with Lagrange’s Theorem that cosets are connected with group actions. It turns out that double cosets are connected with orbits of a group on ordered pairs of elements.

I am afraid that I don’t now even recall the student’s name, since my files from back then are long since lost. Much credit should go to him, altnough of course the main credit goes to Sylow. I claim a small amount; the very last step in the proof was my idea.

Anyway, here we go. The proof of the existence of Sylow p-subgroups proceeds in three steps.

Step 1: Translation. We show the following:

A group G has a Sylow p-subgroup if and only if it has a transitive action on a set X, such that the size of X is coprime to p but the order of any point stabiliser is a power of p.

If P is a Sylow p-subgroup, then the action on the cosets of P has the required property. In the other direction, given such an action, the point stabiliser is a Sylow p-subgroup, since its order is a p-power and its index is coprime to p.

Step 2: The heart of the proof. We show the following:

Suppose that G has a Sylow p-subgroup. Then any subgroup of G has a Sylow p-subgroup.

Take an action of G satisfying the conditions of Step 1. Let H be a subgroup of G, and restrict the action to H. Clearly the number of points is still coprime to p and the orders of the point stabilisers are p-powers. The small difficulty is that the action may not be transitive. But at least some orbit has size coprime to p, since if all sizes were divisible by p then their sum would be as well. Now the action of H on this orbit gives the required conclusion.

Step 3: Conclusion.

Given an arbitrary group, all we have to do is to embed it in a group which has a Sylow p-subgroup.

The first candidate, if you have seen Cayley’s theorem, is a symmetric group. (Cayley’s Theorem asserts that a group of order n is isomorphic to a subgroup of the symmetric group Sn.) It is possible to construct with bare hands a Sylow p-subgroup of Sn. (Write n in base p; the required subgroup is constructed as a direct product of wreath products of copies of the cyclic group of order p.)

But there is an easier way. For any field F, the symmetric group Sn is embeddable in the group GL(n,F) of invertible n×n matrices over F: just take all the permutation matrices, the matrices with entries 0 and 1 having a single 1 in any row or column. Now take F to be the field of integers mod p. A short calculation shows that its order is

(pn−1)(pnp)…(pnpn−1),

and so the exponent of p in its p-part is

0+1+…+(n−1) = n(n−1)/2.

Now consider the group of upper unitriangular matrices (1 on the diagonal, 0 below, and arbitrary entries above). The number in the last display is just the number of arbitrary entries; so the order of this group is the p-part of the order of the general linear group.

We are done.

Posted in exposition | Tagged | Leave a comment

Some good news among the gloom

The University of St Andrews has signed up to DORA, a mere seven years after the declaration was drawn up.

We are committed to fair assessment of research rather than reliance on bibliometrics.

Posted in Uncategorized | Tagged , , | Leave a comment

Not dark yet

I had a bit of a shock this morning, when David Wallace sent sincere condolences to Rosemary.

The December issue of the IMA magazine Mathematics Today records the death of Peter Cameron. But, I am afraid, it is not me.

Posted in Uncategorized | Tagged , | Leave a comment

Election musings

We have a general election in just over a week, the third in less than five years.

Like every election, there are multiple issues. I recommend Diamond Geezer’s post today on the Conservative manifesto; he has heroically read the whole thing and discovered some rather disturbing promises buried at the back. But in this post (I don’t usually do politics so I will be very circumscribed) I will pretend that there is just one thing (or possibly two things) on our mind: Brexit, and a second Scottish Independence Referendum (Indyref2).

Here is how the parties stand.

  • Conservative: Brexit YES, Indyref2 NO.
  • Labour: undecided (but they could be persuaded to support Indyref2 if it would get their leader into Downing Street)
  • Liberal Democrat: Brexit NO, Indyref2 NO.
  • Scottish National Party: Brexit NO, Indyref2 YES.

There is no need to consider others, since we have candidates only from these parties standing here.

In our constituency, North-East Fife, fortunately, the party led by the lying hypocrite and the party led by the indecisive bully seem to have very little chance of getting in, so it is between the LibDems and the SNP. So, under our blanket assumption, my view on Indyref2 should be decisive.

But two things complicate matters.

First, one’s attitude to Indyref2 depends very much on whether and how Brexit happens. If the UK leaves the EU, the best thing for Scotland might be to leave the UK and rejoin the EU; but of course this might mean that Hadrian’s Wall might have to be re-fortified …

Second, and possibly more relevant. The SNP push No Brexit very hard in their campaign literature, but say less about Indyref2 (though it is clear in their leader’s pronouncements). For example,

It is important to remember that Scotland, and North-East Fife in particular, voted decisively to remain in the European Union. It is also important to forget that Scotland, and North-East Fife in particular, voted decisively to remain in the United Kingdom.

Actually they didn’t say that. The first sentence is in their campaign literature, while the second was written by me but seems a fairly clear reflection of the statements made by their leader.

Our current MP, Stephen Gethins, who won by two votes at the third recount in hte last election, is a very good constituency member. But it is worrying that he signs up for this small hypocrisy.

Posted in Uncategorized | Tagged , | 1 Comment

Alex Craik

Last month saw the death of Alex Craik, emeritus professor of mathematics at St Andrews. He spent most of his career here, working on fluid dynamics, and (latterly) on History of Mathematics.

I didn’t know him very well, though he came in to the School from time to time, and had spoken at various events including Research Days.

But what I will mainly remember him for is a paper in the American Mathematical Monthly 112 (2005), 119-130, entitled “Prehistory of Faà di Bruno’s formula”.

This formula gives the nth derivative of a composite function f(g(x)), in an analogous way to Leibniz’s formula for the nth derivative of a product. It is particularly relevant to discrete mathematics, for two reasons: first, it applies to general formal power series over commutative rings with identity, no issues of convergence need to be considered; and second, the coefficients that arise are slightly disguised Stirling numbers (much as Leibniz’s formula involves binomial coefficients).

Francesco Faà di Bruno (1825-1888) is perhaps the only mathematician to be also a Roman Catholic saint. He was a student of Cauchy and friend of Hermite. He returned to Turin and devoted himself to work among the poor, for which he was canonised in 1988.

In his paper, Alex Craik describes several authors who had anticipated the formula to varying extents, and awards the palm of discovery to Arbogast in 1800. I recommend the paper to you.

However, even if Faà di Bruno was not the first to come up with it, it seems that his contribution was sufficient that the naming is not entirely unjust.

Rest in peace, Alex, and thank you for this insight.

Posted in history | Tagged , , | Leave a comment

Something I didn’t know

I didn’t know this, though probably I should have. Maybe you didn’t know it either.

We work in a semigroup, a system with an operation (called multiplication) satisfying the associative law. A generalised inverse of an element A is an element B satisfying ABA = A. The name comes from the fact that, if there is an identity element I, then an inverse of A (an element B satisfying AB = I) is a generalised inverse.

If a generalised inverse B of A exists, then we may assume that A is also a generalised inverse of B, that is, BAB = B. To see this, put C = BAB. Then

  • ACA = ABABA = ABA = A,
  • CAC = BABABAB = BABAB = BAB = C.

So C is also a generalised inverse of A and has the required property.

Now we come to the bit that I didn’t know. Let us consider matrices, over an arbitrary field. The following two theorems hold:

Theorem 1 Every matrix has a generalised inverse.

For let A be a matrix. Choose vectors v1,…,vr spanning the image of A, and let w1,…,wr be preimages of v1,…,vr. Choose B mapping vi to wi for i = 1,…,r. Then ABA = A.

Theorem 2 For a matrix A, the following are equivalent:

  1. A has a generalised inverse which commutes with A;
  2. A has a generalised inverse which is a polynomial in A;
  3. 0 is not a repeated root of the minimal polynomial of A.

Here is the proof.

2 implies 1: Clear.

3 implies 2: Suppose that 0 is not a repeated root of the minimal polynomial of A. Then there is a polynomial f with zero constant term and non-zero coefficient of x which is satisfied by A. (If 0 is a root of the minimal polynomial, use this; otherwise use the minimal polynomial multiplied by x.) After multiplying by a non-zero scalar we can write f(x) = xx2h(x). Then h(A) is a generalised inverse of A.

1 implies 3: Suppose that ABA = A and AB = BA. Then BA2 = A. But, if 0 is a repeated root of the minimal polynomial of A, then there is a vector v which is mapped to 0 by A2 but not by A, and applying the above equation to v gives a contradiction.

Corollary If a matrix A is diagonalisable, then it has a generalised inverse which is a polynomial in A. In particular, this holds for real symmetric matrices.

Posted in exposition | Tagged , , , , | 4 Comments

The Wall conjecture extended

Tim Wall boldly conjectured in 1961 that the number of maximal subgroups of a finite group G is at most |G|−1. (This would be best possible, since the the elementary abelian 2-group attains this bound.) He proved that the conjecture holds if G is soluble. The conjecture itself was disproved by participants in an AIM workshop in 2012, but in the meantime, Martin Liebeck, Laci Pyber and Aner Shalev had proved that the number of maximal subgroups is at most c|G|3/2. (The report of the workshop notes that the counterexamples have order smaller than |G|1+a, where a < 1/1000 (and possibly much smaller).)

The partition into right cosets of a subgroup of a group G is a system of imprimitivity for G in its regular action on itself by right multiplication, and in particular, maximal subgroups correspond to systems of maximal blocks. So, in our work on the Road Closure conjecture (described here), João Araújo and I speculated that the results on Wall’s conjecture might extend to the number of systems of maximal blocks of imprimitivity for all finite transitive permutation groups.

This did indeed turn out to be the case. Mariapia Moscatiello from Padova, who is visiting our department this month, gave a seminar talk on Wednesday, in which she showed that exactly the same bounds (cn3/2 for arbitrary transitive groups of degree n, and n−1 for finite soluble groups) hold for the more general problem. This lovely result is joint work with Andrea Lucchini and Pablo Spiga. Their paper is on the arXiv: 1907.08477.

So one (rather important) question remains. Is there an efficient algorithm to find all the maximal blocks through a point in a transitive permutation group? In particular, can this be done in polynomial time? An efficient algorithm would almost certainly allow us to push further with our computational test of the Road Closure conjecture. In the computation as we have done it so far, we use the fact that all the minimal blocks through a point can be found efficiently, and then climb up to the top of chains of blocks; this is very inefficient since we pass all possible blocks on the way and there may be very many of these!

Posted in exposition | Tagged , , | Leave a comment

A challenge

Let a(n) be defined in the following manner. Write n as an ordered sum of positive integers in all possible ways. (The number of such expressions is 2n−1; showing this is a pleasant exercise, but it is not relevant for what follows.) For each expression, multiply the summands together; then add the resulting products. So, for example,

3 = 2+1 = 1+2 = 1+1+1,

so

a(3) = 3+2.1+1.2+1.1.1 = 8.

Now the values a(1) = 1, a(2) = 3, a(3) = 8, … are alternate Fibonacci numbers.

This is an exercise, not a research problem. Try it for yourself before reading on. [According to Donald Knuth, Richard Bellman included a section called “Exercises and Research Problems” at the end of some chapters of his book Dynamic Programming. When asked how you tell the difference, he replied, “If you can solve it, it is an exercise; otherwise it’s a research problem.”]

I give a proof below, using formal power series. The challenge is to find a more direct proof. This would preferably consist of matching up the values with some known description of Fibonacci numbers (such as the number of binary sequences of length n without consecutive ones, or of expressions for n as a sum of ones and twos). Failing that, proving directly that the numbers a(n) satisfy the same recurrence relation as the alternate Fibonacci numbers (see below).

Here is the proof. It uses an auxiliary power series

F(x) = x+2x2+3x3+…

(the general term is nxn). Using the Binomial Theorem, or by any of various direct arguments, show that F(x) = x/(1−x)2.

The coefficient of xn in F(x) is n, which corresponds to our prescription for a(n) but with just one term in the sum.

Now the coefficient of xn in F(x)2 is the sum of all products kl, where k and l are positive integers summing to n; in other words, our prescription for a(n) but with just two terms in the sum. Similarly the coefficient of xn in F(x)3 corresponds to taking three terms in the sum, and so on.

So, if A(x) is the generating function for the sequence (a(n)), then we have

A(x) = F(x)+F(x)2+F(x)3+… = F(x)/(1−F(x)).

Substituting in our formula for F(x), we find that

A(x) = x/(1−3x+x2).

This shows that the sequence (a(n)) satisfies the recurrence

a(n) = 3a(n−1)-a(n−2),

which is the same as the recurrence for alternate Fibonacci numbers. Using the initial values, it is now immediate to get the result.

This post is the result of my having set this problem to my students, and then realising that I had forgotten how to do it myself.

Posted in exposition | Tagged , | 11 Comments

Very good news!

Cheryl Praeger has been awarded the Australian Prime Minister’s Prize for Science. Here is an announcement on the ABC website.

Congratulations Cheryl!

And my thanks to Liz for sending me the news.

Posted in Uncategorized | Tagged , | 1 Comment

Ginger Baker

At my age, it very often happens that someone who was part of the background of my younger self dies. Yesterday it was Ginger Baker.

The obituary said more about his extraordinary life and his short temper than his drumming, and quoted him as saying that a drummer was no more than a timekeeper. Yet he was one who could really make music with a drumkit.

There was another side of him which they didn’t touch on at all. You will see this if you listen to his song “East Timor”. A passionate denunciation of the hypocrisy of governments who will sell out a small community for money, it is a song with huge contemporary relevance. And after the vocal section and a very mathematical bridge, his colleagues Charlie Haden and Bill Frisell do a very convincing take-off of Jack Bruce and Eric Clapton. Close your eyes and you could be listening to Cream in their heyday.

Posted in Uncategorized | Tagged , , , | Leave a comment