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

has effect , flipping two edge cubies, while the maneuver

has effect , performing a cycle of three edges. This is all we need, because -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 . If we compose this with the -cycle , we get . This is again an odd-length cycle, but two shorter. If we keep doing this we can shrink any odd cycle down to a -cycle. On the other hand, we have the composition , so we can build a pair of -cycles from -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 -cycles. In the end, every even permutation can be written as a product of -cycles.

And now since we can move any three cubies anywhere we want, one -cycle gives us all of them. Let’s pick three — say , , and — and a maneuver that sends to , leaves alone, and sends to . Such a maneuver will always exist, though it may mess up other parts of the cube. Now conjugate by . We know what conjugation in symmetric groups does: it replaces the entries in the cycle notation. So the maneuver has the effect , and we can do something similar to make any -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 and , flip them with , 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 and : twelve copies of for the flips, permuted by the action of . Specifically, the edge group is the subgroup with total flip zero. We call this group , and we know as a subgroup of order .

A very similar argument gives us the corner group. The maneuver

has the effect , twisting two corners in opposite directions, while

has the effect , performing a -cycle on the corners. Conjugations now give us all -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 as a subgroup of order .

Putting these two together we get the entire Rubik’s Group as a subgroup of order . 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 -cycles, and make each -cycle by conjugating by an apropriate maneuver.
• Do the same for the corner permutation, using 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 and .

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 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.

Flag varieties

As another part of preparing for the digestion of the result, I need to talk about flag vareties. You’ll need at least some linear algebra to follow from this point.

A flag in a vector space is a chain of nested subspaces of specified dimensions. In three-dimensional space, for instance, one kind of flag is a choice of some plane through the origin and a line through the origin sitting inside that plane. Another kind is just a choice of a plane through the origin. The space of all flags of a given kind in a vector space can be described by solving a certain collection of polynomial equations, which makes it a “variety”. It’s sort of like a manifold, but there can be places where a variety intersects itself, or comes to a point, or has a sharp kink. In those places it doesn’t look like -dimensional space.

Flag varieties and Lie groups have a really interesting interaction. I’ll try to do the simplest example justice, and the rest are sort of similar. We take a vector space and consider the group of linear transformations with . Clearly this group acts on . If we pick a basis of we can represent each transformation as an matrix. Then there’s a subgroup of “upper triangular” matrices of the form

check that the product of two such matrices is again of this form, and that their determinants are always . Of course if we choose a different basis, the transformations in this subgroup are no longer in this upper triangular form. We’ll have a different subgroup of upper triangular matrices. The subgroups corresponding to different bases are related, though — they’re conjugate!

Corresponding to each basis we also have a flag. It consists of the line spanned by the first basis element contained in the plane spanned by the first two elements, contained in… and so on. So why do we care about this flag? Because the subgroup of upper triangular matrices with respect to this basis fixes this flag! The special line is sent back into itself, the special plane back into itself, and so on. In fact, the group acts on the flag variety “transitively” (there’s only one orbit) and the stabilizer of the flag corresponding to a basis is the subgroup of upper triangular matrices with respect to that basis! The upshot is that we can describe the flag variety from the manifold of by picking a basis, getting the subgroup of upper triangular matrices , and identifying elements of that “differ” by an element of . The subgroup is not normal in , so we can’t form a quotient group, but there’s still a space of cosets: .

So studying the flag variety in ends up telling us about the relationship between the group and its subgroup . In general if we have a Lie group and a subgroup satisfying a certain condition we can study the relation between these two by studying a certain related variety of flags.