PASSIVE COMPLETE ORTHONOMIC SYSTEMS OF PDES AND RIQUIER BASES OF POLYNOMIAL MODULES

JOACHIM APEL

Abstract. The object of this talk is to enlighten the relationship between the two classical theories of passive complete orthonomic systems of PDEs at the one hand side and Gröbner bases of finitely generated modules over polynomial rings at the other hand side. The link between both types of canonical forms are the Riquier bases (also called ‘involutive bases’ in the literature) which are both, a particular type of Gröbner bases which carry some additional structure and a natural translation of the notion of passive complete orthonomic systems of PDEs into the language of polynomial modules.

We will point out some desirable applications which a “good” notion of Riquier bases could provide. Unfortunately, these desires turn out to collide and we will discuss the problem of finding a reasonable compromise.

1. Introduction

Our objective is to discuss a general framework of Riquier bases of finitely generated modules over polynomial rings which at the one hand side still provides a uniform algorithmic treatment but at the other hand side includes useful instances for some natural applications.

First of all, we will shortly introduce the two major pillars of Riquier bases which consist in the passive complete orthonomic form of systems of partial differential equations (PDEs) and the Gröbner bases of polynomial modules. Passive complete orthonomic systems of PDEs are the main idea behind Riquier’s existence theorems (see [Ri10, Th29]) and the corresponding algorithms for solving systems of PDEs due to Janet (see [Ja29]). Gröbner bases and Buchberger’s algorithm for their computation (see [Bu65, Bu85]), nowadays, have countless applications in commutative and noncommutative algebra as well as in algebraic geometry. Moreover, due to their impact on solution methods for systems of differential and algebraic, respectively, equations both methods are fundamental for lots of applications in- and outside mathematics. Riquier’s and Buchberger’s theories are related to each other by the fact that the translation of the passive complete orthonomic form of systems of PDEs into the language of polynomial modules provides a particular type of Gröbner bases carrying an additional structure which can be roughly described by saying that in addition to the direct access to the initial module in_{≺}(M), which is characteristic for all Gröbner bases of a module M, a Riquier basis of M provides a decomposition of in_{≺}(M) in a certain direct sum of finitely many free modules.

Research at MSRI is supported in part by NSF grant DMS-9701755. Further, the author was supported by a research fellowship of the Deutsche Forschungsgemeinschaft (DFG).

Invited talk at the conference “Symbolic and Numerical Scientific Computation” (SNSC’01), Hagenberg/Linz (Austria), September 12–14, 2001.

The Riquier theory leaves some freedom in choosing the multipliers for each of the equations in order to complete an orthonomic system of PDEs (see Section 2). Depending on what application is concerned different ways of defining the sets of multipliers have been introduced in the past. Janet suggested a very sophisticated assignment rule leading to an efficient algorithm (see [Ja29]). In Section 6 we will explain the advantage of Janet’s assignments for algorithmic purposes but we will also show how to further improve them. The main objective of Thomas was to give a most elegant and easy understandable presentation of Riquier’s existence theorems. This aim is fulfilled best by concentrating on only the principal algorithmic aspects and disregarding any efficiency issues (see [Th29, Th37]). Yet another objective can be found in Pommaret’s coordinate free studies of systems of PDEs, where a multiplier notion optimal for systems of PDEs in generic coordinates is applied (see [Po78]).

The use of different multiplier notions for different applications was motivation for Gerdt and Blinkov (see [GB98])^{1} to think about a general framework for fixing the multipliers. In this talk we will discuss and motivate the ideas which stand behind the alternative concept introduced in [Ap98]^{2}. Sometimes the auditor might get the impression that the presented examples are not characteristic since many of them consider only the most simple case of monomial ideals. However, the situation is not much different for general modules M because after fixing an admissible term order ≺ the main algorithmic part takes place only in the initial module in_{≺}(M), which indeed is monomial. Also the second restriction to ideals is not essential. If M, and consequently also in_{≺}(M), are submodules of a module F of higher rank k then we can decompose in_{≺}(M) in a direct sum of k monomial submodules of modules of rank 1, i.e. ideals, and treat each of them separately.

2. Orthonomic Systems of Partial Differential Equations

Let x_{1}, …, x_{n} denote the independent variables, u_{1}, …, u_{k} the unknown functions and D the set of all differential operators of the form

\frac{∂^{i_{1}+···+i_{n}}}{∂x_{1}^{i_{1}} ⋯ ∂x_{n}^{i_{n}}} . (1)

Furthermore, let the set DU = {Du_{j} | D ∈ D, 1 ≤ j ≤ k} of all formal derivatives of the unknown functions by differential operators from D be ordered by a wellorder ≺ which is compatible with differentiation in the sense \frac{∂}{∂x_{i}} D_{1}u_{j_{1}} ≺ \frac{∂}{∂x_{i}} D_{2}u_{j_{2}} for all i ∈ {1, …, n} and D_{1}u_{j_{1}}, D_{2}u_{j_{2}} ∈ DU such that D_{1}u_{j_{1}} ≺ D_{2}u_{j_{2}}. Usually, the additional assumption that ≺ has to be compatible with the order of derivation is made.

1Note, Gerdt and Blinkov introduced the notion ‘involutive bases’ for the generating sets which we call Riquier bases in this paper.

2Following Gerdt and Blinkov the notion ‘involutive bases’ was used also in [Ap98]. Recently, the author replaced it by ‘Riquier bases’ (see [Ap01c]) since the original notion has a geometrical meaning in the theory of PDEs which has no interpretation in the general algebraic context, i.e.

including algebras of solvable type etc., where such bases can be considered.

Consider a system of finitely many partial differential equations which are all of the form

D_{i}u_{j_{i}} = G_{i} , (2)

where D_{i}u_{j_{i}} ∈ DU and G_{i} is a function of the independent variables and the derivatives which are less than D_{i}u_{j_{i}} with respect to ≺, and the left hand sides of the equations are pairwise distinct. Then we call Du_{j} ∈ DU a principal derivative of the system if it can be obtained by differentiation from the left hand side of one of the equations and we call it a parametric derivative of the system, otherwise. A system of PDEs is called orthonomic if it satisfies the above conditions, no right hand side contains any principal derivative, and each right hand side can be developed in a Taylor series in the region under consideration. Let us illustrate the notions introduced so far by an example.

Example 1 (Part 1). Consider the system

(3)  u_{xx} = yv_{x}
(4)  u_{yy} = −x^{2}u

of two partial differential equations in the unknown functions u = u(x, y) and v = v(x, y) in two independent variables x and y. As usual, subscripts at the unknown functions indicate partial derivatives, e.g. u_{xy} = \frac{∂^{2}}{∂x∂y}u. This system is in orthonomic form with respect to any order ≺ which is compatible with the order of derivation. Obviously, the right hand sides considered as functions in x, y and the occurring derivatives of u and v have Taylor series expansions everywhere. Since the derivatives at the right hand side of the equations are of lower order than the derivatives at the left hand side, the derivatives at the right hand side are smaller than the left hand sides with respect to ≺, in particular, no derivative at the right hand side can be obtained by differentiation of a left hand side.

All derivatives of v are parametric. The parametric derivatives of u are u, u_{x}, u_{y} and u_{xy}. The remaining derivatives of u are principal.

Let D_{1}u_{j_{1}} = G_{1} and D_{2}u_{j_{2}} = G_{2} be two equations of the system such that differentiation of the left hand sides by Δ_{1}, Δ_{2} ∈ D, respectively, leads to the same principal derivative Δ_{1}(D_{1}u_{j_{1}}) = Δ_{2}(D_{2}u_{j_{2}}). In particular we must have j_{1} = j_{2} and any solution of our system of PDEs has to satisfy also the equation Δ_{1}G_{1} −Δ_{2}G_{2} = 0 which is called an integrability condition for the system. The system is called passive if the left hand side of any of its integrability conditions becomes identical zero after replacement of all principal derivatives in an obvious way. In what follows by calling a system passive we will subsume that it is also orthonomic.

In general, replacing all principal derivatives in the left hand side of an integrability condition yields a function depending on the independent variables and the parametric derivatives. Obviously, the system of PDEs is incompatible if for some integrability condition this function is nonzero and depends only on the independent variables. If neither such an integrability condition exists nor the system is passive we can solve the nonzero integrability conditions for their highest derivative, write them in form 2 and add them to the system of PDEs. Repeating this process eventually we will produce a passive system or will encounter that the system is incompatible.

Example 1 (Part 2). Differentiating Equation (3) twice by y and Equation (4) twice by x yields the integrability condition

yv_{xyy} + 2v_{xy} + x^{2}u_{xx} + 4xu_{x} + 2u = 0

Replacing the principal derivative u_{xx} by the right hand side of Equation (3) yields

yv_{xyy} + 2v_{xy} + x^{2}yv_{x} + 4xu_{x} + 2u = 0 .

Hence, the system is neither passive nor proved to be incompatible. We solve the equation for the highest occurring derivative v_{xyy} and add the new equation

v_{xyy} = −2\frac{v_{xy} + 2xu_{x} + u}{y} − x^{2}v_{x} (5)

to our system. The system formed by Equations (3), (4) and (5) is passive since there are no further (essential) integrability conditions. For the new system we have

PR = \{ \frac{∂^{i+j}}{∂x^{i}∂y^{j}} u | i ≥ 2 or j ≥ 2\} ∪ \{ \frac{∂^{i+j}}{∂x^{i}∂y^{j}} v | i ≥ 1 and j ≥ 2\}
PA = \{u, \frac{∂}{∂x}u, \frac{∂}{∂y} u, \frac{∂^{2}}{∂x∂y} u, v\} ∪ \{ \frac{∂^{i}}{∂y^{i}} v, \frac{∂^{i}}{∂x^{i}} v, \frac{∂^{i+1}}{∂x^{i}∂y} v | i = 1, 2, … \}

The observation that any compatible system of PDEs can be transformed in passive orthonomic form is due to Tresse (see [Tr1894]). Riquier surpassed this result by showing that any system of this particular form has a unique holomorphic solution for arbitrary given initial determinations of a certain type prescribed by the system (see [Ri10]). Riquier’s result makes use of decompositions of each of the sets PR of principal and PA of parametric derivatives, and hence also of DU, in finitely many pairwise disjoint cones. Such a cone is given by its vertex which is a derivative Du_{j} ∈ DU and a subset Y ⊆ X, where Δ(Du_{j}) belongs to the cone iff Δ ∈ D is a differential operator involving only variables from Y. We will use the denotation [Du_{j}, Y] for this cone. The elements of Y are called the multipliers and the remaining independent variables the non-multipliers for Du_{j}. Such a decomposition of the set DU allows to prove the existence of a convergent power series solution for the unknown functions u_{j}, j ∈ {1, …, k}, at an arbitrary given point (x̂_{1}, …, x̂_{n}) ∈ ℂ^{n} belonging to a region where the system is orthonomic. The particular importance of the cones forming PA is the description of the initial determinations, more precisely, each cone [Du_{j}, Y] belonging to PA provides an initial condition of the form Du_{j}|_{∀x_{i}∉Y:x_{i}=x̂_{i}} = φ(y_{1}, …, y_{r}), where Y = {y_{1}, …, y_{r}} and φ can be chosen as an arbitrary holomorphic function. We will call an orthonomic system of PDEs complete if there exists a disjoint decomposition of PR into cones such that each vertex is the left hand side of an equation of the system, in the language of Thomas that is the left hand sides of the orthonomic system form a complete set (see [Th29]).

Example 1 (Part 3). We have the disjoint decompositions

PR = [u_{xx}, {x}] ∪ [u_{xxy}, {x}] ∪ [u_{yy}, {x, y}] ∪ [v_{xyy}, {x, y}]
PA = [u, ∅] ∪ [u_{x}, ∅] ∪ [u_{y}, ∅] ∪ [u_{xy}, ∅] ∪ [v, {y}] ∪ [v_{x}, {x}] ∪ [v_{xy}, {x}]

Hence, we can extend our system of PDEs to the passive complete form

u_{xx} = yv_{x}
u_{xxy} = yv_{xy} + v_{x}
u_{yy} = −x^{2}u
v_{xyy} = −2\frac{v_{xy} + 2xu_{x} + u}{y} − x^{2}v_{x} .

The system has a uniquely determined holomorphic solution for an arbitrary initial determination u|_{x=x_{0},y=y_{0}} = c_{1}, u_{x}|_{x=x_{0},y=y_{0}} = c_{2}, u_{y}|_{x=x_{0},y=y_{0}} = c_{3}, u_{xy}|_{x=x_{0},y=y_{0}} = c_{4}, v|_{x=x_{0}} = φ_{1}(y), v_{x}|_{y=y_{0}} = φ_{2}(x) and v_{xy}|_{y=y_{0}} = φ_{3}(x), where x_{0}, y_{0}, c_{1}, c_{2}, c_{3}, c_{4} are complex numbers, y_{0} ≠ 0, and φ_{1}, φ_{2}, φ_{3} are holomorphic functions.

Finally, there can be distinguished between two aspects of passive (complete) orthonomic systems of PDEs. Firstly, there is a dynamic aspect which consists in the algorithmic transformation of an arbitrary system of PDEs in passive (complete) orthonomic form. Secondly, there is a static aspect consisting in the determination of the solution space of a system of PDEs in passive (complete) orthonomic form. Janet was the first who investigated the dynamic part from the point of view of efficiency and a crucial property of his algorithm is that it directly computes a complete system of PDEs (see [Ja29]).

For an excellent overview on the basic ideas of the Riquier/Janet theory we refer to the article [Th29] by Joseph M. Thomas.

3. Gröbner Bases of Polynomial Modules

