Where does googolplum lie in the fast growing hierarchy?

Question

Here :

https://sites.google.com/site/largenumbers/home/3-2/andre_joyce

Saibian presents the largest number coined by Andre Joyce, googolplum.

It should lie at the $f_{\omega+2}$-level in the fast growing hierarchy, but where exactly ?

In other words :

Between which tight bounds does googolplum lie ? Is it really at level $f_{\omega+2}$ ?

If yes, what is the smallest number $n$, such that $f_{\omega+2}(n)$ is bigger than googolplum ?

The construction of googolplum works as follows :

Start with $10**100$, where $**$ stands for exponentiation. This is step $1$. In step $2$, we have $10**\cdot\cdot\cdot**10\ $ with $10**100=googol$ stars. In step $3$, we have $10**\cdot\cdot\cdot**10\ $ with as many stars as given by the number in step $2$. Continue in this manner until step

$$(10^{100})\uparrow^{3^{27}-2} (10^{100})$$ is reached.

Here :

https://sites.google.com/site/largenumbers/home/appendix/a/numbers2

Saibian gives bounds for googolplum. It should be less than $G(G(2))$.

I did not get the meaning of the stars, so I have difficulties to determine the size of the number. I think it has something to do with up-arrow-notation but then I do not understand why $**$ stands for exponentiation.

Answer 1

Defining $$f(x):=10\uparrow^{x-1}100,$$ we have $$\mathrm{googolplum} =f^N(2) ,$$ where $$N = (10^{100})\uparrow^{3^{27}-2} (10^{100}).$$

Here's a proof (sketch) that

$$f_{\omega+2}(2) < \mathrm{googolplum} < f_{\omega+2}(3)\tag{*}. $$

For the inequality on the left in $(*)$: $$f_{\omega+2}(2) = f_{\omega+1}^2(2) = f_{\omega+1}(a) = f_\omega^a(a) < (f^2)^\left\lfloor{\frac{N}{2}-1}\right\rfloor f^2(2) \le f^N(2) $$ where $a=f_{\omega+1}(2)=f_\omega^2(2)=f_\omega f_2(2)=f_8(8) \lt \left\lfloor{\frac{N}{2}-1}\right\rfloor \lt f^2(2)$, and we've used the following fact: $$f_\omega(n) < f^2(n) \text{ for all } n\ge 2\tag{1}.$$

For the inequality on the right in $(*)$: $$f_{\omega+2}(3) = f_{\omega+1}^3(3)=f_{\omega+1}(b) = f_\omega^b(b) \ge (f_\omega^2)^{\left\lfloor\frac{b}{2}\right\rfloor}(b) > f^N(2) $$ where $b = f_{\omega+1}f_\omega^3(3)\gg 2N $, and we've used the following fact: $$f_\omega^2(n)>f(n) \text{ for all } n\ge 2\tag{2}.$$ QED

---

NB: Defining the "Graham's number functions"$$ g(x):= 3\uparrow^x 3,\text{ and } G(n):= g^n(4)$$ (so Graham's number is $G(64)$), the claim that $$\text{googolplum }<G^2(2)$$ can be proved correct as follows:

First, consider the following function (which is everywhere larger than googolplum's $f(x)$): $$\phi(x):= (10^{100})\uparrow^{x-1}(10^{100}) > f(x)$$ and note that $$\begin{align} 3\uparrow^x 3 &= 3\uparrow^{x-1}3\uparrow^{x-1}3 \\ &\ge 3\uparrow^{x-1}(3\uparrow^3 3),\quad x\ge4\\ &>(3\uparrow^{x-1}3)\uparrow^{x-1}(3\uparrow^3 3 - 3),\quad x\ge4\quad\text{(by Saibian's theorem)}\\ &>(3\uparrow^3 3)\uparrow^{x-1}(3\uparrow^3 3 - 3),\quad x\ge4\\ &>(10^{100})\uparrow^{x-1}(10^{100}),\quad x\ge4\\ \therefore\ g(x)&>\phi(x)>f(x),\quad x\ge4.\\ \end{align} $$ and also that $$N = (10^{100})\uparrow^{3^{27}-2} (10^{100}) < (10^{100})\uparrow^{10^{100}-1} (10^{100}) = \phi(10^{100}) < g(10^{100}) < g(3\uparrow^4 3) $$ Therefore, $$\begin{align} \text{googolplum } &:= f^N(2)<\phi^N(4)< g^N(4) < g^{g(3\uparrow^4 3)}(4)=g^{g(g(4))}(4)=G(g(g(4)))=G(G(2)). \end{align} $$ QED

(ref: Saibian's theorem [see T1])

Answer 2

I will adopt r.e.s.'s terminology

$$N = (10^{100}) \uparrow^{3^{27}-2} (10^{100})$$

and

$$f(n) = 10\uparrow^{n-1} 100$$

so that

$$\text{googolplum} = f^N(2).$$

We will prove

$$f_{\omega+1}(N-2) < \text{googolplum} < f_{\omega+1}(N-1)$$

To prove this we will use (without proof) the inequalities

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

We prove the right inequality by proving $f_{\omega}^i(N-1) > f^{i+1}(2)$ by induction.

Base case: $N-1 > f(2) = 10^{100}$.

Inductive step: If $f_{\omega}^i(N-1) > f^{i+1}(2)$, then $$f_{\omega}^{i+1}(N-1) = f_{\omega}(f_\omega^i(N-1)) > f_\omega(f^{i+1}(2)) > 2 \uparrow^{f^{i+1}(2)-1}(f^{i+1}(2)+1) > (2\uparrow^{f^{i+1}(2)-1} 3)\uparrow^{f^{i+1}(2)-1}(f^{i+1}(2) - 2) \lbrace \text{by Saibian's Theorem}\rbrace > 10\uparrow^{f^{i+1}(2)-1}100 = f^{i+2}(2)$$ QED

Substituting $i = N-1$ produces the right inequality.

For the left inequality, we prove $f_{\omega}^i(N-2) < f^{i+2}(2)$ also by induction.

Base case: $N-2 < f(f(2)) = 10 \uparrow^{10^{100}-1} 100$.

Inductive step: If $f_{\omega}^i(N-2) < f^{i+2}(2)$, then

$$f_{\omega}^{i+1}(N-2) = f_\omega(f_{\omega}^{i+1}(N-2)) \le f_{\omega}(f^{i+2}(2)-1) < 2\uparrow^{f^{i+2}(2)-1} 4 < 10 \uparrow^{f^{i+2}(2)-1} 100 = f(f^{i+2}(2)) = f^{i+3}(2)$$ QED

and we get the left inequality by substituting $i = N-2$.

If you wish to get rid of Knuth arrows entirely, observe that

$$f_\omega(3^{27}-1) < 2\uparrow^{3^{27}-2}(2 \cdot 3^{27})< N-2 < N-1 < 2\uparrow^{3^{27}-1}(3^{27}+1) < f_\omega(3^{27})$$

so that

$$f_{\omega+1}(f_\omega(3^{27}-1)) < \text{googolplum} < f_{\omega+1}(f_\omega(3^{27}))$$