From Iterated Functions


Tetration is defined as iterated exponentiation but while exponentiation is essential to a large body of mathematics, little is known about tetration due to its chaotic properties. The standard notation for tetration is \(^{1}a=a,   ^{2}a=a^a,  ^{3}a=a^{a^a},\) and so on. Mathematicians have been researching tetration since at least the time of Euler but it is only at the end of the twentieth century that the combination of advances in dynamical systems and access to powerful computers is making real progress possible.

The big question in tetration research is how can tetration be extended to complex numbers. How do you compute numbers like \(^{.5}2\), and \(^{\pi i}e\) ? This web site will show how to compute these and other problems. Two important related concepts to tetration are continuously iterated functions and the Ackermann function.

Continuous iteration of functions[edit]

The study of the iterations of a complex function \(f(z)\) are known as complex dynamics, where \(f^0(z)\equiv z\), \(f^1(z) \equiv f(z)\), \( f^2(z) \equiv f(f(z)), \ldots \). The meaning of \(f^n(z)\), when \( n \in \mathbb{N}\) is clear. It is when \(f(z)\) is viewed in higher dimensional dynamics with \( n \in \mathbb{R}\) or \( n \in \mathbb{C}\) that \(f^n(z)\) as a continuously iterationed functions can represent any possible system in physics. There are two ways in physics to represent arbitrary dynamical systems, as partial differential equations and as a continuously iterationed function. Partial differential equations are known as flows while discretely iterationed functions are known as maps. The continuous iteration of functions is known as Lie groups when the dynamical system is not chaotic.

Consider when \(f(z)\equiv a^z\), then \(f(1)= a^1=a\), \(f^2(1)= a^a=^{2}a\), and \(f^3(1)= a^{a^a}=^{3}a, \ldots\) . Therefore \(f^n(1)= ^{n}a\). So tetration for complex numbers can be easily defined if complex functions can be continuosly iterated, \( n,z \in \mathbb{C}\) for \(f^n(z)\).

The Ackermann function[edit]

The Ackermann function consists of addition, multiplication, exponentiation, tetration, pentation and so on.

Systems of Notation for Arithmetic Operators
Arithmetic Standard Ackermann
Knuth Conway
Addition a+b ack(a,b,0)

Multiplication a*b ack(a,b,1)

Exponentiation ab ack(a,b,2) a↑b a→b→1
Tetration ba ack(a,b,3) a↑↑b a→b→2
Pentation ba ack(a,b,4) a↑↑↑b a→b→3
ack(a,b,5) a↑↑↑↑b a→b→4

... ...

Uniting Two Kinds of Science - The Old and the New[edit]

In 1986 Stephen Wolfram pointed out that the problem of extending tetration to the complex numbers was actually part of the much larger and more important problem of unifying the discreet representation of chaotic systems in mathematics with the continuous representation of chaotic systems in physics, of unifying maps from iterated functions and flows from PDEs. He maintained that the duality prevented the derivation of mathematical solutions for continuous chaotic systems as are found in physics. My understanding of Wolfram’s position is that he was interested in the possibility that there might be a principle at play even deeper than the Principle of Equivalence and that it might be possible to formulate a single mathematical approach to dynamics encompassing iterated functions, cellular automata, PDEs, and recurrence equations. Wolfram suggested at if tetration could be defined for complex numbers then those results might be generalized to unify discrete maps and continuous flows.

How can one extend recursive function definitions to continuous numbers?[edit]

How can one extend recursive function definitions to continuous numbers?
 What is the continuous analog of the Ackermann function? - Stephen Wolfram 

Let \(f(z) \equiv a \rightarrow z \rightarrow k\).

Theorem. When \(f^n(z)\) where \(n \in \mathbb{C}\) is defined, then \( a \rightarrow b \rightarrow k+1 \) where \(a,b \in \mathbb{C}\).

\begin{eqnarray} f(1) &=& a \rightarrow 1 \rightarrow k = a\\ f^2(1) &=& f(a) = a \rightarrow a \rightarrow k = a \rightarrow 2 \rightarrow k+1\\ f^3(1) &=& f(a \rightarrow a \rightarrow k) = a \rightarrow (a \rightarrow a \rightarrow k) \rightarrow k = a \rightarrow 3 \rightarrow k+1\\ f^n(1) &=& a \rightarrow n \rightarrow k+1 \\ \end{eqnarray}

Therefore, when \(f^n(z)\) where \(n \in \mathbb{C}\) is defined, then \( a \rightarrow b \rightarrow k+1 \) where \(a,b \in \mathbb{C}\) is defined.

\( \bullet \)

An Equivalent Problem[edit]

So for tetration and the Ackermann function in general, the problem of extending them to the complex numbers can be simply reduced to the problem of continuous iteration of functions. The problem of continuous iteration of functions is solved by taking the Taylor series \(f^t(z)=\sum_{j=1}^\infty D^j f^t(0) z^j\) .

The Derivatives of Iterated Functions[edit]

Consider the holomorphic function \(f(z): \mathbb{C} \rightarrow \mathbb{C}\) and its iterates \(f^{\;\:t}(z), t \in \mathbb{N}\). The standard convention of using a coordinate translation to set a fixed point at zero is invoked, \(f(0)\equiv 0\), giving \(f(z)=\sum_{n=1}^{\infty} \frac{f_n}{n!} z^n\) for \(0\leq |z|< R\) for some positive \(\mathbb{R}\). Note that \(f(z)\) is the exponential generating function of the sequence \(f_0, f_1, \ldots ,f_\infty\), where \(f_0=0\) and \(f_1\) will be written as \(\lambda\). The expression \(f_j^k\) denotes \((D^j f(z))^k |_{z=0}\) .

Note: The symbol \(t\) for time assumes \(t \in \mathbb{N}\), that time is discrete. This allows the variable $n$ to be used solely in the context of differentiation in this paper. Beginning with the second derivative each component will be expressed in a general form using summations and referred to here as Schroeder summations.

The First Derivative[edit]

The first derivative of a function at its fixed point $Df(0)=f_1$ is often represented by $\lambda$ and referred to as the multiplier or the Lyapunov characteristic number; its logarithm is known as the Lyapunov exponent. Let $g(z)=f^{t-1}(z)$, then \begin{eqnarray*} Df(g(z))&=&f'(g(z))g'(z)\\ &=&f'(f^{t-1}(z))Df^{t-1}(z)\\ &=&\prod^{t-1}_{k_1=0}f'(f^{t-k_1-1}(z))\\ \end{eqnarray*} \begin{eqnarray} Df^t(0)&=&f'(0)^t\nonumber\\ &=&f_1^t = \lambda^t \label{eq:TheFirstDerivative} \end{eqnarray}

The Second Derivative[edit]

\begin{eqnarray*} D^2f(g(z))&=&f''(g(z))g'(z)^2+f'(g(z))g''(z)\\ &=&f''(f^{t-1}(z))(Df^{t-1}(z))^2+f'(f^{t-1}(z))D^2f^{t-1}(z) \end{eqnarray*}

Setting $g(z) = f^{t-1}(z)$ results in \begin{eqnarray} D^2f^t(0)&=& f_2 \lambda^{2t-2}+\lambda D^2f^{t-1}(0)\nonumber \end{eqnarray} When $\lambda \neq 0$, a recurrence equation is formed that is solved as a summation. \begin{eqnarray} D^2f^t(0)&=&f_2\lambda^{2t-2}+\lambda D^2f^{t-1}(0)\nonumber\\ &=&\lambda^0f_2 \lambda^{2t-2}\nonumber\\ &&+\lambda^1f_2 \lambda^{2t-4}\nonumber\\ &&+\cdots\nonumber\\ &&+\lambda^{t-2}f_2 \lambda^2\nonumber\\ &&+\lambda^{t-1}f_2 \lambda^0\nonumber\\ &=&f_2\sum_{k_1=0}^{t-1}\lambda^{2t-k_1-2} \label{eq:TheSecondDerivative} \end{eqnarray}

The Third Derivative[edit]

Continuing on with the third derivative,

