## FANDOM

10,619 Pages

Tetration, also known as hyper4, superpower, superexponentiation, superdegree, powerlog, or power tower, is a binary mathematical operator (that is to say, one with just two inputs), 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, IteratedFunctions.com (formerly tetration.org), dedicated to the operator and its properties.

## Basis

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 hyper4 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

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$$.
• 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$$.
• 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

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

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

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. 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

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.

## Generalization

### For non-integral $$y$$

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$$ Tetration by escape. Black points are periodic; other points are colored based on how quickly they diverge out of a certain radius, (like the Mandelbrot set).

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.

## Examples

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} =$$ $$7,625,597,484,987$$
• $$^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{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:

## Super root

Since ba is perfectly well-defined for non-integer a, we can define a root inverse function as:

$$sr_k(n) = x \text{ such that } ^kx = n$$

### Numerical evaluation

The second-order super root can be calculated as:

$$\frac{ln(x)}{W(ln(x))}$$

where $$W(n)$$ is the Lambert W function.

Formulas for higher-order super roots are unknown.

## Pseudocode

Below is an example of pseudocode for tetration.

function tetration(a, b):
result := 1
repeat b times:
result := a to the power of result
return result


## Sources

1. Robert Munafo, Beyond Exponents: the hyper4 Operator. Large Numbers.
2. Exploding Array Function
3. bigΨ §2.0.1. Star spangled superpowers
4. Ripà, Marco. La strana coda della serie n^n^...^n
5. Von Neumann universe. Complex Projective 4-Space.
6. https://en.wikipedia.org/wiki/Tetration#Super-root