12
$\begingroup$

Consider exponentiation on the natural numbers. Suppose we have an equation involving only the variable $x$, where there are $m$ $x$'s on one side and $n$ $x$'s on another side where $m$ and $n$ are different, like $(x^x)^{x^x}=(x^x)^{(x^x)^x}$, where the brackets can go anywhere. Is it always the case that there is a natural number such that the equation does not hold? In other words, do all single variable identities over exponentiation have the same length?

$\endgroup$
2
  • 2
    $\begingroup$ I would propose that one expression is asymptotically larger than the other even when $m=n$, as long as the expressions differ. A proof by induction on the height of the power tower should work. $\endgroup$
    – mjqxxxx
    Oct 25, 2022 at 4:52
  • $\begingroup$ Your title asks if all the identities have the same length, but your actual question is whether both sides of each identity have the same length. Of course some identities are longer than others, $x=x$ being the shortest one. $\endgroup$
    – bof
    Nov 10, 2022 at 8:56

3 Answers 3

3
$\begingroup$

Yes your claim is true, and actually we can do much better. If $f(x)$ and $g(x)$ are two exponential functions of the form you ask about, and they aren't the same, then one of them asymptotically dominates the other.

My proof is similar to Matija's but a bit shorter, since we don't need to invoke the whole structure of binary expression trees for this problem; thus we can define a simpler tree-to-exponential expression correspondence.

Write $f\gg g$ if $\lim\limits_{x\rightarrow\infty} \frac{f(x)}{g(x)} = \infty$. We make use of two simple facts:

Fact 1: $f\gg g$, and $\liminf\limits_{x\rightarrow\infty} g(x)>0$, then $x^{f(x)} \gg x^{g(x)}$.

Fact 2: There is a one-to-one correspondence between functions formed by exponentiating $x$'s and unordered rooted trees.

The correspondence goes like this: Let $f_T(x)$ represent the function corresponding to tree $T$. If $T$ is a single node, then $f_T(x) = x$. If $T$ has subtrees $T_1,T_2,\dots,T_k$ attached to its root, then we have $$ f_T(x) = ((x^{f_{T_1}(x)})^{f_{T_2}(x)})\cdots)^{f_{T_k}(x)} $$

The fact that ordering on the nodes is irrelevant corresponds to the algebraic fact that $(a^b)^c =(a^c)^b$. It will also be convenient to write the empty tree as $0$, with $f_0(x) = 1$.

For example, look at these trees: Four examples of trees We have $$ F_A(x)=x^{((x^x)^x)^x}\hspace{8pt}F_B(x) = (x^x)^x\hspace{8pt}F_C(x)=x^{x^{x^x}}\hspace{8pt}F_D(x) =x^{\left(\left((x^x)^{x^x}\right)^{(((x^x)^x)^x)^x}\right)} $$ We define a total order on tree inductively as follows: $T>S$ if $S=0$ and $T\ne 0$. If $T$ and $S$ are nonempty, and have subtrees attached to their root $T_1,T_2,\dots$ and $S_1,S_2,\dots$ respectively (all but finitely many of $T_i$ and $S_i$ are $0$) and these are ordered in decreasing order (i.e. $T_1\ge T_2\ge \cdots$ and the same for $S$), then we say $T>S$ if the tuple $(T_1,T_2,\dots)>(S_1,S_2,\dots)$ in lexicographic order.

Theorem: If $T>S$, then for all $p\in (0,\infty)$ $$ f_T(x) \gg f_S(x)^p $$ In particular $f_T(x) = f_S(x)$ has finitely many solutions in $\mathbb N$ if $T\ne S$. The number of nodes of a tree corresponds to the number of $x$'s in the expression of $f_T(x)$, hence your conjecture is true.

Proof: We induct on trees. If $S=0$, this is trivial. Otherwise, suppose $T>S$ have $(T_1,T_2,\dots)$ and $(S_1,S_2,\dots)$ are the subtrees meeting at the root of $T$ and $S$, indexed in decreasing order; we show that if the claim holds for all $T_i$ and $S_i$ then it holds for $T$ and $S$. By $T>S$, there exists $k$ such that $T_k>S_k$ and $T_i=S_i$ for $i<k$. Observe, for any $p\in(0,\infty)$ $$ \lim\limits_{x\rightarrow\infty}\frac{\prod_{i\in\mathbb N} f_{T_i}(x)}{p\prod_{i\in\mathbb N} f_{S_i}(x)} = \frac1p\lim\limits_{x\rightarrow\infty}\frac{f_{T_k}(x)}{f_{S_k}(x)}\frac{\prod_{i>k} f_{T_i}(x)}{\prod_{i>k} f_{S_i}(x)} \ge \frac1p\lim\limits_{x\rightarrow\infty}\frac{f_{T_k}(x)}{f_{S_k}(x)^N} = \infty $$ where $N$ is the number of nonzero trees in $\{S_i\}$. Noting that the numerator and denominator of the fraction on the RHS are $\log_x(f_T(x))$ and $\log_x(f_S(x)^p)$ respectively, fact 1 implies the result.

