# Series of iterates of a power series

Let $f = \sum_{n \ge 2} a_{n} x^{n}$ be a formal power series of order higher/equal two. By $$f^{\circ n} := \underbrace{f \circ \dots \circ f}_{\text{ n times}}$$ we denote the $n^{th}$ iterate of $f$ and set $$f^{0} = x.$$ It is easily seen that the order of $f^{\circ n}$ is higher/equal $2^{n}$, so we may define the formal series $$S(z):= \sum_{n\ge 0} f^{\circ n}.$$ If we assume that $f$ is a convergent power series, it is also not hard to show that $\sum_{n = 0}^{N} f^{\circ n}$ converges locally uniformly to $S$, especially $S$ is again a convergent power series. Note however that $S \neq (x + f)^{ \circ -1}$ - it is in general not the composite inverse of (x+f).

I don't have a particular reason for studying this series, but it seems to be interesting to ask - what is $S$?. In the sense that whether $S$ relates to $f$ in any "familiar" way, i.e. is the value of some better known operator evaluated at $f$ or does it have any interesting properties? Maye someone already had a thought on it,thanks for all answers.

EDIT: Here is the proof the $S(z)$ is analytic if $f$ is of order $\ge 2$ and convergent: Since $f(0)=0$ you can find a neighborhood in which the modulus of $f$ is strictly smaller then one, so there exist $R>0$ and $M \in (0,1)$ so that $$\vert a_{n} \vert \le \frac{M}{R^{n}}.$$ And you obtain $$\vert f(x) \vert \le \vert \frac{x}{R} \vert ^{2} \frac{ M}{1 - \vert \frac{x}{R}\vert }$$

Since $0<M<1$ there is an $s>0$ so that $\frac{ M}{1 - \vert \frac{x}{R}\vert } \le 2$ for all $x \in D_{s}:= \{ \vert x \vert \le s\}$ and we choose $s$ so small that $\vert \frac{s}{R} \vert \le \frac{1}{2}$.

Now I claim that on $D_{s}$ we have $$\vert f^{\circ n }(x) \vert \le \left\vert\frac{x}{R}\right\vert^{n} 2^{n},$$ which is proven by induction:

Let $n=1$. Then $\vert f(x) \vert \le \vert\frac{x}{R} \vert^{2} \frac{ M}{1 - \vert \frac{x}{R}\vert } \le \vert\frac{x}{R} \vert \vert\frac{x}{R} \vert 2 \le \vert\frac{x}{R} \vert$.

Now the step $n\to n+1$:

$$\vert f(f^{\circ n}) \vert \le \vert \frac xR \vert^{2 n} 2^{2n -2} \frac{ M}{1 - \underbrace{\vert (\frac xR^{n}) 2^n\vert}_{\le \vert \frac{x}{R}\vert }} \le \vert \frac{x}{R} \vert^{2 n} 2^{2n -2} \cdot 2 \le 2^{n} \vert \frac{x}{R} \vert^{n+1}$$

• @richard Yes, for e.g. when $f(x) = 2 x$, the finite sums blow up for any $x \neq 0$. On the other hand you might be able to show convergence for polynomials $f$ for which the coefficients have moduli bounded away from 1. Any polynomial may be "renormalized" in such a way as to satisfy this condition. As for general functions, if $f$ is entire, you can renormalize to satisfy the power-series analogue of this condition. – A Blumenthal Apr 18 '13 at 16:57
• @ABlumenthal Note that in the original sum he restricted $n\geq 2$. For, e.g. $f(x)=x^2$, I'm pretty sure this thing converges for $x\in(-1,1)$. – Douglas B. Staple Apr 18 '13 at 17:33
• I have added the proof that $S$ is analytic (under the assumption that $f$ is analytic and of order $\ge 2$). – Sebastian Apr 19 '13 at 10:08
• Have you ever seen the concept of Carleman-matrices? I think it is very helpful for your question. And especially, I've done questions similar like yours (at least I think so...) using the Neumann-series with that Carleman-matrices as argument. "Carleman matrix" and "Neumann series" can be found in wikipedia. – Gottfried Helms Apr 19 '13 at 10:49

## 3 Answers

I've done one example.
Consider the function $f(x)=2 x^2-x^3+1/4 x^4$ The top left segment of the Carlemanmatrix, let's call it $F$ is $$F_{8 \times 8}=\small \begin{bmatrix} 1 & . & . & . & . & . & . & . \\ 0 & 0 & . & . & . & . & . & . \\ 0 & 2 & 0 & . & . & . & . & . \\ 0 & -1 & 0 & 0 & . & . & . & . \\ 0 & 1/4 & 4 & 0 & 0 & . & . & . \\ 0 & 0 & -4 & 0 & 0 & 0 & . & . \\ 0 & 0 & 2 & 8 & 0 & 0 & 0 & . \\ 0 & 0 & -1/2 & -12 & 0 & 0 & 0 & 0 \end{bmatrix}$$ such that the coefficients for $f(x)$ are in the second column (let's define the columnindex $c=1$ and rows and column-indexes always begin at 0) In the next column there are the coefficients for $f(x)^2$ and in the first column that (trivial one) for $f(x)^0 = 1$. (Note: my convention here is the transpose of the example in the wikipedia for some historical reasons)