Let R = 𝕂[X] be the polynomial ring over the field 𝕂 in the variables X = {x_{1}, …, x_{n}}, F a free R-module of rank k with basis {e_{1}, …, e_{k}} and M ⊆ F an arbitrary submodule of F. An R-term is a monomial x_{1}^{i_{1}} ⋯ x_{n}^{i_{n}} without coefficient. By F -term we denote a module element te_{i}, where t is an R-term and e_{i} one of the basis elements of F. If no confusion is possible we will simply speak of terms instead of R- or F -terms. An admissible term order ≺ of F is a well-order of the set of all F - terms which is compatible with the multiplication by R-terms. By lt_{≺}(f) we denote the leading term of a nonzero element f ∈ F with respect to ≺, i.e. the largest (w.r.t. ≺) term appearing in f with nonzero coefficient. in_{≺}(f) denotes the initial term of f ∈ F with respect to ≺, that is in_{≺}(f) = 0 in case f = 0 and in_{≺}(f) = c lt_{≺}(f), where c is the coefficient of lt_{≺}(f) in f, otherwise. For arbitrary subsets V ⊆ F we extend these notions by lt_{≺}(V) = {lt_{≺}(v) | v ∈ V \ {0}} and in_{≺}(V) to be the submodule of F which is generated by all initial terms of elements of V.

Then a (finite) subset V ⊂ M is called a Gröbner basis of M with respect to ≺ iff in_{≺}(V) = in_{≺}(M). One way to compute a Gröbner basis of M from an arbitrary given finite generating set of M is the application of Buchberger’s famous algorithm (see [Bu65, Bu85]; for the module case see also [MM86]). We will illustrate the notions and methods by an example.

Example 2 (Part 1). Consider the polynomial ring R = ℂ[x, y] and the free Rmodule F with basis {e_{1}, e_{2}}. Moreover, let ≺ be the degreewise lexicographical order of the multiplicative monoid of R-terms which is defined by x^{α}y^{β} ≺ x^{α′}y^{β′} iff the first nonzero component of the integer vector ((α + β) − (α′ + β′), β − β′, α − α′) is negative. ≺ is extended to F -terms by te_{i} ≺ se_{j} :⇔ t ≺ s or t = s and i < j .

Consider the module elements p = x^{2}ye_{1} − 2xy^{2}e_{2} + x^{3}e_{2} and q = 2x^{2}ye_{1} + xye_{1} + x^{2}ye_{2}. Then in_{≺}(p) = −2xy^{2}e_{2} since x^{3} ≺ x^{2}y ≺ xy^{2} and, hence, x^{3}e_{2} ≺ x^{2}ye_{1} ≺ xy^{2}e_{2}. Similarly, in_{≺}(q) = x^{2}ye_{2} because xy ≺ x^{2}y and x^{2}ye_{1} ≺ x^{2}ye_{2}. Consequently, in_{≺}(V) = R (−2xy^{2}e_{2}, x^{2}ye_{2}) ⊂ F is the initial module of the set V = {p, q}. By M we denote the submodule of F generated by V. Then we have r := xp + 2yq = 4x^{2}y^{2}e_{1} + x^{3}ye_{1} + x^{4}e_{2} + 2xy^{2}e_{1} ∈ M and since in_{≺}(r) = 4x^{2}y^{2}e_{1} ∉ in_{≺}(V) we deduce that V is not a Gröbner basis of M with respect to ≺. (p, q) was the only critical pair of V (see [Bu85]) and since the initial term of the new element r belongs to a different module generator also the extended set V ∪ {r} has no additional critical pairs. Hence, in_{≺}(M) = R (−2xy^{2}e_{2}, x^{2}ye_{2}, 4x^{2}y^{2}e_{1}), i.e. {p, q, r} is a Gröbner basis of M with respect to ≺.

For a comprehensive introduction to the theory of Gröbner bases we refer to the survey article [Bu85] or one of the textbooks [AdLo94, BW93, Ei95].

4. Relationships between Gröbner Bases and Passive Systems

The idea behind passive complete systems of PDEs can be translated in terms of distinguished Gröbner bases of submodules of a free module F of rank k over the polynomial ring R = ℂ[X], the Riquier bases of polynomial modules. For this purpose let us consider the special case of systems of linear PDEs with constant coefficients. Then in view of the natural isomorphisms between the monoid D with differentiation, the multiplicative monoid T = ⟨X⟩ of R-terms, and the additive monoid ℕ^{n}, there is a natural isomorphism between the ring ℂ[D] of polynomial differential operators and the polynomial ring R = ℂ[X]. The left hand side of a linear partial differential equation G = 0 with constant coefficients can be considered as an element of the ℂ[D]-(left)module F which is freely generated by the unknown functions u_{1}, …, u_{k} and scalar multiplication of m ∈ F by Δ ∈ ℂ[D] means application of the differential operator Δ to m. The modules F and F = R^{k} are isomorphic. There is a natural bijection between the equivalence classes of systems of PDEs of the form G = 0 with left hand sides in F and the submodules of F. Moreover, a passive system of PDEs is mapped to a Gröbner basis and vice versa, where the corresponding orders ≺ are the same under the natural isomorphism between D and T.

Example 1 (Part 4). The system considered in Example 1 does not fit in the above concept due to the nonconstant coefficients. However, it has a natural algebraic translation in a free left module F of rank 2 over the Weyl algebra W_{2} in the indeterminates x, y, ∂x, ∂y, where ∂x x = x∂x + 1, ∂y y = y∂y + 1 and all other pairs of indeterminates commute.

The input translates in the module elements (∂x)^{2}e_{1} − y∂x e_{2} and (∂y)^{2}e_{1} + x^{2}e_{1}, where e_{1} and e_{2} are the free generators of F. By M we denote the left submodule of F generated by these two elements. Applying the Gröbner basis techniques for finitely generated left modules over Weyl algebras (see [ApLa88]) we obtain the left Gröbner basis {(∂x)^{2}e_{1} −y∂x e_{2}, (∂y)^{2}e_{1} +x^{2}e_{1}, y∂x(∂y)^{2} e_{2} +2∂x∂y e_{2} +x^{2}y∂x e_{2} +4x∂x e_{1} + 2e_{1}}. Using the methods introduced in [Ap98] it is also possible to compute Riquier bases in F (for the notion of a Riquier basis see the forthcoming Definition 5). One particular such basis can be obtained by adding the element (∂x)^{2}∂y e_{1} − y∂x∂y e_{2} − ∂x e_{2} to the above Gröbner basis. Retranslation in the language of PDEs confirms the analogy to our previous results. There remains one difference, namely the division by y appearing in Equation 5 cannot take place in the context of the Weyl algebra W_{2}. But we could extend W_{2} by allowing division by x and y and apply the Gröbner theory developed in [Ap00] which does not require the variables and coefficients to commute.

Example 2 (Part 2). The module elements p and q from Example 2 correspond to the following system of linear PDEs with constant coefficients

u_{xxy} − 2v_{xyy} + v_{xxx} = 0
2u_{xxy} + u_{xy} + v_{xxy} = 0

in unknown functions u and v and independent variables x and y. Transformation in orthonomic form yields

v_{xyy} = \frac{1}{2} (u_{xxy} + v_{xxx})
v_{xxy} = −2u_{xxy} − u_{xy}

Differentiating the first equation by x and the second by y leads to a noncontradicting integrability condition and adding the resulting equation

u_{xxyy} = −\frac{1}{4} (u_{xxxy} + v_{xxxx} + 2u_{xyy})

makes the system passive. Moreover, the system is already complete as the decomposition

PR = [v_{xyy}, {x, y}] ∪ [v_{xxy}, {x}] ∪ [u_{xxyy}, {x, y}] (6)

of the set of principal derivative shows. The decomposition

PA = [v, {y}] ∪ [v_{x}, {x}] ∪ [v_{xy}, ∅] ∪ [u, {y}] ∪ [u_{x}, {y}] ∪ [u_{xx}, {x}] ∪ [u_{xxy}, {x}]

of the set of parametric derivatives implies that the system has a unique holomorphic solution for an arbitrary initial determination of the type v_{xy}|_{x=x_{0},y=y_{0}} = c, v|_{x=x_{0}} = φ_{1}(y), v_{x}|_{y=y_{0}} = φ_{2}(x), u|_{x=x_{0}} = φ_{3}(y), u_{x}|_{x=x_{0}} = φ_{4}(y), u_{xx}|_{y=y_{0}} = φ_{5}(x), u_{xxy}|_{y=y_{0}} = φ_{6}(x).

Recall, that the basic property of a Gröbner basis V of the submodule M ⊂ F with respect to ≺ consists in the equality in_{≺}(M) = in_{≺}(V) or, equivalently, in the sum representation

in_{≺}(M) = ∑_{v∈V} R in_{≺}(v) . (7)

In case of a passive complete system of PDEs its image V in F satisfies the stronger condition

in_{≺}(M) = ⨁_{v∈V} ℂ[Y_{v}]in_{≺}(v) . (8)

Example 2 (Part 3). From Equation (6) we deduce that {p, q, r} is not only a Gröbner basis but even a Riquier basis providing the direct sum decomposition in_{≺}(M) = ℂ[x, y] xy^{2}e_{2}⊕ℂ[x] x^{2}ye_{2}⊕ℂ[x, y] x^{2}y^{2}e_{1} of the initial module in_{≺}(M) = in_{≺}({p, q, r}).

Equation (8) is a good starting point for the definition of a Riquier basis of the submodule M ⊂ F with respect to ≺ which we wish to be the analogue notion to a passive complete system of PDEs. In fact, if we restrict our interests to only the static aspect then this equation would be already the correct analogue. However, it is slightly too general in order to reflect also Janet’s dynamical aspects in a satisfactory way.

One method for the computation of a passive complete system is to first compute a passive system and to complete it in a subsequent step. Translated to the language of polynomial modules, that is, first to compute a Gröbner basis and afterwards to decompose the initial module in a direct sum of the required type. Actually, this is the idea which is implicitely suggested by Thomas’ paper [Th29]. In contrast, the most important feature of Janet’s algorithm consists in the fact, that it combines the completion of the set of principal derivatives and the transformation in passive form (see [Ja29]). Also alternative definitions of multipliers and nonmultipliers introduced in the past, e.g. by Thomas (see [Th29, Th37]) or by Pommaret (see [Po78]), show the nice behavior that an orthonomic system of PDEs is passive and complete iff replacing all principal derivatives in \frac{∂}{∂x}(D_{i}u_{j_{i}} − G_{i}) yields zero for all equations D_{i}u_{j_{i}} = G_{i} of the system and all nonmultipliers x of D_{i}u_{j_{i}}. In fact, this is the crucial condition which enables the application of a Janet like algorithm.

5. Riquier Bases of Polynomial Modules

In what follows we will consider arbitrary coefficient fields 𝕂. The only reason we had to restrict ourselves to the field 𝕂 = ℂ of complex numbers in the previous section was the relation to systems of PDEs. Here we will also switch to the more frequently used right module notation. In our setting of a module over a commutative polynomial ring this makes of course no difference. Note, however, in the general case of PDEs or noncommutative algebraic situations such as the Weyl algebra case considered in Part 4 of Example 1 we would have to take care about the correct sides.

The demands on the notion of Riquier basis as a “good” module theoretical analogue to passive complete systems resulting from the investigations made in the previous section can be summarized in two conditions:

1. a minimal Riquier basis V of M has to satisfy Equation (8) and

2. there should exist a Janet type algorithm which transforms an arbitrary finite

generating set of M in a Riquier basis V of M. Two different approaches satisfying both conditions have been introduced by Gerdt and Blinkov (see [GB98]) and by the author (see [Ap98]). While the Gerdt/Blinkov method saves almost all classical dynamic features our approach maintains only the principal idea behind Janet’s algorithm explained at the end of the previous section.

Definition. Let F be a free module of rank k over the polynomial ring R = 𝕂[X] in the indeterminates X = {x_{1}, …, x_{n}} and M a submodule of F. Moreover, let ≺ be an admissible term order of F. Then a subset V ⊂ M is called a minimal Riquier basis of M with respect to ≺ if there exists a linear order ⊏ of lt_{≺}(V) and a family (Y_{v})_{v∈V} of subsets of X such that

1. in_{≺}(M) = ⨁_{v∈V} in_{≺}(v)𝕂[Y_{v}] and

2. in_{≺}(v)𝕂[Y_{v}] ∩ in_{≺}(v′)𝕂[X] = {0} for all v, v′ ∈ V such that lt_{≺}(v′) ⊏ lt_{≺}(v). A subset V′ ⊆ M containing a subset V which is a minimal Riquier basis of M w.r.t. ≺ is called a Riquier basis of M w.r.t. ≺.

It is an immediate consequence of Definition 5 that the initial terms of the elements of a minimal Riquier basis are pairwise distinct. We will call a family (Y_{v})_{v∈V} of subsets of X admissible for the ordered set (lt_{≺}(V), ⊏) if for all v, v′ ∈ V such that lt_{≺}(v′) ⊑ lt_{≺}(v) it holds one of the conditions in_{≺}(v′)𝕂[Y_{v′}] ⊆ in_{≺}(v)𝕂[Y_{v}] or in_{≺}(v)𝕂[Y_{v}] ∩ in_{≺}(v′)𝕂[X] = {0}. Using the admissibility notion we can say that V ⊂ M is a Riquier basis of M with respect to ≺ iff there exist a linear order ⊏ of lt_{≺}(V) and a family (Y_{v})_{v∈V} of multipliers which is admissible for (lt_{≺}(V), ⊏) such that in_{≺}(M) = ∑_{v∈V} in_{≺}(v)𝕂[Y_{v}]. Note, there is a close relationship between the notions of minimal Riquier bases and reduced Gröbner bases. However, since we did not assume that the elements of a minimal Riquier basis have to be totally reduced, the better analog are the Gröbner bases which are minimal with respect to set inclusion. It follow two examples illustrating Definition 5.

