# What are sharp lower and upper bounds of the fast growing hierarachy?

With fast growing hierarchy, I mean the Wainer hierarchy, which starts with

$$f_0(n)=n+1$$ $$f_1(n)=2n$$ $$f_2(n)=2^n n$$

A lower bound for $f_m(n)$ is $2 \uparrow^{m-1} n$.

If $f(n,m):=2 \uparrow^{m-1}n$ and $g(n,m):=f_m(n)$, is it true that $$f(n,m) < g(n,m) < f(n+1,m)$$ for all $m,n\ge 2$ ?

If not, what is the least k such that $$f(n,m) < g(m,n) < f(n+k,m)$$ for all $m,n\ge 2$ ?

The next inequality I found is $f_{\omega+m}(n)>[n,n,m,2]$ , where the square brackets denote bowers linear array notation. Is there a similar inequality chain as above ?

## 2 Answers

The answer to your first question is no. For the second, there is no k that satisfies the inequality chain.

For example, take m = 2:

$$f(n,2) = 2^n n = 2^{n + \log n} \approx g(n + \log n, 2)$$

For m = 3, we have $f(n,3) > 2 \uparrow 2 \uparrow 2 \ldots \uparrow n$, and $n \approx 2 \uparrow \uparrow \log_* n$, so

$$f(n,3) \approx 2 \uparrow \uparrow (n + \log_* n) \approx g(n + \log_* n, 3)$$

and of course $\log_* n$ will eventually exceed any constant k.

More generally, for fixed m let h(n,m) be the number-theoretic inverse of f(n,m). Then

$$f(n,m) > 2 \uparrow^{m-1} 2 \uparrow^{m-1} \ldots n \text{ with n up arrows } \approx 2 \uparrow^m (n + h(n,m)) = g(n + h(n,m), m)$$

and h(n,m), while extremely slow growing, will still eventually consant k, unfortunately. So the best we can do is something like

$$f(n,m) < g(n,m) < f(2n,m)$$

which is true for all $m,n \ge 2$, and is reasonably provable. With additional work you could replace $2n$ with $n + \lceil \log n \rceil$.

For your chain inequality, one has $$f_{\omega+m}(n) > n \rightarrow n \rightarrow (n-1) \rightarrow (m+1)$$

You can use your inequality between FGH and Bowers' array notation in combination with Birds proof to prove this.

• Does this inequality hold for all $m\ge 1,n\ge 2$ ? – Peter Aug 19 '15 at 8:05