19 Polynomials

Let R be a commutative ring-with-one. A (univariate) Laurent polynomial over R is a sequence (..., c_{-1}, c_0, c_1, ...) of elements of R such that only finitely many are non-zero. For a ring element r of R and polynomials f = (..., f_{-1}, f_0, f_1, ...) and g = (..., g_{-1}, g_0, g_1, ...) we define f + g = (..., f_{-1} + g_{-1}, f_0+g_0, f_1+g_1, ...) , rcdot f = (..., r f_{-1}, r f_0, r f_1, ...), and f * g = (..., s_{-1}, s_0, s_1, ...), where s_k = ... + f_i g_{k-i} + .... Note that s_k is well-defined as only finitely many f_i and g_i are non-zero. We call the largest integers d(f), such that f_{d(f)} is non-zero, the degree of f, f_i the i.th coefficient of f, and f_{d(f)} the leading coefficient of f. If the smallest integer v(f), such that f_{v(f)} is non-zero, is negative, we say that f has a pole of order v at 0, otherwise we say that f has a root of order v at 0. We call R the base (or coefficient) ring of f. If f = (..., 0, 0, 0, ...) we set d(f) = -1 and v(f) = 0.

The set of all Laurent polynomials L(R) over a ring R together with above definitions of + and * is again a ring, the Laurent polynomial ring over R, and R is called the base ring of L(R). The subset of all polynomials f with non-negative v(f) forms a subring P(R) of L(R), the polynomial ring over R. If R is indeed a field then both rings L(R) and P(R) are Euclidean. Note that L(R) and P(R) have different Euclidean degree functions. If f is an element of P(R) then the Euclidean degree of f is simply the degree of f. If f is viewed as an element of L(R) then the Euclidean degree is the difference between d(f) and v(f). The units of P(R) are just the units of R, while the units of L(R) are the polynomials f such that v(f) = d(f) and f_{d(f)} is a unit in R.

GAP uses the above definition of polynomials. This definition has some advantages and some drawbacks. First of all, the polynomial (..., x_0 = 0, x_1 = 1, x_2 = 0, ...) is commonly denoted by x and is called an indeterminate over R, (..., c_{-1}, c_0, c_1, ...) is written as ... + c_{-1} x^{-1} + c_0 + c_1 x + c_2 x^2 + ..., and P(R) as R[x] (note that the way GAP outputs a polynomial resembles this definition). But if we introduce a second indeterminate y it is not obvious whether the product xy lies in (R[x])[y], the polynomial ring in y over the polynomial ring in x, in (R[y])[x], in R[x,y], the polynomial ring in two indeterminates, or in R[y,x] (which should be equal to R[x,y]). Using the first definition we would define y as indeterminate over R[x] and we know then that xy lies in (R[x])[y].

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> Rx := LaurentPolynomialRing(Rationals);;
    gap> y := Indeterminate(Rx);; y.name := "y";;
    gap> y^2 + x;
    y^2 + (x)
    gap> last^2;
    y^4 + (2*x)*y^2 + (x^2)
    gap> last + x;
    y^4 + (2*x)*y^2 + (x^2 + x)
    gap> (x^2 + x + 1) * y^2 + y + 1;
    (x^2 + x + 1)*y^2 + y + (x^0)
    gap> x * y;
    (x)*y
    gap> y * x;
    (x)*y
    gap> 2 * x;
    2*x
    gap> x * 2;
    2*x 

Note that GAP does not embed the base ring of a polynomial into the polynomial ring. The trivial polynomial and the zero of the base ring are always different.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> Rx := LaurentPolynomialRing(Rationals);;
    gap> y := Indeterminate(Rx);; y.name := "y";;
    gap> 0 = 0*x;
    false
    gap> nx := 0*x;     # a polynomial over the rationals
    0*x^0
    gap> ny := 0*y;     # a polynomial over a polynomial ring
    0*y^0
    gap> nx = ny;       # different base rings
    false 

The result 0*x neq 0*y is probably not what you expect or want. In order to compute with two indeterminates over R you must embed x into R[x][y].

    gap> x  := Indeterminate(Rationals);; x.name := "x";;
    gap> Rx := LaurentPolynomialRing(Rationals);;
    gap> y  := Indeterminate(Rx);; y.name := "y";;
    gap> x  := x * y^0;                                  
    x*y^0
    gap> 0*x = 0*y;
    true 

