PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 97(111) (2015), 43–48 DOI: 10.2298/PIM141104001L

A NOTE ON MULTIVARIATE POLYNOMIAL DIVISION AND GRÖBNER BASES

Aleksandar T. Lipkovski and Samira Zeada

Abstract. We first present purely combinatorial proofs of two facts: the well-known fact that a monomial ordering must be a well ordering, and the fact (obtained earlier by Buchberger, but not widely known) that the division procedure in the ring of multivariate polynomials over a field terminates even if the division term is not the leading term, but is freely chosen. The latter is then used to introduce a previously unnoted, seemingly weaker, criterion for an ideal basis to be Gröbner, and to suggest a new heuristic approach to Gröbner basis computations.

1. Introduction

The division algorithm for multivariate polynomials over fields has been introduced not so long ago, in connection with algorithmic and computational problems in these rings. It generalizes the univariate algorithm. There is no natural monomial ordering in the multivariate ring K[x_{1}, x_{2}, …, x_{n}]. Still, there are many possibilities to totally order monomials in n variables, such as lexicographic or degree-lexicographic orders. The multivariate division algorithm depends on the choice of this ordering.

In what follows, we use the standard multiindex notation for multivariate monomials x_{1}^{i_{1}} x_{2}^{i_{2}} ⋯ x_{n}^{i_{n}} = x^{i}, their coefficients a_{i_{1} i_{2} ...i_{n}} = a_{i} where i = (i_{1}, i_{2}, …, i_{n}) ∈ ℕ_{0}^{n}, and polynomials f = ∑ _{i∈ℕ_{0}^{n}} a_{i}x^{i}. Denote Supp(f) = {i ∈ ℕ_{0}^{n} | a_{i} ≠ 0} ⊂ ℕ_{0}^{n}, support of the polynomial f. Then, f = ∑ _{i∈Supp (f)} a_{i}x^{i}. Note that monomial x^{i} is divisible by monomial x^{j} precisely when i = j + k for some k ∈ ℕ_{0}^{n}, or, written in a different way, i ∈ j + ℕ_{0}^{n}. Here we use the standard semigroup structure of ℕ_{0}^{n}.

2. Monomial orderings

The ordering of the set of monomials is equivalent to the ordering of the set of exponents ℕ_{0}^{n}. As usual, the sign ≺ denotes the strict, nonreflexive ordering, while the corresponding reflexive ordering is denoted by ⪯.

2010 Mathematics Subject Classification: 13P10, 12Y05, 06A07.

Communicated by Žarko Mijajlović.

Definition 2.1. A monomial ordering ⪯ on ℕ_{0}^{n} is a linear (or total) ordering on ℕ_{0}^{n} such that it respects vector addition in ℕ_{0}^{n} i.e., i ⪯ j ⇒ i + k ⪯ j + k and such that 0 ⪯ i for all i ∈ ℕ_{0}^{n}.

From these conditions it follows that ⪯ must be a well ordering. The proof of this fact is usually based on Hilbert’s basis theorem or its weaker form, Dickson’s lemma [1]. Here we give a simple combinatorial proof based on the idea suggested by Siniša Vrećica.

Proposition 2.1. Let the ordering ⪯ on ℕ_{0}^{n} satisfy the following properties:

1) it is a linear ordering; 2) it is additive in ℕ_{0}^{n} i.e., i ⪯ j ⇒ i + k ⪯ j + k; 3) 0 ⪯ i for all i ∈ ℕ_{0}^{n}. Then ⪯ is a well ordering.

Proof. Conditions 2) and 3) clearly imply that i ∈ j + ℕ_{0}^{n} ⇒ j ⪯ i or equivalently, i ≺ j ⇒ i ∉ j + ℕ_{0}^{n}. Now, it is sufficient to prove that ≺ satisfies the descending chain condition (DCC for short). We shall use mathematical induction on n. The statement obviously holds for n = 1. Let

