Talk: TREE sequence/Archive 1

Can we get the original source for this instead of Wikipedia? FB100Z • talk • contribs 02:18, September 13, 2012 (UTC)

Perhaps it comes from "Enormous Integers In Real Life". Ikosarakt1 (talk) 15:20, October 6, 2012 (UTC)

Anyways, what is the TREE sequence anyway? The article doesn't explain it. FB100Z • talk • contribs 03:54, October 20, 2012 (UTC)

See "chapter 11" for formal definition. As for values, see: http://www.cs.nyu.edu/pipermail/fom/2006-March/010279.html Ikosarakt1 (talk) 08:00, October 20, 2012 (UTC)

Comparison of TREE with array notations

I guess that TREE(3) is between humongulus and golapulus. --Cloudy176 (talk) 13:57, October 24, 2012 (UTC)

In fact: TREE(3) larger than f_Г(3) = {3,3,1,2} & 3, which is larger than humongulus = {10,10,100} & 10. Ikosarakt1 (talk) 18:57, October 25, 2012 (UTC)

Hmm, my reasoning leads me to believe f_Г0(n) is about n & n & n... & n with n n's. This would make TREE(3) much larger than golapulus Deedlit11 (talk) 16:19, November 16, 2012 (UTC)

Golapulus is already ~ {10,100 [1 [1 --| 1 [2] 2] 2} (there: --| is negation sign), but TREE(n) growth is about {3,n [1 [1 --| n] 2] 2} (small Veblen ordinal) Ikosarakt1 (talk) 09:07, November 17, 2012 (UTC)

I assume you are getting those correspondences from Bird's "Bowers Named Numbers", is that correct?? I'm not sure I agree with all the findings.? As I explained in my blog comment, I think Gamma_0 should correspond to n & n & n ... & n with n n's.? So the small Veblen ordinal will certainly be greater than that.

I should point out that the small Veblen ordinal is merely a lower bound for the growth rate of TREE(n). As far as I know, no good upper bound has been found.Deedlit11 (talk) 00:57, November 23, 2012 (UTC)

In this case, need to reconsider the comparison of TREE with array notations. Ikosarakt1 (talk) 12:16, November 23, 2012 (UTC)

After more detailed research on fast-growing hierarchy I am sure that TREE(3) far larger than meameamealokkapoowa oompa (see blog comment). Ikosarakt1 (talk) 15:33, November 24, 2012 (UTC)

TREE(3) made into a game --Cloudy176 (talk) 10:25, December 26, 2012 (UTC)

If your calculations are all correct, then (say) TREE(1,000) will certainly be larger than meameamealokkapoowa oompa. However, I still have doubts that TREE(3) is larger than meameamealokkapoowa oompa. --I want more clouds! 05:02, December 31, 2012 (UTC)

\(f_{\psi(\Omega^\omega)}\)(n)

Is \(\psi(\Omega^\omega)\) is the same ordinal as \(\vartheta(\Omega^\omega)\)? Ikosarakt1 (talk) 10:45, February 23, 2013 (UTC)

No, they're different. \(\psi(\Omega^\omega)=\vartheta(\omega)\), while \(\vartheta(\Omega^\omega)=\psi(\Omega^{\Omega^\omega})\). See here. I want more clouds! 11:29, February 23, 2013 (UTC)

Hmm, ordinal collapsing function definitions may vary by authors. Maybe they are equal, or may not... I want more clouds! 11:31, February 23, 2013 (UTC)

Cloudy is correct, in that under the most usual definitions, \(\vartheta(\Omega^\omega)=\psi(\Omega^{\Omega^\omega})\). Both these notations represent the small Veblen ordinal. Under the most usual definition, \(\psi(\Omega^\omega)\) = \(\phi(\omega, 0)\), not the small Veblen ordinal. Therefore I will fix the main page.Deedlit11 (talk) 14:40, February 28, 2013 (UTC)

Ordered vs unordered siblings

I wanted to point out that there are two definitions of homeomorphic embeddability with rooted trees: the one with ordered siblings, and other one with unordered. On this site and on Goucher's blog we are with no doubt using unordered version, for which trees (()[]) and ([]()) are equivalent. But, if I'm not mistaken, even Kruskal himself used ordered version. This is because he interpreted trees as set of integer strings closed under prefixes. Friedman certainly used this version, because otherwise n(4) argument fails. Here is same story. Ordered siblings make much difference in tree(n) function too. Let utree(n) mean unordered version and otree(n) ordered version. It should be clear that \(utree(n)\leq otree(n)\). I found out that \(utree(2)=otree(2)=5\), \(utree(3)\geq 2^{17}+8\) and \(otree(3)\geq 2\uparrow ^6 3\), so difference quickly becomes significant. Which version you think we should use? Friedman's one, or Goucher's one? LittlePeng9 (talk) 12:43, February 23, 2013 (UTC)

Like busy beaver, TREE function also allows variations. Whatsoever, it is doesn't cancel Goucher's lower bound for TREE(3). Ikosarakt1 (talk) 13:22, February 26, 2013 (UTC)

Yes, you are right. Even better - Goucher's bound was given for unordered trees (I think) so, as ordered embeddability implies unordered one but not vice versa, this lower bound still applies when using utree function, but also otree function. And I'm sure we could add at least one more exponent to this lower bound. LittlePeng9 (talk) 14:15, February 26, 2013 (UTC)

Actually, both Friedman's posts on the FOM mailing list, and my answer on MathOverflow, use unordered trees (Friedman calls ordered trees structured trees.) In fact, I made a point of it in my answer on MathOverflow how my argument had to be changed slightly because I was using unordered trees instead of the ordered trees used by Jervell. Please see the Friedman's FOM postings for an explanation of how n(4) can be embedded in an unordered tree.Deedlit11 (talk) 14:36, February 28, 2013 (UTC)

Ah, sorry, I haven't noticed how you modified Levitz's ordering. Now it makes sense to me. And about Friedman's posting, I've read it, but when I read about linearly ordered vertices starting at the root, what I thought it means is ordered tree with root and vertices attached directly to it. Thanks for all the clarification. LittlePeng9 (talk) 17:03, February 28, 2013 (UTC)

Bird's hierarchy

When Chris Bird writes that"[X] has level \(\alpha\)", he doesn't means that \(f_{\alpha}(n)\) is about {n,n [X] 2}. Rather, he creates his own hierarchy of separators, if you look closer. Ikosarakt1 (talk) 10:04, February 26, 2013 (UTC)

But that is irrelevant to the information you removed. That was the result Chris Bird has shown in the paper. I don't think it should be removed. I want more clouds! 10:55, February 26, 2013 (UTC)

Where Bird was stated that? I opened "Beyond Nested Arrays II" document, page 10, but Bird doesn't says there about TREE(3) strictly. Ikosarakt1 (talk) 11:10, February 26, 2013 (UTC)

You seem older version of his work. in the new version "Beyond Nested Arrays II" of 19.02.2013 on page 10. Konkhra (talk) 23:20, February 26, 2013 (UTC)

Here's the link: [1] -- I want more clouds! 11:29, February 26, 2013 (UTC)

Okay, it turns out that. I will return that info. Thanks. Ikosarakt1 (talk) 12:05, February 26, 2013 (UTC)

Reasonable amount

From the article: "Actually, it has been proven [3] that TREE (3)> n (n (... (5) ...)) with any reasonable amount of nested functions". How much "reasonable amount"? thousand, googol or may be {3,3,3,3,3} in BEAF? Konkhra (talk) 22:20, February 27, 2013 (UTC)

I know it isn't well stated. It's actually larger than anything you may suspect - it's well larger than {3,3,...,3}, where there are {3,3,...,3) 3's, where there are {3,3,...,3) 3's... You can repeat this millions of billions of trillions times, so this is above what I'd call "reasonability limit". Here you can see deriviation of much stronger bound (in every place function F is used, function n will do) LittlePeng9 (talk) 06:25, February 28, 2013 (UTC)

It's great! thanks for the answer Konkhra (talk) 08:07, February 28, 2013 (UTC)

Larger lower bound for TREE(3).

I have found a lower bound for TREE(3) that is larger than AP Goucher's. I wrote up an explanation of this in an answer on mathstackexchange, and I reproduce the explanation here.

Before we get to TREE(3), let's examine some smaller sequences that will build up towards it.

To describe a tree, I will use () to denote a vertex labelled with 1, and [] to denote a vertex labelled with 2. The children of a vertex will be placed within the separators for the vertex; so for example

([][][])

means a vertex labelled with 1 with three children labelled with 2; and

[(()()) ()]

means a vertex labelled with 2 with two children labelled with 1; the left child has two children labelled with 1.

We will start by examining trees that are paths, with the root labelled with 2 and the rest of the vertices labelled with 1.

[]
(())
()

starting from a single vertex labelled with 2 leads to a sequence of length 3.

[()]
(()[])
((([])))
(([]))
([])
[]
(()()()()()()())

the last tree is the first tree in the sequence for tree(7) so we get a sequence of length greater than tree(7)

[(())]
(()[()])
((([()])))
(([()]))
([()])
[()]
(()()()()()()()[])

the last tree is the first tree in the sequence for tree(8), except the last vertex is labelled with a 2. We can thus continue with a sequence of length tree(8) of trees with all but one vertex labelled with 1, finally ending in a tree consisting of one vertex labelled with 2. The next tree is then a tree with more than tree(8) vertices with all vertices labelled with one; this leads to a sequence of more than tree(tree(8)) vertices.

Continuing in this fashion, a path with one vertex labelled with 2 and n vertices labelled with 1 will lead to a sequence of more than tree\(^n(n+6)\) trees. If we define tree\(_2 (n)\) to be tree\(^n(n)\), then our lower bound is more than tree\(_2 (n)\) trees.

Now consider a tree consisting of a path of length \(n+1\) with the bottom vertex of the path having two children. Again, the root will have label 2 and the rest of the vertices will have label 1. For example, with n = 3 the tree is

[(((()())))]

We can construct a sequence of more than tree\(_2 (n-1)\) trees by basically following the previous sequence, with the two children at the bottom added on. This leads us to the tree [()()]. We follow that with the tree [(((...()...)))] with more than tree\(_2 (n-1)\) vertices. By our previous bound, we will wind up with a sequence of length greater than tree\(_2\) (tree\(_2 (n-1))\).

If we next consider a tree similar to the previous one, except we add a child to one of the two children at the bottom, we will get a lower bound of tree\(_2\) (tree\(_2\) (tree\(_2 (n-1)))\). If we add a path of length $m$ rather than a single child, we get a lower bound of tree\(_2^{m+2}(n-1)\). Define tree\(_3 (n)\) to be tree\(_2^n(n)\). If \(n \ge m+3\), we have a lower bound of tree\(_3 (m)\).

Now we are ready to find a lower bound for TREE(3). Start with:

{}  (one vertex with label 3)
[[]]
([][])
[()()()]
[(())(())]
[((()) ()) ()]
[(((()()))) ()]
[((((()()))()))]
([(((()()))())]())
((([(((()()))())])))
(([(((()()))())]))
([(((()()))())])
[(((()()))())]
(()()()()()()()[((()()))()])

this leads to a sequence of tree(8) trees, ending in

[((()()))()]

this is followed by

[((()())())]

where the ( stands for tree(8) ('s and ) stands for tree(8) )'s.

This leads to a sequence of tree\(_2\) (tree(8)) trees, ending in

[(()())()]

This is followed by

[(( () )())]

where the ( stands for tree\(_2\) (tree(8)) ('s and ) stands for tree\(_2\) (tree(8)) )'s.

This leads to a sequence of more than tree\(_3\) (tree\(_2\) (tree(8))) trees.

Thus TREE(3) > tree\(_3\) (tree\(_2\) (tree(8))).

As you can imagine, the TREE(n) function clearly outpaces the tree(n) function, which is already at the level of the Small Veblen Ordinal in the fast-growing hierarchy. This is not surprising, since labelled trees lead to more possibilities than unlabelled trees. —Preceding unsigned comment added by Deedlit11‎ (talk • contribs)

In comparison to Bird's array notation, I believe that your bound should be about \(\{3,\{3,\{3,7 [1 [1 \neg 1,2] 2] 2\},2 [1 [1 \neg 1,2] 2] 2\},3 [1 [1 \neg 1,2] 2] 2\}\) Ikosarakt1 (talk) 22:30, March 6, 2013 (UTC)

Thanks. Unfortunately, I know of no firm upper bounds for either tree(n) or TREE(n). Deedlit11 (talk) 23:19, March 6, 2013 (UTC)

If I understand you correctly that tree\(_3\) (tree\(_2\) (tree(8))) = tree^treetree(8)

but it is much smaller than the lower bound Goucher's. may be I misunderstood? Konkhra (talk) 09:51, March 7, 2013 (UTC)

No, I believe he mean \(tree_2(n)\) is tree^{treetree...tree(n)...(n)(n)}(n) (with n occurrences of tree(n)), and \(tree_3(n)\) is tree₂^{tree₂tree₂...tree₂(n)...(n)(n)}(n) (with n occurrences of tree₂(n)). Ikosarakt1 (talk) 09:59, March 7, 2013 (UTC)

Thanks, now I see the light Konkhra (talk) 10:05, March 7, 2013 (UTC)

Actually, \(tree_2(n)=tree^n(n)\) and \(tree_3(n)=tree_2^n(n)>tree^{tree^{tree^{...}(n)}(n)}(n)\) with n exponents. —Preceding unsigned comment added by LittlePeng9 (talk • contribs)

LittlePeng9 is correct. AP Goucher's bound is therefore about \(tree_3(5)\). \(tree_3 (tree_2 (tree(8) ) ) \) is about tree^{treetree...tree(n)...(n)(n)}(n) with n exponents, where \(n = tree_2 (tree(8)) = tree^{tree(8)} (tree(8)) \). So my bound is not fundamentally larger than Goucher's bound, but it's an improvement nonetheless. Deedlit11 (talk) 00:18, March 8, 2013 (UTC)

By the way, thanks Cloudy for tidying up my post. Deedlit11 (talk) 00:57, March 12, 2013 (UTC)

Chris Bird's private e-mail

In a private e-mail Chris Bird wrote:

tree^(tree^(...(tree^8 (7)) ...) (7)) (7) (with n tree’s)

> {3, n+1, 3 [1 [1¬1,2] 2] 2},

and larger lower bound for TREE(3), which I’ll call L, is

L = tree^(tree^(...(tree (N)) ...) (N)) (N) (with N tree’s),

where N = tree^(tree (8)) (tree (8)).

Hence, L > tree^(tree^(...(tree^8 (7)) ...) (7)) (7) (with N-1 tree’s) > {3, N, 3 [1 [1¬1,2] 2] 2}.

It follows that L > {3, {3, {3, 7 [1 [1¬1,2] 2] 2}, 2 [1 [1¬1,2] 2] 2}, 3 [1 [1¬1,2] 2] 2}.

Like the previous lower bound, the above array is greater than

{3, 2, 4 [1 [1¬1,2] 2] 2} = {3, 3, 3 [1 [1¬1,2] 2] 2}

but less than {3, 3, 4 [1 [1¬1,2] 2] 2}

As {3, 2, 4 [1 [1¬1,2] 2] 2} < {3, 6, 3 [1 [1¬1,2] 2] 2} < L < {3, 3, 4 [1 [1¬1,2] 2] 2},

L is not a vast improvement on the previous lower bound, and so I don’t feel that I need to update my "Beyond Bird’s Nested Arrays II" document.

Konkhra (talk) 01:36, March 20, 2013 (UTC)

Hmm, does Chris read Googology Wiki? Deedlit11 (talk) 01:55, March 20, 2013 (UTC)

I wrote to him about your larger bound Konkhra (talk) 01:57, March 20, 2013 (UTC)

Homeomorphic embedding

Given two trees: [()()()[]] and [()()([])]. Is there a place for the homeomorphic embedding (1st to 2nd or otherwise) or not? It seems that I almost understood how that function really works. Ikosarakt1 (talk ^ contribs) 19:56, March 15, 2013 (UTC)

There's no homeomorphic embedding either way. To embed the first into the second, the four edges of the first must map to four disjoint paths (the "homeomorphic" part implies that different edges must map to disjoint paths), and the second does not contain four disjoint paths. To embed the second into the first, the path of length 2 must map to a path of length 2 or more, and the first doesn't have any. Deedlit11 (talk) 20:39, March 15, 2013 (UTC)

Okay, thanks for the explanation. Ikosarakt1 (talk ^ contribs) 20:49, March 15, 2013 (UTC)

I think explantation in article is wrong. It's more sophiscated than substring. If it were so, we'd have infinite sequence: (); ([]); ([[]]); ([[[]]]) etc. There is allowable modification - we can delete pair of neighbouring parenthesis, e.g. () is embeddable to ([]). In unordered version we can interchange siblings. Optimal sequence for TREE(2) is []; (()); () LittlePeng9 (talk) 20:39, March 16, 2013 (UTC)

LittlePeng9 is correct. For example, {} is homeomorphically embeddable into the fourth example string given in the article, since {} is just a single vertex labelled with 3, so it is embeddable into any tree with a vertex labelled 3, i.e. any string containing braces. Deedlit11 (talk) 21:51, March 16, 2013 (UTC)

FB100Z's new definition doesn't work - for example, ([()]), ([[()]]), ([[[()]]]), ([[[[()]]]]), is an example of an infinite sequence of trees for which no tree embeds into another under the current definition. I will try to find a fix. Deedlit11 (talk) 18:28, March 17, 2013 (UTC)

awwwwwwwwww damnit FB100Z • talk • contribs 19:35, March 17, 2013 (UTC)

Maybe we'll try to work definition backwards, from definition for trees. Embedding must be label-preserving. This seems to be trivial, we just don't allow parenthesis to change color/shape/label. It must also be inf-preserving. inf of two pairs of parenthesis is deepest pair which contain both pairs. If we want to delete non-leaf vertex x, we can delete all vertices such that x may be inf of them - all vertices above x. So we can delete parenthesis along with everything in them. There is also something I call "neck". In tree, this is simple path of vertices with exactly one child each. In string, for example, (([({A})])), where A is any string, (([({})])) is a neck. We can contract part of neck as long as first and last of vertices has same label. So our string can be contracted to (({A})) or ({A}), but not {A}. In trees we can also do edge contraction as long as both ends of edge have same label. Example in strings - [A[B]] -> [AB]. It should be obvious that all of these preserve infs, but I don't know if these are all cases. I know it's a looong explantation, but it should make it clear. No one said understanding homeomorphic embeddings is easy. LittlePeng9 (talk) 20:17, March 17, 2013 (UTC)

I've updated the article once again. Hope I'm right this time. FB100Z • talk • contribs 22:14, March 17, 2013 (UTC)

Unfortunately, it still doesn't work. For example, you can use the third rule "grafting" to reduce ([()()]()) to (()()()) by removing the [], but ([()()]()) is not homeomorphically embeddable in (()()()). A for effort though.Deedlit11 (talk) 22:47, March 17, 2013 (UTC)

No, grafting requires the removed parenthesis to be the same type as their parents. [[(){}]()] (say) can be carved to [(){}()], but [((){})()] cannot because the inner () do not match the outer []. FB100Z • talk • contribs 04:34, March 18, 2013 (UTC)

In that case, you can use grafting to reduce ((()())()) to (()()()). But the latter is not homeomorphically embeddable in the former. Deedlit11 (talk) 04:46, March 18, 2013 (UTC)

Looks like a valid edge contraction to me. I guess I have the definition of homeomorphic embeddability wrong. FB100Z • talk • contribs 05:05, March 18, 2013 (UTC)

A tree S is homeomorphically embeddable in a tree T if there is a function f from the vertices of S to the vertices of T such that

1. If v is a child of u in S, f(v) is a descendant of f(u) in T.

2. Define inf(u, v) to be the greatest common ancestor of u and v. Then for any vertices u and v of S, f(inf(u, v)) = inf(f(u), f(v)).

It is this latter condition that prevents (()()()) from being homeomorphically embeddable into ((()())()). There is an embedding f, but, while the infemum of any two leaves of the first tree is the root of the tree, the infemum of the first two leaves of the second tree is not the root. But the root must map to the root, so the second condition is not satisfied. Deedlit11 (talk) 05:30, March 18, 2013 (UTC)

Okay, I'm going to have to sleep on this issue. In the meantime I have Kleene's \(\mathcal{O}\) to figure out :P FB100Z • talk • contribs 05:42, March 18, 2013 (UTC)

@Deedlit

I don't think that adding so much formalities is a good for the explanation. You can revise my version of explaining and tell me where I was wrong. Ikosarakt1 (talk ^ contribs) 09:26, March 18, 2013 (UTC)

Dammit, this is more complicated than I thought! Now as I think about it, edge contraction isn't valid move. Consider contraction of edge xy with x on top. If x has two children or more, their inf is x, but after contraction, it'd be y. So edge contraction is forbidden. LittlePeng9 (talk) 10:28, March 18, 2013 (UTC)

I believe I have it correct now. Some more examples could be useful. Deedlit11 (talk) 14:26, March 18, 2013 (UTC)

Exact values of tree(n)

Anyone knows exact values for \(tree(n)\) for specific n? I found that \(tree(1) \geq 2\), using the sequence \((()), ()\). Also, \(tree(2) \geq 5\), using the sequence \((()()), (((()))), ((())), (()), ()\). Ikosarakt1 (talk ^ contribs) 22:30, March 16, 2013 (UTC)

It is indeed true that tree(1) = 2 and tree(2) = 5. To prove that tree(2) = 5: Define an n-path to be the tree consisting of a path of n edges starting from the root, and an n-star to be the tree where the root has n children, none of which have children. The first tree must be either an 2-path or an 2-star (or a subtree, and it is never better to take a subtree over a larger tree). If it is a 2-path, then there can be no more paths of length two or more in following trees, so the remaining trees can only be n-stars. So the best choices for the remaining trees must be to take the largest possible n-star each time, so you get ((())), (()()()), (()()), (()), (). Otherwise, the first tree is a 2-star, which means the remaining trees can have no vertices with two or more children. So the remaining trees must be n-paths, and again the best thing to do is to take the largest n-path each time, so you get (()()), (((()))), ((())), (()), (). These are the two longest sequences, and so tree(2) = 5.

For tree(3), I got a sequence of length 2^18 - 4; LittlePeng9 got a sequence of length 2^17 + 8. I think it is reasonably possible that tree(3) = 2^18 - 4, but it will be very difficult to prove.

For tree(4) and above, the numbers are very large. For example, tree(4) will be larger than F_epsilon_0 (n) for very large n (larger than Graham's number to take a random large number). tree(5) will be larger than F_phi(1,0,0,0) (n) and so on. Deedlit11 (talk) 22:47, March 16, 2013 (UTC)

Chris Bird wrote in his work "Beyond Nested Arrays II" (see page 10):

TREE(3) > tree^(tree^(tree^(tree^(tree8(7)) (7)) (7)) (7)) (7),

where the slightly slower growing tree function (lower case) grows at least as quickly as

f(n) = {3, n [1 [1¬1,2] 2] 2}

which is at the level of the small Veblen ordinal (much greater than Γ0). Royce Peng has investigated

that the growth rate of the slower tree function is at the θ(Ω^(n-2)) level for n ≥ 4, meaning that

tree(n) > {3, 3 [1 [1 ¬ n] 2] 2} (for n ≥ 4).

From the information above, I find that tree(7) > {3, 6 [1 [1¬1,2] 2] 2}.

Konkhra (talk) 08:17, March 17, 2013 (UTC)

Deedlit, you wrote that \(tree(4) > f_{\varepsilon_0}(n)\) (for an extremely large n), and \(tree(5) > f_{\varphi(1,0,0,0)}(n)\), but there is a gap between \(\varepsilon_0 = \varphi(1,0)\) and \(\varphi(1,0,0,0)\). So, did you mean that \(tree(5) > f_{\varphi(1,0,0)}(n)\) or \(tree(n)\) leaps on two zeroes in the \(\varphi\) system for every increment? Ikosarakt1 (talk ^ contribs) 21:03, March 20, 2013 (UTC)

I can't be sure, but I think he didn't made a mistake. This is connected to certain well order on trees, in which root with three children (probably best tree ro start tree(4) ) corresponds to \(\varepsilon_0 \), while for n>3 root with n children corresponds to \(\varphi(1,0,...,0)\) with n entries. LittlePeng9 (talk) 22:13, March 20, 2013 (UTC)

That's correct. There is a peculiarity with the well-ordering where binary trees correspond to \(\varepsilon_0 \), but ternary trees skip over \(\varphi(1,0,0) = \Gamma_0\) straight to \(\varphi(1,0,0,0)\). \(\Gamma_0\) corresponds to ((())(())(())) in unordered trees, i.e. the tree where each of the three children has a child; in ordered trees, \(\Gamma_0\) corresponds to (()()(())), i.e. the tree where the "most important" child has one child. If you think about it, it makes sense that a root with n children corresponds to \(\varphi(1,0,...,0)\) with n entries; for example, in ordered trees, if trees A, B, C, D correspond to ordinals a, b, c, d, then the tree (A, B, C, D) corresponds to the ordinal \(\varphi(d, c, b, a)\). So when you close under all such operations, you get all trees less than the tree (()()()()()) and all ordinals less than the ordinal \(\varphi(1,0,0,0,0)\), just like we want. But for whatever reason, binary trees are not strong enough to get to \(\Gamma_0\), it only gets to \(\epsilon_0\). So \(\Gamma_0\) gets delayed, and winds up corresponding to an unexpected tree. But good eye for noticing the anomaly! Deedlit11 (talk) 01:41, March 21, 2013 (UTC)

Enormous integers in real life

Harvey M. Friedman in his work "ENORMOUS INTEGERS IN REAL LIFE" talks about PLANE GEOMETRY and says that "This is at the same rates of growth as in section 11" (section 11 about TREE(3)). Who can write an article about it? Also Harvey M. Friedman talks about REGRESSIVE FUNCTIONS and SOLVABILITY OF INEQUALITIES IN NUMERICAL FUNCTIONS. Interesting to read about it on googology wiki! Konkhra (talk) 03:47, April 16, 2013 (UTC)

I think it'd be best if article was written by someone who understands that. If no one will do that, I can. LittlePeng9 (talk) 05:54, April 16, 2013 (UTC)

Yes, the trouble for me (and many googologists I believe) that Friedman wrote these articles in professional mathematician-style, and it makes it hard to understand. However, his works can be helpful in googology, if you can explain it more comprehensibly, I would be pleased. Ikosarakt1 (talk ^ contribs) 08:20, April 16, 2013 (UTC)

I can write it, but what shall we name the article? Deedlit11 (talk) 14:33, April 16, 2013 (UTC)

I took my time analysing Friedman's paper. First of all, TR(k) function disscuted there isn't TREE function (it concerns unlabelled trees of bounded valence). But it doesn't change fact that this function grows at rate of SVO. Second, I looked at planar circles (not p-circles yet) problem. Call corresponding function f(k). f(k) certainly takes only odd values (same argument as for n(k) function) and f(1)=5. \(f(2)\geq 25\). 

I also found that we don't need exact positions of circles. We need to know which circles are inside of others. This made me think that we can translate problem to trees with numbered vertices - if C_n lies inside of C_m, then vertex numbered m is predecessor of n. I need to find how embeddability relation looks there. LittlePeng9 (talk) 11:20, April 20, 2013 (UTC)

Embeddability relation is just standard embeddability without the inf-preserving requirement. Yes, translating it into trees or strings is a good way to explain it. I also find interesting the variant in which embedding must preserve the ordering of the numbers, in analogy with n(k). The theorem still holds - I wonder what the growth rate will be in this case. One can show that f(1) >= 13 for this variant. Deedlit11 (talk) 13:01, April 20, 2013 (UTC)

Oh, wait, I made fail while checking f(2) - I forgot about unordering. I found f(2)>=13 for unordered version. But ordered version will grow asymptitically at same rate as unordered (I think) - \(\varepsilon_0\). 

Also, forests would be a bit better choice for representation. But after all, set of forests is one-to-one with set of trees by deleting root, so it's not big deal. LittlePeng9 (talk) 13:10, April 20, 2013 (UTC)

Yeah, I would also guess \(\varepsilon_0\) for the ordered version. Incidentally, the ordered f(2) is greater than the n(3) from the block subsequence theorem. I'm unable to get big numbers for the unordered version. Deedlit11 (talk) 16:24, April 20, 2013 (UTC)

I think Deedlit11 and LittlePeng9 are definitely our resident experts in googology. :P --Ixfd64 (talk) 15:47, April 16, 2013 (UTC)

I think so. They are certainly professional mathematicians, while I'm just an amateur and hobbyist. Ikosarakt1 (talk ^ contribs) 16:23, April 16, 2013 (UTC)

I'm 15 and I'll finish middle school this year, just fyi :P I'm hobbyist too. LittlePeng9 (talk) 16:28, April 16, 2013 (UTC)

• Well, you sure know a lot about math for a middle schooler! --Ixfd64 (talk) 16:47, April 16, 2013 (UTC)

Middle school?!! That's disgusting. You have a bright future ahead of you! Deedlit11 (talk) 16:50, April 16, 2013 (UTC)

Holy cow. You definitely know a lot for your age! (I'm 16 btw) FB100Z • talk • contribs 19:31, April 16, 2013 (UTC)

New upper bound

I found a new upper bound for TREE(3).

TREE(4). FB100Z • talk • contribs 04:30, May 10, 2013 (UTC)

More upper bounds: TREE(5) < TREE(6) < TREE(7) < TREE(8) < TREE(9) < ...< TREE(TREE(meameamealokkapoowa oompa)). lol. $Jiawhein$^{\(a\)\(l\)\(t\)} 09:57, May 10, 2013 (UTC)

Larger terms

Anyone did serious research on TREE(4) or any of the terms above? Ikosarakt1 (talk ^ contribs) 15:14, May 29, 2013 (UTC)

Much stronger?

At the end of Beyond Nested Arrays IV Chris Bird mentions his notation being as strong as Extended Kruskal's theorem, concerning trees labelled 1 through n. Finite set with arbitrary preorder is well-quasi-ordered, as any chain must have repeated elements. By standard Kruskal theorem if we take preorder where all elements are incomparable then corresponding tree ordering is well quasi. But this is exactly ordering Bird mentioned! So this "Extended" theorem is provable in normal one. And strength of Kruskal's theorem is SVO, not \(\theta(\Omega_\omega)\). Is it possible that TREE function is that much stronger? Or was just Bird mistaken (or I am)? LittlePeng9 (talk) 17:00, July 8, 2013 (UTC)

Bird was incorrect in his definition of the Extended Kruskal's Theorem. It is the same as the Labelled Kruskal's Theorem, except it adds a "gap condition": T_i is homeomorphically embeddable in T_j with gap condition if there is a map f from the vertices of T_i to T_j such the usual conditions are satisfied, and also, if v is a child of u in T_i, not only does l(f(u)) = l(u) and l(f(v)) = l(v) (here l stands for label), but also l(w) >= l(f(v)) for every w between f(u) and f(v). The strength of this theorem is \(\theta(\Omega_\omega, 0)\). If you have seen Jervell's ordering on finite labelled trees, it's definition also involves this gap condition, and indeed one can use Jervell's ordering to define a bad sequence for Extended Kruskal's Theorem of length \(\approx F_{\theta(\Omega_\omega, 0)}(n)\).

Note that the TREE function grows faster than \(F_{\theta(\Omega^{\omega},0)}(n)\); the strategy I used for the lower bound of TREE(3) can be used to get a lower bound of \(F_{\theta(\Omega^{\omega},0)\omega^{\omega}}(n)\). I don't know any good upper bounds for TREE(n). Deedlit11 (talk) 20:55, July 8, 2013 (UTC)

Font

The entire text of this page is written in a strange font. --84.61.145.180 08:09, February 15, 2014 (UTC)

Aside from the font changes, the following sentence was changed:

Before: "Kruskal's tree theorem states that such a sequence cannot be infinite."

After: "Kruskal's tree theorem states that such a sequence is greater than infinite."

Since that didn't look constructive, I reverted the edit. -- ☁ I want more clouds! ⛅ 09:16, February 15, 2014 (UTC)

STOP REVERTING MY EDITS!

--5.12.95.44 12:51, February 15, 2014 (UTC)

I propose the term "treeish" for functions with growth rate at the small Veblen ordinal. -- ☁ I want more clouds! ⛅ 10:02, April 5, 2014 (UTC)

FFF function?

Friedman mentions an FFF function that seems to be closely related to the tree function. Anyone want to take a closer look? --Ixfd64 (talk) 05:52, April 7, 2014 (UTC)

Growth rate is not something impressive. in comparison with TREE Konkhra (talk) 09:41, April 7, 2014 (UTC)

I believe FFF(n)=tree(n+1), using weak tree function. LittlePeng9 (talk) 12:29, April 7, 2014 (UTC)

I figured that might have been the case, but Friedman's estimate for FFF(4) was no more than 100 while Deedlit11 got a value of 2¹⁸ - 4 for tree(3). What accounts for the discrepancy? --Ixfd64 (talk) 16:50, April 7, 2014 (UTC)

Friedman admitted he didn't analyse this result deeply, I guess he just missed that sequence which gave us so strong bound. LittlePeng9 (talk) 16:53, April 7, 2014 (UTC)

number-theoretical-properticationa-thingies

as far as number theory goes, what do we know about TREE(3)? anything about its parity? its prime factorization? you're.so.pretty! 06:51, April 22, 2014 (UTC)

I'm not 100% sure, but I think TREE(3) is odd. Beacause when we reach (()()...()()) at step n, we reach () at step 2n+1. Wythagoras (talk) 07:02, May 3, 2014 (UTC)

It depends on what type of trees are disallowed by that time. I guess you assume by that stage only this type of trees is allowed. But we don't know if TREE sequence has to terminate with (()()...()) type of trees. LittlePeng9 (talk) 12:16, May 3, 2014 (UTC)

Friedman did once state that every n(k) is odd. [2] --Ixfd64 (talk) 16:51, May 4, 2014 (UTC)

That's correct - if we have even-lengthed string with property * then appending one symbol at the end won't change a thing. LittlePeng9 (talk) 17:56, May 4, 2014 (UTC)

Binary TREE function

Suppose we changed the rules so that at first the tree could have 2 vertices. Or 3. Or even more. Then we could get a binary function TREE(a,b). The only rule change is that at stage n, the tree is allowed n+b-1 nodes. Also, we can remove the second argument if it is 1. TREE(1,2)=2. TREE(1,3)=6. However, TREE(2,2) = TREE(3)-1. In general, TREE(n,2) = TREE(n+1)-1. 77.101.22.166 06:46, June 27, 2014 (UTC)

I have made a similiar function earlier. Also, TREE(1,3) = 5, using (()()), (((()))), ((())), (()), () or ((())), (()()()), (()()), (()), () and TREE(1,n) = tree(n-1). Wythagoras (talk) 09:33, June 27, 2014 (UTC)

I doubt that this significantly increases the power of the function; seems like it just provides another \(\aleph_0\) ways to achieve what is essentially the same growth rate. you're.so.pretty! 18:23, June 27, 2014 (UTC)

should we redirect TREE(3) to TREE sequence?

discuss here. i think yes. Cookiefonster (talk) 01:31, February 17, 2015 (UTC)

I saw that for example Fish's numbers has been added to the full list twice. So, could other values of TREE(k) be in the list? I mean there certainely is values of k at wich TREE(k) would overpower for example Meameamealokkapoowa Oompa of Loader's Number, that would be cool to add a such number 

Fluoroantimonic Acid (talk) 18:52, June 4, 2015 (UTC)Trifluoromethanesulfonic Acid

TREE(3) is the only value that is particularly notable, since it's the smallest nontrivial value of TREE(n) - TREE(1) and TREE(2) are 1 and 3 respectively. the next values aren't really in a different realm of numbers from TREE(3) if i'm not mistaken. the fish numbers are different, since each of them are really separately devised values and not just different outputs of a single function. Cookiefonster (talk) 19:24, June 4, 2015 (UTC)

Another thing is that other specific values of TREE(n) have never been (afaik) considered, so there is no reason to put different values of TREE into the list. LittlePeng9 (talk)