# How can I work with (i.e. add, multiply) algebraic numbers in practice?

I know that the real algebraic numbers $\mathbb A \subset \mathbb R$ form a field. I've seen this as a more theoretical result, but it's also seems nice idea to implement algebraic numbers for the computer in order to make computations more exact.

Now I wonder how could this be done? I thought of representing an algebraic number $\alpha$ as a tuple $(P,(a,b)) \in \mathbb Q[T]\times \mathbb Q^2$ such that $\alpha$ is the unique root of $P$ in $[a,b]$.

Now take for example the numbers

• $\varphi = (T^2-T-1,(\frac 3 2,2))$
• $\sqrt 2 = (T^2-2,(1,2))$

But how can I actually perform computations on this numbers?

Surely $\varphi + \sqrt 2$ lies in $(\frac 5 2, 4)$, but what polynomial's root is it? What about $\varphi \cdot \sqrt 2$? In general, given polynomials $P,Q \in \mathbb Q[T]$ with $P(x)=Q(y)=0$, how do I find some polynomial $S$ such that $S(x+y)=0$?

• I don't remember the method (or even whether or not have I seen a concrete one), but I'm pretty sure that the degree of the polynomial will grow exponentially as you perform operations on algebraic numbers represented that way, so I don't think it would be a good representation to be used by a computer... – tomasz Aug 13 '12 at 13:08
• This is a large and complicated subject. If you want to do a small number of easy computations, Mathematica and Sage (and probably all other computer algebra systems, but those are the ones I know) have routines to do this for you. If you want to understand the underlying theory, see Sasha's answer. If you want to do large examples, or write a library for doing this sort of computation, see Henri Cohen's book "A Course In Computational Algebraic Number Theory". – David E Speyer Aug 13 '12 at 14:22
• Some useful keywords here are "Kronecker sum" and "Kronecker product." – Qiaochu Yuan Aug 13 '12 at 15:58
• The problem of finding a polynomial vanishing at the sum, or the product, of two algebraic numbers got some very nice answers two months ago at math.stackexchange.com/questions/155122/… – Gerry Myerson Aug 14 '12 at 3:56

Suppose $\alpha$ is a root of polynomial $P(x)$ of degree $n$, and $\beta$ is a root of polynomial $Q(y)$ of degree $m$ with coefficients in $\mathbb{Q}$. Using $P(x)$ every power of $\alpha$ can be reduced to a linear combination of $\{1, \alpha, \alpha^2, \ldots, \alpha^{n-1}\}$, similarly every power of $\beta$, modulo $Q(y)$ is a linear combination of $\{1,\beta, \ldots, \beta^{m-1}\}$. Coefficients in these linear combinations are rational numbers.
Consider $\omega = \alpha + \beta$. We can constructively prove that this number is algebraic. Using reductions of powers of $\alpha$ and $\beta$ we can represent any power of $\omega$ as $\sum_{p=0}^{n-1} \sum_{q=0}^{m-1} c_{p,q}\alpha^p \beta^q$, with $c_{p,q} \in \mathbb{Q}$. Thus powes of $\omega$ are mapped into $\mathbb{Q}^{m \cdot n}$, and therefore there will exist coefficients $\{a_0, a_1, \ldots, a_{m \cdot n}\} \in \mathbb{Q}$ such that $$a_0 +a_1 \omega + \cdots + \omega^{m \cdot n} a_{m \cdot n} = 0$$
Example: For $\phi$, polynomial is $P(T) = T^2-T-1$ and for $\sqrt{2}$ the polynomial is $Q(T) = T^2 - 2$. Thus, using basis $\{1, \phi, \sqrt{2}, \phi \sqrt{2}\}$: $$\begin{eqnarray} 1 &=& 1 \cdot 1 + 0 \cdot \phi + 0 \cdot \sqrt{2} + 0 \cdot \phi \sqrt{2} \\ \phi+\sqrt{2} &=& 0 \cdot 1 + 1 \cdot \phi + 1 \cdot \sqrt{2} + 0 \cdot \phi \sqrt{2} \\ \left(\phi+\sqrt{2}\right)^2 &=& 3 \cdot 1 + 1 \cdot \phi + 0 \cdot \sqrt{2} + 2 \cdot \phi \sqrt{2} \\ \left(\phi+\sqrt{2}\right)^3 &=& 1 \cdot 1 + 8 \cdot \phi + 5 \cdot \sqrt{2} + 3 \cdot \phi \sqrt{2} \\ \left(\phi+\sqrt{2}\right)^4 &=& 18 \cdot 1 + 15 \cdot \phi + 4 \cdot \sqrt{2} + 16 \cdot \phi \sqrt{2} \end{eqnarray}$$ Solving the null space problem, we find that $\phi + \sqrt{2}$ is a zero of $$z^4 -2 z^3 - 5 z^2 + 6z -1 = 0$$
Similarly, one can establish the polynomial whose root is $\phi \cdot \sqrt{2}$, which is $z^4 - 6 z^2 + 4$. In Mathematica, one can use MinimalPolynomial (online ref-page) to do these computations.