## The Burnside Theorem and Counting, part I.

### December 8, 2012

Let’s talk about Burnside’s theorem. First, let me note that there are *two *results commonly called "Burnside’s Theorem." The first one that I learned (which we won’t be discussing in this post) was:

**Theorem (Burnside)**. If is a finite group of order where are non-negative integers and where are primes, then is solvable.

The second one is also a group theoretical result, but a bit more combinatorial-feeling. In some books (and, apparently, Wikipedia) this second result is called Burnside’s Lemma. As noted in the Wikipedia article, this theorem was not even due to Burnside, who quoted the result from Frobenius, who probably got it from Cauchy.

Let’s get some definitions down. As usual, we’ll denote the *order* of the group by , and our groups will *all be finite in this post*. If we have a group which acts on a set , then given some fixed we define the set ; this is, of course, the fixed points in when acted on by the element ; for the remainder of the post, we will simply write with the set implied. Remember, when a group acts on , the "product" will sit inside of , and we write the action as for an element acting on an element . The *orbit* of a point when acted on by is given by ; we’ll denote this , though this is not standard notation. The orbit, essentially, is all of the possible values that you can get to by acting on with elements in your group.

One thing to note, also, is that orbits are *pairwise* *disjoint. *You should prove this to yourself if you haven’t already, but the idea is like this: if are orbits of elements in then suppose ; then there is some such that , but this implies which implies the orbits are identical (why?). Hence, each element of is in *exactly one orbit*.

We need one more result before we can sink our teeth into Burnside. Remember the fixed point set above? This was all of the elements such that for some . There’s a similar notion called a *Stabilizer*, denoted ; this is saying that we first fix , and then look at all the elements which stabilize it. These definitions are pretty similar feeling (almost like family!) and, in fact, there is a nice relation between the two:

**Notation. **Let denote the set of orbits of when acted on by ; when is a group and is a subgroup this is the same as a quotient.

**Theorem (Orbit-Stabilizer Theorem).** There is a bijection between and .

That is, if we act on by elements of which fix , then we will have the same number of elements as the orbit of . This might seem a little confusing at first, but if you work through it, it’s not so weird.

*Sketch of the Proof. *(Skip this if you’re not comfortable with all this notation above; just go down to the next theorem.) Here, we want to show a bijection. Notice that $G/G_{x}$ is the set of cosets for . We claim that the mapping which sends is well-defined, injective and surjective (but not a homomorphism). First, well defined: if then $latex $hk^{-1}\in G_{x}$ which means that . This implies, after some manipulation, that , which means these elements are identical in . Second, surjectivity is clear. Last, if in the orbit, then which implies which gives ; hence this map is injective. This gives us that our map is bijective.

One immediate corollary is that ; that is, the number of elements in the orbit of is the same as the number of elements in divided by the number of elements in which fix . Think about this for a minute.

## Road to the Proof.

Okay. Now, let’s think about something for a second. What is the sum

telling us? This is the number of elements in which are fixed by some ; but there might be some overlap, since if and , then will be counted twice: one as an element of and once as an element of . But how much overlap is there? This is an innocent seeming question, and you might think something like, "Well, depends on how much stuff stabilizes each .", and this is pretty close to the point.

First, note that

which is just the long way to write out this sum; but, the nice part about that is, we can now think about this as all of the elements of which are stabilized by some (why?). Then,

If you don’t see this, you should prove to yourself why they’re the same sum (why is each element counted in the left-hand side also counted in the right-hand side?). Now, by the Orbit-Stabilizer theorem above, this right-hand sum becomes pretty nice. Specifically,

where we noted in the last equality that is a constant, so we may pull it out of the sum.

Recalling that denotes the number of orbits, we have that if we take a single orbit (call it ) we will be adding up exactly times (since the sum is taken over each so, in particular, over each $x\in A$); hence, we will add for each orbit we have in . That is;

Putting this all together, we have

We clean it up a bit, and state the following:

**Theorem (Burnside’s). **For a finite group and a set , with notation as above, we have .

That is, the number of orbits is equal to the sum, over , of the elements of fixed under , averaged by the number of elements in . Kind of neat.

Next time, we’ll talk about applications!