Gr¨ obner Bases in

GB Semester, Workshop D2, Linz/Hagenberg, May 2006

Gr¨ obner Bases in

Difference-Differential Modules

Franz Winkler

RISC-Linz

J. Kepler University Linz, Austria

This is joint work with M. Zhou of Beihang University in Beijing.

The work has been supported by the Austrian FWF project P16357-N04 and by the National Key Basic Research Project 2005CB321902 of China, while the first author spent a research year at RISC-Linz.

1

1. Introduction

• We extend the theory of Gr¨obner bases to difference-differen- tial modules. The main purpose of this paper is to give a new approach to the computation of a Gr¨obner basis for an ideal in (or a module over) the ring of difference-differential operators.

• To this aim we introduce the concept of generalized term order on N^m × Zⁿ and on difference-differential modules.

2

Related work

• The theory of GB has been generalized by many authors to non-commutative domains, especially to modules over vari- ous rings of differential operators. Galligo (1985) first gave the Gr¨obner basis algorithm for the Weyl algebra Aⁿ(K) of partial differential operators with coefficients in a polynomial ring over the field K.

• Mora (1986) generalized the concept of Gr¨obner basis to non-commutative free algebras.

• Kondrateva et al. (1998) described the Gr¨obner basis method for differential and difference modules.

• Noumi (1988) and Takayama (1998) formulated Gr¨obner bases in R_n, the ring of differential operators with rational function coefficients.

• Oaku and Shimoyama (1994) treated D₀, the ring of differ- ential operators with power series coefficients.

3

• Insa and Pauer (1998) presented a basic theory of Gr¨obner bases for differential operators with coefficients in a commu- tative Noetherian ring.

• Pauer and Unterkircher (1999) considered Gr¨obner bases in Laurent polynomial rings, but their approach is limited to the commutative case.

• Levin (2000) introduced characteristic sets for free modules over rings of difference-differential operators. Such charac- teristic sets depend on a specific order on N^m × Zⁿ. But this order is not a term order in the sense of the theory of Gr¨obner bases.

4

Difference-differential modules

A ring is always an associative ring with 1. A module over a ring A is a unitary left A-module.

Def.1.1: Let R be a commutative Noetherian ring. Let ∆ = {δ₁,· · ·, δ_m} be a set of derivations on R and Σ = {σ₁,· · ·, σ_n} a set of automorphisms of R, such thatα(x) ∈ R and α(β(x)) = β(α(x)) for any α, β ∈ ∆ ∪ Σ and x ∈ R. Then R is called a difference-differential ring with the basic set of derivations ∆ and the basic set of automorphisms Σ, or shortly a ∆-Σ-ring; if R is a field, then it is called a ∆-Σ-field.

Ex.1.1: Let R = K[x₁, . . . , x_n] for a field K, δ_i = ∂/∂x_i and σ_i the automorphism which maps x_i to x_i − 1. Then R is a

∆-Σ-ring for ∆ = {δ₁, . . . , δ_n} and Σ = {σ₁, . . . , σ_n}.

5

Def.1.2: Let R be a ∆-Σ-ring and Λ be the free commutative semigroup of words over ∆ and ˜Σ (containing the elements of Σ and their inverses).

Then an expression of the form X

λ∈Λ

a_λλ, (1.2)

where a_λ ∈ R for all λ ∈ Λ and only finitely many coefficients a_λ are different from zero, is called a difference-differential op- erator (or shortly a ∆-Σ-operator) over R.

Two ∆-Σ-operators P

λ∈Λa_λλ and P

λ∈Λb_λλ are equal if and only if a_λ = b_λ for all λ ∈ Λ.

6

The set of all ∆-Σ-operators over a ∆-Σ-ring R is a ring with the following fundamental relations

P

λ∈Λa_λλ +P

λ∈Λb_λλ = P

λ∈Λ(a_λ + b_λ)λ, a(P

λ∈Λa_λλ) = P

λ∈Λ(aa_λ)λ, (P

λ∈Λa_λλ)µ = P

λ∈Λa_λ(λµ), δa = aδ + δ(a), σa = σ(a)σ,

(1.3)

