# Graham's number

*3,974*pages on

this wiki

*For other uses, see Graham's number (disambiguation).*

**Graham's number** is a famous large number, defined by Ronald Graham.^{[1]}

Using up-arrow notation, it is defined as:

\begin{eqnarray*} g_0 &=& 4 \\ g_1 &=& 3 \uparrow\uparrow\uparrow\uparrow 3 \\ g_2 &=& 3 \underbrace{\uparrow\uparrow\cdots\uparrow\uparrow}_{g_1 \text{ arrows}} 3 \\ g_{k + 1} &=& 3 \underbrace{\uparrow\uparrow\uparrow\cdots\uparrow\uparrow\uparrow}_{g_k \text{ arrows}} 3 \\ g_{64} &=& \text{Graham's number} \end{eqnarray*}

Graham's number is commonly celebrated as the largest number ever used in a 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.

## Contents

[show]## History Edit

Graham's number arose out of the following unsolved problem in Ramsey theory:

LetN*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.^{[2]} 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 Guiness World Records.

In 2013, the upper bound was further reduced to *N'* = 2↑↑2↑↑2↑↑9 using the Hales–Jewett theorem.^{[3]} As of 2014, the best known *lower* bound for *N** is 13, shown by Jerome Barkley in 2008.^{[4]}

## Comparison Edit

Since g_{0} is 4 and not 3, Graham's number cannot be expressed efficiently in chained arrow notation \(g_{64} \approx 3 → 3 → 64 → 2\) or BEAF \(\{3,65,1,2\} < g_{64} < \{3, 66, 1, 2\}\). Using Jonathan Bowers' G functions it is exactly G^{64}4 in base 3. 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.^{[5]} 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.^{[6]} Coincidentally, Stepney was sent a similar proof by Todd Cesere several days later.

It has been proven that Graham's number is much less than \(\Sigma(64)\),^{[7]} and later a better upper bound \(\Sigma(22)\) was proven.

In the fast-growing hierarchy, Graham's number can be shown to be less than \(f_{\omega+1}(64)\).

## Calculating last digits Edit

The final digits of Graham's number can be computed by taking advantage of the convergence of last digits, because Graham's number is a power tower of threes. Here is a simple algorithm to obtain the last \(x\) digits \(N(x)\) of Graham's number:

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

For example:

- \(N(1) = 3^{N(0)} \equiv 3^3 \equiv 27 \equiv 7 \pmod{10}\), so the last digit is 7.
- \(N(2) = 3^{N(1)} \equiv 3^7 \equiv 2187 \equiv 87 \pmod{100}\), so the last two digits are 87.
- \(N(3) = 3^{N(2)} \equiv 3^{87} \equiv 323257909929174534292273980721360271853387 \equiv 387 \pmod{1000}\), so the last three digits are 387.
- etc.

This naive method is not very efficient, since number of digits in the leftmost expression grows exponentially. We can use right-to left binary method instead:

- Convert the exponent into binary form. E.g. \(87_{10} = 1010111_2\)
- If last digit of exponent is 1, then multiply base to result and square base.
- Otherwise, just square base.

Using this, it can be shown that last 20 digits of Graham's number are: \(...04575627262464195387\).^{[8]}

## Video Edit

Source: Graham's Number - Numberphile

## Sources Edit

- ↑ Graham's Number
- ↑ Graham & Rothchild 1971 paper
- ↑ http://arxiv.org/pdf/1304.6910v2.pdf
- ↑ 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.
- ↑ Proof that BB(64) >> G
- ↑ Last 10000 digits of G

## See also Edit

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

## External links Edit

**By Harvey Friedman:** Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · Friedman's circle theorem · TREE sequence TREE(3) · subcubic graph number SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · Greedy clique sequence**Hydras:** Kirby-Paris · Beklemishev's worms · Buchholz**Miscellaneous:** Factorial · Folkman's number · Exploding Tree Function · **Graham's number** · fusible number · Goodstein function · Laver table