42
$\begingroup$

This is a follow-up to my old question Number of distinct values taken by $x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x$ with parentheses inserted in all possible ways.

In the following let us assume $n$ to be a positive integer, and all other variables to be positive reals. Let $a\hat{\phantom{\hat{}}}b$ denote exponentiation $a^b$.

The number of distinct $\mathbb{R}^+\to\mathbb{R}^+$ functions obtained from the expression $$\underbrace{x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x}_{n\text{ occurences of }x}\tag1$$ by inserting parentheses in all possible ways depends on $n$ and is given by the OEIS sequence A000081. Note that different parenthesizations can result in the same function, e.g.

$$(x\hat{\phantom{\hat{}}}x)\hat{\phantom{\hat{}}}(x\hat{\phantom{\hat{}}}x)=(x\hat{\phantom{\hat{}}}(x\hat{\phantom{\hat{}}}x))\hat{\phantom{\hat{}}}x.\tag2$$

If instead of considering functions, we fix some value of $x$, and ask about the number of distinct numeric outcomes of the expression $(1)$ for all possible parenthesizations, then, depending on the value of $x$ we fixed, the result can be either A000081 (in this case we call the value of $x$ generic), or a slower growing sequence.

For example, the number $2$ is not generic, because the corresponding sequence is A002845 due to some identities specific to the number $2$, e.g.

$$2\hat{\phantom{\hat{}}}(2\hat{\phantom{\hat{}}}2)=(2\hat{\phantom{\hat{}}}2)\hat{\phantom{\hat{}}}2.\tag3$$

Actually, it is not difficult to see that no positive integer is generic. Likewise, $\sqrt2$ is not generic. Furthermore, it can be proved that no positive algebraic number is generic.

Questions:

  • Can we prove that $2^{\sqrt2}$ is generic?
  • Can we find an explicit$^*$ computable generic number?

One might think that a plausible candidate for a generic number could be $\pi$, but, unfortunately, we do not even know yet if $\pi^{\pi^{\pi^\pi}}$ is an integer.


$^*$ By explicit I mean something that can be constructed from algebraic numbers and known $^{**}$ constants, elementary and known special functions, or an isolated root of an equation constructed from those constants and functions.

$^{**}$ known means they appeared in published books or reviewed papers.


References:

  • R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876. ᵖᵈᶠ
  • F. Göbel and R. P. Nederpelt, The number of numerical outcomes of iterated powers, Amer. Math. Monthly, 80 (1971), 1097-1103. ᵖᵈᶠ
$\endgroup$
24
  • 7
    $\begingroup$ @JosephO'Rourke: All but countably many positive reals are generic, as two distinct analytic functions can only intersect at countably many points. $\endgroup$ Aug 22, 2013 at 23:26
  • 1
    $\begingroup$ Are the points of agreement between two such (distinct) functions isolated? Must there be only finitely many points of agreement? If so, it follows that every non-generic point is computable, or put another way: every non-computable number is generic. $\endgroup$ Aug 23, 2013 at 12:20
  • 3
    $\begingroup$ It it possible that 2 non-generic numbers produce the same sequence? $\endgroup$
    – TauMu
    Aug 27, 2013 at 19:01
  • 2
    $\begingroup$ How do we know when two exponential towers define the same function on $\mathbb{R}^+$? Do all such identities follow from the ususal "Highschool" axioms, or are there "exotic" identities? A. Wilkie has shown that for terms over the full exponential semiring there are indeed exotic identities> $\endgroup$ Sep 17, 2013 at 4:38
  • 1
    $\begingroup$ @SJR, I think it is fine to keep your post up, since the OP does not give the argument, and your argument is nice. Just point out that it is mentioned in the OP, but you are fleshing that out. $\endgroup$ Sep 19, 2013 at 15:24

2 Answers 2

17
+100
$\begingroup$

Your first question can be taken with several senses, from weak to strong. Let us understand your "explicit" terminology to mean "computable".

  • (weak version) Is there a computable generic value?

  • (medium) Can we give a specific algorithm for computing a generic value?

  • (strong) Can we identify a computable generic value that we can also understand in a simple way, apart from the property of it being a generic value?

Probably you had something like the strong version in mind when asking your question. But in order to make some small progress, let me point out that we can get affirmative answers to the weak and medium versions of the question. This amounts, in effect, to a pure existence proof that there is an explicit generic value. Let us say that $x$ is fully generic if it is generic with respect to your expressions for all values of $n$ (not just expressions of the same length), so that $f(x)\neq g(x)$ for any two of your functions, provided $f\neq g$.

