Bilddatei chapA.html

Sprache: HTML

products/Sources/formale Sprachen/GAP/pkg/gbnp/doc/chapA.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>
<title>GAP (GBNP) - Appendix A: Examples</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="chapA" onload="jscontent()">

<div class="chlinktop">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapA.html">A</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap5.html">[Previous Chapter]</a> <a href="chapBib.html">[Next Chapter]</a> </div>

<a href="chapA_mj.html">[MathJax on]</a>
<a id="X7A489A5D79DA9E5C" name="X7A489A5D79DA9E5C"></a>
<div class="ChapSects"><a href="chapA.html#X7A489A5D79DA9E5C">A Examples</a>
<div class="ContSect"> <a href="chapA.html#X7DFB63A97E67C0A1">A.1 Introduction</a>

</div>
<div class="ContSect"> <a href="chapA.html#X784586E47E2739E3">A.2 A simple commutative Gröbner basis computation</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7E1B57AA85C2BA70">A.3 A truncated Gröbner basis for Leonard pairs</a>

</div>
<div class="ContSect"> <a href="chapA.html#X79AC59C482A2E4C1">A.4 The truncated variant on two weighted homogeneous polynomials</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7C7742957CEC6E7B">A.5 The order of the Weyl group of type E_6</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7E39C9738509A036">A.6 The gcd of some univariate polynomials</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7F5A6ABA85CDB6E2">A.7 From the Tapas book</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7C2CD4FA838EEE64">A.8 The Birman-Murakami-Wenzl algebra of type A_3</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7B5CA7F379B78CE0">A.9 The Birman-Murakami-Wenzl algebra of type A_2</a>

</div>
<div class="ContSect"> <a href="chapA.html#X83C81C987A4DE15F">A.10 A commutative example by Mora</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7CAB94A37D580C4A">A.11 Tracing an example by Mora</a>

</div>
<div class="ContSect"> <a href="chapA.html#X8599AE8F7E9E0368">A.12 Finiteness of the Weyl group of type E_6</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7B1822C67CF83041">A.13 Preprocessing for Weyl group computations</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7BE4A97886B0930E">A.14 A quotient algebra with exponential growth</a>

</div>
<div class="ContSect"> <a href="chapA.html#X78679D7D80CD8822">A.15 A commutative quotient algebra of polynomial growth</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7CE3005580EF632D">A.16 An algebra over a finite field</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7E4CEC577A18C8ED">A.17 The dihedral group of order 8</a>

</div>
<div class="ContSect"> <a href="chapA.html#X83328C357FB33D17">A.18 The dihedral group of order 8 on another module</a>

</div>
<div class="ContSect"> <a href="chapA.html#X85DBF3967C4DF5FE">A.19 The dihedral group on a non-cyclic module</a>

</div>
<div class="ContSect"> <a href="chapA.html#X78FCAC347D9D607E">A.20 The icosahedral group</a>

</div>
<div class="ContSect"> <a href="chapA.html#X780C4B777FEA9080">A.21 The symmetric inverse monoid for a set of size four</a>

</div>
<div class="ContSect"> <a href="chapA.html#X84C07DC479FBBCD5">A.22 A module of the Hecke algebra of type
A_3 over GF(3)</a>

</div>
<div class="ContSect"> <a href="chapA.html#X78C01D1987FEF3FE">A.23 Generalized Temperley-Lieb algebras</a>

</div>
<div class="ContSect"> <a href="chapA.html#X85A9CEF087F3936B">A.24 The universal enveloping
algebra of a Lie algebra</a>

</div>
<div class="ContSect"> <a href="chapA.html#X8498D69D8160E5FF">A.25 Serre's exercise</a>

</div>
<div class="ContSect"> <a href="chapA.html#X8116448A84D69022">A.26 Baur and Draisma's transformations</a>

</div>
<div class="ContSect"> <a href="chapA.html#X7912E411867E5F8B">A.27 The cola gene puzzle</a>

</div>
</div>

<h3>A Examples</h3>

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

<h4>A.1 Introduction</h4>

In this chapter all available commented examples can be found. Those without comments are in the directory <code class="file">gbnp/examples</code>. Timing results are obtained on an Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz processor running Linux (3.19.0-42-generic #48~14.04.1-Ubuntu SMP Fri Dec 18 10:24:49 UTC 2015) and using GAP 4.6.5.

<ul>
<li><a href="chapA.html#X784586E47E2739E3">A.2</a> <a href="chapA.html#X784586E47E2739E3">A simple commutative Gröbner basis computation</a>

</li>
<li><a href="chapA.html#X7E1B57AA85C2BA70">A.3</a> <a href="chapA.html#X7E1B57AA85C2BA70">A truncated Gröbner basis for Leonard pairs</a>

</li>
<li><a href="chapA.html#X79AC59C482A2E4C1">A.4</a> <a href="chapA.html#X79AC59C482A2E4C1">The truncated variant on two weighted homogeneous polynomials</a>

</li>
<li><a href="chapA.html#X7C7742957CEC6E7B">A.5</a> <a href="chapA.html#X7C7742957CEC6E7B">The order of the Weyl group of type E_6</a>

</li>
<li><a href="chapA.html#X7E39C9738509A036">A.6</a> <a href="chapA.html#X7E39C9738509A036">The gcd of some univariate polynomials</a>

</li>
<li><a href="chapA.html#X7F5A6ABA85CDB6E2">A.7</a> <a href="chapA.html#X7F5A6ABA85CDB6E2">From the Tapas book</a>

</li>
<li><a href="chapA.html#X7C2CD4FA838EEE64">A.8</a> <a href="chapA.html#X7C2CD4FA838EEE64">The Birman-Murakami-Wenzl algebra of type A_3</a>

</li>
<li><a href="chapA.html#X7B5CA7F379B78CE0">A.9</a> <a href="chapA.html#X7B5CA7F379B78CE0">The Birman-Murakami-Wenzl algebra of type A_2</a>

</li>
<li><a href="chapA.html#X83C81C987A4DE15F">A.10</a> <a href="chapA.html#X83C81C987A4DE15F">A commutative example by Mora</a>

</li>
<li><a href="chapA.html#X7CAB94A37D580C4A">A.11</a> <a href="chapA.html#X7CAB94A37D580C4A">Tracing an example by Mora</a>

</li>
<li><a href="chapA.html#X8599AE8F7E9E0368">A.12</a> <a href="chapA.html#X8599AE8F7E9E0368"> Finiteness of the Weyl group of type E_6</a>

This extends Example <a href="chapA.html#X7C7742957CEC6E7B">A.5</a>.

</li>
<li><a href="chapA.html#X7B1822C67CF83041">A.13</a> <a href="chapA.html#X7B1822C67CF83041">Preprocessing for Weyl group computations</a>

This extends two earlier examples <a href="chapA.html#X7C7742957CEC6E7B">A.5</a> and <a href="chapA.html#X8599AE8F7E9E0368">A.12</a>.

</li>
<li><a href="chapA.html#X7BE4A97886B0930E">A.14</a> <a href="chapA.html#X7BE4A97886B0930E">A quotient algebra with exponential growth</a>

</li>
<li><a href="chapA.html#X78679D7D80CD8822">A.15</a> <a href="chapA.html#X78679D7D80CD8822">A commutative quotient algebra of polynomial growth</a>

This extends Example <a href="chapA.html#X7F5A6ABA85CDB6E2">A.7</a>.

</li>
<li><a href="chapA.html#X7CE3005580EF632D">A.16</a> <a href="chapA.html#X7CE3005580EF632D">An algebra over a finite field</a>

</li>
<li><a href="chapA.html#X7E4CEC577A18C8ED">A.17</a> <a href="chapA.html#X7E4CEC577A18C8ED">The dihedral group of order 8</a>

</li>
<li><a href="chapA.html#X83328C357FB33D17">A.18</a> <a href="chapA.html#X83328C357FB33D17">The dihedral group of order 8 on another module</a>

This extends Example <a href="chapA.html#X7E4CEC577A18C8ED">A.17</a>.

</li>
<li><a href="chapA.html#X85DBF3967C4DF5FE">A.19</a> <a href="chapA.html#X85DBF3967C4DF5FE">The dihedral group on a non-cyclic module</a>

This example also extends Example <a href="chapA.html#X7E4CEC577A18C8ED">A.17</a>.

</li>
<li><a href="chapA.html#X78FCAC347D9D607E">A.20</a> <a href="chapA.html#X78FCAC347D9D607E">The icosahedral group</a>

</li>
<li><a href="chapA.html#X780C4B777FEA9080">A.21</a> <a href="chapA.html#X780C4B777FEA9080">The symmetric inverse monoid for a set of size four</a>

</li>
<li><a href="chapA.html#X84C07DC479FBBCD5">A.22</a> <a href="chapA.html#X84C07DC479FBBCD5">A module of the Hecke algebra of type A_3 over GF(3)</a>

</li>
<li><a href="chapA.html#X78C01D1987FEF3FE">A.23</a> <a href="chapA.html#X78C01D1987FEF3FE">Generalized Temperley-Lieb algebras</a>

</li>
<li><a href="chapA.html#X85A9CEF087F3936B">A.24</a> <a href="chapA.html#X85A9CEF087F3936B">The universal enveloping algebra of a Lie algebra</a>

</li>
<li><a href="chapA.html#X8498D69D8160E5FF">A.25</a> <a href="chapA.html#X8498D69D8160E5FF">Serre's exercise</a>

</li>
<li><a href="chapA.html#X8116448A84D69022">A.26</a> <a href="chapA.html#X8116448A84D69022">Baur and Draisma's transformations</a>

</li>
<li><a href="chapA.html#X7912E411867E5F8B">A.27</a> <a href="chapA.html#X7912E411867E5F8B">The cola gene puzzle</a>

</li>
</ul>
<a id="X784586E47E2739E3" name="X784586E47E2739E3"></a>

<h4>A.2 A simple commutative Gröbner basis computation</h4>

In this commutative example the relations are x^2y-1 and xy^2-1; we add xy-yx to enforce that x and y commute. The answer should be {x^3-1, x-y, xy-yx}, as the reduction ordering is total degree first and then lexicographic with x smaller than y.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 2 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,2);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Then input the relations in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). They will be put in the list <code class="code">Lnp</code>.

<div class="example"><pre>
gap> Lnp := [ [[[1,2],[2,1]],[1,-1]] ];
[ [ [ [ 1, 2 ], [ 2, 1 ] ], [ 1, -1 ] ] ]
gap> x2y := [[[1,1,2],[]],[1,-1]];
[ [ [ 1, 1, 2 ], [ ] ], [ 1, -1 ] ]
gap> AddSet(Lnp,x2y);
gap> xy2 := [[[1,2,2],[]],[1,-1]];
[ [ [ 1, 2, 2 ], [ ] ], [ 1, -1 ] ]
gap> AddSet(Lnp,xy2);
</pre></div>

The relations can be exhibited with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(Lnp);
a^2b - 1
ab - ba
ab^2 - 1
</pre></div>

Let the variables be printed as x and y instead of a and b by means of <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>)

<div class="example"><pre>
gap> GBNP.ConfigPrint("x","y");
</pre></div>

The Gröbner basis can now be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>):

<div class="example"><pre>
gap> GB := SGrobner(Lnp);
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I End of phase II
#I length of G =1
#I length of todo is 1
#I length of G =2
#I length of todo is 0
#I List of todo lengths is [ 1, 1, 0 ]
#I End of phase III
#I G: Cleaning finished, 0 polynomials reduced
#I End of phase IV
#I The computation took 4 msecs.
[ [ [ [ 2 ], [ 1 ] ], [ 1, -1 ] ], [ [ [ 1, 1, 1 ], [ ] ], [ 1, -1 ] ] ]
</pre></div>

When printed, it looks like:

<div class="example"><pre>
gap> PrintNPList(GB);
y - x
x^3 - 1
</pre></div>

The dimension of the quotient algebra can be calculated with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>). The arguments are the Gröbner basis <code class="code">GB</code> and the number of variables is <code class="code">2</code>:

<div class="example"><pre>
gap> DimQA(GB,2);
3
</pre></div>

A basis of this quotient algebra can be calculated with <code class="func">BaseQA</code> (<a href="chap3.html#X7EAA04247B2C6330">3.5-1</a>). The arguments are a Gröbner basis <code class="code">GB</code>, the number of variables <var class="Arg">t</var> (=2) and a variable <var class="Arg">maxno</var> for returning partial quotient algebras (0 means full basis). The calculated basis will be printed as well.

<div class="example"><pre>
gap> B:=BaseQA(GB,2,0);;
gap> PrintNPList(B);
1
x
x^2
</pre></div>

The strong normal form of the element xyxyxyx can be found by use of <code class="func">StrongNormalFormNP</code> (<a href="chap3.html#X8563683E7FA604F8">3.5-6</a>). The arguments are this element and the Gröbner basis <code class="code">GB</code>.

<div class="example"><pre>
gap> f:=[[[1,2,1,2,1,2,1]],[1]];;
gap> PrintNP(f);
xyxyxyx
gap> p:=StrongNormalFormNP(f,GB);;
gap> PrintNP(p);
x
</pre></div>

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

<h4>A.3 A truncated Gröbner basis for Leonard pairs</h4>

To provide Terwilliger with experimental dimension information in low degrees for his theory of Leonard pairs a truncated Gröbner basis computation was carried out as follows.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 2 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,2);
</pre></div>

We truncate the example by putting all monomials of degree n in the ideal by means of the function <code class="code">MkTrLst</code> to be introduced below; a better way to compute the result is by means of the truncated GB algorithms (See <a href="chapA.html#X85A9CEF087F3936B">A.24</a>).

We want to truncate at degree 7 so we have fixed n = 8.

<div class="example"><pre>
gap> n := 8;;
</pre></div>

Now enter the relations in NP form (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). The function <code class="code">MkTrLst</code> will be introduced, which will return all monomials of degree <code class="code">n</code>. The list of ideal generators of interest is called <code class="code">I</code>.

<div class="example"><pre>
gap> sqbr := function(n,q) ; return (q^3-q^-3)/(q-q^(-1)); end;;

gap> c := sqbr(3,5);
651/25

gap> s1 :=[[[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1]],[1,-c,c,-1]];;
gap> s2 :=[[[2,2,2,1],[2,2,1,2],[2,1,2,2],[1,2,2,2]],[1,-c,c,-1]];;

gap> MkTrLst := function(l) local ans, h1, h2, a, i;
> ans := [[1],[2]];
> for i in [2..l] do
> h1 := [];
> h2 := [];
> for a in ans do
> Add(h1,Concatenation([1],a));
> Add(h2,Concatenation([2],a));
> od;
> ans := Concatenation(h1,h2);
> od;
> return List(ans, a -> [[a],[1]]);
> end;;

gap> I := Concatenation([s1,s2],MkTrLst(n));;
</pre></div>

To give an impression, we print the first 20 entries of this list:

<div class="example"><pre>
gap> PrintNPList(I{[1..20]});
a^3b - 651/25a^2ba + 651/25aba^2 - ba^3
b^3a - 651/25b^2ab + 651/25bab^2 - ab^3
a^8
a^7b
a^6ba
a^6b^2
a^5ba^2
a^5bab
a^5b^2a
a^5b^3
a^4ba^3
a^4ba^2b
a^4baba
a^4bab^2
a^4b^2a^2
a^4b^2ab
a^4b^3a
a^4b^4
a^3ba^4
a^3ba^3b
</pre></div>

We calculate the Gröbner basis with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>):

<div class="example"><pre>
gap> GB := SGrobner(I);;
#I number of entered polynomials is 258
#I number of polynomials after reduction is 114
#I End of phase I
#I End of phase II
#I End of phase III
#I Time needed to clean G :0
#I End of phase IV
#I The computation took 176 msecs.
</pre></div>

Now print the first part of the Gröbner basis with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>) (only the first 20 polynomials are printed here, the full Gröbner basis can be printed with <code class="code">PrintNPList(GB)</code>):

<div class="example"><pre>
gap> PrintNPList(GB{[1..20]});
ba^3 - 651/25aba^2 + 651/25a^2ba - a^3b
b^3a - 651/25b^2ab + 651/25bab^2 - ab^3
b^2a^2ba - bab^2a^2 - baba^2b + ba^2bab + ab^2aba - abab^2a - aba^2b^2 + a^2b\
^2ab
b^2ab^2a^2 - 651/25b^2ababa + b^2aba^2b + 626/25bab^2aba - bab^2a^2b + babab^\
2a - ba^2b^2ab + ba^2bab^2 - 651/25ab^2ab^2a + ab^2abab + 423176/625abab^2ab -\
423801/625ababab^2 + 626/25aba^2b^3 - 406901/625a^2b^2ab^2 + 423176/625a^2bab\
^3 - 651/25a^3b^4
a^8
a^7b
a^6ba
a^6b^2
a^5ba^2
a^5bab
a^5b^2a
a^5b^3
a^4ba^2b
a^4baba
a^4bab^2
a^4b^2a^2
a^4b^2ab
a^4b^4
a^3ba^2ba
a^3ba^2b^2
</pre></div>

The truncated quotient algebra is obtained by factoring out the ideal generated by the Gröbner basis <code class="code">GB</code> and so its dimension can be calculated with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>):

<div class="example"><pre>
gap> DimQA(GB,2);
#I The computation took 0 msecs.
157
</pre></div>

Here is what Paul Terwilliger wrote in reaction to the computation carried out by this example:

I just wanted to thank you again for the dimension data that you gave me after the Durham meeting. It ended up having a large impact. See the attached paper; joint with Tatsuro Ito.

I spent several weeks in Japan this past January, working with Tatsuro and trying to find a good basis for the algebra on two symbols subject to the q-Serre relations. After much frustration, we thought of feeding your data into Sloane's online handbook of integer sequences. We did it out of curiosity more than anything; we did not expect the handbook data to be particularly useful. But it was.

The handbook told us that the graded dimension generating function, using your data for the coefficients, matched the q-series for the inverse of the Jacobi theta function ϑ_4; armed with this overwhelming hint we were able to prove that the graded dimension generating function was indeed given by the inverse of ϑ_4. With that info we were able to get a nice result about td pairs.

Paul

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

<h4>A.4 The truncated variant on two weighted homogeneous polynomials</h4>

Here we exhibit a truncated non-commutative homogeneous weighted Gröbner basis computation. This example uses the functions from Section <a href="chap3.html#X7E4E3AD07B2465F9">3.8</a>, the truncation variants (see also Section <a href="chap2.html#X78CF5C44879D34B6">2.6</a>).

The input is a set of polynomials in x and y, which are homogeneous when the weight of x is 2 and of y is 3. The input is {x^3y^2-x^6+y^4,y^2x^3+xyxyx+x^2yxy}. We truncate the computation at degree 16. The truncated Gröbner basis is {y^2x^3+xyxyx+x^2yxy,x^6-x^3y^2-y^4,x^3y^2x-x^4y^2-xy^4} and the dimension of the quotient algebra is 134.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

The variables will be printed as x and y.

<div class="example"><pre>
gap> GBNP.ConfigPrint("x","y");
</pre></div>

The level to truncate at is assigned to n.

<div class="example"><pre>
gap> n := 16;;
</pre></div>

Now enter the relations in NP form (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) and the weights.

<div class="example"><pre>
gap> s1 :=[[[1,1,1,2,2],[1,1,1,1,1,1],[2,2,2,2]],[1,-1,1]];;
gap> s2 :=[[[2,2,1,1,1],[1,2,1,2,1],[1,1,2,1,2]],[1,1,1]];;
gap> K := [s1,s2];;
gap> weights:=[2,3];;
</pre></div>

The input can be printed with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>)

<div class="example"><pre>
gap> PrintNPList(K);
x^3y^2 - x^6 + y^4
y^2x^3 + xyxyx + x^2yxy
</pre></div>

Verify whether the list <code class="code">K</code> consists only of polynomials that are homogeneous with respect to <code class="code">weights</code> by means of <code class="func">CheckHomogeneousNPs</code> (<a href="chap3.html#X83C9E598798D5809">3.8-3</a>).

<div class="example"><pre>
gap> CheckHomogeneousNPs(K,weights);
#I Input is homogeneous
[ 12, 12 ]
</pre></div>

Now calculate the truncated Gröbner basis with <code class="func">SGrobnerTrunc</code> (<a href="chap3.html#X7CD043E081BF2302">3.8-2</a>). The output will only contain homogeneous polynomials of degree at most <code class="code">n</code>.

<div class="example"><pre>
gap> G := SGrobnerTrunc(K,n,weights);;
#I number of entered polynomials is 2
#I number of polynomials after reduction is 2
#I End of phase I
#I Input is homogeneous
#I Reached level 16
#I end of the algorithm
#I The computation took 4 msecs.
</pre></div>

