Lower bounds for tree(4) and tree(5)

H. Friedman's finite miniaturization of Kruskal's tree theorem

Hey, guys. You like large numbers, don't you?

Today's topic is about a huge number related to Kruskal's tree theorem in graph theory. This is an important theorem that leads to Nash-Williams' BQO theory, Robertson–Seymour's graph minor theorem, and so on.

Kruskal's tree theorem is, of course, a theorem about trees. A tree is a connected acyclic graph. A rooted tree is a tree with a distinguished vertex called a root. A rooted tree can be thought of as a lower semilattice. A sequence of rooted finite trees $T_1,T_2,\dots,T_\ell$ is called bad if there is no infimum-preserving injection from $T_i$ to $T_j$ whenever $i\lt j$.

Kruskal's tree theorem states that the length of a bad sequence of rooted finite trees must be finite.

Okay, that's good to know. It's finite. So, how large is this finite number? How long can a bad sequence be?

The answer is ... unimaginably large. A mathematical logician, Harvery Friedman, introduced the following number:

Definition. The number ${\bf tree}(n)$ is defined as the length of a longest bad sequence of rooted trees where the $i$th tree $T_i$ in this sequence has at most $n+i$ vertices.

Friedman found that this yields extraordinary huge numbers. For instance, it is known that:

${\bf tree}(3)$ is greater than $10000000000$.

And,

${\bf tree}(4)$ is greater than Graham's number.

Here, Graham's number is known as "the largest number ever used in a serious mathematical proof" which is published in the 1980 Guinness Book of World Records.

We can do a little better: \[{\bf tree}(4)>f_{\varepsilon_0}(\text{Graham's number}),\] where $f_{\varepsilon_0}$ is the $\varepsilon_0$th fast growing function in the Wainer hierarchy. And \[{\bf tree}(5)>f_{\Gamma_0}(\text{Graham's number}),\] where $f_{\Gamma_0}$ is the $\Gamma_0$th fast growing function with respect to the canonical system of fundamental sequences below the Feferman-Shütte ordinal $\Gamma_0$. A rigorous proof of the above inequalities is attached in the bottom of this blog article.

Not to be confused with the famous ${\bf TREE}(3)$, which is a different number defined by using labeled finite trees. The number ${\bf TREE}(3)$ is far larger than ${\bf tree}(\text{Graham’s number})$.

Where is the proof?

You can find a huge number of blog articles and videos in both English and Japanese mentioning that TREE(3) is extremely huge.

So, where is the proof?

Most articles just say that "TREE(3) is big! TREE(3) is sooooo big! TREE(3) is supersuper big! That's it! We omit the proof." That's good. I like that kind of article. But, where can I find the proof?

Even the best articles only reduce the largeness of TREE(3) to the growth rate of ${\bf tree}(x)$, and say that the growth rate of ${\bf tree}(x)$ is known to be comparable to $f_{\vartheta(\Omega^\omega)}$, where $\vartheta(\Omega^\omega)$ is the small Veblen ordinal. However, as of 16 May 2020, none of the articles contain any links to references to this known fact at all, and indeed, there does not seem to be any reference of this in the world. Well, perhaps, it might be obtained from the fact that the rank of bad sequences of finite trees is the small Veblen ordinal.

But some of them say that the growth rate of ${\bf tree}(x)$ is roughly about that of $f_{\vartheta(\Omega^\omega)}$ w.r.t. a system of fundamental sequences obtained from the structure of slow bad sequences of finite trees (and others just say that ${\bf tree}(x)$ is roughly about $f_{\vartheta(\Omega^\omega)}$ without mentioning fundamental sequences. In this case, even what they're claiming is unclear). If the system is different from the canonical one, what will happen doesn't seem so self-evident to me, particularly when taking a specific finite number $x$ as an input.

To avoid confusion, instead of $f_\alpha$, let's use $t_\alpha$ to denote the fast growing hierarchy along this specific system of fundamental sequences, and for example, consider the following extremely-super-super-trivial inequality: \[t_{\vartheta(\Omega^\omega)}(10^{10^{100}})>f_{\omega+1}(64).\] However, if our system of fundamental sequence is different from the canonical one, it seems to take some effort even to prove the above super-super-trivial inequality. Some has claimed $t_\alpha(n)\geq H_\alpha(n)$ (e.g., here), but no one in the world had even mentioned the idea of proof.

Perhaps, it may be obvious to experts, of course, how to give a rigorous proof, but there does not seem to be a written complete proof that links all the necessary information together, at least in the context of tree functions (in partucular, about the claim that the growth rate of $t_\alpha$ is (almost) comparable to $f_\alpha$). Fortunately, at least for some of the inequalities described above, giving a rigorous proof is not so difficult, so I'd like to present the complete proof here.

Summary

Recall that Graham's number is a specific small natural number less than $f_{\omega+1}(64)$, where $f_{\omega+1}$ is the $(\omega+1)$st fast growing function, which grows faster than the Ackermann function.

In the pdf below, we give a rigorous proof of the following inequality: \[{\bf tree}(4)>f_{\varepsilon_0}(\text{Graham's number}),\] where $f_{\varepsilon_0}$ is the $\varepsilon_0$th fast growing function in the Wainer hierarchy. A similar argument also shows that \[{\bf tree}(5)>f_{\Gamma_0}(\text{Graham's number}),\] where $f_{\Gamma_0}$ is the $\Gamma_0$th fast growing function with respect to the canonical system of fundamental sequences below the Feferman-Shütte ordinal $\Gamma_0$. (Indeed, $\Gamma_0$ in the above inequality can be replaced with the Ackermann ordinal $\vartheta(\Omega^3)$)

(Note: The pdf below contains a rigorous proof of the whole part, but the main part that I cared most about is the proof of the (folklore?) claim that the growth rate of the non-canonical fast-growing function $t_\alpha$ introduced above is (almost) comparable to the canonical fast-growing function $f_\alpha$.)

Lower bounds for tree(4) and tree(5)

I don't claim the novelty of the results presented in this note, but I’m writing this in the hope that writing down the proof in detail will be helpful to others.