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

- Multivariate Polynomials
- Indeterminate
- Polynomial
- IsPolynomial
- Comparisons of Polynomials
- Operations for Polynomials
- Degree
- LeadingCoefficient
- Value
- Derivative
- InterpolatedPolynomial
- ConwayPolynomial
- CyclotomicPolynomial
- PolynomialRing
- IsPolynomialRing
- LaurentPolynomialRing
- IsLaurentPolynomialRing
- Ring Functions for Polynomial Rings
- 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 **GAP**.

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

`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

`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

`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

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

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

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

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

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

.

`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

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

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