We know the weak tree function has growth rate \(\vartheta(\Omega^\omega)\) in FGH or HH. However, to find a good bound of TREE(3), it's not enough that we just know tree(n) is comparable to \(H_{\vartheta(\Omega^\omega)}(n)\). We should know how it works. Here I found some results about tree function.
- Sequences whose length comparable to \(H_{\vartheta(\Omega^\omega)}(n)\) (maybe not the winning sequences)
- A better bound for growth rate of TREE(n)
- A sequence of TREE(3) and a bound
We need a definition here for the second question.
tree(n)[]
Sequences started with (()()()...()()) can have length comparable to \(H_{\vartheta(\Omega^\omega)}(n)\). Now vertices have at most n children. Then it'll reduce to "all vertices have at most n-1 children", then "all vertices have at most n-2 children". Finally become a binary tree (but not ordered). It's at \(\varepsilon_0\) level (in HH).
If we get (()()) and at most n vertices, the next tree is ((...(())...)) with n+1 vertices. At the end we get () and at most 2n+1 vertices, at the same time \(H_{\omega}(n)=2n\), so we call (()()) has level \(\omega\).
More comparisons:
| tree | level |
|---|---|
| (()()) | \(\omega\) |
| ((()())) | \(\omega+1\) |
| (((()()))) | \(\omega+2\) |
| ((())()) | \(\omega2\) |
| (((()))()) | \(\omega3\) |
| ((()())()) | \(\omega^2\) |
| (((()())())) | \(\omega^2+1\) |
| (((()()))()) | \(\omega^2+\omega\) |
| (((())())()) | \(\omega^22\) |
| ((((()))())()) | \(\omega^23\) |
| (((()())())()) | \(\omega^3\) |
| ((((()())())())()) | \(\omega^4\) |
| ((())(())) | \(\omega^\omega\) |
| (((())(()))) | \(\omega^\omega+1\) |
| (((())(()))()) | \(\omega^\omega+\omega\) |
| ((((())(())))()) | \(\omega^\omega+\omega2\) |
| ((((())(()))())()) | \(\omega^\omega+\omega^2\) |
| (((()))(())) | \(\omega^\omega2\) |
| ((((())))(())) | \(\omega^\omega3\) |
| ((()())(())) | \(\omega^{\omega+1}\) |
| (((()()))(())) | \(\omega^{\omega+1}+\omega^\omega\) |
| (((())())(())) | \(\omega^{\omega+1}2\) |
| (((()())())(())) | \(\omega^{\omega+2}\) |
| ((((()())())())(())) | \(\omega^{\omega+3}\) |
| (((())(()))(())) | \(\omega^{\omega2}\) |
| ((((())(())))(())) | \(\omega^{\omega2}+\omega^\omega\) |
| ((((()))(()))(())) | \(\omega^{\omega2}2\) |
| ((((())(()))(()))(())) | \(\omega^{\omega3}\) |
| (((()))((()))) | \(\omega^{\omega^2}\) |
| ((((())))((()))) | \(\omega^{\omega^2}2\) |
| (((()()))((()))) | \(\omega^{\omega^2+1}\) |
| (((())(()))((()))) | \(\omega^{\omega^2+\omega}\) |
| ((((()))((())))((()))) | \(\omega^{\omega^22}\) |
| ((((())))(((())))) | \(\omega^{\omega^3}\) |
| ((()())(()())) | \(\omega^{\omega^\omega}\) |
| (((()()))(()())) | \(\omega^{\omega^\omega}2\) |
| (((())())(()())) | \(\omega^{\omega^\omega+1}\) |
| (((())(()))(()())) | \(\omega^{\omega^\omega+\omega}\) |
| (((()())(()()))(()())) | \(\omega^{\omega^\omega2}\) |
| (((()()))((()()))) | \(\omega^{\omega^{\omega+1}}\) |
| ((((()())))(((()())))) | \(\omega^{\omega^{\omega+2}}\) |
| (((())())((())())) | \(\omega^{\omega^{\omega2}}\) |
| ((((()))())(((()))())) | \(\omega^{\omega^{\omega3}}\) |
| (((()())())((()())())) | \(\omega^{\omega^{\omega^2}}\) |
| ((((()())()))(((()())()))) | \(\omega^{\omega^{\omega^2+1}}\) |
| ((((()()))())(((()()))())) | \(\omega^{\omega^{\omega^2+\omega}}\) |
| ((((())())())(((())())())) | \(\omega^{\omega^{\omega^22}}\) |
| ((((()())())())(((()())())())) | \(\omega^{\omega^{\omega^3}}\) |
| (((())(()))((())(()))) | \(\omega^{\omega^{\omega^\omega}}\) |
| ((((()))(()))(((()))(()))) | \(\omega^{\omega^{\omega^\omega2}}\) |
| ((((())(()))(()))(((())(()))(()))) | \(\omega^{\omega^{\omega^{\omega2}}}\) |
| ((((()))((())))(((()))((())))) | \(\omega^{\omega^{\omega^{\omega^2}}}\) |
| (((((())))(((()))))((((())))(((()))))) | \(\omega^{\omega^{\omega^{\omega^3}}}\) |
| (((()())(()()))((()())(()()))) | \(\omega^{\omega^{\omega^{\omega^\omega}}}\) |
| ((((())(()))((())(())))(((())(()))((())(())))) | \(\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}\) |
| ((((()())(()()))((()())(()())))(((()())(()()))((()())(()())))) | \(\omega^{\omega^{\omega^{\omega^{\omega^{\omega^\omega}}}}}\) |
Then, the first tree that has 3-children vertices is (()()()), which has level \(\varepsilon_0\). From \(\varepsilon_0\) to \(\varepsilon_1\) the (()()()) has no changes.
| tree | level |
|---|---|
| (()()()) | \(\varepsilon_0\) |
| ((()()())) | \(\varepsilon_0+1\) |
| ((()()())()) | \(\varepsilon_0+\omega\) |
| ((()()())(()())) | \(\varepsilon_0+\omega^{\omega^\omega}\) |
| ((()()())(()()())) | \(\varepsilon_02\) |
| (((()()()))(()()())) | \(\varepsilon_03\) |
| (((()()())())(()()())) | \(\varepsilon_0\omega=\omega^{\varepsilon_0+1}\) |
| ((((()()())()))(()()())) | \(\omega^{\varepsilon_0+1}+\varepsilon_0\) |
| ((((()()()))())(()()())) | \(\omega^{\varepsilon_0+1}2\) |
| ((((()()())())())(()()())) | \(\omega^{\varepsilon_0+2}\) |
| (((()()())(()))(()()())) | \(\omega^{\varepsilon_0+\omega}\) |
| (((()()())((())))(()()())) | \(\omega^{\varepsilon_0+\omega^2}\) |
| (((()()())(()()))(()()())) | \(\omega^{\varepsilon_0+\omega^\omega}\) |
| (((()()())(()()()))(()()())) | \(\omega^{\varepsilon_02}\) |
| ((((()()())(()()())))(()()())) | \(\omega^{\varepsilon_02}+\varepsilon_0\) |
| ((((()()()))(()()()))(()()())) | \(\omega^{\varepsilon_02}2\) |
| ((((()()())())(()()()))(()()())) | \(\omega^{\varepsilon_02+1}\) |
| ((((()()())(()()()))(()()()))(()()())) | \(\omega^{\varepsilon_03}\) |
| (((((()()()))(()()()))(()()()))(()()())) | \(\omega^{\varepsilon_03}2\) |
| (((((()()())(()()()))(()()()))(()()()))(()()())) | \(\omega^{\varepsilon_04}\) |
| (((()()()))((()()()))) | \(\omega^{\omega^{\varepsilon_0+1}}\) |
| ((((()()())))((()()()))) | \(\omega^{\omega^{\varepsilon_0+1}}2\) |
| (((()()())(()()()))((()()()))) | \(\omega^{\omega^{\varepsilon_0+1}+\varepsilon_0}\) |
| ((((()()())(()()()))(()()()))((()()()))) | \(\omega^{\omega^{\varepsilon_0+1}+\varepsilon_0}2\) |
| ((((()()()))((()()())))((()()()))) | \(\omega^{\omega^{\varepsilon_0+1}2}\) |
| (((((()()()))((()()())))((()()())))((()()()))) | \(\omega^{\omega^{\varepsilon_0+1}3}\) |
| ((((()()())))(((()()())))) | \(\omega^{\omega^{\varepsilon_0+2}}\) |
| (((()()())())((()()())())) | \(\omega^{\omega^{\varepsilon_0+\omega}}\) |
| ((((()()())()))(((()()())()))) | \(\omega^{\omega^{\varepsilon_0+\omega+1}}\) |
| ((((()()()))())(((()()()))())) | \(\omega^{\omega^{\varepsilon_0+\omega2}}\) |
| (((()()())(()()))((()()())(()()))) | \(\omega^{\omega^{\varepsilon_0+\omega^{\omega^\omega}}}\) |
| (((()()())(()()()))((()()())(()()()))) | \(\omega^{\omega^{\varepsilon_02}}\) |
| ((((()()())(()()())))(((()()())(()()())))) | \(\omega^{\omega^{\varepsilon_02+1}}\) |
| ((((()()()))(()()()))(((()()()))(()()()))) | \(\omega^{\omega^{\varepsilon_03}}\) |
| ((((()()())(()()()))(()()()))(((()()())(()()()))(()()()))) | \(\omega^{\omega^{\omega^{\varepsilon_02}}}\) |
| ((((()()())(()()()))((()()())(()()())))(((()()())(()()()))((()()())(()()())))) | \(\omega^{\omega^{\omega^{\omega^{\varepsilon_02}}}}\) |
Next ((())()()) has level \(\varepsilon_1\).
| tree | level |
|---|---|
| ((())()()) | \(\varepsilon_1\) |
| (((()))()()) | \(\varepsilon_2\) |
| ((()())()()) | \(\varepsilon_\omega\) |
| (((()())(()()))()()) | \(\varepsilon_{\omega^{\omega^\omega}}\) |
| ((()()())()()) | \(\varepsilon_{\varepsilon_0}\) |
| (((()()())(()()()))()()) | \(\varepsilon_{\varepsilon_02}\) |
| (((())()())()()) | \(\varepsilon_{\varepsilon_1}\) |
| (((()()())()())()()) | \(\varepsilon_{\varepsilon_{\varepsilon_0}}\) |
| ((())(())()) | \(\zeta_0\) |
| (((())(())())()()) | \(\varepsilon_{\zeta_0+1}\) |
| ((((())(())()))()()) | \(\varepsilon_{\zeta_0+2}\) |
| ((((())(())())((())(())()))()()) | \(\varepsilon_{\zeta_02}\) |
| ((((())(())())()())()()) | \(\varepsilon_{\varepsilon_{\zeta_0+1}}\) |
| (((()))(())()) | \(\zeta_1\) |
| (((())(())())(())()) | \(\zeta_{\zeta_0}\) |
| (((()))((()))()) | \(\varphi(3,0)\) |
| ((()())(()())()) | \(\varphi(\omega,0)\) |
| ((()()())(()()())()) | \(\varphi(\varepsilon_0,0)\) |
| (((()()())(()()())())((()()())(()()())())()) | \(\varphi(\varphi(\varepsilon_0,0),0)\) |
| ((())(())(())) | \(\Gamma_0\) |
| (((())(())(()))()()) | \(\varepsilon_{\Gamma_0+1}\) |
| ((((())(())(())))()()) | \(\varepsilon_{\Gamma_0+2}\) |
| ((((())(())(()))()())()()) | \(\varepsilon_{\varepsilon_{\Gamma_0+1}}\) |
| (((())(())(()))(())()) | \(\zeta_{\Gamma_0+1}\) |
| (((())(())(()))(()()())()) | \(\varphi(\varepsilon_0,\Gamma_0+1)\) |
| (((())(())(()))((())(())(()))()) | \(\varphi(\Gamma_0,1)\) |
| ((((())(())(()))((())(())(()))())(()()())()) | \(\varphi(\varepsilon_0,\varphi(\Gamma_0,1)+1)\) |
| ((((())(())(())))((())(())(()))()) | \(\varphi(\Gamma_0,2)\) |
| ((((())(())(()))((())(())(())))((())(())(()))()) | \(\varphi(\Gamma_0,\Gamma_0)\) |
| ((((())(())(()))()())((())(())(()))()) | \(\varphi(\Gamma_0,\varepsilon_{\Gamma_0+1})\) |
| ((((())(())(()))((())(())(()))())((())(())(()))()) | \(\varphi(\Gamma_0,\varphi(\Gamma_0,1))\) |
| ((((())(())(())))(((())(())(())))()) | \(\varphi(\Gamma_0+1,0)\) |
| ((((())(())(()))()())(((())(())(()))()())()) | \(\varphi(\varepsilon_{\Gamma_0+1},0)\) |
| ((((())(())(()))((())(())(()))())(((())(())(()))((())(())(()))())()) | \(\varphi(\varphi(\Gamma_0,1),0)\) |
| (((()))(())(())) | \(\Gamma_1\) |
| (((())(())(()))(())(())) | \(\Gamma_{\Gamma_0}\) |
| (((()))((()))(())) | \(\varphi(1,1,0)\) |
| (((())(())(()))((())(())(()))(())) | \(\varphi(1,\Gamma_0,0)\) |
| (((()))((()))((()))) | \(\varphi(2,0,0)\) |
| ((()()())(()()())(()()())) | \(\varphi(\varepsilon_0,0,0)\) |
| (((()()())(()()())(()()()))((()()())(()()())(()()()))((()()())(()()())(()()()))) | \(\varphi(\varphi(\varepsilon_0,0,0),0,0)\) |
| (()()()()) | \(\varphi(1,0,0,0)\) |
| ((()()()())()()) | \(\varepsilon_{\varphi(1,0,0,0)+1}\) |
| ((()()()())(())()) | \(\zeta_{\varphi(1,0,0,0)+1}\) |
| ((()()()())(()()()())()) | \(\varphi(\varphi(1,0,0,0),1)\) |
| ((()()()())(())(())) | \(\Gamma_{\varphi(1,0,0,0)+1}\) |
| ((()()()())(()()()())(()()()())) | \(\varphi(\varphi(1,0,0,0),0,1)\) |
| ((())()()()) | \(\varphi(1,0,0,1)\) |
| ((())(())()()) | \(\varphi(1,0,1,0)\) |
| ((())(())(())()) | \(\varphi(1,1,0,0)\) |
| ((())(())(())(())) | \(\varphi(2,0,0,0)\) |
| ((()()()())(()()()())(()()()())(()()()())) | \(\varphi(\varphi(1,0,0,0),0,0,0)\) |
| (()()()()()) | \(\varphi(1,0,0,0,0)\) |
| (()()()()()()) | \(\varphi(1,0,0,0,0,0)\) |
So that is a way up to SVO. Start with (()()...()()) then reduce them from bottom to top in those tables.
TREE(m,n) and TREE(n)[]
The weak tree function tree(n)=TREE(1,n). But what about TREE(2,n), TREE(3,n) and more? Here I found a way to reduce them. Use (), [] and {} for different color of vertices.
A [] can reduce to (()()...()()) so it has level SVO. And more,
| tree | level |
|---|---|
| [] | \(\vartheta(\Omega^\omega)\) |
| ([]) | \(\vartheta(\Omega^\omega)+1\) |
| (([])) | \(\vartheta(\Omega^\omega)+2\) |
| ([]()) | \(\vartheta(\Omega^\omega)+\omega\) |
| ([](()()()())) | \(\vartheta(\Omega^\omega)+\varphi(1,0,0,0)\) |
| ([][]) | \(\vartheta(\Omega^\omega)2\) |
| (([][])(()()())) | \(\vartheta(\Omega^\omega)2+\varepsilon_0\) |
| (([])[]) | \(\vartheta(\Omega^\omega)3\) |
| (([]())[]) | \(\omega^{\vartheta(\Omega^\omega)+1}\) |
| (([][])[]) | \(\omega^{\vartheta(\Omega^\omega)2}\) |
| (([])([])) | \(\omega^{\omega^{\vartheta(\Omega^\omega)+1}}\) |
| (([][])([][])) | \(\omega^{\omega^{\vartheta(\Omega^\omega)2}}\) |
| ([]()()) | \(\varepsilon_{\vartheta(\Omega^\omega)+1}\) |
| ([](())()) | \(\zeta_{\vartheta(\Omega^\omega)+1}\) |
| ([][]()) | \(\varphi(\vartheta(\Omega^\omega),1)\) |
| ([](())(())) | \(\Gamma_{\vartheta(\Omega^\omega)+1}\) |
| ([][][]) | \(\varphi(\vartheta(\Omega^\omega),0,1)\) |
| ([]()()()) | \(\varphi(1,0,0,\vartheta(\Omega^\omega)+1)\) |
| ([][][][]) | \(\varphi(\vartheta(\Omega^\omega),0,0,1)\) |
| ([][][][][]) | \(\varphi(\vartheta(\Omega^\omega),0,0,0,1)\) |
| [()] | \(\vartheta(\Omega^\omega+1)\) |
| [(())] | \(\vartheta(\Omega^\omega+2)\) |
| [(()()())] | \(\vartheta(\Omega^\omega+\varepsilon_0)\) |
| [[]] | \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega))\) |
| [([])] | \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega)+1)\) |
| [([][][])] | \(\vartheta(\Omega^\omega+\varphi(\vartheta(\Omega^\omega),0,1))\) |
| [[()]] | \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega+1))\) |
| [[[]]] | \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega+\vartheta(\Omega^\omega)))\) |
| [()()] | \(\vartheta(\Omega^\omega+\Omega)\) |
| [[()()]] | \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega+\Omega))\) |
| [([()()][()()][()()])] | \(\vartheta(\Omega^\omega+\varepsilon_{\vartheta(\Omega^\omega+\Omega)+1})\) |
| [[[()()]]] | \(\vartheta(\Omega^\omega+\vartheta(\Omega^\omega+\vartheta(\Omega^\omega+\Omega)))\) |
| [(())()] | \(\vartheta(\Omega^\omega+\Omega+1)\) |
| [[]()] | \(\vartheta(\Omega^\omega+\Omega+\vartheta(\Omega^\omega))\) |
| [[()()]()] | \(\vartheta(\Omega^\omega+\Omega+\vartheta(\Omega^\omega+\Omega))\) |
| [[[()()]()]()] | \(\vartheta(\Omega^\omega+\Omega+\vartheta(\Omega^\omega+\Omega+\vartheta(\Omega^\omega+\Omega)))\) |
| [(())(())] | \(\vartheta(\Omega^\omega+\Omega2)\) |
| [(()()())(()()())] | \(\vartheta(\Omega^\omega+\Omega\varepsilon_0)\) |
| [[][]] | \(\vartheta(\Omega^\omega+\Omega\vartheta(\Omega^\omega))\) |
| [[[][]][[][]]] | \(\vartheta(\Omega^\omega+\Omega\vartheta(\Omega^\omega+\Omega\vartheta(\Omega^\omega)))\) |
| [()()()] | \(\vartheta(\Omega^\omega+\Omega^2)\) |
| [(())()()] | \(\vartheta(\Omega^\omega+\Omega^2+1)\) |
| [(())(())()] | \(\vartheta(\Omega^\omega+\Omega^2+\Omega)\) |
| [(())(())(())] | \(\vartheta(\Omega^\omega+\Omega^22)\) |
| [[][][]] | \(\vartheta(\Omega^\omega+\Omega^2\vartheta(\Omega^\omega))\) |
| [()()()()] | \(\vartheta(\Omega^\omega+\Omega^3)\) |
| [[][][][]] | \(\vartheta(\Omega^\omega+\Omega^3\vartheta(\Omega^\omega))\) |
| [[][][][][]] | \(\vartheta(\Omega^\omega+\Omega^4\vartheta(\Omega^\omega))\) |
| {} | \(\vartheta(\Omega^\omega2)\) |
So I get some bound for TREE(m,n) functions:
Growth rate of TREE(2,n)\(\geq\vartheta(\Omega^\omega2)\)
Growth rate of TREE(3,n)\(\geq\vartheta(\Omega^\omega3)\)
and so on.
TREE(n) go across all the TREE(m,n) for constant m, so growth rate of TREE(n)\(\geq\vartheta(\Omega^\omega\omega)\).
However, those sequences are not the winning sequence, so I've no idea about the upper bound of TREE(n).
Update: This paper provided upper bounds for the order type of labeled trees, including TREE sequences. We got \(\text{TREE}(n)\approx f_{\vartheta(\Omega^\omega\omega)}(n)\) from that.
TREE(3)[]
While evaluating TREE(3) (not TREE(n)), it's important to have a good beginning. After some comparisons, I found that sequence as follow. Some parts are not the same as the order in the tables in part 1 and 2.
(And thanks to Deedlit's idea, I get a new version.)
- {}
- [[]]
- [()()]
- [(()())] - Notice that [()()] isn't a minor of [(()())], and this can improve a lot.
- [(((())))]
- (([((()))]))
- ([((()))][][])
- ([((()))][]()()) - Not the same as in the table.
- ([((()))]()()()())
- ([((()))](())(())())
- ([((()))](()()())()()) - Then reduce the (()()()) only. This will take tree(3) steps.
tree(3)+10. ([((()))]()()())
tree(3)+11. ([((()))][((()))](()tree(3)+1)) - Here the superscript means there're tree(3)+1 ()'s as children in a (()()...()()).
tree(tree(3)+1)+tree(3)+10. ([((()))][((()))]())
tree(tree(3)+1)+tree(3)+11. ([((()))][](()tree(tree(3)+1)+tree(3)+4))
tree(tree(3)+1)+tree(3)+12. ([((()))][]((())(())()tree(tree(3)+1)+tree(3)+1))
tree(tree(3)+1)+tree(3)+13. ([((()))][]((()()())()tree(tree(3)+1)+tree(3)+2))
tree(tree(3)+1)+tree(3)+14. ([((()))][](((())(()))()tree(tree(3)+1)+tree(3)+2))
tree(tree(3)+1)+tree(3)+15. ([((()))][]((((())())())()tree(tree(3)+1)+tree(3)+2))
tree(tree(3)+1)+tree(3)+16. ([((()))][](((((()())))())()tree(tree(3)+1)+tree(3)+2))
tree(tree(3)+1)+tree(3)+17. ([((()))][]((((((()()))())))()tree(tree(3)+1)+tree(3)+2))
tree(tree(3)+1)+tree(3)+18. ([((()))][]((((((()()))()))()tree(tree(3)+1)+tree(3)+2)()))
tree(tree(3)+1)+tree(3)+19. ([((()))][]((((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))))
tree(tree(3)+1)+tree(3)+20. ([((()))][(())](((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+21. ([((()))](([()]))(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+22. ([((()))]([()][()])(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+23. ([((()))]([()][][][])(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+24. ([((()))]([()][][]()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+25. ([((()))]([()][]()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+26. ([((()))]([()]()()()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+27. ([((()))]([()](())(())()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+tree(3)+28. ([((()))]([()](()()())()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))) - Again, the (()()()) takes tree(3) steps.
tree(tree(3)+1)+2tree(3)+27. ([((()))]([()]()()()()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+28. ([((()))]([()][](()tree(3)+4)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+29. ([((()))]([()][]((())(())()tree(3)+1)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+30. ([((()))]([()][]((()()())()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+31. ([((()))]([()][](((())(()))()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+32. ([((()))]([()][]((((())())())()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+33. ([((()))]([()][](((((()())))())()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+34. ([((()))]([()][]((((((()()))())))()tree(3)+2)()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+35. ([((()))]([()][]((((((()()))()))()tree(3)+2)())()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+36. ([((()))]([()][]((((((((()()))()))()tree(3)+2))))()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
tree(tree(3)+1)+2tree(3)+37. ([((()))]([()]([][])(((((((()()))()))()tree(3)+2)))()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2))))
Then, changes happen on the subtree ([][]), and this part will be
tree(tree(3)+1)+2tree(3)+38. ([]()())
tree(tree(3)+1)+2tree(3)+39. ([](()()))
tree(tree(3)+1)+2tree(3)+40. ([](((()))))
tree(tree(3)+1)+2tree(3)+41. (([]())((())))
tree(tree(3)+1)+2tree(3)+42. (((([])))((())))
tree(tree(3)+1)+2tree(3)+43. (((([]))((())))())
tree(tree(3)+1)+2tree(3)+44. (((((([]))((()))))))
tree(tree(3)+1)+2tree(3)+45. ((((([]))((())))))
tree(tree(3)+1)+2tree(3)+46. (((([]))((()))))
tree(tree(3)+1)+2tree(3)+47. ((([]))((())))
tree(tree(3)+1)+2tree(3)+48. ((((([])((())))())(()))(()))
tree(tree(3)+1)+2tree(3)+49. ((((((([])((()))))))(()))(()))
tree(tree(3)+1)+2tree(3)+50. ((((((([])((())))))(()))())(()))
tree(tree(3)+1)+2tree(3)+51. ((((((((([])((())))))(())))))(()))
tree(tree(3)+1)+2tree(3)+52. ((((((((([])((())))))(()))))(()))())
tree(tree(3)+1)+2tree(3)+53. ((((((((((([])((())))))(()))))(())))))
tree(tree(3)+1)+2tree(3)+54. (((((((((([])((())))))(()))))(()))))
tree(tree(3)+1)+2tree(3)+55. ((((((((([])((())))))(()))))(())))
tree(tree(3)+1)+2tree(3)+56. (((((((([])((())))))(()))))(()))
tree(tree(3)+1)+2tree(3)+57. ((((((((((([])((())))))(())))(()))())())())())
tree(tree(3)+1)+2tree(3)+58. ((((((((((((([])((())))))(())))(())))))())())())
tree(tree(3)+1)+2tree(3)+59. (((((((((((((([])((())))))(())))(()))))())))())())
tree(tree(3)+1)+2tree(3)+60. ((((((((((((((([])((())))))(())))(()))))()))())))())
tree(tree(3)+1)+2tree(3)+61. (((((((((((((((([])((())))))(())))(()))))()))()))())))
tree(tree(3)+1)+2tree(3)+62. ((((((((((((((([])((())))))(())))(()))))()))()))()))
tree(tree(3)+1)+2tree(3)+63. (((((((((((((([])((())))))(())))(()))))()))()))())
tree(tree(3)+1)+2tree(3)+64. ((((((((((((((((((([])((())))))(())))(()))))()))())())))))))
tree(tree(3)+1)+2tree(3)+70. ((((((((((((([])((())))))(())))(()))))()))())())
tree(tree(3)+1)+2tree(3)+71. (((((((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))))))())
tree(tree(3)+1)+2tree(3)+72. ((((((((((((((((((((((((((([])((())))))(())))(()))))())()))))))))))))))())))
tree(tree(3)+1)+2tree(3)+74. ((((((((((((((((((((((((([])((())))))(())))(()))))())()))))))))))))))())
tree(tree(3)+1)+2tree(3)+75. (((((((((((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))))())))))))
tree(tree(3)+1)+2tree(3)+81. (((((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))))())
tree(tree(3)+1)+2tree(3)+96. ((((((((((((((((((((((([])((())))))(())))(()))))())()))))))))))))())
tree(tree(3)+1)+2tree(3)+127. (((((((((((((((((((((([])((())))))(())))(()))))())())))))))))))())
tree(tree(3)+1)+2tree(3)+65589. (((((((((((([])((())))))(())))(()))))())())())
Now I start using Hardy hierarchy. Notice that it need one step to "expand" so in that hierarchy it's actually \(H_\alpha(n)=H_{\alpha[n]}(n)+1>H_{\alpha[n]}(n)\). So HH is actually slightly smaller.
\(>tree(tree(3)+1)+H_{\omega^3}(65534)\). ((((((((((([])((())))))(())))(())))())())())
\(>tree(tree(3)+1)+H_{\omega^32}(65534)\). (((((((((([])((())))))(())))(()))())())())
\(>tree(tree(3)+1)+H_{\omega^33}(65534)\). ((((((([])((())))))(())))(()))
\(>tree(tree(3)+1)+H_{\omega^\omega+\omega^33}(65534)\). (((((([])((())))))(()))(()))
\(>tree(tree(3)+1)+H_{\omega^{\omega2}+\omega^\omega+\omega^33}(65534)\). ((((([])((()))))(()))(()))
\(>tree(tree(3)+1)+H_{\omega^{\omega2}2+\omega^\omega+\omega^33}(65534)\). (((([])((())))(()))(()))
\(>tree(tree(3)+1)+H_{\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). (([])((())))
\(>tree(tree(3)+1)+H_{\omega^{\omega^2}+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). ([]((())))
\(>tree(tree(3)+1)+H_{\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). []
Now the whole tree becomes ([((()))]([()][](((((((()()))()))()tree(3)+2)))()())(((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))). Then changes happen on the ([()][](((((((()()))()))()tree(3)+2)))()()). Notice that the subtree (((((((()()))()))()tree(3)+2))) has level \(\vartheta(\Omega^{tree(3)+2})\cdot(\omega^2+\omega+1)+2\), and once it decreases one vertix the [] will change into ([][]...[][]) with as many []'s as possible - at level \(\vartheta(\Omega^\omega+1)\). So
- \(>H_{\vartheta(\Omega^\omega+1)\vartheta(\Omega^{tree(3)+2})\cdot(\omega^2+\omega+1)+\vartheta(\Omega^\omega+1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). ([()][]()()())
Then it reduce to ([()][][](()()...())) with as many ()'s as possible - at level \(\vartheta(\Omega^\omega)\), so
- \(>H_{\vartheta(\Omega^\omega+1)^2\vartheta(\Omega^\omega)+\vartheta(\Omega^\omega+1)\vartheta(\Omega^{tree(3)+2})\cdot(\omega^2+\omega+1)+\vartheta(\Omega^\omega+1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). [()]
Now the whole tree becomes ([((()))][()](((((((()()))()))()tree(tree(3)+1)+tree(3)+2)))). Notice that the subtree (((((((()()))()))()tree(tree(3)+1)+tree(3)+2))) has level \(\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+2})\cdot(\omega^2+\omega+1)+2\), and once it decreases one vertix the [()] will change into ([(())][][]...[][]) with as many []'s as possible - at level \(\vartheta(\Omega^\omega+3)\), so
\(>H_{\vartheta(\Omega^\omega+3)\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+2})\cdot(\omega^2+\omega+1)+\vartheta(\Omega^\omega+3)2+\vartheta(\Omega^\omega+1)^2\vartheta(\Omega^\omega)+\vartheta(\Omega^\omega+1)\vartheta(\Omega^{tree(3)+2})\cdot(\omega^2+\omega+1)+\vartheta(\Omega^\omega+1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\). ([((()))][()]())
At last the tree reduce to ([((()))][]()), ([((()))]()()), ([((()))]([(())][][][]...[][])), ([((()))]()), ([((()))]), [((()))], (). But those are only at level \(\vartheta(\Omega^\omega+3)2\), which is nothing comparing to \(\vartheta(\Omega^\omega+3)\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+2})\cdot(\omega^2+\omega+1)\).
Finally, I get TREE(3)>\(H_{\vartheta(\Omega^\omega+3)\vartheta(\Omega^{tree(tree(3)+1)+tree(3)+2})\cdot(\omega^2+\omega+1)+\vartheta(\Omega^\omega+3)2+\vartheta(\Omega^\omega+1)^2\vartheta(\Omega^\omega)+\vartheta(\Omega^\omega+1)\vartheta(\Omega^{tree(3)+2})\cdot(\omega^2+\omega+1)+\vartheta(\Omega^\omega+1)2+\omega^{\omega^2}2+\omega^{\omega2}3+\omega^\omega+\omega^33}(65534)\), and a more simple but slightly weaker bound is TREE(3)>\(f_{\vartheta(\Omega^\omega+3)+\vartheta(\Omega^\omega)}(tree(tree(3)))\).
Who has a better idea?