Next: 2. The standard basis Up: Standard bases, syzygies and Previous: Introduction

# 1. A standard basis algorithm for any semigroup ordering

This algorithm is a generalization of Buchberger's algorithm (which works for wellorderings cf. [B1], [B2]) and Mora's tangent cone algorithm (which works for tangent cone orderings, cf. [M1], [MPT]) and which includes a mixture of both (which is useful for certain applications, in particular to algorithms described by Mora in his Graal paper [M3]). In fact, it is an easy extension of Mora's idea by introducing the correct'' definition of ecart. But we present it in a new way which, as we hope, makes the relation to the existing standard basis algorithms transparent.

Let K be a field, and column vectors in , . Let < be a semigroup ordering on the set of monomials of K[x], that is, < is a total ordering and implies for any . Robbiano (cf. [R]) proved that any semigroup ordering can be defined by a matrix as follows:

Let be the rows of A, then if and only if there is an i with for j < i and . Thus, if and only if is smaller than with respect to the lexicographical ordering of vectors in .

For , , let be the leading monomial with respect to the ordering < and the coefficient of L(g) in g, that is g = c(g)L(g) + smaller terms with respect to <.

Definition 1..1   We define to be the localization of K[x] with respect to the multiplicative closed set or and .

Remark 1..2
1)
, where K[x](x) denotes the localization of K[x] with respect to the maximal ideal . In particular, is noetherian, Loc;SPMlt; K[x] is K[x]-flat and K[x](x) is Loc;SPMlt; K[x]-flat.

2)
If < is a wellordering then x0 = 1 is the smallest monomial and Loc ;SPMlt; K[x] = K[x]. If 1 > xi for all i, then Loc ;SPMlt; K[x] = K[x](x).

3)
If, in general, and then

hence

4)
Let < be an elimination ordering for (that is implies ), then implies . In particular, < is necessarily a wellordering on the set of monomials in . Note that lex+ below eliminates but lex- does not.

Important orderings for applications are:

• The lexicographical ordering, given by the matrix

• The weighted degree reverse lexicographical ordering, given by the matrix

If wi = 1 (respectively wi = -1) for all i we obtain the degree reverse lexicographical ordering, degrevlex+ (respectively degrevlex-).

• An elimination ordering for in is given by the matrix

with . In it is given by the same matrix with and .

• The product ordering, given by the matrix

if the Ai define orderings on monomials given by the corresponding subsets of .

We call an ordering a degree ordering if it is given by a matrix with coefficients of the first row either all positive or all negative. In the positive (respectively negative) case Loc ;SPMlt;K[x] = K[x] (respectively Loc ;SPMlt; K[x] = K[x](x)).

We consider also module orderings <m on the set of monomials'' of which are compatible with the ordering < on K[x]. That is for all monomials and we have: f <m f' implies pf <m pf' and p < q implies pf <m qf.

We now fix an ordering <m on K[x]r compatible with < and denote it also with <. Again we have the notion of coefficient c(f) and leading monomial L(f). < has the important property:

Definition 1..3   Let be a submodule.

1)
denotes the submodule of K[x]r generated by .

2)
is called a standard basis of I if generates the submodule .

3)
A standard basis is called reduced if, for any i, L(fi) does not divide any of the monomials of (except itself).

Proposition 1..4   If is a standard basis of I then ILoc;SPMlt; K[x] .

Note that a reduced standard basis of polynomials does not necessarily exist (cf. Remark 1.12).

The proof will be deduced from the normal form used in the standard basis algorithm (cf. Corollary 1.11). Note that, in general, it is not true that generate I as K[x]-module (take with lex-).

This is also not true if is -primary and if is a reduced standard basis: Consider the ideal generated by which is (x,y)-primary. The first two elements are a reduced standard basis of where < is degrevlex- und hence generate but they do not generate . (This answers a question of T. Mora.)

Notations:

Let , and . If i = j and then we write L(f) | L(g).

If i = j and then

If then, by definition, , spoly (f, g) := 0 and lcm(L(f), L(g)) := 0.

Let finite and ordered .

Definition 1..5   A function , is called a normal form if for any and any the following holds: if then for all . NF(g|G) is called the normal form of with respect to .

Example 1..6   Let < be a wellordering then the following procedure NFBuchberger is a normal form:

h:= NFBuchberger
h:= p
WHILE exist such that L(f) | L(h) DO
choose the first with this property
h:= spoly(h,f)
END.

The principle for many standard basis algorithms depending on a chosen normal form is the following:

S := Standard
S := G