Example 3 (Part 1). Consider the polynomial ring R = 𝕂[x, y, z, w] as a free Rmodule F of rank 1 and let M be the submodule of F, i.e. the ideal of R, which is generated by the set V = {xz, xw, yz, yw} of monomials.

If we order V by xz ⊏ xw ⊏ yz ⊏ yw then there is a unique admissible family of multipliers whose sets of multipliers are all maximal, namely, Y_{xz} = {x, y, z, w}, Y_{xw} = {x, y, w}, Y_{yz} = {y, z, w} and Y_{yw} = {y, w}. It is easy to verify that the sodefined family (Y_{v})_{v∈V} is admissible for (V, ⊏). That each of the sets Y_{v}, v ∈ V, is the only maximal set of multipliers which v can take follows immediately by the observation that for any v ∈ V and any variable s ∉ Y_{v} there exists v′ ∈ V such that v′ ⊏ v and v𝕂[s] ∩ v′R ⊋ {0} in contradiction to the admissibility conditions.

Moreover, one easily observes M = in_{≺}(M) = xz𝕂[x, y, z, w] ⊕ xw𝕂[x, y, w] ⊕ yz𝕂[y, z, w] ⊕ yw𝕂[y, w] and, therefore, V is a Riquier basis of M.

Example 4. In general, the situation is more complicated even for monomial ideals of polynomial rings. Let us consider another example of this type with R = 𝕂[x, y, z, w] and F = R being as in the previous example and V = {xy, xz, w}.

If V is ordered according to xy ⊏ xz ⊏ w then there are two maximal admissible families of multipliers. In both cases we have Y_{xy} = {x, y, z, w} and Y_{xz} = {x, z, w}. But there are two maximal possibilities to fix the set of multipliers for w, namely either Y_{w} = {y, z, w} or Y_{w} = {x, w}. In both cases we have only the inclusion xy𝕂[Y_{xy}] ⊕ xz𝕂[Y_{xz}] ⊕ w𝕂[Y_{w}] ⊊ M, hence, none of the two multiplier assignments makes V a Riquier basis.

Nevertheless, V is a Riquier basis of M. We just need to reorder V according to w ⊏ xy ⊏ xz. Then Y_{w} = {x, y, z, w}, Y_{xy} = {x, y, z} and Y_{xz} = {x, z} is the one and only maximal admissible choice of the sets of multipliers and one easily verifies the direct sum decomposition M = w𝕂[x, y, z, w] ⊕ xy𝕂[x, y, z] ⊕ xz𝕂[x, z].

We remind that there are also sets V of monomials, e.g. V = {x^{2}, y^{2}}, which by no linear order ⊏ and by no admissible family of multipliers can be made a Riquier basis. Also the question whether there is exactly one way to define a maximal admissible family of multipliers for a monomial set V is not related to V being a Riquier basis or not. At the first glance Definition 5 seems to have no dynamical part. However, the following theorem shows that Condition 2, which is slightly more restrictive then the property in_{≺}(v)𝕂[Y_{v}] ∩ in_{≺}(v′)𝕂[Y_{v′}] = {0} for all v, v′ ∈ V following already from Condition 1 of Definition 5 alone, enables the application of a Janet like algorithm for the computation of the sodefined Riquier bases.

Theorem. Let F be a free module of rank k over the polynomial ring R = 𝕂[X] in the variables X = {x_{1}, …, x_{n}} and M ⊂ F a submodule with generating set V, where all elements of V are monic and have pairwise distinct leading terms. Moreover, let ≺ be an admissible term order of F, ⊏ a linear order of lt_{≺}(V) and (Y_{v})_{v∈V} a family of multipliers which is admissible for the ordered set (lt_{≺}(V), ⊏).

Then with V′ = {v′ ∈ V | in_{≺}(v′) ∉ in_{≺}(v)𝕂[Y_{v}] for all v ∈ V \ {v′}} the following conditions are equivalent:

1. in_{≺}(M) = ∑_{v∈V} in_{≺}(v)𝕂[Y_{v}],

2. in_{≺}(M) = ⨁_{v′∈V′} in_{≺}(v′)𝕂[Y_{v′}],

3. V is a Gröbner basis of M with respect to ≺ and for all w ∈ V and all variables x ∉ Y_{w} it holds in_{≺}(xw) = x in_{≺}(w) ∈ ∑_{v∈V} in_{≺}(v)𝕂[Y_{v}],

4. (V \ V′) ⊂ ∑_{v′∈V′} v′𝕂[Y_{v′}] and for all w ∈ V′ and all variables x ∉ Y_{w} it holds

xw ∈ ∑_{v′∈V′} v′𝕂[Y_{v′}]. Moreover, any of the above conditions implies that V is a Riquier basis of M with respect to ≺.

Proof: Before we start to prove the equivalences let us make some remarks concerning the last statement. Obviously, V is a Riquier basis of M with respect to ≺ if Conditions 1. or 2. are satisfied. But one might wonder why the opposite direction should fail to hold. The reason is simply that V could be a Riquier basis according to the definition introduced here but the considered family (Y_{v})_{v∈V} is not suitable for providing the representations stated in 1. and 2. This problem can be avoided by defining the notion of a Riquier basis V with respect to a given order ⊏ and a given family (Y_{v})_{v∈V} in the way it was done in [Ap98].

The equivalence of 1. and 2. follows immediately from the admissibility of (Y_{v})_{v∈V}. The implication 1. → 3. is trivial. Let us sketch the main ideas behind the proof direction 3. → 1. The essential part consists in proving that for all w ∈ V and all terms t ∈ ⟨X⟩ there is a representation tw = a + b, where a = ∑_{v∈V} f_{v}v and b = ∑_{v∈V} g_{v}v such that f_{v}, g_{v} ∈ R, only finitely many of the f_{v} and g_{v} are nonzero, f_{v} ∈ 𝕂[Y_{v}] for all v ∈ V, and lt_{≺}(g_{v}v) ≺ lt_{≺}(tw) for all v ∈ V such that g_{v} ≠ 0. In case t ∈ ⟨Y_{w}⟩ this is obvious, so let x ∈ X \ Y_{w} be a nonmultiplier occurring in t. Then by condition 3. we have in_{≺}(xw) = x in_{≺}(w) ∈ ∑_{v∈V} in_{≺}(v)𝕂[Y_{v}] and, hence, there exist w′ ∈ V and s ∈ 𝕂[Y_{w′}] such that lt_{≺}(xw) = lt_{≺}(sw′). Since V is a Gröbner basis it follows the existence of a representation xw − sw′ = ∑_{v∈V} g′_{v}v, where only finitely many g′_{v} are nonzero and lt_{≺}(g′_{v}v) ≺ lt_{≺}(xw) for all v such that g′_{v} ≠ 0. Consequently, if one can show that \frac{t}{x}sw′ has a required representation a′ + b′ then also tw = \frac{t}{x}sw′ + ∑_{v∈V} \frac{t}{x}g′_{v}v can be represented in the desired way. An obvious idea seems to be to repeat the process recursively and conclude termination by induction on the number of nonmultipliers contained in t. But this approach will not work since a nonmultiplier for w does not need to be also a nonmultiplier for w′. Moreover, relaxing the admissibility condition of (Y_{v})_{v∈V} in such a way that only Condition 1 but not necessarily Condition 2 of Definition 5 holds can actually result in an infinite process. Note, there are simple counter examples showing that the implication 3. → 1. need not to hold in the relaxed case, c.f. the forthcoming Example 3 (Part 2). However, the stronger notion of admissibility used here implies lt_{≺}(w′) ⊏ lt_{≺}(w) which indeed ensures termination. Note, that by the finiteness of the number of terms dividing t in_{≺}(w) this is even true if V is infinite and ⊏ is not a well-order. Application of simple inductive arguments on finite representations m = ∑_{v∈V} h_{v}v of arbitrary elements m ∈ M finishes the proof of direction 3. → 1.

