6.1 Algebraic Numbers

How concisely can we specify an algebraic number? Since every equation in one variable with complex coefficients can be solved completely with complex numbers as solutions (Gauss's Fundamental theorem of algebra), one way to specify an algebraic number is to specify it as a complex number. However, a real (or complex) number is (in general) only specified by its entire decimal expansion which cannot be stored in a finite space. On the other hand it is enough to specify an algorithm that produces, on sufficient iteration, an arbitrarily close approximation to the complex number that represents it.

Thus, one way to specify an algebraic number $\alpha$ is as follows. First we give P(t) which is the non-zero polynomial (with rational or integer coefficients) of least degree such that P($\alpha$) = 0 (by Euclidean division applied to polynomials it follows that P divides any other Q for which Q($\alpha$) = 0). Further, we need to specify a number x₀ of the form r + s ^. $\sqrt{-1}$ with r and s rational so that successive iterations of Newton's method

x_{k + 1} = x_k - $${\frac{P(x_k)}{P'(x_k)}}$$

(where P'(T) denotes the (entirely formal) derivative of P(T) with respect to T) converge to the complex number representing $\alpha$. There is some (minor) ambiguity in this due the to the ``choice'' of $\sqrt{-1}$ (which we cannot ``specify'' by this method). To quote Abhyankar ``which is i and which - i, perhaps only a physicist can tell!''

Another way is to make use of Hensel's lemma. We will define below the discriminant D_P for a polynomial P. For now it suffices that if a prime p does not divide D_P then for any n so that p divides P(n), we have that p does not divide P'(n). In other words D_P is the least common multiple of gcd(P(n), P'(n)) as n varies over all integers. Now, for n sufficiently large it is clear that there is such a prime p (i. e. not dividing D_P) so that p divides P(n). We can now specify $\alpha$ by saying that is should be congruent to n modulo p. Because of Hensel's lemma (which is Newton's iteration done modulo powers of p!) we can then produce n_k so that $\alpha$ - n_k is divisible by p^k for every k. In modern language, we are replacing the approximation by complex numbers given above by a p-adic approximation. We can actually, find a suitable p so that this can be done for all roots of the polynomial P. (This is a particular case of Chebychev's density theorem).

An entirely less obvious problem is how we can perform common arithmetic operations on algebraic numbers when they are represented in this fashion. For that reason, and for the reason mentioned at the beginning of this section we now turn to the matrix representation of algebraic numbers.