The other point which might be startling is that we require the supply of a base ring for a polynomial. But this guarantees that Factor gives a predictable result.

    gap> f5 := GF(5);; f5.name := "f5";;
    gap> f25 := GF(25);; f25.name := "f25";;
    gap> Polynomial( f5, [3,2,1]*Z(5)^0 ); 
    Z(5)^0*(X(f5)^2 + 2*X(f5) + 3)
    gap> Factors(last);
    [ Z(5)^0*(X(f5)^2 + 2*X(f5) + 3) ]
    gap> Polynomial( f25, [3,2,1]*Z(5)^0 );
    X(f25)^2 + Z(5)*X(f25) + Z(5)^3
    gap> Factors(last);
    [ X(f25) + Z(5^2)^7, X(f25) + Z(5^2)^11 ]

The first sections describe how polynomials are constructed (see Indeterminate, Polynomial, and IsPolynomial).

The next sections describe the operations applicable to polynomials (see Comparisons of Polynomials and Operations for Polynomials).

The next sections describe the functions for polynomials (see Degree, Derivative and Value).

The next sections describe functions that construct certain polynomials (see ConwayPolynomial, CyclotomicPolynomial).

The next sections describe the functions for constructing the Laurent polynomial ring L(R) and the polynomial ring P(R) (see PolynomialRing and LaurentPolynomialRing).

The next sections describe the ring functions applicable to Laurent Ring Functions for Laurent Polynomial Rings).

Subsections

  1. Multivariate Polynomials
  2. Indeterminate
  3. Polynomial
  4. IsPolynomial
  5. Comparisons of Polynomials
  6. Operations for Polynomials
  7. Degree
  8. LeadingCoefficient
  9. Value
  10. Derivative
  11. InterpolatedPolynomial
  12. ConwayPolynomial
  13. CyclotomicPolynomial
  14. PolynomialRing
  15. IsPolynomialRing
  16. LaurentPolynomialRing
  17. IsLaurentPolynomialRing
  18. Ring Functions for Polynomial Rings
  19. Ring Functions for Laurent Polynomial Rings

19.1 Multivariate Polynomials

As explained above, each ring R has exactly one indeterminate associated with R. In order to construct a polynomial ring with two indeterminates over R you must first construct the polynomial ring P(R) and then the polynomial ring over P(R).

    gap> x  := Indeterminate(Integers);; x.name := "x";;
    gap> Rx := PolynomialRing(Integers);;
    gap> y  := Indeterminate(Rx);; y.name := "y";;
    gap> x  := y^0 * x;
    x*y^0
    gap> f := x^2*y^2 + 3*x*y + x + 4*y;
    (x^2)*y^2 + (3*x + 4)*y + (x)
    gap> Value( f, 4 );
    16*x^2 + 13*x + 16
    gap> Value( last, -2 );
    54
    gap> (-2)^2 * 4^2 + 3*(-2)*4 + (-2) + 4*4;
    54 

We plan to add support for (proper) multivariate polynomials in one of the next releases of GAP.

19.2 Indeterminate

Indeterminate( R )
X( R )

Indeterminate returns the polynomial (..., x_0 = 0, x_1 = 1, x_2 = 0, ...) over R, which must be a commutative ring-with-one or a field.

Note that you can assign a name to the indeterminate, in which case all polynomials over R are printed using this name. Keep in mind that for each ring there is exactly one indeterminate.

    gap> x := Indeterminate( Integers );; x.name := "x";;
    gap> f := x^10 + 3*x - x^-1;        
    x^10 + 3*x - x^(-1)
    gap> y := Indeterminate( Integers );;    # this is 'x'
    gap> y.name := "y";;
    gap> f;    # so 'f' is also printed differently from now on
    y^10 + 3*y - y^(-1)

19.3 Polynomial

Polynomial( R, l )
Polynomial( R, l, v )

l must be a list of coefficients of the polynomial f to be constructed, namely (..., f_<v> = <l>[1], f_{<v>+1} = <l>[2], ...) over R, which must be a commutative ring-with-one or a field. The default for v is 0. Polynomial returns this polynomial f.

For interactive calculation it might by easier to construct the indeterminate over R and construct the polynomial using ^, + and *.

    gap> x := Indeterminate( Integers );;
    gap> x.name := "x";;
    gap> f := Polynomial( Integers, [1,2,0,0,4] );
    4*x^4 + 2*x + 1
    gap> g := 4*x^4 + 2*x + 1;
    4*x^4 + 2*x + 1 

19.4 IsPolynomial

IsPolynomial( obj ) IsPolynomial returns true if obj, which can be an object of arbitrary type, is a polynomial and false otherwise. The function will signal an error if obj is an unbound variable.

    gap> IsPolynomial( 1 );
    false
    gap> IsPolynomial( Indeterminate(Integers) );
    true

19.5 Comparisons of Polynomials

f = g
f < g

The equality operator = evaluates to true if the polynomials f and g are equal, and to false otherwise. The inequality operator < evaluates to true if the polynomials f and g are not equal, and to false otherwise.

Note that polynomials are equal if and only if their coefficients and their base rings are equal. Polynomials can also be compared with objects of other types. Of course they are never equal.

    gap> f := Polynomial( GF(5^3), [1,2,3]*Z(5)^0 );
    Z(5)^3*X(GF(5^3))^2 + Z(5)*X(GF(5^3)) + Z(5)^0
    gap> x := Indeterminate(GF(25));;
    gap> g := 3*x^2 + 2*x + 1;
    Z(5)^3*X(GF(5^2))^2 + Z(5)*X(GF(5^2)) + Z(5)^0
    gap> f = g;
    false
    gap> x^0 = Z(25)^0;
    false

f < g
f <= g
f g
f = g

The operators <, <=, , and = evaluate to true if the polynomial f is less than, less than or equal to, greater than, or greater than or equal to the polynomial g, and to false otherwise.

A polynomial f is less than g if v(<f>) is less than v(<g>), or if v(<f>) and v(<g>) are equal and d(<f>) is less than d(<g>). If v(<f>) is equal to v(<g>) and d(<f>) is equal to d(<g>) the coefficient lists of f and g are compared.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> (1 + x^2 + x^3)*x^3 < (2 + x^2 + x^3);
    false
    gap> (1 + x^2 + x^4) < (2 + x^2 + x^3);    
    false
    gap> (1 + x^2 + x^3) < (2 + x^2 + x^3);
    true

19.6 Operations for Polynomials

The following operations are always available for polynomials. The operands must have a common base ring, no implicit conversions are performed.

f + g

The operator + evaluates to the sum of the polynomials f and g, which must be polynomials over a common base ring.

    gap> f := Polynomial( GF(2), [Z(2), Z(2)] );
    Z(2)^0*(X(GF(2)) + 1)
    gap> f + f;
    0*X(GF(2))^0
    gap> g := Polynomial( GF(4), [Z(2), Z(2)] );
    X(GF(2^2)) + Z(2)^0
    gap> f + g;
    Error, polynomials must have the same ring

f + scl
scl + f

The operator + evaluates to the sum of the polynomial f and the scalar scl, which must lie in the base ring of f.

    gap> x := Indeterminate( Integers );; x.name := "x";;
    gap> h := Polynomial( Integers, [1,2,3,4] );
    4*x^3 + 3*x^2 + 2*x + 1
    gap> h + 1;
    4*x^3 + 3*x^2 + 2*x + 2
    gap> 1/2 + h;
    Error, <l> must lie in the base ring of <r>

f - g

The operator - evaluates to the difference of the polynomials f and g, which must be polynomials over a common base ring.

    gap> x := Indeterminate( Integers );; x.name := "x";;
    gap> h := Polynomial( Integers, [1,2,3,4] );
    4*x^3 + 3*x^2 + 2*x + 1
    gap> h - 2*h;
    -4*x^3 - 3*x^2 - 2*x - 1

f - scl
scl - f

The operator - evaluates to the difference of the polynomial f and the scalar scl, which must lie in the base ring of f.

    gap> x := Indeterminate( Integers );; x.name := "x";;
    gap> h := Polynomial( Integers, [1,2,3,4] );
    4*x^3 + 3*x^2 + 2*x + 1
    gap> h - 1;
    4*x^3 + 3*x^2 + 2*x
    gap> 1 - h;
    -4*x^3 - 3*x^2 - 2*x

f * g

