# Mathematics Behind the 4×4 and 5×5 Rubik's Cube

A lot is known about the math behind the 3×3 Rubik's cube (symmetries, generators, group structure etc...). Is the same true for the 4×4 and 5×5 cubes? I haven't had much success finding this information on the web; I've mostly found websites that just give instructions and strategies for solving these cubes. Does anyone know of any references?

-
I'd be surprised if David Singmaster hasn't already written anything on this... –  Guess who it is. Apr 28 '11 at 5:35

Singmaster wrote about it a little in the 80's. Jaap Scherphuis has written up more about general puzzles on his site, which is a good read on the topic (see his Articles; he also has Singmaster's Cubic Circular on his website).

While the 4x4x4 and up are obviously permutation puzzles, you certainly don't have a group under a simple sticker interpretation. Consider this commutator: 2R B' 2R 2F2 2R' B 2R 2F2 2R2 and 2R. The first looks like an identity, but it obviously doesn't commute with very simple 2R move. You can patch this, most easily by labeling every piece (making it a "supercube"); I'm not even aware of some other decent way to deal with it by, say, using quotients. However, this is still a bit undesirable, because it doesn't correspond to how we care to use the cube. We can use a supercube labeling to make a transition table and analyze it, but we're now making assumptions that correspond to more than the raw puzzle.

There are also other practical issues with analysis, such as defining what a single move'' is. Nevertheless, there has been some progress; there used to be gradual progress at cubezzz.dyndns.org by Rokicki, Radu, etc. Bruce Norskog wrote a solver that solves a cube in 78 moves (some half-turn metric), I think. I also once witnessed/helped Michael Gottlieb compute generalizations of the 3x3x3 lower counting bound to higher cubes with same recurrences. But in general, progress on the big questions has been slow because the 3x3x3 equivalent questions are complicated and interesting enough. The 3x3x3 has been keeping mathematicians and programmers busy for years, with God's number only recently settled through smart brute force. I don't think more than a handful of people even understand the conjugacy classes of the cube fully, and I haven't seen good writeups on some simple topics.

There's also vague interest in the 4x4x4 and above. The World Cube Association is moving towards random-state scrambles for competitions, and this is hard to achieve on the 4x4x4 – but desirable. Tom Rokicki, behind much of the quest for God's number on 3x3x3, also considers the 4x4x4 a formidable upcoming goal.

Anyhow, that was a bit all over the place, but: The 3x3x3 is very interesting. Either we don't understand something on the 3x3x3, in which case the higher cubes are out of reach – or we do understand it and it's interesting enough. Generalizing the math to higher cubes is mostly tedious without nearly as much new insight.

Some references that (might) touch on higher-order cubes:

-

I don't know much about the puzzles, but a friend of mine is an enthusiast and last I spoke to him, he seemed to be saying that not much is known about the $4 \times 4 \times 4$ puzzle. One of the difficulties is that there isn't a bijection between the transformation group and the state space: because there are pieces which cannot be visually distinguished from each other, there are states where a non-trivial transformation acts as the identity. In other words, this means that unlike the standard Rubik's cube, there are non-trivial group elements which have fixed points.

-
Having fixed points is less of an issue for solving the cube. A bigger issue is that it increases the number of allowed configurations. For the 3x3x3 cube, there are some well known configurations that cannot be achieved unless you take a cube apart (direct swapping of two pieces in certain orientation; reversing the orientation of one edge piece). This is essentially due to a "parity" configuration: the group operations do not act transitively on the possible state space given by taking the cube apart and rebuilding, and the allowed configuration is the orbit. –  Willie Wong Apr 28 '11 at 9:27
In 4x4x4 and bigger, because of the possible swaps that doesn't visually distinguish, you can perform some of those "impossible moves". It's been a while since I played with the 5x5x5 cube, but if I remember correctly, the naive generalisation of the 3x3x3 generator "moves" plus the edge orientation reversal is enough to solve the cube. –  Willie Wong Apr 28 '11 at 9:31
BTW, there are also non-trivial 3x3x3 transformations that do not result in visually distinguishable configurations: you can simultaneously "rotate" the center pieces on several faces as long as the total rotations add up to a multiple of $\pi$ radians. This is not noticeable on a normal cube. But on a cube with patterned stickers, this is a required move to really solve the cube. –  Willie Wong Apr 28 '11 at 9:36
@Willie: Yes, the $5 \times 5 \times 5$ is solvable using only the usual $3 \times 3 \times 3$ algorithms plus some centre-piece moves plus the edge pair swap algorithm. (At least, that's how I do it.) I completely forgot about the supercube. I suppose that implies that the $4 \times 4 \times 4$ can be analysed using the same technology... –  Zhen Lin Apr 28 '11 at 11:56