Part 12: Actions Count! 

Not Burnside's Theorem

 We are going to use the theorems about the sizes of orbits and stabilizers proved in our discussion of group actions to count some configurations which occur in mathematics and science which would otherwise be very puzzling. The main theorem is called Not Burnside's Theorem. This is a joke perpetrated by Peter Neumann because the result was always called Burnside's Theorem until Peter pointed out that it was known to Cauchy at least 50 years before Burnside published it.

 Let X be a finite set and G a finite group acting on X. Recall from Part 10 that for any g in G, Xg = {x 1 X: xg = x} and G is transitive on X if for all x in X, the orbit of x is X.

Lemma 12.1 If G is transitive on X, then |G| = Sg 1 G|Xg|.

Proof We count the set 

S = {(x,g): x 1 X, g 1 G, xg = x}

 in two ways. 

  1. For each fixed g in G, |Xg| = |{(x,g): xg = x}|, so 
  2. |S| = Sg 1 G |Xg|.
  3. For each fixed x in X, |Gx| = |{(x,g): xg = x}|, so 
  4. |S| = Sx 1 X |Gx|.
For each x in X, since G is transitive, the orbit of x = X, so by Lemma 4.3, |X| = |[G:Gx]| = |G|/|Gx|, so |S| = Sx 1 X |G|/|X| = |G|.

 Hence |G| = Sg 1 G|Xg|.

 Let OrbX(G) be the set of G orbits in X. Then:

 Not Burnside's Theorem |OrbX(G)| = (1/|G|) Sg 1 G |Xg|

 At first sight, this doesn't look like a very fertile result, but we shall see that it has a lot of useful consequences. It tells us how many orbits X has in terms of the size of G, which we may take as known, and the sizes of the fixed sets which are easy to calculate.

 Proof of not Burnside's Theorem Let the G-orbits in X be X1, X2,...,Xt. Then for all g in G, Xg is the union of the Xig and hence |Xg| = Si=1,...t |Xig|.

 But G is transitive on each orbit, so by Lemma 12.1, 
|G| = Sg 1 G |Xig|. Hence for all i = 1,2,...,t, (1/|G|) S g 1 G|Xig|=1. Hence t = |OrbX(G)| = Si=1,...t [(1/|G|) S g 1 G|Xig|] = 
(1/|G|) S g 1 G|Xg|.

 Of the many applications of Not Burnside's Theorem, the most famous is a method of counting "patterns", which is best explained by means of Examples.
 

 .

Examples

How many essentially different ways are there to colour the faces of a cube red, white and blue?

A colouring of a cube in 3 colours is a function from the faces to the set {red, white, blue}, so there are 36 colourings of the cube. Two colourings are called equivalent if each can be obtained from the other by a rigid motion of the cube. For example all the 6 colourings in which one face is white and all the others red are equivalent. A pattern is an equivalence class of colourings, and the question is really -- how many patterns are there? In other words, if we construct a set of child's cubes by colouring each face in one of three colours, how many distinguishable cubes do we get?

 In the language of group actions, let X be the set of colourings and G the octahedral group. A pattern is an orbit of G, and we have to count the number of orbits. The only systematic way to do this is to use not Burnside's Theorem, because we know |G| and can easily compute Xg.

 We need to know, for each g in G, how many colourings of the cube g leaves fixed. For example, let g be an edge rotation. If the faces of the cube are called T,B,N,E,S and W, then g switches T and E, B and W and N and S. Hence any colouring fixed by g has the same colours on T and E, B and W and N and S. There ar 33 such colourings, so |Xg| = 33. Since the four edge rotations are conjugate, and conjugate elements have the same size fixed sets all the edge rotations g have |Xg| = 33. By similar arguments, we can construct the following table:
 
 

Rotation Number Xg Contribution to total
Identity 1 36 729
Corner 8 32 72
Edge 6 33 162
Face, angle p 3 34 243
Face, angle p/2, 3p/2 6 33 162
Total 24 1368

Therefore the number of patterns = number of orbits = 1368/24 = 57. This includes the patterns in which not all the colours are used. There are 3 monochrome patterns, and using the same method you can compute that there are 24 two-colour patterns, and hence 30 patterns using all three colours.
 
 

How many essentially different necklaces are there containing 5 white and five black beads?

This time we have to count patterns of necklaces. The number of colourings is {10 choose 5} = 252, since we just have to choose the positions of the white beads from the ten possible positions. The group acting on the colourings is D10, since we get equivalent patterns by rotation or by turning the necklace over. There are 8 conjugacy classes, 
  1. the identity;
  2. rotation by p/5, 
  3. rotations by 2p/5 and 8p/5,
  4. rotations by 3p/5 and 7p/5,
  5. rotations by 4p/5 and 6p/5,
  6. rotation by p ;
  7. reflection in line joing a pair of opposite corners;
  8. reflection in a line joining the mid-points of a pair of opposite sides.
As in the previous example we draw up a table to count fixed points:
Conjugacy class Number Xg Contribution to total
(1) 1 252 252
(2) 2 0 0
(3) 2 2 4
(4) 2 0 0
(5) 2 2 4
(6) 1 0 0
(7) 5 12 60
(8) 5 0 0
Total 20 320

Hence the number of patterns = number of orbits = 16. See if you can draw the 16 patterns.
 
 

The number of conjugacy classes in a group.

Let G be a group and consider G acting on G by conjugation. That is, elements of G are equivalent if and only if they are conjugate. So the patterns are the conjugacy classes and the fixed set of any g is Gg = {h : h-1gh = g} = CG(g). 

So the number of conjugacy classes = |OrbGG| = 
1/|G| Sg 1 G|CG(g)|. But each CG(g) is a subgroup of G, so this number is just Sg 1 G 1/|[G:CG(g)]|.

 (CHECK this equation for A4). 

 .
. Table of Contents.

 To Continue

To return to Page 1, click here .

 Last update December 2 1999

Author: Phill Schultz, schultz@maths.uwa.edu.au

 .