  
  [1m[4m[31m4. Monoid Polynomials[0m
  
  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  will  be  called  monoid
  polynomials, and are stored as lists of pairs [22m[32m[coefficient, word][0m.
  
  
  [1m[4m[31m4.1 Construction of monoid polynomials[0m
  
  [1m[4m[31m4.1-1 MonoidPolyFromCoeffsWords[0m
  
  [1m[34m> MonoidPolyFromCoeffsWords( [0m[22m[34mcoeffs, words[0m[1m[34m ) ______________________[0moperation
  [1m[34m> MonoidPoly( [0m[22m[34mterms[0m[1m[34m ) _____________________________________________[0moperation
  [1m[34m> ZeroMonoidPoly( [0m[22m[34mF[0m[1m[34m ) _____________________________________________[0moperation
  
  There  are  two  possible ways to input a monoid polynomial. The first is by
  listing  the  coefficients  and then the words; the second is by listing the
  terms  as  a  list  of pairs [22m[32m[coefficient, word][0m. Note that 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.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> rels := RelatorsOfFpGroup( q8 );[0m
    [22m[35m[ f1^4, f2^4, f1*f2*f1*f2^-1, f1^2*f2^2 ] [0m
    [22m[35mgap> freeq8 := FreeGroupOfFpGroup( q8 ); [0m
    [22m[35mGroup( [f1, f2] )[0m
    [22m[35mgap> gens := GeneratorsOfGroup( freeq8 );;[0m
    [22m[35mgap> famfree := ElementsFamily( FamilyObj( freeq8 ) );[0m
    [22m[35mNewFamily( "FreeGroupElementsFamily", [ 125, 144, 989 ], [0m
    [22m[35m[ 76, 77, 78, 79, 111, 114, 117, 121, 125, 144, 989 ] )[0m
    [22m[35mgap> famfree!.monoidPolyFam := MonoidPolyFam;[0m
    [22m[35mNewFamily( "MonoidPolyFam", [ 2416 ], [ 111, 114, 117, 2416 ] )[0m
    [22m[35mgap> cg := [6,7];[0m
    [22m[35m[ 6, 7 ][0m
    [22m[35mgap> cr := [3,4,-5,-2];[0m
    [22m[35m[ 3, 4, -5, -2 ][0m
    [22m[35mgap> pg := MonoidPolyFromCoeffsWords( cg, gens );[0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( pg );[0m
    [22m[35m7*f2 + 6*f1 [0m
    [22m[35mgap> pr := MonoidPolyFromCoeffsWords( cr, rels );[0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( pr );[0m
    [22m[35m4*f2^4 - 5*f1*f2*f1*f2^-1 - 2*f1^2*f2^2 + 3*f1^4[0m
    [22m[35mgap> zeromp := ZeroMonoidPoly( freeq8 );[0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( zeromp);[0m
    [22m[35mzero monpoly [0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m4.2 Components of a polynomial[0m
  
  [1m[4m[31m4.2-1 Terms[0m
  
  [1m[34m> Terms( [0m[22m[34mpoly[0m[1m[34m ) ___________________________________________________[0mattribute
  [1m[34m> Coeffs( [0m[22m[34mpoly[0m[1m[34m ) __________________________________________________[0mattribute
  [1m[34m> Words( [0m[22m[34mpoly[0m[1m[34m ) ___________________________________________________[0mattribute
  [1m[34m> LeadTerm( [0m[22m[34mpoly[0m[1m[34m ) ________________________________________________[0mattribute
  [1m[34m> LeadCoeffMonoidPoly( [0m[22m[34mpoly[0m[1m[34m ) _____________________________________[0mattribute
  
  The  function  [22m[32mTerms[0m returns the terms of a polynomial as a list of pairs of
  the  form  [22m[32m[word, coefficient][0m. The function [22m[32mCoeffs[0m returns the coefficients
  of  a  polynomial  as  a list, and the function [22m[32mWords[0m returns the words of a
  polynomial  as  a  list.  The  function  [22m[32mLeadTerm[0m  returns  the  term of the
  polynomial  whose  word  component  is  the  largest  with  respect  to  the
  length-lexicographical  ordering.  The  function [22m[32mLeadCoeffMonoidPoly[0m returns
  the coefficient of the leading term of a polynomial.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Coeffs( pr );[0m
    [22m[35m[ 4, -5, -2, 3 ][0m
    [22m[35mgap> Terms( pr );[0m
    [22m[35m[ [ 4, f2^4 ], [ -5, f1*f2*f1*f2^-1 ], [ -2, f1^2*f2^2 ], [ 3, f1^4 ] ][0m
    [22m[35mgap> Words( pr );[0m
    [22m[35m[ f2^4, f1*f2*f1*f2^-1, f1^2*f2^2, f1^4 ][0m
    [22m[35mgap> LeadTerm( pr );[0m
    [22m[35m[ 4, f2^4][0m
    [22m[35mgap> LeadCoeffMonoidPoly( pr );[0m
    [22m[35m4[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.2-2 Monic[0m
  
  [1m[34m> Monic( [0m[22m[34mpoly[0m[1m[34m ) ___________________________________________________[0moperation
  
  A  monoid  polynomial  is  called  [22m[36mmonic[0m  if  the coefficient of its leading
  polynomial  is  one.  The  function [22m[32mMonic[0m converts a polynomial into a monic
  polynomial by dividing all the coefficients by the leading coefficient.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> mpr := Monic( pr );;[0m
    [22m[35mgap> Print( mpr );[0m
    [22m[35mf2^4 - 5/4*f1*f2*f1*f2^-1 - 1/2*f1^2*f2^2 + 3/4*f1^4[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.2-3 AddTermMonoidPoly[0m
  
  [1m[34m> AddTermMonoidPoly( [0m[22m[34mpoly, coeff, word[0m[1m[34m ) __________________________[0moperation
  
  The  function  [22m[32mAddTermMonoidPoly[0m  adds a new term, given by its coeffiecient
  and word, to an existing polynomial.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> w := gens[1]^gens[2];[0m
    [22m[35mf2^-1*f1*f2[0m
    [22m[35mgap> cw := 3/4;;[0m
    [22m[35mgap> wpg:= AddTermMonoidPoly( pg, cw, w);[0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( wpg );[0m
    [22m[35m3/4*f2^-1*f1*f2 + 7*f2 + 6*f1[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m4.3 Monoid Polynomial Operations[0m
  
  Tests for equality and arithmetic operations are performed in the usual way.
  
  The  operation [22m[32mpoly1 = poly2[0m returns [22m[32mtrue[0m if the monoid polynomials have the
  same  terms,  and [22m[32mfalse[0m 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.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> pg = pg;[0m
    [22m[35mtrue [0m
    [22m[35mgap> pg = pr;[0m
    [22m[35mfalse [0m
    [22m[35mgap> prcw := pr*cw;[0m
    [22m[35m3*f2^4 - 15/4*f1*f2*f1*f2^-1 - 3/2*f1^2*f2^2 + 9/4*f1^4[0m
    [22m[35mgap> cwpr := cw*pr;[0m
    [22m[35m3*f2^4 - 15/4*f1*f2*f1*f2^-1 - 3/2*f1^2*f2^2 + 9/4*f1^4[0m
    [22m[35mgap> pr = prcw;[0m
    [22m[35mfalse [0m
    [22m[35mgap> prcw = cwpr;[0m
    [22m[35mtrue [0m
    [22m[35mgap> Print( pg + pr );[0m
    [22m[35m4*f2^4 - 5*f1*f2*f1*f2^-1 - 2*f1^2*f2^2 + 3*f1^4 + 7*f2 + 6*f1 [0m
    [22m[35mgap> Print( pg - pr );[0m
    [22m[35m- 4*f2^4 + 5*f1*f2*f1*f2^-1 + 2*f1^2*f2^2 - 3*f1^4 + 7*f2 + 6*f1[0m
    [22m[35mgap> Print( pg * w );[0m
    [22m[35m6*f1*f2^-1*f1*f2 + 7*f1*f2 [0m
    [22m[35mgap> Print( pg * pr );[0m
    [22m[35m28*f2^5 - 35*f2*f1*f2*f1*f2^-1 - 14*f2*f1^2*f2^2 + 21*f2*f1^4 [0m
    [22m[35m+ 24*f1*f2^4 - 30*f1^2*f2*f1*f2^-1 - 12*f1^3*f2^2 + 18*f1^5 [0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  [1m[4m[31m4.3-1 Length[0m
  
  [1m[34m> Length( [0m[22m[34mpoly[0m[1m[34m ) __________________________________________________[0mattribute
  
  This function returns the number of distinct terms in the monoid polynomial.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> Length( pr );[0m
    [22m[35m4[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  The  boolean function [22m[32mpoly1 > poly2[0m returns [22m[32mtrue[0m 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 [22m[32mfalse[0m is returned.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> pol > 3*pol;[0m
    [22m[35mfalse [0m
    [22m[35mgap> pol > redpol;[0m
    [22m[35mtrue[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
  
  [1m[4m[31m4.4 Reduction of a Monoid Polynomial[0m
  
  [1m[4m[31m4.4-1 ReduceMonoidPoly[0m
  
  [1m[34m> ReduceMonoidPoly( [0m[22m[34mpoly, rules[0m[1m[34m ) _________________________________[0moperation
  
  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.
  
  [22m[35m---------------------------  Example  ----------------------------[0m
    [22m[35m[0m
    [22m[35mgap> M := genfgmon;[0m
    [22m[35m[ q8_Ml, q8_M2, q8_M3, q8_M4 ] [0m
    [22m[35mgap> r2;[0m
    [22m[35m[ q8_Ml*q8_M3, <identity ...>], [ q8_M2*q8_Ml, q8_Ml*q8_M4 ], [0m
    [22m[35m  [ q8_M2^2, q8_Ml^2], [ q8_M2*q8_M3, q8_Ml*q8_M2 ], [0m
    [22m[35m  [ q8_M2*q8_M4, <identity ...> ], [ q8_M3*q8_Ml, <identity ...> ], [0m
    [22m[35m  [ q8_M3*q8_M2, q8_Ml*q8_M4], [ q8_M3^2, q8_Ml^2 ], [0m
    [22m[35m  [ q8_M3*q8_M4, q8_Ml*q8_M2], [ q8_M4*q8_Ml, q8_Ml*q8_M2 ], [0m
    [22m[35m  [ q8_M4*q8_M2, <identity ...> ], [ q8_M4*q8_M3, q8_Ml*q8_M4 ], [0m
    [22m[35m  [ q8_M4^2, q8_Ml^2 ], [ q8_Ml^3, q8_M3], [ q8_Ml^2*q8_M2, q8_M4 ], [0m
    [22m[35m  [ q8_Ml^2*q8_M4, q8_M2 ] ] [0m
    [22m[35mgap> pol := MonoidPolyFromCoeffsWords([3,2,-5], [M[1]*M[3] ,M[2]-4,M[1]]);[0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( pol );[0m
    [22m[35m2*q8_M2^4 + 3*q8_Ml*q8_M3 - 5*q8_Ml [0m
    [22m[35mgap> redpol := ReduceMonoidPoly( pol, KBrules );[0m
    [22m[35m<monpoly> [0m
    [22m[35mgap> Print( redpol );[0m
    [22m[35m- 5*q8_Ml + 5*<identity ...>[0m
    [22m[35m[0m
  [22m[35m------------------------------------------------------------------[0m
  
