Characterizations of Border Bases

Achim Kehrein and Martin Kreuzer

Fachbereich Mathematik Universität Dortmund D-44221 Dortmund, Germany

Abstract

This paper presents characterizations of border bases of zero-dimensional polynomial ideals that are analogous to the known characterizations of Gröbner bases. Based on a Border Division Algorithm, a variant of the usual Division Algorithm, we characterize border bases as border prebases with one of the following equivalent properties: special generation, generation of the border form ideal, confluence of the corresponding rewrite relation, reduction of S-polynomials to zero, and lifting of syzygies. The last characterization relies on a detailed study of the relative position of the border terms and their syzygy module. In particular, a border prebasis is a border basis if and only if all fundamental syzygies of neighboring border terms lift; these liftings are easy to compute.

Key words: border basis, division algorithm, syzygy module

1 Introduction

Auzinger and Stetter [1], Möller [5], and Mourrain [6], for instance, used border bases successfully to solve zero-dimensional polynomial systems of equations. One of the attractive features of border bases is that they behave numerically better than Gröbner bases. Their key role in numerical polynomial algebra is emphasized in, for example, the new book by Hans Stetter [7]. Recently, border bases have also been applied to statistics, cf. Caboara and Robbiano [2].

Kehrein, Kreuzer, and Robbiano [3] started to lay solid algebraic foundations of the theory of border bases. In the present paper we commence the brickwork and characterize border bases analogously to known characterizations

  Email addresses: Achim.Kehrein@mathematik.uni-dortmund.de (Achim
Kehrein), Martin.Kreuzer@uni-dortmund.de (Martin Kreuzer).

Preprint submitted to Journal of Pure and Applied Algebra 28 April 2004

of Gröbner bases; the latter are collected, for example, in Kreuzer and Robbiano [4, Theorem 2.4.1]. Our basic tool is the Border Division Algorithm, which we present in Section 2; it divides a polynomial by a list of polynomials. Unlike the usual Division Algorithm, it does not require a term ordering; instead, the divisor polynomials must constitute a border prebasis with respect to an order ideal of terms. Accordingly, the familiar reduction of leading terms is substituted by a reduction of terms with largest index, where the index measures a distance from the order ideal. This adapted reduction process is carefully designed to avoid infinite loops.

In Section 3, we apply the Border Division Algorithm and, thus, obtain immediately two characterizing properties of border bases: special generation of the ideal (see Proposition 9) and generation of the border form ideal (see Proposition 11). Another characterization of border bases uses the rewrite relation generated by the border prebasis. This is a trickier subject, because the rewrite relation is in general not Noetherian. In other words, we consider a reduction process with infinite loops (see Example 12). Surprisingly, confluence of this rewrite relation still is equivalent to the border basis property (see Proposition 14).

Section 4 presents a border basis analogue of Buchberger’s criterion. Its proof uses Mourrain’s characterization of border bases in terms of formal multiplication matrices (see Proposition 16) and a lengthy, but straightforward computation. This computation reveals that the border basis property is equivalent to the condition that the S-polynomials of neighboring border terms reduce to zero (see Proposition 18); here, two distinct border terms b and b′ will be called neighbors, if b = xb′ or xb = yb′ for some indeterminates x, y.

The topic of the final section is the lifting of border syzygies. First, we study the relative position of the border terms and their syzygy module. In particular, we show that the border is connected with respect to the neighborhood relation (see Proposition 19) and that the neighbor syzygies generate the module of border syzygies (see Proposition 21). Next, we introduce the concept of a lifting of a border syzygy (see Definition 22) and show that, if liftings exist, then they will be computed easily for neighbor syzygies (see Example 23). Then, we characterize border bases as border prebases, for which all border syzygies lift or, equivalently, all neighbor syzygies lift. (see Proposition 25). After discussing possible border bases analogues of homogeneous syzygies, we conjecture that the liftings of the neighbor syzygies generate the syzygy module of a border basis. We close the paper with a partial result to support this conjecture (see Proposition 30).

Acknowledgements: The authors would like to thank Lorenzo Robbiano and Hans J. Stetter for helpful discussions.

2 Border Division

In the following we use the notation and definitions introduced in [3]. In particular, we work in the polynomial ring P = K[x_{1}, …, x_{n}] over a field K. The monoid of terms (or monomials or power products) of P is denoted by 𝕋^{n}. For every d ≥ 0, we let 𝕋_{d}^{n} be the set of terms of degree d.

Definition 1 A non-empty set of terms O ⊆ 𝕋^{n} is called an order ideal if t ∈ O implies t′ ∈ O for every term t′ dividing t. The border of O is the set of terms

∂O = 𝕋_{1}^{n} · O \ O = (x_{1}O ∪ ⋯ ∪ x_{n}O) \ O

and the first border closure of O is \overline{∂O} = O ∪ ∂O. For every k ≥ 1, we inductively define the (k + 1)^{st} border ∂^{k+1}O = ∂(\overline{∂^{k}O}) and the (k + 1)^{st} border closure \overline{∂^{k+1}O} = \overline{∂^{k}O} ∪ ∂^{k+1}O. Finally, we let ∂^{0}O = \overline{∂^{0}O} = O.

The following proposition is shown in [3, Proposition 3.4]. It contains three ubiquitous consequences of this definition.

Proposition 2 Let O be an order ideal.

a) For every k ≥ 1, we have ∂^{k}O = 𝕋_{k}^{n} · O \ 𝕋_{<k}^{n} · O.

b) For every k ≥ 1, we have a disjoint union \overline{∂^{k}O} = ⋃_{i=0}^{k} ∂^{i}O. In particular, we have a disjoint union 𝕋^{n} = ⋃_{i=0}^{∞} ∂^{i}O.

c) A term t ∈ 𝕋^{n} is divisible by a term in ∂O if and only if t ∈ 𝕋^{n} \ O.

In view of this result, we define ind_{O}(t) = min\{k ≥ 0 | t ∈ \overline{∂^{k}O}\} for every term t ∈ 𝕋^{n} and call it the index of t with respect to O. Given a nonzero polynomial f = c_{1}t_{1} + ⋯ + c_{s}t_{s} ∈ P, where c_{1}, …, c_{s} ∈ K \ {0} and t_{1}, …, t_{s} ∈ 𝕋^{n}, we order the terms in the support of f such that ind_{O}(t_{1}) ≥ ind_{O}(t_{2}) ≥ ⋯ ≥ ind_{O}(t_{s}). Then we call ind_{O}(f) = ind_{O}(t_{1}) the index of f. The following basic properties of the index were shown in [3, Proposition 3.6]. Note how the two concepts index and degree are complementing one another.

Proposition 3 Let O be an order ideal, let t, t′ ∈ 𝕋^{n}, and let f, g ∈ P \ {0}.

a) The index ind_{O}(t) is the smallest natural number k such that t = t_{1}t_{2} with t_{1} ∈ O and t_{2} ∈ 𝕋_{k}^{n}.

b) ind_{O}(t t′) ≤ deg(t) + ind_{O}(t′)

c) If f + g ≠ 0, then ind_{O}(f + g) ≤ max{ind_{O}(f), ind_{O}(g)}.

d) ind_{O}(fg) ≤ max{deg(f) + ind_{O}(g), deg(g) + ind_{O}(f)}

The index and the border form possess properties resembling those of term orderings and leading terms. However, index inequalities need not be preserved under multiplication.

Example 4 Let P = ℚ[x, y] and O = {1, x, x^{2}, x^{3}, y, y^{2}}. Clearly, the set O is an order ideal. Its border is ∂O = {x^{4}, x^{3}y, x^{2}y, xy, xy^{2}, y^{3}}. Hence we have ind_{O}(y^{2}) = 0 < 1 = ind_{O}(xy), but, multiplying both sides by x, we get ind_{O}(xy^{2}) = 1 = ind_{O}(x^{2}y).

This example also shows that the decomposition P = ⨁_{i≥0}(⨁_{{t|ind_{O}(t)=i}} K · t) does not endow P with the structure of a graded ring. Nevertheless the index provides a distance of a term from the order ideal as well as a partial ordering of terms. It allows us to substitute the usual Division Algorithm using a term ordering (see, for instance, [4, Theorem 1.6.4]) by a border version using a partial ordering. For this purpose we introduce the following preliminary notion of a border basis.

Definition 5 Given an order ideal O ⊆ 𝕋^{n} with border ∂O = {b_{1}, …, b_{ν}}, a set of polynomials {g_{1}, …, g_{ν}} ⊆ P is called an O-border prebasis if the polynomials have the form g_{i} = b_{i}+h_{i} such that h_{i} ∈ P satisfies Supp(h_{i}) ⊆ O for i = 1, …, ν.