$\endgroup$
2
  • $\begingroup$ Nice construction, elegant simplifications! Just one typo, maybe: In the denominator of the second step of the last equation the product might be over $i>k$. $\endgroup$
    – Matija
    Oct 27, 2022 at 14:19
  • $\begingroup$ Good catch, thanks $\endgroup$ Oct 27, 2022 at 14:20
2
$\begingroup$

Yes, there always exists a natural number such that the equation does not hold if $m\neq n$.

We show this by proving the following, stronger claim, based on expression trees.

Let $x:\mathbb R_{>0}\rightarrow\mathbb R_{>0}$, $a\mapsto a$, and $e:\mathbb R_{>0}^2\rightarrow\mathbb R_{>0}$, $(a,b)\mapsto a^b$. Let $\mathcal T_1=\{x\}$. For $h\in\mathbb Z_{>1}$ let $\mathcal T_h=\mathcal T_{h-1}\cup\{(e,T_1,T_2):T_1,T_2\in\mathcal T_{h-1}\}$. Notice that $\mathcal T_{h-1}\subseteq\mathcal T_h$, so $\mathcal T_\infty=\lim_{h\rightarrow\infty}\mathcal T_h$ is well-defined, these are the expression trees of arbitrary height.

Next, we define the evaluation function $E:\mathcal T_\infty\times\mathbb R_{>0}\rightarrow\mathbb R_{>0}$ recursively by $E((e,T_1,T_2),a)=e((E(T_1,a),E(T_2,a)))$, and by $E(x,a)=x(a)$. Constructions like these are typical for logic, set theory and computer science. How are the two sides of the equation in the question reflected? The formal expression for $(x^x)^{x^x}$ is $T_1=e(e(x,x),e(x,x))$, and for $(x^x)^{(x^x)^x}$ we have $T_2=e(e(x,x),e(e(x,x),x))$. Evaluating $T_1$ at $2$ gives \begin{align*} E(T_1,2)&=e(E(e(x,x),2),E(e(x,x),2)) =e(e(E(x,2),E(x,2)),e(E(x,2),E(x,2)))\\ &=e(e(x(2),x(2)),e(x(2),x(2))) =e(e(2,2),e(2,2)) =e(2^2,2^2)=(2^2)^{2^2}=256. \end{align*} And, of course, the pleasant part, here is the visualization.

enter image description here

Now, we're ready for the claim.

CLAIM: There exists a set $\mathcal T_\circ$, a strict total order on $\mathcal T_\circ$, an evaluation function $E_\circ$ on $\mathcal T_\circ$ and a function $L:\mathcal T_\circ\times\mathcal T_\circ\rightarrow\mathbb R_{\ge 0}$ with the following properties.

  1. For all $T\in\mathcal T_\infty$ there exists a unique $T_\circ\in\mathcal T_\circ$ such that $E(T,a)=E_\circ(T_\circ,a)$ for all $a\in\mathbb R_{>0}$.
  2. For $T_1,T_2\in\mathcal T_\circ$ we have $L(T_1,T_2)=L(T_2,T_1)$. Further, we have $L(T_1,T_2)=0$ if and only if $T_1=T_2$, and $L(T_1,T_2)\ge 1$ otherwise. For $T_1>T_2$ and $a\in(L(T_1,T_2),\infty)$ we have $E(T_1,a)>E(T_2,a)$.

This means that we provide a unique representation of these power stacks $T$ (say, normalized), because there's a unique $T_\circ$ that always gives the same results as $T$. Further, from these normalizations we obtain an explicit bound $L$, so that the greater side (according to the order) is actually greater than the other side for all (including natural) values above the bound $L$.

PROOF: The set $\mathcal T$ will be pretty similar to $\mathcal T_\infty$. There are only tow differences. First, we introduce the product $p_k:\mathbb R_{>0}^k\rightarrow\mathbb R_{>0}$, $(a_1,\dots,a_k)\mapsto\prod_{i=1}^ka_i$, for $k\ge 2$. Next, we keep the trees ordered. Since we need an order for that, we first look at all trees with product. Let $\mathcal P_1=\{x\}$ and $\mathcal P_{h}=\mathcal P_{h-1}\cup\{(e,P_1,P_2):(P_1,P_2)\in\mathcal P_{h-1}^2\}\cup\bigcup_{k=2}^\infty\{(p_k,P_1,\dots,P_k):(P_1,\dots,P_k)\in\mathcal P_{h-1}^k\}$. Now, we still have the leaf $x$, the exponentiation $e$, but also the product $p_k$ for any number $k\ge 2$ of arguments. Let $\mathcal P_\infty=\lim_{h\rightarrow\infty}\mathcal P_h$ and define $E_*:\mathcal P_\infty\times\mathbb R_{>0}\rightarrow\mathbb R_{>0}$ in the obvious manner.

Notice that we have $\mathcal T_\infty\subseteq\mathcal P_\infty$ since $x$ and the exponentiation $e$ are covered. So, we simply start with the identity $P:\mathcal T_\infty\rightarrow\mathcal P_\infty$, $T\mapsto T$. Also, it's clear that $E_*(P(T),a)=E(T,a)$ is the same. Now, we introduce very basic algebraic transformations in this very cumbersome machinery.

For $(e,(e,P_1,P_2),P_3)\in\mathcal P_\infty$ let $M(e,(e,P_1,P_2),P_3)=(e,M(P_1),p_2(M(P_2),M(P_3)))$. In a more readable (but not rigorous) form, we apply $(P_1^{P_2})^{P_3}\mapsto P_1^{P_2\cdot P_3}$. Otherwise we don't do anything, meaning for $(e,P_1,P_2)$ with $P_1\neq(e,\cdot,\cdot)$ we set $M(e,P_1,P_2)=(e,M(P_1),M(P_2))$, further $M(p_k,(P_1,\dots,P_k))=(p_k,M(P_1),\dots,M(P_k))$ and $M(x)=x$. This defines a function $M:\mathcal P_\infty\rightarrow\mathcal P_\infty$. Notice that we get $M(e,(e,(e,x,\cdot),\cdot),\cdot)=(e,M(e,x,\cdot),p_2(M(\cdot),M(\cdot)))$ and that $M(e,x,\cdot)=(e,x,M(\cdot))$. This means that afterwards, we still have a $(e,(e,\cdot,\cdot),\cdot)$ combination, so we are not done in one sweep. But for $P\in\mathcal P_h$ and $M^h(P)\in\mathcal P_\infty$, where $M^h(P)=M(M(\dots M(P))\dots)$ is the $h$-fold application of $M$, we know that the combination $(e,(e,\cdot,\cdot),\cdot)$ does not exist in $M^h(P)$ anymore (the number of such combinations in each path reduces by at least one in one sweep). For example, the left hand side in the question would be mapped to $(e,x,(p_2,x,(e,x,x)))$.

Now, recall that in $\mathcal T_\infty\subseteq\mathcal P_\infty$ we only use $e$ and $x$, we don't use products. The map $M$ eliminates all occurences of $(e,e(\dots$ eventually, and each time it does, it only introduces a product $p_2$ as a right child of $e$. So, the elements $T\in\mathcal T^*_1=\{M^h(T):h\in\mathbb Z_{>0},T\in\mathcal T_h\}$ have the following properties. The only functions that appear are $x$, $e$ and $p_2$. The leafs are exactly the $x$'s. Either the tree is just $x$, or the root is $e$, since $M$ preserves the position of $e$. The left child of any $e$ is not $e$ since we applied $M$, and it is not $p_2$. Well, so it has to be $x$.

In the next step we aggregate the products. So, each time we see some $(p_k,(p_j,P_1),P_2)$, we map it to $(p_{k+j},P_1,P_2)$, and analogously for the right child. Repeating this often enough gives $\mathcal T^*_2$, with the following properties. The root is still ($x$ or) $e$, left children of $e$ are still $x$, and now children of products can not be products anymore, so they have to be $e$ or $x$.

