The Unapologetic Mathematician

Mathematics for the interested outsider

Sudocube

DO WANT

Tipped off to its existence by Alexandre Borovik.

September 24, 2008 Posted by | Rubik\'s Cube | 1 Comment

A Puzzlement

Randall’s got an analogy for Rubik’s cube. Like the cube, there’s a trick to it. Unlike the cube, it doesn’t really illustrate any interesting mathematics. Also unlike the cube, I’m not about to go telling everyone what the trick is out in public.

I mean, sure, it’s not like I’m using it or anything, but it’s the principle of the thing.

August 1, 2008 Posted by | Rubik\'s Cube | 2 Comments

Rubik’s 7x7x7 Cube

From Alexandre Borovik I find this video of someone solving the “order seven” Rubik’s Cube.

I’m 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 will point out, however, that the solver in this video is making heavy use of both of our solution techniques: commutators and a tower of nested subgroups.

The nested subgroups are obvious. As the solution progresses, more and more structure becomes apparent, and is preserved as the solution continues. In particular, the solver builds up the centers of faces and then slips to the subgroup of maneuvers which leaves such “big centers” fixed in place. Near the end, almost all of the moves are twists of the outer faces, because these are assured not to affect anything but the edge and corner cubies.

The commutators take a quicker eye to spot, but they’re in there. Watch how many times he’ll do a couple twists, a short maneuver, and then undo those couple twists. Just as we used such commutators, these provide easy generalizations of basic cycles, and they form the heart of this solver’s algorithm.

Alexandre asked a question about the asymptotic growth of the “worst assembly time” for the n\times n\times n cube. What this is really asking is for the “diameter” of the nth Rubik’s group G_n. I don’t know offhand what this would be, but here’s a way to get at a rough estimate.

First, find a similar expression for the structure of G_n as we found before for G_3. Then what basic twists do we have? For n=3 we had all six faces, which could be turned either way, and we let the center slices be fixed. In general we’ll have \lfloor\frac{n}{2}\rfloor slices in each of six directions, each of which can be turned either way, for a total of 12\lfloor\frac{n}{2}\rfloor generators (and their inverses). But each generator should (usually) be followed by a different one, and definitely not by its own inverse. Thus we can estimate the number of words of length l as \left(12\lfloor\frac{n}{2}\rfloor-2\right)^l. Then the structure of G_n gives us a total size of the group, and the diameter should be about \log_{\left(12\lfloor\frac{n}{2}\rfloor-2\right)}(|G_n|). Notice that for n=3 this gives us 20, which isn’t far off from the known upper bound of 26 quarter-turns.

February 19, 2008 Posted by | Rubik\'s Cube, Special Topics | 6 Comments

Rubik’s Cube Wrapup

I want to tie up a few loose ends about Rubik’s group today.

We can fit Rubik’s group into a sequence that more clearly shows all the structure I’m talking about. Specifically, it’s a subgroup of the bigger group I mentioned back at the beginning. We can restate the three restrictions as saying the maneuvers in Rubik’s group are those in the kernel of a certain homomorphism. So, first let’s write down the big group.

The unrestricted edge and corner groups are just wreath products, which I’ll write out as semidirect products. Without restrictions, these two groups are independent, so we just have a direct product to give the unrestricted Rubik’s group.
\bar{G}=\left(\mathbb{Z}_2^{12}\rtimes S_{12}\right)\times\left(\mathbb{Z}_3^8\rtimes S_8\right)
I’ll write (((e_1,e_2,...,e_{12}),\sigma_e),((c_1,c_2,...,c_8),\sigma_c)) for a generic element of this group. Each part of this list corresponds to part of the expression for \bar{G} above.

Now we want to add up all the edge flips and make them come out to zero. We can write this sum as a homomorphism:
e:\bar{G}\rightarrow\mathbb{Z}_2
e(((e_1,e_2,...,e_{12}),\sigma_e),((c_1,c_2,...,c_8),\sigma_c))=e_1+e_2+...+e_{12}
where the sum is taken in the group \mathbb{Z}_2. You should be able to verify that this actually is a homomorphism. Similarly, we want the sum of the total twists as a homomorphism:
c:\bar{G}\rightarrow\mathbb{Z}_3
c(((e_1,e_2,...,e_{12}),\sigma_e),((c_1,c_2,...,c_8),\sigma_c))=c_1+c_2+...+c_8
where the sum is taken in \mathbb{Z}_3.

Finally, the permutation condition uses the “signum” homomorphism from a symmetric group to \mathbb{Z}_2. It assigns the value {}0 to even permutations and the value 1 to odd ones. We use it to write the last restriction as a homomorphism:
p:\bar{G}\rightarrow\mathbb{Z}_2
p(((e_1,e_2,...,e_{12}),\sigma_e),((c_1,c_2,...,c_8),\sigma_c))={\rm sgn}(\sigma_e)+{\rm sgn}(\sigma_c)

