Burnsides lemma and beyond: Permutations of vertices and color by Lucas Wagner A harmless problem How many distinguishable ways are there to color a 33 checkerboard with 3 colors, Red, White, and Blue, if two colorings are indistinguishable through rotations, reflections, shiftings, and also a cycle of colors (RWBR)? (What does that even mean?) Patriotic Examples RWBR

So lets solve it! There are 39 = 19,683 possible colorings. The distinguishable ones would be tedious to find, and we wouldnt even know when to stop looking. Lets develop the background we need in group theory to tackle this problem. Groups A set of elements, G, along with one operation, *, is a group if the following hold: 1. The group is closed WRT *. For every a, b in G, a*b is also in G. 2. * is associative.

a*(b*c) = (a*b)*c for every a, b, c in G. 3. There is an identity element, e, in G. a * e = e * a = a for every a in G. 4. There exist inverses for all a in G. a * a-1 = a-1 * a = e for some a-1 in G. Subgroups (H, *) is called a subgroup of (G, *) if the set H is contained in the set G and it is also closed and has inverses. Example: Z6 = {0, 1, 2, 3, 4, 5} Subgroups are {0}, {0, 3}, {0, 2, 4}, and Z6. Lagranges ber-theorem for finite groups states that the size of H must divide the size of G.

Applying groups Our main problem boils down to what sorts of movements (e.g. rotations, reflections) that we allow for our checkerboard. These movements can be abstracted to elements in a subgroup of a symmetric group, which are permutations on the integers. Permuting checkerboard vertices Start small: consider the 22 case. Label the vertices, the interesting points that are moved around. The following is the identity permutation:

(1)(2)(3)(4) Permute those vertices (1 2 3 4) (1 2)(3 4) The operation Every group has an operation. The symmetric groups operation is composition, , which is not necessarily commutative, and works right to left. E.g., (1 2)(3 4)(1 2 3 4) = (1)(2 4)(3)

Expanding our set We need a group for our theory to work. If we have an large group of permutations, we dont want to write them all out by hand. Start with a small set of permutations that represent each of the basic movements. e.g. Rotation by 90 and reflection Let a computer expand the set through composition. E.g. Rotation by 90 twice becomes rotation by 180. This is a surefire way to guarantee closure, which for a subset of a finite group guarantees a subgroup.

Symmetries of the square For the 22 checkerboard, there are 8 elements in our group G. g permutation Identity (1)(2)(3)(4) 90 rotation (1 2 3 4)

180 rotation (1 3)(2 4) 270 rotation (1 4 3 2) Symmetries (ctd.) g permutation

H reflection (1 4)(2 3) V reflection (1 2)(3 4) D1 reflection (1)(2 4)(3) D2 reflection (1 3)(2)(4)

Permutations acting on the colorings Now we can begin to talk about coloring our checkerboards. With the 22 checkerboard, lets consider an easy case: two colors, red and white. Let S be the set of all possible colorings. Then the size of S is |S| = 24 = 16. Some observations If u, v belong to S, and u and v are indistinguishable WRT our group G, then there is some h in G such that h(u) = v.

In this example, h is the 90 rotation. Orbits Making general this observation, the collection of indistinguishable objects that an element s of S belongs to is: Orb(s) = {g(s) for all g in G} The orbit is the set of all colorings which are reachable by the action of the elements of G on a particular coloring, s. Stabilizers Fact: The following is a subgroup of G. G s {g G | g(s) s}

Gs is called the stabilizer of s. It is the set of all permutations, g, that leave a particular coloring, s, unchanged. Orbits and stabilizers Since Gs is a subgroup of G, the size of Gs must divide the size of G by Lagranges theorem. Neat fact: |Orb(s)| is exactly the divisor. i.e. |G| = |Gs| |Orb(s)| If u and v are indistinguishable colorings, then they belong to the same orbit. Therefore |Gu| = |Gv|. Orbit and stabilizer example

Let s be this particular coloring: There are four permutations that leave the coloring as it looks nowthe identity, 180 rotation, and reflections over the diagonals. Therefore |Gs| = 4. Example (conclusion) Recall that the orbit is the set of all colorings which are reachable by the action of the elements of G. With a 90 rotation, one other coloring is reached. Therefore |Orb(s)| = 2. Therefore |Gs| |Orb(s)| = 4 2 = 8 = |G|.

Preparation for the lemma Let N be the number of distinguishable objects, which it is the goal of our problem to find. If we can count the number of total orbits, we would know how many distinguishable objects there are. We could find N. But how do we do that? Tell us now, Lucas! Burnsides lemma Historically, Burnside proved the lemma in

Theory of Groups of Finite Order in 1897. But Cauchy knew of it in 1845 and Frobenius in 1887. The lemma that is not Burnsides 1 N G ( g ) gG where

( g ) s S | g ( s ) s which is the size of the set of colorings in S which are unchanged when acted on by g. Burnside example How many red and white colored 22 distinguishable checkerboards are there? For each of the 8 group elements, find (g). For the 90 rotation, = 2. Why? Answer: There are only two colorings in S that are unchanged when rotated by 90. Example (ctd.) For 180 rotation, there are four elements

of S that are unchanged. So here, = 4. 2 choices each for top two, then the bottom ones must be whatever their kitty corner was: Example (ctd.) Recall |S| = 24 = 16. g permutation (g) Identity

(1)(2)(3)(4) 24 90 rotation (1 2 3 4) 21 180 rotation (1 3)(2 4) 22

270 rotation (1 4 3 2) 21 Example (ctd.) Notice a pattern yet? g permutation

(g) H reflection (1 4)(2 3) 22 V reflection (1 2)(3 4) 22 D1 reflection

(1)(2 4)(3) 23 D2 reflection (1 3)(2)(4) 23 Example (conclusion) The number of colors, raised to the number of cycles for a given permutation, will give that .

The expression for N gives 1 N G 1 ( g ) (16 2 4 2 4 4 8 8) 6 8 gG Proof of the lemma Make a table with g and s. Put 1s wherever gi(sj) = sj and 0s everywhere else. s1

s2 s|S| g1 0 0

1 g2 1 1 0 g|G|

0 1 1 sS g G

Elements of the group Colorings Proof (ctd.) Start counting up the total number of ones: s1 s2 s|S|

g1 0 0 1 ( g1 ) g2 1

1 0 ( g2 )

g|G| 0 1 1

( g|G| ) Gs1 Gs 2 Gs|S| f sS g G

Proof (ctd.) The seemingly uninteresting result is: G sS s f ( g ) gG Which we will use it later. It is easier to find (g) than Gs. Typically |G| is much smaller than |S|.

Proof (ctd.) Now pick some coloring t, and sum up the stabilizer sizes, |Gs|, for all elements s in the orbit of t. Since the elements of an orbit have the same stabilizer size, |Gt|, G sOrb ( t ) s Gt

1 G t sOrb ( t ) Gfact. by that starred Orb(t ) Proof (ctd.) So for each orbit whose elements we sum |Gs| over, we will get exactly one |G|. If we sum over all colorings in S, we will

get exactly the number of orbits times |G|. G s N G sS I see an N. Victory is nigh. Proof (conclusion) Then use the uninteresting result:

( g ) G gG s N G sS to get this beauty: 1 N G

( g ) gG quod erat demonstrandum. Implementation Code can be written to do most of the tediousness. Think up any permutations with anything in mind (e.g. hexagons, tetrahedra, etc.) and get a group. The computer can do the calculations for you, summing up all of the (g), where (g) is just [number of color choices] to

the [number of vertex cycles of g]th power. Extensions to color cycling For every group element g, include color cycles in addition to the vertex cycles. For example, with the 22 checkerboard, allow the switching of colors. Then the usual 90 rotation that leaves the colors alone is [ (1 2 3 4), (R)(W) ] and [ (1 2 3 4), (R W) ] rotates 90 and cycles the colors: This doubles the size of the group, to 16. Finding (g) with color cycling Consider the ith vertex cycle of g, i ranging

from 1 to the number of vertex cycles in g. Let mi(g) be the number of color choices for the ith vertex cycle of g. (g) will then be the product of all mi(g). To calculate mi(g), consider each cycle within the color permutation. Add in the length of that cycle (its number of colors) if it divides the length of the ith vertex cycle. Example calculations Group elements, g m1 m2

m3 (g) [ (1 2 3 4), (R W) ] 2 n/a n/a 2

[ (1 2)(3 4), (R W) ] 2 2 n/a 4 [ (1)(2 4)(3), (R)(W) ] 2 2

2 8 [ (1)(2 4)(3), (R W) ] 0 2 0 0

!!! Example (ctd.) There is no way to color a checkerboard such that a diagonal reflection + color switch preserves the original coloring. [ (1)(2)(3)(4), (R W) ] suffers from a worse case of the same problem. Therefore for these cases is zero. sad Example (conclusion) 1 Use the lemma: N

G ( g ) gG 1 16 2 4 2 4 4 8 8 64 N 16 0 2 4 2 4 4 0 0 16 There are only 4 distinguishable boards. Initial problem: solved Question:

How many distinguishable ways are there to color a 33 checkerboard with 3 colors, Red, White, and Blue, if two colorings are indistinguishable through rotations, reflections, shiftings, and also a cycle of colors (R W B)? Answer: 150 out of the total 19,683. Case closed. Applications? Sources Modern Algebra by John Durbin Modern Algebra II Notes, lectures by Dr. Biebighauser http://en.wikipedia.org/wiki/Burnside's_lemma

http://en.wikipedia.org/wiki/William_Burnside http://en.wikipedia.org/wiki/Cauchy http://en.wikipedia.org/wiki/Ferdinand_Georg_Frobenius Coding done in Python Question Time (e.g., What just happened?)