The Unapologetic Mathematician

Mathematics for the interested outsider

Rubik’s Group and the solution to the cube

Okay, we’re ready to find the structure of Rubik’s group. We’ve established the restrictions stated in my first post. Now we have to show that everything else is possible.

The main technical point here is that we can move any three edge cubies to any three edge cubicles, and the same for corners. I don’t mean that we can do this without affecting the rest of the cube. Just take any three cubies and pick three places you want them to be, and there’s a maneuver that puts them there, possibly doing a bunch of other stuff to other cubies. I’ll let you play with your cubes and justify this assertion yourself.

A slightly less important point is that we only need to consider even permutations of corners or edges. We know that the edge and corner permutations are either both even or both odd. If they’re odd, twist one side and now they’re both even.

Now, let’s solve the edge group. The maneuver
e_F=RUD^{-1}FUD^{-1}LUD^{-1}BUD^{-1}R^{-1}U^{-1}DB^{-1}U^{-1}DL^{-1}U^{-1}DF^{-1}U^{-1}D
has effect (+fr)(+br), flipping two edge cubies, while the maneuver
e_3=R^2UD^{-1}F^2U^{-1}D
has effect (fr\,br\,fl), performing a cycle of three edges. This is all we need, because 3-cycles are enough to generate all even permutations, and one 3-cycle gives us all of them. Similarly, being able to flip two edges gives us all edge flips with zero total flipping.

How does this work? First, forget the orientation of the edges and just consider which places around the cube they’re in. This is some even permutation from the solved state, so it’s made up of a bunch of cycles of odd length and pairs of cycles of even length. Consider an odd-length cycle (a_1\,a_2\,...\,a_k). If we compose this with the 3-cycle (a_k\,a_{k-1}\,a_{k-2}), we get (a_1\,a_2\,...\,a_{k-2}). This is again an odd-length cycle, but two shorter. If we keep doing this we can shrink any odd cycle down to a 3-cycle. On the other hand, we have the composition (a_1\,a_2\,a_3)(a_2\,a_3\,a_4)=(a_1\,a_2)(a_3\,a_4), so we can build a pair of 2-cycles from 3-cycles. We can use these to shrink a pair of even-length cycles into a pair of odd-length cycles, and then shrink those into 3-cycles. In the end, every even permutation can be written as a product of 3-cycles.

And now since we can move any three cubies anywhere we want, one 3-cycle gives us all of them. Let’s pick three — say ub, br, and df — and a maneuver m that sends ub to fr, leaves br alone, and sends df to fl. Such a maneuver will always exist, though it may mess up other parts of the cube. Now conjugate e_3 by M. We know what conjugation in symmetric groups does: it replaces the entries in the cycle notation. So the maneuver me_3m^{-1} has the effect (ub\,br\,df), and we can do something similar to make any 3-cycle we might want. So we can make any even edge permutation we want, and adding a twist makes the odd permutations.

The same sort of thing works for edge flips. Take any pair of edges you want to flip, move them to fr and br, flip them with e_F, and move them back where they started. We can make any flips we need like this.

Together what this says is that the edge group of the Rubik’s cube lives in the wreath product of S_{12} and \mathbb{Z}_2: twelve copies of \mathbb{Z}_2 for the flips, permuted by the action of S_{12}. Specifically, the edge group is the subgroup with total flip zero. We call this group E, and we know E\subseteq S_{12}\wr\mathbb{Z}_2 as a subgroup of order 2.

A very similar argument gives us the corner group. The maneuver
c_T=R^{-1}D^2RB^{-1}U^2BR^{-1}D^2RB^{-1}U^2B
has the effect (+urf)(-dlb), twisting two corners in opposite directions, while
c_3=R^{-1}DRUR^{-1}D^{-1}RU^{-1}
has the effect (urf\,ubr\,lfd), performing a 3-cycle on the corners. Conjugations now give us all 3-cycles, and these make all even corner permutations, and turning one more face makes all corner permutations. Conjugations also can give us all corner twists with zero total twist. This gives the corner group C\subseteq S_8\wr\mathbb{Z}_3 as a subgroup of order 3.

