5
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ One approach would be: if $A$ and $B$ are incomprehensibly large, and you have a hunch that $A < B$, try come up with some $A'$ and $B'$ so that $A \leq A' < B' \leq B$ and for which it is easier to prove that $A' < B'$. In you example, you could, say, replace $S$ with some incomprehensibly large power of $3$ larger than $S$; that should be easier to compare to the real $g_{64}$. (I think the number you describe is smaller than Graham's number.) $\endgroup$ – Lynn Jan 6 '16 at 23:59
  • $\begingroup$ @Mauris Interesting idea, but I don't think it will always work... $\endgroup$ – Simply Beautiful Art Jan 7 '16 at 0:07
  • 3
    $\begingroup$ What do you expect from an answer, then? :) There is no approach that will "always work". $\endgroup$ – Lynn Jan 7 '16 at 0:27
  • $\begingroup$ @Mauris I just want to see all the different ways we could do it. I assume your method is not the only way. $\endgroup$ – Simply Beautiful Art Jan 7 '16 at 0:38
  • 2
    $\begingroup$ I want to explain that my vote to close is because of the second part of this question. If the question were just about the comparison of $G$ to $S^{S^{S^\cdots}}$ you'd be fine, but "how do we compare large numbers" is a hopelessly broad question. I would recommend narrowing the scope to that particular case, or to simular cases $\endgroup$ – Stella Biderman Jan 7 '16 at 5:56
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ ah thanks, fixed. $\endgroup$ – Deedlit Jan 17 '16 at 19:17
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Thank you, and it is indeed at $G_1$ or maybe $G_2$ where it becomes obvious that Graham's number is much larger, but this doesn't work for anything else. I'll edit my question. $\endgroup$ – Simply Beautiful Art Jan 7 '16 at 22:31
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I've looked it up, thank you for your idea. $\endgroup$ – Simply Beautiful Art Jan 7 '16 at 22:23
0
$\begingroup$

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.

|cite|improve this answer
$\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.