Families of rational maps and iterative root-finding algorithms (Q1096744)

This paper develops a rigidity theorem for algebraic families of rational maps with application to the theory of iterative root-finding algorithms. It answers a question of Smale by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree 4 or more, and settles the case of degree 3 by exhibiting the first known generally convergent algorithm for cubics. (Such an algorithm assigns to each polynomial p a rational map \(T_ p(z)\), depending algebraicly on p, such that under iteration \(T^ n_ p(z)\) tends to a root of p for almost all p and z.) In the context of conformal dynamics, the main result is: a stable algebraic family of rational maps is either trivial (all its members are conjugate by Möbius transformations) or affine (its members are obtained as quotients of iterated addition on a family of complex tori.) The classification of generally convergent algorithms follows easily from this result. Another consequence of this rigidity result: the multipliers of a nonaffine rational map along its periodic cycles determine the map up to finite many choices. The techniques of proof include the theory of holomorphic motions (à la Mañe-Sad-Sullivan), elementary algebraic geometry, and Thurston's uniqueness result for critically finite rational maps.