for all a_λ, b_λ ∈ R, λ, µ ∈ Λ, a ∈ R, δ ∈ ∆, σ ∈ Σ. Note that˜ the elements in ∆ and ˜Σ do not commute with the elements in R, and therefore the terms λ ∈ Λ do not commute with the coefficients a_λ ∈ R.

7

Def.1.3: The ring of all ∆-Σ-operators over a ∆-Σ-ring R is called the ring of difference-differential operators (or shortly the ring of ∆-Σ-operators) over R. It will be denoted by D.

A left D-module M is called a difference-differential module (or a ∆-Σ-module). IfM is finitely generated as a left D-module, then M is called a finitely generated ∆-Σ-module.

8

When Σ = ∅, D will be the ring of differential operators R[δ₁,· · ·, δ_m].

If the coefficient ring R is the polynomial ring in x₁, . . . , x_m over a field K and δ_i = ∂/∂x_i for 1 ≤ i ≤ m, then D will be the Weyl algebra Am(K). So ∆-Σ-modules are generalizations of modules over rings of differential operators.

But in the ring of ∆-Σ-operators the terms are of the form (1.1) and the exponent in σ₁,· · ·, σ_n is (l₁,· · ·, l_n) ∈ Zⁿ. The notion of term order, as commonly used in Gr¨obner basis theory, is no longer valid. We need to generalize the concept of term order.

9

2. Generalized term order

Def.2.1: Let Zⁿ be the union of finitely many subsets Zⁿ_j, i.e.

Zⁿ = Sk

j=1 Zⁿ_j, where Zⁿ_j, j = 1,· · ·, k, satisfy the following conditions:

(i) (0,· · ·,0) ∈ Zⁿ_j, and Zⁿ_j does not contain any pair of invertible elements c = (c₁,· · ·, c_n) 6= 0 and −c = (−c₁,· · ·,−c_n),

(ii) Zⁿ_j is isomorphic to Nⁿ as a semigroup, (iii) the group generated by Zⁿ_j is Zⁿ.

Then {Zⁿ_j | j = 1,· · ·, k} is called an orthant decomposition of Zⁿ and Zⁿ_j is called the j-th orthant of the decomposition.

10

Ex.2.1: Let {Zⁿ₁,· · ·,Zⁿ_2n} be all distinct Cartesian products of n sets each of which is either Z₊ or Z₋. Then this is an orthant decomposition of Zⁿ. The set of generators of Zⁿ_j as a semigroup is

{(c₁,0,· · ·,0),(0, c₂,0,· · ·,0),· · ·,(0,· · ·,0, c_n)},

where c_j is either 1 or −1, j = 1,· · ·, n. We call this decompo- sition the canonical orthant decomposition of Zⁿ.

11

Ex.2.2: The decomposition Z² = Z²₀ ∪ Z²₁ ∪Z²₂, where Z²₀ = {(a, b)|a ≥ 0, b ≥ 0, a, b ∈ Z},

Z²₁ = {(a, b)|a ≤ 0, b ≥ a, a, b ∈ Z}, Z²₂ = {(a, b)|b ≤ 0, a ≥ b, a, b ∈ Z}, is an orthant decomposition of Z².

12

Def.2.2: Let {Zⁿ_j | j = 1,· · ·, k} be an orthant decom- position of Zⁿ. Then a = (k₁,· · ·, k_m, l₁,· · ·, l_n) and b = (r₁,· · ·, r_m, s₁,· · ·, s_n) of N^m×Zⁿ are called similarelements, if the n-tuples (l₁,· · ·, l_n) and (s₁,· · ·, s_n) are in the same orthant Zⁿ_j of Zⁿ.

Def.2.3: Let {Zⁿ_j | j = 1,· · ·, k} be an orthant decomposition of Zⁿ. A total order ≺ on N^m×Zⁿ is called a generalized term order on N^m × Zⁿ w.r.t. the decomposition, if the following conditions hold:

(i) (0,· · ·,0) is the smallest element in N^m × Zⁿ, (ii) if a ≺ b, then a +c ≺ b+ c for any c similar to b.

13

