General Solution for Polynomial Equations? 482
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."
The fish (Score:5, Informative)
Re:The fish (Score:5, Funny)
Re:The fish (Score:5, Funny)
I'm guessing your degree was for English Mathematics. This paper is clearly in Dutch Mathematics (so, just head over to Babelfish).
Re:The fish (Score:5, Funny)
At least it isn't in Polish Mathematics. Not only would it be difficult to decipher, you'd also have to read it backwards.
Re:The fish (Score:5, Funny)
Re:The fish (Score:5, Funny)
Re:The fish (Score:3, Funny)
Re:The fish (Score:3, Funny)
Hey, thanks for volunteering!!
Re:The fish (Score:4, Funny)
Re:The fish (Score:3, Informative)
That's fun is the Muppetizer that was on the www.muppets.com website before the evil Disney took it over. I have a copy of it here [jlcooke.ca].
Even funnier are the swear words they replaced!!! [jlcooke.ca]
slashdot walkabout (Score:5, Funny)
1) put poly in standard form and take the first n-1 derivatives.
2) put the derivatives in terms of x(s) (for 1..n-1), or remember why you dropped calculus and goto step 9.
3) Use the derivatives to write a differential equation with coefficients m1..mn, or remember why you dropped differential equations and goto step 9.
4) Use the original equation to reduce the differential equation to order n, and note the use of "then" instead of "than" in the mit write-up. (sorry, mit).
5) Substitute a formula for x(s), multiply resulting eq by it's denominator, getting another diffEq. Whee! ask a Grad student.
6) Now substitute a power series representation. All 's' should be zero. (mutter: Aha! I knew it) Solve b_sub_i for 1..n-2 (Grad student).
7) Substitute another power series to get an equation. (The grad students are gone, ask your hallmates, one of 'em has to be a math major.)
8) Let b_sub_n-1 equal the determinant of a funky, unexplained matrix (here, have an aspirin).
9) Everyone else in the class is out drinking by now, so don't worry about the next matrix, it's even funkier. Write a note on your hand to memorize it this weekend. Go drinking with peers.
10) Wake up at 3pm tomorrow, and try to remember what the hell all those squiggles meant.
11) Change your minor from math to polisci. Don't worry about taking Calc 1-3, DiffEq, or linear algebra. Note: many girls do not care about the roots of arbitrary polynomials, so no worries there. 8^)
damn, you're right. (Score:3, Funny)
Shitsurei shimashita *cuts off finger*
Right in the middle of my Calc class too... (Score:5, Funny)
Dang it, that means I'll have to buy a new math book for this quarter's Calc class, won't I?
Ah, the world, she is a changin'...
Re:Right in the middle of my Calc class too... (Score:3, Funny)
Re:Right in the middle of my Calc class too... (Score:5, Insightful)
Abel's proof showed that polynomials with a degree higher than 4 could not be solved algebraically (i.e through a finite number of additions, subtractions, multiplications, etc.). Abel's proof did no say it was impossible to solve the equations (indeed, numerical solutions to these equations are solved regularly).
This is similar to how some integral equation solutions cannot be expressed in simple terms. However numerical answers are rather easy to obtain (even easier with a computer)
The method presented is a simpler way to find the roots of polynomial equations numerically by treating it like a power series (x, x^1, x^2,...,x^n) and applying standard differential techniques.
Pretty cool if you ask me.
~X~
Re:Right in the middle of my Calc class too... (Score:5, Interesting)
Re:Right in the middle of my Calc class too... (Score:3, Informative)
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 d
I wonder if anyone will get this... (Score:5, Funny)
Less Drang.
Re:Right in the middle of my Calc class too... (Score:5, Funny)
Re:Right in the middle of my Calc class too... (Score:4, Informative)
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 =)
Re:Right in the middle of my Calc class too... (Score:5, Informative)
Re:Right in the middle of my Calc class too... (Score:3, Interesting)
Personally, I am entierly unimpressed with this paper. The numerical method involved looks h
Re:Right in the middle of my Calc class too... (Score:3, Interesting)
I'm pretty sure there is a general numerical solution doing something fairly simple (a little better than newton's method). Of course it is entierly inefficent and practically useless.
Re:Right in the middle of my Calc class too... (Score:3, Funny)
Anything is possible at Zombo.com [zombo.com].
There's no conflict... (Score:5, Interesting)
Although an exact solution has been proven impossible for higher orders, this is not the case for numeric solutions.
No conflict here. Saying that an exact solution does not exist is consistent with saying that numeric solutions do exist.
A numberic solution is a solution that is "close enough", but not exact. Sort of like saying 2.0000000000000001 = 2. They aren't equal, but for many purposes, they are equivalent.
Re:There's no conflict... (Score:2)
Yeah, except that the author of the paper claims an algebraic solution.
Re:There's no conflict... (Score:3, Informative)
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.
Better formula (Score:4, Funny)
Re: Exact solutions are useful (Score:4, Insightful)
Not so. Exact solutions like the ones provided by mathematical formulas are still useful for a number of reasons:
Re:Better formula (Score:5, Funny)
Maths == Dutch (Score:5, Funny)
Re:Maths == Dutch (Score:5, Funny)
Re:Maths == Dutch (Score:5, Funny)
Re:Maths == Dutch (Score:3, Funny)
Man does the impossible (Score:5, Insightful)
i) Abel's proof contains a flaw that generations of extremely talented mathematicians have failed to spot in their years and years of teaching it.
ii) Student mistaken; popular media talking out of arse.
(Can't read PDF; slashdotted)
Re:Man does the impossible (Score:2, Funny)
Re:Man does the impossible (Score:5, Insightful)
iii) Student comes up with interesting (and possibly new, I don't know) result of generating infinate series which converges to root of polynomial. Someone (popular media?) believes that this violates Abel's proof (it doesn't, his proof is for finite representations of the roots).
This has NOTHING to do with Abel, or Godel, or anyone other related theories, as they do not consider the case of infiniate series.
Re:Man does the well-known (Score:4, Interesting)
Using series to approximate the solution of differntial equations is taught in class. Heck, go a little further in mathematics and you'll conjure up polynomials functions as the solution to a set of partial differential equations, known as the Galerkin Method [duke.edu]
So in what way is the above news? (Hint, take a look at the link and what's stated there.)
Better than that (Score:4, Insightful)
You can do "better" than that. If you're prepared to write the roots in terms of logical functions, you can "solve" anything.
Want the roots of f(x) = 0?
They are
There are even computer implementations of this for limited cases (called "generate and test" algorithms). But I wouldn't advocate running big headlines claiming -- MarkusQRe:Man does the impossible (Score:5, Interesting)
Now I'll RTFA to determine which it really is....
Re:Man does the impossible (Score:3, Informative)
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
Re:Man does the impossible (Score:5, Insightful)
Yeah, but Newton's method isn't guaranteed to converge. This method claims to converge; although you don't get the exact answer in a finite number of steps.
Whether this method is useful or not, probably depends on how fast it converges and how long it takes to do each step.
Re:Man does the impossible (Score:5, Funny)
Re:Man does the impossible (Score:3, Funny)
Re:Man does the impossible (Score:3, Insightful)
1,...,9,10
or base 8:
1,...,7,10
Your argument that 1base(pi) should be pi is ridiculous because 1 in any base (short of base 1, which is equally ridiculous) is really just plain 1. Things only get interesting once numbers exceed the base value.
Posted at +2 just for fun
Re:Man does the impossible (Score:3, Insightful)
10(base 2 =2(base 10
10(base 8 =8(base 10
etc.
Mirror (Score:5, Informative)
The Roots of any Polynomial Equation [mit.edu]
Re:Mirror (Score:3, Interesting)
Its no big deal (Score:5, Informative)
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.
Re:Its no big deal (Score:5, Funny)
Re:Its no big deal (Score:4, Funny)
Re:Its no big deal (Score:5, Funny)
In the U.S., that is a big deal.
I have found a replacement for an old cliche (Score:2, Funny)
I will do this whenever possible in honor of this Dutch student's obviously impressive, but absolutely inscrutable (to me) breakthrough.
No sample code or algorithm? (Score:5, Insightful)
Re:No sample code or algorithm? (Score:3, Interesting)
To lend validity to either of these statements, you need to add understandable, accessible evidence. Jim thinks he fixed the mail server. It's been up and running for 30 days without any
I am old (Score:2, Interesting)
This is yet another reminder of how long it has been since I was in university....
I can recognized the names of the equations involved, but that's about it...
In many ways, that illustrates how useful the knowledge has been over the years!
I guess this is obsolete now... (Score:4, Funny)
LISTER: Yeah, the Skutters managed to smuggles something out of the medi-lab for us, y'know that stuff that helps impotent guys put the zest back in their love lives?
KRYTEN: 'Boing!', the virility enhancement drug!?
LISTER: That's the stuff, and we've Mickey Finn'd their drinks.
RIMMER: Within seconds, you're harder than a quadratic equation, and, it doesn't wear off for seven hours.
KRYTEN: For seven hours those guys are going to be like catapults!
Red Dwarf, Series 8, Episode 6 [blueyonder.co.uk]
Rule of equations in school (Score:5, Funny)
The more complicated the equations for the math problem looks, the more likely the answer is 1.
Re:Rule of equations in school (Score:5, Funny)
Re:Rule of equations in school (Score:5, Insightful)
Time for some mega nerdiness: I was captain of the math team when I was in high school.
Feh, screw that "nerdiness" crap. Good for you. Math is a powerful tool, worthy of dedication. I wish I were better at it, and respect those who are. I think being captain of the math team is far and away a better thing than being the captain of the freakin football team.
Isn't it an approximation method? (Score:5, Interesting)
Re:Isn't it an approximation method? (Score:5, Insightful)
/.'ed, try this Coraled URL using another source (Score:3, Informative)
My brain seems to have shut down. (Score:4, Funny)
Easy! (Score:4, Funny)
(2) From [1], we have determined that the correct roots, a1...an, exist in Sa.
(3) Let the set Sb be the set that contains only a1...an.
(4) The intersection of sets Sa and Sb will thus be the roots of the polynomial equation.
Therfore, we derive the formula:
Sa ^ Sb = roots
Re:Easy! (Score:5, Funny)
5) Profit!
(awaits an ass-whooping by the mods)
europe (Score:5, Funny)
european academic finds solution to very hard problem.
2 years later:
a) americans find way of turning said solution into entertainment technology and make billions of dollars.b) European academic still unemployed and eating pasta all week.
We need more GREED in europe..
Re:europe (Score:3, Funny)
Obvious Hoax (Score:4, Funny)
This doesn't seem likely (Score:5, Interesting)
However, from what I remember, Abel's theorem was proven using Galois Groups and Field extensions. This implies that what it actually proves is that analytical solutions using a particular set of functions -- in particular, the field operations (addition, subtraction, multiplication, division by non-zero) extended to include radicals (square, cubic, etc roots), composed in any way possible (as in a ruler and compass construction proof) cannot possibly generate an analytical formula depicting the solution for polynomials of order greater than 4.
Does this mean that an analytical formula using other functions is impossible? Not at all. Trivially, I will define a function called, say, omega, which, given a n-dimensional complex vector, gives a solution to one of the roots of the function a_n * x^n + a_(n-1) * x^(n-1) +
Clearly, this solution is analytical in the sense that it a) provides an exact solution and b) is algebraic in nature. However, it isn't useful, because it depends on a function (omega) which cannot itself be defined analytically in terms of other functions (or at least, not ones we know how to compute).
The reason Abel's proof is so important is because it deals with the 4 fundamental operations that polynomials themselves use (the field ops) and adds radicals, which are inverse ops to the building blocks of polynomials themselves. So it essentially says, we cannot use the functions that we constructed the polynomial with to solve it.
Now, my omega function may seem a little bit contrived to non-math types, but actually a large number of functions are arbitrarily defined this way. Logarithms are a good simple example. An analytical formula for the likes of log n wouldn't be possible either, and yet we study logarithms without having an express analytical means of calculating them.
What you should ask yourself is, what does analytical mean, anyway? It really isn't useful (or correct) to say that no analytical solution exists unless you explicitly restrict what particular set of 'basic' functions/operators the analytical solution can contain. In Abel's case (and it's a beautiful proof, by the way) he uses the field operators plus radicals. But what if you added logarithms into the mix? Exponential functions?
It's impossible to say. If you don't restrict your base, you open yourself up to the attack that I just used with the omega function (which certainly exists, after all, I just defined it.)
No closed formula (Score:5, Insightful)
I did something similar (Score:5, Informative)
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.
Here's a math prof's take on the paper (Score:5, Insightful)
I don't know what his point is. He says its a "method of solving the roots"
of a polynomial. Well, we already have very fine methods for doing that,
interval Newton methods for instance. Using circular disk arithmetic in the
complex plane we can find all the complex roots as well.
There is no need whatever to make things more complicated such as going to
differential equations. That is unneccessary. Root finding is an algebraic
problem."
... guaranteed solution formulae here (Score:4, Informative)
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.
See Mathematica Poster: "Solving the Quintic" (Score:4, Informative)
An applied mathematician's take (Score:3, Insightful)
People here have been commenting that Newton's method works just fine for finding roots of polynomials. But, convergence can be quite slow, especially for unidentified multiple roots though, and for highly clustered roots you can run into conditioning problems.
The paper makes no mention of actual numerical algorithms (in particular no discussion of convergence rates or guarantees for solving the ODE numerically) so it is hard to say whether the result is actually useful or just a bunch of manipulation of symbols on paper.
Translation (Score:3, Informative)
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 (Score:5, Informative)
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)
Professional (Score:3, Interesting)
Besides, at the "Hogeschool" there is teaching of mathematics, just not in the same way as at an university: It is much more "practical" - ie. without going through all the 'proving-stuff' - and the level is generally lower than at a university. But the technical studies still provide an adequate leve
Re:Looks flawed (Score:4, Informative)
Except he doesn't forget this. He tells you to divide the polynomial by a constant to make it so. Since you're a "mathematician" let me help you visualize this difficult step:
Gee, a_0 is less than 1 now and the roots are the same. Huh, I wonder how that happened? In actuallity he tells you to divide by a larger number such that all of the coefficients are fractions, but you get the picture.
Re:Looks flawed (Score:4, Insightful)
Re:Looks flawed (Score:3, Informative)
Read the paper. There is no such assumption that a_n=1. (Why else have a_n in the numerator of equation 5 if it's always 1?) He is quite explict about dividing by "(more than) the maximum of the absolute values of the coefficients". Dividing by any non-zero constant (even complex) does not change the roots of the polynomial at all.
Assuming his formula are correct for the expansion coefficients, the series is guaranteed to converge once you perform the recommended normalization. The grandparent is wrong, a
Re:Looks flawed (Score:3, Insightful)
Well then,
Sounds like precise mathematical terminology and understanding of the operations.
Typical academic arrogance. Letters after your name do not make your more corr
Re:Looks flawed (Score:3, Interesting)
The problem is that it is not "mathematics," in the sense that he doesn't write a logical sequence of formally specified lemmas, proofs or conclusions. It is not clear what the author is doing, so it is also not possible to pinpoint exactly where the errors are.
Re:Looks flawed (Score:3, Insightful)
First, he never gives any clear indication whatsoever of what he intends to prove that his method will do. What does it mean to p
I can't believe nobody's noticed this... (Score:3, Interesting)
What I'm surprised at, though, is that nobody's pointed out the most obvious problems with this scheme:
Mathematical Elucidation (Score:5, Informative)
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).
Can't contradict a proof (Score:3, Interesting)
This is news? His method seems a rehash... (Score:3, Interesting)
The method presented in the paper looks a lot like James Cockle and Robert Harley's differential resolvent, which was new in 1862. This page [wolfram.com] gives an overview of some of the known methods for solving quintic and higher degree equations. Apparently, about twenty years ago Hiroshi Umemura [nagoya-u.ac.jp] found a general analytical solution for a polynomial equation of arbitrarily high degree involving Siegel modular forms, which are generalizations of the elliptic modular functions Charles Hermite used in 1858 as a solution to the quintic. Note: these don't violate Abel's Impossibility Theorem as they are not solutions in radicals.
Re:/.ed after 4 comments (Score:2, Informative)
Re:/.ed after 4 comments (Score:5, Funny)
Re:/.ed after 4 comments (Score:5, Funny)
Dang, I just started reading this, and you allready beat me to it! ;-)
However, I am still typing up my GUT (I prove that there are only 17 dimensions, string theory is wrong, the Multiverse doesn't REALLY exist, and that the cat is alive or dead BEFORE you open the box), and should have it available for subscribers shortly.
Re:/.ed after 4 comments (Score:4, Funny)
<BODY TOPMARGIN=(integer) LEFTMARGIN=(integer) MARGINHEIGHT=(integer) MARGINWIDTH=(integer)>
That way, you'll never run out of space.
Re:/.ed after 4 comments (Score:3, Funny)
Do I hear crickets?
Re:Damn, 11 Years too late (Score:5, Informative)
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.
11 Years too late (Score:4, Funny)
Re:run away! (Score:5, Informative)
Re:run away! (Score:2)
Temporarily not available!
This site is not temporarily available because of too much
data-verkeer.
Re:run away! (Score:5, Funny)
(Mods, parent was mistaken, but not a troll).
My favorite word in the 503 message was geblokkeerd. That's what I'm going to use instead of "slashdotted" from now on -- "Oh no! The site is geblokkeerd!"
Re:Very Skeptical (Score:3, Funny)