Growth Rate of Level-k Goodstein Function

Note:
I posted these same questions early last year to sci.math at
http://groups.google.com/group/sci.m...ac659d9a47b223
http://groups.google.com/group/sci.m...282e18a4b30d48
(Those are the individual postings in case this one get broken:
http://groups.google.com/group/sci.m...94b3349a4c1959)

There've been no replies, but the questions seem interesting
enough to be worth the present cross-posted attempt to see
if anyone can shed some light.

Background
----------
What's usually called "the" Goodstein function is only the 3rd
in a hierarchy of functions at levels k = 1,2,3,..., defined
in Goodstein's 1947 paper. The level-k Goodstein function, g_k,
is defined in terms of the hereditary respresentation of
integers, using only the first k operations in the hierarchy
commonly written +,*,^,^^,^^^,... -- see the links for details,
including the following formula that I derived for g_1 (which
uses only '+' in the hereditary representations) ...

g_1(n) = 2^floor(n/a)*(a + n%a + 1) - 3 (n >= 0)

where a >= 2 is the initial base. It turns out that every
Goodstein function g_k (k >= 1) is some subsequence of g_1.

"The" Goodstein function g_3 uses only +,*,^ in the hereditary
representations, and is known to have a growth rate described
by the ordinal epsilon_0 in the "fast-growing" Wainer hierarchy
of functions.

Questions
---------
(1) At what ordinal in the Wainer hierarchy is g_2, Goodstein's
level-2 function? (It's strictly less than epsilon_0, and I
think a formula should be derivable for g_2 involving operators
at levels higher than '^' -- but I haven't yet succeeded.)

(2) Is the growth rate of g_4 described by an ordinal w.r.t.
some fast-growing hierarchy of functions? If so, what is it,
exactly? If not, how might that growth rate be characterised?
(Etc. for the higher-level g_k.)

--r.e.s.

g_1=w*w, g_2=w^w=ackermann function, g_3=w^^w=Epsilon_0,
g_4=w^^^w=Gamma_0. Ironic isn't it?
These can be written as recursive functions as follows:
g_2(n)=Ack(log2(n),2)
Ack(x,y)=Ack(x-1,Ack(x,y-1))
Ack(0,y)=y+1
Ack(x,0)=2
g_3(n)=F(n,2)
F(x,y)=F(H(x,0,y)-1,y+1)
F(0,y)=y
H(x,y,z)=(x%z)*(z+1)^F(y,0,z)+F(floor(x/z),y+1,b)
H(0,y,z)=0
g_4(n) is a bit harder I'll get back to you on that one.

Heres an interesting ordinal that occurs if instead of using
+,*,^,^^,... you define each combination of w e.g w^(w+5*w^^(w+1))+3*w
as an operator e.g 1,2,3,4,... would be +,*,^,^^,... ,g_w would be
w(operator w iow Ack)w and g_(w^^(w+1)) would be w(w^^(w+1))w.
g_(g_(...(g_(w)...)) (iirc called kappa_0) is (I think) what the fast
growing hierarchy is.

> H(x,y,z)=(x%z)*(z+1)^F(y,0,z)+F(floor(x/z),y+1,b)
Oops! that should have been:
H(x,y,z)=(x%z)*(z+1)^H(y,0,z)+H(floor(x/z),y+1,b)

"CH" <cchh1990{}Yahoo.co.uk> wrote ...
> g_1=w*w, g_2=w^w=ackermann function, g_3=w^^w=Epsilon_0,
> g_4=w^^^w=Gamma_0. Ironic isn't it?

What you've written in terms of w is the least ordinal
having no level-k hereditary representation (k=1,2,3,4)
but that's not generally the ordinal that describes the
growth rate of g_k, say with respect to a fast-growing
hierarchy. E.g., g_1 ~ f_1, not f_(w*w), in the Wainer
hierarchy; also, Ackermann function ~ f_w, not f_(w^w),
and gamma_0 > w^^^w.

>> These can be written as recursive functions as follows:
>> g_2(n)=Ack(log2(n),2)
>> Ack(x,y)=Ack(x-1,Ack(x,y-1))
>> Ack(0,y)=y+1
>> Ack(x,0)=2
>> g_3(n)=F(n,2)
>> F(x,y)=F(H(x,0,y)-1,y+1)
>> F(0,y)=y
>> H(x,y,z)=(x%z)*(z+1)^F(y,0,z)+F(floor(x/z),y+1,b)
>> H(0,y,z)=0
>> g_4(n) is a bit harder I'll get back to you on that one.
>
> Oops! that should have been:
> H(x,y,z)=(x%z)*(z+1)^H(y,0,z)+H(floor(x/z),y+1,b)

The g_k are certainly recursive functions, but what
you've written is incorrect. (Try some test cases.)

<snip>

> "CH" <cchh1990{}Yahoo.co.uk> wrote ...
> > g_1=w*w, g_2=w^w=ackermann function, g_3=w^^w=Epsilon_0,
> > g_4=w^^^w=Gamma_0. Ironic isn't it?
>
> What you've written in terms of w is the least ordinal
> having no level-k hereditary representation (k=1,2,3,4)
> but that's not generally the ordinal that describes the
> growth rate of g_k, say with respect to a fast-growing
> hierarchy. E.g., g_1 ~ f_1, not f_(w*w), in the Wainer
> hierarchy; also, Ackermann function ~ f_w, not f_(w^w),
> and gamma_0 > w^^^w.
>

w*w,w^w, ect. are being represented as a goodstien list,
not by their place in the Wainer hierarchy. In that setting
the least ordinal not to have a level-k representation is
the ordinal that describes g_k's growth rate.

gamma_0 is the solution to epsilon_a=a. This is w^^^w.

> >> These can be written as recursive functions as follows:
> >> g_2(n)=Ack(log2(n),2)
> >> Ack(x,y)=Ack(x-1,Ack(x,y-1))
> >> Ack(0,y)=y+1
> >> Ack(x,0)=2
> >> g_3(n)=F(n,2)
> >> F(x,y)=F(H(x,0,y)-1,y+1)
> >> F(0,y)=y
> >> H(x,y,z)=(x%z)*(z+1)^F(y,0,z)+F(floor(x/z),y+1,b)
> >> H(0,y,z)=0
> >> g_4(n) is a bit harder I'll get back to you on that one.
> >
> > Oops! that should have been:
> > H(x,y,z)=(x%z)*(z+1)^H(y,0,z)+H(floor(x/z),y+1,b)
>
> The g_k are certainly recursive functions, but what
> you've written is incorrect. (Try some test cases.)
>

What I gave for g_2 was an aproximation. g_2 is between
Ack(log2(n)-1,2) and Ack(log2(n)+1,2).
The exact equation is:
g_2(n)=F(1,floor(log2(n)),g_2(n-2^( floor(log2(n)) )))
F(x,y,z)=F(x-1,y,F(z,y-1,z))
F(0,y,z)=z
F(x,0,z)=z+x

CH wrote (in part):

> gamma_0 is the solution to epsilon_a=a. This is w^^^w.

If you're talking about the least fixed point of
the function fmega_1 --> omega_1 defined by
f(a) = epsilon_a, where epsilon_a is the a'th fixed
point of the function gmega_1 --> omega_1 defined
by g(b) = w^b, then you're nowhere near gamma_0.

It is true that gamma_0 is among the solutions to
epsilon_a = a, but gamma_0 is also among the ordinals
that are fixed by gamma_0 many iterations of this
"fixed points of fixed points" process, of which the
first two are described in the previous sentence.

Dave L. Renfro

"CH" <cchh1990{}Yahoo.co.uk> wrote ...
> w*w,w^w, ect. are being represented as a goodstien list,
> not by their place in the Wainer hierarchy. In that setting
> the least ordinal not to have a level-k representation is
> the ordinal that describes g_k's growth rate.

Those ordinals do indicate why the growth rate of g_(k+1)
is "much larger" than that of g_k.


> gamma_0 is the solution to epsilon_a=a. This is w^^^w.

As David Renfro mentioned, gamma_0 is one of infinitely-
many solutions (but not the least one).

I find it tricky to determine which ordinal (in more-
standard notation) corresponds to Goodstein's w^^^w.
Although it's surely far below gamma_0, it's not clear
to me which ordinal it is.


> What I gave for g_2 was an aproximation.
> g_2 is between Ack(log2(n)-1,2) and Ack(log2(n)+1,2).

That's not quite right (try it for g_2(4)), but you've
encouraged me to work out some details. Here's what I
find ...

Writing [k] for the kth of the operators +,*,^,^^,...
(e.g. 2[3]4 = 2^4), and writing p for floor(log_a(n)),

2[p+1](p+a-1) < g_2(n) < 2[p+2](p+a) (n > a)

where a >= 2 is the initial base used in the Goodstein
sequences (usually a=2). These bounds result from a set
of p linked recursions, with the final value of the ith
recursion equal to the initial value of the (i+1)th,
and the ith recursion using operations only up to [i].


> The exact equation is:
> g_2(n)=F(1,floor(log2(n)),g_2(n-2^( floor(log2(n)) )))
> F(x,y,z)=F(x-1,y,F(z,y-1,z))
> F(0,y,z)=z
> F(x,0,z)=z+x

That's not correct -- try it for g_2(3). Having looked
more closely now at the situation, I would be very very
suprised if it were possible to define g_2 by such a
simple recursion, let alone the kind of simple "formula"
I at first had in mind.

-
Does anyone know of any work at all that discuss the g_k
hierarchy (other than by Goodstein, of course)?

It surprises me to never have seen it even mentioned that
the function usually called "the" Goodstein function is
only the 3rd in a hierarchy ordered by the highest level
of operation (+,*,^,^^,...) used to represent integers.
It's commonly mentioned that g_3 ~ f_epsilon_0; surely
the other g_k ought to be of interest?

r.e.s. wrote (in part):

> Does anyone know of any work at all that discuss the g_k
> hierarchy (other than by Goodstein, of course)?
>
> It surprises me to never have seen it even mentioned that
> the function usually called "the" Goodstein function is
> only the 3rd in a hierarchy ordered by the highest level
> of operation (+,*,^,^^,...) used to represent integers.
> It's commonly mentioned that g_3 ~ f_epsilon_0; surely
> the other g_k ought to be of interest?

I wrote up an extensive set of notes on ordinal numbers
in 1985, and then a revised version in 1991, and I've
been meaning to post an outline of them for several years.
Now seems to be a good time for me to do this. It will
take a few days, however. But for the time being, below
are some things I've posted that might be of use. The
first URL is a sci.math thread (at The Math Forum,
because my posts didn't get picked up by google for
some reason) -- look at the posts by Royce Peng and
myself during the period Feb. 5-11, 2002. The next
URL takes you to a sci.math post that discusses
gamma_0 some. The third URL is a sci.math post at
The Math Forum (again, because it wasn't picked up
by google) that includes some of the material that
I intend to be writing about. However, for some
reason, a lot of funny-looking characters crept
in. (They weren't in the post when it first appeared.
They showed up after The Math Forum's last URL change.

http://mathforum.org/kb/thread.jspa?threadID=77834

http://groups.google.com/group/sci.m...d4b9cb3c5e6fc9

http://mathforum.org/kb/thread.jspa?messageID=3414869

Dave L. Renfro

"Dave L. Renfro" <renfr1dl{}cmich.edu> wrote ...
> I wrote up an extensive set of notes on ordinal numbers
> in 1985, and then a revised version in 1991, and I've
> been meaning to post an outline of them for several years.
> Now seems to be a good time for me to do this. It will
> take a few days, however. But for the time being, below
> are some things I've posted that might be of use.
[...]

Thanks for the links. I believe that through the years I've
read with interest most if not all of your postings on these
topics!

However, those and all other sources I know of (except for
Goodstein himself) refer to no Goodstein function other than
the one based on hereditary representations using only +,*,^.
The hierarchy of functions that Goodstein obtained by using
operations +,*,^,^^,^^^,..., up to ever-higher levels in the
hereditary representations, seems never to be mentioned.

In terms of the Wainer hierarchy f_a, we now have ...

g_1 ~ f_1
g_2 ~ f_w
g_3 ~ f_epsilon_0
g_4 ~ f_?????
....

and I wonder whether -- comparable to g_3 -- g_4 might be
related to known results for some Hydra-like game.

On the side-issue concerning w^^^w, any pointers on how to
relate that to the epsilon ordinals?

"r.e.s." <r.s{}ZZmindspring.com> wrote ...
> "CH" <cchh1990{}Yahoo.co.uk> wrote ...
>> The exact equation is:
>> g_2(n)=F(1,floor(log2(n)),g_2(n-2^( floor(log2(n)) )))
>> F(x,y,z)=F(x-1,y,F(z,y-1,z))
>> F(0,y,z)=z
>> F(x,0,z)=z+x
>
> That's not correct -- try it for g_2(3). Having looked
> more closely now at the situation, I would be very very
> suprised if it were possible to define g_2 by such a
> simple recursion, let alone the kind of simple "formula"
> I at first had in mind.

Here's the most concise recursion I've managed to write
for g_2 with initial base a ...

g_2(n) = b_(floor(log_a(n+1))) - 2 (n >= 0)
b_0 = a
b_(k+1) = (f_k)^(x_k) (b_k)

where the f_k are in the fast-growing hierarchy of
functions defined recursively by

f_0 (t) = t + 1
f_(k+1) (t) = (f_k)^(t+1) t

and the x_k are defined recursively by

x_0 = n % a
x_(k+1) = ( (n - sum(a^i*x_i, i=0..k)) / a^k ) % a.

(The x_k -- and hence also the b_k -- depend implicitly
on n. x_k is the coefficient of a^k in the polynomial
obtained by expanding the base-a level-2 complete
hereditary representation of n.)