Tetration

Definition

For any positive real a > 0 and non-negative integer n ≥ 0 , we define n a by:

n a := { 1 if  n = 0 a [ ( n − 1 ) a ] if  n > 0

Iterated powers vs. iterated exponentials

As we can see from the definition, when evaluating tetration expressed as an "exponentiation tower", the exponentiation is done at the deepest level first (in the notation, at the highest level). For example:

  4 2 = 2 2 2 2 = 2 [ 2 ( 2 2 ) ] = 2 ( 2 4 ) = 2 16 = 65 , 536

Note that exponentiation is not associative, so evaluating the expression in the other order will lead to a different answer:

2 2 2 2 ≠ [ ( 2 2 ) 2 ] 2 = 2 2 ⋅ 2 ⋅ 2 = 256

Exponential towers must be evaluated from top to bottom (or right to left). Computer programmers refer to this choice as right-associative.

When a and 10 are coprime, we can compute the last m decimal digits of   n a using Euler's theorem, for any integer m.

Terminology

There are many terms for tetration, each of which has some logic behind it, but some have not become commonly used for one reason or another. Here is a comparison of each term with its rationale and counter-rationale.

The term tetration, introduced by Goodstein in his 1947 paper Transfinite Ordinals in Recursive Number Theory (generalizing the recursive base-representation used in Goodstein's theorem to use higher operations), has gained dominance. It was also popularized in Rudy Rucker's Infinity and the Mind.

The term superexponentiation was published by Bromer in his paper Superexponentiation in 1987. It was used earlier by Ed Nelson in his book Predicative Arithmetic, Princeton University Press, 1986.

The term hyperpower is a natural combination of hyper and power, which aptly describes tetration. The problem lies in the meaning of hyper with respect to the hyperoperation sequence. When considering hyperoperations, the term hyper refers to all ranks, and the term super refers to rank 4, or tetration. So under these considerations hyperpower is misleading, since it is only referring to tetration.

The term power tower is occasionally used, in the form "the power tower of order n" for     a a ⋅ ⋅ a ⏟ n . This is a misnomer, however, because tetration cannot be expressed with iterated power functions (see above), since it is an iterated exponential function.

The term snap is occasionally used in informal contexts, in the form "a snap n" for     a a ⋅ ⋅ a ⏟ n . This term is not yet widely accepted, although it is used within select communities. It is believed to be a reference to Jounce, the fourth derivative of position in physics, since tetration is the fourth hyperoperation.

Owing in part to some shared terminology and similar notational symbolism, tetration is often confused with closely related functions and expressions. Here are a few related terms:

In the first two expressions a is the base, and the number of times a appears is the height (add one for x). In the third expression, n is the height, but each of the bases is different.

Care must be taken when referring to iterated exponentials, as it is common to call expressions of this form iterated exponentiation, which is ambiguous, as this can either mean iterated powers or iterated exponentials.

Notation

There are many different notation styles that can be used to express tetration (also known as hyper-4; some of them can be used as well for hyper-5, hyper-6, and higher hyperoperations).

One notation above uses iterated exponential notation; in general this is defined as follows:

exp a n ⁡ ( x ) = a a ⋅ ⋅ a x with n "a"s.

There are not as many notations for iterated exponentials, but here are a few:

Examples

In the following table, most values are too large to write in scientific notation, so iterated exponential notation is employed to express them in base 10. The values containing a decimal point are approximate.

Extensions

Tetration can be extended to define n 0 and other domains as well.

Extension to base zero

The exponential 0 0 is not consistently defined. Thus, the tetrations n 0 are not clearly defined by the formula given earlier. However, lim x → 0 n x is well defined, and exists:

lim x → 0 n x = { 1 , n  even 0 , n  odd

Thus we could consistently define n 0 = lim x → 0 n x . This is equivalent to defining 0 0 = 1 .

Under this extension, 0 0 = 1 , so the rule 0 a = 1 from the original definition still holds.

Extension to complex bases

Since complex numbers can be raised to powers, tetration can be applied to bases of the form z = a + b i , where i 2 = − 1 . For example, n z where z = i , tetration is achieved by using the principal branch of the natural logarithm, and using Euler's formula we get the relation:

i a + b i = e 1 2 π i ( a + b i ) = e − 1 2 π b ( cos ⁡ π a 2 + i sin ⁡ π a 2 )

This suggests a recursive definition for ( n + 1 ) i = a ′ + b ′ i given any n i = a + b i :

a ′ = e − 1 2 π b cos ⁡ π a 2 b ′ = e − 1 2 π b sin ⁡ π a 2

The following approximate values can be derived:

n i Approximate Value 1 i = i i 2 i = i ( 1 i ) 0.2079 3 i = i ( 2 i ) 0.9472 + 0.3208 i 4 i = i ( 3 i ) 0.0501 + 0.6021 i 5 i = i ( 4 i ) 0.3872 + 0.0305 i 6 i = i ( 5 i ) 0.7823 + 0.5446 i 7 i = i ( 6 i ) 0.1426 + 0.4005 i 8 i = i ( 7 i ) 0.5198 + 0.1184 i 9 i = i ( 8 i ) 0.5686 + 0.6051 i

Solving the inverse relation as in the previous section, yields the expected 0 i = 1 and ( − 1 ) i = 0 , with negative values of n giving infinite results on the imaginary axis. Plotted in the complex plane, the entire sequence spirals to the limit 0.4383 + 0.3606 i , which could be interpreted as the value where n is infinite.

Such tetration sequences have been studied since the time of Euler but are poorly understood due to their chaotic behavior. Most published research historically has focused on the convergence of the infinitely iterated exponential function. Current research has greatly benefited by the advent of powerful computers with fractal and symbolic mathematics software. Much of what is known about tetration comes from general knowledge of complex dynamics and specific research of the exponential map.

Extension to infinite heights

Tetration can be extended to infinite heights (n in n a ). This is because for bases within a certain interval, tetration converges to a finite value as the height tends to infinity. For example, 2 2 2 ⋅ ⋅ ⋅ converges to 2, and can therefore be said to be equal to 2. The trend towards 2 can be seen by evaluating a small finite tower:

2 2 2 2 2 1.414 ≈ 2 2 2 2 1.63 ≈ 2 2 2 1.76 ≈ 2 2 1.84 ≈ 2 1.89 ≈ 1.93

In general, the infinitely iterated exponential x x ⋅ ⋅ ⋅ , defined as the limit of n x as n goes to infinity, converges for e^−e ≤ x ≤ e^1/e, roughly the interval from 0.066 to 1.44, a result shown by Leonhard Euler. The limit, should it exist, is a positive real solution of the equation y = x^y. Thus, x = y^1/y. The limit defining the infinite tetration of x fails to converge for x > e^1/e because the maximum of y^1/y is e^1/e.

This may be extended to complex numbers z with the definition:

∞ z = z z ⋅ ⋅ ⋅ = W ( − ln ⁡ z ) − ln ⁡ z   ,

where W represents Lambert's W function.

As the limit y = ^∞x (if existent, i.e. for e^−e < x < e^1/e) must satisfy x^y = y we see that x ↦ y = ^∞x is (the lower branch of) the inverse function of y ↦ x = y^1/y.

(Limited) extension to negative heights

In order to preserve the original rule:

( k + 1 ) a = a ( k a )

for negative values of k we must use the recursive relation:

k a = log a ⁡ ( ( k + 1 ) a )

Thus:

( − 1 ) a = log a ⁡ ( 0 a ) = log a ⁡ 1 = 0

However smaller negative values cannot be well defined in this way because

( − 2 ) a = log a ⁡ ( − 1 a ) = log a ⁡ 0

which is not well defined.

Note further that for n = 1 any definition of ( − 1 ) 1 is consistent with the rule because

0 1 = 1 = 1 n for any n = ( − 1 ) 1 .

Extension to real heights

At this time there is no commonly accepted solution to the general problem of extending tetration to the real or complex values of n . Various approaches are mentioned below.

In general the problem is finding, for any real a > 0, a super-exponential function f ( x ) = x a over real x > −2 that satisfies

( − 1 ) a = 0

0 a = 1

x a = a ( ( x − 1 ) a )  for all real  x > − 1.

A fourth requirement that is usually one of:

A continuity requirement (usually just that x a is continuous in both variables for x > 0 ).

A differentiability requirement (can be once, twice, k times, or infinitely differentiable in x).

A regularity requirement (implying twice differentiable in x) that:

( d 2 d x 2 f ( x ) > 0 ) for all x > 0

The fourth requirement differs from author to author, and between approaches. There are two main approaches to extending tetration to real heights, one is based on the regularity requirement, and one is based on the differentiability requirement. These two approaches seem to be so different that they may not be reconciled, as they produce results inconsistent with each other.

When x a is defined for an interval of length one, the whole function easily follows for all x > −2.

Linear approximation for the extension to real heights

A linear approximation (solution to the continuity requirement, approximation to the differentiability requirement) is given by:

x a ≈ { log a ⁡ ( x + 1 a ) x ≤ − 1 1 + x − 1 < x ≤ 0 a ( x − 1 a ) 0 < x

hence:

Approximation Domain x a ≈ x + 1 for  − 1 < x < 0 x a ≈ a x for  0 < x < 1 x a ≈ a a ( x − 1 ) for  1 < x < 2

and so on. However, it is only piecewise differentiable; at integer values of x the derivative is multiplied by ln ⁡ a . It is continuously differentiable for x > − 2 if and only if a = e .

Examples: π / 2 e ≈ 5.868... , − 4.3 0.5 ≈ 4.03335...

A main theorem in Hooshmand's paper states: Let 0 < a ≠ 1 . If f : ( − 2 , + ∞ ) → R is continuous and satisfies the conditions:

f ( x ) = a f ( x − 1 ) for all x > − 1 , f ( 0 ) = 1 ,

f is differentiable on ( − 1 , 0 ) ,

f ′ is a nondecreasing or nonincreasing function on ( − 1 , 0 ) ,

f ′ ( 0 + ) = ( ln ⁡ a ) f ′ ( 0 − )  or  f ′ ( − 1 + ) = f ′ ( 0 − ) .

then f is uniquely determined through the equation

f ( x ) = exp a [ x ] ⁡ ( a ( x ) ) = exp a [ x + 1 ] ⁡ ( ( x ) ) for all x > − 2 ,

where ( x ) = x − [ x ] denotes the fractional part of x and exp a [ x ] is the [ x ] -iterated function of the function exp a .

The proof is that the second through fourth conditions trivially imply that f is a linear function on [−1, 0].

The linear approximation to natural tetration function x e is continuously differentiable, but its second derivative does not exist at integer values of its argument. Hooshmand derived another uniqueness theorem for it which states:

If f : ( − 2 , + ∞ ) → R is a continuous function that satisfies:

f ( x ) = e f ( x − 1 ) for all x > − 1 , f ( 0 ) = 1 ,

f is convex on ( − 1 , 0 ) ,

f ′ ( 0 − ) ≤ f ′ ( 0 + ) .

then f = uxp . [Here f = uxp is Hooshmand's name for the linear approximation to the natural tetration function.]

The proof is much the same as before; the recursion equation ensures that f ′ ( − 1 + ) = f ′ ( 0 + ) , and then the convexity condition implies that f is linear on (−1, 0).

Therefore, the linear approximation to natural tetration is the only solution of the equation f ( x ) = e f ( x − 1 ) ( x > − 1 ) and f ( 0 ) = 1 which is convex on ( − 1 , + ∞ ) . All other sufficiently-differentiable solutions must have an inflection point on the interval (−1, 0).

Higher order approximations for the extension to real heights

A quadratic approximation (to the differentiability requirement) is given by:

x a ≈ { log a ⁡ ( x + 1 a ) x ≤ − 1 1 + 2 ln ⁡ ( a ) 1 + ln ⁡ ( a ) x − 1 − ln ⁡ ( a ) 1 + ln ⁡ ( a ) x 2 − 1 < x ≤ 0 a ( x − 1 a ) 0 < x

which is differentiable for all x > 0 , but not twice differentiable. If a = e this is the same as the linear approximation.

Example: 1 / 2 2 ≈ 1.45933...

Note that this function does not satisfy condition that tetration "cancels out" (for example as in raising to power: ( a 1 / n ) n = a ), because it is calculated top-down (as explained in section Iterated powers above) namely:

n ( 1 / n a ) = ( 1 / n a ) ( 1 / n a ) ⋅ ⋅ ⋅ ⋅ ( 1 / n a ) ⏟ n ≠ a .

A cubic approximation and a method for generalizing to approximations of degree n are given at.

Extension to complex heights

It has now been proven that there exists a unique function F which is a solution of the equation F(z+1)=exp(F(z)) and satisfies the additional conditions that F(0)=1 and F(z) approaches the fixed points of the logarithm (roughly 0.318 ± 1.337i) as z approaches ±i∞ and that F is holomorphic in the whole complex z-plane, except the part of the real axis at z≤−2. This proof confirms a previous conjecture. The complex map of this function is shown in the figure at right. The proof also works for other bases besides e, as long as the base is bigger than e 1 / e . The complex double precision approximation of this function is available online.

The requirement of the tetration being holomorphic is important for its uniqueness. Many functions S can be constructed as

S ( z ) = F (   z   + ∑ n = 1 ∞ sin ⁡ ( 2 π n z )   α n + ∑ n = 1 ∞ ( 1 − cos ⁡ ( 2 π n z ) )   β n )

where α and β are real sequences which decay fast enough to provide the convergence of the series, at least at moderate values of ℑ ( z ) .

The function S satisfies the tetration equations S(z+1)=exp(S(z)), S(0)=1, and if α_n and β_n approach 0 fast enough it will be analytic on a neighborhood of the positive real axis. However, if some elements of {α} or {β} are not zero, then function S has multitudes of additional singularities and cutlines in the complex plane, due to the exponential growth of sin and cos along the imaginary axis; the smaller the coefficients {α} and {β} are, the further away these singularities are from the real axis.

The extension of tetration into the complex plane is thus essential for the uniqueness; the real-analytic tetration is not unique.

Non-elementary recursiveness

Tetration (restricted to N 2 ) is not an elementary recursive function. We can easily prove by induction that for every elementary recursive function f, there is a constant c s.t.

f ( x ) ≤ 2 2 ⋅ ⋅ x ⏟ c .

We denote the right hand side by g ( c , x ) . Suppose on the contrary that tetration is elementary recursive. g ( x , x ) + 1 is also elementary recursive. By the above inequality, there is a constant c such that g ( x , x ) + 1 ≤ g ( c , x ) . By letting x = c , we have that g ( c , c ) + 1 ≤ g ( c , c ) , a contradiction.

Open questions

It is not known whether there is a positive integer n for which ⁿπ or ⁿe is an integer. In particular, it is not known whether ⁴π is an integer.

It is not known whether ⁿq is an integer for any positive integer n and positive non-integer rational q. Particularly, it is not known whether the positive root of the equation ⁴x = 2 is a rational number.

Inverse operations

Exponentiation has two inverse operations; roots and logarithms. Analogously, the inverses of tetration are often called the super-root, and the super-logarithm.

Super-root

The super-root is the inverse operation of tetration with respect to the base: if n y = x , then y is an nth super root of x. For example,

4 2 = 2 2 2 2 = 65 , 536

so 2 is the 4th super-root of 65,536 and

4 3 = 3 3 3 3 = 7 , 625 , 597 , 484 , 987

so 3 is the 4th super-root of 7,625,597,484,987.

Square super-root

The 2nd-order super-root, square super-root, or super square root has two equivalent notations, s s r t ( x ) and x s . It is the inverse of 2 x = x x and can be represented with the Lambert W function:

s s r t ( x ) = e W ( l n ( x ) ) = l n ( x ) W ( l n ( x ) )

The function also illustrates the reflective nature of the root and logarithm functions as the equation below only holds true when y = s s r t ( x ) :

x y = log y ⁡ x

Like square roots, the square super-root of x may not have a single solution. Unlike square roots, determining the number of square super-roots of x may be difficult. In general, if e − 1 / e < x < 1 , then x has two positive square super-roots between 0 and 1; and if x > 1 , then x has one positive square super-root greater than 1. If x is positive and less than e − 1 / e it doesn't have any real square super-roots, but the formula given above yields countably infinitely many complex ones for any finite x not equal to 1. The function has been used to determine the size of data clusters.

Other super-roots

For each integer n > 2, the function ⁿx is defined and increasing for x ≥ 1, and ⁿ1 = 1, so that the nth super-root of x, x n s , exists for x ≥ 1.

However, if the linear approximation above is used, then y x = y + 1 if −1 < y ≤ 0, so y y + 1 s cannot exist.

Other super-roots are expressible under the same basis used with normal roots: super cube roots, the function that produces y when x = y y y , can be expressed as x 3 s ; the 4th super-root can be expressed as x 4 s ; and it can therefore be said that the n^th super-root is x n s . Note that x n s may not be uniquely defined, because there may be more than one n^th root. For example, x has a single (real) super-root if n is odd, and up to two if n is even.

The super-root can be extended to n = ∞ , and this shows a link to the mathematical constant e as it is only well-defined if 1/e ≤ x ≤ e (see extension of tetration to infinite heights). Note that x = ∞ y = y [ ∞ y ] = y x , and thus that y = x 1 / x . Therefore, when it is well defined, x ∞ s = x 1 / x and thus it is an elementary function. For example, 2 ∞ s = 2 1 / 2 = 2 .

It follows from the Gelfond–Schneider theorem that super-root n s for any positive integer n is either integer or transcendental, and n 3 s is either integer or irrational. But it is still an open question whether irrational super-roots are transcendental in the latter case.

Super-logarithm

Once a continuous increasing (in x) definition of tetration, ^xa, is selected, the corresponding super-logarithm slog_a x is defined for all real numbers x, and a > 1.

The function slog_a x satisfies:

slog a ⁡ x a = x slog a ⁡ a x = 1 + slog a ⁡ x slog a ⁡ x = 1 + slog a ⁡ log a ⁡ x slog a ⁡ x > − 2