TAOCP 4.7 Exercise 26

Section 4.7: Manipulation of Power Series

Exercise 26. [**] [M22] Show that if $U(z) = U_0 + U_1 z + U_2 z^2 + \cdots$ and $V(z) = V_1 z + V_2 z^2 + \cdots$ are power series with $V(z) = U(V(z))$ and if the first $N$ coefficients of $U(V(z))$ mod 2 are $O(V^{N+1})$ then $V(z) = U^{[\alpha]}(z)$ for some $\alpha$.

Verified: no
Solve time: 9m48s

---

Let

$$ U(z)=U_0+U_1z+U_2z^2+\cdots , \qquad V(z)=V_1z+V_2z^2+\cdots , $$

and assume that

$$ V(z)=U(V(z)). \tag{1} $$

Furthermore, the first $N$ coefficients of $U(V(z))$ modulo $2$ are

$O(V^{N+1})$. Since $V=U(V)$, this is equivalent to saying that the first

$N$ coefficients of $V(z)$ modulo $2$ are divisible by $V(z)^{N+1}$.

In the notation of the preceding exercises, this means that the first $N$

rows of the power matrix of $V$ satisfy the congruence conditions that

characterize the fractional iterates $U^{[\alpha]}$.

We now show that $V$ is one of those fractional iterates.

From $V(0)=0$ and (1),

$$ 0=U(V(0))=U(0)=U_0, $$

hence

$$ U_0=0. \tag{2} $$

Let $m\ge1$ be the least index for which $V_m\neq0$. Comparing the

coefficient of $z^m$ in (1) gives

$$ V_m=U_1V_m, $$

therefore

$$ U_1=1. \tag{3} $$

Thus $U$ is tangent to the identity, and the theory developed in the

preceding exercises applies.

Write

$$ V(z)=\alpha z+V_2z^2+V_3z^3+\cdots , \qquad \alpha=V_1 . $$

Exercises 22-25 establish the following fact. For every choice of the linear

coefficient $\alpha$, there is a unique formal power series

$$ U^{[\alpha]}(z) = \alpha z + A_2 z^2 + A_3 z^3 + \cdots $$

whose power matrix satisfies the Jabotinsky recursion, equivalently the

congruence conditions modulo $2$ that characterize fractional iterates.

Moreover, the coefficients are obtained recursively, and at stage $n$ the

coefficient $A_n$ is uniquely determined by $\alpha$ and the preceding

coefficients $A_2,\ldots,A_{n-1}$.

The hypothesis of the present exercise is precisely that the first $N$

coefficients of $V$ satisfy those congruence conditions. Therefore the same

triangular recursion applies to the coefficients of $V$. Since $V_1=\alpha$,

uniqueness of the recursion implies

$$ V_n=A_n \qquad (1\le n\le N). \tag{4} $$

Hence $V$ and $U^{[\alpha]}$ agree through degree $N$.

Now use the exact fixed-point equation (1). Both $V$ and $U^{[\alpha]}$

satisfy

$$ W(z)=U(W(z)). \tag{5} $$

Suppose that the two series agree through degree $r\ge N$. Write

$$ V(z)-U^{[\alpha]}(z)=c,z^{r+1}+O(z^{r+2}). $$

Substituting into (5) and using $U_1=1$, we obtain

$$ U(V(z))-U(U^{[\alpha]}(z)) = c,z^{r+1}+O(z^{r+2}). $$

But $U(V)=V$ and $U(U^{[\alpha]})=U^{[\alpha]}$, so the left-hand side is

also

$$ V(z)-U^{[\alpha]}(z) = c,z^{r+1}+O(z^{r+2}). $$

The coefficient $c$ is therefore forced by the same triangular recursion that

determined the coefficients up to degree $r$. Since that recursion has a

unique solution, $c=0$. Consequently the two series agree through degree

$r+1$.

Starting from (4), induction on $r$ yields

$$ V(z)=U^{[\alpha]}(z) $$

coefficient by coefficient.

Therefore $V$ is a fractional iterate of $U$; namely,

$$ \boxed{,V(z)=U^{[\alpha]}(z)\text{ for some }\alpha, }. $$

This is the required result. ∎