Friday, April 09, 2010

Insane theorem knockout

(Many millions of thanks to Pradhan, who nucleated an enormously satisfying positive feedback loop that ended up making an extraordinarily dull day memorable)

Step right up folks! On the left, we have the Jordan Curve theorem. Essentially (please correct me if I'm oversimplifying):
You build a closed fence. At any point in time, you're either inside the fence or outside it. 
The proof for this is either 60,000 lines long, or 6,500 lines long, depending on which formal language system we adopt and how many 'libraries' of theorems we invoke.

On the right, we have something that's not quite a theorem, but which we hope will appease the roaring bloodthirsty crowds nonetheless: The problem of finding a theoretical greatest lower bound to Graham's number. At one time, Graham's number was famous as the 'largest number to have ever been used in a mathematical proof'. That's a modest way of putting it:
Indeed, the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies at least one Planck volume.
It was in 1971 that Graham and Rothschild proved that the original problem to which this number is the answer is solvable in the first place, and their best estimate of the lower bound to this monster was ..... 6. They qualified their result modestly with the line, "Clearly, there is some room for improvement here."

There have been dramatic recent developments, where in 40 odd years later another chap, Geoff Exoo, "showed the solution to be at least 11, and provided experimental evidence suggesting that it is at least 12. The current best estimate of the greatest lower bound stands at 11."

Who do you think should win? :-)

Sunday, April 04, 2010


This recent Shoaib Malik telephonic love business has us quite rattled, gentle reader. There, but for the grace of, go half the world's engineers.