Reconstructing the argument that yields Graham's number - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T08:21:03Z http://mathoverflow.net/feeds/question/117006 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/117006/reconstructing-the-argument-that-yields-grahams-number Reconstructing the argument that yields Graham's number Timothy Chow 2012-12-22T03:43:26Z 2013-01-11T18:06:13Z <p><a href="http://en.wikipedia.org/wiki/Graham%27s_number" rel="nofollow">Graham's number</a> 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 <i>better</i> 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.</p> <p>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:</p> <blockquote> <p>Can someone reconstruct a simple argument for the Euclidean Ramsey problem in question that naturally yields Graham's number as an upper bound?</p> </blockquote> <p>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.</p> http://mathoverflow.net/questions/117006/reconstructing-the-argument-that-yields-grahams-number/118650#118650 Answer by John Baez for Reconstructing the argument that yields Graham's number John Baez 2013-01-11T17:26:00Z 2013-01-11T18:06:13Z <p>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! </p> <p>So, apparently the comment on <a href="http://en.wikipedia.org/wiki/Graham%27s_number" rel="nofollow">Wikipedia</a>:</p> <blockquote> <p>This weaker upper bound for the problem, attributed to an unpublished work of Graham [....]</p> </blockquote> <p>is a bit misleading, though still technically true. I'll try to fix it in a while.</p> <p>Nice question!</p>