Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

During our research we came up with the problem of computing the root of a polynomial of degree $\ge 5$ exactly. The coefficients are, except for the linear and constant term, all non-negative and there are only terms with even degree. The only thing we know is that there formulas for a degree up to 4 and no formula for a higher degree, but is it possible to compute the roots of a higher-degree polynomial exactly, too? If so, what is the complexity?

Here is some more information:

The equation looks like $A(n) - x - a_0 = 0$ for some arbitrary integral $n$. Thereby, $A(0)=x$ and $A(i) = a_i \cdot A(i-1) \cdot (A(i-1)+b_i) $ for $i \in \{1,\ldots,n\}$. All the values $a_i,b_i$ are non-negative real numbers for $i \in \{1,\ldots,n\}$ whereas $a_0$ is arbitrary.

share|improve this question
2  
Since you say "there are only terms of even degree", do you mean the polynomials are of the form $\sum_{i=0}^n a_i x^{2i}$? In that case, would it help to substitute $y = x^2$ and solve the corresponding polynomials $\sum_{i=0}^n a_i y^i$? –  Johannes Kloos Sep 13 '13 at 13:19
    
Yes, that was what i meant. Anyway, the degree can still be of any order after the substitution. –  user1742364 Sep 13 '13 at 13:20
    
The possibility of having a formula to find the roots of a polynomial of degree greater than $4$ depends on the polynomial, or rather, on 'how it looks'. Can you provide more details regarding your polynomials? –  Git Gud Sep 13 '13 at 13:21
    
If all terms are even degree, and the coefficients are non-negative, I think this means there are no real roots ? –  bubba Sep 13 '13 at 13:30
    
The answers below are claiming that if your polynomial has degree greater than $8$, then you're screwed. This is not so. Consider the polynomial $x^{12}+x^6+1$. Setting $y=x^3$ you can reduce it to the fourth degree polynomial $y^4+y^2+1$ and setting $z=y^2$ you get the second degree polynomial $z^2+z+1$. So you can easily find the roots of $x^{12}+x^6+1$, despite the fhat that rational root test isn't useful. –  Git Gud Sep 13 '13 at 13:32

2 Answers 2

If all the terms have even degree, you have a polynomial in $x^2$. Written that way, you have a polynomial of half the degree. This solves your problem if the original degree is $8$ or less. Otherwise, some polynomials of higher degree can be factored, giving exact roots. The rational root theorem can be your friend. Unless that is the case, you are out of luck.

share|improve this answer

Exactly? Depends on the polynomial. Note that for a polynomial of even degree, the substitution $y = x^2$ halves the degree of the polynomial, so for instance if the polynomial is degree six or eight, you can find its roots in closed form.

Otherwise, your only hope for exact roots (when the coefficients are rational) is that the polynomial has some special form, or factors. Linear factors can be extracted easily using the Rational Root Test. I'm sure more sophisticated algorithms exist that can be used to attempt to pull out higher-degree factors.

Lastly, if you just need the roots approximately, I will repeat my usual recommendation of the Jenkins-Traub algorithm -- the best numerical algorithm, in my experience, for finding all of the roots of a polynomial with a high degree of efficiency and accuracy.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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