# 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).

## 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```

`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```

GAP 3.4.4
April 1997