Numbers, Part 4: Graham’s Number and Conway Arrows

This post brought to you by http://www.greatplay.net by Peter Hurford.
Check out the homepage for games, projects, and more blog posts.

Ads, woo!

Numbers, Part 4: Graham’s Number and Conway Arrows

29 January 2010, 12:00 am

“Numbers” Table of Contents

Part 1: Magnitude
Part 2: Exponentiation
Part 3: Hyper and Knuth Up Arrows
Part 4: Graham’s Number and Conway Arrows
Part 5: Extended Conway Arrows
Part 6: Limit Functions
Part 7: Larger Limit Functions
Part 8: Exponentiation Within Limit Functions

Graham’s Number and Very Large Quanities of Arrows

We have the notation $a \uparrow^n b$ to describe anything with n arrows. But what if we used Knuth’s up arrow notation to describe the number of arrows?

Graham’s Number does exactly that. Graham’s Number is an upper bound used in a mathematical proof, with more information about its history findable in it’s Wikipedia article.

However, it’s relevant here because it’s the 1980 Guiness Book of World Records holder for largest number that is used seriously in mathematics, as opposed to numbers that exist for the sake of being large, like every other number here. It is also larger than anything that can be expressed in Knuth’s up arrow notation.

Graham’s number is found by continuing a pattern:
$g_1 = 3 \uparrow^4 3 = 3 \uparrow \uparrow \uparrow \uparrow 3$

$g_2 = 3 \uparrow^{g_1} 3 = \underbrace{3 \uparrow \cdots \uparrow 3}_{3 \uparrow \uparrow \uparrow \uparrow 3 \text{ arrows}}$

$g_3 = 3 \uparrow^{g_2} 3 = \underbrace{3 \uparrow \cdots \uparrow 3}_{\underbrace{3 \uparrow \cdots \uparrow 3}_{3 \uparrow \uparrow \uparrow \uparrow 3}}$
…

Graham’s number is G, which is equal to the 64th entry in this series.
$G = g_{64} = 3 \uparrow^{g_63} 3 = \left. \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{\vdots}_{3 \uparrow \uparrow \uparrow \uparrow 3}}} \right\} 64 \text{ layers}$

Graham’s Number in Hyper Notation

Graham’s number can also be represented by the Hyper Function. We know that the c of the Hyper Function is the same as the amount of arrows – 2, so:
g₁ = hyper(3, 3, 6)
g₂ = hyper(3, 3, g₁) = hyper(3, 3, hyper(3, 3, 6))
g₃ = hyper(3, 3, g₂) = hyper(3, 3, hyper(3, 3, g₁)) = hyper(3, 3, hyper(3, 3, hyper(3, 3, 6)))
…
$G = g_{64} = \underbrace{hyper(3, 3, hyper(3, 3, hyper( \cdots hyper(3, 3, 6)))))}_{64 \text{ nested functions}}$

Magnitude within Graham’s Series

The series g₁, g₂, g₃… grows faster than any other series in applicable mathematics. The difference between g₁ and g₂ is already difficult to calculate — the first number has 4 arrows and the second has arrows equal to a number with four arrows.

It’s reminiscent of comparing 10^10 and 10^10^10 where the first number had ten zeros and the second number had zeros equal to a number with ten zeros, but on a much larger scale.

The series technically continues past g₆₄, with g₆₅ having an amount of arrows equal to Graham’s Number — which is much larger than G, or Graham’s number, itself.

Yet, these numbers, and even g_G is much smaller in comparison to what can be made with the next notation.

Conway Chained Arrow Notation

So we now can make larger numbers by using arrows to define the number of arrows, and then using arrows to define the number of arrows of the number arrows, etc.

John Conway summarized this into a single notation and then made the ability to go even larger.

Conway’s notation uses “chains” of arrows that have a finite amount of left-arrows, looking like this: $a \to b \to c \to d \to e \cdots$ .

A single left-arrow is the same as a single exponent:
$a \to b = a^b$

Two left-arrows equal Knuth’s notation:
$a \to b \to c = a\uparrow^c b$

Three left-arrows then blow our current systems out of the water. In order to understand $a \to b \to c \to d$ , we have to use the formal definition of Conway’s chained-arrow notation. This notation uses the following two rules.

Rule One

$\text{(A chain of any finite length)} \to 1 \to \text{(Another chain of any finite length)} = \text{(The first chain)}$

For example,
$6 \to 9 \to 3 \to 8 \to 1 \to 4 \to 5 \to 3 \to 3 = 6 \to 9 \to 3 \to 8$

Rule Two

$\text{(A chain of any finite length)} \to x \to y \to z = \text{(That same chain)} \to x \to [\text{(That same chain again)} \to (x-1) \to z] \to (z-1)$