Ex.2.3: (a) Let {Zⁿ_j | j = 1,· · ·,2ⁿ} be the canonical orthant decomposition of Zⁿ defined in Example 2.1. For every a = (k₁,· · ·, k_m, l₁,· · ·, l_n) ∈ N^m × Zⁿ let

|a| = k₁ + · · · +k_m +|l₁|+ · · · +|l_n|. For two elements a = (k₁,· · ·, k_m, l₁,· · ·, l_n) and

b = (r₁,· · ·, r_m, s₁,· · ·, s_n) of N^m ×Zⁿ define a ≺ b if and only if the (1 + m + n)-tuple (|a|, k₁,· · ·, k_m, l₁,· · ·, l_n) is smaller than (|b|, r₁,· · ·, r_m, s₁,· · ·, s_n) w.r.t. the lexicographic order on N^m+1 × Zⁿ. Then ”≺” is a generalized term order on N^m ×Zⁿ.

14

(b) Let the orthant decomposition of Zⁿ be as in Example 2.1.

For every a = (k₁,· · ·, k_m, l₁,· · ·, l_n) ∈ N^m ×Zⁿ let

|a|1 =

m

X

j=1

k_j, |a|2 =

n

X

j=1

|l_j|. For two elements a = (k₁,· · ·, k_m, l₁,· · ·, l_n) and

b = (r₁,· · ·, r_m, s₁,· · ·, s_n) of N^m ×Zⁿ define a ≺ b if and only if the (2 + m + 2n)-tuple

(|a|1,|a|2, k₁,· · ·, k_m,|l₁|,· · ·,|l_n|, l₁,· · ·, l_n) is lexicographically smaller than

(|b|¹,|b|², r₁,· · ·, r_m,|s₁|,· · ·,|s_n|, s₁,· · ·, s_n).

Then ”≺” is a generalized term order on N^m × Zⁿ.

15

(c) Let {Z⁽ⁿ⁾_j , j = 0,1,· · ·, n} be the orthant decomposition of Zⁿ defined in Example 2.2. For every element

a = (k₁,· · ·, k_m, l₁,· · ·, l_n) ∈ N^m × Zⁿ let kak = −min{0, l₁,· · ·, l_n} . For two elements a = (k₁,· · ·, k_m, l₁,· · ·, l_n) and

b = (r₁,· · ·, r_m, s₁,· · ·, s_n) of N^m ×Zⁿ define a ≺ b if and only if the (1 + m + n)-tuple (kak, k₁,· · ·, k_m, l₁,· · ·, l_n) is lexico- graphically smaller than (kbk, r₁,· · ·, r_m, s₁,· · ·, s_n). Then

”≺” is a generalized term order on N^m × Zⁿ.

16

In order to investigate ∆-Σ-modules, we need to extend the notion of generalized term order to N^m × Zⁿ × E, where E = {e₁,· · ·, e_q} is a set of generators of a module.

Def. 2.4: Let {Zⁿ_j | j = 1,· · ·, k}be an orthant decomposition of Zⁿ. Let E = {e₁,· · ·, e_q} be a set of q distinct elements. A total order ≺ on N^m × Zⁿ × E is called a generalized term order on N^m×Zⁿ×E w.r.t. the decomposition, if the following conditions hold:

(i) (0,· · ·,0, e_i) is the smallest element in N^m × Zⁿ × {e_i} for any e_i ∈ E,

(ii) if (a, e_i) ≺ (b, e_j), then (a + c, e_i) ≺ (b + c, e_j) for any c similar to b.

17

Ex.2.4: Let the orthant decomposition of Zⁿ and the general- ized term order ”≺” on N^m×Zⁿ be as in Example 2.3(b). Given an order ”≺E” on E = {e₁,· · ·, e_q}, for two elements

(a, e_i) = (k₁,· · ·, k_m, l₁,· · ·, l_n, e_i) and (b, e_j) = (r₁,· · ·, r_m, s₁,· · ·, s_n, e_j)

of N^m ×Zⁿ ×E define:

(a, e_i) ≺1 (b, e_j) ⇐⇒ a ≺ b or (a = b and e_i ≺E e_j);

