‣ GP2NP( gp ) | ( function ) |
Returns: If gp is an element of a free algebra, then the polynomial in NP format (see Section 2.1) corresponding to gp; if gp is an element of a free module, then the vector in NPM format (see Section 2.2) corresponding to gp.
This function will convert an element of a free algebra to a polynomial in NP format and an element of a free right module to a vector in NPM format.
Example: Let A be the free associative algebra with one over the rationals on the generators a and b. Let e be the one of the algebra.
gap> A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");; gap> a:=A.a;; gap> b:=A.b;; gap> e:=One(A);; gap> z:=Zero(A);;
Now let gp be the polynomial \(ba-ab-e\).
gap> gp:=b*a-a*b-e; (-1)*<identity ...>+(-1)*a*b+(1)*b*a
The polynomial in NP format, corresponding to gp can now be obtained with GP2NP:
gap> GP2NP(gp); [ [ [ 2, 1 ], [ 1, 2 ], [ ] ], [ 1, -1, -1 ] ]
Let D be the free associative algebra over A of rank 2.
gap> D := A^2;;
Take the following list R of two elements of D.
gap> R := [ [b-e, z], [e+a*(e+a+b), -e-a*(e+a+b)] ];;
Convert the list R to a list of vectors in NPM format.
gap> List(R,GP2NP); [ [ [ [ -1, 2 ], [ -1 ] ], [ 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 ] ] ]
‣ GP2NPList( Lgp ) | ( function ) |
Returns: The list of polynomials in NP or NPM format corresponding to elements of a free algebra or module occurring in the list Lgp.
This function has the same effect as List(Lgp,GBNP).
Example: Let A be the free associative algebra with one over the rationals on the generators a and b. Let e be the one of the algebra.
gap> A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");; gap> a:=A.a;; gap> b:=A.b;; gap> e:=One(A);;
Let Lgp be the list of polynomials \([a^2-e,b^2-e,ba-ab-e]\).
gap> Lgp:=[a^2-e,b^2-e,b*a-a*b-e]; [ (-1)*<identity ...>+(1)*a^2, (-1)*<identity ...>+(1)*b^2, (-1)*<identity ...>+(-1)*a*b+(1)*b*a ]
The polynomial in NP format corresponding to gp can be obtained with GP2NP:
gap> GP2NPList(Lgp); [ [ [ [ 1, 1 ], [ ] ], [ 1, -1 ] ], [ [ [ 2, 2 ], [ ] ], [ 1, -1 ] ], [ [ [ 2, 1 ], [ 1, 2 ], [ ] ], [ 1, -1, -1 ] ] ]
The same result is obtained by a simple application of the standard List function in GAP:
gap> List(Lgp,GP2NP) = GP2NPList(Lgp); true
‣ NP2GP( np, A ) | ( function ) |
Returns: The GAP format of the polynomial np in NP format.
This function will convert a polynomial in NP format to a GAP polynomial in the free associative algebra A and a vector in NPM format to a GAP vector in the free module A. In case of the NP format, the number of variables should not exceed the rank of the free algebra A. In case of the NPM format, the absolute of the negative numbers should not exceed the rank of the free module A.
Example: Let A be the free associative algebra with one over the rationals on the generators a and b.
gap> A:=FreeAssociativeAlgebraWithOne(GF(3),"a","b");;
Let np be a polynomial in NP format.
gap> np:=[ [ [ 2, 1 ], [ 1, 2 ], [ ] ], [ Z(3)^0, Z(3), Z(3) ] ];;
The polynomial can be converted to the corresponding element of A with NP2GP:
gap> NP2GP(np,A); (Z(3)^0)*b*a+(Z(3))*a*b+(Z(3))*<identity ...>
Note that some information of the coefficient field of a polynomial np in NP format can be obtained from the second list of np.
gap> One(np[2][1]); Z(3)^0
Now let M be the module A^2 and let npm be a polynomial over that module in NPM form.
gap> M:=A^2;; gap> npm:=[ [ [ -1, 1 ], [ -2, 2 ] ], [ Z(3)^0, Z(3)^0 ] ];;
The element of M corresponding to npm is
gap> NP2GP(npm,M); [ (Z(3)^0)*a, (Z(3)^0)*b ]
If M is a module of dimension 2 over A and Lnp a list of polynomials in NPM format, then the polynomials can be converted to the corresponding polynomials of M as follows:
gap> M:=A^2;; gap> Lnp:=[ [ [ [ -2, 1, 1 ], [ -2, 1 ] ], [ 1, -1 ] ], > [ [ [ -1, 2, 2], [-2, 1 ] ], [ 1, -1 ]*Z(3)^0 ] ];; gap> List(Lnp, m -> NP2GP(m,M)); [ [ <zero> of ..., (Z(3))*a+(Z(3)^0)*a^2 ], [ (Z(3)^0)*b^2, (Z(3))*a ] ]
‣ NP2GPList( Lnp, A ) | ( function ) |
Returns: The list of polynomials corresponding to Lnp in GAP format.
This function will convert the list Lnp of polynomials in NP format to a list of GAP polynomials in the free associative algebra A.
Example: Let A be the free associative algebra with one over the rationals on the generators a and b.
gap> A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");;
Let Lnp be a list of polynomials in NP format. Then Lnp can be converted to a list of polynomials of A with NP2GPList:
gap> Lnp:=[ [ [ [ 1, 1, 1 ], [ 1 ] ], [ 1, -1 ] ], > [ [ [ 2, 2 ], [ ] ], [ 1, -1 ] ] ];; gap> NP2GPList(Lnp,A); [ (1)*a^3+(-1)*a, (1)*b^2+(-1)*<identity ...> ]
It has the same effect as the function List applied as follows.
gap> List(Lnp, p -> NP2GP(p,A)); [ (1)*a^3+(-1)*a, (1)*b^2+(-1)*<identity ...> ]
Now let M be a module of dimension 2 over A and Lnp a list of vectors in NPM format. Then polynomials Lnp can be converted to the corresponding vectors of M with NP2GPList:
gap> M:=A^2;; gap> Lnp:=[ [ [ [ -2, 1, 1 ], [ -2, 1 ] ], [ 1, -1 ] ], > [ [ [ -1, 1 ], [ -2 ] ], [ 1, -1 ] ] ];; gap> NP2GPList(Lnp,M); [ [ <zero> of ..., (-1)*a+(1)*a^2 ], [ (1)*a, (-1)*<identity ...> ] ]
The same result can be obtained by application of the standard List function:
gap> List(Lnp, m -> NP2GP(m,M)) = NP2GPList(Lnp,M) ; true
‣ PrintNP( np ) | ( function ) |
This function prints a polynomial np in NP format, using the letters a, b, c, \(\ldots\) for \(x_1\), \(x_2\), \(x_3\), \(\ldots\), except that everything beyond \(l\) (the 12-th letter) is printed as \(x\).
This function prints a polynomial np in NP format as configured by the function GBNP.ConfigPrint (3.2-2).
Example: Consider the following polynomial in NP format.
gap> p := [[[1,1,2],[1,2,2],[]],[1,-2,3]];;
It can be printed in the guise of a polynomial in a and b by the function PrintNP:
gap> PrintNP(p); a^2b - 2ab^2 + 3
‣ GBNP.ConfigPrint( arg ) | ( function ) |
By default the generators of the algebra are printed as a, ..., l and everything after the twelfth generator as x. By calling ConfigPrint it is possible to alter this printing convention. The argument(s) will be an algebra or arguments used for naming algebras in GAP upon creation. More specifically, we have the following choices.
When the function is invoked without arguments the printing is reset to the default (see above).
When the function is invoked with an algebra as argument, generators will be printed as they would be in the algebra.
When the function is invoked with an algebra and an integer n as arguments, generators will be printed as they would be in the algebra and separated over the n dimensions.
When the function is invoked with an leftmodule \(A^n\) of an associative algebra as argument, generators will be printed as they would be in the algebra, separated over the n dimensions.
When the function is invoked with a string as its argument, it is assumed that there is only 1 generator and that this should be named as indicated by the string.
When the function is invoked with an integer as its argument, the n-th generator will be printed as x.<n>.
When the function is invoked with a non-negative integer and a string as its arguments, generators will be printed as <s>.<n>, where <s> is the string given as argument and <n> the number of the generator. There is no checking whether the number given as argument is really the dimension. So it is possible that higher numbers return in the output. This way of input is useful however, because it is a distinction from the one-dimensional case and compatible with the way a free algebra is created.
When the function is invoked with a sequence of strings, then generators will be printed with the corresponding string or x if the sequence is not long enough.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];;
They can be printed by the function PrintNP.
gap> PrintNP(p1); a^2b - 1 gap> PrintNP(p2); ab^2 - 1
We can let the variables be printed as x and y instead of a and b by means of GBNP.ConfigPrint.
gap> GBNP.ConfigPrint("x","y"); gap> PrintNP(p1); x^2y - 1 gap> PrintNP(p2); xy^2 - 1
We can also let the variables be printed as x.1 and x.2 instead of a and b by means of GBNP.ConfigPrint.
gap> GBNP.ConfigPrint(2,"x"); gap> PrintNP(p1); x.1^2x.2 - 1 gap> PrintNP(p2); x.1x.2^2 - 1
We can even assign strings to the variables to be printed like alice and bob instead of a and b by means of GBNP.ConfigPrint.
gap> GBNP.ConfigPrint("alice","bob"); gap> PrintNP(p1); alice^2bob - 1 gap> PrintNP(p2); alicebob^2 - 1
Alternatively, we can introduce the free algebra A with two generators, and print the polynomials as members of A:
gap> A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");; gap> GBNP.ConfigPrint(A); gap> PrintNP(p1); a^2b - 1 gap> PrintNP(p2); ab^2 - 1
‣ PrintNPList( Lnp ) | ( function ) |
This function prints a list Lnp of polynomials in NP format, using the function PrintNP.
Example: We put two polynomials in NP format into the list Lnp.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> Lnp := [p1,p2];;
We can print the list with PrintNPList.
gap> PrintNPList(Lnp); a^2b - 1 ab^2 - 1
Alternatively, using the function GBNP.ConfigPrint (3.2-2), we can introduce the free algebra A with two generators, and print the polynomials of the list as members of A:
gap> A:=FreeAssociativeAlgebraWithOne(Rationals,"a","b");; gap> GBNP.ConfigPrint(A); gap> PrintNPList(Lnp); a^2b - 1 ab^2 - 1
‣ NumAlgGensNP( np ) | ( function ) |
Returns: The minimum number t so that np belongs to the free algebra on t generators.
When called with an NP polynomial np, this function returns the minimum number of generators needed for the corresponding algebra to contain the np. If np is a polynomial without generators, that is, equivalent to \(0\) or \(1\), then 0 is returned.
Example: Consider the following polynomial in NP format.
gap> np := [[[2,2,2,1,1,1],[4],[3,2,3]],[1,-3,2]];; gap> PrintNP(np); b^3a^3 - 3d + 2cbc gap> NumAlgGensNP(np); 4
‣ NumAlgGensNPList( Lnp ) | ( function ) |
Returns: The minimum number t so that each polynomial in Lnp belongs to the free algebra on t generators.
When called with a list of NP polynomials Lnp, this function returns the minimum number of generators needed for the corresponding algebra to contain the NP polynomials in Lnp. If Lnp only contains polynomials without generators, that is equivalent to \(0\) and \(1\), then 0 is returned.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2,3,1],[2],[1]],[1,-2,1]];; gap> p2 := [[[2,2,1,4,3],[]],[1,-1]];; gap> PrintNPList([p1,p2]); a^2bca - 2b + a b^2adc - 1 gap> NumAlgGensNPList([p1,p2]); 4
‣ NumModGensNP( npm ) | ( function ) |
Returns: The minimum number mt so that npm belongs to the free module on mt generators.
When called with a polynomial npm in NPM format, this function returns the minimum number of module generators needed for the corresponding algebra to contain npm. If npm is an NP polynomial that does not contain module generators, then 0 is returned.
Example: Consider the following polynomial in NPM format.
gap> np := [[[-1,1,2,3,1],[-2],[-1]],[1,-2,1]];; gap> PrintNP(np); [ abca + 1 , - 2 ] gap> NumModGensNP(np); 2
‣ NumModGensNPList( Lnpm ) | ( function ) |
Returns: The minimum number mt so that each member of npm belongs to the free module on mt generators.
When called with a list of polynomials Lnpm in NPM format, this function returns the minimum number of module generators needed to contain the polynomials in Lnpm. If there are only polynomials in Lnpm in NP format, then 0 is returned.
Example: Consider the following two polynomials in NPM format.
gap> v1 := [[[-1,1,2,3,1],[-2],[-1]],[1,-2,1]];; gap> v2 := [[[-2,2,1,4,3],[-3]],[1,-1]];; gap> PrintNPList([v1,v2]); [ abca + 1 , - 2 ] [ 0, badc , - 1 ] gap> NumModGensNPList([v1,v2]); 3
‣ AddNP( u, v, c, d ) | ( function ) |
Returns: c\(*\)u\(+\)d\(*\)v
Computes c\(*\)u\(+\)d\(*\)v where u and v are polynomials in NP format and c and d are scalars.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-3]];; gap> p2 := [[[1,2,2],[]],[1,-4]];;
The second can be subtracted from the first by the function AddNP.
gap> PrintNP(AddNP(p1,p2,1,-1)); - ab^2 + a^2b + 1
‣ BimulNP( ga, np, dr ) | ( function ) |
Returns: the polynomial ga\(*\)np\(*\)dr in NP format
When called with a polynomial np and two monomials ga, dr, the function will return ga\(*\)np\(*\)dr. Recall from Section 2.1 that monomials are represented as lists.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-3]];; gap> p2 := [[[1,2,2],[]],[1,-4]];;
Multiplying p1 from the right by b and multiplying p2 from the left by a is possible with the function BimulNP:
gap> PrintNP(BimulNP([],p1,[2])); a^2b^2 - 3b gap> PrintNP(BimulNP([1],p2,[])); a^2b^2 - 4a
‣ CleanNP( u ) | ( function ) |
Returns: The cleaned up version of u
Given a polynomial in NP format, this function collects terms with same monomial, removes trivial monomials, and orders the monomials, with biggest one first.
Example: Consider the following polynomial in NP format.
gap> p := [[[1,1,2],[],[1,1,2],[]],[1,-3,-2,3]];; gap> PrintNP(p); a^2b - 3 - 2a^2b + 3
The monomials [1,1,2] and [] occur twice each. For many functions this representation of a polynomial in NP format is not allowed. It needs to be cleaned, as by CleanNP:
gap> PrintNP(CleanNP(p)); - a^2b
In order to define a polynomial over \(GF(2)\), the coefficients need to be defined over this field. Such a list of coefficients can be obtained in GAP from a list of integers by multiplying with the identity element of the field. The resulting polynomial need not be clean, and so should be made clean again with CleanNP.
gap> p := [[[1,1,2],[]],One(GF(2))*[1,-2]];; gap> CleanNP(p); [ [ [ 1, 1, 2 ] ], [ Z(2)^0 ] ]
‣ GtNP( u, v ) | ( function ) |
Returns: true if \(u > v\) and false if \(u \leq v\)
Greater than function for monomials u and v represented as in Section 2.1. It tests whether u\(>\)v. The ordering is done by degree and then lexicographically.
Example: Consider the following two monomials.
gap> u := [1,1,2]; [ 1, 1, 2 ] gap> v := [2,2,1]; [ 2, 2, 1 ]
We test whether u is greater than v.
gap> GtNP(u,v); false
‣ LtNP( u, v ) | ( function ) |
Returns: true if \(u < v\) and false if \(u \geq v\)
Less than function for NP monomials, tests whether u\(<\)v. The ordering is done by degree and then lexicographically.
Example: Consider the following two monomials.
gap> u := [1,1,2]; [ 1, 1, 2 ] gap> v := [2,2,1]; [ 2, 2, 1 ]
We test whether u is less than v.
gap> LtNP(u,v); true
‣ LMonNP( Lnp ) | ( function ) |
‣ LMonsNP( Lnp ) | ( function ) |
Returns: The leading monomial or a list of leading monomials.
These functions return the leading monomial of a polynomial (resp. the leading monomials of a list of polynomials) in NP format. The polynomials of Lnp are required to be clean; see Section 3.3-7.
Example: We put two polynomials in NP format into the list Lnp.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> Lnp := [p1,p2];;
The list of leading monomials is computed by LMonsNP:
gap> LMonsNP(Lnp); [ [ 1, 1, 2 ], [ 1, 2, 2 ] ]
For a nicer printing, the monomials can be converted into polynomials in NP format, and then submitted to PrintNPList:
gap> PrintNPList(List(LMonsNP(Lnp), q -> [[q],[1]])); a^2b ab^2
‣ LTermNP( Lnp ) | ( function ) |
‣ LTermsNP( Lnp ) | ( function ) |
Returns: The leading term or a list of leading terms.
These functions return the leading term of a polynomial (resp. the leading terms of a list of polynomials) in NP format. The polynomials of Lnp are required to be clean; see Section 3.3-7.
gap> p1 := [[[1,1,2],[1]],[6,-7]];; gap> p2 := [[[1,2,2],[2]],[8,-9]];; gap> Lnp := [p1,p2];; gap> LTermNP( p1 ); [ [ [ 1, 1, 2 ] ], [ 6 ] ] gap> LTnp := LTermsNP( Lnp ); [ [ [ [ 1, 1, 2 ] ], [ 6 ] ], [ [ [ 1, 2, 2 ] ], [ 8 ] ] ] gap> PrintNPList( LTnp ); 6a^2b 8ab^2
‣ MkMonicNP( np ) | ( function ) |
Returns: np made monic
This function returns the scalar multiple of a polynomial np in NP format that is monic, i.e., has leading coefficient equal to 1.
Example: Consider the following polynomial in NP format.
gap> p := [[[1,1,2],[]],[2,-1]];; gap> PrintNP(p); 2a^2b - 1
The coefficient of the leading term is \(2\). The function MkMonicNP finds this coefficient and divides every term by it:
gap> PrintNP(MkMonicNP(p)); a^2b - 1/2
‣ FactorOutGcdNP( np ) | ( function ) |
Returns: np with Gcd(coefficients) factored out
This function returns the scalar multiple of a polynomial np in NP format with integer coefficients such that its coefficients have Gcd equal to 1. If the coefficients are not all integers then fail is returned.
Example: Consider the following polynomial in NP format.
gap> p := [[[1,1,2],[1,2],[1]],[30,70,105]];; gap> PrintNP(p); 30a^2b + 70ab + 105a
The Gcd of the coefficients \([30,70,105]\) is \(5\). The function FactorOutGcdNP divides the polynomial by \(5\):
gap> PrintNP(FactorOutGcdNP(p)); 6a^2b + 14ab + 21a gap> m := MkMonicNP(p); [ [ [ 1, 1, 2 ], [ 1, 2 ], [ 1 ] ], [ 1, 7/3, 7/2 ] ] gap> fm := FactorOutGcdNP(m); fail
‣ MulNP( np1, np2 ) | ( function ) |
Returns: np1\(*\)np2
When invoked with two polynomials np1 and np2 in NP format, this function will return the product np1\(*\)np2.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];;
The function MulNP multiplies the two polynomials.
gap> PrintNP(MulNP(p1,p2)); a^2bab^2 - ab^2 - a^2b + 1
The fact that this multiplication is not commutative is illustrated by the following comparison, using MulNP twice and AddNP once.
gap> PrintNP(AddNP(MulNP(p1,p2),MulNP(p2,p1),1,-1)); - ab^2a^2b + a^2bab^2
‣ Grobner( Lnp[, D][, max] ) | ( function ) |
Returns: If the algorithm terminates, a Gröbner Basis or a record if max is specified (see description).
For a list Lnp of polynomials in NP format this function will use Buchberger's algorithm with normal form to find a Gröbner Basis (if possible, the general problem is unsolvable).
When called with the optional argument max, which should be a positive integer, the calculation will be interrupted if it has not ended after max iterations. The return value will be a record containing lists G and todo of polynomials in NP format, a boolean completed, and an integer iterations. Here G and todo form a Gröbner pair (see [Coh07]). The number of performed iterations will be placed in iterations. If the algorithm has terminated, then todo will be the empty list and completed will be equal to true. If the algorithm has not terminated, then todo will be a non-empty list of polynomials in NP format and completed will be false.
By use of the optional argument D, it is possible to resume a previously interrupted calculation.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> PrintNPList([p1,p2]); a^2b - 1 ab^2 - 1
Their Gröbner basis can be computed by the function Grobner.
gap> G := Grobner([p1,p2]);; gap> PrintNPList(G); b - a a^3 - 1
One iteration of the Gröbner computations is invoked by use of the parameter max:
gap> R := Grobner([p1,p2],1);; gap> PrintNPList(R.G); b - a gap> PrintNPList(R.todo); a^3 - 1 gap> R.iterations; 1 gap> R.completed; false
The above list R.todo can be used to resume the computation of the Gröbner basis computation with the Gröbner pair R.G, R.todo:
gap> PrintNPList(Grobner(R.G,R.todo)); b - a a^3 - 1
In order to perform the Gröbner basis computation with polynomials in a free algebra over the field \(GF(2)\), the coefficients of the polynomials need to be defined over that field.
gap> PrintNPList(Grobner([[p1[1],One(GF(2))*p1[2]],[p2[1],One(GF(2))*p1[2]]])); b + a a^3 + Z(2)^0
‣ SGrobner( Lnp[, todo][, max] ) | ( function ) |
Returns: If the algorithm terminates, a Gröbner Basis or a record if max is specified (see description).
For a list Lnp of polynomials in NP format this function will use Buchberger's algorithm with strong normal form (see [Coh07]) to find a Gröbner Basis (if possible, the general problem is unsolvable).
When called with the optional argument max, which should be a positive integer, the calculation will be interrupted if it has not ended after max iterations. The return value will be a record containing lists G and todo of polynomials in NP format, a boolean completed, and an integer iterations. Here G and todo form a Gröbner pair (see [Coh07]). The number of performed iterations will be placed in iterations. If the algorithm has terminated, then todo will be the empty list and completed will be equal to true. If the algorithm has not terminated, then todo will be a non-empty list of polynomials in NP format and completed will be false.
By use of the optional argument D, it is possible to resume a previously interrupted calculation.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> PrintNPList([p1,p2]); a^2b - 1 ab^2 - 1
Their Gröbner basis can be computed by the function Grobner.
gap> G := SGrobner([p1,p2]);; gap> PrintNPList(G); b - a a^3 - 1
One iteration of the Gröbner computations is invoked by use of the parameter max:
gap> R := SGrobner([p1,p2],1);; gap> PrintNPList(R.G); b - a gap> PrintNPList(R.todo); a^3 - 1 gap> R.iterations; 1 gap> R.completed; false
The above list R.todo can be used to resume the computation of the Gröbner basis computation with the Gröbner pair R.G, R.todo:
gap> PrintNPList(SGrobner(R.G,R.todo)); b - a a^3 - 1
‣ IsGrobnerBasis( G ) | ( function ) |
Returns: true if G is a Gröbner basis and false otherwise
When invoked with a list G of polynomials in NP format (see Section 2.1), this function will check whether the list is a Gröbner basis. The check is based on Theorem 1.4 from [Coh07].
Polynomials representing zero are allowed in G.
Example: Consider the following list of two polynomials in NP format.
gap> Lnp := [[[[1,1,2],[]],[1,-1]], [[[1,2,2],[]],[1,-1]]];; gap> PrintNPList(Lnp); a^2b - 1 ab^2 - 1
The function IsGrobner checks whether the list is a Gröbner basis.
gap> IsGrobnerBasis(Lnp); false
So the answer should be true for the result of a Gröbner computation:
gap> IsGrobnerBasis(Grobner(Lnp)); true
‣ IsStrongGrobnerBasis( G ) | ( function ) |
Returns: true if G is a strong Gröbner basis and false otherwise
When invoked with a list G of polynomials in NP format (see Section 2.1), this function will check whether the polynomials in this list form a strong Gröbner basis (see [Coh07]).
Polynomials representing zero are allowed in G.
Example: Consider the following list of two polynomials in NP format.
gap> Lnp := [[[[1,1,2],[]],[1,-1]], [[[1,2,2],[]],[1,-1]]];; gap> PrintNPList(Lnp); a^2b - 1 ab^2 - 1
The function IsStrongGrobner checks whether the list is a strong Gröbner basis.
gap> IsStrongGrobnerBasis(Lnp); false
But the answer should be true for the result of a strong Gröbner computation:
gap> IsStrongGrobnerBasis(SGrobner(Lnp)); true
A Gröbner basis that is not a strong Gröbner basis:
gap> B := SGrobner(Lnp);; gap> Add(B,AddNP(Lnp[1],B[1],1,-1));; gap> PrintNPList(B); b - a a^3 - 1 a^2b - b + a - 1 gap> IsGrobnerBasis(B); true gap> IsStrongGrobnerBasis(B); false
‣ IsGrobnerPair( G, D ) | ( function ) |
Returns: A boolean, which has the value true if the input forms a Gröbner pair
When called with two lists of polynomials in NP format, this function returns true if they form a Gröbner pair. Testing whether D is a basic set for G might involve computing the Gröbner basis. Instead of this only some simple computations are done to see if it can easily be proven that D is a basic set for G. If this cannot be proven easily, then false is returned, even though \(G, D\) might still be a Gröbner pair.
Example: Consider the following four polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> q1 := [[[2],[1]],[1,-1]];; gap> q2 := [[[1,1,1],[]],[1,-1]];;
The function IsGrobnerPair is used to check whether some combinations of these polynomials in two lists provide Gröbner pairs.
gap> IsGrobnerPair([p1,p2,q1],[q2]); true gap> IsGrobnerPair([q1,q2],[p1,p2]); false
The function IsGrobnerPair applied with an empty list as second argument is a check whether the first argument is a Gröbner basis.
gap> IsGrobnerPair([p1,p2],[]) = IsGrobnerBasis([p1,p2]); true
‣ MakeGrobnerPair( G, D ) | ( function ) |
Returns: A record containing a new Grobner pair
When called with as arguments a pair \(G, D\), this function cleans G and D and adds some obstructions to D till it is easily provable that D is a basic set for G (see [Coh07]). The result is a record containing the fields G and todo representing the Gröbner pair.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];;
The function MakeGrobnerPair turns the list with these two polynomials into a Gröbner pair, once the empty list is added as a second argument. The result is a record whose fields G and todo
gap> GP := MakeGrobnerPair([p1,p2],[]);; gap> PrintNPList(GP.G); a^2b - 1 ab^2 - 1 gap> PrintNPList(GP.todo); b - a
These fields are ready for use in Grobner
gap> GB := Grobner(GP.G,GP.todo);; gap> PrintNPList(GB); b - a a^3 - 1
‣ BaseQA( G, t, maxno ) | ( function ) |
Returns: A list of terms forming a basis of the quotient algebra of the (non-commutative) polynomial algebra in t variables by the 2-sided ideal generated by G
When called with a Gröbner basis G, the number t of generators of the algebra, and a maximum number of terms to be found maxno, BaseQA will return a (partial) base of the quotient algebra. If this function is invoked with maxno equal to 0, then a full basis will be given. If the dimension of this quotient algebra is infinite and maxno is set to 0, then the algorithm behind this function will not terminate.
Example: Consider the following Gröbner basis.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> G := Grobner([p1,p2]);; gap> PrintNPList(G); b - a a^3 - 1
The function BaseQA computes a basis for the quotient algebra of the free algebra over the rationals with generators \(a\) and \(b\) by the two-sided ideal generated by G.
gap> PrintNPList(G); b - a a^3 - 1 gap> BaseQA(G,2,0); [ [ [ [ ] ], [ 1 ] ], [ [ [ 1 ] ], [ 1 ] ], [ [ [ 1, 1 ] ], [ 1 ] ] ] gap> PrintNPList(BaseQA(G,2,0)); 1 a a^2
It is necessary for a correct result that the first argument be a Gröbner basis, as will be clear from the following invocation of BaseQA.
gap> PrintNPList(BaseQA([p1,p2],2,10)); 1 a b a^2 ab ba b^2 a^3 aba ba^2 bab b^2a b^3
‣ DimQA( G, t ) | ( function ) |
Returns: The dimension of the quotient algebra
When called with a Gröbner basis G and a number of variables t, the function DimQA will return the dimension of the quotient algebra of the free algebra generated by t variables by the ideal generated by G if it is finite. It will not terminate if the dimension is infinite.
If t=0, the function will compute the minimal value of t such that the polynomials in G belong to the free algebra on t generators.
To check whether the dimension of the quotient algebra is finite and to determine the type of growth if it is infinite, see also the functions FinCheckQA (3.6-2) and DetermineGrowthQA (3.6-1) in Section 3.6.
Example: Consider the following Gröbner basis.
gap> p1 := [[[1,1,2],[]],[1,-2]];; gap> p2 := [[[1,2,2],[]],[1,-2]];; gap> G := Grobner([p1,p2]);; gap> PrintNPList(G); b - a a^3 - 2
The function DimQA computes the dimension of the quotient algebra of the free algebra over the rationals with generators \(a\) and \(b\) by the two-sided ideal generated by G.
gap> DimQA(G,2); 3
‣ MatrixQA( i, B, GB ) | ( function ) |
Returns: The matrix representation for the i-th generator of the algebra for right multiplication in the quotient algebra
Given a basis B of the quotient algebra, a Gröbner basis (record) GB, and a natural number i, this function creates a matrix representation for the i-th generator of the algebra for right multiplication.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,2,1],[]],[1,-1]];;
The matrix of right multiplication by the first indeterminate \(a\) on the quotient algebra with respect to the ideal generated by p1 and p2 is obtained by applying MatrixQA to the Gröbner basis of these generators and a basis of the quotient algebra as found in BaseQA (3.5-1):
gap> GB := Grobner([p1,p2]);; gap> B := BaseQA(GB,2,0);; gap> PrintNPList(B); 1 a b a^2 ab a^3 a^2b a^4 gap> Display(MatrixQA(1, B,GB)); [ [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0 ] ]
The function is also applicable to Gröbner basis records for modules. Consider the following two vectors.
gap> v1 := [[[-1,1,2],[-1]],[1,-1]];; gap> v2 := [[[-2,2,2],[-2]],[1,-2]];;
The Gröbner basis record for this data is found by SGrobnerModule (3.9-1) and a quotient module basis by BaseQM (3.9-2):
gap> GBR := SGrobnerModule([v1,v2],[p1,p2]);; gap> B := BaseQM(GBR,2,2,0);;
The matrix of right multiplication by \(a\), the first generator of the free algebra, is
gap> Display(MatrixQA(1,B,GBR)); [ [ 0, 1 ], [ 1, 0 ] ]
‣ MatricesQA( t, B, GB ) | ( function ) |
Returns: The matrix representation for the t generators of the algebra for right multiplication in the quotient algebra
Given a basis B of the quotient algebra, a Gröbner basis (record) GB, and a natural number t, this function creates a list of t matrices representing the linear transformations of the generators of the algebra by right multiplication on the quotient algebra.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,2,1],[]],[1,-1]];;
The function MatricesQA gives the list of matrices found by MatrixQA (3.5-3) when the first argument takes the integer values between 1 and the number of all algebra generators.
gap> GB := Grobner([p1,p2]);; gap> B := BaseQA(GB,2,0);; gap> mats := MatricesQA(2,B,GB);; gap> for mat in mats do Display(mat); Print("\n"); od; [ [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0, 0, 0, 0 ] ] [ [ 0, 0, 1, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 1, 0, 0 ], [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 1, 0, 0, 0, 0, 0, 0 ] ]
The result is also obtainable by use of the List function:
gap> MatricesQA(2,B,GB) = List([1,2], q -> MatrixQA(q,B,GB)); true
‣ MulQA( p1, p2, G ) | ( function ) |
Returns: The strong normal form of the product p1\(*\)p2 with respect to G
When called with two polynomials in NP form, p1 and p2, and a Gröbner basis G, this function will return the product in the quotient algebra.
Example: Consider the following Gröbner basis.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> G := Grobner([p1,p2]);; gap> PrintNPList(G); b - a a^3 - 1
Print the product in the quotient algebra of the polynomials \(a-2\) and \(b-3\) by use of MulQA:
gap> s1 := [[[1],[]],[1,-2]];; gap> s2 := [[[2],[]],[1,-3]];; gap> PrintNP(MulQA(s1,s2,G)); a^2 - 5a + 6
The result should be equal to the strong normal form of the product of \(a-2\) and \(b-3\) with respect to G:
gap> MulQA(s1,s2,G) = StrongNormalFormNP(MulNP(s1,s2),G); true
‣ StrongNormalFormNP( f, G ) | ( function ) |
Returns: The strong normal form of a polynomial with respect to G
When invoked with a polynomial in NP format (see Section 2.1) and a finite set G of polynomials in NP format, this function will return a strong normal form (that is, a polynomial that is equal to f modulo G, every monomial of which is a multiple of no leading monomial of an element of G).
Note that the StrongNormalForm with respect to a Gröbner basis is uniquely determined, but that for an arbitrary input G the result may depend on the order in which the individual reduction steps are implemented.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];;
The strong normal form of the polynomial
gap> p := [[[1,1,1,2],[2,1],[]],[1,-1,3]];;
with respect to the list [p1,p2] is computed by use of the function StrongNormalFormNP:
gap> PrintNP(StrongNormalFormNP(p,[p1,p2])); - ba + a + 3
‣ DetermineGrowthQA( Lm, t, exact ) | ( function ) |
Returns: If the quotient algebra is finite dimensional, then the integer 0 is returned. If the growth is polynomial and the algorithm found a precise degree d of the growth polynomial, then d is returned. If the growth is polynomial and no precise answer is found, an interval [d1,d2] is returned in which the dimension lies. If the growth is exponential, the string "exponential growth" is returned.
Given leading monomials Lm of some Gröbner basis (these can be obtained with the function LMonsNP (3.3-10)), the number t of generators of a free algebra, say \(A\), in which the monomials lie, and a boolean exact, this function checks whether the quotient algebra of \(A\) by the ideal generated by Lm is finite dimensional. In doing so it constructs a graph of normal words which helps with the computations. It also checks for exponential or polynomial growth in the infinite case.
If the precise degree is needed in the polynomial case, the argument exact should be set to true.
The function DetermineGrowthQA allows preprocessing, which may speed up the computations. This can be done with the function PreprocessAnalysisQA (3.6-4).
Example: For the list of monomials consisting of a single variable in a free algebra generated by two variables the growth is clearly polynomial of degree 1. This is verified by invoking DetermineGrowthQA with arguments [[1]] (the list of the single monomial consisting of the first variable), the number of generators of the free algebra to which the monomials belong (which is 2 here), and the boolean true indicating that we wish a precise degree in case of polynomial growth.
gap> DetermineGrowthQA([[1]],2,true); 1
Here is an example of polynomial growth of degree 2:
gap> L := [[1,2,1],[2,2,1]]; [ [ 1, 2, 1 ], [ 2, 2, 1 ] ] gap> DetermineGrowthQA(L,2,true); 2
In order to show how to apply the function to arbitrary polynomials, consider the following two polynomials in NP format.
gap> F := GF(256); GF(2^8) gap> z := GeneratorsOfField(F)[1]; Z(2^8) gap> p1 := [[[1,1,1,2],[]],[z,1]];; gap> p2 := [[[2,2,2,1],[]],[1,z]];;
The polynomials p1 and p2 have coefficients in the field F of order 256. In order to study the growth of the quotient algebra we first compute the list of leading monomials of the Gröbner basis elements and next apply DetermineGrowthQA.
gap> GB := Grobner([p1,p2]);; gap> L := LMonsNP(GB);; gap> for lm in L do PrintNP( [ [ lm ], [ 1 ] ] ); od; a^3b b^2 ba a^5 gap> DetermineGrowthQA(L,2,true); 0
‣ FinCheckQA( Lm, t ) | ( function ) |
Returns: true, if the quotient algebra is finite dimensional and false otherwise
Given a list Lm of leading monomials such that none of these divides another, and the number t of generators of a free algebra in which they are embedded, this function checks whether the quotient algebra of the free algebra by the ideal generated by Lm is finite dimensional.
When given a Gröbner basis \(G\), the dimension of the quotient algebra of the free algebra by the ideal generated by \(G\) coincides with the the dimension of the quotient algebra of the free algebra by the ideal generated by the leading terms of elements of \(G\). These can be obtained from \(G\) with the function LMonsNP (3.3-10).
The function FinCheckQA allows for preprocessing with the function PreprocessAnalysisQA (3.6-4). This may speed up the computation.
Example: Consider the following list L of two monomials.
gap> L := [[1,2,1],[2,2,1]];;
Finiteness of the dimension of the quotient algebra of the free algebra by the ideal generated by these two monomials can be decided by means of FinCheckQA. Its arguments are L and the number of generators of the free algebra in which the monomials reside.
gap> FinCheckQA(L,2); false
This example turns out to be infinite dimensional. Here is a finite-dimensional example.
gap> FinCheckQA([[1],[2,2]],2); true
‣ HilbertSeriesQA( Lm, t, d ) | ( function ) |
Returns: A list of coefficients of the Hilbert series up to degree d
Given a set of monomials Lm, none of which divides another, and the number n of generators of the free algebra in which they occur, this function computes the Hilbert series up to a given degree d.
Internally, it builds (part of) the graph of standard words. This function will remove zeroes from the end of the list of coefficients.
Example: Consider the following list L of two monomials.
gap> L := [[1,2,1],[2,2,1]];;
Finiteness of the dimension of the quotient algebra of the free algebra by the ideal generated by these two monomials can be decided by means of FinCheckQA. Its arguments are L and the number of generators of the free algebra in which the monomials reside.
gap> HilbertSeriesQA(L,2,10); [ 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 ]
This indicates that the growth may be polynomial. DetermineGrowthQA (3.6-1) can be used to check this.
‣ PreprocessAnalysisQA( Lm, t, iterations ) | ( function ) |
Returns: The left-reduced list of `obstructions', obtained by applying left-reduction recursively
This preprocessing of the list Lm of monomials can be applied to the set of leading terms of a Gröbner basis before calling the functions FinCheckQA (3.6-2) or DetermineGrowthQA (3.6-1), in order to speed up calculations using these functions. As the name suggests, t should be the size of the alphabet. The parameter iterations gives the maximum number of recursion steps in the preprocessing (0 means no restriction). For more information about this function see [Kro03].
Example: Consider the following two polynomials in NP format of which a Gröbner basis is computed.
F := GF(256); z := GeneratorsOfField(F)[1]; gap> p1 := [[[1,1,1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,2,1,1,1],[]],[1,-1]];; gap> GB := Grobner([p1,p2]);; gap> PrintNPList(GB); a^4b - 1 ba - ab b^2 - a a^5 - b
Application of PreprocessAnalysisQA is carried out on the leading terms of GB, with 2, 4, 8, recursions, respectively.
gap> L := LMonsNP(GB); [ [ 1, 1, 1, 1, 2 ], [ 2, 1 ], [ 2, 2 ], [ 1, 1, 1, 1, 1 ] ] gap> L1 := PreprocessAnalysisQA(L,2,2); [ [ 1, 1, 1 ], [ 2, 1 ], [ 1, 1, 2 ], [ 2, 2 ] ] gap> L2 := PreprocessAnalysisQA(L1,2,4); [ [ 1 ], [ 2 ] ]
‣ EvalTrace( p, Lnp ) | ( function ) |
Returns: The trace evaluated to a polynomial in NP format.
For a traced polynomial p and a list Lnp of polynomials in NP format, this program evaluates the trace by substituting the polynomials of Lnp back in the expression p.trace and computing the resulting polynomial. The result should have the same value as p.pol.
Example: First we compute the traced Gröbner basis of the list of the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,1],[]],[1,-1]];; gap> Lnp := [p1,p2];; gap> GBT := SGrobnerTrace(Lnp);;
In order to check that the polynomials in GBT belong to the ideal generated by p1 and p2, we evaluate the trace. For each traced polynomial p in GBT, the polynomial p.pol is equated to the evaluated expression p.trace, in which each occurrence of G(i) is replaced by Lnp[i] by use of EvalTrace.
gap> ForAll(GBT,q -> EvalTrace(q,Lnp) = q.pol); true
‣ PrintTraceList( G ) | ( function ) |
When invoked with a list G of traced polynomials, this function prints the traces of that list.
Example: First we compute the traced Gröbner basis of the list of two polynomials in NP format and next we print it by use of PrintTraceList.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,1],[]],[1,-1]];; gap> GBT := SGrobnerTrace([p1,p2]);; gap> PrintTraceList(GBT); aG(1) - bG(1) - G(1)ba^2b + a^2G(2)ab G(1)ba^2 + bG(1)ba + G(2) - a^2G(2)a - ba^2G(2)
‣ PrintTracePol( p ) | ( function ) |
This function prints the trace of an NP polynomial p.
Example: First we compute the traced Gröbner basis of the list of two polynomials in NP format. Next we print the trace polynomial of the members of the list by use of PrintTracePol.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,1],[]],[1,-1]];; gap> GBT := SGrobnerTrace([p1,p2]);; gap> for np in GBT do PrintTracePol(np); Print("\n"); od; aG(1) - bG(1) - G(1)ba^2b + a^2G(2)ab G(1)ba^2 + bG(1)ba + G(2) - a^2G(2)a - ba^2G(2)
‣ PrintNPListTrace( G ) | ( function ) |
When invoked with a set of traced non-commutative polynomials G, this function prints the list of the traced polynomials, without the trace.
Example: First we compute the traced Gröbner basis of the list of two polynomials in NP format. Next we print the polynomials found by use of PrintNPListTrace.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,1],[]],[1,-1]];; gap> GBT := SGrobnerTrace([p1,p2]);; gap> PrintNPListTrace(GBT); b - a a^3 - 1
‣ SGrobnerTrace( Lnp ) | ( function ) |
Returns: Gröbner Basis, traceable
For a list of noncommutative polynomials Lnp this function will use Buchberger's algorithm with strong normal form to find a Gröbner Basis G (if possible; the general problem is unsolvable).
The results will be traceable. Functions that can print the Gröbner basis are PrintTraceList (3.7-2) (with the trace) and PrintNPListTrace (3.7-4) (without the trace).
Example: For the list of the following two polynomials in NP format, a traced Gröbner basis is computed.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,1],[]],[1,-1]];; gap> GBT := SGrobnerTrace([p1,p2]); [ rec( pol := [ [ [ 2 ], [ 1 ] ], [ 1, -1 ] ], trace := [ [ [ ], 1, [ 2, 1, 1, 2 ], -1 ], [ [ 2 ], 1, [ ], -1 ], [ [ 1 ], 1, [ ], 1 ], [ [ 1, 1 ], 2, [ 1, 2 ], 1 ] ] ), rec( pol := [ [ [ 1, 1, 1 ], [ ] ], [ 1, -1 ] ], trace := [ [ [ 2 ], 1, [ 2, 1 ], 1 ], [ [ ], 1, [ 2, 1, 1 ], 1 ], [ [ ], 2, [ ], 1 ], [ [ 2, 1, 1 ], 2, [ ], -1 ], [ [ 1, 1 ], 2, [ 1 ], -1 ] ] ) ]
‣ StrongNormalFormTraceDiff( np, GBT ) | ( function ) |
Returns: The traced polynomial for the difference of f with the strong normal form of np with respect to GBT
When invoked with a polynomial np in NP format as its first argument, and a traced Gröbner basis GBT as generated by SGrobnerTrace (3.7-5), this function returns the difference of np with the strong normal form of np with respect to GBT. This difference d is returned as a traced polynomial. The trace information d.trace gives an expression of d.pol as a combination of polynomials from the list of polynomials to which the trace parts of GBT are referring. Typically, this is the set of relations used as input to the computation of GBT.
Note that the difference of the polynomials np and d.pol is the same as the StrongNormalForm of np.
Example: First we compute the traced Gröbner basis of the list of the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,1],[]],[1,-1]];; gap> GBT := SGrobnerTrace([p1,p2]);;
Of the polynomial \(a^6\) we compute its difference with the normal form. The result is printed by used of PrintNP (3.2-1) and PrintTraceList (3.7-2).
gap> f := [[[1,1,1,1,1,1]],[1]];; gap> sf := StrongNormalFormTraceDiff(f,GBT);; gap> PrintNP(sf.pol); a^6 - 1 gap> PrintTraceList([sf]); G(1)ba^2 + bG(1)ba + G(1)ba^5 + bG(1)ba^4 + G(2) + G(2)a^3 - a^2G( 2)a - ba^2G(2) - a^2G(2)a^4 - ba^2G(2)a^3
More about these functions can be found in A.4
‣ SGrobnerTrunc( Lnp, deg, wtv ) | ( function ) |
Returns: A list of homogeneous NP polynomials if the first argument of the input is a list of homogeneous NP polynomials, and the boolean false otherwise.
This functions should be invoked with a list Lnp of polynomials in NP format, a natural number deg, and a weight vector wtv of length the number of generators of the free algebra \(A\) containing the elements of Lnp, and with positive integers for entries. If the polynomials of Lnp are homogeneous with respect to wtv, the function will return a Gröbner basis of Lnp truncated above deg. If the list of polynomials Lnp is not homogeneous with respect to wtv, it returns false. The homogeneity check can be carried out by CheckHomogeneousNPs (3.8-3).
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,2,2,1],[2,1,1,2]],[1,-1]];; gap> p2 := [[[2,2,2],[1,1]],[1,-1]];; gap> PrintNPList([p1,p2]); ab^2a - ba^2b b^3 - a^2
These are homogeneous with respect to weights \([3,2]\). The degrees are \(10\) and \(6\), respectively. The Gröbner basis truncated above degree 12 of the list [p1,p2] is computed and subsequently printed as follows.
gap> PrintNPList(SGrobnerTrunc([p1,p2],12,[3,2])); ba^2 - a^2b b^3 - a^2 ab^2a - a^2b^2
‣ CheckHomogeneousNPs( Lnp, wtv ) | ( function ) |
Returns: A list of weighted degrees of the polynomials if these are homogeneous with respect to wtv, and false otherwise.
When invoked with a list of NP polynomials Lnp and a weight vector wtv (whose entries should be positive integers), this function returns the list of weighted degrees of the polynomials in Lnp if these are all homogeneous and nonzero, and false otherwise. Here, a polynomial is (weighted) homogeneous with respect to a weight vector \(w\) if there is constant \(d\) such that, for each monomial \([t_1,...,t_r]\) of the polynomial the sum of all \(w[t_i]\) for \(i\) in \([1..r]\) is equal to \(d\). The natural number \(d\) is then called the weighted degree of the polynomial.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,2,2,1],[2,1,1,2]],[1,-1]];; gap> p2 := [[[2,2,2],[1,1]],[1,-1]];; gap> PrintNPList([p1,p2]); ab^2a - ba^2b b^3 - a^2
These are homogeneous with respect to weights \([3,2]\). The degrees are \(10\) and \(6\), respectively. This is checked as follows.
gap> CheckHomogeneousNPs([p1,p2],[3,2]); [ 10, 6 ]
‣ BaseQATrunc( Lnp, deg, wtv ) | ( function ) |
Returns: A list of monomials if the first argument of the input is a list of homogeneous NP polynomials or false.
When invoked with a list of polynomials Lnp, a natural number deg, and a weight vector wtv of length the number of variables and with positive integers for entries, such that the polynomials of Lnp are homogeneous with respect to wtv, it returns a list whose \(i\)-th entry is a basis of monomials of the homogeneous part of degree \(i-1\) the quotient algebra of the free noncommutative algebra by the weighted homogeneous ideal generated by Lnp truncated above deg. If the list of polynomials Lnp is not homogeneous, it returns false.
Example: Consider the truncated Gröbner basis of the following two polynomials in NP format.
gap> p1 := [[[1,2,2,1],[2,1,1,2]],[1,-1]];; gap> p2 := [[[2,2,2],[1,1]],[1,-1]];; gap> wtv := [3,2];; gap> GB := SGrobnerTrunc([p1,p2],12,wtv);; gap> GBNP.ConfigPrint("a","b"); gap> PrintNPList(GB); ba^2 - a^2b b^3 - a^2 ab^2a - a^2b^2
A basis of standard monomials is found and printed as follows.
gap> BT := BaseQATrunc(GB,12,wtv);; gap> for degpart in BT do > for mon in degpart do PrintNP([[mon],[1]]); od; > od; 1 b a b^2 ba ab a^2 b^3 b^2a bab ab^2 aba a^2b b^4 a^3 b^3a b^2ab bab^2 ab^3 baba abab a^2b^2 b^5 a^2ba b^4a a^3b b^3ab b^2ab^2 bab^3 ab^4 a^4 b^2aba ab^3a babab abab^2 a^2b^3 b^6
‣ DimsQATrunc( Lnp, deg, wtv ) | ( function ) |
Returns: A list of monomials if the first argument of the input is a list of homogeneous NP polynomials or false.
When invoked with a list of polynomials Lnp, a natural number deg, and a weight vector wtv of length the number of variables and with positive integers for entries, such that the polynomials of Lnp are homogeneous with respect to wtv, it returns a list of dimensions of the homogeneous parts of the quotient algebra of the free noncommutative algebra by the ideal generated by Lnp truncated above deg. The \(i\)-th entry of the list gives the dimension of the homogeneous part of degree \(i-1\) of the quotient algebra. If the list of polynomials Lnp is not homogeneous, it returns false.
Example: Consider the truncated Gröbner basis of the following two polynomials in NP format.
gap> p1 := [[[1,2,2,1],[2,1,1,2]],[1,-1]];; gap> p2 := [[[2,2,2],[1,1]],[1,-1]];; gap> wtv := [3,2];; gap> GB := SGrobnerTrunc([p1,p2],12,wtv);;
Information on the dimensions of the homogeneous parts of the quotient algebra is found as follows,
gap> DimsQATrunc(GB,12,wtv); [ 1, 0, 1, 1, 1, 2, 2, 3, 3, 5, 4, 7, 7 ]
‣ FreqsQATrunc( Lnp, deg, wtv ) | ( function ) |
Returns: A list of multiplicities of frequencies of monomials if the first argument of the input is a list of homogeneous polynomials in NP format, and false otherwise.
The frequency of a monomial is the list of numbers of occurrences of a variable in the monomial for each variable; the multiplicity of a frequency is the number of monomials in the standard basis for a quotient algebra with this frequency. When invoked with a list Lnp of polynomials in NP format representing a (truncated) Gröbner basis, a natural number deg, and a weight vector wtv of length the number of variables and with positive integers for entries, such that the polynomials of Lnp are homogeneous with respect to wtv, it returns a list of frequencies occurring with their multiplicities for the quotient algebra of the free noncommutative algebra by the ideal generated by Lnp truncated above deg. The \(i\)-th entry of the list gives the frequencies of the weight \((i-1)\) basis monomials of the quotient algebra. If the list of polynomials Lnp is not homogeneous with respect to wtv, it returns false.
Example: Consider the truncated Gröbner basis of the following two polynomials in NP format.
gap> p1 := [[[1,2,2,1],[2,1,1,2]],[1,-1]];; gap> p2 := [[[2,2,2],[1,1]],[1,-1]];; gap> wtv := [3,2];; gap> GB := SGrobnerTrunc([p1,p2],12,wtv);; gap> PrintNPList(GB); ba^2 - a^2b b^3 - a^2 ab^2a - a^2b^2
The multiplicities of the frequencies of of monomials in a standard basis of the quotient algebra with respect to the ideal generated by GB is found as follows, for weights up to and including 8.
gap> F := FreqsQATrunc(GB,8,wtv); [ [ [ [ ], 1 ] ], [ [ [ 0, 1 ], 1 ] ], [ [ [ 1, 0 ], 1 ] ], [ [ [ 0, 2 ], 1 ] ], [ [ [ 1, 1 ], 2 ] ], [ [ [ 2, 0 ], 1 ], [ [ 0, 3 ], 1 ] ], [ [ [ 1, 2 ], 3 ] ], [ [ [ 2, 1 ], 2 ], [ [ 0, 4 ], 1 ] ] ]
The interpretation of this data is given by the following lines of code.
gap> for f in F do > if f[1][1] <> [] then > Print("At level ", wtv * (f[1][1]), " the multiplicities are\n"); > for x in f do > Print(" for ",x[1],": ",x[2],"\n"); > od; > else > Print("At level ", 0 , " the multiplicity of [] is ",f[1][2],"\n"); > fi; > Print("\n"); > od; At level 0 the multiplicity of [] is 1 At level 2 the multiplicities are for [ 0, 1 ]: 1 At level 3 the multiplicities are for [ 1, 0 ]: 1 At level 4 the multiplicities are for [ 0, 2 ]: 1 At level 5 the multiplicities are for [ 1, 1 ]: 2 At level 6 the multiplicities are for [ 2, 0 ]: 1 for [ 0, 3 ]: 1 At level 7 the multiplicities are for [ 1, 2 ]: 3 At level 8 the multiplicities are for [ 2, 1 ]: 2 for [ 0, 4 ]: 1
‣ SGrobnerModule( Lnpm, Lnp ) | ( function ) |
Returns: A record GBR containing a Gröbner basis (if found...the general problem is unsolvable) for modules; GBR.p will contain the prefix rules and GBR.ts will contain the two-sided rules, and GBR.pg will be the smallest rank of the free module to which all prefix relations belong
For a list Lnpm of vectors in NPM format (see Section 2.1), and a list Lnp of polynomials in NP format, this function will use Buchberger's algorithm with strong normal form applied to the union of Lnpm, Lnp, the set of polynomials \(x*e-x\) and \(x*m[i]\) for \(x\) a standard indeterminate, a module generator \(m[j]\) or the dummy indeterminate \(e\), and the set of all \(e*x -x\) for \(x\) a standard indeterminate, to find a Gröbner Basis record GBR (if possible; the general problem is unsolvable). This record will have a Gröbner Basis GBR.ts for the two-sided ideal generated by Lnp and an intersection with the module GBR.p representing the module relations needed to find representative vectors in the module uniquely by means of a strong normal form computation modding out GBR.p and, for the scalars, GBR.ts.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-2]];; gap> p2 := [[[1,2,2],[]],[1,-3]];;
Consider also the following two vectors in NPM format.
gap> v1 := [[[-1,1,2],[-1]],[1,-1]];; gap> v2 := [[[-2,2,2],[-2]],[1,-2]];;
The Gröbner basis record for this data is found by SGrobnerModule:
gap> GBR := SGrobnerModule([v1,v2],[p1,p2]);;
The record GBR has two fields, p for prefix relations (vectors in the module) and ts for two-sided relations (polynomials in the algebra):
gap> PrintNPList(GBR.p); [ 0, 1 ] [ 1 , 0] gap> PrintNPList(GBR.ts); b - 3/2a a^3 - 4/3
‣ BaseQM( GBR, t, mt, maxno ) | ( function ) |
Returns: A basis of the module obtained from the free module of rank mt over the free algebra on t generators by factoring out the submodule generated by the elements of GBR
When called with a Gröbner basis record GBR (see Section 2.8), the number of variables t, the number of module generators mt, and a maximum number of terms to be found, maxno, the function BaseQM will return a (partial) base of the quotient module of \(A^{mt}\) over the free algebra on \(A\) on t generators by the right sub \(A\)-module generated by the elements of GBR. Note that the record GBR consists of two fields: the list GBR.p of vectors in NPM format representing elements of the free module \(A^{mt}\), and the list GBR.ts of polynomials in NP format representing elements of \(A\). The submodule generated by GBR is considered to be the right submodule of \(A^{mt}\) generated by GBR.p and all elements of the form \(v\cdot np\) with \(np\) in the two-sided ideal of \(A\) generated by GBR.ts and \(v\) in \(A^{mt}\). If this function is invoked with maxno equal to 0, then a full basis will be given.
If t\(=0\), then t will be set to the minimal value such that all polynomials of GBR.ts and all polynomials occurring in GBR.p have at most t variables.
If mt\(=0\), then mt will be set to the minimal value such that all vectors of GBR.p belong to \(A^{mt}\).
If the module is cyclic (that is, has a single generator), it is possible to use the Gröbner basis of the ideal in the algebra instead of the Gröbner basis record. This can be done by entering 0 for the number mt of module generators.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,2,1],[]],[1,-1]];;
Consider also the following two vectors in NPM format.
gap> v1 := [[[-1,1,2],[-1]],[1,-1]];; gap> v2 := [[[-2,2,2],[-2]],[1,-2]];;
The Gröbner basis record for this data is found by SGrobnerModule (3.9-1):
gap> GBR := SGrobnerModule([v1,v2],[p1,p2]);; gap> PrintNPList(GBR.ts); ba - ab b^2 - a^2 a^3b - 1 a^5 - b gap> PrintNPList(GBR.p); [ 0, 1 ] [ b - a , 0] [ a^2 - 1 , 0] [ ab - 1 , 0]
The function BaseQM computes a basis.
gap> B := BaseQM(GBR,2,2,0);; gap> PrintNPList(B); [ 1 , 0] [ a , 0]
The function BaseQM with arguments so as to let the number of dimensions of the module and the number of variables be chosen minimal.
gap> B := BaseQM(GBR,0,0,0);; gap> PrintNPList(B); [ 1 , 0] [ a , 0]
The function BaseQM can also be used to ompute the first three elements of a basis.
gap> B := BaseQM(GBR,2,2,3);; gap> PrintNPList(B); [ 1 , 0] [ a , 0]
‣ DimQM( GBR, t, mt ) | ( function ) |
Returns: The dimension of the quotient module
When called with a Gröbner basis record GBR (see Section 2.8), a number of variables t at least equal to the number of generators involved in the polynomials of GBR.p and GBR.ts, and a number of generators mt of a free module containing the prefix relations in GBR.p, the function DimQM will return the dimension over the coefficient field of the quotient module of the free right module \(A^{mt}\) of rank mt over the free algebra \(A\) on t generators by the right sub \(A\)-module generated by the elements of GBR, if this dimension is finite. Otherwise, the computation invoked by the function will not terminate.
If t\(=0\), then t will be set to the minimal value such that all polynomials of GBR.ts and all polynomials occurring in GBR.p belong to \(A^{mt}\).
If mt\(=0\), then mt will be set to the minimal value such that all vectors of GBR.p belong to \(A^{mt}\). Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,1,2],[]],[1,-1]];; gap> p2 := [[[2,2,2,1],[]],[1,-1]];;
Consider also the following two vectors in NPM format.
gap> v1 := [[[-1,1,2],[-2]],[1,-1]];; gap> v2 := [[[-2,2,2],[-1]],[1,-2]];;
The Gröbner basis record for this data is found by SGrobnerModule (3.9-1):
gap> GBR := SGrobnerModule([v1,v2],[p1,p2]);;
The function DimQM computes the dimension over the rationals of the quotient of the free module over the free algebra on two generators by the submodule generated by the vectors v1, v2, \([p,q]\), where \(p\) and \(q\) run over all elements of the two-sided ideal in the free algebra generated by p1 and p2.
gap> SetInfoLevel(InfoGBNP,2); gap> DimQM(GBR,2,2); 0
The answer should be equal to the size of BaseQM(GBR,t,mt,0).
gap> DimQM(GBR,2,2) = Length(BaseQM(GBR,2,2,0)); true gap> SetInfoLevel(InfoGBNP,0);
‣ MulQM( p1, p2, GBR ) | ( function ) |
Returns: The strong normal form of the product p1\(*\)p2 with respect to GBR
When called with three arguments, the first of which, p1, is a module element in NPM format, the second of which, p2, is a polynomial in NP format representing an element of the quotient algebra, and the third of which is a Gröbner basis record GBR, this function will return the product p1*p2 in the module.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> PrintNPList([p1,p2]); a^2b - 1 ab^2 - 1
Consider also the following two vectors in NPM format.
gap> v1 := [[[-1,1,2],[-1]],[1,-1]];; gap> v2 := [[[-2,2,2],[-2]],[1,-2]];; gap> PrintNPList([v1,v2]); [ ab - 1 , 0] [ 0, b^2 - 2 ]
The Gröbner basis record for this data is found by SGrobnerModule (3.9-1):
gap> GBR := SGrobnerModule([v1,v2],[p1,p2]);; gap> PrintNPList(GBR.ts); b - a a^3 - 1 gap> PrintNPList(GBR.p); [ 0, 1 ] [ a - 1 , 0]
The function MulQM computes the product of the vector w with the polynomial q.
gap> w := [[[-1,2],[-2,1]],[1,-4]];; gap> PrintNP(w); [ b , - 4a ] gap> q := [[[2,2,1],[1]],[2,3]];; gap> PrintNP(q); 2b^2a + 3a gap> wq := MulQM(w,q,GBR);; gap> PrintNP(wq); [ 5 , 0]
‣ StrongNormalFormNPM( f, GBR ) | ( function ) |
Returns: The strong normal form of a polynomial in NP format with respect to GBR
When invoked with a polynomial in NP format (see Section 2.1) and a Gröbner basis record GBR (see Section 2.8), this function will return the strong normal form (the polynomial reduced by the prefix and two-sided relations of the Gröbner basis combination).
This function assumes that GBR.p and GBR.ts are ordered (with the ordering LtNP (3.3-9)), that the polynomials in GBR.ts are monic and clean (see MkMonicNP (3.3-12) and CleanNP (3.3-7)), and that the polynomial f is clean. Note that a Gröbner basis record as returned by a function like SGrobnerModule (3.9-1) is in the required form.
Example: Consider the following two polynomials in NP format.
gap> p1 := [[[1,1,2],[]],[1,-1]];; gap> p2 := [[[1,2,2],[]],[1,-1]];; gap> PrintNPList([p1,p2]); a^2b - 1 ab^2 - 1
Consider also the following two vectors in NPM format.
gap> v1 := [[[-1,1,2],[-1]],[1,-1]];; gap> v2 := [[[-2,2,2],[-2]],[1,-2]];; gap> PrintNPList([v1,v2]); [ ab - 1 , 0] [ 0, b^2 - 2 ]
The Gröbner basis record for this data is found by SGrobnerModule (3.9-1):
gap> GBR := SGrobnerModule([v1,v2],[p1,p2]);; gap> PrintNPList(GBR.ts); b - a a^3 - 1 gap> PrintNPList(GBR.p); [ 0, 1 ] [ a - 1 , 0]
The vector w is brought into strong normal form with respect to GBR:
gap> w := [[[-1,2],[-2,1]],[1,-4]];; gap> PrintNP(w); [ b , - 4a ] gap> v := StrongNormalFormNPM(w,GBR);; gap> PrintNP(v); [ 1 , 0]
generated by GAPDoc2HTML