| 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 |
|