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", false); true 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", false); true 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", false); true 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 frequencies 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", false); true 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", false); true 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", false); true 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", false); true 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", false); true 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);; 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.
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", false); true gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);
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}.
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", false); true gap> SetInfoLevel(InfoGBNP,2); gap> SetInfoLevel(InfoGBNPTime,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");
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", false); true 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", false); true 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.
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", false); true gap> SetInfoLevel(InfoGBNP,2); gap> SetInfoLevel(InfoGBNPTime,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");
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.
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", false); true gap> SetInfoLevel(InfoGBNP,2); gap> SetInfoLevel(InfoGBNPTime,1);
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.
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", false); true gap> SetInfoLevel(InfoGBNP,2); gap> SetInfoLevel(InfoGBNPTime,1);
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.
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", false); true gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);
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", false); true 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).
gap> LoadPackage("gbnp", false); true gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);
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,
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", false); true gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);
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}.
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", false); true gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);
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}.
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", false); true gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);
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", false); true 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", false); 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
gap> LoadPackage("gbnp", false); true gap> SetInfoLevel(InfoGBNP,1); gap> SetInfoLevel(InfoGBNPTime,1);
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", false); true 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", false); true 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 observe 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