Proposition 6 (The Border Division Algorithm) Let O = {t_{1}, …, t_{μ}} be an order ideal, let ∂O = {b_{1}, …, b_{ν}} be its border, and let {g_{1}, …, g_{ν}} be an O-border prebasis. Given a polynomial f ∈ P, consider the following instructions. D1. Let f_{1} = ⋯ = f_{ν} = 0, c_{1} = ⋯ = c_{μ} = 0, and h = f. D2. If h = 0, then return (f_{1}, …, f_{ν}, c_{1}, …, c_{μ}) and stop. D3. If ind_{O}(h) = 0, then find c_{1}, …, c_{μ} ∈ K such that h = c_{1}t_{1} + ⋯ + c_{μ}t_{μ}.

Return (f_{1}, …, f_{ν}, c_{1}, …, c_{μ}) and stop. D4. If ind_{O}(h) > 0, then let h = a_{1}h_{1}+⋯+a_{s}h_{s} with a_{1}, …, a_{s} ∈ K\{0} and

h_{1}, …, h_{s} ∈ 𝕋^{n} such that ind_{O}(h_{1}) = ind_{O}(h). Determine the smallest index i ∈ {1, …, ν} such that h_{1} factors as h_{1} = t′ b_{i} with a term t′ of degree ind_{O}(h) − 1. Subtract a_{1}t′g_{i} from h, add a_{1}t′ to f_{i}, and continue with step D2.

This is an algorithm that returns a tuple (f_{1}, …, f_{ν}, c_{1}, …, c_{μ}) ∈ P^{ν} × K^{μ} such that

f = f_{1}g_{1} + ⋯ + f_{ν}g_{ν} + c_{1}t_{1} + ⋯ + c_{μ}t_{μ}

and deg(f_{i}) ≤ ind_{O}(f) − 1 for all i ∈ {1, …, ν} with f_{i}g_{i} ≠ 0. This representation does not depend on the choice of the term h_{1} in Step D4.

Proof. First we show that the instructions can be executed. In Step D3 the fact that ind_{O}(h) = 0 implies that all terms in the support of h have index zero, i.e. that they are all in O. In Step D4 we write h as a K -linear combination of terms and note that at least one of them, say h_{1}, has to have index k = ind_{O}(h). By Proposition 3.a, there is a factorization h_{1} = t̃t_{i} for some term t̃ of degree k and some t_{i} ∈ O, and there is no such factorization with a term t̃ of smaller degree. Since k > 0, we can write t̃ = t′ x_{j} for some t′ ∈ 𝕋^{n} and j ∈ {1, …, n}. Then we have deg(t′) = k − 1, and the fact that t̃ has the smallest possible degree implies x_{j} t_{i} ∈ ∂O. Thus we have h_{1} = t′ (x_{j} t_{i}) = t′ b_{k} for some b_{k} ∈ ∂O.

Next we prove termination. We show that Step D4 is performed only finitely many times. Let us investigate the subtraction h − a_{1}t′g_{i} in Step D4. Using Definition 5, we find a representation g_{i} = b_{i} − ∑_{k=1}^{μ} α_{ki}t_{k} such that α_{ki} ∈ K for k = 1, …, μ. Hence the subtraction becomes

h − a_{1}t′g_{i} = a_{1}h_{1} + … + a_{s}h_{s} − a_{1}t′b_{i} + a_{1}t′ ∑_{k=1}^{μ} α_{ki}t_{k}.

Now a_{1}h_{1} = a_{1}t′b_{i} shows that a term of index ind_{O}(h) is removed from h and replaced by terms of the form t′ t_{ℓ} ∈ \overline{∂^{k−1}O} which have strictly smaller index. The algorithm terminates after finitely many steps because, for a given term, there are only finitely many terms of smaller or equal index.

Finally, we prove correctness. To do so, we show that the equation

f = h + f_{1}g_{1} + ⋯ + f_{ν}g_{ν} + c_{1}t_{1} + ⋯ + c_{μ}t_{μ}

is an invariant of the algorithm. It is satisfied at the end of Step D1. A polynomial f_{i} is only changed in Step D4. There the subtraction h − a_{1}t′g_{i} is compensated by the addition (f_{i} + a_{1}t′)g_{i}. The constants c_{1}, …, c_{μ} are only changed in Step D3 in which h is replaced by the expression c_{1}t_{1} + … + c_{μ}t_{μ}. When the algorithm stops, we have h = 0. This proves the stated representation of f.

The additional claim that this representation does not depend on the choice of h_{1} in Step D4 follows from the observation that h_{1} is replaced by terms of strictly smaller index. Thus the different executions of Step D4 corresponding to the reduction of several terms of a given index in h do not interfere with one another, and the final result – after all those terms have been rewritten – is independent of the order in which they are taken care of. ⊓ ⊔

Notice that in Step D4 the algorithm uses a representation of h that is not necessarily unique due to the partial aspect of the ordering. Also there may be several factorizations h_{1} = t̃t_{i}. We choose the index i minimally to determine this step of the algorithm uniquely, but this particular choice is not forced upon us. Finally, the result of the division depends on the numbering of the elements of ∂O, as the next example shows.

Example 7 Let P = ℚ[x, y] and let O = {1, x}. The border of O is ∂O = {b_{1}, b_{2}, b_{3}} with b_{1} = y, b_{2} = xy, and b_{3} = x^{2}. We apply the Border Division Algorithm to divide f = x^{2}y +x^{2} +2xy by (g_{1}, g_{2}, g_{3}), where g_{1} = y, g_{2} = xy − 1, and g_{3} = x^{2} − 1. The step by step computations are: D1. Let f_{1} = f_{2} = f_{3} = 0 and c_{1} = c_{2} = 0 as well as h = f. D4. Since ind_{O}(h) = 2, we have h_{1} = x^{2}y = x^{2} b_{1}. Thus we put h = x^{2} + 2xy

and f_{1} = xy. D4. Since ind_{O}(h) = 1, we choose h_{1} = x^{2} = b_{3} and put h = 2xy + 1 as well

as f_{3} = 1. D4. Since ind_{O}(h) = 1, we have h_{1} = xy = b_{2} and put h = 3 as well as

f_{2} = 2. D3. The algorithm returns (xy, 2, 1, 3, 0). Therefore, there is a representation

f = x^{2} (y) + 2 (xy − 1) + (x^{2} − 1) + 3 = x^{2} g_{1} + 2 g_{2} + g_{3} + 3.

However, when we apply the algorithm to the shuffled tuple (g′_{1}, g′_{2}, g_{3}) where g′_{1} = g_{2} and g′_{2} = g_{1}, it computes the representation

f = (x + 2) (xy − 1) + (x^{2} − 1) + 3 + x = (x + 2) g′_{1} + 0 · g′_{2} + g_{3} + 3 + x.

If we fix the tuple G = (g_{1}, …, g_{ν}), the result of the Border Division Algorithm is uniquely determined. This we do. Given an order ideal O = {t_{1}, …, t_{μ}} and a polynomial f ∈ P, let f = f_{1}g_{1} + ⋯ + f_{ν}g_{ν} + c_{1}t_{1} + ⋯ + c_{μ}t_{μ} be a representation computed by the Border Division Algorithm. Then NR_{O,G}(f) = c_{1}t_{1} + ⋯ + c_{s}t_{s} is called the normal O-remainder of f. As we saw in the example, the normal O-remainder sometimes depends on the order of the elements in G.

By construction, a polynomial f and NR_{O,G}(f) represent the same residue class modulo (g_{1}, …, g_{ν}). This shows that the residue classes of the terms in O generate P/(g_{1}, …, g_{ν}) as a K -vector space. However, they do not necessarily constitute a K -basis of this vector space.

In particular, if O consists of finitely many terms, then the ideal (g_{1}, …, g_{ν}) generated by an O-border prebasis is zero-dimensional.

3 Characterizations of Border Bases

First we prescribe the setting that is used throughout the remainder of this paper. Let O = {t_{1}, …, t_{μ}} be an order ideal consisting of finitely many terms. We let ∂O = {b_{1}, …, b_{ν}} be its border, G = {g_{1}, …, g_{ν}} an O-border prebasis, and I a zero-dimensional ideal of P containing G. In this setting, a border basis is defined as follows.

Definition 8 The O-border prebasis {g_{1}, …, g_{ν}} is called an O-border basis of I if the residue classes of the elements of O form a K -vector space basis of P/I.

If I has an O-border basis G, then it is uniquely determined by O and G generates I [3, Section 4.1]. According to the remarks at the end of the previous section a border prebasis is a border basis if and only if the residue classes of t_{1}, …, t_{μ} modulo I are K -linearly independent or, equivalently, I ∩ ⟨O⟩_{K} = 0.

We are going to develop the theory of border bases in analogy with the development of the theory of Gröbner bases in [4, Chapter 2]. Hence, we shall prove characterizations of border bases which imitate the characterizations of Gröbner bases given there. Our first result is a border basis version of the so-called special generation property.

Proposition 9 (Border Bases and Special Generation) In the prescribed setting, the set G is an O-border basis of I if and only if one of the following equivalent conditions is satisfied.

A_{1}. For every f ∈ I \ {0}, there exist polynomials f_{1}, …, f_{ν} ∈ P such that

f = f_{1}g_{1} + ⋯ + f_{ν}g_{ν} and deg(f_{i}) ≤ ind_{O}(f) − 1 whenever f_{i}g_{i} ≠ 0. A_{2}. For every f ∈ I \ {0}, there exist polynomials f_{1}, …, f_{ν} ∈ P such that

f = f_{1}g_{1} + ⋯ + f_{ν}g_{ν} and max{deg(f_{i}) | i ∈ {1, …, ν}, f_{i}g_{i} ≠ 0} =

ind_{O}(f) − 1.

Proof. First we show that A_{1} holds if G is an O-border basis. The Border Division Algorithm computes a representation f = f_{1}g_{1}+⋯+f_{ν}g_{ν}+c_{1}t_{1}+⋯+ c_{μ}t_{μ} with f_{1}, …, f_{ν} ∈ P and c_{1}, …, c_{μ} ∈ K such that deg(f_{i}) ≤ ind_{O}(f) − 1 for i = 1, …, ν. Then c_{1}t_{1} + ⋯ + c_{μ}t_{μ} ≡ 0 (mod I), and the hypothesis implies c_{1} = ⋯ = c_{μ} = 0.

Next we prove that A_{1} implies A_{2}. If deg(f_{i}) < ind_{O}(f) − 1, then Proposition 3.b yields ind_{O}(f_{i}g_{i}) ≤ deg(f_{i}) + ind_{O}(g_{i}) = deg(f_{i}) + 1 < ind_{O}(f). By Proposition 3.c, there has to be at least one number i ∈ {1, …, ν} such that deg(f_{i}) = ind_{O}(f) − 1.

Finally, assume A_{2} and let c_{1}, …, c_{μ} ∈ K satisfy c_{1}t_{1} + ⋯ + c_{μ}t_{μ} ∈ I. Then either f = c_{1}t_{1}+⋯+c_{μ}t_{μ} equals the zero polynomial or not. In the latter case we apply the first part of A_{2} to obtain a representation f = f_{1}g_{1} + ⋯ + f_{ν}g_{ν} with f_{1}, …, f_{ν} ∈ P. Since f ≠ 0, we have max{deg(f_{i}) | i ∈ {1, …, ν}, f_{i}g_{i} ≠ 0} ≥ 0. But ind_{O}(f)−1 = −1, which contradicts the second part of A_{2}. Hence, f is zero, I ∩ ⟨O⟩_{K} = 0, and the set G is an O-border basis. ⊓ ⊔

Commonly, Gröbner bases are defined as sets of polynomials whose leading terms generate the leading term ideal. In the theory of border bases, leading terms have to be replaced with more general border forms which are defined as follows.

Definition 10 Given a polynomial f ∈ P, there is a representation f = a_{1}u_{1} + ⋯ + a_{s}u_{s} with a_{1}, …, a_{s} ∈ K \ {0} and u_{1}, …, u_{s} ∈ 𝕋^{n} such that ind_{O}(u_{1}) ≥ ⋯ ≥ ind_{O}(u_{s}).

a) The polynomial

BF_{O}(f) = ∑_{{i|ind(u_{i})=ind(f)}} a_{i}u_{i}

is called the border form of f with respect to O. For f = 0, we let BF_{O}(f) = 0.

b) Given an ideal I ⊆ P, the ideal BF_{O}(I) = (BF_{O}(f) | f ∈ I) is called the border form ideal of I with respect to O.

The definition is independent of the chosen representation. As an important example, the elements of the O-border prebasis G have the border form BF_{O}(g_{i}) = b_{i}; in particular, they consist of only one term. Now we characterize border bases by their border form ideal.

Proposition 11 (Border Bases and the Border Form Ideal) In the prescribed setting, the set G is an O-border basis of I if and only if one of the following equivalent conditions is satisfied. B_{1}. For every f ∈ I, the support of BF_{O}(f) is contained in 𝕋^{n} \ O. B_{2}. We have BF_{O}(I) = (b_{1}, …, b_{ν}).

Proof. First we show that a border basis satisfies condition B_{1}. Suppose that the border form of a polynomial f ∈ I \ {0} contains a term of O in its support. Then all terms in the support of f are contained in O, i.e. f = c_{1}t_{1} + ⋯ + c_{μ}t_{μ} for suitable c_{1}, …, c_{μ} ∈ K. The border basis hypothesis implies c_{1} = ⋯ = c_{μ} = 0, which contradicts f ≠ 0.

Next we prove that B_{1} implies B_{2}. Since g_{i} ∈ I, we have b_{i} = BF_{O}(g_{i}) ∈ BF_{O}(I) for i = 1, …, ν. To prove the reverse inclusion, let f ∈ I \ {0}. By B_{1} and Proposition 2.c, every term in the support of BF_{O}(f) is divisible by a term in ∂O. Hence the border form of f is contained in (b_{1}, …, b_{ν}).

Finally, we show that B_{2} implies that G is a border basis. Let c_{1}, …, c_{μ} ∈ K be elements such that f = c_{1}t_{1} + ⋯ + c_{μ}t_{μ} ∈ I. Then all terms in the support of f have index zero, and thus f = BF_{O}(f). So, B_{2} and Proposition 2.c imply c_{1} = ⋯ = c_{μ} = 0. ⊓ ⊔

To characterize border bases in analogy with conditions C_{1}) – C_{4}) of [4, Section 2.2] we define the rewrite relation associated to G. Let f ∈ P be a polynomial such that t ∈ Supp(f) is a multiple of a border term t = t′ b_{i}.

Let c ∈ K be the coefficient of t in f. Then h = f − ct′g_{i} does not contain the term t anymore. We say that f reduces to h in one step using g_{i} and write f ⟶^{g_{i}} h. (Instead one may consider the more restrictive rewrite rule that, in addition, the factorization t = t′b_{i} must be optimal in the sense ind(t) = deg(t′) + 1. For instance, the reduction steps used in the Border Division Algorithm satisfy this additional condition. However, the results below indicate that our less restrictive rewrite rule is an appropriate choice.) The reflexive, transitive closure of the relations ⟶^{g_{i}}, i ∈ {1, …, ν}, is called the rewrite relation associated to G and is denoted by ⟶^{G}. The equivalence relation generated by ⟶^{G} is denoted by ⟷^{G}. In stark contrast to Gröbner basis theory, rewrite relations associated to border prebasis are, in general, not Noetherian; this is demonstrated by the following example.

Example 12 Let P = ℚ[x, y] and O = {1, x, y, x^{2}, y^{2}}. Then O is an order ideal with border ∂O = {xy, x^{3}, x^{2}y, xy^{2}, y^{3}}. Consider the O-border prebasis G = {g_{1}, …, g_{5}}, where g_{1} = xy − x^{2} − y^{2}, g_{2} = x^{3}, g_{3} = x^{2}y, g_{4} = xy^{2}, and g_{5} = y^{3}. The chain of reductions

x^{2}y ⟶^{g_{1}} x^{3} + xy^{2} ⟶^{g_{2}} xy^{2} ⟶^{g_{1}} x^{2}y + y^{3} ⟶^{g_{5}} x^{2}y

can be repeated indefinitely, and hence ⟶^{G} is not Noetherian.

The following properties of the equivalence relation ⟷^{G} can be proved in exactly the same way as the corresponding properties in Gröbner basis theory (cf. [4, Proposition 2.2.2]).

Proposition 13 Let ⟷^{G} be the rewrite equivalence relation associated to an O-border prebasis G = {g_{1}, …, g_{ν}}, and let f_{1}, f_{2}, f_{3}, f_{4} ∈ P.

a) If f_{1} ⟷^{G} f_{2} and f_{3} ⟷^{G} f_{4}, then f_{1} + f_{3} ⟷^{G} f_{2} + f_{4}.

b) If f_{1} ⟷^{G} f_{2}, then f_{1}f_{3} ⟷^{G} f_{2}f_{3}.

c) We have f_{1} ⟷^{G} f_{2} if and only if f_{1} − f_{2} ∈ (g_{1}, …, g_{ν}).