For example,
$x \to y \to z = x \to (x \to (y-1) \to z) \to (z-1)$
$v \to w \to x \to y \to z = v \to w \to x \to (v \to w \to x \to (y-1) \to z) \to (z-1)$

and with actual numbers,
$6 \to 9 \to 3 \to 8 = 6 \to 9 \to (6 \to 9 \to 2 \to 8) \to 7$

More Examples

$3 \to 3 \to 2 = 3 \to (3 \to 2 \to 2) \to 1$
$3 \to (3 \to 2 \to 2) \to 1 = 3 \to (3 \to 2 \to 2)$
$3 \to (3 \to 2 \to 2) = 3 \to (3 \to (3 \to 1 \to 2) \to 1)$
$3 \to (3 \to (3 \to 1 \to 2) \to 1) = 3 \to (3 \to 3)$
$3 \to (3 \to 3) = 3 \to 3^3 = 3 \to 27 = 3^{27} = 7625597484987$

$3 \to 2 \to 2 \to 2 = 3 \to 2 \to (3 \to 2 \to 1 \to 2) \to 1$
$3 \to 2 \to (3 \to 2 \to 1 \to 2) \to 1 = 3 \to 2 \to (3 \to 2)$
$3 \to 2 \to (3 \to 2) = 3 \to 2 \to 9$
$3 \to 2 \to 9 = 3 \to (3 \to 1 \to 8) \to 8$
$3 \to (3 \to 1 \to 8) \to 8 = 3 \to 3 \to 8$
$3 \to 3 \to 8 = 3 \uparrow^8 3 = 3 \uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow\uparrow 3$

Comparing Four Entries to Knuth’s Notation

So just how many arrows will something like $3 \to 3 \to 3 \to 3$ make?

Three entries are easier to figure out:
$a \to b \to c = a \underbrace{\uparrow \uparrow \cdots \uparrow}_{c} b$

Then, since $a \to b \to c \to 2 = a \to b \to (a \to b \to (c-1) \to 2)$

$a \to b \to c \to 2 = \left. \underbrace{a \uparrow \cdots \uparrow b}_{ \underbrace{a \uparrow \cdots \uparrow b}_{ \underbrace{\vdots}_{\underbrace{a \uparrow \cdots \uparrow b}_{a}}}} \right\} c$

and

$a \to b \to c \to 3 = \underbrace{\left. \underbrace{a \uparrow \cdots \uparrow a}_{ \underbrace{a \uparrow \cdots \uparrow a}_{ \underbrace{\vdots}_{\underbrace{a \uparrow \cdots \uparrow a}_{a}}}} \right\} \cdots \left. \underbrace{a \uparrow \cdots \uparrow a}_{ \underbrace{a \uparrow \cdots \uparrow a}_{ \underbrace{\vdots}_{\underbrace{a \uparrow \cdots \uparrow a}_{a}}}} \right\} b}_{c}$

Thus,

$3 \to 3 \to 3 \to 3 = \left. \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{\vdots}_{\underbrace{3 \uparrow \cdots \uparrow 3}_{3}}}} \right\} \underbrace{3 \uparrow \cdots \uparrow 3}_{3 \uparrow \uparrow \uparrow 3}$

Comparing Graham’s Number to Four Entries

Graham’s Number evaluates very much like a form of $a \to b \to c \to 2$ , but no value of a can be both the 3 needed to be in front and at the end of the arrows, and the 4 for the initial amount of arrows. Thus that places Graham’s number between two Conway chains:

$\left. \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{\vdots}_{\underbrace{3 \uparrow \cdots \uparrow 3}_{3}}}} \right\} 64 < G < \left. \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{3 \uparrow \cdots \uparrow 3}_{ \underbrace{\vdots}_{\underbrace{3 \uparrow \cdots \uparrow 3}_{3}}}} \right\} 65$

Which means, that $3 \to 3 \to 64 \to 2 < G < 3 \to 3 \to 65 \to 2$

Note that $3 \to 3 \to 3 \to 3 = 3 \to 3 \to (3 \to 3 \to 2 \to 3) \to 2$ , which is much larger than G, and $3 \to 3 \to 3 \to 4$ is much larger than even g_{g_G}.

Next!

Next: Extending Conway Arrows with Subscripts

But Wait! There's More!

Find more posts like this one in the categories: All, Mathematics!
Leave a Comment and Tell Me What You Think!
Find Everything At The Homepage!
Subscribe to RSS and Never Miss a Post!
Following my Twitter and Get Updates on Posts and Cool Links!
Like my Facebook Page and Make My Ego Soar!