For $T_1,T_2\in\mathcal T^*_2$ let $o(T_1,T_1)=0$, $o(T_2,T_1)=-o(T_1,T_2)$ (meaning $T_1=T_1$ and $T_2<T_1$ if $T_1>T_2$) and $L(T_1,T_1)=0$, $L(T_1,T_2)=L(T_2,T_1)$, and the remaining values are given as folllows, together with the definition of $T_\circ(T)\in\mathcal T^*_2$ for $T\in\mathcal T^*_2$. Let $T_\circ(x)=x$ and $T_\circ(e,x,T)=(e,x,T_\circ(T))$. For $T\neq x$ let $o(x,T)=-1$ and $L(x,T)=1$ (this easily follows with induction). Further, let $o((e,x,T),(e,x,T'))=o(T,T')$ and $L((e,x,T),(e,x,T'))=L(T,T')$ (monotonicity). This covers all elements of $\mathcal T^*_2$ that do not involve products. For $(p_k,T_1,\dots,T_k)$, order the children in ascending order (for which the order is already defined), i.e. we take a permutation $\sigma:[k]\rightarrow[k]$ such that $o(T_{i},T_{i+1})\le 0$ for $i=1,\dots,k-1$ and set $T_\circ(p_k,T_1,\dots,T_k)=(p_k,T_\circ(T_{\sigma(1)}),\dots,T_\circ(T_{\sigma(k)}))$.

With the definition above we can sort $T=(p_k,T_1,\dots,T_k)$ and $T'=(p_j,T'_1,\dots,T'_j)$, so we may assume that $T=T_\circ(T)$ and $T'=T_\circ(T')$ are already normalized, and that $k\ge j$. Now, we use the lexicographical order, i.e. $o(T,T')=1$ if $o(T_k,T'_j)=1$, and if $o(T_k,T'_j)=0$, then consider $o(T_{k-1},T'_{j-1})$, $o(T_{k-i},T'_{j-i})$ and so forth. Should they be equal for all $0\le i\le j-1$ then let $o(T,T')=1$ if $k>j$, otherwise they are actually equal, so $o(T,T')=0$. For $T=(e,x,T'')$ we simply have $o(T,T')=1$ if $o(T,T'_j)=1$, i.e. $T'_j=x$ or $o(T'',T''_j)=1$ where $T'_j=(e,x,T''_j)$.

This completely defines the order $o(T,T')$, which we now denote $T>T'$, and the normalizations $T_\circ(T)$, for which we set $\mathcal T_\circ=\{T_\circ(T):T\in\mathcal T^*_2\}$. I hope it is sufficiently clear that these are indeed unique (the product decomposition gives uniqueness up to permutations, and the order takes care of these). Now, we still have to define $L$ for product-product pairs and product-exponential pairs. As seen above, the latter is clear when we understand the former. For the products $T$, $T'$ from above, assume that we have $T>T'$. If all elements are equal, thus $k>j$, let $L(T,T')=1$, since this then suffices. Otherwise, let $i$, $i'$ be the maximal children (the witnesses) with $T_i>T'_{i'}$ (this implies $T_i=(e,x,\cdot)$). Let $L'=\max_{r\le i'}L(T'_{i'},T'_r)$ be the bound which ensures that $T'_{i'}$ is maximal among its siblings, and $L^*=L(T_i,T'_{i'})$ the bound which ensures that $T_i$ outperforms $T'_{i'}$, so $L^\circ=\max(L',L^*)$ ensures that $T_i$ outperforms all preceeding siblings of $T'_{i'}$ with $T'_{i'}$ included. Notice that the successors are equal in both products, meaning always equal.

Hence, the worst case, to which we can restrict, is that we have only one $T$, meaning $T=(e,x,S)$ and $T'_1=\dots=T'_j$, with $T>T'_j$. Notice that, trivially, we have $S\ge x$, so if we have $T'_j=x$, let $L(T,T')=a>0$, where $a$ is given by $e^a=a^j$, if it exists, otherwise let $L(T,T')=1$. Otherwise let $T'_j=(e,x,S')$, and notice that $S>S'$. Now, $T$ has to beat $T'_j$ to the power of $j$, meaning that $S$ has to beat $S'$ times $j$. Now, in all these definitions, notice that the recursive definition of $o$ for $S>S'$ yields that moving up the chain, we find the cause $R>R'$. This means, for $(e,x,A)>(e,x,B)$ we move up the chain to $A>B$, for product-product pairs we move up the chain for the elements $T_i>T'_{i'}$. Then the end of the chain $R>R'$ is reached exactly if $R'=x$ and $R$ is not, or $R$ and $R'$ are products that coincide on the maximal factors, which exhaust the product $R'$, and thus $R$ wins due to the presence of additional factors. These are the only two possible cases. In the former, $R$ may be a product (with at least two factors) or an exponential, in both cases we still have $R\ge(p_2,x,x)$, i.e. we may add an $x$. In the latter case, $R$ does have some additional factor, which suggests again that $R\ge p_2(x,R')$. Next, notice that moving this additional $x$ down the chain decreases the position of the tree in the order, which gives $S\ge p_2(x,S')$. Recall that $S$ has to beat $j$ times $S'$, so $L(T,T')=\max(j,L^\circ)$ suffices. This also completes the definition of $L$. Since we have $\mathcal T_\circ\subseteq\mathcal T^*_2\subseteq\mathcal P_\infty$, we can reuse $E_\circ(T,a)=E_*(T,a)$.

Last words: In this construction we preserved the number of leafs $x$ at all times, e.g. the power of $x$ to $k$ is encoded as $\prod_{i=1}^kx$ (avoiding operations like $x+x=2x$ and $x\cdot x=x^2$). In particular, this means that the number $m$ of $x$'s on the left hand side and the number $n$ of $x$'s on the right hand side is preserved, and thus we can clearly deduce the relationship of numbers of $x$'s to existence of natural numbers that do not solve the equation. This goes down as follows. The two sides of the equation are equal if and only if the normalizations coincide. In this case we have $m=n$, implied by equal normalizations. If the sides of the equation are not equal, then one of the normalizations is greater and we provided a bound, which gives infinitely many natural numbers for which the two sides don't match, and we assert which side is always greater. Finally, there is no relationship whatsoever between which side of the equation is greater, and which of $m$ and $n$ is greater. The minimum working example is $((x^x)^x)^x<x^{x^x}$ for sufficiently large $x$.

$\endgroup$
2
+50
$\begingroup$

Note: This only partially answers the question, as it does not consider the case $m=n$, and $m,n$ are defined slightly differently here (Although if the case $m=n$ was shown to hold too, then it would cover all cases of the original question).

To make the notation easier on the eyes, I'm going to write $(p_1,p_2,...,p_n)$ to mean $x^{p_1^{p_2^{...^{p_n}}}}=x^{\left(p_1^{\left(p_2^{\left(...^{p_n}\right)}\right)}\right)}$ where the $p_i$ are polynomials in $x$

Every equation of the form we are interested in can be written in this way, e.g. $(x^x)^{x^x}=x^{x^{x+1}}=(x,x+1)$.

Now suppose we have an equation $(p_1,...,p_n)=(q_1,...,q_m)$, where $p_i,q_j$ are not constants for all $i,j$, otherwise we can raise the term below to the integer power (we know the power will be an integer because in reducing the expressions in $x$ to this form, we are only multiplying an integer number of times).

Firstly, if $n>m$, then $p_{n-1}^{p_n}$ grows faster than $q_m$, since one is an exponential expression and the other is a polynomial expression. Then we can show $p_{n-2}^{p_{n-1}^{p_n}}$ grows faster than $q_{m-1}^{q_m}$ by taking logarithms:

$p_{n-1}^{p_n}\log{p_{n-2}}$ grows faster than $q_m\log{q_{m-1}}$ since $p_{n-1}^{p_n}$ grows faster than $q_m$.

We repeat this process to get that $(p_{n-m},p_{n-m+1},...,p_{n-1},p_n)$ grows faster than $(q_1,q_2,...,q_m)$, so certainly $(p_1,...,p_n)$ grows faster than $(q_1,...,q_m)$. So taking an $x$ big enough will break the equality.

This argument relies heavily on the fact that "exponentials beat polynomials", the idea that expressions like $a^x$ eventually grow faster than any finite degree polynomial for any positive constant $a$, so certainly it will be true if $a$ is a polynomial in $x$.

$\endgroup$
1
  • 2
    $\begingroup$ I wrote an impressingly lengthy answer, because I see two issues here. For one, the number of involved polynomials is not the number of $x$'s, so $m$ and $n$ as defined in the answer are not $m$ and $n$ as defined in the question. The second, related issue is that the case $m=n$ is not discussed, where the number of polynomials match, but the numbers of appearances of $x$ might still be distinct. Of course, the reasoning that $\exp$ beats $\mathrm{poly}$ is true. But as far as I can see, the "boundary" case where we compare polynomials is also missing, say $x^x$ and $(x^x)^x=x^{x^2}$. $\endgroup$
    – Matija
    Oct 27, 2022 at 5:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .