User:Daniel Geisler/Tetration

Not to be confused with titration.

User:Daniel Geisler/Tetration Background

Tetration by period

Tetration by escape

In mathematics, tetration (or hyper-4) is an operation based on iterated, or repeated, exponentiation. It is the next hyperoperation after exponentiation, but before pentation. The word was coined by Reuben Louis Goodstein from tetra- (four) and iteration.

Under the definition as repeated exponentiation, the notation ${^{n}a}$ means ${a^{a^{\cdot ^{\cdot ^{a}}}}}$, where n copies of a are iterated via exponentiation, right-to-left, I.e. the application of exponentiation $n-1$ times. n is called the "height" of the function, while a is called the "base," analogous to exponentiation. It would be read as "the nth tetration of a".

The two inverses of tetration are called the super-root and the super-logarithm, analogous to the nth root and the logarithmic functions. None of the three functions are elementary.

Tetration is used for the notation of very large numbers.

Introduction

The first four hyperoperations are shown here, with tetration being considered the fourth in the series. The unary operation succession, defined as $a'=a+1$, is considered to be the zeroth operation.

1. Addition

   $a+n=a+\underbrace {1+1+\cdots +1} _{n}$

   n copies of 1 added to a.

2. Multiplication

   $a\times n=\underbrace {a+a+\cdots +a} _{n}$

   n copies of a combined by addition.

3. Exponentiation

   $a^{n}=\underbrace {a\times a\times \cdots \times a} _{n}$

   n copies of a combined by multiplication.

4. Tetration

   ${^{n}a}=\underbrace {a^{a^{\cdot ^{\cdot ^{a}}}}} _{n}$

   n copies of a combined by exponentiation, right-to-left.

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 ${\ \atop {\ }}{{\underbrace {a^{a^{\cdot ^{\cdot ^{a}}}}} } \atop n}$. This is a misnomer, however, because tetration cannot be expressed with iterated power functions (see above), since it is an iterated exponential function.

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. Some notations can also be used to describe other hyperoperations, while some are limited to tetration and have no immediate extension.

Name	Form	Description
Rudy Rucker 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.

Properties

Tetration has several properties that are similar to exponentiation, as well as properties that are specific to the operation and are lost or gained from exponentiation. Because exponentiation does not commute, the product and power rules do not have an analogue with tetration; the statements ${\textstyle {}^{a}\left({}^{b}x\right)=\left({}^{ab}x\right)}$ and ${\textstyle {}^{a}\left(xy\right)={}^{a}x{}^{a}y}$ are not necessarily true for all cases.

Direction of evaluation

When evaluating tetration expressed as an "exponentiation tower", the exponentiation is done at the deepest level first (in the notation, at the apex). For example:

$\,\!\ ^{4}2=2^{2^{2^{2}}}=2^{\left(2^{\left(2^{2}\right)}\right)}=2^{\left(2^{4}\right)}=2^{16}=65,\!536$

This order is important because exponentiation is not associative, and evaluating the expression in the opposite order will lead to a different answer:

$\,\!2^{2^{2^{2}}}\neq \left({\left(2^{2}\right)}^{2}\right)^{2}=4^{2\cdot 2}=256$

Evaluating the expression the left to right is considered less interesting; evaluating left to right, any expression $^{n}a\!$ can be simplified to be $a^{\left(a^{n-1}\right)}\!\!$. Because of this, the towers must be evaluated from right to left (or top to bottom). Computer programmers refer to this choice as right-associative.

Non-elementary recursiveness

Tetration (restricted to $\mathbb {N} ^{2}$) is not an elementary recursive function. One can prove by induction that for every elementary recursive function f, there is a constant c such that

$f(x)\leq \underbrace {2^{2^{\cdot ^{\cdot ^{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\leq g(c,x)$. By letting $x=c$, we have that $g(c,c)+1\leq g(c,c)$, a contradiction.

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 (In fact, all hyperoperations greater than or equal to 3 have analogous inverses); e.g., in the function ${^{3}}y=x$, the two inverses are the cube super-root of y and the super logarithm base y of x.

Super-root

"Super-root" redirects here. For the directory supported by some Unixes, see super-root (computing).

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 (${\sqrt[{n}]{x}}_{s}$ or ${\sqrt[{n}]{x}}_{4}$).

For example,

$^{4}2=2^{2^{2^{2}}}=65{,}536$

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

Square super-root

The graph $y={\sqrt {x}}_{s}$.

The 2nd-order super-root, square super-root, or super square root has two equivalent notations, $\mathrm {ssrt} (x)$ and ${\sqrt {x}}_{s}$. It is the inverse of $^{2}x=x^{x}$ and can be represented with the Lambert W function:

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

The function also illustrates the reflective nature of the root and logarithm functions as the equation below only holds true when $y=\mathrm {ssrt} (x)$:

${\sqrt[{y}]{x}}=\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.

At $x=1$ :

$\mathrm {ssqrt} (x)=1+(x-1)-(x-1)^{2}+{\frac {3}{2}}(x-1)^{3}-{\frac {17}{6}}(x-1)^{4}+{\frac {37}{6}}(x-1)^{5}-{\frac {1759}{120}}(x-1)^{6}+{\frac {13279}{360}}(x-1)^{7}+\mathrm {O} \left((x-1)^{8}\right)$

See also

• Ackermann function
• Big O notation
• Double exponential function
• Hyperoperation
• Iterated logarithm
• Symmetric level-index arithmetic

References

• Daniel Geisler, iteratedfunctions.com
• 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.)
• Joseph MacDonell, Some Critical Points of the Hyperpower Function.
• Dave L. Renfro, Web pages for infinitely iterated exponentials
• Knobel R (1981). "Exponentials Reiterated". American Mathematical Monthly. 88 (4): 235–252. doi:10.1080/00029890.1981.11995239.
• Hans Maurer, "Über die Funktion $y=x^{[x^{[x(\cdots )]}]}$ für ganzzahliges Argument (Abundanzen)." Mittheilungen der Mathematische Gesellschaft in Hamburg 4, (1901), p. 33–50. (Reference to usage of $\ {^{n}a}$ from Knobel's paper.)
• The Fourth Operation
• Luca Moroni, The strange properties of the infinite power tower (https://arxiv.org/abs/1908.05559)

Further reading

• Galidakis, Ioannis and Weisstein, Eric W. "Power Tower". MathWorld. Retrieved 5 July 2019.{{cite web}}: CS1 maint: multiple names: authors list (link)

[[Category:Exponentials]] [[Category:Binary operations]] [[Category:Large numbers]]