Check-ins Using Download Hex

Artifact 2a06a838d2aa77122faf2bd010ef23a024bd5997e3ef1571de074a039a5d2412:

\documentstyle[11pt]{article}
\begin{document}

\title{ALGEBRAIC NUMBER FIELDS}
\author{
Eberhard Schr\"{u}fer \\
GMD, Institut F1   \\
Postfach 1240      \\
5205 St. Augustin  \\
West Germany       \\
                   \\
Email: schrufer@gmdzi.gmd.de \\
}

\maketitle

Algebraic numbers are the solutions of an irreducible polynomial over some
ground domain.  The algebraic number {\bf i} (imaginary unit), for example,
would be defined by the polynomial $i^2 + 1$.  The arithmetic of algebraic
number $s$ can be viewed as a polynomial arithmetic modulo the defining
polynomial.

Given a defining polynomial for an algebraic number {\bf a}
\begin{eqnarray*}
a^n ~ + ~ {p _{n-1}} {a ^ {n -1}} ~ + ~ ... ~ + ~ {p_0}
\end{eqnarray*}

All algebraic numbers which can be built up from $a$ are then of the form:
\begin{eqnarray*}
{r_{n-1}} {a ^{n-1}} ~+~ {r_{n-2}} {a ^{n-2}} ~+~ ... ~+~ {r_0}
\end{eqnarray*}
where the $r_j$'s are rational numbers.

The operation of addition is defined by
\begin{eqnarray*}
({r_{n-1}} {a ^{n-1}} ~+~ {r_{n-2}} {a ^{n-2}} ~+~ ...) ~ + ~
({s_{n-1}} {a ^{n-1}} ~+~ {s_{n-2}} {a ^{n-2}} ~+~ ...) ~ =  \\
({r_{n-1}+s_{n-1}}) {a ^{n-1}} ~+~ ({r_{n-2}+s_{n-2}}) {a ^{n-2}} ~+~ ...
\end{eqnarray*}

Multiplication of two algebraic numbers can be performed by normal
polynomial multiplication followed by a reduction of the result with the
help of the defining polynomial.

\begin{eqnarray*}
({r_{n-1}} {a ^{n-1}} ~+~ {r_{n-2}} {a ^{n-2}} ~+~ ...) ~ \times ~
({s_{n-1}} {a ^{n-1}} ~+~ {s_{n-2}} {a ^{n-2}} ~+~ ...) = \\
 {r_{n-1}} {s ^{n-1}}{a^{2n-2}} ~+~  ... ~ {\bf modulo} ~ 
a^n ~ + ~ {p _{n-1}} {a ^ {n -1}} ~ + ~ ... ~ + ~ {p_0} \\
= ~~~{q_{n-1}} a^{n-1} ~ + ~ {q _{n-2}} {a ^ {n -2}} ~ + ~ ...
\end{eqnarray*}


Division of two algebraic numbers r and s yields another algebraic number q.
$ r/s = q$ or $ r = q s $.

The last equation written out explicitly reads

\begin{eqnarray*}
({r_{n-1}} {a ^{n-1}} ~+~ {r_{n-2}} {a ^{n-2}} ~+~ ...) ~~~ =  \\
({q_{n-1}} {a ^{n-1}} ~+~ {q_{n-2}} {a ^{n-2}} ~+~ ...) ~ \times ~
({s_{n-1}} {a ^{n-1}} ~+~ {s_{n-2}} {a ^{n-2}} ~+~ ...) \\
a^n ~ + ~ {p _{n-1}} {a ^ {n -1}} ~ + ~ ... ~ + ~ {p_0} ~~~ = \\
({t_{n-1}} {a ^{n-1}} ~+~ {t_{n-2}} {a ^{n-2}} ~+~ ...) 
\end{eqnarray*}

The $t_i$ are linear in the $q_j$.  Equating equal powers of {\bf a} yields a
linear system for the quotient coefficients $q_j$.

With this, all field operations for the algebraic numbers are available.
The translation into algorithms is straightforward.  For an implementation
we have to decide on a data structure for an algebraic number.  We have
chosen the representation REDUCE normally uses for polynomials, the so-called standard form.  Since our polynomials have in general rational 
coefficients, we must allow for a rational number domain inside the
algebraic number.

\begin{verbatim}
<algebraic number> ::= :ar: . <univariate poly over the rationals>

<univariate poly over the rationals> ::= <variable> .** <ldeg> .*
                                         <rational> .+ <reductum>

<ldeg> ::= integer

<rational> ::= :rn: . <integer numerator . integer denominator> 
			   : integer

<reductum> ::= <univariate polynomial> : <rational> : nil
\end{verbatim}

