### 2. Description

#### 2.1 Noncommutative Polynomials (NPs)

The main datatype of the GBNP package is a list of noncommutative polynomials (NPs). The data type for a noncommutative polynomial is a list of two lists:

• the first list is a list `m` of monomials

• the second list is a list `c` of coefficients of these monomials

The two lists have the same length. The polynomial represented by the list `[m,c]` of the two lists `m` and `c` is sum_i c_i m_i.

A monomial is a list of positive integers. They are interpreted as the indices of the variables. So, if m = [1,2,3,2,1] and the variables are x,y,z (in this order), then m stands for the monomial xyzyx. By the way, the name of the variables has no meaning. There are various ways to print these but the default is as a,b,c,... (see below).

The zero polynomial is represented by `[[],[]]`. The polynomial 1 is represented by `[[[]],[1]]`.

The algorithms work for the ring F<< x_1,x_2,...,x_t>> of noncommutative polynomials in t variables, where F is a field.

In order to facilitate viewing the polynomials, we provide the function `PrintNP` (3.2-2). For instance

 ```PrintNP([[[1,2],[2,1]],[3,-1]]); ```

yields

 ```3ab - ba ```

Indeed, we have the names: `a`, `b`, `c`, ... for x_1, x_2, x_3, ..., except that everything beyond l (the 12-th letter) is called x. This can be easily changed by calling the function `GBNP.ConfigPrint`, which can be found in Section 3.2.

The function `PrintNPList` (3.2-3) is available for printing a list of NPs (=noncommutative polynomials).

In order to facilitate testing whether two data structures represent the same NP, we use the convention that polynomials are "clean". This means that they look as if they are output of the function `CleanNP` (3.3-3). In other words:

• each monomial occurs at most once in the list of monomials,

• no monomials occur whose coefficients are zero,

• the monomials are ordered (total degree first, then lexicographically) from big to small.

An advantage of the ordering is that the leading monomial of an NP `p` is just `p[1][1]` and that its leading coefficient is `p[2][1]`.

#### 2.2 Noncommutative Polynomials for Modules (NPMs)

The format can be adjusted slightly to allow the use of a free right module over the algebra. The internal format of an element of the module is similar to that of a noncommutative polynomial, see 2.1. The only change is that each monomial will start with a negative number. The absolute value of this number is the index of the standard basis vector of the free module.

For example in a two-dimensional free F<< x_1, x_2, ..., x_t>>-module, `[[[-1]],[1]]` would represent `[1,0]` and `[[[-1,1,2],[-1,2,1],[-3,2,2,2]],[6,-7,9]]` would represent [6x_1x_2-7x_2x_1,0,9x_2^3]. The zero vector is the same as in 2.1 and the only one without a negative entry: `[[],[]]`.

Elements of modules will be printed as vectors. See for instance Examples A.20, A.22, and A.21 of Section A.1, on how to use modules.

#### 2.3 Core functions

The core function is `SGrobner` (3.4-2) (for Strong Gröbner, as we use the Strong Normal Form most of the time). It takes a list of NPs and, prepares two lists for a loopy treatment:

• first the list itself, called `G`. Before entering the loop, `G` is cleaned, ordered and its elements are made monic, that is, multiplied by a scalar so that the leading coefficient becomes one.

• second the list of all NormalForms wrt `G` of S-polynomials of elements of `G`. This list is called `todo` ('`D`' in the report), reminding us that we still need to compute the S-polynomials of these NPs (possibly with an element of `G`). If todo is empty then `G` is a Gröbner basis.

Then, the function calls the routine `GBNP.SGrobnerLoop` on the arguments G, todo which are changed in an attempt to modify `G` so that still

1. `G` generates the same two-sided ideal I as before.

2. `todo` contains all NormalForms wrt `G` of S-polynomials of elements from `G` that need to reduce to zero for the basis to be a Gröbner basis.

The importance of this feature is that, in case of huge computations, the user may store `G` and `todo` at almost any time and take up the computation by loading `G` and `todo` and using the `GBNP.SGrobnerLoop` whenever convenient. The only technical detail to handle is that the last element of the list `G` should be copied into the `todo` list.

Now the loop ends when the list `todo` is empty. As we referred to in the introduction (1.2), this may never happen. But if it does, then the work is essentially done. After some internal cleaning and a bit of further rewriting, the computation is over.

There is also a `Grobner` (3.4-1) function. It uses (at some places) the Normal Form instead of the Strong Normal Form algorithm. In most of our applications, this usually led to slower performance, so we are not very keen to use it.

In many of our own applications we often have finite-dimensional quotient algebras: the full polynomial ring modulo the two-sided ideal I generated by `G`. In such cases, one would like to know the dimension (whence the function `DimQA` (3.5-2), QA for Quotient Algebra), find a basis (whence the function `BaseQA` (3.5-1)), or just the monomials up to a certain degree that are not divisible by a leading term of `G` (whence the function `GBNP.NondivMons`). Actually by use of `MulQA` (3.5-7), you can even multiply elements of the quotient algebra. In case it is unknown whether the quotient algebra is finite or infinite, one can use the functions `FinCheck` (3.6-4), `DetermineGrowth` (3.6-2) and `DetermineGrowthObs` (3.6-3). When the quotient algebra is infinite dimensional you may want to determine its partial Hilbert Series. This can be done with the function `HilbertSeries` (3.6-5).

Rather than storing all obstructions, the Gröbner basis algorithm computes the (Strong) Normal Form of obstructions from `G` and puts them into `todo` whenever nonzero. At the beginning of the loop, we take the first element of the `todo` list and prepare it for addition to `G`. We are then concerned with two goals:

1. to restore the invariant properties,

2. to clean up G (that is, reduce it to a more succinct, shorter set).

This is mainly done by means of additional S-polynomial and Normal Form computations.

As for data management, we have used the facility to work with lists in situ, that is, not to copy the list but rather perform all operations on one and the same list. To this end we use operations like `RemoveElmList` and `Add`, see Reference: Add. The idea here is to economize on space for large computations. We haven't gotten here to the bottom of things, but have concentrated on the potentially biggest lists: `G` and `todo`.

For checking whether a monomial can be reduced, an internal tree structure is used.

#### 2.5 Tracing variant

When computing with small examples, it may be handy to provide the elements of the Gröbner basis with a way of expressing them as elements in `I`, that is, as combinations of elements of the input. This can be done, not only for elements of `G`, but for any element, by the functions in the file `trace.g`. This file calls the file `nparith2.g` for arithmetic keeping track of the expressions of polynomials as combinations of elements from the original basis. With respect to a given input basis `B`, a polynomial `p` in the traced version is a record with two fields. One field, called `p.pol`, is the usual NP. The other, called `p.trace`, is a list of elements indexed by `B`. Each element of `p.trace` is a list whose elements are four-tuples `[ml,i,mr,c]` where `ml` and `mr` are monomials, `i` is an index of an element of `B` and `c` is a scalar. The interpretation of this data structure is that `p.pol` can be written as the sum over all four-tuples `[ml,i,mr,c]` of c*ml*B_i*mr. Functions to print these expressions in a human understandable way are described in Section 3.7.

#### 2.6 Truncation variant

When computing with large and/or infinite examples, it may be handy to truncate everything above a certain degree. In fact, we encountered various examples where the polynomials are homogeneous and then it makes perfect sense to truncate the polynomials, that is, to disregard everything above a certain degree, as all S-polynomials the lower degree part of the Gröbner basis can be found without these. The functions of this variant can be found in Section 3.8.

#### 2.7 Prefix and Two-Sided (PTS) variant

Given an ideal I in a free noncommutative algebra A generated by a finite set G, and a positive integer s, we can work with the free right A/I module (A/I)^s. See 2.2 on how to represent vectors of (A/I)^s by elements of the free module A^s. Given a subset W of A^s, whose elements are called the prefix relations, let W' be the submodule generated by the image of W in (A/I)^s. The function `SGrobnerPTS` (3.9-4) can be used to determine the quotient module (A/I)^s/W'. If the algorithm terminates, the result can be used in `StrongNormalFormPTSNP` (3.9-5), a strong normal form computation, to find the canonical representative in A^s of an element in (A/I)^s/W'.

#### 2.8 Gröbner basis records

The function `SGrobnerPTS` (3.9-4) calculates a Gröbner basis consisting of some two-sided relations in the algebra and some prefix or module relations in the vector space. These are returned in a record `GBR`. The two-sided relations can be found under the name `GBR.ts` and the prefix relations under the name `GBR.p`. Some other information is stored in this record as well.

The prefix conditions are in NPM format (see 2.2), but the two-sided relations are not.

#### 2.9 Dimensionality of a quotient algebra

A number of functions are available to determine whether the quotient algebra of the ideal generated by a Gröbner basis is finite dimensional or infinite dimensional. A set of leading terms of the Gröbner basis needs to be constructed (using `LTermsNP` (3.3-6)). Such a set has the property that no monomial in it divides any other monomial in the set. The function `FinCheck` (3.6-4) determines whether the quotient algebra is finite or infinite dimensional. More generally, the growth of the quotient algebra can be determined by use of the function `DetermineGrowth` (3.6-2), which either states that the algebra is finite, or states that the algebra has polynomial growth, in which case it gives bounds for the degree of polynomial growth, or states that the algebra has exponential growth. Finally, with the function `HilbertSeries` (3.6-5) one can compute coefficients of the Hilbert series.

generated by GAPDoc2HTML