In this chapter all available commented examples can be found. Those without comments are in the directory `gbnp/examples`

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

A.4 The truncated variant on two weighted homogeneous polynomials

A.12 Finiteness of the Weyl group of type E_6

This extends Example A.5.

A.15 A commutative quotient algebra of polynomial growth

This extends Example A.7.

A.18 The dihedral group of order 8 on another module

This extends Example A.17.

A.19 The dihedral group on a non-cyclic module

This example also extends Example A.17.

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 `InfoGBNP`

(4.2-1) to 2 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,2); gap> SetInfoLevel(InfoGBNPTime,1);

Then input the relations in NP format (see Section 2.1). They will be put in the list `Lnp`

.

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

The relations can be exhibited with `PrintNPList`

(3.2-3):

gap> PrintNPList(Lnp); a^2b - 1 ab - ba ab^2 - 1

Let the variables be printed as x and y instead of a and b by means of `GBNP.ConfigPrint`

(3.2-2)

gap> GBNP.ConfigPrint("x","y");

The Gröbner basis can now be calculated with `SGrobner`

(3.4-2):

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

When printed, it looks like:

gap> PrintNPList(GB); y - x x^3 - 1

The dimension of the quotient algebra can be calculated with `DimQA`

(3.5-2). The arguments are the Gröbner basis `GB`

and the number of variables is `2`

:

gap> DimQA(GB,2); 3

A basis of this quotient algebra can be calculated with `BaseQA`

(3.5-1). The arguments are a Gröbner basis `GB`

, the number of variables `t` (=2) and a variable `maxno` for returning partial quotient algebras (0 means full basis). The calculated basis will be printed as well.

gap> B:=BaseQA(GB,2,0);; gap> PrintNPList(B); 1 x x^2

The strong normal form of the element xyxyxyx can be found by use of `StrongNormalFormNP`

(3.5-6). The arguments are this element and the Gröbner basis `GB`

.

gap> f:=[[[1,2,1,2,1,2,1]],[1]];; gap> PrintNP(f); xyxyxyx gap> p:=StrongNormalFormNP(f,GB);; gap> PrintNP(p); x

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 `InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 2 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,2);

We truncate the example by putting all monomials of degree n in the ideal by means of the function `MkTrLst`

to be introduced below; a better way to compute the result is by means of the truncated GB algorithms (See A.24).

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

gap> n := 8;;

Now enter the relations in NP form (see 2.1). The function `MkTrLst`

will be introduced, which will return all monomials of degree `n`

. The list of ideal generators of interest is called `I`

.

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

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

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

We calculate the Gröbner basis with `SGrobner`

(3.4-2):

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.

Now print the first part of the Gröbner basis with `PrintNPList`

(3.2-3) (only the first 20 polynomials are printed here, the full Gröbner basis can be printed with `PrintNPList(GB)`

):

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

The truncated quotient algebra is obtained by factoring out the ideal generated by the Gröbner basis `GB`

and so its dimension can be calculated with `DimQA`

(3.5-2):

gap> DimQA(GB,2); #I The computation took 0 msecs. 157

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

Here we exhibit a truncated non-commutative homogeneous weighted Gröbner basis computation. This example uses the functions from Section 3.8, the truncation variants (see also Section 2.6).

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 `InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);

The variables will be printed as x and y.

gap> GBNP.ConfigPrint("x","y");

The level to truncate at is assigned to n.

gap> n := 16;;

Now enter the relations in NP form (see Section 2.1) and the weights.

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

The input can be printed with `PrintNPList`

(3.2-3)

gap> PrintNPList(K); x^3y^2 - x^6 + y^4 y^2x^3 + xyxyx + x^2yxy

Verify whether the list `K`

consists only of polynomials that are homogeneous with respect to `weights`

by means of `CheckHomogeneousNPs`

(3.8-3).

gap> CheckHomogeneousNPs(K,weights); #I Input is homogeneous [ 12, 12 ]

Now calculate the truncated Gröbner basis with `SGrobnerTrunc`

(3.8-2). The output will only contain homogeneous polynomials of degree at most `n`

.

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.

The Gröbner basis of the truncated quotient algebra can be printed with `PrintNPList`

(3.2-3):

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

The standard basis of the quotient of the free noncommutative algebra on n variables, where n is the length of the vector `weights`

, by the homogeneous ideal generated by `K`

up to degree n is obtained by means of the function `BaseQATrunc`

(3.8-4) applied to `K`

, `n`

, and `weights`

.

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

The same result can be obtained by using the truncated Gröbner basis found for `G`

instead of `K`

.

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

Also, the same result can be obtained by using the leading terms of the truncated Gröbner basis found for `G`

instead of `K`

.

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

A list of dimensions of the homogeneous parts of the quotient algebra up to degree n is obtained by means of `DimsQATrunc`

(3.8-5) with arguments `G`

