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."
a formula to determine the roots of any polynomial equation. Does this conflict with Abel's proof that such a formula cannot exist?
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.
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 am a phycisist, not a professional mathematician, and I didn't understand all steps in the whole paper. However, the author mentions a series expansion with an infinite number of terms in equation (6), although only the first n terms are ever used in defining the solution. That sounds a bit strange to me. In any case, the exact solution for a third-order equation (n=3) involves lots of cube roots and I don't see those anywhere, which also suggests that it's all about an approximation method.
Avantslash: low-bandwidth mobile slashdot.
IANAM, so I cannot really decipher the proof with any accuracy, but like any good Slashdot reader I will not hesitate to state my uniformed opinion.
It strikes me that there may be a problem since taking derivatives is involved. It seems like one might lose some valuable information by using derivatives to solve the equation since the zero-order term is lost.
Can a trained mathematician enlighten us on how this proof works?
Now I'll RTFA to determine which it really is....
The article in question is slashdotted, but my guess is either that this is media sensationalism, or the writeup is claiming something different from the student -- it seems like perhaps a new way to numerically approximate polynomial roots has been discovered.
... + a_0 where a_n are the elements of said vector. Then, by repeated application of omega and polynomial long division, I have an analytical solution to any polynomial, of any order, in complex space.
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.)
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
So in what way is the above news? (Hint, take a look at the link and what's stated there.)
The cesspool just got a check and balance.
It's a shame the paper doesn't say why this is better than using Sturm sequences, which work perfectly well.
Off-topic, but if you are at MIT, then perhaps your requests are routing through Internet 2? Just a thought. Try tracerouting to the site and see what you get.
It doesn't hurt to be nice.
What I'm surprised at, though, is that nobody's pointed out the most obvious problems with this scheme:
- Your polynomial has (up to) n roots; this approach converges, maybe, to one of them. Which one do you get, and how do you get the others?
- For that matter, some chunk of those n roots may be complex; but all the maths in his article are real. How do you solve, say, x^6+1 = 0?
The change in radius of convergence at the end of his post is a little dicey too, at least as I'm reading it, but I could be misreading. Still, I'm frankly stunned. Worthy of a press release? If I'd turned this in as a school assignment it wouldn't even have been worth an A!Wrong. A mathematical proof demonstrates to (some) other mathematicians that the approach works for all cases. Meanwhile, this translates to the rest of the world as "the math guys say they think this works." To many of us, this is roughly equivalent to hearing someone say, "Jim thinks he has fixed the mail server."
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 problems. Here is a proof showing how to numerically solve any polynomial equation and here's a program that runs the algorithm and shows several examples that work.
Not a mathematician here, but just a fellow dutchman who likes to add that even though the student in question isn't studying at a university, that doesn't simply mean he couldn't have come up with a nice idea.
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 level of mathematics, as necessary for any serious engineering work.
Slashdot: stuff for news, nerds that matter, matter for news, stuff that nerd
It's a nice NUMERIC method. There are other numeric methods that do the same exact thing. This one is nice. It may be better to implement, and/or easier to use than other common numeric root finders. This method is, therefore, not only valid, but perhaps very useful science. The next time I need to write a root finder, I will definitely give this a close look. BUT THIS HAS NOTHING TO DO WITH ABEL'S THEOREM!!!
Abel's theorem proves that no exact root finder is possible. It has nothing to do with numeric root finders, except for making them a little more interesting for practical applications.
What I mean is, even if exact root algorithm were possible, numeric root finders would still be useful. For many problems where an exact solution does exist, a numeric solution is more useful. An good example would be Gaussian elimination (for solving systems of linear equations).
Gaussian elimination gives an exact solution. If you try to use it in practice, with coefficients given as floating numbers, you realize that for many matrices the rounding errors kill the precision of the result. A common cure for this is to run a few iterations of a numeric approximation method on the output of the Gaussian elimination, which improves the precision.
Now, back to root finders. An exact solution is not possible for polynomials of degree higher than 5. It is possible for polynomials of degrees 1, 2, 3, and 4. However, the formulas for degree 4 get rather long. So long a numeric method would quite possibly be more accurate. It would not write the roots out in radicals, but the floating point representation (that's what you want anyways, right?) would be more precise.
The point of this essay - when you need numeric results, numeric methods are often more useful than precise formulas, even where precise formulas exist. If Abel's theorem were wrong, you'd probably still use numeric root finders in most practical cases.
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.
Han-Wen Nienhuys -- LilyPond
I already made a long post explaining the article (if you are really curious look at my recent posts) but I needed to point out here that you forgot radicals in your descriptiong. Even the quadratic isn't solveable in terms of finite additions subtractions, multiplications. Abel's theorem says that you can't solve the general polynomial of degree five or higher using addition, multiplication and taking nth-roots.
Personally, I am entierly unimpressed with this paper. The numerical method involved looks horridly inefficent (newton's method is probably pragmatically more interesting) and the math itself seems pretty uninspired.
If you liked this thought maybe you would find my blog nice too:
Hmm...I don't have a source but I'm pretty sure you are incorrect. Sure *fixed width* floating point solutions won't work but this is hardly enough to show there is no general numeric solution.
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.
If you liked this thought maybe you would find my blog nice too:
Proofs cannot be contradicted that's the point. That's why it's called a proof.
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 gives an overview of some of the known methods for solving quintic and higher degree equations. Apparently, about twenty years ago Hiroshi Umemura 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.
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
Being a "young student", he certainly deserves honorable mention for his discovery. Unfortunately though, I don't think that it is new math. I think it is the well-known "Lagrange Inversion Formula" in disguise. See http://encyclopedia.thefreedictionary.com/Lagrange %20inversion%20theorem
Set "z" there to s. Set "w" there to x. Set "f(w)" = - (a_n x^n + ... + a_1 x). So "w = g(z)" is then x = g(s). I believe that the "a" there (the initial estimate for "w") would be -a_{n-1} / n a_n. Give it a try.