Superflip composed with fourspot

Somehow, it slipped past my radar that Tomas Rokicki and Morley Davidson have established the maximum number of quarter-turns necessary to solve a Rubik’s cube (the more widely-popularised figure of 20 was for the half-turn metric). That is to say, any of the six faces can be rotated by 90° clockwise or anticlockwise in a single move.

We can consider the Cayley graph, which is 12-regular (since at each position, there are 12 possible moves one can make) and bipartite; this is most easily seen by noting that a quarter-turn induces an odd permutation (a 4-cycle) on the eight vertices of the cube. Then the maximum number of moves necessary is, by definition, the diameter of the Cayley graph.

Anyway, the diameter of the graph is 26, and surprisingly there are very few positions which take 26 moves to solve (compared with billions of distance-20 positions in the half-turn metric). Indeed, it is conjectured that there are only three such positions, or one up to isomorphism: the so-called superflip composed with fourspot. It is worth explaining this terminology.

The superflip is the unique non-identity element in the centre of the Rubik’s cube group where every cell remains in its original position, but with all 12 edge cells reversed. Since it commutes with every element, the order of composing it with fourspot is not important.

The fourspot is a common pattern where four of the face cells undergo a derangement, and all other cells remain unchanged. Somehow, the fourspot has acquired something of a cult following, and even boasts its own music video:

In other news, the Erdos discrepancy problem was recently solved by Terry Tao. There is a natural way to turn this into a two-player game. Specifically, Alice and Bob take turns colouring positive integers (cobalt blue for Alice and moss green for Bob), and the game terminates when there exists a progression {n, 2n, 3n, …, kn} (for some positive integers k and n) such that the difference between the number of cobalt blue elements and moss green elements in that progression exceeds d (a predetermined constant that determines the difficulty of winning).

Also, there’s a petition for LEGO to produce a Lovelace and Babbage themed set. You’re strongly encouraged to support the petition; more information is available over at the Aperiodical. This is currently in the limelight due to Ada Lovelace’s impending 200th birthday (this December); watch this cp4space for more details of Lovelace-themed events in the coming months…