, `n`

, and `weights`

.

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 ]

Even more detailed information is given by the list of frequences up to degree `n`

. This is obtained by means of `FreqsQATrunc`

(3.8-6) with arguments `G`

, `n`

, and `weights`

.

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

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 `InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 2 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,2);

Then input the relations in NP format (see 2.1). 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 `GBNP.ConfigPrint`

(3.2-2)

gap> GBNP.ConfigPrint(6,"r");

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 `KI`

.

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

The relations can be shown with `PrintNPList`

(3.2-3):

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

The Gröbner basis can now be calculated with `SGrobner`

(3.4-2):

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

The base of the quotient algebra can be calculated with `BaseQA`

(3.5-1), which has as arguments a Gröbner basis `GB`

, a number of symbols `6`

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.

gap> B:=BaseQA(GB,6,0);;

The dimension of the quotient algebra can be calculated with `DimQA`

(3.5-2), the arguments are the Gröbner basis `GB`

and the number of symbols `6`

. Since `InfoGBNPTime`

(4.3-1) is set to 2, we get timing information from `DimQA`

(3.5-2):

gap> DimQA(GB,6); #I The computation took 172 msecs. 51840

Note that the calculation of the dimension takes almost as long as calculating the base. Since we have already calculated a base `B`

it is much more efficient to calculate the dimension with `Length`

:

gap> Length(B); 51840

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 `InfoGBNP`

(4.2-1) to 2 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,2); gap> SetInfoLevel(InfoGBNPTime,1);

Let the single variable be printed as x by means of `GBNP.ConfigPrint`

(3.2-2)

gap> GBNP.ConfigPrint("x");

Now input the relations in NP format (see 2.1). They will be assigned to `KI`

.

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;

The relations can be shown with `PrintNPList`

(3.2-3):

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

The Gröbner basis can now be calculated with `SGrobner`

(3.4-2):

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.

Printed it looks like:

gap> PrintNPList(GB); x^2 + x + 1

This example is a standard commutative Gröbner basis computation from the book Some Tapas of Computer Algebra [CCS99], 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 `p1`

, ..., `p12`

. 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 `InfoGBNP`

(4.2-1) to 2 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,2); gap> SetInfoLevel(InfoGBNPTime,1);

Now define some functions which will help in the construction of relations. The function `powermon(g, exp)`

will return the monomial g^exp. The function `comm(a, b)`

will return a relation forcing commutativity between its two arguments `a`

and `b`

.

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

Now the relations are entered.

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;

The relations can be shown with `PrintNPList`

(3.2-3):

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

It is sometimes easier to enter the relations as elements of a free algebra and then use the function `GP2NP`

(3.1-1) or the function `GP2NPList`

(3.1-2) to convert them. This will be demonstrated below. More about converting can be read in Section 3.1.

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

These relations can be converted to NP form (see 2.1) with `GP2NPList`

(3.1-2). For use in a Gröbner basis computation we have to order the NP polynomials in `KI`

. This can be done with `CleanNP`

(3.3-7).

gap> KI_np:=GP2NPList(KI_gp);; gap> Apply(KI,x->CleanNP(x));; gap> KI_np=KI{[1..12]}; true

The Gröbner basis can now be calculated with `SGrobner`

(3.4-2) and printed with `PrintNPList`

(3.2-3).

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

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 [CGW05].

First load the package and set the standard infolevel `InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);

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 `GBNP.ConfigPrint`

(3.2-2)

gap> GBNP.ConfigPrint("g1","g2","g3","e1","e2","e3");

Now enter the relations. This will be done in NP form (see 2.1). 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.

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

Now print the relations with `PrintNPList`

(3.2-3):

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

Now calculate the Gröbner basis with `SGrobner`

(3.4-2):

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

Now calculate the dimension of the quotient algebra with `DimQA`

(3.5-2) (the second argument is the number of symbols):

gap> DimQA(GB,6); 105

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

The trace variant (see sections 2.5 and 3.7) 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 `InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);

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 `GBNP.ConfigPrint`

(3.2-2)

gap> GBNP.ConfigPrint("g1","g2","e1","e2");

Unlike Example A.8, we work with a field of rational functions.

gap> ll := Indeterminate(Rationals,"l"); l gap> mm := Indeterminate(Rationals,"m"); m gap> F := Field(ll,mm); <algebra-with-one over Field( [ 1 ] )> 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

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

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

The input can be displayed with `PrintNPList`

(3.2-3):

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

Now calculate the Gröbner basis with trace information, using the function `SGrobnerTrace`

(3.7-5):

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.

The full trace can be printed with `PrintTraceList`

(3.7-2), while printing only the relations (and no trace) can be invoked by `PrintNPListTrace`

(3.7-4). Since the total trace is very long we do not call `PrintTraceList(GB)`

here but only show two polynomial expressions from the Gröbner basis with `PrintTracePol`

(3.7-3):

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)

In order to test whether the expression for `GB[10]`

is as claimed we use `EvalTrace`

(3.7-1), For each traced polynomial `x`

in `GB`

, we equate the evaluated expression `x.trace`

, in which each occurrence of `G(i)`

is replaced by `KI[i]`

by use of `EvalTrace`

(3.7-1), with `x.pol`

.

gap> ForAll(GB,x->EvalTrace(x,KI)=x.pol); false

As a result the dimension of the quotient algebra can be calculated with `DimQA`

(3.5-2) and the quotient algebra itself with `BaseQA`

(3.5-1).

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

Here we present a commutative example from page 339 of "An introduction to commutative and non-commutative Gröbner Bases", by Teo Mora [Mor94]. 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.

`InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

The relations will be entered as GAP polynomials and converted to NP form (see 2.1) with `GP2NPList`

(3.1-2).

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

Some relations added to enforce commutativity.

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;

Now the relations are converted to NP form (see 2.1) with the function `GP2NPList`

(3.1-2).

gap> KI:=GP2NPList(rels);;

The Gröbner basis can be calculated with `SGrobner`

(3.4-2) and printed with `PrintNPList`

(3.2-3).

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

To determine whether the quotient algebra is finite dimensional we invoke `FinCheckQA`

(3.6-2), using as arguments the leading monomials of `GB`

and 7, the number of variables involved. The leading monomials of `GB`

are obtained by `LMonsNP`

(3.3-10).

gap> F := LMonsNP(GB);; gap> FinCheckQA(F,7); false

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 `DetermineGrowthQA`

(3.6-1), with the first two arguments as for `FinCheckQA`

above and third argument `false`

, indicating that an interval for the degree of the polynomial degree will suffice.

gap> DetermineGrowthQA(F,7,false); 5

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 `true`

.

gap> DetermineGrowthQA(F,7,true); 5

This example of a non-commutative Gröbner basis computation is from page 18 of "An introduction to commutative and non-commutative Gröbner Bases", by Teo Mora [Mor94]. 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}.

`InfoGBNP`

(4.2-1) to 2 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

Let the variables be printed as x and y instead of a and b by means of `GBNP.ConfigPrint`

(3.2-2)

gap> GBNP.ConfigPrint("x","y");

Next we input the relations in NP format (see Section 2.1). They will be assigned to `KI`

.

gap> xyx := [[[1,2,1],[2]],[1,-1]];; gap> yxy := [[[2,1,2],[2]],[1,-1]];; gap> KI:=[xyx,yxy];;

The relations can be shown with `PrintNPList`

(3.2-3):

gap> PrintNPList(KI); xyx - y yxy - y

The Gröbner basis with trace can now be calculated with `SGrobnerTrace`

(3.7-5):

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

The Gröbner basis can be printed with `PrintNPListTrace`

(3.7-4):

gap> PrintNPListTrace(GB); yx - xy y^2 - xy x^2y - y

The trace of the Gröbner basis can be printed with `PrintTraceList`

(3.7-2):

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)

This example extends A.5, 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 `FinCheckQA`

(3.6-2) is used for this computation. For the use of `PreprocessAnalysisQA`

(3.6-4) to speed up the check, see Example A.13.

