# Possible orders of Rubik's Cube positions



## Ravi (Aug 11, 2010)

A year or two ago, I set out to calculate with pencil and paper the set of all possible orders* of Rubik's Cube positions, combined with the number of positions with each order. The calculation isn't horribly difficult from a theoretical standpoint (SPOILER: details listed below), but my patience didn't last, and I put the question aside.

Today, I tried a similar calculation with a more modest goal: finding only the possible orders. I believe I have succeeded in this. I started by restricting my view to only edges and only corners respectively. The possible cycle structures of edges (or corners) correspond exactly to the partitions of 12 (or 8). I listed all of these partitions in "even permutation" and "odd permutation" columns. Then I found the order of each permutation, noting that for all permutations except a single 12-cycle of edges (or 8-cycle of corners) it is possible for some cycles to be off by a flipped edge (or twisted corner), and therefore that the orders of those permutations can be multiplied by 2 for edges (or 3 for corners). I then tabulated all possible orders for four categories:

ee (edges, even permutation): {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 35, 40, 42, 60}
eo (edges, odd permutation): {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 28, 30, 36, 40, 42, 48, 56, 60, 84, 120}
ce (corners, even permutation): {1, 2, 3, 4, 5, 6, 7, 9, 12, 15, 18, 21, 45}
co (corners, odd permutation): {2, 4, 6, 8, 10, 12, 18, 30, 36}

Since ee only coexists with ce and eo with co, I had Mathematica list all LCMs of an ee order and a ce, as well as LCMs of an eo with a co. Combining the two lists, I obtained the following:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 18, 20, 21, 22, 24, 28, 30, 33, 35, 36, 40, 42, 44, 45, 48, 55, 56, 60, 63, 66, 70, 72, 77, 80, 84, 90, 99, 105, 110, 112, 120, 126, 132, 140, 144, 154, 165, 168, 180, 198, 210, 231, 240, 252, 280, 315, 330, 336, 360, 420, 462, 495, 504, 630, 720, 840, 990, 1260.

These are all possible orders of Rubik's Cube positions. Their frequencies could be found by attaching to each ee/eo/ce/co its frequency (it's not too hard to find the probability of having a "bad" cycle) and carrying these over to the LCMs at the end--this last stage is where I gave up last time.

Feel free to verify my work, or to construct the full table of frequencies. I'd be glad to check your work if you can get some results.

EDIT: This calculation may well have been done before, but I haven't seen it. I googled and oeis-ed the numbers without any results. I once did, however, see a web page listing some short algs for 3x3, 4x4, and 5x5 with given orders--I can't find that page now, and I don't remember who made it, but I remember being so disappointed at the absence of order 11 that I decided to look for the shortest possible pure 11-cycle. (The best I got was L B' F2 L2 U R U L R B2 D R2 B D'.)

*"order" = number of times one must repeat an algorithm before it produces the identity. Here I am abusing notation a little by equating an algorithm with the position it generates when applied to a solved cube.


----------



## TheCubeMaster5000 (Aug 11, 2010)

I wonder what an alg would be for the for the 1260?


----------



## cuBerBruce (Aug 11, 2010)

Yes, this has been done before. A long time ago.

http://www.jaapsch.net/puzzles/cubic3.htm#p34

You are probably thinking of qqwref's page for the orders of 3x3x3 through 3x3x5 cubes. On that page, inner slice, double-layer turns, and cube rotations were also used, so he could have had an order 2520 alg. I see it's still exists: http://www.mzrg.com/rubik/orders.shtml


----------



## Ravi (Aug 11, 2010)

TheCubeMaster5000: 1260 arises only as LCM(28,45). It comes from a 5-cycle and a 3-cycle of corners, both of which must be "bad," and a 7-cycle and two swaps of edges, where at least one of the edge swaps is "bad." Playing around briefly with Cube Explorer yields the 16-move U' B2 D' F2 D L D' F2 L' F2 D F2 L' B2 D R2, which is presumably far from the shortest 1260.

EDIT: The alg above doesn't work. I must have typoed, and I can't recover it. Here's a 17-mover: F L2 F2 B D2 F2 U2 R2 U2 L' U' R L B2 D' B' D2. (even further from the shortest)


----------



## TheCubeMaster5000 (Aug 11, 2010)

That's amazing. I would probably make a chart if I had the time...


----------



## mr. giggums (Aug 11, 2010)

Here's a ramdom 11-cycles I found U B U D' L' F' R' U2 D2 R (10f).


----------



## TMOY (Aug 12, 2010)

Ravi said:


> TheCubeMaster5000: 1260 arises only as LCM(28,45). It comes from a 5-cycle and a 3-cycle of corners, both of which must be "bad," and a 7-cycle and two swaps of edges, where at least one of the edge swaps is "bad." Playing around briefly with Cube Explorer yields the 16-move U' B2 D' F2 D L D' F2 L' F2 D F2 L' B2 D R2, which is presumably far from the shortest 1260.



The following one has been known since at least 1981: R F2 B' U B'. Probably the shortest one.


----------



## cuBerBruce (Aug 13, 2010)

TMOY said:


> Ravi said:
> 
> 
> > TheCubeMaster5000: 1260 arises only as LCM(28,45). It comes from a 5-cycle and a 3-cycle of corners, both of which must be "bad," and a 7-cycle and two swaps of edges, where at least one of the edge swaps is "bad." Playing around briefly with Cube Explorer yields the 16-move U' B2 D' F2 D L D' F2 L' F2 D F2 L' B2 D R2, which is presumably far from the shortest 1260.
> ...



Yes, it's a minimal order-1260 sequence for either FTM or QTM.



Spoiler



My program counted 288 5f* positions and 480 6q* positions of order 1260. So it would seem there are probably 3 distinct 5f* positions mod M+inv, and 5 distinct 6q* positions mod M+inv.


----------



## QCcuber4 (Aug 13, 2010)

Ravi i sent you a message concerning this thread, hope you can reply as soon as possible. This stuff is real awesome, keep at it.


----------



## Ranzha (Aug 13, 2010)

R y.

EDIT: Order 1260.


----------



## Ravi (Aug 19, 2010)

cuBerBruce said:


> Spoiler
> 
> 
> 
> My program counted 288 5f* positions and 480 6q* positions of order 1260. So it would seem there are probably 3 distinct 5f* positions mod M+inv, and 5 distinct 6q* positions mod M+inv.





Spoiler



Correct. In fact, no position of order 1260 can have any symmetries, including inverse symmetries.


*Very messy* (and poorly written) proof of the above claim:


Spoiler



As I mentioned earlier, positions of order 1260 must have edge cycles of 7, 2, 2, and 1 and corner cycles of 5 and 3, with the corner 3-cycle and at least one of the edge swaps "bad." Since one edge is fixed, any symmetries must keep that edge fixed. That leaves only inverses, reflections across center slices, reflections across diagonal planes, and the compositions of any of those. (Note: This includes 180-degree rotations about edge axes, which are the compositions of the two types of reflections above.) The symmetry must also preserve the set of 3-cycled corners. Inverses won't affect that set, but rotations and reflections will. Reflections across center slices swap all eight corners in four pairs, as do the rotations we're concerned with. Those symmetries can't preserve the set of 3-cycled corners; at least one must be switched with a 5-cycled corner. So we are left with reflections across diagonal planes, inverses, and the composition of the two. We now try each of these three possibilities:

1. Pure inverses can't work, because there are cycles of more than two. (Also, an order-1260 element isn't going to be its own inverse. That would make it order-2, if not order-1.)

2. Pure reflections can't work either. Proof: it should be fairly clear that any power of a symmetric position will retain the same symmetry. The 420th power of an order-1260 position must be a pure 3-corner twist (due to the cycle structure), and any reflection of a 3-corner twist will have corners twisted in the opposite direction. Thus the symmetry does not hold.

3. Reflection + inverse: a really annoying case. Let's give it a try. Assume WLOG that the plane of reflection is the one passing through the UFR, DFR, UBL, and DBL corners. Since the other four corners are swapped in pairs (and the 3-cycled corner and 5-cycled corner sets must be preserved), these four other corners (UBR, DBR, UFL, DFL) must contain an even number of each of the two cycles of corners; that is, either 2 of the 3 and 2 of the 5 or just 4 of the 5. Therefore, the corners on the plane of reflection must contain three of one cycle of corners and one of the other cycle. Two cases:
A. FR-BL plane contains one corner of 5-cycle and all of 3-cycle. Then, if our hypothetical order-1260 algorithm cycles corners in the order 1-2-3, its mirror-inverse cycles them in the order 1-3-2, so the symmetry does not hold.
B. FR-BL plane contains three corners of 5-cycle and one of 3-cycle. Then some two of the three 5-cycled corners in this plane must occur consecutively in the 5-cycle (ie. with one sent to another). The mirror-inverse of the 5-cycle would send the second to the first instead of the other way around. Therefore the symmetry does not hold.

None of the cases allow symmetry, so all positions of order 1260 are asymmetric, Q.E.D.



Well, I didn't exactly expect that proof to take until two in the morning. Good luck getting through it. Better yet, just write a better one.


----------



## Rinfiyks (Dec 10, 2010)

Just spent a while trying to find an order 1260 alg that's relatively short. Here's one: U F' U' D2 U2 R'


----------



## Cuc (Feb 22, 2017)

cuBerBruce said:


> On that page, inner slice, double-layer turns, and cube rotations were also used, so he could have had an order 2520 alg.



I wondered why he did not report a 5040 order. For any alg X of order 1260, X y has order 5040. Correct?


----------



## xyzzy (Feb 22, 2017)

Cuc said:


> I wondered why he did not report a 5040 order. For any alg X of order 1260, X y has order 5040. Correct?



Nope. In general, there is no simple rule for calculating the order of gg' given the orders of g and g'. For example, composing an order-2 element with another order-2 element could give you _anything_ if you don't have additional knowledge about the underlying group. (A typical example of "additional knowledge" would be knowing whether the group is abelian, where it's actually possible to calculate the order of gg' (with caveats!), but in this case, the Rubik's cube group is non-abelian.)

Also, 1260 is the maximum order if you're restricted to moves that don't affect the centres (i.e. no slice moves, no wide moves, no rotations), but if you allow for moves that do affect the centres, the maximum order increases to 2520, as mentioned earlier in the thread.


----------

