Permutation Groups

There are lots of things that can form groups, but the things that we’ll use to represent the Rubik’s cube are permutations, which are re-arrangements of items in a set. For example, we could notate a permutation like

where the arrows define the rearrangement. Note that we can have permutations of any number of items rather than just five. We can leave out the top row of the mapping because it will always be the numbers in order, so we could notate it . We can see that this permutation can also be thought of as an invertible, or bijective, function between the numbers and themselves.

So now, lets construct a group. The set of all permutations of a particular size, five in this example, will be the set representing our group. Then, we need an operation. Since permutations are basically functions, permutation composition can simply be function composition!

From here, the group axioms are trivial. Our identity is the do-nothing permutation, . We know that associativity holds because permutation composition is identical to function composition which is known to be associative. We know that there is always an inverse because permutations are bijective mappings and you can simply reverse the arrows to form the inverse:

Therefore, permutation composition satisfies all of the group axioms, so it is a group. Next, there also exists a much cleaner way to notate permutations, called cycle notation. The way you would write in cycle notation is as . Each item maps to the next item in the list, wrapping around at a closing parenthesis. The notation is saying that maps to , maps to , maps to (because of the wraparound), maps to itself, and also maps to itself. This is called “cycle notation” because it shows clearly the underlying cycle structure of the permutation. , , and form a three-cycle and and both form one-cycles. It is also conventional to leave out the one-cycles and to just write down .

This notation also provides a simple way to determine exactly how many times one has to compose a permutation with itself for it to equal identity. Since a three-cycle takes three iterations for its elements to return to their initial spots, you can compose a three-cycle with itself three times to give identity. In full generality, we have to take the least common multiple of all of the cycle lengths to give that number of repetitions. For example, the permutation has a three-cycle and a four-cycle, and the LCM of three and four is , therefore exponentiating it to the twelfth power gives identity.

A permutation is something that we can easily represent in a computer, but how can we represent a Rubik’s Cube in terms of permutations? It is quite simple actually…

A Rubik’s Cube forms a permutation of the stickers! We don’t actually have to consider the centers because they don’t move, so we would have a permutation of stickers. We can define the turns on a Rubik’s Cube in terms of permutations like so:

The exact numbers aren’t actually relevant for understanding, but you can sanity-check that exponentiating all of them to the fourth gives identity, due to all of the cycles having length four. This matches our expectation of how Rubik’s Cube moves should work.

Now, if we restrict our set of permutations to only contain the permutations that are reachable through combinations of moves (after all, we can’t arbitrarily re-sticker the cube), then this structure is mathematically identical — isomorphic — to the Rubik’s Cube group. This is called a subgroup of the permutation group of 48 elements because the Rubik’s Cube group is like its own little group hidden inside that bigger group of all permutations.

It may appear as if our definition of the Rubik’s cube group includes too many elements: after all, each sticker on a Rubik’s cube has seven identical twins, but we’re giving them different numbers and treating them as if they were unique. If there existed an algorithm that could swap two stickers of the same color, then our definition would count those as different states whereas they would really be the same state. However, we don’t have to worry about this because all of the pieces on a cube are unique. The only way to swap two stickers would be to swap two pieces, and that would definitely produce a different cube state. Note that we don’t get to make that assumption for puzzles like the 4x4x4 which have identical center pieces, however we are conveniently not writing about the 4x4x4 because our code doesn’t even work for that yet 🤫.

One final term to define is an orbit. An orbit is a collection of stickers (or whatever elements are being permuted, in full generality) such that if there exists a sequence of moves that moves one sticker in the orbit to another sticker’s place, then that other sticker must be in the same orbit as the first. On a Rubik’s Cube, there are two orbits: the corners and the edges. There obviously doesn’t exist an algorithm that can move a corner sticker to an edge sticker’s place or vice versa, therefore the corners and edges form separate orbits. Intuitively, you can find orbits of any permutation subgroup by coloring the stickers using the most colors possible such that the colors don’t change when applying moves.

Excluding centers, the best we can do is two colors, and those two colors highlight the corner and edge orbits.