# The Extension of the GVW Algorithm to Valuation Domains

Authors: Dongmei Li; Licui Zheng
Journal: Complexity
 (2021)

---

## Abstract

The GVW algorithm is an effective algorithm to compute Gröbner bases for polynomial ideals over a field. Combined with properties of valuation domains and the idea of the GVW algorithm, we propose a new algorithm to compute Gröbner bases for polynomial ideals over valuation domains in this study. Furthermore, we use an example to demonstrate the improvement of our algorithm.


---

## Body

## 1. Introduction

The notion of Gröbner basis was first put forward by Buchberger [1]. The theory of Gröbner has been widely applied in numerous fields such as engineering, signal processing, neuroscience, coding theory, complexity, and control of networked dynamical systems and so on. For example, in the theory of symbolic dynamic systems, the problems of determining whether there is a shift equivalence of lag from one nonnegative matrix to another can be transferred into solving large-scale equations, while the latter can be solved by the Gröbner basis theory [2–13].Seeking more efficient algorithms for the computation of Gröbner bases is a problem in which many researchers cared about extremely [14–19]. Faugère [19] proposed a fast algorithm called F5 for computing Gröbner bases. In this algorithm, he introduced two notions of rewriting and signatures, which allow them to filter the useless S-polynomials in a rather convenient way. A new algorithm named G2V [20] for computing Gröbner bases is presented by Gao et al., which is an algorithm of incremental signature and based on a simple theory. A few months later, they gave an extend version named the GVW algorithm [21]. We are particularly interested in the GVW algorithm which not only matches the original algorithm given by Buchberger in simplicity but also more effective than F5 under some term orders. The algorithms mentioned above are applied to polynomial ideals over fields.Several algorithms have been widely investigated for Gröbner bases to rings, such as Euclidean domain, principle ideal domain, and valuation rings that may contain zero divisors [22–24].In this study, we aim to extend the GVW algorithm to valuation domains and present a signature-based algorithm to compute Gröbner bases for ideals inR=Vx1,…,xn, where V is a valuation domain. In this algorithm, we study relations between J pairs and propose a new concept named factor, which allows us to filter the useless J pairs in a rather convenient way.The structure of the study is arranged as follows: some basic concepts of the Gröbner basis theory is given in Section2. In Section 3, we propose theory for the GVW algorithm over valuation domains and obtain main results of this study. Then, we present the new algorithm and demonstrate the improvement clearly by an example in Section 4.


## 2. Preliminaries

LetV be a valuation ring. For any two nonzero elements a,b∈V, there always exists a|b or b|a. The term order for monomials in R=Vx1,…,xn is arbitrary throughout this section. The form of the monomial in R is(1)xα=x1a1,x2a2,…,xnan,where α=a1,a2,…,an∈ℕn. The definition of the leading monomial (abbreviated as lm), the leading term (abbreviated as lt), and the leading coefficient (abbreviated as lc) of a given polynomial is as usual.A nonzero polynomial setGw in an ideal I is named as (weak) Gröbner basis for I if(2)ltGw=ltI.This does not imply that, for eachf∈I, there exists some polynomial g∈Gw, so that ltg|ltf. For example, I=2x,3y⊂ℤx,y has a Gröbner basis G=2x,3y, and xy=−y2x+x3y∈I, but xy is not divisible by 2x nor 3y in ℤx,y.Definition 1.
A setGs is called a strong Gröbner basis for I if ∀f∈I, and there is a polynomial g∈Gs, so that ltg|ltf, where Gs is formed by the nonzero polynomials from I.
For the above example,2x,3y,xy is a strong Gröbner basis of the ideal I, but the set 2x,3y is not. This shows already some difference when dealing with polynomials over rings from those over fields.Proposition 1.
SupposeV is a valuation domain. Then, every ideal in Vx1,…,xn has a strong Gröbner basis.Proof.
It can be easily obtained by properties of valuation ring.
We now follow the notations in [21]. Let R=Vx1,…,xn, where V denotes a valuation domain, and h1,…,hm∈R are the polynomials. Let(3)I=h1,…,hm=p1h1+⋯+pmhm:p1,…,pm∈Rm⊆Rbe an ideal, and its Gröbner basis is what we want to obtain. Vectors in Rm are denoted by bold letters, for example, p=p1,…,pm. Let ej be the jth unit vector in Rm for 1≤j≤m. Define an R submodule of Rm×R:(4)M=p,f∈Rm×R:pht=f,that is,p1h1+⋯+pmhm=v.
Note that, as anR module, M is generated by(5)e1,h1,e2,h2,…,em,hm.
H=p1,…,pm∈Rm:p1h1+⋯+pmhm=0 is defined to be the syzygy module of h=h1,…,hm. We shall see that the big module M allows us to get the Gröbner bases for I and H in the same time and allows us to develop a criterion to detect useless S polynomials.
We define quasiordering inV: for arbitrary a,b∈V, we say a≺¯b if a|b. Following this definition, then a term order (throughout this study, by a monomial order, we mean a global ordering [21]) ≤ on R is defined by a1t1≤a2t2 iff(6)t1≤t2ort1=t2,a1|a2.
We assumeRm has a term order that is compatible with that of R. We refer the readers to [21] for several examples on how term order of R can be extended to Rm. Note that a term in Rm is the form as(7)xαei,for some α∈ℕm and 1≤i≤m. For any nonzero p∈Rm,(8)ltp=lcp·lmp,where lmp is the leading monomial of p, and lcp∈V is the leading coefficient of p.


## 3. Theory of the Algorithm

In this section, we present the theory of our algorithm. First, some basic definitions are needed.Definition 2.
ltp is said to be the signature of p,f, where p,f∈Rm×R.Definition 3.
We sayp1,f1∈Rm×R can be top-reduced by p2,f2∈Rm×Rltf2≠0 when they meet the following two conditions:(i)
ltf2 divides ltf1 (i.e., f2 is top-divisible by f1) and(ii)
ltt⋅p2≺¯ltp1, where t=ltf1/ltf2
Then, the relevant top-reduction is(9)p1,f1−tp2,f2=p1−tp2,f1−tf2.
Hence, we can divide this reduction into two types; one is called regular when(10)lmtp2≺lmp1,and the other is called super if(11)ltp1ltp2=ltf1ltf2.
Besides, there is another super top-reduction, that is, whenf2=0, we say that p1,f1 is super top-reduced by p2,0 if p1 and p2 are both nonzero and ltp2 divides ltp1. So when a pair p1,f1 can be reduced by p2,0, we just reduce the signature of p1,f1 but without increasing ltf1 (even if f1=0). What attracts more of our attention is that p1,0 is never top-reduced by p2,f2 when f2≠0.
Similar to Definition1, we give the definition of strong Gröbner basis for M in the following.Definition 4.
SupposeGs is a subset of M, Gs is said to be a strong Gröbner basis of M, if every pair p,f∈M can be top-reduced by at least one pair in Gs.
It is easy to draw a conclusion from this definition, that is, every pair inM can be top-reduced to 0 by its strong Gröbner basis.Lemma 1.
IfGs is a strong Gröbner basis of M, where Gs=p1,f1,…,pk,fk, then(1)
A strong Gröbner basis for the syzygy module ofh=h1,…,hm exists, which is G0=pi:fi=0,1≤i≤k(2)
The strong Gröbner basis forI=h1,…,hm also exists, which is G1=fi:1≤i≤kProof.
Assumep=p1,…,pm is an element from the syzygy module of h, then p,0∈M, and there must exist some pair pi,fi in Gs that can top-reduce p,0 with fi=0. Thus, pi∈G0 and ltp can be reduced by ltpi. This tell us that G0 is the set we need, which is a Gröbner basis for the syzygy module of h.
For an arbitrary nonzero polynomialv∈I, there is p=p1,…,pm∈Rm, such that pht=f according to the definition of Rm and then p,f∈M. Among all such p, we choose the minimum ltp. By our assumption, there exists at least one pair in G which can top-reduce p,f.
Iff=0, then p,f can be reduced by pi,0 and get p′,f, but p′ht=f, which contradicts the minimality of ltp as ltp′<ltp. So there exists pi,fi∈G1 with fi≠0 and ltfi|ltf. Hence, G1 is a Gröbner basis of I.Definition 5.
For any pair,P1=p1,f1,P2=p2,f2∈Rm×R, and f1≠0,f2≠0. Let(12)t=lcmlmf1,lmf2,t1=tlmf1,t2=tlmf2.(i)
Ifmaxlmt1p1,lmt2p2=t1lmp1, define(13)JP1,P2=t1P1,if lcf2|lcf1,lcf2lcf1t1P1,if lcf1|lcf2.(ii)
Ifmaxlmt1p1,lmt2p2=t2lmp2, define(14)JP1,P2=lcf1lcf2t2P2,if lcf2|lcf1,t2P2,if lcf1|lcf2.Remark 1.
With notations as above, we do not define J pair forP1=p1,f1 and P2=p2,f2 when one of f1 and f2 is zero nor when lmt1p1=lmt2p2.
In order to study the relation between J pairs, we propose the following conception:Definition 6.
Supposet1p1,f1,t2p2,f2 are the J pairs formed from G which is a (finite) subset of M, and t1p1,f1 is called a factor of t2p2,f2 if(15)at1ltp1w=t2ltp2,at1ltf1w≺¯t2ltf2,for some monomial aw,a∈V.
The next result is very useful for reduction.Lemma 2.
Assumeatpj,fj can be regular top-reduced by pi,fi with neither of fi,fj is zero, where a is an element from V and t is a monomial from R; then, c1t1pj,fj is the J pair of pi,fi and pj,fj, where(16)c1=lcmlcfj,lcfilcfj,t1=lcmlmfj,lmfilmfj,where c1 is a divisor of a, t1|t, and pi,fi can regular top-reduce c1t1pj,fj.Proof.
By our assumption, there exista1∈V and a monomial say w1∈R, so that(17)atltfj=a1w1ltfi,w1lmpi≺¯tlmpj.
Set(18)c2=lcmlcfj,lcfilcfi,t2=lcmlmfj,lmfilmfi,we have that(19)c2t2=lcmlcfj,lcfilcfi·lcmlmfj,lmfilmfi=lcmltfj,ltfiltfi.
Then, somea2∈V and monomial w2∈R exist, such that(20)a2w2lcmltfj,ltfi=atltfj=a1w1ltfi.c1t1=lcmlcfj,lcfilcfj·lcmlmfj,lmfilmfj=lcmltfj,ltfiltfj.
Thus,(21)a1w1ltfi=a2w2c2t2ltfi,atltfj=a2w2c1t1ltfj,alcfj=a2c1lcfj,a1lcfi=a2c2lcfi,tlmfj=t1w2lmfj,w1lmfi=t2w2lmfi.
Then, we have that(22)a=a2c1,a1=a2c2,c1|a,t=t1w2,w1=t2w2.
Hence,c1t2ltpi≺c2t1ltpj as slmpi≺tlmpj. Thus, maxt2lmpi,t1lmpj=t1lmpj. And the J pair of pj,fj and pi,fi is c1t1pj,fj by Definition 5. Note that(23)atltf1=a1w1ltf2,and then,(24)a2c1t1w2ltfj=a2c2t2w2ltfi.
Therefore,(25)ltfi|c1t1ltfj.
We see thatpi,fi can regular top-reduce c1t1pj,fj.
SupposeS is a set formed by the pairs in Rm×R, we say S can regular (super) top-reduce the pair p,f∈Rm×R, if there is at least one pair in S which can regular (super) top-reduce the pair p,f. Furthermore, we implement a series of such reductions to p,f until it cannot be regular top-reduced by this set anymore, but p,f can be super top-reduced by S, and this reduction defined as p,f is eventually super top-reduced by S.Theorem 1.
SupposeT is any term in Rm, and there always exists a pair pi,fi in Gs, a monomial t∈R and a∈V, such that T=atltpi, where Gs is a subset of M. Then, Gs is a strong Gröbner basis for M if and only if, for the J pairs formed from Gs such as p,f, there always exists a pair p1,f1∈Gs, so that ltp1|ltp and tlmf1≺lmf, where t=lmp/lmp1.Proof.
Necessity: letp,f be an arbitrary J pair formed from Gs; then, p,f is in M, and it is top-reduced by Gs as the set Gs is a strong Gröbner basis for the module M. We can do the regular top-reductions to p,f as much as possible until p,f cannot be regular top-reduced any more, say to get p0,f0. And p0,f0 can be top-reduced by Gs as it is still in M; but now, the reduction can only be super reduction, say p0,f0 can be super reduced by p1,f1∈Gs.(1)
Iff1=0, then ltp1|ltp0=ltp, and tf1=0 is smaller than lmf, and the conclusion is true.(2)
Iff1≠0,(26)t=lmf0lmf1=lmp0lmp1,lcf0lcf1⋅lcp1≺¯lcp0.
Combined with the definition of quasiordering given, we have that(27)lcf0lcf1⋅lcp1|lcp0,and then, lcp1|lcp0.
Sincep0,f0 is obtained by performed regular top-reduction to p,f, then lmf0≺lmf and ltp0=ltp; the latter shows that(28)tlmf1=lmf0≺lmf.
So,ltp1|ltp0=ltp and tlmf1≺lmf.
Sufficiency:  suppose there are some pairs inM which cannot be top-reduced the set Gs, say p,f∈M is such a pair. We prove that such a pair does not exist. Select the minimal signature T=ltp from all such pairs with ltp≠0, and we choose a pair pj,fj from Gs, so that(i)
T=atltpj with a∈V and t is a monomial in R, and(ii)
tlmfj is the smallest one among all 1≤j≤k satisfying (i)
In the following, we prove thatatpj,fj should not be regular top-reduced by Gs. Suppose that atpj,fj could be regular top-reduced by a pair pi,fi, i≠j, then fj≠0,fi≠0. What we expect is to get a conclusion that contradicts condition (ii). From Lemma 2, we have that c1t1pj,fj is the J pair of pj,fj and pi,fi; moreover, it can still be regular top-reduced by pi,fi, where(29)c1=lcmlcfi,lcfjlcfj,t1=lcmlmfj,lmfilmfj,t=t1w,c1|a,for some c1∈V and monomial w∈R.Case 1.
Iflcfi|lcfj, then c1=1, and the J pair of pi,fi and pj,fj is t1pj,fj. Note that t1pj,fj is a J pair formed from Gs, so there must exists a pair pℓ,fℓ∈Gs, so that ltpℓ|t1ltpj and t3lmfℓ≺t1lmfj with t3=t1lmpj/lmpℓ. Since lcpℓ|lcpj, we set a3=lcpj/lcpℓ, and then,(30)a⋅a3t3wltpℓ=a⋅t1wlcpj⋅lmpj=at1wltpj=atltpj=T,t3wlmfℓ≺wt1lmfj=tlmfj.
This contradicts the condition (ii) for the selection ofpj,fj in Gs.Case 2.
Iflcfj|lcfi, then c1=lcfi/lcfj, and the J pair of pi,fi and pj,fj is lcfj/lcfit1pj,fj. Note that lcfi/lcfjt1pj,fj is a J pair formed from Gs, and there must exist some pair say pℓ,fℓ∈Gs, such that ltpℓ|lcfi/lcfjt1ltpj and t3lmfℓ≺t1lmfj with t3=t1lmpj/lmpℓ. Since lcpℓ|lcfi/lcfjlcpj, set a3=lcfi/lcfj⋅lcpj/lcpℓ, and then,(31)alcfi/lcfja3t3wltpℓ=alcfi/lcfjlcfilcfjt1wlcpj⋅lmpj=at1wltpj=atltpj=T,t3wlmfℓ≺wt1lmfj=tlmfj.
This contradicts the condition (ii) for the selection ofpj,fj in Gs.
Let(32)p˜,f˜=p,f−atpj,fj,and then, lmp˜≺lmp and ltf≠atltfj. Otherwise, p,f would be top-reduced by pj,fj which contradicts with the selection of p,f. So, f˜≠0 and p˜,f˜ can be top-reduced by Gs as p˜,f˜∈M and lmp˜≺lmp, ltp˜≺ltp, say it is top-reduced by pk,fk. If fk=0, we use this type of pairs to reduce p˜,f˜ as much as possible and obtain a new pair p′,f˜ finally, which cannot be top-reduced by the same type of pairs (here, it refers the pairs whose f-part is zero) in Gs. Since p′,f˜∈M and lmp′≺lmp, ltp′≺ltp, and then p′,f˜ can be top-reduced by Gs, say by pk′,fk′, fk′≠0. For ltf≠atltfj, there are the following three cases that need to be considered:(i)
Iflmf≺tlmfj, then ltf˜=atltfj; but lmp′≺tlmpj, so there must exist some pairs in Gs that can regular top-reduce atpj,fj; assume the pair in Gs is pk′,fk′. This is impossible as atpj,fj cannot be regular top-reduced by any pair in Gs.(ii)
Iflmf≻tlmfj, then lmf˜=lmf, and p,f can be regular top-reduced by pk,fk; this contradicts the choice of p,f.(iii)
Iflmf=tlmfj and lcf≠alcfj, p˜,f˜ is top-reduced by pk′,fk′, and then, ltfk′|ltf˜; this means that lmfl′|lmf˜ and lcfk′|lcf˜=lcf−alcfj.
From the property of valuation ring, we consider the relation betweenalcfj and lcf in the following three cases:(a)
Ifalcfj=blcf and b is not a nonzero unit, note that a valuation ring is a local ring, and b is in the unique maximal ideal. Since lcfk′|lcf−alcfj=1−blcf and 1−b is invertible, then lcfk′|lcf. Note that lmf/lmfk′lmpk′≺¯lmp′≺lmp and p,f are regular top-reduced by pk,fk; this contradicts the choice of p,f.(b)
Ifalcfj⋅b=lcf and b is not a nonzero unit, note that a valuation ring is a local ring, and b is in the unique maximal ideal. Since lcfk′|lcf−alcfj=1−balcfj and 1−b is invertible, then lcfk′|alcfj. Note that tlmfj/lmfℓ′lmpk′≺¯lmp′≺lmp=tlmpj, then atpj,fj is regular top-reduced by pk,fk, and this case is impossible.(c)
Ifalcfj=blcf and b is a nonzero unit, then alcfj|lcf and lcf/alcfj=b−1. Note that ltp=atltpj; combining the definition of the order, we have b−1⋅altpj≺¯ltp. Therefore, p,f can be top-reduced by atpj,fj, and this contradicts the choice of p,f.
Thus, such pairs likep,f cannot exist in M at all; hence, all pairs of M can be top-reduced by Gs, and Gs is a strong Gröbner basis for M.
The pairp=p,f is covered by Gs when there exists at least one pair such as p1=p1,f1 in Gs, such that ltp1|ltp and tlmf1<lmf, where t=lmp/lmp1.Theorem 2.
SupposeGs is a special subset of M, whose particularity is reflected in for any term T∈Rm, there always exists a pair pi,fi∈Gs and monomial t∈R and a∈V, such that T=atltpi. Then, Gs is a strong Gröbner basis for M if the factors of the J pairs formed by Gs can always be eventually super top-reduced by the set Gs.Proof.
Assume thatt1p1,f1,t2p2,f2 are the two J pairs formed by G, and t1p1,f1 is a factor of t2p2,f2. Then, t1p1,f1 can be eventually super top-reducible by Gs, that is, after doing a series of regular top-reduction to t1p1,f1, say it to get p′,f′ where ltp′=t1lmp1,ltf′<t1ltf1; besides, p′,f′ can be super top-reduced by Gs, say pi,fi; then, ailtpi=t1ltp1,aitiltfi<t1ltf1, where aiti=ltf′/ltfi. Clearly, t2p2,f2 can be covered by pi,fi. It is also correct for the rest of J pairs and their factors. By Theorem 1, we have that Gs is a strong Gröbner basis for M.
According to Theorems1 and 2, we can discard the J pairs which can be covered by Gs without doing any regular nor super top-reductions. As a consequence, there are four criteria for discarding redundant J pairs.Corollary 1.
(Covered criterion) For any J pairp,f of Gs, it can be discard if p,f is covered by Gs.Corollary 2.
(Syzygy criterion) If a J pairp,f can be top-reduced by a syzygy, then it can be discarded.Corollary 3.
(Signature criterion) As for the J pairs with the same signature, we only need to keep the one whosef-part is minimal.Corollary 4.
(Factor criterion) As for the J pair which has a factor, we just need to keep the factor.


