Galois Theory tells us that we cannot directly solve for the roots of a quintic polynomial using elementary operations and radicals.

I have seen sources that use this to reason that any computer algorithm that solves for the roots of a quintic must use an iterative method.

However, quintics can be solved using elliptic functions. Is it right to say that those sources are wrong, and that it is possible to have a direct, non-iterative, solver for the roots of a general quintic polynomial via elliptic functions?

  • $\begingroup$ The issue arises already with $x^2=2=0$, and more spectacularly with the casus irreducibilis of the cubic. $\endgroup$ – André Nicolas Jun 10 '14 at 14:44
  • $\begingroup$ See here and here. $\endgroup$ – Lucian Jun 10 '14 at 15:22

... only if you have a direct, non-iterative method for evaluating the elliptic functions.

See Bring radical for more on this subject in general.

20140610 Reply to comment: It depends on what you mean by direct solver. Which of these numbers is "direct": $0$, $1$, $2/3$, $\sqrt{2}$, $\sin(1)$, $\int_{\pi}^{\pi^2} \mathrm{e}^{\mathrm{e}^x} \, \mathrm{d}x$, $\vartheta(1-\mathrm{i}, 1+\mathrm{i})$, where the latter is a relevant Jacobi theta function.

Well first, the single-variable elliptic functions only allow directly writing solutions to quintic and sextic equations, but are inadequate for higher degrees. There are more convoluted functions that allow for writing down the solution of some higher degree polynomials. (The septic requires elliptic and hyperelliptic functions.) I am not aware of a class of functions sufficient to write down the solutions of a polynomial of arbitrary degree. (It may be the the set of hypergeometric functions with numbers of parameters increasing as the degree increases is such a class, but I do not know this.)

Next, the fundamental problem is that there are roots of quintic and higher degree polynomials that cannot be expressed as any sequence of operations of addition, subtraction, multiplication, division, and rational powers (which includes $n^\text{th}$ roots) applied to whatever rational numbers you like. The set of numbers constructed by those operations does not reach all the roots of all the polynomials. (It does reach some roots of some polynomials.) So there is just no way to use these operations and reach an arbitrary root. Consequently some other operation must be used. The operations listed are "nice" because there are no worse than quadratic (in the lengths of the arguments and in the admissible relative error for roots) time algorithms for addition, subtraction, multiplication, division, and rational powers. (I may slightly misremember -- I have a notion that the algorithms aren't much worse than linear (like, $O(d \log d \log\log d)$) in the lengths of the (correct prefix of the) outputs.)

Finally, the functions used in writing down the roots of these higher degree polynomials are evaluated numerically using numerical integration or numerical summation. Both of these methods are iterative and can easily be "slow". So one has a few choices:

  • Leave results written in terms of elliptic and higher functions. Such a result is exactly correct, but hard to compare with other numbers and hard to do arithmetic with. (Consider trying to divide and simplify two numbers both of the form of the general solution of the quartic.) This may be infeasible. As the Bring Radical article comments, the changes of variable to reduce an arbitrary quintic to the form solvable with the Bring radical can require intermediate expressions of extraordinary length. This problem of intermediate expression swell becomes substantially worse for general polynomials every time the degree is increased.
  • Use various (iterative) interval methods to find an interval isolating a single root and then use some sort of (iterative) root-finding algorithm to numerically approximate the root, like Newton's method, which (once it gets in the basin of attraction of a single root) doubles the number of correct digits on each iteration. See Jenkins-Traub algorithm for a modern option. Or
  • Use (iterative) numerical integration or (iterative) numerical summation techniques to approximate the roots starting from the form written in terms of elliptic and higher functions. This version incorporates the worst aspects of both of the above methods. First, the intermediate expression swell can be astounding. Also, one is happy if these methods give one more digit of accuracy per iteration. (Details depend on the functions being evaluated and their behaviour in the neighborhood of the arguments at which they are being evaluated. It's not uncommon to only have logarithmically many correct digits in the number of function evaluations, so getting another correct digit requires as much work as (a multiple of) all the work done so far.)

Implementing the first of these options requires the hard math of finding a sufficient collection of higher functions to write down solutions to any polynomial you care to write down. This may involve infeasible amounts of scratch memory and the results may be "useless" in that unraveling the changes of variables may produce an expression too complicated to do anything with.

Implementing the second of these options requires a little calculus and works almost immediately, giving a result to as much precision as one desires. (Crazy precision can take longer than "immediately".) Other than a few tricks to organize evaluating powers and evaluating polynomials, there is very little complication. The result is a finite precision approximation to a real number that is very easy to perform operations with. There are several widely available implementations that just work.

Implementing the third of these requires relatively complicated numerical methods. ("Complicated" compared to Newton's method.) They are slow to obtain modest accuracy and precision. Crazy precision can require more time than will pass until the Heat Death of the Universe (or whatever other event finitely far in the future one prefers).

To sum up, the usual meaning of "direct, non-iterative" does not apply to any version of finding the roots of a polynomial that gives you a result that is computationally useful.

| cite | improve this answer | |
  • $\begingroup$ So, the unsolvability of quintics from Galois Theory alone does not mean there can never be direct solvers for a general quintic? There might be a stronger result but there are ways to get roots without elementary operations and radicals, and it depends if we have a direct solver for those ways. $\endgroup$ – Jean Valjean Jun 10 '14 at 20:56
  • $\begingroup$ @JeanValjean: I have expanded my answer somewhat. $\endgroup$ – Eric Towers Jun 10 '14 at 22:14
  • $\begingroup$ Thanks for the very detailed response! I wish I could up your answer more than once. $\endgroup$ – Jean Valjean Jun 12 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.