explicit upper bound of TREE(3)

6.5k Views Asked by At

TREE(3) is the famously absurdly large number that is the length of a longest list of rooted, 3-colored trees whose $i$th element has at most $i$ vertices, and for which no tree's vertices can be mapped to the vertices of a subsequent tree preserving color and inf relationships.

Some lower bounds of TREE(3) have been proven. Among them are $A^{A(187196)}(1)$, where the superscript denotes function iteration and $A(x) = 2\uparrow^{x-1}x$ (using Knuth up-arrows) is a version of the Ackermann function. More bounds appear in this Wikia article and here. These bounds are rather unsatisfying because there is no indication of how tight they are.

The only upper bound of TREE(3) that I have seen (other than, trivially, TREE($n$) for $n > 3$) has a similar derivation as a longest sequence of a more general type of graph; I can't find a reference at the moment. This upper bound is also unsatisfying because it is non-constructive.

Does anyone know of an explicit expression that is an upper bound of TREE(3)? Or is it so large that there is no hope to construct one?

2

There are 2 best solutions below

3
On BEST ANSWER

$\ TREE(3)\ $ is far above the $\Gamma_0$-level of the fast growing hierarchy.

See here how insane large it is : https://sites.google.com/site/largenumbers/home/appendix/a/numbers3

I am not sure whether an upper bound is known. Nested Ackermann-functions do not come near to $\ TREE(3)\ $ at all. Conway chains and even Bowers's $3D$-arrays are still MUCH MUCH MUCH too small.

1
On

We could express TREE(3) using BAN for information on ban see here TREE(n), and maybe even SCG(n). The updated function S(n) grows far faster than TREEs and SCGs (assuming there FGH levels are correct). Which S(n), is on the limit of BAN. The other upper bound we could use is the FGH,