In what sense would Graham’s tree be virtually the same as TREE(3)

big numbers

How Big would "Graham's Tree" be?

I'm coming off this post which asks about the size of the number which we would obtain by replacing the 3's in Graham's number construction by TREE(3).

The first answer there mentions that it'd be pretty much the same as TREE(3). I don't understand that response. We say that two numbers are relatively the same when the ratio of their absolute difference divided by one of the numbers is really small.

This works for the analogy given in the answer (adding 1 to a googolplex barely changes anything). But if we use TREE(3) in constructing Graham's number instead of 3, then it'll surely produce a number which is orders of magnitudes above TREE(3). So in what sense is the answer saying that it'll be not much distinguishable from TREE(3)?

Even $TREE^2(3)$ will contain double the digits of TREE(3) and should not be considered close to TREE(3) in the usual sense.

Best Answer

While it is true that one is much larger than the other in that we have $G_{\operatorname{TREE}(3)}-\operatorname{TREE}(3)$ being large, a linear scaling such as this is not very useful for comparing large numbers.

A simpler analogy would be $10^{1,000,000,000,001}$ and $10^{1,000,000,000,000}$. Although we have their difference being as big as $9\times10^{1,000,000,000,000}$, it probably does not seem like one is "significantly" bigger than the other.

One way to clarify what is meant here is by considering how the numbers are constructed, rather than the numbers themselves. When viewed from this perspective, it is clear to see that $10^{1,000,000,000,001}$ and $10^{1,000,000,000,000}$ are "made" the same way.

On the other hand, something such as $10^{10^{10^{10}}}$ is significantly larger than $10^{1,000,000,000,000}$ because it uses repeated exponentiation, which is far larger than just exponentiation.

In the same way, one could argue that

$$^{1,000,000,000,001}10=10^{10^{10^{.^{.^.}}}}\bigg\}1,000,000,000,001\text{ powers of }10$$

is not significantly larger than

$$^{1,000,000,000,000}10=10^{10^{10^{.^{.^.}}}}\bigg\}1,000,000,000,000\text{ powers of }10$$

Going back to our first example, one number was simply $10$ times larger than the other. In general, after a certain point, multiplying by $10$ is not significant. After a certain point, exponentiating one more time is not significant either. After a certain point, $G_n$ is not significantly larger than $n$.


To be more precise about how far one has to go for something to be considered insignificantly larger, we used in our examples:

$f(n)$ is not significantly larger than $n$ when $n\ge\underbrace{f(f(f(\dots f(}_{1,000,000,000,000}k)\dots)))$, for fast growing functions $f$ and some sufficiently large $k$, say $k=10$.

This is, of course, very informal. Another way we could try to formulate this is with the fast growing hierarchy, as Peter mentioned, which can be made more formally.