Weak Bézout inequality for D-modules

Dima Grigoriev

IRMAR, Université de Rennes Beaulieu, 35042, Rennes, France

                              dima@math.univ-rennes1.fr

http://name.math.univ-rennes1.fr/dimitri.grigoriev

Dedicated to Arnold Schoenhage

Abstract

Let \{w_{i,j}\}_{1≤i≤n,1≤j≤s} ⊂ L_{m} = F (X_{1}, …, X_{m})[\frac{∂}{∂X_{1}} , …, \frac{∂}{∂X_{m}}] be linear partial differential operators of orders with respect to \frac{∂}{∂X_{1}} , …, \frac{∂}{∂X_{m}} at most d. We prove an upper bound

n(4m^{2}d min{n, s})^{4^{m−t−1}(2(m−t))}

on the leading coefficient of the Hilbert-Kolchin polynomial of the left L_{m}-module ⟨{w_{1,j}, …, w_{n,j}}_{1≤j≤s}⟩ ⊂ L_{m}^{n} having the differential type t (also being equal to the degree of the Hilbert-Kolchin polynomial). The main technical tool is the complexity bound on solving systems of linear equations over algebras of fractions of the form

L_{m}(F [X_{1}, …, X_{m}, \frac{∂}{∂X_{1}} , …, \frac{∂}{∂X_{k}}])^{−1}.

Introduction

Denote the derivatives D_{i} = \frac{∂}{∂X_{i}} , 1 ≤ i ≤ m and by A_{m} = F [X_{1}, …, X_{m}, D_{1}, …, D_{m}] the Weyl algebra [2] over an infinite field F. It is well-known that A_{m} is defined by the following relations:

X_{i}X_{j} = X_{j}X_{i}, D_{i}D_{j} = D_{j}D_{i}, X_{i}D_{i} = D_{i}X_{i} − 1, X_{i}D_{j} = D_{j}X_{i}, i ≠ j  (1)

For a family {w_{i,j}}_{1≤i≤n,1≤j≤s} ⊂ L_{m} of elements of the algebra of linear partial differential operators one can consider a system

∑_{1≤i≤n} w_{i,j}u_{i} = 0, 1 ≤ j ≤ s  (2)

of linear partial differential equations in the unknowns u_{1}, …, u_{n}. In particular, if the F -linear space of solutions of (2) has a finite dimension l then the quotient of the free L_{m}-module L_{m}^{n} over the left L_{m}-module L = ⟨{w_{1,j}, …, w_{n,j}}_{1≤j≤s}⟩ ⊂ L_{m}^{n} has also the dimension l over the field F (X_{1}, …, X_{m}) [8]. Denote by t the differential type of L [8], then 0 ≤ t ≤ m (observe that the case treated in the previous sentence, corresponds to t = 0).

We consider the filtration on the algebra L_{m} defined on the monomials by ord(cD_{1}^{i_{1}} ⋯ D_{m}^{i_{m}}) = i_{1} + ⋯ + i_{m} where a coefficient c ∈ F (X_{1}, …, X_{m}). With respect to this filtration the dimension dim_{F (X_{1},...,X_{m})}(L_{m}^{n}/L)_{z} of z-component of the quotient L_{m}^{n}/L (for sufficiently big z ≥ z_{0}) equals to the Hilbert-Kolchin polynomial of L [8, 9]:

\frac{l}{t!}z^{t} + l_{t−1}z^{t−1} + ⋯ + l_{0}

of the degree t (which coincides with the differential type of L). The leading coefficient l is called the typical differential dimension [8]. In the treated above particular (holonomic) case t = 0 the dimension of F -linear space of solutions of (2) equals to l.

In case of a module (viewed as a filtered one) over the ring of polynomials the leading coefficient of its Hilbert polynomial equals the degree of the module, and the classical Bézout inequality [13] provides for the leading coefficient an upper bound being the product of the degrees of generators of the module.

In the present paper we prove (see Section 4) the following inequality which could be viewed as a weak analogue of the Bézout inequality for differential modules.

Corollary 0.1 Let ord(w_{i,j}) ≤ d, 1 ≤ i ≤ n, 1 ≤ j ≤ s. Then the leading coefficient of the Hilbert-Kolchin polynomial

l ≤ n(4m^{2}d min{n, s})^{4^{m−t−1}(2(m−t))}

Actually, one could slightly improve this estimate while making it more tedious. We note that the latter estimate becomes better with a smaller value of m−t. In fact, for small values m − t ≤ 2 much stronger estimates are known. In the case m − t = 0 the bound l ≤ n is evident. In the case m − t = 1 the bound l ≤ max_{1≤i≤s}{ord(w_{i,1}} + ⋯ + max_{1≤i≤s}{ord(w_{i,n}} was proved [8] (moreover, the latter bound holds in the more general situation of non-linear partial differential equations, whereas in the situation under consideration in the present paper of linear partial differential equations a stronger Jacobi conjecture was established , see e.g. [9]). In the case m−t = 2, n = 1 the bound l ≤ ord(w_{1})ord(w_{2}) was proved for the left ideal ⟨w_{1}, w_{2}, …⟩ ⊂ L_{m} where ord(w_{1}) ≥ ord(w_{2}) ≥ … [9] which could be viewed as a direct analogue of the Bézout inequality. In the case m = 3, t = 0, n = 1 a counter-example of a left ideal ⟨w_{1}, w_{2}, w_{3}⟩ ⊂ L_{3} is also produced in [9] which shows that the expected upper bound ord(w_{1})ord(w_{2})ord(w_{3}) on l appears to be wrong. It would be interesting to clarify how sharp is the estimate in Corollary 0.1 for large values of m − t.

We mention also that on p.154 [11] a (better than in Corollary 0.1) exponential bound on l (when t = 0) was established in case of a homogeneous toric ideal of the Weyl algebra.

The main technical tool in the proof of Corollary 0.1 is the complexity bound on solving linear systems over algebras of fractions of L_{m}. Let K ⊂ {1, …, m} be a certain subset. Denote by A_{m}^{(K)} = F [X_{1}, …, X_{m}, {D_{k}}_{k∈K}] ⊂ A_{m} the corresponding subalgebra of A_{m}. We consider the algebra of fractions Q_{m}^{(K)} = A_{m}(A_{m}^{(K)})^{−1}. For an element a ∈ A_{m} we denote the Bernstein filtration [2] deg(a) defining it on monomials X_{1}^{j_{1}} ⋯ X_{m}^{j_{m}}D_{1}^{i_{1}} ⋯ D_{m}^{i_{m}} by j_{1} + ⋯ + j_{m} + i_{1} + ⋯ + i_{m}. Then for an element ab^{−1} ∈ Q_{m}^{(K)}, a ∈ A_{m}, b ∈ A_{m}^{(K)} we write that the degree deg(ab^{−1}) ≤ max{deg(a), deg(b)}.

In Section 1 below we study the properties of Q_{m}^{(K)} and the complexity bounds on manipulating in Q_{m}^{(K)}. In Section 2 we establish complexity bounds on quasi-inverse matrices over the algebra Q_{m}^{(K)}. Finally, in Section 3 we consider the problem of solving a system of linear equations over the algebra Q_{m}^{(K)}:

∑_{1≤i≤p} a_{j,i}V_{i} = a_{j}, 1 ≤ j ≤ q  (3)

where the coefficients a_{j,i}, a_{j} ∈ A_{m}, deg(a_{j,i}), deg(a_{j}) ≤ d. We prove the following theorem.

Theorem 0.2 If (3) is solvable over Q_{m}^{(K)} then (3) has a solution with

deg(v_{i}) ≤ (16m^{4}d^{2}(min{p, q})^{2})^{4^{m−|K|}}

Assume now that the ground field F is represented in an effective way, say as a finitely generated extension either of ℚ or of a finite field (see e.g. [6]). Then one can define the bit-size M of the coefficients in F of the input {a_{j,i}, a_{j}}.

Corollary 0.3 One can test the solvability of (3) and if it is solvable then yield some its solution in time polynomial in

M, q, p^{m}, (md min{p, q})^{4^{m−|K|}m}

Theorem 0.2 and Corollary 0.3 generalize the results from [7] established for the algebra Q_{m}^{(∅)} = L_{m} of linear differential operators to the algebras of fractions Q_{m}^{(K)}. In [7] it is noticed that due to the example of [10] the bounds in Theorem 0.2 and Corollary 0.3 are close to sharp.

The problem in question generalizes the one of solving linear systems over the algebra of polynomials which was studied in [12] where the similar complexity bounds were proved. Unfortunately, one cannot extend directly the method from [12] (which arises to G.Hermann) to the (non-commutative) algebra Q_{m}^{(K)} because the method involves the determinants. Nevertheless, we exploit the general approach of [12].

We mention also that certain algorithmical problems in the algebra of linear partial differential operators were posed in [3, 4, 5].

1 Algebra of fractions of differential operators

Let a matrix B = (b_{i,j}), 1 ≤ i ≤ p−1, 1 ≤ j ≤ p have its entries b_{i,j} ∈ A_{m}^{(K)} and deg(b_{i,j}) ≤ d. The following lemma was proved in [7].

Lemma 1.1 There exists a vector 0 ≠ c = (c_{1}, …, c_{p}) ∈ (A_{m}^{(K)})^{p} such that Bc = 0 and moreover, deg(c) ≤ 2(m + |K|)(p − 1)d = N.

Proof. Consider an F -linear space U ⊂ (A_{m}^{(K)})^{p} consisting of all the vectors c = (c_{1}, …, c_{p}) such that deg(c) ≤ N. Then dim U = p\binom{N+m+|K|}{m+|K|}. For any vector c ∈ U we have deg(Bc) ≤ N+d, i.e. Bc ∈ W where the F -linear space W consists of all the vectors w = (w_{1}, …, w_{p−1}) ∈ (A_{m}^{(K)})^{p−1} for which deg(w) ≤ N + d, thereby dim(W) = (p − 1)\binom{N+d+m+|K|}{m+|K|}.

Let us verify an inequality p\binom{N+m+|K|}{m+|K|} > (p−1)\binom{N+d+m+|K|}{m+|K|} whence lemma would follow immediately. Indeed,

\binom{N + d + m + |K|}{m + |K|}/\binom{N + m + |K|}{m + |K|} = \frac{N + d + m + |K|}{N + m + |K|} ⋯ \frac{N + d + 1}{N + 1} ≤ (\frac{N + d + 1}{N + 1})^{m+|K|}.

It suffices to check the inequality (\frac{N+d+1}{N+1})^{m+|K|} < \frac{p}{p−1}. The latter follows in its turn from the inequality

(1 + \frac{1}{p − 1})^{1/(m+|K|)} > 1 + (\frac{1}{m + |K|})\frac{1}{p − 1} + \frac{1}{2}(\frac{1}{m + |K|})(\frac{1}{m + |K|} − 1)\frac{1}{(p − 1)^{2}} >

1 + \frac{1}{2}(\frac{1}{m + |K|})\frac{1}{p − 1} > 1 + \frac{d}{N + 1}

Notice that Lemma 1.1 implies that A_{m}^{(K)} is an Ore domain [2], i.e. the expressions of the form b_{1}b_{2}^{−1} where b_{1}, b_{2} ∈ A_{m}^{(K)} constitute an algebra. Below we use the following notations: letters a, α (respectively, b, β) with subscripts denote the elements from A_{m} (respectively, from A_{m}^{(K)}). Our nearest purpose is to show that the expressions of the form ab^{−1} also constitute an algebra Q_{m}^{(K)} = A_{m}(A_{m}^{(K)})^{−1} (see above the Introduction) and to provide complexity bounds on performing arithmetic operations in Q_{m}^{(K)}. To verify that the sum a_{1}b_{1}^{−1} + a_{2}b_{2}^{−1} can be represented in the desired form a_{3}b_{3}^{−1} we note first the following bound on a (left) common multiple of a family of elements from A_{m}^{(K)} being a consequence of Lemma 1.1.

Corollary 1.2 For a family b_{1}, …, b_{p} ∈ A_{m}^{(K)} of the degrees deg(b_{1}), …, deg(b_{p}) ≤ d there exist c_{1}, …, c_{p} ∈ A_{m}^{(K)} such that b_{1}c_{1} = … = b_{p}c_{p} ≠ 0 of the degrees deg(c_{1}), …, deg(c_{p}) ≤ 2(m + |K|)(p − 1)d.

Evidently, the same bound holds also for a right common multiple of b_{1}, …, b_{p} which

equals to c1^{′}b_{1} = … = cp^{′}b_{p}.

To complete the consideration of the sum one can find c_{1}, c_{2} ∈ A_{m}^{(K)} such that b = b_{1}c_{1} = b_{2}c_{2} according to Corollary 1.2, then a_{1}b_{1}^{−1} + a_{2}b_{2}^{−1} = a_{1}c_{1}b^{−1} + a_{2}c_{2}b^{−1} = (a_{1}c_{1} + a_{2}c_{2})b^{−1}.

For an element a ∈ A_{m} we denote by ord^{(K)}(a) the filtration degree of a with respect to the symbols \{\frac{∂}{∂X_{j}} \} for j ∉ K and by deg^{(K)}(a) the filtration degree of a with respect to the symbols X_{1}, …, X_{m}, \{\frac{∂}{∂X_{k}} \} for k ∈ K.

Next we verify that (A_{m}^{(K)})^{−1}A_{m} = A_{m}(A_{m}^{(K)})^{−1} relying on the following lemma.

Lemma 1.3 Let a ∈ A_{m}, b ∈ A_{m}^{(K)} be such that deg^{(K)}(a), deg^{(K)}(b) ≤ d, ord^{(K)}(a) = e. Then there exist suitable elements α ∈ A_{m}, β ∈ A_{m}^{(K)} such that bα = aβ (or in other terms αβ^{−1} = b^{−1}a) and moreover, ord^{(K)}(α) ≤ ord^{(K)}(a), deg^{(K)}(α), deg^{(K)}(β) ≤ 2(m + |K|)\binom{e+m−|K|}{e}d.

Proof. Write down α = ∑_{I} D^{I}β_{I} where indeterminates β_{I} ∈ A_{m}^{(K)} and the summation ranges over all the derivatives D^{I} = ∏_{j∉K} D_{j}^{i_{j}} with the orders ∑_{j∉K} i_{j} ≤ e. In a similar manner a = ∑_{I} D^{I}b_{I}. Then the equality bα = aβ turns into a linear system in \binom{e+m−|K|}{e} equations in \binom{e+m−|K|}{e} + 1 indeterminates β, \{β_{I}\}_{I}. Applying to this system Lemma 1.1 we complete the proof.

Lemma 1.3 entails that the product of two elements a_{1}b_{1}^{−1} and a_{2}b_{2}^{−1} from Q_{m}^{(K)} has again the similar form a_{3}b_{3}^{−1}: indeed, let b_{1}^{−1}a_{2} = a_{4}b_{4}^{−1} for appropriate a_{4} ∈ A_{m}, b_{4} ∈ A_{m}^{(K)}, then a_{1}b_{1}^{−1}a_{2}b_{2}^{−1} = a_{1}a_{4}(b_{2}b_{4})^{−1}.

Finally, to complete the description of the algebra Q_{m}^{(K)} we need to verify that the relation αβ^{−1} = b^{−1}a ∈ Q_{m}^{(K)} being defined as bα = aβ, induces an equivalence relation on Q_{m}^{(K)}. To this end it suffices to show that the equalities α_{1}β_{1}^{−1} = b_{1}^{−1}a_{1}, b_{1}^{−1}a_{1} = α_{2}β_{2}^{−1}, α_{2}β_{2}^{−1} = b_{2}^{−1}a_{2} imply the equality α_{1}β_{1}^{−1} = b_{2}^{−1}a_{2}. Due to Corollary 1.2 there exist a_{3}, a_{4} ∈ A_{m} such that a_{3}a_{1} = a_{4}a_{2}, hence a_{4}b_{2}α_{2} = a_{4}a_{2}β_{2} = a_{3}a_{1}β_{2} = a_{3}b_{1}α_{2}, therefore a_{4}b_{2} = a_{3}b_{1}. Because of that a_{4}b_{2}α_{1} = a_{3}b_{1}α_{1} = a_{3}a_{1}β_{1} = a_{4}a_{2}β_{1}, thus b_{2}α_{1} = a_{2}β_{1} that was to be shown.

The following corollary summarizes the established above properties of the algebra Q_{m}^{(K)}.

Corollary 1.4 In the algebra of fractions Q_{m}^{(K)} = A_{m}(A_{m}^{(K)})^{−1} = (A_{m}^{(K)})^{−1}A_{m} two elements a_{1}b_{1}^{−1}, a_{2}b_{2}^{−1} ∈ A_{m}(A_{m}^{(K)})^{−1} are equal if and only if there exists an element β^{−1}α ∈ (A_{m}^{(K)})^{−1}A_{m} such that βa_{1} = αb_{1}, βa_{2} = αb_{2}.

2 Quasi-inverse matrices over algebras of differential operators

Let us call an p × p matrix C = (c_{i,j}) a right (respectively, left) quasi-inverse to an p × p matrix B = (b_{i,j}) where the entries c_{i,j}, b_{i,j} ∈ A_{m}^{(K)} if the matrix BC (respectively, CB) has the diagonal form with non-zero diagonal entries. The following lemma was proved in [7].

Lemma 2.1 If an p × p matrix B over A_{m}^{(K)} has a right quasi-inverse (we assume that deg(B) ≤ d) then B has also a left quasi-inverse C over A_{m}^{(K)} such that deg(C) ≤ 2(m + |K|)(p − 1)d.

Proof. First observe that there does not exist a vector 0 ≠ b ∈ (A_{m}^{(K)})^{p} for which bB = 0 since A_{m}^{(K)} is a domain (see [2] and also Section 1). Consider the p × (p − 1) matrix B^{(i)} obtained from B by deleting its i-th column, 1 ≤ i ≤ p. Due to Lemma 1.1 there exists a vector 0 ≠ c^{(i)} ∈ (A_{m}^{(K)})^{p} such that c^{(i)}B^{(i)} = 0 and deg(c^{(i)}) ≤ 2(m + |K|)(p − 1)d. Then the p × p matrix with the rows c^{(i)}, 1 ≤ i ≤ p is a left quasi-inverse of B.

We note that a matrix G over A_{m} (or over Q_{m}^{(K)}) has a quasi-inverse if and only if G is non-singular, i.e. has an inverse over the skew-field Q_{m}^{({1,...,m})} = A_{m}(A_{m})^{−1}. The latter is equivalent to that G has a non-zero determinant of Dieudonné [1]. The rank r = rk(G) is defined as the maximal size of non-singular submatrices of G. The following lemma was proved in [7].

Lemma 2.2 Let G = (g_{i,j}) be a p_{1} × p_{2} matrix over A_{m}^{(K)} with the rank rk(G) = r and assume that the r × r submatrix G_{1} of G in its left-upper corner is non-singular. Let an r × r matrix C_{1} over A_{m}^{(K)} be a left quasi-inverse to G_{1}. Then one can find an (p_{1} − r) × r matrix C_{2} over the algebra Q_{m}^{(K)} such that

( \begin{matrix}C_{1}0 \\ C_{2}E \end{matrix} ) G = ( \begin{matrix}g_{1} & & 0 \\ & ... & & ∗ \\ 0 & & g_{r} \\ & 0 & & 0 \end{matrix} )

where E denotes the unit matrix.

Proof. The matrix C_{2} is determined uniquely by the requirement that in the product of matrices in the right-hand side the left-lower corner is zero. Then the right-lower corner is zero as well by the definition of the rank.

We proceed to solving system (3). Denote r = rk(a_{j,i}). After renumerating the rows and columns one can suppose the r × r submatrix in the left-upper corner of (a_{j,i}) to be non-singular. Applying Lemma 2.1 to r × r submatrix (a_{j,i}), 1 ≤ i, j ≤ r one gets a matrix C_{1}, subsequently applying Lemma 2.2 one gets a matrix C_{2}. If the vector (C_{2} E)(a_{1}, …, a_{q}) does not vanish then system (3) has no solutions. Otherwise, if (C_{2} E)(a_{1}, …, a_{q}) = 0 then system (3) is equivalent to a linear system over Q_{m}^{(K)} of the following form (see Lemma 2.2):

g_{j}V_{j} + ∑_{r+1≤i≤p} g_{j,i}V_{i} = f_{j}, 1 ≤ j ≤ r  (4)

where g_{j}, g_{j,i}, f_{j} ∈ A_{m}. Lemma 2.1 implies that deg(g_{j}), deg(g_{j,i}), deg(f_{j}) ≤ (4m(r − 1) + 1)d. Fix for the time being a certain i, r + 1 ≤ i ≤ p. Applying Lemma 1.1 to the r × (r + 1) submatrix which consists of the first r columns and of the i-th column of the matrix in the left-hand side of (4), we obtain h_{1}^{(i)}, …, h_{r}^{(i)}, h^{(i)} ∈ A_{m} such that

g_{j}h_{j}^{(i)} + g_{j,i}h^{(i)} = 0, 1 ≤ j ≤ r  (5)

Moreover, deg(h_{j}^{(i)}), deg(h^{(i)}) ≤ 4mr(4m(r − 1) + 1)d ≤ (16m^{2}r^{2} − 1)d.

3 Complexity of solving a linear system over an algebra of fractions of differential operators

In the present section we design an algorithm to solve a linear system (4) over Q_{m}^{(K)}. Fix for the time being a certain γ ∉ K. An arbitrary element h ∈ A_{m} can be written as

h = ∑_{0≤s≤t} D_{γ}^{s}h_{s} = ∑_{S={s_{δ}}_{δ∉K}}( ∏_{δ∉K} D_{δ}^{s_{δ}})h_{S}  (6)

where h_{s} ∈ A_{m}^{({1,...,m}\γ)}, h_{S} ∈ A_{m}^{(K)}. Denote the leading coefficient lc_{γ}(h) = h_{t} ≠ 0. We say that h is normalized with respect to D_{γ} when lc_{γ}(h) ∈ A_{m}^{(K)}. The following lemma plays the role of the normalization for the algebra Q_{m}^{(K)} (cf. Lemma 2.3 [14] or Lemma 4 [7]).

Lemma 3.1 For any finite family H = {h} ⊂ A_{m} there exists a non-singular F -linear transformation of the 2(m−|K|)-dimensional F -linear subspace of A_{m} with the basis \{X_{δ}, \frac{∂}{∂X_{δ}} \}_{δ∉K} under which the vector \{\frac{∂}{∂X_{δ}} \}_{δ∉K} is transformed as follows:

\{\frac{∂}{∂X_{δ}} \}_{δ∉K} → Ω\{\frac{∂}{∂X_{δ}} \}_{δ∉K}

where the (m − |K|) × (m − |K|) matrix Ω = (ω_{δ_{1},δ}), ω_{δ_{1},δ} ∈ F, and the vector

{X_{δ}}_{δ∉K} → (Ω^{T})^{−1}{X_{δ}}_{δ∉K}

such that any transformed (under the transformation continued to A_{m}) element \overline{h} ∈ A_{m} for h ∈ H is normalized with respect to D_{γ}. Moreover, deg_{D_{γ}}(\overline{h}) = ord^{(K)}(\overline{h}).

Proof. One can verify that this linear transformation keeps the relations (1), therefore, one can consider A_{m} as a Weyl algebra with respect to the variables {X_{k}}_{k∈K} ∪ (Ω^{T})^{−1}{X_{δ}}_{δ∉K} and the corresponding differential operators \{\frac{∂}{∂X_{k}} \} ∪ Ω\{\frac{∂}{∂X_{δ}} \}_{δ∉K} (cf. also [7]).

We rewrite (6) as

h = ∑_{S_{0}={s_{δ}}_{δ∉K}}( ∏_{δ∉K} D_{δ}^{s_{δ}})h_{S_{0}} + Σ_{1}

where in the first sum all the terms from (6) with the maximal value of the sum ∑_{s_{δ}∈S_{0}} s_{δ} = ord^{(K)}(h) are gathered. Then the leading coefficient

lc_{γ}(\overline{h}) = ∑_{S_{0}}( ∏_{δ∉K} ω_{γ,δ}^{s_{δ}})\overline{h}_{S_{0}} ∈ A_{m}^{(K)}.

Since the latter sum does not vanish if and only if the result of its linear transformation

∑_{S_{0}}( ∏_{δ∉K} ω_{γ,δ}^{s_{δ}})h_{S_{0}} ∈ A_{m}^{(K)}

with respect to Ω^{T} does not vanish as well, the set of the entries \{ω_{γ,δ}\}_{δ∉K} for which lc_{γ}(\overline{h}) does not vanish, is open in the Zariski topology (and thereby, is non-empty taking into account that the ground field F is infinite). Hence for an open set of the entries {ω_{γ,δ}}_{δ∉K} the leading coefficients lc_{γ}(\overline{h}) do not vanish for all h ∈ H. Therefore, deg_{D_{γ}}(\overline{h}) = ord^{(K)}(h) = ord^{(K)}(\overline{h}) and thereby, \overline{h} is normalized with respect to D_{γ}.

Applying Lemma 3.1 to the family {h^{(i)}}_{r+1≤i≤p} constructed in (5), we can assume without loss of generality that 0 ≠ lc_{D_{γ}}(h^{(i)}) ∈ A_{m}^{(K)}, r + 1 ≤ i ≤ p.

Consider a certain solution v_{i} ∈ Q_{m}^{(K)}, 1 ≤ i ≤ p of system (4). Fix some r + 1 ≤ i ≤ p for the time being. One can divide (from the right) v_{i} by h^{(i)} with the remainder in Q_{m}^{(K)} with respect to D_{γ}, i.e. v_{i} = h^{(i)}ϕ_{i} + ψ_{i} for suitable ϕ_{i}, ψ_{i} ∈ Q_{m}^{(K)} such that deg_{D_{γ}}(ψ_{i}) < deg_{D_{γ}}(h^{(i)}) = t. Let v_{i} = ∑_{0≤s≤t_{1}} D_{γ}^{s}v_{i,s} where v_{i,s} ∈ A_{m}^{({1,...,m}\γ)} and v_{i,t_{1}} = lc_{D_{γ}}(v_{i}). Taking into account that h^{(i)} is normalized with respect to D_{γ}, one can rewrite lc_{D_{γ}}(h^{(i)})D_{γ}^{t_{1}−t} = D_{γ}^{t_{1}−t}lc_{D_{γ}}(h^{(i)}) + ∑_{0≤s≤t_{1}−t−1} D_{γ}^{s}η_{s} for appropriate η_{s} ∈ A_{m}^{(K)}. Thus, one can put the leading term of (the quotient) ϕ_{i} to be ϕ_{i,t_{1}−t} = D_{γ}^{t_{1}−t}(lc_{D_{γ}}(h^{(i)}))^{−1}lc_{D_{γ}}(v_{i}) ∈ Q_{m}^{(K)}. Then deg_{D_{γ}}(v_{i} − h^{(i)}ϕ_{i,t_{1}−t}) < t_{1} and one can continue the process of dividing with the remainder achieving finally ϕ_{i}, ψ_{i}.

For a fixed 1 ≤ j ≤ r we multiply each of the equalities (5) for r +1 ≤ i ≤ p from the right by ϕ_{i} and subtract it from the corresponding equality (4), as a result we get an equivalent to (4) linear system

g_{j}ψ_{j} + ∑_{r+1≤i≤p} g_{j,i}ψ_{i} = f_{j}, 1 ≤ j ≤ r  (7)

for certain ψ_{j} ∈ Q_{m}^{(K)}. Since deg(f_{j}), deg(g_{j,i}) ≤ (4m(r−1)−1)d, deg_{D_{γ}}(ψ_{i}) < deg_{D_{γ}}(h^{(i)}) ≤ (16m^{2}r^{2} − 1)d (see the end of Section 2) we conclude that deg_{D_{γ}}(ψ_{j}) ≤ N_{1} ≤ 16m^{2}r^{2}d, 1 ≤ j ≤ r.

Represent ψ_{j} = ∑_{0≤s≤N_{1}} D_{γ}^{s}ψ_{j,s}, 1 ≤ j ≤ p for appropriate ψ_{j,s} ∈ A_{m}^{({1,...,m}\γ)}(A_{m}^{(K)})^{−1}. For each 0 ≤ s ≤ N_{1} we have

g_{j}D_{γ}^{s} = ∑_{0≤l≤N_{0}} D_{γ}^{l}g_{j,s,l}^{(1)}, g_{j,i}D_{γ}^{s} = ∑_{0≤l≤N_{0}} D_{γ}^{l}g_{j,i,s,l}^{(1)}  (8)

for appropriate g_{j,s,l}^{(1)}, g_{j,i,s,l}^{(1)} ∈ A_{m}^{({1,...,m}\γ)} where N_{0}, deg(g_{j,s,l}^{(1)}), deg(g_{j,i,s,l}^{(1)}) ≤ 16m^{2}r^{2}d. Substituting the expressions (8) in (7) and subsequently equating the coefficients at the same powers of D_{γ}, we obtain the following linear system over A_{m}^{({1,...,m}\γ)}(A_{m}^{(K)})^{−1}:

∑_{j,s} g_{j,s,l}^{(2)}ψ_{j,s} = g_{l}^{(2)}  (9)

being equivalent to system (7) and thereby, to system (3), in other words, these systems are solvable simultaneously. Moreover, g_{j,s,l}^{(2)}, g_{l}^{(2)} ∈ A_{m}^{({1,...,m}\γ)}, deg(g_{j,s,l}^{(2)}), deg(g_{l}^{(2)}) ≤ 16m^{2}r^{2}d, the number of the equations in system (9) does not exceed 16m^{2}r^{2}d and the number of the indeterminates ψ_{j,s} is less than 16pm^{2}r^{2}d.

We summarize the proved above in this section in the following lemma.

Lemma 3.2 A linear system (3) of q equations in p indeterminates with the degrees of the coefficients a_{j,i}, a_{j} at most d is solvable over the algebra Q_{m}(K) if and only if the linear system (9) is solvable over the algebra A_{m}^{({1,...,m}\γ)}(A_{m}^{(K)})^{−1}. System (9) in at most 16pm^{2}r^{2}d indeterminates and in at most 16m^{2}r^{2}d equations has the coefficients from the algebra A_{m}^{({1,...,m}\γ)} of the degrees less than 16m^{2}r^{2}d where r ≤ min{p, q} is the rank of the system (3).

Moreover, if system (9) has a solution with the degrees not exceeding a certain λ then system (3) has a solution with the degrees not exceeding λ + 16m^{2}r^{2}d.

Thus, we have eliminated the symbol D_{γ}. Continuing by recursion applying Lemma 3.2 we eliminate consecutively D_{δ} for all δ ∉ K and finally yield a linear system

∑_{1≤l≤N_{3}} g_{s,l}^{(0)}V_{l}^{(0)} = g_{s}^{(0)}, 1 ≤ s ≤ N_{2}  (10)

over the skew-field A_{m}^{(K)}(A_{m}^{(K)})^{−1} with the coefficients g_{s,l}^{(0)}, g_{s}^{(0)} ∈ A_{m}^{(K)} where

N_{2}, deg(g_{s,l}^{(0)}), deg(g_{s}^{(0)}) ≤ N_{4} = (2m)^{4^{m−|K|}}(dr)^{3^{m−|K|}} and the number of the indeterminates N_{3} ≤ pN_{4}. Notice that system (10) is solvable simultaneously with system (3).

As in Section 2 one can reduce (with the help of Lemma 2.2) system (10) to the diagonaltrapezium form similar to (4) with the coefficients from the algebra A_{m}^{(K)} having the degrees less than 2(m+|K|)N_{4}^{2} due to Lemma 2.1. Therefore, if system (10) has a solution in the skewfield A_{m}^{(K)}(A_{m}^{(K)})^{−1} it should have a solution of the form v_{l}^{(0)} = (b_{l}^{(1)})^{−1}b_{l}^{(2)} ∈ (A_{m}^{(K)})^{−1}A_{m}^{(K)} with the degrees deg(b_{l}^{(1)}), deg(b_{l}^{(2)}) ≤ 2(m+|K|)N_{4}^{2} taking into account the achieved diagonaltrapezium form. Applying Corollary 1.2 to v_{l}^{(0)} one can represent v_{l}^{(0)} = v_{l}^{(3)}(v_{l}^{(4)})^{−1} for suitable v_{l}^{(3)}, v_{l}^{(4)} ∈ A_{m}^{(K)} with the degrees deg(v_{l}^{(3)}), deg(v_{l}^{(4)}) ≤ 4(m+|K|)^{2}N_{4}^{2}, 1 ≤ l ≤ N_{3}. Hence due to Lemma 3.2 it provides a solution of system (3) over the algebra Q_{m}(K) = A_{m}(A_{m}^{(K)})^{−1} with the bounds on the degrees N_{5} = 4(m + |K|)N_{4}^{2}. This completes the proof of Theorem 0.2.

Finally we observe that if system (3) has a solution it has also a solution of the form v_{i} = c_{i}b^{−1} for appropriate c_{i} ∈ A_{m}, b ∈ A_{m}^{(K)} with the degrees deg(c_{i}), deg(b) ≤ (2(m + |K|)p + 1)N_{5}, 1 ≤ i ≤ q due to Corollary 1.2. The algorithm looks for a solution of system (3) just in this form with the indeterminate coefficients over the field F at the monomials in the symbols X_{1}, …, X_{m}, D_{1}, …, D_{m} and treats (3) or equivalently, ∑_{1≤i≤p} a_{j,i}c_{i} = a_{j}b, 1 ≤ j ≤ q as a linear system over F in the indeterminate coefficients searching for a non-zero solution of the latter linear system. This completes the proof of Corollary 0.3.

4 A bound on the leading coefficient of the Hilbert-Kolchin polynomial of a linear differential module

In the sequel we use the notations from the Introduction. If the degree 0 ≤ t ≤ m of the Hilbert-Kolchin polynomial of the left L_{m}-module L equals to m then the leading coefficient l is at most n [8].

From now on assume that t < m. For each 1 ≤ i_{0} ≤ n and any family K = {k_{0}, …, k_{t}} ⊂ {1, …, n} of t + 1 integers there exists an element 0 ≠ (0, …, 0, b_{i_{0}}^{(0)}, 0, …, 0) ∈ L with a single non-zero coordinate at the i_{0}-th place where b_{i_{0}}^{(0)} ∈ A_{m}^{(K)}(F [X_{1}, …, X_{m}])^{−1}, taking into account that the differential type of L equals to t (cf. Proposition 2.4 [14]). Rewriting the latter condition as a system of linear equations

∑_{1≤j≤s} C_{j}w_{i,j} = 0, i ≠ i_{0}, ∑_{1≤j≤s} C_{j}w_{i_{0},j} = 1

in the indeterminates C_{1}, …, C_{s} over the algebra Q_{m}^{(K)} and making use of Theorem 0.2 one can find a solution of this system in the form c_{1} = (b_{i_{0}})^{−1}a_{1,i_{0}}, …, c_{s} = (b_{i_{0}})^{−1}a_{s,i_{0}} ∈ Q_{m}^{(K)} for suitable b_{i_{0}} ∈ A_{m}^{(K)}, a_{1,i_{0}}, …, a_{s,i_{0}} ∈ A_{m} with the degrees deg(b_{i_{0}}), deg(a_{1,i_{0}}), …, deg(a_{s,i_{0}}) ≤ (16m^{4}d^{2}(min{n, s})^{2})^{4^{m−t−1}}. Thus, 0 ≠ (0, …, 0, b_{i_{0}}, 0, …, 0) ∈ L.

Applying Lemma 3.1 to the family {b_{i_{0}}}_{1≤i_{0}≤n} we conclude that after an appropriate F - linear transformation Ω of the subspace with the basis D_{k_{0}}, …, D_{k_{t}} and the corresponding transformation (Ω^{T})^{−1} of the subspace with the basis X_{k_{0}}, …, X_{k_{t}}, one can suppose that b_{i_{0}} = α_{e}D_{k_{0}}^{e} +β_{e−1}D_{k_{0}}^{e−1} +⋯+β_{0} is normalized with respect to D_{k_{0}} where 0 ≠ α_{e} ∈ F [X_{1}, …, X_{m}] and β_{e−1}, …, β_{0} ∈ A_{m}^{(K\{k_{0}})}. The Hilbert-Kolchin polynomial does not change under the F - linear transformation Ω. Taking into account that these transformations keep the relations (1) of the Weyl algebra (see the proof of Lemma 3.1), in the applications of these transformations below we may preserve the same notations for the basis of the resulting Weyl algebra after transformations.

First we apply the described above construction to the family K = {1, …, t+1} and obtain normalized elements (0, …, 0, b_{i_{0}}^{(1)}, 0, …, 0) ∈ L, 1 ≤ i_{0} ≤ n with respect to D_{1}. Thereupon consecutively we take K = {2, …, t + 2}, …, K = {m − t, …, m} and obtain elements (0, …, 0, b_{i_{0}}^{(2)}, 0, …, 0), …, (0, …, 0, b_{i_{0}}^{(m−t)}, 0, …, 0) ∈ L, 1 ≤ i_{0} ≤ n being normalized with respect to D_{2}, …, D_{m−t}, correspondingly.

Hence any element in the quotient F (X_{1}, …, X_{m})-vector space L_{m}^{n} over the left L_{m}- module L can be reduced to the form (∑_{I} h_{1,I}D_{1}^{i_{1}} ⋯ D_{m}^{i_{m}}, …, ∑_{I} h_{n,I}D_{1}^{i_{1}} ⋯ D_{m}^{i_{m}}) where the coefficients h_{j,I} ∈ F (X_{1}, …, X_{m}) and i_{1}, …, i_{m−t} ≤ (16m^{4}d^{2}(min{n, s})^{2})^{4^{m−t−1}}. This completes the proof of Corollary 0.1.

Acknowledgements. The paper was done partially under the support of the Humboldts Forschungspreis. The author is grateful to Michel Granger, Fritz Schwarz, Serguey Tsarev for their attention and to SCAI (Fraunhofer Institut) for the hospitality during the stay there.

References

[1] E. Artin, Geometric algebra, Interscience Publishers, 1957.

[2] J.-E. Björk, Rings of differential operators, North-Holland, 1979.

[3] J. Briançon, P. Maisonobe, Idéaux de germes d’opérateurs différentiels à une variable, Enseign. Math., 30, 2 (1984), 7–38.

[4] F. Castro, Théorème de division pour les opérateurs différentiels et calcul des multiplicités, Thèse de 3ème cycle, l’Université Paris-7, 1984.

[5] A. Galligo, Some algorithmical questions on ideals of differential operators, Lect.Notes Comput.Sci., 204 (1985), 413–421.

[6] D. Grigoriev, Computational complexity in polynomial algebra, in Proc.Intern.Congress Mathem., Berkeley (1986), 1452–1460.

[7] D. Grigoriev, Complexity of solving systems of linear equations over the rings of differential operators, Progress in Math., Birkhauser, 94 (1991), 195–202.

[8] E. Kolchin, Differential algebra and algebraic groups, Academic Press, 1973.

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

[10] E. Mayr, A. Meyer, The complexity of the word problems for commutative semigroups and polynomial ideals, Adv.Math., 46 (1982), 305–329.

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

[12] A. Seidenberg, Constructions in algebra, Trans.Amer.Math.Soc. 97 (1974), 273–313.

[13] I. Shafarevich, Basic algebraic geometry, Springer, 1974.

[14] W.Yu. Sit, Typical differential dimension of the intersection of linear differential algebraic groups, J.Algebra 32 (1974), 476–487.