The Gröbner Basis package

*grobner$-$debug*

$\parbox{\pboxargslen}{\em nil \/}$ [VARIABLE]

If T, produce debugging and tracing output.

*buchberger$-$merge$-$pairs*

$\parbox{\pboxargslen}{\em 'buchberger$-$merge$-$pairs$-$smallest$-$lcm \/}$ [VARIABLE]

A variable holding the predicate used to sort critical pairs in the order of decreasing priority for the Buchberger algorithm.

*gebauer$-$moeller$-$merge$-$pairs*

$\parbox{\pboxargslen}{\em 'gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly \/}$ [VARIABLE]

A variable holding the predicate used to sort critical pairs in the order of decreasing priority for the Gebauer$-$Moeller algorithm

*grobner$-$function*

$\parbox{\pboxargslen}{\em 'buchberger \/}$ [VARIABLE]

The name of the function used to calculate Grobner basis

select$-$grobner$-$algorithm

$\parbox{\pboxargslen}{\em algorithm \/}$ [FUNCTION]

Select one of the several implementations of the Grobner basis algorithm.

grobner

$\parbox{\pboxargslen}{\em f {\sf \&optional} (pred \char93 'lex$\gt$) (start 0) (top$-$reduction$-$only nil) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Return Grobner basis of an ideal generated by polynomial list F. Assume that the monomials of each polynomial are ordered according to the admissible monomial order PRED. The result will be a list of polynomials ordered as well according to PRED. The polynomials from 0 to START$-$1 in the list F are assumed to be a Grobner basis, and thus certain critical pairs do not have to be calculated. If TOP$-$REDUCTION$-$ONLY is not NIL then only top reductions will be performed, instead of full division, and thus the returned Grobner basis will have its polynomials only top$-$reduced with respect to the preceding polynomials. RING should be set to the RING structure (see COEFFICIENT$-$RING package) corresponding to the coefficients of the polynomials in the list F. This function is currently just an interface to several algorithms which fine Grobner bases. Use SELECT$-$GROBNER$-$ALGORITHM in order to change the algorithm.

debug$-$cgb

$\parbox{\pboxargslen}{\em {\sf \&rest} args \/}$ [MACRO]

This macro is used in printing debugging and tracing messages and its arguments are analogous to the FORMAT function, except that the stream argument is omitted. By default, the output is sent to *trace$-$output*, which can be set to produce output in a file.

spoly

$\parbox{\pboxargslen}{\em f g pred ring \/}$ [FUNCTION]

Return the S$-$polynomial of F and G, which should be two polynomials with terms ordered by PRED and coefficients in a ring whose operations are the slots of the RING structure.

grobner$-$primitive$-$part

$\parbox{\pboxargslen}{\em p ring \/}$ [FUNCTION]

Divide polynomial P with integer coefficients by gcd of its coefficients and return the result. Use the RING structure from the COEFFICIENT$-$RING package to perform the operations on the coefficients.

grobner$-$content

$\parbox{\pboxargslen}{\em p ring \/}$ [FUNCTION]

Greatest common divisor of the coefficients of the polynomial P. Use the RING structure to compute the greatest common divisor.

normal$-$form

$\parbox{\pboxargslen}{\em f fl pred top$-$reduction$-$only ring \/}$ [FUNCTION]

Calculate the normal form of the polynomial F with respect to the polynomial list FL. Destructive to F; thus, copy$-$tree should be used where F needs to be preserved. It returns multiple values. The first value is the polynomial R which is reduced (or top$-$reduced if TOP$-$REDUCTION$-$ONLY is not NIL). The second value is an integer which is the number of reductions actually performed. The third value is the coefficient by which F needs to be multiplied in order to be able to perform the division without actually having to divide in the coefficient ring (a form of pseudo$-$division is used). All operations on the coefficients are performed using the RING structure from the COEFFICIENT$-$RING package.

buchberger

$\parbox{\pboxargslen}{\em f pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$\space (length f))) b m \/}$ [FUNCTION]

An implementation of the Buchberger algorithm. Return Grobner basis of the ideal generated by the polynomial list F. The terms of each polynomial are ordered by the admissible monomial order PRED. Polynomials 0 to START$-$1 are assumed to be a Grobner basis already, so that certain critical pairs will not be examined. If TOP$-$REDUCTION$-$ONLY set, top reduction will be preformed. The RING structure is used to perform operations on coefficents (see COEFFICIENT$-$RING package).

grobner$-$op

$\parbox{\pboxargslen}{\em c1 c2 m a b pred ring {\sf \&aux} n a1 a2 \/}$ [FUNCTION]

Perform a calculation equivalent to (POLY$-$ (SCALAR$-$TIMES$-$POLY C2 A) (SCALAR$-$TIMES$-$POLY C1 (MONOM$-$TIMES$-$POLY M B)) PRED) but more efficiently; it destructively modifies A and stores the result in it; A is returned.

buchberger$-$sort$-$pairs

$\parbox{\pboxargslen}{\em b g pred ring \/}$ [FUNCTION]

Sort critical pairs B by the function which is the value of the vairable *buchberger$-$merge$-$pairs*. G is the list of polynomials which the elemnts of B point into. PRED is the admissible monomial order. The RING structure holds operations on the coefficients as described in the COEFFICIENT$-$RING package.

mock$-$spoly

$\parbox{\pboxargslen}{\em f g pred \/}$ [FUNCTION]

Returns an upper$-$bound on the leading monomial of the S$-$polynomial of F and G, which are two polynomials sorted by the admissible monomial order PRED.

buchberger$-$merge$-$pairs$-$use$-$mock$-$spoly

$\parbox{\pboxargslen}{\em b c g pred ring \/}$ [FUNCTION]

Merges lists of critical pairs B and C into one list. The pairs are assumed to be ordered according to the increasing value of MOCK$-$SPOLY, as determined by the admissible monomial order PRED. G is the list of polynomials which the pairs of integers in B and C point into, and RING is the ring structure defined in the COEFFICIENT$-$RING package.

buchberger$-$merge$-$pairs$-$smallest$-$lcm

$\parbox{\pboxargslen}{\em b c g pred ring \/}$ [FUNCTION]

Merges lists of critical pairs B and C into a single ordered list. Implements a strategy of ordering pairs according to the smallest lcm of the leading monomials of the two polynomials $-$ so called normal strategy.

buchberger$-$merge$-$pairs$-$use$-$smallest$-$degree

$\parbox{\pboxargslen}{\em b c g pred ring \/}$ [FUNCTION]

Mergest lists B and C of critical pairs. This strategy is based on ordering the pairs according to the smallest degree of the lcm of the leading monomials of the two polynomials.

buchberger$-$merge$-$pairs$-$use$-$smallest$-$length

$\parbox{\pboxargslen}{\em b c g pred ring \/}$ [FUNCTION]

Mergest lists B and C of critical pairs. This strategy is based on ordering the pairs according to the smallest total length of the two polynomials, where length is the number of terms.

buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length

$\parbox{\pboxargslen}{\em b c g pred ring \/}$ [FUNCTION]

Mergest lists B and C of critical pairs. This strategy is based on ordering the pairs according to the smallest combined length of the coefficients of the two polynomials.

buchberger$-$set$-$pair$-$heuristic

$\parbox{\pboxargslen}{\em method {\sf \&aux} (strategy$-$fn (ecase ... ...ar93 'buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) \/}$ [FUNCTION]

Simply sets the variable *buchberger$-$merge$-$pairs* to the heuristic function STRATEGY$-$FN implementing one of several strategies introduces before of selecting the most promising. METHOD should be one of the listed keywords.

criterion$-$1

$\parbox{\pboxargslen}{\em pair g {\sf \&aux} (i (first pair)) (j (second pair)) \/}$ [FUNCTION]

Returns T if the leading monomials of the two polynomials in G pointed to by the integers in PAIR have disjoint (relatively prime) monomials. This test is known as the first Buchberger criterion.

criterion$-$2

$\parbox{\pboxargslen}{\em pair g m {\sf \&aux} (i (first pair)) (j (second pair)) \/}$ [FUNCTION]

Returns T if the leading monomial of some element P of G divides the LCM of the leading monomials of the two polynomials in the polynomial list G, pointed to by the two integers in PAIR, and P paired with each of the polynomials pointed to by the the PAIR has already been treated, as indicated by the hash table M, which stores value T for every treated pair so far.

normalize$-$poly

$\parbox{\pboxargslen}{\em p ring \/}$ [FUNCTION]

Divide a polynomial by its leading coefficient. It assumes that the division is possible, which may not always be the case in rings which are not fields. The exact division operator is assumed to be provided by the RING structure of the COEFFICIENT$-$RING package.

normalize$-$basis

$\parbox{\pboxargslen}{\em plist ring \/}$ [FUNCTION]

Divide every polynomial in a list PLIST by its leading coefficient. Use RING structure to perform the division of the coefficients.

reduction

$\parbox{\pboxargslen}{\em p pred ring \/}$ [FUNCTION]

Reduce a list of polynomials P, so that non of the terms in any of the polynomials is divisible by a leading monomial of another polynomial. Return the reduced list.

reduced$-$grobner

$\parbox{\pboxargslen}{\em f {\sf \&optional} (pred \char93 'lex$\gt$) (start 0) (top$-$reduction$-$only nil) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Return the reduced Grobner basis of the ideal generated by a polynomial list F. This combines calls to two functions: GROBNER and REDUCTION. The parameters have the same meaning as in GROBNER or BUCHBERGER.

monom$-$depends$-$p

$\parbox{\pboxargslen}{\em m k \/}$ [FUNCTION]

Return T if the monomial M depends on variable number K.

term$-$depends$-$p

$\parbox{\pboxargslen}{\em term k \/}$ [FUNCTION]

Return T if the term TERM depends on variable number K.

poly$-$depends$-$p

$\parbox{\pboxargslen}{\em p k \/}$ [FUNCTION]

Return T if the term polynomial P depends on variable number K.

ring$-$intersection

$\parbox{\pboxargslen}{\em plist k {\sf \&key} (key \char93 'identity) \/}$ [FUNCTION]

This function assumes that polynomial list PLIST is a Grobner basis and it calculates the intersection with the ring R[x[k+1],...,x[n]], i.e. it discards polynomials which depend on variables x[0], x[1], ..., x[k].

elimination$-$ideal

$\parbox{\pboxargslen}{\em flist k {\sf \&key} (primary$-$order \char... ...ondary$-$order)) (top$-$reduction$-$only nil) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Returns the K$-$th elimination ideal of the ideal generated by polynomial list FLIST. Thus, a Grobner basis of the ideal generated by FLIST is calculated and polynomials depending on variables 0$-$K are discarded. The monomial order in the calculation is an elimination order formed by combining two orders: PRIMARY$-$ORDER used on variables 0$-$K and SECONDARY$-$ORDER used on variables starting from variable K+1. Thus, if both orders are set to the lexicographic order #'LEX$>$ then the resulting order is simply equivalent to #'LEX$>$. But one could use arbitrary two orders in this function, for instance, two copies of #'GREVLEX$>$ (see ORDER package). When doing so, the caller must ensure that the same order has been used to sort the terms of the polynomials FLIST.

ideal$-$intersection

$\parbox{\pboxargslen}{\em f g pred top$-$reduction$-$only ring \/}$ [FUNCTION]

Return the Grobner basis of the intersection of the ideals generated by the polynomial lists F and G. PRED is an admissible monomial order with respect to which the terms of F and G have been sorted. This order is going to be used in the Grobner basis calculation. If TOP$-$REDUCTION$-$ONLY is not NIL, internally the Grobner basis algorithm will perform top reduction only. The RING parameter, as usual, should be set to a structure defined in the package COEFFICIENT$-$RING, and it will be used to perform all operations on coefficients.

poly$-$contract

$\parbox{\pboxargslen}{\em f {\sf \&optional} (k 1) \/}$ [FUNCTION]

Return a polynomial obtained from polynomial F by dropping the first K variables, if F does not depend on them. Note that this operation makes the polynomial incompatible for certain arithmetical operations with the original polynomial F. Calling this function on a polynomial F which does depend on variables 0$-$K will result in error.

poly$-$lcm

$\parbox{\pboxargslen}{\em f g {\sf \&optional} (pred \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Return LCM (least common multiple) of two polynomials F and G. The polynomials must be ordered according to monomial order PRED and their coefficients must be compatible with the RING structure defined in the COEFFICIENT$-$RING package.

grobner$-$gcd

$\parbox{\pboxargslen}{\em f g {\sf \&optional} (pred \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Return GCD (greatest common divisor) of two polynomials F and G. The polynomials must be ordered according to monomial order PRED and their coefficients must be compatible with the RING structure defined in the COEFFICIENT$-$RING package.

grobner$-$equal

$\parbox{\pboxargslen}{\em g1 g2 {\sf \&optional} (pred \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Returns T if two lists of polynomials G1 and G2, assumed to be Grobner bases, generate the same ideal, and NIL otherwise.

grobner$-$subsetp

$\parbox{\pboxargslen}{\em g1 g2 {\sf \&optional} (pred \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Returns T if a list of polynomials G1 generates an ideal contained in the ideal generated by a polynomial list G2, both G1 and G2 assumed to be Grobner bases. Returns NIL otherwise.

grobner$-$member

$\parbox{\pboxargslen}{\em p g {\sf \&optional} (pred \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Returns T if a polynomial P belongs to the ideal generated by the polynomial list G, which is assumed to be a Grobner basis. Returns NIL otherwise.

ideal$-$equal

$\parbox{\pboxargslen}{\em f1 f2 pred top$-$reduction$-$only ring \/}$ [FUNCTION]

Returns T if two ideals generated by polynomial lists F1 and F2 are identical. Returns NIL otherwise.

ideal$-$subsetp

$\parbox{\pboxargslen}{\em f1 f2 {\sf \&optional} (pred \char93 'lex$\gt$) (ring *coefficient$-$ring*) \/}$ [FUNCTION]

Returns T if the ideal spanned by the polynomial list F1 is contained in the ideal spanned by the polynomial list F2. Returns NIL otherwise.

ideal$-$member

$\parbox{\pboxargslen}{\em p plist pred top$-$reduction$-$only ring \/}$ [FUNCTION]

Returns T if the polynomial P belongs to the ideal spanned by the polynomial list PLIST, and NIL otherwise.

ideal$-$saturation$-$1

$\parbox{\pboxargslen}{\em f p pred start top$-$reduction$-$only ring {\sf \&aux} (pred (elimination$-$order$-$1 pred)) \/}$ [FUNCTION]

Returns the reduced Grobner basis of the saturation of the ideal generated by a polynomial list F in the ideal generated by a single polynomial P. The saturation ideal is defined as the set of polynomials H such for some natural number n (* (EXPT P N) H) is in the ideal F. Geometrically, over an algebraically closed field, this is the set of polynomials in the ideal generated by F which do not identically vanish on the variety of P.

add$-$variables

$\parbox{\pboxargslen}{\em plist n \/}$ [FUNCTION]

Add N new variables, adn the first N variables, to every polynomial in polynomial list PLIST. The resulting polynomial will not depend on these N variables.

extend$-$polynomials

$\parbox{\pboxargslen}{\em plist {\sf \&aux} (k (length plist)) \/}$ [FUNCTION]

Returns polynomial list {U1*P1', U2*P2', ... , UK*PK'} where Ui are new variables and PLIST={P1, P2, ... , PK} is a polynomial list. PI' is obtained from PI by adding new variables U1, U2, ..., UN UK as the first K variables. Thus, the resulting list is consists of polynomials whose terms are ordered by the lexicographic order on variables UI, with ties resolved by the monomial order which was used to order the terms of the polynomials in PLIST. We note that the monomial order does not explicitly participate in this calculation, and neither do the variable names.

saturation$-$extension

$\parbox{\pboxargslen}{\em f plist ring {\sf \&aux} (k (length plist)) (d (+ k (length (caaar plist)))) \/}$ [FUNCTION]

Returns F' union {U1*P1$-$1,U2*P2$-$1,...,UK*PK$-$1} where Ui are new variables and F' is a polynomial list obtained from F by adding variables U1, U2, ..., Uk as the first K variables to each polynomial in F. Thus, the resulting list is consists of polynomials whose terms are ordered by the lexicographic order on variables Ui, with ties resolved by the monomial order which was used to order the terms of the polynomials in F. We note that the monomial order does not explicitly participate in this calculation, and neither do the variable names.

polysaturation$-$extension

$\parbox{\pboxargslen}{\em f plist ring {\sf \&aux} (k (length plist)) (d (+ k (length (caaar plist)))) \/}$ [FUNCTION]

Returns F' union {U1*P1+U2*P2+UK*PK$-$1} where Ui are new variables and F' is a polynomial list obtained from F by adding variables U1, U2, ..., Uk as the first K variables to each polynomial in F. Thus, the resulting list is consists of polynomials whose terms are ordered by the lexicographic order on variables Ui, with ties resolved by the monomial order which was used to order the terms of the polynomials in F. We note that the monomial order does not explicitly participate in this calculation, and neither do the variable names.

saturation$-$extension$-$1

$\parbox{\pboxargslen}{\em f p ring \/}$ [FUNCTION]

Return the list F' union {U*P$-$1} where U is a new variable, where F' is obtained from the polynomial list F by adding U as the first variable. The variable U will be added as the first variable, so that it can be easily eliminated.

ideal$-$polysaturation$-$1

$\parbox{\pboxargslen}{\em f plist pred start top$-$reduction$-$only ring \/}$ [FUNCTION]

Returns the reduced Grobner basis of the ideal obtained by a sequence of successive saturations in the polynomials of the polynomial list PLIST of the ideal generated by the polynomial list F.

ideal$-$saturation

$\parbox{\pboxargslen}{\em f g pred start top$-$reduction$-$only ring ... ...$order k :primary$-$order \char93 'lex$\gt$\space :secondary$-$order pred)) \/}$ [FUNCTION]

Returns the reduced Grobner basis of the saturation of the ideal generated by a polynomial list F in the ideal generated a polynomial list G The saturation ideal is defined as the set of polynomials H such for some natural number n and some P in the ideal generated by G the polynomial P**N * H is in the ideal spanned by F. Geometrically, over an algebraically closed field, this is the set of polynomials in the ideal generated by F which do not identically vanish on the variety of G.

ideal$-$polysaturation

$\parbox{\pboxargslen}{\em f ideal$-$list pred start top$-$reduction$-$only ring \/}$ [FUNCTION]

Returns the reduced Grobner basis of the ideal obtained by a successive applications of IDEAL$-$SATURATIONS to F and lists of polynomials in the list IDEAL$-$LIST.

buchberger$-$criterion

$\parbox{\pboxargslen}{\em g pred ring \/}$ [FUNCTION]

Returns T if G is a Grobner basis, by using the Buchberger criterion: for every two polynomials h1 and h2 in G the S$-$polynomial S(h1,h2) reduces to 0 modulo G.

grobner$-$test

$\parbox{\pboxargslen}{\em g f pred ring \/}$ [FUNCTION]

Test whether G is a Grobner basis and F is contained in G. Return T upon success and NIL otherwise.

minimization

$\parbox{\pboxargslen}{\em p pred \/}$ [FUNCTION]

Returns a sublist of the polynomial list P spanning the same monomial ideal as P but minimal, i.e. no leading monomial of a polynomial in the sublist divides the leading monomial of another polynomial.

add$-$minimized

$\parbox{\pboxargslen}{\em f gred pred \/}$ [FUNCTION]

Adds a polynomial f to GRED, reduced Grobner basis, preserving the property described in the documentation for MINIMIZATION.

colon$-$ideal

$\parbox{\pboxargslen}{\em f g pred top$-$reduction$-$only ring \/}$ [FUNCTION]

Returns the reduced Grobner basis of the colon ideal Id(F):Id(G), where F and G are two lists of polynomials. The colon ideal I:J is defined as the set of polynomials H such that there is a polynomial W in J for which W*H belongs to I.

colon$-$ideal$-$1

$\parbox{\pboxargslen}{\em f g pred top$-$reduction$-$only ring \/}$ [FUNCTION]

Returns the reduced Grobner basis of the colon ideal Id(F):Id({G}), where F is a list of polynomials and G is a polynomial.

pseudo$-$divide

$\parbox{\pboxargslen}{\em f fl pred ring \/}$ [FUNCTION]

Pseudo$-$divide a polynomial F by the list of polynomials FL. Return multiple values. The first value is a list of quotients A. The second value is the remainder R. The third value is an integer count of the number of reductions performed. Finally, the fourth argument is a scalar coefficient C, such that C*F can be divided by FL within the ring of coefficients, which is not necessarily a field. The resulting objects satisfy the equation: C*F= sum A[i]*FL[i] + R

gebauer$-$moeller

$\parbox{\pboxargslen}{\em f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 \/}$ [FUNCTION]

Compute Grobner basis by using the algorithm of Gebauer and Moeller. This algorithm is described as BUCHBERGERNEW2 in the book by Becker$-$Weispfenning entitled ``Grobner Bases''

update

$\parbox{\pboxargslen}{\em g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair \/}$ [FUNCTION]

An implementation of the auxillary UPDATE algorithm used by the Gebauer$-$Moeller algorithm. G is a list of polynomials, B is a list of critical pairs and H is a new polynomial which possibly will be added to G. The naming conventions used are very close to the one used in the book of Becker$-$Weispfenning.

gebauer$-$moeller$-$merge$-$pairs$-$use$-$mock$-$spoly

$\parbox{\pboxargslen}{\em b c pred ring \/}$ [FUNCTION]

The merging strategy used by the Gebauer$-$Moeller algorithm, based on MOCK$-$SPOLY; see the documentation of BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$MOCK$-$SPOLY.

gebauer$-$moeller$-$merge$-$pairs$-$smallest$-$lcm

$\parbox{\pboxargslen}{\em b c pred ring \/}$ [FUNCTION]

The merging strategy based on the smallest$-$lcm (normal strategy); see the documentation of BUCHBERGER$-$MERGE$-$PAIRS$-$SMALLEST$-$LCM.

gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$degree

$\parbox{\pboxargslen}{\em b c pred ring \/}$ [FUNCTION]

The merging strategy based on the smallest$-$lcm (normal strategy); see the documentation of BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$SMALLEST$-$DEGREE.

gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$length

$\parbox{\pboxargslen}{\em b c pred ring \/}$ [FUNCTION]

gebauer$-$moeller$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length

$\parbox{\pboxargslen}{\em b c pred ring \/}$ [FUNCTION]

The merging strategy based on the smallest$-$lcm (normal strategy); see the documentation of BUCHBERGER$-$MERGE$-$PAIRS$-$USE$-$SMALLEST$-$COEFFICIENT$-$LENGTH.

gebauer$-$moeller$-$set$-$pair$-$heuristic

$\parbox{\pboxargslen}{\em method {\sf \&aux} (strategy$-$fn (ecase ... ...ar93 'buchberger$-$merge$-$pairs$-$use$-$smallest$-$coefficient$-$length))) \/}$ [FUNCTION]

spoly$-$sugar

$\parbox{\pboxargslen}{\em f$-$with$-$sugar g$-$with$-$sugar ring \/}$ [FUNCTION]

Calculate the ``sugar'' of the S$-$polynomial of two polynomials with sugar. A polynomial with sugar is simply a pair (P . SUGAR) where SUGAR is an integer constant defined according to the following algorighm: the sugar of sum or difference of two polynomials with sugar is the MAX of the sugars of those two polynomials. The sugar of a product of a term and a polynomial is the sum of the degree of the term and the sugar of the polynomial. The idea is to accumulate sugar as we perform the arithmetic operations, and that polynomials with small (little) sugar should be given priority in the calculations. Thus, the ``sugar strategy'' of the critical pair selection is to select a pair with the smallest value of sugar of the resulting S$-$polynomial.

spoly$-$with$-$sugar

$\parbox{\pboxargslen}{\em f$-$with$-$sugar g$-$with$-$sugar pred ring \/}$ [FUNCTION]

The S$-$polynomials of two polynomials with SUGAR strategy.

normal$-$form$-$with$-$sugar

$\parbox{\pboxargslen}{\em f fl pred top$-$reduction$-$only ring \/}$ [FUNCTION]

Normal form of the polynomial with sugar F with respect to a list of polynomials with sugar FL. Assumes that FL is not empty. Parameters PRED, TOP$-$REDUCTION$-$ONLY and RING have the same meaning as in NORMAL$-$FORM. The parameter SUGAR$-$LIMIT should be set to a positive integer. If the sugar limit of the partial remainder exceeds SUGAR$-$LIMIT then the calculation is stopped and the partial remainder is returned, although it is not fully reduced with respect to FL.

buchberger$-$with$-$sugar

$\parbox{\pboxargslen}{\em f$-$no$-$sugar pred start top$-$reduction$-$only ring {\sf \&aux} (s (1$-$\space (length f$-$no$-$sugar))) b m f \/}$ [FUNCTION]

Returns a Grobner basis of an ideal generated by a list of ordinary polynomials F$-$NO$-$SUGAR. Adds initial sugar to the polynomials and performs the Buchberger algorithm with ``sugar strategy''. It returns an ordinary list of polynomials with no sugar. One of the most effective algorithms for Grobner basis calculation.

buchberger$-$with$-$sugar$-$merge$-$pairs

$\parbox{\pboxargslen}{\em b c g m pred ring \/}$ [FUNCTION]

Merges lists of critical pairs. It orders pairs according to increasing sugar, with ties broken by smaller MOCK$-$SPOLY value of the two polynomials. In this function B must already be sorted.

buchberger$-$with$-$sugar$-$sort$-$pairs

$\parbox{\pboxargslen}{\em c g m pred ring \/}$ [FUNCTION]

Sorts critical pairs C according to sugar strategy.

criterion$-$1$-$with$-$sugar

$\parbox{\pboxargslen}{\em pair g {\sf \&aux} (i (first pair)) (j (second pair)) \/}$ [FUNCTION]

An implementation of Buchberger's first criterion for polynomials with sugar. See the documentation of BUCHBERGER$-$CRITERION$-$1.

criterion$-$2$-$with$-$sugar

$\parbox{\pboxargslen}{\em pair g m {\sf \&aux} (i (first pair)) (j (second pair)) \/}$ [FUNCTION]

An implementation of Buchberger's first criterion for polynomials with sugar. See the documentation of BUCHBERGER$-$CRITERION$-$2.

gebauer$-$moeller$-$with$-$sugar

$\parbox{\pboxargslen}{\em f pred start top$-$reduction$-$only ring {\sf \&aux} b g f1 \/}$ [FUNCTION]

Compute Grobner basis by using the algorithm of Gebauer and Moeller. This algorithm is described as BUCHBERGERNEW2 in the book by Becker$-$Weispfenning entitled ``Grobner Bases''

update$-$with$-$sugar

$\parbox{\pboxargslen}{\em g b h pred ring {\sf \&aux} c d e b$-$new g$-$new pair \/}$ [FUNCTION]

An implementation of the auxillary UPDATE algorithm used by the Gebauer$-$Moeller algorithm. G is a list of polynomials, B is a list of critical pairs and H is a new polynomial which possibly will be added to G. The naming conventions used are very close to the one used in the book of Becker$-$Weispfenning. Operates on polynomials with sugar.

gebauer$-$moeller$-$with$-$sugar$-$merge$-$pairs

$\parbox{\pboxargslen}{\em b c pred ring \/}$ [FUNCTION]

Merges lists of critical pairs. It orders pairs according to increasing sugar, with ties broken by smaller lcm of head monomials In this function B must already be sorted. Operates on polynomials with sugar.

grobner$-$primitive$-$part$-$with$-$sugar

$\parbox{\pboxargslen}{\em h ring \/}$ [FUNCTION]