Googology Wiki
Register
Advertisement
Googology Wiki

View full site to see MathJax equation

Not to be confused with Exploding Tree Function or Friedman's finite trees.

The TREE sequence is a fast-growing function TREE[n] arising out of graph theory, devised by mathematical logician Harvey Friedman.[1][2] Friedman proved that the function eventually dominates all recursive functions provably total in the system \(\text{ACA}_0+\Pi_2^1-\text{BI}\).[1][note 1]

The first significantly large member of the sequence is the famous TREE[3] (sometimes written as TREE(3)[4]), notable because it is a number that appears in serious mathematics that is larger than Graham's number.

Definition[]

TREE[n][]

Suppose we have a sequence of n-labeled trees T1, T2 ... with the following properties:

  1. Each tree Ti has at most i vertices.
  2. No tree is inf preserving and label preserving embeddable into any tree following it in the sequence.

Kruskal's tree theorem states that such a sequence cannot be infinite. Harvey Friedman expanded on this by asking the question: given some n, what is the maximum length of such a sequence? This maximal length is a function of n, and is the definition of TREE[n] or the TREE sequence.

tree(n)[]

Define \(\text{tree}(n)\), the weak tree function, as the length of the longest sequence of 1-labelled (or unlabeled) trees such that:

  1. Every tree at position k (for all k) has no more than k + n vertices.
  2. No tree is homeomorphically embeddable into any tree following it in the sequence.

Lowercase tree is the weak tree, and TREE all uppercase is the regular function.

Analysis[]

Values for TREE[n][]

The first two values are TREE[1] = 1 and TREE[2] = 3. The next value, TREE[3], is famously very large. TREE[3] exceeds Graham's number, Ackermann Numbers, nn(5)(5), G3\(\uparrow\uparrow\uparrow\uparrow\)3, \(tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{tree\left(7\right)^{8}}}}}}\)[5]. Chris Bird claimed that \(\text{TREE}[3] > \{3, 6, 3 [1 [1 \neg 1,2] 2] 2\}\), using his array notation.[6]

Lower bounds of weak tree(n) and TREE[3][]

Although there are few known results, i.e. proved statements, of lower bounds of tree, a Japanese mathematician Takayuki Kihara[7] verified that the weak tree(4) is greater than Graham's number.[8] He introduced a hierarchy \(\text{tree}_n\) of large functions indexed by ordinals \(n \leq \omega + 1\) associated to a hierarchy of binary trees equipped with a fixed coding of a sequence of natural numbers, and precisely estimated the hierarchy in terms of fast-growing hierarchy. The significance of his works is that he explicitly estimated the value of the combinatoric large functions, while many googologists roughly talk about "the corresponding ordinals" without proofs. The ability of trees to express ordinals does not ensure the comparison between \(\text{tree}\) and the fast-growing hierarchy, and hence many arguments based on this wrong deduction are meaningless. See #Wrong arguments of the growth rate for detail.

Further, Kihara developed the method to precisely estimate the hierarchy \(\text{tree}_n\) extended to ordinals \(n < \Gamma_0\) associated to a hierarchy of ternary trees equipped with a fixed coding of Veblen hierarchy, and verified \(\textrm{tree}(4) > f_{\varepsilon_0}(G)\) and \(\text{tree}(5) > f_{\Gamma_0}(G)\) with respect to the canonical system of fundamental sequences, where \(G\) denotes Graham's number.[9] Unlike #Wrong arguments of the growth rate, the result explicitly estimates the lower bounds of the specific values of tree function.

As a consequence of the precise argument, Kihara obtained a strict inequality \(\textrm{tree}(1.0001n+2) > f_{\textrm{SVO}}(n)\) for \(n \geq 3\), where \(\textrm{SVO}\) denotes small Veblen ordinal. As Kihara states[9] that TREE[3] is far larger than \(\textrm{tree}(G)\), it follows that TREE[3] is larger than \(f_{\textrm{SVO}}(G)\).

A googologist Deedlit11 stated a lower bound of TREE[3] by tree. Define \(\text{tree}_2(n)=\text{tree}^n(n)\) and \(\text{tree}_3(n)=\text{tree}_2^n(n)\). (Note that it differs from the hierarchy \(\text{tree}_n\) in the previously explained one.) Then Deedlit11 stated \(\text{TREE}[3] > \text{tree}_3(\text{tree}_2(\text{tree}(8)))\).[10][note 2]

Values for \(\text{tree}(n)\)[]

It can be shown that \(\text{tree}(1) = 2, \text{tree}(2) = 5\), \(\text{tree}(3) \geq 844,424,930,131,960\), and \(\text{tree}(4) > \text{Graham's number}\).[8] \(\text{tree}(1)\) uses the sequence (by using #Alternative notations):

(())
()

\(\text{tree}(2)\) is a bit larger, we have two longest sequences that go as follows:

((()))
(()()())
(()())
(())
()

Otherwise:

(()())
(((())))
((()))
(())
()

Determining the exact value for \(\text{tree}(3)\) is much harder, since there are a lot of sequences to check, and each of these is very long. Nevertheless, a sequence has been formulated and an answer given[11]. The sequence is as follows:

(()()())
((()())())
((((()()))))
((((())(()))))
... 4 steps ...
(((()()))) 
((((((()))))((((()))))))) 
... 82 steps ...
((()()))
... many steps ...
()

As calculated from the reference above, tree(3) = (3/2 * 2^(46+2) - 2*46 - 6 + 95)*2 + 1 - 3 = 3*2^48 - 8 = 844,424,930,131,960.

Friedman has defined an FFF(k) function, which is equal to tree(k+1), but his guess as to the value of FFF(2) (aka tree(3)) of less than 100 seems a bit low.[12]

Alternative notations[]

(This alternative has yet to be formally verified.)

Trees are tricky to visualize without drawing them out, so we shall devise a more compact way of representing them. Consider a language which has various kinds of parentheses such as (), [], {} etc. Parentheses always come in pairs and can nest within each other. Within a larger node, they may be concatenated. For example, the following strings are valid in this language:

[]
([])
{[()]()}
[(){[[]]}(){(())[]}]

Suppose we have a string A. We shall call a pair of corresponding parentheses a node, in deference to the original tree construction. Define a child of a node to be a node that is nested one level deep within the original node. For example, take the string {[()()][][()]}; the children of the node represented by {} are the nodes represented by [], but not the nodes represented by ().

Call a node deletable if it has fewer than two children. For example, in the string {[()()][][()]}, the () nodes are all deletable, as are the latter two [] nodes, but not the first [] or the {}. In the string ([(()())]), the [] node is deletable.

We say a string A is reducible to a string B if A can be transformed into B by removing deletable nodes. A string A is reducible to a string B if and only if the tree represented by B is homeomorphically embeddable in the tree represented by A.

With all this in mind, we can create a function which should correspond with the original definition of TREE[k] assuming this notation was derived correctly. Suppose we have a sequence of strings with the following properties:

  1. You may only use k types of brackets.
  2. The first string has at most one pair of brackets, the second string has at most two pairs of brackets, the third string has at most three pairs of brackets, etc.
  3. No string is reducible to an earlier string.

TREE[k] is the maximal length of the sequence.

For k = 1, the optimal sequence has only one member: ().

For k = 2, the optimal sequence has only three members: (), then [[]], then [].

Weak tree function[]

Suppose we have a sequence of strings with the following properties:

  1. You may only use () and no other types of brackets.
  2. The first string has at most 1 + k pairs of brackets, the second string has at most 2 + k pairs of brackets, the third string has at most 3 + k pairs of brackets, etc.
  3. No string is carvable from a later string.

tree(k) (the weak tree function) is the maximal length of the sequence.

Videos[]

The readers should be very careful that there are many videos in which results which have not been proved are explained as if they are known results. See #Wrong arguments of the growth rate. Therefore if videos do not cite peer-reviewed sources or proofs, the reader should be skeptical of the results and should not spread them as if they were known to be correct.(All Numberphile videos)

History of discussion[]

Wrong arguments of the growth rate[]

TREE[n] was strongly believed to grow at least as fast as \(f_{\vartheta(\Omega^\omega\omega)}(n)\) in the fast-growing hierarchy, making it quite sizable even to a googologist. However, the estimation was based on wrong arguments by googologists, and hence has never been proved. If this belief is actually correct, then the TREE function is more powerful than Kirby-Paris hydras and Goodstein sequences, but weaker than SCG and Buchholz hydras. For a look into one of the issues of estimating high growth rates, check this section of a page on Jason's notation.

As we explained in #Analysis, many googologists roughly talks about "the corresponding ordinals" without proofs and "usual" arguments in this community are based on wrong deductions like "the fast-growing hierarchy depends only on ordinals" or "the existence of the correspondence to ordinals automatically ensures the comparability to the fast-growing hierarchy". Therefore the reader should be very careful if there are statements without peer-reviewed sources or proofs in this wiki. Since TREE and tree are quite difficult to evaluate, there are so many wrong or proofless statements about them. For example, several videos and articles explain how large TREE[3] is by "comparing" to many other known numbers without sources. Those estimations might be fortunately true, but the truth is irrelevant to the fact that they have not been proved.

For example, a googologist stated certain estimations of lower bounds of TREE[3] and tree(n):[13] His original claims lacked proofs, but many users of this wiki just believed that these results were verified and gave new lower bounds of TREE[3] and tree(n) in terms of FGH with respect to a canonincal choice of fundamental sequences.[note 3]

Footnotes[]

  1. Friedman further proved a theorem that TREE[3] is greater than the halting time of any Turing machine initialized with a blank tape, which can be proved to halt in \(\text{ACA}_0+\Pi_2^1-\text{BI}\) by a proof with at most \(2 \uparrow \uparrow 1000\)[3] symbols.[1]
  2. \(\text{tree}_3(\text{tree}_2(\text{tree}(8)))\) is equal to treetreetree...tree(n)...(n)(n)(n) with n layers, where \(n = \text{tree}^{\text{tree}(8)}(\text{tree}(8))\). We note that even if it is correct, it does not give a lower bound of TREE[3] in terms of FGH for larger ordinals with respect to a canonical choice of fundamental sequences.
  3. In order to solve this issue, he added a "proof" on 24/07/2020,[13], which was praised as a "perfectly good proof" by a user, but it soon turned out that it was not a full proof, i.e. did not give lower bounds by TREE[3] and tree(n) in terms of FGH with respect to a canonical choices of fundamental sequences. Later, on the same day, he provided "proofs" in another blog post of the estimations,[14] but also on the same day, another user pointed out that these proofs are completely incorrect because they are based on common mistakes.[15]

Sources[]

See also[]

Graph theory in googology

TREE sequence  TREE(3) · Greedy clique sequence · Friedman's finite trees · Subcubic graph number  SCG(13) · Graham's number  G(64)

Advertisement