arXiv:1705.02776v1 [cs.SC] 8 May 2017

Dimension-Dependent Upper Bounds for Grobner
Bases
Amir Hashemi

Werner M. Seiler

Department of Mathematical Sciences
Isfahan University of Technology
Isfahan, 84156-83111, Iran
School of Mathematics, Institute for Research in
Fundamental Sciences (IPM)
Tehran, 19395-5746, Iran

- Mathematik, Universitat
- Kassel,
Institut fur
Heinrich-Plett-Straıe 40, 34132 Kassel,
Germany

seiler@mathematik.uni-kassel.de

Amir.Hashemi@cc.iut.ac.ir

ABSTRACT
We improve certain degree bounds for Gröbner bases of polynomial ideals in generic position. We work exclusively in deterministically verifiable and achievable generic positions of
a combinatorial nature, namely either strongly stable position or quasi stable position. Furthermore, we exhibit
new dimension- (and depth-)dependent upper bounds for
the Castelnuovo-Mumford regularity and the degrees of the
elements of the reduced Gröbner basis (w.r.t. the degree reverse lexicographical ordering) of a homogeneous ideal in
these positions.

Categories and Subject Descriptors
F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

Keywords
Polynomial ideals, Gröbner bases, Pommaret bases, generic
positions, stability, degree, dimension, depth, CastelnuovoMumford regularity.

1.

INTRODUCTION

Gröbner bases, introduced by Bruno Buchberger in his
Ph.D. thesis (see e.g. [6, 7]), have become a powerful tool
for constructive problems in polynomial ideal theory and related domains. For practical applications, in particular, the
implementation in computer algebra systems, it is important
to establish upper bounds for the complexity of determining
a Gröbner basis for a given homogeneous polynomial ideal.
Using Lazard’s algorithm [23], a good measure to estimate
such a bound, is an upper bound for the degree of the intermediate polynomials during the Gröbner basis computation.
If the input ideal is not homogeneous, the maximal degree
of the output Gröbner basis is not sufficient for this estimation. On the other hand, Möller and Mora [30] showed that
to discuss degree bounds for Gröbner bases, one can restrict

Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
ISSAC’17, July 25-28, 2017, Kaiserslautern, Germany.
Copyright 2012 ACM X-XXXXX-XX-X/XX/XX ...$5.00.

to homogeneous ideals. Thus upper bounds for the degrees
of the elements of Gröbner bases of homogeneous ideals, allow us to estimate the complexity of computing Gröbner
bases in general.
Let us review some of the existing results in this direction. Let P be the polynomial ring [x1 , . . . , xn ] where
is of characteristic zero and I ⊂ P be an ideal generated by homogeneous polynomials of degree at most d with
dim(I) = D. The first doubly exponential upper bounds
were proven by Bayer, Möller, Mora and Giusti, see [31,
Chapter 38] for a comprehensive review of this topic. Based
on results due to Bayer [2] and Galligo [14, 15], Möller and
n+1
Mora [30] provided the upper bound (2d)(2n+2)
for any
Gröbner basis of I. They also proved that this doubly exponential behavior cannot be improved. Simultaneously,
n−1
for the degree
Giusti [16] showed the upper bound (2d)2
of the reduced Gröbner basis (w.r.t. the degree reverse lexicographic order) of I when the ideal is in generic position.
Then, using a self-contained and constructive combinatorial argument, Dubé [10] proved the so far sharpest degree
n−1
n
bound 2(d2 /2 + d)2
∼ 2d2 .
In 2005, Caviglia and Sbarra [8] studied upper bounds for
the Castelnuovo-Mumford regularity of homogeneous ideals.
Analyzing Giusti’s proof, they gave a simple proof of the
n−2
upper bound (2d)2
for the degree reverse lexicographic
Gröbner basis of an ideal I in generic position (they also
showed that this bound holds independent of the characteristic of ). Finally, Mayr and Ritscher [29], by following the
tracks of Dubé [10], obtained the dimension-dependent upD−1
per bound 2(1/2dn−D + d)2
for any reduced Gröbner basis of I. It is worth while remarking
that there are also lower
m
bounds for the complexity: d2 with m = n/10 − O(1) from
m
the work of Mayr and Meyer [28] and d2 where m ∼ n/2
due to Yap [37].
In this article, we will first improve Giusti’s bound by
showing that if I is in strongly stable position and D > 1,
D−1
then 2d(n−D)2
is a simultaneous upper bound for the
Castelnuovo-Mumford regularity of I and for the maximal
degree of the elements of the Gröbner basis of I (with respect to the degree reverse lexicographic order). Furthermore, we will sharpen the bound of Caviglia-Sbarra to (dn−D +
D−1
(n−D)(d−1))2
. We will see that neither of these bounds
is always greater than the other. Finally, we will show that,
if I is in quasi stable position and D ≤ 1, Giusti’s bound
may be replaced by nd − n + 1 (this result was already obtained by Lazard [23] when the ideal is in generic position).

k

k

k

In the recent work [21], we showed how many variants of
stable positions – including quasi stable and strongly stable
position – can be achieved via linear coordinate transformations constructed with a deterministic algorithm.
The article is organized as follows. In the next section, we
give basic notations and definitions. In Sections 4, 5 and 6
we improve the degree bounds provided by Giusti, CavigliaSbarra and Lazard, respectively.

Lemma 2.2. ([25, Prop. 4.1, page 108]) There exist homogeneous polynomials g1 , . . . , gn−D ∈ P such that the following conditions hold:
(1) deg(gi ) = di for each i,
(2) gi ≡ λi fi mod hfi+1 , . . . , fk i for some 0 6= λi ∈
i = 1, . . . , n − D,

k for

(3) g1 , . . . , gn−D is regular sequence in P.

2.

PRELIMINARIES

Throughout this article, we keep the following notations.
Let P = [x1 , . . . , xn ] be the polynomial ring (where is
of characteristic zero). A power product of the variables
x1 , . . . , xn is called term and
denotes the monoid of all
terms in P. We consider non-zero homogeneous polynomials f1 , . . . , fk ∈ P and the ideal I = hf1 , . . . , fk i generated
by them. We assume that fi is of degree di and that the
numbering is such that d1 ≥ d2 ≥ · · · ≥ dk > 0. We also
set d = d1 . Furthermore, we denote by R = P/I the corresponding factor ring and by D its dimension. Finally, we
use throughout the degree reverse lexicographic order with
xn ≺ · · · ≺ x1 .
The leading term of a polynomial f ∈ P, denoted by
LT(f ), is the greatest term (with respect to ≺) appearing in f and its coefficient is the leading coefficient of f
and we denote it by LC(f ). The leading monomial of f
is the product LM(f ) = LC(f )LT(f ). The leading ideal
of I is defined as LT(I) = hLT(f ) | f ∈ Ii. For the
finite set F = {f1 , . . . , fk } ⊂ P, LT(F ) denotes the set
{LT(f1 ), . . . , LT(fk )}. A finite subset G ⊂ I is called a
Gröbner basis of I w.r.t. ≺, if LT(I) = hLT(G)i. We refer
to [1] for more details on Gröbner bases.
Given a graded P-module X and a positive integer s, we
denote by Xs the set of all homogeneous elements of X of
degree s. To define the Hilbert regularity of an ideal, recall that the Hilbert function of I is defined by HFI (t) =
dimk (Rt ); the dimension of Rt as a -linear space. From
a certain degree on, this function of t is equal to a polynomial in t, called Hilbert polynomial, and denoted by HPI
(see [9] for more details on this topic). The Hilbert regularity of I is hilb(I) = min{m | ∀t ≥ m, HFI (t) = HPI (t)}.
Finally, recall
series of I is the power series
P that the Hilbert
s
HSI (t) = ∞
HF
(s)t
.
I
s=0

