When applying a noncommutative rewriting system we conventionally apply a rule ℓ -> r to a word w if and only if w has the form w = u ℓ v, where u or v may be the empty word ϵ. Then w reduces to urv.
An involutive monoid rewriting system I will restrict these conventional reductions by imposing a limitation on the letters allowed in u and v. Sets M^L_I(w), the left multiplicative variables for w, and M^R_I(w), the right multiplicative variables for w, are defined by I.
An involutive division I is a procedure for determining, given an arbitrary set of monomials W, sets of left and right multiplicative letters M^L_I(ℓ,W) and M^R_I(ℓ,W) for any ℓ ∈ W. Then set M^L_I(W) = {M^L_I(ℓ,W) ∣ ℓ ∈ W} and M^R_I(W) = {M^R_I(ℓ,W) ∣ ℓ ∈ W}.
An involutive rewriting system I is based on I if M^L_I(W) and M^R_I(W) are determined using I, in which case we may write M^L_I}(W) and M^R_I}(W) for these sets of letters.
A word ℓ is an involutive divisor of w, written ℓ ∣_I w, if
w = u ℓ v;
either u = ϵ, or the last letter of u is left multiplicative for ℓ;
and either v = ϵ, or the first letter of v is right multiplicative for ℓ.
When this is the case, w involutively reduces to urv by the rule ℓ -> r.
For example, let S = rws({x,y,z},~ {xy -> z,~ yz -> x}), so that W = {xy,yz}. Choose left and right multiplicative variables as shown in the following table:
| ℓ | M^L_I(ℓ,W) | M^R_I(ℓ,W) |
| xy | {x,y,z} | {y,z} |
| yz | {y,z} | {x} |
We consider reductions of w = xyzx. Conventionally, both rules may be used, giving reductions z^2x and x^3 respectively. Involutively, we see that xy ∣_I xyzx because z is right multiplicative for xy, but yz not∣_I~ xyzx because x is left nonmultiplicative for yz. Thus the only involutive reduction is xyzx ->_I z^2x.
If an involutive division I determines the left and right multiplicative variables for a word ℓ ∈ W independently of the set W, then the division is known as a global involutive division. Otherwise I is a local involutive division.
‣ LeftDivision( alg, mons, order ) | ( operation ) |
Given a word w, the left division ◃ assigns all letters to be left multiplicative for w, and all letters to be right nonmultiplicative for w. The example is taken from Example 5.5.12 in the thesis [Eva05].
gap> A3 := Algebra3IBNP;; gap> a:=A3.1;; b:=A3.2;; c:=A3.3;; gap> ord := NCMonomialLeftLengthLexicographicOrdering( A3 );; gap> M6 := [ a*b, a, b*c, a*c, c*b, c^2 ];; gap> U6 := GM2NMList( M6 ); [ [ 1, 2 ], [ 1 ], [ 2, 3 ], [ 1, 3 ], [ 3, 2 ], [ 3, 3 ] ] gap> LeftDivision( A3, U6, ord ); [ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ], [ [ ], [ ], [ ], [ ], [ ], [ ] ] ]
‣ RightDivision( alg, mons, order ) | ( operation ) |
Given a word w, the right division ▹ assigns all letters to be left nonmultiplicative for w, and all letters to be right multiplicative for w.
gap> RightDivision( A3, U6, ord ); [ [ [ ], [ ], [ ], [ ], [ ], [ ] ], [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ] ]
‣ LeftOverlapDivision( alg, mons, order ) | ( operation ) |
Let W = {w_1, ..., w_m}. The left overlap division L assumes, to begin with, that all letters are left and right multiplicative for every w_i. It then assigns some letters to be right nonmultiplicative as follows.
Suppose w_j ∈ W is a subword, but not a suffix, of a (different) word w_i ∈ W. Then, for some k, we have w_j = Subword(w_i,k,k+deg(w_j)-1). Assign the letter in position k+deg(w_j) ∈ w_i to be right nonmultiplicative for w_j.
Suppose a proper prefix of w_i is equal to a proper suffix of a (not neccessarily different) w_j, and that w_i is not a proper subword of w_j, or vice versa. Then, for some k, we have Prefix(w_i,k) = Suffix(w_j,k). Assign the letter in position k+1 in w_i to be right nonmultiplicative for w_j.
Fox example, consider the rewriting system with rules {ab^2 -> b,~ ba^2 -> a}, so that the leading monomials are {u=ab^2, v=ba^2}. Neither monomial is a subword of the other, so the first rule above does not apply. Since Prefix(v,1) = b = Suffix(u,1), then v[2]=a is assigned to be right nonmulitplicative for u. By symmetry, u[2]=b is assigned to be right nonmulitplicative for v. The resulting sets are shown in the following table.
| w | M^L_L}(w,W) | M^R_L}(w,W) |
| u = ab^2 | {a,b} | {b} |
| v = ba^2 | {a,b} | {a} |
The following example takes W to be the list U6, continuing Example 5.5.12 in the thesis [Eva05]. As a is a subword of ab and ac, so b and c are right nonmultiplicative for a. Secondly, ab and cb have suffix b which is a prefix of bc, so c is right nonmultiplicative for ab and cb. Thirdly, ac, bc, c^2 all have suffix c, which is a prefix of cb and c^2, so b and c are both right nonmultiplicative for ac, bc, c^2.
gap> M6; [ (1)*a*b, (1)*a, (1)*b*c, (1)*a*c, (1)*c*b, (1)*c^2 ] gap> LeftOverlapDivision( A3, U6, ord ); [ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ], [ [ 1, 2 ], [ 1 ], [ 1 ], [ 1 ], [ 1, 2 ], [ 1 ] ] ]
‣ RightOverlapDivision( alg, mons, order ) | ( operation ) |
This division is the mirror image of LeftOverlapDivision.
In the example, a is a prefix of ab and ac but is not a proper suffix of any monomial. However, bc has prefix b which is a suffix of ab and cb, so a and c and left nonmultiplicative for bc. Also cb and c^2 have prefix c which is a suffix of ac, bc, c^2, so all of a,b,c are left nonmultiplicative for cb and c^2.
gap> RightOverlapDivision( A3, U6, ord ); [ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 2 ], [ 1 .. 3 ], [ ], [ ] ], [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ] ]
The global variable NoncommutativeDivision can take values "Left", "Right", "LeftOverlap", "RightOverlap", "StrongLeftOverlop" or "StrongRightOverlap". The default is "LeftOverlap". The example shows how to select the left overlap division.
gap> NoncommutativeDivision := "LeftOverlap"; "LeftOverlap"
Other divisions may be added in due course.
‣ DivisionRecordNP( alg, mons, order ) | ( operation ) |
This operation is called by the global function DivisionRecord when the algebra is noncommutative. This operation finds the sets of multiplicative variables for a set of polynomials using one of the involutive divisions listed above. As in the commutative case, a three-field record drec is returned: drec.div is the division string; drec.mvars is a two-element list, the first listing the sets of left multiplicative variables, and the second listing the sets of right multiplicative variables; drec.polys is the list of polynomials in NP-format.
gap> L3 := [ [ [ [1,2,2], [3] ], [1,-1] ], > [ [ [2,3,3], [1] ], [1,-1] ], > [ [ [3,1,1], [2] ], [1,-1] ] ];; gap> PrintNPList( L3 ); ab^2 - c bc^2 - a ca^2 - b gap> drec := DivisionRecord( A3, L3, ord ); rec( div := "LeftOverlap", mvars := [ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ], [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ] ] ], polys := [ [ [ [ 1, 2, 2 ], [ 3 ] ], [ 1, -1 ] ], [ [ [ 2, 3, 3 ], [ 1 ] ], [ 1, -1 ] ], [ [ [ 3, 1, 1 ], [ 2 ] ], [ 1, -1 ] ] ] )
‣ IPolyReduceNP( algebra, polynomial, DivisionRecord, order ) | ( operation ) |
This operation is called by the global function IPolyReduce when the algebra is noncommutative. This function reduces a polynomial p using the current overlap record for a basis, and an ordering.
In the example p = 5c^2a^2b^2 + 6b^2c^2a^2 + 7a^2b^2c^2. The monomial c^2a^2b^2 reduces to c^2ac by ab^2 -> c, since there are no letters to the right, but not by ca^2 -> b since b is not right multiplicative for ca^2. The other terms are similar, and p reduces to 5c^2ac + 6b^2cb + 7a^2ba.
gap> ## choose a polynomial to reduce gap> p := 5*c^2*a^2*b^2 + 6*b^2*c^2*a^2 + 7*a^2*b^2*c^2;; gap> ## convert to NP format and reduce gap> Lp := GP2NP( p ); [ [ [ 3, 3, 1, 1, 2, 2 ], [ 2, 2, 3, 3, 1, 1 ], [ 1, 1, 2, 2, 3, 3 ] ], [ 5, 6, 7 ] ] gap> Lrp := IPolyReduce( A3, Lp, drec, ord );; gap> ## convert back to a polynomial gap> rp := NP2GP( Lrp, A3 ); (5)*c^2*a*c+(6)*b^2*c*b+(7)*a^2*b*a gap> ## p-rp should now belong to the ideal and reduce to 0 gap> q := p - rp;; gap> Lq := GP2NP( q );; gap> Lrq := IPolyReduce( A3, Lq, drec, ord );; [ [ ], [ ] ]
‣ LoggedIPolyReduceNP( algebra, polynomial, DivisionRecord, order ) | ( operation ) |
This operation is called by the global function LoggedIPolyReduce when the algebra is noncommutative. This function is similar to IPolyReduceNP, reducing a polynomial p using the current overlap record for a basis, and an ordering. It's output, however, is a record containing, as well as the reduced polynomial r, logging information L which shows how the reduction has been obtained:
p ~=~ r + \sum_{i,j} L[i][j][1] * L[i][j][2] * polys[i] * L[i][j][3].
In the example r = logr.result is equal to Lrp, and the equation above is then verified:
p ~=~ r + 5c^2a(ab^2-c) + 7a^2b(bc^2-a) + 6b^2c(ca^2-b).
gap> logr := LoggedIPolyReduce( A3, Lp, drec, ord ); rec( logs := [ [ [ 5, [ 3, 3, 1 ], [ ] ] ], [ [ 7, [ 1, 1, 2 ], [ ] ] ], [ [ 6, [ 2, 2, 3 ], [ ] ] ] ], polys := [ [ [ [ 1, 2, 2 ], [ 3 ] ], [ 1, -1 ] ], [ [ [ 2, 3, 3 ], [ 1 ] ], [ 1, -1 ] ], [ [ [ 3, 1, 1 ], [ 2 ] ], [ 1, -1 ] ] ], result := [ [ [ 3, 3, 1, 3 ], [ 2, 2, 3, 2 ], [ 1, 1, 2, 1 ] ], [ 5, 6, 7 ] ] ) gap> logr.result = Lrp; true gap> L := logr.logs;; gap> p1 := ScalarMulNP( BimulNP( L[1][1][2], L3[1], L[1][1][3] ), L[1][1][1] );; gap> p2 := ScalarMulNP( BimulNP( L[2][1][2], L3[2], L[2][1][3] ), L[2][1][1] );; gap> q := AddNP( p1, p2, 1, 1 );; gap> p3 := ScalarMulNP( BimulNP( L[3][1][2], L3[3], L[3][1][3] ), L[3][1][1] );; gap> q := AddNP( q, p3, 1, 1 );; gap> Lp = AddNP( q, Lrp, 1, 1 ); true
‣ VerifyLoggedRecordNP( polynomial, LogRecord ) | ( operation ) |
This operation checks the identity in the equation displayed above.
For a more complicated example, see file ibnp/tst/extras/reduce.tst.
gap> VerifyLoggedRecordNP( Lp, logr ); true
‣ IAutoreduceNP( alg, polys, order ) | ( operation ) |
This operation is called by the global function IAutoreduce when the algebra is noncommutative. This function applies IPolyReduceNP to a list of polynomials recursively until no more reductions are possible. More specifically, this function involutively reduces each member of a list of polynomials with respect to all the other members of the list, removing the polynomial from the list if it is involutively reduced to 0. This process is iterated until no more reductions are possible.
If the set of polynomials is already reduced, then true is returned.
In the example we form L4 by adding Lp to L3. Applying IAutoreduceNP, only p reduces, and the concatenation of L3 with Lrp is returned.
gap> L4 := Concatenation( L3, [Lp] );; gap> R4 := IAutoreduceNP( A3, L4, ord );; gap> PrintNPList( R4 ); 5c^2ac + 6b^2cb + 7a^2ba ca^2 - b bc^2 - a ab^2 - c gap> IAutoreduceNP( A3, R4, ord ); true
The involutive algorithm for constructing an involutive basis in the noncommutative case also uses prolongations and autoreduction.
‣ InvolutiveBasisNP( alg, polys, order ) | ( operation ) |
This operation is called by the global function InvolutiveBasis when the algebra is noncommutative. This function finds an involutive basis for the ideal generated by a set of polynomials, using a chosen ordering.
In the example we find that a Gröbner basis starting from L3 is rather large, so add a fourth polynomial a^2b-c defining the ideal. The resulting Gröbner basis then has just three terms. We then calculate an involutive basis, which has just seven terms. We also find the reduced form of p to be 18a^2.
gap> gbas := SGrobner( L3 );; gap> Length( gbas ); 64 gap> ## that's too large an example for this manual, so add a fourth poly gap> K4 := Concatenation( L3, [ [ [ [1,1,2], [3] ], [1,-1] ] ] );; gap> PrintNPList( K4 ); ab^2 - c bc^2 - a ca^2 - b a^2b - c gap> gbas := SGrobner( K4 );; gap> PrintNPList( gbas ); b - a c - a a^3 - a gap> ## so the only reduced elements are {1,a,a^2} with a^3=a gap> ibasK := InvolutiveBasis( A3, K4, ord ); rec( div := "LeftOverlap", mvars := [ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ], [ [ 2, 3 ], [ 2, 3 ], [ 2, 3 ], [ 2, 3 ], [ 2, 3 ], [ 2, 3 ], [ 2, 3 ] ] ], polys := [ [ [ [ 3, 1, 1 ], [ 1 ] ], [ 1, -1 ] ], [ [ [ 2, 1, 1 ], [ 1 ] ], [ 1, -1 ] ], [ [ [ 1, 1, 1 ], [ 1 ] ], [ 1, -1 ] ], [ [ [ 3, 1 ], [ 1, 1 ] ], [ 1, -1 ] ], [ [ [ 2, 1 ], [ 1, 1 ] ], [ 1, -1 ] ], [ [ [ 3 ], [ 1 ] ], [ 1, -1 ] ], [ [ [ 2 ], [ 1 ] ], [ 1, -1 ] ] ] ) gap> PrintNPList( ibasK.polys ); ca^2 - a ba^2 - a a^3 - a ca - a^2 ba - a^2 c - a b - a gap> Lr := IPolyReduce( A3, p, ibasK, ord );; gap> PrintNP( Lr ); 18a^2
In this simple example the left division produces the same basis, while the right and right overlap divisions do not produce (as might be expected) a mirror image basis.
gap> NoncommutativeDivision := "RightOverlap";; gap> ribasK := InvolutiveBasis( A3, K4, ord );; gap> PrintNPList( ribasK.polys ); a^3 - a c - a b - a
The disjoint right cones condition for a set of monomials W requires that, for each monomial w_i ∈ W, at least one variable in every monomial w_j ∈ W is right nonmultiplicative for w_i. The disjoint left cones condition is the mirror image of this.
‣ StrongLeftOverlapDivision( alg, mons, order ) | ( operation ) |
The strong left overlap division is the extension of the left overlap division obtained by enforcing the disjoint right cones condition. This is achieved by considering all pairs [w_i,w_j] and, if no variable in w_j is right nonmultiplicative for w_i, then w_j[1] is removed from the list of right multiplicative variables for w_i.
In the example, the involutive basis using the left overlap division contains six polynomials with leading monomials [c^2,cb,ca,ba,ac,ab] and with corresponding right non-multiplicative variables [[a,b,c],[a],[b,c],[b,c],[a,b,c],[a]]. Every monomial contains either b or c. When using the strong left overlap division, the first change is in the case i=j=2 when neither b nor c is non-multiplicative for cb. So c is made non-multiplicative for w_2. Similarly c is made non-multiplicative for w_6 = ab. The right multiplicative variables are now [[~],[b],[a],[a],[~],[b]], and InvolutiveBasisNP continues with this information.
gap> P4 := [ [ [ [1,2], [3] ], [1,-2] ], > [ [ [2,1], [3] ], [1,-2] ], > [ [ [1,3], [2] ], [1,-2] ], > [ [ [3,1], [2] ], [1,-2] ] ];; gap> PrintNPList( P4 ); ab - 2c ba - 2c ac - 2b ca - 2b gap> NoncommutativeDivision := "LeftOverlap";; gap> ibasP := InvolutiveBasisNP( A3, P4, ord ); rec( div := "LeftOverlap", mvars := [ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ]\ ], [ [ ], [ 2, 3 ], [ 1 ], [ 1 ], [ ], [ 2, 3 ] ] ], polys := [ [ [ [ 3, 3 ], [ 2, 2 ] ], [ 1, -1 ] ], [ [ [ 3, 2 ], [ 2, 3 ] ], [ 1, -1 ] ], [ [ [ 3, 1 ], [ 2 ] ], [ 1, -2 ] ], [ [ [ 2, 1 ], [ 3 ] ], [ 1, -2 ] ], [ [ [ 1, 3 ], [ 2 ] ], [ 1, -2 ] ], [ [ [ 1, 2 ], [ 3 ] ], [ 1, -2 ] ] ] ) gap> PrintNPList( ibasP.polys ); c^2 - b^2 cb - bc ca - 2b ba - 2c ac - 2b ab - 2c gap> ## check that cbc reduces to b^3 and abc reduces to 2b^2 gap> IPolyReduce( A3, GP2NP( c*b*c ), ibasP, ord ); [ [ [ 2, 2, 2 ] ], [ 1 ] ] gap> IPolyReduce( A3, GP2NP( a*b*c ), ibasP, ord ); [ [ [ 2, 2 ] ], [ 2 ] ] gap> ## now apply the strong left overlap division - two polynomials are added gap> NoncommutativeDivision := "StrongLeftOverlap";; gap> sbasP := InvolutiveBasisNP( A3, P4, ord ); rec( div := "StrongLeftOverlap", mvars := [ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ], [ [ ], [ ], [ ], [ 2 ], [ 1 ], [ 1 ], [ ], [ 2 ] ] ], polys := [ [ [ [ 3, 2, 3 ], [ 2, 2, 2 ] ], [ 1, -1 ] ], [ [ [ 1, 2, 3 ], [ 2, 2 ] ], [ 1, -2 ] ], [ [ [ 3, 3 ], [ 2, 2 ] ], [ 1, -1 ] ], [ [ [ 3, 2 ], [ 2, 3 ] ], [ 1, -1 ] ], [ [ [ 3, 1 ], [ 2 ] ], [ 1, -2 ] ], [ [ [ 2, 1 ], [ 3 ] ], [ 1, -2 ] ], [ [ [ 1, 3 ], [ 2 ] ], [ 1, -2 ] ], [ [ [ 1, 2 ], [ 3 ] ], [ 1, -2 ] ] ] ) gap> PrintNPList( sbasP.polys ); cbc - b^3 abc - 2b^2 c^2 - b^2 cb - bc ca - 2b ba - 2c ac - 2b ab - 2c
‣ StrongRightOverlapDivision( alg, mons, order ) | ( operation ) |
This operation is the mirror image of StrongLeftOverlapDivision.
When we compute an involutive basis rbasP using the right overlap division we find that rbasP.polys = ibasP.polys. However there is just one left multiplicative variable for each of the polynomials and the left disjoint cones condition is already satisfied. So, when using the strong right overlap division, we get the same basis.
gap> NoncommutativeDivision := "RightOverlap";; gap> rbasP := InvolutiveBasisNP( A3, P4, ord ); rec( div := "RightOverlap", mvars := [ [ [ 2 ], [ 2 ], [ 2 ], [ 2 ], [ 1 ], [ 1 ] ], [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ] ], polys := [ [ [ [ 3, 3 ], [ 2, 2 ] ], [ 1, -1 ] ], [ [ [ 3, 2 ], [ 2, 3 ] ], [ 1, -1 ] ], [ [ [ 3, 1 ], [ 2 ] ], [ 1, -2 ] ], [ [ [ 2, 1 ], [ 3 ] ], [ 1, -2 ] ], [ [ [ 1, 3 ], [ 2 ] ], [ 1, -2 ] ], [ [ [ 1, 2 ], [ 3 ] ], [ 1, -2 ] ] ] ) gap> NoncommutativeDivision := "StrongRightOverlap";; gap> srbasP := InvolutiveBasisNP( A3, P4, ord );; gap> ( rbasP.polys = srbasP.polys ) and ( rbasP.mvars = srbasP.mvars ); true
generated by GAPDoc2HTML