Find roots of polynomial with degree $\ge 5$

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?

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.

• 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

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.
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.