Shared publicly  - 
 
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

and

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:

http://mathoverflow.net/questions/117006/reconstructing-the-argument-that-yields-grahams-number

#bigness
57
8
David Roberts's profile photoAlan Eggleston's profile photoAndres Caicedo's profile photoJeremy Kent's profile photo
15 comments
 
haven't you been following?  infinities can be very well defined, indeed!
 
I followed this video's discussion, and far from defining infinity, he said it was a very large number and he's an example of a very large number. It still didn't define infinity. You can't mathematically manipulate infinity as you can any true number.
 
I meant following Baez' big-numbers posts for the last... two months?  three?
 
No, I just joined the "community" recently. I see a lot of his posts but haven't seen anything on big numbers yet. He does a huge variety of posts. I'll dig through and see what else he's said.
 
+Alan Eggleston  All the posts on this issue should have the tage #bigness
 
Another mystery of mathematics history solved!
 
So should we call it the Graham–Gardner number now?
 
Thanks!  Big improvement!  They're using the term 'Graham's number' in a slightly new way.
 
In fact, what they do is provide a new upper bound for the problem that g(64) was supposed to be an upper bound for. I think it almost certainly false that g(64) < 2^^^6 = 2^^(2^^(2^^65536)). I would even suggest they change the title of their paper, because 'Graham's number' is a very specific number, not the solution to a combinatorial problem, as they define it.
 
Yes, that's what I meant: they're defining 'Graham's number' to be the solution to the problem, rather than Graham's upper bound on the solution (more precisely, the weak upper bound he told Martin Gardner about).  I agree that will confuse most people.
Add a comment...