Graham's number closest power of two

Question

Using Knuth's up-arrow notation, Graham's number $G$ is defined as $$ G=g_{64},\,\,\, \text{ where }g_1=3\uparrow\uparrow\uparrow\uparrow 3 \text{ and } g_n=3\uparrow^{g_{n-1}}3. $$ I was wondering if it's possible to know what is the power of two, $H$, that is closest to $G$.

My initial idea was to construct it in a similar way, that is, $$ H=h_{64},\,\,\, \text{ where }h_1=2\uparrow\uparrow\uparrow\uparrow 2 \text{ and } h_n=2\uparrow^{h_{n-1}}2, $$ which is a power of two. However, something tells me it should be a bigger number. For instance, is it true that $h_{65}>G$?

Answer 1

Unfortunately, any up-arrow of $2$'s expands as $$ 2 \uparrow^n 2 = \underbrace{2 \uparrow^{n-1} \dots \uparrow^{n-1} 2}_{\text{2 times}} = 2 \uparrow^{n-1} 2 $$ and so eventually we just get to $2 \uparrow 2 = 2^2 = 2\cdot 2 = 2 + 2 = 4$. So your definition of $h_{64}$ is not all that big: we just get $H = h_{64} = 4$.

(Graham and Rothschild's original paper starts with $h_1 = 2 \uparrow^{12} 3$ and then iterates $h_n = 2 \uparrow^{h_{n-1}} 3$, ending with $h_7$, to get the upper bound they need. Putting a $3$ at the end avoids the cancellation we see in $2 \uparrow^n 2$. But this $h_7$ is actually much smaller than $G$.)

There is not likely to be a great expression for the closest power of $2$ to $G$. The sequence $g_1, g_2, g_3, \dots$ grows so quickly that it is not too misleading to say that $G$ and $2^G$ are "basically the same" - they are very close on the scale that we're considering! We definitely have $2^{g_{63}} < G < 2^{g_{64}}$, and the second inequality is much closer than the first.

Answer 2

In a sense, one might say something such as

$$10^{100}+1\approx10^{100}$$

in the sense that if we tried to write the left side as $10^x$, $x$ would have to differ from $100$ by about $10^{-100}$, which is extremely insignificant.

In the same manner, one might say things such as

$$2^{2\uparrow\uparrow10^{100}}=2\uparrow\uparrow(10^{100}+1)\approx2\uparrow\uparrow10^{100}$$

in the sense that this is basically the closest way we can write the result compactly.

Following this line of thought, we would then have

$$2\uparrow^n2\uparrow^{n+1}k\approx2\uparrow^{n+1}k$$

for sufficiently large values of $k$, and by induction, the reasonable interpretation of

$$2^G\approx G$$

meaning that $G$ is the "closest" we can get to $\operatorname{lg}(G)$ by using digits and uparrows in a compact form.