Is there some standard way to make the "roughly comparable" to more precise form? I would like to understand the claim better.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I discuss this in some detail in my paper
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.
(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
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.