Tetration

In mathematics, tetration is an operation based on iterated, or repeated, exponentiation. There is no universal notation for tetration, though Knuth's up arrow notation and the left-exponent are common.
Under the definition as repeated exponentiation, means, where copies of are iterated via exponentiation, right-to-left, i.e. the application of exponentiation times. The number is called the height of the function, while is called the base, analogous to exponentiation. It would be read as "the th tetration of ". For example, 2 tetrated to 4 is.
Tetration is the next hyperoperation after exponentiation, but before pentation. Along with the other hyperoperations, tetration is used for the notation of very large numbers. The name was coined by Reuben Goodstein from the prefix tetra- and the word "iteration".
Tetration can also be defined recursively as
This form allows for the extension of tetration to more general domains than the natural numbers such as real, complex, or ordinal numbers.
The two inverses of tetration are called super-root and super-logarithm. They are respectively analogous to the operations of taking th roots and taking logarithms. None of the three functions are elementary.

Introduction

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

Addition copies of 1 added to combined by succession.
Multiplication copies of combined by addition.
Exponentiation copies of combined by multiplication.
Tetration copies of combined by exponentiation, right-to-left.

Importantly, nested exponents are interpreted from the top down: means and not
Succession,, is the most basic operation; while addition is a primary operation, for addition of natural numbers it can be thought of as a chained succession of successors of ; multiplication is also a primary operation, though for natural numbers it can analogously be thought of as a chained addition involving numbers of. Exponentiation can be thought of as a chained multiplication involving numbers of and tetration as a chained power involving numbers. Each of the operations above are defined by iterating the previous one; however, unlike the operations before it, tetration is not an elementary function.
The parameter is referred to as the base, while the parameter may be referred to as the height. In the original definition of tetration, the height parameter must be a natural number; for instance, it would be illogical to say "three raised to itself negative five times" or "four raised to itself one half of a time." However, just as addition, multiplication, and exponentiation can be defined in ways that allow for extensions to real and complex numbers, several attempts have been made to generalize tetration to negative numbers, real numbers, and complex numbers. One such way for doing so is using a recursive definition for tetration; for any positive real and non-negative integer, we can define recursively as:
The recursive definition is equivalent to repeated exponentiation for natural heights; however, this definition allows for extensions to the other heights such as,, and as well – many of these extensions are areas of active research.

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, 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 " for. Exponentiation is easily misconstrued: note that the operation of raising to a power is right-associative. Tetration is iterated exponentiation, starting from the top right side of the expression with an instance a^a. Exponentiating the next leftward a, is to work leftward after obtaining the new value b^c. Working to the left, use the next a to the left, as the base b, and evaluate the new b^c. 'Descend down the tower' in turn, with the new value for c on the next downward step.

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:

Terminology	Form
Tetration
Iterated exponentials
Nested exponentials
Infinite exponentials

In the first two expressions is the base, and the number of times appears is the height. In the third expression, 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. Some notations can also be used to describe other hyperoperations, while some are limited to tetration and have no immediate extension.

Name	Form	Description
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, but also, even more powerfully, by extending the chain.
Ackermann function		Allows the special case 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 notations		Used by M. H. Hooshmand .
Hyperoperation notations		Allows extension by increasing the number 4; this gives the family of hyperoperations.
Double caret notation		Since the up-arrow is used identically to the caret, tetration may be written as ; convenient for ASCII.

One notation above uses iterated exponential notation; this is defined in general as follows:
There are not as many notations for iterated exponentials, but here are a few:

Name	Form	Description
Standard notation		Euler coined the notation, and iteration notation 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.
Text notation		Based on standard notation; convenient for ASCII.
J notation		Repeats the exponentiation. See J (programming language).
Infinity barrier notation		Jonathan Bowers coined this, and it can be extended to higher hyper-operations.

Examples

Because of the extremely fast growth of tetration, most values in the following table are too large to write in scientific notation. In these cases, iterated exponential notation is used to express them in base 10. The values containing a decimal point are approximate. Usually, the limit that can be calculated in a numerical calculation program such as Wolfram Alpha is 3↑↑4, and the number of digits up to 3↑↑5 can be expressed.


1	1	1	1	1	1	1
2	4	16	65,536	2.00353 × 10
3	27	7,625,597,484,987	1.25801 × 10
4	256	1.34078 × 10
5	3,125	1.91101 × 10
6	46,656	2.65912 × 10
7	823,543	3.75982 × 10
8	16,777,216	6.01452 × 10
9	387,420,489	4.28125 × 10
10	10,000,000,000	10

