Group actions and colorings · Thobias Høivik

When are two colorings actually different?

Suppose we color the four corners of a square.

If we have $k$ colors, there are obviously

k^4

ways to color the four vertices.

Four choices of vertex, $k$ choices each. Done.

Except perhaps not.

Imagine I draw this coloring on a piece of paper, then rotate the paper by $90^\circ$ .

rotating a coloring of the square to illustrate how this is not a new coloring — One of the k^4 colorings will correspond to this rotation, but it is not really a new coloring!

Did I just create a new coloring?

Probably not.

It is the same colored square, merely viewed from a different direction.

So if we care about the square itself, rather than its orientation on the page, $k^4$ is overcounting.

We need to be able to separate these duplicate instances! We should then want to be able to say when two colorings can be obtained from the other by a symmtery of the square.

Enter group actions!

Symmetries are moves

The square has eight ways of moving it around without changing its shape:

do nothing (equivalently, rotate by $360^\circ$ ),
rotate by $90^\circ$ ,
rotate by $180^\circ$ ,
rotate by $270^\circ$ ,
reflect it in four different ways.

These eight moves have some nice properties.

If you perform one symmetry and then another, the result is still a symmetry of the square.

There is a move which does nothing.

And every move can be undone.

That collection of reversible moves is a group.

For our purposes, that is enough intuition for now.

What is a group, actually?

A group is a set $G$ equipped with a binary operation

\circ:G\times G\to G

such that

the operation is associative,
there is an identity element $e\in G$ satisfying $e\circ g=g\circ e=g$ ,
every $g\in G$ has an inverse $g^{-1}\in G$ satisfying

g\circ g^{-1} = g^{-1}\circ g = e.

For the symmetries of the square, the elements of $G$ are geometric transformations and the operation is composition.

I will write $D_4$ for the eight-element symmetry group of the square.

Now let the moves act on something

The symmetries of the square are interesting by themselves.

But what we actually care about is what happens when those symmetries are applied to our colorings.

Take a coloring.

Rotate the square.

The colors move with the vertices, producing another coloring.

Reflect it.

Again, we get another coloring.

So we have:

\text{symmetry} + \text{coloring} \longrightarrow \text{coloring}.

That is the essential idea of a group action.

The below demo lets you choose a coloring of the square, apply some symmetry of the square and see how many “fake different” colorings you can make. “Fake different” refering to those instances of overcounting.

Try choosing an asymmetric-looking coloring and applying the different symmetries.

Then try a very symmetric coloring.

Notice how some colorings generate lots of visibly different versions of themselves, while others barely change at all.

That distinction will lead to something interesting below!

Current coloring

Color the square

Number of colors: 2

Selected symmetry

rotate 90°

Rotate the square clockwise by 90 degrees.

before

→

after

Orbit

All versions of this coloring

The orbit is the collection of colorings reachable by rotating or reflecting the square. These are the colorings we agree to count as the same.

orbit size: 2

Stabilizer

Symmetries that do nothing

The stabilizer consists of the symmetries that leave this particular coloring unchanged.

er²d₁d₂

stabilizer size: 4

Notice the pattern: orbit size × stabilizer size = 8, the size of the symmetry group of the square.

Burnside's lemma

Counting without overcounting

There are 16 raw colorings of the four vertices using 2 colors. Burnside's lemma counts the genuinely different ones by averaging how many colorings are fixed by each symmetry.

raw colorings2⁴ = 16

unique up to symmetry6

symmetry	cycles	fixed colorings
identity	(A) (B) (C) (D)	2⁴ = 16
rotate 90°	(A B C D)	2¹ = 2
rotate 180°	(A C) (B D)	2² = 4
rotate 270°	(A D C B)	2¹ = 2
vertical reflection	(A B) (C D)	2² = 4
horizontal reflection	(A D) (B C)	2² = 4
main diagonal reflection	(A) (B D) (C)	2³ = 8
other diagonal reflection	(A C) (B) (D)	2³ = 8

(16 + 2 + 4 + 2 + 4 + 4 + 8 + 8) / 8 = 6

Define a group action precisely

Let $G$ be a group and let $X$ be a set.

An action of $G$ on $X$ is a function

G\times X\to X, \qquad (g,x)\mapsto g\cdot x,

satisfying

e\cdot x=x

and

g\cdot(h\cdot x) = (gh)\cdot x

for every $g,h\in G$ and $x\in X$ .

The first condition says that the identity move really does nothing.

The second says that acting by $h$ and then by $g$ agrees with first composing the two group elements and then acting once.

In our example,

G=D_4

and $X$ is the set of all vertex colorings of the square.

Orbits: all the ways the same thing can look

Take one particular coloring and apply every symmetry of the square to it.

You obtain a collection of colorings.

That collection is called its orbit.

Intuitively:

The orbit contains all the appearances of an object that we have decided should count as the same object.

If two colorings lie in the same orbit, then one can be rotated or reflected into the other.

So when we say

“count colorings up to symmetry”

we are really counting orbits.

Stabilizers: which moves fail to change the object?

Now ask the opposite question.