The implication 3. → 4. is obvious and it remains to consider the branch 4. → 3. An arbitrary element m ∈ M can be represented in the form m = ∑_{v∈V} h_{v}v, where only finitely many of the h_{v} ∈ R are nonzero. According to the first part of 4. we can assume w.l.o.g. h_{v} = 0 for all v ∉ V′. A rewriting process which successively replaces products of the form xv, where x is a nonmultiplier for v ∈ V′, finally ends up with a finite representation m = ∑_{v′∈V′} f_{v′}v′. Note, that here the strong definition of admissibility of (Y_{v})_{v∈V} is again essential. Now, we can deduce lt_{≺}(f_{v′}v′) ⪯ lt_{≺}(m) for all v′ ∈ V′ such that f_{v′} ≠ 0 since no initial parts of the summands at the right hand side can cancel out^{3}. This proves that V is a Gröbner basis and the second part of 3. follows easily by considering the special case m = xw in our above investigations. □

The above theorem shows that there is a Janet like algorithm for testing the Riquier basis property with respect to an arbitrary given admissible multiplier family (Y_{v})_{v∈V} by application of Condition 4. However, we are faced with a series of (minor) problems if the test fails, what is the case if some v ∈ V \ V′ or xw, where w ∈ V′ and x ∈ X \ Y_{w}, cannot be represented as an element of ⨁_{v′∈V′} v′𝕂[Y_{v′}]. Then the test provides a reduction remainder m ∈ M such that in_{≺}(m) ∉ ∑_{v∈V} in_{≺}(v)𝕂[Y_{v}] and the common idea of a critical pair/completion algorithm is to extend V by m and repeat the test algorithm until it ends without failure. But for this purpose the family of multipliers has to be adapted. Moreover, one has to show that the completion process eventually will terminate. Janet solved the problems by giving a general rule how to adapt the sets of multipliers and proved termination for his particular multiplier choice. But it turns out that the process will also terminate if one chooses the sets of multipliers in each step completely new taking care only that the multiplier sets are “sufficiently large”. The advantage is the possibility to adapt the family (Y_{v})_{v∈V} to the intermediate bases. However, this freedom in choice causes a large overhead and some heuristical restrictions are advisable in order to find a compromise. A detailed analysis how to compute the families (Y_{v})_{v∈V} and a detailed discussion of the algorithm which completes an arbitrary finite generating set of M to a finite (minimal) Riquier basis of M can be found in [Ap98].

3Note, by the same argument if will follow immediately that the sum ∑_{v′∈V′} v′𝕂[Y_{v′}] is direct, i.e. ∑_{v′∈V′} v′𝕂[Y_{v′}] = ⨁_{v′∈V′} v′𝕂[Y_{v′}].

In contrast, the Gerdt/Blinkov approach follows the classical method of fixing a priori all sets of multipliers, i.e. of fixing the families (Y_{v})_{v∈V} for all finite sets V of monomials. In addition, some technical restrictions are necessary in order to ensure the termination of the algorithm. In [Ap98] it is proved that there does not exist any family of multiplier assignments satisfying all conditions of [GB98] and having the additional property that for all finite sets of monomials the corresponding multiplier family is maximal. However, the Gerdt/Blinkov approach is also not subsumed by the method discussed here since it might include assignments of multiplicative variables which violate Condition 2 of our Definition 5. It is an open question whether there are situations where one can take advantage of this fact.

6. “Good” Riquier Bases

There are theoretical as well as computational issues which pose further conditions on a “good” choice of a Riquier basis V of a module M ⊂ F. Some of them are related to questions of the following type:

1. What is the minimal value of the sum ∑_{v∈V} |X \ Y_{v}| which a Riquier basis V of M can take?

2. What is the minimal number of elements of a Riquier basis V of M?

3. What is the minimal highest degree of the elements of a Riquier basis of M?

4. What is the maximal number d for which exist V ⊂ M and a multiplier family

(Y_{v})_{v∈V} making V a Riquier basis of M such that |Y_{v}| ≥ d for all v ∈ V? In case of generic coordinates and a degreewise reverse lexicographical term order ≺ Questions 1. - 3. have simple answers in terms of well-known algebraic invariants. In this case Bayer and Stillman (see [BS]), some generalizations of their results which are required here are due to Eisenbud (see [Ei95]), could show that the crucial invariants of the module M coincide with those of its generic initial module and Mall proved that, under the same conditions, any set V such that lt_{≺}(V) consists of the minimal monomial generators of in_{≺}(M) becomes a Riquier basis of M when the multipliers are assigned in a Pommaret like way (see [Ma98]). In case rank F = 1 the results of Bayer/Stillman, Eisenbud, and Mall answer also Question 4.

