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