Root two, raised to itself for ever

Here is a calculation that goes wrong in a way worth remembering. Suppose $x^{x^{x^{\cdots}}}$ equals 2, with the tower running up for ever. Since the whole tower is the exponent of its bottom $x$, the tower can be replaced by its value, which gives $x^2 = 2$ and $x = \sqrt 2$. Now suppose instead that the same tower equals 4. The same step gives $x^4 = 4$, so $x = \sqrt 2$ again. A single tower has apparently produced two different values.

Exactly one of those statements is true, and the tower on $\sqrt 2$ settles on 2. Nothing is wrong with either piece of algebra, in that both 2 and 4 are solutions of $y = (\sqrt 2)^y$. What the algebra assumes without saying so is that the tower has a value at all, and if it has, that the value is the solution being looked for. Those are questions about iteration and not about equations. Answering them means treating the tower as what it is: a map applied over and over, and the question becomes which bases allow the limit and which solution the orbit picks. The answer has two exact endpoints, and these are stranger than anybody would guess.

A tower is an orbit #

A tower is naturally read from the top down, and there it has no first step. To make sense of it, build it from the bottom of the stack upward by heights: $y_1 = a$, $y_2 = a^a$, $y_3 = a^{a^a}$, and in general $y_{n+1} = a^{y_n}$. So a tower of height $n$ is the $n$-th point on an orbit of the single map $f(x) = a^x$. The infinite tower means the limit of this orbit, if there is one. Now everything from the staircase that shows the whole orbit is available, including the cobweb diagram, where an orbit bounces between the curve and the diagonal.

For $a = \sqrt 2$ the first few heights are 1, 1.414214, 1.632527, 1.760840, 1.840911, 1.892713 and 1.927. They climb, and the staircase in the figure shows why they must stop at 2. The curve $y = (\sqrt 2)^x$ crosses the diagonal at 2 and again at 4. Starting anywhere below 2, each step moves right and stays under the crossing, so the orbit is increasing and bounded and has a limit. The orbit can never reach 4 because it cannot get past 2.

There is a simple test for the crossing itself. An orbit near a fixed point $y$ has its error multiplied each step by the slope $f'(y)$, and for this map

$$f'(y) = a^y \ln a = y \ln a = \ln y,$$

where the last step uses $a^y = y$ and hence $\ln a = (\ln y)/y$. So the slope at a crossing depends only on the height of the crossing. At 2 it is $\ln 2 = 0.693$, which is less than one, so 2 attracts. At 4 it is $\ln 4 = 1.386$, greater than one, so 4 repels. That single formula, the slope equals the logarithm of the value, is what the whole problem depends on, and it could not be simpler.

The two ends of the range #

A fixed point attracts when its slope has size less than one, which means $|\ln y| < 1$, that is $1/e < y < e$. Translate those into the base by $a = y^{1/y}$. The top end, $y = e$, gives $a = e^{1/e} = 1.444668$. The bottom end, $y = 1/e$, gives $a = (1/e)^e = e^{-e} = 0.065988$. These numbers are the whole answer: the tower has a limit exactly for

$$e^{-e} \le a \le e^{1/e}.$$

This was known to Euler in 1778, at least for the top and the general picture, and the endpoints were worked on through the nineteenth century by Gotthold Eisenstein and others, with a full treatment by David Barrow in 1936. There is a good deal of folklore about who proved what. The picture is what the curve below draws.

The upper end has a simple geometric meaning. For large bases the curve $a^x$ lies entirely above the diagonal, and the staircase climbs for ever. As $a$ falls, the curve eventually touches the diagonal at a single point. That happens when the curve is tangent to the diagonal, with slope exactly one, at $y = e$. Every smaller base then has two crossings, of which the lower attracts. That moment, $a = e^{1/e}$, is also the base at which the curve $\ln x / x$ has its peak, the same calculation that shows $e$ maximises $x^{1/x}$ and so makes $3^{1/3}$ larger than $2^{1/2}$ and $4^{1/4}$. So the top of the tower range is a familiar fact in a new setting. A base of 1.44 towers up to 2.47 or so. A base of 1.45 runs away, past any number whatever.

The lower end is the surprise. Most people’s guess, seeing a formula involving $x^x$, is that something goes wrong at the minimum of $x^x$, at $x = 1/e$, where $x^x = 0.6922$. Nothing does. The tower has a perfectly good limit well below that, down to a base of about a fifteenth. The curve is steep and decreasing there, and the slope only reaches $-1$ when $y$ has fallen to $1/e$.

What happens below the bottom #

For $a < 1$ the map is decreasing, and an orbit alternates. Odd heights are above the crossing and even heights are below. So $y_1 > y_3 > y_5 > \ldots$ and $y_2 < y_4 < y_6 < \ldots$, and two separate limits exist, one for each side. Whether they coincide is the question. They coincide while the slope at the fixed point has size less than one, and once it passes $-1$ the two limits part.

