Inverting Polynomials and Formal Power Series

The problem of inverting a general polynomial of degree $d > 0$, the inverse being a formal power series with coefficients $z_0 ,z_1 ,z_2 , \ldots $ is considered. It is shown that computing $z_0 , \ldots ,z_n $ can be carried out in $n + (2d - 1)\lceil {\log _2 n} \rceil + 2$ nonscalar operations over any infinite field. A lower bound of $n + 1$ for all fields follows from standard linear-independence arguments. (The model of computation consists of straight-line algorithms.)

For fields of characteristic 0, it is also shown that computing $z_{n + 1} , \ldots ,z_{n + s} $ for $n \geqslant 0$, $s \geqslant 1$, requires at least $s + \min {{(n + 1,d)} / {2 - 1}}$ nonscalar operations. For the case of inverting a general formal power series a corresponding lower bound of $s + {{(n + 1)} / {2 - 1}}$ exists. In particular, computing the nth coefficient of the inverse of a general formal power series requires at least ${n / 2}$ nonscalar operations (the coefficients are numbered from zero).