Ackermann function and $f_\omega$

Question

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.

Answer 1

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.

Answer 2

Generally, when one compares functions to the fast growing hierarchy, we say that a function $g(n)$ grows at $f_\alpha(n)$ if $g(n)$ grows faster than $f_\beta(n)$ for every $\beta<\alpha$ and $g(n)$ grows slower than $f_\alpha^k(n)$ for a fixed $k$. For functions/notations that come with multiple arguments, we diagonalize, for example,

$$g(n)=\chi(n,n,n,\dots,n)$$

Basically, replace every argument of the function with $n$ and call that $g(n)$.

Formally, we may define

$$g(n)\in f_\alpha(n)\iff\exists k\in\mathbb N\forall\beta<\alpha\exists0<N\forall n>N\text{ s.t. }g(n)>f_\beta(n)\land g(n)<f_\alpha^k(n)$$

Particularly here, all one needs to show is that

$$f_k(n)\ll A(n,n)\ll f_\omega(n)$$

Under this definition, you will find that every eventually monotonically increasing function can find a place on the fast growing hierarchy, and that there are simple properties, for example:

$$g(n)\in f_\alpha(n)\implies\begin{cases}g^k(n)\in f_\alpha(n)\\g^n(n)\in f_{\alpha+1}(n)\end{cases}$$

So repeatedly nesting Ackermann functions a fixed amount of times does not take you further down the fast growing hierarchy, instead, you need to nest the function a non-constant (and increasing) amount of times.