Graham's Number

Graham's number is a tremendously large finite number that is a proven upper bound to the solution of a certain problem in Ramsey theory. It is named after mathematician Ronald Graham who used the number as a simplified explanation of the upper bounds of the problem he was working on in conversations with popular science writer Martin Gardner. The number was published in the 1980 Guinness Book of World Records, which added to the popular interest in the number. Graham's number is much larger than any other number you can imagine. It is so large that 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 which equals to about \(4.2217\times 10^{-105}\text{ m}^{3}\). Even power towers of the form \({\displaystyle \scriptstyle a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}}\) are insufficient for this purpose, although it can be described by recursive formulas using Knuth's up-arrow notation. Though too large to be computed in full, many of the last digits of Graham's number can be derived through simple algorithms.

The last 400 digits are these:

\[38814483140652526168785095552646051071172000997092 91249544378887496062882911725063001303622934916080 25459461494578871427832350829242102091825896753560 43086993801689249889268099510169055919951195027887 17830837018340236474548882222161573228010132974509 27344594504343300901096928025352751833289884461508 94042482650181938515625357963996189939679054966380 03222348723967018485186439059104575627262464195387.\]

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. Color each of the edges of this graph either red or blue. What is the smallest value of \(n\) for which every such coloring contains at least one single-colored complete subgraph on four coplanar vertices?

In 1971, Graham and Rothschild proved that this problem has a solution \(N^*,\) giving as a bound \(6 \le N^* \le N,\) with \(N\) being a large but explicitly defined number \[{F^{7}(12)\;=\;F\big(F(F(F(F(F(F(12))))))\big)},\] where \({ F(n)\;=\;2\uparrow ^{n}3}\) 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 2014 via upper bounds on the Hales-Jewett number to \({ N'\;=\;2\;\uparrow \uparrow \uparrow \;6}.\) 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:\) \({f^{64}(4)},\) where \({ f(n)\;=\;3\uparrow ^{n}3}.\) 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. 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."

Knuth's up-arrow notation is a way of describing very large numbers. It's defined recursively, with the base case of repeated multiplication. So, for example, \(3 \uparrow 4\) means \( 3 \times (3 \times (3 \times 3))\). Therefore, the first level of up-arrow notation is just exponentiation, and we can write \(3 \uparrow 4\) as \(3^4.\)

However, each additional up-arrow requires repeated application of the previous level of up-arrows. Thus, \(3 \uparrow \uparrow 4\) means \( 3 \uparrow (3 \uparrow (3 \uparrow 3))\) or \(3^{3^{3^3}}.\) These numbers grow very, very quickly; \(3 \uparrow \uparrow 4\) is trillions of digits long.

Using Knuth's up-arrow notation, Graham's number \(G\) is

where the number of arrows in each subsequent layer is specified by the value of the next layer below it; that is, \[{\displaystyle G=g_{64} ,{\text{ where }}g_{1}=3\uparrow \uparrow \uparrow \uparrow 3,\ g_{n}=3\uparrow ^{g_{n-1}}3,}\] 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 \(g_1\) with four up-arrows between 3s; the second step is to calculate \(g_2\) with \(g_3\) up-arrows between 3s; the third step is to calculate \(g_3\) with \(g_2\) up-arrows between 3s, and so on, until finally calculating G = \(g_{64}\) with \(g_{63}\) up-arrows between 3s.

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 \(g_1\) of the rapidly growing 64-term sequence. First, in terms of tetration ( ↑↑ \({\displaystyle \scriptstyle \uparrow \uparrow }\) ) alone, \[{\displaystyle g_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow \big(3\uparrow \uparrow (3\uparrow \uparrow \ \dots \ (3\uparrow \uparrow 3)\dots )\big)},\] where the number of 3s in the expression on the right is \({\displaystyle 3\uparrow \uparrow \uparrow 3\ =\ 3\uparrow \uparrow (3\uparrow \uparrow 3)}.\)

Now each tetration ( ↑↑ \({\displaystyle \scriptstyle \uparrow \uparrow }\) ) operation reduces to a power tower ( ↑ \({\displaystyle \scriptstyle \uparrow }\) ) according to the definition \[{\displaystyle 3\uparrow \uparrow X\ =\ 3\uparrow \big(3\uparrow (3\uparrow \dots (3\uparrow 3)\dots )\big)\ =\ 3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}},\quad {\text{where there are X 3s}}.}\] Thus, \(g_1 = 3 ↑↑ \big( 3 ↑↑ ( 3 ↑↑   …   ( 3 ↑↑ 3 ) … ) \big),\) where the number of 3s is \( 3 \uparrow \uparrow ( 3 \uparrow \uparrow 3), \) becomes, solely in terms of repeated "exponentiation towers," \[{\displaystyle g_{1}=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3, \quad {\text{where the number of towers is}}\quad \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3},\] 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. Anyway other specific integers known to be far larger than Graham's number have since appeared in many serious mathematical proofs, for example, in connection with Harvey Friedman's various finite forms of Kruskal's theorem.