1

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.

Ryder Rude
  • 1,417
  • 2
    In "googology" (the "theory of the large numbers"), we consider numbers to be "approximately equal", if they lie in the same level in the fast-growing hierarchy. The level of $TREE(3)$ is unimaginably higher than that of Graham's number. Hence iterated up-arrow operations have virtually no effect.We still land in the same level. The usual considerations like ratios or the number of digits do not apply here. – Peter Apr 10 '20 at 16:03
  • 1
    Even Graham's number cannot be distinguished from its square. It is so large, that squaring has no significant effect. Even Graham^Graham is not much larger than Graham. – Peter Apr 10 '20 at 16:06
  • @Peter Thanks I'll read up Fast Growing Hierarchy. So they're not really close in the usual sense, but close has a different meaning here. – Ryder Rude Apr 10 '20 at 16:17
  • Yes, they are not close in the usual sense, of course. – Peter Apr 10 '20 at 16:25
  • @Peter It doesn't make sense to talk about the place of a number in the fast-growing hierarchy of functions. One informal way to compare two numbers $x,y$ via the fast-growing hierarchy would be to say that the smallest-rank "natural" function which yields something $>x$ on a "small" input has bigger rank than the smallest-rank "natural" function which yields somethign $>y$ on a "small" input. But of course that's subjective. – Noah Schweber May 18 '20 at 17:30

1 Answers1

2

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.

Simply Beautiful Art
  • 74,685
  • Re: your final paragraph, it doesn't make sense to talk about the place of a number in the fast-growing hierarchy of functions. One informal way to compare two numbers $x,y$ via the fast-growing hierarchy would be to say that the smallest-rank "natural" function which yields something $>x$ on a "small" input has bigger rank than the smallest-rank "natural" function which yields somethign $>y$ on a "small" input. But of course that's subjective. I don't really think it can be made formal here, at least not in a really satisfying way. – Noah Schweber May 18 '20 at 17:31
  • Yes, as with most of the discussion here, the number itself is not what matters, but the functions involved, in which case it can be made more formal. Alternatively, I would actually prefer hierarchies that are increasing in both arguments for this reason, where an argument on specific numbers being placed somewhere can actually be made. – Simply Beautiful Art May 19 '20 at 13:05