A press release from MIT reports on a new theorem of Erik Demaine, Martin Demaine, Sarah Eisenstat, Anna Lubiw, and Andrew Winslow: the group of transformations of the n x n x n Rubik’s cube has diameter on order n^2 / log n in the standard generators. The press release quotes (Erik) Demaine as saying

“That that’s the answer, and not N

^{2}, is a surprising thing,”

That they were able to prove this is surprising, and impressive, indeed! Upper bounds on diameters of Cayley graphs are hard; you use a big spectral hammer if you have one at hand, and otherwise you really have to get dirty and explain algorithmically how you’re going to get all the group elements from short words. And in general, the best you can hope for is an asymptotic result like the one obtained by Demaine et al; the precise diameter of the 3x3x3 Rubik’s group was only just determined to be 20 with the help of 35 CPU-years donated by Google.

But the *truth *of the theorem is much less surprising, in my opinion. Let’s start with the lower bound, which is easy, as Demaine recounts.

“In the first hour, we saw that it had to be at least N

^{2}/log N,” Demaine says.

Why was this so fast? Because the number of generators is just 6 N; for each of the 3 coordinate axes, there are N clockwise quarter-turns perpendicular to the axis and N counterclockwise quarter-turns. So the total number of words of length k in those generators is on order N^k; for this to cover the whole group, whose size is known to be exponential in N^2, you need k to be at least N^2 / log N.

If all those words were distinct, then the diameter of the group would be N^2/log N. But they’re not distinct! The Rubik’s group has relations; it is not free. Far from it.

But *how* far from it, is the question.

To measure this, we write W(k) for the number of distinct words of length k, or “the volume of the word ball.” If the group were free on the given generators, we’d have W(k) = (6N)^k, exponential in k. If, on the other hand, the group were free *abelian* on the given generators, W(k) would be on order of k^(6N), polynomial in k. Commutativity crushes words together a lot. And notice that a lot of the Rubik generators commute with each other: whenever two twists are perpendicular to the same axis, they commute. Does that make W(k) grow a lot more slowly?

The *Cartier-Foata theorem* is a beautiful identity that addresses this question. It provides an exact formula for the number of length-k words in a “partially commutative monoid,” where some pairs of generators commute, and others don’t. Namely: if we construct a generating function

then

where C ranges over all *commutative cliques*, i.e. mutually commutative subsets of the generators. When there are no commutation relations, the commutative cliques are just the subsets of size 0 and 1, so you get P(t) = 1/(1-mt) where m is the number of generators, and W(k) grows like m^k. When all generators commute, every subset is a commutative clique, and you get P(t) = (1-t)^(-m), whose coefficients have polynomial growth. Julianna Tymoczko and I used the Cartier-Foata formula to give a lower bound for the diameter of unipotent subgroups of Lie groups of finite type. In our case, the number of generators grew with the rank n of the group, but the generators commute to such a great extent that the diameter was on order log |G| instead of log |G| / n.

The Rubik’s group is not quite *that* commutative. The commutative cliques are just the subsets of generators which are perpendicular to the same axis, so there are

commutative cliques of size a for all positive a. Cartier-Foata tells us that the monoid whose only relations are these commutations has

whose smallest pole, if I did this right, is at around (log 3/2)(1/2N). So the t^k coefficient, which is an upper bound for the W(k) of the Rubik’s group, is exponential on order of (2/log(3/2)N)^k. In particular, this poses no obstacle to filling up the whole group with words of length O(N^2 / log N).

Now that doesn’t mean you can actually do it! W(k) might be much smaller. But in my (limited) experience, commutativity relations really do a lot of the work. (For instance, in my paper with Tymoczko, we give an algorithmic way of writing group elements as short words that shows that the Cartier-Foata bound is correct up to a constant, just as in the Rubik’s case. Also as in the Rubik’s case, that upper bound is the hard part.) Of course it’s easy to construct examples where the Cartier-Foata estimate is way off (e.g. a free k-nilpotent group on N generators.) But if you had made me guess what the asymptotic behavior of the Rubik’s group is, I like to think I would have gotten it right.

Typo: according to Cube20.org, the amount of CPU years donated/used was 35, not 350.

Fixed, thanks. Not the only constant I was careless about in this post!

re: “as in the Rubik’s cube case, that upper bound is the hard part,” indeed the new result of 20 moves is really an upper bound that equals a previously known lower bound.

Mike Reid (another IMO/Harvard/Putnam guy) proved the correct lower bound of 20 moves back in 1995. He had worked on Rubik diameter bound problems for several years, using a combination of theory, cleverness, deep knowledge of all things cube, and computer calculation. I think it’s fair to say that the lower bound was no piece of cake, either, though certainly less computer-intensive.

Oh yeah, sorry — if you want an actual number for a single group, as in 3x3x3 Rubik, then both upper and lower bounds are really hard! I was referring to the asymptotic lower bound of n^2 / log n in the nxnxn Rubik problem.