Slashdot Mirror
General Solution for Polynomial Equations?
An anonymous reader writes "On september 9, several media reported that a young Dutch student found a formula to determine the roots of any polynomial equation. Does this conflict with Abel's proof that such a formula cannot exist? Here is the news item (in Dutch) on his school's homepage." Another reader writes "A Dutch student at the Fontys school of physics has solved a math problem of several centuries old: finding the roots of any polynomial equation. Arxciv copy here. Although an exact solution has been proven impossible for higher orders, this is not the case for numeric solutions."
http://babelfish.altavista.com/babelfish/trurl_pag econtent?url=http%3A%2F%2Fwww.fontys.nl%2Fnieuws%2 Fnieuws_artikel.asp%3Fdocid%3D3487&lp=nl_en
- Leon Mergen
http://www.solatis.com
Try this one.
To do so, we express x as a powerseries of s, and calculate the first n-1 coefficients. We turn the polynomial equation into a differential equation that has the roots as solutions. Then we express the powerseries' coefficients in the first n-1 coefficients. Then the variable s is set to a0. A free parameter is added to make the series convergent.
The short paper has more details.
"It is a greater offense to steal men's labor, than their clothes"
Apparently some people can't get to the site, which is funny because I'm having no problem, but here is a mirror.
The Roots of any Polynomial Equation
This space intentionally left blank.
The theorem of Abel (or Galois) that is being referred to merely claims that you can't find a general formula built from just the arithmetic operations plus taking nth roots. It has been known for a long time that there is a general formula using elliptic functions.
The student just used the method of formal power series to solve the equation. This approach dates back at least to Cauchy ~1850 and probably can be found in the works of Euler.
That's dutch, not german.
quidquid latine dictum sit altum videtur.
Check it out...
I used hypergeometric functions to solve the equation
a x^b + c x^d + e x^f = 0
where the exponents are integers and the coefficients can be complex. I tried to generalize it for complex exponents but I quit after a while. Google should provide some preliminary information on using hypergeometric functions to solve the quintic
a x^5 + b x^c + e = 0
where c is less than 5 and greater than zero.
This is an analytic solution to the general trinomial that I found empirically (without proof). If one wants to solve to solve the quartnomial then two dimensional structures, quintnomials need 3 dimensional structures. This was computationally taxing on me and my computer so I didn't even consider the quartnomial equations.
By the way, I have implemented a Jenkins-Traub algorithm not so long ago that gives numerical approximations to general polynomial roots. It is fast and well known.
I thought the issue with older methods was that although they converge easily on any root, it becomes non-trivial to find out where to start in order to hit some of the roots when you get to the higher orders. If this method reliably finds them efficiently and is suitable as an automated algorithm, that is certainly a useful result, though it might be not exactly revoloutionary to the field of mathematics.
sudo ergo sum
In this poster, they discuss this topic precisely, including Abel's theorem. One of the readers was correct: although Abel proved impossibility of solution for polynomials higher than degree 5 IN TERMS OF ROOTS AND OTHER ALGEBRAIC ENTITIES, there is nothing ruling out a solution in terms of, say, hypergeometrics. This is precisely what they do, and there's a nice development of this using power series. So, although I didn't get to read the PDF, it seems from the posts here that this is what the student did. Thus, no big deal. That said, I salute the student for figuring this out on his own, and he shouldn't be discouraged by discovering something that is not new.
ii) Student mistaken; popular media talking out of arse.
iii) Abel's theorem holds ("you cannot solve all polynomial equations by radicals"); student solves all polynomial equations not using radicals but using differential equations and power series; popular media like /. do not understand that this method is known for more than hundred years and that there is no inconsistence.
ps: a link provided by the author himself: solving the quintic
more quotes from the professor: "The "range" software of Oliver Aberth (that I have on our computer) can find
all the roots, real and complex, of any polynomial to whatever accuracy you
specify. Of course the more you ask for, the longer it may take, but it's
pretty fast for ten places for polynomials of degree say ten or so.
His book "Precise Numerical Methods Using C++" describes the methods used in
his range software."
Those are guaranteed solutions, too, not just "i think it's pretty close, but there's no way to prove it."
They also have guaranteed solvers for nonlinear (and/or partial) DE's... this kid is about 50 years too late.
stuff |
I agree the paper is lacking somewhat in describing why this algorithm is better. I looked into Sturm sequences. It appears that part of the algorithm is relying on a similar principal. The difference seems to come in when trying to converge on the root, which the student is using differential methods.
But as you pointed out, I'm not sure what the advantage is in doing so. I wouldn't really classify that document as a paper, more like an empirical proof. It is not by any stretch rigorous (for instance you don't use the word "should" to describe a result from a step in a proof.
~X~
~X~
Intended humour aside, that may work in many browsers, but it's not valid HTML.
Use CSS styling instead.
Ydco co
Disclaimer: it has been years since I've spoken Dutch. What follows hsould be taken with a fairly large grain of salt...
Fontys student develops important mathematical discoveryWhile most students languished on the beaches this Summer, Fontys student Geert-Jan Uytdewilligen discovered the solution to one of the oldest mathematical problems. He proved an inportant step in - wait for it - the classification of the zero-points of polynomials of any order.
This problem was already known to the ancient Egyptians. During the Renaissance, a clearer understaning of (the problem) existed, and one 19th century scientist published (a paper) on his findings that stated the problem could not be solved. But Geert-Jan Uytdewilligen, a fourth-year student at Fontys High-school of Applied Science finally shed light on the complex problem. He discovered a formula for the classification of the zero-points of any order. Mathematical proofs have thus far not come from the sixth grade.
Difficult PuzzlesEver since his youth, Geert-Jan Uytdewilligen was obsessed with the solution of difficult puzzles. 'I always feel at home in abstract thought', he says, 'In elementary school, I was very good at arithmetic, and therefore in my future studies, I stuck to mathematics. At one particular point in (my) mathemetics lesson, (we) handled the parabola. From that moment, I became interested in the pure algebraic problems that flowed from that. In particular, the higher grade comparison of the zero-points intruiged me, since mathematicians had been searching for a solution to the problem for ages. This was a challenge for me, to solve the problem which is purely theoretical. I had a slight practical advantage, because one can usually fill in the numbers(?) with a computer. The problem is then solved in this manner.'
PolynomialsGeert-jan designed mathematical formulae that were previously regarded as not-undestandable by the layperson. Perhaps you might recognize this formula: a[n]*x^n+a[n-1]*x^(n-1)+..+a1*x+a0=0. 'This is the general form of a regular polynomial', he says. Regular polynomials are a combination of increasing powers and multiplication. If you solve for x in this formula, then you get the zero-points of the polynomial. Polynomial solutions up to the sixth order are already known. I found a formula to find the zero-points of a polynomial of any order!'
PublicationGeert-Jan's discovery first saw light of day in the magazine Science Guide, and generated a lot of publicity. This was the reward of two years of hard work. Geert-Jan: 'You don't expect such a vague starting-point to result in such a hit. This is strange, considering the amount of technical jargon, which make the theory hard to follow. But at the same time, the pieces of the puzzle began to come together. Yes, I had the Eureka-moment! But I remained a freely sober person, and held myself together. I didn't allow my studies to suffer because of my hobby.'
Looks flawed to me. He performs a sensitivity analysis in the constant of the polynomial (which he calls "s"). It remains unclear why. After a convoluted sequence of operations, he derives a power series for x as function of s , and proves convergence by requiring |s| smaller than 1.
Finally, he puts back a_0 into s, but conveniently forgets the case that a_0 is bigger than 1.
Also, it is not clear whether this is in the complex plane or not. For example, for finding real roots of real polynomials, you could use Sturm Sequences. There's even sample code in graphics Gems IV (IIRC).
In any case, the student was studying at the "hogeschool" which roughly translates to "higher professional education", a school which doesn't teach mathematics, and whose level which significantly lower than Dutch the MSc., BSc. or engineering degree.
Han-Wen
(yes, I am a mathematician)
Han-Wen Nienhuys -- LilyPond
Because otherwise it wouldn't be called a solution.
"Numeric solution" is used here sloppily, it should be "numeric approximation": a number that is close enough to the real solution, or better, a process to progressively come with numbers closer and closer to the solution. In the second case, you can stop the process when you got close enough to the solution, depending on the precision you need.
Watch great movie opening scenes!
In the event you weren't joking (I'm sure lots of people don't know what he means), I believe it means that there will never be a magic equation to 4th order polynomials and above like one learned in algebra to the 2nd order polynomial:
ax^2+bx+c =0
which is:
x= (-b +- sqrt(b^2-4ac))/2a
(aka the quadratic equation)
Instead you can get VALUES for the roots by using algorithmic approaches, but you cannot come up with a generalized equation like the quadratic equation above.
If it still doesn't make sense, then it probably doesn't matter, but some lines of engineering require finding roots of high order polynomials. I haven't done it since school, so my whole post may be wrong, but there's your explanation =)
How can we continue to believe in a just universe and freedom to eat crackers if we have no ale?
Look up the "Sturm and Drang period" :)
It's not quite that simple. Your function isn't well-defined. Furthermore, I believe you would need the Axiom of Choice just to show that such functions exist.
Although I am not a mathematician, only a humble theoretical physicist, I think I understand the method and I believe that the author has come up with a clever algorithm for solving polynomial equations. Although the mathemaitcs involved is elementary (real analysis only) the note is a bit hard to follow because the presentation is a little awkward and chaotic even for a physicist (mathematicians have much higher expectations regarding the style of a scientific paper). This is a minor point, the author is probably very young and has plenty of time to master the art of scientific writing.
An important question is whether the method can be extended for computing imaginary or complex roots (other algorithms can do this without major problems).
Regarding the solution of algebraic equations of order higher than 4 by formulas, I remember vaguely that about 30 years ago I read that analytic formulas exist which involve transcendental functions (probably elliptic functions, I dont remember exactly). Of course, such formulas do not invalidate Abels' result which refers to formulas invoIving elementary functions such as square or cubic roots, etc. In addition, formulas involving special functions are hard to use, it is much easier to apply numerical methods.
Alright, whoever wrote the article seems very confused about mathematics and abel's theorem in particular. I'm not actually an algebraist myself but I am in mathematical logician so I can comment a bit about impossibility results.
Abel's theorem merely says you can not solve the general quintic (5th degree) or higher in terms of radicals. That is entierly in terms of multiplication, addition, and taking nth roots. If we don't put that restriction about radicals the solution is trivial. Let x be such that P(x)=0 is one obvious solution.
Going through this again the write up is *entierly wrong*. It is completly possible to give an exact solution for the general polynomial (I just did in the paragraph above). Furthermore this distinction between exact and numerical solutions which is made so much of by our high school and college teachers is really illusionary. Writing a solution in terms of sin(3) isn't an exact value, we just have a good algorithm to approximate sin. Really what we mean when we talk about exact solutions is solvable in elementary functions, which is nothing but a certain commonly used set of functions for which we have good approximations. Unfortunatly, we still insist on students 'solving' differntial equations rather than just finding some quickly converging numerical solution even though at a deep level these are not differnt.
Now since abel's theorem there has been considerable research on other ways to solve polynomial equations. For instance one big result was that a certain degree of polynomials could be solved in a terms of continous two place function. Possibly this result in question is another result like this one but I imagine it is much less significant. For one I'm not entierly convinced he is correct, nor novel. (Don't make the mistake of assuming if he is right he has given a continous solution of any polynomial..it isn't clear his solution is continous in the coefficents).
If you liked this thought maybe you would find my blog nice too:
When you substitute power series into an algebraic equation of degree higher then 2, you get a system of true nonlinear equations for the coefficients of the series.
Example:givesIn contrast, the paper arrives at a system of linear equations.
a formula to determine the roots of any polynomial equation. Does this conflict with Abel's proof that such a formula cannot exist? There are some misunderstandings here. Abel's result says it's not possible to solve polynomials of degree 5 or higher in terms of multiplication, addition and taking roots. If you allow fancier functions (like elliptic functions, which are similar as sin/arcsin), it's possible to solve polynomials of degree 5 [1]. The solution that the student posted is an exact solution (no numerical one). The series is exact (unless you take only a few terms of course). You can write down its coefficients explicitly in terms of the coefficients of the original polynomial. Two important remarks: 1) There exists several classes of functions (hypergeometric functions in several variables, and Siegal modular functions) which can be used to solve polynomials of any degree (this is known since 30 years or so). See bottom of [2]. 2) The method which the student used, is also known since 30 years. It can be found in the same link [3]. So, nothing new ...
[1] http://mathworld.wolfram.com/QuinticEquation.html
[2] http://library.wolfram.com/examples/quintic/main.h tml#higher
[3]: http://library.wolfram.com/examples/quintic/main.h tml#diffeq
Sturm and Drang was a pre-romantic movement in Europe, somewhere around the 1780's i believe. Some of the famous Classical composers dabbled in it, I think Beethoven has a Sturm and Drang piece. It died quickly and gave rise to the Classical (then romantic) movement.
The name of the period comes from a play by Friedrich Klinger, I think it means "Storm and Urge"
Funny, we discussed this today in academic decathlon.
Beware the Jubjub bird, and shun the frumious Bandersnatch.