# Computing Independent Variable Sets for Polynomial Ideals

Authors: Zhuoran Yang; Chang Tan
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Computing independent variable sets for polynomial ideals plays an important role in solving high-dimensional polynomial equations. The computation of a Gröbner basis for an ideal, with respect to a block lexicographical order in classic methods, is huge, and then an improved algorithm is given. Based on the quasi-Gröbner basis of the extended ideal, a criterion of assigning independent variables is gained. According to the criteria, a maximal independent variable set for a polynomial ideal can be computed by assigning indeterminates gradually. The key point of the algorithm is to reduce dimensions so that the unit of computation is one variable instead of a set, which turns a multivariate problem into a single-variable problem and turns the computation of rational function field into that of the fundamental number field. Hence, the computation complexity is reduced. The algorithm has been analysed by an example, and the results reveal that the algorithm is correct and effective.


---

## Body

## 1. Introduction

Solving systems of algebraic equations is a main subject in mathematics. In the theory researches and practical problems of many disciplines, it is frequently related to solving high-dimensional equations, whose key point is to know the independent variables of equations. During the research on the ideal of polynomials, the Hilbert-basis theory provides researchers with the direction of computing basis of the ideal. Then, Buchberger [1] and Möller and Mora [2] presented Gröbner basis with good properties.As noticed in [3], the method of testing whether a subset of indeterminates is independent modulo an ideal aims to compute the Gröbner basis with respect to a block lexicographical order. Moreover, combining results given by Carra-Ferro [4] and Gröbner basis with the definition of strong independent modulo an ideal, it is concluded that the algorithm is correct with respect to any arbitrary admissible term order. Zhang and Feng [5] proposed a different approach to compute the independent variable sets of an ideal. The idea is to compute quasi-Gröbner basis instead of Gröbner basis. Shang et al. [6] used this method to compute independent variable sets for computing rational representation of positive-dimensional ideals. It is noticeable that all computations are in the rational function field. In particular, computations are huge when the number of variables is large, which means it is hard to realize the algorithm. Besides, Bernasconi et al. [7] and Kratzer [8] turned deciding whether variables are independent modulo an ideal to decide whether there is a nontrivial solution for homogeneous equations.Among the existing algorithms, the whole variables are considered as a unit of computation. Therefore, based on [5], we will propose a descending dimension algorithm. We choose only one variable at a time and assign it a value according to the assigning criteria, which guarantees that there is at least one variable set independent modulo, not only the assigned ideal but also the extended ideal. Then, one independent variable can be selected and added to the independent variable set. Thus, the dimension of algebraic variety will be reduced gradually. Based on this algorithm, computations in the rational function field with several variables are turned to computations with only one variable, which reflects that the algorithm is easy to realize to some extent.The rest of this paper is organized as follows. In Section2, we give some basic definitions and results. Section 3 is devoted to introducing the definition of quasi-Gröbner basis of ring. According to the definition, we propose the assignment criteria. Then, we demonstrate how to gain the maximal independent variable sets based on the criteria and prove the algorithm. In Section 4, we give an example and analyse it through the algorithm given in Section 3.


## 2. Preliminary

