FACTORIZATION FREE DECOMPOSITION ALGORITHMS IN DIFFERENTIAL ALGEBRA

EVELYNE HUBERT

Abstract. We present an effective version of Ritt’s algorithm. We apply material of (Boulier et al. 1995) for which we give new concise proofs. We present original results in constructive algebra that makes the algorithm flexible and simple.

1. Introduction

We present an algorithm to compute a representation of the radical differential ideal generated by a system of differential equations (ordinary or partial). The method we use here involves characteristic set techniques^{1}; these were introduced by J.F. Ritt, the founder of differential algebra. The basic idea is to write the radical differential ideal generated by a finite set Σ of differential polynomials as an intersection of (radical) differential ideals that are uniquely defined by their characteristic sets. We will call these latter differential ideals components of {Σ} and we will call their intersection the characteristic decomposition of {Σ}.

With a characteristic decomposition of {Σ} we can decide membership to {Σ} and study the dimension properties of {Σ}. By choosing an appropriate ranking, an algorithm to compute a characteristic decomposition can also answer questions like: do the solutions of Σ = 0 satisfy

- an algebraic equation? Find all such constraints.

- an ordinary differential equation in one of the independent variables? Find these ordinary differential equations.

- a differential equation involving only a specific dependent variable? Find these differential equations.

Ritt (1950) gave an algorithm to compute a characteristic decomposition of {Σ} where the components are prime differential ideals. Boulier (1994, 1995) pioneered an effective approach to the problem of the representation of a radical differential ideal generated by a finite set of differential polynomial. Evolving from Seidenberg’s elimination theory, the version of the Rosenfeld-Groebner algorithm presented in (Boulier et al. 1997) does compute a characteristic decomposition of {Σ}. In the ordinary case Maârouf et al. (1998) provided means to compute a characteristic decomposition. All these methods work by interweaving differential reductions with algebraic operations. The algebraic operations are factorization over towers of algebraic extensions in (Ritt 1950), Groebner bases in (Boulier et al. 1997) and computation of inverse polynomials in towers of algebraic extensions in (Maârouf et al. 1998).

In this paper we rework Ritt’s approach to establish that the same algebraic results as the ones uncovered by Boulier et al. (1995, 1997) can be applied to make this approach effective. We furthermore present some new and concise proofs of these results (Theorem 3.1, Theorem 3.2, Theorem 4.3, Theorem 4.4).

The main original contribution of this paper is to provide the tool (Theorem 6.2) that enables one to decouple completely the typically differential operations from the purely algebraic operations. We also show that all the purely algebraic operations can be done in dimension zero (Theorem 3.10). In our opinion, this paper clarifies and simplifies the essence of the algorithms in differential algebra and sets the framework for improving independently the separated pieces, differential reductions on the one hand and the algebraic operations in dimension zero on the other hand.

Research at MSRI is supported in part by NSF grant DMS-9701755.

1differential analogues of Groebner bases techniques were studied by Carra’Ferro (1987), Mansfield (1991) and Ollivier (1990)

In the course of the paper, the notion of characteristic presentation is quite central. This notion was introduced in (Boulier et al. 1997). We will give in this paper a necessary and sufficient conditions for the existence of a characteristic presentation in different contexts (Lemma 3.5, Lemma 3.9, Lemma 6.1). The basic condition of Lemma 3.5 is in fact much simpler and more efficient than the sufficient condition obtained in (Boulier et al. 1997) and establishes the connection there is between a characteristic presentation and a Groebner basis.

The purely algebraic method proposed here is based on Groebner bases computations of zero dimensional radical ideals. These are widely known and well studied. Using a simple heuristic preprocessing - as the ones presented in the appendix - the Groebner bases computations are in fact no longer the bottleneck of our implementation. We nonetheless expect that triangular set techniques, as in (Kalkbrener 1993) and (Lazard 1992), will provide an efficient and aesthetically more consistent substitute to Algorithm 3.8. The description of the output reflects such a concern: we dictate the properties that should be achieved to carry on in the algorithm.

Though we shall, in this article, compute irredundant decomposition of coherent components, the complete decomposition computed are not generally minimal - neither is the decomposition of Ritt, Boulier or Rody. Only for the case where Σ consists of a single differential polynomial are there known algorithms to eliminate the redundancy in the decomposition (Ritt 1936), (Kolchin 1973), (Hubert 1998).

In this paper, we adhere to the traditional mathematical objects of differential algebra, such as autoreduced sets and characteristic sets. The underlying reason is, on the one hand, to highlight the basic scheme of a decomposition algorithm, and, on the other hand, keep the paper of reasonable size and self-contained in the sense that only reference to textbooks - mainly (Kolchin 1973) - is required. There is no question, nonetheless, that we benefitted of the recent work of (Boulier et al. 1997), (Maârouf et al. 1998). The readers should also be aware that generalizations of the definitions and consequences of coherence, autoreduced sets, characteristic sets have been studied by Boulier et al. (1997) and Morrison (1999). These generalizations can actually be smoothly incorporated in the framework of the present paper.

Readers interested in using a simple interfaced implementation of the Rosenfeld-Groebner algorithm, modified according to the contributions of this paper, are invited to visit the web site http://daisy.uwaterloo.ca/˜ ehubert/Diffalg. From there they can load the maple v package diffalg(2) developed by F. Boulier and the author during their postdoctoral stays at the Symbolic Computation Group, University of Waterloo. Examples of use and applications will also be found there.

Given a finite set of differential polynomials Σ, we show in Section 5 how to compute a first decomposition of {Σ}, a decomposition into coherent components, with differential reductions. This is the differential part of the algorithm. The rest of the algorithm requires no further differentiation.

In Section 6, the properties and the irredundant characteristic decomposition of a coherent component are shown to be the lifting to the differential case of properties and decomposition of ideals defined by autoreduced sets in a finitely generated polynomial algebra. We thus start our investigations around the properties of such ideals; This is the purpose of Section 3. This section also details the purely algebraic part of the algorithm.

Section 2 mainly recollects the definitions and basic results in differential algebra. Section 7 recapitulates the complete algorithm.

2. Differential ideal theory

Differential algebra extends the concepts of polynomial algebra to differential equations. The purpose of this section is to give the basic information for reading this paper. We base our paper on the material found in (Kolchin 1973). We will recall the definitions to ease the reading but we will omit the proofs to lighten the paper. More detailed presentation can be found in (Ritt 1950), (Kaplansky 1970), (Kolchin 1973), (Boulier 1994), (Hubert 1997). The reader already familiar with (Kolchin 1973) - more specifically with the characteristic zero version of it - needs only to look at the definition of characteristic presentation and decomposition and the notation S^{∞}.

2.1. Ring of differential polynomials. We consider differential rings (R, Θ), where R is a commutative integral domain that contains a field isomorphic to ℚ, and Θ is the free commutative monoid of derivation operators generated by a finite set of derivations Δ. When Δ consists of a single derivation δ we shall speak of the ordinary differential ring R.

Let Σ be a subset of R. We denote respectively [Σ] and {Σ} the differential ideal and the radical differential ideal generated by Σ.

(R{Y }, Θ) denotes the ring of differential polynomials with differential indeterminates Y = {y_{1}, …, y_{n}} and coefficients in (R, Θ). In ring theoretic terms, R{Y } is the polynomial ring in infinitely many indeterminates R[ΘY] = R[{θy_{i}, y_{i} ∈ Y, θ ∈ Θ}].

We will consider rings F{Y } of differential polynomials the coefficients of which belong to a differential field F of characteristic zero. For computational purposes we will typically choose a rational function field F = K(t_{1}, …, t_{μ}) where K is a finite extension of ℚ.

Any radical differential ideal R in F{Y } is the intersection of a finite set of prime differential ideals none of which contains another (Kolchin 1973, III.4, the basis theorem and 0.9 Theorem 1). This unique set is the set of essential prime components of R and forms the minimal prime decomposition of R.

Let S be a subset of F{Y }. We denote by S^{∞} the multiplicative free monoid generated by 1 and the irreducible factors of the element of S. Let I be a differential ideal of F{Y }. We define the saturation of I by a set S as I : S^{∞} = {q ∈ F{Y } | ∃ s ∈ S^{∞} s q ∈ I}. I : S^{∞} is also a differential ideal and we have I ⊂ I : S^{∞}. This practical way of defining the saturation of an ideal originates in the work of Morrison (1999). When S is finite, we can match the usual definition by assigning s to the product of its elements. What we call I:S^{∞} is in fact equal to {q ∈ F{Y } | ∃ α ∈ ℕ s^{α} q ∈ I} that is usually denoted I:s^{∞}.

Consider a prime differential ideal P of F{Y }. P : S^{∞} is either equal to P or F{Y } according to whether S ∩P is empty or not. As a consequence, if R is a radical differential ideal of F{Y }, R:S^{∞} is the intersection of the essential components of R that have an empty intersection with S.

Proposition 2.1. Let Σ be a non-empty subset of R.

- Let a_{1}, …, a_{r} ∈ R. We have {Σ, ∏_{i=1}^{r} a_{i}} = ⋂_{i=1}^{r}{Σ, a_{i}}

- Let S be a finite subset of R. We have {Σ} = {Σ}:S^{∞} ∩ (⋂_{s∈S} {Σ, s}) .

2.2. Reduction. A ranking over F{Y } is a total order on ΘY = {θy_{i}, i = 1, …, n, θ ∈ Θ} such that for any derivative u ∈ ΘY we have δu ≥ u, ∀δ ∈ Δ and for any pair of derivatives u, v ∈ ΘY with u ≥ v we have δu ≥ δv, ∀δ ∈ Δ.

Let p be a differential polynomial of F{Y }. The leader u_{p} and the initial i_{p} of p are respectively the highest ranking derivative appearing in p and the coefficient of its highest power in p. The separant of p is s_{p} = \frac{∂p}{∂u_{p}}. θu_{p} and s_{p} are respectively the leader and the initial of θp when θ is a proper derivation operator (i.e. not the identity):

p = i_{p} u_{p}^{d} + i_{d−1} u_{p}^{d−1} + ⋯ + i_{0},
θp = s_{p}θu_{p} + q, where q has no derivative equal or higher than θu_{p}.

Any decreasing sequence of derivatives is finite (Kolchin 1973, I.8).

The rank of p is u_{p}^{d}. An element q ∈ F{Y } is said to have higher rank than p when its leader ranks higher than u_{p} or is equal but with higher degree in q. The ranking on the derivatives thus induces a partial order on the differential polynomials of F{Y }.

A differential polynomial q is partially reduced w.r.t. p if no proper derivatives of u_{p} appears in q; q is reduced w.r.t. p if q is partially reduced w.r.t. to p and the degree of q in u_{p} is strictly less then the degree of p in u_{p}.

Sparse pseudo-division: Let R[x] be a ring of polynomials with coefficients in the ring R. Let p, q ∈ R[x], d, e the respective degrees of p, q in x, c the coefficient of x^{d} in p. The pseudo-remainder of q w.r.t. p is defined as the polynomial q̄ such that deg_{x} q̄ < deg_{x} p and c^{e−d} q ≡ q̄ mod p when e ≥ d. A sparse pseudo-remainder is usually defined by taking a power of c as small as possible. What we will call a sparse pseudo-remainder of q with respect to p is a polynomial srem(q, p, x) of degree in x strictly lower than that p such that ∃h ∈ c^{∞} such that h q ≡ srem(q, p) mod p; h is taken as small as possible to limit the expressions swell. R is usually a ring of polynomials over a field and we shall use gcd computations to find srem(q, p, x) and h.

Differential reduction: Let p and q be differential polynomial in F{Y }; With differentiation and sparse pseudo division we can compute d-prem(q, p) and d-rem(q, p) respectively partially reduced and reduced with respect to p such that ∃s ∈ (s_{p})^{∞} and h ∈ (s_{p} i_{p})^{∞} such that s q ≡ d-prem(q, p) mod [p] and h q ≡ d-rem(q, p) mod [p].

Algorithm 2.2. d-rem ( or d-prem )

input: p, q ∈ F{Y }

output: q̄ (partially) reduced w.r.t. p and such that ∃h ∈ (s_{p} i_{p})^{∞} (or s_{p}^{∞}), h q ≡ q̄ mod [p].

q̄ := q;

While q is not (partially) reduced w.r.t. p do θu_{p} := the highest ranking derivative of u_{p} in q. q̄:= srem(q̄, θp, θu_{p});

od;

2.3. Auto-reduced sets and characteristic presentations. Let F{Y } be endowed with a ranking. A subset A of F{y_{1}, …, y_{n}} is called autoreduced set if no element of A belongs to F and each element of A is reduced w.r.t. all the others. Distinct elements of A have distinct leaders and A must be finite^{2}. We denote

- I_{A} the set of the initials of the elements of A;

- S_{A} the set of the separants of the elements of A;

- H_{A} = I_{A} ∪ S_{A}.

- 𝔏(A) the set of the leaders of the elements of A.

- 𝔑(A) the set of derivatives present in A that are not the leaders of elements of A.

Thus 𝔏(A) ∪ 𝔑(A) is the finite subset of ΘY of the derivatives present in A.

For an autoreduced set A, (A) denotes the ideal generated by A in the finitely generated polynomial algebra F[𝔏(A) ∪ 𝔑(A)]. Note that H_{A} ⊂ F[𝔏(A) ∪ 𝔑(A)] so that (A) : I_{A}^{∞}, (A) : S_{A}^{∞}, (A) : H_{A}^{∞} are also understood to be ideals in this algebra.

A differential polynomial is said to be (partially) reduced w.r.t. an autoreduced set A when it is (partially) reduced w.r.t. each element of A. Given an element q ∈ F{Y } we can compute h ∈ H_{A}^{∞} and d-rem(q, A) that is reduced w.r.t. A such that h q ≡ d-rem(q, A). Similarly, we can compute s ∈ S_{A}^{∞} and d-prem(q, A) that is partially reduced w.r.t. A such that s q ≡ d-prem(q, A).

Algorithm 2.3. d-rem (or d-prem ) .

input: q ∈ F{Y }, A ⊂ F{Y } an autoreduced set , a ranking on F{Y }.

output: q̄ (partially) reduced w.r.t. A and such that ∃h ∈ H_{A}^{∞} (or ∈ S_{A}^{∞}) such that h q ≡ q̄ mod [A]. q̄ := q; While q is not (partially) reduced w.r.t. A do

a := an element of A s.t. q̄ is not reduced w.r.t. a. q̄:= d-rem(q̄, a) (or d-prem(q̄, a));

od;

A ranking on F{Y } induces a partial order on the autoreduced sets of F{Y }. Let A = a_{1}, …, a_{r} and B = b_{1}, …, b_{s} be autoreduced sets arranged in order of increasing rank. A is said to be of lower rank than B when either - there exists 1 ≤ k ≤ r, s such that the rank of a_{i} and b_{i} are the same for 1 ≤ i ≤ k − 1 and the rank of

2(Kolchin 1973, I.9)

a_{k} is less than the rank of b_{k}.

- r > s and the rank of a_{i} is equal to the rank of b_{i}, 1 ≤ i ≤ s.

Definition 2.4. An autoreduced set A in F{Y } is a characteristic set of a differential ideal I if one of the following equivalent conditions holds:

- A is an autoreduced set of minimal rank among the autoreduced sets of I.

- A ⊂ I and ∀q ∈ I, d-rem(p, A) = 0.

- there is no non zero element of I reduced w.r.t. A.

Thus, any two characteristic sets of a differential ideal have the same rank. Every differential ideal I admits a characteristic set^{3}. If A is a characteristic set of the differential ideal I in F{Y } then [A] ⊂ I ⊂ [A]:H_{A}^{∞}. When A is a characteristic set of [A]:H_{A}^{∞} then q ∈ [A]:H_{A}^{∞} ⇔ d-rem(q, A) = 0.

Example 2.5. Consider, in F{x, y} endowed with a ranking such that x < y, the autoreduced set A = (x − 1) y − 1, x^{2} − 1. Note that (x + 1) ∈ [A]:H_{A}^{∞} though it is not reduced w.r.t. A. An autoreduced set A is not obviously a characteristic set of [A]:H_{A}^{∞} nor of (A):H_{A}^{∞}.

Example 2.6. A = u_{xy} − u, u_{xx} is an autoreduced set of ℚ(x, y){u}, endowed with derivation according to x and y. It is a characteristic set of (A):H_{A}^{∞}. But δ_{x}(u_{xy} − u) − δ_{y}(u_{xx}) = u_{x} ∈ [A]:H_{A}^{∞} is not reduced to 0 by A. An autoreduced set A that is a characteristic set of (A):H_{A}^{∞} is not obviously a characteristic set of [A]:H_{A}^{∞} when dealing with partial differential polynomials.

Definition 2.7. Let F{Y } be endowed with a ranking. An autoreduced set is a characteristic presentation if A is a characteristic set of [A]:H_{A}^{∞}. A differential ideal is said to be characterizable if for a characteristic set A of I we have I = [A]:H_{A}^{∞}. We say that A is a characteristic presentation of I.

Prime differential ideals are characterizable for any ranking. Furthermore, any characteristic set of a prime differential ideal is a characteristic presentation of it. These are the properties that Ritt (1950) and Kolchin (1973) used in their work. Recent algorithmic improvement in differential algebra owes to the idea of using a wider class of differential ideals than prime differential ideals. And, indeed characterizable differential ideal that are not prime do exist; But, this then depends on the ranking (see Example 3.6). We will see that a characterizable differential ideal is radical (Theorem 4.3) and has specific dimension properties (Theorem 4.4).