The operator * evaluates to the product of the two polynomials f and g, which must be polynomial over a common base ring.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> h := 4*x^3 + 3*x^2 + 2*x + 1;
    4*x^3 + 3*x^2 + 2*x + 1
    gap> h * h;
    16*x^6 + 24*x^5 + 25*x^4 + 20*x^3 + 10*x^2 + 4*x + 1

f * scl
scl * f

The operator * evaluates to the product of the polynomial f and the scalar scl, which must lie in the base ring of f.

    gap> f := Polynomial( GF(2), [Z(2), Z(2)] );
    Z(2)^0*(X(GF(2)) + 1)
    gap> f - Z(2);
    X(GF(2))
    gap> Z(4) - f;
    Error, <l> must lie in the base ring of <r>

f ^ n

The operator ^ evaluates the the n-th power of the polynomial f. If n is negative ^ will try to invert f in the Laurent polynomial ring ring.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> k := x - 1 + x^-1;
    x - 1 + x^(-1)
    gap> k ^ 3;
    x^3 - 3*x^2 + 6*x - 7 + 6*x^(-1) - 3*x^(-2) + x^(-3)
    gap> k^-1;
    Error, cannot invert <l> in the laurent polynomial ring

f / scl

The operator / evaluates to the product of the polynomial f and the inverse of the scalar scl, which must be invertable in its default ring.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> h := 4*x^3 + 3*x^2 + 2*x + 1;
    4*x^3 + 3*x^2 + 2*x + 1
    gap> h / 3;
    (4/3)*x^3 + x^2 + (2/3)*x + (1/3) 

scl / f

The operator / evaluates to the product of the scalar scl and the inverse of the polynomial f, which must be invertable in its Laurent ring.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> 30 / x;
    30*x^(-1)
    gap> 3 / (1+x);
    Error, cannot invert <l> in the laurent polynomial ring 

f / g

The operator / evaluates to the quotient of the two polynomials f and g, if such quotient exists in the Laurent polynomial ring. Otherwise / signals an error.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> f := (1+x+x^2) * (3-x-2*x^2);
    -2*x^4 - 3*x^3 + 2*x + 3
    gap> f / (1+x+x^2);
    -2*x^2 - x + 3
    gap> f / (1+x);
    Error, cannot divide <l> by <r> 

19.7 Degree

Degree( f )

Degree returns the degree d_<f> of f (see Polynomials).

Note that this is only equal to the Euclidean degree in the polynomial ring P(R). It is not equal in the Laurent polynomial ring L(R).

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> Degree( x^10 + x^2 + 1 );
    10
    gap> EuclideanDegree( x^10 + x^2 + 1 );
    10      # the default ring is the polynomial ring
    gap> Degree( x^-10 + x^-11 );
    -10
    gap> EuclideanDegree( x^-10 + x^-11 );
    1       # the default ring is the Laurent polynomial ring

19.8 LeadingCoefficient

LeadingCoefficient( f )

LeadingCoefficient returns the last non-zero coefficient of f (see Polynomials).

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> LeadingCoefficient( 3*x^2 + 2*x + 1);
    3 

19.9 Value

Value( f, w )

Let f be a Laurent polynomial (..., f_{-1}, f_0, f_1, ...). Then Value returns the finite sum ... + f_{-1} <w>^{-1} + f_0 <w>^0 + f_1 <w> + ....

Note that x need not be contained in the base ring of f.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> k := -x + 1;
    -x + 1
    gap> Value( k, 2 );
    -1
    gap> Value( k, [[1,1],[0,1]] );
    [ [ 0, -1 ], [ 0, 0 ] ]

19.10 Derivative

Derivative( f )

Let f be a Laurent polynomial (..., f_{-1}, f_0, f_1, ...). Then Derivative returns the polynomial g = (..., g_{i-1} = i* f_i, ... ).

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> Derivative( x^10 + x^-11 );
    10*x^9 - 11*x^(-12)
    gap> y := Indeterminate(GF(5));; y.name := "y";;    
    gap> Derivative( y^10 + y^-11 );
    Z(5)^2*y^(-12)

19.11 InterpolatedPolynomial

InterpolatedPolynomial( R, x, y )

