Tetration:Combinatorics

From Tetration.net

Contents

Combinatorics - Extending Tetration

Faa Di Bruno's Formula

In order to address the difficulties posed by dynamics ew will employ combinatorics to derive the Taylor series of an arbitrary iterated function.

Consider an exponential generating function f(z)=\sum_{n=0}^{\infty} \frac{D^nf(f_0)}{n!} (z-f_0)^n where the coefficient f0 is a fixed point for the function f(z); thus f(f0) = f0. Define a coefficient f_k \equiv D^k f(z)|_{z=f_0} giving the sequence {f0,f1,...,f∞}.

Consider the complex dynamics of a holomorphic function f(z): \mathbb{C}\ \rightarrow \mathbb{C}\ \, and its iterates f^t(z), t \in \mathbb{N}\ \,.

We invoke the standard convention of using a coordinate translation to set a fixed point at zero, f(0)\equiv 0\,.

Thus f(z)=\sum_{n=1}^{\infty} \frac{f_n}{n!} z^n\, for 0\leq |z|<R\, for some positve R\,. Note that f(z)\, is the exponential generating function of the sequence f_0, f_1, \ldots ,f_\infty\, where f_0=0\,.

D^nf(g(z))=\sum \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}

Faa Di Bruno's Formula for Iterated Functions

D^n f^t(z)=\sum \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}

Faa Di Bruno's Formula for Iterated Functions with a Fixed Point at f0

D^n f^t(f_0)=\sum \frac{(D^k f)(f_0) n!}{k_1! \cdots k_n!} \left(\frac{Df^{t-1}(f_0)}{1!}\right)^{k_1} \cdots \left(\frac{D^n f^{t-1}(f_0)}{n!}\right)^{k_n} + (D f)(f_0) D^n f^{t-1}(f_0)


D^n f^t(f_0)=\sum \frac{f_k n!}{k_1! \cdots k_n!} \left(\frac{Df^{t-1}(f_0)}{1!}\right)^{k_1} \cdots \left(\frac{D^n f^{t-1}(f_0)}{n!}\right)^{k_n} + f_1 D^n f^{t-1}(f_0)

The proceeding equation is a generalized form of the equation I used for my first extension of tetration in 1986 and I suspect that it may also be generalized form of the equation used in Ioannis' definition of {}^n(e^x)\,.

The First Derivative

\begin{matrix} Df(g(z))&=&f'(g(z))g'(z) \\ Df^t(z) &=&f'(f^{t-1}(z))Df^{t-1}(z) \\ &=&\prod^{t-1}_{k_1=0}f'(f^{t-k_1-1}(z)) \\ \end{matrix}


\begin{matrix} Df^t(0) &=&f'(f_0)^t \\ &=&f_1^t \end{matrix}

The Second Derivative

The second derivative is found by using Bell polynomials, as in Aldrovandi and Freitas \cite{Aldrovandi}. Here a specific class of the Bell polynomials is investigated where D^mf(g(z))=D^mf(f^{t-1}(z))\,.


\begin{matrix} 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)\\ \\ D^2f^t(f_0)&=&f_2f_1^{2t-2}+f_1D^2f^{t-1}(f_0) \end{matrix}


When f_1\neq0\, , a recurrence equation is formed that is easily solved as a summation.

\begin{matrix} D^2f^t(f_0)&=&f_2f_1^{2t-2}+f_1D^2f^{t-1}(f_0) \\ &=&f_1^0f_2f_1^{2t-2} \\ &&+f_1^1f_2f_1^{2t-4} \\ &&+\cdots \\ &&+f_1^{t-2}f_2 f_1^2 \\ &&+f_1^{t-1}f_2 f_1^0 \\ && \\ &=&f_2\sum_{k_1=0}^{t-1}f_1^{2t-k_1-2} \end{matrix}

The index ki is used differently from the index ji used in Equation \ref{FaaDiBruno}. The index ji is associated with partitions containing i items while ki is associated with the ith nested summation.

The Third Derivative

