6
$\begingroup$

I am trying to write a program to find the roots a given polynomial of degree N, with the form $$ A_{0}X^{N}+A_{1}X^{N-1}+A_{2}X^{N-2}+A_{3}X^{N-3}+...+A_{N} $$

I know that if there are rational roots at all, I can find an exhaustive list with the rational root theorem, and then factor them out using synthetic division to find any and all rational roots. I also know that I am fine if I can factor down to degree two, but I would like to know how to find the irrational roots of an nth degree polynomial without numeric ways like Newton's method, to be able to display the polynomial thusly.

$$ (x+2)(x-6)(x\pm\sqrt{8})... $$

Any help to be had would be appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ Numeric methods can be very interesting in their own right. Before using Newton methods and their close relations, separating roots (isolating them in the complex plane) is necessary in general. It would be more in keeping with your intent to "write a program" to learn more about numerical root finding algorithms. $\endgroup$
    – hardmath
    Commented Jul 22, 2016 at 1:50
  • $\begingroup$ You might want to look for the series of books by John McNamee. $\endgroup$
    – J. M. ain't a mathematician
    Commented Jul 22, 2016 at 11:28

2 Answers 2

Reset to default
6
$\begingroup$

It can't be done. There are formulas for the roots of a quadratic, cubic or quartic in terms of radicals, but not (in general) for the roots of a polynomial of degree $5$ or higher. For example, the roots of $x^5 + 2 x + 1$ can't be written in terms of radicals. See e.g. Abel-Ruffini theorem

$\endgroup$
11
  • $\begingroup$ @IanMiller: Roots are either rational or irrational. What Dr. Israel says is true, that the irrational roots generally cannot be expressed using only symbols for radicals and rational arithmetic, once degree $n \ge 5$. $\endgroup$
    – hardmath
    Commented Jul 22, 2016 at 2:19
  • 1
    $\begingroup$ @IanMiller You don't seem to understand what I wrote. There's no question that the roots exist, it's just that they can't be expressed in the form that the OP appears to want to express them in. Numerical methods can be used (but the OP doesn't want them); sometimes special functions or series can be useful. $\endgroup$
    – Robert Israel
    Commented Jul 22, 2016 at 5:20
  • $\begingroup$ To expand on Robert's note: it is known that there are algebraic numbers of degree 5 and higher that cannot be expressed in terms of radicals; one thus has to use special functions like the hypergeometric functions, Meijer $G$, (multivariate) theta functions, or (hyper)elliptic functions to represent them in closed form. $\endgroup$
    – J. M. ain't a mathematician
    Commented Jul 22, 2016 at 11:26
  • $\begingroup$ Sorry I used the wrong words. I meant surds not irrationals. I meant the OP was interested in finding roots involving surds. These will exist for some polynomials of degree 5 or higher. Can you expand your answer to cover when roots involving surds will exist or not and how to find such roots. Depending on the context the OP intends to run their program they may only be looking at problems involving surd based roots (e.g. from a textbook). $\endgroup$
    – Ian Miller
    Commented Jul 22, 2016 at 23:55
  • $\begingroup$ I assume your polynomial has rational coefficients. First factor it over the rationals. For each factor, compute the Galois group, and check whether that is solvable. If so, you find the splitting field... All this is not something the OP is likely to be able to program. See e.g. Andreas Distler's dissertation and the GAP package Radiroot. $\endgroup$
    – Robert Israel
    Commented Jul 23, 2016 at 0:25
5
$\begingroup$

An efficient algorithm to factor a polynomial into irreducible polynomials is given in this article. The lattice basis reduction algorithm they developed for this purpose is the famous LLL algorithm which has many applications besides its use in polynomial factorization problems.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .