Complexity of constructing the roots of a polynomial in the field of multiple formal fractional power series in zero characteristic

A. L. Chistov

St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences

Abstract: By a change of variables we reduce the problem of constructing the roots of a polynomial in the field of multiple formal fractional power series in zero characteristic to constructing the roots of another polynomial in the ring of multivariables formal power series. The efficient estimates for this change of variables are obtained. To achieve this aim we suggest a new refined version of the result on the complexity of the Newton–Puiseux algorithm. After that one can apply the algorithm for factoring polynomials over the ring multivariables formal power series constructed by the author earlier with efficient estimates for the working time.

Key words and phrases: formal fractional power series, formal power series, factoring polynomials, many variables, complexity of the algorithms.

UDC: 513.6, 518.5