MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\alpha\in\mathbf{Ord}$ and $n\in\mathbb{N}^+$.

Let $F_\alpha(n)$ be the number of distinct values taken by ordinal exponentiation $\underbrace{\alpha \hat{\phantom{\hat{}}} \alpha \hat{\phantom{\hat{}}} \dots \hat{\phantom{\hat{}}} \alpha}_\text{n times}$ with parentheses inserted in all possible ways.

The case $\alpha<\omega$ (i.e. natural numbers) was studied in "The Nesting and Roosting Habits of The Laddered Parenthesis", by R. K. Guy and J. L. Selfridge. Here I am interested in a case when $\alpha\ge\omega$.

Questions: Does the sequence $F_\alpha(n)$ depend on $\alpha$ in this case? Is there a simple closed form formula, recurrence relation or generating function for this sequence? What can be said about its asymptotic growth? What is $\lim\limits_{n\to\infty}\frac{F_\alpha(n+1)}{F_\alpha(n)}$? Do odd and even numbers occur infinitely often in the sequence?

$F_\omega(n)$ is given in A199812: $1, 1, 2, 5, 13, 32, 79, 193, 478, 1196, 3037, 7802, 20287, 53259, 141069, 376449, 1011295, \dots$

It is bounded by Catalan numbers $\frac{(2n-2)!}{n! (n-1)!}$. The first difference occurs at $n=5$ because among $14$ possible parenthesizations there are only $13$ distinct ordinals: $(((\omega^\omega)^\omega)^\omega)^\omega < ((\omega^\omega)^\omega)^{\omega^\omega} < ((\omega^\omega)^{\omega^\omega})^\omega < ((\omega^{\omega^\omega})^\omega)^\omega < (\omega^{\omega^\omega})^{\omega^\omega} < (\omega^\omega)^{(\omega^\omega)^\omega} < $ $(\omega^{(\omega^\omega)^\omega})^\omega < \omega^{((\omega^\omega)^\omega)^\omega} < \pmb{(\omega^\omega)^{\omega^{\omega^\omega}} = \omega^{(\omega^\omega)^{\omega^\omega}}} < (\omega^{\omega^{\omega^\omega}})^\omega < \omega^{(\omega^{\omega^\omega})^\omega} < \omega^{\omega^{(\omega^\omega)^\omega}} < \omega^{\omega^{\omega^{\omega^\omega}}}$

share|cite|improve this question
The two conjectures stated at the OEIS page might help: "It appears that any transfinite ordinal gives the same sequence. It appears that 2nd differences of this sequence give A174145 (starting from offset 2)." – Will Sawin Jul 29 '12 at 20:22
up vote 11 down vote accepted

The sequence $F_{\alpha}(n)$ indeed does not depend on $\alpha$ when $\alpha \geq \omega$. This question is closely related to this other question, and I will refer to my answer in that question.

Let $S_\alpha(n)$ be the set of ordinals defined by $\alpha ^ {\alpha ^ {\cdots ^ \alpha}}$ with all possible arrangements of parentheses. Since $\alpha = \alpha^{\alpha^0}$ and $(\alpha^{\alpha ^ \beta})^{\alpha^{\alpha^\gamma}} = \alpha^{\alpha ^ {\beta + \alpha^\gamma}}$, every element of $S_\alpha(n)$ is of the form $\alpha^{\alpha ^ \beta}$. So we define $T_\alpha (n) = \lbrace \beta | \alpha^{\alpha^\beta} \in S_\alpha(n) \rbrace$. We observe that $T_\alpha(0) = \lbrace 0 \rbrace$ and $T_\alpha(n) = \lbrace \beta + \alpha^\gamma | \beta \in T_\alpha(i), \gamma \in T_\alpha(j), i + j = n - 1 \rbrace$.

From my answer to the other question, we observe that $T_\alpha(n)$ is contained in the set $E(\alpha)$, which I refer to as the "exponential polynomials over the base $\alpha$". For each element $\beta$ of $E(\alpha)$, we can write $\beta$ in the iterative normal form to the base $\alpha$, which I describe as follows:

0 is represented as 0

$\beta$ is represented as $\alpha^{\beta_1} + \alpha^{\beta_2} + \ldots + \alpha^{\beta_n}$, where $\beta_1 \geq \beta_2 \geq \ldots \geq \beta_n$ and each $\beta_i$ is itself represented in iterative normal form.

We claim that, for any n and any $\alpha, \beta \geq \omega$, $T_\alpha(n)$, when written in iterative normal form, is the same set as $T_\beta(n)$, except the base $\beta$ is replaced everywhere it appears by $\alpha$. If we let $f(\gamma)$ be the ordinal obtained by replacing the base $\beta$ by $\alpha$ everywhere in the iterative normal form of $\gamma$, our claim amounts to $T_{\alpha}(n) = f(T_\beta(n))$. From our above expression for $T_\alpha(n)$, we see that it suffices to show that $f(\gamma + \beta^\delta) = f(\gamma) + \alpha^{f(\delta)}$ for any $\gamma, \delta \in E(\beta)$.

Let $\gamma = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_n}$. Let $m$ be the largest index such that $\gamma_m \geq \delta$. Then we claim that

$\gamma + \beta^\delta = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_m} + \beta^\delta$

(note that this is in iterative normal form, provided that $\gamma_i$ and $\delta$ are.)

First we prove:

Lemma. If $\beta, \mu, \nu$ are any ordinals such that $\mu < \nu$, then $\beta^\mu + \beta^\nu = \beta^\nu$.

