# Intersection of Ideals in a Polynomial Ring over a Dual Valuation Domain

Authors: Regis F. Babindamana; Andre S. E. Mialebama Bouesso
Journal: Journal of Mathematics
 (2018)

---

## Abstract

LetV be a valuation domain and let A=V+εV be a dual valuation domain. We propose a method for computing a strong Gröbner basis in R=A[x1,…,xn]; given polynomials f1,…,fs∈R, a method for computing a generating set for Syz(f1,…,fs)={(h1,…,hs)∈Rs∣h1f1+⋯+hsfs=0} is given; and, finally, given two ideals I=〈f1,…,fs〉 and J=〈g1,…,gr〉 of R, we propose an algorithm for computing a generating set for I∩J.


---

## Body

## 1. Introduction

The theory of Gröbner bases initially introduced over the fields (see [1]) is well developed over a great family of rings (see [2–8]). However, many rings are still not part of this family. In this paper, we are interested in the ring of dual valuation domain A=V+εV where V is a valuation domain. This ring is well known in the case of V=R as a typical example of Weil bundle in differential geometry (see the example on page 2 in [9]). Athough the ring V has no zero divisors, the ring A is noetherian and has zero divisors. In this paper, we study this ring in detail and we propose an algorithm for computing strong Gröbner basis for ideals of R. We generalize Schreyer’s theorem which enables us to compute a strong Gröbner basis for Syz(f1,…,fs)⊂Rs when {f1,…,fs} is a strong Gröbner basis for some ideal I⊂R. This important result is used later to compute a generating set for Syz(f1,…,fs)⊂Rs for any arbitrary subset {f1,…,fs}⊂R. The last part of this paper is devoted in the computation of a generating set of the intersection of two ideals; that is, given two ideals I=〈f1,…,fs〉 and J=〈g1,…,gs〉 of R, it is well known that a polynomial f∈I∩J if there exist q1,…,qs,p1,…,pr∈R such that(1)f=q1f1+⋯+qsfs=p1g1+⋯+psgs.Observe that if one can find (q1,…,qs,p1,…,pr)∈Rs+r such that (2)q1f1+⋯+qsfs+p1g1+⋯+psgs=0then the polynomial f can be easily found. The goal of this paper is to compute the set of all the syzygies Syz(f1,…,fs,g1,…,gr)⊂Rs+r which will directly lead to computing a generating set for I∩J.


## 2. Basic Notions

