What Can Be Computed in Algebraic Geometry?

May 7, 1992

$\ast$Partially supported by NSF grant DMS-90-06116.

This paper evolved from a long series of discussions between the two authors, going back to around 1980, on the problems of making eﬀective computations in algebraic geometry, and it took more deﬁnite shape in a survey talk given by the second author at a conference on Computer Algebra in 1984. The goal at that time was to bring together the perspectives of theoretical computer scientists and of working algebraic geometers, while laying out what we considered to be the main computational problems and bounds on their complexity. Only part of the talk was written down and since that time there has been a good deal of progress. However, the material that was written up may still serve as a useful introduction to some of the ideas and estimates used in this ﬁeld (at least the editors of this volume think so), even though most of the results included here are either published elsewhere, or exist as “folk-theorems” by now.

The article has four sections. The ﬁrst two parts are concerned with the theory of Gröbner bases; their construction provides the foundation for most computations, and their complexity dominates the complexity of most techniques in this area. The ﬁrst part introduces Gröbner bases from a geometric point of view, relating them to a number of ideas which we take up in more detail in subsequent sections. The second part develops the theory of Gröbner bases more carefully, from an algebraic point of view. It could be read independently, and requires less background. The third part is an investigation into bounds in algebraic geometry of relevance to these computations. We focus on the regularity of an algebraic variety (see Deﬁnition 3.2), which, beyond its intrinsic interest to algebraic geometers, has emerged as a measure of the complexity of computing Gröbner bases (see [BS87a], [BS87b], [BS88]). A principal result in this part is a bound on the regularity of any smooth variety by the second author: Theorem 3.12(b). This bound has stimulated subsequent work, and has now been generalized by [BEL91]. Another result of interest is Proposition 3.13, which elucidates the scheme structure of the ideal membership problem. The fourth part is a short discussion of work on algorithms for performing some other key operations on varieties, some open problems about these operations and some general ideas about what works and what doesn’t, reﬂecting the prejudices of the authors.

One of the diﬃculties in surveying this area of research is that mathematicians from so many specialties have gotten involved, and they tend both to publish in their own specialized journals and to have speciﬁc agendas corresponding to their area. Thus one group of researchers, the working algebraic geometers, are much more interested in actually computing examples than in worst-case complexity bounds. This group, including the ﬁrst author, has put a great deal of work into building a functioning system, Macaulay, based on Gröbner bases, which has solved many problems and provided many examples to the algebraic geometry community [BS92a]. Another group comes from theoretical computer science and is much more interested in theoretical bounds than practical systems (cf. the provocative comments in Lenstra’s survey [Len92]). It seems to us that more communication would be very helpful: On the one hand, the working algebraic geometer knows lots of facts about varieties that can be very relevant to ﬁnding fast algorithms. Conversely asymptotic and/or worst-case performance bounds are sometimes, at least, important indicators of real-time performance. These theoretical bounds may also reveal important distinctions between classes of procedures, and may pose new and deep problems in algebraic geometry. Thus we will see in Section 3 how regularity estimates ﬂesh out a picture explaining why Gröbner basis computations can have such explosive worst case behavior, yet be so useful for the kinds of problems typically posed by mathematicians. Finally, to make this article more useful in bridging this gap, we have tried to include a substantial number of references in our discussions below.

1 A Geometric Introduction

Let $X$ be a subvariety or a subscheme of projective $n$-space $\text{}Pn\text{}$, over a ﬁeld $k$. Let $\mathsc{ℱ}$ be a vector bundle or a coherent sheaf supported on $X$. We would like to be able to manipulate such objects by computer. From algebra we get ﬁnite descriptions, amenable to such manipulations: Let $S=k\left[{x}_{0},\dots ,{x}_{n}\right]$ be the homogeneous coordinate ring of $\text{}Pn\text{}$. Then $X$ can be taken to be the subscheme deﬁned by a homogenous ideal $I\subset S$, and $\mathsc{ℱ}$ can be taken to be the sheaf associated to a ﬁnitely generated $S$-module $M$. We can represent $I$ by a list of generators $\left({f}_{1},\dots ,{f}_{r}\right)$, and $M$ by a presentation matrix $F$, where

${M}_{1}\stackrel{F}{\to }{M}_{0}\to M\to 0$

presents $M$ as a quotient of ﬁnitely generated free $S$-modules ${M}_{0}$, ${M}_{1}$. We concentrate on the case of an ideal $I$; by working with the submodule $J=Im\left(F\right)\subset {M}_{0}$, the module case follows similarly.

The heart of most computations in this setting is a deformation of the input data to simpler data, combinatorial in nature: We want to move through a family of linear transformations of $\text{}Pn\text{}$ so that in the limit our objects are described by monomials. Via this family, we hope to pull back as much information as possible to the original objects of study.

Choose a one-parameter subgroup $\lambda \left(t\right)\subset GL\left(n+1\right)$ of the diagonal form

$\lambda \left(t\right)=\left[\begin{array}{cccc}\hfill {t}^{{w}_{0}}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill {t}^{{w}_{1}}\hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \dots \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill {t}^{{w}_{n}}\hfill \end{array}\right],$

where $W=\left({w}_{0},\dots ,{w}_{n}\right)$ is a vector of integer weights. For each $t\ne 0$, $\lambda \left(t\right)$ acts on $X$ via a linear change of coordinates of $\text{}Pn\text{}$, to yield the subscheme ${X}_{t}=\lambda \left(t\right)X\cong X$. The limit

${X}_{0}=lim t\to 0{X}_{t}$

is usually a simpler object, preferable to $X$ for many computational purposes.

Even if we start out by restricting $X$ to be a subvariety rather than a subscheme of $\text{}Pn\text{}$, it does not suﬃce to take the limit ${X}_{0}$ set-theoretically; often all we will get pointwise in the limit is a linear subspace $L\subset \text{}Pn\text{}$, reﬂecting little besides the dimension of the original variety $X$. By instead allowing this limit to acquire embedded components and a nonreduced structure, we can obtain an ${X}_{0}$ which reﬂects much more closely the character of $X$ itself.

We compute explicitly with the generators ${f}_{1},\dots ,{f}_{r}$ of $I$: Let $\lambda$ act on $S$ by mapping each ${x}_{i}$ to ${t}^{{w}_{i}}{x}_{i}$; $\lambda$ maps each monomial ${x}^{A}={x}_{0}^{{a}_{0}}\cdots {x}_{n}^{{a}_{n}}$ to ${t}^{W\cdot A}{x}^{A}={t}^{{w}_{0}{a}_{0}+\dots +{w}_{n}{a}_{n}}{x}_{0}^{{a}_{0}}\cdots {x}_{n}^{{a}_{n}}$. If $f=a{x}^{A}+b{x}^{B}+\dots$, then $\lambda f=a\phantom{\rule{0em}{0ex}}{t}^{W\cdot A}{x}^{A}+b\phantom{\rule{0em}{0ex}}{t}^{W\cdot B}{x}^{B}+\dots$. We take the projective limit $in\left(f\right)=lim t\to 0\lambda f$ by collecting the terms of $\lambda f$ involving the least power of $t$; $in\left(f\right)$ is then the sum of the terms $a{x}^{A}$ of $f$ so $W\cdot A$ is minimal. For a given $f$ and most choices of $\lambda$, $in\left(f\right)$ consists of a single term.

The limit ${X}_{0}$ we want is deﬁned with all its scheme structure by the ideal $in\left(I\right)=lim t\to 0\lambda I$, generated by the set $\left\{\phantom{\rule{0em}{0ex}}in\left(f\right)\phantom{\rule{0em}{0ex}}|\phantom{\rule{0em}{0ex}}f\in I\phantom{\rule{0em}{0ex}}\right\}$. For a given $I$ and most choices of $\lambda$, $in\left(I\right)$ is generated by monomials. Unfortunately, this deﬁnition is computationally unworkable because $I$ is an inﬁnite set, and $in\left(I\right)$ need not equal $\left(in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)\right)$ for a given set of generators ${f}_{1},\dots ,{f}_{r}$ of $I$. To understand how to compute $in\left(I\right)$, we need to look more closely at the family of schemes ${X}_{t}$ deﬁned by $\lambda$.

Let $S\left[t\right]$ be the polynomial ring $k\left[{x}_{0},\dots ,{x}_{n},t\right]$; we view $S\left[t\right]$ as the coordinate ring of a one-parameter family of projective spaces ${P}_{t}^{n}$ over the aﬃne line with parameter $t$. For each generator ${f}_{j}$ of $I$, rescale $\lambda {f}_{j}$ so the lowest power of $t$ has exponent zero: Let ${g}_{j}={t}^{-\ell }\lambda {f}_{j}$, where $\ell =W\cdot A$ is the least exponent of $t$ in $\lambda {f}_{j}$. Then ${f}_{j}={g}_{j}\mid t=1$ and $in\left({f}_{j}\right)={g}_{j}\mid t=0$. Now, let $J\subset S\left[t\right]$ be the ideal generated by $\left({g}_{1},\dots ,{g}_{r}\right)$; $J$ deﬁnes a family $Y$ over $\text{}A1\text{}$ whose central ﬁber is cut out by $\left(in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)\right)$.

What is wrong with the family $Y$? $Y$ can have extra components over $t=0$, which bear no relation to its limiting behavior as $t\to 0$. Just as the set-theoretic limit $lim t\to 0{X}_{t}$ can be too small (we need the nonreduced structure), this algebraically deﬁned limit can be too big; the natural limit lies somewhere in between.

The notion of a ﬂat family captures exactly what we are looking for here. For example, if $Y$ is ﬂat, then there are no extra components over $t=0$. While the various technical deﬁnitions of ﬂatness can look daunting to the newcomer, intuitively ﬂatness captures exactly the idea that every ﬁber of a family is the natural scheme-theoretic continuation of its neighboring ﬁbers.

In our setting, all the ${X}_{t}$ are isomorphic for $t\ne 0$, so we only need to consider ﬂatness in a neighborhood of $t=0$. Artin [Art76] gives a criterion for ﬂatness applicable here: The syzygies of ${g}_{1},\dots ,{g}_{r}$ are the relations ${h}_{1}{g}_{1}+\dots +{h}_{r}{g}_{r}=0$ for ${h}_{1},\dots ,{h}_{r}\in S\left[t\right]$. Syzygies correspond to elements $\left({h}_{1},\dots ,{h}_{r}\right)$ of the $S\left[t\right]$-module $S{\left[t\right]}^{r}$; the set of all syzygies is a submodule of $S{\left[t\right]}^{r}$. $Y$ is a ﬂat family at $t=0$ if and only if the restrictions $\left({h}_{1}\mid t=0,\dots ,{h}_{r}\mid t=0\right)$ of these syzygies to the central ﬁber generate the $S$-module of syzygies of ${g}_{1}\mid t=0,\dots ,{g}_{r}\mid t=0$.

When ${g}_{1}\mid t=0,\dots ,{g}_{r}\mid t=0$ are single terms, their syzygies take on a very simple form: The module of syzygies of two terms $a{x}^{A}$, $b{x}^{B}$ is generated by the syzygy $b{x}^{C}\left(a{x}^{A}\right)-a{x}^{D}\left(b{x}^{B}\right)=0$, where ${x}^{E}={x}^{C}{x}^{A}={x}^{D}{x}^{B}$ is the least common multiple of ${x}^{A}$ and ${x}^{B}$. The module of syzygies of $r$ such terms is generated (usually not minimally) by the syzygies on all such pairs.

We want to lift these syzygies to syzygies of ${g}_{1},\dots ,{g}_{r}$, working modulo increasing powers of $t$ until each syzygy lifts completely. Whenever we get stuck, we will ﬁnd ourselves staring at a new polynomial ${g}_{r+1}$ so ${t}^{\ell }{g}_{r+1}\in J$ for some $\ell >0$. Including ${g}_{r+1}$ in the deﬁnition of a new ${J}^{\prime }\supset J$ has no eﬀect on the family deﬁned away from $t=0$, but will cut away unwanted portions of the central ﬁber; what we are doing is removing $t$-torsion. By iterating this process until every syzygy lifts, we obtain explicit generators ${g}_{1},\dots ,{g}_{r},{g}_{r+1},\dots ,{g}_{s}$ for a ﬂat family describing the degeneration of $X={X}_{1}$ to a good central ﬁber ${X}_{0}$. The corresponding generators ${g}_{1}\mid t=1,\dots ,{g}_{s}\mid t=1$ of $I$ are known as a Gröbner basis for $I$.

This process is best illustrated by an example. Let $S=k\left[w,x,y,z\right]$ be the coordinate ring of $\text{}P3\text{}$, and let $I=\left({f}_{1},{f}_{2},{f}_{3}\right)\subset S$ for

${f}_{1}={w}^{2}-xy,{f}_{2}=wy-xz,{f}_{3}=wz-{y}^{2}.$

$I$ deﬁnes a twisted cubic curve $X\subset \text{}P3\text{}$; $X$ is the image of the map $\left(r,s\right)↦\left({r}^{2}s,{r}^{3},r{s}^{2},{s}^{3}\right)$. Let

$\lambda \left(t\right)=\left[\begin{array}{cccc}\hfill {t}^{-16}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill {t}^{-4}\hfill & \hfill \hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill {t}^{-1}\hfill & \hfill \hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill {t}^{0}\hfill \end{array}\right].$

If ${w}^{a}{x}^{b}{y}^{c}{z}^{d}$ is a monomial of degree $<4$, then $\lambda \cdot {w}^{a}{x}^{b}{y}^{c}{z}^{d}={t}^{-\ell }{w}^{a}{x}^{b}{y}^{c}{z}^{d}$ where $\ell =16a+4b+c$. Thus, sorting the monomials of $S$ of each degree $<4$ by increasing powers of $t$ with respect to the action of $\lambda$ is equivalent to sorting the monomials of each degree in lexicographic order.

We have

$\begin{array}{rcll}{g}_{1}& ={t}^{32}\lambda {f}_{1}& ={w}^{2}-{t}^{27}xy,& \text{}\\ {g}_{2}& ={t}^{17}\lambda {f}_{2}& =wy-{t}^{13}xz,& \text{}\\ {g}_{3}& ={t}^{16}\lambda {f}_{3}& =wz-{t}^{14}{y}^{2}.& \text{}\end{array}$

The module of syzygies on ${w}^{2}$, $wy$, $wz$ is generated by the three possible pairwise syzygies; we start with the syzygy $y\left({w}^{2}\right)-w\left(wy\right)=0$. Substituting ${g}_{1}$, ${g}_{2}$ for the lead terms ${w}^{2}$, $wy$ we get

$y\left({w}^{2}-{t}^{27}xy\right)-w\left(wy-{t}^{13}xz\right)={t}^{13}wxz-{t}^{27}x{y}^{2}$

which is a multiple ${t}^{13}x$ of ${g}_{3}$. Thus, the syzygy

$y{g}_{1}-w{g}_{2}-{t}^{13}x{g}_{3}=0$

of ${g}_{1}$, ${g}_{2}$, ${g}_{3}$ restricts to the monomial syzygy $y\left({w}^{2}\right)-w\left(wy\right)=0$ when we substitute $t=0$, as desired.

Similarly, the syzygy

$z{g}_{1}-{t}^{14}y{g}_{2}-w{g}_{3}=0$

restricts to the monomial syzygy $z\left({w}^{2}\right)-w\left(wz\right)=0$. When we attempt to lift $z\left(wy\right)-y\left(wz\right)=0$, however, we ﬁnd that

$z\left(wy-{t}^{13}xz\right)-y\left(wz-{t}^{14}{y}^{2}\right)=-{t}^{13}x{z}^{2}+{t}^{14}{y}^{3}.$

$x{z}^{2}$ is not a multiple of ${w}^{2}$, $wy$, or $wz$, so we cannot continue; $J=\left({g}_{1},{g}_{2},{g}_{3}\right)$ does not deﬁne a ﬂat family. Setting $t=1$, the troublesome remainder is $-x{z}^{2}+{y}^{3}$. Making this monic, let ${f}_{4}=x{z}^{2}-{y}^{3}$; ${f}_{4}\in I$ and

${g}_{4}={t}^{4}\lambda {f}_{4}=x{z}^{2}-t{y}^{3}.$

Adjoin ${g}_{4}$ to the ideal $J$, redeﬁning the family $Y$. Now,

$z{g}_{2}-y{g}_{3}+{t}^{13}{g}_{4}=0$

restricts to $z\left(wy\right)-y\left(wz\right)=0$ as desired.

The module of syzygies of ${w}^{2}$, $wy$, $wz$, and $x{z}^{2}$ is generated by the pairwise syzygies we have already considered, and by the syzygy $xz\left(wz\right)-w\left(x{z}^{2}\right)=0$, which is the restriction of

$-t{y}^{2}{g}_{2}+xz{g}_{3}-w{g}_{4}=0.$

Thus, $J=\left({g}_{1},{g}_{2},{g}_{3},{g}_{4}\right)$ deﬁnes a ﬂat family $Y$, and

${w}^{2}-xy,wy-xz,wz-{y}^{2},x{z}^{2}-{y}^{3}$

is a Gröbner basis for $I$. The limit ${X}_{0}$ is cut out by the monomial ideal $in\left(I\right)=\left({w}^{2},wy,wz,x{z}^{2}\right)$, which we shall see shares many properties with the original ideal $I$. Note that $x{z}^{2}-{y}^{3}=0$ deﬁnes the projection of $X$ to the plane $\text{}P2\text{}$ in $x$, $y$, and $z$.

The scheme structure of ${X}_{0}$ is closely related to the combinatorial structure of the monomial $k$-basis for $S∕in\left(I\right)$: For each degree $d$ in our example, the monomials not belonging to $in\left(I\right)$ consist of three sets $\left\{{x}^{d},{x}^{d-1}y,\dots ,{y}^{d}\right\}$, $\left\{{x}^{d-1}z,{x}^{d-2}yz,\dots ,{y}^{d-1}z\right\}$, $\left\{{y}^{d},{y}^{d-1}z,\dots ,{z}^{d}\right\}$, and a lone extra monomial ${x}^{d-1}w$. The ﬁrst two sets correspond to a double line supported on $w=z=0$, the third set to the line $w=x=0$, and the extra monomial to an embedded point supported at $w=y=z=0$. Together, this describes the scheme structure of ${X}_{0}$. The ﬁrst two sets consist of $d+1$ and $d$ monomials, respectively; the third set adds $d-1$ new monomials, and overlaps two monomials we have already seen. With the extra monomial, we count $3d+1$ monomials in each degree, which agrees with the dimensions of the graded pieces of $S∕I$. The embedded point is crucial; it makes this count come out right, and it alone keeps ${X}_{0}$ nonplanar like $X$.

The new monomial generator $x{z}^{2}$ of $in\left(I\right)$ excludes the line $w=y=0$ from ${X}_{0}$; combinatorially, it excludes all but three monomials of the set $\left\{{x}^{d},{x}^{d-1}z,\dots ,{z}^{d}\right\}$ from the monomial $k$-basis for each degree of the quotient $S∕in\left(I\right)$. We can see that this line is unwanted as follows: Away from $t=0$, $Y$ is parametrized by $\left(r,s,t\right)↦\left({t}^{16}{r}^{2}s,{t}^{4}{r}^{3},tr{s}^{2},{s}^{3},t\right)$. Thus, ﬁxing $r$ and $s$, the curve $\left(r,ts,t\right)↦\left({t}^{17}{r}^{2}s,{t}^{4}{r}^{3},{t}^{3}r{s}^{2},{t}^{3}{s}^{3},t\right)$, with projective limit $\left(0,0,r,s,0\right)$ as $t\to 0$. Similarly, the curve $\left(r,{t}^{3}s,{t}^{2}\right)$ has as its limit $\left(0,{r}^{2},{s}^{2},0,0\right)$. These calculations show that the lines $w=z=0$ and $w=x=0$ indeed belong set-theoretically to the limit ${X}_{0}$. We can ﬁnd no such curve whose limit is a general point on the line $w=y=0$, for $\left(r,{t}^{4}s,{t}^{3}\right)$ doesn’t work. Thus, the line $w=y=0$ sticks out of the good total space $Y$.

One usually computes Gröbner bases by working directly in the ring $S$, dispensing with the parameter $t$. The one-parameter subgroup $\lambda$ is replaced by a total order on the monomials of each degree, satisfying the multiplicative property ${x}^{A}>{x}^{B}⇒{x}^{C}{x}^{A}>{x}^{C}{x}^{B}$ for all ${x}^{C}$. In fact, for our purposes these are equivalent concepts: The weight vector $W$ associated with $\lambda$ induces the order ${x}^{A}>{x}^{B}⇔W\cdot A, which is a total multiplicative order in low degrees as long as no two monomials have the same weight. Conversely, given any multiplicative order and a degree bound $d$, one can ﬁnd many $\lambda$ which induce this order on all monomials of degree $. See [Bay82], [Rob85] for characterizations of such orders.

We shall be particularly interested in two multiplicative orders, the lexicographic order used in our example, and the reverse lexicographic order. The lexicographic order simply expands out the monomials of each degree into words, and sorts them alphabetically, i.e. ${x}^{A}>{x}^{B}$ iﬀ the ﬁrst nonzero entry in $A-B$ is positive. The reverse lexicographic order pushes highest powers of ${x}_{n}$ in any expression back to the end, then within these groups pushes highest powers of ${x}_{n-1}$ to the end, etc., i.e. ${x}^{A}>{x}^{B}$ iﬀ the last nonzero entry of $A-B$ is negative.

What do these orders mean geometrically? The dominant eﬀect of the lexicographic order is a projection from $\text{}Pn\text{}$ to $\text{}Pn-1\text{}$, eliminating ${x}_{0}$. A second order eﬀect is a projection to $\text{}Pn-2\text{}$, and so forth. We could compute the deformation from $X$ to ${X}_{0}$ with respect to the lexicographic order in stages carrying out these projections, ﬁrst applying a $\lambda$ with $W=\left(-1,0,\dots ,0\right)$, then with $W=\left(-1,-1,0,\dots ,0\right)$, etc. Alternatively, for monomials of each degree $, we can apply the single $\lambda$ with $W=\left(-{d}^{n-1},\dots ,-d,-1,0\right)$, generalizing the $\lambda$ used in our example. Use of the lexicographic order tends to muck up the family $Y$ more than necessary in most applications, because projections tend to complicate varieties.

For the reverse lexicographic order, the dominant eﬀect is a projection of $\text{}Pn\text{}$ down to the last coordinate point $\left(0,\dots ,0,1\right)$. As a secondary eﬀect, this order projects down to the last coordinate line, and so forth. In other words, this order ﬁrst tries to make $X$ into a cone over the last coordinate point, and only then tries to squash the result down to or cone it over the last coordinate line, etc. For monomials of each degree $, this can be realized by applying $\lambda$ with $W=\left(0,1,d,\dots ,{d}^{n-1}\right)$. Like such cones, the reverse lexicographic order enjoys special properties with respect to taking linear sections of $X$ or ${X}_{0}$ by intersection with the spaces deﬁned by the last variable(s) (see [BS87a]). The preferred status of the reverse lexicographic order can be attributed to this relationship, because generic linear sections do not complicate varieties.

For example, if we take $X$ to be three general points in $\text{}P2\text{}$, then using the lexicographic order ${X}_{0}$ becomes a triple point on a line, because the ﬁrst order eﬀect is the projection of the three points to a line, and the second order limiting process keeps the points within this line. By contrast, if we use the reverse lexicographic order then ${X}_{0}$ becomes the complete ﬁrst order neighborhood of a point (a point doubled in all directions). This is because the ﬁrst order limiting process brings the three points together from distinct directions, tracing out a cone over the three points. The ﬁrst order neighborhood of the vertex in this cone has multiplicity 3, and is the same as the complete ﬁrst order neighborhood in the plane of this vertex.

For those familiar with the theory of valuations in birational geometry [ZS76, Vol. II, Ch. VI], the lexicographic and reverse lexicographic orders have simple interpretations. Recall that if $X$ is a variety of dimension $n$, and

$F:X={Z}_{0}\supset {Z}_{1}\supset {Z}_{2}\supset \dots \supset {Z}_{n}$

is a ﬂag of subvarieties, ${codim}_{X}\left({Z}_{i}\right)=i$, with ${Z}_{i}$ smooth at the generic point of ${Z}_{i+1}$, then we can deﬁne a rank $n$ valuation ${v}_{F}$ on $X$ as follows: For each $i=1,\dots ,n-1$, ﬁx ${f}_{i}$ to be a function on ${Z}_{i-1}$ with a $1st$ order zero on ${Z}_{i}$. Then for any function $f$, we can deﬁne ${e}_{1}={ord}_{{Z}_{1}}\left(f\right)$, ${e}_{2}={ord}_{{Z}_{2}}\left(\left(f∕{f}_{1}^{{e}_{1}}\right){\mid }_{{Z}_{1}}\right)$, etc., and ${v}_{F}\left(f\right)=\left({e}_{1},\dots ,{e}_{n}\right)\in {\text{Z}}^{n}$, where the value group ${\text{Z}}^{n}$ is ordered lexicographically. The arbitrarily chosen ${f}_{i}$ are not needed to compare two functions $f$, $g$: We have ${v}_{F}\left(f\right)\succ {v}_{F}\left(g\right)$ if and only if ${ord}_{{Z}_{1}}\left(f∕g\right)>0$, or if this order is zero and ${ord}_{{Z}_{2}}\left(\left(f∕g\right){\mid }_{{Z}_{1}}\right)>0$, and so forth. Such a valuation also deﬁnes an order on each graded piece ${S}_{d}$ of the homogeneous coordinate ring: take any ${f}_{0}\in {S}_{d}$ and say $f>g$ if and only if ${v}_{F}\left(f∕{f}_{0}\right)\succ {v}_{F}\left(g∕{f}_{0}\right)$. More generally, one may take the ${Z}_{i}$ to be subvarieties of a variety ${X}^{\prime }$ dominating $X$ and pull back functions to ${X}^{\prime }$ before computing ${v}_{F}$.

The lexicographic order on monomials of each degree of $\text{}Pn\text{}$ is now induced by the ﬂag

$\text{}Pn\text{}\supset V\left({x}_{0}\right)\supset V\left({x}_{0},{x}_{1}\right)\supset \dots \supset V\left({x}_{0},\dots ,{x}_{n-1}\right).$

For example, the ﬁrst step in the comparison deﬁning ${v}_{F}\left({x}^{A}∕{f}_{0}\right)\succ {v}_{F}\left({x}^{B}∕{f}_{0}\right)$ has the eﬀect of asking if ${a}_{0}-{b}_{0}>0$.

The reverse lexicographic order is induced by a ﬂag on a blowup $X$ of $\text{}Pn\text{}$: First blow up $V\left({x}_{0},\dots ,{x}_{n-1}\right)$ and let ${E}_{1}$ be the exceptional divisor. Next blow up the proper transform of $V\left({x}_{0},\dots ,{x}_{n-2}\right)$, and let ${E}_{2}$ be this exceptional divisor. Iterating, we can deﬁne a ﬂag

$X\supset {E}_{1}\supset {E}_{1}\cap {E}_{2}\supset \dots \supset {E}_{1}\cap \dots \cap {E}_{n}$

which induces the reverse lexicographic order on monomials in each degree. For example, looking at the aﬃne piece of the ﬁrst blow up obtained by substituting ${x}_{0}={x}_{0}^{\prime }{x}_{n-1},\dots ,{x}_{n-2}={x}_{n-2}^{\prime }{x}_{n-1}$, the power of ${x}_{n-1}$ in the transform of ${x}^{A}$ is ${a}_{0}+\dots +{a}_{n-1}$, which is the order of vanishing of this monomial on ${E}_{1}$. Thus, the ﬁrst step in the comparison deﬁning ${v}_{F}\left({x}^{A}∕{f}_{0}\right)\succ {v}_{F}\left({x}^{B}∕{f}_{0}\right)$ has the eﬀect of asking if ${a}_{0}+\dots +{a}_{n-1}-{b}_{0}-\dots -{b}_{n-1}>0$, which is what we want.

Taking into account the equivalence between multiplicative orders and one-parameter subgroups, the process we have described in $S\left[t\right]$ is exactly the usual algorithm for computing Gröbner bases. It is computationally advantageous to set $t=1$ and dismiss our extra structure as unnecessary scaﬀolding, but it is conceptually advantageous to treat our viewpoint as what is “really” going on; many techniques of algebraic geometry become applicable to the family $Y$, and assist in analyzing the complexity of Gröbner bases. Moreover, this picture may help guide improvements to the basic algorithm. For example, for very large problems, it could be computationally more eﬃcient to degenerate to ${X}_{0}$ in several stages; this has not been tried in practice.

The coarsest measure of the complexity of a Gröbner basis is its maximum degree, which is the highest degree of a generator of the ideal $in\left(I\right)$ deﬁning ${X}_{0}$. This quantity is bounded by the better-behaved regularity of $in\left(I\right)$: The regularity of an ideal $I$ is the maximum over all $i$ of the degree minus $i$ of any minimal $i$th syzygy of $I$, treating generators as $0$th syzygies. When $I$ is the largest (the saturated) ideal deﬁning a scheme $X$, we call this the regularity of $X$. We take up regularity in detail in Section 3; here it suﬃces to know that regularity is upper semi-continuous on ﬂat families, i.e. the regularity can only stay the same or go up at special ﬁbers.

Let $reg\left(I\right)$ denote the regularity of $I$, and ${reg}_{0}\left(I\right)$ denote the highest degree of a generator of $I$. In our case, $t=0$ is the only special ﬁber, and the above says that

${reg}_{0}\left(I\right)\le reg\left(I\right)\le reg\left(in\left(I\right)\right)\ge {reg}_{0}\left(in\left(I\right)\right),$

where ${reg}_{0}\left(I\right)$ can be immediately determined from the input data, and ${reg}_{0}\left(in\left(I\right)\right)$ is the degree-complexity of the Gröbner basis computation. In practice, each of these inequalities are often strict.

However when $k$ is inﬁnite, then for any set of coordinates for $\text{}Pn\text{}$ chosen from a dense open set $U\subset GL\left(n+1\right)$ of possibilities, Galligo ([Gal74]; see also [BS87b]) has shown that the limiting ideal $in\left(I\right)$ takes on a very special form: $in\left(I\right)$ is invariant under the action of the Borel subgroup of upper triangular matrices in $GL\left(n+1\right)$. This imposes strong geometric conditions on ${X}_{0}$. In particular, the associated primes of $in\left(I\right)$ are also Borel-ﬁxed, so they are all of the form $\left({x}_{0},\dots ,{x}_{i}\right)$ for various $i$. This means that the components of ${X}_{0}$ are supported on members of a ﬂag.

In characteristic zero, it is shown in [BS87a] that the regularity of a Borel-ﬁxed ideal is exactly the maximum of the degrees of its generators, or in our notation, that $reg\left(in\left(I\right)\right)={reg}_{0}\left(in\left(I\right)\right)$ when $in\left(I\right)$ is Borel-ﬁxed. Thus, for generic coordinates in characteristic zero, the degree-complexity of computing Gröbner bases breaks down into two eﬀects: the gap ${reg}_{0}\left(I\right)\le reg\left(I\right)$ between the input degrees and the regularity of $X$, and the gap $reg\left(I\right)\le reg\left(in\left(I\right)\right)$ allowed by upper-semicontinuity.

A combination of theoretical results, hunches and experience guides the practitioner in assessing the ﬁrst gap; what about the second? Does the regularity have to jump at all? One can easily ﬁnd examples of ideals and total orders exhibiting such a jump, but in [BS87a], it is shown that for the reverse lexicographic order, in generic coordinates and any characteristic, there is no jump: $reg\left(I\right)=reg\left(in\left(I\right)\right)$, so in characteristic zero we have

${reg}_{0}\left(in\left(I\right)\right)=reg\left(I\right).$

In this sense, this order is an optimal choice: For the reverse lexicographic order, the degree-complexity of a Gröbner basis computation is exactly the regularity of the input data. This agrees with experience; computations made on the same inputs using the lexicographic order can climb to much higher degrees than the reverse lexicographic order, in practice.

For many applications, one is free to choose any order, but some problems restrict us to using orders satisfying combinatorial properties which the reverse lexicographic order fails to satisfy. An example, developed further in Section 2, is that of eliminating variables, or equivalently, of computing projections. To compute the intersection of $I$ with a subring $R=k\left[{x}_{i},\dots ,{x}_{n}\right]$, it is necessary to use an order which in each degree sorts all monomials not in $R$ ahead of any monomial in $R$. The lexicographic order is an example of such an order, for each $i$ simultaneously. This strength comes at a cost; we are paying in regularity gaps for properties we may not need in a particular problem. An optimal order if you need one speciﬁc projection (in the same sense as above) is constructed by sorting monomials by total degree in the variables to be eliminated, and then breaking ties using the reverse lexicographic order. See [BS87b] for this result, and a generalization to the problem of optimally reﬁning any nonstrict order.

Using this elimination order, one ﬁnds that the inherent degree-complexity of a computation is given not by the regularity of $X$ itself, but rather by the regularity of the ﬂat projection ${X}^{\prime }$ of $X$, which is the central ﬁber of a ﬂat family which animates the desired projection of $X$ as $t\to 0$. The jump in regularity between $X$ and ${X}^{\prime }$ is unavoidable; by choosing an optimal order, we avoid the penalty of a further jump in regularity between ${X}^{\prime }$ and ${X}_{0}$.

The regularity of algebraic varieties or schemes $X$ is far from being well understood, but there is considerable interest in its study; this computational interpretation of regularity as the inherent degree-complexity of an ideal is but one more log on the ﬁre.

From a theoretical computer science perspective, the full complexity of computing Gröbner bases is determined not merely by the highest degree ${reg}_{0}\left(I\right)$ in the basis, but by the total number of arithmetic operations in the ﬁeld $k$ required to compute this basis. This has not been analyzed in general, but for $0$-dimensional ideals $I$, Lakshman and Lazard ([Lak91], [LL91]) have shown that the complexity of computing reduced Gröbner bases is bounded by a polynomial in ${d}^{n}$, where $d$ is the maximum degree of the generators, and $n$ is the number of variables.

2 Gröbner Bases

Let $S=k\left[{x}_{0},\dots ,{x}_{n}\right]$ be a graded polynomial ring over the ﬁeld $k$, and let $I\subset S$ be a homogeneous ideal.

Let ${S}_{d}$ denote the ﬁnite vector space of all homogeneous, degree d polynomials in $S$, so $S={S}_{0}\oplus {S}_{1}\oplus \dots \oplus {S}_{d}\oplus \dots$. Writing $I$ in the same manner as $I={I}_{0}\oplus {I}_{1}\oplus \dots \oplus {I}_{d}\oplus \dots$, we have ${I}_{d}\subset {S}_{d}$ for each $d$. Recall that the Hilbert function of $I$ is deﬁned to be the function $p\left(d\right)=dim\left({I}_{d}\right)$, for $d\ge 0$.

A total order $>$ on the monomials of $S$ is said to be multiplicative if whenever ${x}^{A}>{x}^{B}$ for two monomials ${x}^{A}$, ${x}^{B}$, then ${x}^{C}{x}^{A}>{x}^{C}{x}^{B}$ for all monomials ${x}^{C}$. This condition insures that if the terms of a polynomial are in order with respect to $>$, then they remain in order after multiplication by a monomial.

Deﬁnition 2.1 Let $>$ be a multiplicative order. For a homogeneous polynomial $f={c}_{1}{x}^{{A}_{1}}+\dots +{c}_{m}{x}^{{A}_{m}}$ with ${x}^{{A}_{1}}>\dots >{x}^{{A}_{m}}$, deﬁne the initial term $in\left(f\right)$ to be the lead (that is, the largest) term ${c}_{1}{x}^{{A}_{1}}$ of $f$. For a homogeneous ideal $I\subset S$, deﬁne the initial ideal $in\left(I\right)$ to be the monomial ideal generated by the lead terms of all elements of $I$.

Note that the deﬁnitions of $in\left(f\right)$ and $in\left(I\right)$ depend on the choice of multiplicative order $>$. See [BM88] and [MR88] for characterizations of the ﬁnite set of $in\left(I\right)$ realized as the order $>$ varies.

Fix a multiplicative order $>$ on $S$.

Proposition 2.2 (Macaulay) I and in(I) have the same Hilbert function.

Proof. ([Mac27]) The lead terms of ${I}_{d}$ span $in{\left(I\right)}_{d}$, because every monomial ${x}^{A}\in in\left(I\right)$ is itself the lead term $in\left(f\right)$ of some polynomial $f\in I$: Since ${x}^{A}={x}^{C}{x}^{B}$ for some ${x}^{B}=in\left(g\right)$ with $g\in I$, we have ${x}^{A}=in\left(f\right)$ for $f={x}^{C}g$.

Choose a $k$-basis ${B}_{d}\subset {I}_{d}$ with distinct lead terms, and let $in\left({B}_{d}\right)$ be the set of lead terms of ${B}_{d}$; $in\left({B}_{d}\right)$ has cardinality $p\left(d\right)=dim\left({I}_{d}\right)$. Since any element of ${I}_{d}$ is a linear combination of elements of ${B}_{d}$, any lead term of ${I}_{d}$ is a scalar multiple of an element of $in\left({B}_{d}\right)$. Thus, $in\left({B}_{d}\right)$ is a basis for $in{\left(I\right)}_{d}$, so $p\left(d\right)=dim\left(in{\left(I\right)}_{d}\right).$     _

One can compute the Hilbert function of $I$ by ﬁnding $in\left(I\right)$ and applying this result; see [MM83], [BCR91], and [BS92b].

Corollary 2.3 The monomials of S which don’t belong to $in\left(I\right)$ form a $k$-basis for $S∕I$.

Proof. These monomials are linearly independent in $S∕I$, because any linear relation among them is a polynomial belonging to $I$, and all such polynomials have lead terms belonging to $in\left(I\right)$. These monomials can be seen to span $S∕I$ by a dimension count, applying Proposition 2.2.     _

Two examples of multiplicative orders are the lexicographic order and the reverse lexicographic order. ${x}^{A}>{x}^{B}$ in the lexicographic order if the ﬁrst nonzero coordinate of $A-B$ is positive. For example, if $S=k\left[w,x,y,z\right]$, then $w>x>y>z$ in ${S}_{1}$, and

${w}^{2}>wx>wy>wz>{x}^{2}>xy>xz>{y}^{2}>yz>{z}^{2}$

in ${S}^{2}$.

${x}^{A}>{x}^{B}$ in the reverse lexicographic order if the last nonzero coordinate of $A-B$ is negative. For example, if $S=k\left[w,x,y,z\right]$, then $w>x>y>z$ in ${S}_{1}$, and

${w}^{2}>wx>{x}^{2}>wy>xy>{y}^{2}>wz>xz>yz>{z}^{2}$

in ${S}^{2}$. These two orders agree on ${S}_{1}$, but diﬀer on the monomials of $S$ of degree $>1$ when $n\ge 2$.

The lexicographic order has the property that for each subring $k\left[{x}_{i},\dots ,{x}_{n}\right]\subset S$ and each polynomial $f\in S$, $f\in k\left[{x}_{i},\dots ,{x}_{n}\right]$ if and only if $in\left(f\right)\in k\left[{x}_{i},\dots ,{x}_{n}\right]$. The reverse lexicographic order has the property that for each $f\in k\left[{x}_{0},\dots ,{x}_{i}\right]$, ${x}_{i}$ divides $f$ if and only if ${x}_{i}$ divides $in\left(f\right)$.

