# Ackermann function and $f_\omega$

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.

-

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.

-
Oh, that's nice. If possible, please email me a copy of your thesis once it is done. – Andrés E. Caicedo Aug 23 '13 at 14:23