4 Monoid Polynomials
  
  This  chapter  describes  functions  to  compute  with  elements  of  a free
  noncommutative  algebra.  The  elements  of the algebra are sums of rational
  multiples  of  words  in a free monoid. These are called monoid polynomials,
  and are stored as lists of pairs [coefficient, word].
  
  
  4.1 Construction of monoid polynomials
  
  4.1-1 MonoidPolyFromCoeffsWords
  
  > MonoidPolyFromCoeffsWords( coeffs, words ) ______________________operation
  > MonoidPoly( terms ) _____________________________________________operation
  > ZeroMonoidPoly( F ) _____________________________________________operation
  
  There are two ways to input a monoid polynomial: by listing the coefficients
  and then the words; or by listing the terms as a list of pairs [coefficient,
  word].  If  a word occurs more than once in the input list, the coefficients
  will  be  added  so  that the terms of the monoid polynomial recorded do not
  contain any duplicates. The zero monoid polynomial is the polynomial with no
  terms.
  
  ---------------------------  Example  ----------------------------
    
    gap> rels := RelatorsOfFpGroup( q8 );
    [ f1^4, f2^4, f1*f2*f1*f2^-1, f1^2*f2^2 ] 
    gap> freeq8 := FreeGroupOfFpGroup( q8 );; 
    gap> gens := GeneratorsOfGroup( freeq8 );;
    gap> famfree := ElementsFamily( FamilyObj( freeq8 ) );;
    gap> famfree!.monoidPolyFam := MonoidPolyFam;;
    gap> cg := [6,7];; 
    gap> pg := MonoidPolyFromCoeffsWords( cg, gens );; 
    gap> Display( pg ); 
    7*f2 + 6*f1
    gap> cr := [3,4,-5,-2];;
    gap> pr := MonoidPolyFromCoeffsWords( cr, rels );; 
    gap> Display( pr );
    4*f2^4 - 5*f1*f2*f1*f2^-1 - 2*f1^2*f2^2 + 3*f1^4
    gap> Display( ZeroMonoidPoly( freeq8 ) );
    zero monpoly
    
  ------------------------------------------------------------------
  
  
  4.2 Components of a polynomial
  
  4.2-1 Terms
  
  > Terms( poly ) ___________________________________________________attribute
  > Coeffs( poly ) __________________________________________________attribute
  > Words( poly ) ___________________________________________________attribute
  > LeadTerm( poly ) ________________________________________________attribute
  > LeadCoeffMonoidPoly( poly ) _____________________________________attribute
  
  The  function  Terms returns the terms of a polynomial as a list of pairs of
  the  form  [word, coefficient]. The function Coeffs returns the coefficients
  of  a  polynomial  as  a list, and the function Words returns the words of a
  polynomial  as  a  list.  The  function  LeadTerm  returns  the  term of the
  polynomial  whose  word  component  is  the  largest  with  respect  to  the
  length-lexicographical  ordering.  The  function LeadCoeffMonoidPoly returns
  the coefficient of the leading term of a polynomial.
  
  ---------------------------  Example  ----------------------------
    
    gap> Coeffs( pr );
    [ 4, -5, -2, 3 ]
    gap> Terms( pr );
    [ [ 4, f2^4 ], [ -5, f1*f2*f1*f2^-1 ], [ -2, f1^2*f2^2 ], [ 3, f1^4 ] ]
    gap> Words( pr );
    [ f2^4, f1*f2*f1*f2^-1, f1^2*f2^2, f1^4 ]
    gap> LeadTerm( pr );
    [ 4, f2^4]
    gap> LeadCoeffMonoidPoly( pr );
    4
    
  ------------------------------------------------------------------
  
  4.2-2 Monic
  
  > Monic( poly ) ___________________________________________________operation
  
  A  monoid  polynomial  is  called  monic  if  the coefficient of its leading
  polynomial  is  one.  The  function Monic converts a polynomial into a monic
  polynomial by dividing all the coefficients by the leading coefficient.
  
  ---------------------------  Example  ----------------------------
    
    gap> mpr := Monic( pr );;
    gap> Display( mpr );
    f2^4 - 5/4*f1*f2*f1*f2^-1 - 1/2*f1^2*f2^2 + 3/4*f1^4
    
  ------------------------------------------------------------------
  
  4.2-3 AddTermMonoidPoly
  
  > AddTermMonoidPoly( poly, coeff, word ) __________________________operation
  
  The  function  AddTermMonoidPoly  adds a new term, given by its coeffiecient
  and word, to an existing polynomial.
  
  ---------------------------  Example  ----------------------------
    
    gap> w := gens[1]^gens[2];
    f2^-1*f1*f2
    gap> cw := 3/4;;
    gap> wpg:= AddTermMonoidPoly( pg, cw, w);;
    gap> Display( wpg );
    3/4*f2^-1*f1*f2 + 7*f2 + 6*f1
    
  ------------------------------------------------------------------
  
  
  4.3 Monoid Polynomial Operations
  
  Tests for equality and arithmetic operations are performed in the usual way.
  
  The  operation poly1 = poly2 returns true if the monoid polynomials have the
  same  terms,  and false otherwise. Multiplication of a monoid polynomial (on
  the  left  or  right)  by  a coefficient; the addition or subtraction of two
  monoid  polynomials; multiplication (on the right) of a monoid polynomial by
  a word; and multiplication of two monoid polynomials; are all implemented.
  
  ---------------------------  Example  ----------------------------
    
    gap> [ pg = pg, pg = pr ];
    [ true, false ]
    gap> prcw := pr*cw;;
    gap> Display( prcw );
    3*f2^4 - 15/4*f1*f2*f1*f2^-1 - 3/2*f1^2*f2^2 + 9/4*f1^4
    gap> cwpr := cw*pr;; 
    gap> Display( cwpr ); 
    3*f2^4 - 15/4*f1*f2*f1*f2^-1 - 3/2*f1^2*f2^2 + 9/4*f1^4
    gap> [ pr = prcw, prcw = cwpr ];
    [ false, true ] 
    gap> Display( pg + pr );
    4*f2^4 - 5*f1*f2*f1*f2^-1 - 2*f1^2*f2^2 + 3*f1^4 + 7*f2 + 6*f1 
    gap> Display( pg - pr );
    - 4*f2^4 + 5*f1*f2*f1*f2^-1 + 2*f1^2*f2^2 - 3*f1^4 + 7*f2 + 6*f1
    gap> Display( pg * w );
    6*f1*f2^-1*f1*f2 + 7*f1*f2 
    gap> Display( pg * pr );
    28*f2^5 - 35*f2*f1*f2*f1*f2^-1 - 14*f2*f1^2*f2^2 + 21*f2*f1^4 
    + 24*f1*f2^4 - 30*f1^2*f2*f1*f2^-1 - 12*f1^3*f2^2 + 18*f1^5 
    
  ------------------------------------------------------------------
  
  4.3-1 Length
  
  > Length( poly ) __________________________________________________attribute
  
  This function returns the number of distinct terms in the monoid polynomial.
  
  ---------------------------  Example  ----------------------------
    
    gap> Length( pr );
    4
    
  ------------------------------------------------------------------
  
  The  boolean function poly1 > poly2 returns true if the first polynomial has
  more  terms  than the second. If the polynomials are the same length it will
  compare   their  leading  terms.  If  the  leading  word  of  the  first  is
  lengthlexicographically  greater  than the leading word of the second, or if
  the  words  are  equal  but the coefficient of the first is greater than the
  coefficient  of  the  second then true is returned. If the leading terms are
  equal then the next terms are compared in the same way. If all terms are the
  same then false is returned.
  
  ---------------------------  Example  ----------------------------
    
    gap> [ pr > 3*pr, pr > pg ];
    [ false, true ] 
    
  ------------------------------------------------------------------
  
  
  4.4 Reduction of a Monoid Polynomial
  
  4.4-1 ReduceMonoidPoly
  
  > ReduceMonoidPoly( poly, rules ) _________________________________operation
  
  Recall  that the words of a monoid polynomial are elements of a free monoid.
  Given  a  rewrite  system (set of rules) on the free monoid the words can be
  reduced.  This  allows  us to simulate calculation in monoid rings where the
  monid  is  given by a complete presentation. This function reduces the words
  of the polynomial (elements of the free monoid) with respect to the complete
  rewrite system. The words of the reduced polynomial are normal forms for the
  elements of the monoid presented by that rewite system. The list of rules r2
  is displayed in section 2.3.3.
  
  ---------------------------  Example  ----------------------------
    
    gap> M := genfgmon;;
    gap> mp1 := MonoidPolyFromCoeffsWords( [9,-7,5], [M[1]*M[3], M[2]^3, M[4]*M[3]*M[2]] );; 
    gap> Display( mp1 ); 
    5*q8_M4*q8_M3*q8_M2 - 7*q8_M2^3 + 9*q8_M1*q8_M3
    gap> rmp1 := ReduceMonoidPoly( mp1, r2 );;
    gap> Display( rmp1 ); 
     - 7*q8_M4 + 5*q8_M1 + 9*<identity ...>
    
  ------------------------------------------------------------------