LetK be a field with characteristic 0, and X=x1,x2,…,xn a finite set of indeterminates. The polynomial ring in x1,x2,…,xn is denoted by KX, whose coefficients are in the field K. We call Tx1,x2,…,xn the set, including all power products of variables in X and >T, an arbitrary admissible term order on Tx1,x2,…,xn. Let f=∑αaαxα be a nonzero polynomial in KX, and then Tf=xα|aα≠0. The multidegree of f is multidegf=max>Tα∈ℤ≥0n:aα≠0, where ℤ stands for the integer set. We denote by LCf the leading coefficient of f, LMf the leading monomial of f, and LTf=LCfLMf.Definition 1.
LetI⊂Kx1,x2,…,xn be an ideal. For any set U=xi1,xi2,…,xim⊂x1,x2,…,xn, U is an independent modulo I if I∩KU=0; otherwise, U is dependent modulo I. Moreover, if U is an independent variable set modulo I and V is a dependent modulo I for any U⊊V⊆x1,x2,…,xn, then we call U a maximal independent set modulo I. Let U be the number of indeterminates in U. The dimension of I, denoted by dimI, is the maximal U, where U is an independent modulo I.
LetS be an integral ring with unit and f1,f2,…,fm be polynomials in SX, a polynomial ring in X with coefficients in S. I=f1,f2,…,fm denotes the ideal generated by polynomials f1,f2,…,fm. Similarly, we can define the independent variable set modulo I in SX.Definition 2.
LetI⊂Sx1,x2,…,xn be an ideal. For any set U=xi1,xi2,…,xim⊂x1,x2,…,xn independent modulo I, U is a maximal independent modulo I if V is a dependent modulo I for any set V, which satisfies that U⊊V⊆x1,x2,…,xn. Let U be the number of indeterminates in U. The dimension of I, denoted by dimI, is the maximal U, where U is independent mod I.
The idea of Gröbner basis of an idealI in a field plays an important role in solving many a problem of algebraic system. When it turns to focus on a polynomial ring, there is a definition called quasi-Gröbner basis, which is much the same.Lemma 1.
LetG=g1,g2,…,gm be a subset of Sx1,x2,…,xn and f a polynomial in Sx1,x2,…,xn. Then, there are s1,s2,…,sm∈ℤ≥0, q1,q2,…,qm, and r∈Sx1,x2,…,xn such that(1)∏i=1mLCgisif=∑i=1mqigi+r,where degqigi≤degf and for any u∈Tr and gi∈G, u is not the multiple of LMgi.
Based on Lemma1, we introduce a quasi-Gröbner basis of an ideal I in SX [5] and review a theorem guaranteeing its existence.Definition 3.
(see [5]). Let I be an ideal in Sx1,x2,…,xn. Suppose that G=g1,g2,…,gm⊂I satisfies that there are s1,s2,…,sm∈ℤ≥0 and q1,q2,…,qm∈Sx1,x2,…,xn such that(2)∏i=1mLCgisif=∑i=1mqigi,degqigi≤degf,we call G a quasi-Gröbner basis of I.Theorem 1.
(see [5]). Let I be an ideal in Sx1,x2,…,xn and >T an arbitrary admissible term order on T. Then, there is a finite set G⊂I, such that G is a quasi-Gröbner basis of I with respect with >T.
There is also some preparation for proving the correctness of the algorithm given in the following section. In the rest of this section, we assume thatL is the algebraic closure of K. Let Ln be the set a1,a2,…,an|∀a1,a2,…,an∈L. We consider f1,f2,…,fm∈KX and I=f1,f2,…,fm. The zero set of I in Ln, a1,a2,…,an∈Ln|∀f∈I,fa1,a2,…,an=0, is denoted by VLI.Definition 4.
LetV⊂Ln be a K-affine variety. If there are no K-affine varieties, V1 and V2, such that V=V1∪V2, then we call V an irreducible K-affine variety.Proposition 1.
(see [9]). A K-affine variety, V⊂Ln, is irreducible if and only if the vanished ideal of V, IV, is prime. In other words, for all f and g∈KX, if fg∈IV, then it is concluded that f belongs to IV or g belongs to IV.Proposition 2.
(see [9]). If a K-affine variety, V⊂Ln, can be written in the form of V=∪i=1mVi, where each variety Vi is irreducible and m is finite, then we call the form the irreducible decomposition of V.


## 3. The Algorithm of the Maximally Independent Set Modulo An Ideal

In our algorithm, computing quasi-Gröbner basis of extended ideal is inevitable. For more details, we refer the readers to [10–12].


### 3.1. The Algorithm for Computing the Quasi-Gröbner Basis

