Tetration

From Wikipedia, the free encyclopedia

Jump to: navigation, search
Complex plot of holomorphic tetration ze.
nx, for n = 1, 2, 3 ..., showing convergence to the infinite power tower between the two dots.
Infinite power tower

In mathematics, tetration (also known as hyper-4) is an iterated exponential, the first hyper operator after exponentiation. The word tetration was coined by English mathematician Reuben Louis Goodstein from tetra- (four) and iteration. Tetration is used for the notation of very large numbers but has few practical applications, so it has only been studied in pure mathematics. Shown here are examples of the first four hyper operators, with tetration as the fourth:

  1. addition
    The primary and simplest operation.
  2. multiplication
    a \times n = \underbrace{a + a + \cdots + a}_n
    a added to itself, n times.
  3. exponentiation
    a^n = \underbrace{a \times a \times \cdots \times a}_n
    a multiplied by itself, n times.
  4. tetration
    {^{n}a} = \underbrace{a^{a^{\cdot^{\cdot^{a}}}}}_n
    a exponentiated by itself, n times.

where each operation is defined by iterating the previous one. The peculiarity of the tetration among these operations is that the first three (addition, multiplication and exponentiation) are generalized for complex values of n, while for tetration, no such regular generalization is yet established; and tetration is not considered an elementary function.

Addition is the most basic operation, multiplication (an) can be thought of as a chained addition involving n numbers a, and exponentiation (an) can be thought of as a chained multiplication involving n numbers a. Analogously, tetration (na) can be thought of as a chained power involving n numbers a. The parameter a may be called the base-parameter in the following, while the parameter n in the following may be called the height-parameter (which is integral in the first approach but may be generalized to fractional, real and complex heights, see below)

Contents

[edit] Definition

For any positive real a > 0 and non-negative integer  n \ge 0 , we define \,\! {^{n}a} by:

  • \,\! {^{0}a} = 1 (if n = 0) and
  • \,\! {^{n}a} = a^{(^{n-1}a)} (if n > 0)

[edit] Iterated powers

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). In other words:

\,\!\ ^{4}2 = 2^{2^{2^2}} = 2^{\left(2^{\left(2^2\right)}\right)} = 2^{\left(2^4\right)} = 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}} \ne \left({\left(2^2\right)}^2\right)^2 = 2^{2 \cdot 2 \cdot2} = 256

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

[edit] 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 super-exponentiation was published by Bromer in his paper Superexponentiation in 1987.
  • 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 hyper operator hierarchy. When considering hyper operators, 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 {\ \atop {\ }} {{\underbrace{a^{a^{\cdot^{\cdot^{a}}}}}} \atop n}
  • Ultra exponential is also used, see Ultra exponential function.

Tetration is often confused with closely related functions and expressions. This is because much of the terminology that is used with them can be used with tetration. Here are a few related terms:

Form Terminology
a^{a^{\cdot^{\cdot^{a^a}}}} Tetration
a^{a^{\cdot^{\cdot^{a^x}}}} Iterated exponentials
a_1^{a_2^{\cdot^{\cdot^{a_n}}}} Nested exponentials (also towers)
a_1^{a_2^{a_3^{\cdot^{\cdot^\cdot}}}} Infinite exponentials (also towers)

In the first two expressions a is the base, and the number of 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.

[edit] Notation

The notations in which tetration can be written (some of which allow even higher levels of iteration) include:

Name Form Description
Standard notation \,{}^{n}a Used by Maurer [1901] and Goodstein[1947]; Rudy Rucker's book Infinity and the Mind popularized the notation.
Knuth's up-arrow notation a {\uparrow\uparrow} n Allows extension by putting more arrows, or, even more powerfully, an indexed arrow.
Conway chained arrow notation a \rightarrow n \rightarrow 2 Allows extension by increasing the number 2 (equivalent with the extensions above), but also, even more powerfully, by extending the chain
Ackermann function {}^{n}2 = \operatorname{A}(4, n - 3) + 3 Allows the special case a = 2 to be written in terms of the Ackermann function.
Iterated exponential notation {}^{n}a = \exp_a^n(1) Allows simple extension to iterated exponentials from initial values other than 1.
Hooshmand notation[1] \operatorname{uxp}_a n, \,  a^{\frac{n}{}}
Hyper operator notation a^{(4)}n, \, \operatorname{hyper}_4(a,n) Allows extension by increasing the number 4; this gives the family of hyper operations
ASCII notation a^^n Since the up-arrow is used identically to the caret (^), the tetration operator may be written as (^^).

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

\exp_a^n(x) = a^{a^{\cdot^{\cdot^{a^x}}}} with n a's.

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

Name Form Description
Standard notation \exp_a^n(x) Euler coined the notation expa(x) = ax, and iteration notation fn(x) has been around about as long.
Knuth's up-arrow notation (a{\uparrow})^n(x) Allows for super-powers and super-exponential function by increasing the number of arrows; used in the article on large numbers.
Ioannis Galidakis' notation \,{}^{n}(a, x) Allows for large expressions in the base; used by Ioannis Galidakis in On Extending hyper4 ... to the Reals.
ASCII (auxiliary) a^^n@x Based on the view that an iterated exponential is auxiliary tetration.
ASCII (standard) exp_a^n(x) Based on standard notation.

[edit] 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.

x 2x 3x 4x
1 1 1 1
2 4 16 65,536
3 27 7,625,597,484,987 \exp_{10}^3(1.09902)
4 256 \exp_{10}^2(2.18788) \exp_{10}^3(2.18726)
5 3,125 \exp_{10}^2(3.33931) \exp_{10}^3(3.33928)
6 46,656 \exp_{10}^2(4.55997) \exp_{10}^3(4.55997)
7 823,543 \exp_{10}^2(5.84259) \exp_{10}^3(5.84259)
8 16,777,216 \exp_{10}^2(7.18045) \exp_{10}^3(7.18045)
9 387,420,489 \exp_{10}^2(8.56784) \exp_{10}^3(8.56784)
10 10,000,000,000 \exp_{10}^3(1) \exp_{10}^4(1)

[edit] Extensions

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

[edit] Extension to base zero

The exponential 00 is non consistently defined. Thus, the tetrations \,{^{n}0} are not clearly defined by the formula given earlier. However, \lim_{x\rightarrow0} {}^{n}x is well defined, and exists:

\lim_{x\rightarrow0} {}^{n}x = \begin{cases} 1, & n \mbox{ even} \\ 0, & n \mbox{ odd} \end{cases}

Thus we could consistently define {}^{n}0 = \lim_{x\rightarrow0} {}^{n}x. This is equivalent to defining 00 = 1.

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

[edit] Extension to complex bases

Tetration by period
Tetration by escape

Since complex numbers can be raised to powers, tetration can be applied to bases of the form z = a + bi, where i is the square root of −1. For example, nz 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+bi} = e^{{i\pi \over 2} (a+bi)} = e^{-{b\pi \over 2}} \left(\cos{a\pi \over 2} + i \sin{a\pi \over 2}\right)

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

a' = e^{-{b\pi \over 2}} \cos{a\pi \over 2}
b' = e^{-{b\pi \over 2}} \sin{a\pi \over 2}

The following approximate values can be derived:

ni Approximate Value
1i = i i
{}^{2}i = i^{\left({}^{1}i\right)} 0.2079
{}^{3}i = i^{\left({}^{2}i\right)} 0.9472 + 0.3208i
{}^{4}i = i^{\left({}^{3}i\right)} 0.0501 + 0.6021i
{}^{5}i = i^{\left({}^{4}i\right)} 0.3872 + 0.0305i
{}^{6}i = i^{\left({}^{5}i\right)} 0.7823 + 0.5446i
{}^{7}i = i^{\left({}^{6}i\right)} 0.1426 + 0.4005i
{}^{8}i = i^{\left({}^{7}i\right)} 0.5198 + 0.1184i
{}^{9}i = i^{\left({}^{8}i\right)} 0.5686 + 0.6051i

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.3606i, 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 power tower 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.

[edit] Extension to infinite heights

The function \left | \frac{\mathrm{W}(-\ln{z})}{-\ln{z}} \right | on the complex plane, showing infinite real power towers (black curve)

Tetration can be extended to infinite heights (n in na). This is because for bases within a certain interval, tetration converges to a finite value as the height tends to infinity. For example, \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdot^{\cdot^{\cdot}}}}} 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:

\begin{align}
\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{1.41}}}}} &= \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\sqrt{2}^{1.63}}}} \\
&= \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{1.76}}} = \sqrt{2}^{\sqrt{2}^{1.84}} \\
&= \sqrt{2}^{1.89} = 1.93
\end{align}

In general, the infinite power tower x^{x^{\cdot^{\cdot^{\cdot}}}}, defined as the limit of nx as n goes to infinity, converges for ee ≤ x ≤ e1/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 = xy. Thus, x = y1/y. The limit defining the infinite tetration of x fails to converge for x > e1/e because the maximum of y1/y is e1/e.

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

{}^{\infty}z = z^{z^{\cdot^{\cdot^{\cdot}}}} = \frac{\mathrm{W}(-\ln{z})}{-\ln{z}}

where W(z) represents Lambert's W function.

As the limit y = x (if existent, i.e. for ee < x < e1/e) must satisfy xy = y we see that x ↦ y = x is (the lower branch of) the inverse function of y ↦ x = y1/y.

[edit] 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 \left( {^{(k+1)}a} \right)

Thus:

 {}^{(-1)}a = \log_{a} \left( {}^{0}a \right) = \log_{a} 1 = 0

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

 {}^{(-2)}a = \log_{a} \left( {}^{-1}a \right) = \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

01 = 1 = 1n for any \,\! n = {^{(-1)}1} .

[edit] Extension to real heights

\,{}^{x}e using linear approximation.

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^{\left({}^{(x-1)}a\right)} for all real x > -1.
  • A fourth requirement that is usually one of:
  • A continuity requirement (usually just that xa 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:
\left( \frac{d^2}{dx^2}f(x) > 0\right) 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.

Fortunately, any solution that satisfies one of these in an interval of length one can be extended to a solution for all positive real numbers. When \,{}^{x}a is defined for an interval of length one, the whole function easily follows for all x > − 2.

[edit] Polynomial approximations

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

{}^{x}a \approx \begin{cases}
\log_a({}^{(x+1)}a) & x \le -1 \\
1 + x & -1 < x \le 0 \\
a^{\left({}^{(x-1)}a\right)} & x > 0
\end{cases}

hence:

Approximation Domain
\,{}^{x}a \approx x+1 for − 1 < x < 0
\,{}^{x}a \approx a^x for 0 < x < 1
\,{}^{x}a \approx 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 lna.

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

{}^{x}a \approx \begin{cases}
\log_a({}^{(x+1)}a) & x \le -1 \\
1 + \frac{2\log(a)}{1+\log(a)}x - \frac{1-\log(a)}{1+\log(a)}x^2 & -1 < x \le 0 \\
a^{\left({}^{(x-1)}a\right)} & x > 0
\end{cases}

which is differentiable for all x > 0, but not twice differentiable.

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

[edit] Ultra exponential function

\lim_{n\rightarrow \infty} x^{\frac{n}{}} Infinite power tower.

Hooshmand introduced a super exponential function he calls the ultra exponential function.[1]

A main theorem in Hooshmand's paper states: Let  0 <a \neq 1. If f:(-2,+\infty)\rightarrow \mathbb{R} satisfies the conditions:

  •  f(x)=a^{f(x-1)} \; \; \mbox{for all} \; \; x>-1, \; f(0)=1 ,
  • f is differentiable on ( − 1,0),
  • f^\prime is a nondecreasing or nonincreasing function on ( − 1,0),
  • f^\prime (0^+) = (\ln a) f^\prime (0^-) \mbox{ or } f^\prime (-1^+) = f^\prime (0^-).

then f is uniquely determined through the equation

 \; \; \; f(x)=\exp^{[x]}_a (a^{(x)})=\exp^{[x+1]}_a((x)) \; \; \; \mbox{for all} \; \; x>-2,

where (x) = x − [x] denotes the fractional part of x and  \exp^{[x]}_a is the [x]-iterated function of the function expa.

The ultra exponential function is then defined as  \mbox{uxp}_a(x)=\exp^{[x+1]}_a((x)) \; \; \; \mbox{for all} \; \; x>-2 .

Examples:  \mbox{uxp}_a(0) = 1,\; \mbox{uxp}_a(-1) = 0,\; \mbox{uxp}_2(4) = 65536,\; \mbox{uxp}_e(\pi / 2) = 5.868...,\; \mbox{uxp}_{0.5}(-4.3) = 4.03335...,\;

The natural ultra exponential function uxp(x) = uxpe(x) is continuously differentiable, but its second derivative does not exist at integer values of its argument. There is another uniqueness theorem for it which states:

(Another uniqueness conditions for the natural ultra exponential function). If  f: (-2, +\infty)\rightarrow \mathbb{R} is a function that

  •  f(x)=e^{f(x-1)} \; \; \mbox{for all} \; \; x>-1, \; f(0)=1 ,
  • f is convex on ( − 1,0),
  • f^\prime (0^-)\leq f^\prime (0^+).

then f = uxp.

Therefore uxp is the only solution of the equation  f(x)=e^{f(x-1)} \; \; (x>-1) which is convex on (-1,+\infty) and f(0) = 1.

[edit] Extension to complex heights

Drawing of the analytic extension f = F(x + iy) of tetration to the complex plane. Levels |f|=1,e^{\pm 1},e^{\pm 2},\ldots and levels \arg(f)=0,\pm 1,\pm 2,\ldots are shown with thick curves.

The conjecture is suggested,[3] 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.31813150520476413531 ± 1.33723570143068940890i) 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 function is shown in the figure at right. The complex double precision approximation of this function is available online [4].

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

S(z)=F\!\left(~z~
+\sum_{n=1}^{\infty} \sin(2\pi n z)~ \alpha_n
+\sum_{n=1}^{\infty} \Big(1-\cos(2\pi n z) \Big) ~\beta_n \right)

where α and β are real sequences which decay fast enough to provide the convergence of the series, at least at moderate values of \Im(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.

[edit] Inverse functions

The inverse functions of tetration are often called the super-root, and the super-logarithm. The square super root ssrt(x) which is the inverse function of xx can be represented with the Lambert W function:

\mathrm{ssqrt}(x)=e^{W(\mathrm{ln}(x))}=\frac{\mathrm{ln}(x)}{W(\mathrm{ln}(x))}

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

However, if the linear approximation above is used, then yx = y + 1 if -1≤y≤0, so ysroot(y + 1) cannot exist.

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

The function sloga satisfies:

slogaxa = x
slogaax = 1 + slogax
slogax = 1 + slogalogax
slogax > − 2

[edit] See also

[edit] References

[edit] External links