Remark: If does not differ from 10 by orders of magnitude, then for all. For example, in the above table, and the difference is even smaller for the following rows.

Extensions

Tetration can be extended in two different ways; in the equation, both the base and the height can be generalized using the definition and properties of tetration. Although the base and the height can be extended beyond the non-negative integers to different domains, including, complex functions such as, and heights of infinite, the more limited properties of tetration reduce the ability to extend tetration.

Extension of domain for bases

Base zero

The exponential is not consistently defined. Thus, the tetrations are not clearly defined by the formula given earlier. However, is well defined, and exists:
Thus we could consistently define. This is analogous to defining.
Under this extension,, so the rule from the original definition still holds.

Complex bases

Since complex numbers can be raised to powers, tetration can be applied to bases of the form . For example, in with, tetration is achieved by using the principal branch of the natural logarithm; using Euler's formula we get the relation:
This suggests a recursive definition for given any :
The following approximate values can be derived:

	Approximate value

Solving the inverse relation, as in the previous section, yields the expected and, with negative values of giving infinite results on the imaginary axis. Plotted in the complex plane, the entire sequence spirals to the limit, which could be interpreted as the value where 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.

Extensions of the domain for different heights

Infinite heights

Tetration can be extended to infinite heights; i.e., for certain and values in, there exists a well defined result for an 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 infinitely iterated exponential, defined as the limit of as goes to infinity, converges for, 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. Thus,. The limit defining the infinite exponential of does not exist when because the maximum of is. The limit also fails to exist when.
This may be extended to complex numbers with the definition:
where represents Lambert's W function. This formula follows from the assumption that converges, and thus,,, and .
As the limit must satisfy we see that is the inverse function of.

Negative heights

We can reverse the recursive rule for tetration,
to write:
Substituting −1 for gives
Smaller negative values cannot be well defined in this way. Substituting −2 for in the same equation gives
which is not well defined. They can, however, sometimes be considered sets.
For, any definition of is consistent with the rule because

Linear approximation for real heights

A linear approximation is given by:
hence:

Approximation	Domain
	for
	for
	for

and so on. However, it is only piecewise differentiable; at integer values of, the derivative is multiplied by. It is continuously differentiable for if and only if. For example, using these methods and
A main theorem in Hooshmand's paper states: Let. If is continuous and satisfies the conditions:

is differentiable on,
is a nondecreasing or nonincreasing function on,

then is uniquely determined through the equation
where denotes the fractional part of and is the -iterated function of the function.
The proof is that the second through fourth conditions trivially imply that is a linear function on.
The linear approximation to natural tetration function 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 is a continuous function that satisfies:

is convex on,

then.
The proof is much the same as before; the recursion equation ensures that and then the convexity condition implies that is linear on.
Therefore, the linear approximation to natural tetration is the only solution of the equation and which is convex on. All other sufficiently-differentiable solutions must have an inflection point on the interval.

Higher order approximations for real heights

Beyond linear approximations, a quadratic approximation is given by:
which is differentiable for all, but not twice differentiable. For example, If this is the same as the linear approximation.
Because of the way it is calculated, this function does not "cancel out", contrary to exponents, where. Namely,
Just as there is a quadratic approximation, cubic approximations and methods for generalizing to approximations of degree also exist, although they are much more unwieldy.

Complex heights

In 2017, it was proved that there exists a unique function satisfying
, with the auxiliary conditions
, and
as. Moreover, is holomorphic on all of except for the cut along the real axis at. This construction was first conjectured by Kouznetsov and rigorously carried out by Kneser in 1950. Paulsen & Cowgill’s proof extends Kneser’s original construction to any base, and subsequent work showed how to allow with.
In May 2025, Vey gave a unified, holomorphic extension for arbitrary complex bases and complex heights by means of Schröder’s equation. In particular, one constructs a linearizing coordinate near the attracting fixed point of the map, and then patches together two analytic expansions to produce a single function that satisfies
and on all of. The key step is to define
where is a fixed point of,, and denotes -fold iteration. One then solves Schröder’s functional equation
locally, extends both branches holomorphically, and glues them so that there is no monodromy except the known cut-lines. Vey also provides explicit series for the coefficients in the local Schröder expansion:
and gives rigorous bounds proving factorial convergence of.
Using Kneser’s tetration, example values include
, and
The requirement that tetration be holomorphic on all of is essential for uniqueness. If one relaxes holomorphicity, there are infinitely many real‐analytic “solutions” obtained by pre‐ or post‐composing with almost‐periodic perturbations. For example, for any fast‐decaying real sequences and, one can set
which still satisfies and, but has additional singularities creeping in from the imaginary direction.

