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."
The video here gives a fun explanation. But it seems nobody in the video can quite remember the problem where Graham's number shows up. It's a bit tricky:
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?
For a while the best 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))
etc. But Graham used a devilish trick to let the number of up-arrows grow very rapidly. Each number in his sequence g(k) is the number of up-arrows in the next one! And so, his number is vastly bigger than any numbers I've mentioned so far in my tale... except, of course, for all the infinite
Graham's number was an upper bound
on the answer to a problem. One way to get a huge upper bound is to be stupid. For example, I could say "a million is an upper bound on the smallest prime, because a million is not prime, so it must have a prime factor smaller than this."
Graham is certainly not stupid, and he improved his bound considerably by the time he published a paper on this stuff. But it's worth noting that the logician Harvey Friedman has found math problems where the lower
bound on the right answer is much bigger than Graham's number! We'll talk about those later.
For more on Graham's number, try this:http://en.wikipedia.org/wiki/Graham%27s_number#bigness