3
$\begingroup$

Which is the minimal number k, so that

$f_{\omega+1}(n) > G_n$ is true for all $n\ge k$ ?

For the definition of $f_{\omega+1}$ see Wikipedia: fast growing hierarchy

$G_n$ is defined by

$$G_0 = 4$$

$$G_{n+1} = 3 \uparrow^{G(n)} 3$$ for all $n\ge 0$. $\uparrow$ stands for knuth's up-arrow notation

I found the following upper bounds :

$$f_{\omega+1}(n) > [n,n,1,2] > n \rightarrow n \rightarrow (n-1) \rightarrow 2 >> G(n-2)$$ for $n\ge 3$

[n,n,1,2] means Bowers Arrow notation and $\rightarrow$ stands for conways arrow chain notation.

At n = 64, G(n) is catched up. So $k \le 64$

$\endgroup$
5
$\begingroup$

The inequality is true if and only if $n \ge 5$.

We will use the fact that

$$2 \uparrow^{m-1} (n+1) < f_m(n) < 2 \uparrow^{m-1} (2n)$$

for $m \ge 3, n \ge 2$. This of course implies that for $n \ge 3$,

$$2 \uparrow^{n-1} (n+1) < f_{\omega}(n) < 2\uparrow^{n-1}(2n)$$

Let $g(n) = 3\uparrow^n 3$. Then if $x > y, x\ge 3$,

$$f_\omega(x) > 2\uparrow^{x-1}(x+1) > 3\uparrow^{x-1}(x-1) \ge 3\uparrow^y y = g(y)$$

By induction we have $f_\omega^k(x) > g^k(y)$ for all $k$. So for $n > 4$,

$$f_{\omega+1}(n) = f_\omega^n(n) > g^n(4) = G(n)$$

On the other hand, if $x \le y, x \ge 3$,

$$f_\omega(x) < 2\uparrow^{x-1}(2x) < 2\uparrow^{x-1}(2\uparrow^{x-1}4) = 2\uparrow^x 4 < 3\uparrow^x 3 \le 3\uparrow^y 3 = g(y)$$

So

$$f_{\omega+1}(3) = f_\omega^3(3) < g^3(4) = G(3)$$

The cases $n=0,1,2$ can be directly computed:

$$f_{\omega+1}(0) = 0 < G(0) = 4$$ $$f_{\omega+1}(1) = 2 < G(1)$$ $$f_{\omega+1}(2) = f_\omega(f_\omega(2)) = f_\omega(8) = f_8(8) < G(2)$$


Okay, you probably want a proof of $2 \uparrow^{m-1} (n+1) < f_m(n) < 2 \uparrow^{m-1} (2n)$.

The left inequality is straightforward by induction:

$f_2(n) = n * 2^n \ge 2^{n+1}$, for $n \ge 2$.

$f_{k+1}(n) = f_k(f_k(\ldots(f_k(n))\ldots)) > 2\uparrow^{k-1}(2\uparrow^{k-1}(\ldots(2\uparrow^{k-1}(n+1))\ldots)) > 2\uparrow^k (n+1)$ for $n \ge 2$.

The right inequality is much more problematic, because of the "little bit extra" that $f_k$ has over Knuth arrow notation. We will require some lemmas.

Lemma 1. $a^b + c < a^{b+\frac{c}{a^b \log a}}$.

Proof: $a^b + c = a^b(1+\frac{c}{a^b}) = a^{b + \log_a (1+\frac{c}{a^b})} = a^{b + \frac{\log(1+\frac{c}{a^b})}{\log (a)}} < a^{b+\frac{c}{a^b \log a}}$.

Corollary 1. If $a^b \log a > 1, a^b+c < a^{b+c}$.

Let $E(n,a,b) = a^{a^{\cdots^{b}}}$, with n a's and one b.

Corollary 2. If $a^b \log a > 1, E(n,a,b)+c < E(n,a,b+c)$.

Proof: By induction on n.

Corollary 3. If $a^b \log a > 1, E(n,a,b)+c < E(n,a,b + \frac{c}{E(n,a,b)})$.

Proof: $E(n,a,b)+c = a^{E(n-1,a,b)}+c < a^{E(n-1,a,b + \frac{c}{E(n,a,b)})}$ (by Lemma 1) $ < a^{E(n-1,a,b+\frac{c}{E(n,a,b)})}$ (by Corollary 2) $ = E(n,a,b+\frac{c}{E(n,a,b)})$.

Lemma 2. $f_2^m(n) < E(m,2,2n+m-1)$.

Proof: By induction. $f_2(n) = n*2^n < 2^{2n} = E(1,2,2n)$.

$f_2^{m+1}(n) = f_2(f_2^m(n)) < f_2(E(m,2,2n+m-1)) < 2^{2E(m,2,2n+m-1)} = 2^{2^{E(m-1,2,2n+m-1)+1}}$

$ < 2^{2^{E(m-1,2,2n+m)}}$ (by Corollary 2) $= E(m+1,2,2n+m)$.

So $f_3(n) = f_2^n(n) < E(n,2,3n-1) < E(n,2,E(n,2,1)) = 2\uparrow\uparrow(2n)$.

Finally the general case. Let $E(m,n,a,b) = a \uparrow^n (a\uparrow^n(\ldots(a\uparrow^n b)\ldots))$. Assume $f_m(n) < 2\uparrow^{m-1}(2n)$.

Lemma 3. $f_m^k(n) < E(k,m-1,2,2n+k-1)$.

Proof: By induction. $f_m(n) < 2\uparrow^{m-1}(2n) = E(1,m-1,2,2n)$.

$f_m^{k+1}(n) = f_m(f_m^k(n)) < f_m(E(k,m-1,2,2n+k-1)) < E(1,m-1, 2, 2E(k,m-1,2,2n+k-1)) < E(1,m-1,2,E(k,m-1,2,2n+k)) = E(k+1,m-1,2,2n+k)$.

So $$f_{m+1}(n) = f_m^n(n) = E(n,m-1,2,3n-1) < E(n,m-1,2,E(n,m-1,2,1)) = E(2n,m-1,2,1) = 2 \uparrow^m (2n)$$

and we are done.

$\endgroup$
  • $\begingroup$ To state the case for $n=4$ in the first part, you probably want to write $f_{\omega+1}(4) = f_\omega^4(4) < g^4(4) = G(4)$ just before the line $f_{\omega+1}(3) = f_\omega^3(3) < g^3(4) = G(3)$. $\endgroup$ – r.e.s. Apr 27 '14 at 20:16
  • $\begingroup$ I will have to work through the answer, but thank you very much! $\endgroup$ – Peter Apr 28 '14 at 13:25
  • $\begingroup$ In the proof of corollary 3, there are two identical expressions with a "<" between. $\endgroup$ – Peter May 5 '14 at 20:58

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.