k

k

T

k

Proposition 2.1. There exists a univariate polynomial
p(t) with p(1) 6= 0 such that HSI (t) = p(t)/(1 − t)D . Furthermore, hilb(I) = max{0, deg(p) − d + 1}.

Definition 2.3. The depth of the homogeneous ideal I
is defined as the maximal integer λ such that there exists a
regular sequence of linear forms y1 , . . . , yλ on P/I.
Definition 2.4. The homogeneous ideal I is m-regular,
if its minimal graded free resolution is of the form
M
0 −→
P(erj ) −→ · · ·
j

· · · −→

M

P(e1j ) −→

j

M

P(e0j ) −→ I −→ 0

j

with eij − i ≤ m for each i, j. The Castelnuovo-Mumford
regularity of I is the smallest m such that I is m-regular;
we denote it by reg(I).
For more details on the regularity, we refer to [32, 12, 3,
5]. It is well-known that in generic coordinates reg(I) is
an upper bound for the degree of the Gröbner basis w.r.t.
the degree reverse lexicographic order. This upper bound is
sharp, if the characteristic of is zero (see [3]). A good measure to estimate the complexity of the computation of the
Gröbner basis of I is the maximal degree of the polynomials
which appear in this computation (see [22, 23, 16]).

k

Definition 2.5. We denote by deg(I, ≺) the maximal degree of the elements of the reduced Gröbner basis of the nonzero homogeneous ideal I w.r.t. the term order ≺.
Theorem 2.6. ([25, Prop. 4.8, page 117]) If I is zerodimensional, then deg(I, ≺) ≤ d1 + · · · + dn − n + 1.
We conclude this section with a brief review of the theory
of Pommaret bases. Suppose that f ∈ P and LT(f ) = xα
with α = (α1 , . . . , αn ). We call max {i | αi 6= 0} the class
of f , denoted by cls(f ). Then the multiplicative variables
of f are XP (f ) = {xcls(f ) , . . . , xn }. Furthermore, xβ is a
Pommaret divisor of xα , written xβ |P xα , if xβ | xα and
xα−β ∈ [xcls(f ) , . . . , xn ].

k

For a proof of this result, we refer to [13, Thm. 7, page
Definition 2.7. Let H ⊂ I be a finite set such that no
130]. It follows immediately from Macaulay’s theorem that
leading term of an element of H is a Pommaret divisor of
the Hilbert function of I is the same as that of LT(I) and
the leading term of another element. Then H is called a
this provides an effective method to compute it using Gröbner
Pommaret basis of I for ≺, if
bases, see e.g. [18].
M
Let us state some auxiliary results on regular sequences.
[XP (h)] · h.
(1)
I=
Recall that a sequence of polynomials f1 , . . . , fk ∈ P is
h∈H
called regular if fi is a non-zero divisor on the ring P/hf1 , . . . , fi−1 i
for i = 2, . . . , k. This is equivalent to the condition that fi
One can easily show that any Pommaret basis is a (gendoes not belong to any associated prime of hf1 , . . . , fi−1 i. It
erally non-reduced) Gröbner basis of the ideal it generates.
can be shown that theQHilbert series of a regular sequence
The main difference between Gröbner and Pommaret bases
f1 , . . . , fk is equal to ki=1 (1 − tdi )/(1 − tn ), see e.g. [25].
consists of the fact that by (1) any polynomial f ∈ I has a
The converse of this result is also true, see [13, Exercise 7,
unique involutive standard representation. If an ideal I pospage 137]. In addition, these conditions are equivalent to
sesses a Pommaret basis H, then reg(I) equals the maximal
the statement that D = n − k.
degree of an element of H, cf. [34, Thm. 9.2]. The main

k

drawback of Pommaret bases is however that they do not
always exist. Indeed, a given ideal possesses a finite Pommaret basis, if and only if the ideal is in quasi stable position
– see [34, Prop 4.4].
Definition 2.8. A monomial ideal J in P is called quasi
stable, if for any term m ∈ J and all integers i, j, s with
1 ≤ j < i ≤ n and s > 0 such that xsi | m, there exists an
exponent t ≥ 0 such that xtj m/xsi ∈ J . A homogeneous ideal
I is in quasi stable position, if LT(I) is quasi stable.
In the sequel, we will use the following notations: given an
ideal I in quasi stable position, we write H = {h1 , . . . , hs }
for its Pommaret basis. Furthermore, for each i we set mi =
LT(hi ) and it is then easy to see that {m1 , . . . , ms } forms a
Pommaret basis of LT(I).
Remark 2.9. Since any linear change of variables is a
of P preserving the degree, it follows trivially that the dimensions over of the homogeneous
components of a homogeneous ideal I or of its factor ring R
remain invariant. Hence the Hilbert function and therefore
also the Hilbert series, the Hilbert polynomial and the Hilbert
regularity of I do not change. The same is obviously true
for the Castelnuovo-Mumford regularity. In addition, due to
the special form of the Hilbert series of the ideal generated
by a regular sequence, we conclude that any regular sequence
remains regular after a linear change of variables and hence
the depth is invariant, too. Finally, we note that almost all
linear changes of variables transform a given homogeneous
ideal into quasi stable position (which is thus a generic position) [34]. It follows that to study any of the mentioned
invariants of I, w.l.o.g. we may assume that I is in quasi
stable position.

k-linear automorphism

3.

k

IMPROVING GIUSTI’S UPPER BOUND
n−1

