How do we compare the size of numbers that are around the size of Graham's number or larger?

Solution 1:

Basically you want to construct a chain of inequalities that links the smaller expression to the larger expression. Induction is often helpful in these cases.

A useful theorem for Knuth arrows is $(a \uparrow^n b) \uparrow^n c < a \uparrow^n (b+c)$, proven in this paper. It is also proven that $a \uparrow^n c$ is monotonic in $a,n$, and $c$ when $a,c \ge 3$, which is useful as well.

For example, one can easily see that $S < 3 \uparrow\uparrow 6$, so

$$S^{S^{S^\cdots}} = S \uparrow \uparrow S < (3\uparrow\uparrow 6)\uparrow\uparrow(3 \uparrow\uparrow 6) < 3\uparrow\uparrow (6 + 3\uparrow\uparrow 6) < 3 \uparrow\uparrow (3 \uparrow\uparrow 7) < 3 \uparrow\uparrow (3\uparrow\uparrow 3^{3^3}) = 3 \uparrow\uparrow (3\uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow 4 < 3\uparrow\uparrow\uparrow (3 \uparrow\uparrow\uparrow 3) = 3\uparrow\uparrow\uparrow\uparrow 3 = G_1$$

To address your harder question, first we need to know what $G(0,y)$ is. Since we need $G(0,3) =4$ so that $G(64,3)$ is Graham's number, I will assume that $G(0,y)=4$.

Theorem: $G(n,S) < G(n+1,3)$

We will prove this by induction. First, observe that $G(0,S) = 4 < 3\uparrow\uparrow\uparrow\uparrow 3 = G(1,3)$.

Observe that for $n \ge 3$,

$$S \uparrow^n S < (3\uparrow\uparrow 6)\uparrow^n (3\uparrow\uparrow 6) < (3\uparrow^n 6)\uparrow^n (3\uparrow\uparrow 6) < 3\uparrow^n (6+3\uparrow\uparrow 6) < 3\uparrow^n (3\uparrow\uparrow\uparrow 3) \le 3\uparrow^n (3\uparrow^n 3) = 3\uparrow^{n+1} 3$$

So if we have $G(n,S) < G(n+1,3)$, then $G(n,S)+1 \le G(n+1,3)$, so

$$G(n+1,S) = S \uparrow^{G(n,S)} S < 3 \uparrow^{G(n,S)+1} 3 \le 3 \uparrow^{G(n+1,3)} 3 = G(n+2,3)$$

and the theorem follows by induction.

So in particular, $G(60,S) < G(61,3) < G(64,3)$.

Solution 2:

It is difficult to describe the magnitude of Graham's number.

With power towers , it is hopeless to describe it because the height of the power tower would have a comparable magnitude.

Already a number like $3 \uparrow^{10} 3$ is much larger than the given number constructed by Skewes number. This is because every arrow is an additional level of recursivity. $G(2)=3\uparrow^{3\uparrow^4 3} 3$ is already horribly large, but absolutely tiny compared to Graham's number.

With the fast-growing hierarchy, you get that Graham's number is comparable to $f_{\omega+1}(64)$, whereas the number $\ S\uparrow S\uparrow... \uparrow S\ \ $ will not even reach $f_\omega(10)$.

To demonstrate how large $G(2)$ already is :

Denote $M=3\uparrow \uparrow \uparrow 3$

M is a power tower of $3's$ with height $3^{27}$.

Step $1$ : $N_1=3$

Step $2$ : $N_2=$ A power tower with $N_1=3$ $3's$ $=3^{27}$.

Step $3$ : $N_3=$ A power tower with $N_2$ $3's$$=M$.

Step $4$ : $N_4=$ A power tower with $N_3$ $3's$.

Continue, until you reach step $M$. Then, you have $G(1)$ , already huge!

$G(2)$ is $3\uparrow^k 3$, where $k=G(1)$

We well beat the number $\ S\uparrow S\uparrow ...\uparrow S\ \ $ already at Step $4$.

Solution 3:

Look up "large number contest".

In general, it is far easier to come up with methods for describing large numbers than it is to compare two such numbers.