30
$\begingroup$

Graham's number achieved a kind of cult status, thanks to Martin Gardner, as the largest finite number appearing in a mathematical proof. (It may no longer hold that record, but that is not my concern here.) I was surprised to learn relatively recently that it is not actually the best known bound for that particular Euclidean Ramsey problem, and that the original paper by Graham and Rothschild, which predates "Graham's number," explicitly derives a better bound. I'm left to assume that Graham later found a simpler argument that gave a weaker bound, that we now know as Graham's number.

Some time ago, before I realized the above facts, I asked Graham about his "Graham's number" proof. As I recall the conversation, he no longer had the argument at his fingertips and did not seem too interested in trying to reconstruct it. This brings me to my question:

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

This would not normally be that interesting a question except that Graham's number still circulates in recreational mathematics circles, so it's a bit embarrassing if nobody knows how to "derive" it.

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ Though irrelevant to Tim's question, Graham's number is small potatoes compared to some of the numbers cooked up by Harvey Friedman, e.g., his paper Long finite sequences, JCT(A) 95 (2001), 102-144. $\endgroup$
    – Richard Stanley
    Commented Dec 22, 2012 at 4:14
  • 22
    $\begingroup$ I once unwisely told a taxi driver in Glasgow that I was a mathematician. He got excited and said, "So what's the biggest number then?" I ummed and ahhed, trying to think up a good diplomatic answer, when he interrupted and said "It's Graham's number, isn't it?" Now that's cult status. $\endgroup$
    – Tom Leinster
    Commented Dec 22, 2012 at 4:22
  • 17
    $\begingroup$ My daughter (who is 8) and I were discussing large numbers some time back, and I said to her that mathematicians sometimes talk about this indescribably large number called Graham's number, that you couldn't write down in ordinary (decimal) notation even if you filled the universe with numbers. This has come back to haunt me with some frequency. I think she thinks it's effectively infinite. Perhaps I have a budding ultrafinitist on my hands. $\endgroup$
    – Todd Trimble
    Commented Dec 22, 2012 at 13:20
  • 1
    $\begingroup$ A related answer on math.SE for a general audience, by user @MJD: Graham's Number: why so big? $\endgroup$
    – shreevatsa
    Commented Feb 8, 2018 at 17:35

1 Answer 1

Reset to default
24
$\begingroup$

I talked to Ronald Graham last night at the Joint Mathematics Meeting in San Diego and asked him the question here. He said he'd made up Graham's number when talking to Martin Gardner because 1) it was simpler to explain than his actual upper bound, the one that appears in his paper with Rothschild, and 2) it's bigger, so it's still an upper bound!

So, apparently the comment on Wikipedia:

This weaker upper bound for the problem, attributed to an unpublished work of Graham [....]

is a bit misleading, though still technically true. I'll try to fix it in a while.

Nice question!

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ John's Google+ post on Graham's number: plus.google.com/117663015413546257905/posts/KJTgfjkTZCQ $\endgroup$
    – Andrés E. Caicedo
    Commented Jan 11, 2013 at 18:08
  • 3
    $\begingroup$ Interesting! Thanks. I just took another look at Graham and Rothschild's paper and there might still be an interesting question here. Namely, given that you want to write down a number using Knuth's arrow notation that is bigger than the upper bound in the paper, would you be fairly naturally led to write down Graham's number? It's not immediately obvious to me. $\endgroup$
    – Timothy Chow
    Commented Jan 11, 2013 at 19:55
  • 4
    $\begingroup$ So we should stop referring to it as a number that appears naturally in a proof. $\endgroup$
    – Brendan McKay
    Commented Jan 11, 2013 at 23:15
  • 8
    $\begingroup$ @TimothyChow: The upper bound given in the paper is $f^7(12)$ where $f(n) = 2 \mathbin{\uparrow}^{n} 3$. That seems to me about exactly as easy to specify as Graham's number $f^{64}(4)$ where $f(n) = 3 \mathbin{\uparrow}^{n} 3$, so I don't know why the latter ever came up. Perhaps Graham actually tried to outline to Gardner the argument for the upper bound, and found it simpler with the weaker bound. $\endgroup$
    – Sridhar Ramesh
    Commented Jul 23, 2014 at 1:30
  • 3
    $\begingroup$ It's not known that $f^{63}(4)$ is not large enough. Indeed, for all we know, 13 [that is, the number 13, in itself] may be large enough (and for all Graham knew at the time, 6 may be large enough). But, at any rate, he was able to show that $f^{64}(4)$ was definitely large enough. I don't know the argument, but presumably, this was some random thing he could relatively easily show large enough, by an argument that did not immediately apply just as well to $f^{63}(4)$. $\endgroup$
    – Sridhar Ramesh
    Commented Jun 30, 2017 at 17:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .