On Triangular Decompositions of Algebraic Varieties

M. Moreno Maza^{1}

Computational Mathematics Group, NAG Ltd, Oxford OX2 8DR, Great-Britain

Abstract

Different kinds of triangular decompositions of algebraic varieties are presented. The main result is an efficient method for obtaining them. Our strategy is based on a lifting theorem for polynomial computations modulo regular chains.

Introduction

Triangular decompositions are one of the major tools for solving polynomial systems. For systems of algebraic equations, they provide a convenient way to describe complex solutions and a step towards decompositions into irreducible components. Combined with other techniques, they are used for these purposes by several computer algebra systems such as AXIOM [JS92] or SINGULAR [GPS98]. For systems of partial differential equations, they provide the only practicable way for determining a symbolic solution. Moreover, triangulation methods for the algebraic case apply since Rosenfeld’s Lemma [Ros59] reduces a differential problem to an algebraic one [BLOP95,BL00,Hub00].

Triangular Decompositions were introduced by Ritt [Rit32] for solving systems of partial differential equations. They rely on the concept of a characteristic set of a polynomial ideal, which is a set with a triangular shape and no more elements than variables. Ritt’s decompositions involved only characteristic sets of prime ideals [Rit50]. In this case, they have good properties and Theorem 3.2 in [ALM99] shows that a characteristic set of a prime ideal is no harder to compute than a lexicographical Gröbner basis. We refer also to the work of Mishra [Mis93] for the complexity of characteristic set computations and the work of Szántó [Szá99] for the complexity of triangular decompositions.

Following the work of Ritt, Wu [Wu86] provided an algorithm for solving systems of algebraic equations by means of characteristic sets of not necessarily

1 Mail to moreno@lifl.fr or marc@nag.co.uk

NAG Technical Report TR 4/99. Accepted at the MEGA-2000. 22 June 2000

prime ideals. Wu’s method appears to be efficient for geometric problems where degenerate solutions are not interesting, but his decompositions may contain inconsistent, and thus redundant, components. See [AM99] for more details about the redundancies in triangular decompositions.

The consistency problem was solved by Kalkbrener [Kal91] who considered particular characteristic sets, called regular chains. Theorem 6.1 in [ALM99] show that the good properties of characteristic sets of prime ideals generalize to regular chains. Kalkbrener gave also an algorithm for computing an unmixed-dimensional decomposition V_{1} ∪ ⋯ ∪ V_{m} of an algebraic variety V, where each V_{i} is given by a regular chain, representing the generic points of the irreducible components of V_{i}. However Kalkbrener’s decompositions may contain redundant components and may not contain the points of V that are not generic [AM99].

The redundancy problem was solved by Lazard [Laz91] who strengthened the notion of a regular chain. Without giving a correctness proof, he also proposed a new method to obtain Wu-like decompositions where all the points, generic or not, are represented. Following Seidenberg [Sei56] another approach was given by Wang [Wan93]. By associating a set of inequations to every characteristic set, Wang’s method avoids redundant components but this technique makes the output sometimes hard to read. By considering special triangular systems, called simple systems, this last point has been improved by Wang in [Wan98]. Simple systems are closely related to Lazard regular chains and Dellière [Del99] showed that simple systems could be used to describe the triangular systems involved in Dynamic Evaluation [Góm94].

The four methods of Wu, Lazard, Wang and Kalkbrener are compared from an experimental point of view in [AM99]. It appears that the methods based on regular chains perform better than the others, and among them Kalkbrener’s method have better timings. However Kalkbrener’s decompositions may contain redundant components and are not convenient for algebraic varieties of positive dimension where all the points, generic or not, are needed. It appears also that the construction of Lazard regular chains may be expensive in positive dimension. Finally it appears that the four methods generate many redundant intermediate components. Therefore the challenge of providing an efficient algorithm for controlling the intermediate computations and for computing triangular decompositions in the sense of Lazard remained.

The algorithm presented in this paper decomposes the variety V by means of regular chains. All the zeros of V, generic or not, are represented. The components are produced in order of decreasing dimension allowing good control of the redundant intermediate components. Moreover, we show how our algorithm can produce Kalkbrener’s decompositions or Lazard’s regular chains.

A preliminary implementation (which does not contain most of the improvements given in this paper) is distributed with version 2.2 of AXIOM and experiments are reported in [AM99]. They show that this implementation is comparable in performances with that of Kalkbrener, although our method provides a complete decomposition of V. Moreover we obtain much better results than with our implementation of Lazard’s method.

Our decomposition strategy is based on a procedure called decompose that computes the intersection of a hypersurface with a quasi-component (the set of the generic points associated with a regular chain). More precisely, this operation computes the quasi-components with maximal dimension contained in this intersection, and the necessary information in order to obtain those of lower dimension when they are needed. A top-level procedure manages the calls to the procedure decompose such that the output quasi-components are produced in order of decreasing dimension and such that the redundant quasi-components are removed as soon as possible, by means of an inclusion test. The procedure decompose itself relies on a procedure for polynomial gcd computations modulo regular chains that produces a main result and a way to terminate some degenerated computations when they are needed.

This strategy leads to the following difficulty. Since we proceed in order of decreasing dimension, we cannot use a top-down elimination process (eliminating the greatest variables first) as in Wang’s algorithm or a bottom-up construction as in Kalkbrener’s algorithm. In fact, we need to perform projections into some subspace and then reconstructions in the whole space where the algebraic variety V is to be decomposed. Lazard’s algorithm has to face the same difficulty but solves it with the strong properties of Lazard regular chains. General regular chains do not have these properties, this leads us to establish a lifting theorem for polynomial computations modulo regular chains. The paper is organized as follows.

Section 1. For the reader’s convenience we review the concept of a regular

chain. Section 2. We give some fundamental properties of regular chains. They may

be deduced from most text books in commutative algebra. For the reader’s convenience we give direct proofs, because we have not found any reference where they are explicit.

Section 3. We introduce the notions needed for the description of our decomposition process in order of decreasing dimension. Our lifting theorem concludes this section.

Section 4. We assume that we are given an operation for computing polynomial gcds modulo regular chains and an operation for testing the regularity of a polynomial w.r.t. a regular chain. Then we state and prove our algorithm decompose for computing the quasi-components of maximal dimension in the intersection of a hypersurface and a quasi-component.

Section 5. We show that the assumptions of the previous sections hold and we prove that the whole decomposition process terminates and is correct. Our arguments rely only on the properties of regular chains given in [ALM99] and the basic properties of prime ideals [SZ67].

Section 6. We give several improvements of the algorithms of the previous sections. We show how to obtain Kalkbrener’s decomposition by means of our method. Lazard regular chains have two additional properties w.r.t. general regular chains: we show to obtain them with our method. Then we discuss the problem of deciding whether a quasi-component is contained in another. This question is crucial for removing the redundant intermediate quasi-components during our decomposition process, and thus in order to produce decompositions in the sense of Lazard. Finally we explain how our decomposition process must be conducted in order to remove the redundant intermediate quasi-components at an early stage.

1 Notations and Basic Definitions

We review in this section the notions related to triangular sets and regular chains. See [Aub99,ALM99,Mor97] for more details. We shall use some notions from Commutative Algebra (such as the dimension of an ideal) and refer for instance to [SZ67] for this subject.

Let k be a field and let x_{1} < x_{2} < ⋯ < x_{n} be n ordered variables. For every i = 1 ⋯ n we define P_{i} = k[x_{1}, …, x_{i}] and we put P_{0} = k. Let q ∈ P_{n} be a non-constant polynomial i.e. q ∉ k. The leading coefficient and the degree of p regarded as univariate polynomial in the variable x_{i} will be denoted by lc(p, x_{i}) and deg(p, x_{i}) respectively. The greatest variable occurring in q is called the main variable of q and it is denoted by mvar(q). The degree, the leading coefficient, the (monic) leading monomial, the leading term, and the reductum of q regarded as a univariate polynomial in mvar(q) are called the main degree, the initial, the rank, the head and the tail of q; they are denoted by mdeg(q), init(q), rank(q), head(q) and tail(q) respectively. Hence we have q = head(q) + tail(q) and head(q) = init(q) rank(q). We call the separant of q the derivative of q w.r.t. mvar(q). For p ∈ P_{n} we denote by prem(p, q) and pquo(p, q) the pseudo-remainder and the pseudo-quotient of p by q as univariate polynomials in mvar(q). We say that p is smaller than q and we write p≺q if either p ∈ k and q ∉ k or both are non-constant polynomials such that either mvar(p) < mvar(q) or mvar(p) = mvar(q) and mdeg(p) < mdeg(q). We write p ∼ q if neither p ≺ q nor q ≺ p hold.

Let I be an ideal of P_{n}. We denote by Ass(I) the set of the prime ideals associated with I and by \sqrt{I} the radical of I. We denote by I : p^{∞} the saturated ideal of I w.r.t. p, that is the set of the polynomials q such that there exists an integer m ≥ 0 such that p^{m}q ∈ I. Let K be an algebraic closure of k and let F be a subset of P_{n}. We denote by I(F) the ideal generated by F in P_{n} and by V(F) the affine variety associated with F in K^{n}. If F = ∅ we define V(F) = K^{n}. If F consists of a single element f, then f will also denote the set F when no confusion is possible. For any W ⊆ K^{n} we denote by \overline{W} the Zariski closure of W w.r.t. k.

A subset T of P_{n} is called a triangular set if T ∩ k is empty and if for every t ∈ T and every t′ ∈ T such that t ≠ t′ we have mvar(t) ≠ mvar(t′). A variable x_{i} is algebraic w.r.t. T if there exists t ∈ T such that x_{i} = mvar(t). We denote by alg(T) the set of the algebraic variables of T. For x_{i} ∈ alg(T) we denote by T_{x_{i}} the polynomial in T whose main variable is x_{i}. We denote by T_{x_{i}}^{−} and T_{x_{i}}^{+} the sets of polynomials t ∈ T such that mvar(t) < x_{i} and mvar(t) > x_{i} respectively. We say that T is purely algebraic if for every variable v occuring in T there exists t ∈ T such that v = mvar(t). The pseudo-remainder of p w.r.t. T is denoted by prem(p, T).

A point ζ ∈ V(T) is called a regular zero of T if for every t ∈ T the initial of t does not vanish at ζ. The set of the regular zeros of T is denoted by W(T). We denote by Z(F, T) the intersection of W(T) and V(F).

Let i be in the range 0 ⋯ n. Assume T ∩ P_{i} ≠ ∅. We denote by sat_{i}(T) the ideal I(T ∩ P_{i}) : h_{i}^{∞} of P_{i} where h_{i} is the product of the initials of T ∩ P_{i}. If T ∩ P_{i} = ∅ we define sat_{i}(T) = {0}. The saturated ideal of T is the ideal of P_{n} denoted by Sat(T) and defined by Sat(T) = sat_{n}(T). We denote by dim(T) the dimension of the ideal Sat(T). For any triangular set T we have:

\overline{W(T)} = V(Sat(T)). (1)

Moreover if W(T) ≠ ∅ then for every i = 0 ⋯ n we have:

Ass(Sat(T) ∩ P_{i}) = {P ∩ P_{i} | P ∈ Ass(Sat(T))}. (2)

We introduce here the reduced form of the polynomial p w.r.t. the ideal I as the polynomial denoted by red(p, I) and defined as follows. If p ∈ I then red(p, I) = 0, otherwise if p ∈ k then red(p, I) = p, otherwise if head(p) ∈ I then red(p, I) = red(tail(p), I), otherwise red(p, I) = red(init(p), I) rank(p)+ red(tail(p), I). It is important to observe that p and red(p, I) are equal modulo I. We shall use red(p, T) as a short hand for red(p, Sat(T)).

Let us denote by rank(T) the set of the rank(t) for t ∈ T. Let S be a second triangular set. We say that T has smaller rank than S and we write T ≺ S if there exists v ∈ alg(T) such that rank( T_{v}^{−}) = rank( S_{v}^{−}) and either v ∉ alg(S) or v ∈ alg(S) and T_{v} ≺ S_{v}. We say that T and S have the same rank and we write T ∼ S if rank(T) = rank(S). Recall that any sequence of triangular sets which is strictly decreasing w.r.t. ≺ is finite.

The polynomial p ∈ P_{n} is regular w.r.t. (or modulo) the ideal I if for every P ∈ Ass(I) we have p ∉ P. The polynomial p ∈ P_{n} is regular w.r.t. the triangular set T if it is regular w.r.t. Sat(T). The triangular set T ⊆ P_{n} is a regular chain if for any x_{i} ∈ alg(T) with i ≥ 2 the initial of T_{x_{i}} is regular w.r.t. sat_{i−1}(T). It is shown in [Aub99] that T is a regular chain iff for every i = 0 ⋯ n we have sat_{i−1}(T) = Sat(T) ∩ P_{i}. Moreover in [Mor97] we show that T is a regular chain iff for every p ∈ P_{n} we have p ∈ Sat(T) ⟺ prem(p, T) = 0. A subset W of K^{n} is a quasi-component if there exists a regular chain T such that W(T) = W. It is shown in [Kal91] that if T is a regular chain with r elements, then W(T) ≠ ∅ and Sat(T) is unmixed-dimensional with dimension n − r. Let k be an integer in the range 0 ⋯ n − 1. Let p ∈ P_{n} with p ∉ k and mvar(p) = x_{k+1}. Assume that T is a regular chain contained in P_{k} and that init(p) is regular w.r.t. T. Then we have:

Sat(T ∪ p) = (I(p) + Sat(T)) : init(p)^{∞}. (3)

See Proposition 4.3.2. of [Aub99]. This property has an immediate and very useful consequence. Let T′ be a second regular chain of P_{n} contained in P_{k} such that T′ ∪p is a regular chain and Sat(T) ⊆ Sat(T′). Relation (3) shows that we have Sat(T ∪ p) ⊆ Sat(T′ ∪ p).

The polynomial p is normalized w.r.t. T if either p ∈ k or mvar(p) ∉ alg(T) and init(p) is normalized w.r.t. T. The triangular set T is normalized if for every x_{i} ∈ alg(T) the polynomial T_{x_{i}} is normalized w.r.t T_{x_{i}}^{−}. Any normalized triangular set is a regular chain. For the concepts of square-free regular chain and Lazard triangular set, please see [AM99].

To state our algorithms, we use the syntax of the programming language of the Computer Algebra System AXIOM [JS92]. In particular we use indentation for denoting blocks of instructions. However we use # instead of −− to start a line of comments. Let B = {I_{1}, …, I_{ℓ}} be a block of instructions. Assume that some instruction I_{j} has the form Bool ⟹ C where Bool evaluates to a boolean value and C is a block of instructions. Then B is equivalent to: {I_{1}, …, I_{j−1}, if Bool then C else {I_{j+1}, …, I_{ℓ}}} . Assume now that B is the block of instructions of a loop. If C consists of the single instruction iterate, then B is equivalent to: {I_{1}, …, I_{j−1}, if not Bool then {I_{j+1}, …, I_{ℓ}}} .

An instruction return(x) inside a body of a function means: return x and leave the body. Most of our algorithms return a sequence of values. One way to implement this is to manage a list S of the output items and to use return(S) when S is complete. Another approach is to use the concept of a generator which is supported by Aldor, the AXIOM compiler [BDI^{+}94]. Instead of inserting each output item s in a list we throw s directly in the flow of output with the statement output(s) and we use the key-word exit to leave the body.

2 Properties of Quasi-Components under Factorization

Most of the algorithms described in this paper take a regular chain T as part of their input and return a sequence T_{1}, …, T_{ℓ} of regular chains as part of their output. We give in this section various relations on regular chains and quasi-components. More precisely, we study in Lemma 4 and Theorem 7 the possible splits of the quasi-component W(T) when a polynomial of T has a non-trivial factorization. We consider two kinds of relations. The following definition clarifies this latter point.

Definition 1 Let W, W_{1}, …, W_{ℓ} be subsets of the affine space K^{n}. We say that the sequence (W_{1}, …, W_{ℓ}) is a Kalkbrener split of W and we write

W ⟶_{K} (W_{1}, …, W_{ℓ})

if W and the union W_{1}∪⋯∪W_{ℓ} have the same closure w.r.t. Zariski topology. We say that (W_{1}, …, W_{ℓ}) is a Lazard split of W and we write

W ⟶_{L} (W_{1}, …, W_{ℓ})

if this is a Kalkbrener split of W and if the union W_{1} ∪ ⋯ ∪ W_{ℓ} contains W. By convention, if W is empty, the empty sequence is a Lazard split of W.

The terminology follows from the specification of the algorithms of Kalkbrener [Kal93] and Lazard [Laz91] as they are presented in [AM99]. Let us point out two useful relations that follow immediately from Definition 1.

Proposition 2 Let W, W_{1}, …, W_{ℓ}, W_{1,1}, …, W_{1,n_{1}}, …, W_{ℓ,1}, …, W_{ℓ,n_{ℓ}} be subsets of K^{n} such that W ⟶_{L} (W_{1}, …, W_{ℓ}). The following properties hold.

(a) If for every i = 1 ⋯ ℓ the relation W_{i} ⟶_{L} (W_{i,1}, …, W_{i,n_{i}}) is satisfied, then we have:

W ⟶_{L} (W_{1,1}, …, W_{1,n_{1}}, …, W_{ℓ,1}, …, W_{ℓ,n_{ℓ}}).

(b) Assume that W is an algebraic variety. Let V be another algebraic variety such that the relation V ∩ W_{i} ⟶_{L} (W_{i,1}, …, W_{i,n_{i}}) holds for every i = 1 ⋯ ℓ. Then we have:

V ∩ W ⟶_{L} (W_{1,1}, …, W_{1,n_{1}}, …, W_{ℓ,1}, …, W_{ℓ,n_{ℓ}}).

Observe that relation (a) holds also for Kalkbrener splits. In Section 3 we will introduce another kind of splits that satisfies a similar property (Proposition 13) and we will often refer to it as the Composition Property. Of course, without this nice behavior, a notion of split would have a limited interest.

Property (b) is crucial for decomposing an algebraic variety into quasi-components in an incremental manner. We shall explain this in Section 3. Unfortunately property (b) does not hold for Kalkbrener splits. Indeed, consider a variety W ⊆ K^{n} and a regular chain T ⊆ P_{n} such that \overline{W(T)} = W and W(T) ≠ W hold. Assume that for some t ∈ T the initial h of t satisfies (W \ W(T)) ∩ V(h) ≠ ∅. We have W ⟶_{K} (W(T)) and W ∩ V(h) ≠ ∅. However we have W(T)∩V(h) = ∅. Hence (W(T)∩V(h)) is not a Kalkbrener split of W ∩ V(h). Note that (W(T)) is not a Lazard split of W. In Lemma 4 and in Theorem 7 we shall give fundamental examples of Kalkbrener and Lazard splits by means of Definition 3. The proof of Lemma 4 follows easily from the relations (1), (2) and (3) of Section 1.

Definition 3 Let T, T_{1}, …, T_{ℓ} be regular chains in P_{n}. We say that (T_{1}, …, T_{ℓ}) is a Kalkbrener split (resp. Lazard split) of T if (W(T_{1}), …, W(T_{ℓ})) is a Kalkbrener split (resp. Lazard split) of W(T). We will use the same notations to denote splits of regular chains as those for splits of subsets of K^{n}.

Lemma 4 Let T ⊆ P_{n} be a regular chain. Let t, c ∈ P_{n} be two non-constant polynomials such that c is regular w.r.t. T and mvar(c) < mvar(t) holds. Then T ∪ t is a regular chain if and only if T ∪ c t is a regular chain. Moreover, if T ∪ t is a regular chain, then the following relations hold:

(a) T ∪ t ⟶_{K} (T ∪ c t),

(b) T ∪ c t ⟶_{L} (T ∪ t),

(c) W(T ∪ t) ⟶_{L} (W(T ∪ c t), Z(c, T ∪ t)).

Roughly speaking, Lemma 4 shows how to split the quasi-component W(T) under the primitive factorization of t regarded as univariate w.r.t. mvar(t). We are interested now in the case where t factors into several polynomials with mvar(t) as main variable. This problem is treated in Theorem 7 which requires the following preliminary results.

Proposition 5 Let T and U be two regular chains of P_{n}. Assume that the radical of Sat(T) is contained in the radical of Sat(U). Then we have:

(a) dim(U) ≤ dim(T),

(b) If dim(U) = dim(T) then every polynomial h regular w.r.t. T is also regular w.r.t. U.

Proof. Our assumption means that the intersection of the prime ideals associated with Sat(T) is contained in the intersection of the prime ideals associated with Sat(U). Now recall that if a prime ideal contains an intersection of ideals then it contains one of them. Therefore every prime ideal associated with Sat(U) contains a prime ideal associated with Sat(T). Since the saturated ideal of a regular chain is unmixed, property (a) is proved. Now assume that dim(U) = dim(T) holds. This implies that every prime ideal associated with Sat(U) is a prime ideal associated with Sat(T). So if a polynomial h is regular w.r.t. T, then it is regular w.r.t. U. □

Lemma 6 Let T ⊆ P_{n} be a triangular set. Let a, b, t be non-constant polynomials with the same main variable x_{k+1} (with k in the range 0 ⋯ n − 1). We denote by h_{a} the initial of a. We assume that the following properties hold:

(i) T ∪ t is a regular chain, (ii) prem(t, a) ∈ Sat(T) ∩ P_{k} and b = pquo(t, a), (iii) h_{a} is regular w.r.t. T.

Then T ∪ a and T ∪ b are regular chains. Moreover we have:

(a) Sat(T ∪ t) ⊆ Sat(T ∪ a),

(b) Sat(T ∪ t) ⊆ Sat(T ∪ b),

(c) \sqrt{Sat(T ∪ t)} = \sqrt{Sat(T ∪ a)} ∩ \sqrt{Sat(T ∪ b)}.

Proof. Let us fix some notations. We define h = init(t) and h_{b} = init(b). The fact that the polynomials a, b, t have main variable x_{k+1} together with assumption (ii) implies that there exist an integer e ≥ 1 and a polynomial r_{t} ∈ Sat(T) ∩ P_{k} such that: h_{a}^{e} t = a b + r_{t}.

First we assume that T ⊆ P_{k} holds. Assumption (iii) implies that T ∪ a is a regular chain. We prove that T ∪ b is a regular chain too. Observe that the product h_{a}^{e} h equals the product h_{a} h_{b}. Since h_{a} and h are regular w.r.t. T, then so is h_{b}. Hence T ∪ b is a regular chain. We prove that Sat(T ∪ t) ⊆ Sat(T ∪ a). Let f be in Sat(T ∪ t). Thus prem(f, t) lies in Sat(T). Then there exits a non-negative integer e′, a polynomial q_{f} ∈ P_{k+1} and a polynomial r_{f} ∈ Sat(T) ∩ P_{k} such that h^{e′} f = q_{f} t + r_{f}. Therefore we have:

h_{a}^{e} h^{e′} f = q_{f} a b + q_{f} r_{t} + h_{a}^{e} r_{f}. (4)

This shows that h_{a}^{e} h^{e′} f ∈ I(a) + Sat(T) and thus that h^{e′} f ∈ (I(a) + Sat(T)) : h_{a}^{∞}. With relation (3) page 6, we obtain h^{e′} f ∈ Sat(T ∪ a). Thus f lies in Sat(T ∪ a) : h^{∞}. Since h ∈ P_{k} and since h is regular w.r.t. Sat(T), it cannot belong to a prime ideal associated with Sat(T ∪ a) (we are using here relation (2) page 5). Therefore we have Sat(T ∪ a) : h^{∞} = Sat(T ∪ a) and we obtain f ∈ Sat(T ∪ a). Now we prove that f ∈ Sat(T ∪ b). Recall that we have h_{a}^{e} h = h_{a} h_{b}. Thus equation 4, after multiplication by h, shows that h_{a} h_{b} h^{e′} f lies in I(b) + Sat(T). As above this leads to h_{a} h^{e′} f ∈ Sat(T ∪ b). Since h_{a} h^{e′} is regular w.r.t. T, we conclude that f ∈ Sat(T ∪ b).

We come back to the general case and assume that T contains at least one polynomial with main variable greater than x_{k+1}. We define v = x_{k+1}. Let p be the polynomial of T_{v}^{+} with smallest main variable. We know that T_{v}^{−} ∪ t, T_{v}^{−} ∪a, and T_{v}^{−} ∪b are regular chains such that the saturated ideal of the first one is contained in the saturated ideals of the other ones. Since they all have the same dimension, property (b) of Proposition 5 shows that init(p) is regular w.r.t. T_{v}^{−} ∪ a and T_{v}^{−} ∪ b. Hence T_{v}^{−} ∪ {a, p} and T_{v}^{−} ∪ {b, p} are regular chains. Moreover relation (3) page 6 shows that their saturated ideals contain that of T_{v}^{−} ∪ {t, p}. Continuing in this manner with the other polynomials of T_{v}^{+}, it follows that T ∪ a and T ∪ b are regular chains and that both the relations (a) and (b) hold. Finally, proving relation (c) is easy. □

Theorem 7 With the same notations and assumptions as in Lemma 6, the following properties hold:

(a) T ∪ t ⟶_{K} (T ∪ a, T ∪ b),

(b) W(T ∪ t) ⟶_{L} (W(T ∪ a), W(T ∪ b), Z(h_{a}, T ∪ t)).

Proof. Property (a) follows from relation (1) page 5 and property (c) of Lemma 6. We prove property (b). Using the notations of the proof of Lemma 6, observe first that the polynomial h_{a}^{e} t − a b vanishes at any point ζ of the algebraic variety associated with Sat(T). Since V(Sat(T)) contains W(T) we get Z(h_{a} t, T) = Z(a b, T). Since the initials of h_{a}^{e} t and ab are equal, we deduce: W(T ∪ h_{a} t) = W(T ∪ a b). This can be easily written as:

W(T ∪ h_{a} t) = W(T ∪ h_{b} a) ∪ W(T ∪ h_{a} b) (5)

where each triangular set is a regular chain by Lemmas 4 and 6. Now observe that we have:

W(T ∪ t) = W(T ∪ h_{a} t) ∪ Z(h_{a}, T ∪ t).

Thus with relation (5) and property (a) we obtain:

W(T ∪ t) = W(T ∪ h_{b} a) ∪ W(T ∪ h_{a} b) ∪ Z(h_{a}, T ∪ t)
⊆ W(T ∪ a) ∪ W(T ∪ b) ∪ Z(h_{a}, T ∪ t)
⊆ \overline{W(T ∪ a)} ∪ \overline{W(T ∪ b)} ∪ \overline{Z(h_{a}, T ∪ t)}
⊆ \overline{W(T ∪ t)}.

The theorem is proved. □

Corollary 8 With the above hypothesis, let (W(T_{1}), …, W(T_{ℓ})) be a Lazard split of Z(h_{a}, T ∪ t) then (T ∪ a, T ∪ b, T_{1}, …, T_{ℓ}) is a Lazard split of T ∪ t.

3 Incremental Triangular Decompositions

Let F denote a subset of P_{n} and let V be its associated algebraic variety in K^{n}. Our aim is to decompose V into a finite union of regular chains by solving each of the following problems:

(K) Compute regular chains T_{1}, …, T_{ℓ} such that V ⟶_{K} (W(T_{1}), …, W(T_{ℓ})), (L) Compute regular chains T_{1}, …, T_{ℓ} such that V ⟶_{L} (W(T_{1}), …, W(T_{ℓ})).

Since V = \overline{V}, solving each problem leads to a decomposition of V. The former brings a decomposition into varieties and the latter brings a decomposition into quasi-components. Clearly, a solution of problem (L) is a solution of problem (K) but the converse is false. Roughly speaking, a solution of problem (K) gives only the generic zeros (in the sense of [van91]) of the irreducible components of V. See for instance [AM99] for several examples. Another interesting feature of problem (L) is that it can be solved in an incremental manner; this follows from Proposition 2. So we will concentrate now on problem (L). In Section 6 we shall show how to modify our algorithm for solving problem (L) in order to get an efficient method for solving problem (K).

The goal of the following three sections will be to describe an operation denoted by solve such that solve(F) computes a Lazard split of V. Proceeding in an incremental manner, we shall reduce the computation of solve(F) into more elementary computations as follows. Assume that we are given an operation intersect with the following specification as in [Laz91]. For every polynomial p ∈ P_{n} and every regular chain T ⊆ P_{n}, the output of intersect(p, T) is a sequence (T_{1}, …, T_{d}) of regular chains of P_{n} such that Z(p, T) ⟶_{L} (W(T_{1}), …, W(T_{d})). By using Proposition 2, this operation leads to the straightforward algorithm.

Algorithm 1

• Input: F a finite set of polynomials of P_{n}.

• Output: Regular chains T_{1}, …, T_{d} such that (W(T_{1}), …, W(T_{d})) is a Lazard split of V(F).

• solve(F) ==

C := [∅]

# C is a list of regular chains while F ≠ ∅ repeat

choose and remove a polynomial p from F C′ := [ ] for T ∈ C repeat

C′ := concat(intersect(p, T), C′) C := C′ return C Assume that F = {p_{1}, …, p_{m}} where p_{i} is the i-th polynomial chosen by Algorithm 1. Then observe that the i-th iteration of the while loop computes a split of Lazard of V(p_{1}, …, p_{i}). As pointed out in [Laz91] the order in which the regular chains are output should be in decreasing dimension. Indeed, if the quasi-component W(T) is contained in the quasi-component W(T′) then we have dim(T) ≤ dim(T′). Hence, assuming that we have an inclusion test for quasi-components, producing regular chains by decreasing dimension allows us to remove redundant quasi-components as soon as possible and to control the number of unnecessary computations. Therefore one would like to compute first the quasi-components with maximal dimension and to delay the computation of the others. This leads to the new notion of splits of Definition 11 together with the following concept.

Definition 9 A process of P_{n} is a pair [F, T] where F is a subset of P_{n} and T is a triangular set of P_{n}. We say that the process [F_{1}, T_{1}] of P_{n} has a lower rank than the process [F_{2}, T_{2}] of P_{n} and we write [F_{1}, T_{1}] ≺ [F_{2}, T_{2}] if either T_{1} ≺ T_{2} holds or T_{1} ∼ T_{2} holds and there exists a polynomial f in F_{1} with smaller rank w.r.t. ≺ than any polynomial in F_{2}.

If F is empty or if T is not a regular chain, then the process [F, T] represents a computation that needs to be done in order to describe Z(F, T). We will use processes to represent these computations that we want to delay. To establish the termination of our algorithm we need the following Proposition 10, whose proof is straightforward.

Proposition 10 Let S be a sequence of processes in P_{n}. If S is strictly decreasing w.r.t. the ordering ≺, then S is finite.

Definition 11 Let [F_{1}, T_{1}], …, [F_{d}, T_{d}] and [F, T] be processes of P_{n}. We say that the sequence (Z(F_{1}, T_{1}), …, Z(F_{d}, T_{d})) is a delayed split of Z(F, T) and we write:

Z(F, T) ⟶_{D} (Z(F_{1}, T_{1}), …, Z(F_{d}, T_{d}))

if for every i = 1 ⋯ d the following conditions hold:

(D_{1}) [F_{i}, T_{i}] ≺ [F, T], (D_{2}) Z(F, T) ⊆ Z(F_{1}, T_{1}) ∪ ⋯ ∪ Z(F_{d}, T_{d}), (D_{3}) Sat(T) ⊆ Sat(T_{i}), (D_{4}) F_{i} ≠ ∅ ⟹ F ⊆ F_{i}, (D_{5}) F_{i} = ∅ ⟹ W(T_{i}) ⊆ V(F).

If this holds and if for every i = 1 ⋯ d the triangular set T_{i} is a regular chain, we say that (Z(F_{1}, T_{1}), …, Z(F_{d}, T_{d})) is a regular delayed split of Z(F, T). By convention, if Z(F, T) is empty, we say that the empty sequence is a regular delayed split of Z(F, T).

Let [F, T], [F_{1}, T_{1}], …, [F_{d}, T_{d}] be processes of P_{n} such that (Z(F_{1}, T_{1}), …, Z(F_{d}, T_{d})) is a delayed split of Z(F, T). We give first an informal explanation of Definition 11. Condition (D_{1}) means that each Z(F_{i}, T_{i}) is better described than Z(F, T). Condition (D_{2}) means that no information is lost. Conditions (D_{3}) to (D_{5}) mean essentially that the possible extraneous information is kept under control, as we shall see now. So let us have a closer look at these three conditions. Condition (D_{3}) implies that each V(Sat(T_{i})) is contained in \overline{W(T)}. Condition (D_{4}) implies that if F_{i} is not empty then V(F_{i}) ⊆ V(F) and Z(F_{i}, T_{i}) ⊆ W(T_{i}) ∩ V(F) hold. Condition (D_{5}) implies that if F_{i} is empty then W(T_{i}) ⊆ V(F) and again Z(F_{i}, T_{i}) ⊆ W(T_{i}) ∩ V(F) hold. Therefore with condition (D_{2}) we obtain:

V(F) ∩ W(T) ⊆ Z(F_{1}, T_{1}) ∪ ⋯ ∪ Z(F_{d}, T_{d}) ⊆ V(F) ∩ \overline{W(T)}.

Observe that Z(F_{1}, T_{1}) ∪ ⋯ ∪ Z(F_{d}, T_{d}) may not be contained in the closure of Z(F, T) and the sequence (Z(F_{1}, T_{1}), …, Z(F_{d}, T_{d})) may be neither a Kalkbrener split nor a Lazard split of Z(F, T). It is important to remark that a Kalkbrener split or a Lazard split may not be a delayed split, obviously because of condition (D_{1}) but also because of condition (D_{3}). Indeed these former notions of splits impose only conditions on radicals whereas (D_{3}) is a condition on ideals. Proposition 12 gives an important example of (regular) delayed splits. Its proof follows immediately from Lemma 6 and Theorem 7. Recall that Z(∅, T) and W(T) denote the same object.

Proposition 12 With the same notations and assumptions as in Lemma 6, we have:

W(T ∪ t) ⟶_{D} (W(T ∪ a), W(T ∪ b), Z(h_{a}, T ∪ t)).

Following the previous discussion, we need to explain why we can use these splits even though they may lead to extraneous solutions. In fact we shall see that if the starting point of a cascade of delayed splits is a variety, then this bad situation never happens. The first step is to show that we have a composition property similar to property (a) of Proposition 2. This is the goal of Proposition 13 whose proof is straightforward. The second step is to show that delayed splits have a nice behavior with algebraic varieties, a property similar to point (b) of Proposition 2. This will be done in Proposition 14.

Proposition 13 Let [F, T], [F_{1}, T_{1}], …, [F_{d}, T_{d}], [F_{1,1}, T_{1,1}], …, [F_{1,e}, T_{1,e}] be processes of P_{n} such that F_{1} ≠ ∅. Assume that the following relations hold:

(i) Z(F, T) ⟶_{D} (Z(F_{1}, T_{1}), …, Z(F_{d}, T_{d})), (ii) Z(F_{1}, T_{1}) ⟶_{D} (Z(F_{1,1}, T_{1,1}), …, Z(F_{1,e}, T_{1,e})).

Then we have:

Z(F, T) ⟶_{D} (Z(F_{1,1}, T_{1,1}), …, Z(F_{1,e}, T_{1,e}), Z(F_{2}, T_{2}), …, Z(F_{d}, T_{d})).

Proposition 14 Let F, F_{1}, …, F_{d}, F_{1,1}, …, F_{1,e} be subsets of P_{n} such that F_{1} ≠ ∅. Let T_{1}, …, T_{d}, T_{1,1}, …, T_{1,e} be triangular sets of P_{n}. Assume that the following relations hold:

(i) V(F) ⊆ Z(F_{1}, T_{1}) ∪ ⋯ ∪ Z(F_{d}, T_{d}), (ii) for every i = 1 ⋯ d we have F_{i} = ∅ ⟹ W(T_{i}) ⊆ V(F), (iii) for every i = 1 ⋯ d we have F_{i} ≠ ∅ ⟹ W(T_{i}) ⊆ V(F \ F_{i}), (iv) Z(F_{1}, T_{1}) ⟶_{D} (Z(F_{1,1}, T_{1,1}), …, Z(F_{1,e}, T_{1,e})).

Then the properties below hold:

(a) for every j = 1 ⋯ e we have F_{1,j} = ∅ ⟹ W(T_{1,j}) ⊆ V(F),

(b) for every j = 1 ⋯ e we have F_{1,j} ≠ ∅ ⟹ W(T_{1,j}) ⊆ V(F \ F_{1,j}),

(c) If F_{2}, …, F_{d}, F_{1,1}, …, F_{1,e} are all empty then we have:

V(F) = ∪_{i=2}^{d} W(T_{i}) ∪ ∪_{j=1}^{e}W(T_{1,j}).

Proof. Let j be in the range 1 ⋯ e. We prove property (a). Assume F_{1,j} = ∅. By condition (D_{5}) we have W(T_{1,j}) ⊆ V(F_{1}). By condition (D_{3}) we have W(T_{1,j}) ⊆ \overline{W(T_{1})}. Since F_{1} ≠ ∅ by hypothesis (iii) we have W(T_{1}) ⊆ V(F \ F_{1}). Thus W(T_{1,j}) ⊆ V(F_{1}) ∩ V(F \ F_{1}). Therefore W(T_{1,j}) ⊆ V(F) and property (a) is proved. Assume now that F_{1,j} ≠ ∅ holds. Thus F_{1} ⊆ F_{1,j} holds. Since W(T_{1}) ⊆ V(F \ F_{1}) and W(T_{1,j}) ⊆ \overline{W(T_{1})} hold, we easily obtain W(T_{1,j}) ⊆ V(F \ F_{1,j}) and property (b) is proved. We prove property (c). Assume that F_{2}, …, F_{d}, F_{1,1}, …, F_{1,e} are empty. By hypothesis (i) and (iv) the union of all W(T_{i,j}) and W(T_{i}) contains V(F). By hypothesis (ii) and property (a) the same union is contained in V(F). Property (c) is proved. □

Delayed splits involving only processes of the form [∅, T] play a special role in the algorithms of Sections 4 and 5. This leads us to Definition 15, Proposition 16 and its Corollary 17 which enhance the results of Section 2.

Definition 15 Let T, T_{1}, …, T_{d} be triangular sets of P_{n}. We say that the sequence (T_{1}, …, T_{d}) is a delayed split of T and we write:

T ⟶_{D} (T_{1}, …, T_{d})

if either d = 1 and T = T_{d}, or W(T) ⟶_{D} (W(T_{1}), …, W(T_{d})). If this holds and if for every i = 1 ⋯ d the triangular set T_{i} is a regular chain, we say that (T_{1}, …, T_{d}) is a regular delayed split of T. By convention, if W(T) = ∅ holds, we say that the empty sequence is a regular delayed split of T.

Proposition 16 Let T, T_{1}, …, T_{d} be regular chains of P_{n}. Let p be a polynomial of P_{n} regular w.r.t. T and such that (W(T_{1}), …, W(T_{d})) is a delayed split of Z(p, T). Then for every i = 1 ⋯ d we have dim(T_{i}) < dim(T).

Proof. Indeed, if we had dim(T_{i}) = dim(T), then condition (D_{3}) of delayed splits together with Proposition 5 shows that p would be regular w.r.t. T_{i}. Therefore p would not belong to any prime ideal associated with Sat(T_{i}). However condition (D_{5}) of delayed splits implies that p must belong to the radical of Sat(T_{i}). A contradiction. □

Corollary 17 With the same assumptions as in Lemma 6, let T_{1}, …, T_{d} be regular chains of P_{n} such that Z(h_{a}, T ∪ t) ⟶_{D} (W(T_{1}), …, W(T_{d})). Then we have: T ∪ t ⟶_{L} (T ∪ a, T ∪ b, T_{1}, …, T_{d}). Moreover, for every i = 1 ⋯ d we have dim(T_{i}) < dim(T ∪ t).

Proposition 18 states a last technical result before presenting our algorithm for solving problem (L) by means of delayed splits. The proof of this proposition is straightforward. From now on we assume that we are given an operation decompose defined below in Specification 1. This leads to Algorithm 2 which provides an operation solve (as in Algorithm 1) based on delayed splits.

Proposition 18 Let [F, T], [F_{1}, T_{1}], …, [F_{d}, T_{d}] be processes of P_{n} such that F ≠ ∅. Let p be a polynomial in F minimal w.r.t. ≺ Assume that (Z(H_{1}, T_{1}), …, Z(H_{d}, T_{d})) is a delayed split of Z(p, T). Then (Z(F ∪ H_{1}, T_{1}), …, Z(F ∪ H_{d}, T_{d})) is a delayed split of Z(F, T).

Specification 1 For any regular chain T ⊆ P_{n} and any polynomial p ∈ P_{n} such that p ∉ k and p ∉ Sat(T) the operation decompose(p, T) returns a regular delayed split of Z(p, T).

Algorithm 2

• Input: F a finite set of polynomials of P_{n}.

• Output: Regular chains T_{1}, …, T_{d} such that (W(T_{1}), …, W(T_{d})) is a Lazard split of V(F).

• solve(F) ==

R := [[F, ∅]]

# R is a list of processes while R ≠ [ ] repeat

choose and remove a process [F_{1}, U_{1}] from R F_{1} = ∅ ⟹ output U_{1} choose a polynomial p ∈ F_{1} minimal w.r.t. ≺ G := F_{1} \ {p} p := red(p, U_{1}) p = 0 ⟹ R := cons ([G, U_{1}], R) p ∈ k ⟹ iterate for [H, T] ∈ decompose(p, U_{1}) repeat

R := cons ([F_{1} ∪ H, T], R) exit Proposition 19 If every call to the operation decompose satisfies Specification 1, then Algorithm 2 terminates and satisfies its specification.

Proof. We denote by L_{i} the i-th iteration of the while loop. Let [F_{1}, U_{1}], …, [F_{r}, U_{r}] be the processes in R before L_{i}. Let T_{1}, …, T_{s} be the regular chains that have returned via the output statement before L_{i}. Assume that during L_{i} the process [F_{1}, U_{1}] is chosen and removed from R. We first prove that the above algorithm terminates. If F_{1} is empty, note that the number of processes has decreased after L_{i}. If F_{1} is not empty and if the polynomial p reduces to a constant w.r.t. U_{1}, then again the number of processes has decreased. Thus if the while loop is infinite, the for loop needs to be performed an infinite number of times. Now assume that the for loop is performed during L_{i}. Observe that the new processes have smaller rank than [F_{1}, U_{1}] (because of the choice of p and because of condition (D_{1}) of Definition 11). If the for loop was performed an infinite number of times, then the successive values of R could be organized as an ordered tree w.r.t. ≺ with at least one infinite chain. But this would contradict Proposition 10. Therefore the algorithm terminates.

We check now that the above algorithm is correct. We assume that before L_{i} the following relations holds:

(M_{i}) V(F) ⊆ Z(F_{1}, U_{1}) ∪ ⋯ ∪ Z(F_{r}, U_{r}) ∪ W(T_{1}) ∪ ⋯ ∪ W(T_{s}), (m_{i}) W(T_{1}) ∪ ⋯ ∪ W(T_{s}) ⊆ V(F), (S_{i}) for every j = 1 ⋯ r we have W(U_{j}) ⊆ V(F \ F_{j}).

Note that this assumption is clearly satisfied for every i = 1, so we next prove that this still holds for every i + 1. Assume that F_{1} is empty. Then Z(F_{1}, U_{1}) = W(U_{1}). Thus (M_{i+1}) clearly holds. Now U_{1} becomes a new output regular chain. From S_{i} we know that W(U_{1}) ⊆ V(F). Hence relation (m_{i+1}) holds. Trivially (S_{i+1}) also holds. So consider now that a polynomial p is extracted from F_{1}. Assume that p reduces to zero w.r.t. U_{1}. This means that p ∈ Sat(U_{1}). Hence W(U_{1}) ⊆ V(p) and Z(F_{1}, U_{1}) = Z(F_{1} \{p}, U_{1}). Thus the relations (M_{i+1}), (m_{i+1}) and (S_{i+1}) hold again. Assume now that p reduces to a non-zero constant. This means that Z(p, U_{1}) = ∅ = Z(F_{1}, U_{1}). Thus we can delete Z(F_{1}, U_{1}) from (M_{i}). Then it follows easily that the relations (M_{i+1}), (m_{i+1}) and (S_{i+1}) hold. Now assume that the for loop is performed. The conclusion follows by applying Proposition 18 and then Proposition 14. Finally we observe that if L_{i} is the last iteration of the while loop, then Proposition 14 shows that our algorithm returns a Lazard split of V(F). □

Remark 20 Let p be in P_{n} and let T ⊆ P_{n} be a regular chain. Note that ([∅, T]) may never be a delayed split of Z(p, T) because of condition (D_{1}). This justifies the input specification of decompose(p, T) (Specification 1) and the design of Algorithm 2. Observe now that Algorithm 2 can easily be adapted in order to implement an operation intersect with the following specification: for a polynomial p ∈ P_{n} and a regular chain T ⊆ P_{n} such that p ∉ Sat(T) we denote by intersect(p, T) a sequence (T_{1}, …, T_{d}) of regular chains in P_{n} such that Z(p, T) ⟶_{D} (W(T_{1}), …, W(T_{d})). Indeed, it suffices to replace the line R := [[F, ∅]] of Algorithm 2 by R:= [{p}, T]. The termination and the correctness of intersect(p, T) result from Propositions 10 and 13 respectively. Note that this operation intersect has weaker specification than the one of Lazard’s algorithm. This is because the union of our W(T_{i}) may not be contained in the closure of Z(p, T). However this will never lead us to any trouble (i.e. extraneous solutions) since we shall always use this operation intersect in the context of Corollary 17 (to compute a regular delayed split of Z(h_{a}, T ∪ t)).

Algorithm 2 reduces problem (L) to the following task. Given a polynomial p ∈ P_{n} and a regular chain T ⊆ P_{n} such that p ∉ Sat(T) compute a regular delayed split of the intersection Z(p, T) of the hypersurface V(p) and the quasi-component W(T). We will achieve this task in Sections 4 and 5. First we will show that with additional conditions on p and T, a regular delayed split of Z(p, T) can be obtained. Then we will provide a way to replace T by a regular delayed split (T_{1}, …, T_{d}) of T such that p and each T_{i} satisfy our additional conditions. In order for this strategy to work we need a composition property. Proposition 22 will provide the appropriate result after Definition 21.

When computing a regular delayed split of Z(p, T) we will often be led to consider a projection. More precisely, if p has main variable x_{k+1}, we will consider Z(p, T) ∩ P_{k+1}. Therefore we need a way to lift the resulting computations from P_{k+1} to P_{n}. This is the goal of Theorem 23, concluding this section.

Definition 21 Given a subset F of P_{n} and a polynomial p ∈ P_{n} we define the subset F ·p of P_{n} as follows. If F = ∅ then F ·p = ∅ otherwise F ·p = F ∪p.

Proposition 22 Let T, T_{1}, …, T_{d} be triangular sets of P_{n} such that (T_{1}, …, T_{d}) is a delayed split of T. Let p be a polynomial of P_{n} such that p ∉ Sat(T). For every i = 1 ⋯ d let ([F_{i,1}, T_{i,1}], …, [F_{i,e_{i}}, T_{i,e_{i}}]) be processes of P_{n} such that one of the following conditions holds:

(A_{i}) p ∈ Sat(T_{i}), e_{i} = 1, F_{i,1} = ∅ and T_{i,1} = T_{i}, (B_{i}) p ∉ Sat(T_{i}) and Z(q_{i}, T_{i}) ⟶_{D} (Z(F_{i,1}, T_{i,1}), …, Z(F_{i,e_{i}}, T_{i,e_{i}})) where q_{i} is

a non-constant polynomial equal to p modulo Sat(T_{i}) and with no higher rank than p w.r.t. ≺.

Then we have:

\begin{aligned}Z(p, T) & ⟶_{D} & (Z(F_{1,1} · p, T_{1,1}), …, Z(F_{1,e_{1}} · p, T_{1,e_{1}}), …, \\ & & Z(F_{d,1} · p, T_{d,1}), …, Z(F_{d,e_{d}} · p, T_{d,e_{d}})). \end{aligned}

Proof. Since (T_{1}, …, T_{d}) is a delayed split of T two cases arise: either d = 1 and T = T_{d} hold or W(T) ⟶_{D} (W(T_{1}), …, W(T_{d})) holds. Proving the proposition in the first case is easy, so we restrict ourselves to the second one. First, we prove that condition (D_{1}) holds. Let i be in the range 1 ⋯ d. We can assume that assumption (B_{i}) holds otherwise there is nothing to prove. Since (W(T_{1}), …, W(T_{d})) is a delayed split of W(T), we have T_{i} ≺ T which implies [p, T_{i}] ≺ [p, T]. Let j be in the range 1 ⋯ e_{i}. Since (Z(F_{i,1}, T_{i,1}), …, Z(F_{i,e_{i}}, T_{i,e_{i}})) is a delayed split of Z(q_{i}, T_{i}) we have [F_{i,j}, T_{i,j}] ≺ [q_{i}, T_{i}]. We need to check that [F_{i,j} · p, T_{i,j}] ≺ [p, T] holds. Two cases arise. If T_{i,j} ≺ T_{i}, then the result is obvious. If T_{i,j} ∼ T_{i} then F_{i,j} must contain a polynomial smaller w.r.t. ≺ than q_{i} and the result is clear again since q_{i} has no higher rank than p. Therefore property (D_{1}) holds. We now prove property (D_{2}). Since (W(T_{1}), …, W(T_{d})) is a delayed split of W(T) we have:

W(T) ⊆ ∪_{i=1}^{d} W(T_{i}). (6)

Since p − q_{i} ∈ Sat(T_{i}) we have V(p) ∩ W(T_{i}) = V(q_{i}) ∩ W(T_{i}), leading to:

V(p) ∩ W(T_{i}) ⊆ ∪_{j=1}^{e_{i}} Z(F_{i,j}, T_{i,j}). (7)

In relation (7) we can replace every term Z(F_{i,j}, T_{i,j}) such that F_{i,j} ≠ ∅ by V(p) ∩ Z(F_{i,j}, T_{i,j}). Hence relations (6) and (7) lead to (D_{2}). Since Sat(T) ⊆ Sat(T_{i}) and Sat(T_{i}) ⊆ Sat(T_{i,j}) hold property (D_{3}) is clear. Since F_{i,j} · p ≠ ∅ implies p ∈ F_{i,j} ·p property (D_{4}) is clear. We prove (D_{5}). We assume F_{i,j} ·p = ∅ which implies F_{i,j} = ∅. If (A_{i}) holds, then we have W(T_{i,j}) ⊆ V(p) since T_{i,j} = T_{i} and p ∈ Sat(T_{i}). If (B_{i}) holds, then we have also W(T_{i,j}) ⊆ V(q_{i}) because (D_{5}) holds for the delayed split (Z(F_{i,1}, T_{i,1}), …, Z(F_{i,e_{i}}, T_{i,e_{i}})) of Z(q_{i}, T_{i}). Moreover we have W(T_{i,j}) ⊆ V(p − q_{i}) since p − q_{i} ∈ Sat(T_{i}) and Sat(T_{i}) ⊆ Sat(T_{i,j}) hold. Thus W(T_{i,j}) ⊆ V(p) holds in any case, leading to (D_{5}). □

Theorem 23 (Lifting Theorem) Let k be an integer such that 0 ≤ k < n. Let C ⊆ P_{k} and D ⊆ P_{n} such that C ∪ D is a regular chain, the set D is not empty and D ∩ P_{k} = ∅ holds. Let h_{C} the product of the initials of C. Let F be a finite subset of P_{n}. We assume that the following conditions hold:

(i) there exist regular chains C_{1}, …, C_{d} of P_{k} and finite subsets F_{1}, …, F_{d} of P_{n} such that

Z(F, C) ⟶_{D} (Z(F_{1}, C_{1}), …, Z(F_{d}, C_{d})),

(ii) for every i = 1 ⋯ d there exist regular chains C_{i,1}, … C_{i,e_{i}} such that

C_{i} ∪ D ⟶_{D} (C_{i,1}, … C_{i,e_{i}}),

(iii) for every i = 1 ⋯ d and every j = 1 ⋯ e_{i} the polynomial h_{C} is regular w.r.t. C_{i,j}.

Then we have:

\begin{aligned}Z(F, C ∪ D) & ⟶_{D} & (Z(F_{1}, C_{1,1}), …, Z(F_{1}, C_{1,e_{1}}), …, \\ & & Z(F_{d}, C_{d,1}), …, Z(F_{d}, C_{d,e_{d}})). \end{aligned}

Proof. Let i be in the range 1 ⋯ d and j be in 1 ⋯ e_{i}. First we prove [F_{i}, C_{i,j}] ≺ [F, C ∪ D]. From (i) we have [F_{i}, C_{i}] ≺ [F, C]. From (ii) we have either C_{i,j} ∼ C_{i} ∪ D or C_{i,j} ≺ C_{i} ∪ D. Two cases arise. If C_{i} ≺ C holds then we have C_{i} ∪ D ≺ C ∪ D leading to C_{i,j} ≺ C ∪ D and thus to the desired relation. Assume now that C_{i} ∼ C holds. This leads to C_{i} ∪ D ∼ C ∪ D. If C_{i,j} ≺ C_{i} ∪ D we are done again. Otherwise C_{i,j} ∼ C ∪ D holds. Moreover, F_{i} must contain a polynomial with smaller rank than any polynomial of F. Hence [F_{i}, C_{i,j}] ≺ [F, C ∪ D] holds in any case and property (D_{1}) is proved. Now we prove property (D_{2}). From (i) we have Z(F, C) ⊆ ∪_{i=1}^{d} Z(F_{i}, C_{i}). This leads to Z(F, C ∪ D) ⊆ ∪_{i=1}^{d} Z(F_{i}, C_{i} ∪ D). Indeed one can easily check that W(C ∪ D) = W(C) ∩ W(D) and W(C_{i} ∪ D) = W(C_{i}) ∩ W(D) hold for i = 1 ⋯ d. Now, from (ii) we have W(C_{i} ∪ D) ⊆ ∪_{j=1}^{e_{i}} W(C_{i,j}). Therefore we obtain

Z(F, C ∪ D) ⊆ ∪_{i=1}^{d} ∪_{j=1}^{e_{i}} Z(F_{i}, C_{i,j}).

Now we prove property (D_{3}). From (i) we have Sat(C) ⊆ Sat(C_{i}). Assume that we have Sat(C ∪ D) ⊆ Sat(C_{i} ∪ D). Then we conclude with (ii) by using Sat(C_{i} ∪ D) ⊆ Sat(C_{i,j}). Note that this shows that Sat(C_{i} ∪ D) ≠ P_{n} (since C_{i,j} is a regular chain). So we check now that we have Sat(C ∪ D) ⊆ Sat(C_{i} ∪ D) (although C_{i} ∪ D is not necessarily a regular chain). Let h_{D} and h_{C_{i}} be the product of the initials of D and C_{i} respectively. Let f be in Sat(C ∪ D). There exists a non-negative integer m, a polynomial f_{C} ∈ I(C) and a polynomial f_{D} ∈ I(D) such that we have: (h_{C} h_{D})^{m} f = f_{C} +f_{D}. Since I(C) ⊆ Sat(C) and Sat(C) ⊆ Sat(C_{i}) there exists a non-negative integer m′ and a polynomial f_{i} ∈ I(C_{i}) such that h_{C_{i}}^{m′} f_{C} = f_{i}. We obtain:

h_{C_{i}}^{m′} (h_{C} h_{D})^{m} f = f_{i} + h_{C_{i}}^{m′} f_{D}.

This shows that h_{C}^{m} f ∈ Sat(C_{i} ∪ D) holds. Now observe that (ii) implies that the radical of Sat(C_{i} ∪ D) is equal to the intersection of the radicals of the Sat(C_{i,j}). Thus every prime ideal associated with Sat(C_{i} ∪ D) is a prime ideal associated with one Sat(C_{i,j}) (by uniqueness of a minimal primary decomposition). Hence with (iii) it follows that h_{C} is regular modulo Sat(C_{i} ∪ D). Therefore f ∈ Sat(C_{i} ∪ D) holds and property (D_{3}) is proved. We remark that property (D_{4}) is clearly satisfied. Finally we prove property (D_{5}). So we assume F_{i} = ∅. With (i) this implies W(C_{i}) ⊆ V(F). This leads to W(C_{i} ∪ D) ⊆ V(F) and thus to \overline{W(C_{i} ∪ D)} ⊆ V(F). From (ii) we have Sat(C_{i} ∪ D) ⊆ Sat(C_{i,j}) and thus \overline{W(C_{i,j})} ⊆ \overline{W(C_{i} ∪ D)} leading to W(C_{i,j}) ⊆ V(F) and proving (D_{5}). □

4 Intersecting Hypersurfaces with Quasi-Components

Let T ⊆ P_{n} be a regular chain and let p ∈ P_{n} be a polynomial satisfying p ∉ k and p ∉ Sat(T). The goal of this section is to show how a regular delayed split of the intersection Z(p, T) of the hypersurface V(p) and the quasi-component W(T) can be obtained. If the main variable of p is not algebraic w.r.t. T, we will use the following proposition whose proof is straightforward.

Proposition 24 Let T ⊆ P_{n} be a regular chain and let p ∈ P_{n} be a polynomial satisfying p ∉ k and p ∉ Sat(T). We assume that mvar(p) is not algebraic w.r.t. T and we denote by h_{p} the initial of p. Let (T_{1}, …, T_{d}) be a regular delayed split of T ∪ p. Then we have:

Z(p, T) ⟶_{D} (Z({h_{p}, p}, T), W(T_{1}), …, W(T_{d})).

The above triangular set T ∪ p may not be a regular chain. Hence we need a procedure for building a regular delayed split (T_{1}, …, T_{d}) of T ∪ p. To do so we assume from now on that we are given an operation regular? defined in Specification 2. The validity of this assumption will be established in Section 5. The operation regular? leads to the operation extend defined in Algorithm 3.

Specification 2 For any polynomial f ∈ P_{n} and any regular chain C ⊆ P_{n}, the operation regular?(f, C) returns a regular delayed split (C_{1}, …, C_{d}) of C such that for every i = 1 ⋯ d if red(f, C_{i}) ≠ 0 then f is regular w.r.t. C_{i}.

Algorithm 3

• Input: a regular chain C contained in P_{k}, for an integer k in the range 0 ⋯ n − 1, and a non-constant p ∈ P_{n} with mvar(p) = x_{k+1}.

• Output: a regular delayed split of C ∪ p.

• extend(C, p) ==

h := init(p)

Let h_{C} be the product of the initials of C

for D ∈ regular?(h, C) repeat red(h, D) = 0 ⟹ iterate dim(D) = dim(C) ⟹ output D ∪ p for E ∈ regular?(h_{C} h, D) repeat

red(h_{C} h, E) ≠ 0 ⟹ output E ∪ p exit

We will see that each of the algorithms presented in Sections 3, 4 and 5 may call each other directly or indirectly. In order to establish their termination and correctness we need to point out on which hypothesis each algorithm calls another. Proposition 26 states that Algorithm 3 terminates and satisfies its specification provided that its calls to the operation regular? are valid.

Hypothesis 25 Let C and p be as in the input specification of Algorithm 3. We denote by H_{1}(C, p) the following hypothesis: for every regular chain R ⊆ P_{n} and for every polynomial f ∈ P_{n} such that [f, R] ≺ [p, C] holds, the call regular?(f, R) satisfies Specification 2.

Proposition 26 Let C and p be as in the input of Algorithm 3. If hypothesis H_{1}(C, p) holds then Algorithm 3 terminates and satisfies its output specification. Moreover Sat(C ∪ p) is the unit ideal iff extend(C, p) is empty.

Proof. We first show that the hypothesis of Proposition 26 applies to every call to the operation regular? in Algorithm 3. As in Algorithm 3 we denote by h the initial of p and by h_{C} the product of the initials of C. Since h ≺ p we have [h, C] ≺ [p, C]. Thus, since H_{1}(C, p) holds, we can assume that regular?(h, C) returns a regular delayed split (C_{1}, …, C_{d}, C′_{1}, …, C′_{e}) of C such that for every i = 1 ⋯ d the polynomial h is regular w.r.t. C_{i}, and for every j = 1 ⋯ e the polynomial h reduces to zero w.r.t. C′_{j}. We observe that every regular chain C′_{1}, …, C′_{e} is discarded. Then the regular chains C_{1}, …, C_{d} are separated in two groups: those satisfying dim(C_{i}) = dim(C) and the others. We denote D_{1}, …, D_{a} the former ones and D′_{1}, …, D′_{b} the latter ones. The algorithm returns D_{1} ∪p, …, D_{a} ∪p and calls regular?(h_{C} h, D) for every D = D′_{1}, …, D′_{b}. By Definition 15 we have either D′_{i} ∼ C or D′_{i} ≺ C for i = 1 ⋯ b. Thus for every D = D′_{1}, …, D′_{b} the call regular?(h_{C} h, D) satisfies Specification 2. Therefore every call to regular? of Algorithm 3 satisfies Specification 2 and every returned set is a regular chain. Moreover, Algorithm 3 terminates. We prove now that all these returned sets form a delayed split of the input C ∪ p.

Checking properties (D_{1}), (D_{4}) and (D_{5}) is easy. We prove (D_{2}). By Specification 2 and Definition 15 the union of the quasi-components of C′_{1}, …, C′_{e}, D_{1}, …, D_{a}, D′_{1,1}, …, D′_{b,c_{b}} contains W(C). Since either h or h_{C} is zero modulo the saturated ideal of every discarded regular chain, the quasi-component W(C ∪ p) is contained in the union of the quasi-components of the returned regular chains. This proves property (D_{2}). Now we prove (D_{3}). Observe that h_{C} is regular w.r.t. every returned regular chain. Indeed this holds for D_{1} ∪ p, …, D_{a} ∪ p by Proposition 5. This holds also for the regular chains D′_{i,j} ∪ p such that red(h_{C} h, D′_{i,j}) ≠ 0. by Specification 2. Therefore Theorem 23 applies. This proves (D_{3}). Observe that if Algorithm 3 does not return any regular chain, then \overline{W(C)} ⊆ V(h) holds. Hence we have W(C ∪p) = ∅, leading to Sat(C ∪ p) = P_{n}. On the contrary, if Algorithm 3 returns at least one regular chain R, then Sat(C ∪ p) ⊆ Sat(R) holds showing that Sat(C ∪ p) ≠ P_{n}. □

Algorithm 4 generalizes the operation extend to the case where its second argument is a triangular set. This will provide us the tool for lifting computations in the context of Theorem 23. Proposition 28 states that Algorithm 4 terminates and satisfies its specification, provided that its calls to the operation regular? are valid. Proposition 28 follows from Proposition 26 and its proof is not reported here.

Algorithm 4

• Input: C and D as in the statement of Theorem 23 and let p be the element of D with smallest main variable.

• Output: a regular delayed split of C ∪ D.

• extend(C, D) ==

D^{+} := D \ p

for E ∈ extend(C, p) repeat D^{+} = ∅ ⟹ output E for F ∈ extend(E, D^{+}) repeat output F

exit

Hypothesis 27 Let T ⊆ P_{n} be a triangular set and let m be an integer in the range 1 ⋯ m. We denote by H_{2}(T, m) the following hypothesis: for every regular chain R ⊆ P_{m−1} and for every polynomial f ∈ P_{m−1} such that R has no higher rank than T_{x_{m}}^{−}, the call regular?(f, R) satisfies Specification 2.

Proposition 28 Let C and D be as in the input of Algorithm 4. Let m be the smallest index such that C ∪ D ⊆ P_{m} holds. If hypothesis H_{2}(C ∪ D, m) holds then Algorithm 4 terminates and satisfies its output specification. Moreover Sat(C ∪ D) is the unit ideal of P_{n} iff extend(C, D) does not return any regular chain. In addition, for any regular chain R returned by extend(C, D) the product of the initials of C ∪ D is regular w.r.t. R.

When the hypothesis of Proposition 28 is satisfied, we have an algorithm to compute a delayed split of Z(p, T) in the context of Proposition 24. So we consider now the case where the main variable of p is algebraic w.r.t. T. The following concept will be our main tool in this new context.

Definition 29 Let T ⊆ P_{n} be a regular chain. Let k be an integer in the range 0 ⋯ n − 1. Let p and t be two non-constant polynomials in P_{n} with main variable x_{k+1} such that the initial of p is regular w.r.t. T and T ∪ t is a regular chain. Let g be a polynomial in P_{k+1}. We say that g is a regular gcd of the polynomials p and t modulo T if the following conditions hold:

(G_{1}) the leading coefficient of g as a univariate polynomial in P_{k}[x_{k+1}] is reg-

ular w.r.t. T, (G_{2}) there exist polynomials u, v ∈ P_{k+1} such that ut + vp − g ∈ Sat(T)∩P_{k}, (G_{3}) if g ∉ k and mvar(g) = x_{k+1} then both t and p lye in Sat((T ∩ P_{k}) ∪ g).

If g is not constant and has main variable x_{k+1}, then we say that g is a nontrivial regular gcd of p and t modulo T.

Remark 30 Let T, p, t, g be as in Definition 29 such that g is a regular gcd of t and p modulo T. We point out three obvious remarks that are used quite often in practice. First observe that condition (G_{1}) implies g ≠ 0. Secondly, condition (G_{2}) shows that if g ∈ k holds then we have Z({p, t}, T) = ∅. Lastly, condition (G_{3}) implies: rank(g) = rank(t) ⟹ p ∈ Sat(T ∪ t). We prove this statement. We define h = init(t) and h_{g} = init(g). There exist non-negative integers e and e′, polynomials q_{t}, q_{f} ∈ P_{k+1} and polynomials r_{t}, r_{f} ∈ Sat(T) ∩ P_{k} such that h_{g}^{e}t = q_{t}g + r_{t} and h_{g}^{e′}p = q_{p}g + r_{p}. This leads to q_{t}h_{g}^{e′}p = q_{p}h_{g}^{e}t + q_{t}r_{p} − q_{p}r_{t}. Since mdeg(t) = mdeg(g) the relation h_{g}^{e}t = q_{t}g + r_{t} shows that q_{t} ∈ P_{k} holds, which leads to h_{g}^{e}h_{t} = q_{t}h_{g}. Thus q_{t}h_{g}^{e′} is regular w.r.t. T ∩ P_{k}. It follows with relation (3) p. 6 that p lies in Sat((T ∩ P_{k}) ∪ t). Therefore p ∈ Sat(T ∪ t). This last property shows that if mvar(g) = x_{k+1} and p ∉ Sat(T ∪ t) hold then we have mdeg(g) < mdeg(t). Indeed mdeg(g) > mdeg(t) and (G_{3}) implies prem(t, T) = 0 contradicting the fact that h is regular w.r.t. T.

Lemma 31 Let T, p, t, g be as in Definition 29. Assume that p ∉ Sat(T ∪ t) and that g is a non-trivial regular gcd of t and p modulo T. Let h_{g} be the initial of g and q be the pseudo-quotient of t by g. Then T ∪ q is a regular chain with mvar(q) = x_{k+1}. Moreover we have:

(1) W(T ∪ g) ⊆ Z({p, t}, T),

(2) Z(p, T ∪ q) \ V(h_{g}) ⊆ W(T ∪ g).

Proof. By assumption we have mvar(g) = x_{k+1}. Since p ∉ Sat(T ∪ t) holds, Remark 30 implies mdeg(g) < mdeg(t). Hence mvar(q) = x_{k+1} holds. Since the initial of t is regular w.r.t. T, conditions (G_{1}) and (G_{3}) allows us to apply Theorem 7 and we deduce that T ∪ g and T ∪ q are regular chains. Now, let us prove (1). Condition (G_{3}) implies p ∈ Sat(T ∪ g) and t ∈ Sat(T ∪ g). Thus we have V(p)∩V(t) ⊇ \overline{W(T ∪ g)}, proving (1). We prove (2). From condition (G_{2}) there exist polynomials u, v ∈ P_{k+1} and a polynomial r′ ∈ Sat(T) such that g = ut + vp + r′. From condition (G_{3}), there exists a polynomial r′′ ∈ Sat(T) and a non-negative integer m such that h_{g}^{m} t = qg + r′′. Thus we have:

h_{g}^{m} g = u(qg + r′′) + h_{g}^{m}(vp + r′).

Since W(T) ⊆ V(Sat(T)) any point ζ of Z(p, T ∪ q) cancels the right hand side of the above equality and thus belongs to V(h_{g} g), leading to (2). □

Theorem 32 Let T, p, t, g be as in Definition 29. Assume that p ∉ Sat(T ∪ t) and that g is a non-trivial regular gcd of t and p modulo T. Let h_{g} be the initial of g. Then we have:

Z(p, T ∪ t) ⟶_{D} (W(T ∪ g), Z({h_{g}, p}, T ∪ t)). (8)

Proof. Let us prove that properties (D_{1}) to (D_{5}) of Definition 11 hold. Recall that our assumptions imply mvar(g) = mvar(t) and mdeg(g) < mdeg(t). Since g ≺ t and h_{g} ≺ p hold each of the processes [∅, T ∪ g] and [{h_{g}, p}, T ∪ t] has smaller rank than the process [{p}, T ∪ t]. This proves (D_{1}). As in Lemma 31 let q be the pseudo-quotient of t w.r.t. g. From Theorem 7 we know that T ∪ g and T ∪ q are regular chains. Moreover we have:

Z(p, T ∪ t) ⊆ W(T ∪ g) ∪ Z(p, T ∪ q) ∪ Z({h_{g}, p}, T ∪ t).

Indeed Relation (1) of Lemma 31 shows that Z(p, T ∪ g) = W(T ∪ g). Observe that all the points of Z(p, T ∪ t) that cancel h_{g} are already captured by Z({h_{g}, p}, T ∪ t) and we replace the term Z(p, T ∪ q) by Z(p, T ∪ q) \ V(h_{g}) in the above union. Hence with relation (2) of Lemma 31 we obtain (D_{2}). Property (D_{3}) follows from Lemma 6 and properties (D_{4}) and (D_{5}) are clear. □

We will show in Section 5 that there exists an operation called lastSubResultant, denoted for short by lsr and defined in Specification 3. The operation lsr together with Theorems 23 and 32 leads us to a first algorithm for the operation decompose in a restricted case, given below in Algorithm 5. This specialized decompose takes three arguments whereas the general one (Algorithm 7) will only have two, Proposition 34 states that Algorithm 5 terminates and satisfies its specifications provided that its call to regular? and lsr are valid.

Specification 3 Let k be an integer in the range 0 ⋯ n − 1. Let T ⊆ P_{k} be a regular chain. Let p_{1}, p_{2} ∈ P_{k+1} be non-constant polynomials such that mvar(p_{1}) = mvar(p_{2}) = x_{k+1} and mdeg(p_{1}) ≥ mdeg(p_{2}) hold. Assume that init(p_{1}) and init(p_{2}) are regular w.r.t. T. The operation lsr(p_{1}, p_{2}, T) returns a sequence of processes ([g_{1}, C_{1}], … [g_{d}, C_{d}], [∅, D_{1}], … [∅, D_{e}]) of P_{n} where C_{1}, …, C_{d}, D_{1}, …, D_{e} are regular chains of P_{k} and g_{1}, …, g_{d} are polynomials of P_{k+1} satisfying the following conditions:

(L_{1}) T ⟶_{D} (C_{1}, …, C_{d}, D_{1}, …, D_{e}), (L_{2}) for every i = 1 ⋯ d the polynomial g_{i} is a regular gcd of p_{1} and p_{2} modulo

C_{i} and we have dim(C_{i}) = dim(T), (L_{3}) for every j = 1 ⋯ e we have dim(D_{j}) < dim(T).

Algorithm 5

• Input: T, p, t, g be as in Definition 29 such that p ∉ Sat(T ∪ t) and define v = mvar(p).

• Output: a regular delayed split of Z(p, T ∪ t).

• decompose(p, T, t) ==

Let h_{v}^{−} be the product of the initials of T_{v}^{−}

if mdeg(p) < mdeg(t) then (p_{1}, p_{2}) := (t, p) else (p_{1}, p_{2}) := (p, t)

for [G, C] ∈ lsr(p_{1}, p_{2}, T_{v}^{−}) repeat G = ∅ ⟹

for D ∈ extend(C, T_{v}^{+} ∪ h_{v}^{−}t) repeat output [p, D] {g} := G g ∈ k ⟹ iterate mvar(g) < v ⟹ output [{g, p}, C ∪ t ∪ T_{v}^{+}] mdeg(g) = mdeg(t) ⟹ output [∅, C ∪ t ∪ T_{v}^{+}] output [∅, C ∪ g ∪ T_{v}^{+}] output [{init(g), p}, C ∪ t ∪ T_{v}^{+}]

exit

Hypothesis 33 Let T ⊆ P_{n} be a triangular set and let m be an integer in the range 1 ⋯ n. We denote by H_{3}(T, m) the following hypothesis: for every regular chain R ⊆ P_{m−1} with no higher rank than T_{x_{m}}^{−}, every call to lsr with R as third argument satisfies Specification 3.

Proposition 34 Let T, p, t be as in the input of Algorithm 5. Let m be the smallest index such that T ∪ t ⊆ P_{m} holds. If hypothesis H_{2}(T ∪ t, m) and H_{3}(T ∪ t, m) hold then Algorithm 5 terminates and satisfies its specification. Moreover for every process [F, R] returned by decompose(p, T, t) such that dim(R) < dim(T ∪ t) holds we have F ≠ ∅.

Proof. We assume that H_{2}(T ∪ t, m) and H_{3}(T ∪ t, m) hold. Let h be the initial of t. First we prove that the calls to the operations lsr and extend satisfy Specification 3 and the specifications of Algorithm 4 respectively. This implies immediately that Algorithm 5 terminates. Since T_{v}^{−} ⊆ P_{m−1} holds the call lsr(p_{1}, p_{2}, T_{v}^{−}) satisfies Specification 3. Hence every regular chain C computed by lsr(p_{1}, p_{2}, T_{v}^{−}) has no higher rank than T_{v}^{−}. By Proposition 28 it follows that extend(C, T_{v}^{+} ∪ h_{v}^{−}t) returns a regular delayed split (D_{1}, …, D_{e}) of C ∪ T_{v}^{+} ∪ h_{v}^{−}t such that h_{v}^{−} h is regular modulo D_{i} for every i = 1 ⋯ e. This proves our claim. Now we show that Algorithm 5 is correct. First we assume T_{v}^{+} = ∅. We claim that in this case Algorithm 5 returns a regular delayed split of Z(p, T ∪ h_{v}^{−}t). To see this let (C_{1}, …, C_{d}, C′_{1}, …, C′_{e}) be the regular delayed split of T_{v}^{−} returned by lsr(p_{1}, p_{2}, T_{v}^{−}) such that for every i = 1 ⋯ d we have dim(C_{i}) < dim( T_{v}^{−}) and for every j = 1 ⋯ e we have dim(C′_{j}) = dim( T_{v}^{−}). Note that the second for loop computes for i = 1 ⋯ d a regular delayed split (possibly empty) of C_{i} ∪ h_{v}^{−}t. By Proposition 5, for j = 1 ⋯ e the triangular set C′_{j} ∪ h_{v}^{−}t is a regular chain. Then, by applying the formulas of Remark 30 and Theorem 32 we complete easily the proof of our claim. We return now to the case where T_{v}^{+} may not be empty. Since h_{v}^{−} h is regular w.r.t. every returned set, it suffices to apply Theorem 23. □

We are now ready to state an algorithm for the operation decompose in the general case. It consists essentially in a preparation phase by means of the operation regularizeInitial defined in Algorithm 6 so that we can apply either Proposition 24 (the non-algebraic case) or Proposition 34 (the algebraic case).

Algorithm 6

• Input: f ∈ P_{n} a polynomial and C ⊆ P_{n} a regular chain.

• Output: a regular delayed split (C_{1}, …, C_{d}) of C such that the polynomial red(f, C_{i}) is either null or regular w.r.t. C_{i}, for every i = 1 ⋯ d.

• regularizeInitial(f, C) ==

f := red(f, C) R := [[f, C]] # R is a list of processes while R ≠ [ ] repeat

choose and remove a process [f, C] from R

f ∈ k ⟹ output C

for D ∈ regular?(init(f), C) repeat red(init(f), D) ≠ 0 ⟹ output D R := cons([red(tail(f), D), D])

exit

Proposition 35 Let C and f be as in the input of Algorithm 6. If hypothesis H_{1}(C, f) holds then Algorithm 6 terminates and satisfies its specification.

Algorithm 7

• Input: T regular chain of P_{n} and p ∈ P_{n} such that p ∉ k and p ∉ Sat(T).

• Output: a regular delayed split of Z(p, T).

• decompose(p, T) ==

for C ∈ regularizeInitial(p, T) repeat f := red(p, C) f = 0 ⟹ output [∅, C] f ∈ k ⟹ iterate v := mvar(f) v ∉ alg(C) ⟹

output [{init(f), p}, C]
for D ∈ extend( C_{v}^{−} ∪ f, C_{v}^{+}) repeat output [∅, D]

for [F, E] ∈ decompose(f, C_{v}^{−} ∪ C_{v}^{+}, C_{v}) repeat output [F · p, E] exit

Proposition 36 Let T and p be as in the input specification of Algorithm 7. Let m be the smallest index such that T ⊆ P_{m} holds. If hypothesis H_{1}(T, p), H_{2}(T, m) and H_{3}(T, m) hold then Algorithm 7 terminates and satisfies its specification. Moreover for every process [F, R] returned by decompose(p, T) such that dim(R) < dim(T ∪ t) holds we have F ≠ ∅.

Proof. We assume that H_{1}(T, p), H_{2}(T, m) and H_{3}(T, m) hold. Since H_{1}(T, p) holds, it follows from Proposition 35 that regularizeInitial(p, T) returns a regular delayed split of T. We claim that for each regular chain C produced by regularizeInitial(p, T) the corresponding iteration of the for loop returns either C or a regular delayed split of Z(p, C). Therefore the correctness of the whole algorithm follows from Proposition 22. Let us prove this claim. So let C be a regular chain produced by regularizeInitial(p, T). Recall that C has not higher rank than T. As in Algorithm 7 we put f = red(p, C). If f = 0 or f ∈ k, the conclusion is clear. Let v = mvar(f). Note that init(f) is regular w.r.t. C. Moreover C_{v}^{−} has not higher rank than T_{v}^{−}. First assume that v ∉ alg(C). Since H_{2}(T, m) holds we can apply Proposition 28. Then the conclusion follows from Proposition 24. Now Assume v ∈ alg(C). Since H_{2}(T, m) and H_{3}(T, m) hold we can apply Proposition 34. This proves our above claim. Finally we observe that the last statement of Proposition 34 is clear. □

5 Computations Modulo Regular Chains

The goal of this section is to establish algorithms for the operations regular? and lastSubResultant introduced in Specifications 2 and 3 respectively. For the latter operation we will rely on subresultant theory. We start this section by a brief review of this subject and refer to [Loo82,Duc00] for more details.

Let A be an integral domain. For p_{1} ∈ A[X] with p_{1} ≠ 0 we denote by lc(p_{1}) and deg(p_{1}) the leading coefficient and the degree of p_{1}. If deg(p_{1}) > 0, for p_{2} ∈ A[X] we denote by prem(p_{1}, p_{2}) the pseudo-remainder of p_{1} by p_{2}. From now on we assume that p_{1} and p_{2} have positive degrees d_{1} and d_{2} such that d_{1} ≥ d_{2}. Recall that for j = 0 ⋯ d_{2} the j-th subresultant S_{j} of p_{1} and p_{2} lies in A[X] and that it is either null or satisfies deg(S_{j}) ≤ j; we say that S_{j} is regular if deg(S_{j}) = j. Let S be a non-zero subresultant of p_{1} and p_{2} with degree d < d_{2}. From the Block Structure Theorem of subresultants [Loo82] there exist at most two subresultants with the same degree d: that with biggest index is denoted by S^{+} and that with smallest index is denoted by S^{−}. Moreover S^{−} is regular. We denote by S^{<} (resp. S^{>}) the non-zero subresultant S_{k} with biggest (resp. smallest) index k whose degree is strictly less (resp. greater) than d. The non-zero subresultant of p_{1} and p_{2} with smallest index is denoted by lsr(p_{1}, p_{2}) and called the last-subresultant of p_{1} and p_{2}. If S_{ℓ} is the last-subresultant of p_{1} and p_{2}, the subresultant S_{ℓ}^{+} is denoted by srgcd(p_{1}, p_{2}) and called the subresultant-gcd of p_{1} and p_{2}. If lsr(p_{1}, p_{2}) has degree zero, then it is the resultant of p_{1} and p_{2}. We will use the following fact. The polynomial lsr(p_{1}, p_{2}) lies in the ideal generated by p_{1} and p_{2} in A[X]. Moreover p_{1} and p_{2} reduces to zero w.r.t. lsr(p_{1}, p_{2}) by pseudo-division. Let S be a non-zero subresultant of p_{1} and p_{2} with degree d < d_{2} and such that S = S^{+}. If S^{>} has degree d_{2} we define s = lc(p_{1})^{δ} where δ = d_{1} − d_{2} otherwise we define s = lc(S^{>}). The Block Structure Theorem implies the following properties. First, one can compute the subresultant S^{−} from S^{>}, S^{+} and s. Secondly, one can compute the subresultant S^{<} from S^{>}, S^{+}, S^{−} and s. This allows us to define a next-subresultant operation denoted by nsr and defined by nsr(S^{>}, S^{+}, s) = S^{−} and nsr(S^{>}, S^{+}, S^{−}, s) = S^{<}. We will use the following facts. Computing nsr(p_{1}, p_{2}, s) only requires multiplications by lc(p_{2}) and exact divisions by s. The only exact divisions involved in nsr(p_{1}, p_{2}, p_{3}, s) are by lc(p_{1}), lc(p_{2}) and s. Finally lsr(p_{1}, p_{2}) can be computed as follows:

Algorithm 8

• Input: p_{1}, p_{2} ∈ A[X] with deg(p_{1}) ≥ deg(p_{2}) > 0.

• Output: The last-subresultant of p_{1} and p_{2}.

• lsr(p_{1}, p_{2}) ==

δ := deg(p_{1}) − deg(p_{2})

s := lc(p_{2})^{δ}

(p_{1}, p_{2}) := (p_{2}, prem(p_{1}, −p_{2}))

repeat p_{2} = 0 ⟹ return p_{1} p_{3} := nsr(p_{1}, p_{2}, s) deg(p_{3}) = 0 ⟹ return p_{3} (p_{1}, p_{2}) := (p_{3}, nsr(p_{1}, p_{2}, p_{3}, s)) s := lc(p_{1})

Let T, p_{1}, p_{2} and k be as in Specification 3. Let a = p_{1} and b = p_{2}. Assume that H_{2}(T, k + 1) holds. We shall adapt Algorithm 8 in order to compute lsr(p_{1}, p_{2}, T). We proceed by induction on the rank of the process [{p_{1}, p_{2}}, T].

A first step is modify in Algorithm 8 as follows. First, we replace the test p_{2} = 0 by red(p_{2}, T) = 0. Secondly, we insert between the first and the second lines of the repeat loop the following: if lc(p_{2}, v) is not regular w.r.t. T then error. Indeed, since H_{2}(T, k+1) holds we can check whether lc(p_{2}, v) is regular or not w.r.t. T. Assume now that this modified algorithm terminates without producing an error. Then we return either [p_{1}, T] (if red(p_{2}, T) = 0 holds) or [p_{3}, T] (if deg(p_{3}, v) = 0). Observe that these returned values satisfy property (G_{1}) of Definition 29. Indeed, the leading coefficients w.r.t. v of the successive subresultants have been proved to be regular w.r.t. T. For the same reason every exact division performed by the algorithm is well defined modulo Sat(T). Now observe that the fact that lsr(p_{1}, p_{2}) lies in the ideal generated by p_{1} and p_{2} comes from a manipulation of determinants (that only requires commutativity for the coefficient ring). Therefore, even if Sat(T) is not prime, our returned values satisfy property (G_{2}). Finally property (G_{3}) holds because lsr(p_{1}, p_{2}) pseudo-divides p_{1} and p_{2}, provided that this pseudo-division is well defined, which is the case. It follows that we have proved Algorithm 9 in the case where at each iteration either lc(p_{2}, v) is regular w.r.t. T or p_{2} is null modulo Sat(T).

Algorithm 9

• Input: see Specification 3.

• Output: see Specification 3.

• lsr(p_{1}, p_{2}, T) ==

v := mvar(p_{1})

δ := mdeg(p_{1}) − mdeg(p_{2})

s := init(p_{2})^{δ}

(p_{1}, p_{2}) := (p_{2}, prem(p_{1}, −p_{2}))

R := [T] repeat R′ := [ ] for C ∈ R repeat

for D ∈ regularizeInitial(p_{2} v, C) repeat dim(D) < dim(C) ⟹ output [∅, D] red(p_{2}, D) = 0 ⟹ output [p_{1}, D] red(lc(p_{2}, v), D) ≠ 0 ⟹ R′ := cons(D, R′) deg(red(p_{2}, D), v) = 0 ⟹ output [red(p_{2}, D), D] for [G, E] ∈ lsr(p_{1}, red(p_{2}, D), D) repeat output [G, E]

R′ = [ ] ⟹ exit p_{3} := nsr(p_{1}, p_{2}, s) deg(p_{3}, v) = 0 ⟹

for C ∈ R′ repeat output [p_{3}, C] exit

(p_{1}, p_{2}) := (p_{3}, nsr(p_{1}, p_{2}, p_{3}, s))

s := init(p_{1}) R := R′

The variable R of Algorithm 9 is a list of regular chains whose initial value is [T]. Then the call regularizeInitial(p_{2} v, C) may split C and lead to new cases. Some of these cases are treated directly inside the second for loop, possibly by means of a recursive call to lsr. The others are delayed by inserting the corresponding regular chains into R. Observe that the multiplication of p_{2} by v = x_{k+1} in the call regularizeInitial(p_{2} v, C) is just a trick in order to avoid the distinction between the cases deg(p_{2}, v) = 0 and deg(p_{2}, v) > 0. Because of the composition property of Proposition 22 we only need to check the second for loop. Once this is done we will have proved Proposition 37. For every regular chain D returned by regularizeInitial(p_{2} v, C) five cases arise.

(1) dim(D) < dim(C). We return [∅, D] as expected in Specification 3.

(2) red(p_{2}, D) = 0. We return [p_{1}, D]. Indeed, since dim(D) = dim(C), all our arguments for the Algorithm 8 with error apply.

(3) red(lc(p_{2}, v), D) ≠ 0. Since dim(D) = dim(C), we can continue the computations as if they were started w.r.t. D.

(4) deg(red(p_{2}, D), v) = 0. Since dim(D) = dim(C), we could have followed the computations as if they were started w.r.t. D. Since red(p_{2}, D) is regular w.r.t. D and has degree 0 w.r.t. v, we return [red(p_{2}, D), D].

(5) red(lc(p_{2}, v), D) = 0 but deg(red(p_{2}, D), v) > 0. This implies that init(p_{2}) reduces to zero w.r.t. D. Therefore our induction hypothesis applies. Since init(p_{1}) is regular w.r.t. D, the recursive call lsr(p_{1}, red(p_{2}, D), D) is valid. Since each regular subresultant S of the input polynomials a and b lies in the ideal they generate, each value returned by lsr(p_{1}, red(p_{2}, D), D) is a correct result for the starting call lsr(a, b, T).

Proposition 37 Let T, p_{1}, p_{2} be as above. If H_{2}(T, k + 1) holds then Algorithm 9 terminates and satisfies its specification. Moreover H_{3}(T, k +1) holds.

Let p ∈ P_{n} be a polynomial and T ⊆ P_{n} be a regular chain. Let m be the smallest integer in the range 1 ⋯ n such that T ⊆ P_{m} holds. We assume that H_{1}(T, p) and H_{2}(T, m) hold. We shall prove that regular?(p, T) defined in Algorithm 10 below satisfies its output specification.

Since H_{1}(T, p) holds Proposition 35 applies. Hence regularizeInitial(p, T) returns a regular delayed split (C_{1}, …, C_{d}) of T such that either red(p, C_{i}) lies in k or its initial is regular w.r.t. C_{i}. By Proposition 22 it suffices to prove that for every C = C_{1}, …, C_{d} the corresponding iteration of the for loop satisfies the output specification of regular?(p, C). The case where red(p, C) lies in k or its main variable variable v is not algebraic w.r.t. C is easy to check. So we assume that v ∈ alg(C) holds. Since H_{2}(T, m) holds Proposition 37 applies. In particular the call lsr(p_{1}, p_{2}, C_{v}^{−}) generates a regular delayed split of C_{v}^{−}.

For each of the above cases, if there is a recursive call to regular? we show that it satisfies its output specification (i.e. using hypothesis H_{1}(T, p)) otherwise we show that the desired result is obtained directly without any recursive call.

(1) G = ∅. Since H_{2}(T, m) holds, extend(D, ht ∪ C_{v}^{+}) returns a regular delayed split of D ∪ ht ∪ C_{v}^{+}, by Proposition 28. Each regular chain E of this split has no higher rank than D ∪ ht ∪ C_{v}^{+}. Moreover we have either D ≺ C_{v}^{−} or D ∼ C_{v}^{−}. But the latter would imply dim(D) = dim( C_{v}^{−}), a contradiction with G = ∅. Since C = C_{v}^{−} ∪ t ∪ C_{v}^{+}, we obtain E ≺ C. With hypothesis H_{1}(T, p), since C has no higher rank than T, it follows that the recursive call regular?(q, E) is valid. Note that in order to apply Theorem 23 the multiplication by h in extend(D, ht ∪ C_{v}^{+}) is needed.

(2) (g ∈ k) or (mvar(g) < v). Recall that we have Sat(D) ⊆ Sat( C_{v}^{−}). Since dim(D) = dim( C_{v}^{−}) holds, D ∪ t ∪ C_{v}^{+} is a regular chain. Since p equals red(p, C) modulo Sat(C), this equality holds also modulo Sat(D ∪ t). Then, by condition (G_{2}) of Definition 29, there exist polynomials u, u ∈ P_{k+1} such that up = vt + g holds modulo Sat(D). Now, by condition (G_{1}), the polynomial g is regular w.r.t. D and thus w.r.t. D ∪t. It follows that p is regular w.r.t. D ∪ t ∪ C_{v}^{+} and that this regular chain must be

returned. Observe that h is regular w.r.t the output regular chain.

(3) mvar(g) = x_{k+1} and mdeg(g) = mdeg(t). By Remark 30 we have p ∈ Sat(D ∪ t). Thus D ∪ t ∪ C_{v}^{+} must be returned by the algorithm.

(4) mvar(g) = x_{k+1} and mdeg(g) ≠ mdeg(t). We have mdeg(g) < mdeg(t), by Remark 30. Hence we apply Theorem 7 and its Corollary 8. We use the operation intersect specified in Remark 20 and consequently the operation decompose from Specification 1. By Theorem 7 the sets D ∪ g ∪ C_{v}^{+} and D ∪ f ∪ C_{v}^{+} are regular chains. Moreover, the polynomial h is regular w.r.t. them. By condition (G_{3}), the polynomial p reduces to zero w.r.t. D ∪ g ∪ C_{v}^{+} and this set must be returned by the algorithm. Since D ∪ f ∪ C_{v}^{+} ≺ C. holds, the recursive call regular?(q, D ∪ f ∪ C_{v}^{+}) is valid. We put h_{g} = init(g). Since H_{2}(T, k + 1) holds, Proposition 36 applies. Hence intersect(h_{g}, D ∪ t ∪ C_{v}^{+}) returns a delayed split of Z(h_{g}, D∪ t ∪ C_{v}^{+}) consisting of regular chains. Let E be one of them. By Proposition 16, since h_{g} is regular w.r.t. D ∪ t ∪ C_{v}^{+}, we have dim(E) < dim(C). Hence E ≺ C holds and the last recursive call is valid too.

Algorithm 10

• Input: T regular chain of P_{n} and p ∈ P_{n}.

• Output: a regular delayed split (T_{1}, … T_{d}) of T such that if red(p, T_{i}) ≠ 0 then p is regular w.r.t. T_{i}, for every i = 1 ⋯ d.

• regular?(p, T) ==

for C ∈ regularizeInitial(p, T) repeat q := red(p, C) q ∈ k ⟹ output C v := mvar(q) v ∉ alg(C) ⟹ output C t := C_{v} if mdeg(t) ≤ mdeg(q) then (p_{1}, p_{2}) := (q, t) else (p_{1}, p_{2}) := (t, q) Let h be the product of the initials of C_{v}^{−} for [G, D] ∈ lsr(p_{1}, p_{2}, C_{v}^{−}) repeat

G = ∅ ⟹

for E ∈ extend(D, ht ∪ C_{v}^{+}) repeat

for H ∈ regular?(q, E) repeat output H {g} := G (g ∈ k) or (mvar(g) < v) ⟹ output D ∪ t ∪ C_{v}^{+} mdeg(g) = mdeg(t) ⟹ output D ∪ t ∪ C_{v}^{+} f := pquo(t, g) output D ∪ g ∪ C_{v}^{+} for E ∈ regular?(q, D ∪ f ∪ C_{v}^{+}) repeat output E for E ∈ intersect(init(g), D ∪ t ∪ C_{v}^{+}) repeat for H ∈ regular?(q, E) repeat output H

exit Theorem 38 Alorithm 10 terminates and satisfies its specification.

Proof. Following the above discussion, the only remaining point to prove is that Algorithm 10 terminates. Let us consider the ordered tree T of the recursive calls to regular? (possibly via the other operations) required to compute regular?(p, T). We know if H_{1}(T, p) and H_{2}(T, m) hold then regular?(p, T) can be computed. Hence for each recursive call regular?(p′, T′) we have either [p′, T′] ≺ [p, T] or the greatest variable occuring in T′ is strictly smaller than that of T. Hence T is finite. Finally it is easy to check than when no call to regular? is needed, each of our algorithms satisfies its specification. □

Corollary 39 Algorithms 2, 3, 4, 6, 5, 7, and 9 terminate and satisfy their specifications.

6 Improvements

We give several improvements for the algorithms of the previous sections. Then we show how to use them for producing decompositions into normalized and square-free regular chains, and for removing redundant quasi-components. In particular we explain how to compute the decompositions of Lazard’s algorithm [Laz91]. Finally we adapt our algorithms in order to compute efficiently the decompositions of Kalkbrener [Kal91].

Clearly, the operation regular? is called intensively by our algorithms. Let p ∈ P_{n} be a polynomial and T ⊆ P_{n} be a regular chain. Here are some tricks in order to speed up the computation of regular?(p, T) and to reduce the number of recursive calls. First, if p is normalized w.r.t. T or if Sat(T) is a prime ideal then regular?(p, T) is simply (T). Consider now the call to intersect in our Algorithm 10. Let h_{g} be the initial of g. Assume that T is purely algebraic. Assume also that every variable occuring in h_{g} is algebraic w.r.t. D ∪ t ∪ C_{v}^{+}. Then Z(h_{g}, D ∪ t ∪ C_{v}^{+}) is necessarily empty, by virtue of Proposition 16. This trick applies very often in practice and provides a great speed up. Consider now the case where the previous trick does not work. Let h_{t} and h_{q} be the initials of t and q. Let γ be the gcd of h_{t} and h_{q} as multivariate polynomials of P_{k}. Assume that g is the subresultant-gcd of t and q regarded as univariate polynomials in x_{k+1}. Then h_{g} divides γg and again Z(h_{g}, D ∪ t ∪ C_{v}^{+}) is necessarily empty. This is a very powerful trick.

We give now some tricks in order to improve the operation lsr. Let p_{1}, p_{2}, and T be as Algorithm 9. If T is purely algebraic and if the coefficients of p_{1} and p_{2} (regarded as univariate polynomials) are algebraic w.r.t. T, then we can use the algorithm given in [MR95]. Furthermore, if Sat(T) is prime, we can use a modular algorithm for computing polynomial gcds [LM89,Enc94].

Several of our algorithms are simpler if their input polynomials or regular chains are normalized. Let T ⊆ P_{n} be a regular chain. If the polynomial p ∈ P_{n} is normalized w.r.t. T then regularizeInitial(p, T) returns simply (T). In the same way, if p ∈ P_{n} is normalized w.r.t. T (and mvar(p) is greater than any variable of T) then extend(p, T) returns simply (T ∪ p).

We explain now how we compute a delayed split of T by means of normalized regular chains. We proceed by induction on the rank of the greatest variable occuring in T. Assume that T writes N ∪ t where N is a normalized regular chain and t is a polynomial regular w.r.t. N with main variable greater than any variable of N. By repeated calls to the operation lsr, computing the Bézout coefficients given by property (G_{2}) of Definition 29, we can compute a sequence of processes ([q_{1}, M_{1}], …, [q_{e}, M_{e}]) with the following properties. First (M_{1} ∪ t, …, M_{e} ∪ t) is a regular delayed split of N ∪ t where each M_{i} is normalized. Secondly, each polynomial red(q_{i} t, M_{i}) is not constant, normalized w.r.t. M_{i} and has the same rank as t. Clearly every set M_{i} ∪red(q_{i} t, M_{i}) is a normalized regular chain and is part of the desired delayed split of N ∪ t. In order to apply formula (c) of Lemma 4 we need to compute intersect(q_{i}, M_{i}) for every i = 1 ⋯ e, obtaining regular chains M_{i,j}. Then we call extend(M_{i,j}, t) since t may not be regular w.r.t. M_{i,j} and obtain regular chains M_{i,j,l} to which we apply recursively our normalization procedure. The whole normalization procedure terminates since the call intersect(q_{i}, M_{i}) returns regular chains M_{i,j} such that dim(M_{i,j}) < dim(M_{i}) holds. Indeed q_{i} is regular w.r.t. M_{i}.

Several of our algorithms are also simpler if the input regular chain T is square-free. In this case, Sat(T) is radical. See Proposition V.1 in [Mor97]. This has several advantages. First, this is crucial for deciding whether a quasicomponent is contained in another as we shall below. Secondly, this clearly reduces the size of the computed objects and increases the legibility of the output. Lastly, this allows an improvement of Algorithm 10 as follows. Assume that we are considering the case mvar(g) = mvar(t) and mdeg(g) < mdeg(t) in Algorithm 10. If t is known to be square-free w.r.t. D, then the polynomials g and f are relatively prime modulo Sat(D). Recall that p reduces to zero modulo D ∪ g. Then p must be regular w.r.t. D ∪ f. Hence we can avoid the second recursive call in Algorithm 10 and return directly D ∪ f ∪ C_{v}^{+}. The production of square-free regular chains is similar to that of normalized triangular sets and we do not detail this point.

Let T_{1} and T_{2} be two regular chains of P_{n}. We want to decide whether W(T_{1}) ⊆ W(T_{2}) holds. If T_{1} and T_{2} are square-free normalized triangular sets, one can use the procedure subQuasiComponent? of [Mor97]. We discuss here the general case, for which we provide several criteria. Indeed we do not know a decision algorithm in the general case. However these criteria are powerful enough in practice, especially if T_{1} and T_{2} are square-free. Let h_{2} be the product of the initials of T_{2}. If h_{2} ∈ k then W(T_{2}) = V(T_{2}). Thus W(T_{1}) ⊆ W(T_{2}) and \overline{W(T_{1})} ⊆ \overline{W(T_{2})} are equivalent. Thus if T_{2} ⊆ Sat(T_{1}) holds, we can answer yes otherwise we cannot conclude. Clearly, the chain T_{1} should better be square-free. If h_{2} ∉ k then we need to add another condition. First we can test intersect(h_{2}, T_{1}) = ∅ (together with T_{2} ⊆ Sat(T_{1})) and answer yes if this holds. Secondly we can refine this idea by computing regular?(h_{2}, T_{1}) = (R_{1}, …, R_{d}). Then, for every R_{i} such that red(h_{2}, R_{i}) ≠ 0 and such that intersect(h_{2}, R_{i}) ≠ ∅ together with T_{2} ⊆ Sat(R_{i}) we answer yes.

A direct application of our procedures to decide whether a quasi-component is contained in another is the management of the processes. This task has to be realized by Algorithm 2. We use its notations. Recall that the idea is to produce the regular chains in the output of solve(F) in order of decreasing dimension such that the redundant quasi-components can be removed as soon as possible. Hence, among all the processes in R one must chose a process [F_{1}, U_{1}] such that dim(U_{1}) is maximal. Then we must refine this choice by avoiding the process [F_{1}, U_{1}] such that F_{1} contains polynomials which have been proved to be regular w.r.t. U_{1}. When decompose(p, U_{1}) has returned a delayed split of Z(p, U_{1}) we must perform several cleanings. First, for a given process [F_{1}, U_{1}], we can remove from F_{1} any polynomial f such that red(f, U_{1}) = 0 holds. Indeed any regular chain C generated by this process satisfies Sat(U_{1}) ⊆ Sat(C) and thus red(f, C) = 0. Secondly, we can remove from R every process [F_{1}, U_{1}] such that there exists a computed regular chain R (part of the output) satisfying Z(F_{1}, U_{1}) ⊆ W(R). Lastly, we can compare the processes of R between them. All these cleanings leave the loop invariants of the proof of Proposition 19 unchanged.

It follows that we have provided all the tools in order to compute a Lazard split of V(F) by means of Lazard’s sets (i.e. square-free normalized triangular sets) such no output quasi-component is contained in another one.

If Algorithm 2 is used for computing a Kalkbrener split of a given algebraic variety V(F), redundant components may appear. More precisely this split may contain two regular chains T and T′ such that \overline{W(T)} ⊆ \overline{W(T′)} holds, even if W(T) ⊆ W(T′) does not hold. This is essentially due to Theorem 7. Here are some tricks to reduce these redundancies in a significant manner.

Since the height of the saturated ideal of a regular chain equals the number of its elements, we can delete any process [F_{1}, T_{1}] of Algorithm 2 such that T_{1} contains more elements than the input system F. In fact we can do more as follows. Let T be a regular chain containing as many elements as F. Let p be in P_{n} and [F_{i}, T_{i}] be a process returned by decompose(p, T) such that F_{i} ≠ ∅ holds. Then we can discard [F_{i}, T_{i}] from the output of decompose(p, T).

Indeed there exists f_{i} ∈ F_{i} such that f_{i} is regular w.r.t. T_{i}. Observe also that during the computation of decompose(p, T) we should never perform the case G = ∅ in Algorithm 5 and the case v ∉ alg(C) in Algorithm 7, since they will generate regular chains D such that dim(D) < dim(T). See Table 6 in [AM99] for experimental results.

Acknowledgements

– First, I would like to thank Fanou Etienne. Her affection created the environment which permited this research.

– I am grateful to François Boulier, François Lemaire and Michel Petitot. Without their cooperation and encouragements, this paper would probably not have been finished in a reasonable time. Many thanks also for their comments on preliminary versions of this paper.

– I would like to thank the referees for their careful work and many constructive suggestions.

– I would like to thank James Davenport, Laureano González Vega and Tomas Recio for many interesting discussions and their support.

– I would like to thank Philippe Aubry and Daniel Lazard for many helpful discussions during my PhD Thesis at the University Paris 6.

– I would like to thank Themos Tsikas for his advice in the AXIOM implementation of the algorithm presented in this paper.

– I am also grateful to NAG Ltd and the European research project FRISCO 2 for supporting this work.

References

[ALM99] P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets. J. Symb. Comp., 28(1-2):105–124, 1999.

[AM99] P. Aubry and M. Moreno Maza. Triangular sets for solving polynomial systems: A comparative implementation of four methods. J. Symb. Comp., 28(1-2):125–154, 1999.

[Aub99] P. Aubry. Ensembles triangulaires de polynômes et résolution des systèmes d’équations algébriques. PhD thesis, Université Paris 6, 1999.

[BDI^{+}94] Peter A. Broadbery, Samuel S. Dooley, Pietro Iglio, Scott C. Morisson, Jonathan M. Steinbach, Robert S. Sutor, and Stephen M. Watt. AXIOM Library Compiler User Guide. NAG, The Numerical Algorithms Group

2 A Framework for Integrated Symbolic/Numeric Computation. Esprit Scheme Project No. 21 024 Limited, Oxford, United Kingdom, 1st edition, November 1994. AXIOM is a registred trade mark of NAG.

[BL00] F. Boulier and F. Lemaire. Computing canonical representatives of regular differential ideals. In proceedings of ISSAC 2000, pages 37–46, St Andrews, Scotland, 2000. ACM Press.

[BLOP95] F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Representation for the radical of a finitely generated differential ideal. In proceedings of ISSAC’95, pages 158–166, Montréal, Canada, 1995.

[Del99] S. Dellière. Triangularisation de systèmes constructibles. Application à l’évaluation dynamique. PhD thesis, Université de Limoges, 1999.

[Duc00] L. Ducos. Optimizations of the subresultant algorithm. Journal of Pure and Applied Algebra, 145:149–163, 2000.

[EM99] I.Z. Emiris and B. Mourrain. Matrices in elimination theory. J. Symb. Comp., 28(1-2):3–44, 1999.

[Enc94] Mark J. Encarnación. On a modular algorithm for computing gcds of polynomials over algebraic number fields. In Proc. ISSAC’94, pages 58– 65. ACM Press, 1994.

[Góm94] T. Gómez Díaz. Quelques applications de l’évaluation dynamique. PhD thesis, Université de Limoges, 1994.

[GPS98] G.-M. Greuel, G. Pfister, and H. Schönemann. Singular vers. 1.2 User Manual. In Reports On Computer Algebra, number 21. Centre for Computer Algebra, University of Kaiserslautern, June 1998.

[Hub00] É. Hubert. Factorization free decomposition algorithms in differential algebra. J. Symb. Comp., 29(4-5):641–662, 2000.

[JS92] R. D. Jenks and R. S. Sutor. AXIOM, The Scientific Computation System. Springer-Verlag, 1992. AXIOM is a trade mark of NAG Ltd, Oxford UK.

[Kal91] M. Kalkbrener. Three contributions to elimination theory. PhD thesis, Johannes Kepler University, Linz, 1991.

[Kal93] M. Kalkbrener. A generalized euclidean algorithm for computing triangular representations of algebraic varieties. J. Symb. Comp., 15:143–167, 1993.

[Kal98] M. Kalkbrener. Algorithmic properties of polynomial rings. J. Symb. Comp., 26(5):525–581, 1998.

[Laz91] D. Lazard. A new method for solving algebraic systems of positive dimension. Discr. App. Math, 33:147–160, 1991.

[Li95] Z. Li. An implementation of the characteristic set method for solving algebraic equations. In Proc. POSSO Workshop, pages 107–122, 1995.

[LM89] L. Langemyr and S. McCallum. The computation of polynomial greatest common divisors over an algebraic number field. J. Symbolic Comp, 8:429– 448, 1989.

[Loo82] R. Loos. Generalized polynomial remainder sequences. In Symbolic and Algebraic Computation, pages 115–137. Spinger-Verlag, 1982.

[Mis93] B. Mishra. Algorithmic Algebra. Springer-Verlag, New Yor, 1993.

[Mor97] M. Moreno Maza. Calculs de Pgcd au-dessus des Tours d’Extensions Simples et Résolution des Systèmes d’Équations Algébriques. PhD thesis, Université Paris 6, 1997.

[MR95] M. Moreno Maza and R. Rioboo. Polynomial gcd computations over towers of algebraic extensions. In Proc. AAECC-11, pages 365–382. Springer, 1995.

[Oll90] F. Ollivier. Le problème de l’identifiabilité structurelle globale : approche théorique, méthodes effectives et bornes de complexité. PhD thesis, École Polytechnique, 1990.

[Rit32] J. F. Ritt. Differential Equations from an Algebraic Standpoint, volume 14. American Mathematical Society, New York, 1932.

[Rit50] J. F. Ritt. Differential Algebra. Amer. Math. Soc, New York, 1950.

[Ros59] A. Rosenfeld. Specializations in differential algebra. Trans. Amer. Math. Soc., 90:394–407, 1959.

[Sei56] A. Seidenberg. Some remarks on Hilbert’s Nullstellensatz. Archiv der Mathematik, 7:235–240, 1956.

[SZ67] P. Samuel and O. Zariski. Commutative algebra. D. Van Nostrand Company, INC., 1967.

[Szá99] Á. Szántó. Computation with polynomial systems. PhD thesis, Cornell University, 1999.

[van91] B.L. van der Waerden. Algebra. Springer-Verlag, 1991. seventh edition.

[Wan93] D. M. Wang. An elimination method for polynomial systems. J. Symb. Comp., 16:83–114, 1993.

[Wan98] D. M. Wang. Decomposing polynomial systems into simple systems. J. Symb. Comp., 25(3):295–314, 1998.

[Wan99] D. M. Wang. Decomposing algebraic varieties. In D. Wang X.-S. Gao and L. Yang, editors, Automated Deduction in Geometry, number LNAI 1669, pages 180–206. Springer-Verlag, Berlin Heidelberg, 1999.

[Wan00] D. M. Wang. Elimination Methods. Springer, Wein, New York, 2000.

[Wu86] W. T. Wu. On zeros of algebraic equations – an application of Ritt principle. Kexue Tongbao, 31(1):1–5, 1986.