We will make some preparations correlated to the computation of a quasi-Gröbner basis. First, the definition of extended ideal and some properties are introduced.Definition 5.
LetU be the set xi1,xi2,…,xim, V the set X/U=xim+1,xim+2,…,xin, and KU the rational function field in U with coefficients in K. The ring of quotients of KX with respect to U, denoted by KUV, is the polynomial ring in V with coefficients in KU. Let I be an ideal in KX, and then we define extended ideal of I to KUV, denoted by Ie, as the ideal generated by the set I in KU. For any ideal J in KUV, contraction ideal of J to KX, denoted by Jc, is defined as Jc=J∩KX.Proposition 3.
(see [10]). Let I be an ideal in Kx1,x2,…,xn, and then the extended ideal generated by I in KUV is as follows:(3)Ie=fg|f∈I,0≠g∈Kxi1,xi2,…,xim.
The reduction of polynomials in the ring is necessary for getting a quasi-Gröbner basis.Definition 6.
LetS be an integral ring, f,g,p∈Sx1,x2,…,xn with p≠0, and P be a finite subset of SX. Then, we say that(i)
Ifg=LCpf−Coeff,tsp for some t∈Tf satisfying LMp|t and t=LMps, where Coeff,t is the coefficient of t in f, then we say that f generally reduces to g modulo p.(ii)
Iff generally reduces to g modulo p for some p∈P, then we say that f generally reduces to g modulo P .(iii)
Iff generally reduces to g modulo p for some g∈SX, then we say that f is generally a reducible modulo p.(iv)
Iff generally reduces to g modulo P for some g∈SX, then we say that f is generally a reducible modulo P.
According to the preparations above, we will show a relationship between a Gröbner basis and a quasi-Gröbner basis next.Theorem 2.
(see [5]). Let Qs be the quotient field of integral ring S and >T an arbitrary admissible term order on Tx1,x2,…,xn. I is an ideal in Sx1,x2,…,xn, and it is easy to know that the extended ideal of I to QsX is Ie=1/af|f∈I,a∈S/0. For any subset G of I, G is the quasi-Gröbner basis of I, if and only if G is the Gröbner basis of Ie.
We can gain a quasi-Gröbner basis of an idealI in a polynomial ring. The details are in the following definition and theorem.Definition 7.
LetK be a field with characteristic 0, U=xi1,xi2,…,xim, and V=X/U. For any f and g∈KUV, we define the ES-polynomial of f and g as(4)ESf,g=LCgLCMLMf,LMgLMff−LCfLCMLMf,LMgLMgg,where LCf,LCg∈KU, and LMf,LMg∈TV.Theorem 3.
(see [12]). Let S be an integral ring and I an ideal of Sx1,x2,…,xn. G=g1,g2,…,gm is a basis of I, then G is a quasi-Gröbner basis of I, if and only if the remainder of ESgi,gj modulo G is 0 with respect to the reduction in Definition 6 for any i≠j,i,j=1,2,…,m.


### 3.2. Main Algorithm

We first demonstrate the correctness of the following algorithm.Theorem 4.
(see [5]). Let S be an integral ring, I an ideal in Sx1,x2,…,xn, and G quasi-Gröbner basis of I. Then, I∩S/0=∅, if and only if G∩S/0=∅.Proposition 4.
(see [10]). Let U=xi1,xi2,…,xim, V=xim+1,xim+2,…,xin=X/U, and >v an admissible term order on TV. I is an ideal in Kx1,x2,…,xn, and G⊂I is a Gröbner basis of the extension Ie of I to KUV with respect to >v. Then, we have the following:(i)
U is a maximal independent modulo I, if and only if Ie is a zero-dimensional proper ideal in KUV.(ii)
For anyg∈G, let LCg be the leading coefficient of g with respect to >v, where g is regarded as a polynomial in KUV and f=LCMLCg|g∈G. Then, the contraction ideal of Ie is Iec=I:f∞=g∈I|∃s∈N,gfs∈I, where Ie is the extended ideal of I to KUV.
The next theorem shows the correctness of our algorithm.Theorem 5.
LetI be an ideal in Kx1,x2,…,xn. U=xi1 is an independent modulo I, and V=X/U. Ie is the extended ideal of I to KUV and G is a Gröbner basis of Ie with respect to >v. Let LCg be the leading coefficient of g with respect to >v, where g is regarded as a polynomial in KUV and fxi1=LCMLCg|g∈G. Suppose that a∈K satisfies fa≠0 and I1=I|xi1=a. If U2=xi2,xi3,…,xim is independent mod I1, then U1=xi1,xi2,…,xim is an independent mod I.Proof.
We assume thatU1=xi1,xi2,…,xim is a dependent mod I, which means there is a polynomial h such that h is in I∩KU1/0. If h|xi1=a is not equal to 0, then h|xi1=a belongs to KU2/0 because h is in KU1. h belongs to I, and thus h|xi1=a is in I1, which means there is a polynomial h|xi1=a such that h|xi1=a belongs to I1∩KU2/0. This contradicts the fact that U2 is an independent modulo I1; otherwise, h|xi1=a equals 0. Then, it is concluded that xi1−a|h, which means that there exists a polynomial u∈SU1 such that h=uxi1−aq,q∈Z≥1, and u|xi1=a≠0. Let Iec be the contraction ideal of Ie to Kx1,x2,…,xn. By Proposition 3, u=h/xi1−aq∈Ie. Moreover, u∈Kx1,x2,…,xn, and hence, u∈Iec. Based on Proposition 4, Iec=I:f∞=w∈I|∃s∈N,wfs∈I, and then ∃s0∈N such that ufs0∈I. As a result of the fact that f is in KU, ufs0 belongs to KU1. Also, under the given condition that fa≠0, ufs0|xi1=a≠0. It follows that ufs0|xi1=a is in I1∩KU2/0, which contradicts that U2 is an independent modulo I1. In conclusion, xi1,xi2,…,xim is the independent modulo I.Remark 1.
According to Theorem 5, suppose thatxi1 is an independent modulo I and a∈K satisfies fa≠0. If U2=xi2,xi3,…,xim is an independent mod I1, then U1=xi1,xi2,…,xim is the independent mod I. Conversely, if fa=0, the conclusion of Theorem 5 may not be true. For instance, I=xy−x,xz⊂ℂx,y,z, where ℂ is the complex field. It is concluded that x is the independent modulo I and fx=x, correspondingly. If x=0, letI1=I|x=0=0. Obviously, y is an independent mod I1, but x,y is a dependent mod I. If xi1 is an independent mod I, let V1=X/xi1. Then, consider I as the ideal in Kxi1V1, and compute G1, the quasi-Gröbner basis of I with respect to an admissible term order>v1 (based on Theorem 3, we can compute the quasi-Gröbner basis of I with respect to the admissible term order >v1). Let f1xi1=LCMLCg|g∈G1. Next, choose a1∈K such that f1a1≠0, and then I1=I|xi1=a1. For simplicity, we call the value polynomial of I with respect to xi1. Repeat these steps gradually until xim is the independent modulo Im−1m≥2 and Im−1 is a zero-dimensional ideal, which means xi1,xi2,…,xim is an independent modulo I. In the end, we can check whether xi1,xi2,…,xim is a maximal independent modulo I by Proposition 4. If not, specify xi1,xi2,…,xim the proper values and repeat the steps as before, a maximal independent variable set modulo I can be gained in finite steps.
The following algorithm is the main algorithm in our paper where we describe the main steps to compute maximal independent variable sets.Algorithm 1:
Input:I:=f1,f2,…,fm.(i)
j:=1,W:=∅,X0:=X,I0:=I.(ii)
Compute the dimension ofI. If it is zero, then stop; otherwise, do (iii).(iii)
Choose randomlyxij∈X/W,Uj=xij, and Vj=Xj−1/Uj. Then, consider Ij−1 as an ideal in KUjVjand compute Gj, the quasi-Gröbner basis of Ij−1 with respect to an admissible term order >vj.Next, check whether Gj∩KUj/0 is ∅. If true, it is concluded that xij is an independent modulo I, and then do (iv). Otherwise, repeat (iii) until choosing a variable xij independent modulo Ij−1.(iv)
Computefjxij=LCMLCg|g∈Gj. Choose randomly aj∈K such that fjaj≠0, and then Ij:=Ij−1|xij=aj.(v)
W:=W∪xij. If the dimension of Ij is zero, then do (vi). Otherwise, Xj:=Xj−1/xij,j:=j+1, and return to (iii).(vi)
ConsiderI as the ideal in KWX/W and compute G, the quasi-Gröbner basis of I with respect to an admissible term order >X/W. If Ie⊂KWX/W is a zero-dimensional proper ideal, the algorithm stops. In other words, W is a maximal independent modulo I. Otherwise, enter the next step.(vii)
Computefxi1,xi2,…,xij=LCMLCg|g∈G. Choose p=p1,p2,…,pj∈Kjsuch that fp1,p2,…,pj≠0, Ij:=I|xi1=p1,xi2=p2,…,xij=pj, and j:=j+1. Return to (iii).Output:W.


## 3.1. The Algorithm for Computing the Quasi-Gröbner Basis

