Googology Wiki
Register
Advertisement
Googology Wiki

Tetration, also known as hyper4, superpower, superexponentiation, superdegree, powerlog, or power tower,[1] 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\).[2]
  • 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

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

The last digits of \(^yx\) for sufficiently large y are given below.

2: ...98,615,075,353,432,948,736

3: ...04,575,627,262,464,195,387

4: ...22,302,555,290,411,728,896

5: ...17,493,152,618,408,203,125

First digits

Computing the first digits of \(^yx\) in a reasonable amount of time for y > 6 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.

Nonetheless, the first digits of \(^yx\) are still computable for small y. Below are some examples.

\(^52\): 200352993040684646497907235156...

\(^62\): 212003872880821198488516469166...

\(^43\): 125801429062749131786039069820...

\(^44\): 236102267145973132068770274977...

\(^35\): 191101259794547752035640455970...

\(^45\): 111102880817999744528617827418...

\(^36\): 265911977215322677968248940438...

\(^46\): 444623519023693469752565822282...

\(^39\): 4281247731757470480369871159...

\(^49\): 214198329479680561133336437344...

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 escape

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[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:

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.[6]

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

See also

Advertisement