Mathematical Computations Using Bergman

Jörgen Backelin, Svetlana Cojocaru, Victor Ufnarovski

ISBN:91-631-7203-8

Mathematics

Centre for Mathematical Sciences

Lund University

Box118, SE-221 00 Lund, Sweden

http:/www.maths.lth.se/

1 A brief bergman tutorial
    1.1 Preliminaries
        1.1.1 Starting a bergman session
        1.1.2 Ending a bergman session
        1.1.3 What you need to know about Lisp syntax
    1.2 Simplest calculations in bergman
        1.2.1 Selecting alternatives
        1.2.2 Commutative algebras
        1.2.3 Non-commutative algebras
        1.2.4 Normal form and reduction
        1.2.5 Starting a new calculation
        1.2.6 Working safely in low degrees
        1.2.7 Some useful advises
2 Computations in bergman
    2.1 Introduction
    2.2 Bergman: philosophy and approach
    2.3 Bergman: main restrictions
    2.4 The polynomial ring set up
        2.4.1 Variable names and the flag raise
        2.4.2 Ordering
        2.4.3 Using eliminating ordering
        2.4.4 Matrix Ordering
        2.4.5 Coefficients: background
        2.4.6 Coefficients: choices
        2.4.7 Weights handling
        2.4.8 Rings exchange
    2.5 Homogenisation
    2.6 Choosing a strategy
    2.7 Input-output modes for the polynomials
        2.7.1 Commutative case
        2.7.2 Non-commutative case
    2.8 Calculating and using series
        2.8.1 Hilbert series computation
        2.8.2 Computation of Gröbner basis using known
Hilbert series
    2.9 The jumping rabbit
    2.10 Stability and Non-graded Algebras
    2.11 Some bricks to build your own procedures
    2.12 Modules over non-commutative algebras
        2.12.1 Gröbner basis for modules over
non-commutative algebras
        2.12.2 Hilbert series for modules over
non-commutative algebras
        2.12.3 The Anick resolution and Betti numbers for the tri -vi -al module
        2.12.4 Writing own procedures
        2.12.5 The Anick resolution and Betti numbers for a right module
        2.12.6 The minimal resolution and Betti numbers for a right module
        2.12.7 The Anick resolution and Betti numbers for right, two-sided ideals, and factor-algebras, considered as right modules
        2.12.8 Working with the left modules
        2.12.9 Betti numbers for two modules
        2.12.10 Calculating Hochschild homology of an algebra
    2.13 Bergman under Reduce
        2.13.1 Working in the Reduce syntax
        2.13.2 Parametric coefficients
    2.14 Debugging in bergman
    2.15 Customising bergman
    2.16 Computations in bergman under shell
        2.16.1 Problems of interface to bergman
        2.16.2 Shell overview
        2.16.3 Shell description
3 Bergman for the advanced user
    3.1 References
        3.1.1 Mode handling
        3.1.2 Sustained operating mode alternatives
        3.1.3 The mode designator tree structure
        3.1.4 The mode handling procedures
    3.2 Monomials and polynomials in bergman
    3.3 Controlling the calculations process
    3.4 The commutative Hilbert series procedures
    3.5 User available flags
    3.6 User available counters
4 Some useful appendixes
    4.1 Bergman proceedings extending
Standard Lisp
        4.1.1 Introduction
        4.1.2 Fast variant Standard Lisp extensions
        4.1.3 General Standard Lisp extensions
    4.2 Formal description of bergman
        4.2.1 Organisation of the programme source files
        4.2.2 Overview of the (main) units and source files
        4.2.3 Basic structures and naming conventions
        4.2.4 Global structures and programme outline
    4.3 Mathematical background
Index

Chapter 1
A brief bergman tutorial

"If easy of use was the only valid criterion

people would stick to tricycles and never

try bicycles".

D.Engelbart

1.1 Preliminaries

Bergman is a system for computations in commutative and purely non-commutative algebra. It is mainly developed by Jörgen Backelin (Stockholm University). Some additional facilities are implemented in the framework of a joint project "Non-commutative computer algebra" executed by the Department of Mathematics at the Stockholm University in collaboration with the Lund University and the Institute of Mathematics and Computer Science of the Academy of Science of Moldova in Chisinau. The project is supported by the Royal Swedish Academy of Sciences which is gratefully acknowledged.

We would like to express our sincere gratitude to the first project leader and a faithful bergman user Prof. Jan-Erik Roos.

We also thank other people participated the project since its beginning: Alexander Podoplelov who took part in the developing of Anick resolution component, Sergey Verlan who took part in the elaboration of the Common Lisp version. Our colleagues Alexander Colesnicov and Ludmila Malahova are working on the project starting with 1994. They have drawn up the Common Lisp version, the bergman site and programmed two versions of shell: the first one under MS DOS and the current one in Java. Section 2.16 in this book is written together with them.

Bergman is public domain software available from the following address http://servus.math.su.se/bergman. It is written in Standard Lisp, the Lisp dialect underlying Reduce implementation. An alternative Common Lisp version is also supported for some platforms.

In principle, bergman can be used on all platforms where Reduce, PSL, or CLISP are implemented. We have implemented it on:

MS Windows 95 and later (CLISP);
Linux on different machines (PSL, Reduce, CLISP);
Sun Solaris for Sparc and Sun Blade (PSL, Reduce, CLISP);
Dec Alpha under OSF and Linux (PSL, Reduce).

For detailed information about different versions of operating systems and Reduce or Lisp releases, see the installation guide.

Bergman is far from a full computer algebra system. However, it may be run under Reduce and in the commutative setting be treated as any Reduce module.

Using bergman one can compute both for ideals and right modules:

Gröbner basis
Hilbert series
Poincaré series
Anick resolution
Betti numbers

The last three features are destined to the graded non-commutative computations only.

One can find the description of bergman, including a demo version on its home page.

Of course, the demo version offers only limited possibilities, but you can try to solve your own problems.

Here we describe a version of bergman, installed under Reduce, and working in the Standard Lisp environment. In this installation the user can use both Reduce and Lisp syntax. Nevertheless most of the text is valid for other installations too. The Reduce-oriented syntax will be discussed in section 2.13.

For those who is unfamiliar with the Gröbner basis concept we refer to 4.3 for an elementary introduction in the subject.

1.1.1 Starting a bergman session

You can start a bergman session by typing bergman followed by Enter. When you are successful in starting the bergman session you will see a prompt. If the installation was under Reduce, the prompt (after some possible messages about memory and version) may look like:

Now you maybe want to switch to the Lisp-mode. (If you prefer to work in the Reduce-mode read section 2.13 instead.) For this you simply type end; and then press Return key. You will see a new Lisp-prompt:


Entering LISP ...

Bergman 0.984, 14-Dec-2004 

1 lisp>

(If your installation was without Reduce you are here from the very beginning). Of course, the date and the version can be different - it depends from the date when bergman was compiled on your computer.

Typically bergman will print a prompt such as

4 lisp >

at the beginning of the line you should enter. Whenever you see a prompt, bergman is waiting for you to enter new commands.

The Common Lisp version starts directly:

  i i i i i i i    ooooo    o        ooooooo   ooooo   ooooo 
  I I I I I I I   8     8   8           8     8     o  8    8
  I  \ `+' /  I   8         8           8     8        8    8
   \  `-+-'  /    8         8           8      ooooo   8oooo
    `-__|__-'     8         8           8           8  8
        |         8     o   8           8     o     8  8
  ------+------    ooooo    8oooooo  ooo8ooo   ooooo   8

Copyright(c) Bruno Haible,Michael Stoll 1992, 1993
Copyright(c) Bruno Haible,Marcus Daniels 1994-1997
Copyright(c) Bruno Haible,Pierpaolo Bernardi,Sam Steingold 1998
Copyright(c) Bruno Haible,Sam Steingold 1999

Welcome to the BERGMAN system.

[1]>

Now you are ready for computations: [1] > is the input prompt. Lately we will not distinguish PSL and Common Lisp version and will use the word Lisp for both of them.

1.1.2 Ending a bergman session

The command (quit) followed by the Return key, ends a bergman session.

Example. Here you finish the session.

10 lisp > (quit)
In Reduce syntax you omit the parenthesis but add a semicolon, thus:

10: quit;

An alternative solution on some platforms is to use Ctrl-D; holding down the Ctrl-key while pushing one or several times on key "D" will make quit. This may work in Reduce syntax, too.

1.1.3 What you need to know about Lisp syntax

The user should realise that bergman is a Lisp program and whenever (s)he starts bergman (s)he works under Lisp and in the Lisp notations. Here we describe the necessary minimum of Lisp syntax to deal with bergman in the simplest cases.

First of all, all commands should be written within parenthesis - see Example above.

It is important that uppercase and lowercase may be different in Lisp. One can use, for instance, only lowercase. Nevertheless in some situations, arising from mistakes, you leave bergman, but still need to leave Lisp. In this case (quit) not necessary ends the session and you need to use (QUIT) to do this. In the later version of Reduce the situation is opposite: you are able to use lowercase, but uppercase produces errors. Conclusion: try both in troubles!

Note also that a typical mistake is to forget one of the right parenthesis or quotes (" ). So maybe a couple of them might be useful to leave Lisp safely.

During the session you can get some kind of messages from Lisp. All of them start with stars. The message that starts from five stars ***** means an error. Three stars *** mean a minor error or only a warning - it is possible to continue the work.

Example. Here we forget to write the parenthesis.

2 lisp > simple
***** `simple' is an unbound ID
3 lisp >

Sometimes the output from garbarge collection can irritate the user. The comand (off gc) can help in this case.

1.2 Simplest calculations in bergman

Here we describe and explain several examples that you can easily copy and modify.

The simplest way to employ bergman is to start it, to use some specially written routines such as simple or ncpbhgroebner, to feed it input interactively or by means of an input file prepared in advance, and to quit.

In a slightly more sophisticated use, you may influence the behavior by various "mode changing" procedures.

In very sophisticated use, you may employ and expand the experimental procedures enclosed to the program, and/or interact directly with the underlying Lisp representations of the algebraic objects.

You also have access to all source code and can use all procedures to implement your own applications.

This chapter covers the first use. For more sophisticated use guidance see the next chapters.

1.2.1 Selecting alternatives

Bergman works in different modes. You can find a full overview of these in 3.1.

To perform some computations in bergman it is necessary at least to set up the polynomial ring selecting commutative or non-commutative alternative, ordering (degrevlexify or deglexify), coefficients field (characteristic 0, 2 or arbitrary prime), weights of variables etc.

For the first examples we skip the complete description of alternatives using the corresponding setting included in the main top level procedures. We shall distinguish here only commutative and non-commutative calculations.

1.2.2 Commutative algebras

Let us start with an example of Gröbner basis computation for an ideal. It will be performed by the procedure simple. There are several ways to call this procedure explained below. Here we illustrate two of them.

Calling simple without arguments one can introduce the relations directly from the screen following the prompt and respecting one restriction: the relations must be homogeneous. An example of the session follows:

1 lisp> (simple)
Now input in-variables and ideal generators in 
algebraic form, thus:
      vars v1, ..., vn;
      r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> vars x,y;x^2-y^2,x*y;
% 2
x*y,
   x^2-y^2,

% 3
y^3,

Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
2 lisp>

The result contains three elements of Gröbner basis : xy, x²−y², y³. Note that, according to the order of variables, x (the first in the list) is highest, so xx, xy and yyy are highest monomials. Thus, only the monomials 1, x, y, yy are normal (not divisible by the highest monomials) and serve as a basis of our algebra. Its dimension is equal to 4 and we can easily create a multiplication table too. (All elements of the Gröbner basis are equal to zero in the quotient algebra, so we can use their highest terms for the reduction of non-normal words). For example, x ·x=yy, y ·x=0, y ·yy=0.

As was said above, simple may be called in several ways. One of them is to perform input and output by means of files. Let us prepare the following one (suppose that its name is "test1.a". Check its existence in the directory bergman/tests and copy it into your current directory):

(algforminput)
vars x,y;
x*x−y*y, x*y;

The first line informs bergman that the succeeding lines are input data in the algebraic form. It means that you need to write multiplication symbol * or powers for example x^2 or x**2 instead of x*x but not xx (the same conventions as in Reduce or Maple). The other possibility is Lisp-form; read about them in the subsection 2.7.

The next two lines are the input data themselves. The first one contains variables, they should be written between keyword vars and semicolon. Then comes the defining relations, separated by commas and finished by semicolon.

To start the calculation select the name for output file, for example "test1.bg" (it should not exists!), start bergman, switch to the Lisp mode and write

(simple "test1.a" "test1.bg")

(do not forget double quotes!) and then quit.

The following is the full session of our work.

1 lisp> (simple "test1.a" "test.bg")
t
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
2 lisp> (quit)

Quitting

Here is the resulting file "test1.bg", containing Gröbner basis

% 2
x*y,
   x^2-y^2,

% 3
y^3,

Done

1.2.3 Non-commutative algebras

The procedure simple may be used to perform non-commutative Gröbner basis computations also. Bergman by default is in commutative mode, so, first of all we need to turn it to non-commutative calculations. Here is an example of the session:

2 lisp> (noncommify)
nil
3 lisp>  (simple)
Now input in-variables and ideal generators in 
algebraic form, thus:
      vars v1, ..., vn;
      r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> vars x,y;x^2-y^2,x*y;
% 2
x*y,
   -y^2+x^2,
   
% 3
x^3,
   y*x^2,
   
Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
4 lisp>

