Loewy- and Primary- Decompositions of D-Modules

D. Grigoriev CNRS, IRMAR, Université de Rennes, Beaulieu, 35042, Rennes, France, e-mail: dima@math.univ-rennes.fr, website: http://name.math.univ-rennes1.fr/dimitri.grigoriev

F. Schwarz FhG, Institut SCAI, 53754 Sankt Augustin, Germany, e-mail: fritz.schwarz@scai.fraunhofer.de website: www.scai.fraunhofer.de/schwarz.0.html

Abstract Starting from the well-known factorization of linear ordinary differential equations, we define the Loewy- and primary- decomposition of a D-module. Furthermore, we design an algorithm which constructs these decompositions in case of any finite-dimensional D-module. To this end the new concept of the module of relative syzygies Syz(I, J) for two given modules I and J with I ⊆ J is introduced. The invariance of this module and its solution space w.r.t. the set of generators is shown. Also an algorithm is exhibited which describes all isomorphisms of finite-dimensional D-modules.

Introduction

The concept of factorization of a linear ordinary differential equation (lode) originally goes back to Beke [1] and Schlesinger [17]. Loewy [12] extended it and introduced a unique decomposition of any lode into largest completely reducible factors, i. e. factors which are the least common multiple of irreducible right factors. Similar as in the algebraic case, if such a nontrivial decomposition may be found, the solution procedure is faciliated because the order of the equations to be solved is lowered. Algorithms for factoring a lode have been described by Schwarz [19] and, with an improved complexity bound, by Grigoriev [6]. A survey on factorization of lode’s may be found in the recent book by Singer and van der Put [14].

Factoring linear partial differential equations (lpde’s) is much more complicated. Moreover, so far there is no common agreement on what to understand under factoring lpde’s in general. A first attempt to generalize the above theory to certain classes of lpde’s has been undertaken by Li et al. [11], see also Tsarev [24]. In theses references factorization means finding overmodules of a given D-module. Some background on D-modules may be found e. g. in the books by Sabbah [15] or [4]. In [11] an algorithm is described for finding all factors of a finite-dimensional module, see also Section 7 below.

On the other hand, the problem of factoring an infinite-dimensional module remained essentially untouched. Recently in [8] the problem of factoring a single lpde into factors being also single lpde’s was studied. An algorithm was designed to factor so-called separable lpde’s, but the general factorization problem remains open.

In the article at hand we generalize the results of [11] and [8] in two respects. We obtain complete Loewy- and primary-decompositions of a finite-dimensional D-module. Moreover we study Loewyand primary-decompositions of infinite-dimensional modules. In Section 1 we show that the space of solutions of a module is determined by its class of isomorphisms (Proposition 1.1), up to an equivalence ≃_{D} which is called D-isomorphism.

In Section 2 we introduce the new concept of the module of relative syzygies Syz(I, J) of two modules I and J with I ⊆ J. It extends the one given in [11] for finite-dimensional modules. It is shown that it is essentially invariant w.r.t. to the set of generators. We also show that for the space of solutions of Syz(I, J) there holds V_{Syz(I,J)} ≃_{D} V_{I}/V_{J} (Lemma 2.4), this provides a bijective correspondence between classes of isomorphisms of the factors I/J and classes of D-isomorphisms of the solutions spaces V_{Syz(I,J)} (Corollary 2.5). In addition we describe a procedure to calculate the module of relative syzygies. Finally, the relation a_{τ} (Syz(I, J)) = a_{τ} (I) − a_{τ} (J) (Theorem 2.7) is proved for the coefficients a_{τ} of the Hilbert-Kolchin polynomials; τ is the differential type of the module I, see [9] and [10].

In Section 3 we define a unique Loewy decomposition of a finite-dimensional module I. The crucial role here plays the intersection R(I) of all maximal overmodules of I. Instead of I the modules R(I) and Syz(I, R(I)) with smaller differential type or smaller typical differential dimension (see e.g., [9], [10]) are considered in the inductive definition.

In Section 4 the Loewy decomposition is generalized to infinite-dimensional modules I of differential type τ > 0. It relies on the intersection R_{τ} (I) of the classes of maximal overmodules of I with differential type τ, considered up to modules of differential types less than τ.

In Section 5 a primary decomposition of a finite-dimensional module I is introduced. The crucial role here plays the intersection N(I) of all proper overmodules of I. Similar to Section 3, we replace I in the inductive definition by N(I) and Syz(I, N(I)). In Section 6 the primary decomposition is extended to an infinite-dimensional module I of differential type τ > 0. Similar to Section 4 the intersection N_{τ} (I) of the classes of overmodules, up to modules of differential type less than τ is introduced.

In Section 7 we introduce the formal concept of a parametric-algebraic family of D-modules. Its significance is justified by the algorithms from [11] which generates all the overmodules of a finitedimensional module I as a parametric-algebraic family. Based on it and on the algorithms manipulating algebraic varieties, we design an algorithm which accepts two such families as input and returns a family of pairs of modules such that one of the modules in a pair contains the other. In particular, this allows one to produce the family of all maximal modules in a given family. Relying on these algorithms one can construct Loewy- and primary decompositions of a finite-dimensional module, see Section 8. In Section 9 an algorithm is exhibited which allows one to yield a parametric-linear family of all D-homomorphisms of two finite-dimensional D-modules and furthermore, a parametric-algebraic family of all their D-isomorphisms.

1 Invariance of the space of solutions of a D-module

Let F be a universal differential field [9] with derivatives d_{1}, …, d_{m} and D = F [d_{1}, …, d_{m}] be the ring of partial differential operators. Denote by C ⊂ F its subfield of constants. Introduce differential indeterminates y_{1}, …, y_{n} over F. By Θ denote the commutative monoid generated by d_{1}, …, d_{m} and by Γ the set of all the derivatives θy_{i} for θ ∈ Θ, 1 ≤ i ≤ n. We fix also some admissible total ordering ≺ on the derivatives [10, 16]. A background in differential algebra may be found in [9, 2, 21, 22].

Let I ⊂ D^{n} be a left D-module. For vectors g = (g_{1}, …, g_{n}), v = (v_{1}, …, v_{n}) ∈ F^{n} we denote the inner product gv = (g, v^{T}) = ∑ g_{i}v_{i} ∈ F. By V_{I} = {v ∈ F^{n} : Iv = 0} ⊂ F^{n} we denote the space of solutions of I being a C-vector space. A priori V_{I} depends on the imbedding I ⊂ D^{n}. The purpose of this section is to show that actually V_{I} depends up to an isomorphism just on the factor D^{n}/I (considered as well up to an isomorphism).