Proof: Let $\beta = \omega^{\beta_1} + \omega^{\beta_2} + \ldots + \omega^{\beta_n}$ be the Cantor Normal Form for $\beta$. Then the leading term of the Cantor Normal Form of $\beta^\mu$ will be $\omega^{\beta_1 \mu}$, i.e.

$\beta^\mu = \omega^{\xi_1} + \omega^{\xi_2} + \ldots + \omega^{\xi_m}$ where $\xi_i \leq \beta_1 \mu$.

Since $\omega$ is a principal ordinal, for $\mu < \nu, \omega^\mu + \omega^\nu = \omega^\nu$. Therefore

$\beta^\mu + \beta^\nu = \omega^{\xi_1} + \omega^{\xi_2} + \ldots + \omega^{\xi_m} + \beta^\nu = \beta^\nu$, as desired. (end of proof of Lemma)

Therefore, since $\gamma_i \leq \delta$ for $m+1 \leq i \leq n$, we have

$\beta^{\gamma_{m+1}} + \ldots + \beta^{\gamma_n} + \beta^\delta = \beta^\delta$

and therefore

$\gamma + \beta^\delta = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_m} + \beta^\delta$.

We have

$f(\gamma) = \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_n)}$

$f(\gamma + \beta^\delta) = \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_m)} + \alpha^{f(\delta)}$,

and, provided that $m$ is the largest index such that $f(\gamma_m) \geq f(\delta)$, the same argument as above shows that

$f(\gamma) + \alpha^{f(\delta)} = \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_n)} + \alpha^{f(\delta)} $ $= \alpha^{f(\gamma_1)} + \alpha^{f(\gamma_2)} + \ldots + \alpha^{f(\gamma_m)} + \alpha^{f(\delta)} = f(\gamma + \beta^\delta)$.

So we are done if we can show that for all $\gamma, \delta \in E(\beta)$, $\gamma < \delta \Leftrightarrow f(\gamma) < f(\delta)$.

This follows from the fact that we can describe the comparison relation < using the same inductive rules, regardless of base. The inductive rules are as follows:

0 is less than any ordinal besides 0.

If $\gamma = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_m}$, and $\delta = \beta^{\delta_1} + \beta^{\delta_2} + \ldots + \beta^{\delta_n}$, with the $\gamma_i$ and the $\delta_i$ weakly decreasing, than $\gamma < \delta$ if and only if one of the following two conditions hold:

  1. For some $i$, $\gamma_i < \delta_i$ and for all $1 \leq j < i, \gamma_j = \delta_j$.

  2. $m < n$ and for all $1 \leq i \leq m$, $\gamma_i = \delta_i$.

It is easy to see that if the second condition holds, then $\gamma < \delta$. So assume the first condition holds. Since $\beta \geq \omega$ and $\delta_i \geq \gamma_i + 1$,

$\beta^{\delta_i} \geq \beta^{\gamma_i + 1} \geq \beta^{\gamma_i} \omega > \beta^{\gamma_i} m \geq \beta^{\gamma_i} + \beta^{\gamma_{i+1}} + \ldots + \beta^{\gamma_m}$, so

$\beta^{\delta_1} + \beta^{\delta_2} + \ldots + \beta^{\delta_n} \geq \beta{\delta_1} + \beta^{\delta_2} + \ldots + \beta^{\delta_i} = \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_{i-1}} + \beta^{\delta_i} > \beta^{\gamma_1} + \beta^{\gamma_2} + \ldots + \beta^{\gamma_{m}}$.

Going the other way, observe that, if neither conditions 1 nor 2 hold for $\gamma < \delta$, nor conditions 1 nor 2 hold for $\delta < \gamma$, we must have $m = n$ and $\gamma_i = \delta_i$ for $1 \leq i \leq m$, so $\gamma = \delta$. So if $\gamma < \delta$, either conditions 1 or 2 must hold.

We have shown that $T_\alpha(n)$ and $T_\beta(n)$ are the same ordinals except for a change of base from $\alpha$ to $\beta$. It follows that $S_\alpha(n)$ and $S_\beta(n)$ are the same except for the same change of base. So $F_\alpha(n) = F_\beta(n)$ for any $\alpha, \beta \geq \omega$.

As for the asymptotics of $F_\omega(n)$, all I can prove is that $F_\omega(n) \geq 2^{n-2}$. Take any binary string of n-2 symbols. Starting from $\omega^\omega$, apply the function $\alpha \rightarrow \alpha^\omega$ if the $i$th symbol is a 0, and apply the function $\alpha \rightarrow \omega^\alpha$ if the $i$th symbol is a 1. Defining $\beta$ by $\alpha = \omega^{\omega^\beta}$, the two operations affect $\beta$ by $\beta \rightarrow \beta + 1$ and $\beta \rightarrow \omega^\beta$ respectively. It's not hard to see that two distinct binary strings lead to two different final ordinals.

I conjecture that $\lim_{n \rightarrow \infty} \frac{F_\omega(n+1)}{F_\omega(n)} = 4$, but am nowhere close to a proof.

share|cite|improve this answer
Again, braces are not appearing in my LaTeX. Is it not correct to use \{ and \}? – Deedlit Aug 1 '12 at 3:54
@Deedlit: try using lbrace and rbrace (with backslashes of course) to get $\lbrace ... \rbrace$ – Suvrit Aug 1 '12 at 6:48
It works, thanks! – Deedlit Aug 1 '12 at 6:54
Or, more simply, double the backslashes: \\{ \\}. – Emil Jeřábek Aug 1 '12 at 10:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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