**Tetration**, also known as **hyper4**, **superpower**, **superexponentiation**, **superdegree**, **powerlog**, or **power tower**,^{[1]} is a binary mathematical operator defined as \(^yx = x^{x^{x^{.^{.^.}}}}\) with \(y\) copies of \(x\). In other words, tetration is repeated exponentiation. Formally, this is

\[^0x=1\]

\[^{n + 1}x = x^{^nx}\]

where \(n\) is a nonnegative integer.

Tetration is the fourth hyper operator, and the first hyper operator not appearing in mainstream mathematics. When repeated, it is called pentation.

If \(c\) is a non-trivial constant, the function \(a(n) = {}^nc\) grows at a similar rate to \(f_3(n)\) in FGH.

Daniel Geisler has created a website, tetration.org, dedicated to the operator and its properties.

## Basis Edit

Addition is defined as repeated counting:

\[x + y = x + \underbrace{1 + 1 + \ldots + 1 + 1}_y\]

Multiplication is defined as repeated addition:

\[x \times y = \underbrace{x + x + \ldots + x + x}_y\]

Exponentiation is defined as repeated multiplication:

\[x^y = \underbrace{x \times x \times \ldots \times x \times x}_y\]

Analogously, tetration is defined as repeated exponentiation:

\[^yx = \underbrace{x^{x^{x^{.^{.^.}}}}}_y\]

But since exponentiation is not an associative operator (that is, \(a^{b^{c}}\) is generally not equal to \(\left(a^b\right)^c = a^{bc}\)), we can also group the exponentiation from bottom to top, producing what Robert Munafo calls the **hyper _{4} operator**, written \(x_④y\). \(x_④y\) reduces to \(x^{x^{y - 1}}\), which is not as mathematically interesting as the usual tetration. This is equal to \(x \downarrow\downarrow y\) in down-arrow notation.

### Notations Edit

Tetration was independently invented by several people, and due to lack of widespread use it has several notations:

- \(^yx\) is pronounced "to-the-\(y\) \(x\)" or "\(x\) tetrated to \(y\)." The notation is due to Rudy Rucker, and is most often used in situations where none of the higher operators are called for.
- Robert Munafo uses \(x^④y\), the
*hyper4 operator*. - In arrow notation it is \(x \uparrow\uparrow y\), nowadays the most common way to denote tetration.
- In chained arrow notation it is \(x \rightarrow y \rightarrow 2\).
- In array notation it is \(\{x, y, 2\}\) or \(x\ \{2\}\ y\).
^{[2]}- The latter of these also represents tetration in X-Sequence Hyper-Exponential Notation.

- In Hyper-E notation it is E[x]1#y (alternatively x^1#y).
- In plus notation it is \(x ++++ y\).
- In star notation (as used in the Big Psi project) it is \(x *** y\).
^{[3]} - An exponential stack of
*n*2's was written as E*(n) by David Moews, the man who held Bignum Bakeoff. - Harvey Friedman uses \(x^{[y]}\).

## Properties Edit

Tetration lacks many of the symmetrical properties of the lower hyper-operators, so it is difficult to manipulate algebraically. However, it does have a few noteworthy properties of its own.

### Power identity Edit

It is possible to show that \({^ba}^{^ca} = {^{c + 1}a}^{^{b - 1}a}\):

\[{^ba}^{^ca} = (a^{^{b - 1}a})^{(^ca)} = a^{^{b - 1}a \cdot {}^ca} = a^{^ca \cdot {}^{b - 1}a} = (a^{^ca})^{^{b - 1}a} = {^{c + 1}a}^{^{b - 1}a}\]

For example, \({^42}^{^22} = {^32}^{^32} = 2^{64}\).

### Moduli of power towers Edit

The last digits of \(^yx\) converge as \(y \rightarrow \infty\). In other words, given a large enough power tower, it is easy to find its last digits^{[4]}. The last \(d\) digits of \(^yx\) in base \(b\) is defined by the following recursive formula:

- \(N(0) = x\)
- \(N(d + 1) = x^{N(d)} \mod{b^d}\)

The exponentiation can be computed very quickly using modular exponentiation tricks.

### First digits Edit

Computing the first digits of \(^yx\) in a reasonable amount of time is probably impossible. In base 10:

\[a^b = 10^{b \log_{10} a} = 10^{\text{frac}(b \log_{10} a) + \lfloor b \log_{10} a \rfloor} = 10^{\text{frac}(b \log_{10} a)} \times 10^{\lfloor b \log_{10} a \rfloor}\]

The leading digits of \(^ba\) are then \(10^{\text{frac}(^{b - 1}a \log_{10} a)}\), so the problem is finding the fractional part of \(^{b - 1}a \log_{10} a\). This is equivalent to finding arbitrary base-\(a\) digits of \(^{b - 2}a\) starting at the \(^{b - 2}a\)th place. The most efficient known way to do this is a BBP algorithm, which, unfortunately, requires linear time to operate and works only with radixes that are powers of 2. We need an algorithm at least as efficient as \(O(\log^*n)\) (where \(\log^*n\) is the iterated logarithm), and it is unlikely that one exists.

This roadblock ripples through the rest of the hyperoperators. Even if we do find a \(O(\log^*n)\) algorithm, it becomes unworkable at the pentational level. A constant time algorithm is needed, and finding such an algorithm would take a miracle.

## GeneralizationEdit

### For non-integral \(y\)Edit

Mathematicians have not agreed on the function's behavior on \(^yx\) where \(y\) is not an integer. In fact, the problem breaks down into a more general issue of the meaning of \(f^t(x)\) for non-integral \(t\). For example, if \(f(x) := x!\), what is \(f^{2.5}(x)\)? Stephen Wolfram was very interested in the problem of continuous tetration because it may reveal the general case of "continuizing" discrete systems.

Daniel Geisler describes a method for defining \(f^t(x)\) for complex \(t\) where \(f\) is a holomorphic function over \(\mathbb{C}\) using Taylor series. This gives a definition of complex tetration that he calls *hyperbolic tetration*.

### As \(y \rightarrow \infty\)Edit

One function of note is **infinite tetration**, defined as

\[^\infty x = \lim_{n\rightarrow\infty}{}^nx\]

If we mark the points on the complex plane at which \(^\infty x\) becomes periodic (as opposed to escaping to infinity), we get an interesting fractal. Daniel Geisler studied this shape extensively, giving names to identifiable features.

## ExamplesEdit

Here are some small examples of tetration in action:

- \(^22 = 2^2 = 4\)
- \(^32 = 2^{2^2} = 2^4 = 16\)
- \(^23 = 3^3 = 27\)
- \(^33 = 3^{3^3} = 3^{27} =\) Template:Mathlink
- \(^42 = 2^{2^{2^2}} = 2^{2^4} = 2^{16} = 65,536\)
- \(^35 = 5^{5^5} \approx 1.9110125979 \cdot 10^{2,184}\)
- \(^52 \approx 2.00352993041 \cdot 10^{19,728}\)
- \(^310 = 10^{10^{10}} = 10^{10,000,000,000}\)
- \(^43 \approx 10^{10^{10^{1.11}}}\)

When given a negative or non-integer base, irrational and complex numbers can occur:

- \(^2{-2} = (-2)^{(-2)} = \frac{1}{(-2)^2} = \frac{1}{4}\)
- \(^3{-2} = (-2)^{(-2)^{(-2)}} = (-2)^{1/4} = \frac{1 + i}{\sqrt[4]{2}}\)
- \(^2(1/2) = (1/2)^{(1/2)} = \sqrt{1/2} = \frac{\sqrt2}{2}\)
- \(^3(1/2) = (1/2)^{(1/2)^{(1/2)}} = (1/2)^{\sqrt{2}/2}\)

Functions whose growth rates are on the level of tetration include:

- The Catalan-Mersenne sequence
- The size of power sets in the von Neumann universe as a function of stage
^{[5]} - \(f_3\) in the fast-growing hierarchy

## PseudocodeEdit

Below is an example of pseudocode for tetration.

functiontetration(a,b):result:= 1repeatbtimes:result:=ato the power ofresultreturnresult

## SourcesEdit

- ↑ Robert Munafo, Beyond Exponents: the hyper4 Operator.
*Large Numbers*. - ↑ Exploding Array Function
- ↑ bigΨ §2.0.1. Star spangled superpowers
- ↑ Template:Citation/CS1
- ↑ Von Neumann universe.
*Complex Projective 4-Space*.