Comparing power towers of $2$s and $3s$

Question

Let $x=[x_1,x_2,...,x_n]$ be a finite list of positive real numbers, and define $\tau x$ as the power tower formed by these numbers. The function $\tau$ can be recursively defined by the following two equations:

$$\tau [x_1] = x_1$$

$$\tau [x_1,x_2,...]=x_1^{\tau [x_2,...]}$$

For example,

$$\tau [2,3,0.5,\pi]=2^{3^{0.5^\pi}}$$

I’m trying to find an algorithm which, given two finite ordered lists $x,y$ consisting only of $2$s and $3$s (e.g. $[2,2,3,2,3,3,3]$), determines which of $\tau x$ and $\tau y$ is larger, without explicitly calculating their values (the values quickly get much too big for most computers).

My thoughts so far: if $x$ and $y$ start with the same number, then we can eliminate this first number and just compare the subsequent entries of $x$ and $y$. This means that the only “interesting” cases are (WLOG) comparisons of the form $2^{\tau x’}$ and $3^{\tau y’}$, where $x’$ and $y’$ are formed by deleting the first entries of $x$ and $y$ respectively.

My intuition tells me that all reasonably tall distinct power towers of $2$s and $3$s will be “very far apart,” and in most cases determining which of $2^{\tau x’}$ and $3^{\tau y’}$ is greater will just boil down to determining which of $\tau x’$ and $\tau y’$ is greater. However, I’m having trouble formally determining exactly when this will be the case and what the exceptions will be.

Can anyone figure out a way to make my intuition rigorous, or suggest a different approach to finding an algorithm for comparing these power towers?

DISCLAIMER: This question arose while I was messing around with power towers. It’s not from a homework assignment or competition - purely a product of my personal math shenanigans. (For that reason, I can’t guarantee that it has a simple solution.)

Answer 1

Since all we want are comparing $2$'s and $3$'s, the only issue is when one base is $2$ and the other is $3$ (otherwise just compare the exponents).

The key to comparing $2^x$ and $3^y$ is to compare their logarithms. If we take the base $2$ logarithm, we end up comparing $x$ and $y\log_2(3)\approx1.585y$.

We will need to then push further another step. Let $(x,y)=(i^m,j^n)$. We apply one more logarithm to get $m$ and $n\log_i(j)+\log_i(\log_2(3))$. This is the point where we have to start introducing possible errors in the answer. If $m$ or $n$ can be directly calculated, then it suffices to... just calculate them. Otherwise, we may use the following:

If $m=n\log_i(j)$ is true, then $2^x<3^y$. (This can only be discerned exactly if $i=j$).

Otherwise, we just compare $m$ and $n\log_i(j)$ and ignore the $\log_i(\log_2(3))$ term. Note that this allows us to once again take a logarithm and reduce another power.

---

The actual algorithm

In short, this is essentially:

$$2^x<3^y\iff x\le y$$

$$2^x>3^y\iff x>y$$

where we can stop earlier to directly calculate values by taking the logarithm twice.

Answer 2

Just some quick thoughts:

I think the only natural thing to do here is to take logarithm. This leads to a more general problem: comparing $\ln(a)\cdot\tau x$ and $\ln(b) \cdot \tau y$, where $a, b\in\{2, 3\}$.

Taking logarithm again leads to comparing $\ln(a)\cdot \tau x + \ln(\ln(c))$ and $\ln(b) \cdot\tau y + \ln(\ln(d))$, where $a, b, c, d \in\{2, 3\}$.

Here comes a possible optimization: $\ln(\ln(c))$ and $\ln(\ln(d))$ are quite small numbers, compared to the supposedly huge $\tau x$ and $\tau y$. Hence if we can produce an inequality of the type $\ln(a) \tau x < (1 + \epsilon) \ln(b) \tau y$, even for some very tiny $\epsilon$, then a rough estimation on the size of $\tau y$ should be enough to give our willing inequality.

---

To summerize, we define the following process:

Checking_Process

Input: two lists, $x$ and $y$, and a positive real number $\alpha$

Output: a boolean value, true means $\alpha \cdot \tau x < \tau y$ and false means we don't know.

In Checking_Process, we write $x = [a, x']$ and $y = [b, y']$, and take a number $\alpha'$ that is "a tiny bit larger" than $\frac {\ln(a)}{\ln(b)}$.

We then recursively call Checking_Process on the inputs $x', y', \alpha'$. If the return is true, then we know that $\alpha' \tau x' < \tau y'$, which (with a suitable choice of $\alpha'$) implies $$\frac{\ln \alpha}{\ln(b)} + \frac {\ln(a)}{\ln(b)} \tau x' < \alpha' \tau x' < \tau y',$$ hence $\alpha \cdot \tau x < \tau y$ and we return true.

Otherwise, we return false to mean we don't know.

---

Now we just glue two pieces of Checking_Process: call Checking_Process on $x, y, 1$ and $y, x, 1$. Hopefully one of them will return true, and we are done.

In case both return false, it means that the inputs are in a very tricky situation. Since all the entries are $2$ and $3$, I think the chance of encountering this case should be negligible.