\begin{eqnarray} D^3f(g(z))&=&f'''(g(z))g'(z)^3+3f''(g(z))g'(z)g''(z)+f'(g(z))g'''(z)\nonumber\\ &=&f'''(f^{t-1}(z))(Df^{t-1}(z))^3\nonumber\\ &&+3f''(f^{t-1}(z))Df^{t-1}(z)D^2f^{t-1}(z)\nonumber\\ &&+f'(f^{t-1}(z))D^3f^{t-1}(z)\nonumber \end{eqnarray}

\begin{eqnarray} D^3f^t(0)&=&f_3\lambda^{3t-3}+3 f_2^2\sum_{k_1=0}^{t-1}\lambda^{3t-k_1-5} +\lambda D^3f^{t-1}(0) \nonumber\\ &=&f_3\sum_{k_1=0}^{t-1}\lambda^{3t-2k_1-3} +3f_2^2 \sum_{k_1=0}^{t-1} \sum_{k_2=0}^{t-k_1-2} \lambda^{3t-2k_1-k_2-5} \label{eq:TheThirdDerivative} \end{eqnarray}

Note that the index $k_1$ from the second derivative is renamed $k_2$ in the final summation of the third derivative. A certain amount of renumbering is unavoidable in order to use a simple index scheme.

The $n^{th}$ Derivative[edit]

Let $f(z)$ and $g(z)$ be holomorphic functions, then the Bell polynomials can be constructed using Faa Di Bruno's formula.

\begin{eqnarray} D^nf(g(z))= \sum_{\pi(n)} \frac{n!}{k_1! \cdots k_n!} (D^kf)(g(z)) \left(\frac{Dg(z)}{1!}\right)^{k_1} \cdots \left(\frac{D^ng(z)}{n!}\right)^{k_n} \end{eqnarray}

A partition of $n$ is $\pi(n)$, usually denoted by $1^{k_1}2^{k_2}\cdots n^{k_n}$ with $k_1+2k_2+ \cdots nk_n=k$; where $k_i$ is the number of parts of size $i$. The partition function $p(n)$ is a decategorized version of $\pi(n)$, the function $\pi(n)$ enumerates the integer partitions of $n$, while $p(n)$ is the cardinality of the enumeration of $\pi(n)$.

Setting $g(z) = f^{t-1}(z)$ results in

\begin{eqnarray} D^n f^t(z) = \sum_{\pi(n)} \frac{n!}{k_1! \cdots k_n!} (D^k f)(f^{t-1}(z)) \left(\frac{Df^{t-1}(z)}{1!}\right)^{k_1} \cdots \left(\frac{D^n f^{t-1}(z)}{n!}\right)^{k_n} \end{eqnarray}

The Taylors series of $f^t(z)$ is derived by evaluating the derivatives of the iterated function at a fixed point $f^t(0)$ by setting $z=0$ and separating out the $k_n$ term of the summation that is dependent on $D^n f^{t-1}(0)$.

\begin{eqnarray} D^n f^t(0) = \sum \frac{n!(D^k f)(0)}{k_1! \cdots k_{n-1}!} \left(\frac{Df^{t-1}(0)}{1!}\right)^{k_1} \cdots \left(\frac{D^n f^{t-1}(0)}{(n-1)!}\right)^{k_{n-1}} + (D f)(0) D^n f^{t-1}(0) \end{eqnarray}

The remaining $p(n)-1$ terms of the summation are only dependent on $D^k f^{t-1}(0)$, where \(0 < k < n\).

Iterated Functions[edit]

Functional Equations[edit]

Schroeder's and Abel's equations are often used to derive fractionally iterated functions.

Putting the pieces together and setting the fixed point at \(f_0\) gives,

\begin{eqnarray} f^t(z)&=&\sum_{j=0}^\infty D^j f^t(0) z^j \\ &=&f_0+\lambda^t (z-f_0)+( f_2\sum_{k_1=0}^{t-1}\lambda^{2t-k_1-2}) (z-f_0)^2+ (f_3\sum_{k_1=0}^{t-1}\lambda^{3t-2k_1-3} +3f_2^2 \sum_{k_1=0}^{t-1} \sum_{k_2=0}^{t-k_1-2} \lambda^{3t-2k_1-k_2-5}) (z-f_0)^3+ \ldots \end{eqnarray}

So far we have covered a decent amount of algebra, but still \(t \in \mathbb{N}\). The equation \(f^t(z)\), \(t \in \mathbb{N}\) is important because it is convergent when \(f(z)\) is convergent. A number of different attempts have been made to extend tetration to complex numbers, but have failed because they couldn't show convergence.

Hyperbolic Fixed Points

When \(\lambda\) is neither zero nor a root of unity \(\lambda^t \neq 1, t \in \mathbb{N}\), then the nested summations simplify to

\begin{eqnarray} f^t(z)=f_0 &+& \lambda ^t (z-f_0)+\frac{\lambda ^{-1+t} \left(-1+\lambda ^t\right) f_2}{2 (-1+\lambda )} (z-f_0)^2 \\ & + & \frac{1}{6} \left(\frac{3 \lambda ^{-2+t} \left(-1+\lambda ^t\right) \left(-\lambda +\lambda ^t\right) f_2^2}{(-1+\lambda )^2 (1+\lambda )}+\frac{\lambda ^{-1+t} \left(-1+\lambda ^{2 t}\right) f_3}{-1+\lambda ^2}\right) (z-f_0)^3+\ldots \end{eqnarray}

Hyperbolic Tetration[edit]

Let \(a_0\) be a limit point for \(f(z)=a^z\), so that \(a^{a_0}=a_0\). Also \(a_1=\lambda\). This results in a definition for tetration of complex points for all except the set of points with rationally neutral fixed points. For the real numbers \(a=e^{e^{-1}}\approx 1.44467, a=e^{-e}\approx 0.065988 \) have rationally neutral fixed points while \(a=1\) is a superattractor. All other real values of \(a\) are defined by hyperbolic tetration.

\begin{eqnarray} {}^t a = a_o & + & \lambda ^t\left(1-a_o\right)+\frac{\lambda ^{-1+t} \left(-1+\lambda ^t\right) \text{Log}\left(a_o\right){}^2}{2 (-1+\lambda )}\left(1-a_o\right){}^2 \\ & + &\frac{1}{6}\text{ }\left(\frac{3 \lambda ^{-2+t} \left(-1+\lambda ^t\right) \left(-\lambda +\lambda ^t\right)\text{ }\text{Log}\left(a_o\right){}^4}{(-1+\lambda )^2 (1+\lambda )}+\frac{\lambda ^{-1+t} \left(-1+\lambda ^t\right) \left(1+\lambda ^t\right)\text{ }\text{Log}\left(a_o\right){}^3}{(-1+\lambda ) (1+\lambda )}\right)\left(1-a_o\right){}^3+\ldots \end{eqnarray}

An Example of Hyperbolic Tetration[edit]

Consider a question posed at the begining of this article: what is \({}^{.5}2\). The function \(f(z)=2^z\) has an infinite number of fixed points that are nearly periodic, including fixed points at \(a_0=0.824679+1.56743 i\), \(a_0=3.51524 + 10.8801 i\), and \(a_0=4.36143 + 20.0872 i\). The fractal below is the Julia set of the function \(f(z)=2^z\) .

<a href="../julia2.gif" title="Julia set for 2^z"><img src="../julia2.gif" alt="Julia for 2^z" width="512" height="384" ></a>

For limit point \(a_0=0.824679+1.56743 i, {}^{.5}2=1.824-0.745596 i\), for limit point \(a_0=3.51524 + 10.8801 i, {}^{.5}2=-171.818+199.332 i\), and for limit point \(a_0=4.36143 + 20.0872 i, {}^{.5}2=-1178.18+1829.92 i\). Therefore \({}^{.5}2=\{\ldots,1.824-0.745596 i,-171.818+199.332 i,-1178.18+1829.92 i,\ldots\}\).

Parabolic Neutral Fixed Points[edit]

\[f^t(z)=z+\frac{1}{2}t f_2 (z-f_0)^2 +\frac{1}{12}(3(t^2-t)f_2^2+2tf_3)(z-f_0)^3+\ldots\]

Parabolic Tetration