**Graham's number** \(G_{64}\) is a famous large number, defined by Ronald Graham.^{[1]}^{[2]}

Using Up-arrow notation, it is defined as the 64th term of the following sequence:

\(\begin{array}{l} G_0=4 \\ G_1=3\uparrow\uparrow\uparrow\uparrow3 \\ \textrm{For}\;0\le k<64\textrm{,}\;G_{k+1}=3\underbrace{\uparrow\uparrow\cdots\uparrow\uparrow}_{G_k}3 \\ \text{Graham's number}=G_{64}\end{array}\)

\(g_{64} = \underbrace{3 \uparrow^{3 \uparrow^{3 \uparrow^{\cdot^{\cdot^{\cdot^{3 \uparrow \uparrow \uparrow \uparrow 3}\cdot}\cdot}\cdot}3}3}3}_{64\text{ layers}} = \left. \begin{matrix}3 \underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}_{\displaystyle 3 \underbrace{\uparrow \uparrow \cdots \cdots \cdots \uparrow}_{\displaystyle \underbrace{\qquad \vdots \qquad}_{\displaystyle 3 \underbrace{\uparrow \uparrow \cdots \uparrow}_{\displaystyle 3 \uparrow \uparrow \uparrow \uparrow 3}3}}3}3 \end{matrix}\right \} 64 \text{ layers}\)

(\(G_n\) is sometimes written \(G(n)\), \(g_n\) or \(g(n)\))

Graham's number is commonly celebrated as the largest number ever used in a serious mathematical proof, although much larger numbers have since claimed this title (such as TREE(3) and SCG(13)). The smallest Bowersism exceeding Graham's number is corporal, and the smallest Saibianism exceeding Graham's number is graatagold.

## History[]

Graham's number arose out of the following unsolved problem in Ramsey theory:^{[3]}

Let

N*be the smallest dimensionnof a hypercube such that if the lines joining all pairs of corners are two-colored for anyn≥N*, a complete graph K_{4}of one color with coplanar vertices will be forced. FindN*.

To understand what this problem asks, first consider a hypercube of any number of dimensions (1 dimension would be a line, 2 would be a square, 3 would be a cube, 4 would be a tesseract (4-dimensional cube), etc.), and call that number of dimensions N. Then, imagine connecting all possible vertex pairs with lines, and coloring each of those red or blue - one such way you can color all of the vertex pairs of the 3-dimensional cube is shown to the right. What is the smallest number of dimensions N such that all possible colorings would have a monochromatic complete graph of four coplanar vertices (that is a set of four points that are connected in all possible ways, with all lines being the same color)?

Graham published a paper in 1971 proving that the answer exists, providing the upper bound \(F^{7}(12)\), where \(F(n) = 2 \uparrow^{n} 3\) in Arrow notation.^{[4]} Sbiis Saibian calls this number "Little Graham". Martin Gardner, when discovering the number's size, found it difficult to explain, and he devised a larger, easier-to-explain number which Graham proved in an unpublished 1977 paper. Martin Gardner wrote about the number in *Scientific American* and it even made it to *Guiness World Records* in 1980 as the largest number used in a mathematical proof, although a few years later the title was removed from Guinness World Records.

In 2013, the upper bound was further reduced to *N'* = 2↑↑2↑↑(3+2↑↑8) using the Hales–Jewett theorem ^{[5]}, and to N" = (2↑↑5138) x ((2↑↑5140)↑↑(2 x (2↑↑5137))) << 2↑↑↑5 in 2019 ^{[6]}. As of 2014, the best known *lower* bound for *N** is 13, shown by Jerome Barkley in 2008.^{[7]}

## Comparison[]

Since g_{0} is 4 and not 3, Graham's number cannot be expressed efficiently in Chained arrow notation \(g_{64} \approx 3 \rightarrow 3 \rightarrow 64 \rightarrow 2\) or BEAF \(\{3,65,1,2\} < g_{64} < \{3, 66, 1, 2\}\). Using Jonathan Bowers' base-3 G functions it is exactly G^{64}4. It can be also exactly expressed in the Graham Array Notation as \([3,3,4,64]\).