One can anticipate the applications of these properties by considering a $k$-basis ${B}_{d}\subset {I}_{d}$ with distinct lead terms, as in the proof of Proposition 2.2. With respect to the lexicographic order, ${B}_{d}\cap k\left[{x}_{i},\dots ,{x}_{n}\right]$ is then a $k$-basis for ${I}_{d}\cap k\left[{x}_{i},\dots ,{x}_{n}\right]$ for each $i$. With respect to the reverse lexicographic order, ${B}_{d}\cap \left({x}_{n}\right)$ is then a $k$-basis for ${I}_{d}\cap \left({x}_{n}\right)$. Thus, these orders enable us to ﬁnd polynomials in an ideal which do not involve certain variables, or which are divisible by a certain variable. For a given degree $d$, one could construct such a basis ${B}_{d}$ by applying Gaussian elimination to an arbitrary $k$-basis for ${I}_{d}$. However, this cannot be done for all $d$ at once; such a computation would be inﬁnite. We will ﬁnesse this diﬃculty by instead constructing a ﬁnite set of elements of I whose monomial multiples yield polynomials in $I$ with every possible lead term.

Such sets can be described as follows:

Deﬁnition 2.4 A list $F=\left[{f}_{1},\dots ,{f}_{r}\right]\subset I$ is a (minimal) Gröbner basis for $I$ if $in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)$ (minimally) generate $in\left(I\right)$.

$in\left(I\right)$ is ﬁnitely generated because $S$ is Noetherian, so Gröbner bases exist for any ideal I.

The order of the elements of $F$ is immaterial to this deﬁnition, so $F$ can be thought of as a set. We are using list notation for $F$ because we are going to consider algorithms for which the order of the elements is signiﬁcant. For convenience, we shall extend the notation of set intersections and containments to the lists $F$.

A minimal set of generators for an ideal $I$ need not form a Gröbner basis for I. For example, if $S=k\left[x,y\right]$ and $I=\left({x}^{2}+{y}^{2},xy\right)$, then with respect to the lexicographic order, $in\left({x}^{2}+{y}^{2}\right)={x}^{2}$ and $in\left(xy\right)=xy$. Yet $y\left({x}^{2}+{y}^{2}\right)-x\left(xy\right)={y}^{3}\in I$, so ${y}^{3}\in in\left(I\right)$. Thus, any Gröbner basis for $I$ must include ${y}^{3}$; it can be shown that $in\left(I\right)=\left({x}^{2},xy,{y}^{3}\right)$ and $\left[{x}^{2}+{y}^{2},xy,{y}^{3}\right]$ is a Gröbner basis for $I$.

On the other hand,

Lemma 2.5 If $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ is a Gröbner basis for $I$, then ${f}_{1},\dots ,{f}_{r}$ generate $I$.

Proof. For each degree $d$, we can construct a $k$-basis ${B}_{d}\subset {I}_{d}$ with distinct lead terms, whose elements are monomial multiples of ${f}_{1},\dots ,{f}_{r}$: For each ${x}^{A}\in in{\left(I\right)}_{d}$, ${x}^{A}$ is a scalar multiple of ${x}^{C}in\left({f}_{i}\right)$ for some ${x}^{C}$ and some $i$; include ${x}^{C}{f}_{i}$ in the set ${B}_{d}$. Thus, the monomial multiples of ${f}_{1},\dots ,{f}_{r}$ span $I$.     _

Proposition 2.6 (Spear, Trinks) Let $R\subset S$ be the subring $R=k\left[{x}_{i},\dots ,{x}_{n}\right]$. If $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ is a Gröbner basis for the ideal $I$ with respect to the lexicographic order, then $F\cap R$ is a Gröbner basis for the ideal $I\cap R$. In particular, $F\cap R$ generates $I\cap R$.

Proof. ([Spe77], [Zac78], [Tri78]) Let $f\in I\cap R$; $in\left(f\right)$ is a multiple of $in\left({f}_{i}\right)$ for some $i$. Since $in\left(f\right)\in R$, $in\left({f}_{i}\right)\in R$, so ${f}_{i}\in R$. Thus, $F\cap R$ is a Gröbner basis for $I\cap R$. By Lemma 2.5, $F\cap R$ generates $I\cap R$.     _

Proposition 2.6 has the following geometric application: If $I$ deﬁnes the subscheme $X\subset {\text{P}}^{n}$, then $I\cap k\left[{x}_{i},\dots ,{x}_{n}\right]$ deﬁnes the projection of $X$ to ${\text{P}}^{n-i}=Proj\left(k\left[{x}_{i},\dots ,{x}_{n}\right]\right)$.

Recall that the saturation $Isat$ of $I$ is deﬁned to be the largest ideal deﬁning the same subscheme $X\subset {\text{P}}^{n}$ as $I$. $Isat$ can be obtained by taking an irredundant primary decomposition for $I$, and removing the primary ideal whose associated prime is the irrelevant ideal $\left({x}_{0},\dots ,{x}_{n}\right)$. $I$ is saturated if $I=Isat$.

If the ideal $I$ is saturated, and deﬁnes a ﬁnite set of points $X\subset {\text{P}}^{n}$, then $I\cap k\left[{x}_{n-1},{x}_{n}\right]$ is a principal ideal $\left(f\right)$, where $\left\{f=0\right\}$ is the image of the projection of $X$ to ${\text{P}}^{1}=Proj\left(k\left[{x}_{n-1},{x}_{n}\right]\right)$. Given a linear factor of $f$ of the form $\left(b{x}_{n-1}-a{x}_{n}\right)$, we can make the substitution ${x}_{n-1}=az$, ${x}_{n}=bz$ for a new variable $z$, to obtain from $I$ an ideal $J\subset k\left[{x}_{0},\dots ,{x}_{n-2},z\right]$ deﬁning a ﬁnite set of points in ${\text{P}}^{n-1}$. For each point $\left({c}_{0},\dots ,{c}_{n-2},d\right)$ in the zero locus of $J$, $\left({c}_{0},\dots ,{c}_{n-2},ad,bd\right)$ is a point in the zero locus of $I$.

If $X\subset {\text{P}}^{n-1}$ is of dimension $1$ or greater, then in general $I\cap k\left[{x}_{n-1},{x}_{n}\right]=\left(0\right)$, because a generic projection of $X$ to ${\text{P}}^{1}$ is surjective. In this case, an arbitrary substitution ${x}_{n-1}=az$, ${x}_{n}=bz$ can be made, and the process of projecting to ${\text{P}}^{1}$ iterated. Thus, the lexicographic order can be used to ﬁnd solutions to systems of polynomial equations.

Recall that the ideal quotient $\left(I:f\right)$ is deﬁned to be the ideal $\left\{\phantom{\rule{0em}{0ex}}g\in S\phantom{\rule{0em}{0ex}}|\phantom{\rule{0em}{0ex}}fg\in I\phantom{\rule{0em}{0ex}}\right\}$. Since $S$ is Noetherian, the ascending chain of ideals $\left(I:f\right)\subset \left(I:{f}^{2}\right)\subset \left(I:{f}^{3}\right)\subset \dots$ is stationary; call this stationary limit .

Proposition 2.7 If $\left[{x}_{n}^{{a}_{1}}{f}_{1},\dots ,{x}_{n}^{{a}_{r}}{f}_{r}\right]$ is a Gröbner basis for the ideal $I$ with respect to the reverse lexicographic order, and if none of ${f}_{1},\dots ,{f}_{r}$ are divisible by ${x}_{n}$, then $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ is a Gröbner basis for the ideal $\left(I:{x}_{n}^{\infty }\right)$. In particular, ${f}_{1},\dots ,{f}_{r}$ generate $\left(I:{x}_{n}^{\infty }\right)$.

Proof. ([Bay82], [BS87a]) We have $F\subset \left(I:{x}_{n}^{\infty }\right)$. Let $f\in \left(I:{x}_{n}^{\infty }\right)$; ${x}_{n}^{m}f\in I$ for some $m$, so $in\left({x}_{n}^{m}f\right)$ is a multiple of $in\left({x}_{n}^{{a}_{i}}{f}_{i}\right)$ for some $i$. Since ${f}_{i}$ is not divisible by ${x}_{n}$, $in\left({f}_{i}\right)$ is not divisible by ${x}_{n}$, so $in\left(f\right)$ is a multiple of $in\left({f}_{i}\right)$. Thus, $F$ is a Gröbner basis for $\left(I:{x}_{n}^{\infty }\right)$. By Lemma 2.5, ${f}_{1},\dots ,{f}_{r}$ generate $\left(I:{x}_{n}^{\infty }\right)$.     _

If $I={q}_{0}\cap {q}_{1}\cap \dots \cap {q}_{t}$ is a primary decomposition of $I$, then $\left(I:{x}_{n}^{\infty }\right)=\left(\cap {q}_{i}:{x}_{n}^{\infty }\right)=\cap \left({q}_{i}:{x}_{n}^{\infty }\right)$. We have $\left({q}_{i}:{x}_{n}^{\infty }\right)=\left(1\right)$ if the associated prime ${p}_{i}$ of ${q}_{i}$ contains ${x}_{n}$, and $\left({q}_{i}:{x}_{n}^{\infty }\right)={q}_{i}$ otherwise. Thus, if $I$ deﬁnes the subscheme $X\subset {\text{P}}^{n}$, then $\left(I:{x}_{n}^{\infty }\right)$ deﬁnes the subscheme consisting of those primary components of $X$ not supported on the hyperplane $\left\{{x}_{n}=0\right\}$.

$\left(I:{x}_{n}^{\infty }\right)$ is saturated, because it cannot have $\left({x}_{0},\dots ,{x}_{n}\right)$ as an associated prime. If ${x}_{n}$ belongs to none of the associated primes of $I$ except $\left({x}_{0},\dots ,{x}_{n}\right)$, or equivalently if $\left\{{x}_{n}=0\right\}$ is a generic hyperplane section of $X\subset {\text{P}}^{n}$, then $\left(I:{x}_{n}^{\infty }\right)=Isat$. Thus, the reverse lexicographic order can be used to ﬁnd the saturation of $I$.

One of the most important uses of Gröbner bases is that they lead to canonical representations of polynomials modulo an ideal $I$, i.e. a division algorithm in which every $f\in S$ is written canonically as $f=\sum {g}_{i}{f}_{i}+h$, where $\left[{f}_{1},\dots ,{f}_{r}\right]$ is a Gröbner basis for $I$, and $h$ is the remainder after division.

Recall the division algorithm for inhomogeneous, univariate polynomials $f\left(x\right)$, $g\left(x\right)\in k\left[x\right]$: Let $in\left(f\right)$ denote the highest degree term of $f$. The remainder of $g$ under division by $f$ can be recursively deﬁned by

${R}_{f}\left(g\right)={R}_{f}\left(g-c{x}^{a}f\right)$

if $in\left(f\right)$ divides $in\left(g\right)$, where $c{x}^{a}=in\left(g\right)∕in\left(f\right)$, and by

${R}_{f}\left(g\right)=g$

otherwise.

Division can be generalized to homogeneous polynomials ${f}_{1},\dots ,{f}_{r},g\in S$, given a multiplicative order on $S$ ([Hir64], [Bri73], [Gal74], [Sch80]): The remainder ${R}_{F}\left(g\right)$ of $g$ under division by the list of polynomials $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ can be recursively deﬁned by

${R}_{F}\left(g\right)={R}_{F}\left(g-c{x}^{A}{f}_{i}\right)$

for the least $i$ so $in\left(g\right)$ is a multiple $c{x}^{A}$ of $in\left({f}_{i}\right)$, and by

${R}_{F}\left(g\right)=in\left(g\right)+{R}_{F}\left(g-in\left(g\right)\right)$

if $in\left(g\right)$ is not a multiple of any $in\left({f}_{i}\right)$. ${R}_{F}\left(g\right)$ is an element of $S$.

Thus, the fate of $in\left(g\right)$ depends on whether or not $in\left(g\right)\in \left(in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)\right)$. Let $I$ be the ideal generated by ${f}_{1},\dots ,{f}_{r}$. If $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ fails to be a Gröbner basis for $I$, then the remainder is poorly behaved. For example, with respect to the lexicographic order on $k\left[x,y\right]$,

${R}_{\left[xy,{x}^{2}+{y}^{2}\right]}\left({x}^{2}y\right)={x}^{2}y-x\left(xy\right)=0,$

but

${R}_{\left[{x}^{2}+{y}^{2},xy\right]}\left({x}^{2}y\right)={x}^{2}y-y\left({x}^{2}+{y}^{2}\right)=-{y}^{3},$

so the remainder ${R}_{F}\left(g\right)$ is dependent on the order of the list $F$. Note that ${x}^{2}y\in \left({x}^{2}+{y}^{2},xy\right)$.

If on the other hand, $F$ is a Gröbner basis for the ideal $I$, then ${R}_{F}\left(g\right)$ is a $k$-linear combination of monomials not belonging to $in\left(I\right)$. By Corollary 2.3, these monomials form a $k$-basis for $S∕I$, so each polynomial in $S$ has a unique representation in terms of this $k$-basis, modulo the ideal $I$. The remainder gives this unique representation, and is independent of the order of $F$ (but dependent on the multiplicative order chosen for the monomials of $S$). In particular, ${R}_{F}\left(g\right)=0$ if and only if $g\in I$.

An algorithm for computing a Gröbner basis for $I$ from a set of generators for $I$ was ﬁrst given by Buchberger ([Buc65], [Buc76]). This algorithm was discovered independently by Spear ([Spe77], [Zac78]), Bergman [Ber78], and Schreyer [Sch80]. It was termed the division algorithm by Schreyer, after the division theorem of Hironaka ([Hir64], [Bri73], [Gal74]).

Deﬁne $S\left({f}_{i},{f}_{j}\right)$ for $i by

$S\left({f}_{i},{f}_{j}\right)=b{x}^{B}{f}_{i}-c{x}^{C}{f}_{j},$

where ${x}^{A}=b{x}^{B}in\left({f}_{i}\right)=c{x}^{C}in\left({f}_{j}\right)$ is the least common multiple of $in\left({f}_{i}\right)$ and $in\left({f}_{j}\right)$. $b{x}^{B}{f}_{i}$ and $c{x}^{C}{f}_{j}$ each have ${x}^{A}$ as lead term, so ${x}^{A}$ cancels out in $S\left({f}_{i},{f}_{j}\right)$, and ${x}^{A}>in\left(S\left({f}_{i},{f}_{j}\right)\right)$.

If $F$ is a Gröbner basis for the ideal $I$, then ${R}_{F}\left(S\left({f}_{i},{f}_{j}\right)\right)=0$ for each $i, since $S\left({f}_{i},{f}_{j}\right)\in I$. Conversely,

Proposition 2.8 (Buchberger) If ${R}_{F}\left(S\left({f}_{i},{f}_{j}\right)\right)=0$ for each $i, then $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ is a Gröbner basis for the ideal $I=\left({f}_{1},\dots ,{f}_{r}\right)$.

See [Buc65], [Buc76]. We postpone a proof until the theory has been extended to $S$-modules. This result can also be thought of as an explicit converse to the assertion that if $F$ is a Gröbner basis, then division is independent of the order of $F$: Whenever we have a choice in division between subtracting oﬀ a multiple of ${f}_{i}$ and a multiple of ${f}_{j}$, the diﬀerence is a multiple of $S\left({f}_{i},{f}_{j}\right)$. If division is independent of the order of $F$, then these diﬀerences must have remainder zero, so by Proposition 2.8, $F$ is a Gröbner basis.

As sketched in Section 1, Proposition 2.8 can be used to compute a Gröbner basis from a set of generators ${f}_{1},\dots ,{f}_{r}$ for the ideal $I$: For each $i so ${f}_{r+1}={R}_{F}\left(S\left({f}_{i},{f}_{j}\right)\right)\ne 0$, adjoin ${f}_{r+1}$ to the list $F=\left[{f}_{1},\dots ,{f}_{r}\right]$. Note that ${f}_{r+1}\in I$. By iterating until no new polynomials are found, a Gröbner basis $F$ is obtained for $I$. This process terminates because $S$ is Noetherian, and each new basis element corresponds to a monomial not in the ideal generated by the preceding lead terms.

We now extend this theory to $S$-modules. Let $M$ be a graded, ﬁnitely generated $S$-module, given by the exact sequence of graded $S$-modules

${M}_{1}\stackrel{F}{\to }{M}_{0}\to M\to 0,$

where ${M}_{0}=S{e}_{01}\oplus \dots \oplus S{e}_{0q}$ and ${M}_{1}=S{e}_{11}\oplus \dots \oplus S{e}_{1r}$ are free $S$-modules with $deg\left({e}_{ij}\right)={d}_{ij}$ for each $i$, $j$. We now think of $F$ both as a list $\left[{f}_{1},\dots ,{f}_{r}\right]$ of module elements, and as a map between free modules: Let ${f}_{i}=F\left({e}_{1i}\right)\ne 0$ for $i=1,\dots ,r$, and let $I\subset {M}_{0}$ be the homogeneous submodule generated by ${f}_{1},\dots ,{f}_{r}$. Thus, $M={M}_{0}∕I$.

A monomial of ${M}_{0}$ is an element of the form ${x}^{A}{e}_{0i}$; such an element has degree $deg\left({x}^{A}\right)+{d}_{0i}$. An order on the monomials of ${M}_{0}$ is multiplicative if whenever ${x}^{A}{e}_{0i}>{x}^{B}{e}_{0j}$, then ${x}^{C}{x}^{A}{e}_{0i}>{x}^{C}{x}^{B}{e}_{0j}$ for all ${x}^{C}\in S$. For some applications, such as developing a theory of Gröbner bases over quotients of $S$, one wants this order to be compatible with an order on $S$: If ${x}^{A}>{x}^{B}$, then one wants ${x}^{A}{e}_{0i}>{x}^{B}{e}_{0i}$ for $i=1,\dots ,r$. The orders encountered in practice invariably satisfy this second condition, but it does not follow from the ﬁrst, and we do not require it here.

One way to extend a multiplicative order on $S$ to a compatible multiplicative order on ${M}_{0}$ is to declare ${x}^{A}{e}_{0i}>{x}^{B}{e}_{0j}$ if $i, or if $i=j$ and ${x}^{A}>{x}^{B}$. Another way is to assign monomials ${x}^{{C}_{1}},\dots ,{x}^{{C}_{q}}$ in $S$ to the basis elements ${e}_{01},\dots ,{e}_{0q}$ of ${M}_{0}$, and to declare ${x}^{A}{e}_{0i}>{x}^{B}{e}_{0j}$ if ${x}^{A+{C}_{i}}>{x}^{B+{C}_{j}}$, or if $A+{C}_{i}=B+{C}_{j}$ and $i.

Fix a choice of a multiplicative order $>$ on ${M}_{0}$. The constructions developed for $S$ carry over intact to ${M}_{0}$, with the same proofs ([Gal79], [Sch80], [Bay82]): Given an element $f\in {M}_{0}$, deﬁne $in\left(f\right)$ to be the lead term of $f$. Deﬁne $in\left(I\right)$ to be the submodule generated by the lead terms of all elements of $I\subset {M}_{0}$; $in\left(I\right)$ is a monomial submodule of ${M}_{0}$ with the same Hilbert function as $I$. Deﬁne $F=\left[{f}_{1},\dots ,{f}_{r}\right]\subset I$ to be a Gröbner basis for $I$ if $in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)$ generate $in\left(I\right)$; a set of generators for $I$ need not be a Gröbner basis for $I$, but a Gröbner basis for $I$ generates $I$. Given an element $g\in {M}_{0}$, deﬁne ${R}_{F}\left(g\right)\in {M}_{0}$ exactly as was done for the free module $S$. If $F$ is a Gröbner basis for $I$, then ${R}_{F}\left(g\right)=0$ if and only if $g\in I$.

The quotient of $g$ under division by ${f}_{1},\dots ,{f}_{r}$ can be recursively deﬁned by

${Q}_{F}\left(g\right)=c{x}^{A}{e}_{1i}+{Q}_{F}\left(g-c{x}^{A}{f}_{i}\right)$