First load the package and set the standard infolevel `InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 2 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,2);

Then input the relations in NP format (see Section 2.1). They will be assigned to `KI`

. These relations are the same as those in Example 3.

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

The Gröbner basis can now be calculated with `SGrobner`

(3.4-2):

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.

We will check whether the quotient algebra is finite dimensional or infinite dimensional. The function `FinCheckQA`

(3.6-2) 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 `LMonsNP`

(3.3-10).

gap> L:=LMonsNP(GB);; gap> FinCheckQA(L,6); true gap> time; 60

If a quotient algebra is finite dimensional, the dimension can be calculated with `DimQA`

(3.5-2), the arguments are the Gröbner basis `GB`

and the number of symbols `6`

. Since `InfoGBNPTime`

(4.3-1) is set to 2, we get timing information from `DimQA`

(3.5-2):

gap> dim := DimQA(GB,6); #I The computation took 144 msecs. 51840

This example extends Example A.5 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 `PreprocessAnalysisQA`

(3.6-4) and `FinCheckQA`

(3.6-2) 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 "The dimensionality of quotient algebras" [Kro03] 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.12 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 `InfoGBNP`

(4.2-1) to 0 and the time infolevel `InfoGBNPTime`

(4.3-1) to 2 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,0); gap> SetInfoLevel(InfoGBNPTime,2);

Then input the relations in NP format (see Section 2.1). They will be assigned to `KI`

.

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

The Gröbner basis can now be calculated with `SGrobner`

(3.4-2):

gap> GB := SGrobner(KI);; #I Time needed to clean G :0 #I The computation took 104 msecs.

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 `FinCheckQA`

(3.6-2), 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 `LMonsNP`

(3.3-10). 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.

gap> L:=LMonsNP(GB);; gap> L:=PreprocessAnalysisQA(L,6,4);; gap> time; 4 gap> fd:=FinCheckQA(L,6); true gap> time; 4

If a quotient algebra is finite dimensional, the dimension can be calculated with `DimQA`

(3.5-2), the arguments are the Gröbner basis `GB`

and the number of symbols `6`

. Since `InfoGBNPTime`

(4.3-1) is set to 2, we get timing information from `DimQA`

(3.5-2):

gap> dim := DimQA(GB,6); #I The computation took 176 msecs. 51840

This example demonstrates an instance in which the quotient algebra is infinite dimensional and has exponential growth. We start out with `KI`

:=[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 [Kro03]. The function `DetermineGrowthQA`

(3.6-1) is used for the computation.

`InfoGBNP`

(4.2-1) to 2 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

Let the variables be printed as x and y instead of a and b by means of `GBNP.ConfigPrint`

(3.2-2)

gap> GBNP.ConfigPrint("x","y");

Then input the relations in NP format (see Section 2.1). They will be assigned to `KI`

.

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

We calculate the Gröbner basis with the function `SGrobner`

(3.4-2) and print it with `PrintNPList`

(3.2-3).

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

Next we check the dimensionality of the quotient algebra with the function `FinCheckQA`

(3.6-2) or the function `DetermineGrowthQA`

(3.6-1). These functions expect as first argument a list `F` of leading terms of a Gröbner basis, which can be calculated with the function `LMonsNP`

(3.3-10) and as second argument the number of symbols (here equal to 2). The function `DetermineGrowthQA`

(3.6-1) will not only report whether a Gröbner basis is finite, but will also provide information about its growth.

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"

Although the quotient algebra is infinite dimensional, multiplication of two elements can be carried out by `MulQA`

(3.5-5). We print three positive powers of x+y.

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

This example extends A.7, a commutative example from Some Tapas of Computer Algebra [CCS99], 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 `DetermineGrowthQA`

(3.6-1) is used for this computation. Then part of its Hilbert series is computed. The function `HilbertSeriesQA`

(3.6-3) is used for the computations.

`InfoGBNP`

(4.2-1) to 2 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

Now define some functions which will help in the construction of relations. The function `powermon(i, exp)`

will return the monomial i^exp. The function `comm(aa, bb)`

will return a relation forcing commutativity between its two arguments `aa`

and `bb`

.

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

Now the relations are entered:

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;

The relations can be shown with `PrintNPList`

(3.2-3):

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

It is usually easier to use the function `GP2NP`

(3.1-1) or the function `GP2NPList`

(3.1-2) to enter relations. Entering the first twelve relations and then converting them with `GP2NPList`

(3.1-2) is demonstrated in example 6 (A.7). More about converting can be read in Section 3.1.

The Gröbner basis can now be calculated with `SGrobner`

(3.4-2) and printed with `PrintNPList`

(3.2-3).

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

The growth of the quotient algebra can be studied with `DetermineGrowthQA`

(3.6-1). The first argument is the list of leading monomials, which can be calculated with `LMonsNP`

(3.3-10). The second argument is the size of the alphabet.

gap> L:=LMonsNP(GB);; gap> DetermineGrowthQA(L,6,false); 4 gap> time; 0

Now compute the first 10 terms of the Hilbert Series with `HilbertSeriesQA`

(3.6-3) (note that trailing zeroes are removed):

gap> HilbertSeriesQA(L,6,10); [ 1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286 ]

A small example over a field other than the rationals, using the conversion functions from 3.1. The input relations define the symmetric group of degree 3, denoted S_3.

`InfoGBNP`

(4.2-1) to 2 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

Let `F`

be the field GF(2). The relations can be entered as elements of a free associative algebra with one `A`

(see Reference: FreeAssociativeAlgebraWithOne (for ring, rank (and name))).

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 ]

Enter the relations {a^2-1,b^2-1,(ab)^3-1}, convert them to NP-form, see Section 2.1, with `GP2NPList`

(3.1-2) and print them with `PrintNPList`

(3.2-3):

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

Now calculate the Gröbner basis with `SGrobner`

(3.4-2) and print it with `PrintNPList`

(3.2-3):

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

Now calculate the dimension of the quotient algebra with `DimQA`

(3.5-2) (2 symbols) and a base with `BaseQA`

(3.5-1) (2 symbols, 0 for whole base) and print the base. This will give a list of elements of the group.

gap> DimQA(GB,2); 6 gap> B:=BaseQA(GB,2,0);; gap> PrintNPList(B); Z(2)^0 a b ab ba aba

We can print the Gröbner basis and the basis of the quotient algebra, converted back to GAP polynomials with `NP2GPList`

(3.1-4). The functions used to convert the polynomials also require the algebra as an argument. The result is useful for further computations in A.

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 ]

The matrix of right multiplication with the image of the first variable can be computed by `MatrixQA`

(3.5-3).

gap> Display(MatrixQA(1,B,GB)); . 1 . . . . 1 . . . . . . . . . 1 . . . . . . 1 . . 1 . . . . . . 1 . .

In this example (Example 1 from Linton [Lin93]) 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 `k`

. In this example `k`

will be the field of rational numbers.

`InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

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 Reference: FreeAssociativeAlgebraWithOne (for ring, rank (and name))). For convenience we use the variables `a`

