Fast Growing Functions

r.e.s.

unread,

May 17, 2003, 10:34:32 PM5/17/03

to

Last August, in a thread with the above subject line, I made an
assertion concerning a function n(k) defined by Harvey Friedman
in Section 8 of his article 'Enormous Integers in Real Life' at
http://www.math.ohio-state.edu/foundations/manuscripts.html

Since someone recently asked me for it, I'm posting now a rationale
(not a proof) for the assertion, which is
-------------------------------------------------------------------
> The lower bound for n(4) is enormously larger than any "familiar"
> big number -- including Graham's number
-------------------------------------------------------------------
where the lower bound is the one given by Friedman in the above-
mentioned article.

Here's my rationale ...

Define recursively an Ackermann hierarchy of "base b" operators:
b[1] n = b*n,
b[k] n = b[k-1] b[k-1] ... b[k-1] 1 (b[k-1] applied n times),
where b > 1, k > 1, n > 0, and all variables are integral.

Friedman's lower bound is defined with base 2, and Graham's number
is defined with base 3:

Friedman's lower bound is a(2[187196] 187196), where
a(0) = 1,
a(n) = 2[a(n-1)] a(n-1) for n > 0.

Graham's Number is g(64), where
g(0) = 4,
g(n) = 3[g(n-1)+1] 3 for n > 0.

That Friedman's lower bound is much greater than Graham's number
is a consequence of the following claim:

(*) For all p > 3, 2[p] p > (3[p-1] 3) + 2.

(The inequality is reversed for p = 2,3, then switches at p = 4,
and stays switched, I believe -- the left-hand side having the
greater growth rate.)

Now a(3) > g(0) + 2, so by (*) 2[a(3)] a(3) > (3[g(0)+1] 3) + 2,
giving a(4) > g(1) + 2; so by (*) 2[a(4)] a(4) > (3[g(1)+1] 3) + 2,
giving a(5) > g(2) + 2; etc.,
giving a(n) > g(n-3) + 2 for all n > 2.

In particular, a(2[187196] 187196) > a(68) > g(64).

Any suggestions for proving (*)?

(I believe a much stronger inequality also holds:
for all b > 1 and p > 3, b[p] p > (b+1)[p-1] p.)

--r.e.s.

r.e.s.

unread,

May 21, 2003, 3:33:26 PM5/21/03

to

"r.e.s." <rs.1 at mindspring.com> wrote ...

> Define recursively an Ackermann hierarchy of "base b" operators:
> b[1] n = b*n,
> b[k] n = b[k-1] b[k-1] ... b[k-1] 1 (b[k-1] applied n times),
> where b > 1, k > 1, n > 0, and all variables are integral.

Maybe that looks complicated, but it just defines the operations
[1] = *
[2] = ^
[3] = ^^
etc.

> (*) For all p > 3, 2[p] p > (3[p-1] 3) + 2.

> Any suggestions for proving (*)?

I've made several attempts at math. induction, without success --
so I'm asking again. Note that (*) will follow from

(**) For all p > 3, 2[p] p > 3[p-1] 4.

p=2: 2[2]2 = 2^2 = 4 < 3[1]4 = 3*4 = 12
p=3: 2[3]3 = 2^^3 = 2^2^2 = 16 < 3[2]4 = 3^4 = 81
p=4: 2[4]4 = 2^^^4 = 2^2^...^2 (2^16 2's) > 3[3]4 = 3^^4 = 3^3^3^3
etc

Once reversed, as it has at p=4, I can't believe the inequality will
ever switch back for some p>4. This isn't a case of "unprovable in
Peano arithmetic", is it?

--r.e.s.

r.e.s.

unread,

Jun 1, 2003, 7:16:53 PM6/1/03

to

"r.e.s." <rs.1 at mindspring.com> wrote ...
> Define recursively an Ackermann hierarchy of "base b" operators:
> b[1] n = b*n,
> b[k] n = b[k-1] b[k-1] ... b[k-1] 1 (b[k-1] applied n times),
> where b > 1, k > 1, n > 0, and all variables are integral.

Here's a nice inequality concerning "change of base". (I don't
know if it's already in the literature.) In the following, all
operators associate from right to left, and all variables are
positive integers.

Theorem 1. For all b>1, k>0, n>0, b[k] n <= 2[k] (b-1)n,
with strict inequality for b>2.

<begin sketch pf of Thm.1>
Proposition S(k): For all b>1, n>0, b[k] n <= 2[k] (b-1)n.

S(1): For all b>1, n>0, b[1] n <= 2[1] (b-1)n;
this holds since 2 <= b --> 2n <= bn --> bn <= 2(b-1)n.

S(k) --> S(k+1):
S(k+1): For all b>1, n>0, b[k+1] n <= 2[k+1] (b-1)n.

For n=1, b[k+1]1 = b <= 2(b-1) <= 2[k+1](b-1), as required,
so consider n > 1:

On the one hand,
b[k+1]n = b[k] b[k+1] (n-1)
b[k+1]n <= 2[k](b-1)* b[k+1] (n-1), by S(k)
...
b[k+1]n <= (2[k](b-1)*)^(n-1) b[k+1] 1 (^ meaning iteration)
b[k+1]n <= (2[k](b-1)*)^(n-1) b, since b[x]1 = b

while on the other hand,
2[k+1](b-1)n = (2[k])^((b-1)n) 1
2[k+1](b-1)n = (2[k])^((b-1)(n-1)) (2[k])^(b-1) 1
2[k+1](b-1)n >= ((2[k])^(b-1))^(n-1) b ((1))
2[k+1](b-1)n >= ((2[k](b-1)*)^(n-1) b ((2))

where ((1)) and ((2)) follow from
(2[k])^(b-1) x = 2[k] (2[k])^(b-2) x (any x>0)
(2[k])^(b-1) x >= 2[k] 2^(b-2) x
(2[k])^(b-1) x >= 2[k] (b-1) x cf. ((2))
(2[k])^(b-1) 1 >= 2[k] (b-1) 1
(2[k])^(b-1) 1 >= 2(b-1)
(2[k])^(b-1) 1 >= b cf. ((1))
<end sketch pf of Thm.1>

Lemma 1. For all k>0, 2 + 3[k]3 < 2[k]7.

A corollary of the next theorem is that Friedman's lower
bound, which is a(2[187196] 187196) in the sequence defined
by a(1) = 2, a(n) = 2[a(n-1)]a(n-1) (n>1), is enormously
larger than Graham's number, which is g(64) in the sequence
defined by g(1) = 3[5]3, g(n) = 3[1 + g(n-1)]3 (n>1):

Theorem 2. For all n>0, g(n) < a(n+3).

<begin sketch pf of Thm.2>
Proposition T(n): 1 + g(n) < a(n+3)
T(1): 1 + g(1) < a(4):
1 + g(1) = 1 + 3[5]3
1 + g(1) < 2[5]7, by Lem.1
1 + g(1) < 2[a(3)]a(3), since a(3) > 7
1 + g(1) < a(4).

T(n) --> T(n+1):
T(n+1): 1 + g(n+1) < a(n+4).

1 + g(n+1) = 1 + 3[1 + g(n)]3
1 + g(n+1) < 2[1 + g(n)]7, by Lem.1
1 + g(n+1) < 2[1 + g(n)](1 + g(n)), since 1 + g(n) > 7
1 + g(n+1) < 2[a(n+3)]a(n+3), by T(n)
1 + g(n+1) < a(n+4).
<end sketch pf of Thm.2>

Corollary. Graham's number, g(64), is less than a(67).

It would be nice to prove g(64) < a(n) for some n < 64.