An Interesting Prime Number Fact, Rubik’s Cube and the Gömböc

In the summer of 2010 I traveled to Hungary for the 25th anniversary reunion of the Budapest Semesters in Mathematics program, and had the pleasure of seeing the inauguration of another study abroad program for computer science, the Aquincum Institute of Technology.

The interesting part of the ceremony was a series of mathematics talks to celebrate the genius of Hungarian mathematics and technology. There were also talks by Balázs Bús, the mayor of Óbuda, and by János Kocsány, the CEO of Graphisoft Park.

The Graphisoft Park Rubik's Cube
The Graphisoft Park Rubik's Cube

László Babai talked about Mathematical Generalizations of Rubik’s Cube, and mentioned the following.

The diameter of the Rubik’s Cube graph is at least 20, but probably no more than 21 (Richard Korf, UCLA, 1997), and definitely no more than 26 (Gene Cooperman, Dan Kunkle, Northeastern, 2007).

It was very interesting that just a month later, in July, 2010, the diameter was confirmed as 20. A team used 35 years of CPU time, donated by Google, to complete the computation. Even more interesting for me was to learn that the lower bound of 20 had been established in 1995 by Mike Reid, who identified the “superflip” position that required 20 moves to solve. Here’s an interesting website that documents progress on this problem: God’s Number is 20.

I had met Mike in person about 25 years ago, when I attended the Hampshire College Summer Studies in Mathematics. Now that I am involved with the New York Math Circle, I’ve had the pleasure of meeting Mike’s old math teachers, who have wonderful stories to tell.

Babai had brought up the diameter of the Rubik’s Cube graph because his talk was really about the connection between the size of a group at the diameter of its Cayley graph. For the Rubik’s cube, the group has about 34 quintillion elements (The exact number is 43,252,003,274,489,856,000. Remember: thousand, million, billion, trillion, quadrillion, quintillion, sextillion, septillion, …), but its diameter is just 20, which is on the order of the logarithm of the size of the group.

Babai mentioned a recent result of Harald Helfgott and Akos Seres, On the diameter of permutation groups, which gives a “quasipolynomial upper bound” for the diameter.

One beautiful formula that Babai presented was:

$latex \prod_{p \leq x} p \approx e^x$.

This seems related to the prime number theorem, that $latex \pi(x) \approx \frac{x}{\ln{x}}$, where $latex \pi(x)$ denotes how many primes are less than x. I leave it to the readers to find the connection.

Another great talk was by Gábor Domokos, The Story of Gömböc. The gömböc is a solid object with just one stable point of equilibrium (and also one unstable point). If you place the gömböc on a flat surface, it rocks back and forth, and eventually stabilizes in the same position each time.

Amazing invention–I want one!



, , ,