The Gröbner basis of the truncated quotient algebra can be printed with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(G);
y^2x^3 + xyxyx + x^2yxy
x^6 - x^3y^2 - y^4
x^3y^2x - x^4y^2 + y^4x - xy^4
</pre></div>

The standard basis of the quotient of the free noncommutative algebra on n variables, where n is the length of the vector <code class="code">weights</code>, by the homogeneous ideal generated by <code class="code">K</code> up to degree n is obtained by means of the function <code class="func">BaseQATrunc</code> (<a href="chap3.html#X7E33C064875D95CA">3.8-4</a>) applied to <code class="code">K</code>, <code class="code">n</code>, and <code class="code">weights</code>.

<div class="example"><pre>
gap> B := BaseQATrunc(K,n,weights);;
#I number of entered polynomials is 2
#I number of polynomials after reduction is 2
#I End of phase I
#I Input is homogeneous
#I Reached level 16
#I end of the algorithm
#I The computation took 0 msecs.
gap> i := Length(B);
17
gap> Print("at level ",i-1," the standard monomials are:\n");
at level 16 the standard monomials are:
gap> PrintNPList(List(B[i], qq -> [[qq],[1]]));
yxyx^4
yx^2yx^3
xyxyx^3
yx^3yx^2
xyx^2yx^2
x^2yxyx^2
y^4x^2
yx^4yx
xyx^3yx
x^2yx^2yx
x^3yxyx
y^3xyx
y^2xy^2x
yxy^3x
xy^4x
yx^5y
xyx^4y
x^2yx^3y
x^3yx^2y
y^3x^2y
x^4yxy
y^2xyxy
yxy^2xy
xy^3xy
x^5y^2
y^2x^2y^2
yxyxy^2
xy^2xy^2
yx^2y^3
xyxy^3
x^2y^4
</pre></div>

The same result can be obtained by using the truncated Gröbner basis found for <code class="code">G</code> instead of <code class="code">K</code>.

<div class="example"><pre>
gap> B2 := BaseQATrunc(G,n,weights);;
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I Input is homogeneous
#I Reached level 16
#I end of the algorithm
#I The computation took 0 msecs.
gap> B = B2;
true
</pre></div>

Also, the same result can be obtained by using the leading terms of the truncated Gröbner basis found for <code class="code">G</code> instead of <code class="code">K</code>.

<div class="example"><pre>
gap> B3 := BaseQATrunc(List( LMonsNP(G), qq -> [[qq],[1]]),n,weights);;
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I Input is homogeneous
#I Reached level 16
#I end of the algorithm
#I The computation took 0 msecs.
gap> B = B3;
true
</pre></div>

A list of dimensions of the homogeneous parts of the quotient algebra up to degree n is obtained by means of <code class="func">DimsQATrunc</code> (<a href="chap3.html#X7C6882DB837A9F5A">3.8-5</a>) with arguments <code class="code">G</code>, <code class="code">n</code>, and <code class="code">weights</code>.

<div class="example"><pre>
gap> DimsQATrunc(G,n,weights);
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I Input is homogeneous
#I Reached level 16
#I end of the algorithm
#I The computation took 4 msecs.
[ 1, 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 10, 16, 17, 24, 31 ]
</pre></div>

Even more detailed information is given by the list of frequencies up to degree <code class="code">n</code>. This is obtained by means of <code class="func">FreqsQATrunc</code> (<a href="chap3.html#X7FBA7F1D79DA883F">3.8-6</a>) with arguments <code class="code">G</code>, <code class="code">n</code>, and <code class="code">weights</code>.

<div class="example"><pre>
gap> FreqsQATrunc(G,n,weights);
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I Input is homogeneous
#I Reached level 16
#I end of the algorithm
#I The computation took 0 msecs.
[ [ [ [ ], 1 ] ], [ [ [ 1, 0 ], 1 ] ], [ [ [ 0, 1 ], 1 ] ],
 [ [ [ 2, 0 ], 1 ] ], [ [ [ 1, 1 ], 2 ] ],
 [ [ [ 3, 0 ], 1 ], [ [ 0, 2 ], 1 ] ], [ [ [ 2, 1 ], 3 ] ],
 [ [ [ 4, 0 ], 1 ], [ [ 1, 2 ], 3 ] ], [ [ [ 3, 1 ], 4 ], [ [ 0, 3 ], 1 ] ],
 [ [ [ 5, 0 ], 1 ], [ [ 2, 2 ], 6 ] ], [ [ [ 4, 1 ], 5 ], [ [ 1, 3 ], 4 ] ],
 [ [ [ 3, 2 ], 9 ], [ [ 0, 4 ], 1 ] ], [ [ [ 5, 1 ], 6 ], [ [ 2, 3 ], 10 ] ],
 [ [ [ 4, 2 ], 12 ], [ [ 1, 4 ], 5 ] ],
 [ [ [ 6, 1 ], 5 ], [ [ 3, 3 ], 18 ], [ [ 0, 5 ], 1 ] ],
 [ [ [ 5, 2 ], 16 ], [ [ 2, 4 ], 15 ] ] ]
</pre></div>

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

<h4>A.5 The order of the Weyl group of type E_6</h4>

In order to show how the order of a finite group of manageable size with a manageable presentation can be computed, we determine the order of the Weyl group of type E_6. This number is well known to be 51840.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 2 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,2);
</pre></div>

Then input the relations in NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). They come from the presentation of the Weyl group as a Coxeter group. This means that there are six variables, one for each generator. We let the corresponding variables be printed as r_1, ..., r_6 by means of <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>)

<div class="example"><pre>
gap> GBNP.ConfigPrint(6,"r");
</pre></div>

The relations are binomial and represent the group relations, which express that the generators are involutions (that is, have order 2) and that the orders of the products of any two generators is specified by the Coxeter diagram (see any book on Coxeter groups for details). The relations will be assigned to <code class="code">KI</code>.

<div class="example"><pre>
gap> k1 := [[[1,3,1],[3,1,3]],[1,-1]];;
gap> k2 := [[[4,3,4],[3,4,3]],[1,-1]];;
gap> k3 := [[[4,2,4],[2,4,2]],[1,-1]];;
gap> k4 := [[[4,5,4],[5,4,5]],[1,-1]];;
gap> k5 := [[[6,5,6],[5,6,5]],[1,-1]];;
gap> k6 := [[[1,2],[2,1]],[1,-1]];;
gap> k7 := [[[1,4],[4,1]],[1,-1]];;
gap> k8 := [[[1,5],[5,1]],[1,-1]];;
gap> k9 := [[[1,6],[6,1]],[1,-1]];;
gap> k10 := [[[2,3],[3,2]],[1,-1]];;
gap> k11 := [[[2,5],[5,2]],[1,-1]];;
gap> k12 := [[[2,6],[6,2]],[1,-1]];;
gap> k13 := [[[3,5],[5,3]],[1,-1]];;
gap> k14 := [[[3,6],[6,3]],[1,-1]];;
gap> k15 := [[[4,6],[6,4]],[1,-1]];;
gap> k16 := [[[1,1],[]],[1,-1]];;
gap> k17 := [[[2,2],[]],[1,-1]];;
gap> k18 := [[[3,3],[]],[1,-1]];;
gap> k19 := [[[4,4],[]],[1,-1]];;
gap> k20 := [[[5,5],[]],[1,-1]];;
gap> k21 := [[[6,6],[]],[1,-1]];;
gap> KI := [k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,
> k11,k12,k13,k14,k15,k16,k17,k18,k19,k20,k21
> ];;
</pre></div>

The relations can be shown with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(KI);
r.1r.3r.1 - r.3r.1r.3
r.4r.3r.4 - r.3r.4r.3
r.4r.2r.4 - r.2r.4r.2
r.4r.5r.4 - r.5r.4r.5
r.6r.5r.6 - r.5r.6r.5
r.1r.2 - r.2r.1
r.1r.4 - r.4r.1
r.1r.5 - r.5r.1
r.1r.6 - r.6r.1
r.2r.3 - r.3r.2
r.2r.5 - r.5r.2
r.2r.6 - r.6r.2
r.3r.5 - r.5r.3
r.3r.6 - r.6r.3
r.4r.6 - r.6r.4
r.1^2 - 1
r.2^2 - 1
r.3^2 - 1
r.4^2 - 1
r.5^2 - 1
r.6^2 - 1
</pre></div>

The Gröbner basis can now be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>):

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I number of entered polynomials is 21
#I number of polynomials after reduction is 21
#I End of phase I
#I End of phase II
#I End of phase III
#I Time needed to clean G :0
#I End of phase IV
#I The computation took 132 msecs.
gap> PrintNPList(GB);
r.1^2 - 1
r.2r.1 - r.1r.2
r.2^2 - 1
r.3r.2 - r.2r.3
r.3^2 - 1
r.4r.1 - r.1r.4
r.4^2 - 1
r.5r.1 - r.1r.5
r.5r.2 - r.2r.5
r.5r.3 - r.3r.5
r.5^2 - 1
r.6r.1 - r.1r.6
r.6r.2 - r.2r.6
r.6r.3 - r.3r.6
r.6r.4 - r.4r.6
r.6^2 - 1
r.3r.1r.2 - r.2r.3r.1
r.3r.1r.3 - r.1r.3r.1
r.4r.2r.4 - r.2r.4r.2
r.4r.3r.4 - r.3r.4r.3
r.5r.4r.5 - r.4r.5r.4
r.6r.5r.6 - r.5r.6r.5
r.4r.3r.1r.4 - r.3r.4r.3r.1
r.5r.4r.2r.5 - r.4r.5r.4r.2
r.5r.4r.3r.5 - r.4r.5r.4r.3
r.6r.5r.4r.6 - r.5r.6r.5r.4
r.4r.2r.3r.4r.2 - r.3r.4r.2r.3r.4
r.4r.2r.3r.4r.3 - r.2r.4r.2r.3r.4
r.5r.4r.2r.3r.5 - r.4r.5r.4r.2r.3
r.5r.4r.3r.1r.5 - r.4r.5r.4r.3r.1
r.6r.5r.4r.2r.6 - r.5r.6r.5r.4r.2
r.6r.5r.4r.3r.6 - r.5r.6r.5r.4r.3
r.4r.2r.3r.1r.4r.2 - r.3r.4r.2r.3r.1r.4
r.5r.4r.2r.3r.1r.5 - r.4r.5r.4r.2r.3r.1
r.6r.5r.4r.2r.3r.6 - r.5r.6r.5r.4r.2r.3
r.6r.5r.4r.3r.1r.6 - r.5r.6r.5r.4r.3r.1
r.4r.2r.3r.1r.4r.3r.1 - r.2r.4r.2r.3r.1r.4r.3
r.5r.4r.2r.3r.4r.5r.4 - r.4r.5r.4r.2r.3r.4r.5
r.6r.5r.4r.2r.3r.1r.6 - r.5r.6r.5r.4r.2r.3r.1
r.6r.5r.4r.2r.3r.4r.6 - r.5r.6r.5r.4r.2r.3r.4
r.5r.4r.2r.3r.1r.4r.5r.4 - r.4r.5r.4r.2r.3r.1r.4r.5
r.6r.5r.4r.2r.3r.1r.4r.6 - r.5r.6r.5r.4r.2r.3r.1r.4
r.6r.5r.4r.2r.3r.1r.4r.3r.6 - r.5r.6r.5r.4r.2r.3r.1r.4r.3
r.6r.5r.4r.2r.3r.4r.5r.6r.5 - r.5r.6r.5r.4r.2r.3r.4r.5r.6
r.5r.4r.2r.3r.1r.4r.3r.5r.4r.3 - r.4r.5r.4r.2r.3r.1r.4r.3r.5r.4
r.6r.5r.4r.2r.3r.1r.4r.5r.6r.5 - r.5r.6r.5r.4r.2r.3r.1r.4r.5r.6
r.5r.4r.2r.3r.1r.4r.3r.5r.4r.2r.3 - r.4r.5r.4r.2r.3r.1r.4r.3r.5r.4r.2
r.6r.5r.4r.2r.3r.1r.4r.3r.5r.6r.5 - r.5r.6r.5r.4r.2r.3r.1r.4r.3r.5r.6
r.6r.5r.4r.2r.3r.1r.4r.3r.5r.4r.6r.5r.4 - r.5r.6r.5r.4r.2r.3r.1r.4r.3r.5r.4r.\
6r.5
r.6r.5r.4r.2r.3r.1r.4r.3r.5r.4r.2r.6r.5r.4r.2 - r.5r.6r.5r.4r.2r.3r.1r.4r.3r.\
5r.4r.2r.6r.5r.4
</pre></div>

The base of the quotient algebra can be calculated with <code class="func">BaseQA</code> (<a href="chap3.html#X7EAA04247B2C6330">3.5-1</a>), which has as arguments a Gröbner basis <code class="code">GB</code>, a number of symbols <code class="code">6</code> and a maximum terms to be found (here 0 is entered, for a full base) . Since it is very long we will not print it here.

<div class="example"><pre>
gap> B:=BaseQA(GB,6,0);;
</pre></div>

The dimension of the quotient algebra can be calculated with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>), the arguments are the Gröbner basis <code class="code">GB</code> and the number of symbols <code class="code">6</code>. Since <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) is set to 2, we get timing information from <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>):

<div class="example"><pre>
gap> DimQA(GB,6);
#I The computation took 172 msecs.
51840
</pre></div>

Note that the calculation of the dimension takes almost as long as calculating the base. Since we have already calculated a base <code class="code">B</code> it is much more efficient to calculate the dimension with <code class="code">Length</code>:

<div class="example"><pre>
gap> Length(B);
51840
</pre></div>

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

<h4>A.6 The gcd of some univariate polynomials</h4>

A list of univariate polynomials is generated. The result of the Gröbner basis computation on this list should be a single monic polynomial, their gcd.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 2 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,2);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Let the single variable be printed as x by means of <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>)

<div class="example"><pre>
gap> GBNP.ConfigPrint("x");
</pre></div>

Now input the relations in NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). They will be assigned to <code class="code">KI</code>.

<div class="example"><pre>
gap> p0 := [[[1,1,1],[1,1],[1],[]],[1,2,2,1]];;
gap> p1 := [[[1,1,1,1],[1,1],[]],[1,1,1]];;
gap> KI := [p0,p1];;

gap> for i in [2..12] do
> h := AddNP(AddNP(KI[i],KI[i-1],1,3),
> AddNP(BimulNP([1],KI[i],[]),KI[i-1],2,1),3,-5);
> Add(KI,h);
> od;
</pre></div>

The relations can be shown with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(KI);
x^3 + 2x^2 + 2x + 1
x^4 + x^2 + 1
- 10x^5 + 3x^4 - 6x^3 + 11x^2 - 2x + 7
100x^6 - 60x^5 + 73x^4 - 128x^3 + 57x^2 - 76x + 25
- 1000x^7 + 900x^6 - 950x^5 + 1511x^4 - 978x^3 + 975x^2 - 486x + 103
10000x^8 - 12000x^7 + 12600x^6 - 18200x^5 + 14605x^4 - 13196x^3 + 8013x^2 - 2\
792x + 409
- 100000x^9 + 150000x^8 - 166000x^7 + 223400x^6 - 204450x^5 + 181819x^4 - 123\
630x^3 + 55859x^2 - 14410x + 1639
1000000x^10 - 1800000x^9 + 2150000x^8 - 2780000x^7 + 2765100x^6 - 2504340x^5 \
+ 1840177x^4 - 982264x^3 + 343729x^2 - 70788x + 6553
- 10000000x^11 + 21000000x^10 - 27300000x^9 + 34850000x^8 - 36655000x^7 + 342\
32300x^6 - 26732590x^5 + 16070447x^4 - 6878602x^3 + 1962503x^2 - 335534x + 262\
15
100000000x^12 - 240000000x^11 + 340000000x^10 - 437600000x^9 + 479700000x^8 -\
463408000x^7 + 381083200x^6 - 250919600x^5 + 124358069x^4 - 44189892x^3 + 106\
17765x^2 - 1551904x + 104857
- 1000000000x^13 + 2700000000x^12 - 4160000000x^11 + 5480000000x^10 - 6219000\
000x^9 + 6212580000x^8 - 5347676000x^7 + 3789374800x^6 - 2103269850x^5 + 87925\
4915x^4 - 266261734x^3 + 55222347x^2 - 7046418x + 419431
10000000000x^14 - 30000000000x^13 + 50100000000x^12 - 68240000000x^11 + 79990\
000000x^10 - 82533200000x^9 + 74033300000x^8 - 55790408000x^7 + 33925155700x^6\
- 16106037100x^5 + 5797814361x^4 - 1527768240x^3 + 278602281x^2 - 31541180x +\
1677721
- 100000000000x^15 + 330000000000x^14 - 595000000000x^13 + 843500000000x^12 -\
1021260000000x^11 + 1087222000000x^10 - 1012808600000x^9 + 804854300000x^8 - \
528013485000x^7 + 277993337300x^6 - 114709334310x^5 + 36188145143x^4 - 8434374\
466x^3 + 1372108031x^2 - 139586422x + 6710887
gap> Length(KI);
13
</pre></div>

The Gröbner basis can now be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>):

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I number of entered polynomials is 13
#I number of polynomials after reduction is 1
#I End of phase I
#I End of phase II
#I List of todo lengths is [ 0 ]
#I End of phase III
#I G: Cleaning finished, 0 polynomials reduced
#I End of phase IV
#I The computation took 0 msecs.
</pre></div>

Printed it looks like:

<div class="example"><pre>
gap> PrintNPList(GB);
x^2 + x + 1
</pre></div>

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

<h4>A.7 From the Tapas book</h4>

This example is a standard commutative Gröbner basis computation from the book Some Tapas of Computer Algebra <a href="chapBib.html#biBCohenCuypersSterk1999">[CCS99]</a>, page 339. There are six variables, named a, ... , f by default. We work over the rationals and study the ideal generated by the twelve polynomials occurring on the middle of page 339 of the Tapas book in a project by De Boer and Pellikaan on the ternary cyclic code of length 11. Below these are named <code class="code">p1</code>, ..., <code class="code">p12</code>. The result should be the union of {a,b} and the set of 6 homogeneous binomials (that is, polynomials with two terms) of degree 2 forcing commuting between c, d, e, and f.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 2 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,2);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Now define some functions which will help in the construction of relations. The function <code class="code">powermon(g, exp)</code> will return the monomial g^exp. The function <code class="code">comm(a, b)</code> will return a relation forcing commutativity between its two arguments <code class="code">a</code> and <code class="code">b</code>.

<div class="example"><pre>
gap> powermon := function(base, exp)
> local ans,i;
> ans := [];
> for i in [1..exp] do ans := Concatenation(ans,[base]); od;
> return ans;
> end;;

gap> comm := function(a,b)
> return [[[a,b],[b,a]],[1,-1]];
> end;;
</pre></div>

Now the relations are entered.

<div class="example"><pre>
gap> p1 := [[[5,1]],[1]];;
gap> p2 := [[powermon(1,3),[6,1]],[1,1]];;
gap> p3 := [[powermon(1,9),Concatenation([3],powermon(1,3))],[1,1]];;
gap> p4 := [[powermon(1,81),Concatenation([3],powermon(1,9)),
> Concatenation([4],powermon(1,3))],[1,1,1]];;
gap> p5 := [[Concatenation([3],powermon(1,81)),Concatenation([4],powermon(1,9)),
> Concatenation([5],powermon(1,3))],[1,1,1]];;
gap> p6 := [[powermon(1,27),Concatenation([4],powermon(1,81)),Concatenation([5],
> powermon(1,9)),Concatenation([6],powermon(1,3))],[1,1,1,1]];;
gap> p7 := [[powermon(2,1),Concatenation([3],powermon(1,27)),Concatenation([5],
> powermon(1,81)),Concatenation([6],powermon(1,9))],[1,1,1,1]];;
gap> p8 := [[Concatenation([3],powermon(2,1)),Concatenation([4],powermon(1,27)),
> Concatenation([6],powermon(1,81))],[1,1,1]];;
gap> p9 := [[Concatenation([],powermon(1,1)),Concatenation([4],powermon(2,1)),
> Concatenation([5],powermon(1,27))],[1,1,1]];;
gap> p10 := [[Concatenation([3],powermon(1,1)),Concatenation([5],powermon(2,1)),
> Concatenation([6],powermon(1,27))],[1,1,1]];;
gap> p11 := [[Concatenation([4],powermon(1,1)),Concatenation([6],powermon(2,1))],
> [1,1]];;
gap> p12 := [[Concatenation([],powermon(2,3)),Concatenation([],powermon(2,1))],
> [1,-1]];;
gap> KI := [p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12];;
gap> for i in [1..5] do
> for j in [i+1..6] do
> Add(KI,comm(i,j));
> od;
> od;
</pre></div>