(a, e_i) ≺2 (b, e_j) ⇐⇒ e_i ≺E e_j or (e_i = e_j and a ≺ b);

(a, e_i) ≺³ (b, e_j) ⇐⇒

(|a|1,|a|2, e_i, k₁,· · ·, k_m,|l₁|,· · ·,|l_n|, l₁,· · ·, l_n)

< (|b|1,|b|2, e_j, r₁,· · ·, r_m,|s₁|,· · ·,|s_n|, s₁,· · ·, s_n) in lexicographic order.

Then ”≺1”, ”≺2”,”≺3” are generalized term orders on N^m × Zⁿ × E.

18

Lemma 2.1: Let {Zⁿ_j | j = 1,· · ·, k} be an orthant decompo- sition of Zⁿ and ”≺” be a generalized term order on N^m × Zⁿ with respect to the orthant decomposition.

(a) Every strictly descending sequence in N^m × Zⁿ is finite. In particular, every subset of N^m × Zⁿ contains a smallest ele- ment.

(b) Every strictly descending sequence in N^m×Zⁿ×E is finite.

In particular, every subset ofN^m×Zⁿ×E contains a smallest element.

19

3. Gr¨ obner bases in finitely gener- ated difference-differential modules

Let K be a ∆-Σ-field and D be the ring of ∆-Σ-operators over K, and let F be a finitely generated free D-module (i.e. a finitely generated free difference-differential-module) with a set of free generators E = {e₁,· · ·, e_q}. Then F can be considered as a K-vector space generated by the set of all elements of the form λe_i, where λ ∈ Λ and i = 1, . . . , q. This set will be denoted by ΛE and its elements will be called “terms” of F. If “≺” is a generalized term order on N^m × Zⁿ × E then “≺” obviously induces an order on ΛE, which we also call a generalized term order.

Every element f ∈ F has a unique representation as a linear combination of terms

f = a₁λ₁e_j1 +· · · +a_dλ_de_jd (3.1) for some nonzero elements a_i ∈ K (i = 1,· · ·, d) and some distinct elements λ₁e_j1,· · ·, λ_de_jd ∈ ΛE.

20

Reduction in difference-differential modules Def.3.1: Let

λ₁ = δ₁^k1 · · ·δ_m^kmα^l₁¹ · · ·α^l_nⁿ and λ₂ = δ₁^r1 · · ·δ_m^rmα^s₁¹ · · ·α^s_nⁿ be two elements in Λ. If they are similar and r_µ ≤ k_µ, |s_ν| ≤ |l_ν| for µ = 1,· · ·, m, ν = 1,· · ·, n, then λ₁ is called a multiple of λ₂ and this relation is denoted by λ₂|λ₁. If λ₂|λ₁ and i = j then u = λ₁e_i is called a multiple of v = λ₂e_j and this relation is denoted by v|u.

Def. 3.2: Let ≺ be a generalized term order on ΛE, f ∈ F be of the form (3.1). Then

lt(f) = max_≺{λ_ie_ji|i = 1,· · ·, d}

is called the leading term of f. If λ_ie_ji = lt(f), then a_i is called the leading coefficient of f, denoted by lc(f).

21

Lemma 3.1: Let λ ∈ Λ, a ∈ K, and ≺ be a generalized term order on Λ ⊆ D. Then

λa = a⁰λ+ξ,

where a⁰ = σ(a) for some σ ∈ Σ^∗. If a 6= 0 then also a⁰ 6= 0.

Furthermore, ξ ∈ D with lt(ξ) ≺ λ and all terms of ξ are similar to λ.

Lemma 3.2: Let F be a finitely generated free D-module and 0 6= f ∈ F. Then the following hold:

(i) If λ ∈ Λ, then lt(λf) = λ · u for a unique term u of f. (ii) If lt(f) ∈ Λ_jE then for any λ ∈ Λ_j

lt(λf) = λ· lt(f) ∈ Λ_jE.

Lemma 3.3: Let F be a finitely generated free D-module and 0 6= f ∈ F. Then for each j, there exists some λ ∈ Λ and a unique term u_j of f such that

lt(λf) = λ· u_j ∈ Λ_jE.