We will make some preparations correlated to the computation of a quasi-Gröbner basis. First, the definition of extended ideal and some properties are introduced.Definition 5.
LetU be the set xi1,xi2,…,xim, V the set X/U=xim+1,xim+2,…,xin, and KU the rational function field in U with coefficients in K. The ring of quotients of KX with respect to U, denoted by KUV, is the polynomial ring in V with coefficients in KU. Let I be an ideal in KX, and then we define extended ideal of I to KUV, denoted by Ie, as the ideal generated by the set I in KU. For any ideal J in KUV, contraction ideal of J to KX, denoted by Jc, is defined as Jc=J∩KX.Proposition 3.
(see [10]). Let I be an ideal in Kx1,x2,…,xn, and then the extended ideal generated by I in KUV is as follows:(3)Ie=fg|f∈I,0≠g∈Kxi1,xi2,…,xim.
The reduction of polynomials in the ring is necessary for getting a quasi-Gröbner basis.Definition 6.
LetS be an integral ring, f,g,p∈Sx1,x2,…,xn with p≠0, and P be a finite subset of SX. Then, we say that(i)
Ifg=LCpf−Coeff,tsp for some t∈Tf satisfying LMp|t and t=LMps, where Coeff,t is the coefficient of t in f, then we say that f generally reduces to g modulo p.(ii)
Iff generally reduces to g modulo p for some p∈P, then we say that f generally reduces to g modulo P .(iii)
Iff generally reduces to g modulo p for some g∈SX, then we say that f is generally a reducible modulo p.(iv)
Iff generally reduces to g modulo P for some g∈SX, then we say that f is generally a reducible modulo P.
According to the preparations above, we will show a relationship between a Gröbner basis and a quasi-Gröbner basis next.Theorem 2.
(see [5]). Let Qs be the quotient field of integral ring S and >T an arbitrary admissible term order on Tx1,x2,…,xn. I is an ideal in Sx1,x2,…,xn, and it is easy to know that the extended ideal of I to QsX is Ie=1/af|f∈I,a∈S/0. For any subset G of I, G is the quasi-Gröbner basis of I, if and only if G is the Gröbner basis of Ie.
We can gain a quasi-Gröbner basis of an idealI in a polynomial ring. The details are in the following definition and theorem.Definition 7.
LetK be a field with characteristic 0, U=xi1,xi2,…,xim, and V=X/U. For any f and g∈KUV, we define the ES-polynomial of f and g as(4)ESf,g=LCgLCMLMf,LMgLMff−LCfLCMLMf,LMgLMgg,where LCf,LCg∈KU, and LMf,LMg∈TV.Theorem 3.
(see [12]). Let S be an integral ring and I an ideal of Sx1,x2,…,xn. G=g1,g2,…,gm is a basis of I, then G is a quasi-Gröbner basis of I, if and only if the remainder of ESgi,gj modulo G is 0 with respect to the reduction in Definition 6 for any i≠j,i,j=1,2,…,m.


## 3.2. Main Algorithm