According to property c) the rewrite equivalence relation ⟷^{G} is in fact the congruence relation modulo the ideal (g_{1}, …, g_{ν}). In other words, applying reduction steps forwards as well as backwards to a polynomial, we can move through the complete congruence class modulo (g_{1}, …, g_{ν}) in search for a “good” representative.

Regardless of their lack of Noetherianity, rewrite relations ⟶^{G} characterize border bases by the confluence property. In this respect ⟶^{G} is called confluent if for any two co-initial reductions f_{1} ⟶^{G} f_{2} and f_{1} ⟶^{G} f_{3} there exist co-terminal reductions f_{2} ⟶^{G} f_{4} and f_{3} ⟶^{G} f_{4}. Finally, a polynomial f ∈ P is called G-reduced if f ⟶^{G} h implies h = f.

For example, any polynomial f with support in O is G-reduced; by Proposition 2.c, it cannot contain a term that can be reduced. In particular, the normal remainder NR_{O,G}(f) computed by the Border Division Algorithm is G-reduced.

Proposition 14 (Border Bases and Rewrite Relations) In the prescribed setting, the set G is an O-border basis of I if and only if one of the following equivalent conditions is satisfied.

C_{1}. For f ∈ P, we have f ⟶^{G} 0 if and only if f ∈ I. C_{2}. If f ∈ I is G-reduced, then f = 0. C_{3}. For every f ∈ P, there exists a G-reduced element h ∈ P such that

f ⟶^{G} h and h is unique.

C_{4}. The rewrite relation ⟶^{G} is confluent.

Proof. First we show that a border basis has property C_{1}. If a polynomial f ∈ P satisfies f ⟶^{G} 0, then it is enough to collect the subtractions performed by the individual reduction steps on the right-hand side to obtain f ∈ (g_{1}, …, g_{ν}). Conversely, let f ∈ I. We apply the Border Division Algorithm to f; it performs reduction steps using elements of G to compute the normal remainder NR_{O,G}(f) ∈ ⟨O⟩_{K}. Since f ∈ I, we also have NR_{O,G}(f) ∈ I. The hypothesis that G is a border basis yields NR_{O,G}(f) ∈ I ∩ ⟨O⟩_{K} = 0, i.e.

f ⟶^{G} 0.

To prove that C_{1} implies C_{2}, note that C_{1} shows f ⟶^{G} 0 for f ∈ I. Thus a G-reduced polynomial f ∈ I has to be zero. Next we prove that C_{2} implies C_{3}. Let f ∈ P. The Border Division Algorithm performs a reduction f ⟶^{G} NR_{O,G}(f), i.e. there exists a reduction to a G-reduced polynomial. Suppose that f ⟶^{G} h and h is G-reduced. Then h − NR_{O,G}(f) ∈ I and the support of this difference is contained in O. Thus it is G-reduced and C_{2} yields h = NR_{O,G}(f). Altogether, the normal remainder of f has the properties required by C_{3}.

Now we show that C_{3} implies C_{4}. Let f_{1} ⟶^{G} f_{2} and f_{1} ⟶^{G} f_{3} be co-initial reductions. The Border Division Algorithm produces f_{1} ⟶^{G} NR_{O,G}(f_{2}) and f_{1} ⟶^{G} NR_{O,G}(f_{3}). Since normal remainders are G-reduced, condition C_{3} implies NR_{O,G}(f_{2}) = NR_{O,G}(f_{3}). Therefore, there are co-terminal reductions

f_{2} ⟶^{G} f_{4} and f_{3} ⟶^{G} f_{4} with f_{4} = NR_{O,G}(f_{2}) = NR_{O,G}(f_{3}).

Finally, to show that G is a border basis if it satisfies C_{4}, we can use Proposition 13.c and proceed as in the proof of C_{4}) ⇒ C_{1}) in [4, Proposition 2.2.5].

⊓ ⊔

Given an O-border basis G = {g_{1}, …, g_{ν}} and f ∈ P, the unique G-reduced polynomial h such that f ⟶^{G} h is the normal remainder NR_{O,G}(f). Hence it is effectively computed by the Border Division Algorithm and it agrees with the normal form NF_{O,I}(f) with respect to the ideal I = (g_{1}, …, g_{ν}). The properties of the normal form are studied in [3, Section 4.2].

4 A Buchberger Criterion for Border Bases

Instead of examining a polynomial ideal I directly, one can consider its quotient algebra P/I. The K -vector space structure of P/I suffices to single out the zero-dimensional ideals, as they are precisely those ideals with a finitedimensional quotient. Now each multiplication by an element of P/I defines a K -linear map and thus we obtain a P -module structure on P/I. This P - module structure determines the ideal I as its annihilator. In particular, the indeterminates x_{1},… x_{n} define so-called mutliplication matrices which commute. This procdure can be reversed in the following sense. For each border prebasis we define formal multiplication matrices. Then the border prebasis is a border basis if and only if the formal multiplication matrices commute. A detailed account of these remarks is given in [3].

Definition 15 Let O = {t_{1}, …, t_{μ}} be an order ideal, ∂O = {b_{1}, …, b_{ν}} its border, and G = {g_{1}, …, g_{ν}} an O-border prebasis with

g_{j} = b_{j} − ∑_{m=1}^{μ} α_{mj}t_{m} , 1 ≤ j ≤ ν

For 1 ≤ r ≤ n, define the r-th formal multiplication matrix X_{r} := (ξ_{kℓ}^{(r)}) by

ξ_{kℓ}^{(r)} = \{ \begin{matrix}δ_{ki} & , if t_{i} = x_{r} t_{ℓ} \\ α_{kj} & , if b_{j} = x_{r} t_{ℓ} \end{matrix} .

The formal multiplication matrices encode the following procedure. First, we multiply an element of ⟨O⟩_{K} by the indeterminate x_{r} and, second, whenever x_{r} t_{i} = b_{j} is a border term, we reduce by the corresponding border polynomial g_{j}. The reduction guarantees that the result stays in ⟨O⟩_{K}. More concretely, the elements c_{1} t_{1} + … + c_{μ} t_{μ} ∈ ⟨O⟩_{K} are encoded as column vectors c_{1} e_{1} + … + c_{μ} e_{μ} ∈ K^{μ}. For example, x_{r} t_{i} corresponds to X_{r} (c_{1}, …, c_{μ})^{T}.

Bernard Mourrain [6] showed the following result. A proof using our notation and terminology is contained in [3].

Proposition 16 (Border Bases and Formal Multiplication Matrices) In the setting of Definition 15, the border prebasis G is a border basis if and only if the formal multiplication matrices commute, i.e. if and only if X_{r} X_{s} = X_{s} X_{r} for all r, s ∈ {1, …, n}.

Next we want to analyze these commutativity conditions in more detail by considering their effect on an arbitrary base vector e_{i}. For each i ∈ {1, …, μ} we compare X_{r} X_{s} e_{i} with X_{s} X_{r} e_{i}. Translating the comparision back into the language of ⟨O⟩_{K}, we shall find that the resulting description depends on the position of t_{i} relative to the border. The following case by case discussion reveals the details.

To lighten the index load we abbreviate x = x_{r} and y = x_{s}.

\begin{matrix}t_{k} & t_{l} \\ t_{i} & t_{j} \end{matrix} First case: Let x y t_{i} ∈ O.

Since O is an order ideal, we also have x t_{i}, y t_{i} ∈ O, say x t_{i} = t_{j}, y t_{i} = t_{k}, and x y t_{i} = t_{ℓ}. Then X Y e_{i} = X e_{k} = e_{ℓ} = Y e_{j} = Y X t_{i}, i.e., the commutativity condition holds by definition of the formal multiplication matrices.

\begin{matrix}t_{k} & b_{l} \\ t_{i} & t_{j} \end{matrix} Second case: Let x y t_{i} ∈ ∂O and x t_{i}, y t_{i} ∈ O.

Say x t_{i} = t_{j}, y t_{i} = t_{k}, and x y t_{i} = b_{ℓ}. Then

X Y e_{i} = X e_{k} = ( α_{1ℓ} ; ⋮ ; α_{μℓ} ) = Y e_{j} = Y X e_{i}

Again, commutativity follows immediately from the definition of the formal multiplication matrices.

\begin{matrix}b_{k} & b_{l} \\ t_{i} & t_{j} \end{matrix} Third case: Let x t_{i} ∈ O and y t_{i} ∈ ∂O.

Since \overline{∂O} and O are order ideals, this case implies x y t_{i} ∈ ∂O. Say x t_{i} = t_{j}, y t_{i} = b_{k}, and x y t_{i} = b_{ℓ}. The commutativity condition becomes

X ( α_{1k} ; ⋮ ; α_{μk} ) = ( α_{1ℓ} ; ⋮ ; α_{μℓ} )

i.e., ∑_{m=1}^{μ} ξ_{pm}α_{mk} = α_{pℓ} for all p ∈ {1, …, μ}. According to the definition of the formal multiplication matrices, this condition can be rewritten as follows.

∑_{{m \atop x tm=t_{φ(m)}}} δ_{p,φ(m)}α_{mk} + ∑_{{m \atop x tm=b_{ψ(m)}}} α_{p,ψ(m)}α_{mk} = α_{pℓ} , 1 ≤ p ≤ μ (1)

The first sum stretches over all indices m for which x t_{m} ∈ O. For such an index m, let φ(m) be the index with x t_{i} = t_{φ(m)}. The notation in the second sum is chosen analogously.

\begin{matrix}b_{k} & ∗ \\ t_{i} & b_{j} \end{matrix} Fourth case: Let x t_{i}, y t_{i} ∈ ∂O.

Say x t_{i} = b_{j} and y t_{i} = b_{k}. The commutativity condition becomes

X ( α_{1k} ; ⋮ ; α_{μk} ) = Y ( α_{1j} ; ⋮ ; α_{μj} )

i.e., ∑_{m=1}^{μ} ξ_{pm}α_{mk} = ∑_{m=1}^{μ} η_{pm}α_{mj} for all p ∈ {1, …, μ}. This condition can be rewritten as

∑_{{m \atop x tm=t_{φ(m)}}} δ_{p,φ(m)}α_{mk} + ∑_{{m \atop x tm=b_{ψ(m)}}} α_{p,ψ(m)}α_{mk} =

∑_{{m \atop x tm=t_{ϱ(m)}}} δ_{p,ϱ(m)}α_{mj} + ∑_{{m \atop x tm=b_{σ(m)}}} α_{p,σ(m)}α_{mj} , 1 ≤ p ≤ μ  (2)

This covers all cases. The two cases with non-trivial commutativity conditions motivate the following definition.

Definition 17 Let b_{i}, b_{j} ∈ ∂O be two distinct border terms.

a) The border terms b_{i} and b_{j} are called next-door neighbors if b_{i} = x b_{j} for some x ∈ {x_{1}, …, x_{n}}.

