Group actions IV: intrinsic actions

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.

20 Responses to “Group actions IV: intrinsic actions”

"The Chaz" Says:
December 11, 2011 at 4:59 pm | Reply
Mr. Gowers,
Thank you for this series on group actions. I appreciate your “ground up” approach.

Hopefully I will be sufficiently informed as to appreciate more of your work in the future.

Sincerely,
An aspiring mathematician
Adam Bohn Says:
December 12, 2011 at 9:40 am | Reply
Another very enjoyable post…I only wish these were being written when I was first learning group theory!

Also just wanted to say thanks for your honest confession at the start of the post. It seems to be a bit of a taboo for mathematicians to admit to ever having (had) difficulties like this (especially in the US, although I suspect that is a cultural thing), and coming from a Fields medallist it is music to the ears of this occasionally self-doubting PhD student!

Judging by the quality and accessibility of this series your students will not be having the same problems…
Dave Says:
December 13, 2011 at 11:08 am | Reply
Given you’ve posted this in IA groups, you may be amused to know that your first paragraph reminds me greatly of when Thompson lectured the IA course to me. I think it would be safest to simply say it was an experience.
Joseph Says:
December 13, 2011 at 3:53 pm | Reply
I have been struggling with your proof that $\binom nk$ is always a multiple of $n/(n,k)$ . I get tripped up by the statement “it follows that it is necessary and sufficient for $a$ to be a multiple of $n/m$ “. Sufficiency does not seem to be proven.

Indeed, I do not believe it is sufficient. Consider $n=8, k=2, E = \{2,3\}$ . Then $n/m = n/(n,k) = 8/(8,2) = 8/2 = 4$ . However, $a = 4$ is not in the stabilizer of $E$ .

In the next paragraph, it is implied that the stabilizer is the same size, in fact the same set, for every set $E$ . In fact, in this example the stabilizer is $\{0\}$ for three of the orbits, and is $\{0, 4\}$ for the class of $\{0, 4\}$ .
- gowers Says:
  December 13, 2011 at 5:38 pm
  When I next get the chance, I’ll look back at what I wrote and see whether I understand it. I remember feeling slightly worried when I wrote those words “necessary and sufficient”, but I think that an argument along the lines of what I was writing does exist.
gowers Says:
December 13, 2011 at 8:56 pm | Reply
OK, here’s a much better presentation of the proof. (I haven’t checked whether the previous version was fundamentally incorrect or just unclear and incorrect in certain details.)

I want to prove that $\binom nk$ is always a multiple of $n/(n,k)$ , using the action of the cyclic group $\mathbb{Z}_n$ on the set of all its subsets of size $k$ . We will be able to prove this if we can prove that the cardinality of every orbit is a multiple of $n/(n,k)$ , since the collection of sets of size $k$ can be partitioned into orbits. And to prove that it is sufficient, by the orbit-stabilizer theorem, to prove that the stabilizer of a set $E$ of size $k$ must have size that divides $(n,k)$ .

So let $E$ be a set of size $k$ . The stabilizer of $E$ is a subgroup of $\mathbb{Z}_n$ , and all subgroups of $\mathbb{Z}_n$ are cyclic. In fact, we can say slightly more. If we choose the minimal positive integer $d$ that belongs to a subgroup, then it generates that subgroup. So let $d$ be the minimal generator of the stabilizer of $E$ . So the stabilizer of $E$ has size $n/d$ , which means that we need $n/d$ to divide $(n,k)$ .

But for every $x\in E$ we know that $x,x+d,x+2d,\dots$ all belong to $E$ . Since $E$ has size $k$ it follows that $k$ is a multiple of $n/d$ , and therefore that $n/d$ is a common factor of $k$ and $n$ . Therefore, $n/d$ divides $(n,k)$ , as we wanted.
job seeker Says:
December 14, 2011 at 4:17 pm | Reply
Dear Prof Gowers,

This is off topic, but there are some open positions in math at Cambridge for “pure mathematics”. Is combinatorics considered “pure math”? Since there does not appear to be theoretical computer science in the cs department at Cambridge, is complexity theory and/or algorithms considered “(pure) math” at Cambridge?

Thanks!!!!
- Ralph Says:
  December 14, 2011 at 9:10 pm
  Off-topic: is hairdressing pure trade?
- gowers Says:
  December 14, 2011 at 10:46 pm
  Yes, combinatorics would be considered pure maths, as would those parts of TCS that involve proving theorems.
Jeremy Kahn Says:
December 21, 2011 at 7:05 pm | Reply
This is great—I will never again forget the proof (or the statement) of the first Sylow Theorem. I think the easiest way to remember it as follows: because every the size of every orbit of the left action of $G$ is either a multiple of $p$ or equal to $m$, and every orbit of size $m$ corresponds to a unique $p$-Sylow subgroup of $G$, the number of $p$-Sylow subgroups, reduced mod $p$, depends only on the size of $G$!. So you can compute this number by letting $G$ be $C_{p^r m}$, and you easily find that it is 1.
Mike B Says:
December 24, 2011 at 4:23 am | Reply
Sylow theorems were where algebra suddenly got tough for me, too. Eventually I decided that I had bad a bad experience but this stuff isn’t really impossible to learn. My current effort to re-study algebra has a twofold goal of getting comfortable with Sylow (semester 1) and the unsolvability of the Quintic (semester 2)
- gowers Says:
  December 24, 2011 at 12:01 pm
  The quintic’s on my to-do list as well. What I’d ideally like to do is discover the proof for myself (though of course my half memory of the proof combined with comments I’ve read that people have written about it will add up to a massive hint about how to proceed). If I get round to it, then I’ll report back to this blog.
Alex Youcis Says:
December 26, 2011 at 8:14 am | Reply
Mr. Gowers,

There is something that I have often pondered when hearing people’s difficulties with Sylow (and Sylow related) theorems: have they learned actions of $p$ -groups on finite groups? Namely, there is a fact about actions of finite $p$ -groups on finite sets that a) is of a very simple, basic number theoretic flavor and b) makes much more tidy, and apparent the rest of the “usual suspects” in a basic group theory course. The fact I am referring to is that if $G$ is a finite $p$ -group acting on a finite set $X$ then $\#(X^G)\equiv\#(X)\mod p$ where $X^G=\left\{x\in X:gx=x\text{ for all }g\in G\right\}$ is the “fix set” of $G$ . The proof is simple, $X$ is the disjoint union of singleton orbits and non-singleton orbits. The union of the singleton orbits is precisely the fix set, and so the difference of $\#(X)$ by $\#(X^G)$ is the sum of the cardinalities of the distinct non-singleton orbits. But, the orbit stabilizer theorem says the cardinality of each of these orbits must divide $|G|$ , but since this is a power of $p$ and each of these orbits is not a singleton, we may conclude they are divisible by $p$ . Thus, $\#(X)-\#(X^G)$ is a sum of numbers divisible by $p$ , and thus the conclusion follows. This makes literally everything simpler. Sylow’s theorems, the class equation (a much more robust version of it, in fact), etc. all become little more than one-liners after this simple observation. I don’t know why this approach isn’t taken more often. I can try to point you towards a (not written by me reference) if that sounds appealing to you. Regardless, thanks again for another great post!
A Says:
December 31, 2011 at 4:56 pm | Reply
I hope you will also eventually talk about tensor products, perhaps to construct some tangible group.

Thanks again for these series of posts.

A
Benjamin Steinberg Says:
January 2, 2012 at 2:05 am | Reply
Here is how I would motivate/prove the existence of Sylow subgroups.

Let $p$ be a prime dividing $|G|$. If $G$ had a $p$-Sylow subgroup $P$ then $G/P$ would be a $G$-set $X$ with 2 remarkable properties:

(1) $p$ does not divide the order of $X$
(2) each point stabilizer is a $p$-group.

Perhaps surprisingly, the converse holds: if $G$ has a $G$-set $X$ satisfying (1) and (2) then it has a $p$-Sylow subgroup. Indeed, $p$ cannot divide the size of each orbit of $G$ on $X$ by (1). Thus by restricting to an appropriate orbit, we may assume the action is transitive. But then a point stabilizer would be a $p$-subgroup of index coprime to $p$, done.

I know of essentially 2 ways to construct such a $G$-set $X$.

(a) If $p^m$ is the largest power of $p$ dividing the order of $G$, then as you show above, condition (1) is satisfied for the $p^m$-subsets of $G$. Condition (2) follows because if $A$ is a subset of $G$, then the stabilizer of $A$ acts freely on $A$ and so its order divides the size of $A$, this yields (2).

However, I somehow think the more natural approach (and I believe it was Sylow’s) is to observe that if $G$ embeds in a group $H$ with an action satisfying (1) and (2), then $G$ has such an action by restriction. Thus it suffices to embed $G$ into a group with a $p$-Sylow subgroup. I can’t help but imagine that to suspect the Sylow theorem is true one must already have a good collection of examples of groups for which they are true.

The easiest example is the general linear group $Gl(n,p)$ over the $p$-element field. A simple counting argument shows that the subgroup $UT(n,p)$ of unitriangular matrices is a $p$-Sylow subgroup. Since $G$ embeds in a general linear group by the regular representation we are done.

A more difficult counting argument shows that the automorphism group of the $p$-regular rooted tree of depth $n$ is a p-Sylow subgroup of the symmetric group $S_{p^n}$. Again $G$ embeds in such a group by taking $n$ large enough.
- Alex Youcis Says:
  January 9, 2012 at 7:03 pm
  Benjamin, this approach by proving Sylow for $UT(n)$ and then embedding every group in $UT(n)$ was the preferred method of Serre, no?
Maths lover Says:
March 4, 2012 at 6:11 pm | Reply
Hi,

Please add this site to your blogroll: http://www.mathsrev.com/

It is a helping a lot improve their maths skills.
AV Says:
March 28, 2012 at 12:51 am | Reply
Thank you for all these posts (I am writing as a Cambridge first year Maths undergraduate). I’ll be partly off-topic, but I have noticed there is a tendency in Cambridge to work mostly for the exams. What would you recommend those students who want to prepare for research in (pure) mathematics?
- gowers Says:
  March 28, 2012 at 10:02 am
  My short answer to this would be (i) work for exams too, but (ii) do plenty of hard problems as well. To elaborate on (ii), if there are starred questions on examples sheets, stick at them for longer than you ordinarily might: the experience of solving a problem after several days of effort is an extremely valuable preparation for research, and even failing to solve it after several days of effort is valuable — partly because research is like that too, and partly because if you’re seriously trying, you’ll learn a lot from failed attempts as well as successful ones. If you can’t find interesting and difficult questions on examples sheets, try to get hold of them from somewhere else — they exist!
  
  Going back to (i), there are two ways of preparing for exams. One is to practise old questions and basically focus completely on the exams. The other is to digest the course as well as you possibly can in an attempt to make the exams easy. Both are necessary, but ultimately it is the second that will do you more good when it comes to research. Having said that, the second can be a longer process, so if you’re short of time you’ll be forced to put more emphasis on the first than is ideal or you risk messing up your exams. The ideal is to start the process of digesting courses early in the year, rather than in a mad rush nearer to the exam.
  
  One other piece of advice is not to assume at this stage that you know what kind of pure mathematics appeals to you. This can change a lot during your three years, and in any case what you are doing for at least your first two years is likely to be essential to you whatever your research topic might be, so it is best to try to get on top of everything.
- AV Says:
  March 30, 2012 at 5:58 pm
  Thank you very much!