TAOCP 4.7 Exercise 15
The key point is to identify correctly what equation (27) says in the Brent-Traub discussion.
Section 4.7: Manipulation of Power Series
Exercise 15. [HM30] For what functions $U(z)$ does $U^{[n]}(z)$ have the simple form $z^k$ in (27)? What do you deduce about the answers to exercise 8?
Verified: yes
Solve time: 4m44s
The key point is to identify correctly what equation (27) says in the Brent-Traub discussion.
Let
$$ U(z)=U_1z+U_2z^2+\cdots , $$
and let
$$ U^{[n]}(z)=\underbrace{U\circ U\circ\cdots\circ U}_{n\ \text{times}}(z) $$
denote the $n$-fold iterate. In the development leading to Brent and Traub's method, equation (27) becomes especially simple when the iterates $U^{[n]}(z)$ can be written explicitly as a monomial $z^k$.
We therefore seek all formal power series $U$ for which every iterate remains a monomial.
Suppose
$$ U(z)=a z^m+\text{higher-degree terms}, \qquad a\neq0, $$
and let $m$ be the order of $U$, that is, the least exponent occurring in $U$.
If $U$ contains at least two nonzero terms, write
$$ U(z)=a z^m+b z^r+\cdots , \qquad r>m,\ b\neq0. $$
Then
$$ U(U(z)) =a(U(z))^m+b(U(z))^r+\cdots . $$
Since $U(z)$ itself has at least two nonzero terms, the expansion of $(U(z))^m$ contains at least two distinct powers of $z$:
$$ (U(z))^m =a^m z^{m^2} +m a^{m-1}b, z^{m^2-m+r} +\cdots . $$
Hence $U(U(z))$ already contains at least two nonzero terms. Therefore $U^{[2]}(z)$ cannot be a monomial.
Consequently, if every iterate $U^{[n]}(z)$ is to have the simple form $z^k$, the series $U$ itself must consist of a single monomial:
$$ U(z)=a z^m. $$
Conversely, for such a series,
$$ U^{[n]}(z) =a^{,1+m+\cdots+m^{n-1}} z^{m^n}. $$
Therefore the iterates are monomials for all $n$.
To obtain the exact form $z^k$ occurring in (27), the coefficient must also remain $1$. This forces $a=1$, and we obtain
$$ \boxed{U(z)=z^m \qquad (m\ge1)}. $$
Indeed,
$$ U^{[n]}(z)=z^{m^n}. $$
Thus the only functions whose iterates have the required simple monomial form are the pure monomials $z^m$.
Deduction for Exercise 8
Exercise 8 asked for explicit formulas obtained from the generalized Algorithm L. The present result shows that the only cases in which the iterates appearing in Brent-Traub's method collapse to elementary monomials are the monomial maps
$$ U(z)=z^m. $$
Hence among the answers to Exercise 8, the exceptionally simple closed forms occur precisely in the monomial cases. For these,
$$ U^{[n]}(z)=z^{m^n}, $$
so the iteration process can be written down immediately without carrying out the general Brent-Traub computation.
$$ \boxed{\text{The only such }U\text{ are }U(z)=z^m,\ \text{and then }U^{[n]}(z)=z^{m^n}.} $$
∎