# Where does googolplum lie in the fast growing hierarchy?

Here :

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 :

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.

• Using $**$ for exponentiation comes from computer languages such as FORTRAN. We would deprecate it in favor of ^ For numbers like this, you want powers of uparrow as you have done. – Ross Millikan May 28 '16 at 22:50
• I haven't seen the use of more than $2$ stars. I didn't find it in the article you linked to. Whoever uses it should define it. Maybe it is three uparrows, with two stars converting to one uparrow. – Ross Millikan May 28 '16 at 22:56
• Saibian approximates it as $\{10,\{10,10,3^{27}\},1,2\}$. I will write a longer answer soon. – wythagoras May 29 '16 at 19:07
• The binary hyperoperations are sometimes denoted by choosing to repeat the symbol for an operation that precedes $\uparrow$, i.e. repeating $*$ or $+$. Thus, $$(+,*,\uparrow,\uparrow\uparrow,\uparrow\uparrow\uparrow,...)= (+,\ *,\ **,\ ***,\ ****,\ ...)=(+, ++, +++, ++++, +++++, ...).$$ So $n$ "$\uparrow$"s means the same as $n+1$ "$*$"s or $n+2$ "$+$"s. The "$*$" version is described in the OP's first linked paper, in the section on the Ackermann function. – r.e.s. May 30 '16 at 21:55
• (cont'd) Therefore, the number of steps you describe is $(10^{100})\uparrow^{3^{27}-2} (10^{100}) = (10^{100}){*}^{3^{27}-1} (10^{100})$. (That is, $3^{27}-1$ is the number of stars, so the number of uparrows is one less than that.) – r.e.s. May 30 '16 at 22:36

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])

• Nice, and it coincides with the fact that $f_{\omega+2}(3)\approx 3\rightarrow 3\rightarrow 3\rightarrow 3$, and the conway chain already exceeds googolplum. – Peter May 31 '16 at 13:49
• What about my claim that $$googolplum<G(G(2))$$, where $G(n)$ is the Graham-function ? – Peter May 31 '16 at 19:28
• @Peter - Your claim is correct. I've added a proof. – r.e.s. Jun 1 '16 at 1:33
• @Peter - BTW, your post still needs to have the uparrow-count ${3^{27}-1}$ corrected. It should be ${3^{27}-2}$, as explained in my earlier comment. – r.e.s. Jun 1 '16 at 1:38
• So, we have $G(G(1))<googolplum<G(G(2))$ (The lower bound is mentioned in my second link) – Peter Jun 1 '16 at 11:21

$$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}))$$