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 \(G\) 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 \(G\) on itself. That is, let’s consider actions where the set \(X\) on which \(G\) acts is the set of elements of \(G\). A very obvious action is given by left multiplication. That is, if \(a\in G\), we define a function \(\phi_a:G\to G\) by \(\phi_a(g)=ag\). (If you prefer the product notation you could let \(X=G\) and define the action, which is now a function from \(G\times X\) to \(X\), by \((a,g)\mapsto ag\).)
It doesn’t take much to come up with right multiplication as another action. That is, we can define \(\psi_a(g)\) to be \(ga\). But is that an action? Let’s check. What is \(\psi_{ab}(g)\)? It’s \(gab\). And what is \(\psi_a\psi_b(g)\)? It’s \(gba\). Oops.
What we would really like is to insert that \(a\) after the \(g\) and before the \(b\). And there is in fact a way of doing that … sort of. We define \(\psi_a(g)\) to be \(ga^{-1}\) instead. Let’s do the check again. This time, \(\psi_{ab}(g)=g(ab)^{-1}\), and \(\psi_a\psi_b(g)=gb^{-1}a^{-1}\). 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 \(\rho_a(g)\) to be \(aga^{-1}\). This is the conjugation action of \(G\) on itself, so called for the obvious reason that \(\rho_a(g)\) is what you get when you conjugate \(g\) by \(a\). (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 \(\phi_a\) does to \(g\) what \(\psi_a\) does to \(g^{-1}\). To put that more precisely, let \(\beta:X\to X\) be the map that takes each element to its inverse. Then \(\beta\) is a bijection, and \(\psi_a(g)=\beta^{-1}\phi_a(\beta g)\). (Also, as it happens, \(\beta^{-1}=\beta\), 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 \((a,g)\) to \(ag\), 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 \(X\) on which these operations act. Instead of taking \(X\) to be \(G\), we can build something else out of \(G\). Here are a few examples of actions derived from left multiplication in an obvious way.
1. If we happen to know that \(G\) has a subgroup \(H\), then we can take the obvious left-multiplication action of \(G\) on the set of all left cosets of \(H\). (This isn’t really an intrinsic action in the sense I mean, because \(H\) is an “external” object.)
2. We could define an action on the set of all ordered pairs \((g,h)\) of elements of \(G\) by \(\phi_a(g,h)=(ag,ah)\).
3. We could define an action on the set of all subsets of \(G\) of size \(k\) by taking \(\phi_a(E)=aE\). Here \(aE\) is defined to be \(\{ag:g\in E\}\).
4. We could define an action on the set of all partitions of \(G\) into sets \(E_1,\dots,E_r\) of sizes \(k_1,\dots,k_r\) by taking \(\phi_a\) of the partition \(\{E_1,\dots,E_r\}\) to be the partition \(\{aE_1,\dots,aE_r\}\).
One thing I can remember is the proof of Cauchy’s theorem: that if \(p\) is a prime that divides the order of \(G\), then \(G\) has a subgroup of order \(p\). The action there is a bit different, since it’s an action not of \(G\) but of the cyclic group \(C_p\) on a set that is derived from \(G\). To be precise, it acts on the set of all \(p\)-tuples \((a_0,a_1,\dots,a_{p-1})\) such that \(a_0a_1\dots a_{p-1}=e\), and it acts by cyclically permuting the \(p\)-tuples. So I’ll have to bear in mind that we may be looking for that kind of action rather than an action of \(G\). However, for now let’s press on.
How am I going to be able to use a left-multiplication action of \(G\) to tell me anything about the existence of a subgroup of some cardinality? Let’s take the cardinality to be \(k\).
The one that looks most promising to start with is the action of \(G\) on the set of all subsets of size \(k\), for the simple reason that a subgroup of \(G\) is in particular a subset of size \(k\). Of course, a subgroup isn’t just any old subset of size \(k\), 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 \(H\) is a subgroup, then every set \(a H\) is a left coset of \(H\), 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 \(H\) under the left-multiplication action has cardinality \(|G|/|H|\). We also know that the stabilizer of \(H\) is \(H\) itself, which of course has cardinality \(|H|\). (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 \(E\) of size \(k\) that is not a subgroup, and yet its orbit has size \(|G|/k\)?
Oops, that was the wrong question, since \(E\) could be a left coset of a subgroup. So let’s ask whether \(E\) 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 \(|G|/k\) looks tricky, whereas to show that something has size \(k\), when the object we start with already has size \(k\), 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 \(E\) 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 \(E\) is a set of size \(k\) that contains the identity, then what can we say about the stabilizer of \(E\)? Well, for \(a\) to belong to the stabilizer of \(E\), we need \(aE=E\), and in particular, we need \(ae=a\) to belong to \(E\). Therefore, the only possible elements of the stabilizer of \(E\) are elements of \(E\). But do they belong to the stabilizer? Yes, if and only if \(E\) is closed under left multiplication, which is true if and only if \(E\) is a subgroup.
How do we “translate that discussion”? Let’s just fix any old element of \(E\) and call it \(g\). Now we can say with complete confidence that if \(a\) belongs to the stabilizer, then \(ag\in E\), from which it follows that \(a\in Eg^{-1}\). For the stabilizer to have size \(k\), we therefore need it to equal \(Eg^{-1}\), so we need the following to be true: if \(h,h'\in E\), then \(hg^{-1}h'\in E\).
We’re hoping to show that this implies that \(E=gH\) for some subgroup \(H\), so let’s see what this condition tells us about \(g^{-1}E\). If \(h,h'\in E\), then \(g^{-1}h,g^{-1}h'\in g^{-1}E\), and the condition above tells us that \(g^{-1}hg^{-1}h'\in g^{-1}E\). So \(g^{-1}E\) is closed under multiplication, just as we wanted.
All this suggests a proof strategy. We could consider the left-multiplication action of \(G\) on the set of all subsets of \(G\) of size \(k\), and try to show that at least one orbit has size \(|G|/k\), under appropriate conditions on \(|G|\) and \(k\), 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 \(k\) to divide \(|G|\), 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 \(G\) of size \(k\), 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 \(G\), so its size will be a factor of \(|G|\). 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 \(k\) we’ve got to have at least some orbits of size \(|G|/k\).
Of course, the number of sets of size \(k\) is just \(\binom {|G|}k\), 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 \(p\) is a prime and \(1\leq a\leq p-1\), then \(\binom pa\) is divisible by \(p\).
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 \(C_p\) on all its subsets of size \(k\). For convenience, let’s think of \(C_p\) as the group \(\mathbb{Z}_p\) of integers mod \(p\) under addition. So if \(E\) is a subset of size \(k\), then \(\phi_aE\) is \(a+E\). I claim that the stabilizer of \(E\) is just \(0\). Indeed, if \(a\) is any non-zero element of the stabilizer and \(x\in E\), then all of \(x, x+a, x+2a, \dots\) have to belong to \(E\), which tells us that \(E\) is the whole group. But we’re assuming that \(k\) is non-empty and not equal to the whole group.
What happens if we look at an arbitrary pair of numbers \(n\) and \(k\) and try to run the same argument? That is, we consider the left action of \(\mathbb{Z}_n\) on its subsets of size \(k\). Let \(E\) be one of those subsets, and, as before, let \(x\) be an element of \(E\). Then, again as before, if \(a\) is in the stablizer of \(E\), the elements \(x, x+a, x+2a,\dots\) must all belong to \(E\). But if \(n\) isn’t prime, we can no longer deduce that the numbers \(x, x+a, x+2a,\dots\) run through the whole of \(\mathbb{Z}_n\).
However, we can say exactly what they do run through — this is a bit of Numbers and Sets. If \(d=(a,n)\), then they run through all elements of \(\mathbb{Z}_n\) that differ from \(x\) by a multiple of \(d\), of which there are \(n/d\). That is, we take the subgroup \(H\) of \(\mathbb{Z}_n\) generated by \(d\) and then we know that if \(a\) is in the stabilizer of \(E\) and \(E\) contains an element \(x\), then the entire coset \(x+H\) lies in \(E\) as well. So \(E\) must be a union of cosets of \(H\).
This isn’t possible unless \(|E|=k\) is a multiple of \(n/d\). That is, \(a\) can’t be in the stabilizer of \(E\) unless \(n/(a,n)\) is a factor of \(k\), or equivalently \(n\) is a factor of \(k(a,n)\), or equivalently again \((a,n)\) is a multiple of \(n/(n,k)\). In particular, if \((n,k)=1\), then \((a,n)\) has to be a multiple of \(n\), which implies that \(a\equiv 0\), so in this case the stabilizer of every set has size \(1\) and we can deduce, just as before, that \(\binom nk\) is a multiple of \(n\). More generally, if \((n,k)=m\), then \((a,n)\) has to be a multiple of \(n/m\). Since \(n/m\) is a factor of \(n\), it follows that it is necessary and sufficient for \(a\) to be a multiple of \(n/m\).
There are \(m\) multiples of \(n/m\), which form a subgroup, so the stabilizer is a subgroup of a group of size \(m\). Therefore, the orbit has size equal to a multiple of \(n/m\). It follows that the union of the orbits has size equal to a multiple of \(n/m\). Therefore, \(\binom nk\) is always a multiple of \(n/(n,k)\). (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 \(k\) 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 \(n/(n,k)\).)
I seem to remember that at least one Sylow theorem has something to do with the highest power of a prime \(p\) that divides the order of the group. So let’s think briefly about what happens if \(n=p^rm\), where \(p\) is a prime and \(m\) is not a multiple of \(p\). What should we take as our \(k\)? If we try \(p^r\), then we get that \((n,k)=p^r\), so \(n/(n,k)=m\). So we can deduce from that that \(\binom n{p^r}\) is a multiple of \(m\).
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 \(p^r\) if \(G\) is a group of order \(n=p^rm\). The plan is to consider the action of \(G\) on the collection of all subsets of size \(k=p^r\). What we’d like to show is that at least one orbit has size \(n/k=m\). 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 \(n=p^rm\).
(ii) The sum of the sizes of all the orbits is a multiple of \(m\).
Is there anything else we can say? Well, a rather simple fact is that the union of all the translates of a subset of \(G\) is the whole of \(G\). So if that subset has size \(p^r\), then the number of distinct translates (which is the same as the size of the orbit of that set) must be at least \(m\). So let’s add that to our list.
(iii) Every orbit has size at least \(m\).
This is starting to look promising. Every factor of \(p^rm\) that exceeds \(m\) is forced to be a multiple of \(p\). So every orbit must have a size that is either a multiple of \(p\) or equal to \(m\). So one possible strategy would be to identify somehow an orbit that has a size that is not a multiple of \(p\), 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 \(\binom n{p^r}\) was not a multiple of \(p\). Is that true? I think it might be, so let’s do a tiny little experiment. Let’s take \(n=12=2^23\) and let’s calculate \(\binom{12}4\). We get \(12\times 11\times 10\times 9/4\times 3\times 2\times 1\). If we cancel out 2s, we get \(3\times 11\times 5\times 9\), which is odd, just as we wanted.
At the moment, I can’t think of a nice argument that \(\binom{p^rm}{p^r}\) is not a multiple of \(p\) when \(m\) 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 \(\mathbb{Z}_n\) acts on the sets of size \(p^r\) (where \(n\) is still \(p^rm\)). What I’m hoping is that plenty of these will have sizes that are multiples of \(p\), 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 \(p\).
Let \(E\) be a set of size \(p^r\). The only way the orbit of \(E\) can fail to have size divisible by \(p\) is if the stabilizer has size divisible by \(p^r\). 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 \(E\) can fail to have size divisible by \(p\) is if \(E\) is a coset of a subgroup of size \(p^r\). But the only subgroup of \(\mathbb{Z}_n\) of size \(p^r\) is the subgroup that consists of all multiples of \(m\). That tells us that there is precisely one orbit of size \(m\), and we have already observed that all the rest have sizes that are multiples of \(p\). Since \(m\) isn’t a multiple of \(p\), we have shown that the sum of the sizes of all the orbits, which is \(\binom{p^rm}{p^r}\), is not a multiple of \(p\), just as we were trying to do.
The less nice argument I was contemplating was simply to show that the largest power of \(p\) that divides \(p^rm-t\) is the same as the largest power tat divides \(p^r-t\) when \(m\) isn’t a multiple of \(p\) and \(0\leq t<p^r\). I haven’t checked whether that’s true, but if it is, then it means that all the \(p\)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 \(\mathbb{Z}_n\) of size \(p^r\) into a bunch of sets with sizes divisible by \(p\) and one set of size not divisible by \(p\). 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 \(\mathbb{Z}_n\) and going back to an arbitrary group \(G\) of size \(p^rm\). By “orbit” I mean orbit of the left action of \(G\) on the set of all subsets of \(G\) of size \(p^r\).
Earlier we remarked the following.
(i) The size of each orbit is a factor of \(n=p^rm\).
(ii) The sum of the sizes of all the orbits is a multiple of \(m\).
(iii) Every orbit has size at least \(m\).
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 \(p\) (because it equals \(\binom {p^rm}{p^r}\), which we’ve just shown isn’t a multiple of \(p\)).
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 \(m\) or has size that is a multiple of \(p\).
But from (iv) and (v) it follows that at least one orbit must have size \(m\). If \(E\) is a set in that orbit, then the stabilizer of \(E\) has size \(p^r\), so we’ve found a subgroup of size \(p^r\)!
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 \(k\), 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 \(n=p^rm\) and \(k=p^r\), then \(\binom nk\) is not a multiple of \(p\).
3. To prove that, think carefully about orbits of the left-multiplication action of \(\mathbb{Z}_n\) on its subsets of size \(k\). [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 \(p^rm\). Use the orbit-stabilizer theorem and the observation that every orbit has size at least \(m\).
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 \(\binom nk\) is not a multiple of \(p\), 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 \(p\), then it’s enough to show that their sum is not a multiple of \(p\).
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.
This entry was posted on December 10, 2011 at 5:42 pm and is filed under Cambridge teaching, IA Groups. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.