# Large numbers

1. Jun 19, 2013

### Mentallic

I'd like to discuss numbers at "orders of magnitude" around Graham's number.

If any readers haven't heard of this number but are curious to follow, you'll first need to understand Knuth's[/PLAIN] [Broken] up arrow notation and then read up on Graham's[/PLAIN] [Broken] number.

My question is, since Graham's number ($G=g_{64}$) is essentially a very large power tower of 3's, can we replace the 3's with a larger (but relatively small) number such that we get a new number $H=h_{63}>G$. So for example, let the larger number be a googol, so
$$\newcommand\up{\mathbin{\uparrow}}$$
$$g_0=h_0=4$$
and
$$g_{n}=3\hspace{1 mm}\underbrace{\up\dots\up}_{g_{n-1}} \hspace{2 mm}3,\hspace{5 mm}n>0$$
$$h_{n}=10^{100}\hspace{1 mm}\underbrace{\up\dots\up}_{h_{n-1}} \hspace{2 mm}10^{100},\hspace{5 mm}n>0$$

So clearly $h_{63}>g_{63}$ but can we relate $h_{63}$ to $g_{64}$? The number of up arrows are by far the most powerful operator in $a\up\dots\up b$, so I'd guess $g_{64}$ is larger, but I can't prove it.

A naturally extension to the question could also be what size the number needs to be such that $h_{63}>g_{64}$.

Last edited by a moderator: May 6, 2017
2. Jun 20, 2013

### Deedlit

Okay, for convenience I will use $a c$ for $a\underbrace{\uparrow\dots\uparrow}_{b} c$ when there are a lot of up arrows.

I will start by proving that $3 \uparrow\uparrow b+3 > 10^{100} \uparrow\uparrow b$ for all $b \geq 1$. I will in fact prove the stronger statement
$3 \uparrow\uparrow b+3 > (10^{100} \uparrow\uparrow b)^2$, using induction.

Case $b=1$: $3 \uparrow\uparrow 4 = 3^{3^{27}} > 3^{600} = 27^{200} > 10^{200} = (10^{100} \uparrow\uparrow 1)^2$.

Now assume the statement is true for b, and prove it for b+1.

$$3 \uparrow\uparrow b+4 = 3^{3 \uparrow\uparrow b+3} > 3^{(10^{100} \uparrow\uparrow b)^2} = (3^{10^{100} \uparrow\uparrow b})^{10^{100} \uparrow\uparrow b} \geq (3^{10 ^ {100}})^{10^{100} \uparrow\uparrow b}$$
$$> (10^{10^{99}})^{10^{100} \uparrow\uparrow b} > (10^{200})^{10^{100} \uparrow\uparrow b} = ((10^{100})^{10^{100} \uparrow\uparrow b})^2 = (10^{100} \uparrow\uparrow b+1)^2.$$

Next, we will prove that $3 \uparrow\uparrow\uparrow b+2 > (10^{100} \uparrow\uparrow\uparrow b)+4$ for $b \geq 1$. We will use induction again.

Case $b = 1$:
$3 \uparrow\uparrow\uparrow 3 \geq 3 \uparrow\uparrow 4 > 10 ^ {100}$

Next, we assume the statement for b, and prove it for b+1.

$$3\uparrow\uparrow\uparrow b+3 = 3 \uparrow\uparrow (3\uparrow\uparrow\uparrow b+2) > 3 \uparrow\uparrow ((10^{100} \uparrow\uparrow\uparrow b) + 4) \text{(by induction)}$$
$$> 10^{100} \uparrow\uparrow (10^{100} \uparrow\uparrow\uparrow b+1) \text{(by the previous proposition)} \geq (10^{100}\uparrow\uparrow\uparrow b+1) + 4.$$

Next, we have $3 [a] b+1 > (10^{100} [a] b) + 3$ for $a \geq 4, b \geq 1$.
We will prove it using double induction and a and b.

Case $b=1$:
$$3 [a] 2 \geq 3 [4] 2 = 3 \uparrow\uparrow\uparrow 3 > 3 \uparrow\uparrow 4 > 10^{100}.$$

Next assume that statement is true for (4, b), and we prove it for (4, b+1).
$$3 [4] b+2 = 3 [3] (3 [4] b+1) > 3 [3] ((10^{100} [4] b) + 3) > 10 ^ {100} [3] ((10^{100} [4] b) + 1)$$
$$> 10^{100} [3] (10^{100} [4] b) + 3 = (10^{100} [4] b) + 3.$$

Finally we prove the statement for (a+1, b+1), given that it is true for (a+1, b) and (a, x) for any x.

$$3 [a+1] b+2 = 3 [a] (3 [a+1] b+1) > 3 [a] ((10^{100} [a+1] b) + 3) > 10 ^ {100} [a] ((10^{100} [a+1] b) + 2)$$
$$> 10 ^{100} [a] (10^{100} [a+1] b) + 3 = 10 ^{100} [a+1] (b+1) + 3.$$

Next, we have $3 [a+1]3 > 10^{100} [a] 10^{100}$ for $a \geq 3$.
Indeed, $3 [a+1] 3 = 3 [a] (3 [a] 3) > 3 [a] (10^{100} + 2) > 10^{100} [a] 10^{100}$.

So $h_n < g_{n+1}$, since $h_0 = 4 < 3 [4] 3 = g_1$, and if $h_n < g_{n+1}$, then
$$h_{n+1} = 10^{100} [h(n)] 10^{100} < 3 [h(n)+1] 3 \leq 3[g_{n+1}] 3 = g_{n+2}$$.

Last edited: Jun 20, 2013