and `b`

for the generators of the algebra and `e`

for the one of the algebra.

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

Now the relations are entered:

gap> twosidrels:=[a^4-e,b^2-e,(a*b)^2-e];; gap> prefixrels:=[b-e];;

First the relations are converted into NP format, see Section 2.1, after which the function `SGrobnerModule`

(3.9-1) is called to calculate a Gröbner basis record.

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.

The record GBR has two members: the two-sided relations `GBR.ts`

and the prefix relations `GBR.p`

. It is possible to print these using the function `PrintNPList`

(3.2-3):

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 ]

It is now possible to calculate the standard basis of the quotient module with the function `BaseQM`

(3.9-2). This function has as arguments the Gröbner basis record `GBR`

, the number of generators of the algebra (2), the number of generators of the module (1), and a variable `maxno`

for returning partial bases (0 means full basis).

gap> B:=BaseQM(GBR,2,1,0);; gap> PrintNPList(B); [ 1 ] [ a ] [ a^2 ] [ ab ]

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

gap> D:=A^1;; gap> gd:=GeneratorsOfLeftModule(D);; gap> prefixrelsdom:=[gd[1]*(b-e)];;

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

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 ]

To compute the image of right multiplication of the basis element `B[Length(B)]`

of the module with the quotient algebra element corresponding to ab we use the function `MulQM`

(3.9-4) with arguments `B[Length(B)]`

, `GB2NP(a*b)`

, and `GBR`

We subsequently use `PrintNP`

(3.2-1) to display the result as a 1-dimensional vector with an entry from A.

gap> v := MulQM(B[Length(B)],GP2NP(a*b),GBR); [ [ [ -1 ] ], [ 1 ] ] gap> PrintNP(v); [ 1 ]

In this example (Example 2 from Linton [Lin93]) 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.17: 1 + a(1+a+b).

First load the package and set the standard infolevel `InfoGBNP`

(4.2-1) to 0 and the time infolevel `InfoGBNPTime`

(4.3-1) to 0 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,0); gap> SetInfoLevel(InfoGBNPTime,0);

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.17. 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 Reference: FreeAssociativeAlgebraWithOne (for ring, rank (and name))). For convenience we use the variables `a`

and `b`

for the generators of the algebra and `e`

for the one of the algebra.

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

Now the relations are entered:

gap> twosidrels:=[a^4-e,b^2-e,(a*b)^2-e];; gap> prefrels:=[ b-e, e + a * (e + a + b) ];;

First the relations are converted into NP format (see 2.1) after which the function `SGrobnerModule`

(3.9-1) is called to calculate a Gröbner basis record.

gap> GBR:=SGrobnerModule(GP2NPList(prefrels),GP2NPList(twosidrels));;

The record GBR has two members: the two-sided relations `GBR.ts`

and the prefix relations `GBR.p`

. It is possible to print these using the function `PrintNPList`

(3.2-3):

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 ]

It is now possible to calculate the standard basis of the quotient module with the function `BaseQM`

(3.9-2). This function has as arguments the Gröbner basis record `GBR`

, 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 `maxno`

for returning partial bases (0 means full basis).

gap> B:=BaseQM(GBR,2,1,0);; gap> PrintNPList(B); [ 1 ] [ a ] [ a^2 ]

In this example (Example 3 from Linton [Lin93]), 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.17 and fusing their one-dimensional submodules.

