2
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.