The relations can be shown with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(KI);
ea
a^3 + fa
a^9 + ca^3
a^81 + ca^9 + da^3
ca^81 + da^9 + ea^3
a^27 + da^81 + ea^9 + fa^3
b + ca^27 + ea^81 + fa^9
cb + da^27 + fa^81
a + db + ea^27
ca + eb + fa^27
da + fb
b^3 - b
ab - ba
ac - ca
ad - da
ae - ea
af - fa
bc - cb
bd - db
be - eb
bf - fb
cd - dc
ce - ec
cf - fc
de - ed
df - fd
ef - fe
gap> Length(KI);
27
</pre></div>

It is sometimes easier to enter the relations as elements of a free algebra and then use the function <code class="func">GP2NP</code> (<a href="chap3.html#X7B0EBCBC7857F1AE">3.1-1</a>) or the function <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>) to convert them. This will be demonstrated below. More about converting can be read in Section <a href="chap3.html#X81ABB91B79E00229">3.1</a>.

<div class="example"><pre>
gap> F:=Rationals;;
gap> A:=FreeAssociativeAlgebraWithOne(F,"a","b","c","d","e","f");;
gap> a:=A.a;; b:=A.b;; c:=A.c;; d:=A.d;; e:=A.e;; f:=A.f;;
gap> KI_gp:=[e*a, #p1
> a^3 + f*a, #p2
> a^9 + c*a^3, #p3
> a^81 + c*a^9 + d*a^3, #p4
> c*a^81 + d*a^9 + e*a^3, #p5
> a^27 + d*a^81 + e*a^9 + f*a^3, #p6
> b + c*a^27 + e*a^81 + f*a^9, #p7
> c*b + d*a^27 + f*a^81, #p8
> a + d*b + e*a^27, #p9
> c*a + e*b + f*a^27, #p10
> d*a + f*b, #p11
> b^3 - b];; #p12
</pre></div>

These relations can be converted to NP form (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) with <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>). For use in a Gröbner basis computation we have to order the NP polynomials in <code class="code">KI</code>. This can be done with <code class="func">CleanNP</code> (<a href="chap3.html#X855F3D4C783000E3">3.3-7</a>).

<div class="example"><pre>
gap> KI_np:=GP2NPList(KI_gp);;
gap> Apply(KI,x->CleanNP(x));;
gap> KI_np=KI{[1..12]};
true
</pre></div>

The Gröbner basis can now be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>) and printed with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>).

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I number of entered polynomials is 27
#I number of polynomials after reduction is 8
#I End of phase I
#I End of phase II
#I List of todo lengths is [ 0 ]
#I End of phase III
#I G: Cleaning finished, 0 polynomials reduced
#I End of phase IV
#I The computation took 748 msecs.
gap> PrintNPList(GB);
a
b
dc - cd
ec - ce
ed - de
fc - cf
fd - df
fe - ef
</pre></div>

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

<h4>A.8 The Birman-Murakami-Wenzl algebra of type A_3</h4>

We study the Birman-Murakami-Wenzl algebra of type A_3 as an algebra given by generators and relations. A reference for the relations used is <a href="chapBib.html#biBMR2124811">[CGW05]</a>.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

The variables are g_1, g_2, g_3, e_1, e_2, e_3, in this order. In order to have the results printed out with these symbols, we invoke <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>)

<div class="example"><pre>
gap> GBNP.ConfigPrint("g1","g2","g3","e1","e2","e3");
</pre></div>

Now enter the relations. This will be done in NP form (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). The inderminates m and l in the coefficient ring of the Birman-Murakami-Wenzl algebra are specialized to 7 and 11 in order to make the computations more efficient.

<div class="example"><pre>
gap> m:= 7;;
gap> l:= 11;;

gap> #relations Theorem 1.1
gap> k1 := [[[4],[1,1],[1],[]],[1,-l/m,-l,l/m]];;
gap> k2 := [[[5],[2,2],[2],[]],[1,-l/m,-l,l/m]];;
gap> k3 := [[[6],[3,3],[3],[]],[1,-l/m,-l,l/m]];;

gap> #relations B1
gap> #empty set here

gap> #relations B2:
gap> k4 := [[[1,2,1],[2,1,2]],[1,-1]];;
gap> k5 := [[[2,3,2],[3,2,3]],[1,-1]];;
gap> k6 := [[[1,3],[3,1]],[1,-1]];;

gap> #relations R1
gap> kr1 := [[[1,4],[4]],[1,-1/l]];;
gap> kr2 := [[[2,5],[5]],[1,-1/l]];;
gap> kr3 := [[[3,6],[6]],[1,-1/l]];;

gap> #relations R2:
gap> kr4 := [[[4,2,4],[4]],[1,-l]];;
gap> kr5 := [[[5,1,5],[5]],[1,-l]];;
gap> kr6 := [[[5,3,5],[5]],[1,-l]];;
gap> kr7 := [[[6,2,6],[6]],[1,-l]];;

gap> #relations R2'
gap> km1 := [[[4,5,4],[4]],[1,-1]];;
gap> km2 := [[[5,4,5],[5]],[1,-1]];;
gap> km3 := [[[5,6,5],[5]],[1,-1]];;
gap> km4 := [[[6,5,6],[6]],[1,-1]];;

gap> KI := [k1,k2,k3,k4,k5,k6,kr1,kr2,kr3,kr4,kr5,kr6,kr7,km1,km2,km3,km4];;
</pre></div>

Now print the relations with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(KI);
e1 - 11/7g1^2 - 11g1 + 11/7
e2 - 11/7g2^2 - 11g2 + 11/7
e3 - 11/7g3^2 - 11g3 + 11/7
g1g2g1 - g2g1g2
g2g3g2 - g3g2g3
g1g3 - g3g1
g1e1 - 1/11e1
g2e2 - 1/11e2
g3e3 - 1/11e3
e1g2e1 - 11e1
e2g1e2 - 11e2
e2g3e2 - 11e2
e3g2e3 - 11e3
e1e2e1 - e1
e2e1e2 - e2
e2e3e2 - e2
e3e2e3 - e3
gap> Length(KI);
17
</pre></div>

Now calculate the Gröbner basis with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>):

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I number of entered polynomials is 17
#I number of polynomials after reduction is 17
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 76 msecs.
gap> PrintNPList(GB);
g1^2 - 7/11e1 + 7g1 - 1
g1e1 - 1/11e1
g2^2 - 7/11e2 + 7g2 - 1
g2e2 - 1/11e2
g3g1 - g1g3
g3^2 - 7/11e3 + 7g3 - 1
g3e3 - 1/11e3
e1g1 - 1/11e1
e1g3 - g3e1
e1^2 + 43/77e1
e2g2 - 1/11e2
e2^2 + 43/77e2
e3g1 - g1e3
e3g3 - 1/11e3
e3e1 - e1e3
e3^2 + 43/77e3
g1g2e1 - e2e1
g1g3e1 - 1/11g3e1
g1e2e1 + 7e2e1 - g2e1 - 7e1
g2g1g2 - g1g2g1
g2g1e2 - e1e2
g2g3e2 - e3e2
g2e1g2 - g1e2g1 - 7e2g1 + 7e1g2 + 7g2e1 - 7g1e2 - 49e2 + 49e1
g2e1e2 + 7e1e2 - g1e2 - 7e2
g2e3e2 + 7e3e2 - g3e2 - 7e2
g3g2g3 - g2g3g2
g3g2e3 - e2e3
g3e1e3 - 1/11e1e3
g3e2g3 - g2e3g2 - 7e3g2 + 7e2g3 + 7g3e2 - 7g2e3 - 49e3 + 49e2
g3e2e3 + 7e2e3 - g2e3 - 7e3
e1g2g1 - e1e2
e1g2e1 - 11e1
e1e2g1 + 7e1e2 - e1g2 - 7e1
e1e2e1 - e1
e2g1g2 - e2e1
e2g1e2 - 11e2
e2g3g2 - e2e3
e2g3e2 - 11e2
e2e1g2 + 7e2e1 - e2g1 - 7e2
e2e1e2 - e2
e2e3g2 + 7e2e3 - e2g3 - 7e2
e2e3e2 - e2
e3g2g3 - e3e2
e3g2e3 - 11e3
e3e2g3 + 7e3e2 - e3g2 - 7e3
e3e2e3 - e3
g1g2g3e1 - e2g3e1
g1g3g2e1 - g3e2e1
g1g3e2e1 + 7g3e2e1 - g3g2e1 - 7g3e1
g1e2g3e1 + 7e2g3e1 - g2g3e1 - 7g3e1
g1e3g2e1 - e3e2e1
g1e3e2e1 + 7e3e2e1 - e3g2e1 - 7e1e3
g3g2g1g3 - g2g3g2g1
g3g2g1e3 - e2g1e3
g3g2e1e3 - e2e1e3
g3e1g2e3 - e1e2e3
g3e1e2e3 + 7e1e2e3 - e1g2e3 - 7e1e3
g3e2g1g3 - g2e3g2g1 - 7e3g2g1 + 7e2g1g3 + 7g3e2g1 - 7g2g1e3 + 49e2g1 - 49g1e3\

g3e2g1e3 + 7e2g1e3 - g2g1e3 - 7g1e3
g3e2e1e3 + 7e2e1e3 - g2e1e3 - 7e1e3
e1g2g3g2 - g3e1g2g3
e1g2g3e1 - 11g3e1
e1g2e3g2 - g3e1e2g3 + 7e1e3g2 - 7e1e2g3 + 7e1g2e3 - 7g3e1e2 + 49e1e3 - 49e1e2\

e1e2g3e1 - g3e1
e1e3g2g1 - e1e3e2
e1e3g2e1 - 11e1e3
e1e3e2g1 + 7e1e3e2 - e1e3g2 - 7e1e3
e1e3e2e1 - e1e3
e2g3e1e2 - e2g1e3e2
e2e1e3e2 + 7e2g1e3e2 - e2g1g3e2 - 77e2
e3g2g1g3 - e3e2g1
e3g2g1e3 - 11g1e3
e3g2e1e3 - 11e1e3
e3e2g1g3 + 7e3e2g1 - e3g2g1 - 7g1e3
e3e2g1e3 - g1e3
e3e2e1e3 - e1e3
g1g2g1g3e2 - g2g1e3e2
g1g2g1e3e2 + 7g2g1e3e2 - g2g1g3e2 - 7e1e2
g1g2g3g2e1 - g2e3g2e1 - 7e3g2e1 + 7e2g3e1 + 7g3e2e1 - 7g2e1e3 + 49e2e1 - 49e1\
e3
g1g2e3g2e1 + 7g2e3g2e1 - g2g3g2e1 + 7e3e2e1 + 49e3g2e1 + 7e2e1e3 - 7g3g2e1 + \
49g2e1e3 - 7g2g3e1 + 343e1e3 - 49g3e1 - 49g2e1 - 350e1
g1e2g1g3e2 + 7e2g1g3e2 - g2e1e3e2 - 7g2g3e1e2 - 7e1e3e2 - 49g3e1e2 + 77g1e2 +\
539e2
g1e2g1e3e2 + 7e2g1e3e2 - g2g3e1e2 - 7g3e1e2
g2g3e1g2g3 - g1e2g1g3g2 - 7e2g1g3g2 + 7g3e1g2g3 + 7g2g3e1g2 + 49g3e1g2 - 7g1e\
2e3 - 49e2e3
g2g3e1e2g3 - g1e2g1e3g2 - 7e2g1e3g2 + 7g3e1e2g3 + 7g2g3e1e2 - 7g1e2g1e3 - 49e\
2g1e3 + 49g3e1e2
e2g1g3g2g1 - e2g1e3g2
e2g1g3e2g1 - e2e1e3g2 - 7e2g3e1g2 + 7e2g1g3e2 - 7e2e1e3 - 49e2g3e1 + 77e2g1 +\
539e2
e2g1e3g2g1 + 7e2g1e3g2 - e2g1g3g2 - 7e2e1
e2g1e3e2g1 - e2g3e1g2 + 7e2g1e3e2 - 7e2g3e1
e2g3e1g2g3 + 7e2g3e1g2 - e2g1g3g2 - 7e2e3
</pre></div>

Now calculate the dimension of the quotient algebra with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>) (the second argument is the number of symbols):

<div class="example"><pre>
gap> DimQA(GB,6);
105
</pre></div>

The conclusion is that the BMW algebra of type A3 has dimension 105.

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

<h4>A.9 The Birman-Murakami-Wenzl algebra of type A_2</h4>

The trace variant (see sections <a href="chap2.html#X8739B6547BC89505">2.5</a> and <a href="chap3.html#X7BA5CAA07890F7AA">3.7</a>) will be used for a presentation of the Birman-Murakami-Wenzl algebra of type A_2 by generators and relations in order to find a proof that the algebra has dimension 15.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

The variables are g_1, g_2, e_1, e_2, in this order. In order to have the results printed out with these symbols, we invoke <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>)

<div class="example"><pre>
gap> GBNP.ConfigPrint("g1","g2","e1","e2");
</pre></div>

Unlike Example <a href="chapA.html#X7C2CD4FA838EEE64">A.8</a>, we work with a field of rational functions.

<div class="example"><pre>
gap> ll := Indeterminate(Rationals,"l");
l
gap> mm := Indeterminate(Rationals,"m");
m
gap> F := Field(ll,mm);;
gap> gens := GeneratorsOfField(F);
[ l, m ]
gap> l := gens[1];;
gap> m := gens[2];
m
gap> F1 := One(F);;
gap> Print("identity element of F: ",F1,"\n");
identity element of F: 1
</pre></div>

Now enter the relations. This will be done in NP form.

<div class="example"><pre>
gap> #relations Theorem 1.1
gap> k1 := [[[3],[1,1],[1],[]],[F1,-l/m,-l,l/m]];;
gap> k2 := [[[4],[2,2],[2],[]],[F1,-l/m,-l,l/m]];;

gap> #relations B1
gap> #empty set here

gap> #relations B2:
gap> k3 := [[[1,2,1],[2,1,2]],[F1,-F1]];;

gap> #relations R1
gap> k4 := [[[1,3],[3]],[F1,-1/l]];;
gap> k5 := [[[2,4],[4]],[F1,-1/l]];;

gap> #relations R2:
gap> k6 := [[[3,2,3],[3]],[F1,-l]];;
gap> k7 := [[[4,1,4],[4]],[F1,-l]];;
gap> k8 := [[[3,4,3],[3]],[F1,-F1]];;
gap> k9 := [[[4,3,4],[4]],[F1,-F1]];;

gap> KI := [k1,k2,k3,k4,k5,k6,k7,k8,k9];;
</pre></div>

The input can be displayed with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(KI);
e1 + -l/mg1^2 + -lg1 + l/m
e2 + -l/mg2^2 + -lg2 + l/m
g1g2g1 + -1g2g1g2
g1e1 + -l^-1e1
g2e2 + -l^-1e2
e1g2e1 + -le1
e2g1e2 + -le2
e1e2e1 + -1e1
e2e1e2 + -1e2
</pre></div>

Now calculate the Gröbner basis with trace information, using the function <code class="func">SGrobnerTrace</code> (<a href="chap3.html#X78AE6EED83B97595">3.7-5</a>):

<div class="example"><pre>
gap> GB := SGrobnerTrace(KI);;
#I number of entered polynomials is 9
#I number of polynomials after reduction is 9
#I End of phase I
#I End of phase II
#I List of todo lengths is [ 8, 7, 6, 5, 4, 6, 4, 4, 4, 3, 3, 2, 1, 0 ]
#I End of phase III
#I End of phase IV
#I The computation took 484 msecs.
</pre></div>

The full trace can be printed with <code class="func">PrintTraceList</code> (<a href="chap3.html#X83D1560C7F2A04BA">3.7-2</a>), while printing only the relations (and no trace) can be invoked by <code class="func">PrintNPListTrace</code> (<a href="chap3.html#X7DD0B56D7BD6CD98">3.7-4</a>). Since the total trace is very long we do not call <code class="code">PrintTraceList(GB)</code> here but only show two polynomial expressions from the Gröbner basis with <code class="func">PrintTracePol</code> (<a href="chap3.html#X8039BEE77C070FB1">3.7-3</a>):

<div class="example"><pre>
gap> PrintNPListTrace(GB);
g1^2 + m/-le1 + mg1 + -1
g1e1 + -l^-1e1
g2^2 + m/-le2 + mg2 + -1
g2e2 + -l^-1e2
e1g1 + 1/-le1
e1^2 + (l^2-l*m-1)/(l*m)e1
e2g2 + 1/-le2
e2^2 + (l^2-l*m-1)/(l*m)e2
g1g2e1 + -1e2e1
g1e2e1 + me2e1 + -1g2e1 + -me1
g2g1g2 + 1/-1g1g2g1
g2g1e2 + -1e1e2
g2e1g2 + -1g1e2g1 + -me2g1 + me1g2 + mg2e1 + -mg1e2 + -m^2e2 + m^2e1
g2e1e2 + me1e2 + -1g1e2 + -me2
e1g2g1 + -1e1e2
e1g2e1 + -le1
e1e2g1 + me1e2 + -1e1g2 + -me1
e1e2e1 + -1e1
e2g1g2 + -1e2e1
e2g1e2 + -le2
e2e1g2 + me2e1 + -1e2g1 + -me2
e2e1e2 + -1e2
gap> PrintTracePol(GB[1]);
m/-lG(1)
gap> PrintTracePol(GB[10]);
-l*m/(-l*m-1)G(1)g1e2e1 + -l*m/(l*m+1)g1G(1)e2e1 + l^2*m/(-l*m-1)G(
1)g2g1e1 + l*m^2/(-l*m-1)G(1)g2g1e2e1 + -l/(-l*m-1)g2G(
1)g1e2e1 + -l/(l*m+1)g2g1G(1)e2e1 + l^2/(-l*m-1)g2G(
1)g2g1e1 + l*m/(-l*m-1)g2G(1)g2g1e2e1 + -l*m/(-l*m-1)e1g2G(
1)g2g1e1 + -l/(-l*m-1)g2e1g2G(1)g2g1e1 + -m/-lG(
2)g1e2e1 + -l^2*m/(-l*m-1)g2g1G(2)e1 + -l^2/(-l*m-1)g2^2g1G(
2)e1 + m^2/(-l*m-1)e1G(2)g1e2e1 + m/(-l*m-1)g2e1G(
2)g1e2e1 + -l*m/(l*m+1)e1g2^2g1G(2)e1 + -l/(l*m+1)g2e1g2^2g1G(
2)e1 + l^3*m/(-l*m-1)G(3)e1 + l^3/(-l*m-1)g1G(3)e1 + l^3/(-l*m-1)G(
3)g2e1 + l^3/(-l*m-1)g2G(3)e1 + l^2*m^2/(-l*m-1)G(3)e2e1 + l^2*m/(-l*m-1)g1G(
3)e2e1 + l^3/(-l*m^2-m)g2g1G(3)e1 + l^3/(-l*m^2-m)g2G(
3)g2e1 + l^2*m/(-l*m-1)G(3)g2e2e1 + l^2*m/(-l*m-1)g2G(
3)e2e1 + -l^2*m/(-l*m-1)e1g2G(3)e1 + l^2/(-l*m-1)g2g1G(
3)e2e1 + l^2/(-l*m-1)g2G(3)g2e2e1 + -l^2/(-l*m-1)g2e1g2G(
3)e1 + -l^2/(-l*m-1)e1g2g1G(3)e1 + -l^2/(-l*m-1)e1g2G(
3)g2e1 + -l^2/(-l*m^2-m)g2e1g2g1G(3)e1 + -l^2/(-l*m^2-m)g2e1g2G(
3)g2e1 + -l*m/(-l*m-1)G(4)e2e1 + -l/(-l*m-1)g2G(4)e2e1 + -l*mg2g1G(
5)e1 + l^2*m/(-l*m-1)g2g1g2G(5)e1 + -lg2^2g1G(5)e1 + l^2/(-l*m-1)g2^2g1g2G(
5)e1 + l*m/(-l*m-1)G(6)g2g1e1 + l/(-l*m-1)g2G(6)g2g1e1 + m/-lG(
7)e1 + -m^2/(-l*m-1)e1G(7)e1 + -m/(-l*m-1)g2e1G(7)e1 + mG(8) + g2G(8)
</pre></div>