Tim Chow proved that Graham's number is much larger than the Moser.^{[8]} The proof hinges on the fact that, using Steinhaus-Moser Notation, *n* in a (*k* + 2)-gon is less than \(n\underbrace{\uparrow\uparrow\ldots\uparrow\uparrow}_{2k-1}n\). He sent the proof to Susan Stepney on July 7, 1998.^{[9]} Coincidentally, Stepney was sent a similar proof by Todd Cesere several days later.

Japanese googologist Fish proved that Graham's number is less than \(f_{\omega+1}(64)\) in the Fast-growing hierarchy with respect to Wainer hierarchy.^{[10]}

### Comparison with busy beaver function[]

- 2010-09-19: It was proven that Graham's number is much less than \(\Sigma(64)\).
^{[11]} - 2016-07-24: According to Wythagoras, he found a Turing machine that proves \(\Sigma(18) > G\) by improving Deedlit11's machine, and wrote a brief sketch of the proof instead of a rigorous proof.
^{[12]} - In this community, it was believed that a better upper bound \(\Sigma(17)\) was proven by someone
^{[13]}until 2021-07-09, but at least there was no cited source about the result. Therefore the reader should be careful that he or she might have caught a wrong information. - 2021-03-18: Daniel Nagaj
^{[14]}^{[15]}claims that his 16-state Turing machine implements multiexpansion and beats Graham's number,^{[16]}which implies \(\Sigma(16) > G\). 2022-07-11: S. Ligocki confirmed that Daniel Nagaj's 16-state Turing machine beaten Graham's number^{[17]}

## Approximations in other notations[]

Notation | Approximation |
---|---|

Chained arrow notation | \(3 \rightarrow 3\rightarrow 64\rightarrow 2\) |

BEAF | \(\{3,65,1,2\}\) |

Graham Array Notation | \([3,3,4,64]\) (exact) |

Extended Hyper-E Notation | \(\textrm E[3]3\#\#4\#64\) |

Strong array notation | \(s(3,64,2,2)\) |

Ampersand Notation | \(64[\&1]\) |

Fast-growing hierarchy | \(f_{\omega+1}(64)\) |

Hardy hierarchy | \(H_{\omega^{\omega+1}}(64)\) or \(H_{\omega^\omega 64}(4)\) |

Slow-growing hierarchy | \(g_{\Gamma_0}(65)\) |

### Calculating last digits[]

The final digits of Graham's number are easily computed by a simple application of algorithms for modular exponentiation. Here is a simple algorithm to obtain the last \(x\) digits \(N(x)\) of Graham's number for small values of x:

- \(N(0) = 3\)
- \(N(x) = 3^{N(x-1)} \text{ mod } 10^x\)

However, this formula is **wrong** if theoretically applied to extremely large values of x, although it was believed to be correct in and was spread from this community up to December in 2019. This error can be easily fixed by considering that Graham's number, \(G_{64}\), is just an integer tetration with base \(3\) and a very large hyperexponent, \(b\) (i.e., \(G_{64}:={^{b}3}\)).

Then, in 2020, Marco Ripà proven that, in radix-\(10\) (the well-known decimal numeral system), the congruence speed of \(3\) is equal to zero if and only if its (strictly positive integer) hyperexponent is \(0\) and that it is equal to \(1\) otherwise (see Lemma 1 of https://nntdm.net/volume-26-2020/number-3/245-260/, and also Equation (16) of https://nntdm.net/volume-28-2022/number-3/441-457/ for further details).

Consequently, \(G_{64}\) has the same \(b-1\) rightmost digits of \({^{c}3}\) for all \(c=1,2,\ldots,b-2,b-1\), but this is no longer true by considering the \(b\)-th rightmost digit of \(G_{64}\), which is not equal to the \(b\)-th rightmost digit of \({^{b+1}3}, {^{b+2}3}, {^{b+3}3}, \ldots \).

Then, we have that \(G_{63} << b-1 << G_{64} \) since \( b-1 = slog_3(G_{64})-1 \), where \( slog \) indicates the super-logarithm. Therefore, we can finally state that \(G_{64} \equiv ^{slog_3(G_{64})+c}3 \pmod {{10}^{slog_3(G_{64})-1}} \wedge G_{64} \not\equiv ^{slog_3(G_{64})+c}3 \pmod {{10}^{slog_3(G_{64})}}\) holds for all \(c \in \mathbb{Z}^+\).

In fact, for arbitrarily many digits, the method actually returns the last digits of the \(10\)-adic fixed point of \(x \mapsto 3^x\).

Therefore, the above-mentioned "wrong algorithm" can only return the last \(b-1\) digits of Graham's number. See the main article on modular exponentiation. However, the value of \(b\) is extremely large (in fact, on this scale, it is barely smaller than Graham's number itself), so the method works for all practical values of \(x\), which is likely why the method was assumed to work for any positive integer \(x\).

The last 20 digits of Graham's number are ...04,575,627,262,464,195,387.

While it is not known how to calculate the leading digit of Graham's number in base 10 in the current community (and, in all likelihood, never will be), the leading digit must be 1 in base 2 (because all positive integers except 0 have this property), 1 in base 3 (because it is a power of 3) , and 3 in base 9 (because it is an odd-numbered power of 3). It is not known how to calculate the leading digit of Graham's number in any other base in the current community, unless if it is a power of 3 (such as 27), or at least comparable to Graham's number (such as Graham's number - 64).

