Let's start with these two questions on MathOverflow. Or perhaps let's start with the reference that gets mentioned in these: "The Nesting and Roosting Habits of The Laddered Parenthesis", by R. K. Guy and J. L. Selfridge. Or one of the papers it refers to, "The Number of Numerical Outcomes of Iterated Powers", by F. Göbel and R. P. Nederpelt.
Whatever. Obviously, this sort of thing can be asked about whole numbers (considered in Guy & Selfridge), nonnegative reals (considered in Guy & Selfridge, and in the first question above), ordinals (considered in the second question above), cardinals... anything else? Probably. Guy & Selfridge notes that you could plug in x=-1, though there's only ever one thing you can get out. The OEIS has sequences for ω, 2 through 10, and also for i, where it uses principal value, but I don't like principal values so I'll ignore that. Still I guess it would work for anything sufficiently like the reals -- Wikipedia mentions the idea of an "exponentially closed field" (though I don't see the point of the restriction on the size of E(1)). In particular the surreals I guess. But this is getting silly, let's stick to reals, ordinals, and cardinals.
Question 1: If a is a whole number, what's the asymptotic behavior of Fa(n)? Vladimir Reshetnikov asks this question of Fω(n), so you would think this meant Guy & Selfridge had already covered it for finite a, but I don't see it in there, nor in the references. (Though what they do say I think may be enough to determine it for a=2? Unsure.)
Non-question 2: What about infinite cardinals? Well, OK, I know the answer to this one because it's easy. If λ is an infinite cardinal, then for n≥2, Fλ(n)=n-1, because the values you get are exactly בk(λ) for 1≤k≤n-1. (Yes, yes, assuming choice.)
(Glad that showed up right; I was afraid of BIDI issues. Unrelatedly -- Wikipedia claims that in ZF without choice, you can still prove that given any two cardinals κ and μ, there exists some ordinal α such that κ≤בα(μ). I find that surprising, and have to wonder why that's true, but I'm certainly not going to take the time to learn about it now.)
Question 3: At the end of their paper, Guy & Selfridge make the following remark: "There seems to be no simple characterization of what we might call exponential numbers, which lead to coincidence of value of k-level expressions. ... The exponential numbers include all algebraic numbers, but do not form a field." So, uh, how do they know this? It doesn't look to me like this was anywhere in the paper. Göbel and Nederpelt show that the set of these exponential numbers is countable, but they don't provide an explicit non-exponential number. OK, now that I think about it, it's not too hard to see why all algebraic numbers are in, but how on earth do they know it's not a field? Do they just mean it's not necessarily a field? I guess strictly speaking it doesn't include negatives, actually, but I guess we can throw those in. Hold on -- I was thinking of problems with inversion, but is it even closed under addition, and, to the extent it makes sense, subtraction? Multiplication? What's going on there?
-Harry
Whatever. Obviously, this sort of thing can be asked about whole numbers (considered in Guy & Selfridge), nonnegative reals (considered in Guy & Selfridge, and in the first question above), ordinals (considered in the second question above), cardinals... anything else? Probably. Guy & Selfridge notes that you could plug in x=-1, though there's only ever one thing you can get out. The OEIS has sequences for ω, 2 through 10, and also for i, where it uses principal value, but I don't like principal values so I'll ignore that. Still I guess it would work for anything sufficiently like the reals -- Wikipedia mentions the idea of an "exponentially closed field" (though I don't see the point of the restriction on the size of E(1)). In particular the surreals I guess. But this is getting silly, let's stick to reals, ordinals, and cardinals.
Question 1: If a is a whole number, what's the asymptotic behavior of Fa(n)? Vladimir Reshetnikov asks this question of Fω(n), so you would think this meant Guy & Selfridge had already covered it for finite a, but I don't see it in there, nor in the references. (Though what they do say I think may be enough to determine it for a=2? Unsure.)
Non-question 2: What about infinite cardinals? Well, OK, I know the answer to this one because it's easy. If λ is an infinite cardinal, then for n≥2, Fλ(n)=n-1, because the values you get are exactly בk(λ) for 1≤k≤n-1. (Yes, yes, assuming choice.)
(Glad that showed up right; I was afraid of BIDI issues. Unrelatedly -- Wikipedia claims that in ZF without choice, you can still prove that given any two cardinals κ and μ, there exists some ordinal α such that κ≤בα(μ). I find that surprising, and have to wonder why that's true, but I'm certainly not going to take the time to learn about it now.)
Question 3: At the end of their paper, Guy & Selfridge make the following remark: "There seems to be no simple characterization of what we might call exponential numbers, which lead to coincidence of value of k-level expressions. ... The exponential numbers include all algebraic numbers, but do not form a field." So, uh, how do they know this? It doesn't look to me like this was anywhere in the paper. Göbel and Nederpelt show that the set of these exponential numbers is countable, but they don't provide an explicit non-exponential number. OK, now that I think about it, it's not too hard to see why all algebraic numbers are in, but how on earth do they know it's not a field? Do they just mean it's not necessarily a field? I guess strictly speaking it doesn't include negatives, actually, but I guess we can throw those in. Hold on -- I was thinking of problems with inversion, but is it even closed under addition, and, to the extent it makes sense, subtraction? Multiplication? What's going on there?
-Harry
