14 October 2008

An upper bound for the order of an element of the Rubik's cube group

The maximum order of an element of the Rubik's cube group R is 462 might be 462, or might be 1260, or might be something else.

Why? The Rubik's cube group is a subgroup of S8 × S12 × Z38 × Z212; the four factors here arise from possible permutations of the edge and corner pieces, and the orientations of the edges and the corners. (This is in fact twelve times as large as the actual group.) More concretely, it's the subgroup of this group consisting of quadruples (σ, τ, v, w), where σ ∈ S8 and τ ∈ S12 have the same parity, v is an element of Z38 whose coordinates sum up to zero, and w is a similar element of Z212. The group operation in this group is given by working componentwise.

(If I have misunderstood what I've heard about Rubik's cubes, then please ignore the rest of this post.)

[edited, 8:48 pm: turns out I have, as the multiplication isn't exactly componentwise.]

So the order of (σ, τ, v, w) is the least common multiple of the orders of σ, τ, v, w in S8, S12, Z38, and Z212 respectively. Call these o(σ), o(τ), o(v), o(w). If σ has one 7-cycle and one 1-cycle, τ has one 11-cycle and one 1-cycle, and v and w are nontrivial, then o(σ) = 7, o(τ) = 11, o(v) = 3, o(w) = 2, and so the order of (σ, τ, v, w) is lcm(7, 11, 3, 2) = 462. (This corresponds to a sequence of moves, whatever it may be, that permutes seven of the corners and eleven of the edges cyclically, and disrupts the orientations of both the corners and the edges.) Note that σ and τ are both even permutations.

Furthermore, we can't do better. I don't think there's a particularly elegant proof, but it's not hard to check by brute-force computation that no choice of the cycle types for σ and τ which gives both the same parity allows us to do better. If you let σ have one cycle of order 8, and τ have one cycle of order 7 and one of order 5, and let v, w both be nontrivial, then you'd think the order of (σ, τ, v, w) was lcm(8, 35, 3, 2) = 840, but σ is odd and τ is even. In fact, that's how I got the number 462 -- take lcm(s, t, 3, 2) where s ran over possible orders of elements of S8 and t ran over possible orders of elements of S12; the largest number you get this way is 840, but it can only come about in the way I described. 462 is the next-largest.

In case you're wondering how I came to this question -- it's easy to see if you play around with the cube that if you do the same sequence of moves over and over again, you eventually get back where you started. (Theoretically, this is a consequence of the fact that any element of a group has finite order.) So I just started to wonder how many times you might have to do the same sequence of moves on a solved cube to get it back to the solved state.

7 comments:

Boris said...

Once, I tried to solve a Rubik's cube without having any prior knowledge of algorithms for solving the cube, or any sequences of moves accomplishing desired tasks, etc. (I succeeded after 10 hours; note that I also wasn't using paper. By the way, it seemed to me that the hardest thing by far was having a solved cube except for two adjacent corner pieces.)

At some point, I ran out of ideas for how to accomplish a certain sub-task. I decided to get more ideas by choosing "random" elements of the Rubik's cube group with low order. I reasoned that a good way of generating those would be to pick a random element g, figure out its order n "the dumb way", and then take g to the power of n/k for some small divisor k of n. This would produce a "random" element of order k.

Even though I succeeded in finding good maneuvers, let's just say that I also became acquainted with some elements of large order ...

unapologetic said...

The operation isn't exactly componentwise. There are two wreath products going on, so permuting the edges (or corners) doesn't commute with a collection of edge-twists (or corner-flips).

Michael Lugo said...

John,

I had a feeling I was oversimplifying things. Thanks.

unapologetic said...

I should, of course, show a counterexample as well: Twisting the right face of the cube by 90 degrees and then turning the whole cube around the vertical axis by 90 degrees has order 1260. And that is maximal.

Michael Lugo said...

John,

I'm not sure that counts as a counterexample. Implicit in my framing of the problem is the idea that the cube stays in a fixed position, so you're really talking about the move RBLF in the usual notation, which would have order 1260/4 = 315. (That is, (RBLF)^315 is the identity and no smaller power is -- assuming your claim of 1260 is correct.)

unapologetic said...

In my modified cycle notation (outlined here) the move I mean has cycle structure:

(+ufl ulb ubr rdf) (+urf) (+dlf dbl drb) (+uf ul ub ur rf) (+df dl db dr lf bl rb) (f l b r)

Okay, here's another one that *does* satisfy your requirement of not making cube moves. It doesn't even use middle-layer moves:

RU^2D^{-1}BD^{-1}

with cycle structure:

(-ufl lbu rfu) (+ubr fdl dfr rbd ldb) (+uf lb dr fr ul ur bu) (+dl rb) (df db)

Orders 9, 15, 14, 4, 2. Least common multiple is 1260.

kowalski@math.ethz.ch said...

According to Magma (and assuming the generators in S48 of the group R that I found here are correct), the maximal order is 1260 (and there are 8 conjugacy classes of order 1260, out of 81120).