Mixing
explicit upper bound of TREE(3)
$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) = 2uparrow^{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?
combinatorics graph-theory computability big-numbers
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
$endgroup$
add a comment |
$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) = 2uparrow^{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?
combinatorics graph-theory computability big-numbers
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
$endgroup$
3
$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$
– Solomonoff's Secret
Jun 4 '16 at 16:39
add a comment |
$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) = 2uparrow^{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?
combinatorics graph-theory computability big-numbers
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
$endgroup$
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) = 2uparrow^{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?
combinatorics graph-theory computability big-numbers
combinatorics graph-theory computability big-numbers
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
edited Jun 4 '16 at 2:45
r.e.s.
7,66311953
7,66311953
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
asked Jun 3 '16 at 21:21
Solomonoff's SecretSolomonoff's Secret
3,63711233
3,63711233
3
$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$
– Solomonoff's Secret
Jun 4 '16 at 16:39
add a comment |
3
$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$
– Solomonoff's Secret
Jun 4 '16 at 16:39
3
3
$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$
$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$
$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$
– Solomonoff's Secret
Jun 4 '16 at 16:39
$begingroup$
@r.e.s. Thank you. I get way too little sleep :)
$endgroup$
– Solomonoff's Secret
Jun 4 '16 at 16:39
add a comment |
4 Answers
4
active
oldest
votes
$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.
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
$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
add a comment |
$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.
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
$endgroup$
$begingroup$
As far as I know, it is not known whether $F_{theta(Omega^omegaomega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{theta(Omega^omegaomega,0)}$, so $F_{theta(Omega^omegaomega,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
add a comment |
$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.
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
$endgroup$
add a comment |
$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.
edited Jan 25 at 23:15
Noah Harris
592316
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
$endgroup$
$begingroup$
Welcome to MSE. Your answer adds nothing new to the already existing answers.
$endgroup$
– José Carlos Santos
Jan 25 at 20:26
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1811602%2fexplicit-upper-bound-of-tree3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
$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
add a comment |
$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.
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
$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
add a comment |
$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.
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
$endgroup$
$ 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.
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
edited Jun 3 '16 at 21:43
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
answered Jun 3 '16 at 21:31
PeterPeter
48.9k1239136
48.9k1239136
$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
add a comment |
$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
$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$
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$
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
$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
add a comment |
$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.
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
$endgroup$
$begingroup$
As far as I know, it is not known whether $F_{theta(Omega^omegaomega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{theta(Omega^omegaomega,0)}$, so $F_{theta(Omega^omegaomega,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
add a comment |
$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.
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
$endgroup$
$begingroup$
As far as I know, it is not known whether $F_{theta(Omega^omegaomega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{theta(Omega^omegaomega,0)}$, so $F_{theta(Omega^omegaomega,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
add a comment |
$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.
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
$endgroup$
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.
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
answered Oct 22 '16 at 12:39
DeedlitDeedlit
6,0421723
6,0421723
$begingroup$
As far as I know, it is not known whether $F_{theta(Omega^omegaomega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{theta(Omega^omegaomega,0)}$, so $F_{theta(Omega^omegaomega,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
add a comment |
$begingroup$
As far as I know, it is not known whether $F_{theta(Omega^omegaomega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{theta(Omega^omegaomega,0)}$, so $F_{theta(Omega^omegaomega,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
$begingroup$
As far as I know, it is not known whether $F_{theta(Omega^omegaomega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{theta(Omega^omegaomega,0)}$, so $F_{theta(Omega^omegaomega,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
$begingroup$
As far as I know, it is not known whether $F_{theta(Omega^omegaomega,0)}$ is optimal. We just know (form Hyp cos) that there exists a ordering that gives approximately$F_{theta(Omega^omegaomega,0)}$, so $F_{theta(Omega^omegaomega,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
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$
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
$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
add a comment |
$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.
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
$endgroup$
add a comment |
$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.
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
$endgroup$
add a comment |
$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.
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
$endgroup$
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.
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
answered Feb 23 '17 at 20:48
Andreas WeiermannAndreas Weiermann
1391
1391
add a comment |
add a comment |
$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.
edited Jan 25 at 23:15
Noah Harris
592316
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
$endgroup$
$begingroup$
Welcome to MSE. Your answer adds nothing new to the already existing answers.
$endgroup$
– José Carlos Santos
Jan 25 at 20:26
add a comment |
$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.
edited Jan 25 at 23:15
Noah Harris
592316
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
$endgroup$
$begingroup$
Welcome to MSE. Your answer adds nothing new to the already existing answers.
$endgroup$
– José Carlos Santos
Jan 25 at 20:26
add a comment |
$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.
edited Jan 25 at 23:15
Noah Harris
592316
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
$endgroup$
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.
edited Jan 25 at 23:15
Noah Harris
592316
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
edited Jan 25 at 23:15
Noah Harris
592316
edited Jan 25 at 23:15
Noah Harris
592316
edited Jan 25 at 23:15
Noah Harris
592316
592316
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
answered Jan 25 at 20:09
Joey PetersJoey Peters
11
11
$begingroup$
Welcome to MSE. Your answer adds nothing new to the already existing answers.
$endgroup$
– José Carlos Santos
Jan 25 at 20:26
add a comment |
$begingroup$
Welcome to MSE. Your answer adds nothing new to the already existing answers.
$endgroup$
– José Carlos Santos
Jan 25 at 20:26
$begingroup$
Welcome to MSE. Your answer adds nothing new to the already existing answers.
$endgroup$
– José Carlos Santos
Jan 25 at 20:26
$begingroup$
Welcome to MSE. Your answer adds nothing new to the already existing answers.
$endgroup$
– José Carlos Santos
Jan 25 at 20:26
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1811602%2fexplicit-upper-bound-of-tree3%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$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$
– Solomonoff's Secret
Jun 4 '16 at 16:39