This representation allows us to use the REDUCE functions for adding and
multiplying polynomials on the tail of the tagged algebraic number.  Also,
the routines for solving linear equations can easily be used for the
calculation of quotients.  We are still left with the problem of
introducing a particular algebraic number.  In the current version this is
done by giving the defining polynomial to the statement {\bf defpoly}.  The
algebraic number sqrt(2), for example, can be introduced by
\begin{verbatim}
   defpoly sqrt2**2 - 2;
\end{verbatim}

This statement associates a simplification function for the
translation of the variable in the defining polynomial into its tagged
internal form and also generates a power reduction rule used by the
operations {\bf times} and {\bf quotient} for the reduction of their
result modulo the defining polynomial.  A basis for the representation
of an algebraic number is also set up by the statement.  In the
working version, the basis is a list of powers of the indeterminate of
the defining polynomial up to one less then its degree.  Experiments
with integral bases, however, have been very encouraging, and these
bases might be available in a later version.  If the defining
polynomial is not monic, it will be made so by an appropriate
substitution.

Examples:
\begin{verbatim}
     defpoly sqrt2**2-2;

     1/(sqrt2+1);

     SQRT2 - 1

     (x**2+2*sqrt2*x+2)/(x+sqrt2);

     X + SQRT2

     on gcd;

     (x**3+(sqrt2-2)*x**2-(2*sqrt2+3)*x-3*sqrt2)/(x**2-2);

       2
     (X  - 2*X - 3)/(X - SQRT2)

     off gcd;

     sqrt(x**2-2*sqrt2*x*y+2*y**2);

     X - SQRT2*Y
\end{verbatim}

Until now we have dealt with only a single algebraic number.  In practice
this is not sufficient as very often several algebraic numbers appear in an
expression.  There are two possibilities for handling this: one can use
multivariate extensions \cite{Davenport:81} or one can construct a defining
polynomial that contains all specified extensions.  This package implements
the latter case (the so called primitive representation).  The algorithm we
use for the construction of the primitive element is the same as given by
Trager \cite{Trager:76}.  In the implementation, multiple extensions can be
given as a list of equations to the statement {\bf defpoly}, which, among other
things, adds the new extension to the previously defined one.  All
algebraic numbers are then expressed in terms of the primitive element.

Example:

\begin{verbatim}
   defpoly sqrt2**2-2,cbrt5**3-5;

   *** defining polynomial for primitive element:

     6       4        3        2
   A1  - 6*A1  - 10*A1  + 12*A1  - 60*A1 + 17

   sqrt2;

         5             4              3              2
   48/1187*A1  + 45/1187*A1  - 320/1187*A1  - 780/1187*A1  +


   735/1187*A1 - 1820/1187

   sqrt2**2;

   2
\end{verbatim}

We can provide factorization of polynomials over the algebraic number
domain by using Trager's algorithm.  The polynomial to be factored is first
mapped to a polynomial over the integers by computing the norm of the
polynomial, which is the resultant with respect to the primitive element of
the polynomial and the defining polynomial.  After factoring over the
integers, the factors over the algebraic number field are recovered by GCD
calculations.

Example:
\begin{verbatim}
   defpoly a**2-5;

   x**2 + x - 1;

   (X + (1/2*A + 1/2))*(X - (1/2*A - 1/2))
\end{verbatim}
We have also incorporated a function {\bf split\_field} for the calculation of a
primitive element of minimal degree for which a given polynomial splits
into linear factors.  The algorithm as described in Trager's article is
essentially a repeated primitive element calculation.

Example:

\begin{verbatim}
    split!_field(x**3-3*x+7);

   *** Splitting field is generated by:

     6        4        2
   A5  - 18*A5  + 81*A5  + 1215



       4          2
   {1/126*A5  - 5/42*A5  - 1/2*A5 + 2/7,


          4          2
    - (1/63*A5  - 5/21*A5  + 4/7),


       4          2
   1/126*A5  - 5/42*A5  + 1/2*A5 + 2/7}


   for each j in ws product (x-j);

    3
   X  - 3*X + 7
\end{verbatim}

A more complete description can be found in \cite{Bradford:86}.

\begin{thebibliography}{9}

\bibitem{Bradford:86} R.~J.~Bradford, A.~C.~Hearn, J.~A.~Padget and
E.~Schr{\"u}fer, {\em Enlarging the REDUCE Domain of Computation},
Proceedings of SYMSAC '86, (1986), pp100-106.

\bibitem{Trager:76} B.~M.~Trager, {\em Algebraic Factoring and
Rational Function Integration}, Proceedings of SYMSAC '76, (1976) pp196-208.

\bibitem{Davenport:81} James Harold Davenport, {\bf On the Integration
of Algebraic Functions}, Lecture Notes in Computer Science,
\underline{102}, (1981).

\end{thebibliography}

\end{document}
REDUCE Historical
[ REDUCE Sourceforge Project | Historical SVN Repository | GitHub Mirror | SourceHut Mirror | NotABug Mirror | Chisel Mirror | Chisel RSS ]