Groups

The last chapter ended with eight matrices. They’re the orthogonal $2 \times 2$ matrices that take a square centred at the origin to itself: four rotations and four reflections. Multiply any two, and you get one of the eight again. These matrices have their own $8 \times 8$ multiplication table, and nothing else is needed to work with them. The turns of the faces of a Rubik’s cube have a table like it, and so do the ways of shuffling a deck, and adding hours on a clock face. What do they have in common?

We’ll answer with puzzles: a cardboard square, a deck of cards, the fifteen puzzle and the Rubik’s cube. The cube has 43 quintillion positions, and by the end of the chapter we’ll be able to say of each one whether it can be solved, without even trying to solve it.

A cardboard square

Cut a square out of cardboard, draw a flag on it and put it into a square slot that fits it. In how many ways can it be taken out and put back so that it lies in the slot again? The flag is there so that the ways can be told apart: a blank piece of card doesn’t care how it lies, but we do.

The square can be rotated about its centre by $90^\circ$, $180^\circ$ or $270^\circ$ anticlockwise; we’ll call these rotations $r$, $r^2$ and $r^3$ (why, will become clear shortly). It can be flipped over, reflected in one of four axes: horizontal $h$, vertical $v$, or the diagonals $d$ and $d'$. And it can be left alone; that’s a way too, and we’ll call it $e$. Eight in all. Each of them is a symmetry of the square in the sense of chapter 23, that is, a motion taking the figure to itself. There are no others, and that’s worth proving: we’ll see what the number eight is made of.

The trick is to follow not the whole square but two neighbouring vertices.

Number the vertices of the card anticlockwise: $1, 2, 3, 4$. A symmetry takes vertices to vertices. Indeed, two points of a square are at most a diagonal apart, and a distance equal to the diagonal occurs only between opposite vertices. A motion preserves distances, so such pairs go to such pairs. So vertex $1$ lands in one of the four corners of the slot; call it $1'$. Vertex $2$ is a neighbour of vertex $1$: between them is a side $a$, not a diagonal $a\sqrt2$. Distance is preserved, so its image $2'$ is also a corner next to $1'$. A corner has two neighbours, and for any choice of $1'$ there are two places left for $2'$. Vertex $4$ is the other neighbour of vertex $1$, so it has to take the other corner next to $1'$, $4'$. The points $1$, $2$ and $4$ don’t lie on one line, and by the three-point lemma a motion is determined entirely by where it sends them. So the choice of $1'$ and $2'$ fixes the symmetry completely. There are at most $4 \cdot 2 = 8$ symmetries. And all eight options occur. The four rotations send vertex $1$ to four different corners, and vertex $2$ follows anticlockwise. The four reflections also send $1$ to all four corners, but $2$ ends up clockwise from it.

Two motions can be carried out one after the other, and the result is again one of the eight: if each returns the card to the slot, both in a row do too. We’ll write them in the same order as composition of functions and the product of matrices: $a \circ b$, or simply $ab$, means “first $b$, then $a$”. Then $r^2 = r \circ r$ is the square turned twice by $90^\circ$, hence the names of the rotations.

It’s best to fill it in yourself. The widget below carries out each motion slowly: rotations turn the card, while reflections flip it over, and then the flag is seen from the back, mirrored.

Two things catch the eye even when half the table is filled. First: $r \circ h = d$, while $h \circ r = d'$. Reflecting and then rotating isn’t the same as rotating and then reflecting, and the table isn’t symmetric about its diagonal. Second: in every row and every column all eight symmetries occur exactly once each, like the digits in a sudoku. The first is a peculiarity of the square. The second, as we’ll soon prove, holds for any such table.

We can also see where the table from the last chapter came from. Each symmetry of the square is an orthogonal matrix: $r = \left(\begin{smallmatrix} 0 & -1 \\ 1 & 0 \end{smallmatrix}\right)$, $h = \left(\begin{smallmatrix} 1 & 0 \\ 0 & -1 \end{smallmatrix}\right)$ and so on, and carrying out motions one after another means multiplying the matrices. Check: $rh = \left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)$. This matrix swaps the coordinates, that is, reflects in the diagonal $y = x$: that’s $d$.

