# The Ackermann hierarchy vs. the fast growing hierarchy

Suppose we've defined the Ackermann hierarchy as follows:

$$A_\alpha(n)=\begin{cases}n+1,&\alpha=0\\A_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\A_\beta(1),&n=0,\alpha=\beta+1\\A_\beta(A_\alpha(n-1)),&n>0,\alpha=\beta+1\end{cases}$$

Compare this to the fast growing hierarchy:

$$f_\alpha(n)=\begin{cases}n+1,&\alpha=0\\f_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\f_\beta^n(n)=f_\beta(\dots f_\beta(n)\dots),&\alpha=\beta+1\end{cases}$$

It is easy to see that

$$A_0(n)=f_0(n)$$

$$A_{k+1}(n)\ll f_k(n)\ll A_{k+1}^2(n)\quad\forall0<k<\omega$$

$$A_\omega(n)\ll f_\omega(n)\ll A_\omega^2(n)$$

etc.

Using fundamental sequences of the Veblen Hierarchy, is it the case that for $\alpha$ between $\omega$ and the Large Veblen ordinal that we have the following bounds for sufficiently large $n$?

$$A_\alpha(n)\ll f_\alpha(n)\ll A_\alpha^2(n)$$

Both bounds may be proven with induction. Assume that they hold for some $\alpha$ and all sufficiently large $n$. We then have

$$A_\alpha(n)<f_\alpha(n)\implies A_\alpha^n(n)<f_\alpha^n(n)$$

$$A_\alpha(1)<n\implies A_\alpha^n(A_\alpha(1))<f_\alpha^n(n)$$

From here, we can see by induction and definition that

$$A_\alpha^n(A_\alpha(1))=A_{\alpha+1}(n)\\f_\alpha^n(n)=f_{\alpha+1}(n)$$

Since the inequalities hold true for all $\omega\le\beta<\alpha$, they hold true for $\alpha\in\Bbb{Lim}$.

The upper bound is more complicated by follows the same general idea:

$$kn\ll A_{\alpha+1}(n)\quad\forall \alpha\ge\omega$$

$$f_\alpha(n)<A_\alpha^2(n)\implies f_\alpha^{kn}(kn)<A_\alpha^{2kn}(kn)<A_\alpha^{2kn}(A_{\alpha+1}(n))$$

$$\implies f_{\alpha+1}(kn)<A_{\alpha+1}((2k+1)n)\ll A_{\alpha+1}^2(n)$$

This likewise improves the bounds and gives us

$$A_\alpha(n)<f_\alpha(n)\ll A_{\alpha+1}\left(\frac{2k+1}{2k}n\right)$$

For every $k\gg0$ and $n\gg N$.