Subject: Re: [HM] Roots of polynomials
From: William Tait (wwtx@midway.uchicago.edu)
Date: Thu Apr 27 2000 - 23:32:15 EDT
Mic Detlefsen asked
> Is there a (possibly quite complicated) law that someone has stated
> to determine the number of REAL roots of polynomials with real
> coefficients? If so, where could I find a statement of it? What is
> its earliest appearance. I've been reading quite a lot of 17th-19th
> century algebra books the past many months, and I don't recall having
> ever seen such a law stated. (I know, of course, that no general
> decision procedures for quintic equations can be given, but my
> question is, it seems to me, independent of this. I am asking not
> for an algorithm for finding all the particular real roots of an
> equation, but rather a (possibly non-constructive) law for determining
> the number of such.)
John Conway and William Waterhouse answer the question of the
existence of a method for determining the number of roots (in an
interval) by reference to Sturm's Theorem. John Conway answers the
remark about the existence of an algorithm for effectively
determining the number of roots as follows:
> Sturm's theorem is very constructive. It burst like a bombshell
> on the 19th century algebraists, none of whom expected such a result
> to exist.
But, in fact, the question of how many roots an arbitrary equation of
degree 1 has (remembering that Mic is asking about polynomials with
*real* coefficients) is precisely the question of whether an
arbitrary real number is = 0, for which there is no algorithm.
Of course, for equations with rational coefficients, Sturm's Theorem
does yield an algorithm both for determining both the number of roots
in a real interval and for constructing all the real roots. This is
interesting historically for at least the following reason: It has
often been said that Cantor's proof that every interval contains
transcendental numbers is non-constructive. His proof has two parts.
The first, using a nested interval construction, shows that there is
a real that is not in the range of a given *non-repeating*
enumeration of reals. The second is his proof that there is a
non-repeating enumeration of the algebraic numbers. His proof of the
first part is not constructive, but can easily be constructivized
(without departing from the idea of his proof). The second part
consisted in constructing an enumeration, with repetitions, of the
algebraic numbers and then taking the non-constructive step of
eliminating repetitions. But with Sturm's Theorem (unknown of course
to Cantor), this last step can also be constructivized.
Bill Tait
William W. Tait
Professor Emeritus of Philosophy
University of Chicago
wwtx@midway.uchicago.edu
Home:
5522 S. Everett Ave
Chicago, IL 60637
(773) 241-7288
This archive was generated by hypermail 2b28 : Fri Apr 28 2000 - 00:26:21 EDT