| 1 |
\hspace{5cm} \mbox {``If easy of use was the only valid criterion} |
| 2 |
|
| 3 |
\hspace{5cm} \mbox { people would stick to tricycles and never} |
| 4 |
|
| 5 |
\hspace{5cm} \mbox { try bicycles''.} |
| 6 |
|
| 7 |
\hspace{10cm} \mbox{ D.Engelbart} |
| 8 |
|
| 9 |
\section{Preliminaries} |
| 10 |
{\bf Bergman} is a system for computations in commutative and purely |
| 11 |
non-commutative |
| 12 |
algebra. It is mainly developed by J\"{o}rgen Backelin (Stockholm University). |
| 13 |
Some additional facilities are implemented by participants of the joint |
| 14 |
project ''Non-commutative computer algebra'' (Stockholm University, |
| 15 |
Institute of Mathematics of Moldavian Academy of Sciences). |
| 16 |
|
| 17 |
{\bf Bergman} is public domain software available by anonymous ftp from |
| 18 |
ftp.matematik.su.se. It is written in Standard Lisp, the Lisp dialect |
| 19 |
underlying Reduce implementation. An alternative Common Lisp |
| 20 |
version is also supported for some platforms. |
| 21 |
|
| 22 |
{\bf Bergman} presently runs on the following platforms with |
| 23 |
pre--installed Reduce or PSL. |
| 24 |
|
| 25 |
\begin{itemize} |
| 26 |
\item Sun--Sparc station under SunOS, Solaris and Linux; |
| 27 |
\item Alpha station under Dec OSF and Linux; |
| 28 |
\item PC under MS DOS. |
| 29 |
\end{itemize} |
| 30 |
|
| 31 |
The Common Lisp version runs on the following platforms with |
| 32 |
pre--installed Common Lisp: |
| 33 |
|
| 34 |
\begin{itemize} |
| 35 |
\item Sun--Sparc station under SunOS, Solaris and Linux; |
| 36 |
\item Alpha station under Dec OSF and Linux; |
| 37 |
\item PC under Windows 95/98/NT. |
| 38 |
\end{itemize} |
| 39 |
|
| 40 |
|
| 41 |
|
| 42 |
For detailed information about different versions of operating |
| 43 |
systems and Reduce or Lisp releases, see the installation guide. |
| 44 |
|
| 45 |
{\bf Bergman} is far from a full computer algebra system. However, it |
| 46 |
may be run under Reduce and in the commutative setting be treated as any |
| 47 |
Reduce module. |
| 48 |
|
| 49 |
Using {\bf bergman} one can compute both for ideals and right modules: |
| 50 |
|
| 51 |
\begin{itemize} |
| 52 |
\index{Gr\"{o}bner basis} \item Gr\"{o}bner basis |
| 53 |
\index{Hilbert series} \item Hilbert series |
| 54 |
\index{Poincar\'{e} series} \item Poincar\'{e} series |
| 55 |
\index{Anick resolution} \item Anick resolution |
| 56 |
\index{Betti numbers} \item Betti numbers |
| 57 |
\end{itemize} |
| 58 |
|
| 59 |
The last three features are destined to non-commutative computations only. |
| 60 |
|
| 61 |
One can find the description of {\bf bergman}, including a demo version on |
| 62 |
its home page: |
| 63 |
http://servus.math.su.se/bergman/ |
| 64 |
|
| 65 |
Of course, the demo version offers only limited possibilities, but you |
| 66 |
can try to solve your own problems. |
| 67 |
|
| 68 |
Here we describe a version of {\bf bergman}, installed under Reduce, |
| 69 |
and working |
| 70 |
in the Standard Lisp environment. In this installation the user can |
| 71 |
use both Reduce and Lisp syntax. Nevertheless most of the text is |
| 72 |
valid for other installations too. The Reduce--oriented syntax |
| 73 |
will be discussed in section \ref{reduce}. |
| 74 |
|
| 75 |
\subsection{Starting a {\bf bergman} session} |
| 76 |
|
| 77 |
You can start a \index{bergman session} {\bf bergman} session by typing |
| 78 |
{\bf bergman } followed by {\bf Enter}. |
| 79 |
When you are successful in starting the {\bf bergman} session you will |
| 80 |
see a prompt. |
| 81 |
If the installation was under Reduce, the prompt (after some possible |
| 82 |
messages about memory and version) may look like: |
| 83 |
|
| 84 |
{\bf |
| 85 |
|
| 86 |
4: } |
| 87 |
|
| 88 |
Now you maybe want to switch to the \index{Lisp mode} Lisp--mode. (If you prefer to work |
| 89 |
in the |
| 90 |
\index{Reduce mode} Reduce--mode read section \ref{reduce} instead.) For this you simply type |
| 91 |
{\bf end; } and then press {\bf Return } key. You will see a new Lisp--prompt: |
| 92 |
|
| 93 |
{\bf Entering LISP ... |
| 94 |
|
| 95 |
Bergman 0.922, 9-Jun-98 |
| 96 |
|
| 97 |
1 lisp$>$ } |
| 98 |
|
| 99 |
(If your installation was without Reduce you are here from the very beginning). |
| 100 |
Of course, the date and the version can be different -- it depends |
| 101 |
from the date |
| 102 |
when {\bf bergman} was compiled on your computer. |
| 103 |
|
| 104 |
Typically {\bf bergman} will print a prompt such as\\ |
| 105 |
{\bf 4 lisp$>$ }\\ |
| 106 |
at the beginning of the line you should enter. Whenever you |
| 107 |
see a prompt, {\bf bergman} is waiting for you to enter new |
| 108 |
commands. |
| 109 |
|
| 110 |
The Common Lisp version starts directly: |
| 111 |
\begin{verbatim} |
| 112 |
i i i i i i i ooooo o ooooooo ooooo ooooo |
| 113 |
I I I I I I I 8 8 8 8 8 o 8 8 |
| 114 |
I \ `+' / I 8 8 8 8 8 8 |
| 115 |
\ `-+-' / 8 8 8 ooooo 8oooo |
| 116 |
`-__|__-' 8 8 8 8 8 |
| 117 |
| 8 o 8 8 o 8 8 |
| 118 |
------+------ ooooo 8oooooo ooo8ooo ooooo 8 |
| 119 |
|
| 120 |
Copyright(c) Bruno Haible,Michael Stoll 1992, 1993 |
| 121 |
Copyright(c) Bruno Haible,Marcus Daniels 1994-1997 |
| 122 |
Copyright(c) Bruno Haible,Pierpaolo Bernardi,Sam Steingold 1998 |
| 123 |
Copyright(c) Bruno Haible,Sam Steingold 1999 |
| 124 |
|
| 125 |
Welcome to the BERGMAN system. |
| 126 |
|
| 127 |
[1]> |
| 128 |
|
| 129 |
\end{verbatim} |
| 130 |
|
| 131 |
Now you are ready for computations -- $ [1]>$ is the input prompt. |
| 132 |
Lately we will not distinguish PSL and Common Lisp version and will use |
| 133 |
the word Lisp for both of them. |
| 134 |
|
| 135 |
\subsection{Ending a {\bf bergman} session} |
| 136 |
|
| 137 |
The command \index{quit} {\bf (quit)} followed by the {\bf Return } key, ends |
| 138 |
a {\bf bergman} session. |
| 139 |
\begin{exm}\label{exquit}. Here you finish the session |
| 140 |
\end{exm} |
| 141 |
|
| 142 |
{\bf 10 lisp$>$ (quit) } |
| 143 |
|
| 144 |
In Reduce syntax you omit the parenthesis but add a semicolon, thus: |
| 145 |
|
| 146 |
{\bf 10: quit; } |
| 147 |
|
| 148 |
An alternative solution on some platforms is to use Ctrl--D: holding down the Ctrl--key |
| 149 |
while pushing one or several times on key ``D'' will make quit. This |
| 150 |
may work in Reduce syntax, too. |
| 151 |
|
| 152 |
\subsection{What you need to know about Lisp syntax} |
| 153 |
|
| 154 |
The user should realise that {\bf bergman} is a Lisp program and whenever (s)he |
| 155 |
starts {\bf bergman} he works under Lisp and in Lisp notations. Here |
| 156 |
we |
| 157 |
describe |
| 158 |
the necessary minimum of Lisp syntax to deal with {\bf bergman} in the simplest |
| 159 |
cases. |
| 160 |
|
| 161 |
First of all, all commands should be written within parenthesis - |
| 162 |
see Example \ref{exquit}. |
| 163 |
|
| 164 |
It is important that uppercase and lowercase may be different in Lisp. |
| 165 |
One can use, for instance, only lowercase. Nevertheless in some situations, |
| 166 |
arising from |
| 167 |
mistakes you leave {\bf bergman}, but still need to leave Lisp. In this case |
| 168 |
usual, |
| 169 |
{\bf (quit)} not necessary ends the session |
| 170 |
and you need to use |
| 171 |
\index{quit} {\bf (QUIT)} to do this. |
| 172 |
% (and sometimes twice!). |
| 173 |
In the later version of Reduce the situation is opposite: you are able |
| 174 |
to use lowercase, but uppercase produces errors. Conclusion: try |
| 175 |
both in troubles! |
| 176 |
|
| 177 |
Note also that a typical mistake is to forget one of the right parenthesis or |
| 178 |
quotes ({\bf '' }). So maybe a couple of them might be useful to leave |
| 179 |
Lisp safely. |
| 180 |
|
| 181 |
During the session you can get some kind of messages from Lisp. |
| 182 |
All of them start with stars. The message that starts from five stars |
| 183 |
$*****$ means an error. Three stars $***$ mean a minor error or |
| 184 |
only a warning -- |
| 185 |
it is possible to continue the work. |
| 186 |
\begin{exm}. Here we forget to write the parenthesis. |
| 187 |
\end{exm} |
| 188 |
|
| 189 |
{\bf |
| 190 |
2 lisp$>$ simple |
| 191 |
|
| 192 |
***** `simple' is an unbound ID |
| 193 |
|
| 194 |
3 lisp$>$ |
| 195 |
} |
| 196 |
|
| 197 |
|
| 198 |
|
| 199 |
|
| 200 |
|
| 201 |
\section{Simplest calculations in {\bf bergman}} |
| 202 |
|
| 203 |
Here we describe and explain |
| 204 |
several examples that you can easily copy and modify. |
| 205 |
|
| 206 |
|
| 207 |
The simplest way to employ {\bf bergman} is to start it, to use some |
| 208 |
specially written routines |
| 209 |
such as |
| 210 |
\index{simple} {\bf simple} or \index{ncpbhgroebner} {\bf |
| 211 |
ncpbhgroebner,} to |
| 212 |
feed it input interactively or by means of an input file prepared in |
| 213 |
advance, and to quit. |
| 214 |
|
| 215 |
In a slightly more sophisticated use, you may |
| 216 |
influence the behavior by various "mode changing" procedures. |
| 217 |
|
| 218 |
In very sophisticated use, you may employ and expand the |
| 219 |
experimental procedures enclosed to the program, and/or interact |
| 220 |
directly with the underlying lisp representations of the algebraic |
| 221 |
objects. |
| 222 |
|
| 223 |
You also have access to all source code and can use all procedures |
| 224 |
to implement your own applications. |
| 225 |
|
| 226 |
This chapter covers the first use. For more |
| 227 |
sophisticated use guidance see the next chapters. |
| 228 |
|
| 229 |
\subsection{Selecting alternatives} |
| 230 |
|
| 231 |
{\bf Bergman} works in different modes. You can find a full overview of these |
| 232 |
in \ref{refm}. |
| 233 |
|
| 234 |
To perform some computations in {\bf bergman} it is necessary at least |
| 235 |
to set up the polynomial ring selecting commutative or non-commutative |
| 236 |
alternative, \index{ordering} ordering \index{degrevlexify} ({\bf degrevlexify} or |
| 237 |
\index{deglexify} {\bf deglexify}), |
| 238 |
\index{coefficients} coefficients field |
| 239 |
(characteristic \index{characteristic} 0, 2 or arbitrary prime), |
| 240 |
\index{weights} weights of variables etc. |
| 241 |
|
| 242 |
For the first examples we skip the complete description of alternatives |
| 243 |
using the corresponding setting included in the main top level procedures. |
| 244 |
We shall distinguish here only commutative and non-commutative calculations. |
| 245 |
|
| 246 |
\subsection{Commutative algebras} |
| 247 |
|
| 248 |
|
| 249 |
|
| 250 |
Let us start with an example of \index{Gr\"{o}bner basis} Gr\"{o}bner |
| 251 |
basis computation for an ideal. |
| 252 |
It will be performed by the procedure \index{simple} {\bf simple}. There are several |
| 253 |
way to call this procedure explained completely in \ref{procsimple}. |
| 254 |
Here we illustrate two of them. |
| 255 |
|
| 256 |
Calling {\bf simple} without arguments you can introduce the relations |
| 257 |
directly from the screen following the prompt and respecting one |
| 258 |
restriction: the relations must be homogeneous. Here is an example of |
| 259 |
the session: |
| 260 |
|
| 261 |
\begin{verbatim} |
| 262 |
1 lisp> (SIMPLE) |
| 263 |
Now input in-variables and ideal generators in |
| 264 |
algebraic form, thus: |
| 265 |
vars v1, ..., vn; |
| 266 |
r1, ..., rm; |
| 267 |
where v1, ..., vn are the variables, |
| 268 |
and r1, ..., rm the generators. |
| 269 |
algebraic form input> vars x,y;x^2-y^2,x*y; |
| 270 |
% 2 |
| 271 |
x*y, |
| 272 |
x^2-y^2, |
| 273 |
|
| 274 |
% 3 |
| 275 |
y^3, |
| 276 |
|
| 277 |
Done |
| 278 |
- All is OK (I hope). Now you may (e. g.): |
| 279 |
- kill bergman with (QUIT); or |
| 280 |
- interrupt bergman with ^Z; or |
| 281 |
- clear the memory with (CLEARIDEAL), |
| 282 |
and run a new (SIMPLE). |
| 283 |
nil |
| 284 |
2 lisp> |
| 285 |
\end{verbatim} |
| 286 |
|
| 287 |
The result contains three elements of Gr\"{o}bner basis : $x*y, x^2-y^2, y^3.$ |
| 288 |
Note that, according to the order of variables, $x$ (the first in the list) |
| 289 |
is highest, so $xx, xy$ and $yyy$ are highest monomials. |
| 290 |
Thus, only the monomials $ 1, x, y, yy$ are normal (not divisible by the |
| 291 |
highest monomials) and serve as a basis of our algebra. Its |
| 292 |
dimension is equal to 4 and we can easily create a multiplication table too. |
| 293 |
(All elements of the Gr\"{o}bner basis are equal to zero in the |
| 294 |
quotient algebra, so we can |
| 295 |
use their highest terms for the reduction of non-normal words). |
| 296 |
For example, $x*x=yy$, $yx=yx$, $y*yy=0$, $x*yy=0$. |
| 297 |
|
| 298 |
As was said above, \index{simple} {\bf simple} may be called in several ways. One |
| 299 |
of them is to perform input and output by means of files. |
| 300 |
Let us prepare the following one (suppose that its name is "test1.a". |
| 301 |
Check its existence in the directory {\bf bergman/tests} and copy it |
| 302 |
into your current directory): |
| 303 |
|
| 304 |
{\bf |
| 305 |
\index{algforminput} (algforminput) |
| 306 |
|
| 307 |
vars x,y; |
| 308 |
|
| 309 |
x$*$x$-$y$*$y, x$*$y; |
| 310 |
} |
| 311 |
|
| 312 |
The first line informs {\bf bergman} that the succeeding lines are |
| 313 |
input data in the \index{algebraic form} algebraic form. It means that you need to write |
| 314 |
multiplication symbol $*$ or powers for example |
| 315 |
$ x\verb-^-2$ or $x**2$ instead of |
| 316 |
$x*x$ but not $xx$ |
| 317 |
(the same conventions as in Reduce or Maple). The other possibility is |
| 318 |
\index{Lisp form} Lisp--form; |
| 319 |
read about them in the subsection \ref{inputform}. |
| 320 |
|
| 321 |
The next two lines are input data themselves. The first one contains variables, they should be |
| 322 |
written between keyword \index{vars} {\bf vars} and semicolon. Then comes the |
| 323 |
defining relations, |
| 324 |
separated by commas and finished by semicolon. |
| 325 |
|
| 326 |
To start the calculation select the name for output file, for example |
| 327 |
"test1.bg" |
| 328 |
(it should not |
| 329 |
exists!), start {\bf bergman}, switch to the Lisp |
| 330 |
mode and write |
| 331 |
|
| 332 |
{\bf (simple "test1.a" "test1.bg")} |
| 333 |
|
| 334 |
(do not forget double quotes!) and then quit. |
| 335 |
|
| 336 |
The following is the full session of our work. |
| 337 |
|
| 338 |
\begin{verbatim} |
| 339 |
|
| 340 |
bergman |
| 341 |
|
| 342 |
7: end; |
| 343 |
Entering LISP ... |
| 344 |
Bergman 0.926, 23-Oct-98 |
| 345 |
1 lisp> (SIMPLE "test1.a" "test.bg") |
| 346 |
t |
| 347 |
- All is OK (I hope). Now you may (e. g.): |
| 348 |
- kill bergman with (QUIT); or |
| 349 |
- interrupt bergman with ^Z; or |
| 350 |
- clear the memory with (CLEARIDEAL), |
| 351 |
and run a new (SIMPLE). |
| 352 |
nil |
| 353 |
2 lisp> (quit) |
| 354 |
|
| 355 |
Quitting |
| 356 |
\end{verbatim} |
| 357 |
|
| 358 |
Here is the resulting file "test1.bg", containing Gr\"{o}bner basis |
| 359 |
\begin{verbatim} |
| 360 |
% 2 |
| 361 |
x*y, |
| 362 |
x^2-y^2, |
| 363 |
|
| 364 |
% 3 |
| 365 |
y^3, |
| 366 |
|
| 367 |
Done |
| 368 |
|
| 369 |
|
| 370 |
\end{verbatim} |
| 371 |
|
| 372 |
|
| 373 |
|
| 374 |
\subsection{Non-commutative algebras} |
| 375 |
|
| 376 |
The procedure \index{simple} {\bf simple} may be used to perform |
| 377 |
non-commutative \index{Gr\"{o}bner basis} Gr\"{o}bner basis computations also. |
| 378 |
{\bf Bergman} by default is in commutative mode, so, |
| 379 |
first of all we need to turn it to non-commutative calculations. |
| 380 |
|
| 381 |
Here is an example of the session: |
| 382 |
|
| 383 |
\begin{verbatim} |
| 384 |
2 lisp> (NONCOMMIFY) |
| 385 |
nil |
| 386 |
3 lisp> (SIMPLE) |
| 387 |
Now input in-variables and ideal generators in |
| 388 |
algebraic form, thus: |
| 389 |
vars v1, ..., vn; |
| 390 |
r1, ..., rm; |
| 391 |
where v1, ..., vn are the variables, |
| 392 |
and r1, ..., rm the generators. |
| 393 |
algebraic form input> vars x,y;x^2-y^2,x*y; |
| 394 |
% 2 |
| 395 |
x*y, |
| 396 |
-y^2+x^2, |
| 397 |
|
| 398 |
% 3 |
| 399 |
x^3, |
| 400 |
y*x^2, |
| 401 |
|
| 402 |
Done |
| 403 |
- All is OK (I hope). Now you may (e. g.): |
| 404 |
- kill bergman with (QUIT); or |
| 405 |
- interrupt bergman with ^Z; or |
| 406 |
- clear the memory with (CLEARIDEAL), |
| 407 |
and run a new (SIMPLE). |
| 408 |
nil |
| 409 |
4 lisp> |
| 410 |
|
| 411 |
|
| 412 |
\end{verbatim} |
| 413 |
|
| 414 |
|
| 415 |
|
| 416 |
Although variables and generators look the same as in the commutative case, we have, of course, different output of \index{Gr\"{o}bner basis} |
| 417 |
Gr\"{o}bner basis. |
| 418 |
|
| 419 |
According to the order of variables,$y$ (the last in the list -- |
| 420 |
opposite to the defaults in the commutative case) |
| 421 |
is the highest, so $ xy$, $yy$, $xxx$ and $yxx$ are the highest monomials. |
| 422 |
Thus only monomials $1$, $x$, $y$, $xx$, $yx$ are normal (do not contain the highest |
| 423 |
monomials as subwords) and serve as a basis of our algebra. Its |
| 424 |
dimension is equal to 5 and we can easily create a multiplication table too. |
| 425 |
(All elements of the Gr\"{o}bner basis are equal to zero in algebra, thus |
| 426 |
we can |
| 427 |
use their highest terms for the reduction of non-normal words). |
| 428 |
For example, $ x*x=xx$, $y*y=xx$, $x*xx=0$. |
| 429 |
|
| 430 |
In the non-commutative case the homogeneity restriction also must be |
| 431 |
respected. |
| 432 |
|
| 433 |
The input can be performed also by means of a file. |
| 434 |
Let us prepare the following one (suppose that its name is "test2.a". |
| 435 |
Check its existence in the directory {\bf bergman/tests} and copy it |
| 436 |
into your current directory): |
| 437 |
|
| 438 |
\index{noncommify} {\bf (noncommify) |
| 439 |
|
| 440 |
(setmaxdeg 10)} |
| 441 |
|
| 442 |
\index{algforminput} {\bf (algforminput) |
| 443 |
|
| 444 |
vars x,y; |
| 445 |
|
| 446 |
x$*$x$-$y$*$y,x$*$y; |
| 447 |
} |
| 448 |
|
| 449 |
The first line switches {\bf bergman} to the non-commutative mode. |
| 450 |
The second line was not necessary in this example. It restricts |
| 451 |
calculations up to degree 10. Here calculations stops in degree 3 |
| 452 |
(as you will see later), but in general \index{Gr\"{o}bner basis} |
| 453 |
Gr\"{o}bner basis might be |
| 454 |
infinite so it is recommended to restrict the degree of calculations |
| 455 |
(although {\bf bergman} will try to do them until the memory doesn't suffice). |
| 456 |
|
| 457 |
The third line informs {\bf bergman} that the following is input data in the |
| 458 |
\index{algebraic form} algebraic form. It means that you need to write multiplication |
| 459 |
symbol $*$ or powers for example $x\verb-^-2$ or |
| 460 |
$x**2$ instead of $ x*x$ but not $xx$ |
| 461 |
(the same as in Reduce or Maple). Another possibility is |
| 462 |
\index{Lisp form} Lisp--form; read about it in the section \ref{inputform}. |
| 463 |
|
| 464 |
The next two lines are input data themselves. The first contains variables, they should be |
| 465 |
written between keyword \index{vars} {\bf vars} and semicolon. Then the |
| 466 |
generators are listed, |
| 467 |
separated by commas and finished by a semicolon. |
| 468 |
|
| 469 |
To start the calculation select the name for output file, |
| 470 |
for example "test2.bg" (it should not |
| 471 |
exist!), for example "test2.bg", start {\bf bergman}, switch to the Lisp |
| 472 |
mode and write\\ |
| 473 |
{\bf (simple "test2.a" "test2.bg")}\\ |
| 474 |
(do not forget double quotes!) and then quit. |
| 475 |
|
| 476 |
The following is the full session of our work. |
| 477 |
|
| 478 |
\begin{verbatim} |
| 479 |
|
| 480 |
> bergman |
| 481 |
Bergman 0.926, 23-Oct-98 |
| 482 |
1 lisp> (simple "test2.a" "test2.bg") |
| 483 |
nil |
| 484 |
nil |
| 485 |
t |
| 486 |
- All is OK (I hope). Now you may (e. g.): |
| 487 |
- kill bergman with (QUIT); or |
| 488 |
- interrupt bergman with ^Z; or |
| 489 |
- clear the memory with (CLEARIDEAL), |
| 490 |
and run a new (SIMPLE). |
| 491 |
nil |
| 492 |
2 lisp> |
| 493 |
|
| 494 |
\end{verbatim} |
| 495 |
|
| 496 |
|
| 497 |
The file {\bf test2.bg} contains the corresponding \index{Gr\"{o}bner basis} |
| 498 |
Gr\"{o}bner basis: |
| 499 |
|
| 500 |
\begin{verbatim} |
| 501 |
|
| 502 |
% 2 |
| 503 |
x*y, |
| 504 |
-y^2+x^2, |
| 505 |
|
| 506 |
% 3 |
| 507 |
x^3, |
| 508 |
y*x^2, |
| 509 |
|
| 510 |
Done |
| 511 |
|
| 512 |
\end{verbatim} |
| 513 |
|
| 514 |
|
| 515 |
In the next example we use another procedure, working with \\ |
| 516 |
non-commutative algebras only and calculating besides the Gr\"{o}bner basis |
| 517 |
of the algebra the Hilbert and monomial \index{Poincar\'{e} series} |
| 518 |
Poincar\'{e} series. |
| 519 |
There is no screen input, we should use files only. |
| 520 |
We can use the same {\bf test2.a} |
| 521 |
for input and {\bf test2.bg } for output (supposing that the output file |
| 522 |
does not exist. If there is such file in your current directory remove |
| 523 |
or rename it) and want to get two new files: {\bf test2.hs} for |
| 524 |
the |
| 525 |
\index{Hilbert series} Hilbert series and {\bf test2.pb} for the Poincar\'e series. The procedure has |
| 526 |
a name \index{ncpbhgroebner} {\bf ncpbhgroebner} (from NonCommutative Poincar\'e--Betti and |
| 527 |
Hilbert series) |
| 528 |
and it always |
| 529 |
has 4 parameters. Here is a session (messages can be different): |
| 530 |
|
| 531 |
\begin{verbatim} |
| 532 |
1 lisp>(ncpbhgroebner "test2.a""test2.bg""test2.pb""test2.hs") |
| 533 |
*** I turn on noncommutativity |
| 534 |
nil |
| 535 |
10 |
| 536 |
nil |
| 537 |
*** Function `degreeenddisplay' has been redefined |
| 538 |
|
| 539 |
% No. of Spolynomials calculated until degree 2: 0 |
| 540 |
% No. of ReducePol(0) demanded until degree 2: 0 |
| 541 |
% Time: 425 |
| 542 |
|
| 543 |
% No. of Spolynomials calculated until degree 3: 2 |
| 544 |
% No. of ReducePol(0) demanded until degree 3: 0 |
| 545 |
% Time: 646 |
| 546 |
|
| 547 |
% No. of Spolynomials calculated until degree 4: 8 |
| 548 |
% No. of ReducePol(0) demanded until degree 4: 5 |
| 549 |
% Time: 833 |
| 550 |
*** Function `degreeenddisplay' has been redefined |
| 551 |
nil |
| 552 |
2 lisp> |
| 553 |
\end{verbatim} |
| 554 |
|
| 555 |
The file "test2.hs" for \index{Hilbert series} Hilbert series looks now as: |
| 556 |
|
| 557 |
\begin{verbatim} |
| 558 |
+2*z^2 |
| 559 |
+0*z^3 |
| 560 |
+0*z^4 |
| 561 |
\end{verbatim} |
| 562 |
|
| 563 |
(note that known from the very beginning part \verb- 1+2*z- is absent here), |
| 564 |
and the file "test2.pb" for the monomial \index{Poincar\'{e} series} |
| 565 |
Poincar\'{e} series looks as: |
| 566 |
|
| 567 |
|
| 568 |
|
| 569 |
\begin{verbatim} |
| 570 |
+t^2*(2*z^2) |
| 571 |
+t^3*(2*z^2+2*z^3) |
| 572 |
+t^4*(6*z^3+2*z^4) |
| 573 |
\end{verbatim} |
| 574 |
|
| 575 |
and also does not contain first terms \verb- 1+t*(2*z).- |
| 576 |
|
| 577 |
Note also that neither series contains terms in degree more |
| 578 |
than 4 -- the last degree where {\bf bergman} have done some calculations. |
| 579 |
Look to the next section if you need more terms. |
| 580 |
|
| 581 |
%But you will be especially surprised investigating "test2.bg." |
| 582 |
%It looks now as: |
| 583 |
|
| 584 |
%begin{verbatim} (the slash before begin and end were removed!!) |
| 585 |
% 2 |
| 586 |
%((1 1 2)) |
| 587 |
%((-1 2 2) (1 1 1)) |
| 588 |
|
| 589 |
% 3 |
| 590 |
%((1 1 1 1)) |
| 591 |
%((1 2 1 1)) |
| 592 |
|
| 593 |
%Done |
| 594 |
%end{verbatim} |
| 595 |
|
| 596 |
%It means that the result was written in the \index{Lisp form} Lisp--form. You %can try to |
| 597 |
%understand it (it is the same as before -- try to recognize it!) or |
| 598 |
%read more |
| 599 |
%about this in the subsection \ref{inputform}, but let us |
| 600 |
%now change the input file a little and name it "test3.bg." |
| 601 |
|
| 602 |
%\begin{verbatim} |
| 603 |
%(noncommify) |
| 604 |
%(setmaxdeg 10) |
| 605 |
%(setq algoutmode 'ALG) |
| 606 |
%(algforminput) |
| 607 |
%vars x,y; |
| 608 |
%x*x-y*y,x*y; |
| 609 |
%\end{verbatim} |
| 610 |
|
| 611 |
%The session now looks almost the same (but the message about \index{algebraic |
| 612 |
%form} algebraic form appeared): |
| 613 |
|
| 614 |
%\begin{verbatim} |
| 615 |
|
| 616 |
%1 lisp> (NCPBHGROEBNER "test3.a" "test3.bg" "test3.pbs" "test3.hs") |
| 617 |
%*** I turn on noncommutativity |
| 618 |
%nil |
| 619 |
%10 |
| 620 |
%alg |
| 621 |
%nil |
| 622 |
%*** Function `degreeenddisplay' has been redefined |
| 623 |
|
| 624 |
% No. of Spolynomials calculated until degree 2: 0 |
| 625 |
% No. of ReducePol(0) demanded until degree 2: 0 |
| 626 |
% Time: 442 |
| 627 |
|
| 628 |
% No. of Spolynomials calculated until degree 3: 2 |
| 629 |
% No. of ReducePol(0) demanded until degree 3: 0 |
| 630 |
% Time: 629 |
| 631 |
|
| 632 |
% No. of Spolynomials calculated until degree 4: 8 |
| 633 |
% No. of ReducePol(0) demanded until degree 4: 5 |
| 634 |
% Time: 833 |
| 635 |
%*** Function `degreeenddisplay' has been redefined |
| 636 |
%nil |
| 637 |
%2 lisp> |
| 638 |
|
| 639 |
%\end{verbatim} |
| 640 |
|
| 641 |
The file "test2.bg" is the same as "test2.bg" in the |
| 642 |
example with {\bf simple}: |
| 643 |
|
| 644 |
\begin{verbatim} |
| 645 |
|
| 646 |
% 2 |
| 647 |
x*y, |
| 648 |
-y^2+x^2, |
| 649 |
|
| 650 |
% 3 |
| 651 |
x^3, |
| 652 |
y*x^2, |
| 653 |
|
| 654 |
Done |
| 655 |
\end{verbatim} |
| 656 |
|
| 657 |
\subsection {Normal form and reduction} |
| 658 |
|
| 659 |
The main idea to use Gr\"{o}bner basis is to have a possibility to reduce |
| 660 |
a given |
| 661 |
element $u$ to its normal form. {\bf Bergman} suggests |
| 662 |
a simple procedure named \index{readtonormalform} {\bf readtonormalform} which interactively |
| 663 |
asks an input for a desired polynomial and prints its normal form - |
| 664 |
the result of the reduction. Let us consider a small example. |
| 665 |
Suppose that we want to check if two elements $a^3$ and $b^3$ commute |
| 666 |
in the non-commutative factor-algebra $A=<a,b|2*a^2-3*b^2>.$ |
| 667 |
The way to do it is the following:\\ |
| 668 |
1. First to calculate Gr\"{o}bner basis: |
| 669 |
|
| 670 |
\begin{verbatim} |
| 671 |
2 lisp> (noncommify) |
| 672 |
nil |
| 673 |
3 lisp> (simple) |
| 674 |
Now input in-variables and ideal generators in |
| 675 |
algebraic form, thus: |
| 676 |
vars v1, ..., vn; |
| 677 |
r1, ..., rm; |
| 678 |
where v1, ..., vn are the variables, |
| 679 |
and r1, ..., rm the generators. |
| 680 |
algebraic form input> vars a,b; 2*a^2-3*b^2; |
| 681 |
SetupGlobals |
| 682 |
... done |
| 683 |
+t^2*(z^2) |
| 684 |
% 2 |
| 685 |
-3*b^2+2*a^2, |
| 686 |
|
| 687 |
+t^3*(z^2+z^3) |
| 688 |
% 3 |
| 689 |
-b*a^2+a^2*b, |
| 690 |
|
| 691 |
+t^4*(z^3+z^4) |
| 692 |
Done |
| 693 |
- All is OK (I hope). Now you may (e. g.): |
| 694 |
- kill bergman with (QUIT); or |
| 695 |
- interrupt bergman with ^Z; or |
| 696 |
- clear the memory with (CLEARIDEAL), |
| 697 |
and run a new (SIMPLE). |
| 698 |
nil |
| 699 |
4 lisp> |
| 700 |
|
| 701 |
\end{verbatim} |
| 702 |
2.Check the commutator $a^3*b^3-b^3*a^3:$ |
| 703 |
|
| 704 |
\begin{verbatim} |
| 705 |
4 lisp> (readtonormalform) |
| 706 |
algebraic form input> a^3*b^3-b^3*a^3; |
| 707 |
|
| 708 |
is reduced to |
| 709 |
2/3*(-a^4*b*a+a^5*b), |
| 710 |
|
| 711 |
nil |
| 712 |
\end{verbatim} |
| 713 |
|
| 714 |
We see that the result (the normal form of the commutator) is nonzero, |
| 715 |
so, the polynomials are not commuting. Moreover, we know exactly how |
| 716 |
far from the zero the commutator is. The same computation |
| 717 |
with $a^4$ and $b^2$ gives us a different result: |
| 718 |
|
| 719 |
\begin{verbatim} |
| 720 |
5 lisp> (readtonormalform) |
| 721 |
algebraic form input> a^4*b^2-b^2*a^4; |
| 722 |
|
| 723 |
is reduced to |
| 724 |
0, |
| 725 |
\end{verbatim} |
| 726 |
|
| 727 |
and we can conclude that polynomials are commuting. More generally, |
| 728 |
the procedure {\bf readtonormalform} can be used for the equality |
| 729 |
test: $u=v$ in our factor-algebra if and only if their difference |
| 730 |
is reduced to zero. |
| 731 |
|
| 732 |
To be able to use the normal form in his own programs one can apply the |
| 733 |
following procedures: |
| 734 |
|
| 735 |
\begin{itemize} |
| 736 |
|
| 737 |
\item \index{readpol} {\bf (readpol l), } which reads the list $l$ of |
| 738 |
polynomials from the |
| 739 |
input, separated by the semicolons, |
| 740 |
|
| 741 |
\item \index{writepol}{\bf (writepol l), } which prints them on the screen, |
| 742 |
|
| 743 |
|
| 744 |
\item \index{reducepol}{\bf (reducepol a b), } which reduces the |
| 745 |
polynomial $a$ to the |
| 746 |
(printable) polynomial $b$, |
| 747 |
|
| 748 |
|
| 749 |
\item \index{prinqtpols} {\bf (prinqtpols b), } which prints (printable) polynomial. |
| 750 |
|
| 751 |
\end{itemize} |
| 752 |
|
| 753 |
Note the difference between inner form of the polynomial, which normally is |
| 754 |
unprintable and external, printable form. |
| 755 |
|
| 756 |
\subsection {Starting a new calculation: the procedure {\bf clearideal}} |
| 757 |
|
| 758 |
|
| 759 |
We hope that your first experiments with {\bf bergman} were successful and |
| 760 |
following the prompt after calculations you can: |
| 761 |
|
| 762 |
\begin{itemize} |
| 763 |
\item kill {\bf bergman} with (QUIT); or |
| 764 |
\item interrupt {\bf bergman} with \verb- ^Z -; or |
| 765 |
\item clear the memory with (CLEARIDEAL), and run a new (SIMPLE). |
| 766 |
\end{itemize} |
| 767 |
|
| 768 |
Presuming you would like to run a new computation |
| 769 |
let us explain more carefully what the function \index{clearideal} |
| 770 |
{\bf clearideal} is doing. |
| 771 |
|
| 772 |
According to its name it does not clear all that was done before, but |
| 773 |
only clear memory from the ideal generators and results of the previous |
| 774 |
calculations. |
| 775 |
|
| 776 |
You always {\it should} call this function before starting a new cycle of |
| 777 |
the calculations. The only exclusion is when you want to add some |
| 778 |
new elements to the already calculated Gr\"{o}bner basis or use the |
| 779 |
Gr\"{o}bner basis for reduction, but for doing this kind of |
| 780 |
staff you should be a professional. So, once again, in this chapter: |
| 781 |
{\em before the calling second time one of the top--of--the--top |
| 782 |
procedures, such |
| 783 |
as} {\bf simple, ncpbhgroebner} {\em always call} {\bf clearideal} |
| 784 |
|
| 785 |
You need not do it from the very beginning, but you need to know |
| 786 |
what it really clears. {\em It clears:} |
| 787 |
\begin{itemize} |
| 788 |
\item initial generators, |
| 789 |
\item calculated Gr\"{o}bner basis, |
| 790 |
\item all the memory, used for the calculations. |
| 791 |
\end{itemize} |
| 792 |
|
| 793 |
{\em It saves:} |
| 794 |
\begin{itemize} |
| 795 |
\item all selected modes (see section \ref{modes}), including |
| 796 |
list of input variables. |
| 797 |
\end{itemize} |
| 798 |
|
| 799 |
|
| 800 |
|
| 801 |
You can use this possibility: {\em do not introduce the same set of variables, |
| 802 |
skipping } {\bf vars \ldots} |
| 803 |
|
| 804 |
\begin{exm}. Several computations in the same polynomial ring with |
| 805 |
different ideals. |
| 806 |
\end{exm} |
| 807 |
|
| 808 |
\begin{verbatim} |
| 809 |
|
| 810 |
1 lisp> (simple) |
| 811 |
Now input in-variables and ideal generators |
| 812 |
in algebraic form, thus: |
| 813 |
vars v1, ..., vn; |
| 814 |
r1, ..., rm; |
| 815 |
where v1, ..., vn are the variables, |
| 816 |
and r1, ..., rm the generators. |
| 817 |
algebraic form input> vars x,y,z; |
| 818 |
algebraic form input> x^3, x^2*y-y^2*x, z^2*x, x^2*z-y^2*z; |
| 819 |
% 3 |
| 820 |
x*z^2, |
| 821 |
x^2*z-y^2*z, |
| 822 |
x^2*y-x*y^2, |
| 823 |
x^3, |
| 824 |
|
| 825 |
% 4 |
| 826 |
y^2*z^2, |
| 827 |
y^3*z, |
| 828 |
x*y^2*z, |
| 829 |
x*y^3, |
| 830 |
|
| 831 |
Done |
| 832 |
- All is OK (I hope). Now you may (e. g.): |
| 833 |
- kill bergman with (QUIT); or |
| 834 |
- interrupt bergman with ^Z; or |
| 835 |
- clear the memory with (CLEARIDEAL), |
| 836 |
and run a new (SIMPLE). |
| 837 |
nil |
| 838 |
2 lisp> (clearideal) |
| 839 |
nil |
| 840 |
3 lisp> (simple) |
| 841 |
Now input in-variables and ideal generators |
| 842 |
in algebraic form, thus: |
| 843 |
vars v1, ..., vn; |
| 844 |
r1, ..., rm; |
| 845 |
where v1, ..., vn are the variables, |
| 846 |
and r1, ..., rm the generators. |
| 847 |
algebraic form input> y*z^2-z^3, x^2*z-y*z^2, x*y*z; |
| 848 |
% 3 |
| 849 |
y*z^2-z^3, |
| 850 |
x*y*z, |
| 851 |
x^2*z-z^3, |
| 852 |
|
| 853 |
% 4 |
| 854 |
z^4, |
| 855 |
x*z^3, |
| 856 |
|
| 857 |
Done |
| 858 |
- All is OK (I hope). Now you may (e. g.): |
| 859 |
- kill bergman with (QUIT); or |
| 860 |
- interrupt bergman with ^Z; or |
| 861 |
- clear the memory with (CLEARIDEAL), |
| 862 |
and run a new (SIMPLE). |
| 863 |
nil |
| 864 |
4 lisp> |
| 865 |
|
| 866 |
\end{verbatim} |
| 867 |
|
| 868 |
One should take in account the previous settings in order to avoid |
| 869 |
strange situations, when the well known procedure yields some unexpected |
| 870 |
results. It might happens, for example, if you have computed the Gr\"{o}bner basis |
| 871 |
in non-commutaive mode, forgot about this setting and start a new {\bf simple} |
| 872 |
expecting the commutative calculations and seeing a strange result. |
| 873 |
|
| 874 |
The situation will surprise you even more |
| 875 |
in the case, when you computed the Anick resolution (which assigns to the |
| 876 |
resolution type the value ``anick''), call {\bf clearideal}, setup |
| 877 |
{\bf (commify)} and start |
| 878 |
{\bf simple} obtaining in a surprising way an output with Betti numbers! |
| 879 |
(which, by the way, are very far from the real ones). |
| 880 |
To avoid this one should call the function {\bf (setresolutiontype nil)}. |
| 881 |
|
| 882 |
In order to check the current setup one can apply the function |
| 883 |
\index{getsetup} {\bf getsetup} |
| 884 |
which provides some useful information: |
| 885 |
|
| 886 |
\begin{verbatim} |
| 887 |
|
| 888 |
1 lisp> (getsetup) |
| 889 |
((objecttype ring (autoaddrelationstate nil nil)) |
| 890 |
(resolutiontype none) |
| 891 |
(variablesetup |
| 892 |
(ringtype commutative) |
| 893 |
(commutativeorder tdegrevlex) |
| 894 |
(noncommutativeorder tdegleftlex) |
| 895 |
(variablenumber nil) |
| 896 |
(invariables nil) |
| 897 |
(outvariables nil) |
| 898 |
(variableweights nil)) |
| 899 |
(strategy |
| 900 |
(mindeg nil) |
| 901 |
(maxdeg nil) |
| 902 |
(interruption ordinary)) |
| 903 |
(coefficientdomain nil (oddprimesmoduli ordinary)) |
| 904 |
(inputformat casesensalgin) |
| 905 |
(outputformat lisp exptsprint) |
| 906 |
(variousflags |
| 907 |
(custshow off) |
| 908 |
(custstrategy off) |
| 909 |
(degreeprintoutput off) |
| 910 |
(dynamiclogtables off) |
| 911 |
(homogenised off) |
| 912 |
(immediatecrit off) |
| 913 |
(immediatefullreduction on) |
| 914 |
(immediaterecdefine off) |
| 915 |
(nobignum off) |
| 916 |
(obsoletenamesinform off) |
| 917 |
(oldprintmodes1 off) |
| 918 |
(oldseriesmodes1 on) |
| 919 |
(standardanickmodes on) |
| 920 |
(pbseries off) |
| 921 |
(reductivity on) |
| 922 |
(savedegree off) |
| 923 |
(saverecvalues on))) |
| 924 |
|
| 925 |
\end{verbatim} |
| 926 |
|
| 927 |
All this setting will be explained below, in the appropriate place |
| 928 |
(in particular, into the Section ``Debugging in {\bf bergman}'') |
| 929 |
|
| 930 |
|
| 931 |
|
| 932 |
%The {\bf clearideal} procedure has an obsolete synonym {\bf clearall}. |
| 933 |
|
| 934 |
|
| 935 |
|
| 936 |
|
| 937 |
|
| 938 |
|
| 939 |
|
| 940 |
|