Tetration
From Wikipedia, the free encyclopedia
It has been suggested that Ultra exponential function be merged into this article or section. (Discuss) |
In mathematics, tetration (also known as hyper-4) is an iterated exponential, the first hyper operator after exponentiation. The portmanteau 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 its study is part of only pure mathematics. Shown here are examples of the first four hyper operators, with tetration as the fourth:
- addition
-
- 1 added to a b times.
-
- multiplication
-
- a added to a b-1 times.
-
- exponentiation
-
- a multiplied by a b-1 times.
-
- tetration
-
- a exponentiated by a b-1 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 , while for tetration, no such regular generalization is yet established; and tetration is not considered an elementary function.
Addition (a+b) can be thought of as being b iterations of the "add one" function applied to a, multiplication (ab) can be thought of as a chained addition involving b numbers a, and exponentiation (ab) can be thought of as a chained multiplication involving b numbers a. Analogously, tetration (ba) can be thought of as a chained power involving b numbers a. The parameter a may be called the base-parameter in the following, while the parameter b 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] Iterated powers
Note that 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:
The convention for iterated exponentiation is to work from the right to the left. Thus,
- .
To generalize the first case (tetration) above, a new notation is needed (see below); however, the second case can be written as
Thus, its general form still uses ordinary exponentiation notation.
In general, we can use Knuth's up-arrow notation to write a power as which allows us to write its general form as:
[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 b" for
- 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 Tetration Iterated exponentials Nested exponentials (also towers) Infinite exponentials (also towers)
In the first two expressions a is the base, and the number of as is the height (add one for x). In the third expression, n is the height, but each of the bases are 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 Used by Goodstein[1947]; Rudy Rucker's book Infinity and the Mind popularized the notation. Knuth's up-arrow notation Allows extension by putting more arrows, or, even more powerfully, an indexed arrow. Conway chained arrow notation Allows extension by increasing the number 2 (equivalent with the extensions above), but also, even more powerfully, by extending the chain Ackermann function Allows the special case a = 2 to be written in terms of the Ackermann function. Iterated exponential notation Allows simple extension to iterated exponentials from initial values other than 1. Hooshmand notation[1] Hyper operator notation Allows extension by increasing the number 4; this gives the family of hyper operators ASCII notation a^^b
Since the up-arrow is used identically to the caret ( ^
), the tetration operator may be written as (^^
).
One notation above shows that tetration can be written as an iterated exponential function where the initial value is one. As a reminder, iterated exponentials have the general form:
- with n a's.
There are not as many notations for iterated exponentials, but here are a few:
-
Name Form Description Standard notation Euler coined the notation expa(x) = ax, and iteration notation fn(x) has been around about as long. Knuth's up-arrow notation Allows for super-powers and super-exponential function by increasing the number of arrows; used in the article on large numbers. Ioannis Galidakis' notation 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.
-
n 2n 3n 4n 1 1 1 1 2 4 16 65,536 3 27 7,625,597,484,987 4 256 5 3,125 6 46,656 7 823,543 8 16,777,216 9 387,420,489 10 10,000,000,000
[edit] Extensions
Extending to real numbers x > 0 is straightforward and gives, for each natural number b, a super-power function . The term super is sometimes replaced by hyper, but this only applies to tetration with integer height, and is falling out of usage. All other uses of the two prefixes use the convention: hyper for all ranks of hyper operators, and super for the rank 4 hyper operator, known as tetration.
Consider , where , , and . Initially, may mean "reals", and each of and may mean "non-negative integers". For the extension to other sets , and , one has no need to deal with a function of 3 variables. Let , where is an invertible function. Then tetration can be expressed as follows:
- .
For this reason, in the subsections below, various extensions of a function of 2 variables are considered.
[edit] Extension to infinitesimal bases
Sometimes, 00 is taken to be an undefined quantity. In this case, values for cannot be defined directly. However, is well defined, and exists:
This limit holds for negative n, as well. could be defined in terms of this limit and this would agree with a definition of 00 = 1. This limit definition holds for 20 = 1 because 2 is even, and holds for 00 = 1 because 0 is even.
[edit] Extension to complex bases
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, kz where z = i, tetration is achieved by using the principal branch of the natural logarithm, and using Euler's formula we get the relation:
This suggests a recursive definition for (k + 1)i = a' + b'i given any ki = a + bi:
The following approximate values can be derived:
-
ki Approximate Value 1i = i i 0.2079 0.9472 + 0.3208i 0.0501 + 0.6021i 0.3872 + 0.0305i 0.7823 + 0.5446i 0.1426 + 0.4005i 0.5198 + 0.1184i 0.5686 + 0.6051i
Solving the inverse relation as in the previous section, yields the expected and , with negative values of k 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 k 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
Tetration can be extended to heights (b in ba) that are not finite, but infinite. This is because for bases within a certain interval, tetration converges to a finite value as the height tends to infinity. For example, 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:
In general, the infinite power tower , defined as the limit of nx as n goes to infinity, converges for e−e ≤ x ≤ e1/e, roughly the interval from 0.066 to 1.44, a result due to 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:
where W(z) represents Lambert's W function. As the limit (if existent, i.e. for e−e < x < e1/e) must satisfy xy = y we see that is (the lower branch of) the inverse function of .
[edit] Extension to negative heights
Tetration can be extended to heights that are negative. Using the relation:
(which follows from the definition of tetration), one can derive (or define) values for kn where .
This confirms the intuitive definition of 1n as simply being n. However, no further values can be derived by further iteration in this fashion, as logn0 is undefined.
Similarly, since log11 is also undefined:
the derivation above does not hold when n = 1. Therefore, ( − 1)1 must remain an undefined quantity as well. (The figure 01 can safely be defined as 1, however.)
[edit] 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 b, although it is an active area of research. Various approaches are mentioned below. For an approach that is still disputed until it has been reviewed further, see ultra exponential function.
In general the problem is finding, for any real a > 0, a super-exponential function over real x > − 2 that satisfies
- for all real b > -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, n times, or infinitely differentiable in x).
- A regularity requirement (implying twice differentiable in x) that:
- 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 is defined for an interval of length one, the whole function easily follows for all x > − 2.
A linear approximation (solution to the continuity requirement, approximation to the differentiability requirement) is given by:
hence:
-
Approximation Domain for − 1 < x < 0 for 0 < 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:
which is differentiable for all x > 0, but not twice differentiable.
Other, more complicated solutions may be smoother and/or satisfy additional properties. When defining xa for every a, another possible requirement could be that xa is monotonically increasing with a. Other solutions require not just continuity, but differentiability, or even infinite differentiability. Another approach is to define tetration over real heights as the inverse of the super-logarithm, which is its inverse function with respect to the height.
[edit] Extension to complex heights
The conjecture is suggested [2], 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 ) as z approaches , and that F is holomorphic in the whole complex z-plane, except the part of the real axis at . This function is shown in the figure at right. The complex double precision approximation of this function is available online [3].
The requirement of holomorphism of tetration is important for the uniqueness. Many functions S can be constructed as
where α and β are real sequences which decay fast enough to provide the convergence of the series, at least at moderate values of .
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] Super-exponential growth
A super-exponential function grows even faster than a double exponential function; for example, if a = 10 and we use the (not very smooth) linear approximation:
- f( − 1) = 0
- f(0) = 1
- f(1) = 10
- f(2) = 1010
- f(2.3) = 10100 (googol)
- (googolplex)
- It passes at x = 2.376:
[edit] Approaches to inverse functions
The inverse functions of tetration are called the super-root (or hyper-4-root), and the super-logarithm (or hyper-4-logarithm). The square super root ssrt(x) which is the inverse function of xx can be represented with the Lambert W function:
The super-logarithm slogab is defined for all positive and negative real numbers.
The function sloga satisfies:
- slogaab = 1 + slogab
- slogab = 1 + slogalogab
- slogab > − 2
[edit] See also
[edit] References
- ^ M.H.Hooshmand, (2006). "Ultra power and ultra exponential functions". Integral Transforms and Special Functions 17 (8): 549–558. doi:. http://www.informaworld.com/smpp/content~content=a747844256?words=ultra%7cpower%7cultra%7cexponential%7cfunctions&hash=721628008.
- ^ D.Kouznetsov (2009). ""Solution of F(z + 1) = exp(F(z)) in complex z-plane"". Mathematics of computation. http://www.ams.org/mcom/0000-000-00/S0025-5718-09-02188-7/home.html.
- ^ Mathematica code for evaluation and plotting of the tetration and its derivatives. http://en.citizendium.org/wiki/TetrationDerivativesReal.jpg/code
- Daniel Geisler, tetration.org
- Ioannis Galidakis, On extending hyper4 to nonintegers (undated, 2006 or earlier) (A simpler, easier to read review of the next reference)
- Ioannis Galidakis , On Extending hyper4 and Knuth's Up-arrow Notation to the Reals (undated, 2006 or earlier).
- Robert Munafo, Extension of the hyper4 function to reals (An informal discussion about extending tetration to the real numbers.)
- Lode Vandevenne, Tetration of the Square Root of Two, (2004). (Attempt to extend tetration to real numbers.)
- Ioannis Galidakis, Mathematics, (Definitive list of references to tetration research. Lots of information on the Lambert W function, Riemann surfaces, and analytic continuation.)
- Galidakis, Ioannis and Weisstein, Eric W. Power Tower
- Joseph MacDonell, Some Critical Points of the Hyperpower Function.
- Dave L. Renfro, Web pages for infinitely iterated exponentials (Compilation of entries from questions about tetration on sci.math.)
- Andrew Robbins, Home of Tetration (An infinitely differentiable extension of tetration to real numbers.)
- R. Knobel. "Exponentials Reiterated." American Mathematical Monthly 88, (1981), p. 235-252.
- Hans Maurer. "Über die Funktion für ganzzahliges Argument (Abundanzen)." Mittheilungen der Mathematische Gesellschaft in Hamburg 4, (1901), p. 33-50. (Reference to usage of from Knobel's paper.)
- Reuben Louis Goodstein. "Transfinite ordinals in recursive number theory." Journal of Symbolic Logic 12, (1947).