When applying a noncommutative rewriting system we conventionally apply a rule \(\ell \to r\) to a word \(w\) if and only if \(w\) has the form \(w = u \ell v\), where \(u\) or \(v\) may be the empty word \(\epsilon\). 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 \(\mathbb{I}\) is a procedure for determining, given an arbitrary set of monomials \(W\), sets of left and right multiplicative letters \(M^L_I(\ell,W)\) and \(M^R_I(\ell,W)\) for any \(\ell \in W\). Then set \(M^L_I(W) = \{M^L_I(\ell,W) \mid \ell \in W\}\) and \(M^R_I(W) = \{M^R_I(\ell,W) \mid \ell \in W\}\).
An involutive rewriting system \(I\) is based on \(\mathbb{I}\) if \(M^L_I(W)\) and \(M^R_I(W)\) are determined using \(\mathbb{I}\), in which case we may write \(M^L_{\mathbb{I}}(W)\) and \(M^R_{\mathbb{I}}(W)\) for these sets of letters.
A word \(\ell\) is an involutive divisor of \(w\), written \(\ell \mid_I w\), if
\(w = u \ell v\);
either \(u = \epsilon\), or the last letter of \(u\) is left multiplicative for \(\ell\);
and either \(v = \epsilon\), or the first letter of \(v\) is right multiplicative for \(\ell\).
When this is the case, \(w\) involutively reduces to \(urv\) by the rule \(\ell \to r\).
For example, let \(S = rws(\{x,y,z\},~ \{xy \to z,~ yz \to x\})\), so that \(W = \{xy,yz\}\). Choose left and right multiplicative variables as shown in the following table:
| \(\ell\) | \(M^L_I(\ell,W)\) | \(M^R_I(\ell,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 \mid_I xyzx\) because \(z\) is right multiplicative for \(xy\), but \(yz \not{\mid}_I~ xyzx\) because \(x\) is left nonmultiplicative for \(yz\). Thus the only involutive reduction is \(xyzx \to_I z^2x\).
If an involutive division \(\mathbb{I}\) determines the left and right multiplicative variables for a word \(\ell \in W\) independently of the set \(W\), then the division is known as a global involutive division. Otherwise \(\mathbb{I}\) is a local involutive division.
‣ LeftDivision( alg, mons, order ) | ( operation ) |
Given a word \(w\), the left division \(\triangleleft\) 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 \(\triangleright\) 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, \ldots, w_m\}\). The left overlap division \(\mathbb{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 \in W\) is a subword, but not a suffix, of a (different) word \(w_i \in 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) \in 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 \to b,~ ba^2 \to 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_{\mathbb{L}}(w,W)\) | \(M^R_{\mathbb{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 \to c\), since there are no letters to the right, but not by \(ca^2 \to 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 \in W\), at least one variable in every monomial \(w_j \in 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