I have a confession to make. When I was an undergraduate at Cambridge (hmm, that sounds as though it might be the beginning of quite an interesting confession, so I’d better forestall any disappointment by saying right now that it isn’t), there was a third-year course in group theory, taught by John Thompson no less, on which I did not do very well. For a few weeks it seemed to cover material that we’d done in our first year, and then suddenly it got serious, with things like the Sylow theorems. And at that point I got lost, and was unable to do the questions on the examples sheets. I can’t remember much about the questions, but I think my difficulty was that there was a slightly indirect style of proof that caused me to find arguments hard to remember and even harder to come up with. And I never got round to doing anything about it: I went into a different area of maths, and even now I don’t know the proofs of the Sylow theorems. In fact, I don’t even know the statements, though I know they’re about the existence of subgroups of various cardinalities, and I know that they are proved using cleverly defined group actions. I’ve skim-read the proofs, so I have a fairly good idea of their flavour, but I don’t know the details. In particular, I don’t know which action does the job.
This post is an experiment. I’m going to try to come up with a group action that will tell me about the existence of a subgroup of some given cardinality, and see whether I end up formulating and proving one of the Sylow theorems. And I’ll try to record all my thoughts as I do so. The aim of this is not to give you a nice slick proof of a Sylow theorem — far from it — but to give an idea of how one might search for a group action that achieves some specific purpose.
Perhaps I ought to say more about the Sylow theorems. They are sometimes presented as a kind of converse to Lagrange’s theorem. Lagrange’s theorem tells us that every subgroup of a group has order that divides the order of the whole group. But if we’re given a factor of the order of the group, can we find a subgroup with that order? At least one of Sylow’s theorems tells us that for certain factors we can.
Since that is a (not yet fully worked out) statement about general groups rather than groups that are defined in a particular way, we are not given any external objects on which the group acts. So we can’t define an action in terms of some action that is already around. It would appear therefore that our only choice is to come up with an intrisic action — that is, one that is defined in terms of the group itself. To put that another way, an intrinsic group action is one that you could define for a group about which you know absolutely nothing at all. (Well, that’s not quite true — I’m going to assume that it’s finite.)
Before we go any further, let’s list a few intrinsic group actions. To begin with, let’s think about what actions there are of a group on itself. That is, let’s consider actions where the set on which acts is the set of elements of . A very obvious action is given by left multiplication. That is, if , we define a function by . (If you prefer the product notation you could let and define the action, which is now a function from to , by .)
It doesn’t take much to come up with right multiplication as another action. That is, we can define to be . But is that an action? Let’s check. What is ? It’s . And what is ? It’s . Oops.
What we would really like is to insert that after the and before the . And there is in fact a way of doing that … sort of. We define to be instead. Let’s do the check again. This time, , and . This time it checks out.
And that neatly brings us to a third action, which is where we do the first two at the same time. That is, we define to be . This is the conjugation action of on itself, so called for the obvious reason that is what you get when you conjugate by . (For weeks now I’ve been meaning to write a post on conjugation. I’ll try to get round to it at some point.)
The first two actions aren’t interestingly different, because does to what does to . To put that more precisely, let be the map that takes each element to its inverse. Then is a bijection, and . (Also, as it happens, , but that is not the main point here.)
However, the first action is completely different from the third. For example, for the left-multiplication action, there is precisely one orbit, whereas the orbits of the conjugation action are conjugacy classes. (If this isn’t obvious to you, that can only be because you haven’t properly internalized the definitions. I recommend sitting down to prove it, and after a few seconds you’ll see that when you write down what the orbit of a point is, you have written out the definition of the conjugacy class of that point.)
The left-multiplication action just defined doesn’t feel as though it is going to be all that helpful, because in some sense it just is the group. In fact, if we write it in the product way, then it takes to , so it really is nothing other than the group operation, so any information we can glean from it, we can glean from the group itself. And it’s also hard to see what we can learn from the conjugation action that we couldn’t learn just by talking directly about conjugacy classes.
However, all that changes if we change the set on which these operations act. Instead of taking to be , we can build something else out of . Here are a few examples of actions derived from left multiplication in an obvious way.
1. If we happen to know that has a subgroup , then we can take the obvious left-multiplication action of on the set of all left cosets of . (This isn’t really an intrinsic action in the sense I mean, because is an “external” object.)
2. We could define an action on the set of all ordered pairs of elements of by .
3. We could define an action on the set of all subsets of of size by taking . Here is defined to be .
4. We could define an action on the set of all partitions of into sets of sizes by taking of the partition to be the partition .
One thing I can remember is the proof of Cauchy’s theorem: that if is a prime that divides the order of , then has a subgroup of order . The action there is a bit different, since it’s an action not of but of the cyclic group on a set that is derived from . To be precise, it acts on the set of all -tuples such that , and it acts by cyclically permuting the -tuples. So I’ll have to bear in mind that we may be looking for that kind of action rather than an action of . However, for now let’s press on.
How am I going to be able to use a left-multiplication action of to tell me anything about the existence of a subgroup of some cardinality? Let’s take the cardinality to be .
The one that looks most promising to start with is the action of on the set of all subsets of size , for the simple reason that a subgroup of is in particular a subset of size . Of course, a subgroup isn’t just any old subset of size , but one of a very particular kind. If we want to make progress, we’d ideally like to say what is special about subgroups using concepts like orbits and stabilizers. So let’s begin by thinking about what the orbit of a subgroup looks like when we act on the left.
If is a subgroup, then every set is a left coset of , and one thing we know about left cosets of subgroups is that they partition the group. In terms of orbits, that tells us that the orbit of under the left-multiplication action has cardinality . We also know that the stabilizer of is itself, which of course has cardinality . (Incidentally, the orbit-stabilizer theorem implies Lagrange’s theorem, as these observations show.)
But do these facts distinguish subgroups from other subsets? Might there be a subset of size that is not a subgroup, and yet its orbit has size ?
Oops, that was the wrong question, since could be a left coset of a subgroup. So let’s ask whether has to be a left coset of a subgroup.
It feels very much as though we should use the orbit-stabilizer theorem here. Why? Because to show that something has size looks tricky, whereas to show that something has size , when the object we start with already has size , looks potentially a lot easier.
Because I prefer thinking about subgroups to thinking about left cosets, I’m going to make the additional assumption that contains the identity (so that if it is a left coset then it has to be a subgroup). It should be possible to “translate the whole discussion” later.
If is a set of size that contains the identity, then what can we say about the stabilizer of ? Well, for to belong to the stabilizer of , we need , and in particular, we need to belong to . Therefore, the only possible elements of the stabilizer of are elements of . But do they belong to the stabilizer? Yes, if and only if is closed under left multiplication, which is true if and only if is a subgroup.
How do we “translate that discussion”? Let’s just fix any old element of and call it . Now we can say with complete confidence that if belongs to the stabilizer, then , from which it follows that . For the stabilizer to have size , we therefore need it to equal , so we need the following to be true: if , then .
We’re hoping to show that this implies that for some subgroup , so let’s see what this condition tells us about . If , then , and the condition above tells us that . So is closed under multiplication, just as we wanted.
All this suggests a proof strategy. We could consider the left-multiplication action of on the set of all subsets of of size , and try to show that at least one orbit has size , under appropriate conditions on and , whatever they might turn out to be.
But how are we going to do that? A pretty obvious starting point is that we’ll want to divide , so let’s assume that without further comment.
What else can we say? We know that the orbits form a partition of the collection of subsets of of size , so it might help to know how many of those there are. Indeed, it definitely would, because that would open up the possibility of using the orbit-stabilizer theorem.
Can we say in advance how the orbit-stabilizer theorem might conceivably come in useful? Well, one thing we know is that the stabilizer of a subset is going to be a subgroup of , so its size will be a factor of . This puts a restriction on the possible sizes of the stabilizers, and also, by the orbit-stabilizer theorem, on the possible sizes of the orbits. So perhaps we can argue somehow that in order to get those sizes to add up to the total number of subsets of size we’ve got to have at least some orbits of size .
Of course, the number of sets of size is just , so the real question is whether we can say anything interesting about that number.
Here, I have to admit that I’m drawing on my mathematical experience, and possibly also on dim memories of what the proofs looked like, which result in my strongly expecting that divisibility properties are going to be relevant. You’ll know from Numbers and Sets, for example, that if is a prime and , then is divisible by .
Edit: The next four paragraphs are not very clear and contain at least one false statement. I have written a better account in this comment. Thanks to Joseph for drawing my attention to this, and apologies to anyone else who has struggled with the original version.
That fact can be considerably generalized, so let me pause to discuss it for a while. My favourite proof of the fact itself is one that can be expressed in terms of group actions if you want. Consider the action of the cyclic group on all its subsets of size . For convenience, let’s think of as the group of integers mod under addition. So if is a subset of size , then is . I claim that the stabilizer of is just . Indeed, if is any non-zero element of the stabilizer and , then all of have to belong to , which tells us that is the whole group. But we’re assuming that is non-empty and not equal to the whole group.
What happens if we look at an arbitrary pair of numbers and and try to run the same argument? That is, we consider the left action of on its subsets of size . Let be one of those subsets, and, as before, let be an element of . Then, again as before, if is in the stablizer of , the elements must all belong to . But if isn’t prime, we can no longer deduce that the numbers run through the whole of .
However, we can say exactly what they do run through — this is a bit of Numbers and Sets. If , then they run through all elements of that differ from by a multiple of , of which there are . That is, we take the subgroup of generated by and then we know that if is in the stabilizer of and contains an element , then the entire coset lies in as well. So must be a union of cosets of .
This isn’t possible unless is a multiple of . That is, can’t be in the stabilizer of unless is a factor of , or equivalently is a factor of , or equivalently again is a multiple of . In particular, if , then has to be a multiple of , which implies that , so in this case the stabilizer of every set has size and we can deduce, just as before, that is a multiple of . More generally, if , then has to be a multiple of . Since is a factor of , it follows that it is necessary and sufficient for to be a multiple of .
There are multiples of , which form a subgroup, so the stabilizer is a subgroup of a group of size . Therefore, the orbit has size equal to a multiple of . It follows that the union of the orbits has size equal to a multiple of . Therefore, is always a multiple of . (It’s possible to give more or less the same argument but without using the language of orbits and stabilizers: you just define two sets of size to be cyclically equivalent if one is a translate of the other, and you then argue that the equivalence classes must have sizes that are multiples of .)
I seem to remember that at least one Sylow theorem has something to do with the highest power of a prime that divides the order of the group. So let’s think briefly about what happens if , where is a prime and is not a multiple of . What should we take as our ? If we try , then we get that , so . So we can deduce from that that is a multiple of .
I don’t know whether that will be useful, but let’s press on and see whether we can show that there must be a subgroup of order if is a group of order . The plan is to consider the action of on the collection of all subsets of size . What we’d like to show is that at least one orbit has size . What do we know about the orbits? Here are some facts that we can write down.
(i) The size of each orbit is a factor of .
(ii) The sum of the sizes of all the orbits is a multiple of .
Is there anything else we can say? Well, a rather simple fact is that the union of all the translates of a subset of is the whole of . So if that subset has size , then the number of distinct translates (which is the same as the size of the orbit of that set) must be at least . So let’s add that to our list.
(iii) Every orbit has size at least .
This is starting to look promising. Every factor of that exceeds is forced to be a multiple of . So every orbit must have a size that is either a multiple of or equal to . So one possible strategy would be to identify somehow an orbit that has a size that is not a multiple of , or at least to show that such a thing must exist.
Now I’m feeling a bit stuck, because I don’t really see why such an orbit has to exist. Or do I? It suddenly occurs to me that there would be an easy argument if we knew that was not a multiple of . Is that true? I think it might be, so let’s do a tiny little experiment. Let’s take and let’s calculate . We get . If we cancel out 2s, we get , which is odd, just as we wanted.
At the moment, I can’t think of a nice argument that is not a multiple of when isn’t. And for the second paragraph in a row, no sooner do I express that kind of pessimism than an idea occurs to me. Let’s think about the orbits when acts on the sets of size (where is still ). What I’m hoping is that plenty of these will have sizes that are multiples of , and just a few won’t, so that we’ll be able to tell that the sum of the sizes of the orbits is not a multiple of .
Let be a set of size . The only way the orbit of can fail to have size divisible by is if the stabilizer has size divisible by . But as we’ve already seen, the only way that the stabilizer of a set can have size equal to the size of the set itself is if the set is a coset of a subgroup. So the only way the orbit of can fail to have size divisible by is if is a coset of a subgroup of size . But the only subgroup of of size is the subgroup that consists of all multiples of . That tells us that there is precisely one orbit of size , and we have already observed that all the rest have sizes that are multiples of . Since isn’t a multiple of , we have shown that the sum of the sizes of all the orbits, which is , is not a multiple of , just as we were trying to do.
The less nice argument I was contemplating was simply to show that the largest power of that divides is the same as the largest power tat divides when isn’t a multiple of and . I haven’t checked whether that’s true, but if it is, then it means that all the s cancel when you work out the binomial coefficient. But I don’t like that proof (if it works) because it doesn’t tell me why the result is true, whereas the one I’ve just given does: it gives me a natural partition of the collection of subsets of of size into a bunch of sets with sizes divisible by and one set of size not divisible by . That’s a genuine explanation.
Where have we got to now? We know the following facts. Just in case there is any confusion, I’m now leaving behind and going back to an arbitrary group of size . By “orbit” I mean orbit of the left action of on the set of all subsets of of size .
Earlier we remarked the following.
(i) The size of each orbit is a factor of .
(ii) The sum of the sizes of all the orbits is a multiple of .
(iii) Every orbit has size at least .
To these three facts, we can now add one more.
(iv) The sum of the sizes of all the orbits is not a multiple of (because it equals , which we’ve just shown isn’t a multiple of ).
Also, we used (i) and (iii) earlier to deduce the following (which is why we bothered to prove (iv)).
(v) Every orbit either has size or has size that is a multiple of .
But from (iv) and (v) it follows that at least one orbit must have size . If is a set in that orbit, then the stabilizer of has size , so we’ve found a subgroup of size !
As usual, if you remove all the how-did-I-think-of-that discussion you end up with a much shorter argument, but it also leaves you with mysterious and unmotivated steps. Suppose you were trying to retain this proof in your head while actively memorizing as little as you possibly could. What might you go for? Here’s a possibility.
1. Amongst all subsets of size , those that are cosets of subgroups can be defined in terms of sizes of orbits of the left-multiplication action. [Then it's just a question of working out the details, which is not too bad.]
2. If and , then is not a multiple of .
3. To prove that, think carefully about orbits of the left-multiplication action of on its subsets of size . [You'll then find that you've done most of the work while thinking about 1.]
4. Now write down what you can about the orbits of the same action when the group is a general group of order . Use the orbit-stabilizer theorem and the observation that every orbit has size at least .
5. By this time you’ll have written down enough information for the result to follow easily.
Even that looks like quite a bit to commit to memory, but with experience one can reduce it further. For example, it should be a reflex action to apply the orbit-stabilizer theorem whenever you are thinking about group actions and the opportunity arises. Also, if you’re on the ball, then you don’t have to remember to show that is not a multiple of , since the need to do that arises from the proof. Or perhaps I should say that it’s a standard trick: if you’ve got a bunch of numbers and you want to show that at least one of them is not a multiple of , then it’s enough to show that their sum is not a multiple of .
This post has ended up being much more specific than its title promised. I haven’t talked in general about intrinsic group actions, but have instead concentrated on just one proof and discussed how one can come up naturally with an appropriate action (given a small list of possible actions to draw on). Just before I finish, I’m going to look back at a comment on my previous post but one on group actions, which I deliberately didn’t read properly because I knew I was going to write this. It will be interesting to see whether I have come up with precisely the same statement and proof.
It seems that I have, but when looking at the comment I find that I have a bizarre experience that I often have when reading maths: that even if I know an argument well, somebody else’s presentation of it is often quite hard to understand (even if they’ve presented it perfectly well, as is the case here). Anyhow, it’s clearly the same argument, and it demonstrates very clearly what I said about the actual argument being much much shorter than the thought processes that give rise to it, though the comparison is slightly unfair because some of the details were left out in that comment.
I’m going to stop here, but if I were more conscientious I would continue with an application of an action based on conjugation. Instead, I refer you to the same comment, which briefly mentions an application of this kind. I also refer you to the Wikipedia article on the Sylow theorems if you’re interested. (This post has proved the first of the three Sylow theorems.)
I now see that what I’ve just talked about in this post was covered in question 13 of Examples Sheet 3. So let me stress that what I’m interested in here is different. That question tells you exactly what to do — consider such-and-such an action, apply the orbit-stabilizer theorem, etc. — whereas here I’ve attempted to start from scratch without any of those hints. I’m hoping that that will give a better idea of how to think of instrinsic group actions than you get if you’re fed them out of a spoon.