Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Wikipedia page of Ackermann function states that Ackermann function is "roughly comparable" to $f_\omega$ in fast-growing hierarchy.

Is there some standard way to make the "roughly comparable" to more precise form? I would like to understand the claim better.

share|improve this question
add comment

1 Answer

up vote 3 down vote accepted

I discuss this in some detail in my paper

Andres E. Caicedo, Regressive functions on pairs, European Journal of Combinatorics, 31 (3), (2010), 803–812. MR2587031 (2011e:05270),

but the results are more or less folklore, so I do not include details there (but they are not hard). Anyway, as mentioned in section 2, say that a function $f:\mathbb N\to\mathbb N$ is (precisely) of Ackermannian growth iff there are constants $c,C>0$ such that for all but finitely many $m$, we have $$f_\omega(cm)\le f(m)\le f_\omega(Cm). $$ Similarly, say that a function's rate of growth is like that of the $n$th level of the Ackermann hierarchy iff there are constants $c,C>0$ such that for all but finitely many $m$, we have $$A_n(cm)\le f(m)\le A_n(Cm).$$ (Here, $A_n(m)=A(n,m)$.)

This is similar to the notion of Ackermannic functions, in the sense defined in the book Ramsey theory by Graham, Rothschild, and Spencer (Section 2.7), which is probably the most easily available reference that discusses related matters.

We have:

Lemma. $1.$ For all $n$, $A_n <A_{n+1}$ (pointwise) and $f_n<^∗f_{n+1}$ (that is, in the sense of eventual domination: From some point on). In fact, for any $C>0$ and almost all $m$, $A_n(Cm)< A_{n+1}(m)$ for $n>0$, and $f_n(Cm)<f_{n+1}(m)$ for all $n$.

$2.$ For all $n>0$, $A_{n+1}<^∗f_n$ and $f_n(m)<A_{n+1}(cm)$ for some constant $c=c_n$, and all $m$.

$3.$ $f_\omega$ and $\mathrm{Ack}$, (the diagonal function, $\mathrm{Ack}(n)=A_n(n)$) are of Ackermannian growth.

$4.$ If $f$ is of Ackermannian growth, it eventually dominates each primitive recursive function. In particular, it eventually dominates each $f_n$.

$5.$ If $f$ is of Ackermannian growth, then it is eventually dominated by $f_{\omega+1}$.

$6.$ There is a function $f$ that eventually dominates each $f_n$ and is eventually dominated by $f_{\omega +1}$, but is not of Ackermannian growth.

$7.$ If $g,h$ are strictly increasing primitive recursive functions, and $f$ is of Ackermannian growth, then $g\circ f$ is of Ackermannian growth, and $f\circ h<^* f_{\omega+1}$.

(Most of the items in this list can be significantly strengthened.) One question the above does not address is whether functions that eventually dominate all primitive recursive functions are of Ackermannian growth or higher. This is actually not the case, and is discussed at length in the paper

Harold Simmons. The Ackermann functions are not optimal but by how much?, J. Symbolic Logic, 75 (1), (2010), 289–313. MR2605895 (2011j:03099).

The reason why the comparison came about is that in my paper I identified a natural combinatorial problem that gives us a function of Ackermannian growth. This may well be the first example of such a thing. The problem came from an earlier result of Kanamori and McAloon in Ramsey theory that is true but nor provable in Peano Arithmetic. The result depends on a parameter $k$, and the case $k=2$ is the one giving rise to the Ackermannian function.

share|improve this answer
    
Wow, thank you. Its a funny coincidence that I've been studying the Kanamori-McAloon paper for my thesis and I wondered the parameter $k$. (I also studied and cited your paper about Goodstein function - it was fun to read!) –  rank Aug 23 '13 at 7:05
    
Oh, that's nice. If possible, please email me a copy of your thesis once it is done. –  Andres Caicedo Aug 23 '13 at 14:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.