Theorem. There is a computable fully generic value.

Proof. Observe that functions corresponding to any of your expressions is continuous, and furthermore, they have computable moduli of continuity (that is, for any of them, at any rational input value, we can compute sufficient $\delta$ from $\epsilon=\frac 1n$ for continuity).

Next, I believe that distinct functions arising from your expressions never agree on an interval of positive real input values $x$. (Please let me know if this is wrong; I will defer to experts.)

It follows that there is a computable procedure to enumerate the pairs of your expressions that give rise to distinct functions: simply evaluate on more and more rational number inputs, until the inequality is detected. (Perhaps one would hope to computably decide equality of expressions as well, but I don't need this.)

Now, we construct a computable $x$ in stages. At any stage $k$, we have made a promise to a certain rational approximation $r_k$ to the value $x$ we are computing, with a certain promise of accuracy $\delta_k$, so that $x$ will be within $\delta_k$ of $r_k$. In the background, we have been running the computable algorithm to enumerate the pairs of expressions corresponding to distinct functions. We now take the $k^{th}$ such pair that we have found, $f$ and $g$. Since they are distinct, they will disagree on some rational value within $\delta_k$ of $r_k$, and we can computably find such a value. Using the $\epsilon$ value revealing the difference between $f(r_{k+1})$ and $g(r_{k+1})$, we can compute a new accuracy $\delta_{k+1}$ that will ensure $f(x)\neq g(x)$ for any $x$ within $\delta_{k+1}$ of $r_{k+1}$. This is the new approximation to $x$, and we proceed.

Thus, we diagonalize against all the pairs of distinct expressions, and thereby compute rational approximations to a value $x$ that will resolve all the expressions as distinct, provided that those expressions in fact correspond to distinct functions. So $x$ is computable and fully generic. QED

I know this answer is not really what you want, which is a specific number that you already knew about in some simple way, like the candidate $2^{\sqrt{2}}$ that you mentioned. My reply to this objection is to point out that there is a widespread phenomenon in computability theory — some call it the "If you build it, they will come" phenomenon — that if one wants to prove that there is an explicit example of something, then often you've got to just build the thing to order.

Meanwhile, I will hope along with you that someone comes through with a solution to the strong formulation of the question.

Let me also add that the theorem obviously generalizes to cover genericity with respect to much larger collections of computable functions. For any computable listing of computable functions on $\mathbb{R}$ (in the sense of computable analysis) with computable moduli of continuity, such that distinct functions are revealed as distinct on rationals in any interval, then there will be a computable real $x$ resolving them all as different.

Update. Following the ideas in the comments:

Theorem. Every non-computable real number is fully generic.

Proof. This is a consequence of the fact that the points of agreement between two of your expressions, if they are not everywhere in agreement, are isolated. And since these are computable functions with computable moduli of continuity, it follows that we can compute these points of agreement. (See the question Intermediate value theorem on computable reals for further discussion of this and similar issues.) So any violation of full genericity occurs only at a computable real. QED

So any non-computable real is fully generic, and many such reals qualify under your definition of "explicit". In particular:

  • The number $0'$, which is the binary sequence encoding the halting problem.

  • Kleene's $\mathcal{O}$, which can be viewed as a binary sequence corresponding to representations of the computable ordinals.

  • The number $0^{(\omega)}$, which is the binary sequence encoding the true theorems of arithmetic.

  • The number $0^{\triangledown}$, which is the binary sequence encoding the halting problem for infinite time Turing machines.

  • The number $0^\sharp$.

  • The number $0^\dagger$.

None of these is computable and so each of them is fully generic, as well as explicit in the sense you described, since indeed, many of them have their own Wikipedia pages. And there are many more that would seem to qualify, at least formally, as known constants under your definition. The field of computability theory has thousands of published examples of explicit constructions of binary sequences that are not computable, but which are the limit of a computably enumerable sequence of rational approximations from below, and all of these will be fully generic.

Probably the right response to this, as you hinted in the comments, is that you only want to consider computable constants in your definition of explicit.

$\endgroup$
7
  • $\begingroup$ Thanks, Joel! Your definition of fully generic seems to be exactly what I meant by just generic (the corresponding sequence indexed by $n$ is A000081). Doesn't it follow from the wording I used? Yes, I meant a stronger meaning of explicit: something that can be expressed using algebraic numbers and known constants, elementary and known special functions (known means they appear in published books or reviewed papers) or, at least, a symbolic sum or integral (even without a known closed form), or an isolated root of an equation constructed using constants and functions mentioned above. $\endgroup$ Aug 23, 2013 at 19:43
  • 1
    $\begingroup$ It seems to me to be conceivable that a number $x$ could be generic in your sense, with that sequence, but still some expression of length $m$ is equal at $x$ to an expression of length $n\neq m$, even though expressions of the same length are all different. Whether there are such $x$'s is the difference between your genericity notion and what I called fully generic. $\endgroup$ Aug 23, 2013 at 20:15
  • $\begingroup$ Ah, now I see. I misunderstood your definition at first. Thanks! $\endgroup$ Aug 23, 2013 at 20:21
  • $\begingroup$ Joel, your answer is great! But I still hope to see a computable generic number that, as you put it, we already knew about in some simple way, so I started a bounty on this question. $\endgroup$ Aug 26, 2013 at 21:03
  • $\begingroup$ Good, I hope that we'll find a more concrete answer. $\endgroup$ Aug 26, 2013 at 23:04
13
+200
$\begingroup$

Two observations:

  1. Not every transcendental is generic. Indeed the real solution $r$ of the equation $x^x=2$ is not generic because $r$ satisfies $$x^{x^{x^x}}=\left( x^x\right)^x,$$ and $r$ is transcendental by the Gelfond-Schneider theorem.

  2. Here is an argument showing that no positive real algebraic is generic (by which I mean that every positive real algebraic satisfies an equation between two exponential towers that have the same number of $x$'s and that do not define the same functions on $\mathbb{R}^+$.) This is mentioned in the original problem but maybe it would be nice to put up a proof here. It seems quite significant to me that 'generic' is a strengthening of 'transcendental'.

Rather than give a formal proof of the claim, I'll present an example that should make the general argument clear. Let $r$ be a solution of the polynomial equation $x^2-3x-2=0$. To prove that $r$ is not generic, first write the equation as

$$xx=x+x+x+1+1.$$ (In general, construct an equation made from additions and multiplications, all of whose coefficients are 1.)

Equating $x$ raised to the left-hand-side and $x$ raised to the right-hand-side, we obtain the following non-identity (also satisfied by $r$)

$$(x^x)^x=(x^x)(x^x)(x^x)xx.$$

Doing the same thing with the last equation, we get

$$x^{(x^x)^x}=\left(\left(\left(\left(x^{(x^x)}\right)^{(x^x)}\right)^{(x^x)}\right)^x\right)^x.$$

Now call the left and right hand sides of the last equation $a$ and $b$. Then $r$ satisfies the equation $a^b=b^a$, and both $a^b$ and $b^a$ have the same number of $x$'s. Furthermore $a^b$ and $b^a$ cannot define the same function. This follows from the calculus problem to the effect that if $u$ and $v$ are greater than $e$ (the base of the natural logarithm) and if $u^v=v^u$, then $u=v$.

$\endgroup$
8
  • 1
    $\begingroup$ +1. Meanwhile, a small quibble: you are saying "generic", but your examples are really about what I had called "fully generic" in my answer, because the towers do not involve exactly the same number of $x$'s. $\endgroup$ Sep 19, 2013 at 16:14
  • $\begingroup$ @SJR "not generic" is a stricter requirement than "not fully generic". $\endgroup$ Sep 19, 2013 at 17:43
  • $\begingroup$ But have you straightened it out? You've only provided equations showing that $r$ is not fully generic. But further work would be required to show that $r$ is not generic. $\endgroup$ Sep 19, 2013 at 18:14
  • 4
    $\begingroup$ @Joel: You're absolutely right -- I wasn't clear about your distinction. Here's the argument that $r$ is not generic in the sense that you mean. Suppose the left and right sides of my last equation are $a$ and $b$. Then $r$ satisfies the equation $a^b=b^a$, and now the number of $x$'s is the same on both sides. Furthermore, $a^b$ and $b^a$ cannot define the same function: This follows from the calculus problem that if $u$ and $v$ are greater than $e$ (the base of the natural logarithm) and $u^v=v^u$ then $u=v$. $\endgroup$ Sep 19, 2013 at 19:26
  • $\begingroup$ That is great! This argument seems almost to show that full genericity is the same as genericity! Can you push it harder to get that result? Then we would really have only one genericity concept. $\endgroup$ Sep 19, 2013 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.