A while back I told you about Graham's number, a whopping big number that Martin Gardner said was the biggest integer ever used in a serious mathematical proof.  But there's a little mystery concerning this number.  Yesterday I talked to Ronald Graham and solved this mystery.   He also recommended the video here.

The mystery is this.  In 1977, Martin Gardner wrote that "in an unpublished proof, Graham has recently established … a bound so vast that it holds the record for the largest number ever used in a serious mathematical proof." 

Graham was working on this puzzle:  Consider an n-dimensional hypercube.   Connect each pair of vertices with an edge.   Color each of the edges either red or blue. What is the smallest value of n for which every such coloring contains 4 vertices lying in a plane that are all connected to each other with edges of the same color?

According to Gardner, Graham proved that an upper bound on this n was Graham’s number, namely g(64), where we define

g(1) = 3↑↑↑↑3


g(k+1) = 3 ↑↑↑↑↑↑↑↑↑↑↑↑g(k) of these↑↑↑↑↑↑↑↑↑↑↑↑ 3

Remember, Knuth’s up-arrow notation is a way of talking about exponentiation, tetration, and so on:

2↑4 = 2 × (2 × (2 × 2))
2↑↑4 = 2 ↑ (2 ↑ (2 ↑ 2))
2↑↑↑4 = 2 ↑↑  (2 ↑↑ (2 ↑↑ 2))

However, when Graham published a paper on this puzzle, the number that shows up is  not Graham's number, but something much smaller... though still insanely large:

• Ronald Graham and B. Rothschild, Ramsey's Theorem for n-Parameter Sets, Transactions of the American Mathematical Society 159 (1971), 257–292.   http://www.cs.umd.edu/~gasarch/vdw/Graham-Rothchild.pdf

So the puzzle is: where did Graham's number really come from?

According to Wikipedia, it's "attributed to an unpublished work of Graham".   On Mathoverflow, someone asked:

"Can someone reconstruct a simple argument for the Euclidean Ramsey problem in question that naturally yields Graham's number as an upper bound?"

So I asked Graham.  And the answer was interesting.  He said he made up Graham's number when talking to Martin Gardner!  Why?   Because it was simpler to explain than his actual upper bound - and bigger, so it's still an upper bound!

So, I should change the Wikipedia entry and answer the Mathoverflow question.

For more see:


Shared publiclyView activity