How many symmetries does a rectangle that isn’t a square have?

Argue as for the square. Vertices again go to vertices, and vertex $1$ can land in any of the four corners. But now the neighbours aren’t on an equal footing: a long side has to go to a long side, so there’s only one place left for vertex $2$. We get $4 \cdot 1 = 4$ symmetries: $e$, the rotation by $180^\circ$, and the reflections in the horizontal and vertical axes. The reflections in the diagonals have gone: a diagonal of a rectangle doesn’t bisect its angles.

Four rules

Let’s step away from the cardboard. What do we need from a set of actions for it to be handled like the symmetries of a square? Just four rules. The first definition of a group tied neither to symmetries nor to permutations was given in 1854 by the English mathematician Arthur Cayley, together with the tables that now bear his name. Today it’s written like this.

The symmetries of the square satisfy all four. We’ve seen closure. Associativity holds for any transformations: both $(a \circ b) \circ c$ and $a \circ (b \circ c)$ mean the same thing, first $c$, then $b$, then $a$. The identity element is $e$. The inverse of a rotation is a rotation by the same angle the other way, $r^{-1} = r^3$, and each reflection is its own inverse: flip the card twice, and it lies as it was.

The axioms don’t allow factors to be swapped, and rightly so: for the square $rh \ne hr$. Groups in which $ab = ba$ for any two elements are called abelian, after the Norwegian mathematician Niels Henrik Abel. The number of elements of a finite group is called its order and written $|G|$.

The group of symmetries of a regular $n$-gon is called the dihedral group and written $D_n$; these are the very sets $D_n$ from Leonardo’s theorem. It has $2n$ elements, $n$ rotations and $n$ reflections; that’s why some books write it $D_{2n}$. Our square is $D_4$, and $|D_4| = 8$.

Groups are everywhere.

More about the clock face. If the hand points at nine, in five hours it will show two: $9 + 5 = 2$. The marks $0, 1, \dots, n - 1$ with addition round the circle form a group, written $\mathbb Z_n$ (the notation $\mathbb Z/n\mathbb Z$ is also used); on an ordinary clock $n = 12$, with midnight playing the role of zero. Invertible matrices form a group, because a product of invertible matrices is invertible and each has an inverse; inside it live the orthogonal matrices from chapter 39.

Which of these sets with the given operation is a group?

The natural numbers with addition The integers with subtraction The non-zero rational numbers with multiplication The integers with multiplication

A product of non-zero fractions is a non-zero fraction, multiplication is associative, the identity is $1$, and $\frac pq$ has the inverse $\frac qp$. Zero had to be thrown out: it has no inverse.

Three facts follow straight from the axioms, and each will come in handy.

A deck of cards

Magicians can shuffle a deck perfectly: they cut the 52 cards exactly in half and interleave the halves, card by card. If the top card stays on top, it’s called an out-shuffle. The deck looks mixed afterwards, but the magician knows what we’re about to find out: after eight such shuffles the cards come back to their original order.

A shuffle is a permutation: a rule that says, for each place, where the card lying there goes. A permutation of $n$ objects is conveniently understood as a one-to-one map $\sigma$ of the set $\{1, 2, \dots, n\}$ onto itself and written in two rows: the places on top, and underneath where the card from each goes.

$$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 4 & 1 & 2 \end{pmatrix}: \qquad \sigma(1) = 3,\ \ \sigma(2) = 5,\ \ \sigma(3) = 4,\ \ \sigma(4) = 1,\ \ \sigma(5) = 2.$$

All the permutations of $n$ objects together with composition form a group. It’s called the symmetric group and written $S_n$. The identity is the permutation that leaves everything in place, the inverse of $\sigma$ sends each card back, and composition of maps is always associative. $S_n$ has as many elements as there are ways of arranging $n$ objects in a row, that is, $n!$ (chapter 45). For a deck of 52 cards that’s a 68-digit number.