In 1984, Giusti [16] established the upper bound (2d)2
for deg(I, ≺) in the case that the coordinates are in generic
position. The key point of Giusti’s proof is the use of the
combinatorial structure of the generic initial ideal in characteristic zero. Later on, Mora [31, Ch. 38], by a deeper analyD−λ
sis of Giusti’s proof, improved this bound to (d+1)(n−D)2
where λ is the depth of I. In this section, we improve Mora’s
bound by following his general approach and correcting some
flaws in his method. Our presentation seems to be simpler
than the ones by Mora and Giusti.
We first note that for a given ideal in quasi stable position,
we are able to reduce the number of variables by the depth
of the ideal to obtain a sharper bound for deg(I, ≺). A novel
proof à la Pommaret of this result is given below.
Proposition 3.1. Suppose that U (n, d, D) is a function
depending in n, d and D so that deg(I, ≺) ≤ U (n, d, D) for
any ideal I which is in quasi stable position and is generated by homogeneous polynomials of degree at most d in
n variables. Then, deg(I, ≺) ≤ U (n − λ, d, D − λ) where
depth(I) = λ.
Proof. Let t be the maximal class of the elements in H.
It is shown in [34, Prop 2.20] that in quasi-stable position
the variables xt+1 , . . . , xn define a regular sequence on R and
that thus λ = n − t (note that this reference distinguishes
between depth(I) and depth(R) with the two related by

depth(R) = depth(I) − 1; what we call here depth(I) corresponds to depth(R) in [34]). By definition of t, no leading
term of an element of H is divisible by any of these variables. Thus H̃ = H|xt+1 =···=xn =0 is the Pommaret basis
of the ideal Ĩ = I|xt+1 =···=xn =0 in [x1 , . . . , xt ] and hence
deg(I, ≺) = deg(Ĩ, ≺). This entails our claim.

k

Corollary 3.2. As a similar statement to Prop. 3.1,
suppose that R(n, d, D) is a function depending in n, d and
D such that reg(I) ≤ R(n, d, D). Then, reg(I) ≤ R(n −
λ, d, D − λ).
Proof. This claim follows by the same argument as in
the proof of Prop. 3.1 and using the facts that for each f in
the Pommaret bases H the corresponding element f˜ ∈ H̃ has
the same degree as f and in quasi stable position reg(I) =
reg(Ĩ) is given by the maximal degree of the elements of H
and H̃.
To state the refined version of Giusti’s bound, we need to
recall the crystallisation principle. Let A = (aij ) ∈ GL(n, )
be an n × n invertible matrix. By A.I we mean the ideal
generated
by the polynomials
A.f with f ∈ I where A.f =
P
Pn
f( n
a
x
,
.
.
.
,
a
x
).
The following fundamental
i1
i
in
i
i=1
i=1
theorem is due to Galligo [14].

k

Theorem 3.3. There exists a non-empty Zariski open subset U ⊂ GL(n, ) such that LT(A.I) = LT(A′ .I) for all
matrices A, A′ ∈ U.

k

Definition 3.4. The monomial ideal LT(A.I) with A ∈
U and U as given in Theorem 3.3 is called the generic initial
ideal of I (w.r.t. ≺) and is denoted by gin(I).

N

Suppose that I = hf1 , . . . , fk i and that for some s ∈
we have deg(fi ) ≤ s for all i and gin(I) has no minimal
generator in degree s + 1. Then, the crystallisation principle
(CP) states that for each m in the generating set of gin(I)
we have deg(m) ≤ s, see [17, Prop 2.28]. Note that this
principle holds only in characteristic zero and it has been
proven only for generic initial ideals and for lexicographic
ideals (see [17, Thm. 3.8]).
Giusti’s proof consists in applying this property along
with an induction on the number of variables. One crucial fact in this direction is that CP also holds for a generic
initial ideal modulo the last variable. Below, we will show
that both properties remain true for arbitrary strongly stable
ideals.
Definition 3.5. A monomial ideal J is called strongly
stable, if for any term m ∈ J we have xj m/xi ∈ J for all
i and j such that j < i and xi divides m. A homogeneous
ideal I is in strongly stable position, if LT(I) is strongly
stable.
Proposition 3.6. Let I be in strongly stable position.
Then, CP holds for LT(I).
Proof. The following arguments are inspired by [31, page
728]. Let us consider an integer s ≥ d. Suppose that we are
computing a Gröbner basis of I using Buchberger’s algorithm and by applying the normal strategy. In addition, assume that we have already computed the set G = {g1 , . . . gt }
up to degree s (this set will be enlarged to a Gröbner basis
of I), and there is no new polynomial of degree s + 1 to be

added into G. Note that we have chosen s ≥ d to be sure
that G generates I. To prove the assertion, it suffices to
show that G is a Göbner basis of I.
We introduce the set Ms = hLT(G)is ∩ . We now
β
αn
1
claim that for each pair of terms xα = xα
1 · · · xn 6= x =
β1
α
β
βn
x1 · · · xn in it either deg(lcm(x , x )) = s + 1 or there
exists a further term xγ ∈ Ms \ {xα , xβ } such that

T

• xγ | lcm(xα , xβ ),
• deg(lcm(xγ , xα )) < deg(lcm(xα , xβ )),
• deg(lcm(xγ , xβ )) < deg(lcm(xα , xβ )).
If this claim is true, then Buchberger’s second criterion implies that it suffices to consider those pairs {gi , gj } with
deg(lcm(LT(gi ), LT(gj ))) = s + 1. If for each such pair
the corresponding S-polynomial reduces to zero, then G is
a Gröbner basis and we are done. Otherwise, there exists
a new generator of degree s + 1 contradicting the made assumptions.
For proving the made claim, it suffices to show that, if
deg(lcm(xα , xβ )) > s + 1, then there exists a term xγ ∈
Ms \ {xα , xβ } satisfying the above conditions. Let j be an
integer such that αj 6= βj and αj+1 = βj+1 , . . . , αn = βn .
W.l.o.g., we may assume that αj > βj . Since xα and xβ
have the same degree, there is an index i < j such that
βi > αi . The strongly stable position of I implies that Ms
is a strongly stable set. Therefore the term xγ = xi xα /xj
satisfies xγ ∈ Ms \ {xα , xβ } and xγ | lcm(xα , xβ ). Furthermore, deg(lcm(xγ , xα )) = s + 1 < deg(lcm(xα , xβ )) and
deg(lcm(xγ , xβ )) = deg(lcm(xα , xβ )) − 1.
Example 3.7. One should note that strong stability of the
leading term ideal does not imply that it is the generic initial
ideal, as the following example due to Green [17] shows: I =
hx1 x3 , x1 x2 + x22 , x21 i ⊂ [x1 , x2 , x3 ]. Its leading term ideal
LT(I) = hx1 x3 , x1 x2 , x21 , x22 x3 , x32 i is strongly stable, but we
find gin(I) = hx22 , x1 x2 , x21 , x1 x23 i 6= LT(I). Nevertheless, it
is clear that both LT(I) and gin(I) satisfy CP.

k

As a consequence of the proof of this proposition, we can
infer a generalization of CP.
Corollary 3.8. Suppose we know in advance that I is
in strongly stable position. Let us fix an integer t (not necessarily greater than d). Suppose that we are computing a
Gröbner basis for I using Buchberger’s algorithm and applying the normal strategy. Assume that we have treated
all S-polynomials of degree at most t and Gt is the set of
all polynomials computed so far. If all S-polynomials of degree t + 1 reduce to zero, then any critical pair {f, g} with
max{deg(f ), deg(g)} ≤ t is superfluous. In particular, Gt is
a Gröbner basis for hI≤t i.
In the sequel, for an index i we denote by Ii the ideal
I|xi =···=xn =0 ⊂ [x1 , . . . , xi−1 ]. Since we assume that ≺ is
the degree reverse lexicographic term order, strongly stable
position of I entails that Ii is in strongly stable position,
too, for any index i. The essence of Giusti’s approach consists of finding, by repeated evaluation, relations between
deg(I, ≺) and deg(Ii , ≺) for i = n, . . . , n − D + 1. For this
purpose, we introduce some further notations for an ideal
I in strongly stable position. We denote by N (I) the set
of all terms m ∈
/ LT(I). If dim(I) = 0, then we define

k

F (I) = N (I). Otherwise we set F (I) = {τ xan ∈ N (I) | τ ∈
F (In ) and deg(τ xan ) < deg(I, ≺)}. Since I is in strongly
stable position, N (I) is strongly stable for the reverse ordering of the variables. More precisely, if xα ∈ N (I) with
αi > 0, then we claim that xj xα /xi ∈ N (I) for any j > i.
Indeed, otherwise it belonged to LT(I) and thus – since
LT(I) is strongly stable – xα ∈ LT(I) which is a contradiction.
Lemma 3.9. Suppose that I is in strongly stable position.
Then the following statements hold.
(a) deg(I, ≺) ≤ max{d, deg(In , ≺)} + #F (In ),
2
(b) #F (I) ≤ max{d, #F (In )} .
(Here #X denotes the cardinality of a finite set X.)
Proof. (a) Let G be the reduced Gröbner basis of I
for ≺. Because of our use of the degree reverse lexicographic term order, we easily see that G|xn =0 is the reduced
Gröbner basis of In for ≺. Let G′ ⊂ G be the subset of
all polynomials in G of maximal degree. We distinguish
two cases. If LT(G′ ) ∩ [x1 , . . . , xn−1 ] 6= ∅, then obviously
deg (I, ≺) = deg(In , ≺) and the assertion is proved.
Otherwise, CP (applicable by Prop. 3.6) implies that for
each degree max {d, deg(In , ≺)} < i ≤ deg(I, ≺) there exists a polynomial gi ∈ G with deg(gi ) = i (note that if
deg(I, ≺) = d then (a) holds and we are done). Thus,
we can write LT(gi ) in the form xani τi with ai > 0 and
τi ∈ [x1 , . . . , xn−1 ]. We claim that τi ∈ F (In ). Writαi
α
ing τi = xi1i1 · · · xik k where i1 < · · · < ik , we may conclude by the assumed reducedness of G that τi ∈
/ LT(I)
αi +ai
αi
∈
and by the strong stability of LT(I) that xi1 1 · · · xik k
LT(I). Hence there exists an integer a > 0 such that
αi +a
αi +a−1
α
α
∈ LT(I).
∈
/ LT(I) and xi1i1 · · · xik k
xi1i1 · · · xik k
It follows that there exists a generator g ∈ G ∩ In such
βi
βi
that its leading term LT(g) = xi1 1 · · · xik k divides the latter term. We must have βℓ ≤ αℓ for each ℓ < ik and
βik = αik + a by definition of a. Furthermore, the strong
stability of LT(I) implies that deg(g) > deg(τi ), as otherwise another generator g ′ ∈ G existed with LT(g ′ ) | τi . Thus
αi
deg(τi ) < deg(In , ≺). If we write τi = τ̄i xik k , then there
only remains to show that τ̄i ∈ F (Iik ), as τi ∈ N (In ) is
a trivial consequence of τi ∈ N (I). If dim(Iik ) = 0, this
follows immediately from F (Iik ) = N (Iik ). Otherwise we
repeated the same arguments as above.
Thus for each i with max{d, deg(In , ≺)} < i ≤ deg(I, ≺)
there exists a generator gi ∈ G such that LT(gi ) = xani τi and
τi ∈ F (In ). Since G is reduced, the terms τi are pairwise
different. Hence deg(I, ≺) − max {d, deg(In , ≺)} ≤ #F (In )
and this proves (a).
To show (b), we introduce for each degree δ ∈ the subset
Fδ (I) = {xδn τ | xδn τ ∈ F (I)}. By definition, xδn τ ∈ Fδ (I)
implies τ ∈ F (In ) and thus #Fδ (I) ≤ #F (In ). Since we
used in the proof of (a) CP, the claims proven there are
true only for polynomials of degree at least d. Thus in
the sequel we shall replace #F (In ) by max{d, #F (In )}.
We observe that the maximal δ such that xδn τ ∈ F (I) is
max{d, #F (In )} and thus

k

k

N

max{d,#F (In )}−1

#F (I) ≤

X

max{d, #F (In )}

δ=0

which immediately yields the inequality in (b).

Remark 3.10. Mora [31, Thm. 38.2.7] presented another
version of this lemma. Instead of our set F (I), he defined
F̃ (I) = {τ xan ∈ N (I) | τ ∈ N (In ), deg(τ xan ) < deg (I, ≺)}
which differs only in the condition on τ . Assuming the equality F̃0 (I) = F̃ (In ) where F̃0 (I) contains the elements of
F̃ (I) with a = 0, he proved the following two properties:
(a) deg(I, ≺) ≤ deg(In , ≺) + #F̃ (In ),
2
(b) #F̃ (I) ≤ #F̃ (In ) .

and thus the first inequality.
For the second inequality, Thm. 5.3, which will be proven
in the last section, provides the starting point for the induction, as it immediately implies our claim for D ≤ 1. For
D ≥ 2, we obviously have (n − 1 − (D − 1) + 1)(d − 1) + 1 ≤
D−1
D−2
D−1
d(n−D)2
and 2d(n−1−(D−1))2
≤ d(n−1−(D−1))2
. We
can thus rewrite the induction hypothesis as

deg (In , ≺) ≤ max (n − 1 − (D − 1) + 1)(d − 1) + 1,
D−2

2d(n−1−(D−1))2

However, in general these assertions are not correct – not
even for an ideal in generic position. Indeed, in general we
have only F̃ (In ) ⊆ F̃0 (I) and if dim(I) > 0 and deg (I1 ≺) <
deg (I, ≺) then equality does not hold. As a concrete ex[x1 , x2 ]. We perform
ample consider I = hx21 , x11
2 x1 i ⊂
a generic linear change x1 = ay1 + by2 and x2 = cy1 +
dy2 with parameters a, b, c, d ∈ . The leading term ideal
of the new ideal is then hy12 , y211 y1 i. This show that I =
gin(I) and therefore the original coordinates for I are already generic. We have I2 = hx21 i, F (I2 ) = {1, x1 } and
deg(I2 , ≺) = 2. Furthermore, we have F̃ (I) = {x11
2 } ∪
{xi2 , xi2 x1 | i = 0, . . . , 10} and #F̃ (I) = 23. Thus, 12 =
deg(I, ≺) 6≤ deg(In , ≺) + #F̃ (In ) = 2 + 2 = 4 and 23 =
#F̃ (I) 6≤ (#F̃ (In ))2 = 4.
In the case that I is a zero-dimensional ideal, we can
derive explicit upper bounds for deg(I, ≺) and #F (I) using
the following well-known lemma. We include an elementary
proof for the sake of completeness.
Lemma 3.11. Let I be a zero-dimensional ideal. Then
(a) deg(I, ≺) ≤ d1 + · · · + dn − n + 1,
(b) #F (I) ≤ d1 · · · dn .
Proof. (a) was already proven in Thm. 2.6. We present
now an elementary proof for (b). The assumption dim(I) =
0 implies that #F (I) = dimk (P/I) and this dimension is
equal to the sum of the coefficients of the Hilbert series
of I (which is of course a polynomial here). We may assume w.l.o.g. that the first n generators f1 , . . . , fn form a
regular sequence (Lem. 2.2). Thus
of
Q the Hilbertdiseries
−1
I ′ = hf1 , . . . , fn i is HSI ′ (t) = n
) and
i=1 (1 + · · · + t
dimk (P/I ′ ) is at most HSI ′ (1) = d1 · · · dn . We obviously
have dimk (P/I) ≤ dimk (P/I ′ ) and this proves the assertion.
We state now the main result of this section.
Theorem 3.12. If the ideal I is in strongly stable posiD
tion, then #F (I) ≤ d(n−D)2 and

D−1
deg(I, ≺) ≤ max (n − D + 1)(d − 1) + 1, 2d(n−D)2
.
Proof. We proceed by induction over D = dim(I). In
this proof without loss of generality, we may assume that
d ≥ 2. If D = 0, the assertions follow immediately from
Lem. 3.11. For D > 0, we exploit that then dim(I) =
dim(In ) + 1 and that we may consider In as an ideal in
[x1 , . . . , xn−1 ]. Lem. 3.9 now entails that

k

#F (I) ≤ max{d, #F (In )}2
D−1

≤ d(n−1−(D−1))2

2

D

= d(n−D)2

.

Again by Lem. 3.9, we can also estimate
deg(I, ≺) ≤ max {d, deg(In , ≺)} + #F (In )
D−1

≤ d(n−D)2

k

k

D−1

≤ d(n−D)2

D−1

+ d(n−1−(D−1))2

D−1

= 2d(n−D)2

proving the second assertion.
Example 3.13. Let us consider the values n = 2, d = 2
and D = 0. The above theorem states deg(I, ≺) ≤ 22 = 4.
Consider the ideal I = hx21 , x1 x2 + x22 i. By performing
a generic linear change of coordinates, we get gin(I) =
hx2 x1 , x21 , x32 i. Therefore #F (I) = 4 ≤ 4 and deg (I, ≺) =
3 ≤ 4 confirming the accuracy of the presented upper bounds.
It should be noted that for such a zero-dimensional ideal
Theorem 2.6 provides the best upper bound for deg (I, ≺),
namely d1 + · · · + dn − n + 1 which is equal to the exact value
3 for this example.
Using Prop. 3.1, we obtain even sharper bounds depending on both the dimension and the depth of I. We continue
to write dim(I) = D and depth(I) = λ. It is well-known
that we always have D ≥ λ (a simple proof using Pommaret
bases can be found in [34] after Prop. 3.19). If D = λ,
then R is Cohen-Macaulay. In this case, a nearly optimal
upper bound for deg(I, ≺) exists. Recall that a homogeneous ideal I ⊂ P is in Nœther position, if the ring extension [xn−D+1 , . . . , xn ] ֒→ P/I is integral. Alternatively,
Nœther position can be defined combinatorially as a weakened version of quasi stable position (see [21, Thm. 4.4]).

k

Theorem 3.14. ([25, Prop. 4.8, page 117]) Let R be a
Cohen-Macaulay ring with I in Nœther position. Then,
deg(I, ≺) ≤ d1 + · · · + dn−D − (n − D) + 1.
For the rest of this section, we thus assume that R is not
Cohen-Macaulay, i. e. that D > λ.
Corollary 3.15. If I is in strongly stable position and
D−λ−1
D > 1, then #F (I) ≤ d(n−D)2
and deg(I, ≺) ≤
D−λ−1
2d(n−D)2
.
The maximal degree of an element of the Pommaret basis
of an ideal in quasi stable position equals the CastelnuovoMumford regularity [34, Cor. 9.5]. If the ideal is even in
stable position, then the Pommaret basis coincides with the
reduced Gröbner basis [26, Thm. 2.15]. These considerations
imply now immediately the following two results.
Corollary 3.16. If the ideal I is in strongly stable poD−λ−1
sition and D > 1, then reg(I) ≤ 2d(n−D)2
.
Corollary 3.17. Let the ideal I be in quasi stable position, H its Pommaret basis and D > 1. If we write deg(H)
for the maximal degree of an element of H, then deg (I, ≺) ≤
D−λ−1
deg (H) ≤ 2d(n−D)2
.

4.

IMPROVING THE UPPER BOUND OF
CAVIGLIA-SBARRA

In 2005, Caviglia and Sbarra [8] gave a simple proof for
n−2
the upper bound (2d)2
for deg(I, ≺) when the coordinates are in generic position by analyzing Giusti’s proof and
exploiting some properties of quasi stable ideals. We will
now improve this bound to a dimension dependent bound.
As a by-product, we will show that the notion of genericity
that one needs here is strongly stable position.
We begin with a quick review of the approach of Caviglia
and Sbarra [8]. For any monomial ideal J ⊂ P let G(J )
be its unique minimal generating set. We write degi (J ) =
max{degi (u) | u ∈ G(J )} where degi denotes the degree in
the variable xi . Slightly changing our previous notation, we
now denote by Ji the ideal J |xi+1 =···=xn =0 ⊂ [x1 , . . . , xi ].
It follows immediately from the definition of a quasi stable
ideal that degi (Ji ) = degi (J ). We note that two distinct
terms in G(J ) must differ already in the first n − 1 variables
Qn−1 because of the minimality of G(J ). Hence #G(J ) ≤
i=1 (degi (J ) + 1).
Assume that I is in quasi stable position and I satisfies
CP w.r.t. d. CP implies that deg(I,
≺)−d+1 ≤ #G(LT(I))
Q
and hence deg(I, ≺) ≤ d−1+ n−1
(deg
i (LT(I))+1). Quasi
i=1
stability of LT(I) implies thatQdegi (LT(I)) = deg(Ii , ≺) and
thereby deg(I, ≺) ≤ d − 1 + n−1
i=1 (deg(Ii , ≺) + 1).
Set
B
=
d
and
for
i
≥
2
recursively Bi = d − 1 +
1
Qi−1
j=1 (Bj + 1). If we assume that for each index 1 ≤ i < n
the reduced ideal Ii satisfies CP w.r.t. d, then by the considerations above deg(Ii , ≺) ≤ Bi . In particular, B2 = 2d
and deg(I, ≺) ≤ Bn . One easily sees that the Bi satisfy the
recursion relation Bi = d − 1 + (Bi−1 + 1)(Bi−1 − d + 1) =
2
Bi−1
− (d − 2)Bi−1 for all i ≥ 2. Since we may suppose that
2
d ≥ 2, we have Bi ≤ Bi−1
. Thus, for all i ≥ 2 we have
n−2
i−2
Bi ≤ (2d)2
and therefore Bn = deg(I, ≺) ≤ (2d)2
.
We summarize the above discussion in the next theorem.

k

Theorem 4.1. ([8]) Suppose that I is in quasi stable position and that the ideals I1 , . . . , In−1 , I satisfy CP w.r.t. d.
n−2
Then deg(I, ≺) ≤ reg(I) ≤ (2d)2
.
Proof. We mentioned already above that for any ideal in
quasi stable position deg(I, ≺) ≤ reg(I), since the regularity
equals the maximal degree of an element of the Pommaret
basis of I. As the regularity remains invariant under linear
coordinate transformations, we may w.l.o.g. assume that I
is even in strongly stable position where deg(I, ≺) = reg(I)
and where Prop. 3.6 entails that also I1 , . . . , In−1 , I satisfy
CP w.r.t. d. Now the assertion follows from the consideration above.
We derive now a dimension dependent upper bound for
deg(I, ≺).
Theorem 4.2. Suppose that I is in strongly stable position and D = dim(I) ≥ 1. Then
2D−1
deg(I, ≺) = reg(I) ≤ dn−D + (n − D)(d − 1)
.
Proof. Since I is in strongly stable position, the ideal
In−D ⊂ [x1 , . . . , xn−D ] is zero-dimensional [34, Prop 3.15].
According to Lem. 3.11, deg(In−D ) ≤ (n − D)(d − 1) + 1.
Hence the maximal degree of a term in G(LT(I)) which depends only on x1 , . . . , xn−D is at most this bound. We shall
now construct an upper bound for the degree of the terms

k

in G(LT(I)) containing at least one of the remaining variables xn−D+1 , . . . , xn . Following the approach of Caviglia
and Sbarra, we first look for an upper bound for the number of these terms.
αn
1
Consider a term m = xα
i > 0
1 · · · xn ∈ G(LT(I)) with αα
n−D
1
for some i ≥ n − D + 1. It is clear that xα
1 · · · xn−D
belongs to the complement of LT(In−D ). Since the ideal
In−D ⊂ [x1 , . . . , xn−D ] is zero-dimensional,
Lem. 3.11 en
tails that dimk [x1 , . . . , xn−D ]/In−D ≤ dn−D . Hence the
αn−D
1
number of terms xα
is at most dn−D . On the
1 · · · xn−D
other hand, for any index n − D + 1 ≤ i ≤ n we have
αi ≤ degi (LT(I)) ≤ deg(Ii , ≺). Furthermore, we know that
two distinct term in G(LT(I)) differ already in their first
n − 1 variables. These arguments imply that the number of
terms in G(LT(I)) containing atQleast one of the variables

xn−D+1 , . . . , xn is at most dn−D n−1
i=n−D+1 deg(Ii , ≺) + 1 .
The strongly stability of I implies that CP holds for LT(I)
w.r.t. (n−D)(d−1)+1
 ≥ d by Prop. 3.6. Hence deg (I, ≺)−
(n − D)(d − 1) + 1 + 1 must be less than or equal to the
number of terms in G(LT(I)) containing at least one of the
variables xn−D+1 , . . . , xn leading to the estimate

k

k

deg(I, ≺) ≤ dn−D

n−1
Y


deg(Ii , ≺) + 1 + (n − D)(d − 1) .

i=n−D+1

Set Bn−D+1 = dn−D + (n − D)(d − 1) and recursively Bj =
Q
dn−D j−1
i=n−D+1 (Bi +1)+(n−D)(d−1) for n−D+2 ≤ j ≤ n.
One easily verifies that these numbers
 satisfy the recursion
relation Bj = Bj−1 −(n−D)(d−1) (Bj−1 +1)+(n−D)(d−

2
1) = Bj−1
− (n−D)(d−1)−1 Bj−1 . We may again assume
2
that d ≥ 2, and therefore Bj ≤ Bj−1
for n − D + 2 ≤ j ≤ n.
j−n+D−1

This implies that Bj ≤ (dn−D +(n−D)(d−1))2
and
D−1
in particular we have Bn ≤ (dn−D + (n − D)(d − 1))2
.
Remark 4.3. Let us compare the dimension dependent
D−1
bounds A(n, d, D) = 2d(n−D)2
derived in Thm. 3.12 and
D−1
B(n, d, D) = 2(1/2dn−D + d)2
due to Mayr and Ritscher
D−1
[29] with C(n, d, D) = (dn−D + (n − D)(d − 1))2
obtained
now. Obviously, all three bounds describe essentially the
same qualitative behaviour, although they are derived with
fairly different approaches. However, the bound B(n, d, D)
of Mayr and Ritscher has almost always the best constants.
But there are some cases where one of the other bounds is
better. For example, in the case of a hypersurface, i.e. for
D = n − 1, A(n, d, D) is smaller than B(n, d, D). For some
curves of low degree, i.e. for D = 1 and small values of
d, C(n, d, D) is smaller than B(n, d, D). Some concrete inequalities are:
• A(5, 3, 4) < C(5, 3, 4),
• A(3, 5, 2) > C(3, 5, 2),
• A(5, 2, 4) < B(5, 2, 4),
• A(5, 4, 2) > B(5, 4, 2),
• B(4, 5, 1) > C(4, 5, 1),
• B(5, 2, 3) < C(5, 2, 3).
Hence no bound is always the best one.

Again an application of Prop. 3.1 yields immediately an
improved bound depending on both the depth and the dimension of I.
Corollary 4.4. Under the assumptions of Thm. 4.2, one
D−λ−1
has deg(I, ≺) = reg(I) ≤ (dn−D + (n − D)(d − 1))2
.
It should be noted that in positive characteristic it is not
always possible to achieve strongly stable position by linear
coordinate transformations (see [21] for a more detailed discussion). Nevertheless, following [8], we state the following
conjecture.
Conjecture 4.5. The upper bound for the CastelnuovoMumford regularity of I in Cor. 4.4 holds independently of
the characteristic of .

k

5.

LAZARD’S UPPER BOUND

Finally, in this section we study Lazard’s upper bound [23]
for the degree of Gröbner bases for both homogeneous and
non-homogeneous ideals. We provide a simple proof for his
results and generalize Giusti’s bound to non-homogeneous
ideals. Note that for Lazard [23] dimension was always the
one as projective variety, whereas we use throughout this
paper the one as affine variety which is one higher. In the
sequel, we always set di = 1 for any i > k.
Theorem 5.1. ([23, Thm. 2]) Assume that dim(I) ≤ 1.
Then we have deg (gin(I), ≺) ≤ d1 + · · · + dr − r + 1 where
r = n − λ.
We showed in [20] that many properties of gin(I) also hold
for lt(I) provided I is in quasi stable position. Along these
lines, we shall now prove that in Lazard’s upper bound we
can replace gin(I) by I, if I is in quasi stable position. For
this, we need the next proposition also due to Lazard, which
is the key point in the proof of the above theorem.
Proposition 5.2 ([22, Thm. 3.3]). Assume again that
dim(I) ≤ 1. Then dimk (P/I)ℓ = dimk (P/I)ℓ+1 for each
ℓ ≥ d1 + · · · + dn − n + 1.
Thus, under the assumptions of this proposition, we can
say that hilb(I) ≤ d1 + · · · + dn − n + 1.
Theorem 5.3. Suppose that I is in quasi stable position
and dim(I) ≤ 1. Then, deg(I, ≺) ≤ d1 + · · · + dr − r + 1
where r = n − λ.
Proof. It suffices to show that deg(I, ≺) ≤ d1 + · · · +
dn − n + 1, since then the desired inequality follows immediately from Prop. 3.1. As I is in quasi stable position,
we have the inequality deg(I, ≺) ≤ max{hilb(I), hilb(I ′ )}
where I ′ = (I +hxn i)∩ [x1 , . . . , xn−1 ] is an ideal in the ring
[x1 , . . . , xn−1 ] [19, Thm. 4.17], [36, Thm. 4.7]. Obviously,
I ′ is generated by f1 |xn =0 , . . . , fk |xn =0 and dim(I) ≤ 1 (by
using the fact that I is in quasi stable position) entails
dim(I ′ ) ≤ 1. These arguments show that, by Prop. 5.2,
hilb(I) ≤ d1 + · · · + dn − n + 1 and hilb(I ′ ) ≤ d1 + · · · +
dn−1 − (n − 1) + 1 which proves the assertion.

k

k

Example 5.4. Lazard [23, Conj. 3] conjectured that the
conclusion of Theorem 5.1 remained true, if one replaces
gin I by I. Mora claimed that the following ideal (see the
Appendix of [23]) provided a counter-example. Consider the

t
homogeneous ideal I = hx1 xt−1
−xt3 , xt+1
−x2 xt−1
2
1
3 x4 , x1 x3 −
t
x2 x4 i in the polynomial ring P = [x1 , . . . , x4 ]. Thus we
have d1 = t, d2 = d3 = t + 1. One can show that the poly2
2
nomial xt3 +1 − xt2 x4 appears in the Gröbner basis of I and
hence deg(I, ≺) ≥ t2 + 1. For simplicity we restrict to the
case t = 4 where we obtain

k

17
LT(I) = hx1 x32 , x41 x3 , x51 , x31 x53 , x21 x93 , x1 x13
3 , x3 i .

Thus we find here deg(I, ≺) = 17 > d1 + d2 + d3 − 3 = 11.
But as dim(I) = 2, I does not yield a counter-example to
Lazard’s conjecture. However, if we consider I ′ = I|x4 =0 ⊂
[x1 , x2 , x3 ], then we find that I ′ has dimension 1 and that
LT(I ′ ) is generated by the same terms as LT(I). I ′ is
not in quasi stable position, as no pure power of x2 belongs to LT(I ′ ). Hence I ′ represents a counter-example to
Lazard’s conjecture. This example shows furthermore that in
Thm. 5.3 it is not possible to drop the assumption of quasi
stable position.

k

Remark 5.5. We gave above a direct proof for Thm. 5.3.
However, we can provide a more concise proof using Thm. 5.1
and Pommaret bases. Indeed, from Thm. 5.1 it follows that
reg(I) ≤ d1 + · · · + dr − r + 1 where r = n − λ, as reg(I) =
deg(gin(I), ≺). Since the ideal I is in quasi stable position, it possesses a finite Pommaret basis H where reg(I)
is the maximal degree of the elements of H and therefore
deg(I, ≺) ≤ d1 + · · · + dr − r + 1. These considerations also
yield immediately the following corollary.
Corollary 5.6. If dim(I) ≤ 1, then reg(I) ≤ d1 + · · · +
dr − r + 1 where r = n − λ.
Finally, we present an affine version of Thm. 5.3. We drop
now the assumption that the polynomials f1 , . . . , fk generating I are homogeneous. Let xn+1 be an extra variable
and f˜ the homogenization of f using xn+1 . We further denote by Ĩ the ideal generated by f˜1 , . . . , f˜k (note that in
general this is not equal to the homogenization of I). The
next proposition may be considered as a generalization of
Lazard’s upper bound [23, Thm. 2] to ideals in quasi stable
position.
Proposition 5.7. Assume that Ĩ is in quasi stable position, that dim(Ĩ) ≤ 1 and that depth(Ĩ) = λ. Then,
deg(I, ≺) ≤ d1 + · · · + dr − r + 1 where r = n + 1 − λ.
Proof. By Thm. 5.3, hilb(Ĩ) ≤ reg(Ĩ) ≤ d1 + · · · + dr −
r+1 where r = n+1−λ. Hence dimk ( [x1 , . . . , xn+1 ]/Ĩ)ℓ =
dimk ( [x1 , . . . , xn+1 ]/Ĩ)ℓ+1 for all degrees ℓ ≥ d1 +· · ·+dr −
r + 1. Therefore, we have dimk (P/I)≤ℓ = dimk (P/I)≤ℓ+1
for each ℓ ≥ d1 + · · · + dr − r + 1 and this observation implies
that the reduced Gröbner basis of I contains no element of
degree greater than d1 + · · · + dr − r + 1.

k

k

We conclude this paper by mentioning that it is easy to
see that for a homogeneous ideal with dim(I) ≤ 1, being
in quasi stable position is equivalent to being in Nœther
position. This implies that in Thm. 5.3 and Prop. 5.7 one
can replace “quasi stable position” by “Nœther position”.

Acknowledgments.
The research of the first author was in part supported by
a grant from IPM (No. 94550420). The work of the sec-

ond author was partially performed as part of the H2020FETOPEN-2016-2017-CSA project SC 2 (712689). The authors would like to thank the anonymous reviewers for their
valuable comments.

6.

REFERENCES

[1] T. Becker and V. Weispfenning. Gröbner Bases, a
Computational Approach to Commutative Algebra.
Springer, 1993.
[2] D. Bayer. The Division Algorithm and the Hilbert
Scheme. Ph.D. thesis, Harvard University, 1982.
[3] D. Bayer and M. Stillman. A Criterion for Detecting
m-Regularity. Invent. Math. 87(1), pages 1–11, 1987.
[4] I. Bermejo and P. Gimenez. Computing the
Castelnuovo-Mumford Regularity of Some Subschemes
of Pn
K Using Quotients of Monomial Ideals. J. Pure
Appl. Algebra, 164(1-2), pages 23–33, 2001.
[5] I. Bermejo and Ph. Gimenez. Saturation and
Catelnuovo-Mumford regularity. J. Algebra, 303,
pages 592–617, 2006.
[6] B. Buchberger. Ein Algorithmus zum Auffinden der
Basiselemente des Restklassenringes nach einem
nulldimensionalen Polynomideal. PhD thesis,
Universität Innsbruck, 1965.
[7] B. Buchberger. A Criterion for Detecting Unnecessary
Reductions in the Construction of Gröbner Bases.
EUROSAM’79, Lecture Notes in Compute. Sci.,
Springer, 72, pages 3–21, 1979.
[8] G. Caviglia and E. Sbarra. Characteristic-free Bounds
for the Castelnuovo-Mumford Regularity. Compos.
Math., 141(6), pages 1365–1373, 2005.
[9] D. Cox, J. Little and D. O’Shea. Ideals, Varieties, and
Algorithms. Springer-Verlag, third edition, 2007.
[10] T. Dubé. The Structure of Polynomial Ideals and
Gröbner Bases. SIAM Journal on Computing, 19,
pages 750–773, 1990.
[11] D. Eisenbud. Commutative Algebra with a View
toward Algebraic Geometry. Springer-Verlag, 1995.
[12] D. Eisenbud and S. Goto. Linear Free Resolutions and
Minimal Multiplicity. J. Algebra, 88(1), pages 89–133,
1984.
[13] R. Fröberg. An Introduction to Gröbner Bases. John
Wiley & Sons Ltd., Chichester, 1997.
[14] A. Galligo. A propos du théorème de preparation de
Weierstrass. Lect. Notes Math., 409, pages 543–579,
1974.
[15] A. Galligo. Théorème de division et stabilité en
géométrie analytique locale.. Ann. Inst. Fourier,
29(2), pages 107–184, 1979.
[16] M. Giusti. Some Effectivity Problems in Polynomial
Ideal Theory. EUROSAM’84, Lecture Notes in
Comput. Sci., 174, pages 159–171, Springer, 1984.
[17] M. Green. Generic Initial Ideals. In: Elias, J., Giral,
J., Miró-Roig, R., Zarzuela, S. (eds.) Six Lectures on
Commutative Algebra, pages 119–186. Progress in
Mathematics 166, Birkhäuser, Basel, 1998.
[18] G.M. Greuel and G. Pfister. A Singular Introduction
to Commutative Algebra. Springer-Verlag, 2008.
[19] A. Hashemi. Strong Noether Position and Stabilized
Regularities. Commun. Algebra, 38(2), pages 515–533,
2010.

[20] A. Hashemi, M. Schweinfurter and W.M. Seiler.
Quasi-stability versus Genericity. Proc. CASC’12,
Lecture Notes in Comput. Sci., 7442, pages 172–184,
2012.
[21] A. Hashemi, M. Schweinfurter and W.M. Seiler.
Deterministic Genericity for Polynomial Ideals. J.
Symb. Comput., accepted for publication (2017), 31
pages (doi.org/10.1016/j.jsc.2017.03.008).
[22] D. Lazard. Résolution des systèmes d’équations
algébriques. Theoret. Comput. Sci. 15(1), pages
77–110, 1981.
[23] D. Lazard. Gröbner Bases, Gaussian Elimination and
Resolution of Systems of Algebraic Equations. Proc.
EUROCAL’83, Lecture Notes in Comput. Sci., 162,
pages 146–156, Springer, 1983.
[24] D. Lazard. A Note on Upper Bounds for
Ideal-Theoretic Problems. J. Symb. Comput., 13(3),
pages 231–234, 1992.
[25] M. Lejeune-Jalabert. Effectivité de calculs
polynomiaux. Cours de D.E.A, Institute Fourier,
Grenoble. 1984.
[26] D. Mall. On the Relation between Gröbner and
Pommaret Bases. Appl. Alg. Eng. Comm. Comp., 9,
pages 117–123, 1998.
[27] H. Matsumura. Commutative ring theory. Cambridge
University Press, second edition, 1989.
[28] E. W. Mayr and A. R. Meyer. The Complexity of the
Word Problems for Commutative Semigroups and
Polynomial Ideals. Adv. Math., 46(3), pages 305–329,
1982.
[29] E.W. Mayr and S. Ritscher. Dimension-Dependent
Bounds for Gröbner Bases of Polynomial Ideals. J.
Symb. Comput., 49, pages 78–94, 2013.
[30] H.M. Möller and F. Mora. Upper and Lower Bounds
for the Degree of Groebner Bases. In Proc.
EUROSAM’84, Lecture Notes in Comput. Sci., 174,
pages 172–183. Springer, 1984.
[31] T. Mora. Solving Polynomial Equation Systems II:
Macaulay’s Paradigm and Gröbner Technology.
Cambridge University Press, 2005.
[32] D. Mumford. Lectures on Curves on an Algebraic
Surface. Princeton University Press, 1966.
[33] W.M. Seiler. A Combinatorial Approach to Involution
and δ-Regularity I: Involutive Bases in Polynomial
Algebras of Solvable Type. Appl. Alg. Eng. Comm.
Comp. 20, pages 207–259, 2009.
[34] W.M. Seiler. A Combinatorial Approach to Involution
and δ-Regularity II: Structure Analysis of Polynomial
Modules with Pommaret Bases. Appl. Alg. Eng.
Comm. Comp. 20, pages 261–338, 2009.
[35] W.M. Seiler. Involution – The Formal Theory of
Differential Equations and its Applications in
Computer Algebra. Springer-Verlag, 2010.
[36] W.M. Seiler. Effective Genericity, δ-Regularity and
Strong Noether Position. Commun. Algebra, 40(10),
pages 3933–3949, 2012.
[37] C. Yap. A New Lower Bound Construction for the
Word Problem for Commutative Thue Systems. J.
Symb. Comput., 12(1), pages 1–28, 1991.