b) The border terms b_{i} and b_{j} are called across-the-street neighbors if x b_{i} = y b_{j} for some x, y ∈ {x_{1}, …, x_{n}}.

c) The border terms b_{i} and b_{j} are called neighbors if they are next-door neighbors or across-the-street neighbors.

This definition comprises slightly more than the above case distinction. In a polynomial ring with at least three indeterminates there are order ideals that allow a constellation of border terms b_{j} = x b_{i} and b_{k} = y b_{i},

\begin{matrix}b_{k} & ∗ \\ b_{i} & b_{j} \end{matrix} ,

which, correctly, is absent from the above cases. The above case by case discussion considers at most the relations b_{j} = x b_{i} and b_{k} = y b_{i}, while it disregards x b_{k} = y b_{j}. Our definition also acknowledges b_{k} and b_{j} as neighbors.

In the remainder of this section we interpret the commutativity conditions in terms of rewrite rules.

Consider the next-door neighbor relation b_{ℓ} − x b_{k} = 0. The corresponding combination of border polynomials is

g_{ℓ} − x g_{k} = (b_{ℓ} − ∑_{m=1}^{μ} α_{mℓ}t_{m}) − x(b_{k} − ∑_{m=1}^{μ} α_{mk}t_{m})
= − ∑_{m=1}^{μ} α_{mℓ}t_{m} + ∑_{m=1}^{μ} α_{mk}(x t_{m})
= − ∑_{m=1}^{μ} α_{mℓ}t_{m} + ∑_{x t_{m}=t_{φ(m)}} α_{mk}t_{φ(m)} + ∑_{x t_{m}=b_{ψ(m)}} α_{mk}b_{ψ(m)}

= − ∑_{m=1}^{μ} α_{mℓ}t_{m} + ∑_{x t_{m}=t_{φ(m)}} α_{mk}t_{φ(m)} + ∑_{x t_{m}=b_{ψ(m)}} α_{mk}g_{ψ(m)}

+ ∑_{x t_{m}=b_{ψ(m)}}(α_{mk} ∑_{s=1}^{μ} α_{s,ψ(m)}t_{s})

Since (g_{1}, …, g_{ν}) ⊆ I, we obtain the congruence

0 ≡ − ∑_{m=1}^{μ} α_{mℓ}t_{m} + ∑_{x t_{m}=t_{φ(m)}} α_{mk}t_{φ(m)} + ∑_{x t_{m}=b_{ψ(m)}}(α_{mk} ∑_{s=1}^{μ} α_{s,ψ(m)}t_{s}) (mod I).

For a border basis the coefficient of each t_{p}, 1 ≤ p ≤ μ, on the right-hand side must vanish. This vanishing condition is exactly the commutativity condition (1).

Across-the-street neighbor combinations x g_{k} − y g_{j} are treated analogously. The corresponding combination of border polynomials is

x g_{k} − y g_{j} = x(b_{k} − ∑_{m=1}^{μ} α_{mk}t_{m}) − y(b_{j} − ∑_{m=1}^{μ} α_{mj}t_{m})
= − ∑_{m=1}^{μ} α_{mk}(x t_{m}) + ∑_{m=1}^{μ} α_{mj}(y t_{m})

= − ∑_{x t_{m}=t_{φ(m)}} α_{mk}t_{φ(m)} − ∑_{x t_{m}=b_{ψ(m)}} α_{mk}b_{ψ(m)}

+ ∑_{y t_{m}=t_{ϱ(m)}} α_{mj}t_{ϱ(m)} + ∑_{y t_{m}=b_{σ(m)}} α_{mj}b_{σ(m)}

= − ∑_{x t_{m}=t_{φ(m)}} α_{mk}t_{φ(m)} − ∑_{x t_{m}=b_{ψ(m)}} α_{mk}g_{ψ(m)}

− ∑_{x t_{m}=b_{ψ(m)}} α_{mk} ∑_{s=1}^{μ} α_{sψ(m)}t_{s}

+ ∑_{y t_{m}=t_{ϱ(m)}} α_{mj}t_{ϱ(m)} + ∑_{y t_{m}=b_{σ(m)}} α_{mj}g_{σ(m)}

+ ∑_{y t_{m}=b_{σ(m)}} α_{mj} ∑_{s=1}^{μ} α_{sσ(m)}t_{s}

We obtain the congruence

0 ≡ − ∑_{x t_{m}=t_{φ(m)}} α_{mk}t_{φ(m)} − ∑_{x t_{m}=b_{ψ(m)}} α_{mk} ∑_{s=1}^{μ} α_{sψ(m)}t_{s}

+ ∑_{y t_{m}=t_{ϱ(m)}} α_{mj}t_{ϱ(m)} + ∑_{y t_{m}=b_{σ(m)}} α_{mj} ∑_{s=1}^{μ} α_{sσ(m)}t_{s} (mod I)

Considering the coefficients individually produces the commutativity condition (2).

This computation allows us to characterize border bases analogously to Buchberger’s criterion for Gröbner bases. A similar result appears in [7, Theorem 8.11].

In Gröbner basis theory the S-polynomials are obtained by applying a syzygy of two leading terms to the corresponding polynomials. Analogously, we apply the fundamental syzygy of the border terms b_{i} and b_{j} and get the corresponding S-polynomial. More concretely, an S-polynomial has the form

S(g_{i}, g_{j}) = (lcm(b_{i}, b_{j})/b_{i}) g_{i} − (lcm(b_{i}, b_{j})/b_{j}) g_{j}.

Proposition 18 (Buchberger Criterion for Border Bases) In the prescribed setting, the O-border prebasis G is an O-border basis of I if and only if one of the following equivalent conditions is satisfied.

D_{1}. For all 1 ≤ i < j ≤ ν, the S-polynomial S(g_{i}, g_{j}) reduces to zero via ⟶^{G}. D_{2}. For all neighbors b_{i} and b_{j}, the S-polynomial S(g_{i}, g_{j}) reduces to zero

via ⟶^{G}.

Proof. Condition D_{1} holds if G is a border basis, since S(g_{i}, g_{j}) ∈ I and G satisfies Condition C_{1}. Since D_{1} logically implies D_{2}, it remains to prove that G is a border basis if D_{2} holds. Let g_{i} − xg_{j} or xg_{i} − yg_{j} be the Spolynomial corresponding to a neighbor syzygy. The above calculation shows that g_{ℓ} −x g_{k} ⟶^{G} 0 or x g_{k} −y g_{j} ⟶^{G} 0 respectively implies the commutativity of the formal multiplication matrices, and therefore that G is an O-border basis. ⊓ ⊔

Condition D_{2} can be rephrased as follows:

a) For all next-door neighbors b_{ℓ} = x b_{k}, there are constant coefficients c_{1} …, c_{ν} ∈ K such that g_{ℓ} − x g_{k} = ∑_{j=1}^{ν} c_{j} g_{j}.

b) For all across-the-street neighbors x b_{k} − y b_{j}, there are constant coefficients d_{1} …, d_{ν} ∈ K such that x g_{k} − y g_{j} = ∑_{j=1}^{ν} d_{j} g_{j}.

This is the special generation condition restricted to all neighbor combinations. By the preceding Buchberger criterion and the characterization of border bases via special generation, this implies the special generation of all polynomials in the ideal.

5 Border Syzygies

In this section we study the syzygy module

Syz_{P} (b_{1}, …, b_{ν}) = {(f_{,} …, f_{ν}) ∈ P^{ν} | f_{1}b_{1} + ⋯ + f_{ν}b_{ν} = 0}.

Its elements are called border syzygies.

As preliminary work, we consider the neighboring structure of the border ∂O. Let ∼ denote the equivalence relation generated by the neighbor relation. The following proposition states that ∂O is connected in the sense that there is only one equivalence class with respect to ∼.

Proposition 19 For any two border terms b_{i}, b_{j} ∈ ∂O, there is a finite sequence b_{k_{0}}, b_{k_{1}}, …, b_{k_{s}} of border terms from b_{i} = b_{k_{0}} to b_{j} = b_{k_{s}} such that b_{k_{ℓ−1}}, b_{k_{ℓ}} are neighbors for ℓ = 1, …, s.

Proof. Let b_{i}, b_{j} ∈ ∂O and g = gcd(b_{i}, b_{j}). Then we have b_{i} = x_{i_{1}}^{α_{1}} ⋯ x_{i_{p}}^{α_{p}} g and b_{j} = x_{j_{1}}^{β_{1}} ⋯ x_{j_{q}}^{β_{q}} g with α_{k}, β_{ℓ} ∈ ℕ_{+} and {i_{1}, …, i_{p}} ∩ {j_{1}, …, j_{q}} = ∅. We use induction on α_{1} + ⋯ + α_{p} + β_{1} + … + β_{q}. If β_{1} + … + β_{q} = 0, i.e. if g = b_{j}, then

b_{i} = b_{k_{0}} = x_{i_{1}}^{α_{1}} ⋯ x_{i_{p}}^{α_{p}} g = b_{i}, x_{i_{1}}^{α_{1}} ⋯ x_{i_{p}}^{α_{p}−1} g, …, x_{i_{1}}^{α_{1}} ⋯ x_{i_{p−1}}^{α_{p−1}} g,
x_{i_{1}}^{α_{1}} ⋯ x_{i_{p−1}}^{α_{p−1}−1} g, …, x_{i_{1}} g, g = b_{k_{s}} = b_{j}

is a sequence of border terms, since \overline{∂O} and O are order ideals. By construction, any two consecutive terms in this sequence are next-door neighbors. Symmetrically, the case α_{1} + … + α_{p} = 0 is proved.

Now assume that α_{1} + … + α_{p}, β_{1} + … + β_{q} > 0. Then x_{j_{1}} | b_{j}, say b_{j} = x_{j_{1}}t with t ∈ 𝕋^{n}. Since \overline{∂O} is an order ideal, we have t ∈ \overline{∂O}. We finish the proof by considering three cases.

Case 1: If t ∈ ∂O, then t is a next-door neighbor of b_{j} and t ∼ b_{i} by induction hypothesis. Thus we have b_{i} ∼ b_{j} in this case.

Case 2: If t ∈ O and x_{i_{1}} t ∈ ∂O, then x_{i_{1}} t is an across-the-street neighbor of b_{j}. Since gcd(x_{i_{1}} t, b_{i}) = x_{i} g, we have x_{i_{1}} t ∼ b_{i} by induction hypothesis. Hence we obtain b_{i} ∼ x_{i_{1}} t ∼ x_{j_{1}} t = b_{j}.

Case 3: If t ∈ O and x_{i_{1}} t ∈ O, then x_{j_{1}}x_{i_{1}} t = x_{i_{1}}b_{j} ∈ ∂O is a next-door neighbor of b_{j}. Since gcd(x_{i_{1}}b_{j}, b_{i}) = x_{i_{1}} g, we have x_{i_{1}}b_{j} ∼ b_{i} by induction hypothesis. Hence we obtain b_{i} ∼ x_{i_{1}}b_{j} ∼ b_{j}. ⊓ ⊔

Let {e_{1}, …, e_{ν}} be the canonical basis of the free module P^{ν}. The fundamental syzygies σ_{ij} = (lcm(b_{i}, b_{j})/b_{i}) e_{i} − (lcm(b_{i}, b_{j})/b_{j}) e_{j} generate the border syzygy module Syz_{P} (b_{1}, …, b_{ν}) (see, for instance, [4, Theorem 2.3.7.b]). We are going to show that there exists a much more efficient set of generators for this syzygy module.

Definition 20 Let O be an order ideal with border ∂O = {b_{1}, …, b_{ν}}.

a) For two next-door neighbors b_{i}, b_{j}, i.e. for b_{i} = x_{k}b_{j}, the fundamental syzygy σ_{ij} has the form τ_{ij} = e_{i} − x_{k}e_{j} and is called a next-door neighbor syzygy.

b) For two across-the-street neighbors b_{i}, b_{j}, i.e. for x_{k}b_{i} = x_{ℓ}b_{j}, the fundamental syzygy σ_{ij} has the form υ_{ij} = x_{k}e_{i} − x_{ℓ}e_{j} and is called an across-the-street neighbor syzygy.

c) The set of all neighbor syzygies is the set of all next-door or across-the street neighbor syzygies.

Proposition 21 The set of all neighbor syzygies generates Syz_{P} (b_{1}, …, b_{ν}).

Proof. Since the module Syz_{P} (b_{1}, …, b_{ν}) is generated by the set of fundamental syzygies {σ_{ij} | 1 ≤ i < j ≤ ν}, it suffices to show that every fundamental syzygy is a P -linear combination of neighbor syzygies. For notational convenience we let σ_{ji} = −σ_{ij} for 1 ≤ i < j ≤ n. Let b_{k_{0}}, …, b_{k_{s}} be a sequence of border terms constructed in the proof of Proposition 19, i.e. such that b_{k_{0}} = b_{i}, b_{k_{s}} = b_{j} and b_{k_{ℓ−1}}, b_{k_{ℓ}} are neighbors for ℓ = 1, …, s. We claim that there are terms f_{1}, …, f_{s} ∈ 𝕋^{n} such that σ_{ij} = ∑_{ℓ=1}^{s} f_{ℓ}φ_{ℓ}, where φ_{ℓ} is the neighbor syzygy between b_{k_{ℓ−1}} and b_{k_{ℓ}}.

To prove this claim, we proceed by induction on s. For s = 1, the terms b_{i} and b_{j} are neighbors and σ_{ij} is the corresponding neighbor syzygy. For s > 1, let b_{i} = x_{i_{1}}^{α_{1}} ⋯ x_{i_{p}}^{α_{p}} · gcd(b_{i}, b_{j}) and b_{j} = x_{j_{1}}^{β_{1}} ⋯ x_{j_{q}}^{β_{q}} · gcd(b_{i}, b_{j}) as in the proof of Proposition 19. If q = 0, i.e. if b_{i} = x_{i_{1}}^{α_{1}} ⋯ x_{i_{p}}^{α_{p}} · b_{j}, then b_{i} = b_{k_{0}} = x_{i_{p}}b_{k_{1}} and therefore σ_{ij} − t_{ij}τ_{k_{0}k_{1}} = t_{ij}x_{i_{p}}e_{k_{1}} − t_{ji}e_{k_{s}} = x_{i_{p}}σk_{1}k_{s} is a syzygy of b_{k_{1}} and b_{k_{s}}. The claim follows by induction. If q ≥ 1, we write b_{j} = x_{j_{1}} t with t ∈ 𝕋^{n} and check the same three cases as in the proof of Proposition 19.

Case 1: If t ∈ ∂O, then b_{k_{s−1}} = t and τ_{k_{s}k_{s−1}} = e_{k_{s}} − x_{j_{1}}e_{k_{s−1}} is a next-door neighbor syzygy. Thus σ_{ij} + t_{ji}τ_{k_{s}k_{s−1}} = t_{ij}e_{k_{0}} − t_{ji}x_{j_{1}}e_{k_{s−1}} = x_{j_{1}}σ_{k_{0}k_{s−1}} is a syzygy of b_{k_{0}} and b_{k_{s−1}} . The claim follows by induction.

Case 2: If t ∈ O and b_{k_{s−1}} = x_{i_{1}} t ∈ ∂O, then x_{i_{1}}b_{k_{s}} = x_{i_{1}}x_{j_{1}} t = x_{j_{1}}b_{k_{s−1}} and υ_{k_{s}k_{s−1}} = x_{i_{1}}e_{k_{s}} − x_{j_{1}}e_{k_{s−1}} is an across-the-street neighbor syzygy. Since t_{k_{s}k_{0}} = lcm(b_{k_{s}}, b_{k_{0}})/b_{k_{s}} = x_{i_{1}}^{α_{1}} ⋯ x_{i_{p}}^{α_{p}}, and since x_{i_{1}} | b_{k_{s−1}} implies α_{i_{1}} ≥ 1, we have a factorization t_{k_{s}k_{0}} = x_{i_{1}} · t′ with t′ ∈ 𝕋^{n}. Then σ_{ij} + t′υ_{k_{s}k_{s−1}} = t_{ij}e_{k_{0}} − t′x_{j_{1}}e_{k_{s−1}} = x_{j_{1}}σ_{k_{0}k_{s−1}} is a syzygy of b_{k_{0}} and b_{k_{s−1}} . The claim follows by induction.

Case 3: If x_{i_{1}} t ∈ O and b_{k_{s−1}} = x_{i_{1}}b_{j} ∈ ∂O, then τ_{k_{s−1}k_{s}} = e_{k_{s−1}} − x_{i_{1}}e_{k_{s}} is a next-door neighbor syzygy. Again we write t_{k_{s}k_{0}} = x_{i_{1}}t′ with t′ ∈ 𝕋^{n} and compute σ_{ij} − t′ τ_{k_{s−1}k_{s}} = t_{ij}e_{k_{0}} − t′e_{k_{s−1}} = σ_{k_{0}k_{s−1}} . Again, the claim follows by induction. ⊓ ⊔

Notice that neighbor syzygies are particularly simple: They are binomials, and their coefficients are either the constants ±1 or indeterminates. Now we apply our knowledge of border syzygies to characterize border bases via the lifting of syzygies; this corresponds to [4, Proposition 2.3.12]. We are especially interested in the syzygy module

Syz(g_{1}, …, g_{ν}) = {(f_{1}, …, f_{ν}) ∈ P^{ν} | f_{1}g_{1} + ⋯ + f_{ν}g_{ν} = 0}

and begin with defining a lifting of a border syzygy.

Definition 22 Let (f_{1}, …, f_{ν}) ∈ Syz_{P} (b_{1}, …, b_{ν}) be a border syzygy. A syzygy (F_{1}, …, F_{ν}) ∈ Syz_{P} (g_{1}, …, g_{ν}) is a lifting of (f_{1}, …, f_{ν}) if one of the following two cases occurs:

1. ∑_{j=1}^{ν} f_{j}g_{j} = 0 and F_{i} − f_{i} = 0 for all i ∈ {1, …, ν}, or

2. ∑_{j=1}^{ν} f_{j}g_{j} ≠ 0 and for all i ∈ {1, …, ν} such that F_{i} − f_{i} ≠ 0 we have deg(F_{i} − f_{i}) ≤ ind_{O}(∑_{j=1}^{ν} f_{j}g_{j}) − 1.

In the second case the combination ∑_{j}(F_{j} − f_{j})g_{j} cancels ∑_{j} f_{j}g_{j}, and the degree bound insures that there are no internal cancellations in the combination ∑_{j}(F_{j} −f_{j})g_{j} beyond the index of ∑_{j} f_{j}g_{j}. The next example shows that there are liftings and, moreover, that liftings of neighbor syzygies are very easy to compute if G is a border basis.

Example 23 Assume that G is an O-border basis.

a) Given a next-door neighbor syzygy τ_{ij} = e_{i} − x_{k}e_{j}, all terms appearing in g_{i} − x_{k}g_{j} have index ≤ 1. Therefore there exist c_{1}, …, c_{m} ∈ K such that the support of g_{i} − x_{k}g_{j} − ∑_{m=1}^{ν} c_{m}g_{m} is contained in O. Since G is a border basis, it follows that φ_{ij} = e_{i} − x_{k}e_{j} − ∑_{m=1}^{ν} c_{m}e_{m} is a syzygy of (g_{1}, …, g_{ν}). This syzygy lifts τ_{ij}, because g_{i} − x_{k}g_{j} = 0 or deg(c_{m}) = 0 < 1 = ind_{O}(g_{i} − x_{k}g_{j})

b) Given an across-the-street neighbor syzygy υ_{ij} = x_{k}e_{i} − x_{ℓ}e_{j}, the only terms of index two appearing in x_{k}g_{i} − x_{ℓ}g_{j} are x_{k}b_{i} and x_{ℓ}b_{j}. Since these two terms cancel and all other terms have index ≤ 1, there exist d_{1}, …, d_{ν} ∈ K such that the support of x_{k}g_{i} − x_{ℓ}g_{j} − ∑_{m=1}^{ν} d_{m}g_{m} is contained in O. Again the border basis property of G implies that ψ_{ij} = x_{k}e_{i}−x_{ℓ}e_{j}−∑_{m=1}^{ν} d_{m}e_{m} is a syzygy of (g_{1}, …, g_{ν}) which lifts υ_{ij}, because x_{k}g_{i} − x_{ℓ}g_{j} = 0 or deg(d_{m}) = 0 < 1 = ind_{O}(x_{k}g_{i} − x_{ℓ}g_{j}).

Since the index need not be monotone with respect to multiplication by a term, the index of ∑_{j=1}^{ν} f_{j}g_{j} can actually be larger than the index r of the terms in f_{1}b_{1} + ⋯ + f_{ν}b_{ν}. The following example is a case in point.

Example 24 Let O = {1, x, x^{2}} ⊂ 𝕋^{2}. Then ∂O = {y, xy, x^{2}y, x^{3}}. The set G = {g_{1}, g_{2}, g_{3}, g_{4}} where g_{1} = y − x^{2}, g_{2} = xy, g_{3} = x^{2}y, and g_{4} = x^{3} is an O-border basis of I = (g_{1}, g_{2}, g_{3}, g_{4}). We have ind_{O}(fb_{1}) = 1 for f = x^{2} and b_{1} = y, while the polynomial fg_{1} = x^{2}y − x^{4} has O-index two.

The next proposition is the main result of this section. It characterizes border bases via liftings of pure border syzygies.

Proposition 25 (Border Bases and Liftings of Border Syzygies) In the prescribed setting, the set G is an O-border basis of I if and only if one of the following equivalent conditions is satisfied. E_{1}. Every border syzygy lifts to a syzygy of (g_{1}, …, g_{ν}). E_{2}. Every neighbor syzygy lifts to a syzygy of (g_{1}, …, g_{ν}).

Proof. First we show that a border basis satisfies E_{1}. Let (f_{1}, …, f_{ν}) be a border syzygy, and let f = f_{1}g_{1} + ⋯ + f_{ν}g_{ν}. Using the Border Division Algorithm, we compute a representation f = h_{1}g_{1} +⋯+h_{ν}g_{ν} with deg(h_{i}) ≤ ind_{O}(f) − 1. The normal remainder is zero, since f ∈ I and G is a border basis of I. Now (f_{1} − h_{1}, …, f_{ν} − h_{ν}) is a syzygy of (g_{1}, …, g_{ν}) that lifts (f_{1}, …, f_{ν}).

Since E_{1} logically implies E_{2}, it remains to prove that G is a border basis if E_{2} holds true. Given a next-door neighbor syzygy τ_{ij} = e_{i} − x_{k}e_{j}, we have g_{i} − x_{k}g_{j} = 0 or the index of g_{i} − x_{k}g_{j} is one. Therefore any lifting of τ_{ij} has the form τ_{ij} − ∑_{m=1}^{ν} c_{m}e_{m} with c_{m} ∈ K. Given an across-the street neighbor syzygy υ_{ij} = x_{k}e_{i} − x_{ℓ}e_{j}, the polynomial x_{k}g_{i} − x_{ℓ}g_{j} is zero or its index is one. Therefore any lifting of υ_{ij} has the form υ_{ij} − ∑_{m=1}^{ν} c_{m}e_{m} with c_{m} ∈ K. In both cases the S-polynomial has the shape S(g_{i}, g_{j}) = ∑_{m=1}^{ν} c_{m}g_{m}, and the claim follows from the last part of the proof of Proposition 18. ⊓ ⊔

There is an important difference between liftings in border basis and those in Gröbner basis theory: condition E_{1} guarantees liftings for all border syzygies, whereas in Gröbner basis theory we can only lift homogeneous syzygies of leading terms. To examine which kind of border syzygies is the correct analogue of homogeneous syzygies of leading terms, we introduce two particularly nice kinds of border syzygies.

Definition 26 Let O be an order ideal with border ∂O = {b_{1}, …, b_{ν}}, and let k ∈ ℕ.

a) A border syzygy (f_{1}, …, f_{ν}) is called pure of index k if ⋃_{i=1}^{ν} Supp(f_{i}b_{i}) is contained in ∂^{k}O. It is called pure if it is pure of some index.

b) A border syzygy (f_{1}, …, f_{ν}) is called perfect of index k if it is pure of index k and the polynomials f_{i} are homogeneous of degree k − 1.

The following example amplifies the details of this definition.

Example 27

a) The next-door neighbor syzygy τ_{ij} = e_{i} − x_{r}e_{j} is a pure syzygy of index one. We note that τ_{ij} is not perfect of index one, since deg(1) ≠ deg(x_{r}).

b) The across-the-street neighbor syzygy υ_{ij} = x_{r}e_{i}−x_{s}e_{j} looks like a perfect syzygy. It is indeed perfect of index two, if x_{r}b_{i} ∉ ∂O. However, if x_{r}b_{i} ∈ ∂O, then it is not a perfect syzygy: We have ind_{O}(x_{r}b_{i}) = ind_{O}(x_{r}b_{j}) = 1 and deg(x_{r}) = deg(x_{s}) = 1; the index and the degree fail the perfectness condition ind = deg +1.

c) Let O = {1, x, y} with border ∂O = {x^{2}, xy, y^{2}}. Then (y, −x − y, x) is a perfect syzygy of index two. Unlike the analogous situation in Gröbner basis theory, perfect border syzygies can have components with several terms in their support.

Since neighbor syzygies are pure, a border prebasis G is an O-border basis of I if and only if the following condition is satisfied:

E_{3}. Every pure border syzygy lifts to a syzygy of (g_{1}, …, g_{ν}).

Pure border syzygies play a role analogous to homogeneous syzygies of the tuple of leading terms in Gröbner basis theory.

Remark 28 Every syzygy s = (f_{1}, …, f_{ν}) ∈ Syz_{P} (b_{1}, …, b_{ν}) decomposes into pure syzygies, s = ∑_{r≥1} s_{r}, where s_{r} collects all terms in the support of s such that the corresponding summand in f_{1}b_{1} + ⋯ + f_{ν}b_{ν} has index r. Since P = ⨁_{i≥0}(⨁_{{t|ind_{O}(t)=i}} K · t), the tuples s_{r} are again syzygies of (b_{1}, …, b_{ν}). Therefore, the characterization of border bases via liftings restricts to pure syzygies.

Can we restrict our characterization via liftings to the even simpler perfect syzygies? If G is a border bases, then E_{1} implies that every perfect border syzygy possesses a lifting in Syz_{P} (g_{1}, …, g_{ν}). However, the converse is not true in general, as our next example shows.

Example 29 Let O = {1, x} ⊂ 𝕋^{2}. Then ∂O = {y, xy, x^{2}}, and every perfect border syzygy f_{1}y + f_{2}xy + f_{3}x^{2} = 0 is of the form (f_{1}, f_{2}, f_{3}) = (0, fx, −fy) with a homogeneous polynomial f ∈ K[x, y]. The O-border prebasis G = {g_{1}, g_{2}, g_{3}} with g_{1} = y − 1, g_{2} = xy, and g_{3} = x^{2}, is not a border basis, because x = g_{2} − xg_{1} ∈ I. However, every perfect border syzygy (0, fx, −fy) is its own lifting.

In Example 23 we lifted every next-door neighbor syzygy τ_{ij} to φ_{ij} and every across-the-street neighbor syzygy υ_{ij} to ψ_{ij}.

Conjecture. The liftings φ_{ij}, ψ_{ij} of the neighbor syzygies generate the syzygy module Syz_{P} (g_{1}, …, g_{ν}) of a border basis G = {g_{1}, …, g_{ν}}.

This conjecture is motivated by the analogy with [4, Proposition 3.1.4] and supported by several examples that we computed with CoCoA. As a further indication, we show that the liftings φ_{ij}, ψ_{ij} generate at least the following special syzygies of (g_{1}, …, g_{ν}).

Proposition 30 Let G = {g_{1}, …, g_{ν}} be an O-border basis. Every syzygy (f_{1}, …, f_{ν}) ∈ Syz_{P} (g_{1}, …, g_{ν}) such that f_{1}b_{1} + ⋯ + f_{ν}b_{ν} = 0 is contained in ⟨{φ_{ij} | b_{i}, b_{j} next-door neighbors} ∪ {ψ_{ij} | b_{i}, b_{j} across-the-street neighbors}⟩.

Proof. Since (f_{1}, …, f_{ν}) is a border syzygy, there exist polynomials h_{ij}, k_{ij} ∈ P such that (f_{1}, …, f_{ν}) = ∑_{i,j} h_{ij}τ_{ij} + ∑_{i,j} k_{ij}υ_{ij} where the sums range over all i, j such that b_{i}, b_{j} are next-door or across-the-street neighbors, respectively and such that each unordered pair of neighbors appears only once. For these indices, we write φ_{ij} = τ_{ij} − ∑_{m=1}^{ν} c_{m}^{(i,j)}e_{m} and ψ_{ij} = υ_{ij} − ∑_{m=1}^{ν} d_{m}^{(i,j)}e_{m} with c_{m}^{(i,j)}, d_{m}^{(i,j)} ∈ K. Then we calculate

0 = f_{1}g_{1} + ⋯ + f_{ν}g_{ν} = ∑_{i,j} h_{ij}τ_{ij}(g_{1}, …, g_{ν}) + ∑_{i,j} k_{ij}υ_{ij}(g_{1}, …, g_{ν})
= ∑_{i,j} h_{ij}(φ_{ij} + ∑_{m=1}^{ν}c_{m}^{(i,j)}e_{m})(g_{1}, …, g_{ν}) + ∑_{i,j} k_{ij}(ψ_{ij} + ∑_{m=1}^{ν}d_{m}^{(i,j)}e_{m})(g_{1}, …, g_{ν})
= ∑_{m=1}^{ν}(∑_{i,j} c_{m}^{(i,j)} + ∑_{i,j} d_{m}^{(i,j)}) g_{m}.

In the last step the other summands disappear, because they involve the liftings φ_{ij} and ψ_{ij}, i.e. syzygies of (g_{1}, …, g_{ν}). Since {g_{1}, …, g_{ν}} is K -linearly independent, we get ∑_{i,j} c_{m}^{(i,j)} + ∑_{i,j} d_{m}^{(i,j)} = 0 for every m ∈ {1, …, ν}, and, therefore,

(f_{1}, …, f_{ν}) = ∑_{i,j} h_{ij}(φ_{ij} + ∑_{m=1}^{ν} c_{m}^{(i,j)}e_{m}) + ∑_{i,j} k_{ij}(ψ_{ij} + ∑_{i,j} d_{m}^{(i,j)}e_{m})
= ∑_{i,j} h_{ij}φ_{ij} + ∑_{i,j} k_{ij}ψ_{ij}

is contained in the module generated by the syzgyies φ_{ij}, ψ_{ij}. ⊓ ⊔ References

[1] W. Auzinger and H.J. Stetter, An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations, in: R.G. Agarwal (ed.), Int. Conf. on Numerical Mathematics, Singapore 1988, Birkhäuser ISNM 86, Basel 1988, pp. 11–30.

[2] M. Caboara and L. Robbiano, Families of estimable terms, in: B. Mourrain (ed.), Symbolic and Algebraic Computation, Proc. Conf. ISSAC, London (Ontario) 2001, ACM Press, New York 2001, pp. 56–63.

[3] A. Kehrein, M. Kreuzer, and L. Robbiano, An algebraist’s view on border bases, in: I. Emiris and A. Dickenstein (eds.), Proc. CIMPA School 2003, Springer, Heidelberg 2004 (to appear).

[4] M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1, Springer, Heidelberg 2000.

[5] H.M. Möller, Systems of algebraic equations solved by means of endomorphisms, in: G. Cohen et al. (eds.), Applied algebra, algebraic algorithms and error-correcting codes, Proc. Conf. AAECC-10, LNCS 673, Springer, Heidelberg 1993, pp. 43–46.

[6] B. Mourrain, A new criterion for normal form algorithms, in: M. Fossorier, H. Imai, S. Lin, A. Poli (eds.), Proc. Conf. AAECC-13, Honolulu 1999, LNCS 1719, Springer, Heidelberg 1999, pp. 440–443.

[7] H.J. Stetter, Numerical polynomial algebra, SIAM 2004 (to appear).