Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation denotes iteration). But actually, using the fast-growing hierarchy, $n(p)$ is smaller than $f_{\omega^{\omega^\omega}}(p)$, shown by Friedman in
- Long finite sequences, Journal of Combinatorial Theory, Series A 95 Issue 1 (2001) pp. 102-144, doi:10.1006/jcta.2000.3154, author pdf
while it seems that TREE grows faster than $f_{\Gamma_0}$ (${\Gamma_0}$ being the Feferman-Schütte ordinal). So it could well be that in fact TREE(3) is larger than, say, n(n(4)), or even any number expressible by iterations of n. What is known on this question?
For reference, I should have added that TREE(3) is the incredibly (at first, or even second look) large answer to the question : "which is the length of the longest sequence $(T_2,T_3,T_4,\dots,T_n)$ of labeled trees such that $T_k$ has at most $k$ nodes labeled $a$ or $b$, and $T_i$ is not a subtree of $T_j$ for $i < j$ ?".
Here, trees are rooted trees, and are treated as poset on their sets of vertices. A tree $T$ is called a subtree of $T'$ if there is an inf-preserving embedding from $T$ into $T'$, (that is, an injective map $h:Vertices(T) \to Vertices(T')$ such that $h(\inf(x,y)) = \inf((h(x), h(y))$) that respects the labeling by $a$ or $b$.
Best Answer
I believe I can state with some confidence that TREE(3) is larger than $f_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, given a natural definition of $f$ up to $\vartheta (\Omega^{\omega}, 0)$. I can state with certainty that TREE(3) is larger than $H_{\vartheta (\Omega^{\omega}, 0)} (n(4))$, where H is a certain version of the Hardy hierarchy.
To obtain this result, I will first define a version of TREE(n) for unlabeled trees:
Let tree(n) be the length of the longest sequence of unlabeled rooted trees $T_1, T_2, \ldots, T_m$ such that $T_i$ has less than or equal to $n+i$ vertices and for no $i, j$ with $i < j$ do we have $T_i$ homeomorphically embeddable into $T_j$. (Note the term "embeddable" rather than "subtree"; the terms are different, and I believe using "subtree" would lead to infinite sequences.)
In order to obtain a long sequence of trees, we will define a well-order on unlabeled rooted trees. This definition will be by induction on the sum of the heights of the two trees being compared.
Define an immediate subtree of a rooted tree $T$ to be a full subtree starting at one of its children.
Given two rooted trees $S, T$, we define $S = T$ if the two trees are identical. We define $S \leq T$ if $S = T$ or $S < T$.
Given two rooted trees $S, T$, we define $ < $ as follows. Say $S < T$ if $S \leq T_i$, where $T_i$ is an immediate subtree of $T$. Similarly, say $T < S$ if $T \leq S_i$, where $S_i$ is an immediate subtree of $S$.
Otherwise, compare the number of children of $S$ and $T$. If $S$ has more children than $T$, then $S > T$, and vice versa.
Otherwise, suppose $S$ and $T$ both have $n$ children. Let $S_1, S_2, \ldots, S_n$ and $T_1, T_2, \ldots T_n$ be the immediate subtrees of $S$ and $T$ respectively, ordered from smallest to largest. Compare $S_1$ to $T_1$, then $S_2$ to $T_2$, etc., until we get a pair of unequal trees $S_i$ and $T_i$. If $S_i > T_i$ then $S > T$, and vice versa. Of course, of all pairs of immediate subtrees are equal, then $S$ and $T$ will be equal.
This gives a linear order on unlabeled rooted trees, and one can prove that this is a well-order. Further, this well-ordering has order type $\vartheta(\Omega^\omega,0)$. This definition is a modification of a well-ordering of ordered rooted trees due to Levitz, and expounded on in papers by Jervell.
From this well-ordering we can define fundamental sequences for ordinals up to $\vartheta (\Omega^{\omega}, 0)$. Simply put, given an ordinal $\alpha$, let $\alpha[n]$ be the largest ordinal less than $\alpha$ corresponding to a tree of $n$ vertices or less.
From this, we can define our version of the Hardy hierarchy:
$H_0(n) = n$
$H_{\alpha + 1}( n) = H_{\alpha}( n+1)$
For $\alpha$ a limit ordinal, $H_{\alpha}( n) = H_{\alpha[n+1]}( n+1)$
Note the $n+1$'s in the last line - this differs from the usual values of $n$. Of course, this will only make the functions larger.
$H_{\alpha}( n)$ for $\alpha < \vartheta (\Omega^{\omega}, 0)$ is the final index $m$ in the sequence of trees $T_n, T_{n+1}, \ldots, T_m$ where $T_n$ corresponds to $\alpha$ and $T_i$ is the largest tree with at most $i$ vertices that is smaller than $T_{i-1}$, and $T_m$ is the tree with one vertex. Thus $H_{\vartheta (\Omega^{\omega}, 0)}( n)$ will be the final index $m$ in the sequence of trees $T_{n+1}, T_{n+2}, \ldots, T_m$ where $T_{n+1}$ is arbitrary.
Thus tree(n) $\geq H_{\vartheta (\Omega^{\omega}, 0)}( n) - n$.
So where does TREE(3) come in? Harvey Friedman himself explains in a post to the Foundations of Mathematics message boards:
http://www.cs.nyu.edu/pipermail/fom/2006-March/010260.html
In the post he explains why a proof of the theorem "TREE(3) exists" in the theory $ACA_0 + \Pi^1_2\text{-}BI$ must have more than $2\uparrow\uparrow 1000$ symbols. He does this by showing that TREE(3) must be very large - specifically, he constructs a sequence of more than $n(4)$ rooted trees labeled from {1,2,3} such that $T_i$ has at most $i$ vertices, for no $i, j$ with $i < j$ do we have $T_i$ homeomorphically embeddable into $T_j$, and each tree contains either a 2 label or a 3 label. We can obviously continue this with tree($n(4)$) trees with all labels 1. Thus we have
TREE(3) $\geq$ tree$(n(4)) + n(4) \geq H_{\vartheta (\Omega^{\omega}, 0)}(n(4))$
In fact, we can do somewhat better than this; we can replace the $n(4)$ above by $F(4)$, where $F(4)$ is defined as the length of the longest sequence of sequences $x_1, x_2, \ldots x_n$ from {1,2,3,4} such that $x_i$ has length $i+1$ and for no $i,j$ with $i < j$ do we have $x_i$ a subsequence of $x_j$. I can prove much better bounds for $F(4)$ than Friedman's lower bound for $n(4)$; specifically,
$F(4) > f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega + 1}f_{\omega^2 + \omega}f_{\omega^2 + 1}f_{\omega^2 + 1}f_{\omega^2}f_{ \omega + 1}f_{ \omega + 1}f_{\omega}(30)$
But such specificity is perhaps unwarranted given how far from TREE(3) it may be.