8
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ $TREE(3)$ is so unimaginably massive, that Nested Ackermann-functions are extremely far from being tight lower bounds. $\endgroup$ – Peter Jun 3 '16 at 21:56
  • $\begingroup$ $A()$ is "a version of", not "the inverse of", the Ackermann function. (Edited) $\endgroup$ – r.e.s. Jun 4 '16 at 3:00
  • $\begingroup$ @r.e.s. Thank you. I get way too little sleep :) $\endgroup$ – Reinstate Monica Jun 4 '16 at 16:39
6
$\begingroup$

$\ 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.

$\endgroup$
  • $\begingroup$ The approximate magnitude of a very large number is determined with the help of the so-called fast growing hierarchy. $\endgroup$ – Peter Jun 3 '16 at 22:30
  • $\begingroup$ We choose a function growing fast enough that applied to a reasonable input, it returns approximately the given number. Look here : en.wikipedia.org/wiki/Fast-growing_hierarchy $\endgroup$ – Peter Jun 3 '16 at 22:31
  • $\begingroup$ For example, Graham's number is approximately $f_{\omega+1}(64)$, so we say that Graham's number is at level $f_{\omega+1}$ , or short at the $\omega+1$-level. $\endgroup$ – Peter Jun 3 '16 at 22:43
6
$\begingroup$

After discussing the problem with Andreas Weiermann, it appears there are no good upper bounds to TREE(3). One can derive a good asymptotic bound to TREE(n) on the order of $F_{\theta(\Omega^\omega \omega,0)}(n)$, however this does not in and of itself prove any bound to TREE(3).

I suppose it seems unlikely, given the asymptotic upper bound for TREE(n), that TREE(3) would exceed say $F_\alpha(3)$ for $\alpha$ much larger than $\theta(\Omega^\omega \omega,0)$, but this is speculative.

$\endgroup$
  • $\begingroup$ As far as I know, it is not known whether $F_{\theta(\Omega^\omega\omega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{\theta(\Omega^\omega\omega,0)}$, so $F_{\theta(\Omega^\omega\omega,0)}(n)$ is just a lower bound (for some version of $F$). I don't know why this would be an (asymptotic) upper bound. $\endgroup$ – wythagoras Oct 22 '16 at 12:45
  • 1
    $\begingroup$ It was proven by Diana Schmidt in her thesis that the largest order type of any extension of the ordering on trees in TREE(n) is $\theta(\Omega^\omega \omega,0)$. According to Weiermann, we can use this to extract an upper bound of about that level of the fast-growing hierarchy. See math.stackexchange.com/questions/1950116/… $\endgroup$ – Deedlit Oct 22 '16 at 12:52
  • $\begingroup$ I see, very interesting! Could you add a few things about this to the Googology wiki article (I don't understand it completely yet). $\endgroup$ – wythagoras Oct 22 '16 at 13:03
3
$\begingroup$

The underlying rationale will be as follows. The Tree(n) question can be translated into a problem of the length of effectively given bad sequences. I think this goes directly back to Friedman. Such effectively given bad sequences can be mapped into effectively descending sequences of ordinals using the reification technique. Effectively descending sequences can be bounded by the Hardy hierarchy (by say an old MLQ article by Buchholz, Cichon, Weiermann). This will also give a reasonable concrete upper bound for n=3. The problem in writing this up is that until now according to my judgement very few people were interested in it. Moreover the material would be considered as "folklore" and so a publication might be turned down.

$\endgroup$
-1
$\begingroup$

TREE(3) is known to be finite, but few finite upper bounds have been proven that do not rely on constructions such as TREE(n) and n>3.

As for lower bounds, saying $g_{64}$ (Graham's number) is a lower bound for TREE(3) is like saying 1 is a lower bound for Graham's number. Even $g_{187,196}$ has proven to be an EXTREMELY WEAK lower bound for TREE(3).

See https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem and https://www.youtube.com/watch?v=3P6DWAwwViU.

$\endgroup$
  • $\begingroup$ Welcome to MSE. Your answer adds nothing new to the already existing answers. $\endgroup$ – José Carlos Santos Jan 25 at 20:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.