2
$\begingroup$

Here :

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

Deedlit mentions that for natural $m,n\ge 2$ and natural $k>n+log_2(n)$ , we have $$2\uparrow^{m-1}n<f_m(n)<2\uparrow^{m-1} k$$

The left inequality can be proven by induction. But what about the right inequality ? How can I bound $2\uparrow^{m-1} k$ in a way that induction can be applied ? Or do I need another idea ?

$\endgroup$
  • 1
    $\begingroup$ Interesting. Never seen the RH inequality before either... Very interesting though! $\endgroup$ – Brevan Ellefsen Jun 1 '16 at 15:54
  • $\begingroup$ Although hyperoperations satisfy a similar recursion, for the FGH it is not correct that $s(m,n+1)=f_m(n+1)=f_{m-1}(f_m(n))=s(m-1,s(m,n))$, because $f_m(n+1)=f_{m-1}^{n+1}(n+1) = f_{m-1}( f_{m-1}^{n}(n+1)) \neq f_{m-1}(f_m(n))$. $\endgroup$ – r.e.s. Jun 1 '16 at 23:04
  • $\begingroup$ @r.e.s. You are right, I will have to delete my idea ... $\endgroup$ – Peter Jun 2 '16 at 10:25
  • $\begingroup$ On second thought ... In the recursion theory literature there's another version of the FGH (not mentioned on the WP page) that's actually defined to satisfy a similar recursion. For finite indices, it's defined by $F_0(n):=n+1,\ F_{m+1}(0):=F_m(1),\ F_{m+1}(n+1):=F_{m}(F_{m+1}(n))$, which is the same as $F_0(n):=n+1,\ F_{m+1}(n):=F_{m}^{n+1}(1)$. This version is described on p.2 of [this article]. $\endgroup$ – r.e.s. Jun 6 '16 at 4:40
  • $\begingroup$ @r.e.s. This version could be easier compared with up-arrows or Conway-chains, but I think it is not the one usually used. $\endgroup$ – Peter Jun 6 '16 at 8:44
3
$\begingroup$

So we will prove that for $m \ge 2, n \ge 3$, $f_m(n) \le 2\uparrow^{m-1}\lceil n + \log_2(n) + 1\rceil$.

Base case $m=2$: $f_2(n) = n 2^n = 2^{n+\log_2(n)} \le 2 \uparrow \lceil n + \log_2(n) + 1\rceil$.

Inductive step:

We assume that $f_m(n) \le 2\uparrow^{m-1}\lceil n + \log_2(n) + 1 \rceil \le 2 \uparrow^{m-1}(2n)$.

Lemma. For $m,n \ge 1$, $2\uparrow^m (n+2) > 2(2\uparrow^m n) + 2$.

Proof of Lemma: $2\uparrow^m(n+2) = 2 \uparrow^{m-1} (2 \uparrow^{m-1} (2\uparrow^m n)) \ge 2 \uparrow^0 (2\uparrow^0 (2\uparrow^m n)) = 4(2\uparrow^m n) > 2(2\uparrow^m n) + 2$ QED

Let $g(n) = 2 \uparrow^{m-1} n$ and $h(n) = 2 \cdot 2\uparrow^{m-1}(n)$. Then the Lemma is equivalent to $g(n+2) > h(n)+2$.

Lemma 2. $f_m^i(n) < h^i(2n)) < g^i(2n+2)$.

Proof: $$g^i(2n+2) = g^{i-1}(g(2n+2)) > g^{i-1}(h(2n)+2) > g^{i-2}(h^2(2n)+2) > g^{i-3}(h^3(2n)+2) > \ldots > h^i(2n) > f_m^i(n)$$

QED

Lemma 3. $2n+2 < 2 \uparrow^m \lceil \log_2(n) + 1\rceil$ for $m \ge 2, n \ge 3$.

Proof of Lemma 3: It suffices to prove the case $n = 2^k$, which reduces the lemma to

$$2 \cdot 2^k + 2 < 2 \uparrow^m ( k + 1)$$

Base case $k=2$: $2 \cdot 2^2 + 2 = 10 < 2\uparrow\uparrow 3 \le 2\uparrow^m 3$.

Inductive step:

$$2\uparrow^m(k+2) = 2\uparrow^{m-1}(2\uparrow^m(k+1)) \ge 2(2\uparrow^m(k+1)) > 2(2^{k+1}+2) = 2^{k+2} + 4 > 2^{k+2} + 2$$

QED

So, $$f_{m+1}(n) = f_m^n(n) < g^n(2n+2) <g^n(2\uparrow^m \lceil \log_2(n)+1\rceil) = 2\uparrow^m \lceil n+ \log_2(n) + 1 \rceil$$

$\endgroup$

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.