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

Question

When numbers get as large as Graham's number, or somewhere around the point where we can't write them as numerical values, how do we compare them?

For example:

$$G>S^{S^{S^{\dots}}}$$

Where $G$ is Graham's number and $S^{S^{S^{\dots}}}$ is $S$ raised to itself $S$ times and $S$ is Skewes number.

It appears obvious (I think) that Graham's number is indeed larger, but how does one go about proving that if both numbers are "so large" that they become hard to compare?

More generally, how do we compare numbers of this general size?

As a much harder problem than the above, imagine a function $G(x,y)$ where $G(64,3)=$ Graham's number. The function $G(x,y)$ is as follows:

$$G(x,y)=y\uparrow^{(G(x-1,y))}y$$

Where $G(0,y)$ is given.

I ask to compare $G(60,S)$ and $G(64,3)$

Answer 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)$.

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

Answer 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.

Answer 4

Perhaps, as an idea, we could compare the growth rates of the functions that make our large numbers.

Imagine you were comparing two numbers that were given as $G=g(x)$ and $S=s(y)$.

You compare the growth rates and then, if $x$ is somewhat close to $y$, the function with more growth rates produces the bigger number.

If $x<y$ but $g(x)$ grows faster than $s(y)$, it gets messy.