S : ⋯≺ i^{(k)} = (i_{1}^{(k)}, …, i_{n}^{(k)}) ≺ ⋯≺ i^{(1)} = (i_{1}^{(1)}, …, i_{n}^{(1)})

be a descending chain in ℕ_{0}^{n}. It would suffice to show that the set S_{1} = {i ∈ S | i_{1} < i_{1}^{(1)}} ⊂ S is finite, since this can be applied to any coordinate i_{1}, …, i_{n} of i. Let i′_{1} = max{i_{1} | i ∈ S_{1}} < i_{1}^{(1)} be the biggest first coordinate of elements in S_{1}. and i′ ∈ S_{1} any point with this first coordinate. The interval subset {i ∈ S_{1} | i′ ≺ i ≺ i^{(1)}} ⊂ S_{1} is finite. The hyperplane subset S′_{1} = {i ∈ S_{1} | i ≺ i′, i_{1} = i′_{1}} ⊂ S_{1} of all points in S_{1} less (with respect to ≺) than i′ and with the first coordinate i′_{1} forms a DCC in ℕ_{0}^{n−1} . By induction hypothesis, S′_{1} must be finite. Therefore, there can be only finitely many points in S_{1} with the first coordinate i′_{1} and there is the smallest one (with respect to ≺) i^{(m)} ∈ S_{1}. So, i_{1}^{(m)} = i′_{1} < i_{1}^{(1)} and i ≺ i^{(m)} ⇒ i_{1} < i′_{1}. Since the set of first coordinates i_{1} < i′_{1} is finite, by infinite descent reasoning one obtains that the set S_{1} must be finite. □

3. Multivariate reduction and division

First, let us recall the standard multivariate polynomial reduction and division. Choose the monomial ordering ≺ in ℕ_{0}^{n} once for all. The multidegree of polynomial f is the n-tuple deg(f) := maxSupp(f) ∈ ℕ_{0}^{n}. The maximum is attained because Supp(f) is finite. If α = deg(f), then f has a leading term lt(f) = a_{α} x^{α} with leading monomial lm(f) = x^{α} and leading coefficient lc(f) = a_{α}. The standard division algorithm in the ring K[x_{1}, …, x_{n}] is performed in the following way (see [1] or [2]).

Let f, g ∈ K[x_{1}, …, x_{n}] be two polynomials, and suppose first that lm(f) is divisible by lm(g). This is equivalent to deg(f) ∈ deg(g) + ℕ_{0}^{n} and implies that deg(g) ≺ deg(f). In this case, the leading terms of two polynomials f and \frac{lt(f)}{lt(g)} g are

identical, and polynomial r = f − \frac{lt(f)}{lt(g)} g has smaller multidegree deg(r) ≺ deg(f). In such case, one says that f reduces to r modulo g, and this is denoted by f →_{g} r. This is sometimes called a one-step reduction of f by g.

If the leading monomial lm(f) is not divisible by lm(g), then one takes the maximum of all terms which are divisible – the term corresponding to max{i ∈ Supp(f) | i = deg(g)+k for some k ∈ ℕ_{0}^{n}}. This process is continued until no term in r is divisible by lm(g). One says then that f completely reduces to r modulo g or that r is the remainder in the division algorithm f = gh + r. It is not difficult to prove that polynomials r and h are uniquely determined.

Since in K[x_{1}, …, x_{n}] we have to deal with nonprincipal ideals, one needs division algorithm for an ordered m-tuple (g_{1}, …, g_{m}) of polynomials rather than a single polynomial g. So, f is usually reduced using the left-most g_{i} with the property that lt(g_{i}) divides some term in the remainder. It is easy to see that this algorithm always terminates, but it is clear that the remainder r (the polynomial such that none of its terms is divisible by some of lt(g_{1}), …, lt(g_{m})) depends on the choice of order of polynomials g_{1}, …, g_{m}.

Now, introduce the support of f with respect to g

Supp_{g}(f) = {i ∈ Supp(f) | i = deg(g) + k for some k ∈ ℕ_{0}^{n}}
= Supp(f) ∩ (deg(g) + ℕ_{0}^{n})

of multiindices of all monomials in f divisible by lt(g). The standard algorithm described above takes for the next division step the maximal divisible term in f, which corresponds to the multiindex maxSupp_{g}(f). Clearly, r is the remainder in the division algorithm f = gh + r ⇔ Supp_{g}(r) = ∅. It is not obvious whether the algorithm would stop if, instead of always choosing the maximal index in the set Supp_{g}(f), one chooses an arbitrary one. This is because after reducing f modulo g_{1} and then modulo g_{2}, it is possible that some terms divisible by lt(g_{1}), which were previously eliminated, reappear. Therefore, it is natural to ask whether any reduction process modulo a given m-tuple (g_{1}, …, g_{m}), with arbitrary choice of division term in each step would terminate? For a set of m polynomials G = {g_{1}, …, g_{m}} let us introduce Supp_{G}(f) = Supp_{g}(f) ∪ ⋯∪ Supp_{g}(f).

Theorem 3.1. Let f ∈ K[x_{1}, …, x_{n}] and G = {g_{1}, …, g_{m}} a set of m polynomials, g_{i} ∈ K[x_{1}, …, x_{n}]. Then, any reduction process (with arbitrary choice of the next reduction term in Supp_{g_{i_{j}}} (f_{j−1} ))

f →_{g_{i_{1}}} f_{1} →_{g_{i_{2}}} f_{2} → ⋯

with g_{i_{k}} ∈ G must terminate in finitely many steps. This means that there exists k such that f_{k} does not contain a term divisible by any of the lt(g_{1}), …, lt(g_{m}).

Proof. Let m_{j} = maxSupp_{g_{i_{j+1}}} (f_{j}) and let r_{j} be the index used for reduction by g_{i_{j+1}} (j = 0, 1, 2, …, f_{0} := f). Clearly, r_{j} ∈ Supp_{g_{i_{j+1}}} (f_{j}) and r_{j} ⩽ m_{j}. It is easy to see that m_{0} ⩾ m_{1} ⩾ · · · . According to DCC, from some point on m_{k_{1}} = m_{k_{1} +1} = · · · . Let m_{k_{1}}^{(1)} = max[Supp_{g_{i_{k_{1} +1}}} (f_{k_{1}} ) ∖ {m_{k_{1}} }] < m_{k_{1}} . Clearly,

r_{k_{1}} ⩽ m_{k_{1}}^{(1)} < m_{k_{1}} . Repeat the process for the sequence m_{k_{1}}^{(1)} ⩾ m_{k_{1} +1}^{(1)} ⩾ · · · . In this way we obtain a sequence of indices m_{k_{1}}^{(1)} ⩾ m_{k_{2}}^{(2)} ⩾ · · · . Again, according to DCC, this sequence must be stationary from some point on m_{k_{p}}^{(p)} = m_{k_{p+1}}^{(p+1)} = ⋯, which means that from that point on, Supp_{g_{ip}} (f_{p−1} ) = ∅ and the reduction process terminates. □

So, no matter how we choose the next term in the division algorithm (in the set of all possible terms), the algorithm will stop in finitely many steps. The polynomial f_{k} obtained in this way is then the remainder of the particular reduction process. As we have already noted, the remainder depends on the order in which the reductions are performed.

4. Ordered sets and multivariate division

The fact that in the reduction process, one can arbitrarily choose the term for the next reduction in the set Supp_{G}(f) was known to Buchberger (see [3, p. 14]). However, it was not widely used and even not mentioned in the standard textbooks. Buchberger’s argument in [3] involves extension of a given monomial order to a partial order on the set of all polynomials. This order seems somehow unnatural. It is not total because the coefficients are also taken into account. However, we have already seen that it is not necessary to speak about monomials and polynomials, but about underlying monomial orders on the exponent set ℕ_{0}^{n} (= ℤ_{+}^{n} ) instead. When we took a closer look, we discovered more natural, underlying combinatorial fact about total orders, which actually belongs to set theory.

Recall that a set X together with binary partial order relation ⩽ (reflexive, antisymmetric and transitive) is called (partially) ordered set. Ordered set (X, ⩽) is totally ordered if for any two elements x, y ∈ X either x ⩽ y or y ⩽ x. Recall the following trivial fact.

Lemma 4.1. Let (X, ⩽) be totally ordered and A ⊂ X its nonempty finite subset. Then the minimal element minA and the maximal element maxA of A exist and are unique. Actually, the elements in A are ordered in a unique way.

Ordered set (X, ⩽) is well ordered if every nonempty subset has a least element. A well-ordered set is totally ordered. We now come to the set-theoretic essence of the division algorithm in the multivariate polynomial ring, Buchberger’s polynomial order and Buchberger’s proof.

Let (X, ⩽) be a well-ordered set and F the family of all its (nonempty) finite subsets. Consider the following binary relation on F

A < B ⇔ max(A Δ B) ∈ B.

Here, A Δ B = (A ∖ B) ∪ (B ∖ A) is a common symmetric difference of two sets. It is easy to see that this definition is equivalent to the following:

A < B ⇔ there exists b ∈ B ∖ A such that the strict upper

intervals A_{>b} and B_{>b} are either empty or coincide.

Here, A_{>b} = {x ∈ A | x > b} is the upper interval of b in A. Clearly, such element must be unique.

Theorem 4.1. With respect to this (strict) order <, the set F is well ordered.

Proof. (1) It is easy to see that this is an order on F. Reflexivity is obtained in the usual way by reflexive completion of the given strict order A ⩽ B ⇔ (A < B) ∨ (A = B). Antisymmetry is obvious, since A < B and B < A leads to a contradiction. Now, let A < B and B < C, and let b = max(A Δ B) ∈ B and c = max(B Δ C) ∈ C. Then c ∉ B and therefore c ≠ b. There are two possibilities: either b < c or b > c. In the first case, c ∉ A and max(A Δ C) = c. In the second case, b ∈ C and max(A Δ C) = b. This proves transitivity. This is a total order since the maximal element in A Δ B ≠ ∅ has to be either in A or in B.

(2) Now, let us prove that this is a well order i.e., it satisfies the DCC. Let A_{1} > A_{2} > ⋯> A_{n} > ⋯be a strictly descending chain in F. For n ∈ ℕ, define two sequences in X,

a_{n} = max(A_{n} ∖ A_{n+1} ) ∈ A_{n} and p_{n} = max{a_{1}, …, a_{n}}.

The last sequence is actually an ascending chain

p_{1} ⩽ p_{2} ⩽ … ⩽ p_{n} ⩽ · · ·.

Now notice that if there is a strict jump in the sequence i.e., if p_{n} > p_{n−1} , then p_{n} = a_{n} ∈ A_{i} for all i ⩽ n. But A_{1} is finite, so the number of strict jumps is also finite, and the chain must be stationary. Let p^{(1)} be its stationary value: p_{m} = p_{m+1} = ⋯= p^{(1)}, which means that from that point on all subsets A_{m+i} ∩ {x ∈ X | x ⩾ p^{(1)}} = S ⊂ A_{m+i} coincide for all i ⩾ 1.

The following easy fact will be used without proof.

