10
$\begingroup$

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}$$

$\endgroup$
  • 1
    $\begingroup$ @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. $\endgroup$ – A Blumenthal Apr 18 '13 at 16:57
  • $\begingroup$ @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)$. $\endgroup$ – Douglas B. Staple Apr 18 '13 at 17:33
  • $\begingroup$ I have added the proof that $S$ is analytic (under the assumption that $f$ is analytic and of order $\ge 2$). $\endgroup$ – Sebastian Apr 19 '13 at 10:08
  • $\begingroup$ 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. $\endgroup$ – Gottfried Helms Apr 19 '13 at 10:49
3
$\begingroup$

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]

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sebastian Apr 19 '13 at 12:09
  • $\begingroup$ @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$ $\endgroup$ – Gottfried Helms Apr 19 '13 at 12:17
  • $\begingroup$ Ah sorry, of course, the Carleman matrix of $x - f$ is not $I-F$. $\endgroup$ – Sebastian Apr 19 '13 at 12:47
  • $\begingroup$ 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}$. $\endgroup$ – Sebastian Apr 21 '13 at 19:47
  • $\begingroup$ 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. $\endgroup$ – Sebastian Apr 21 '13 at 19:52
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.