Now we assemble our overall restriction homomorphism as the direct product of these three:
f=e\times c\times p:\bar{G}\rightarrow\mathbb{Z}_2\times\mathbb{Z}_3\times\mathbb{Z}_2
and get the short exact sequence:
\mathbf{1}\rightarrow G\rightarrow\bar{G}\rightarrow^{f}\mathbb{Z}_2\times\mathbb{Z}_3\times\mathbb{Z}_2\rightarrow\mathbf{1}

Commenter Dan Hoey brought up where my fundamental operations come from. To be honest, these four are just ones I remember off the top of my head. He’s right, though, that there are systematic ways of coming up with maneuvers that perform double-flips, double-twists, and 3-cycles. I’ll leave you to read his comment and work out yourself that you can realize four such basic maneuvers as commutators — products of elements of the form m_1m_2m_1^{-1}m_2^{-1}. This means that the commutator subgroup \left[G,G\right] of Rubik’s group is almost all of G itself. It just misses a single twist. In fact, G/\left[G,G\right]\cong\mathbb{Z}_2 — Rubik’s group is highly non-abelian.

Incidentally, this approach to the cube is not the first one I worked out, but it’s far more elegant than my pastiche of particular tools. I picked it up back when I was at the University of Maryland from a guy who had worked it out while he was at Yale as a graduate student back when the cube first came out: Jeff Adams.

March 28, 2007 Posted by | Group theory, Rubik\'s Cube | 2 Comments

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.

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

Restrictions of Rubik’s Group

Today I’m going to prove the other two constraints I mentioned in the first post about Rubik’s Group: the total corner twist and the total edge flip must both be zero.

First I’ll tackle the corner flipping. Imagine a cube painted with just black and white. All the facelets are black, except for the four corners of the top face and the four corners of the bottom face. If you’ve got a real cube in front of you, tape a little bit of paper onto each of those eight facelets. We’re going to look at how a maneuver twists the corners by looking at how it moves those marked facelets.

Now every maneuver is a composition of the six basic moves U, D, R, L, F, and B. If we can show that these all have a net twist of zero then any composition of them must also have net twist zero. The moves U and D are easy: they don’t change the marked facelets at all.

Now let’s consider the move R. After twisting the right face of the cube, the four marked facelets on the left are left alone. The upper-front corner on the right was marked on the top, but now is marked on the front. That’s an anticlockwise twist of 1/3 if we look directly at that corner. The upper-rear corner is now marked on the back, which is a clockwise twist of 1/3. The lower-front is twisted clockwise by 1/3, and the lower-right is twisted anticlockwise by 1/3. Adding all of these up, we get a total twist of zero.

The moves L, F, and B are similar: each changes which facelet of four corners is marked. Each twists two markings clockwise and two markings anticlockwise, for a total twist of zero. If we do any maneuver and look at which facelet of each corner is marked, the total twist from the starting position will always be zero.

The restriction on edge flips is proved similarly. This time mark the top facelets of the four upper edges, the bottom facelets of the four lower edges, the front facelets of the two front middle edges, and the back facelets of the two rear middle edges. Now the four moves U, D, R, and L send marked facelets to marked facelets. The moves F and B flip the markings on the four edges that they move, and four flips is the same as zero flips, since flipping an edge twice returns it to its original state. If we do any maneuver, the total number of markings that have been flipped from the starting position will always be even, for a net flip of zero.

We can use this to analyze the cycle structure of a maneuver. Let’s say that the cycle notation of a maneuver M contains a positively twisted cycle of length k on the corners. If we do the maneuver k times, it returns those k cubies to their original cubicles, each twisted once clockwise. That is, M^k has a total twist of k on these cubies. Since each copy of M does the same thing, that’s one twist each time we perform M. If we look at all the corner cycles in M, some will have a positive twist, some a negative twist, and some no twist. The number of positively twisted cycles minus the number of negatively twisted cycles must be a multiple of three, since three twists counts as zero total twist.

The same goes for the edges. Each flipped edge cycle in M contributes a single net flip, and the total number of flips has to be even. You can check yourself that all the cycle notations I wrote down last time satisfy both of these conditions. You can also see that the parity of the edge permutation and the parity of the corner permutation are equal in each example.

So I’ve established that the total edge flip is zero, the total corner twist is zero, and the parities of the edge and corner permutations are equal. When I come back to the cube I’ll show that we can realize any maneuver whose cycle notation satisfies these three conditions can be realized as a composition of basic twists. That will lead us to the structure of Rubik’s Group, and to a solution of the Cube.

March 7, 2007 Posted by | Group theory, Rubik\'s Cube | 2 Comments

Rubik’s Group notation

Today I want to introduce some notation for discussing the cube.

