J. Symbolic Computation (1998) 11, 1–20

On the Theories of Triangular Sets

PHILIPPE AUBRY^{†}, DANIEL LAZARD^{†} AND MARC MORENO MAZA^{†‡}

†LIP6, Université Paris 6, 4 Place Jussieu 75252 Paris Cedex 05, France ‡Computational Mathematics Group, NAG Ltd, Jordan Hill Rd, Oxford OX2 8DR, U.K.

aubry@calfor.lip6.fr, lazard@calfor.lip6.fr, marc@nag.co.uk

(Received 6 August 1997)

Different notions of triangular sets are presented (Ritt, 1932; Wu, 1987; Kalkbrener, 1991; Lazard, 1991a; Wang, 1993). The relationship between these notions are studied. The main result is that four different existing notions of good triangular sets are equivalent.

1. Introduction

Triangular sets appear under various names in many papers concerning systems of polynomial equations. Ritt (1932) introduced them as characteristic sets. He described also an algorithm for solving polynomial systems by computing characteristic sets of prime ideals and factorizing in field extensions. Characteristic sets of prime ideals have good properties but factorization in algebraic extensions is, most of the time, too costly. In order to avoid factorizations, Wu’s algorithm (Wu, 1986; Wu, 1987) computes characteristic sets of finite sets of polynomials which do not generate necessarily prime ideals. Wu’s algorithm may produce redundant decompositions of varieties and may not discover their possible emptiness. Several authors continued and improved Wu’s approach, mainly Chou and Gao (1990, 1991a, 1992), Gallo and Mishra (1990, 1991) and Wang (1992, 1993, 1995).

Kalkbrener (1991) and Yang and Zhang (1994) introduced particular triangular sets, called regular chains. Taking advantage of the good properties of regular chains, Kalkbrener presented also an algorithm for decomposing a variety into unmixed-dimensional non-empty components described as regular chains. In addition, Lazard (1991a) introduced the notion of normalized triangular sets which are special regular chains and he provided a method for uniquely decomposing the solution of a polynomial system as regular zeros of such normalized triangular sets. This avoids the problems resulting from the non-canonicity of Wu’s and other decompositions. Wang (1998a) gave a generalization of the notion of a regular chain to pairs of polynomial sets (one set for equations and the other one for inequations) whose union is a triangular set, such pairs being called simple systems. He also presented an algorithm for solving polynomial systems by means of simple systems.

On the other hand, it has been remarked for a long time that field extensions of finite type are well represented as towers of simple transcendental or algebraic extensions, themselves represented by triangular sets. As irreducible varieties correspond to field

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1998 Academic Press Limited

extensions, solving polynomial systems may be viewed as equivalent to find the triangular sets corresponding to the fields associated to the components of the variety.

All these theories are very close together and the situation is rather confusing because many slightly different notions are used under the same (or, on the contrary, completely different) names by various authors. In this paper we are concerned with the clarification of this situation and we think that our main result is a step in this direction. More specifically we study the theoretical relationship between these various approaches to triangular sets, namely characteristic set (Ritt, 1932; Wu, 1984a), regular chain and representation of a regular chain (Kalkbrener, 1991), tower of simple extensions (Lazard, 1991a), regular set (Moreno Maza, 1997).

One can easily verify that if T is a reduced triangular set contained in a prime ideal P, then the following conditions are equivalent:

(i) T is a regular chain whose representation is P, (ii) T is a regular set which describes a tower of field extension defining the field asso-

ciated to P, (iii) P is the set of all polynomials reducible to 0 by T, (iv) T is a Ritt characteristic set of P.

It appears also that an ideal is naturally associated to any triangular set; we call it the saturated ideal. We review or define precisely all the above notions when the saturated ideal is not necessarily prime. We prove their main properties and study the relationship between them. Our main result is that, for a non-empty triangular set T, the following conditions are equivalent:

(i) T is a regular chain, (ii) T is a regular set, which is the name we give for the generalization of triangular

sets defining towers of field extensions, (iii) the set of all polynomials reducible to 0 by T is the saturated ideal of T, (iv) T is a Ritt characteristic set of its saturated ideal.

The paper is structured as follows. Section 2 consists mainly of standard preliminaries. In section 3, we review Ritt characteristic sets and the way they are used in the

algorithms of Ritt (1966), and Wu (1987).

We also examine the relationship between Ritt characteristic sets and Gröbner bases. In fact Ritt characteristic sets may easily be deduced from lexicographical Gröbner bases.

In section 4, we study properties of regular chains and establish that the ideal associated to a regular chain (namely its representation) is the radical of the saturated ideal of T.

In section 5 we define regular sets and their associated tower of simple extensions. We give an isomorphism which shows the relation between the saturated ideal of a regular set and its tower.

The very short section 6 states precisely the above mentioned main result and proves it as a corollary of the preceding sections.

Some natural results which appear in the paper may have been stated earlier (or may easily be deduced from earlier work) but we have not always found the original sources. For this reason and for an easier reading, several results which are not new are given with self-contained proofs.

2. Preliminaries

2.1. triangular sets

In this section we define our notations related to multivariate polynomials and we recall the most general definition for triangular sets, as in Wang (1993) where they are called triangular forms. We present a terminology which is completely different from the one of Gröbner basis theory, even if the notions are similar, in order to avoid confusion when both theories are used simultaneously. Note also that the term of initial is standard in differential algebra.

Notations 2.1. Let k be a field and x_{1} < x_{2} < ⋯ < x_{n} be n ordered variables. For every i in the range 1 … n we define P_{i} = k[x_{1}, …, x_{i}] to be the ring of multivariate polynomials in the variables x_{1}, …, x_{i} with coefficients in k. We also put P_{0} = k. Let p ∈ P_{n} with p ∉ k. We write deg(p, x_{i}) for the degree of p with respect to x_{i}.

Definition 2.1. Let p ∈ P_{n} with p ∉ k. We call the main variable of p, denoted by mvar(p), the greatest variable v ∈ {x_{1}, …, x_{n}} such that deg(p, v) ≠ 0. Assuming mvar(p) = x_{i}, let us regard p as a univariate polynomial in P_{i−1}[x_{i}]. Thus, we can write p = cx_{i}^{d} + r, where d = deg(p, x_{i}), c ∈ P_{i−1}, r ∈ P_{i} and r ≠ 0 ⇒ deg(r, x_{i}) < d. The quantities c, d and r are respectively called the initial, the main degree and the tail of p and denoted by init(p), mdeg(p) and tail(p). Finally, we call the head of p, denoted by head(p), the polynomial p − tail(p).

Example 2.1. Assume n ≥ 3 and let p ∈ P_{n}. If p = x_{1}x_{3}^{2} − 2x_{2}x_{3} + 1, then we have mvar(p) = x_{3}, mdeg(p) = 2, init(p) = x_{1}, tail(p) = −2x_{2}x_{3} + 1 and head(p) = x_{1}x_{3}^{2}.

Definition 2.2. A subset T of P_{n} is called a triangular set if no element of T lies in k and if for all p, q ∈ T with p ≠ q we have mvar(p) ≠ mvar(q). A variable v ∈ {x_{1}, …, x_{n}} is called algebraic w.r.t. T if there exists p ∈ T such that v = mvar(p). We denote by algVar(T) the set of all variables which are algebraic w.r.t. T.

Example 2.2. Assume n ≥ 4. The subset T_{1} = {x_{2}^{2} − x_{1}, x_{1}x_{3}^{2} − 2x_{2}x_{3} + 1, (x_{2}x_{3} − 1)x_{4} + x_{2}^{2}} of P_{n} is a triangular set (whose algebraic variables are x_{2}, x_{3}, x_{4}) whereas the subset T_{2} = {x_{1}^{2}x_{2} + 1, x_{1}x_{2}^{2} − 1} of P_{n} is not a triangular set.

Example 2.3. Let p ∈ P_{n}. Let iter(p) be the subset of P_{n} recursively defined as follows: if p ∈ R then iter(p) = ∅ otherwise iter(p) = {p}∪iter(init(p)). Then iter(p) is a triangular set of P_{n} whose elements are called the iterated initials of p. For instance, with p = (x_{2}x_{3} − 1)x_{4} + x_{2}^{2} we have iter(p) = {x_{2}, x_{2}x_{3} − 1, p}.

2.2. reduced triangular sets

In this section we first recall the partial ordering on the polynomials which is used in various algorithms dealing with triangular sets, and especially in the one of Ritt and Wu (Ritt, 1966; Wu, 1987). The termination of this algorithm is also based on the notion of reduced triangular sets (Definition 2.5) called chains in Ritt (1966) and ascending sets in Wu (1987). To increase the efficiency of Ritt-Wu algorithm, one may use the weaker notion of initially reduced triangular sets instead: see Moreno Maza (1997) for some examples. Moreover, initially reduced triangular sets appear in the output of the algorithm of Lazard and Moreno Maza (Lazard, 1991a; Moreno Maza, 1997) and in the connection between triangular sets and Gröbner bases (Theorem 3.3).

Definition 2.3. Let p, q ∈ P_{n}. We say that p is smaller than q w.r.t. Ritt ordering and we write p ≺_{r} q if one of the following assertions holds:

(i) p ∈ k and q ∉ k, (ii) p, q ∉ k and mvar(p) < mvar(q), (iii) p, q ∉ k and mvar(p) = mvar(q) and mdeg(p) < mdeg(q).

We say that p is greater than q w.r.t. Ritt ordering and we write p ≻_{r} q if q ≺_{r} p. We say that p and q are not comparable w.r.t. Ritt ordering and we write p ∼_{r} q if neither p ≺_{r} q nor p ≻_{r} q hold.

Remark 2.1. For p ∈ P_{n} with p ∉ k we have init(p) ≺_{r} p and tail(p) ≺_{r} p. Note also that every decreasing chain w.r.t. the Ritt ordering starting at p breaks off after finitely many steps.

Definition 2.4. Let p, q ∈ P_{n} with q ∉ k. We say that p is reduced w.r.t. q in Ritt sense and we write red?(p, q) if one of the following assertions holds:

(i) p ≺_{r} q, (ii) p ∉ k and mvar(p) > mvar(q) and red?(init(p), q) and red?(tail(p), q).

For a subset T of P_{n} we say that p is reduced w.r.t. T and we write red?(p, T) if for every t ∈ T the assertion red?(p, t) holds. We say that p is initially reduced w.r.t. q and we write iRed?(p, q) if one of the following assertions holds:

(i) p ≺_{r} q, (ii) p ∉ k and mvar(p) > mvar(q) and iRed?(init(p), q).

For a subset T of P_{n} we say that p is initially reduced w.r.t. T and we write iRed?(p, T) if for every t ∈ T the assertion iRed?(p, t) holds.

Proposition 2.1. For p, q ∈ P_{n} with q ∉ k, the following assertions are equivalent:

(i) red?(p, q), (ii) deg(p, mvar(q)) < mdeg(q).

Proof. The result is trivial if p ≺_{r} q. The general case is treated by induction on v^{d}, where v = mvar(p) and d = mdeg(p), using the Ritt ordering (see Remark 2.1). □

Notations 2.2. Let T be a triangular set of P_{n} and i be an integer in {1, …, n}. If x_{i} is an algebraic variable w.r.t. T, we denote by T_{x_{i}} the polynomial in T whose main variable is x_{i}. We also define:

T_{x_{i}}^{−} = T ∩ P_{i−1} and T_{x_{i}}^{+} = {t ∈ T | mvar(t) > x_{i}}.

Definition 2.5. A triangular set T of P_{n} is called reduced (resp. initially reduced) if for every v ∈ algVar(T) we have red?( T_{v}, T_{v}^{−}) (resp. iRed?( T_{v}, T_{v}^{−})).

Example 2.4. Assume n ≥ 4. The subset T_{1} (Example 2.2) of P_{n} is an initially reduced triangular set, but it is not reduced because of the tail of the third polynomial. The subset T_{3} = {x_{1}(x_{1} − 1), x_{1}^{2}x_{2} + 1} of P_{n} is not initially reduced because of the initial of the second polynomial.

Remark 2.2. Our notion of reduced triangular set is the same as in (Ritt, 1966) or (Wu, 1987). However our notion of initially reduced triangular set is weaker than Wu’s notion of ascending set in the weak sense, see p. 6 in (Wu, 1987). Indeed, a triangular set T has this latter property if for every t ∈ T, the head of t is reduced w.r.t. T \ {t}, whereas we only ask that for each polynomial p in iter(t) \ {t} such that there exists q ∈ T with mvar(p) = mvar(q) we have red?(p, q). Wu remarked that without any notion of reduction, his computations were frequently faster but may not terminate. Our notion of initially reduced triangular guarantees the termination of Wu’s algorithm. Moreover, the efficiency of the corresponding implementation compares to the one which does not use any notion of reduction.

On the other hand, for the algorithm of Chou and Gao (1990) and the algorithm of Wang (1993) the following notion of fine triangular sets, which is weaker than the one of initially reduced triangular sets, is adequate. Moreover, fine triangular sets are crucial for the main result of this paper (Theorem 6.1).

Notations 2.3. Let p, q ∈ P_{n}, with q ∉ k. We denote by prem(p, q) and pquo(p, q) the pseudo-remainder and the pseudo-quotient of p by q when interpreting them as univariate in mvar(q). Let T ⊆ P_{n} be a triangular set. If T = ∅ we define prem(p, T) = p otherwise we define prem(p, T) = prem(prem(p, T_{v}), T_{v}^{−}) where v is the greatest variable of algVar(T). For instance, with T_{4} = {x_{1}(x_{1} − 1), x_{1}x_{2} − 1} and p = x_{2}^{2} + x_{1}x_{2} + x_{1}^{2}, we have

prem(p, T) = prem(prem(p, T_{x_{2}}), T_{x_{1}}) = prem(x_{1}^{4} + x_{1}^{2} + 1, T_{x_{1}}) = 2 x_{1} + 1.

Definition 2.6. A triangular set T of P_{n} is called fine if it is not empty and if for every v ∈ algVar(T) we have prem(init( T_{v}), T_{v}^{−}) ≠ 0.

2.3. saturated ideals and regular zeros

Triangular sets are deeply involved in polynomial system solving. In methods like those of Wu (1987), Wang (1993), Lazard and Moreno Maza (Lazard, 1991a; Moreno Maza, 1997), one has to consider a particular subset of the affine variety associated to a triangular set (on an algebraic closure of k), namely the set of regular zeros.

In the method of Kalkbrener, one has to consider a particular ideal associated with a triangular set, namely its saturated ideal. This concept of saturated ideal associated with a triangular set was first considered in Chou and Gao (1991b). However the more general concept of saturated ideal w.r.t. a multiplicatively closed subset of a ring is standard in commutative algebra, see p. 90 in (Bourbaki, 1961).

To investigate triangular set properties, we recall these notions in this section.

Notations 2.4. For F ⊆ P_{n} we denote by ⟨F ⟩ the ideal of P_{n} generated by F and by \sqrt{⟨F ⟩} the radical of ⟨F ⟩. For h ∈ P_{n} we denote by ⟨F ⟩ : h the ideal quotient of ⟨F ⟩ by h (i.e. the set of the polynomials p ∈ P_{n} such that p h ∈ ⟨F ⟩). Let T ⊆ P_{n} be a triangular set. We denote by red_{↦0}(T) the subset of P_{n} defined as follows:

red_{↦0}(T) = {p ∈ P_{n} | prem(p, T) = 0}.

Proposition 2.2. Let p ∈ P_{n} and T = {t_{1}, …, t_{ℓ}} be a triangular set of P_{n}. Let c_{k} be the initial of t_{k}. Then we have red?(prem(p, T), T). Moreover, there exist integers e_{1}, …, e_{ℓ} and polynomials q_{1}, …, q_{ℓ} in P_{n} such that:

c_{1}^{e_{1}} ⋯ c_{ℓ}^{e_{ℓ}}p = q_{1}t_{1} + ⋯ + q_{ℓ}t_{ℓ} + prem(p, T).

Proof. This statement is easily obtained by induction on ℓ and using Proposition 2.1. It appears in (Wu, 1984a) as the remainder formula. □

Definition 2.7. Let T ⊆ P_{n} be a non-empty triangular set. Let h be the product of the initials of the polynomials in T. We call the saturated ideal of T the ideal of P_{n} denoted by sat(T) and defined as follows:

sat(T) = {p ∈ P_{n} | (∃n ∈ IN) h^{n}p ∈ ⟨T ⟩}.

If T = ∅ we set sat(T) = {0}.

Proposition 2.3. For any triangular set T ⊆ P_{n} we have:

red_{↦0}(T) ⊆ sat(T).

The set red_{↦0}(T) is not necessarily an ideal of P_{n} and the previous inclusion is not necessarily an equality.

Proof. The above inclusion is obviously obtained from Proposition 2.2. Let us now give a counter-example illustrating the fact that red_{↦0}(T) is not necessarily an ideal of P_{n}. Assume n ≥ 2 and consider the following triangular set T_{4} = {x_{1}(x_{1} − 1), x_{1}x_{2} − 1}. One can check that a lexicographical Gröbner basis of sat(T_{4}) is {x_{1} − 1, x_{2} − 1}. We define p = (x_{1} −1)(x_{1}x_{2} −1) and q = −(x_{1} −1)x_{1}x_{2}. We see that prem(p, T_{4}) = prem(q, T_{4}) = 0. But we have p + q = 1 − x_{1} and thus (p + q) ∉ red_{↦0}(T_{4}). □

Notations 2.5. Let K be an algebraic closure of k. For F ⊆ P_{n} we denote by V(F) the affine variety of K^{n} associated with F (i.e. the set of the points in K^{n} where every polynomial in F vanishes). For W ⊆ K^{n} we denote by \overline{W} the Zariski closure of W w.r.t. k (i.e. the intersection of those V(F) containing W, for any F ⊆ P_{n}).

Definition 2.8. Let T ⊆ P_{n} be a non-empty triangular set. Let h be the product of the initials of the polynomials in T. We call the regular zeros of T the elements of the subset of V(T) denoted by W(T) and defined as follows:

W(T) = V(T) \ V(h).

The triangular set T is called consistent if W(T) ≠ ∅, or, in other words, if h ∉ \sqrt{⟨T ⟩}.

Theorem 2.1. For any non-empty triangular set T ⊆ P_{n} we have:

\overline{W(T)} = V(sat(T)).

Proof. It is clear that \overline{W(T)} = \overline{V(\sqrt{⟨T ⟩}) \ V(h)}. Thus, by Theorem 7 p. 193 in Cox et al. (1991), we have \overline{W(T)} = V(\sqrt{⟨T ⟩} : h). Finally, one can check that for any positive integer k > 0 we have \sqrt{⟨T ⟩} : h = \sqrt{⟨T ⟩} : h^{k} and thus \sqrt{⟨T ⟩} : h = \sqrt{sat(T)}. □

3. Characteristic Sets

Ritt (1932) introduced the concept of a characteristic set of a finite or infinite set of differential polynomials; see p. 4 in Ritt (1966). One of his goals was to provide a method to solve systems of differential equations. A byproduct of that work is an algorithm for solving systems of algebraic equations by means of triangular sets, p. 95 in (Ritt, 1966). More precisely, given a finite subset F of P_{n}, Ritt’s algorithm computes characteristic sets T_{1}, …, T_{ℓ} of prime ideals such that:

V(F) = ∪_{1}^{ℓ} W(T_{i}).

Characteristic sets of prime ideals have good properties (see theorem 3.3) but Ritt’s process involves factorization in field extensions.

Wu (1986, 1987) used Ritt’s work to provide an algorithm for solving systems of algebraic equations by means of triangular sets which only requires pseudo-remainder computations (i.e. no factorizations are needed). Wu’s process is based on a procedure called CHRST-REM, see p. 3 in (Wu, 1987). Given a finite subset F of P_{n}, this procedure computes a characteristic set T of a finite subset G of P_{n} such that ⟨F ⟩ = ⟨G⟩. But this T is not necessarily a characteristic set of ⟨F ⟩. If F generates the unit ideal of P_{n}, it is not always possible to discover it by using the procedure CHRST-REM. Moreover, the decompositions provided by Wu’s algorithm (Wu, 1987) may be redundant. See Chapter 6 in Moreno Maza (1997) for some examples. However, Chou and Gao (1992) proved that Wu’s algorithm provides a decomposition of an affine variety into unmixed-dimensional (or empty) components, and provided an algorithm for removing empty components.

Wu used the concept of characteristic set in a more general situation than Ritt did in his algorithm. But Wu did not give a precise definition for his case: in (Wu, 1987) a characteristic set is the result of algorithm CHRST-REM. The output of this algorithm depends on the ordering in which the input polynomials are being read. Taking into account the way algorithm CHRST-REM works, we propose the Definition 3.1 below for a characteristic set in the sense of Wu.

Wu characteristic set computations are based on Ritt ordering (see Definition 3.2) for reduced triangular sets. In view of our Theorem 6.1 we extend Ritt ordering defined for reduced triangular sets in p. 4 of Ritt (1966) to fine triangular sets. With this modification, we review Ritt definition for characteristic sets of ideals in P_{n} (Definition. 3.3) and their basic properties (Proposition. 3.3, Theorem. 3.1). Until Remark 3.2, the content of this section is standard, but generally stated for reduced characteristic sets (Ritt, 1966), whereas we are concerned here with fine triangular sets. Then, we show how a Ritt characteristic set of an ideal I can easily be produced from a lexicographical Gröbner basis of I (prop. 3.4, 3.5 and th. 3.2). Following Ritt (1966) we also investigate the case of prime ideals (th. 3.3).

Notations 3.1. Throughout this section F will denote a non-empty subset of non-null polynomials of P_{n}.

Definition 3.1. A non-empty subset T of ⟨F ⟩ is a Wu characteristic set of F if one of the following conditions holds:

(i) T = {a} for a ≠ 0 in k, (ii) T is a triangular set and there exists a subset G of ⟨F ⟩ such that ⟨F ⟩ = ⟨G⟩ and

G ⊆ red_{↦0}(T).

Proposition 3.1. Let T = {t_{1}, …, t_{ℓ}} be a triangular set of P_{n}. We denote by c_{k} the initial of t_{k}. If T is a Wu characteristic set of F, then we have:

(i) ⟨F ⟩ ⊆ sat(T), (ii) \overline{W(T)} ⊆ V(F) ⊆ V(T), (iii) V(F) = W(T) ∪ ∪_{1}^{l} V(F ∪ {c_{k}}), (iv) If ⟨F ⟩ is a prime ideal and if W(T) ≠ ∅ then we have V(F) = \overline{W(T)}.

Proof. Property (i) is deduced from Proposition 2.3. Then, property (ii) results from (i) and Theorem 2.1. Since (ii) holds, we clearly have:

W(T) ∪ ∪_{1}^{l} V(F ∪ {c_{k}}) ⊆ V(F).

Conversely, since W(T) ⊆ V(F) ⊆ V(T), if a point ζ ∈ V(F) does not belong to W(T), then it lies in one of the V(F ∪ {c_{k}}). Property (iv) follows easily from (iii). □

Remark 3.1. Let F and T be as above. The triangular set T may be a Wu characteristic set of F even if F generates the unit ideal of P_{n}. For instance, choose F = T_{1} as in Example 2.2. In that case F is a Wu characteristic set of itself but we have ⟨F ⟩ = ⟨1⟩.

Definition 3.2. Let T = {t_{1}, …, t_{ℓ}} and S = {s_{1}, …, s_{k}} be two fine triangular sets of P_{n}. We say that T is smaller than S w.r.t. Ritt ordering and we write T ≺_{r} S if one of the following conditions holds:

(i) (∃i ∈ {1, …, min(k, ℓ)}) (∀j ∈ {1, …, i − 1}) t_{j} ∼_{r} s_{j} and t_{i} <_{r} s_{i}, (ii) ℓ > k and (∀j ∈ {1, …, k}) t_{j} ∼_{r} s_{j}.

We say that T is greater than S w.r.t. Ritt ordering and we write T ≻_{r} S if S ≺_{r} T. We say that T and S are not comparable w.r.t. Ritt ordering and we write T ∼_{r} S if neither T ≺_{r} S nor T ≻_{r} S holds.

Proposition 3.2. Let T = {t_{1}, …, t_{ℓ}} and S = {s_{1}, …, s_{k}} be two fine triangular sets of P_{n}. Then the following assertions hold:

(i) T ∼_{r} S ⟺ l = k and (∀j ∈ {1, …, k}) t_{j} ∼_{r} s_{j}, (ii) (∀p ∈ P_{n} \ k) (red?(p, T) and x_{i} = mvar(p)) ⟹ T_{x_{i}}^{−} ∪ {p} ≺_{r} T.

Proof. This statement results obviously from Definitions 2.4 and 3.2. □

Definition 3.3. A subset T of F is a Ritt characteristic set of F if one of the following conditions holds:

(i) T = {a} for a ≠ 0 in k, (ii) F ∩ k ⊆ {0} and T is a minimal element for ≺_{r} in F, where F denotes the set of

all fine triangular sets contained in F.

Proposition 3.3. Let T be a Ritt characteristic set of ⟨F ⟩. Then T is a Wu characteristic set of F. Moreover, if T is a triangular set, then we have ⟨F ⟩ ⊆ red_{↦0}(T).

Proof. The case T ⊂ k is trivial. So we assume that T is a triangular set. Thus we have ⟨F ⟩ ∩ k = {0}. Let f ∈ ⟨F ⟩. We define r = prem(f, T). From (i) of Proposition 2.2 we get r ∈ ⟨F ⟩. Assuming r ≠ 0, we have r ∉ k and r has a main variable v. From Proposition 3.2 and (ii) of Proposition 2.2 we have:

T_{v}^{−} ∪ {r} ≺_{r} T.

This leads to a contradiction and shows that r = 0 and ⟨F ⟩ ⊆ red_{↦0}(T). □

Theorem 3.1. Let T be a fine triangular set contained in ⟨F ⟩. Then the following conditions are equivalent:

(i) T is a Ritt characteristic set of ⟨F ⟩, (ii) ⟨F ⟩ ⊆ red_{↦0}(T).

Proof. From Proposition 3.3 we only need to prove that if T is not a Ritt characteristic set of ⟨F ⟩ then there exists a polynomial p ∈ ⟨F ⟩ such that prem(p, T) ≠ 0. Thus we assume that there exists a fine triangular set S ⊆ ⟨F ⟩ such that S ≺_{r} T. We define S = {s_{1}, …, s_{k}} and T = {t_{1}, …, t_{ℓ}}. If S is not reduced, and since S is a fine triangular set, we can replace s_{j} by prem(s_{j}, {s_{1}, …, s_{j−1}}) for j in the range 2 … k without violating any of the previous assumptions. We distinguish two cases. First if ℓ < k and for all j ∈ {1, …, ℓ} we have t_{j} ∼_{r} s_{j}, then let p = s_{ℓ+1}. Note that red?(p, {s_{1}, …, s_{ℓ}}). Since for all j ∈ {1, …, ℓ} we have t_{j} ∼_{r} s_{j} we also get red?(p, {t_{1}, …, t_{ℓ}}). Now if there exists i ∈ {1, …, min(k, ℓ)} such that s_{i} ≺_{r} t_{i} and for all j ∈ {1, …, i − 1} we have t_{j} ∼_{r} s_{j}, then let p = s_{i}. As above we have red?(p, {t_{1}, …, t_{i−1}}). Since p ≺_{r} t_{i} and since for j ∈ {i + 1, …, ℓ} we have mvar(p) ≺_{r} mvar(t_{j}), we get red?(p, {t_{1}, …, t_{ℓ}}). Finally in both cases, we have found a polynomial p ∈ ⟨F ⟩ such that prem(p, T) ≠ 0. □

Remark 3.2. Computing Wu characteristic sets by means of Wu’s procedure CHRST-REM is a hard task on some examples. Thus, in (Wang, 1992), the following weaker notion is used: a triangular set T contained in ⟨F ⟩ is called a medial set of F if it is not greater w.r.t. Ritt ordering than any characteristic set of F. Of course, a Wu characteristic set of F and thus a Ritt characteristic set of ⟨F ⟩ are medial sets of F.

3.1. characteristic sets and lexicographical Gröbner bases

Notations 3.2. From now on, we assume ⟨F ⟩ ≠ P_{n}. We define I = ⟨F ⟩. Let ≺_{lex} be the lexicographical ordering on the monomials of P_{n} w.r.t the ordering x_{1} < ⋯ < x_{n}. Let p ∈ P_{n}. We denote by lm(p) the leading monomial of p w.r.t. ≺_{lex} and by lc(p) the corresponding leading coefficient in k. Let G be the minimal Gröbner basis of I w.r.t. ≺_{lex} such that for every g ∈ G we have lc(p) = 1. We define lm(G) = {lm(g) | g ∈ G}.

Recall that if p lies in I then there exists g ∈ G such that lm(g) divides lm(p). Let v be a variable in {x_{1}, …, x_{n}}. Now, we define:

G_{v} = {g ∈ G | mvar(g) = v} and G_{v}^{−} = {g ∈ G | mvar(g) < v}.

Finally, we denote by algVar(G) the set of those variables v such that G_{v} ≠ ∅.

Definition 3.4. Let G be as above and let algVar(G) = {y_{1}, …, y_{m}} with y_{1} < ⋯ < y_{m}. We call the median set of F and denote by M(F) the subset of G defined as follows:

(i) if m = 1 then M(F) = {g_{1}} where g_{1} is the smallest polynomial in G_{y_{1}} w.r.t. ≺_{lex},

(ii) if m > 1 then defining T = M( G_{y_{m}}^{−}) we distinguish two cases:

(a) if G_{y_{m}} ⊆ red_{↦0}(T) then M(F) = T,

(b) if G_{y_{m}} ⊈ red_{↦0}(T) then M(F) = T ∪ {g_{m}} where g_{m} is the smallest polynomial g in G_{y_{m}} w.r.t. ≺_{lex} such that prem(g, T) ≠ 0.

Example 3.1. Assume n ≥ 4 and define F = {x_{1}x_{2}, x_{2}x_{3}, x_{3}x_{4}}. Then we have G = F and M(F) = {x_{1}x_{2}, x_{3}x_{4}}.

Example 3.2. Assume n ≥ 4 and define F = {x_{2}^{2} − x_{1}, x_{3}^{2} − 2x_{2}x_{3} + x1, (x_{3} − x_{2})x_{4}}. Then we have G = F and M(F) = G. Note that W(M(F)) = ∅ since (x_{3} − x_{2}) lies in the radical of G_{x_{4}}^{−}.

Remark 3.3. Even if F generates a radical ideal we may have W(M(F)) = ∅. Assume n ≥ 4 and consider F = {x_{1}^{2} − 2, x_{2}^{2} − 2, (x_{1} − x_{2})x_{3}, (x_{1} + x_{2})x_{4}}. In this case we have G = F ∪ {x_{3}x_{4}} and M(F) = F. We easily check that the product of the initials of F_{x_{3}} and F_{x_{4}} lies in the ideal generated by F_{x_{3}}^{−}. In order to avoid W(M(F)) being empty, one may assume that F generates a prime ideal (see Theorem 3.3).

Proposition 3.4. The median set M(F) is a non-empty triangular set such that

M(F) ⊆ ⟨F ⟩ ⊆ red_{↦0}(M(F)).

Proof. Let I and G be as in Notation 3.2 and set T = M(F). Remark that T is not empty and that the first inclusion is trivial. Let us prove the second one. Suppose that there exists some p ∈ I such that p ∉ red_{↦0}(M(F)). Let r = prem(p, T). Note that r ∈ I. Thus, there exists g ∈ G such that lm(r) is a multiple of lm(g). Since red?(r, T) we have also red?(lm(r), T) and red?(lm(g), T). Let v = mvar(g). It follows from Definition 3.4 that either g ∈ red_{↦0}( T_{v}^{−}), or g = T_{v}, or lm( T_{v}) ≺_{lex} lm(g). Since red?(lm(g), T) the last two cases are impossible. Suppose that the first one holds. Define h = init(g). Thus we have prem(h, T_{v}^{−}) = 0 and one can check that there exists a polynomial c ∈ iter(h) such that mvar(c) ∈ algVar( T_{v}^{−}) and prem(c, T_{v}^{−}) = 0. Hence c and lm(g) are not reduced w.r.t. T_{v}^{−}. This contradicts Definition 3.4. □

Proposition 3.5. The median set M(F) is a fine triangular set.

Proof. Let I and G be as in Notation 3.2 and define T = M(F). Assume that for some v ∈ algVar(T) we have prem(init(g_{v}), M(F)) = 0 and put r = prem(tail(g_{v}), T_{v}^{−}). Then, one can check that:

prem(g_{v}, T_{v}^{−}) = r.

Since T_{v}^{−} ∪ {g_{v}} ⊆ I we get r ∈ I. Thus, by Proposition 3.4 we have prem(r, T) = 0. As red?(r, T), in fact we have r = 0. Hence prem(g_{v}, T_{v}^{−}) = 0. This contradicts the definition of M(F). □

Theorem 3.2. The median set M(F) is a Ritt characteristic set of ⟨F ⟩.

Proof. This statement results from Theorem 3.1 and Propositions 3.4 and 3.5. □

Proposition 3.6. The median set M(F) is initially reduced.

Proof. Let I and G be as in Notation 3.2. We define T = M(F). Assume that T is not initially reduced. Thus, there exists v ∈ algVar(T) such that T_{v} is not initially reduced w.r.t. T_{v}^{−}. We choose v as small as possible. It is clear that T_{v}^{−} ≠ ∅. Since T is a fine triangular set, we have prem(init( T_{v}), T_{v}^{−}) ≠ 0. Then by multiplying T_{v} by a product of the initials of T_{v}^{−} we can compute a polynomial t ∈ I such that mvar(t) = v, the polynomial t is reduced w.r.t. T_{v}^{−} and lm(t)≺_{lex}lm( T_{v}). Consequently, due to the definition of T, the monomial lm(t) can be divided by one of those polynomials g ∈ G_{v} such that prem(g, T_{v}^{−}) = 0. This shows that t is not reduced w.r.t. T_{v}^{−} and leads to a contradiction. □

Remark 3.4. Theorem 3.2 shows that every ideal I of P_{n} possesses a Ritt characteristic set and that such a set is not harder to compute than a lexicographical Gröbner basis of I. Moreover, to check whether a subset C of I is a Ritt characteristic set of I it is sufficient to verify that C is a fine triangular set such that C∼_{r}M(I). The following theorem shows that if F generates a prime ideal then M(F) is consistent and is easier to obtain than in the general case.

Notations 3.3. For v ∈ algVar(G), if G_{v} ≠ ∅ we denote by g_{v} the smallest polynomial in G_{v} w.r.t. ≺_{lex}. We denote by T_{G} the triangular set whose elements are these polynomials g_{v}.

Theorem 3.3. If F generates a prime ideal in P_{n}, then we have:

(i) M(F) = T_{G}, (ii) ⟨F ⟩ = sat(M(F)), (iii) V(F) = \overline{W(M(F))}, (iv) M(F) is consistent.

Proof. Let I and G be as in Notation 3.2. For convenience, we simply write T instead of T_{G}. We first prove (i). Let v ∈ algVar(T). We shall verify that T_{v} is initially reduced w.r.t. T_{v}^{−}. Let us assume the contrary. So let h be in iter( T_{v}) with w = mvar(h). Let us assume that w ∈ algVar( T_{v}^{−}) and that h is not reduced w.r.t. T_{w}. Thus there exist an integer e and two polynomials q and r such that:

init( T_{w})^{e} h = q T_{w} + r and r ≺_{r} T_{w}.

If r = 0 then init( T_{w})^{e}h ∈ I. Since I is a prime ideal, either init( T_{w}) or h would lie in I. This is impossible: G is a minimal Gröbner basis and thus for every g ∈ G, no polynomial in iter(init(g)) can belong to I. If r ≠ 0 then we can reduce T_{v} w.r.t. T_{w} and obtain a polynomial t ∈ I such that mvar(t) = v and lm(t)≺_{lex}lm( T_{v}). Since G is a minimal Gröbner basis of I, and since T_{v} is the smallest polynomial in G with v as main variable, we are led to another contradiction. This completes the proof of (i). We now prove (ii). From Propositions 3.4 and 2.3 we only need to verify: I ⊇ sat(T). Let p ∈ sat(T). There exists a product π of the initials of T such that πp lies in the ideal generated by T and thus in I. We have already remarked that no initial of T could lie in I. Thus, since I is a prime ideal, we have p ∈ I. Point (iii) follows from (ii) and Theorem 2.1. Finally, point (iv) follows from (iii) since we have assumed I ≠ P_{n}. □

4. Regular Chains

The concept of a regular chain was introduced independently by Yang and Zhang (1994) and Kalkbrener (1991). Regular chains also appear in Chou and Gao (1992). Regular chains are special fine triangular sets which are used by these authors to provide algorithms for computing unmixed-dimensional decompositions of algebraic varieties. Without using factorization, these decompositions have better properties than the ones produced by Wu’s algorithm.

Kalkbrenner’s original definition was based on the following remark. Since every irreducible variety is uniquely determined by one of its generic points, varieties can be represented by describing the generic points of their irreducible components. These generic points are given in Kalkbrener (1991) by regular chains.

Since varieties correspond to radical ideals and generic points to prime ideals, varieties can also be represented by describing their associated prime ideals. These associated prime ideals are given by regular chains in Kalkbrener (1998) where regular chains correspond to a particular case of system of representations. The Definition 4.1 below follows this second point of view.

Propositions 4.1 and 4.2 give a practical characterization of the representation of a regular chain. Propositions 4.3 and 4.4 give practical properties of the radical of the saturated ideal of a regular chain. Finally, Theorem 4.1 states the main result of this section: the representation of a regular chain is the radical of its saturated ideal. This result is close to Lemma 4.3 in Kalkbrener (1998) which is essentially an induction assertion for our theorem. As the context is not exactly the same we provide a self-contained proof.

Notations 4.1. Let A be a commutative Noetherian ring with units. We denote by reg(A) the multiplicatively closed subset of A consisting of the regular elements of A (i.e. the elements of A which are not zero-divisors). Then we denote by fr(A) the total quotient ring of A (i.e. the ring of fractions with numerators from A and denominators from reg(A)). Let I be an ideal of A. We denote by A/I the residue class ring of A by I, we denote by \sqrt{I} the radical of I and we denote by I[x] the ideal generated by I in A[x]. For h ∈ A we denote by I : h^{∞} the saturated ideal of I w.r.t. h (i.e. the set of the a ∈ A such that there exists an non-negative integer e with h^{e} a ∈ I). For p ∈ A[x] we denote by \overline{p}I the canonical image of p in fr(A/I)[x]. Finally, for any prime ideal P associated to I, defining κ = fr(A/P), we will write \overline{p}^{κ} for \overline{p}P.

Remark 4.1. The following basic relations and properties will be useful in this section and in the next one. First note that \sqrt{I[x]} = \sqrt{I}[x] and (I : h^{∞})[x] = (I[x]) : h^{∞}. Let p ∈ A[x] with p ∉ A. The polynomial \overline{p}I is monic in fr(A/I)[x] iff for any prime ideal P associated to I the initial of p does not belong to P. See vol. 1, p.214 in Samuel and Zariski (1967). Assume from now on that \overline{p}I is monic. Then we clearly have deg(p, x) = deg(\overline{p}I, x). Moreover, giving another polynomial r ∈ A[x] with r ∉ A, if deg(r, x) < deg(p, x) then we have deg(\overline{r}I, x) < deg(\overline{p}I, x).

Example 4.1. Assume n ≥ 3, let k = Q ı the field of rational numbers. Let T_{5} = {p_{1}, p_{2}} where p_{1} = x_{1}^{4} − 5 x_{1}^{2} + 6 and p_{2} = (x_{1}^{2} − 2) x_{2}^{2} + (−2 x_{1}^{3} + 4 x_{1}) x_{2} + x_{1}^{4} − 2 x_{1}^{2}. Let I be the ideal generated by T_{5} in P_{n}. We have the following primary decomposition:

I = ⟨x_{1}^{2} − 3, (x_{2} − x_{1})^{2}⟩ ∩ ⟨x_{1}^{2} − 2⟩.

Thus the associated prime ideals of I are P_{1} = ⟨x_{1}^{2} − 3, (x_{2} − x_{1})⟩ and P_{2} = ⟨x_{1}^{2} − 2⟩ so that we have \sqrt{I} = P_{1} ∩ P_{2}. Hence the associated fields of I are

κ_{1} = fr(Q ı [x_{1}, x_{2}]/P_{1}) = Q ı (\sqrt{3}) and κ_{2} = fr(Q ı [x_{1}, x_{2}]/P_{2}) = Q ı (\sqrt{2})(x_{2}).

Now let p_{3} = (x_{1}^{2} − 2) x_{3}^{4} + (x_{2} − x_{1}) x_{3}^{3} + (1 − x_{1}) x_{3} + 1 and put h = init(p_{3}). We have \overline{h}^{κ_{1}} = 1 and \overline{h}^{κ_{2}} = 0. This shows that \overline{p}I is not monic in fr(A/I)[x].

Notations 4.2. Let T be a triangular set of P_{i} and let j ∈ {1, …, i}. From now on Rep_{j}(T) will denote an ideal of P_{j} and we define Rep_{0}(T) = {0}. Then K_{j}(T) will denote the set of all fields κ = fr(P_{j}/P), where P is a prime ideal associated to Rep_{j}(T). Finally we denote by sat_{j}(T) the saturated ideal of T ∩ P_{j} in P_{j}. Note from Remark 4.1 that if x_{i} ∉ algVar(T) then we have sat_{i}(T) = sat_{i−1}(T)[x_{i}].

Definition 4.1. We say that T is a regular chain in P_{i} whose representation is Rep_{i}(T) if one of the following conditions holds:

(i) i = 0 and the set T is empty, (ii) i > 0, the set T_{x_{i}}^{−} is a regular chain of P_{i−1} whose representation is Rep_{i−1}(T)

such that one of both assertions holds:

(a) x_{i} ∉ algVar(T) and for every p ∈ P_{i} we have:

p ∈ Rep_{i}(T) ⟺ (∀κ ∈ K_{i−1}( T_{x_{i}}^{−})) \overline{p}^{κ} = 0,

(b) x_{i} ∈ algVar(T), and for every κ ∈ K_{i−1}( T_{x_{i}}^{−}) we have \overline{init( T_{x_{i}})}^{κ} ≠ 0 and for every p ∈ P_{i} we have:

p ∈ Rep_{i}(T) ⟺ (∀κ ∈ K_{i−1}( T_{x_{i}}^{−})) \overline{p}^{κ} ∈ \sqrt{⟨ \overline{T_{x_{i}}}^{κ}⟩}.

Example 4.2. Assume n ≥ 3 and let p_{1}, p_{2}, p_{3} be as in Example 4.1. The set {p_{1}} is clearly a regular chain in P_{n} whose representation is ⟨p_{1}⟩. However {p_{1}, p_{2}} is not a regular chain in P_{n} since init(p_{2}) vanishes w.r.t. one of the prime ideals associated to ⟨p_{1}⟩. The two sets C_{1} = {x_{1}^{2} − 3, (x_{2} − x_{1})^{2}} and C_{2} = {x_{1}^{2} − 2} are regular chains whose representations are respectively P_{1} and P_{2}. The set C_{1} ∪ {p_{3}} is a regular chain since \overline{h}^{κ_{1}} = 1 where h = init(p_{3}) and its representation is ⟨x_{1}^{2} − 3, x_{2} − x_{1}, (x_{3}^{2} − x_{1}) (x_{3}^{2} + 1)⟩.

Proposition 4.1. Let T be a regular chain in P_{i}. Then we have

x_{i} ∉ algVar(T) ⟹ Rep_{i}(T) = \sqrt{Rep_{i−1}(T)}[x_{i}].

Proof. Let p ∈ P_{i} and let κ ∈ K_{i−1}( T_{x_{i}}^{−}). The relation \overline{p}^{κ} = 0 means that every coefficient of p as a univariate polynomial in P_{i−1}[x_{i}] is null in κ. Thus f ∈ Rep_{i}(T) means that every coefficient of p as a univariate polynomial in P_{i−1}[x_{i}] lies in every prime ideal associated to Rep_{i−1}(T). Finally, the statement results from the fact that \sqrt{Rep_{i−1}(T)} is the intersection of the prime ideals associated to Rep_{i−1}(T). □

Proposition 4.2. Let T be a regular chain in P_{i}. Then we have

x_{i} ∈ algVar(T) ⟹ Rep_{i}(T) = {p ∈ P_{i} | (∃m ≥ 0) prem(p^{m}, T_{x_{i}}) ∈ Rep_{i}( T_{x_{i}}^{−})}.

Proof. Let p ∈ P_{i}. We define t = T_{x_{i}} and h = init(t). Let e ≥ 0 be an integer. We define r_{e} = prem(p^{e}, t). Let δ_{e} be a non-negative integer and let q_{e} ∈ P_{i} such that:

h^{δ_{e}}p^{e} = q_{e}t + r_{e}.  (4.1)

We first assume that p ∈ Rep_{i}(T). We prove that there exists an integer m ≥ 0 such that r_{m} ∈ Rep_{i}( T_{x_{i}}^{−}). Let κ ∈ K_{i−1}( T_{x_{i}}^{−}). By point (b) of Definition 4.1 there exists an integer m ≥ 0 such that (\overline{p}^{κ})^{m} lies in the ideal generated by \overline{t}^{κ}. By choosing m big enough, we can take the same integer m for every prime ideal P associated to Rep_{i−1}( T_{x_{i}}^{−}). With the relation (4.1) we see that \overline{r_{m}}^{κ} lies in the ideal generated by \overline{t}^{κ}. By Remark 4.1 it follows that \overline{r_{m}}^{κ} = 0. The same way as in the proof of Proposition 4.1 we get:

r_{m} ∈ \sqrt{Rep_{i−1}( T_{x_{i}}^{−})}[x_{i}].

Finally, from the statement of the same proposition we are led to r_{m} ∈ Rep_{i}( T_{x_{i}}^{−}). Conversely, assume that there exists an integer m ≥ 0 such that r_{m} ∈ Rep_{i}( T_{x_{i}}^{−}). We prove that p ∈ Rep_{i}(T). Let κ ∈ K_{i−1}( T_{x_{i}}^{−}). Since \overline{r_{m}}^{κ} = 0, with the above relation (4.1), we see that \overline{h^{δ_{m}}p^{m}}^{κ} ∈ ⟨\overline{t}^{κ}⟩. By point (b) of Definition 4.1, the element \overline{h^{δ_{m}}}^{κ} is invertible. Then it follows that \overline{p}^{κ} lies in the radical of ⟨\overline{t}^{κ}⟩. Finally we get p ∈ Rep_{i}(T). □

Proposition 4.3. Let T be a non-empty triangular set of P_{i} with x_{i} ∈ algVar(T) and let r ∈ P_{i}. We define t = T_{x_{i}}. We assume that the following assertions hold:

(i) for every prime ideal P associated to sat_{i−1}( T_{x_{i}}^{−}) we have init(t) ∉ P, (ii) r ∈ sat_{i}(T), (iii) deg(r, x_{i}) < mdeg(t).

Then we have r ∈ \sqrt{sat_{i}( T_{x_{i}}^{−})}.

Proof. We define h = init(t). We distinguish two cases. First we assume that T_{x_{i}}^{−} = ∅. From hypothesis (ii), there exists an integer δ ≥ 0 such that t divides h^{δ}r. From hypothesis (iii), and since we are working in the integral domain P_{i−1}[x_{i}] we get r = 0, which proves our claim. Now let us assume that T_{x_{i}}^{−} ≠ ∅. We denote by h′ the product of the initials of the polynomials in T_{x_{i}}^{−}. From hypothesis (ii), there exists an integer δ ≥ 0 and q ∈ P_{i} such that (hh′)^{δ}r + qt lies in the ideal generated by T_{x_{i}}^{−} in P_{i}. Let P be a prime ideal associated to sat_{i−1}( T_{x_{i}}^{−}) and put κ = fr(P_{i−1}/P). It is a classical remark that h′ ∉ P. Thus, by hypothesis (i), the element \overline{hh′}^{κ} is invertible. Therefore \overline{t}^{κ} divides \overline{r}^{κ}. Since we are working with univariate polynomials with coefficients in a field, hypothesis (iii) yields \overline{r}^{κ} = 0. Finally, the statement follows from Remark 4.1 □

Proposition 4.4. Let T be a non-empty triangular set of P_{i} with x_{i} ∈ algVar(T) and let p ∈ P_{i}. We define t = T_{x_{i}}. We assume that for every prime ideal P associated to sat_{i−1}( T_{x_{i}}^{−}) we have init(t) ∉ P. Then the following conditions are equivalent:

(i) p ∈ \sqrt{sat_{i}(T)},

(ii) (∃m ≥ 0) | prem(p^{m}, t) ∈ \sqrt{sat_{i}( T_{x_{i}}^{−})}.

Proof. We first prove that (i) ⇒ (ii). Let m ≥ 0 be an integer such that p^{m} ∈ sat_{i}(T). Since t ∈ sat_{i}(T), we clearly have prem(p^{m}, t) ∈ sat_{i}(T). Then Proposition 4.3 applies with r = prem(p^{m}, t) and we get (ii). We now prove (ii) ⇒ (i). Let m ≥ 0 be an integer such that prem(p^{m}, t) lies in the radical of sat_{i}( T_{x_{i}}^{−}). If T_{x_{i}}^{−} is empty we easily get (i). So we assume T_{x_{i}}^{−} ≠ ∅. We denote by h′ the product of the initials of the polynomials in T_{x_{i}}^{−}. There exists an integer δ ≥ 0 and q ∈ P_{i} such that h^{δ}p^{m} = qt + prem(p^{m}, t). Let I be the ideal generated by T in P_{i}. From (ii) we deduce prem(p^{m}, t) ∈ \sqrt{I : h′^{∞}}. Since qt ∈ I we get h^{δ}p^{m} ∈ \sqrt{I : h′^{∞}}. Since sat_{i}(T) = I : (hh′)^{∞}, it is easy to check that p ∈ \sqrt{sat_{i}(T)} and this completes the proof. □

Theorem 4.1. Let T be a regular chain in P_{i}. Then we have

Rep_{i}(T) = \sqrt{sat_{i}(T)}.

Proof. We first assume i = 0. According to Definition 4.1, we have T = ∅ and Rep_{i}(T) = {0}. On the other hand, from Definition 2.7, we have sat_{i}(T) = {0}. Since P_{i} is an integral domain, the result is obvious in that case. Now let i > 0. Since T_{x_{i}}^{−} is a regular chain, we can assume that the theorem is true for i − 1. If x_{i} ∉ algVar(T), then the equality easily follows from Proposition 4.1, Remark 4.1 and the final remark in Notation 4.2. We now assume x_{i} ∈ algVar(T). From Proposition 4.2, we have

Rep_{i}(T) = {p ∈ P_{i} | (∃m ≥ 0) prem(p^{m}, T_{x_{i}}) ∈ Rep_{i}( T_{x_{i}}^{−})}.

Since x_{i} ∉ algVar( T_{x_{i}}^{−}), we get from the previous case

Rep_{i}( T_{x_{i}}^{−}) = \sqrt{sat_{i}( T_{x_{i}}^{−})}.

Finally, the conclusion follows from Proposition 4.4 □

Proposition 4.5. If T is a regular chain in P_{i}, then T is consistent.

Proof. From Theorems 2.1 and 4.1, and from Hilbert theorem of zeros we only need to prove that Rep_{i}(T) ≠ P_{i}. It follows from Propositions 4.1 and 4.2 that 1 ∈ Rep_{i}(T) iff 1 ∈ Rep_{i−1}( T_{x_{i}}^{−}). Thus, since the statement is clear for i = 0, it also holds for any i. □

5. Towers of Simple Extensions

The notion of tower of simple extensions presented in this section generalize the usual notion of tower of field extensions. Towers of simple extensions and regular chains will appear in the final section as equivalent notions (Theorem 6.1). Moreover, the former concept is useful to present Lazard triangular sets (Lazard, 1991a) in a simple way. It is also convenient for presenting computations with multivariate polynomials modulo a regular chain as computations with univariate polynomials, especially when working with Lazard triangular sets (Moreno Maza, 1997).

Let us give first an idea of this notion, before introducing a precise definition (Definition 5.2). Given a tower of simple extensions, for i = 1 … n − 1, if A_{i−1} is a floor in this tower, the next floor A_{i} is built by applying one of the following rules:

(i) A_{i} = fr(A_{i−1}[x_{i}]), (ii) there exists a non-constant and monic t_{i} ∈ A_{i−1}[x_{i}] such that A_{i} = fr(A_{i−1}[x_{i}]/⟨t_{i}⟩).

Since A_{0} = k, if each t_{i} is irreducible as a polynomial in A_{i−1}[x_{i}] then A_{n} is a field and there exists a vprime ideal P in P_{n} such that A_{n} and fr(P_{n}/P) are isomorphic. Conversely, let P be a prime ideal in P_{n} and let A_{i} = fr(P_{i}/P_{i} ∩ P). If ξ_{i} is the image of x_{i} in A_{i}, then A_{i} = A_{i−1}(ξ_{i}) is a simple field extension. Thus, there is an one-to-one correspondence between towers of field extensions (of k with n floors) and prime ideals (of P_{n}). Therefore varieties can be represented by describing the towers of field extensions of their irreducible components. These towers of field extension are given in Lazard (1991a) by Lazard triangular sets.

More generally, Theorem 6.1 will state that towers of (ring) simple extension correspond to regular chains. In order to show it, we need to introduce an intermediate concept, namely the concept of a regular set. Regular sets are special fine triangular sets which naturally encode towers of simple extensions. Note that each one of the above t_{i} can be viewed as a polynomial in P_{i−1}[x_{i}] and that the set of the t_{i} is a triangular set.

Definition 5.1 presents the inverse construction: from a suitable triangular set to a tower of simple extensions. Proposition 5.1 is an important step to establish Theorem 6.1: it states that if T is a regular set in P_{n} then sat(T) and red_{↦0}(T) are the same objects. Finally, the main result of this section is Theorem 5.1: it can be viewed as an analogous result of Theorem 4.1 but stated for regular sets.

The results of this section appear in (Moreno Maza, 1997) and Proposition 5.1 is also established in (Wang, 1998b).

Notations 5.1. Let A_{0}, A_{1}, …, A_{n} be commutative rings with units such that k = A_{0} and A_{i−1} is a sub-ring of A_{i} for i ∈ {1, …, n}. Let x_{n+1} be an additional variable and put P_{n+1} = k[x_{1}, …, x_{n+1}]. Let F_{0} be the identity map of P_{1}. Finally, for i ∈ {1, …, n}, let F_{i} be an algebra homomorphism from P_{i+1} onto A_{i}[x_{i+1}] such that F_{i}(x_{i+1}) = x_{i+1}.

Definition 5.1. Let T be a triangular set of P_{i}. The set T is a regular set of P_{i} whose associated map is (F_{0}, …, F_{i}) and whose associated tower of simple extensions is (A_{0}, …, A_{i}) if one of the following conditions holds:

(i) i = 0 and the set T is empty, (ii) i > 0, the set T_{x_{i}}^{−} is a regular set of P_{i−1} whose associated map is (F_{0}, …, F_{i−1}) and whose associated tower of simple extensions is (A_{0}, …, A_{i−1}) such that one of the two assertions holds:

(a) x_{i} ∉ algVar(T) and we have A_{i} = fr(A_{i−1}[x_{i}]) and for every p ∈ P_{i}, the

element F_{i}(p) is the canonical image of F_{i−1}(p) in A_{i},

(b) x_{i} ∈ algVar(T), the element F_{i−1}(init( T_{x_{i}})) is a unit in A_{i−1}, and we have A_{i} = fr(A_{i−1}[x_{i}]/⟨t_{i}⟩) and, for every p ∈ P_{i}, the element F_{i}(p) is the canonical

image of \overline{F_{i−1}(p)}⟨t_{i}⟩ in A_{i} where t_{i} denotes F_{i−1}( T_{x_{i}}).

Definition 5.2. The sequence (A_{0}, …, A_{i}) is called a tower of simple extensions of k (t.o.s.e. for short) if there exists a regular set of P_{i} whose associated tower of simple extensions is (A_{0}, …, A_{i}).

Example 5.1. Assume n ≥ 4. The subset T_{1} (Example 2.2) is not a regular set of P_{n} whereas T_{x_{4}}^{−} is one: since F_{2}( T_{x_{3}}) = (x_{1}x_{3} − 1)^{2} the element F_{2}(init( T_{x_{4}})) = (x_{1}x_{3} − 1) is nilpotent in A_{3} where (A_{0}, …, A_{n}) denotes the associated t.o.s.e. of T_{x_{4}}^{−}.

Remark 5.1. Let T ⊆ P_{i} be a regular set whose associated t.o.s.e. is (A_{0}, …, A_{i}) and whose associated map is (F_{0}, …, F_{i}). For 0 ≤ j ≤ i and x ∈ A_{j}, note that x is either a unit in A_{j} or a zero-divisor in A_{j}. Moreover, if j < i and if x is a unit in A_{j} then it is also a unit in A_{j+1}. Proposition 5.2 characterizes the units of A_{i} whereas Proposition 5.1 characterizes the kernel of F_{i}, and, consequently the zero-divisors of A_{i}.

Proposition 5.1. Let T ⊆ P_{i} be a regular set whose associated t.o.s.e. is (A_{0}, …, A_{i}) and whose associated map is (F_{0}, …, F_{i}). Then, for every p ∈ P_{i} the following three conditions are equivalent:

(i) F_{i}(p) = 0, (ii) prem(p, T) = 0, (iii) p ∈ sat_{i}(T).

Proof. We prove that the above assertions are equivalent by induction on i. We first assume i = 0. By virtue of Definition 5.1, we have F_{0}(p) = 0 ⟺ p = 0. Moreover we have T = ∅ and thus prem(p, T) = 0 ⟺ p = 0. On the other hand, we have sat_{0}(T) = {0} from Definition 2.7. It follows that the result is obvious in this case. Now let i > 0. Since T_{x_{i}}^{−} is a regular set, we can assume that the result is true for i − 1. Following Definition 5.1, we distinguish two cases: x_{i} ∉ algVar(T) and x_{i} ∈ algVar(T). First we assume x_{i} ∉ algVar(T). From Definition 5.1, we obviously have

F_{i}(p) = 0 ⟺ F_{i−1}(p) = 0.

Regarding p as a univariate polynomial in P_{i−1}[x_{i}], we get by the induction hypothesis

F_{i−1}(p) = 0 ⟺ p ∈ sat_{i−1}( T_{x_{i}}^{−})[x_{i}] ⟺ prem(p, T_{x_{i}}^{−}) = 0.

Since sat_{i}(T) = sat_{i−1}(T)[x_{i}] we obtain the desired result.

Now we assume x_{i} ∈ algVar(T). We define t = T_{x_{i}}, h = init(t) and r = prem(p, t). From Definition 5.1 and Remark 5.1 the element F_{i}(h) of A_{i} is a unit and we have F_{i}(t) = 0. Thus we easily get

F_{i}(p) = 0 ⟺ F_{i}(r) = 0.

From Definition 5.1 we have

F_{i}(r) = 0 ⟺ F_{i−1}(r) ∈ ⟨F_{i−1}(t)⟩.

Since deg(r, x_{i}) < mdeg(t) and since F_{i−1}(t) is monic, we obtain from Remark 4.1

F_{i}(r) = 0 ⟺ F_{i−1}(r) = 0.

Regarding r as a univariate polynomial in P_{i−1}[x_{i}], we get by the induction hypothesis

F_{i−1}(r) = 0 ⟺ r ∈ sat_{i−1}( T_{x_{i}}^{−})[x_{i}] ⟺ prem(r, T_{x_{i}}^{−}) = 0.

Since prem(p, T) = prem(r, T_{x_{i}}^{−}) we easily get

F_{i}(p) = 0 ⟺ prem(p, T) = 0.

Thus, we have by Proposition 2.3

F_{i}(p) = 0 ⟹ p ∈ sat_{i}(T).

Conversely, assume p ∈ sat_{i}(T). We denote by h′ the product of the initials of the polynomials in T_{x_{i}}^{−}. Thus there exists an integer m ≥ 0 such that (hh′)^{m}p ∈ ⟨T ⟩. From Remark 5.1 the element F_{i}(hh′) is a unit in A_{i}. Moreover we have (∀t ∈ T) F_{i}(t) = 0. Finally we obtain

p ∈ sat_{i}(T) ⟹ F_{i}(p) = 0.

□

Theorem 5.1. Let T ⊆ P_{i} be a regular set whose associated t.o.s.e. is (A_{0}, …, A_{i}) and whose associated map is (F_{0}, …, F_{i}). Then we have

A_{i} ≅ fr(P_{i}/sat_{i}(T)).

Proof. If i = 0 the result is trivial. So, we assume i > 0. Recall that F_{i−1} is a surjective algebra homomorphism from P_{i} onto A_{i−1}[x_{i}] such that F_{i−1}(x_{i}) = x_{i}. From Proposition 5.1 we know that for p ∈ P_{i−1} we have

F_{i−1}(p) = 0 ⟺ p ∈ sat_{i−1}( T_{x_{i}}^{−}).

Thus, the kernel of F_{i−1} is sat_{i−1}( T_{x_{i}}^{−})[x_{i}] and we have

A_{i−1}[x_{i}] ≅ P_{i}/(sat_{i−1}( T_{x_{i}}^{−})[x_{i}]).

If x_{i} ∉ algVar(T), we know that sat_{i−1}( T_{x_{i}}^{−})[x_{i}] = sat_{i}(T). Moreover, from Definition 5.1, we have A_{i} = fr(A_{i−1}[x_{i}]) Thus we get the desired isomorphism. The same conclusion easily follows if x_{i} ∈ algVar(T). □

Proposition 5.2. Let T ⊆ P_{i} be a regular set whose associated t.o.s.e. is (A_{0}, …, A_{i}) and whose associated map is (F_{0}, …, F_{i}). Let p be an element of P_{i}. Then F_{i}(p) is a unit in A_{i} iff for every prime ideal P associated to sat_{i}(T) we have p ∉ P.

Proof. From Remark 5.1 we know that F_{i}(p) is a unit in A_{i} iff it is not a zero-divisor in A_{i}. From Theorem 5.1 F_{i}(p) is a zero-divisor in A_{i} iff the class of p in P_{i}/sat_{i}(T) is a zero-divisor. Thus the statement follows from the following classical remark. For an ideal I in a Noetherian ring A, for x ∈ A, the class of x in A/I is a zero-divisor iff there exists a prime ideal P associated with I such that x belongs to P. See vol.1, p.214 in Samuel and Zariski (1967). □

6. The main result

Theorem 6.1. For any non-empty triangular set T ⊆ P_{n} the following four conditions are equivalent:

(i) T is a regular chain in P_{i}, (ii) T is a regular set in P_{i}, (iii) red_{↦0}(T) = sat_{i}(T), (iv) T is a Ritt characteristic set of sat_{i}(T).

Proof. From Proposition 5.2 and Theorem 4.1 we easily get (i) ⟺ (ii). From Proposition 5.1 we have (ii) ⇒ (iii). We now prove (iii) ⟺ (iv). From Theorem 3.1 we have (iv) ⟺ sat_{i}(T) ⊆ red_{↦0}(T). Thus together with Proposition 2.3 we get (iii) ⟺ (iv). Finally we prove (iii) ⇒ (ii). We assume that (iii) holds and that (ii) does not. We can assume that T_{x_{i}}^{−} is a regular set in P_{i−1} and that T is not a regular set in P_{i}. So let (A_{0}, …, A_{i−1}) be the associated t.o.s.e. of T_{x_{i}}^{−} and let (F_{0}, …, F_{i−1}) be its associated map. We define t = T_{x_{i}} and h = init(t). Thus we assume that F_{i−1}(h) is a zero-divisor in A_{i−1}. In other words, there exists p ∈ P_{i−1} such that F_{i−1}(hp) = 0 and F_{i−1}(p) ≠ 0. From Proposition 5.1 we get

hp ∈ sat_{i−1}( T_{x_{i}}^{−}) and prem(p, T_{x_{i}}^{−}) ≠ 0.

We define r = prem(p, T_{x_{i}}^{−}). Note that we also have hr ∈ sat_{i−1}( T_{x_{i}}^{−}) and then r ∈ sat_{i}(T). Consequently we have found a polynomial r ∈ P_{i−1} such that

r ∈ sat_{i}(T) and r ∉ red_{↦0}(T).

This contradicts (iii). □

Acknowledgements

We would like to thank Dongming Wang, Mike Dewar and the referees for their helpful suggestions on an earlier version of this paper. The third author is also grateful to the European research project FRISCO † for supporting his work.

References

Aubry, P., Moreno Maza, M. (1997). Triangular sets for solving polynomial systems: a comparative

implementation of four methods. Presented at CoCoA V and submitted to J. Symb. Comp.. Boulier, F., Lazard, D., Ollivier, F., Petitot, M. (1995). Representation for the radical of a finitely

generated differential ideal. In proceedings of ISSAC’95, pages 158–166, Montréal, Canada. Boulier, F., Lazard, D., Ollivier, F., Petitot, M. (1997). Computing representations for radicals of finitely

generated differential ideals. Technical report, ref. IT–306, Université Lille I, 59655, Villeneuve d’Ascq, France. (submitted to the JSC).

Bourbaki (1961). Algèbre Commutative, chapter 2. Herman, Paris. Chou, S., Gao, X. (1990). Ritt-Wu’s decomposition algorithm and geometry theorem proving. In Proc.

CADE-10, pages 202–220, Kaiserslautern, Germany. Chou, S., Gao, X. (1991a). Computations with parametric equations. In Proc. ISAAC’91, pages 122–127,

Bonn, Germany. Chou, S., Gao, X. (1991b). On the dimension of an arbitrary ascending chain. Chinese Bull. of Sci.,

38:799–804. Chou, S., Gao, X. (1992). Solving parametric algebraic systems. In Proc. ISAAC’92, pages 335–341,

Berkeley, California.

† A Framework for Integrated Symbolic/Numeric Computation. Esprit Scheme Project No. 21 024 Cox, D., Little, J., O’Shea, D. (1991). Ideals, Varieties, and Algorithms. Spinger-Verlag. Gallo, G., Mishra, B. (1990). Efficient algorithms and bounds for Wu-Ritt characteristic sets. In Proc.

MEGA’90, pages 119–142. Gallo, G., Mishra, B. (1991). Wu-Ritt characteristic sets and their complexity. In J.E. Goodman, R.

Pollack and W. Steiger, editor, Discrete and Computational Geometry: Papers from the DIMACS Special Year, volume 6 of Dimacs Series in Discrete Mathematics and Theoretical Computer Science, pages 111–136. American Mathematical Society and Association for Computing Machinery.

Kalkbrener, M. (1987). Solving systems of algebraic equations by using Gröbner basis. Lecture Notes in

Computer Science, 378:282–292. Kalkbrener, M. (1991). Three contributions to elimination theory. PhD thesis, Johannes Kepler Univer-

sity, Linz. Kalkbrener, M. (1993). A generalized euclidean algorithm for computing triangular representations of

algebraic varieties. J. Symb. Comp., 15:143–167. Kalkbrener, M. (1998). Algorithmic properties of polynomial rings. JSC, 26(5):525–581. Lazard, D. (1991a). A new method for solving algebraic systems of positive dimension. Discr. App.

Math, 33:147–160. Lazard, D. (1991b). Systems of algebraic equations (algorithms and complexity). In Eisenbud, Robbiano,

editors, Cortona proceedings. Cambridge University Press. Lazard, D. (1992). Solving zero-dimensional algebraic systems. J. Symb. Comp., 15:117–132. Moreno Maza, M. (1997). 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. Moreno Maza, M. (1998). A new algorithm for computing triangular decompositions of algebraic varieties.

Technical Report TR 4/98, NAG Ltd, Oxford, UK. Moreno Maza, M., Rioboo, R. (1995). Polynomial gcd computations over towers of algebraic extensions.

In Proc. AAECC-11, pages 365–382. Springer. Ritt, J. (1932). Differential equations from an algebraic standpoint, volume 14. American Mathematical

Society, New York. Ritt, J. (1966). Differential Algebra. Dover Publications, Inc., New York. Samuel, P., Zariski, O. (1967). Commutative algebra. D. Van Nostrand Company, INC. Wang, D. M. (1992). Some improvements on Wu’s method for solving systems of algebraic equations. In

Wen-Tsün, W., Min-De, C., editors, Proc. of the Int. Workshop on Math. Mechanisation, Beijing, China. Institute of Systems Science, Academia Sinica.

Wang, D. M. (1993). An elimination method for polynomial systems. J. Symb. Comp., 16:83–114. Wang, D. M. (1995). An implementation of the characteristic set method in Maple. In Pfalzgraf, J.,

Wang, D. M., editors, Automated practical reasoning: algebraic approaches, pages 187–201. Springer, Wien.

Wang, D. M. (1998a). Decomposing Polynomial Systems into Simple Systems. JSC, 25(3):295–314. Wang, D. M. (1998b). Elimination Methods. Springer. (in press). Wu, W. T. (1984a). Basic principles of mechanical theorem proving in elementary geometries. J. Sys.

Sci. and Math. Scis, 4:207–235. Wu, W. T. (1984b). Some recent advances in mechanical theorem-proving of geometries. Contemporary

Math., 29:235–241. Wu, W. T. (1986). On zeros of algebraic equations – an application of Ritt principle. Kexue Tongbao,

31(1):1–5. Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints,

1:2–12. Yang, L., Zhang, J. (1994). Searching dependency between algebraic equations: an algorithm applied

to automated reasoning. In Johnson, J., McKee, S., Vella, A., editors, Artificial intelligence in mathematics, pages 147–156. Oxford University Press.