TREE(3) is an extremely large number that requires ordinal arithmetic to prove it is finite. For what value of n would $G(n)>TREE(3)$? The length of the Goodstein sequence $G(n)$ is how many numbers in the sequence beginning with n are traversed in reaching 0. Proving that $G(n)$ is finite for all n also requires ordinal arithmetic and I'm more familiar with the Goodstein sequence.
For $n\ge8$, an $\omega^{\omega+1}$ sequence of decreasing ordinals is required to describe the Goodstein sequence and $G(12)$ is greater than Graham's number. For $G(16)$; $n\ge16$ a sequence beginning with $\omega^{\omega^\omega}$ iteration is required, and numbers that large are difficult to imagine even in terms of Graham's number type iterations. $G(65536)$ requires $\omega\uparrow\uparrow 4$ iteration.
How large a value of n would be required so that $G(2\uparrow\uparrow n)>TREE(3)$? I chose the $2\uparrow\uparrow n$ notation on the assumption that using $G(n)>TREE(3)$ might require an extremely large value for $n$.
I found this How large is TREE(3)? post on mathoverflow.net, which should be useful in putting a lower bounds on the answer to this question, but I'm still trying to understand the post on mathoverflow. A partial answer with the lower bounds answer would also be appreciated!
I also found this related mathstack question giving a lower bound for Kruskal's weak tree function, which along with the wikipedia TREE(3) article may give a lower bounds for this answer.
EDIT: The Fast-growing hierarchy along with another Tree(n) mathstack question provides a possible answer. Here is the Goodstein sequence written exactly in terms of the fast growing hierarchy; hopefully my notation here is correct:
- $G(4)=f_3(3)-2$
- $G(8)=f_{\omega+1}(3)-2$
- $G(16)=f_{\omega^\omega}(3)-2$
- $G(2\uparrow\uparrow n) = f_{\omega\uparrow\uparrow(n-1)}(3)-2$
The mathoverflow Tree3 link gives this inequality:
TREE(3) $\geq H_{\vartheta (\Omega^{\omega}, 0)}(n(4))$
Based on the links, the Fast-growing hierachy can be written in term's of Hardy's H function but I don't understand the $\Omega^\omega$ notation term in the inequality. The implication seems to be that *more * layers of diagonalization are required and perhaps $TREE(3) > G(2\uparrow \uparrow n)$ for any value of n that could possibly be written down!
Yes, and this should not be surprising! Using the fast-growing hierarchy with fundamental sequences defined as in the reference below at Footnote(2), we have, for all $n\gt 2,$ $$G(2\uparrow\uparrow n) = f_{\omega\uparrow\uparrow(n-1)}(3)-2 \lt f_{\epsilon_0}(n)$$
whereas$^\dagger$
$$TREE(3) \gt f_{\epsilon_0+1}(k) $$ where $k$ is Graham's number. (Using $\epsilon_0+1$ here is an extremely conservative choice.)
If $n^*$ denotes the least $n$ s.t. $G(2\uparrow\uparrow n)>TREE(3),$ then $n^*$ must be greater than the least $n$ s.t. $$f_{\epsilon_0}(n)\gt f_{\epsilon_0+1}(k)=f_{\epsilon_0}^{k}(k), $$ i.e., $$n^* \gt f_{\epsilon_0}^{k-1}(k).$$
The decimal digits of Graham's number $k$ are already impossible to "write down", let alone doing so for the digits of $\underbrace{f_{\epsilon_0}(f_{\epsilon_0}(\dots f_{\epsilon_0}(k)\dots ))}_{k-1 \text{ applications of } f_{\epsilon_0}}.$
NB: The cited references prove (rigorously) that $TREE(3) > f_{\Gamma_0}(k).$ Thus $f_{\epsilon_0}(n^*)\gt f_{\Gamma_0}(k),$ from which we could derive much stronger results of the form $n^*>f_{\epsilon_0}^{-1}f_{\Gamma_0}(k);$ but nothing stronger than our very weak bound is needed to answer your question.
$^\dagger$ This extremely weak lower bound is proved by combining the following two facts that are established at the cited links:
(1) https://mathoverflow.net/a/95588/20307: $$TREE(3) \gt tree(n(4))\gt tree(5)$$
(2) https://recursion-theory.blogspot.com/2020/05/lower-bounds-for-tree4-and-tree5.html: $$tree(5) > f_{\Gamma_0}(\text{Graham's number}) \gt f_{\epsilon_0+1}(\text{Graham's number}) $$