# When does $f_{\omega+1}$ catch up the $G_n$-sequence?

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$

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.

• 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)$. – r.e.s. Apr 27 '14 at 20:16
• I will have to work through the answer, but thank you very much! – Peter Apr 28 '14 at 13:25
• In the proof of corollary 3, there are two identical expressions with a "<" between. – Peter May 5 '14 at 20:58