In order to test whether the expression for <code class="code">GB[10]</code> is as claimed we use <code class="func">EvalTrace</code> (<a href="chap3.html#X813454F6799B1D57">3.7-1</a>), For each traced polynomial <code class="code">x</code> in <code class="code">GB</code>, we equate the evaluated expression <code class="code">x.trace</code>, in which each occurrence of <code class="code">G(i)</code> is replaced by <code class="code">KI[i]</code> by use of <code class="func">EvalTrace</code> (<a href="chap3.html#X813454F6799B1D57">3.7-1</a>), with <code class="code">x.pol</code>.

<div class="example"><pre>
gap> ForAll(GB,x->EvalTrace(x,KI)=x.pol);
false
</pre></div>

As a result the dimension of the quotient algebra can be calculated with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>) and the quotient algebra itself with <code class="func">BaseQA</code> (<a href="chap3.html#X7EAA04247B2C6330">3.5-1</a>).

<div class="example"><pre>
gap> GB_pols:=List(GB,x->x.pol);;
gap> PrintNPList(GB_pols);
g1^2 + m/-le1 + mg1 + -1
g1e1 + -l^-1e1
g2^2 + m/-le2 + mg2 + -1
g2e2 + -l^-1e2
e1g1 + 1/-le1
e1^2 + (l^2-l*m-1)/(l*m)e1
e2g2 + 1/-le2
e2^2 + (l^2-l*m-1)/(l*m)e2
g1g2e1 + -1e2e1
g1e2e1 + me2e1 + -1g2e1 + -me1
g2g1g2 + 1/-1g1g2g1
g2g1e2 + -1e1e2
g2e1g2 + -1g1e2g1 + -me2g1 + me1g2 + mg2e1 + -mg1e2 + -m^2e2 + m^2e1
g2e1e2 + me1e2 + -1g1e2 + -me2
e1g2g1 + -1e1e2
e1g2e1 + -le1
e1e2g1 + me1e2 + -1e1g2 + -me1
e1e2e1 + -1e1
e2g1g2 + -1e2e1
e2g1e2 + -le2
e2e1g2 + me2e1 + -1e2g1 + -me2
e2e1e2 + -1e2
gap> DimQA(GB_pols,2);
6
gap> B:=BaseQA(GB_pols,2,0);;
gap> PrintNPList(B);
1
g1
g2
g1g2
g2g1
g1g2g1
</pre></div>

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

<h4>A.10 A commutative example by Mora</h4>

Here we present a commutative example from page 339 of <q>An introduction to commutative and non-commutative Gröbner Bases</q>, by Teo Mora <a href="chapBib.html#biBTCS::Mora1994:131">[Mor94]</a>. It involves the seven variables a,b,c,d,e,f,g. In order to force commuting between each pair from {a,b,c,d,e,f,g}, we let part of the input equations be the homogeneous binomials of the form xy - yx. GBNP is built for non-commutative polynomial arithmetic, and should handle the commutative case by means of this forced commutation. But it should not be considered as a serious alternative to the well-known Gröbner bases packages when it comes to efficiency.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

The relations will be entered as GAP polynomials and converted to NP form (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) with <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>).

<div class="example"><pre>
gap> F:=GF(7);; ef:=One(F);;
gap> A:=FreeAssociativeAlgebraWithOne(F, "a", "b", "c", "d", "e", "f", "g");
<algebra-with-one over GF(7), with 7 generators>
gap> gens:=GeneratorsOfAlgebra(A);
[ (Z(7)^0)*<identity ...>, (Z(7)^0)*a, (Z(7)^0)*b, (Z(7)^0)*c, (Z(7)^0)*d,
 (Z(7)^0)*e, (Z(7)^0)*f, (Z(7)^0)*g ]
gap> a:=gens[2];; b:=gens[3];; c:=gens[4];; d:=gens[5];; e:=gens[6];; f:=gens[7];;
gap> g:=gens[8];; ea:=gens[1];;

gap> rels := [ a^3 + f*a,
> a^9 + c*a^3 + g*a,
> a^81 + c*a^9 + d*a^3,
> c*a^81 + d*a^9 + e*a^3,
> a^27 + d*a^81 + e*a^9 + f*a^3,
> b + c*a^27 + e*a^81 + f*a^9 + g*a^3,
> c*b + d*a^27 + f*a^81 + g*a^9,
> a + d*b + e*a^27 + g*a^81,
> c*a + e*b + f*a^27,
> d*a + f*b + g*a^27,
> e*a + g*b,
> b^3 - b ];;
</pre></div>

Some relations added to enforce commutativity.

<div class="example"><pre>
gap> for i in [1..6] do
> for j in [i+1..7] do
> Add(rels,gens[i+1]*gens[j+1]-gens[j+1]*gens[i+1]);
> od;
> od;
</pre></div>

Now the relations are converted to NP form (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) with the function <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>).

<div class="example"><pre>
gap> KI:=GP2NPList(rels);;
</pre></div>

The Gröbner basis can be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>) and printed with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>).

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I number of entered polynomials is 33
#I number of polynomials after reduction is 33
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 24820 msecs.
gap> PrintNPList(GB);
a
b
dc + Z(7)^3cd
ec + Z(7)^3ce
ed + Z(7)^3de
fc + Z(7)^3cf
fd + Z(7)^3df
fe + Z(7)^3ef
gc + Z(7)^3cg
gd + Z(7)^3dg
ge + Z(7)^3eg
gf + Z(7)^3fg
</pre></div>

To determine whether the quotient algebra is finite dimensional we invoke <code class="func">FinCheckQA</code> (<a href="chap3.html#X792E39A98717D779">3.6-2</a>), using as arguments the leading monomials of <code class="code">GB</code> and 7, the number of variables involved. The leading monomials of <code class="code">GB</code> are obtained by <code class="func">LMonsNP</code> (<a href="chap3.html#X7A42AE79811CC5D7">3.3-10</a>).

<div class="example"><pre>
gap> F := LMonsNP(GB);;
gap> FinCheckQA(F,7);
false
</pre></div>

Thus, the quotient algebra turns out to be infinite dimensional. This is no surprise as the Gröbner basis shows it is actually the free commutative algebra generated by c,d,e,f,g. In particular, it has polynomial growth of degree 5. This is confirmed by application of <code class="func">DetermineGrowthQA</code> (<a href="chap3.html#X83C57C3A7DCF0471">3.6-1</a>), with the first two arguments as for <code class="code">FinCheckQA</code> above and third argument <code class="code">false</code>, indicating that an interval for the degree of the polynomial degree will suffice.

<div class="example"><pre>
gap> DetermineGrowthQA(F,7,false);
5
</pre></div>

It turns out that this quick version already gives an exact answer. More time consuming would be the algorithm run with third argument equal to <code class="code">true</code>.

<div class="example"><pre>
gap> DetermineGrowthQA(F,7,true);
5
</pre></div>

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

<h4>A.11 Tracing an example by Mora</h4>

This example of a non-commutative Gröbner basis computation is from page 18 of <q>An introduction to commutative and non-commutative Gröbner Bases</q>, by Teo Mora <a href="chapBib.html#biBTCS::Mora1994:131">[Mor94]</a>. The traced version of the algorithm will be used. The input is {xyx-y,yxy-y}. The answer should be {yy-xy,yx-xy,xxy-y}.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 2 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,2);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Let the variables be printed as x and y instead of a and b by means of <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>)

<div class="example"><pre>
gap> GBNP.ConfigPrint("x","y");
</pre></div>

Next we input the relations in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). They will be assigned to <code class="code">KI</code>.

<div class="example"><pre>
gap> xyx := [[[1,2,1],[2]],[1,-1]];;
gap> yxy := [[[2,1,2],[2]],[1,-1]];;
gap> KI:=[xyx,yxy];;
</pre></div>

The relations can be shown with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(KI);
xyx - y
yxy - y
</pre></div>

The Gröbner basis with trace can now be calculated with <code class="func">SGrobnerTrace</code> (<a href="chap3.html#X78AE6EED83B97595">3.7-5</a>):

<div class="example"><pre>
gap> GB := SGrobnerTrace(KI);
#I number of entered polynomials is 2
#I number of polynomials after reduction is 2
#I End of phase I
#I End of phase II
#I j =2
#I Current number of elements in todo is 1
#I j =3
#I Current number of elements in todo is 0
#I List of todo lengths is [ 2, 1, 0 ]
#I End of phase III
#I End of phase IV
#I The computation took 4 msecs.
[ rec( pol := [ [ [ 2, 1 ], [ 1, 2 ] ], [ 1, -1 ] ],
 trace := [ [ [ ], 1, [ 2 ], -1 ], [ [ 2 ], 1, [ ], 1 ],
 [ [ 1 ], 2, [ ], 1 ], [ [ ], 2, [ 1 ], -1 ] ] ),
 rec( pol := [ [ [ 2, 2 ], [ 1, 2 ] ], [ 1, -1 ] ],
 trace := [ [ [ 2 ], 1, [ ], -1 ], [ [ ], 1, [ 2 ], -1 ],
 [ [ 2 ], 1, [ ], 1 ], [ [ ], 2, [ 1 ], 1 ], [ [ 1 ], 2, [ ], 1 ],
 [ [ ], 2, [ 1 ], -1 ] ] ),
 rec( pol := [ [ [ 1, 1, 2 ], [ 2 ] ], [ 1, -1 ] ],
 trace := [ [ [ ], 1, [ ], 1 ], [ [ 1 ], 1, [ 2 ], 1 ],
 [ [ 1, 2 ], 1, [ ], -1 ], [ [ 1, 1 ], 2, [ ], -1 ],
 [ [ 1 ], 2, [ 1 ], 1 ] ] ) ]
</pre></div>

The Gröbner basis can be printed with <code class="func">PrintNPListTrace</code> (<a href="chap3.html#X7DD0B56D7BD6CD98">3.7-4</a>):

<div class="example"><pre>
gap> PrintNPListTrace(GB);
yx - xy
y^2 - xy
x^2y - y
</pre></div>

The trace of the Gröbner basis can be printed with <code class="func">PrintTraceList</code> (<a href="chap3.html#X83D1560C7F2A04BA">3.7-2</a>):

<div class="example"><pre>
gap> PrintTraceList(GB);
- G(1)y + yG(1) - G(2)x + xG(2)

- G(1)y + xG(2)

G(1) + xG(1)y - xyG(1) + xG(2)x - x^2G(2)
</pre></div>

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

<h4>A.12 Finiteness of the Weyl group of type E_6</h4>

This example extends <a href="chapA.html#X7C7742957CEC6E7B">A.5</a>, which computes the order of the Weyl group of type E_6.

Here, before the dimension is calculated, it is checked whether the quotient algebra is finite dimensional or infinite dimensional. The function <code class="func">FinCheckQA</code> (<a href="chap3.html#X792E39A98717D779">3.6-2</a>) is used for this computation. For the use of <code class="func">PreprocessAnalysisQA</code> (<a href="chap3.html#X863124677B933CEE">3.6-4</a>) to speed up the check, see Example <a href="chapA.html#X7B1822C67CF83041">A.13</a>.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 2 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,2);
</pre></div>

Then input the relations in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). They will be assigned to <code class="code">KI</code>. These relations are the same as those in Example 3.

<div class="example"><pre>
gap> k1 := [[[1,3,1],[3,1,3]],[1,-1]];;
gap> k2 := [[[4,3,4],[3,4,3]],[1,-1]];;
gap> k3 := [[[4,2,4],[2,4,2]],[1,-1]];;
gap> k4 := [[[4,5,4],[5,4,5]],[1,-1]];;
gap> k5 := [[[6,5,6],[5,6,5]],[1,-1]];;
gap> k6 := [[[1,2],[2,1]],[1,-1]];;
gap> k7 := [[[1,4],[4,1]],[1,-1]];;
gap> k8 := [[[1,5],[5,1]],[1,-1]];;
gap> k9 := [[[1,6],[6,1]],[1,-1]];;
gap> k10 := [[[2,3],[3,2]],[1,-1]];;
gap> k11 := [[[2,5],[5,2]],[1,-1]];;
gap> k12 := [[[2,6],[6,2]],[1,-1]];;
gap> k13 := [[[3,5],[5,3]],[1,-1]];;
gap> k14 := [[[3,6],[6,3]],[1,-1]];;
gap> k15 := [[[4,6],[6,4]],[1,-1]];;
gap> k16 := [[[1,1],[]],[1,-1]];;
gap> k17 := [[[2,2],[]],[1,-1]];;
gap> k18 := [[[3,3],[]],[1,-1]];;
gap> k19 := [[[4,4],[]],[1,-1]];;
gap> k20 := [[[5,5],[]],[1,-1]];;
gap> k21 := [[[6,6],[]],[1,-1]];;
gap> KI := [k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,
> k11,k12,k13,k14,k15,k16,k17,k18,k19,k20,k21
> ];;
</pre></div>

The Gröbner basis can now be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>):

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I number of entered polynomials is 21
#I number of polynomials after reduction is 21
#I End of phase I
#I End of phase II
#I End of phase III
#I Time needed to clean G :0
#I End of phase IV
#I The computation took 96 msecs.
</pre></div>

We will check whether the quotient algebra is finite dimensional or infinite dimensional. The function <code class="func">FinCheckQA</code> (<a href="chap3.html#X792E39A98717D779">3.6-2</a>) exists for this purpose. Its first argument is the list of leading monomials of a Gröbner basis and its second argument the number of symbols. The leading monomials can be calculated with <code class="func">LMonsNP</code> (<a href="chap3.html#X7A42AE79811CC5D7">3.3-10</a>).

<div class="example"><pre>
gap> L:=LMonsNP(GB);;
gap> FinCheckQA(L,6);
true
gap> time;
60
</pre></div>

If a quotient algebra is finite dimensional, the dimension can be calculated with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>), the arguments are the Gröbner basis <code class="code">GB</code> and the number of symbols <code class="code">6</code>. Since <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) is set to 2, we get timing information from <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>):

<div class="example"><pre>
gap> dim := DimQA(GB,6);
#I The computation took 144 msecs.
51840
</pre></div>

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

<h4>A.13 Preprocessing for Weyl group computations</h4>

This example extends Example <a href="chapA.html#X7C7742957CEC6E7B">A.5</a> with the following action: after the Gröbner basis computation, we first check if the quotient algebra is finite dimensional or infinite dimensional before we possibly try to compute that dimension. Preprocessing of the set of leading terms of the Gröbner basis is used to speed up the check. The functions <code class="func">PreprocessAnalysisQA</code> (<a href="chap3.html#X863124677B933CEE">3.6-4</a>) and <code class="func">FinCheckQA</code> (<a href="chap3.html#X792E39A98717D779">3.6-2</a>) are used for the computations. Even without preprocessing this already goes fast. Still, preprocessing can speed up more involved cases. For instance, after adapting this example to run for E7, we found that preprocessing speeds up the computation from 400 secs to about 40 secs. (Be aware that Gröbner basis computation will take a while for E7.)

More information about the preprocessing can be found in the preprint <q>The dimensionality of quotient algebras</q> <a href="chapBib.html#biBKrook2003">[Kro03]</a> which is part of the documentation.

Note: there is no information on the amount of preprocessing which is optimal, but in general for big examples, even full preprocessing is better than using no preprocessing at all.

Note: Example <a href="chapA.html#X8599AE8F7E9E0368">A.12</a> also determines if the quotient algebra appearing here is finite or infinite dimensional but does not use preprocessing.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 0 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 2 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,0);
gap> SetInfoLevel(InfoGBNPTime,2);
</pre></div>

Then input the relations in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). They will be assigned to <code class="code">KI</code>.

<div class="example"><pre>
gap> k1 := [[[1,3,1],[3,1,3]],[1,-1]];;
gap> k2 := [[[4,3,4],[3,4,3]],[1,-1]];;
gap> k3 := [[[4,2,4],[2,4,2]],[1,-1]];;
gap> k4 := [[[4,5,4],[5,4,5]],[1,-1]];;
gap> k5 := [[[6,5,6],[5,6,5]],[1,-1]];;
gap> k6 := [[[1,2],[2,1]],[1,-1]];;
gap> k7 := [[[1,4],[4,1]],[1,-1]];;
gap> k8 := [[[1,5],[5,1]],[1,-1]];;
gap> k9 := [[[1,6],[6,1]],[1,-1]];;
gap> k10 := [[[2,3],[3,2]],[1,-1]];;
gap> k11 := [[[2,5],[5,2]],[1,-1]];;
gap> k12 := [[[2,6],[6,2]],[1,-1]];;
gap> k13 := [[[3,5],[5,3]],[1,-1]];;
gap> k14 := [[[3,6],[6,3]],[1,-1]];;
gap> k15 := [[[4,6],[6,4]],[1,-1]];;
gap> k16 := [[[1,1],[]],[1,-1]];;
gap> k17 := [[[2,2],[]],[1,-1]];;
gap> k18 := [[[3,3],[]],[1,-1]];;
gap> k19 := [[[4,4],[]],[1,-1]];;
gap> k20 := [[[5,5],[]],[1,-1]];;
gap> k21 := [[[6,6],[]],[1,-1]];;
gap> KI := [k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,
> k11,k12,k13,k14,k15,k16,k17,k18,k19,k20,k21
> ];;
</pre></div>

The Gröbner basis can now be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>):

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I Time needed to clean G :0
#I The computation took 104 msecs.
</pre></div>

Check the dimensionality of the quotient algebra. We will check whether it is finite dimensional or infinite dimensional. In case of finite dimensionality we can compute this dimension.

The function <code class="func">FinCheckQA</code> (<a href="chap3.html#X792E39A98717D779">3.6-2</a>), which is used to check finite dimensionality has as first argument the list of leading monomials of a Gröbner basis and as second argument the number of symbols. The monomials can be calculated with <code class="func">LMonsNP</code> (<a href="chap3.html#X7A42AE79811CC5D7">3.3-10</a>). They then will be preprocessed using 4 recursions. If you want full preprocessing, use 0 instead of 4 as a parameter for the number of recursions.

<div class="example"><pre>
gap> L:=LMonsNP(GB);;
gap> L:=PreprocessAnalysisQA(L,6,4);;
gap> time;
4
gap> fd:=FinCheckQA(L,6);
true
gap> time;
4
</pre></div>

If a quotient algebra is finite dimensional, the dimension can be calculated with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>), the arguments are the Gröbner basis <code class="code">GB</code> and the number of symbols <code class="code">6</code>. Since <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) is set to 2, we get timing information from <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>):

<div class="example"><pre>
gap> dim := DimQA(GB,6);
#I The computation took 176 msecs.
51840
</pre></div>

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

<h4>A.14 A quotient algebra with exponential growth</h4>

This example demonstrates an instance in which the quotient algebra is infinite dimensional and has exponential growth. We start out with <code class="code">KI</code>:=[y^4-y^2,x^2y-xy] and obtain a Gröbner basis with leading terms [xxy,yyy]. The quotient algebra will thus have exponential growth since the cycles (xyyx)^n and (xy)^m intersect in the common subwords xy (and in yx). This is explained in <a href="chapBib.html#biBKrook2003">[Kro03]</a>. The function <code class="func">DetermineGrowthQA</code> (<a href="chap3.html#X83C57C3A7DCF0471">3.6-1</a>) is used for the computation.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 2 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,2);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Let the variables be printed as x and y instead of a and b by means of <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>)

<div class="example"><pre>
gap> GBNP.ConfigPrint("x","y");
</pre></div>

Then input the relations in NP format (see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>). They will be assigned to <code class="code">KI</code>.

<div class="example"><pre>
gap> k1 := [[[2,2,2,2],[2,2]],[1,-1]];;
gap> k2 := [[[1,1,2],[1,2]],[1,-1]];;
gap> KI := [k1,k2];;
gap> PrintNPList(KI);
y^4 - y^2
x^2y - xy
</pre></div>

We calculate the Gröbner basis with the function <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>) and print it with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>).

<div class="example"><pre>
gap> GB := SGrobner(KI);;
#I number of entered polynomials is 2
#I number of polynomials after reduction is 2
#I End of phase I
#I End of phase II
#I List of todo lengths is [ 0 ]
#I End of phase III
#I G: Cleaning finished, 0 polynomials reduced
#I End of phase IV
#I The computation took 0 msecs.
gap> PrintNPList(GB);
x^2y - xy
y^4 - y^2
</pre></div>