2.4. Characteristic decomposition - Definition. Let R be a radical differential ideal of F{Y }. We call a characteristic decomposition of R a representation of R as an intersection of characterizable differential ideals, called components of {Σ}. Such a characteristic decomposition of R exists: R is the intersection of prime differential ideals and prime differential ideals are characterizable.

Given a finite set Σ of differential polynomials of F{Y }, computing a characteristic decomposition of {Σ} means finding a characteristic presentation of its components. In other words, given Σ, we want to compute characteristic presentations C_{1}, …, C_{r} such that {Σ} = ∩_{i=1}^{r}[C_{i}]:H_{C_{i}}^{∞}.

A characteristic decomposition of a radical differential ideal R will be said to be irredundant if associating each component in the decomposition with the set of its essential prime components yields a partition of the set of the essential prime components of R. In other words, consider a characteristic decomposition of R, R = ∩_{i=1}^{r}[C_{i}] : H_{C_{i}}^{∞}. This decomposition is irredundant if any prime differential ideal that contains two distinct components [C_{i}]:H_{C_{i}}^{∞} is not an essential prime component of R.

3. Results in finitely generated polynomial algebras

This section contains all the purely algebraic material needed to justify a decomposition algorithm in differential algebra. We work in a ring of polynomials in finitely many indeterminates x_{1}, …, x_{n} with coefficients in a field K of characteristic zero: K[X] = K[x_{1}, …, x_{n}]. The underlying ranking is given by x_{1} < … < x_{n}.

3(Kolchin 1973, I.10, Proposition 3)

The first subsection presents the properties of (non-differential) ideals (A):S_{A}^{∞} and (A):H_{A}^{∞}, where A is an autoreduced set of K[X]. The second and third subsections give an algorithm to compute an irredundant characteristic decomposition of an ideal defined by an autoreduced set. The decomposition of (A) : H_{A}^{∞} is completely done in dimension zero (Theorem 3.7, Algorithm 3.8) and then only lifted to positive dimension (Theorem 3.10). Theorem 3.10 is an original contribution of this paper.

We give a method to compute the decomposition in dimension zero. It relies on Groebner bases computations in dimension 0 (Algorithm 3.8). But this can easily be replaced without preturbing the rest of the results. In the development of this method, we nonetheless establish the connection there is between characteristic sets and Groebner bases (Lemma 3.5).

We shall assume, without loss of generality, that the set of indeterminates is equal to 𝔏(A) ∪ 𝔑(A) so that K[X] = K[x_{1}, …, x_{n}] = K[𝔑(A)][𝔏(A)]. We will denote K_{A} = K(𝔑(A)) and we will also consider the ring of polynomials K_{A}[𝔏(A)]. When there might be some confusion, the ideals taken in K[𝔑(A)][𝔏(A)] or in K_{A}[𝔏(A)] = K(𝔑(A))[𝔏(A)] will be subscripted with K or K_{A}.

3.1. Ideals defined by autoreduced sets. The definitions and properties presented in Section 2 are immediately transposed to polynomial algebra by setting the derivation to be the trivial one. In this section we give two fundamental properties of the ideals (A) : S_{A}^{∞} and (A) : H_{A}^{∞}, where A is an autoreduced set in K[X] = K[𝔑(A)][𝔏(A)]

The first property, Theorem 3.2, is essential in differential algebra to compute effectively a decomposition in coherent components (see Section 5). This property was first presented in a differential algebra context by (Boulier et al. 1995) under the name of Lazard’s lemma. Morrison (1999) proposes another proof. We give here a new and concise proof which makes the result a direct application of the Jacobian criterion for regularity. The second property, Theorem 3.2, will be used to reduce the computation in dimension zero. We claim no special originality in the proof of this result in comparison with the previous mentioned papers.

Theorem 3.1. Let A be an autoreduced set of K[X]. (A):S_{A}^{∞} is a radical ideal.

Proof. If Q is a primary ideal and S is a subset of K[X], Q:S^{∞} is either equal to Q or K[X] according to whether S has an empty intersection with \sqrt{Q} or not. Thus, for any ideal I and any subset S in a polynomial ring K[X], I:S^{∞} is equal to the intersection of those primary components of I with radical having an empty intersection with S.

The product of the separants of A, s_{A}, is the determinant of a maximal square submatrix of the Jacobian matrix of A. This is due to the triangular shape of A. Thus s_{A} belongs to the Jacobian ideal of (A).

If 1 ∈ (A) : S_{A}^{∞} the result is trivial. Assume 1 ∉ (A) : S_{A}^{∞}. By the Jacobian criterion for regularity (Vasconcelos 1998, corollay 5.2.1, page 127), the primary components of (A) with radical not containing the Jacobian ideal are prime. This is the case of all the primary components of (A) the intersection of which is equal to (A) : s_{A}^{∞}. We have (A) : s_{A}^{∞} = (A) : S_{A}^{∞}. Thus (A) : S_{A}^{∞} is an intersection of prime ideals; It is a radical ideal. □

Note that we can state the same result when considering a subset H of K[X] containing S_{A}. The primary components of (A):H^{∞} is a subset of the primary components of (A):S_{A}^{∞}. Thus (A):H^{∞} is also radical.

Theorem 3.2. Let A be an autoreduced set of K[X]. If 1 ∉ (A) : S_{A}^{∞} then any minimal prime of (A) : S_{A}^{∞} admits the set of non-leaders of A, 𝔑(A), as a transcendence basis. More specifically, any characteristic set of a minimal prime of (A):S_{A}^{∞} has the same set of leaders as A.

Proof. By (Kolchin 1973, 0.16, corollary 4), the minimal primes of (A) : S_{A}^{∞} admit the finite set of non leaders of A as a transcendence basis. Assume A = a_{1}, …, a_{r} is arranged in order of increasing rank. We can apply the same result to subsets A_{k} = a_{1}, …, a_{k}, 1 ≤ k ≤ r of A.

If P is a minimal prime of (A):H_{A}^{∞}, P ∩F[𝔑(A_{k}), 𝔏(A_{k})] is a prime ideal containing (A_{k}):H_{A_{k}}^{∞} and therefore one of its minimal prime P̄. P ∩ F[𝔑(A_{k}), 𝔏(A_{k})] and P̄ have the same dimension, and therefore are equal. P ∩ F[𝔑(A_{k}), 𝔏(A_{k})] is a minimal prime of (A_{k}):H_{A_{k}}^{∞}.

Thus P admits a characteristic set having the same set of leaders than A. □

Here again, we could replace S_{A} in the theorem by a set of polynomials containing S_{A}.

This theorem bears as immediate consequences the following facts: If A is an autoreduced set of K[X] and H is a subset of K[X] containing S_{A}, the extension of ((A):H^{∞})_{K} over K_{A} is a zero dimensional radical ideal of K_{A}[𝔏(A)]. Furthermore ((A):H^{∞})_{K_{A}} ∩ K[X] = ((A):H^{∞})_{K}.

We shall make now some comments on characteristic sets and presentations in a non-differential context. There are indeed slight differences due to the fact that no derivation occurs in the reduction process. If an autoreduced set A is a characteristic set of an ideal I then A ⊂ I ⊂ (A) : I_{A}^{∞}. It follows that if A is a characteristic set of (A):H_{A}^{∞} then (A):H_{A}^{∞} = (A):I_{A}^{∞} and therefore (A):I_{A}^{∞} is radical. We have in fact the following equivalence:

Proposition 3.3. Let A be an autoreduced set such that A is a characteristic set of (A):I_{A}^{∞}. Then (A):I_{A}^{∞} is radical if and only if (A):I_{A}^{∞} = (A):H_{A}^{∞}.

We will in fact use only this result in dimension zero to prove Theorem 3.10.

Proof. By Theorem 3.1, (A):H_{A}^{∞} is radical. Thus (A):I_{A}^{∞} = (A):H_{A}^{∞} ⇒ (A):I_{A}^{∞} is radical is immediate.

We shall prove first the other implication in dimension 0. Consider A as an autoreduced set of K(𝔑(A))[𝔏(A)]. The Jacobian ideal of (A) is generated by s_{A}, the product of the separants of A. By (Vasconcelos 1998, Theorem 5.4.2.), (A) : s_{A} = \sqrt{(A)} = (A). Thus (A) : H_{A}^{∞} = ((A) : S_{A}^{∞}) : I_{A}^{∞} = ((A) : s_{A}^{∞}) : I_{A}^{∞} = \sqrt{(A):I_{A}^{∞}} = (A):I_{A}^{∞}.

It is now enough to prove that (A) : I_{A}^{∞} has no zero divisor in K[𝔑(A)]. We first prove that (A) : I_{A}^{∞} is unmixed dimensional. Then we prove that 𝔑(A) is algebraically independent modulo any minimal prime of (A):I_{A}^{∞}.

(A):I_{A}^{∞} is the pull back of the image of (A) through the localization K[X] ⟶ L_{A} = I_{A}^{−1} K[X]. Let us note A = a_{1}, …, a_{n} and let u_{i} denote the leader of a_{i}. Each a_{i} introduces a new variable, u_{i}, and, considered as a univariate polynomial in u_{i}, it has one of its coefficient, its initial, invertible in L_{A}. Thus a_{i} can not divide zero modulo I_{A}^{−1} (a_{1}, …, a_{i−1}) (Eisenbud 1994, Gauss’ lemma). It follows that a_{1}, …, a_{n} is a L_{A}-regular sequence. Thus I_{A}^{−1} (A) is unmixed dimensional of dimension the cardinal of 𝔑(A) (Eisenbud 1994).

By hypothesis, (A):I_{A}^{∞} is radical. We have proved that all its minimal primes have dimension the cardinal of 𝔑(A). A minimal prime P of (A) : I_{A}^{∞} does not contain any initial of A. Therefore, for each 1 ≤ i ≤ n, the image of a_{i} modulo P ∩ K[𝔑(A), u_{1}, …, u_{i−1}] has a strictly positive degree in u_{i}. It follows that 𝔏(A) is algebraic over K[𝔑(A)] modulo P. Given the dimension of P, we conclude that 𝔑(A) is algebraically independent modulo P. It follows that ((A):I_{A}^{∞})_{K} = ((A):I_{A}^{∞})_{K_{A}} ∩ K[𝔑(A), 𝔏(A)]. □

In the course of a decomposition algorithm in differential algebra, we will have to compute an irredundant characteristic decomposition of some (A) : H_{A}^{∞} where A is an autoreduced set. The components of the decomposition will also need to be radical ideals. We shall therefore specialized our vocabulary to radical ideals. We will say that an ideal R is characterizable if it is radical and it admits a characteristic set A such that R = (A):I_{A}^{∞}. Similarly, an autoreduced set will be a characteristic presentation if A is a characteristic set of (A):I_{A}^{∞} and this ideal is radical, or, equivalently A is a characteristic set of (A):H_{A}^{∞}.

3.2. Characteristic decomposition of 0-dimensional radical ideals. In this section we will give a necessary and sufficient condition for a zero dimensional radical ideal to be characterizable. Using this criterion we give a process to compute an irredundant characteristic decomposition of a zero dimensional radical ideal.

We shall start with properties of zero dimensional radical ideal that are easy consequences of the Chinese remainder theorem.

Proposition 3.4. Let p be a polynomial and R be a zero dimensional radical ideal of K[x_{1}, …, x_{n}].

- if p does not divide zero modulo R, then p is invertible modulo R. If furthermore p ∈ K[x_{1}, …, x_{k}] there exists p̄ ∈ K[x_{1}, …, x_{k}] such that p̄p ≡ 1 mod R ∩ K[x_{1}, …, x_{k}].

- if p divides zero modulo R there exists p̄ ∈ K[X] such that p̄p ∈ R and p̄ + p is invertible modulo R.

Proof. R is the finite intersection of zero dimensional prime ideals, say R = M_{1} ∩ … ∩ M_{r}; these M_{i} are maximal ideals of K[X]. By the Chinese remainder theorem (Eisenbud 1994, exercise 2.6) there is an isomorphisms ϕ from K[X]/R to the product of fields K[X]/M_{1} × … × K[X]/M_{r}.

Therefore, any element of K[X]/R that is not a zero divisor admits an inverse. For 1 ≤ k ≤ n, let R_{k} = R ∩ K[x_{1}, …, x_{k}]. R_{k} is also a zero dimensional radical ideal. Let p ∈ K[x_{1}, …, x_{k}]. If p does not divide zero modulo R, then p does not divide zero modulo R_{k}; we can thus find p̄ ∈ K[x_{1}, …, x_{k}] such that p̄p ≡ 1 mod R

Let p′, p_{1}, …, p_{r} be the respective projections of p on K[X]/R, K[X]/M_{1}, …, K[X]/M_{r}. For 1 ≤ i ≤ r, let p̄_{i} = 0 if p_{i} ≠ 0 and p̄_{i} = 1 if p_{i} = 0. Let p̄′ ∈ K[X]/R be the unique element such that ϕ(p̄′) = (p̄_{1}, …, p̄_{r}). We have p̄′ p′ = 0 and ϕ(p̄′ + p′) = (p̄_{1} + p_{1}, …, p̄_{r} + p_{r}) where p̄_{i} + p_{i} ≠ 0 is invertible in K[X]/M_{i}. Let p̄ be a preimage of p̄′ through the projection K[X] ⟶ K[X]/R; it satisfies the property enunciated in the proposition. □

We proceed by giving a necessary and sufficient condition for a zero dimensional radical ideal to be characterizable. The idea of extracting a characteristic presentation from a Groebner basis originates in (Boulier et al. 1997). There only a sufficient condition was used. Our criterion is nonetheless much simpler and, together with its proof, makes precise the connection there exists between a Groebner basis and a characteristic presentation. The idea of inverting the initials, which we use to go from a characteristic set to the Groebner basis, owes to some extent to (Maârouf et al. 1998).

Lemma 3.5. Let R be a zero dimensional radical ideal of K[x_{1}, …, x_{n}]. R is characterizable for the ranking x_{1} < … < x_{n} iff its reduced Groebner basis, G, according to the lexicographic order x_{1} < … < x_{n}, has exactly n element. Then G is a characteristic presentation of R.

Before proving this theorem, it should be reminded that if G has exactly n elements this implies that the leading terms are x_{1}^{d_{1}}, …, x_{n}^{d_{n}}, for some d_{i} ∈ ℕ^{∗} (Becker and Weispfenning 1993, corollary 6.56).

Proof. If G has n elements then G is an autoreduced set and its elements have 1 as initial. It is furthermore of minimal rank and therefore is a characteristic set of R. We have (G) : I_{G}^{∞} = (G) = R so that G is a characteristic presentation of R.

Assume A = a_{1}, …, a_{n} is a characteristic set of R and R = (A):I_{A}^{∞}. The initials i_{1}, …, i_{n} of the elements of A do not divide zero modulo R. Let R_{k} = R ∩ K[x_{1}, …, x_{k}] , 1 ≤ k ≤ n. We have i_{1} ∈ K; let ī_{1} = 1/i_{1}. Let c_{1} = ī_{1} a_{1}; c_{1} ∈ R_{1} is monic and has the same rank as a_{1}. For 2 ≤ k ≤ n there exists ī_{k} ∈ K[x_{1}, …, x_{k−1}] such that i_{k} ī_{k} = 1 + q_{k} where q_{k} ∈ R_{k−1}. Let c_{k} = ī_{k}a_{k} − q_{k} x_{k}^{d_{k}}. Each c_{k} belongs to R, has the same rank as a_{k} and is monic in x_{k}. C = c_{1}, …, c_{n} is therefore a triangular set R of minimal rank. Thus C is a characteristic set of R. It follows that (C) ⊂ R ⊂ (C) : I_{C}^{∞}. The initials of C being 1, R = (C) = (C) : I_{C}^{∞} and C is a Groebner basis of R according to the lexicographic order x_{1} < … < x_{n} because the leading monomials have no common divisors. By autoreducing the element of C (note that here Ritt reduction is equivalent to Hironaka division), we obtain the unique reduced Groebner basis of R that is also a characteristic presentation of R. □

Example 3.6. Some radical zero dimensional ideals are not characterizable. Consider for instance R = (2 x_{1}^{2} + 3 x_{1} + 1, 2 x_{1} x_{2} + x_{2}, x_{2}^{2} − 2 x_{1} − 2) ∈ ℚ[x_{1}, x_{2}]. R is a zero dimensional radical ideal since R ∩ ℚ[x_{1}] and R ∩ ℚ[x_{2}] are generated by squarefree polynomials, respectively 2 x_{1}^{2} + 3 x_{1} + 1 and x_{2}^{3} − x_{2}.

The generators of R given above are a reduced Groebner basis for the lexicographical order where x_{1} < x_{2}. We see that this does not satisfy the condition of the previous proposition. R is not characterizable. Note nonetheless that R = (R, 2 x_{1}+1)∩R:(2 x_{1}+1) = (2 x_{1}+1, 2 x_{2}^{2}−1)∩(x_{1}+1, x_{2}). The two components of this decomposition are characterizable zero-dimensional ideals that are comaximal since 2 (x_{1} +1)−(2 x_{1} +1) = 1.

Note furthermore that the Groebner basis for the lexicographical order x_{2} < x_{1} is G′ = x_{2}^{3} − x_{2}, 2 x_{1} − x_{2}^{2} + 2. Thus R is characterizable for the ranking x_{2} < x_{1}.

Proposition 3.7. Every zero-dimensional radical ideal is the intersection of a finite number of pairwise comaximal characterizable zero dimensional radical ideals. Algorithm 3.8 computes such an irredundant characteristic decomposition.

The fact that a zero dimensional radical ideal is the intersection of pairwise comaximal radical ideals is easily proved: every zero-dimensional radical ideal is the intersection of a finite number of zero dimensional prime ideals. These admit a characteristic presentation and are maximal. This argument is nonetheless misleading in the sense that the components of an irredundant decomposition do not need to be prime. We give a constructive proof which justifies Algorithm 3.8.

Proof. Assume R is a zero dimensional radical ideal of K[X] that does not admit a characteristic presentation. Let G be the reduced Groebner basis according to the lexicographical order. One of the element g of G has its initial i_{g} which does belong to K. We claim that i_{g} is a zero divisor modulo R. Let x_{k} be the leader of g and d = deg_{x_{k}} g. Because G is reduced, there cannot be an element of G with leading monomial x_{k}^{e}, with e ≤ d. If i_{g} were not a zero divisor modulo R, there would exist ī_{g} ∈ K[x_{1}, …, x_{k−1}] such that ī_{g} i_{g} ≡ 1 mod R. Then ī_{g} g would be an element of R with leading monomial x_{k}^{d}. This cannot be since otherwise there would be an element of G with leading monomial dividing x_{k}^{d}.

Thus there exists ī_{g}, q ∉ R such that i_{g} ī_{g} ∈ R and q (ī_{g} + i_{g}) ≡ 1 mod R. Thus

- R = R:i_{g} ∩ R:ī_{g}. Indeed, if p ∈ R:i_{g} ∩ R:ī_{g} then (ī_{g} + i_{g}) p ∈ R and therefore p ∈ R.

- R:ī_{g} and R:i_{g} are comaximal because i ∈ R:ī_{g} and ī_{g} ∈ R:i_{g}. For this same reason, the inclusion of

R in both R:i_{g} and R:ī_{g} is strict.

We can thus construct growing sequences of zero dimensional radical ideals that cannot become stationary before we have obtained zero dimensional radical ideals that admit a characteristic presentation.

Furthermore (R, i_{g}) ⊂ R: ī_{g} and p ∈ R: ī_{g} ⇒ ī_{g} p + i_{g} p ∈ (R, i_{g}) ⇒ p ∈ (R, i_{g}), so that R: ī_{g} = (R, i_{g}). We do not need to actually compute ī_{g}. □

Algorithm 3.8. 0D-Irredundant-χ-Decomposition

input: R a zero dimensional radical ideal in K[X].

output: T = T_{1}, …, T_{r} a sequence of characteristic presentations of zero dimensional radical ideals

such that R = (T_{1}):I_{T_{1}}^{∞} ∩ … ∩ (T_{r}):H_{T_{r}}^{∞} and (T_{j}):I_{T_{j}}^{∞} + (T_{k}):I_{T_{k}}^{∞} = K[X], j ≠ k. G := the reduced Groebner basis of R w.r.t. to the lexicographical order. if G = {1} then

return (Null-Sequence) elif G has n elements then return (G)

else i := the initial of an element of G such that i ≠ 1 R_{1} := (R, i); R_{2} := R:i; T := 0D-irredundant-χ-decomposition (R_{1}, K[X]), 0D-irredundant-χ-decomposition (R_{2}, K[X]);

fi;

We invite the reader to refer to (Moreno-Maza 1997) and (Szanto 1998) to establish constructions that do not involve Groebner basis computations. The elements of the characteristic presentation T_{i} obtained by the above algorithm all have 1 as initial. It needs not be the case to be in a position to lift the result to positive dimension nor to the differential case. Also, this algorithm requires the input ideal R to be given in a way that a Groebner basis of it can be computed. The fact is that this algorithm needs to be in a position to deal with ideals given as saturations (A):H_{A}^{∞}, where A is an autoreduced set.

3.3. Lifting to positive dimension. This section shows how an irredundant characteristic decomposition of the ideal defined by an autoreduced set can be simply computed by the algorithm of the previous section, i.e. in dimension zero. This allows to make the necessary intermediate step between the differential case and the computations in dimension zero. This is an original and very practical result. We start by an easy criterion to determine when an autoreduced set is a characteristic presentation in positive dimension.

Lemma 3.9. Let A be an autoreduced set. A is a characteristic presentation in K[𝔑(A), 𝔏(A)] if and only if A is a characteristic presentation in K(𝔑(A))[𝔏(A)].

Proof. Recall from Theorem 3.2 that ((A):H_{A}^{∞})_{K_{A}} ∩ K[𝔑(A), 𝔏(A)] = ((A):H_{A}^{∞})_{K}.

Assume A is a characteristic set of ((A):H_{A}^{∞})_{K_{A}}. If ((A):H_{A}^{∞})_{K} contained a nonzero element reduced with respect to A, so would ((A):H_{A}^{∞})_{K_{A}}. Thus A is a characteristic set of ((A):H_{A}^{∞})_{K}

Assume A is a characteristic set of ((A):H_{A}^{∞})_{K}. Assume, for contradiction, there is a nonzero element p of ((A) : H_{A}^{∞})_{K_{A}} reduced with respect to A. Clearing out the denominators of p amounts to multiply p with some element of K[𝔑(A)]. Let p̄ be the result of this operation. Obviously p̄ is nonzero and reduced with respect to A and belongs to ((A):H_{A}^{∞})_{K_{A}} ∩ K[𝔑(A), 𝔏(A)] = ((A):H_{A}^{∞})_{K}. This contradict the hypothesis.

□

For this reason and Lemma 3.5, (A) : H_{A}^{∞} is characterizable iff its reduced Groebner basis with respect to the lexicographic ordering on K_{A}[𝔏(A)] induced by the ranking has exactly as many elements as 𝔏(A).

Theorem 3.10. Let A be an autoreduced set of K[X]. Let ((A):H_{A}^{∞})_{K_{A}} = (T_{1}) : I_{T_{1}}^{∞} ∩ … ∩ (T_{r}) : I_{T_{r}}^{∞} be a (zero dimensional) irredundant characteristic decomposition in K_{A}[𝔏(A)]. For 1 ≤ i ≤ r, let C_{i} in K[X] be obtained from T_{i} by clearing out the denominators. Then ((A):H_{A}^{∞})_{K} = (C_{1}) : I_{C_{1}}^{∞} ∩ … ∩ (C_{r}) : I_{C_{r}}^{∞} is an irredundant characteristic decomposition in K[X].

Proof. C_{i} is a characteristic set of (T_{i}) : I_{T_{i}}^{∞} in K_{A}[𝔏(A)]. The I_{C_{i}} and S_{C_{i}} are simply obtained from I_{T_{i}} and S_{T_{i}} by multiplication by an element of K[𝔑(A)]. Thus, in K_{A}[𝔏(A)], ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} and ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} are respectively equal to (T_{i}) : I_{T_{i}}^{∞} and (T_{i}) : H_{T_{i}}^{∞}. Consequently, by Proposition 3.3 applied to (T_{i}) : H_{T_{i}}^{∞}, ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} = ((C_{i}):H_{C_{i}}^{∞})_{K_{A}}.

Recall from Theorem 3.1 and Theorem 3.2 that ((A):H_{A}^{∞})_{K_{A}} is a zero dimensional radical ideal in K_{A}[𝔏(A)] and ((A):H_{A}^{∞})_{K_{A}} ∩ K[X] = ((A):H_{A}^{∞})_{K}. We have

((A):H_{A}^{∞})_{K} = (((C_{1}):I_{C_{1}}^{∞})_{K_{A}} ∩ K[X]) ⋂ … ⋂ (((C_{r}):I_{C_{r}}^{∞})_{K_{A}} ∩ K[X]) .

The ideals ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩K[X] are radical. The ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} being pairwise comaximal in K_{A}[𝔏(A)] implies that a prime ideal P of K[X] containing two distinct ideals ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X] must contain an element of K[𝔑(A)]. Thus P cannot be an essential component of ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X]. Therefore the minimal primes of the ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X] give a partition of the set of minimal primes of (A):H_{A}^{∞}.

Consider 1 ≤ i ≤ r. Let P be a minimal prime of ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X]. Both C_{i} and A are included in P. Assume C_{i} were not an autoreduced set. Then P would contain an autoreduced set lower than A and with a set of leaders different than 𝔏(A). This would contradict Theorem 3.2. C_{i} is an autoreduced set in K[X].

((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X] contains no autoreduced set lower than C_{i} otherwise ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} = (T_{i}) : I_{T_{i}}^{∞} would too; It follows that C_{i} is a characteristic set of ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X] and thus C_{i} ⊂ ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X] ⊂ ((C_{i}):I_{C_{i}}^{∞})_{K}. Taking the saturation by I_{C_{i}} on each member of this inclusion we are lead to ((C_{i}):I_{C_{i}}^{∞})_{K_{A}} ∩ K[X] = ((C_{i}):I_{C_{i}}^{∞})_{K}. C_{i} is thus a characteristic presentation and we have (A):H_{A}^{∞} = (C_{1}):I_{C_{1}}^{∞} ∩ … ∩ (C_{r}): I_{C_{r}}^{∞}, which is an irredundant decomposition. □

4. Coherence and its consequences

Coherence is a concept similar to formal integrability or involutivity in some other algebraic formalism for differential equations. It was introduced in differential ideal theory by (Rosenfeld 1959). It answers the problem exposed in Example 2.6.

Differential ideals defined by coherent autoreduced sets enjoy specific properties which make them the bridge between differential algebra and polynomial algebra. Neither Theorem 4.3 nor Theorem 4.4 appears in the work of Ritt and Kolchin; they did use only particular cases of these theorems related to prime ideals. The first occurrences of these theorem is in (Boulier et al. 1995). They are the lifting of Theorem 3.1 and Theorem 3.2 through what Boulier (1994) named the Rosenfeld lemma.

Theorem 4.3 is a direct lifting of Theorem 3.1. Our proof of Theorem 4.4 is somewhat different than the one presented in (Boulier et al. 1997). From now on, we assume that F{Y } is endowed with a ranking.

Let A be an autoreduced set of F{Y }. For a derivative v of F{Y } we define Θ_{v}A to be the set of the elements of A and their derivatives that have a leader ranking strictly less than v.

Definition 4.1. Let A be an autoreduced set in F{Y }. A is said to be coherent if whenever a, b ∈ A are such that u_{a} and u_{b} have a common derivative, say v = ψ u_{a} = ϕ u_{b}, ϕ, ψ ∈ Θ, then s_{b} ψa − s_{a}ϕb ∈ (Θ_{v}A):H_{A}^{∞}.

Definition 4.2. Let a and b be differential polynomials in F{Y }. If u_{a} and u_{b} have a common derivative, let lcd(u_{a}, u_{b}) = ψ̄u_{a} = ϕ̄u_{b} be the lowest such derivative. We define the cross-derivative of a and b to be

X-derivative(a, b) = \frac{s_{b}}{gcd(s_{b}, s_{a})} ψ̄a − \frac{s_{a}}{gcd(s_{b}, s_{a})} ϕ̄b

When u_{a} and u_{b} have no common derivative, we define X-derivative(a, b) = 0.

We introduce the systematic division by gcd(s_{b}, s_{a}) in the cross derivative to reduce the expression swell in an implementation. From (Kolchin 1973, IV.9), it is easy to conclude that an autoreduced set A in F{Y } is coherent if and only if X-derivative(a, b) ∈ (Θ_{lcd(u_{a},u_{b})}A):H_{A}^{∞}, ∀a, b ∈ A. An autoreduced set A in F{Y } is coherent if d-rem(X-derivative(a, b), A) = 0, ∀a, b ∈ A.

The key result here is a theorem by^{4} Rosenfeld (1959) according to which, if A is a coherent autoreduced set, q ∈ F{Y } partially reduced w.r.t. A belongs to [A]:H_{A}^{∞} iff it belongs to (A):H_{A}^{∞}. This bears as immediate corollary that p ∈ [A]:H_{A}^{∞} ⇔ d-prem(p, A) ∈ (A):H_{A}^{∞}. The fundamental result to obtain a decomposition into coherent components is then the following.

Theorem 4.3. Let A be an coherent autoreduced set of F{Y }. Then [A]:H_{A}^{∞} is a radical differential ideal.

Proof. By Theorem 3.1 (A):H_{A}^{∞} is radical. It then follows from a corollary of Rosenfeld’s lemma (Kolchin 1973, III.8, lemma 6) that [A]:H_{A}^{∞} is radical. □

Furthermore, the computation of an irredundant characteristic decomposition of [A]:H_{A}^{∞} can be reduced to polynomial algebra computations thanks to the following result.

Theorem 4.4. Let A be a coherent autoreduced set of F{Y } such that 1 ∉ [A] : H_{A}^{∞}. There is a oneto-one correspondence between the minimal primes of (A) : H_{A}^{∞} in F[𝔑(A), 𝔏(A)] and the essential prime components of [A]:H_{A}^{∞} in F{Y }; Assume C_{i} is a characteristic set of a minimal prime of (A):H_{A}^{∞} then C_{i} is the characteristic set of a single essential prime component of [A]:H_{A}^{∞} (and vice versa).

Proof. We divide the proof in three steps.

∘ Let P be an essential prime component of [A]:H_{A}^{∞}. P ∩ F[𝔑(A), 𝔏(A)] is a minimal prime of (A):H_{A}^{∞}.

By Rosenfeld’s lemma,(Kolchin 1973, III.8, lemma 5), [A] : H_{A}^{∞} ∩ F[𝔑(A), 𝔏(A)] = (A) : H_{A}^{∞}. P ∩ F[𝔑(A), 𝔏(A)] is a prime ideal that contains (A):H_{A}^{∞}. It therefore contains a minimal prime P̄ of (A):H_{A}^{∞}.

Let p̄ be an element of P ∩ F[𝔑(A), 𝔏(A)] that does not belong to (A):H_{A}^{∞} and therefore does not belong to [A]:H_{A}^{∞}. There exists q ∈ F{Y }, q ∉ P such that q p̄ ∈ [A]:H_{A}^{∞}. Let q⟶_{A} q̄ so that there exists h ∈ H_{A}^{∞} such that h q ≡ q̄ mod [A]. We have that q̄ ∉ (A):H_{A}^{∞} otherwise q would belong to [A]:H_{A}^{∞} and therefore to P. Nonetheless, q̄p̄ belongs to [A] : H_{A}^{∞} and thus to (A) : H_{A}^{∞} since it is partially reduced w.r.t. A. This says that p̄ belongs to a minimal prime of (A):H_{A}^{∞}. Thus P ∩ F[𝔑(A), 𝔏(A)] belongs to a union of minimal primes of (A):H_{A}^{∞}. By the prime avoidance theorem, (Eisenbud 1994, Lemma 3.3), P ∩ F[𝔑(A), 𝔏(A)] must be contained in one of the minimal primes, say P̄′, of (A) : H_{A}^{∞}. Thus P̄ ⊂ P ∩ F[𝔑(A), 𝔏(A)] ⊂ P̄′. We must have P̄′ = P̄ and therefore P ∩ F[𝔑(A), 𝔏(A)] is a minimal prime of (A):H_{A}^{∞}.

∘ Every minimal prime of (A) : H_{A}^{∞} is the intersection of an essential prime component of [A] : H_{A}^{∞} with F[𝔑(A), 𝔏(A)]

Assume the minimal prime decomposition of [A]:H_{A}^{∞} is [A]:H_{A}^{∞} = ⋂_{i=1}^{r} P_{i}. By (Kolchin 1973, III.8, lemma 5), ⋂_{i=1}^{r} (P_{i} ∩ F[𝔑(A), 𝔏(A)]) = (A):H_{A}^{∞}. Therefore, all the minimal prime of (A):H_{A}^{∞} are the intersection of an essential prime component of [A]:H_{A}^{∞} with F[𝔑(A), 𝔏(A)].

4see also (Kolchin 1973, III.8, lemma 5)

∘ If C_{i} is the characteristic set of a minimal prime P_{i} ∩ F[𝔑(A), 𝔏(A)] of (A):H_{A}^{∞} then C_{i} is a characteristic set of P_{i}.

Let p be an element of P_{i} and p⟶_{C_{i}} p̄. Then p̄ ∈ P_{i} ∩ F[𝔑(A), 𝔏(A)]. C_{i} being a characteristic set of P_{i} ∩ F[𝔑(A), 𝔏(A)], p̄ must be zero. Therefore C_{i} is a characteristic set of P_{i}. (In particular C_{i} must be coherent!).

Furthermore: since a characteristic set of a prime differential ideal determines uniquely this prime differential ideal, there is a unique essential prime component of [A]:H_{A}^{∞} whose intersection with F[𝔑(A), 𝔏(A)] is equal to (C_{i}):H_{C_{i}}^{∞} = P_{i} ∩ F[𝔑(A), 𝔏(A)]. □

This theorem together with Theorem 3.2 bears the following consequence: a characteristic set of an essential prime component of [A]:H_{A}^{∞} has the the same set of leaders as A iff (A):H_{A}^{∞} ≠ (1).

5. Decomposition into coherent components

We have seen in the previous section that the differential ideal [A]:H_{A}^{∞}, where A is a coherent autoreduced set, bears pleasant properties that can be lifted from the algebraic properties of (A) : H_{A}^{∞}. For a given finite set Σ of F{Y } it would thus be very nice to be able to find a coherent autoreduced set A such that {Σ} = [A]:H_{A}^{∞}. This is obviously not the general case. We will nonetheless manage to represent {Σ} as an intersection of such differential ideals.

We will first show how we can compute a coherent autoreduced A that would satisfy one of the property of a characteristic set of [Σ], namely that A ⊂ [Σ] ⊂ [A] : H_{A}^{∞}. This is the first step of the Ritt algorithm (Kolchin 1973, IV.9).

We will then exhibit radical differential ideals that, when intersected with [A] : H_{A}^{∞}, give {Σ}. The justification for this splitting step relies on Theorem 4.3. Note that neither Ritt nor Kolchin used this property that [A] : H_{A}^{∞} is radical. The way they would proceed in their decomposition algorithm would rely on a process^{5} to decide whether A is a characteristic presentation of a prime differential ideal. In case A were not a characteristic presentation of a prime differential ideal, their process would exhibit p, q ∉ [A] : H_{A}^{∞} reduced w.r.t. A such that p q ∈ [A]:H_{A}^{∞} and operate the splitting {Σ} = {Σ, p} ∩ {Σ, q}. Only in the case where A is a characteristic presentation of a prime differential ideal, would they be in a position to justify the splitting on the separants.

Boulier et al. (1995) already presented a decomposition into coherent component - that are called there regular component. The decomposition was obtained by reworking Seidenberg’s elimination scheme. It is interesting that the point of view of Ritt and Seidenberg on reduction do converge.

5.1. Exhibiting a coherent autoreduced set. Let Σ be a finite set of differential polynomials of F{Y }. With a finite number of differentiations and arithmetic operations in F{Y }, we can compute a coherent autoreduced set A such that A ⊂ [Σ] and ∀p ∈ Σ, p⟶_{A} 0. Thus A ⊂ [Σ] ⊂ [A] : H_{A}^{∞}. Algorithm 5.1 is devoted to compute such a A. We have noted Min-Autoreduced a procedure which selects an autoreduced set of minimal rank among a finite set of differential polynomials of F{Y }.

Algorithm 5.1. Coherent-Autoreduced .

input: Σ a set of differential polynomials in F{Y } endowed with a ranking.

output: A a coherent autoreduced set such that [A] ⊂ [Σ] ⊂ [A]:H_{A}^{∞}.

S := ∅; R := Σ \ {0}; D := ∅;

While R ∪ D ≠ ∅ and S ∩ F = ∅ do S := S ∪ R ∪ D; A := Min-Autoreduced (S); R := {d-rem(q, A) ≠ 0 | q ∈ R \ A}; D := {d-rem( X-derivative(a, a′), A) ≠ 0 | a, a′ ∈ A}; od; if S ∩ F ≠ ∅ then

5based on factorizations in tower of algebraic extension (Ritt 1950)

return ( Null-Sequence);

else

return (A);

fi;

At each iteration, a minimal autoreduced set of S ∪ R ∪ D has strictly lower rank than one of S. By (Kolchin 1973, I.10, Proposition 3) any decreasing sequence of autoreduced sets is finite. This algorithm thus terminates.

It is worth noting that we can avoid forming certain cross derivatives thanks to an analogue of the second Buchberger criterion (Boulier et al. 1997).

5.2. Splitting. The crucial information here is that [A] : H_{A}^{∞} is radical. Thus [A] ⊂ {Σ} ⊂ [A] : H_{A}^{∞} and therefore {Σ}:H_{A}^{∞} ⊂ [A]:H_{A}^{∞}. This, with Proposition 2.1, allows us to write:

{Σ} = [A]:H_{A}^{∞} ∩ ⋂_{a∈A} ({Σ, i_{a}} ∩ {Σ, s_{a}}) .

Theorem 5.2. Given a finite set Σ of differential polynomials in F{Y } we can compute a finite number of coherent autoreduced sets A_{1}, …, A_{r} such that

{Σ} = ⋂_{i=1}^{r}[A_{i}]:H_{A_{i}}^{∞}.

The differential ideals [A_{i}] : H_{A_{i}}^{∞} are radical and we call them coherent components^{6} of {Σ}. Algorithm 5.3 computes such a decomposition into coherent components.

Algorithm 5.3. Coherent-Components

input: Σ, a finite set of differential polynomials of F{Y } endowed with a ranking.

output: 𝔄 = A_{1}, …, A_{r}, a sequence of coherent autoreduced sets such that {Σ} = ⋂_{i=1}^{r} [A_{i}]:H_{A_{i}}^{∞}.

A := Coherent-Autoreduced (Σ, F{Y }) ;

if A = 1 then

return ( Null-Sequence ); else

𝔄 = A, Coherent-Components ({Σ, s_{a}}, F{Y })_{a∈A}, Coherent-Components ({Σ, i_{a}}, F{Y })_{a∈A};

fi;

Note that, at each step, {Σ, i_{a}} and {Σ, s_{a}} admit autoreduced sets of lower rank than A. The algorithm thus terminates.

Thanks to the properties of coherent components disclosed by Rosenfeld’s lemma, this decomposition brings already information. For instance, it already allows us to test membership to {Σ} (Boulier et al. 1995).

6. Irredundant characteristic decomposition of a coherent component

This section explains how an irredundant characteristic decomposition of (A) : H_{A}^{∞}, where A is a coherent autoreduced set of F{Y }, can be readily used as an irredundant characteristic decomposition of [A] : H_{A}^{∞}. This is a new result that can be applied in many different ways. It allows to decouple the differential operations from the purely algebraic computations in a decomposition algorithm in differential algebra.

We start with a necessary and sufficient condition for an autoreduced set to be a characteristic presentation. Let’s note that Ritt and Kolchin enunciated and made use only of the prime ideal case (Kolchin 1973, IV.9, lemma 2) of the following lemma.

6called regular components in (Boulier et al., 1995, 1997) and (Hubert 1998).

Lemma 6.1. Let A be an autoreduced set of F{Y }. A necessary and sufficient condition for A to be a characteristic presentation in F{Y } is that A be coherent and A is a characteristic presentation in F[𝔑(A)∪ 𝔏(A)].

In other words, A is a characteristic set of [A] : H_{A}^{∞} in F{Y } if and only if A is coherent and A is a characteristic set of (A):H_{A}^{∞} in K[𝔑(A) ∪ 𝔏(A)], or equivalently in K_{A}[𝔏(A)] (Lemma 3.9).

Proof. We claim that if A is a characteristic set of [A] : H_{A}^{∞} then A must be coherent. Indeed, for any a, b ∈ A, X-derivative(a, b) ∈ [A] ⊂ [A] : H_{A}^{∞}. It must therefore be reduced to zero by A. The derivatives of the elements of A needed in the reduction have leaders that are not ranking higher than the lowest common derivative of u_{a} and u_{b}, say v. Thus X-derivative(a, b) ∈ (Θ_{v}A) : H_{A}^{∞}. Now, if A is a characteristic set of [A]:H_{A}^{∞}, [A]:H_{A}^{∞} has no non-zero element reduced w.r.t. A. It is then obviously also the case for (A):H_{A}^{∞}.

Conversely, assume A is coherent and a characteristic set of (A) : H_{A}^{∞}. If there would exist a non-zero differential polynomial p in [A] : H_{A}^{∞} reduced w.r.t. A then, by Rosenfeld’s lemma, (Kolchin 1973, III.8, lemma 5), it would belong to (A):H_{A}^{∞}. This cannot be so since A is a characteristic set of (A):H_{A}^{∞}. Thus A is a characteristic set of [A]:H_{A}^{∞}. □

Theorem 6.2. If A is a coherent autoreduced set of F{Y } and (A):H_{A}^{∞} = ∩_{i=1}^{r} (C_{i}):I_{C_{i}}^{∞} is a characteristic irredundant decomposition in F[𝔑(A), 𝔏(A)] then C_{i} is coherent, 1 ≤ i ≤ r, and [A] : H_{A}^{∞} = ∩_{i=1}^{r} [C_{i}] : H_{C_{i}}^{∞} is a characteristic irredundant decomposition of [A]:H_{A}^{∞} in F{Y }.

Proof. Let B_{i,j}, 1 ≤ j ≤ r_{i}, be the characteristic sets of the minimal primes of (C_{i}) : I_{C_{i}}^{∞}; (C_{i}) : I_{C_{i}}^{∞} = ∩_{j=1}^{r_{i}} (B_{ij}):I_{B_{ij}}^{∞}. By Theorem 4.4, B_{ij} is the characteristic set of [B_{ij}]:H_{B_{ij}}^{∞}, an essential prime component of [A]:H_{A}^{∞}.

Let a, b ∈ C_{i}; X-derivative(a, b) belongs to ∩_{j=1}^{r_{i}} [B_{ij}] : H_{B_{ij}}^{∞}. Thus, d-rem(X-derivative(a, b), C_{i}) belongs

to ∩_{j=1}^{r_{i}} ([B_{ij}]:H_{B_{ij}}^{∞} ∩ F[𝔑(A), 𝔏(A)]). As [B_{ij}] : H_{B_{ij}}^{∞} ∩ F[𝔑(A), 𝔏(A)] = (B_{ij}) : H_{B_{ij}}^{∞} = (B_{ij}) : I_{B_{ij}}^{∞} (Theorem 4.4) and ∩_{j=1}^{r_{i}} (B_{ij}) : I_{B_{ij}}^{∞} = (C_{i}) : I_{C_{i}}^{∞}, we deduct that d-rem(X-derivative(a, b), C_{i}) ∈ (C_{i}) : I_{C_{i}}^{∞}. C_{i} being a characteristic set of (C_{i}) : I_{C_{i}}^{∞}, we are led to the conclusion that d-rem(X-derivative(a, b), C_{i}) = 0. Therefore C_{i} is coherent. By Lemma 6.1, C_{i} is a characteristic set of [C_{i}]:H_{C_{i}}^{∞}. By Theorem 4.4, [C_{i}]:H_{C_{i}}^{∞} = ∩_{j=1}^{r_{i}} [B_{ij}]:H_{B_{ij}}^{∞} and therefore [A]:H_{A}^{∞} = ∩_{i=1}^{r} [C_{i}]:H_{C_{i}}^{∞}. This decomposition is furthermore irredundant. □

7. Conclusion

We recapitulate in maple pseudo-code the algorithm for which we have given all the mathematical justifications in this paper. It is very simple and relies only on two ingredients; First a decomposition into coherent components, as described in Section 5. Then, Theorem 6.2 together with Theorem 3.10 justify the fact that a characteristic decomposition of a coherent component can be lifted from an irredundant characteristic decomposition of a zero dimensional radical ideal. The second ingredient is therefore Algorithm 3.8, or an algorithm of the same specification.

Algorithm 7.1. χ-Decomposition

input: Σ, a finite set of differential polynomials of F{Y } endowed with a ranking.

output: ℭ = C_{1}, …, C_{r}, a sequence of characteristic presentations such that {Σ} = ⋂_{i=1}^{r} [C_{i}]:H_{C_{i}}^{∞}.

𝔄 := Coherent-Components (Σ, F{Y }) ;

ℭ := Null-sequence; For A in 𝔄 do

C := 0D-Irredundant-χ-Decomposition (A, F(𝔑(A))[𝔏(A)]); C := clear out the denominators in the elements of C; ℭ := C, ℭ

od; This theoretical simplicity is unfortunately not always reflected by reasonably sized computations. Careful implementation and heuristics are needed to avoid expression swell and to minimize the number of reductions, cross-derivative formations and splittings.

We presented in this paper the basics of an effective decomposition algorithm in differential algebra. The key idea is to work with differential ideals that are not prime, the little drawback being that the results depend on the ranking chosen. This idea was first successfully explored by Boulier (1994, 1995,1997) who used a Seidenberg’s like approach.

In this paper we reworked Ritt’s approach and saw that the same algebraic results could be used to make this approach effective. We have provided some new concise proofs of these results. We furthermore presented new results that can be applied in both approaches. This results allow to lift a decomposition obtained in polynomial algebra of dimension zero to a differential decomposition. This complete uncoupling of the algebraic and differential operations allow direct improvement and simplification of the algorithms.

Appendix A. Implementation tips

The main work in the purely algebraic part (Algorithm 3.8) of our decomposition algorithm is the computation of the reduced Groebner basis of a zero dimensional radical idea according to a lexicographic term order. We can find in the literature several ways to make this process efficient. Now, the ideal of which we want the Groebner basis is the saturation ideal (A):H_{A}^{∞}, where A is an autoreduced set. The point of this appendix is just to show how we can rewrite A so that the traditional Buchberger algorithm is no longer the bottleneck of our Maple implementation.

We work in K[x_{1}, …, x_{n}] with a ranking x_{1} < … < x_{s}. We assume A = a_{1}, a_{2}, …, a_{n} where x_{j} is the leader of a_{j}, 1 ≤ j ≤ n. We denote i_{j}, s_{j} and d_{j} respectively the initial, the separant and the degree in x_{j} of a_{j}.

For 1 ≤ k ≤ 2 n, we introduce the dummy indeterminates z_{k}. They will represent 1/i_{k} and 1/s_{k−n+1}. We endow K[x_{1}, …, x_{n}, z_{1}, …, z_{2n}] = K[X][Z] with a block term order eliminating Z and extending the lexicographic term order x_{1} < … < x_{s}. The reduced Groebner basis G of (A):H_{A}^{∞} can be obtain as follow: if G_{Z} is a Groebner basis of (a_{1}, …, a_{n}, 1 − z_{1} i_{1}, 1 − z_{1} i_{1}, …, 1 − z_{n} i_{n}, 1 − z_{n+1} s_{1}, …, 1 − z_{2n} s_{n}), then G = G_{Z} ∩ K[X]. From practical experience it is nonetheless useful to make some substitution for the a_{j} and s_{j}, as explained below.

Let a be an element of K[X]. Let x, s and d be respectively its leader, initial, separant and the degree of a in x. Write f_{d}, …, f_{0} the coefficients of the powers of x in a; f_{d} is the leader of a and a = f_{d} u^{d}+f_{d−1} u^{d−1}+…+f_{0}. We note that s = d f_{d} x^{d−1} + (d − 1) f_{d−1} x^{d−2} + … + f_{1} = d f_{d} x^{d−1} + (s mod x^{d−1}) and d a = s x + ã, where ã = ∑_{k=0}^{d−1} f_{k} x^{k}. Before computing G_{Z}, we can therefore replace a_{j} by x_{j} + z_{n+1+j} ã_{j} and s_{j} by d_{j} x_{j}^{d_{j}−1} + z_{j} (s_{j} mod x_{j}^{d_{j}−1}).

It is also worthwhile not considering plainly the separant and the initials but a set of pairwise prime squarefree factors that generates H_{A}^{∞}. These factors are obtained by partial squarefree factorization of the separants and initials.

We can also make the following substitution for the elements of A. If a_{j} has a content with respect to x_{j} which does not belong to K this content divides i_{j}. We can thus replace a_{j} by its primitive part according to x_{j}. Similarly, to decrease the degrees, we can eliminate from a_{j} the factors which are common with s_{j}. Thus we can substitute \frac{a_{j}}{gcd(a_{j},s_{j}^{2})} to a_{j}.

References

Becker, T., Weispfenning, V. (1993). Gröbner Bases - A Computational Approach to Commutative Algebra. Springer-Verlag. Boulier, F. (1994). Étude et Implantation de Quelques Algorithmes en Algèbre Différentielle. PhD thesis, Université de Lille. Boulier, F., Lazard, D., Ollivier, F., Petitot, M. (1995). Representation for the radical of a finitely generated differential ideal.

In Levelt, A., editor, ISSAC’95. ACM Press. Boulier, F., Lazard, D., Ollivier, F., Petitot, M. (1997). Computing representations for radicals of finitely generated differential

ideals. Technical Report IT-306, LIFL.

Carra’Ferro, G. (1987). Gröbner bases and differential algebra. In AAECC, volume 356 of Lecture notes in Computer Science.

Springer. Eisenbud, D. (1994). Commutative Algebra with a view toward Algebraic Geometry. Graduate Texts in Mathematics. Springer-

Verlag. Hubert, E. (Avril 1997). Algebra and Algorithms for Singularities of Implicit Differential Equations. PhD thesis, Insti-

tut National Polytechnique de Grenoble. Possible download from ftp://ftp.imag.fr/pub/Mediatheque.IMAG/theses/97-Hubert.Evelyne/notice-anglais.html.

Hubert, E. (1998). Essential components of an algebraic differential equation. Journal of Symbolic Computation. (To appear). Kalkbrener, M. (1993). A generalized euclidean algorithm for computing triangular representations of algebraic varieties.

Journal of Symbolic Computations, 15(2):143–167. Kaplansky, I. (1970). An Introduction to Differential Algebra. Hermann. Kolchin, E. (1973). Differential Algebra and Algebraic Groups, volume 54 of Pure and Applied Mathematics. Academic Press. Lazard, D. (1992). Solving zero dimensional algebraic systems. Journal of Symbolic Computations, 15:117–132. Maârouf, H., Kandri Rody, A., Ssafini, M. (1998). Triviality and dimension of a system of algebraic differential equations. J.

Automat. Reason., 20(3):365–385. Mansfield, E. (1991). Differential Gröbner Bases. PhD thesis, University of Sydney. Moreno-Maza, M. (1997). Calculs de pgcd au-dessus des tours d’extensions simples et résolution des système d’équations

algébriques. PhD thesis, Université Paris 6. Morrison, S. (1999). To appear. Ollivier, F. (1990). Le problème de l’identifiabillité Structurelle Globale: Approche Théorique, Méthodes Effectives et Bornes

de Complexité.. PhD thesis, École Polytechnique. Ritt, J. (1936). On the singular solutions of algebraic differential equations. Annals of Mathematics, 37(3):552–617. Ritt, J. (1950). Differential Algebra, volume XXXIII of Colloquium publications. American Mathematical Society. Reprinted

by Dover Publications, Inc (1966). Rosenfeld, A. (1959). Specializations in differential algebra. Transaction of the American Mathematical Society, 90:394–407. Szanto, A. (1998). Computation with polynomial systems. PhD thesis, Cornell University. Vasconcelos, W. (1998). Computational Methods in Commutative Algebra and Algebraic Geometry, volume 2 of Algorithms

and Computation in Mathematics. Springer.

MSRI, 1000 centennial drive, Berkeley CA 94720-5070 USA

E-mail address: evelyne @ msri.org