Although variables and generators look the same as in the commutative case, we have, of course, different output of Gröbner basis.

According to the order of variables, y (the last in the list - opposite to the defaults in the commutative case) is the highest, so xy, yy, xxx and yxx are the highest monomials. Thus only monomials 1, x, y, xx, yx are normal (do not contain the highest monomials as subwords) and serve as a basis of our algebra. Its dimension is equal to 5 and we can easily create a multiplication table too. (All elements of the Gröbner basis are equal to zero in algebra, thus we can use their highest terms for the reduction of non-normal words). For example, x ·x=xx, y ·y=xx, x ·xx=0.

In the non-commutative case the homogeneity restriction also must be respected (excepting "the jumping rabbit" strategy, see 2.9).

The input can be performed also by means of a file. Let us prepare the following one (suppose that its name is "test2.a". Check its existence in the directory bergman/tests and copy it into your current directory):

(noncommify)
(setmaxdeg 10)

(algforminput)
vars x,y;
x*x−y*y,x*y;

The first line switches bergman to the non-commutative mode. The second line is not necessary in this example. It restricts calculations up to degree 10. Here calculations stops in degree 3 (as you will see later), but in general Gröbner basis might be infinite so it is recommended to restrict the degree of calculations (although bergman will try to do them until the memory doesn't suffice).

The third line informs bergman that the following are the input data in the algebraic form. It means that you need to write multiplication symbol * or powers, for example x^2 or x**2 instead of x*x, but not xx (the same as in Reduce or Maple). Another possibility is Lisp-form; read about it in the section 2.7.

The next two lines are input data themselves. The first contains variables, they should be written between keyword vars and semicolon. Then the generators are listed, separated by commas and finished by a semicolon.

To start the calculation select the name for output file, for example "test2.bg" (it should not exist!), for example "test2.bg", start bergman, switch to the Lisp mode and write
(simple "test2.a" "test2.bg")
(do not forget double quotes!) and then quit.

The following is the full session of our work.

1 lisp> (simple "test2.a" "test2.bg")
nil
nil
t
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
2 lisp>

The file test2.bg contains the corresponding Gröbner basis:

% 2
x*y,
   -y^2+x^2,
   
% 3
x^3,
   y*x^2,

Done

Summing up our knowledges about the procedure simple we can describe it now in a more formal way.

Simple can be applied both in the commutative and noncommutative case. By default bergman works in the commutative mode. To turn off commutativity one need to call (noncommify)

To return to the commutative case one should call (commify)

Simple is called as a procedure with 0, 1, or 2 file names as arguments (file names being given in the explicit form.) If you give no argument, the procedure assumes that you want to give input on-line in "algebraic form" (see the section 2.7) and prompts you for this. If you give arguments, and the first one is the name of an existing file, this is read, and it is assumed that it (inter alia) contains the input (in one or another form). If file does not exist, the procedure works as if there were 0 names. Note, that if input file contains (noncommify) or (commify), the procedure will work in the corresponding mode (and save it after returning).

If there is a second argument, the output is put there. However, if there is an existing file with this name, it is NOT overwritten and the procedure informs you about its existence and finishs its work without doing something else.

There exists a related procedure stagsimple which works similarly, but it uses a different algorithm of calculations, namely the Staggered linear basis Algorithm With Substance (SAWS). It thus may only be used in the commutative case. It takes 0, 1, 2, or 3 arguments; the last two are for output of the SAWS. deduced Gröbner basis and for the reduced Gröbner basis, respectively. In some cases it works more efficient than simple.

In the next example we use another procedure, working with non-commutative algebras only and calculating besides the Gröbner basis of the algebra the Hilbert and Poincaré series for the corresponding monomial algebra (see 4.3).

There is no screen input, we should use files only. We can use the same test2.a for input and test2.bg for output (supposing that the output file does not exist. If there is such file in your current directory remove or rename it) and want to get two new files: test2.hs for the Hilbert series and test2.pb for the Poincaré series. The procedure has the name ncpbhgroebner (from NonCommutative Poincaré-Betti and Hilbert series) and it always has 4 parameters. Here is a session (messages can be different):

1 lisp>(ncpbhgroebner "test2.a""test2.bg""test2.pb""test2.hs")
*** I turn on noncommutativity
nil
10
nil
*** Function `degreeenddisplay' has been redefined

% No. of Spolynomials calculated until degree 2: 0
% No. of ReducePol(0) demanded until degree 2: 0
% Time: 425

% No. of Spolynomials calculated until degree 3: 2
% No. of ReducePol(0) demanded until degree 3: 0
% Time: 646

% No. of Spolynomials calculated until degree 4: 8
% No. of ReducePol(0) demanded until degree 4: 5
% Time: 833
*** Function `degreeenddisplay' has been redefined
nil
2 lisp>

The file "test2.hs" for Hilbert series looks now as:

+2*z^2
+0*z^3
+0*z^4

(note that the known from the very beginning part 1+2*z is absent here), and the file "test2.pb" for the monomial Poincaré series looks as:

+t^2*(2*z^2)
+t^3*(2*z^2+2*z^3)
+t^4*(6*z^3+2*z^4)

and also does not contain the first terms 1+t*(2*z).

Note also that neither series contains terms in degree more than 4 - the last degree where bergman have done some calculations. Look to the section 2.8.1 if you need more terms.

The file "test2.bg" is the same as "test2.bg" in the example with simple:


% 2
x*y,
   -y^2+x^2,
   
% 3
x^3,
   y*x^2,

Done

Now we give a formal description of this procedure.

Ncpbhgroebner always takes 4 arguments, which should evaluate to file names. The first file is the input file (which must exist). The second one will be the Gröbner basis output file. It must not exist before the call to ncpbhgroebner. On the third and fourth files the double Poincaré-Betti series and the Hilbert series of the associated monomial ring will be output. Existing files are overwritten. The output will be done degree by degree, whence you may read partial results while the calculations continue (and interrupt the calculations without losing the lower degree results). Note that the ring and its associated monomial ring have the same Hilbert series, while the double Poincaré-Betti series only fulfill a termwise inequality; due to the existence of a certain spectral sequence, the coefficients in the Poincaré-Betti series of the associated ring can never be less than the corresponding coefficients for the `true' ring.

A related procedure is ncpbh. The only difference with the previous one consists in the absence of output file for the Gröbner basis. So, the computations are the same, but it takes only 3 arguments.

1.2.4 Normal form and reduction

The main idea to use Gröbner basis is to have a possibility to reduce a given element u to its normal form. Bergman suggests a simple procedure named readtonormalform which interactively asks an input for a desired polynomial and prints its normal form - the result of the reduction. Let us consider a small example. Suppose that we want to check if two elements a³ and b³ commute in the non-commutative algebra A= < a,b|2a²−3b² > . The way to do it is the following:

A) Calculate Gröbner basis:


2 lisp> (noncommify)
nil
3 lisp> (simple)
Now input in-variables and ideal generators in 
algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> vars a,b; 2*a^2-3*b^2;
SetupGlobals
 ... done
+t^2*(z^2)
% 2
-3*b^2+2*a^2,

+t^3*(z^2+z^3)
% 3
-b*a^2+a^2*b,

+t^4*(z^3+z^4)
Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL),
     and run a new (SIMPLE).
nil
4 lisp>

B) Check the commutator a³*b³−b³*a³:


4 lisp> (readtonormalform)
algebraic form input> a^3*b^3-b^3*a^3;
is reduced to
2/3*(-a^4*b*a+a^5*b),
nil

We see that the result (the normal form of the commutator) is nonzero, so, the elements are not commuting. Moreover, we know exactly how far from zero the commutator is. The same computation with a⁴ and b² gives us a different result:

5 lisp> (readtonormalform)
algebraic form input> a^4*b^2-b^2*a^4;

is reduced to
0,

and we can conclude that those elements are commuting. More generally, the procedure readtonormalform can be used for the equality test: u=v in our factor-algebra if and only if their difference is reduced to zero.

To be able to use the normal form in his own programs one can apply the following procedures:

(readpol l), which reads the list l of polynomials from the input, separated by the semicolons,
(writepol l), which prints them on the screen,
(reducepol a b), which reduces the polynomial a to the (printable) polynomial b,
(printqpols b), which prints (printable) polynomial.

Note the difference between inner form of the polynomial, which normally is unprintable and external, printable form.

1.2.5 Starting a new calculation

We hope that your first experiments with bergman were successful and following the prompt after calculations you can:

kill bergman with (quit); or
interrupt bergman with ^Z ; or
clear the memory with (clearideal), and run a new (simple).

Presuming you would like to run a new computation let us explain more carefully what the function clearideal is doing.

According to its name it does not clear all that was done before, but only clear memory from the ideal generators and results of the previous calculations.

You always should call this function before starting a new cycle of the calculations. The only exclusion is when you want to add some new elements to the already calculated Gröbner basis or use the Gröbner basis for reduction, but for doing this kind of stuff you should be a professional. So, once again, in this chapter: before the calling at the second time one of the top-of-the-top procedures, such as simple, ncpbhgroebner always call clearideal (or clearring, see below.)

You need not do it from the very beginning, but you need to know what it really clears. It clears:

initial ideal generators,
calculated Gröbner basis,
all the memory, used for the calculations.

It saves:

all selected modes (see section 2.4), including list of input variables.

You can use this possibility: do not introduce the same set of variables, skipping vars ...

Example. Several computations in the same polynomial ring with different ideals.

 
1 lisp> (simple)
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input>  vars x,y,z;
algebraic form input> x^3, x^2*y-y^2*x, z^2*x, x^2*z-y^2*z;
% 3
x*z^2,
   x^2*z-y^2*z,
   x^2*y-x*y^2,
   x^3,
   
% 4
y^2*z^2,
   y^3*z,
   x*y^2*z,
   x*y^3,
   
Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
2 lisp> (clearideal)
nil
3 lisp> (simple)
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> y*z^2-z^3, x^2*z-y*z^2, x*y*z;
% 3
y*z^2-z^3,
   x*y*z,
   x^2*z-z^3,
   
% 4
z^4,
   x*z^3,
   
Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
4 lisp>

A more powerful function is clearring which clears also the list of input and output variables and their weights. Depending how you plan to continue calculations you can select one of the clearing functions.

Note that both of them do not clear all the selected alternatives, a part of settings being kept even after their applying. One can see how to avoid troubles caused by this situation reading the section 2.14.

1.2.6 Working safely in low degrees

It is supposed by default that a minimal degree where the user starts his calculations is at least 2. It gives some possibilities for the optimisation and, in fact, it is not a real restriction, because it is easy to remove linear relations decreasing the number of variables. But sometimes the user may have linear or constant terms in relations (e.g. to solve a system of linear equations or working in the non-graded case). For those cases there is a special mode, which can be achieved by long-named command (setsafelowtermshandling). To restore the the initial situation one can use the call (setquicklowtermshandling).

1.2.7 Some useful advises

Working in LISP the user can find some difficulties. A simple error as a forgotten parenthesis can lead to dramatical results with the message like

 
***** Segmentation Violation
Break loop
5 lisp break (1) >

Normally it means that the calculation was unsuccessful. Most probably the input was wrong, or was done in the wrong mode setting (e.g. wrong ring: trying non-commutative performance in the commutative situation). One can leave safely the break situation using Ctrl-D key and even try to call the procedure again in the correct mode (e.g. using (clearring) for clearing the ring and (noncommify) for making it non-commutative). Note that one can copy old inputs by mouse. It is a good idea to have inputs into a separate file - it can save time, because it is easier to copy lines from this file than from the previous lines.

When the volume of the calculations is really huge the system could finish the work with the message

 ``***** heap space low''

and in this case one may try to increase the memory for bergman. How to do it depends on platform. For example when the user calls bergman in Unix under PSL he uses in fact the following command inside

 exec /usr/.../bpsl -td 10000000 -f /home/.../bin/Linux_elf/bergman.img

(we skipped the current names of the directories). Copying the corresponding exe-file bergman to a new one (e.g longbergman) and changing −td 10000000 to −td 80000000 one can increase the memory 8 times! In Common Lisp the corresponding change will looks as a replacement of −m 50M to −m 400M (if the system allows such a memory).

Chapter 2
Computations in bergman

2.1 Introduction

In this section we suppose that the user is already familiar with bergman and is able to start and use it in the simplest cases. The aim of this section is to explain more detailed how to use bergman and to present all its facilities.

2.2 Bergman: philosophy and approach

The philosophy of bergman is to give the user a possibility to use Bergman's Diamond Lemma with a maximum flexibility. It means that bergman is mainly a powerful instrument for calculating Gröbner basis in several situations: commutative and non-commutative algebras, modules over them.

Besides that it provides some facilities to calculate appropriate invariants of the algebras and modules: Poincaré and Hilbert series, Anick's resolution and Betti numbers.

The aim is maximum efficiency with few restrictions. Note however the homogeneity setting. The user need not care how long the coefficients might be if (s)he wants to work over rationals, but should also have a possibility to work over prime characteristic or to include indeterminates as coefficients.

Nevertheless bergman is not a full computer algebra system. Rather it is a box, containing several useful routines, so it takes some efforts from the user to find them here and to use them in a correct way. Additional problems might appear because of the Lisp-oriented form of the procedures. But this box is not black: the user can read, modify the procedures and create its own. Moreover, (s)he can use them together with Reduce, so from this point of view, bergman can be considered as a Reduce package. (You can read more about this in section 2.13). The purpose of this chapter is to explain bergman as if it is a black box, describing all its main (unmodified) procedures.

2.3 Bergman: main restrictions

Bergman has two main restrictions. First, it is not a separate program and cannot be used without some underlying Lisp, like PSL or CLISP (or Reduce, which contains PSL). The second and important one, mentioned above, is homogeneity. All input to the simple top level procedures (excepting rabbit, see 2.9) must be homogeneous (e.g. by the natural grading, where each variable has degree one). They do not automatically check homogeneity. The possibility to use weighted variables extends the class of problems which can be solved by bergman: the degree function need not be a natural ("standard") grading.

There are some experimental procedures which under some restrictions test for homogeneity, homogenise input, and dehomogenise output; see the subsection 2.5 below.

In the commutative case homogeneity is not the principal restriction. It is not so difficult to homogenise relations to obtain the same, in principal, result. But for the non-commutative algebras this restriction is essential and this is the price for the efficiency. Unfortunately, it means that it is impossible to use bergman for the homological investigations of the groups or most of the finite dimension nontrivial idempotents. Nevertheless, using the rabbit strategy it is possible to calculate their Gröbner bases.

Note also that bergman has no routines for the polynomial factorisation. So, the applications of bergman to the solutions of the nonlinear systems of equations are sufficiently restricted.

2.4 The polynomial ring set up

To perform some computations in bergman you should set up the polynomial ring and its environment. This action includes selection of the algebra type (commutative or non-commutative), the variables, the ordering, the type of coefficients, and variable weights. One can also select the strategy of computation, and input-output mode. There are some minor mode selections too. For a complete description see section 3.1. This section contains an informal explanation of the most important components in the ring definition.

2.4.1 Variable names and the flag raise

We start from the variables - generators of our algebras (modules). Their names may be specified to almost any valid Lisp identifiers. (Some special signs, like * and ^, should not be used unslashified in the identifier names.) So, not only usual letters such as x,Y may be used, but also x1,Y45 or even I_kiss_you_a_1000_times can be used as a variable. But do not try x[1] or Y(2) as names! In any place you may have a look to your current list of variables using (getinvars).

Here is a possible example.

6 lisp> (getinvars)
(x y z)

One important question is if the names "y" and "Y" represent the same variable. The answer depends on the current value of the flag raise. If it is in the state OFF, they are different, otherwise (if it is in the state ON) "y"="Y".

The meaning of this flag is to translate all the letters to capitals (or the opposite case in the later versions). Next come several important notes, concerning this flag:

From the very beginning the value of this flag is ON. That is why you can write (SIMPLE) instead of (simple)
You may influence whether or not reading of variables and generators is case sensitive mode. Typing
(setcasesensalgin t)
you establish the case sensitive mode of algebraic input and by
(setcasesensalgin nil)
the mode is switched to no-case sensitivity.
Most the procedures, available to user have been written in source files using capital names. The procedures, intended to be unavailable to the normal user have been written with the names containing both small and capital letters, such as SecretProcedure. They will be unavailable because by the default flag raise is ON.
In the later versions of Reduce and LISP the situation is more complicated. Because flag raise works in the opposite direction now (decapitalizing instead of capitalizing), all the procedures written in capitals would be unavailable too. That is why in those versions a special converter is used to interchange lowercase and capital characters. So, for example, even if in the source files the procedure is written as (SIMPLE) it will have the name (simple) inside the bergman and will be available independent of the flag raise. The unpleasant effect of this is that such procedures as SecretProcedure can appears as sECRETpROCEDURE or even as s!E!C!R!E!Tp!R!O!C!E!D!U!R!E, but this ugly names we can see in the case of errors only (when the user is able to recover easy the original name the SecretProcedure).
More exactly, some procedures may turn OFF the flag raise while they are working. If a break loop (for example because of mistake) happens during their work the value of the flag will be OFF and, for example, you will be unable to quit from the program writing
(QUIT)
because in this case the name should be decapitalized:
(quit)
Another way to quit is
(on raise)
(QUIT)
If the user wants (e.g. for the debugging) to have access inside the bergman to the procedures and variables with the names, containing both small and capital letters, such as SecretProcedure (s)he needs to switch the flag raise OFF and use the names, where secret letters (capital in last version and lowercase in the older versions) are printed after exclamations: b!A!D. Even the multiplication in some versions is secret and looks as !*. But normally you don't need take care about this.

2.4.2 Ordering

In the commutative setting bergman can perform computations in three different orderings: lexicographical (DEGLEX) or reverse lexicographical ordering (DEGREVLEX, which is the default choice), and matrix ordering. We discuss matrix ordering later in section 2.4.4, and here we consider the first two ordering only. Both of them are graded, it means that first we compare length (or weights) of words and only after that use the lexicographical comparison.

For example, if x > y > z is our ordered alphabet, then we have

1 < z < y < x < zz < yz < yy < xz < xy < xx < . . .

in the commutative DEGLEX computation and

1 < z < y < x < zz < yz < xz < yy < xy < xx < . . .

in the commutative DEGREVLEX computation.

By default the DEGLEX ordering is chosen in the non-commutative bergman computation. Keeping the same ordered alphabet with x > y > z we have

1 < z < y < x < zz < zy < zx < yz < yy < yx < xz < xy < xx < zzz . . .

Besides that there exist two eliminating orderings in the non-commutative mode: ELIMLEFTLEX and INVELIMLEFTLEX. In the first one the words are compared first as commutative words in DEGLEX. If they are equal as commutative words they are compared as in non-commutative DEGLEX .

Keeping the same ordered alphabet with x > y > z we have

1 < z < y < x < zz < yz < zy < yy < xz < zx < xy < yx < xx < zzz . . .

In the INVELIMLEFTLEX the first comparison is as commutative DEGREVLEX, and if the words are equal as the commutative words they are compared as in non-commutative DEGLEX .

So the order will be:

1 < z < y < x < zz < yz < zy < xz < zx < yy < xy < yx < xx < zzz . . .

It is important for the Gröbner basis calculations which of the variables is the highest (largest). The rule is determined by the order of the variables, written after vars in one of the top-of-the-top procedures and is as follows:

in the non-commutative DEGLEX mode the last variable is always the highest;
in the commutative mode and both eliminating orderings first variable is the highest.

The following procedures set the corresponding orderings.

Ordering	Procedure
DEGREVLEX	REVLEXIFY()
DEGLEX	DEGLEXIFY()
	(commutative case)
	DEGLEFTLEXIFY()
	(non-commutative case)
ELIMLEFTLEX	ELIMORDER()
INVELIMLEFTLEX	INVELIMORDER()
MATRIX	MATRIXIFY
	(commutative case)

Note that the procedure deglexify works only in the commutative mode, in the non-commutative case DEGLEX ordering is established by the procedure degleftlexify.

2.4.3 Using eliminating ordering

Despite the fact that bergman works mainly with graded algebras, it can be successfully applied to the non-graded case. The idea is to homogenize the ideal (using an additional commuting homogenizing variable h) and to perform calculations in the eliminating ordering and then dehomogenise the result setting h=1.

Let us consider an example suggested by Prof. I.Kantor. Let A be the following algebra:

A = < r,l,q| r²−q²+lr−r,rq−qr+lq−q,lr−rl,lq+ql−2q,rr−rl−2lr+2l²−r+l >

It was important to find the minimal polynomial for q. Here is the solution achieved by bergman:

2 lisp> (noncommify)
nil
3 lisp> (elimorder)
nil
4 lisp> (simple)
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input>  vars r,l,q,h;
algebraic form input>  r*r-q*q+l*r-r*h,r*q-q*r+l*q-q*h,
algebraic form input>  l*r-r*l,l*q+q*l-2*q*h,
algebraic form input>  r*r-r*l-2*l*r+2*l*l-r*h+l*h,
algebraic form input>  r*h-h*r,q*h-h*q,l*h-h*l;

% 2
-h*q+q*h,
   -h*l+l*h,
   q*l+l*q-2*q*h,
   -h*r+r*h,
   -q*r+r*q+l*q-q*h,
   -4*r*l+2*l^2+l*h+q^2,
   4*l*r-2*l^2-l*h-q^2,
   4*r^2-4*r*h+2*l^2+l*h-3*q^2,

% 3
4*r*q*h-4*l^2*q+10*l*q*h-q^3-9*q*h^2,
   4*r*q^2+12*l^3-10*l*q^2-3*l*h^2-3*q^2*h,

% 4
l*q^3-3*l*q*h^2-q^3*h+3*q*h^3,
   -12*l^3*h-4*l^2*q^2+20*l*q^2*h+3*l*h^3-q^4-6*q^2*h^2,
   -4*l^3*q+12*l^2*q*h-11*l*q*h^2+3*q*h^3,
   12*l^4-8*l^2*q^2-3*l^2*h^2-2*l*q^2*h+q^4,

% 5
-48*l^2*q*h^2+96*l*q*h^3-q^5+10*q^3*h^2-57*q*h^4,

% 6
-48*l^2*q^2*h^2+96*l*q^2*h^3-q^6+10*q^4*h^2-57*q^2*h^4,

% 7
-q^7+13*q^5*h^2-39*q^3*h^4+27*q*h^6,

If we look at the last element of the obtained Gröbner basis and put h=1 we get the desired equation:

q⁷−13q⁵+39q³−27q=0

The secret is in the command elimorder: now if two words are compared, they are compared first as the commutative words in pure left lexicographical ordering and after that (if commutatively they are equal) as usual. That is why if the minimal polynomial exists its homogenized variant should belong to the Gröbner basis: if the leading monomial is qⁿ all other terms should contain the letters h and q only, h being in the end because it commutes with q. To obtain the minimal polynomial for l it is sufficient to put l before the homogenizing variable (which should remain the last) in the list of the variables, e.g. vars r,q,l,h;

2.4.4 Matrix Ordering

Using matrix ordering one can get all possible orderings in the commutative case. The idea is the following. Suppose we want to compare two monomials x_a=x₁^a₁…x_n^a_n and x_b=x₁^b₁…x_n^b_n. Let a=(a₁,…,a_n)^T and b=(b₁,…,b_n)^T be the corresponding column-vectors and M be an invertible n by n matrix. We say that x_a > x_b if the vector Ma is lexicographically larger than Mb. For example, if we want to compare x²y³z³ and x³y⁴z we consider a = (2, 3, 3)^T, b = (3,4,1)^T. Suppose that we have a matrix ordering defined by the matrix

⎛
⎜
⎜
⎜
⎝

−1

⎞
⎟
⎟
⎟
⎠

We have

Ma=

⎛
⎜
⎜
⎜
⎝

−1

⎞
⎟
⎟
⎟
⎠

⎛
⎜
⎜
⎜
⎝

⎞
⎟
⎟
⎟
⎠

⎛
⎜
⎜
⎜
⎝

⎞
⎟
⎟
⎟
⎠

; Mb=

⎛
⎜
⎜
⎜
⎝

−1

⎞
⎟
⎟
⎟
⎠

⎛
⎜
⎜
⎜
⎝

⎞
⎟
⎟
⎟
⎠

⎛
⎜
⎜
⎜
⎝

⎞
⎟
⎟
⎟
⎠

so x²y³z³ > x³y⁴z.

Note that the matrices

⎛
⎜
⎜
⎜
⎝

⎞
⎟
⎟
⎟
⎠

,M=

⎛
⎜
⎜
⎜
⎝

⎞
⎟
⎟
⎟
⎠

define orders DEGLEX and DEGREVLEX, respectively, but the identity matrix defines pure lexicographical ordering.

If the variables have weights (see section 2.4.7) we should naturally modify the vectors. For example, if the weights for x,y,z were 1, 2, and 3, respectively, we should use vector a=(2,6,9) for x_a=x²y³z³.

In bergman we can use the matrix order in the commutative mode using the command (matrixify). The matrix itself is described by the command (setordermatrix M), where M is a matrix, written as a list of vectors (rows). Here is an example of calculations using matrix order combined with the weights (compare order of monomials in input and output!):

4 lisp> (setweights 1 2 1)
nil
5 lisp> (setordermatrix  ((1 2 1) (0 -1 1) (3 -2 2)))
nil
6 lisp> (matrixify)
nil
7 lisp> (commify)
nil
8 lisp> (simple)
Now input in-variables and ideal generators in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, and r1, ..., rm the generators.
algebraic form input> vars x,y,z;
algebraic form input> x*y^3+y^3*z,
algebraic form input> 6*x^2*y^2+3*x*y^2*z+y^2*z^2+4*y^3;
SetupGlobals
 ... done
% 6
y^2*z^2+3*x*y^2*z+6*x^2*y^2+4*y^3,

% 7
y^3*z+x*y^3,

% 8
-x^2*y^3-y^4,

Done

2.4.5 Coefficients: background

Coefficients handling is an important part of bergman. Mathematically, the ring of coefficients should be a field K, the coefficient field. In basic bergman, this field must be a prime field; i.e., either the field Q of rational numbers, or the Galois field Z/ (p) of residue classes of integers with respect to a prime number p. The characteristic of Q is 0, and the characteristic of Z/ (p) is p, so that the prime field is completely determined by its characteristic.

If you run bergman under Reduce in commutative mode, then you have further possibilities, as it is described in the next subsection. In order to employ these, it is necessary to understand the way bergman treats coefficients.

In order to simplify the internal representation and thus make coefficient calculations faster, bergman tries to avoid fractions in coefficients, whenever feasible. This is done by means of the coefficient domain, associated polynomials, and gcd calculations.

The coefficient domain A should be a sub-domain of the coefficient field K, such that its field of fractions is K. (Here domain signifies integral domain, i.e., unitary commutative ring without non-trivial zero-divisors.) In the basic coefficient modes, A is the smallest possible sub-domain of K, so that A = Z = the ring of integers in characteristic 0, but A = K = Z/ (p) in positive characteristic.

Recall that if f = f(x₁,…,x_n) and g = g(x₁,…,x_n) are elements in R = K \mathopen[ x₁,…,x_n\mathclose], then f and g are associated polynomials if g = uf for some non-zero u ∈ K. (Then clearly f = u⁻¹g; and more generally, `associatedness' is an equivalence relation on R.) Since K is the field of fractions of A, each f ∈ R has associated polynomials with all their coefficients in A. We may e.g. write all coefficients of f as fractions of elements in A, and let u be the product of all the denominators; then clearly uf ∈ A \mathopen[ x₁,…,x_n\mathclose].

However, normally this is far from efficient. The coefficients in this uf often are extremely large (or complex). For A = Z, this may be avoided by factoring out the content of uf, i.e., the greatest common divisor of all the coefficients. Thus we get a new associated polynomial, hopefully with reasonably complex coefficients.

If g_i is associated to f_i for i = 1, …, r, then f₁,…,f_r and g₁, …, g_r generate the same ideal in R. Hence, if K = Q and all we want is to calculate a Gröbner basis, then we may always replace any appearing polynomial by an associated polynomial in Z\mathopen[x₁,…,x_n \mathclose] of content 1. In practice, it is more efficient to make such replacements dynamically during the calculation of normal forms. This is the default content taking strategy of bergman.

There are some situations when such tactics does not work, as when we want to calculate Anick resolutions. For these cases bergman also has a procedure normalform for calculating the true normal form of a polynomial.

2.4.6 Coefficients: choices

To select a coefficient field (and a coefficient domain) you call (setmodulus p) where either p is the desired characteristic (0 or a prime number), or p is sf (from "(Reduce) Standard Forms").

By default and after the call of (setmodulus 0), the coefficient field is the field Q of rational numbers, and the coefficient domain is the ring Z of integers. This means that all input coefficients and most internal and output coefficients are considered as integers. There are no restrictions for the length of the integers - only the restrictions of the memory of your own computer. Nevertheless, when you are sure from the very beginning that your coefficients (even inside the calculations) never will be too large (e.g. if the relations have a semigroup form: f−g, where f and g are words) you can try to achieve more efficiency using the flag nobignum - see the subsection 3.5 for more details.

However, if you want to perform series calculations, you should also decide whether or not the series coefficients may exceed the `small integer limit' of your Lisp implementation, before turning on nobignums.

You cannot use fractions in the input and do not ordinarily get them as output.

Another minor mode choice affecting the characteristic zero (and the sf) coefficient mode is the dense or sparse content taking.

After the call setmodulus p, where p is a prime number, the coefficient field and the coefficient domain both are Z/ (p) = GF(p), the unique field with p elements.

Note that in the prime characteristic the highest term of any polynomial in the Gröbner basis has always the coefficient 1 (in contrast to the zero characteristic case).

In odd prime characteristic with a reasonably small p, bergman employs efficient `small number calculations' only with the coefficients. If you need to optimise coefficient handling further, please note the following. With some hardware and software architectures, multiplication is a much more time consuming operation than are (single) additions and multiplications. In such cases, you should consider employing the modulus logarithms method . Mathematically speaking, it works by finding a generator γ for the cyclic multiplicative group of non-zero elements in Z/(p), and by representing such elements by their "γ-logarithms" (i.e., representing a = γ^s by s), whenever convenient.

The main effect of using the `modular logarithms mode' in typical bergman Gröbner basis calculations is that in the most time consuming combined coefficient operation, of the type

a ·b + c ,

one multiplication and one addition is replaced by two additions and one `logarithm table lookup operation', represented by finding an item in a Lisp vector (array). In addition, one Lisp remainder operation is replaced by one comparison and (in average) a half subtraction. The net effect is to replace one multiplication and one remainder operation by one addition, a half subtraction, one comparison and one `look-up'.

The draw-back is that bergman must construct or to read the `logarithm table' and the inverse `exponential table' into memory.

If you want to employ this, do

(setoddprimesmoduli modlogarithmic)

before you do the setmodulus p for your odd prime p.

When you do this, bergman may or may not succeed in finding a prepared file for the look-up tables; and if it doesn't find the file, it may or it may not succeed in creating the tables. In the present version, it is depending on being able to create the tables file, if this doesn't exist. Thus, you may run into troubles, e.g. if you do not have write access to the directory for modular logarithm tables handling. Some ways of overcoming this are discussed in the next chapter.

You need not this mode in characteristic 2 or 0, and should avoid it (possibly loosing a bit in time efficiency) if you want to save memory. By default, modular logarithms are off.

In addition to the few efficient basic coefficient modes available in bergman, there is a possibility to set up `your own' coefficient field and domain in an ordinary Reduce way. In this case, bergman calls Reduce for each coefficient operation. The domain elements are represented as Standard Forms, and the field elements as Standard Quotients. Similarly, the general Reduce Greatest Common Divisor procedure is employed for taking contents. Any reduction rules for calculating in Reduce are active, including Reduce modulus setting, but with the following exception: At input from Reduce, the variables specified as bergman in-variables are treated by bergman variable handling procedures.

In order to employ this, the user should have a good understanding both of the mathematics and of Reduce. It is entirely her/his responsibility to ensure that indeed the given in-coefficients reside in a mathematically well-defined field, with respect to the given Reduce rules.

Example: In order to calculate with coefficients in the field GF(169)(a) (where a is transcendent over GF(169)), you may note that GF(169) may be realised as a quadratic extension of its prime field GF(13), e.g., by means of √2. Thus, you might try

algebraic;

setmod 13;

on modular;

b^2 := 2;

and then go on as usual, employing the i+j*b (i,j ∈ {0,1,…,12}) as representatives for the elements in GF(169).

2.4.7 Weights handling

There are possibilities to handle some non-naturally graded situations, i.e., situations where not all variables have degree 1. Then the weights, i.e., the degrees of the variables, may be set to arbitrary positive integers. (Thus weight 0 is not allowed.) The degree of a monomial then will be calculated as the sum of the weights of its variable factors.

The natural grading corresponds to giving each variable weight 1. However, using the weighted variables mode could yield considerably slower calculations than using the natural grading mode. Thus weights should be set only if some of them deviate from 1.

Restrictions: For computational efficiency reasons, all degrees appearing during calculations are assumed to be "inums", i.e., small enough to fit into the small numbers representation of your computer. In the naturally graded situation, this is hardly ever a practical limitation; but if you give rather high weights to some variables, you could get into some trouble.

There are moreover some inconsistencies in the variable ordering in this version of bergman. Also, series calculation and the Anick resolution implementation are not yet compatible with the weighted variables mode.

The weight list contains the weights of variable 1, 2, 3, ... , in this order.

There are several procedures for weights handling in bergman.

(setweights int₁ int₂ ... int_n)
Sets the weights to int₁, ... , int_n. The int_i must be positive integers. No weights given restores the naturally graded mode.

(clearweights)
Restores the naturally graded mode. Returns the old weight list.

(getweights)
Returns the current weight list.

(printweights)
If weights are set, print these (with spaces between but without parentheses or line feeds) and return T. Else, print nothing and return NIL.

(setweightstoone)
Put weights 1 to all variables in the current list of variables.

Example of a Gröbner basis computation in a non-naturally graded situation:

1 lisp> (setweights 2  2 1)
nil
2 lisp> (getweights)
(2 2 1)
3 lisp> (simple)
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> vars x,y,z;
algebraic form input> x^3, x*z-y*z;
% 3
x*z-y*z,
   
% 6
x^3,
   
% 7
y^3*z,
   
Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
4 lisp>

2.4.8 Rings exchange

Normally bergman works with one fixed ring only. For some applications the user would like to have the access to several different rings (e.g. to compare two different normal forms of the same element).

For this purpose in bergman exists a stack of rings. Because only one ring is formally available, it is possible to save the current ring in this stack, perform the computations in a new ring and then restore the old ring from the stack. Here is the list of available procedures:

(pushring) saves the current ring on the top of the stack;

(popring) takes the ring from the top of the stack and makes it current;

(switchring) makes rings exchange: the top ring from the stack becomes a current and the current one becomes a top;

(ringstacklength) gives the length of the stack.

Here is an example of the session where we calculate the normal form of x² in two different commutative rings:

1 lisp> (simple)
Now input in-variables and ideal generators
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables,
and r1, ..., rm the generators.
algebraic form input> vars x,y;x^2-y^2;

% 2
x^2-y^2,

Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), and run a new (SIMPLE).
nil
2 lisp> (readtonormalform)
algebraic form input> x^2;

is reduced to
y^2,

nil
3 lisp> (pushring)
1
4 lisp> (clearideal)
5 lisp> (simple)
Now input in-variables and ideal generators
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables,
and r1, ..., rm the generators.
algebraic form input> vars x,y;x^2;
% 2
x^2,

Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), and run a new (SIMPLE).
nil
6 lisp> (readtonormalform)
algebraic form input> x^2;

is reduced to
0,
nil
7 lisp> (switchring)
t
8 lisp> (readtonormalform)
algebraic form input> x^2;

is reduced to
y^2,

nil
9 lisp> (popring)
1
10 lisp> (readtonormalform)
algebraic form input> x^2;

is reduced to
0,
nil

2.5 Homogenisation

Suppose we would like to find a minimal polynomial for α = √2+√3+√5, i.e. such a polynomial p(x) with the integer coefficients that p(α)=0.

One possible way to do it is to find a Gröbner basis for the following ring:

A= < x,y,z,t| xx−2,yy−3,zz−5, t−x−y−z >

The important thing is the choice of ordering. We want to get the element that contains the variable t only - it would be desired minimal polynomial. So the variable t should be the lowest, for example x > y > z > t. Even more - any power of t should be less than any monomial, containing any variable different from t. It means that we need pure lexicographical ordering. In such an ordering (for example pure revlex) we should have the following Gröbner basis:t⁸ − 40t⁶ + 352t⁴ − 960t² + 576,576z − 5t⁷ + 194t⁵ − 1520t³ + 2544t, 96y + t⁷ − 37t⁵ + 244t³ − 360t, 576x − t⁷ + 28t⁵ + 56t³ − 960t.

How to get from the bergman such a result? The problem is that bergman uses homogeneous relations only. The solution is to homogenize the relations, using a new variable (say f):

B= < x,y,z,t,f| x*x−2*f*f,y*y−3*f*f,z*z−5*f*f, t−x−y−z >

It means that every monomial that had less degree than highest one (constants in our case) was completed by corresponding number of factor f. The relations are now homogeneous and we can calculate the Gröbner basis in the corresponding ordering. Let us see the session:

1 lisp> (purelexify)
nil
3 lisp> (setalgoutmode alg)
nil
4 lisp> (algforminput)
algebraic form input> vars x,y,z,t;
algebraic form input> x^2-2, y^2-3, z^2-5, t-x-y-z;
t
5 lisp> (homogeniseinput)
*** Function `h!O!M!O!Gpm!O!N' has been redefined
nil
6 lisp> (groebnerinit)
nil
7 lisp> (groebnerkernel)
d!O!N!E
8 lisp> (algforminput)
algebraic form input> vars x,y,z,t,f;
algebraic form input> ;
nil
9 lisp> (bigoutput)
-x-y-z+t,
   z^2-5*f^2,
   2*y*z-2*y*t-2*z*t+t^2+6*f^2,
   y^2-3*f^2,
   2*y*f^2-3*z*t^2+6*z*f^2+t^3+4*t*f^2,
   y*t^2-7*z*t^2+12*z*f^2+2*t^3+12*t*f^2,
   4*z*t^3-t^4-20*t^2*f^2+24*f^4,
   -80*z*t^2*f^2+96*z*f^4-t^5+60*t^3*f^2+24*t*f^4,
   96*z*t*f^4-t^6+40*t^4*f^2-376*t^2*f^4+480*f^6,
   576*z*f^6-5*t^7+194*t^5*f^2-1520*t^3*f^4+2544*t*f^6,
   -t^8+40*t^6*f^2-352*t^4*f^4+960*t^2*f^6-576*f^8,
   
nil
10 lisp> (quit)

The reader can find some useful comments about the procedures used here in the section 2.11. Note that we used algforminput twice. The second one is necessary to create an (external) name for the homogenizing variable, otherwise printing of Gröbner basis is impossible. The ordering used here gives not exactly the same result as pure lexicographical ordering, but because t,f were the lowest variables we obtained our minimal polynomial.

2.6 Choosing a strategy

One of the important mode choice that should be mentioned is selecting the strategy of the calculations. Besides selecting of the algorithm (Buchberger, staggered or "the jumping rabbit" (see 2.9)) that you are doing by appropriate procedure, you have some influence on the intermediate calculation. Choosing

(setimmediatefullreduction t)

(and this is default) you demand immediate reduction of all the terms of Gröbner basis and obtain it in the reduced form. Sometimes it might be more efficient to switch OFF this flag. The obtained Gröbner basis may be not reduced, but calculations might be slightly faster. There is no clear receipts when it happens - try yourself!

2.7 Input-output modes for the polynomials

There are three basic output formats, named lisp (default), alg (synonim - Maple), and macaulay, corresponding to the formats, used in those 3 languages. The first two of these also are acceptable input formats. In all input and output, the polynomials are distributed (written with no parentheses). There is a difference between commutative and non-commutative case.

2.7.1 Commutative case

The (output) alg representation of the polynomial is

c₁*v₁^m₁₁* . . . *v_n^m_1n+ . . .+ c_r*v₁^m_r1* . . . *v_n^m_rn .

Here v₁, . . ., v_n stand for the variable names, m_ij for the exponents, and c_i for the coefficients. Highest terms will be printed first.

Occurrences of *v_i^0 and of ^1 are omitted. + is omitted before −. The macaulay representation is similar, but without * and ^; and the polynomials then are not separated by commata. In input, some slight variation is allowed in the alg format:

** may be used instead of ^;
Blank space may be inserted everywhere, except within identifiers or integers or between two successive ** .
Exponents 0 and 1 may occur.
The order of the variables in a monomial is arbitrary.

The lisp representation of the same commutative polynomial in n variables is a Lisp list of length n+1 lists of integers:

((c₁ m₁₁ . . . m_1n) . . .(c_r m_r1 . . . m_rn))

where the CAR of the i:th list is the coefficient of the i:th monomial, and the other n integers (which should be non-negative) are the exponents. Highest terms will be printed first in the output.

2.7.2 Non-commutative case

If you want to have output in alg or macaulay form, you must define in one or another way the variable names, and you must set the the output mode to alg or macaulay using the function variable setalgoutmode with corresponding arguments alg or macaulay. The variable names are most easily given by vars within a algforminput, as explained below. Moreover, many of the top-of-the-top bergman's procedures use algebraic output mode as default.

You may add your own algebraic output mode options by means of
addalgoutmode, as explained below.

One can inspect the current mode by getalgoutmode.

In order to perform alg mode input, write

(algforminput)

vars v1, ...,vn;

pol1, ... , pols;

where v1, ..., vn are the variable names and pol1, ..., pols are polynomials on alg form.

In order to perform lisp mode input, write

(lispforminput)

pol1 pol2 ..... pols

(lispforminputend)

where pol1, ..., pols are polynomials on lisp form. If you must specify the number of variables to a number n (as in the non-commutative case, if you want to know the Hilbert series), then set embdim to n. (embdim is short for "the embedding dimension".)

Lisp form (homogeneous) polynomial of degree d is a list of lists of integers of length d+1:

((c₁ m₁₁ . . . m_1d) . . . (c_r m_r1 . . . m_rd))

where the CAR of the i:th list is the coefficient of the i:th monomial, and the other n integers (which should be positive) are the "indices" of the variables, i. e., their position if they are ordered by increasing significance. The corresponding alg format is

c₁*v_m₁₁* . . .*v_{m_1d}+ . . . +c_r*v_{m_r1}* . . .*v_{m_rd} .

In input, identical factors may be collected to exponents. For example, if the variables are x,y, and z (in this order), then the lisp form polynomial ((5 1 1 1 3 2 2)) will be alg form output as 5*x*x*x*z*y*y, but it may optionally be input as 5*x**3*z*y^2. Highest terms will be printed first in the output.

To perform output in the desired form apply setalgoutmode with the corresponding argument (alg, macaulay or lisp.)

Comments:

Both algforminput parts, i. e., the input variable setting and the polynomial listing, are optional. You may thus give lisp form input, but perform algforminput vars v1,...,vn; ; (NOTE the double ;), in order to enable alg or macaulay output. Of course, if you try to print polynomials when the variables are not set, you are in trouble.
New successful (and non-empty) polynomial inputs replace old ones. Likewise, new successful input variable settings replace old ones. Running groebnerkernel (successfully) or clearideal kills the input polynomials, but not the variable settings.
The implementation of algforminput depends on specific PSL features, since the pure Standard Lisp has poor alternative scanning abilities. If algforminput should be disabled in some other implementation, and if you still wish to use algebraic output modes, then you must define the variable names in another way, using the internal representations. In bergman 0.9* and the next versions, the output variable settings performed by
vars x,y,z;
in the commutative case corresponds to
(setq O!u!tV!a!r!s (quote (!x !y !z)))
and in the non-commutative case corresponds to
(setq O!u!tV!a!r!s (quote ((1 . !x) (2 . !y) (3 . !z)))) .

2.8 Calculating and using series

2.8.1 Hilbert series computation

There is a simple way to calculate the Hilbert series in non-commutative case: using the top level procedure ncpbhgroebner. The previous chapter contains all the explanations concerning its calling, arguments and results. The only problem is that the Hilbert series computation is stopped in the degree where the computation of the corresponding Gröbner basis was finished. If you want to get the next power series coefficients you may continue computation and call two procedures:
(calctolimit degree)
(tdegreehseriesout degree)

Let us see an example. The file "test.a" should be the input file:

(setmaxdeg 10)
(setalgoutmode alg)
(algforminput)
vars x,y;
x*x-2*y*y;

Here is the corresponding session:


1 lisp>(ncpbhgroebner "test.a" "test.gb" "test.pb" "test.hs")
*** I turn on noncommutativity
nil
alg
t
*** Function `!O!L!D!D!E!D' has been redefined
*** Function `degreeenddisplay' has been redefined
%ufn malencie bucvi seichas 'degreeenddisplay'
% No. of Spolynomials calculated until degree 2: 0
% No. of ReducePol(0) demanded until degree 2: 0
% Time: 238


% No. of Spolynomials calculated until degree 3: 1
% No. of ReducePol(0) demanded until degree 3: 0
% Time: 289


% No. of Spolynomials calculated until degree 4: 2
% No. of ReducePol(0) demanded until degree 4: 0
% Time: 323

*** Function `degreeenddisplay' has been redefined
NIL
2 lisp> (calctolimit(getmaxdeg))
+t^5*(z^4+z^5)
+t^6*(z^5+z^6)
+t^7*(z^6+z^7)
+t^8*(z^7+z^8)
+t^9*(z^8+z^9)
+t^10*(z^9+z^10)
NIL
3 lisp> (tdegreehseriesout(getmaxdeg))
+6*z^5
+7*z^6
+8*z^7
+9*z^8
+10*z^9
+11*z^10
11
4 lisp>

The resulting files are:

test.gb:

% 2
-2*y^2+x^2,

% 3
-y*x^2+x^2*y,

test.pbs:

+t^2*(z^2)
+t^3*(z^2+z^3)
+t^4*(z^3+z^4)

test.hs:

+3*z^2
+4*z^3
+5*z^4

As you can see, all calculations by ncpbhgroebner are done up to the degree 4 - the last degree in which the Gröbner basis were done (though without generating a new element).

Calling
(calctolimit (getmaxdeg))
we obtain the continuation of Poincaré-Betti series and by
(tdegreehseriesout (getmaxdeg))
the next terms of Hilbert series are displayed (but not saved in the file!)

If you prefer the interactive input/output you can operate in the same manner with the procedure simple as it is illustrated in the following example:

1 lisp> (noncommify)
NIL
2 lisp> (setmaxdeg 10)
10
3 lisp> (simple)
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form (noncomm.) input> vars x,y;
algebraic form (noncomm.) input> x*x-2*y*y;

+t^2*(z^2)
% 2
-2*y^2+x^2,

+t^3*(z^2+z^3)
% 3
-y*x^2+x^2*y,

+t^4*(z^3+z^4)

Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
NIL
4 lisp>  (calctolimit(getmaxdeg))
+t^5*(z^4+z^5)
+t^6*(z^5+z^6)
+t^7*(z^6+z^7)
+t^8*(z^7+z^8)
+t^9*(z^8+z^9)
+t^10*(z^9+z^10)
NIL
5 lisp>  (tdegreehseriesout(getmaxdeg)) 
+3*z^2
+4*z^3
+5*z^4
+6*z^5
+7*z^6
+8*z^7
+9*z^8
+10*z^9
+11*z^10
11
6 lisp>

There are two ways to compute Hilbert series in the commutative case. The easy one (hilbert) we consider at the end of this section. The more complicated one will be useful to consider if the reader wants to understand how bergman is organized internally. For this method it is necessary to involve several procedures. First of all, it is necessary to input the ring ideal variables and generators calling algforminput and following its prompt (if it was not done before). You can start Gröbner basis calculation by means of two procedures: groebnerinit and groebnerkernel. Now the system is ready to compute Hilbert series.

There are two main uses for the Hilbert series facilities: stand alone and within the Hilbert series interrupt strategy minor mode. The interrupt strategy is very efficient and more sophisticated, you can find its explanation below (see sections 2.8.2,3.4).

Let us deal here with the first case. You may get the Hilbert series as a rational expression

p(t)

(1−t)^q

or with the power series coefficient for some specified t degree(s). The calculation is performed by procedure calcrathilbertseries. To see the result you should note that the global variables hilbertnumerator and hilbertdenominator represent a calculated

p(t)/(1−t)^q = (a_ntⁿ + a_n−1tⁿ⁻¹ + . . . +a₀)/(1−t)^q

by (the Lisp items) ((n . a_n) (n−1 . a_n−1) ... (0 . a₀)) and q, respectively.

To display the power series coefficients one may use the procedure
tdegreehseriesout giving the degree as argument.

Here is an example of Hilbert series computation.

1 lisp> (algforminput)
algebraic form input> vars x,y; x^3, x*y^2-x^2*y;
t
2 lisp> (groebnerinit)
SetupGlobals
 ... done
nil
3 lisp> (groebnerkernel)
d!O!N!E
4 lisp> (calcrathilbertseries)
nil
5 lisp> (setq p hilbertnumerator)
((4 . -1) (3 . -1) (2 . 1) (1 . 1) (0 . 1))
6 lisp> (setq q hilbertdenominator)
1
7 lisp>  (tdegreehseriesout 1)
2
8 lisp>  (tdegreehseriesout 2)
3
9 lisp>  (tdegreehseriesout 3) 
2
10 lisp> (tdegreehseriesout 4)
1
11 lisp> (tdegreehseriesout 5)
1
12 lisp> (tdegreehseriesout 6)
1
13 lisp> (tdegreehseriesout 7)
1
15 lisp> (groebnerfinish)

The obtained result presented as a rational function is the following:

1+t+t² −t³ − t⁴

1−t

The sequence of (tdegreehseriesout degree) displays the corresponding power series coefficients representing the series:

1+2t+3t²+2t³+t⁴+t⁵+t⁶+t⁷+ . . .

All the functions listed abowe are collected in the procedure hilbert destined to commutative Hilbert series computation reducing the manipulation to its call only. The previous example might be computed using this procedure:

1 lisp> (hilbert)
Input the maximal power series degree you want to calculate
1 lisp> 6
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> vars x,y;
algebraic form input> x^3, x*y^2-x^2*y;
% 3
-x^2*y+x*y^2,
   x^3,

% 4
x*y^3,

Hilbert series numerator:   +1*t^0+1*t^1+1*t^2-1*t^3-1*t^4
Hilbert series denominator:  1-t
Hilbert power series:        1+2t^1+3t^2+2t^3+t^4+t^5+t^6+...
Done

In this example both rational and power series are displayed. To avoid the last one it is necessary to input the maximal power series degree 0.

To perform the input from a file one should prepare it including the following lines:

(setmaxdeg 6)
(algforminput)
vars x,y;
x^3, x*y^2-x^2*y;

The corresponding call containing one input file and two output files - for Gröbner basis and Hilbert series - looks like:

(hilbert ``input_file'' ``output_gb_file'' ``output_hs_file'')

2.8.2 Computation of Gröbner basis using known
Hilbert series

It rather often happens that we know (at least partly) the Hilbert series before we start any computations. Bergman proposes an efficient optimisation of the Gröbner basis calculations in those cases. Here we learn us how to translate our knowledge about the Hilbert series to bergman. Let us consider a classical example.

Suppose that we want to calculate Gröbner basis of the following ideal (the corresponding system of equations, when z=1, has a proper name "6-cyclic roots system")

a+b+c+d+e+f,

ab+bc+cd+de+ef+fa,

abc+bcd+cde+def+efa+fab,

abcd+bcde+cdef+defa+efab+fabc,

abcde+bcdef+cdefa+defab+efabc+fabcd,

abcdef−z⁶;

It is not so difficult to calculate Gröbner basis of this ideal - it takes (on our computer) about 7.72 sec. From the literature we can find that Hilbert series of the corresponding factor-ring is equal to

1 +4t+9t²+15t³+20t⁴+22t⁵+19t⁶+ 11t⁷+t⁸−7t⁹−10t¹⁰−12t¹¹−10t¹²−5t¹³+2t¹⁵

(1−t)²

1 +6t+20t²+49t³+98t⁴+169t⁵+ 259t⁶+ 360t⁷+ 462t⁸+ 557t⁹+ 642t¹⁰+ 715t¹¹+

+778t¹² +836t¹³+ 894t¹⁴+ 954t¹⁵+ 1014t¹⁶+ 1074t¹⁷+ 1134t¹⁸+ 1194t¹⁹+ . . .

The following session shows how to calculate Gröbner basis in 3.3 sec - more than twice faster!


1 lisp> (setinterruptstrategy minhilblimits) 
nil
2 lisp> (sethseriesminima 1 6 20 49 98 169 259 360 462 557 642
  715 778 836 894 954 1014 1074 1134 1194)
t
3 lisp> (simple "sixroots" "sixroots.bg")
t
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
4 lisp>

Now some comments. In the first line bergman is informed that the strategy of the computations is changed - we want bergman to stop the calculations in the current degree d when the desired coefficient of the Hilbert series is achieved (in this degree). The next line describes coefficients themselves.

The idea is evident - we cannot get more nontrivial elements in this degree d (otherwise Hilbert series will be less then it was prescribed). The responsibility of the user is clear too - if the restrictions would be above the real coeffitient (for example, if we, by mistake, write 269 instead of 259 in the example above) the result of computations may be absolutely wrong. To avoid such a situation (for example, when we are not sure in the part of the coefficients) one can use nil instead of the numbers. This informs bergman that the calculations in this degree goes "as usual".

Another even more efficient application of this technique is skipping the Gröbner basis calculations in those degrees when they were preliminary done before. Suppose that after a 20 hours of calculations we get a Gröbner basis until degree 4 and saved it in a file. The next day we use this file (after minor changes) as input file but do not want to repeat calculation in the degree 4 or less. The solution is the line
(sethseriesminima skipcdeg skipcdeg skipcdeg skipcdeg skipcdeg)
(note that we used 5 skipcdegs, because the first degree is 0). Don't forget to precede this line by (setinterruptstrategy minhilblimits).

There is another (more advanced) way of doing it, employing a little Lisp programming (and that if the degree is - say - 15 instead of 5, then indeed this may be the point to start entering the more advanced phase). The actual programming might look like

(sethseriesminimumdefault (cond ((lessp hsdeg 5) skipcdeg)))

or like

(sethseriesminima (default (cond ((lessp hsdeg 5) skipcdeg))))

The complete information about the possibilities of using the function (sethseriesminima) the user should find in the section 3.4.

2.9 The jumping rabbit

In this section we discuss the possibilities to perform non-homogeneous calculations. Let A = < X|R > be an algebra we are interesting in and suppose that not all of elements of R are homogeneous. One possible way to get a Gröbner basis for A is to homogenize all the relations using the additional variable t and to calculate a Gröbner basis for another algebra B= < X,t|R_h,tx−xt, x ∈ X > , where R_h stands for the set of homogenized relations. After dehomogenising the obtained Gröbner basis for B by putting t=1. Though it works theoretically with some orders, which eliminates t, the problem is that even for the finite dimensional algebra A a Gröbner basis for B is usually infinite. The reason is that B is not the same algebra as C, which is obtained from A by homogenizing all the relations of A (not only the defining relations!) That is why a reduced Gröbner basis for B contains a lot of elements of the form ut^k, where u=0 in C but not in B. Therefore after the dehomogenization we get a Gröbner basis in A that is far from being reduced. Thus it is practically impossible to use this approach for computing the Gröbner basis even for finite dimensional algebras.

To solve this problem bergman suggests a special procedure rabbit which starts from A, homogenizes the relations getting B and then calculates a reduced Gröbner basis for C instead of B (more exactly, a part of it until the given degree maxdeg).

The trick is to cancel all obtained elements of form ut^k replacing them by u. This means that after finishing calculations in some degree m=degu and doing calculations in the degree m+k we need to jump back to degree m and restart the calculations beginning from this degree! That is why the program is named rabbit and takes three parameters, which permit jumping to be organized in a more or less regular manner. The parameters are startdeg, jumpstep and maxdeg. So, (rabbit startdeg jumpstep maxdeg) is a call of the procedure, which works as follows. First it suggests to input generators and relations in usual manner starting from vars. Second it homogenizes the input and starts to calculate a Gröbner basis degree after degree. When the degree becomes equal to the startdeg it prepares for jumping. It means that it collects all the elements of Gröbner basis which can be canceled by the homogenizing variable. When jumpstep degrees mostly are done the program checks if something was collected. If not, the next jumpstep degrees should be done before the next checking. If yes, the canceling is performed and the degree is reduced to the minimum degree of new obtained relations and the process continues in the same manner. It stops when maxdeg is achieved or when no new Gröbner basis elements can be obtained. In both cases the dehomogenization is performed and the result is printed, but in the first case a warning that the Gröbner basis may be wrong is displayed. Jumping during the process is always shown, but to display the intermediate homogeneous relations the program has to be run in the debug mode.

In the following example a Gröbner basis for the algebra A= < a,b,c|ab=c,bc=a,ca=b > is calculated:

2 lisp> (rabbit 2 2 8)
algebraic form input> vars a,b,c;a*b-c, b*c-a, c*a-b;
SetupGlobals
 ... done
RABBIT: Added step, Maxdegree=4
 Jump number 1

RABBIT: Jump number 2

RABBIT: Jump number 3

RABBIT: Added step, Maxdegree=6
 Jump number 4

GB is completely calculated
Rabbit have finished jumping. GB is 
a*b-c,
   b^2-a^2,
   b*c-a,
   c*a-b,
   -c^2+a^2,
   a^3-c*b,
   -a^2*c+b*a,
   b*a^2-a*c,
   b*a*c-a*c*b,
   -c*b*a+a*c*b,
   
nil

We see that the Gröbner basis is calculated completely and there are only 8 nonempty normal words: a,b,c,a²,ac,ba,cb,cba. One can conclude that a semigroup with our defining relations is in fact the quaternion group (because it has 8 elements and has those relations).

As a rule it is possible to apply rabbit with 0,1,2 or 3 parameters. The last case (with 3 integer parameters) corresponds to the example below. If no parameters are given, then the values of the "jumping variables" are set to 0,1 and 20 correspondingly. If there are 1 or 2 parameters they should be file names. The first (or the only) one is the input file, the second is destined to output. An input file may look like the following:


(setrabbit 2 2 8)
(algforminput)
vars a,b,c;
a*b-c, b*c-a, c*a-b;

where the first line sets the startdeg, jumpstep and maxdeg to 2,2 and 8 correspondingly applying the procedure setrabbit.

2.10 Stability and Non-graded Algebras

Starting from the version 1.0 there is another, in some cases more efficient (but not completely tested) possibility to make calculations in the non-graded algebras. Instead of homogenisation and reducing to the graded case bergman can perform calculations directly. But this demands some changes in modes. The main problem is that the leading monomials of the obtained Gröbner basis elements are unstable: we do not know if such a monomial will remain in the final Gröbner basis, because during the calculations we can get a new leading monomial of smaller degree which may be used to reduce it. This cannot happen in the graded case, which is why we then may relay on stability and do calculations more efficiently.

To inform bergman that the calculations are unstable the user has the procedure (setstability s) with one parameter s which has the value t if the calculations are stable and nil if not. There is a shorter call without parameter: (stabilise) and (destabilise) correspondingly.

Other aspects that should be taken into account concern degrees. First we probably need one call (setsafelowtermshandling) to save the possibility to work with linear or constant terms (if we have them in input. Second we cannot work degree-wise now (e.g. for output), because we normally do not know if we cannot get the element of the lower degree later. To take care about this the user should use call (setitemwise). Naturally the call (setdegreewise) restore degree-wise output (which is default value of this mode).

Here is an example for non-graded calculations:

2 lisp> (destabilise)
t
3 lisp> (setsafelowtermshandling)
quick
4 lisp> (setitemwise)
t
5 lisp> (simple)
Now input in-variables and ideal generators in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, and r1, ..., rm the generators.
algebraic form input> vars x,y,z; x*y-z, y*z-1;
SetupGlobals
 ... done
-z^2+x,
   y*z-1,
   x*y-z,
    - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), and run a new (SIMPLE).
nil
6 lisp>

2.11 Some bricks to build your own procedures

In this section we suppose that the user have already tried procedures, described above and want to write his own, involving Gröbner bases calculations. Bergman is an open system, you have access to its source code, you can use each of its procedures as useful items in your own applications. There is a three levels hierarchy of procedures:

the top-of-the-top level,
the top level,
the level of internal using.

Simple and ncpbhgroebner, for example, are top-of-the-top procedures, they solve completely some concrete problems - to compute Gröbner basis and series. But such procedures as algforminput, groebnerinit, groebnerkernel, groebnerfinish belong to the top level. The extended list of the top level procedures you can find in Chapter 3.

Users are recommended to use the procedures from the first two levels, if they would like to see how the last level looks like, they might read the source code.

Here we describe several procedures that can help you to perform your own calculations. The reader is already familiar with part of them and now we want to explain more carefully their functions.

The first thing that might be necessary is input. If the user wants algebraic form of input (instead of Lisp form) then the procedure algforminput should be used. You have see, above several examples of its using. Algforminput scans the succeeding input for variables list and/or polynomial list in algebraic form. If you type its call on the screen you get its prompt:


algebraic form input>

and the system is waiting for the input list.

If you perform the input from a file, you should put in this file the line: (algforminput) and vars... after that.

Gröbner basis calculations are organized in such a way that a user is able to include his own operators inside them. For this purposes they are divided into 3 separate procedures:

groebnerinit, that initiates numerous internal variables. It should be called after selecting modes and doing input.
groebnerkernel. Here the main calculations are performed. The results of calculations are saved in several variables and files (see section 4.2.4). You can use them in your own procedures.
groebnerfinish. This procedure closes all files and restores variables and flags.

The user can include his code between those three procedures (see section 2.8.1 as example of such the inclusion).

There exists another way which demands less knowledge in the Lisp programming. The user has a possibility to have some minor influence on computations or displaying the result using custstrategy or custdisplay mode. To do this simply write (setcuststrategy t) or (setcustdisplay t) changing the corresponding mode (see 3.1).

After that the user has a possibility to write (or, better to say, to rewrite) several own procedures to change the strategy of the calculations or the displaying of the result. We refer to the section 2.15 for complete list of the procedures and here consider only one of them - degreeenddisplay. This top level procedure will be called immediately after the ending of the calculations in the current degree and exactly here we should "explain" to the computer what we would like to have as output.

Of course, the most natural way to do it is to take the existing template procedure which looks as

(DE DEGREEENDDISPLAY () 
 (PROGN 
    (DEGREEOUTPUT) 
    (TERPRI)
    (PRIN2 "% No. of Spolynomials calculated until degree ")
    (PRIN2 (GETCURRENTDEGREE)) (PRIN2 ": ")  
    (PRINT NOOFSPOLCALCS)
    (PRIN2 "% Time: ") (PRINT (TIME))
))

If you have some difficulties to understand it (e.g. PRIN2 and TERPRI are some of the Lisp printing procedures) you can find the explanation using index at the end of the book. But maybe it will be easier when you will see the example below. Suppose, we want to print the leading monomials instead of the Gröbner basis elements. It is sufficient to replace the procedure degreeprintout, which prints all Gröbner basis elements by the existing procedure degreelmoutput which prints the leading monomials only.

You can write it directly (or better in a separate file, suppose its name is "mydisplay"):

(DE DEGREEENDDISPLAY () 
  (PROGN 
     (DEGREELMOUTPUT) 
     (TERPRI)
     (PRIN2 "% No. of Spolynomials calculated until degree ")
     (PRIN2 (GETCURRENTDEGREE)) (PRIN2 ": ")  
     (PRINT NOOFSPOLCALCS)
     (PRIN2 "% Time: ") (PRINT (TIME))
))

Now we do our usual calculations. We use dskin to skip copying the file.

1 lisp> (setcustdisplay t)
nil
2 lisp> (dskin "mydisplay")
*** Function `degreeenddisplay' has been redefined
degreeenddisplay
nil
3 lisp> (simple)
Now input in-variables and ideal generators
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables,
and r1, ..., rm the generators.
algebraic form input> vars x,y;x*x-y*y,x*y;
SetupGlobals
 ... done
% 2
x*y
x^2


% No. of Spolynomials calculated until degree 2: 0
% Time: 30

% 3
y^3


% No. of Spolynomials calculated until degree 3: 1
% Time: 30

Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), and run a new (SIMPLE).
nil

One can see we get the leading monomials only, as desired, time and the number of S-polynomials.

2.12 Modules over non-commutative algebras

In the previous sections we have described how to work with the ring (more exactly with the algebra over a field K) both in the commutative and non-commutative cases. In this section we restrict ourselves to non-commutative algebras only and will study modules over such algebras, and their homological properties.

Let A be a non-commutative algebra and M be a right module M over A. Bergman does not consider the module M as a special structure. Instead bergman works with a larger ring, that has as a generators set the union of the generators for A and M and as the set of the relations the union of the relations. This ring mathematically can be considered as the A⊗T(M), where T(M) is the tensor algebra

T(M)=K⊕M⊕M⊗M+ M⊗M⊗M+…,

and the multiplication is given by

(a⊗m₁…⊗m_r)·(a′⊗n₁…⊗n_s) = a⊗m₁…⊗m_ra′⊗n₁…⊗n_s.

It is important to understand how to extract the information from this extended ring to obtain the necessary results about the module M. We use mainly mathematics and partly some programming tricks to do this. But we still are working with the ring (though large). Nevertheless the computations of the Anick resolution are different in different cases and the user will get the warning about the changing mode from RING to MODULE, or TWOMODULES. All the procedures we describe below do changes automatically and those modes are important for Anick calculations only.