Next we check the dimensionality of the quotient algebra with the function <code class="func">FinCheckQA</code> (<a href="chap3.html#X792E39A98717D779">3.6-2</a>) or the function <code class="func">DetermineGrowthQA</code> (<a href="chap3.html#X83C57C3A7DCF0471">3.6-1</a>). These functions expect as first argument a list <var class="Arg">F</var> of leading terms of a Gröbner basis, which can be calculated with the function <code class="func">LMonsNP</code> (<a href="chap3.html#X7A42AE79811CC5D7">3.3-10</a>) and as second argument the number of symbols (here equal to 2). The function <code class="func">DetermineGrowthQA</code> (<a href="chap3.html#X83C57C3A7DCF0471">3.6-1</a>) will not only report whether a Gröbner basis is finite, but will also provide information about its growth.

<div class="example"><pre>
gap> L:=LMonsNP(GB);
[ [ 1, 1, 2 ], [ 2, 2, 2, 2 ] ]
gap> fd:=FinCheckQA(L,2);
false
gap> fd:=DetermineGrowthQA(L,2,false);
"exponential growth"
</pre></div>

Although the quotient algebra is infinite dimensional, multiplication of two elements can be carried out by <code class="func">MulQA</code> (<a href="chap3.html#X80C4D0E882B05FDF">3.5-5</a>). We print three positive powers of x+y.

<div class="example"><pre>
gap> w := [[[1],[2]],[1,1]];;
gap> hlp := [[[]],[1]];;
gap> for i in [3..5] do
> hlp := MulQA(hlp, w, GB);
> Print("\n (x+y)^",i," = \n");
> PrintNP(hlp);
> od;

(x+y)^3 =
y + x

(x+y)^4 =
y^2 + yx + xy + x^2

(x+y)^5 =
y^3 + y^2x + yxy + yx^2 + xy^2 + xyx + x^3 + xy
</pre></div>

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

<h4>A.15 A commutative quotient algebra of polynomial growth</h4>

This example extends <a href="chapA.html#X7F5A6ABA85CDB6E2">A.7</a>, a commutative example from Some Tapas of Computer Algebra <a href="chapBib.html#biBCohenCuypersSterk1999">[CCS99]</a>, page 339.

The result of the Gröbner basis computation should be the union of {a,b} and the set of 6 homogeneous binomials (that is, polynomials with two terms) of degree 2 forcing commuting between c, d, e, and f, as before. After computation of the Gröbner basis, the quotient algebra is studied and found to be infinite dimensional of polynomial growth of degree 4. The function <code class="func">DetermineGrowthQA</code> (<a href="chap3.html#X83C57C3A7DCF0471">3.6-1</a>) is used for this computation. Then part of its Hilbert series is computed. The function <code class="func">HilbertSeriesQA</code> (<a href="chap3.html#X7CFD47367CF309EB">3.6-3</a>) is used for the computations.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 2 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,2);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Now define some functions which will help in the construction of relations. The function <code class="code">powermon(i, exp)</code> will return the monomial i^exp. The function <code class="code">comm(aa, bb)</code> will return a relation forcing commutativity between its two arguments <code class="code">aa</code> and <code class="code">bb</code>.

<div class="example"><pre>
gap> powermon := function(base, exp)
> local ans,i;
> ans := [];
> for i in [1..exp] do ans := Concatenation(ans,[base]); od;
> return ans;
> end;;

gap> comm := function(aa,bb)
> return [[[aa,bb],[bb,aa]],[1,-1]];
> end;;
</pre></div>

Now the relations are entered:

<div class="example"><pre>
gap> p1 := [[[5,1]],[1]];;
gap> p2 := [[powermon(1,3),[6,1]],[1,1]];;
gap> p3 := [[powermon(1,9),Concatenation([3],powermon(1,3))],[1,1]];;
gap> p4 := [[powermon(1,81),Concatenation([3],powermon(1,9)),Concatenation([4],
> powermon(1,3))],[1,1,1]];;
gap> p5 := [[Concatenation([3],powermon(1,81)),Concatenation([4],powermon(1,9)),
> Concatenation([5],powermon(1,3))],[1,1,1]];;
gap> p6 := [[powermon(1,27),Concatenation([4],powermon(1,81)),Concatenation([5],
> powermon(1,9)),Concatenation([6],powermon(1,3))],[1,1,1,1]];;
gap> p7 := [[powermon(2,1),Concatenation([3],powermon(1,27)),Concatenation([5],
> powermon(1,81)),Concatenation([6],powermon(1,9))],[1,1,1,1]];;
gap> p8 := [[Concatenation([3],powermon(2,1)),Concatenation([4],powermon(1,27)),
> Concatenation([6],powermon(1,81))],[1,1,1]];;
gap> p9 := [[Concatenation([],powermon(1,1)),Concatenation([4],powermon(2,1)),
> Concatenation([5],powermon(1,27))],[1,1,1]];;
gap> p10 := [[Concatenation([3],powermon(1,1)),Concatenation([5],powermon(2,1)),
> Concatenation([6],powermon(1,27))],[1,1,1]];;
gap> p11 := [[Concatenation([4],powermon(1,1)),Concatenation([6],powermon(2,1))],
> [1,1]];;
gap> p12 := [[Concatenation([],powermon(2,3)),Concatenation([],powermon(2,1))],
> [1,-1]];;
gap> KI := [p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12];;
gap> for i in [1..5] do
> for j in [i+1..6] do
> Add(KI,comm(i,j));
> od;
> od;
</pre></div>

The relations can be shown with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(KI);
ea
a^3 + fa
a^9 + ca^3
a^81 + ca^9 + da^3
ca^81 + da^9 + ea^3
a^27 + da^81 + ea^9 + fa^3
b + ca^27 + ea^81 + fa^9
cb + da^27 + fa^81
a + db + ea^27
ca + eb + fa^27
da + fb
b^3 - b
ab - ba
ac - ca
ad - da
ae - ea
af - fa
bc - cb
bd - db
be - eb
bf - fb
cd - dc
ce - ec
cf - fc
de - ed
df - fd
ef - fe
</pre></div>

It is usually easier to use the function <code class="func">GP2NP</code> (<a href="chap3.html#X7B0EBCBC7857F1AE">3.1-1</a>) or the function <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>) to enter relations. Entering the first twelve relations and then converting them with <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>) is demonstrated in example 6 (<a href="chapA.html#X7F5A6ABA85CDB6E2">A.7</a>). More about converting can be read in Section <a href="chap3.html#X81ABB91B79E00229">3.1</a>.

The Gröbner basis can now be calculated with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>) and printed with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>).

<div class="example"><pre>
gap> GB := SGrobner(KI);
#I number of entered polynomials is 27
#I number of polynomials after reduction is 8
#I End of phase I
#I End of phase II
#I List of todo lengths is [ 0 ]
#I End of phase III
#I G: Cleaning finished, 0 polynomials reduced
#I End of phase IV
#I The computation took 728 msecs.
[ [ [ [ 1 ] ], [ 1 ] ], [ [ [ 2 ] ], [ 1 ] ],
 [ [ [ 4, 3 ], [ 3, 4 ] ], [ 1, -1 ] ], [ [ [ 5, 3 ], [ 3, 5 ] ], [ 1, -1 ] ]
 , [ [ [ 5, 4 ], [ 4, 5 ] ], [ 1, -1 ] ],
 [ [ [ 6, 3 ], [ 3, 6 ] ], [ 1, -1 ] ], [ [ [ 6, 4 ], [ 4, 6 ] ], [ 1, -1 ] ]
 , [ [ [ 6, 5 ], [ 5, 6 ] ], [ 1, -1 ] ] ]
gap> PrintNPList(GB);
a
b
dc - cd
ec - ce
ed - de
fc - cf
fd - df
fe - ef
</pre></div>

The growth of the quotient algebra can be studied with <code class="func">DetermineGrowthQA</code> (<a href="chap3.html#X83C57C3A7DCF0471">3.6-1</a>). The first argument is the list of leading monomials, which can be calculated with <code class="func">LMonsNP</code> (<a href="chap3.html#X7A42AE79811CC5D7">3.3-10</a>). The second argument is the size of the alphabet.

<div class="example"><pre>
gap> L:=LMonsNP(GB);;
gap> DetermineGrowthQA(L,6,false);
4
gap> time;
0
</pre></div>

Now compute the first 10 terms of the Hilbert Series with <code class="func">HilbertSeriesQA</code> (<a href="chap3.html#X7CFD47367CF309EB">3.6-3</a>) (note that trailing zeroes are removed):

<div class="example"><pre>
gap> HilbertSeriesQA(L,6,10);
[ 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286 ]
</pre></div>

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

<h4>A.16 An algebra over a finite field</h4>

A small example over a field other than the rationals, using the conversion functions from <a href="chap3.html#X81ABB91B79E00229">3.1</a>. The input relations define the symmetric group of degree 3, denoted S_3.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 2 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,2);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Let <code class="code">F</code> be the field GF(2). The relations can be entered as elements of a free associative algebra with one <code class="code">A</code> (see <a href="../../../doc/ref/chap62_mj.html#X845A777584A7D711">Reference: FreeAssociativeAlgebraWithOne for ring, rank (and name)</a>).

<div class="example"><pre>
gap> F:=GF(2);;
gap> A:=FreeAssociativeAlgebraWithOne(F,"a","b");
<algebra-with-one over GF(2), with 2 generators>
gap> g:=GeneratorsOfAlgebraWithOne(A);
[ (Z(2)^0)*a, (Z(2)^0)*b ]
</pre></div>

Enter the relations {a^2-1,b^2-1,(ab)^3-1}, convert them to NP-form, see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>, with <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>) and print them with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> KI_GP := [ g[1]^2-g[1]^0, g[2]^2-g[1]^0, (g[1]*g[2])^3-g[1]^0];
[ (Z(2)^0)*<identity ...>+(Z(2)^0)*a^2, (Z(2)^0)*<identity ...>+(Z(2)^0)*b^2,
 (Z(2)^0)*<identity ...>+(Z(2)^0)*(a*b)^3 ]
gap> KI:=GP2NPList(KI_GP);;
gap> PrintNPList(KI);
a^2 + Z(2)^0
b^2 + Z(2)^0
ababab + Z(2)^0
</pre></div>

Now calculate the Gröbner basis with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>) and print it with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> GB:=SGrobner(KI);;
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I End of phase II
#I length of G =3
#I length of todo is 2
#I length of G =3
#I length of todo is 1
#I length of G =3
#I length of todo is 0
#I List of todo lengths is [ 2, 2, 1, 0 ]
#I End of phase III
#I G: Cleaning finished, 0 polynomials reduced
#I End of phase IV
#I The computation took 0 msecs.
gap> PrintNPList(GB);
a^2 + Z(2)^0
b^2 + Z(2)^0
bab + aba
</pre></div>

Now calculate the dimension of the quotient algebra with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>) (2 symbols) and a base with <code class="func">BaseQA</code> (<a href="chap3.html#X7EAA04247B2C6330">3.5-1</a>) (2 symbols, 0 for whole base) and print the base. This will give a list of elements of the group.

<div class="example"><pre>
gap> DimQA(GB,2);
6
gap> B:=BaseQA(GB,2,0);;
gap> PrintNPList(B);
Z(2)^0
a
b
ab
ba
aba
</pre></div>

We can print the Gröbner basis and the basis of the quotient algebra, converted back to GAP polynomials with <code class="func">NP2GPList</code> (<a href="chap3.html#X844A23EA7D97150C">3.1-4</a>). The functions used to convert the polynomials also require the algebra as an argument. The result is useful for further computations in A.

<div class="example"><pre>
gap> NP2GPList(GB,A);
[ (Z(2)^0)*a^2+(Z(2)^0)*<identity ...>, (Z(2)^0)*b^2+(Z(2)^0)*<identity ...>,
 (Z(2)^0)*b*a*b+(Z(2)^0)*a*b*a ]
gap> NP2GPList(B,A);
[ (Z(2)^0)*<identity ...>, (Z(2)^0)*a, (Z(2)^0)*b, (Z(2)^0)*a*b,
 (Z(2)^0)*b*a, (Z(2)^0)*a*b*a ]
</pre></div>

The matrix of right multiplication with the image of the first variable can be computed by <code class="func">MatrixQA</code> (<a href="chap3.html#X7DFA841A8425DD94">3.5-3</a>).

<div class="example"><pre>
gap> Display(MatrixQA(1,B,GB));
. 1 . . . .
1 . . . . .
. . . . 1 .
. . . . . 1
. . 1 . . .
. . . 1 . .
</pre></div>

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

<h4>A.17 The dihedral group of order 8</h4>

In this example (Example 1 from Linton <a href="chapBib.html#biBMR94k:20022">[Lin93]</a>) the two-sided relations give the group algebra of the group with presentation ⟨ a,b ∣ a^4=b^2=(ab)^2=1⟩, the dihedral group of order 8. It is possible to construct a permutation module of degree 4, over a field <code class="code">k</code>. In this example <code class="code">k</code> will be the field of rational numbers.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Now enter the relations as GAP polynomials. It is possible to enter them with and without module generators. First it is shown how to enter the relations without using a module. It is possible to enter them with a free associative algebra with one over the field (the rational numbers) (see also <a href="../../../doc/ref/chap62_mj.html#X845A777584A7D711">Reference: FreeAssociativeAlgebraWithOne for ring, rank (and name)</a>). For convenience we use the variables <code class="code">a</code> and <code class="code">b</code> for the generators of the algebra and <code class="code">e</code> for the one of the algebra.

<div class="example"><pre>
gap> A:=FreeAssociativeAlgebraWithOne(Rationals, "a", "b");
<algebra-with-one over Rationals, with 2 generators>
gap> a:=A.a;;b:=A.b;;e:=One(A);;
</pre></div>

Now the relations are entered:

<div class="example"><pre>
gap> twosidrels:=[a^4-e,b^2-e,(a*b)^2-e];;
gap> prefixrels:=[b-e];;
</pre></div>

First the relations are converted into NP format, see Section <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>, after which the function <code class="func">SGrobnerModule</code> (<a href="chap3.html#X860966487ED88A43">3.9-1</a>) is called to calculate a Gröbner basis record.

<div class="example"><pre>
gap> GBR:=SGrobnerModule(GP2NPList(prefixrels),GP2NPList(twosidrels));;
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 0 msecs.
#I number of entered polynomials is 7
#I number of polynomials after reduction is 7
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 4 msecs.
</pre></div>

The record GBR has two members: the two-sided relations <code class="code">GBR.ts</code> and the prefix relations <code class="code">GBR.p</code>. It is possible to print these using the function <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(GBR.ts);
b^2 - 1
aba - b
ba^2 - a^2b
bab - a^3
a^4 - 1
a^3b - ba
gap> PrintNPList(GBR.p);
[ b - 1 ]
[ a^3 - ab ]
[ a^2b - a^2 ]
</pre></div>

It is now possible to calculate the standard basis of the quotient module with the function <code class="func">BaseQM</code> (<a href="chap3.html#X7E3160E67C504F37">3.9-2</a>). This function has as arguments the Gröbner basis record <code class="code">GBR</code>, the number of generators of the algebra (2), the number of generators of the module (1), and a variable <code class="code">maxno</code> for returning partial bases (0 means full basis).

<div class="example"><pre>
gap> B:=BaseQM(GBR,2,1,0);;
gap> PrintNPList(B);
[ 1 ]
[ a ]
[ a^2 ]
[ ab ]
</pre></div>

It is also possible to use a module with one generator to enter these relations:

<div class="example"><pre>
gap> D:=A^1;;
gap> gd:=GeneratorsOfLeftModule(D);;
gap> prefixrelsdom:=[gd[1]*(b-e)];;
</pre></div>

It is possible to use the two-sided Gröbner basis which was already calculated.

<div class="example"><pre>
gap> GBR:=SGrobnerModule(GP2NPList(prefixrelsdom),GBR.ts);;
#I number of entered polynomials is 6
#I number of polynomials after reduction is 6
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 4 msecs.
#I number of entered polynomials is 7
#I number of polynomials after reduction is 7
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 0 msecs.
gap> PrintNPList(GBR.p);;
[ b - 1 ]
[ a^3 - ab ]
[ a^2b - a^2 ]
gap> B:=BaseQM(GBR,2,1,0);;
gap> PrintNPList(B);
[ 1 ]
[ a ]
[ a^2 ]
[ ab ]
</pre></div>

To compute the image of right multiplication of the basis element <code class="code">B[Length(B)]</code> of the module with the quotient algebra element corresponding to ab we use the function <code class="func">MulQM</code> (<a href="chap3.html#X805FB42A7EEF510F">3.9-4</a>) with arguments <code class="code">B[Length(B)]</code>, <code class="code">GB2NP(a*b)</code>, and <code class="code">GBR</code> We subsequently use <code class="func">PrintNP</code> (<a href="chap3.html#X7B63BEA87A8D6162">3.2-1</a>) to display the result as a 1-dimensional vector with an entry from A.

<div class="example"><pre>
gap> v := MulQM(B[Length(B)],GP2NP(a*b),GBR);
[ [ [ -1 ] ], [ 1 ] ]
gap> PrintNP(v);
[ 1 ]
</pre></div>

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

<h4>A.18 The dihedral group of order 8 on another module</h4>

In this example (Example 2 from Linton <a href="chapBib.html#biBMR94k:20022">[Lin93]</a>) the two-sided relations give the group algebra of the group with presentation ⟨ a,b∣ a^4=b^2=(ab)^2=1⟩, the dihedral group of order 8. This module relation fixes the all-one vector of Example <a href="chapA.html#X7E4CEC577A18C8ED">A.17</a>: 1 + a(1+a+b).

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 0 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 0 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,0);
gap> SetInfoLevel(InfoGBNPTime,0);
</pre></div>

We will enter the relations as GAP polynomials. It is possible to enter these with and without a module. How to do this is shown in <a href="chapA.html#X7E4CEC577A18C8ED">A.17</a>. The relations here are entered without a module, since the module is only one-dimensional. It is possible to enter them using a free associative algebra with one over the field (the rational numbers) (see also <a href="../../../doc/ref/chap62_mj.html#X845A777584A7D711">Reference: FreeAssociativeAlgebraWithOne for ring, rank (and name)</a>). For convenience we use the variables <code class="code">a</code> and <code class="code">b</code> for the generators of the algebra and <code class="code">e</code> for the one of the algebra.

<div class="example"><pre>
gap> A:=FreeAssociativeAlgebraWithOne(Rationals, "a", "b");
<algebra-with-one over Rationals, with 2 generators>
gap> g:=GeneratorsOfAlgebra(A);;
gap> a:=g[2];;b:=g[3];;e:=g[1];;
</pre></div>

Now the relations are entered:

<div class="example"><pre>
gap> twosidrels:=[a^4-e,b^2-e,(a*b)^2-e];;
gap> prefrels:=[ b-e, e + a * (e + a + b) ];;
</pre></div>

First the relations are converted into NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) after which the function <code class="func">SGrobnerModule</code> (<a href="chap3.html#X860966487ED88A43">3.9-1</a>) is called to calculate a Gröbner basis record.

<div class="example"><pre>
gap> GBR:=SGrobnerModule(GP2NPList(prefrels),GP2NPList(twosidrels));;
</pre></div>

The record GBR has two members: the two-sided relations <code class="code">GBR.ts</code> and the prefix relations <code class="code">GBR.p</code>. It is possible to print these using the function <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(GBR.ts);
b^2 - 1
aba - b
ba^2 - a^2b
bab - a^3
a^4 - 1
a^3b - ba
gap> PrintNPList(GBR.p);
[ b - 1 ]
[ ab + a^2 + a + 1 ]
[ a^3 + a^2 + a + 1 ]
[ a^2b - a^2 ]
</pre></div>

It is now possible to calculate the standard basis of the quotient module with the function <code class="func">BaseQM</code> (<a href="chap3.html#X7E3160E67C504F37">3.9-2</a>). This function has as arguments the Gröbner basis record <code class="code">GBR</code>, the number of generators of the algebra (here it is 2), the number of generators of the mdoule (here it is 1), and a variable <code class="code">maxno</code> for returning partial bases (0 means full basis).

<div class="example"><pre>
gap> B:=BaseQM(GBR,2,1,0);;
gap> PrintNPList(B);
[ 1 ]
[ a ]
[ a^2 ]
</pre></div>

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

<h4>A.19 The dihedral group on a non-cyclic module</h4>

In this example (Example 3 from Linton <a href="chapBib.html#biBMR94k:20022">[Lin93]</a>), the two-sided relations give the group algebra of the group with presentation ⟨ a,b∣ a^4=b^2=(ab)^2=1⟩, the dihedral group of order 8. The module under construction is a non-cyclic module, obtained by taking two copies of the representation of Example <a href="chapA.html#X7E4CEC577A18C8ED">A.17</a> and fusing their one-dimensional submodules.

Load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Create the free associative algebra to enter the relations in:

<div class="example"><pre>
gap> A:=FreeAssociativeAlgebraWithOne(Rationals, "a", "b");
<algebra-with-one over Rationals, with 2 generators>
gap> g:=GeneratorsOfAlgebra(A);;
gap> a:=g[2];;b:=g[3];;e:=g[1];;
</pre></div>

Now the relations are entered:

<div class="example"><pre>
gap> twosidrels:=[a^4-e,b^2-e,(a*b)^2-e];;
gap> D:=A^2;;
gap> y:=GeneratorsOfLeftModule(D);;
gap> modrels:=[y[1]*b-y[1], y[2]*b-y[2], y[1]+y[1]*a*(e+a+b) -y[2]-y[2]*a*(e+a+b)];;
</pre></div>

First the relations are converted into NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) with the function <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>). They are printed in raw form and subsequently in a more legible format.

<div class="example"><pre>
gap> modrelsNP:=GP2NPList(modrels);
[ [ [ [ -1, 2 ], [ -1 ] ], [ 1, -1 ] ], [ [ [ -2, 2 ], [ -2 ] ], [ 1, -1 ] ],
 [ [ [ -1, 1, 2 ], [ -1, 1, 1 ], [ -2, 1, 2 ], [ -2, 1, 1 ], [ -1, 1 ],
 [ -2, 1 ], [ -1 ], [ -2 ] ], [ 1, 1, -1, -1, 1, -1, 1, -1 ] ] ]
gap> PrintNPList(modrelsNP);
[ b - 1 , 0]
[ 0, b - 1 ]
[ ab + a^2 + a + 1 , - ab - a^2 - a - 1 ]
</pre></div>

Next the function <code class="func">SGrobnerModule</code> (<a href="chap3.html#X860966487ED88A43">3.9-1</a>) is called to calculate a Gröbner basis record (see <a href="chap2.html#X80DAE0A97CFC95DD">2.8</a>).

<div class="example"><pre>
gap> GBR:=SGrobnerModule(modrelsNP,GP2NPList(twosidrels));;
#I number of entered polynomials is 3
#I number of polynomials after reduction is 3
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 0 msecs.
#I number of entered polynomials is 9
#I number of polynomials after reduction is 9
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 0 msecs.
</pre></div>

The record <code class="code">GBR</code> has two members: the two-sided relations <code class="code">GBR.ts</code> and the prefix relations <code class="code">GBR.p</code>. It is possible to print these using the function <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(GBR.ts);
b^2 - 1
aba - b
ba^2 - a^2b
bab - a^3
a^4 - 1
a^3b - ba
gap> PrintNPList(GBR.p);
[ 0, b - 1 ]
[ b - 1 , 0]
[ ab + a^2 + a + 1 , - ab - a^2 - a - 1 ]
[ 0, a^3 - ab ]
[ 0, a^2b - a^2 ]
[ a^3 + a^2 + a + 1 , - ab - a^2 - a - 1 ]
[ a^2b - a^2 , 0]
</pre></div>

It is now possible to calculate the standard basis of the quotient module with the function <code class="func">BaseQM</code> (<a href="chap3.html#X7E3160E67C504F37">3.9-2</a>). This function has as arguments the Gröbner basis record <code class="code">GBR</code>, the number of generators of the algebra (in this case 2), the number of generators of the module (in this case 2), and a variable <code class="code">maxno</code> for returning partial bases (0 means full basis).

<div class="example"><pre>
gap> B:=BaseQM(GBR,2,2,0);;
gap> PrintNPList(B);
[ 0, 1 ]
[ 1 , 0]
[ 0, a ]
[ a , 0]
[ 0, a^2 ]
[ 0, ab ]
[ a^2 , 0]
</pre></div>

It is also possible to convert each member of the list <code class="code">B</code> of polynomials in NP form to GAP polynomials to do further calculations within the algebra or module. This can be done with the function <code class="func">NP2GPList</code> (<a href="chap3.html#X844A23EA7D97150C">3.1-4</a>).

<div class="example"><pre>
gap> NP2GPList(B,D);
[ [ <zero> of ..., (1)*<identity ...> ], [ (1)*<identity ...>, <zero> of ... ]
 , [ <zero> of ..., (1)*a ], [ (1)*a, <zero> of ... ],
 [ <zero> of ..., (1)*a^2 ], [ <zero> of ..., (1)*a*b ],
 [ (1)*a^2, <zero> of ... ] ]
</pre></div>

Individual GAP polynomials can be obtained from polynomials in NP form with the function <code class="func">NP2GP</code> (<a href="chap3.html#X86C3912F781ABEDC">3.1-3</a>). This also holds for elements of the free module <code class="code">D</code> in NP form.

<div class="example"><pre>
gap> Display(NP2GP(B[Length(B)],D));
[ (1)*a^2, <zero> of ... ]
</pre></div>

Next we write down the matrices for the right action of the generators on the module by means of <code class="func">MatrixQA</code> (<a href="chap3.html#X7DFA841A8425DD94">3.5-3</a>).

<div class="example"><pre>
gap> Display(MatrixQA(1,B,GBR));
[ [ 0, 0, 1, 0, 0, 0, 0 ],
 [ 0, 0, 0, 1, 0, 0, 0 ],
 [ 0, 0, 0, 0, 1, 0, 0 ],
 [ 0, 0, 0, 0, 0, 0, 1 ],
 [ 0, 0, 0, 0, 0, 1, 0 ],
 [ 1, 0, 0, 0, 0, 0, 0 ],
 [ 1, -1, 1, -1, 1, 1, -1 ] ]
gap> Display(MatrixQA(2,B,GBR));
[ [ 1, 0, 0, 0, 0, 0, 0 ],
 [ 0, 1, 0, 0, 0, 0, 0 ],
 [ 0, 0, 0, 0, 0, 1, 0 ],
 [ 1, -1, 1, -1, 1, 1, -1 ],
 [ 0, 0, 0, 0, 1, 0, 0 ],
 [ 0, 0, 1, 0, 0, 0, 0 ],
 [ 0, 0, 0, 0, 0, 0, 1 ] ]
</pre></div>

In order to compute the image of the vector 2y[1]+3y[2] of the two standard generators of the module under the action of the element aab, we use <code class="func">StrongNormalFormNPM</code> (<a href="chap3.html#X87D51A8379C50A80">3.9-5</a>). Its first argument will be the vector and its second the Gröbner basis. The transformation <code class="func">GP2NP</code> (<a href="chap3.html#X7B0EBCBC7857F1AE">3.1-1</a>) to the NP format needs to be applied to the vector before it can be used as an argument.

<div class="example"><pre>
gap> v:=StrongNormalFormNPM(GP2NP((y[1]*2+y[2]*3)*a*a*b), GBR);;
gap> PrintNP(v);
[ 2a^2 , 3a^2 ]
</pre></div>

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

<h4>A.20 The icosahedral group</h4>

In this example the two-sided relations give the group algebra of the group with presentation ⟨ a,b,c ∣ a^2=b^2=c^2=(ab)^3=(bc)^5=(ac)^2=1⟩, the icosahedral group of order 120. This is the Coxeter group of type H_3. The module under construction is a 3-dimensional reflection representation,

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Create the field containing the golden ratio <code class="code">tau</code>.

<div class="example"><pre>
gap> x := Indeterminate(Rationals,"x");
x
gap> p := x^2+ x-1;
x^2+x-1
gap> K := AlgebraicExtension(Rationals,p);
<algebraic extension over the Rationals of degree 2>
gap> tau:=RootOfDefiningPolynomial(K);
a
</pre></div>

Create the free algebra with three generators over this field:

<div class="example"><pre>
gap> A:=FreeAssociativeAlgebraWithOne(K, "a", "b", "c");
<algebra-with-one over <algebraic extension over the Rationals of degree
2>, with 3 generators>
gap> e:=One(A);; a:=A.a;; b:=A.b;; c:=A.c;;
</pre></div>

The ideal for a quotient of the icosahedral group algebra over this field, in which <code class="code">b</code>*<code class="code">c</code> has a quadratic minimal polynomial involving <code class="code">tau</code>:

<div class="example"><pre>
gap> #(b*c)^2-tau*b*c+e
gap> Irels:=[a^2-e,b^2-e,c^2-e,a*b*a-b*a*b,((b*c)^2-tau*b*c+e)*(b*c-e),a*c-c*a];
[ (!-1)*<identity ...>+(!1)*a^2, (!-1)*<identity ...>+(!1)*b^2,
 (!-1)*<identity ...>+(!1)*c^2, (!1)*a*b*a+(!-1)*b*a*b,
 (!-1)*<identity ...>+(a+1)*b*c+(-a-1)*(b*c)^2+(!1)*(b*c)^3,
 (!1)*a*c+(!-1)*c*a ]
</pre></div>

We now give module relations. The first two describe group elements of a vector stabilizer, the third forces the central element (abc)^5 to be nontrivial.

<div class="example"><pre>
gap> Mrels:=[b*c-e,b-e,(a*b*c)^5+e];;
</pre></div>

First the relations are converted into NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) with the function <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>). Next the function <code class="func">SGrobnerModule</code> (<a href="chap3.html#X860966487ED88A43">3.9-1</a>) is called to calculate a Gröbner basis record (see <a href="chap2.html#X80DAE0A97CFC95DD">2.8</a>).

<div class="example"><pre>
gap> GBR:=SGrobnerModule(GP2NPList(Mrels),GP2NPList(Irels));;
#I number of entered polynomials is 6
#I number of polynomials after reduction is 6
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 16 msecs.
#I number of entered polynomials is 12
#I number of polynomials after reduction is 12
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 36 msecs.
gap> PrintNPList(GBR.ts);;
a^2 + !-1
b^2 + !-1
ca + !-1ac
c^2 + !-1
bab + !-1aba
cbc + !-1bcb + -a-1c + a+1b
bcba + !-1acba + !-1abcb + abac + cb + !-1bc + -a-2ba + a+2ab
cbac + !-1acba + !-1abcb + abac + cb + !-1bc + !-1ba + -a-1ac + a+2ab
bacba + abacb + !-1cba + !-1bcb + !-1abc + -a-2aba + c + a+2a
gap> PrintNPList(GBR.p);;
[ b + !-1 ]
[ c + !-1 ]
[ ac + !-1a ]
[ aba + !-1ab ]
[ abc + ab + -aa + -a ]
</pre></div>

It is now possible to calculate the basis of the quotient algebra with the function <code class="func">BaseQM</code> (<a href="chap3.html#X7E3160E67C504F37">3.9-2</a>). This function has as arguments the Gröbner basis record <code class="code">GBR</code>, the number of generators of the algebra (in this case 3), the number of generators of the free module in which the vectors are chosen (in this case 1), and a variable <code class="code">maxno</code> for returning partial quotient algebras (0 means full basis).

<div class="example"><pre>
gap> B:=BaseQM(GBR,3,1,0);;
gap> PrintNPList(B);
[ !1 ]
[ a ]
[ ab ]
</pre></div>

Calculate the dimension of the quotient algebra with the function <code class="func">DimQM</code> (<a href="chap3.html#X813E6A2C8709C9F3">3.9-3</a>). This function has as arguments the Gröbner basis record <code class="code">GBR</code>, the number of generators of the algebra (in this case 3) and the number of generators of the module (in this case 1).

<div class="example"><pre>
gap> DimQM(GBR,3,1);
3
</pre></div>

Next we write down the matrices for the right action of the generators on the module by means of <code class="func">MatrixQA</code> (<a href="chap3.html#X7DFA841A8425DD94">3.5-3</a>).

<div class="example"><pre>
gap> aa := MatrixQA(1,B,GBR);;
gap> Display(aa);
[ [ !0, !1, !0 ],
 [ !1, !0, !0 ],
 [ !0, !0, !1 ] ]
gap> bb := MatrixQA(2,B,GBR);;
gap> Display(bb);
[ [ !1, !0, !0 ],
 [ !0, !0, !1 ],
 [ !0, !1, !0 ] ]
gap> cc := MatrixQA(3,B,GBR);;
gap> Display(cc);
[ [ !1, !0, !0 ],
 [ !0, !1, !0 ],
 [ a, a, !-1 ] ]
</pre></div>

Finally we check the defining relations for the icosahedral group on the three new matrix generators. This can be done by verifying if the result is equal to the identity matrix or with the function <code class="func">IsOne</code> (<a href="../../../doc/ref/chap31_mj.html#X814D78347858EC13">Reference: IsOne</a>).

<div class="example"><pre>
gap> ee := IdentityMat(3,K);;
gap> Display(ee);
[ [ !1, !0, !0 ],
 [ !0, !1, !0 ],
 [ !0, !0, !1 ] ]
gap> aa^2 = ee;
true
gap> IsOne(aa^2);
true
gap> IsOne(bb^2);
true
gap> IsOne(cc^2);
true
gap> IsOne((aa*bb)^3);
true
gap> IsOne((aa*cc)^2);
true
gap> IsOne((bb*cc)^5);
true
</pre></div>

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

<h4>A.21 The symmetric inverse monoid for a set of size four</h4>

The algebra we will consider is from Example 4 from Linton <a href="chapBib.html#biBMR94k:20022">[Lin93]</a>. Its monomials form the symmetric inverse monoid, that is, the monoid of all partial bijections on a given set, for a set of size four. The presentation is ⟨ s_1,s_2,s_3,e∣ s_i^2=(s_1s_2)^3=(s_2s_3)^3=(s_1s_3)^2=1, e^2=e, s_1e=es_1,s_2e=es_2,es_3e=(es_3)^2=(s_3e)^2⟩. The dimension of the monoid algebra is 209. The monoid has a natural representation of degree 4 by means of partial permutation matrices, which can be obtained by taking prefix relations {e,s_1-1, s_2-1, s_3e-s_3}.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Now enter the relations as GAP polynomials. The module is one dimensional so it is possible to enter it with and without a module. In Example 18 (<a href="chapA.html#X7E4CEC577A18C8ED">A.17</a>) both ways are shown. Here the relations will be entered without a module, with a free associative algebra with one over the field (the rational numbers) (see also <a href="../../../doc/ref/chap62_mj.html#X845A777584A7D711">Reference: FreeAssociativeAlgebraWithOne for ring, rank (and name)</a>). For convenience we use the variables <code class="code">s1</code>, <code class="code">s2</code>, <code class="code">s3</code>, and <code class="code">e</code> for the generators of the algebra, and <code class="code">o</code> for the identity element of the algebra.

<div class="example"><pre>
gap> A:=FreeAssociativeAlgebraWithOne(Rationals, "s1", "s2", "s3", "e");
<algebra-with-one over Rationals, with 4 generators>
gap> g:=GeneratorsOfAlgebra(A);;
gap> s1:=g[2];;s2:=g[3];;s3:=g[4];;e:=g[5];;o:=g[1];;
</pre></div>

It is possible to print symbols like they are printed in the algebra <code class="code">A</code> with the function <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>):

<div class="example"><pre>
gap> GBNP.ConfigPrint(A);
</pre></div>

Now the relations are entered:

<div class="example"><pre>
gap> twosidrels:=[s1^2-o,s2^2-o,s3^2-o,(s1*s2)^3-o,(s2*s3)^3-o,(s1*s3)^2-o,
> e^2-e,s1*e-e*s1,s2*e-e*s2,e*s3*e-(e*s3)^2,e*s3*e-(s3*e)^2];
[ (-1)*<identity ...>+(1)*s1^2, (-1)*<identity ...>+(1)*s2^2,
 (-1)*<identity ...>+(1)*s3^2, (-1)*<identity ...>+(1)*(s1*s2)^3,
 (-1)*<identity ...>+(1)*(s2*s3)^3, (-1)*<identity ...>+(1)*(s1*s3)^2,
 (-1)*e+(1)*e^2, (1)*s1*e+(-1)*e*s1, (1)*s2*e+(-1)*e*s2,
 (1)*e*s3*e+(-1)*(e*s3)^2, (1)*e*s3*e+(-1)*(s3*e)^2 ]
gap> prefixrels:=[e,s1-o,s2-o,s3*e-s3];
[ (1)*e, (-1)*<identity ...>+(1)*s1, (-1)*<identity ...>+(1)*s2,
 (-1)*s3+(1)*s3*e ]
</pre></div>

First the relations are converted into NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) and next the function <code class="func">SGrobnerModule</code> (<a href="chap3.html#X860966487ED88A43">3.9-1</a>) is called to calculate a Gröbner basis record.

<div class="example"><pre>
gap> GBR:=SGrobnerModule(GP2NPList(prefixrels),GP2NPList(twosidrels));;
#I number of entered polynomials is 11
#I number of polynomials after reduction is 11
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 24 msecs.
#I number of entered polynomials is 42
#I number of polynomials after reduction is 42
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 20 msecs.
</pre></div>

The record GBR has two members: the two-sided relations <code class="code">GBR.ts</code> and the prefix relations <code class="code">GBR.p</code>. We print these using the function <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(GBR.ts);
s1^2 - 1
s2^2 - 1
s3s1 - s1s3
s3^2 - 1
es1 - s1e
es2 - s2e
e^2 - e
s2s1s2 - s1s2s1
s3s2s3 - s2s3s2
s3s2s1s3 - s2s3s2s1
s3es3e - es3e
es3es3 - es3e
s3es3s2e - es3s2e
s2s3s2es3e - s3s2es3e
s3es3s2s1e - es3s2s1e
es3s2es3s2 - es3s2es3
s2s3s2s1es3e - s3s2s1es3e
s2s3s2es3s2e - s3s2es3s2e
s2es3s2es3e - es3s2es3e
s1s2s1s3s2es3e - s2s1s3s2es3e
s2s3s2s1es3s2e - s3s2s1es3s2e
s2s3s2es3s2s1e - s3s2es3s2s1e
s2es3s2s1es3e - es3s2s1es3e
es3s2s1es3s2s1 - es3s2s1es3s2
s1s2s1s3s2s1es3e - s2s1s3s2s1es3e
s1s2s1s3s2es3s2e - s2s1s3s2es3s2e
s1s2s1es3s2es3e - s2s1es3s2es3e
s2s3s2s1es3s2s1e - s3s2s1es3s2s1e
s2es3s2s1es3s2e - es3s2s1es3s2e
s1s2s1s3s2s1es3s2e - s2s1s3s2s1es3s2e
s1s2s1s3s2es3s2s1e - s2s1s3s2es3s2s1e
s1s2s1es3s2s1es3e - s2s1es3s2s1es3e
s1s3s2s1es3s2es3e - s3s2s1es3s2es3e
s1s2s1s3s2s1es3s2s1e - s2s1s3s2s1es3s2s1e
s1s2s1es3s2s1es3s2e - s2s1es3s2s1es3s2e
s1s3s2s1es3s2s1es3e - s3s2s1es3s2s1es3e
s1es3s2s1es3s2es3e - es3s2s1es3s2es3e
s1s3s2s1es3s2s1es3s2e - s3s2s1es3s2s1es3s2e
gap> PrintNPList(GBR.p);
[ s1 - 1 ]
[ s2 - 1 ]
[ e ]
[ s3e - s3 ]
[ s3s2e - s3s2 ]
[ s3s2s1e - s3s2s1 ]
</pre></div>

It is now possible to calculate the standard basis of the quotient module with the function <code class="func">BaseQM</code> (<a href="chap3.html#X7E3160E67C504F37">3.9-2</a>). This function has as arguments the Gröbner basis record <code class="code">GBR</code>, the number of generators of the algebra (here this is 4), the number of generators of the module (here this is 1), and a variable <code class="code">maxno</code> for returning partial bases (0 means full basis).

<div class="example"><pre>
gap> B:=BaseQM(GBR,4,1,0);;
gap> PrintNPList(B);
[ 1 ]
[ s3 ]
[ s3s2 ]
[ s3s2s1 ]
</pre></div>

Next we write down the matrices for the right action of the generators on the module. First by means of the list command <code class="func">MatricesQA</code> (<a href="chap3.html#X78E4BF2F7F0D5E74">3.5-4</a>), next one by one by means of <code class="func">MatrixQA</code> (<a href="chap3.html#X7DFA841A8425DD94">3.5-3</a>) within a loop.

