\section{Introduction} \label{sec:intr} In this section we suppose that the user is already familiar with {\bf 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 {\bf bergman} and to present all its facilities. \section{{\bf Bergman}: philosophy and approach} The philosophy of {\bf bergman} is to give the user a possibility to use Bergman's Diamond Lemma with a maximum flexibility. It means that {\bf bergman} is mainly a powerful instrument for calculating Gr\"{o}bner basis in the several modifications: commutative and non-commutative algebras, modules over them. Besides that it provides some facilities to calculate appropriate invariants of the algebras and modules: Poincar\'{e} and Hilbert series, Anick's resolution and Betti numbers. Main principals are maximum efficiency with minimum restrictions (except one -- homogeneity). User need not care how long might be coefficient if he wants to work over rationals, but should also have a possibility to work over prime characteristic or to include indeterminants as coefficients. Nevertheless {\bf bergman} is not a language. Rather it is a box, containing several useful routines, so it takes some efforts from the user to find them here and to use in a correct way. Additional problems might appear because of Lisp--oriented form of the procedures. But this box is not black: the user can read, change the procedures and create its own. Moreover, he can use them together with Reduce, so from this point of view, {\bf bergman} can be considered as a package for Reduce. (You can read more about this in section \ref{reduce}). The aim of this section is to explain {\bf bergman} as a black box, describing all its main procedures. \section{{\bf Bergman}: main restrictions} {\bf Bergman} has only two main restrictions. First, it is not a separate program and cannot be used without PSL (or Reduce, which contains PSL). The second, and important, as it was mentioned above, is HOMOGENEITY. All input to the simple top level procedures must be homogeneous (by the natural grading, where each variable has degree one). There is no automatic check of homogeneity. The possibility to use weighted variables permits to extend the class of problems which can be solved by {\bf bergman}. %There are some %experimental procedures which under some restrictions test for %homogeneity, homogenise input, and dehomogenise output; see the % sub-section \ref{homog} 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 {\bf bergman} for investigations of the groups or most of the finite dimension algebras (such as matrix algebras), everything that contains nontrivial idempotents. Note also that {\bf bergman} has no routines for the polynomial factorisation. So, the applications of {\bf bergman} to the solutions of the nonlinear systems of equations are sufficiently restricted. \section{The polynomial ring set up} \label{modes} To perform some computations in {\bf bergman} you should set up the \index{polynomial ring} polynomial ring and its environment. This action includes the variable and generators definition, \index{commutativity} commutativity or \index{non-commutativity} non-commutativity selection, \index{ordering} ordering, \index{characteristic} characteristic, \index{weights} weights. One can select also strategy of computation, and input--output mode. There are some minor mode selections too. For complete description see section \ref{refm}. This section contains an informal explanation of the most important components in the ring definition. \subsection{Variable names and the flag {\bf 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 $^,$ cannot 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\_ 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: \index{getinvars} {\bf (getinvars)} \begin{exm} \begin{verbatim} 6 lisp> (GETINVARS) (!x !y !z) \end{verbatim} \end{exm} One important question is if the names "y" and "Y" represent the same variable. The answer depend on the current value of the flag \index{raise} {\bf 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 the capitals. Important notes, concerning this flag: \begin{enumerate} \item From very beginning the value of this flag is ON. That is why you can write {\bf (simple)} instead of {\bf (SIMPLE)} \item Most the procedures, available to user have capital names. (In the later version of Reduce the situation is opposite: the user available procedures names are in lowercase characters.) Nevertheless several procedures turn OFF the flag while they are working. If 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 \index{quit} {\bf (quit)} because in this case the name should be capitalised: {\bf (QUIT)} Another way to quit is {\bf (ON RAISE)} {\bf (quit)} \item Note, that turning ON this flag you loose access to all the procedures and variables with the names, containing small letter, such as SecretProcedure. The idea is that they should be unavailable to the usual user, being absolutely internal and private. Nevertheless user can sometimes see their names, where small letter are printed after exclamations: S!e!c!r!e!tP!r!o!c!e!d!u!r!e. Even the multiplication is secret in this mode and looks as !*. But normally you need not care about this and turn OFF the RAISE flag. \end{enumerate} \subsection{Ordering} \index{ordering} \label{sec:ord} {\bf Bergman} can perform computations in two different orderings: \index{lexicographical ordering} lexicographical (DEGLEX) or reverse lexicographical \index{reverse lexicographical ordering} (REVLEX). 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 x*z*y > x*y*y + in the noncommutative mode % \item \verb+ y*z*z >x*y*z (=x*z*y) > x*y*y + in the noncommutative mode %\end{itemize} \subsection{Coefficients handling} \label{sec:field} \index{coefficients} Coefficients handling is one of the most important part of {\bf bergman}. To select a characteristic you need to call \index{setmodulus} {\bf (setmodulus p) } where p is desired \index{characteristic} characteristic. By default or after the call {\bf (setmodulus 0) } all the coefficients are considered as integers. There are no restrictions for the length of the integers - only 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 semigroup form: $f-g,$ where $f$ and $g$ are words) you can try to achieve more efficiency using flag \index{nobignum} {\bf *nobignum} - see subsection \ref{flags} about more details. You cannot use fractions in the input and never get them as output. So, the highest term of your Gr\"{o}bner basis elements may have a coefficient, even negative. You have also a possibility to select prime characteristic in the both variants - with bignums or without them. For example {\bf (on nobignum) } {\bf (setmodulus 2) } is a reasonable preparation if you plan to work over the field of two elements only. Nevertheless there is no possibility to work in the field other then $F_p$ inside {\bf bergman}. You can do it only under Reduce (see section \ref{reduce} for more details). Note that in the prime characteristic the highest term in the Gr\"{o}bner basis has always the coefficient 1 (opposite to zero characteristic). There is one important choice of the mode that you have in the prime characteristic. If you have sufficient memory on your computer or prime $p$ is not so large it is reasonable to put the following flag: \index{modlogarithms} {\bf (on modlogarithms)} The effect (after calling the {\bf (setmodulus Q) }) is to create in the subdirectory {\bf domains} the file with the first letter p, following the digits, representing the number Q (e.g. p37 for Q=37) or using existing one if it was already created. It provides efficient calculations of the products, using so-called logarithmic tables.% (see chapter \ref{MATH-APP} for more details.) You need not this flag in the characteristic 2 or 0, and can survive without it (loosing in the efficiency only) if you want to save memory. Note, however, that default value of this flag is {\bf off}. The most useful (but difficult) choice is selecting arbitrary form of the coefficients is possible under Reduce only and is described in the subsection \ref{reduce}. \subsection{Weights handling} There are possibilities to handle some non-naturally graded situations, i.e., situations where not all variables have degree 1. Then the \index{weights} 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. %The weights %information is saved internally in two structures. The %weight list is NIL in the naturally graded case, and else contains %the weights of variable 1, 2, 3, ..., in this order. The weight %dotted pair list explicitly combines variable numbers and variable %weights as dotted pairs (1 . weight_1) (2 . weight_2) ..., in this %order. There are moreover some inconsistencies in the variable ordering in this version of {\bf bergman}. Also, series calculation is not yet compatible with the weighted variables mode. The weight list contains the weights of variable 1, 2, 3, \ldots , in this order. There are several procedures for weights handling in {\bf bergman}. \index{setweights} {\bf (setweights $int_1$ $ int_2$ \ldots $int_n$)}\\ Sets the weights to $int_1$, \ldots , $int_r$. The $int_*$ must be positive integers. No weights given restores the naturally graded mode. % Returns the old weight list. \index{clearweights} {\bf (clearweights)} \\ Restores the naturally graded mode. Returns the old weight list. \index{getweights} {\bf (getweights)} \\ Returns the current weight list. %Caution: Do not manipulate this %destructively, as long as the weight has not been reset. \index{getweightdps} {\bf (getweightdps)}\\ Returns the present weight as dotted pair list, where variable numbers and variable weights are combined explicitly:\\ $(1\ .\ weight_1) (2\ .\ weight_2) $..., in this order. %Caution: Do not %manipulate this destructively, as long as the weight has not been %reset. \index{printweights} {\bf (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. Example of a Gr\"{o}bner basis computation in a non-naturally graded situation:\\ \begin{verbatim} > bergman 4: end; Entering LISP ... Bergman 0.922, 9-Jun-98 1 lisp> (SETWEIGHTS 1 1 2) nil 2 lisp> (GETWEIGHTS) (1 1 2) 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 (comm.) input> vars x,y,z; algebraic form (comm.) 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 (CLEARALL), and run a new (SIMPLE). nil 4 lisp> \end{verbatim} \subsection {Strategies} The last important mode choice that should be mentioned is selecting the \index{strategy} strategy of the calculations. Besides selecting of the algorithm (commutative or non-commutative, Buchberger or staggered) that you are doing selecting by appropriate procedure, you have some influence on the intermediate calculation. Choosing \index{immediatefullreduction} {\bf (on immediatefullreduction) } (and this is default) you demand immediate reduction of all the terms of your Gr\"{o}bner basis and obtain it in the reduced form. Sometimes it might be more efficient to switch OFF this flag. The obtained Gr\"{o}bner basis may be not reduced, but calculations might be slightly faster. There is no clear receipts when it happens - try yourself! \subsection{Input--output modes for the polynomials} \label{inputform} There are three basic \index{output format} output formats, named \index{Lisp form} LISP (default), \index{algebraic form} ALG (its synonym is also MAPLE), and \index{Macaulay form} MACAULAY, corresponding to the formats, used in those 3 languages. The first two of these also are acceptable \index{input format} 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. \begin{description} \item{{\bf Commutative case}} The (output) ALG representation of the polynomial is $$c_1*v_1\wedge m_{11}*\ldots *v_n\wedge m_{1n}+ \ldots + c_r*v_1\wedge m_{r1}* \ldots *v_n\wedge m_{rn} .$$ Here $v_1, \ldots , 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\wedge 0$ and of $\wedge 1$ are omitted. + is omitted before $-$ . The MACAULAY representation is similar, but without $*$ and $\wedge$; and the polynomials then are not separated by commata. In input, some slight variation is allowed in the ALG format: \begin{itemize} \item $**$ may be used instead of $\wedge$; \item Blank space may be inserted everywhere, except within identifiers or integers or between two successive $**$ . \item Exponents 0 and 1 may occur. \item The order of the variables in a monomial is arbitrary. \end{itemize} The LISP representation of the same commutative polynomial in n variables is a lisp list of length n+1 lists of integers: $$((c_1\ m_{11}\ \ldots m_{1n}) \ldots (c_r\ m_{r1}\ \ldots 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. %\begin{exm} ------------------To be written-------------------- %\end{exm} \item{{\bf Non--commutative case}} LISP form (homogeneous) polynomial of degree $d$ is a list of lists of integers of length $d+1:$ $$((c_1\ m_{11}\ \ldots m_{1d}) \ldots (c_r\ m_{r1}\ \ldots 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_1*v_{m_{11}}*...*v_{m_{1d}}+ ... +c_r*v_{m_{r1}}*...*v_{m_{rd}} .$$ In input, identical factors may be collected to exponents. E. g., if the variables are $x,y,$ and $z$ (in this order), then the \index{Lisp form} LISP form polynomial $((5\ 1\ 1\ 1\ 3\ 2\ 2))$ will be \index{algebraic form} ALG form output as $5*x*x*x*z*y*y,$ but it may optionally be input as $5*x**3*z*y\wedge 2.$ Highest terms will be printed first in the output. \end{description} If you want to have output in ALG or \index{Macaulay form} MACAULAY form, you in one way or another must define the variable names, and you must set the global variable \index{algoutmode} {\bf algoutmode} to ALG or MACAULAY. The variable names are most easily given by setinvars within a {\bf algforminput}, as explained below. You may add your own algebraic output mode options by means of\\ \index{addalgoutmode} {\bf addalgoutmode}, as explained below. In order to perform \index{Lisp form} LISP mode input, write \index{lispforminput} {\bf (lispforminput) } pol1 pol2 ..... pols {\bf (lispforminputend)} \index{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".) In order to perform ALG mode input, write {\bf (algforminput) } {\bf vars v1, ...,vn;} {\bf pol1, ... , pols;} where v1, ..., vn are the variable names and pol1, ..., pols are polynomials on ALG form. COMMENTS: \begin{enumerate} \index{algforminput} \item Both {\bf algforminput} parts, i. e., the input variable setting and the polynomial listing, are optional. You may thus give LISP form input, but perform {\bf algforminput} vars v1,...,vn; ; (NOTE the double ;), in order to enable ALG or MACAULAY output. Of course, if you try to {\bf (algforminput)} polynomials when the variables are not set, you are in trouble. \item New successful (and non-empty) polynomial inputs replace old ones. Likewise, new successful input variable settings replace old ones. Running {\bf groebnerkernel} \index{groebnerkernel} (successfully) or {\bf clearall} \index{clearall} kills the input polynomials, but not the variable settings. \item The implementation of {\bf algforminput} depends on specific PSL features, since the pure Standard Lisp has poor alternative scanning abilities. If {\bf algforminput} should be disabled in some other implementation, and you still wish to use algebraic output modes, then you must define the variable names in another way, using the internal representations. In {\bf 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)))) . \end{enumerate} \section{Additional facilities: series and resolution} \label{sec:add} \subsection{Hilbert series computation} \label{Hilbertseries} There is a simple way to calculate the \index{Hilbert series} Hilbert series in non-commutative case: using the top level procedure \index{ncpbhgroebner} {\bf ncpbhgroebner.} The previous chapter contains all the explanation 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\"{o}bner basis was finished. If you want to get the next power series coefficients you may continue computation and call two procedures:\\ \index{calctolimit} {\bf (calctolimit degree)}\\ \index{tdegreehseriesout} {\bf (tdegreehseriesout degree)} Let us see an example. The file ``test3.a'' should be the input file:\\ \begin{verbatim} (setq maxdegree 10) (setq algoutmode 'ALG) (algforminput) vars x,y; x*x-2*y*y; \end{verbatim} Here is the corresponding session: \begin{verbatim} 1 lisp> (NCPBHGROEBNER "test3.a" "test3.gb" "test3.pbs" "test3.hs") *** I turn on noncommutativity NIL 10 ALG NIL *** Function `DEGREEENDDISPLAY' has been redefined SetupGlobals ... done % 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 MAXDEGREE) +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 MAXDEGREE) +6*z^5 +7*z^6 +8*z^7 +9*z^8 +10*z^9 +11*z^10 11 4 lisp> \end{verbatim} The resulting files are:\\ {\bf test3.gb}:\\ \begin{verbatim} % 2 -2*y^2+x^2, % 3 -y*x^2+x^2*y, \end{verbatim} {\bf test3.pbs}:\\ \begin{verbatim} +t^2*(z^2) +t^3*(z^2+z^3) +t^4*(z^3+z^4) \end{verbatim} {\bf test3.hs}:\\ \begin{verbatim} +3*z^2 +4*z^3 +5*z^4 \end{verbatim} As you can see, all calculations are done up to the degree 4 -- the last degree in the resulting Gr\"{o}bner basis. Calling\\ {\bf (calctolimit maxdegree)}\\ we obtain the continuation of Poincar\'{e}--Betti series and by\\ {\bf (tdegreehseriesout maxdegree)}\\ the next terms of Hilbert series are displayed. If you prefer the interactive input/output you can operate in the same manner with procedure \index{simple} {\bf simple} as it is illustrated in the following example: \begin{verbatim} 1 lisp> (NONCOMMIFY) NIL 2 lisp> (SETQ MAXDEGREE 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; SetupGlobals ... done +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 (CLEARALL), and run a new (SIMPLE). NIL 4 lisp> (CALCTOLIMIT MAXDEGREE) +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 MAXDEGREE) +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> \end{verbatim} To compute Hilbert series in the commutative case it is necessary to involve several procedures. First of all, the corresponding binary file should be loaded by\\ \index{hseries} {\bf (load hseries)}\\ The system may react by printing {\bf nil}. After that it is necessary to input the ring ideal variables and generators calling {\bf algforminput} and following its prompt. You can start Gr\"{o}bner basis calculation by means of two procedures: \index{groebnerinit} {\bf groebnerinit} and \index{groebnerkernel} {\bf 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 \index{interrupt strategy} interrupt strategy minor mode. The interrupt strategy is very efficient and more sofisticated, you can find its explanation below (see section \ref{comHS}). Let us deal here with the first case. You may get the Hilbert series as a rational expression $$\frac {p(t)}{(1-t)^ q},$$ or with the power series coefficient for some specified $t $ degree(s). The calculation is performed by procedure \index{calcrathilbertseries} {\bf calcrathilbertseries.} To see the result you should note that the global variables \index{hilbertnumerator} {\bf hilbertnumerator} and \index{hilbertdenominator} {\bf hilbertdenominator} represent a calculated $$p(t)/(1-t)^q = (a_{n}t^n + a_{n-1}t^{n-1} + \ldots + a_0)/(1-t)^q $$ by (the lisp items) $ ((n\ .\ a_n) (n-1\ .\ a_{n-1}) ... (0\ .\ a_0))$ and $ q$, respectively. To display the power series coefficients one may use the procedure\\ \index{tdegreehseriesout} {\bf tdegreehseriesout} giving the degree as argument. Here is an example of Hilbert series computation. \begin{verbatim} > bergman 4: end; Entering LISP ... Bergman 0.922, 9-Jun-98 1 lisp> (LOAD hseries) nil 2 lisp> (ALGFORMINPUT) algebraic form (comm.) input> vars x,y; algebraic form (comm.) input> x^3, x*y^2-x^2*y; nil 3 lisp> (GROEBNERINIT) nil 4 lisp> (GROEBNERKERNEL) d!o!n!e 5 lisp> (CALCRATHILBERTSERIES) nil 6 lisp> (SETQ p HILBERTNUMERATOR) ((4 . -1) (3 . -1) (2 . 1) (1 . 1) (0 . 1)) 7 lisp> (SETQ q HILBERTDENOMINATOR) 1 8 lisp> (TDEGREEHSERIESOUT 1) 2 9 lisp> (TDEGREEHSERIESOUT 2) 3 10 lisp> (TDEGREEHSERIESOUT 3) 2 11 lisp> (TDEGREEHSERIESOUT 4) 1 12 lisp> (TDEGREEHSERIESOUT 5) 1 13 lisp> (TDEGREEHSERIESOUT 6) 1 14 lisp> (TDEGREEHSERIESOUT 7) 1 15 lisp> (GROEBNERFINISH) \end{verbatim} The obtained result presented as a rational function is the following: $$\frac {1+t+t^2 -t^3 - t^4 }{1-t}.$$ The sequence of {\bf (tdegreehseriesout degree)} displays the corresponding power series coefficients representing the series: $$ 1+2t+3t^2+2t^3+t^4+t^5+t^6+t^7 +\ldots $$ Of course, one can collect all commands in a procedure destined to commutative Hilbert series computation reducing the manipulation to its call only. \subsection{Right modules over non-commutative algebras} It is possible to calculate Gr\"{o}bner basis and Hilbert series for right finitely-presented modules. To start some \index{calculations over modules} calculations over modules it is necessary first of all to load the corresponding component of {\bf bergman} -- the binary file \index{hseries} {\bf hseries}. Type\\ {\bf (load hseries)} The system may react by printing {\bf nil}. \begin{verbatim} 1 lisp> (LOAD hseries) nil \end{verbatim} Gr\"{o}bner bases and Hilbert series computations for modules are performed by the top level procedure \index{modulehseries} {\bf modulehseries.} It is necessary to input: \begin{itemize} \item the maximal degree of computation, \item the number of module variables, \item the list of the ring ideal and module variables, (the ring ideal variables should be at the beginning of the list), \item the ideal generators, \item the module generators. \end{itemize} 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. {\bf Interactive input/output}. It is the simplest way to start the computations. You should type only:\\ {\bf (modulehseries)} In this case a dialogue is initiated. The user is asked to input: \begin{itemize} \item the maximal degree of computation, \item the number of module variables, \item the list of the ring ideal and module variables (the ring ideal variables should be at the beginning of the list) and the ideal generators, \end{itemize} Receiving this data the Gr\"{o}bner basis for ideal is calculated and user is asked to input \begin{itemize} \item the module generators. \end{itemize} Here is an example of computations over modules: \begin{verbatim} > bergman 4: end; Entering LISP ... Bergman 0.922, 9-Jun-98 1 lisp> (LOAD hseries) nil 2 lisp> (MODULEHSERIES) *** I 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*y+x*x, +t^3*(2*z^2+2*z^3) % 3 x*x*x, y*x*x, +t^4*(6*z^3+2*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 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> \end{verbatim} {\bf 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.\\ {\bf (modulehseries "file1" "file2")} The file ``file1'' should contain: \begin{itemize} \item the maximal degree of computation defined by {\bf (setq maxdeg degree)} \item the number of module generators defined by {\bf (setq nmodgen number)} \index{nmodgen} \item the procedure call to process the list of variables presented in algebraic form: {\bf (algforminput)} \item the list of the ring ideal and module variables (the ring ideal variables should be at the beginning of the list). To input them it is necessary to write (without brackets!): {\bf vars $v_1, ... , v_n$;\\ $r_1,...,r_n$;\\} where $v_i$ are the ring ideal and module variables, $r_i$ are the ideal generators {\bf only}. Note that the items are separated by commas and every list is ended by semicolon. \end{itemize} Besides the above mentioned strings this file may contain flags and variables setting etc. according to {\bf bergman} common rules explained above and in the next chapter. The file ``file2'' should contain: \begin{itemize} \item the procedure call to process the list of variables presented in algebraic form: {\bf (algforminput)} \item the module generators: $m_1,...,m_n$; \end{itemize} Examples of ``file1'': \begin{verbatim} (SETQ MAXDEG 16) (SETQ NMODGEN 2) (ALGFORMINPUT) vars z,y,x,b,a; x*x, x*y+z*x; \end{verbatim} and ``file2'': \begin{verbatim} (ALGFORMINPUT) a*x*y-b*y*y+14*b*z*z, a*z*z*z-b*x*z*y; \end{verbatim} {\large {\bf Errors messages}}. If there was only one parameter in the parameter list it yields the following message:\\ {\bf ***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:\\ {\bf ***Input file must exist\\ Input data from keyboard\\} and the system will turn to the interactive input/output mode. {\bf Input from the files -- output to one or two files.} In this case the procedure call contains three or four parameters and looks like\\ {\bf (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\"{o}bner basis, the fourth is destined for Hilbert series output. If the last parameter is absent only the Gr\"{o}bner basis will be printed in the file. Independently of the number of parameters, the resulted Gr\"{o}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. {\large {\bf Errors messages}}. If the name of the third file is incorrect (it is not a quoted string), it yields the following message:\\ {\bf ***Incorrect output file.\\ Do you agree to use the file outf\underline{ }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:\\ {\bf outf\underline{ }mgb is used as output file.\\ Don't forget to rename it after calculations!}\\ and computing will continue using the file outf\underline{ }mgb as output file to print the resulting Gr\"{o}bner basis. If your answer is N ("Not") the following message will be displayed:\\ {\bf No output file. Program is cancelled}\\ and {\bf bergman} will finish its work. If the fourth parameter is incorrect an analogous dialogue appears proposing to use the file outf\underline{ }mhs to output Hilbert series. \subsection{Anick resolution and Betti numbers} \index{Anick resolution} Anick resolution and \index{Betti numbers} Betti numbers for the trivial module are computed for non-commutative case. (Resolution and Betti numbers for arbitrary module over non-commutative ring are under development now). To perform the calculations it is necessary to switch to the non-commutative mode:\\ {\bf (noncommify)}\\ and to load the corresponding binary file by:\\ {\bf (load anick)} As usual, doing non-commutative computations it is recommended to limit the process with some maximal degree. Thus the next procedure call should be:\\ {\bf (setq maxdeg degree)} Two following flags should be switched on: \begin{itemize} \item {\bf (on calcbetti)} \index{calcbetti} -- turns on the Betti numbers calculation mode. \item {\bf (on onflybetti)} \index{onflybetti} -- informs the application to calculate Betti numbers after each degree of Gr\"{o}bner basis is operated out. This allows to view Betti numbers degree by degree during the Gr\"{o}bner basis computations. \end{itemize} Using, for instance, the procedure {\bf simple}, you can obtain now not only Gr\"{o}bner basis, but Anick resolution and Betti numbers also. The procedure \index{calculateanickresolutiontolimit} {\bf (calculateanickresolutiontolimit maxdeg)} invokes method for calculation of Anick resolution till the degree MAXDEG. All the intermediate results, if any, are printed on the terminal. The procedure \index{anickdisplay} {\bf (anickdisplay)} prints the result resolution in the file which name is assigned to the variable \index{anickresolutionoutputfile} {\bf anickresolutionoutputfile}. If no file name is assigned the result by default will be printed in the file \index{andifres} {\bf andifres.txt}. %anDIFFTIME - time in milliseconds taken by processor %for operations related computing resolution elements %(differentials). % anBETTITIME - time in milliseconds taken by processor %for operations related computing Betti numbers. Let us see an example of Anick resolution and Betti numbers computation: \begin{verbatim} 1 lisp> (NONCOMMIFY) nil 2 lisp> (LOAD anick) nil 3 lisp> (SETQ MAXDEG 4) 4 4 lisp> (ON CALCBETTI) nil 5 lisp> (ON ONFLYBETTI) nil 6 lisp> (SETQ ANICKRESOLUTIONOUTPUTFILE "resolution.txt") "resolution.txt" 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 (noncomm.) input> vars x,y; algebraic form (noncomm.) input> x*y; Anick's resolution initialization... B(1,1)=2 Anick's resolution initialization done. +t^2*(z^2) % 2 x*y, Calculating Anick's resolution in degree 2... B(1,1)=2 B(2,2)=1 0 1 2 +---------- 0 | 1 2 1 1 | - - 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 (CLEARALL), and run a new (SIMPLE). nil 8 lisp> (CALCULATEANICKRESOLUTIONTOLIMIT MAXDEG) Calculating Anick's resolution in degree 3... B(1,1)=2 B(2,2)=1 0 1 2 +---------- 0 | 1 2 1 1 | - - end of Calculations. Calculating Anick's resolution in degree 4... B(1,1)=2 B(2,2)=1 0 1 2 +---------- 0 | 1 2 1 1 | - - end of Calculations. nil 9 lisp> (ANICKDISPLAY) 7 10 lisp> \end{verbatim} The example should be more or less clear except the last result -- the digit 7 obtained after {\bf (anickdisplay).} It is related to the Lisp conception of channel oriented input/output. Each channel has a corresponding number, and 7 is the current one in this example. You can see the computed resolution in the file {\bf resolution.txt} in your current directory. For this example it contains just:\\ \begin{verbatim} D(1, xy)=x.y B(1,1)=2 B(2,2)=1 0 1 2 +---------- 0 | 1 2 1 1 | - - \end{verbatim} D(1, xy)=x.y means that there exists the only 1-chain -- $xy$ and the differential $d_1$ acts as $$ d_1: xy\otimes 1 \rightarrow x\otimes y.$$ (see more comments about the Anick resolution for example in V.Ufnarovski, ``Introduction to Noncomutative Gr\"{o}bner Bases Theory'', in ``Gr\"{o}bner Bases and Applications'', Lect.Notes. London Math.Soc, 251, 1998, Cambridge Univ. Press). \section{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\"{o}bner bases calculations. {\bf 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: \begin{itemize} \item the top--of--the--top level, \item the top level, \item the level of internal using. \end{itemize} \index{simple} {\bf Simple} and \index{ncpbhgroebner} {\bf ncpbhgroebner}, for example, are top--of--the--top procedures, they solve completely some concrete problems -- to compute Gr\"{o}bner basis and series. \index{algforminput} \index{groebnerinit} \index{groebnerkernel} \index{groebnerfinish} {\bf Algforminput, groebnerinit, groebnerkernel, groebnerfinish } belong to the top level. The complete 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 four procedures that can help you to perform your own calculations. The reader is already familiar with them and now we want to explain more carefully their functions. We refer to the Lisp--appendix for more details about Lisp and will use Lisp--syntax without detailed explanations. The first thing that might be necessary is input. If the user wants algebraic form of input (instead of Lisp form) then the following procedure \\ {\bf algforminput }\\ should be used. You have see above several examples of its using. {\bf 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: \begin{verbatim} algebraic form (comm.) input> \end{verbatim} 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: {\bf (algforminput) } and {\bf vars } \ldots after that. Gr\"{o}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: \begin{itemize} \item {\bf groebnerinit }, \index{groebnerinit} that initiates numerous internal variables. It should be called {\it after} selecting modes and doing input. \item {\bf groebnerkernel. } \index{groebnerkernel} Here the main calculations are performed. The results of calculations are saved in several variables and files. You can use them in your own procedure using special procedures, created for this (see section \ref{functions} ). \item {\bf groebnerfinish. } \index{groebnerfinish} This procedure closes all files and restores variables and flags. \end{itemize} The user can include his code between those three procedures (see section \ref{Hilbertseries} as example of such the inclusion).