home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / polynom.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  25.3 KB  |  761 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  polynom.tex                 GAP documentation                Frank Celler
  4. %%
  5. %A  @(#)$Id: polynom.tex,v 3.11 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %H  $Log: polynom.tex,v $
  10. %H  Revision 3.11  1993/02/19  10:48:42  gap
  11. %H  adjustments in line length and spelling
  12. %H
  13. %H  Revision 3.10  1993/02/12  11:35:41  felsch
  14. %H  examples adjusted to line length 72
  15. %H
  16. %H  Revision 3.9  1993/02/05  07:39:29  felsch
  17. %H  new examples fixed
  18. %H
  19. %H  Revision 3.8  1993/02/04  14:05:50  fceller
  20. %H  added '/' for polynomials
  21. %H
  22. %H  Revision 3.7  1993/02/03  13:31:09  felsch
  23. %H  examples fixed
  24. %H
  25. %H  Revision 3.6  1993/02/01  12:34:19  fceller
  26. %H  fixed a few typos
  27. %H
  28. %H  Revision 3.5  1993/01/27  11:50:00  fceller
  29. %H  added example in introduction
  30. %H
  31. %H  Revision 3.4  1993/01/04  10:59:55  fceller
  32. %H  added 'LeadingCoefficient'
  33. %H
  34. %H  Revision 3.3  1992/12/02  10:10:59  fceller
  35. %H  fixed a few misspellings
  36. %H
  37. %H  Revision 3.2  92/11/30  13:44:29  fceller
  38. %H  initial GAP 3.2 revision
  39. %%
  40. \Chapter{Polynomials}
  41.  
  42. Let  $R$  be  a  commutative  ring-with-one.    A  *(univariate)  Laurent
  43. polynomial*  over $R$ is a  sequence  $(..., c_{-1}, c_0,  c_1, ...)$  of
  44. elements of $R$ such  that only  finitely many are non-zero.  For a  ring
  45. element $r$ of $R$ and polynomials $f = (..., f_{-1}, f_0, f_1, ...)$ and
  46. $g = (...,  g_{-1},  g_0,  g_1, ...)$ we define $f +  g = (..., f_{-1}  +
  47. g_{-1}, f_0+g_0, f_1+g_1, ...)$ , $r\cdot f = (...,  r  f_{-1},  r f_0, r
  48. f_1, ...)$, and $f \* g = (..., s_{-1}, s_0, s_1, ...)$, where $s_k = ...
  49. +  f_i g_{k-i} + ...$.  Note that  $s_k$ is well-defined as only finitely
  50. many $f_i$ and $g_i$ are non-zero.  We call  the largest integers $d(f)$,
  51. such that  $f_{d(f)}$  is  non-zero, the *degree* of $f$, $f_i$ the *i.th
  52. coefficient* of $f$,  and $f_{d(f)}$ the leading coefficient of $f$.   If
  53. the  smallest  integer  $v(f),$  such  that $f_{v(f)}$  is  non-zero,  is
  54. negative, we say that $f$ has a pole of order $v$ at  0, otherwise we say
  55. that $f$ has  a root of  order  $v$  at 0.  We  call  $R$  the *base  (or
  56. coefficient) ring*  of $f$. If  $f  = (..., 0, 0, 0, ...)$ we set $d(f) =
  57. -1$ and $v(f) = 0$.
  58.  
  59. The set of  all Laurent polynomials $L(R)$ over a ring $R$ together  with
  60. above  definitions  of  $+$  and  $\*$  is  again  a  ring, the  *Laurent
  61. polynomial ring* over  $R$, and $R$ is  called the *base ring* of $L(R)$.
  62. The  subset  of  all  polynomials $f$  with non-negative  $v(f)$  forms a
  63. subring $P(R)$  of  $L(R)$,  the *polynomial  ring* over $R$.  If $R$  is
  64. indeed  a  field then  both  rings $L(R)$ and $P(R)$ are Euclidean.  Note
  65. that $L(R)$ and $P(R)$ have different Euclidean degree functions.  If $f$
  66. is  an element of  $P(R)$ then the Euclidean degree of  $f$ is simply the
  67. degree of $f$.   If  $f$ is viewed  as  an  element  of  $L(R)$  then the
  68. Euclidean  degree is the difference between $d(f)$ and $v(f)$.  The units
  69. of $P(R)$  are  just  the units of $R$, while the units of $L(R)$ are the
  70. polynomials $f$ such that $v(f) = d(f)$ and $f_{d(f)}$ is a unit in $R$.
  71.  
  72. {\GAP} uses the above definition  of  polynomials.   This  definition has
  73. some advantages and some drawbacks.  First of all, the  polynomial $(...,
  74. x_0 = 0, x_1 = 1, x_2 = 0, ...)$ is commonly denoted by $x$ and is called
  75. an indeterminate over  $R$, $(..., c_{-1}, c_0, c_1, ...)$  is written as
  76. $...   + c_{-1}  x^{-1} + c_0  + c_1 x + c_2  x^2 + ...$, and  $P(R)$  as
  77. $R[x]$ (note  that the  way {\GAP}  outputs a  polynomial  resembles this
  78. definition).  But if we introduce  a  second indeterminate $y$ it is  not
  79. obvious whether the product $xy$ lies in $(R[x])[y]$, the polynomial ring
  80. in $y$  over the polynomial ring in $x$, in $(R[y])[x]$, in $R[x,y]$, the
  81. polynomial ring in two  indeterminates, or  in  $R[y,x]$ (which should be
  82. equal to $R[x,y]$).  Using the  first  definition we would define $y$  as
  83. indeterminate over $R[x]$ and we know then that $xy$ lies in $(R[x])[y]$.
  84.  
  85. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  86.     gap> Rx := LaurentPolynomialRing(Rationals);;
  87.     gap> y := Indeterminate(Rx);; y.name := "y";;
  88.     gap> y^2 + x;
  89.     y^2 + (x)
  90.     gap> last^2;
  91.     y^4 + (2*x)*y^2 + (x^2)
  92.     gap> last + x;
  93.     y^4 + (2*x)*y^2 + (x^2 + x)
  94.     gap> (x^2 + x + 1) * y^2 + y + 1;
  95.     (x^2 + x + 1)*y^2 + y + (x^0)
  96.     gap> x * y;
  97.     (x)*y
  98.     gap> y * x;
  99.     (x)*y
  100.     gap> 2 * x;
  101.     2*x
  102.     gap> x * 2;
  103.     2*x |
  104.  
  105. Note that {\GAP}  does *not* embed the base ring of a polynomial into the
  106. polynomial ring. The trivial polynomial and the zero of the base ring are
  107. always different.
  108.  
  109. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  110.     gap> Rx := LaurentPolynomialRing(Rationals);;
  111.     gap> y := Indeterminate(Rx);; y.name := "y";;
  112.     gap> 0 = 0*x;
  113.     false
  114.     gap> nx := 0*x;     # a polynomial over the rationals
  115.     0*x^0
  116.     gap> ny := 0*y;     # a polynomial over a polynomial ring
  117.     0*y^0
  118.     gap> nx = ny;       # different base rings
  119.     false |
  120.  
  121. The result |0*x| $\neq$ |0*y| is probably not what you expect or want. In
  122. order to compute with two indeterminates over $R$ you must embed $x$ into
  123. $R[x][y]$.
  124.  
  125. |    gap> x  := Indeterminate(Rationals);; x.name := "x";;
  126.     gap> Rx := LaurentPolynomialRing(Rationals);;
  127.     gap> y  := Indeterminate(Rx);; y.name := "y";;
  128.     gap> x  := x * y^0;                                  
  129.     x*y^0
  130.     gap> 0*x = 0*y;
  131.     true |
  132.  
  133. The other point which might be startling is that we require the supply of
  134. a base ring  for a polynomial. But  this guarantees that 'Factor' gives a
  135. predictable result.
  136.  
  137. |    gap> f5 := GF(5);; f5.name := "f5";;
  138.     gap> f25 := GF(25);; f25.name := "f25";;
  139.     gap> Polynomial( f5, [3,2,1]*Z(5)^0 ); 
  140.     Z(5)^0*(X(f5)^2 + 2*X(f5) + 3)
  141.     gap> Factors(last);
  142.     [ Z(5)^0*(X(f5)^2 + 2*X(f5) + 3) ]
  143.     gap> Polynomial( f25, [3,2,1]*Z(5)^0 );
  144.     X(f25)^2 + Z(5)*X(f25) + Z(5)^3
  145.     gap> Factors(last);
  146.     [ X(f25) + Z(5^2)^7, X(f25) + Z(5^2)^11 ]|
  147.  
  148. The   first  sections  describe  how  polynomials  are  constructed  (see
  149. "Indeterminate", "Polynomial", and "IsPolynomial").
  150.  
  151. The  next sections describe the operations applicable to polynomials (see
  152. "Comparisons of Polynomials" and "Operations for Polynomials").
  153.  
  154. The next sections describe the functions for polynomials  (see  "Degree",
  155. "Derivative" and "Value").
  156.  
  157. The  next  sections describe the  functions  for constructing the Laurent
  158. polynomial  ring   $L(R)$   and   the   polynomial   ring   $P(R)$   (see
  159. "PolynomialRing" and "LaurentPolynomialRing").
  160.  
  161. The  next  sections  describe the ring  functions  applicable  to Laurent
  162. polynomial rings. (see "Ring  Functions for Polynomial  Rings" and  "Ring
  163. Functions for Laurent Polynomial Rings").
  164.  
  165.  
  166. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  167. \Section{Multivariate Polynomials}
  168.  
  169. As  explained  above,  each  ring   $R$  has  exactly  one  indeterminate
  170. associated with  $R$.  In order to construct a  polynomial  ring with two
  171. indeterminates  over $R$  you  must first  construct the polynomial  ring
  172. $P(R)$ and then the polynomial ring over $P(R)$.
  173.  
  174. |    gap> x  := Indeterminate(Integers);; x.name := "x";;
  175.     gap> Rx := PolynomialRing(Integers);;
  176.     gap> y  := Indeterminate(Rx);; y.name := "y";;
  177.     gap> x  := y^0 * x;
  178.     x*y^0
  179.     gap> f := x^2*y^2 + 3*x*y + x + 4*y;
  180.     (x^2)*y^2 + (3*x + 4)*y + (x)
  181.     gap> Value( f, 4 );
  182.     16*x^2 + 13*x + 16
  183.     gap> Value( last, -2 );
  184.     54
  185.     gap> (-2)^2 * 4^2 + 3*(-2)*4 + (-2) + 4*4;
  186.     54 |
  187.  
  188. We  plan  to add support for (proper) multivariate polynomials  in one of
  189. the next releases of {\GAP}.
  190.  
  191. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  192. \Section{Indeterminate}%
  193. \index{X}
  194.  
  195. 'Indeterminate( <R> )'\\
  196. 'X( <R> )'
  197.  
  198. 'Indeterminate' returns the polynomial $(..., x_0 = 0, x_1 = 1, x_2 =  0,
  199. ...)$ over <R>, which must be a commutative ring-with-one or a field.
  200.  
  201. Note  that you can assign a name to the indeterminate,  in which case all
  202. polynomials over  $R$ are printed using this name. Keep in mind  that for
  203. each ring there is exactly one indeterminate.
  204.  
  205. |    gap> x := Indeterminate( Integers );; x.name := "x";;
  206.     gap> f := x^10 + 3*x - x^-1;        
  207.     x^10 + 3*x - x^(-1)
  208.     gap> y := Indeterminate( Integers );;    # this is 'x'
  209.     gap> y.name := "y";;
  210.     gap> f;    # so 'f' is also printed differently from now on
  211.     y^10 + 3*y - y^(-1)|
  212.  
  213.  
  214. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  215. \Section{Polynomial}
  216.  
  217. 'Polynomial( <R>, <l> )'\\
  218. 'Polynomial( <R>, <l>, <v> )'
  219.  
  220. <l>  must  be  a  list  of  coefficients  of  the  polynomial  $f$ to  be
  221. constructed, namely $(..., f_<v> = <l>[1], f_{<v>+1} = <l>[2], ...)$ over
  222. <R>, which must be a  commutative ring-with-one or  a field.  The default
  223. for <v> is 0. 'Polynomial' returns this polynomial $f$.
  224.  
  225. For  interactive  calculation  it   might  by  easier  to  construct  the
  226. indeterminate over <R> and construct  the polynomial using '\^', '+'  and
  227. '\*'.
  228.  
  229. |    gap> x := Indeterminate( Integers );;
  230.     gap> x.name := "x";;
  231.     gap> f := Polynomial( Integers, [1,2,0,0,4] );
  232.     4*x^4 + 2*x + 1
  233.     gap> g := 4*x^4 + 2*x + 1;
  234.     4*x^4 + 2*x + 1 |
  235.  
  236.  
  237. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  238. \Section{IsPolynomial}
  239.  
  240. 'IsPolynomial( <obj> )'
  241.     
  242. 'IsPolynomial' returns 'true'  if <obj>,  which can  be  an object  of
  243. arbitrary type, is  a  polynomial and  'false' otherwise. The function
  244. will signal an error if <obj> is an unbound variable.
  245.  
  246. |    gap> IsPolynomial( 1 );
  247.     false
  248.     gap> IsPolynomial( Indeterminate(Integers) );
  249.     true|
  250.  
  251.  
  252. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  253. \Section{Comparisons of Polynomials}%
  254. \index{comparisons!of polynomials}
  255.  
  256. '<f> =   <g>' \\
  257. '<f> \<> <g>'
  258.  
  259. The equality operator '='  evaluates to 'true' if the polynomials <f> and
  260. <g> are equal, and  to 'false' otherwise.  The inequality operator  '\<>'
  261. evaluates to 'true' if the polynomials <f> and <g>  are not equal, and to
  262. 'false'  otherwise.
  263.  
  264. Note that polynomials are equal if and  only  if their coefficients *and*
  265. their base  rings are  equal.  Polynomials  can  also  be  compared  with
  266. objects of other types.  Of course they are never equal.
  267.  
  268. |    gap> f := Polynomial( GF(5^3), [1,2,3]*Z(5)^0 );
  269.     Z(5)^3*X(GF(5^3))^2 + Z(5)*X(GF(5^3)) + Z(5)^0
  270.     gap> x := Indeterminate(GF(25));;
  271.     gap> g := 3*x^2 + 2*x + 1;
  272.     Z(5)^3*X(GF(5^2))^2 + Z(5)*X(GF(5^2)) + Z(5)^0
  273.     gap> f = g;
  274.     false
  275.     gap> x^0 = Z(25)^0;
  276.     false|
  277.  
  278. '<f> \<\ <g>' \\
  279. '<f> \<= <g>' \\
  280. '<f> >   <g>' \\
  281. '<f> >=  <g>'
  282.  
  283. The  operators '\<', '\<=',  '>',  and '>='  evaluate  to 'true'  if  the
  284. polynomial <f>  is less than,  less than  or  equal  to, greater than, or
  285. greater than or equal to the polynomial <g>, and to 'false' otherwise.
  286.  
  287. A polynomial  <f> is  less than <g> if $v(<f>)$ is less than $v(<g>)$, or
  288. if $v(<f>)$ and $v(<g>)$  are equal and $d(<f>)$  is less  than $d(<g>)$.
  289. If $v(<f>)$ is equal to  $v(<g>)$ and  $d(<f>)$ is equal to $d(<g>)$  the
  290. coefficient lists of <f> and <g> are compared.
  291.  
  292. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  293.     gap> (1 + x^2 + x^3)*x^3 < (2 + x^2 + x^3);
  294.     false
  295.     gap> (1 + x^2 + x^4) < (2 + x^2 + x^3);    
  296.     false
  297.     gap> (1 + x^2 + x^3) < (2 + x^2 + x^3);
  298.     true|
  299.  
  300.  
  301. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  302. \Section{Operations for Polynomials}%
  303. \index{operations!for polynomials}
  304.  
  305. The following  operations  are  always available  for  polynomials.   The
  306. operands must  have a  common  base  ring, no  implicit  conversions  are
  307. performed.
  308.  
  309. '<f> + <g>'
  310.  
  311. The operator  '+'  evaluates to the sum of the polynomials <f>  and  <g>,
  312. which must be polynomials over a common base ring.
  313.  
  314. |    gap> f := Polynomial( GF(2), [Z(2), Z(2)] );
  315.     Z(2)^0*(X(GF(2)) + 1)
  316.     gap> f + f;
  317.     0*X(GF(2))^0
  318.     gap> g := Polynomial( GF(4), [Z(2), Z(2)] );
  319.     X(GF(2^2)) + Z(2)^0
  320.     gap> f + g;
  321.     Error, polynomials must have the same ring|
  322.  
  323. '<f> + <scl>' \\
  324. '<scl> + <f>'
  325.  
  326. The operator '+'  evaluates to  the  sum of the  polynomial  <f>  and the
  327. scalar <scl>, which must lie in the base ring of <f>.
  328.  
  329. |    gap> x := Indeterminate( Integers );; x.name := "x";;
  330.     gap> h := Polynomial( Integers, [1,2,3,4] );
  331.     4*x^3 + 3*x^2 + 2*x + 1
  332.     gap> h + 1;
  333.     4*x^3 + 3*x^2 + 2*x + 2
  334.     gap> 1/2 + h;
  335.     Error, <l> must lie in the base ring of <r>|
  336.  
  337. '<f> - <g>'
  338.  
  339. The operator '-' evaluates  to  the difference of the polynomials <f> and
  340. <g>, which must be polynomials over a common base ring.
  341.  
  342. |    gap> x := Indeterminate( Integers );; x.name := "x";;
  343.     gap> h := Polynomial( Integers, [1,2,3,4] );
  344.     4*x^3 + 3*x^2 + 2*x + 1
  345.     gap> h - 2*h;
  346.     -4*x^3 - 3*x^2 - 2*x - 1|
  347.  
  348. '<f> - <scl>' \\
  349. '<scl> - <f>'
  350.  
  351. The operator '-' evaluates  to the difference of  the  polynomial <f> and
  352. the scalar <scl>, which must lie in the base ring of <f>.
  353.  
  354.  
  355. |    gap> x := Indeterminate( Integers );; x.name := "x";;
  356.     gap> h := Polynomial( Integers, [1,2,3,4] );
  357.     4*x^3 + 3*x^2 + 2*x + 1
  358.     gap> h - 1;
  359.     4*x^3 + 3*x^2 + 2*x
  360.     gap> 1 - h;
  361.     -4*x^3 - 3*x^2 - 2*x|
  362.  
  363. '<f> \*\ <g>'
  364.  
  365. The operator '\*' evaluates to the product of the two polynomials <f> and
  366. <g>, which must be polynomial over a common base ring.
  367.  
  368. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  369.     gap> h := 4*x^3 + 3*x^2 + 2*x + 1;
  370.     4*x^3 + 3*x^2 + 2*x + 1
  371.     gap> h * h;
  372.     16*x^6 + 24*x^5 + 25*x^4 + 20*x^3 + 10*x^2 + 4*x + 1|
  373.  
  374. '<f> \*\ <scl>' \\
  375. '<scl> \*\ <f>'
  376.  
  377. The operator '\*' evaluates to the product of the polynomial <f>  and the
  378. scalar <scl>, which must lie in the base ring of <f>.
  379.  
  380. |    gap> f := Polynomial( GF(2), [Z(2), Z(2)] );
  381.     Z(2)^0*(X(GF(2)) + 1)
  382.     gap> f - Z(2);
  383.     X(GF(2))
  384.     gap> Z(4) - f;
  385.     Error, <l> must lie in the base ring of <r>|
  386.  
  387. '<f> \^\ <n>'
  388.  
  389. The operator '\^' evaluates the the <n>-th power  of the  polynomial <f>.
  390. If <n> is negative '\^'  will try to invert <f> in the Laurent polynomial
  391. ring ring.
  392.  
  393. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  394.     gap> k := x - 1 + x^-1;
  395.     x - 1 + x^(-1)
  396.     gap> k ^ 3;
  397.     x^3 - 3*x^2 + 6*x - 7 + 6*x^(-1) - 3*x^(-2) + x^(-3)
  398.     gap> k^-1;
  399.     Error, cannot invert <l> in the laurent polynomial ring|
  400.  
  401. '<f> / <scl>'
  402.  
  403. The operator  '/' evaluates to  the product of the polynomial <f> and the
  404. inverse  of the scalar  <scl>, which  must be  invertable in  its default
  405. ring.
  406.  
  407. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  408.     gap> h := 4*x^3 + 3*x^2 + 2*x + 1;
  409.     4*x^3 + 3*x^2 + 2*x + 1
  410.     gap> h / 3;
  411.     (4/3)*x^3 + x^2 + (2/3)*x + (1/3) |
  412.  
  413. '<scl> / <f>'
  414.  
  415. The  operator '/' evaluates to  the  product of the scalar <scl>  and the
  416. inverse of the  polynomial <f>, which  must  be invertable in its Laurent
  417. ring.
  418.  
  419. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  420.     gap> 30 / x;
  421.     30*x^(-1)
  422.     gap> 3 / (1+x);
  423.     Error, cannot invert <l> in the laurent polynomial ring |
  424.  
  425. '<f> / <g>'
  426.  
  427. The operator '/' evaluates to the quotient of the two polynomials <f> and
  428. <g>, if such quotient exists. Otherwise '/' signals an error.
  429.  
  430. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  431.     gap> f := (1+x+x^2) * (3-x-2*x^2);
  432.     -2*x^4 - 3*x^3 + 2*x + 3
  433.     gap> f / (1+x+x^2);
  434.     -2*x^2 - x + 3
  435.     gap> f / (1+x);
  436.     Error, cannot divide <l> by <r> |
  437.  
  438. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  439. \Section{Degree}
  440.  
  441. 'Degree( <f> )'
  442.  
  443. 'Degree' returns the degree $d_<f>$ of $f$ (see "Polynomials").
  444.  
  445. Note that  this  is only equal to  the Euclidean degree in the polynomial
  446. ring $P(R)$. It is not equal in the Laurent polynomial ring $L(R)$.
  447.  
  448. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  449.     gap> Degree( x^10 + x^2 + 1 );
  450.     10
  451.     gap> EuclideanDegree( x^10 + x^2 + 1 );
  452.     10      # the default ring is the polynomial ring
  453.     gap> Degree( x^-10 + x^-11 );
  454.     -10
  455.     gap> EuclideanDegree( x^-10 + x^-11 );
  456.     1       # the default ring is the Laurent polynomial ring|
  457.  
  458.  
  459. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  460. \Section{LeadingCoefficient}
  461.  
  462. 'LeadingCoefficient( <f> )'
  463.  
  464. 'LeadingCoefficient' returns the  last non-zero  coefficient  of <f> (see
  465. "Polynomials").
  466.  
  467. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  468.     gap> LeadingCoefficient( 3*x^2 + 2*x + 1);
  469.     3 |
  470.  
  471.  
  472. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  473. \Section{Value}
  474.  
  475. 'Value( <f>, <w> )'
  476.  
  477. Let <f> be  a Laurent  polynomial $(..., f_{-1}, f_0,  f_1,  ...)$.  Then
  478. 'Value' returns the finite sum $... +  f_{-1} <w>^{-1} + f_0 <w>^0 +  f_1
  479. <w> + ...$.
  480.  
  481. Note that <x> need not be contained in the base ring of <f>.
  482.  
  483. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  484.     gap> k := -x + 1;
  485.     -x + 1
  486.     gap> Value( k, 2 );
  487.     -1
  488.     gap> Value( k, [[1,1],[0,1]] );
  489.     [ [ 0, -1 ], [ 0, 0 ] ]|
  490.  
  491.  
  492. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  493. \Section{Derivative}
  494.  
  495. 'Derivative( <f> )'
  496.  
  497. Let  <f> be a Laurent  polynomial $(..., f_{-1},  f_0,  f_1,  ...)$. Then
  498. 'Derivative' returns the polynomial $g = (..., g_{i-1} = i\* f_i, ... )$.
  499.  
  500. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  501.     gap> Derivative( x^10 + x^-11 );
  502.     10*x^9 - 11*x^(-12)
  503.     gap> y := Indeterminate(GF(5));; y.name := "y";;    
  504.     gap> Derivative( y^10 + y^-11 );
  505.     Z(5)^2*y^(-12)|
  506.  
  507.  
  508. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  509. \Section{PolynomialRing}
  510.  
  511. 'PolynomialRing( <R> )'
  512.  
  513. 'PolynomialRing' returns the ring of all polynomials  over a field <R> or
  514. ring-with-one <R>.
  515.  
  516. |    gap> f2 := GF(2);;                
  517.     gap> R := PolynomialRing( f2 );
  518.     PolynomialRing( GF(2) )
  519.     gap> Z(2) in R;
  520.     false
  521.     gap> Polynomial( f2, [Z(2),Z(2)] ) in R;
  522.     true
  523.     gap> Polynomial( GF(4), [Z(2),Z(2)] ) in R;
  524.     false
  525.     gap> R := PolynomialRing( GF(2) );
  526.     PolynomialRing( GF(2) )|
  527.  
  528.  
  529. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  530. \Section{IsPolynomialRing}
  531.  
  532. 'IsPolynomialRing( <domain> )'
  533.  
  534.  
  535. 'IsPolynomialRing'  returns 'true'  if  the object  <domain>  is  a  ring
  536. record,  representing  a  polynomial  ring  (see  "PolynomialRing"),  and
  537. 'false' otherwise.
  538.     
  539. |    gap> IsPolynomialRing( Integers );                  
  540.     false
  541.     gap> IsPolynomialRing( PolynomialRing( Integers ) );
  542.     true
  543.     gap> IsPolynomialRing( LaurentPolynomialRing( Integers ) );
  544.     false |
  545.  
  546.  
  547. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  548. \Section{LaurentPolynomialRing}
  549.  
  550. 'LaurentPolynomialRing( <R> )'
  551.  
  552. 'LaurentPolynomialRing'  returns the ring of all Laurent polynomials over
  553. a field <R> or ring-with-one <R>.
  554.  
  555. |    gap> f2 := GF(2);;
  556.     gap> R := LaurentPolynomialRing( f2 );
  557.     LaurentPolynomialRing( GF(2) )
  558.     gap> Z(2) in R;
  559.     false
  560.     gap> Polynomial( f2, [Z(2),Z(2)] ) in R;   
  561.     true
  562.     gap> Polynomial( GF(4), [Z(2),Z(2)] ) in R;
  563.     false
  564.     gap> Indeterminate(f2)^-1 in R;
  565.     true|
  566.  
  567.  
  568. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  569. \Section{IsLaurentPolynomialRing}
  570.  
  571. 'IsLaurentPolynomialRing( <domain> )'
  572.  
  573. 'IsLaurentPolynomialRing' returns 'true' if the object <domain> is a ring
  574. record,    representing     a    Laurent     polynomial     ring     (see
  575. "LaurentPolynomialRing"), and 'false' otherwise.
  576.     
  577. |    gap> IsPolynomialRing( Integers );                  
  578.     false
  579.     gap> IsLaurentPolynomialRing( PolynomialRing( Integers ) );
  580.     false
  581.     gap> IsLaurentPolynomialRing( LaurentPolynomialRing( Integers ) );
  582.     true |
  583.  
  584.  
  585. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  586. \Section{Ring Functions for Polynomial Rings}
  587.  
  588. As was already noted in the introduction to this chapter polynomial rings
  589. are rings, so all ring functions (see chapter "Rings") are  applicable to
  590. polynomial rings.  This section comments on the implementation  of  those
  591. functions.
  592.  
  593. Let $R$ be  a  commutative ring-with-one or  a field and  let <P>  be the
  594. polynomial ring over $R$.
  595.  
  596. \vspace{5mm}
  597. 'EuclideanDegree( <P>, <f> )'
  598.  
  599. <P> is an Euclidean ring if  and only if $R$  is field. In this case  the
  600. Euclidean  degree  of <f> is simply the degree  of  <f>.  If $R$ is not a
  601. field then the function signals an error.
  602.  
  603. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  604.     gap> EuclideanDegree( x^10 + x^2 + 1 );
  605.     10
  606.     gap> EuclideanDegree( x^0 );
  607.     0 |
  608.  
  609. \vspace{5mm}
  610. 'Gcd( <P>, <f>, <g> )'
  611.  
  612. <P> is an Euclidean ring  if and only if $R$  is field. In this case  you
  613. can compute the greatest common divisor of <f> and <g> using 'Gcd'.
  614.  
  615. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  616.     gap> g := x^2 + 2*x + 1;;
  617.     gap> h := x^2 - 1;;
  618.     gap> Gcd( g, h );
  619.     x + 1
  620.     gap> GcdRepresentation( g, h );
  621.     [ 1/2*x^0, -1/2*x^0 ]
  622.     gap> g * (1/2) * x^0 - h * (1/2) * x^0;
  623.     x + 1 |
  624.  
  625. \vspace{5mm}
  626. 'Factors( <P>, <f> )'
  627.  
  628. This method is only implemented for a polynomial ring  <P>  over a finite
  629. field  $R$.  In  this  case <f>  is  factored using  a  Cantor-Zassenhaus
  630. algorithm. As <f> is  an element  of <P> if and only  if the base ring of
  631. <f> is $R$ you  must embed the polynomial into the polynomial ring <P> if
  632. it is written as polynomial over a subring.
  633.  
  634. |    gap> f5 := GF(5);; f5.name := "f5";;
  635.     gap> x  := Indeterminate(f5);; x.name := "x";;
  636.     gap> g := x^20 + x^8 + 1;
  637.     Z(5)^0*(x^20 + x^8 + 1)
  638.     gap> Factors(g);
  639.     [ Z(5)^0*(x^8 + 4*x^4 + 2), Z(5)^0*(x^12 + x^8 + 4*x^4 + 3) ]
  640.     gap> f25 := GF(25);; Indeterminate(f25).name := "y";;
  641.     gap> l := Factors( EmbeddedPolynomial( PolynomialRing(f25), g ) );   
  642.     [ y^4 + Z(5^2)^13, y^4 + Z(5^2)^17, y^6 + Z(5)^3*y^2 + Z(5^2)^3, 
  643.       y^6 + Z(5)^3*y^2 + Z(5^2)^15 ]
  644.     gap> l[1] * l[2];
  645.     y^8 + Z(5)^2*y^4 + Z(5)
  646.     gap> l[3] * l[4];
  647.     y^12 + y^8 + Z(5)^2*y^4 + Z(5)^3 |
  648.  
  649.  
  650. \vspace{5mm}
  651. 'StandardAssociate( <P>, <f> )'
  652.  
  653. For a  ring $R$ the standard associate $a$  of  <f>  is a multiple of <f>
  654. such  that the leading  coefficient of <a> is the  standard associate  in
  655. $R$. For  a field $R$ the standard associate  $a$ of <f> is a multiple of
  656. <f> such that the leading coefficient of <a> is 1.
  657.  
  658. |    gap> x := Indeterminate(Integers);; x.name := "x";; 
  659.     gap> StandardAssociate( -2 * x^3 - x );
  660.     2*x^3 + x|
  661.  
  662. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  663. \Section{Ring Functions for Laurent Polynomial Rings}
  664.  
  665. As  was  already  noted  in the  introduction  to  this  chapter  Laurent
  666. polynomial rings are rings,  so all ring functions (see chapter  "Rings")
  667. are applicable  to  polynomial  rings.   This  section  comments  on  the
  668. implementation of those functions.
  669.  
  670. Let $R$ be a commutative ring-with-one or a  field  and  let <P>  be  the
  671. polynomial ring over $R$.
  672.  
  673. \vspace{5mm}
  674. 'EuclideanDegree( <P>, <f> )'
  675.  
  676. <P> is  an Euclidean ring if and only  if $R$ is field. In  this case the
  677. Euclidean  degree of <f> is  the  difference of $d(f)$  and  $v(f)$  (see
  678. "Polynomials"). If $R$ is not a field then the function signals an error.
  679.  
  680. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  681.     gap> LR := LaurentPolynomialRing(Rationals);;
  682.     gap> EuclideanDegree( LR, x^10 + x^2 );
  683.     8
  684.     gap> EuclideanDegree( LR, x^7 );
  685.     0
  686.     gap> EuclideanDegree( x^7 );
  687.     7
  688.     gap> EuclideanDegree( LR, x^2 + x^-2 );
  689.     4
  690.     gap> EuclideanDegree( x^2 + x^-2 );
  691.     4 |
  692.  
  693. \vspace{5mm}
  694. 'Gcd( <P>, <f>, <g> )'
  695.  
  696. <P> is an Euclidean ring  if and only if $R$  is field. In this case  you
  697. can compute the greatest common divisor of <f> and <g> using 'Gcd'.
  698.  
  699. |    gap> x := Indeterminate(Rationals);; x.name := "x";;
  700.     gap> LR := LaurentPolynomialRing(Rationals);;
  701.     gap> g := x^3 + 2*x^2 + x;;
  702.     gap> h := x^3 - x;;
  703.     gap> Gcd( g, h );
  704.     x^2 + x
  705.     gap> Gcd( LR, g, h );
  706.     x + 1     # 'x' is a unit in 'LR'
  707.     gap> GcdRepresentation( LR, g, h );
  708.     [ (1/2)*x^(-1), (-1/2)*x^(-1) ] |
  709.  
  710. \vspace{5mm}
  711. 'Factors( <P>, <f> )'
  712.  
  713. This method is only implemented for a Laurent  polynomial ring <P> over a
  714. finite field $R$.  In this case <f> is factored using a Cantor-Zassenhaus
  715. algorithm.  As <f>  is an element  of <P> if and only if the base ring of
  716. <f> is $R$ you must embed the polynomial into the polynomial  ring <P> if
  717. it is written as polynomial over a subring.
  718.  
  719. |    gap> f5 := GF(5);; f5.name := "f5";;
  720.     gap> x  := Indeterminate(f5);; x.name := "x";;
  721.     gap> g := x^10 + x^-2 + x^-10;
  722.     Z(5)^0*(x^10 + x^(-2) + x^(-10))
  723.     gap> Factors(g);
  724.     [ Z(5)^0*(x^(-2) + 4*x^(-6) + 2*x^(-10)),
  725.       Z(5)^0*(x^12 + x^8 + 4*x^4 + 3) ]
  726.     gap> f25 := GF(25);; Indeterminate(f25).name := "y";;
  727.     gap> gg := EmbeddedPolynomial( LaurentPolynomialRing(f25), g );
  728.     y^10 + y^(-2) + y^(-10)
  729.     gap> l := Factors( gg );
  730.     [ y^(-6) + Z(5^2)^13*y^(-10), y^4 + Z(5^2)^17,
  731.       y^6 + Z(5)^3*y^2 + Z(5^2)^3, y^6 + Z(5)^3*y^2 + Z(5^2)^15 ]
  732.     gap> l[1] * l[2];
  733.     y^(-2) + Z(5)^2*y^(-6) + Z(5)*y^(-10)
  734.     gap> l[3]*[4];
  735.     [ Z(5)^2*y^6 + Z(5)*y^2 + Z(5^2)^15 ]|
  736.  
  737. \vspace{5mm}
  738. 'StandardAssociate( <P>, <f> )'
  739.  
  740. For a ring $R$ the standard  associate $a$  of  <f> is a multiple of  <f>
  741. such that the leading coefficient of <a> is the standard associate in $R$
  742. and $v(<a>)$ is zero. For a field $R$ the  standard  associate $a$ of <f>
  743. is a multiple of <f> such  that the leading coefficient  of <a>  is 1 and
  744. $v(<a>)$ is zero.
  745.  
  746. |    gap> x := Indeterminate(Integers);; x.name := "x";;
  747.     gap> LR := LaurentPolynomialRing(Integers);;
  748.     gap> StandardAssociate( LR, -2 * x^3 - x );
  749.     2*x^2 + 1|
  750.  
  751. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  752. %E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local Emacs variables
  753. %%
  754. %%  Local Variables:
  755. %%  mode:               outline
  756. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section\\|%E"
  757. %%  fill-column:        73
  758. %%  eval:               (hide-body)
  759. %%  End:
  760. %%
  761.