The coefficients for the h'th iterate of $f(x)$ occur in the second column of the h'th power of $F$.

Then the coefficients for the sum of all iterates occur in the second column of the sum of all powers of $F$. But that means, that we could define the matrix $A$ as result of the geometric series of $F$, which is known as Neumann series and would be computed by $$\sum_{k=0}^\infty F^k = (I - F)^{-1}$$

Unfortunately, the top left element of that geometric series $(I-F)$ is zero, so it is not invertible. But for any finite truncation we can use the submatrix without the first column and row and then this is invertible: $$A = ((I - F)^*)^{-1}$$ The top left segment of $A$ is then $$A=\small \begin{bmatrix} 1 & . & . & . & . & . & . & . \\ 2 & 1 & . & . & . & . & . & . \\ -1 & 0 & 1 & . & . & . & . & . \\ 33/4 & 4 & 0 & 1 & . & . & . & . \\ -8 & -4 & 0 & 0 & 1 & . & . & . \\ -4 & 2 & 8 & 0 & 0 & 1 & . & . \\ 11 & -1/2 & -12 & 0 & 0 & 0 & 1 & . \\ 985/8 & 1025/16 & 9 & 16 & 0 & 0 & 0 & 1 \end{bmatrix}$$ The coefficients in the first column in $A$ allow now to compute the sum of any contiguous segment of the iterates of $f°^h(x)$ just by the function $$g(x_0,x_m) = \sum_{h=0}^{m-1} f°^h(x_0) = \sum_{k=1}^\infty (x_0^k-x_m^k) \cdot A_{k-1,0}$$ where $x_m = f°^m(x_0)$

This is a pretty general scheme and the current example is just to get an intuition. For other polynomials and even power series $f(x)$ one might need some finetuning and exceptions, but I think it is pretty obvious what's going on in general.

[update] I should add, that the current example gives a pretty small range of convergence, and perhaps one should take a better one. We can only use such $x_0$ , where $|f(x_0)|<|x_0|$, and I tried with $x=0.01$ and smaller... [/update]

• Thanks a lot for the input! But I think that $(I-F)$ is invertible - as $(I-F)$ stands for the polynomial $x - f$, which is invertible as its linear term is not zero. – Sebastian Apr 19 '13 at 12:09
• @Sebastian: No, that's not quite correct. The problem is the top-left zero in $I-F$, which -if at all- would reflect something like the inverse of $(x^0-f(x)^0)$ because the first column in a Carleman-matrix is always associated to $f(x)^0$ – Gottfried Helms Apr 19 '13 at 12:17
• Ah sorry, of course, the Carleman matrix of $x - f$ is not $I-F$. – Sebastian Apr 19 '13 at 12:47
• An aspect about the Carleman matrix which I think may be interesting is that it allows you to estimate the modulus of the coeffiecients of the inverse series: Let $f(x) = x + \sum_{n=2}^{\infty}a_{n} x^{n}$ and let $A$ be the Carleman matrix of $f$. Then $A$ is unitarian. Write $A$ as $I - B$, where $B$ is the neggative of the part below the main diagonal of $A$. Since $I-B$ is unitarian, we can compute its inverse by $\sum_{k =0}^{\infty} B^{k}$. Let $A_{n}$ denote the $n\times n$ truncation of $A$. Since $B$ is nilpotent, one has $A_{n} = \sum_{k=0}^{n} B^{k}_{n}$. – Sebastian Apr 21 '13 at 19:47
• I had a similar situation where I dealt with coefficient estimates of some special unitarian infinite dimensional matrix. Using mathematica I was able to guess usable estimates for coefficients of the inverse, since only finite parts of the matrix enter the computation. – Sebastian Apr 21 '13 at 19:52

If $f(z),g(z)$ are the generating functions for combinatorial classes $\mathcal{F},\mathcal{G}$, then the composition $f(g(z))$ is the generating function for the class of objects of $\mathcal{F}$ whose atoms have been replaced with elements of $\mathcal{G}$.

So, for example, if $f(z)=z^2(1-z)^{-1}$ is considered to be the g.f. for rooted trees of depth 1 with at least two leaf nodes, then $f^{\circ n}$ is the g.f. for balanced trees of depth $n$ in which each internal node has at least two child nodes, and $S$ is the g.f. for all such balanced trees, satisfying $S(z) = z + S(f(z))$.

Another interpretation: Let $T_{f}(g) := f \circ g$ denote the right-composition operator associated with $T_{f}$, let $H := id + T_{f}$. Then $H^{-1} = \sum_{n=0}^{\infty} T_{f}^{n}$. Note that $T_{f}^{n}(f) =f^{ \circ (n+1)}$. Thus $$\sum_{k=0}^{\infty} f^{\circ n} = x + H^{-1}(f).$$