Continuing on with the third derivative, \begin{matrix} D^3f(g(z))&=&f'''(g(z))g'(z)^3+3f''(g(z))g'(z)g''(z)+f'(g(z))g'''(z)\\ &=&f'''(f^{n-1}(z))(Df^{n-1}(z))^3\\ &&+3f''(f^{n-1}(z))Df^{n-1}(z)D^2f^{n-1}(z)\\ &&+f'(f^{n-1}(z))D^3f^{n-1}(z)\\ \\ D^3f^n(f_0)&=&f_3f_1^{3n-3}+f_2^2\sum_{k_1=0}^{n-1}f_1^{3n-k_1-5} +D^3f^{n-1}(f_0)\\ &=&f_3\sum_{k_1=0}^{n-1}f_1^{3n-2k_1-3}\\ &&+3f_2^2 \sum_{k_1=0}^{n-1} \sum_{k_2=0}^{n-k_1-2} f_1^{3n-2k_1-k_2-5} \end{matrix}

Note that the index k1 from the second derivative is renamed k2 in the final summation of the third derivative. A certain amount of renumbering is unavoidable in order to use a simple index scheme. Concrete Mathematics is recommended for its treatment of the products of summations.

Continuous Iteration

Note that some function F(\chi)\, can always be constructed so that D^kf^n(f_0)= F(f_0,\ldots,f_k;D^0f^n(f_0),\ldots,D^{k-1}f^n(f_0)) + D^kf^{n-1}(f_0)\,.

More suscintly D^kf^n(f_0)= F(\chi) + D^kf^{n-1}(f_0)\,, which means that D^kf^n(f_0)\, can be solved by solving the simple difference equation that generates a geometrical progression.

The Taylor Series of an Iterated Function

Assembling the results from the previous section allows us to compute the first few terms of the Taylor series of an arbitrary iterated function.

f^{\,t}(z)=f_0 +f_1^t (z-f_0) + \frac{1}{2!}(f_2 \sum_{k_1=0}^{t-1}f_1^{2t-k_1-2}) (z-f_0)^2 + \frac{1}{3!}( f_3\sum_{k_1=0}^{n-1}f_1^{3n-2k_1-3} +3f_2^2 \sum_{k_1=0}^{n-1} \sum_{k_2=0}^{n-k_1-2} f_1^{3n-2k_1-k_2-5}) (z-f_0)^3 + \ldots

where t \in \mathbb{Z}\. Consider the classic formula for the sum of a geometric progression \sum_{k=0}^{n-1} f_1^k = \frac{1-f_1^n}{1-f_1}. The formula works as long as |f_1|^k \ne 1 \, for some k \in \mathbb{Z}^+. Note that if |f_1|^k \ne 1 \, then the range of n in \sum_{k=0}^{n-1} f_1^k is n \in \mathbb{Z}^+, but that the range of n can be extended to n \in \mathbb{C} without loose of consistency in \frac{1-f_1^n}{1-f_1}.

This leads to an interesting idea. What if t \in \mathbb{Z}\ for f^{\,t}(z) in the abstract, but that when each of the specific cases of f^{\,t}(z) is considered, that t \in \mathbb{C}\? Then the function under consideration would be linearized in different way for each of the specific cases, but it would always be linearized in some manner. Every map would ultimately be a flow.

Just as it can be asked whether tetration may be extended, it could just as easily be asked can as to whether it is possible to prevent tetration from being extended. In order words, could the nonexistence of is complex tetration be used to prove the nonexistence of tetration with whole numbers?

I argue that it was never an issue of "extending" tetration to the real and the complex numbers, but that the basic definition of tetration implicitly contains complex tetration. The implicit existence of continuous iteration natrurally extends not only tetration to the complex numbers, but it extends the Ackermann function to the complex numbers.

Hyperbolic Continuous Iteration

Hyperbolic continuous iteration is the most common type of continuous iteration. The Schröder equation f(h(x)) = cf(x) has historically been used to derive linearizations for this class of iterated functions.

f^{\,t}(z)=f_0 +f_1^t (z-f_0) + \frac{1}{2!} f_2 \frac{{{f_1}}^{-1 + n}\, (-1 + {{f_1}}^n) } {-1 + {f_1}} (z-f_0)^2 + \frac{1}{3!} ( f_3 \frac{{{f_1}}^{-2 + n}\, \left( -1 + {{f_1}}^n \right) \, \left( -{f_1} + {{f_1}}^n \right) } {{\left( -1 + {f_1} \right) }^2\, \left( 1 + {f_1} \right) } + 3f_2^2 \frac{{{f_1}}^{-1 + n}\, \left( -1 + {{f_1}}^n \right) \, \left( 1 + {{f_1}}^n \right) }{ \left( -1 + {f_1} \right) \, \left( 1 + {f_1} \right) } ) (z-f_0)^3 + \ldots

Parabolic Continuous Iteration

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

Rationally Neutral Continuous Iteration

Superattracting Continuous Iteration