<div class="example"><pre>
gap> MatricesQA(4,B,GBR);
[ [ [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ] ],
 [ [ 1, 0, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 0, 1 ] ],
 [ [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ],
 [ [ 0, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 0, 1, 0 ], [ 0, 0, 0, 1 ] ] ]
gap> for i in [1..4] do
> Display(MatrixQA(i,B,GBR)); Print("\n");
> od;
[ [ 1, 0, 0, 0 ],
 [ 0, 1, 0, 0 ],
 [ 0, 0, 0, 1 ],
 [ 0, 0, 1, 0 ] ]

[ [ 1, 0, 0, 0 ],
 [ 0, 0, 1, 0 ],
 [ 0, 1, 0, 0 ],
 [ 0, 0, 0, 1 ] ]

[ [ 0, 1, 0, 0 ],
 [ 1, 0, 0, 0 ],
 [ 0, 0, 1, 0 ],
 [ 0, 0, 0, 1 ] ]

[ [ 0, 0, 0, 0 ],
 [ 0, 1, 0, 0 ],
 [ 0, 0, 1, 0 ],
 [ 0, 0, 0, 1 ] ]

</pre></div>

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

<h4>A.22 A module of the Hecke algebra of type
A_3 over GF(3)</h4>

This example is an extension of Example 5 from Linton, <a href="chapBib.html#biBMR94k:20022">[Lin93]</a>. It concerns the Hecke Algebra of type A_3. By reducing mod 3 but without evaluating at q=1 it is possible to obtain the following representation of the Hecke algebra of type A_3 over GF(3): ⟨ x, y, z∣ x^2+(1-q)*x-q,y^2+(1-q)*y-q,z^2+(1-q)*z-q,y*x*y-x*y*x, z*y*z-y*z*y, z*x-x*z⟩. It has a natural representation of the same dimension as the Lie algebra of type A_3, namely 4. This representation can be obtained with the module relations {x+1,y+1}.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 1 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

Now enter the relations as GAP polynomials. The module is one dimensional so it is possible to enter it with and without a module. Both are used in Example <a href="chapA.html#X7E4CEC577A18C8ED">A.17</a>. Here the relations will be entered without using a module. First a free associative algebra with one is created over the field (GF(3)) (see also <a href="../../../doc/ref/chap62_mj.html#X845A777584A7D711">Reference: FreeAssociativeAlgebraWithOne for ring, rank (and name)</a>). For convenience we use the variables <code class="code">a</code> and <code class="code">b</code> for the generators of the algebra and <code class="code">e</code> for the one of the algebra.

<div class="example"><pre>
gap> q:=Indeterminate(GF(3),"q");
q
gap> A:=FreeAssociativeAlgebraWithOne(Field(q), "x", "y", "z");;
gap> g:=GeneratorsOfAlgebra(A);;
gap> x:=g[2];;y:=g[3];;z:=g[4];;e:=g[1];;q:=q*e;;
</pre></div>

In order to print the variables like they are printed in the algebra <code class="code">A</code> with the function <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>):

<div class="example"><pre>
gap> GBNP.ConfigPrint(A);
</pre></div>

Now the relations are entered:

<div class="example"><pre>
gap> twosidrels:=[x^2+(e-q)*x-q,y^2+(e-q)*y-q,z^2+(e-q)*z-q,
> y*x*y-x*y*x,z*y*z-y*z*y,z*x-x*z];
[ (-q)*<identity ...>+(-q+Z(3)^0)*x+(Z(3)^0)*x^2,
 (-q)*<identity ...>+(-q+Z(3)^0)*y+(Z(3)^0)*y^2,
 (-q)*<identity ...>+(-q+Z(3)^0)*z+(Z(3)^0)*z^2,
 (-Z(3)^0)*x*y*x+(Z(3)^0)*y*x*y, (-Z(3)^0)*y*z*y+(Z(3)^0)*z*y*z,
 (-Z(3)^0)*x*z+(Z(3)^0)*z*x ]
gap> prefixrels:=[x+e,y+e];
[ (Z(3)^0)*<identity ...>+(Z(3)^0)*x, (Z(3)^0)*<identity ...>+(Z(3)^0)*y ]
</pre></div>

First the relations are converted into NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) after which the function <code class="func">SGrobnerModule</code> (<a href="chap3.html#X860966487ED88A43">3.9-1</a>) is called to calculate a Gröbner basis record.

<div class="example"><pre>
gap> GBR:=SGrobnerModule(GP2NPList(prefixrels),GP2NPList(twosidrels));;
#I number of entered polynomials is 6
#I number of polynomials after reduction is 6
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 4 msecs.
#I number of entered polynomials is 9
#I number of polynomials after reduction is 9
#I End of phase I
#I End of phase II
#I End of phase III
#I End of phase IV
#I The computation took 8 msecs.
</pre></div>

The record GBR has three members: the two-sided relations <code class="code">GBR.ts</code>, the prefix relations <code class="code">GBR.p</code>, and the number <code class="code">GBR.pg</code> of generators of the free module. It is possible to print the first two using the function <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>):

<div class="example"><pre>
gap> PrintNPList(GBR.ts);
x^2 + -q+Z(3)^0x + -q
y^2 + -q+Z(3)^0y + -q
zx + -Z(3)^0xz
z^2 + -q+Z(3)^0z + -q
yxy + -Z(3)^0xyx
zyz + -Z(3)^0yzy
zyxz + -Z(3)^0yzyx
gap> PrintNPList(GBR.p);
[ x + Z(3)^0 ]
[ y + Z(3)^0 ]
</pre></div>

It is now possible to calculate the standard basis of the quotient module with the function <code class="func">BaseQM</code> (<a href="chap3.html#X7E3160E67C504F37">3.9-2</a>). This function has as arguments the Gröbner basis record <code class="code">GBR</code>, the number of generators of the algebra (here this is 3), the number of generators of the module (here this is 1), and a variable <code class="code">maxno</code> for returning partial bases (0 means full basis).

<div class="example"><pre>
gap> B:=BaseQM(GBR,3,1,0);;
gap> PrintNPList(B);
[ Z(3)^0 ]
[ z ]
[ zy ]
[ zyx ]
</pre></div>

Next we write down the matrices for the right action of the generators on the module, by means of the command <code class="func">MatricesQA</code> (<a href="chap3.html#X78E4BF2F7F0D5E74">3.5-4</a>).

<div class="example"><pre>
gap> MM := MatricesQA(3,B,GBR);;
gap> for i in [1..Length(MM)] do
> Display(MM[i]); Print("\n");
> od;
[ [ -Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],
 [ 0*Z(3), -Z(3)^0, 0*Z(3), 0*Z(3) ],
 [ 0*Z(3), 0*Z(3), 0*Z(3), Z(3)^0 ],
 [ 0*Z(3), 0*Z(3), q, q-Z(3)^0 ] ]

[ [ -Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ],
 [ 0*Z(3), 0*Z(3), Z(3)^0, 0*Z(3) ],
 [ 0*Z(3), q, q-Z(3)^0, 0*Z(3) ],
 [ 0*Z(3), 0*Z(3), 0*Z(3), -Z(3)^0 ] ]

[ [ 0*Z(3), Z(3)^0, 0*Z(3), 0*Z(3) ],
 [ q, q-Z(3)^0, 0*Z(3), 0*Z(3) ],
 [ 0*Z(3), 0*Z(3), -Z(3)^0, 0*Z(3) ],
 [ 0*Z(3), 0*Z(3), 0*Z(3), -Z(3)^0 ] ]

</pre></div>

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

<h4>A.23 Generalized Temperley-Lieb algebras</h4>

This example shows how the dimension of a Generalized Temperley-Lieb Algebra of type A, D, or E can be calculated. For A_n-1 this is the usual Temperley-Lieb Algebra on n strands with dimension dim TL(A_n-1)={2n choose n}/(n+1). For more information see <a href="chapBib.html#biBGraham1995">[Gra95]</a>.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 0 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 1 (for more information about timing; see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,0);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

The relations are generated automatically from the Coxeter diagram. This example can be easily adapted by specifying the number of points and the set of edges describing another Coxeter diagram. First enter the number of points, <code class="code">numpoints</code>.

<div class="example"><pre>
gap> numpoints:=8;
8
</pre></div>

Now define some edges describing the diagrams of E_n, (these can be easily extended). In this example the dimension of the Generalized Temperley-Lieb algebra of type E_8 will be calculated. For A_1... 10 the command

<code class="code">edges:=[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10]];</code>

can be used. For D_1... 10 the command

<code class="code">edges:=[[1,3],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10]];</code> can

be used.

<div class="example"><pre>
gap> edges:=[[1,3],[2,4],[3,4],[4,5],[5,6],[6,7],[7,8]]; # for E6..8
[ [ 1, 3 ], [ 2, 4 ], [ 3, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 7 ], [ 7, 8 ] ]
</pre></div>

Now enter the relations as GAP polynomials. First a free associative algebra with identity element is created over the Rationals (see also <a href="../../../doc/ref/chap62_mj.html#X845A777584A7D711">Reference: FreeAssociativeAlgebraWithOne for ring, rank (and name)</a>). For convenience the generators are stored in <code class="code">gens</code>.

<div class="example"><pre>
gap> A:=FreeAssociativeAlgebraWithOne(Rationals,numpoints,"e");;
gap> e := GeneratorsOfAlgebraWithOne(A);
[ (1)*e.1, (1)*e.2, (1)*e.3, (1)*e.4, (1)*e.5, (1)*e.6, (1)*e.7, (1)*e.8 ]
</pre></div>

It is possible to print symbols like they are printed in the algebra <code class="code">A</code> with the function <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>):

<div class="example"><pre>
gap> GBNP.ConfigPrint(A);
</pre></div>

Now the relations are generated automatically. For this we need to make sure the edges are sorted and converted to a set.

<div class="example"><pre>
gap> edges:=Set(edges, x->SortedList(x));
[ [ 1, 3 ], [ 2, 4 ], [ 3, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 7 ], [ 7, 8 ] ]
</pre></div>

Now the relations can be generated. The relations are e_i*e_i=e_i, for all i and e_i*e_j*e_i=e_i for all i,j that are connected in the Coxeter diagram and e_i*e_j=e_j*e_i for all i, j that are not connected in the Coxeter diagram.

<div class="example"><pre>
gap> rels:=[];;
gap> for i in [1..numpoints] do
> for j in [1..numpoints] do
> if (i=j) then
> # if i=j then add e.i*e.i=e.i
> Add(rels, e[i]*e[i]-e[i]);
> elif ([i,j] in edges) or ([j,i] in edges) then
> # if {i,j} is an edge then add e.i*e.j*e.i=e.i
> Add(rels, e[i]*e[j]*e[i]- e[i]);
> else
> # if {i,j} is not an edge then add e.i*e.j=e.j*e.i
> # (note: this causes double rules, but that's ok)
> Add(rels, e[i]*e[j]- e[j]*e[i]);
> fi;
> od;
> od;
</pre></div>

Then the relations are converted into NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) after which the function <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>) is called to calculate a Gröbner basis.

<div class="example"><pre>
gap> relsNP:=GP2NPList(rels);;
gap> GB:=SGrobner(relsNP);;
#I The computation took 184 msecs.
</pre></div>

It is now possible to calculate the dimension of the quotient algebra with the function <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>). This function has as arguments the Gröbner basis <code class="code">GB</code> and the number of generators of the algebra (here this is <code class="code">numpoints</code>). To get the full basis the function <code class="func">BaseQA</code> (<a href="chap3.html#X7EAA04247B2C6330">3.5-1</a>) can be used.

<div class="example"><pre>
gap> DimQA(GB,numpoints);
10846
</pre></div>

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

<h4>A.24 The universal enveloping
algebra of a Lie algebra</h4>

Consider the Lie algebra with generators e, f and h, and relations [e,f]=h, [e,h]=-2e, [f,h]=2f. This is the well-known Lie algebra of type A_1. We construct the corresponding universal enveloping algebra of this Lie algebra and show how one can prove that f^2 belongs to the ideal generated by e^2 in that associative algebra. The example is from Knopper's report <a href="chapBib.html#biBKnopper2004">[Kno04]</a>.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 0 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 0 (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,0);
gap> SetInfoLevel(InfoGBNPTime,0);
</pre></div>

Then define the algebra and enter the relations as polynomials in GAP.

<div class="example"><pre>
gap> A:=FreeAssociativeAlgebraWithOne(Rationals, "e", "f", "h");
<algebra-with-one over Rationals, with 3 generators>
gap> e:=A.e;; f:=A.f;; h:=A.h;; o:=One(A);;
gap> uerels:=[f*e-e*f+h,h*e-e*h-2*e,h*f-f*h+2*f];
[ (1)*h+(-1)*e*f+(1)*f*e, (-2)*e+(-1)*e*h+(1)*h*e, (2)*f+(-1)*f*h+(1)*h*f ]
</pre></div>

The relations can be converted to NP format (see <a href="chap2.html#X7FDF3E5E7F33D3A2">2.1</a>) with the function <code class="func">GP2NPList</code> (<a href="chap3.html#X7CF0ED937DDA5A7E">3.1-2</a>) and can be subsequently displayed with <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>).

<div class="example"><pre>
gap> uerelsNP:=GP2NPList(uerels);;
gap> PrintNPList(uerelsNP);
ba - ab + c
ca - ac - 2a
cb - bc + 2b
</pre></div>

Now configure printing in such a way that this algebra is used with the function <code class="func">GBNP.ConfigPrint</code> (<a href="chap3.html#X7F7510A878045D3A">3.2-2</a>).

<div class="example"><pre>
gap> GBNP.ConfigPrint(A);
</pre></div>

The set is actually a Gröbner basis, as can be verified by calculating the Gröbner basis with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>).

<div class="example"><pre>
gap> GB:=SGrobner(uerelsNP);;
gap> PrintNPList(GB);
fe - ef + h
he - eh - 2e
hf - fh + 2f
</pre></div>

Determine whether the quotient algebra is finite dimensional by means of <code class="func">FinCheckQA</code> (<a href="chap3.html#X792E39A98717D779">3.6-2</a>), with arguments the leading monomials of <code class="code">GB</code> and 3, the number of variables involved. The leading monomials of <code class="code">GB</code> are found by invoking <code class="func">LMonsNP</code> (<a href="chap3.html#X7A42AE79811CC5D7">3.3-10</a>).

<div class="example"><pre>
gap> F:=LMonsNP(GB);
[ [ 2, 1 ], [ 3, 1 ], [ 3, 2 ] ]
gap> FinCheckQA(F,3);
false
</pre></div>

Adding the relation e^2=0 results in a finite quotient algebra.

<div class="example"><pre>
gap> extendedrels:=[f*e-e*f+h,h*e-e*h-2*e,h*f-f*h+2*f,e^2];
[ (1)*h+(-1)*e*f+(1)*f*e, (-2)*e+(-1)*e*h+(1)*h*e, (2)*f+(-1)*f*h+(1)*h*f,
 (1)*e^2 ]
gap> extendedrelsNP:=GP2NPList(extendedrels);;
</pre></div>

With the function <code class="func">SGrobnerTrace</code> (<a href="chap3.html#X78AE6EED83B97595">3.7-5</a>) it is possible to calculate a Gröbner basis with trace information.

<div class="example"><pre>
gap> GB:=SGrobnerTrace(extendedrelsNP);;
</pre></div>

The Gröbner basis can now be displayed with <code class="func">PrintNPListTrace</code> (<a href="chap3.html#X7DD0B56D7BD6CD98">3.7-4</a>).

<div class="example"><pre>
gap> PrintNPListTrace(GB);
e^2
eh + e
fe - ef + h
f^2
fh - f
he - e
hf + f
h^2 - 2ef + h
</pre></div>

Note the fourth relation: f^2=0. To view a trace one can use the function <code class="func">PrintTracePol</code> (<a href="chap3.html#X8039BEE77C070FB1">3.7-3</a>).

<div class="example"><pre>
gap> PrintTracePol(GB[4]);
- 1/12G(1)f^2 + 1/12f^2G(1) + 1/12f^2G(1)h - 1/6fG(1)hf + 1/12G(1)hf^2 + 1/
24G(1)ef^3 + 1/24eG(1)f^3 - 1/8fG(1)ef^2 - 1/8feG(1)f^2 + 1/8f^2G(1)ef + 1/
8f^2eG(1)f - 1/24f^3G(1)e - 1/24f^3eG(1) - 1/24G(2)f^3 + 1/8fG(2)f^2 - 1/
8f^2G(2)f + 1/24f^3G(2) + 1/4G(3)f + 1/4fG(3) + 1/12fG(3)h + 1/12fhG(3) - 1/
12G(3)hf - 1/12hG(3)f - 1/12eG(3)f^2 + 1/6feG(3)f - 1/12f^2eG(3) + 1/24G(
4)f^4 - 1/6fG(4)f^3 + 1/4f^2G(4)f^2 - 1/6f^3G(4)f + 1/24f^4G(4)
</pre></div>

This proves that f^2=0 is a consequence of e^2=0 in the universal enveloping algebra of the simple Lie algebra of type A_1.

The function <code class="func">StrongNormalFormTraceDiff</code> (<a href="chap3.html#X8219059A86A54130">3.7-6</a>) can be used to trace the difference between an element and its strong normal form in the terms of <code class="code">extendedrels</code>. Apparently, in the first example the strong normal form of <code class="code">r</code> is <code class="code">r - s.pol=0</code>.

<div class="example"><pre>
gap> r := [[[2,2,2,2,1,1,1,1]],[1]];;
gap> s := StrongNormalFormTraceDiff(r, GB);;

gap> PrintNP(s.pol);
f^4e^4
gap> PrintTracePol(s);
f^4G(4)e^2
gap> PrintNP(AddNP(r,s.pol,1,-1));
0
</pre></div>

One more example where the strong normal form is not zero.

<div class="example"><pre>
gap> r := [[[3,3,3]],[1]];;
gap> s := StrongNormalFormTraceDiff(r, GB);;

gap> PrintNP(s.pol);
h^3 - h
gap> PrintTracePol(s);
- G(1) - 1/2G(1)ef - 1/6eG(1)f + 1/3efG(1) + 1/2fG(1)e + 1/2feG(1) + G(
1)h^2 + 1/2G(1)efh + 1/2eG(1)fh + 1/3efG(1)h - 1/3eG(1)hf - 1/2fG(1)eh - 1/
2feG(1)h - 1/6eG(1)ef^2 - 1/6e^2G(1)f^2 + 1/3efG(1)ef + 1/3efeG(1)f - 1/
6ef^2G(1)e - 1/6ef^2eG(1) + 1/2G(2)f - 1/2fG(2) - 1/2G(2)fh + 1/2fG(2)h + 1/
6eG(2)f^2 - 1/3efG(2)f + 1/6ef^2G(2) - 2/3eG(3)h + 1/3ehG(3) + 1/3e^2G(3)f -
1/3efeG(3) - 1/2G(4)f^2 + fG(4)f - 1/2f^2G(4) + 1/2G(4)f^2h - fG(4)fh + 1/
2f^2G(4)h - 1/6eG(4)f^3 + 1/2efG(4)f^2 - 1/2ef^2G(4)f + 1/6ef^3G(4)
gap> PrintNP(AddNP(r,s.pol,1,-1));
h
</pre></div>

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

<h4>A.25 Serre's exercise</h4>

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,1);
gap> SetInfoLevel(InfoGBNPTime,1);
</pre></div>

In Serre's book <a href="chapBib.html#biBMR1954121">[Ser03]</a> the following exercise can be found: Prove that the group ⟨ {a,b,c}∣ { bab^-1a^-2, cbc^-1b^-2, aca^-1c^-2}⟩ is the trivial group. Here we solve the exercise by running the trace variant of the Gröbner basis function with input the set of equations ba - a^2 b, cb - b^2c, ac - c^2a together with relations forcing that a,b,c are invertible with inverse A,B,C.

<div class="example"><pre>
gap> KI := [ [[[2,1],[1,1,2]],[1,-1]],
> [[[3,2],[2,2,3]],[1,-1]],
> [[[1,3],[3,3,1]],[1,-1]],
> [[[1,4], []],[1,-1]],
> [[[4,1], []],[1,-1]],
> [[[2,5], []],[1,-1]],
> [[[5,2], []],[1,-1]],
> [[[3,6], []],[1,-1]],
> [[[6,3], []],[1,-1]],
> ];;
gap> PrintNPList(KI);
ba - a^2b
cb - b^2c
ac - c^2a
ad - 1
da - 1
be - 1
eb - 1
cf - 1
fc - 1
</pre></div>

We use <code class="func">SGrobnerTrace</code> (<a href="chap3.html#X78AE6EED83B97595">3.7-5</a>), the trace variant of the Gröbner basis computation,

<div class="example"><pre>
gap> GB := SGrobnerTrace(KI);;
#I number of entered polynomials is 9
#I number of polynomials after reduction is 9
#I End of phase I
#I End of phase II
#I List of todo lengths is [ 9, 10, 11, 12, 14, 16, 18, 20, 21, 22, 24, 26, 28, 31, 34, 33, 35, 37, 40,
 43, 46, 49, 52, 56, 59, 62, 61, 60, 64, 64, 65, 65, 68, 71, 76, 76, 80, 88,
 93, 94, 99, 110, 115, 117, 131, 139, 146, 150, 158, 171, 186, 198, 206,
 220, 229, 246, 260, 263, 102, 40, 19, 9, 3, 0 ]
