# Graham's number

## Primary tabs

\documentclass{article}
% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%%%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here

\begin{document}
{\em 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 {\it 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{matrix} \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \ \\ 3^{3^3} & \text{threes} \end{matrix} \right) = \left. \begin{matrix} \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \ \\ \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \text{threes} \\ \vdots & \vdots \\ \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \text{threes} \\ 3^{3^3} & \text{threes} \\ \end{matrix} \right \} \begin{matrix} \ & \ \\ \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \mbox{ layers} \\ 3^{3^3} & \text{ threes} \end{matrix}$$

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 {\it 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.

\begin{thebibliography}{2}
\bibitem{ms} M. P. Slone, PlanetMath message, March 19, 2007.
\bibitem{rg} R.~L.~Graham and B.~L.~Rothschild, Ramsey's theorem for $n$-parameter sets'', {\it Trans.~Amer.~Math.~Soc.}, {\bf 159} (1971): 257 - 292
\bibitem{rg} R.~L.~Graham and B.~L.~Rothschild. Ramsey theory. {\it Studies in combinatorics}, ed. G.-C.~Rota, Mathematical Association of America, 1978.
\end{thebibliography}
%%%%%
%%%%%
nd{document}