Polynomials (Maxima 5.47post Manual)

14 Polynomials

Introduction to Polynomials
Functions and Variables for Polynomials
Introduction to algebraic extensions
Functions and Variables for algebraic extensions

14.1 Introduction to Polynomials

Polynomials are stored in Maxima either in General Form or as Canonical Rational Expressions (CRE) form. The latter is a standard form, and is used internally by operations such as factor, ratsimp, and so on.

Canonical Rational Expressions constitute a kind of representation which is especially suitable for expanded polynomials and rational functions (as well as for partially factored polynomials and rational functions when ratfac is set to true). In this CRE form an ordering of variables (from most to least main) is assumed for each expression.

Polynomials are represented recursively by a list consisting of the main variable followed by a series of pairs of expressions, one for each term of the polynomial. The first member of each pair is the exponent of the main variable in that term and the second member is the coefficient of that term which could be a number or a polynomial in another variable again represented in this form. Thus the principal part of the CRE form of 3*x^2-1 is (X 2 3 0 -1) and that of 2*x*y+x-3 is (Y 1 (X 1 2) 0 (X 1 1 0 -3)) assuming y is the main variable, and is (X 1 (Y 1 2 0 1) 0 -3) assuming x is the main variable. "Main"-ness is usually determined by reverse alphabetical order.

The "variables" of a CRE expression needn’t be atomic. In fact any subexpression whose main operator is not +, -, *, / or ^ with integer power will be considered a "variable" of the expression (in CRE form) in which it occurs. For example the CRE variables of the expression x+sin(x+1)+2*sqrt(x)+1 are x, sqrt(X), and sin(x+1). If the user does not specify an ordering of variables by using the ratvars function Maxima will choose an alphabetic one.

In general, CRE’s represent rational expressions, that is, ratios of polynomials, where the numerator and denominator have no common factors, and the denominator is positive. The internal form is essentially a pair of polynomials (the numerator and denominator) preceded by the variable ordering list. If an expression to be displayed is in CRE form or if it contains any subexpressions in CRE form, the symbol /R/ will follow the line label.

See the rat function for converting an expression to CRE form.

An extended CRE form is used for the representation of Taylor series. The notion of a rational expression is extended so that the exponents of the variables can be positive or negative rational numbers rather than just positive integers and the coefficients can themselves be rational expressions as described above rather than just polynomials. These are represented internally by a recursive polynomial form which is similar to and is a generalization of CRE form, but carries additional information such as the degree of truncation. As with CRE form, the symbol /T/ follows the line label of such expressions.

Categories: Polynomials · Rational expressions ·

14.2 Functions and Variables for Polynomials

Option variable: algebraic ¶

Default value: false

algebraic must be set to true in order for the simplification of algebraic integers to take effect.

Categories: Simplification flags and variables ·

Option variable: berlefact ¶

Default value: true

When berlefact is false then the Kronecker factoring algorithm will be used otherwise the Berlekamp algorithm, which is the default, will be used.

Categories: Polynomials ·

Function: bezout (p1, p2, x) ¶

an alternative to the resultant command. It returns a matrix. determinant of this matrix is the desired resultant.

Examples:

(%i1) bezout(a*x+b, c*x^2+d, x);
                         [ b c  - a d ]
(%o1)                    [            ]
                         [  a     b   ]
(%i2) determinant(%);
                            2      2
(%o2)                      a  d + b  c
(%i3) resultant(a*x+b, c*x^2+d, x);
                            2      2
(%o3)                      a  d + b  c

Categories: Polynomials ·

Function: bothcoef (expr, x) ¶

Returns a list whose first member is the coefficient of x in expr (as found by ratcoef if expr is in CRE form otherwise by coeff) and whose second member is the remaining part of expr. That is, [A, B] where expr = A*x + B.

Example:

(%i1) islinear (expr, x) := block ([c],
        c: bothcoef (rat (expr, x), x),
        is (freeof (x, c) and c[1] # 0))$
(%i2) islinear ((r^2 - (x - r)^2)/x, x);
(%o2)                         true

Categories: Polynomials ·

Function: coeff
coeff (expr, x, n)
coeff (expr, x) ¶

Returns the coefficient of x^n in expr, where expr is a polynomial or a monomial term in x. Other than ratcoef coeff is a strictly syntactical operation and will only find literal instances of x^n in the internal representation of expr.

coeff(expr, x^n) is equivalent to coeff(expr, x, n). coeff(expr, x, 0) returns the remainder of expr which is free of x. If omitted, n is assumed to be 1.

x may be a simple variable or a subscripted variable, or a subexpression of expr which comprises an operator and all of its arguments.

It may be possible to compute coefficients of expressions which are equivalent to expr by applying expand or factor. coeff itself does not apply expand or factor or any other function.

coeff distributes over lists, matrices, and equations.

14.3 Introduction to algebraic extensions

We assume here that the fields are of characteristic 0 so that irreductible polynomials have simple roots (are separable, thus square free). The base fields K of interest are the field Q of rational numbers, for algebraic numbers, and the fields of rational functions on the real numbers R or the complex numbers C, that is R(t) or C(t), when considering algebraic functions. An extension of degree n is defined by an irreducible degree n polynomial p(x) with coefficients in the base field, and consists of the quotient of the ring K[x] of polynomials by the multiples of p(x). So if p(x) = x^n + p_0 x^{n - 1} + ... + p_n, each time one encounters x^n one substitutes -(p_0 x^{n - 1} + ... + p_n). This is a field because of Bezout’s identity, and a vector space of dimension n over K spanned by 1, x, ..., x^{n - 1}. When K = C(t), this field can be identified with the field of algebraic functions on the algebraic curve of equation p(x, t) = 0.

In Maxima the process of taking rationals modulo p is obtained by the function tellrat when algebraic is true. The best way to ensure, in particular when considering the case where p depends on other variables that this simplification property is attached to x is to write (note the polynomial must be monic): tellrat(x^n = -(p_0*x^(n - 1) + ... + p_n)) where the p_i may depend on other variables. When one wants to remove this tellrat property one then has to write untellrat(x).

In the field K[x] one may do all sorts of algebraic computations, taking quotients, GCD of two elements, etc. by the same algorithms as in the usual case. In particular one can do factorization of polynomials on an extension, using the function algfac below. Moreover multiplication by an element f is a linear operation of the vector space K[x] over K and as such has a trace and a determinant. These are called algtrace and algnorm below. One can see that the trace of an element f(x) in K[x] is the sum of the values f(a) when a runs over roots of p and the norm is the product of the f(a). Both are symmetric in the roots of p and thus belong to K.

The field K[x] is also called the field obtained by adjoining a root a of p(x) to K. One can similarly adjoin a second root b of another polynomial obtaining a new extension K[a,b]. In fact there is a “prime element” c in K[a, b] such that K[a, b] = K[c]. This is obtained by function primeelmt below. Recursively one can thus adjoin any number of elements. In particular adjoining all the roots of p(x) to K one gets the splitting field of p, which is the smallest extension in which p completely splits in linear functions. The function splitfield constructs a primitive element of the splitting field, which in general is of very high degree.

The relevant concepts are explained in a concise and self-contained way in the small books edited by Dover: “Algebraic theory of numbers,” by Pierre Samuel, “Algebraic curves,” by Robert Walker, and the methods presented here are described in the article “Algebraic factoring and rational function integration” by B. Trager, Proceedings of the 1976 AMS Symposium on Symbolic and Algebraic Computation.

14.4 Functions and Variables for algebraic extensions

Function: algfac (f, p) ¶

Returns the factorization of f in the field K[a]. Does the same as factor(f, p) which in fact calls algfac. One can also specify the variable a as in algfac(f, p, a).

Examples:

(%i1) algfac(x^4 + 1, a^2 - 2);
                           2              2
(%o1)                    (x  - a x + 1) (x  + a x + 1)
(%i2) algfac(x^4 - t*x^2 + 1, a^2 - t - 2, a);
                           2              2
(%o2)                    (x  - a x + 1) (x  + a x + 1)

In the second example note that a = sqrt(2 + t).

Function: algnorm (f, p, a) ¶

Returns the norm of the polynomial f(a) in the extension obtained by a root a of polynomial p. The coefficients of f may depend on other variables.

Examples:

(%i1) algnorm(x*a^2 + y*a + z,a^2 - 2, a);
                            2              2      2
(%o1)/R/                   z  + 4 x z - 2 y  + 4 x

The norm is also the resultant of polynomials f and p, and the product of the differences of the roots of f and p.

Function: algtrace (f, p, a) ¶

Returns the trace of the polynomial f(a) in the extension obtained by a root a of polynomial p. The coefficients of f may depend on other variables which remain “inert”.

Example:

(%i1) algtrace(x*a^5 + y*a^3 + z + 1, a^2 + a + 1, a);
(%o1)/R/                       2 z + 2 y - x + 2

Function: bdiscr (args) ¶

Computes the discriminant of a basis x_i in K[a] as the determinant of the matrix of elements trace(x_i*x_j). The args are the elements of the basis followed by the minimal polynomial.

Example:

(%i1) bdiscr(1, x, x^2, x^3 - 2);
(%o1)/R/                             - 108
(%i2) poly_discriminant(x^3 - 2, x);
(%o2)                                - 108

A standard base in an extension of degree n is 1, x, ..., x^{n - 1}. In this case it is known that the discriminant of this base is the discriminant of the minimal polynomial. This is checked in (%o2) above.

Function: primelmt (f_b, p_a, c) ¶

Computes a prime element for the extension of K[a] by a root b of a polynomial f_b(b) whose coefficients may depend on a. One assumes that f_b is square free. The function returns an irreducible polynomial, a root of which generates K[a, b], and the expression of this primitive element in terms of a and b.

Examples:

(%i1) primelmt(b^2 - a*b - 1, a^2 - 2, c);
                              4       2
(%o1)                       [c  - 12 c  + 9, b + a]
(%i2) solve(b^2 - sqrt(2)*b - 1)[1];
                                  sqrt(6) - sqrt(2)
(%o2)                       b = - -----------------
                                          2
(%i3) primelmt(b^2 - 3, a^2 - 2, c);
                              4       2
(%o3)                       [c  - 10 c  + 1, b + a]
(%i4) factor(c^4 - 12*c^2 + 9, a^4 - 10*a^2 + 1);
                 3    2                       3    2
(%o4) ((4 c - 3 a  - a  + 27 a + 5) (4 c - 3 a  + a  + 27 a - 5)
                           3    2                       3    2
                 (4 c + 3 a  - a  - 27 a + 5) (4 c + 3 a  + a  - 27 a - 5))/256
(%i5) primelmt(b^3 - 3, a^2 - 2, c);
                   6      4      3       2
(%o5)            [c  - 6 c  - 6 c  + 12 c  - 36 c + 1, b + a]
(%i6) factor(b^3 - 3, %[1]);
            5       4        3        2
(%o6) ((48 c  + 27 c  - 320 c  - 468 c  + 124 c + 755 b - 1092)
           5        5         4       4          3        3          2        2
 ((- 48 b c ) - 54 c  - 27 b c  + 64 c  + 320 b c  + 360 c  + 468 b c  + 149 c
                           2
 - 124 b c - 1272 c + 755 b  + 1092 b + 1606))/570025

In (%o1), f_b depends on a. Using solve, the solution depends on sqrt(2) and sqrt(3). In (%o3), K[sqrt(2), sqrt(3)] is computed, and we see that the the primitive polynomial in (%o1) factorizes completely here. In (%i5), we compute K[sqrt(2), 3^{1/3}], and we see that b^3 - 3 gets one factor in this extension. If we assume this extension is real, the two other factors are complex.

Function: splitfield (p, x) ¶

Computes the splitting field of the polynomial p(x). In the generic case it is of degree n! in terms of the degree n of p, but may be of lower order if the Galois group of p is a strict subgroup of the group of permutations of n elements. The function returns a primitive polynomial for this extension and the expressions of the roots of p as polynomials of a root of this primitive polynomial. The polynomial f may be irreducible or factorizable.

Examples:

(%i1) splitfield(x^3 + x + 1, x);
                                              4         2
              6         4         2       alg1  + 5 alg1  - 9 alg1 + 4
(%o1)/R/ [alg1  + 6 alg1  + 9 alg1  + 31, ----------------------------, 
                                                       18
                                 4         2          4         2
                             alg1  + 5 alg1  + 4  alg1  + 5 alg1  + 9 alg1 + 4
                           - -------------------, ----------------------------]
                                      9                        18
(%i2) splitfield(x^4 + 10*x^2 - 96*x - 71, x)[1];
             8           6           5            4             3
(%o2)/R/ alg2  + 148 alg2  - 576 alg2  + 9814 alg2  - 42624 alg2
                                                    2
                                       + 502260 alg2  + 1109952 alg2 + 18860337

In the first case we have the primitive polynomial of degree 6 and the 3 roots of the third degree equations in terms of a variable alg1 produced by the system. In the second case the primitive polynomial is of degree 8 instead of 24, because the Galois group of the equation is reduced to D8 since there are relations between the roots.