How many rotational symmetries does a cube have? This question can be answered in a number of ways. Perhaps the one that most readily occurs to people is this: each vertex can end up in one of eight places; once you’ve decided where to put it, there are three places you can put one of its neighbours; once you’ve decided where to put that, the rotation is determined, so the total number of rotations is .
Here’s another proof. Take one of the faces. It can go to one of six other faces, and once you’ve decided which face it will go to, one of the vertices on the face has four places it can go, and once you’ve decided that you’ve fixed the rotation. So the total number of rotations is .
And here’s another. Take one of the midpoints of the twelve edges. There are twelve places it can end up, and once you’ve decided where to put it, there are two choices for how you send the two endpoints of the original edge to the endpoints of the new edge. So the total number of rotations is .
And here’s yet another. Take a point half way between the centre of one of the faces and one of the vertices. (If the cube is the set of all points such that and all lie in the closed interval , then we could, for instance, take the point .) There are 24 places that that point can end up — the 24 points that are half way between the centre of some face and one of the vertices of that face. There is only one rotational symmetry that takes the original point to any given one of those 24 points. Therefore, the number of rotations of the cube is .
If you understood those arguments, then you basically understand the orbit-stabilizer theorem, even if you think you don’t. To try to convince you of that, I’ll first show how to convert one of the proofs into a proof that explicitly uses the orbit-stabilizer theorem. I’ll then discuss how much you have to remember in order to remember the proof of the orbit-stabilizer theorem. As usual, I shall aim to show that the answer is “very little indeed”. However, routine proofs in abstract algebra have a somewhat different flavour from routine proofs in set theory and analysis, and as this one is a good representative example, it bears discussing in some detail. (Later I may try the same with the first isomorphism theorem, which you should be meeting fairly soon.)
To illustrate how to count symmetries using the orbit-stabilizer theorem, let me convert the proof that used faces. The obvious way to capture the idea of “which face a particular face goes to” is to let the symmetry group of the cube act on the faces of the cube. Then the set of places that a particular face can go to is nothing other than the orbit of that face. How does the group act on the faces? Well, any rotation of the cube will permute the faces, and that permutation is the one that corresponds to the rotation.
In the earlier version of the argument, we said that our chosen face can go to any one of six other faces. The fancy way of saying that is that the orbit of the chosen face is the set of all faces, which has size 6.
And in the earlier version of the argument, we said that once we had decided which face our chosen face would go to, there were four ways of lining up the vertices. This doesn’t quite correspond to a statement about stabilizers, but let us note for now that if the chosen face maps to itself, then we have four choices. So the stabilizer of our chosen face has size 4. Multiplying those two numbers together gives us 24.
The content of the orbit-stabilizer theorem is basically that if a group acts on a set , then once you know how many ways there are of sending an element of to itself, you also know how many ways there are of sending it to any other element in its orbit. In the faces-of-the-cube example, knowing that there are four ways of rotating the cube so that a face ends up where it was before tells us that there are also four ways of sending it to some other face . And that is because “all faces look basically the same” from the point of view of the rotation group. In general, “all points of the orbit of look basically the same” from the point of view of the transformations performed by the elements of .
I’m going to give a few different proofs of the orbit-stabilizer theorem, not because they are fundamentally different, but because they have certain stylistic features that are worth commenting on. Also, it may be interesting to see how much variety is possible even when presenting a proof, even when the underlying argument is the same.
First, I’ll remind you of the statement we are trying to prove.
Theorem. Let be a group that acts on a set , let be an element of , let be the orbit of and let be the stabilizer of . Then .
In words, the size of the group is the size of the orbit times the size of the stabilizer.
Proof 1. For this proof I want to try to capture as closely as possible our intuition in the cube example that the set of rotations that takes one face to another is “just like the set of rotations that fix that face, but over at another place”. However, I’ll argue in general.
What am I trying to show in the abstract? I want to show that if belongs to the orbit of , then the set of such that is the same size as , which is the set of such that . (Here I’m slipping into the condensed notation and writing instead of or . But it’s important to bear in mind that the “product” is not the group operation, since it’s only that belongs to a group. Rather, it is what one might call the group action operation, which has some nice group-like properties such as and .)
What is the most natural way to show that two sets have the same size? It’s to produce a bijection between them. (It isn’t the only way. Another is to calculate their sizes, possibly by completely different methods, and show that you get the same answer in both cases. But that is not an appropriate method here, since we’re not given enough information to calculate anything.)
Let me write for the set of that take to . If I’m given an element of , how do I turn it into an element of ? Well, in the faces-of-cube example, what I might do is this. I fix, once and for all, a rotation that takes my initial face to the given face. And then, given a rotation that fixes the initial face, I compose it with to get a rotation that takes the initial face to the given face.
Let’s try that with and . Since belongs to the orbit of (by assumption), there is some such that . Now let me define a map from to by mapping to . Note that takes first to (since ) and then to (since ). Thus, really does belong to .
However, is the map we’ve just defined a bijection? Let’s see if we can prove that it’s an injection and a surjection. No, let’s not do that. Let’s try to find an inverse. Given an element of , how might we convert it into an element of ? There’s only one thing we can even dream of trying at this point. Since takes to and also takes to , takes to , as we want. So the map takes to . Does it invert the previous map? Yes of course it does.
We’ve shown that for each there are precisely elements of that take to . But every element of takes to something in the orbit, so , as we were trying to prove.
In case you found that off-puttingly long, here it is stripped of all the accompanying chat.
The real Proof 1. Let be an arbitrary element of , and let . Pick and define a map by . The map defined by inverts , so for every . But the sets with form a partition of . It follows that .
I cheated slightly there by not checking carefully that really does take to and that really does take to . But those facts are easy enough to be left to the reader to do in his/her head.
That proof is so short that one might wonder why another proof could possibly be desirable. Well, it’s mostly an aesthetic point, at least as far as this proof is concerned, but there’s something a bit ugly about choosing that . Why? Because I didn’t say how to do it. So, for example, the way I chose for one might be completely unrelated to the way I chose it for another . Wouldn’t it be nicer if there were some natural way of defining in terms of ?
Well, yes it would, but it’s not that easy to do. Just think of the cube example. Suppose I take a face and I ask you to define, for each other face , a rotation of the cube that takes to . I want you to do it in a nice systematic way. How might you do it? Well, if then probably the most natural thing to do is take the identity. How about if is one of the neighbouring faces to ? Perhaps the most natural thing there is to take a 90-degree rotation about an axis through the centre of the cube that’s parallel to the edge where and meet. But then what about the face opposite ? There are four ways of rotating the cube so that lands up at the opposite face, and they are of two kinds: two of them are half turns about axes that go through the midpoints of two opposite faces, and the other two are half turns about axes that go through the midpoints of two opposite edges. (If you draw a diagram, I hope you’ll be able to see what I’m talking about here. It’s one of those things that may be easier to work out for yourself.) Anyhow, for each of these two types of half turn, there is absolutely nothing to choose between the two half turns of that type. So there just isn’t a natural way to choose a rotation for each face. As mathematicians might say, there isn’t a canonical choice.
So is that the end of the story? Not quite. There’s a useful principle that sometimes applies in this kind of situation. It says this.
This meme was embedded in my brain as a result of a nice Mathoverflow question, though I suppose I was aware of it less consciously before that. Let’s see how it plays out with our proof.
If I don’t choose just one , then what do I do instead? I choose all that belong to .
A problem then arises when I try to define a bijection from to . Never mind, though. Let’s just define a map from to by sending to . Note that this is like what we did before, but we’re doing it for every and not just one chosen . And what’s nice about it is that we are now doing precisely the same thing for every .
Let’s call our map . Obviously, is not a bijection, but that doesn’t matter. We’re trying to show that it’s a bit like a putting together of bijections. So what we’d like to show is that every element of has exactly preimages under . That will tell us that , which will imply that .
So let’s take . How many preimages has it got? Well, a preimage of is a pair such that . So I want to show that there are precisely solutions of the equation with and . But that’s easy: for each there is precisely one possible , namely , which does indeed belong to .
Let me again give the condensed version, just to convince you that what I’ve written doesn’t add up to a long proof. In fact, I don’t even need to bother to define the function .
Proof 2. Let be an arbitrary element of and let . For every there is exactly one such that , namely . It follows that every can be written in ways as with and . Also, for every and every . It follows that . Therefore, . But the sets with form a partition of . It follows that .
Here is a variant of the above argument that I like better.
Proof 3. Let be an arbitrary element of and let . Let and let us see in how many ways we can write with and . Well, for each , there is exactly one such that , namely . So we can write in ways. But also, for each there is exactly one such that , namely . This shows that we can write in ways. Therefore, . But the sets with form a partition of . It follows that .
Or do I like it better? It’s starting to look, with its non-canonical choice of , a bit too like the first argument.
I still don’t feel as though I’ve arrived at the neatest and most symmetrical argument, and I’ve also not satisfied another urge, which is to prove that by finding a nice bijection between and . There are good reasons for the second problem, as I’ve already discussed, but I might be able to satisfy my urge by finding not a one-to-one correspondence, but something a bit more general and multivalued.
So let’s take a point . What can we do with it? We can use it to define the element of , but that doesn’t seem very exciting or helpful. What we’d really like is to define an element of , which earlier we did by fixing some and taking . But that felt too non-canonical, so instead we preferred to take all .
If we take all , then that’s saying that we can get from to in several different ways. So we seem to get a map from to , which is very simple: it takes to . But what’s the point of it? And where does come in?
One way of making come in is to go one step further and let act on to create . So now we’ve got a map from to , the map that takes to . How many preimages does an element have?
I’m not going to answer that question (though I could) because once we’ve got to the point of mapping to using the map above, we see that isn’t really playing a role, so why not just focus on the map from to that takes (which I was calling above) to ? If , then how many preimages does have?
I won’t bother to answer that question either: it’s the same as asking how big the set is, and we’ve established already that that is , so it wouldn’t be a particularly new proof that resulted. However, one remark that’s worth making is that the set is a left coset of . Probably the proof you were given in lectures was this.
Proof 4. We shall show that there is a bijection between and the set of left cosets of . To do this, we map the left coset to . We must show that this is well-defined. But if , then , and therefore, since is a subgroup, . From that it follows that , so .
Since the number of left cosets of is , we are done.
If the phrase “well-defined” worries you in the above argument, then I recommend a post I once wrote about what it means.
Here’s a different way of writing the above proof, where we think more about equivalence relations than about partitions.
Proof 5. Here are two equivalence relations on . For the first, I define if . For the second, I define if . Note that this is the same as saying that and also the same as saying that .
Now if and only if if and only if . So the two equivalence relations are the same. The number of equivalence classes for the first relation is obviously and the size of each equivalence class for the second relation is obviously , so the result is proved.
Let me make one final remark about the orbit-stabilizer theorem. Why, one might ask, is it a useful result? A rather general answer is that it gives us a relationship between three quantities, namely , and , that allows us to determine any one of them from the other two. Situations crop up quite frequently in group theory where it is not very easy to see what one of these quantities is directly, but quite easy to calculate the other two. The orbit-stabilizer theorem then gives us the hard one too. For example, in the case of counting rotational symmetries of a cube, it isn’t easy to think of all the rotations unless you partition them in some nice way, such as looking at what they do to a particular vertex or face, which, as we saw before, amounts to counting orbits and stabilizers.
It’s not always that’s the tough one to get a handle on. For example, in question 10 of Examples Sheet 3 it’s the size of the orbit that isn’t obvious. (In general with the bunch of questions around there, I recommend thinking to yourself, “What is the orbit-stabilizer theorem giving me?”)