The two-row notation is cumbersome, and there’s a handier one. Follow the card from place $1$: $\sigma$ sends it to place $3$, the card from place $3$ to place $4$, and from place $4$ back to $1$. The circle has closed: $1 \to 3 \to 4 \to 1$. The remaining places $2$ and $5$ swap cards. So we write: $\sigma = (1\,3\,4)(2\,5)$.

Now let’s work out when the deck comes back. For this we need one more word. The order of an element $g$ of a group is the smallest natural number $k$ for which $g^k = g \circ g \circ \dots \circ g = e$; if there’s no such $k$, the order is infinite. The rotation $r$ of the square has order $4$, a reflection order $2$, $e$ order $1$, and the number $1$ in the group $\mathbb Z$ has infinite order.

Why the out-shuffle has such short cycles is explained by arithmetic. Number the places from zero, $0$ to $51$. A card from place $i$ in the top half goes to place $2i$, from the bottom half to $2i - 51$. The top and bottom cards stay put, and for the rest the place is multiplied by $2$ “round a circle” of $51$ marks. Since $2^8 = 256 = 5 \cdot 51 + 1$, eight doublings bring every card home. This trick, counting round a circle, will be the hero of the next chapter.

Find the order of the permutation $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 1 & 7 & 6 & 4 & 2 \end{pmatrix}$: how many times does it have to be repeated for everything to come back?

Decompose into cycles: $1 \to 3 \to 1$ gives $(1\,3)$, and $2 \to 5 \to 6 \to 4 \to 7 \to 2$ gives $(2\,5\,6\,4\,7)$. The lengths are $2$ and $5$, and the order is $\operatorname{lcm}(2, 5) = 10$.

Even and odd

The simplest permutations swap two objects and touch nothing else. They’re called transpositions; the transposition $(a\,b)$ is a cycle of length $2$. Any permutation can be built from transpositions: a deck can be put in order by swapping two cards at a time, which is how many sorting algorithms work. It’s enough to decompose a single cycle into transpositions.

One permutation has many decompositions: $(1\,2) = (1\,3)(2\,3)(1\,3)$, one transposition or three. But the number of transpositions in a decomposition always has the same parity. To prove this we need a quantity that doesn’t depend on the decomposition.

The trick is to draw the permutation with wires: inversions become crossings, and crossings are easy to count.

Mark the places $1, \dots, 6$ at the top, and the same places at the bottom. Run the wire of card $i$ as a straight segment from place $i$ at the top to place $\sigma(i)$ at the bottom. The wires of cards $i < j$ cross exactly when these cards have changed order at the bottom, that is, $\sigma(i) > \sigma(j)$. So there are as many crossings as inversions; here there are five. Swap the cards in two neighbouring places at the bottom. The pair of these two cards changes order: if their wires crossed, the crossing disappears, and if not, one appears. Every other pair of cards keeps its order: there are no other places between neighbouring places, and a third card stands on the same side of both. The number of inversions changes by exactly one. Swapping places $i < j$ comes down to swapping neighbours. Walk the card from place $i$ to the right, swapping it with its neighbour each time, until it reaches place $j$: that’s $j - i$ swaps. The card that was in place $j$ now stands in place $j - 1$; walk it left to place $i$: another $j - i - 1$ swaps. All the other cards moved one step left and then one step right, that is, came back. That’s $2(j - i) - 1$ swaps of neighbours in all, an odd number. Each swap of neighbours changes the parity of the number of inversions, and there’s an odd number of swaps. So after swapping any two places the parity of the number of inversions is different.

Counting inversions one by one is tedious. Cycles give the answer faster.

The number of inversions, pairs standing in reverse order. This is the definition of the sign. How many objects are being permuted. The number of disjoint cycles, counting fixed points as cycles of length $1$. A cycle of length $\ell$ is $\ell - 1$ transpositions, and in all we get $(\ell_1 - 1) + \dots + (\ell_c - 1) = n - c$ transpositions. Example: for $\sigma = (1\,3\,4)(2\,5)$ we have $n = 5$, $c = 2$, $n - c = 3$, and there are seven inversions, as we counted; $(-1)^7 = (-1)^3 = -1$, and the permutation is odd. The out-shuffle of 52 cards has nine cycles, $52 - 9 = 43$, and it’s odd too.

