Things I saw at ANALCO '09

1. a picture of a Rubik's cube subwoofer. (They're only making 200, so I could never afford one.) This was actually in the magazine in my hotel room, so it's really just a coincidence.

2. An actual copy of Flajolet and Sedgewick's book Analytic Combinatorics. (Cambridge University Press had a display table.) I was not the only person who didn't believe it was actually a book. (In fact, Sedgewick seemed a bit surprised.) It appears to be very nice as a physical object, and in particular is surprisingly un-brick-like for an 800-page book.

3. A bunch of talks, many of which were interesting. I may have more commentary on the ones I found particularly interesting once I read the associated papers.

NYT profiles of Jessica Fridrich

Specializing in Problems That Only Seem Impossible to Solve , by Bina Venkataraman, in yesterday's New York Times.

This is an article about Jessica Fridrich, a professor at Binghamton University, who at one point held the world record for the fastest solving of the Rubik's Cube. She currently specializes in the research of information hiding in digital imagery.

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 S₈ × S₁₂ × Z₃⁸ × Z₂¹²; 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 σ ∈ S₈ and τ ∈ S₁₂ have the same parity, v is an element of Z₃⁸ whose coordinates sum up to zero, and w is a similar element of Z₂¹². 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 S₈, S₁₂, Z₃⁸, and Z₂¹² 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 S₈ and t ran over possible orders of elements of S₁₂; 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.

Rubik's cube hustling?

So I've finally memorized a solution to the Rubik's Cube. (I may be speaking too soon; let's see if the move I could never remember is still in my head tomorrow.)

I'm very slow, though. It's not the most efficient solution.

That got me thinking. There are pool hustlers, who act like they're no good at pool, start taking bets, and then all of a sudden are really good. If someone could solve the Rubik's cube really quickly, could they make money off it as a Rubik's cube hustler? Bring the cube somewhere where there are people, act like you can only solve it slowly, take bets, and then solve it quickly.

It just might work.

It would be crucial to find the right audience, though -- somewhere where people are familiar with the cube. So a bar, the typical place for pool hustling, wouldn't work. The right math department might work. But not mine -- I have readers within my department, and I'm pretty sure I've given too much away by making this post. Fortunately I don't have the skill to pull this off anyway.

Rubik's deck of cards?

By Igor Kriz and Paul Siegel, at Scientific American: Rubik's Cube Inspired Puzzles Demonstrate Math's "Simple Groups".

The Rubik's cube can be said to be a physical embodiment of the Rubik group, which is a certain subgroup of S₄₈. (Why 48? There are 54 "facets" of the Rubik's cube, nine on each side; six of these don't move, leaving 48.) This subgroup has an easy presentation with six generators, namely rotations of the six faces. As the authors point out, other "Rubik's-type" puzzles embody groups of the same general sort.

The authors have invented puzzles based on certain sporadic groups, namely theMathieu groups M₁₂ and M₂₄ and the Conway group Co₀. These right now only exist as computer programs, although the authors claim that a physical version of the M₂₄ puzzle could be built.

A possibly interesting, although not-at-all well-defined question -- which groups are "buildable", in the sense that one can build a physical object that represents them?

The programs (which run on Windows machines) can be downloaded from Igor Kriz's home page.

Thanks to John Armstrong for pointing me to the article.

Large Rubik's cubes and asymptotic thoughts

A video of the solution of a Rubik's cube of side 100, from YouTube.

I don't know the details of the algorithm, but it has the interesting property that at first it looks like nothing's happening, and then larger and larger blocks of each color seem to form -- I'm not sure if this is because of the low resolution or if this really is some sort of "phase transition" in the algorithm. This is the sort of thing one just doesn't see in the normal-sized cube.

I came to this from a solution of the size-20 cube, which works in a much different way; each of the faces of the cube gets "filled in" in turn. So in the second case the algorithm appears to be making steady progress; in the first case it doesn't. There are essentially two different families of algorithm.

It would be interesting to know how the solution time (measured in number of moves) of these families of algorithms -- and I'm calling them "families" because I suspect that the actual side length of the cube isn't all that important -- scales with time. Also, how do these algorithms compare with the asymptotically fastest one? One could compute a lower bound on the number of moves needed to solve a Rubik's cube of arbitrary size by just computing the number of possible positions (analogously to the calculation of that number for the normal cube I outlined here) and comparing that to the number of possible moves one can make from a given position. An absolutely useless question -- is that lower bound (I worked it out once, but I forget what it is, and it was the sort of the back-of-the-envelope work that might have been wrong anyway) asymptotically tight? That is, does there exist a solution procedure for the Rubik's cube for which the number of moves needed to solve the size-n cube is within a constant factor of this obvious lower bound?

As for what that lower bound is, I may write that up as another post; I'd either need to find the notes I made on it a few months ago or (more likely) rederive them.

A Mobius strip video

A video about the Mobius strip, with an interesting choice of background music.

This video illustrates certain classical facts about the Mobius strip:
- if you draw a line down the middle of the Mobius strip, it runs down "both sides" of it (by which I mean both sides of the original sheet of paper; the Mobius strip isn't orientable)
- if you cut along that line, you end up with a long twisted strip;
- if you cut along a line one-third of the way from one of the edges of the original strip of paper to the other, you get two linked strips, of equal thickness but different lengths;
and another fact I didn't know:
- if you cut along a line one-quarter of the way from one of the original edges to the other, you get three linked strips (I assume at least one of them is Mobius), but now one is twice as wide as the other two. (But I think there's something trickier going on with the cutting here; it's hard to get a good look.)

Also, breaking the underwater one-handed Rubik's-cube-solving record. I can't make this stuff up.

(These are both from is from sciencehack, which is a site for science videos that claims that "every science video on ScienceHack is screened by a scientist to verify its accuracy and quality". Apparently they don't host the videos; they just index other people's science-related videos.) Here is their index of mathematics videos.0

another shot at Rubik's cube

On Monday I wrote that the Rubik's cube can be solved in 26 moves, where a move is defined as a half-turn or a quarter-turn of any face.

I'd forgotten that number, which I got from Wikipedia.

Then I came across this article at MathTrek, claiming 26 moves. The strategy was basically as follows: find the positions from which one could get to the starting position by making only half-turns, and no quarter-turns (call this set S); it turns out that from any of these, one can get to the starting position in 13 moves, and there are about 15,000 of them. Then the remaining items were put into sets such that the members of any such set only differed by half-turns; this roughly means that it's enough to reduce a single member of each set to some member of S. There are 1.4 trillion such sets, which sounds like a lot but is only one part in 30,000 of all the configurations of the cube. It turns out that a member of each such set can be reduced to a member of S in 16 moves, and 13+16 = 29. But the algorithm implied here solves most configurations in 26 moves or less; those that weren't, they solved by a brute-force computation.

Now, this sort of two-stage computation could probably be made better if the two stages were roughly equal in "size", that is, if 15,000 and 1.4 trillion (the product of which is roughly the number of configurations of the Rubik's cube) were equal. This is since the computation time is roughly proportional to the sum of these. If we have the constraint that the product of two numbers x and y is a known constant k, then we can minimize the sum of those numbers by taking x = y = k^1/2. Of course, in the case of the Rubik's cube there might not be some natural class of configurations with size roughly the square root of the total number of configurations.

Similarly, if we had a problem with k possible configurations and a three-stage reduction, you'd ideally want to reduce the number of possible configurations by a factor of k^1/3 at each stage.

But this is probably all useless, because if there were two intermediate subgroups you could reduce to, you'd probably want to take both of them even if you weren't lucky enough to have them at sizes k^1/3 and k^2/3 as would be ideal.