Graham's Number on the Next Layer And TREE(3)

Question

We all know how we calculate Graham's number. If you don't, a quick google search will familiarise you with the notation used and the G() function that is used. Now I learnt about Graham's number from Numberphile which is probably where that Google search should have redirected you by now. We obviously also know (from Numberphile) how off the scale if TREE(3). "It absolutely puts Graham's number to shame" is said in the video. But my question is: we know Graham's number is G(64). Let's upgrade it and go to G(65). Is it bigger than TREE(3)? No? Let's upgrade it again. At what point would G(n)>TREE(3). And an even more interesting question (for which I don't expect an answer) at what point is G(n)>TREE(x)? (x,n are natural and bigger than 0.)

Answer 1

In this answer I'll assume that $\uparrow^k$ stands for $k$ up-arrows, $G(0)=4$, $G(n+1)=3\uparrow^{G(n)}3$, superscript denotes function iteration, and that the definition of the fundamental sequence of $\omega$ is $\omega[n]=n$.

The $\textrm{tree}$ function is defined similarly to the $\textrm{TREE}$ function, except there is only one color of node, and the node count restriction is relaxed some: the $i$th tree in a sequence for $\textrm{tree}(n)$ is no longer required to have at most $i$ nodes, but at most $n+i$ nodes. (This function is still very fast-growing.)

To show how much larger $\textrm{TREE}(3)$ is than Graham's function applied to any familiar integer, here is a descent from $\textrm{TREE}(3)$:

• Math StackExchange answer #320162 contains a sequence for $\textrm{TREE}(3)$ that's of length longer than $\textrm{tree}_3(\textrm{tree}_2(\textrm{tree}(8)))$, where $\textrm{tree}_3(n)=\underbrace{\textrm{tree}_2(\ldots(\textrm{tree}_2}_n (n)\ldots)$ and $\textrm{tree}_2(n)=\underbrace{\textrm{tree}(\ldots(\textrm{tree}}_n (n)\ldots)$.
• $\textrm{tree}$ itself has large outputs for small inputs, for example in the note "Lower Bounds for $\textrm{tree}(4)$ and $\textrm{tree}(5)$" by T. Kihara it's shown that $\textrm{tree}(5)$ is greater than $f_{\Gamma_0}(G(64))$, where $f$ is the fast-growing hierarchy, and $\Gamma_0$ is the Feferman-Schütte ordinal.
• $f_{\Gamma_0}(G(64))$ is already far larger than $f_{\omega+3}(G(64))$, which itself is larger than many iterations of Graham's construction. To be specific, $f_{\omega+3}(G(64))$ is larger than $G^{G^{G^{G(64)}(0)}(0)}(0)$, as shown below.

---

Comparing the fast-growing hierarchy with up-arrow notation

Lemma 1: For all $n\geq 1$, $f_2(2n)>3\uparrow n$.

Proof: $f_2(2n)=2n\cdot 2^{2n}=2n\cdot 4^n$, and this is greater than $3^n$ for $n\geq 1$. $\square$

Corollary 1: For $k,n\geq 1$, $f_2^k(2n)>\underbrace{3\uparrow 3\uparrow\ldots 3\uparrow}_{k\;\uparrow\;\textrm{applications}}n$.

Lemma 2: For all $n\geq 2$, $f_3(n)>\log_2(3)\cdot(3\uparrow\uparrow n)$.

Proof: By induction on $n$: If $n=2$, then $f_3(n)=f_2(f_2(2))=f_2(8)=2048$, which is greater than $3\uparrow\uparrow 1=3$. Now assume this is proven for some $n>2$. To prove this for $n+1$, $f_3(n+1)$ is equal to $f_2^{n+1}(n+1)$ by definition, which is equal to $f_2(f_2^n(n+1))$ or $f_2^n(n+1)\cdot 2^{f_2^n(n+1)}$. This is greater than $2\cdot 2^{f_2^n(n)}$, which by definition of $f_3$, is in turn equal to $2\cdot 2^{f_3(n)}$. Since $f_2^n(n)>(3\uparrow\uparrow n)\cdot\log_2(3)$, $2\cdot 2^{f_2^n(n)}$ is greater than $2\cdot 2^{(3\uparrow\uparrow n)\cdot\log_2(3)}=2\cdot 3^{3\uparrow\uparrow n}=2\cdot 3\uparrow\uparrow(n+1)$. Since $2$ is greater than $\log_2(3)$, $f_3(n+1)$ is greater than $\log_2(3)\cdot(3\uparrow\uparrow(n+1))$. $\square$.

Corollary 2: $f_3(n)>3\uparrow\uparrow n$. In general, for $k,n\geq 1$, $f_3^k(n)>\underbrace{3\uparrow\uparrow 3\uparrow\uparrow\ldots 3\uparrow\uparrow}_{k\;\uparrow\uparrow\;\textrm{applications}}n$.

Lemma 3: For all $m\geq 3$ and $n\geq 2$, $f_m(n)>3\uparrow^{m-1} n$.

Corollary 3 for $m$: For $k,n\geq 1$ and $m\geq 3$, $f_m^k(n)>\underbrace{3\uparrow^{m-1} 3\uparrow^{m-1}\ldots 3\uparrow^{m-1}}_{k\;\uparrow^{m-1}\;\textrm{applications}}n$.

