On the Castelnuovo regularity for curves

Marc Giusti ^{∗}

Centre de Mathématiques (URA CNRS D.0169) / Laboratoire d’Informatique

Ecole Polytechnique 91128 PALAISEAU CEDEX and GRECO de Calcul Formel No. 60 uucp : giusti@cmep.polytechnique.fr bitnet : cfmagi@frpoly11

February 23, 1995

INTRODUCTION

Let k be a field of characteristic zero ; let us consider an algebraic subvariety of the projective space P_{k}^{n}, defined by a homogeneous ideal I of the polynomial algebra R = k[x_{0}, …, x_{n}]. There exists different objects measuring the complexity of this subvariety : some of them depend on the coordinates, for example a standard basis of I, w.r.t. a total compatible ordering on the monomials of R. An especially important integer is the maximal degree of the polynomials of this standard basis, which is a fortiori unfortunately not intrinsic. But after a theorem of Galligo, at least in characteristic zero, the initial ideal do not depend on the coordinates provided they are general enough [GA]. In particular the maximal degree of a standard basis in generic coordinates will become an intrinsic quantity.

On the other hand, other invariants (according to their name) are naturally intrinsic : let us mention the dimension and the degree of the subvariety, the Hilbert function and its regularity, eventually the Castelnuovo regularity (for the definition of this last notion see the introduction of the paper [GLP]).

A natural question is to study the relationships between the integers mentioned above, at least when the dimension is small (less or equal to one). I want to give here a slightly different version of the Castelnuovo-Gruson-Lazarsfeld-Peskine theorem [GLP], which relates the Castelnuovo regularity and the degree in the case of curves, with more general hypotheses but unfortunately slightly weaker conclusion.

∗Partially supported by a grant of the PRC “Mathématiques et Informatique”.

1 Statement of the problem

If (y_{0}, y_{1}, …, y_{n}) is a generic system of coordinates, obtained by n + 1 linear generic combinations of x_{0}, x_{1}, …, x_{n}, let us denote by I^{(r)} the ideal I + (y_{0}, …, y_{r−1}).

1.1 Definitions : lower lexicographic ordering and filtration

A point a = (a_{0}, …, a_{n}) of N^{n+1} is smaller than a point b = (b_{0}, …, b_{n}) for the lower lexicographic ordering if and only if there exists an index i (0 ≤ i ≤ n) such that :

a_{0} = b_{0}, …, a_{i−1} = b_{i−1}, a_{i} < b_{i}

To every non zero homogeneous polynomial :

f = ∑_{a∈N^{n+1}} f_{a} x^{a}

is then associated its support {a ∈ N^{n+1} | f_{a} ≠ 0} in N^{n+1}. The smallest element of the support of f for the lower lexicographic ordering is called its leading monomial exp(f).

From now on the filtration hence defined of the polynomial ring R will be called the lower lexicographic filtration.

1.2 Various integers measuring the complexity

The generic stairs of I are all leading monomials of the elements of I, w.r.t. generic coordinates and the lower lexicographic filtration. The corresponding subset E(I) of N^{n+1} is called stable, i.e. stable under addition of any element of N^{n+1}. By noetherianity, the section E_{s} of the stairs by the coordinate hyperplane x_{0} = s is constant for s large enough : it is the section at infinity E_{∞}(I).

The maximal degree of the generators of E(I) will be denoted by D(I), the regularity of the Hilbert function by H(I), the dimension and the degree of the variety respectively by dim(I) and deg(I). The first two integers measure rather well the complexity of the ideal I, since from their knowledge a standard basis and the Hilbert polynomial are easily deduced. Hence it is highly important to give upper bounds for them. Note that since the regularity of the Hilbert function is always at most some quite simple linear function of the maximal degree of a standard basis (w.r.t. any ordering and any coordinates) [GI1] [GI3], D(I) is the most interesting integer. Furthermore a fundamental result of Bayer and Stillman shows that in characteristic zero, the Castelnuovo regularity is actually equal to the integer D(I). This justifies to call this common value the regularity reg(I) (after Bayer and Stillman), but in order to avoid confusions with the regularity of the Hilbert function, we will use below the expression intrinsic complexity.

Usually, the general upper bounds known for this intrinsic complexity involve highly non intrinsic quantities, such as typically the maximum degree d of the input given generators of I [GI1]. This is rather natural since the double exponential behaviour of this general upper bound is unavoidable from the Mayr-Meyer examples [MM], while the other intrinsic invariants such as the dimension and the degree are comparatively small (respectively at most n and d^{n} by Bézout theorem).

It is then conceptually interesting to try to isolate “good” cases, where an upper bound for the intrinsic complexity involves only intrinsic quantities. But as we are still concerned with the “practical” point of view, we look also at the behaviour of these last intrinsic quantities in terms of the input data, essentially d.

2 Intrinsic complexity in negative or zero dimension

Let us review in this section what is known in these low dimensions.

In the negative dimensional case, there exists a quite pleasant linear upper bound, essentially (n + 1)d coming from the work of D. Lazard [L1] [L2] [L3]. It is not surprising that there are no intrinsic quantities involved, since the defining ideal is irrelevant and the variety empty.

In the zero dimensional case, if by chance the defining ideal is saturated the same bound as before holds [L3], but we can remark that we can give also at the same time an intrinsic bound which is the degree deg(I), considering the same section by a non zero divisor.

If there is an irrelevant ideal in the primary decomposition of I, we can apply the general intrinsic bound Max((n + 1)deg(I), H(I)) given in [GI2]. It seems that because of the presence of H(I) this bound is not very useful, but in this zero dimensional situation D. Lazard proved that H(I) is at most (n + 1)d. So the Bézout bound d^{n} for the degree yields a single exponential behaviour of the intrinsic complexity in terms of d.

3 Intrinsic complexity in dimension one

We have to consider only equidimensional and reduced curves.

3.1 Theorem

Let C be an equidimensional reduced curve of P^{n}, defined by some ideal I intersection of prime ideals of same dimension. Then we have :

D(I) ≤ (H(E_{∞}(I^{(1)}) − 1)) deg(I) + H(E_{∞}(I^{(1)}))

Proof : As the curve is equidimensional, the first (generic) coordinate y_{0} can be assumed to be a non zero divisor of the ring R/I, and D(I) is equal to D(I^{(1)}). Now the second (generic) coordinate y_{1} is a parameter for the ring R/(I +y_{0}), and looking at the canonical decomposition of the complementary of E(I^{(1)}) we conclude :

N^{n+1} − E(I^{(1)}) = (N^{n+1} − N × E_{∞}(I^{(1)})) ∐ B

where B is finite.

The Hilbert function of E_{∞}(I^{(1)}) (respectively the Hilbert function of N×E_{∞}(I^{(1)}), which is the integral of the previous one) takes the successive values :

1 = a_{0}, a_{1}, …, a_{H(E_{∞}(I^{(1)}))−1}, 0, 0, …

(respectively :

1 = A_{0}, A_{1}, …, A_{H(E_{∞}(I^{(1)}))−1} = deg(I), deg(I), deg(I), …

with A_{i} = ∑_{j≤i} a_{j}). Now it is enough to perturbe it, adding the sequence :

0, 0, …, 0, B_{min}, …, B_{max}, 0, 0, …

coming from B to obtain the Hilbert function of E(I^{(1)}). The Hilbert function of E(I) is eventually the integral of this last one, and the Hilbert polynomial is equal for the argument s large enough :

A_{0} + ⋯ + A_{H(E_{∞}(I^{(1)}))−2} + B_{min} + ⋯ + B_{max} + (s − H(E_{∞}(I^{(1)})) + 2) deg(I)

But using the upper bound of the Hilbert function (hence of the polynomial) established by M. Chardin [C] :

HF_{I}(s) ≤ ( \begin{matrix}s + dim(I) \\ dim(I) \end{matrix} ) deg(I)

we obtain very roughly the upper bound (H(E_{∞}(I^{(1)})) − 1) deg(I) for B_{min} + ⋯ + B_{max} which is nothing else than the volume of B.

We divide the generators of E(I^{(1)}) into two classes : the first ones are generators of N × E_{∞}(I^{(1)}) and the others. The degree of the first ones is at most H(E_{∞}(I^{(1)})). On the other hand, the degree of every element of the second class is at most the same quantity, plus the volume B. Finally we obtain the rough upper bound :

D(E(I)) = D(E(I^{(1)})) ≤ (H(E_{∞}(I^{(1)})) − 1) deg(I) + H(E_{∞}(I^{(1)}))

3.2 Corollary

The Castelnuovo regularity of an equidimensional reduced curve over a field of characteristic zero has a single exponential behaviour in the maximal degree of the defining equations

Actually, if the degree of the generators of the ideal I is at most d, the total degree is at most d^{n−1} after the Bézout theorem, and the regularity H(E_{∞}(I^{(1)})) is at most nd.

REFERENCES

[BS] D. BAYER, M. STILLMAN, A criterion for detecting m-regularity, Invent. math. 87, 1-11 (1987)

[C] M. CHARDIN, Une majoration de la fonction de Hilbert et ses conséquences pour l’interpolation algébrique, preprint Centre de Mathématiques de l’Ecole Polytechnique, 91128 Palaiseau Cedex (France), to be published in Bull. S.M.F.

[GA] A. GALLIGO, A propos du théorème de préparation de Weierstrass, Lect. Notes in Math. 409 (1973), 543-579, Springer Verlag.

[GI1] M. GIUSTI, Some effectivity problems in polynomial ideal theory, Proceedings EUROSAM 84 (Cambridge, Angleterre), Lecture Notes in Computer Science 174, Springer (1984).

[G2] M. GIUSTI, Complexity of standard bases in projective dimension zero. Accepté pour publication dans les proceedings d’EUROCAL Leipzig (1987).

[G3] M. GIUSTI, Combinatorial dimension theory of algebraic varieties. Prépublication du Centre de Mathématiques de l’Ecole Polytechnique 1986, à paraître dans le Volume spécial du “Journal of Symbolic Computation” : Computational Aspects of Commutative Algebra.

[GLP] L. GRUSON, R. LAZARSFELD, C. PESKINE, On a theorem of Castelnuovo, and the Equations defining Space Curves, Invent. math 72, 491-506 (1983).

[L1] D. LAZARD, Algèbre linéaire sur K[x_{1}, …, x_{n}] et élimination, Bull. Soc. Math. France, 105 (1977), 165-190.

[L2] D. LAZARD, Résolution des systèmes d’équations algébriques, Theoretical Computer Science 15 (1981), 77-110.

[L3] D. LAZARD, Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, in Eurocal 83, Lecture Note in Computer Science 162, Springer (1983).

[MM] E. MAYR, A. MEYER, The complexity of the word problem for commutative semi-groups and polynomial ideals, Adv. in Maths. 46 (1982), 305-329.