## Video[]

Source: Graham's Number - Numberphile

## See also[]

- Moser
- Little Graham
- Folkman's number
- Expansion
- Grahal, a number equal to \(g_1\)
- Mouffles Monster

## Sources[]

- ↑ Conway and Guy. The Book of Numbers. Copernicus. 1995. ISBN 978-0387979939 p.61
- ↑ Graham's Number
- ↑ Weisstein, Eric W. "Graham's Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GrahamsNumber.html
- ↑ Graham & Rothchild 1971 paper
- ↑ http://arxiv.org/abs/1304.6910
- ↑ http://arxiv.org/abs/1905.05617
- ↑ http://arxiv.org/abs/0811.1055
- ↑ Proof that
*G*>>*M*. (This website uses*n*[*m*] =*n*inside an*m*-gon for Steinhaus-Moser Notation.) - ↑ Stepney, Susan. Moser's polygon notation. Retrieved 2013-03-17.
- ↑ Fish. Upper bound of Graham's number in fast-growing hierarchy, July 11, 2021.
- ↑ Proof that BB(64) >> G
- ↑ User blog:Wythagoras/The nineteenth Busy Beaver number is greater than Graham's Number!
- ↑ a difference page of this article
- ↑ Daniel Nagaj's website
- ↑ Record of personal contact to Daniel Nagaj
- ↑ Daniel Nagaj, Multiexpandal growth Turing machine with 16 states, 2021-03-18. (Saved machine on Gist)
- ↑ BB(16) > Graham's Number

## External links[]

