Let R be a commutative ring-with-one. A (univariate) Laurent polynomial over R is a sequence (..., c-1, c0, c1, ...) of elements of R such that only finitely many are non-zero. For a ring element r of R and polynomials f = (..., f-1, f0, f1, ...) and g = (..., g-1, g0, g1, ...) we define f + g = (..., f-1 + g-1, f0+g0, f1+g1, ...) , r. f = (..., r f-1, r f0, r f1, ...), and f * g = (..., s-1, s0, s1, ...), where sk = ... + fi gk-i + .... Note that sk is well-defined as only finitely many fi and gi are non-zero. We call the largest integers d(f), such that fd(f) is non-zero, the degree of f, fi the i.th coefficient of f, and fd(f) the leading coefficient of f. If the smallest integer v(f), such that fv(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 fd(f) is a unit in R.
GAP3 uses the above definition of polynomials. This definition has some advantages and some drawbacks. First of all, the polynomial (..., x0 = 0, x1 = 1, x2 = 0, ...) is commonly denoted by x and is called an indeterminate over R, (..., c-1, c0, c1, ...) is written as ... + c-1 x-1 + c0 + c1 x + c2 x2 + ..., and P(R) as R[x] (note that the way GAP3 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 GAP3 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 ≠ 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 polynomial rings. (see Ring Functions for Polynomial Rings and Ring Functions for Laurent Polynomial Rings).
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 GAP3.
Indeterminate( R )
X( R )
Indeterminate returns the polynomial (..., x0 = 0, x1 = 1, x2 = 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)
Polynomial( R, l )
Polynomial( R, l, v )
l must be a list of coefficients of the polynomial f to be
constructed, namely (..., fv = l[1], fv+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
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>
Degree( f )
Degree returns the degree df 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
Valuation( f )
Valuation returns the valuation f (see Polynomials).
gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> Valuation( x^10 + x^2 + 1 );
0
gap> Valuation( x^10 + x^2);
2
gap> Valuation( x^-10 + x^-11 );
-11
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
Coefficient( f, i)
Coefficient returns the i-th coefficient of f (see Polynomials).
for other objects the function looks if f has a Coefficient method in
its operations record and then returns f.operations.Coefficient(f,i).
gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> Coefficient(3*x^2 + 2*x, 2);
3
gap> Coefficient(3*x^2 + 2*x, 1);
2
gap> Coefficient(3*x^2 + 2*x, 0);
0
Value( f, w )
Let f be a Laurent polynomial (..., f-1, f0, f1, ...). Then
Value returns the finite sum ... + f-1 w-1 + f0 w0 + f1
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 ] ]
Derivative( f )
If f is a Laurent polynomial (..., f-1, f0, f1, ...), then
Derivative returns the polynomial g = (..., gi-1 = i* fi, ... ).
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)
In a second form f is a list interpreted as the coefficients of a
polynomial; then Derivative returns the coefficients of the derivative
polynomial, that is the list [f[2],2*f[3],..].
gap> Derivative([1,2,1,2,1,2]);
[ 2, 2, 6, 4, 10 ]
Resultant( f, g )
f and g must be polynomials, not Laurent polynomials. The function returns their resultant.
gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> Resultant(x^3+1,3*x^2);
27
Discriminant( f )
f must be a polynomial, not a Laurent polynomial. The function returns its discriminant.
gap> x := Indeterminate(Rationals);; x.name := "x";;
gap> Discriminant(x^3+1);
-27
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 );
ConwayPolynomial( p, n )
returns the Conway polynomial of the finite field GF(pn) as polynomial over the Rationals.
The Conway polynomial Φn,p of GF(pn) is defined by the following properties.
First define an ordering of polynomials of degree n over GF(p) as follows.
f = ∑i=0n (-1)i fi xi is smaller than g = ∑i=0n (-1)i gi xi if and only if there is an index m ≤ n such that fi = gi for all i > m, and ~fm < ~gm, where ~c denotes the integer value in { 0, 1, ..., p-1 } that is mapped to c∈ GF(p) under the canonical epimorphism that maps the integers onto GF(p).
Φn,p is primitive over GF(p), that is, it is irreducible, monic, and is the minimal polynomial of a primitive element of GF(pn) over GF(p).
For all divisors d of n the compatibility condition Φd,p( x(pn-1)/(pm-1) ) ≡ 0 (mod Φn,p(x)) holds.
With respect to the ordering defined above, Φ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.
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 GAP3 session the computed cyclotomic polynomials are stored in
the global list CYCLOTOMICPOLYNOMIALS.
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) )
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
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
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.22 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.
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
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
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
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 ]
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
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
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.23 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.
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
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) ]
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 ]
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
gap3-jm