We will write lt_j(f) for this term u_j.

Proposition 3.1: Let 0 6= f ∈ F, 0 6= h ∈ D. Then lt(hf) = max_≺{λ_iu_k} where λ_i are terms of h and u_k are terms of f. Therefore lt(hf) = λ · u for a unique term λ of h and a unique term u of f.

22

Now we are ready to introduce the concept of “reduction”, which is central in the theory of Gr¨obner bases.

Theorem 3.1: Let f₁,· · ·, f_p ∈ F \ {0}. Then every g ∈ F can be represented as

g = h₁f₁ + · · ·+ h_pf_p +r (3.2) for some elements h₁,· · ·, h_p ∈ D and r ∈ F such that

(i) h_i = 0 or lt(h_if_i) lt(g) for i = 1,· · ·, p,

(ii) r = 0 or lt(r) is not a multiple of any lt(λf_i) for λ ∈ Λ, i = 1,· · ·, p.

23

Def.3.4: Let f₁, . . . , f_p ∈ F \ {0}, g ∈ F. Suppose that equation (3.2) in Theorem 3.1 holds and the conditions (i), (ii) are satisfied. If r 6= g we say g can be reduced by {f₁,· · ·, f_p} to r. In this case we have lt(r) ≺ lt(g) by the proof of Theorem 3.1. In the case of r = g and h_i = 0 for i = 1,· · ·, p, we say that g is reduced w.r.t. {f₁,· · ·, f_p}.

Note that we are using the notion of reduction as head- reduction.

24

Ex.3.1: Let K = Q(x₁, x₂), D = K[δ₁, δ₂, α, α⁻¹], where δ₁, δ₂ are the partial derivatives w.r.t. x₁, x₂, respectively, and α is an automorphism of K. So D is the {δ₁, δ₂} − {α}-ring over the coefficient field Q(x₁, x₂). Choose the generalized term order on N² × Z as in Example 2.3 (a), i.e.

u = δ₁^k1δ₂^k2α^l ≺ v = δ₁^r1δ₂^r2α^s ⇐⇒

(kuk, k₁, k₂, l) <_lex (kvk, r₁, r₂, s), where kuk = k₁ + k₂ +|l|. Let

g = δ₁α⁻² +δ₂α², f = δ₁α⁻¹ +α.

Then

g = δ₁α⁻² +δ₂α² = α⁻¹(δ₁α⁻¹+α) + (δ₂α²− 1) = α⁻¹f +r₁. Although lt(r₁) = δ₂α² is not any multiple of lt(f) = δ₁α⁻¹, we can find λ = δ₂α such that lt(r₁) = lt(λf) = lt(δ₁δ₂ + δ₂α²).

Therefore

g = α⁻¹f +δ₂αf + (−δ₁δ₂ − 1) = (α⁻¹ + δ₂α)f +r₂ Now r₂ satisfies the condition (ii) in Theorem 3.1. Sog is reduced by f to r₂.

25

Gr¨obner bases

Def. 3.5: Let W be a submodule of the finitely generated free D-module F and ≺ be a generalized term order on ΛE. Let G = {g₁,· · ·, g_p} ⊆ W\{0}. Then G is called a Gr¨obner basis of W (w.r.t. the generalized term order ≺) if and only if for every f ∈ W \ {0}, lt(f) is a multiple of lt(λg_j) for some λ ∈ Λ, g_j ∈ G. If every element of G is reduced with respect to the other elements of G, then G is called a reduced Gr¨obner basis of W.

26

Proposition 3.2: Let G be a finite subset of W \ {0}. The following assertions hold:

(i) G is a Gr¨obner basis of W if and only if every f ∈ W can be reduced by G to 0. So a Gr¨obner basis of W generates the D-module W.

(ii) If G is a Gr¨obner basis of W, f ∈ F, then f ∈ W if and only if f can be reduced by G to 0.

(iii) If G is a Gr¨obner basis of W, then f ∈ W is reduced w.r.t.

G if and only if f = 0.

27

Def. 3.6: Let F be a finitely generated free D-module and f, g ∈ F \ {0}. For every Λ_j let V(j, f, g) be a finite system of generators of the K[Λ_j]-module

K[Λ_j]hlt(λf)|lt(λf) ∈ Λ_jE, λ ∈ Λi ∩

K[Λ_j]hlt(ηg)|lt(ηg) ∈ Λ_jE, η ∈ Λi. Then for every generator v ∈ V(j, f, g),

S(j, f, g, v) = v lt_j(f)

f

lc_j(f) − v lt_j(g)

g lc_j(g)

is called an S-polynomial of f and g with respect to j and v.

TheK[Λ_j]-module considered in Definition 3.6 is a “monomial module”, i.e. it is generated by elements containing only one term. Such a module always has a finite “monomial basis”, i.e.

every basis element contains only one term. In the following we assume that V (j, f, g) is such a finite monomial basis.

The computation of V(j, f, g) involves the generalized term order on ΛE. Pauer and Unterkircher (1999) have investigated V (j, f, g) for commutative Laurent polynomial rings and have given algorithms for some important cases. Their results are still valid for difference-differential modules.

28

Ex. 3.3: Let F = D = K[δ₁, δ₂, α₁, α⁻₁¹, α₂, α⁻₂¹] and K = Q(x₁, x₂), where δ₁, δ₂ are the partial derivatives w.r.t. x₁ and x₂, respectively, andα₁, α₂ are two automorphism onK. Choose the generalized term order on N²×Z² as in Example 2.3(c), i.e.

u = δ₁^k1δ₂^k2α^l₁¹α^l₂² ≺ v = δ₁^r1δ₂^r2α^s₁¹α₂^s2

⇐⇒ (kuk, k₁, k₂, l₁, l₂) <_lex (kvk, r₁, r₂, s₁, s₂), where kuk = −min(0, l₁, l₂).

Let

f = α⁻₁² − δ₂, g = δ₁ +α₂⁴.

Note that the orthants of Λ are Λ₀,Λ₁,Λ₂ as described in Exam- ple 2.2 for n = 2. One can see that

{λ ∈ Λ | lt(λf) ∈ Λ₀} = Λ₀α²₁ , {η ∈ Λ | lt(ηg) ∈ Λ₀} = Λ₀ and

{lt(λf) ∈ Λ₀ | λ ∈ Λ} = Λ₀δ₂α²₁, {lt(ηg) ∈ Λ₀ | η ∈ Λ} = Λ₀δ₁.

Then V (0, f, g) = {v₀} = {δ₁δ₂α²₁} and by Definition 3.6, S(0, f, g, v₀) = δ₁α²₁f + δ₂α²₁g = δ₁ +δ₂α²₁α⁴₂. Similarly we have

{λ ∈ Λ | lt(λf) ∈ Λ₁} = Λ₁α₁ , {η ∈ Λ | lt(ηg) ∈ Λ₁} = Λ₁ and

{lt(λf) ∈ Λ₁ | λ ∈ Λ} = Λ₁α₁⁻¹, {lt(ηg) ∈ Λ₁ | η ∈ Λ} = Λ₁δ₁. Then V (1, f, g) = {v₁} = {δ₁α⁻₁¹} and

S(1, f, g, v₁) = δ₁α₁f − α⁻₁¹g = −δ₁δ₂α₁ − α⁻₁¹α₂⁴.

29

Finally,

{λ ∈ Λ | lt(λf) ∈ Λ₂} = Λ₂α²₁, {η ∈ Λ | lt(ηg) ∈ Λ₂} = Λ₂α⁻₂¹, {lt(λf) ∈ Λ₂ | λ ∈ Λ} = Λ₂δ₂α²₁, {lt(ηg) ∈ Λ₂ | η ∈ Λ} = Λ₂δ₁α₂⁻¹. Then V (2, f, g) = {v₂} = {δ₁δ₂α₁α⁻₂¹} and

S(2, f, g, v₂) = δ₁α₁α⁻₂¹f +δ₂α₁α⁻₂¹g = δ₁α⁻₁¹α⁻₂² +δ₂α₁α³₂.

30

For the proof of the Generalized Buchberger Theorem we need the following lemmas.

