Computing Border Bases

Achim Kehrein and Martin Kreuzer

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

Abstract

This paper presents several algorithms that compute border bases of a zero-dimen-sional ideal. The first relates to the FGLM algorithm as it uses a linear basis transformation. In particular, it is able to compute border bases that do not contain a reduced Gröbner basis. The second algorithm is based on a generic algorithm by Bernard Mourrain originally designed for computing an ideal basis that need not be a border basis. Our fully detailed algorithm computes a border basis of a zerodimensional ideal from a given set of generators. To obtain concrete instructions we appeal to a degree-compatible term ordering σ and hence compute a border basis that contains the reduced σ-Gröbner basis. We show an example in which this computation actually has advantages over Buchberger’s algorithm. Moreover, we formulate and prove two optimizations of the Border Basis Algorithm which reduce the dimensions of the linear algebra subproblems.

Key words: border basis, Gröbner basis, FGLM algorithm, Buchberger’s algorithm

1 Introduction

Border bases play a key role in numerical polynomial algebra because they behave numerically better than Gröbner bases (see Stetter’s book [11]). Auzinger and Stetter [1], Möller [9], and Mourrain [10] successfully used border bases to solve zero-dimensional polynomial systems of equations. In previous papers (see [7] and [6]) Robbiano and the authors laid a foundation for the algebraic theory of border bases. Here we address the question of how to compute a border basis of a zero-dimensional polynomial ideal I from a given set of generators.

  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 3 June 2005

The most straightforward idea is to compute a Gröbner basis and then to perform a base change in the spirit of the well-known FGLM technique (see [3]). To compare this algorithm to other approaches, we spell it out in Section 2. This easy method is able to compute the border basis of I with respect to any order ideal for which a border basis exists. Its drawback is that it involves a Gröbner basis computation which can be quite time consuming.

Then we move on to a technique inspired by Faugère’s algorithms F_{4} and F_{5} (see [4] and [5]). A general framework for this technique was given by Mourrain in [10]. The idea is to enlarge the given set of generators by repeatedly applying all possible linear syzygies while simultaneously keeping the computation in a finite-dimensional vector subspace of the polynomial ring. This computational universe is enlarged only when necessary. Mourrain’s generic algorithm applies this idea in a more general setting than we do: his sets of monomials connected to 1 are not necessarily order ideals, and the generators it produces are not necessarily a border basis. The price for this generality is that it is difficult to make the choices involved in the algorithm explicit, and that it is uncertain whether the resulting type of generating sets satisfies the wonderful characterizations of border bases explained in [6]. Moreover, from the numerical point of view, according to [11, Example 2.21], “the computational use of such bases [not involving order ideals] is awkward”.

In Section 4 we formulate and prove an algorithm which yields a concrete construction of an order ideal O and an O-border basis of I. We buy its explicit nature at the expense of introducing a term ordering. Thus the resulting border basis will contain a reduced Gröbner basis and we have lost some of the flexibility border bases offer. On the other hand, in many cases our algorithm behaves better than Buchberger’s algorithm does. We owe this to the simplicity of the Buchberger Criterion for border bases (see Proposition 4): in contrast to Gröbner bases, only neighboring pairs need to be considered and thus the degree of the border adapted S-polynomials stays comparatively small. The entire computation takes place in a degree bounded part of the polynomial ring and the algorithm never has to reduce S-polynomials of a degree much larger than the maximal degree of a border term. Another advantage is that the computation requires only K -linear reductions. And if a border basis with respect to some other order ideal is required, we can still follow the algorithm with the FGLM technique explained before.

Finally, in Section 5, we present improved versions of our border basis algorithm. These versions minimize the enlargements of the computational universe. Thereby we keep the size of the necessary linear algebra operations as small as possible. The resulting algorithm has been implemented in CoCoA and performs well in concrete examples.

2 Definitions and Basic Algorithm

In the following we adopt the notation from [7]. So, we work in the polynomial ring P = K[x_{1}, …, x_{n}] over a field K. The monoid of terms is 𝕋^{n} := {x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} | α_{1}, …, α_{n} ∈ ℕ} and, for every d ∈ ℕ, we let 𝕋_{≤d}^{n} denote the set of terms with total degree at most d.

Definition 1 A set of terms O ⊆ 𝕋^{n} is called an order ideal if it is closed under divisors, i.e. if t ∈ O and t′ | t imply t′ ∈ O. The border of a nonempty order ideal O is the set of terms ∂O = {x_{i} t | 1 ≤ i ≤ n, t ∈ O} \ O; for the empty order ideal, we define ∂∅ := {1}.

The concept of an order ideal appears under many different names in the literature. We use “order ideal” in agreement with [2] and [12]. In the present paper, order ideals and consequently their borders consist of only finitely many terms. Unlass stated otherwise, we write O = {t_{1} …, t_{μ}} and ∂O = {b_{1} …, b_{ν}}. (For μ = 0, this includes the case O = ∅.) Moreover, we shall reserve calligraphic symbols for finite sets of polynomials.

Definition 2 Let O = {t_{1}, …, t_{μ}} be an order ideal with border ∂O = {b_{1}, …, b_{ν}}. Let G = {g_{1} …, g_{ν}} ⊂ P be a set of polynomials and let I ⊆ P be an ideal.

(1) The set G is an O-border prebasis if the polynomials have the form

g_{j} = b_{j} − ∑_{i=1}^{μ} α_{ij}t_{i} for 1 ≤ j ≤ ν and α_{ij} ∈ K.

(2) An O-border prebasis G is an O-border basis of I if G generates I and if P = I ⊕ ⟨O⟩_{K} as vector spaces. If there exists an O-border basis of I, we say that the order ideal O supports a border basis of I.

Four remarks are in order. First, it is sometimes convenient to express the direct sum condition “P = I ⊕ ⟨O⟩_{K} ” in the the equivalent form “the residue classes of the terms in O constitute a vector basis of P/I.” Second, the condition ⟨G⟩_{P} = I follows already from the mere inclusion G ⊆ I in combination with the direct sum condition. This is shown in [7] and is analoguous to Gröbner basis theory [8, Proposition 2.4.3a]. Third, since the order ideal is stipulated to consist of only finitely many, namely μ terms, the border basis definition implies dim_{K}(P/I) = μ. Thus the ideal I is necessarily zerodimensional. Fourth, for each order ideal there is at most one border basis {g_{1}, …, g_{ν}} of I because of the unique decomposition b_{j} = g_{j} ⊕ ∑_{i=1}^{μ} α_{ij}t_{i} for each 1 ≤ j ≤ ν.

In the termination proof of the Border Basis Algorithm below we require the following notions and result.

Definition 3 Let G = {g_{1}, …, g_{ν}} be an O-border prebasis as in Definition 2. Two prebasis polynomials g_{k}, g_{ℓ} are neighbors if their border terms are related according to x_{i}b_{k} = x_{j}b_{ℓ} or x_{i}b_{k} = b_{ℓ} for some indeterminates x_{i}, x_{j}. Then, the corresponding S-polynomials are

S(g_{k}, g_{ℓ}) := x_{i}g_{k} − x_{j}g_{ℓ} and S(g_{k}, g_{ℓ}) := x_{i}g_{k} − g_{ℓ}

respectively.

Proposition 4 (Buchberger Criterion for Border Bases) An O-border prebasis G = {g_{1} …, g_{ν}} is an O-border basis of an ideal I if and only if G ⊂ I and, for each pair of neighboring prebasis polynomials, there are constant coefficients c_{j} ∈ K such that

S(g_{k}, g_{ℓ}) = c_{1}g_{1} + … + c_{ν}g_{ν}.

The proof and a detailed discussion of these notions are included in [6].

It is helpful to understand the relationship between border bases and reduced Gröbner bases. So let us take a closer look at it. The Gröbner basis approach uses a term ordering σ and the set of leading terms LT_{σ}{I} = {LT_{σ}(f) | f ∈ I \ {0}}. The complementary set of terms O_{σ}{I} := 𝕋^{n} \ LT_{σ}{I} is an order ideal. Hence order ideals appear naturally in Gröbner basis theory.

Let O_{σ}{I} = {s_{1}, …, s_{μ}}. By Macaulay’s Basis Theorem the residue classes {s̄_{1}, …, s̄_{μ}} form a vector basis of P/I; equivalently, we have the direct sum decomposition P = I ⊕ ⟨O_{σ}{I}⟩_{K}. Now let {ℓ_{1}, …, ℓ_{λ}} ⊂ LT_{σ}{I} be the set of leading terms that are minimal in the sense that ℓ_{l} ∈ LT_{σ}{I} while all proper divisors are in O_{σ}{I} = 𝕋^{n} \ LT_{σ}{I}. The direct sum decomposition provides for each ℓ_{l} a unique polynomial h_{l} and unique coefficients β_{il} ∈ K with ℓ_{l} = h_{l}+∑_{i} β_{il}s_{i} and this yields the reduced σ-Gröbner basis {h_{1}, …, h_{λ}} of I. In the same way we obtain the O_{σ}{I}-border basis {g_{1}, …, g_{ν}} from the decompositions b_{j} = g_{j} + ∑_{i} α_{ij}s_{i} for each border term in {b_{1}, …, b_{ν}} = ∂(O_{σ}{I}). Due to the minimal property, we have ℓ_{1}, …, ℓ_{λ} ∈ ∂(O_{σ}{I}), and the uniqueness of the decompositions implies {h_{1}, …, h_{λ}} ⊆ {g_{1} …, g_{ν}}. In this sense the O_{σ}{I}-border basis of an ideal extends its reduced σ-Gröbner basis.

These observations motivate the following straightforward algorithm.

Proposition 5 (Basis Transformation Algorithm) Let I ⊆ P be a zero-dimensional ideal and O = {t_{1}, …, t_{μ}} an order ideal.

The following algorithm checks whether O supports a border basis of I and, in the affirmative, computes the O-border basis {g_{1}, …, g_{ν}} of I.

(T1) Choose a term ordering σ and compute O_{σ}{I} := 𝕋^{n} \ LT_{σ}{I}. (T2) If |O_{σ}{I}| ≠ μ then return “O has the wrong cardinality to support a

border basis of I ” and stop. (T3) Let O_{σ}{I} = {s_{1}, …, s_{μ}}. For 1 ≤ m ≤ μ, compute the coefficients τ_{im} ∈

K of the normal form NF_{σ,I}(t_{m}) = ∑_{i=1}^{μ} τ_{im}s_{i}. Let T be the matrix (τ_{im})_{1≤i,m≤μ}.

(T4) If det T = 0 then return “O has the wrong form to support a border basis

of I ” and stop. (T5) Let ∂O = {b_{1}, …, b_{ν}}. For 1 ≤ j ≤ ν, compute the coefficients β_{ij} ∈ K

of NF_{σ,I}(b_{j}) = ∑_{i=1}^{μ} β_{ij}s_{i}. Let B be the matrix (β_{ij})_{1≤i≤μ,1≤j≤ν}. (T6) Compute (α_{ij}) = T^{−1}B. Return g_{j} := b_{j} − ∑_{i=1}^{μ} α_{ij}t_{i} for 1 ≤ j ≤ ν.

Proof. By Macaulay’s basis theorem, |O_{σ}{I}| = dim_{K} P/I. Step (T2) checks whether O has the correct number of terms to represent a vector basis of P/I. Step (T3) calculates the expansions of the vectors t̄_{i} with respect to the vector basis Ō_{σ}(I) = {s̄_{1}, …, s̄_{μ}} of P/I:

t̄_{i} = τ_{1i}s̄_{1} + … + τ_{μi}s̄_{μ} for 1 ≤ i ≤ μ.

In matrix notation, ( t̄_{1} … t̄_{μ}) = ( s̄_{1} … s̄_{μ}) T . Therefore, Ō is a vector basis of P/I, if and only if T is invertible. Finally, the computation

b̄_{j} = ( s̄_{1} … s̄_{μ}) ( β_{1j} ; ⋮ ; β_{μj} ) = ( t̄_{1} … t̄_{μ}) T^{−1} ( β_{1j} ; ⋮ ; β_{μj} )

in P/I implies that steps (T5) and (T6) produce the correct result. ⊓ ⊔

The following example serves several purposes. First, it provides a particular instance of the preceding algorithm. Secondly, it demonstrates that not every order ideal of the correct cardinality supports a border basis. Thirdly, it presents a border basis that is not an O_{σ}{I}-border basis. In other words, there are border bases that are not extensions of reduced Gröbner bases.

Example 6 This example appeared in a different context in [7]. Let I be the vanishing ideal of the five points (−1, 1), (1, 1), (0, 0), (1, 0), and (0, −1) in 𝔸^{2}(ℚ). Let σ := DegRevLex. Then O_{σ}{I} = {1, x, y, xy, y^{2}} and hence dim_{ℚ} ℚ[x, y]/I = 5. The bivariate set of terms 𝕋^{2} contains seven order ideals with five elements, namely O_{1} = {1, x, x^{2}, x^{3}, x^{4}}, O_{2} = {1, x, x^{2}, x^{3}, y}, O_{3} = {1, x, y, y^{2}, y^{3}}, O_{4} = {1, y, y^{2}, y^{3}, y^{4}} O_{5} = {1, x, x^{2}, y, xy}, O_{6} = {1, x, y, xy, y^{2}}, and O_{7} = {1, y, y^{2}, x, x^{2}}. Applying the Basis Transformation Algorithm to all seven order ideals respectively, we obtain three classes of results:

The order ideals O_{1}, O_{2}, O_{3}, and O_{4} have the wrong form to support a border basis of I and, accordingly, the algorithm terminates in step (T4). (This can also be seen as follows: the vanishing ideal I contains x^{3} − x and y^{3} − y, so ⟨O_{i}⟩_{K} ∩ I ≠ 0 for i = 1, 2, 3, 4.)

Next, O_{5} and O_{6} support border bases of I. The former consists of h_{1} := x^{3}−x, h_{2} := x^{2}y−x^{2}−xy+x, h_{3} := y^{2}−2x^{2}−2xy+2x+y, and h_{4} := xy^{2}−xy; the latter comprises k_{1} := x^{2} +xy − \frac{1}{2}y^{2} −x− \frac{1}{2}y, k_{2} := xy^{2} −xy, k_{3} := y^{3} −y, and k_{4} := x^{2}y − \frac{1}{2}y^{2} − \frac{1}{2}y. Both order ideals are of the form O_{σ}\{I\}, for instance, with respect to lexicographical term orderings with y < x and x < y respectively. The first three polynomials constitute the reduced Gröbner basis respectively.

Finally, the calculation for O_{7} produces the border basis g_{1} := xy − \frac{1}{2}y − \frac{1}{2}y^{2} − x + x^{2}, g_{2} := xy^{2} − \frac{1}{2}y − \frac{1}{2}y^{2} − x + x^{2}, g_{3} := x^{3} − x, g_{4} := y^{3} − y, and g_{5} := x^{2}y − \frac{1}{2}y − \frac{1}{2}y^{2} Note that this border basis consists of five polynomials in contrast to the two previous examples. Most importantly, this order ideal cannot be the complement of any LT_{σ}{I}: the leading term of g_{1} with respect to an arbitrary term ordering is x^{2} or y^{2}; in either case, LT_{σ}{I} ∩ O_{7} ≠ ∅.

The Basis Transformation Algorithm is similar to the well-known FGLM Algorithm [3]: both compute an ideal basis from a known Gröbner basis via a vector basis transformation. However, there is a fundamental difference. While the FGLM Algorithm uses a σ-Gröbner basis of I to compute O_{τ}{I} term by term with respect to some new term ordering τ, the Basis Transformation Algorithm requires the complete order ideal O as input.

The Basis Transformation Algorithm is unsatisfactory since it significantly uses Gröbner basis calculations. In section 4 we present an algorithm that uses linear algebra instead. It is an adaptation of the algorithm by Mourrain described in the next section.

3 Mourrain’s Generic Algorithm

Mourrain [10] proposed a generic algorithm for computing a more general concept than that of a border basis. For the reader’s convenience, we list briefly the parts of his work that are pertinent to our approach. We slightly rephrase some material to prepare the ground for our adaptation.

Definition 7 Let V and W be vector subspaces of P and let v_{0} ∈ V .

(1) Let W^{+} := W + x_{1}W + … + x_{n}W.

(2) Inductively define the vector subspaces

V_{0} := ⟨v_{0}⟩_{K} and V_{k+1} := V_{k}^{+} ∩ V for k = 0, 1, 2, …

Then V is connected to v_{0} if the ascending chain V_{0} ⊆ V_{1} ⊆ V_{2} ⊆ … converges to V in the sense ⋃_{k≥0} V_{k} = V .

When V is generated by a set of terms we also say that the set of terms is connected to v_{0}. The set of terms {1, x, xy} is connected to 1, but not an order ideal. In Mourrain’s algorithm, sets of terms connected to 1 play the role that order ideals play in border basis theory. For easy reference, we introduce the following name.

Definition 8 Let I ⊆ P be an ideal and B ⊆ P be a vector subspace. We call B a Mourrain base space for I if it is connected to 1 and if P = B ⊕I as vector spaces.

Proposition 9 (Mourrain’s Generic Algorithm) Let F := {f_{1}, …, f_{s}} ⊂ P be a set of polynomials that generates a zerodimensional ideal I = ⟨F⟩_{P}. The following algorithm computes a Mourrain base space B for I.

(M1) Determine a finite-dimensional vector subspace L ⊆ P that is connected

to 1 and contains f_{1}, …, f_{s}. (M2) Let K_{0} be the vector subspace ⟨f_{1} …, f_{s}⟩_{K}. Let ℓ = 0. (M3) Compute K_{ℓ+1} := K_{ℓ}^{+} ∩ L. (M4) If K_{ℓ+1} ≠ K_{ℓ} then increase ℓ by 1 and go to step M3. (M5) Compute a vector subspace B connected to 1 such that L = B ⊕ K_{ℓ}. (M6) If B^{+} ⊈ L then replace L with L^{+} and go to step 3. Otherwise return

B and stop.

Mourrain [10] remarks on step M5 , “since L is connected to 1, the vector space B connected to 1 and supplementary to K_{∗} [= K_{ℓ} in step M5] can be computed incrementally, starting from 1 (in the case where 1 ∉ K_{∗}).” However, he does not specify how this computation should be effected. We are unaware of an example whose result is a set of terms connected to 1 but not an order ideal. The problem of making step M5 explicit is the starting point for the development of the border basis algorithm in the next section.

4 The Border Basis Algorithm

The K -linear span ⟨O⟩_{K} of an order ideal O is connected to 1. Thus Mourrain’s framework relates to the border basis setting. Indeed, in this section we present an adaptation of Mourrain’s algorithm to border bases. To do so, we serve the algorithm in easily digestible pieces. We begin with distilling a fundamental concept from Mourrain’s generic algorithm.

Definition 10 Let F ⊆ L be vector subspaces of P. We think of L as the universe in which our calculations are taking place. Define inductively the vector subspaces

F_{0} := F and F_{k+1} := F_{k}^{+} ∩ L for k = 0, 1, 2, …

The union F_{L} := ⋃_{k≥0} F_{k} of the ascending chain F_{0} ⊆ F_{1} ⊆ F_{2} ⊆ … is called the L-stable span of F. In particular, if F := {f_{1}, …, f_{s}} is a set of polynomials spanning F = ⟨F⟩_{K}, then we also write F_{L} instead of F_{L}.

This definition is motivated by the special case L = P in which the P -stable span equals the ideal generated by F, i.e. F_{P} = ⟨f_{1}, …, f_{r}⟩_{P}. But of course, to keep things computable, we prefer finite-dimensional universes L. Let us collect some basic properties of stable spans that will come in handy later.

Lemma 11 Let F ⊆ G ⊆ U ⊆ L be vector subspaces of P. Then the following relations hold.

F ⊆ F_{L} , F_{L} = (F_{L})_{L} , F_{L} ⊆ G_{L} , F_{U} ⊆ F_{L} , and F_{L} = (F_{U})_{L}.

Proof. The first two relations are immediate consequences of the stable span’s definition. Next, let F_{0} := F and F_{k+1} := F_{k}^{+} ∩ L for k ∈ ℕ. Analogously define G_{k} for k ∈ ℕ. From F ⊆ G and F_{k+1} = F_{k}^{+} ∩ L ⊆ G_{k}^{+} ∩ L = G_{k+1} we deduce inductively F_{k} ⊆ G_{k} for all k. Hence F_{L} = ⋃_{k} F_{k} ⊆ ⋃_{k} G_{k} = G_{L} which proves the third relation. The similar proof of the fourth is skipped.

To derive the last relation, apply the third relation to F ⊆ F_{U} to obtain F_{L} ⊆ (F_{U})_{L}. The converse inclusion follows from forming the L-stable spans of both sides of F_{U} ⊆ F_{L}. ⊓ ⊔

The last property shows that the L-stable span can be computed from the U -stable span instead of from scratch.

Our next goal is to describe explicitly how to compute the stable span for the particular universe L = ⟨𝕋_{≤d}^{n}⟩_{K}. This includes the repeatedly occuring subproblem of computing a basis extension for vector spaces ⟨V⟩_{K} ⊆ ⟨V ∪ G⟩_{K} where V is a basis of the smaller space and G comprises the additional generators. For this computation we use Gaussian elimination in the following form.

Lemma 12 Let σ be a term ordering and V = {v_{1}, …, v_{r}} ⊂ P \ {0} a finite set of polynomials with pairwise different leading terms and leading coefficients equal to 1. Let G = {g_{1}, …, g_{s}} ⊂ P be a finite set of polynomials. The following algorithm computes a finite set W ⊂ P with leading coefficients equal to 1 and such that V ∪ W has pairwise different leading terms and ⟨V ∪ W⟩_{K} = ⟨V ∪ G⟩_{K}. (The set V or W may be empty.)

(1) Let H := G and ϱ := 0.

(2) If H = ∅ then return W := {v_{r+1} …, v_{r+ϱ}} and stop.

(3) Choose f ∈ H and remove it from H. Let i := 1.

(4) If f = 0 or i > r + ϱ then go to step 7.

(5) If LT_{σ}(f) = LT_{σ}(v_{i}) then replace f with f − LC_{σ}(f) · v_{i}, reset i := 1 and go to step 4.

(6) Increase i by 1, and go to step 4.

(7) If f ≠ 0 then increase ϱ by 1, and put v_{r+ϱ} := f/ LC_{σ}(f). Continue with step 2.

Proof. The algorithm maintains the following invariant: The leading terms of the polynomials v_{1}, …, v_{r+ϱ} are pairwise different and

⟨{v_{1}, …, v_{r+ϱ}} ∪ {f} ∪ H⟩_{K} = ⟨V ∪ G⟩_{K}. (1)

In the beginning, when f is still undefined, interpret {f} as the empty set.

The loop of steps 4–6 is finite, since in each iteration either i increases or it is reset along with a reduction of the leading term of f. The latter can happen only finitely many times, since σ is a well ordering. Hence after finitely many iterations i is not reset anymore and, eventually, surpasses the unchanged upper bound r + ϱ. The reduction in step 5 does not alter the span in equation (1) and, when the loop terminates, either f = 0 or LT_{σ}(f) ∉ {LT_{σ}(v_{1}) …, LT_{σ}(v_{r+ϱ})}. Also, the loop of steps 2–7 terminates: the set H is initialized as the finite set G and then each iteration removes one element from H while no elements are added. Thus, the whole algorithm terminates.

At termination, H = ∅ and {f} ⊆ {0, v_{r+ϱ}}, so the invariant verifies the algorithm’s correctness. ⊓ ⊔

The reason for using vector bases with pairwise different leading terms is the following: if V = {v_{1}, …, v_{r}} is a basis of a vector subspace V ⊆ P with pairwise different leading terms then the set LT_{σ}{V } := {LT_{σ}(v) | v ∈ V \{0}} of leading terms of elements of V equals the set of leading terms of its basis LT_{σ}{V} := {LT_{σ}(v_{1}), …, LT_{σ}(v_{r})}.

Next, we must make the ^{+}-operation on a vector subspace ⟨F⟩_{K} ⊆ P more explicit. So we abuse notation and also define a ^{+}-operation on a set of polynomials F := {f_{1}, …, f_{r}} by letting F^{+} := F ∪ x_{1}F ∪ … ∪ x_{n}F. Thus we have ⟨F⟩_{K}^{+} = ⟨F^{+}⟩_{K}.

Proposition 13 (Computing a Stable Span) Let F := {f_{1}, …, f_{r}} ⊂ P and L := ⟨𝕋_{≤d}^{n}⟩_{K} with f_{1}, …, f_{r} ∈ L, i.e. such that d ≥ max{deg f_{i} | 1 ≤ i ≤ r}. Let σ be a degree-compatible term ordering. The following algorithm computes a vector basis V of the stable span F_{L}. Moreover, the basis vectors have pairwise different leading terms.

(1) Compute a vector basis V of ⟨F⟩_{K} with pairwise different leading terms. (Apply the lemma to V = ∅ and G := F.)

(2) Compute a basis extension W′ := {v′_{r+1} …, v′_{r+ϱ′}} for ⟨V⟩_{K} ⊆ ⟨V^{+}⟩_{K} so that the elements of V ∪W′ have pairwise different leading terms. (Apply the lemma to V and G := V^{+} \ V.)

(3) Let W := {v_{r+1}, …, v_{r+ϱ}} := {v ∈ W′ | deg(v) ≤ d}.

(4) If ϱ > 0 then replace V with V ∪ W, increase r by ϱ, and go to step 2.

(5) Return V.

Proof. Steps 2–4 maintain the following loop invariant. Each iteration of the loop of steps 2–4 starts with a finite set V with pairwise different leading terms and computes a finite set W such that V ∪ W has pairwise different leading terms and

⟨V⟩_{K} ⊆ ⟨V ∪ W⟩_{K} = ⟨V^{+}⟩_{K} ∩ L ⊆ L.

In particular, V ∪ W is a vector basis of ⟨V^{+}⟩_{K} ∩ L.

By Lemma 12, step 1 computes a finite set V with pairwise different leading terms. So the loop invariant is correctly initialized. By the same lemma, step 2 determines a vector basis extension W′ such that V ∪ W′ is a vector basis of ⟨V⟩_{K}^{+} with pairwise different leading terms. Then step 4 intersects this subspace with L by discarding the polynomials of degree larger than d; here we use the degree-compatibility of L = ⟨𝕋_{≤d}^{n}⟩_{K} and of σ.

Another iteration is called in step 4 if and only if a non-empty basis extension W′ has been computed. Since r increases by a positive ϱ with each new iteration while the upper bound r < dim_{K} L stays constant, this loop terminates. After termination the loop invariant becomes ⟨V⟩_{K} = ⟨V⟩_{K}^{+} ∩ L which proves correctness. ⊓ ⊔ The stable span F_{L} is contained in L as well as in the ideal generated by F, i.e. F_{L} ⊆ L ∩ ⟨F⟩_{P}. The following example shows that this inclusion can be strict and that, in insufficiently large universes, this approximation depends on the set of generators F and not only on the generated ideal ⟨F⟩_{P}.

Example 14 Let F := {f_{1}, f_{2}, f_{3}} with f_{1} := x^{2}y^{2} + 1, f_{2} := x^{4}, and f_{3} := y^{4}. Also, let H := {1}. The sets F and H generate the same trivial ideal ⟨1⟩_{P} because 1 = f_{2} · f_{3} − f_{1}^{2} + 2f_{1}.

(1) Let L := ⟨𝕋_{≤4}^{n}⟩_{K}. Then F_{L} = ⟨F⟩_{K} with dim_{K} F_{L} = 3, while H_{L} = L with dim_{K} H_{L} = 10.

(2) Let L := ⟨𝕋_{≤5}^{n}⟩_{K}. Then F_{L} = L = H_{L}.

The above computation of the stable span also includes information about an order ideal that is a candidate for supporting a border basis.

Proposition 15 Let F := {f_{1}, …, f_{s}} ⊂ P and let L = ⟨𝕋_{≤d}^{n}⟩_{K} such that F ⊆ L. Then there exists an order ideal O such that

L = F_{L} ⊕ ⟨O⟩_{K}.

Namely, if σ is a degree-compatible term ordering and V := {v_{1}, …, v_{r}} a vector basis of F_{L} with pairwise different leading terms then LT_{σ}{F_{L}} is closed under multiples in L, i.e. if t ∈ 𝕋_{≤d}^{n} and LT_{σ}(v) | t for some v ∈ F_{L} then t = LT_{σ}(w) for some w ∈ F_{L}. Dually this states that O = 𝕋_{≤d}^{n} \ {LT_{σ}(v_{1}), …, LT_{σ}(v_{r})} is an order ideal. It also satisfies the above direct sum decomposition.

Proof. The definition of O and Steinitz’s exchange lemma yield

L = ⟨LT_{σ}(v_{1}), … LT_{σ}(v_{r})⟩_{K} ⊕ ⟨O⟩_{K} = ⟨v_{1}, … v_{r}⟩_{K} ⊕ ⟨O⟩_{K} = F_{L} ⊕ ⟨O⟩_{K}.

To prove the order ideal property of O, we show dually that for each term t ∈ 𝕋^{n} \ O and each indeterminate x_{i} the product x_{i} t is in 𝕋^{n} \ O. Since O ⊆ 𝕋_{≤d}^{n}, we only have to consider the case x_{i} t ∈ 𝕋_{≤d}^{n}. As t ∉ O, there is a basis element v ∈ V such that t = LT_{σ}(v). We have x_{i}v ∈ V^{+} ⊆ F_{L}^{+} and, by case consideration, LT_{σ}(x_{i}v) = x_{i}t ∈ 𝕋_{≤d}^{n}. Since σ is degree-compatible, x_{i}v ∈ ⟨𝕋_{≤d}^{n}⟩_{K} = L. Thus, x_{i}v ∈ F_{L}^{+} ∩ L = F_{L}, and therefore LT_{σ}(x_{i}v) ∈ LT_{σ}{F_{L}} = LT_{σ}{V} which shows x_{i}t ∈ 𝕋_{≤d}^{n} \ O. ⊓ ⊔

The next proposition presents the statement that will serve as stop criterion in the Border Basis Algorithm below. It checks whether the candidate order ideal actually supports a border basis. Note how the special case L = P and Ĩ = I resembles the definition of a border basis.

Proposition 16 Let L be a vector subspace of P. Let Ĩ be a vector subspace of a zero-dimensional ideal I ⊆ P such that Ĩ^{+} ∩ L = Ĩ and ⟨Ĩ⟩_{P} = I (In a sense, Ĩ is an L-stable approximation of I). Let O = {t_{1}, …, t_{μ}} be an order ideal such that

L = Ĩ⊕ ⟨O⟩_{K}.

If ∂O ⊆ L then O supports a border basis of I.

Proof. For each border term b_{j} ∈ ∂O ⊆ L the direct sum decomposition defines a polynomial g_{j} ∈ Ĩ according to

b_{j} = g_{j} + ∑_{i=1}^{m} α_{ij}t_{i} ∈ Ĩ⊕ ⟨O⟩_{K}.

By construction, G := {g_{1}, …, g_{ν}} is an O-border prebasis.

Consider two neighboring prebasis polynomials g_{k}, g_{ℓ}. The support of their S-polynomial S(g_{k}, g_{ℓ}) ∈ Ĩ^{+} is contained in O^{+}. Hence there are coefficients c_{j} ∈ K such that h := S(g_{k}, g_{ℓ}) − ∑_{j=1}^{ν} c_{j}g_{j} has its support in O. Then h ∈ Ĩ^{+} ∩ ⟨O⟩_{K} = Ĩ^{+} ∩ L ∩ ⟨O⟩_{K} = Ĩ ∩ ⟨O⟩_{K} = {0}. By the Buchberger Criterion for Border Bases, G is a border basis of ⟨Ĩ⟩_{P} = I. ⊓ ⊔

We have to deal with one more technicality. The following reduction process transforms a suitable set of polynomials into the wanted border basis.

Proposition 17 (Final Reduction Algorithm) Let F = {f_{1}, …, f_{s}} ⊂ P be a system of generators of a zero-dimensional ideal I. Let σ be a degree-compatible term ordering. Let L be an order ideal (e.g. L = 𝕋_{≤d}^{n}), V a vector basis of the span F_{L} with pairwise different leading terms, and let O := L \ LT_{σ}(V) such that

L = F_{L} ⊕ ⟨O⟩_{K}  and  ∂O ⊆ L.

Then the following algorithm computes the O_{σ}{I}-border basis {g_{1}, …, g_{ν}}.

(F1) Let V_{R} := ∅. (F2) If V = ∅ then go to step (F8). (F3) Determine in V the element v with minimal leading term. Remove it

from V. (F4) Let H := Supp(v) \ ({LT_{σ}(v)} ∪ O). (F5) If H = ∅ then append v/ LC_{σ}(v) to V_{R} and go to step (F2). (F6) For each h ∈ H determine w_{h} ∈ V_{R} and c_{h} ∈ K such that LT_{σ}(w) = h

and h ∉ Supp(v − c_{h} · w_{h}). (F7) Replace v with v−∑_{h} c_{h}·w_{h}, append v/ LC_{σ}(v) to V_{R} and go to step (F2). (F8) Let ∂O = {b_{1}, …, b_{ν}}. Determine for each b_{j} ∈ ∂O the polynomial

g_{j} ∈ V_{R} with b_{j} = LT_{σ}(g_{j}). Return g_{1}, …, g_{ν}.

Proof. The hypotheses give a vector basis V of F_{L} so that for each b_{j} ∈ ∂O there is an h_{j} ∈ V with b_{j} = LT_{σ}(h_{j}). We have almost reached our goal, but it is still possible that Supp(h_{j}) contains terms outside {b_{j}} ∪ O. The algorithm reduces these unwanted terms.

The loop of steps (F2)–(F7) maintains the invariant ⟨V ∪ {v} ∪ V_{R}⟩_{K} = F_{L} where the set V ∪ {v} ∪ V_{R} has pairwise different leading terms. (In the beginning, when v is undefined, interpret {v} as the empty set.) Moreover, the elements of V_{R} are polynomials g with Supp(g) ⊆ {LT_{σ}(g)} ∪ O and LC_{σ}(g) = 1. This invariant property holds prior to the first iteration since the first part of the algorithm computed V as a vector basis of F_{L} with pairwise different leading terms and step (F1) defines V_{R} as the empty set. Each iteration removes from V the element v with minimal leading term. Thus, if Supp(v) contains a term outside {LT_{σ}(v)} ∪ O then it is necessarily the leading term of some element in V_{R}: it must be in 𝕋_{≤d}^{n} \ O = LT_{σ}{F_{L}}, which equals LT_{σ}{V ∪ {v} ∪ V_{R}}, while it cannot be in LT_{σ}{{v} ∪ V} by the minimal property of LT_{σ}(v). Hence w and c in step (F6) do exist as stated. The loop of steps (F2)–(F7) is finite since each iteration removes one element from the finite set V. At termination the invariant proves that we have obtained a vector basis V_{R} of F_{L} with pairwise different leading terms and that Supp(g) ⊆ {LT_{σ}(g)} ∪ O for all g ∈ V_{R}.

We have found polynomials g_{j} ∈ V_{R} ⊆ F_{L} ⊆ I with Supp(g_{j}) ⊆ LT_{σ}(g_{j}) ∪ O, with LC_{σ}(g_{j}) = 1, and {LT_{σ}(g_{1}), … LT_{σ}(g_{ν})} = ∂O. By our hypotheses and Proposition 16, the order ideal O supports a border basis. Due to the border basis uniqueness, the computed polynomials g_{1}, …, g_{ν} constitute this O-border basis. ⊓ ⊔

This Final Reduction Algorithm is more subtle than it may appear at first sight. The information contained in V is not limited to having for each border term one polynomial having this term in its support. In trying to get rid of the term ordering, we contemplated the following question.

Let I be a zero-dimensional ideal and O an order ideal that supports a border basis of I. Let ∂O = {b_{1} …, b_{ν}} and v_{1}, …, v_{ν} ∈ I be polynomials with b_{j} ∈ Supp(v_{j}) for all 1 ≤ j ≤ ν. Can there be an algorithm that computes the O-border basis {g_{1} …, g_{ν}} of I?

The answer is negative. For example, consider the monomial ideal I := ⟨x^{2}, y⟩_{P} in P := K[x, y]. The order ideal O = {1, x} supports the border basis {y, xy, x^{2}} and I contains the polynomials y, xy, x^{2} + x^{3}. Clearly, there is no way to obtain the basis polynomial x^{2} via reductions using only the given polynomials.

Finally, we are ready to assemble the main algorithm.

Proposition 18 (Border Basis Algorithm)

Let F = {f_{1}, …, f_{s}} ⊂ P be a set of polynomials that generates a zerodimensional ideal I = ⟨F⟩_{P}. Let σ be a degree-compatible term ordering. The following algorithm computes the O_{σ}{I}-border basis {g_{1}, …, g_{ν}}.

(B1) Let d := max{deg(f_{i}) | 1 ≤ i ≤ s} and L := ⟨𝕋_{≤d}^{n}⟩_{K}. (B2) Compute a vector space basis V = {v_{1}, …, v_{r}} of ⟨F⟩_{K} with pairwise

different leading terms. (B3) Compute a basis extension W′ := {v′_{r+1}, …, v′_{r+ϱ′}} for ⟨V⟩_{K} ⊆ ⟨V^{+}⟩_{K} so

that the elements of V ∪ W′ have pairwise different leading terms. (B4) Let W = {v_{r+1}, …, v_{r+ϱ}} = {v ∈ W′ | deg(v) ≤ d}. (B5) If ϱ > 0 then replace V with V ∪W, increase r by ϱ, and go to step (B3). (B6) Let O := 𝕋_{≤d}^{n} \ {LT_{σ}(v_{1}) … LT_{σ}(v_{r})}. (B7) If ∂O ⊈ L then increase d by one, update L := ⟨𝕋_{≤d}^{n}⟩_{K}, and continue

with step (B3). (B8) Apply the Final Reduction Algorithm and return the polynomials g_{1}, …, g_{ν}

it computes.

Proof. Step (B1) initializes L so that F ⊆ L. By Proposition 13, steps (B2)– (B5) compute a vector basis V of the stable span F_{L} with pairwise different leading terms. By Proposition 15, step (B6) defines an order ideal.

Now consider the loop of steps (B3)–(B7). Each new iteration starts with the updated universe L := ⟨𝕋_{≤d}^{n}⟩_{K} and a vector basis Ṽ := V with pairwise different leading terms of the stable span F_{U} with respect to the preceding universe U := ⟨𝕋_{≤d−1}^{n}⟩_{K}. Applying Proposition 13 to the set of polynomials Ṽ, we see that steps (B3)–(B5) compute a vector basis V of the stable span Ṽ_{L}, and Lemma 11 gives Ṽ_{L} = (F_{U})_{L} = F_{L}. Therefore each iteration ends with an updated vector basis V of F_{L} and an updated order ideal O such that L = F_{L} ⊕ ⟨O⟩_{K}. Next we check that only finitely many iterations occur. Though the order ideal O_{σ}{I} and the border basis polynomials g_{j} have not been computed yet, they do exist. In particular, ∂(O_{σ}{I}) = {LT_{σ}(g_{1}), … LT_{σ}(g_{ν})}, and there are polynomials h_{j1},… h_{js} such that

g_{j} = h_{j1}f_{1} + … + h_{js}f_{s} for 1 ≤ j ≤ ν. (2)

Let d̃:= max({d}∪{deg(h_{ji}f_{i}) | 1 ≤ i ≤ s, 1 ≤ j ≤ ν}). It suffices to consider the case that the loop has not terminated prior to reaching the iteration with parameter value d = d̃. This iteration uses the universe L = ⟨𝕋_{≤d̃}^{n}⟩_{K} and computes a vector basis V of F_{L} with pairwise different leading terms. By the choice of d̃, all summands h_{ji}f_{i} in the expansions (2) are in L and hence g_{1}, …, g_{ν} ∈ F_{L}. We have ∂(O_{σ}{I}) = {LT_{σ}(g_{1}), … LT_{σ}(g_{ν})} ⊆ LT_{σ}{F_{L}}. Since LT_{σ}{F_{L}} is closed under multiples in L (Proposition 15), we deduce 𝕋_{≤d̃}^{n} \ O_{σ}{I} ⊆ LT_{σ}{F_{L}}. Therefore, O_{σ}{I} contains the order ideal O := 𝕋_{≤d̃}^{n} \ LT_{σ}{F_{L}} which is determined by the current iteration. This leads to ∂O ⊆ O_{σ}{I} ∪ ∂(O_{σ}{I}) ⊆ L and the loop terminates.

Having reached step (B8), we have a vector basis V of F_{L} that satisfies all hypotheses of Proposition 17. Hence the Final Reduction Algorithm computes the O-border basis. Above we showed O ⊆ O_{σ}{I}. Both order ideals support border bases of I; in particular, they must consist of the same finite number of terms and therefore coincide. ⊓ ⊔

The O_{σ}{I}-border basis computed by the algorithm is an extension of the reduced σ-Gröbner basis. Hence we better show an example in which this algorithm performs better than Buchberger’s algorithm.

Example 19 We consider the zero-dimensional ideal I generated by F := \{f_{1}, …, f_{5}\} where f_{1} = x^{3} − x, f_{2} = y^{3} − y, f_{3} = x^{2}y − \frac{1}{2}y − \frac{1}{2}y^{2}, f_{4} = xy −x− \frac{1}{2}y +x^{2} − \frac{1}{2}y^{2}, and f_{5} = xy^{2} −x− \frac{1}{2}y +x^{2} − \frac{1}{2}y^{2}; this is the O_{7}-border basis in Example 6. Let σ be the degree-lexicographic term ordering DegLex on 𝕋^{2}. First we compute the O_{σ}{I}-border basis according to the steps of the above Border Basis Algorithm.

(B1) The generators induce the universe L := ⟨𝕋_{≤3}^{2}⟩_{ℚ}. (B2) The set of generators is a vector basis of ⟨F⟩_{ℚ} with pairwise different

leading terms, hence (rewritten with respect to DegLex) V = {x^{3} − x, y^{3} − y, x^{2}y − \frac{1}{2}y^{2} − \frac{1}{2}y, x^{2} + xy − \frac{1}{2}y^{2} − x − \frac{1}{2}y, xy^{2} + x^{2} − \frac{1}{2}y^{2} − x − \frac{1}{2}y\}.

(B3) We obtain V^{+} = \{x^{4} −x^{2}, x^{3}y −xy, xy^{3} −xy, y^{4} −y^{2}, x^{3}y − \frac{1}{2}xy^{2} − \frac{1}{2}xy, x^{2}y^{2} − \frac{1}{2}y^{3} − \frac{1}{2}y^{2}, x^{3} + x^{2}y − \frac{1}{2}xy^{2} − x^{2} − \frac{1}{2}xy, x^{2}y + xy^{2} − \frac{1}{2}y^{3} − x − \frac{1}{2}y^{2}, x^{2}y^{2}+x^{2}− \frac{1}{2}xy^{2}−x^{2}− \frac{1}{2}xy, xy^{3}+x^{2}y− \frac{1}{2}y^{3}−xy− \frac{1}{2}y^{2}\}. A basis extension with pairwise different leading terms is W′ = {x^{4}−x^{2}, x^{3}y−xy, xy^{3}−xy, y^{4} − y^{2}, x^{2}y^{2} − \frac{1}{2}y^{3} − \frac{1}{2}y^{2}\}.

(B4) W = W′ ∩ L = ∅. (B6) The algorithm computes the order ideal O = {1, x, y, y^{2}, xy} with border

∂O = {x^{2}, xy^{2}, x^{2}y, y^{3}} which is contained in the universe. (B8) Let V_{R} := ∅. The Final Reduction Algorithm processes the elements

of V in the order v = x^{2} + xy − \frac{1}{2}y^{2} − x − \frac{1}{2}y (H = ∅), v = y^{3} − y (H = ∅), v = xy^{2} + x^{2} − \frac{1}{2}y^{2} − x − \frac{1}{2}y (H = \{x^{2}\}; replace v with v − 1 · (x^{2} + xy − \frac{1}{2}y^{2} − x − \frac{1}{2}y), thus v = xy^{2} − xy.), v = x^{2}y − \frac{1}{2}y^{2} − \frac{1}{2}y (H = ∅), and v = x^{3} − x (H = ∅). Eventually, the border basis {x^{2} + xy − \frac{1}{2}y^{2} − x − \frac{1}{2}y, y^{3} − y, xy^{2} − xy, x^{2}y − \frac{1}{2}y^{2} − \frac{1}{2}y\} is returned.

On the other hand, the Buchberger algorithm computes the S-polynomials S_{12} = −x^{6}+x^{3}y^{3}+x^{4}−xy^{3}, S_{13} = −x^{4}+x^{3}y+x^{2}−xy, S_{14} = −x^{4}+x^{3}+x^{2}−x, S_{15} = −x^{5} + x^{3}y^{2} + x^{3} − xy^{2}, S_{23} = x^{2}y^{3} − y^{5} − x^{2}y + y^{3}, S_{24} = −y^{6} + x^{2}y^{3} + y^{4} − x^{2}y, S_{25} = xy^{3} − y^{4} − xy + y^{2}, S_{34} = −x^{2}y^{2} + x^{2}y + \frac{1}{2}y^{3} − \frac{1}{2}y, S_{35} = −x^{3}y+x^{2}y^{2}+ \frac{1}{2}xy^{2}− \frac{1}{2}y^{3}+ \frac{1}{2}xy− \frac{1}{2}y^{2}, S_{45} = x^{2}y^{2}+xy^{3}− \frac{1}{2}y^{4}−x^{3}−x^{2}y− \frac{1}{2}xy^{2}− \frac{1}{2}y^{3} + x^{2} + \frac{1}{2}xy. The pairs of generators (f_{1}, f_{2}) and (f_{2}, f_{4}) have relatively prime leading terms; we let the Buchberger algorithm justifiably disregard them. All S-polynomials reduce to zero, hence the system of generators is already a Gröbner basis.

How do these calculations differ? The border basis computation requires only the terms up to degree 3. In the Buchberger computation the nine additional terms x^{5}, x^{3}y^{2}, x^{2}y^{3}, y^{5}, x^{4}, x^{3}y, x^{2}y^{2}, xy^{3}, y^{4} appear (This list excludes the terms x^{6}, x^{3}y^{3}, and y^{6} that appear in the S-polynomials whose generators have relatively prime leading terms). So, this calculation produces terms up to degree 5 which subsequently need to be reduced. Thus, even in this small example we observe a redundancy in the Buchberger algorithm that is avoided by the border basis algorithm.

Let us compute another, more complicated example.

Example 20 This time we consider the vanishing ideal of the points (−1, 0, 0), (0, 0, 0), (1, 0, 0), (3, 0, 0), (5, 0, 0), (4, 4, 4), and (0, 0, 7) in 𝔸^{3}(ℚ). It is generated by the set of polynomials {z^{2} + 3y − 7z, yz − 4y, xz − 4y, y^{2} − 4y, xy − 4y, x^{5} − 8x^{4} + 14x^{3} + 8x^{2} − 15x + 15y}. Let σ := DegRevLex. The Border Basis Algorithm starts with the universe ⟨𝕋_{≤5}^{3}⟩_{K} which consists of 56 terms. To compute the stable span, the algorithm performs four linear basis extensions. Then it obtains the order ideal O = {1, x, x^{2}, x^{3}, x^{4}, y, z} whose border is already contained in the universe. The universe need not be enlarged. The border basis is the set of 12 polynomials {z^{2} +3y −7z, yz −4y, xz − 4y, y^{2} − 4y, xy − 4y, x^{2}z − 16y, x^{2}y − 16y, x^{3}z − 64y, x^{3}y − 64y, x^{4}z − 256y, x^{4}y − 256y, x^{5} − 8x^{4} + 14x^{3} + 8x^{2} − 15x + 15y}.

The Buchberger Algorithm applied to this example works with S-polynomials up to degree 6 (There are S-polynomials of degree 7, but they belong to pairs of polynomials with relatively prime leading terms). The difference is not particularly striking here, but it is still there.

5 Some Optimizations of the Border Basis Algorithm

The following improved version of the Border Basis Algorithm replaces the use of 𝕋_{≤d}^{n} as a computational universe with order ideals which are kept as small as possible.

Proposition 21 (Improved Border Basis Algorithm) Let F = {f_{1}, …, f_{s}} ⊂ P be polynomials that generate a zero-dimensional ideal I := ⟨F⟩_{P}. Let σ be a degree-compatible term ordering. The following algorithm computes the O_{σ}{I}-border basis {g_{1} …, g_{ν}}.

(I1) Let L be the order ideal spanned by ⋃_{i=1}^{r} Supp(f_{i}). (I2) Compute a vector basis V of ⟨F⟩_{K} with pairwise different leading terms. (I3) Compute a basis extension W′ for ⟨V⟩_{K} ⊆ ⟨V^{+}⟩_{K} so that the elements

of V ∪ W′ have pairwise different leading terms. (I4) Let W := {w ∈ W′ | LT_{σ}(w) ∈ L}. (I5) If ⋃_{w∈W} Supp(w) ⊈ L then replace L with the order ideal spanned by L

and ⋃_{w∈W} Supp(w) and continue with step (I4). (I6) If W ≠ ∅ then replace V with V ∪ W and continue with step (I3). (I7) Let O := L \ {LT_{σ}(v) | v ∈ V}. (I8) If ∂O ⊈ L then replace L with the order ideal L^{+} and continue with

step (I3). (I9) Apply the Final Reduction Algorithm and return the polynomials g_{1}, …, g_{ν}

computed by it.

Proof. To show that the procedure terminates and that the algorithm is correct, we consider its loops in order of their appearance. The subloop of steps (I4)–(I5) is finite because W ⊆ W′ implies that each instance of L is contained in the invariant order ideal spanned by ∪_{v∈V∪W′} Supp(v). Since each new iteration corresponds to an enlargement of L inside this invariant finite set, there can be only finitely many iterations.

When this subloop terminates, we have ⟨V ∪ W⟩_{K} = ⟨V ∪ W′⟩_{K} ∩ ⟨L⟩_{K}. The left-hand side is contained in the right-hand side because the universe enlargements in (I5) insure that the premise w ∈ W, i.e. LT_{σ}(w) ∈ L, implies Supp(w) ⊆ L. For the reverse inclusion, let v = α_{1}v_{1} + … + α_{r}v_{r} + β_{1}w_{1} + … + β_{s}w_{s} be in ⟨L⟩_{k}, where α_{1}, …, α_{r}, β_{1}, …, β_{s} ∈ K \ {0}, v_{1}, …, v_{r} ∈ V, and w_{1}, …, w_{s} ∈ W′. The vectors are assumed to be pairwise different. We need to show that w_{1}, …, w_{s} ∈ W. Since the leading terms of V ∪ W′ are pairwise different, LT_{σ}(v) equals some LT_{σ}(v_{i}) or some LT_{σ}(w_{j}). We know Supp(v_{i}) ⊆ L; hence, in the former case, we obtain v−α_{i}v_{i} ∈ ⟨V∪W′⟩_{K}∩⟨L⟩_{K}. In the latter case, we deduce from LT_{σ}(w_{j}) = LT_{σ}(v) ∈ L that w_{j} ∈ W. We get v − β_{j}w_{j} ∈ ⟨V ∪ W′⟩_{K} ∩ ⟨L⟩_{K}. The desired inclusion follows by induction.

Next we show that the loop of steps (I3)-(I6) is finite. At the beginning of an arbitrary iteration let L be contained in some 𝕋_{≤d}^{n}. Then the subset selection criterion LT_{σ}(w) ∈ L and σ being degree-compatible yield Supp(w) ⊆ 𝕋_{≤d}^{n}. Thus, for L ⊆ 𝕋_{≤d}^{n} at the beginning of the first iteration, all linear basis extensions take place in the finite-dimensional space ⟨𝕋_{≤d}^{n}⟩_{K}.

At termination of this loop, we have ⟨V⟩_{K} = ⟨V⟩_{K}^{+} ∩⟨L⟩_{K} due to the following identities. The basis extension in step (I3) gives ⟨V ∪ W′⟩_{K} = ⟨V⟩_{K}^{+} . Since we passed the subloop (I4)–(I5), we have ⟨V ∪ W⟩_{K} = ⟨V ∪ W′⟩_{K} ∩ ⟨L⟩_{K}.

Finally, when exiting the subloop in step (I6), we have W = ∅ and hence ⟨V⟩_{K} = ⟨V ∪ W⟩_{K}.

Now, we show that the definition of O in step (I9) produces an order ideal. Analogously to the proof of Proposition 15 let t ∈ L\O and consider the case x_{i} t ∈ L. Since t ∉ O there is a v ∈ V with t = LT_{σ}(v). We have x_{i} v ∈ V^{+} and by case consideration LT_{σ}(x_{i}v) = x_{i}t ∈ L, i.e. x_{i}v ∈ V∪W. Having passed the subloop (I4)–(I5), we infer Supp(x_{i}v) ⊆ L. Thus x_{i}v ∈ ⟨V⟩_{K}^{+} ∩ ⟨L⟩_{K}. By the argument in the preceding paragraph this intersection equals ⟨V⟩_{K}. As the leading terms of V are pairwise different, LT_{σ}(x_{i}v) ∈ LT_{σ}{V}. This shows x_{i} t ∈ L \ O.

The loop of steps (I3)–(I8) terminates because, with each call of a new iteration in step (I8), the universe L becomes strictly larger. Unless the loop has terminated before, eventually the universe becomes sufficiently large to contain the polynomials (2) as in the proof of the original Border Basis Algorithm. By the same argument as there, the loop terminates.

This covers all changes in the algorithm. ⊓ ⊔

The following example shows what kind of improvement can be expected.

Example 22 For comparison we apply the Improved Border Basis Algorithm to the set of generators stated in Example 20. The algorithm starts with the universe {1, z, z^{2}, y, yz, x, xz, y^{2}, xy, x^{2}, x^{3}, x^{4}, x^{5}} consisting of 13 terms. The first basis extension produces a nonempty W′, but the restriction to elements with leading term in the universe leads to W = ∅ and to the order ideal O = {1, z, y, x, x^{2}, x^{3}, x^{4}}. The border ∂O is not contained in the universe and hence we enlarge the universe. From now on we are working in a universe with 29 terms. Next, four linear basis extensions are computed and we obtain again the order ideal O as above. Of course, this time its border is contained in the universe and the border basis is computed.

So, instead of computing four linear basis extensions and the final reduction in a 56-dimensional space (cf. Example 20), the Improved Border Basis Algorithm computes one extension in a 13-dimensional space as well as four extensions and the final reduction in a 29-dimensional space.

We can do even better. In step (I8) of the Improved Border Basis Algorithm we enlarge the universe L more than is required to fit in ∂O.

Corollary 23 Let N be a positive integer. Replace step (I8) in the Improved Border Basis Algorithm with (I8’) If ∂O ⊈ L then replace L with the order ideal spanned by L and ∂O;

every N th time this is done, replace L with L^{+} instead. Continue with step (I3).

The instructions (I1)–(I7), (I8’), (I9) form an algorithm that computes a border basis g_{1}, …, g_{ν}.

We included the L^{+} replacement every N th time as a safeguard. In that way the above termination argument also applies to the loop (I3)–(I8’). Without this there is a theoretical chance that the modified procedure may run in an infinite loop: potentially, universe enlargements to accomodate ∂O may always act in the x-direction while the wanted reduction information is along the ydirection. This problematic behaviour is avoided in the Improved Border Basis Algorithm, since the enlargement L^{+} lets the universe grow in all directions. However, we have not met this problematic behaviour in any of the examples computed and we strongly believe that the use of (I8’) without the safeguard does not produce termination problems. In other words, our N is huge.

Using this primed version of the Improved Border Basis Algorithm we compute the preceding example once more. Of course, we start with the same universe of 13 terms as before and compute one linear basis extension that leads to W = ∅. Now, the enlargement leads to a universe with only 19 terms, in which four linear basis extensions are computed until the border basis is found.

References

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

[2] W. Bruns, J. Herzog. Cohen-Macaulay Rings, Cambridge University Press, Cambridge 1993.

[3] J.C. Faugère, P. Gianni, D. Lazard, T. Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering, Journal of Symbolic Computation 16 (1993), pp. 329-344.

[4] J.C. Faugère. A new efficient algorithm for computing Gröbner bases (F_{4}), Journal of Pure and Applied Algebra 139 (1999), pp. 61–88.

[5] J.C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F_{5}), in: T. Mora (ed.), Proc. Conf. ISSAC 2002, ACM Press, New York 2002, pp. 75–83.

[6] A. Kehrein, M. Kreuzer. Characterizations of border bases, Journal of Pure and Applied Algebra 196 (2005), pp. 251–270.

[7] A. Kehrein, M. Kreuzer, L. Robbiano. An algebraist’s view on border bases, in: I. Emiris and A. Dickenstein (eds.). Solving Polynomial Equations, Alg. and Comp. in Math. 14, Springer, Heidelberg 2005, pp. 169-202.

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

[9] 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.

[10] 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.

[11] H. J. Stetter. Numerical polynomial algebra, SIAM, Philadelphia 2004.

[12] B. Sturmfels. Gröbner Bases and Convex Polytopes, AMS, University Lecture series 8, Providence R.I. 1996.