Debian Codegraph @

doc/bergman1.0.man/advance.tex

raw
1
2 %\def\newconcept#1\index{#1}\emph{#1}
3 \def\bm{{\bf bergman}}
4 \def\Bm{{\bf Bergman}}
5 \def\setQ{\mathbf{Q}}
6 \def\setZ{\mathbf{Z}}
7 \def\Gbas{Gr\"{o}bner bas}
8
9
10
11
12 \section{Introduction}
13 \label{sec:intr}
14
15
16 In this section we suppose that the user is already familiar with
17 {\bf bergman} and is able to start and use it in the simplest cases.
18 The aim of this section is to explain more detailed how to use
19 {\bf bergman} and to present all its facilities.
20
21
22
23 \section{{\bf Bergman}: philosophy and approach}
24
25
26 The philosophy of {\bf bergman} is to give the user a possibility
27 to use Bergman's Diamond Lemma with a maximum flexibility.
28 It means that {\bf bergman} is mainly a powerful instrument for
29 calculating Gr\"{o}bner basis in several situations: commutative and
30 non-commutative algebras, modules over them.
31
32 Besides that it provides some facilities to calculate
33 appropriate invariants of the algebras and modules:
34 Poincar\'{e} and Hilbert series, Anick's resolution and
35 Betti numbers.
36
37 The aim is maximum efficiency with few
38 restrictions. Note however the homogeneity setting. The user need not
39 care how long the coefficients might be if (s)he wants to work
40 over rationals, but should also have a possibility
41 to work over prime characteristic or to include
42 indeterminates as coefficients.
43
44 Nevertheless {\bf bergman} is not a full computer algebra system.
45 Rather it is a box,
46 containing several useful routines, so it takes
47 some efforts from the user to find them here and to use them
48 in a correct way. Additional problems might appear
49 because of the Lisp--oriented form of the procedures. But
50 this box is not black: the user can read, modify the procedures
51 and create its own. Moreover, (s)he can use them together
52 with Reduce, so from this point of view, {\bf bergman}
53 can be considered as a package for Reduce. (You can read
54 more about this in section \ref{reduce}).
55 The aim of this section is to explain {\bf bergman} as were it a
56 black box, describing all its main (unmodified) procedures.
57
58
59 \section{{\bf Bergman}: main restrictions}
60
61 {\bf Bergman} has two main restrictions.
62 First, it is not a
63 separate program and cannot be used without some underlying Lisp, like
64 PSL or CLISP (or Reduce,
65 which contains PSL). The second and important one, mentioned
66 above, is {\it homogeneity}.
67 All input to the simple top level procedures must be
68 homogeneous (by the natural grading, where each variable has degree
69 one). They do not automatically check homogeneity. The possibility to
70 use weighted variables extends the class of problems which
71 can be solved by {\bf bergman}: the degree function need not be a natural
72 (``standard'') grading.
73
74
75
76 There are some experimental procedures which under some restrictions test for
77 homogeneity, homogenise input, and dehomogenise output; see the
78 sub-section \ref{homog} below.
79
80 In the commutative case homogeneity is not the principal restriction.
81 It is not so difficult to homogenise relations to obtain the
82 same, in principal, result. But for the non-commutative algebras
83 this restriction is essential and this is the price for the efficiency.
84 Unfortunately, it means that it is impossible to use {\bf bergman}
85 for investigations of the groups or most of the finite dimension
86 algebras (such as matrix algebras), everything that contains
87 nontrivial idempotents.
88
89 Note also that {\bf bergman} has no routines for the polynomial
90 factorisation. So, the applications of {\bf bergman} to the solutions
91 of the nonlinear systems of equations are sufficiently restricted.
92
93
94
95 \section{The polynomial ring set up}
96 \label{modes}
97
98 To perform some computations in \bm\ you should set up the
99 polynomial ring and its environment. This action includes
100 %\index{polynomial ring} polynomial ring and its environment. This action includes
101 selection of the algebra type (\index{commutativity} commutative or
102 \index{non-commutativity} non-commutative),
103 the variables, the \index{ordering} ordering, the
104 %\index{characteristic} characteristic,
105 type of coefficients, and variable
106 \index{weights} weights. One can also select the strategy of computation,
107 and input--output mode. There are some minor mode selections too. For a
108 complete description see section \ref{refm}. This section contains an
109 informal explanation of the most important components in the ring
110 definition. The next section describes ideals definitions.
111
112
113 \subsection{Background}
114
115 Most Gr\"obner basis computations are performed within a given
116 \index{polynomial ring} polynomial ring $R = K \mathopen[ x_1, \ldots ,x_n
117 \mathclose]$ over a fixed \index{coefficient field} coefficient field~$K$.
118 We may recall that $R$ consists either of all commutative or of all
119 non-commutative polynomials in the \index{variable}
120 variables~$x_1$,~\dots, $x_n$. A polynomial $f \in R$ is a finite sum
121 $\sum_{i=1}^r c_ip_i$, where the terms or summands $c_ip_i$ are products
122 of coefficients $c_i \in K$ and (monic) monomials or \index{power product}
123 power products~$p_i$ (of variables).
124
125 %In the commutative case, (Since the terms `term' and `monomial' are used
126 %with different meanings.
127
128 \subsection{Variable names and the flag {\bf raise} }
129
130 We start from the variables -- generators of our algebras (modules).
131 Their names may be specified
132 to almost any valid Lisp identifiers. (Some special signs, like $*$ and
133 $^,$ should not be used unslashified in the identifier names.)
134 So, not only usual letters such as x,Y may be used, but also
135 x1,Y45 or even I\_kiss\_you\_a\_1000\_times can be used as a variable.
136 But do not try $x[1]$ or $Y(2)$ as names!
137 In any place you may have a look to your current list of variables:
138 \index{getinvars}
139
140 {\bf (getinvars)}
141
142 \begin{exm}
143 \begin{verbatim}
144 6 lisp> (GETINVARS)
145 (x y z)
146 \end{verbatim}
147 \end{exm}
148
149
150 One important question is if the names ''y'' and ''Y'' represent the same
151 variable. The answer depend on the current value of the flag \index{raise}
152 {\bf raise}. If it is in the state OFF, they are different, otherwise
153 (if it is in the state ON) ''y''=''Y''.
154
155 The meaning of this flag is to translate all the letters to
156 capitals (or the oppsite case in the later versions). Important notes, concerning this flag:
157 \begin{enumerate}
158 \item From the very beginning the value of this flag is ON. That is
159 why you can write {\bf (simple)} instead of {\bf (SIMPLE)}
160 \item You may influence whether or not reading of variables and generators
161 is case sensitive. Typing \index{setcasesensalgin}
162
163 {\bf (setcasesensalgin t)}
164
165 you establish the case sensitive mode of algebraic input and by
166
167 {\bf (setcasesensalgin nil)}
168
169 the mode is switched to no-case sensitivity.
170
171 \item Most the procedures, available to user have capital names.
172 (In the later version of Reduce the situation is opposite: the user
173 available procedures names are in lowercase characters.)
174 Nevertheless some procedures may turn OFF the flag while they
175 are working. If a break loop (for example because of mistake)
176 happens during their work the value of the flag will be OFF
177 and, for example, you will be unable to quit from the program
178 writing \index{quit}
179
180 {\bf (quit)}
181
182 because in this case the name should be capitalised:
183
184 {\bf (QUIT)}
185
186 Another way to quit is
187
188 {\bf (ON RAISE)}
189
190 {\bf (quit)}
191
192 \item Note, that turning ON this flag you loose access to all
193 the procedures and variables with the names, containing small letter,
194 such as SecretProcedure. The idea is that they should be unavailable
195 to the usual user, being absolutely internal and private. Nevertheless
196 user can sometimes see their names, where small letter are printed after
197 exclamations: S!e!c!r!e!tP!r!o!c!e!d!u!r!e. Even the multiplication
198 is secret in this mode and looks as !*.
199 But normally you need not care about this and turn OFF the
200 RAISE flag.
201
202
203 \end{enumerate}
204
205
206 \subsection{Ordering} \index{ordering}
207 \label{sec:ord}
208
209
210
211
212 In the commutative setting {\bf bergman} can perform computations in two different orderings:
213 \index{lexicographical ordering}
214 lexicographical (DEGLEX) or reverse lexicographical
215 \index{reverse lexicographical ordering} (DEGREVLEX). Both of them are graded,
216 it means that first we compare length (or weights) of words and only
217 after
218 that use the lexicographical comparison. For example, if $x>y>z$ is
219 our ordered alphabet, then we have
220 $$1 <z<y<x< zz<yz<yy<xz<xy<xx<\,.\,.\,.$$
221 in the commutative DEGLEX computation and
222 $$1 <z<y<x< zz<yz<xz<yy<xy<xx<\,.\,.\,.$$
223 in the commutative DEGREVLEX computation.
224
225 By default the DEGLEX ordering is chosen in the non-commutative {\bf berg\-man}
226 computation. Keeping the same ordered alphabet with $x>y>z$ we have
227 $$1 <z<y<x< zz<zy<zx<yz<yy<yx<xz<xy<xx<zzz\,.\,.\,.$$
228
229 Besides that there exist two eliminating orderings in the non-commutative mode:
230 ELIMLEFTLEX and INVELIMLEFTLEX.
231 In the first one the words are compared first as commutative words in
232 DEGLEX. If they are equal as commutative words they are compared
233 as in noncommutative DEGLEX.
234 Keeping the same ordered alphabet with $x>y>z$ we have
235
236 $$1 <z<y<x< zz<yz<zy<yy<xz<zx<xy<yx<xx<zzz\,.\,.\,.$$
237
238 In the INVELIMLEFTLEX. the first comparison is as commutative DEGREVLEX,
239 and if the words are equal as the commutative words they are compared
240 as in noncommutative DEGLEX. So the order will be:
241
242 $$1 <z<y<x< zz<yz<zy<xz<zx<yy<xy<yx<xx<zzz\,.\,.\,.$$
243
244 It is important for the Gr\"{o}bner basis calculations which of the variables is highest
245 (largest). The rule is determined by the order of the variables,
246 written after {\bf vars } in one of the top-of-the-top
247 procedures and is as follows:
248 \begin{itemize}
249 \item in the non-commutative DEGLEX mode the last variable is always highest.
250 \item in the commutative mode and both eliminating orderings first variable i highest.
251 % from the very beginning or after the
252 % calling the procedure
253 %
254 % {\bf (deglexify)} \index{deglexify}
255 %
256 % \item in the commutative mode the last variable is highest after the
257 % calling the procedure
258 %
259 % {\bf (degrevlexify)} \index{degrevlexify}
260
261
262 \end{itemize}
263
264 The following procedures set the corresponding orderings.
265
266 \vspace*{0.4cm}
267 \begin{tabular}{|l|l|}
268 \hline
269 Ordering & Procedure\\
270 \hline
271 DEGREVLEX & \index{degrevlexify} REVLEXIFY() \\ \hline
272 DEGLEX & \index{deglexify} DEGLEXIFY() \\
273 & (commutaive case)\\
274 & \index{degleftlexify} DEGLEFTLEXIFY() \\
275 & (noncommutaive case) \\ \hline
276 ELIMLEFTLEX & \index{elimorder} ELIMORDER() \\ \hline
277 INVELIMLEFTLEX &\index{invelimorder} INVELIMORDER() \\
278 \hline
279 \end{tabular}
280 \vspace*{0.4cm}
281
282 Note that the procedure {\bf deglexify} works only in the
283 commutative mode, in the noncommutaive case DEGLEX ordering
284 is established by the procedure {\bf degleftlexify}.
285
286
287 \subsection {Using eliminating ordering}
288
289 Despite the fact that {\bf bergman} works with graded algebras only,
290 it can be successfully applied to the non-graded case. The idea is to
291 homogenize the
292 ideal (using an additional commuting homogenizing variable $h$) and to
293 perform calculations
294 in the eliminating ordering and then dehomogenize the result setting $h=1.$
295
296 Let us consider an example suggested by Prof. I.Kantor.
297 Let $A$ be the following algebra:
298 $$A= < r,l,q| r^2-q^2+lr-r,
299 rq-qr+lq-q,
300 lr-rl,
301 lq+ql-2q,
302 rr-rl-2lr+2l^2-r+l>$$
303 It was important to find the minimal polynomial for $q.$
304 Here is the solution achieved by {\bf bergman}:
305
306 \begin{footnotesize}
307 \begin{verbatim}
308 2 lisp> (noncommify)
309 nil
310 3 lisp> (elimorder)
311 nil
312 4 lisp> (simple)
313 Now input in-variables and ideal generators
314 in algebraic form, thus:
315 vars v1, ..., vn;
316 r1, ..., rm;
317 where v1, ..., vn are the variables,
318 and r1, ..., rm the generators.
319 algebraic form input> vars r,l,q,h;
320 algebraic form input> r*r-q*q+l*r-r*h,r*q-q*r+l*q-q*h,
321 algebraic form input> l*r-r*l,l*q+q*l-2*q*h,
322 algebraic form input> r*r-r*l-2*l*r+2*l*l-r*h+l*h,
323 algebraic form input> r*h-h*r,q*h-h*q,l*h-h*l;
324
325 % 2
326 -h*q+q*h,
327 -h*l+l*h,
328 q*l+l*q-2*q*h,
329 -h*r+r*h,
330 -q*r+r*q+l*q-q*h,
331 -4*r*l+2*l^2+l*h+q^2,
332 4*l*r-2*l^2-l*h-q^2,
333 4*r^2-4*r*h+2*l^2+l*h-3*q^2,
334
335 % 3
336 4*r*q*h-4*l^2*q+10*l*q*h-q^3-9*q*h^2,
337 4*r*q^2+12*l^3-10*l*q^2-3*l*h^2-3*q^2*h,
338
339 % 4
340 l*q^3-3*l*q*h^2-q^3*h+3*q*h^3,
341 -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,
342 -4*l^3*q+12*l^2*q*h-11*l*q*h^2+3*q*h^3,
343 12*l^4-8*l^2*q^2-3*l^2*h^2-2*l*q^2*h+q^4,
344
345 % 5
346 -48*l^2*q*h^2+96*l*q*h^3-q^5+10*q^3*h^2-57*q*h^4,
347
348 % 6
349 -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,
350
351 % 7
352 -q^7+13*q^5*h^2-39*q^3*h^4+27*q*h^6,
353
354 \end{verbatim}
355 \end{footnotesize}
356
357 If we look at the last element of the obtained Gr\"{o}bner basis and
358 put $h=1$ we get the desired equation:
359 $$q^7-13q^5+39q^3-27q=0$$
360 The secret is in the command {\bf elimorder}: now if two words are compared,
361 they are compared first as the commutative words in pure left lexicographical
362 ordering and after that (if commutatively they are equal) as usual. That is
363 why if the minimal polynomial exists its homogenized variant should belong to
364 the Gr\"{o}bner basis: if the leading monomial is $q^n$ all other terms
365 should contain the letters $h$ and $q$ only, $h$ being in the end because it
366 commutes with $q.$ To obtain the minimal polynomial for $l$ it is sufficient
367 to put $l$ before the homogenizing variable (which should remain the last)
368 in the list of the variables, e.g. {\bf vars} r,q,l,h;
369
370
371
372 \subsection{Coefficients: background}
373 \label{sec:field}
374
375
376 \index{coefficients} Coefficients handling is an important part of
377 \bm. Mathematically, the ring of coefficients should be a field~$K$,
378 the \index{coefficient field}{\bf coefficient field}. In basic \bm, this field must be a
379 prime field; i.e., either the field $\setQ$ of rational numbers, or the
380 Galois field $\setZ / (p)$ of residue classes of integers with respect to
381 a prime number $p$. The \index{characteristic}{\bf characteristic} of $\setQ$ is 0, and
382 the characteristic of $\setZ / (p)$ is $p$, so that the prime field is
383 completely determined by its characteristic.
384
385
386 If you run \bm\ under \index{Reduce mode} Reduce in commutative mode,
387 then you have further possibilities, as described in the next
388 subsection. In order to employ these, it is necessary to understand
389 the way bergman treats coefficients.
390
391 In order to simplify the internal representation and thus make
392 coefficient calculations faster, \bm\ tries to avoid fractions in
393 coefficients, whenever feasible. This is done by means of the
394 coefficient domain, associated polynomials, and gcd calculations.
395
396 The \index{coefficient domain} {\it coefficient domain\/}~$A$ should be a
397 sub-domain of the coefficient field~$K$, such that its field of fractions
398 is~$K$. (Here {\it domain} signifies integral domain, i.e., unitary
399 commutative ring without non-trivial zero-divisors.) In the basic
400 coefficient modes, $A$ is the smallest possible sub-domain of~$K$,
401 so that $A = \setZ =$~the ring of integers in characteristic~0, but
402 $A = K = \setZ / (p)$ in positive characteristic.
403
404 Recall that if $f = f(x_1,\ldots,x_n)$ and $g = g(x_1,\ldots,x_n)$ are
405 elements in $R = K \mathopen[ x_1,\ldots,x_n
406 \mathclose]$, then $f$ and $g$ are \index{associated
407 polynomial} {\it associated polynomials\/} if $g = uf$ for some non-zero
408 $u \in K$. (Then clearly $f = u^{-1}g$; and more generally, `associatedness'
409 is an equivalence relation on $R$.) Since $K$ is the field of fractions
410 of~$A$, each $f \in R$ has associated polynomials with all their
411 coefficients in~$A$. We may e.g.\ write all coefficients of~$f$ as
412 fractions of elements in~$A$, and let $u$ be the product of all the
413 denominators; then clearly $uf \in A \mathopen[ x_1,\ldots,x_n
414 \mathclose]$.
415
416 However, normally this is far from efficient. The
417 coefficients in this $uf$ often are extremely large (or complex).
418 For $A = \setZ$, this may be avoided by factoring out the \index{content}
419 {\it content\/} of $uf$, i.e., the greatest common divisor of all the
420 coefficients. Thus we get a new associated polynomial, hopefully with
421 reasonably complex coefficients.
422
423 If $g_i$ is associated to $f_i$ for $i = 1, \ldots, r$, then $f_1,\ldots,
424 f_r$ and $g_1, \ldots, g_r$ generate the same ideal in $R$. Hence, if
425 $K = \setQ$ and
426 all we want is to calculate a \Gbas is, then we may always replace any
427 appearing polynomial by an associated polynomial in $\setZ \mathopen[
428 x_1,\ldots,x_n \mathclose]$ of content~1. In practice, it is more efficient
429 to make such replacements dynamically during the calculation of normal
430 forms. This is the default content taking strategy of \bm.
431
432 There are some situations when such tactics do not work, as when we
433 want to calculate Anick resolutions. Hence, \bm\ also has a procedure
434 NORMALFORM for calculating the true normal form of a polynomial.
435
436
437
438 \subsection{Coefficients: Choices}
439
440 \index{coefficients}
441
442 To select a \index{coefficient field} coefficient field (and a
443 \index{coefficient domain} coefficient domain) you call \index{setmodulus}
444 {\bf (setmodulus $p$) }
445
446 where either $p$ is the desired \index{characteristic} characteristic (0 or
447 a prime number), or $p$ is {\bf sf} (for ``(Reduce) Standard Forms'').
448
449 By default and after the call {\bf (setmodulus 0)}, the coefficient field
450 is the field~$\setQ$ of rational numbers, and the coefficient domain is
451 the ring~$\setZ$ of integers. This means that all input coefficients
452 and most internal and output coefficients are considered as integers. There are
453 no restrictions for the length of the integers - only the restrictions of the
454 memory of your own computer. Nevertheless, when you are sure from the
455 very beginning that your coefficients (even inside the calculations)
456 never will be too large (e.g. if the relations have a semigroup form:
457 $f-g,$ where $f$ and $g$ are words) you can try to achieve more
458 efficiency using the flag \index{nobignum} {\bf *nobignum} - see
459 the subsection \ref{flags} for more details.
460
461 However, if you want to perform series calculations, you should also
462 decide whether or not the series coefficients may exceed the `small
463 integer limit' of your lisp implementation, before turning on
464 nobignums.
465
466 You cannot use fractions in the input and do not ordinarily get them as output.
467 %So, the highest term of your Gr\"{o}bner basis elements may have a coefficient, even
468 %negative.
469
470 Another minor mode choice affecting the characteristic zero (and the {\bf sf})
471 coefficient mode is the dense or sparse content taking.
472
473
474 \medskip
475
476 After the call {\bf{setmodulus}~$p$}, where $p$ is a prime number, the
477 coefficient field and the coefficient domain both are $\setZ / (p) = GF(p)$,
478 the unique field with $p$ elements.
479
480
481 %You have also a possibility to select prime characteristic in the both
482 %variants - with bignums or without them.
483 %For example
484
485 %{\bf (nobignums) }
486
487
488 %{\bf (setmodulus 2) }
489
490
491 % is a reasonable preparation if you plan to work over the field of two
492 % elements only.
493 %Nevertheless there is no possibility to work in the field other then
494 %$F_p$ inside {\bf bergman}. You can do it only under Reduce (see section
495 %\ref{reduce} for more details).
496
497 Note that in the prime characteristic the highest term of any
498 polynomial in the Gr\"{o}bner basis has
499 always the coefficient~1 (in contrast to the zero characteristic case).
500
501 In odd prime characteristic with a reasonably small~$p$, bergman employs
502 efficient `small number calculations' only with the coefficients. If you
503 need to optimise coefficient handling further, please note the
504 following. With some hardware and software architectures, multiplication
505 is a much more time consuming operation than are (single) additions and
506 multiplications. In such cases, you should consider employing the
507 \index{modulus logarithms method} {\it modulus logarithms method\/}.
508 Mathematically speaking, it works by finding a generator $\gamma$ for the
509 cyclic multiplicative group of non-zero elements in $\setZ/(p)$, and by
510 representing such elements by their ``$\gamma$-logaritms'' (i.e.,
511 representing $a = \gamma^s$ by $s$), whenever convenient.
512
513 The main effect of using the `modular logaritms mode'
514 in typical {\bf berg\-man} \Gbas is calculations is that in the most time
515 consuming combined coefficient operation, of the type
516 $$a \cdot b + c \,,$$
517 one multiplication and one addition is replaced by two additions and
518 one `logaritm table lookup operation', represented by finding an item
519 in a lisp vector (array). In addition, one lisp remainder operation is
520 replaced by one comparison and (in average) a half subtraction. The
521 net effect is to replace one multiplication and one remainder operation
522 by one addition, a half subtraction, one comparison and one `look-up'.
523
524 The draw-back is that \bm\ must construct or to read the `logarithm
525 table' and the inverse `exponential table' into memory.
526
527 If you want to employ this, do \index{modlogs}
528 {\bf (modlogs on)}
529 {\it before} you do the {\bf setmodulus $p$} for your odd
530 prime~$p$.
531
532 When you do this, \bm\ may or may not succeed in finding a prepared
533 file for the look-up tables; and if it doesn't find the file, it
534 may or it may not succeed in creating the tables. In the present
535 version, it is depending on being able to create the tables file, if
536 this doesn't exist. Thus, you may run into troubles, e.g.\ if you do
537 not have write access to the directory for modular logarithm tables
538 handling. Some ways of overcoming this are discussed in the
539 next chapter.
540
541 %The effect (after calling the {\bf (setmodulus Q) })
542 %is to create in the subdirectory {\bf domains} the file with the first
543 %letter p, following the digits, representing the number Q (e.g. p37
544 %for Q=37) or using existing one if it was already created. It
545 %provides efficient calculations of the products, using so-called
546 %logarithmic tables.% (see chapter \ref{MATH-APP} for more details.)
547
548 You need not this mode in characteristic 2 or 0, and should avoid
549 it (possibly loosing a bit in time efficiency) if you want to save
550 memory. By default, modular logarithms are off.
551
552
553 \medskip
554
555 %The most general (but difficult) choice is selecting arbitrary
556 %forms of the coefficients, by
557 %{\bf setmodulus sf}
558 %This is possible under Reduce only. % and is described in the subsection \ref{reduce}.
559
560 In addition to the few efficient basic coefficient modes available in {\bf berg\-man},
561 there is a possibility to set up `your own' coefficient field and domain
562 in an ordinary Reduce way. In this case, \bm\ calls Reduce for each
563 coefficient operation. The domain elements are represented as Standard
564 Forms, and the field elements as Standard Quotients. Similarly, the
565 general Reduce Greatest Common Divisor procedure is employed for taking
566 contents. Any reduction rules for calculating in Reduce are active,
567 including Reduce modulus setting, but with the following exception:
568 At input from Reduce, the variables specified as bergman in-variables
569 are treated by \bm\ variable handling procedures.
570
571 In order to employ this, the user should have a good understanding
572 both of the mathematics and of Reduce. It is entirely her/his
573 responsibility to ensure that indeed the given in-coefficients reside
574 in a mathematically well-defined field, with respect to the given
575 Reduce rules.
576
577 Example: In order to calculate with coefficients in the field
578 $GF(169)(a)$ (where $a$ is transcendent over $GF(169)$), you may note
579 that $GF(169)$ may be realised as a quadratic extension of its
580 prime field $GF(13)$, e.g., by means of $\sqrt2$. Thus, you might try
581
582 {\bf algebraic;}
583
584 {\bf setmod 13;}
585
586 {\bf on modular;}
587
588 {\bf b\^{}2 := 2;}
589
590 and then go on as usual, employing the $i+j*b$ ($i,j \in
591 \{0,1,\ldots,12\}$) as representatives for the elements in $GF(169)$.
592
593
594
595
596 \subsection{Weights handling}
597
598 There are possibilities to handle some non-naturally graded
599 situations, i.e., situations where not all variables have degree 1.
600 Then the \index{weights} weights, i.e., the degrees of the variables, may be set
601 to arbitrary positive integers. (Thus weight 0 is not allowed.)
602 The degree of a monomial then will be calculated as the sum of the
603 weights of its variable factors.
604
605 The natural grading corresponds to giving each variable weight 1.
606 However, using the weighted variables mode could yield considerably
607 slower calculations than using the natural grading mode. Thus weights
608 should be set only if some of them deviate from 1.
609
610 Restrictions: For computational efficiency reasons, all degrees
611 appearing during calculations are assumed to be ''inums'', i.e., small
612 enough to fit into the small numbers representation of your computer.
613 In the naturally graded situation, this is hardly ever a practical
614 limitation; but if you give rather high weights to some variables,
615 you could get into some trouble.
616
617 %The weights
618 %information is saved internally in two structures. The
619 %weight list is NIL in the naturally graded case, and else contains
620 %the weights of variable 1, 2, 3, ..., in this order. The weight
621 %dotted pair list explicitly combines variable numbers and variable
622 %weights as dotted pairs (1 . weight_1) (2 . weight_2) ..., in this
623 %order.
624
625 There are moreover some inconsistencies in the variable ordering in
626 this version of {\bf bergman}. Also, series calculation and the Anick
627 resolution implementation are not yet
628 compatible with the weighted variables mode.
629
630 The weight list contains the weights of variable 1, 2, 3, \ldots , in
631 this order.
632
633 There are several procedures for weights handling in {\bf bergman}.
634
635 \index{setweights} {\bf (setweights $int_1$ $ int_2$ \ldots $int_n$)}\\
636 Sets the weights to $int_1$, \ldots , $int_n$. The $int_*$ must be positive
637 integers. No weights given restores the naturally graded mode.
638 % Returns the old weight list.
639
640 \index{clearweights} {\bf (clearweights)} \\
641 Restores the naturally graded mode. Returns the old weight list.
642
643 \index{getweights} {\bf (getweights)} \\
644 Returns the current weight list.
645
646 %Caution: Do not manipulate this
647 %destructively, as long as the weight has not been reset.
648
649 \index{getweightdps} {\bf (getweightdps)}\\
650 Returns the present weight as dotted pair list, where variable
651 numbers and variable weights are combined explicitly:\\
652 $(1\ .\ weight_1) (2\ .\ weight_2) $..., in this order.
653
654 %Caution: Do not
655 %manipulate this destructively, as long as the weight has not been
656 %reset.
657
658 \index{printweights} {\bf (printweights)}\\
659 If weights are set, print these (with spaces between but without
660 parentheses or line feeds) and return T. Else, print nothing and
661 return NIL.
662
663 Example of a Gr\"{o}bner basis computation in a non-naturally graded
664 situation:\\
665
666 \begin{verbatim}
667
668
669 > bergman
670
671 7: end;
672 Entering LISP ...
673 Bergman 0.926, 24-Oct-98
674 1 lisp> (SETWEIGHTS 1 1 2)
675 nil
676 2 lisp> (GETWEIGHTS)
677 (1 1 2)
678 3 lisp> (SIMPLE)
679 Now input in-variables and ideal generators
680 in algebraic form, thus:
681 vars v1, ..., vn;
682 r1, ..., rm;
683 where v1, ..., vn are the variables,
684 and r1, ..., rm the generators.
685 algebraic form input> vars x,y,z;
686 algebraic form input> x^3, x*z-y*z;
687 % 3
688 x*z-y*z,
689
690 % 6
691 x^3,
692
693 % 7
694 y^3*z,
695
696 Done
697 - All is OK (I hope). Now you may (e. g.):
698 - kill bergman with (QUIT); or
699 - interrupt bergman with ^Z; or
700 - clear the memory with (CLEARIDEAL),
701 and run a new (SIMPLE).
702 nil
703 4 lisp>
704
705
706 \end{verbatim}
707
708 \subsection{Homogenisation}
709 \label{homog}
710
711 Suppose we would like to find a minimal polynomial for
712 $\alpha=\sqrt{2}+\sqrt{3}+\sqrt{5},$ i.e. such a polynomial $f(x)$ with the
713 integer coefficients that $f(\alpha)=0.$ One possible way to do it is to find a
714 Gr\"{o}bner basis for the following ring:
715
716 $$ A=<x,y,z,t| xx-2,yy-3,zz-5, t-x-y-z>$$
717
718 The important thing is the choice of ordering. We want to get the element that
719 contains the variable $t$ only - it would be desired minimal polynomial. So
720 the variable $t$ should be the lowest, for example $x>y>z>t.$ Even more -
721 any power of $t$ should be less than any monomial, containing any variable
722 different from $t.$ It means that we need pure lexicographical ordering.
723 In such an ordering (for example pure revlex) we should have the following
724 Gr\"{o}bner basis$:\\
725 t^{8} - 40t^{6} + 352t^{4} - 960t^{2} + 576\\
726 576z - 5t^{7} + 194t^{5} - 1520t^{3} + 2544t \\
727 96y + t^{7} - 37t^{5} + 244t^{3} - 360t \\
728 576x - t^{7} + 28t^{5} + 56t^{3} - 960t $
729
730 How to get from the \bm\ such a result? The problem is that \bm\ uses
731 homogeneous relations only. The solution is to homogenize the relations, using
732 a new variable (say $f$):
733
734 $$ 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>$$
735
736 It means that every monomial that had less degree than highest one (constants
737 in our case) was completed by corresponding number of factor $f.$ The
738 relations are now homogeneous and we can calculate the Gr\"{o}bner basis in
739 the corresponding ordering. Let us see the session:
740
741 \begin{verbatim}
742
743 Bergman 0.94, 17-Dec-99
744 1 lisp> (purelexify)
745 nil
746 2 lisp> (off usermode)
747 nil
748 4 lisp> (setalgoutmode alg)
749 nil
750 5 lisp> (algforminput)
751 algebraic form input> vars x,y,z,t;
752 algebraic form input> x^2-2, y^2-3, z^2-5, t-x-y-z;
753 t
754 6 lisp> (homogeniseinput)
755 *** Function `h!O!M!O!Gpm!O!N' has been redefined
756 nil
757 7 lisp> (groebnerinit)
758 nil
759 8 lisp> (groebnerkernel)
760 d!O!N!E
761 9 lisp> (algforminput)
762 algebraic form input> vars x,y,z,t,f;
763 algebraic form input> ;
764 nil
765 10 lisp> (bigoutput)
766 -x-y-z+t,
767 z^2-5*f^2,
768 2*y*z-2*y*t-2*z*t+t^2+6*f^2,
769 y^2-3*f^2,
770 2*y*f^2-3*z*t^2+6*z*f^2+t^3+4*t*f^2,
771 y*t^2-7*z*t^2+12*z*f^2+2*t^3+12*t*f^2,
772 4*z*t^3-t^4-20*t^2*f^2+24*f^4,
773 -80*z*t^2*f^2+96*z*f^4-t^5+60*t^3*f^2+24*t*f^4,
774 96*z*t*f^4-t^6+40*t^4*f^2-376*t^2*f^4+480*f^6,
775 576*z*f^6-5*t^7+194*t^5*f^2-1520*t^3*f^4+2544*t*f^6,
776 -t^8+40*t^6*f^2-352*t^4*f^4+960*t^2*f^6-576*f^8,
777
778 nil
779 11 lisp> (quit)
780
781 \end{verbatim}
782
783 %(DE HOMOGENP (auginhpol)
784 %(DE TESTINDATA ()
785 %(DE PREPAREHOMOGENISATION ()
786 %(DE PREPAREDEHOMOGENISATION ()
787 %(DE CLEARHOMOGENISATION ()
788 %(DE HOMOGENISE (auginhpol)
789 %(DE HOMOGENISEINPUT ()
790
791 %(DE DEGREELISTPUTPOINTERS(deglmonpol)
792
793
794 %Homogenisation/dehomogenisation preparation. %%%%%%%%
795
796 % Homogenisation/inhomogenisation is a bit intricate, since the
797 % internal representation of monomials depends on the number of
798 % variables (the "embedding dimension", embdim). The homogenisation
799 % SHOULD HAPPEN IN THE SAME PLACE, ONCE in the run, unless an
800 % explicit dehomogenisation or a (CLEARIDEAL) has been performed.
801 % The reason is that else there is a grave risque of mixing in-
802 % homogeneous polynomials and monomials with homogeneous ones,
803 % or to use operations assuming the right kind of internal
804 % representation on the former, when they no longer have it.
805 % MOST SAFE AND SIMPLE should be only to use HOMOGENISEINPUT
806 % and DEHOMOGENISEREDUCEGBASIS. However, other top level functions
807 % may be needed in particular applications.
808
809
810 % The switch HOMOGENISED is normally set on or off by the
811 % (de-)homogenising routines. Touch it only e.g. to fool the
812 % system that the data is (not) homogenised, in order to perform
813 % an extra (de-)homogenisation.
814
815
816 % Checks that the mode settings are appropriate; sets HOMOGENISED;
817 % Stores away/Throws away the old saved unique monomial information
818 % (depending on whether SAVEINHOMOGMONS is set or not); changes the
819 % internal embdim, if set.
820
821
822
823
824
825 \subsection {Strategies}
826 The last important mode choice that should be mentioned is selecting
827 the \index{strategy} strategy of the calculations. Besides selecting of the
828 algorithm (commutative or non-commutative, Buchberger or staggered)
829 that you are doing selecting by appropriate procedure, you have
830 some influence on the intermediate calculation. Choosing
831 \index{immediatefullreduction}
832
833 {\bf (on immediatefullreduction) }
834
835 (and this is default) you demand immediate reduction of all the terms
836 of your Gr\"{o}bner basis and obtain it in the reduced form.
837 Sometimes it might be
838 more efficient to switch OFF this flag. The obtained Gr\"{o}bner basis may be
839 not reduced, but calculations might be slightly faster. There is no
840 clear receipts when it happens - try yourself!
841
842
843 \section{Ideals and quotient ring}
844
845 To perform Gr\"{o}bner basis computation in the quotient ring $A=<X|R>$
846 we need to define a polynomial ring and an ideal $I=(R)$ in it.
847 \subsection{Input--output modes for the polynomials}
848 \label{inputform}
849
850 There are three basic \index{output format} output formats, named
851 \index{Lisp form} LISP (default), \index{algebraic form} ALG
852 (its synonym is also MAPLE), and
853 \index{Macaulay form} MACAULAY, corresponding to the formats, used in those 3 languages.
854 The first two of these also are acceptable \index{input format} input formats.
855 In all input and output, the polynomials are distributed (written with
856 no parentheses). There is a difference between commutative and
857 non-commutative case.
858 \begin{description}
859 \item{{\bf Commutative case}}
860
861 The (output) ALG representation of the polynomial is
862 $$c_1*v_1\verb-^-m_{11}*\,.\,.\,. *v_n\verb-^-m_{1n}+ \,.\,.\,.
863 + c_r*v_1\verb-^-m_{r1}* \,.\,.\,. *v_n\verb-^-m_{rn} .$$
864 Here $v_1, \,.\,.\,., v_n$ stand for the variable names, $m_{ij}$
865 for the exponents,
866 and $c_i$ for the coefficients. Highest terms will be printed first.
867
868 Occurrences of $*v_i\verb-^-0$ and of $\verb-^-1$ are omitted.
869 + is omitted before $-$ .
870 The MACAULAY representation is similar, but without $*$ and $\verb-^-$; and the
871 polynomials then are not separated by commata.
872 In input, some slight variation is allowed in the ALG format:
873 \begin{itemize}
874 \item $**$ may be used instead of $\verb-^-$;
875 \item Blank space may be inserted everywhere, except within identifiers
876 or integers or between two successive $**$ .
877 \item Exponents 0 and 1 may occur.
878 \item The order of the variables in a monomial is arbitrary.
879 \end{itemize}
880
881
882 The LISP representation of the same commutative polynomial in n variables is a
883 lisp list of length n+1 lists of integers:
884 $$((c_1\ m_{11}\ \,.\,.\,. m_{1n}) \,.\,.\,.(c_r\ m_{r1}\ \,.\,.\,. m_{rn}))$$
885 where the CAR of the i:th list is the coefficient of the i:th monomial,
886 and the other n integers (which should be non-negative) are the
887 exponents. Highest terms will be printed first in the output.
888
889 %\begin{exm} ------------------To be written--------------------
890 %\end{exm}
891
892 \item{{\bf Non--commutative case}}
893
894 LISP form (homogeneous) polynomial of
895 degree $d$ is a list of lists of integers of length $d+1:$
896 $$((c_1\ m_{11}\ \,.\,.\,. m_{1d}) \,.\,.\,. (c_r\ m_{r1}\ \,.\,.\,. m_{rd})) $$
897 where the CAR of the i:th list is the coefficient of the i:th monomial,
898 and the other n integers (which should be positive) are the
899 ''indices''
900 of the variables, i. e., their position if they are ordered by increasing
901 significance. The corresponding ALG format is
902 $$c_1*v_{m_{11}}*\,.\,.\,.*v_{m_{1d}}+\,.\,.\,. +c_r*v_{m_{r1}}*\,.\,.\,.*v_{m_{rd}} .$$
903 In input, identical factors may be collected to exponents. E. g., if
904 the variables are $x,y,$ and $z$ (in this order), then the
905 \index{Lisp form} LISP form
906 polynomial $((5\ 1\ 1\ 1\ 3\ 2\ 2))$ will be \index{algebraic form}
907 ALG form output as
908 $5*x*x*x*z*y*y,$
909 but it may optionally be input as $5*x**3*z*y\verb-^-2.$
910 Highest terms will be printed first in the output.
911
912
913 \end{description}
914
915 If you want to have output in ALG or \index{Macaulay form} MACAULAY form, you in one way or
916 another must define the variable names, and you must set the global
917 variable \index{algoutmode} {\bf algoutmode} to ALG or MACAULAY. The variable names are most
918 easily given by setinvars within a {\bf algforminput}, as explained below.
919
920 You may add your own algebraic output mode options by means
921 of\\ \index{addalgoutmode} {\bf addalgoutmode}, as explained below.
922
923 In order to perform \index{Lisp form} LISP mode input, write
924 \index{lispforminput}
925
926 {\bf (lispforminput) }
927
928 pol1 pol2 ..... pols
929
930 {\bf (lispforminputend)}
931
932 \index{lispforminputend}
933
934 where pol1, ..., pols are polynomials on LISP form. If you must specify
935 the number of variables to a number $n$ (as in the non-commutative case,
936 if you want to know the Hilbert series), then set EMBDIM to $n$. (EMBDIM
937 is short for "the embedding dimension".)
938
939 In order to perform ALG mode input, write
940
941
942 {\bf (algforminput) }
943
944 {\bf vars v1, ...,vn;}
945
946 {\bf pol1, ... , pols;}
947
948 where v1, ..., vn are the variable names and pol1, ..., pols are
949 polynomials on ALG form.
950
951 COMMENTS:
952
953 \begin{enumerate} \index{algforminput}
954 \item Both {\bf algforminput} parts, i. e., the input variable setting and the
955 polynomial listing, are optional. You may thus give LISP form input,
956 but perform {\bf algforminput} vars v1,...,vn; ; (NOTE the double ;),
957 in order to enable ALG or MACAULAY output. Of course, if you try
958 to {\bf (algforminput)} polynomials when the variables are not set, you are in
959 trouble.
960 \item New successful (and non-empty) polynomial inputs replace old ones.
961 Likewise, new successful input variable settings replace old ones.
962 Running {\bf groebnerkernel} \index{groebnerkernel} (successfully)
963 or
964 {\bf clearideal} \index{clearideal} kills the input
965 polynomials, but not the variable settings.
966 \item The implementation of {\bf algforminput} depends on specific PSL features,
967 since the pure Standard Lisp has poor alternative scanning abilities.
968 If {\bf algforminput} should be disabled in some other
969 implementation, and if
970 you still wish to use algebraic output modes, then you must define
971 the variable names in another way, using the internal
972 representations. In {\bf bergman 0.9*} and the next versions, the output variable settings
973 performed by
974
975 vars x,y,z;
976
977 in the commutative case corresponds to
978
979 (SETQ O!u!tV!a!r!s (QUOTE (!x !y !z)))
980
981 and in the non-commutative case corresponds to
982
983 (SETQ O!u!tV!a!r!s (QUOTE ((1 . !x) (2 . !y) (3 . !z)))) .
984
985 \end{enumerate}
986
987
988
989 \section{Calculating and using series}
990 \label{sec:add}
991
992
993
994
995 \subsection{Hilbert series computation} \label{Hilbertseries}
996
997
998 There is a simple way to calculate the \index{Hilbert series} Hilbert
999 series in
1000 non-commutative case: using the top level procedure \index{ncpbhgroebner} {\bf ncpbhgroebner.} The
1001 previous chapter contains all the explanation concerning its calling,
1002 arguments and results. The only problem is that the Hilbert series computation is stopped
1003 in the degree where the computation of the corresponding Gr\"{o}bner basis was finished.
1004 If you want to get the next power series coefficients you may continue computation and call two procedures:\\
1005 \index{calctolimit} {\bf (calctolimit degree)}\\
1006 \index{tdegreehseriesout} {\bf (tdegreehseriesout degree)}
1007
1008
1009
1010 Let us see an example. The file ``test3.a'' should be the input file:\\
1011
1012 \begin{verbatim}
1013 (setmaxdeg 10)
1014 (setalgoutmode 'ALG)
1015 (algforminput)
1016 vars x,y;
1017 x*x-2*y*y;
1018 \end{verbatim}
1019
1020
1021 Here is the corresponding session:
1022
1023 \begin{verbatim}
1024
1025 1 lisp>(ncpbhgroebner "test3.a""test3.gb""test3.pb""test3.hs")
1026 *** I turn on noncommutativity
1027 nil
1028 alg
1029 t
1030 *** Function `!O!L!D!D!E!D' has been redefined
1031 *** Function `DEGREEENDDISPLAY' has been redefined
1032
1033 % No. of Spolynomials calculated until degree 2: 0
1034 % No. of ReducePol(0) demanded until degree 2: 0
1035 % Time: 238
1036
1037
1038 % No. of Spolynomials calculated until degree 3: 1
1039 % No. of ReducePol(0) demanded until degree 3: 0
1040 % Time: 289
1041
1042
1043 % No. of Spolynomials calculated until degree 4: 2
1044 % No. of ReducePol(0) demanded until degree 4: 0
1045 % Time: 323
1046
1047 *** Function `DEGREEENDDISPLAY' has been redefined
1048 NIL
1049 2 lisp> (CALCTOLIMIT (GETMAXDEG))
1050 +t^5*(z^4+z^5)
1051 +t^6*(z^5+z^6)
1052 +t^7*(z^6+z^7)
1053 +t^8*(z^7+z^8)
1054 +t^9*(z^8+z^9)
1055 +t^10*(z^9+z^10)
1056 NIL
1057 3 lisp> (TDEGREEHSERIESOUT (GETMAXDEG))
1058 +6*z^5
1059 +7*z^6
1060 +8*z^7
1061 +9*z^8
1062 +10*z^9
1063 +11*z^10
1064 11
1065 4 lisp>
1066
1067 \end{verbatim}
1068
1069
1070 The resulting files are:\\
1071
1072 {\bf test3.gb}:\\
1073
1074 \begin{verbatim}
1075 % 2
1076 -2*y^2+x^2,
1077
1078 % 3
1079 -y*x^2+x^2*y,
1080 \end{verbatim}
1081
1082 {\bf test3.pbs}:\\
1083
1084 \begin{verbatim}
1085 +t^2*(z^2)
1086 +t^3*(z^2+z^3)
1087 +t^4*(z^3+z^4)
1088 \end{verbatim}
1089
1090
1091 {\bf test3.hs}:\\
1092
1093 \begin{verbatim}
1094 +3*z^2
1095 +4*z^3
1096 +5*z^4
1097 \end{verbatim}
1098
1099 As you can see, all calculations by {\bf ncpbhgroebner}
1100 are done up to the degree 4 -- the last degree
1101 in the resulting Gr\"{o}bner basis. Calling\\
1102 {\bf (calctolimit (getmaxdeg))}\\
1103 we obtain the continuation of Poincar\'{e}--Betti series and by\\
1104 {\bf (tdegreehseriesout (getmaxdeg))}\\
1105 the next terms of Hilbert series are displayed.
1106
1107
1108 If you prefer the interactive input/output you can operate in the same manner with
1109 procedure \index{simple} {\bf simple} as it is illustrated in the following example:
1110
1111
1112
1113 \begin{verbatim}
1114 1 lisp> (NONCOMMIFY)
1115 NIL
1116 2 lisp> (SETMAXDEG 10)
1117 10
1118 3 lisp> (SIMPLE)
1119 Now input in-variables and ideal generators
1120 in algebraic form, thus:
1121 vars v1, ..., vn;
1122 r1, ..., rm;
1123 where v1, ..., vn are the variables,
1124 and r1, ..., rm the generators.
1125 algebraic form (noncomm.) input> vars x,y;
1126 algebraic form (noncomm.) input> x*x-2*y*y;
1127
1128 +t^2*(z^2)
1129 % 2
1130 -2*y^2+x^2,
1131
1132 +t^3*(z^2+z^3)
1133 % 3
1134 -y*x^2+x^2*y,
1135
1136 +t^4*(z^3+z^4)
1137
1138 Done
1139 - All is OK (I hope). Now you may (e. g.):
1140 - kill bergman with (QUIT); or
1141 - interrupt bergman with ^Z; or
1142 - clear the memory with (CLEARIDEAL),
1143 and run a new (SIMPLE).
1144 NIL
1145 4 lisp> (CALCTOLIMIT (GETMAXDEG))
1146 +t^5*(z^4+z^5)
1147 +t^6*(z^5+z^6)
1148 +t^7*(z^6+z^7)
1149 +t^8*(z^7+z^8)
1150 +t^9*(z^8+z^9)
1151 +t^10*(z^9+z^10)
1152 NIL
1153 5 lisp> (TDEGREEHSERIESOUT (GETMAXDEG))
1154 +3*z^2
1155 +4*z^3
1156 +5*z^4
1157 +6*z^5
1158 +7*z^6
1159 +8*z^7
1160 +9*z^8
1161 +10*z^9
1162 +11*z^10
1163 11
1164 6 lisp>
1165
1166 \end{verbatim}
1167
1168
1169
1170
1171 To compute Hilbert series in the commutative case it is necessary to
1172 involve
1173 several procedures. First of all,
1174 it is necessary to input the ring ideal variables and
1175 generators calling {\bf algforminput} and following its prompt (if it
1176 was not done before).
1177 You can start Gr\"{o}bner basis calculation by means of two
1178 procedures: \index{groebnerinit} {\bf groebnerinit} and
1179 \index{groebnerkernel} {\bf groebnerkernel.}
1180 Now the system is ready
1181 to compute Hilbert series.
1182
1183 There are two main uses for the Hilbert series facilities: stand alone
1184 and within the Hilbert series \index{interrupt strategy} interrupt strategy minor mode. The
1185 interrupt strategy is very efficient and more sophisticated, you can
1186 find its explanation below (see sections \ref{limHS},\ref{comHS}).
1187
1188 Let us
1189 deal here with the
1190 first case. You may get the Hilbert series
1191 as a rational expression
1192 $$\frac {p(t)}{(1-t)^ q},$$ or with
1193 the power series coefficient for some specified $t $ degree(s).
1194 The calculation is performed by procedure
1195 \index{calcrathilbertseries} {\bf calcrathilbertseries.}
1196 To see the result you should note that the global variables
1197 \index{hilbertnumerator} {\bf hilbertnumerator} and
1198 \index{hilbertdenominator} {\bf hilbertdenominator} represent a calculated
1199 $$p(t)/(1-t)^q = (a_{n}t^n + a_{n-1}t^{n-1} + \,.\,.\,. +
1200 a_0)/(1-t)^q $$
1201 by (the lisp items) $ ((n\ .\ a_n) (n-1\ .\ a_{n-1}) ... (0\ .\ a_0))$ and $
1202 q$,
1203 respectively.
1204
1205 To display the power series coefficients one may use the procedure\\
1206 \index{tdegreehseriesout} {\bf tdegreehseriesout} giving the degree as argument.
1207
1208 Here is an example of Hilbert series computation.
1209
1210 \begin{verbatim}
1211
1212 > bergman
1213
1214 4: end;
1215 Entering LISP ...
1216 Bergman 0.922, 9-Jun-98
1217 1 lisp> (LOAD hseries)
1218 nil
1219 2 lisp> (ALGFORMINPUT)
1220 algebraic form (comm.) input> vars x,y;
1221 algebraic form (comm.) input> x^3, x*y^2-x^2*y;
1222 t
1223 3 lisp> (GROEBNERINIT)
1224 nil
1225 4 lisp> (GROEBNERKERNEL)
1226 d!O!N!E
1227 5 lisp> (CALCRATHILBERTSERIES)
1228 nil
1229 6 lisp> (SETQ p HILBERTNUMERATOR)
1230 ((4 . -1) (3 . -1) (2 . 1) (1 . 1) (0 . 1))
1231 7 lisp> (SETQ q HILBERTDENOMINATOR)
1232 1
1233 8 lisp> (TDEGREEHSERIESOUT 1)
1234 2
1235 9 lisp> (TDEGREEHSERIESOUT 2)
1236 3
1237 10 lisp> (TDEGREEHSERIESOUT 3)
1238 2
1239 11 lisp> (TDEGREEHSERIESOUT 4)
1240 1
1241 12 lisp> (TDEGREEHSERIESOUT 5)
1242 1
1243 13 lisp> (TDEGREEHSERIESOUT 6)
1244 1
1245 14 lisp> (TDEGREEHSERIESOUT 7)
1246 1
1247 15 lisp> (GROEBNERFINISH)
1248
1249 \end{verbatim}
1250
1251
1252 The obtained result presented as a rational function is the following:
1253 $$\frac {1+t+t^2 -t^3 - t^4 }{1-t}.$$ The sequence of
1254 {\bf (tdegreehseriesout degree)} displays the corresponding power series
1255 coefficients representing the series: $$ 1+2t+3t^2+2t^3+t^4+t^5+t^6+t^7
1256 +\,.\,.\,. $$
1257
1258
1259
1260 All the functions listed abowe are collected in the procedure
1261 \index{hilbert} {\bf hilbert} destined to
1262 commutative Hilbert series computation reducing the manipulation to
1263 its call only.
1264 The previous example might be computed using this procedure:
1265
1266 \begin{verbatim}
1267 1 lisp> (hilbert)
1268 Input the maximal power series degree you want to calculate
1269 1 lisp> 6
1270 Now input in-variables and ideal generators
1271 in algebraic form, thus:
1272 vars v1, ..., vn;
1273 r1, ..., rm;
1274 where v1, ..., vn are the variables,
1275 and r1, ..., rm the generators.
1276 algebraic form input> vars x,y;
1277 algebraic form input> x^3, x*y^2-x^2*y;
1278 % 3
1279 -x^2*y+x*y^2,
1280 x^3,
1281
1282 % 4
1283 x*y^3,
1284
1285 Hilbert series numerator: +1*t^0+1*t^1+1*t^2-1*t^3-1*t^4
1286 Hilbert series denominator: 1-t
1287 Hilbert power series: 1+2t^1+3t^2+2t^3+t^4+t^5+t^6+...
1288 Done
1289 \end{verbatim}
1290
1291 In this example both rational and power series are displayed. To avoid the last one
1292 it is necessary to input the maximal power series degree 0.
1293
1294 To perform the input from a file one should prepare it including the following lines:
1295
1296 \begin{verbatim}
1297 (SETQ MAXSERDEG 6)
1298 (ALGFORMINPUT)
1299 vars x,y;
1300 x^3, x*y^2-x^2*y;
1301 \end{verbatim}
1302
1303 The corresponding call (after {\bf hseries} loading) containing a input file and two
1304 output files - for Groebner basis and Hilbert series - looks like:
1305
1306 \begin{verbatim}
1307 (hilbert ``input_file'' ``output_gb_file'' ``output_hs_file'')
1308 \end{verbatim}
1309
1310
1311
1312 \subsection{Computation of Gr\"{o}bner basis using known Hilbert series}
1313 \label{limHS}
1314
1315
1316 It rather often happens that we know (at least partly) the Hilbert
1317 series before we start any computations. {\bf Bergman} proposes an
1318 efficient optimisation of the Gr\"{o}bner basis calculations in those cases.
1319 Here we
1320 learn us how to translate our knowledge about the Hilbert
1321 series to {\bf bergman}. Let us consider a classical example.
1322
1323 Suppose that we want to calculate Gr\"{o}bner basis of the following ideal
1324 (the corresponding system of equations, when $z=1,$ has a proper
1325 name ``6-cyclic roots system'')
1326
1327 $$a+b+c+d+e+f,$$
1328
1329 $$ ab+bc+cd+de+ef+fa,$$
1330
1331 $$ abc+bcd+cde+def+efa+fab,$$
1332
1333 $$ abcd+bcde+cdef+defa+efab+fabc,$$
1334
1335 $$ abcde+bcdef+cdefa+defab+efabc+fabcd,$$
1336
1337 $$ abcdef-z^6;$$
1338
1339 It is not so difficult to calculate Gr\"{o}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
1340 \begin{footnotesize}
1341 $$\frac{1 +4t+9t^2+15t^3+20t^4+22t^5+19t^6+
1342 11t^7+t^8-7t^9-10t^{10}-12t^{11}-10t^{12}-5t^{13}+2t^{15}}{(1-t)^2}=$$
1343 \end{footnotesize}
1344 $$1 +6t+20t^2+49t^3+98t^4+169t^5+ 259t^6+ 360t^7+ 462t^8+ 557t^9+ 642t^{10}+ 715t^{11}+ $$
1345 $$ +778t^{12} +836t^{13}+ 894t^{14}+ 954t^{15}+ 1014t^{16}+ 1074t^{17}+ 1134t^{18}+ 1194t^{19}+\,.\,.\,.$$
1346
1347 The following session shows how to calculate Gr\"{o}bner basis in 3.3 sec - more than twice faster!
1348
1349 \begin{verbatim}
1350
1351 1 lisp> (setinterruptstrategy minhilblimits)
1352 nil
1353 2 lisp> (sethseriesminima 1 6 20 49 98 169 259 360 462 557 642
1354 715 778 836 894 954 1014 1074 1134 1194)
1355 t
1356 3 lisp> (simple "sixroots" "sixroots.bg")
1357 t
1358 - All is OK (I hope). Now you may (e. g.):
1359 - kill bergman with (QUIT); or
1360 - interrupt bergman with ^Z; or
1361 - clear the memory with (CLEARIDEAL),
1362 and run a new (SIMPLE).
1363 nil
1364 4 lisp>
1365 \end{verbatim}
1366
1367 Now some comments. In the first line {\bf bergman} is informed that
1368 the strategy of the computations is changed -- we want {\bf bergman} to stop the calculations in the current degree $d$
1369 when the desired coefficient of the Hilbert series is achieved (in this degree). The next line describes coefficients themselves.
1370
1371 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.
1372 To avoid such a situation (for example, when we are not sure in the part of the coefficients) one can use {\bf nil} instead of the numbers. This informs
1373 {\bf bergman} that the calculations in this degree goes ``as usual''.
1374
1375 Another even more efficient application of this technique is skipping the
1376 Gr\"{o}bner basis calculations in those degrees when they were preliminary done before. Suppose that after a 20 hours of calculations we get a Gr\"{o}bner basis until degree 4 and saved it in a file. The next day we use this file
1377 (after minor changes) as input file but do not want to repeat calculation in the
1378 degree 4 or less. The solution is the line\\
1379 {\bf (sethseriesminima skipcdeg skipcdeg skipcdeg skipcdeg skipcdeg) }\\
1380 (note that we used 5 {\bf skipcdeg}s, because the first degree is 0).
1381
1382 There is another
1383 (more advanced) way of doing it, employing a little lisp programming
1384 (and that if the degree is - say - 15 instead of 5, then indeed this
1385 may be the point to start entering the more advanced phase). The
1386 actual programming might look like
1387
1388 {\bf (sethseriesminimumdefault (cond ((lessp hsdeg 5) skipcdeg)))}
1389
1390 or like
1391
1392 {\bf (sethseriesminima (default (cond ((lessp hsdeg 5) skipcdeg))))}
1393
1394 The complete information about the possibilities of using the function
1395 {\bf (sethseriesminima)} the user should find in the section \ref{comHS}.
1396
1397 \section{The jumping \index{rabbit} rabbit}
1398
1399 In this section we discuss the possibilities to perform
1400 non-homogeneous calculations. Let $A= <X|R>$ be an algebra we are
1401 interesting in and suppose that not all of elements of $R$ are
1402 homogeneous. One possible way to get a Gr\"{o}bner basis for $A$ is to homogenize
1403 all the relations using the additional variable $t,$ calculate a Gr\"{o}bner basis
1404 for the
1405 new algebra $B=<X,t|R_h,tx-xt, x\in X>,$ where $R_h$ stands for the set of
1406 homogenized relations and to dehomogenize the obtained Gr\"{o}bner basis for $B$ by
1407 putting
1408 $t=1.$ Though it works theoretically with some orders, which
1409 eliminates $t,$ the problem is that even for the finite dimensional
1410 algebra $A$ a Gr\"{o}bner basis for $B$ is usually infinite. The problem
1411 is that $B$ is not the same algebra as $C,$ which is obtained from $A$ by
1412 homogenizing all the relations of $A$ (not only the defining relations!) That is why
1413 a reduced Gr\"{o}bner basis for $B$ contains a lot of elements of the form $ut^k,$
1414 where
1415 $u=0$ in $C$ but not in $B.$ Therefore
1416 after the dehomogenization
1417 we get a Gr\"{o}bner basis in $A$ that is far from being reduced. Thus it is practically
1418 impossible to use this approach for computing the Gr\"{o}bner basis even
1419 for finite dimensional algebras.
1420
1421 To solve this problem {\bf bergman} suggests a special procedure {\bf rabbit}
1422 which starts from $A,$ homogenizes the relations getting $B$ and then
1423 calculates a reduced Gr\"{o}bner basis for $C$ instead of $B$ (more exactly, a part of
1424 it until the given degree {\bf maxdeg}).
1425
1426 The trick is to cancel all obtained elements of form $ut^k$
1427 replacing them by $u.$ This means that after finishing
1428 calculations
1429 in some degree $m=\deg u$ and doing calculations in the degree $m+k$
1430 we need to jump back to degree $m$ and restart the calculations
1431 beginning from this degree! That is why the program is named rabbit
1432 and takes three parameters, which permit jumping to be organized
1433 in a more or less regular manner. The parameters are {\bf startdeg, jumpstep} and
1434 {\bf maxdeg}. So,
1435 {\bf (rabbit startdeg jumpstep maxdeg)} is a call of the procedure, which works as follows.
1436 First it suggests to input generators and relations in usual manner starting from {\bf vars}.
1437 Second it homogenizes the input and starts to calculate a Gr\"{o}bner basis degree after
1438 degree. When the degree becomes equal to the {\bf startdeg} it
1439 prepares for jumping. It means that it collects all the elements of Gr\"{o}bner basis
1440 which can be canceled by the homogenizing variable. When {\bf jumpstep} degrees more are
1441 done the program checks if something was collected. If not, the next {\bf jumpstep}
1442 degrees should be done before the next checking. If yes, the canceling is performed and the
1443 degree is reduced to the minimum degree of new obtained relations and the process continues
1444 in the same manner. It stops when {\bf maxdeg} is achieved or when no new
1445 Gr\"{o}bner basis elements can be obtained. In both cases the dehomogenization is
1446 performed and the result is printed, but in the first case a warning that the Gr\"{o}bner
1447 basis may be wrong is displayed. Jumping during the process is always shown, but to
1448 display the intermediate homogeneous relations the program has to be run in the debug mode.
1449
1450
1451 In the following example a Gr\"{o}bner basis for the algebra
1452 $A=<a,b,c|ab=c,bc=a,ca=b> $ is calculated:
1453
1454 \begin{footnotesize}
1455 \begin{verbatim}
1456 2 lisp> (rabbit 2 2 8)
1457 algebraic form input> vars a,b,c;a*b-c, b*c-a, c*a-b;
1458 SetupGlobals
1459 ... done
1460 RABBIT: Added step, Maxdegree=4
1461 Jump number 1
1462
1463 RABBIT: Jump number 2
1464
1465 RABBIT: Jump number 3
1466
1467 RABBIT: Added step, Maxdegree=6
1468 Jump number 4
1469
1470 GB is completely calculated
1471 Rabbit have finished jumping. GB is
1472 a*b-c,
1473 b^2-a^2,
1474 b*c-a,
1475 c*a-b,
1476 -c^2+a^2,
1477 a^3-c*b,
1478 -a^2*c+b*a,
1479 b*a^2-a*c,
1480 b*a*c-a*c*b,
1481 -c*b*a+a*c*b,
1482
1483 nil
1484 \end{verbatim}
1485 \end{footnotesize}
1486
1487 We see that the Gr\"{o}bner basis is calculated completely and there are only 8
1488 nonempty normal words: $a,b,c,a^2,ac,ba,cb,cba.$ One can conclude that
1489 a semigroup with our defining relations is in fact the quaternion group
1490 (because it has 8 elements and has those relations).
1491
1492
1493
1494
1495
1496
1497 \section{Some bricks to build your own procedures}
1498 \label{sec:bricks}
1499
1500 In this section we suppose that the user have already tried procedures, described above
1501 and want to write his own, involving Gr\"{o}bner bases
1502 calculations. {\bf Bergman} is an open system,
1503 you have access to its source code, you can use each of its procedures as useful items in your own
1504 applications. There is a three levels hierarchy of procedures:
1505
1506 \begin{itemize}
1507 \item the top--of--the--top level,
1508 \item the top level,
1509 \item the level of internal using.
1510 \end{itemize}
1511
1512 \index{simple} {\bf Simple} and \index{ncpbhgroebner} {\bf ncpbhgroebner}, for example, are top--of--the--top procedures, they
1513 solve completely some concrete problems -- to compute Gr\"{o}bner basis and series.
1514 \index{algforminput} \index{groebnerinit} \index{groebnerkernel}
1515 \index{groebnerfinish} {\bf Algforminput, groebnerinit, groebnerkernel, groebnerfinish } belong to the top level.
1516 The complete list of the top level procedures you can find in Chapter 3.
1517
1518 Users are recommended to use the procedures from the first two levels, if they would like to see
1519 how the last level looks like, they might read the source code.
1520
1521
1522 Here we describe
1523 four procedures that can help you to perform your own calculations. The reader is already
1524 familiar with them and now we want to explain more carefully their functions. %We refer to the
1525 %Lisp--appendix for more details about Lisp and will use Lisp--syntax
1526 %without detailed explanations.
1527
1528 The first thing that might be necessary is input. If the user wants algebraic
1529 form of input (instead of Lisp form) then the following procedure \\
1530 {\bf algforminput }\\
1531 should be used. You have see above several examples of its using.
1532 {\bf Algforminput } scans the
1533 succeeding input for variables list and/or polynomial list in algebraic form. If you type its call
1534 on the screen you get its prompt:
1535
1536
1537 \begin{verbatim}
1538
1539 algebraic form (comm.) input>
1540
1541 \end{verbatim}
1542
1543 and the system is waiting for the input list.
1544
1545 If you perform the input from a file, you should put in this file the line:
1546
1547 {\bf (algforminput) }
1548
1549 and {\bf vars } \ldots after that.
1550
1551
1552
1553 Gr\"{o}bner basis calculations are organized in such a way that a user is able to include his
1554 own operators inside them. For this purposes they are divided into 3 separate procedures:
1555 \begin{itemize}
1556 \item {\bf groebnerinit, } \index{groebnerinit} that initiates numerous internal variables. It should be called {\it after} selecting modes and
1557 doing input.
1558 \item {\bf groebnerkernel. } \index{groebnerkernel} Here the main calculations are performed.
1559 The results of calculations are
1560 saved in several variables and files. You can use them in your own procedure using
1561 special procedures, created for this (see section \ref{functions} ).
1562
1563 \item {\bf groebnerfinish. } \index{groebnerfinish} This procedure closes all files and restores variables and flags.
1564
1565
1566 \end{itemize}
1567
1568 The user can include his code between those three procedures (see
1569 section \ref{Hilbertseries} as example of such the inclusion).
1570
1571
1572
1573
1574