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, $x = (x_1, \ldots, x_n)$ and $\alpha, \beta, \gamma$ column vectors in ${\Bbb N}^n$, ${\Bbb N}= \{0, 1, 2, \ldots \}$. Let < be a semigroup ordering on the set of monomials $\{x^\alpha \vert \alpha \in {\Bbb N}^n\}$ of K[x], that is, < is a total ordering and $x^\alpha < x^\beta$ implies $x^\gamma x^\alpha < x^\gamma x^\beta$ for any $\gamma \in {\Bbb N}^n$. Robbiano (cf. [R]) proved that any semigroup ordering can be defined by a matrix $A \in GL(n, {\Bbb R})$ as follows:

Let $\frak a_1, \ldots, \frak a_k$ be the rows of A, then $x^\alpha < x^\beta$ if and only if there is an i with $\frak a_j \alpha = \frak a_j\beta$ for j < i and $\frak a_i \alpha < \frak a_i \beta$. Thus, $x^\alpha < x^\beta$ if and only if $A\alpha$ is smaller than $A\beta$ with respect to the lexicographical ordering of vectors in ${\Bbb R}^n$.

For $g \in K[x]$, $g \not= 0$, let $\bf L(g)$ be the leading monomial with respect to the ordering < and $\bf c(g)$ the coefficient of L(g) in g, that is g = c(g)L(g) + smaller terms with respect to <.

Definition 1..1   We define ${\bf Loc_< K[x]}:= S^{-1}_< K[x]$ to be the localization of K[x] with respect to the multiplicative closed set $S_< := \{1 + g \mid g = 0$ or $g \in K[x]\backslash \{ 0\}$ and $1 > L(g)\}$.

Remark 1..2  

1)

$K[x] \subseteq \mbox{Loc}_< K[x] \subseteq K[x]_{(x)}$, where K[x]_(x) denotes the localization of K[x] with respect to the maximal ideal $(x_1, \ldots, x_n)$. In particular, $\mbox{Loc}_< K[x]$ 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 x⁰ = 1 is the smallest monomial and Loc _;SPMlt; K[x] = K[x]. If 1 > x_i for all i, then Loc _;SPMlt; K[x] = K[x]_(x).

3)

If, in general, $x_1, \ldots, x_r < 1$ and $x_{r+1}, \ldots, x_n > 1$ then

$$1 + (x_1, \ldots, x_r) K[x_1, \ldots, x_r]\; \subseteq\; S_< \;\subseteq\; 1 + (x_1, \ldots, x_r) K[x] =: S,$$

hence

$$K[x_1, \ldots, x_r]_{(x_1, \ldots, x_r)} [x_{r+1}, \ldots, x_n]\; \subseteq\; \mbox{ Loc}_< K[x] \;\subseteq\; S^{-1} K[x].$$

4)

Let < be an elimination ordering for $x_{r+1}, \ldots, x_n$ (that is $L(g) \in K[x_1, \ldots, x_r]$ implies $g \in K[x_1, \ldots, x_r]$), then $x^\alpha < 1$ implies $x^\alpha \in K[x_1, \ldots, x_r]$. In particular, < is necessarily a wellordering on the set of monomials in $K[x_{r+1}, \ldots, x_n]$. Note that lex⁺ below eliminates but lex^- does not.

Important orderings for applications are:

• The lexicographical ordering, given by the matrix
  
  $$\begin{array}{cc} lex \mbox{ or } lex^+: \left(\begin{array}{... ...\\ & & \diagdown &\\ & 0 & & -1\end{array}\right) \end{array}$$
  
  

• The weighted degree reverse lexicographical ordering, given by the matrix
  
  $$W^+: \pmatrix{w_1 & w_2 & \ldots & w_n\cr & & & -1\cr & & \... ...or all } i, \mbox{ (resp.\ } W^-: w_i < 0 \mbox{ for all } i).$$
  
  

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

• An elimination ordering for $x_{r+1}, \ldots, x_n$ in $K[x] = \mbox{ Loc}_< K[x]$ is given by the matrix
  
  $$\pmatrix{ 0 & 0 & \ldots & 0 & w_{r+1} & w_{r+2} & \ldots & ... ...1 & & & & \cr & & \diagup& & & & &\cr 0 & -1 & & & & & &\cr}$$
  
  
  with $w_1 > 0, \ldots, w_n > 0$. In $K[x_1, \ldots, x_r]_{(x_1, \ldots, x_r)} [x_{r+1}, \ldots, x_n] = \mbox{ Loc}_<K[x]$ it is given by the same matrix with $w_1 < 0, \ldots, w_r < 0$ and $w_{r+1} > 0, \ldots, w_n > 0$.

• The product ordering, given by the matrix
  
  $$\pmatrix{A_1 & & & 0\cr & A_2 & & \cr & & \diagdown & \cr 0 & & &A_k \cr}$$
  
  
  if the A_i define orderings on monomials given by the corresponding subsets of $\{x_1, \ldots, x_n\}$.

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'' $\{ x^\alpha e_i\}$ of $K[x]^r = \sum_{i=1, \ldots, r} K[x] e_i$ which are compatible with the ordering < on K[x]. That is for all monomials $f, f' \in K[x]^r$ and $p, q \in K[x]$ 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:

$$\begin{array}{ll} L(qf) = L(q) L(f) & \mbox{for } q \in K[x] ... ...\le \max(L(f), L(g)) & \mbox{for } f, g \in K[x]^r. \end{array}$$

Definition 1..3   Let $I \subseteq K[x]^r$ be a submodule.

1)

${\bf L}(I)$ denotes the submodule of K[x]^r generated by $\{L(f) \vert f \in I\}$.

2)

$f_1, \ldots, f_s \in I$ is called a standard basis of I if $\{L(f_1), \ldots, L(f_s)\}$ generates the submodule $L(I) \subset K[x]^r$.

3)

A standard basis $f_1, \ldots, f_s$ is called reduced if, for any i, L(f_i) does not divide any of the monomials of $f_1, \ldots, f_s$ (except itself).

Proposition 1..4   If $\{ f_1, \ldots, f_s\}$ is a standard basis of I then ILoc_;SPMlt; K[x] $= (f_1, \ldots, f_s) \mbox{Loc}_< 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 $f_1, \ldots, f_s$ generate I as K[x]-module (take $I = (x) K[x],\; n = 1,\; f = x+x^2$ with lex^-).

This is also not true if $I \subset K[x]$ is $(x_1, \ldots, x_n)$-primary and if $\{ f_1, \ldots, f_s\}$ is a reduced standard basis: Consider the ideal $I \subset K[x,y]$ generated by $x^{10} - y^2 x^9,\; y^8 - x^2 y^7,\; x^{10}y^7$ which is (x,y)-primary. The first two elements are a reduced standard basis of $I\, Loc_< K[x,y] = I\, K[x,y]_{(x,y)}$ where < is degrevlex^- und hence generate $I\,K[x,y]_{(x,y)}$ but they do not generate $I\, K[x,y]$. (This answers a question of T. Mora.)

Notations:

Let $f, g \in K[x]^r$, $L(f) = x^\alpha e_i$ and $L(g) = x^\beta e_j$. If i = j and $x^\alpha \vert x^\beta$ then we write L(f) | L(g).

If i = j and $x^\gamma = lcm(x^\alpha, x^\beta),\ \gamma = (\max(\alpha_1, \beta_1), \ldots, \max(\alpha_n, \beta_n))$ then

$$\begin{array}{lcl} {\bf lcm(L(f), L(g))}& := & x^\gamma \mbox... ...alpha} f - \frac{c(f)} {c(g)} x^{\gamma - \beta} g. \end{array}$$

If $i \not= j$ then, by definition, $L(f) \not\vert L(g)$, spoly (f, g) := 0 and lcm(L(f), L(g)) := 0.

Let ${\cal F}= \{G \subseteq K[x]^r \vert G$ finite and ordered $\}$.

Definition 1..5   A function $NF : K[x]^r \times {\cal F}\to K[x]^r, (p,G) \mapsto NF(p\vert G)$, is called a normal form if for any $p \in K[x]^r$ and any $G\in {\cal F}$ the following holds: if $NF(p\vert G) \not= 0$ then $L(g) \not\vert L(NF(p\vert G))$ for all $g \in G$. NF(g|G) is called the normal form of $\bf p$ with respect to $\bf G$.

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

h:= NFBuchberger $\bf (p\vert G)$

h:= p
WHILE exist $f \in G$ such that L(f) | L(h) DO

choose the first $f \in G$ 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 $\bf (G, NF)$

S := G
$P := \{(f,g) \vert f,g \in S\}$
WHILE $\; P \not= \emptyset\;$ DO

choose $(f,g) \in P$; $P:= P\backslash \{(f,g)\}$
h:= NF(spoly $(f,g) \mid S)$
IF $\; h \not= 0\;$ THEN

$P := P \cup \{(h,f) \mid f \in S\}$
$S := S \cup \{ h \}$

END

END

In this language Buchberger's algorithm is just

$${\tt\mbox{{\bf Buchberger}} ({\bf G}) = \mbox{ Standard }(G, \mbox{ NFBuchberger}).}$$

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

$$\pmatrix{ 1 & 1 \ldots 1\cr 0 & \cr \vdots & A\cr 0 & \cr}$$

defines a wellordering on the monomials of K[t, x] which we denote also by <. For $f \in K[x]$ let f^h be the homogenization of f with respect to t and for $G \subseteq K[x]$ let $G^h = \{ f^h \mid f \in G\}$. If $f \in K[x]^r$, $f = \sum f_i e_i$ then $f^h = \sum t^{\alpha_i} f_i^h e_i$, $\deg\, f_i^h + \alpha_i = \deg\, f_j^h + \alpha_j$ for all i, j and the $\alpha_i$ minimal with this property. Similarly, we define $G^h = \{ f^h \mid f \in G\}$ for $G \subseteq K[x]^r$.

This ordering has the following property:

Lemma 1..7   If $t^\alpha > x^\gamma$, for some $\gamma = (\gamma_1, \ldots, \gamma_n)$, and $\alpha = \gamma_1 + \cdots + \gamma_n$ then $x^\gamma < 1$. 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 $(\bf G)$

S := G^h
S := Buchberger (S)
S := S(t = 1)

Remark 1..8   The result S is a standard basis of the submodule $\langle G \rangle$ generated by G in K[x]^r with the additional property that $\langle G \rangle$ 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 $\langle G \rangle$ 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 $(\bf G)$

S := G^h
S := Standard (S, NFMora)
S := S(t = 1)

Let $G \subseteq K[t,x]^r$ be a finite set of homogeneous elements and $p \in K[t,x]^r$ 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 $(\bf p\vert G)$

h := p
T := G
WHILE exist $f \in T$, such that $L(f) \mid t^\alpha L(h)$ for some $\alpha$ DO

choose $f \in T$ with $L(f) \mid t^\alpha L(h)$ and $\alpha$ minimal
IF $\alpha > 0$ THEN
$T := T \cup \{ h\}$
END
h := spoly $(t^\alpha h, f)$
IF $t\mid h$ THEN

choose $\alpha$ maximal such that $t^\alpha$ divides h
$h := \frac{h}{t^\alpha}$

END

END

Proposition 1..9  

1)

NFMora terminates.

2)

If h is a normal form of p with respect to $G = \{ f_1, \ldots, f_s\}$ computed by NFMora then there are homogeneous polynomials $g,\; \xi_1, \ldots, \xi_s \in K[t, x]$ such that

-

$gp = \sum \xi_i f_i + h$

-

$L(g) = t^\alpha$

-

deg $p + \alpha = \deg\; \xi_i + \deg\; f_i = \deg(h)$ (if $\xi_i \not= 0,\; h \not= 0$)

-

$L(f_i) \not\vert t^\alpha L(h)$ for all $i, \alpha$

If < is a wellordering on K[x] then $g = t^\alpha$.

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

$$g_\nu p = \sum \xi_{i\nu} f_i + h_\nu,$$

and

-

$L(g_\nu) = t^{\alpha_\nu},$

-

$\deg\, p + \alpha_\nu = \deg\, \xi_{i,\nu} + \deg\, f_i = \deg\, h_\nu$ (if $\xi_{i,\nu} \not= 0,\; h_\nu \not= 0)$

-

$t^{-\alpha_\mu} L(h_\mu) > t^{-\alpha_\nu} L(h_\nu) \mbox{ for } \mu < \nu$.

If $L(f_i) \not\vert t^\alpha L(h_\nu)$ for all $i, \alpha$ then we have finished.

Since T consists of elements $f_k \in G$ and of $h_\mu$ constructed in previous steps we have to consider two cases:

-

If $L(f_k) \mid t^\alpha L(h_\nu)$ and $\alpha$ is minimal for all possible choices for $f_k \in G$ then

$$t^\alpha g_\nu p = \sum t^\alpha \xi_{i\nu} f_i + t^\alpha h_\nu - \eta f_k + \eta f_k$$

with $L(f_k)\eta = t^\alpha L(h_\nu)$.

We obtain

$$\begin{eqnarray*}h_{\nu + 1} & = & t^\alpha h_\nu - \eta f_k\\ g_{\nu + 1} & = ... ... \nu \not= k\\ \xi_{k \nu + 1} & = & t^\alpha \xi_{k\nu} + \eta \end{eqnarray*}$$

and the induction step follows with $\alpha_{\nu + 1} = \alpha + \alpha_\nu$.

-

If $L(h_\mu) \mid t^\alpha L(h_\nu)$ for some $\mu < \nu$ and $\alpha$ is minimal for all possible choices from T then

$$t^\alpha g_\nu p = \sum t^\alpha \xi_{i\nu} f_i + t^\alpha h_\nu - \eta h_\mu + \eta h_\mu$$

with $L(h_\mu) \eta = t^\alpha L(h_\nu)$.

$$\begin{eqnarray*}h_{\nu + 1} & = & t^\alpha h_\nu - \eta h_\mu\\ g_{\nu + 1} & ... ...\\ \xi_{i \nu + 1} & = & t^\alpha \xi_{i\nu} - \eta \xi_{i\mu}. \end{eqnarray*}$$

Now $t^{\alpha_\nu - \alpha_\mu} L(h_\mu) > L(h_\nu)$ implies $t^{\alpha + \alpha_\nu}> L(\eta) t^{\alpha_\mu}$, that is $t^{\alpha + \alpha_\nu} = L(g_{\nu+1})$.

This proves 2).

To prove 1) let $I_\nu = \langle L(f) \mid f \in T_\nu \rangle,\; T_\nu$ be the set T after the $\nu$-th reduction. Let N be an integer such that $I_N = I_{N+1} = \ldots$ (such N exists because K[t, x]^r is noetherian). This implies $T_N = T_{N+1} = \ldots$. 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 $x^\alpha \mid x^\beta$ implies $x^\alpha < x^\beta$. 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 $(p) = \deg_t(p^h)$. During the implementation of SINGULAR we discovered that the normal form with ecart $(p) := \deg_t(L(p^h))$ terminates for any ordering, not only for tangent cone orderings. This was found also by Gräbe (cf. [G]).

Corollary 1..11   Let $S = \{f_1, \ldots, f_s\}$ be a finite subset of the submodule $I \subseteq K[x]^r$.

1)

If S is a standard basis of I then:

(i)

For any $f \in K[x]^r$ there are $g, \xi_i\in K[x]$, $h \in K[x]^r$, such that

$$(1 + g) f = \sum \xi_i f_i + h,$$

L(g) < 1 if $g \not= 0$, $L(\xi_i f_i) \le L(f)$ if $\xi_i \not= 0$ and, for all i, $L(f_i) \not\vert L(h)$.

(ii)

$f \in I$ if and only if NFMora $(f^h\mid S^h) = 0$.

(ii')

$f \in I$ if and only if $(1+g)f = \sum \xi_i f_i$ for suitable $g, \xi_i \in K[x],\; L(g) < 1$ if $g \not= 0$ and $L(\xi_i f_i) \le L(f)$ if $\xi_i \not= 0$.

(iii)

$I\, \mbox{Loc}_< K[x] = \langle S \rangle \mbox{ Loc}_< K[x]$.

2)

The following are equivalent:

(i)

S is a standard basis of I.

(ii)

S^h = Standard (S^h, NFMora).

(iii)

NFMora (spoly $(f,g),\; S^h) = 0$ for all $f, g \in S^h$.

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

$$\pmatrix{1 & w_1, \ldots, w_n\cr 0 & \cr \vdots & A\cr 0 & },\; w_i > 0$$

and use homogenization with respect to the weights $w_1, \ldots, w_n$ 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 $f \in K[x]^r$,

$$(\ast)\qquad\qquad f = \sum \xi_i f_i + h,$$

for suitable $\xi_i \in K[x]$, $h \in K[x]^r$ such that $L(\xi_i f_i) \le L(f)$ if $\xi_i \not= 0$ and, for all i, no monomial of h is divisible by L(f_i); 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 $(\ast)$ with $\xi_i \in K[[x]]$ and $h \in K[[x]]^r$ (formal power series) having the above properties.

3)

A reduced standard basis is uniquely determined by I and <. If < is a wellordering or $\dim_K Loc_<K[x]^r/I < \infty$ then there exists always a reduced standard basis in K[x]^r. In general, it exists only in K[[x]]^r.