Definition 1 (dual valuation domain).
(i)
A commutative ringV is called valuation domain if it is a domain and whenever a,b∈V∖{0}, we have a∣b or b∣a.(ii)
IfV is a valuation domain, the ring V[ε]/ε2, also denoted as V+εV, is called dual valuation domain.(iii)
Elements ofV+εV are of the form z=a+εb where a,b∈V and ε2=0. We call R(z)=a the real part of z and call I(z)=b the imaginary part of z.Throughout this work, we writeA for the dual valuation domain V+εV and R for the polynomial ring A[x1,…,xn].Lemma 2.
An elementz1∈A divides z2∈A if and only if the following hold in V: (i)
R(z1) divides R(z2).(ii)
R(z1) divides I(z2)-I(z1)·R(z2)/R(z1).Proof.
Assume thatz1 divides z2 in A; then there exists t∈A such that z2=t·z1. That is, R(z2)+εI(z2)=(R(t)+εI(t))(R(z1)+εI(z1)); this leads to(3)Rz2=Rt·Rz1Iz2=Rt·Iz1+It·Rz1
The first equation shows thatR(z1) divides R(z2) and R(t)=R(z2)/R(z1); replacing this in the second equation, we have I(z2)-R(z2)/R(z1)·I(z1)=I(t)·R(z1).
Conversely, ifR(z1) divides R(z2), then we can set c1=R(z2)/R(z1)∈V. Since by hypothesis R(z1) divides also I(z2)-I(z1)·R(z2)/R(z1), there exists d1∈V such that I(z2)-c1I(z1)=d1·R(z1); that is, I(z2)=d1·R(z1)+c1I(z1). We can then write (4)Rz2+εIz2=c1Rz1+εd1·Rz1+c1Iz1=Rz1c1+εd1+εIz1c1.Observe that εI(z1)c1=εI(z1)(c1+εd1); this leads to (5)Rz2+εIz2=c1+εd1Rz1+εIz1That is, z1∣z2.Example 3.
Let us consider the valuation domainV=Z3Z={a/b∣a∈Zandb∉3Z} which is nothing but the localization of Z at the multiplicative subset Z∖3Z. In A=V+εV, let us check the divisibility between z1=3+4ε and z=2+5ε. Observe that 3∤2 but 2∣3 and 2∣(4-15/2); this means that z1=t·z2, where t=3/2-ε7/4.Definition 4 (monomial ordering).
(1)
A total ordering< on the set of monomials Mon(x1,…,xn) is said to be a monomial ordering if ∀α,β,γ∈Nn we have xα<xβ⟹xα+γ<xβ+γ.(2)
A monomial ordering is called
(i)
global ifxα>1∀α≠(0,…,0);(ii)
local ifxα<1∀α≠(0,…,0);(iii)
mixte if it is neither global nor local.
For details on monomial ordering, see [10, 11].Definition 5 (monomial ordering for modules).
LetF≔Rr be a free R-module of rank r>1, and let e1,…,er be the canonical basis of F. (1)
A monomial inF is the product of a monomial in R with a basis element ei, that is, an element of the form xαei where α∈Nn. We denote by Mon(F) the set of all monomials in F.(2)
Accordingly, a term inF is the product of a monomial in F with an element in A.(3)
For monomialsm1,m2∈R and coefficients c1,c2∈A, the least common multiple of two terms c1m1ei,c2m2ej∈F is given by(6)lcmc1m1ei,c2m2ej=lcmc1m1,c2m2eiifi=j0otherwise.(4)
A monomial ordering onMon(F) is a total ordering < such that if xαei and xβej are monomials in F, then, ∀α,β,γ∈Nn, we have xαei<xβej⟹xα+γei<xβ+γej.(5)
A monomial ordering> in R can be extended in F as a module ordering. Denoting a module ordering by >M, we say that xα·ei>Mxβ·ej if one of the following conditions holds:
(a)
xα>xβ or xα=xβ and i>j. In this case, we say that the priority is given to monomials.(b)
i>i or i=j and xα>xβ. In this case, we say that the priority is given to components.Definition 6 (notations).
Letf=∑iaiXαi be a nonzero polynomial in R and let I=〈f1,…,fs〉 be a finitely generated ideal of R. With respect to a monomial ordering <, we have the following(i)
The multidegree off denoted as mdeg(f) is defined as mdeg(f)≔max{αi∈Nn/ai≠0}.(ii)
The leading coefficient off denoted as Lc(f) is defined as Lc(f)≔amdeg(f).(iii)
The leading monomial off denoted as Lm(f) is defined as Lm(f)≔Xmdeg(f).(iv)
The leading term off denoted as Lm(f) is defined as Lt(f)≔Lc(f)·Lm(f).(v)
The tail off is defined as tail(f)≔f-Lt(f).(vi)
The leading ideal ofI is defined as Lt(I)≔〈Lt(g)/g∈I〉.Lemma 7.
Letz,z1,…,zr∈A and m,m1,…,mr be monomials in R=A[x1,…,xn]. An element z·m belongs to 〈z1m1,…,zrmr〉 if and only if there exists i0∈{1,…,r} such that zi0∣z in A and mi0∣m in R.Proof.
The proof follows from the proof of Lemma 2.2 in [6].Lemma 8.
Leta,b∈V∖{0}. Then the quotient ideal (7)a:b=cwhere(8)c=abifb∣a1else. And 〈a〉:b={c∈V∣b·c∈〈a〉}.Proof.
Letx∈〈a〉:b; then xb∈〈a〉; that is, there exists y∈V such that xb=ya. (i)
Ifb∣a, then x=ya/b∈a/b.(ii)
Ifb∤a, then a∣b; in this case, b=k1·a for some k1∈V; since x·b∈〈a〉, then xk1·a=k2·a for some k2∈V. This means that x=k2/k1∈V=〈1〉.
Conversely letx∈〈c〉 where c is described in the hypothesis. (i)
Ifc=a/b, then b∣a; in this case, there exists y∈V such that x=ya/b; that is, xb=ya∈〈a〉; therefore x∈〈a〉:b.(ii)
Ifc=1, then x∈〈1〉=V and b∤a⇒a∣b; that is, b∈〈a〉; in this case, we have xb∈〈a〉; therefore x∈〈a〉:b.Throughout this work, we denoteF=Rs with basis e1,…,es, where s>1.Theorem 9 (division’s algorithm).
Let< be a monomial ordering on Mon(F) and g,f1,…,fs∈F∖{0}. There exist q1,…,qs∈R and h∈F such that the following conditions hold: (i)
g=q1f1+⋯+qsfS+h.(ii)
Lm(qifi)≤Lm(f)∀1≤i≤s.(iii)
h=0 or no term occurring in h is divisible by any of Lt(fi)∀1≤i≤s.Example 10.
LetA=V+εV, where V=Z3Z. Let f=(3+4ε)x4y3+(4+5ε)y5,f1=(2+ε)xy2+y,f2=(5+ε)x2y+x. The goal is to divide f by f1,f2,f3 in R=A[x,y] using the lexicographic ordering. Set p≔f,q1≔0≔q2. Observe that Lm(f1)∣Lm(p) and using Lemma 2, we have Lc(p)=(3/2+5/4ε)Lc(f1); this leads to q1≔(3/2+5/4ε)x3y and p≔p-[(3/2+5/4ε)x3y]f1=-(3/2+5/4ε)x2y2+(4+5ε)y5. Again Lm(f1)∣Lm(p) and using Lemma 2, we have Lc(p)=-(3/4+ε/4)Lc(f1); this leads to q1≔(3/2+5/4ε)x3y-(3/4+ε/4)x2 and p≔p+[(3/4+ε/4)x2]f1=-(3/4+ε/4)x2y+(4+5ε)y5. Since Lm(f1)∤Lm(p), then we move to the next polynomial. Observe that Lm(f2)∣Lm(p) and using Lemma 2, we have Lc(p)=-(3/20+ε/50)Lc(f2); this leads to q2≔-(3/20+ε/50) and p≔(3/20+ε/50)x+(4+5ε)y5. Since neither Lt(f1) nor Lt(f2) is divisible by any term occurring in p, we will send each term of p in the remainder r and get p=0 and r=(3/20+ε/50)x+(4+5ε)y5. Thus, f=q1f1+q2f2+r.


## 3. Gröbner Bases

Definition 11.
A set of polynomials{f1,…,fs} is called strong Gröbner basis for I=〈f1,…,fs〉 with respect to a monomial ordering < if ∀f∈I there exists k∈{1,…,s} such that Lt(fk)∣Lt(f).Proposition 12 (ideal membership problem).
LetG={f1,…,fs} be a strong Gröbner basis for I=〈f1,…,fs〉 and let > be a monomial ordering. Let f∈R; then f∈I if and only if the remainder of the division of f by {f1,…,fs} is zero.Proof.
The proof follows from [12].Definition 13 (S-vectors).
Letf,g∈F∖{0} be nonzero polynomial vectors and let < be a monomial ordering. The S-vector S(f,g) of f and g is defined as follows: (1)
IfLc(f)∤Lc(g) and Lc(g)∤Lc(f), then (9)Sf,g=LcgdlcmLmf,LmgLmff-LcfdlcmLmf,LmgLmggwhered=〈RLcf,RLcg,ILcf,ILcg〉.(2)
Else(10)Sf,g=LcgLcflcmLmf,LmgLmff-lcmLmf,LmgLmggifLcf∣LcglcmLmf,LmgLmff-LcgLcflcmLmf,LmgLmggifLcg∣LcfandLcf∤Lcg.If F=R, we call S(f,g) the S-polynomial of f and g.Example 14.
LetA=V+εV where V=Z3Z and let us compute the S-polynomial for f1 and f2 using the lexicographic ordering in R=A[x,y], where (1)
f1=(3+2ε)x2y+x and f2=(2+3ε)xy2+y.Observe thatLc(f2)∤Lc(f1) but Lc(f1)∣Lc(f2); in this case, the S-polynomial is given by the formula(11)Sf2,f1=lcmLmf,LmgLmff-LcgLcflcmLmf,LmgLmgg,and
we haveS(f2,f1)=yf2-(3/2-5/4ε)xf1.(2)
f1=2εx2y+x and f2=(3+5ε)xy2+y.Observe thatLc(f1)∤Lc(f2) and Lc(f2)∤Lc(f1); in this case, we compute the S-polynomial S(f2,f1) by the formula(12)Sf2,f2=Lcf1dlcmLmf,LmgLmff-Lcf2dlcmLmf,LmgLmgg,where〈2,3,5〉=〈d〉=〈1〉, since 2 and 5 are units. In this case, we have (13)Sf2,f1=2εyf-3+5εxg.Definition 15 (extended S-vector).
Letf∈F∖{0} be a polynomial vector such that R(Lc(f))=0; then we define the extended S-vector of f as S(f)=εf.Example 16.
Iff=2εx2y+x, then, using the lexicographic ordering in R=A[x,y], we have S(f)=εf=εx.Definition 17 (syzygy).
Letf1,…,fs be nonzero polynomials of R and let e1,…,es be the canonical basis for F=Rs. By a syzygy on f1,…,fs, we mean an element of the kernel of the homomorphism of R-modules (14)ψ:F→R,ei↦fi.In the other words, a syzygy on f1,…,fs is an element (h1,…,hs)∈F such that (15)h1f1+⋯+hsfs=0.The set of all syzygies on f1,…,fs is denoted by syz(f1,…,fs)=ker(ψ).Definition 18 (Schreyer’s ordering).
Given a monomial ordering> on R and nonzero polynomials f1,…,fr∈R, we define Schreyer’s ordering >1 (or induced ordering) on F1≔Rr induced by > and f1,…,fr as follows: xαei>1xβej if and only if (1)
xαLm(fi)>xβLm(fj) or(2)
xαLm(fi)=xβLm(fj) and i>j∀α,β∈Nn.Theorem 19 (Buchberger’s criterion).
Letf1,…,fr be nonzero polynomials of R and let > be a monomial ordering. Then {f1,…,fr} form a strong Gröbner basis for I=〈f1,…,fr〉 if and only if the following conditions hold: (1)
For each pair of integers(i,j)i>j, the remainder of the division’s algorithm of S(fi,fj) by {f1,…,fs} is zero.(2)
The remainder of the divisoin’s algorithm ofS(fi) by {f1,…,fs} is zero for each i.Proof.
Assume that{f1,…,fs} is a Gröbner basis for I. Since S(fi,fj)i>j and S(fi)∈I, by Proposition 12, we see straightforwardly that each remainder by division’s algorithm (see Algorithm 1) will be zero.
Assume that the remainder of each S-polynomialS(fi,fj)i>j and each extended S-polynomial S(fi) is zero; using Algorithm 1, we have (16)Sfi,fji>j=∑k=1sgkijfk+0,Sfi=∑k=1shkifk+0.Observe by definition that, for some i, we have (17)Sfi=εfi=∑k=1shkifk,and then (18)h1if1+⋯+h1i-εfi+⋯+hsifs=0Therefore (h1i,…,(h1i-ε),…,hsi) is a syzygy for f1,…,fs. Set ∗Hi=h1i,…,h1i-ε,…,hsi.Observe by Algorithm 1 that (19)Lmhkifk≤LmSfi<εLmfiThis means that Lm(hki)Lm(fk)<εLm(fi) and by Schreyer’s ordering Lm(hki)ek<εei; therefore ALtHi=-εei.
Observe also thatS(fi,fj)=qjimjifi-qijmijfj, where mji=lcm(Lm(fi),Lm(fj))/Lm(fi),mij=lcm(Lm(fi),Lm(fj))/Lm(fj), and qji,qij are coefficients as in the definition of S-polynomials. For each i>j, we have qjimjifi-qijmijfj=∑k=1sgkijfk; that is, (20)g1ijf1+⋯+gjij+qijmijfj+⋯+giij-qjimjifi+⋯+gsijfs=0,and then (g1ij,…,(gjij+qijmij),…,(giij-qjimji),…,gsij) is a syzygy for f1,…,fs. Set 2∗Gij=g1ij,…,gjij+qijmij,…,giij-qjimji,…,gsij.
Observe by Algorithm1 that Lm(gkij)Lm(fk)≤Lm(S(fi,fj))<mjiLm(fi)=mijLm(fj); this means that mjiLm(fi)=mijLm(fj) and since i>j, by Schreyer’s ordering, we conclude that mjiei>mijej; therefore BLtGij=qjimjiei∀i>j.Let  us  prove  that  {f1,…,fs}form  a  strong  Gröbner  basis  for  I.
Letf∈I; then f=a1f1+⋯+asfs for some a1,…,as∈R. Let us prove that there exists k∈{1,…,s} such that Lt(fk)∣Lt(f). Let A=(a1,…,as)∈Rs; with respect to Schreyer’s ordering >1 induced by > and {f1,…,fs}, let us divide A by T={Hi,Gij/Hi,Gij∈syz(f1,…,fs)} (listed in some order). We have 3∗A=∑ijQijGij+∑ipiHi+Gwhere Qij,pi∈R and the remainder G=(g1,…,gs)∈Rs. Let F=(f1,…,fs)t∈Rs; multiplying 3∗ by F, we get 4∗AF=f=g1f1+⋯+gsfsWe transform 6∗ as (21)f=∑i=1sLtgiLtfi+∑i=1stailgiLtfi+∑i=1sgitailfi(1)
IfLt(f)≠Lt(∑i=1sgitail(fi)), then it is clear that Lt(f)=Lt(∑i=1sLt(gi)Lt(fi)+∑i=1stail(gi)Lt(fi)); that is, Lt(f)∈〈Lt(f1),…,Lt(fs)〉 and by Lemma 7 there exists i0 such that Lt(fi0)∣Lt(f).(2)
IfLt(f)=Lt(∑i=1sgitail(fi)), then there exists K⊆{1,…,s} such that ∑i∈KLt(gi)Lt(fi)=0 and ∑i∈Kgitail(fi)≠0.
Case  1. Assume that there exists j∈K such that Lt(gj)Lt(fj)=0; then it is clear that R(Lc(gj)=R(Lc(fj))=0. Observe that Lt(gj)=εLt(hj) for some polynomial hj with Lc(hj)∈V∖{0}. This means that Lt(gj)ej=-Lt(hj)(-εej)=-Lt(hj)Lt(Hj), which contradict the fact that no term occurring in the remainder G is divisible by any of Lt(Hi) and Lt(Gij).
Case  2. ∀i∈K, we have R(Lc(fi))≠0≠R(Lc(gi)). In this case, we choose the biggest j∈K such that Lt(gj)Lt(fj)=-∑i∈K∖{j}Lt(gi)Lt(fi)∈〈Lt(fi)/i∈K∖{j}〉. Since Lt(fj)∉〈Lt(fi)/i∈K∖{j}〉, then it is clear that Lt(gj)∈〈Lt(fi)/i∈K∖{j}〉; by Lemma 7, there exists l∈K∖{j} such that Lt(fl)∣Lt(gj); that is, Lc(fl)∣Lc(gj) and Lm(fl)∣Lm(gj). Of course Lm(fl)∣Lm(gj)Lm(fj) which means that lcm(Lm(fl),Lm(fj))∣Lm(gj)Lm(fj); therefore lcm(Lm(fl),Lm(fj))/Lm(fj)∣Lm(gj); that is,5∗mlj∣Lmgj.(i)
Assume thatLc(fj)∣Lc(fl); in this case, we have Lc(fj)∣Lc(fl)∣Lc(gj); that is, there exists z∈A=V[ε]/〈ε2〉 such that 6∗Lcgj=zLcfl=zLcfjLcflLcfj.Observe thatS(fj,fl)=Lc(fl)/Lc(fj)mljfj-mjlfl and Lt(Glj)=Lc(fl)/Lc(fj)mljej; using 5∗ and 6∗, we see that Lt(Glj)∣Lt(gj)ej which contradict the fact that no term occurring in the remainder G is divisible by any of Lt(Gij).(ii)
Assume thatLc(fj)∤Lc(fl) and Lc(fl)∣Lc(fj); in this case, we have S(fj,fl)=mljfj-Lc(fj)/Lc(fl)mjlfl and Lt(Glj)=mljej; using 5∗, we see that Lt(Glj)∣Lt(gj)ej which contradict the fact that no term occurring in the remainder G is divisible by any of Lt(Gij).(iii)
Assume thatLc(fj)∤Lc(fl) and Lc(fl)∤Lc(fj); in this case, we have(22)Sfj,fl=Lcfldmljfj-LcfjdmjlflandLt(Glj)=Lc(fl)/dmljej, where 〈d〉=〈R(Lc(fl)),R(Lc(fj)),I(Lc(fl)),I(Lc(fj))〉. Since by hypothesis Lc(fl)∣Lc(gj) (i.e., Lc(gj)=tLc(fl) for some t∈A), we have Lc(gj)=t·dLc(fl)/d; using 5∗, we see that Lt(Glj)∣Lt(gj)ej, which contradict the fact that no term occurring in the remainder G is divisible by any of Lt(Gij).Algorithm 1:Division’s algorithm.
Input:  f,f1,…,fs∈R and a monomial ordering >. Output:   q1,…,qs∈R and h∈F such that f=q1f1+⋯+qsfs+h. 1Initialization:  q1≔q2≔⋯≔qs≔h≔0 and v≔f; 2while  v≠0  do 3i≔1 4k≔0 5while  i≤sandk≔0  do 6if  Lt(fi)∣Lt(v)  then 7qi≔qi+Lt(v)/Lt(fi) 8v≔v+Lt(v)/Lt(fi)fi 9k≔1 10end 11else 12i≔i+1 13end 14end 15if  k≔0  then 16h≔h+Lt(v) 17v≔v-Lt(v) 18end 19endExample 20.
LetA=V+εV, where V=Z2Z; let us compute a Gröbner basis for 〈f1,f2,f3〉 using Algorithm 2, where f1=2εx2y+y3,f2=(1+ε)xy2,f3=4x4+(1+ε)y using the lexicographic ordering in R=A[x,y]. Observe that (1)
S(f3,f1)=Lc(f1)/dyf3-Lc(f3)/dx2f1=-2x2y3+εy2=-(2-2ε)xyf2+εy2 where d=2. Set f4=εy2.(2)
S(f3,f2)=y2f3-Lc(f3)/Lc(f2)x3f2=(1+ε)y3. Set f5=(1+ε)y3.(3)
S(f1)=εf1=εy3=εy3=ε(1+ε)y3=εf5.(4)
S(f2,f1)=Lc(f1)/Lc(f1)xf2-yf1=-y4=-(1-ε)(1+ε)y4=-(1-ε)yf5.(5)
S(f4,f1)=Lc(f1)/Lc(f4)x2f4-yf1=-y4=-(1-ε)(1+ε)y4=-(1-ε)yf5.(6)
S(f4,f2)=xf4-Lc(f4)/Lc(f2)f2=0.(7)
S(f4,f3)=Lc(f3)/dx4f4-Lc(f4)/dy2f3=εy3=ε(1+ε)y3=εf5 where d=1.(8)
S(f5,f4)=Lc(f4)/Lc(f5)f5-yf4=0.(9)
S(f5,f3)=Lc(f3)/Lc(f5)x4f5-y3f3=(1+ε)y4=yf5.(10)
S(f5,f2)=Lc(f2)/Lc(f5)xf5-yf2=0.(11)
S(f5,f1)=Lc(f1)/Lc(f5)x2f5-y2f1=-y5=-(1-ε)y2f5.
Then the set{f1,…,f5} form a strong Gröbner basis for 〈f1,f2,f3〉.Algorithm 2:Buchberger’s algorithm.
Input: given an ideal I=〈f1,…,fs〉⊂R and a monomial ordering > on R. Output: a strong Gröbner basis for IL. 1k≔s 2P≔{S(fi,fj)1≤j<i≤k,S(fi)1≤i≤s} 3while  P≠∅  do 4choose h∈P and denote by r the remainder of the division’s algorithm of h by {f1,…,fk} if  r=0  then 5P≔P∖{h} 6end 7else 8k≔k+1; 9fk≔r; 10P≔(P∖{h})∪{S(fk,fi),S(fi)/1≤i≤k} 11end 12end 13return  {f1,…,fk}Theorem 21 (Schreyer’s theorem).
LetG={f1,…,fs} be a strong Gröbner basis for I=〈G〉⊂R with respect to a monomial ordering >. The set of syzygies T={Gij,Hi∈Syz(f1,…,fs)/i>j} form a strong Gröbner basis for Syz(f1,…,fs) with respect to the Shreyer’s ordering induced by > and G.Proof.
LetA∈Syz(f1,…,fs); we wish to prove that ∃h∈T such that Lt(h)∣Lt(A).
By the division’s algorithm inRs for A by T, we have #A=∑i,jQijGij+∑i,jpijHij+Gwhere each pij,Qij∈R and G=(g1,…,gs)∈Rs. Let F=(f1,…,fs)t∈Rs; by multiplying # by F, we get 2#g1f1+⋯+gsfs=0.Assume that G=(g1,…,gs) is a nontrivial syzygy; then there exists K={i1,…,ir}⊆{1,…,s} such that3#gi1fi1+⋯+girfir=0and gifi≠0∀i∈K. We can transform 3# as follows: (23)4:0=∑i=i1irLtgiLtfi+∑i=i1irtailgiLtfi+∑i=i1irgitailfi.It is clear that ∑i=i1irLt(gi)Lt(fi)=0. (1)
If there existsi∈K such that Lt(gi)Lt(fi)=0; then we use the same technique as that in the proof of Buchberger’s criterion; that is, ELtgi=εLthifor some polynomialhi∈R such that Lc(hi)∈V. Observe that S(fi)=εfi=∑j=1spjifj for some pji∈R, and Lt(Hi)=-εei. We have Lt(gi)ei=-Lt(hi)Lt(Hi); that is, Lt(Hi)|Lt(gi), which contradict the fact that no term occurring in the remainder G is divisible by any of Lt(Hi) or Lt(Gij).(2)
Assume that,∀i∈K,Lt(gi)Lt(fi)≠0; then we have F∑i=i1irLcgiLcfi=0andGLmgi1Lmfi1=⋯=LmgirLmfir.
Letj∈K be the biggest integer in K; we have (24)LmgjLmfj=LmgiLmfi∀i∈K∖j.Observe thatLm(gj)Lm(fj) is a common multiple of Lm(fi) and Lm(fj); it is then a multiple of lcm(Lm(fi),Lm(j)); this means that Lm(gj) is a multiple of HlcmLmfi,LmjLmfj=mij.FromF, we have Lc(fj)Lc(gj)∈〈Lc(fi)/i∈K∖{j}〉; since Lc(fj)∉〈Lc(fi)/i∈K∖{j}〉, then Lc(gj)∈〈Lc(fi)/i∈K∖{j}〉 and from Lemma 7 there exists l∈K∖{j} such that Lc(fl)∣Lc(fj). This case leads to a contradiction, since it has been treated in the proof of Buchberger’s criterion.
Since we get a contradiction in any cases,G must be zero and in this case (25)LtA=maxi,j⁡LtQijLtGij,LtpijLtHij.Example 22.
LetA=V+εV, where V=Z2Z. We have seen in Example 20 that {f1,…,f5} form a Gröbner basis for 〈f1,f2,f3〉 with respect to the lexicographic ordering > in R=A[x,y]. Let us compute a Gröbner basis for syz(f1,…,f5)⊂R5 using Algorithm 3 with respect to to Schreyer’s ordering >1 induced by > and {f1,…,f5}. Observe that (1)
S(f3,f1)=εyf3-2x2f1=-(2-2ε)xyf2+f4. Set r1=(2x2,(-2+2ε)xy,-εy,1,0).(2)
S(f3,f2)=y2f3-(4-4ε)x3f2=f5. Set r2=(0,(4-4ε)x3,-y2,0,1).(3)
S(f1)=εf1=εf5. Set r3=(-ε,0,0,0,ε).(4)
S(f2,f1)=2εxf2-yf1=-(1-ε)yf5. Set r4=(y,-2εx,0,0,-(1-ε)x).(5)
S(f4,f1)=2x2f4-yf1=-(1-ε)yf5. Set r5=(y,0,0,-2x2,(-1+ε)y).(6)
S(f4,f2)=xf4-εf2=0. Set r6=(0,ε,0,-x,0).(7)
S(f4,f3)=4x4f4-εy2f3=εf5. Set r7=(0,0,εy2,-4x4,-ε).(8)
S(f5,f4)=εf5-yf4=0. Set r8=(0,0,0,y,-ε).(9)
S(f5,f3)=(4-4ε)x4f5-y3f3=yf5. Set r9=(0,0,y3,0,y-(4-4ε)x4).(10)
S(f5,f2)=xf5-yf2=0. Set r10=(0,y,0,0,-x).(11)
S(f5,f1)=2εx2f5-y2f1=-(1-ε)y2f5. Set r11=(y2,0,0,0,-(1-ε)y2--2εx2).
Then the set{r1,…,r11} form a strong Gröbner basis for syz(f1,…,f5) with respect to Shreyer’s ordering >1 induced by > and {f1,…,f5}.Algorithm 3:Gröbner basis for syz(f1,…,fs).
Input: strong Gröbner basis G={f1,…,fs} for I=〈G〉 and a monomial ordering >. Output: strong Gröbner basis T for syz(G) w.r.t >1 induced by > and G. 1T1:=∅:=T2 2for  i,j=1,…,s  do 3S(fi,fj)i>j=qjimjifi-mijfj=∑i=1spijifi 4s:=p1jie1+⋯+(pjji+mij)ej+⋯+(piji-qjimji)ei+⋯+psjies 5T1:=T1∪{s} 6end 7for  i=1,…,s  do 8if  R(Lc(fi))=0  then 9S(fi)=εfi=∑j=1sqjifj 10r:=q1ie1+⋯+(qii-ε)ei+⋯+qsies 11T2:=T2∪{s} 12end 13T:=T1∪T2 14end 15return  T


## 4. Algorithm for Computing the Module of Syzygies inR

Given nonzero polynomialsf1,…,fs∈R=A[x1,…,xn], we propose in this section an algorithm for computing the set of all (h1,…,hs)∈Rs such that h1f1+⋯+hsfs=0.Remark 23.
Letf1,…,fs∈R∖{0} be nonzero polynomials and let G={f1,…,fs,…,fs′} be a Gröbner basis for 〈f1,…,fs〉 with respect to the monomial ordering <. Let Gij,Hij∈syz(f1,…,fs′) with i>j. We have seen in Theorem 21 that syz(f1,…,fs′)=〈Gijwithi>j,Hiforsomei〉. Assume that there are t such syzygies arranged as follows: while computing the strong Gröbner basis G={f1,…,fs,…,fs′}, we store each nonzero syzygy Gij and Hi such that those obtained from a division leading to a new polynomial fk are first and those obtained from a division with remainder zero are second. Gij and Hi fit as columns of the s′×t matrix: (26)Ms′×t=g11g12⋯g1s′-sg1s′-s+1⋯g1tg21g22⋯g2s′-sg2s′-s+1⋯g2t⋮⋮⋯⋮⋯⋮gs1gs2⋯gss′-sgss′-s+1⋯gst1gs+12⋯gs+1s′-sgs+1s′-s+1⋯gs+1t01⋯gs+2s′-sgs+2s′-s+1⋯gs+2t⋮0⋯gs+3s′-sgs+3s′-s+1⋯gs+3t⋮⋮⋯⋮⋯⋮00⋯1gs′s′-s+1⋯gs′t
Let(27)As×s′-s=g11g12⋯g1s′-sg21g22⋯g2s′-s⋮⋮⋯⋮gs1gs2⋯gss′-s,Bs×t-s′-s=g1s′-s+1⋯g1tg2s′-s+1⋯g2t⋮⋯⋮gss′-s+1⋯gst,Cs′-s=1gs+12⋯gs+1s′-s01⋯gs+2s′-s⋮0⋯gs+3s′-s⋮⋮⋯⋮00⋯1and(28)Ds′-s×t-s′-s=gs+1s′-s+1⋯gs+1tgs+2s′-s+1⋯gs+2t⋮⋯⋮gs′s′-s+1⋯gs′t
ThenMs′×t can be regarded as the s′×t block matrix:(29)Ms′×t=As×s′-sBs×t-s′-sCs′-sDs′-s×t-s′-s.Notation 24.
For simplicity, we denoteA=As×(s′-s),B=Bs×(t-(s′-s)),C=Cs′-s and D=Ds′-s×t-s′-s.With notations as above, we have the following theorem.Theorem 25.
The columns of thes×(t-s′+s) matrix B-AC-1D are syzygies on f1,…,fs.Proof.
Set(30)F=f1⋯fs,F′=fs+1⋯fs′,FF′=f1⋯fs⋯fs′.We know by hypothesis that each column of the matrix (31)ABCDforms a syzygy on f1,…,fs′. We can write (32)FF′ABCD=01×s′-s01×t-s′+sThen(33)FA+F′C=01×s′-s(34)FB+F′D=01×t-s′+sNote that C is invertible; by multiplying each side of (33) by C-1, we get(35)FAC-1+F′=01×s′-sReplacing (35) in (34), we get F(B-AC-1D)=0; this means that B-AC-1D is a syzygy on f1,…,fs.Example 26.
LetA=V+εV, where V=Z2Z. Using Algorithm 4, we would like to compute a generating set for syz(f1,f2,f3). We have seen in Example 22 that {r1,…,r11} form a strong Gröbner basis for syz(f1,…,f5) with respect to Shreyer’s ordering >1 induced by > and {f1,…,f5}. We arrange these elements in the following matrix: (36)M=2x20-εyy00000-2+2εxy4-4εx30-2εx0ε000y-εy-y20000εy20y301000-2x2-x-4x4y0001ε-1-εy-1+εy0-ε-εy-4-4εx4-xtogether with the column r11=(y2,0,0,0,-(1-ε)y2-2εx2). Let us consider the following block matrices:(37)A=2x20-2+2εxy4-4εx3-εy-y2,B=-εyy00000y20-2εx0ε000y00000εy20y300,C=1001and (38)D=00-2x2-x-4x4y000ε-1-εy-1+εy0-ε-εy-4-4εx4-x-1-εy2-2εx2.
We compute the matrixB-AC-1D and we separate it into the two following matrices:(39)-εyy+4x42x38x6-4εx34-8εx3y-2εx-4εx3yε-2-2εx2y-8-8εx5y+4εx3εy2-1-εy3-2εx2y+-1+εy3-εxy-4εx4y and (40)-2x2y00y24εx3+2-2εxy2-4-4εx3y+16-32εx7y+4-4εx44-8εx3y2+8εx502y3-4-4εx4y2-xy2-1-εy4-2εx2y2.Algorithm 4:Algorithm for computing the module of syzygies.
Input: polynomials f1,…,fs∈R∖{0} and a monomial ordering > Output:  S={(h1,…,hs)∈Rs/h1f1+…+hsfs=0} (1) Compute a strong Gröbner basis G={f1,…,fs,fs+1,…,fs} for 〈f1,…,fs〉 w.r.t < (2) Compute the set T={h∈Rs′/h∈syz(f1,…,fs′)} of all syzygies for G. (3) Arrange elements of T as columns of the matrix A B C D as explained in the Remark 23 (4) Compute P=B-AC-1D. Assume that P has t columns p1,…,pt. (5) Return S={p1,…,pt}.Each column of the two matrices above forms a a syzygy forf1,f2,f3. In other words, syz(f1,f2,f3)=〈h1,…,h9〉, where, ∀1≤i≤9, hi is a 3-tuple representing each column of the two matrices above.


## 5. Algorithm for Computing the Intersection of Ideals inR

In this section, we denote byR=A[x1,…,xn] a polynomial ring over A. Given two ideals I=〈f1,…,fs〉 and J=〈g1,…,gr〉 of R, we propose an algorithm for computing a generating set for the intersection I∩J. Observe that an element h∈I∩J satisfies h=∑i=1spifi=∑j=1rqjfj for some p1,…,pr,q1,…,qs∈R. To find h, we need to choose pi,qj such that ∑i=1spifi-∑j=1rqjfj=0.Theorem 27.
LetI=〈f1,…,fs〉 and J=〈g1,…,gr〉 be two ideals in R=A[x1,…,xn], and let (h1,…,hr+s) be a nontrivial syzygy on f1,…,fs,g1,…,gr. Then the polynomial h=∑i=1shifi belongs to the ideal I∩J.Proof.
It is clear thath=∑i=1shifi∈I.
Let(h1,…,hr+s) be a syzygy on f1,…,fs,g1,…,gr; then ∑i=1shifi+∑j=1rhs+jgj=0; that is, h=∑i=1shifs=-∑j=1rhs+jgj∈J. Thus, h∈I∩J.LetF=(f1…fs)t and G=(g1…gr)t. With notations as above, we have the following corollary.Corollary 28.
LetK=I+J=〈f1,…,fs,g1,…,gr〉 be an ideal in R and let B-AC-1D be the matrix of syz(f1,…,fs,g1,…,gr). There exists a submatrix E of B-AC-1D such that FE generates I∩J.Proof.
Lett be the number of columns of the matrix AC-1D-B; then (41)AC-1D-B=E=Es×tK=Kr×tSince AC-1D-B is the syzygy matrix generator for Syz(FG); then FE=-GK. Each column of FE is an element of I and each column of GK is an element of J. Thus, 〈FE〉⊂I∩J.
Conversely, ifh∈I∩J, then h=∑i=1spifi=∑i=1rqigi. In other words, (p1,…,ps,-q1,…,-qr) is a syzygy on f1,…,fs,g1,…,gr; then it is straightforward to see that h∈〈FE〉.Example 29.
LetA=V+εV, where V=Z2Z. Let I=〈f1,f2〉 and J=〈f3〉 be two ideals of R=A[x,y], where f1=2εx2y+y3,f2=(1+ε)xy2,f3=4x4+(1+ε)y. Using Algorithm 5, we would like to compute a generating set for I intersect J. We have seen in Example 26 that, ∀1≤i≤9,hi is a syzygy for f1,f2,f3. We have the following from each syzygy: (1)
-εf1-4εx3f2=εy2f3(2)
yf1+[(4-8ε)x3y-2εx]f2=(1-ε)y3f3(3)
y+4x4f1-4εx3yf2=[2εx2y-(-1+ε)y3]f3(4)
2x3f1+[ε-(2-2ε)x2y]=εxyf3(5)
8x6f1+[-(8-8ε)x5y+4εx3]f2=4εx4yf3(6)
-2x2yf1+[4εx3+(2-2ε)xy2]f2=0(7)
0f1+[-(4-4ε)x3y+(16-32ε)x7]f2=-[2y3-(4-4ε)x4y2]f3(8)
0f1+[y+(4-4ε)x4]f2=xy2f3(9)
y2f1+[(4-8ε)x3y2+8εx5]f2=[(1-ε)y4+2εx2y2]f3.
This means thatI∩J=〈εy2f3,(1-ε)y3f3,[2εx2y-(-1+ε)y3]f3,εxyf3,4εx4yf3,-[2y3-(4-4ε)x4y2]f3,xy2f3,[(1-ε)y4+2εx2y2]f3〉; that is, (42)I∩J=εy2,1-εy3,2εx2y--1+εy3,εxy,-2y3-4-4εx4y2,xy2,1-εy4+2εx2y2.Algorithm 5:Computing a generating set for I∩J.
Input: given ideals I=〈f1,…,fs〉 and J=〈g1,…,gr〉 in R. Output: generating set for I∩J. 1 Compute a syzygy matrixS for f1,…,fs,g1,…,gr. Let t be the number of columns of S 2for  each column  (h1,…,hs+r) of A (i.e ∑i=1shifi+∑j=1rhs+jgj=0)  do 3Compute each qk:=∑i=1s‍hifi for 1≤k≤t 4end 5return  q1,…,qt



---

*Source: 9316901-2018-11-15.xml*