On the algebraic complexity of rational iteration procedures (Q811125)

Let \(K={\mathbb{R}}\) or \(K={\mathbb{C}}\) and let k be a subfield of K. A k-rational n-point iteration procedure (I.P.) for \(\alpha\in K\) is a rational function \(f\in k(X_ 0,...,X_{n-1})\setminus k(X_ 0,...,X_{n-1})\) such that for some nonempty neighborhood V of \(\alpha\), if \(x_ 0,...,x_{n-1}\in V\) then the sequence \(x_ i=f(x_{i-n},...,x_{i- 1})\) (i\(\geq n)\) is well-defined and converges to \(\alpha\). The I-step complexity of an iteration procedure is the multiplicative complexity of f as a rational function divided by the logarithm of its order of convergence. The author proves that any multipoint iteration procedure satisfying some technical hypothesis can be replaced by a I- point iteration procedure without increasing the complexity. In the special case of 2-point iteration procedure he considerably weaks his technical hypothesis. (cf. \textit{M. Paterson} [Efficient iterations for algebraic numbers, Complexity of Computer Computations, New York: Plenum Press, 41-52 (1972)].