Twistspace

The order of a cube algorithm, from its cycle structure

Abstract

A Rubik's cube algorithm, composed, is a bijection of the stickers onto themselves: an element of a finite permutation group. This companion sets out what follows. Every algorithm repeated sufficiently often returns the cube to solved; the number of repetitions is the least common multiple of the cycle lengths of that permutation; and the model used here departs from a physical cube in three specific, measurable ways. Section 7 takes the same question in the other direction and asks what a camera can recover from a cube in someone's hands, where the answer turns out to be exact on a three by three and provably indeterminate above it.

1. The shift

1.1 Two descriptions

Take R U R' U'. As a procedure it is four turns. As a permutation it is a rearrangement of fifty-four stickers, stated completely by:

two cycles of length 6, two cycles of length 3, and 36 stickers left alone

Eighteen stickers move; the permutation is even; repetition returns the cube after six applications, six being the least number divisible by both 6 and 3. None of these follow from the move sequence without composing it.

1.2 Why this is a group

The reachable positions form a group: turns compose, composition is associative, the null turn is an identity, and every turn has an inverse. The group axioms are satisfied exactly, which is what makes the rest of this short.

The consequence that matters: repetition cannot diverge. The orbit of any element visits finitely many positions, so it must revisit one, and invertibility forces the first revisited position to be the starting one, since A^i = A^j with i < j gives A^(j-i) = I.

2. Return length

2.1 The cycle argument

Any permutation of a finite set decomposes uniquely into disjoint cycles. A sticker sitting in a cycle of length L visits L positions and returns to its own after exactly L applications, never sooner.

The cube is solved when every sticker is home simultaneously. So the number of repetitions that solves it is the smallest number divisible by every cycle length:

ord(A) = lcm(L1, L2, ..., Lm)

The argument uses no property of the cube beyond finiteness.

2.2 What it predicts

algorithmcycle lengthsreturn length
R4, 4, 4, 4, 44
R U R' U'6, 6, 3, 36
R U15, 7, 7, 3105
R U2 D' B D'15, 14, 9, 4, 2, 21260
superflip2 twelve times over2

The third row is not pathological: 15, 7 and 3 are pairwise coprime, so the least common multiple is large relative to the length of the algorithm.

The fourth row is the maximum. No element of the three by three group has order above 1260, and R U2 D' B D' attains it, with cycle lengths 15, 14, 9, 4, 2, 2 giving 2^2 . 3^2 . 5 . 7 = 1260.

2.3 Order is not a smooth function

It is worth dwelling on how badly behaved the return length is as a function of the algorithm. Building R U2 D' B D' up one move at a time gives:

R            ->     4
R U2         ->    30
R U2 D'      ->   360
R U2 D' B    ->   144
R U2 D' B D' ->  1260

The sequence is not monotone, falling by a factor of 2.5 at the fourth move before rising by 8.75 at the fifth. Cycle structure is a property of the composed permutation and not of any prefix, so no local argument predicts it. The sensitivity panel uses a logarithmic axis for the same reason.

3. The size of the group

Counting the reachable positions is a counting argument with three corrections:

8!        orderings of the eight corners
3^7       twists of them, the eighth forced by the other seven
12!       orderings of the twelve edges
2^11      flips of them, the twelfth forced
/ 2       because corner and edge permutation parity are locked together

which multiplies out to

43,252,003,274,489,856,000  =  2^27 . 3^14 . 5^3 . 7^2 . 11

The playground derives this product rather than storing the answer, and keeps it in factored form. That is not only tidiness. Lagrange's theorem says the order of any element must divide the order of the group, and when both are prime factorisations, dividing is comparing exponents. So every return length the playground reports can be checked against the group for free, and any implementation error that produced an order with a prime factor outside {2, 3, 5, 7, 11} would be caught instantly.

The three constraints correspond to three invariants: corner orientation sums to zero modulo three, edge orientation sums to zero modulo two, and corner and edge permutation parities agree. They are why a cube disassembled and reassembled at random is solvable with probability 1/12.

4. Parity, and a correction

Parity is the invariant behind every "that case cannot happen" in cubing, but what it tells you depends on the cube, and it is easy to state wrongly.

A single-layer quarter turn carries a band of N four-cycles around the cube and spins its own face in about N^2 / 4 more. Whether that total is odd changes with N:

  • On a three by three a quarter turn is an odd permutation of the stickers. Parity therefore counts turns: an algorithm with odd parity uses an odd number of quarter turns, and is certainly not the identity.
  • On a four by four a quarter turn is already even. Every algorithm is then even, and parity carries no information whatsoever.

An earlier draft of this playground asserted that an odd sticker permutation meant an unreachable position. That is false, and a plain R refutes it: R is odd as a sticker permutation and is obviously a legal move. The parity constraint people mean when they talk about cubing is a statement about piece permutations, where corner and edge parities must agree, and it is not the same statement. The playground now measures the parity of a quarter turn on the current cube rather than assuming one, which is why the panel says something different on a four by four than on a three by three.

