Computing the complex roots of a monic polynomial

Question

The map from monic complex polynomials to the unordered tuples of their roots (each appearing according to its multiplicity) is computable. This seems to have been known for a long time, and with modern technology is quick and easy to prove.

What I am interested in is whether there is a canonical reference for this (and if so, whom to credit).

The weaker observation that if the coefficients are computable numbers, then the roots are computable numbers, too, doesn't count here. The uniformity is important.

There is a paper from 2002 proving the result I mentioned (Lester, Chambers, and Lu – A constructive algorithm for finding the exact roots of polynomials with computable real coefficients), but there are older references to the result being well-known. In fact, I vaguely remember having read a pre-LaTeX paper containing a proof — unfortunately, I don't remember where I may have come across it. Weihrauch's Computable Analysis has this as Exercise 6.3.11.

Answer 1

I'm worried that I'm misunderstanding your question, but I think one could argue there is no satisfactory answer here except to say that this result likely predates "computability" itself.

From the wikipedia article on the Fundamental theorem of algebra:

None of the proofs mentioned so far is constructive. It was Weierstrass who raised for the first time, in the middle of the 19th century, the problem of finding a constructive proof of the fundamental theorem of algebra. He presented his solution, which amounts in modern terms to a combination of the Durand–Kerner method with the homotopy continuation principle, in 1891.

Moreover, it's been known since Brouwer and Weyl that the theorem was constructive. Brouwer and deLoor in 1924 showed that the Fundamental Theorem of Algebra was Intuitionistically provable:

• L. E. J. Brouwer and B. deLoor, Intuitionistischer Beweis des Fundamentalsatzes der Algebra, Amsterdam Kon. Akad. van Wetenschappen, Proc., vol. 27, 1924, pp. 186-188

In the same year, Weyl also gave a constructive proof of some sort:

• H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik, Math. Zeit., vol. 20, 1924, pp. 131-150

In that case, it is really just a matter of connecting constructive math with computable math. (Also, constructive math has the advantage that uniformity is built in.) I don't know if there is a clear first mention of a uniformly computable FTA, but here is what I've found.

Rosenbloom gives an alternative elementary constructive proof avoiding the heavy machinery of Brouwer, deLoor and Weyl:

• P. C. Rosenbloom. An Elementary Constructive Proof of the Fundamental Theorem of Algebra. The American Mathematical Monthly, Vol. 52, No. 10 (Dec., 1945), pp. 562-570

In this paper we shall give a method of constructing from a given polynomial $P(z)$ by rational operations a sequence of complex numbers ${z_n}$ which satisfies the Cauchy convergence criterion and such that $P(z_n)$ converges to zero. All of this part of the proof is constructive and completely elementary.

Rice cites Rosenbloom's construction to show that the recursively complex numbers are algebraically closed (but not explicitly mentioning uniformity) in

• H. G. Rice. Recursive real numbers. Proc. Amer. Math. Soc. 5 (1954), 784-791

And I believe, Bishop also has a constructive proof of the FTA in his book. (And I haven't looked at the Russian school of constructive math or Martin-Lof's book on constructive math, but I wouldn't be surprised if both discuss this.) At this point in history, the 1960s, I would say the theorem is basically folklore if there hasn't already been a canonical reference to it yet, since it is one short step away from a lot that is already known. I think all computable analysts understand, at least now if not then, that if something is in Bishop's book, it is (no more than an exercise to check that it is) uniformly computable.

---

Update 1:

Actually, maybe this is the paper you want.

• P. Henrici and I. Gargantini, Uniformly convergent algorithms for the simultaneous approximation of all zeros of a polynomial, in [2], pp. 77–113

where [2] is

• B. Dejon and P. Henrici, Editors, Constructive Aspects of the Fundamental Theorem of Algebra, Proceedings of a symposium at IBM Research Lab, Zürich-Rüschlikon, June 5-7, 1967, Wiley-Interscience, London

I found this mentioned in "A Constructive Proof of the Fundamental Theorem of Algebra without using the Rationals" (Herman Geuvers, Freek Wiedijk, Jan Zwanenburg):

The first constructive proof of FTA (for monic polynomials) is from Weyl, where the winding number is used to simultaneously find all zeros of a (monic) polynomial. A similar but more abstract proof, also using the winding number, occurs in [Bishop and Bridges], where FTA is proved for arbitrary non-constant polynomials. Based on Weyl’s approach, [Henrici and Gargantini] presents an implementation of an algorithm for the simultaneous determination of the zeros of a polynomial.

So maybe the best answer is the first uniform construction is due to Weyl, but Henrici and Gargantini first put it in terms of uniform computability.

---

Update 2:

Actually, maybe this paper is more canonical looking. (Note, I don't actually have access to a lot of these papers, so you should check them yourself.) It is in the same book [2] mentioned above:

• E. Specker, The Fundamental Theorem of Algebra in Recursive Analysis, in [2], pp. 321–329.

Again, more from the the same section of Geuvers-Wiedijk-Zwanenburg:

In [Brouwer and De Loor], Brouwer and De Loor give a constructive proof of FTA for monic polynomials by first proving it for polynomials with rational complex coefficients (which have the advantage that equality is decidable) and then make the transition (viewing a complex number as the limit of a series of rational complex numbers) to general monic polynomials over C. This proof – and also Weyl’s and other FTA proofs – are discussed and compared in [deLoor 1925].

Brouwer [1924] was the first to generalize the constructive FTA proof to arbitrary non-constant polynomials (where we just know some coefficient to be apart from 0). In [Specker] it is shown that, for general non-constant polynomials, there is a continuous map from the coefficients to the set of zeros.

Also, on the Google Books page for Ernst Specker Selecta p 375, I found more description about this paper:

So this looks like exactly the sort of thing you want! (Nonetheless, I still think the pre-Turing works--namely Weyl, Brouwer-deLoor, and Brouwer--likely deserve the most credit, unless I'm mistaken on the uniformity of those constructions.)