- Sbiis Saibian's article on Graham's number
- Mitsuki1729, グラハム数 scratch巨大数選手権コンテスト, scratch. (scratch code for Graham's number)

TREE sequence TREE(3) · Greedy clique sequence · Friedman's finite trees · Subcubic graph number SCG(13) · **Graham's number** G(64)

**By Aeton:** Okojo numbers · N-growing hierarchy**By 新井 (Arai):** Arai's psi function**By aster:** White-aster notation · White-aster**By バシク (BashicuHyudora):** Primitive sequence number · Pair sequence number · Bashicu matrix system 1/2/3/4 original idea**By ふぃっしゅ (Fish):** Fish numbers (Fish number 1 · Fish number 2 · Fish number 3 · Fish number 4 · Fish number 5 · Fish number 6 · Fish number 7 · S map · SS map · s(n) map · m(n) map · m(m,n) map) · Bashicu matrix system 1/2/3/4 formalisation · TR function (I0 function)**By Gaoji:** Weak Buchholz's function**By じぇいそん (Jason):** Irrational arrow notation · δOCF · δφ · ε function**By 甘露東風 (Kanrokoti):** KumaKuma ψ function**By koteitan:** Bashicu matrix system 2.3**By mrna:** 段階配列表記 · 降下段階配列表記 · 多変数段階配列表記 · SSAN · S-σ**By Naruyoko Naruyo:** Y sequence formalisation · ω-Y sequence formalisation**By Nayuta Ito:** N primitive · Flan numbers (Flan number 1 · Flan number 2 · Flan number 3 · Flan number 4 version 3 · Flan number 5 version 3) · Large Number Lying on the Boundary of the Rule of Touhou Large Number 4 · Googology Wiki can have an article with any gibberish if it's assigned to a number**By Okkuu:** Extended Weak Buchholz's function**By p進大好きbot:** Ordinal notation associated to Extended Weak Buchholz's function · Ordinal notation associated to Extended Buchholz's function · Naruyoko is the great · Large Number Garden Number**By たろう (Taro):** Taro's multivariable Ackermann function**By ゆきと (Yukito):** Hyper primitive sequence system · Y sequence original idea · YY sequence · Y function · ω-Y sequence original idea

**By バシク (BashicuHyudora):** Bashicu matrix system as a notation template**By じぇいそん (Jason):** Shifting definition**By mrna:** Side nesting**By Nayuta Ito and ゆきと (Yukito):** Difference sequence system

**By ふぃっしゅ (Fish):** Ackermann function**By koteitan:** Ackermann function · Beklemishev's worms · KumaKuma ψ function**By Mitsuki1729:** Ackermann function · Graham's number · Conway's Tetratri · Fish number 1 · Fish number 2 · Laver table**By みずどら:** White-aster notation**By Naruyoko Naruyo:** p進大好きbot's Translation map for pair sequence system and Buchholz's ordinal notation · KumaKuma ψ function · Naruyoko is the great**By 猫山にゃん太 (Nekoyama Nyanta):** Flan number 4 version 3 · Fish number 5 · Laver table**By Okkuu:** Fish number 1 · Fish number 2 · Fish number 3 · Fish number 5 · Fish number 6**By rpakr:** p進大好きbot's ordinal notation associated to Extended Weak Buchholz's function · Standardness decision algorithm for Taranovsky's ordinal notation

**By ふぃっしゅ (Fish):** Computing last 100000 digits of mega · Approximation method for FGH using Arrow notation · Translation map for primitive sequence system and Cantor normal form**By Kihara:** Proof of an estimation of TREE sequence · Proof of the incomparability of Busy Beaver function and FGH associated to Kleene's \(\mathcal{O}\)**By koteitan:** Translation map for primitive sequence system and Cantor normal form**By Naruyoko Naruyo:** Translation map for Extended Weak Buchholz's function and Extended Buchholz's function**By Nayuta Ito:** Comparison of Steinhaus-Moser Notation and Ampersand Notation**By Okkuu:** Verification of みずどら's computation program of White-aster notation**By p進大好きbot:** Proof of the termination of Hyper primitive sequence system · Proof of the termination of Pair sequence number · Proof of the termination of segements of TR function in the base theory under the assumption of the \(\Sigma_1\)-soundness and the pointwise well-definedness of \(\textrm{TR}(T,n)\) for the case where \(T\) is the formalisation of the base theory

**By 小林銅蟲 (Kobayashi Doom):** Sushi Kokuu Hen**By koteitan:** Dancing video of a Gijinka of Fukashigi · Dancing video of a Gijinka of 久界 · Storyteller's theotre video reading Large Number Garden Number aloud

See also: Template:Googology in Asia