# An Algorithm to Compute the H-Bases for Ideals of Subalgebras

Authors: Rabia; Muhammad Ahsan Binyamin; Nazia Jabeen; Adnan Aslam; Kraidi Anoh Yannick
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

The concept of H-bases, introduced long ago by Macauly, has become an important ingredient for the treatment of various problems in computational algebra. The concept of H-bases is for ideals in polynomial rings, which allows an investigation of multivariate polynomial spaces degree by degree. Similarly, we have the analogue of H-bases for subalgebras, termed as SH-bases. In this paper, we present an analogue of H-bases for finitely generated ideals in a given subalgebra of a polynomial ring, and we call them “HSG-bases.” We present their connection to the SAGBI-Gröbner basis concept, characterize HSG-basis, and show how to construct them.


---

## Body

## 1. Introduction

The concept of H-bases, introduced long ago by Macaulay [1], is based solely on homogeneous terms of a polynomial. In [2], an extension of Buchberger’s algorithm is presented to construct H-bases algorithmically. Some applications of H-bases are given in [3]; in addition, many of the problems in applications which can be solved by the Gröbner technique can also be treated successfully with H-bases. The concept of H-basis for ideals of a polynomial ring over a field K can be adopted in a natural way to K-subalgebras of a polynomial ring. In [4], SH-basis (Subalgebra Analogue to H-basis for Ideals) for the K-subalgebra of Kx1,…,xn is defined. The properties of SH-bases are typically similar to H-basis results [3]. Like H-bases, the concept of SH-basis is also tied to homogeneous polynomials. In this paper, we will present an analogue to H-bases for ideals in a given subalgebra of a polynomial ring, and we call them “HSG-bases.”The paper is organized as follows. In Section2, we briefly describe the underlying concept of grading which leads to SAGBI-Gröbner bases and HSG-basis. Then, we give the notion of si-reduction, which is one of the key ingredients for the characterization and construction of HSG-basis. After setting up the necessary notation, we present the si-reduction algorithm (see Algorithm 1). Also, here we present some properties characterizing HSG-basis (Theorem 1). In Section 3, we present a criterion through which we can check that the given system of polynomials is an HSG-basis of the subalgebra it generates (Theorem 2), and further on the basis of this theorem, we present an algorithm for the construction of HSG-basis (Algorithm 2).Algorithm 1: Algorithm to compute si-reduction
Input: a subalgebra A, a finite subset G⊂A, and a polynomial f∈A.Output: a polynomial h such that f⟶GA,∗h.(1)
h:=f.(2)
Whileh≠0andGh=∑iaigi|MH∑iaigi=MHh≠∅; where ai∈A and gi∈G.(3)
Choose∑iaigi∈Gh.(4)
h:=h−∑iaigi and continue at 2.Algorithm 2: Algorithm for the construction of HSG basis.
Input: a subalgebra A and a finite subset G⊂A.Output: HSG-basis H for GA.(1)
H:=G, OldH:=∅.(2)
H=h1,…,hs.(3)While (H≠ OldH) do(4)
ComputeQ, an MH−generating set for syzMHH.(5)
ComputeP:=∑i=1sqihi|qii=1s∈Q.(6)
Compute redP:=finalsi-reduction viaHof every element ofP−0.(7)
OldH:=H∪redP.


## 2. HSG-Bases and SAGBI-Gröbner Bases