#I End of phase III
#I End of phase IV
#I The computation took 19308 msecs.
</pre></div>

The dimension of the quotient algebra is 1, showing that the group algebra is 1-dimensional. This implies that the group with the above presentation is trivial.

<div class="example"><pre>
gap> GBpols := List([1..Length(GB)], x -> GB[x].pol);;
gap> PrintNPList(GBpols);
a - 1
b - 1
c - 1
d - 1
e - 1
f - 1
gap> DimQA(GBpols,6);
1
</pre></div>

Since the output is large and might spoil the exercise, we confine ourselves to the printing first polynomial <code class="code">GB[1]</code> and the length of its trace. As the trace polynomial expresses <code class="code">GB[1]</code>, which is equal to a-1, as a combination of the binomials in <code class="code">KI</code>, it gives a proof that a can be rewritten within the group to the trivial element. It is easy to derive from this that b and c are also trivial in the group. This justifies the restriction to <code class="code">GB[1]</code>.

<div class="example"><pre>
gap> PrintNP(GB[1].pol);
a - 1
gap> Length(GB[1].trace);
1119
</pre></div>

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

<h4>A.26 Baur and Draisma's transformations</h4>

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,0);
gap> SetInfoLevel(InfoGBNPTime,0);
</pre></div>

The paper <a href="chapBib.html#biBMR2090062">[BD04]</a> by Baur and Draisma uses the computation of a quotient algebra of dimension 37, which we repeat here. The set of equations, after specialisation of the scalars to 1, is as follows.

<div class="example"><pre>
gap> KI := [ [[[2,2]],[1]],
> [[[1,1]],[1]],
> [[[3,3]],[1]],
> [[[1,2,1],[1]],[1,-1]],
> [[[2,1,2],[2]],[1,-1]],
> [[[3,2,3],[3]],[1,-1]],
> [[[2,3,2],[2]],[1,-1]],
> [[[1,3,1],[1]],[1,-1]],
> [[[3,1,3],[3]],[1,-1]],
> [[[1,2,3,1,2,3,1],[1,3,2,1,3,2,1],[1]],[1,1,-1]],
> [[[3,1,2,3,1,2,3],[3,2,1,3,2,1,3],[3]],[1,1,-1]],
> [[[2,3,1,2,3,1,2],[2,1,3,2,1,3,2],[2]],[1,1,-1]],
> ];;
gap> PrintNPList(KI);
b^2
a^2
c^2
aba - a
bab - b
cbc - c
bcb - b
aca - a
cac - c
abcabca + acbacba - a
cabcabc + cbacbac - c
bcabcab + bacbacb - b
</pre></div>

We carry out a traced Gröbner basis computation by use of <code class="func">SGrobnerTrace</code> (<a href="chap3.html#X78AE6EED83B97595">3.7-5</a>), and form the usual Gröbner basis by extracting the polynomials from the traced polynomials using the field indicator <code class="code">.pol</code>.

<div class="example"><pre>
gap> GBT := SGrobnerTrace(KI);;
gap> GB := List([1..Length(GBT)], i -> GBT[i].pol);;
</pre></div>

The dimension of the quotient algebra is computable with <code class="func">DimQA</code> (<a href="chap3.html#X81A50EEE7B56C723">3.5-2</a>).

<div class="example"><pre>
gap> DimQA(GB,3);
37
</pre></div>

In order to express the last GB element, viz.

<div class="example"><pre>
gap> PrintNP(GB[Length(GB)]);
cabcabca + cbacba - ca
</pre></div>

as a combination of elements of <code class="code">KI</code>, we use <code class="func">PrintTracePol</code> (<a href="chap3.html#X8039BEE77C070FB1">3.7-3</a>):

<div class="example"><pre>
gap> PrintTracePol(GBT[Length(GBT)]);
- G(9)bacba + cG(10)
</pre></div>

We compute matrices for left multiplication by generators using <code class="func">MatricesQA</code> (<a href="chap3.html#X78E4BF2F7F0D5E74">3.5-4</a>) and determine the minimal polynomial of the sum of the three matrices.

<div class="example"><pre>
gap> B := BaseQA(GB,3,0);;
gap> M := MatricesQA(3,B,GB);;
gap> f := MinimalPolynomial(Rationals,M[1]+M[2]+M[3]);
x_1^7-6*x_1^5+9*x_1^3-3*x_1
gap> Factors(f);
[ x_1, x_1^6-6*x_1^4+9*x_1^2-3 ]
</pre></div>

It turns out that there are three non-zero numbers u,v,w such that the eigenvalues of the sum are 0,u,v,w,-u,-v,-w. This is the information used in <a href="chapBib.html#biBMR2090062">[BD04]</a>.

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

<h4>A.27 The cola gene puzzle</h4>

A prize question appearing in the January 2005 issue of the Dutch journal "Natuur en Techniek" asked for a DNA change of cows so that they could produce Cola instead of milk. A team of genetic manipulators has tools to perform the following five DNA string operations. (Here the strings before and after the equality sign can be interchanged at will.)

operation 1: TCAT = T;

operation 2: GAG = AG;

operation 3: CTC = TC;

operation 4: AGTA = A;

operation 5: TAT = CT.

The first question is to show how they can transform the milk gene TAGCTAGCTAGCT to the cola gene CTGACTGACT.

A second question is to show that mad cow disease related retro virus CTGCTACTGACT can be avoided at all times. Can this be guaranteed?

We answer these questions using the trace functions of the Gröbner basis package GBNP in Section <a href="chap3.html#X7BA5CAA07890F7AA">3.7</a>.

First load the package and set the standard infolevel <code class="func">InfoGBNP</code> (<a href="chap4.html#X82D40B0E84383BBC">4.2-1</a>) to 0 and the time infolevel <code class="func">InfoGBNPTime</code> (<a href="chap4.html#X7FAE244E80397B9A">4.3-1</a>) to 0 to minimize the printing of data regarding the computation (for more information about the info level, see Chapter <a href="chap4.html#X79C5DF3782576D98">4</a>).

<div class="example"><pre>
gap> LoadPackage("gbnp", false);
true
gap> SetInfoLevel(InfoGBNP,0);
gap> SetInfoLevel(InfoGBNPTime,0);
</pre></div>

We introduce the free algebra <code class="code">ALG</code> on the generators corresponding to the four letters in the DNA code and express the milk gene and cola gene as monomials in this algebra.

<div class="example"><pre>
gap> ALG:=FreeAssociativeAlgebraWithOne(Rationals, "A", "C", "G", "T");;
gap> g:=GeneratorsOfAlgebra(ALG);;
gap> A:=g[2];;
gap> C:=g[3];;
gap> G:=g[4];;
gap> T:=g[5];;

gap> milk := T*A*G*C*T*A*G*C*T*A*G*C*T;;
gap> cola := C*T*G*A*C*T*G*A*C*T;;
</pre></div>

We next enter the set K of binomials x-y corresponding to the five operations x = y listed above. We enter the binomials as members of <code class="code">ALG</code> and let <code class="code">KNP</code> be the corresponding set of NP polynomials.

<div class="example"><pre>
gap> rule1 := T*C*A*T - T;;
gap> rule2 := G*A*G - A*G;;
gap> rule3 := C*T*C - T*C;;
gap> rule4 := A*G*T*A - A;;
gap> rule5 := T*A*T - C*T;;
gap> K := [rule1,rule2,rule3,rule4,rule5];;
gap> KNP := List(K,x-> GP2NP(x));;
</pre></div>

We stipulate how the variables will be printed and print <code class="code">KNP</code>. See <code class="func">PrintNPList</code> (<a href="chap3.html#X832103DC79A9E9D0">3.2-3</a>).

<div class="example"><pre>
gap> GBNP.ConfigPrint("A","C","G","T");
gap> PrintNPList(KNP);
TCAT - T
GAG - AG
CTC - TC
AGTA - A
TAT - CT
</pre></div>

Now calculate the usual Gröbner basis with <code class="func">SGrobner</code> (<a href="chap3.html#X7FEDA29E78B0CEED">3.4-2</a>).

<div class="example"><pre>
gap> GB := SGrobner(KNP);;
</pre></div>

Compare milk and cola after taking their strong normal forms with respect to <code class="code">GB</code> using <code class="func">StrongNormalFormNP</code> (<a href="chap3.html#X8563683E7FA604F8">3.5-6</a>). We observe that they have the same normal form and so there is a way to transform the milk gene into the cola gene.

<div class="example"><pre>
gap> milkNP := GP2NP(milk);;
gap> colaNP := GP2NP(cola);;
gap> milkRed := NP2GP(StrongNormalFormNP(milkNP,GB),ALG);
(1)*T
gap> colaRed := NP2GP(StrongNormalFormNP(colaNP,GB),ALG);
(1)*T
</pre></div>

But this information does not yet show us how to perform the transformation. To this end we calculate the Gröbner basis with trace information, using the function <code class="func">SGrobnerTrace</code> (<a href="chap3.html#X78AE6EED83B97595">3.7-5</a>).

<div class="example"><pre>
gap> GTrace := SGrobnerTrace(KNP);;
</pre></div>

The full trace can be printed with <code class="func">PrintTraceList</code> (<a href="chap3.html#X83D1560C7F2A04BA">3.7-2</a>), but we only print the relations (and no trace) by invoking <code class="func">PrintNPListTrace</code> (<a href="chap3.html#X7DD0B56D7BD6CD98">3.7-4</a>).

<div class="example"><pre>
gap> PrintNPListTrace(GTrace);
CT - T
GA - A
AGT - AT
ATA - A
TAT - T
TCA - TA
</pre></div>

In order to display a proof that milk-cola belongs to the ideal we use <code class="func">StrongNormalFormTraceDiff</code> (<a href="chap3.html#X8219059A86A54130">3.7-6</a>), The result is a record, <code class="code">p</code> say, containing <code class="code">milk-cola</code> in the field <code class="code">p.pol</code> (the normal form will be subtracted from the argument <code class="code">milk-cola</code> to obtain <code class="code">p.pol</code>, but the normal form is zero because the argument belongs to the ideal generated by <code class="code">K</code>). The other field of the record <code class="code">p</code> is <code class="code">p.trace</code>, the traced polynomial, which is best displayed by use of <code class="func">PrintTracePol</code> (<a href="chap3.html#X8039BEE77C070FB1">3.7-3</a>).

<div class="example"><pre>
gap> p := StrongNormalFormTraceDiff(CleanNP(GP2NP(milk-cola)),GTrace);;
gap> NP2GP(p.pol,ALG);
(1)*(T*A*G*C)^3*T+(-1)*(C*T*G*A)^2*C*T
gap> PrintTracePol(p);
- TGATGAG(1) + TAGG(1)ATAT - TATATAGG(1) - TGAG(1)GACT + TGATGACG(1) - G(
1)GACTGACT - TAGCG(1)ATAT - TATAGG(1)AGT + TATATAGCG(1) + TGACG(1)GACT + CG(
1)GACTGACT - TAGG(1)AGTAGT + TAGTAGTAGG(1) + TATAGCG(1)AGT + TAGCG(
1)AGTAGT + TAGTAGG(1)AGCT - TAGTAGTAGCG(1) + TAGG(1)AGCTAGCT - TAGTAGCG(
1)AGCT - TAGCG(1)AGCTAGCT - TATG(2)TAT - TG(2)TATGAT - TGATGAG(3)AT + TAGG(
3)ATATAT - TATATAGG(3)AT - TGAG(3)ATGACT - G(3)ATGACTGACT - TATAGG(
3)ATAGT - TAGG(3)ATAGTAGT + TAGTAGTAGG(3)AT + TAGTAGG(3)ATAGCT + TAGG(
3)ATAGCTAGCT - TATG(4)T + TG(4)TAT + TATGG(4)T - TG(4)TGAT + TATATG(4)T + TGG(
4)TGAT - TG(4)TATAT + TATG(4)TAGT + TG(4)TAGTAGT + TAGG(5)ATAT - TATATAGG(
5) - TATAGG(5)AGT - TAGG(5)AGTAGT
</pre></div>

In order to give a precise answer to the first question we need to work a little on <code class="code">p.trace</code>. To do so, we introduce the following function, which creates the NP polynomial corresponding to the <code class="code">i</code>-th term in the expression <code class="code">p.trace</code> of <code class="code">p.pol</code> as a linear combination of members of <code class="code">KNP</code>. It is used to obtain the list <code class="code">EvalList</code> of polynomials for all <code class="code">i</code>.

<div class="example"><pre>
gap> EvalTracePol := function(i,p,KNP)
> local x,pi;
> pi := p.trace[i];
> x := BimulNP(pi[1],KNP[pi[2]],pi[3]);
> return [x[1],pi[4]*x[2]];
> end;;

gap> lev := Length(p.trace);;
gap> EvalList := List([1..lev], y -> CleanNP(EvalTracePol(y,p,KNP)));;
</pre></div>

In order to find the rewrite from the milk gene to the cola gene as required for an answer to the first question, we match leading terms recursively.

<div class="example"><pre>
gap> UnusedIndices := Set([1..lev]);;
gap> RunningTerm := milkNP[1][1];;
gap> stepno := 0;;
gap> NP2GP(milkNP,ALG);
(1)*(T*A*G*C)^3*T
gap> while Length(UnusedIndices) > 0 do
> i := 0;
> notfnd := true;
> while i < lev and notfnd do
> i := i+1;
> if EvalList[i][1][1] = RunningTerm and i in UnusedIndices then
> notfnd := false;
> RemoveSet(UnusedIndices, i);
> RunningTerm := EvalList[i][1][2];
> stepno := stepno+1;
> elif EvalList[i][1][2] = RunningTerm and i in UnusedIndices then
> notfnd := false;
> RemoveSet(UnusedIndices, i);
> RunningTerm := EvalList[i][1][1];
> stepno := stepno+1;
> fi;
> od;
> if i = lev and notfnd = true then Print("error not fnd in"); fi;
> Print(" -(",stepno,")- ");
> PrintNP([[p.trace[i][1]],[1]]);
> Print(" K[",p.trace[i][2],"]\n ");
> PrintNP([[p.trace[i][3]],[1]]);
> Print(" --> ");
> PrintNP([[EvalList[i][1][2]],[1]]);
> od;;
-(1)- TAGC
 K[1]
 AGCTAGCT
--> TAGCTAGCTAGCT
-(2)- TAG
 K[3]
 ATAGCTAGCT
--> TAGTCATAGCTAGCT
-(3)- TAG
 K[1]
 AGCTAGCT
--> TAGTAGCTAGCT
-(4)- TAGTAGC
 K[1]
 AGCT
--> TAGTAGCTAGCT
-(5)- TAGTAG
 K[3]
 ATAGCT
--> TAGTAGTCATAGCT
-(6)- TAGTAG
 K[1]
 AGCT
--> TAGTAGTAGCT
-(7)- TAGTAGTAGC
 K[1]
 1
--> TAGTAGTAGCT
-(8)- TAGTAGTAG
 K[3]
 AT
--> TAGTAGTAGTCAT
-(9)- TAGTAGTAG
 K[1]
 1
--> TAGTAGTAGT
-(10)- TAG
 K[1]
 AGTAGT
--> TAGTAGTAGT
-(11)- TAG
 K[3]
 ATAGTAGT
--> TAGTCATAGTAGT
-(12)- TAGC
 K[1]
 AGTAGT
--> TAGCTAGTAGT
-(13)- TAG
 K[5]
 AGTAGT
--> TAGCTAGTAGT
-(14)- T
 K[4]
 TAGTAGT
--> TATAGTAGT
-(15)- TATAG
 K[1]
 AGT
--> TATAGTAGT
-(16)- TATAG
 K[3]
 ATAGT
--> TATAGTCATAGT
-(17)- TATAGC
 K[1]
 AGT
--> TATAGCTAGT
-(18)- TATAG
 K[5]
 AGT
--> TATAGCTAGT
-(19)- TAT
 K[4]
 TAGT
--> TATATAGT
-(20)- TATATAG
 K[1]
 1
--> TATATAGT
-(21)- TATATAG
 K[3]
 AT
--> TATATAGTCAT
-(22)- TATATAGC
 K[1]
 1
--> TATATAGCT
-(23)- TATATAG
 K[5]
 1
--> TATATAGCT
-(24)- TATAT
 K[4]
 T
--> TATATAT
-(25)- T
 K[4]
 TATAT
--> TATATAT
-(26)- TAG
 K[5]
 ATAT
--> TAGCTATAT
-(27)- TAGC
 K[1]
 ATAT
--> TAGCTATAT
-(28)- TAG
 K[3]
 ATATAT
--> TAGTCATATAT
-(29)- TAG
 K[1]
 ATAT
--> TAGTATAT
-(30)- T
 K[4]
 TAT
--> TATAT
-(31)- TAT
 K[4]
 T
--> TATAT
-(32)- TAT
 K[2]
 TAT
--> TATAGTAT
-(33)- TATG
 K[4]
 T
--> TATGAT
-(34)- T
 K[4]
 TGAT
--> TATGAT
-(35)- T
 K[2]
 TATGAT
--> TAGTATGAT
-(36)- TG
 K[4]
 TGAT
--> TGATGAT
-(37)- TGATGA
 K[1]
 1
--> TGATGAT
-(38)- TGATGA
 K[3]
 AT
--> TGATGATCAT
-(39)- TGATGAC
 K[1]
 1
--> TGATGACT
-(40)- TGA
 K[1]
 GACT
--> TGATGACT
-(41)- TGA
 K[3]
 ATGACT
--> TGATCATGACT
-(42)- TGAC
 K[1]
 GACT
--> TGACTGACT
-(43)- 1
 K[1]
 GACTGACT
--> TGACTGACT
-(44)- 1
 K[3]
 ATGACTGACT
--> TCATGACTGACT
-(45)- C
 K[1]
 GACTGACT
--> CTGACTGACT
gap> NP2GP(colaNP,ALG);
(1)*(C*T*G*A)^2*C*T
</pre></div>

And now the second question regarding the retro virus.

<div class="example"><pre>
gap> retro := C*T*G*C*T*A*C*T*G*A*C*T;;
</pre></div>

We compute the Strong Normal Form <code class="func">StrongNormalFormNP</code> (<a href="chap3.html#X8563683E7FA604F8">3.5-6</a>) of <code class="code">retro</code> with respect to <code class="code">GB</code>. As it is <code class="code">TGT</code>, distinct to <code class="code">T</code>, the strong normal form of milk, there is no transformation from milk to retro.

<div class="example"><pre>
gap> NP2GP(StrongNormalFormNP(CleanNP(GP2NP(retro)),GB), ALG);
(1)*T*G*T
</pre></div>

Of course, here too we can verify the reduction, by computing <code class="func">StrongNormalFormTraceDiff</code> (<a href="chap3.html#X8219059A86A54130">3.7-6</a>) with input the NP polynomial corresponding to <code class="code">retro</code> and with respect to <code class="code">K</code>; it is called <code class="code">retroTrace</code>. The symbol <code class="code">G</code> in expression like <code class="code">G(2)</code> are not to be confused with the single symbols <code class="code">G</code> representing the DNA element.

<div class="example"><pre>
gap> retroTrace := StrongNormalFormTraceDiff(CleanNP(GP2NP(retro)),GTrace);;
gap> PrintTracePol(retroTrace);
TGG(1) - TGC^2G(1) - TGTAG(1) + TGTACG(1) + TGTAGG(1)AT + TGTATGAG(
1) + TGTAG(1)GACT - TGTAGCG(1)AT - TGTATGACG(1) + TGG(1)ACTGACT - TGTACG(
1)GACT + G(1)GCTACTGACT - TGCG(1)ACTGACT - CG(1)GCTACTGACT + TGTATG(
2)TAT + TGG(3)AT + TGCG(3)AT - TGTAG(3)AT + TGTAGG(3)ATAT + TGTATGAG(
3)AT + TGTAG(3)ATGACT + TGG(3)ATACTGACT + G(3)ATGCTACTGACT + TGTG(
4)T + TGTATG(4)T - TGTG(4)TAT - TGTATGG(4)T + TGCG(5) + TGG(5)AT - TGTAG(
5) + TGTAGG(5)AT
</pre></div>

<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap5.html">[Previous Chapter]</a> <a href="chapBib.html">[Next Chapter]</a> </div>

<div class="chlinkbot">Goto Chapter: <a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chapA.html">A</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>

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

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.142 Sekunden (vorverarbeitet am 2026-04-27) ¤

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 und die Messung sind noch experimentell.