# On Syzygy Modules over Laurent Polynomial Rings

Authors: Morou Amidou; Ousmane Moussa Tessa
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

In this paper, we present a dynamical method for computing the syzygy module of multivariate Laurent polynomials with coefficients in a Dedekind ring (with zero divisors) by reducing the computation over Laurent polynomial rings to calculations over a polynomial ring via an appropriate isomorphism.


---

## Body

## 1. Introduction

Our goal is to give a dynamical method for computing a finite basis for the syzygy module of finitely many multivariate Laurent polynomials with coefficients in a Dedekind ringR. More precisely, given nonzero polynomials f1,…,fs∈Rx1±1,…,xn±1, we will compute s1,…,st∈Rx1±1,…,xn±1s×1 generating the syzygy module Syzf1,…,fs≔w1,…,wst∈Rx1±1,…,xn±1s×1such thatw1f1+⋯+wsfs=0. The technique consists in reducing the computation over the Laurent polynomial ring Rx1±1,…,xn±1 to a problem over a polynomial ring Rx1,…,xn,y via an appropriate isomorphism. One advantage of this indirect approach is that we can use techniques over polynomial rings more efficient than the corresponding methods in Laurent polynomial rings. Such kind of algorithm can be used in signal processing for the computation of the inverse FIR filter of a given multidimensional FIR filter. Our approach is inspired by the theory developed in the papers [1–13] and outlined in the next section.


## 2. Computing Dynamically a Basis for Syzygies of Polynomials over Dedekind Rings

LetS be a multiplicative subset of a ring R; then, the localization of R at S is the ring S−1R=x/s,x∈R,s∈S and the elements of S are forced to be invertible. If x∈R, the localization of R at the multiplicative subset ℳx generated by x will be denoted by Rx. Moreover, by induction, for each x1,…,xk∈R, we define Rx1.x2.….xk≔Rx1.x2.….xk−1xk.Now, letR be a Dedekind ring and consider f1,…,fs∈Rx1,…,xn\0. First of all, we need to present a dynamical process [6] for computing a basis for Syzf1,…,fs. This method works like the case where the basic ring is a Noetherian valuation ring [11]. The Noetherian hypothesis is added so that a dynamical Gröbner basis G=S1,G1,…,Sk,Gk for the ideal f1,…,fs of Rx1,…,xn can be computed. The only difference is when one has to handle two incomparable (under division) elements a,b in R. In this situation, one should first compute u,v,w∈R such that(1)ub=va,wb=1−ua.Henceforth, one opens two branches: the computations are pursued inRu and R1+uR≔x/y,x∈Rand∃z∈Rsuch thaty=1+zu. Note that contrary to [11], the localization R1+uR instead of R1−u is used in order to avoid redundancies. The Dedekind ring R is forced to behave like a valuation ring and this situation will produce a binary tree in which leaves correspond to localizations Sj−1R, 1≤j≤k, of R at comaximal multiplicative subsets S1,…,Sk. The fact that a basis for Syzf1,…,fs can be computed at each leaf together with Lemma 1 will yield the desired one.LetHj=hj,1,…,hj,pj denote a basis for Syzf1,…,fs over Sj−1Rx1,…,xn, 1≤j≤k. There exists a dj∈Sj such that djhj,i∈Rx1,…,xn, for each 1≤i≤pj, and djhj,1,…,djhj,pj is a generator for Syzf1,…,fs over Sj−1Rx1,…,xn. As explained in Theorem II.3.6 [10], we have the following concrete local-global principle for coherent modules.Lemma 1.
(syzygy, coherent modules). LetA be a ring, S1,…,Sn be comaximal monoids, M be a A−module, and a=a1,…,am∈Mm.(1)
The syzygy moduleN⊆Am of the vector whose elements ai are seen as vectors in M is finitely generated if and only if each syzygy module Ni⊆ASim of the ai’s vector (ai are seen as vector in M) is finitely generated.(2)
M is coherent if and only if each MSi is coherent.(3)
The ringA is coherent if and only if each ASi is coherent.Proof.
(1)
LetS be a monoid in A and N′ be the syzygy module of the vector whose elements ai are considered in MS. We will prove that NS=N′. It is clear that NS⊆N′. Conversely, if ∑j=1mxj/sjaj=0 in MS, let us denote u=∏isi and uj=∏i≠jsi, such that ∑j=1mxjujaj=0 in MS and ∑j=1msxjujaj=0 in M for s∈S. We have y=y1,…,ym=sx1u1,…,sxmum∈N and x1/s1,…,xm/sm=1/suy in AS.
(2)
Leta=a1,…,am∈Mm and N⊆Am be the module of relations for a. For all monoids S, NS is the module of relations for a in MS.
(3)
Is a particular case of 2.Theorem 1.
Leta=a1,…,am∈Rx1±1,…,xn±1m and a˜=ua1,…,am, where u=x1k1…xnkn is a polynomial in Rx1,…,xn such that a˜=a˜1,…,a˜m∈Rx1,…,xnm. The syzygy module N of a over Rx1±1,…,xn±1 is the same than the syzygy module of a˜ over Rx1,…,xn.Proof.
Let us denote byN⊆Rx1±1,…,xn±1m the syzygy module of a over Rx1±1,…,xn±1 and N′⊆Rx1,…,xnm that of a˜ in Rx1,…,xn.
If∑j=1mxja˜j=0 over Rx1,…,xn, then ∑j=1mxja˜j/u=∑j=1mxjaj=0, so we have N′⊆N.
Conversely if∑j=1mxjaj=0 over Rx1±1,…,xn±1, we can suppose that xi∈Rx1,…,xnm (the set of generators of a over Rx1±1,…,xn±1m can be supposed with only elements of Rx1,…,xn) and we can write ∑j=1mxjuaj=∑j=1mxja˜j=0. Finally, N=N′.


## 3. Syzygies of Laurent Polynomials over Dedekind Ring

Now, we can give a method for computing a set of generators for the syzygy module,Syzf1,…,fs, over the Laurent polynomial ring Rx1±1,…,xn±1. For this, we need the following.Lemma 2 (see [14]).
LetI be the ideal of Rx1,…,xn,y generated by x1…xny−1; then,(2)Rx1±1,…,xn±1≅Rx1,…,xn,yI.Proof.
Letϕ be an R-algebra homomorphism defined from Rx1,…,xn,y to Rx1±1,…,xn±1 by(3)ϕxi=xi,ϕy=x1−1…xn−1and extended to Rx1,…,xn,y as follows: for α∈R and f,g∈Rx1,…,xn,y,(4)ϕαf=αϕf,ϕf+g=ϕf+ϕg,ϕfg=ϕfϕg.
Considering such isomorphism, our problem is reduced to a computation over the polynomial ringRx1,…,xn,y. More precisely, we are going to rely on such isomorphism between Rx1±1,…,xn±1 and Rx1,…,xn,y/I to obtain an algorithm computing syzygy basis in Rx1±1,…,xn±1.
The previous isomorphism is well defined, as it does not depend on the way elements ofRx1,…,xn,y/I and Rx1±1,…,xn±1 are represented. First, every Laurent polynomial can be written as a polynomial in the variables x1,…,xn,x1−1…xn−1, and to get an element of Rx1,…,xn,y from a Laurent polynomial by this isomorphism, we have to consider the relation x1…xny=1 on I.
Note that ift=x1e1…xnen with ei∈ℤ being a term of Rx1±1,…,xn±1 and e=−min0,e1,…,en, we have(5)ϕ−1t=x1e1+e…xnen+e⋅ye∈Rx1,…,xn,y.
Conversely, each element ofRx1,…,xn,y/I is the image of a polynomial in Rx1,…,xn,y through the canonical (surjective) homomorphism of R-algebras:(6)Rx1,…,xn,y⟶Rx1,…,xn,yI,which converts f∈Rx1,…,xn,y into f¯=fmodI.
Givenf∈Rx1,…,xn,y, we obtain f¯ by replacing xi by x¯i and y by y¯, bearing in mind that x¯1⋯x¯n.y¯=1. Each f¯∈Rx1,…,xn,y/I can be expressed as algebraic combination of x¯,…,x¯n,y¯, with coefficients in R. By taking this expression of f¯ without the bars over variables, we get a polynomial p∈Rx1,…,xn,y such that p¯=f¯. Also, each g with f¯ as image can be written as g=p+x1…xny−1q where q∈Rx1,…,xn,y.
By the isomorphism betweenRx1±1,…,xn±1 and Rx1,…,xn,y/I, we get the image of f¯ replacing x¯i by xi and y¯ by x1−1⋯xn−1.Theorem 2.
Lets1,…,sm be a set of generators for Syzf1,…,fr,x1…xny−1; then, s¯1,…,s¯m is a set of generators for Syzf¯1,…,f¯r.Proof.
Sinceq¯1f¯1+⋯+q¯rf¯r=0 is equivalent to q1f1+⋯+qrfr+q⋅x1…xny−1=0 with q∈Rx1,…,xn,y, the Rx1,…,xn,y-homomorphism(7)Syzf1,…,fr,x1…xny−1⟶Syzf¯1,…,f¯r,s=q1,…,qr,q⟼s¯=q¯1,…,q¯ris surjective. We conclude that if s1,…,sm is a set of generators for Syzf1,…,fr,x1…xny−1, then s¯1,…,s¯m is a set of generators for Syzf¯1,…,f¯r.


## 4. Illustrative Examples

Example 1.
LetI be the ideal of ℤx±1,y±1 generated by(8)f1=10y−1+1,f2=6x2y+3x−1y−1,f3=12x−y+6x−2y−2−10.
To compute a set of generators forSyzf1,f2,f3, we rely on the isomorphism between ℤx±1,y±1 and ℤx,y,t/xyt−1. It is equivalent to compute a set of generators for Syzg¯1,g¯2,g¯3 with(9)g¯1=10x¯t¯+1,g¯2=6x¯2y¯+3t¯,g¯3=12x¯−y¯+6t¯2−10.
First of all, let us compute inℤx,y,t a set of generators for Syzg1,g2,g3,g4 with(10)g1=10xt+1,g2=6x2y+3t,g3=12x−y+6t2−10,g4=xyt−1.
Let us use the lexicographic order withx>t>y as monomial order to compute a dynamical Gröbner basis for J=g1,g2,g3,g4 in ℤx,y,t. As the leading coefficients of g1 and g2 are not comparable under division in ℤ and l cm10,6=2, we can open two following leaves to proceed:(11)
Inℤ5, Sg1,g2=3/5xyg1−tg2=3/5xy−3t2≔g5. Since the leading coefficients of g1 and g5 are not comparable, we need to open two new leaves as(12)
Inℤ5.3, G5.3=y+10,2x+t2,1−5t3 is a special Gröbner basis for J at the leaf ℤ5.3. And over ℤ5.3x,y,t, we have Syzg1,g2,g3,g4 as(13)2xy+yt2ty+10t30−10t2+2xy,yt3+2t2y+10t230−10t3+2+2xyt+20xt,2x+t25−115t−23xt2025x+4x2t,3xyt2−3t−xyt+10−30xt2+6x2y,y−2t1−10+12x,−xyt+10010xt+1.
Inℤ5.2, we find G5.2=y+10,6x+3t2,3/5−3t3,10xt+1 as a special Gröbner basis for J at the leaf ℤ5.2, and we have the following Syzg1,g2,g3,g4 over ℤ5.2x,y,t:(14)−310t2−35x110t+10xt20−35x−6x2t,6xy+3yt2−ty−10t0−30t2+6xy,−6−3yt3t2y+10t20−6+30t3−6xyt−60xt,65x+35t2−15t−2xt2065x+12x2t,3xyt2−3t−xyt+10−30xt2+6x2y,y−2t1−10+12x,−xyt+10010xt+1.
Inℤ3, we proceed as above, and we will open two leaves:(15)
G
3.2
=
y
+
10,2
x
+
t
2
,
1
−
5
t
3 is a special Gröbner basis for J at the leaf ℤ3.2, and we get Syzg1,g2,g3,g4 as(16)xy+12t2−ty−10t60−5t2+xy,−5yt3+105t2y+50t23050t3−10−10xyt−100xt,−x−12t216t+53xt20−x−10x2t,3xyt2−3t−xyt+10−30xt2+6x2y,y−2t1−10+12x,−xyt+10010xt+1.
Note thatG3.5=G5.3.
Finally,Syzg1,g2,g3,g4 over ℤx,y,t is(17)15yt3+2−5t2y+100−10t3+2+2xyt+20xt,3y2x+t2−ty+100−30t2+6xy,−6x+3t2t1+10xt0−6x1+10xt,y−2t1−10+12x,3xyt2−3t−xyt+10−30xt2+6x2y,−xyt+10010xt+1.
Note thatx¯y¯t¯=1. Hence, a set of generators for Syzg¯1,g¯2,g¯3 is(18)15y¯t¯3+2−5t¯2y¯+100,3y¯2x¯+t¯2−t¯y¯+100,−6x¯+3t¯2t¯1+10x¯t¯0,y¯−2t¯1.
Therefore, a set of generators forSyzf1,f2,f3 is(19)15y−2x−3+30−5x−2y−1−50x−2y−20,6xy+3x−2y−1−x−1−10x−1y−10,−6x−3x−2y−2x−1y−1+10x−1y−20,y−2x−1y−11.
Finally, a set of generators ofSyzf1,f2,f3 over ℤx±1,y±1 is(20)6xy+3x−2y−1−x−1−10x−1y−10,y−2x−1y−11.
Now, let us see an example where the basic ring is not principal.Example 2.
Let us consider the ringℤθy±1,z±1, where θ2=−5 is its ideal I generated by(21)f1=8+4θz−1−y−1+15y−1z−1,f2=1+3z−1,f3=4+2θy+9.
To compute a set of generators forSyzf1,f2,f3, we rely on the isomorphism between ℤθy±1,z±1 and ℤθx,y,z/xyz−1. It is equivalent to compute a set of generators for Syzg¯1,g¯2,g¯3 with(22)g¯1=8+4θx¯y¯−x¯z¯+15x¯,g¯2=3x¯y¯+1,g¯3=4+2θy¯+9.
First of all, let us compute inℤθx,y,z a set of generators for Syzg1,g2,g3,g4 with(23)g1=8+4θxy−xz+15x,g2=3xy+1,g3=4+2θy+9,g4=xyz−1.
Using the lexicographic order withx>y>z as monomial order, we proceed as above by computing a dynamical Gröbner basis for J=g1,g2,g3,g4 in ℤx,y,z.
Let us denote bya and b the leading coefficients of g2 and g3, respectively. Since a≔3 and b≔4+2θ are not comparable, we have to find u,v,w∈ℤθ such that(24)ub=va,wb=1−ua.
With the solution of this system given byu=5+2θ,v=6θ, and w=−3, we can open two leaves:(25)
Inℤθ4+2θ:(26)Sg2,g3=g2−34+2θg3=−274+2θx+1≔g5,Sg2,g4=zg2−3tg4=z+3≔g6,Sg2,g5=−94+2θg2−ytg5=−94+2θ−y⟶g30,Sg2,g6=zg2−3xyg6=z−9xy⟶g2g6⟶g60and,g1⟶g3−xg6⟶g60,Sg3,g5=−274+2θ2xg3−yg5=−2434+2θ2x−y=−14+2θg3+94+2θg5⟶g50,Sg3,g6=zg3−4+2θyg6=9z−34+2θy=−3g3+9g6⟶g3g60,g4⟶g6−g2⟶g20,Sg5,g6=zg5+274+2θxg6=−3g5+g6⟶g5,g60.
Thus,4+2θy+9,−27/4+2θx+1,z+3 is a special Gröbner basis for J at the leaf ℳ4+2θ−1ℤ=ℤ4+2θ.
And we have onℤ4+2θx,y,z,Syzg1,g2,g3,g4 as(27)0−4+2θy+94+2θ1+3xy4+2θ0,0−4yz−2θyz−9zz+312y+6θy+27,012+6θ+27xz4+2θ−3xz−9x4+2θ−81x+12+6θ4+2θ,1xz−2x−3x.
Inℤθ5+2θ¯, as 2 and 3 are not comparable under division in ℤθ5+2θ, in order to pursue the computations, we need to open two new leaves:(28)
The final evaluation tree is given by(29)
Inℤθ5+2θ.2¯, we get z+3,−6+3θ/2x+1,2θ/5+2θy+1 as a special Gröbner basis for(30)8+4axy−xz+15x,3xy+1,4+2θy+9,xyz−1,at the leaf ℳ5+2θ,2−1ℤθ=ℤθ5+2θ⋅2. And over ℤθ≤5+2θ⋅2x,y,z,Syzg1,g2,g3,g4 is(31)15xz+2θxz−90x−36θx−36θxy+270x2y+108θx2y+108θx2y25+2θ−18x3y2−3x,02−θ−6θ+45x+18xθ+6xyzθ+18xyθ25+2θθ−2x2yz+3x2y25+2θ2−θ45x+18xθ−6θ2,02−θ18θxy2+6xyzθ−6θy+18xyθ+6θxy2z−15+45xy+15xyz25+2θθ−25x2y2z+2θx2y2z+15x2y2+6θx2y225+2θ2−θ−6θy−15−6θ25+2θ,01−4θ−90θx2y2+180x2y2−45x2y−180θx2y45+2θ21−4θ5x2y+2θx2y+15x3y2+6θx3y245+2θ0,0−45−18θ−18θy+135xy+54θxy+54θxy25+2θ1−9x2y20.
Inℤθ5+2θ⋅3, we get z+3,3x−2θ/5+2θ,2θ/5+2θy+1 as a special Gröbner basis for(32)8+4axy−xz+15x,3xy+1,4+2θy+9,xyz−1,at the leaf ℳ5+2θ,3−1ℤθ=ℤθ5+2θ.3. And on ℤθ5+2θ⋅3x,y,z,Syzg1,g2,g3,g4 is(33)15xz+2θxz−90x−36θx−36θxy+270x2y+108θx2y+108θx2y25+2θ−18x3y2−3x,02θ−15x−6xθ−2xyzθ−6xyθ5+2θx2yz+3x2y3−15x−6xθ+2θ5+2θ,0−45−18θ−18θy+135xy+54θxy+54θxy25+2θ1−9x2y20,018θxy2+6xyzθ−6θy+18xyθ−6θxy2z−15+45xy+15xyz5+2θ−x2y2z−3x2y2−6θy−15−6θ5+2θ,06θx2y2+15x2y+6θx2y5+2θ−x2y−3x3y230.
Hence, overℤθx,y,z, a generating set of Syzg1,g2,g3,g4 is(34)0−4y−2θy−91+3xy0,0−4yz−2θyz−9zz+312y+6θy+27,1xz−2x−3x,012+6θ+27xz−3xz−9x−81x+12+6θ,5+2θ5xz+2θxz−90x−36θx−36θxy+270x2y+108θx2y+108θx2y2−90+36θx3y2−15+6θx,0−6θ+45x+18xθ1+y+6xyzθ−5+2θx2yz+3x2y45x+18xθ−6θ,018θxy2+6xyzθ−6θ−6θy+18xyθ+6θxy2z−15+45xy+15xyz−5x2y2z−2θx2y2z−15x2y2−6θx2y2−6θy−15−6θ,0−90θx2y2+180x2y2−45x2y−180θx2y5+2θ5x2y+2θx2y+15x3y2+6θx3y20.
Note that we havex¯y¯z¯=1, and over ℤθy±1,z±1, the generation is reduced to Syzf1,f2,f3 as(35)11y−2yz,0−4yz−2θyz−9zz+3,5+2θ25+2θy−90+36θyz−36θz+270+108θyz2+108θy2z2−90−36θyz3.
In fact the trick in Lemma2 can be used for computing syzygies of a finite system in any module M1/u over A1/u when A is a coherent A−module. Here, M=A=Rx1,…,xn and u=x1…xn.
Note that a generator set for the syzygy module off1,…,fs over the Laurent polynomial ring Rx1±1,…,xn±1 can be directly computed in Rx1,…,xn by multiplying f1,…,fs by a polynomial such that the new vector obtained is in Rx1,…,xn, by virtue of Theorem1. The syzygy module does not change and the problem is reduced to a computation of a generator set for the syzygy module in Rx1,…,xn.Example 3.
LetI=F1=8Y−1+X−2Y−2,F2=10XY−2−2X−2Y−2 in ℤX±1,Y±1. The problem of computing a generator for the syzygy module of I can be reduced to find a generator for the syzygy module of f1=8X2Y+1,f2=10X3−2 in ℤX,Y.
f
1
,
f
2 is obtained by multiplying F1,F2 by X2Y2.
Let us consider the lexicographic order withX>Y.
As8∧10=2,8=2×4, and 10=2×5, we have to open two leaves: ℤ4 and ℤ5.
Inℤ4, Sf1,f2=5/4Xf1−Yf2=5/4X+2Y=:f3. The leading coefficients of f1 and f3 are comparable under division. As 8∧5/4=2∧5=1, we open in ℤ4 two new leaves ℤ4.2 and ℤ4.5.
Inℤ4.2:(36)Sf1,f3=5/32f1−XYf3=532−2XY2≔f4,Sf1,f4=Yf1+4Xf4=12f3⟶f30,Sf2,f4=Y2f2+5X2f4=58X−Yf3⟶f30,Sf3,f4=Y2f3+5/8f4=2Y3+25256≔f5,Sf1,f5=Y2f1−4X2f5=−516X+12Yf3⟶f30,Sf2,f5=Y3f2−5X3f5=−2564X2+58XY−Y2f3⟶f30…,Sf3,f5=Y3f3−58Xf5⟶f3Yf5⟶f50,Sf4,f5=Yf4+Xf5=564f3⟶f30.
So,G1=f1,f2,f3,f4,f5 is a special Gröbner basis for f1,f2 over ℤ4.2X,Y.
We obtain(37)SyzF=2−10X31+8X2,Y2−58XY−5X3Y2+258X4Y12Y2−516XY+4X2Y3−52X3Y2,overℤ4.2X,Y.
Inℤ4.5X,Y, we obtain G2=1+8X2,10X3−2,5/4X+2Y,1−64/5XY2,2Y3+25/256 as special Gröbner basis for f1,f2 over ℤ4.5X,Y.
Also,(38)SyzF=2−10X31+8X2Y,Y2−58XY−5X3Y2+258X4Y−516XY+12Y2+4X2Y3−52X3Y2,overℤ4.5X,Y.
We findG3=1+8X2,10X3−2,X+8/5Y,1−64/5XY2,−512/25Y3−1 as special Gröbner basis for f1,f2 over ℤ5X,Y.
Also,(39)SyzF=2−10X31+8X2Y,85XY−6425Y2−8X4Y+645X3Y245XY−3225Y2−25625X2Y3+325X3Y2,overℤ5X,Y.
Finally, we obtain(40)Syzf1,f2=2−10X31+8X2Y,16Y2−10XY−80X3Y2+50X4Y−5XY+8Y2+64X2Y3−40X3Y2,overℤX,Y.
The two approaches used give similar results. In the approach used in the last example, there is one less polynomial than using the isomorphism approach, but the calculations remain similar and relationx1¯…xn¯=1 allows simplifications with the isomorphism approach.



---

*Source: 5803914-2020-05-01.xml*