doc/info/extensions.texi

   1 @node Introduction to algebraic extensions, Functions and Variables for algebraic extensions, Functions and Variables for Polynomials, Polynomials
   2 @section Introduction to algebraic extensions
   3
   4 We assume here that the fields are of characteristic 0 so that
   5 irreductible polynomials have simple roots (are separable, thus square
   6 free). The base fields K of interest are the field Q of rational
   7 numbers, for algebraic numbers, and the fields of rational functions on
   8 the real numbers R or the complex numbers C, that is R(t) or C(t), when
   9 considering algebraic functions. An extension of degree n is defined by
  10 an irreducible degree n polynomial p(x) with coefficients in the base
  11 field, and consists of the quotient of the ring K[x] of polynomials by
  12 the multiples of p(x). So if p(x)=x^n+p0*x^(n-1)+...+pn, each time one
  13 encounters x^n one substitutes -(p0*x^(n-1)+...+pn). This is a field
  14 because of Bezout's identity, and a vector space of dimension n over K
  15 spanned by 1,x,...,x^(n-1).  When K=C(t), this field can be identified
  16 to the field of algebraic functions on the algebraic curve of equation
  17 p(x,t)=0.
  18
  19 In Maxima the process of taking rationals modulo p is obtained by the
  20 function tellrat when @code{algebraic} is true. The best way to ensure,
  21 in particular when considering the case where p depends on other
  22 variables that this simplification property is attached to x is to write
  23 (note the polynomial must be monic):
  24 @code{tellrat(x^n=-(p0*x^(n-1)+...+pn))} where the pi may depend on
  25 other variables. When one wants to remove this tellrat property one then
  26 has to write @code{untellrat(x)}.
  27
  28
  29 In the field K[x] one may do all sorts of algebraic computations, taking
  30 quotients, gcd of 2 elements, etc. by the same algorithms as in the
  31 usual case.  In particular one can do factorization of polynomials on an
  32 extension, using the function @code{algfac} below.  Moreover
  33 multiplication by an element f is a linear operation of the vector space
  34 K[x] over K and as such has a trace and a determinant. These are called
  35 @code{algtrace} and @code{algnorm} below. One can see that the trace of
  36 an element f(x) in K[x] is the sum of the values f(a) when a runs over
  37 roots of p and the norm is the product of the f(a). Both are symmetric
  38 in the roots of p and thus belong to K.
  39
  40
  41 The field K[x] is also called the field obtained by adjoining a root a
  42 of p(x) to K. One can similarly adjoin a second root b of another
  43 polynomial obtaining a new extension K[a,b]. In fact there is a ``prime
  44 element'' c in K[a,b] such that K[a,b]=K[c]. This is obtained by
  45 function @code{primeelmt} below. Recursively one can thus adjoin any
  46 number of elements.  In particular adjoining all the roots of p(x) to K
  47 one gets the splitting field of p, which is the smallest extension in
  48 which p completely splits in linear functions. The function
  49 @code{splitfield} constructs a primitive element of the splitting field,
  50 which in general is of very high degree.
  51
  52 The relevant concepts are explained in a concise and self-contained way in the
  53 small books edited by Dover:
  54 Algebraic theory of numbers by Pierre Samuel
  55 Algebraic curves by  Robert Walker.
  56 and the methods presented here are described in the article
  57 ``Algebraic factoring and rational function integration'' by B. Trager
  58 Proceedings of the 1976 AMS symposium on symbolic and algebraic computation.
  59
  60 @node  Functions and Variables for algebraic extensions, , Introduction to algebraic extensions, Polynomials
  61 @section  Functions and Variables for algebraic extensions
  62
  63 @anchor{algfac}
  64 @deffn {Function} algfac(@var{f},@var{p})
  65
  66 Returns the factorization of f in the field K[a]. Does the same
  67 as @code{factor(f,p)} which in fact calls algfac. One can also
  68 specify the variable @var{a} as in @code{algfac(f,p,a)}.
  69
  70 @example
  71 (%i1) algfac(x^4+1,a^2-2);
  72                            2              2
  73 (%o1)                    (x  - a x + 1) (x  + a x + 1)
  74 (%i2) algfac(x^4-t*x^2+1,a^2-t-2,a);
  75                            2              2
  76 (%o2)                    (x  - a x + 1) (x  + a x + 1)
  77 @end example
  78
  79 In the second example note that @code{a=sqrt(2+t)}.
  80 @end deffn
  81
  82 @anchor{algnorm}
  83 @deffn {Function} algnorm(@var{f},@var{p},@var{a})
  84 Returns the norm of the polynomial @code{f(a)} in the extension
  85 obtained by a root @var{a} of polynomial @var{p}. The coefficients of
  86 @var{f} may depend on other variables.
  87
  88 @example
  89 (%i1) algnorm(x*a^2+y*a+z,a^2-2,a);
  90                             2              2      2
  91 (%o1)/R/                   z  + 4 x z - 2 y  + 4 x
  92 @end example
  93
  94 The norm is also the resultant of polynomials f and p, and the product
  95 of the differences of the roots of f and p.
  96 @end deffn
  97
  98
  99 @anchor{algtrace}
 100 @deffn {Function} algtrace(@var{f},@var{p},@var{a})
 101 Returns the trace of the polynomial @code{f(a)} in the extension
 102 obtained by a root @var{a} of polynomial @var{p}. The coefficients of
 103 @var{f} may depend on other variables which remain ``inert''.
 104
 105 @example
 106 (%i1) algtrace(x*a^5+y*a^3+z+1,a^2+a+1,a);
 107 (%o1)/R/                       2 z + 2 y - x + 2
 108 @end example
 109 @end deffn
 110
 111 @anchor{bdiscr}
 112 @deffn {Function} bdiscr(@var{args})
 113 Computes the discriminant of a basis @code{x_i} in @code{K[a]} as
 114 the determinant of the matrix of elements @code{trace(x_i*x_j)}.
 115 The args are the elements of the basis followed by the minimal
 116 polynomial.
 117 @example
 118 (%i1) bdiscr(1,x,x^2,x^3-2);
 119 (%o1)/R/                             - 108
 120 (%i2) poly_discriminant(x^3-2,x);
 121 (%o2)                                - 108
 122 @end example
 123 A standard base in an extension of degree n is @code{1,x,...,x^(n-1)}.
 124 In this case it is known that the discriminant of this base is the discriminant
 125 of the minimal polynomial. This is checked in (%o2)
 126
 127 @end deffn
 128
 129
 130 @anchor{primelmt}
 131 @deffn {Function} primelmt(@var{f_b},@var{p_a},@var{c})
 132 Computes a prime element for the extension of @code{K[a]} by a root
 133 @var{b} of a polynomial @code{f_b(b)} whose coefficients may depend on
 134 @var{a}. One assumes that @var{f_b} is square free. The function returns
 135 an irreducible polynomial, a root of which generates @code{K[a,b]}, and
 136 the expression of this primitive element in terms of @var{a} and
 137 @var{b}
 138
 139 @example
 140 (%i1) primelmt(b^2-a*b-1,a^2-2,c);
 141                               4       2
 142 (%o1)                       [c  - 12 c  + 9, b + a]
 143 (%i2) solve(b^2-sqrt(2)*b-1)[1];
 144                                   sqrt(6) - sqrt(2)
 145 (%o2)                       b = - -----------------
 146                                           2
 147 (%i3) primelmt(b^2-3,a^2-2,c);
 148                               4       2
 149 (%o3)                       [c  - 10 c  + 1, b + a]
 150 (%i4) factor(c^4-12*c^2+9,a^4-10*a^2+1);
 151                  3    2                       3    2
 152 (%o4) ((4 c - 3 a  - a  + 27 a + 5) (4 c - 3 a  + a  + 27 a - 5)
 153                            3    2                       3    2
 154                  (4 c + 3 a  - a  - 27 a + 5) (4 c + 3 a  + a  - 27 a - 5))/256
 155 (%i5) primelmt(b^3-3,a^2-2,c);
 156                    6      4      3       2
 157 (%o5)            [c  - 6 c  - 6 c  + 12 c  - 36 c + 1, b + a]
 158 (%i6) factor(b^3-3,%[1]);
 159             5       4        3        2
 160 (%o6) ((48 c  + 27 c  - 320 c  - 468 c  + 124 c + 755 b - 1092)
 161            5        5         4       4          3        3          2        2
 162  ((- 48 b c ) - 54 c  - 27 b c  + 64 c  + 320 b c  + 360 c  + 468 b c  + 149 c
 163                            2
 164  - 124 b c - 1272 c + 755 b  + 1092 b + 1606))/570025
 165 @end example
 166 In (%1) f_b depends on a. Using solve, the solution depends on sqrt(2) and sqrt(3).
 167 In (%o3) K[sqrt(2),sqrt(3)] is computed and we see that the the primitive polynomial
 168 in (%o1) factorizes completely here. In (%i5) we compute K[sqrt(2),3^(1/3)] and we see
 169 that b^3-3 gets one factor in this extension. If we assume this extension is real,
 170 the two other factors are complex.
 171
 172 @end deffn
 173
 174 @anchor{splitfield}
 175 @deffn {Function} splitfield(@var{p},@var{x})
 176 Computes the splitting field of the polynomial @code{p(x)}.
 177 In the generic case it is of degree @code{n!} in terms of the degree
 178 of @var{p}, but may be of lower order if the Galois group of @var{p}
 179 is a strict subgroup of the group of permutations of @var{n}
 180 elements. The function returns a primitive polynomial for this extension
 181 and the expressions of the roots of @var{p} as polynomials of a root
 182 of this primitive polynomial. The polynomial @var{f} may be
 183 irreducible or factorizable.
 184
 185 @example
 186 (%i1) splitfield(x^3+x+1,x);
 187                                               4         2
 188               6         4         2       alg1  + 5 alg1  - 9 alg1 + 4
 189 (%o1)/R/ [alg1  + 6 alg1  + 9 alg1  + 31, ----------------------------,
 190                                                        18
 191                                  4         2          4         2
 192                              alg1  + 5 alg1  + 4  alg1  + 5 alg1  + 9 alg1 + 4
 193                            - -------------------, ----------------------------]
 194                                       9                        18
 195 (%i2) splitfield(x^4+10*x^2-96*x-71,x)[1];
 196              8           6           5            4             3
 197 (%o2)/R/ alg2  + 148 alg2  - 576 alg2  + 9814 alg2  - 42624 alg2
 198                                                     2
 199                                        + 502260 alg2  + 1109952 alg2 + 18860337
 200 @end example
 201
 202 In the first case we have the primitive polynomial of degree 6 and the 3 roots
 203 of the third degree equations in terms of a variable @var{alg1} produced by
 204 the system. In the second case the primitive polynomial is of degree 8
 205 instead of 24, because the Galois group of the equation is reduced to D8
 206 since there are relations between the roots.
 207
 208 @end deffn