The even permutations of $n$ objects form a group: a product of even permutations is even, the identity is even, and the inverse of an even permutation is even, because $\operatorname{sgn}\sigma \cdot \operatorname{sgn}\sigma^{-1} = \operatorname{sgn} e = 1$. It’s called the alternating group $A_n$. For $n \ge 2$ it contains exactly half of all permutations, $n!/2$: tacking on the transposition $(1\,2)$ takes the even permutations one-to-one to the odd ones and back.

How many inversions does the permutation with bottom row $2\;4\;1\;3$ have? Is it even?

The two stands to the left of the one: one inversion; the four to the left of the one and the three: two more; the other pairs are in the right order. That’s $3$ inversions in all, and the permutation is odd. A check with cycles: $1 \to 2 \to 4 \to 3 \to 1$, one cycle of length $4$, and $n - c = 4 - 1 = 3$, also odd.

You can get your hand in with compositions, cycles, orders and signs in the trainer.

The fifteen puzzle

In the winter of 1880 America was gripped by a craze for a game in a $4 \times 4$ box: fifteen numbered tiles and one empty square. A tile next to the empty square can be slid into it, and the aim is to put the tiles in order. By the spring the craze had reached Europe, and by the summer it had died down. The game was invented by Noyes Chapman, the postmaster of the town of Canastota in New York State, around 1874; in March 1880 he applied for a patent. In 1891 the famous puzzle-maker Sam Loyd declared himself the inventor and for the rest of his life told the story that he’d offered a thousand dollars to anyone who could put back the swapped tiles 14 and 15. In 2006 the puzzle historians Jerry Slocum and Dic Sonneveld showed that Loyd had nothing to do with the invention of the game or the craze for it. The promised prize is most likely part of the same legend. But the problem about 14 and 15 is real.

To keep track of a position, we’ll count the empty square as a sixteenth tile. Then a position is a permutation $\pi$ of sixteen places: the tile that belongs in place $i$ stands in place $\pi(i)$. Colour the board like a chessboard so that the bottom right corner, where the empty square stands in the solved position, is white.

The trick is to follow two features at once: each move changes both.

In the solved position $\pi$ is the identity, there are no inversions, and it’s even. The empty square stands in its corner, on a white square. The statement holds. A move is swapping the empty square with a neighbouring tile. For the permutation of sixteen places this is swapping the contents of two places, and by the transposition theorem the parity of $\pi$ changes. The empty square meanwhile moves to a neighbouring square, and neighbouring squares of a chessboard have different colours. The colour of the square under the empty square changes too. Both features change at the same time, so the rule “even means on white” survives any move, and with it any chain of moves. The table on the right shows this over three moves. In the position with 14 and 15 swapped the empty square stands at home, on a white square, while $\pi$ is a single transposition $(14\,15)$, that is, odd. The rule is broken, and no chain of moves leads to this position.

This half of the answer was published in 1879 by William Johnson, in a note on the fifteen puzzle for the American Journal of Mathematics. In the same publication William Story proved the other half: everything the invariant doesn’t forbid is reachable. So of the $16!$ arrangements of the tiles and the empty square exactly half can be reached by moves: $10{,}461{,}394{,}944{,}000$.

Why everything else is reachable

Any position in which the permutation $\pi$ is even exactly when the empty square is on a white square can be reached by moves from the solved position.

The idea: learn to cycle any three tiles round without touching anything else, and then build any even permutation out of such three-cycles.

First bring the empty square home, to the bottom right corner, by any route. The invariant is preserved, so the permutation of the fifteen tiles in the resulting position is even. Moves are reversible, so it’s enough to show that with the empty square at home any even permutation of the tiles can be obtained. Call chains of moves that begin and end with the empty square at home loops. Loops can be performed one after another and undone by going through them backwards, so the permutations of the tiles they produce form a group $G$. By the invariant $G$ lies in $A_{15}$; we have to prove that $G = A_{15}$.

