Graham's number
**
G
**
and the
Moser number

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 thata^(b×c) <a^(b^c), or thatb×c<b^c, which is true forb,c>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
^{
n
}
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 (andn>2):

n[5] =n[4]_{ n }[from definition]

=n[4][4]_{ n -1 }

< (n^^^n)[4]_{ n -1 }[by Lemma 2, withk= 2]

< ((n^^^n)^^^(n^^^n))[4]_{ n -2 }[by Lemma 2 again]

...

< (...(n^^^n)^^^(n^^^n)...)^^^...^^^(...(n^^^n)^^^(n^^^n)...) (2^{ n }terms)

<n^^^^2^n[by Lemma 1]

<n^^^^^n

**
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

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