Algebraic Numbers

Download this example as a Mathematica notebook.

The following sections give a high-level introduction to the way Mathematica handles algebraic numbers. It is not essential to understanding the Mathematica equation solvers but is included for interested readers. The text is adapted from a talk presented by Robert Knapp at the Japanese Society for Symbolic and Algebraic Computing.

For higher-order polynomials, it is not always possible to represent the exact solution in closed form. Currently, the highest polynomial that a closed-form solution has been found for is the fifth-order polynomial. However, the expression represents an exact mathematical quantity, which is based on the abstraction of algebraic numbers, represented in Mathematica as Root objects.

The method Mathematica uses internally to calculate roots of polynomials is the well-established Jenkins-Traub method. It works by finding successive roots with what is essentially a numerically stable variant of the Newton-Raphson method. Then, the polynomial is deflated by dividing out by a factor involving each root that is found. This is the engine behind algebraic numbers. Mathematical theorems, which allow roots to be isolated, and Mathematica's significance arithmetic make it possible to have an implicit representation that is reasonably efficient.

Let's take a closer look at the roots of a higher-order equation.

This gives the solution to the equation. This is given in terms of replacement rules so that you can see how the variables relate to the solution. In this case, it indicates that there are five possible solutions. In cases where you just want to work with the roots, you can extract them into a list.

A plot of the root positions in the complex plane as a function of the parameter value helps to visualize the numbers represented here implicitly. First, an auxiliary package is loaded in order to highlight the roots with different colors.

It is interesting to note that two roots come together on the real axis at the point Sigma = -1. The lines going across the plot are an artifact of the canonical order Mathematica gives to the roots. You may be asking how Mathematica distinguishes between and orders the roots. The process is an elegant example of numerical and symbolic mathematics working together. We will work with the last root to illustrate this. To make things a bit more convenient, we define the root as a function of the parameter.

When the parameter Sigma is given a numerical value, Mathematica does the computations necessary to determine an approximate root that is precise enough to be isolated from the other roots of the polynomial.

First, root approximations at machine precision are found using the Jenkins-Traub algorithm. The isolation is possible because, for a given root approximation, it is possible to find an enclosing circle in which an exact root of the polynomial is guaranteed to lie. Isolation makes sure that none of the circles around the approximate values overlap. Optionally, Mathematica allows you to use an exact root isolation algorithm that is more complicated and time consuming. When Sigma = 0, the roots are reasonably far apart from each other, so that 16 digits are sufficient to ensure isolation. Once the roots are isolated, they are ordered based on a canonical ordering. Real roots are ordered first along the real line; then complex ones based on complex absolute value are ordered. This is why you see the lines across the plot above at Sigma = -1. The pairs of roots switch to maintain the canonical ordering.

When Sigma = -1, the polynomial is reducible in terms of radicals. Mathematica recognizes this, so the polynomial is given in its simplest form.

However, for Sigma sightly greater than -1, the polynomial cannot be reduced, and so it is given in terms of a root object.

Notice that the polynomial is recalculated to be the minimal polynomial with integer coefficients. Internally, Mathematica recognizes that the two roots are very close together and adapts to using higher precision--in this case, 32 digits--to do the root isolation for these. Then, when you request a numerical value, the positive imaginary part is indicated correctly.

Hopefully this example has given you a rough idea of how the fusion of implicit representations with numerical approximations using adaptive precision yields a powerful computational tool. Mathematica provides a framework where objects like algebraic numbers fit naturally. You can similarly use Mathematica to set up implicit representations of your own objects by defining numeric and symbolic rules that apply to them. Implicit representations can be thought of, in some sense, as a transparent interface to a combination of powerful numerical algorithms and mathematical information--a tool that does not overburden a user with the implementation details.