3 Functions

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

, ... for x_1, x_2, x_3, ..., 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.

*no arguments*When the function is invoked without arguments the printing is reset to the default (see above).

**algebra**When the function is invoked with an algebra as argument, generators will be printed as they would be in the algebra.

**algebra,integer**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 seperated over the`n`dimensions.**leftmodule**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, seperated over the

`n`dimensions.**string**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.

**integer**When the function is invoked with an integer as its argument, the

`n`-th generator will be printed as`x.<n>`

.**integer, string**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.**string, string, ..., string**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 ≤ 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 ≥ 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

`‣ LMonsNP` ( Lnp ) | ( function ) |

Returns: A list of leading monomials

This function returns the leading monomials of a list `Lnp` 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

`‣ 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 all terms by it:

gap> PrintNP(MkMonicNP(p)); a^2b - 1/2

`‣ 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⋅ 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-11) 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.

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