Graham's number

Graham's number

, named after Ronald Graham, is a large number often described as the largest finite number that has ever been seriously used in a mathematical proof. Guinness World Records even listed Graham's number as the World Champion largest number. Graham's number is much larger than other well known large numbers such as a googol and a googolplex, and even larger than Skewes' number and Moser's number, other well-known large numbers. Indeed, there is no concise way to write Graham's number, or any reasonable approximation, using conventional mathematical operators. Even power towers (of the form a ^{ b ^{ c ^{ cdot ^{ cdot ^{ cdot}}}}}) are useless for this purpose. It can be most easily notated by recursive means using Knuth's up-arrow notation or the Hyper operator.



Graham's number is connected to the following problem in the branch of mathematics known as Ramsey theory:

    Consider an n-dimensional hypercube, and connect each pair of vertices to obtain a complete graph on 2n vertices. Then colour each of the edges of this graph using only the colours red and black. What is the smallest value of n for which every possible such colouring must necessarily contain a single-coloured complete sub-graph with 4 vertices which lie in a plane?

Although the solution to this problem is not yet known, Graham's number is the smallest known upper bound for it. This bound was found by Graham and B. L. Rothschild (see (GR), corollary 12). They also provided the lower bound 6, adding the qualifying understatement: "Clearly, there is some room for improvement here."


In Penrose Tiles to Trapdoor Ciphers, Martin Gardner wrote, "Ramsey-theory experts believe the actual Ramsey number for this problem is probably 6, making Graham's number perhaps the worst smallest-upper-bound ever discovered." More recently Geoff Exoo of Indiana State University has shown (in 2003) that it must be at least 11 and provided evidence that it is larger.

Definition of Graham's number

Using Knuth's up-arrow notation, Graham's number G is defined as

Equivalently,

G = g₆₄ where ,

or

G = f⁶⁴(4) where f(n) = hyper(3,n + 2,3) and hyper() is the hyper operator.

Graham's number G itself cannot succinctly be expressed in Conway chained arrow notation, but , see bounds on Graham's number in terms of Conway chained arrow notation.

Posted in: