Over the top

I was having fun browsing the 3D Printing marketplace Shapeways, and then I stumbled across this 17 \times 17 \times 17 Rubik’s Cube by Oskar van Deventer and my brain exploded a little bit.

over

Van Deventer has designed an impressive collection of cube-like puzzles which can only be made by 3D printing.

I have an older puzzle by him called Topsy Turvy mounted on the wall in my office. This one isn’t 3D printed, but it requires lasers to carefully etch the paths so that the numbered coins can stack perfectly until the very end, and then cascade to make a particular permutation. To me it is not interesting as a puzzle at all (and frankly neither is the 17^3 cube), but I like Topsy Turvy as mathematical art, and especially as a “faithful embedding” of the Mathieu group M12 in physical space.

Packing tetrahedra

Last spring I saw a great colloquium talk on packing regular tetrahedra in space by Jeffrey Lagarias. He pointed out that in some sense the problem goes back to Aristotle, who apparently claimed that they tile space. Since Aristotle was thought to be infallible, this was repeated throughout the ages until someone (maybe Minkowski?) noticed that they actually don’t.

John Conway and Sal Torquato considered various quantitative questions about packing, tiling, and covering, and in particular asked about the densest packing of tetrahedra in space. They optimized over a very special kind of periodic packing, and in the densest packing they found, the tetrahedra take up about 72% of space.

Compare this to the densest packing of spheres in space, which take up about 74%. If Conway and Torquato’s example was actually the densest packing of tetrahedra, it would be a counterexample to Ulam’s conjecture that the sphere is the worst case scenario for packing.

But a series of papers improving the bound followed, and as of early 2010 the record is held by Chen, Engel, and Glotzer with a packing fraction of 85.63%.

I want to advertise two attractive open problems related to this.

(1) Good upper bounds on tetrahedron packing.

At the time of the colloquium talk I saw several months ago, it seemed that despite a whole host of papers improving the lower bound on tetrahedron packing, there was no upper bound in the literature. Since then Gravel, Elser, and Kallus posted a paper on the arXiv which gives an upper bound. This is very cool, but the upper bound on density they give is something like 1- 2.6 \times 10^{-25}, so there is still a lot of room for improvement.

(2) Packing tetrahedra in a sphere.

As far as I know, even the following problem is open. Let’s make our lives easier by discretizing the problem and we simply ask how many tetrahedra we can pack in a sphere. Okay, let’s make it even easier: the edge length of each of the tetrahedra is the same as the radius of the sphere. Even easier: every one of the tetrahedra has to have one corner at the center of the sphere. Now how many tetrahedra can you pack in the sphere?

It is fairly clear that you can get 20 tetrahedra in the sphere, since the edge length of the icosahedron is just slightly longer than the radius of its circumscribed sphere. By comparing the volume of the regular tetrahedron to the volume of the sphere, we get a trivial upper bound of 35 tetrahedra. But by comparing surface area instead, we get an upper bound of 22 tetrahedra.

There is apparently a folklore conjecture that 20 tetrahedra is the right answer, so proving this comes down to ruling out 21 or 22. To rule out 21 seems like a nonlinear optimization problem in some 63-dimensional space.

I’d guess that this is within the realm of computation if someone made some clever reductions. Oleg Musin settled the question of the kissing number in 4-dimensional space in 2003. To rule out kissing number of 25 is essentially optimizing some function over a 75-dimensional space. This sounds a little bit daunting, but it is apparently much easier than Thomas Hales’s proof of the Kepler conjecture. (For a nice survey of this work, see this article by Pfender and Ziegler.)

God’s number is 20

After thirty years of people thinking about it, a famous open problem about the Rubik’s Cube has finally been resolved: God’s number is 20. In other words, every Rubik’s Cube, no matter how mixed up, can be solved in 20 moves or less. A nice summary of the work can be found at: http://www.cube20.org/

This enormous calculation was completed by a team of Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki, and oh yes, 35 CPU-years of idle computer time donated by Google. The preprint should be available by early September sometime.

It should be noted that for quite a while “God’s algorithm” has been known — in other words computers could quickly solve any given position with a minimal number of moves. But even with the algorithm in hand, to get God’s number by brute force would take too long, since there are 4.3 \times 10^{19} possible positions and one would have to check that they can all be solved in 20 moves or less. To get around checking this humongous number of positions required a lot of ingenuity and not only computing muscle, and the team should be warmly congratulated.

For the rest of this note, I’d like to briefly discuss a tiny bit of the mathematics involved, and an open problem or two.

First of all we should be clear about what we mean by “20 moves” — this is in the half-turn metric (HTM), where a move consists of turning any side, by either a quarter turn or a half turn. So to mathematicians, “God’s number” is the diameter of the Cayley graph for the generating set \langle L, R, U, D, F, B, L^2, R^2, U^2, D^2, F^2, B^2 \rangle. This is the metric of choice for cubers, and probably has been for thirty years. To cubers turning a side is turning a side.

Of course a half turn is just two quarter turns, and this leads us to consider the quarter-turn metric (QTM), where we only allow turning any side a quarter turn. Of course you can still give it a half turn, but now this counts as two moves. What is the diameter of the Cayley graph for the generating set \langle L, R, U, D, F, B \rangle? This is probably a more natural generating set to mathematicians, who might resist including both x and x^2 in the list of generators for a group.

