• Keine Ergebnisse gefunden

Gr¨obner Bases for Ideals in Laurent Polynomial Rings and their Application to Systems of Difference Equations

N/A
N/A
Protected

Academic year: 2022

Aktie "Gr¨obner Bases for Ideals in Laurent Polynomial Rings and their Application to Systems of Difference Equations"

Copied!
21
0
0

Wird geladen.... (Jetzt Volltext ansehen)

Volltext

(1)

Gr¨obner Bases for Ideals in Laurent Polynomial Rings and their Application to Systems of Difference Equations

Franz Pauer1, Andreas Unterkircher2

1Institut f¨ur Mathematik, Universit¨at Innsbruck, Technikerstrasse 25, A-6020 Innsbruck, Austria, (e-mail: [email protected])

2Institut f¨ur Umformtechnik, ETH Z¨urich, Tannenstrasse 3, CH-8092 Z¨urich, Switzerland, (e-mail: [email protected])

Received: January 20, 1997

Abstract. We develop a basic theory of Gr¨obner bases for ideals in the algebra of Laurent polynomials (and, more generally, in its monomial subalgebras). For this we have to generalize the notion of term order. The theory is applied to systems of linear partial difference equations (with constant coefficients) on Zn. Furthermore, we present a method to compute the intersection of an ideal in the algebra of Laurent polynomials with the subalgebra of all polynomials.

Keywords: Laurent polynomial ring, groebner basis, generalized term order, partial difference equation

1 Motivation and Introduction

LetRbe a commutative noetherian ring (e. g. a field,ZorZm),0a set, letR0 be theR-module of all maps from 0toR, and letR(0) be theR-submodule of all maps from0toRwith finite support. There is a natural nondegenerate bilinear form

h−,−i:R(0)×R0 −→R, (f, g)7−→X

i∈0

f (i)g(i) .

Let<be a well-order on0. (Then every strictly descending sequence in0is finite). For 06=fR(0)we define the “degree off

deg(f ):=max{i0|f (i)6=0}

(2)

and the “leading coefficient off

lc(f ):=f (deg(f )) . For∅ 6=MR(0)let

deg(M):= {deg(f )|fM, f 6=0} and

M:=

gR0| hf, gi =0, for allfM . ObviouslyMis anR-submodule ofR0.

Definition 1.1 Let {0} 6= WR(0) be a submodule ofR(0). Then a family (vi)i∈deg(W)inW is a “triangular basis of W” if and only ifdeg(vi) = i and lc(vi) = 1, for allideg(W).

Remark 1.1 It is clear that every triangular basis is anR-basis ofW. IfRis a field, then there always exists a triangular basis ofW. Nevertheless, in general it is not possible to compute actually such a basis.

Proposition 1.1 LetW be anR-subspace ofR(0). Assume that there is a tri- angular basis(vi)i∈deg(W)ofW. Then the map

r :W−→R0\deg(W), g 7−→g|0\deg(W)

is anR-linear isomorphism.

Let (ei)i∈0 be the standard basis ofR(0) and lethR0\deg(W). Theng :=

r1(h)can be computed recursively as follows:

Letmbe the smallest element in0.

Ifmdeg(W), theng(m)=0, elseg(m)=h(m).

Leti > mand suppose thatg(j)has already been computed for allj < i. Ifideg(W), theng(i)= heivi, gi, elseg(i)=h(i).

Proof. LetwWsuch thatr(w) = 0. Supposew6=0. Letjbe the smallest element in the support of w. Thenjdeg(W) and w(j) = hvj, wi = 0.

Contradiction. Hencer is injective.

Leti0 and1 := {j0|j < i, (eivi)(j)6=0}. Then 1is finite.

Sincelc(vi) = 1 we haveheivi, gi = heivi,P

j∈1g(j)eji, hence the recursive definition (with respect to the well-order<) ofgR0 given above is correct.

It remains to show thatgW. If not, then the set jdeg(W)| hvj, gi 6=0 would not be empty. Letibe its smallest element. Then

06= hvi, gi = heiei+vi, gi = hei, gi − heivi, gi =g(i)g(i)=0.

Contradiction.

(3)

Now we consider important special cases of the situation above: Let0be a submonoid of(Zn,+), for instance0=Zn−m×Nm, Zn, Nn. In this caseR(0) can be considered as the (monomial) subalgebra R[xi;i0] generated by the set

nxi =x1i1. . . xnin|i0o

in the algebraR[x1, . . . , xn, x11, . . . , xn1] of Laurent polynomials. We then writeP

i∈0f (i)xiR[xi;i0] instead of fR(0).

LetWR[xi;i0] be an ideal generated by elementsf1, . . . , fkR[xi;i0] . Then the set

xifj|i0,1≤jk is a system of generators of theR-moduleW. Hence

W =

gR0| ∀i ∈0,∀j, hxifj, gi =0

= (

gR0| ∀i∈0,∀j,X

s∈0

fj(s)g(s+i)=0 )

,

i.e.Wis the set of solutions of the system of difference equations X

s∈0

fj(s)g(s+i) = 0, 1≤jk, i0 (wheregR0is the unknown function).

We extend this to a slightly more general situation: LetBbe a finite set, let00 be a submonoid of(Zn,+), and let0:=00×B. ThenR(0)can be considered as the free R[xi;i00] -moduleV :=L

b∈B R[xi;i00]b. We then write P

i∈00,b∈Bf (i, b)xibV instead offR(0).

LetWV be an R[xi;i00] -submodule ofV, generated by elements f1, . . . , fkV. Then the set

xifj|i00,1≤jk is a system of R- module generators ofW. Hence

W= (

gR0| ∀i ∈00, ∀j, X

s∈00

X

d∈B

fj(s, d)g(s+i, d)=0 )

,

i.e.Wis the set of solutions of the system of difference equations X

(s,d)∈0

fj(s, d)g(s+i, d) = 0, 1≤jk, i00

(wheregR0 ∼=(RB)00 is the unknown function).

IfRis a field, Proposition 1.1 reduces the problem of solving this system of difference equations to the problem of computingdeg(W)and a triangular basis ofW. If0 = Nn(orNn×B) and<is a term order, this can be done by com- puting a Gr¨obner basis ofW. This was first observed and applied by U. Oberst in [4]. The case0 = Znwas treated in [11] and in [10]. The method there was to consider the algebra of Laurent polynomialsR[x1, . . . , xn, x−11 , . . . , xn−1] as the factor algebra

R[x1, . . . , xn, y1, . . . , yn]/hx1y1−1, . . . , xnyn−1i

(4)

and to compute a Gr¨obner basis of the inverse image of the idealW in R[x1, . . . , xn, y1, . . . , yn].

The aim of this paper is to present a direct method: we define Gr¨obner bases with respect to generalized term orders for ideals in the algebra of Laurent polynomials (and, more generally, in its finitely generated monomial subalge- bras). For the sake of completeness we do not restrict ourselves to the case of coefficient fields, but admit coefficients in a commutative noetherian ring R. Of course, if we want to compute Gr¨obner bases, we have to assume ad- ditionally that we can solve linear equations over R, i.e. for given elements r, r1, r2, . . . , rkRwe should be able to decide ifris anR-linear combination ofr1, r2, . . . , rk, and if so, to compute a parameter form of the affine subspace {s ∈Rk|Pk

i=1risi=r}ofRk.

Gr¨obner bases for ideals in the algebra of Laurent polynomials over Z have first been considered in [8], Chapter 10.7. There they were defined with respect to a specified well-order on the set of Laurent-monomials. Our approach extends an idea of S. Zampieri, who introduced generalized term orders on the set of monomials in a polynomial ring in view of applications to the modelling problem in system theory [6]. Gr¨obner bases for monomial subalgebras of polynomial rings have been studied in [9], Chapter 11. A slightly more general situation (monomial algebras with no non-constant invertible elements) has been treated in [7], Chapter 3.

LetRbe a commutative noetherian ring, letT be a finitely generated sub- monoid of the group {xi|iZn}of power-products in the ring of Laurent polynomialsR[x1, . . . , xn, x11, . . . , xn1], and letR[T] be a subalgebra gener- ated byT. In Section 2 we define generalized term orders onT and Gr¨obner bases (with respect to them) for submodules of finite-dimensional freeR[T]- modules. We present a method to compute the intersection of an ideal in the ring of Laurent polynomials with the subring of all polynomials. (This answers a question of G. Traverso). In Section 3 we formulate and prove an analogon of Buchberger’s Algorithm for the computation of Gr¨obner bases. In Section 4 several examples are discussed, among them those given in [10] and [11]. For the latter our method yields the results without essential computations.

We assume the reader to be familiar with the theory of Gr¨obner bases with respect to term orders (see [2], [1] or [3]).

2 Gr¨obner Bases with Respect to Generalized Term Orders LetRbe a commutative noetherian ring, letnN>0, and let

R[x, x1] :=R[x1, . . . , xn, x11, . . . , xn1]

(5)

be the commutative ring of Laurent polynomials overR. The set nxi :=x1i1x2i2. . . xnin|iZno

of power-products (or terms) inR[x, x1]is a group, isomorphic toZn. Let T be a finitely generated submonoid of

xi|iZn , e.g.

T =

xi|iZn orT =

xi|iZm×Nn−m .

Definition 2.1 (conic decomposition) A “conic decomposition” of T is a finite family(Ti)i∈I of finitely generated submonoids ofT, such that

for eachiI the group generated byTi containsT,

for eachiI the monoidTicontains only one invertible element, and [

i∈I

Ti = T .

Example 2.1 LetT :=

xi|iZn and letD be the set of all maps from {1, . . . , n} to { −1,1}. FordDdefine

Td := n

x1d(1)m1x2d(2)m2. . . xnd(n)mn|m1, . . . , mnNo . Then(Td)d∈D is a conic decomposition ofT.

Example 2.2 LetT00 :=

xi|iNn and letTj0be the monoid generated by {x11x22. . . xn1} ∪ {x1, x2, . . . , xn} \ {xj},

1≤jn. Then(Tj0)0≤j≤nis a conic decomposition ofT :=

xi|iZn . The following figures illustrate the conic decompositions defined above for n=2:

. . . r . . . . . . r . . . . . . r . . . r r r r r r r . . . r . . . . . . r . . . . . . r . . .

T1

T2

T3 T4

. . . . . . . . . . . . . . . r r r r . . . r . . . . . . r . . . . . . r . . .

T00 T10

T20

Notation. For a submonoidSof

xi|iZn let R[S] :=

(X

s∈S

css|csR )

R[x, x1]

be the subalgebra ofR[x, x1] generated byS. (If we use the notationP

s∈Scss we always assume that only finitely manycs are not zero). ThenR[S] is the

“monomial algebra defined byS”.

(6)

Let V be a finite-dimensional free R[T]-module with basis B and let U := {tb|tT , bB}. If (Ti)i∈I is a conic decomposition of T, let Ui:= {tb|tTi, bB},iI.

(IfV = R[T] andB = {1}, thenUi = Ti, for alliI).

Definition 2.2 (generalized term order) Let(Ti)i∈Ibe a conic decomposition ofT. A “generalized term order” onUfor(Ti)i∈Iis a total order<onUsuch that

bis the smallest element in{tb|tT}, for allbB, and

r < simpliestr < ts, for alliI,sUi,tTi, andrU. Remark 2.1 If |I| = 1 and T =

xi|iNn , thenT is a (trivial) conic decomposition ofT. In this case any generalized term order is a term order.

Remark 2.2 Let (Ti)i∈I be a conic decomposition of T, V = R[T], and B = {t}, wheret is an invertible element ofT. ThenUi = tTi andt is the minimal element inT = U with respect to every generalized term order for (Ti)i∈I.

The following Lemma shows how to construct a generalized term order on T and onU.

Lemma 2.1 Let(Ti)i∈I be a conic decomposition ofT and letS := {1}or S := Tj for somejI. Let<Gbe a total group order onG:=

xi|iZn such that 1 is the smallest element inSand let<B be a total order onB. Let f :T −→Q0be a function fulfilling the following conditions:

1. for alltT \S:f (t) >0,

2. for alls, tT:f (st)f (s)+f (t),

3. for alliI:f|Ti is a monoid-homomorphism.

Then the order<T defined by

r <T s :⇐⇒ f (r) < f (s) or (f (r)=f (s) and r <Gs), for allr, sT, is a generalized term order onT for(Ti)i∈I.

The order defined by

rb <U sc:⇐⇒ r <T s or (r =s and b <B c), for allr, sT , b, cB, is a generalized term order onU for(Ti)i∈I. Proof. Conditions 1 and 3 forf imply that 1 is the smallest element inT. Let rT,iI,s, tTisuch thatr <T s. Then

f (r) < f (s)orf (r)=f (s)andr <Gs.

In the first case we have

f (rt)f (r)+f (t) < f (s)+f (t)=f (st)

(7)

hencert <T st. In the second case we have

f (rt)f (r)+f (t)=f (s)+f (t)=f (st)andrt <Gst

(since<Gis a group order), hencert <T st.

Example 2.3 Let(Td)d∈Dbe the conic decomposition defined in Example 2.1.

Define

f (x1i1x2i2. . . xnin):= |i1| + |i2| +. . .+ |in| and

x1i1x2i2. . . xnin <G x1j1x2j2. . . xnjn if and only if(i1, i2, . . . , in)is lexicographically smaller than(j1, j2, . . . , jn). Then<T (defined byf and<G) is a generalized term order onT for(Td)d∈D.

Example 2.4 Let(Tj)0≤j≤nbe the conic decomposition defined in Example 2.2. Define

f (x1i1x2i2. . . xnin):=i1+. . .+in(n+1)min{0, i1, i2, . . . , in} and define<G as in Example 2.3. Then<T is a generalized term order onT for(Tj)0≤j≤n.

Example 2.5 Let(Tj)0≤j≤nand<G be as in Example 2.4. Define f (x1i1x2i2. . . xnin):= −min{0, i1, i2, . . . , in}.

Then<T is a generalized term order onT for(Tj)0≤j≤n. All elements ofT0are smaller than any element ofT \T0.

Lemma 2.2 (see [6], Lemma 2.3) Every strictly descending sequence inT is finite. In particular, any subset ofT contains a smallest element.

Proof. Lets1> s2> s3> . . .be a strictly descending sequence inT. SinceI is finite, it is sufficient to prove the assertion under the assumption that allsj

are elements ofTi. But then for allj there exists notTisuch thatsj = tsk

for somek < j. In particular, the sequence

hs1i ⊂ hs1, s2i ⊂ hs1, s2, s3i ⊂. . .

of ideals inZ[Ti] is strictly increasing. Since the monoidTiis finitely generated, the ringZ[Ti] is noetherian. This yields the assertion.

Definition 2.3 Let(Ti)i∈I be a conic decomposition ofT and let<be a gen- eralized term order for(Ti)i∈I. Letf = P

u∈Ucuube a non-zero element in V,cuR. Then we define

supp(f ):= {uU|cu6=0}(the “support off”), lt(f ):= maxsupp(f )(the “leading term off”), lc(f ):= clt(f ), (the “leading coefficient off”),

lm(f ):= lc(f )lt(f )(the “leading monomial off”), and Ti(f ):= {tT|lt(tf )Ui},iI.

(8)

Definition 2.4 (Gr¨obner basis) LetW be anR[T]-submodule ofV andGa finite subset ofW \ {0}.

ThenGis a Gr¨obner basis ofW(with respect to a conic decomposition(Ti)i∈I

ofT and a generalized term order <on U) if and only if for all iI the R[Ti]-module

R[Ti]hlm(f );f 6=0, f ∈W, lt(f )Uii is generated by

{lm(tg); gG, tTi(g)}.

Example 2.6 LetfV\{0}andW := R[T]f. IfRis a domain, then {f} is a Gr¨obner basis ofW (with respect to every generalized term order). But for R := Z4,V := Z4[x1],f := 2x1+1, andW :=Z4[x1]f,the set {f} is not a Gr¨obner basis ofW, since 2f = 2 ∈ W.

Proposition 2.1 Let G be a Gr¨obner basis of an ideal W in R[x1, . . . , xn, x11, . . . , xn1] with respect to the generalized term order<T defined in Example 2.5. ForgR[x1, . . . , xn, x11, . . . , xn1] lett(g)T be the uniquely determined power-product such that

\

s∈supp(g)

s1T0 = t(g)T0.

Then{t(g)g|g∈G}is a Gr¨obner basis ofWR[x1, . . . , xn].

Proof. LetfW. Since<T is the order defined in Example 2.5,lt(f )T0

impliessupp(f )T0, i.e.fR[x1, . . . , xn]. Hence

R[x1,...,xn]hlm(f );f 6=0, fW, lt(f )T0i

=R[x1,...,xn]hlm(f );f 6=0, fWR[x1, . . . , xn]i.

LettT0(g)andgG. Thenlt(tg)T0andsupp(tg)T0. Therefore

t ∈ \

s∈supp(g)

s1T0

and there is anuT0such thatt =t(g)u. Hence{lm(tg);gG, tT0(g)}

and{lm(t(g)g);gG}generate the same ideal inR[x1, . . . , xn].

Remark 2.3 Proposition 2.1 yields a method to compute generators of the ideal WR[x1, . . . , xn], see Example 4.1.

Lemma 2.3 (See [6] , Lemma 2.1 and Lemma 2.2)

1. LetN be a finite subset ofT and letiI. Then there is apTisuch that pNTi.

2. Let 0 6=fV,s, tTi(f ), and letu, vsupp(f )such thatlt(tf ) = tuUi,lt(sf ) = svUi. Thenu = v.

(9)

Proof. 1. The group generated byTicontainsT, hence for everytN there arert, stTi such thatrt1st = t. Then takep:= Q

t∈NrtTi.

2. Sinceu, vsupp(f ), tvtu andsusv. Choose pTi such that pu, pvUiandps, ptTi(see 1). Then

tuUi, tvtu, p2Ti imply p2tvp2tu , and

svUi, susv, p2Ti imply p2sup2sv.

Hence

(pt)(pv)(pt)(pu)and (ps)(pu)(ps)(pv) . This implies

(ps)(pt)(pv)(ps)(pt)(pu)and (pt)(ps)(pu)(pt)(ps)(pv) ,

therefore(ps)(pt)(pv) = (pt)(ps)(pu)andu = v.

Definition 2.5 Let 06=fV,iI andtTi(f ). Then define lti(f ):= lt(tf )

t , lci(f ):= lc(tf )andlmi(f ):= lci(f )lti(f ) . Remark 2.4 By Lemma 2.3, lti(f ) is well-defined (i.e. does not depend on the choice oftTi(f )). Furthermore,lci(f )is the coefficient off atlti(f ).

We can compute lti(f ) in the following way: choosepTi such that p.supp(f )Ui(cf. Lemma 2.3). Thenlt(pf )Uiandlti(f ) = lt(pf )p .

For the computation of the setsTi(f )see chapter 4.

3 Buchberger’s Algorithm for Generalized Term Orders

We maintain the notations of Section 2 and fix a conic decomposition(Ti)i∈I ofT and a generalized term order<onU.

Definition 3.1 LetF be a finite subset of V \ {0}and let 0 6= (hf)f∈F be a family inR[T]. Then

uF((hf)f∈F):= max



tv|(t, v)∈ [

f∈F

(supp(hf)×supp(f ))



.

Remark 3.1 Consider two families 0 6= (hf)f∈F, 0 6=(h0f)f∈F inR[T]. Let u:= uF((hf)f∈F)andu0 := uF((h0f)f∈F. Then

uF((hf +h0f)f∈F)max{u, u0}. (Ifu6=u0, thenuF((hf +h0f)f∈F) = max{u, u0}).

(10)

IfuUiandtTi, then

uF((thf)f∈F) = tuUi. Ifu0Ui,u < u0andtTi, then

uF((thf)f∈F) < tu0.

IfcRand(chf)f∈F 6=0, thenuF((chf)f∈F)u. (Ifcis not a zero-divisor inR, thenuF((chf)f∈F) = u).

Proposition 3.1 LetF be a finite subset ofV \ {0}and letgV. Then there is a family(hf)f∈F inR[T]such that

(hf)f∈F =0or uF((hf)f∈F) = lt(g) and

g = X

f∈F

hff or lm(g−X

f∈F

hff ) 6∈ [

i∈I

R[Ti]hlm(tf );fF, tTi(f )i . The family(hf)f∈F can be computed as follows (“Division algorithm”):

First sethf :=0, f ∈F.

While there arecfR, tfT such that lm(g) = P

f∈F cflm(tff ), replacehf byhf +cftf andgbyg−P

f∈Fcftff.

(Note that this “algorithm” is effective only under the hypothesis that we can solve linear equations overR).

Proof. We only have to show that the algorithm above terminates after a finite number of steps. But since in each step lt(g−P

f∈Fcftff ) < lt(g), this

follows from Lemma 2.2 .

Definition 3.2 LetF, g, hf be as in the proposition above. Then rem(g, F ):= g−P

f∈F hff is “a remainder on division ofgbyF”.

(It is clear thatrem(g, F )is not uniquely determined bygandF).

Proposition 3.2 LetW be a non-zero submodule ofV . 1.W contains a Gr¨obner basis.

2. LetGbe a Gr¨obner basis ofW. ThenfV is an element ofW if and only if a remainder (or all remainders) on division off byGis zero.

3. Each Gr¨obner basis ofW generates theR[T]-moduleW.

Proof. 1. For alliI choose a finite subsetEiof{lm(f )|f 6=0, fW, lt(f )Ui}which generates the R[Ti]-submoduleR[Ti]hlm(f );0 6= f, fW, lt(f )Uii. Then

(

fW|lm(f )∈[

i∈I

Ei

)

(11)

is a Gr¨obner basis ofW. 2. follows from Proposition 3.1.

3. follows from 2.

Remark 3.2 LetiI and letEV \ {0}. Then

\

g∈E

R[Ti]hlt(tg); tTi(g)i = {0}

if and only if there are elementsf, gEsuch thatlti(f )=lti(f )b,lti(g)= lti(g)c, wherelti(f )T,lti(g)T,bB,cBandb6=c.

Proposition 3.3 LetG be a finite subset ofV \ {0}and let W be theR[T]- submodule ofV generated byG. ForiI andEGletS(i, E)be a finite system of generators of theR-module



(cg)g∈ERE|X

g∈E

cglci(g) = 0



and let U(i, E)Ui be a finite system of generators of theR[Ti]-module

\

g∈E

R[Ti]hlt(tg); tTi(g)i (i.e.U(i, E)= ∅orT

g∈ETi(g)lti(g) = Ti.U(i, E)). Then the following assertions are equivalent:

(1)Gis a Gr¨obner basis ofW.

(2) For alliI, for allEGsuch thatU(i, E)6= ∅, for alls =(sg)g∈GS(i, E), and for allvU(i, E):

rem

X

g∈E

sg v lti(g)g, G

 = 0.

(Hereltv

i(g)meansltv

i(g), wherevandlti(g)are the power-products inR[T]with vb =vandlti(g)b=lti(g), for somebB, see Remark 3.2).

Proof. (1)(2) : SinceP

g∈Ecsltiv(g)gis an element ofW, the assertion follows from Proposition 3.2.

(2)(1): LetfW,f 6=0. We have to show lm(f ) ∈ [

i∈I

R[Ti]hlm(tg);gG, tTi(g)i. SinceW is generated byG, we have

f = X

g∈G

hgg ,

(12)

for somehgR[T].

Letu:= uG((hg)g∈G). We choose the family(hg)g∈Gsuch thatuis minimal, i.e. if

f = X

g∈G

h0gg

thenuuG((h0g)g∈G).

LetjI be such thatuUjand let E :=

gG| there is a p(g)supp(hg)such thatp(g)ltj(g) = u . ThenE is not empty and for allgE we have p(g)Tj(g). LetcgR be the coefficient ofhgatp(g). Ifcglcj(g) 6=0, thenlm(hgg) = cglcj(g)u, otherwisehgg = 0 orlt(hgg) < u. It is clear thatlt(f )u.

Iflt(f ) = u, then

E0:=

gE|lt(hgg)=u is not empty and

lm(f ) = X

g∈E0

lm(hgg) = X

g∈E0

cglm(p(g)g)R[Tj]hlm(tg);gG, tTj(g)i.

Hence it remains to show thatlt(f )cannot be smaller thanu. Iflt(f ) < u, then X

g∈E

cglci(g) = 0.

Hence there is a family(ds)s∈S(j,E)inRsuch that (cg)g∈G = X

s∈S(j,E)

dss ,

i.e. for allgE,cg = P

s∈S(j,E)dssg. ForgEdefinehg := cgp(g), for gG\Elethg:= 0. Then

f = X

g∈G

hgg = X

g∈G

(hghg)g+X

g∈E

hgg

and

uG((hghg)g∈G) < u . Now consider

X

g∈E

hgg = X

g∈E

cgp(g)g = X

s∈S(j,E)

ds

X

g∈E

sgp(g)g .

(13)

For gE we have p(g)ltj(g) = uUj and p(g)Tj(g), thus u ∈ T

g∈ETj(g)ltj(g). Hence there are vU(j, E)Uj andrTj such that r.v = u. Letq(g)Tj(g)be such thatv =q(g)ltj(g), i.e.

q(g) = v ltj(g). Then

r·q(g)ltj(g) = r·v = u = p(g)ltj(g) , hencep(g) = r·q(g)and

X

g∈E

hgg = X

s∈S(j,E)

dsrX

g∈E

sgq(g)g .

By (2), for everysS(j, E)there is a family(kg,s)g∈GinR[T]such that X

g∈E

sgq(g)g = X

g∈G

kg,sg

and

uG((kg,s)g∈G) = lt

X

g∈E

sgq(g)g

 =:w(s) .

For allgEwe havelt(q(g)g) = vUj and moreoverP

g∈Esglcj(g)=0.

Hencew(s) < vUj. SincerTj, this implies uG((rkg,s)g∈G) < r·v=uUj

(see Remark 3.1). Thus X

g∈E

hgg = X

g∈G

 X

s∈S(j,E)

dsrkg,s

g ,

and

uG

 X

s∈S(j)

dsrkg,s

g∈G

< u

(see Remark 3.1). For allgGlet

h0g := (hghg)+ X

s∈S(j,E)

dsrkg,s,

then

uG((h0g)g∈G) < u and f = X

g∈G

h0gg ,

which contradicts the minimality ofu.

(14)

Proposition 3.4 LetRbe a principal ideal domain (e.g. a field). LetG be a finite subset ofV\ {0}and letW be theR[T]-submodule ofV generated byG.

ForiI andf, gGlet U(i, f, g)Ui be a finite system of generators of theR[Ti]-module

R[Ti]hlt(tf );tTi(f )i ∩R[Ti]hlt(tg);tTi(g)i

(i.e.U(i, E)= ∅orTi(f )lti(f )∩Ti(g)lti(g) = Ti.U(i, f, g)) and letLi(f, g) be a least common multiple oflci(f )andlci(g). ForvU(i, f, g)define

S(i, f, g, v):= Li(f, g) lci(f )

v

lti(f )fLi(f, g) lci(g)

v

lti(g)gW . Then the following assertions are equivalent:

(1)Gis a Gr¨obner basis ofW.

(2) For alliI, for allf, gG, and for allvU(i, f, g) rem(S(i, f, g, v), G) = 0.

Proof. LetEGbe a subset with at least two elements and let

δg|gERE be the standard-basis of RE . If R is a principal ideal domain, then nLi(f,g)

lci(f )δfLlci(f,g)i(g) δg|f, gEo

is a finite system of generators of



(cg)g∈ERE|X

g∈E

cglci(g) = 0



(see for example [5], Lemma 3.4). Hence Proposition 3.4 is a Corollary of

Proposition 3.3 .

Proposition 3.5 (Buchberger’s Algorithm) LetGbe a finite subset ofV\{0} and letW be theR[T] -submodule generated byG. ForiI andEGlet S(i, E)be a finite system of generators of theR-module



(cg)g∈ERE| X

g∈E

cglci(g) = 0



and

let U(i, E)Ui be a finite system of generators of theR[Ti]-module

\

g∈E

R[Ti]hlt(tg); tTi(g)i (i.e.U(i, E)= ∅orT

g∈ETi(g)lti(g) = Ti.U(i, E) ).

By the following algorithm a Gr¨obner basis ofW can be computed:

G0:= G,

Gj+1:= Gj({rem(P

g∈Esg v

lti(g)g, Gj)|iI, EGj, sS(i, E), vU(i, E)} \ {0}.

IfGj+1 = Gj, thenGj is a Gr¨obner basis ofJ.

(15)

Proof. By Proposition 3.3 we only have to show that there is akNsuch that Gk =Gk+1. Suppose there is no suchk. Then there is an indexiIsuch that for alljNthere is amNsuch that theR[Ti] -submodulehlm(tg); gGj, tTi(g)iofL

b∈BR[Ti]bis strictly contained inhlm(tg); gGj+m, tTi(g)i. SinceR[Ti] is noetherian, this is not possible.

4 Examples

LetF be a finite subset ofV \ {0}. In order to compute a Gr¨obner basis of the submodule generated byF, we first have to determine the setsTi(f ), for all iI,fF. For that purpose we use the facts that

T = [

i∈I

Ti(f )

and

Ti.Ti(f ) = Ti(f ), for alliI, as well as the following two lemmas.

Lemma 4.1 Let(Ti)i∈I be a conic decomposition ofT such that

grhTiTji ∩Ti = TiTj

for alli, jI. (Here grhTiTjiis the subgroup of{xi|i ∈Zn}generated by TiTj). LetfV andi, jI such thatTi(f )Tj(f )6= ∅. Then

lti(f ) = ltj(f ) and

tTi(f ), sTiTj, stTi(f )Tj(f ) imply tTj(f ).

Proof. FromTi(f )Tj(f )6= ∅and the uniqueness oflti(f )andltj(f )we getlti(f ) = ltj(f ) =: l.

Nowlt(tf ) = tlTi andlt(stf ) = stlTiTj. We have to show that tlTj.

Letv:=stl, thentl=s1vgrhTiTji ∩Ti=TiTj. ThustlTj. Lemma 4.2 LetfR[T] and let(Ti)i∈I be a conic decomposition ofT. If there exists a subset∅ 6=JI such that

\

j∈J

Tj = {1}and \

j∈J

Tj(f )6= ∅

then

fT and \

j∈J

Tj(f )= {f1}.

(16)

Proof. Let t ∈ T

j∈JTj(f ). Thenlt(tf ) ∈ T

j∈JTj = {1}. Since 1 is the smallest element inT, we havetf =1 andt =f1. Remark 4.1 The conic decompositions defined in Examples 2.1 and 2.2 fulfill the condition in Lemma 4.1.

Hence, if we take for instance the generalized term order defined in Example 2.3 (withn = 2), the following case cannot occur:T1(f ) = T1, T4(f ) = T4.x12.

. . r . . . . r . . r r r r r r . . . . r . . . .

T4(f ) T1(f )

Remark 4.2 LetT := {xi|i ∈ Z2}and let< be the generalized term order with respect to(T0, T1, T2)defined in Example 2.4. Using Lemma 4.1 it is easy to see that theTi(f )’s are always generated by one element and that only six different cases for(T0(f ), T1(f ), T2(f ))can occur:

1 2 3

4 5 6

Moreover, the intersectionsT

g∈ETi(g).lti(g)(cf. Proposition 3.3) are gen- erated by one element, i.e. the setsU(i, E)contain only one element. Conse- quently Buchberger’s algorithm for this generalized term order is particularly simple.

The following algorithm computesT0(f ),T1(f )andT2(f )forfR[T].

Fors =x1i1x2i2T letek(s):=ik, k=1,2.

Algorithm Input:fR[T]

Output:T0(f ), T1(f ), T2(f ) Iff is a monomial then

(17)

T0(f )=T0.f1, T1(f )=T1.f1, T2(f )=T2.f1(Case 1). END Fork=1 to 2 do

mk := −min({ek(s)|ssupp(f )} ∪ {0}) t := x1m1x2m2

While (tT0(f )) do t := t.x11x21 t := t.x1x2

While (t∈T0(f )) do t := t.x11

t := t.x1

While (t∈T0(f )) do t := t.x2−1

t := t.x2

IftT1(f )then

T0(f )=T0.t, T1(f )=T1.t, T2(f )=T2.(t.x21)(Case 2). END IftT2(f )then

T0(f )=T0.t, T1(f )=T1.(t.x11), T2(f )=T2.t (Case 3). END Ift.x11x216∈T1(f )then

T0(f )=T0.t, T1(f )=T1.(t.x11), T2(f )=T2.(t.x11x21)(Case 5). END Ift.x11x216∈T2(f )then

T0(f )=T0.t, T1(f )=T1.(t.x11x21), T2(f )=T2.(t.x21)(Case 6). END T0(f )=T0.t, T1(f )=T1.(t.x11x22), T2(f )=T2.(t.x11x21)(Case 4). END End of Algorithm.

For the conic decomposition defined in Example 2.1 the analogous algo- rithm is slightly more complicated (in this case theTi(f )’s may be generated by more than one element) but still not costly.

Example 4.1 We compute a Gr¨obner basis with respect to the generalized term order defined in Example 2.5 of the idealW generated byf := x12x22+x22 andg:=x1x23+x1x2inQ[x1, x2, x11, x21].

LetF = {f, g}. Now

lt(f )=x12x22T1T2;

lt0(f )=x22, T0(f )=T0·x12x22; lt1(f )=x12x21, T1(f )=T1·x1x2; lt2(f )=x12x21, T2(f )=T2·x1x2;

lt(g)=x1x23T2.

Sincelt(g)T2(f )·lt2(f )we may replacegby

−rem(g,{f})=x13x2x1x2=:h1andF by{f, h1}.

Since

Referenzen

ÄHNLICHE DOKUMENTE

The method of Gr¨ obner bases (see Buchberger, 1965; also Hironaka, 1964) is a technique that provides algorithmic solutions to a variety of problems, for instance, primary

An algorithm to compute Gr¨ obner bases of ideals that are defined by linear forms, which is based on the FGLM algorithm, has proved to be successful in the commutative case and

This concept was used to define a Noetherian reduction in group rings over finitely generated nilpotent rings in Madlener and Reinert (1996) and to generalize Gr¨ obner basis

⇒ local orderings and the generalization of standard basis algorithm, Gr ¨obner basics and homological algebra localization as field of fractions of commutative variables.

Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity.. Signature Gröbner bases:

Since the notion of reduced standard bases exists for ideals in B, then the natural way in order to study our question is in adapting to the D-module case the theory of the Grobner

Buchberger (1965), An algorithm for finding a basis for the residue class ring of a zero-dimensional polynomial ideal, Ph.D. Buchberger, Introduction to Gr¨ obner bases. Win- kler,

• Find monoid or group rings having ideals whose Gr¨ obner bases are difficult to compute. • Encode a hard instance of an action of a group on a set by letting the group act on