Lemma 3.4: Let f₁,· · ·, f_l ∈ F and a₁,· · ·, a_l ∈ K. If Pl

j=1a_j = 0 , then

l

X

j=1

a_jr_j =

l−1

X

j=1

b_j(f_j − f_j+1) for some b_j ∈ R.

Lemma 3.5: Let g_i, g_k ∈ F and lt(λg_i) = lt(ηg_k) = u ∈ Λ_jE, where λ, η ∈ Λ. Then there exists ζ ∈ Λ_j and v ∈ V(j, g_i, g_k), such that u = ζv. Therefore if G is a finite subset of F\{0} and the S-polynomial S(j, g_i, g_k, v) can be reduced to 0 by G then

ζS(j, g_i, g_k, v) = u lt_j(g_i)

g_i

lc_j(g_i) − u lt_j(g_k)

g_k

lc_j(g_k) = X

g∈G

h_gg

with lt(h_gg) ≺ u for g ∈ G.

31

Theorem 3.2 (Generalized Buchberger Theorem) Let F be a free D-module and ≺ be a generalized term order on ΛE, G be a finite subset of F\{0} and W be the submodule in F generated by G. Then G is a Gr¨obner basis of W if and only if for all Λ_j, for all g_i, g_k ∈ G and for all v ∈ V(j, g_i, g_k), the S-polynomials S(j, g_i, g_k, v) can be reduced to 0 by G.

32

Theorem 3.3 (Buchberger Algorithm)Let F be a free D- module and ≺ be a generalized term order on ΛE, G be a finite subset of F\{0} and W be the submodule in F generated by G.

For each Λ_j and f, g ∈ F\{0} let V(j, f, g) and S(j, f, g, v) be as in Definition 3.6. Then by the following algorithm a Gr¨obner basis of W can be computed:

Input: G = {g₁,· · ·, g_µ}, a set of generators of W Output: G⁰ = {g₁⁰,· · ·, g_ν⁰}, a Gr¨obner basis of W Begin

G₀ := G

While ∃f, g ∈ G_i, v ∈ V (j, f, g) s.t.

S(j, f, g, v) reduces to r 6= 0 by G_i Do G_i+1 := G_i ∪ {r}

If G_i+1 = G_i then G_i+1 = G⁰ End

33

Ex. 3.5: Let F and the generalized term order on Λ be as in Example 3.3. Let G = {g₁, g₂, g₃} = {α⁴₂+ 1, α²₁−1, α²₁α⁴₂+ 1}. Then G is a Gr¨obner basis of the submodule W generated by G.

To prove this, we must show that all S-polynomials of G can be reduced to 0 by G.

Following the method described in Example 3.3, we have V (0, g₁, g₂) = {α²₁α⁴₂}, V (1, g₁, g₂) = {α⁻₁¹α³₂}, V (2, g₁, g₂)=

{α₁α⁻₂¹}. So

S(0, g₁, g₂, α²₁α⁴₂) = α²₁g₁ − α⁴₂g₂ = α²₁ +α⁴₂ = g₁ +g₂, S(1, g₁, g₂, α⁻₁¹α³₂) = α⁻₁¹α⁻₂¹g₁ +α⁻₁¹α³₂g₂ =

α⁻₁¹α⁻₂¹ +α₁α³₂ = (α⁻₁¹α⁻₂¹)g₃, S(2, g₁, g₂, α₁α₂⁻¹) = α₁α⁻₂¹g₁ −α₁⁻¹α⁻₂¹g₂ =

α⁻₁¹α⁻₂¹ +α₁α³₂ = (α⁻₁¹α⁻₂¹)g₃.

Furthermore, V (0, g₁, g₃) = {α²₁α⁴₂}, V(1, g₁, g₃) = {α⁻₁¹α³₂}, V (2, g₁, g₃) = {α⁻₂¹}. So

S(0, g₁, g₃, α²₁α⁴₂) = α²₁g₁ − g₃ = α²₁ −1 = g₂, S(1, g₁, g₃, α⁻₁¹α³₂) = α⁻₁¹α₂⁻¹g₁ − α⁻₁¹α³₂g₃ =

