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? :-)

1 comment:

Pranesh Srinivasan said...

Another "obvious" but very controversial theorem is the Axiom of Choice (http://en.wikipedia.org/wiki/Axiom_of_choice):

Informally, it just says that given a collection of non-empty sets, it is possible to make a selection of exactly one obj...ect from each set.

This is obvious for finite sets, but is very non-trivial for infinite sets. Assuming it is equivalent to:

a) Every set of vectors has a basis.

b) The cross product of a set of non empty sets is a non empty set.

(more on the wiki page).

But it also leads to things like the Banach Tarski paradox:

"It is possible to decompose ("carve up") the 3-dimensional solid unit ball into finitely many pieces and, using only rotations and translations, reassemble the pieces into two solid balls each with the same volume as the original"

As Bertrand Russel once put it:

"To choose one sock from each of infinitely many pairs of socks requires the Axiom of Choice, but for shoes the Axiom is not needed."