format: text

text:
# A Combinatorial Approach to Involution and 𝛿-Regularity II: Structure Analysis of Polynomial Modules with Pommaret Bases

## 1 Introduction

Rees rees:polymod  introduced a combinatorial decomposition of finitely generated polynomial modules and related it for graded modules to the Hilbert series. Later, more general decompositions of $`𝕜`$-algebras were studied by Stanley and several other authors (see e. g. bg:comb ; bcs:stanley ; rps:hilbert ; rps:diophant ), especially in the context of Cohen-Macaulay complexes but also for other applications like invariant theory or the theory of normal forms of vector fields with nilpotent linear part. Sturmfels and White sw:comb  presented algorithms to compute various combinatorial decompositions.

Apparently all these authors have been unaware that similar decompositions are implicitly contained in the Janet-Riquier theory of differential equations. In fact, they represent the fundamental idea underlying this theory. Involutive bases combine this idea with concepts from Gröbner bases. As we have seen in Part I, one may consider involutive bases as those Gröbner bases which automatically induce a combinatorial decomposition of the ideal they generate.

The main goal of this second part is to show that Pommaret bases possess a number of special properties not shared by other involutive bases which makes them particularly useful for the structure analysis of polynomial modules. A number of important invariants can be directly read off a Pommaret basis. One reason for this is that Pommaret bases induce the special type of decomposition introduced by Rees rees:polymod  and which now carries his name.

Pommaret bases (for ideals in power series rings) implicitly appeared already in the classical work of Hironaka hh:resol  on the resolution of singularities. Later, Amasaki ma:applweier ; ma:gener  followed up this idea and explicitly introduced them under the name Weierstraß bases because of their connection to the Weierstraß Preparation Theorem. In his study of their properties, Amasaki obtained to some extent similar results than we present in this article, however in a different way.

This second part is organised as follows. Section 2 discusses the problem of $`\delta `$-regularity and presents a very simple and effective criterion for detecting $`\delta `$-singular coordinate systems based on a comparison of the Janet and Pommaret multiplicative variables. The proof of this criterion furthermore implies a method for the automatic construction of $`\delta `$-regular coordinates without destroying too much sparsity. As a first application, we determine the depth of a polynomial ideal $``$ and a maximal $``$-regular sequence.

The following section studies combinatorial decompositions of general polynomial modules using involutive bases. A trivial application, already given by Janet ja:lec  and Stanley rps:hilbert , is the determination of the Hilbert series and thus of the Krull dimension. For Pommaret bases an alternative characterisation of the dimension can be given which is related to Gröbner’s approach via maximal independent sets of variables wg:mag ; kw:dim . Extending our previous results on the depth from submodules to arbitrary polynomial modules, we obtain as a simple corollary Hironaka’s criterion for Cohen-Macaulay modules.

Section 4 discusses the relation between $`\delta `$-regularity and Noether normalisation. It turns out that searching $`\delta `$-regular coordinates for an ideal $``$ is equivalent to putting simultaneously $``$ and all primary components of $`\mathrm{lt}_{}`$ into Noether position. As a by-product we provide a number of equivalent characterisations for monomial ideals possessing a Pommaret basis and show how an irredundant primary decomposition of such ideals can be easily obtained. These results are heavily based on recent work by Bermejo and Gimenez bg:scmr .

Section 5 develops the syzygy theory of involutive bases. We show that the involutive standard representations of the non-multiplicative multiples of the generators induce a Gröbner basis (for an appropriately chosen term order) of the first syzygy module. Essentially, this involutive form of Schreyer’s theorem follows from the ideas behind Buchberger’s second criterion for redundant $`S`$-polynomials. For Janet and Pommaret bases the situation is even better, as the arising Gröbner basis is then again a Janet and Pommaret basis, respectively.

In the next three sections we construct by iteration of this result free resolutions of minimal length. We first outline the construction for arbitrary polynomial modules with a Pommaret basis. Then we specialise to monomial modules where one can always endow the resolution with the structure of a differential algebra and provide an explicit formula for the differential. In the special case of a stable monomial module the resolution is even minimal. Most of these results are inspired by and generalisations of the work of Eliahou and Kervaire ek:res .

In Section 9 we show that the degree of a Pommaret basis with respect to the degree reverse lexicographic order equals the Castelnuovo-Mumford regularity of the ideal. Together with our results on the construction of $`\delta `$-regular coordinates, this leads to a simple effective method for the computation of this important invariant. As corollaries we recover characterisations of the Castelnuovo-Mumford regularity previously proposed by Bayer/Stillman bs:mreg  and Eisenbud/Goto eg:freeres . In the following section we discuss the relation between regularity and saturation from the point of view of Pommaret bases. Here we make contact with recent works of Trung ngt:cmr  and Bermejo/Gimenez bg:scmr .

Finally, we apply the previously developed syzygy theory to the construction of involutive bases in iterated polynomial algebras of solvable type. A rather technical appendix clarifies the relation between Pommaret bases and the Sturmfels-White approach sw:comb  to the construction of Rees decompositions.

## 2 Pommaret Bases and $`\delta `$-Regularity

We saw in Part I (Example 2.12) that not every monoid ideal in $`_0^n`$ possesses a finite Pommaret basis: the Pommaret division is not Noetherian. Obviously, this is also implies that there are polynomial ideals $`𝒫=𝕜[x_1,\mathrm{},x_n]`$ without a finite Pommaret basis for a given term order. However, we will show now that at the level of *polynomial* ideals this may be considered as solely a problem of the chosen variables $`\stackrel{}{x}`$. For this purpose, we take in the sequel the following point of view: term orders are defined for exponent vectors, i. e. on the monoid $`_0^n`$; performing a linear change of variables $`\stackrel{~}{\stackrel{}{x}}=A\stackrel{}{x}`$ leads to new exponent vectors in each polynomial which are then sorted according to the same term order as before.

###### Definition 1

The variables $`\stackrel{}{x}`$ are *$`\delta `$-regular* for the ideal $`𝒫`$ and the term order $``$, if $``$ possesses a finite Pommaret basis for $``$.

Given our definition of an involutive basis, it is obvious that $`\delta `$-regularity concerns the existence of a Pommaret basis for the monoid ideal $`\mathrm{le}_{}`$. A coordinate transformation generally yields a new leading ideal which may possess a Pommaret basis. In fact, we will show in this section that for every polynomial ideal $`𝒫`$ variables $`\stackrel{}{x}`$ exist such that $``$ has a finite Pommaret basis provided that the chosen term order $``$ is class respecting.111Recall from the appendix of Part I that any class respecting term order coincides on terms of the same degree with the reverse lexicographic order.

Besides showing the mere existence of $`\delta `$-regular variables, we will develop in this section an effective approach to recognising $`\delta `$-singular coordinates and transforming them into $`\delta `$-regular ones. It is inspired by the work of Gerdt vpg:janpom  on the relation between Pommaret and Janet bases and the key ideas have already been used in the context of the combined algebraic-geometric completion to involution of linear differential equations wms:geocompl . We begin by proving two useful technical lemmata. The number $`\mathrm{max}_h\mathrm{deg}h`$ is called the *degree* of the finite set $`𝒫`$ and denoted by $`\mathrm{deg}`$.

###### Lemma 1

Let the set $``$ be a homogeneous Pommaret basis of the homogeneous ideal $`𝒫`$. Then for any degree $`q\mathrm{deg}`$ a Pommaret basis of the truncated ideal $`_q=_{pq}_p`$ is given by

$$_q=\{x^\mu hh,|\mu |+\mathrm{deg}h=q,j>\mathrm{cls}h:\mu _j=0\}.$$
(1)
Conversely, if $`_q`$ possesses a finite Pommaret basis, then so does $``$.

###### Proof

According to the conditions in (1), each polynomial $`h`$ is multiplied by terms $`x^\mu `$ containing only variables which are multiplicative for it. Thus trivially $`\mathrm{cls}(x^\mu h)=\mathrm{cls}\mu `$. Furthermore, $`_q`$ is involutively head autoreduced, as $``$ is. Now let $`f_q`$ be an arbitrary homogeneous polynomial. As $``$ is a Pommaret basis of $``$, it has a standard representation $`f=_hP_hh`$ with polynomials $`P_h𝕜[x_1,\mathrm{},x_{\mathrm{cls}h}]`$. Hence $`f`$ can be written as a linear combination of polynomials $`x^\nu h`$ where $`|\nu |=\mathrm{deg}f\mathrm{deg}hq\mathrm{deg}h`$ and where $`x^\nu `$ contains only multiplicative variables. We decompose $`\nu =\mu +\rho `$ with $`|\mu |=q\mathrm{deg}h`$ and $`\rho _j=0`$ for all $`j>\mathrm{cls}\mu `$. Thus $`x^\nu h=x^\rho (x^\mu h)`$ with $`x^\mu h_q`$ and $`x^\rho `$ contains only variables multiplicative for it. But this trivially implies the existence of a standard representation $`f=_{h^{}_q}P_h^{}h^{}`$ with $`P_h^{}𝕜[x_1,\mathrm{},x_{\mathrm{cls}h^{}}]`$ and thus $`_q`$ is a Pommaret basis of $`_q`$.

The converse is also very simple. Let $`_q`$ be a finite Pommaret basis of the truncated ideal $`_q`$ and $`_p`$ head autoreduced $`𝕜`$-linear bases of the components $`_p`$ for $`0p<q`$. If we set $`=_{p=0}^q_q`$, then $`\mathrm{le}_{}`$ is obviously a weak Pommaret basis of the full monoid ideal $`\mathrm{le}_{}`$ and by Proposition 5.7 of Part I an involutive head autoreduction yields a strong basis.∎

###### Lemma 2

With the same notations as in Lemma 1, let $`𝒩=\mathrm{le}_{}_q`$. If $`\nu 𝒩`$ with $`\mathrm{cls}\nu =k`$, then222Recall from Part I that $`\mathrm{}_i`$ denotes for any number $`\mathrm{}`$ the multi index where all entries except the $`i`$th one vanish and the $`i`$th one is given by $`\mathrm{}`$. $`\nu 1_k+1_j𝒩`$ for all $`k<jn`$. Conversely, let $`𝒩(_0^n)_q`$ be a set of multi indices of degree $`q`$. If for each $`\nu 𝒩`$ with $`\mathrm{cls}\nu =k`$ and each $`k<jn`$ the multi index $`\nu 1_k+1_j`$ is also contained in $`𝒩`$, then the set $`𝒩`$ is involutive for the Pommaret division.

###### Proof

$`j`$ is non-multiplicative for $`\nu `$. As $`𝒩`$ is an involutive basis of $`\mathrm{le}_{}_q`$, it must contain a multi index $`\mu `$ with $`\mu |_P\nu +1_j`$. Obviously, $`\mathrm{cls}(\nu +1_j)=k`$ and thus $`\mathrm{cls}\mu k`$. Because of $`|\mu |=|\nu |`$, the only possibility is $`\mu =\nu +1_j1_k`$. The converse is trivial, as each non-multiplicative multiple of $`\nu 𝒩`$ is of the form $`\nu +1_j`$ with $`j>k=\mathrm{cls}\nu `$ and hence has $`\nu 1_k+1_j`$ as an involutive divisor.∎

As in practice one is defining an ideal $`𝒫`$ by some finite generating set $``$, we introduce a concept of $`\delta `$-regularity for such sets. Assume that $``$ is involutively head autoreduced with respect to an involutive division $`L`$ and a term order $``$; then we call the total number of multiplicative variables of the elements of $``$ its *involutive size* and denote it by

$$||_{L,}=\underset{f}{}|X_{L,,}(f)|.$$
(2)
Let $`\stackrel{~}{\stackrel{}{x}}=A\stackrel{}{x}`$ be a linear change of coordinates with a regular matrix $`A𝕜^{n\times n}`$. It transforms each polynomial $`f𝒫`$ into a polynomial $`\stackrel{~}{f}\stackrel{~}{𝒫}=𝕜[\stackrel{~}{x}_1,\mathrm{},\stackrel{~}{x}_n]`$ of the same degree. Thus $``$ is transformed into a set $`\stackrel{~}{}\stackrel{~}{𝒫}`$ which generally is no longer involutively head autoreduced. Performing an involutive head autoreduction yields a set $`\stackrel{~}{}^{\mathrm{}}`$. The leading exponents of $`\stackrel{~}{}^{\mathrm{}}`$ may be very different from those of $``$ and thus $`||_{L,}`$ may differ from $`|\stackrel{~}{}^{\mathrm{}}|_{L,}`$.

###### Definition 2

Let the finite set $`𝒫`$ be involutively head autoreduced with respect to the Pommaret division and a term order $``$. The coordinates $`\stackrel{}{x}`$ are called *$`\delta `$-regular* for $``$ and $``$, if after any linear change of coordinates $`\stackrel{~}{\stackrel{}{x}}=A\stackrel{}{x}`$ the inequality $`||_{P,}|\stackrel{~}{}^{\mathrm{}}|_{P,}`$ holds.

###### Example 1

Let us reconsider Example 2.12 of Part I where $`=\{xy\}𝕜[x,y]`$. Independent of how we order the variables, the class of $`xy`$ is $`1`$. After the change of coordinates $`x=\stackrel{~}{x}+\stackrel{~}{y}`$ and $`y=\stackrel{~}{y}`$, we obtain the set $`\stackrel{~}{}=\{\stackrel{~}{y}^2+\stackrel{~}{x}\stackrel{~}{y}\}𝕜[\stackrel{~}{x},\stackrel{~}{y}]`$. If we use the degree reverse lexicographic order, the leading term is $`\stackrel{~}{y}^2`$ which is of class $`2`$. Thus it is possible to enlarge the involutive size of $``$ and the original coordinates are not $`\delta `$-regular. The new coordinates obviously are, as a higher class than $`2`$ is not possible. $``$

Note that generally $`\delta `$-regularity of the variables $`\stackrel{}{x}`$ for a finite set $``$ according to Definition 2 and for the ideal $`=`$ according to Definition 1 are independent properties. For a concrete instance where the two definitions differ see Example 2 below where one easily checks that the used coordinates are $`\delta `$-regular for the whole submodule but not for the given generating set, as any transformation of the form $`x=\overline{x}+a\overline{y}`$ with $`a0`$ will increase the involutive size. The main point is that $`\delta `$-regularity for the ideal $``$ is concerned with the monoid ideal $`\mathrm{le}_{}`$ whereas $`\delta `$-regularity for the set $``$ depends on the ideal $`\mathrm{le}_{}\mathrm{le}_{}`$.

###### Proposition 1

Let $``$ be a Pommaret basis of the ideal $`𝒫`$ for the term order $``$. Then the coordinates $`\stackrel{}{x}`$ are $`\delta `$-regular for $``$ and $``$.

###### Proof

By definition, $`\mathrm{le}_{}`$ is a Pommaret basis of $`\mathrm{le}_{}`$. Thus it suffices to consider homogeneous ideals and, by Lemma 1, we may further reduce to the case that all generators are of the same degree $`q`$. The involutive size of $`_q`$ is then the vector space dimension of $`_{q+1}`$. This value is independent of the chosen coordinates and no involutively head autoreduced set can lead to a larger involutive size. Thus our coordinates are $`\delta `$-regular for $``$, too.∎

Thus we conclude that $`\delta `$-regularity is necessary for the existence of Pommaret bases and from an algorithmic point of view $`\delta `$-singular coordinates are “bad”. Note that for the completion Algorithm 3 of Part I $`\delta `$-regularity for the current basis $``$ is as important as $`\delta `$-regularity for the ideal $`=`$. Even if the variables $`\stackrel{}{x}`$ are $`\delta `$-regular for $``$, it may still happen that the algorithm does not terminate, as it tries to construct a non-existing Pommaret basis for $`\mathrm{le}_{}`$.

###### Example 2

One of the simplest instance where this termination problem occurs is not for an ideal but for a submodule of the free $`𝕜[x,y]`$-module with basis $`\{\stackrel{}{e}_1,\stackrel{}{e}_2\}`$. Consider the set $`=\{y^2\stackrel{}{e}_1,xy\stackrel{}{e}_1+\stackrel{}{e}_2,x\stackrel{}{e}_2\}`$ and any term order for which $`xy\stackrel{}{e}_1\stackrel{}{e}_2`$. The used coordinates are not $`\delta `$-regular for $``$, as any transformation of the form $`x=\overline{x}+a\overline{y}`$ with $`a0`$ will increase the involutive size. Nevertheless, the used coordinates are $`\delta `$-regular for the submodule $``$. Indeed, adding the generator $`y\stackrel{}{e}_2`$ (the $`S`$-“polynomial” of the first two generators) makes $``$ to a reduced Gröbner basis which is simultaneously a minimal Pommaret basis.

Note that the termination of the involutive completion algorithm depends here on the precise form of the used term order. If we have $`xy^k\stackrel{}{e}_2xy^2\stackrel{}{e}_1`$ for all $`k`$, then the algorithm will not terminate, as in the $`k`$th iteration it will add the generator $`xy^k\stackrel{}{e}_2`$. Otherwise it will treat at some stage the non-multiplicative product $`y(xy\stackrel{}{e}_1+\stackrel{}{e}_2)`$ and thus find the decisive generator $`y\stackrel{}{e}_2`$. This is in particular the case for any degree compatible order. $``$

Fortunately, most coordinates are $`\delta `$-regular for a given set $``$ of polynomials. Choosing an arbitrary reference coordinate system, we may identify every system of coordinates with the regular matrix $`A𝕜^{n\times n}`$ defining the linear transformation from our reference system to it.

###### Proposition 2

The coordinate systems that are $`\delta `$-singular for a given finite involutively head autoreduced set $`𝒫`$ form a Zariski closed set in $`𝕜^{n\times n}`$.

###### Proof

We perform first a linear coordinate transformation with an undetermined matrix $`A`$, i. e. we treat its entries as parameters. This obviously leads to a $`\delta `$-regular coordinate system, as each polynomial in $`\stackrel{~}{}^{\mathrm{}}`$ will get its maximally possible class. $`\delta `$-singular coordinates are defined by the vanishing of certain (leading) coefficients. These coefficients are polynomials in the entries of $`A`$. Thus the set of all $`\delta `$-singular coordinate systems can be described as the zero set of an ideal.∎

Thus the $`\delta `$-singular coordinate systems form a variety of dimension less than $`n^2`$ in an $`n^2`$-dimensional space and if we randomly choose a coordinate system, it is $`\delta `$-regular with probability $`1`$. Nevertheless, $`\delta `$-singular coordinate systems exist for most sets $``$ (exceptions are sets like $`=\{x^2+y^2\}`$ over $`𝕜=`$ where one easily shows that any coordinate system is $`\delta `$-regular), and in applications such coordinates often show up. We will see below in the proof of Theorem 2.1 that it suffices for the construction of $`\delta `$-regular coordinates to consider only transformations $`\stackrel{}{x}A\stackrel{}{x}`$ where the matrix $`A`$ satisfies $`A_{ii}=1`$ and $`A_{ij}=0`$ for $`j>i`$.

Our goal is to develop a simple criterion that coordinates are $`\delta `$-singular for a given set $``$ and a class respecting term order. The basic idea is to compare the multiplicative variables assigned by the Pommaret and the Janet division, respectively. The definitions of these two divisions are very different. Somewhat surprisingly, they yield very similar results, as shown by Gerdt and Blinkov (gb:invbas, , Prop. 3.10).

###### Proposition 3

Let the finite set $`𝒩_0^n`$ be involutively autoreduced with respect to the Pommaret division. Then $`N_P(\nu )N_{J,𝒩}(\nu )`$ for all $`\nu 𝒩`$.

For later use, we mention the following simple corollaries which further study the relationship between the Janet and the Pommaret division. Recall that any set $`𝒩_0^n`$ is involutively autoreduced with respect to the Janet division. We first note that by an involutive autoreduction of $`𝒩`$ with respect to the *Pommaret* division its *Janet* span can become only larger but not smaller.

###### Corollary 1

Let $`𝒩_0^n`$ be an arbitrary finite set of multi indices and set $`𝒩_P=𝒩\{\nu 𝒩\mu 𝒩:\mu |_P\nu \}`$, i. e. we eliminate all multi indices possessing a Pommaret divisor in $`𝒩`$. Then $`𝒩_J𝒩_P_J`$.

###### Proof

If $`\mu ^{(1)}|_P\mu ^{(2)}`$ and $`\mu ^{(2)}|_P\nu `$, then trivially $`\mu ^{(1)}|_P\nu `$. Thus for each eliminated multi index $`\nu 𝒩𝒩_P`$ another multi index $`\mu 𝒩_P`$ exists with $`\mu |_P\nu `$. Let $`\mathrm{cls}\mu =k`$. By the proposition above $`\{1,\mathrm{},k\}N_{J,𝒩_P}(\mu )`$. Assume that an index $`j>k`$ exists with $`jN_{J,𝒩}(\nu )`$. By definition of the Pommaret division, $`\mu _i=\nu _i`$ for all $`i>k`$. Thus $`\mu (\nu _{j+1},\mathrm{},\nu _n)`$ and $`jN_{J,𝒩}(\mu )`$. As by the second condition on an involutive division $`N_{J,𝒩}(\mu )N_{J,𝒩_P}(\mu )`$ for all $`\mu 𝒩_P`$, we conclude that $`jN_{J,𝒩_P}(\mu )`$ and $`𝒞_{J,𝒩}(\nu )𝒞_{J,𝒩_P}(\mu )`$. But this immediately implies $`𝒩_J𝒩_P_J`$. ∎

This implies that any Pommaret basis is simultaneously a Janet basis (a similar result is contained in (vpg:janpom, , Thm. 17)). Thus if $``$ is a Pommaret basis, then $`X_{P,}(h)=X_{J,,}(h)`$ for all polynomials $`h`$.

###### Corollary 2

Let the finite set $`𝒫`$ be involutive with respect to the Pommaret division (and some term order). Then $``$ is also involutive for the Janet division.

###### Proof

By the proposition above, it is obvious that the set $``$ is at least weakly involutive with respect to the Janet division. For the Janet division any weakly involutive set is strongly involutive, if no two elements have the same leading terms. But as $``$ is a Pommaret basis, this cannot happen.∎

We show now that for $`\delta `$-regular coordinate systems and a class respecting term order the inclusions in Proposition 3 must be equalities. In other words, if a variable $`x_{\mathrm{}}`$ exists which is multiplicative for an element of $``$ with respect to the Janet division but non-multiplicative with respect to the Pommaret division, then the used coordinates are $`\delta `$-singular. Our proof is constructive in the sense that it shows us how to find coordinates leading to a larger involutive span.

###### Theorem 2.1

Let the finite set $`𝒫`$ be involutively head autoreduced for the Pommaret division and a class respecting term order $``$. Furthermore assume that the field $`𝕜`$ contains more than $`||\mathrm{deg}`$ elements. If $`||_{J,}>||_{P,}`$, then the coordinates $`\stackrel{}{x}`$ are $`\delta `$-singular for $``$.

###### Proof

By the proposition above, we have $`X_P(f)X_{J,}(f)`$ for all $`f`$. Assume that for a polynomial $`h`$ the strict inclusion $`X_P(h)X_{J,}(h)`$ holds. Thus at least one variable $`x_{\mathrm{}}X_{J,}(h)`$ with $`\mathrm{}>k=\mathrm{cls}h`$ exists. We perform the linear change of variables $`x_i=\stackrel{~}{x}_i`$ for $`ik`$ and $`x_k=\stackrel{~}{x}_k+a\stackrel{~}{x}_{\mathrm{}}`$ with a yet arbitrary parameter $`a𝕜\{0\}`$. This induces the following transformation of the terms $`x^\mu 𝕋`$:

$$x^\mu =\underset{j=0}{\overset{\mu _k}{}}\left(\genfrac{}{}{0pt}{}{\mu _k}{j}\right)a^j\stackrel{~}{x}^{\mu j_k+j_{\mathrm{}}}.$$
(3)
Let $`\mathrm{le}_{}h=\mu `$. Thus $`\mu =[0,\mathrm{},0,\mu _k,\mathrm{},\mu _n]`$ with $`\mu _k>0`$. Consider the multi index $`\nu =\mu (\mu _k)_k+(\mu _k)_{\mathrm{}}`$; obviously, $`\mathrm{cls}\nu >k`$. Applying our transformation to the polynomial $`h`$ leads to a polynomial $`\stackrel{~}{h}`$ containing the term $`\stackrel{~}{x}^\nu `$. Note that $`\nu `$ cannot be an element of $`\mathrm{le}_{}`$. Indeed, if it was, it would be an element of the same set $`(\mu _{\mathrm{}+1},\mathrm{},\mu _n)`$ as $`\mu `$. But this contradicts our assumption that $`\mathrm{}`$ is multiplicative for the multi index $`\mu `$ with respect to the Janet division, as by construction $`\nu _{\mathrm{}}>\mu _{\mathrm{}}`$.

Transforming all polynomials $`f`$ yields the set $`\stackrel{~}{}`$ on which we perform an involutive head autoreduction in order to obtain the set $`\stackrel{~}{}^{\mathrm{}}`$. Under our assumption on the size of the ground field $`𝕜`$, we can choose the parameter $`a`$ such that after the transformation each polynomial $`\stackrel{~}{f}\stackrel{~}{}`$ has at least the same class as the corresponding polynomial $`f`$, as our term order respects classes. This is a simple consequence of (3): cancellations of terms may occur only, if the parameter $`a`$ is a zero of some polynomial (possibly one for each member of $``$) with a degree not higher than $`\mathrm{deg}`$. By the definition of the Pommaret division, if $`\mathrm{le}_{}f_2|_P\mathrm{le}_{}f_1`$, then $`\mathrm{cls}\mathrm{le}_{}f_2\mathrm{cls}\mathrm{le}_{}f_1`$. Hence even after the involutive head autoreduction the involutive size of $`\stackrel{~}{}^{\mathrm{}}`$ cannot be smaller than that of $``$.

Consider again the polynomial $`h`$. The leading term of the transformed polynomial $`\stackrel{~}{h}`$ must be greater than or equal to $`\stackrel{~}{x}^\nu `$. Thus its class is greater than $`k`$. This remains true even after an involutive head autoreduction with all those polynomials $`\stackrel{~}{f}\stackrel{~}{}`$ that are of class greater than $`k`$, as $`x^\nu \mathrm{lt}_{}`$. Hence the only possibility to obtain a leading term of class less than or equal to $`k`$ consists of an involutive reduction with respect to a polynomial $`\stackrel{~}{f}\stackrel{~}{}`$ with $`\mathrm{cls}fk`$. But this implies that $`\mathrm{cls}\mathrm{le}_{}\stackrel{~}{f}>k`$. So we may conclude that after the transformation we have at least one polynomial more whose class is greater than $`k`$. So the coordinates $`\stackrel{}{x}`$ cannot be $`\delta `$-regular.∎

###### Corollary 3

If the coordinates $`\stackrel{}{x}`$ are $`\delta `$-regular for the Pommaret head autoreduced set $``$, then $`_{J,}=_{P,}`$ for any class respecting term order $``$.

It is important to note that this corollary provides us only with a necessary but *not* with a sufficient criterion for $`\delta `$-regularity. In other words, even if the Janet and the Pommaret size are equal for a given set $`𝒫`$, this does not imply that the used coordinates are $`\delta `$-regular.

###### Example 3

Let $`=\{\underset{¯}{z^2}y^22x^2,\underset{¯}{xz}+xy,\underset{¯}{yz}+y^2+x^2\}`$. The underlined terms are the leaders with respect to the degree reverse lexicographic order. One easily checks that the Janet and the Pommaret division yield the same multiplicative variables. If we perform the transformation $`\stackrel{~}{x}=z`$, $`\stackrel{~}{y}=y+z`$ and $`\stackrel{~}{z}=x`$, then after an autoreduction we obtain the set $`\stackrel{~}{}^{\mathrm{}}=\{\underset{¯}{\stackrel{~}{z}^2}\stackrel{~}{x}\stackrel{~}{y},\underset{¯}{\stackrel{~}{y}\stackrel{~}{z}},\underset{¯}{\stackrel{~}{y}^2}\}`$. Again the Janet and the Pommaret division yield the same multiplicative variables, but $`|\stackrel{~}{}^{\mathrm{}}|_{P,}>||_{P,}`$. Thus the coordinates $`(x,y,z)`$ are not $`\delta `$-regular for $``$.

The explanation of this phenomenon is very simple. Obviously our criterion depends only on the leading terms of the set $``$. In other words, it analyses the monomial ideal $`\mathrm{lt}_{}`$. Here $`\mathrm{lt}_{}=xz,yz,z^2`$ and one easily verifies that the used generating set is already a Pommaret basis. However, for $`=`$ the leading ideal is $`\mathrm{lt}_{}=x^3,xz,yz,z^2`$ (one obtains a Janet basis for $``$ by adding the polynomial $`x^3`$ to $``$) and obviously it does not possess a finite Pommaret basis, as such a basis would have to contain all monomials $`x^3y^k`$ with $`k`$ (or we exploit our criterion noting that $`y`$ is a Janet but not a Pommaret multiplicative variable for $`x^3`$). Thus we have the opposite situation compared to Example 2: there $`\mathrm{lt}_{}`$ had a finite Pommaret basis but $`\mathrm{lt}_{}`$ not; here it is the other way round. We will show later in Proposition 14 that whenever $`\mathrm{lt}_{}`$ does not possess a finite Pommaret basis, then $`||_{J,}>||_{P,}`$. $``$

While we have defined $`\delta `$-regularity as a problem of the Pommaret division, this example shows that the Janet division “feels” it, too. Usually it yields in $`\delta `$-singular coordinates a lower number of multiplicative variables and thus larger involutive bases. $`\delta `$-regularity is a typical phenomenon in commutative algebra: many results hold only in “generic” coordinates, i. e. from a Zariski open set.

Now we are finally in the position to prove that in suitably chosen coordinates every ideal possesses a finite Pommaret basis for any term order. The proof exploits again the close relationship of the Janet and the Pommaret division and a little trick due to Gerdt vpg:janpom .

###### Theorem 2.2

Let $``$ be an arbitrary term order and the field $`𝕜`$ sufficiently large. Then every ideal $`𝒫`$ possesses a finite Pommaret basis for $``$ in suitably chosen variables $`\stackrel{}{x}`$.

###### Proof

As a first step we show that every ideal has a *Pommaret* head autoreduced *Janet* basis. Indeed, let us apply our polynomial completion algorithm (Algorithm 3 of Part I) for the Janet division with one slight modification: in the Lines /1/ and /9/ we perform the involutive head autoreductions with respect to the Pommaret division. It is obvious that if the algorithm terminates, the result is a basis with the wanted properties.

The Janet division is Noetherian (Lemma 2.14 of Part I). Thus without our modification the termination is obvious. With respect to the Janet division every set of multi indices is involutively autoreduced. Hence a Janet head autoreduction only takes care that no two elements of a set have the same leading exponents. But in Line /9/ we add a polynomial that is in involutive normal form so that no involutive head reductions are possible. As the Pommaret head autoreduction may only lead to a larger monoid ideal $`\mathrm{le}_{}_i`$, the Noetherian argument in the proof of the termination of the algorithm remains valid after our modification.

Once the ascending ideal chain $`\mathrm{le}_{}_1\mathrm{le}_{}_2\mathrm{}`$ has become stationary, the polynomial completion algorithm essentially reduces to the “monomial” one (Algorithm 2 of Part I). According to Corollary 1, the Pommaret head autoreductions may only increase the Janet spans $`\mathrm{le}_{}_i_J`$. Thus the termination of the monomial completion is not affected by our modification and the algorithm terminates for arbitrary input.

By Proposition 2, the coordinate systems that are $`\delta `$-singular for a given finite set $`𝒫`$ form a Zariski closed set. As our modified algorithm terminates, it treats only a finite number of sets $`_i`$ and the coordinate systems that are $`\delta `$-singular for at least one monomial set $`\mathrm{lt}_{}_i`$ still form a Zariski closed set. Thus generic coordinates are $`\delta `$-regular for all sets $`\mathrm{lt}_{}_i`$ and by Corollary 3333Note that it is not relevant here that the corollary assumes the use of a class respecting term order, since we are arguing only with monomial sets. their Janet and their Pommaret spans coincide. But this implies that the result of the modified algorithm is not only a Janet but also a Pommaret basis.∎

###### Remark 1

The assumption on the size of the field $`𝕜`$ is obviously trivially satisfied for a field of characteristic zero. In the case of a finite field, it may be necessary to enlarge $`𝕜`$ in order to guarantee the existence of a Pommaret basis. This is similar to the situation when one tries to put a zero-dimensional ideal in normal $`x_n`$-position kr:cca1 . $``$

###### Remark 2

In Part I we discussed the extension of the Mora normal form to involutive basis computation. Obviously, the above result remains valid, if we substitute the ordinary normal form by Mora’s version and hence we may also apply it to Pommaret bases with respect to semigroup orders. $``$

Theorem 2.1 provides us with an effective mean to detect that the completion to a Pommaret basis does *not* terminate. We follow the polynomial completion algorithm with the Pommaret division but check after each iteration whether $`|_i|_{J,}=|_i|_{P,}`$. If no finite Pommaret basis exists in the given coordinates, sooner or later the Janet size is greater than the Pommaret size. Indeed, by the considerations above the completion with respect to the Janet division terminates. Thus either the result is simultaneously a Pommaret basis or in some iteration our criterion must detect a variable which is multiplicative only for the Janet but not for the Pommaret division. Alternatively, we compute a Pommaret head autoreduced Janet basis (which always exists by the considerations above) and check whether it is simultaneously a Pommaret basis.

###### Example 4

Let us apply this approach to the Pommaret completion of the set $`=\{\underset{¯}{z^2}y^22x^2,\underset{¯}{xz}+xy,\underset{¯}{yz}+y^2+x^2\}`$ (with respect to the degree reverse lexicographic order). We have seen in Example 3 that the coordinates are not $`\delta `$-regular for $``$, although the Janet and the Pommaret span of $``$ coincide. According to our algorithm we must first analyse the polynomial $`y(xz+xy)`$. Its involutive normal form with respect to $``$ is $`\underset{¯}{x^3}`$. If we determine the multiplicative variables for the enlarged set, they do not change for the old elements. For the new polynomial the Janet division yields $`\{x,y\}`$. But $`y`$ is obviously not multiplicative for the Pommaret division. Thus our criterion tells us that the Pommaret completion will not terminate. Indeed it is easy to see that no matter how often we multiply the new polynomial by $`y`$, it will never become involutively head reducible and no finite Pommaret basis exists.

In this example, the Janet completion (with or without Pommaret autoreductions) ends with the addition of this single obstruction to involution and we obtain as Janet basis the set

$$_J=\{\underset{¯}{z^2}y^22x^2,\underset{¯}{xz}+xy,\underset{¯}{yz}+y^2+x^2,\underset{¯}{x^3}\}.$$
(4)
In Example 3 we showed that the transformation $`\stackrel{~}{x}=z`$, $`\stackrel{~}{y}=y+z`$ and $`\stackrel{~}{z}=x`$ yields after an autoreduction the set $`\stackrel{~}{}^{\mathrm{}}=\{\underset{¯}{\stackrel{~}{z}^2}\stackrel{~}{x}\stackrel{~}{y},\underset{¯}{\stackrel{~}{y}\stackrel{~}{z}},\underset{¯}{\stackrel{~}{y}^2}\}`$. One easily checks that it is a Pommaret and thus also a Janet basis. We see again that the Janet division also “feels” $`\delta `$-singularity in the sense that in such coordinates it typically leads to larger bases of higher degree. $``$

