# Number of distinct values taken by $\alpha$ ^ $\alpha$ ^ $\dots$ ^ $\alpha$ with parentheses inserted in all possible ways, $\alpha\in\mathbf{Ord}$

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}}}$

-
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

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.

-
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