Fork me on GitHub
Math for the people, by the people.

User login

Graham's number

% 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

% used for TeXing text within eps files
% need this for including graphics (\includegraphics)
% for neatly defining theorems and propositions
% making logically defined graphics

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

% define commands here

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

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:

= 3 \uparrow \uparrow \uparrow \uparrow 3 
= 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) 
= 3 \uparrow \uparrow \uparrow 
      \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \  \\ 
      3^{3^3} & \text{threes} 
= \left.
      \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} \\
  \right \}
    \ & \ \\
    \underbrace{3^{3^{\cdot^{\cdot^{\cdot^{3}}}}}} & \mbox{ layers} \\ 
    3^{3^3} & \text{ threes}

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.  

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