4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Ross Millikan May 28 '16 at 22:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan May 28 '16 at 22:56
  • 1
    $\begingroup$ Saibian approximates it as $\{10,\{10,10,3^{27}\},1,2\}$. I will write a longer answer soon. $\endgroup$ – wythagoras May 29 '16 at 19:07
  • 1
    $\begingroup$ 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. $\endgroup$ – r.e.s. May 30 '16 at 21:55
  • 1
    $\begingroup$ (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.) $\endgroup$ – r.e.s. May 30 '16 at 22:36
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Peter May 31 '16 at 13:49
  • $\begingroup$ What about my claim that $$googolplum<G(G(2))$$, where $G(n)$ is the Graham-function ? $\endgroup$ – Peter May 31 '16 at 19:28
  • $\begingroup$ @Peter - Your claim is correct. I've added a proof. $\endgroup$ – r.e.s. Jun 1 '16 at 1:33
  • $\begingroup$ @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. $\endgroup$ – r.e.s. Jun 1 '16 at 1:38
  • $\begingroup$ So, we have $G(G(1))<googolplum<G(G(2))$ (The lower bound is mentioned in my second link) $\endgroup$ – Peter Jun 1 '16 at 11:21
3
$\begingroup$

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

$\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.