WHILE DO
choose ;
h:= NF(spoly
IF THEN

END
END

In this language Buchberger's algorithm is just

If < is any ordering (not necessarily a wellordering) and A the corresponding matrix, then the matrix

defines a wellordering on the monomials of K[t, x] which we denote also by <. For let fh be the homogenization of f with respect to t and for let . If , then , for all i, j and the minimal with this property. Similarly, we define for .

This ordering has the following property:

Lemma 1..7   If , for some , and then . Especially, < is not a wellordering in this case on K[x].

The Lazard method (cf. [L]) to compute a standard basis is the following:

S := Lazard
S := Gh
S := Buchberger (S)
S := S(t = 1)

Remark 1..8   The result S is a standard basis of the submodule generated by G in K[x]r with the additional property that is generated by S as K[x]-module (we need not pass to Loc;SPMlt; K[x]!). If we are only interested in a standard basis of this algorithm computes usually too much and this might be the reason why it is often too slow (although there are cases where it is surprisingly fast).

Mora found for tangent cone orderings (cf. [M1], [MPT]) an algorithm which computes a standard basis over Loc;SPMlt; K[x]. This algorithm can be generalized to any ordering and we can describe it as follows:

S:= Standard basis
S := Gh
S := Standard (S, NFMora)
S := S(t = 1)

Let be a finite set of homogeneous elements and homogeneous. Note that an element of K[t, x]r is homogeneous if its components are homogeneous polynomials of the same degree. The generalization of Mora's normal form to any semigroup ordering is as follows:

h := NFMora
h := p
T := G
WHILE exist , such that for some DO
choose with and minimal
IF THEN

END
h := spoly
IF THEN
choose maximal such that divides h
END
END

Proposition 1..9
1)
NFMora terminates.
2)
If h is a normal form of p with respect to computed by NFMora then there are homogeneous polynomials such that
-
-
-
deg (if )
-
for all
If < is a wellordering on K[x] then .

Proof: 2) By induction suppose that after the -th step in NFMora we have

and

-
-
(if
-
.

If for all then we have finished.

Since T consists of elements and of constructed in previous steps we have to consider two cases:

-
If and is minimal for all possible choices for then

with .

We obtain

and the induction step follows with .

-
If for some and is minimal for all possible choices from T then

with .

Now implies , that is .

This proves 2).

To prove 1) let be the set T after the -th reduction. Let N be an integer such that (such N exists because K[t, x]r is noetherian). This implies . The algorithm continues with fixed T and terminates because < is a wellordering on K[t, x]r.

Remark 1..10
1)
If the ordering < on K[x] is a wellordering, then the standard basis algorithm is essentially Buchberger's algorithm because then implies . This shows that only elements from G are used for the reduction in NFMora. Moreover, if G is homogeneous but < arbitrary, the standard basis algorithm coincides with Buchberger's algorithm.

2)
If < is a tangent cone ordering then the algorithm is Mora's tangent cone algorithm. In his algorithm Mora uses the same normal form, just in another language. Instead of passing from K[x] to K[t, x] by homogenizing and extending the ordering, he uses the notion of ecart, where ecart . During the implementation of SINGULAR we discovered that the normal form with ecart terminates for any ordering, not only for tangent cone orderings. This was found also by Gräbe (cf. [G]).

Corollary 1..11   Let be a finite subset of the submodule .

1)
If S is a standard basis of I then:
(i)
For any there are , , such that

L(g) < 1 if , if and, for all i, .
(ii)
if and only if NFMora .
(ii')
if and only if for suitable if and if .
(iii)
.

2)
The following are equivalent:
(i)
S is a standard basis of I.
(ii)
Sh = Standard (Sh, NFMora).
(iii)
NFMora (spoly for all .

The corollary is an easy consequence of 1.9.

Remark 1..12
1)
If one extends the ordering < given by the matrix A on K[x] to K[t, x] by

and use homogenization with respect to the weights then the standard basis algorithm works as well.

Gräbe discovered (cf. [G]) that for a suitable choice of the weights adapted to the input (the polynomials should become as homogeneous as possible with respect to these weights) the algorithm can become faster. We call this the (weighted) ecartMethod.

2)
If < is a wellordering, we can apply the normal form algorithm to each monomial of h and we can achieve that for any ,

for suitable , such that if and, for all i, no monomial of h is divisible by L(fi); h is then unique.

If we try the same for an arbitrary semigroup ordering, this procedure will, in general, not terminate. We can only derive a presentation with and (formal power series) having the above properties.

3)
A reduced standard basis is uniquely determined by I and <. If < is a wellordering or then there exists always a reduced standard basis in K[x]r. In general, it exists only in K[[x]]r.

Next: 2. The standard basis Up: Standard bases, syzygies and Previous: Introduction
| ZCA Home | Reports |