The Unapologetic Mathematician

Mathematics for the interested outsider

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 »

  1. To answer Borovik’s question — I think the answer, for large n, is something like Cn2/log(n). I may try to explain this in more detail but the computation’s kind of confusing.

    But to give a sketch: to estimate |G_n| sufficiently precisely to get the sort of estimate you’re looking for (which really is not that precisely at all), you have to consider:
    – first, the orbits of indidivudal cubicles under the action of the various generators of the group;
    – second, the orientations that cubicles within each orbit can take.
    For example, in your previous analysis there are eight corner cubicles, which can be placed in the eight corner spaces in 8! different ways; there are then 38 ways to orient them.
    Then there’s a factor that we have to divide by (12 in the n = 3 case) which is the number of orbits that you mention here. I’m assuming this factor doesn’t grow too quickly with n, for no good reason.

    It turns out that for large n, “most” of the multiplicative factors in the upper bound one obtains for |G_n| in this way come from cubicles which are in the interior of one face or another, and not on any of the symmetry planes of the cube. In particular, there are roughly n2/8 different orbits of face cubicles; each of them is of size 48. So the number of possible positions |G_n| is in some sense “like” (48!)^(n^2/8); so log |G_n| is n2 times a constant. The log n in the denominator comes from the fact that your estimate of the denominator is the base-O(n) log of |G_n|.

    The constant C which I mentioned above is log(48!)/8, which is about 18 if you use natural logs — but don’t try to test it on known results for n = 3, because the 3-by-3-by-3 cube looks nothing like the general case. In the traditional cube the faces have no interiors!

    This might turn into a post on my blog… but I’ve really got other, more important things I should be writing about!

    Comment by Isabel Lugo | February 20, 2008 | Reply

  2. Even if you don’t post about it, that’s great work right off. It’s the sort of practical, problem solving, analytical mathematics I’m not great with, but which gets hired a lot more.

    Comment by John Armstrong | February 20, 2008 | Reply

  3. The 2008 Abel Prize has been awarded to Thompson and Tits:

    http://www.abelprisen.no/en/prisvinnere/2008/

    The announcement specifically mentions Rubik’s Cube as an example of the utility of symmetry groups.

    I see the award to Tits— for his theory of buildings, which in a sense realizes the other half of Klein’s proposed duality between groups and geometries— as further evidence of a resurgent appreciation of the importance of Klein’s legacy.

    Chris Hillman

    Comment by Chris Hillman | March 27, 2008 | Reply

  4. […] Abel Prize As Chris Hillman just pointed out in a comment, the 2008 Abel Prize went to John Griggs Thompson and Jacques Tits “for their profound […]

    Pingback by 2008 Abel Prize « The Unapologetic Mathematician | March 27, 2008 | Reply

  5. Where can I get this cube “Rubik´s 7x7x7????
    rgds N.

    Comment by Nicole Frank | December 10, 2009 | Reply

  6. I don’t know, Nicole. I’d go ask whoever posted the video on YouTube.

    Comment by John Armstrong | December 10, 2009 | Reply


Leave a comment

« Previous | Next »