Graham’s number
Graham’s number $G$ is an upper bound in a problem in Ramsey theory, first mentioned in a paper by Ronald Graham and B. Rothschild. The Guinness Book of World Records calls it the largest number ever used in a mathematical proof. Graham’s number is too difficult to write in scientific notation, so it is generally written using Knuth’s arrow-up notation. In Graham’s paper, the bound is given as
$$6\le N(2)\le A(A(A(A(A(A(A(12,3),3),3),3),3),3),3),$$ |
where $N(2)$ is the least natural number^{} such that $n\ge N(2)$ implies that given any arbitrary $2$-coloring^{} of the line segments between pairs of vertices of an $n$-dimensional box, there must exist a monochromatic rectangle in the box.
Here $A$ is the function defined by (this is a direct quote):
$$A(1,n)={2}^{n},A(m,2)=4,m\ge 1,n\ge 2,A(m,n)=A(m-1,A(m,n-1)),m\ge 2,n\ge 3.$$ |
In the earlier paper Graham and Rothschild called this function $F$ instead of $A$, and commented: “Clearly, there is some room for improvement here.”
In Knuth’s arrow-up notation, Graham’s number is still cumbersome to write: we define the recurrence relation ${g}_{1}=3\uparrow \uparrow \uparrow \uparrow 3$ and ${g}_{n}=3{\uparrow}^{{g}_{n-1}}3$. Graham’s number is then $G={g}_{64}$.
To help understand Graham’s number from the more familiar viewpoint of standard exponentiation, Wikipedia offers the following chart:
$${g}_{1}=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow \uparrow \left(\begin{array}{cc}\hfill \underset{\u23df}{{3}^{{3}^{{\cdot}^{{\cdot}^{{\cdot}^{3}}}}}}\hfill & \hfill \hfill \\ \hfill {3}^{{3}^{3}}\hfill & \hfill \text{threes}\hfill \end{array}\right)=\begin{array}{cc}\hfill \underset{\u23df}{{3}^{{3}^{{\cdot}^{{\cdot}^{{\cdot}^{3}}}}}}\hfill & \hfill \hfill \\ \hfill \underset{\u23df}{{3}^{{3}^{{\cdot}^{{\cdot}^{{\cdot}^{3}}}}}}\hfill & \hfill \text{threes}\hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill \underset{\u23df}{{3}^{{3}^{{\cdot}^{{\cdot}^{{\cdot}^{3}}}}}}\hfill & \hfill \text{threes}\hfill \\ \hfill {3}^{{3}^{3}}\hfill & \hfill \text{threes}\hfill \end{array}\}\begin{array}{cc}\hfill \hfill & \hfill \hfill \\ \hfill \underset{\u23df}{{3}^{{3}^{{\cdot}^{{\cdot}^{{\cdot}^{3}}}}}}\hfill & \hfill \text{layers}\hfill \\ \hfill {3}^{{3}^{3}}\hfill & \hfill \text{threes}\hfill \end{array}$$ |
We don’t know what the most significant base 10 digits of Graham’s number are, but we do know that the least significant digit is 7 (and of course 0 in base 3).
Graham’s number has its own entry in Wells’s Dictionary of Curious and Interesting Numbers, it is the very last entry, right after Skewes’ number, which it significantly dwarfs, and which was once also said to be the largest number ever used in a serious mathematical proof.
References
- 1 M. P. Slone, PlanetMath message, March 19, 2007.
- 2 R. L. Graham and B. L. Rothschild, “Ramsey’s theorem^{} for $n$-parameter sets”, Trans. Amer. Math. Soc., 159 (1971): 257 - 292
- 3 R. L. Graham and B. L. Rothschild. Ramsey theory. Studies in combinatorics, ed. G.-C. Rota, Mathematical Association of America, 1978.
Title | Graham’s number |
---|---|
Canonical name | GrahamsNumber |
Date of creation | 2013-03-22 17:15:15 |
Last modified on | 2013-03-22 17:15:15 |
Owner | PrimeFan (13766) |
Last modified by | PrimeFan (13766) |
Numerical id | 4 |
Author | PrimeFan (13766) |
Entry type | Definition |
Classification | msc 00A05 |
Classification | msc 05A05 |
Classification | msc 68P30 |