Abstract
In this paper we develop a rigidity theorem for algebraic families of rational maps and apply it to the study of iterative root-finding algorithms.
We answer a question of Smale’s by showing there is no generally convergent algorithm for finding the roots of a polynomial of degree $4$ or more. We settle the case of degree $3$ by exhibiting a generally convergent algorithm for cubics; and we give a classification of all such algorithms.
In the context of conformal dynamics, our main result is the following: 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). Our classification of generally convergent algorithms follows easily from this result.
As another consequence of rigidity, we observe that the eigenvalues of a nonaffine rational map at its periodic points determine the map up to finitely many choices. This implies that bounded analytic functions nearly separate points on the moduli space of a rational map.
