home > factoids > big numbers > Graham v Moser

Tim Chow's proof outline

Lemma 1

In any expression involving Knuth arrows and positive integers n > 2, the parenthisation that creates the largest number is the one that associates from the right.

For example, ( a^^^b )^^ c < a ^^^( b^^c )

Proof : by induction.

For single arrows, or ordinary exponentiation, this is the well known result that ( a^b )^ c < a ^( b^c ), or that a ^( b × c )  < a ^( b^c ), or that b × c < b^c , which is true for b , c > 2 .

Lemma 2

If n >2, then n [ k +2] < n ^^...^^ n (2 k -1 arrows)

Proof . From the details of the Moser construction, it is easy to see that n [4] = (...( n^n )^( n^n )...)^...^(...( n^n )^( n^n )...)[2 ⁿ terms]. From Lemma 1, this is less than the expression with n terms all associating to the right: n [4] < n^n ^...^ n [2^ n terms]. From the definition of Knuth arrows, we have n [4] < n ^^2^ n

It is not hard to show, for n >2, that n ^^2^ n < n^^^n

Then one can proceed to the general result by induction on k , invoking Lemma 1 in the general case.

For example, when k =3 (and n >2):

n [5] = n [4] _n [from definition]
= n [4][4] _{n -1}
< ( n^^^n )[4] _{n -1} [by Lemma 2, with k = 2]
< (( n^^^n )^^^( n^^^n ))[4] _{n -2} [by Lemma 2 again]
...
< (...( n^^^n )^^^( n^^^n )...)^^^...^^^(...( n^^^n )^^^( n^^^n )...) (2 ⁿ terms)
< n ^^^^2^ n [by Lemma 1]
< n^^^^^n

Proof that G >> M

M = 2[2[5]] < 3[2[5]] < 3^^...^^3 (2[5]×2 -1 arrows), by lemma 2.

Now 2[5] < 3[5] < 3^^^^^3 by lemma 2

So M < 3^^...^^3 (3^^^^^3×2-1 arrows) << G ₂ << G

[ 7 July 1998 . My thanks to Tim Chow for emailing me this proof.]