# Solving polynomials in $\mathbb{Q}[X]$ exactly

I wanted to write an equation solver for rational polynomials in one variable $X$. However, such solutions do not need to be in $\mathbb{Q}$. What I wanted was to display solutions "lossless", i.e. not $1.414$, but $\sqrt 2$. Somehow, I believe that solutions for Polynomials in $\mathbb{Q}[X]$ are always constructible with "$+$", "$\cdot$" and "$\sqrt[n]{}$".

Now, I have a lot of questions:

1. Let's call $K:=\mathbb{Q}(i)(\sqrt[n]{2},\sqrt[n]{3}, \sqrt[n]{5}, ...)$ (brackets mean adjunction). Is $K$ algebraically closed? If not, what field do I need to solve polynomials in $\mathbb{Q}[X]$?
2. Is it true that $K$ is exactly the set of algebraic numbers?
3. Do you know a simple algorithm for constructing the solutions of a polynomial in $\mathbb{Q}[X]$? For maximum degree $4$, there are formulas, but what if the degree is higher? Important: The algorithm shall not approximate, I would like to have radical terms in the end.
-
There is a field called Galois theory that explores all this. It is fairly technical, but there are no formulas involving only radicals for polynomials greater than $4$. In particular, your assertion that starts "I believe" is false, even if you mean to include general $k$th roots, not just square roots. – Thomas Andrews Aug 22 '12 at 13:36
$\sqrt[3]{2}$ is a simple example of an algebraic number not in $K$. – Chris Eagle Aug 22 '12 at 13:37
@ChrisEagle I was sort of assuming OP meant to include general roots, not just square roots, but that's unclear from his examples. – Thomas Andrews Aug 22 '12 at 13:40
If you really only want to allow square roots, then the numbers are exactly the numbers which can be constructed with a straight edge and compass alone. – Thomas Andrews Aug 22 '12 at 13:43
The important thing to note is that Galois theory shows not only that there is no general solution to polynomials using radicals, but that there are specific polynomials for which the solutions cannot be expressed in terms of radicals. In other words, you can show a particular $5$th degree polynomial with no roots in $K$ (even if $K$ includes general roots, not just square roots.) – Thomas Andrews Aug 22 '12 at 13:56

The Abel-Ruffini theorem implies that there is no formula for solving in radicals a general polynomial of degree at least 5. In practical terms, this means that for some polynomials of degree $n\geq 5$, you will be able to construct their root using addition, multiplication and radicals, but not for all. For example, consider the polynomial $x^5-x+1$.

As for the field $K$, as mentionned in the comments, it is not algebraically closed; for example, $2+\sqrt{2}{}$ has no square root in $K$. The field in which all rational polynomials have a root is the algebraic closure of $\mathbb Q$ (in $\mathbb C$). The right way to deal with all your questions in through Galois theory, a branch of Abstract algebra.

-
Okay, I corrected that, I really meant nth roots. If I take nth roots, do I get the algebraic closure then? Are my questions (1) and (2) right? – Johannes Aug 22 '12 at 14:06
And one additional question: Even if there is no formula for degree $>5$, is there really no algorithm? I mean, aren't there for example some candidates for solutions which I could test? Or is there any heuristic? – Johannes Aug 22 '12 at 14:09
No, adding all n-th roots will not get you an algebraic closure - if it did, you could solve $x^5 - x + 1$ over that field, which is impossible by Abel-Ruffini. – Johannes Kloos Aug 22 '12 at 14:19
@Johannes No, there is no algorithm that will give you the exact roots. Of course, there are approximation techniques, e.g. Newton's method. Also, $K$ is still not algebraically closed - see my edit. – M Turgeon Aug 22 '12 at 14:52
@Johannes In fact, someone mentioned on another post that the general quintic can be solved using the Jacobi theta functions, although I am in no way familiar with this method. And by the way, if you look at the first picture of this link (mathworld.wolfram.com/QuinticEquation.html), all the red dots correspond to unsolvable quintics, which indicates that most quintics are not solvable. – M Turgeon Aug 22 '12 at 15:53

As mentioned in the other answers there are polynomial root which cannot be expressed as radical expressions. Nevertheless there are different ways to store polynomial roots "lossless". The most intuitive one is an interval representation

$$(a,b,P)$$

with $a,b \in \mathbb{Q}; a < b$ and $P \in \mathbb{Q}[X]$ such that the open interval $(a,b)$ contains exactly one root of $P$. This representation can arbitrarily refined with a simple bisection algorithm. Interval representations containing exactly one root of a univariate polynomial with rational coefficients can be obtained with an algorithm using Sturm sequences. There are several implementations for example in GiNacRA. If you still want radicial expression but a complete representation of polynomial roots in $\mathbb{Q}[X]$ you can use Galois theory to decide whether there is a radical expression, compute it and in the other cases use complete representations like the above.

-
Thanks. If I got you right, between $a$ and $b$ is exactly one root in $P$, so $(a,b,P)$ indeed references exactly one root. This is amazing. However, I think it does not let me do much computation with it, e.g. split a polynomial into factors, right? – Johannes Aug 27 '12 at 19:27
There algorithms for addition, multiplication and inverses of interval representations. Unfortunately, they have polynomial complexity which can be slow for this basic operations. See chapter 8 of Mishra's "Algorithmic Algebra" about real algebraic numbers. – joachim Aug 27 '12 at 21:28