Putting these two together we get the entire Rubik’s Group G\subseteq E\times C as a subgroup of order 2. Here it’s a subgroup because we can only use maneuvers with the edge and corner permutations either both even or both odd, not one of each.

This result gives us an algorithm to solve the cube!

  • First, pick the colors of the face cubies to be on each side.
  • Then write out the maneuver that will take the scrambled cube to the solved one in cycle notation. If the edge and corner permutations are odd, twist one side and start again — now they’ll both be even.
  • Now write the edge permutation as a product of 3-cycles, and make each 3-cycle by conjugating e_3 by an apropriate maneuver.
  • Do the same for the corner permutation, using c_3 as the basic piece.
  • Write down how each edge and each corner needs to be flipped or twisted. Make these flips and twists by conjugating e_F and c_T.

That’s all there is to it. It’s far from the most efficient algorithm, but it exploits to the hilt the group theory running through the Rubik’s Cube. You should be able to apply the same sort of analysis to all sorts of similar puzzles. For example, the 2\times2\times2 cube is just the corner group on its own. The Pyraminx uses a simpler, but similar group. The Megaminx is more complicated, but not really that different. It’s just group theory underneath the surface.

About these ads

March 21, 2007 - Posted by | Group theory, Rubik\'s Cube

4 Comments »

  1. Nice treatment. I made some comments in this direction to a high-school student who e-mailed me from Turkey. He wanted to do a project on how to use group theory to solve Rubik’s Cube. They teach group theory in high school? Who knew? Anyway, I asked for feedback, but I haven’t heard anything.

    There’s also the question of where the magic operators e_F, e_3, c_T, and c_3 come from.

    e_F is a conjugate of [UD^{-1}RUD^{-1}, FUD^{-1}LUD^{-1}B].
    e_3 can be seen as a commutator in the group that includes movement of the whole cube in space.
    c_T is [R^{-1}D^2R, B^{-1}U^2B].
    c_3 is [R^{-1}DR, U].

    The idea is that if we consider the support of an operator to be the set of pieces that are not fixed, then it’s immediate that operators with disjoint support commute, and only a little more tricky to see that operators whose supports intersect very little have simple commutators. I don’t know if this has been formalized anywhere.

    I (or was it Jim Saxe?) used something like this for an “f_T” operator that twists one face-center ninety degrees clockwise and another face-center ninety degrees anticlockwise. You can’t conjugate it by anything except whole-cube moves, but that’s enough to solve the face centers, almost. You also need a magic one-hundred-eighty-degree face-center process we got from Singmaster.

    By the way, in the paragraph that begins “Together” you use S_12 three times, and you should use S_{12}.

    Still a fine article. Happy cubing!

    –Dan

    Comment by Dan Hoey | March 27, 2007 | Reply

  2. [...] not about to sit down and work up a solution like we did before, but it shouldn’t be impossible to repeat the same sort of analysis. I [...]

    Pingback by Rubik’s 7×7×7 Cube « The Unapologetic Mathematician | February 19, 2008 | Reply

  3. [...] Construction of Root Systems (setup) Now that we’ve proven the classification theorem, we know all about root systems, right? No! All we know is which Dynkin diagrams could possibly arise from root systems. We don’t know whether there actually exists a root system for any given one of them. The situation is sort of like what we found way back when we solved Rubik’s magic cube: first we established some restrictions on allowable moves, and then we showed that everything else actually happened. [...]

    Pingback by Construction of Root Systems (setup) « The Unapologetic Mathematician | March 1, 2010 | Reply

  4. [...] first permutation to move everything back where it started from. In fact, this is a lot like what we saw way back with the Rubik’s cube, when dealing with the edge group. We can effect whatever [...]

    Pingback by Construction of D-Series Root Systems « The Unapologetic Mathematician | March 3, 2010 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 391 other followers

%d bloggers like this: