Definition:Graham's Number

From ProofWiki
Jump to navigation Jump to search


Let $3 \uparrow 3$ denote Knuth's notation for powers:

$3 \uparrow 3 := 3^3$

Further, let:

$3 \uparrow \uparrow 3 := 3 \uparrow \paren {3 \uparrow 3} = 3^{\paren {3^3} }$

and so define:

$3 \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow}_n 3 := 3 \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow}_{n - 1} \paren {3 \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow}_{n - 1} 3}$

Thus, for example:

$3 \uparrow \uparrow \uparrow \uparrow 3 = 3 \uparrow \uparrow \uparrow \paren {3 \uparrow \uparrow \uparrow 3}$


$n_1 := 3 \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow}_{3 \uparrow \uparrow \uparrow \uparrow 3} 3$

That is, a total of $3 \uparrow \uparrow \uparrow \uparrow 3$ instances of $\uparrow$.

Similarly, let:

$n_2 := 3 \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow}_{n_1} 3$

In general for $m \ge 2$:

$n_m := 3 \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow}_{n_{m - 1} } 3$

and so specifically:

$n_{63} := 3 \underbrace {\uparrow \uparrow \ldots \uparrow \uparrow}_{n_{62} } 3$

It is this $n_{63}$ which is defined as Graham's number.

Source of Name

This entry was named for Ronald Lewis Graham.

Historical Note

Ronald Lewis Graham arrived at his number as an upper bound to the solution to a certain problem in Ramsey theory.

Strictly speaking, the number used by Graham is somewhat smaller than the number described here, but is less easily described.

This version is the one given to Martin Gardner, who then publicised it in his Mathematical Games column in Scientific American.

It entered the record books as the largest number ever used in a mathematical proof.

Amusingly, given that Graham's number is an upper bound, the actual solution to the problem in question, according to certain experts, may well be $6$.