5. Being solved and looking solved

The engine tracks stickers, and two stickers of the same colour are different objects to it. A person has no such opinion. This produces a genuine and interesting gap, and the playground reports both numbers rather than picking one.

A whole-cube rotation. Turning the entire cube ninety degrees moves all fifty-four stickers, so as a permutation it has order four. The cube is solved the whole time. Order four, visual return one.

Even cubes. On a four by four the four centre stickers of a face are interchangeable in the hand and distinct in the model, so an algorithm that only permutes them among themselves is invisible and non-trivial at once.

Marked centres. Conversely, a cube with a logo printed on one centre has more distinguishable states than the standard count above admits, by a factor of 4^6 / 2. The playground models the unmarked case.

None of these is a defect in the model. They are places where "the same position" means two different things, and the honest response is to compute both.

6. Commutators, and why they matter

Two elements commute when AB = BA. The commutator measures the failure:

[A, B] = A B A' B'

which is the identity exactly when A and B commute, and otherwise is a measure of how badly they do not.

Its usefulness is a support argument. Where A and B overlap in few pieces, most of A is undone by A' and most of B by B', and the residue is confined to the overlap. [R U R', D] expands to eight moves and moves nine stickers: a 3-cycle of corners, with forty-five stickers fixed.

Hand-solving methods require operations that alter a small controlled region without disturbing solved material. Commutators supply them systematically.

The conjugate [A : B] = A B A' does the complementary job: it performs B somewhere else. Set the cube up with A, do the thing, undo the setup. Together, conjugates place and commutators act, and essentially every human solving method is built from the two.

7. Reading a cube with a camera

A camera can put a real cube on screen, and the interesting part is what it cannot do and why.

7.1 Colour is compared, never measured

The classic failure of cube scanners is red against orange under warm light, and it is a failure of stored colour constants rather than of cameras. Nothing here stores one. On a three by three the six centres cannot move relative to each other, so whatever they look like under the light in the room are, by definition, the six face colours; every other facelet is placed relative to those.

Each patch is reduced to three numbers chosen so that exposure cannot move them: the two channel fractions, and brightness relative to the whole scan measured in octaves. Multiply every channel by a common factor and all three are unchanged, so a frame shot two stops darker lands in exactly the same place. This is exact rather than approximate, and the calibration checks it by photographing the same position at 0.3 and 0.85 of full brightness and requiring the two classifications to agree facelet for facelet.

A colour cast is a per-channel factor and is not cancelled by that argument. It is absorbed instead by where the prototypes come from: the centres were photographed under the same lamp as everything else, so a cast moves the samples and the references together. Raising red by a third and cutting blue by a third leaves the reading exact.

7.2 Nine of each

Nearest prototype, facelet by facelet, is the obvious method and is wrong. It has no way to know that a face has nine stickers, so under poor light it returns ten of one colour and eight of another and then produces a position that does not exist.

Imposing the count turns classification into a minimum cost assignment: forty-eight patches, forty-eight places, eight per colour beyond the six centres, solved exactly by the Hungarian method. Being confidently right about eight patches then forces the ninth, even where that patch on its own is ambiguous. At forty-eight elements the cubic cost is nothing.

7.3 Colour names a piece, not a sticker

A colouring says what each facelet looks like. A state says which sticker is in each slot, and the second names something the first cannot see. The bridge is the piece: a cubie showing white, red and blue can only be the one white-red-blue corner, and once that is settled each of its three stickers is pinned by its own colour.

This works exactly when a piece's colours name it uniquely, and that is the whole of the restriction to the three by three. Eight corners, twelve edges and six centres, all distinct. A four by four has four indistinguishable centres per face and two indistinguishable wings per edge, so distinct positions genuinely produce identical colourings, and no better camera would settle it because there is nothing left to see. It is the same distinction as section 5, applied to input rather than to output.

7.4 Three quantities that catch the mistakes

Every face turn conserves three things: the corner twists sum to zero modulo three, the edge flips sum to zero modulo two, and the corner and edge permutations have equal parity. Together they cut the reassemblies of a dismantled cube by a factor of twelve, which is the standard result, and the calibration reproduces it by building all twelve combinations of one twist, one flip and one swap and finding exactly one reachable.

Their value here is not the theory, which is old, but that a misread facelet almost always breaks one of them. Across three hundred and sixty readings taken under light bad enough that most of them failed, not one wrong position was accepted: every failure was caught by the sticker counts, by a piece whose colours name nothing, or by one of the three invariants. That is the property worth having, and it survives well past the point where accuracy does not.

The limit on accuracy itself is set by additive sensor noise, which is the one thing the feature space cannot cancel because everything else it handles is multiplicative. All three palettes survive twelve levels out of 255 at full exposure. The site palette gives way first, at around sixteen, and for a reason worth stating: it separates the three opposite face pairs by brightness so that it stays legible in greyscale, and noise attacks brightness directly. The limit is the darkest sticker, which for that palette is a face at a twentieth of full scale.

7.5 The frame, which is the one thing not checked

A reading is in the cube's own frame rather than the room's. Faces are named by where the camera was pointed, so a cube with the colours in any arrangement reads the same. The cost is that the six captures must share a grip, and each step therefore names the face that goes to the top of the frame rather than leaving it to be inferred: the four side faces with up at the top, the up face with back at the top, the down face with front at the top, which is what tipping a cube toward you and away from you actually produces.

Presenting one face a quarter turn off is caught, because rotating a face in place without moving the bands around it is not something turning can do and it produces pieces whose colours name nothing. In two hundred trials it was caught every time. Holding the whole cube in a different orientation throughout is a subtler matter: that is a legal cube seen from elsewhere, and of the twenty-four orientations, the twelve odd ones break the parity agreement and are refused while the twelve even ones are accepted and return the position in a rotated frame. The count is twelve whatever the position, because the even rotations form a subgroup of index two.

7.6 Naming the turns, within a bound

Given two readings, the turns between them can be named without solving anything, by trying all of them. Every product of at most three of the eighteen face turns is enumerated into a table, and the same table is read a second time against the target, which turns a search of eighteen to the sixth into two of eighteen cubed. Skipping two consecutive turns of one face, which always collapse into one, takes the branching from eighteen to fifteen.

This is a search and not a method. It has no heuristic, no notion of what a cube is, and it fails flatly beyond its bound, which is the useful part: a scanner that guesses is worse than one that admits the gap and asks for another look. It declines the superflip, twenty turns away, rather than answering.

The turns it does name are written onto the algorithm, so everything else in the playground goes on describing what is now a real cube: the cycle rings, the return length and the orbit are computed from the same permutation whether it was typed, pressed on the turn pad, or performed in someone's hands between two photographs.

8. What this does not do

It does not solve. The playground computes how long an algorithm takes to return, never how to reach a position or how to leave one. These are not comparably hard: the return length falls out of the cycle lengths in linear time, whereas establishing that twenty face turns always suffice took thirty years and a large donation of computer time. Nothing here should be read as a claim about distance from solved. The superflip is described as the furthest position because that is a published result, not because this measured it.

The bounded search of section 7.6 is the one exception and is worth stating precisely rather than waving at: it can settle any position within six turns of another, which includes positions within six turns of solved. It cannot solve a scrambled cube, and the calibration checks that it declines rather than answers.

It does not track a cube continuously. The camera reads six still faces, not a cube being turned. Following arbitrary turns from any angle needs a trained detector and pose estimation, and more fundamentally a camera that sees three faces at once cannot observe a turn of a hidden one.

The group order is for the three by three. Larger cubes have their own groups and the counting argument in section 3 does not describe them, so the Lagrange check is shown only at that size rather than shown and quietly wrong.

Notation is a dialect. 3R is taken here as the third layer alone and 3Rw as the outer three, following big-cube convention, and x is expanded to every layer of the R family. Sources differ. The parser writes back what it understood, which is the only honest way to handle this: an algorithm copied from a source using the other convention will parse cleanly and describe a different permutation, and the expansion is where that becomes visible.

9. How the engine is checked

The cube group is among the most thoroughly documented finite groups there is, which makes it an unusually good place to check an implementation. Thirty-eight calibration cases run against published values.

These are unusually sensitive to convention errors. The order of R U is 105 only if all six faces turn correctly relative to one another. During development the U and D bands ran the wrong way around the cube and R U came out as 77, not as a slightly wrong value. Two tests localised it:

  • every ordered pair of adjacent faces must give 105, and every opposite pair 4;
  • R U2 D' B D' must give exactly 1260.

Thirty ordered face pairs now pass, and the maximum-order element attains its published maximum.

The piece model of section 7 is derived from the slot convention rather than tabulated, so the two files cannot disagree, and it is checked against the turn engine, which was built without reference to it: every layer turn of a three by three and a four by four must carry every piece to a piece. The reading path is checked without a camera, because classification and reconstruction are pure functions of the patches handed to them. Synthesising those patches from a known position supplies a ground truth no real scan has, namely what the cube actually was.

Two further checks are worth naming because they compare independent routes rather than a computation against itself. The return length is computed once as the least common multiple of the cycle lengths, without ever applying the algorithm, and once by applying the algorithm repeatedly until the cube comes back, without ever looking at a cycle. Both must equal Singmaster's 105. And the group order is derived from the counting argument rather than stored, then checked against the published factorisation exponent by exponent.

References