In 1977, Martin Gardner wrote that

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

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

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

Graham's number was an

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

For more on Graham's number, try this:

http://en.wikipedia.org/wiki/Graham%27s_number

#bigness

**"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 defineg(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))

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*ones.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

View 24 previous comments

- +John Baez Concerning the current best bounds, I was able to derive an upper bound of 2^^^(2^^n), where n is a reasonably small number - still a monstrously large number, but much lower than either of Graham's numbers. I basically just found explicit bounds for Spencer's proof of the theorem, and used Shelah's primitive recursive bound for the Hales-Jewett theorem, which was not available to Graham and Rothschild when they wrote their paper. (In fact, the non-primitive recursive bound on the Hales-Jewett theorem is the main reason why Graham's number is so big!)Mar 5, 2013
- +Royce Peng - have you written up and/or published your proof? (Unfortunately I'm too ignorant about these matters to understand
*in detail*what you're saying, but you're making it sound interesting, and other people, who know more, would be even more interested.)Mar 5, 2013 - +John Baez Unfortunately, I doubt it is publishable, since I am just finding explicit bounds for already published proofs. I suppose I will write a blog post about it. Stay tuned!Mar 5, 2013
- Great! Blog posts are a good way to get something out of results that aren't quite publishable. But if you look at all the papers that have been published, you'll see the bar is not very high, either.Mar 5, 2013
- I wasn't able to find Spencer's proof, but the proof in Shelah's paper is sufficient to get a pretty good bound. The blog post is up at:

http://googology.wikia.com/wiki/User_blog:Deedlit11/A_lower_upper_bound_for_the_Graham%27s_number_problemMar 6, 2013 - That is a nice wiki, by the way,Mar 6, 2013

Related Collections