We first demonstrate the correctness of the following algorithm.Theorem 4.
(see [5]). Let S be an integral ring, I an ideal in Sx1,x2,…,xn, and G quasi-Gröbner basis of I. Then, I∩S/0=∅, if and only if G∩S/0=∅.Proposition 4.
(see [10]). Let U=xi1,xi2,…,xim, V=xim+1,xim+2,…,xin=X/U, and >v an admissible term order on TV. I is an ideal in Kx1,x2,…,xn, and G⊂I is a Gröbner basis of the extension Ie of I to KUV with respect to >v. Then, we have the following:(i)
U is a maximal independent modulo I, if and only if Ie is a zero-dimensional proper ideal in KUV.(ii)
For anyg∈G, let LCg be the leading coefficient of g with respect to >v, where g is regarded as a polynomial in KUV and f=LCMLCg|g∈G. Then, the contraction ideal of Ie is Iec=I:f∞=g∈I|∃s∈N,gfs∈I, where Ie is the extended ideal of I to KUV.
The next theorem shows the correctness of our algorithm.Theorem 5.
LetI be an ideal in Kx1,x2,…,xn. U=xi1 is an independent modulo I, and V=X/U. Ie is the extended ideal of I to KUV and G is a Gröbner basis of Ie with respect to >v. Let LCg be the leading coefficient of g with respect to >v, where g is regarded as a polynomial in KUV and fxi1=LCMLCg|g∈G. Suppose that a∈K satisfies fa≠0 and I1=I|xi1=a. If U2=xi2,xi3,…,xim is independent mod I1, then U1=xi1,xi2,…,xim is an independent mod I.Proof.
We assume thatU1=xi1,xi2,…,xim is a dependent mod I, which means there is a polynomial h such that h is in I∩KU1/0. If h|xi1=a is not equal to 0, then h|xi1=a belongs to KU2/0 because h is in KU1. h belongs to I, and thus h|xi1=a is in I1, which means there is a polynomial h|xi1=a such that h|xi1=a belongs to I1∩KU2/0. This contradicts the fact that U2 is an independent modulo I1; otherwise, h|xi1=a equals 0. Then, it is concluded that xi1−a|h, which means that there exists a polynomial u∈SU1 such that h=uxi1−aq,q∈Z≥1, and u|xi1=a≠0. Let Iec be the contraction ideal of Ie to Kx1,x2,…,xn. By Proposition 3, u=h/xi1−aq∈Ie. Moreover, u∈Kx1,x2,…,xn, and hence, u∈Iec. Based on Proposition 4, Iec=I:f∞=w∈I|∃s∈N,wfs∈I, and then ∃s0∈N such that ufs0∈I. As a result of the fact that f is in KU, ufs0 belongs to KU1. Also, under the given condition that fa≠0, ufs0|xi1=a≠0. It follows that ufs0|xi1=a is in I1∩KU2/0, which contradicts that U2 is an independent modulo I1. In conclusion, xi1,xi2,…,xim is the independent modulo I.Remark 1.
According to Theorem 5, suppose thatxi1 is an independent modulo I and a∈K satisfies fa≠0. If U2=xi2,xi3,…,xim is an independent mod I1, then U1=xi1,xi2,…,xim is the independent mod I. Conversely, if fa=0, the conclusion of Theorem 5 may not be true. For instance, I=xy−x,xz⊂ℂx,y,z, where ℂ is the complex field. It is concluded that x is the independent modulo I and fx=x, correspondingly. If x=0, letI1=I|x=0=0. Obviously, y is an independent mod I1, but x,y is a dependent mod I. If xi1 is an independent mod I, let V1=X/xi1. Then, consider I as the ideal in Kxi1V1, and compute G1, the quasi-Gröbner basis of I with respect to an admissible term order>v1 (based on Theorem 3, we can compute the quasi-Gröbner basis of I with respect to the admissible term order >v1). Let f1xi1=LCMLCg|g∈G1. Next, choose a1∈K such that f1a1≠0, and then I1=I|xi1=a1. For simplicity, we call the value polynomial of I with respect to xi1. Repeat these steps gradually until xim is the independent modulo Im−1m≥2 and Im−1 is a zero-dimensional ideal, which means xi1,xi2,…,xim is an independent modulo I. In the end, we can check whether xi1,xi2,…,xim is a maximal independent modulo I by Proposition 4. If not, specify xi1,xi2,…,xim the proper values and repeat the steps as before, a maximal independent variable set modulo I can be gained in finite steps.
The following algorithm is the main algorithm in our paper where we describe the main steps to compute maximal independent variable sets.Algorithm 1:
Input:I:=f1,f2,…,fm.(i)
j:=1,W:=∅,X0:=X,I0:=I.(ii)
Compute the dimension ofI. If it is zero, then stop; otherwise, do (iii).(iii)
Choose randomlyxij∈X/W,Uj=xij, and Vj=Xj−1/Uj. Then, consider Ij−1 as an ideal in KUjVjand compute Gj, the quasi-Gröbner basis of Ij−1 with respect to an admissible term order >vj.Next, check whether Gj∩KUj/0 is ∅. If true, it is concluded that xij is an independent modulo I, and then do (iv). Otherwise, repeat (iii) until choosing a variable xij independent modulo Ij−1.(iv)
Computefjxij=LCMLCg|g∈Gj. Choose randomly aj∈K such that fjaj≠0, and then Ij:=Ij−1|xij=aj.(v)
W:=W∪xij. If the dimension of Ij is zero, then do (vi). Otherwise, Xj:=Xj−1/xij,j:=j+1, and return to (iii).(vi)
ConsiderI as the ideal in KWX/W and compute G, the quasi-Gröbner basis of I with respect to an admissible term order >X/W. If Ie⊂KWX/W is a zero-dimensional proper ideal, the algorithm stops. In other words, W is a maximal independent modulo I. Otherwise, enter the next step.(vii)
Computefxi1,xi2,…,xij=LCMLCg|g∈G. Choose p=p1,p2,…,pj∈Kjsuch that fp1,p2,…,pj≠0, Ij:=I|xi1=p1,xi2=p2,…,xij=pj, and j:=j+1. Return to (iii).Output:W.


## 4. Experiment

### 4.1. Example