Here and in the following sections we consider polynomials inn variables x1,…,xn with coefficients from a field K. For short, we write(1)P≔Kx1,…,xn.IfG is a subset of subalgebra A in Kx1,…,xn, then the set(2)I≔∑g∈Ghgg|hg∈Aand only finitely manyhg≠0is the ideal of A in P generated by G and we write it shortly as GA. In this section, we want to introduce HSG-bases and discuss some of their properties. This concept is very similar to the concept of SAGBI-Gröbner bases. Therefore, we will briefly explain the underlying common structure. Let Γ denote an ordered monoid, i.e., an abelian semigroup under an operation +, equipped with a total ordering > such that, for all α,β,γ∈Γ,(3)α>β⇒α+γ>β+γ.A direct sum,(4)P=⊕γ∈ΓPγΓ,is called grading (induced by Γ) or briefly a Γ-grading if for all α,β∈Γ,(5)f∈PαΓ,g∈PβΓ⇒f⋅g∈Pα+βΓ.Since the decomposition above is a direct sum, each polynomialf≠0 has a unique representation.(6)f=∑i=1sfγi,0≠fγi∈PγiΓ.Assuming thatγ1>γ2>⋯>γs, the Γ-homogeneous term fγ1 is called the maximal part of f, denoted by MΓf:=fγ1, and f−MΓf is called the d-reductum of f. For G⊂A, MΓG:=MΓg|g∈G.There are two major examples of gradings. The first one is grading by degrees:(7)PdΓ=p∈P|pis homogeneous of degreed,∀d∈ℕ.Here,Γ=ℕ with the natural total ordering. This grading is called the H-grading because of the homogeneous polynomials. Therefore, we also write H in place of this Γ. The space of all polynomials of degree at most d can now be written as(8)Pd≔⊕k=0dPkH.The maximal part of a polynomialf≠0 is its homogeneous form of highest degree, MHf. For simplicity, let MH0:=0.Definition 1.
A subsetG=g1,…,gs⊂A (subalgebra) is called HSG-basis for the ideal IA⊂A, if for all 0≠f∈IA,(9)∃h1,…,hs∈A:f=∑i=1shigi,degf=maxi=1sdeghigiNote that this condition is not obvious,−x3y3+x4=x2x3y+x2+−xyx4+x2y2see inKx2,xy.
The representation forf in (9) is also called its HSG representation with respect to G.Note that HSG-basis for ideal in a subalgebra is also a generating set of it. To obtain more insights into HSG-bases, we will give some equivalent definitions. First, we need a more technical notion.Definition 2.
For givenf,f1,…,fm, we say that fsi−reduces to f˜ with respect to F=f1,…,fm in A if(10)f˜=f−∑i=1maifi,degf˜<degfholds with polynomials ai∈A satisfying degaifi≤degf. We write it as f⟶FAf˜. By ⟶FA,∗ we denote the transitive closure of the binary relation ⟶FA 1.The concept ofsi−reduction plays an important role in the characterization and construction of HSG-basis. For f∈A and G⊂A, the following algorithm computes h such that f⟶GA,∗h (i.e., f reduces to h completely).We note that such an elementai in the subalgebra A can easily be determined as in the case of reduction in polynomial ring. We also note that degh−∑iaigi is strictly smaller than the degh (by the choice of ∑iaigi). This shows that Algorithm 1 always terminates.Theorem 1.
LetG=g1,…,gs⊂A (subset of subalgebra A) and IA be an ideal of A. Then, the following conditions are equivalent:(1)
G is an HSG-basis for the ideal IA.(2)
MHg1,…,MHgsKMH=MHf|f∈IAKMH.(3)
For allf∈I,f⟶GA,∗0.Proof.
1⇒2. Let MHp∈MHf|f∈IA for some p∈IA. Since G is an HSG-basis, by (9), there are some h1,…,hs∈A so that p=∑i=1shigi and MHp=MH∑i=1shigi=∑i∈JMHhiMHgi∈MHg1,…,MHgs, where J=i|deghigi=degp.2⇒3. Let 0≠f∈IA. By using Algorithm 1, we get f⟶FAh1⟶FAh2…⟶FAh, where h is si−reduced any further with respect to F. MHf∈MHg1,…,MHgs implies MHf=∑i∈JMHhiMHgi; then, f⟶GAf˜=f−∑higi∈IA. If we follow the above process inductively, then f⟶GA,∗0.3⇒1. Let(11)f0⟶GAf1⟶GA…⟶GAfd=0,where MHfi−1=∑j=1sMHhijMHgj,i=1,2,…,d,degfi−1>degfi. Then,(12)f=∑j=1s∑i=1dMHhijMHgj.
Note that(13)degf=degf∘=deg∑j=1sMHh1jMHgj,and(14)deg∑j=1sMHhijMHgj>deg∑j=1sMHhi+1,jMHgj,i=1,2,…,d.
Hence,(15)degf=maxideg∑j=1sMHhijMHgj.
(11) and (15) give the HSG representation.The second major example of gradings leads to the SAGBI-Gröbner basis concept. Here,Γ=ℕn with component-wise addition equipped with a total ordering satisfying (11). In addition, γ≥0,∀γ∈Γ. For arbitrary γ=γ1,…,γn∈Γ, the space PγΓ is a vector space of dimension 1, namely,(16)PγΓ=c⋅xγ1…xγn|c∈K.The maximal partMΓf of a polynomial f is a product of a leading coefficient LCf and a leading monomial LMf, that is MΓf=LCf⋅LMf,where LCf∈K. The si-reduction f⟶GAf˜ is defined if there exists a polynomial g∈G and a∈A such that LMf=LMgLMa and then we set f˜:=f−MΓf/MΓgMΓaag. The relation ⟶GA,∗ is constructed as above.A SAGBI-Gröbner basisG (with respect to a given monomial ordering and a given ideal IA in a subalgebra A) is a set of polynomials generating IA and satisfying one of the following equivalent conditions:(i)
Everyf∈IA has a representation:(17)f=∑i=1shigi,LMf=maxi=1sLMhiLMgi,wherehi∈A and gi∈G.(ii)
MΓg|g∈G=MΓf|f∈IA.(iii)
Everyf∈IAsi-reduces to 0 with respect to G.The proof of this equivalence and many other equivalent conditions can be found in [5]. If a monomial ordering is compatible with the semiordering by degrees,(18)degxγ>degxβ⇒γ>β,γ,β∈ℕn,then any SAGBI-Gröbner representation as given in (i) is an HSG representation; in other words, a SAGBI-Gröbner basis with respect to a degree compatible ordering is an HSG-basis as well. The converse is false, as the following example shows.Example 1.
Letf1=x4+2x2y2+y4−1, f2=x2y2+y4−2, f3=2x2+y2. These polynomials belong to the subalgebra A=ℚx2,y2. Then, we can see that f1,f2, and f3 already constitute an HSG-basis for ideal IA=f1,f2,f3 in A. If we order the monomials by degree lexicographical ordering, then MHf|f∈IAℚMHA=x4,x2y2,x2ℚMHA. Every SAGBI-Gröbner basis G with respect to this ordering contains at least four elements, for instance, G=g1,g2,g2,g4 with g1=x4+2x2y2+y4−1=f1, g2=x2y2+y4−2=f2, g3=2x2+y2=f3, and g4=y4−4. Obviously, this SAGBI-Gröbner basis is an HSG-basis as well.


## 3. Construction of HSG-Bases

In this section, we present an HSG-basis criterion, through which we can construct HSG-basis. For this purpose, we fix some notations which are necessary for this construction. LetA be a K−subalgebra of Kx1,…,xn.(i)
We denoteA⊕…⊕As−times by ⊕SA.(ii)
For a subsetG⊆A, we denote MHgi|gi∈G by MHG.Definition 3.
ForK−subalgebra A of Kx1,…,xn and a subset G=g1,…,gs⊆A,(1)
syzAG=a⟶=aii=1s∈⊕SA|∑i=1saigi=0. We call an element of syzAG an A−syzygy of G.(2)
Fora⟶=aii=1s∈⊕SA, let MHa⟶ represent the vector MHaii=1s.Definition 4.
We call a subsetQ=q1⟶,q2⟶,…,qm⟶ a MH-generating set for syzMHG if MHqi⟶|1≤i≤m generates the KMHA-module syzMHG, i.e., for a⟶∈syzMHG, there are some h1,h2,…hm∈MHA such that(19)MHaii=1s=∑j=1mMHhjMHqiji=1s.In the case of SAGBI-Gröbner bases, there is an algorithm for computing SAGBI-Gröbner bases by means of syzygies (see [6]) where syzygies and their connection to SAGBI-Gröbner bases are studied in detail. The analogue for constructing HSG-bases by means of syzygies is connected to the following result [7].Theorem 2.
(HSG-basis criterion). LetG=g1,…,gs be the subset of a subalgebra A. Let Q be MH−generating set for the syzMHG. Then, G is an HSG-basis for GA if and only if for every qj⟶=qj,1,…,qj,s∈Q, we have ∑i=1sqj,igi⟶GA,∗0.Proof.
⇒: The statement is a direct result of Theorem 1.⇐: Take f∈GA. We need to show that MHf∈MHGKMHA. For this, we write f=∑i=1maigi such that p0=maxMHaigi (degree wise) is minimal among all such representations of f. We have MHf≤p0. Suppose that MHf<p0. Assume that a1g1,…,am0gm0 are contributing to p0, i.e., MHaigi=p0for all1≤i≤m0. If we set a⟶=a1,…,am0,0,…,0, we can see that MHa⟶∈syzMHG. This implies that there are b1,…,bn∈A and Q1⟶,…,Qn⟶∈Q⟶ such that MHa⟶=∑j=1nMHbjMHQj⟶. We may assume that MHbjMHqj,iMHgi=p0 for each j by homogeneity of the syzygies. Now,(20)f=∑i=1maigi−∑i=1m∑j=1nbjqj,igi+∑j=1nbj∑i=1mqj,igi=∑i=1mai−∑j=1nbjqj,igi+∑j=1nbj∑i=1mpj,igi,where ∑i=1mpj,igi is an HSG representation for ∑i=1mqj,igi since ∑i=1mqj,igi⟶G0. If we define Hj=maxMHpj,igi, then(21)Hj=MH∑qj,igi<maxMHqj,igi,for allj,because MHQj⟶∈syzMHG.
Consider the first sum of equation (20). For i≤m0, we have MHai=MH∑j=1nbjqj,i, so by the cancellation of highest terms,(22)MHai−∑j=1nbjqj,igi<MHaigi=p0.
Fori>m0,MHaigi<p0 and ∑j=1nMHbjMHqj,i=0 implies that(23)MH∑j=1nbjqj,igi<maxjMHbjqj,igi=p0.
Since(24)MHai−∑j=1nbjqj,igi≤maxMHaigi,MH∑j=1nbiqj,igi<p0∀i.
So, first sum of equation (20) is less than p0. For the second sum of equation (20), we have(25)MH∑j=1nbj∑i=1mpj,igi≤maxi,jMHbjpj,igi≤maxjMHbjHj<maxi,jMHbjqj,igi=p0.
Hence, equation (20) does provide a new representation for f such that maxMHaigi<p0, a contradiction. Therefore, MHf=p0 and MHf=∑i=1m0MHaigi∈MHG.On the basis of Theorem2, now we present an algorithm which computes HSG-basis from a given set of generators. This algorithm is not necessarily terminating but does terminate, if and only if, the considered ideal in the subalgebra has a finite HSG-basis.Now we present some examples which show the computation of HSG-basis through Algorithm2.Example 2.
Let the subalgebraA=Qx2,xy and G=x3y+x2,xy+2⊆A. Consider H=G; then, MHH=x3y,xy.First pass through the while loop:(i)
MHq1x3y+MHq2xy=0 implies Q=−1,x2. Then, −1x3y+x2+x2xy+2=−x3y−x2+x3y+2x2=x2 gives P=x2.(ii)
Asx2 is si-reduced with respect to H, redP=x2.(iii)
Define: OldH=H∪x2.AsH≠ OldH, we repeat the whole process. Now we have MHH=x3y,xy,x2.Second pass through the while loop:(i)
MHq1x3y+MHq2xy+MHq3x2=0 implies −1x3y+0xy+xyx2=0. Therefore, Q=−1,x2,0,−1,0,xy. Then, −1x3y+x2+0xy+2+xyx2=−x3y−x2+0+x3y=−x2 gives P=x2,−x2.(ii)
Now, redP=∅.
Since OldH=H, we stop here. The HSG-basis for GA is x3y+x2,xy+2,x2.Example 3.
LetA=Qx2,xy and G=x3y+x2y2+x2,xy+2⊆A. Consider H=G; then, MHH=x3y+x2y2,xy.First pass through the while loop:(i)
MHq1x3y+x2y2+MHq2xy=0 gives Q=−1,x2+xy. Then, from −1x3y+x2y2+x2+x2+xyxy+2=−x3y−x2y2−x2+x3y+x2y2+2x2+2xy=x2+2xy,(ii)
redP=x2−4.(iii)
Define: OldH=H∪x2−4.
AsH≠ OldH, we repeat the whole process. Now we have MHH=x3y+x2y2,xy,x2.Second pass through the while loop:(i)
From the equationMHq1x3y+x2y2+MHq2xy+MHq3x2=0, we have Q=−1,xy,xy,−1,x2+xy,0. We can compute P from −1x3y+x2y2+x2+xyxy+2+xyx2−4=−x3y−x2y2−x2+x2y2+2xy+x3y−4xy=−x2−2xy.(ii)
Now, redP=∅.
Since OldH=H, we stop here. The HSG-basis for GA is x3y+x2y2+x2,xy+2,x2−4.


## 4. Conclusion

In this paper, we presented the theory of HSG-bases, which are a good basis of an ideal in a subalgebra of a polynomial ring. We can further develop this theory for an arbitrary grading for which HSG-bases would be a special case for degree-based grading.



---

*Source: 2400073-2021-07-07.xml*