Twenty-four ways to set a cube down

A symmetry of a square does something to everything drawn on the square. It carries a corner to a corner, an edge to an edge, a diagonal to a diagonal, and a colouring of the corners to another colouring. The eight symmetries were found by testing every relabelling and keeping the ones that move no distance; what they do to the things on the square has not yet been asked.

Ask it, one thing at a time, and two numbers come out of each. One is how many places the thing can be carried to. The other is how many of the eight motions leave it exactly where it was.

A corner can go to any of four corners and is left alone by two motions: doing nothing, and the flip whose axis runs through it. A diagonal can go to only two places — it is either the diagonal it was or the other one — and is left alone by four motions, since the half turn and two of the flips all keep it in place. A colouring with two adjacent dark corners can be carried to four colourings and is fixed by two motions; one with alternating corners has only two images and four motions that leave it alone.

The rows have nothing in common except the group. A corner is not a colouring and a diagonal is not an edge. Yet every row multiplies to eight, and that is a theorem rather than a pattern.

Two names for the two numbers #

The set of places a thing can be carried to is its orbit. The set of motions that leave it where it is is its stabiliser. The claim the table makes is

$$|\text{orbit of } x| \times |\text{stabiliser of } x| = |G|,$$

for any group $G$ acting on anything at all, and for any $x$ it acts on.

The stabiliser is always a subgroup. If two motions each leave $x$ alone, so does doing one after the other; doing nothing leaves $x$ alone; and undoing a motion that leaves $x$ alone also leaves $x$ alone. So the stabiliser is one of the closed collections that cut the group into blocks, and that is where the proof lives.

The orbit, by contrast, is not a subgroup of anything. It is a set of corners, or of colourings, or of whatever the group is moving. The theorem therefore connects a structure inside the group — a subgroup and its blocks — with a structure outside it, a set of positions. It is the first result in the subject in which the group is used to do something rather than examined for its own sake, and nearly everything later in group theory is built on it.

The equation also turns one hard count into two easy ones. Listing all rotations of a solid directly is tedious and error-prone. Counting the corners and then the rotations that pin one corner is easy, because the second question is about a much smaller group that can often be seen at a glance.

Why every row is the group #

Sort the eight motions by where they send corner 1.

Two motions land in the same row exactly when they send corner 1 to the same place. Now take two motions $g$ and $g'$ in one row. Doing $g'$ and then undoing $g$ carries corner 1 to $g'$'s target and then back home, so $g^{-1}g'$ is in the stabiliser. Rearranged, $g'$ is $g$ followed by something from the stabiliser — so every row is exactly $g$ composed with the stabiliser, which is a coset.

The figure makes the three facts visible and then counts them. Each row has as many motions as the stabiliser, because composing with $g$ is reversible and cannot merge two different motions into one. Different rows are different cosets, because they send corner 1 to different places. And there is one row for each place in the orbit, because each place is reached by something. So the group is chopped into (orbit) rows of (stabiliser) motions each, and the product is the size of the group.

That is a bijection, and it is worth stating it as one because the bijection is what survives when nothing is finite. The cosets of the stabiliser correspond exactly to the points of the orbit, with $g\,\mathrm{Stab}(x) \mapsto g(x)$. In an infinite group the counting version of the theorem is meaningless, but the correspondence still holds, and it is how a space of positions gets identified with a space of cosets in geometry — the sphere, for example, is the rotations of space with the rotations about one axis collapsed out.

The equation puts Lagrange’s theorem to work outside the group. An orbit’s size is the index of a subgroup — the number of its blocks — so every orbit has a size dividing the order of the group. The eight symmetries of a square can move a thing to one, two, four or eight places, and never to three, five, six or seven. The colourings in the essay on colourings that cannot be told apart fell into classes of sizes one, two and four, and that was not a feature of the particular colourings chosen. It was forced.

The cube, counted three ways #

The same equation counts the rotations of a solid without listing any.

A corner of a cube can be carried to any of eight corners, and the rotations that keep one corner fixed are the turns about the long diagonal through it: a third of a turn, two thirds, and none. Eight times three. An edge can go to any of twelve edges, and is kept by two rotations — doing nothing, and the half turn about the axis through its midpoint and the midpoint of the opposite edge. Twelve times two. A face can go to any of six, and is kept by the four quarter turns about the axis through its centre. Six times four.

Three different axes, three different stabilisers, three different orbits, and the same product. A count of rotations obtained by listing them is only as trustworthy as the listing; a count obtained three times independently, with three different geometric pictures agreeing, is harder to get wrong. The figure does not rely on the arithmetic either: it tries every candidate rotation, keeps the ones that carry the cube onto itself, and only then compares the survivors with each of the three products.