function ComplexTetration:
# 1) Find attracting fixed point alpha of w ↦ b^w
α ← the unique solution of α = b^α near the real line
# 2) Compute multiplier s = b^α · ln
s ← b**α * log
# 3) Solve Schröder’s equation coefficients around α:
# Φ_b = ∑_^∞ a_n · ^n, Φ_b = s · Φ_b
← SolveLinearSystemSchroeder
# 4) Define inverse φ_b⁻¹ via the local power series around 0
φ_inv = α + ∑_^∞ c_n · u^n #
# 5) Put F_b = φ_b⁻¹ · Φ_b)
return φ_inv * ∑_^∞ a_n ·

Ordinal tetration

Tetration can be defined for ordinal numbers via transfinite induction. For all and all :

Non-elementary recursiveness

Tetration is not an elementary recursive function. One can prove by induction that for every elementary recursive function, there is a constant such that
We denote the right hand side by. Suppose on the contrary that tetration is elementary recursive. is also elementary recursive. By the above inequality, there is a constant such that. By letting, we have that, 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 ; e.g., in the function, the two inverses are the cube super-root of and the super-logarithm base of.

Super-root

The super-root is the inverse operation of tetration with respect to the base: if, then is an th super-root of .
For example,
so 2 is the 4th super-root of 65,536.

Square super-root

The 2nd-order super-root, square super-root, or super square root has two equivalent notations, and. It is the inverse of and can be represented with the Lambert W function:
The function also illustrates the reflective nature of the root and logarithm functions as the equation [|below] only holds true when :
Like square roots, the square super-root of may not have a single solution. Unlike square roots, determining the number of square super-roots of may be difficult. In general, if, then has two positive square super-roots between 0 and 1 calculated using formulas:; and if, then has one positive square super-root greater than 1 calculated using formulas:. If is positive and less than it does not have any real square super-roots, but the formula given above yields countably infinitely many complex ones for any finite not equal to 1. The function has been used to determine the size of data clusters.
At :

Other super-roots

One of the simpler and faster formulas for a third-degree super-root is the recursive formula. If then one can use:
This recursive formula makes use of the explicit representation of the square super-root via the Lambert W function given above, as we can represent in the form of and apply the square super-root twice:.
For each integer, the function is defined and increasing for, and, so that the th super-root of,, exists for.
However, if the linear approximation above is used, then if, so cannot exist.
In the same way as the square super-root, terminology for other super-roots can be based on the normal roots: "cube super-roots" can be expressed as ; the "4th super-root" can be expressed as ; and the "th super-root" is. Note that may not be uniquely defined, because there may be more than one root. For example, has a single super-root if is odd, and up to two if is even.
Just as with the extension of tetration to infinite heights, the super-root can be extended to, being well-defined if. Note that and thus that. Therefore, when it is well defined, and, unlike normal tetration, is an elementary function. For example,.
It follows from the Gelfond–Schneider theorem that super-root for any positive integer is either integer or transcendental, and is either integer or irrational. It is still an open question whether irrational super-roots are transcendental in the latter case.

Super-logarithm

Once a continuous increasing definition of tetration,, is selected, the corresponding super-logarithm or is defined for all real numbers, and.
The function satisfies:

Open questions

Other than the problems with the extensions of tetration, there are several open questions concerning tetration, particularly when concerning the relations between number systems such as integers and irrational numbers:

It is not known whether there is an integer for which is an integer, because we could not calculate precisely enough the numbers of digits after the decimal points of. It is similar for for, as we are not aware of any other methods besides some direct computation. In fact, since, then. Given and, then for. It is believed that is not an integer for any positive integer, due to the algebraic independence of, given Schanuel's conjecture.
It is not known whether is rational for any positive integer and positive non-integer rational. For example, it is not known whether the positive root of the equation is a rational number.
It is not known whether or are rationals or not.

Applications

For each graph H on h vertices and each, define
Then each graph G on n vertices with at most copies of H can be made H-free by removing at most edges.