Example 1.
Considering the system in the complex fieldℂ,(5)f1=z3−z2y+xy−xz+y−z=0,f2=w2−y2+1=0.
LetI=f1,f2=z3−z2y+xy−xz+y−z,w2−y2+1.Show a maximal independent variable set modulo I.
The detailed steps according to our algorithm to solve this problem are as follows:(i)
LetG=f1,f2. Firstly, choose variable z. Then, consider I as the ideal in Czw,x,y, and compute the quasi-Gröbner basis of I with respect to graded reverse lexicographic order, an admissible term order on Tw,x,y. The result is G=f1,f2. G∩Cz/0=∅. Therefore, z is an independent mod I.(ii)
Compute the value polynomial ofI with respect to variable z. The result is hz=LCM1,1=1. Because h0=1≠0, let z=0. Then, I turns to I1=xy+y,w2−y2+1. The dimension of I1 is not 0, and hence choose one variable again.(iii)
Firstly, choose variablex. Then, consider I1 as the ideal in Cxw,y, and compute the quasi-Gröbner basis of I1 with respect to graded reverse lexicographic order, an admissible term order on Tw,y. The result is G′=x+1y,w2−y2+1. G′∩Cx/0=∅, and thus x is an independent mod I1.(iv)
Compute the value polynomial ofI1 with respect to variable x, and the value polynomial is h˜x=LCMx+1,1=x+1. Choose x=1 because h˜1=2≠0. Then, I1 turns to I2=f1′,f2′=2y,w2−y2+1. Also, the dimension of I2 is 0.(v)
ConsiderI as the ideal in Cz,xw,y and compute the quasi-Gröbner basis of I with respect to graded reverse lexicographic order, an admissible term order on Tw,y. The result is G″=1+x−z2y+z3−xz−z,w2−y2+1. The dimension of Ie is 0, and hence a maximal independent set mod I is x,z.
Regarding Algorithm 1, there is one thing to notice that is described as follows.Remark 2.
By Algorithm 1, one maximal independent variable set moduloI can be computed. If the ideal I is prime, which means the variety VLI is irreducible; the rest of maximal independent variable sets can be obtained by exchanging the order of variables selected in each step. Otherwise, in the case that I is not a prime ideal, we can only get all the maximal independent variable sets for one irreducible component of VLI by Algorithm 1. For example, assume that I=xy−x,xz⊂ℂx,y,z. The sets x and y,z are all the maximal independent variable sets modulo I. According to Algorithm 1, if the variable x that is an independent modulo I is selected firstly, it is concluded that f1x=x. Let x=1, then the ideal I1=I|x=1=y−1,z⊂ℂy,z is zero-dimensional. Thus, the set x is a maximal independent modulo I. Moreover, in order to get another maximal independent set y,z, two methods can be considered. One way is exchanging the order of variables selected in each step as before. For instance, choose the variable y, which is an independent modulo I, firstly. Compute the value polynomial of I with respect to variable y. The result is f1y=y−1. Set y=0, then I1=I|y=0=−x,xz⊂ℂx,z. Next, we choose the variable z that is an independent modulo I1. The value polynomial f2z of I1 with respect to z is z. Let z=1, then I2=I1|z=1=−x,x, which is zero-dimensional in ℂx. Thus, the maximal independent variable set y,z is obtained. Another way is continuing the algorithm for the new ideal I′=xy−x,xz,f1x⊂ℂx,y,z. We can also obtain the maximal independent set y,z.
In each step of Algorithm 1, the variablexij selected randomly needs to be assigned aj∈K such that fjaj≠0. The values of aj satisfying fjaj=0 are finite in K, so the “correct value” for aj can be obtained in finite steps. For example, suppose that the degree of the polynomial fj is d, then there is at least one value in the set 0,1,2,…,d, which satisfies fjaj≠0 . Therefore, Algorithm 1 is terminated in finite steps.


### 4.2. Algorithm Analysis

In the existing algorithms of computing the independent variable sets of an ideal, all variables are regarded as a unit, and computations are all in the rational function field, which might lead to high complexity. Compared with those algorithms, the algorithm given in this paper chooses one variable once, and thus it turns a multivariate problem into a single-variable problem. Moreover, the algorithm reduces the number of variables by assigning them some values, which avoids the redundancy of computation and effectively reduces the complexity of the algorithm to some extent.


## 4.1. Example