Take the empty square along a closed route through all sixteen squares: from the corner to the left, up the third column to the second row, down the second column, up the first to the very top, right along the top row, and down the right-hand column home. Number the squares in the order of the route with the numbers $1, \dots, 15$. After a full circuit each tile moves one square back along the route, and the tile from square $1$ goes to square $15$: the loop gives a cycle $s$ of length $15$. A small loop, the empty square up, left, down and right round the $2 \times 2$ square in the bottom right corner, cycles the three tiles on squares $15$, $1$ and $2$. These squares are consecutive along the route.

Do the loop $s$ several times, then the small loop, and then undo the circuits. The tiles that the circuits brought to squares $15$, $1$ and $2$ are cycled round, and after the circuits are undone they end up cycled round among their original squares, three squares consecutive along the route. The other tiles come back into place. This gives the three-cycles of any three squares consecutive along the route: $(1\,2\,3)$, $(2\,3\,4)$, …, $(13\,14\,15)$, and, going round the small loop the other way, their inverses.

It remains to prove that such cycles generate $A_{15}$. Any even permutation is a product of an even number of transpositions; split them into pairs. A pair with a common element gives a three-cycle: $(a\,b)(b\,c) = (a\,b\,c)$. A pair with no common elements gives two three-cycles: $(a\,b)(c\,d) = (a\,b)(b\,c) \cdot (b\,c)(c\,d)$. So it’s enough to obtain all three-cycles. Let’s show by induction that the cycles $(1\,2\,3), \dots, (k-2\;k-1\;k)$ and their inverses give all the three-cycles on the numbers $1, \dots, k$. For $k = 3$ the statement holds: there are only two three-cycles on three numbers, $(1\,2\,3)$ and its inverse. Suppose the statement holds for $k$, and add the cycle $c = (k-1\;k\;k+1)$. We need any cycle $(a\,b\;k+1)$ with distinct $a, b \le k$. By the inductive hypothesis all three-cycles on the numbers $1, \dots, k$ are available to us, and so, by what was said above, the whole group $A_k$. Take a permutation $p$ of the numbers $1, \dots, k$ with $p(k-1) = a$ and $p(k) = b$; if it’s odd and $k \ge 4$, make it even by tacking on, on the right, a transposition of two numbers other than $k-1$ and $k$. Then $p\,c\,p^{-1} = (a\;b\;k+1)$: by direct checking, $p\,c\,p^{-1}$ takes $a$ to $b$, $b$ to $k+1$, $k+1$ to $a$, and touches nothing else. For $k = 3$ the even $p$ are enough to get the cycles $(a\,b\,4)$ for three of the six pairs $(a, b)$, and the rest are their inverses: $(a\,b\,4)^{-1} = (b\,a\,4)$. Every three-cycle on the numbers $1, \dots, k+1$ either doesn’t contain $k + 1$ or has the form $(a\,b\;k+1)$, and the induction is complete. So $G = A_{15}$.

The lesson of the fifteen puzzle is broader than the game. To prove that a problem is unsolvable, you don’t need to try every attempt. You need to find a quantity that no permitted move changes, an invariant, and show that the goal has a different value of it. Groups supply ready material for such quantities: parity, orders, remainders. Below, the same trick will deal with the Rubik’s cube.

How many subgroups?

The hour hand jumps four hours forward each time. Which marks will it visit? Zero, four, eight, and zero again: three in all. Jumping by three hours, it visits four marks; by six, two; by five, all twelve: $5, 10, 3, 8, 1, 6, 11, 4, 9, 2, 7, 0$. Three, four, two, twelve: all divisors of twelve. A coincidence?