Besides being necessary for the mere existence of a finite Pommaret basis, a second application of $`\delta `$-regular coordinates is the construction of $``$-regular sequences for a homogeneous ideal $`𝒫`$. Recall that for any $`𝒫`$-module $``$ a sequence $`(f_1,\mathrm{},f_r)`$ of polynomials $`f_i𝒫`$ is called $``$-regular, if the polynomials generate a proper ideal, $`f_1`$ is a non zero divisor for $``$ and each $`f_i`$ is a non zero divisor for $`/f_1,\mathrm{},f_{i1}`$. The maximal length of an $``$-regular sequence is the *depth* of the module. While the definition allows for arbitrary polynomials in such sequences, it suffices for computing the depth to consider only linear forms $`f_i𝒫_1`$. This follows, for example, from (de:ca, , Cor. 17.7) or (sw:comb, , Lemma 4.1). For this reason, the following proof treats only this case.

###### Proposition 4

Let $`𝒫`$ be a homogeneous ideal and $``$ a homogeneous Pommaret basis of it for a class respecting term order. Let $`d=\mathrm{min}_h\mathrm{cls}h`$. Then the variables $`(x_1,\mathrm{},x_d)`$ form a maximal $``$-regular sequence and thus $`\mathrm{depth}=d`$.

###### Proof

A Pommaret basis $``$ induces a decomposition of $``$ of the form

$$=\underset{h}{}𝕜[x_1,\mathrm{},x_{\mathrm{cls}h}]h.$$
(5)
If $`d=\mathrm{min}_h\mathrm{cls}h`$ denotes the minimal class of a generator in $``$, then (5) trivially implies that the sequence $`(x_1,\mathrm{},x_d)`$ is $``$-regular.

Let us try to extend this sequence by a variable $`x_k`$ with $`k>d`$. We introduce $`_d=\{h\mathrm{cls}h=d\}`$ and choose an element $`\overline{h}_d`$ of maximal degree. As we use a class respecting order, $`\overline{h}x_1,\mathrm{},x_d`$ by Lemma A.1 of Part I. By construction, $`x_k`$ is non-multiplicative for $`\overline{h}`$ and for each $`h`$ a polynomial $`P_h𝕜[x_1,\mathrm{},x_{\mathrm{cls}h}]`$ exists such that $`x_k\overline{h}=_hP_hh`$. No polynomial $`h`$ with $`\mathrm{cls}h>d`$ lies in $`x_1,\mathrm{},x_d`$ (obviously $`\mathrm{lt}_{}hx_1,\mathrm{},x_d`$). As the leading terms cannot cancel in the sum, $`P_hx_1,\mathrm{},x_d`$ for all $`h_d`$. Thus $`x_k\overline{h}=_{h_d}c_hh+g`$ with $`c_h𝕜`$ and $`gx_1,\mathrm{},x_d`$. As $``$ is a homogeneous ideal and as the degree of $`\overline{h}`$ is maximal in $`_d`$, all constants $`c_h`$ must vanish.

It is not possible that $`\overline{h}x_1,\mathrm{},x_d`$, as otherwise $`\overline{h}`$ would be involutively head reducible by some other element of $``$. Hence we have shown that any variable $`x_k`$ with $`k>d`$ is a zero divisor in $`/x_1,\mathrm{},x_d`$ and the $``$-regular sequence $`(x_1,\mathrm{},x_d)`$ cannot be extended by any $`x_k`$ with $`k>d`$. Obviously, the same argument applies to any linear combination of such variables $`x_k`$.

Finally, assume that $`y_1,\mathrm{},y_{d+1}𝒫_1`$ form an $``$-regular sequence of length $`d+1`$. We extend them to a basis $`\{y_1,\mathrm{},y_n\}`$ of $`𝒫_1`$ and perform a coordinate transformation $`\stackrel{}{x}\stackrel{}{y}`$. Our basis $``$ transforms into the set $`_\stackrel{}{y}`$ and after an involutive head autoreduction we obtain the set $`_\stackrel{}{y}^{\mathrm{}}`$. In general, the coordinates $`\stackrel{}{y}`$ are not $`\delta `$-regular for $`_\stackrel{}{y}^{\mathrm{}}`$. But there exist coordinates $`\stackrel{~}{\stackrel{}{y}}`$ of the form $`\stackrel{~}{y}_k=y_k+_{i=1}^{k1}a_{ki}y_i`$ with $`a_{ki}𝕜`$ such that if we transform $``$ to them and perform afterwards an involutive head autoreduction, they are $`\delta `$-regular for the obtained set $`\stackrel{~}{}_\stackrel{}{y}^{\mathrm{}}`$.

This implies that $`\stackrel{~}{}_\stackrel{}{y}^{\mathrm{}}`$ is a Pommaret basis of the ideal it generates.444The involutive sizes of $``$ and $`\stackrel{~}{}_\stackrel{}{y}^{\mathrm{}}`$ are equal. Thus local involution of $``$ implies local involution of $`\stackrel{~}{}_\stackrel{}{y}^{\mathrm{}}`$ and for the Pommaret division as a continuous division local involution is equivalent to involution by Corollary 7.3 of Part I. Thus $`\mathrm{min}_{\stackrel{~}{h}\stackrel{~}{}_\stackrel{}{y}^{\mathrm{}}}\mathrm{cls}\stackrel{~}{h}=d`$ and by the same argument as above $`\stackrel{~}{y}_{d+1}`$ is a zero divisor in $`/\stackrel{~}{y}_1,\mathrm{},\stackrel{~}{y}_d`$. Because of the special form of the transformation from $`\stackrel{}{y}\stackrel{~}{\stackrel{}{y}}`$, we have $`\stackrel{~}{y}_1,\mathrm{},\stackrel{~}{y}_d=y_1,\mathrm{},y_d`$ and $`y_{d+1}`$ must be a zero divisor in $`/y_1,\mathrm{},y_d`$. But this contradicts the assumption that $`(y_1,\mathrm{},y_{d+1})`$ is an $``$-regular sequence and $`\mathrm{depth}=d`$.∎

###### Remark 3

One may wonder to what extent this result really requires the Pommaret division. Given an arbitrary involutive basis $``$ of $``$, we may introduce the set $`X_{}=_hX_{L,,}(h)`$; obviously, for a Pommaret basis $`X_{}=\{x_1,\mathrm{},x_d\}`$ with $`d=\mathrm{min}_h\mathrm{cls}h`$. Again it is trivial to conclude from the induced combinatorial decomposition that any sequence formed by elements of $`X_{}`$ is $``$-regular. But in general we cannot claim that these are *maximal* $``$-regular sequences and there does not seem to exist an obvious method to extend them. Thus only a lower bound for the depth is obtained this way.

As a simple example we consider the ideal $``$ generated by $`f_1=z^2xy`$, $`f_2=yzwx`$ and $`f_3=y^2wz`$. If we set $`x_1=w`$, $`x_2=x`$, $`x_3=y`$ and $`x_4=z`$, then it is straightforward to check that the set $`=\{f_1,f_2,f_3\}`$ is a Pommaret basis of $``$ with respect to the degree reverse lexicographic order. By Proposition 4, $`(w,x,y)`$ is a maximal $``$-regular sequence and $`\mathrm{depth}=3`$.

If we set $`x_1=w`$, $`x_2=z`$, $`x_3=y`$ and $`x_4=x`$, then no finite Pommaret basis exists; these coordinates are not $`\delta `$-regular. In order to obtain a Janet basis $`_J`$ of $``$ (for the degree reverse lexicographic order with respect to the new ordering of the variables), we must enlarge $``$ by $`f_4=z^3wx^2`$ and $`f_5=xz^3wx^3`$. We find now $`X_{}=\{w,z\}`$, as

$$\begin{array}{c}X_{J,_J,_{\text{degrevlex}}}(f_1)=\{w,z,y,x\},X_{J,_J,_{\text{degrevlex}}}(f_3)=\{w,z,y\},\\ X_{J,_J,_{\text{degrevlex}}}(f_i)=\{w,z\}\text{for}i=2,4,5,\end{array}$$
(6)
One easily verifies that both $`x`$ and $`y`$ are not zero divisors in $`/w,z`$, so that $`X_{}`$ can be extended to a maximal $``$-regular sequence. However, the Janet basis gives no indications, how this could be done. One could also conjecture that the minimal number of multiplicative variables for a generator gives the depth. But clearly this is also not true for the above Janet basis. Thus no obvious way seems to exist to deduce $`\mathrm{depth}`$ from it. $``$

## 3 Combinatorial Decompositions

In the proof of Proposition 4 we could already see the power of the direct sum decompositions induced by (strong) involutive bases. In this section we want to study this aspect in more details. All results apply to arbitrary finitely generated polynomial modules. But for notational simplicity, we restrict to graded $`𝕜`$-algebras $`𝒜=𝒫/`$ with a homogeneous ideal $`𝒫`$. If we speak of a basis of the ideal $``$, we always assume that it is homogeneous, too.

The main motivation of Buchberger for the introduction of Gröbner bases was to be able to compute effectively in such factor spaces. Indeed given a Gröbner basis $`𝒢`$ of the ideal $``$, the normal form with respect to $`𝒢`$ distinguishes a unique representative in each equivalence class. Our goal in this section is to show that Pommaret bases contain in addition much structural information about the algebra $`𝒜`$. More precisely, we want to compute fundamental invariants like the Hilbert polynomial (which immediately yields the Krull dimension and the multiplicity), the depth or the Castelnuovo-Mumford regularity (see Section 9). Our basic tools are combinatorial decompositions of the algebra $`𝒜`$ into direct sums of polynomial rings with a restricted number of variables.

###### Definition 3

A *Stanley decomposition* of the graded $`𝕜`$-algebra $`𝒜=𝒫/`$ is an isomorphism of graded $`𝕜`$-linear spaces

$$𝒜\underset{t𝒯}{}𝕜[X_t]t$$
(7)
with a finite set $`𝒯𝕋`$ and sets $`X_t\{x_1,\mathrm{},x_n\}`$.

The elements of the set $`X_t`$ are again called the *multiplicative variables* of the generator $`t`$. As a first, trivial application of such decompositions we determine the Hilbert series and the (Krull) dimension.

###### Proposition 5 (rps:hilbert )

Let the graded algebra $`𝒜`$ possess the Stanley decomposition (7). Then its Hilbert series is

$$_𝒜(\lambda )=\underset{t𝒯}{}\frac{\lambda ^{q_t}}{(1\lambda )^{k_t}}$$
(8)
where $`q_t=\mathrm{deg}t`$ and $`k_t=|X_t|`$. Thus the (Krull) dimension of $`𝒜`$ is given by $`D=\mathrm{max}_{t𝒯}k_t`$ and the multiplicity (or degree) by the number of terms $`t𝒯`$ with $`k_t=D`$.

Vasconcelos (wvv:comp, , p. 23) calls Stanley decompositions *“an approach that is not greatly useful computationally but it is often nice theoretically”*. One reason for this assessment is surely that the classical algorithm for their construction works only for monomial ideals and uses a recursion over the variables $`x_1,\mathrm{},x_n`$. Thus for larger $`n`$ it becomes quite inefficient. For a general ideal $``$ one must first compute a Gröbner basis of $``$ for some term order $``$ and then, exploiting the vector space isomorphism $`𝒫/𝒫/\mathrm{lt}_{}`$, one determines a Stanley decomposition. Its existence is guaranteed by the following result.

###### Proposition 6

Let $`_0^n`$ be a monoid ideal and $`\overline{}=_0^n`$ its complementary set. There exists a finite set $`\overline{𝒩}\overline{}`$ and for each multi index $`\nu \overline{𝒩}`$ a set of indices $`N_\nu \{1,\mathrm{},n\}`$ such that555Recall from Part I the notation $`_N^n=\{\nu _0^njN:\nu _j=0\}`$.

$$\overline{}=\underset{\nu \overline{𝒩}}{}\left(\nu +_{N_\nu }^n\right)$$
(9)
and $`(\nu +_{N_\nu }^n)(\mu +_{N_\mu }^n)=\mathrm{}`$ for all $`\mu ,\nu \overline{𝒩}`$.

A proof of this proposition may be found in the textbook (clo:iva, , pp. 417–418) (there it is not shown that one can always construct a disjoint decomposition, but this extension is trivial). This proof is not completely constructive, as a certain degree $`q_0`$ is defined by a Noetherian argument. But it is not difficult to see that we may take $`q_0=\mathrm{max}_{\nu 𝒩}\nu _n`$ where $`𝒩`$ is the minimal basis of the monoid ideal $``$. Now one can straightforwardly transform the proof into a recursive algorithm for the construction of Stanley decompositions. In fact, one obtains then the algorithm proposed by Sturmfels and White sw:comb .

One must stress that the decomposition (9) is not unique and different decompositions may use sets $`\overline{𝒩}`$ of different sizes. Given an involutive basis of the monoid ideal $``$, it is trivial to determine a disjoint decomposition of $``$ itself. However, there does not seem to exist an obvious way to obtain a complementary decomposition (9). The situation is different for Janet bases where already Janet (ja:lec, , §15) presented a solution of this problem. Again it is easy to see that it can straightforwardly be extended to an algorithm. We recall his proof in our notations, as we will need it later on.

###### Proposition 7

Let $`𝒩_J`$ be a Janet basis of the monoid ideal $`_0^n`$. Then the set $`\overline{𝒩}_0^n`$ in the decomposition (9) may be chosen such that for all $`\nu \overline{𝒩}`$ the equality $`N_\nu =N_{J,𝒩_J\{\nu \}}(\nu )`$ holds.

###### Proof

666For an alternative proof see pr:janet .

We explicitly construct the set $`\overline{𝒩}`$. Let $`q_n=\mathrm{max}_{\mu 𝒩_J}\mu _n`$. Then we put into $`\overline{𝒩}`$ all multi indices $`\nu =[0,\mathrm{},0,q]`$ such that $`0q<q_n`$ and such that $`𝒩_J`$ does not contain any multi index $`\mu `$ with $`\mu _n=q`$. We set $`N_\nu =\{1,\mathrm{},n1\}`$ which obviously is $`N_{J,𝒩_J\{\nu \}}(\nu )`$ according to the definition of the Janet division.

Let $`(d_k,\mathrm{},d_n)𝒩_J`$ be one of the subsets considered in the assignment of the Janet multiplicative variables to the elements of $`𝒩_J`$ (see Example 2.2 in Part I) and set $`q_{k1}=\mathrm{max}_{\mu (d_k,\mathrm{},d_n)}\mu _{k1}`$. We enlarge the set $`\overline{𝒩}`$ by all those multi indices $`\nu =[0,\mathrm{},0,q,d_k,\mathrm{},d_n]`$ where $`0q<q_{k1}`$ and where $`(d_k,\mathrm{},d_n)`$ does not contain any multi index $`\mu `$ with $`\mu _{k1}=q`$. The corresponding sets $`N_\nu `$ of multiplicative indices contain the indices $`1,\mathrm{},k1`$ and all those indices greater than $`k`$ that are multiplicative for the elements of $`(d_k,\mathrm{},d_n)`$. Again it is easy to verify that this entails $`N_\nu =N_{J,𝒩_J\{\nu \}}(\nu )`$.

We claim that the thus constructed set $`\overline{𝒩}`$ (together with the sets $`N_\nu `$) defines a disjoint decomposition (9) of the complementary set $`\overline{}`$. We proceed by an induction on $`n`$. The case $`n=1`$ is trivial. Suppose that our assertion is true for $`n1`$. Let $`\rho _0^n`$ be an arbitrary multi index and let $`q_1<q_2<\mathrm{}<q_r`$ represent all values that occur for the entry $`\mu _n`$ in the multi indices $`\mu 𝒩_J`$. We distinguish three cases depending on $`\rho _n`$: (i) $`\rho _n<q_r`$ but $`\rho _n\{q_1,\mathrm{},q_{r1}\}`$, (ii) $`\rho _n\{q_1,\mathrm{},q_{r1}\}`$, and (iii) $`\rho _nq_r`$.

In the first case, the set $`\overline{𝒩}`$ contains the multi index $`\nu =[0,\mathrm{},0,\rho _n]`$ and, as $`N_\nu =\{1,\mathrm{},n1\}`$, obviously $`\rho \nu +_{N_\nu }^n`$. It is easy to see that $`\rho `$ cannot be an element of $``$ or of the cone $`\overline{\nu }+_{N_{\overline{\nu }}}^n`$ of any other multi index $`\overline{\nu }\overline{𝒩}`$.

In the second case, we “slice” the two sets $`𝒩_J`$ and $`\overline{𝒩}`$ at degree $`\rho _n`$. For this purpose we must introduce some notations. Primed letters always refer to multi indices $`\nu ^{}_0^{n1}`$; unprimed ones to multi indices $`\nu _0^n`$. For a given $`\nu _0^n`$, we define $`\nu ^{}=[\nu _1,\mathrm{},\nu _{n1}]_0^{n1}`$, i. e. we simply drop the last entry. Finally, we write $`[\nu ^{},q]`$ for the multi index $`[\nu _1,\mathrm{},\nu _{n1},q]_0^n`$. If we are given some monoid ideal $`_0^n`$, we define for every integer $`q_0`$ the monoid ideal $`_q^{}=\{\nu ^{}_0^{n1}[\nu ^{},q]\}_0^{n1}`$.

The “slicing” yields the two sets: $`𝒩_J^{}=\{\mu ^{}_0^{n1}\mu 𝒩_J,\mu _n=\rho _n\}`$ and $`\overline{𝒩}^{}=\{\nu ^{}_0^{n1}\nu \overline{𝒩},\nu _n=\rho _n\}`$, respectively. If we compute the sets $`N_{J,𝒩_J^{}}(\mu ^{})`$ of multiplicative indices for the elements $`\mu ^{}𝒩_J^{}`$, it is straightforward to verify that they are just $`N_{J,𝒩_J}(\mu )`$, as $`\mu _n`$ is not maximal and $`\mu (\rho _n)`$, if and only if $`\mu ^{}𝒩_J^{}`$. Furthermore, $`𝒩_J^{}`$ is a Janet basis of the monoid ideal $`_{\rho _n}^{}`$. If we apply the procedure above to this ideal in $`_0^{n1}`$, we obtain $`\overline{𝒩}^{}`$ as complementary basis and the sets of multiplicative variables remain unchanged.

By our inductive hypothesis, $`\overline{𝒩}^{}`$ defines a disjoint decomposition of the sought form of the set $`\overline{}_{\rho _n}^{}`$. If $`\rho \overline{}`$, then $`\rho ^{}\overline{}_{\rho _n}^{}`$ and a multi index $`\nu ^{}\overline{𝒩}^{}`$ exists such that $`\rho ^{}\nu ^{}+_{N_\nu ^{}}^{n1}`$. By construction, $`\nu =[\nu ^{},\rho _n]\overline{𝒩}`$ and $`\rho \nu +_{N_\nu }^n`$. If $`\rho `$, then $`\rho ^{}_{\rho _n}^{}`$, and it is not possible to find a multi index $`\nu ^{}\overline{𝒩}^{}`$ such that $`\rho ^{}\nu ^{}+_{N_\nu ^{}}^{n1}`$. Hence $`\rho \nu +_{N_\nu }^n`$ for any $`\nu \overline{𝒩}`$.

The third case is very similar to the second one. For the definition of $`𝒩_J^{}`$ and $`\overline{𝒩}^{}`$ we consider only multi indices where the value of the last entry is $`q_r`$. Note that for all multi indices $`\nu \overline{𝒩}`$ that contribute to $`\overline{𝒩}^{}`$ the index $`n`$ is multiplicative. If $`\rho \overline{}`$, then $`\rho ^{}\overline{}_{\rho _n}^{}`$ and a multi index $`\nu ^{}\overline{𝒩}^{}`$ exists such that $`\rho ^{}\nu ^{}+_{N_\nu ^{}}^{n1}`$ and we conclude as above that $`\rho \nu +_{N_\nu }^n`$ for $`\nu =[\nu ^{},q_r]\overline{𝒩}`$. Again it is obvious that for a multi index $`\rho `$, it is not possible to find such a $`\nu \overline{𝒩}`$.∎

We have formulated this proposition only for the case that $`𝒩_J`$ is a Janet basis, but the proof yields an even stronger result. Let $`𝒩_J`$ be an *arbitrary* subset of $`_0^n`$ and construct the corresponding set $`\overline{𝒩}`$. Then we may substitute everywhere in the proof $``$ by the involutive span $`𝒩_J_J`$ and still obtain that any multi index $`\rho _0^n`$ either lies in $`𝒩_J_J`$ or in exactly one of the cones defined by $`\overline{𝒩}`$ and the sets $`N_\nu `$.

###### Remark 4

Janet did not formulate his algorithm in this algebraic language. He considered the problem of determining a formally well-posed initial value problem for an overdetermined system of partial differential equations wms:habil . Identifying this system with our ideal $``$, his problem is equivalent to computing a Stanley decomposition of $`𝒫/`$. An algorithmic approach to formally well-posed initial value problem was also presented by Reid gr:red . $``$

According to Corollary 2, we may apply the construction of Proposition 7 to Pommaret bases, too. But as the Pommaret division has such a simple global definition, it is almost trivial to provide an alternative decomposition depending only on the degree $`q`$ of a Pommaret basis of the ideal $``$ (we will see later in Sect. 9 that this degree is in fact an important invariant of $``$). In general, this decomposition is larger than the one obtained with the Janet approach but it has some advantages in theoretical applications.

###### Proposition 8

The monoid ideal $`_0^n`$ has a Pommaret basis of degree $`q`$, if and only if the sets $`\overline{𝒩}_0=\{\nu \overline{}|\nu |<q\}`$ and $`\overline{𝒩}_1=\{\nu \overline{}|\nu |=q\}`$ yield the disjoint decomposition

$$\overline{}=\overline{𝒩}_0\underset{\nu \overline{𝒩}_1}{}𝒞_P(\nu ).$$
(10)
###### Proof

The definition of the Pommaret division implies the identity

$$\left(_0^n\right)_q=\underset{|\nu |=q}{}𝒞_P(\nu )$$
(11)
from which one direction of the proposition follows trivially. Here $`\left(_0^n\right)_q`$ denotes the set of all multi indices of length greater than or equal to $`q`$. By the definition of an involutive division, the union on the right hand side is disjoint.

For the converse, we claim that the set $`=\{\mu _q\}`$ is a Pommaret basis of monoid ideal $`_q`$; this immediately implies our assertion by Lemma 1. Assume that $`\mu `$ with $`\mathrm{cls}\mu =k`$ and let $`k<jn`$ be a non-multiplicative index for it. We must show that $`\mu +1_j_P`$. But this is trivial: we have $`\mu +1_j𝒞_P(\mu 1_k+1_j)`$ and $`\mu 1_k+1_j_q`$, as otherwise we encounter the contradiction $`\mu +1_j`$ by (10).∎

###### Example 5

The decomposition (10) is usually redundant. Considering for $`\overline{𝒩}_1`$ only multi indices of length $`q`$ makes the formulation much easier but it is not optimal. Consider the trivial example $`𝒩_P=\left\{[0,1]\right\}`$. According to Proposition 8 we should set $`\overline{𝒩}_0=\left\{[0,0]\right\}`$ and $`\overline{𝒩}_1=\left\{[1,0]\right\}`$. But obviously $`\overline{}=[0,0]+_{\{1\}}^2`$. Applying the construction used in the proof of Proposition 7 yields directly this more compact form. $``$

If $`𝒥𝒫`$ is a polynomial ideal possessing a Pommaret basis for some term order $``$, then applying Proposition 8 to $`=\mathrm{le}_{}𝒥`$ yields a Stanley decomposition of a special type: all sets $`X_t`$ are of the form $`X_t=\{x_1,x_2,\mathrm{},x_{\mathrm{cls}t}\}`$ where the number $`\mathrm{cls}t`$ is called the *class*777Some authors prefer the term *level*. of the generator $`t`$. One speaks then of a *Rees decompositions* of $`𝒜=𝒫/𝒥`$ rees:polymod . It is no coincidence that we use here the same terminology as in the definition of the Pommaret division: if $`t=x^\mu `$ with $`\mu \overline{𝒩}_1`$, then indeed its class is $`\mathrm{cls}\mu `$. Reducing in a straightforward manner the redundancy in the decomposition (10) leads to the following result.

###### Corollary 4

Let $`𝒫`$ be a polynomial ideal which has for some term order $``$ a Pommaret basis $``$ such that $`\mathrm{min}_h\mathrm{cls}\mathrm{le}_{}h=d`$. Then $`𝒫/`$ possesses a Rees decomposition where the minimal class of a generator is $`d1`$.

###### Proof

Obviously, it suffices to consider the monomial case and formulate the proof therefore in the multi index language of Proposition 8. Furthermore, for $`d=1`$ there is nothing to be shown so that we assume from now on $`d>1`$. Our starting point is the decomposition (10). For each $`\nu \overline{𝒩}_1`$ with $`\mathrm{cls}\nu =k<d`$ we introduce the multi index $`\stackrel{~}{\nu }=\nu (\nu _k)_k`$, i. e. $`\stackrel{~}{\nu }`$ arises from $`\nu `$ by setting the $`k`$th entry to zero. Obviously, the $`k`$-dimensional cone $`C_\nu =\stackrel{~}{\nu }+_{\{1,\mathrm{},k\}}^n`$ is still completely contained in the complement $`\overline{}`$ and $`𝒞_P(\nu )C_\nu `$.

If we replace in (10) for any such $`\nu `$ the cone $`𝒞_P(\nu )`$ by $`C_\nu `$, then we still have a decomposition of $`\overline{}`$, but no longer a disjoint one. We now show first that in the thus obtained decomposition all cones $`C`$ with $`0<dimC<d1`$ can be dropped without loss. Indeed, for $`k<d1`$ we consider the multi index $`\mu =\stackrel{~}{\nu }+(\nu _k)_{k+1}`$. Obviously, $`|\mu |=q`$ and $`\mathrm{cls}\mu =k+1`$; hence under the made assumptions $`\mu \overline{𝒩}_1`$. Furthermore, $`\stackrel{~}{\mu }=\mu (\mu _{k+1})_{k+1}`$ is a divisor of $`\stackrel{~}{\nu }`$ (the two multi indices can differ at most in their $`(k+1)`$st entries and $`\stackrel{~}{\mu }_{k+1}=0`$) and thus the inclusion $`C_\nu C_\mu =\stackrel{~}{\mu }+_{\{1,\mathrm{},k+1\}}^n`$ holds.

The remaining cones with $`dimCd1`$ are all disjoint. This is trivially true for all cones with $`dimCd`$, as these have not been changed. For the other ones, we note that if $`\mu `$ and $`\nu `$ are two multi indices with $`\mathrm{cls}\mu =\mathrm{cls}\nu =d1`$ and $`|\mu |=|\nu |=q`$, then they must differ at some position $`\mathrm{}`$ with $`\mathrm{}d`$. But this implies that the cones $`C_\mu `$ and $`C_\nu `$ are disjoint.

Thus there only remains to study the zero-dimensional cones consisting of the multi indices $`\nu \overline{𝒩}_0`$. If we set $`\mathrm{}=q|\nu |`$, then $`\mu =\nu +\mathrm{}_1\overline{𝒩}_1`$, since we assumed $`d>1`$, and trivially $`\nu C_\mu =(\mu (\mu _1)_1)+_{\{1\}}^n`$. By our considerations above the cone $`C_\mu `$ and thus $`\nu `$ is contained in some $`(d1)`$-dimensional cone. Therefore we may also drop all zero-dimensional cones and obtain a Rees decomposition where all cones are at least $`(d1)`$-dimensional. ∎

Sturmfels et al. stv:degree  introduced the notion of *standard pairs* also leading to a kind of combinatorial decomposition, however not a disjoint one. They consider pairs $`(\nu ,N_\nu )`$ where $`\nu _0^n`$ is a multi index and $`N_\nu \{1,\mathrm{},n\}`$ a set of associated indices. Such a pair is called *admissible*, if $`\mathrm{supp}\nu N_\nu =\mathrm{}`$, i. e. $`\nu _i=0`$ for all $`iN_v`$. On the set of admissible pairs one defines a partial order: $`(\nu ,N_\nu )(\mu ,N_\mu )`$, if and only if the restricted cone $`\mu +_{N_\mu }^n`$ is completely contained in $`\nu +_{N_\nu }^n`$. Obviously, this is equivalent to $`\nu \mu `$ and any index $`i`$ such that either $`\mu _i>\nu _i`$ or $`iN_\mu `$ is contained in $`N_\nu `$.

###### Definition 4

Let $`_0^n`$ be an arbitrary monoid ideal. An admissible pair $`(\nu ,N_\nu )`$ is called *standard* for $``$, if $`\nu +_{N_\nu }^n=\mathrm{}`$ and $`(\nu ,N_\nu )`$ is minimal with respect to $`<`$ among all admissible pairs with this property.

Any monoid ideal $`_0^n`$ leads thus automatically to a uniquely determined set of standard pairs. These define both a decomposition of the complementary set $`\overline{}`$ into cones (though these will overlap in general) and a decomposition of the ideal $``$ itself as an intersection of irreducible monomial ideals.

###### Proposition 9 (stv:degree )

Let $`_0^n`$ be an arbitrary monoid ideal and denote the set of all associated standard pairs by $`𝒮_{}=\{(\nu ,N_\nu )(\nu ,N_\nu )\text{ }\text{standard for }\}`$. Then the complementary set $`\overline{}`$ of $``$ can be written in the form

$$\overline{}=\underset{(\nu ,N_\nu )𝒮_{}}{}\nu +_{N_\nu }^n$$
(12)
and the ideal $``$ itself can be decomposed as

$$=\underset{(\nu ,N_\nu )𝒮_{}}{}(\nu _i+1)_iiN_\nu .$$
(13)
According to Sturmfels et al. (stv:degree, , Lemma 3.3) the number of standard pairs of a monomial ideal $``$ equals the *arithmetic degree* of $``$, a refinement of the classical concept of the degree of an ideal introduced by Bayer and Mumford bm:cac . We further note that the ideals on the right hand side of (13) are trivially irreducible, so that (13) indeed represents an irreducible decomposition of $``$.

In general, this decomposition is highly redundant. Let $`N\{1,\mathrm{},n\}`$ be an arbitrary subset and consider all standard pairs $`(\nu ,N_\nu )`$ with $`N_\nu =N`$. Obviously, among these only the ones with multi indices $`\nu `$ which are maximal with respect to divisibility are relevant for the decomposition (13) and in fact restricting to the corresponding ideals yields the irredundant irreducible decomposition of $``$ (which is unique according to (ms:cca, , Thm. 5.27)). Their intersection defines a possible choice for the primary component for the prime ideal $`𝔭_N=x_iiN`$, so that we can also extract an irredundant primary decomposition from the standard pairs. As a trivial corollary to these considerations the standard pairs immediately yield the set $`\mathrm{Ass}(𝒫/)`$ of associated prime ideals, as it consists of all prime ideals $`𝔭_N`$ such that a standard pair $`(\nu ,N)`$ exists.

Hoşten and Smith hs:monom  discuss two algorithms for the direct construction of the set $`𝒮_{}`$ of all standard pairs given the minimal basis of $``$. Alternatively, $`𝒮_{}`$ can easily be extracted from any complementary decomposition, as we show now. Thus once a Janet basis of $``$ is known, we may use Janet’s algorithm for the construction of a complementary decomposition and then obtain the standard pairs.

Let the finite set $`𝒯_{}=\{(\nu ,N_\nu )\nu _0^n,N_\nu \{1,\mathrm{},n\}\}`$ define a complementary decomposition of $``$. If the pair $`(\nu ,N_\nu )𝒯_{}`$ is not admissible, then we substitute it by the pair $`(\overline{\nu },N_\nu )`$ where $`\overline{\nu }_i=0`$ for all $`iN_\nu `$ and $`\overline{\nu }_i=\nu _i`$ else. Obviously, this operation produces an admissible pair and the thus obtained set $`\overline{𝒮}_{}`$ still defines a (generally no longer disjoint) decomposition of the complementary set $`\overline{}`$. Finally, we eliminate all pairs in $`\overline{𝒮}_{}`$ which are not minimal with respect to the partial order $``$ and obtain a set $`𝒮_{}`$.

###### Proposition 10

Let $`𝒯_{}`$ be a finite complementary decomposition of the monoid ideal $`_0^n`$. The thus constructed set $`𝒮_{}`$ consists of all standard pairs of $``$.

###### Proof

It is trivial to see that the set $`\overline{𝒮}_{}`$ contains only admissible pairs and that $`\nu +_{N_\nu }^n\overline{}`$ for any pair $`(\nu ,N_\nu )\overline{𝒮}_{}`$. Thus there only remains to show that all standard pairs are contained in $`\overline{𝒮}_{}`$.

Let $`(\mu ,N_\mu )`$ be an admissible pair such that $`\mu +_{N_\mu }^n\overline{}`$. Since the union of the cones $`\nu +_{N_\nu }^n`$ with $`(\nu ,N_\nu )\overline{𝒮}_{}`$ still covers $`\overline{}`$, the finiteness of $`\overline{𝒮}_{}`$ implies the existence of a multi index $`\overline{\mu }\mu +_{N_\mu }^n`$ and a pair $`(\nu ,N_\nu )\overline{𝒮}_{}`$ such that $`\overline{\mu }+_{N_\mu }^n\nu +_{N_\nu }^n`$ (obviously, it is not possible to cover $`\mu +_{N_\mu }^n`$ with a finite number of lower-dimensional cones). As both $`(\mu ,N_\mu )`$ and $`(\nu ,N_\nu )`$ are admissible pairs, this entails that in fact $`(\nu ,N_\nu )(\mu ,N_\mu )`$. Hence either $`(\mu ,N_\mu )\overline{𝒮}_{}`$ or it is not a standard pair.∎

###### Remark 5

If we use the decomposition (10) derived from a Pommaret basis of degree $`q`$, then the determination of the set $`\overline{𝒮}_{}`$ is completely trivial. For all pairs $`(\nu ,N_\nu )𝒯_{}`$ with $`|\nu |<q`$ we have $`N_\nu =\mathrm{}`$ and hence they are trivially admissible. For all other pairs we find that $`\mathrm{supp}\nu N_\nu =\{\mathrm{cls}\nu \}`$. Thus none of them is admissible, but they become admissible by simply setting the first non-vanishing entry of $`\nu `$ to zero. $``$

###### Example 6

Consider the ideal $`=z^3,yz^2xz^2,y^2xy𝕜[x,y,z]`$. Both a Janet and Pommaret basis of $``$ for the degree reverse lexicographic order is given by the set $`=\{z^3,yz^2xz^2,y^2zxyz,y^2xy\}`$. Following the construction in the proof of Proposition 7, we obtain the set $`𝒯=\{1,y,z,yz,z^2\}`$ and the complementary decomposition

$$𝒫/𝕜[x]𝕜[x]y𝕜[x]z𝕜[x]yz𝕜[x]z^2.$$
(14)
The term $`z^2`$ comes from the set $`(2)=\left\{[0,1,2]\right\}`$. The terms $`yz`$ and $`z`$ arise from $`(1)=\left\{[0,2,1]\right\}`$ and, finally, $`1`$ and $`y`$ stem from $`(0)=\left\{[0,2,0]\right\}`$. The last non-vanishing set $`(3)=\left\{[0,0,3]\right\}`$ does not contribute to the decomposition.

It follows from (14) that a complementary decomposition of the corresponding monoid ideal $`\mathrm{le}_{}=[0,0,3],[0,1,2],[0,2,0]`$ is given by

$$\begin{array}{cc}\hfill 𝒮_{}=\{& ([0,0,0],\{1\}),([0,1,0],\{1\}),([0,0,1],\{1\}),\hfill \\ & ([0,1,1],\{1\}),([0,0,2],\{1\})\}\hfill \end{array}$$
(15)
and one easily verifies that these are all standard pairs.

The complementary decomposition constructed via Proposition 8 is much larger. Besides many multi indices without any multiplicative indices, we obtain the following six multi indices for which $`1`$ is the sole multiplicative index: $`[3,0,0]`$, $`[2,1,0]`$, $`[2,0,1]`$, $`[1,1,1]`$, $`[1,2,0]`$ and $`[1,0,2]`$. After setting the first entry to zero, we find precisely the multi indices appearing in (15) plus the multi index $`[0,2,0]`$. As $`([0,1,0],\{1\})<([0,2,0],\{1\})`$, the latter pair is not minimal. The same holds for all pairs corresponding to the multi indices without multiplicative indices and hence we also arrive at (15). $``$

As an application of Rees decompositions, we show that given a Pommaret basis of the ideal $``$, we can easily read off the dimension and the depth of the algebra $`𝒜=𝒫/`$. In principle, the determination of the dimension is of course already settled by Proposition 5 for arbitrary involutive bases. However, in the case of a Pommaret basis a further useful characterisation of $`dim𝒜`$ exists.

###### Proposition 11

Let $``$ be a homogeneous Pommaret basis of the homogeneous ideal $`𝒫`$ with $`\mathrm{deg}=q`$ for some term order $``$. Then the dimension $`D`$ of the algebra $`𝒜=𝒫/`$ is

$$D=\mathrm{min}\left\{i,x_1,\mathrm{},x_i_q=𝒫_q\right\}.$$
(16)
###### Proof

The Hilbert polynomials of $`𝒜`$ and the truncation $`𝒜_q`$ coincide. Thus it suffice to consider the latter algebra. By Lemma 1, a Pommaret basis of $`_q`$ is given by the set $`_q`$ determined in (1). If $`D`$ is the smallest number such that $`_q,x_1,\mathrm{},x_D_q=𝒫_q`$, then all multi indices $`\nu `$ with $`|\nu |=q`$ and $`\mathrm{cls}\nu >D`$ lie in $`\mathrm{le}_{}_q`$ but a multi index $`\mu `$ exists such that $`|\mu |=q`$, $`\mathrm{cls}\mu =D`$ and $`\mu \mathrm{le}_{}_q`$. By Proposition 8, this observation entails that $`\mu `$ is a generator of class $`D`$ of the complementary decomposition (10) and that the decomposition does not contain a generator of higher class. But this trivially implies that $`dim𝒜=D`$.∎

In a terminology apparently introduced by Gröbner (wg:mag, , Section 131), a subset $`X_{}\{x_1,\mathrm{},x_n\}`$ is called *independent modulo* $``$, if $`𝕜[X_{}]=\{0\}`$. If even $`\mathrm{lt}_{}𝕜[X_{}]=\{0\}`$ for some term order $``$, then one speaks of a *strongly* independent set for $``$. One can show that the maximal size of either an independent or a strongly independent set coincides with $`dim𝒜`$. This approach to determining the dimension of an ideal has been taken up again by Kredel and Weispfenning kw:dim  using Gröbner bases (see also (bw:groe, , Sects 6.3 & 9.3)).

###### Corollary 5

Under the assumptions of Proposition 11, $`\{x_1,\mathrm{},x_D\}`$ is the unique maximal strongly independent set modulo the ideal $``$.

###### Proof

As above, it suffices to consider the truncation $`_q`$. Assume that a non-zero polynomial $`f_q`$ exists with $`\mathrm{lt}_{}f𝕜[x_1,\mathrm{},x_D]`$. As $`_q`$ is a Pommaret basis of the ideal $`_q`$, it must contain a polynomial $`h`$ such that $`\mathrm{le}_{}h|_P\mathrm{le}_{}f`$; this implies $`\mathrm{lt}_{}h𝕜[x_d,\mathrm{},x_D]`$. Repeated applications of Lemma 2 to $`\mathrm{le}_{}h`$ with $`j=D`$ yields that $`\nu =q_D\mathrm{le}_{}_q`$. Further applications of Lemma 2 to $`\nu `$ with $`k=D`$ show that in fact any multi index of length $`q`$ and class $`D`$ is contained in $`\mathrm{le}_{}_q`$. But thus already $`,x_1,\mathrm{},x_{D1}_q=𝒫_q`$ in contradiction to the characterisation of $`D`$ in Proposition 11.

Hence $`\{x_1,\mathrm{},x_D\}`$ is a strongly independent set. Any larger strongly independent set would have to contain at least one variable $`x_j`$ with $`j>D`$. However, according to the proof of Proposition 11 any multi index $`\mu `$ with $`\mathrm{cls}\mu >D`$ and thus in particular $`\mu =j_q`$ lies in $`\mathrm{le}_{}_q`$. Therefore no strongly independent set may contain such a variable $`x_j`$.∎

Applying standard arguments in homological algebra to the exact sequence $`0𝒫𝒫/0`$, one can easily show that $`\mathrm{depth}(𝒫/)=\mathrm{depth}1`$. Hence Proposition 4 immediately implies the following result (one can also easily prove it directly along the lines of the proof of Proposition 4).

###### Proposition 12

Let $``$ be a homogeneous Pommaret basis of the homogeneous ideal $`𝒫`$ for a class respecting term order and $`d=\mathrm{min}_h\mathrm{cls}h`$. Then the depth of $`𝒜=𝒫/`$ is $`\mathrm{depth}𝒜=d1`$.

Since $`\{x_1,\mathrm{},x_{d1}\}`$ is trivially a strongly independent set modulo $``$, we obviously find that always $`Dd1`$. Thus as a trivial corollary to Propositions 11 and 12, we find the well-known fact that for any graded algebra $`𝒜=𝒫/`$ the inequality $`\mathrm{depth}𝒜dim𝒜`$ holds. In the limit case $`\mathrm{depth}𝒜=dim𝒜`$, the algebra is by definition *Cohen-Macaulay* and we obtain the following characterisation of such algebras.

###### Theorem 3.1

Let $``$ be a Pommaret basis of degree $`q`$ of the homogeneous ideal $`𝒫`$ for a class respecting term order $``$ and set $`d=\mathrm{min}_h\mathrm{cls}h`$. The algebra $`𝒜=𝒫/`$ is Cohen-Macaulay, if and only if $`,x_1,\mathrm{},x_{d1}_q=𝒫_q`$.

An alternative characterisation, which is more useful for computations, is based on the existence of a special kind of Rees decomposition; one sometimes speaks of a , a terminology introduced in (bs:inv, , Sect. 2.3).

###### Corollary 6

$`𝒜=𝒫/`$ is a Cohen-Macaulay algebra, if and only if a Rees decomposition of $`𝒜`$ exists where all generators have the same class.

###### Proof

One direction is trivial. If such a special decomposition exists with $`d`$ the common class of all generators, then obviously both the dimension and the depth of $`𝒜`$ is $`d`$ and thus $`𝒜`$ is Cohen-Macaulay.

For the converse, let us assume that $`𝒜`$ is a Cohen-Macaulay algebra and that $`dim𝒜=\mathrm{depth}𝒜=d`$. Let $``$ be a Pommaret basis of $``$ with respect to the degree reverse lexicographic order. By Theorem 2.2, such a basis always exists in $`\delta `$-regular variables $`\stackrel{}{x}`$. Proposition 12 implies that $`\mathrm{min}_h\mathrm{cls}h=d+1`$. We introduce the set $`\overline{𝒩}=\{\nu _0^n\mathrm{le}_{}\mathrm{cls}\nu >d\}`$ (recall that by convention we defined $`\mathrm{cls}[0,\mathrm{},0]=n`$ so that $`[0,\mathrm{},0]\overline{𝒩}`$ whenever $`𝒫`$). $`\overline{𝒩}`$ is finite, as all its elements satisfy $`|\nu |<\mathrm{deg}`$ by Theorem 3.1, and we claim that

$$𝒜\underset{\nu \overline{𝒩}}{}𝕜[x_1,\mathrm{},x_d]x^\nu .$$
(17)
In fact, this is precisely the decomposition obtained by applying the algorithm implicitly contained in the proof of Proposition 7. Consider any multi index $`\nu \overline{𝒩}`$; obviously, it is of the form $`\nu =[0,\mathrm{},0,\nu _{d+1},\mathrm{},\nu _n]`$ with $`_{i=d+1}^n\nu _i<q=\mathrm{deg}`$. If we set $`q^{}=q_{i=d+2}^n\nu _i`$, then by Theorem 3.1 the multi index $`[0,\mathrm{},0,q^{},\nu _{d+2},\mathrm{},\nu _n]`$ lies in the monoid ideal $`\mathrm{le}_{}`$. But this implies the existence of a multi index $`\nu ^{}\mathrm{le}_{}`$ with $`\nu ^{}=[0,\mathrm{},0,\nu _{d+1}^{},\nu _{d+2},\mathrm{},\nu _n]`$ with $`\nu _{d+1}<\nu _{d+1}^{}q^{}`$. Hence the set $`(\nu _{d+2},\mathrm{},\nu _n)`$ is considered in the assignment of multiplicative variables to the elements of $``$ for the Janet division and it consists only of the multi index $`\nu ^{}`$, as $``$ is involutively head autoreduced (with respect to the Pommaret division). But this implies that our algorithm chooses $`\nu `$ as an element of $`\overline{𝒩}`$ and assigns to it the multiplicative variables $`x_1,\mathrm{},x_d`$.

The algorithm cannot lead to a larger set $`\overline{𝒩}`$, as any further multi index would be of class less than or equal to $`d`$ and thus be contained in $`𝕜[x_1,\mathrm{},x_d]1`$. But we know that the sets are disjoint, so that this cannot happen and we get the decomposition (17).∎

###### Example 7

Consider again the ideal $`=z^3,yz^2xz^2,y^2xy𝕜[x,y,z]`$ of Example 6. It follows from the Pommaret basis given there that both the depth and the dimension of $`𝒫/`$ is $`1`$. Hence $`𝒜=𝒫/`$ is Cohen-Macaulay and indeed (14) is a Hironaka decomposition. $``$

## 4 Noether Normalisation and Primary Decomposition

One immediately sees that any strongly independent set is automatically also an independent set (the converse is generally not true). Hence Corollary 5 entails that $`𝕜[x_1,\mathrm{},x_D]=\{0\}`$ and now it is easy to show that a Pommaret basis of the ideal $``$ defines a *Noether normalisation* (gp:singular, , Def. 3.4.2) of the algebra $`𝒜`$ (or that $`x_1,\mathrm{},x_D`$ form a *homogeneous system of parameters* for it).

###### Corollary 7

Under the assumptions of Proposition 11, the restriction of the canonical projection $`\pi :𝒫=𝕜[x_1,\mathrm{},x_n]𝒜=𝒫/`$ to $`𝕜[x_1,\mathrm{},x_D]`$ is a Noether normalisation of $`𝒜`$. If $``$ is a Pommaret bases with respect to the (degree) lexicographic order, then it is even a general Noether normalisation.

###### Proof

It follows immediately from Corollary 5 that the restriction of the projection $`\pi `$ to $`𝕜[x_1,\mathrm{},x_D]`$ is injective. Thus there only remains to show that $`𝒜`$ is finitely generated as a $`𝕜[x_1,\mathrm{},x_D]`$-module. Proposition 8 gives us the complementary decomposition (10) for $`\mathrm{le}_{}`$ which is defined by a finite set $`𝒩_0^n`$. As for each generator in $`𝒩`$ the associated multiplicative indices form a subset of $`\{1,\mathrm{},D\}`$ and since the complement of $`\mathrm{lt}_{}`$ is a basis of $`𝒜`$ as $`𝕜`$-linear space, the finite set $`\{\pi (x^\nu )\nu 𝒩\}`$ generates $`𝒜`$ as $`𝕜[x_1,\mathrm{},x_D]`$-module.

It follows from the considerations in the proof of Proposition 11 that for each $`D<kn`$ the basis $`_q`$ contains a generator $`h_k`$ with leading term $`x_k^q`$. If $``$ is a Pommaret basis with respect to the (degree) lexicographic order, then $`h_k`$ must be of the form $`h_k=x_k^q+_{j=0}^{q1}P_{k,j}x_k^j`$ with polynomials $`P_{k,j}𝕜[x_1,\mathrm{},x_{k1}]`$. Thus we have a general Noether normalisation.∎

The existence of a Noether normalisation for every affine algebra $`𝒜=𝒫/`$ follows now immediately from Theorem 2.2 asserting the existence of a Pommaret basis for $``$. Comparing with the existence proof of Noether normalisations given in gp:singular , we see that the search for $`\delta `$-regular coordinates corresponds to putting the ideal $``$ into Noether position (wvv:comp, , Def. 2.22).

The converse of Corollary 7 is generally not true: even if the variables are chosen such that $`𝕜[x_1,\mathrm{},x_D]`$ defines a Noether normalisation of $`𝒜`$, this is not sufficient for concluding that the ideal $``$ possesses a Pommaret basis. As we will show now, the existence of a Pommaret basis is equivalent to a stronger property. Since under the assumptions of Proposition 11 $`𝕜[x_1,\mathrm{},x_D]`$ also defines a Noether normalisation of $`𝒫/\mathrm{lt}_{}`$, it suffices to consider monomial ideals.

###### Definition 5

A monomial ideal $`𝒫`$ is called *quasi-stable*, if it possesses a finite Pommaret basis.

The reason for this terminology will become apparent in Section 8 when we consider stable ideals. We now give several equivalent algebraic characterisations of quasi-stable ideals which are independent of the theory of Pommaret bases. They will provide us with a further criterion for $`\delta `$-regularity and also lead to a simple description of an irredundant primary decomposition of such ideals.

###### Proposition 13

Let $`𝒫`$ be a monomial ideal with $`dim𝒫/=D`$. Then the following six statements are equivalent.

$``$ is quasi-stable.

The variable $`x_1`$ is not a zero divisor for888See Section 10 for a more detailed discussion of the saturation $`^{\mathrm{sat}}`$. $`𝒫/^{\mathrm{sat}}`$ and for all $`1j<D`$ the variable $`x_{j+1}`$ is not a zero divisor for $`𝒫/,x_1,\mathrm{},x_j^{\mathrm{sat}}`$.

We have $`:x_1^{\mathrm{}}:x_2^{\mathrm{}}\mathrm{}:x_D^{\mathrm{}}`$ and for all $`D<jn`$ an exponent $`k_j1`$ exists such that $`x_j^{k_j}`$.

For all $`1jn`$ the equality $`:x_j^{\mathrm{}}=:x_j,\mathrm{},x_n^{\mathrm{}}`$ holds.

For every associated prime ideal $`𝔭\mathrm{Ass}(𝒫/)`$ an integer $`1jn`$ exists such that $`𝔭=x_j,\mathrm{},x_n`$.

If $`x^\mu `$ and $`\mu _i>0`$ for some $`1i<n`$, then for each $`0<r\mu _i`$ and $`i<jn`$ an integer $`s0`$ exists such that $`x^{\mu r_i+s_j}`$.

###### Proof

The equivalence of the statements (ii)–(v) was proven by Bermejo and Gimenez (bg:scmr, , Prop. 3.2); the equivalence of (iv) and (vi) was shown by Herzog et al. (hpv:ext, , Prop. 2.2) (alternatively the equivalence of (i) and (vi) is an easy consequence of Lemma 2). Bermejo and Gimenez bg:scmr  called ideals satisfying any of these conditions *monomial ideals of nested type*; Herzog et al. hpv:ext  spoke of *ideals of Borel type* (yet another terminology used by Caviglia and Sbarra cs:reg  is *weakly stable ideals*).999As usual, one must revert the ordering of the variables $`x_1,\mathrm{},x_n`$ in order to recover the results of the given references. Thus it suffices to show that these concepts coincide with quasi-stability by proving the equivalence of (i) and (iii).

Assume first that the ideal $``$ is quasi-stable with Pommaret basis $``$. The existence of a term $`x_j^{k_j}`$ for all $`D<jn`$ follows then immediately from Proposition 11. Now consider a term $`x^\mu :x_k^{\mathrm{}}`$ for some $`1kn`$. By definition of such a colon ideal, there exists an integer $`\mathrm{}`$ such that $`x_k^{\mathrm{}}x^\mu `$ and hence a generator $`x^\nu `$ such that $`x^\nu |_Px_k^{\mathrm{}}x^\mu `$. If $`\mathrm{cls}\nu >k`$, then $`\nu `$ would also be an involutive divisor of $`\mu `$ contradicting the assumption $`x^\mu `$. Thus we find $`\mathrm{cls}\nu k`$ and $`\nu _k>\mu _k`$.

Next we consider for arbitrary exponents $`m>0`$ the non-multiplicative products $`x_{k+1}^mx^\nu `$. For each $`m`$ a generator $`x^{\rho ^{(m)}}`$ exists which involutively divides $`x_{k+1}^mx^\nu `$. By the same reasoning as above, $`\mathrm{cls}x^{\rho ^{(m)}}>k+1`$ is not possible, as the Pommaret basis $``$ is by definition involutively autoreduced. This yields the estimate $`\mathrm{cls}\nu \mathrm{cls}x^{\rho ^{(m)}}k+1`$.

We claim now that there exists an integer $`m_0`$ such that $`\rho ^{(m)}=\rho ^{(m_0)}`$ for all $`mm_0`$ and $`\mathrm{cls}x^{\rho ^{(m_0)}}=k+1`$. Indeed, if $`\mathrm{cls}x^{\rho ^{(m)}}<k+1`$, then we must have $`\rho _{k+1}^{(m)}=v_{k+1}+m`$, since $`x_{k+1}`$ is not multiplicative for $`x^{\rho ^{(m)}}`$. Hence $`x^{\rho ^{(m)}}`$ cannot be an involutive divisor of $`x_{k+1}^{m+1}x^\nu `$ and $`\rho ^{(m+1)}\{\rho ^{(1)},\mathrm{},\rho ^{(m)}\}`$. As the Pommaret basis $``$ is a finite set, $`\mathrm{cls}x^{\rho ^{(m_0)}}=k+1`$ for some value $`m_0>0`$. But then $`x_{k+1}`$ is multiplicative for $`x^{\rho ^{(m_0)}}`$ and thus $`x^{\rho ^{(m_0)}}`$ is trivially an involutive divisor of $`x_{k+1}^mx^\nu `$ for all values $`mm_0`$.

Note that, by construction, the generator $`x^{\rho ^{(m_0)}}`$ is also an involutive divisor of $`x_{k+1}^{m_0}x^\mu `$, as $`x_k`$ is multiplicative for it. Hence this term must lie in $``$ and consequently $`x^\mu :x_{k+1}^{\mathrm{}}`$. Thus we may conclude that $`:x_k^{\mathrm{}}:x_{k+1}^{\mathrm{}}`$ for all $`1k<n`$. This proves (iii).

For the converse assume that (iii) holds and let $``$ be the minimal basis of the ideal $``$. Let $`x^\mu `$ be an arbitrary term of class $`k`$. Then $`x^\mu /x_k:x_k^{\mathrm{}}`$. By assumption, this means that also $`x^\mu /x_k:x_{\mathrm{}}^{\mathrm{}}`$ for any non-multiplicative index $`\mathrm{}`$. Hence for each term $`x^\mu `$ and for each value $`\mathrm{cls}(x^\mu )<\mathrm{}n`$ there exists an integer $`q_{\mu ,\mathrm{}}`$ such that $`x_{\mathrm{}}^{q_{\mu ,\mathrm{}}}x^\mu /x_k`$ but $`x_{\mathrm{}}^{q_{\mu ,\mathrm{}}+1}x^\mu /x_k`$. For the values $`1\mathrm{}\mathrm{cls}x^\mu `$ we set $`q_{\mu ,\mathrm{}}=0`$. Observe that if $`x^\nu `$ is a minimal generator dividing $`x_{\mathrm{}}^{q_{\mu ,\mathrm{}}+1}x^\mu /x_k`$, then we find for the inverse lexicographic order that $`x^\nu _{\mathrm{invlex}}x^\mu `$, since $`\mathrm{cls}(x^\nu )\mathrm{cls}(x^\mu )`$ and $`\nu _k<\mu _k`$.

Consider now the set

$$=\{x^{\mu +\rho }x^\mu 1\mathrm{}n:0\rho _{\mathrm{}}q_{\mu ,\mathrm{}}\}.$$
(18)
We claim that $``$ is a weak involutive completion of $``$ and thus a weak Pommaret basis of $``$. In order to prove this assertion, we must show that each term $`x^\lambda `$ lies in the involutive cone of a member of $``$.

As $`x^\lambda `$ is assumed to be an element of $``$, we can factor it as $`x^\lambda =x^{\sigma ^{(1)}}x^{\rho ^{(1)}}x^{\mu ^{(1)}}`$ where $`x^{\mu ^{(1)}}`$ is a minimal generator, $`x^{\sigma ^{(1)}}`$ contains only multiplicative variables for $`x^{\mu ^{(1)}}`$ and $`x^{\rho ^{(1)}}`$ only non-multiplicative ones. If $`x^{\mu ^{(1)}+\rho ^{(1)}}`$, then we are done, as obviously $`\mathrm{cls}\left(x^{\mu ^{(1)}+\rho ^{(1)}}\right)=\mathrm{cls}\left(x^{\mu ^{(1)}}\right)`$ and hence all variables contained in $`x^{\sigma ^{(1)}}`$ are multiplicative for $`x^{\mu ^{(1)}+\rho ^{(1)}}`$, too.

Otherwise there exists at least one non-multiplicative variables $`x_{\mathrm{}}`$ such that $`\rho _{\mathrm{}}^{(1)}>q_{\mu ^{(1)},\mathrm{}}`$. Any minimal generator $`x^{\mu ^{(2)}}`$ dividing $`x_{\mathrm{}}^{q_{\mu ^{(1)},\mathrm{}}+1}x^{\mu ^{(1)}}/x_k`$ is also a divisor of $`x^\lambda `$ and we find a second factorisation $`x^\lambda =x^{\sigma ^{(2)}}x^{\rho ^{(2)}}x^{\mu ^{(2)}}`$ where again $`x^{\sigma ^{(2)}}`$ consists only of multiplicative and $`x^{\rho ^{(2)}}`$ only of non-multiplicative variables for $`x^{\mu ^{(2)}}`$. If $`x^{\mu ^{(2)}+\rho ^{(2)}}`$, then we are done by the same argument as above; otherwise we iterate.

According to the observation made above, the sequence $`(x^{\mu ^{(1)}},x^{\mu ^{(2)}},\mathrm{})`$ of minimal generators constructed this way is strictly descending with respect to the inverse lexicographic order. However, the minimal basis $``$ is a finite set and thus the iteration cannot go on infinitely. As the iteration only stops, if there exists an involutive cone containing $`x^\lambda `$, the involutive span of $``$ is indeed $``$ and thus the ideal $``$ quasi-stable.∎

###### Remark 6

Note that our considerations about standard pairs and the induced primary decomposition in the last section imply a simple direct proof of the implication “(i)$``$(v)” in Proposition 13. If the ideal $``$ is quasi-stable, then $``$ admits a complementary Rees decomposition according to Proposition 8. Together with Propositions 9, 10 and Remark 5, this observation trivially implies that all associated prime ideals are of the form $`𝔭=x_j,\mathrm{},x_n`$. $``$

###### Lemma 3

Let $`_1,_2𝒫`$ be two quasi-stable ideals. Then the sum $`_1+_2`$, the product $`_1_2`$ and the intersection $`_1_2`$ are quasi-stable, too. If $`𝒫`$ is a quasi-stable ideal, then the quotient $`:𝒥`$ is again quasi-stable for arbitrary monomial ideals $`𝒥𝒫`$.

###### Proof

For the sum $`_1+_2`$ the claim follows immediately from Remark 2.9 of Part I which states that the union $`_1_2`$ of (weak) Pommaret bases $`_k`$ of $`_k`$ is a weak Pommaret basis of the sum $`_1+_2`$. Similarly, the case of both the product $`_1_2`$ and the intersection $`_1_2`$ was settled in Remark 6.5 of Part I where for both ideals weak Pommaret bases were constructed.

For the last assertion we use Part (vi) of Proposition 13. If $`𝒥`$ is minimally generated by the monomials $`m_1,\mathrm{},m_r`$, then $`:𝒥=_{k=1}^r:m_k`$ and thus it suffice to consider the case that $`𝒥`$ is a principal ideal with generator $`x^\nu `$. Assume that $`x^\mu :x^\nu `$ and that $`\mu _i>0`$. Since $`x^{\mu +\nu }`$ lies in the quasi-stable ideal $``$, we find for each $`0<r\mu _i`$ and $`i<jn`$ and integer $`s0`$ exists such that $`x^{\mu +\nu r_i+s_j}`$. As $`r\mu _i`$, this trivially implies that $`x^{\mu r_i+s_j}:x^\nu `$.∎

###### Remark 7

Alternative proofs for Lemma 3 were given by Cimpoeaş mc:borel . There it was also noted that its final statement trivially implies Part (v) of Proposition 13, as any associated prime ideal $`𝔭`$ of a quasi-stable ideal $``$ is of the form $`𝔭=:x^\nu `$ for some monomial $`x^\nu `$ and thus is also quasi-stable. But the only quasi-stable prime ideals are obviously the ideals $`x_j,\mathrm{},x_n`$.

Above we actually proved that Part (iii) of Proposition 13 may be replaced by the equivalent statement $`:x_1^{\mathrm{}}:x_2^{\mathrm{}}\mathrm{}:x_n^{\mathrm{}}`$ which does not require a priori knowledge of $`D`$ (the dimension $`D`$ arises then trivially as the smallest value $`k`$ such that $`:x_k^{\mathrm{}}=𝒫`$, i., e, for which $``$ contains a minimal generator $`x_k^{\mathrm{}}`$ for some exponent $`\mathrm{}>0`$). In this formulation it is straightforward to verify (iii) effectively: bases of the colon ideals $`:x_k^{\mathrm{}}`$ are easily obtained by setting $`x_k=1`$ in any basis of $``$ and for monomial ideals it is trivial to check inclusion, as one must only compare their minimal bases.

We furthermore note that if we have for some value $`1kn`$ an ascending chain $`:x_1^{\mathrm{}}:x_2^{\mathrm{}}\mathrm{}:x_k^{\mathrm{}}`$, then for each $`1jk`$ the minimal basis $`_j`$ of $`:x_j^{\mathrm{}}`$ lies in $`𝕜[x_{j+1},\mathrm{},x_n]`$. Indeed, no element of $`_j`$ can depend on $`x_j`$. Now assume that $`x^\nu _j`$ satisfies $`\mathrm{cls}\nu =\mathrm{}<j`$. Then $`x_j^mx^\nu `$ is a minimal generator of $``$ for some suitable exponent $`m_0`$. This in turn implies that $`x_j^mx^\nu /x_{\mathrm{}}^\nu _{\mathrm{}}:x_{\mathrm{}}^{\mathrm{}}:x_j^{\mathrm{}}`$ and hence $`x^\nu /x_{\mathrm{}}^\nu _{\mathrm{}}:x_j^{\mathrm{}}`$ which contradicts our assumption that $`x^\nu `$ was a minimal generator. $``$

Proposition 13 provides us with a simple criterion for $`\delta `$-regularity. Actually, this new criterion is closely related to our previous one based on a comparison of the Janet and Pommaret multiplicative variables, as the proof of the following converse to Theorem 2.1 demonstrates.

###### Proposition 14

Let $`𝒫`$ be a monomial ideal and $``$ a finite, Pommaret autoreduced monomial basis of it. If the ideal $``$ is not quasi-stable, then $`||_J>||_P`$, i. e. for at least one generator in the basis $``$ a variable exists which is Janet but not Pommaret multiplicative.

###### Proof

By Proposition 3 we have $`||_J||_P`$. As $``$ is not quasi-stable, there exists a minimal value $`k`$ such that $`:x_k^{\mathrm{}}:x_{k+1}^{\mathrm{}}`$. Let $`x^\mu `$ be a minimal generator of $`:x_k^{\mathrm{}}`$ which is not contained in $`:x_{k+1}^{\mathrm{}}`$. Then for a suitable exponent $`m_0`$ the term $`x^{\overline{\mu }}=x_k^mx^\mu `$ is a minimal generator of $``$ and hence contained in $``$.

We claim now that $``$ contains a generator for which $`x_{k+1}`$ is Janet but not Pommaret multiplicative. If $`x_{k+1}X_{J,}(x^{\overline{\mu }})`$, then we are done, as according to Remark 7 $`\mathrm{cls}\overline{\mu }=k`$ and hence $`x_{k+1}X_P(x^{\overline{\mu }})`$. Otherwise $``$ contains a term $`x^\nu `$ such that $`\nu _{\mathrm{}}=\mu _{\mathrm{}}`$ for $`k+1<\mathrm{}n`$ and $`\nu _{k+1}>\mu _{k+1}`$. If several generators with this property exist in $``$, we choose one for which $`\nu _{k+1}`$ takes a maximal value so that we have $`x_{k+1}X_{J,}(x^\nu )`$ by definition of the Janet division. If $`\mathrm{cls}\nu <k+1`$, we are again done, as then $`x_{k+1}X_P(x^\nu )`$. Now assume that $`\mathrm{cls}\nu =k+1`$ and consider the term $`x^\rho =x^\nu /x_{k+1}^{\nu _{k+1}}`$. Obviously, $`x^\rho :x_{k+1}^{\mathrm{}}`$ contradicting our assumption $`x^\mu :x_{k+1}^{\mathrm{}}`$ since $`x^\rho x^\mu `$. Hence this case cannot arise.∎

Proposition 13 (v) furthermore allows us to formulate for monomial ideals a converse to Corollary 7. It is equivalent to (bg:scmr, , Prop. 3.6) and shows that a Pommaret basis of a monomial ideal $``$ induces *simultaneous* Noether normalisations of all primary components of the ideal.

###### Corollary 8

Let $`𝒫`$ be a monomial ideal with $`dim𝒫/=D`$. Furthermore, let $`=𝔮_1\mathrm{}𝔮_r`$ be an irredundant monomial primary decomposition with $`D_j=dim𝒫/𝔮_j`$ for $`1jr`$. The ideal $``$ is quasi-stable, if and only if $`𝕜[x_1,\mathrm{},x_D]`$ defines a Noether normalisation of $`𝒫/`$ and $`𝕜[x_1,\mathrm{},x_{D_j}]`$ one of $`𝒫/𝔮_j`$ for each primary component $`𝔮_j`$.

###### Proof

By assumption, each $`𝔮_j`$ is a monomial primary ideal. This implies that $`𝕜[x_1,\mathrm{},x_{D_j}]`$ defines a Noether normalisation of $`𝒫/𝔮_j`$, if and only if the associated prime ideal is $`\sqrt{𝔮_j}=x_{D_j+1},\mathrm{},x_n`$. Now the assertion follows immediately from Proposition 13 (v).∎

We may also exploit Proposition 13 for actually deriving an irredundant primary decomposition $`=𝔮_1\mathrm{}𝔮_t`$ with monomial ideals $`𝔮_j`$ for an arbitrary quasi-stable ideal $``$.101010The following construction is joint work with M. Hausdorf and M. Sahbi and has already appeared in wms:delta . Bermejo and Gimenez (bg:scmr, , Rem. 3.3) noted that their proof of the implication “(v)$``$(iv)” in Proposition 13 has some simple consequences for the primary ideals $`𝔮_j`$. Let again $`D=dim𝒫/`$. Then $`𝔭=x_{D+1},\mathrm{},x_n`$ is the unique minimal prime ideal associated to $``$ and the corresponding unique primary component is given by $`:x_D^{\mathrm{}}`$ (if $`D=0`$, then obviously $``$ is already a primary ideal). More generally, we find for any $`1kD`$ that

$$:x_k^{\mathrm{}}=\underset{𝔭_jx_{k+1},\mathrm{},x_n}{}𝔮_j$$
(19)
where $`𝔭_j=\sqrt{𝔮_j}`$ is the corresponding associated prime ideal. Based on these observations, an irredundant primary decomposition can be constructed by working backwards through the sequence $`:x_1^{\mathrm{}}:x_2^{\mathrm{}}\mathrm{}:x_n^{\mathrm{}}`$.

Let $`d=\mathrm{depth}𝒫/`$, i. e. $`d+1`$ is the minimal class of a generator in the Pommaret basis $``$ of $``$ according to Proposition 12.111111Note that for determining the depth $`d`$ in the case of a quasi-stable ideal, it is not necessary to compute the Pommaret basis: since multiplication with a non-multiplicative variable never decreases the class, $`d+1`$ is also the minimal class of a minimal generator. For $`1kD`$ we set $`s_k=\mathrm{min}\{s:x_k^s=:x_k^{s+1}\}`$, i. e. $`s_k`$ is the highest $`x_k`$-degree of a minimal generator of $``$. Then we introduce the ideals $`𝒥_k=+x_{k+1}^{s_{k+1}},\mathrm{},x_D^{s_D}`$ and

$$𝔮_k=𝒥_k:x_k^{\mathrm{}}=:x_k^{\mathrm{}}+x_{k+1}^{s_{k+1}},\mathrm{},x_D^{s_D}.$$
(20)
It is easy to see that all the ideals $`𝒥_k`$ are again quasi-stable provided the ideal $``$ is quasi-stable (this follows immediately from Proposition 13 and the fact that in this case $`(:x_i^{\mathrm{}}):x_j^{\mathrm{}}=:x_j^{\mathrm{}}`$ for $`i<j`$). For notational simplicity we formally define $`:x_0^{\mathrm{}}=`$ and $`𝔮_0=𝒥_0=+x_1^{s_1},\mathrm{},x_D^{s_D}`$. Since obviously $`dim𝒫/𝒥_k=k`$ for $`0kD`$, it follows from the considerations above that $`𝔮_k`$ is an $`x_{k+1},\mathrm{},x_n`$-primary ideal.

###### Proposition 15

Let $`𝒫`$ be a quasi-stable ideal. Then $`=_{k=d}^D𝔮_k`$ is a primary decomposition. Eliminating all ideals $`𝔮_k`$ where $`:x_k^{\mathrm{}}=:x_{k+1}^{\mathrm{}}`$ makes it an irredundant decomposition.

###### Proof

We first show that the equality $`:x_k^{\mathrm{}}=_{\mathrm{}=k}^D𝔮_{\mathrm{}}`$ holds or equivalently that $`:x_k^{\mathrm{}}=𝔮_k(:x_{k+1}^{\mathrm{}})`$ for $`0kn`$; for $`k=d`$ this represents the first statement of the proposition, since obviously $`:x_0^{\mathrm{}}=\mathrm{}=:x_d^{\mathrm{}}=`$. By definition of the value $`s_{k+1}`$, we have that (gp:singular, , Lemma 3.3.6)

$$:x_k^{\mathrm{}}=(:x_k^{\mathrm{}}+x_{k+1}^{s_{k+1}})((:x_k^{\mathrm{}}):x_{k+1}^{\mathrm{}}).$$
(21)
The second factor obviously equals $`:x_{k+1}^{\mathrm{}}`$. To the first one we apply the same construction and decompose

$$\begin{array}{cc}\hfill :x_k^{\mathrm{}}& +x_{k+1}^{s_{k+1}}=\hfill \\ & =(:x_k^{\mathrm{}}+x_{k+1}^{s_{k+1}},x_{k+2}^{s_{k+2}})((:x_k^{\mathrm{}}+x_{k+1}^{s_{k+1}}):x_{k+2}^{\mathrm{}})\hfill \\ & =(:x_k^{\mathrm{}}+x_{k+1}^{s_{k+1}},x_{k+2}^{s_{k+2}})(:x_{k+2}^{\mathrm{}}+x_{k+1}^{s_{k+1}}).\hfill \end{array}$$
(22)
Continuing in this manner, we arrive at a decomposition

$$:x_k^{\mathrm{}}=𝔮_k\mathrm{}(:x_{k+1}^{\mathrm{}})$$
(23)
where the dots represent factors of the form $`:x_{\mathrm{}}^{\mathrm{}}+x_{k+1}^{s_{k+1}},\mathrm{},x_\mathrm{}1^{s_\mathrm{}1}`$ with $`\mathrm{}k+2`$. Since we assume that $``$ is quasi-stable, $`:x_{k+1}^{\mathrm{}}`$ is contained in each of these factors and we may omit them which proves our claim.

In the thus obtained primary decomposition of $``$ the radicals of all appearing primary ideals are pairwise different. Furthermore, it is obvious that $`𝔮_k`$ is redundant whenever $`:x_k^{\mathrm{}}=:x_{k+1}^{\mathrm{}}`$. Thus there only remains to prove that all the other primary ideals $`𝔮_k`$ are indeed necessary. Assume that $`:x_k^{\mathrm{}}:x_{k+1}^{\mathrm{}}`$ (which is in particular the case for $`k<d`$). Then there exists a minimal generator $`x^\mu `$ of $`:x_{k+1}^{\mathrm{}}`$ which is not contained in $`:x_k^{\mathrm{}}`$. Consider the monomial $`x_k^{s_k}x^\mu `$. It cannot lie in $`:x_k^{\mathrm{}}`$, as otherwise already $`x^\mu :x_k^{\mathrm{}}`$, and thus it also cannot be contained in $`𝔮_k`$ (since we showed above that $`:x_k^{\mathrm{}}=𝔮_k(:x_{k+1}^{\mathrm{}})`$). On the other hand we find that $`x_k^{s_k}x^\mu 𝔮_{\mathrm{}}`$ for all $`\mathrm{}>k`$ since then $`:x_{k+1}^{\mathrm{}}𝔮_{\mathrm{}}`$ and for all $`\mathrm{}<k`$ since then $`x_k^{s_k}𝔮_{\mathrm{}}`$. Hence $`𝔮_k`$ is not redundant.∎

According to Lemma 3, the quotient ideals $`:x_k^{\mathrm{}}`$ are again quasi-stable. It is straightforward to obtain Pommaret bases for them. We disjointly decompose the monomial Pommaret basis $`=_1\mathrm{}_n`$ where $`_k`$ contains all generators of class $`k`$. Furthermore, we write $`_k^{}`$ for the set obtained by setting $`x_k=1`$ in each generator in $`_k`$.

###### Lemma 4

For any $`1kn`$ the set $`^{}=_k^{}_{\mathrm{}=k+1}^n_{\mathrm{}}`$ is a weak Pommaret basis of the colon ideal $`:x_k^{\mathrm{}}`$.

###### Proof

We first show that $`^{}`$ is an involutive set. By definition of the Pommaret division, it is obvious that the subset $`_{\mathrm{}=k+1}^n_{\mathrm{}}`$ is involutive. Thus there only remains to consider the non-multiplicative products of the members of $`_k^{}`$. Take $`x^\mu _k^{}`$ and let $`x_{\mathrm{}}`$ be a non-multiplicative variable for it. Obviously, there exists an $`m>0`$ such that $`x_k^mx^\mu _k`$ and hence a generator $`x^\nu _{\mathrm{}=k}^n_{\mathrm{}}`$ such that $`x_{\mathrm{}}x_k^mx^\mu `$ lies in the involutive cone $`𝒞_P(x^\nu )`$. Writing $`x_{\mathrm{}}x_k^mx^\mu =x^{\rho +\nu }`$, we distinguish two cases. If $`\mathrm{cls}\nu >k`$, then $`\rho _k=m`$ and we can divide by $`x_k^m`$ in order to obtain an involutive standard representation of $`x_{\mathrm{}}x^\mu `$ with respect to $`^{}`$. If $`\mathrm{cls}\nu =k`$, then the multi index $`\rho `$ is of the form $`r_k`$, i. e. only the $`k`$th entry is different from zero, and we even find that $`x_{\mathrm{}}x^\mu =x^\nu /x_k^r_k^{}`$.

Thus there only remains to prove that $`^{}`$ is actually a generating set for $`:x_k^{\mathrm{}}`$. For this we first note that the Pommaret basis of a quasi-stable ideal contains a generator of class $`k`$ only, if there is a minimal generator of class $`k`$, as applying the monomial completion Algorithm 2 of Part I to the minimal basis adds only non-multiplicative multiples of the minimal generators (and these are trivially of the same class). By Remark 6, all minimal generators of $`:x_k^{\mathrm{}}`$ have at least class $`k+1`$. Thus setting $`x_k=1`$ in any member of $`_{\mathrm{}=1}^{k1}_{\mathrm{}}`$ can never produce a minimal generator of $`:x_k^{\mathrm{}}`$ and thus $`^{}`$ is a weak involutive completion of the minimal basis of $`:x_k^{\mathrm{}}`$. According to Proposition 2.8 of Part I, an involutive autoreduction yields a strong basis.∎

The ideals $`x_{k+1}^{s_{k+1}},\mathrm{},x_D^{s_D}`$ are obviously irreducible and for $`kd`$ exactly of the form that they possess a Pommaret basis as discussed in Example 2.12 of Part I. There we also gave an explicit Pommaret basis for such an ideal. Since according to Remark 2.9 of Part I the union of two (weak) Pommaret bases of two monomial ideals $`_1`$, $`_2`$ yields a weak Pommaret basis of $`_1+_2`$, we obtain this way easily weak Pommaret bases for all primary ideals $`𝔮_k`$ appearing in the irredundant decomposition of Proposition 15.

Thus the crucial information for obtaining an irredundant primary decomposition of a quasi-stable ideal $``$ is where “jumps” are located, i. e. where $`:x_k^{\mathrm{}}:x_{k+1}^{\mathrm{}}`$. Since these ideals are quasi-stable, the positions of the jumps are determined by their depths. A chain with all the jumps is obtained by the following simple recipe: set $`_0=`$ and define $`_{k+1}=_k:x_{d_k}^{\mathrm{}}`$ where $`d_k=\mathrm{depth}_k`$. This leads to the so-called *sequential chain* of $``$:

$$_0=_1\mathrm{}_r=𝒫;.$$
(24)
###### Remark 8

With the help of the sequential chain (24) one can also show straightforwardly that any quasi-stable ideal is *sequentially Cohen-Macaulay* (hpv:ext, , Cor. 2.5) (recall that the algebra $`𝒜=𝒫/`$ is sequentially Cohen-Macaulay rps:cca , if a chain $`_0=_1\mathrm{}_r=𝒫`$ exists such that all quotients $`_{k+1}/_k`$ are Cohen-Macaulay and their dimensions are ascending: $`dim(_k/_{k1})<dim(_{k+1}/_k)`$).

Indeed, consider the ideal $`𝒥_k=_k𝕜[x_{d_k},\mathrm{},x_n]`$. By Remark 7, the minimal generators of $`𝒥_k`$ are the same as the minimal ones of $`_k`$; furthermore, by Proposition 13(iv) $`𝒥_k^{\mathrm{sat}}=𝒥_k:x_{d_k}^{\mathrm{}}`$. Hence we find that $`_{k+1}=𝒥_k^{\mathrm{sat}}_𝒫`$ and

$$_{k+1}/_k(𝒥_k^{\mathrm{sat}}/𝒥_k)[x_1,\mathrm{},x_{d_k1}].$$
(25)
Since the factor ring $`𝒥_k^{\mathrm{sat}}/𝒥_k`$ is trivially finite (as a $`𝕜`$-linear space), the quotient $`_{k+1}/_k`$ is thus a $`(d_k1)`$-dimensional Cohen-Macaulay module. $``$

## 5 Syzygies for Involutive Bases

Gröbner bases are a very useful tool in syzygy theory. A central result is *Schreyer’s Theorem* al:gb ; fos:syz  that the standard representations of the $`S`$-polynomials between the elements of a Gröbner basis determine directly a Gröbner basis of the first syzygy module with respect to an appropriately chosen term order. Now we study the use of involutive bases in this context.

In Part I we introduced involutive bases only for ideals, but the extension to submodules of free modules $`𝒫^m`$ is trivial. We represent elements of $`𝒫^m`$ as vectors $`\stackrel{}{f}=(f_1,\mathrm{},f_m)`$ with $`f_\alpha 𝒫`$. The standard basis of $`𝒫^m`$ consists of the unit vectors $`\stackrel{}{e}_\alpha `$ with $`e_{\alpha \beta }=\delta _{\alpha \beta }`$ and $`1\alpha m`$; thus $`\stackrel{}{f}=f_1\stackrel{}{e}_1+\mathrm{}+f_m\stackrel{}{e}_m`$. Now a term $`\stackrel{}{t}`$ is a vector of the form $`\stackrel{}{t}=t\stackrel{}{e}_\alpha `$ for some $`\alpha `$ and with $`t𝕋`$ a term in $`𝒫`$. We denote the set of all terms by $`𝕋^m`$; it is a monoid module over $`𝕋`$.

Let $`𝒫^m`$ be a finite set, $``$ a term order on $`𝕋^m`$ and $`L`$ an involutive division on $`_0^n`$. We divide $``$ into $`m`$ disjoint sets $`_\alpha =\{\stackrel{}{h}\mathrm{lt}_{}\stackrel{}{h}=t\stackrel{}{e}_\alpha ,t𝕋\}`$. This leads naturally to $`m`$ sets $`𝒩_\alpha =\{\mu _0^nx^\mu \stackrel{}{e}_\alpha \mathrm{lt}_{}_\alpha \}`$. If $`\stackrel{}{h}_\alpha `$, we assign the multiplicative variables $`X_{L,,}(\stackrel{}{h})=\{x_iiN_{L,𝒩_\alpha }(\mathrm{le}_{}\stackrel{}{h})\}`$. The involutive span $`_{L,}`$ is defined by an obvious generalisation of the old definition in Part I.

Let $`=\{\stackrel{}{h}_1,\mathrm{},\stackrel{}{h}_s\}`$ be an involutive basis of the submodule $`𝒫^m`$. Take an arbitrary element $`\stackrel{}{h}_\alpha `$ and choose an arbitrary non-multiplicative variable $`x_k\overline{X}_{L,,}(\stackrel{}{h}_\alpha )`$ of it. By the results of Part I, we can determine for each generator $`\stackrel{}{h}_\beta `$ with an involutive normal form algorithm a unique polynomial $`P_\beta ^{(\alpha ;k)}𝕜[X_{L,,}(\stackrel{}{h}_\beta )]`$ such that $`x_k\stackrel{}{h}_\alpha =_{\beta =1}^sP_\beta ^{(\alpha ;k)}\stackrel{}{h}_\beta `$. To this relation corresponds the syzygy

$$\stackrel{}{S}_{\alpha ;k}=x_k\stackrel{}{e}_\alpha \underset{\beta =1}{\overset{s}{}}P_\beta ^{(\alpha ;k)}\stackrel{}{e}_\beta 𝒫^s.$$
(26)
We denote the set of all thus obtained syzygies by

$$_{\mathrm{Syz}}=\{\stackrel{}{S}_{\alpha ;k}1\alpha s;x_k\overline{X}_{L,,}(\stackrel{}{h}_\alpha )\}.$$
(27)
###### Lemma 5

Let $``$ be an involutive basis for the involutive division $`L`$ and the term order $``$. If $`\stackrel{}{S}=_{\beta =1}^sS_\beta \stackrel{}{e}_\beta `$ is an arbitrary syzygy in the module $`\mathrm{Syz}()`$ with $`S_\beta 𝕜[X_{L,,}(\stackrel{}{h}_\beta )]`$ for all $`1\beta s`$, then $`\stackrel{}{S}=0`$.

###### Proof

By definition of a syzygy, $`_{\beta =1}^sS_\beta \stackrel{}{h}_\beta =0`$. As the involutive basis $``$ is involutively head autoreduced, each element $`\stackrel{}{f}`$ possesses a unique involutive normal form. In particular, this holds for $`0`$. Thus either $`\stackrel{}{S}=0`$ or $`S_\beta 𝕜[X_{L,,}(\stackrel{}{h}_\beta )]`$ for at least one $`\beta `$.∎

A fundamental ingredient of Schreyer’s Theorem is the term order $`_{}`$ on $`𝕋^s`$ induced by an arbitrary finite set $`=\{\stackrel{}{f}_1,\mathrm{},\stackrel{}{f}_s\}𝒫^m`$ and an arbitrary term order $``$ on $`𝕋^m`$: given two terms $`\stackrel{}{s}=s\stackrel{}{e}_\sigma `$ and $`\stackrel{}{t}=t\stackrel{}{e}_\tau `$, we set $`\stackrel{}{s}_{}\stackrel{}{t}`$, if either $`\mathrm{lt}_{}(s\stackrel{}{f}_\sigma )\mathrm{lt}_{}(t\stackrel{}{f}_\tau )`$ or $`\mathrm{lt}_{}(s\stackrel{}{f}_\sigma )=\mathrm{lt}_{}(t\stackrel{}{f}_\tau )`$ and $`\tau <\sigma `$.

###### Corollary 9

If $`𝒫`$ is an involutive basis, then the set $`_{\mathrm{Syz}}`$ generates the syzygy module $`\mathrm{Syz}()`$.

###### Proof

Let $`\stackrel{}{S}=_{\beta =1}^sS_\beta \stackrel{}{e}_\beta `$ by an arbitrary non-vanishing syzygy in $`\mathrm{Syz}()`$. By Lemma 5, at least one of the coefficients $`S_\beta `$ must contain a term $`x^\mu `$ with a non-multiplicative variable $`x_j\overline{X}_{L,,}(\stackrel{}{h}_\beta )`$. Let $`cx^\mu \stackrel{}{e}_\beta `$ be the maximal such term with respect to the term order $`_{}`$ and $`j`$ the maximal non-multiplicative index with $`\mu _j>0`$. Then we eliminate this term by computing $`\stackrel{}{S}^{}=\stackrel{}{S}cx^{\mu 1_j}\stackrel{}{S}_{\beta ;j}`$. If $`\stackrel{}{S}^{}0`$, we iterate. Since all new terms introduced by the subtraction are smaller than the eliminated term with respect to $`_{}`$, we must reach zero after a finite number of steps. Thus this computation leads to a representation of $`\stackrel{}{S}`$ as a linear combination of elements of $`_{\mathrm{Syz}}`$.∎

Let $`=\{\stackrel{}{h}_1,\mathrm{},\stackrel{}{h}_s\}`$ be an involutive basis and thus a Gröbner basis for the term order $``$. Without loss of generality we may assume that $``$ is a monic basis. Set $`\stackrel{}{t}_\alpha =\mathrm{lt}_{}\stackrel{}{h}_\alpha `$ and $`\stackrel{}{t}_{\alpha \beta }=\mathrm{lcm}(\stackrel{}{t}_\alpha ,\stackrel{}{t}_\beta )`$. We have for every $`S`$-polynomial a standard representation $`\stackrel{}{S}_{}(\stackrel{}{h}_\alpha ,\stackrel{}{h}_\beta )=_{\gamma =1}^sf_{\alpha \beta \gamma }\stackrel{}{h}_\gamma `$ where the polynomials $`f_{\alpha \beta \gamma }𝒫`$ satisfy $`\mathrm{lt}_{}\left(\stackrel{}{S}_{}(\stackrel{}{h}_\alpha ,\stackrel{}{h}_\beta )\right)\mathrm{lt}_{}(f_{\alpha \beta \gamma }\stackrel{}{h}_\gamma )`$ for $`1\gamma s`$. Setting $`\stackrel{}{f}_{\alpha \beta }=_{\gamma =1}^sf_{\alpha \beta \gamma }\stackrel{}{e}_\gamma `$, we introduce for $`\alpha \beta `$ the syzygy

$$\stackrel{}{S}_{\alpha \beta }=\frac{\stackrel{}{t}_{\alpha \beta }}{\stackrel{}{t}_\alpha }\stackrel{}{e}_\alpha \frac{\stackrel{}{t}_{\alpha \beta }}{\stackrel{}{t}_\beta }\stackrel{}{e}_\beta \stackrel{}{f}_{\alpha \beta }.$$
(28)
Schreyer’s Theorem asserts that the set $`_{\mathrm{Schreyer}}=\{\stackrel{}{S}_{\alpha \beta }1\alpha <\beta s\}`$ of all these syzygies is a Gröbner basis of the first syzygy module $`\mathrm{Syz}()`$ for the induced term order $`_{}`$.

We denote by $`\stackrel{~}{\stackrel{}{S}}_{\alpha \beta }=\frac{\stackrel{}{t}_{\alpha \beta }}{\stackrel{}{t}_\alpha }\stackrel{}{e}_\alpha \frac{\stackrel{}{t}_{\alpha \beta }}{\stackrel{}{t}_\beta }\stackrel{}{e}_\beta `$ the syzygy of the leading terms corresponding to $`\stackrel{}{S}_{\alpha \beta }`$ and if $`𝒮_{\mathrm{Schreyer}}`$ is a set of syzygies, $`\stackrel{~}{𝒮}`$ contains the corresponding syzygies of the leading terms.

###### Lemma 6

Let $`𝒮_{\mathrm{Schreyer}}`$ be such that $`\stackrel{~}{𝒮}`$ generates $`\mathrm{Syz}(\mathrm{lt}_{})`$. Then $`𝒮`$ generates $`\mathrm{Syz}()`$. Assume furthermore that the three pairwise distinct indices $`\alpha `$, $`\beta `$, $`\gamma `$ are such that121212If $`\alpha >\beta `$, then we understand that $`\stackrel{}{S}_{\beta \alpha }𝒮`$ etc. $`\stackrel{}{S}_{\alpha \beta },\stackrel{}{S}_{\beta \gamma },\stackrel{}{S}_{\alpha \gamma }𝒮`$ and $`\stackrel{}{t}_\gamma \stackrel{}{t}_{\alpha \beta }`$. Then the smaller set $`𝒮\{\stackrel{}{S}_{\alpha \beta }\}`$ still generates $`\mathrm{Syz}()`$.

###### Proof

It is a classical result in the theory of Gröbner bases that $`\stackrel{~}{𝒮}\{\stackrel{~}{\stackrel{}{S}}_{\alpha \beta }\}`$ still generates $`\mathrm{Syz}(\mathrm{lt}_{})`$. In fact, this is the basic property underlying Buchberger’s second criterion for avoiding redundant $`S`$-polynomials. Thus it suffices to show the first assertion; the second one is a simple corollary.

Let $`\stackrel{}{R}=_{\alpha =1}^sR_\alpha \stackrel{}{e}_\alpha \mathrm{Syz}()`$ be an arbitrary syzygy of the full generators and set $`\stackrel{}{t}_\stackrel{}{R}=\mathrm{max}_{}\left\{\mathrm{lt}_{}(R_\alpha \stackrel{}{h}_\alpha )1\alpha s\right\}`$. Then

$$\stackrel{~}{\stackrel{}{R}}=\underset{\mathrm{lt}_{}(R_\alpha \stackrel{}{h}_\alpha )=\stackrel{}{t}_R}{}\mathrm{lt}_{}(R_\alpha \stackrel{}{h}_\alpha )\mathrm{Syz}(\mathrm{lt}_{}).$$
(29)
According to our assumption $`\stackrel{~}{𝒮}`$ is a generating set of $`\mathrm{Syz}(\mathrm{lt}_{})`$, so that we may write $`\stackrel{~}{\stackrel{}{R}}=_{\stackrel{~}{\stackrel{}{S}}\stackrel{~}{𝒮}}a_{\stackrel{~}{\stackrel{}{S}}}\stackrel{~}{\stackrel{}{S}}`$ for some coefficients $`a_{\stackrel{~}{\stackrel{}{S}}}𝒫`$. Let us now consider the syzygy $`\stackrel{}{R}^{}=\stackrel{}{R}_{\stackrel{}{S}𝒮}a_{\stackrel{~}{\stackrel{}{S}}}\stackrel{}{S}`$. Obviously, $`\stackrel{}{t}_\stackrel{}{R}^{}\stackrel{}{t}_\stackrel{}{R}`$. By iteration we obtain thus in a finite number of steps a representation $`\stackrel{}{R}=_{\stackrel{}{S}𝒮}b_\stackrel{}{S}\stackrel{}{S}`$ and thus $`𝒮`$ generates the module $`\mathrm{Syz}()`$.∎

As a consequence of this simple lemma, we can now show that each involutive basis yields immediately a Gröbner basis of the first syzygy module. In fact, this basis is automatically computed during the determination of the involutive basis with the completion Algorithm 3 of Part I. This is completely analogously to the automatic determination of $`_{\mathrm{Schreyer}}`$ with the Buchberger algorithm.

###### Theorem 5.1

Let $``$ be an involutive basis for the involutive division $`L`$ and the term order $``$. Then the set $`_{\mathrm{Syz}}`$ is a Gröbner basis of the syzygy module $`\mathrm{Syz}()`$ for the term order $`_{}`$.

###### Proof

Without loss of generality, we may assume that $``$ is a monic basis, i. e. all leading coefficients are $`1`$. Let $`\stackrel{}{S}_{\alpha ;k}_{\mathrm{Syz}}`$. As $``$ is an involutive basis, the unique polynomials $`P_\beta ^{(\alpha ;k)}`$ in (26) satisfy $`\mathrm{lt}_{}(P_\beta ^{(\alpha ;k)}\stackrel{}{h}_\beta )\mathrm{lt}_{}(x_k\stackrel{}{h}_\alpha )`$ and there exists only one index $`\overline{\beta }`$ such that $`\mathrm{lt}_{}(P_{\overline{\beta }}^{(\alpha ;k)}\stackrel{}{h}_{\overline{\beta }})=\mathrm{lt}_{}(x_k\stackrel{}{h}_\alpha )`$. It is easy to see that we have $`\stackrel{}{S}_{\alpha ;k}=\stackrel{}{S}_{\alpha \overline{\beta }}`$. Thus $`_{\mathrm{Syz}}_{\mathrm{Schreyer}}`$.

Let $`\stackrel{}{S}_{\alpha \beta }_{\mathrm{Schreyer}}_{\mathrm{Syz}}`$ be an arbitrary syzygy. We prove first that the set $`_{\mathrm{Schreyer}}\{\stackrel{}{S}_{\alpha \beta }\}`$ still generates $`\mathrm{Syz}()`$. Any syzygy in $`_{\mathrm{Schreyer}}`$ has the form $`\stackrel{}{S}_{\alpha \beta }=x^\mu \stackrel{}{e}_\alpha x^\nu \stackrel{}{e}_\beta +\stackrel{}{R}_{\alpha \beta }`$. By construction, one of the monomials $`x^\mu `$ and $`x^\nu `$ must contain a non-multiplicative variable $`x_k`$ for $`\stackrel{}{h}_\alpha `$ or $`\stackrel{}{h}_\beta `$, respectively. Without loss of generality, we assume that $`x_k\overline{X}_{L,,}(\stackrel{}{h}_\alpha )`$ and $`\mu _k>0`$. This implies that $`_{\mathrm{Syz}}`$ contains the syzygy $`\stackrel{}{S}_{\alpha ;k}`$. As shown above, a unique index $`\gamma \beta `$ exists such that $`\stackrel{}{S}_{\alpha ;k}=\stackrel{}{S}_{\alpha \gamma }`$.

Let $`\stackrel{}{S}_{\alpha \gamma }=x_k\stackrel{}{e}_\alpha x^\rho \stackrel{}{e}_\gamma +\stackrel{}{R}_{\alpha \gamma }`$. By construction, $`x^\rho \stackrel{}{t}_\gamma =x_k\stackrel{}{t}_\alpha `$ divides $`x^\mu \stackrel{}{t}_\alpha =\stackrel{}{t}_{\alpha \beta }`$. Thus $`\stackrel{}{t}_\gamma \stackrel{}{t}_{\alpha \beta }`$ and by Lemma 6 the set $`_{\mathrm{Schreyer}}\{\stackrel{}{S}_{\alpha \beta }\}`$ still generates $`\mathrm{Syz}()`$. If we try to iterate this argument, we encounter the following problem. In order to be able to eliminate $`\stackrel{}{S}_{\alpha \beta }`$ we need both $`\stackrel{}{S}_{\alpha \gamma }`$ and $`\stackrel{}{S}_{\beta \gamma }`$ in the remaining set. For $`\stackrel{}{S}_{\alpha \gamma }_{\mathrm{Syz}}`$, this is always guaranteed. But we know nothing about $`\stackrel{}{S}_{\beta \gamma }`$ and, if it is not an element of $`_{\mathrm{Syz}}`$, it could have been removed in an earlier iteration.

We claim that with respect to the term order $`_{}`$ the term $`\mathrm{lt}_{_{}}\stackrel{}{S}_{\alpha \beta }`$ is greater than both $`\mathrm{lt}_{_{}}\stackrel{}{S}_{\alpha \gamma }`$ and $`\mathrm{lt}_{_{}}\stackrel{}{S}_{\beta \gamma }`$. Without loss of generality, we may assume for simplicity that $`\alpha <\beta <\gamma `$, as the syzygies $`\stackrel{}{S}_{\alpha \beta }`$ and $`\stackrel{}{S}_{\beta \alpha }`$ differ only by a sign. Thus $`\mathrm{lt}_{_{}}\stackrel{}{S}_{\alpha \beta }=\frac{\stackrel{}{t}_{\alpha \beta }}{\stackrel{}{t}_\alpha }\stackrel{}{e}_\alpha `$ and similarly for $`\stackrel{}{S}_{\alpha \gamma }`$ and $`\stackrel{}{S}_{\beta \gamma }`$. Furthermore, $`\stackrel{}{t}_\gamma \stackrel{}{t}_{\alpha \beta }`$ trivially implies $`\stackrel{}{t}_{\alpha \gamma }\stackrel{}{t}_{\alpha \beta }`$ and hence $`\stackrel{}{t}_{\alpha \gamma }\stackrel{}{t}_{\alpha \beta }`$ for any term order $``$. Obviously, the same holds for $`\stackrel{}{t}_{\beta \gamma }`$. Now a straightforward application of the definition of the term order $`_{}`$ proves our claim.

Thus if we always remove the syzygy $`\stackrel{}{S}_{\alpha \beta }_{\mathrm{Schreyer}}_{\mathrm{Syz}}`$ whose leading term is maximal with respect to the term order $`_{}`$, it can never happen that the syzygy $`\stackrel{}{S}_{\beta \gamma }`$ required for the application of Lemma 6 has already been eliminated earlier and $`_{\mathrm{Syz}}`$ is a generating set of $`\mathrm{Syz}()`$.

It is a simple corollary to Schreyer’s theorem that $`_{\mathrm{Syz}}`$ is even a Gröbner basis of $`\mathrm{Syz}()`$. Indeed, we know that $`_{\mathrm{Schreyer}}`$ is a Gröbner basis of $`\mathrm{Syz}()`$ for the term order $`_{}`$ and it follows from our considerations above that whenever we remove a syzygy $`\stackrel{}{S}_{\alpha \beta }`$ we still have in the remaining set at least one syzygy whose leading term divides $`\mathrm{lt}_{_{}}\stackrel{}{S}_{\alpha \beta }`$. Thus we find

$$\mathrm{lt}_{_{}}(_{\mathrm{Syz}})=\mathrm{lt}_{_{}}(_{\mathrm{Schreyer}})=\mathrm{lt}_{_{}}\mathrm{Syz}()$$
(30)
which proves our assertion.∎

This result is not completely satisfying, as it only yields a Gröbner and not an involutive basis of the syzygy module. The latter seems to be hard to achieve for arbitrary divisions $`L`$. For some divisions it is possible with a little effort. The key is that in the order $`_{}`$ the numbering of the generators in $``$ is important and we must choose the right one. For this purpose we slightly generalise a construction of Plesken and Robertz pr:janet  for the special case of a Janet basis.

We associate a graph with each involutive basis $``$. Its vertices are given by the terms in $`\mathrm{lt}_{}`$. If $`x_j\overline{X}_{L,,}(\stackrel{}{h})`$ for some generator $`\stackrel{}{h}`$, then, by definition of an involutive basis, $``$ contains a unique generator $`\overline{\stackrel{}{h}}`$ such that $`\mathrm{le}_{}\overline{\stackrel{}{h}}`$ is an involutive divisor of $`\mathrm{le}_{}(x_j\stackrel{}{h})`$. In this case we include a directed edge from $`\mathrm{le}_{}\stackrel{}{h}`$ to $`\mathrm{le}_{}\overline{\stackrel{}{h}}`$. The thus defined graph is called the *$`L`$-graph* of the basis $``$.

###### Lemma 7

If the division $`L`$ is continuous, then the $`L`$-graph of any involutive set $`𝒫`$ is acyclic.

###### Proof

The vertices of a path in an $`L`$-graph define a sequence as in the definition of a continuous division. If the path is a cycle, then the sequence contains identical elements contradicting the continuity of the division.∎

We order the elements of $``$ as follows: whenever the $`L`$-graph of $``$ contains a path from $`\stackrel{}{h}_\alpha `$ to $`\stackrel{}{h}_\beta `$, then we must have $`\alpha <\beta `$. Any ordering satisfying this condition is called an *$`L`$-ordering*. Note that by the lemma above for a continuous division $`L`$-orderings always exist (although they are in general not unique).

For the Pommaret division $`P`$ it is easy to describe explicitly a $`P`$-ordering without using the $`P`$-graph: we require that if either $`\mathrm{cls}\stackrel{}{h}_\alpha <\mathrm{cls}\stackrel{}{h}_\beta `$ or $`\mathrm{cls}\stackrel{}{h}_\alpha =\mathrm{cls}\stackrel{}{h}_\beta =k`$ and and the last non-vanishing entry of $`\mathrm{le}_{}\stackrel{}{h}_\alpha \mathrm{le}_{}\stackrel{}{h}_\beta `$ is negative, then we must have $`\alpha <\beta `$. Thus we sort the generators $`\stackrel{}{h}_\alpha `$ first by their class and within each class lexicographically (according to our definition in Appendix A of Part I). It is straightforward to verify that this defines indeed a $`P`$-ordering.

###### Example 8

Let us consider the ideal $`𝕜[x,y,z]`$ generated by the six polynomials $`h_1=x^2`$, $`h_2=xy`$, $`h_3=xzy`$, $`h_4=y^2`$, $`h_5=yzy`$ and $`h_6=z^2z+x`$. One easily verifies that they form a Pommaret basis $``$ for the degree reverse lexicographic order. The corresponding $`P`$-graph has the following form

(31)
One clearly sees that the generators are already $`P`$-ordered, namely according to the description above. $``$

The decisive observation about an $`L`$-ordering is that we can now easily determine the leading terms of all syzygies $`𝒮_{\alpha ;k}_{\mathrm{Syz}}`$ for the Schreyer order $`_{}`$.

###### Lemma 8

Let the elements of the involutive basis $`𝒫`$ be ordered according to an $`L`$-ordering. Then the syzygies $`𝒮_{\alpha ;k}`$ satisfy $`\mathrm{lt}_{_{}}𝒮_{\alpha ;k}=x_k\stackrel{}{e}_\alpha `$.

###### Proof

By the properties of the involutive standard representation, we have in (26) $`\mathrm{lt}_{}(P_\beta ^{(\alpha ;k)}\stackrel{}{h}_\beta )\mathrm{lt}_{}(x_k\stackrel{}{h}_\alpha )`$ for all $`\beta `$ and only one index $`\overline{\beta }`$ exists for which $`\mathrm{lt}_{}(P_{\overline{\beta }}^{(\alpha ;k)}\stackrel{}{h}_{\overline{\beta }})=\mathrm{lt}_{}(x_k\stackrel{}{h}_\alpha )`$. Thus $`\mathrm{le}_{}\stackrel{}{h}_{\overline{\beta }}`$ is an involutive divisor of $`\mathrm{le}_{}(x_k\stackrel{}{h}_\alpha )`$ and the $`L`$-graph of $``$ contains an edge from $`\stackrel{}{h}_\alpha `$ to $`\stackrel{}{h}_{\overline{\beta }}`$. In an $`L`$-ordering, this implies $`\alpha <\overline{\beta }`$. Now the assertion follows immediately from the definition of the term order $`_{}`$.∎

There remains the problem of controlling the multiplicative variables associated to these leading terms by the involutive division $`L`$. For arbitrary divisions it does not seem possible to make any statement. Thus we simply define a class of involutive divisions with the desired properties and show afterwards that at least the Janet and the Pommaret division belong to this class.

###### Definition 6

An involutive division $`L`$ is of *Schreyer type* for the term order $``$, if for any set $``$ which is involutive with respect to $`L`$ and $``$ all sets $`\overline{X}_{L,,}(\stackrel{}{h})`$ with $`\stackrel{}{h}`$ are again involutive.

###### Lemma 9

Both the Janet and the Pommaret division are of Schreyer type for any term order $``$.

###### Proof

For the Janet division any set of variables, i. e. monomials of degree one, is involutive. Indeed, let $``$ be such a set and $`x_k`$, then

$$X_{J,}(x_k)=\{x_ix_iik\}$$
(32)
which immediately implies the assertion. For the Pommaret division sets of non-multiplicative variables are always of the form $`=\{x_k,x_{k+1},\mathrm{},x_n\}`$ and such a set is trivially involutive.∎

An example of an involutive division which is not of Schreyer type is the *Thomas division* $`T`$ defined as follows: let $`𝒩_0^n`$ be a finite set and $`\nu 𝒩`$ an arbitrary element; then $`iN_{T,𝒩}(\nu )`$, if and only if $`\nu _i=\mathrm{max}_{\mu 𝒩}\mu _i`$ (obviously, one may consider the Janet division as a kind of refinement of the Thomas division). One easily sees that no set consisting only of variables can be involutive for the Thomas division so that it cannot be of Schreyer type.

###### Theorem 5.2

Let $`L`$ be a continuous involutive division of Schreyer type for the term order $``$ and $``$ an $`L`$-ordered involutive basis of the polynomial module $``$ with respect to $`L`$ and $``$. Then $`_{\mathrm{Syz}}`$ is an involutive basis of $`\mathrm{Syz}()`$ with respect to $`L`$ and the term order $`_{}`$.

###### Proof

By Lemma 8, the leading term of $`\stackrel{}{S}_{\alpha ;k}_{\mathrm{Syz}}`$ is $`x_k\stackrel{}{e}_\alpha `$ and we have one such generator for each non-multiplicative variable $`x_k\overline{X}_{L,,}(\stackrel{}{h}_\alpha )`$. Since we assume that $`L`$ is of Schreyer type for $``$, these leading terms form an involutive set. As we know already from Theorem 5.1 that $`_{\mathrm{Syz}}`$ is a Gröbner basis of $`\mathrm{Syz}()`$, the assertion follows trivially.∎

Note that under the made assumptions it follows immediately from the simple form of the leading terms that $`_{\mathrm{Syz}}`$ is a minimal Gröbner basis of $`\mathrm{Syz}()`$.

###### Example 9

We continue with Example 8. As all assumption of Theorem 5.2 are satisfied, the eight syzygies

$`\stackrel{}{S}_{1;3}`$ $`=z\stackrel{}{e}_1x\stackrel{}{e}_3\stackrel{}{e}_2,`$ (33a)
$`\stackrel{}{S}_{2;3}`$ $`=z\stackrel{}{e}_2x\stackrel{}{e}_5\stackrel{}{e}_2,`$ (33b)
$`\stackrel{}{S}_{3;3}`$ $`=z\stackrel{}{e}_3x\stackrel{}{e}_6+\stackrel{}{e}_5\stackrel{}{e}_3+\stackrel{}{e}_1,`$ (33c)
$`\stackrel{}{S}_{4;3}`$ $`=z\stackrel{}{e}_4y\stackrel{}{e}_5\stackrel{}{e}_4,`$ (33d)
$`\stackrel{}{S}_{5;3}`$ $`=z\stackrel{}{e}_5y\stackrel{}{e}_6+\stackrel{}{e}_2,`$ (33e)
$`\stackrel{}{S}_{1;2}`$ $`=y\stackrel{}{e}_1x\stackrel{}{e}_2,`$ (33f)
$`\stackrel{}{S}_{2;2}`$ $`=y\stackrel{}{e}_2x\stackrel{}{e}_4,`$ (33g)
$`\stackrel{}{S}_{3;2}`$ $`=y\stackrel{}{e}_3x\stackrel{}{e}_5+\stackrel{}{e}_4\stackrel{}{e}_2`$ (33h)
form a Pommaret basis of the syzygy module $`\mathrm{Syz}()`$ with respect to the induced term order $`_{}`$. Indeed, as

$`z\stackrel{}{S}_{1;2}`$ $`=y\stackrel{}{S}_{1;3}x\stackrel{}{S}_{2;3}+x\stackrel{}{S}_{4;2}+\stackrel{}{S}_{2;2},`$ (34a)
$`z\stackrel{}{S}_{2;2}`$ $`=y\stackrel{}{S}_{2;3}x\stackrel{}{S}_{4;3}+\stackrel{}{S}_{2;2},`$ (34b)
$`z\stackrel{}{S}_{3;2}`$ $`=y\stackrel{}{S}_{3;3}x\stackrel{}{S}_{5;3}\stackrel{}{S}_{2;3}+\stackrel{}{S}_{4;3}+\stackrel{}{S}_{3;2}\stackrel{}{S}_{1;2},`$ (34c)
all products of the generators with their non-multiplicative variables possess an involutive standard representation. $``$

## 6 Free Resolutions I: The Polynomial Case

As Theorem 5.2 yields again an involutive basis, we may apply it repeatedly and construct this way a syzygy resolution for any polynomial module $``$ given an involutive basis of it for an involutive division of Schreyer type. We specialise now to Pommaret bases where one can even make a number of statements about the size of the resolution. In particular, we immediately obtain a stronger form of Hilbert’s Syzygy Theorem as a corollary (in fact, we will see later that this is the strongest possible form, as the arising free resolution is always of minimal length).

###### Theorem 6.1

Let $``$ be a Pommaret basis of the polynomial module $`𝒫^m`$. If we denote by $`\beta _0^{(k)}`$ the number of generators $`\stackrel{}{h}`$ such that $`\mathrm{cls}\mathrm{le}_{}\stackrel{}{h}=k`$ and set $`d=\mathrm{min}\{k\beta _0^{(k)}>0\}`$, then $``$ possesses a finite free resolution

$$0𝒫^{r_{nd}}\mathrm{}𝒫^{r_1}𝒫^{r_0}0$$
(35)
of length $`nd`$ where the ranks of the free modules are given by

$$r_i=\underset{k=1}{\overset{ni}{}}\left(\genfrac{}{}{0pt}{}{nk}{i}\right)\beta _0^{(k)}.$$
(36)
###### Proof

According to Theorem 5.2, $`_{\mathrm{Syz}}`$ is a Pommaret basis of $`\mathrm{Syz}()`$ for the term order $`_{}`$. Applying the theorem again, we can construct a Pommaret basis of the second syzygy module $`\mathrm{Syz}^2()`$ and so on. In the proof of Theorem 5.2 we showed that $`\mathrm{le}_{_{}}\stackrel{}{S}_{\alpha ;k}=x_k\stackrel{}{e}_\alpha `$. Hence $`\mathrm{cls}\stackrel{}{S}_{\alpha ;k}=k>\mathrm{cls}\stackrel{}{h}_\alpha `$ and if $`d`$ is the minimal class of a generator in $``$, then the minimal class in $`_{\mathrm{Syz}}`$ is $`d+1`$. This yields the length of the resolution (35), as a Pommaret basis with $`d=n`$ generates a free module.

The ranks of the modules follow from a rather straightforward combinatorial calculation. Let $`\beta _i^{(k)}`$ denote the number of generators of class $`k`$ of the $`i`$th syzygy module $`\mathrm{Syz}^i()`$. By definition of the generators $`\stackrel{}{S}_{\alpha ;k}`$, we find $`\beta _i^{(k)}=_{j=1}^{k1}\beta _{i1}^{(j)}`$, as each generator of class less than $`k`$ in the Pommaret basis of $`\mathrm{Syz}^{i1}()`$ contributes one generator of class $`k`$ to the basis of $`\mathrm{Syz}^i()`$. A simple induction allows us to express the $`\beta _i^{(k)}`$ in terms of the $`\beta _0^{(k)}`$:

$$\beta _i^{(k)}=\underset{j=1}{\overset{ki}{}}\left(\genfrac{}{}{0pt}{}{kj1}{i1}\right)\beta _0^{(j)}.$$
(37)
The ranks of the modules in (35) are given by $`r_i=_{k=1}^n\beta _i^{(k)}`$; entering (37) yields via a classical identity for binomial coefficients (36).∎

###### Remark 9

Theorem 6.1 remains valid for any involutive basis $``$ with respect to a continuous division of Schreyer type, if we define $`\beta _0^{(k)}`$ (respectively $`\beta _i^{(k)}`$ in the proof) as the number of generators with $`k`$ multiplicative variables, since Theorem 5.2 holds for any such basis. Indeed, after the first step we always analyse monomial sets of the form $`\{x_{i_1},x_{i_2},\mathrm{},x_{i_{nk}}\}`$ with $`i_1<i_2<\mathrm{}<i_{nk}`$. By assumption, these sets are involutive and this is only possible, if one for the generators possesses $`n`$ multiplicative variables, another one $`n1`$ and so on until the last generator which has only $`nk`$ multiplicative variables (this follows for example from Proposition 5 on the form of the Hilbert series). Hence the basic recursion relation $`\beta _i^{(k)}=_{j=1}^{k1}\beta _{i1}^{(j)}`$ and all subsequent combinatorial computations remain valid for any division of Schreyer type.

For the special case of the Janet division, Plesken and Robertz pr:janet  proved directly the corresponding statement. Here it is straightforward to determine explicitly the multiplicative variables for any syzygy: if $`h_\alpha `$ is a generator in the Janet basis $``$ with the non-multiplicative variables $`\overline{X}_{J,,}(h_\alpha )=\{x_{i_1},x_{i_2},\mathrm{},x_{i_{nk}}\}`$ where $`i_1<i_2<\mathrm{}<i_{nk}`$, then

$$X_{J,_{\mathrm{Syz}},}(\stackrel{}{S}_{\alpha ;i_j})=\{x_1,\mathrm{},x_n\}\{x_{i_{j+1}},x_{i_{j+2}},\mathrm{},x_{i_{nk}}\},$$
(38)
as one easily verifies. $``$

As in general the resolution (35) is not minimal, the ranks $`r_i`$ appearing in it cannot be identified with the Betti numbers of the module $``$. However, they obviously represent an upper bound. With a little bit more effort one can easily derive similar bounds even for the multigraded Betti numbers; we leave this as an exercise for the reader.

We may explicitly write the syzygy resolution (35) as a complex. Let $`𝒲`$ be a free $`𝒫`$-module with basis $`\{w_1,\mathrm{},w_p\}`$, i. e. its rank is given by the size of the Pommaret basis $``$. Let $`𝒱`$ be a further free $`𝒫`$-module with basis $`\{v_1,\mathrm{},v_n\}`$, i. e. its rank is determined by the number of variables in $`𝒫`$, and denote by $`\mathrm{\Lambda }𝒱`$ the exterior algebra over $`𝒱`$. We set $`𝒞_i=𝒲_𝒫\mathrm{\Lambda }^i𝒱`$ for $`0in`$. If $`\stackrel{}{k}=(k_1,\mathrm{},k_i)`$ is a sequence of integers with $`1k_1<k_2<\mathrm{}<k_in`$ and $`v_\stackrel{}{k}`$ denotes the wedge product $`v_{k_1}\mathrm{}v_{k_i}`$, then a basis of this free $`𝒫`$-module is given by the set of all tensor products $`w_\alpha v_\stackrel{}{k}`$. Finally, we introduce the submodule $`𝒮_i𝒞_i`$ generated by all those basis elements where $`k_1>\mathrm{cls}\stackrel{}{h}_\alpha `$. Note that the rank of $`𝒮_i`$ is precisely $`r_i`$ as defined by (36).

We denote the elements of the Pommaret basis of $`\mathrm{Syz}^i()`$ by $`\stackrel{}{S}_{\alpha ;\stackrel{}{k}}`$ with the inequalities $`\mathrm{cls}\stackrel{}{h}_\alpha <k_1<\mathrm{}<k_i`$. An involutive normal form computation determines for every non-multiplicative index $`nk_{i+1}>k_i=\mathrm{cls}\stackrel{}{S}_{\alpha ;\stackrel{}{k}}`$ unique polynomials $`P_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k},k_{i+1})}𝕜[x_1,\mathrm{},x_\mathrm{}_i]`$ such that

$$x_{k_{i+1}}\stackrel{}{S}_{\alpha ;\stackrel{}{k}}=\underset{\beta =1}{\overset{p}{}}\underset{\stackrel{}{\mathrm{}}}{}P_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k},k_{i+1})}\stackrel{}{S}_{\beta ;\stackrel{}{\mathrm{}}}$$
(39)
where the second sum is over all integer sequences $`\stackrel{}{\mathrm{}}=(\mathrm{}_1,\mathrm{},\mathrm{}_i)`$ satisfying $`\mathrm{cls}\stackrel{}{h}_\beta <\mathrm{}_1<\mathrm{}<\mathrm{}_in`$. Now we define the $`𝒫`$-module homomorphisms $`ϵ:𝒮_0`$ and $`\delta :𝒮_{i+1}𝒮_i`$ by $`ϵ(w_\alpha )=\stackrel{}{h}_\alpha `$ and

$$\delta (w_\alpha v_{\stackrel{}{k},k_{i+1}})=x_{k_{i+1}}w_\alpha v_\stackrel{}{k}\underset{\beta ,\stackrel{}{\mathrm{}}}{}P_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k},k_{i+1})}w_\beta v_{\stackrel{}{\mathrm{}}}.$$
(40)
We extend the differential $`\delta `$ to a map $`𝒞_{i+1}𝒞_i`$ as follows. If $`k_i\mathrm{cls}\stackrel{}{h}_\alpha `$, then we set $`\delta (w_\alpha v_\stackrel{}{k})=0`$. Otherwise let $`j`$ be the smallest value such that $`k_j>\mathrm{cls}\stackrel{}{h}_\alpha `$ and set (by slight abuse of notation)

$$\delta (w_\alpha v_{k_1}\mathrm{}v_{k_i})=v_{k_1}\mathrm{}v_{k_{j1}}\delta (w_\alpha v_{k_j}\mathrm{}v_{k_i}).$$
(41)
Thus the factor $`v_{k_1}\mathrm{}v_{k_{j1}}`$ remains simply unchanged and does not affect the differential. This definition makes, by construction, $`(𝒞_{},\delta )`$ to a complex and $`(𝒮_{},\delta )`$ to an exact subcomplex which (augmented by the map $`ϵ:𝒮_0`$) is isomorphic to the syzygy resolution (35).

###### Example 10

We continue with the ideal of Example 8 and 9, respectively. As here $`d=1`$, the resolution has length $`2`$ in this case. Using the notation introduced above, the module $`𝒮_0`$ is then generated by $`\{w_1,\mathrm{},w_6\}`$, the module $`𝒮_1`$ by the eight elements $`\{w_1v_3,\mathrm{},w_5v_3,w_1v_2,\mathrm{},w_3v_2\}`$ (the first three generators in the Pommaret basis $``$ are of class $`1`$, the next two of class $`2`$ and the final one of class $`3`$) and the module $`𝒮_2`$ by $`\{w_1v_2v_3,\mathrm{},w_3v_2v_3\}`$ corresponding to the three first syzygies of class $`2`$. It follows from the expressions (33) and (34), respectively, for the first and second syzygies that the differential $`\delta `$ is here defined by the relations

$`\delta (w_1v_3)`$ $`=zw_1xw_3w_2,`$ (42a)
$`\delta (w_2v_3)`$ $`=zw_2xw_5w_2,`$ (42b)
$`\delta (w_3v_3)`$ $`=zw_3xw_6+w_5w_3+w_1,`$ (42c)
$`\delta (w_4v_3)`$ $`=zw_4yw_5w_4,`$ (42d)
$`\delta (w_5v_3)`$ $`=zw_5yw_6+w_2,`$ (42e)
$`\delta (w_3v_2)`$ $`=yw_3xw_5+w_4w_2,`$ (42f)
$`\delta (w_2v_2)`$ $`=yw_2xw_4,`$ (42g)
$`\delta (w_1v_2)`$ $`=yw_1xw_2,`$ (42h)
$`\delta (w_1v_2v_3)`$ $`=\begin{array}{cc}& zw_1v_2yw_1v_3+xw_2v_3\hfill \\ & xw_3v_2w_2v_2.\hfill \end{array}`$ (42i)
$`\delta (w_2v_2v_3)`$ $`=zw_2v_2yw_2v_3+xw_4v_3w_2v_2,`$ (42j)
$`\delta (w_3v_2v_3)`$ $`=\begin{array}{cc}& zw_3v_2yw_3v_3+xw_5v_3+\hfill \\ & w_2v_3w_4v_3w_3v_2+w_1v_2,\hfill \end{array}`$ (42k)
It is straightforward to verify explicitly the exactness of the complex $`(𝒮_{},\delta )`$. $``$

In the case that $`m=1`$ and thus $``$ is actually an ideal in $`𝒫`$, it is tempting to try to equip the complex $`(𝒞_{},\delta )`$ with the structure of a differential algebra. We first introduce a multiplication $`\times `$ on $`𝒲`$. If $`h_\alpha `$ and $`h_\beta `$ are two elements of the Pommaret basis $``$, then their product possesses a unique involutive standard representation $`h_\alpha h_\beta =_{\gamma =1}^pP_{\alpha \beta \gamma }h_\gamma `$ and we define

$$w_\alpha \times w_\beta =\underset{\gamma =1}{\overset{p}{}}P_{\alpha \beta \gamma }w_\gamma $$
(43)
and continue $`𝒫`$-linearly on $`𝒲`$. This multiplication can be extended to the whole complex $`𝒞_{}`$ by defining for arbitrary elements $`w,\overline{w}𝒲`$ and $`\omega ,\overline{\omega }\mathrm{\Lambda }𝒱`$

$$(w\omega )\times (\overline{w}\overline{\omega })=(w\times \overline{w})(\omega \overline{\omega }).$$
(44)
The distributivity of $`\times `$ is obvious from its definition. For obtaining a differential algebra, the product $`\times `$ must furthermore be associative and satisfy the graded Leibniz rule $`\delta (a\times b)=\delta (a)\times b+(1)^{|a|}a\times \delta (b)`$ where $`|a|`$ denotes the form degree of $`a`$. While in general both conditions are not met, a number of special situations exist where one indeed obtains a differential algebra.

Let us first consider the associativity. It suffices to study it at the level of $`𝒲`$ where we find that

$`w_\alpha \times (w_\beta \times w_\gamma )`$ $`={\displaystyle \underset{\delta ,ϵ=1}{\overset{p}{}}}P_{\beta \gamma \delta }P_{\alpha \delta ϵ}w_ϵ,`$ (45a)
$`(w_\alpha \times w_\beta )\times w_\gamma `$ $`={\displaystyle \underset{\delta ,ϵ=1}{\overset{p}{}}}P_{\alpha \beta \delta }P_{\gamma \delta ϵ}w_ϵ.`$ (45b)
One easily checks that both $`_{\delta ,ϵ=1}^pP_{\beta \gamma \delta }P_{\alpha \delta ϵ}h_ϵ`$ and $`_{\delta ,ϵ=1}^pP_{\alpha \beta \delta }P_{\gamma \delta ϵ}h_ϵ`$ are standard representations of the product $`h_\alpha h_\beta h_\gamma `$ for the Pommaret basis $``$. However, we cannot conclude that they are involutive standard representations, as we do not know whether $`P_{\beta \gamma \delta }`$ and $`P_{\alpha \beta \delta }`$, respectively, are multiplicative for $`h_ϵ`$. If this was the case, the associativity would follow immediately from the uniqueness of involutive standard representations.

For the graded Leibniz rule the situation is similar but more involved. In the next section we will discuss it in more details for the monomial case. In the end, it boils down to analysing standard representations for products of the form $`x_kh_\alpha h_\beta `$. Again there exist two different ways for obtaining them and a sufficient condition for the satisfaction of the Leibniz rule is that both lead always to the unique involutive standard representation.

###### Example 11

Let us analyse the by now familiar ideal $`𝕜[x,y,z]`$ generated by $`h_1=y^2z`$, $`h_2=yzx`$ and $`h_3=z^2xy`$. We showed already in Part I (Example 5.10) that these polynomials form a Pommaret basis of $``$ for the degree reverse lexicographic term order. The Pommaret basis of the first syzygy module consists of $`\stackrel{}{S}_{1;3}=z\stackrel{}{e}_1y\stackrel{}{e}_2+\stackrel{}{e}_3`$ and $`\stackrel{}{S}_{2;3}=z\stackrel{}{e}_2y\stackrel{}{e}_3x\stackrel{}{e}_1`$. As both generators are of class $`3`$, this is a free module and the resolution stops here.

In a straightforward calculation one obtains for the multiplication $`\times `$ the following defining relations:

$$w_1^2=w_3yw_2+y^2w_1,w_1\times w_2=yw_3+y^2w_2xw_1,$$
(46a)
$$w_1\times w_3=(y^2z)w_3,w_2^2=y^2w_3xw_2+xyw_1,$$
(46b)
$$w_2\times w_3=(yzx)w_3,w_3^2=(z^2xy)w_3.$$
(46c)
Note that all coefficients of $`w_1`$ and $`w_2`$ are contained in $`𝕜[x,y]`$ and are thus multiplicative for all generators. This immediately implies that our multiplication is associative, as any way to evaluate the product $`w_\alpha \times w_\beta \times w_\gamma `$ leads to the unique involutive standard representation of $`h_\alpha h_\beta h_\gamma `$.

As furthermore in the only two non-multiplicative products $`zh_2=yh_3+xh_1`$ and $`zh_1=yh_2+h_3`$ all coefficients on the right hand sides lie in $`𝕜[x,y]`$, too, it follows from the same line of reasoning that the differential satisfies the Leibniz rule and we have a differential algebra. $``$

The situation is not always as favourable as in this example. The next example shows that in general we cannot expect to obtain a differential algebra (in fact, not even an associative algebra).

###### Example 12

Let us continue with the ideal of Examples 8, 9 and 10. Evaluating the defining relation (43) is particularly simple for the products of the form $`w_i\times w_6=h_iw_6`$, as all variables are multiplicative for the generator $`h_6`$. Two further products are $`w_5^2=y^2w_6yw_5xw_4`$ and $`w_3\times w_5=xyw_6yw_5xw_2`$. In a straightforward computation one finds

$$(w_3\times w_5)\times w_5w_3\times w_5^2=x^2w_4xyw_2,$$
(47)
so that the multiplication is not associative. Note that the difference corresponds to the syzygy $`x^2h_4xyh_2=0`$. This is not surprising, as it encodes the difference between two standard representations of $`h_3h_5^2`$. The reason for the non-associativity lies in the coefficient $`y`$ of $`w_5`$ in the power $`w_5^2`$; it is non-multiplicative for $`h_2`$ and the generator $`w_2`$ appears in the product $`w_3\times w_5`$. Hence computing $`w_3\times w_5^2`$ does not lead to an involutive standard representation of $`h_3h_5^2`$ whereas the product $`(w_3\times w_5)\times w_5`$ does. $``$

## 7 Free Resolutions II: The Monomial Case

In the special case of monomial modules, stronger results can be obtained. In particular, it is possible to obtain a closed form of the differential (40) based only on the set $``$ and to characterise those modules for which (35) is a minimal resolution. These are generalisations of results by Eliahou and Kervaire ek:res .

For a monomial module the existence of a Pommaret basis is a non-trivial assumption, as the property of being a monomial module is not invariant under coordinate transformations. Therefore we always assume in the sequel that we are dealing with a quasi-stable submodule $`𝒫^m`$. Let $`=\{\stackrel{}{h}_1,\mathrm{},\stackrel{}{h}_p\}`$ with $`\stackrel{}{h}_\alpha 𝕋^m`$ be its monomial Pommaret basis (by Proposition 2.11 of Part I, it is unique). Furthermore, we introduce the function $`\mathrm{\Delta }(\alpha ,k)`$ determining the unique generator in the Pommaret basis $``$ such that $`x_k\stackrel{}{h}_\alpha =t_{\alpha ,k}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)}`$ with a term $`t_{\alpha ,k}𝕜[X_P(\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)})]`$.

###### Lemma 10

The function $`\mathrm{\Delta }`$ and the terms $`t_{\alpha ,k}`$ satisfy the following relations.

The inequality $`\mathrm{cls}\stackrel{}{h}_\alpha \mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)}k`$ holds for all non-multiplicative indices $`k>\mathrm{cls}\stackrel{}{h}_\alpha `$.

Let $`k_2>k_1>\mathrm{cls}\stackrel{}{h}_\alpha `$ be two non-multiplicative indices. If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_2)}k_1`$, then $`\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_1),k_2)=\mathrm{\Delta }(\alpha ,k_2)`$ and $`x_{k_1}t_{\alpha ,k_2}=t_{\alpha ,k_1}t_{\mathrm{\Delta }(\alpha ,k_1),k_2}`$. Otherwise we have the two equations $`\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_1),k_2)=\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_2),k_1)`$ and $`t_{\alpha ,k_1}t_{\mathrm{\Delta }(\alpha ,k_1),k_2}=t_{\alpha ,k_2}t_{\mathrm{\Delta }(\alpha ,k_2),k_1}`$.

###### Proof

Part (i) is trivial. The inequality $`\mathrm{cls}\stackrel{}{h}_\alpha \mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)}`$ follows from the definition of $`\mathrm{\Delta }`$ and the Pommaret division. If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)}>k`$, then $`\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)}`$ would be an involutive divisor of $`\stackrel{}{h}_\alpha `$ which contradicts the fact that any involutive basis is involutively head autoreduced.

For Part (ii) we compute the involutive standard representation of $`x_{k_1}x_{k_2}\stackrel{}{h}_\alpha `$. There are two ways to do it. We may either write

$$x_{k_1}x_{k_2}\stackrel{}{h}_\alpha =x_{k_2}t_{\alpha ,k_1}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_1)}=t_{\alpha ,k_1}t_{\mathrm{\Delta }(\alpha ,k_1),k_2}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_1),k_2)},$$
(48)
which is an involutive standard representation by Part (i), or start with

$$x_{k_1}x_{k_2}\stackrel{}{h}_\alpha =x_{k_1}t_{\alpha ,k_2}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_2)}$$
(49)
which requires a case distinction. If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_2)}k_1`$, we have already an involutive standard representation and its uniqueness implies our claim. Otherwise we must rewrite multiplicatively $`x_{k_1}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_2)}=t_{\mathrm{\Delta }(\alpha ,k_2),k_1}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_2),k_1)}`$ in order to obtain the involutive standard representation. Again our assertion follows from its uniqueness.∎

Using this lemma, we can now provide a closed form for the differential $`\delta `$ which does not require involutive normal form computations in the syzygy modules $`\mathrm{Syz}^i()`$ (which are of course expensive to perform) but is solely based on information already computed during the determination of $``$. For its proof we must introduce some additional notations and conventions. If again $`\stackrel{}{k}=(k_1,\mathrm{},k_i)`$ is an integer sequence with $`1k_1<\mathrm{}<k_in`$, then we write $`\stackrel{}{k}_j`$ for the same sequence of indices but with $`k_j`$ eliminated. Its first entry is denoted by $`(\stackrel{}{k}_j)_1`$; hence $`(\stackrel{}{k}_j)_1=k_1`$ for $`j>1`$ and $`(\stackrel{}{k}_j)_1=k_2`$ for $`j=1`$. The syzygy $`\stackrel{}{S}_{\alpha ;\stackrel{}{k}}`$ is only defined for $`\mathrm{cls}\stackrel{}{h}_\alpha <k_1`$. We extend this notation by setting $`\stackrel{}{S}_{\alpha ;\stackrel{}{k}}=0`$ for $`\mathrm{cls}\stackrel{}{h}_\alpha k_1`$. This convention will simplify some sums in the sequel.

###### Theorem 7.1

Let $`𝒫^m`$ be a quasi-stable submodule and $`\stackrel{}{k}=(k_1,\mathrm{},k_i)`$. Then the differential $`\delta `$ of the complex $`𝒞_{}`$ may be written in the form

$$\delta (w_\alpha v_\stackrel{}{k})=\underset{j=1}{\overset{i}{}}(1)^{ij}\left(x_{k_j}w_\alpha t_{\alpha ,k}w_{\mathrm{\Delta }(\alpha ,k)}\right)v_{\stackrel{}{k}_j}.$$
(50)
###### Proof

Note that all summands where $`k_j`$ is multiplicative for $`\stackrel{}{h}_\alpha `$ vanish. This implies trivially (41), so that we can restrict to the case that $`\mathrm{cls}\stackrel{}{h}_\alpha <k_1`$. Then our theorem is equivalent to

$$\stackrel{}{S}_{\alpha ;\stackrel{}{k}}=\underset{j=1}{\overset{i}{}}(1)^{ij}\left(x_{k_j}\stackrel{}{S}_{\alpha ;\stackrel{}{k}_j}t_{\alpha ,k_j}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k);\stackrel{}{k}_j}\right).$$
(51)
Some of the terms $`\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k);\stackrel{}{k}_j}`$ might vanish by our above introduced convention. The equation (51) is trivial for $`i=1`$ (with $`\stackrel{}{S}_\alpha =\stackrel{}{h}_\alpha `$) and a simple corollary to Lemma 10 (ii) for $`i=2`$.

For $`i>2`$ things become messy. We proceed by induction on $`i`$. In our approach, the syzygy $`\stackrel{}{S}_{\alpha ;\stackrel{}{k}}`$ arises from the non-multiplicative product $`x_{k_i}\stackrel{}{S}_{\alpha ;\stackrel{}{k}_i}`$. Thus we must compute now the involutive normal form of this product. By our induction hypothesis we may write

$$x_{k_i}\stackrel{}{S}_{\alpha ;\stackrel{}{k}_i}=\underset{j=1}{\overset{i1}{}}(1)^{i1j}\left(x_{k_j}x_{k_i}\stackrel{}{S}_{\alpha ;\stackrel{}{k}_{ji}}x_{k_i}t_{\alpha ,k_j}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_j);\stackrel{}{k}_{ji}}\right).$$
(52)
As $`x_{k_i}`$ is always non-multiplicative, using again the induction hypothesis, each summand may be replaced by the corresponding syzygy—but only at the expense of the introduction of many additional terms. The main task in the proof will be to show that most of them cancel. However, the cancellations occur in a rather complicated manner with several cases, so that no simple way for proving (51) seems to exist. We obtain the following lengthy expression:

$`x_{k_i}`$ $`\stackrel{}{S}_{\alpha ;\stackrel{}{k}_i}={\displaystyle \underset{j=1}{\overset{i1}{}}}(1)^{i1j}\left[x_{k_j}\stackrel{}{S}_{\alpha ;\stackrel{}{k}_j}^1t_{\alpha ,k_j}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_j);\stackrel{}{k}_j}^2\right]`$ (53)
$`+`$ $`{\displaystyle \underset{j=1}{\overset{i1}{}}}x_{k_j}\left[{\displaystyle \underset{\mathrm{}=1}{\overset{j1}{}}}(1)^{\mathrm{}+j+1}x_k_{\mathrm{}}\stackrel{}{S}_{\alpha ;\stackrel{}{k}_\mathrm{}j}^3{\displaystyle \underset{\mathrm{}=j+1}{\overset{i1}{}}}(1)^{\mathrm{}+j+1}x_k_{\mathrm{}}\stackrel{}{S}_{\alpha ;\stackrel{}{k}_j\mathrm{}}^4\right]`$
$``$ $`{\displaystyle \underset{j=1}{\overset{i1}{}}}\begin{array}{cc}\hfill [& {\displaystyle \underset{\mathrm{}=1}{\overset{j1}{}}}(1)^{\mathrm{}+j+1}x_{k_j}t_{\alpha ,k_{\mathrm{}}}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}});\stackrel{}{k}_\mathrm{}j}^5\hfill \\ & {\displaystyle \underset{\mathrm{}=j+1}{\overset{i1}{}}}(1)^{\mathrm{}+j+1}x_{k_j}t_{\alpha ,k_{\mathrm{}}}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}});\stackrel{}{k}_j\mathrm{}}^6]\hfill \end{array}`$
$`+`$ $`{\displaystyle \underset{j=1}{\overset{i2}{}}}(1)^{i1j}x_{k_j}t_{\alpha ,k_i}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_i);\stackrel{}{k}_{ji}}^7+x_{k_{i1}}t_{\alpha ,k_i}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_i);\stackrel{}{k}_{i1,i}}^8`$
$``$ $`{\displaystyle \underset{j=1}{\overset{i1}{}}}t_{\alpha ,k_j}\begin{array}{cc}\hfill [& {\displaystyle \underset{\mathrm{}=1}{\overset{j1}{}}}(1)^{\mathrm{}+j+1}x_k_{\mathrm{}}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_j);\stackrel{}{k}_\mathrm{}j}^9\hfill \\ & {\displaystyle \underset{\mathrm{}=j+1}{\overset{i1}{}}}(1)^{\mathrm{}+j+1}x_k_{\mathrm{}}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_j);\stackrel{}{k}_j\mathrm{}}^{10}]\hfill \end{array}`$
$`+`$ $`{\displaystyle \underset{j=1}{\overset{i1}{}}}t_{\alpha ,k_j}\begin{array}{cc}\hfill [& {\displaystyle \underset{\mathrm{}=1}{\overset{j1}{}}}(1)^{\mathrm{}+j+1}t_{\mathrm{\Delta }(\alpha ,k_j),k_{\mathrm{}}}\stackrel{}{S}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_j),k_{\mathrm{}});\stackrel{}{k}_\mathrm{}j}^{11}\hfill \\ & {\displaystyle \underset{\mathrm{}=j+1}{\overset{i1}{}}}(1)^{\mathrm{}+j+1}t_{\mathrm{\Delta }(\alpha ,k_j),k_{\mathrm{}}}\stackrel{}{S}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_j),k_{\mathrm{}});\stackrel{}{k}_j\mathrm{}}^{12}]\hfill \end{array}`$
$``$ $`{\displaystyle \underset{j=1}{\overset{i1}{}}}(1)^{i1j}t_{\alpha ,k_j}t_{\mathrm{\Delta }(\alpha ,k_j),k_i}\stackrel{}{S}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_j),k_i);\stackrel{}{k}_{ji}}^{13}.`$
Note that the terms $`7`$, $`8`$ and $`13`$, respectively, correspond to the special case $`\mathrm{}=i`$ (and $`j=i1`$) in the sums $`6`$ and $`12`$, respectively. We list them separately, as they must be treated differently. The existence of any summand where the coefficient contains a term $`t_,`$ is bound on conditions.

With the exception of the coefficient $`x_{k_{i1}}`$ in the term $`8`$, all coefficients are already multiplicative. Thus this term must be further expanded using the induction hypothesis for the last time:

$`x_{k_{i1}}t_{\alpha ,k_i}`$ $`\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_i);\stackrel{}{k}_{i1,i}}=t_{\alpha ,k_i}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_i);\stackrel{}{k}_i}^{14}`$ (54)
$``$ $`{\displaystyle \underset{j=1}{\overset{i2}{}}}(1)^{i1j}x_{k_j}t_{\alpha ,k_i}\stackrel{}{S}_{\mathrm{\Delta }(\alpha ,k_i);\stackrel{}{k}_{ji}}^{15}`$
$`+`$ $`{\displaystyle \underset{j=1}{\overset{i1}{}}}(1)^{i1j}t_{\alpha ,k_i}t_{\mathrm{\Delta }(\alpha ,k_i),k_j}\stackrel{}{S}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_i),k_j);\stackrel{}{k}_{ji}}^{16}.`$
The left hand side of (53) and the terms $`1`$, $`2`$ and $`14`$ represent the syzygy $`\stackrel{}{S}_{\alpha ,\stackrel{}{k}}`$ we are looking for. We must thus show that all remaining terms vanish. In order to simplify the discussion of the double sums, we swap $`j`$ and $`\mathrm{}`$ in $`3`$, $`5`$, $`9`$ and $`11`$ so that everywhere $`j<\mathrm{}`$. It is now easy to see that $`3`$ and $`4`$ cancel; each summand of $`3`$ also appears in $`4`$ but with the opposite sign. Note, however, that the same argument does not apply to $`11`$ and $`12`$, as the existence of these terms is bound to different conditions!

For the other cancellations, we must distinguish several cases depending on the classes of the generators in the Pommaret basis $``$. We first study the double sums and thus assume that $`1j<i`$.

* If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_j)}<(\stackrel{}{k}_j)_1`$, the terms $`5`$ and $`10`$ are both present and cancel each other. We must now make a second case distinction on the basis of $`\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}})}`$.

+ If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}})}<(\stackrel{}{k}_j)_1`$, then the terms $`6`$ and $`9`$ are also present and cancel each other. Furthermore, both $`11`$ and $`12`$ exist and cancel due to the second case of Lemma 10 (ii).
    + If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}})}(\stackrel{}{k}_j)_1`$, then none of the four terms $`6`$, $`9`$, $`11`$ and $`12`$ exists. For the latter two terms, this fact is a consequence of the first case of Lemma 10 (ii).
* If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_j)}(\stackrel{}{k}_j)_1`$, then neither $`5`$ nor $`10`$ nor $`12`$ exists. For the remaining double sums, we must again consider the class of $`\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}})}`$.

+ If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}})}<(\stackrel{}{k}_j)_1`$, then the terms $`6`$ and $`9`$ exist and cancel each other. The term $`11`$ does not exist, as Lemma 10 implies the inequalities $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_{\mathrm{}}),k_j)}=\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_j),k_{\mathrm{}})}\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_j)}(\stackrel{}{k}_j)_1`$.
    + If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}})}(\stackrel{}{k}_j)_1`$, then neither $`6`$ nor $`9`$ exist and the term $`11`$ is not present either; this time the application of Lemma 10 (ii) yields the chain of inequalities $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_{\mathrm{}}),k_j)}\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_{\mathrm{}})}(\stackrel{}{k}_j)_1`$.

For the remaining terms everything depends on the class of $`\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_i)}`$ controlling in particular the existence of the term $`8`$.

* If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_i)}<k_1(\stackrel{}{k}_j)_1`$, then the term $`8`$ exists and generates the terms $`15`$ and $`16`$. Under this condition, the term $`7`$ is present, too, and because of Lemma 10 (ii) it cancels $`15`$. Again by Lemma 10 (ii), the conditions for the existence of $`13`$ and $`16`$ are identical and they cancel each other.
* If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_i)}k_1`$, then $`8`$ and consequently $`15`$ and $`16`$ are not present. The analysis of $`7`$ and $`13`$ requires a further case distinction.

+ Under the made assumption, the case $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_i)}<(\stackrel{}{k}_j)_1`$ can occur only for $`j=1`$ as otherwise $`(\stackrel{}{k}_j)_1=k_1`$. Because of Lemma 10 (ii), the terms $`7`$ and $`13`$ exist for $`j=1`$ and cancel each other.
    + If $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_i)}(\stackrel{}{k}_j)_1`$, then $`7`$ does not exist. The term $`13`$ is also not present, but there are two different possibilities: depending on which case of Lemma 10 (ii) applies, we either find $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_j),k_i)}=\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_i)}`$ or $`\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_j),k_i)}=\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\mathrm{\Delta }(\alpha ,k_i),k_j)}\mathrm{cls}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k_i)}`$; but in any case the class is too high.

Thus we have shown that indeed all terms vanish with the exception of $`1`$, $`2`$ and $`14`$ which are needed for the syzygy $`\stackrel{}{S}_{\alpha ,\stackrel{}{k}}`$. This proves our claim.∎

As in the previous section, we may introduce for monomial ideals, i. e. for $`m=1`$, the product $`\times `$. The right hand side of its defining equation (43) simplifies for a monomial basis $``$ to

$$w_\alpha \times w_\beta =m_{\alpha ,\beta }w_{\mathrm{\Gamma }(\alpha ,\beta )}$$
(55)
where the function $`\mathrm{\Gamma }(\alpha ,\beta )`$ determines the unique generator $`h_{\mathrm{\Gamma }(\alpha ,\beta )}`$ such that $`h_\alpha h_\beta =m_{\alpha ,\beta }h_{\mathrm{\Gamma }(\alpha ,\beta )}`$ with a term $`m_{\alpha ,\beta }𝕜[X_P(h_{\mathrm{\Gamma }(\alpha ,\beta )})]`$. Corresponding to Lemma 10, we obtain now the following result.

###### Lemma 11

The function $`\mathrm{\Gamma }`$ and the terms $`m_{\alpha ,\beta }`$ satisfy the following relations.

$`\mathrm{cls}h_{\mathrm{\Gamma }(\alpha ,\beta )}\mathrm{max}\{\mathrm{cls}h_\alpha ,\mathrm{cls}h_\beta \}`$.

$`\mathrm{\Gamma }(\mathrm{\Gamma }(\alpha ,\beta ),\gamma )=\mathrm{\Gamma }(\alpha ,\mathrm{\Gamma }(\beta ,\gamma ))`$ and $`m_{\alpha ,\beta }m_{\mathrm{\Gamma }(\alpha ,\beta ),\gamma }=m_{\beta ,\gamma }m_{\mathrm{\Gamma }(\beta ,\gamma ),\alpha }`$.

$`\mathrm{\Gamma }(\mathrm{\Delta }(\alpha ,k),\beta )=\mathrm{\Delta }(\mathrm{\Gamma }(\alpha ,\beta ),k)`$ and $`t_{\alpha ,k}m_{\mathrm{\Delta }(\alpha ,k),\beta }=t_{\mathrm{\Gamma }(\alpha ,\beta ),k}m_{\alpha ,\beta }`$.

###### Proof

Part (i) is obvious from the definition of the function $`\mathrm{\Gamma }`$. Part (ii) and (iii), respectively, follow from the analysis of the two different ways to compute the involutive standard representation of $`h_\alpha h_\beta h_\gamma `$ and $`x_kh_\alpha h_\beta `$, respectively. We omit the details, as they are completely analogous to the proof of Lemma 10.∎

###### Theorem 7.2

Let $``$ be the Pommaret basis of the quasi-stable ideal $`𝒫`$. Then the product $`\times `$ defined by (55) makes the complex $`(𝒞_{},\delta )`$ to a differential algebra.

###### Proof

This is a straightforward consequence of Lemma 11. Writing out the relations one has to check, one easily finds that Part (ii) ensures the associativity of $`\times `$ and Part (iii) the satisfaction of the graded Leibniz rule.∎

## 8 Minimal Resolutions and Projective Dimension

Recall that for a graded polynomial module $``$ a graded free resolution is *minimal*, if all entries of the matrices corresponding to the maps $`\varphi _i:𝒫^{r_i}𝒫^{r_{i1}}`$ are of positive degree, i. e. no constant coefficients appear. Up to isomorphisms, the minimal resolution is unique and its length is an important invariant, the *projective dimension* $`\mathrm{proj}\mathrm{dim}`$ of the module. If the module $``$ is graded, the resolution (35) is obviously graded, too. However, in general, it is not minimal. We introduce now a class of monomial modules for which it is always the minimal resolution.

###### Definition 7

A (possibly infinite) set $`𝒩_0^n`$ is called *stable*, if for each multi index $`\nu 𝒩`$ all multi indices $`\nu 1_k+1_j`$ with $`k=\mathrm{cls}\nu <jn`$ are also contained in $`𝒩`$. A monomial submodule $`𝒫^m`$ is *stable*, if each of the sets $`𝒩_\alpha =\{\mu x^\mu \stackrel{}{e}_\alpha \}_0^n`$ with $`1\alpha m`$ is stable.

###### Remark 10

The stable modules are of considerable interest, as they contain as a subset the *Borel-fixed* modules, i. e. modules $`𝒫^m`$ which remain invariant under the natural action of the Borel group.131313Classically, the Borel group consists of upper triangular matrices. In our “inverse” conventions we must take lower triangular matrices. Indeed, one can show that (for a ground field of characteristic $`0`$) a module is Borel-fixed, if and only if it can be generated by a set $`𝒮`$ of monomials such that whenever $`x^\nu \stackrel{}{e}_j𝒮`$ then also $`x^{\nu 1_k+1_j}\stackrel{}{e}_j𝒮`$ for all $`\mathrm{cls}\nu k<jn`$ (de:ca, , Thm. 15.23). Generically, the leading terms of any polynomial module form a Borel-fixed module (de:ca, , Thm. 15.20). Note that while stability is obviously independent of the characteristic of the base field, the same is not true for the notion of a Borel-fixed module. $``$

Any monomial submodule has a unique minimal basis. For stable submodules it must coincide with its Pommaret basis. This result represents a very simple and effective characterisation of stable submodules. Furthermore, it shows that any stable submodule is trivially quasi-stable and thus explains the terminology introduced in Definition 5.

###### Proposition 16

Let $`𝒫^m`$ be a monomial submodule. $``$ is stable, if and only if its minimal basis $``$ is simultaneously a Pommaret basis.

###### Proof

Let us assume first that $``$ is stable; we have to show that $`_P=`$. For every term $`\stackrel{}{s}`$ a unique term $`\stackrel{}{t}_1`$ exists such that $`\stackrel{}{s}=s_1\stackrel{}{t}_1`$ for some term $`s_1𝕋`$. If $`s_1𝕜[X_P(\stackrel{}{t}_1)]`$, we are done. Otherwise there exists an index $`j>k=\mathrm{cls}\stackrel{}{t}_1`$ such that $`x_js_1`$ and we rewrite

$$\stackrel{}{s}=\left(\frac{x_k}{x_j}s_1\right)\left(\frac{x_j}{x_k}\stackrel{}{t}_1\right).$$
(56)
Since, by assumption, $``$ is stable, $`(x_j/x_k)\stackrel{}{t}_1`$. Thus a term $`\stackrel{}{t}_2`$ exists such that $`(x_j/x_k)\stackrel{}{t}_1=s_2\stackrel{}{t}_2`$ for some term $`s_2𝕋`$. We are done, if $`\stackrel{}{t}_2|_P\stackrel{}{s}`$. Otherwise we iterate this construction. By the continuity of the Pommaret division, this cannot go on infinitely, i. e. after a finite number of steps we must reach a term $`\stackrel{}{t}_N`$ such that $`\stackrel{}{t}_N|_P\stackrel{}{s}`$ and thus $`\stackrel{}{s}_P`$.

For the converse, assume that the minimal basis $``$ is a Pommaret basis. Then a unique $`\stackrel{}{t}`$ exists for each $`\stackrel{}{s}`$ such that $`\stackrel{}{t}|_P\stackrel{}{s}`$. We must show that with $`k=\mathrm{cls}\stackrel{}{s}\mathrm{cls}\stackrel{}{t}`$ for all $`i>k`$ the terms $`(x_i/x_k)\stackrel{}{s}`$ are also elements of $``$. We distinguish two cases. If $`\stackrel{}{s}=\stackrel{}{t}`$, a $`\overline{\stackrel{}{t}}`$ exists with $`\overline{\stackrel{}{t}}|_P(x_i\stackrel{}{t})`$. As $``$ is a minimal basis, it cannot be that $`\overline{\stackrel{}{t}}=x_i\stackrel{}{t}`$. Instead we must have that $`\overline{\stackrel{}{t}}(x_i/x_k)\stackrel{}{t}=(x_i/x_k)\stackrel{}{s}`$ and we are done. If $`\stackrel{}{s}\stackrel{}{t}`$, we write $`\stackrel{}{s}=s\stackrel{}{t}`$ with $`s𝕋`$. If $`k<\mathrm{cls}\stackrel{}{t}`$, then $`x_ks`$ which implies that we can divide by $`x_k`$ and thus $`(x_i/x_k)\stackrel{}{s}`$. Otherwise, $`\mathrm{cls}\stackrel{}{s}=\mathrm{cls}\stackrel{}{t}`$ and we know from the first case that $`(x_i/x_k)\stackrel{}{t}`$. But $`(x_i/x_k)\stackrel{}{s}=(x_i/x_k)s\stackrel{}{t}`$.∎

This result is due to Mall mall:pom  (but see also the remark after Lemma 1.2 in ek:res ). He used it to give a direct proof of the following interesting result which for us is an immediate corollary to our definition of an involutive basis.

###### Theorem 8.1

Let $`𝒫^m`$ be a graded submodule in generic position and $`𝒢`$ the reduced Gröbner basis of $``$ for an arbitrary term order $``$. If $`\mathrm{char}𝕜=0`$, then $`𝒢`$ is also the minimal Pommaret basis of $``$ for $``$.

###### Proof

The generic initial module of any module is Borel fixed gall:weier  (see also the discussion in (de:ca, , Section 15.9)) which implies in particular that it is stable for $`\mathrm{char}𝕜=0`$. By definition of a reduced Gröbner basis, $`\mathrm{le}_{}𝒢`$ is the minimal basis of $`\mathrm{le}_{}`$. But as $`\mathrm{le}_{}`$ is generically stable, this implies that $`\mathrm{le}_{}𝒢`$ is a Pommaret basis of $`\mathrm{le}_{}`$ and thus $`𝒢`$ is a Pommaret basis of $``$. As the Pommaret division is global, $`𝒢`$ is automatically the unique minimal basis.∎

###### Remark 11

It follows from Lemma 2, that if $``$ is a Pommaret basis of the submodule $`𝒫^m`$ of degree $`q`$, then $`(\mathrm{lt}_{})_q`$ is a stable monomial submodule, as $`\mathrm{lt}_{}_q`$ is obviously its minimal basis and simultaneously a Pommaret basis. $``$

###### Theorem 8.2

Let $`𝒫^m`$ be a quasi-stable module. Then the syzygy resolution given by (35) is minimal, if and only if $``$ is stable.

###### Proof

We denote again the elements of the Pommaret basis of $`\mathrm{Syz}^i()`$ as above by $`\stackrel{}{S}_{\alpha ;\stackrel{}{k}}`$ with the inequalities $`\mathrm{cls}\stackrel{}{h}_\alpha <k_1<\mathrm{}<k_i`$ and the basis elements of the free module $`𝒫^{r_i}`$ by $`\stackrel{}{e}_{\alpha ;\stackrel{}{k}}`$ with the same inequalities. For a monomial module our syzygies are, by construction, of the form

$$\stackrel{}{S}_{\alpha ;\stackrel{}{k}}=x_{k_i}\stackrel{}{e}_{\alpha ;\stackrel{}{k}_i}\underset{\beta =1}{\overset{p}{}}\underset{\stackrel{}{\mathrm{}}}{}t_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k})}\stackrel{}{e}_{\beta ;\stackrel{}{\mathrm{}}}$$
(57)
with terms $`t_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k})}𝕜[x_1,\mathrm{},x_{\mathrm{}_{i1}}]`$ and where the second sum is over all sequences $`\stackrel{}{\mathrm{}}=(\mathrm{}_1,\mathrm{},\mathrm{}_{i1})`$ with $`\mathrm{cls}\stackrel{}{h}_\beta <\mathrm{}_1<\mathrm{}<\mathrm{}_{i1}`$. By definition, the resolution is minimal, if and only if all non-vanishing $`t_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k})}𝕜`$.

We proceed by an induction over the resolution. If $``$ is stable, the Pommaret basis $``$ is the minimal basis of $``$ by Proposition 16. For each element $`\stackrel{}{h}_\alpha `$ and each non-multiplicative index $`k>\mathrm{cls}\stackrel{}{h}_\alpha `$ the product $`x_k\stackrel{}{h}_\alpha `$ has the involutive standard representation $`t_{\alpha ,k}\stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)}`$. As $``$ is the minimal basis of $``$, it is not possible that $`t_{\alpha ,k}𝕜`$, as otherwise $`\stackrel{}{h}_\alpha \stackrel{}{h}_{\mathrm{\Delta }(\alpha ,k)}`$.

Assume that $`t_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k})}𝕜`$ for all possible values of the scripts. For the induction we must show that all non-vanishing coefficients $`t_{\beta ;\stackrel{}{\mathrm{}},\mathrm{}_i}^{(\alpha ;\stackrel{}{k},k_{i+1})}`$ with $`\mathrm{}_i>\mathrm{}_{i1}`$ and $`k_{i+1}>k_i`$ do not lie in $`𝕜`$. For this purpose, we rewrite

$$x_{k_{i+1}}\stackrel{}{S}_{\alpha ;\stackrel{}{k}}=x_{k_i}(x_{k_{i+1}}\stackrel{}{e}_{\alpha ;\stackrel{}{k}_i})\underset{\beta ,\stackrel{}{\mathrm{}}}{}t_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k})}(x_{k_{i+1}}\stackrel{}{e}_{\beta ;\stackrel{}{\mathrm{}}})$$
(58)
and compute a normal form with respect to the Pommaret basis of $`\mathrm{Syz}^{i+1}()`$. We solve each syzygy (57) for its initial term, the first term on the right hand side, and substitute the result in (58) whenever there is a non-multiplicative product of a basis vector $`\stackrel{}{e}_{\beta ;\stackrel{}{\mathrm{}}}`$. As all non-vanishing coefficients $`t_{\beta ;\stackrel{}{\mathrm{}}}^{(\alpha ;\stackrel{}{k})}𝕜`$, such a substitution can never decrease the degree of a coefficient. Thus $`t_{\beta ;\stackrel{}{\mathrm{}},\mathrm{}_i}^{(\alpha ;\stackrel{}{k},k_{i+1})}𝕜`$ for all possible values of the scripts, too.

This proves that for a stable module the resolution (35) is minimal. Assume for the converse that $``$ is not stable. By Proposition 16 the Pommaret basis $``$ cannot be the minimal basis. In this case, $``$ contains elements $`\stackrel{}{h}_\alpha `$, $`\stackrel{}{h}_\beta `$ with $`\stackrel{}{h}_\beta =x_k\stackrel{}{h}_\alpha `$ for some $`x_k\overline{X}_P(\stackrel{}{h}_\alpha )`$. So the syzygy $`\stackrel{}{S}_{\alpha ;k}=x_k\stackrel{}{e}_\alpha \stackrel{}{e}_\beta `$ contains a constant coefficient and the resolution is not minimal.∎

###### Example 13

One might be tempted to conjecture that this result extended to polynomial modules, i. e. that (35) was minimal for polynomial modules $``$ with stable leading module $`\mathrm{lt}_{}`$. Unfortunately, this is not true. Consider the homogeneous ideal $`𝕜[x,y,z]`$ generated by $`h_1=z^2+xy`$, $`h_2=yzxz`$, $`h_3=y^2+xz`$, $`h_4=x^2z`$ and $`h_5=x^2y`$. One easily checks that these elements form a Pommaret basis $``$ for the degree reverse lexicographic term order and that $`\mathrm{lt}_{}`$ is a stable module. A Pommaret basis of $`\mathrm{Syz}()`$ is given by

$`\stackrel{}{S}_{2;3}`$ $`=z\stackrel{}{e}_2+(xy)\stackrel{}{e}_1+x\stackrel{}{e}_3\stackrel{}{e}_4\stackrel{}{e}_5,`$ (59a)
$`\stackrel{}{S}_{3;3}`$ $`=z\stackrel{}{e}_3x\stackrel{}{e}_1(x+y)\stackrel{}{e}_2\stackrel{}{e}_4+\stackrel{}{e}_5,`$ (59b)
$`\stackrel{}{S}_{4;3}`$ $`=z\stackrel{}{e}_4x^2\stackrel{}{e}_1+x\stackrel{}{e}_5,`$ (59c)
$`\stackrel{}{S}_{5;3}`$ $`=z\stackrel{}{e}_5x^2\stackrel{}{e}_2x\stackrel{}{e}_4,`$ (59d)
$`\stackrel{}{S}_{4;2}`$ $`=(yx)\stackrel{}{e}_4x^2\stackrel{}{e}_2,`$ (59e)
$`\stackrel{}{S}_{5;2}`$ $`=y\stackrel{}{e}_5x^2\stackrel{}{e}_3+x\stackrel{}{e}_4.`$ (59f)
As the first two generators show, the resolution (35) is not minimal. $``$

Given an arbitrary graded free resolution, it is a standard task to reduce it to the minimal resolution using just some linear algebra (see for example (clo:uag, , Chapt. 6, Theorem 3.15) for a detailed discussion). Thus for any concrete module $``$ it is straightforward to obtain from (35) the minimal resolution. However, even in the monomial case it seems highly non-trivial to find a closed form description of the outcome of the minimisation process. Nevertheless, the resolution (35) contains so much structure that certain statements are possible.

###### Theorem 8.3

Let $``$ be a Pommaret basis of the graded module $`𝒫^m`$ for a class respecting term order and set $`d=\mathrm{min}_\stackrel{}{h}\mathrm{cls}\stackrel{}{h}`$. Then $`\mathrm{proj}\mathrm{dim}=nd`$.

###### Proof

Consider the resolution (35) which is of length $`nd`$. The last map in it is defined by the syzygies $`\stackrel{}{S}_{\alpha ;(d+1,\mathrm{},n)}`$ originating in the generators $`\stackrel{}{h}_\alpha `$ with $`\mathrm{cls}\stackrel{}{h}_\alpha =d`$. Choose now among these generators an element $`\stackrel{}{h}_\gamma `$ of maximal degree (recall that the same choice was crucial in the proof of Proposition 4). Then the syzygy $`\stackrel{}{S}_{\gamma ;(d+1,\mathrm{},n)}`$ cannot contain any constant coefficient, as the coefficients of all basis vectors $`\stackrel{}{e}_{\beta ;\stackrel{}{k}}`$ where the last entry of $`\stackrel{}{k}`$ is $`n`$ must be contained in $`x_1,\mathrm{},x_{n1}`$ and the coefficients of the basis vectors $`\stackrel{}{e}_{\alpha ;(d+1,\mathrm{},n1)}`$ cannot be constant for degree reasons.

If we start now a minimisation process at the end of the resolution, then it will never introduce a constant term into the syzygy $`\stackrel{}{S}_{\gamma ;(d+1,\mathrm{},n)}`$ and thus it will never be eliminated. It is also not possible that it is reduced to zero, as the last map in a free resolution is obviously injective. This implies that the last term of the resolution will not vanish during the minimisation and the length of the minimal resolution, i. e. $`\mathrm{proj}\mathrm{dim}`$, is still $`nd`$.∎

The graded form of the *Auslander-Buchsbaum formula* (de:ca, , Exercise 19.8) is now a trivial corollary to this theorem and Proposition 4 on the depth. Note that, in contrast to other proofs, our approach is constructive in the sense that we automatically have an explicit regular sequence of maximal length and an explicit free resolution of minimal length.

###### Corollary 10 (Auslander-Buchsbaum)

Let $`𝒫^m`$ be a graded polynomial module with $`𝒫=𝕜[x_1,\mathrm{},x_n]`$. Then $`\mathrm{depth}+\mathrm{proj}\mathrm{dim}=n`$.

As for a monomial module we do not need a term order, we obtain as further simple corollary the following relation between $`\mathrm{proj}\mathrm{dim}`$ and $`\mathrm{proj}\mathrm{dim}(\mathrm{lt}_{})`$.

###### Corollary 11

Let $`𝒫^m`$ be a graded module and $``$ an arbitrary term order for which $``$ possesses a Pommaret basis. Then $`\mathrm{proj}\mathrm{dim}\mathrm{proj}\mathrm{dim}(\mathrm{lt}_{})`$.

###### Proof

Let $``$ be the Pommaret basis of the module $``$ for the term order $``$ and set $`d=\mathrm{min}_\stackrel{}{h}\mathrm{cls}(\mathrm{lt}_{}\stackrel{}{h})`$. Then it follows immediately from Theorem 8.3 that $`\mathrm{proj}\mathrm{dim}(\mathrm{lt}_{})=nd`$. On the other hand, Theorem 6.1 guarantees the existence of the free resolution (35) of length $`nd`$ for $``$ so that this value is an upper bound for $`\mathrm{proj}\mathrm{dim}`$.∎

## 9 Castelnuovo-Mumford Regularity

For notational simplicity we restrict again to ideals instead of submodules. In many situations it is of interest to obtain a good estimate on the degree of an ideal basis. Up to date, no satisfying answer is known to this question. Somewhat surprisingly, the stronger problem of bounding not only the degree of a basis of $``$ but also of its syzygies can be treated effectively.

###### Definition 8

Let $`𝒫`$ be a homogeneous ideal. $``$ is called *$`q`$-regular*, if its $`i`$th syzygy module is generated by elements of degree less than or equal to $`q+i`$. The *Castelnuovo-Mumford regularity* $`\mathrm{reg}`$ is the least $`q`$ for which $``$ is $`q`$-regular.

Among other applications, the Castelnuovo-Mumford regularity $`\mathrm{reg}`$ is a useful measure for the complexity of Gröbner basis computations bm:cac . The question of effectively computing $`\mathrm{reg}`$ has recently attracted some interest. In this section we show that $`\mathrm{reg}`$ is trivially determined by a Pommaret basis with respect to the degree reverse lexicographic order and provide alternative proofs to some characterisations of the Castelnuovo-Mumford regularity proposed in the literature.

###### Theorem 9.1

Let $`𝒫`$ be a homogeneous ideal. The Castelnuovo-Mumford regularity of $``$ is $`q`$, if and only if $``$ has in some coordinates a homogeneous Pommaret basis of degree $`q`$ with respect to the degree reverse lexicographic order.

###### Proof

Let $`\stackrel{}{x}`$ be some $`\delta `$-regular coordinates for the ideal $``$ so that it possess a Pommaret basis $``$ of degree $`q`$ with respect to the degree reverse lexicographic order in these coordinates. Then the $`i`$th module of the syzygy resolution (35) induced by the basis $``$ is obviously generated by elements of degree less than or equal to $`q+i`$. Thus we have the trivial estimate $`\mathrm{reg}q`$ and there only remains to show that it is in fact an equality.

For this purpose, consider a generator $`h_\gamma `$ of degree $`q`$ which is of minimal class among all elements of this maximal degree $`q`$ in $``$. If $`\mathrm{cls}h_\gamma =n`$, then $`h_\gamma `$ cannot be removed from $``$ without loosing the basis property, as the leading term of no other generator of class $`n`$ can divide $`\mathrm{lt}_{}h_\gamma `$ and, since the degree reverse lexicographic order is class respecting, all other generators do not contain any terms of class $`n`$. Hence we trivially find $`\mathrm{reg}=q`$ in this case.

If $`\mathrm{cls}h_\gamma =ni`$ for some $`i>0`$, then the resolution (35) contains at the $`i`$th position the syzygy $`\stackrel{}{S}_{\gamma ;(ni+1,\mathrm{},n)}`$ of degree $`q+i`$. Assume now that we minimise the resolution step by step starting at the end. We claim that the syzygy $`\stackrel{}{S}_{\gamma ;(ni+1,\mathrm{},n)}`$ is not eliminated during this process.

There are two possibilities how $`\stackrel{}{S}_{\gamma ;(ni+1,\mathrm{},n)}`$ could be removed during the minimisation. The first one is that a syzygy at the next level of the resolution contained the term $`\stackrel{}{e}_{\gamma ;(ni+1,\mathrm{},n)}`$ with a constant coefficient. Any such syzygy is of the form (39) with $`\mathrm{cls}h_\alpha <ni`$ and $`\mathrm{cls}h_\alpha <k_1<\mathrm{}<k_i<n`$ and its leading term is $`x_{k_{i+1}}\stackrel{}{e}_{\alpha ;\stackrel{}{k}}`$ with $`k_{i+1}>k_i`$. However, since $`\mathrm{cls}(x_{k_1}\mathrm{}x_{k_{i+1}}h_\alpha )<ni`$ and $`\mathrm{cls}(x_{ni+1}\mathrm{}x_nh_\gamma )=ni`$, it follows from our use of the degree reverse lexicographic order (since we assume that everything is homogeneous, both polynomial have the same degree) and the definition of the induced Schreyer term orders, that the term $`\stackrel{}{e}_{\gamma ;(ni+1,\mathrm{},n)}`$ is greater than the leading term $`x_{k_{i+1}}\stackrel{}{e}_{\alpha ;\stackrel{}{k}}`$ of any syzygy $`\stackrel{}{S}_{\alpha ;(k_1,\mathrm{},k_{i+1})}`$ at the level $`i+1`$ and thus cannot appear.

The second possibility is that $`\stackrel{}{S}_{\gamma ;(ni+1,\mathrm{},n)}`$ itself contained a constant coefficient at some vector $`\stackrel{}{e}_{\beta ;\stackrel{}{\mathrm{}}}`$. However, this required $`\mathrm{deg}h_\beta =\mathrm{deg}h_\gamma +1`$ which is again a contradiction.141414For later use we note the following fact about this argument. If $`\stackrel{}{e}_{\beta ;\stackrel{}{\mathrm{}}}`$ is a constant term in the syzygy $`\stackrel{}{S}_{\gamma ;(ni+1,\mathrm{},n)}`$, then it must be smaller than the leading term and hence $`\mathrm{lt}_{}(x_\mathrm{}_1\mathrm{}x_\mathrm{}_ih_\beta )\mathrm{lt}_{}(x_{k_1}\mathrm{}x_{k_{i+1}}h_\alpha )`$ implying that $`\mathrm{cls}h_\beta \mathrm{cls}h_\gamma `$. Thus it suffices, if $`h_\gamma `$ is of maximal degree among all generators $`h_\beta `$ with $`\mathrm{cls}h_\beta \mathrm{cls}h_\gamma `$. For the special case that $`h_\gamma `$ is of minimial class, we exploited this observation already in the proof of Theorem 8.3. As the minimisation process never introduces new constant coefficients, the syzygy $`\stackrel{}{S}_{\gamma ;(ni+1,\mathrm{},n)}`$ may only be modified but not eliminated. Furthermore, the modifications cannot make $`\stackrel{}{S}_{\gamma ;(ni+1,\mathrm{},n)}`$ to the zero syzygy, as otherwise a basis vector of the next level was in the kernel of the differential. However, this is not possible, as we assume that the tail of the resolution is already minimised and by the exactness of the sequence any kernel member must be a linear combination of syzygies. Hence the final minimal resolution will contain at the $`i`$th position a generator of degree $`q+i`$ and $`\mathrm{reg}=q`$.∎

To some extent this result was to be expected. By Theorem 8.1, the reduced Gröbner basis is generically also a Pommaret basis and according to Bayer and Stillman bs:mreg  this basis has for the degree reverse lexicographic order generically the degree $`\mathrm{reg}`$. Thus the only surprise is that Theorem 9.1 does not require that the leading ideal is stable and the Pommaret basis $``$ is not necessarily a reduced Gröbner basis (if the ideal $``$ has a Pommaret basis of degree $`q`$, then the truncated ideal $`(\mathrm{le}_{})_q`$ is always stable by Remark 11 and thus the set $`_q`$ defined by (1) is the reduced Gröbner basis of $`_q`$).

Note furthermore that Theorem 9.1 implies a remarkable fact: given arbitrary coordinates $`\stackrel{}{x}`$, the ideal $``$ either does not possess a finite Pommaret basis for the degree reverse lexicographic order or, if such a basis exists, it is of degree $`\mathrm{reg}`$. Hence using Pommaret bases, it becomes trivial to determine the Castelnuovo-Mumford regularity: it is just the degree of the basis.

###### Remark 12

The proof of Theorem 9.1 also provides us with information about the positions at which in the minimal resolution the maximal degree is attained. We only have to look for all elements of maximal degree in the Pommaret basis; their classes correspond to these positions. $``$

###### Remark 13

Recall from Remark 9 that Theorem 6.1 remains valid for any involutive basis $``$ with respect to a continuous division of Schreyer type (with an obvious modification of the definition of the numbers $`\beta _0^{(k)}`$) and that it is independent of the used term order. It follows immediately from the form of the resolution (35), i. e. from the form of the maps in it given by the respective involutive bases according to Theorem 5.2, that always the estimate $`\mathrm{reg}\mathrm{deg}`$ holds and thus any such basis provides us with a bound for the Castelnuovo–Mumford regularity.

This observation also implies that an involutive basis with respect to a division of Schreyer type and an arbitrary term order can never be of lower degree than the Pommaret basis for the degree reverse lexicographic order. The latter one is thus in this sense optimal. As a concrete example consider again the ideal mentioned in Remark 3: in “good” coordinates a Pommaret basis of degree $`2`$ exists for it and after a simple permutation of the variables its Janet basis is of degree $`4`$. $``$

In analogy to Corollary 11 comparing the projective dimension of a module $``$ and its leading module $`\mathrm{lt}_{}`$ with respect to an arbitrary term order $``$, we may derive a similar estimate for the Castelnuovo-Mumford regularity.

###### Corollary 12

Let $`𝒫`$ be a homogeneous ideal and $``$ an arbitrary term order such that a Pommaret basis of $``$ exists. Then $`\mathrm{reg}\mathrm{reg}(\mathrm{lt}_{})`$.

###### Proof

Let $``$ be the Pommaret basis of $``$ for the term order $``$ and set $`q=\mathrm{deg}`$. Then it follows immediately from Theorem 9.1 that $`\mathrm{reg}(\mathrm{lt}_{})=q`$. On the other hand, the form of the free resolution (35) implies trivially that $`\mathrm{reg}q`$.∎

###### Remark 14

Bayer et al. bcp:betti  introduced a refinement of the Castelnuovo–Mumford regularity: the *extremal Betti numbers*. Recall that the (graded) Betti number $`\beta _{ij}`$ of the ideal $`I`$ is defined as the number of minimal generators of degree $`i+j`$ of the $`i`$th module in the minimal free resolution of $``$ (thus $`\mathrm{reg}`$ is the maximal value $`j`$ such that $`\beta _{i,i+j}>0`$ for some $`i`$). A Betti number $`\beta _{ij}>0`$ is called extremal, if $`\beta _k\mathrm{}=0`$ for all $`ki`$ and $`\mathrm{}>j`$. There always exists a least one extremal Betti number: if we take the maximal value $`i`$ for which $`\beta _{i,i+\mathrm{reg}}>0`$, then $`\beta _{i,i+\mathrm{reg}}`$ is extremal. In general, there may exist further extremal Betti numbers. Bayer et al. (bcp:betti, , Thm. 1.6) proved that for any ideal $``$ both the positions and the values of the extremal Betti numbers coincides with those of its generic initial ideal with respect to the degree reverse lexicographic order.

Our proof of Theorem 9.1 allows us to make the same statement for the ordinary initial ideal for $`_{\text{degrevlex}}`$—provided the coordinates are $`\delta `$-regular. Furthermore, it shows that the extremal Betti numbers of $``$ can be immediately read off the Pommaret basis $``$ of $``$. Finally, if we introduce “pseudo-Betti numbers” for the (in general non-minimal) resolution (35), then the positions and values of the extremal numbers coincide with the true extremal Betti numbers of $``$.

Take the generator $`h_\gamma `$ used in the proof of Theorem 9.1. If $`\mathrm{cls}h_\gamma =ni_1`$ and $`\mathrm{deg}h_\gamma =q_1`$, then the considerations in the proof imply immediately that $`\beta _{i_1,q_1+i_1}`$ is an extremal Betti number and its value is given by the number of generators of degree $`q_1`$ and class $`ni_1`$ in the Pommaret basis $``$. If $`i_1=\mathrm{depth}`$, then this is the only extremal Betti number. Otherwise, let $`q_2`$ be the maximal degree of a generator $`h`$ with $`\mathrm{cls}h<ni_1`$ and assume that $`ni_2`$ is the minimal class of such a generator. Then the arguments used in the proof of Theorem 9.1 show that $`\beta _{i_2,q_2+i_2}`$ is also an extremal Betti number and that its value is given by the number of generators of degree $`q_2`$ and class $`ni_2`$ in the Pommaret basis $``$. Continuing in this manner, we obtain all extremal Betti numbers. Since all our considerations depend only on the leading terms of the generators, we find for the leading ideal $`\mathrm{lt}_{}`$ exactly the same situation. $``$

Combining the above results with Remark 11 and Proposition 16 immediately implies the following generalisation of a result by Eisenbud, Reeves and Totaro (ert:veronese, , Prop. 10) for Borel-fixed monomial ideals.

###### Proposition 17

Let $``$ be a quasi-stable ideal generated in degrees less than or equal to $`q`$. The ideal $``$ is $`q`$-regular, if and only if the truncation $`_q`$ is stable.

Bayer and Stillman bs:mreg  gave the following characterisation of $`q`$-regularity for which we now provide a new proof. Note the close relationship between their first condition and the idea of assigning multiplicative variables.

###### Theorem 9.2

Let $`𝒫`$ be a homogeneous ideal which can be generated by elements of degree less than or equal to $`q`$. Then $``$ is $`q`$-regular, if and only if for some value $`0dn`$ linear forms $`y_1,\mathrm{},y_d𝒫_1`$ exist such that

$$(,y_1,\mathrm{},y_{j1}:y_j)_q=,y_1,\mathrm{},y_{j1}_q,1jd,$$
(60a)
$$,y_1,\mathrm{},y_d_q=𝒫_q.$$
(60b)
###### Proof

Assume first that the conditions (60) are satisfied for some linear forms $`y_1,\mathrm{},y_d𝒫_1`$ and choose variables $`\stackrel{}{x}`$ such that $`x_i=y_i`$ for $`1id`$. Let the finite set $`_q`$ be a basis of $`_q`$ as a vector space in triangular form with respect to the degree reverse lexicographic order, i. e. $`\mathrm{lt}_{}h_1\mathrm{lt}_{}h_2`$ for all $`h_1,h_2_q`$. We claim that $`_q`$ is a Pommaret basis of the truncation $`_q`$ implying that the full ideal $``$ possesses a Pommaret basis of degree $`q^{}q`$ and hence by Theorem 9.1 that $`\mathrm{reg}q`$.

Let us write $`_q=\{h_{k,\mathrm{}}1kn,1\mathrm{}\mathrm{}_k\}`$ where $`\mathrm{cls}h_{k,\mathrm{}}=k`$. A basis of the vector space $`,x_1,\mathrm{},x_j_q`$ is then given by all $`h_{k,\mathrm{}}`$ with $`k>j`$ and all terms in $`x_1,\mathrm{},x_j_q`$. We will now show that

$$_{q+1}=\{x_jh_{k,\mathrm{}}1jk,1kn,1\mathrm{}\mathrm{}_k\}$$
(61)
is a basis of $`_{q+1}`$ as a vector space. This implies that $`_q`$ is locally involutive for the Pommaret division and thus involutive by Corollary 7.3 of Part I. Since, by assumption, $``$ is generated in degrees less than or equal to $`q`$, we have furthermore $`_q=_q`$ so that indeed $`_q`$ is a Pommaret basis of the ideal $`_q`$.

Let $`f_{q+1}`$ and $`\mathrm{cls}f=j`$. By the properties of the degree reverse lexicographic order this implies that $`f=x_j\widehat{f}+g`$ with $`\widehat{f}\left(𝕜[x_j,\mathrm{},x_n]\{0\}\right)_q`$ and $`g\left(x_1,\mathrm{},x_{j1}\right)_{q+1}`$ (cf. Lemma A.1 of Part I). We distinguish two cases. The condition (60b) implies that $`\left(,x_1,\mathrm{},x_d\right)_q=𝒫_q`$. Thus if $`j>d`$, we may write $`\widehat{f}=_{k=d+1}^n_{\mathrm{}=1}^\mathrm{}_kc_{k,\mathrm{}}h_{k,\mathrm{}}+\widehat{g}`$ with $`c_{k,\mathrm{}}𝕜`$ and $`\widehat{g}\left(x_1,\mathrm{},x_d\right)_q`$. We set $`\widehat{f}_0=_{k=j}^n_{\mathrm{}=1}^\mathrm{}_kc_{k,\mathrm{}}h_{k,\mathrm{}}`$ and $`\widehat{f}_1=_{k=d+1}^{j1}_{\mathrm{}=1}^\mathrm{}_kc_{k,\mathrm{}}h_{k,\mathrm{}}+\widehat{g}`$. Obviously, $`\widehat{f}(,x_1,\mathrm{},x_{j1}:x_j)_q`$. If $`jd`$, then the condition (60a) implies that actually $`\widehat{f},x_1,\mathrm{},x_{j1}_q`$. Hence in this case we may decompose $`\widehat{f}=\widehat{f}_0+\widehat{f}_1`$ with $`\widehat{f}_0=_{k=j}^n_{\mathrm{}=1}^\mathrm{}_kc_{k,\mathrm{}}h_{k,\mathrm{}}`$ and $`\widehat{f}_1\left(x_1,\mathrm{},x_{j1}\right)_q`$.

It is trivial that $`_{q+1}_{q+1}`$ (here we mean the linear span over $`𝕜`$ and not over $`𝒫`$). We show by an induction over $`j`$ that $`_{q+1}_{q+1}`$. If $`j=1`$, then $`f=x_1\widehat{f}`$ with $`\widehat{f}_q`$. Thus $`f_{q+1}`$. If $`j>1`$, we write $`f=f_0+f_1`$ with $`f_0=x_j\widehat{f}_0`$ and $`f_1=x_j\widehat{f}_1+g`$ where $`\widehat{f}_0`$ and $`\widehat{f}_1`$ have been defined above. By construction, $`f_0_{q+1}`$, as $`x_j`$ is multiplicative for all generators contained in $`\widehat{f}_0`$, and $`f_1_{q+1}`$ with $`\mathrm{cls}f_1<j`$. According to our inductive hypothesis this implies that $`f_1_{q+1}`$, too. Hence $`_{q+1}=_{q+1}`$.

Assume conversely that the ideal $``$ is $`q`$-regular. Then, by Theorem 9.1, it possesses a Pommaret basis $``$ of degree $`\mathrm{reg}q`$ with respect to the degree reverse lexicographic order. We set $`d=dim𝒫/`$ and claim that for the choice $`y_i=x_i`$ for $`1id`$ the conditions (60) are satisfied. For the second equality (60b) this follows immediately from Proposition 11 which shows that it actually holds already at degree $`\mathrm{reg}q`$.

For the first equality (60a) take a polynomial $`f(,x_1,\mathrm{},x_{j1}:x_j)_q`$. By definition, we have then $`x_jf,x_1,\mathrm{},x_{j1}`$. If $`fx_1,\mathrm{},x_{j1}`$, then there is nothing to prove. Otherwise, a polynomial $`gx_1,\mathrm{},x_{j1}`$ exists such that $`x_jfg`$ and obviously $`\mathrm{cls}(x_jfg)=j`$. If we introduce the set $`_j=\{h\mathrm{cls}hj\}`$, the involutive standard representation of $`x_jfg`$ induces an equation $`x_jf=_{h_j}P_hh+\overline{g}`$ where $`\overline{g}x_jx_1,\mathrm{},x_{j1}`$ and $`P_hx_j`$ (this is trivial if $`\mathrm{cls}h>j`$ and follows from $`\mathrm{deg}hq`$ if $`\mathrm{cls}h=j`$). Thus we can divide by $`x_j`$ and find that already $`f,x_1,\mathrm{},x_{j1}_q`$.∎

Bayer and Stillman bs:mreg  further proved that in *generic* coordinates it is not possible to find a Gröbner basis of degree less than $`\mathrm{reg}`$ and that this estimate is sharp, as it is realised by bases with respect to the degree reverse lexicographic order. The restriction to the generic case is here essential, as for instance most monomial ideals are trivial counter examples. Hence their result is only of limited use for the actual computation of the Castelnuovo-Mumford regularity, as one never knows whether one works with generic coordinates.

###### Example 14

Consider the homogeneous ideal

$$=z^8wxy^6,y^7x^6z,yz^7wx^7[w,x,y,z].$$
(62)
The given basis of degree $`8`$ is already a Gröbner basis for the degree reverse lexicographic term order. If we perform a permutation of the variables and consider $``$ as an ideal in $`[w,y,x,z]`$, then we obtain for the degree reverse lexicographic term order the following Gröbner basis of degree $`50`$:

$$\begin{array}{c}\{y^7x^6z,yz^7wx^7,z^8wxy^6,y^8z^6wx^{13},\hfill \\ \hfill y^{15}z^5wx^{19},y^{22}z^4wx^{25},y^{29}z^3wx^{31},\\ \hfill y^{36}z^2wx^{37},y^{43}zwx^{43},y^{50}wx^{49}\}.\end{array}$$
(63)
Unfortunately, neither coordinate system is generic: as $`\mathrm{reg}=13`$, one yields a basis of too low degree and the other one one of too high degree.

With a Pommaret basis it is no problem to determine the Castelnuovo-Mumford regularity, as the first coordinate system is $`\delta `$-regular. A Pommaret basis of $``$ for the degree reverse lexicographic term order is obtained by adding the polynomials $`z^k(y^7x^6z)`$ for $`1k6`$ and thus the degree of the basis is indeed $`13`$. $``$

Yet another characterisation of $`q`$-regularity is due to Eisenbud and Goto eg:freeres . Again it can be obtained as an easy corollary to Theorem 9.1.

###### Theorem 9.3

The homogeneous ideal $`𝒫`$ is $`q`$-regular, if and only if its truncation $`_q`$ admits a linear free resolution, i. e. $`_q`$ is generated by elements of degree $`q`$ and all maps in the resolution are linear in the sense that the entries of the matrices describing them are zero or homogeneous polynomials of degree $`1`$.

###### Proof

If $``$ is $`q`$-regular, then by Theorem 9.1 it possesses in suitable coordinates a Pommaret basis $``$ of degree $`\mathrm{reg}q`$. The set $`_q`$ defined by (1) is a Pommaret basis of the truncated ideal $`_q`$ according to Lemma 1. Now it follows easily from Theorem 5.2 that $`_q`$ possesses a linear free resolution, as all syzygies in the resolution (35) derived from $`_q`$ are necessarily homogeneous of degree $`1`$.

The converse is trivial. The existence of a linear resolution for $`_q`$ immediately implies that $`\mathrm{reg}_q=q`$. Hence $`_q`$ possesses a Pommaret basis of degree $`q`$ by Theorem 9.1 entailing the existence of a Pommaret basis for $``$ of degree $`q^{}q`$. Hence, again by Theorem 9.1, $`\mathrm{reg}=q^{}q`$.∎

## 10 Regularity and Saturation

Already in the work of Bayer and Stillman bs:mreg  on the Castelnuovo-Mumford regularity the *saturation* $`^{\mathrm{sat}}`$ of a homogeneous ideal $`𝒫`$ plays an important role. Recall that by definition

$$^{\mathrm{sat}}=:𝒫_+^{\mathrm{}}=\{f𝒫k_0:f𝒫_k\}.$$
(64)
An ideal $``$ such that $`=^{\mathrm{sat}}`$ is called *saturated*. We show now first how $`^{\mathrm{sat}}`$ can be effectively determined from a Pommaret basis of $``$.151515It seems to be folklore that for Gröbner bases the construction in Proposition 18 yields a Gröbner basis of $`:x_1^{\mathrm{}}`$; in (ms:pc, , Prop. 5.1.11) this observation is attributed (without reference) to Bayer. In our case we do not only get a Pommaret basis but it also turns out that here $`^{\mathrm{sat}}=:x_1^{\mathrm{}}`$ (see the remarks below).

###### Proposition 18

Let $``$ be a Pommaret basis of the homogeneous ideal $``$ for a class respecting term order. We introduce the sets $`_1=\{h\mathrm{cls}h=1\}`$ and $`\overline{}_1=\{h/x_1^{\mathrm{deg}_{x_1}\mathrm{lt}_{}h}h_1\}`$. Then $`\overline{}=(_1)\overline{}_1`$ is a weak Pommaret basis of the saturation $`^{\mathrm{sat}}`$.

###### Proof

Recall that for terms of the same degree any class respecting term order coincides with the reverse lexicographic order. Hence of all terms in a generator $`h_1`$ the leading term $`\mathrm{lt}_{}h`$ has the lowest $`x_1`$-degree. This implies in particular that $`\overline{}_1`$ is well-defined and does not contain a generator of class $`1`$ anymore.

We first show that indeed $`\overline{}_1^{\mathrm{sat}}`$. Let $`d_1=\mathrm{max}_{h_1}\{\mathrm{deg}_{x_1}\mathrm{lt}_{}h\}`$ and $`\mathrm{\Delta }=d_1+\mathrm{max}_{h_1}\{\mathrm{deg}h\}\mathrm{min}_{h_1}\{\mathrm{deg}h\}`$. We claim that $`𝒫_\mathrm{\Delta }\overline{h}`$ for all $`\overline{h}\overline{}_1`$. Thus let $`x^\mu 𝒫_\mathrm{\Delta }`$ and choose $`k_0`$ such that $`x_1^k\overline{h}_1`$; obviously, we have $`kd_1`$. Since the polynomial $`x^\mu x_1^k\overline{h}`$ lies in $``$, it possesses an involutive standard representation of the form

$$x^\mu x_1^k\overline{h}=\underset{h_1}{}P_hh+\underset{h_1}{}Q_hh$$
(65)
with $`P_h𝕜[x_1,\mathrm{},x_{\mathrm{cls}h}]`$ and $`Q_h𝕜[x_1]`$.

The left hand side of this equation is contained in $`x_1^k`$ and thus also the right hand side. Analysing an involutive normal form computation leading to the representation (65), one immediately sees that this implies that all coefficients $`P_h`$ (since here $`\mathrm{cls}h>1`$) and all summands $`Q_hh`$ lie in $`x_1^k`$. As a first consequence of this representation we observe that for any monomial $`x^\mu `$ (not necessarily of degree $`\mathrm{\Delta }`$) we may divide (65) by $`x_1^k`$ and then obtain an involutive standard representation of $`x^\mu \overline{h}`$ with respect to the set $`\overline{}`$; hence this set is indeed weakly involutive for the Pommaret division and the given term order.

If $`x^\mu 𝒫_\mathrm{\Delta }`$, then we find for any $`h_1`$ that $`|\mathrm{deg}\overline{h}\mathrm{deg}h|\mathrm{\Delta }`$ and hence $`\mathrm{deg}Q_h=\mathrm{deg}\left(x^\mu x_1^k\overline{h}\right)\mathrm{deg}hk`$. Since $`Q_h𝕜[x_1]`$, this implies that under the made assumption on $`x^\mu `$ already the coefficient $`Q_h`$ lies in $`x_1^k`$ so that the product $`x^\mu \overline{h}`$ possesses an involutive standard representation with respect to $``$ and thus is contained in the ideal $``$ as claimed.

Now we show that every polynomial $`f^{\mathrm{sat}}`$ may be decomposed into an element of $``$ and a linear combination of elements of $`\overline{}_1`$. We may write $`f=\stackrel{~}{f}+g`$ where $`\stackrel{~}{f}`$ is the involutive normal form of $`f`$ with respect to $``$ and $`g`$. If $`\stackrel{~}{f}=0`$, then already $`f`$ and nothing is to be shown. Hence we assume that $`\stackrel{~}{f}0`$. By definition of the saturation $`^{\mathrm{sat}}`$, there exists a $`k_0`$ such that $`\stackrel{~}{f}𝒫_k`$, hence in particular $`x_1^k\stackrel{~}{f}`$. This implies that $`\mathrm{lt}_{}(x_1^k\stackrel{~}{f})\mathrm{lt}_{}_P`$. Therefore a unique generator $`h`$ exists with $`\mathrm{lt}_{}h|_P\mathrm{lt}_{}(x_1^k\stackrel{~}{f})`$.

So let $`\mathrm{lt}_{}(x_1^k\stackrel{~}{f})=x^\mu \mathrm{lt}_{}h`$ and assume first that $`\mathrm{cls}h>1`$. Since the term on the left hand side is contained in $`x_1^k`$, we must have $`\mu _1k`$ so that we can divide by $`x_1^k`$. But this implies that already $`\mathrm{lt}_{}\stackrel{~}{f}\mathrm{lt}_{}_P`$ contradicting our assumption that $`\stackrel{~}{f}`$ is in involutive normal form. Hence we must have $`\mathrm{cls}h=1`$ and by the same argument as above $`\mu _1<k`$.

Division by $`x_1^k`$ shows that $`\mathrm{lt}_{}\stackrel{~}{f}\mathrm{lt}_{}\overline{}_1_P`$. Performing the corresponding involutive reduction leads to a new element $`f_1^{\mathrm{sat}}`$. We compute again its involutive normal form $`\stackrel{~}{f}_1`$ and apply the same argument as above, if $`\stackrel{~}{f}_10`$. After a finite number of such reductions we obtain an involutive standard representation of $`f`$ with respect to the set $`\overline{}`$ proving our assertion.∎

By Proposition 5.7 of Part I, an involutive head autoreduction of the set $`\overline{}`$ yields a strong Pommaret basis for the saturation $`^{\mathrm{sat}}`$. As a trivial consequence of the considerations in the proof above we find that in $`\delta `$-regular coordinates $`^{\mathrm{sat}}`$ is simply given by the quotient $`:x_1^{\mathrm{}}`$ (in the monomial case this also follows immediately from Proposition 13 (iv)). This observation in turn implies that for degrees $`q\mathrm{deg}_1`$ we have $`_q=_q^{\mathrm{sat}}`$. Hence all ideals with the same saturation possess also the same Hilbert polynomial and become identical for sufficiently high degrees; $`^{\mathrm{sat}}`$ is the largest among all these ideals. The smallest value $`q_0`$ such that $`_q=_q^{\mathrm{sat}}`$ for all $`qq_0`$ is often called the *satiety* $`\mathrm{sat}`$ of the ideal $``$.

###### Corollary 13

Let $``$ be a Pommaret basis of the ideal $`𝒫`$. Then $``$ is saturated, if and only if $`_1=\mathrm{}`$. If $``$ is not saturated, then $`\mathrm{sat}=\mathrm{deg}_1`$. Independent of the existence of a Pommaret basis, we have for any homogeneous generating set $``$ of the socle $`:𝒫_+`$ the equality

$$\mathrm{sat}=1+\mathrm{max}\{\mathrm{deg}fff\}.$$
(66)
###### Proof

Except of the last statement, everything has already been proven in the discussion above. For its proof we may assume without loss of generality that the coordinates are $`\delta `$-regular so that a Pommaret basis $``$ of $``$ exists, as all quantities appearing in (66) are invariant under linear coordinate transformations.

Let $`\stackrel{~}{h}`$ be an element of $`_1`$ having maximal degree. We claim that then $`\stackrel{~}{h}/x_1(:𝒫_+)`$. Indeed, since $`x_1`$ is always multiplicative for the Pommaret division, we cannot have $`\stackrel{~}{h}/x_1`$ (otherwise $``$ would not be involutively head autoreduced), and if we analyse for any $`1<\mathrm{}n`$ the involutive standard representation of $`x_{\mathrm{}}\stackrel{~}{h}`$, then all coefficients of generators $`h_1`$ are trivially contained in $`x_1`$ and for the coefficients of elements $`h_1`$ the same holds for degree reasons. Hence we can divide by $`x_1`$ and find that $`x_{\mathrm{}}\stackrel{~}{h}/x_1`$ for all $`1\mathrm{}n`$ implying $`\stackrel{~}{h}/x_1:𝒫_+`$.

By our previous results, $`\mathrm{sat}=\mathrm{deg}\stackrel{~}{h}`$. By assumption, homogeneous polynomials $`P_f𝒫`$ exist such that $`\stackrel{~}{h}/x_1=_fP_ff`$. If $`\mathrm{deg}P_f1`$, then $`P_ff`$ since $`f:𝒫_+`$. Hence for at least one $`\stackrel{~}{f}`$, the coefficient $`P_{\stackrel{~}{f}}`$ must be a non-zero constant and thus $`\mathrm{deg}\stackrel{~}{f}=\mathrm{sat}1`$.∎

###### Remark 15

The last statement in Corollary 13 is due to Bermejo and Gimenez (bg:scmr, , Prop. 2.1) who proved it in a slightly different way. For *monomial* ideals $``$, one obtains as further corollary (bg:scmr, , Cor. 2.4) that, if $`:𝒫_+=:x_1`$, then $`\mathrm{sat}`$ is the maximal degree of a minimal generator of $``$ divisible by $`x_1`$ (this observation generalises a classical result about Borel-fixed ideals (mlg:gin, , Cor. 2.10)). If the considered ideal $``$ possesses a Pommaret basis $``$, this statement also follows from the fact that under the made assumptions all elements of $`_1`$ are minimal generators. Indeed, suppose to the contrary that $`_1`$ contains two elements $`h_1h_2`$ such that $`h_1h_2`$. Obviously, the minimality implies $`\mathrm{deg}_{x_1}h_1=\mathrm{deg}_{x_1}h_2`$ and a non-multiplicative index $`1<\mathrm{}n`$ exists such that $`x_{\mathrm{}}h_1h_2`$. Without loss of generality, we may assume that $`h_2=x_{\mathrm{}}h_1`$. But this immediately entails that $`x_{\mathrm{}}h_1/x_1=h_2/x_1`$ and hence $`h_1/x_1(:x_1)(:𝒫_+)`$. $``$

A first trivial consequence of our results is the following well-known formula relating Castelnuovo-Mumford regularity and saturation.

###### Corollary 14

Let $`𝒫`$ be an ideal. Then $`\mathrm{reg}=\mathrm{max}\{\mathrm{sat},\mathrm{reg}^{\mathrm{sat}}\}`$.

###### Proof

Without loss of generality, we may assume that we use $`\delta `$-regular coordinates so that $``$ possesses a Pommaret basis $``$ with respect to the degree reverse lexicographic order. Now the statement follows immediately from Proposition 18 and Corollary 13.∎

Trung ngt:cmr  proposed the following approach for computing the regularity of a monomial ideal $``$ based on evaluations. Let $`D=dim(𝒫/)`$ and introduce for $`j=0,\mathrm{},D`$ the polynomial subrings161616Compared with Trung ngt:cmr , we revert as usual the order of the variables in order to be consistent with our conventions. $`𝒫^{(j)}=𝕜[x_{j+1},\mathrm{},x_n]`$ and within them the elimination ideals $`^{(j)}=𝒫^{(j)}`$ and their saturations $`\stackrel{~}{}^{(j)}=^{(j)}:x_{j+1}^{\mathrm{}}`$. A basis of $`^{(j)}`$ is obtained by setting $`x_1=\mathrm{}=x_j=0`$ in a basis of $``$ and for a basis of $`\stackrel{~}{}^{(j)}`$ we must additionally set $`x_{j+1}=1`$. Now define the numbers

$`c_j`$ $`=sup\{q(\stackrel{~}{}^{(j)}/^{(j)})_q0\}+1,0j<D`$ (67a)
$`c_D`$ $`=sup\{q(𝒫^{(D)}/^{(D)})_q0\}+1.`$ (67b)
Trung ngt:cmr  proved that whenever none of these numbers is infinite, then their maximum is just $`\mathrm{reg}`$. We show now that this genericity condition is satisfied, if and only if the coordinates are $`\delta `$-regular and express the numbers $`c_j`$ as satieties.

###### Theorem 10.1

The numbers $`c_0,\mathrm{},c_D`$ are all finite, if and only if the monomial ideal $`𝒫`$ is quasi-stable. In this case $`c_j=\mathrm{sat}^{(j)}`$ for $`0jD`$ and

$$\mathrm{max}\{c_0,\mathrm{},c_D\}=\mathrm{reg}.$$
(68)
If $`d=\mathrm{depth}`$, then it suffices to consider $`c_d,\mathrm{},c_D`$.

###### Proof

We assume first that $``$ is quasi-stable and thus possesses a Pommaret basis which we write $`=\{h_{k,\mathrm{}}1kn,1\mathrm{}\mathrm{}_k\}`$ where $`\mathrm{cls}h_{k,\mathrm{}}=k`$. One easily verifies that the subset $`^{(j)}=\{h_{k,\mathrm{}}k>j\}`$ is the Pommaret basis of the ideal $`^{(j)}`$. If we set $`a_{k,\mathrm{}}=\mathrm{deg}_{x_k}h_{k,\mathrm{}}`$, then the Pommaret basis of $`\stackrel{~}{}^{(j)}`$ is $`\stackrel{~}{}^{(j)}=^{(j+1)}\{h_{j+1,\mathrm{}}/x_{j+1}^{a_{j+1,\mathrm{}}}1\mathrm{}\mathrm{}_{j+1}\}`$. This immediately implies that $`c_j=\mathrm{max}\left\{\mathrm{deg}h_{j+1,\mathrm{}}1\mathrm{}\mathrm{}_{j+1}\right\}`$. By construction, $`dim(𝒫^{(D)}/^{(D)})=0`$ and Proposition 11 entails that for $`\widehat{q}=\mathrm{deg}^{(D)}`$ the equality $`_{\widehat{q}}^{(D)}=𝒫_{\widehat{q}}^{(D)}`$ holds. Hence $`c_D=\widehat{q}`$ (it is not possible that $`c_D<\widehat{q}`$, as otherwise the set $``$ was not involutively autoreduced).

Thus we find that $`\mathrm{max}\{c_0,\mathrm{},c_D\}=\mathrm{deg}`$ and Theorem 9.1 yields (68). Furthermore, it follows immediately from Corollary 13 and Proposition 11, respectively, that $`c_j=\mathrm{sat}^{(j)}`$ for $`0jD`$. Finally, Proposition 4 entails that the values $`c_0,\mathrm{},c_{d1}`$ vanish.

Now assume that the ideal $``$ was not quasi-stable. By Part (ii) of Proposition 13 this entails that for some $`0j<D`$ the variable $`x_{j+1}`$ is a zero divisor in the ring $`𝒫/,x_1,\mathrm{},x_j^{\mathrm{sat}}𝒫^{(j)}/(^{(j)})^{\mathrm{sat}}`$. Thus a polynomial $`f(^{(j)})^{\mathrm{sat}}`$ exists for which $`x_{j+1}f(^{(j)})^{\mathrm{sat}}`$ which means that we can find for any sufficiently large degree $`q0`$ a polynomial $`g𝒫^{(j)}`$ with $`\mathrm{deg}g=q\mathrm{deg}f`$ such that $`fg^{(j)}`$ but $`x_{j+1}fg^{(j)}`$. Hence the equivalence class of $`fg`$ is a non-vanishing element of $`(\stackrel{~}{}^{(j)}/^{(j)})_q`$ so that for a not quasi-stable ideal $``$ at least one value $`c_j`$ is not finite. ∎

One direction of the proof above uses the same idea as the one of Theorem 9.1: the Castelnuovo-Mumford regularity is determined by the basis members of maximal degree and their classes give us the positions in the minimal resolution where it is attained (recall Remark 12; here these are simply the indices $`j`$ for which $`c_j`$ is maximal). However, while Theorem 9.1 holds for arbitrary homogeneous ideals, Trung’s approach can only be applied to monomial ideals. The formulation using satieties is at the heart of the method of Bermejo and Gimenez bg:scmr  to compute the Castelnuovo-Mumford regularity. Similar considerations yield an alternative proof of the following result of Bermejo and Gimenez (bg:scmr, , Cor. 17) for monomial ideals.

###### Proposition 19

Let $`𝒫`$ be a quasi-stable ideal and $`=𝒥_1\mathrm{}𝒥_r`$ its unique irredundant decomposition into irreducible monomial ideals. Then the equality $`\mathrm{reg}=\mathrm{max}\{\mathrm{reg}𝒥_1,\mathrm{},\mathrm{reg}𝒥_r\}`$ holds.

###### Proof

We first note that the Castelnuovo-Mumford regularity of a monomial irreducible ideal $`𝒥=x_{i_1}^\mathrm{}_1,\mathrm{},x_{i_k}^\mathrm{}_k`$ is easily determined using the considerations in Example 2.12 of Part I. There we showed that any such ideal becomes quasi-stable after a simple renumbering of the variables and explicitly gave its Pommaret basis. Up to the renumbering, the unique element of maximal degree in this Pommaret basis is the term $`x_{i_1}^\mathrm{}_1x_{i_2}^{\mathrm{}_21}\mathrm{}x_{i_k}^{\mathrm{}_k1}`$ and thus it follows from Theorem 9.1 that $`\mathrm{reg}𝒥=_{j=1}^k\mathrm{}_jk+1`$.

Recall from Proposition 9 that an irreducible decomposition can be constructed via standard pairs. As discussed in Section 3, the decomposition (13) is in general redundant; among all standard pairs $`(\nu ,N_\nu )`$ with $`N_\nu =N`$ for some given set $`N`$ only those exponents $`\nu `$ which are maximal with respect to divisibility appear in the irredundant decomposition and thus are relevant.

If we now determine the standard pairs of $``$ from a Pommaret basis according to Remark 5, then we must distinguish two cases. We have first the standard pairs coming from the terms $`x^\mu `$ of degree $`q=\mathrm{deg}`$ not lying in $``$. They are of the form $`(x^\nu ,\{x_1,\mathrm{},x_k\})`$ where $`k=\mathrm{cls}\mu `$ and $`x^\nu =x^\mu /x_k^{\mu _k}`$. By Proposition 9, each such standard pair leads to the irreducible ideal $`𝒥=x_{\mathrm{}}^{\nu _{\mathrm{}}+1}k<\mathrm{}n`$. By the remarks above, $`\mathrm{reg}𝒥=|\nu |+1|\mu |=q=\mathrm{reg}`$.

The other standard pairs come from the terms $`x^\nu `$ with $`|\nu |<q`$. It is easy to see that among these the relevant ones correspond one-to-one to the “end points” of the monomial completion process: we call an element of the Pommaret basis $``$ of $``$ an end point, if each non-multiplicative multiple of it has a *proper* involutive divisor in the basis (and thus one branch of the completion process ends with this element171717Note that an end point may very well be a member of the minimal basis of $``$!). If $`x^\mu `$ is such an end point, then the corresponding standard pair consists of the monomial $`x^\nu =x^\mu /x_k`$ where $`k=\mathrm{cls}\mu `$ and the empty set and it yields the irreducible ideal $`𝒥=x_{\mathrm{}}^{\nu _{\mathrm{}}+1}1\mathrm{}n`$. Thus we find again $`\mathrm{reg}𝒥=|\nu |+1=|\mu |q=\mathrm{reg}`$.

This proves the estimate $`\mathrm{reg}\mathrm{max}\{\mathrm{reg}𝒥_1,\mathrm{},\mathrm{reg}𝒥_r\}`$. The claimed equality follows from the observation that any element of degree $`q`$ in $``$ must trivially be an end point and the corresponding standard pair yields then an irreducible ideal $`𝒥`$ with $`\mathrm{reg}𝒥=q`$.∎

The question of bounding the Castelnuovo-Mumford regularity of a homogeneous ideal $``$ in terms of the degree $`q`$ of an arbitrary generating set has attracted quite some interest. Hermann gh:endl  gave already very early a doubly exponential bound; much later Mayr and Meyer mm:word  showed with explicit examples that this bound is indeed sharp (see bm:cac  for a more detailed discussion).

For monomial ideals $``$ the situation is much more favourable. It follows immediately from Taylor’s explicit resolution of such ideals dt:res  (see wms:taylor  for a derivation via Gröbner bases) that here a *linear* bound

$$\mathrm{reg}n(q1)+1$$
(69)
holds where $`n`$ is again the number of variables. Indeed, this resolution is supported by the $`\mathrm{lcm}`$-lattice of the given basis and the degree of its $`k`$th term is thus trivially bounded by $`kq`$. By Hilbert’s Syzygy Theorem, it suffices to consider the first $`n`$ terms which immediately yields the above bound. If the ideal $``$ is even quasi-stable, a simple corollary to Proposition 19 yields an improved bound using the minimal generators of $``$.

###### Corollary 15

Let the monomials $`m_1,\mathrm{},m_r`$ be the minimal generators of the quasi-stable ideal $`𝕜[x_1,\mathrm{},x_n]`$. If we set $`x^\lambda =\mathrm{lcm}(m_1,\mathrm{},m_r)`$ and $`d=\mathrm{min}\{\mathrm{cls}m_1,\mathrm{},\mathrm{cls}m_r\}`$ (i. e. $`d=\mathrm{depth}`$), then the Castelnuovo–Mumford regularity of $``$ satisfies the estimate

$$\mathrm{reg}|\lambda |+dn$$
(70)
and this bound is sharp.

###### Proof

Applying repeatedly the rule $`,t_1t_2=,t_1,t_2`$ for arbitrary generating sets $``$ and coprime monomials $`t_1`$, $`t_2`$, one obtains an irreducible decomposition of $``$. Obviously, in the worst case one of the irreducible ideals is $`𝒥=x_d^{\lambda _d},\mathrm{},x_n^{\lambda _n}`$. As we already know that $`\mathrm{reg}𝒥=|\lambda |+dn`$, this value bounds $`\mathrm{reg}`$ by Proposition 19.∎

###### Remark 16

An alternative direct proof of the corollary goes as follows. Let $``$ be the Pommaret basis of $``$. We claim that each generator $`x^\mu `$ with $`\mathrm{cls}\mu =k`$ satisfies $`\mu _k\lambda _k`$ and $`\mu _j<\lambda _j`$ for all $`j>k`$. The estimate for $`\mu _k`$ is obvious, as it follows immediately from our completion algorithm that there is a minimal generator $`x^\nu x^\mu `$ with $`\nu _k=\mu _k`$.

Assume for a contradiction that the Pommaret basis $``$ contains a generator $`x^\mu `$ where $`\mu _j>\lambda _j`$ for some $`j>\mathrm{cls}\mu `$. If several such generators exist for the same value $`j`$, choose one for which $`\mu _j`$ is maximal. Obviously, $`j`$ is non-multiplicative for $`x^\mu `$ and hence the multiple $`x_jx^\mu `$ must contain an involutive divisor $`x^\nu `$. Because of our maximality assumption $`\nu _j\mu _j`$ and hence $`j`$ must be multiplicative for $`x^\nu `$ so that $`\mathrm{cls}\nu j`$. But this fact trivially implies that $`x^\nu |_Px^\mu `$ contradicting that $``$ is by definition involutively autoreduced.

Now the assertion follows immediately: under the made assumptions $`\mathrm{cls}\lambda =d`$ and in the worst case $``$ contains the generator $`x_d^{\lambda _d}x_{d+1}^{\lambda _{d+1}1}\mathrm{}x_n^{\lambda _n1}`$ which is of degree $`|\lambda |+dn`$. $``$

###### Remark 17

The same arguments together with Proposition 18 also yield immediately a bound for the satiety of a quasi-stable ideal $``$. As already mentioned above, a quasi-stable ideal is not saturated, if and only if $`d=1`$. In this case, we have trivially $`\mathrm{sat}|\lambda |+1n`$. Again the bound is sharp, as shown by exactly the same class of irreducible ideals as considered above.

The estimate (70) also follows immediately from the results in bg:scmr . Yet another derivation is contained in ah:hilser . $``$

If one insists on having an estimate involving only the maximal degree $`q`$ of the minimal generators and the depth, then the above result yields immediately the following estimate, variations of which appear in aa:reg ; cs:reg ; mc:reg .

###### Corollary 16

Let $`𝒫`$ be a quasi-stable ideal minimally generated in degrees less than or equal to $`q`$. If $`\mathrm{depth}=d`$, then

$$q\mathrm{reg}(nd+1)(q1)+1$$
(71)
and both bounds are sharp.

###### Proof

Under the made assumptions we trivially find that the degree of the least common multiple of the minimal generators is bounded by $`|\lambda |(nd+1)q`$. Now (71) follows immediately from (70). The upper bound is realised by the irreducible ideal $`=x_1^q,\mathrm{},x_n^q`$. The lower bound is attained, if $``$ is even stable, as then Proposition 16 implies that $`\mathrm{reg}=q`$ independent of $`\mathrm{depth}`$.∎

###### Remark 18

Eisenbud, Reeves and Totaro ert:veronese  presented a variation of the estimate (71). They introduced the notion of $`s`$-stability as a generalisation of stability: let $`s1`$ be an integer; a monomial ideal $``$ is $`s`$-stable, if for every monomial $`x^\mu `$ and every index $`nj>\mathrm{cls}\mu =k`$ an exponent $`1es`$ exists such that $`x^{\mu e_k+e_j}`$. Then it is easy to see that for an $`s`$-stable ideal generated in degrees less than or equal to $`q`$ the estimate

$$\mathrm{reg}q+(n1)(s1)$$
(72)
holds, as $`_{q+(n1)(s1)}`$ is stable (thus any $`s`$-stable ideal is trivially quasi-stable). However, in general this is an overestimate, as it based on the assumption that $``$ possesses a minimal generator of class $`1`$ and degree $`q`$ which must be multiplied by $`x_2^{s1}x_3^{s1}\mathrm{}x_n^{s1}`$ in order to reach a stable set.

Thus for the $`8`$-stable ideal $`x^8,y^8,z^8`$ the estimate is indeed sharp (this is exactly the same worst case as in the proof above for an ideal of depth $`1`$); the Pommaret basis contains as maximal degree element the monomial $`x^8y^7z^7`$. On the other hand, for the also $`8`$-stable ideal $`x^6,x^2y^4,x^2z^4,y^8,z^8`$ the regularity is only $`16`$, as now the maximal degree element of the Pommaret basis is $`x^2y^7z^7`$. $``$

Finally, we recall that, given two quasi-stable ideals $`,𝒥𝒫`$ and their respective Pommaret bases, we explicitly constructed in Remarks 2.9 and 6.5, respectively, of Part I weak Pommaret bases for the sum $`+𝒥`$, the product $`𝒥`$ and the intersection $`𝒥`$. They lead to the following estimates for the regularity of these ideals which were recently also given by Cimpoeaş mc:borel ; mc:stable .

###### Proposition 20

Let $`,𝒥𝒫`$ be two quasi-stable ideals. Then the following three estimates hold:

$`\mathrm{reg}(+𝒥)`$ $``$ $`\mathrm{max}\{\mathrm{reg},\mathrm{reg}𝒥\},`$ (73a)
$`\mathrm{reg}(𝒥)`$ $``$ $`\mathrm{reg}+\mathrm{reg}𝒥,`$ (73b)
$`\mathrm{reg}(𝒥)`$ $``$ $`\mathrm{max}\{\mathrm{reg},\mathrm{reg}𝒥\}.`$ (73c)
###### Proof

The first two estimates follow immediately from the weak Pommaret bases given in the above mentioned remarks and Theorem 9.1. For the last estimate the weak Pommaret basis constructed in Remark 6.5 of Part I is not good enough; it would also yield $`\mathrm{reg}+\mathrm{reg}𝒥`$ as upper bound. However, Lemma 1 allows us to improve it significantly. Let $`𝒢`$ be the Pommaret basis of $``$ and $``$ the one of $`𝒥`$. If we set $`q=\mathrm{max}\{\mathrm{deg}𝒢,\mathrm{deg}\}`$, then one easily sees that $`𝒢_q_q`$ is the Pommaret basis of $`(𝒥)_q`$. Hence, the intersection $`𝒥`$ possesses a Pommaret basis of degree at most $`q`$.∎

## 11 Iterated Polynomial Algebras of Solvable Type

In Section 11 of Part I we studied involutive bases in polynomial algebras of solvable type over rings. We had to substitute the notion of an involutively head autoreduced set by the more comprehensive concept of an involutively $``$-saturated set. In a certain sense this was not completely satisfying, as we had to resort here to classical Gröbner techniques, namely computing normal forms of ideal elements arising from syzygies. Using the syzygy theory developed in Section 5, we provide now an alternative approach for the special case that the coefficient ring $``$ is again a polynomial algebra of solvable type (over a field). It is obvious that in this case left ideal membership in $``$ can be decided algorithmically and by Theorem 5.1 it is also possible to construct algorithmically a basis of the syzygy module.

###### Remark 19

In Section 5 we only considered the ordinary commutative polynomial ring, whereas now we return to general polynomial algebras of solvable type (over a field). However, it is easy to see that all the arguments in the proof of the involutive Schreyer Theorem 5.1 depend only on normal form computations and on considerations concerning the leading exponents. The same holds for the classical Schreyer theorem, as one may easily check (see also vl:ade ; vl:diss  for a non-commutative version). Thus the in the sequel crucial Theorem 5.1 remains valid in the general case of non-commutative polynomial algebras. $``$

We use the following notations in this section: $`=(𝕜[y_1,\mathrm{},y_m],,_y)`$ and $`𝒫=([x_1,\mathrm{},x_n],,_x)`$. Furthermore, we are given an involutive division $`L_y`$ on $`_0^m`$ and a division $`L_x`$ on $`_0^n`$. For simplicity, we always assume in the sequel that at least $`L_y`$ is Noetherian. In order to obtain a reasonable theory, we make similar assumptions as in Section 11 of Part I: both $``$ and $`𝒫`$ are solvable algebras with centred commutation relations so that both are (left) Noetherian.

We now propose an alternative algorithm for the involutive $``$-saturation. Until Line /13/ it is identical with Algorithm 6 of Part I; afterwards we perform an involutive completion and multiply in Line /17/ each polynomial in $`\overline{}_{f,L_x}^{}`$ by the non-multiplicative variables of its leading coefficient. In the determination of involutive normal forms, we may multiply each polynomial $`h^{}^{}`$ only by monomials $`rx^\mu `$ such that $`x^\mu [X_{L_x,^{},_x}(h^{})]`$ *and* $`r𝕜\left[Y_{L_y,\mathrm{lc}__x(\overline{}_{h^{},L_x}^{}),_y}(\mathrm{lc}__xh^{})\right]`$.

###### Proposition 21

Let $`L_y`$ be a Noetherian constructive division. Algorithm 1 terminates for any input $``$ with an involutively $``$-saturated and head autoreduced set $``$ such that $`=`$. Furthermore, the sets $`\mathrm{lc}__x\overline{}_{h,L_x}`$ form weak $`L_y`$-involutive bases of the $``$-ideals generated by them for each $`h`$.

###### Proof

The termination criterion in Line /26/ is equivalent to local involution of all the sets $`\mathrm{lc}__x\overline{}_{f,L_x}^{}`$. Under the made assumptions on the division $`L_y`$ and because of the fact that $`𝒫`$ is Noetherian, the termination of the algorithm and the assertion about these sets is obvious. In general we only obtain weak involutive bases, as no involutive head autoreductions of these sets are performed. The correctness is a consequence of Theorem 5.1: by analysing all non-multiplicative products we have taken into account a whole basis of the syzygy module $`\mathrm{Syz}(\mathrm{lc}__x\overline{}_{f,L_x}^{})`$. Thus the output $``$ is indeed involutively $``$-saturated.∎

###### Theorem 11.1

Let $`𝒫`$ satisfy the made assumptions and $`L_x`$ be a Noetherian division. If in Algorithm 3 of Part I the subalgorithm $`\mathrm{𝙸𝚗𝚟𝙷𝚎𝚊𝚍𝙰𝚞𝚝𝚘𝚁𝚎𝚍𝚞𝚌𝚎}_{L_x,_x}`$ is substituted by Algorithm 1, then the completion will terminate with a weak involutive basis of $`=`$ for any finite input set $`𝒫`$ such that the monoid ideal $`\mathrm{le}__x`$ possesses a weak involutive basis. Furthermore, the sets $`\mathrm{lc}__x\overline{}_{h,L_x}`$ form strong $`L_y`$-involutive bases of the $``$-ideals generated by them for each $`h`$.

###### Proof

The proof of the termination and of the correctness of the algorithm is as in Part I. The only new claim is that the sets $`\mathrm{lc}__x\overline{}_{h,L_x}`$ are strongly $`L_y`$-involutive. This is a simple consequence of the fact that under the made assumption on the product in $`𝒫`$ the loop in Lines /5-13/ of Algorithm 1 leads to an involutive head autoreduction of these sets. Hence we indeed obtain strong involutive bases. ∎

###### Corollary 17

If $`L_x`$ is the Janet division, then each polynomial $`f`$ possesses a unique involutive standard representation $`f=_hP_hh`$ where $`P_h𝕜[Y_{L_y,\mathrm{lc}__x(\overline{}_{h,L_x}),_y}(\mathrm{lc}__xh)][X_{L_x,,_x}(h)]`$.

###### Proof

For the Janet division the only obstruction for $``$ being a strong involutive basis is that some elements of it may have the same leading exponents. More precisely, for any $`h`$ we have $`_{h,L_x}=\{h^{}\mathrm{le}__xh^{}=\mathrm{le}__xh\}`$. This immediately implies furthermore $`\overline{}_{h,L_x}=_{h,L_x}`$. By Theorem 11.1 the sets $`\mathrm{lc}__x\overline{}_{h,L_x}`$ form a strong $`L_y`$-involutive basis of the ideals they generate. Hence the claimed representation must be unique.∎

## 12 Conclusions

$`\delta `$-regularity is often considered as a purely technical nuisance and a problem specific to the Pommaret division. Our results here lead to a more intricate picture. $`\delta `$-regularity of a given generating set in the sense of Definition 2 is indeed a technical concept appearing in the analysis of the termination of the completion Algorithm 3 of Part I. By contrast, $`\delta `$-regularity of an ideal in the sense of Definition 1 has an intrinsic meaning. This can already be seen from the simple fact that in the case of linear differential operators there is a close relation to characteristics (see any textbook on partial differential equations, e. g. jo:pde ; rr:intro ): a necessary condition for a coordinate system to be $`\delta `$-regular is that the hypersurface $`x_n=0`$ is non-characteristic. Indeed, the standard definition of a characteristic hypersurface may be rephrased that on it one cannot solve for all derivatives of class $`n`$.

We have also seen that $`\delta `$-regularity is related to many regularity concepts in commutative algebra and algebraic geometry. Many statements that are only generically true hold in $`\delta `$-regular coordinates. In particular, in $`\delta `$-regular coordinates many properties of an affine algebra $`𝒜=𝒫/`$ may already be read off the monomial algebra $`𝒜^{}=𝒫/\mathrm{lt}_{}`$ where $``$ is the degree reverse lexicographic order.

For example, it follows immediately from Proposition 12 that $`\mathrm{depth}𝒜=\mathrm{depth}𝒜^{}`$ and that $`(x_1,\mathrm{},x_d)`$ is a maximal regular sequence for both algebras. As in the homogeneous case it is also trivial that $`dim𝒜=dim𝒜^{}`$, we see that the algebra $`𝒜`$ is Cohen-Macaulay, if and only if $`𝒜^{}`$ is so. Similarly, it is an easy consequence of Theorem 8.3 that $`\mathrm{proj}\mathrm{dim}𝒜=\mathrm{proj}\mathrm{dim}𝒜^{}`$ and of Theorem 9.1 that $`\mathrm{reg}𝒜=\mathrm{reg}𝒜^{}`$. An exception are the Betti numbers where Example 13 shows that even in $`\delta `$-regular coordinates $`𝒜`$ and $`𝒜^{}`$ may have different ones.

These equalities are of course not new; they can already be found in bs:mreg  (some even in earlier references). However, one should note an important difference: Bayer and Stillman bs:mreg  work with the *generic initial ideal*, whereas we assume $`\delta `$-regularity of the coordinates. These are two different genericity concepts, as even in $`\delta `$-regular coordinates $`\mathrm{lt}_{}`$ is not necessarily the generic initial ideal (in contrast to the former, the latter is always Borel fixed).

When we proved in Corollary 11 and 12, respectively, the two inequalities $`\mathrm{proj}\mathrm{dim}𝒜\mathrm{proj}\mathrm{dim}𝒜^{}`$ and $`\mathrm{reg}\mathrm{reg}(\mathrm{lt}_{})`$ for arbitrary term orders $``$, we had to assume the existence of a Pommaret basis of $``$ for $``$. It is well-known that these inequalities remain true, if we drop this assumption (see for example the discussions in bm:cac ; bs:mreg ; bc:initial ). We included here our alternative proofs because of their great simplicity and they cover at least the generic case.

In view of these observations, it seems to be of interest for the structure analysis of polynomial modules to construct explicitly $`\delta `$-regular coordinates. The approaches presented in Sections 2 and 4 offer an alternative to the classical expensive methods like random or generic coordinates. For coordinate systems not too far away from $`\delta `$-regularity, they should be much more efficient and in particular destroy much less sparsity. Of course, one may also combine the random strategy with our criterion of $`\delta `$-singularity in order to ensure that the transformation has indeed resulted in a good coordinate system. We also note that $`\delta `$-regularity of the coordinates $`x_1,\mathrm{},x_n`$ for an ideal $``$ is equivalent to their quasi-regularity for the algebra $`𝒫/`$ in the sense of Serre (see his letter published as an appendix to the article gs:alg  by Guillemin and Sternberg) wms:delta .

As already mentioned, many of the results in Sections 68 are generalisations of the work of Eliahou and Kervaire ek:res . They considered exclusively the case of stable modules where we obtain a minimal resolution. If one analyses closely their proofs, it is not difficult to see that implicitly they introduce Pommaret bases and exploit some of their basic properties. Our proof of Theorem 8.2 appears so much simpler only because we have already shown all these properties in Part I. Furthermore, Eliahou and Kervaire did not realise that they constructed a syzygy resolution in Schreyer form. Hence they had to give a lengthy and rather messy proof that the complex $`(𝒮_{},\delta )`$ is exact, whereas in our approach this is immediate.

We rediscover all their complicated calculations in the proof of Theorem 7.1. But note that this explicit formula for the differential is needed neither for proving the minimality of the resolution nor for its construction, although the latter is of course simplified by it. Furthermore, the theory of involutive standard representations gives us a clear guideline how to proceed.

Our results strongly suggest a homological background of the Pommaret division. Indeed, most of the quantities like the depth or the Castelnuovo-Mumford regularity determined by the Pommaret basis of an ideal $``$ are of a homological nature; more precisely, they correspond to certain extremal points in the Betti diagram and thus come from the Koszul homology. It is a conjecture of us that knowledge of the Pommaret basis (for the degree reverse lexicographic term order) of $``$ is equivalent to knowing the full Koszul homology of $``$ and that it is possible to construct explicitly one from the other. In the special case of monomial ideals, Sahbi showed recently in his diploma thesis ms:dipl  how the Koszul homology of a quasi-stable ideal can be computed from the $`P`$-graph of its Pommaret basis.

The combination of Corollary 4 and Proposition 12 allows us to make some statements about the so-called *Stanley conjecture*. It concerns the minimal number of multiplicative variables for a generator in a Stanley decomposition. Following Apel (apel:stanley1, , Def. 1) and Herzog et al. hsy:stanley  we call this number the *Stanley depth* of the decomposition and for an ideal $`𝒫`$ the Stanley depth of the algebra $`𝒜=𝒫/`$, written $`\mathrm{sdepth}𝒜`$, is defined as the maximal Stanley depth of a complementary decomposition for $``$. In its simplest form the Stanley conjecture claims that we always have the inequality $`\mathrm{sdepth}𝒜\mathrm{depth}𝒜`$. Obviously, Corollary 4 together with Proposition 12 (plus the existence Theorem 2.2 for Pommaret bases) shows that this inequality holds for arbitrary ideals.

The rigorous formulation of the Stanley conjecture (rps:diophant, , Conj. 5.1) concerns monomial ideals and requires that all generators in the decomposition are again monomials. Furthermore, no variables transformation is allowed. Then our results only allow us to conclude that the Stanley conjecture is true for all quasi-stable ideals. Some further results on this question have been achieved by Apel apel:stanley1 ; apel:stanley2  with the help of a slightly different notion of involutive bases.181818apel:stanley1  considers the Stanley conjecture for the ideal $``$ itself instead of the factor algebra $`𝒜=𝒫/`$. Here it follows immediately from the definition of a Pommaret basis and Proposition 4 that the Stanley conjecture is true in its weak form for arbitrary polynomial ideals and in its strong form for all quasi-stable ideals.

Many of the results mentioned above are quite well-known for Borel-fixed ideals and thus for generic initial ideals. However, it appears that for many purposes it is not necessary to move to this highly special class of ideals; quasi-stable ideals which are easier to produce algorithmically share many of their properties. Thus it is not surprising that quasi-stable ideals have appeared under different names in quite a number of recent works in commutative algebra (e. g. bg:scmr ; cs:reg ; hpv:ext ).

The results presented in this article offer two heuristic explanations for the efficiency of the involutive completion algorithm already mentioned in Part I. The first one is that according to our proof of Theorem 5.1 the involutive algorithm automatically takes into account many instances of Buchberger’s two criteria for redundant $`S`$-polynomials. Whereas a naive implementation of Buchberger’s algorithm without these criteria fails already for rather small examples, a naive implementation of the involutive completion algorithm works reasonably for not too large examples.

The second explanation concerns Proposition 5. It is well-known that the so-called “Hilbert driven” Buchberger algorithm ct:hdba  is often very fast, but it requires a priori knowledge of the Hilbert polynomial. The involutive completion algorithm may also be interpreted as “Hilbert driven”. The assignment of the multiplicative variables defines at each iteration a trial Hilbert function. This trial function is the true Hilbert function, if and only if we have already reached an involutive basis; otherwise it yields too small values. For continuous divisions the analysis of the products of the generators with their non-multiplicative variables represents a simple check for the trial Hilbert function to be the true one.

While for many ideals the involutive approach is an interesting alternative for the construction of Gröbner bases, there exist some obvious cases where this is not the case. The first class are monomial ideals. Here any basis is already a Gröbner basis, whereas an involutive basis still has to be constructed. Another class are toric ideals where recent work by Blinkov and Gerdt bg:toric  showed that involutive bases are typically much larger than Gröbner bases. In both cases, the reason is that these ideals are rarely in general position and that hence Gröbner bases of a much lower degree than $`\mathrm{reg}`$ exist.

An interesting question is whether the results of this second part can be extended to the polynomial algebras of solvable type introduced in the first part. This is trivial only for the determination of Stanley decompositions, as they are defined as vector space isomorphisms and therefore do not feel the non-commutativity (note that we always have the commutative product $``$ on the right hand side of the defining equation (7) of a Stanley decomposition). Thus involutive bases are a valuable tool for computing Hilbert functions even in the non-commutative case. This also yields immediately the *Gelfand-Kirillov dimension* (mr:ncrings, , Sect. 8.1.11) as the degree of the Hilbert polynomial (only in the commutative case it always coincides with the Krull dimension). Some examples for such computations in the context of quantum groups (however, using Gröbner instead of involutive bases) may be found in bglc:quantum .

By contrast, our results on the depth and on the Castelnuovo-Mumford regularity rely on the fact that for commutative polynomials $`fx_j`$ implies that any term in $`f`$ is divisible by $`x_j`$. In a non-commutative algebra of solvable type we have the relations $`x_ix_j=c_{ij}x_ix_j+h_{ij}`$ and in general the polynomial $`h_{ij}`$ is not divisible by $`x_j`$.

For syzygies the situation is complicated, too. The proof of Theorem 5.1 is independent of the precise form of the multiplication and thus we may conclude that we can always construct at least a Gröbner basis of the syzygy module. Our proof of Theorem 5.2 relies mainly on normal form arguments that generalise. A minimal requirement is that the term order $`_{}`$ respects the multiplication $``$, as otherwise the theorem does not even make sense. Furthermore, we must be careful with all arguments involving multiplicative variables. We need that if $`x_i`$ and $`x_j`$ are both multiplicative for a generator, then $`x_ix_j=c_{ij}x_ix_j+h_{ij}`$ must also contain only multiplicative variables which will surely happen, if $`h_{ij}`$ depends only on variables $`x_k`$ with $`k\mathrm{max}\{i,j\}`$. This is for example the case for linear differential operators, so that we may conclude that Theorem 5.2 (and its consequences) remain true for the Weyl algebra and other rings of differential operators.

###### Example 15

Recall from Example 3.9 of Part I that the universal enveloping algebra of the Lie algebra $`𝔰𝔬(3)`$ is isomorphic to the ring $`(𝕜[x_1,x_2,x_3],)`$ with the product $``$ induced by the relations

$`x_1x_2`$ $`=x_1x_2,`$ $`x_2x_1`$ $`=x_1x_2x_3,`$ (74)
$`x_1x_3`$ $`=x_1x_3,`$ $`x_3x_1`$ $`=x_1x_3+x_2,`$
$`x_2x_3`$ $`=x_2x_3,`$ $`x_3x_2`$ $`=x_2x_3x_1.`$
Obviously $`x_1x_2x_3x_1`$, but the term $`x_3`$ is not divisible by $`x_1`$. It follows from the same relation that $`x_2x_1`$ depends on $`x_3`$ and thus the arguments on multiplicative variables required by our proof of Theorem 5.2 break down. $``$

## Appendix A Rees Decompositions à la Sturmfels-White

Sturmfels and White sw:comb  presented an algorithm for the effective construction of Rees decompositions (based on earlier works by Baclawski and Garsia bg:comb ). We show now that generically it yields a Pommaret basis. However, we believe that the involutive approach is much more efficient. It does not only allow us to avoid completely computations in factor algebras, using our results in Section 2 we obtain more easily and constructively the right coordinates whereas Sturmfels and White must rely on a probabilistic approach.

We introduce some additional notations. Let again $``$ be a finitely generated module over the ring $`𝒫=𝕜[x_1,\mathrm{},x_n]`$. The *annihilator* of an element $`\stackrel{}{f}`$ is $`\mathrm{Ann}(\stackrel{}{f})=\{g𝒫g\stackrel{}{f}=0\}`$. The $`𝕜`$-vector space $`Z_{}`$ is defined as the set $`Z_{}=\{\stackrel{}{f}\mathrm{Ann}(\stackrel{}{f})=x_1,\mathrm{},x_n\}`$. The approach of Sturmfels and White is based on the following fact which may be interpreted as their version of the concept of $`\delta `$-regularity.

###### Lemma 12

If $`Z_{}=0`$, there exists a non zero divisor $`y𝒫_1`$, i. e. $`y\stackrel{}{f}=0`$ implies $`\stackrel{}{f}=0`$ for all $`\stackrel{}{f}`$. Identifying $`𝒫_1`$ with $`𝕜^n`$, the set of all non zero divisors contains a Zariski open subset.

The Sturmfels-White Algorithm 2 computes a basis $`𝒴=\{y_1,\mathrm{},y_n\}`$ of $`𝒫_1`$ and a set $``$ of generators such that (as graded $`𝕜`$-vector spaces)

$$M\underset{\stackrel{}{h}}{}𝕜[y_1,\mathrm{},y_{\mathrm{cls}\stackrel{}{h}}]\stackrel{}{h}.$$
(75)
Here the class $`\mathrm{cls}\stackrel{}{h}`$ is automatically assigned in the course of the algorithm and not necessarily equal to the notion of class we introduced in the definition of the Pommaret division. Within this appendix, the latter one will be referred to as *coordinate class* $`\mathrm{ccls}_\stackrel{}{x}\stackrel{}{h}`$, since its definition depends on the chosen coordinates $`\stackrel{}{x}`$.

Whether the individual steps of Algorithm 2 can be made effective depends on how $``$ is given. If it is presented by generators and relations, as we always assume, one may use Gröbner bases; Sturmfels and White formulated their algorithm directly for this case. Note that they need repeated Gröbner bases calculations in order to perform algorithmically all the computations in factor modules. A further problem is to find the non zero divisors, as Lemma 12 only guarantees their existence but says nothing about their determination. Sturmfels and White proposed a probabilistic approach. As the non zero divisors contain a Zariski open subset of $`𝒫_1`$, random choice of an element of $`𝒫_1`$ yields one with probability $`1`$.

###### Theorem A.1

The Algorithm 2 terminates for any finitely generated polynomial module $``$ with a Rees decomposition.

For a proof we refer to bg:comb ; sw:comb  where also Lemma 12 is proved. We will show that generically the Sturmfels-White Algorithm 2 returns a Pommaret basis when applied to a submodule of a free module. We begin by studying the relation between the classes and the coordinate classes of the generators of a Rees decomposition determined with this algorithm.

###### Proposition 22

Let $``$ define a Rees decomposition of the form (75) for the submodule $`𝒫^r`$ with respect to the basis $`𝒴`$ of $`𝒫_1`$ and let $``$ and $`𝒴`$ be determined with the Sturmfels-White Algorithm 2. With respect to the basis $`𝒴`$ we have the inequalities $`\mathrm{cls}\stackrel{}{h}\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}`$ for all $`\stackrel{}{h}`$.

###### Proof

$`Z_{}=0`$ for a submodule $`𝒫^r`$. Thus Algorithm 2 produces no generators of class $`0`$. The coordinate class is always greater than $`0`$.

We follow step by step Algorithm 2. In the first iteration some non zero divisor $`y_1𝒫_1`$ is chosen and in the second iteration we must treat the factor module $`^{(1)}=/y_1`$. Now $`\stackrel{}{f}`$ represents an element of $`Z_{^{(1)}}`$, if and only if $`y_k\stackrel{}{f}y_1`$ for all $`k>1`$. Thus $`\mathrm{ccls}_\stackrel{}{y}(y_k\stackrel{}{f})=1`$ for all $`k>1`$ which is only possible if $`\mathrm{ccls}_\stackrel{}{y}\stackrel{}{f}=1`$.

If $`Z_{^{(1)}}0`$, Algorithm 2 proceeds with $`^{(2)}=^{(1)}/Z_{^{(1)}}`$. Now $`\stackrel{}{f}`$ represents an element of $`Z_{^{(2)}}`$, if and only if for all $`k>1`$ the product $`y_k\stackrel{}{f}`$ either is an element of $`y_1`$ or represents an element of $`Z_{^{(1)}}`$. In both cases this is only possible, if $`\mathrm{ccls}_\stackrel{}{y}\stackrel{}{f}=1`$. The same argument holds until $`Z_{^{(\mathrm{})}}=0`$ for some $`\mathrm{}`$. Thus all generators $`\stackrel{}{h}`$ to which Algorithm 2 assigns the class $`1`$ are divisible by $`y_1`$ and hence all their terms possess the coordinate class $`1`$.

The next module to consider is $`^{(\mathrm{}+1)}=^{(\mathrm{})}/y_2^{(\mathrm{})}`$. Proceeding as above we see that $`\stackrel{}{f}`$ represents an element of $`Z_{^{(\mathrm{}+1)}}`$, if and only if $`y_k\stackrel{}{f}y_2^{(\mathrm{})}`$ for all $`k>2`$ implying that $`\mathrm{ccls}_\stackrel{}{y}\stackrel{}{f}2`$. Using the same argument as above, we conclude that all generators of class $`2`$ according to the Sturmfels-White algorithm consist of terms with a coordinate class less than or equal to $`2`$. Following Algorithm 2 until the end we obtain the assertion, namely that $`\mathrm{cls}\stackrel{}{h}\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}`$ for all generators $`\stackrel{}{h}`$.∎

As it may happen that $`\mathrm{cls}\stackrel{}{h}>\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}`$ for some generator $`\stackrel{}{h}`$, the set $``$ is not necessarily a Pommaret basis. More precisely, the coordinates $`\stackrel{}{y}`$ are not necessarily $`\delta `$-regular for $``$. We show now similarly to the proof of Theorem 2.1 that we may always transform $`\stackrel{}{y}`$ into a $`\delta `$-regular coordinate system $`\stackrel{}{z}`$.

For simplicity, let us assume that only one generator $`\stackrel{}{h}`$ with $`\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}<\mathrm{cls}\stackrel{}{h}`$ exists and that $`\mathrm{cls}\stackrel{}{h}=2`$. Consider a coordinate transformation $`z_k=y_k`$ for $`k>1`$ and $`z_1=y_1+cy_2`$ where $`c𝕜`$ is chosen such that with respect to the new coordinates $`\mathrm{ccls}_\stackrel{}{z}\stackrel{}{h}=2`$. The possible values of $`c`$ form a Zariski open set in $`𝕜`$. By Lemma 12, the non zero divisors among which $`y_1`$ was chosen in Algorithm 2 contain a Zariski open subset of $`𝒫_1`$. Thus there exist values of $`c`$ such that both $`\mathrm{ccls}_\stackrel{}{z}\stackrel{}{h}=2`$ *and* $`z_1`$ is a non zero divisor.

As in the proof of Theorem 2.1, it is not difficult to show that this transformation increases the involutive size of the set $``$. Applying a finite number of similar changes of coordinates leads to a new basis $`𝒵`$ of $`𝒫_1`$ in which $`\mathrm{ccls}_\stackrel{}{z}\stackrel{}{h}=\mathrm{cls}\stackrel{}{h}`$. As we still have a Rees decomposition, $``$ is a Pommaret basis of $``$ and the coordinates $`\stackrel{}{z}`$ are $`\delta `$-regular. Obviously, the one-forms $`z_i`$ would have been valid choices for the non zero divisors in Algorithm 2. Thus we conclude that this algorithm may be used for the construction of Pommaret bases. The following proposition shows that in fact any Pommaret basis may be constructed this way.

###### Proposition 23

Let $``$ be a Pommaret basis of the submodule $`𝒫^r`$ with respect to the $`\delta `$-regular coordinates $`\stackrel{}{y}`$ and a class respecting term order $``$. The one-forms $`y_i`$ may be used as non zero divisors in Algorithm 2 and the there obtained generators $`\overline{\stackrel{}{h}}`$ satisfy $`\mathrm{cls}\overline{\stackrel{}{h}}=\mathrm{ccls}_\stackrel{}{y}\overline{\stackrel{}{h}}`$. They are $`𝕜`$-linear combinations of the elements of $``$; one may even use the elements of $``$ as generators.

###### Proof

The Pommaret basis $``$ defines a Rees decomposition

$$=\underset{\stackrel{}{h}}{}𝕜[y_1,\mathrm{},y_{\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}}]\stackrel{}{h}.$$
(76)
As in the proof of the Proposition 22, we follow step by step the Sturmfels-White Algorithm 2. Let $`^{(1)}=/y_1`$ and $`_1=\{\stackrel{}{h}\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}=1\}`$. The vector space $`Z_{^{(1)}}`$ is isomorphic to a subspace of the vector space freely generated by $`_1`$, as by Proposition 22 $`Z_{^{(1)}}`$ contains only elements with coordinate class $`1`$ and the only elements of $``$ of coordinate class $`1`$ which are not in $`y_1`$ are $`𝕜`$-linear combinations of the elements of $`_1`$.

Let $`\stackrel{}{h}_1`$ and $`k>1`$. We determine the involutive normal form of $`y_k\stackrel{}{h}`$ induced by (76). Every term in $`y_k\stackrel{}{h}`$ has coordinate class $`1`$, thus $`t=\mathrm{lt}_{}(y_k\stackrel{}{h})`$ satisfies $`\mathrm{ccls}_\stackrel{}{y}t=1`$. Since $``$ is a strong basis, there exists precisely one generator $`\stackrel{}{h}^{}`$ such that $`\mathrm{lt}_{}\stackrel{}{h}^{}|_Pt`$. If $`\mathrm{lt}_{}\stackrel{}{h}^{}=t`$, then $`\stackrel{}{h}^{}_1`$, as $``$ is class respecting. After the corresponding reduction step, the initial term of the result is still of coordinate class $`1`$. So the normal form of $`y_k\stackrel{}{h}`$ has the following structure

$$y_k\stackrel{}{h}=\underset{\stackrel{~}{\stackrel{}{h}}_1}{}c_{\stackrel{~}{\stackrel{}{h}}}\stackrel{~}{\stackrel{}{h}}+y_1\stackrel{}{f}$$
(77)
for some coefficients $`c_{\stackrel{~}{\stackrel{}{h}}}𝕜`$ and an element $`\stackrel{}{f}`$. The vector space $`Z_{^{(1)}}`$ is generated by those $`\stackrel{~}{\stackrel{}{h}}_1`$ where the first summand in (77) is zero; this includes all elements of $`_1`$ of maximal degree.

Thus if $`_1\mathrm{}`$, then $`Z_{^{(1)}}\mathrm{}`$. Algorithm 2 proceeds in this case with $`^{(2)}=^{(1)}/Z_{^{(1)}}`$. If $`dimZ_{^{(1)}}<|_1|`$, then $`Z_{^{(2)}}\mathrm{}`$. Algorithm 2 will iterate Line /14/, until all elements of $`_1`$ have been used up. When this stage is reached, $`Z_{^{(\mathrm{})}}=0`$. It follows from the direct sum in (76) that $`y_2`$ is a non zero divisor for $`^{(\mathrm{})}`$ and we may proceed with $`^{(\mathrm{}+1)}=^{(\mathrm{})}/y_2^{(\mathrm{})}`$.

Let $`_2=\{\stackrel{}{h}\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}=2\}`$. As above, $`Z_{^{(\mathrm{}+1)}}`$ is isomorphic to a subspace of the vector space freely generated by $`_2`$. There are some minor modifications in (77): the first sum is over all $`\stackrel{~}{\stackrel{}{h}}_2`$ and there are additional summands which vanish either modulo $`y_1`$ or modulo $`y_2^{(\mathrm{})}`$ or modulo some $`Z_{^{(i)}}`$ for $`1i\mathrm{}`$. Again Algorithm 2 will iterate line /14/, until all elements of $`_2`$ have been used up. The same argument may be repeated for $`y_3,\mathrm{},y_n`$.

Thus, Algorithm 2 terminates with a Rees decomposition (with respect to the basis $`𝒴𝒫_1`$) generated by $`\overline{}`$ where $`|\overline{}|=||`$ and where the elements $`\overline{\stackrel{}{h}}\overline{}`$ with $`\mathrm{cls}\overline{\stackrel{}{h}}=k`$ freely generate the same vector space as the elements $`\stackrel{}{h}`$ with $`\mathrm{ccls}_\stackrel{}{y}\stackrel{}{h}=k`$. We may even choose $`\overline{}=`$. In any case, $`\mathrm{cls}\overline{\stackrel{}{h}}=\mathrm{ccls}_\stackrel{}{y}\overline{\stackrel{}{h}}`$ and $`\overline{}`$ is a Pommaret basis of $``$.∎

###### Remark 20

Note the strong similarity between this proof and the proof of Proposition 4. This is not surprising, as the minimal class assigned by the algorithm is equal to $`\mathrm{depth}`$ sw:comb  and the basis $`𝒴`$ determined by Algorithm 2 is quasi-regular for the module $``$ in the sense of Serre (see the letter of Serre appended to gs:alg  or wms:spencer2 ). In fact, Lemma 12 follows immediately from the results of Serre. They imply furthermore that $`𝒵_{}`$ is always finite-dimensional and thus it is not really necessary to factor by $`𝒵_{}`$. In wms:spencer2  it is shown that coordinates are $`\delta `$-regular for the a submodule $`𝒫^r`$, if and only if they are quasi-regular for the factor module $`𝒫^r/`$. Thus in principle, one should always compare Algorithm 2 applied to $`𝒫^r/`$ with the Pommaret basis of $``$ (recall that the latter also leads immediately to a Rees decomposition of $`𝒫^r/`$ via Corollary 4). $``$

###### Acknowledgements.

The author would like to thank V.P. Gerdt for a number of interesting discussions on involutive bases. M. Hausdorf and R. Steinwandt participated in an informal seminar at Karlsruhe University where many ideas of this article were presented and gave many valuable comments. The constructive remarks of the anonymous referees were also very helpful. This work received partial financial support by Deutsche Forschungsgemeinschaft, INTAS grant 99-1222 and NEST-Adventure contract 5006 (*GIFT*).