%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A polynom.tex GAP documentation Frank Celler %% %A @(#)$Id: polynom.tex,v 3.22 1994/06/10 02:52:54 vfelsch Rel $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %H $Log: polynom.tex,v $ %H Revision 3.22 1994/06/10 02:52:54 vfelsch %H updating examples %H %H Revision 3.21 1994/05/30 07:14:18 vfelsch %H more index entires rearranged %H %H Revision 3.20 1994/05/30 06:39:24 vfelsch %H index entries rearranged %H %H Revision 3.19 1994/05/19 13:50:18 sam %H removed overfull box ... %H %H Revision 3.18 1994/04/26 10:23:03 sam %H added documentation of 'ConwayPolynomial', 'CyclotomicPolynomial' %H %H Revision 3.17 1994/03/16 11:12:39 ahulpke %H Added reference to polynomial factorization over the rationals %H %H Revision 3.16 1993/11/09 00:08:10 martin %H fixed overfull box %H %H Revision 3.15 1993/07/05 10:48:30 fceller %H added 'InterpolatedPolynomial' %H %H Revision 3.14 1993/05/06 07:51:32 fceller %H / now computes the quotient in the Laurent ring %H %H Revision 3.13 1993/03/11 17:58:44 fceller %H added index entries for gcd and degree %H %H Revision 3.12 1993/03/11 11:00:41 fceller %H added 'EuclideanQuotient', 'EuclideanRemainder' and 'QuotientRemainder' %H %H Revision 3.11 1993/02/19 10:48:42 gap %H adjustments in line length and spelling %H %H Revision 3.10 1993/02/12 11:35:41 felsch %H examples adjusted to line length 72 %H %H Revision 3.9 1993/02/05 07:39:29 felsch %H new examples fixed %H %H Revision 3.8 1993/02/04 14:05:50 fceller %H added '/' for polynomials %H %H Revision 3.7 1993/02/03 13:31:09 felsch %H examples fixed %H %H Revision 3.6 1993/02/01 12:34:19 fceller %H fixed a few typos %H %H Revision 3.5 1993/01/27 11:50:00 fceller %H added example in introduction %H %H Revision 3.4 1993/01/04 10:59:55 fceller %H added 'LeadingCoefficient' %H %H Revision 3.3 1992/12/02 10:10:59 fceller %H fixed a few misspellings %H %H Revision 3.2 92/11/30 13:44:29 fceller %H initial GAP 3.2 revision %% \Chapter{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, ...)$ , $r\cdot 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 polynomial rings. (see "Ring Functions for Polynomial Rings" and "Ring Functions for Laurent Polynomial Rings"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Indeterminate}% \index{X} 'Indeterminate( )'\\ 'X( )' 'Indeterminate' returns the polynomial $(..., x_0 = 0, x_1 = 1, x_2 = 0, ...)$ over , 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)| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Polynomial} 'Polynomial( , )'\\ 'Polynomial( , , )' must be a list of coefficients of the polynomial $f$ to be constructed, namely $(..., f_ = [1], f_{+1} = [2], ...)$ over , which must be a commutative ring-with-one or a field. The default for is 0. 'Polynomial' returns this polynomial $f$. For interactive calculation it might by easier to construct the indeterminate over 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsPolynomial} 'IsPolynomial( )' 'IsPolynomial' returns 'true' if , which can be an object of arbitrary type, is a polynomial and 'false' otherwise. The function will signal an error if is an unbound variable. | gap> IsPolynomial( 1 ); false gap> IsPolynomial( Indeterminate(Integers) ); true| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Comparisons of Polynomials}% \index{comparisons!of polynomials} ' = ' \\ ' \<> ' The equality operator '=' evaluates to 'true' if the polynomials and are equal, and to 'false' otherwise. The inequality operator '\<>' evaluates to 'true' if the polynomials and 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| ' \<\ ' \\ ' \<= ' \\ ' > ' \\ ' >= ' The operators '\<', '\<=', '>', and '>=' evaluate to 'true' if the polynomial is less than, less than or equal to, greater than, or greater than or equal to the polynomial , and to 'false' otherwise. A polynomial is less than if $v()$ is less than $v()$, or if $v()$ and $v()$ are equal and $d()$ is less than $d()$. If $v()$ is equal to $v()$ and $d()$ is equal to $d()$ the coefficient lists of and 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| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Polynomials}% \index{operations!for polynomials} The following operations are always available for polynomials. The operands must have a common base ring, no implicit conversions are performed. ' + ' The operator '+' evaluates to the sum of the polynomials and , 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| ' + ' \\ ' + ' The operator '+' evaluates to the sum of the polynomial and the scalar , which must lie in the base ring of . | 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, must lie in the base ring of | ' - ' The operator '-' evaluates to the difference of the polynomials and , 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| ' - ' \\ ' - ' The operator '-' evaluates to the difference of the polynomial and the scalar , which must lie in the base ring of . | 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| ' \*\ ' The operator '\*' evaluates to the product of the two polynomials and , 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| ' \*\ ' \\ ' \*\ ' The operator '\*' evaluates to the product of the polynomial and the scalar , which must lie in the base ring of . | 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, must lie in the base ring of | ' \^\ ' The operator '\^' evaluates the the -th power of the polynomial . If is negative '\^' will try to invert 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 in the laurent polynomial ring| ' / ' The operator '/' evaluates to the product of the polynomial and the inverse of the scalar , 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) | ' / ' The operator '/' evaluates to the product of the scalar and the inverse of the polynomial , 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 in the laurent polynomial ring | ' / ' The operator '/' evaluates to the quotient of the two polynomials and , 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 by | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Degree} 'Degree( )' 'Degree' returns the degree $d_$ 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| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LeadingCoefficient} 'LeadingCoefficient( )' 'LeadingCoefficient' returns the last non-zero coefficient of (see "Polynomials"). | gap> x := Indeterminate(Rationals);; x.name := "x";; gap> LeadingCoefficient( 3*x^2 + 2*x + 1); 3 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Value} 'Value( , )' Let be a Laurent polynomial $(..., f_{-1}, f_0, f_1, ...)$. Then 'Value' returns the finite sum $... + f_{-1} ^{-1} + f_0 ^0 + f_1 + ...$. Note that need not be contained in the base ring of . | 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 ] ]| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Derivative} 'Derivative( )' Let 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)| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{InterpolatedPolynomial} 'InterpolatedPolynomial( , , )' 'InterpolatedPolynomial' returns the unique polynomial of degree less than $n$ which has value $y[i]$ at $x[i]$ for all $i=1,...,n$, where and must be lists of elements of the ring or field , if such a polynomial exists. Note that the elements in 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 ); | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{ConwayPolynomial} 'ConwayPolynomial(

, )' 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

and . Note that the computation of Conway polynomials may be very expensive, especially if is not a prime. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{CyclotomicPolynomial} 'CyclotomicPolynomial( , )' returns the -th cyclotomic polynomial over the field . | 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'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{PolynomialRing} 'PolynomialRing( )' 'PolynomialRing' returns the ring of all polynomials over a field or ring-with-one . | 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) )| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsPolynomialRing} 'IsPolynomialRing( )' 'IsPolynomialRing' returns 'true' if the object 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{LaurentPolynomialRing} 'LaurentPolynomialRing( )' 'LaurentPolynomialRing' returns the ring of all Laurent polynomials over a field or ring-with-one . | 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| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsLaurentPolynomialRing} 'IsLaurentPolynomialRing( )' 'IsLaurentPolynomialRing' returns 'true' if the object 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 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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

be the polynomial ring over $R$. \vspace{5mm} 'EuclideanDegree(

, )'% \index{EuclideanDegree!for polynomials}

is an Euclidean ring if and only if $R$ is field. In this case the Euclidean degree of is simply the degree of . 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 | \vspace{5mm} 'EuclideanRemainder(

, , )'% \index{EuclideanRemainder!for polynomials}

is an Euclidean ring if and only if $R$ is field. In this case it is possible to divide by with remainder. | gap> x := Indeterminate(Rationals);; x.name := "x";; gap> EuclideanRemainder( (x+1)*(x+2)+5, x+1 ); 5*x^0 | \vspace{5mm} 'EuclideanQuotient(

, , )'% \index{EuclideanQuotient!for polynomials}

is an Euclidean ring if and only if $R$ is field. In this case it is possible to divide by with remainder. | gap> x := Indeterminate(Rationals);; x.name := "x";; gap> EuclideanQuotient( (x+1)*(x+2)+5, x+1 ); x + 2 | \vspace{5mm} 'QuotientRemainder(

, , )'% \index{QuotientRemainder!for polynomials}

is an Euclidean ring if and only if $R$ is field. In this case it is possible to divide by with remainder. | gap> x := Indeterminate(Rationals);; x.name := "x";; gap> QuotientRemainder( (x+1)*(x+2)+5, x+1 ); [ x + 2, 5*x^0 ] | \vspace{5mm} 'Gcd(

, , )'% \index{Gcd!for polynomials}

is an Euclidean ring if and only if $R$ is field. In this case you can compute the greatest common divisor of and 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 | \vspace{5mm} 'Factors(

, )'% \index{Factors!for polynomials} This method is implemented for polynomial rings

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, 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 is an element of

if and only if the base ring of is $R$ you must embed the polynomial into the polynomial ring

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 | \vspace{5mm} 'StandardAssociate(

, )'% \index{StandardAssociate!for polynomials} For a ring $R$ the standard associate $a$ of is a multiple of such that the leading coefficient of is the standard associate in $R$. For a field $R$ the standard associate $a$ of is a multiple of such that the leading coefficient of is 1. | gap> x := Indeterminate(Integers);; x.name := "x";; gap> StandardAssociate( -2 * x^3 - x ); 2*x^3 + x| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{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

be the polynomial ring over $R$. \vspace{5mm} 'EuclideanDegree(

, )'% \index{EuclideanDegree!for polynomials}

is an Euclidean ring if and only if $R$ is field. In this case the Euclidean degree of 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 | \vspace{5mm} 'Gcd(

, , )'% \index{Gcd!for polynomials}

is an Euclidean ring if and only if $R$ is field. In this case you can compute the greatest common divisor of and 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) ] | \vspace{5mm} 'Factors(

, )'% \index{Factors!for polynomials} This method is only implemented for a Laurent polynomial ring

over a finite field $R$. In this case is factored using a Cantor-Zassenhaus algorithm. As is an element of

if and only if the base ring of is $R$ you must embed the polynomial into the polynomial ring

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 ]| \vspace{5mm} 'StandardAssociate(

, )'% \index{StandardAssociate!for polynomials} For a ring $R$ the standard associate $a$ of is a multiple of such that the leading coefficient of is the standard associate in $R$ and $v()$ is zero. For a field $R$ the standard associate $a$ of is a multiple of such that the leading coefficient of is 1 and $v()$ is zero. | gap> x := Indeterminate(Integers);; x.name := "x";; gap> LR := LaurentPolynomialRing(Integers);; gap> StandardAssociate( LR, -2 * x^3 - x ); 2*x^2 + 1| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %E Emacs . . . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section\\|%E" %% fill-column: 73 %% eval: (hide-body) %% End: %%