Complexity of Janet basis of a D-module
Alexander Chistov
Steklov Institute of Mathematics,
Fontanka 27, St. Petersburg 191023, Russia
alch@pdmi.ras.ru
Dima Grigoriev
CNRS, IRMAR, Université de Rennes
Beaulieu, 35042, Rennes, France
dmitry.grigoryev@univ-rennes1.fr
http://perso.univ-rennes1.fr/dmitry.grigoryev
Abstract
We prove a double-exponential upper bound on the degree and on the
complexity of constructing a Janet basis of a D-module. This generalizes
a well known bound on the complexity of a Gröbner basis of a module
over the algebra of polynomials. We would like to emphasize that the
obtained bound can not be immediately deduced from the commutative
case.
Introduction
Let A be the Weyl algebra F [X1, . . . , Xn,
, . . . , ∂
] (or the algebra of
differential operators F (X1, . . . , Xn)[
, . . . , ∂
]). Denote for brevity Di =
, 1 ≤ i ≤ n. Any A–module is called D–module. It is well known that
an A–module which is a submodule of a free finitely generated A-module has a
Janet basis. Historically, it was first introduced in [9]. In more recent times of
developing computer algebra Janet bases were studied in [5], [13], [10]. Janet
bases generalize Gröbner bases which were widely elaborated in the algebra of
polynomials (see e. g.[3]). For Gröbner bases a double-exponential complexity
bound was obtained in [12], [6] relying on [1] and which was made more precise
(with a self–contained proof) in [4].
Surprisingly, no complexity bound on Janet bases was established so far; in
the present paper we fill this gap and prove a double-exponential complexity
bound. On the other hand, a double-exponential complexity lower bound on
Gröbner bases [12], [14] provides by the same token a bound on Janet bases.
There is a folklore opinion that the problem of constructing a Janet basis
is easily reduced to the commutative case by considering the associated graded
module, and, on the other hand, in the commutative case [6], [12], [4] the double–
exponential upper bound is well known. But it turns out to be a fallacy! From
a known system of generators of a D-module one can not obtain immediately
any system of generators (even not necessarily a Gröbner basis) of the associ-
ated graded module. The main problem here is to construct such a system of
generators of the graded module. It may have the elements of degrees (dl)2
http://arxiv.org/abs/0704.1257v1
http://perso.univ-rennes1.fr/dmitry.grigoryev
see the notation below. Then, indeed, to the last system of generators of big
degrees one can apply the result known in the commutative case and get the
bound ((dl)2
= (dl)2
. So new ideas specific to non–commutative
case are needed.
We are interested in the estimations for Janet bases of A-submodules of Al.
The Janet basis depends on the choice of the linear order on the monomials (we
define them also for l > 1). In this paper we consider the most general linear
orders on the monomials from Al. They satisfy conditions (a) and (b) from
Section 1 and are called admissible. We prove the following result.
THEOREM 1 For any admissible linear order on the monomials from Al any
A-submodule I of Al generated by elements of degrees at most d (with respect
to the filtration in the corresponding algebra, see Section 1 and Section 9) has
a Janet basis with the degrees and the number of its elements less than
(dl)2
We prove in detail this theorem for the case of the Weyl algebra A. The proof
for the case of the algebra of differential operators is similar. It is sketched
in Section 9. ¿From Theorem 1 we get that the Hilbert function H(I,m), see
Section 1, of the A-submodule from this theorem is stable for m ≥ (dl)2
and the absolute values of all coefficients of the Hilbert polynomial of I are
bounded from above by (dl)2
, cf. e.g., [12]. This fact follows directly from
(10), Lemma 12 from Appendix 1, Lemma 2 and Theorem 2. We mention that
in [7] the similar bound was shown on the leading coefficient of the Hilbert
polynomial.
Now we outline the plan for the proof of Theorem 1. The main tool in the
proof is a homogenized Weyl algebra hA (or respectively, a homogenized alge-
bra of differential operators hB). It is introduced in Section 3 (respectively,
Section 9). The algebra hA (respectively hB) is generated over the ground
field F by X0, . . . , Xn, D1, . . . , Dn (respectively over the field F (X1, . . . , Xn)
by X0, D1, . . . , Dn). Here X0 is a new homogenizing variable. In the algebra
(respectively hB) relations (12) Section 3 (respectively (50) Section 9) hold for
these generators in hA.
We define the homogenization hI of the module I. It is a hA–submodule of
hAl. The main problem is to estimate the degrees of a system of generators of hI.
These estimations are central in the paper. They are deduced from Theorem 2
Section 7. This theorem is devoted to the problem of solving systems of linear
equations over the ring hA; we discuss it below in more detail.
The system of generators of hI gives a system of generators of the graded
gr(A)–module gr(I) corresponding to I. But gr(A) is a polynomial ring. Hence
using Lemma 12 Appendix 1 we get a double–exponential bound (dl)2
the stabilization of the Hilbert function of gr(I) and the absolute values of the
coefficients of the Hilbert polynomial of gr(I). Therefore, the similar bound
holds for the stabilization of the Hilbert functions of I and the coefficients of
the Hilbert polynomial of I, see Section 2.
But the Hilbert functions of the modules I and hI coincide, see Section 3.
Hence the last bound holds also for the stabilization of the Hilbert functions of
hI and the coefficients of the Hilbert polynomial of hI. In Section 5 we introduce
the linear order on the monomials from hAl induced by the initial linear order
on the monomials from Al (the homogenizing variable X0 is the least possible
in this ordering). Further, we define the Janet basis of hI with respect to the
induced linear order on the monomials. Such a basis can be obtained by the
homogenization of the elements of a Janet basis of I with respect to the initial
linear order, see Lemma 3.
Let Hdt(hI) be the monomial module (i.e., the module which has a system
of generators consisting of monomials) generated by the greatest monomials of
all the elements of the module hI, see Section 4. Let cI, see Section 4, be the
module over the polynomial ring cA = F [X0, . . . , Xn, D1, . . . , Dn] generated by
all the monomials from Hdt(hI) (they are considered now as elements of cA).
Then the Hilbert functions of the modules hI and cI coincide. Thus, we have the
same as above double–exponential estimation for the stabilization of the Hilbert
functions of cI and the coefficients of the Hilbert polynomial of cI. Now using
Lemma 13 we get the estimation (dl)2
on the monomial system of generators
of cI, hence also of Hdt(hI). This gives the bound for the degrees of the elements
of the Janet bases of hI and hence also for the required Janet basis of I, and
proves Theorem 1.
The problem of solving systems of linear equations over the homogenized
algebra is central in this paper, see Theorem 2. It is studied in Sections 5–
7. A similar problem over the Weyl algebra (without a homogenization) was
considered in [7]. The principal idea is to try to extend the well known method
due to G.Hermann [8] which was elaborated for the algebra of polynomials, to
the homogenized Weyl algebra. There are two principal difficulties on this way.
The first one is that in the method of G.Hermann the use of determinants is
essential which one has to avoid dealing with non-commutative algebras. The
second is that one needs a kind of the Noether normalization theorem in the
situation under consideration. So it is necessary to choose the leading elements
in the analog of the G.Hermann method with the least ordX0 , where X0 is a
homogenizing variable, see Section 3.
The obtained bound on the degree of a Janet basis implies a similar bound on
the complexity of its constructing. Indeed, by Corollary 1 (it is formulated for
the case of Weyl algebra but the analogous corollary holds for the case of algebra
of differential operators) one can compute the linear space of all the elements
z ∈ I of degrees bounded from above by (dl)2
. Further, by Theorem 1 the
module Hdt(I), see Section 1, is generated by all the elements Hdt(z) with z ∈ I
of degrees bounded from above by (dl)2
. Hence one can compute a system
of generators of Hdt(I) and a Janet basis of I solving linear systems over F of
size bounded from above (dl)2
(just by the enumeration of all monomials
of degrees at most (dl)2
which are possible generators of Hdt(I)). If one
needs to construct the reduced Janet basis it is sufficient to apply additionally
Remark 1 Section 4.
For the sake of self–containedness in Appendix 1, see Lemma 12, we give a
short proof of the double–exponential estimation for stabilization of the Hilbert
function of a graded module over a homogeneous polynomial ring. A conversion
of Lemma 12 also holds, see Appendix 1 Lemma 13. It is essential for us.
The proof of Lemma 13 uses the classic description of the Hilbert function of
a homogeneous ideal in F [X0, . . . , Xn] via Macaulay constants bn+2, . . . , b1 and
the constant b0 introduced in [4]. In Appendix 2 we give an independent and
instructive proof of Proposition 1 which is similar to Lemma 13. In some sence
Proposition 1 is even more strong than Lemma 13 since to apply it one does
not need a bound for the stabilization of the Hilbert function. Of course, the
reference to Proposition 1 can be used in place of Lemma 13 in our paper.
1 Definition of the Janet basis
Let A = F [X1, . . . , Xn, D1, . . . , Dn], n ≥ 1, be a Weyl algebra over a field F of
zero–characteristic. So A is defined by the following relations
XvXw = XwXv, DvDw = DwDv, DvXv−XvDv = 1, XvDw = DwXv, v 6= w.
By (1) any element f ∈ A can be uniquely represented in the form
i1,...,in,j1,...,jn≥0
fi1,...,in,j1,...,jnX
1 . . .X
1 . . . D
n , (2)
where all fi1,...,in,j1,...,jn ∈ F and only a finite number of fi1,...,in,j1,...,jn are
nonzero. Denote for brevity Z+ = {z ∈ Z : z ≥ 0} to the set of all nonnegative
integers and
i = (i1, . . . , in), j = (j1, . . . , jn), fi,j = fi1,...,in,j1,...,jn
X i = X i11 . . . X
n , D
j = D
1 . . . D
n , f =
fi,jX
iDj ,
|i| = i1 + . . .+ in, i+ j = (i1 + j1, . . . , in + jn).
So i, j ∈ Zn+ are multiindices. By definition the degree of f
deg f = degX1,...,Xn,D1,...,Dn f = max{|i|+ |j| : fi,j 6= 0}.
LetM be a left A-module given by its generatorsm1, . . . ,ml, l ≥ 0, and relations
1≤w≤l
av,wmw, 1 ≤ v ≤ k. (4)
where k ≥ 0 and all av,w ∈ A. We assume that deg av,w ≤ d for all v, w. By (4)
we have the exact sequence
→ M → 0 (5)
of left A-modules. Denote I = ι(Ak) ⊂ Al. If l = 1 then I is a left ideal of A
and M = A/I. In the general case I is generated by the elements
(av,1, . . . , av,l) ∈ A
l, 1 ≤ v ≤ k.
For an integer m ≥ 0 put
Am = {a : deg a ≤ m}, Mm = π(A
m), Im = I ∩ A
m. (6)
So now A, M , I are filtered modules with filtrations Am, Mm, Im, m ≥ 0,
respectively and the sequence of homomorphisms of vector spaces
0 → Im → A
m → Mm → 0
induced by (5) is exact for every m ≥ 0. The Hilbert function H(M,m) of the
module M is defined by the equality
H(M,m) = dimF Mm, m ≥ 0.
Each element ofAl can be uniquely represented as an F -linear combination of
elements ev,i,j = (0, . . . , 0, X
iDj , 0, . . . , 0), herewith i, j ∈ Zn+ are multiindices,
see (3), and the nonzero monomial X iDj is at the position v, 1 ≤ v ≤ l. So
every element f ∈ Al can be represented in the form
v,i,j
fv,i,jev,i,j , fv,i,j ∈ F. (7)
The elements ev,i,j will be called monomials.
Consider a linear order < on the set of all the monomials ev,i,j or which is
the same on the set of triples (v, i, j), 1 ≤ v ≤ l, i, j ∈ Zn+. If f 6= 0 put
o(f) = max{(v, i, j) : fv,i,j 6= 0}, (8)
see (7). Set
o(0) = −∞ < o(f)
for every 0 6= f ∈ A. Let us define the leading monomial of the element
0 6= f ∈ Al by the formula
Hdt(f) = fv,i,jev,i,j ,
where o(f) = (v, i, j). Put Hdt(0) = 0. Hence o(f−Hdt(f)) < o(f) if f 6= 0. For
f1, f2 ∈ A
l if o(f1) < o(f2) we shall write f1 < f2. We shall require additionally
(a) for all multiindices i, j, i′, j′ for all 1 ≤ v ≤ l if i1 ≤ i
1, . . . , in ≤ i
n and
j1 ≤ j
1, . . . , jn ≤ j
n then (v, i, j) ≤ (v, i
′, j′).
(b) for all multiindices i, j, i′, j′, i′′, j′′ for all 1 ≤ v, v′ ≤ l if (v, i, j) < (v′, i′, j′)
then (v, i+ i′′, j + j′′) < (v′, i′ + i′′, j′ + j′′).
Conditions (a) and (b) imply that for all f1, f2 ∈ A
l for every nonzero a ∈ A
if f1 < f2 then af1 < af2, i.e., the considered linear order is compatible with
the products. Any linear order on monomials ev,i,j satisfying (a) and (b) will
be called admissible.
Hdt(I) =
AHdt(f).
So Hdt(I) is an ideal of A. By definition the family f1, . . . , fm of elements of I
is a Janet basis of the module I if and only if
1) Hdt(I) = AHdt(f1)+ . . .+AHdt(fm), i.e., the submodule of A
l generated
by Hdt(f1), . . . ,Hdt(fm) coincides with Hdt(I).
Further, the Janet basis f1, . . . , fm of I is reduced if and only if the following
conditions hold.
2) f1, . . . , fm does not contain a smaller Janet basis of I,
3) Hdt(f1) > . . . > Hdt(fm).
4) the coefficient from F of every monomial Hdt(fv), 1 ≤ v ≤ l, is 1.
5) Let fα =
v,i,j
fα,v,i,jev,i,j be representation (2) for fα, 1 ≤ α ≤ m.
Then for all 1 ≤ α < β ≤ m for all 1 ≤ v ≤ l and multiindices i, j the
monomial fα,v,i,jev,i,j 6∈ Hdt(Afβ \ {0}).
Since the ringA is Noetherian for considered I there exists a Janet basis. Further
the reduced Janet basis of I is uniquely defined.
2 The graded module corresponding to a D–mo-
Put Av = Iv = Mv = 0 for v < 0 and
gr(A) = ⊕m≥0Am/Am−1, gr(I) = ⊕m≥0Im/Im−1, gr(M) = ⊕m≥0Mm/Mm−1.
The structure of the algebra on A induces the structure of a graded algeb-
ra on gr(A). So we have gr(A) = F [X1, . . . , Xn, D1, . . . , Dn] is an algebra of
polynomials with respect to the variables X1, . . . , Xn, D1, . . . , Dn. Further,
gr(I) and gr(M) are graded gr(A)-modules. From (6) we get the exact sequences
0 → Im/Im−1 → (Am/Am−1)
l → Mm/Mm−1 → 0, m ≥ 0. (9)
The Hilbert function of the module gr(M) is defined as follows
H(gr(M),m) = dimF Mm/Mm−1, m ≥ 0.
Obviously
H(M,m) =
0≤v≤m
H(gr(M), v), H(gr(M),m) = H(M,m)−H(M,m− 1).
for every m ≥ 0.
Denote for an arbitrary a ∈ M by gr(a) ∈ gr(M) the image of a in gr(M).
LEMMA 1 Assume that b1, . . . , bs is a system of generators of I. Let νi =
deg bi, 1 ≤ i ≤ s. Suppose that for every m ≥ 0
1≤v≤µ
cvbv : cv ∈ A, deg cv ≤ m− νv, 1 ≤ i ≤ s
. (11)
Then gr(b1), . . . , gr(bs) is a system of generators of the gr(A)-module gr(I).
PROOF This is straightforward.
So it is sufficient to construct a system of generators b1, . . . , bs of I satisfying
(11).
3 Homogenization of the Weyl algebra
Let X0 be a new variable. Consider the algebra
hA = F [X0, X1, . . . , Xn, D1,
. . . , Dn] given by the relations
XvXw = XwXv, DvDw = DwDv, for all v, w,
DvXv −XvDv = X
0 , 1 ≤ v ≤ n, XvDw = DwXv for all v 6= w.
The algebra hA is Noetherian similarly to the Weyl algebra A. By (12) an
element f ∈ hA can be uniquely represented in the form
i0,i1,...,in,j1,...,jn≥0
fi0,...,in,j1,...,jnX
0 . . . X
1 . . .D
n , (13)
where all fi0,...,in,j1,...,jn ∈ F and only a finite number of fi0,...,in,j1,...,jn are
nonzero. Let i, j be multiindices, see (3). Denote for brevity
i = (i1, . . . , in), j = (j1, . . . , jn), fi0,i,j = fi0,...,in,j1,...,jn
i0,i,j
fi0,i,jX
iDj .
By definition the degrees of f
deg f = degX0,...,Xn,D1,...,Dn f = max{i0 + |i|+ |j| : fi0,i,j 6= 0},
degD1,...,Dn f = max{|j| : fi0,i,j 6= 0},
degDα f = max{jα : fi0,i,j 6= 0}, 1 ≤ α ≤ n
degXα f = max{iα : fi0,i,j 6= 0}, 1 ≤ α ≤ n
Set ord 0 = ordX0 0 = +∞. If 0 6= f ∈
hA then put
ord f = ordX0 f = µ if and only if f ∈ X
hA) \X
hA), µ ≥ 0. (15)
For every z = (z1, . . . , zl) ∈
hAl put
ord z = min
1≤i≤l
{ord zi}, deg z = max
1≤i≤l
{deg zi}.
Similarly one defines ord b and deg b for an arbitrary (k × l)–matrix b with
coefficients from hA. More precisely, one consider here b as a vector with kl
entries.
The element f ∈ hA is homogeneous if and only if fi0,i,j 6= 0 implies i0+ |i|+
|j| = deg f , i.e., if and only if f is a sum of monomials of the same degree deg f .
The homogeneous degree of a nonzero homogeneous element f is its degree.
The homogeneous degree of 0 is not defined (0 belongs to all the homogeneous
components of hA, see below).
The m-th homogeneous component of hA is the F -linear space
(hA)m =
z ∈ hA : z is homogeneous & deg z = m or z = 0
for every integer m. Now hA is a graded ring with respect to the homogeneous
degree. By definition the ring hA is a homogenization of the Weyl algebra A.
We shall consider the category of finitely generated graded modules G over
the ring hA. Such a module G = ⊕m≥m0Gm is a direct sum of its homogeneous
components Gm, where m,m0. are integers. Every Gm is a finite dimensional
F -linear space and (hA)pGm ⊂ Gp+m for all integers p,m. If G and G
′ are
two finitely generated graded hA-modules then ϕ : G → G′ is a morphism (of
degree 0) of the graded modules if and only if ϕ is a morphism of hA-modules
and ϕ(Gm) ⊂ G
m for every integer m.
The element z ∈ hA (respectively z ∈ A) is called to be the term if and
only if z = λz1 · . . . · zν for some 0 6= λ ∈ F , integer ν ≥ 0 and zw ∈
{X0, . . . , Xn, D1, . . . , Dn} (respectively zw ∈ {X1, . . . , Xn, D1, . . . , Dn}), 1 ≤
w ≤ ν.
Let z =
zj ∈ A be an arbitrary element of the Weyl algebraA represented
as a sum of terms zj and deg z = maxj deg zj. One can take here, for example,
representation (3) for z. Then we define the homogenization hz ∈ hA by the
formula
deg z−deg zj
By (1), (12) the right part of the last equality does not depend on the chosen
representation of z as a sum of terms. Hence hz is defined correctly. If z ∈ hA
then az ∈ A is obtained by substituting X0 = 1 in z. Hence for every z ∈ A we
have ahz = z, and for every z ∈ hA the element z = hazX
0 , where µ = ord z.
For an element z = (z1, . . . , zl) ∈ A
l put deg z = max1≤i≤l{deg zi} and
deg z−deg z1
0 , . . . ,
deg z−deg zl
∈ hAl.
Similarly one defines deg a and the homogenization ha = (av,w)1≤v≤k, 1≤w≤l for
an arbitrary k×l–matrix a with coefficients from A. More precisely, one consider
here a as a vector with kl entries. Hence if b = (bv,w)1≤v≤k, 1≤w≤l =
ha then
bv,w =
hav,wX
deg a−deg av,w
0 for all v, w.
The m-th homogeneous component of hAl is
(hAl)m =
hz : z ∈ Al & deg z = m or z = 0
For an F -linear subspace X ⊂ Al put hX to be the least linear subspace of hAl
containing the set {hz : z ∈ X}. If X is a (finitely generated) A-submodule of
Al then hX is a (finitely generated) graded submodule of hAl. The graduation
on hX is induced by the one of hAl.
For an element z = (z1, . . . , zl) ∈
hAl put az = (az1, . . . ,
azl) ∈ A
l. For a
subset X ⊂ hAl put aX = {az : z ∈ X} ⊂ Al. If X is a F -linear space then aX
is also a F -linear space. If X is a finitely generated graded submodule of hAl
then aX is finitely generated submodule of Al.
Now hI is a graded submodule of hAl. Further, ahI = I. Let (hI)m be the
m-th homogeneous component of hI. Then
h(Im) = ⊕0≤j≤m(
hI)j , m ≥ 0, (16)
a((hI)m) = Im, m ≥ 0. (17)
and (17) induces the isomorphism ι : (hI)m → Im. Set
hM = hAl/hI. Hence
hM is a graded hA-module and we have the exact sequence
0 → hI → hAl → hM → 0. (18)
The m-th homogeneous component (hM)m of
(hM)m = (
hAl)m/(
hI)m ≃ A
m/Im. (19)
by the isomorphism ι. We have the exact sequences
0 → (hI)m → (
hAl)m → (
hM)m → 0, m ≥ 0. (20)
By definition the Hilbert function of the module hM is
H(hM,m) = dimF (
hM)m, m ≥ 0.
By (19) we have H(M,m) = H(hM,m) for every m ≥ 0, i.e., the Hilbert
functions of M and hM coincide.
LEMMA 2 Let b1, . . . , bs be a system of homogeneous generators of the
module hI. Then
gr(ab1), . . . , gr(
abs) ∈ gr(A)
is a system of generators of gr(A)-module gr(I).
PROOF By (17) a((hI)m) = Im. Now the required assertion follows from
Lemma 1. The lemma is proved.
4 The Janet bases of a module and of its ho-
mogenization
Each element of hAl can be uniquely represented as an F -linear combination of
elements ev,i0,i,j = (0, . . . , 0, X
iDj , 0, . . . , 0), herewith 0 ≤ i0 ∈ Z, i, j ∈ Z
are multiindices, see (3), and the nonzero monomial X i00 X
iDj is at the position
v, 1 ≤ v ≤ l. So every element f ∈ hAl can be represented in the form
v,i0,i,j
fv,i0,i,jev,i0,i,j , fv,i0,i,j ∈ F. (21)
and only a finite number of fv,i0,i,j are nonzero. The elements ev,i0,i,j will be
called monomials.
Let us replace everywhere in Section 1 after the definition of the Hilbert
function the ring A, the monomials ev,i,j , the multiindices i, i
′, i′′, triples
(v, i, j), (v, i′, j′), the module I and so on by the ring hA, monomials ev,i0,i,j ,
the pairs (i0, i), (i
′), (i′′0 , i
′′) (they are used without parentheses), quadruples
(v, i0, i, j), (v, i
′, j′), the homogenization hI and so on respectively. Thus, we
get the definitions of o(f), Hdt(f) for f ∈ hAl, new conditions (a) and (b) which
define admissible linear order on the monomials of hAl, new conditions 1)–5),
the definitions of the Janet basis and reduced Janet basis of hI. For example,
the new conditions (a) and (b) are
(a) for all indices i0, i
0, all multiindices i, j, i
′, j′ for all 1 ≤ v ≤ l if i0 ≤ i
i1 ≤ i
1, . . . , in ≤ i
n and j1 ≤ j
1, . . . , jn ≤ j
n then (v, i0, i, j) ≤ (v, i
′, j′).
(b) for all indices i0, i
0 , all multiindices i, j, i
′, j′, i′′, j′′ for all 1 ≤ v, v′ ≤ l
if (v, i0, i, j) < (v
′, i′0, i
′, j′) then (v, i0+ i
0 , i+ i
′′, j+ j′′) < (v′, i′0+ i
0 , i
i′′, j′ + j′′).
The Janet basis of hI is homogeneous if and only if it consists of homogeneous
elements from hAl.
Let< be an admissible linear order on the monomials fromAl, or which is the
same, on the triples (v, i, j), see Section 1. So < satisfies conditions (a) and (b).
Let us define the linear order on the monomials ev,i0,i,j or, which is the same,
on the quadruples (v, i0, i, j). This linear order is induced by < on the triples
(v, i, j) and will be denoted again by <. Namely, for two quadruples (v, i0, i, j)
and (v′, i′0, i
′, j′) put (v, i0, i, j) < (v
′, i′0, i
′, j′) if and only if (v, i, j) < (v′, i′, j′),
or (v, i, j) = (v′, i′, j′) but i0 < i
0. Notice that this induced linear order satisfies
conditions (a) and (b) (in the new sense).
REMARK 1 If f1, . . . , fm is a Janet basis of I (respectively homogeneous
Janet basis of hI) satisfying 1)–4) then there are the unique cα,β ∈ A (respec-
tively cα,β ∈
hA), 1 ≤ α < β ≤ m, such that
α<β≤m
cα,βfβ , 1 ≤ α ≤ m,
is a reduced Janet basis of I (respectively reduced homogeneous Janet basis of
hI), cf. [3].
LEMMA 3 Let f1, . . . , fm be a (reduced) Janet basis of I with respect to the
linear order <. Then hf1, . . . ,
hfm is a (reduced) homogeneous Janet basis of the
module hI with respect to the induced linear order <. Conversely, let g1, . . . , gm
be a (reduced) homogeneous Janet basis of the module hI with respect to the
induced linear order <. Then ag1, . . . ,
agm is a (reduced) Janet basis of I with
respect to the linear order <.
PROOF This follows immediately from the definitions.
Let f ∈ hAl and the module hI be as above. Then there is the unique element
g ∈ hAl such that
v,i0,i,j
gv,i0,i,jev,i0,i,j , gv,i0,i,j ∈ F,
f −g ∈ hI and if gv,i0,i,j 6= 0 then ev,i0,i,j 6∈ Hdt(
hI). The element g is called the
normal form of f with respect to the module hI. We shall denote g = nf(hI, f).
Obviously nf(hI, (hAl)m) ⊂ (
hAl)m is a linear subspace.
Let cA = F [X0, . . . , Xn, D1, . . . , Dn] be the polynomial ring in the variables
X0, . . . , Xn, D1, . . . , Dn. Each monomial ev,i0,i,j can be considered also as an
element of cAl. Denote by cI ⊂ cAl the graded submodule of cAl generated by
all the monomials ev,i0,i,j such that there is 0 6= f ∈
hI with o(f) = (v, i0, i, j).
The Hilbert functions
H(cI,m) = dimF {(z1, . . . , zl) ∈
cI : ∀ i ( deg zi = m or zi = 0 )},
H(cAl/cI,m) =
m+ 2n
−H(cI,m).
Let us replace in the definition of the normal form above hA, hI by cA, cI respec-
tively. Thus, for f ∈ cAl we get the definition of the normal form nf(cI, f) ∈ cAl,
cf. [4]. Obviously, nf(cI, (cAl)m) ⊂ (
cAl)m is a linear subspace. Since the ideals
and Hdt(hI) are generated by the same monomials we have dimnf(cI, (cAl)m) =
dimnf(hI, (hAl)m). Hence the Hilbert functions
H(hAl/hI,m) = H(cAl/cI,m), H(hI,m) = H(cI,m), m ≥ 0,
coincide. Therefore, see Section 3,
H(I,m) = H(cI,m), m ≥ 0 (22)
5 Bound on the kernel of a matrix over the ho-
mogenized Weyl algebra
LEMMA 4 Let k = l− 1 and l ≥ 1 be integers. Let b = (bi,j)1≤i≤k, 1≤j≤l be a
matrix where bi,j ∈
hA are homogeneous elements for all i, j. Let deg bi,j < d,
d ≥ 1, for all i, j. Assume that there are integers dj ≥ 0, 1 ≤ i ≤ k, and d
i ≥ 0,
1 ≤ j ≤ l, such that
deg bi,j = di − d
j (23)
for all nonzero bi,j, and additionally min1≤j≤l{d
j} = 0 (hence di < d, d
j < d
for all i, j), d ≥ 1. Then there are homogeneous elements z1, . . . , zl ∈
hA such
that (z1, . . . , zl) 6= (0, . . . , 0),
1≤j≤l
bi,jzj = 0, 1 ≤ i ≤ l − 1, (24)
all nonzero bi,jzj have the same degree depending only on i and
deg zj ≤ (2n+ 3)ld, 1 ≤ j ≤ l. (25)
Besides that, if all bi,j do not depend on Xn (i.e., they can be represented as
sums of monomials which do not contain Xn) then one can choose also z1, . . . , zl
satisfying additionally the same property. Finally, dividing by an appropriate
power of X0 one can assume without loss of generality that min{ord zi : 1 ≤
i ≤ l} = 0.
PROOF We shall assume without loss of generality that l ≥ 2. At first
suppose that that deg bi,j = deg b for all nonzero bi,j . Consider the linear
mapping
(hA)lm−deg b −→ (
hA)l−1m ,
( z1, . . . , zl ) 7→
1≤j≤l bi,jzj
1≤i≤l−1
m− deg b+ 2n
> (l − 1)
m+ 2n
then the kernel of (26) is nonzero. But (27) holds if
deg b
m+ 2n− deg b
deg b
m+ 2n− 1− deg b
. . .
deg b
m− deg b
l − 1
Further, (28) is true if (1+ deg b/(m− deg b))2n < l/(l− 1). The last inequality
follows from m ≥ (2n + 1) deg b/ log(l/(l − 1)). Hence also from m ≥ (2n +
1)l deg b. Notice that (2n + 2)ld ≥ 1 + (2n + 1)l deg b. Thus, the existence of
z1, . . . , zl is proved, and even more all nonzero bi,jzj have the same degree which
does not depend on i, j. Notice that in the considered case we prove a more
strong inequality deg zj ≤ (2n+ 2)ld for all 1 ≤ j ≤ l.
Suppose that a1, . . . , al do not depend on Xn. We represent zi =
zi,jX
1 ≤ i ≤ l, where all zi,j do not on Xn. Let α = maxi{degXn zi}. Obviously in
this case one can replace (z1, . . . , zl) by (z1,α, . . . , zl,α).
Let us return to general case of arbitrary deg bi,j . We shall reduce it to
the considered one. Namely, multiplying the i-th equation of system (24) to
maxi{di}−di
0 we shall suppose without loss of generality that all di are equal.
Let us substitute zjX
0 for zj in (24). Now the degrees of all the nonzero
coefficients of the obtained system coincide. Thus, we get the required reduction
and estimation (25). The lemma is proved.
REMARK 2 Lemma 4 remains true if one replaces in its statement condition
(24) by ∑
1≤j≤l
zjbi,j = 0, 1 ≤ i ≤ l − 1, (29)
The proof is similar.
REMARK 3 Let the elements bi,j be from Lemma 4. Notice that there are
integers δ′i ≥ 0, 1 ≤ i ≤ k, and δj ≥ 0, 1 ≤ j ≤ l, such that
deg bi,j = δj − δ
for all nonzero bi,j, and min1≤i≤k{δ
i} = 0. Namely, δ
i = −di +max1≤i≤k{di},
δj = −d
j +max1≤i≤k{di}.
6 Transforming a matrix with coefficients from
A to the trapezoidal form
Let b be the matrix from Lemma 4 but now k, l are arbitrary. Hence (23)
holds. Let b = (b1, . . . , bl) where b1, . . . , bl ∈
hAk be the columns of the matrix
b (notice that in Lemma 1 and Lemma 2 bi are rows of size l; so now we change
the notation). By definition b1, . . . , bl are linearly independent over
hA from the
right (or just linearly independent if it will not lead to an ambiguity) if and only
if for all z1, . . . , zl ∈
hA the equality b1z1+. . .+blzl = 0 implies z1 = . . . = zl = 0.
By (23) in this definition one can consider only homogeneous z1, . . . , zl. For an
arbitrary family b1, . . . , bl from Lemma 4 (with arbitrary k, l) one can choose a
maximal linearly independent from the right subfamily bi1 , . . . , bir of b1, . . . , bl.
It turns out that r does not depend on the choice of a subfamily. More precisely,
we have the following lemma.
LEMMA 5 Let cj =
1≤i≤l bizi,j, 1 ≤ j ≤ r1, where zi,j ∈
hA are homo-
geneous elements. Suppose that there are integers d′′j , 1 ≤ j ≤ r1, such that
for all i, j the degree deg zi,j = d
i − d
j . Assume that cj, 1 ≤ j ≤ r1, are lin-
early independent over hA from the right. Then r1 ≤ r, and if r1 < r there are
cr1+1, . . . , cr ∈ {bi1 , . . . , bir} such that cj, 1 ≤ j ≤ r, are linearly independent
over hA from the right.
PROOF The proof is similar to the case of vector spaces over a field and we
leave it to the reader.
We denote r = rankr{b1, . . . , bl} and call it the rank from the right of b1, . . . , bl.
In the similar way one can define rank from the left of b1, . . . , bl. Denote it by
rankl{b1, . . . , bl}. It is not difficult to construct examples when rankr{b1, . . . , bl}
6= rankl{b1, . . . , bl}. The aim of this section is to prove the following result.
LEMMA 6 Let b be the matrix with homogeneous coefficient from hA satisfying
(23), see above. Suppose that deg bi,j < d for all i, j. Assume that k ≥ l ≥ 1. Let
l1 = rankr{b1, . . . , bl} and b1, . . . , bl1 be linearly independent. Hence 0 ≤ l1 ≤ l.
Then there is a matrix (zj,r)1≤j,r≤l1 with homogeneous entries zj,r ∈
hA and a
square permutation matrix σ of size k satisfying the following properties.
(i) All the nonzero elements bi,jzj,r for 1 ≤ j ≤ l have the same degree
depending only on i, r and
deg zj,r ≤ (2n+ 3)ld. (30)
(ii) Set the matrix e = (ei,j)1≤i≤k, 1≤j≤l1 = σbz. Then the matrix
where e′ = diag(e′1,1, . . . , e
l1,l1
) is a diagonal matrix with l1 columns and
each e′j,j, 1 ≤ j ≤ l1, is nonzero.
(iii) ord ei,j ≥ ord e
j,j for all 1 ≤ i ≤ k, 1 ≤ j ≤ l1.
Besides that, if all ai,j (and hence all bi,j) do not depend on Xn (i.e., they
can be represented as sums of monomials which do not contain Xn) then one
can choose also zj,r satisfying additionally the same property. Finally, dividing
by an appropriate power of X0 one can assume without loss of generality that
min{ord zj,r : 1 ≤ j ≤ l1} = 0 for every 1 ≤ r ≤ l1.
PROOF At first we shall show how to construct z and e such that (ii) and
(iii) hold. We shall use a kind of Gauss elimination and Lemma 4. Namely, we
transform the matrix e. At the beginning we put
e = (e1, . . . , el1) = (b1, . . . , bl1).
We shall perform some hA-linear transformations of columns and permutations
of rows of the matrix e and replace each time e by the obtained matrix. These
transformation do not change the rank from the right of the family of columns
of e. At the end we get a matrix e satisfying the required properties (ii), (iii).
We have rankr(e) = l1. If l1 = 0, i.e, e is an empty matrix, then this is the
end of the construction: z′ is an empty matrix. Suppose that l1 > 0. Let us
choose indices 1 ≤ i0 ≤ k, 1 ≤ j0 ≤ l1 such that ord ei0,j0 = min1≤j≤l1{ord ej}.
Permuting rows and columns of e we shall assume without loss of generality
that (i0, j0) = (1, 1).
By Lemma 4 we get elements wi,1, wi,i ∈
hA of degrees at most (2n + 3)2d
such that e1,1w1,i = e1,iwi,i, 1 ≤ i ≤ l1, and ordwi,i = 0 for every 1 ≤ i ≤ l1.
Set w′ = (−w1,2, . . . ,−w1,l1), and w
′′ = diag(w2,2, . . . , wl1,l1) to be the diagonal
matrix. Put
1, w′
0, w′′
to be the square matrix with l1 rows. We replace e by ew. Now
e1,1, 0
E2,1, E2,2
where E2,2 has l1 − 1 columns and
1≤j≤l1
{ord bj} = ord e1,1 = min
1≤j≤l1
{ord ej} (31)
(for the new matrix e).
Let us apply recursively the described construction to the matrix E2,2 in
place of e. So using only linear transformations of columns with indices 2, . . . , l1
and permutation of rows with indices 2, . . . , k we transform e to the form
σeτ =
e1,1, 0
E′2,1, E
E′′2,1 E
 , τ =
0, τ ′
where σ is a permutation matrix and τ ′ is a square matrix with l1 − 1 rows (it
transforms E2,2), the matrix E
2,2 = diag(e2,2, . . . , el1,l1) is a diagonal matrix
with l1 − 1 ≥ 0 columns, and all the elements e2,2, . . . , el1,l1 ∈
hA are nonzero.
We shall assume without loss of generality that σ = 1 is the identity matrix. We
replace e by eτ . Conditions (ii) and (iii) hold for the obtained e and, more than
that, by (iii) applied recursively for (E2,2, E
2,2, E
2,2) (in place of (e, e
′, e′′)), and
(31) the same equalities are satisfied for the new obtained matrix e.
Let E′2,1 = (e2,1, . . . , el1,1)
t where t denotes transposition. By Lemma 4
there are nonzero elements v1,1, . . . , vl1,1 ∈
hA of degrees at most
(2n+ 3)(max{deg ei,i : 1 ≤ i ≤ l1}+ 1)l1 (32)
such that ei,1v1,1 = ei,ivi,1 and min{ord v1,1, ord v1,i} = 0 for all 1 ≤ i ≤ l1 − 1.
Let v′ = (−v2,1, . . . ,−vl1,1)
t and v′′ be the identity matrix of size l1 − 1. Put
v1,1, 0
v′, v′′
Let us replace e by ev. Put z = wτv, where the matrix z has l1 columns. Recall
that without loss of generality σ = 1 is the identity permutation. We have
e = (b1, . . . , bl1)z. These Gauss elimination transformations of e do not change
the rank from the right of the family of columns of e. It can be easily proved
using the recursion on l, cf. Lemma 8 below. Now the matrix e satisfies required
conditions (ii), (iii) and σ = 1.
Let us change the notation. Denote the obtained matrix z by z′. Let z′ =
(z′1, . . . , z
) where z′j is the j-th column of z
′. Our aim now is to prove the
existence of the matrix z satisfying (i)–(iii). By Lemma 4 for every 1 ≤ r ≤ l1
there are homogeneous elements zj,r ∈
hA, 1 ≤ j ≤ l, such that (z1,r, . . . , zl,r) 6=
(0, . . . , 0), ∑
1≤j≤l1
bi,jzj,r = 0 for every 1 ≤ i ≤ l1, i 6= r, (33)
and estimations for degrees (30) hold. Put the matrix z = (zj,r)1≤j,r≤l1 . Let
z = (z1, . . . , zl1) where zj is the j-th column of z. Hence zj = (z1,r, . . . , zl,r)
LEMMA 7 For every 1 ≤ r ≤ l1 we have
1≤j≤l1
br,jzj,r 6= 0. (34)
Further, for every 1 ≤ r ≤ l1 there are nonzero homogeneous elements g
r, gr ∈
hA such that z′rg
r = zrgr.
PROOF Consider the matrix (z′, zr) with l1 rows and l1 + 1 columns. By
Lemma 4 there are homogeneous elements h1, . . . , hl1+1 ∈
hA (they depend on r)
such that (h1, . . . , hl1+1) 6= (0, . . . , 0) and the following property holds. Denote
h = (h1, . . . , hl1+1)
t, h′ = (h1, . . . , hl1)
t. Then
z′h′ + zrhl1+1 = 0 (35)
(we don’t need at present any estimation on degrees from Lemma 4; only the
existence of h). Denote by b′′ the submatrix consisting of the first l1 rows of the
matrix (b1, . . . , bl1). Multiplying (35) to b
′′ from the left we get
b′′z′h′ + b′′zrhl1+1 = 0. (36)
But b′′z′ is a diagonal matrix with nonzero elements on the diagonal, see (ii)
(for z′ in place of z). Hence by (33) and (36) hj = 0 for every j 6= r. Now
h 6= (0, . . . , 0)t implies hr 6= 0 and hl1+1 6= 0. Therefore, (34) holds. Put
g′r = hr and gr = hl1+1. We have z
r = zrgr by (36). The lemma is proved.
Let us return to the proof of Lemma 6. Now (i)–(iii) are satisfied by Lemma 7.
The last assertions of Lemma 6 are proved similarly to the ones of Lemma 4.
Lemma 6 is proved.
7 An algorithm for solving linear systems with
coefficients from hA.
Let u = (u1, . . . , ul)
t ∈ hAl. Let all nonzero uj be homogeneous elements of the
degree −d′j+ρ for an integer ρ. Suppose that −d
j+ρ < d
′ for an integer d′ > 1.
Let b = (bi,j)1≤i≤k, 1≤j≤l be the matrix with k rows and l columns from the
statement of Lemma 6 (but now k and l are arbitrary). So deg bi,j = di−d
j < d
for all i, j. Let Z = (Z1, . . . , Zk) be unknowns. Consider the linear system
1≤i≤k
Zibi,j = uj , 1 ≤ j ≤ l, (37)
or, which is the same,
Zb = u.
Denote
ordu = min
1≤i≤k
{ordui}. (38)
The similar notations will be used for other vectors and matrices. In this section
we shall describe an algorithm for solving linear systems over hA and prove the
following theorem.
THEOREM 2 Suppose that system (37) has a solution over hA. One can
represent the set of all solutions of (37) over hA in the form
J + z∗,
where J ⊂ hAl is a hA-submodule of all the solutions of the homogeneous system
corresponding to (37) (i.e., system (37) with all uj = 0) and z
∗ is a particular
solution of (37). Moreover, the following assertions hold.
(A) One can choose z∗ such that ord z∗ ≥ ordu− ν, where ν ≥ 0 is an integer
bounded from above by (dl)2
(and depends only on d and l). The degree
deg z∗ is bounded from above by d′(dl)2
(B) There exists a system of generators of J of degrees bounded from above by
(dl)2
. The number of elements of this system of generators is bounded
from above by k(dl)2
Besides that, if all bi,j and uj do not depend on Xn (i.e., they can be represented
as sums of monomials which do not contain Xn) then z
∗ and all the generators
of the module J also satisfy this property.
PROOF Let l1 = rankr(b1, . . . , bl). Permuting equations of (37) we shall
assume without loss of generality that (b1, . . . , bl1) are linearly independent from
the right over hA. Let σ, z, e, e′, e′′ be the matrices from Lemma 6. Similarly to
the proof of Lemma 6 we shall assume without loss of generality that σ = 1.
Denote by b′ the submatrix of b consisting of the first l1 columns of b, i.e.,
b′ = (b1, . . . , bl1). By Lemma 4 there are nonzero elements q1,1, . . . , ql1,l1 of
degrees at most (32) such that e1,1q1,1 = ei,iqi,i and min{ord q1,1, ord qi,i} = 0
for all 2 ≤ i ≤ l1. Set q = diag(q1,1, . . . , ql1,l1) to be the diagonal matrix. Let
ν0 = ord e1,1q1,1. Then by Lemma 6 (iii) ord(b
′zq) ≥ ν0. Let X
0 δ = b
Then δ is a matrix with coefficients from hA and
where δ′ = diag(δ1,1, . . . , δl1,l1) is a diagonal matrix with homogeneous coef-
ficients from hA and all the elements on the diagonal are nonzero and equal,
i.e., δj,j = δ1,1 for every 1 ≤ j ≤ l1. Besides that, ord δ1,1 = 0. Fur-
ther, δ′′ = (δi,j)l1+1≤i≤k, 1≤j≤l1 . We have ord(uzq) ≥ ν0, since, otherwise,
system (37) does not have a solution. Obviously ordu ≤ ord(uzq). Denote
u′ = (u′0, . . . , u
t = X−ν00 uzq ∈
hAl. Hence ordu′ ≥ ord(u) − ν0. Consider the
linear system
Zδ = u′. (39)
LEMMA 8 Suppose that system (37) has a solution over hA. Then linear
system (39) is equivalent to (37), i.e., the sets of solutions of systems (39) and
(37) over hA coincide.
PROOF The system Zb′z = uz is equivalent to (37) by Lemma 5. System
(39) is equivalent to Zb′z = uz since the ring hA does not have zero–divisors.
The lemma is proved.
REMARK 4 Since rankr(b1, . . . , bl) = l1 and by Lemma 6 for every l1 + 1 ≤
j ≤ l there are homogeneous zj,j, z1,j , . . . , zl1,j ∈
hA such that zj,j 6= 0 and
bjzj,j +
1≤r≤l1
brzr,j = 0 and all deg zj,j, deg zr,j are bounded from above by
(2n+3)(l1+1)d. Put u
j = ujzj,j +
1≤r≤l1
urzr,j, l1+1 ≤ j ≤ l. Then system
(37) has a solution if and only if system (39) has a solution and u′j = 0 for all
l1 + 1 ≤ j ≤ l. This follows from Lemma 8 and Lemma 5. But in what follows
for our aims it is sufficient to use only Lemma 8.
REMARK 5 Assume that degXn bi,j ≤ 0 for all i, j, i.e., the elements of the
matrix b do not depend on Xn. Then by Lemma 4 and the described construction
all the elements of the matrices b, z, q, δ, δ′, δ′′ also do not depend on Xn.
By Lemma 4 and Remark 2 for every l1 + 1 ≤ j ≤ k there are homogeneous
elements gj,j , gj,i ∈
hA, 1 ≤ i ≤ l1, such that
gj,jδj,i = gj,iδ1,1, 1 ≤ i ≤ l1,
all the degrees deg gj,j , deg gj,i, 1 ≤ i ≤ l1, are bounded from above by
(2n+ 3)(l1 + 1)(max{deg δj,i : 1 ≤ i ≤ k}+ 1)
and min1≤i≤l1{ord gj,j , ord gj,i} = 0. Hence ord gj,j = 0 for every l1+1 ≤ j ≤ k
since ord δ1,1 = 0.
Denote h = δ1,1gl1+1,l1+1gl1+2,l1+2 . . . gk,k. So h ∈
hA is a nonzero homoge-
neous element and ordh = 0. Set ε = deg h. We need an analog of the Noether
normalization theorem from commutative algebra, cf. also Lemma 3.1 [7].
LEMMA 9 There is a linear automorphism of the algebra hA
α : hA → hA, α(Xi) =
1≤j≤n
(α1,i,jXj + α2,i,jDj),
α(Di) =
1≤j≤n
(α3,i,jXj + α4,i,jDj), α(X0) = X0, 1 ≤ i ≤ n,
such that all αs,i,j ∈ F , degDn α(h) = ε. If degXn h = 0 then one can choose
additionally α(Xn) = Xn, all α1,n,j = 0 for 1 ≤ j ≤ n − 1 and α3,n,j = 0 for
1 ≤ j ≤ n.
PROOF Recall that ordh = 0. Hence at first it is not difficult to construct
a linear automorphism β such that β(X0) = X0,
β(Xi) = β1,iXi + β2,iDi, β(Di) = β3,iXi + β4,iDi, 1 ≤ i ≤ n, (40)
and β(h) contains a monomial ai1,...,inD
1 , . . . , D
n with ai1,...,in 6= 0 and i1 +
. . .+in = ε, i.e., ε = degD1,...,Dn β(h). After that one can find an automorphism
γ such that γ(X0) = X0,
γ(Xi) =
1≤j≤n
γ1,i,jXj , γ(Di) =
1≤j≤n
γ4,i,jDj , 1 ≤ i ≤ n, (41)
and (γ ◦ β)(h) contains a monomial aDεn with a coefficient 0 6= a ∈ F . Put
α = γ ◦ β. We leave to prove the last assertion to the reader. The lemma is
proved.
We apply the automorphism α. In what follows to simplify the notation we
shall suppose without loss of generality that α = 1. So h contains a monomial
aDεn with a coefficient 0 6= a ∈ F , where ε = deg h. It follows from here that
degDn δ1,1 = deg δ1,1, degDn gj,j = deg gj,j , l1 + 1 ≤ j ≤ k. (42)
Let z = (z1, . . . , zk) ∈
hAk be a solution of (39). Then (42) implies that one can
uniquely represent
zj = z
jgj,j +
0≤s<deg gj,j
zj,sD
n, l1 + 1 ≤ j ≤ k, (43)
where z′j , zj,s ∈
hA, the degrees degDn zj,s ≤ 0 for all l1 + 1 ≤ j ≤ k, 0 ≤ s <
degD1 gj,j . Again by (42) one can uniquely represent
u′i = u
i δ1,1 +
0≤s<deg δ1,1
u′i,sD
n, 1 ≤ i ≤ l,
where u′′i , u
i,s ∈
hA, the degrees degDn u
i,s ≤ 0 for all 1 ≤ i ≤ l, 0 ≤ s <
degD1 gj,j . Finally, by (42) for all l1 +1 ≤ j ≤ k, 1 ≤ i ≤ l1, 0 ≤ r < degD1 gj,j,
one can uniquely represent
Drnδj,i = δj,r,iδ1,1 +
0≤r<deg δ1,1
δj,r,i,sD
where δj,r,i, δj,r,i,s ∈
hA, the degrees degDn δj,r,i,s ≤ 0 for all considered j, r, i, s.
I = { (j, r) : l1 + 1 ≤ j ≤ k&0 ≤ r < deg gj,j } ,
J = { (i, s) : 1 ≤ i ≤ l1 &1 ≤ s < deg δ1,1 } .
Therefore,
zi = −
l1+1≤j≤k
z′jgj,i −
(j,r)∈I
zj,rδj,r,i + u
i , 1 ≤ i ≤ l1, (44)
(j,r)∈I
zj,rδj,r,i,s = u
i,s, (i, s) ∈ J . (45)
Let us introduce new unknowns Zj,r, (j, r) ∈ I. By (43)–(45) system (37) is
reduced to the linear system
(j,r)∈I
Zj,rδj,r,i,s = u
i,s, (i, s) ∈ J . (46)
More precisely, any solution of system (37) is given by (43), (44) where z′j ∈
are arbitrary and zj,r is a solution of system (45) over
hA (we underline that
here this solution zj,r may depend on Dn although one can restrict oneself
by solutions zj,r which do not depend on Dn). Note that all δj,r,i,s and u
are homogeneous elements of hA and there are integers dj,r, (j, r) ∈ I, d
(i, s) ∈ J , ρ̃ such that deg δj,r,i,s = dj,r − d
i,s and deg u
i,s = −d
i,s + ρ̃ for all
(j, r) ∈ I, (i, s) ∈ J . This follows immediately from the described construction.
Now all the coefficients of system (46) do not depend on Dn. As we have
proved if the coefficients of (37) do not depend on Xn then the coefficients of
(46) also do not depend on Xn, and hence in the last case they do not depend
on Xn, Dn.
If the coefficients of (46) depend on Xn we perform an automorphism Xn 7→
Dn Dn 7→ −Xn, Xi 7→ Xi, Di 7→ Di, 1 ≤ i ≤ n − 1. Now the coefficients of
system (46) do not depend on Xn (but depend on Dn). After that we apply
our construction recursively to system (46).
The final step of the recursion is n = 0 (although in the statement of theorem
n ≥ 1, see Section 1; we are interested only in Weyl algebras). In this case
I = J = ∅. Hence using (44) for n = 0 we get the required z∗ and J for n = 0.
Thus, by the recursive assumption we get a particular solution Zj,r = z
(j, r) ∈ I, of system (46), an integer ν1 (in place of ν from assertion (A)) such
(j,r)∈I
{ord z∗j,r} ≥ min
(i,s)∈J
{ordu′i,s} − ν1, (47)
and a system of generators
( zα,j,r )(j,r)∈I , 1 ≤ α ≤ β, (48)
of the module J ′ of solutions of the homogeneous system corresponding to (46).
Notice that if the coefficients of (37) do not depend on Xn then J
′ is a module
over the homogenization F [X0, X1, . . . , Xn−1, D1, . . . , Dn−1] of the Weyl alge-
bra of X1, . . . , Xn−1, D1, . . . , Dn−1. But obviously in the last case (48) gives
also a system of generators of the hA-module J ′′ = hAJ ′ of solutions of the
homogeneous system corresponding to (46). Put
z∗i = −
(j,r)∈I
z∗j,rδj,r,i + u
i , 1 ≤ i ≤ l1,
z∗j =
0≤s<deg gj,j
z∗j,sD
n, l1 + 1 ≤ j ≤ k,
z∗ = (z∗1 , . . . , z
Then z∗ is a particular solution of (37). Put
zα,i = −
(j,r)∈I
zα,j,rδj,r,i, 1 ≤ i ≤ l1, 1 ≤ α ≤ β,
zα,j =
0≤s<deg gj,j
zα,j,sD
n, l1 + 1 ≤ j ≤ k, 1 ≤ α ≤ β,
zβ−l1+j,i = 0, l1 + 1 ≤ i, j ≤ k, i 6= j,
zβ−l1+j,j = gj,j , l1 + 1 ≤ j ≤ k,
zβ−l1+j,i = −gj,i, 1 ≤ i ≤ l1, l1 + 1 ≤ j ≤ k.
Then J =
1≤α≤β+k−l1
hA(zα,1, . . . , zα,k). Hence (zα,1, . . . , zα,k), 1 ≤ α ≤
β+k− l1, is a system of generators of the module J . By (47) and the definitions
of u′, u′′i and u
i,s we have ord z
∗ ≥ ordu− ν0 − ν1. Put ν = ν0 + ν1.
LEMMA 10 All the degrees deg δj,i, deg gj,i, deg δj,r,i, deg δj,r,i,s and ν, see
above, are bounded from above by (nld)O(1), the degrees deg u′i are bounded from
above d′ + (nld)O(1), the degrees deg u′′i , deg u
i,s are bounded from above by
d′(nld)O(1). Further, all ordu′′i , ordu
i,s are bounded from below by ordu − ν.
Finally, in system (46) the number of equations #J is bounded from above by
(nld)O(1) and the number of unknowns #I is bounded from above by k(nld)O(1).
PROOF This follows immediately from the described construction.
Let us return to the proof of Theorem 2. Applying Lemma 10 and recursively
assertions (A) and (B) for the formulas giving z∗ and J we get (A) and (B)
from the theorem. The last assertion (related to the case when all bi,j and uj
do not depend on Dn) has been already proved. The theorem is proved.
8 Proof of Theorem 1 for Weyl algebra
Let a be the matrix from Section 1. We shall suppose without loss of generality
that the vectors (ai,1, . . . , ai,l), 1 ≤ i ≤ k, are linearly independent over the field
F . We have deg ai,j < d. This implies k ≤ l
Put the matrix b = ha. Let us define the graded submodules of hI
hA(b1,1, . . . , b1,l) + . . .+
hA(bk,1, . . . , bk,l),
Jν = J0 : (X
0 ) = {z ∈
hAl : zXν0 ∈ J0}, ν ≥ 1.
We have the exact sequence of graded hA-modules
hAk → J0 → 0.
Further, Jν ⊂ Jν+1 ⊂
hI for every ν ≥ 0 and hI =
ν≥0 Jν . Since
hA is
Noetherian there is N ≥ 0 such that hI = JN . So to construct a system of
generators of hI it is sufficient to compute the least N such that hI = JN and
to find a system of generators of JN .
LEMMA 11 hI = JN for some N bounded from above by (dl)
2O(n) . There is a
system of generators b1, . . . , bs of the module JN such that s and all the degrees
deg bv, 1 ≤ v ≤ s, are bounded from above by (dl)
2O(n) .
PROOF Let us show that the module JN+1 ⊂ JN for N ≥ ν. Let u ∈ JN+1.
Consider system (37). By assertion (A) of Theorem 2 there is a particular
solution z∗ of (37) such that ord z∗ ≥ 1. Hence u ∈ X0JN ⊂ JN . The required
assertion is proved. Hence hI = Jν .
Let us replace in (37) (u1, . . . , ul) by (U1X
0 , . . . , UlX
0 ), where U1, . . . , Ul are
new unknowns. Then applying (B) from Theorem 2 to this new homogeneous
linear system with respect to all unknowns U1, . . . , Ul, Z1, . . . , Zk we get the
required estimations for the number of generators of Jν and the degrees of these
generators. The lemma is proved.
COROLLARY 1 Let (ai,1, . . . , ai,l), 1 ≤ i ≤ l, be from the beginning of the
section and the integer N be from Lemma 3. Then for every integer m ≥ 0 the
F–linear space
Am+N (a1,1, . . . , a1,l) + . . .+Am+N (ak,1, . . . , ak,l) ⊃ Im. (49)
PROOF By Lemma 3 we have (J0)m+N ⊃ X
0 (JN )m = X
hI)m. Taking
the affine parts we get (49). The corollary is proved.
Now everything is ready for the proof of Theorem 1. By Lemma 11 and
Lemma 1 there is a system of generators of the module gr(I) with degrees
bounded from above by (dl)2
. By Lemma 12 from Appendix 1 the Hilbert
function H(gr(I),m) is stable for m ≥ (dl)2
. By (10) Section 2 the Hilbert
function H(I,m) is stable for all m ≥ (dl)2
Consider the linear order < on the monomials from hAl which is induced by
the linear order < on the monomials from Al, see Section 4. Then the monomial
submodule cI ⊂ cAl is defined, see Section 4, where cA = F [X0, . . . , Xn, D1, . . . ,
Dn] is the polynomial ring. By (22) Section 4 the Hilbert function H(
cI,m) is
stable for all m ≥ (dl)2
. Hence all the coefficients of the Hilbert polynomial
of cI are bounded from above (dl)2
. Therefore, according to (31) the module
cI has a system of generators with degrees (dl)2
. This means, see Section 4,
that the module Hdt(hI) has a system of generators with degrees (dl)2
Therefore, the degrees of all the elements of the Janet basis of hI with respect
to the induced linear order < are bounded from above by (dl)2
. Hence by
Lemma 3 Section 4 the same is true for the Janet basis of the module I with
respect to the linear order < on the monomials from Al. Theorem 1 is proved
for Weyl algebra.
9 The case of algebra of differential operators
Denote by B = F (X1, . . . , Xn)[D1, . . . , Dn] the algebra of differential operators.
Recall that A ⊂ B and hence relations (1) are satisfied. Further, each element
f ∈ B can be uniquely represented in the form
j1,...,jn≥0
fj1,...,jnD
1 . . . D
where all fj1,...,jn = fj ∈ F (X1, . . . , Xn) and F (X1, . . . , Xn) is a field of rational
functions over F . Let us replace everywhere in Section 1 and Section 2 A,
X iDj , deg f = degX1,...,Xn,D1,...,Dn f , dimF M , ev,i,j , fv,i,j ∈ F , (v, i, j), (i, j),
(i′, j′), (i′′, j′′) by B, Dj , deg f = degD1,...,Dn f , dimF (X1,...,Xn) M , ev,j , fv,j ∈
F (X1, . . . , Xn), (v, j), j, j
′, j′′ respectively. Thus, we get the definition of the
Janet basis and all other objects from Section 1 for the case of the algebra of
differential operators.
We define the homogenization hB of B similarly to hA, see Section 3. Namely,
hB = F (X1, . . . , Xn)[X0, D1, . . . , Dn] given by the relations
XiXj = XjXi, DiDj = DjDi, for all i, j,
DiXi −XiDi = X0, 1 ≤ i ≤ n, XiDj = DjXi for all i 6= j.
Further, the considerations are similar to the case of the Weyl algebra A with
minor changes. We leave them to the reader. For example, Theorem 2 for
the case of the algebra of differential operators is the same. One need only to
replace everywhere in its statement A, hA and Xn by B,
hB and Dn respectively.
Thus, one can prove Theorem 1 for the case when A is an algebra of differential
operators (but now it is B). Theorem 1 is proved completely.
One can consider more general algebra of differential operators. Let F be a
field with n derivatives D1, . . . , Dn. Then Kn = F [D1, . . . , Dn] is the algebra of
differential operators and similarly one can define its homogenization hKn by
means of adding the variable X0 satisfying the relations
DiDj = DjDi, X0Di = DiX0, Dif − fDi = fDiX0
for all i, j and any element f ∈ F where fDi ∈ F denotes the result of the
application of Di to f . Following the proof of Theorem 1 one can deduce the
following statement.
REMARK 6 A similar bound to Theorem 1 holds for Kn.
Appendix 1: Degrees of generators of a graded
module over a polynomial ring and its Hilbert
function.
We give a short proof of the following result, cf. [1], [12], [6], [4].
LEMMA 12 Let I ⊂ Al be a graded submodule over the graded polynomial
ring A = F [X0, . . . , Xn], and I is given by a system of generators f1, . . . , fm of
degrees less than d. Then the Hilbert function H(Al/I,m) = dimF (A
l/I)m is
stable for m ≥ (dl)2
O(n+1)
. Further, all the coefficients of the Hilbert polynomial
of Al/I are bounded from above by (dl)2
O(n+1)
PROOF Denote M = Al/I. Let L ∈ F [X0, . . . , Xn] be a linear form in gen-
eral position. Denote byK the kernel of the morphismM → M of multiplication
to L. We have K = {z ∈ Al : Lz =
1≤i≤m fizi,& zi ∈ A}. Hence solving
a linear system over A, we get that K has a system of generators g1, . . . , gµ
with degrees bounded from above by (dl)2
O(n+1)
. Let P be an arbitrary associ-
ated prime ideal of the module M such that P 6= (X0, . . . , Xn). Since L is in
general position we have L 6∈ P. Hence P is not an associated prime ideal of
K. Therefore, KN = 0 for all sufficiently big N . So X
i gj ∈ I for sufficiently
big N and all i, j. Hence gj =
1≤i≤m yj,ifi where yj,i ∈ F (Xi)[X0, . . . , Xn].
Solving a linear system over the ring F (Xi)[X0, . . . , Xn] we get an estimation
for denominators from F [Xi] of all yj,i. Since all gj and fi are homogeneous we
can suppose without loss of generality that all the denominators are XNi . Thus,
we get an upper bound for N . Namely, N is bounded from above by (dl)2
O(n+1)
Therefore, the sequence
0 → Mm → Mm+1 → (M/LM)m+1 → 0 (51)
is exact for m ≥ (dl)2
O(n+1)
. But M/LM = Al/(I + LAl) is a module over
a polynomial ring of F [X0, . . . , Xn]/(L) ≃ F [X0, . . . , Xn−1]. Hence by the
inductive assumption the Hilbert function H(Al/(I + LAl),m) is stable for
m ≥ (dl)2
. Therefore, (51) implies that the Hilbert function H(Al/I,m) is
stable for m ≥ (dl)2
O(n+1)
Obviously for m < (dl)2
O(n+1)
the values H(Al/I,m) are bounded from
above by (dl)2
O(n+1)
. Hence by the Newton interpolation all the coefficients of
the Hilbert polynomial of Al/I are bounded from above by (dl)2
O(n+1)
. The
lemma is proved.
We need also a conversion of Lemma 12.
LEMMA 13 Let I ⊂ Al be a graded submodule over the graded polynomial
ring A = F [X0, . . . , Xn]. Assume that the Hilbert function H(A
l/I,m) =
dimF (A
l/I)m is stable for m ≥ D and all absolute values of the coefficients
of the Hilbert polynomial of the module Al/I are bounded from above by D for
some integer D > 1. Then I has a system of generators f1, . . . , fm with degrees
O(n+1)
PROOF Let us choose f1, . . . , fm to be the reduced Gröbner basis of I with
respect to an admissible linear order < on the monomials from Al, cf. the
definitions from Section 1 and Section 4. The degree of a monomial from Al is
defined similarly to Section 1 and Section 4. We shall suppose additionally that
the considered linear order is degree compatible, i.e., for any two monomials
z1, z2 if deg z1 < deg z2 then z1 < z2. For every z ∈ A the greatest monomial
Hdt(z) is defined. Further the monomial ideal Hdt(I) is generated by all Hdt(z),
z ∈ I. Now Hdt(f1), . . . ,Hdt(fm) is a minimal system of generators of Hdt(I)
and deg fi = degHdt(fi) for every 1 ≤ i ≤ m. The values of Hilbert functions
H(Al/Hdt(I),m) = H(Al/I,m) coincide for all m ≥ 0. Thus, replacing I
by Hdt(I) we shall assume in what follows in the proof that I is a monomial
module.
For every 1 ≤ i ≤ l denote by Ai ⊂ A
l the i-th direct summand of Al. Put
Ii = I ∩ Ai, 1 ≤ i ≤ l. Then I ≃ ⊕1≤i≤lIi since I is a monomial module.
Further, for every 1 ≤ α ≤ m there is 1 ≤ i ≤ l such that fα ∈ Ii. Let us
identify Ai = A. Then Ii ⊂ A is a homogeneous monomial ideal. The case
Ii = A is not excluded for some i. For the Hilbert functions we have
H(Al/I,m) =
1≤i≤l
H(A/Ii,m), m ≥ 0. (52)
If (A/Ii)D = 0 for some i then (A/Ii)m = 0 for every m ≥ D. In this case the
ideal Ii is generated by
0≤m≤D(Ii)m. Hence in (52) for the values m ≥ D one
can omit this index i in the sum from the right part. Therefore, in this case the
proof is reduced to a smaller l. So we shall assume without loss of generality
that (A/Ii)D 6= 0, 1 ≤ i ≤ l.
Further, we use the exact description of the Hilbert function of a homoge-
neous ideal, see [4] Section 7. Namely there are the unique integers bi,0 ≥ bi,1 ≥
. . . ≥ bi,n+2 = 0 such that
H(A/Ii,m) =
m+ n+ 1
1≤j≤n+1
m− bi,j + j − 1
for all sufficiently big m and
bi,0 = min{d : d ≥ bi,1 & ∀m > d (53) holds }. (54)
This description (without constants bi,0) is originated from the classical paper
[11]. The integers bi,0, . . . , bi,n+2 are called the Macaulay constants of the ideal
Ii. Besides that,
h(i,m) = H(A/Ii,m)−
m+ n+ 1
+ 1 +
1≤j≤n+1
m− bi,j + j − 1
for every m ≥ bi,1, see [4] Section 7. By Lemma 7.2 [4] for all 1 ≤ α ≤ m if
fα ∈ Ii then deg fα ≤ bi,0. Hence it is sufficient to prove that all bi,0, 1 ≤ i ≤ l,
are bounded from above by D2
O(n+1)
By (52) and (53) the coefficient at mn−j , 0 ≤ j ≤ n, of the Hilbert polyno-
mial of Al/I is
(n+ 1− j)!
1≤i≤l
bi,n+1−j +
0≤v≤j−1
1≤i≤l
(n+ 1− v)!
µj,v(bi,n+1−v), (56)
where 0 6= µj is an integer and µj,v ∈ Z[Z], 0 ≤ v ≤ j − 1, is a polynomial
with integer coefficients with deg µj,v = j − v + 1. Moreover, |µj | and absolute
values of all the coefficients of all the polynomials µj,v are bounded from above
by, say, 2O(n
2). Denote bj =
1≤i≤l bi,j , 0 ≤ j ≤ n + 2. By the condition of
the lemma all the coefficients of the Hilbert polynomial of Al/I are bounded
from above by D. Hence from (56) one can recursively estimate bn+1, bn, . . . , b1.
Namely, bn+1−j = (2
O(j+1)
, 0 ≤ j ≤ n. Hence b1 = (lD)
2O(n+1) . Notice
that bi,1 ≤ max1≤i≤l bi,1 ≤ b1 for every 1 ≤ i ≤ m.
Now let m ≥ max1≤i≤l bi,1. By (55) if h(i,m) 6= 0 for some 1 ≤ i ≤ l then
m < D, i.e., m is less than the bound D for the stabilization of the Hilbert
function of Al/I. Thus, bi,0 ≤ max{bi,1, D} by (54). Hence bi,0 is bounded
from above by (lD)2
O(n+1)
We have (A/Ii)D 6= 0 for every 1 ≤ i ≤ l. This implies H(A
l/I,D) ≥ l.
Denote by cj the j-th coefficient of the Hilbert polynomial of the module A
Now |cj |D
j ≥ l/(n + 1) for at least one j. Hence Dn+1(n + 1) ≥ l by the
condition of the lemma. This implies that l2
O(n+1)
is bounded from above by
O(n+1)
. Therefore, bi,0 is bounded from above by D
2O(n+1) . The lemma is
proved.
Appendix 2: Bound on the Gröbner basis of a
monomial module via the coefficients of its Hilbert
polynomial
Denote by Cl = Z
+ ∪ · · · ∪ Z
+ the disjoint union of l copies of the semigrid
+ = {(i1, . . . , in) : ij ≥ 0, 1 ≤ j ≤ n}. A subset of Cl which intersects
each disjoint copy of Zn+ by a semigroup closed with respect to addition of
elements from Zn+ is called an ideal of Cl. Any ideal I in Cl has a unique
finite Gröbner basis V = VI , denote T = Cl \ I. Clearly, I corresponds to a
monomial submodule in the free module (F [X1, . . . , Xn])
l. The degree of an
element u = (k; i1, . . . , in) ∈ Cl, 1 ≤ k ≤ l is defined as |u| = i1 + · · · + in.
The degree of a subset in Cl is defined as the maximum of the degrees of its
elements. The Hilbert function HT (z) equals to the number of vectors u ∈ T
such that |u| ≤ z. Then HT (z) =
0≤s≤m csz
s, z ≥ z0 for suitable z0,
integers c0, . . . , cm where the degree m ≤ n. Denote c = max0≤s≤m |cs|s! + 1.
PROPOSITION 1 (cf. [6], [12], [4]). The degree of V does not exceed
(cn)2
PROOF An s-cone we call a subset of a k-th copy of Zn+ in Cl for a certain
1 ≤ k ≤ l of the form
P = {Xj1 = i1, . . . , Xjn−s = in−s} (57)
for suitable 1 ≤ j1, . . . , jn−s ≤ n. The degree of (57) we define as |P | =
i1 + · · · + in−s (note that this definition is different from the one in [4]). By
a predessesor of (57) we mean each s-cone in the same k-th copy of Zn+ of the
{Xj1 = i1, . . . , Xjp−1 = ip−1, Xjp = ip − 1, Xjp+1 = ip+1, . . . , Xjn−s = in−s}
for some 1 ≤ p ≤ n− s, provided that ip ≥ 1. Fix an arbitrary linear order on
s-cones compatible with the relation of predessesors.
By inverse recursion on s we fill gradually T (as a union) by s-cones. For the
base we start with s = m. Assume that a current union T0 ⊂ T of m-cones is
already constructed (at the very beginning we put T0 = ∅) and an m-cone of the
form (57) with s = m is the least one (with respect to the fixed linear order on
m-cones) which is contained in T not being a subset of T0. Observe that each
predessesor of this m-cone was added to T0 at earlier steps of its construction.
Since the total number of m-cones added to T0 does not exceed cmm! < c we
deduce that the degree of every such m-cone is less than cmm! (taking into
account that the very first m-cone added to T0 has the degree 0).
For the recursive step assume that the current T0 is a union of all possible
m-cones, (m− 1)-cones,...,(s+1)-cones and perhaps, some s-cones. This can be
expressed as deg(HT −HT0) ≤ s. Again as in the base take the least s-cone of
the form (57) which is contained in T not being a subset of T0. Observe that
each predessesor of the type (58) of this s-cone is contained in an appropriate
r-cone Q, r ≥ s, such that Q was added to T0 at earlier steps of its constructing
and Q ⊂ {Xjp = ip − 1}. Hence
|Q| ≥ ip − 1. (59)
The described construction terminates when T0 = T . Denote by ts the
number of s-cones added to T0 and by ks the maximum of their degrees. We
have seen already that tm, km < c.
Now by inverse induction on s we prove that ts, ks ≤ (cn)
2O(m−s) . To this end
we introduce a relevant semilattice on cones. Let C = {Cα,β}α,β, 0 ≤ β ≤ γα
be a family of cones of the form (57) where dimCα,β = α. By an α-piece we
call an α-cone being the intersection of a few cones from C. All the pieces
constitute a semilattice L with respect to the intersection and with maximal
elements from C. We treat L also as a partially ordered set with respect to the
inclusion relation. Clearly, the depth of L is less than n. Our nearest purpose
is to bound from above the size of L. For the sake of simplifying the bound we
assume (and this will suffice for our goal in the sequel) that γα ≤ (cn)
2O(m−α)
for s ≤ α ≤ m and γα = 0 when α < s, although one could write a bound in
general in the same way. Besides that we assume that the constant in O(. . .) is
sufficiently big. In what follows all the constants in O(. . .) coincide.
LEMMA 14 Under the assumption on the numbers γα ≤ (cn)
2O(m−α) , s ≤
α ≤ m of maximal elements of all dimensions from C, the number of α-pieces in
L does not exceed (cn)2
O(m−α)+1 for s ≤ α ≤ m or (cn)2
O(m−s)(s−α+1)+1 when
α < s.
PROOF For each α-piece choose its arbitrary irredundant representation as
the intersection of the cones from C. Let δ be the minimal dimension among
these cones. Then this intersection contains at most δ−α+1 cones. Therefore,
the number of possible α-pieces does not exceed
max{α,s}≤δ≤m
(cn)2
O(m−δ)(δ−α+1),
that proves the lemma.
Now we come back to estimating ts, ks by inverse induction on s. Let in
the described above construction the current T0 is the union of all added m-
cones, (m − 1)-cones,...,s-cones. Denote this family of cones by C and consider
the corresponding semilattice L (see above). Our next purpose is to represent
T0 as a Z-linear combination of the pieces from L by means of a kind of the
inclusion-exclusion formula. We assign the coefficients of this combination by
recursion in L. As a base we assign 1 to each maximal piece, so to the elements
of C. As a recursive step, if for a certain piece P ∈ L the coefficients are already
assigned to all the pieces greater than P , we assign to P the coefficient ǫP in
such a way that the sum of the assigned coefficients to P and to all the greater
pieces equals to 1. Therefore, we get
where the sum is understood in the sense of multisets. Hence
HT0(z) =
z − |P |+ dimP
for large enough z. We recall that deg(HT −HT0) ≤ s− 1.
Now we majorate the coefficients |ǫP | by induction in the semilattice L. The
inductive hypothesis on tα ≤ (cn)
2O(m−α) , s ≤ α ≤ m and Lemma 14 imply that
dimP=λ
|ǫP | ≤ (cn)
2O(m−λ) , s− 1 ≤ λ ≤ m.
by inverse induction on λ following the assigning ǫP . In fact, one could majorate
in a similar way also
dimP=λ |ǫP | when λ < s− 1, but we don’t need it. The
inductive hypothesis on kα ≤ (cn)
2O(m−α) , s ≤ α ≤ m and (60) entail that
the coefficient of HT0(z) at the power z
α does not exceed (cn)2
O(m−α)
, s− 1 ≤
α ≤ m (actually, due to the inequality deg(HT −HT0) ≤ s− 1 the coefficients
at the powers zα for s ≤ α ≤ m are less than c). In particular, the coefficient at
the power zs−1 does not exceed (cn)2
O(m−s+1)
. Denote HT −HT0 = ηz
s−1+ · · ·.
By constructing T0 we add to it ts−1 = η(s− 1)! of (s− 1)-cones, which justifies
the inductive step for ts−1 ≤ (cn)
2O(m−s+1) .
To conduct the inductive step for ks−1 ≤ (cn)
2O(m−s+1) we observe that for
each (s − 1)-cone P added to T0 either every its predessesor is contained in a
cone of dimension at least s, or some its predessesor is an (s − 1)-cone as well.
In the former case |P | ≤ (maxs≤α≤m kα + 1)(n − s + 1) (due to (59)), while
in the latter case |P | is greater by 1 than the degree of this predessesor, hence
ks−1 ≤ (maxs≤α≤m kα + 1)(n − s + 1) + ts−1. Finally, exploit the inductive
hypothesis for km, . . . , ks, and the just obtained inequality on ts−1.
To complete the proof of the proposition it suffices to notice that for any
vector from the basis V treated as an 0-cone, each its predessesor of the type
(58) for s = 0 is contained in an appropriate r-cone, whence the degree of V
does not exceed (max0≤α≤m kα + 1)n again due to (59) (cf. above).
Acknowledgement. The authors are grateful to the Max-Planck Institut
für Mathematik, Bonn for its hospitality during the stay where the paper was
written.
References
[1] D.A. Bayer, The division algorithm and the Hilbert scheme, Ph.D. Thesis,
Harvard, 1982.
[2] A. Chistov, D. Grigoriev, Complexity of quantifier elimination in the theory
of algebraically closed fields, Lect. Notes Comput. Sci., 176 (1984), 17-31.
[3] D. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, Springer, 1998.
[4] T. Dubé, The structure of polynomial ideals and Gröbner bases, SIAM J.
Comput., 19 (1990), 750–775.
[5] A. Galligo, Some algorithmical questions on ideals of differential operators,
Lect.Notes Comput.Sci., 204 (1985), 413–421.
[6] M. Giusti, Some effective problems in polynomial ideal theory, Lect. Notes
Comput. Sci, 174 (1984), 159–171.
[7] D. Grigoriev, Weak Bézout inequality for D-modules, J.Complexity, 21,
(2005), 532–542.
[8] G. Hermann Die Frage der endlich vielen Schritte in der Theorie der Poli-
nomideale, Math. Ann. 95, (1926), 736-788.
[9] M. Janet, Les modules de formes algébriques et la théorie générale des
systèmes différentiels, Annals Sci. Ecole Normale Supér., 41 (1924), 27–65.
[10] H. Li, Noncommutative Gröbner bases and filtered-graded transfer, Lect.
Notes Math., 1795, 2002.
[11] F.S. Macaulay Some properties of enumeration in the theory of modular
systems, Proc. London Math. Soc. 26 (1927), 531–555.
[12] M. Möller, T. Mora, Upper and lower bounds for the degree of Groebner
bases, Lect. Notes Comput. Sci., 174 (1984), 172–183.
[13] F. Schwarz, Janet bases for symmetry groups, Groebner bases and applica-
tions, in London Math. Society, Lecture Note Ser. 251, 221-234, Cambridge
University Press, Cambridge, 1998.
[14] C. Yap, A new lower bound construction for commutative Thue systems,
with applications, J. Symb. Comput., 12 (1991), 1–27.
	Definition of the Janet basis
	The graded module corresponding to a D–module 
	Homogenization of the Weyl algebra
	The Janet bases of a module and of its homogenization
	Bound on the kernel of a matrix over the homogenized Weyl algebra
	Transforming a matrix with coefficients from h-A to the trapezoidal form
	An algorithm for solving linear systems with coefficients from h-A.
	Proof of Theorem ?? for Weyl algebra
	The case of algebra of differential operators

  We prove a double-exponential upper bound on the degree and on the complexity
of constructing a Janet basis of a $D$-module. This generalizes a well known
bound on the complexity of a Gr\"obner basis of a module over the algebra of
polynomials. We would like to emphasize that the obtained bound can not be
immediately deduced from the commutative case.

Introduction
Let A be the Weyl algebra F [X1, . . . , Xn,
, . . . , ∂
] (or the algebra of
differential operators F (X1, . . . , Xn)[
, . . . , ∂
]). Denote for brevity Di =
, 1 ≤ i ≤ n. Any A–module is called D–module. It is well known that
an A–module which is a submodule of a free finitely generated A-module has a
Janet basis. Historically, it was first introduced in [9]. In more recent times of
developing computer algebra Janet bases were studied in [5], [13], [10]. Janet
bases generalize Gröbner bases which were widely elaborated in the algebra of
polynomials (see e. g.[3]). For Gröbner bases a double-exponential complexity
bound was obtained in [12], [6] relying on [1] and which was made more precise
(with a self–contained proof) in [4].
Surprisingly, no complexity bound on Janet bases was established so far; in
the present paper we fill this gap and prove a double-exponential complexity
bound. On the other hand, a double-exponential complexity lower bound on
Gröbner bases [12], [14] provides by the same token a bound on Janet bases.
There is a folklore opinion that the problem of constructing a Janet basis
is easily reduced to the commutative case by considering the associated graded
module, and, on the other hand, in the commutative case [6], [12], [4] the double–
exponential upper bound is well known. But it turns out to be a fallacy! From
a known system of generators of a D-module one can not obtain immediately
any system of generators (even not necessarily a Gröbner basis) of the associ-
ated graded module. The main problem here is to construct such a system of
generators of the graded module. It may have the elements of degrees (dl)2
http://arxiv.org/abs/0704.1257v1
http://perso.univ-rennes1.fr/dmitry.grigoryev
see the notation below. Then, indeed, to the last system of generators of big
degrees one can apply the result known in the commutative case and get the
bound ((dl)2
= (dl)2
. So new ideas specific to non–commutative
case are needed.
We are interested in the estimations for Janet bases of A-submodules of Al.
The Janet basis depends on the choice of the linear order on the monomials (we
define them also for l > 1). In this paper we consider the most general linear
orders on the monomials from Al. They satisfy conditions (a) and (b) from
Section 1 and are called admissible. We prove the following result.
THEOREM 1 For any admissible linear order on the monomials from Al any
A-submodule I of Al generated by elements of degrees at most d (with respect
to the filtration in the corresponding algebra, see Section 1 and Section 9) has
a Janet basis with the degrees and the number of its elements less than
(dl)2
We prove in detail this theorem for the case of the Weyl algebra A. The proof
for the case of the algebra of differential operators is similar. It is sketched
in Section 9. ¿From Theorem 1 we get that the Hilbert function H(I,m), see
Section 1, of the A-submodule from this theorem is stable for m ≥ (dl)2
and the absolute values of all coefficients of the Hilbert polynomial of I are
bounded from above by (dl)2
, cf. e.g., [12]. This fact follows directly from
(10), Lemma 12 from Appendix 1, Lemma 2 and Theorem 2. We mention that
in [7] the similar bound was shown on the leading coefficient of the Hilbert
polynomial.
Now we outline the plan for the proof of Theorem 1. The main tool in the
proof is a homogenized Weyl algebra hA (or respectively, a homogenized alge-
bra of differential operators hB). It is introduced in Section 3 (respectively,
Section 9). The algebra hA (respectively hB) is generated over the ground
field F by X0, . . . , Xn, D1, . . . , Dn (respectively over the field F (X1, . . . , Xn)
by X0, D1, . . . , Dn). Here X0 is a new homogenizing variable. In the algebra
(respectively hB) relations (12) Section 3 (respectively (50) Section 9) hold for
these generators in hA.
We define the homogenization hI of the module I. It is a hA–submodule of
hAl. The main problem is to estimate the degrees of a system of generators of hI.
These estimations are central in the paper. They are deduced from Theorem 2
Section 7. This theorem is devoted to the problem of solving systems of linear
equations over the ring hA; we discuss it below in more detail.
The system of generators of hI gives a system of generators of the graded
gr(A)–module gr(I) corresponding to I. But gr(A) is a polynomial ring. Hence
using Lemma 12 Appendix 1 we get a double–exponential bound (dl)2
the stabilization of the Hilbert function of gr(I) and the absolute values of the
coefficients of the Hilbert polynomial of gr(I). Therefore, the similar bound
holds for the stabilization of the Hilbert functions of I and the coefficients of
the Hilbert polynomial of I, see Section 2.
But the Hilbert functions of the modules I and hI coincide, see Section 3.
Hence the last bound holds also for the stabilization of the Hilbert functions of
hI and the coefficients of the Hilbert polynomial of hI. In Section 5 we introduce
the linear order on the monomials from hAl induced by the initial linear order
on the monomials from Al (the homogenizing variable X0 is the least possible
in this ordering). Further, we define the Janet basis of hI with respect to the
induced linear order on the monomials. Such a basis can be obtained by the
homogenization of the elements of a Janet basis of I with respect to the initial
linear order, see Lemma 3.
Let Hdt(hI) be the monomial module (i.e., the module which has a system
of generators consisting of monomials) generated by the greatest monomials of
all the elements of the module hI, see Section 4. Let cI, see Section 4, be the
module over the polynomial ring cA = F [X0, . . . , Xn, D1, . . . , Dn] generated by
all the monomials from Hdt(hI) (they are considered now as elements of cA).
Then the Hilbert functions of the modules hI and cI coincide. Thus, we have the
same as above double–exponential estimation for the stabilization of the Hilbert
functions of cI and the coefficients of the Hilbert polynomial of cI. Now using
Lemma 13 we get the estimation (dl)2
on the monomial system of generators
of cI, hence also of Hdt(hI). This gives the bound for the degrees of the elements
of the Janet bases of hI and hence also for the required Janet basis of I, and
proves Theorem 1.
The problem of solving systems of linear equations over the homogenized
algebra is central in this paper, see Theorem 2. It is studied in Sections 5–
7. A similar problem over the Weyl algebra (without a homogenization) was
considered in [7]. The principal idea is to try to extend the well known method
due to G.Hermann [8] which was elaborated for the algebra of polynomials, to
the homogenized Weyl algebra. There are two principal difficulties on this way.
The first one is that in the method of G.Hermann the use of determinants is
essential which one has to avoid dealing with non-commutative algebras. The
second is that one needs a kind of the Noether normalization theorem in the
situation under consideration. So it is necessary to choose the leading elements
in the analog of the G.Hermann method with the least ordX0 , where X0 is a
homogenizing variable, see Section 3.
The obtained bound on the degree of a Janet basis implies a similar bound on
the complexity of its constructing. Indeed, by Corollary 1 (it is formulated for
the case of Weyl algebra but the analogous corollary holds for the case of algebra
of differential operators) one can compute the linear space of all the elements
z ∈ I of degrees bounded from above by (dl)2
. Further, by Theorem 1 the
module Hdt(I), see Section 1, is generated by all the elements Hdt(z) with z ∈ I
of degrees bounded from above by (dl)2
. Hence one can compute a system
of generators of Hdt(I) and a Janet basis of I solving linear systems over F of
size bounded from above (dl)2
(just by the enumeration of all monomials
of degrees at most (dl)2
which are possible generators of Hdt(I)). If one
needs to construct the reduced Janet basis it is sufficient to apply additionally
Remark 1 Section 4.
For the sake of self–containedness in Appendix 1, see Lemma 12, we give a
short proof of the double–exponential estimation for stabilization of the Hilbert
function of a graded module over a homogeneous polynomial ring. A conversion
of Lemma 12 also holds, see Appendix 1 Lemma 13. It is essential for us.
The proof of Lemma 13 uses the classic description of the Hilbert function of
a homogeneous ideal in F [X0, . . . , Xn] via Macaulay constants bn+2, . . . , b1 and
the constant b0 introduced in [4]. In Appendix 2 we give an independent and
instructive proof of Proposition 1 which is similar to Lemma 13. In some sence
Proposition 1 is even more strong than Lemma 13 since to apply it one does
not need a bound for the stabilization of the Hilbert function. Of course, the
reference to Proposition 1 can be used in place of Lemma 13 in our paper.
1 Definition of the Janet basis
Let A = F [X1, . . . , Xn, D1, . . . , Dn], n ≥ 1, be a Weyl algebra over a field F of
zero–characteristic. So A is defined by the following relations
XvXw = XwXv, DvDw = DwDv, DvXv−XvDv = 1, XvDw = DwXv, v 6= w.
By (1) any element f ∈ A can be uniquely represented in the form
i1,...,in,j1,...,jn≥0
fi1,...,in,j1,...,jnX
1 . . .X
1 . . . D
n , (2)
where all fi1,...,in,j1,...,jn ∈ F and only a finite number of fi1,...,in,j1,...,jn are
nonzero. Denote for brevity Z+ = {z ∈ Z : z ≥ 0} to the set of all nonnegative
integers and
i = (i1, . . . , in), j = (j1, . . . , jn), fi,j = fi1,...,in,j1,...,jn
X i = X i11 . . . X
n , D
j = D
1 . . . D
n , f =
fi,jX
iDj ,
|i| = i1 + . . .+ in, i+ j = (i1 + j1, . . . , in + jn).
So i, j ∈ Zn+ are multiindices. By definition the degree of f
deg f = degX1,...,Xn,D1,...,Dn f = max{|i|+ |j| : fi,j 6= 0}.
LetM be a left A-module given by its generatorsm1, . . . ,ml, l ≥ 0, and relations
1≤w≤l
av,wmw, 1 ≤ v ≤ k. (4)
where k ≥ 0 and all av,w ∈ A. We assume that deg av,w ≤ d for all v, w. By (4)
we have the exact sequence
→ M → 0 (5)
of left A-modules. Denote I = ι(Ak) ⊂ Al. If l = 1 then I is a left ideal of A
and M = A/I. In the general case I is generated by the elements
(av,1, . . . , av,l) ∈ A
l, 1 ≤ v ≤ k.
For an integer m ≥ 0 put
Am = {a : deg a ≤ m}, Mm = π(A
m), Im = I ∩ A
m. (6)
So now A, M , I are filtered modules with filtrations Am, Mm, Im, m ≥ 0,
respectively and the sequence of homomorphisms of vector spaces
0 → Im → A
m → Mm → 0
induced by (5) is exact for every m ≥ 0. The Hilbert function H(M,m) of the
module M is defined by the equality
H(M,m) = dimF Mm, m ≥ 0.
Each element ofAl can be uniquely represented as an F -linear combination of
elements ev,i,j = (0, . . . , 0, X
iDj , 0, . . . , 0), herewith i, j ∈ Zn+ are multiindices,
see (3), and the nonzero monomial X iDj is at the position v, 1 ≤ v ≤ l. So
every element f ∈ Al can be represented in the form
v,i,j
fv,i,jev,i,j , fv,i,j ∈ F. (7)
The elements ev,i,j will be called monomials.
Consider a linear order < on the set of all the monomials ev,i,j or which is
the same on the set of triples (v, i, j), 1 ≤ v ≤ l, i, j ∈ Zn+. If f 6= 0 put
o(f) = max{(v, i, j) : fv,i,j 6= 0}, (8)
see (7). Set
o(0) = −∞ < o(f)
for every 0 6= f ∈ A. Let us define the leading monomial of the element
0 6= f ∈ Al by the formula
Hdt(f) = fv,i,jev,i,j ,
where o(f) = (v, i, j). Put Hdt(0) = 0. Hence o(f−Hdt(f)) < o(f) if f 6= 0. For
f1, f2 ∈ A
l if o(f1) < o(f2) we shall write f1 < f2. We shall require additionally
(a) for all multiindices i, j, i′, j′ for all 1 ≤ v ≤ l if i1 ≤ i
1, . . . , in ≤ i
n and
j1 ≤ j
1, . . . , jn ≤ j
n then (v, i, j) ≤ (v, i
′, j′).
(b) for all multiindices i, j, i′, j′, i′′, j′′ for all 1 ≤ v, v′ ≤ l if (v, i, j) < (v′, i′, j′)
then (v, i+ i′′, j + j′′) < (v′, i′ + i′′, j′ + j′′).
Conditions (a) and (b) imply that for all f1, f2 ∈ A
l for every nonzero a ∈ A
if f1 < f2 then af1 < af2, i.e., the considered linear order is compatible with
the products. Any linear order on monomials ev,i,j satisfying (a) and (b) will
be called admissible.
Hdt(I) =
AHdt(f).
So Hdt(I) is an ideal of A. By definition the family f1, . . . , fm of elements of I
is a Janet basis of the module I if and only if
1) Hdt(I) = AHdt(f1)+ . . .+AHdt(fm), i.e., the submodule of A
l generated
by Hdt(f1), . . . ,Hdt(fm) coincides with Hdt(I).
Further, the Janet basis f1, . . . , fm of I is reduced if and only if the following
conditions hold.
2) f1, . . . , fm does not contain a smaller Janet basis of I,
3) Hdt(f1) > . . . > Hdt(fm).
4) the coefficient from F of every monomial Hdt(fv), 1 ≤ v ≤ l, is 1.
5) Let fα =
v,i,j
fα,v,i,jev,i,j be representation (2) for fα, 1 ≤ α ≤ m.
Then for all 1 ≤ α < β ≤ m for all 1 ≤ v ≤ l and multiindices i, j the
monomial fα,v,i,jev,i,j 6∈ Hdt(Afβ \ {0}).
Since the ringA is Noetherian for considered I there exists a Janet basis. Further
the reduced Janet basis of I is uniquely defined.
2 The graded module corresponding to a D–mo-
Put Av = Iv = Mv = 0 for v < 0 and
gr(A) = ⊕m≥0Am/Am−1, gr(I) = ⊕m≥0Im/Im−1, gr(M) = ⊕m≥0Mm/Mm−1.
The structure of the algebra on A induces the structure of a graded algeb-
ra on gr(A). So we have gr(A) = F [X1, . . . , Xn, D1, . . . , Dn] is an algebra of
polynomials with respect to the variables X1, . . . , Xn, D1, . . . , Dn. Further,
gr(I) and gr(M) are graded gr(A)-modules. From (6) we get the exact sequences
0 → Im/Im−1 → (Am/Am−1)
l → Mm/Mm−1 → 0, m ≥ 0. (9)
The Hilbert function of the module gr(M) is defined as follows
H(gr(M),m) = dimF Mm/Mm−1, m ≥ 0.
Obviously
H(M,m) =
0≤v≤m
H(gr(M), v), H(gr(M),m) = H(M,m)−H(M,m− 1).
for every m ≥ 0.
Denote for an arbitrary a ∈ M by gr(a) ∈ gr(M) the image of a in gr(M).
LEMMA 1 Assume that b1, . . . , bs is a system of generators of I. Let νi =
deg bi, 1 ≤ i ≤ s. Suppose that for every m ≥ 0
1≤v≤µ
cvbv : cv ∈ A, deg cv ≤ m− νv, 1 ≤ i ≤ s
. (11)
Then gr(b1), . . . , gr(bs) is a system of generators of the gr(A)-module gr(I).
PROOF This is straightforward.
So it is sufficient to construct a system of generators b1, . . . , bs of I satisfying
(11).
3 Homogenization of the Weyl algebra
Let X0 be a new variable. Consider the algebra
hA = F [X0, X1, . . . , Xn, D1,
. . . , Dn] given by the relations
XvXw = XwXv, DvDw = DwDv, for all v, w,
DvXv −XvDv = X
0 , 1 ≤ v ≤ n, XvDw = DwXv for all v 6= w.
The algebra hA is Noetherian similarly to the Weyl algebra A. By (12) an
element f ∈ hA can be uniquely represented in the form
i0,i1,...,in,j1,...,jn≥0
fi0,...,in,j1,...,jnX
0 . . . X
1 . . .D
n , (13)
where all fi0,...,in,j1,...,jn ∈ F and only a finite number of fi0,...,in,j1,...,jn are
nonzero. Let i, j be multiindices, see (3). Denote for brevity
i = (i1, . . . , in), j = (j1, . . . , jn), fi0,i,j = fi0,...,in,j1,...,jn
i0,i,j
fi0,i,jX
iDj .
By definition the degrees of f
deg f = degX0,...,Xn,D1,...,Dn f = max{i0 + |i|+ |j| : fi0,i,j 6= 0},
degD1,...,Dn f = max{|j| : fi0,i,j 6= 0},
degDα f = max{jα : fi0,i,j 6= 0}, 1 ≤ α ≤ n
degXα f = max{iα : fi0,i,j 6= 0}, 1 ≤ α ≤ n
Set ord 0 = ordX0 0 = +∞. If 0 6= f ∈
hA then put
ord f = ordX0 f = µ if and only if f ∈ X
hA) \X
hA), µ ≥ 0. (15)
For every z = (z1, . . . , zl) ∈
hAl put
ord z = min
1≤i≤l
{ord zi}, deg z = max
1≤i≤l
{deg zi}.
Similarly one defines ord b and deg b for an arbitrary (k × l)–matrix b with
coefficients from hA. More precisely, one consider here b as a vector with kl
entries.
The element f ∈ hA is homogeneous if and only if fi0,i,j 6= 0 implies i0+ |i|+
|j| = deg f , i.e., if and only if f is a sum of monomials of the same degree deg f .
The homogeneous degree of a nonzero homogeneous element f is its degree.
The homogeneous degree of 0 is not defined (0 belongs to all the homogeneous
components of hA, see below).
The m-th homogeneous component of hA is the F -linear space
(hA)m =
z ∈ hA : z is homogeneous & deg z = m or z = 0
for every integer m. Now hA is a graded ring with respect to the homogeneous
degree. By definition the ring hA is a homogenization of the Weyl algebra A.
We shall consider the category of finitely generated graded modules G over
the ring hA. Such a module G = ⊕m≥m0Gm is a direct sum of its homogeneous
components Gm, where m,m0. are integers. Every Gm is a finite dimensional
F -linear space and (hA)pGm ⊂ Gp+m for all integers p,m. If G and G
′ are
two finitely generated graded hA-modules then ϕ : G → G′ is a morphism (of
degree 0) of the graded modules if and only if ϕ is a morphism of hA-modules
and ϕ(Gm) ⊂ G
m for every integer m.
The element z ∈ hA (respectively z ∈ A) is called to be the term if and
only if z = λz1 · . . . · zν for some 0 6= λ ∈ F , integer ν ≥ 0 and zw ∈
{X0, . . . , Xn, D1, . . . , Dn} (respectively zw ∈ {X1, . . . , Xn, D1, . . . , Dn}), 1 ≤
w ≤ ν.
Let z =
zj ∈ A be an arbitrary element of the Weyl algebraA represented
as a sum of terms zj and deg z = maxj deg zj. One can take here, for example,
representation (3) for z. Then we define the homogenization hz ∈ hA by the
formula
deg z−deg zj
By (1), (12) the right part of the last equality does not depend on the chosen
representation of z as a sum of terms. Hence hz is defined correctly. If z ∈ hA
then az ∈ A is obtained by substituting X0 = 1 in z. Hence for every z ∈ A we
have ahz = z, and for every z ∈ hA the element z = hazX
0 , where µ = ord z.
For an element z = (z1, . . . , zl) ∈ A
l put deg z = max1≤i≤l{deg zi} and
deg z−deg z1
0 , . . . ,
deg z−deg zl
∈ hAl.
Similarly one defines deg a and the homogenization ha = (av,w)1≤v≤k, 1≤w≤l for
an arbitrary k×l–matrix a with coefficients from A. More precisely, one consider
here a as a vector with kl entries. Hence if b = (bv,w)1≤v≤k, 1≤w≤l =
ha then
bv,w =
hav,wX
deg a−deg av,w
0 for all v, w.
The m-th homogeneous component of hAl is
(hAl)m =
hz : z ∈ Al & deg z = m or z = 0
For an F -linear subspace X ⊂ Al put hX to be the least linear subspace of hAl
containing the set {hz : z ∈ X}. If X is a (finitely generated) A-submodule of
Al then hX is a (finitely generated) graded submodule of hAl. The graduation
on hX is induced by the one of hAl.
For an element z = (z1, . . . , zl) ∈
hAl put az = (az1, . . . ,
azl) ∈ A
l. For a
subset X ⊂ hAl put aX = {az : z ∈ X} ⊂ Al. If X is a F -linear space then aX
is also a F -linear space. If X is a finitely generated graded submodule of hAl
then aX is finitely generated submodule of Al.
Now hI is a graded submodule of hAl. Further, ahI = I. Let (hI)m be the
m-th homogeneous component of hI. Then
h(Im) = ⊕0≤j≤m(
hI)j , m ≥ 0, (16)
a((hI)m) = Im, m ≥ 0. (17)
and (17) induces the isomorphism ι : (hI)m → Im. Set
hM = hAl/hI. Hence
hM is a graded hA-module and we have the exact sequence
0 → hI → hAl → hM → 0. (18)
The m-th homogeneous component (hM)m of
(hM)m = (
hAl)m/(
hI)m ≃ A
m/Im. (19)
by the isomorphism ι. We have the exact sequences
0 → (hI)m → (
hAl)m → (
hM)m → 0, m ≥ 0. (20)
By definition the Hilbert function of the module hM is
H(hM,m) = dimF (
hM)m, m ≥ 0.
By (19) we have H(M,m) = H(hM,m) for every m ≥ 0, i.e., the Hilbert
functions of M and hM coincide.
LEMMA 2 Let b1, . . . , bs be a system of homogeneous generators of the
module hI. Then
gr(ab1), . . . , gr(
abs) ∈ gr(A)
is a system of generators of gr(A)-module gr(I).
PROOF By (17) a((hI)m) = Im. Now the required assertion follows from
Lemma 1. The lemma is proved.
4 The Janet bases of a module and of its ho-
mogenization
Each element of hAl can be uniquely represented as an F -linear combination of
elements ev,i0,i,j = (0, . . . , 0, X
iDj , 0, . . . , 0), herewith 0 ≤ i0 ∈ Z, i, j ∈ Z
are multiindices, see (3), and the nonzero monomial X i00 X
iDj is at the position
v, 1 ≤ v ≤ l. So every element f ∈ hAl can be represented in the form
v,i0,i,j
fv,i0,i,jev,i0,i,j , fv,i0,i,j ∈ F. (21)
and only a finite number of fv,i0,i,j are nonzero. The elements ev,i0,i,j will be
called monomials.
Let us replace everywhere in Section 1 after the definition of the Hilbert
function the ring A, the monomials ev,i,j , the multiindices i, i
′, i′′, triples
(v, i, j), (v, i′, j′), the module I and so on by the ring hA, monomials ev,i0,i,j ,
the pairs (i0, i), (i
′), (i′′0 , i
′′) (they are used without parentheses), quadruples
(v, i0, i, j), (v, i
′, j′), the homogenization hI and so on respectively. Thus, we
get the definitions of o(f), Hdt(f) for f ∈ hAl, new conditions (a) and (b) which
define admissible linear order on the monomials of hAl, new conditions 1)–5),
the definitions of the Janet basis and reduced Janet basis of hI. For example,
the new conditions (a) and (b) are
(a) for all indices i0, i
0, all multiindices i, j, i
′, j′ for all 1 ≤ v ≤ l if i0 ≤ i
i1 ≤ i
1, . . . , in ≤ i
n and j1 ≤ j
1, . . . , jn ≤ j
n then (v, i0, i, j) ≤ (v, i
′, j′).
(b) for all indices i0, i
0 , all multiindices i, j, i
′, j′, i′′, j′′ for all 1 ≤ v, v′ ≤ l
if (v, i0, i, j) < (v
′, i′0, i
′, j′) then (v, i0+ i
0 , i+ i
′′, j+ j′′) < (v′, i′0+ i
0 , i
i′′, j′ + j′′).
The Janet basis of hI is homogeneous if and only if it consists of homogeneous
elements from hAl.
Let< be an admissible linear order on the monomials fromAl, or which is the
same, on the triples (v, i, j), see Section 1. So < satisfies conditions (a) and (b).
Let us define the linear order on the monomials ev,i0,i,j or, which is the same,
on the quadruples (v, i0, i, j). This linear order is induced by < on the triples
(v, i, j) and will be denoted again by <. Namely, for two quadruples (v, i0, i, j)
and (v′, i′0, i
′, j′) put (v, i0, i, j) < (v
′, i′0, i
′, j′) if and only if (v, i, j) < (v′, i′, j′),
or (v, i, j) = (v′, i′, j′) but i0 < i
0. Notice that this induced linear order satisfies
conditions (a) and (b) (in the new sense).
REMARK 1 If f1, . . . , fm is a Janet basis of I (respectively homogeneous
Janet basis of hI) satisfying 1)–4) then there are the unique cα,β ∈ A (respec-
tively cα,β ∈
hA), 1 ≤ α < β ≤ m, such that
α<β≤m
cα,βfβ , 1 ≤ α ≤ m,
is a reduced Janet basis of I (respectively reduced homogeneous Janet basis of
hI), cf. [3].
LEMMA 3 Let f1, . . . , fm be a (reduced) Janet basis of I with respect to the
linear order <. Then hf1, . . . ,
hfm is a (reduced) homogeneous Janet basis of the
module hI with respect to the induced linear order <. Conversely, let g1, . . . , gm
be a (reduced) homogeneous Janet basis of the module hI with respect to the
induced linear order <. Then ag1, . . . ,
agm is a (reduced) Janet basis of I with
respect to the linear order <.
PROOF This follows immediately from the definitions.
Let f ∈ hAl and the module hI be as above. Then there is the unique element
g ∈ hAl such that
v,i0,i,j
gv,i0,i,jev,i0,i,j , gv,i0,i,j ∈ F,
f −g ∈ hI and if gv,i0,i,j 6= 0 then ev,i0,i,j 6∈ Hdt(
hI). The element g is called the
normal form of f with respect to the module hI. We shall denote g = nf(hI, f).
Obviously nf(hI, (hAl)m) ⊂ (
hAl)m is a linear subspace.
Let cA = F [X0, . . . , Xn, D1, . . . , Dn] be the polynomial ring in the variables
X0, . . . , Xn, D1, . . . , Dn. Each monomial ev,i0,i,j can be considered also as an
element of cAl. Denote by cI ⊂ cAl the graded submodule of cAl generated by
all the monomials ev,i0,i,j such that there is 0 6= f ∈
hI with o(f) = (v, i0, i, j).
The Hilbert functions
H(cI,m) = dimF {(z1, . . . , zl) ∈
cI : ∀ i ( deg zi = m or zi = 0 )},
H(cAl/cI,m) =
m+ 2n
−H(cI,m).
Let us replace in the definition of the normal form above hA, hI by cA, cI respec-
tively. Thus, for f ∈ cAl we get the definition of the normal form nf(cI, f) ∈ cAl,
cf. [4]. Obviously, nf(cI, (cAl)m) ⊂ (
cAl)m is a linear subspace. Since the ideals
and Hdt(hI) are generated by the same monomials we have dimnf(cI, (cAl)m) =
dimnf(hI, (hAl)m). Hence the Hilbert functions
H(hAl/hI,m) = H(cAl/cI,m), H(hI,m) = H(cI,m), m ≥ 0,
coincide. Therefore, see Section 3,
H(I,m) = H(cI,m), m ≥ 0 (22)
5 Bound on the kernel of a matrix over the ho-
mogenized Weyl algebra
LEMMA 4 Let k = l− 1 and l ≥ 1 be integers. Let b = (bi,j)1≤i≤k, 1≤j≤l be a
matrix where bi,j ∈
hA are homogeneous elements for all i, j. Let deg bi,j < d,
d ≥ 1, for all i, j. Assume that there are integers dj ≥ 0, 1 ≤ i ≤ k, and d
i ≥ 0,
1 ≤ j ≤ l, such that
deg bi,j = di − d
j (23)
for all nonzero bi,j, and additionally min1≤j≤l{d
j} = 0 (hence di < d, d
j < d
for all i, j), d ≥ 1. Then there are homogeneous elements z1, . . . , zl ∈
hA such
that (z1, . . . , zl) 6= (0, . . . , 0),
1≤j≤l
bi,jzj = 0, 1 ≤ i ≤ l − 1, (24)
all nonzero bi,jzj have the same degree depending only on i and
deg zj ≤ (2n+ 3)ld, 1 ≤ j ≤ l. (25)
Besides that, if all bi,j do not depend on Xn (i.e., they can be represented as
sums of monomials which do not contain Xn) then one can choose also z1, . . . , zl
satisfying additionally the same property. Finally, dividing by an appropriate
power of X0 one can assume without loss of generality that min{ord zi : 1 ≤
i ≤ l} = 0.
PROOF We shall assume without loss of generality that l ≥ 2. At first
suppose that that deg bi,j = deg b for all nonzero bi,j . Consider the linear
mapping
(hA)lm−deg b −→ (
hA)l−1m ,
( z1, . . . , zl ) 7→
1≤j≤l bi,jzj
1≤i≤l−1
m− deg b+ 2n
> (l − 1)
m+ 2n
then the kernel of (26) is nonzero. But (27) holds if
deg b
m+ 2n− deg b
deg b
m+ 2n− 1− deg b
. . .
deg b
m− deg b
l − 1
Further, (28) is true if (1+ deg b/(m− deg b))2n < l/(l− 1). The last inequality
follows from m ≥ (2n + 1) deg b/ log(l/(l − 1)). Hence also from m ≥ (2n +
1)l deg b. Notice that (2n + 2)ld ≥ 1 + (2n + 1)l deg b. Thus, the existence of
z1, . . . , zl is proved, and even more all nonzero bi,jzj have the same degree which
does not depend on i, j. Notice that in the considered case we prove a more
strong inequality deg zj ≤ (2n+ 2)ld for all 1 ≤ j ≤ l.
Suppose that a1, . . . , al do not depend on Xn. We represent zi =
zi,jX
1 ≤ i ≤ l, where all zi,j do not on Xn. Let α = maxi{degXn zi}. Obviously in
this case one can replace (z1, . . . , zl) by (z1,α, . . . , zl,α).
Let us return to general case of arbitrary deg bi,j . We shall reduce it to
the considered one. Namely, multiplying the i-th equation of system (24) to
maxi{di}−di
0 we shall suppose without loss of generality that all di are equal.
Let us substitute zjX
0 for zj in (24). Now the degrees of all the nonzero
coefficients of the obtained system coincide. Thus, we get the required reduction
and estimation (25). The lemma is proved.
REMARK 2 Lemma 4 remains true if one replaces in its statement condition
(24) by ∑
1≤j≤l
zjbi,j = 0, 1 ≤ i ≤ l − 1, (29)
The proof is similar.
REMARK 3 Let the elements bi,j be from Lemma 4. Notice that there are
integers δ′i ≥ 0, 1 ≤ i ≤ k, and δj ≥ 0, 1 ≤ j ≤ l, such that
deg bi,j = δj − δ
for all nonzero bi,j, and min1≤i≤k{δ
i} = 0. Namely, δ
i = −di +max1≤i≤k{di},
δj = −d
j +max1≤i≤k{di}.
6 Transforming a matrix with coefficients from
A to the trapezoidal form
Let b be the matrix from Lemma 4 but now k, l are arbitrary. Hence (23)
holds. Let b = (b1, . . . , bl) where b1, . . . , bl ∈
hAk be the columns of the matrix
b (notice that in Lemma 1 and Lemma 2 bi are rows of size l; so now we change
the notation). By definition b1, . . . , bl are linearly independent over
hA from the
right (or just linearly independent if it will not lead to an ambiguity) if and only
if for all z1, . . . , zl ∈
hA the equality b1z1+. . .+blzl = 0 implies z1 = . . . = zl = 0.
By (23) in this definition one can consider only homogeneous z1, . . . , zl. For an
arbitrary family b1, . . . , bl from Lemma 4 (with arbitrary k, l) one can choose a
maximal linearly independent from the right subfamily bi1 , . . . , bir of b1, . . . , bl.
It turns out that r does not depend on the choice of a subfamily. More precisely,
we have the following lemma.
LEMMA 5 Let cj =
1≤i≤l bizi,j, 1 ≤ j ≤ r1, where zi,j ∈
hA are homo-
geneous elements. Suppose that there are integers d′′j , 1 ≤ j ≤ r1, such that
for all i, j the degree deg zi,j = d
i − d
j . Assume that cj, 1 ≤ j ≤ r1, are lin-
early independent over hA from the right. Then r1 ≤ r, and if r1 < r there are
cr1+1, . . . , cr ∈ {bi1 , . . . , bir} such that cj, 1 ≤ j ≤ r, are linearly independent
over hA from the right.
PROOF The proof is similar to the case of vector spaces over a field and we
leave it to the reader.
We denote r = rankr{b1, . . . , bl} and call it the rank from the right of b1, . . . , bl.
In the similar way one can define rank from the left of b1, . . . , bl. Denote it by
rankl{b1, . . . , bl}. It is not difficult to construct examples when rankr{b1, . . . , bl}
6= rankl{b1, . . . , bl}. The aim of this section is to prove the following result.
LEMMA 6 Let b be the matrix with homogeneous coefficient from hA satisfying
(23), see above. Suppose that deg bi,j < d for all i, j. Assume that k ≥ l ≥ 1. Let
l1 = rankr{b1, . . . , bl} and b1, . . . , bl1 be linearly independent. Hence 0 ≤ l1 ≤ l.
Then there is a matrix (zj,r)1≤j,r≤l1 with homogeneous entries zj,r ∈
hA and a
square permutation matrix σ of size k satisfying the following properties.
(i) All the nonzero elements bi,jzj,r for 1 ≤ j ≤ l have the same degree
depending only on i, r and
deg zj,r ≤ (2n+ 3)ld. (30)
(ii) Set the matrix e = (ei,j)1≤i≤k, 1≤j≤l1 = σbz. Then the matrix
where e′ = diag(e′1,1, . . . , e
l1,l1
) is a diagonal matrix with l1 columns and
each e′j,j, 1 ≤ j ≤ l1, is nonzero.
(iii) ord ei,j ≥ ord e
j,j for all 1 ≤ i ≤ k, 1 ≤ j ≤ l1.
Besides that, if all ai,j (and hence all bi,j) do not depend on Xn (i.e., they
can be represented as sums of monomials which do not contain Xn) then one
can choose also zj,r satisfying additionally the same property. Finally, dividing
by an appropriate power of X0 one can assume without loss of generality that
min{ord zj,r : 1 ≤ j ≤ l1} = 0 for every 1 ≤ r ≤ l1.
PROOF At first we shall show how to construct z and e such that (ii) and
(iii) hold. We shall use a kind of Gauss elimination and Lemma 4. Namely, we
transform the matrix e. At the beginning we put
e = (e1, . . . , el1) = (b1, . . . , bl1).
We shall perform some hA-linear transformations of columns and permutations
of rows of the matrix e and replace each time e by the obtained matrix. These
transformation do not change the rank from the right of the family of columns
of e. At the end we get a matrix e satisfying the required properties (ii), (iii).
We have rankr(e) = l1. If l1 = 0, i.e, e is an empty matrix, then this is the
end of the construction: z′ is an empty matrix. Suppose that l1 > 0. Let us
choose indices 1 ≤ i0 ≤ k, 1 ≤ j0 ≤ l1 such that ord ei0,j0 = min1≤j≤l1{ord ej}.
Permuting rows and columns of e we shall assume without loss of generality
that (i0, j0) = (1, 1).
By Lemma 4 we get elements wi,1, wi,i ∈
hA of degrees at most (2n + 3)2d
such that e1,1w1,i = e1,iwi,i, 1 ≤ i ≤ l1, and ordwi,i = 0 for every 1 ≤ i ≤ l1.
Set w′ = (−w1,2, . . . ,−w1,l1), and w
′′ = diag(w2,2, . . . , wl1,l1) to be the diagonal
matrix. Put
1, w′
0, w′′
to be the square matrix with l1 rows. We replace e by ew. Now
e1,1, 0
E2,1, E2,2
where E2,2 has l1 − 1 columns and
1≤j≤l1
{ord bj} = ord e1,1 = min
1≤j≤l1
{ord ej} (31)
(for the new matrix e).
Let us apply recursively the described construction to the matrix E2,2 in
place of e. So using only linear transformations of columns with indices 2, . . . , l1
and permutation of rows with indices 2, . . . , k we transform e to the form
σeτ =
e1,1, 0
E′2,1, E
E′′2,1 E
 , τ =
0, τ ′
where σ is a permutation matrix and τ ′ is a square matrix with l1 − 1 rows (it
transforms E2,2), the matrix E
2,2 = diag(e2,2, . . . , el1,l1) is a diagonal matrix
with l1 − 1 ≥ 0 columns, and all the elements e2,2, . . . , el1,l1 ∈
hA are nonzero.
We shall assume without loss of generality that σ = 1 is the identity matrix. We
replace e by eτ . Conditions (ii) and (iii) hold for the obtained e and, more than
that, by (iii) applied recursively for (E2,2, E
2,2, E
2,2) (in place of (e, e
′, e′′)), and
(31) the same equalities are satisfied for the new obtained matrix e.
Let E′2,1 = (e2,1, . . . , el1,1)
t where t denotes transposition. By Lemma 4
there are nonzero elements v1,1, . . . , vl1,1 ∈
hA of degrees at most
(2n+ 3)(max{deg ei,i : 1 ≤ i ≤ l1}+ 1)l1 (32)
such that ei,1v1,1 = ei,ivi,1 and min{ord v1,1, ord v1,i} = 0 for all 1 ≤ i ≤ l1 − 1.
Let v′ = (−v2,1, . . . ,−vl1,1)
t and v′′ be the identity matrix of size l1 − 1. Put
v1,1, 0
v′, v′′
Let us replace e by ev. Put z = wτv, where the matrix z has l1 columns. Recall
that without loss of generality σ = 1 is the identity permutation. We have
e = (b1, . . . , bl1)z. These Gauss elimination transformations of e do not change
the rank from the right of the family of columns of e. It can be easily proved
using the recursion on l, cf. Lemma 8 below. Now the matrix e satisfies required
conditions (ii), (iii) and σ = 1.
Let us change the notation. Denote the obtained matrix z by z′. Let z′ =
(z′1, . . . , z
) where z′j is the j-th column of z
′. Our aim now is to prove the
existence of the matrix z satisfying (i)–(iii). By Lemma 4 for every 1 ≤ r ≤ l1
there are homogeneous elements zj,r ∈
hA, 1 ≤ j ≤ l, such that (z1,r, . . . , zl,r) 6=
(0, . . . , 0), ∑
1≤j≤l1
bi,jzj,r = 0 for every 1 ≤ i ≤ l1, i 6= r, (33)
and estimations for degrees (30) hold. Put the matrix z = (zj,r)1≤j,r≤l1 . Let
z = (z1, . . . , zl1) where zj is the j-th column of z. Hence zj = (z1,r, . . . , zl,r)
LEMMA 7 For every 1 ≤ r ≤ l1 we have
1≤j≤l1
br,jzj,r 6= 0. (34)
Further, for every 1 ≤ r ≤ l1 there are nonzero homogeneous elements g
r, gr ∈
hA such that z′rg
r = zrgr.
PROOF Consider the matrix (z′, zr) with l1 rows and l1 + 1 columns. By
Lemma 4 there are homogeneous elements h1, . . . , hl1+1 ∈
hA (they depend on r)
such that (h1, . . . , hl1+1) 6= (0, . . . , 0) and the following property holds. Denote
h = (h1, . . . , hl1+1)
t, h′ = (h1, . . . , hl1)
t. Then
z′h′ + zrhl1+1 = 0 (35)
(we don’t need at present any estimation on degrees from Lemma 4; only the
existence of h). Denote by b′′ the submatrix consisting of the first l1 rows of the
matrix (b1, . . . , bl1). Multiplying (35) to b
′′ from the left we get
b′′z′h′ + b′′zrhl1+1 = 0. (36)
But b′′z′ is a diagonal matrix with nonzero elements on the diagonal, see (ii)
(for z′ in place of z). Hence by (33) and (36) hj = 0 for every j 6= r. Now
h 6= (0, . . . , 0)t implies hr 6= 0 and hl1+1 6= 0. Therefore, (34) holds. Put
g′r = hr and gr = hl1+1. We have z
r = zrgr by (36). The lemma is proved.
Let us return to the proof of Lemma 6. Now (i)–(iii) are satisfied by Lemma 7.
The last assertions of Lemma 6 are proved similarly to the ones of Lemma 4.
Lemma 6 is proved.
7 An algorithm for solving linear systems with
coefficients from hA.
Let u = (u1, . . . , ul)
t ∈ hAl. Let all nonzero uj be homogeneous elements of the
degree −d′j+ρ for an integer ρ. Suppose that −d
j+ρ < d
′ for an integer d′ > 1.
Let b = (bi,j)1≤i≤k, 1≤j≤l be the matrix with k rows and l columns from the
statement of Lemma 6 (but now k and l are arbitrary). So deg bi,j = di−d
j < d
for all i, j. Let Z = (Z1, . . . , Zk) be unknowns. Consider the linear system
1≤i≤k
Zibi,j = uj , 1 ≤ j ≤ l, (37)
or, which is the same,
Zb = u.
Denote
ordu = min
1≤i≤k
{ordui}. (38)
The similar notations will be used for other vectors and matrices. In this section
we shall describe an algorithm for solving linear systems over hA and prove the
following theorem.
THEOREM 2 Suppose that system (37) has a solution over hA. One can
represent the set of all solutions of (37) over hA in the form
J + z∗,
where J ⊂ hAl is a hA-submodule of all the solutions of the homogeneous system
corresponding to (37) (i.e., system (37) with all uj = 0) and z
∗ is a particular
solution of (37). Moreover, the following assertions hold.
(A) One can choose z∗ such that ord z∗ ≥ ordu− ν, where ν ≥ 0 is an integer
bounded from above by (dl)2
(and depends only on d and l). The degree
deg z∗ is bounded from above by d′(dl)2
(B) There exists a system of generators of J of degrees bounded from above by
(dl)2
. The number of elements of this system of generators is bounded
from above by k(dl)2
Besides that, if all bi,j and uj do not depend on Xn (i.e., they can be represented
as sums of monomials which do not contain Xn) then z
∗ and all the generators
of the module J also satisfy this property.
PROOF Let l1 = rankr(b1, . . . , bl). Permuting equations of (37) we shall
assume without loss of generality that (b1, . . . , bl1) are linearly independent from
the right over hA. Let σ, z, e, e′, e′′ be the matrices from Lemma 6. Similarly to
the proof of Lemma 6 we shall assume without loss of generality that σ = 1.
Denote by b′ the submatrix of b consisting of the first l1 columns of b, i.e.,
b′ = (b1, . . . , bl1). By Lemma 4 there are nonzero elements q1,1, . . . , ql1,l1 of
degrees at most (32) such that e1,1q1,1 = ei,iqi,i and min{ord q1,1, ord qi,i} = 0
for all 2 ≤ i ≤ l1. Set q = diag(q1,1, . . . , ql1,l1) to be the diagonal matrix. Let
ν0 = ord e1,1q1,1. Then by Lemma 6 (iii) ord(b
′zq) ≥ ν0. Let X
0 δ = b
Then δ is a matrix with coefficients from hA and
where δ′ = diag(δ1,1, . . . , δl1,l1) is a diagonal matrix with homogeneous coef-
ficients from hA and all the elements on the diagonal are nonzero and equal,
i.e., δj,j = δ1,1 for every 1 ≤ j ≤ l1. Besides that, ord δ1,1 = 0. Fur-
ther, δ′′ = (δi,j)l1+1≤i≤k, 1≤j≤l1 . We have ord(uzq) ≥ ν0, since, otherwise,
system (37) does not have a solution. Obviously ordu ≤ ord(uzq). Denote
u′ = (u′0, . . . , u
t = X−ν00 uzq ∈
hAl. Hence ordu′ ≥ ord(u) − ν0. Consider the
linear system
Zδ = u′. (39)
LEMMA 8 Suppose that system (37) has a solution over hA. Then linear
system (39) is equivalent to (37), i.e., the sets of solutions of systems (39) and
(37) over hA coincide.
PROOF The system Zb′z = uz is equivalent to (37) by Lemma 5. System
(39) is equivalent to Zb′z = uz since the ring hA does not have zero–divisors.
The lemma is proved.
REMARK 4 Since rankr(b1, . . . , bl) = l1 and by Lemma 6 for every l1 + 1 ≤
j ≤ l there are homogeneous zj,j, z1,j , . . . , zl1,j ∈
hA such that zj,j 6= 0 and
bjzj,j +
1≤r≤l1
brzr,j = 0 and all deg zj,j, deg zr,j are bounded from above by
(2n+3)(l1+1)d. Put u
j = ujzj,j +
1≤r≤l1
urzr,j, l1+1 ≤ j ≤ l. Then system
(37) has a solution if and only if system (39) has a solution and u′j = 0 for all
l1 + 1 ≤ j ≤ l. This follows from Lemma 8 and Lemma 5. But in what follows
for our aims it is sufficient to use only Lemma 8.
REMARK 5 Assume that degXn bi,j ≤ 0 for all i, j, i.e., the elements of the
matrix b do not depend on Xn. Then by Lemma 4 and the described construction
all the elements of the matrices b, z, q, δ, δ′, δ′′ also do not depend on Xn.
By Lemma 4 and Remark 2 for every l1 + 1 ≤ j ≤ k there are homogeneous
elements gj,j , gj,i ∈
hA, 1 ≤ i ≤ l1, such that
gj,jδj,i = gj,iδ1,1, 1 ≤ i ≤ l1,
all the degrees deg gj,j , deg gj,i, 1 ≤ i ≤ l1, are bounded from above by
(2n+ 3)(l1 + 1)(max{deg δj,i : 1 ≤ i ≤ k}+ 1)
and min1≤i≤l1{ord gj,j , ord gj,i} = 0. Hence ord gj,j = 0 for every l1+1 ≤ j ≤ k
since ord δ1,1 = 0.
Denote h = δ1,1gl1+1,l1+1gl1+2,l1+2 . . . gk,k. So h ∈
hA is a nonzero homoge-
neous element and ordh = 0. Set ε = deg h. We need an analog of the Noether
normalization theorem from commutative algebra, cf. also Lemma 3.1 [7].
LEMMA 9 There is a linear automorphism of the algebra hA
α : hA → hA, α(Xi) =
1≤j≤n
(α1,i,jXj + α2,i,jDj),
α(Di) =
1≤j≤n
(α3,i,jXj + α4,i,jDj), α(X0) = X0, 1 ≤ i ≤ n,
such that all αs,i,j ∈ F , degDn α(h) = ε. If degXn h = 0 then one can choose
additionally α(Xn) = Xn, all α1,n,j = 0 for 1 ≤ j ≤ n − 1 and α3,n,j = 0 for
1 ≤ j ≤ n.
PROOF Recall that ordh = 0. Hence at first it is not difficult to construct
a linear automorphism β such that β(X0) = X0,
β(Xi) = β1,iXi + β2,iDi, β(Di) = β3,iXi + β4,iDi, 1 ≤ i ≤ n, (40)
and β(h) contains a monomial ai1,...,inD
1 , . . . , D
n with ai1,...,in 6= 0 and i1 +
. . .+in = ε, i.e., ε = degD1,...,Dn β(h). After that one can find an automorphism
γ such that γ(X0) = X0,
γ(Xi) =
1≤j≤n
γ1,i,jXj , γ(Di) =
1≤j≤n
γ4,i,jDj , 1 ≤ i ≤ n, (41)
and (γ ◦ β)(h) contains a monomial aDεn with a coefficient 0 6= a ∈ F . Put
α = γ ◦ β. We leave to prove the last assertion to the reader. The lemma is
proved.
We apply the automorphism α. In what follows to simplify the notation we
shall suppose without loss of generality that α = 1. So h contains a monomial
aDεn with a coefficient 0 6= a ∈ F , where ε = deg h. It follows from here that
degDn δ1,1 = deg δ1,1, degDn gj,j = deg gj,j , l1 + 1 ≤ j ≤ k. (42)
Let z = (z1, . . . , zk) ∈
hAk be a solution of (39). Then (42) implies that one can
uniquely represent
zj = z
jgj,j +
0≤s<deg gj,j
zj,sD
n, l1 + 1 ≤ j ≤ k, (43)
where z′j , zj,s ∈
hA, the degrees degDn zj,s ≤ 0 for all l1 + 1 ≤ j ≤ k, 0 ≤ s <
degD1 gj,j . Again by (42) one can uniquely represent
u′i = u
i δ1,1 +
0≤s<deg δ1,1
u′i,sD
n, 1 ≤ i ≤ l,
where u′′i , u
i,s ∈
hA, the degrees degDn u
i,s ≤ 0 for all 1 ≤ i ≤ l, 0 ≤ s <
degD1 gj,j . Finally, by (42) for all l1 +1 ≤ j ≤ k, 1 ≤ i ≤ l1, 0 ≤ r < degD1 gj,j,
one can uniquely represent
Drnδj,i = δj,r,iδ1,1 +
0≤r<deg δ1,1
δj,r,i,sD
where δj,r,i, δj,r,i,s ∈
hA, the degrees degDn δj,r,i,s ≤ 0 for all considered j, r, i, s.
I = { (j, r) : l1 + 1 ≤ j ≤ k&0 ≤ r < deg gj,j } ,
J = { (i, s) : 1 ≤ i ≤ l1 &1 ≤ s < deg δ1,1 } .
Therefore,
zi = −
l1+1≤j≤k
z′jgj,i −
(j,r)∈I
zj,rδj,r,i + u
i , 1 ≤ i ≤ l1, (44)
(j,r)∈I
zj,rδj,r,i,s = u
i,s, (i, s) ∈ J . (45)
Let us introduce new unknowns Zj,r, (j, r) ∈ I. By (43)–(45) system (37) is
reduced to the linear system
(j,r)∈I
Zj,rδj,r,i,s = u
i,s, (i, s) ∈ J . (46)
More precisely, any solution of system (37) is given by (43), (44) where z′j ∈
are arbitrary and zj,r is a solution of system (45) over
hA (we underline that
here this solution zj,r may depend on Dn although one can restrict oneself
by solutions zj,r which do not depend on Dn). Note that all δj,r,i,s and u
are homogeneous elements of hA and there are integers dj,r, (j, r) ∈ I, d
(i, s) ∈ J , ρ̃ such that deg δj,r,i,s = dj,r − d
i,s and deg u
i,s = −d
i,s + ρ̃ for all
(j, r) ∈ I, (i, s) ∈ J . This follows immediately from the described construction.
Now all the coefficients of system (46) do not depend on Dn. As we have
proved if the coefficients of (37) do not depend on Xn then the coefficients of
(46) also do not depend on Xn, and hence in the last case they do not depend
on Xn, Dn.
If the coefficients of (46) depend on Xn we perform an automorphism Xn 7→
Dn Dn 7→ −Xn, Xi 7→ Xi, Di 7→ Di, 1 ≤ i ≤ n − 1. Now the coefficients of
system (46) do not depend on Xn (but depend on Dn). After that we apply
our construction recursively to system (46).
The final step of the recursion is n = 0 (although in the statement of theorem
n ≥ 1, see Section 1; we are interested only in Weyl algebras). In this case
I = J = ∅. Hence using (44) for n = 0 we get the required z∗ and J for n = 0.
Thus, by the recursive assumption we get a particular solution Zj,r = z
(j, r) ∈ I, of system (46), an integer ν1 (in place of ν from assertion (A)) such
(j,r)∈I
{ord z∗j,r} ≥ min
(i,s)∈J
{ordu′i,s} − ν1, (47)
and a system of generators
( zα,j,r )(j,r)∈I , 1 ≤ α ≤ β, (48)
of the module J ′ of solutions of the homogeneous system corresponding to (46).
Notice that if the coefficients of (37) do not depend on Xn then J
′ is a module
over the homogenization F [X0, X1, . . . , Xn−1, D1, . . . , Dn−1] of the Weyl alge-
bra of X1, . . . , Xn−1, D1, . . . , Dn−1. But obviously in the last case (48) gives
also a system of generators of the hA-module J ′′ = hAJ ′ of solutions of the
homogeneous system corresponding to (46). Put
z∗i = −
(j,r)∈I
z∗j,rδj,r,i + u
i , 1 ≤ i ≤ l1,
z∗j =
0≤s<deg gj,j
z∗j,sD
n, l1 + 1 ≤ j ≤ k,
z∗ = (z∗1 , . . . , z
Then z∗ is a particular solution of (37). Put
zα,i = −
(j,r)∈I
zα,j,rδj,r,i, 1 ≤ i ≤ l1, 1 ≤ α ≤ β,
zα,j =
0≤s<deg gj,j
zα,j,sD
n, l1 + 1 ≤ j ≤ k, 1 ≤ α ≤ β,
zβ−l1+j,i = 0, l1 + 1 ≤ i, j ≤ k, i 6= j,
zβ−l1+j,j = gj,j , l1 + 1 ≤ j ≤ k,
zβ−l1+j,i = −gj,i, 1 ≤ i ≤ l1, l1 + 1 ≤ j ≤ k.
Then J =
1≤α≤β+k−l1
hA(zα,1, . . . , zα,k). Hence (zα,1, . . . , zα,k), 1 ≤ α ≤
β+k− l1, is a system of generators of the module J . By (47) and the definitions
of u′, u′′i and u
i,s we have ord z
∗ ≥ ordu− ν0 − ν1. Put ν = ν0 + ν1.
LEMMA 10 All the degrees deg δj,i, deg gj,i, deg δj,r,i, deg δj,r,i,s and ν, see
above, are bounded from above by (nld)O(1), the degrees deg u′i are bounded from
above d′ + (nld)O(1), the degrees deg u′′i , deg u
i,s are bounded from above by
d′(nld)O(1). Further, all ordu′′i , ordu
i,s are bounded from below by ordu − ν.
Finally, in system (46) the number of equations #J is bounded from above by
(nld)O(1) and the number of unknowns #I is bounded from above by k(nld)O(1).
PROOF This follows immediately from the described construction.
Let us return to the proof of Theorem 2. Applying Lemma 10 and recursively
assertions (A) and (B) for the formulas giving z∗ and J we get (A) and (B)
from the theorem. The last assertion (related to the case when all bi,j and uj
do not depend on Dn) has been already proved. The theorem is proved.
8 Proof of Theorem 1 for Weyl algebra
Let a be the matrix from Section 1. We shall suppose without loss of generality
that the vectors (ai,1, . . . , ai,l), 1 ≤ i ≤ k, are linearly independent over the field
F . We have deg ai,j < d. This implies k ≤ l
Put the matrix b = ha. Let us define the graded submodules of hI
hA(b1,1, . . . , b1,l) + . . .+
hA(bk,1, . . . , bk,l),
Jν = J0 : (X
0 ) = {z ∈
hAl : zXν0 ∈ J0}, ν ≥ 1.
We have the exact sequence of graded hA-modules
hAk → J0 → 0.
Further, Jν ⊂ Jν+1 ⊂
hI for every ν ≥ 0 and hI =
ν≥0 Jν . Since
hA is
Noetherian there is N ≥ 0 such that hI = JN . So to construct a system of
generators of hI it is sufficient to compute the least N such that hI = JN and
to find a system of generators of JN .
LEMMA 11 hI = JN for some N bounded from above by (dl)
2O(n) . There is a
system of generators b1, . . . , bs of the module JN such that s and all the degrees
deg bv, 1 ≤ v ≤ s, are bounded from above by (dl)
2O(n) .
PROOF Let us show that the module JN+1 ⊂ JN for N ≥ ν. Let u ∈ JN+1.
Consider system (37). By assertion (A) of Theorem 2 there is a particular
solution z∗ of (37) such that ord z∗ ≥ 1. Hence u ∈ X0JN ⊂ JN . The required
assertion is proved. Hence hI = Jν .
Let us replace in (37) (u1, . . . , ul) by (U1X
0 , . . . , UlX
0 ), where U1, . . . , Ul are
new unknowns. Then applying (B) from Theorem 2 to this new homogeneous
linear system with respect to all unknowns U1, . . . , Ul, Z1, . . . , Zk we get the
required estimations for the number of generators of Jν and the degrees of these
generators. The lemma is proved.
COROLLARY 1 Let (ai,1, . . . , ai,l), 1 ≤ i ≤ l, be from the beginning of the
section and the integer N be from Lemma 3. Then for every integer m ≥ 0 the
F–linear space
Am+N (a1,1, . . . , a1,l) + . . .+Am+N (ak,1, . . . , ak,l) ⊃ Im. (49)
PROOF By Lemma 3 we have (J0)m+N ⊃ X
0 (JN )m = X
hI)m. Taking
the affine parts we get (49). The corollary is proved.
Now everything is ready for the proof of Theorem 1. By Lemma 11 and
Lemma 1 there is a system of generators of the module gr(I) with degrees
bounded from above by (dl)2
. By Lemma 12 from Appendix 1 the Hilbert
function H(gr(I),m) is stable for m ≥ (dl)2
. By (10) Section 2 the Hilbert
function H(I,m) is stable for all m ≥ (dl)2
Consider the linear order < on the monomials from hAl which is induced by
the linear order < on the monomials from Al, see Section 4. Then the monomial
submodule cI ⊂ cAl is defined, see Section 4, where cA = F [X0, . . . , Xn, D1, . . . ,
Dn] is the polynomial ring. By (22) Section 4 the Hilbert function H(
cI,m) is
stable for all m ≥ (dl)2
. Hence all the coefficients of the Hilbert polynomial
of cI are bounded from above (dl)2
. Therefore, according to (31) the module
cI has a system of generators with degrees (dl)2
. This means, see Section 4,
that the module Hdt(hI) has a system of generators with degrees (dl)2
Therefore, the degrees of all the elements of the Janet basis of hI with respect
to the induced linear order < are bounded from above by (dl)2
. Hence by
Lemma 3 Section 4 the same is true for the Janet basis of the module I with
respect to the linear order < on the monomials from Al. Theorem 1 is proved
for Weyl algebra.
9 The case of algebra of differential operators
Denote by B = F (X1, . . . , Xn)[D1, . . . , Dn] the algebra of differential operators.
Recall that A ⊂ B and hence relations (1) are satisfied. Further, each element
f ∈ B can be uniquely represented in the form
j1,...,jn≥0
fj1,...,jnD
1 . . . D
where all fj1,...,jn = fj ∈ F (X1, . . . , Xn) and F (X1, . . . , Xn) is a field of rational
functions over F . Let us replace everywhere in Section 1 and Section 2 A,
X iDj , deg f = degX1,...,Xn,D1,...,Dn f , dimF M , ev,i,j , fv,i,j ∈ F , (v, i, j), (i, j),
(i′, j′), (i′′, j′′) by B, Dj , deg f = degD1,...,Dn f , dimF (X1,...,Xn) M , ev,j , fv,j ∈
F (X1, . . . , Xn), (v, j), j, j
′, j′′ respectively. Thus, we get the definition of the
Janet basis and all other objects from Section 1 for the case of the algebra of
differential operators.
We define the homogenization hB of B similarly to hA, see Section 3. Namely,
hB = F (X1, . . . , Xn)[X0, D1, . . . , Dn] given by the relations
XiXj = XjXi, DiDj = DjDi, for all i, j,
DiXi −XiDi = X0, 1 ≤ i ≤ n, XiDj = DjXi for all i 6= j.
Further, the considerations are similar to the case of the Weyl algebra A with
minor changes. We leave them to the reader. For example, Theorem 2 for
the case of the algebra of differential operators is the same. One need only to
replace everywhere in its statement A, hA and Xn by B,
hB and Dn respectively.
Thus, one can prove Theorem 1 for the case when A is an algebra of differential
operators (but now it is B). Theorem 1 is proved completely.
One can consider more general algebra of differential operators. Let F be a
field with n derivatives D1, . . . , Dn. Then Kn = F [D1, . . . , Dn] is the algebra of
differential operators and similarly one can define its homogenization hKn by
means of adding the variable X0 satisfying the relations
DiDj = DjDi, X0Di = DiX0, Dif − fDi = fDiX0
for all i, j and any element f ∈ F where fDi ∈ F denotes the result of the
application of Di to f . Following the proof of Theorem 1 one can deduce the
following statement.
REMARK 6 A similar bound to Theorem 1 holds for Kn.
Appendix 1: Degrees of generators of a graded
module over a polynomial ring and its Hilbert
function.
We give a short proof of the following result, cf. [1], [12], [6], [4].
LEMMA 12 Let I ⊂ Al be a graded submodule over the graded polynomial
ring A = F [X0, . . . , Xn], and I is given by a system of generators f1, . . . , fm of
degrees less than d. Then the Hilbert function H(Al/I,m) = dimF (A
l/I)m is
stable for m ≥ (dl)2
O(n+1)
. Further, all the coefficients of the Hilbert polynomial
of Al/I are bounded from above by (dl)2
O(n+1)
PROOF Denote M = Al/I. Let L ∈ F [X0, . . . , Xn] be a linear form in gen-
eral position. Denote byK the kernel of the morphismM → M of multiplication
to L. We have K = {z ∈ Al : Lz =
1≤i≤m fizi,& zi ∈ A}. Hence solving
a linear system over A, we get that K has a system of generators g1, . . . , gµ
with degrees bounded from above by (dl)2
O(n+1)
. Let P be an arbitrary associ-
ated prime ideal of the module M such that P 6= (X0, . . . , Xn). Since L is in
general position we have L 6∈ P. Hence P is not an associated prime ideal of
K. Therefore, KN = 0 for all sufficiently big N . So X
i gj ∈ I for sufficiently
big N and all i, j. Hence gj =
1≤i≤m yj,ifi where yj,i ∈ F (Xi)[X0, . . . , Xn].
Solving a linear system over the ring F (Xi)[X0, . . . , Xn] we get an estimation
for denominators from F [Xi] of all yj,i. Since all gj and fi are homogeneous we
can suppose without loss of generality that all the denominators are XNi . Thus,
we get an upper bound for N . Namely, N is bounded from above by (dl)2
O(n+1)
Therefore, the sequence
0 → Mm → Mm+1 → (M/LM)m+1 → 0 (51)
is exact for m ≥ (dl)2
O(n+1)
. But M/LM = Al/(I + LAl) is a module over
a polynomial ring of F [X0, . . . , Xn]/(L) ≃ F [X0, . . . , Xn−1]. Hence by the
inductive assumption the Hilbert function H(Al/(I + LAl),m) is stable for
m ≥ (dl)2
. Therefore, (51) implies that the Hilbert function H(Al/I,m) is
stable for m ≥ (dl)2
O(n+1)
Obviously for m < (dl)2
O(n+1)
the values H(Al/I,m) are bounded from
above by (dl)2
O(n+1)
. Hence by the Newton interpolation all the coefficients of
the Hilbert polynomial of Al/I are bounded from above by (dl)2
O(n+1)
. The
lemma is proved.
We need also a conversion of Lemma 12.
LEMMA 13 Let I ⊂ Al be a graded submodule over the graded polynomial
ring A = F [X0, . . . , Xn]. Assume that the Hilbert function H(A
l/I,m) =
dimF (A
l/I)m is stable for m ≥ D and all absolute values of the coefficients
of the Hilbert polynomial of the module Al/I are bounded from above by D for
some integer D > 1. Then I has a system of generators f1, . . . , fm with degrees
O(n+1)
PROOF Let us choose f1, . . . , fm to be the reduced Gröbner basis of I with
respect to an admissible linear order < on the monomials from Al, cf. the
definitions from Section 1 and Section 4. The degree of a monomial from Al is
defined similarly to Section 1 and Section 4. We shall suppose additionally that
the considered linear order is degree compatible, i.e., for any two monomials
z1, z2 if deg z1 < deg z2 then z1 < z2. For every z ∈ A the greatest monomial
Hdt(z) is defined. Further the monomial ideal Hdt(I) is generated by all Hdt(z),
z ∈ I. Now Hdt(f1), . . . ,Hdt(fm) is a minimal system of generators of Hdt(I)
and deg fi = degHdt(fi) for every 1 ≤ i ≤ m. The values of Hilbert functions
H(Al/Hdt(I),m) = H(Al/I,m) coincide for all m ≥ 0. Thus, replacing I
by Hdt(I) we shall assume in what follows in the proof that I is a monomial
module.
For every 1 ≤ i ≤ l denote by Ai ⊂ A
l the i-th direct summand of Al. Put
Ii = I ∩ Ai, 1 ≤ i ≤ l. Then I ≃ ⊕1≤i≤lIi since I is a monomial module.
Further, for every 1 ≤ α ≤ m there is 1 ≤ i ≤ l such that fα ∈ Ii. Let us
identify Ai = A. Then Ii ⊂ A is a homogeneous monomial ideal. The case
Ii = A is not excluded for some i. For the Hilbert functions we have
H(Al/I,m) =
1≤i≤l
H(A/Ii,m), m ≥ 0. (52)
If (A/Ii)D = 0 for some i then (A/Ii)m = 0 for every m ≥ D. In this case the
ideal Ii is generated by
0≤m≤D(Ii)m. Hence in (52) for the values m ≥ D one
can omit this index i in the sum from the right part. Therefore, in this case the
proof is reduced to a smaller l. So we shall assume without loss of generality
that (A/Ii)D 6= 0, 1 ≤ i ≤ l.
Further, we use the exact description of the Hilbert function of a homoge-
neous ideal, see [4] Section 7. Namely there are the unique integers bi,0 ≥ bi,1 ≥
. . . ≥ bi,n+2 = 0 such that
H(A/Ii,m) =
m+ n+ 1
1≤j≤n+1
m− bi,j + j − 1
for all sufficiently big m and
bi,0 = min{d : d ≥ bi,1 & ∀m > d (53) holds }. (54)
This description (without constants bi,0) is originated from the classical paper
[11]. The integers bi,0, . . . , bi,n+2 are called the Macaulay constants of the ideal
Ii. Besides that,
h(i,m) = H(A/Ii,m)−
m+ n+ 1
+ 1 +
1≤j≤n+1
m− bi,j + j − 1
for every m ≥ bi,1, see [4] Section 7. By Lemma 7.2 [4] for all 1 ≤ α ≤ m if
fα ∈ Ii then deg fα ≤ bi,0. Hence it is sufficient to prove that all bi,0, 1 ≤ i ≤ l,
are bounded from above by D2
O(n+1)
By (52) and (53) the coefficient at mn−j , 0 ≤ j ≤ n, of the Hilbert polyno-
mial of Al/I is
(n+ 1− j)!
1≤i≤l
bi,n+1−j +
0≤v≤j−1
1≤i≤l
(n+ 1− v)!
µj,v(bi,n+1−v), (56)
where 0 6= µj is an integer and µj,v ∈ Z[Z], 0 ≤ v ≤ j − 1, is a polynomial
with integer coefficients with deg µj,v = j − v + 1. Moreover, |µj | and absolute
values of all the coefficients of all the polynomials µj,v are bounded from above
by, say, 2O(n
2). Denote bj =
1≤i≤l bi,j , 0 ≤ j ≤ n + 2. By the condition of
the lemma all the coefficients of the Hilbert polynomial of Al/I are bounded
from above by D. Hence from (56) one can recursively estimate bn+1, bn, . . . , b1.
Namely, bn+1−j = (2
O(j+1)
, 0 ≤ j ≤ n. Hence b1 = (lD)
2O(n+1) . Notice
that bi,1 ≤ max1≤i≤l bi,1 ≤ b1 for every 1 ≤ i ≤ m.
Now let m ≥ max1≤i≤l bi,1. By (55) if h(i,m) 6= 0 for some 1 ≤ i ≤ l then
m < D, i.e., m is less than the bound D for the stabilization of the Hilbert
function of Al/I. Thus, bi,0 ≤ max{bi,1, D} by (54). Hence bi,0 is bounded
from above by (lD)2
O(n+1)
We have (A/Ii)D 6= 0 for every 1 ≤ i ≤ l. This implies H(A
l/I,D) ≥ l.
Denote by cj the j-th coefficient of the Hilbert polynomial of the module A
Now |cj |D
j ≥ l/(n + 1) for at least one j. Hence Dn+1(n + 1) ≥ l by the
condition of the lemma. This implies that l2
O(n+1)
is bounded from above by
O(n+1)
. Therefore, bi,0 is bounded from above by D
2O(n+1) . The lemma is
proved.
Appendix 2: Bound on the Gröbner basis of a
monomial module via the coefficients of its Hilbert
polynomial
Denote by Cl = Z
+ ∪ · · · ∪ Z
+ the disjoint union of l copies of the semigrid
+ = {(i1, . . . , in) : ij ≥ 0, 1 ≤ j ≤ n}. A subset of Cl which intersects
each disjoint copy of Zn+ by a semigroup closed with respect to addition of
elements from Zn+ is called an ideal of Cl. Any ideal I in Cl has a unique
finite Gröbner basis V = VI , denote T = Cl \ I. Clearly, I corresponds to a
monomial submodule in the free module (F [X1, . . . , Xn])
l. The degree of an
element u = (k; i1, . . . , in) ∈ Cl, 1 ≤ k ≤ l is defined as |u| = i1 + · · · + in.
The degree of a subset in Cl is defined as the maximum of the degrees of its
elements. The Hilbert function HT (z) equals to the number of vectors u ∈ T
such that |u| ≤ z. Then HT (z) =
0≤s≤m csz
s, z ≥ z0 for suitable z0,
integers c0, . . . , cm where the degree m ≤ n. Denote c = max0≤s≤m |cs|s! + 1.
PROPOSITION 1 (cf. [6], [12], [4]). The degree of V does not exceed
(cn)2
PROOF An s-cone we call a subset of a k-th copy of Zn+ in Cl for a certain
1 ≤ k ≤ l of the form
P = {Xj1 = i1, . . . , Xjn−s = in−s} (57)
for suitable 1 ≤ j1, . . . , jn−s ≤ n. The degree of (57) we define as |P | =
i1 + · · · + in−s (note that this definition is different from the one in [4]). By
a predessesor of (57) we mean each s-cone in the same k-th copy of Zn+ of the
{Xj1 = i1, . . . , Xjp−1 = ip−1, Xjp = ip − 1, Xjp+1 = ip+1, . . . , Xjn−s = in−s}
for some 1 ≤ p ≤ n− s, provided that ip ≥ 1. Fix an arbitrary linear order on
s-cones compatible with the relation of predessesors.
By inverse recursion on s we fill gradually T (as a union) by s-cones. For the
base we start with s = m. Assume that a current union T0 ⊂ T of m-cones is
already constructed (at the very beginning we put T0 = ∅) and an m-cone of the
form (57) with s = m is the least one (with respect to the fixed linear order on
m-cones) which is contained in T not being a subset of T0. Observe that each
predessesor of this m-cone was added to T0 at earlier steps of its construction.
Since the total number of m-cones added to T0 does not exceed cmm! < c we
deduce that the degree of every such m-cone is less than cmm! (taking into
account that the very first m-cone added to T0 has the degree 0).
For the recursive step assume that the current T0 is a union of all possible
m-cones, (m− 1)-cones,...,(s+1)-cones and perhaps, some s-cones. This can be
expressed as deg(HT −HT0) ≤ s. Again as in the base take the least s-cone of
the form (57) which is contained in T not being a subset of T0. Observe that
each predessesor of the type (58) of this s-cone is contained in an appropriate
r-cone Q, r ≥ s, such that Q was added to T0 at earlier steps of its constructing
and Q ⊂ {Xjp = ip − 1}. Hence
|Q| ≥ ip − 1. (59)
The described construction terminates when T0 = T . Denote by ts the
number of s-cones added to T0 and by ks the maximum of their degrees. We
have seen already that tm, km < c.
Now by inverse induction on s we prove that ts, ks ≤ (cn)
2O(m−s) . To this end
we introduce a relevant semilattice on cones. Let C = {Cα,β}α,β, 0 ≤ β ≤ γα
be a family of cones of the form (57) where dimCα,β = α. By an α-piece we
call an α-cone being the intersection of a few cones from C. All the pieces
constitute a semilattice L with respect to the intersection and with maximal
elements from C. We treat L also as a partially ordered set with respect to the
inclusion relation. Clearly, the depth of L is less than n. Our nearest purpose
is to bound from above the size of L. For the sake of simplifying the bound we
assume (and this will suffice for our goal in the sequel) that γα ≤ (cn)
2O(m−α)
for s ≤ α ≤ m and γα = 0 when α < s, although one could write a bound in
general in the same way. Besides that we assume that the constant in O(. . .) is
sufficiently big. In what follows all the constants in O(. . .) coincide.
LEMMA 14 Under the assumption on the numbers γα ≤ (cn)
2O(m−α) , s ≤
α ≤ m of maximal elements of all dimensions from C, the number of α-pieces in
L does not exceed (cn)2
O(m−α)+1 for s ≤ α ≤ m or (cn)2
O(m−s)(s−α+1)+1 when
α < s.
PROOF For each α-piece choose its arbitrary irredundant representation as
the intersection of the cones from C. Let δ be the minimal dimension among
these cones. Then this intersection contains at most δ−α+1 cones. Therefore,
the number of possible α-pieces does not exceed
max{α,s}≤δ≤m
(cn)2
O(m−δ)(δ−α+1),
that proves the lemma.
Now we come back to estimating ts, ks by inverse induction on s. Let in
the described above construction the current T0 is the union of all added m-
cones, (m − 1)-cones,...,s-cones. Denote this family of cones by C and consider
the corresponding semilattice L (see above). Our next purpose is to represent
T0 as a Z-linear combination of the pieces from L by means of a kind of the
inclusion-exclusion formula. We assign the coefficients of this combination by
recursion in L. As a base we assign 1 to each maximal piece, so to the elements
of C. As a recursive step, if for a certain piece P ∈ L the coefficients are already
assigned to all the pieces greater than P , we assign to P the coefficient ǫP in
such a way that the sum of the assigned coefficients to P and to all the greater
pieces equals to 1. Therefore, we get
where the sum is understood in the sense of multisets. Hence
HT0(z) =
z − |P |+ dimP
for large enough z. We recall that deg(HT −HT0) ≤ s− 1.
Now we majorate the coefficients |ǫP | by induction in the semilattice L. The
inductive hypothesis on tα ≤ (cn)
2O(m−α) , s ≤ α ≤ m and Lemma 14 imply that
dimP=λ
|ǫP | ≤ (cn)
2O(m−λ) , s− 1 ≤ λ ≤ m.
by inverse induction on λ following the assigning ǫP . In fact, one could majorate
in a similar way also
dimP=λ |ǫP | when λ < s− 1, but we don’t need it. The
inductive hypothesis on kα ≤ (cn)
2O(m−α) , s ≤ α ≤ m and (60) entail that
the coefficient of HT0(z) at the power z
α does not exceed (cn)2
O(m−α)
, s− 1 ≤
α ≤ m (actually, due to the inequality deg(HT −HT0) ≤ s− 1 the coefficients
at the powers zα for s ≤ α ≤ m are less than c). In particular, the coefficient at
the power zs−1 does not exceed (cn)2
O(m−s+1)
. Denote HT −HT0 = ηz
s−1+ · · ·.
By constructing T0 we add to it ts−1 = η(s− 1)! of (s− 1)-cones, which justifies
the inductive step for ts−1 ≤ (cn)
2O(m−s+1) .
To conduct the inductive step for ks−1 ≤ (cn)
2O(m−s+1) we observe that for
each (s − 1)-cone P added to T0 either every its predessesor is contained in a
cone of dimension at least s, or some its predessesor is an (s − 1)-cone as well.
In the former case |P | ≤ (maxs≤α≤m kα + 1)(n − s + 1) (due to (59)), while
in the latter case |P | is greater by 1 than the degree of this predessesor, hence
ks−1 ≤ (maxs≤α≤m kα + 1)(n − s + 1) + ts−1. Finally, exploit the inductive
hypothesis for km, . . . , ks, and the just obtained inequality on ts−1.
To complete the proof of the proposition it suffices to notice that for any
vector from the basis V treated as an 0-cone, each its predessesor of the type
(58) for s = 0 is contained in an appropriate r-cone, whence the degree of V
does not exceed (max0≤α≤m kα + 1)n again due to (59) (cf. above).
Acknowledgement. The authors are grateful to the Max-Planck Institut
für Mathematik, Bonn for its hospitality during the stay where the paper was
written.
References
[1] D.A. Bayer, The division algorithm and the Hilbert scheme, Ph.D. Thesis,
Harvard, 1982.
[2] A. Chistov, D. Grigoriev, Complexity of quantifier elimination in the theory
of algebraically closed fields, Lect. Notes Comput. Sci., 176 (1984), 17-31.
[3] D. Cox, J. Little, D. O’Shea, Using Algebraic Geometry, Springer, 1998.
[4] T. Dubé, The structure of polynomial ideals and Gröbner bases, SIAM J.
Comput., 19 (1990), 750–775.
[5] A. Galligo, Some algorithmical questions on ideals of differential operators,
Lect.Notes Comput.Sci., 204 (1985), 413–421.
[6] M. Giusti, Some effective problems in polynomial ideal theory, Lect. Notes
Comput. Sci, 174 (1984), 159–171.
[7] D. Grigoriev, Weak Bézout inequality for D-modules, J.Complexity, 21,
(2005), 532–542.
[8] G. Hermann Die Frage der endlich vielen Schritte in der Theorie der Poli-
nomideale, Math. Ann. 95, (1926), 736-788.
[9] M. Janet, Les modules de formes algébriques et la théorie générale des
systèmes différentiels, Annals Sci. Ecole Normale Supér., 41 (1924), 27–65.
[10] H. Li, Noncommutative Gröbner bases and filtered-graded transfer, Lect.
Notes Math., 1795, 2002.
[11] F.S. Macaulay Some properties of enumeration in the theory of modular
systems, Proc. London Math. Soc. 26 (1927), 531–555.
[12] M. Möller, T. Mora, Upper and lower bounds for the degree of Groebner
bases, Lect. Notes Comput. Sci., 174 (1984), 172–183.
[13] F. Schwarz, Janet bases for symmetry groups, Groebner bases and applica-
tions, in London Math. Society, Lecture Note Ser. 251, 221-234, Cambridge
University Press, Cambridge, 1998.
[14] C. Yap, A new lower bound construction for commutative Thue systems,
with applications, J. Symb. Comput., 12 (1991), 1–27.
	Definition of the Janet basis
	The graded module corresponding to a D–module 
	Homogenization of the Weyl algebra
	The Janet bases of a module and of its homogenization
	Bound on the kernel of a matrix over the homogenized Weyl algebra
	Transforming a matrix with coefficients from h-A to the trapezoidal form
	An algorithm for solving linear systems with coefficients from h-A.
	Proof of Theorem ?? for Weyl algebra
	The case of algebra of differential operators