At base 0.02, the fixed point is at 0.304205, with slope $-1.190$, and it repels. The orbit settles on a two-cycle, alternating between 0.031462 and 0.884194. So tall towers of 0.02 are near 0.03 when their height is even and near 0.88 when it is odd, and the difference is far from small. The infinite tower has no value. It is a clean failure, and one that a naive use of the fixed-point equation would never catch, since the fixed point is still there, and it continues as the dashed curve in the previous figure.

This looks exactly like the first period doubling of the logistic map, with a slope passing $-1$ and a cycle of two being born. For real bases it also stops there. A decreasing map has an increasing square, and an increasing map of the line moves every orbit monotonically, so all orbits of $f \circ f$ go to fixed points. The real tower can have no 3-cycle, no 4-cycle and no chaos, and no cascade can ever follow the first split. A short monotonicity argument controls the whole picture, and the theorem about the order of periods never gets a start. The cycle’s two values continue as the base goes to nought, and they tend to 0 and 1, so a tiny base gives even towers near nought and odd ones near one.

How the limit is approached #

Within the range the error shrinks like the slope to the power of the height, so the speed depends only on where the limit is. This is the ordinary arithmetic of how fast a staircase arrives, with one unusual feature: the slope and the value are tied together by a logarithm.

For base 1.2 the slope is 0.229, and the tower is correct to machine rounding by height 20 or so. For base 1.4 it is 0.635, and it takes about seventy steps. Base 0.1 has slope $-0.919$ and at height 300 is still $2.7 \times 10^{-12}$ away. These are straight lines on the logarithmic scale, and the slopes of those lines are the logarithms of these numbers. There is a slow zone near each end of the range, and exactly at the ends the decay is no longer geometric at all. Exactly at the top, with slope one, the orbit’s approach has the form $y_{n+1} - e \approx (y_n - e) + (y_n - e)^2/(2e)$, the slow tangency familiar from a window that opens with a stutter, and it makes the error about $2e/n$. At height 300 that predicts 0.0181, and the computation gives 0.0178. At the bottom end the slope is $-1$, the second-order term cancels when the map is applied twice, and the error is reduced at the much slower rate of $1/\sqrt n$. At height 300 it is 0.053.

The picture therefore has a third feature that a table of limits misses. A tower near either end of the range has a limit, but anyone evaluating it numerically would see a slow drift, and a calculation stopped at any fixed height would give a wrong answer to several digits. The tower can be right at infinity and wrong at a million.

The trees inside the tower #

The limit has a formula. Put $L = \ln a$ and $y = a^y$, so that $y = e^{Ly}$, and write $T = Ly$; then $T = L e^{T}$. This is the functional equation of the generating function of rooted labelled trees. Cayley’s formula says that $n^{n-1}$ rooted trees exist on $n$ labelled points, and if $T(z) = \sum n^{n-1} z^n/n!$ then $T = z e^{T}$, since a rooted tree is a root with a set of rooted trees attached. So the tower is

$$y = \frac{T(\ln a)}{\ln a} = \sum_{n \ge 1} \frac{n^{n-1}}{n!} (\ln a)^{n-1}.$$

This is the series Eisenstein studied in 1844, and it is what is called Lambert’s $W$ function, with the sign changed, in modern notation. For $a = \sqrt 2$, adding the terms of this series gives 2 to nine digits. The tower of $\sqrt 2$ is therefore counting labelled trees, weighted by powers of half a logarithm. That is about as unexpected a connection as a formula gets. Nothing about stacking exponents suggests a tree, and yet the recursion that defines a tree, a root and its subtrees, is the same as the recursion of a tower, a base and its exponent. The same equation lies behind the map from functions to trees and the expected size of a tree’s leaves.

The series has a radius of convergence that gives a second reading of one endpoint. Stirling’s formula says the coefficients behave like $e^n$, so the radius is $|\ln a| = 1/e$. The top of the range is exactly $\ln a = 1/e$, and the singularity of the tree function explains why the tower stops there. The bottom is a different matter. The series converges only down to $\ln a = -1/e$, which is the base $e^{-1/e} = 0.692$, yet the tower converges all the way to 0.066. So the tower outlives its own series, by a long way, on the side where the terms alternate. The tree function has a perfectly good analytic continuation along the negative axis, and $y$ is defined and correct there, even though adding up the terms would no longer work. The base 0.692 is that $x^x$ minimum again, so the naive guess about that number does have something behind it after all.

Towers on complex bases #

Nothing stops the base from being complex. Pick a logarithm, the choice that a matrix or a number may not make uniquely, and the iteration $z \mapsto a^z$ makes sense. It may have a limit or an orbit of some other period, or run off. Now a fixed point’s slope is the complex number $\ln y$, and it attracts if that number has size less than one. Writing $t = \ln y$ gives $\ln a = t e^{-t}$, and so a base with an attracting fixed point has the form

$$a = \exp\!\left(t e^{-t}\right), \qquad |t| < 1.$$

The boundary is therefore an exactly known curve, the image of a unit circle, and it is what the dark line in the figure traces. The cells were not told about that line, and the limit region fills it exactly. At the real points, $t = 1$ gives the top end and $t = -1$ gives the bottom. W. J. Thron and Donald Shell found this region by different means, around 1960, and I. N. Baker and P. J. Rippon proved in 1983 that it is exactly the convergence region for the tower.

Round the outside of that region, the picture has something it shares with a very famous one. Whenever the slope $t$ reaches a root of unity on the unit circle, a cycle of that period is born, and a region of bases with period $q$ is attached at the point where $t = e^{2\pi i p/q}$. That is the same rule as for the bulbs on the Mandelbrot set’s cardioid, with $\exp(te^{-t})$ in place of the map $\lambda/2 - \lambda^2/4$ of the quadratic family. The cells detect periods 3, 4, 5 and more. Period 2 lies on the real axis just to the right of nought, where the real base goes below $e^{-e}$, and on this grid that region is thin: it covers only fourteen cells of the 14,560 sampled, far fewer than period 3 with its 2,700. The rest of the left-hand part, near a base of nought, is the complicated part of the picture, as the map is wildly expanding there, and the colouring is only as good as the short list of periods it looks for.

How far a drawing reaches #

A cobweb is a proof for a real base when the curve can be read, and on the real axis it does the entire job. The monotonicity arguments are complete. What the figures cannot do is prove anything about the exact endpoints, where the behaviour is decided by higher-order terms, and they only show the rates there after someone has calculated them. The comparison with $2e/n$ was made at one height, 300, and it is good to a couple of per cent, as would be expected since that estimate carries a logarithmic correction.

The complex figure deserves more caution. Each cell was tested from the starting point 1 for 3,000 steps with the principal logarithm, with a period detected to six digits. Cells close to any boundary can converge so slowly that they are recorded as having no short period. The large “no short period” area on the left of the picture is not a claim of chaos. It may hold long periods, and it includes cells at which rounding has already mixed things up. The curve bounding the limit region is exact; the shapes of the attached regions are a sample.

What was computed and what was quoted #

The real orbits were computed directly in double precision, and the bisection for fixed points was checked at both endpoints. The value 2 at $\sqrt 2$, the fixed-point equation at 4, the two-cycle at base 0.02 and the rates at height 300 were all computed and are exact to rounding, except the top-end rate, which is an asymptotic statement checked at one height. The tree series was summed numerically at $\sqrt 2$ to nine digits.

The monotonicity argument is a proof. The historical attributions, to Euler, Eisenstein and Barrow, are quoted and their dates are approximate in places, since the early history is tangled. The theorem identifying the complex region is from Baker and Rippon and was not reproved. The cells in the last figure are illustrative, and the claim about attached regions at roots of unity is the standard local bifurcation statement, which the cells merely fit.

Still open: what the outside of the region is made of #

The exterior of the region has been studied mostly through the closely related exponential family $z \mapsto \lambda e^z$, by Robert Devaney and others. Its parameter plane has its own bulbs, its own hairs running out to infinity, and sets of escaping points that form curves, rather than the dust of the quadratic case. Lasse Rempe and Dierk Schleicher, among others, have described it in much detail.

Is hyperbolicity dense in that family? That is, can every exponential map be perturbed into one with an attracting cycle? It is the same question as the one asked of the quadratic family, the Fatou conjecture, and it is open in both. In the exponential family it is tied up with whether the parameters with no attracting cycle can form a set with interior. Nobody knows how to rule out what is called a queer component. The picture of periods drawn here is one very coarse view of that structure, and it suggests nothing either way, since a grid of 3.4-pixel cells cannot see any of the fine features the question depends on.

Which of two solutions the tower chose #

The tower of $a$ is the orbit of $x \mapsto a^x$, its slope at a limit $y$ is $\ln y$, and that makes the limit stable exactly for $1/e \le y \le e$, or $e^{-e} \le a \le e^{1/e}$. Above that range the tower runs away, and below it the tower splits into two values that never merge again. The equation $y = a^y$ knows nothing of this: it has two solutions for $\sqrt 2$ and it does not say which is real.

That is the original paradox resolved. Both 2 and 4 solve the equation, the slope at 2 is below one and at 4 it is above, and so the tower of $\sqrt 2$ is 2. The same one-line formula gives both ends of the range, the slow convergence at each of them, and the boundary curve in the complex plane. And the tree recursion gives the value itself, so the tower has been counting something all along.