The structure of the section is the following. First we describe how to get Gröbner basis and Hilbert series for modules. Then the Anick resolution will be introduced and will be explained how to calculate Betti numbers for algebra A (i.e. dimensions B(i,j)=dimTor^A_i,j(K,K) in homological degree i and degree j). Betti numbers can be printed in two forms - ordinary B(i,j)=… and so-called Macaulay form, i.e. in matrix form C, where C(k,l)=B(l,k+l). We do not loose any information because B(i,j)=0 if j < i.

Using Anick resolution for the extended ring we will extract Anick resolution and Betti numbers for the right module (i.e. B(i,j)=dimTor^A_i,j(M,K) and will show how to proceed with the right ideals, two-sided ideals, factor-algebras (considered as right modules) and how to work with this for left modules.

Then we consider the most general case B(i,j)=dimTor^A_i,j(M,N). Since this employs the computer resources maximally, it should not be used in the previous cases (although of course this can be done).

At last we will show how to calculate the Hochschild homology of an algebra.

2.12.1 Gröbner basis for modules over
non-commutative algebras

To obtain a Gröbner basis for a right module M over a non-commutative algebra A it is sufficient to calculate the Gröbner basis for the extended ring. In other words, one needs to input the union of the set of variables and a set of generators for M (considered as a right module) and all algebra and module relations (in any order). What we get is the set that is the union of two Gröbner bases - one for the algebra and one for our module. To distinguish them we need only to check the presence of a module variables. If an element contains a module variable (it should be on the first place if it was a right module and on the last if it was a left module) then the element belongs to the module Gröbner basis. Let us consider an example. Suppose we want to calculate a Gröbner basis for the right module M= < a,b|ax−by > over the algebra A= < x,y|x²−y² > . We can do it (after the switching to the non-commutative mode), for example, with the help of the procedure simple (note the order we used in variable names - we want x be larger than y and a larger than b).

2 lisp>  (noncommify)
nil
3 lisp> (simple)
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables,
 and r1, ..., rm the generators.
algebraic form (noncomm.) input> vars y,x,b,a;x*x-y*y,a*x-b*y;
+t^2*(2*z^2)
% 2
x*x-y*y,
   a*x-b*y,
 
+t^3*(2*z^2+2*z^3)
% 3
x*y*y-y*y*x,
   a*y*y-b*y*x,
 
+t^4*(2*z^3+2*z^4)
Done

What we get are two Gröbner bases: one for the algebra:

xx−yy,xy²−y²x

and another for the module:

ax−by,ay²−byx.

Now we can construct a K−basis for M, which consists of the normal words, containing a or b on the first place and only algebra variables after them, i.e.:

a,b; ay, bx,by; ayx,bxy,byx,byy; ayxy,bxyx, byxy, byyx,byyy;…

and we can even calculate the Hilbert series:

H_M(t)=2t+3t²+4t³+… =

2t−t²

(1−t)²

Unfortunately we do not get the correct Hilbert series if we will try to use the procedure ncpbhgroebner - instead we get the Hilbert series for the extended ring R. But knowing it and the Hilbert series for algebra A one can obtain the Hilbert series for M using the formula

H_R=H_A

⎛
⎝

1−H_M

⎞
⎠

But if the user needs a Hilbert series he can apply a procedure that uses this formula and is described in the following section.

2.12.2 Hilbert series for modules over
non-commutative algebras

It is possible to calculate both Gröbner basis and Hilbert series for finitely-presented (right or left) modules. Gröbner bases and Hilbert series computations for modules are performed by the top level procedure modulehseries. It is necessary to input:

the maximal degree of computation,
the number of module variables,
the list of the algebra and module variables, (the algebra variables should be at the beginning of the list),
the algebra relations (more exactly - ideal generators, because instead of the relation r_i=0 we input r_i itself.)
the module relations.

The input/output may be performed from the screen or by means of files. Depending of this the procedure call may contain 0, 2, 3 or 4 parameters.

Interactive input/output.

It is the simplest way to start the computations. You should type only: (modulehseries)

In this case a dialogue is initiated. The user is asked to input:

the maximal degree of computation,
the number of module variables,
the list of the algebra and module variables (the algebra variables should be at the beginning of the list) and the ideal generators,

Receiving this data the Gröbner basis for ideal is calculated and user is asked to input

the module relations.

Here is an example of computations over modules:

2 lisp> (modulehseries)
*** Function `modulehseries' has been redefined
*** We turn on noncommutativity
Input the Maximum Degree you want to calculate
2 lisp> 4
Input the number of module generators
2 lisp> 2
Now input ALL ring and module variables but ONLY
the ring ideal generators in algebraic form, thus:
      vars v1, ..., vn;
       r1, ..., rm;
where v1, ..., vn are all the variables, 
and r1, ..., rm the generators.
algebraic form (noncomm.) input> vars x,y,a,b;
algebraic form (noncomm.) input> x*x-y*y, x*y;
+t^2*(2*z^2)
% 2
x*y,
   -y^2+x^2,
   
+t^3*(2*z^2+2*z^3)
% 3
x^3,
   y*x^2,
   
+t^4*(6*z^3+2*z^4)
+14*z^2
+48*z^3
+168*z^4
Now input ONLY the module relations, 
thus:    r1, ..., rm;
where  r1, ..., rm are the module relations.
algebraic form (noncomm.) input> a*x-b*y;
+t^2*(3*z^2)
% 2
-b*y+a*x,

+t^3*(3*z^2+3*z^3)
% 3
b*x*x,

+t^4*(9*z^3+3*z^4)
Done
+13*z^2
+40*z^3
+127*z^4

Here is (1-H)^(-1) for the Hilbert series H of the module

 +1
 +2*t^1
 +7*t^2
+22*t^3
+69*t^4
Here is the Hilbert series H of the module
+2*t^1
+3*t^2
+2*t^3
nil
3 lisp>

Input from a file - output on the screen

In this case you should type the procedure call with two parameters, which are names of existing files.
(modulehseries < file1 > < file2 > )

The file < file1 > should contain:

the maximal degree of computation defined by
(setmaxdeg degree)
the number of module generators defined by
(setq nmodgen number)
the procedure call to process the list of variables presented in algebraic form:
(algforminput)
the list of the algebra and module variables (the algebra variables should be at the beginning of the list). To input them it is necessary to write (without brackets!):
vars v₁, ... , v_n;
r₁,...,r_n;

where v_i are the algebra and module variables, r_i are the ideal generators only. Note that the items are separated by commas and every list is ended by semicolon.

Besides the above mentioned strings this file may contain flags and variables setting etc. according to bergman common rules explained above and in the next chapter.

The file < file2 > should contain:

the procedure call to process the list of variables presented in algebraic form:
(algforminput)
the module relations:
m₁,...,m_n;

The file "tesths1" is an example of < file1 > :

(setmaxdeg 16)
(setq nmodgen 2)
(algforminput)
vars z,y,x,b,a;
x*x, x*y+z*x;

and the file "tesths2" is an example of < file2 > :

(algforminput)
a*x*y-b*y*y+14*b*z*z,
a*z*z*z-b*x*z*y;

Errors messages.

If there was only one parameter in the parameter list it yields the following message:
***It must be two input files.
Input data from keyboard
and the system will turn to the interactive input/output mode.

If some file name is not a name of an existing file it yields the following message:
***Input file must exist
Input data from keyboard
and the system will turn to the interactive input/output mode.

Input from the files - output to one or two files

In this case the procedure call contains three or four parameters and looks like
(modulehseries < file1 > < file2 > < file3 > < file4 > )

The first two are input files and should respect all the rules mentioned above. The third parameter is a file to output Gröbner basis, the fourth is destined for Hilbert series output. If the last parameter is absent only the Gröbner basis will be printed in the file. Independently of the number of parameters, the resulted Gröbner basis and Hilbert series always are displayed on the screen (in the two last cases the output is performed simultaneously in files and on the screen). If the output file is one of the existing it will be overwritten without some warning message.

Errors messages.

If the name of the third file is incorrect (it is not a quoted string), it yields the following message:
***Incorrect output file.
Do you agree to use the file outf mgb as output?
Type Yes or No
and the system will be switched to waiting of input.

If your answer is Y (it means "Yes") the following message will be displayed:
outf mgb is used as output file.
Don't forget to rename it after calculations!
and computing will continue using the file outf mgb as output file to print the resulting Gröbner basis.

If your answer is N ("Not") the following message will be displayed:
No output file. Program is cancelled
and bergman will finish its work.

If the fourth parameter is incorrect an analogous dialogue appears proposing to use the file outf mhs to output Hilbert series.

2.12.3 The Anick resolution and Betti numbers for the trivial module

The Anick resolution and the Betti numbers for K as a trivial module may be computed in the non-commutative case. Resolution and Betti numbers for an arbitrary right module over non-commutative ring are described in the subsection 2.12.5.

To perform the calculations it is necessary to apply the procedure anick

It is necessary to input:

the maximal degree of computation,
the list of the algebra variables,
the algebra relations.

The input/output may be performed from the screen or by means of files. Depending of this the procedure call may contain 0, 1 or 2 parameters.

Interactive input/output

This is the simplest way to start the computations. You should type only:
(anick)

In this case a dialog is initiated. The user is asked to input:

the maximal degree of computation,
the list of the ideal variables and relations.

Here is an example of computation:


2 lisp> (anick)
*** We turn on noncommutativity
Input the Maximum Degree you want to calculate
2 lisp> 4

Now input in-variables and ideal generators 
in algebraic form, thus:
     vars v1, ..., vn;
      r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> vars x,y; x*x+y*y+x*y+y*x;
The Anick resolution initialization...
B(1,1)=2
The Anick resolution initialization done.
+t^2*(z^2)
% 2
y^2+y*x+x*y+x^2,

Calculating the Anick resolution in degree 2...
B(1,1)=2
B(2,2)=1
    0   1   2
  +----------
0 | 1   2   1
1 | -   -
end of Calculations.
+t^3*(z^3)
Calculating the Anick resolution in degree 3...
B(1,1)=2
B(2,2)=1
B(3,3)=1
    0   1   2   3
  +--------------
0 | 1   2   1   1
1 | -   -   -
2 | -   -
end of Calculations.

Groebner basis is finite.
If you want to continue calculations until maximal degree
type (CALCULATEANICKRESOLUTIONTOLIMIT (GETMAXDEG))
nil
3 lisp> (calculateanickresolutiontolimit (getmaxdeg))
Calculating the Anick resolution in degree 4...
B(1,1)=2
B(2,2)=1
B(3,3)=1
B(4,4)=1
    0   1   2   3   4
  +------------------
0 | 1   2   1   1   1
1 | -   -   -   -
2 | -   -   -
3 | -   -
end of Calculations.
nil
4 lisp> (anickdisplay)
Printing the results ...
Printing is done.
nil
5 lisp> (quit)

The procedure prints in every degree new Gröbner basis elements and all Betti numbers both in ordinary and Macaulay form. Sometimes (when the Gröbner basis is finite) it finishes the calculations before the desired maximal degree is achieved. To continue the calulations the user can write the suggested line

(calculateanickresolutiontolimit (getmaxdeg))

(e.g. copying from the prompt). Of course the number (getmaxdeg) may be replaced by another one. All the intermediate results, if any, are printed on the terminal.

The procedure (anick) does not print the resolution itself, though calculates it. To print the resolution and Betti numbers into a file one should use the procedure (anickdisplay). It prints the outcoming resolution in the file which name is assigned to the variable anickresolutionoutputfile. If no file name is assigned the result by default will be printed in the file andifres.txt. Note that the assigment should be done before the call of (anick), for example as

(setq anickresolutionoutputfile "resolution.txt")

Another important note is that this file is impossible to see before it will be closed. In our example it was achieved simply by quitting bergman. You can see the computed resolution in the resulting file (andifres.txt by default) in your current directory.


D(0, x)=1.x
D(0, y)=1.y
D(1, yy)=y.y+y.x+x.y+x.x
D(2, yyy)=yy.y+yy.x
D(3, yyyy)=yyy.y+yyy.x
B(1,1)=2
B(2,2)=1
B(3,3)=1
B(4,4)=1
    0   1   2   3   4
  +------------------
0 | 1   2   1   1   1
1 | -   -   -   -
2 | -   -   -
3 | -   -

D(1, yy)=y.y+y.x+x.y+x.x means that there exists the only 1-chain - yy and the differential d₁ acts as

d₁: y²⊗1 → y⊗y+y⊗x+ x⊗y +x⊗x,

thus the sign "." means the tensor product (see more comments about the Anick resolution for example in [2],[23]).

To have a file input and screen output one should type

(anick < file1 > )

The file < file1 > should contain:

the maximal degree of computation defined by
(setmaxdeg degree). In fact this line may be omitted. In this case calculations will finish when the Gröbner basis will be completely calculated or be formally infinite (until there are enough resources).
the procedure call to process the list of variables presented in algebraic form:
(algforminput)
the list of the algebra variables and the list of the algebra relations. To input them it is necessary to write (without brackets!):
vars v₁, ... , v_n;
r₁,...,r_n;

where v_i are the algebra variables, r_i are the algebra relations. Note that the items are separated by commas and every list is ended by semicolon.

The following file"anick" is an example of < file1 > :

(setmaxdeg 4)
(algforminput)
vars x,y,a,b;
x*x-y*y, a*x-b*y;

To have a file input and file output for Gröbner basis one should type

(anick < file1 > < file2 > )

where < file2 > is an output file containing the corresponding Gröbner basis. Note that output file does not contain results related to the Anick resolution. For this purpose one should define before apply anick the corresponding output file by (setq anickresolutionoutputfile < file3 > ).

2.12.4 Writing own procedures

The procedures described above and later are sufficient to make different type of calculations of Betti numbers. Nevertheless the user can find their output inconvenient or insufficient. To give him a possibility to create without problem his own procedure we will describe in this subsection how the procedure anick is organized.

Inside this short procedure the reader can find the following important lines:

(setringobject) to switch to the RING mode,

(noncommify) to switch to the non-commutative mode and

(load anick) to load the corresponding binary file.

Those lines are mandatory.

As usual, doing non-commutative computations it is recommended to limit the process with some maximal degree. Thus the next procedure could be:
(setmaxdeg degree)

Two following flags are switched on:

(on calcbetti) - turns on the Betti numbers calculation mode. This flag is mandatory.
(on onflybetti) - informs the application to calculate Betti numbers after each degree of Gröbner basis is operated out. This allows to view Betti numbers degree by degree during the Gröbner basis computations.

Both switches can be set on by the only procedure (onflybetti value ), where value should have the value T to switch ON and NIL for OFF.

After that the user can call simple, which performs all the calculations, one can obtain now not only Gröbner basis, but the Anick resolution and Betti numbers also. But (s)he may also replace simple by the series of procedures, described in section 2.11.

One useful procedure is (calculateanickresolutiontolimit n) which invokes a method for calculation of the Anick resolution till the given degree n.

All the intermediate results, if any, are printed on the terminal. Here is an example of the session which explains how the procedure anick works.

2 lisp> (setringobject)
nil
3 lisp> (noncommify)
nil
4 lisp> (load anick)
nil
5 lisp> (setmaxdeg 4)
nil
6 lisp> (onflybetti)
nil
7 lisp> (simple)
Now input in-variables and ideal generators 
in algebraic form, thus:
        vars v1, ..., vn;
        r1, ..., rm;
where v1, ..., vn are the variables, 
and r1, ..., rm the generators.
algebraic form input> vars x;x*x;
The Anick resolution initialization...
B(1,1)=1
The Anick resolution initialization done.
+t^2*(z^2)
% 2
x^2,
Calculating the Anick resolution in degree 2...
B(1,1)=1
B(2,2)=1
    0   1   2
  +----------
0 | 1   1   1
1 | -   -
end of Calculations.
+t^3*(z^3)
Calculating the Anick resolution in degree 3...
B(1,1)=1
B(2,2)=1
B(3,3)=1
    0   1   2   3
  +--------------
0 | 1   1   1   1
1 | -   -   -
2 | -   -
end of Calculations.
Done
 - All is OK (I hope). Now you may (e. g.):
   - kill bergman with (QUIT); or
   - interrupt bergman with ^Z; or
   - clear the memory with (CLEARIDEAL), 
     and run a new (SIMPLE).
nil
8 lisp>

2.12.5 The Anick resolution and Betti numbers for a right module

It is possible to calculate Anick resolution and Betti numbers for a graded right module over non-commutative algebra. The computation is performed by the top level procedure modulebettinumbers. It is necessary to input:

the maximal degree of computation,
the number of module variables,
the list of the algebra and module variables (the algebra variables should be at the beginning of the list),
the algebra relations (more exactly - the corresponding ideal generators, but it will be convenient to call them relations to avoid in the future ambiguity in the interpretation of the word "generators")
the module relations.

The input/output may be performed from the screen or by means of files. Depending of this the procedure call may contain 0, 1 or 2 parameters.

Interactive input/output

It is the simplest way to start the computations. You should type only:
(modulebettinumbers)

In this case a dialogue is initiated. The user is asked to input:

the maximal degree of computation,
the number of module variables,
the list of the algebra and module variables (the algebra variables should be at the beginning of the list) and the algebra and module relations.

Here is an example of computations over modules:

1 lisp> (setq anickresolutionoutputfile  "resolution.txt")
"resolution.txt"
2 lisp> (modulebettinumbers)

*** We turn on the MODULE mode
*** We turn on noncommutativity
Input the Maximum Degree you want to calculate
2 lisp> 5
Input the number of the module variables
2 lisp> 1
Now input all ring and then all module variables.
Input  the ring ideal and module relations 
in algebraic form  thus:
      vars v1, ..., vn;
       r1, ..., rm;
where v1, ..., vn are all the variables, 
and r1, ..., rm the  relations.
algebraic form input>  vars x,a;x*x,a*x;
The Anick resolution initialization...
B(0,0)=1
The Anick resolution initialization done.
+t^2*(2*z^2)
% 2
x^2,
   a*x,

Calculating the module Anick resolution in degree 2...
B(0,0)=1
B(1,1)=1
    0   1   2
  +----------
0 | 1   1
1 | -
end of Calculations.
+t^3*(2*z^3)
Calculating the module Anick resolution in degree 3...
B(0,0)=1
B(1,1)=1
B(2,2)=1
    0   1   2   3
  +--------------
0 | 1   1   1
1 | -   -
2 | -
end of Calculations.

Groebner basis is finite.
If you want to continue calculations until the maximal 
degree type (CALCULATEANICKRESOLUTIONTOLIMIT (GETMAXDEG))
nil
3 lisp>  (CALCULATEANICKRESOLUTIONTOLIMIT (GETMAXDEG))
Calculating the module Anick resolution in degree 4...
B(0,0)=1
B(1,1)=1
B(2,2)=1
B(3,3)=1
    0   1   2   3   4
  +------------------
0 | 1   1   1   1
1 | -   -   -
2 | -   -
3 | -
end of Calculations.
Calculating the module Anick resolution in degree 5...
B(0,0)=1
B(1,1)=1
B(2,2)=1
B(3,3)=1
B(4,4)=1
    0   1   2   3   4   5
  +----------------------
0 | 1   1   1   1   1
1 | -   -   -   -
2 | -   -   -
3 | -   -
4 | -
end of Calculations.
nil
4 lisp> (anickdisplay)
Printing the results ...
Printing is done.
nil
5 lisp> (quit)

In this example the input is performed from the screen and, correspondingly, the result is displayed on the screen also. The computed resolution you can see in the file resolution.txt in your current directory. For this example it contains just:

D(0, a)=1.a
D(1, ax)=a.x
D(2, axx)=ax.x
D(3, axxx)=axx.x
D(4, axxxx)=axxx.x
B(0,0)=1
B(1,1)=1
B(2,2)=1
B(3,3)=1
B(4,4)=1
    0   1   2   3   4   5
  +----------------------
0 | 1   1   1   1   1
1 | -   -   -   -
2 | -   -   -
3 | -   -
4 | -

Note that in the case of Betti numbers computations the module generators are considered as zero degree elements. That is why the maximal degree which we have got for Betti numbers is one less than the maximal degree used in the Gröbner basis calculations.

To have a file input and screen output one should type

(modulebettinumbers < file1 > )

The file < file1 > should contain:

the maximal degree of computation defined by
(setmaxdeg degree). In fact this line may be omitted. In this case calculations will finish when the Gröbner basis will be completely calculated or be formally infinite (until there are enough resources).
the number of module generators defined by
(setq nmodgen number)
the procedure call to process the list of variables presented in algebraic form:
(algforminput)
the list of the algebra and module variables (the algebra variables should be at the beginning of the list) and the list of the algebra and module relations. To input them it is necessary to write (without brackets!):
vars v₁, ... , v_n;
r₁,...,r_m;

where v_i are the algebra and module variables, r_j are the algebra and module relations. Note that the items are separated by commas and every list is ended by semicolon.

Besides the above mentioned strings this file may contain flags and variables setting etc. according to bergman common rules explained above and in the next chapter.

The following file"bnmt" is an example of < file1 > :

(setmaxdeg 4)
(setq nmodgen 2)
(algforminput)
vars x,y,a,b;
x*x-y*y, a*x-b*y;

To have a file input and file output for Gröbner basis one should type

(modulebettinumbers < file1 > < file2 > )

where < file2 > is an output file containing the corresponding Gröbner basis. Note that output file does not contain results related to the Anick resolution.

2.12.6 The minimal resolution and Betti numbers for a right module

There is another alternative to calculate Betti numbers for a graded right module using a minimal resolution. As it is well known, it may be constructed with the help of iterating calculation of module syzigies. The corresponding internal procedure puresyzygies is described in the next chapter, it demands some knowledge from the user - see section 3.3. In this section we describe another more convenient procedure minr, which takes rings and module generators and relations as input and return the Poincare-Betti series, calculated with the help of the minimal resolution. The resolution itself is not printed. In some cases the minimal resolution is much more efficient than Anick resolution, especially when the minimal resolution is finite. But for some cases Anick resolution gives Betti numbers faster, so it is a good idea to test both.Note that they coincide in the case of monomial algebras.

So is possible to calculate Betti numbers for a graded right module over non-commutative algebra using the minimal resolution. The computation is performed by the top level procedure minr. It is necessary to input:

the maximal degree of computation,
the number of module variables,
the list of the algebra and module variables (the algebra variables should be at the beginning of the list),
the algebra relations,
the module relations.

The input/output may be performed from the screen or by means of files. Depending of this the procedure call may contain 0, 1, 2 or 3 parameters.

Interactive input/output

It is the simplest way to start the computations. You should type only:
(minr)

In this case a dialogue is initiated. The user is asked to input:

the maximal degree of computation,
the number of module variables,
the list of the algebra and module variables (the algebra variables should be at the beginning of the list) and the algebra relations,
the module relations.

Here is an example of computations:

2 lisp> (minr)
Input the Maximum Degree you want to calculate
2 lisp> 5
Input the number of module generators
2 lisp> 1
Now input ALL ring and module variables but ONLY
the ring ideal generators in algebraic form, thus:
      vars v1, ..., vn;
       r1, ..., rm;
where v1, ..., vn are all the variables, and r1, ..., rm the generators.
algebraic form input> vars x,y,a;x*x+x*y+y*x+y*y;
Now input  module elements:
algebraic form input> a*x,a*y;

*** We turn on the MODULE mode
SetupGlobals
 ... done

Current homological degree=2
Current Poincare-Betti series is
1t+2t^2z+1t^3z^2

Current homological degree=3
Current Poincare-Betti series is
1t+2t^2z+1t^3z^2+1t^4z^3

Current homological degree=4
Current Poincare-Betti series is
1t+2t^2z+1t^3z^2+1t^4z^3+1t^5z^4

Calculated Poincare-Betti series is
1t+2t^2z+1t^3z^2+1t^4z^3+1t^5z^4
nil
3 lisp>

In this example we calculate the Poincare-Betti series of a trivial module (where its generator a is assumed to have a degree 1) over the ring with one relations. The input was performed from the screen and, correspondingly, the results (both intermediate and final) are displayed on the screen also.

Note that in the case of Anick resolution module generators are considered as zero degree elements. That is why we have got Betti numbers shifted if we compare outputs for the same example.

If 0 is chosen as maximum degree the calculations will be done until it will be enough memory (if the Poincare-Betti series is infinite).

To have a file input and screen output one should type

(minr < file file2 > )

The file < file1 > should contain:

the maximal degree of computation defined by
(setmaxdeg degree). In fact this line may be omitted. In this case calculations will finish when the Gröbner basis will be completely calculated or be formally infinite (until there are enough resources). The same result gives (setmaxdeg 0)
the number of module generators defined by
(setq nmodgen number)
the procedure call to process the list of variables presented in algebraic form:
(algforminput)
the list of the algebra and module variables (the algebra variables should be at the beginning of the list) and the list of the algebra relations. To input them it is necessary to write (without brackets!):
vars v₁, ... , v_n;
r₁,...,r_m;

where v_i are the algebra and module variables, r_j are the algebra relations. Note that the items are separated by commas and every list is ended by semicolon.

Besides the above mentioned strings the first file may contain modes and variables setting etc. according to bergman common rules explained above and in the next chapter.

The file < file2 > contains the line (algforminput) followed by module relations and ended with the semicolon.

The following file"min1" is an example of < file1 > :

(setmaxdeg 8)
(setq nmodgen 1)
(algforminput)
vars x,y,z,a;x*y, y*x+z*z,x*x*z;

(algforminput)
a*x,a*y,a*z;

Mathematical Computations Using Bergman

Jörgen Backelin, Svetlana Cojocaru, Victor Ufnarovski

Contents

Chapter 1 A brief bergman tutorial

1.1 Preliminaries

1.1.1 Starting a bergman session

1.1.2 Ending a bergman session

1.1.3 What you need to know about Lisp syntax

1.2 Simplest calculations in bergman

1.2.1 Selecting alternatives

1.2.2 Commutative algebras

1.2.3 Non-commutative algebras

1.2.4 Normal form and reduction

1.2.5 Starting a new calculation

1.2.6 Working safely in low degrees

1.2.7 Some useful advises

Chapter 2 Computations in bergman

2.1 Introduction

2.2 Bergman: philosophy and approach

2.3 Bergman: main restrictions

2.4 The polynomial ring set up

2.4.1 Variable names and the flag raise

2.4.2 Ordering

2.4.3 Using eliminating ordering

2.4.4 Matrix Ordering

2.4.5 Coefficients: background

2.4.6 Coefficients: choices

2.4.7 Weights handling

2.4.8 Rings exchange

2.5 Homogenisation

2.6 Choosing a strategy

2.7 Input-output modes for the polynomials

2.7.1 Commutative case

2.7.2 Non-commutative case

2.8 Calculating and using series

2.8.1 Hilbert series computation

2.8.2 Computation of Gröbner basis using knownHilbert series

2.9 The jumping rabbit

2.10 Stability and Non-graded Algebras

2.11 Some bricks to build your own procedures

2.12 Modules over non-commutative algebras

2.12.1 Gröbner basis for modules overnon-commutative algebras

2.12.2 Hilbert series for modules overnon-commutative algebras

2.12.3 The Anick resolution and Betti numbers for the trivial module

2.12.4 Writing own procedures

2.12.5 The Anick resolution and Betti numbers for a right module

2.12.6 The minimal resolution and Betti numbers for a right module

Chapter 1
A brief bergman tutorial

Chapter 2
Computations in bergman

2.8.2 Computation of Gröbner basis using known
Hilbert series

2.12.1 Gröbner basis for modules over
non-commutative algebras

2.12.2 Hilbert series for modules over
non-commutative algebras