InterpolatedPolynomial returns the unique polynomial of degree less than n which has value y[i] at x[i] for all i=1,...,n, where x and y must be lists of elements of the ring or field R, if such a polynomial exists. Note that the elements in x must be distinct.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> p := InterpolatedPolynomial( Rationals, [1,2,3,4], [3,2,4,1] );
    (-4/3)*x^3 + (19/2)*x^2 + (-121/6)*x + 15
    gap> List( [1,2,3,4], x -> Value(p,x) );
    [ 3, 2, 4, 1 ] 
    gap> Unbind( x.name ); 

19.12 ConwayPolynomial

ConwayPolynomial( p, n )

returns the Conway polynomial of the finite field GF(p^n) as polynomial over the Rationals.

The Conway polynomial Phi_{n,p} of GF(p^n) is defined by the following properties.

First define an ordering of polynomials of degree n over GF(p) as follows.

f = sum_{i=0}^n (-1)^i f_i x^i is smaller than g = sum_{i=0}^n (-1)^i g_i x^i if and only if there is an index m leq n such that f_i = g_i for all i > m, and tilde{f_m} < tilde{g_m}, where tilde{c} denotes the integer value in { 0, 1, ldots, p-1 } that is mapped to c in GF(p) under the canonical epimorphism that maps the integers onto GF(p).

Phi_{n,p} is primitive over GF(p), that is, it is irreducible, monic, and is the minimal polynomial of a primitive element of GF(p^n) over GF(p).

For all divisors d of n the compatibility condition Phi_{d,p}( x^{frac{p^n-1}{p^m-1}} ) equiv 0 pmod{Phi_{n,p}(x)} holds.

With respect to the ordering defined above, Phi_{n,p} shall be minimal.

    gap> ConwayPolynomial( 7, 3 );
    X(Rationals)^3 + 6*X(Rationals)^2 + 4
    gap> ConwayPolynomial( 41, 3 );
    X(Rationals)^3 + X(Rationals) + 35 

The global list CONWAYPOLYNOMIALS contains Conway polynomials for small values of p and n. Note that the computation of Conway polynomials may be very expensive, especially if n is not a prime.

19.13 CyclotomicPolynomial

CyclotomicPolynomial( R, n )

returns the n-th cyclotomic polynomial over the field R.

    gap> CyclotomicPolynomial( GF(2), 6 );
    Z(2)^0*(X(GF(2))^2 + X(GF(2)) + 1)
    gap> CyclotomicPolynomial( Rationals, 5 );
    X(Rationals)^4 + X(Rationals)^3 + X(Rationals)^2 + X(Rationals) + 1 

In every GAP session the computed cyclotomic polynomials are stored in the global list CYCLOTOMICPOLYNOMIALS.

19.14 PolynomialRing

PolynomialRing( R )

PolynomialRing returns the ring of all polynomials over a field R or ring-with-one R.

    gap> f2 := GF(2);;                
    gap> R := PolynomialRing( f2 );
    PolynomialRing( GF(2) )
    gap> Z(2) in R;
    false
    gap> Polynomial( f2, [Z(2),Z(2)] ) in R;
    true
    gap> Polynomial( GF(4), [Z(2),Z(2)] ) in R;
    false
    gap> R := PolynomialRing( GF(2) );
    PolynomialRing( GF(2) )

19.15 IsPolynomialRing

IsPolynomialRing( domain )

IsPolynomialRing returns true if the object domain is a ring record, representing a polynomial ring (see PolynomialRing), and false otherwise.

    gap> IsPolynomialRing( Integers );                  
    false
    gap> IsPolynomialRing( PolynomialRing( Integers ) );
    true
    gap> IsPolynomialRing( LaurentPolynomialRing( Integers ) );
    false 

19.16 LaurentPolynomialRing

LaurentPolynomialRing( R )

LaurentPolynomialRing returns the ring of all Laurent polynomials over a field R or ring-with-one R.

    gap> f2 := GF(2);;
    gap> R := LaurentPolynomialRing( f2 );
    LaurentPolynomialRing( GF(2) )
    gap> Z(2) in R;
    false
    gap> Polynomial( f2, [Z(2),Z(2)] ) in R;   
    true
    gap> Polynomial( GF(4), [Z(2),Z(2)] ) in R;
    false
    gap> Indeterminate(f2)^-1 in R;
    true

19.17 IsLaurentPolynomialRing

IsLaurentPolynomialRing( domain )

IsLaurentPolynomialRing returns true if the object domain is a ring record, representing a Laurent polynomial ring (see LaurentPolynomialRing), and false otherwise.

    gap> IsPolynomialRing( Integers );                  
    false
    gap> IsLaurentPolynomialRing( PolynomialRing( Integers ) );
    false
    gap> IsLaurentPolynomialRing( LaurentPolynomialRing( Integers ) );
    true 

19.18 Ring Functions for Polynomial Rings

As was already noted in the introduction to this chapter polynomial rings are rings, so all ring functions (see chapter Rings) are applicable to polynomial rings. This section comments on the implementation of those functions.

Let R be a commutative ring-with-one or a field and let P be the polynomial ring over R.

EuclideanDegree( P, f )

P is an Euclidean ring if and only if R is field. In this case the Euclidean degree of f is simply the degree of f. If R is not a field then the function signals an error.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> EuclideanDegree( x^10 + x^2 + 1 );
    10
    gap> EuclideanDegree( x^0 );
    0 

EuclideanRemainder( P, f, g )

P is an Euclidean ring if and only if R is field. In this case it is possible to divide f by g with remainder.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> EuclideanRemainder( (x+1)*(x+2)+5, x+1 );
    5*x^0 

EuclideanQuotient( P, f, g )

P is an Euclidean ring if and only if R is field. In this case it is possible to divide f by g with remainder.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> EuclideanQuotient( (x+1)*(x+2)+5, x+1 ); 
    x + 2 

QuotientRemainder( P, f, g )

P is an Euclidean ring if and only if R is field. In this case it is possible to divide f by g with remainder.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> QuotientRemainder( (x+1)*(x+2)+5, x+1 );
    [ x + 2, 5*x^0 ] 

Gcd( P, f, g )

P is an Euclidean ring if and only if R is field. In this case you can compute the greatest common divisor of f and g using Gcd.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> g := x^2 + 2*x + 1;;
    gap> h := x^2 - 1;;
    gap> Gcd( g, h );
    x + 1
    gap> GcdRepresentation( g, h );
    [ 1/2*x^0, -1/2*x^0 ]
    gap> g * (1/2) * x^0 - h * (1/2) * x^0;
    x + 1 

Factors( P, f )

This method is implemented for polynomial rings P over a domain R, where R is either a finite field, the rational numbers, or an algebraic extension of either one. If char R is a prime, f is factored using a Cantor-Zassenhaus algorithm.

    gap> f5 := GF(5);; f5.name := "f5";;
    gap> x  := Indeterminate(f5);; x.name := "x";;
    gap> g := x^20 + x^8 + 1;
    Z(5)^0*(x^20 + x^8 + 1)
    gap> Factors(g);
    [ Z(5)^0*(x^8 + 4*x^4 + 2), Z(5)^0*(x^12 + x^8 + 4*x^4 + 3) ]

If char R is 0, a quadratic Hensel lift is used.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> f:=x^105-1;
    x^105 - 1
    gap> Factors(f);
    [ x - 1, x^2 + x + 1, x^4 + x^3 + x^2 + x + 1, 
      x^6 + x^5 + x^4 + x^3 + x^2 + x + 1, 
      x^8 - x^7 + x^5 - x^4 + x^3 - x + 1, 
      x^12 - x^11 + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1, 
      x^24 - x^23 + x^19 - x^18 + x^17 - x^16 + x^14 - x^13 + x^12 - x^
        11 + x^10 - x^8 + x^7 - x^6 + x^5 - x + 1, 
      x^48 + x^47 + x^46 - x^43 - x^42 - 2*x^41 - x^40 - x^39 + x^36 + x^
        35 + x^34 + x^33 + x^32 + x^31 - x^28 - x^26 - x^24 - x^22 - x^
        20 + x^17 + x^16 + x^15 + x^14 + x^13 + x^12 - x^9 - x^8 - 2*x^
        7 - x^6 - x^5 + x^2 + x + 1 ]

As f is an element of P if and only if the base ring of f is R you must embed the polynomial into the polynomial ring P if it is written as polynomial over a subring.

    gap> f25 := GF(25);; Indeterminate(f25).name := "y";;
    gap> l := Factors( EmbeddedPolynomial( PolynomialRing(f25), g ) );   
    [ y^4 + Z(5^2)^13, y^4 + Z(5^2)^17, y^6 + Z(5)^3*y^2 + Z(5^2)^3, 
      y^6 + Z(5)^3*y^2 + Z(5^2)^15 ]
    gap> l[1] * l[2];
    y^8 + Z(5)^2*y^4 + Z(5)
    gap> l[3] * l[4];
    y^12 + y^8 + Z(5)^2*y^4 + Z(5)^3 

StandardAssociate( P, f )

For a ring R the standard associate a of f is a multiple of f such that the leading coefficient of a is the standard associate in R. For a field R the standard associate a of f is a multiple of f such that the leading coefficient of a is 1.

    gap> x := Indeterminate(Integers);; x.name := "x";; 
    gap> StandardAssociate( -2 * x^3 - x );
    2*x^3 + x

19.19 Ring Functions for Laurent Polynomial Rings

As was already noted in the introduction to this chapter Laurent polynomial rings are rings, so all ring functions (see chapter Rings) are applicable to polynomial rings. This section comments on the implementation of those functions.

Let R be a commutative ring-with-one or a field and let P be the polynomial ring over R.

EuclideanDegree( P, f )

P is an Euclidean ring if and only if R is field. In this case the Euclidean degree of f is the difference of d(f) and v(f) (see Polynomials). If R is not a field then the function signals an error.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> LR := LaurentPolynomialRing(Rationals);;
    gap> EuclideanDegree( LR, x^10 + x^2 );
    8
    gap> EuclideanDegree( LR, x^7 );
    0
    gap> EuclideanDegree( x^7 );
    7
    gap> EuclideanDegree( LR, x^2 + x^-2 );
    4
    gap> EuclideanDegree( x^2 + x^-2 );
    4 

Gcd( P, f, g )

P is an Euclidean ring if and only if R is field. In this case you can compute the greatest common divisor of f and g using Gcd.

    gap> x := Indeterminate(Rationals);; x.name := "x";;
    gap> LR := LaurentPolynomialRing(Rationals);;
    gap> g := x^3 + 2*x^2 + x;;
    gap> h := x^3 - x;;
    gap> Gcd( g, h );
    x^2 + x
    gap> Gcd( LR, g, h );
    x + 1     # 'x' is a unit in 'LR'
    gap> GcdRepresentation( LR, g, h );
    [ (1/2)*x^(-1), (-1/2)*x^(-1) ] 

Factors( P, f )

This method is only implemented for a Laurent polynomial ring P over a finite field R. In this case f is factored using a Cantor-Zassenhaus algorithm. As f is an element of P if and only if the base ring of f is R you must embed the polynomial into the polynomial ring P if it is written as polynomial over a subring.

    gap> f5 := GF(5);; f5.name := "f5";;
    gap> x  := Indeterminate(f5);; x.name := "x";;
    gap> g := x^10 + x^-2 + x^-10;
    Z(5)^0*(x^10 + x^(-2) + x^(-10))
    gap> Factors(g);
    [ Z(5)^0*(x^(-2) + 4*x^(-6) + 2*x^(-10)),
      Z(5)^0*(x^12 + x^8 + 4*x^4 + 3) ]
    gap> f25 := GF(25);; Indeterminate(f25).name := "y";;
    gap> gg := EmbeddedPolynomial( LaurentPolynomialRing(f25), g );
    y^10 + y^(-2) + y^(-10)
    gap> l := Factors( gg );
    [ y^(-6) + Z(5^2)^13*y^(-10), y^4 + Z(5^2)^17,
      y^6 + Z(5)^3*y^2 + Z(5^2)^3, y^6 + Z(5)^3*y^2 + Z(5^2)^15 ]
    gap> l[1] * l[2];
    y^(-2) + Z(5)^2*y^(-6) + Z(5)*y^(-10)
    gap> l[3]*[4];
    [ Z(5)^2*y^6 + Z(5)*y^2 + Z(5^2)^15 ]

StandardAssociate( P, f )

For a ring R the standard associate a of f is a multiple of f such that the leading coefficient of a is the standard associate in R and v(<a>) is zero. For a field R the standard associate a of f is a multiple of f such that the leading coefficient of a is 1 and v(<a>) is zero.

    gap> x := Indeterminate(Integers);; x.name := "x";;
    gap> LR := LaurentPolynomialRing(Integers);;
    gap> StandardAssociate( LR, -2 * x^3 - x );
    2*x^2 + 1

Previous Up Next
Index

GAP 3.4.4
April 1997