for the least $i$ so $in\left(g\right)$ is a multiple $c{x}^{A}$ of $in\left({f}_{i}\right)$, and by

${Q}_{F}\left(g\right)={Q}_{F}\left(g-in\left(g\right)\right)$

if $in\left(g\right)$ is not a multiple of any $in\left({f}_{i}\right)$. The quotient is an element of ${M}_{1}$.

Following the recursive deﬁnitions of the remainder and quotient, it can be inductively veriﬁed that

$g=F\left({Q}_{F}\left(g\right)\right)+{R}_{F}\left(g\right).$

If $F$ is a Gröbner basis for $I$, and $g\in I$, then ${R}_{F}\left(g\right)=0$, so the quotient lifts $g$ to ${M}_{1}$. In this case, the quotient can be thought of as expressing $g$ in terms of ${f}_{1},\dots ,{f}_{r}$.

Deﬁne $S\left({f}_{i},{f}_{j}\right)$ for $i by

$S\left({f}_{i},{f}_{j}\right)=b{x}^{B}{f}_{i}-c{x}^{C}{f}_{j},$

if $in\left({f}_{i}\right)$ and $in\left({f}_{j}\right)$ have a least common multiple ${x}^{A}{e}_{0k}=b{x}^{B}in\left({f}_{i}\right)=c{x}^{C}in\left({f}_{j}\right)$. Leave $S\left({f}_{i},{f}_{j}\right)$ undeﬁned if $in\left({f}_{i}\right)$ and $in\left({f}_{j}\right)$ lie in diﬀerent summands of ${M}_{0}$, and so don’t have common multiples.

Recall that the module of syzygies of ${f}_{1},\dots ,{f}_{r}$ is deﬁned to be the kernel of the map $F$, which is the submodule of ${M}_{1}$ consisting of all $h\in {M}_{1}$ so $F\left(h\right)=0$. Thus, if $h={h}_{1}{e}_{11}+\dots +{h}_{r}{e}_{1r}$ is a syzygy, then ${h}_{1}{f}_{1}+\dots +{h}_{r}{f}_{r}=0$. Let $J\subset {M}_{1}$ denote the module of syzygies of ${f}_{1},\dots ,{f}_{r}$, and let $K\subset {M}_{1}$ denote the module of syzygies of $in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)$.

Deﬁne the map $in\left(F\right):{M}_{1}\to {M}_{0}$ by $in\left(F\right)\left({e}_{1i}\right)=in\left({f}_{i}\right)$; $K$ is the kernel of $in\left(F\right)$. For each $i so $S\left({f}_{i},{f}_{j}\right)$ is deﬁned, deﬁne ${t}_{ij}$ to be the element

${t}_{ij}=b{x}^{B}{e}_{1i}-c{x}^{C}{e}_{1j}\in {M}_{1},$

where ${x}^{A}{e}_{0k}=b{x}^{B}in\left({f}_{i}\right)=c{x}^{C}in\left({f}_{j}\right)$ is the least common multiple of $in\left({f}_{i}\right)$ and $in\left({f}_{j}\right)$, as before. $in\left(F\right)\left({t}_{ij}\right)=0$, so each ${t}_{ij}$ belongs to the syzygy module $K$. Observe that $F\left({t}_{ij}\right)=S\left({f}_{i},{f}_{j}\right)$.

Assign the following multiplicative order on ${M}_{1}$, starting from the order on ${M}_{0}$ ([Sch80]; see also [MM86]): Let ${x}^{A}{e}_{1i}>{x}^{B}{e}_{1j}$ if ${x}^{A}in\left({f}_{i}\right)>{x}^{B}in\left({f}_{j}\right)$, or if these terms are $k$-multiples of each other and $i. If the order on ${M}_{0}$ is compatible with an order on $S$, then this order on ${M}_{1}$ is compatible with the same order on $S$.

With respect to this order on ${M}_{1}$, we have

Lemma 2.9 The list $\left[\phantom{\rule{0em}{0ex}}{t}_{ij}\phantom{\rule{0em}{0ex}}\right]$ is a Gröbner basis for the module $K$ of syzygies of $in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)$.

Proof. Let $h\in {M}_{1}$, so $in\left(F\right)\left(h\right)=0$. Then $in\left(F\right)\left(in\left(h\right)\right)$ is canceled by $in\left(F\right)\left(h-in\left(h\right)\right)$ in ${M}_{0}$. Therefore, if $in\left(h\right)={x}^{A}{e}_{1i}$, then $h$ has another term ${x}^{B}{e}_{1j}$ so ${x}^{A}in\left({f}_{i}\right)$ and ${x}^{B}in\left({f}_{j}\right)$ are $k$-multiples of each other and $i. Thus, ${t}_{ij}$ is deﬁned and $in\left({t}_{ij}\right)$ divides $in\left(h\right)$, so $\left[\phantom{\rule{0em}{0ex}}{t}_{ij}\phantom{\rule{0em}{0ex}}\right]$ is a Gröbner basis for $K$.     _

Thus, the set $\left\{{t}_{ij}\right\}$ generates $K$. In general, the $\left[\phantom{\rule{0em}{0ex}}{t}_{ij}\phantom{\rule{0em}{0ex}}\right]$ are far from being a minimal Gröbner basis for $K$; we consider the eﬀects of trimming this list in Proposition 2.10 below.

Deﬁne

${s}_{ij}={t}_{ij}-{Q}_{F}\left(S\left({f}_{i},{f}_{j}\right)\right)$

whenever ${R}_{F}\left(S\left({f}_{i},{f}_{j}\right)\right)=0$. Note that $in\left({s}_{ij}\right)=in\left({t}_{ij}\right)$. Each ${s}_{ij}$ is the diﬀerence of two distinct elements of ${M}_{1}$, each of which is mapped by $F$ to $S\left({f}_{i},{f}_{j}\right)$, so $F\left({s}_{ij}\right)=0$. In other words, ${s}_{ij}$ belongs to the syzygy module $J$. Conversely,

Proposition 2.10 (Richman, Spear, Schreyer) Choose a set of pairs $T=\left\{\left(i,j\right)\right\}$ such that the set ${\left\{{t}_{ij}\right\}}_{\left(i,j\right)\in T}$ generates the module $K$ of syzygies of $in\left({f}_{1}\right),\dots ,in\left({f}_{r}\right)$. If ${R}_{F}\left(S\left({f}_{i},{f}_{j}\right)\right)=0$ for each $\left(i,j\right)\in T$, then

(a) $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ is a Gröbner basis for $I$;

(b) the set ${\left\{{s}_{ij}\right\}}_{\left(i,j\right)\in T}$ generates the module $J$ of syzygies of ${f}_{1},\dots ,{f}_{r}$.

Moreover,

(c) if ${\left[\phantom{\rule{0em}{0ex}}{t}_{ij}\phantom{\rule{0em}{0ex}}\right]}_{\left(i,j\right)\in T}$ is a Gröbner basis for $K$, then ${\left[\phantom{\rule{0em}{0ex}}{s}_{ij}\phantom{\rule{0em}{0ex}}\right]}_{\left(i,j\right)\in T}$ is a Gröbner basis for $J$.

Proof. ([Ric74], [Spe77], [Zac78], [Sch80]) First, suppose that ${\left[\phantom{\rule{0em}{0ex}}{t}_{ij}\phantom{\rule{0em}{0ex}}\right]}_{\left(i,j\right)\in T}$ is a Gröbner basis for $K$. Let $h\in J$, so $F\left(h\right)=0$. By the same reasoning as in the proof of Lemma 2.9, we can ﬁnd $\left(i,j\right)\in T$ so $in\left({t}_{ij}\right)$ divides $in\left(h\right)$. Since $in\left({s}_{ij}\right)=in\left({t}_{ij}\right)$, $in\left({s}_{ij}\right)$ also divides $in\left(h\right)$, so ${\left[\phantom{\rule{0em}{0ex}}{s}_{ij}\phantom{\rule{0em}{0ex}}\right]}_{\left(i,j\right)\in T}$ is a Gröbner basis for $J$, proving (c).

Now, suppose that ${\left\{{t}_{ij}\right\}}_{\left(i,j\right)\in T}$ merely generates $K$. Let ${T}^{\prime }$ be a set of pairs so ${\left[\phantom{\rule{0em}{0ex}}{t}_{\ell m}\phantom{\rule{0em}{0ex}}\right]}_{\left(\ell ,m\right)\in {T}^{\prime }}$ is a Gröbner basis for $K$. It is enough to construct a list ${\left[\phantom{\rule{0em}{0ex}}{u}_{\ell m}\phantom{\rule{0em}{0ex}}\right]}_{\left(\ell ,m\right)\in {T}^{\prime }}$ of elements of $J$, generated by ${\left\{{s}_{ij}\right\}}_{\left(i,j\right)\in T}$, so $in\left({u}_{\ell m}\right)=in\left({t}_{\ell m}\right)$ for all $\left(\ell ,m\right)\in {T}^{\prime }$. Then by the preceding argument, ${\left[\phantom{\rule{0em}{0ex}}{u}_{\ell m}\phantom{\rule{0em}{0ex}}\right]}_{\left(\ell ,m\right)\in {T}^{\prime }}$ is a Gröbner basis for $J$, so ${\left\{{s}_{ij}\right\}}_{\left(i,j\right)\in T}$ generates $J$.

Write each ${t}_{\ell m}=\sum {g}_{\ell mij}{t}_{ij}$, for $\left(\ell ,m\right)\in {T}^{\prime }$ and $\left(i,j\right)\in T$, in such a way that the terms of ${t}_{\ell m}$ and each term of each product ${g}_{\ell mij}{t}_{ij}$ map via $in\left(F\right)$ to multiples of the same monomial in ${M}_{0}$. In other words, ﬁnd a minimal expression for each ${t}_{\ell m}$, which avoids unnecessary cancellation. Then deﬁne

${u}_{\ell m}=\sum {g}_{\ell mij}{s}_{ij}.$

We have $in\left({u}_{\ell m}\right)=in\left({t}_{\ell m}\right)$, proving (b).

Let $f\in I$, and choose $g\in {M}_{1}$ so $f=F\left(g\right)$. Let $h\in {M}_{1}$ be the remainder of $g$ under division by ${\left[\phantom{\rule{0em}{0ex}}{u}_{\ell m}\phantom{\rule{0em}{0ex}}\right]}_{\left(\ell ,m\right)\in {T}^{\prime }}$; $f=F\left(h\right)$. Since $in\left(h\right)$ is not a multiple of any $in\left({u}_{\ell m}\right)=in\left({t}_{\ell m}\right)$, the lead term of $F\left(in\left(h\right)\right)$ is not canceled by any term of $F\left(h-in\left(h\right)\right)$. Therefore, if $in\left(h\right)=a{x}^{A}{e}_{1i}$, then $in\left({f}_{i}\right)$ divides $in\left(F\right)$. Thus, $F=\left[{f}_{1},\dots ,{f}_{r}\right]$ is a Gröbner basis for $I$, proving (a).     _

Proposition 2.8 follows as a special case of this result.

The above proof can be understood in terms of an intermediate initial form ${in}_{0}\left(h\right)$ for $h\in {M}_{1}$: Apply the map $in\left(F\right)$ separately to each term of $h$, and let ${x}^{A}\in {M}_{0}$ be the greatest monomial that occurs in the set of image terms. Deﬁne ${in}_{0}\left(h\right)$ to be the sum of all terms of $h$ which map via $in\left(F\right)$ to multiples of ${x}^{A}$. Then $in$ reﬁnes ${in}_{0}$, for according to the order we have deﬁned on ${M}_{1}$, $in\left(h\right)$ is the term of ${in}_{0}\left(h\right)$ lying in the summand of ${M}_{1}$ whose basis element ${e}_{i}$ has the smallest index $i$.

In this language, ${t}_{ij}={in}_{0}\left({t}_{ij}\right)={in}_{0}\left({s}_{ij}\right)$. Our expressions for the ${t}_{\ell m}$ have the property that each ${g}_{\ell mij}{t}_{ij}={in}_{0}\left({g}_{\ell mij}{t}_{ij}\right)$, with each term of each product for a given ${t}_{\ell m}$ mapping via $in\left(F\right)$ to multiples of the same monomial ${x}^{A}$. Thus, each ${in}_{0}\left({g}_{\ell mij}{s}_{ij}\right)={g}_{\ell mij}{t}_{ij}$; the tails ${g}_{\ell mij}\left({s}_{ij}-{in}_{0}\left({s}_{ij}\right)\right)$ stay out of our way, mapping termwise via $in\left(F\right)$ to monomials which are less than ${x}^{A}$ with respect to the order on ${M}_{0}$.

Observe that ${Q}_{F}\left(g\right)$ is a linear combination of monomials not belonging to $in\left(J\right)$, for any $g\in {M}_{0}$.

In [Buc79], Buchberger gives a criterion for selecting a set $T$ of pairs $\left(i,j\right)$ in the case where $I$ is an ideal: If $\left({i}_{0},{i}_{1}\right),\left({i}_{1},{i}_{2}\right),\dots ,\left({i}_{s-1},{i}_{s}\right)\in T$, and the least common multiple of $in\left({f}_{{i}_{0}}\right),in\left({f}_{{i}_{1}}\right),\dots ,in\left({f}_{{i}_{s}}\right)$ is equal to the least common multiple of $in\left({f}_{{i}_{0}}\right)$ and $in\left({f}_{{i}_{s}}\right)$, then $\left({i}_{0},{i}_{s}\right)$ need not belong to $T$. In other words, if ${t}_{{i}_{0}{i}_{s}}\in \left({t}_{{i}_{0}{i}_{1}},\dots ,{t}_{{i}_{s-1}{i}_{s}}\right)$, then the pair $\left({i}_{0},{i}_{s}\right)$ is unnecessary; this condition is equivalent to the condition of Proposition 2.10, for the case of an ideal.

Suppose that we wish to compute the syzygies of a given set of elements ${g}_{1},\dots ,{g}_{s}$ of ${M}_{0}$. To do this, compute a Gröbner basis ${f}_{1},\dots ,{f}_{r}$ for the submodule $I\subset {M}_{0}$ generated by ${g}_{1},\dots ,{g}_{s}$. Keep track of how to write each ${f}_{i}$ in terms of ${g}_{1},\dots ,{g}_{s}$. Using these expressions, each syzygy of ${f}_{1},\dots ,{f}_{r}$ can be mapped to a syzygy of ${g}_{1},\dots ,{g}_{s}$. These images generate the module of syzygies of ${g}_{1},\dots ,{g}_{s}$; the set of syzygies obtained in this way is not in general minimal.

Syzygies can be used to ﬁnd a minimal set of generators for a submodule $I\subset {M}_{0}$ from a given set of generators ${g}_{1},\dots ,{g}_{s}$: If ${h}_{1}{g}_{1}+\dots +{h}_{r}{g}_{r}=0$ is a syzygy of ${g}_{1},\dots ,{g}_{s}$ with ${h}_{1}\in k$, then ${g}_{1}=\left({h}_{2}{g}_{2}+\dots +{h}_{r}{g}_{r}\right)∕{h}_{1}$, so ${g}_{1}$ is not needed to generate $I$. All unnecessary generators can be removed in this way.

Alternatively, a careful implementation of Gröbner bases can directly ﬁnd minimal sets of generators for submodules: Starting from an arbitrary set of generators, we can eliminate unnecessary generators degree by degree, by removing those which reduce to zero under division by a Gröbner basis for the ideal generated by the preceding generators.

Either way, we can trim the set of syzygies computed via Gröbner bases for a given set of generators ${g}_{1},\dots ,{g}_{s}$ of $I$, to obtain a minimal set of generators for the syzygy module $J$. By starting with a minimal generating set for $I$, and iterating this method, a minimal free resolution can be found for $I$.

A beautiful application of these ideas yields a proof of the Hilbert syzygy theorem, that minimal free resolutions terminate (Schreyer [Sch80], [Sch91], for an exposition see also Eisenbud [Eis92]). At each stage of a resolution, order the Gröbner basis $F$ for $I$ in such a way that for each $i, letting $in\left({f}_{i}\right)=a{x}^{A}{e}_{0k}$ and $in\left({f}_{j}\right)=b{x}^{B}{e}_{0\ell }$, we have ${x}^{A}>{x}^{B}$ in the lexicographic order. If the variables ${x}_{1},\dots ,{x}_{m}$ are missing from the initial terms of the ${f}_{i}$, then the variables ${x}_{1},\dots ,{x}_{m+1}$ will be missing from the initial terms of the syzygies ${s}_{ij}$. Iterating, we run out of variables, so the resolution terminates.

3 Bounds

How hard are the algorithms in algebraic geometry? We describe some key bounds. The best known example is the bound established by G. Hermann [Her26] for ideal membership:

Theorem 3.1 (G. Hermann) Let $k$ be any ﬁeld, let $\left({f}_{1},...,{f}_{k}\right)\subset k\left[{x}_{1},...,{x}_{n}\right]$ and let $d=max\left(deg\left({f}_{i}\right)\right)$. If $g\in \left({f}_{1},...,{f}_{k}\right)$, then there is an expression

$g=\sum _{i=1}^{k}{a}_{i}{f}_{i}$

where $deg\left({a}_{i}\right)\le deg\left(g\right)+2{\left(kd\right)}^{{2}^{n-1}}$.

This type of bound is called “doubly exponential”. However, with the advent of the concept of coherent sheaf cohomology [Ser55] and the systematic study of vanishing theorems, it has become apparent that the vanishing of these groups in high degrees is almost always the most fundamental bound. The concept of an ideal being “m-regular” or “regular in degrees $\ge m$” was introduced by one of us [Mum66] by generalizing ideas of Castelnuovo:

Deﬁnition 3.2 1 Let $k$ be any ﬁeld, let $I\subset k\left[{x}_{0},\dots ,{x}_{n}\right]$ be an ideal generated by homogeneous polyomials, let ${I}_{d}$ be the homogeneous elements in $I$ of degree $d$, let $I$ be the corresponding sheaf of ideals in ${\mathsc{𝒪}}_{\text{}Pn\text{}}$, and let $I\left(d\right)$ be the ${d}^{th}$ twist of $I$. Then the following properties are equivalent and deﬁne the term “m-regular”:

(a) the natural map ${I}_{m}\to {H}^{0}\left(\mathsc{ℐ}\left(m\right)\right)$ is an isomorphism and ${H}^{i}\left(\mathsc{ℐ}\left(m-i\right)\right)$ $=\left(0\right)$, $1\le i\le n$

(b) the natural maps ${I}_{d}\to {H}^{0}\left(\mathsc{ℐ}\left(d\right)\right)$ are isomorphisms for all $d\ge m$ and ${H}^{i}\left(\mathsc{ℐ}\left(d\right)\right)$ = $\left(0\right)$ if $d+i\ge m$, $i\ge 1$.

(c) Take a minimal resolution of $I$ by free graded $k\left[X\right]$-modules:

$0\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}\stackrel{\stackrel{{r}_{n}}{\oplus }}{\alpha =1}\phantom{\rule{0em}{0ex}}k\left[x\right]\cdot {e}_{\alpha ,n}\phantom{\rule{0em}{0ex}}\stackrel{{\varphi }_{n}}{\to }\phantom{\rule{0em}{0ex}}\dots \stackrel{{\varphi }_{1}}{\to }\phantom{\rule{0em}{0ex}}\stackrel{\stackrel{{r}_{0}}{\oplus }}{\alpha =1}\phantom{\rule{0em}{0ex}}k\left[x\right]\cdot {e}_{\alpha ,0}\phantom{\rule{0em}{0ex}}\stackrel{{\varphi }_{0}}{\to }\phantom{\rule{0em}{0ex}}k\left[x\right]\to k\left[x\right]∕I\to 0.$