α⁻₁¹α₂⁻¹ − α₁α⁷₂ = (α⁻₁¹α⁻₂¹)g₃ − α₁α³₂g₁,

(note that the r.h.s. of this equation satisfies the condition in Theorem 3.1 (i), i.e. lt(h_ig_i) lt(S))

S(2, g₁, g₃, α⁻₂¹) = α⁻₂¹g₁ −α⁻₂¹g₃ = α³₂ − α²₁α³₂ = −α³₂g₂.

34

Finally, V (0, g₂, g₃) = {α²₁α₂⁴}, V (1, g₂, g₃) = {α⁻₁¹}, V (2, g₂, g₃) = {α₁α⁻₂¹}. So

S(0, g₂, g₃, α²₁α⁴₂) = α⁴₂g₂ − g₃ = −α⁴₂ − 1 = −g₁, S(1, g₂, g₃, α⁻₁¹) = α⁻₁¹g₂ − α⁻₁¹g₃ = α₁α⁴₂ + α₁ =

α₁g₁,

S(2, g₂, g₃, α₁α⁻₂¹) = α⁻₁¹α⁻₂¹g₂ − α₁α⁻₂¹g₃ =

−α⁻₁¹α⁻₂¹ − α³₁α³₂ = α⁻₁¹α⁻₂¹g₃ +α₁α³₂g₂.

The r.h.s. of this equation also satisfies the condition in Theorem 3.1 (i). So, by Theorem 3.2, G is a Gr¨obner basis of W.

35

References

[1] T. Becker, V. Weispfenning. Gr¨obner bases. A Computa- tional Approach to Commutative Algebra. Spinger-Verlag, New York (1993).

[2] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem null- dimensionalen Polynomideal. Ph.D. dissertation, Univ.

Innsbruck, Austria (1965).

[3] B. Buchberger. Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal.J. Symb. Comp.

41/3-4, 475–511 (2006).

[4] D. Cox, J. Little, D. O’Shea. Ideals, Varieties, and Algo- rithms, 2nd ed. Springer-Verlag (1997)

[5] A. Galligo. Some algorithmic questions on ideals of differ- ential operators. Proc. EUROCAL’85, B.F. Caviness (ed.), LNCS 204, 413-421, Springer-Verlag, Berlin (1985).

[6] M. Insa, F. Pauer. Gr¨obner bases in rings of differential oper- ators. In Gr¨obner Bases and Applications, B. Buchberger and F. Winkler (eds.), 367-380, Cambridge University Press (1998).

[7] M.V. Kondrateva, A.B. Levin, A.V. Mikhalev and E.V.

Pankratev. Differential and Difference Dimension Poly- nomials. Kluwer Acad. Publ., Dordrecht (1998).

36

[8] A.B. Levin. Reduced Gr¨obner bases, free difference- differential modules and difference-differential dimension polynomials. J. Symb. Comput. 30/4, 357-382 (2000).

[9] T. Mora. Gr¨obner bases for non-commutative polynomial rings. In Proc. AAECC-3, J. Calmet (ed.), LNCS 229, 353- 362, Springer-Verlag (1986).

[10] M. Noumi. Wronskian determinants and the Gr¨obner repre- sentation of linear differential equations. In Algebraic Anal- ysis, M. Kashiwara, T. Kawai (eds.), 549-569, Academic Press, Boston (1988).

[11] T. Oaku, T. Shimoyama. A Gr¨obner basis method for mod- ules over rings of differential operators. J. Symb. Comput.

18/3, 223-248 (1994).

[12] F. Pauer, A. Unterkircher. Gr¨obner bases for ideals in Lau- rent polynomial rings and their applications to systems of difference equations. AAECC 9, 271-291 (1999).

[13] N. Takayama. Gr¨obner basis and the problem of contiguous relations. Japan J. Appl. Math. 6, 147-160 (1989).

[14] F. Winkler. Polynomial Algorithms in Computer Algebra.

Springer-Verlag, Wien New York (1996).

[15] M. Zhou, F. Winkler. Gr¨obner bases in difference-differential modules and their applications. Techn.Rep. 05-14, RISC, J.Kepler Univ. Linz, Austria (2005).

37