Take a cube — either a real one, the Java version, or just one in your mind’s eye — and hold it with the center cubies fixed in place pointing up, down, left, right, front, and back. Twists of the faces will generate Rubik’s goup G. We pick the six generators as follows

  • U is a twist of the upper face by a quarter turn clockwise, looking down at the top of the cube.
  • D is a twist of the lower face by a quarter turn clockwise, looking up at the bottom of the cube.
  • R is a twist of the right face by a quarter turn clockwise, looking left at the right side of the cube.
  • L is a twist of the left face by a quarter turn clockwise, looking right at the left of the cube.
  • F is a twist of the front face by a quarter turn clockwise, looking at the front of the cube.
  • B is a twist of the back face by a quarter turn clockwise, looking at the back of the cube.

For instance, executing B involves turning the whole cube around to look at the back, twisting that face clockwise by 90°, and turning the cube back to the original orientation.

For each twist T, the 180° twist of the corresponding face is T^2, and the anticlockwist twist is T^{-1}. Four quarter-twists is the same as doing nothing, so T^4 is the identity.

It’s also useful to label the cubicles. I’ll do this by listing the faces it touches. The face cubicle on the left side of the cube is l, the lower edge on the back ls db or bd. The upper-right corner on the front of the cube is urf, ufr, ruf, rfu, fur, or fru. The order of the faces doesn’t matter so much for a single cubicle, but becomes important when we start thinking about how maneuvers affect the state of the cube.

For instance, the effect of the maneuver R^2U^{-1}DB^2UD^{-1} has an effect on the cube I’ll write as (fr\,bl\,br). This takes the cubie in the front-right cubicle and puts it in the back-left cubicle, with the facelet that was in the front now in the back and the facelet from the right now on the left. It takes the cubie from the back-left cubicle and puts it in the back-right cubicle with the facelet from the back still on the back and the facelet from the left now on the right. Finally it takes the cubie from the back-right and moves it to the front-right with the right facelet still on the right and the back facelet now on the front.

As another example, (R^{-1}U^2RB^{-1}U^2B)^2 takes the cubie from the upper-right-front cubicle and leaves it where it is, but twists it to the right, and similarly twists the cubie in the lower-left-back cubicle. We write this transformation as (urf\,rfu\,fur)(dlb\,lbd,bdl). For shorthand we’ll modify this permutation notation slightly. When a cycle brings a cubie back to its starting cubicle but rotated, we add a sign. In this example we’ll write (+urf)(-dlb), since if we look directly at the upper-right-front cubie it’s been rotated clockwise by 1/3 of a turn and looking directly at the lower-left-back it’s been rotated anticlockwise by 1/3 of a turn.

This notation does make sense. Let’s say that we have a maneuver whose effect contains some cycle on the corners of the cube of length k. If we apply that maneuver k times each cubie in the cycle comes back where it started, but the cubies may have been twisted in the process. Each one will be twisted by the same amount: either 1/3 to the right, 1/3 to the left, or untwisted. The sign in the notation tells us what that twist is.

The same notation goes for edges. The maneuver RUD^{-1}FUD^{-1}LUD^{-1}BUD^{-1} has effect (+ur)(+fr)(+fl)(+bl), flipping those four edges. We could write this out as (ur\,ru)(fr\,rf)(fl\,lf)(bl\,lb), but the “twisted permutation” notation is more compact.

From this notation it’s easy to compute the order of a maneuver — what power of the maneuver returns to the identity transformation. A corner cycle of length k has order k if there’s no twist, and order 3k if there is a twist. Similarly, an edge k-cycle has order k if there’s no flip and order 2k if there is a flip. So if we write the effect of a maneuver as a twisted permutation we can find the order of each twisted cycle. The order the the whole maneuver is the least common multiple of those orders.

As an example, consider the maneuver RU. This has effect (+urf)(-ufl\,ulb\,ubr\,bdr\,dfr)(fr\,uf\,ul\,ub\,ur\,br\,dr). The three twisted cycles have orders 3, 15, and 7, so the total order is 105. If you actually sit and perform (RU)^{105} you’ll get back exactly where you started.

February 28, 2007 Posted by | Group theory, Rubik\'s Cube | Leave a comment

Rubik’s Magic Cube

Rubik’s Cube is a classic fad from the ’80s. Invented by architecture professor Ernő Rubik in 1974 as an illustration of design principles, it became an immensely popular puzzle for a while. Now it’s a hallmark of geekiness — when I visited Dartmouth I saw at least six or seven floating around the graduate student lounge.

What’s most interesting to us here is that it’s also a big case study in group theory. The official website has a pretty good Java implementation, for those who don’t remember (or who have repressed their memories of) the cube. I’ll start talking about the cube after the jump.
Continue reading →

February 22, 2007 Posted by | Group theory, Rubik\'s Cube | 17 Comments