Notes on infinite tetration

Couple weeks ago my math teacher gave this problem to the class:

$x^{x^{x^{\cdot}}} = 2$

Solve for x

Here the tower of x’s is supposedly infinite (although I have no way of showing that in Latex).

The solution is simple, and it involves a single trick. Notice that the tower is infinite; thus if you remove an x from it, the power doesn’t change. Thus the exponent of the left hand side is equal to the whole left hand side. As the left hand side is equal to the right hand side which is 2, by substitution you get $x^2 = 2$ , and $x = \sqrt{2}$ .

There are a couple of problems in this approach.

Consider the similar equation, $x^{x^{x^{\cdot}}} = 4$ . If we use the same logic, it follows that $x = \sqrt[4]{4}$ or $x = \sqrt{2}$ .

Clearly that is not possible, as the left hand side equals $\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\sqrt{2}}}}$ , which cannot both equal 2 and 4. Evaluating it on a computer confirms that 2 is the value of this expression.

Even weirder is the case where $x^{x^{x^{\cdot}}} = 3$ ; when $x = \sqrt[3]{3}$ , the value of the expression converges to 2.4780526802882967 for the tower, where algebra dictates it should be 3.

What is going on here?

Introducing the Product Log function

The Product log function (sometimes called the Lambert W function or Omega function is an interesting function. It is usually written as $W(x)$ , with this definition:

$y = xe^x \Longleftrightarrow W(y)=x$

Compare this with the natural log:

$y = e^x \Longleftrightarrow \ln(y) = x$

The Product log function allows you to solve some interesting problems that can’t be solved with normal logarithms:

Example 1

$\begin{array}{rcl} 3x &=& 3^x \\ \frac{3x}{3^x} &=& 1 \\ 3x \cdot e^{-x \ln 3} &=& 1 \\ x \cdot e^{-x \ln 3} &=& \frac{1}{3} \\ -x \ln 3 \cdot e^{-x \ln 3} &=& \frac{-\ln 3}{3} \\ W(\frac{-\ln 3}{3}) &=& -x \ln 3 \\ x &=& -\frac{W(\frac{-\ln 3}{3})}{\ln 3} \end{array}$

Example 2

$\begin{array}{rcl} x^x &=& 100 \\ e^{x \ln x} &=& 100 \\ x \ln x &=& \ln 100 \\ e^{\ln x} \cdot \ln x &=& \ln 100 \\ W(\ln 100) &=& \ln x \\ x &=& e^{W(\ln 100)} \end{array}$

So the pattern is to manipulate the equation into $z e^z = k$ , where $k$ does not contain the variable. From there, $W(k) = z$ , and we can solve it because the variable is in $z$ .

A closed form expression

$x^{x^{x^{\cdot}}} = -\frac{W(-\ln x)}{\ln x}$

Similar to the two examples, we start by solving $y = x^y$ for $y$ :

$\begin{array}{rcl} y &=& x^y \\ \frac{y}{x^y}&=&1 \\ y \cdot e^{-y \ln x} &=& 1 \\ -y \ln x \cdot e^{-y \ln x} &=& -\ln x \\ W(-\ln x) &=& -y \ln x \\ y &=& -\frac{W(-\ln x)}{\ln x} \end{array}$

For the infinite tower scenario, let $y = x^{x^{x^{\cdot}}}$ . Then, $y = x^y$ , since the tower is infinite already. From what we just did, $y = -\frac{W(-\ln x)}{\ln x}$ .

Let’s use this formula to compute $\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\sqrt{2}}}}$ :

$\begin{array}{rcl} \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\sqrt{2}}}} &=& -\frac{W(-\ln \sqrt{2})}{\ln \sqrt{2}} \\ &=& \frac{\ln 2}{\ln (2^{\frac{1}{2}})} \\ &=& 2 \end{array}$

Why is it that $W(- \ln \sqrt{2}) = - \ln 2$ ? $-\ln \sqrt{2} = -\frac{1}{2} \ln 2$ , so $W(-\frac{1}{2} \ln 2) = -\ln 2$ because $-\ln 2 \cdot e^{-\ln 2} = -\frac{1}{2} \ln 2$ .