Lemma 4.2 (“cut-off"). Let A < B, max(A Δ B) = b ∈ B ∖ A, and S ⊂ A ∩ B. Denote A^{(1)} = A∖S and B^{(1)} = B∖S. Then A^{(1)} < B^{(1)} and max(A^{(1)}Δ B^{(1)}) = b.

Let A_{i}^{(1)} = A_{m+i} ∩ {x ∈ X | x < p^{(1)}} ⊂ A_{m+i} (we “cut-off" the set S i.e., all elements in the original chain which are ⩾ p^{(1)}). If A_{1}^{(1)} ≠ ∅, then A_{i}^{(1)} also form a strictly descending chain of finite sets

A_{1}^{(1)} > A_{2}^{(1)} > ⋯> A_{n}^{(1)} > · · ·.

such that all corresponding maxima coincide: a_{i}^{(1)} = a_{m+i} . Now apply the same construction to this chain and obtain the stationary value p^{(2)} < p^{(1)}. In this way, we obtain a strictly descending chain

p^{(1)} > p^{(2)} > ⋯> p^{(k)}

in X which eventually must stop since X is well ordered. This means that at this point A_{1}^{(k)} = ∅, the construction can not be continued and the original sequence must be finite. This proves the theorem. □

If we now apply this theorem to the sequence of finite sets of exponents of polynomials in the division algorithm, we obtain the previous theorem: the fact that in the reduction process, one can arbitrarily choose the term for the next reduction in the set Supp_{G}(f). This leads to a conclusion that for certain special classes of polynomials, one could try to find heuristics which could improve the calculation speed of a Gröbner basis. This remark could open a quite new and broad area of research.

5. Application to Gröbner bases

As an illustration of free choice in the reduction process, we will apply it in order to obtain a new equivalent characterisation of Gröbner basis. One of the standard definitions of a Gröbner basis of an ideal is the following (see [1]).

Definition 5.1. The basis G = {g_{1}, …, g_{m}} of an ideal (g_{1}, …, g_{m}) = I ⊂

K[x_{1}, …, x_{n}] is called a Gröbner basis, if the leading term lt(f) of any f ∈ I is divisible by some of the leading terms lt(g_{1}), …lt(g_{m}).

Its nice properties, such as the uniqueness of the reduced Gröbner basis of a given ideal and the uniqueness of the remainder obtained by complete reduction process with respect to Gröbner basis, are widely used for algorithmic and calculational purposes. Using the above theorem, this standard definition of Gröbner basis could be slightly relaxed, as the following statement in (3) shows. Recall that the syzygy in (6) below is the polynomial

S(g, h) := \frac{lcm(lt(g), lt(h))}{lt(g)} · g − \frac{lcm(lt(g), lt(h))}{lt(h)} · h.

Theorem 5.1. Let I = (g_{1}, …, g_{m}) ⊂ K[x_{1}, …, x_{n}] be the ideal generated by the set G = {g_{1}, …, g_{m}}. The following conditions are equivalent.

(1) G = {g_{1}, …, g_{m}} is a Gröbner basis;

(2) For all nonzero f ∈ I, lt(f) ∈ Supp_{G}(f);

(3) For all nonzero f ∈ I, Supp_{G}(f) ≠ ∅;

(4) The remainder h of a complete reduction process f →_{G} h with Supp_{G}(h) = ∅ is uniquely determined;

(5) For all f ∈ I, f →_{G} 0;

(6) All syzygies S(g_{i}, g_{j}) →_{G} 0

Proof. Equivalences (1) ⇔ (2) ⇔ (4) ⇔ (5) ⇔ (6) are standard (see [1] or [2]) and are stated here just for reasons of completeness. The proof is required only for the new equivalent condition (3). Obviously, (2) ⇒ (3). Suppose that (3) holds and let f →_{G} h_{1} and f →_{G} h_{2}. Then h_{1} − h_{2} ∈ I and Supp_{G}(h_{1} − h_{2}) = ∅ which contradicts (3). Therefore, (3) ⇒ (4) is proved. □

References

1. D. Cox, J. Little, D. O’Shea, Ideals, Varieties, and Algorithms, 2nd ed., Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997

2. W. Adams, P. Loustaunau, An Introduction to Gröbner Bases, Grad. Stud. Math. 3, American Mathematical Society, 1994

3. B. Buchberger, Introduction to Gröbner bases; in: B. Buchberger, F. Winkler (editors), Gröbner Bases and Applications, London Math. Soc. Lect. Notes 251, Cambridge Univ. Press, 1998, pp. 3–31

Matematički fakultet (Received 15 08 2014) Univerzitet u Beogradu Beograd Serbia

    acal@matf.bg.ac.rs