From: greg@math.ucdavis.edu (Greg Kuperberg) Subject: Re: Roots of higher order polynomials Date: 2 Jun 1999 08:35:05 -0700 Newsgroups: sci.math.research Keywords: alternative methods of root-finding In article , Jurek Tyszkiewicz wrote: >It is known that there are no formulas for (complex) zeros of polynomials >of degree higher than 4, in terms of +,*,/,- and roots. > >Do there exist more complicated formulas for these solutions, permitting >substantially more operations? There is a very interesting algorithm due to Doyle and McMullen that solves the quintic by rational iteration on the Riemann sphere. The difference between their algorithm and something much more elementary such as Newton's method is that it converges almost surely. Thus it is as "robust" as extracting roots. A recent archive article by Scott Crass [math.DS/9903111] discusses a possible generalization of the quintic algorithm to sextic polynomials. Solving the sextic this way would require two variables, or more precisely, an algebraic variety on which the alternating group A_6 acts. >More specifically, are the following problems decidable, given three >polynomials p,q,r \in Z[x]: > >1) The roots of p and q of minimal absolute value are equal. > >2) The sum of the roots of p and q of minimal absolute value is equal to >the root of r of minimal absolute value. > >3) The product of the roots of p and q of minimal absolute value is equal >to the root of r of minimal absolute value. This is a horse of a different color. All of them are decidable, are indeed are decided by various computer algebra packagess. It is not hard to guess one approach using elementary lore. You can compute the roots of the polynomials to high accuracy using Newton's method. (It requires some ad hoc plodding at the beginning to find rough values for the roots, but this is certainly still algorithmic.) At the same time, you can derive bounds from number theory involving the coefficients of the polynomials that tell you how close is close enough, i.e., if the entities in the three questions are close enough to equal, then they must be exactly equal. Actually there is a vastly more general result in decidability theory due to Tarski. Any assertion involving equalities or inequalities of fixed algebraic expressions with real variables and quantifiers of those variables ("there exists x" or "for every x") is decidable. Your three questions can be cast in this form. -- /\ Greg Kuperberg (UC Davis) / \ \ / Visit the Math Archive Front at http://front.math.ucdavis.edu/ \/ * All the math that's fit to e-print * ============================================================================== From: jared@abacus.math.uiuc.edu (Jared Bronski) Subject: Re: Roots of higher order polynomials Date: 2 Jun 1999 18:09:53 GMT Newsgroups: sci.math.research Greg Kuperberg wrote: >Jurek Tyszkiewicz wrote: >>It is known that there are no formulas for (complex) zeros of polynomials >>of degree higher than 4, in terms of +,*,/,- and roots. >> >>Do there exist more complicated formulas for these solutions, permitting >>substantially more operations? >There is a very interesting algorithm due to Doyle and McMullen >that solves the quintic by rational iteration on the Riemann sphere. >The difference between their algorithm and something much more >elementary such as Newton's method is that it converges almost >surely. Thus it is as "robust" as extracting roots. It has been shown (by Hermite, I think) that one can express the roots of any quintic in terms of elliptic theta functions.