Let us consider the much more delicate but also much more interesting case of nongeneric coordinates. We start with the investigation of Riquier bases which are “good” in the sense that they can be computed in a minimal number of steps. The importance of the first three questions for a complexity analysis of the completion algorithm is obvious. In particular, the first question is highly interesting since the number ∑_{v∈V} |X \ Y_{v}| provides an estimate for the costs of the Riquier basis verification algorithm. In case of homogeneous modules M and the input generating set V′ being a minimal homogeneous generating set of M the completion algorithm to Riquier form has the same costs under the additional assumption that we have an oracle which tells us how to define the multipliers for the intermediate generating sets in the same way as they will appear in the final output. Note, the complexity analysis is harder than in the case of Buchberger’s algorithm where analogue statements hold without an oracle. We can offer a heuristic for the multiplier assignment which in some sense is a static approximation of the oracle. While, in general, Question 1 is difficult to answer it is always easy to find a family (Y_{v})_{v∈V} of admissible multiplier assignments such that ∑_{v∈V} |X \Y_{v}| is minimal for a given finite set V, a given term order ≺, and a given linear order ⊏ of lt_{≺}(V). Note, we neither require M = ∑_{v∈V} v𝕂[Y_{v}] (which clearly would be unfulfillable in general) nor that ⊏ and ≺ are optimal in whatsoever sense. Let us discuss the objective of minimizing ∑_{v∈V} |X \Y_{v}| a little more detailed. In order to have a trivial intersection v𝕂[Y_{v}] ∩ v′𝕂[Y_{v′}] = {0} it is necessary and sufficient to ensure lcm(v, v′) ∉ v𝕂[Y_{v}] ∩ v′𝕂[Y_{v′}], which is exactly the case if at least one of the conditions \frac{lcm(v,v′)}{v} ∉ 𝕂[Y_{v}] or \frac{lcm(v,v′)}{v′} ∉ 𝕂[Y_{v′}] holds. How this property is achieved by the different approaches applied in the past? Thomas uses the most rigid way which consists in requiring that for any distinct elements v, v′ ∈ V no variable of \frac{lcm(v,v′)}{v} belongs to Y_{v} and no variable of \frac{lcm(v,v′)}{v′} belongs to Y_{v′}. The method due to Janet is much more sophisticated. It enumerates the variables and requires that for any two distinct elements v, v′ ∈ V the first variable x in which v and v′ have distinct degrees, without loss of generality let us assume deg_{x} v < deg_{x} v′, is not contained in Y_{v} and, therefore, Janet’s method ensures \frac{lcm(v,v′)}{v} ∉ 𝕂[Y_{v}] by introducing a single condition x ∉ Y_{v} for the pair (v, v′). Janet’s approach sounds already very promising but still can be improved for two reasons. Firstly, it does not make any use of inclusions v′𝕂[Y_{v′}] ⊂ v𝕂[Y_{v}] which might allow to waive the condition x ∉ Y_{v} for the pair (v, v′) in case v | v′ and Y_{v′} ⊆ Y_{v} ∪ {x}. Secondly, it always poses a condition on the first variable x in which v and v′ have different degrees. But it can happen that the consideration of v and a third basis element v′′ ∈ V yields a condition y ∉ Y_{v} in such a way that by accident also deg_{y} v < deg_{y} v′. In this case the single condition y ∉ Y_{v} ensures already v𝕂[Y_{v}]∩v′𝕂[Y_{v′}] = v𝕂[Y_{v}]∩v′′𝕂[Y_{v′′}] = {0} and the condition x ∉ Y_{v} can be refused again.

Example 5. Consider the ideal M generated by V = {x_{2}x_{3}^{2}, x_{2}^{2}x_{3}, x_{1}x_{2}^{2}} in F = R = 𝕂[x_{1}, x_{2}, x_{3}]. Janet’s sets of multipliers are Y_{x_{2}x_{3}^{2}} = {x_{3}}, Y_{x_{2}^{2}x_{3}} = {x_{2}, x_{3}} and Y_{x_{1}x_{2}^{2}} = {x_{1}, x_{2}, x_{3}}. A better assignment is Y′_{x_{2}x_{3}^{2}} = {x_{1}, x_{3}}, Y′_{x_{2}^{2}x_{3}} = {x_{2}, x_{3}} and Y′_{x_{1}x_{2}^{2}} = {x_{1}, x_{2}, x_{3}}. Not only that ∑_{v∈V} |X \ Y′_{v}| = 2 < 3 = ∑_{v∈V} |X \ Y_{v}|, we have even the proper inclusion {xv | v ∈ V and x ∈ X \ Y′_{v}} ⊂ {xv | v ∈ V and x ∈ X \ Y_{v}} of the sets of elements which have to be reduced to zero during a Riquier basis check. Hence, the running time in case of success is not only heuristically but provable faster for the second family of multipliers. Finally, we observe that the family (Y′_{x_{2}x_{3}^{2}}, Y′_{x_{2}^{2}x_{3}}, Y′_{x_{1}x_{2}^{2}}) yields the decomposition M = x_{2}x_{3}^{2}𝕂[x_{1}, x_{3}] ⊕ x_{2}^{2}x_{3}𝕂[x_{2}, x_{3}] ⊕ x_{1}x_{2}^{2}𝕂[x_{1}, x_{2}, x_{3}] showing that V is a Riquier basis of M. In contrast the original Janet assignment fails the check since x_{1}x_{2}x_{3}^{2} ∈ M \ (x_{2}x_{3}^{2}𝕂[x_{3}] ⊕ x_{2}^{2}x_{3}𝕂[x_{2}, x_{3}] ⊕ x_{1}x_{2}^{2}𝕂[x_{1}, x_{2}, x_{3}]), i.e. V is not a Janet basis of M.

A mild variation of the above static approach which includes also dynamic features without essentially increasing the costs is to look for an admissible multiplier assignment (Y_{v})_{v∈V} such that the sum ∑_{v∈V} |X \ (Y_{v} ∪ Z_{v}) |, where Z_{v} ⊆ X denotes the set of all variables x for which xv had been reduced already during the previous completion process, becomes minimal. If a fixed linear order ⊏ of the set of all terms is used during the completion algorithm then this number is the better approximation for the remaining costs of the completion process since no repeated reductions are necessary under these conditions (see [Ap98]). The basic idea behind the strategy suggested in [Ap98, Remark 6.2] is to choose the multiplicative variables according to this heuristic.

Now let us consider another notion of “good” Riquier bases, namely, such which provide the maximal value d introduced in Question 4. The search for Riquier bases which are “good” in such a sense is strongly related to the solution of combinatorial problems and the computation of invariants of the module. There is the following open conjecture due to Stanley: an arbitrary monomial module M can be decomposed in the form (8) such that |Y_{v}| ≥ depth M for all v ∈ V (see [St82]). In [Ap01a] this conjecture could be proved for some huge classes of modules in the case rank F = 1 by proving the existence of “good” Riquier bases, i.e. such which for a suitable multiplier definition satisfy d ≥ depth M. This property is even more restrictive than conjectured by Stanley since the additional Condition 2 of Definition 5 holds. So it is not surprising that the class of Riquier bases defined in Definition 5 is not reach enough to prove Stanley’s conjecture in general. The following simple counter examples illustrates that no definition of Riquier bases allowing a Janet type algorithm need to provide the maximal possible d.

Example 3 (Part2). In Part 1 we observed that V = {xz, xw, yz, yw} is a Riquier basis and one easily verifies that the largest element of V with respect to any linear order ⊏ will have at most two multipliers. However, M can be decomposed also in the form M = xz𝕂[x, z, w]⊕xw𝕂[x, y, w]⊕yz𝕂[x, y, z]⊕yw𝕂[y, z, w]⊕xyzw𝕂[x, y, z, w] with vertices from the larger generating set V′ = {xz, xw, yz, yw, xyzw} of M. While the corresponding multiplier sets satisfy Equation (8) they do not allow a Janet like algorithm. Note, that V′ and the above family of multipliers satisfy the last two but violate the first two conditions of the theorem on page 10. One easily observes that Condition 2 of Definition 5 is not satisfied for any linear order ⊏ of V′.

The above example shows that even in the case that the minimal generators of a monomial module M can be used as the vertices of a direct sum decomposition (8) of M such a decomposition needs not to be “best” possible with respect to Question 4. Consequently, “good” in the sense of the first three questions can be quite distinct from “good” in the sense of the last question. The difficulties one meets in the study of Stanley’s conjecture make clear that a relaxation of the assignment rules for the multiplicative variables will not only disable Janet’s algorithm but will have also impact on the costs of the alternative method which consists in first computing a Gröbner basis and doing the direct sum decomposition of the initial module subsequently. In fact, this shows that the sometimes underestimated task of computing a Riquier basis of a given monomial module is not easy if additional conditions are posed on the decomposition. Note, there is an obvious but infeasible algorithm for solving this problem which is based on the simple observation that the number of decompositions of type (8) in maximal direct summands is finite. During the search for suitable initial determinations of a system of PDEs the demands on the decomposition of the set PA of parametric derivatives in disjoint cones are often similar to those of Stanley. Therefore, the investigation of Stanley’s conjecture for modules R/I (see [Ap01b]) can contribute to this part of the Riquier/Janet theory which seems to be much less investigated in the past.

7. Concluding Remarks

The observation of Zharkov and Blinkov that there is something interesting at the junction of passive complete orthonomic systems of PDEs and Gröbner bases of polynomial ideals (see [ZB93]) was the starting point of the investigation of Riquier (or involutive) bases. Zharkov and Blinkov’s motivation was to find a fast alternative algorithm for the computation of Gröbner bases in polynomial rings and a series of remarkable results and computer experiments in this direction have been reported in the past (c.f. [GBY01], [He01]). Each comparison depends strongly on the used implementations since Buchberger’s algorithm for the computation of Gröbner bases and Janet’s algorithm for the computation of Riquier bases are of the same complexity order. Though, Gerdt/Blinkov/Yanovich as well as Hemmecke compared to todays state of the art implementations of Buchberger’s algorithm there still remains a little danger that at some day the original justification of (polynomial) Riquier bases might disappear, for instance, when an essentially improvement in the strategies of Buchberger’s algorithm will be found. This is the reason one should have always in mind also theoretical justifications resulting from the additional structure of Riquier bases. This additional structure consists in a direct sum decomposition of the initial module and allows, for instance, to give a closed formula for the Hilbert function (see [Ap98]) or to compute Stanley decompositions (see [Ap01a, Ap01b]).

The quite different approaches due to Gerdt and Blinkov [GB98] and Apel [Ap98], respectively, show that there is no canonical generalization of Riquier’s ideas to rings and modules. The objective of this talk was to convince the auditors that there is certainly no “best” algebraic generalization and that there is still a wide open field in finding “good” ones depending on the application one has in mind. The application might be one of the previously investigated as well as some completely new which probably will be discovered in the future.

References

[AdLo94] W. W. Adams, P. Loustaunau. An Introduction to Gröbner Bases, Graduate Studies in Mathematics, Vol. 3, AMS Press, Providence, (1994).

[Ap98] J. Apel. The Theory of Involutive Divisions and an Application to Hilbert Function Computations. J. Symb. Comp. 25, 683-704 (1998).

[Ap00] J. Apel. Computational Ideal Theory in Finitely Generated Extension Rings. Theoretical Computer Science, 244/1-2, 1–33 (2000).

[Ap01a] J. Apel. On a Conjecture of R. P. Stanley; Part I – Monomial Ideals. MSRI Preprint 2001-004 (2001).

[Ap01b] J. Apel. On a Conjecture of R. P. Stanley; Part II – Quotients modulo Monomial Ideals. MSRI Preprint 2001-009 (2001).

[Ap01c] J. Apel. Stanley Decompositions and Riquier Bases. Talk presented at the Conference on Applications of Computer Algebra (ACA’01), Albuquerque (2001).

[ApLa88] J. Apel, W. Laßner. An Extension of Buchberger’s Algorithm and Calculations in Enveloping Fields of Lie Algebras. J. Symb. Comp. 6, 361–370 (1988).

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

[BW93] T. Becker, V. Weispfenning, in cooperation with H. Kredel. Gröbner Bases, A Computational Approach to Commutative Algebra. Springer, New York, Berlin, Heidelberg, (1993).

[Bu65] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. Thesis, University of Innsbruck, (1965).

[Bu85] B. Buchberger. An Algorithmic Method in Polynomial Ideal Theory, Chapter 6 in: N.K. Bose, ed., Recent Trends in Multidimensional System Theory, D.Reidel Publ.Comp., (1985).

[Ei95] D. Eisenbud. Commutative Algebra. With a view toward algebraic geometry. Graduate Texts in Mathematics, 150. Springer-Verlag, New York, (1995).

[GB98] V. P. Gerdt, Yu. A. Blinkov. Involutive Bases of Polynomial Ideals. Mathematics and Computers in Simulation 45, 519–542 (1998).

[GBY01] V. P. Gerdt, Yu. A. Blinkov, D. A. Yanovich. Fast Computation of Polynomial Janet Bases. Talk presented at the Conference on Applications of Computer Algebra (ACA’01), Albuquerque (2001).

[He01] R. Hemmecke. Dynamical Aspects of Involutive Bases Computations. Talk presented at the Conference on Applications of Computer Algebra (ACA’01), Albuquerque (2001).

[Ja29] M. Janet. Lecons sur les systèmes d’equations aux dérivées partielles. Gauthier-Villars, Paris (1929).

[Ma98] D. Mall, On the relation between Gröbner and Pommaret bases. AAECC 9/2, 117–123 (1998).

[MM86] H. M. Möller, T. Mora. New Constructive Methods in Classical Ideal Theory, J.Algebra 100, 138–178, (1986).

[Po78] J. F. Pommaret. Systems of Partial Differential Equations and Lie Pseudogroups. Gordan and Breach, New York (1978).

[Ri10] C. H. Riquier. Les systémes d’equations aux dérivées partielles. Gauthier-Villars, Paris (1910).

[St82] R. P. Stanley. Linear Diophantine Equations and Local Cohomology. Invent. math. 68, 175– 193 (1982).

[Th29] J. M. Thomas. Riquier’s Existence Theorems. Annals of Mathematics 30/2, 285–310 (1929).

[Th37] J. M. Thomas. Differential Systems. American Mathematical Society, New York, (1937).

[Tr1894] A. R. Tresse. Su les invariants différentials des groupes continus de transformations. Acta Mathematica 18, 1–8 (1894).

[ZB93] A. Yu. Zharkov, Yu. .A. Blinkov. Involution Approach to Solving Systems of Algebraic Equations. Proc. IMACS’93, 11–16 (1993).

Joachim Apel^{4}, Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, CA 94720, U.S.A.

E-mail address: apel@msri.org

4On leave from Mathematisches Institut, Universität Leipzig, Augustusplatz 10–11, 04109 Leipzig, Germany, E-mail address: apel@mathematik.uni-leipzig.de