Example 1.
Considering the system in the complex fieldℂ,(5)f1=z3−z2y+xy−xz+y−z=0,f2=w2−y2+1=0.
LetI=f1,f2=z3−z2y+xy−xz+y−z,w2−y2+1.Show a maximal independent variable set modulo I.
The detailed steps according to our algorithm to solve this problem are as follows:(i)
LetG=f1,f2. Firstly, choose variable z. Then, consider I as the ideal in Czw,x,y, and compute the quasi-Gröbner basis of I with respect to graded reverse lexicographic order, an admissible term order on Tw,x,y. The result is G=f1,f2. G∩Cz/0=∅. Therefore, z is an independent mod I.(ii)
Compute the value polynomial ofI with respect to variable z. The result is hz=LCM1,1=1. Because h0=1≠0, let z=0. Then, I turns to I1=xy+y,w2−y2+1. The dimension of I1 is not 0, and hence choose one variable again.(iii)
Firstly, choose variablex. Then, consider I1 as the ideal in Cxw,y, and compute the quasi-Gröbner basis of I1 with respect to graded reverse lexicographic order, an admissible term order on Tw,y. The result is G′=x+1y,w2−y2+1. G′∩Cx/0=∅, and thus x is an independent mod I1.(iv)
Compute the value polynomial ofI1 with respect to variable x, and the value polynomial is h˜x=LCMx+1,1=x+1. Choose x=1 because h˜1=2≠0. Then, I1 turns to I2=f1′,f2′=2y,w2−y2+1. Also, the dimension of I2 is 0.(v)
ConsiderI as the ideal in Cz,xw,y and compute the quasi-Gröbner basis of I with respect to graded reverse lexicographic order, an admissible term order on Tw,y. The result is G″=1+x−z2y+z3−xz−z,w2−y2+1. The dimension of Ie is 0, and hence a maximal independent set mod I is x,z.
Regarding Algorithm 1, there is one thing to notice that is described as follows.Remark 2.
By Algorithm 1, one maximal independent variable set moduloI can be computed. If the ideal I is prime, which means the variety VLI is irreducible; the rest of maximal independent variable sets can be obtained by exchanging the order of variables selected in each step. Otherwise, in the case that I is not a prime ideal, we can only get all the maximal independent variable sets for one irreducible component of VLI by Algorithm 1. For example, assume that I=xy−x,xz⊂ℂx,y,z. The sets x and y,z are all the maximal independent variable sets modulo I. According to Algorithm 1, if the variable x that is an independent modulo I is selected firstly, it is concluded that f1x=x. Let x=1, then the ideal I1=I|x=1=y−1,z⊂ℂy,z is zero-dimensional. Thus, the set x is a maximal independent modulo I. Moreover, in order to get another maximal independent set y,z, two methods can be considered. One way is exchanging the order of variables selected in each step as before. For instance, choose the variable y, which is an independent modulo I, firstly. Compute the value polynomial of I with respect to variable y. The result is f1y=y−1. Set y=0, then I1=I|y=0=−x,xz⊂ℂx,z. Next, we choose the variable z that is an independent modulo I1. The value polynomial f2z of I1 with respect to z is z. Let z=1, then I2=I1|z=1=−x,x, which is zero-dimensional in ℂx. Thus, the maximal independent variable set y,z is obtained. Another way is continuing the algorithm for the new ideal I′=xy−x,xz,f1x⊂ℂx,y,z. We can also obtain the maximal independent set y,z.
In each step of Algorithm 1, the variablexij selected randomly needs to be assigned aj∈K such that fjaj≠0. The values of aj satisfying fjaj=0 are finite in K, so the “correct value” for aj can be obtained in finite steps. For example, suppose that the degree of the polynomial fj is d, then there is at least one value in the set 0,1,2,…,d, which satisfies fjaj≠0 . Therefore, Algorithm 1 is terminated in finite steps.


## 4.2. Algorithm Analysis

In the existing algorithms of computing the independent variable sets of an ideal, all variables are regarded as a unit, and computations are all in the rational function field, which might lead to high complexity. Compared with those algorithms, the algorithm given in this paper chooses one variable once, and thus it turns a multivariate problem into a single-variable problem. Moreover, the algorithm reduces the number of variables by assigning them some values, which avoids the redundancy of computation and effectively reduces the complexity of the algorithm to some extent.


## 5. Conclusions

This paper gives an improved algorithm for computing the maximally independent variable set modulo an ideal. An assignment criterion is proposed, by which the problem of extended ideals is converted into that of assignment ideals gradually. In other words, the computations in rational function field are turned to computations in the fundamental number field. We reduce the dimension of ideal by assigning variables and prefer to choose one variable each time, avoiding increasing the number of considered variables, which realizes the change from a multivariable problem to a single-variable problem. This is the mainly improved aspect with respect to classical algorithms, by which we could reduce the computation complexity to some extent. Although the computations of our algorithm will be smaller than some of the classical algorithms, it is not the perfect one. We compute quasi-Gröbner basis byES-polynomial in ring whose computations are still large. Therefore, computing quasi-Gröbner basis in ring can be improved.



---

*Source: 7049980-2022-09-19.xml*