The marks the hand visits form a subgroup of $\mathbb Z_{12}$. This happens in any group: for each element $g$ all its powers $\dots, g^{-2}, g^{-1}, e, g, g^2, \dots$ form a subgroup, written $\langle g \rangle$. If the order of $g$ is $k$, then $\langle g \rangle = \{e, g, g^2, \dots, g^{k-1}\}$ and it has exactly $k$ elements: after that the powers repeat, and before that there can be no repeat, since $g^i = g^j$ with $0 \le i < j < k$ would give $g^{j-i} = e$. A group all of whose elements are powers of one element is called cyclic, and that element is its generator. The clock face $\mathbb Z_{12}$ is cyclic: it’s generated by the mark $1$, and also by $5$, $7$ and $11$. The rotations of the square $\{e, r, r^2, r^3\}$ are a cyclic subgroup of $D_4$ with generator $r$.

The trick is to cut the whole group into shifted copies of $H$.

In the picture $G = \mathbb Z_{12}$, and $H = \langle d \rangle$ is all the marks the hand reaches by jumps of $d$ hours; the point $d$ can be moved. At $d = 4$ it’s $\{0, 4, 8\}$. It’s a subgroup: the sum of two of its elements is again in it, and so is the inverse of $h$, the mark $12 - h$. The coset $1 + H$ is the same figure turned by an hour. In any group the coset $gH$ has exactly $|H|$ elements: if $gh_1 = gh_2$, then by the sudoku rule $h_1 = h_2$, so different elements of $H$ give different elements of $gH$. Two cosets either coincide or don’t overlap. Suppose $aH$ and $bH$ have a common element: $ah_1 = bh_2$. Then $b = ah_1h_2^{-1}$, and any element $bh$ equals $a\,(h_1h_2^{-1}h)$, where the product in brackets lies in $H$. So $bH \subset aH$; likewise $aH \subset bH$. Moreover, each element $g$ lies in its own coset $gH$, because $e \in H$. The cosets cut $G$ into non-overlapping pieces of $|H|$ elements, and there’s a whole number $k$ of pieces. So $|G| = k\,|H|$, and $|H|$ divides $|G|$. In the picture $12 = 3 \cdot 4$.

