[FOM] n(3) < Graham's number < n(4) < TREE[3]

[Harvey Friedman]

There seems to be some confusion (evidently on my part) about just what
Graham's number is.
http://www.cs.nyu.edu/pipermail/fom/2006-March/010284.html gives a
definition of it using my notation

A_1 = the doubling function from {1,2,...} into {1,2,...}.
A_k+1(n) = A_kA_k...A_k(1), where there are n A_k's.
A(k,n) = A_k(n).
A(k) = A(k,k).

More formally, for all k >= 1, we define A_k:Z+ into Z+ as follows.

A_1(n) = 2n.
A_k+1(1) = 2.
A_k+1(n+1) = A_k(A_k+1(n)).

We also define

A(k,n) = A_k(n).
A(k) = A(k,k).

If we take the definition in
http://www.cs.nyu.edu/pipermail/fom/2006-March/010284.html

then Graham's number is a lot bigger than my number n(3). However, it would
be very much smaller than my n(4). See
http://www.cs.nyu.edu/pipermail/fom/2006-March/010279.html

*********************************

Here is an account of Graham's number from
http://www-users.cs.york.ac.uk/susan/cyc/g/graham.htm

"The World Champion largest number, listed in the latest Guinness
Book of Records , is an upper bound, derived by R. L. Graham,
from a problem in a part of combinatorics called Ramsey theory.

Graham's number cannot be expressed using the conventional
notation of powers, and powers of powers. If all the material in
the universe were turned into pen and ink it would not be enough
to write the number down. Consequently, this special notation,
devised by Donald Knuth, is necessary.

3^3 means '3 cubed', as it often does in computer printouts.

3^^3 means 3^(3^3), or 3^27, which is already quite large: 3^27
= 7,625,597,484,987, but is still easily written, especially as a
tower of 3 numbers: 3 33.

3^^^3 = 3^^(3^^3), however, is 3^^7,625,597,484,987 =
3^(7,625,597,484,987^7,625,597,484,987), which makes a tower of
exponents 7,625,597,484,987 layers high.

3^^^^3 = 3^^^(3^^^3), of course. Even the tower of exponents is
now unimaginably large in our usual notation, but Graham's number
only starts here. 

Consider the number 3^^^...^^^3 in which there are 3^^^^3
arrows. A largish number!

Next construct the number 3^^^...^^^3 where the number of arrows
is the previous 3^^^...^^^3 number.

An incredible, ungraspable number! Yet we are only two steps
away from the original ginormous 3^^^^3. Now continue this
process, making the number of arrows in 3^^^...^^^3 equal to the
number at the previous step, until you are 63 steps, yes, sixty-three ,
steps from 3^^^^3. That is Graham's number.

There is a twist in the tail of this true fairy story. Remember
that Graham's number is an upper bound, just like Skewes' number . What is
likely to be the actual answer to Graham's problem? Gardner quotes the
opinions of the experts in Ramsey theory, who suspect that the
answer is: 6 

'Mathematical Games', Scientific American , November 1977.

-- Wells. Dictionary of Curious and Interesting Numbers . 1986"

*****************************************

When I read this account, I WRONGLY assumed that ^ was simple
exponentiation. 

BUT, now I see the LIGHT, also from

http://en.wikipedia.org/wiki/Graham's_number
http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation

that ^ is (supposed to be) the Knuth UPARROWS notation, where the number of
uparrows in a row corresponds to the level of the Ackermann hierarchy; i.e.,
roughly the subscript on my A's.

So we are talking about something like, if it was in base 2,

A...A(1), where there are 64 A's.

But being in base 3, it is somewhat bigger, say with a few more A's.

So this is certainly bigger than the lower bound that I state for n(3) >
A_7198(158386). In fact, I know an upper bound for n(3) of, if I memory is
not failing me, AA(5), which is certainly smaller than Graham's number.

However, n(4) > AA...A(1), where there are A(L) A's. Here L >= 187196.

So n(4) >> Graham's number.

NOTE: n(k) is the ACTUAL solution of a simple combinatorial problem, and
these are KNOWN lower bounds. See

H. Friedman, Long Finite Sequences, Journal of Combinatorial Theory, Series
A 95, 102-144 (2001).

PS: n(1) = 3, n(2) = 11. n(4) is too puny to even think about mentioning
against TREE[3]. 

Harvey Friedman