Group actions, colorings and Burnside’s lemma

What are group actions?

We begin by semi-rigorously defining what a group action is. Now, it is a bit silly to try to define what group actions are without the prerequisite knowledge of what a group is. The definition of what a group is can be found in many places on the internet with good introductions on youtube, but for our purposes the rigorous background is not that important in my opinion. I will almost ceirtanly make a page on groups at some point, in which case I shall link to it here.

For this little introduction and demo we will introduce group
actions as follows.

Loosely speaking, a group $(G,\circ)$ (usually denoted $G$ when the operation $\circ$ is obvious) is a set $G$ and a binary operation $\circ : G \times G \to G$ which acts as multiplication on the elements of $G$. For some intuition common examples of groups are $\mathbb Z$ with addition, $\mathbb R\setminus\{0\}$ with multiplication. Some fun, and perhaps surprising at first, examples of groups are the bijections on $[n]$ under function composition, and the configurations of the standard Rubik’s cube generated by $\{F,B,U,D,L,R\}$.

An action of a group $G$ on a set $S$ is an operation that takes an element of $G$ and an element of $S$ and returns an element of $S$ in a way which makes sense. So a group action $\iota$ is a function

satisfying

for all $g,h \in G$ and all $x \in X$. Here $e \in G$ denotes the identity element of $G$ (the element which does nothing).

Some examples include the Rubik’s cube group acting on $48$ colored stickers or the physical corner and edge pieces of the cube, and the symmetric group $S_{52}$ acting on the $52$ positions in a standard deck of cards.

Why group actions are useful

A surprisingly common problem in mathematics is that the objects we are counting have symmetries.

Suppose we color the four vertices of a square. If we use $k$ colors, then the naive count is simply

There are four vertices, and each one gets one of $k$ colors. Easy.

But this count is a little dishonest if we care about the square itself rather than the particular drawing of it on the page. Rotating or reflecting the square should not always give us a genuinely new coloring. It is often the same coloring, just viewed from a different angle.

This is where group actions are useful.

A group action is a systematic way for a group of symmetries to act on a collection of objects. In this case, the symmetry group of the square acts on the set of vertex colorings. Two colorings should be considered the same if one can be transformed into the other by rotating or reflecting the square.

Orbits and stabilizers

The orbit of a coloring is the collection of all colorings you can reach from it by applying symmetries. These are the versions of the coloring that we agree to count as the same.

The stabilizer of a coloring is the collection of symmetries that leave it unchanged. Some colorings have lots of symmetry. Some have almost none.

For a square, there are eight symmetries in total: four rotations and four reflections. The orbit-stabilizer theorem says that

In this case, that means

The interactive demo above lets you see this directly. A very symmetric coloring has a small orbit and a large stabilizer. A generic-looking coloring has a large orbit and a small stabilizer.

Burnside’s lemma

The final counting trick is Burnside’s lemma. It says that the number of genuinely different objects is the average number of objects fixed by a symmetry:

For square vertex colorings, the group $G$ is the symmetry group of the square. Each symmetry permutes the four vertices. A coloring is fixed by a symmetry exactly when all vertices in the same cycle have the same color.

That is why the identity fixes $k^4$ colorings, a 90-degree rotation fixes only $k$ colorings, and a diagonal reflection fixes $k^3$ colorings.

So for the square we get

For example, with two colors there are $2^4 = 16$ raw colorings, but only

different colorings up to symmetry.

Some applications

This example is quite small and might seem pretty silly and inconsequential, but the underlying idea is central in plenty of areas of mathematics, and even outside mathematics.

For instance, symmetry is fundamental in physics. Noether’s theorem says, roughly, that continuous symmetries of a physical system give rise to conservation laws. Time-translation symmetry corresponds to conservation of energy, space-translation symmetry to conservation of momentum, and rotational symmetry to conservation of angular momentum.

Group actions also show up in chemistry, where symmetries help us recognize when molecular structures should be considered the same. More generally, this kind of thinking appears whenever we care about objects only up to symmetry: necklaces, graphs, tilings, molecules, physical systems, and plenty of other things.