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?

Solution 1:

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:

• Michael's list of orders.
• Joyner's Book: Adventures in Group Theory
• Rokicki's slides from a talk at Stanford
• Dan Bump's lecture notes

Solution 2:

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.