Quelle chap6_mj.html Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/ibnp/doc/chap6_mj.html

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<script type="text/javascript"
 src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>GAP (IBNP) - Chapter 6: Noncommutative Involutive Bases</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap6" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap5_mj.html">[Previous Chapter]</a> <a href="chapBib_mj.html">[Next Chapter]</a> </div>

<a href="chap6.html">[MathJax off]</a>
<a id="X797E483A84214975" name="X797E483A84214975"></a>
<div class="ChapSects"><a href="chap6_mj.html#X797E483A84214975">6 Noncommutative Involutive Bases</a>
<div class="ContSect"> <a href="chap6_mj.html#X7A86C2437F6EB83D">6.1 Noncommutative Involutive Divisions</a>

<div class="ContSSBlock">
 <a href="chap6_mj.html#X8593BCDB8402C46C">6.1-1 LeftDivision</a>
 <a href="chap6_mj.html#X784AF6B87B2B5E5D">6.1-2 RightDivision</a>
 <a href="chap6_mj.html#X7A979BF38311024C">6.1-3 LeftOverlapDivision</a>
 <a href="chap6_mj.html#X83CE05CF7CB18611">6.1-4 RightOverlapDivision</a>
 <a href="chap6_mj.html#X83A3B3F77C712DA1">6.1-5 Selecting a Division</a>

 <a href="chap6_mj.html#X86FAAD527E20A573">6.1-6 DivisionRecordNP</a>
 <a href="chap6_mj.html#X828DA2AE844847E9">6.1-7 IPolyReduceNP</a>
 <a href="chap6_mj.html#X78935EBD85A02F3F">6.1-8 LoggedIPolyReduceNP</a>
 <a href="chap6_mj.html#X7EBFCE307BE928BA">6.1-9 VerifyLoggedRecordNP</a>
 <a href="chap6_mj.html#X8189DEDD87CE1667">6.1-10 IAutoreduceNP</a>
</div></div>
<div class="ContSect"> <a href="chap6_mj.html#X80C3BE018688AFB7">6.2 Computing a Noncommutative Involutive Basis</a>

<div class="ContSSBlock">
 <a href="chap6_mj.html#X7A71E4CD7B43726B">6.2-1 InvolutiveBasisNP</a>
</div></div>
<div class="ContSect"> <a href="chap6_mj.html#X7DB2608C86CA3B04">6.3 The Disjoint Cones Conditions</a>

<div class="ContSSBlock">
 <a href="chap6_mj.html#X7D87860878548EF2">6.3-1 StrongLeftOverlapDivision</a>
 <a href="chap6_mj.html#X819FE8F87ACDB19C">6.3-2 StrongRightOverlapDivision</a>
</div></div>
</div>

<h3>6 Noncommutative Involutive Bases</h3>

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\).

<a id="X7A86C2437F6EB83D" name="X7A86C2437F6EB83D"></a>

<h4>6.1 Noncommutative Involutive Divisions</h4>

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

<ul>
<li>\(w = u \ell v\);

</li>
<li>either \(u = \epsilon\), or the last letter of \(u\) is left multiplicative for \(\ell\);

</li>
<li>and either \(v = \epsilon\), or the first letter of \(v\) is right multiplicative for \(\ell\).

</li>
</ul>
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:

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">\(\ell\)</td>
<td class="tdcenter">\(M^L_I(\ell,W)\)</td>
<td class="tdcenter">\(M^R_I(\ell,W)\)</td>
</tr>
<tr>
<td class="tdcenter">\(xy\)</td>
<td class="tdcenter">\(\{x,y,z\}\)</td>
<td class="tdcenter">\(\{y,z\}\)</td>
</tr>
<tr>
<td class="tdcenter">\(yz\)</td>
<td class="tdcenter">\(\{y,z\}\)</td>
<td class="tdcenter">\(\{x\}\)</td>
</tr>
</table> 
</div>

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.

<a id="X8593BCDB8402C46C" name="X8593BCDB8402C46C"></a>

<h5>6.1-1 LeftDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
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 <a href="chapBib_mj.html#biBgareth-thesis">[Eva05]</a>.

<div class="example"><pre>

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 ] ],
 [ [ ], [ ], [ ], [ ], [ ], [ ] ] ]

</pre></div>

<a id="X784AF6B87B2B5E5D" name="X784AF6B87B2B5E5D"></a>

<h5>6.1-2 RightDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
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\).

<div class="example"><pre>

gap> RightDivision( A3, U6, ord );
[ [ [ ], [ ], [ ], [ ], [ ], [ ] ],
 [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ] ]

</pre></div>

<a id="X7A979BF38311024C" name="X7A979BF38311024C"></a>

<h5>6.1-3 LeftOverlapDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LeftOverlapDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
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.

<ul>
<li>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\).

</li>
<li>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\).

</li>
</ul>
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.

<div class="pcenter"><table class="GAPDocTable">
<tr>
<td class="tdcenter">\(w\)</td>
<td class="tdcenter">\(M^L_{\mathbb{L}}(w,W)\)</td>
<td class="tdcenter">\(M^R_{\mathbb{L}}(w,W)\)</td>
</tr>
<tr>
<td class="tdcenter">\(u = ab^2\)</td>
<td class="tdcenter">\(\{a,b\}\)</td>
<td class="tdcenter">\(\{b\}\)</td>
</tr>
<tr>
<td class="tdcenter">\(v = ba^2\)</td>
<td class="tdcenter">\(\{a,b\}\)</td>
<td class="tdcenter">\(\{a\}\)</td>
</tr>
</table> 
</div>

The following example takes \(W\) to be the list <code class="code">U6</code>, continuing Example 5.5.12 in the thesis <a href="chapBib_mj.html#biBgareth-thesis">[Eva05]</a>. 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\).

<div class="example"><pre>

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 ] ] ]

</pre></div>

<a id="X83CE05CF7CB18611" name="X83CE05CF7CB18611"></a>

<h5>6.1-4 RightOverlapDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RightOverlapDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This division is the mirror image of <code class="code">LeftOverlapDivision</code>.

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\).

<div class="example"><pre>

gap> RightOverlapDivision( A3, U6, ord ); 
[ [ [ 1 .. 3 ], [ 1 .. 3 ], [ 2 ], [ 1 .. 3 ], [ ], [ ] ],
 [ [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ], [ 1 .. 3 ] ] ]

</pre></div>

<a id="X83A3B3F77C712DA1" name="X83A3B3F77C712DA1"></a>

<h5>6.1-5 Selecting a Division</h5>

The global variable <code class="code">NoncommutativeDivision</code> can take values "Left", "Right", "LeftOverlap", "RightOverlap", "StrongLeftOverlop" or "StrongRightOverlap". The default is "LeftOverlap". The example shows how to select the left overlap division.

<div class="example"><pre>

gap> NoncommutativeDivision := "LeftOverlap";
"LeftOverlap"

</pre></div>

Other divisions may be added in due course.

<a id="X86FAAD527E20A573" name="X86FAAD527E20A573"></a>

<h5>6.1-6 DivisionRecordNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DivisionRecordNP</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This operation is called by the global function <code class="code">DivisionRecord</code> 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 <code class="code">drec</code> is returned: <code class="code">drec.div</code> is the division string; <code class="code">drec.mvars</code> is a two-element list, the first listing the sets of left multiplicative variables, and the second listing the sets of right multiplicative variables; <code class="code">drec.polys</code> is the list of polynomials in NP-format.

<div class="example"><pre>

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 ] ] ] )

</pre></div>

<a id="X828DA2AE844847E9" name="X828DA2AE844847E9"></a>

<h5>6.1-7 IPolyReduceNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IPolyReduceNP</code>( <var class="Arg">algebra</var>, <var class="Arg">polynomial</var>, <var class="Arg">DivisionRecord</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This operation is called by the global function <code class="code">IPolyReduce</code> 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\).

<div class="example"><pre>

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 );;
[ [ ], [ ] ]

</pre></div>