It is now known (due to a calculation by Rokicki) that 29 moves are always sufficient, and he suspects that the methods used to show that 20 suffice for HTM could probably easily bring this down to 28.

On the other hand, there is essentially only one position known that requires 26 moves in the QTM, and only two in that require 25 moves. This is a very different situation than HTM, where there are roughly 300 million positions distance 20 from solved. Extensive searches by Rokicki have failed to find any more positions requiring 25 or 26 moves. So the conjecture is that the diameter of the Cayley graph with the QTM generators is 26, but it might be a while before we know that for sure. In particular the methods applied to solve HTM apparently don’t work quite as cleanly as they do for QTM.

So this is one problem: show that God’s number for quarter-turn metric is 26.

What might be nice to see, for either metric, is a description of the geometry or topology of the Rubik’s cube. One could imagine, for example, adding higher dimensional cells to extend the Cayley graph to a polyhedral complex, and studying the topology of this complex.

Finally, the following also seems to be wide open: if one makes random moves on the cube (i.e. takes a random walk on one of the Cayley graphs), what can be said about the Markov chain mixing time? A famous result of Bayer and Diaconis is that it takes “seven shuffles” to mix up a deck of 52 cards, and it would be mathematically nice to have such an answer for the Cube. (The diameter of the Cayley graph being 20 puts an upper bound on the mixing time, but the bound obtained in this naive way is much too large to be close to the truth.)

But unlike the card shuffling, which actually has some practical application, at least for (say) casinos who want to make sure their decks are randomized, this would be purely for knowledge and enjoyment. Apparently this kind of mixing time question was once an issue for speed-solving tournaments, as they would make a sequence of random moves to mix up the cube, and one might want to know how many random moves to make. But this is no longer an issue — instead of choosing a sequence of random moves, now they have the computer choose a random position uniformly from all 4.3 \times 10^{19} positions, and then use God’s algorithm to put the cube into that position.

(Special thanks to Tom Rokicki for very helpful conversations in writing this note.)

RIP Martin Gardner

Martin Gardner passed away yesterday, at 95; here is the NYTimes obituary.

I grew up with his puzzles and mathematical recreations, as I’m sure many mathematicians of my generation (and generations before) did. I am reminiscing this evening about interesting topics that Gardner introduced me to, and the following geometric gem comes to mind. The problem was apparently first proposed by Henri Lebesgue in 1914 and is still open, so it is almost 100 years old now.

Question: Find a universal cover C of least area in the plane, meaning a set having a subset congruent to every planar set of unit diameter.

If one restricts to convex C, then such a minimum is guaranteed to exist by the Blaschke selection theorem, a compactness result for sequences of bounded convex sets. A hexagon of unit width does the trick, but surprisingly, one can take off tiny pieces and still have a universal cover.

No one has ever exhibited such a minimum with proof, although there have been a few false claims of optimal solutions. I just searched and found an amusing 1992 Geometriae Dedicata article by H. C. Hansen in which the author shaves 4 \times 10^{-11} off the then reigning world record. I am not sure if anyone has improved on this result since, but this might be a fun thing to think about; indeed, Hansen suggests in the article how computers might help solve the problem, and computers have come a long way since 1992.

Gardner’s name came up in conversation just the other day. Tom Rokicki came to talk to my Rubik’s Cube class at Stanford about his work on “God’s algorithm” — Tom set a world record recently by proving that every Rubik’s Cube, no matter how scrambled, can be solved in 22 or fewer face turns. I asked him how long it would be until we have a proof of the conjectured answer of 20. He said he thought he might have 21 in the next few months, and then said that he wanted to have it down to 20 moves by Gathering for Gardner 2012. I hope that the Gatherings for Gardner continue, and it would be nice to see Tom succeed in his goal too.

I am not sure if anyone in history has ever made more people smile and shake their head about mathematical things than Martin Gardner. His writings illuminated it’s magical and mysterious qualities. Gardner was also famous as skeptic and a debunker, like many magicians before him. The NYTimes obituary reports:

He ultimately found no reason to believe in anything religious except a human desire to avoid “deep-seated despair.” So, he said, he believed in God.

Well godspeed to you Martin, and thanks for all the wonderful writings and beautiful thoughts.

V-Cube 7

This looks neat:

7 x7 x 7 Rubik’s Cube. Will report back with a review after it comes in the mail…

I haven’t bothered to check their claim of a ludicrously large number of possible positions (1.95 \times 10^{160}) yet. But I remember the packaging on the original Rubik’s Cubes advertising something like, “millions and millions of positions possible,” which is true, and might be (quantitatively speaking) one of the biggest understatements in human history. I think the right answer for the 3 \times 3 \times 3 is roughly 4 \times 10^{19}? I remember some people telling me that it was actually physically impossible to build bigger than 5 \times 5 \times 5, but I guess surprisingly it’s not.

What I’d really like to see is a nice physical implementation of the four-dimensional  cube.

Update: Got the V-Cube 5, 6, and 7 in the mail, and they are great. Very cleverly made, they turn well and make a satisfying “click” when aligned. A piece might pop out if you turn it funny, but it clicks back in pretty easily.