So the group $S_5$ of $120$ elements has no permutation of order $7$: seven doesn’t divide $120$. $D_4$ has ten subgroups: the group itself, $\{e\}$, five subgroups of two elements, $\{e, r^2\}$ and one for each reflection, and three subgroups of four: the rotations $\langle r \rangle$, $\{e, r^2, h, v\}$ and $\{e, r^2, d, d'\}$. Their sizes $1$, $2$, $4$, $8$ all divide eight.

How many marks will the hour hand visit if it jumps nine hours forward each time? In other words, how many elements are in the subgroup $\langle 9 \rangle$ of the group $\mathbb Z_{12}$?

$9, 18 \to 6, 15 \to 3, 12 \to 0$: the hand visits $\{0, 9, 6, 3\}$ and comes back. Four marks, the same as when jumping by three hours. That’s as it should be: a shift of nine forward is a shift of three back, and $4$ divides $12$.

The Rubik’s cube

The Hungarian architect and teacher Ernő Rubik invented his cube in 1974. The cube is also a permutation machine. Each turn of a face permutes the 54 coloured stickers (the centre stickers of the faces stay in place), and every position is obtained from the solved one by some chain of turns. All such permutations of the stickers form a group: chains can be carried out one after another and undone. The cubers’ notation: $R$, $L$, $U$, $D$, $F$, $B$ are quarter turns of the right, left, up, down, front or back face clockwise, as seen looking at that face; $R'$ is the same turn anticlockwise, and $R2$ a half turn.

Let’s repeat one combination many times. If it’s $R$, the cube comes back solved after four turns. And if it’s $R\,U$, the right face, then the top? The answer is $105$ times, and the formula for the order of a permutation explains it.

How many positions does the cube have in all? Take it apart and put it back together any old how: the eight corners can be arranged in the corner places in $8!$ ways and each turned in three ways, the twelve edges arranged in $12!$ ways and each flipped in two. By the product rule that’s $8! \cdot 3^8 \cdot 12! \cdot 2^{12} = 519{,}024{,}039{,}293{,}878{,}272{,}000$ assemblies. But not all of them can be reached by turns. We need two definitions. The orientation of a corner is marked by its sticker of the top or bottom colour: $0$ if it faces up or down, $1$ if the corner is twisted a third of a turn clockwise from that position, $2$ if anticlockwise. For each edge choose a main sticker: of the top or bottom colour, and if there’s none, of the front or back colour. Call an edge flipped if its main sticker faces sideways when the edge is in the top or bottom layer, and right or left when it’s in the middle layer.

Cubers use a trick that group theory calls the commutator: $x\,y\,x^{-1}y^{-1}$. If $x$ and $y$ commute, the commutator does nothing. Face turns don’t commute, but they almost do: $R$ and $U$ share pieces only in one corner of the cube. So $R\,U\,R'\,U'$ moves only seven pieces out of twenty and returns the rest to their places; its order is $6$. Algorithms that change two or three pieces and leave the rest alone are built out of such “almost nothings”.

How many moves are needed to solve the most scrambled position? In July 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson and John Dethridge proved: no more than twenty, if a half turn of a face counts as one move. The search took about 35 years of processor time, donated by Google. Positions needing exactly twenty moves exist, so 20 is called God’s number. If only a quarter turn counts as a move, God’s number is 26; this was established in 2014.

You can learn to solve the cube, and see all these permutations live along the way, in the Rubik’s cube guide on this site.

One table, different costumes

The rotations of the square $e, r, r^2, r^3$, the four-mark clock face $\mathbb Z_4$, and the four complex numbers $1, i, -1, -i$ under multiplication are three different sets, but their tables are the same once the elements are renamed: $r^k \leftrightarrow k \leftrightarrow i^k$. Multiplying by $i$ is a rotation by $90^\circ$ (chapter 15), and multiplying $i^a$ by $i^b$ is the same as adding the hours $a + b$ on a four-hour clock.

Any cyclic group of $n$ elements is isomorphic to $\mathbb Z_n$: powers of the generator add like hours on a clock face of $n$ marks, $g^ag^b = g^{a+b}$, and after $g^{n-1}$ comes $g^n = e$ again. The symmetries of an equilateral triangle permute its vertices, and different symmetries permute them differently. There are six symmetries, and six permutations of three vertices too, $3! = 6$, so all of them occur, and $D_3 \cong S_3$. With the square this doesn’t work: there are $24$ permutations of four vertices but only $8$ symmetries. For example, you can’t swap two neighbouring vertices while leaving the other two in place.

The symmetries of a rectangle that isn’t a square: $e$, the rotation by $180^\circ$ and two reflections. Is this group isomorphic to the clock face $\mathbb Z_4$?

Yes: both have four elements No No, because one of them isn’t abelian

$\mathbb Z_4$ has an element of order $4$, the mark $1$: $1 + 1 + 1 + 1 = 0$. For the rectangle any symmetry done twice gives $e$, and the orders are at most $2$. An isomorphism preserves orders: $g^k = e$ implies $\varphi(g)^k = \varphi(g^k) = e$, and vice versa. So there’s no correspondence. The group of symmetries of a rectangle is called the Klein four-group.

A strong conclusion follows from the sudoku rule: up to isomorphism, every finite group is a group of permutations.

Where next

The clock face $\mathbb Z_{12}$ is a group under addition. But what if we multiply on the clock face? On a clock with a prime number of marks, say seven, the non-zero marks $1, 2, \dots, 6$ form a group under multiplication: $3 \cdot 5 = 15$, and fifteen hours on a seven-hour clock is $1$, so $5$ is the inverse of $3$. This group has six elements, and by Lagrange’s theorem the order of any of them divides six, so $a^6$ always gives $1$. That’s Fermat’s little theorem, proved almost for free. The cipher your bank uses to protect your payment rests on it. A riddle remains: how can two people agree on a secret key if strangers overhear their whole conversation? The answer is in chapter 41.