Similarly this rule applies to other numbers: $W(-\frac{1}{n} \ln n) = -\ln n$ .

Limitations of the W function

The plot of $y = W(x)$ looks like this:

Here, the function ‘stops’ at the point $(-\frac{1}{e}, -1)$ , because there is no value $y$ when $y e^y < -\frac{1}{e}$ .

So if $W(x)$ is only meaningful when $x \ge -\frac{1}{e}$ , then in the previous closed form expression $-\ln x \ge -\frac{1}{e}$ , which means $x \le e^{\frac{1}{e}}$ .

This is easily imagined: $5^{5^{5^{\cdot}}} = \infty$ and there is no solution to $y = 5^y$ . So the graph of $y = -\frac{W(-\ln x)}{\ln x}$ looks like this:

Surprisingly, the formula does not fail for $\sqrt[3]{3}$ , as $-\frac{W(-\ln \sqrt[3]{3})}{-\ln \sqrt[3]{3}}$ gives the correct answer of 2.478. Where I said previously that $W(-\frac{1}{n} \ln n) = -\ln n$ , this only applies when $n \le e$ ; otherwise the two diverge.

Recap

The expression $x^{x^{x^{\cdot}}}$ is only valid for $x \le e^{\frac{1}{e}}$ . The value of the expression can never exceed $e$ (unless of course it’s infinity).

There is also a lower bound for x: it doesn’t work unless $x > e^{-e}$ ; I didn’t explain the reasoning in this post.

7 thoughts on “Notes on infinite tetration”

Manuel says:

March 19, 2011 at 12:10 pm Reply

hi! nice post on this curious expression. I was wondering why x has to be greater than e^{-e} can you send me a reference for the proof, please? I can’t figure it out thanks!

LikeLike
1. luckytoilet says:
  
  March 19, 2011 at 12:46 pm Reply
  
  Hi. Unfortunately I don’t have any proof for that statement, but basically what happens is it doesn’t converge because the result ‘oscillates’ between two different values if x is smaller than a certain amount.
  
  LikeLike
Anonymous says:

October 15, 2011 at 10:02 am Reply

So, why doesn’t the method your teacher used work? I see the contradiction, but is there a better explanation?

LikeLike
1. Anonymous says:
  
  October 20, 2011 at 1:43 am Reply
  
  The maximum value of an infinite tower is e, so there is no x such that a tower of x’s evaluates to 3 or 4.
  
  The original argument shows (correctly) that tower(x) = 4 implies x = 2. But it doesn’t show that tower(2) = 4.
  
  LikeLike
Dave says:

April 29, 2013 at 3:20 pm Reply

One thing I’ve never figured out – if x^x^x….^x = 2 (= y), then if you raise both sides to the power x, you get x^x^x….^x^x (=y) = 2^x, because the left side is unaffected, as its an infinite series. Therefore, you have now shown that y = 2 and y = 2^x, implying x=1. Why doesn’t this work?

LikeLike
1. Anonymous says:
  
  May 15, 2013 at 7:18 am Reply
  
  Because the tower of x’s by convention means the limit of the sequence u(0) = x, u(i+1) = x^u(i), which converges for x upto 1.44-ish. Your argument would apply to the alternative sequence u(0) = x, u(i+1) = u(i)^x, which does not converge for any x > 1.
  
  I suggest you put x = sqrt(2) and calculate the first few terms of each of the two sequences – it will quickly become obvious.
  
  LikeLike
  1. Anonymous says:
    
    May 15, 2013 at 8:13 am Reply
    
    Hi. Thanks for the reply. Yeah, I spotted that too, shortly after my post. It’s interesting how powers are not associative (i.e. x^(x^x) does not equal (x^x)^x), unlike all the other operators everyone is used to (multiplication, addition, etc). I’d incorrectly assumed that because there were no brackets in the original tetration equation, that it would, but I guess that shows the dangers of making assumptions. Still, a bit ambiguous to write the problem x^x^x^.. without brackets given associativity doesn’t hold. Anyway, thanks for your reply
    
    LikeLike

Lucky's Notes

Notes on math, coding, and other stuff