Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
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
4  
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 Speyer Aug 13 '12 at 14:22
1  
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
add comment

1 Answer

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.

share|improve this answer
    
Thanks, I'll try some examples like this by myself and see where I get. –  Dario Aug 14 '12 at 8:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.