## 4. Algorithm and Example

According to the theorems and corollaries in Section3, we can get an algorithm for computing Gröbner bases for the polynomial ideals over valuation domains. We call the algorithm as VID−GVW. The main idea of VID−GVW is analogue to the GVW algorithm of principal ideal domain [23]. First, we form J pairs by the initial pairse1,g1,…,em,gm. By Theorems 1 and 2, we just store the J pairs with different signatures. We only consider the J pairs that we store, choose any one of them, denoted as p,f, and then check whether it satisfies Corollary 1, that is, whether it is covered by Gs. If so, discard it. Otherwise, delete all the J pairs whose factor is p,f and perform regular top-reductions to it repeatedly until it cannot be regular top-reduced any more, say to get p′,f′ finally. If f′=0, then p′ is a syzygy in H. We add it to H and delete the pairs whose signature is divisible by ltp′. Otherwise, p′,f′ adds to the set JP, and we will not stop the process until the set of J pair is empty. In the while-loop, all the J pairs formed from Gs will be top-reduced by the set Gs. We describe the algorithm in more detail and accurately with Figure 1. H is used to store the leading terms of syzygies; the Gröbner basis we get is a list of pairs T1,f1,T2,f2,…,Tk,fk, where fj≠0 for 1≤j≤k. We store this list as(33)P=T1,T2,…,Tk,F=f1,f2,…,fk.Figure 1
VID-GVW.So the whole listT1,f1,T2,f2,…,Tk,fk is represented by P,F.Theorem 3.
Assume the term orders inR are compatible with which in Rm; then, the algorithm shown in Figure 1 will terminate after a finite number of steps and get a strong Gröbner basis for M.Proof.
The correctness of our algorithm is obviously according to Theorems1 and 2. As for the termination of the algorithm, we can refer to the Theorem 1 in [21].
Next, we present our algorithm and use a concrete example to demonstrate the improvement clearly.Example 1.
LetVx,y=ℤ33x⋅y, and we consider the Gröbner basis of the ideal I=f1,f2,f3∈Vx,y, where(34)f1=x2y−x,f2=xy2−xy,f3=y3,and ℤ33 is a discrete valuation ring, for each prime p (here is 3); set vp:Q∗⟶ℤ is a function given by vppka/b=k if a,b are integers relatively prime to p.
The term order we set onVx,y is the lexicographical ordering, which is defined by y≺x. Besides, the term order ≺ on Vmx,y is xαei≺xβej if i<j or i=j and xα≺xβ.
First, letP,F=e1,f1,e2,f2,e3,f3; then, H=xy2e1,y3e1,y3e2, which is a set that stands for leading term of principle syzygy.
Choosee1,f1,e2,f2 from P,F; then, lcmlmf1,lmf2=x2y2. Hence, t1=y,t2=x, and J pair of e1,f1 and e2,f2 is ye1,f1, whose signature cannot be reduced by H, and we store it.
Doing the same process, theJ-pairs set of other pairs in P,F is y2e1,f1,ye2,f2, but ye1,f1 is a factor of y2e1,f1, so delate. Then,(35)JP=ye1,f1,ye2,f2.
Selectingye2,f2 from JP, we get y+1e2−xe3,−xy after a series of regular top-reduction, add it to P,F, and recalculate the J pairs and(36)H=xy2e1,y3e1,y3e2.
Using the syzygy criterion and factor criterion, we obtain(37)JP=ye1,f1,yy+1e2−xe3,−xy.
Selectyy+1e2−xe3,−xy from JP; it can be regular top-reduced to yy+1e2−xe3,0 and add y2e2 to H.
Selectye1,f1 from JP; it can be regular top-reduced to ye1,0 and add ye1 to H.
Now,JP=∅. So x2y−x,xy2−xy,y3,−xy is a strong Gröbner basis for I in Vx,y.


## 5. Conclusions

In this study, we have generalized the GVW algorithm and presented an algorithm to compute Gröbner bases for polynomial ideals over valuation domains. We have also given an example to illustrate our method. All of these could provide useful information for engineers to solve large linear systems and networked dynamical systems. Valuation domains are special kinds of valuation rings which may have zero divisors. In the future, we want to consider new algorithms for Gröbner bases of ideals over general valuation rings. And we also hope to establish a dynamical Gröbner basis algorithm which combined with the algorithm in the study.



---

*Source: 7010413-2021-06-07.xml*