%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%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  <f> / <g> 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( <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)|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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 |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Comparisons of Polynomials}%
\index{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|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LeadingCoefficient}

'LeadingCoefficient( <f> )'

'LeadingCoefficient' returns the  last non-zero  coefficient  of <f> (see
"Polynomials").

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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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 ] ]|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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)|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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 ); |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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) )|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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 |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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|


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{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 |


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 <P>  be the
polynomial ring over $R$.

\vspace{5mm}
'EuclideanDegree( <P>, <f> )'%
\index{EuclideanDegree!for polynomials}

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

\vspace{5mm}
'EuclideanRemainder( <P>, <f>, <g> )'%
\index{EuclideanRemainder!for polynomials}

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

\vspace{5mm}
'EuclideanQuotient( <P>, <f>, <g> )'%
\index{EuclideanQuotient!for polynomials}

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

\vspace{5mm}
'QuotientRemainder( <P>, <f>, <g> )'%
\index{QuotientRemainder!for polynomials}

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

\vspace{5mm}
'Gcd( <P>, <f>, <g> )'%
\index{Gcd!for polynomials}

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

\vspace{5mm}
'Factors( <P>, <f> )'%
\index{Factors!for polynomials}

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 |


\vspace{5mm}
'StandardAssociate( <P>, <f> )'%
\index{StandardAssociate!for polynomials}

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|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 <P>  be  the
polynomial ring over $R$.

\vspace{5mm}
'EuclideanDegree( <P>, <f> )'%
\index{EuclideanDegree!for polynomials}

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

\vspace{5mm}
'Gcd( <P>, <f>, <g> )'%
\index{Gcd!for polynomials}

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

\vspace{5mm}
'Factors( <P>, <f> )'%
\index{Factors!for polynomials}

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

\vspace{5mm}
'StandardAssociate( <P>, <f> )'%
\index{StandardAssociate!for polynomials}

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|

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local Emacs variables
%%
%%  Local Variables:
%%  mode:               outline
%%  outline-regexp:     "\\\\Chapter\\|\\\\Section\\|%E"
%%  fill-column:        73
%%  eval:               (hide-body)
%%  End:
%%