Now let I_{1} ⊂ D^{n_{1}}, I_{2} ⊂ D^{n_{2}}. We say that a n_{1} × n_{2} matrix A = (a_{ij}) with a_{ij} ∈ D provides a D-homomorphism from D^{n_{1}}/I_{1} to D^{n_{2}}/I_{2} if (D^{n_{1}}/I_{1})A ⊂ (D^{n_{2}}/I_{2}). Clearly one gets a homomorphism of D-modules.

We call D^{n_{1}}/I_{1} and D^{n_{2}}/I_{2} to be D-isomorphic if in addition there exists a n_{2}×n_{1} matrix B = (b_{ij}) with b_{ij} ∈ D such that (D^{n_{2}}/I_{2})B ⊂ D^{n_{1}}/I_{1} and

AB|_{(D^{n_{1}}/I_{1})} = id, BA|_{(D^{n_{2}}/I_{2})} = id.  (1)

For the spaces of solutions V_{I_{1}} ⊂ F^{n_{1}}, V_{I_{2}} ⊂ F^{n_{2}} we say that a matrix A provides a Dhomomorphism if A(V_{I_{2}})^{T} ⊂ (V_{I_{1}})^{T} (more precisely, one should talk about a D-homomorphism of the imbeddings V_{I_{1}} ⊂ F^{n_{1}}, V_{I_{2}} ⊂ F^{n_{2}}). In a similar way, if there exists a n_{2} × n_{1} matrix B such that B(V_{I_{1}})^{T} ⊂ (V_{I_{2}})^{T} and

AB|_{V_{I_{1}}^{T}} = id, BA|_{V_{I_{2}}^{T}} = id  (2)

we call V_{I_{1}}, V_{I_{2}} to be D-isomorphic and denote this by V_{I_{1}} ≃_{D} V_{I_{2}}. The following proposition extends Lemma 2.5 [20] (established for the ordinary case m = 1) to finite-dimensional modules.

Proposition 1.1 i) A matrix A provides a D-homomorphism of D^{n_{1}}/I_{1} to D^{n_{2}}/I_{2} if and only if it provides D-homomorphisms of V_{I_{2}} to V_{I_{1}}.

ii) D^{n_{1}}/I_{1} and D^{n_{2}}/I_{2} are D-isomorphic if and only if V_{I_{1}} and V_{I_{2}} are D-isomorphic.

Proof. i) Assume that (D^{n_{1}}/I_{1})A ⊂ (D^{n_{2}}/I_{2}). We need to verify that A(V_{I_{2}})^{T} ⊂ (V_{I_{1}})^{T}. The latter is equivalent to the equality I_{1}A(V_{I_{2}})^{T} = 0 which holds because of the inclusion I_{1}A ⊂ I_{2}.

Conversely, assume that A(V_{I_{1}})^{T} ⊂ (V_{I_{1}})^{T}, then as above I_{1}A(V_{I_{2}})^{T} = 0 which implies I_{1}A ⊂ I_{2} due to the duality in the differential Zariski topology (see Corollary 1, page 148 in [9], also [21]). Hence (D^{n_{1}}/I_{1})A ⊂ (D^{n_{2}}/I_{2}).

ii) Assume that (1) holds. One has to verify (2), i. e. for any v ∈ V_{I_{1}} to show that ABv^{T} = v^{T}. The latter holds if and only if for any g ∈ D^{n_{1}} the equality gABv^{T} = gv^{T} is true. Equation (1) entails that gABv^{T} = (g + g_{0})v^{T} = gv^{T} for a certain vector g_{0} ∈ I_{1}.

Conversely, assume (2) is valid. For any g ∈ D^{n_{1}} (2) implies the equality (gAB − g)(V_{I_{1}})^{T} = 0, therefore gAB − g ∈ I_{1} again due to Corollary 1, page 148 of [9]. This establishes (1). □

Remark 1.2 We observe that for any two D-modules I_{1} ⊂ D^{n_{1}}, I_{2} ⊂ D^{n_{2}} such that dim_{F} (D^{n_{1}}/I_{1}) = dim_{F} (D^{n_{2}}/I_{2}) < ∞ we have D^{n_{1}}/I_{1} ≃_{D} D^{n_{2}}/I_{2}. On the other hand, in case of infinite-dimensional modules the isomorphism does not always hold: e.g., in case m = 2 the modules D/(d_{1}) and D/(d_{2}) are not D-isomorphic.

If F_{0} ⊂ F is a differential subfield then one can consider D_{0}-isomorphisms ≃_{D_{0}} where D_{0} = F_{0}[d_{1}, …, d_{m}], i.e. to take the coefficients a_{ij}, b_{ij} of matrices A, B from D_{0}. For example, one could take F_{0} = \overline{Q}(X_{1}, …, X_{m}) (see Section 7). In [20] several algorithms are exposed to compute the dimension of the C-space of D_{0}-automorphisms of D_{0}/I_{1} in the ordinary case m = 1. In Section 9 an algorithm is designed which describes the set of all D_{0}-homomorphisms, D_{0}-isomorphisms (and in particular, D_{0}-automorphisms) of finite-dimensional D_{0}-modules.

2 Relative syzygies of D-modules

Definition 2.1 Let I ⊆ J ⊆ D^{n} be two D-modules, and let J =< g_{1}, …, g_{t} >. The relative syzygies D-module Syz(I, J) of I and J is Syz(I, J) = {(h_{1}, …, h_{t}) ∈ D^{t}| ∑ h_{i}g_{i} ∈ I}.

This definition is more general than the definition of the quotient of D-modules in [11] because we do not require g_{1}, …, g_{t} to be a Janet basis of J (for a background on Janet basis see e.g. [9, 10, 13, 18]) and in addition it takes into account all the relations among g_{1}, …, g_{t} which put them in I. We notice that in case when I = 0 the module Syz(0, J) coincides with the usual syzygies module Syz(J). Our next goal is to show that Definition 2.1 does not depend in fact, on the choice of generators g_{1}, …, g_{t}.

Lemma 2.2 Let I ⊆ I_{1} ⊆ J be D-modules. Then Syz(I_{1}, J)/Syz(I, J) ≃ I_{1}/I.

Proof. First we verify that the mapping φ(h_{1}, …, h_{t}) = ∑ h_{i}g_{i} provides a homomorphism φ : Syz(I_{1}, J)/Syz(I, J) → I_{1}/I being a monomorphism according to Definition 2.1. Finally, for any representative g ∈ I_{1} of a class ḡ ∈ I_{1}/I one can write g = ∑ h_{i}g_{i}, then φ(h_{1}, …, h_{t}) = g. □

Corollary 2.3 i) D^{t}/Syz(I, J) ≃ J/I; ii) Syz(I, J)/Syz(J) ≃ I.

The main goal for introducing the relative syzygies module according to Definition 2.1 is the following statement proved in [11] in case when g_{1}, …, g_{t} being a Janet basis of J.

Lemma 2.4 With the notation above there holds V_{Syz(I,J)} ≃_{D} V_{I}/V_{J}.

Proof. The mapping ψ : v → (g_{1}, …, g_{t})^{T} v assures the D-monomorphism V_{I}/V_{J} ↪ V_{Syz(I,J)} ⊂ F^{t}. To establish that it is an epimorphism, suppose first that g_{1}, …, g_{t} constitute a Janet basis of J. Let y = (y_{1}, …, y_{n}) be a vector of differential indeterminates. For any vector (w_{,} …, w_{t})^{T} ∈ V_{Syz(I,J)} the system of linear pde’s g_{i}y = w_{i}, 1 ≤ i ≤ t is solvable since {g_{1}y − w_{1}, …, g_{t}y − w_{t}} is a linear coherent autoreduced set, see page 136 in [9], also Theorem 5.5.6, page 247 [10] and [11]. Taking any f ∈ I one can represent f = ∑ h_{i}g_{i}, then (h_{1}, …, h_{t}) ∈ Syz(I, J) and 0 = ∑ h_{i}w_{i} = fy, thus y ∈ V_{I}. This completes the proof that ψ : V_{I}/V_{J} ≃ V_{Syz(I,J)} is a D-isomorphism.

To get rid of the supposition that g_{1}, …, g_{t} constitute a Janet basis take an arbitrary set g_{1}^{(1)}, …, g_{t_{1}}^{(1)} of generators of J and construct the syzygies module Syz(I, J)^{(1)} ⊂ D^{t_{1}}; the notation Syz(I, J)^{(1)} is used to distinguish it from the syzygies module Syz(I, J) constructed from a Janet basis g_{1}, …, g_{t}. Corollary 2.3 implies that D^{t}/Syz(I, J) ≃ D^{t_{1}}/Syz(I, J)^{(1)}. Proposition 1.1 entails that V_{Syz(I,J)} ≃_{D} V_{Syz(I,J)^{(1)}}. Together with the D-isomorphism ψ this completes the proof. □

The following corollary claims that the space of solutions V_{Syz(I,J)} of a syzygies module depends just on the factor of D-modules J/I.

Corollary 2.5 Let I_{1} ⊆ J_{1} ⊆ D^{n_{1}}, I_{2} ⊆ J_{2} ⊆ D^{n_{2}}. Then J_{1}/I_{1} ≃ J_{2}/I_{2} if and only if

V_{Syz(I_{1},J_{1})} ≃_{D} V_{I_{1}}/V_{J_{1}} ≃_{D} V_{I_{2}}/V_{J_{2}} ≃_{D} V_{Syz(I_{2},J_{2})}.

Proof. Corollary 2.3 implies that J_{1}/I_{1} ≃ D^{q_{1}}/Syz(I_{1}, J_{1}) and J_{2}/I_{2} ≃ D^{q_{2}}/Syz(I_{2}, J_{2}). Both D-isomorphisms V_{Syz(I_{1},J_{1})} ≃_{D} V_{I_{1}}/V_{J_{1}} and V_{Syz(I_{2},J_{2})} ≃_{D} V_{I_{2}}/V_{J_{2}} follow from Lemma 2.4. Proposition 1.1 entails that V_{Syz(I_{1},J_{1})} ≃_{D} V_{Syz(I_{2},J_{2})} if and only if D^{q_{1}}/Syz(I_{1}, J_{1}) ≃ D^{q_{2}}/Syz(I_{2}, J_{2}) □

Remark 2.6 As usually, having Janet bases of I =< f_{1}, …, f_{s} > and of J =< g_{1}, …, g_{t} > one can construct a Janet basis of Syz(I, J), e. g. cf. Theorem 5.3.7 in [10], also [11]. Briefly to remind, for each f_{j} there holds f_{j} = ∑ h_{i,j}g_{i}, 1 ≤ j ≤ s for certain h_{i,j} ∈ D. Furthermore, for each pair (k, j) with 1 ≤ k < j ≤ t we represent the Δ-polynomial of g_{k} and g_{j} as lc(g_{j})θ_{1}g_{k} − lc(g_{k})θ_{2}g_{j} = ∑ h_{ijk}g_{i} such that the operators lc(g_{j})θ_{1}g_{k} and lc(g_{k})θ_{2}g_{j} have the same leading terms with the minimal possible leading derivative w.r.t. the applied term ordering ≺. Then the basis of Syz(I, J) consists of the vectors (h_{1,j}, …, h_{t,j}), 1 ≤ j ≤ s, and of the vectors

(h_{1jk}, …, h_{kjk} − lc(g_{j})θ_{1}, …, h_{jjk} − lc(g_{k})θ_{2}, …, h_{tjk}), 1 ≤ k < j ≤ t.  (3)

In the special case I = 0, the relative syzygies module Syz(0, J) reduces to the syzygies module of J. Then as in Schreyer’s theorem, page 212 of [3], one can show that the constructed basis of Syz(0, J) which consists of vectors of the form (3), constitutes in fact, a Janet basis.

We mention also that relying on the algorithm from [7] one can produce a basis of Syz(I, J) starting with arbitrary, not necessarily Janet bases, of I and J, with double-exponential complexity.

Let us denote by H_{I} the Hilbert-Kolchin polynomial of I w.r.t. the usual filtration by order of derivatives, so (D^{n})_{r} = {f ∈ D^{n} : ord f ≤ r} (cf. page 223 of [10]). Denote by τ ≤ m the degree of H_{I} (which is also called the differential type of I [9], page 130 and [10], page 229), and by a_{τ} (I) the coefficient at the power τ in H_{I} (which is also called the typical differential dimension of I ibid.). Then a_{τ} (I) = lc(H_{I}) is the leading coefficient of H_{I}. The next theorem can be deduced directly from Theorem 5.2.9 of [10], but we give an independent proof following the arguments from [10], cf. also Theorem 4.1 in [21].

Theorem 2.7 With the above notation there holds deg (H_{J}) ≤ deg (H_{I}), deg (H_{Syz(I,J)}) ≤ deg (H_{I}) and deg (H_{Syz(I,J)}) = deg (H_{I} − H_{J}), lc (H_{Syz(I,J)}) = lc (H_{I} − H_{J}), in particular a_{τ} (Syz(I, J)) = a_{τ} (I) − a_{τ} (J).

Proof. We recall that the isomorphism φ : D^{t}/Syz(I, J) ↪ J/I in Lemma 2.2 (putting I_{1} = J) maps h_{1}, …, h_{t} to ∑ h_{i}g_{i}. Let ord(g_{i}) ≤ p, 1 ≤ i ≤ t. Since we have in the filtration (J/I)_{r} = J_{r}/I_{r}, r ≥ 0 (cf. Theorem 5.1.8 of [10]) we obtain that φ((D^{t}/Syz(I, J))_{r}) ⊆ (J/I)_{r+p} and thereby

H_{Syz(I,J)}(r) = dim_{F} (D^{t}/Syz(I, J))_{r} ≤ dim_{F} (J/I)_{r+p} = H_{I}(r + p) − H_{J}(r + p)

for sufficiently large r.

Conversely, assuming w.l.o.g that g_{1}, …, g_{t} constitute a Janet basis of J we conclude that for any g ∈ (J/I)_{r} on can represent g = ∑ h_{i}g_{i} with ord(h_{i}g_{i}) ≤ r, 1 ≤ i ≤ t and hence

H_{I}(r) − H_{J}(r) = dim_{F} (J/I)_{r} ≤ dim_{F} (D^{t}/Syz(I, J))_{r} = H_{Syz(I,J)}(r)

for sufficiently large r. This completes the proof. □

Remark 2.8 We say that an ideal I_{1} (or a system of linear pde’s) is of lower gauge than another one I_{2} if the pair (deg(H_{I_{1}}), lc(H_{I_{1}})) is less than (deg(H_{I_{2}}), lc(H_{I_{2}})) in the lexicographic ordering. Taking into account Corollary 2.5 one can talk also about the gauges of the corresponding spaces of solutions V_{I_{1}} and V_{I_{2}}.

The construction of the relative syzygies allows one to reduce finding a basis of V_{I} to finding a basis of V_{J} and joining it with any solution y of the system g_{i}y = w_{i}, 1 ≤ i ≤ t (see the proof of Lemma 2.3) for each element (w_{1}, …, w_{t}) of a basis of V_{Syz(I,J)}. An algorithm for solving the inhomogeneous system g_{i}y = w_{i} may be obtained by a proper generalization of Lagrange’s variation of constants, see e. g. the textbook [23], page 193-195. Theorem 2.7 implies that both J and Syz(I, J) have gauges not greater than the gauge of I. Moreover, in the applications in the next Sections 3, 4, 5, 6 the gauges of J and Syz(I, J) will be actually lower than the gauge of I. In case of a finite-dimensional ideal I this reduction was exploited in [11].

3 Loewy decomposition of finite-dimensional modules

Let us first study the case of a finite-dimensional module I ⊂ D^{n}, i. e. modules of differential type 0. Consider the intersection R(I) = J^{(0)} = ∩J of all maximal modules J ⊇ I (any intersection of maximal modules will be called a complete intersection), we mention that R(I) plays a role similar to the role of the radical of two-sided ideals in a ring. Note that there exists a finite number of maximal modules J_{1}, …, J_{q} for which J_{1} ∩ ⋯ ∩ J_{q} = R(I). Indeed, keep taking J_{1}, J_{2}, … while it is possible to have dim_{C}(J_{1} ∩ ⋯ ∩ J_{i+1}) > dim_{C}(J_{1} ∩ ⋯ ∩ J_{i}) for every i ≥ 1 (slightly abusing the notations by dim_{C}(I) we mean dim_{C}(V_{I})). Since dim_{C}(I) < ∞ we arrive finally at J_{1}, …, J_{q} such that dim_{C}(J_{1} ∩ ⋯ ∩ J_{q} ∩ J) = dim_{C}(J_{1} ∩ ⋯ ∩ J_{q}) for any maximal module J ⊇ I. Then J_{1} ∩ ⋯ ∩ J_{q} = R(I). Applying this procedure to the relative syzygies module I^{(1)} = Syz(I, J^{(0)}) (replacing the role of I), which one can compute making use of Remark 2.6, this yields a complete intersection J^{(1)} such that J^{(1)} = R(I^{(1)}) ⊇ I^{(1)}. Continuing this way, one obtains subsequently the complete intersections J^{(0)}, J^{(1)}, …, J^{(s)} and the modules I^{(1)}, …, I^{(s)} such that J^{(l)} = R(I^{(l)}) and I^{(l+1)} = Syz(I^{(l)}, J^{(l)}), 0 ≤ l ≤ s − 1, adopting that I^{(0)} = I. At the last step J^{(s)} = I^{(s)} holds. We have dim_{C}(I^{(l)}) − dim_{C}(I^{(l+1)}) = dim_{C}(J^{(l)}), 0 ≤ l ≤ s adopting I^{(s+1)} = {0}. Thus, dim_{C}(I) = ∑_{0≤l≤s} dim_{C}(J^{(l)}), which provides an upper bound s < dim_{C}(I) on the number of steps of the described procedure. The uniquely defined sequences J^{(0)}, J^{(1)}, …, J^{(s)} and I^{(1)}, …, I^{(s)} can be viewed as a Loewy decomposition of I.

To get the spaces of solutions V_{J^{(l)}}, 0 ≤ l ≤ s of the complete intersections J^{(l)} = ∩_{q}J_{q} where J_{q} being maximal modules, we apply the result from [21, 2] which states that V_{J^{(l)}} = ∑_{q} V_{J_{q}}.

4 Loewy decomposition of infinite-dimensional modules

Now we proceed to a Loewy decomposition of an infinite-dimensional module I ⊂ D^{n} of a differential type τ > 0. Denote τ = dim(I) and lc(I) to be the leading coefficient of the Hilbert-Kolchin polynomial h_{I}.

Introduce the following relation on all the modules J ⊂ D^{n} with dim(J) = τ. We say that J_{1} and J_{2} are τ-equivalent if dim(J_{1} ∩ J_{2}) = τ and lc(J_{1}) = lc(J_{2}) = lc(J_{1} ∩ J_{2}). In particular, J_{1}, J_{2} are of the same gauge (see Remark 2.8). Informally speaking, this relation means that the spaces V_{J_{1}}, V_{J_{2}} differ by subspaces of differential types less than τ, taking into account that dim(J_{1} + J_{2}) = τ and lc(J_{1} + J_{2}) = lc(J_{1} ∩ J_{2}) due to Theorem 4.1 [21]. Therefore, τ-equivalence is an equivalence relation. Denote by [J] = [J]_{τ} the τ-equivalence class which contains J.

We say that [J_{1}] is subordinated to [J_{2}] if J_{1} ∩ J_{2} is τ-equivalent to J_{1}. One can verify that this relation does not depend on representatives J_{1} and J_{2} of the classes. We denote this relation by [J_{1}] ⊴ [J_{2}]. Then lc(J_{1}) ≥ lc(J_{2}). If in addition [J_{1}] ≠ [J_{2}] (we denote this by [J_{1}] ⊲ [J_{2}]) then lc(J_{1}) > lc(J_{2}). Hence any increasing chain of τ-equivalence classes stops and one can consider maximal τ-equivalence classes.

For any τ-equivalence classes [J_{1}], [J_{2}] satisfying [J] ⊴ [J_{1}], [J] ⊴ [J_{2}] one can uniquely define the class [J_{1} ∩ J_{2}] such that [J] ⊴ [J_{1} ∩ J_{2}]. One can verify that dim(J_{1} ∩ J_{2}) = τ and the class [J_{1} ∩ J_{2}] does not depend on the representatives J_{1}, J_{2}.

Now take all the τ-maximal classes [J] such that [I] ⊴ [J]. Since J + I is τ-equivalent to J (again due to Theorem 4.1 [21]) we can assume without loss of generality that the representatives are chosen in such a way that I ⊆ J. We choose consecutively such classes [J_{1}], [J_{2}], …, [J_{p}] while it is possible to have

[J_{1}] ⊳ [J_{1} ∩ J_{2}] ⊳ ⋯ ⊳ [J^{(0)} = J_{1} ∩ J_{2} ∩ ⋯ ∩ J_{p}].

Clearly, p ≤ lc(I). Then for any maximal class [J] for which [I] ⊴ [J], we obtain [J^{(0)}] ⊴ [J]. Hence for any finite family [J1^{′}], …, [Jq^{′}] of τ-maximal classes for which [I] ⊴ [Jl^{′}], 1 ≤ l ≤ q, we conclude that [J^{(0)}] ⊴ [J1^{′} ∩ ⋯ ∩ Jq^{′}]. Therefore, the class [J^{(0)}] is defined uniquely and in addition I ⊆ J^{(0)} holds. We say that J^{(0)} = J_{1} ∩ J_{2} ∩ ⋯ ∩ J_{p} is completely τ-reducible.

We define a Loewy decomposition of I by induction on the gauge of I. As a base of induction when the τ-class [I] is maximal then I provides a Loewy decomposition of itself. When [I] is not maximal one can further apply the described inductive definition of a Loewy decomposition (thereby, replacing the role of I) to the relative syzygies module I^{(1)} = Syz(I, J^{(0)}) (see Section 2) taking into account that either dim(I^{(1)}) < τ or dim(I^{(1)}) = τ, and in the latter case lc(I^{(1)}) = lc(I) − lc(J^{(0)}) < lc(J) due to Theorem 2.7; in other words, I^{(1)} is of a lower gauge than I. In case when dim(I^{(1)}) < τ we have [I] = [J^{(0)}] again due to Theorem 2.7 and [I] being completely τ-reducible.

Continuing this way we arrive at a sequence of modules J^{(0)}, J^{(1)}, …, J^{(q)} with non-decreasing differential types such that each module J^{(l)}, 0 ≤ l ≤ q is completely dim(J^{(l)})-reducible. We notice that this sequence is not necessarily unique unlike the Loewy decomposition of a finite-dimensional module (see Section 3). The obtained sequence could be called a Loewy decomposition of I. At present we don’t possess an algorithm to construct it in general.

5 Primary decomposition of finite-dimensional modules

Again let I ⊂ D^{n} be a finite-dimensional module. Denote by J^{(0)} = N(I) = ∩_{J⊃I}J the intersection of all ideals J properly containing I (we mention that N(I) plays a role similar to the role of the nil-radical of two-sided ideals in a ring). We call I primary if N(I) ≠ I. In the latter case N(I) is the minimal module which properly contains I and the relative syzygies module Syz(I, N(I)) is a maximal module.

Lemma 5.1 Any module I is an intersection of a finite number of primary modules.

Proof goes by induction on dim_{C}(I). The base of induction for a maximal module is obvious because it is primary. For the inductive step in case when I is not primary one can represent it as a finite intersection I = J_{1} ∩ ⋯ ∩ J_{q} with J_{i} ⊃ I (cf. Section 3). Then lemma follows from the inductive hypothesis applied to J_{i}. □

Therefore, by recursion on dim_{C}(I) one can define a primary decomposition of I. If I is not primary then one takes I = J_{1} ∩ ⋯ ∩ J_{q} from Lemma 5.1 and the primary decomposition of I is defined as the collection of primary decompositions of J_{1}, …, J_{q} by the recursive hypothesis. For a primary module I its primary decomposition consists of a pair of the relative syzygies module Syz(I, N(I)) (being a maximal module) and a primary decomposition of N(I) by the recursive hypothesis.

One can view as an advantage of a primary decomposition versus the Loewy decomposition from Section 3 that the expensive operation of taking the relative syzygies module leads to a maximal module, and so taking relative syzygies modules do not iterate each other. On the other hand, a primary decomposition is not unique, but still allows one to find the space V_{I} by combining the already cited result from [21, 2], and also obtaining V_{I} from V_{J} and the space V_{I}/V_{J} (see Remark 2.8).

6 Primary decomposition of infinite-dimensional modules

We follow the notations from Section 4. We choose consecutively classes [J_{1}], [J_{2}], …, [J_{p}] (again one can assume that I ⊆ J_{i}) while it is possible such that

[J_{1}] ⊳ [J_{1} ∩ J_{2}] ⊳ ⋯ ⊳ [J^{(0)} = J_{1} ∩ J_{2} ∩ ⋯ ∩ J_{p}].

Then for any class [J] for which [I]⊲[J] we have [J^{(0]}]⊴[J]. We denote [J^{(0]}] = N_{τ} ([I]). If N_{τ} ([I])⊳[I] we call [I] τ-primary.

We define a primary decomposition of I by induction on the gauge of I. For the base of induction when [I] is a maximal τ-equivalence class then I constitutes its own primary decomposition. For the inductive step a primary decomposition of I consists of the ones of the modules J_{1}, …, J_{p} and in addition of the relative syzygies module Syz(I, J^{(0)}) which has a gauge less than the gauge of I (due to Theorem 2.7, cf. Section 4). We observe that when the differential type dim(Syz(I, J^{(0)})) = τ then Syz(I, J^{(0)}) is τ-maximal and provides its own primary decomposition, else dim(Syz(I, J^{(0)})) < τ and one deals further in the induction with modules of differential types less than τ.

As a result we arrive at a set of modules {J} such that each [J] is a dim(J)-maximal class, which one can view as a primary decomposition of I. It would be interesting to design an algorithm which constructs a primary decomposition.

7 Parametric-algebraic families of D-modules

For the rest of the paper, dealing with the design of algorithms, we assume that the coefficients of the input operators belong to the differential field F_{0} = \overline{Q}(X_{1}, …, X_{m}) (cf. Remark 1.2) with derivatives d_{k} = ∂/∂X_{k}, 1 ≤ k ≤ m and D_{0} = F_{0}[d_{1}, …, d_{m}], D = F [d_{1}, …, d_{m}] where F is a universal extension of F_{0}.

In the sequel we suppose that all the considered algebraic (affine) varieties W ⊂ \overline{Q}^{N} are given in an efficient way, say as in [5]. Namely, W = ∪W_{j} where W_{j} are irreducible over Q components of W, and the algorithms from [5] represent each W_{j} (of a dimension s) in two following ways.

First, we represent W_{j} by means of a generic point, i.e. an isomorphism

Q(t_{1}, …, t_{s})[α] ≃ Q(W_{j})  (4)

where Q(W_{j}) is the field of rational functions on W_{j}. The elements t_{1}, …, t_{s} ⊂ {Z_{1}, …, Z_{N}} constitute a basis of transcendency of Q(W_{j}) over Q which can be taken among the coordinates Z_{1}, …, Z_{N} of the affine space \overline{Q}^{N}. The element α = ∑_{1≤l≤N} α_{l}Z_{l} for suitable integers α_{l} is algebraic over the field Q(t_{1}, …, t_{s}) with a minimal polynomial ϕ ∈ Q(t_{1}, …, t_{s})[Z]. The algorithms from [5] yield the ingredients of (4) explicitly, in other words, t_{1}, …, t_{s}; α_{1}, …, α_{N}; ϕ and the rational expressions of Z_{l} via t_{1}, …, t_{s}, α, i.e. the rational functions of the form g_{l}(t_{1}, …, t_{s}, Z)/g(t_{1}, …, t_{s}) where the polynomials g(t_{1}, …, t_{s}), g_{l}(t_{1}, …, t_{s}, Z) ∈ Q[t_{1}, …, t_{s}, Z] being such that the equality Z_{l} = g_{l}(t_{1}, …, t_{s}, Z)/g(t_{1}, …, t_{s}) holds everywhere on W_{j}.

Second, the algorithms from [5] yield polynomials h_{1}, …, h_{M} ∈ Q[Z_{1}, …, Z_{N}] such that W_{j} coincides with the variety of all the points from \overline{Q}^{N} which satisfy the system of equations h_{1} = ⋯ = h_{M} = 0.

The algorithms from [5] allow one to produce the union, intersection, complement of varieties, to get the dimension of W_{j}, to project a variety (in other words, to eliminate quantifiers), to find all the points of W_{j} in case when it is finite (i.e. zero-dimensional) or to yield as many points as one wishes in case when W_{j} is infinite (positive-dimensional). Moreover, one extends these algorithms from varieties to constructive sets , i.e. the unions of the sets of the form W′ \ W′′ where W′, W′′ are varieties (in other terms, constructive sets constitute the boolean algebra generated by all the varieties).

Definition 7.1 We say that a family of D-modules J = {J} ⊂ D^{n} is parametric-algebraic if there is a constructive set V = ∪V_{j} ⊂ \overline{Q}^{N} for an appropriate N such that J = ∪J_{j} and for any fixed j the following holds. A Janet basis of any J ∈ J_{j} has fixed leading derivatives lder(J) = lder_{j} and the parametric derivatives pder(J) = pder_{j} (see [11]). Moreover, any element of the Janet basis of J has the form

γ_{0} + ∑_{γ∈pder_{j}} A_{γ}(Z_{1}, …, Z_{N})γ  (5)

where γ_{0} ∈ lder_{j} and A_{γ} ∈ Q(Z_{1}, …, Z_{N})(X_{1}, …, X_{m}).

When (Z_{1}, …, Z_{N}) ranges over the constructive set V_{j}, the set of linear differential operators of the form (5) for all γ_{0} ∈ lder_{j} ranges over the Janet basis for all modules J from J_{j}. Thus, we have a bijective correspondance between the points of V_{j} and the modules (or more precisely, their Janet basis) from J_{j}.

We rephrase in our terms the following proposition which was actually proved in [11].

Proposition 7.2 ([11]). One can design an algorithm which for any finite-dimensional D-module I ⊂ D^{n} finds a parametric-algebraic family of all the factors of I, i.e. the modules J ⊂ D^{n} such that I ⊂ J.

Lemma 7.3 One can design an algorithm which for a pair of parametric-algebraic families I, J of D-modules yields the parametric-algebraic family of all the pairs (I, J) where I ∈ I, J ∈ J such that I ⊆ J.

Proof. Let

{γ_{0} + ∑_{γ∈pder_{j}} A_{γ}(Z_{1}, …, Z_{N})γ}_{γ_{0}∈lder_{j}}

be a Janet basis of J_{j} and

{λ_{0} + ∑_{λ∈pder_{s}} B_{λ}(Z_{1}, …, Z_{N})λ}_{λ_{0}∈lder_{s}}

be a Janet basis of I_{s}. Then the condition that I ⊆ J for I ∈ I_{s}, J ∈ J_{j} can be expressed as the existence for each λ_{0} ∈ lder_{s} of operators of the form ∑_{θ} C_{θ,γ_{0},λ_{0}}θ ∈ D where θ ≺ θ_{0} and λ_{0} = θ_{0}y_{i} for a certain 1 ≤ i ≤ n such that

λ_{0} + ∑_{λ∈pder_{s}} B_{λ}(Z_{1}, …, Z_{N})λ = ∑_{γ_{0}∈lder_{j}}(∑_{θ} C_{θ,γ_{0},λ_{0}}θ)(γ_{0} + ∑_{γ∈pder_{j}} A_{γ}(Z_{1}, …, Z_{N})γ)  (6)

where the external summation in the right-hand side ranges over the elements of the Janet basis of J_{j}.

Clearly, one can rewrite (6) as a system of linear (algebraic) equations in the unknowns C_{θ,γ_{0},λ_{0}}, while the entries of this system are the rational functions from Q(X_{1}, …, X_{m})(Z_{1}, …, Z_{N}). One can find the constructive set U = U_{j,s} ⊂ \overline{Q}^{N} such that just for (Z_{1}, …, Z_{N}) ∈ U this linear system is solvable. Combining this for all pairs l, s completes the proof of the lemma. □

Corollary 7.4 For a finite-dimensional D-module I ⊂ D^{n} one can find a parametric-algebraic family I_{max} of all maximal D-modules J which contain I.

Proof. Among the family of all the factors J of I produced in proposition 7.2 one can relying on Lemma 7.3 distinguish all J_{0} such that if J_{0} ⊆ J then J_{0} = J holds. □

8 Constructing Loewy and primary decompositions of finitedimensional modules

Now we are able for a finite-dimensional D-module I ⊂ D_{0}^{n} to construct its Loewy (see section 3) and primary decompositions (see section 5). First, in order to obtain Loewy decomposition we apply corollary 7.4. After that the purpose is to find the intersection R(I) of all the maximal modules from I_{max}. To this end we conduct the (internal) recursion on dim(R(I)). Assume that a current (complete) intersection J_{0} of several maximal modules from I_{max} is already constructed. Applying lemma 7.3 we test whether there exists a maximal module J ∈ I_{max} which does not contain J_{0}. Then we replace J_{0} by the (complete) intersection J ∩ J_{0} and continue the (internal) recursion. Finally, we arrive at R(I) and thereupon (by the external recursion) proceed to the relative syzygies module Syz(I, R(I)) (see section 2), provided that the latter is not zero, else halt.

In order to construct a primary decomposition of I we use Proposition 7.2 and Lemma 7.3 in a similar way and (by the internal recursion) compute the intersection N(I) of all the modules strictly containing I in the form N(I) = ∩J where the latter intersection is finite. Thereupon we proceed (by the external recursion) to primary decompositions of all the non-maximal J from this intersection joined by the relative syzygies module Syz(I, N(I)) (provided that the latter does not vanish). If all J are maximal then halt.

Thus, we have shown the following

Corollary 8.1 For a finite-dimensional D-module I ⊂ D_{0}^{n} one can construct its Loewy and primary decompositions.

9 Testing isomorphism of finite-dimensional D-modules

We follow the notations of Section 1. We assume that the field of constants C ⊂ F coincides with Q̄ and the modules I_{1} ⊂ D^{n_{1}}, I_{2} ⊂ D^{n_{2}} are defined over the field F_{0} = Q̄(X_{1}, …, X_{m}). We design an algorithm to test whether D^{n_{1}}/I_{1} ≃_{D_{0}} D^{n_{2}}/I_{2}. W.l.o.g. one can suppose that dim(D^{n_{1}}/I_{1}) = dim(D^{n_{2}}/I_{2}) = l. Then dim_{C}V_{I_{1}} = dim_{C}V_{I_{2}} = l ([9], page 151). Let I_{1} =< g_{1}, …, g_{q} >, I_{2} = < f_{1}, …, f_{p} > be Janet bases of I_{1} and I_{2} respectively. The condition that a matrix A = (a_{i,j}) with a_{i,j} ∈ D provides a D-homomorphism can be expressed as a system

∑_{1≤i≤n_{1}} g_{s,i}a_{i,j} = ∑_{1≤t≤p} h_{s,t}f_{t,j}, 1 ≤ s ≤ q, 1 ≤ j ≤ n_{2}  (7)

of lpde’s with unknowns a_{i,j}, h_{s,t} ∈ D. Since a_{i,j} are taken modulo f_{j}, 1 ≤ j ≤ p one can assume a_{i,j} to be reduced modulo f_{j}, 1 ≤ j ≤ p. Let ord(g_{s}), ord(f_{j}) ≤ r, 1 ≤ s ≤ q, 1 ≤ j ≤ p, then ord(a_{i,j}) ≤ r, ord(g_{s,i}a_{i,j}) ≤ 2r and therefore ord(h_{s,t}f_{t,j}) ≤ 2r as well because f_{1}, …, f_{p} is a Janet basis. Thus writing a_{i,j} = ∑_{K} a_{i,j,K}d^{K}, h_{s,t} = ∑_{K} h_{s,t,K}d^{K} with the weights of multiindices |K| ≤ 2r, one can treat (7) as a system of lpde’s in the indeterminates a_{i,j,K} and h_{s,t,K}.

By virtue of Corollary 2.5 the matrix A provides a C-linear transformation of l-dimensional Cvector spaces (V_{I_{2}})^{T}, (V_{I_{1}})^{T}. If A provides a zero transformation then A ⊂ I_{2} due to the duality in the Zariski topology (cf. the proof of Proposition 2.5). Hence the a_{i,j}-components of all solutions of (7) constitute a C-linear subspace of l × l matrices representing C-linear transformations between (V_{I_{2}})^{T} and (V_{I_{1}})^{T}. In other words, Hom(D^{n_{1}}/I_{1}, D^{n_{2}}/I_{2}) can be viewed as a C-linear subspace of l ×l matrices over C (this generalizes the considerations of the ordinary case m = 1, see pages 42-44 [14]).

In terms close to Definition 7.1 Hom(D^{n_{1}}/I_{1}, D^{n_{2}}/I_{2}) can be represented as parametric-linear family A(Z) = (a_{i,j}(Z)) where the parameters Z = ({Z_{u}}_{1≤u≤N}) range over the space C^{N}, and a_{i,j}(Z) depend on Z linearly.

The algorithm finds this parametric-linear family A(Z) by producing a Janet basis of system (7). We have already established that A(Z) lies in a finite-dimensional C-vector space of dimension at most N ≤ l^{2}, therefore one obtains from the Janet basis an ideal of A(Z) and thereupon making use of [11], page 448, finds a basis of all rational solutions A(Z) over the field F_{0}. Slightly changing the notation, we keep the notation A(Z) for the parametric-linear family of all elements from Hom(D_{0}^{n_{1}}/I_{1}, D_{0}^{n_{2}}/I_{2}) with rational coefficients, in other words, D_{0}-homomorphisms.

In a similar way the algorithm yields a parametric-linear family B(Z′) of all the elements from Hom(D_{0}^{n_{2}}/I_{2}, D_{0}^{n_{1}}/I_{1}) with rational coefficients. Then D_{0}^{n_{1}}/I_{1} and D_{0}^{n_{2}}/I_{2} are D_{0}-isomorphic if and only if there exist elements of the form A = A(Z), B = B(Z′) such that AB|_{D_{0}^{n_{2}}/I_{2}} = id, BA|_{D_{0}^{n_{1}}/I_{1}} = id that can be rewritten as a system

BAe_{i} − e_{i} = ∑_{1≤t≤q} h_{t}g_{t}, 1 ≤ i ≤ n_{1}, ABe′_{j} − e′_{j} = ∑_{1≤s≤p} h′_{s}f_{s}, 1 ≤ j ≤ n_{2}  (8)

with unknowns h_{t}, h′_{s}, where e_{1}, …, e_{n_{1}} (respectively e′_{1}, … e′_{n_{2}}) form a basis of the free module D_{0}^{n_{1}} (respectively D_{0}^{n_{2}}).

We have already seen that ord(A), ord(B) ≤ r, hence ord(h_{t}g_{t}), ord(h′_{s}f_{s}) ≤ 2r, taking into account that g_{1}, …, g_{q} and f_{1}, …, f_{p} constitute Janet bases. Denote h_{t} = ∑ h_{t,K}d^{K}, h′_{s} = ∑ h′_{s,K}d^{K} where |K| ≤ 2r. Thus one can treat (8) as a parametric linear algebraic system in the indeterminates h_{t,K}, h′_{s,K} with parameters Z, Z′. One can solve such a parametric system using an algorithm described e.g. in [6]. The algorithm outputs the constructive set of all parameters Z, Z′ for which system (8) is solvable, i.e. which provide an isomorphism A(Z), B(Z′), in particular this constructive set is not empty if an only if D_{0}^{n_{1}}/I_{1} and D_{0}^{n_{2}}/I_{2} are D_{0}-isomorphic. We summarize the results of the present section in the following theorem.

Theorem 9.1 There is an algorithm which finds for any pair of finite-dimensional D_{0}-modules all D_{0}- homomorphisms (respectively isomorphisms) of D_{0}^{n_{1}}/I_{1} and D_{0}^{n_{2}}/I_{2} as a parametric-linear (respectively parametric-algebraic) family. By the same token the algorithm can yield the (algebraic) groups of all D_{0}-automorphisms of the D_{0}-module D_{0}^{n_{1}}/I_{1}.

It would be interesting to design an algorithm to test D_{0}-isomorphism or even D-isomorphism of infinite-dimensional D-modules.

Acknowledgments. The paper was done during a stay of the first author at the institute SCAI of the Fraunhofer Gesellschaft, supported by the Forschungspreis of the Humboldt Foundation which is gratefully acknowledged.

References

[1] E. Beke, Die Irreduzibilität der homogenen linearen Differentialgleichungen, Mathematische Annalen 45, 278–294(1894).

[2] P. Cassidy, Differential Algebraic Groups, Amer. J. Math., 94, 891-954 (1972).

[3] D. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, Springer, 1998.

[4] S. C. Coutinho, A Primer of Algebraic D-Modules, London Mathematical Society Student Texts, Vol. 33, Cambridge University Press, Cambridge, 1995.

[5] D. Grigoriev, Computational complexity in polynomial algebra, Proc. Intern. Congress of Mathematicians, vol. 2, Berkeley, 1452-1460, 1986.

[6] D. Grigoriev, Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators, J. Symbolic Computation, 7, 7-37 (1990).

[7] D. Grigoriev, Complexity of Solving Systems of Linear Equations over the Rings of Differential Operators, Progress in Math., Birkhauser, 94, 195-202 (1991)

[8] D. Grigoriev, F. Schwarz, Factoring and solving linear partial differential equations, Computing (2004)

[9] E. Kolchin, Differential Algebra and Algebraic Groups, Academic Press, 1973.

[10] M. Kondratieva, A. Levin, A. Mikhalev, E. Pankratiev, Differential and difference dimension polynomials, Kluwer, 1999.

[11] Z. Li, F. Schwarz, S. Tsarev, Factoring systems of linear PDE’s with finite-dimensional solution space, J. Symbolic Comput., 36, 443-471 (2003).

[12] A. Loewy, Über vollständig reduzible lineare homogene Differentialgleichungen, Mathematische Annalen, 56, 89-117 (1906).

[13] T. Oaku, Algorithms for finding the structure of solutions of a system of linear partial differential equations, in Proc. Intern. Symp. Symbol. Algebr. Comput., Oxford, ACM, 1994, 216-223.

[14] M. van der Put, M. Singer, Galois theory of linear differential equations, Grundlehren der Mathematischen Wissenschaften, 328, Springer, 2003.

[15] C. Sabbah, D-modules cohérents et holonomes, Travaux en cours, 45, Hermann, 1993.

[16] M. Saito, B. Sturmfels, N. Takayama, Gröbner deformations of hypergeometric differential equations, Algorithms and Computations in Mathematics, 6, Springer, 2000.

[17] L. Schlesinger, Handbuch fuer Theorie der linearen Differentialgleichungen, Leipzig, Teubner, 1897.

[18] F. Schwarz, Janet bases for symmetry groups, Groebner bases and applications, in London Math. Society, Lecture Note Ser., 251, Cambridge University Press, 221-234 (1998).

[19] F. Schwarz, A Factorization Algorithm for Linear Ordinary Differential Equations, Proceedings of the ISSAC’89, page 17-25, ACM Press, 1989, Gaston Gonnet, ed.

[20] M. Singer, Testing Reducibility of Linear Differential Operators: A Group Theoretic Perspective, Applic. Algebra in Engin., Communic. Comp. 7, 77-104 (1996).

[21] W. Sit, Typical Differential Dimension of the Intersection of Linear Differential Algebraic Groups, Journal of Algebra 32, 476-487 (1974).

[22] W. Sit, The Ritt-Kolchin theory for differential polynomials, in ”Differential algebra and related topics”, ed. Li Guo, P.Cassidy, W.Keigher, W.Sit, World Scientific, 2002.

[23] W. W. Stepanow, Lehrbuch der Differentialgleichungen, Deutscher Verlag der Wissenschaften, Berlin, 1956.

[24] S. Tsarev, Factorization of linear partial differential operators and the Darboux method for integrating nonlinear partial differential equations, Theoret. and Math. Phys., 122, 121-133 (2000).