Proof: We prove both lemma 3 and corollary 3 for each $m\geq 3$ this by induction on $m$, with a subsidiary induction on $n$ at each step.

The base cases of $m=3$ are almost the same as those in lemma 2 and corollary 2. When $m>3$, the proof is very similar, also by induction on $n$: If $n=2$, then $f_m(n)=f_{m-1}(f_{m-1}(2))$ is greater than $3\uparrow^{m-1} 2=3\uparrow^{m-2} 3\uparrow^{m-2} 1$. Assume this is proven for $n>1$. $f_m(n+1)$ is at least $f_{m-1}^n(n)$, and by corollary 3 for $m-1$, $f_{m-1}^n(n)>\underbrace{3\uparrow^{m-2} 3\uparrow^{m-2}\ldots 3\uparrow^{m-2}}_{n\;\uparrow^{m-2}\;\textrm{applications}}n$, which is at least $\underbrace{3\uparrow^{m-2} 3\uparrow^{m-2}\ldots 3\uparrow^{m-2}}_{n-1\;\uparrow^{m-2}\;\textrm{applications}}3$ or $3\uparrow^{m-1} n$.

At each step of the induction, corollary 3 for $m$ follows from lemma 3 for $m$ in the same way that corollaries 1 and 2 follow from lemmas 1 and 2. $\square$

This lets us compare up-arrow notation with the finite-indexed functions in the fast-growing hierarchy. Once we begin to consider $f_\alpha$ for transfinite $\alpha$, this will let us get bounds on Graham's number and the iterated Graham construction, but some more work is needed. Specifically, we start out by upper-bounding $G(1)=3\uparrow\uparrow\uparrow\uparrow 3$ by $f_5(4)$, and for any $k\geq 1$, $G(k+1)$ is upper-bounded by $f_{G(k)+1}(4)$. There is an extra $+1$ that appears in the index of the fast-growing hierarchy, but we will see that the following numbers are so large that these are subsumed in the process of upper-bounding the iterated Graham construction.

Lemma 4: For $n>1$, $f_\omega(G(n)+1)>G(n+1)$.

Proof: $f_\omega(G(n)+1)=f_{G(n)+1}(G(n)+1)>f_{G(n)+1}(3)$, which by lemma 3 is greater than $3\uparrow^{G(n)}3=G(n+1)$. $\square$

Theorem 5: For $n>0$, $f_{\omega+1}(n+1)>G(n)$.

Proof: By strong induction on $n$. If $n=1$, then $f_{\omega+1}(2)=f_\omega(f_\omega(2))=f_\omega(8)=f_8(8)>3\uparrow^7 3$ is greater than $G(1)$. Assume this has been proven for all values of $n$ up to the current one. Then $f_{\omega+1}(n+2)=f_\omega(f_\omega^n(n+2))>f_\omega(f_\omega^n(n+1))=f_{f_\omega^n(n+1)}(f_\omega^n(n+1))$. Since $f_\omega^n(n+1)>f_\omega^n(n)+1$ and the latter is equal to $f_{\omega+1}(n)+1$, then $f_{f_\omega^n(n+1)}(f_\omega^n(n+1))$ is greater than $f_{f_{\omega+1}(n)+1}(f_\omega^n(n+1))$. From the induction hypothesis, this is greater than $f_{G(n)+1}(f_\omega^n(n+1))$, which by decreasing the argument is greater than $f_{G(n)+1}(3)$, which by lemma 3 is greater than $3\uparrow^{G(n)}3$. $\square$

A better bound $f_{\omega+1}(n)>G(n)$ for sufficiently large $n$ could be obtainable with more work.

So $f_{\omega+1}(65)$ is greater than $G(64)$. However to show the much larger size of $\textrm{TREE}(3)$, the goal was to bound an iterated Graham construction.

Iterating theorem 5:

Corollary 6: For $n>0$ and $k>0$, $f_{\omega+1}^k(n+1)>G^k(n-k)$.

Theorem 7: For $n>0$, $f_{\omega+2}(n)>G^n(0)$.

Proof: $f_{\omega+2}(n)=f_{\omega+1}^n(n)$, then apply corollary 6 with $k=n$. $\square$

To complete the comparison we show that $f_{\omega+3}(G(64))>G^{G^{G^{G(64)}(0)}(0)}(0)$. $f_{\omega+3}(G(64))=f_{\omega+2}^{G(64)}(G(64))$, which is equal to $f_{\omega+2}(f_{\omega+2}(f_{\omega+2}(x)))$ where $x$ stands for $f_{\omega+2}^{G(64)-3}(G(64))$. Since $x$ is far larger than $G(64)$, this number is greater than $f_{\omega+2}(f_{\omega+2}(f_{\omega+2}(G(64))))$. Applying theorem 7 once shows this is greater than $f_{\omega+2}(f_{\omega+2}(G^{G(64)}(0)))$, applying twice more shows this is greater than $G^{G^{G^{G(64)}(0)}(0)}(0)$ as desired.

Much stronger lower bounds can be obtained than just three layers of this iterated $G$ construction, since the $3$ in $G(64)-3$ can be greatly increased. The comparisons in this section only utilized the levels $f_\alpha$ of the fast-growing hierarchy for $\alpha\leq\omega+3$, while much further levels such as $f_{\Gamma_0}$ appear in the estimation of $\textrm{TREE}(3)$.