Load the package and set the standard infolevel `InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

Create the free associative algebra to enter the relations in:

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

Now the relations are entered:

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

First the relations are converted into NP format (see 2.1) with the function `GP2NPList`

(3.1-2). They are printed in raw form and subsequently in a more legible format.

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 ]

Next the function `SGrobnerModule`

(3.9-1) is called to calculate a Gröbner basis record (see 2.8).

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.

The record `GBR`

has two members: the two-sided relations `GBR.ts`

and the prefix relations `GBR.p`

. It is possible to print these using the function `PrintNPList`

(3.2-3):

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]

It is now possible to calculate the standard basis of the quotient module with the function `BaseQM`

(3.9-2). This function has as arguments the Gröbner basis record `GBR`

, 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 `maxno`

for returning partial bases (0 means full basis).

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]

It is also possible to convert each member of the list `B`

of polynomials in NP form to GAP polynomials to do further calculations within the algebra or module. This can be done with the function `NP2GPList`

(3.1-4).

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

Individual GAP polynomials can be obtained from polynomials in NP form with the function `NP2GP`

(3.1-3). This also holds for elements of the free module `D`

in NP form.

gap> Display(NP2GP(B[Length(B)],D)); [ (1)*a^2, <zero> of ... ]

Next we write down the matrices for the right action of the generators on the module by means of `MatrixQA`

(3.5-3).

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

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 `StrongNormalFormNPM`

(3.9-5). Its first argument will be the vector and its second the Gröbner basis. The transformation `GP2NP`

(3.1-1) to the NP format needs to be applied to the vector before it can be used as an argument.

gap> v:=StrongNormalFormNPM(GP2NP((y[1]*2+y[2]*3)*a*a*b), GBR);; gap> PrintNP(v); [ 2a^2 , 3a^2 ]

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,

`InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

Create the field containing the golden ratio `tau`

.

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

Create the free algebra with three generators over this field:

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

The ideal for a quotient of the icosahedral group algebra over this field, in which `b`

*`c`

has a quadratic minimal polynomial involving `tau`

:

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 ]

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.

gap> Mrels:=[b*c-e,b-e,(a*b*c)^5+e];;

First the relations are converted into NP format (see 2.1) with the function `GP2NPList`

(3.1-2). Next the function `SGrobnerModule`

(3.9-1) is called to calculate a Gröbner basis record (see 2.8).

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 ]

It is now possible to calculate the basis of the quotient algebra with the function `BaseQM`

(3.9-2). This function has as arguments the Gröbner basis record `GBR`

, 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 `maxno`

for returning partial quotient algebras (0 means full basis).

gap> B:=BaseQM(GBR,3,1,0);; gap> PrintNPList(B); [ !1 ] [ a ] [ ab ]

Calculate the dimension of the quotient algebra with the function `DimQM`

(3.9-3). This function has as arguments the Gröbner basis record `GBR`

, the number of generators of the algebra (in this case 3) and the number of generators of the module (in this case 1).

gap> DimQM(GBR,3,1); 3

Next we write down the matrices for the right action of the generators on the module by means of `MatrixQA`

(3.5-3).

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

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 `IsOne`

(Reference: IsOne).

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

The algebra we will consider is from Example 4 from Linton [Lin93]. 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}.

`InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

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.17) 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 Reference: FreeAssociativeAlgebraWithOne (for ring, rank (and name))). For convenience we use the variables `s1`

, `s2`

, `s3`

, and `e`

for the generators of the algebra, and `o`

for the identity element of the algebra.

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

It is possible to print symbols like they are printed in the algebra `A`

with the function `GBNP.ConfigPrint`

(3.2-2):

gap> GBNP.ConfigPrint(A);

Now the relations are entered:

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 ]

First the relations are converted into NP format (see 2.1) and next the function `SGrobnerModule`

(3.9-1) is called to calculate a Gröbner basis record.

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.

The record GBR has two members: the two-sided relations `GBR.ts`

and the prefix relations `GBR.p`

. We print these using the function `PrintNPList`

(3.2-3):

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 ]

It is now possible to calculate the standard basis of the quotient module with the function `BaseQM`

(3.9-2). This function has as arguments the Gröbner basis record `GBR`

, 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 `maxno`

for returning partial bases (0 means full basis).

gap> B:=BaseQM(GBR,4,1,0);; gap> PrintNPList(B); [ 1 ] [ s3 ] [ s3s2 ] [ s3s2s1 ]

Next we write down the matrices for the right action of the generators on the module. First by means of the list command `MatricesQA`

(3.5-4), next one by one by means of `MatrixQA`

(3.5-3) within a loop.

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

This example is an extension of Example 5 from Linton, [Lin93]. 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}.

`InfoGBNP`

(4.2-1) to 1 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about the info level, see Chapter 4).

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.17. 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 Reference: FreeAssociativeAlgebraWithOne (for ring, rank (and name))). For convenience we use the variables `a`

and `b`

for the generators of the algebra and `e`

for the one of the algebra.

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

In order to print the variables like they are printed in the algebra `A`

with the function `GBNP.ConfigPrint`

(3.2-2):

gap> GBNP.ConfigPrint(A);

Now the relations are entered:

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 ]

First the relations are converted into NP format (see 2.1) after which the function `SGrobnerModule`

(3.9-1) is called to calculate a Gröbner basis record.

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.

The record GBR has three members: the two-sided relations `GBR.ts`

, the prefix relations `GBR.p`

, and the number `GBR.pg`

of generators of the free module. It is possible to print the first two using the function `PrintNPList`

(3.2-3):

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 ]

It is now possible to calculate the standard basis of the quotient module with the function `BaseQM`

(3.9-2). This function has as arguments the Gröbner basis record `GBR`

, 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 `maxno`

for returning partial bases (0 means full basis).

gap> B:=BaseQM(GBR,3,1,0);; gap> PrintNPList(B); [ Z(3)^0 ] [ z ] [ zy ] [ zyx ]

Next we write down the matrices for the right action of the generators on the module, by means of the command `MatricesQA`

(3.5-4).

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

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 [Gra95].

First load the package and set the standard infolevel `InfoGBNP`

(4.2-1) to 0 and the time infolevel `InfoGBNPTime`

(4.3-1) to 1 (for more information about timing; see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,0); gap> SetInfoLevel(InfoGBNPTime,1);

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, `numpoints`

.

gap> numpoints:=8; 8

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

`edges:=[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10]];`

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

`edges:=[[1,3],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10]];`

can

be used.

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

Now enter the relations as GAP polynomials. First a free associative algebra with identity element is created over the Rationals (see also Reference: FreeAssociativeAlgebraWithOne (for ring, rank (and name))). For convenience the generators are stored in `gens`

.

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 ]

It is possible to print symbols like they are printed in the algebra `A`

with the function `GBNP.ConfigPrint`

(3.2-2):

gap> GBNP.ConfigPrint(A);

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

gap> edges:=Set(edges, x->SortedList(x)); [ [ 1, 3 ], [ 2, 4 ], [ 3, 4 ], [ 4, 5 ], [ 5, 6 ], [ 6, 7 ], [ 7, 8 ] ]

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.

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;

Then the relations are converted into NP format (see 2.1) after which the function `SGrobner`

(3.4-2) is called to calculate a Gröbner basis.

gap> relsNP:=GP2NPList(rels);; gap> GB:=SGrobner(relsNP);; #I The computation took 184 msecs.

It is now possible to calculate the dimension of the quotient algebra with the function `DimQA`

(3.5-2). This function has as arguments the Gröbner basis `GB`

and the number of generators of the algebra (here this is `numpoints`

). To get the full basis the function `BaseQA`

(3.5-1) can be used.

gap> DimQA(GB,numpoints); 10846

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 [Kno04].

First load the package and set the standard infolevel `InfoGBNP`

(4.2-1) to 0 and the time infolevel `InfoGBNPTime`

(4.3-1) to 0 (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP"); ───────────────────────────────────────────────────────────────────────────── Loading GBNP 1.0.3 (Non-commutative Gröbner bases) by A.M. Cohen (http://www.win.tue.nl/~amc) and J.W. Knopper (J.W.Knopper@tue.nl). Homepage: http://mathdox.org/products/gbnp/ ───────────────────────────────────────────────────────────────────────────── true gap> SetInfoLevel(InfoGBNP,0); gap> SetInfoLevel(InfoGBNPTime,0);

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

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 ]

The relations can be converted to NP format (see 2.1) with the function `GP2NPList`

(3.1-2) and can be subsequently displayed with `PrintNPList`

(3.2-3).

gap> uerelsNP:=GP2NPList(uerels);; gap> PrintNPList(uerelsNP); ba - ab + c ca - ac - 2a cb - bc + 2b

Now configure printing in such a way that this algebra is used with the function `GBNP.ConfigPrint`

(3.2-2).

gap> GBNP.ConfigPrint(A);

The set is actually a Gröbner basis, as can be verified by calculating the Gröbner basis with `SGrobner`

(3.4-2).

gap> GB:=SGrobner(uerelsNP);; gap> PrintNPList(GB); fe - ef + h he - eh - 2e hf - fh + 2f

Determine whether the quotient algebra is finite dimensional by means of `FinCheckQA`

(3.6-2), with arguments the leading monomials of `GB`

and 3, the number of variables involved. The leading monomials of `GB`

are found by invoking `LMonsNP`

(3.3-10).

gap> F:=LMonsNP(GB); [ [ 2, 1 ], [ 3, 1 ], [ 3, 2 ] ] gap> FinCheckQA(F,3); false

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

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

With the function `SGrobnerTrace`

(3.7-5) it is possible to calculate a Gröbner basis with trace information.

gap> GB:=SGrobnerTrace(extendedrelsNP);;

The Gröbner basis can now be displayed with `PrintNPListTrace`

(3.7-4).

gap> PrintNPListTrace(GB); e^2 eh + e fe - ef + h f^2 fh - f he - e hf + f h^2 - 2ef + h

Note the fourth relation: f^2=0. To view a trace one can use the function `PrintTracePol`

(3.7-3).

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)

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 `StrongNormalFormTraceDiff`

(3.7-6) can be used to trace the difference between an element and its strong normal form in the terms of `extendedrels`

. Apparently, in the first example the strong normal form of `r`

is `r - s.pol=0`

.

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

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

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

In Serre's book [Ser03] 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.

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

We use `SGrobnerTrace`

(3.7-5), the trace variant of the Gröbner basis computation,

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.

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.

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

Since the output is large and might spoil the exercise, we confine ourselves to the printing first polynomial `GB[1]`

and the length of its trace. As the trace polynomial expresses `GB[1]`

, which is equal to a-1, as a combination of the binomials in `KI`

, 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 `GB[1]`

.

gap> PrintNP(GB[1].pol); a - 1 gap> Length(GB[1].trace); 1119

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,0); gap> SetInfoLevel(InfoGBNPTime,0);

The paper [BD04] 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.

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

We carry out a traced Gröbner basis computation by use of `SGrobnerTrace`

(3.7-5), and form the usual Gröbner basis by extracting the polynomials from the traced polynomials using the field indicator `.pol`

.

gap> GBT := SGrobnerTrace(KI);; gap> GB := List([1..Length(GBT)], i -> GBT[i].pol);;

The dimension of the quotient algebra is computable with `DimQA`

(3.5-2).

gap> DimQA(GB,3); 37

In order to express the last GB element, viz.

gap> PrintNP(GB[Length(GB)]); cabcabca + cbacba - ca

as a combination of elements of `KI`

, we use `PrintTracePol`

(3.7-3):

gap> PrintTracePol(GBT[Length(GBT)]); - G(9)bacba + cG(10)

We compute matrices for left multiplication by generators using `MatricesQA`

(3.5-4) and determine the minimal polynomial of the sum of the three matrices.

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 ]

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 [BD04].

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 3.7.

First load the package and set the standard infolevel `InfoGBNP`

(4.2-1) to 0 and the time infolevel `InfoGBNPTime`

(4.3-1) to 0 to minimize the printing of data regarding the computation (for more information about the info level, see Chapter 4).

gap> LoadPackage("GBNP","0",false);; gap> SetInfoLevel(InfoGBNP,0); gap> SetInfoLevel(InfoGBNPTime,0);

We introduce the free algebra `ALG`

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.

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

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 `ALG`

and let `KNP`

be the corresponding set of NP polynomials.

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

We stipulate how the variables will be printed and print `KNP`

. See `PrintNPList`

(3.2-3).

gap> GBNP.ConfigPrint("A","C","G","T"); gap> PrintNPList(KNP); TCAT - T GAG - AG CTC - TC AGTA - A TAT - CT

Now calculate the usual Gröbner basis with `SGrobner`

(3.4-2).

gap> GB := SGrobner(KNP);;

Compare milk and cola after taking their strong normal forms with respect to `GB`

using `StrongNormalFormNP`

(3.5-6). We oberve that they have the same normal form and so there is a way to transform the milk gene into the cola gene.

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

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 `SGrobnerTrace`

(3.7-5).

gap> GTrace := SGrobnerTrace(KNP);;

The full trace can be printed with `PrintTraceList`

(3.7-2), but we only print the relations (and no trace) by invoking `PrintNPListTrace`

(3.7-4).

gap> PrintNPListTrace(GTrace); CT - T GA - A AGT - AT ATA - A TAT - T TCA - TA

In order to display a proof that milk-cola belongs to the ideal we use `StrongNormalFormTraceDiff`

(3.7-6), The result is a record, `p`

say, containing `milk-cola`

in the field `p.pol`

(the normal form will be subtracted from the argument `milk-cola`

to obtain `p.pol`

, but the normal form is zero because the argument belongs to the ideal generated by `K`

). The other field of the record `p`

is `p.trace`

, the traced polynomial, which is best displayed by use of `PrintTracePol`

(3.7-3).

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

In order to give a precise answer to the first question we need to work a little on `p.trace`

. To do so, we introduce the following function, which creates the NP polynomial corresponding to the `i`

-th term in the expression `p.trace`

of `p.pol`

as a linear combination of members of `KNP`

. It is used to obtain the list `EvalList`

of polynomials for all `i`

.

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

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.

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

And now the second question regarding the retro virus.

gap> retro := C*T*G*C*T*A*C*T*G*A*C*T;;

We compute the Strong Normal Form `StrongNormalFormNP`

(3.5-6) of `retro`

with respect to `GB`

. As it is `TGT`

, distinct to `T`

, the strong normal form of milk, there is no transformation from milk to retro.

gap> NP2GP(StrongNormalFormNP(CleanNP(GP2NP(retro)),GB), ALG); (1)*T*G*T

Of course, here too we can verify the reduction, by computing `StrongNormalFormTraceDiff`

(3.7-6) with input the NP polynomial corresponding to `retro`

and with respect to `K`

; it is called `retroTrace`

. The symbol `G`

in expression like `G(2)`

are not to be confused with the single symbols `G`

representing the DNA element.

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

generated by GAPDoc2HTML