# Growth rate of $f(f(n))$, where $f(n)$ is the ackermann-function.

Let $$f(n)\ :=\ n \uparrow^n n$$

and $$g(n)\ :=f(f(n))\ =\ f(n)\uparrow ^{f(n)} f(n)=n\uparrow^n n \uparrow^ {n \uparrow ^n n} n\uparrow ^n n$$

So, $g(n)$ is $f(n)$ applied twice.

• What is the growth rate of $g(n)$ ?
• How can I estimate $g(n)$ (I search an upper and a lower bound in terms of conway-chain-notation and entries not much larger than n) ?

$f(n)$ is simply $n\rightarrow n \rightarrow n$ and $g(n)$ should be upperbounded by a conway chain with $4$ moderate entries and perhaps even a chain with $3$ moderate entries. But it is very difficult to compare the values of conway chains in general.

I tried to manipulate $(n \rightarrow n\rightarrow n)\rightarrow (n\rightarrow n\rightarrow n)\rightarrow (n\rightarrow n\rightarrow n)$, but the first entry is very large, and I do not know how to compare this with a chain with a moderate first entry.

A simple upper bound which is easy to prove (for $n>2$) would be: $$U=(n→2→3→2)$$

Using the definition of Conway arrow notation, we get: $$U = n↑^{{n↑^{n↑2}}2}2 = n↑^{{n↑^{(n↑2-1)}}n}2= n↑^{{n↑^{(n↑2-1)}}n-1}n$$

Since ${{n↑^{(n↑2-1)}}n-1}$ is clearly bigger than $n↑^{n}n$, we get that $U>g(n)$.

But we can tighten the bound even further.

Let us pick some $k$, such that $k^2-3>n$. I propose that the number $$V=(k→2→3→2)$$ is larger than $g(n)$.

Proving it formally is tricky, but I can show you why this has to be so. We calculate $V$:

$$V = k↑^{{k↑^{k↑2}}2}k = k↑^{{k↑^{(k↑2-1)}}k}k > k↑^{{k↑^{(n+2)}}k}k$$.

With numbers of such magnitudes, the first and final $k$ are irrelevant (as long as k>2). Only the number of arrows matters, when comparing thw two numbers. The number of arrows in $V$ is:

$${k↑^{(n+2)}}k$$

While the number of arrows in $g(n)$ is:

$${n↑^{n}}n$$

Using the same argument again, we find the number of arrows in "the number of arrows of $V$" is $n+2$ while we the number of arrows in "the number of arrows of $g(x)$" is $n$. And since $n+2>n$ we get that $V>g(x)$

In conclusion, a reasonable upper bound for $g(n)$ is:

$$V(n)=(1+[\sqrt{n+3}])→2→3→2$$

For example:

$$g(10)<(4→2→3→2)$$ $$g(100)<(11→2→3→2)$$

BTW, while the above anlysis works only for $n>2$, the inequality $V(n)>g(n)$ happens to hold for $n=2$ as well:

$$V(2)=3→2→3→2 = 3↑^{3↑^{8}2}2 > 4↑↑↑↑4 = g(2)$$