Then $deg\left({e}_{\alpha ,i}\right)\le m+i$ for all $\alpha$, $i$. (In particular, if ${f}_{\alpha }={\varphi }_{0}\left({e}_{\alpha ,0}\right)$, then ${f}_{1},\dots ,{f}_{{r}_{0}}$ are minimal generators of $I$, and $deg\left({e}_{\alpha ,0}\right)=deg\left({f}_{\alpha }\right)\le m$.)

The intuitive idea is that past degree $m$, nothing tricky happens in the ideal $I$. Unfortunately, neither (a), (b) nor (c) can be veriﬁed by any obvious ﬁnite algorithm. This lack of a ﬁnitely veriﬁable criterion for $m$-regularity has been remedied by a joint result of the ﬁrst author and M. Stillman [BS87a]:

Theorem 3.3 (Bayer-Stillman) $I$ is $m$-regular if and only if the degrees of the minimal set of generators of $I$ are at most $m$, and there exists a set ${y}_{0},\dots ,{y}_{\ell }$ of linear combinations of ${x}_{0},...,{x}_{n}$ such that for all homogeneous $f$ of degree $m$,

$\begin{array}{rcll}{y}_{0}f\in I& ⇒& f\in I& \text{}\\ {y}_{1}f\in I& ⇒& f\in I+k\left[x\right]\cdot {y}_{0}& \text{}\\ & \cdots & & \text{}\\ {y}_{\ell }f\in I& ⇒& f\in I+\sum _{i=0}^{\ell -1}k\left[x\right]\cdot {y}_{i}& \text{}\end{array}$

and

$f\in I+\sum _{i=0}^{\ell }k\left[x\right]\cdot {y}_{i}.$

Moreover, if this holds at all, it holds for ${y}_{0},\dots ,{y}_{\ell }$ taken arbitrarily from a Zariski-open set in the space of $\ell +1$ linear forms.

To see why $m$-regularity is a key bound, we want to show that it controls some of the geometric features of the ideal $I$. Let’s introduce several reﬁned notions of the “degree” of $I$:

Deﬁnition 3.4 If $I={q}_{0}\phantom{\rule{0em}{0ex}}\cap \phantom{\rule{0em}{0ex}}{q}_{1}\phantom{\rule{0em}{0ex}}\cap \phantom{\rule{0em}{0ex}}\dots \phantom{\rule{0em}{0ex}}\cap \phantom{\rule{0em}{0ex}}{q}_{t}$ is a primary decomposition of $I$, $\sqrt{{q}_{i}}={p}_{i}$ is prime and $V\left({p}_{i}\right)$ is the subvariety ${Z}_{i}$ of $\text{}Pn\text{}$ for $i\ge 1$, while ${p}_{0}=\left({x}_{0},\dots ,{x}_{n}\right)$ (so that $V\left({p}_{0}\right)=\varnothing$), then ﬁrst let ${q}_{1},\dots ,{q}_{s}$ be the isolated components, (i.e., ${Z}_{i}\not\subset {Z}_{j}$ if $1\le i\le s$, $1\le j\le t$, $i\ne j$, or equivalently, $V\left(I\right)={Z}_{1}\phantom{\rule{0em}{0ex}}\cup \phantom{\rule{0em}{0ex}}\dots \phantom{\rule{0em}{0ex}}\cup \phantom{\rule{0em}{0ex}}{Z}_{s}$ is set-theoretically the minimal decomposition of $V\left(I\right)$ into varieties). Then let

(Equivalently, this is the length of the local ring $k{\left[x\right]}_{{p}_{i}}∕Ik{\left[x\right]}_{{p}_{i}}$, or, in the language of schemes, if $\eta$ is the generic point of ${Z}_{i}$, then this is the length of ${\mathsc{𝒪}}_{\eta ,\text{}Pn\text{}}.$)

If ${q}_{i}$ is one of the non-isolated, or embedded components, then we extend the concept of multiplicity more carefully: Let

and

(Equivalently, ${J}_{k}$ equals ${q}_{k}\cap {I}_{i}$ for some ${p}_{i}$-primary ideal ${q}_{k}$.) In particular:

For $s+1\le i\le t$, an equivalent way to deﬁne ${mult}_{I}\left({q}_{i}\right)$ is as the length of the module

${I}_{i}k{\left[x\right]}_{{p}_{i}}∕Ik{\left[x\right]}_{{p}_{i}}$

or, in the language of schemes, the length of

${I}_{i}{\mathsc{𝒪}}_{\eta ,\text{}Pn\text{}}∕I{\mathsc{𝒪}}_{\eta ,\text{}Pn\text{}}$

where $\eta$ is the generic point of ${Z}_{i}$.

Then write

and

${\text{arith-deg}}_{-1}\left(I\right)={mult}_{I}\left({q}_{0}\right).$

The idea here is best illustrated by an example: let

$I=\left({x}_{1}^{2},{x}_{1}{x}_{2}\right)\subset k\left[{x}_{0},{x}_{1},{x}_{2}\right].$

Then

Then

$deg\left({Z}_{1}\right)=1,mult\left({q}_{1}\right)=1$

so

${\text{geom-deg}}_{1}\left(I\right)={\text{arith-deg}}_{1}\left(I\right)=1.$

One might be tempted to simply deﬁne

and since

$k{\left[x\right]}_{{q}_{2}}∕{q}_{2}k{\left[x\right]}_{{p}_{2}}\cong K\cdot 1+K\cdot {x}_{1}+K\cdot {x}_{2},K=k\left({x}_{0}\right)$

this is $3$. But embedded components are not unique! In fact,

$k{\left[x\right]}_{{p}_{2}}∕{q}_{2}^{\prime }k{\left[x\right]}_{{p}_{2}}\cong K\cdot 1+K\cdot {x}_{2}$

which has length $2$. The canonical object is not the local ring $k{\left[x\right]}_{{p}_{2}}∕{q}_{2}k\left[x\right]{p}_{2}$ but the ideal

$\text{Ker}\left(k{\left[x\right]}_{{p}_{2}}∕Ik{\left[x\right]}_{{p}_{2}}\to k{\left[x\right]}_{{p}_{2}}∕{p}_{2}k{\left[x\right]}_{{p}_{2}}\right)\cong k\cdot {x}_{1}$

which has length $1$. Thus, the correct numbers are

${mult}_{I}\left({q}_{2}\right)=1$

and

$\begin{array}{rcll}{\text{geom-deg}}_{0}\left(I\right)& =& 0& \text{}\\ {\text{arith-deg}}_{0}\left(I\right)& =& 1.& \text{}\end{array}$

Now the question arises: ﬁnd bounds on these degrees in terms of generators of $I$. For geometric degrees, a straightforward extension of Bezout’s theorem gives:

Proposition 3.5 Let $d\left(I\right)$ be the maximum of the degrees of a minimal set of generators of $I$. Then

${\text{geom-deg}}_{r}\left(I\right)\le d{\left(I\right)}^{n-r}.$

A proof can be found in [MW83]. The idea is clear from a simple case: Suppose $f,g,h\in K\left[x,y,z\right]$ and $f=g=h=0$ consists of a curve $C$ and $\ell$ points ${P}_{i}$ oﬀ $C$. We can bound $\ell$ like this: Choose $2$ generic combinations ${f}^{\prime }$, ${g}^{\prime }$ of $f$, $g$, $h$ so that ${f}^{\prime }={g}^{\prime }=0$ does not contain a surface. It must be of the form $C\cup {C}^{\prime }$, ${C}^{\prime }$ one-dimensional, containing all the ${P}_{i}$ but not the generic point of $C$. Then by the usual Bezout theorem

$deg{C}^{\prime }\le deg{f}^{\prime }deg{g}^{\prime }=d{\left(I\right)}^{2}.$

Let ${h}^{\prime }$ be a $3$rd generic combination of $f,g,h$. Then ${C}^{\prime }\cap \left\{{h}^{\prime }=0\right\}$ consists of a ﬁnite set of points including the ${P}_{i}$’s. Thus

Can $\text{arith-deg}\left(I\right)$ be bounded in the same way? In fact, it cannot, as we will show below. Instead, we have

Proposition 3.6 If $m\left(I\right)$ is the regularity of $I$, then for $-1\le r\le n$,

${\text{arith-deg}}_{r}\left(I\right)\le \left(\genfrac{}{}{0}{}{m\left(I\right)+n-r-1}{n-r}\right)\le m{\left(I\right)}^{n-r}$

which replaces $d\left(I\right)$ by the regularity of $I$. A proof is given in the technical appendix.

We have introduced two measures of the complexity of a homogeneous ideal $I$. The ﬁrst is $d\left(I\right)$, the maximum degree of a polynomial in a minimum set of generators of $I$. The second is $m\left(I\right)$, which bounds the degrees of generators and of all higher order syzygies in the resolution of $I$ (Deﬁnition 3.2 (c)). Obviously,

$d\left(I\right)\le m\left(I\right).$

A very important question is how much bigger can $m\left(I\right)$ be than $d\left(I\right)$? The nature of the answer was conjectured by one of us in his thesis [Bay82] and this conjecture is being borne out by subsequent investigations. This conjecture is that in the worst case $m\left(I\right)$ is roughly the $\left({2}^{n}\right)$th power of $d\left(I\right)$ – a bound like G. Hermann’s. But that if $I=I\left(Z\right)$ where $Z$ is geometrically nice, e.g. is a smooth irreducible variety, then $m\left(I\right)$ is much smaller, like the $n$th power of $d\left(I\right)$ or better. This conjecture then has three aspects:

 (1) a doubly exponential bound for $m\left(I\right)$ in terms of $d\left(I\right)$, which is always valid, (2) examples of $I$ where the bound in (1) is best possible, or nearly so, (3) much better bounds for $m\left(I\right)$ valid if $V\left(I\right)$ satisﬁes various conditions.

All three aspects are partially proven, but none are completely clariﬁed yet. We will take them up one at a time.

A doubly exponential bound for $m\left(I\right)$ in terms of $d\left(I\right)$ may be deduced easily in characteristic zero from the work of M. Giusti [Giu84] and A. Galligo [Gal79]:

Theorem 3.7 If $\text{char}\left(k\right)=0$ and $I\subset k\left[{x}_{0},\dots {x}_{n}\right]$ is any homogeneous ideal, then

$m\left(I\right)\le {\left(2d\left(I\right)\right)}^{{2}^{n-1}}.$

It seems likely that Theorem 3.7 holds in characteristic $p$, too. A weaker result can be derived quickly in any characteristic by straightforward cohomological methods:

Proposition 3.8 If $I\subset k\left[{x}_{0},\dots {x}_{n}\right]$ is any homogeneous ideal, then

$m\left(I\right)\le {\left(2d\left(I\right)\right)}^{n!}.$

The proof is given in the technical appendix.

Next, we ask whether Theorem 3.7 is the best possible, or nearly so. The answer is yes, because of a very remarkable example due to E. Mayr and A. Meyer [MM82].

Example 3.9 Let ${I}_{n}^{A}$ be the ideal in $10n$ variables ${S}^{\left(m\right)},{F}^{\left(m\right)},{C}_{i}^{\left(m\right)},{B}_{i}^{\left(m\right)},1\le i\le 4,1\le m\le n$ deﬁned by the $10n-6$ generators

Let ${I}_{n}^{H}$ be the ideal gotten from ${I}_{n}^{A}$ by homogenizing with an extra variable $u$. Then Mayr and Meyer [MM82, lemma 8, p. 318] prove:

Lemma 3.10 Let ${e}_{n}={2}^{{2}^{n}}$. If $M$ is any monomial in these variables, ${S}^{\left(n\right)}{C}_{i}^{\left(n\right)}-{F}^{\left(n\right)}M\in {I}_{n}^{A}$ if and only if

$M={C}_{i}^{\left(n\right)}{\left({B}_{i}^{\left(n\right)}\right)}^{{e}_{n}},$

and ${S}^{\left(n\right)}{C}_{i}^{\left(n\right)}-{S}^{\left(n\right)}M\in {I}_{n}^{A}$ if and only if

$M={C}_{i}^{\left(n\right)}.$

Now note that the generators of ${I}_{n}^{A}$ and ${I}_{n}^{H}$ are all of the very simple type given by a diﬀerence of two monomials. Quite generally, if

$\begin{array}{rcll}J& \subset & k\left[{x}_{1},\dots ,{x}_{n}\right]& \text{}\\ J& =& {\left(\dots ,{x}^{{\alpha }_{i}}-{x}^{{\beta }_{i}},\dots \right)}_{1\le i\le k}& \text{}\end{array}$

then the quotient ring $k\left[x\right]∕J$ has a very simple form. In fact, we get an equivalence relation between monomials generated by

and

$k\left[x\right]∕J\cong {\oplus }_{\delta }k\cdot {x}^{\delta }$

where $\delta$ runs over a set of representatives of each equivalence class.

Bearing this in mind, let’s look at the $1$st order syzygies for the homogeneous ideal:

${J}_{n}^{H}=\left({S}^{\left(n\right)},{F}^{\left(n\right)},{I}_{n}^{H}\right).$

${S}^{\left(n\right)}$ and ${F}^{\left(n\right)}$ are part of a minimal set of generators, and let ${f}_{\alpha }\in {I}_{n}^{H}$ complete them. Then syzygies are equations:

$p\phantom{\rule{0em}{0ex}}{S}^{\left(n\right)}\phantom{\rule{0em}{0ex}}+\phantom{\rule{0em}{0ex}}q\phantom{\rule{0em}{0ex}}{F}^{\left(n\right)}\phantom{\rule{0em}{0ex}}+\phantom{\rule{0em}{0ex}}\sum \phantom{\rule{0em}{0ex}}{r}_{\alpha }\phantom{\rule{0em}{0ex}}{f}_{\alpha }\phantom{\rule{0em}{0ex}}=\phantom{\rule{0em}{0ex}}0.$

One such is given by:

$\left[{u}^{{e}_{n}+e}\phantom{\rule{0em}{0ex}}{C}_{i}^{\left(n\right)}\right]\phantom{\rule{0em}{0ex}}{S}^{\left(n\right)}\phantom{\rule{0em}{0ex}}+\phantom{\rule{0em}{0ex}}\left[-{u}^{e}\phantom{\rule{0em}{0ex}}{\left({B}_{i}^{\left(n\right)}\right)}^{{e}_{n}}\phantom{\rule{0em}{0ex}}{C}_{i}^{\left(n\right)}\right]\phantom{\rule{0em}{0ex}}{F}^{\left(n\right)}\phantom{\rule{0em}{0ex}}+\phantom{\rule{0em}{0ex}}\sum \phantom{\rule{0em}{0ex}}{R}_{\alpha }\phantom{\rule{0em}{0ex}}{f}_{\alpha }\phantom{\rule{0em}{0ex}}=\phantom{\rule{0em}{0ex}}0$

for some ${R}_{\alpha }$, and some $e\ge 0$ (the extra power ${u}^{e}$ is necessary because some terms ${R}_{\alpha }{f}_{\alpha }$ have degree greater than ${e}_{n}+2$) whose degree is $2+{e}_{n}+e$. Now express this syzygy as a combination of a minimal set of syzygies. This gives us in particular:

$\begin{array}{rcll}{u}^{{e}_{n}+e}\phantom{\rule{0em}{0ex}}{C}_{i}^{\left(n\right)}\phantom{\rule{0em}{0ex}}& =& \phantom{\rule{0em}{0ex}}\sum \phantom{\rule{0em}{0ex}}{a}_{\lambda }\phantom{\rule{0em}{0ex}}{p}_{\lambda }& \text{}\\ -{u}^{e}\phantom{\rule{0em}{0ex}}{\left({B}_{i}^{\left(n\right)}\right)}^{{e}_{n}}\phantom{\rule{0em}{0ex}}{C}_{i}^{\left(n\right)}\phantom{\rule{0em}{0ex}}& =& \phantom{\rule{0em}{0ex}}\sum \phantom{\rule{0em}{0ex}}{a}_{\lambda }\phantom{\rule{0em}{0ex}}{q}_{\lambda }& \text{}\\ {p}_{\lambda }\phantom{\rule{0em}{0ex}}{S}^{\left(n\right)}\phantom{\rule{0em}{0ex}}+\phantom{\rule{0em}{0ex}}{q}_{\lambda }\phantom{\rule{0em}{0ex}}{F}^{\left(n\right)}\phantom{\rule{0em}{0ex}}+\phantom{\rule{0em}{0ex}}\sum \phantom{\rule{0em}{0ex}}{R}_{\alpha \lambda }\phantom{\rule{0em}{0ex}}{f}_{\alpha }\phantom{\rule{0em}{0ex}}& =& \phantom{\rule{0em}{0ex}}0\phantom{\rule{0em}{0ex}}.& \text{}\end{array}$

Then for some $\lambda$, ${p}_{\lambda }$ must have a term of the form ${u}^{\ell }$ or ${u}^{\ell }\phantom{\rule{0em}{0ex}}{C}_{i}^{\left(n\right)}$, hence the monomial ${u}_{\ell }\phantom{\rule{0em}{0ex}}{S}^{\left(n\right)}$ or ${u}_{\ell }\phantom{\rule{0em}{0ex}}{C}_{i}^{\left(n\right)}\phantom{\rule{0em}{0ex}}{S}^{\left(n\right)}$ occurs in ${p}_{\lambda }\phantom{\rule{0em}{0ex}}{S}^{\left(n\right)}$. But by the general remark on quotient rings by such simple ideals, this means that this term must equal some second term $M\phantom{\rule{0em}{0ex}}{S}^{\left(n\right)}$ ($M$ a monomial in ${p}_{\lambda }$) or $M\phantom{\rule{0em}{0ex}}{F}^{\left(n\right)}$ ($M$ a monomial in ${q}_{\lambda }$) mod ${I}_{n}^{H}$. By the lemma, the ﬁrst doesn’t happen and the second only happens if the term ${u}^{\ell }\phantom{\rule{0em}{0ex}}{C}_{i}^{\left(n\right)}\phantom{\rule{0em}{0ex}}{\left({B}_{i}^{\left(n\right)}\right)}^{{e}_{n}}$ occurs in ${q}_{\lambda }$, in which case ${e}_{n}+1\le deg\phantom{\rule{0em}{0ex}}{q}_{\lambda }\phantom{\rule{0em}{0ex}}=\phantom{\rule{0em}{0ex}}deg\left(\text{syzygy}\left({p}_{\lambda },{q}_{\lambda },{R}_{\alpha \lambda }\right)\right)-1$. This proves:

Proposition 3.11 ${J}_{n}^{H}$ has for its bounds:

$\begin{array}{rcll}d\left(J\right)& =& 4& \text{}\\ m\left(J\right)& \ge & {2}^{{2}^{n}}+1.& \text{}\end{array}$

Going on to the $3$rd aspect of the conjecture, consider results giving better bounds for $m\left(I\right)$ under restrictive hypotheses on $V\left(I\right)$.

Theorem 3.12 If $Z\subset \text{}Pn\text{}$ is a reduced subscheme purely of dimension $r$, and $I=I\left(Z\right)$ is the full ideal of functions vanishing on $Z$, then

(a) if $r\le 1$, or $Z$ is smooth, $char\left(k\right)=0$ and $r\le 3$, then:

$m\left(I\right)\le degZ-n+r+1$

(b) if char$\left(k\right)=0$ and $Z$ is smooth,

$m\left(I\right)\le \left(r+1\right)\left(deg\left(Z\right)-2\right)+2.$

Since $deg\left(Z\right)\le d{\left(I\right)}^{n-r}$ (Proposition 3.5), these bound $m\left(I\right)$ in terms of $d\left(I\right).$

Part (a) of this are due to Gruson-Lazarsfeld-Peskine [GLP83] for $r\le 1$, and to Pinkham [Pin86], Lazarsfeld [Laz87], and Ran [Ran90] for $r\le 3$. It is conjectured by Eisenbud and Goto [EG84], and others, that the bound in (a) holds for all reduced irreducible $Z$, and it might well hold even for reduced equidimensional $Z$ which are connected in codimension 1. As this problem is now understood, the needed cohomological arguments follow formally, once one can control the singularities of a projection of the variety. These singularities become progressively harder to subdue as the dimension of the variety increases, and are what impedes deﬁnitive progress beyond dimension 3.

Part (b) is due to the second author and is proven in the technical appendix. It has been generalized by Bertram, Ein, and Lazarsfeld [BEL91] to show that any smooth characteristic $0$ variety of codimension $e$ deﬁned as a subscheme of ${P}^{n}$ by hypersurfaces of degrees ${d}_{1}\ge \dots \ge {d}_{m}$ is $\left({d}_{1}+\dots {d}_{e}-e+1\right)$-regular. Since we cannot decide the previous conjecture, this is a result of considerable practical importance, for it strongly bounds the complexity of computing Gröbner bases of smooth characterisitic $0$ varieties in terms of the degrees of the input equations.

The biggest missing link in this story is a decent bound on $m\left(I\right)$ for any reduced equidimensional ideal $I$. We would conjecture that if a linear bound as in part (a) doesn’t hold, at the least a so-called “single exponential” bound, i.e. $m\left(I\right)\le {d}^{0\left(n\right)}$ ought to hold. This is an essential ingredient in analyzing the worst-case behavior of all algorithms based on Gröbner bases, and would complete the story about what causes the bad examples discussed above. At least in some cases Ravi [Rav90] has proven that the regularity of the radical of a scheme is no greater than the regularity of the scheme itself.

There is a direct link between the bounds that we have given so far and the G. Hermann bound with which we started the section. This results from the following:

Proposition 3.13 Let ${I}^{A}\subset k\left[{x}_{1},\dots ,{x}_{n}\right]$ have generators ${f}_{1},\dots ,{f}_{k}$ and let ${I}^{H}\subset k\left[{x}_{0},{x}_{1},\dots ,{x}_{n}\right]$ be the ideal generated by homogenizations ${f}_{1}^{h},\dots ,{f}_{k}^{h}$ of the ${f}_{i}$. Let ${I}^{H}={q}_{0}\cap \dots \cap {q}_{t}$ be the primary decomposition of ${I}^{H}$, let ${Z}_{i}=V\left({q}_{i}\right)$ and let

${mult}_{\infty }\left({I}^{H}\right)=max\left[{mult}_{I}\left({q}_{{i}_{1}}\right)+\dots +{mult}_{I}\left({q}_{{i}_{k}}\right)+{mult}_{I}\left({q}_{0}\right)\right]$

where the $max$ is taken over chains $V\left(\left({x}_{0}\right)\right)\supset {Z}_{{i}_{1}}\phantom{\rule{0em}{0ex}}\stackrel{\supset }{\ne }\phantom{\rule{0em}{0ex}}\dots \phantom{\rule{0em}{0ex}}\stackrel{\supset }{\ne }\phantom{\rule{0em}{0ex}}{Z}_{{i}_{k}}$. If $g\in {I}^{A}$, then we can write:

$g=\sum _{i=1}^{k}\phantom{\rule{0em}{0ex}}{a}_{i}\phantom{\rule{0em}{0ex}}{f}_{i}$

where

$deg{a}_{i}\le degg+{mult}_{\infty }\left({I}^{H}\right).$

The proof goes like this: Let ${g}^{h}$ be the homogenization of $g$. Consider the least integer $m$ such that ${x}_{0}^{m}{g}^{h}\in {I}^{H}$. Since $g\in I$, this $m$ is ﬁnite. Moreover, if

${x}_{0}^{m}{g}^{h}=\sum \underset{0}{\overset{{m}_{i}}{x}}{a}_{i}^{h}{f}_{i}^{h}$

then

$g=\sum {a}_{i}{f}_{i}$

and

$deg{a}_{i}=deg\left({a}^{h}\right)\le deg\left({x}_{0}^{m}{g}^{h}\right)-deg{f}_{j}\le m+deg\left(g\right).$

Now in the primary decomposition of ${I}^{H}$, suppose that for some $k$,

Choose $\ell \notin S$ such that $V\left({q}_{\ell }\right)$ is maximal. Since $g\in {I}^{A}$, we know $V\left({q}_{\ell }\right)\subset V\left(\left({x}_{0}\right)\right)$, hence ${x}_{0}\in {p}_{\ell }$. Let

${I}_{S}=\stackrel{\bigcap ^{}}{i\in S}{q}_{i}.$

Then ${mult}_{I}\left({q}_{\ell }\right)$ is easily seen to be the length of a maximal chain of ideals between:

But look at the ideals ${J}_{p}$, for $p\ge 0$, deﬁned by

$I\phantom{\rule{0em}{0ex}}k{\left[x\right]}_{{p}_{\ell }}\subset \underset{{J}_{p}}{\underbrace{\left(I,{x}_{0}^{k+p}{g}^{h}\right)\phantom{\rule{0em}{0ex}}k{\left[x\right]}_{{p}_{\ell }}}}\subset {I}_{S}\phantom{\rule{0em}{0ex}}k{\left[x\right]}_{{p}_{\ell }}.$

If ${J}_{p}={J}_{p+1}$, then

$\begin{array}{rcll}{x}_{0}^{k+p}{g}^{h}& \in & \left(I,{x}_{0}^{k+p+1}{g}^{h}\right)& \text{}\\ \text{i.e.,}{x}_{0}^{k+p}{g}^{h}& =& a\phantom{\rule{0em}{0ex}}{x}_{0}^{k+p+1}{g}^{h}+b,b\in I.& \text{}\end{array}$

But $1-a{x}_{0}$ is a unit in $k{\left[x\right]}_{{p}_{\ell }}$, so

${J}_{p}={x}_{0}^{k+p}{g}^{h}={\left(1-a{x}_{0}\right)}^{-1}b\in I\phantom{\rule{0em}{0ex}}k{\left[x\right]}_{{p}_{\ell }}.$

This means that in any case

${x}_{0}^{k+{mult}_{I}\left({q}_{\ell }\right)}{g}^{h}\in I\cdot k{\left[x\right]}_{{p}_{\ell }}$

hence, because ${q}_{\ell }$ is ${p}_{\ell }$-primary:

${x}_{0}^{k+{mult}_{I}\left({q}_{\ell }\right)}{g}^{h}\in {q}_{\ell }$

Induction now shows that

${x}_{0}^{{mult}_{\infty }\left({I}^{H}\right)}{g}^{h}\in {I}^{H}$

Corollary 3.14 Let ${I}^{A}$, ${I}^{H}$ be as above. If $g\in {I}^{A}$, then

$g=\sum {a}_{i}{f}_{i}$

where $deg\left({a}_{i}\right)\le deg\left(g\right)+\left(\genfrac{}{}{0}{}{m\left(I\right)+n+1}{n+1}\right)$.

Proof. Combine Propositions 3.6 and 3.13.

If we further estimate $m\left(I\right)$ by Theorem 3.7 in characteristic $0$ or by Proposition 3.8, we get somewhat weaker versions of Hermann’s Theorem 3.1. But if $I=V\left(Z\right)$, $Z$ a good variety, we may expect the Corollary to give much better bounds than Theorem 3.1.

Corollary 3.14 shows that any example which demonstrates the necessity of double exponential growth in Hermann’s ideal membership bound (Theorem 3.1) also demonstrates the necessity of double exponential growth in the bounds on $m\left(I\right)$ given in Theorem 3.7 and Proposition 3.8. Thus we can make use of the general arguments for the existence of such examples given in [MM82], rather than depending on the single example of Proposition 3.11, to show that the bounds on $m\left(I\right)$ inevitably grow double exponentially: Since in Corollary 3.14, the degrees of the ${a}_{i}$ are bounded by a single exponential function of $m\left(I\right)$, in all examples where the degrees of the ${a}_{i}$ grow double exponentially, $m\left(I\right)$ also grows double exponentially.

This line of argument gives a geometric link between the ideal membership problem and $m\left(I\right)$: In Corollary 3.14, if ${I}^{A}$ exhibits ${a}_{i}$ of high degree, then ${I}^{H}$ has primary components of high multiplicity. These components force $m\left(I\right)$ to be large, and distinguish ${I}^{H}$ from good ideals considered in Theorem 3.12 and related conjectures.

A major step in understanding the gap between the double exponential examples and the strong linear bounds on the regularity of many smooth varieties was taken by Brownawell [Bro87] and Kollár [Kol88]. They discovered the beautiful and satisfying fact that if we replace membership in $I$ by membership in $\sqrt{I}$, then there are single exponential bounds on the degrees of ${a}_{i}$:

Theorem 3.15 (Brownawell, Kollár) Let $k$ be any ﬁeld, let $I=\left({f}_{1},...,{f}_{k}\right)\subset k\left[{x}_{1},...,{x}_{n}\right]$ and let $d=max\left(deg\left({f}_{i}\right),i=1,\cdots ,k;3\right)$. If $n=1$, replace $d$ by $2d-1$. If $g\in \sqrt{I}$, then there is an expression

${g}^{s}=\sum _{i=1}^{k}{a}_{i}{f}_{i}$

where $s\le {d}^{n}$ and $deg\left({a}_{i}\right)\le \left(1+deg\left(g\right)\right){d}^{n}$. In particular:

${\left(\sqrt{I}\right)}^{{d}^{n}}\subset I.$

What this shows is that although the bad examples have to have primary components at inﬁnity of high degree, nonetheless these primary ideals contain relatively small powers of $\sqrt{{I}^{H}}$. The picture you should have is that these embedded components at inﬁnity are like strands of ivy that creep a long way out from the hyperplane at inﬁnity, but only by clinging rather closely to the aﬃne components.

Technical Appendix to Section 3

1. Proof of the equivalence of the conditions in Deﬁnition 3.2:

In [Mum66, pp. 99-101], it is proven that for any coherent sheaf $\mathsc{ℱ}$ on $\text{}Pn\text{}$, ${H}^{i}\left(\mathsc{ℱ}\left(-i\right)\right)=\left(0\right)$, $i\ge 1$ implies that the same holds for $\mathsc{ℱ}\left(d\right)$, all $d\ge 0$, and that ${H}^{0}\left(\mathsc{ℱ}\left(d\right)\right)$ is generated by ${H}^{0}\left(\mathsc{ℱ}\right)\otimes {H}^{0}\left(\mathsc{𝒪}\left(d\right)\right)$. In particular, if you apply this to $\mathsc{ℱ}=\mathsc{ℐ}\left(m\right)$, the equivalence of (a) and (b) follows. (Note the diagram:

$\begin{array}{ccc}\hfill {I}_{d}\hfill & \hfill \to \hfill & \hfill {H}^{0}\left(\mathsc{ℐ}\left(d\right)\right)\hfill \\ \hfill \bigcap \hfill & \hfill \hfill & \hfill \bigcap \hfill \\ \hfill k{\left[x\right]}_{d}\hfill & \hfill \to \hfill & \hfill {H}^{0}\left({\mathsc{𝒪}}_{\text{}Pn\text{}}\left(d\right)\right)\hfill \end{array}$

which shows that ${I}_{m}\to {H}^{0}\left(\mathsc{ℐ}\left(m\right)\right)$ is injective for every $d$). To show that (b) $⇒$ (c), ﬁrst note that we may rephrase the reults in [Mum66] to say that if ${H}^{i}\left(\mathsc{ℱ}\left(-i\right)\right)=\left(0\right)$, $i\ge 1$, then the degrees of the minimal generators of the $k\left[x\right]$-module

$\stackrel{\oplus }{d\in \text{Z}}{H}^{0}\left(\mathsc{ℱ}\left(d\right)\right)$

are all zero or less. So we may construct the resolution in (c) inductively: at the $k$th stage, say

$\stackrel{\stackrel{{r}_{k}+1}{\oplus }}{\alpha =1}k\left[x\right]\cdot {e}_{\alpha ,k-1}\stackrel{{\varphi }_{k-1}}{\to }\cdots \to k\left[x\right]\to k\left[x\right]∕I\to 0$

has been constructed, let and let ${\mathsc{ℱ}}_{k}$ be the corresponding sheaf of ideals. The induction hypothesis will say that ${H}^{i}\left({\mathsc{ℱ}}_{k}\left(m+k-1\right)\right)=\left(0\right)$, $i\ge 1$. Therefore ${M}_{k}$ is generated by elements of degree $\le m+k$, i.e., ${d}_{\alpha }=deg{e}_{\alpha ,k}\le m+k$, all $\alpha$. We get an exact sequence

$0\to {M}_{k+1}\to \stackrel{\stackrel{{r}_{k}}{\oplus }}{\alpha =1}\left(k\left[x\right]\cdot {e}_{\alpha ,k}\right)\to {M}_{k}\to 0$

hence

$\begin{array}{rcll}0\to {\mathsc{ℱ}}_{k+1}\to \stackrel{\stackrel{{r}_{k}}{\oplus }}{\alpha =1}{\mathsc{𝒪}}_{\text{}Pn\text{}}\left(-{d}_{\alpha }\right)\to {\mathsc{ℱ}}_{k}\to 0& & & \text{(1)}\text{}\text{}\end{array}$

Therefore

$\begin{array}{rcll}\stackrel{\stackrel{{r}_{k}}{\oplus }}{\alpha =1}{H}^{i}\left({\mathsc{𝒪}}_{\text{}Pn\text{}}\left(m+k-i-{d}_{\alpha }\right)\right)\to {H}^{i}\left({\mathsc{ℱ}}_{k}\left(m+k-i\right)\right)\to & & & \text{(2)}\text{}\text{}\\ {H}^{i+1}\left({\mathsc{ℱ}}_{k+1}\left(m+\left(k+1\right)-\left(i+1\right)\right)\right)\to \stackrel{\stackrel{{r}_{k}}{\oplus }}{\alpha =1}{H}^{i+1}\left({\mathsc{𝒪}}_{\text{}Pn\text{}}\left(m+k-i-{d}_{\alpha }\right)\right)& & & \text{}\end{array}$

is exact. But $m+k-i-{d}_{\alpha }\ge -i$ so ${H}^{i+1}\left({\mathsc{𝒪}}_{\text{}Pn\text{}}\left(m+k-i-{d}_{\alpha }\right)\right)=\left(0\right)$. This shows that ${\mathsc{ℱ}}_{k+1}$ satisﬁes the induction hypothesis and we can continue. Thus (c) holds. To see that (c) $⇒$ (a), we just use the same exact sequences (1) and prove now by descending induction on $k$ that ${H}^{i}\left({\mathsc{ℱ}}_{k}\left(m+k-i\right)\right)=\left(0\right)$, $i\ge 1$. Since $I={\mathsc{ℱ}}_{0}$, this does it. The inductive step again uses (2), since ${H}^{i}\left({\mathsc{𝒪}}_{\text{}Pn\text{}}\left(m+k-i-{d}_{\alpha }\right)\right)=\left(0\right)$ too.

2. Proof of Proposition 3.6:

Look ﬁrst at the case $r=0$. Let $\mathsc{ℐ}$ be the sheaf of ideals deﬁned by $I$ and let ${\mathsc{ℐ}}^{\ast }\supset \mathsc{ℐ}$ be the sheaf deﬁned by omitting all $0$-dimensional primary components of $I$. Consider the exact sequence:

$0\to \mathsc{ℐ}\left(m-1\right)\to {\mathsc{ℐ}}^{\ast }\left(m-1\right)\to \left({\mathsc{ℐ}}^{\ast }∕\mathsc{ℐ}\right)\left(m-1\right)\to 0$

This gives us:

${H}^{0}\left({\mathsc{ℐ}}^{\ast }\left(m-1\right)\right)\to {H}^{0}\left(\left({\mathsc{ℐ}}^{\ast }∕\mathsc{ℐ}\right)\left(m-1\right)\right)\to {H}^{1}\left(\mathsc{ℐ}\left(m-1\right)\right)$

Now ${H}^{1}\left(\mathsc{ℐ}\left(m-1\right)\right)=\left(0\right)$ by $m$-regularity, and since ${\mathsc{ℐ}}^{\ast }∕\mathsc{ℐ}$ has $0$-dimensional support. But ${H}^{0}\left({\mathsc{ℐ}}^{\ast }\left(m-1\right)\right)\subset {H}^{0}\left({\mathsc{𝒪}}_{\text{}Pn\text{}}\left(m-1\right)\right)$, so

$\begin{array}{rcll}{\text{arith-deg}}_{0}\left(I\right)& \le & {h}^{0}\left({\mathsc{ℐ}}^{\ast }\left(m-1\right)\right)& \text{}\\ & \le & {h}^{0}\left({\mathsc{𝒪}}_{\text{}Pn\text{}}\left(m-1\right)\right)& \text{}\\ & =& \left(\genfrac{}{}{0}{}{m+n-1}{n}\right)& \text{}\end{array}$

If $r>0$, we can prove the Proposition by induction on $r$. Let $H$ be a generic hyperplance in $\text{}Pn\text{}$, given by $h=0$. Let ${I}_{H}=\left(I,h\right)∕\left(h\right)\subset k\left[{x}_{0},\dots ,{x}_{n}\right]∕\left(h\right)\cong k\left[{x}_{0}^{\prime },\dots ,{x}_{n-1}^{\prime }\right]$ for suitable linear combinations ${x}_{i}^{\prime }$ of ${x}_{i}$. Then it is easy to check that:

${\text{arith-deg}}_{r}\left(I\right)={\text{arith-deg}}_{r-1}\left({I}_{H}\right)$

and that ${I}_{H}$ is also $m$-regular, so by induction

$\begin{array}{rcll}{\text{arith-deg}}_{r-1}\left({I}_{H}\right)& \le & \left(\genfrac{}{}{0}{}{m+\left(n-1\right)-\left(r-1\right)-1}{\left(n-1\right)-\left(r-1\right)}\right)& \text{}\\ & =& \left(\genfrac{}{}{0}{}{m+n-r-1}{n-r}\right)& \text{}\end{array}$

If $r=-1$, we use the fact that

$0\to {I}_{d}\to {H}^{0}\left(\mathsc{ℐ}\left(d\right)\right)\stackrel{\approx }{←}{\left({I}^{\text{sat}}\right)}_{d}$

if $d\ge m$, hence

$dim\left({I}^{\text{sat}}∕I\right)\le dimk\left[x\right]∕{\left({x}_{0},\dots ,{x}_{n}\right)}^{m}=\left(\genfrac{}{}{0}{}{m+n}{n+1}\right).$

3. Proof of Proposition 3.8:

Let $I\subset k\left[{x}_{0},\dots {x}_{n}\right]$ and assume, after a linear change of coordinates, that ${x}_{n}$ is not contained in any associated prime ideals of $I$. Let $\overline{I}\subset k\left[{x}_{0},\dots {x}_{n-1}\right]$ be the image of $I$. Then $d\left(\overline{I}\right)=d\left(I\right)$ and by induction we may assume

$m\left(\overline{I}\right)\le {\left(2d\left(I\right)\right)}^{\left(n-1\right)!}.$

We will prove, in fact, that

$\begin{array}{rcll}m\left(I\right)\le m\left(\overline{I}\right)+\left(\genfrac{}{}{0}{}{m\left(\overline{I}\right)-1+n}{n}\right)& & & \text{(3)}\text{}\text{}\end{array}$

and then we will be done by virtue of the elementary estimate:

To prove (3), we use the long exact sequence

$\begin{array}{ccccccccc}\hfill 0\hfill & \hfill \to \hfill & \hfill {\left(I:\left({x}_{0}\right)\right)}_{k-1}\hfill & \hfill \stackrel{{x}_{0}}{\to }\hfill & \hfill {I}_{k}\hfill & \hfill \to \hfill & \hfill {\overline{I}}_{k}\hfill & \hfill \to \hfill & \hfill 0\hfill \\ \hfill \hfill & \hfill \hfill & \hfill ↓\hfill & \hfill \hfill & \hfill ↓\hfill & \hfill \hfill & \hfill ↓\hfill \\ \hfill 0\hfill & \hfill \to \hfill & \hfill {H}^{0}\left(\mathsc{ℐ}\left(k-1\right)\right)\hfill & \hfill \to \hfill & \hfill {H}^{0}\left(\mathsc{ℐ}\left(k-1\right)\right)\hfill & \hfill \to \hfill & \hfill {H}^{0}\left(\overline{\mathsc{ℐ}}\left(k-1\right)\right)\hfill & \hfill \stackrel{\delta }{\to }\hfill \\ \hfill \hfill \\ \hfill \hfill & \hfill \stackrel{\delta }{\to }\hfill & \hfill {H}^{1}\left(\mathsc{ℐ}\left(k-1\right)\right)\hfill & \hfill \to \hfill & \hfill {H}^{1}\left(\mathsc{ℐ}\left(k\right)\right)\hfill & \hfill \to \hfill & \hfill {H}^{1}\left(\overline{\mathsc{ℐ}}\left(k\right)\right)\hfill & \hfill \hfill \\ \hfill \hfill \end{array}$

where $\left(I:\left({x}_{0}\right)\right)=\left\{\phantom{\rule{0em}{0ex}}f\phantom{\rule{0em}{0ex}}|\phantom{\rule{0em}{0ex}}{x}_{0}f\in I\phantom{\rule{0em}{0ex}}\right\}$. Let $\overline{m}=m\left(\overline{I}\right)$. Note that ${H}^{i}\left(\overline{\mathsc{ℐ}}\left(k-1\right)\right)=\left(0\right)$, $i\ge 1$, $k\ge \overline{m}$, hence

${H}^{i}\left(\mathsc{ℐ}\left(k-1\right)\right)\to {H}^{i}\left(\mathsc{ℐ}\left(k\right)\right)$

is an isomorphism if $k\ge \overline{m}-1+1$ and $i\ge 2$. Since ${H}^{i}\left(\mathsc{ℐ}\left(k\right)\right)=\left(0\right)$, $k\gg 0$, this shows that ${H}^{i}\left(\mathsc{ℐ}\left(k\right)\right)=\left(0\right)$, $i\ge 2$, $k\ge \overline{m}-i$. Moreover ${\overline{I}}_{k}\to {H}^{0}\left(\overline{\mathsc{ℐ}}\left(k\right)\right)$ is an isomorphism if $k\ge \overline{m}$, hence $\delta =0$ if $k\ge \overline{m}$, hence ${H}^{1}\left(\mathsc{ℐ}\left(k\right)\right)=\left(0\right)$, $k\ge \overline{m}-1$. But now look at the surjectivity of ${I}_{k}\to {H}^{0}\left(\mathsc{ℐ}\left(k\right)\right)$. For all $k$, let ${M}_{k}$ be the cokernel. Then $\oplus {M}_{k}$ is a $k\left[x\right]$-module of ﬁnite dimension. Multiplication by ${x}_{0}$ induces a sequence:

$0\to \frac{{\left(I:\left({x}_{0}\right)\right)}_{k-1}}{{I}_{k-1}}\to {M}_{k-1}\stackrel{{x}_{0}}{\to }{M}_{k}\to 0$

which is exact if $k\ge \overline{m}$. But if, for one value of $k\ge \overline{m}$,

$\begin{array}{rcll}{\left(I:\left({x}_{0}\right)\right)}_{k}={I}_{k}& & & \text{(4)}\text{}\text{}\end{array}$

then by Theorem 3.3, $I$ is $k$-regular and (4) continues to hold for larger $k$, and ${M}_{k}$ must be $\left(0\right)$. In other words,

$dim{M}_{k},k\ge \overline{m}-1$

is non increasing and monotone decreasing to zero when $k\ge \overline{m}$. Therefore

$\begin{array}{rcll}m\left(I\right)& \le & \overline{m}+dim{M}_{\overline{m}-1}& \text{}\\ & \le & \overline{m}+dimk{\left[x\right]}_{\overline{m}-1}& \text{}\\ & \le & \overline{m}+\left(\genfrac{}{}{0}{}{\overline{m}-1+n}{n}\right)& \text{}\\ & & & \text{}\end{array}$

which proves (3).

4. Proof of Theorem 3.12(b):

Let $Z$ be a smooth $r$-dimensional subvariety of $\text{}Pn\text{}$ and $d=$ degree of $Z$. We ﬁrst consider linear projections of $Z$ to $\text{}Pr\text{}$ and to $\text{}Pr-1\text{}$. To get there, let ${L}_{1}\subset \text{}Pn\text{}$ be a linear subspace of dimension $n-r-1$ disjoint from $Z$ and ${L}_{2}\subset {L}_{1}$ a linear subspace of dimension $n-r-2$. Take these as centers of projection:

$\begin{array}{ccc}\hfill \text{}Pn\text{}-{L}_{1}\hfill & \hfill \supset \hfill & \hfill Z\stackrel{{p}_{2}}{\to }\hfill \\ \hfill ↓\hfill & \hfill \hfill & \hfill ↓{p}_{1}\hfill \\ \hfill \text{}Pr+1\text{}-\left\{P\right\}\hfill & \hfill \supset \hfill & \hfill {Z}_{1}\hfill \\ \hfill ↓\hfill \\ \hfill \stackrel{{p}_{2}}{\to }\text{}Pr\text{}\hfill \end{array}$

Let ${x}_{0},\dots {x}_{r+1}$ be coordinates on $\text{}Pr+1\text{}$ so that $p=\left(0,\dots ,0,1\right)$, hence ${x}_{0},\dots {x}_{r}$ are coordinates on $\text{}Pr\text{}$. Let $f\left({x}_{0},\dots {x}_{r+1}\right)=0$ be the equation of the hypersurface ${Z}_{1}$.

Now there are two ways of getting $r$-forms on $Z$: by pullback of $r$-forms on $\text{}Pr\text{}$ and by residues of $\left(r+1\right)$-forms on $\text{}Pr-1\text{}$ with simple poles along ${Z}_{1}$. The ﬁrst gives us a sheaf map

${p}_{2}^{\ast }{\Omega }_{\text{}Pr\text{}}^{r}↪{\Omega }_{Z}^{r}$

whose image is ${\Omega }_{Z}^{r}\left(-{B}_{1}\right)$, ${B}_{1}$ the branch locus of ${p}_{2}$. Corresponding to this on divisor classes:

$\begin{array}{rcll}{K}_{Z}& \equiv & {p}_{2}^{\ast }\left({K}_{\text{}Pr\text{}}\right)+{B}_{1}& \text{(5)}\text{}\text{}\\ & \equiv & -\left(r+1\right)H+{B}_{1},& \text{}\end{array}$

where $H=$ hyperplane divisor class on $Z$. The second is deﬁned by

$\begin{array}{rcll}a\left(x\right)\cdot \frac{d{x}_{1}\wedge \dots \wedge d{x}_{r+1}}{f}↦{p}_{1}^{\ast }\left(a\left(x\right)\cdot \frac{d{x}_{1}\wedge \dots \wedge d{x}_{r}}{\partial f∕\partial {x}_{r+1}}\right)& & & \text{(6)}\text{}\text{}\end{array}$

and it gives us an isomorphism

${p}_{1}^{\ast }\left({\Omega }_{\text{}Pr+1\text{}}^{r+1}\left({Z}_{1}\right){\mid }_{{Z}_{1}}\right)\cong {\Omega }_{Z}^{r}\left({B}_{2}\right)$

${B}_{2}$ is a divisor which can be interpreted as the conductor of the aﬃne rings of $Z$ over those of ${Z}_{1}$: i.e.,

$f\in {\mathsc{𝒪}}_{Z}\left(-{B}_{2}\right)⇔f\cdot \left({p}_{1,\ast }{\mathsc{𝒪}}_{Z}\right)\subset {\mathsc{𝒪}}_{{Z}_{1}}.$

In particular,

A classical reference for these basic facts is Zariski [Zar69], Prop. 12.13 and Theorem 15.3. A modern reference is Lipman [Lip84] (apply Def. (2.1)b to ${p}_{1}$ and apply Cor. (13.6) to ${Z}_{1}\subset \text{}Pr+1\text{}$). (4) gives us the divisor class identity:

$\begin{array}{rcll}{K}_{Z}+{B}_{2}& \equiv & {p}_{1}^{\ast }\left({K}_{\text{}Pr+1\text{}}+{Z}_{1}\right)& \text{(8)}\text{}\text{}\\ & \equiv & \left(d-r-2\right)H.& \text{}\end{array}$

(5) and (8) together tell us that

${B}_{1}+{B}_{2}\equiv \left(d-1\right)H.$

In fact, the explicit description (6) of the residue tells us more: namely that if ${y}_{1},\dots ,{y}_{r}$ are local coordinates on $Z$, then

$\frac{\partial \left({x}_{1},\dots ,{x}_{r}\right)}{\partial \left({y}_{1},\dots ,{y}_{r}\right)}\cdot \frac{1}{\partial f∕\partial {x}_{r+1}}d{y}_{1}\wedge \dots \wedge d{y}_{r}$

generates ${\Omega }_{Z}^{r}\left({B}_{2}\right)$ locally. But $\frac{\partial \left({x}_{1},\dots ,{x}_{r}\right)}{\partial \left({y}_{1},\dots ,{y}_{r}\right)}=0$ is a local equation for ${B}_{1}$, so this means that $\partial f∕\partial {x}_{r+1}=0$ is a local equation for ${B}_{1}+{B}_{2}$. But $\partial f∕\partial {x}_{r+1}=0$ is a global hypersurface of degree $d-1$ in $\text{}Pr+1\text{}$, hence globally:

${B}_{1}+{B}_{2}={p}_{1}^{\ast }\left(V\left(\frac{\partial f}{\partial {x}_{{r}_{1}}}\right)\right)$

(equality of divisors, not merely divisor classes). All this is standard classical material.

(7) has an important cohomological consequence: let ${C}^{\ast }\subset {\mathsc{𝒪}}_{\text{}Pr+1\text{}}$ be the sheaf of ideals consisting of functions whose restriction to ${Z}_{1}$ lies in C. Then we get an exact sequence:

$0\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{\mathsc{𝒪}}_{\text{}Pr+1\text{}}\left(-{Z}_{1}\right)\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{C}^{\ast }\phantom{\rule{0em}{0ex}}{\mathsc{𝒪}}_{\text{}Pr+1\text{}}\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}C\phantom{\rule{0em}{0ex}}{\mathsc{𝒪}}_{{Z}_{1}}\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}0$

hence an exact sequence

$0\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{\mathsc{𝒪}}_{\text{}Pr+1\text{}}\left(\ell -d\right)\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{C}^{\ast }{\mathsc{𝒪}}_{\text{}Pr+1\text{}}\left(\ell \right)\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{p}_{1,\ast }\left({\mathsc{𝒪}}_{Z}\left(\ell H-{B}_{2}\right)\right)\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}0$

for all integers $\ell$. But ${H}^{1}\left({\mathsc{𝒪}}_{\text{}Pr+1\text{}}\left(\ell -d\right)\right)=\left(0\right)$, hence

${H}^{0}\left({C}^{\ast }{\mathsc{𝒪}}_{\text{}Pr+1\text{}}\left(\ell \right)\right)\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{H}^{0}\left({\mathsc{𝒪}}_{Z}\left(\ell H-{B}_{2}\right)\right)$

is surjective, hence

Now let us vary the projections ${p}_{1}$ and ${p}_{2}$. For each choice of ${L}_{1}$, we get a diﬀerent ${B}_{1}$: call it ${B}_{1}\left({L}_{1}\right)$, and for each choice of ${L}_{2}$, as diﬀerent ${B}_{2}$: call it ${B}_{2}\left({L}_{2}\right)$. By (5) and (8), all divisors ${B}_{1}\left({L}_{1}\right)$ are linearly equivalent as are all divisors ${B}_{2}\left({L}_{2}\right)$. Moreover:

$\begin{array}{rcll}\stackrel{\bigcap ^{}}{{L}_{1}}{B}_{1}\left({L}_{1}\right)& =& \varnothing & \text{}\\ \stackrel{\bigcap ^{}}{{L}_{2}}{B}_{2}\left({L}_{2}\right)& =& \varnothing & \text{}\end{array}$

This is because, if $x\in Z$, then there is a choice of ${L}_{1}$ such that ${p}_{1}:Z\to \text{}Pr\text{}$ is unramiﬁed at $y$; and a choice of ${L}_{2}$ such that ${p}_{2}\left(x\right)\in {Z}_{1}$ is smooth, hence ${p}_{2}$ is an isomorphism near $x$. Thus

$\text{}\mid {B}_{1}\left({L}_{1}\right)\mid \text{}=\text{}\mid {K}_{Z}+\left(r+1\right)H\mid \text{}$

and

$\text{}\mid {B}_{2}\left({L}_{2}\right)\mid \text{}=\text{}\mid {K}_{Z}+\left(d-r-2\right)H\mid \text{}$

are base point free linear systems.

Next choose $\left(r+1\right)$ ${L}_{2}$’s, called ${L}_{2}^{\alpha }$, $1\le \alpha \le r+1$, so that if ${B}_{2}^{\left(\alpha \right)}={B}_{2}\left({L}_{2}^{\left(\alpha \right)}\right)$, then $\stackrel{\bigcap ^{}}{\alpha }{B}_{2}^{\left(\alpha \right)}=\varnothing$. Look at the Koszul complex:

$\begin{array}{rcll}0\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{\mathsc{𝒪}}_{Z}\left(\ell H-\sum \underset{2}{\overset{\left(\alpha \right)}{B}}\right)& \to & \cdots & \text{}\\ \to \phantom{\rule{0em}{0ex}}\sum _{\alpha ,\beta }{\mathsc{𝒪}}_{Z}\left(\ell H-{B}_{2}^{\left(\alpha \right)}-{B}_{2}^{\left(\beta \right)}\right)& \to & \sum _{\alpha }{\mathsc{𝒪}}_{Z}\left(\ell H-{B}_{2}^{\left(\alpha \right)}\right)\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}{\mathsc{𝒪}}_{Z}\left(\ell H\right)\phantom{\rule{0em}{0ex}}\to \phantom{\rule{0em}{0ex}}0.& \text{}\end{array}$

This is exact and diagram chasing gives the conclusion:

hence by (9)

and

$⇒{H}^{j}\left({\mathsc{𝒪}}_{Z}\left(\ell H\right)\right)=\left(0\right).$

Now $I\left(Z\right)$ is $m$-regular if and only if ${H}^{i}\left({\mathsc{ℐ}}_{Z}\left(m-i\right)\right)=\left(0\right)$, $i\ge 1$, hence if and only if

${H}^{i}\left({\mathsc{𝒪}}_{Z}\left(m-i-1\right)\right)=\left(0\right),i\ge 1.$

By the previous remark, this follows provided that

But let us rewrite:

$\left(m-i-1\right)H-\left(j+1\right){B}_{2}\equiv {K}_{Z}+j{B}_{1}+\left(m-i-\left(j+1\right)\left(d-1\right)+r\right)H$

using (5) and (8). Note that $j{B}_{1}+\ell H$ is an ample divisor if $\ell \ge 1,j\ge 0$, because $\text{}\mid {B}_{1}\mid \text{}$ is base point free. Therefore by the Kodaira Vanishing Theorem,

${H}^{i}\left({\mathsc{𝒪}}_{Z}\left({K}_{Z}+j{B}_{1}+\ell H\right)\right)=\left(0\right),i,j\ge 1,j\ge 0$

and provided $m=\left(r+1\right)\left(d-2\right)+2$, this gives the required vanishing.

4 Applications

From some points of view, the ﬁrst main problem of algebraic geometry is to reduce the study of a general ideal $I$ to that of prime ideals, or the study of arbitrary schemes to that of varieties. One way of doing this is to ﬁnd a decomposition of the ideal into primary ideals: i.e. write it as an intersection of primary ideals. But even when non-redundancy is added, this is not unique, and usually one actually wants something less: to ﬁnd its radical and perhaps write the radical as an intersection of prime ideals, or to ﬁnd its top dimensional part, or to ﬁnd its associated prime ideals and their multiplicities. There are really four computational problems involved here which should be treated separately: (i) eliminating the multiplicities in the ideal $I$, (ii) separating the pieces of diﬀerent dimension, (iii) “factoring” the pieces of each dimension into irreducible components, and ﬁnally (iv) describing the original multiplicities, either numerically or by a primary ideal. Three of these four problems are the direct generalizations of the basic problems for factoring a single polynomial: we can eliminate multiple factors, getting a square-free polynomial, we can factor this into irreducible pieces and we can ask for the multiplicities with which each factor appeared in the original polynomial. There is a ﬁfth question which arises when we work, as we always must do on a computer, over a non-algebarically closed ﬁeld $k$: we can ask (v) for an extension ﬁeld ${k}^{\prime }$ of $k$ over which the irreducible components break up into absolutely irreducible components.

Classical algorithms for all of these of these rely heavily on making explicit projections of $V\left(I\right)$ to lower dimensional projective spaces. This can be done either by multi-variable resultants if you want only the set-theoretic projection, or by Gröbner bases with respect to the lexicographic order or an elimination order, to get the full ideal $I\cap k\left[{X}_{0},\cdots ,{X}_{m}\right]$. Recent treatments of multi-variable resultants can be found in [Can89], [Cha91], and a recent treatment of the basis method can be found in [GTZ88]. There is no evidence that either of these is an eﬃcient method, however, and taking Gröbner bases in the lexicographical order or an elimination order is often quite slow, certainly slow in the worst case. The general experience is that taking projections can be very time consuming. One reason is that the degree of the generators may go up substantially and that sparse deﬁning polynomials may be replaced by more or less generic polynomials. A speciﬁc example is given by principally polarized abelian varieties of dimension $r$: they are deﬁned by quadratic polynomials in $\left({4}^{r}-1\right)$-space, but their degree here (hence the degree of their generic projection to $\text{}Pr+1\text{}$) is ${4}^{r}r!$ [Mum70a]. In fact, any variety is deﬁned purely by quadratic relations in a suitable embedding [Mum70b].

Instead of using real computational experience, the fundamental method in theoretical computer science for analyzing complexity of algorithms is to count operations. For algebraic algorithms, the natural measure of complexity is not the number of bit operations, but the number of ﬁeld operations, addition, subtraction, multiplication and (possibly) division that are used. In this sense, any methods that involve taking Gröbner bases for any order on monomials will have a worst-case behavior whose complexity goes up with the regularity of the ideal hence will take “double exponential time”. However, it appears that this worst-case behavior may in fact only concern problem (iv) – ﬁnding the primary ideals – and that problems (i), (ii) and (iii) may be solvable in “single exponential time”. The idea that such algorithms should exist for ﬁnding $V\left(I\right)$ set-theoretically was proposed in the 1984 lecture on which this article is based, but turned out, in fact, to have been already proven by Chistov and Grigoriev, cf. their unpublished 1983 note [CG83]. Their line of research led, in some sense, to the work of Brownawell and Kollár, showing the single exponential bound ${\left(\sqrt{I}\right)}^{m}\subset I$ for $m={d}^{n}$, where $d=max\left(degreesofgeneratorsofI\right)$.

Based on this work, Giusti and Heintz [GH91] give a singly exponentially bounded algorithm for computing ideals ${q}_{i}$ such that $V\left({q}_{i}\right)$ are the irreducible components of $V\left(I\right)$ (over the ground ﬁeld $k$). The method depends on computing what is essentially the Chow form of each component, and leads to an ideal deﬁning this variety but not its full ideal. In fact, their ${q}_{i}$ may be guaranteed to be prime except for possible embedded components.

A direct approach to constructing both $\sqrt{I}$ and the intersection of the top-dimensional primary components of $I$, denoted $Top\left(I\right)$, is given in a recent paper by Eisenbud, Huneke and Vasconcelos [EHV92]. Their construction of the radical uses the Jacobian ideals, i.e. the ideals of minors of various sizes of the Jacobian matrix of generators of $I$. This is certainly the most direct approach, but, again they have trouble with possible embedded components, and must resort to ideal quotients, hence they need a Gröbner basis of $I$ in the reverse lexicographic order. They compute $Top\left(I\right)$ as the annihilator of ${Ext}^{codim\left(I\right)}\left(k\left[{X}_{0},\cdots ,{X}_{n}\right]∕I,k\left[{X}_{0},\cdots ,{X}_{n}\right]\right)$, which is readily found from a full resolution using Gröbner bases. Their algorithm appears to be practical in some cases of interest, but still has double exponential time worst-case behavior.

It may turn out to be most eﬀective in practice to combine these ideas. Often an ideal under study has regularity far smaller than the geometric degree of its top dimensional components; projecting these components to a hypersurface requires computing in degrees up to the geometric degree, which is wasteful. On the other hand, methods such as those in [EHV92] work better in low codimensions, if only because there are fewer minors to consider in the Jacobian matrix. Thus, projecting an arbitary scheme down to low codimension and then switching to direct methods may work best of all.

This still does not settle the issue of the complexity of calculating $\sqrt{I}$, or, for that matter, calculating the full prime ideal of any subvariety of codimension greater than one. Chow form type methods give you an eﬀective method of deﬁning the set $V\left(I\right)$ but only of generating $I$ up to possible embedded components. For this reason, the two schools of research, one based on the algebra of $I$, the other based on subsets of ${P}^{n}$ have diverged. If we knew, as discussed in the previous section, that the regularity of a reduced ideal could be bounded singly exponentially, then we could bound the degrees of the generators of $\sqrt{I}$, and, using Brownawell-Kollár, we could determine $\sqrt{I}$ up to these degrees and get the whole ideal. But without such a bound, it is still not clear whether only $V\left(I\right)$ and not $\sqrt{I}$ can be found in worst-case single exponential time.

Let’s look at problem (iii). Assume you have found a reduced equidimensional $I$. To study splitting it into irreducible or absolutely irreducible pieces, we shall assume initially it is a hypersurface, i.e. $I=\left(f\right)$. Computationally, there may often be advantages to not projecting a general $I$ to a hypersurface, and we will discuss one such approach below. Geometrically, there is nothing very natural about irreducible but not absolutely irreducible varieties: from the standpoint of their properties, they behave like reducible varieties, except that, being conjugate over $k$, their components have very similar properties. If the ground ﬁeld $k$ gets bigger or smaller, the set of absolutely irreducible components gets partitioned in ﬁner or coarser ways into the $k$-components. If one has never done any calculations, one would therefore be inclined to say – let’s extend $k$ as far as needed to split our algebraic set up into absolutely irreducible components. This is a very bad idea! Unless this extension ${k}^{\prime }$ happens to be something simple like a quadratic or cyclotomic extension of $k$, the splitting ﬁeld ${k}^{\prime }$ is usually gigantic. This is what happens if one component of $V\left(I\right)$ is deﬁned over an extension ﬁeld ${k}_{1}$ of $k$ of degree $e$, and the Galois group of ${k}_{1}∕k$ is the full symmetric group, a very common occurence. Then $V\left(I\right)$ only splits completely over the Galois closure of ${k}_{1}∕k$ and this has degree $e!$. The moral is: never factor unless you have to.

In fact, unless you need to deal simultaneously with more than one of its irreducible components, you can proceed as follows: the function ﬁeld $K=k\left[{X}_{0},\cdots ,{X}_{n}\right]∕\left(f\right)$ contains as a subﬁeld an isomorphic copy of ${k}_{1}$: you ﬁnd that ﬁeld as an extension ${k}_{1}=k\left[y\right]∕\left(p\left(y\right)\right)$ of $k$, and solve for the equation of one irreducible component ${f}_{1}\in {k}_{1}\left[{X}_{0},\cdots ,{X}_{n}\right]$ by the formula ${Norm}_{{k}_{1}∕k}\left({f}_{1}\right)=f$.

Pursuing this point, why should one even factor the deﬁning equation $f$ over $k$? Factoring, although it takes polynomial time [LLL82], is often very slow in real time, and, unless the geometry dictates that the components be treated separately, why not leave them alone. In some situations, for instance, [DD84] one may have an ideal, module or other algebraic structure deﬁned by polynomials or matrices of polynomials over a ground ring $D=k\left[y\right]∕\left(p\left(y\right)\right)$, where $p$ is a square-free polynomial. Thus $D$ is a direct sum of extension ﬁelds, but there is no need to factor $p$ or split up $D$ until the calculations take diﬀerent turns with the structures over diﬀerent pieces of $Spec\left(D\right)$.

The standard methods of factoring in computer algebra all depend on (i) writing the polynomial over a ring, ﬁnitely generated over $Z$, and reducing modulo a maximal ideal $m$ in that ring, obtaining a polynomial over a ﬁnite ﬁeld; and (ii) restricting to a line $L$, i.e. substituting ${X}_{i}={a}_{i}{X}_{0}+{b}_{i},i\ge 1$ for all but one variable, obtaining a polynomial in one variable over a ﬁnite ﬁeld. This is then factored and then, using Hensel’s lemma, one lifts this factorization modulo higher powers of $m$ and of the linear space $L$. One then checks whether a coarsened version of this factorization works for $f$. This is all really the arithmetic of various small ﬁelds. Geometrically, every polynomial in one variable factors over a suitable extension ﬁeld and the question of counting the absolutely irreducible components of a variety is really more elementary: it is fundamentally topological and not arithmetic. One should, therefore, expect there to be direct geometric ways of counting these components and separating them. Assuming $I$ is a reduced, equi-r-dimensional ideal, the direct way should be to use Serre duality, computing the cohomology ${H}^{r}\left({\Omega }_{V\left(I\right)}^{r}\right)$, where ${\Omega }_{V\left(I\right)}^{r}\subset {\omega }_{V\left(I\right)}$ is the subsheaf of the top-dimensional dualizing sheaf of $V\left(I\right)$ of absolutely regular $r$-forms. Its dimension will be the number of absolutely irreducible components into which $V\left(I\right)$ splits. Calculating this cohomology involves two things: algebraically resolving the ideal $I$ and geometrically resolving the singularities of $V\left(I\right)$ far enough to work out ${\Omega }_{V\left(I\right)}^{r}$. Classically, when $I=\left(f\right)$ was principal, ${\Omega }_{V\left(I\right)}^{r}$ was called its ideal of “subadjoint” polynomials.

There is one case where this is quite elementary and has been carried out: this is for plane curves. One can see immediately what is happening by remarking that a non-singular plane curve is automatically absolutely irreducible, hence one should expect that its singularities control its decomposition into absolutely irreducible pieces. Indeed, if $C\subset k\left[{X}_{0},{X}_{1},{X}_{2}\right]∕\left(f\right)$ is the conductor ideal, then ${\Omega }_{V\left(f\right)}^{1}$ is given by the homogeneous ideal $C$, but with degree 0 being shifted to be polynomials of degree $d-3$, $d$ the degree of $f$. To calculate ${H}^{1}$, assume ${X}_{0}$ is not zero at any singularity of $V\left(f\right)$ and look at the ﬁnite-dimensional vector space of all functions $k\left[{X}_{1}∕{X}_{0},{X}_{2}∕{X}_{0}\right]∕\left(C+\left(f\right)\right)$ modulo the restrictions $g∕\left({X}_{0}^{d-3}\right)$ for all homogeneous polynomials $g$ of degree $d-3$. This will be canonically the space of functions on the set of components of $V\left(f\right)$ with sum $0$. In particular, it is $\left(0\right)$ if and only if $V\left(f\right)$ is absolutely irreducible. This follows from standard exact sequences and duality theory. It was known classically as the Cayley-Bacharach theorem, for the special case where $V\left(f\right)$ was smooth except for a ﬁnite number of ordinary double points. It states that $V\left(f\right)$ is absolutely irreducible if and only if for every double point $P$, there is a curve of degree $d-3$ passing through all the double points except $P$.

This example gives one instance where a deeper computational analysis of varieties requires a computation of its resolution of singularities. We believe that there will be many instances where practical problems will require such an analysis. In many ways, resolution theorems look quite algorithmic, and, for instance, Abhyankar and his school have been approaching the problem in this way [Abh82], as have Bierstone and Milman [BM91]. However, the only case of resolution of singularities to be fully analyzed in the sense of computational complexity is that of plane curves. This has been done by Teitelbaum [Tei89], [Tei90]. His analysis is notable in various ways: he is extremely careful about not making unnecessary factorizations, let alone taking unnecessary ﬁeld extensions, and uses the “$D$” formalism discussed above. He describes his algorithm so precisely that it would be trivial to convert it to code and, as a result, he gives excellent bounds on its complexity.

References

[Abh82]    S. S. Abhyankar, Weighted expansions for canonical desingularization, Lecture Notes in Math., vol. 910, Springer-Verlag, 1982.

[Art76]    M. Artin, Lectures on deformations of singularities, Tata Institute on Fundamental Research, Bombay, 1976.

[Bay82]    Dave Bayer, The division algorithm and the Hilbert scheme, Ph.D. thesis, Harvard University, Department of Mathematics, June 1982, order number 82-22588, University Microﬁlms International, 300 N. Zeeb Rd., Ann Arbor, MI 48106.

[BEL91]    Aaron Bertram, Lawrence Ein, and Robert Lazarsfeld, Vanishing theorems, a theorem of Severi, and the equations deﬁning projective varieties, J. Amer. Math. Soc. 4 (1991), 587–602.

[Ber78]    G. M. Bergman, The diamond lemma for ring theory, Adv. in Math. 29 (1978), 178–218.

[BM88]    Dave Bayer and Ian Morrison, Standard bases and geometric invariant theory I. Initial ideals and state polytopes, J. Symb. Comput. 6 (1988), no. 2–3, 209–217, reprinted in [Rob89].

[BM91]    E. Bierstone and P. Milman, A simple constructive proof of canonical resolution of singularities, Eﬀective methods in algebraic geometry (Castiglioncello, 1990), Progr. Math., vol. 94, Birkhauser Boston, 1991, pp. 11–30.

[BCR91]    A. M. Bigatti, M. Caboara, and L. Robbiano, On the computation of Hilbert-Poincare series, Applicable Algebra in Engineering, Communications, and Computing 2 (1991), 21–33.

[Bri73]    J. Briancon, Weierstrass prepare a la Hironaka, Astérisque 7,8 (1973), 67–73.

[Bro87]    W. D. Brownawell, Bounds for the degrees in the Nullstellensatz, Ann. of Math. (2) 126 (1987), 577–591.

[BS87a]    Dave Bayer and Mike Stillman, A criterion for detecting $m$-regularity, Invent. Math. 87 (1987), 1–11.

[BS87b]    Dave Bayer and Mike Stillman, A theorem on reﬁning division orders by the reverse lexicographic order, Duke Math. J. 55 (1987), no. 2, 321–328.

[BS88]    Dave Bayer and Mike Stillman, On the complexity of computing syzygies, J. Symb. Comput. 6 (1988), 135–147.

[BS92a]    Dave Bayer and Mike Stillman, Macaulay: A system for computation in algebraic geometry and commutative algebra, 1982–1992, computer software available via anonymous ftp from zariski.harvard.edu.

[BS92b]    Dave Bayer and Mike Stillman, Computation of Hilbert functions, J. Symb. Comput. 6 (1992), 31-50.

[Buc65]    B. Buchberger, Ph.D. thesis, Univ. Innsbrück, 1965.

[Buc76]    B. Buchberger, A theoretical basis for the reduction of polynomials to canonical forms, ACM SIGSAM Bull. 39 (1976), 19–29.

[Buc79]     B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Gröbner bases, Symbolic and Algebraic Computation (Proceedings of EUROSAM 79), Lecture Notes in Computer Science, vol. 72, Springer-Verlag, 1979, pp. 3–21.

[Can89]    J. Canny, Generalized characteristic polynomials, Symbolic and Algebraic Computation (Proceedings of ISSAC 88), Lecture Notes in Computer Science, vol. 358, Springer-Verlag, 1989, pp. 293–299.

[CG83]    A. L. Chistov and D. Yu. Grigoriev, Subexponential-time solving systems of algebraic equations I, II, Steklov Mathematical Institute, Leningrad department, LOMI Preprints E-9-93, 0E-10-c83, 1983.

[Cha91]    Marc Chardin, Un algorithme pour le calcu des résultants, Eﬀective methods in algebraic geometry (Castiglioncello, 1990), Progr. Math., vol. 94, Birkhauser Boston, 1991, pp. 47–62.

[DD84]    C. Dicrescenzo and D. Duval, Computations on curves, Lecture Notes in Computer Science, vol. 174, Springer-Verlag, 1984.

[EG84]    David Eisenbud and Shiro Goto, Linear free resolutions and minimal multiplicity, J. Algebra 88 (1984), no. 1, 89–133.

[EHV92]    David Eisenbud, Craig Huneke, and Wolmer Vasconcelos, Direct methods for primary decomposition, Invent. Math. (1992), to appear.

[Eis92]    David Eisenbud, Commutative algebra with a view toward algebraic geometry, 1992, in preparation.

[Gal74]    A. Galligo, A propos du theoreme de preparation de Weierstrass, Fonctions de Plusieurs Variables Complexes, Lecture Notes in Math., vol. 409, Springer-Verlag, 1974, pp. 543–579.

[Gal79]    A. Galligo, Theoreme de division et stabilite en geometrie analytique locale, Ann. Inst. Fourier (Grenoble) 29 (1979), 107–184.

[GH91]    Marc Giusti and Joos Heintz, Algorithmes—disons rapides—pour la decomposition d’une variete algebrique en composantes irreductibles et equidimensionnelles [“Fast” algorithms for the decomposition of an algebraic variety into irreducible and equidimensional components], Eﬀective methods in algebraic geometry (Castiglioncello, 1990), Progr. Math., vol. 94, Birkhauser Boston, 1991, pp. 169–194.

[Giu84]    Marc Giusti, Some eﬀectivity problems in polynomial ideal theory, EUROSAM 84), Lecture Notes in Computer Science, vol. 204, Springer-Verlag, 1984, pp. 159–171.

[GLP83]    L. Gruson, R. Lazarsfeld, and C. Peskine, On a theorem of Castelnuovo, and the equations deﬁning space curves, Invent. Math. 72 (1983), 491–506.

[GTZ88]    P. Gianni, B. Trager, and G. Zacharias, Gröbner bases and primary decomposition of polynomial ideals, J. Symb. Comput. 6 (1988), no. 2–3, 149–167, reprinted in [Rob89].

[Her26]    Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), 736–788.

[Hir64]    H. Hironaka, Resolution of singularities of an algebraic variety over a ﬁeld of characteristic zero: I, II, Ann. of Math. (2) 79 (1964), 109–326.

[Kol88]    János Kollár, Sharp eﬀective Nullstellensatz, J. Amer. Math. Soc. 1 (1988), no. 4, 963–975.

[Lak91]    Y. N. Lakshman, A simple exponential bound on the complexity of computing gröbner bases of zero-dimensional ideals, Eﬀective methods in algebraic geometry (Castiglioncello, 1990), Progr. Math., vol. 94, Birkhauser Boston, 1991, pp. 227–234.

[Laz87]    Robert Lazarsfeld, A sharp Castelnuovo bound for smooth surfaces, Duke Math. J. 55 (1987), 423–429.

[Len92]    H. W. Lenstra, Jr., Algorithms in algebraic number theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 2, 211–244.

[Lip84]    Joseph Lipman, Dualizing sheaves, diﬀerentials and residues on algebraic varieties, Astérisque, vol. 117, 1984.

[LL91]    Y. N. Lakshman and D. Lazard, On the complexity of zero-dimensional algebraic systems, Eﬀective methods in algebraic geometry (Castiglioncello, 1990), Progr. Math., vol. 94, Birkhauser Boston, 1991, pp. 217–225.

[LLL82]    A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coeﬃcients, Math. Ann. 261 (1982), 515–534.

[Mac27]    F. S. Macaulay, Some properties of enumeration in the theory of modular systems, Proc. London Math. Soc. 26 (1927), 531–555.

[MM82]    Ernst W. Mayr and Albert R. Meyer, The complexity of the word problem for commutative semigroups and polynomial ideals, Adv. in Math. 46 (1982), 305–329.

[MM83]    H. Michael Möller and Ferdinando Mora, Upper and lower bounds for the degree of Gröbner bases, Computer Algebra (EUROCAL 83), Lecture Notes in Computer Science, vol. 162, Springer-Verlag, 1983, pp. 157–167.

[MM86]    H. Michael Möller and Ferdinando Mora, New constructive methods in classical ideal theory, J. Algebra 100 (1986), no. 1, 138–178.

[MR88]    T. Mora and L. Robbiano, The Gröbner fan of an ideal, J. Symb. Comput. 6 (1988), no. 2–3, 183–208, reprinted in [Rob89].

[Mum66]    David Mumford, Lectures on curves on an algebraic surface, Princeton University Press, Princeton, New Jersey, 1966.

[Mum70a]   David Mumford, Abelian varieties, Oxford University Press, Oxford, 1970.

[Mum70b]   David Mumford, Varieties deﬁned by quadratic equations, Questions on Algebraic Varieties, Centro Internationale Matematica Estivo, Cremonese, Rome, 1970, pp. 29–100.

[MW83]    D. W. Masser and G. Wüstholz, Fields of large transcendence degree generated by values of elliptic functions, Invent. Math. 72 (1983), 407–464.

[Pin86]    Henry C. Pinkham, A Castelnuovo bound for smooth surfaces, Invent. Math. 83 (1986), 491–506.

[Ran90]    Ziv Ran, Local diﬀerential geometry and generic projections of threefolds, J. Diﬀerential Geom. 32 (1990), 131–137.

[Rav90]    M. S. Ravi, Regularity of ideals and their radicals, Manuscripta Math. 68 (1990), 77–87.

[Ric74]    F. Richman, Constructive aspects of Noetherian rings, Proc. Amer. Math. Soc. 44 (1974), 436–441.

[Rob85]    L. Robbiano, Term orderings on the polynomial ring, Proceedings of EUROCAL ’85 (Linz), Lecture Notes in Computer Science, vol. 204, Springer-Verlag, 1985, pp. 513–517.

[Rob89]    Lorenzo Robbiano (ed.), Computational aspects of commutative algebra, Academic Press, 1989, ISBN 0-12-589590-9.

[Sch80]    Frank-Olaf Schreyer, Die Berechnung von Syzygien mit dem verallgemeinerten Weierstrass’schen Divisionssatz, Diplomarbeit am Fachbereich Mathematik der Universität Hamburg, 1980.

[Sch91]    Frank-Olaf Schreyer, A standard basis approach to syzygies of canonical curves, J. Reine Angew. Math. 421 (1991), 83–123.

[Ser55]    J.-P. Serre, Faisceaux algebrique coherents, Ann. of Math. (2) 61 (1955), 197–278.

[Spe77]    D. Spear, A constructive approach to commutative ring theory, Proceedings of the 1977 MACSYMA Users’ Conference, NASA CP-2012, 1977, pp. 369–376.

[Tei89]    Jeremy Teitelbaum, On the computational complexity of the resolution of plane curve singularities, Symbolic and algebraic computation (Rome, 1988), Lecture Notes in Computer Science, vol. 358, Springer, 1989, pp. 285–292.

[Tei90]    Jeremy Teitelbaum, The computational complexity of the resolution of plane curve singularities, Math. Comp. 54 (1990), no. 190, 797–837.

[Tri78]    W. Trinks, Über B. Buchberger’s Verfahren, Systeme algebraischer Gleichungen zu lösen, J. Number Theory 10 (1978), 475–488.

[Zac78]    G. Zacharias, Bachelor’s thesis, Mass. Inst. of Technology, 1978.

[Zar69]    Oscar Zariski, An introduction to the theory of algebraic surfaces, Lecture Notes in Math., vol. 83, Springer-Verlag, 1969.

[ZS76]    Oscar Zariski and Pierre Samuel, Commutative algebra, Volumes I, II, Graduate texts in mathematics, vol. 28–29, Springer-Verlag, 1975–1976.