Thread: Disjoint Cycle Decomposition

Problem:

Get a Rubik's cube and determine the order of the move "rotate top face a quarter-turn clockwise and then the right face a quarter-turn away from you." That is, how many iterations of this move will return a clean cube to a clean cube again? Write this move out as a permutation of the pieces in a Rubik's cube and then find its order using the disjoint cycle decomposition of that permutation.

I used the Rubik's Cube, and found the answer to be 63. However, I am unsure as to how to write the move as a permutation of the pieces and using cycle decomposition to find it's order.

The answer I get is either 105 or 210, depending on the possible flipping of a side orientation that I haven't determined yet. One of us has made a mistake somewhere.

My idea would be to do this in 2 parts. The part I'll do first just tracks the *position* of the pieces, not their orientation.

Call the combined move M = "top a quarter clockwise, then right a quarter away".

Here's my labelling:
Do the top first:
Label top-front side as s1. Then continue labelling the sides on the top clockwise (looking down) as s2, s3, s4, so that s4 is on the top-right.
Label top-right-front corner as c1. Then continue labelling the corners on the top clockwise (looking down) as c2, c3, c4, so that c4 is on the top-right-back.
Now the 5 remaining pieces on the right side:
From s4, going away from you (i.e. with R), the sides are s5, s6, and s7, so that s7 is the front-right.
Label bottom-right-back as c5 and bottom-right-front as c6.

Then as permutation cycles:
T (top) = (c1 c2 c3 c4)(s1 s2 s3 s4) and R (right) = (c1 c4 c5 c6)(s4 s5 s6 s7)
M = R T (multiplying ordered by function composition) = (c1 c2 c3 c5 c6)(s1 s2 s3 s5 s6 s7 s4)
Thus, since those are independent cycles, the order of M is lcm(5, 7) = 35.

Thus every 35 combined moves M, the pieces will return to their original position.

But the Cube won't then necessarily be in its original state, because the orientations of the pieces might (will) have been permuted.

Observe c4, which is the only invariant peice of the combined move M.
If I label c4's sides by: c4_T, c4_B, and c4_R (top, back, and right), then when T sends c4 to c1, have at c1 that: top=c4_T, front = c4_R, and right = c4_B.
Then when R acts on c1, sending it back to c4, get at c4: top = c4_R, back = c4_T, and right = c4_B.
Thus when do M, act on the sides of c4 by: Top->Back, Right->Top, Back->Right.
M fixes c4's position, but effects its orientation as a permutation (written as a cycle): (Top, Back, Right). Call this permutation p4.

Since p4 has order 3, and effects c4 with every application of M, after 35 moves will have applied p4 to c4 35 times, which is the same as applying it twice (since every 3 is the identity).
So 35 moves to get the peices right, but now p4 has applied twice to c4.
Another 35 moves to get the peices right, but now p4 has applied 2 + 2 = 1 (mod 3) times to c4.
Do a final 35 moves, and p4 has no been applied to c3 a number of times divisible by 3, so that c4 is in the correct orientation.

Thus it takes 105 moves to get the peices back AND have c4 oriented correctly.

Every side peice after 35 moves M will be in the correct position, but might have its orientation wrong. For side peices, there's only two orientations.
Thus M repeated 35 times, seen as acting on the orientation of a side piece, either returns it correctly, or flipped it.
If it flipped it after 35 times, it flipped it after 105 times ( = 3 x 35).
Thus must do a whole 105 applications of M again to both put c4 into its initial state (w/ orientation) and put this bad side peice into its initial state (w/ orientation).

Note that if have one "side piece that was flipped after doing M 35 times", then must do the full 210, however, that will cover *every* side piece that way flipped.

Now consider the corners orientations. After 35 applications of M, they'll be in the right location, but their might have changed as it did for c4. Like c4, we can label the sides of the corner peice and then consider every 35 applications of M to act as a permutation of those 3 sides. The possibilities are, after doing M 35 times, a coner piece's orientation permuation is either the identity, or a 2-cycle, or a 3-cycle.
If it's a 3 cycle, then the 105 applications of M is 3 applications of the permutation, hence sets it right.
If it's a 2 cycle, then as with the sides, we'll need to double to 210 applications to set it right.

Summary:
1) It takes 35 applications of M to get the positions correct.
2) It takes a multiple of 105 applications of M to hope to get the orientations correct.
3) If after 35 applications of M, a side piece is flipped, OR a corner peice has had its orientation permuted as a 2-cycle, then it takes exactly 210 applications of M to return the cube to its initial state. Otherwise, it takes exactly 105 applications of M to return the cube to its initial state.