<a id="X78935EBD85A02F3F" name="X78935EBD85A02F3F"></a>

<h5>6.1-8 LoggedIPolyReduceNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LoggedIPolyReduceNP</code>( <var class="Arg">algebra</var>, <var class="Arg">polynomial</var>, <var class="Arg">DivisionRecord</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This operation is called by the global function <code class="code">LoggedIPolyReduce</code> when the algebra is noncommutative. This function is similar to <code class="code">IPolyReduceNP</code>, 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 <code class="code">r = logr.result</code> 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).
\]

<div class="example"><pre>

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

</pre></div>

<a id="X7EBFCE307BE928BA" name="X7EBFCE307BE928BA"></a>

<h5>6.1-9 VerifyLoggedRecordNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ VerifyLoggedRecordNP</code>( <var class="Arg">polynomial</var>, <var class="Arg">LogRecord</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This operation checks the identity in the equation displayed above.

For a more complicated example, see file <code class="file">ibnp/tst/extras/reduce.tst</code>.

<div class="example"><pre>

gap> VerifyLoggedRecordNP( Lp, logr );
true

</pre></div>

<a id="X8189DEDD87CE1667" name="X8189DEDD87CE1667"></a>

<h5>6.1-10 IAutoreduceNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IAutoreduceNP</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This operation is called by the global function <code class="code">IAutoreduce</code> when the algebra is noncommutative. This function applies <code class="code">IPolyReduceNP</code> 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 <code class="code">true</code> is returned.

In the example we form <code class="code">L4</code> by adding <code class="code">Lp</code> to <code class="code">L3</code>. Applying <code class="code">IAutoreduceNP</code>, only \(p\) reduces, and the concatenation of <code class="code">L3</code> with \(Lrp\) is returned.

<div class="example"><pre>

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

</pre></div>

<a id="X80C3BE018688AFB7" name="X80C3BE018688AFB7"></a>

<h4>6.2 Computing a Noncommutative Involutive Basis</h4>

The involutive algorithm for constructing an involutive basis in the noncommutative case also uses prolongations and autoreduction.

<a id="X7A71E4CD7B43726B" name="X7A71E4CD7B43726B"></a>

<h5>6.2-1 InvolutiveBasisNP</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InvolutiveBasisNP</code>( <var class="Arg">alg</var>, <var class="Arg">polys</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This operation is called by the global function <code class="code">InvolutiveBasis</code> 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 <code class="code">L3</code> 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\).

<div class="example"><pre>

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

</pre></div>

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.

<div class="example"><pre>

gap> NoncommutativeDivision := "RightOverlap";;
gap> ribasK := InvolutiveBasis( A3, K4, ord );; 
gap> PrintNPList( ribasK.polys ); 
a^3 - a
c - a
b - a

</pre></div>

<a id="X7DB2608C86CA3B04" name="X7DB2608C86CA3B04"></a>

<h4>6.3 The Disjoint Cones Conditions</h4>

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.

<a id="X7D87860878548EF2" name="X7D87860878548EF2"></a>

<h5>6.3-1 StrongLeftOverlapDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StrongLeftOverlapDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
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 <code class="code">InvolutiveBasisNP</code> continues with this information.

<div class="example"><pre>

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

</pre></div>

<a id="X819FE8F87ACDB19C" name="X819FE8F87ACDB19C"></a>

<h5>6.3-2 StrongRightOverlapDivision</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StrongRightOverlapDivision</code>( <var class="Arg">alg</var>, <var class="Arg">mons</var>, <var class="Arg">order</var> )</td><td class="tdright">( operation )</td></tr></table></div>
This operation is the mirror image of <code class="code">StrongLeftOverlapDivision</code>.

When we compute an involutive basis <code class="code">rbasP</code> using the right overlap division we find that <code class="code">rbasP.polys = ibasP.polys</code>. 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.

<div class="example"><pre>

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

</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap5_mj.html">[Previous Chapter]</a> <a href="chapBib_mj.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>

<hr />
generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a>
</body>
</html>

quality97%

¤ Dauer der Verarbeitung: 0.18 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.