Graham's number, named after Ronald Graham, is a large number that is an upper bound on
the solution to a certain problem in Ramsey theory.
The number gained a degree of popular attention when Martin Gardner described it in the "Mathematical
Games" section of Scientific American in November 1977, writing that Graham had recently established,
in an unpublished proof, "a bound so vast that it holds the record for the largest number
ever used in a serious mathematical proof." The 1980 Guinness Book of World Records repeated
Gardner's claim, adding to the popular interest in this number. According to physicist John
Baez, Graham invented the quantity now known as Graham's number in conversation with Gardner
himself. While Graham was trying to explain a result in Ramsey theory which he had derived
with his collaborator B. L. Rothschild, Graham found that the quantity now known as Graham's
number was easier to explain than the actual number appearing in the proof. Because the
number which Graham described to Gardner is larger than the number in the paper itself,
both are valid upper bounds for the solution to the Ramsey-theory problem studied by Graham
and Rothschild. Graham's number is much larger than other
large numbers such as a googol, googolplex, Skewes' number and Moser's number. Indeed,
like the last three of those numbers, the observable universe is far too small to contain
an ordinary digital representation of Graham's number, assuming that each digit occupies
one Planck volume. Even power towers of the form are insufficient for this purpose, although
it can be described by recursive formulas using Knuth's up-arrow notation or equivalent,
as was done by Graham. The last ten digits of Graham's number are ...2464195387.
Specific integers known to be far larger than Graham's number have since appeared in many
serious mathematical proofs.
Context
Graham's number is connected to the following problem in Ramsey theory:
Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete
graph on 2n vertices. Colour each of the edges of this graph either red or blue. What is
the smallest value of n for which every such colouring contains at least one single-coloured
complete subgraph on four coplanar vertices?
In 1971, Graham and Rothschild proved that this problem has a solution N*, giving as
a bound 6 ≤ N* ≤ N, with N being a large but explicitly defined number , where in Knuth's
up-arrow notation; the number is between 4 → 2 → 8 → 2 and 2 → 3 → 9 → 2
in Conway chained arrow notation. This was reduced in 2013 via upper bounds on the Hales–Jewett
number to . The lower bound of 6 was later improved to 11 by Geoff Exoo in 2003, and
to 13 by Jerome Barkley in 2008. Thus, the best known bounds for N* are 13 ≤ N* ≤ N'.
Graham's number, G, is much larger than N: , where . This weaker upper bound for the
problem, attributed to an unpublished work of Graham, was eventually published and named
by Martin Gardner in Scientific American in November 1977.
Definition Using Knuth's up-arrow notation, Graham's
number G is
where the number of arrows in each layer, starting at the top layer, is specified by
the value of the next layer below it; that is,
and where a superscript on an up-arrow indicates how many arrows there are. In other words,
G is calculated in 64 steps: the first step is to calculate g1 with four up-arrows between
3s; the second step is to calculate g2 with g1 up-arrows between 3s; the third step is
to calculate g3 with g2 up-arrows between 3s; and so on, until finally calculating G
= g64 with g63 up-arrows between 3s. Equivalently,
and the superscript on f indicates an iteration of the function, e.g., f 4(n) = f(f(f(f(n)))).
Expressed in terms of the family of hyperoperations , the function f is the particular sequence
, which is a version of the rapidly growing Ackermann function A(n,n). The function f
can also be expressed in Conway chained arrow notation as , and this notation also provides
the following bounds on G:
Magnitude To convey the difficulty of appreciating the
enormous size of Graham's number, it may be helpful to express—in terms of exponentiation
alone—just the first term of the rapidly growing 64-term sequence. First, in terms
of tetration alone:
where the number of 3s in the expression on the right is
Now each tetration operation reduces to a "tower" of exponentiations according to the
definition
Thus,
becomes, solely in terms of repeated "exponentiation towers",
and where the number of 3s in each tower, starting from the leftmost tower, is specified
by the value of the next tower to the right. In other words, g1 is computed by first calculating
the number of towers, n = 3↑3↑3↑...↑3, and then computing the nth tower in the following
sequence:
1st tower: 3
2nd tower: 3↑3↑3 = 7625597484987
3rd tower: 3↑3↑3↑3↑...↑3 = …
⋮
g1 = nth tower: 3↑3↑3↑3↑3↑3↑3↑...↑3
where the number of 3s in each successive tower is given by the tower just before it.
Note that the result of calculating the third tower is the value of n, the number of towers
for g1. The magnitude of this first term, g1, is so
large that it is practically incomprehensible, even though the above display is relatively
easy to comprehend. Even n, the mere number of towers in this formula for g1, is far greater
than the number of Planck volumes into which one can imagine subdividing the observable
universe. And after this first term, still another 63 terms remain in the rapidly growing
g sequence before Graham's number G = g64 is reached.
Rightmost decimal digits Graham's number is a "power tower" of the
form 3↑↑n, so its rightmost decimal digits must satisfy certain properties common to
all such towers. One of these properties is that all such towers of height greater than
d, have the same sequence of d rightmost decimal digits. This is a special case of a more general
property: The d rightmost decimal digits of all such towers of height greater than d+2,
are independent of the topmost "3" in the tower; i.e., the topmost "3" can be changed
to any other nonnegative integer without affecting the d rightmost digits.
The following table illustrates, for a few values of d, how this happens. For a given
height of tower and number of digits d, the full range of d-digit numbers does not occur;
instead, a certain smaller subset of values repeats itself in a cycle. The length of the
cycle and some of the values are shown in each cell of this table:
The particular rightmost d digits that are ultimately shared by all sufficiently tall
towers of 3s are in bold text, and can be seen developing as the tower height increases.
For any fixed number of digits d, the number of values possible for 33↑…3↑x mod 10d,
as x ranges over all nonnegative integers, is seen to decrease steadily as the height
increases, until eventually reducing the "possibility set" to a single number when the height exceeds
d+2. A simple algorithm for computing these digits
may be described as follows: let x = 3, then iterate, d times, the assignment x = 3x mod
10d. Except for omitting any leading 0s, the final value assigned to x is then composed
of the d rightmost decimal digits of 3↑↑n, for all n > d.
Let k be the numerousness of these stable digits, which satisfy the congruence relation
G(mod 10k)≡[GG](mod 10k). k=t-1, where G(t):=3↑↑t. It follows that,
g63 ≪ k ≪ g64. The algorithm above produces the following
500 rightmost decimal digits of Graham's number:
…02425950695064738395657479136519351798334535362521 43003540126026771622672160419810652263169355188780
38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080
25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887
17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508
94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387
See also Hyperoperation
Ackermann function Kruskal's tree theorem
Ramsey theorem Notes
References Graham, R. L.; Rothschild, B. L.. "Ramsey's
Theorem for n-Parameter Sets". Transactions of the American Mathematical Society 159:
257–292. doi:10.2307/1996010. JSTOR 1996010. The explicit formula for N appears on p. 290.
This is
not the "Graham's number" G published by Martin Gardner.
Graham, R. L.; Rothschild, B. L.. "Ramsey Theory". In Rota, G-C. Studies in Combinatorics
17. Mathematical Association of America. pp. 80–99. ISBN 0-88385-117-2. On p. 90, in stating
"the best available estimate" for the solution, the explicit formula for N is repeated from
the 1971 paper. Gardner, Martin. "Mathematical Games". Scientific
American 237: 18–28. doi:10.1038/scientificamerican1177-18. ; reprinted in Gardner, cited below.
Gardner, Martin. Penrose Tiles to Trapdoor Ciphers. Washington, D.C.: Mathematical Association
of America. ISBN 0-88385-521-6. Gardner, Martin. The Colossal Book of Mathematics:
Classic Puzzles, Paradoxes, and Problems. New York, NY: Norton. ISBN 0-393-02023-1.
External links "A Ramsey Problem on Hypercubes" by Geoff
Exoo Mathworld article on Graham's number
How to calculate Graham's number Some Ramsey results for the n-cube prepublication
mentions Graham's number Padilla, Tony; Parker, Matt. "Graham's Number".
Numberphile. Brady Haran. Ron Graham. "What is Graham's Number?". Numberphile.
Brady Haran. Ron Graham. "How Big is Graham's Number?".
Numberphile. Brady Haran.