The essay on the five solids and their three groups counts the same rotations by a fourth route, through directed edges, where the stabiliser is trivial and the product is simply twice the edge count. That route is the cleanest, because a directed edge pins the cube completely. What the corner, edge and face counts add is the information in the stabilisers themselves. The orders 3, 2 and 4 are the orders of the turns about the three kinds of axis, and they are what the classification of rotation groups in that essay is built from.

Five solids, fifteen products #

Doing the same thing for all five regular solids gives a table in which every row has to agree with itself.

Two pairs of rows are mirror images, with the first and third columns exchanged. The cube’s eight corners held still by three rotations each become the octahedron’s eight faces held still by three; the cube’s six faces with four become the octahedron’s six corners with four. The same happens between the dodecahedron and the icosahedron, and the tetrahedron is its own partner. This is duality — putting a point at the centre of every face of one solid gives the other — and in the table it is visible as an exchange of columns, because a rotation that keeps a face fixed keeps the dual’s corresponding corner fixed and nothing else about it changes.

The table also contains Euler’s formula in disguise. For the cube, the three orbit sizes are 8, 12 and 6, and each is the group’s order divided by a stabiliser order: 24/3, 24/2 and 24/4. So $V - E + F$ is $24(1/3 - 1/2 + 1/4)$. That this equals two is the statement that every corner pays for itself, and here it has turned into an equation about the orders of turns: for a solid with $p$-sided faces meeting $q$ at a corner, the orbit sizes are $N/q$, $N/2$ and $N/p$, so $N(1/q - 1/2 + 1/p) = 2$. That one equation, with $N$ positive, is why there are only five regular solids: $1/p + 1/q$ must exceed a half, and only five pairs of whole numbers from three upward manage it.

Sixteen trees, split by relabelling #

The theorem is not about shapes. Anything a group moves will do, and one of the most useful things to move is a labelling.

Four labelled points can be joined into a single tree in sixteen ways, and the proof of that count builds a code for every tree. The symmetric group — the twenty-four ways of relabelling four points — acts on those sixteen trees by relabelling, and two trees lie in one orbit exactly when they are the same tree with the labels moved.

A path through four points is left unchanged by exactly two relabellings — doing nothing, and reversing it end to end. So its orbit has $24/2 = 12$ members, and there are twelve labelled paths. A star is left unchanged by any relabelling of its three outer points while the centre stays put, which is $3! = 6$ relabellings, so there are $24/6 = 4$ stars, one for each choice of centre. Twelve and four make sixteen, which is Cayley’s formula $n^{n-2}$ at $n = 4$ recovered by a completely different argument.

At five points the same count runs as $120 \div 2 + 120 \div 2 + 120 \div 24 = 60 + 60 + 5$, which is 125, which is $5^3$.

The surprising thing is that the two sides of this identity are about different objects. Cayley’s formula counts trees with labels and has a clean answer. The orbits count trees without labels — shapes — and weight each shape by $n!$ over its number of symmetries. So

$$\sum_{\text{shapes } T} \frac{n!}{|\mathrm{Aut}(T)|} = n^{n-2},$$

a sum over the unlabelled trees, which have no formula at all, that nevertheless adds up to something as simple as $n^{n-2}$. Every shape contributes at most $n!$, so there are at least $n^{n-2}/n!$ shapes; since $n!$ is roughly $(n/e)^n$ by Stirling’s estimate, the number of distinct tree shapes on $n$ points grows at least as fast as $e^n$ divided by a power of $n$. That a lower bound on unlabelled trees drops out of a formula about labelled ones is the kind of transfer the orbit–stabiliser count exists to make.

The same sorting applies to every graph on four labelled points, not only the trees. There are sixty-four of them, one for each subset of the six possible edges, and they fall into eleven kinds whose orbit sizes — 1, 6, 12, 3, 12, 4, 4, 12, 3, 6, 1 — are twenty-four divided by the size of each kind’s symmetry group, and add to sixty-four. Two graphs in one orbit are isomorphic, and deciding whether two given graphs are in one orbit is the graph isomorphism problem, which for large graphs is a genuinely hard computational question.

The group moving itself #

The richest action of all is a group acting on its own elements. Let $g$ send $x$ to $g x g^{-1}$ — do $g$’s inverse, then $x$, then $g$ — which is $x$ seen from a different vantage point. For the square’s symmetries, conjugating a flip by a quarter turn gives the flip in the axis a quarter turn round.

The orbits of this action are the conjugacy classes. The stabiliser of $x$ is everything with $g x g^{-1} = x$, which is everything that commutes with $x$.

Adding the class sizes gives the class equation: $8 = 1 + 1 + 2 + 2 + 2$ for the square, and $10 = 1 + 2 + 2 + 5$ for the pentagon, whose five flips form a single class because in an odd polygon every flip axis runs from a corner to the middle of the opposite edge, and a turn carries any one of those axes to any other. Each term is an orbit size, so each divides the order of the group. The classes of size one are the elements that commute with everything, which form the centre.

Now suppose the group has a prime-power order, $p^k$. Every class has a size dividing $p^k$, so every class has size 1 or a multiple of $p$. The sizes add to $p^k$, a multiple of $p$. So the classes of size one, taken together, number a multiple of $p$ — and there is at least one, the identity. So there are at least $p$ of them, and every group of prime-power order has a non-trivial centre.

For the square that is $\{e, r^2\}$: the half turn commutes with every symmetry of the square, which is unsurprising once seen and not at all obvious before. For a group of order $p^2$ the argument goes one step further and shows the group is commutative. A structural fact about every group of order 8, 9, 16, 25 or any other prime power has come out of adding up orbit sizes and reading the total modulo a prime.

What the pictures do not reach #

Every figure here is a finite group acting on a finite set, and the counts were checked by applying every element to every object. That checks the equation where it was drawn and nowhere else. The general statement rests on the argument in the second section, which uses nothing about squares or cubes — only that a stabiliser is a subgroup and that composing with a fixed element is reversible.

The figures also say nothing about which orbit a thing lies in. The equation relates an orbit’s size to its stabiliser’s size, and it never produces the orbit. For the colourings, knowing that a colouring’s orbit has size four does not say which four colourings are in it; for graphs, knowing that a kind of graph has twelve labelled copies does not say whether two given labelled graphs are copies of each other. The count is easy and the membership is hard, and nothing in the equation bridges the gap.

And the solids were drawn from one fixed viewpoint, with one corner, one edge and one face marked. The rotations were found numerically, by comparing coordinates to six decimal places, which is a measurement rather than a proof that no rotation was missed. What makes the count trustworthy is that the three products agree with each other and with twice the number of edges — four checks that could each have failed independently.

Still open: telling two orbits apart quickly #

The graph count above sorted sixty-four graphs into eleven orbits by applying all twenty-four relabellings to each. For $n$ points that is $n!$ relabellings, which is hopeless once $n$ is in the dozens. Deciding whether two labelled graphs lie in the same orbit — whether they are isomorphic — has no known polynomial-time method.

It is also not known to be hard in the way many search problems are. In 2015 László Babai announced an algorithm running in quasipolynomial time, $\exp((\log n)^c)$ for a constant $c$, far faster than anything previously known and, after a correction he made in 2017, generally accepted. Whether graph isomorphism can be decided in polynomial time remains open. The obstacle is exactly the one this essay keeps meeting: counting an orbit is arithmetic, while recognising one requires understanding the stabilisers — the symmetries of the graphs — well enough to rule out the ones that are not there.

A related count is settled. Since almost every large graph has no symmetry except the identity, almost every orbit has the full size $n!$, and the number of unlabelled graphs on $n$ points is asymptotically $2^{\binom{n}{2}}/n!$ — the orbit–stabiliser equation with the stabiliser trivial. The labelled count divided by the relabellings is the answer, up to an error that vanishes, and it is the same sentence that gave twelve paths and four stars.

One count, read four ways #

The places a thing can go, times the motions that keep it still, is the size of the group. For a square it gave eight five times over from five unrelated things; for a cube it gave twenty-four from a corner, an edge and a face; for trees it split Cayley’s count into shapes weighted by their symmetry; and applied to the group acting on itself it forced a centre on every group of prime-power order.

The proof is one sentence about cosets, and it is the same sentence each time. The reason it keeps paying is that the two numbers it multiplies are usually easy to find separately — how many places, and what holds one place fixed — while the product is the thing that was wanted and was hard to count directly. Next comes the question the table of orbit sizes invites but does not answer. Every orbit size divides the group’s order, so does every prime that divides the order turn up as the order of some element? It does, and the proof counts necklaces made of symmetries — beads turned round a loop, exactly as in the necklace proof of Fermat’s little theorem, with the beads replaced by elements of the group and the orbits of the turning doing the work the stabilisers did here.