Rather than asking

Which colorings can I reach?

ask

Which symmetries leave this coloring exactly as it is?

Those symmetries form the stabilizer of the coloring.

A completely generic-looking coloring might only be fixed by the identity.

A highly symmetric coloring may survive several rotations or reflections unchanged.

This creates a beautiful tradeoff:

the more symmetries an object has, the fewer distinct versions of it appear in its orbit.

For a square there are eight possible symmetries in total.

So if a coloring is fixed by four of them, it can only have two distinct appearances.

If it is fixed only by the identity, it has eight.

Orbit-stabilizer theorem

For $x\in X$ , define its orbit by

\operatorname{Orb}(x) = \{g\cdot x:g\in G\}

and its stabilizer by

\operatorname{Stab}(x) = \{g\in G:g\cdot x=x\}.

For a finite group,

|\operatorname{Orb}(x)| \cdot |\operatorname{Stab}(x)| = |G|.

Since the symmetry group of the square has eight elements,

|\operatorname{Orb}(x)| \cdot |\operatorname{Stab}(x)| = 8.

More generally,

|\operatorname{Orb}(x)| = [G:\operatorname{Stab}(x)].

But how do we actually count the orbits?

We now know what we want to count.

Every orbit corresponds to one genuinely different coloring.

Unfortunately, listing every coloring, computing its orbit, and then removing duplicates is not a particularly elegant way to count them.

Enter Burnside’s lemma!

Instead of looking at each coloring and asking where all the symmetries send it, we reverse the question.

Take each symmetry and ask:

How many colorings does this symmetry leave completely unchanged?

Call that number

|\operatorname{Fix}(g)|.

Burnside’s lemma says, roughly speaking, that

the number of genuinely different colorings is the average number of colorings fixed by a symmetry.

Formally,

|X/G| = \frac{1}{|G|} \sum_{g\in G} |\operatorname{Fix}(g)|.

What does each symmetry fix?

Start with the identity.

It moves nothing, so every coloring remains unchanged.

Therefore it fixes

k^4

colorings.

Now rotate by $90^\circ$ .

Every vertex moves to the next vertex.

For the coloring to look identical after the rotation, all four vertices must have the same color.

So only

k

colorings survive.

The same is true for the $270^\circ$ rotation.

A $180^\circ$ rotation pairs opposite vertices.

Each pair must have the same color, giving

k^2

fixed colorings.

A reflection across a diagonal leaves two vertices in place and swaps the other two.

That gives

k^3

fixed colorings.

There are two such diagonal reflections.

The other two reflections swap two pairs of vertices, giving

k^2

fixed colorings each.

Put everything together:

k^4 + 2k + k^2 + 2k^3 + 2k^2.

Hence

|X/D_4| = \frac{k^4+2k^3+3k^2+2k}{8}.

For two colors, there are

2^4=16

raw colorings, but only

\frac{ 2^4 + 2\cdot2^3 + 3\cdot2^2 + 2\cdot2 }{8} = 6

genuinely different colorings once rotations and reflections are treated as the same.

Why does Burnside’s lemma work?

Consider all pairs

(g,x)

such that

g\cdot x=x.

We can count these pairs in two different ways.

If we first choose $g$ , then the number of possible $x$ is

|\operatorname{Fix}(g)|.

So the total number of such pairs is

\sum_{g\in G} |\operatorname{Fix}(g)|.

Instead, fix one orbit $O$ .

For each $x\in O$ , there are

|\operatorname{Stab}(x)|

group elements fixing it.

Orbit-stabilizer gives

|O| \cdot |\operatorname{Stab}(x)| = |G|.

Therefore every orbit contributes exactly $|G|$ pairs.

If there are $|X/G|$ orbits, then

\sum_{g\in G} |\operatorname{Fix}(g)| = |G|\cdot|X/G|.

Dividing by $|G|$ gives

|X/G| = \frac{1}{|G|} \sum_{g\in G} |\operatorname{Fix}(g)|.

You can stop here

The central idea is surprisingly simple.

A group is, intuitively, a collection of reversible moves.

A group action lets those moves operate on some set of objects.

An orbit collects all objects which are equivalent under those moves.

A stabilizer records the moves which leave one particular object unchanged.

And Burnside’s lemma lets us count the orbits by averaging how many objects each symmetry fixes.

This is applicable to lots of cool stuff!

The square may seem like a contrived example, but the principle appears in a lot of interesting places.

A Rubik’s cube gives a group of legal moves acting on configurations of its pieces.

Permutations form groups acting on positions in a deck of cards.

Groups act on graphs, geometric objects, algebraic structures, solutions of equations, vector spaces, and many other things.

Whenever we say that two objects are “the same up to”

rotation,
reflection,
relabeling,
permutation,
change of coordinates,

there is a decent chance that a group action is hiding nearby.

Symmetry also sits extremely deep in physics.

Noether’s theorem connects continuous symmetries of physical systems with conservation laws: time-translation symmetry with conservation of energy, spatial translation with conservation of momentum, and rotational symmetry with conservation of angular momentum.