Polynomial Gcd Computations over Towers of Algebraic Extensions

Marc Moreno Maza and Renaud Rioboo

LITP, Institut Blaise Pascal, Boite 168 Université Pierre et Marie Curie 4, Place Jussieu 75252 Paris Cedex 05

                 e-mail : m3@posso.ibp.fr, rr@posso.ibp.fr

Abstract. Some methods for polynomial system solving require efficient techniques for computing univariate polynomial gcd over algebraic extensions of a field. Currently used techniques compute generic univariate polynomial gcd before specializing the result using algebraic relations in the ring of coefficients. This strategy generates very big intermediate data and fails for many problems. We present here a new approach which takes permanently into account those algebraic relations. It is based on a property of subresultant remainder sequences and leads to a great increase of the speed of computation and thus the size of accessible problems. Keywords. Polynomial gcd, subresultants, algebraic numbers, triangular sets, zero dimensional systems, AXIOM.

1 Introduction

Polynomial gcd computations appear among other problems in algebraic number manipulation and in system solving through triangular systems. This paper presents a new algorithm to compute gcds of univariate polynomial with coefficients satisfying algebraic relations. It is a generalization of the subresultants algorithm ([14]) which enables machine resolution of problems that could not be solved with classical techniques. One of the main reasons is roughly the following. When we compute generic univariate polynomial gcd (using the subresultants algorithm) before specializing the result using algebraic relations in the ring of coefficients, we deal with univariate polynomials whose coefficients are multivariate polynomials. Thus, when applying the subresultants algorithm, pseudo-divisions increase dramatically the size of the coefficients of the intermediate polynomials and exact quotients are expensive. Our idea is to keep the leading coefficients of the intermediate polynomials in the base field. So we limit the swell of their coefficients and make easy the exact quotients which appear in the subresultants algorithm. To do so, we need to test the invertibility of the leading coefficients. This leads us to use our algorithm recursively, applying a D5-like process ([4, 5]). Now, let us introduce the problem more formally. We will state it completely in section 2.

Let R be an integral domain (a commutative ring with unit element and no zero-divisors), K its fraction field and K[X_{1}] the ring of univariate polynomials with coefficients in K. Let p_{1} ∈ K[X_{1}] be a square-free polynomial of positive degree and A_{1} be K[X_{1}]/⟨p_{1}⟩. How to test if q ∈ A_{1} is invertible ? This can be done by interpreting q as an element of K[X_{1}] and by computing the gcd g of q and p_{1} in K[X_{1}]. This yields to a factorization p_{1} = fg together with a decomposition of K[X_{1}]/⟨p_{1}⟩ into a product K[X_{1}]/⟨f⟩ and K[X_{1}]/⟨g⟩. In the first component q is invertible and is zero in the second. Thus, with no necessity for p_{1} to be irreducible, we have answered the question. This remark of D. Lazard is the basis of the D5 system ([4, 5]) for algebraic number computations.

We see that the question of invertibility in K[X_{1}]/⟨p_{1}⟩ led us to the question of gcd in K[X_{1}] together with a discussion process. This is a fundamental problem (over more general rings) in many classes of methods for algebraic solving ([9, 11, 12]). This problem is solved using the subresultant specialization property ([14]) by an algorithm described in [11]. We will briefly recall it here in the next section. However, a first implementation of the lextriangular algorithm of D. Lazard ([12]) using these techniques induced a 400 megabyte memory saturation for certain problems. This motivated us to develop better gcd algorithms. In section 3 we give definitions for the notions of polynomial gcd and discussion (we will use the term of splits) in our context. Then, we give a property of the subresultant remainder sequences algorithm which avoids the swell of memory appearing in the current techniques. In section 4 we revisit the problem of finding gcd described in section 2 in light of the previous remarks. We give explicit and complete algorithms to answer this problem. These algorithms are our AXIOM programs ([7]) up to some syntax details. So we hope that they could be easily adapted in other programming languages. We then show how this approach enables to have an efficient implementation for the lextriangular algorithm. In particular it allows a completely automatic solution for the cyclic-7 system ([6]) with results as in [1].

2 Background

Let us assume that we have introduced non-constant polynomials p_{1}, …, p_{n} and rings A_{1}, …, A_{n} such that p_{i} ∈ A_{i−1}[X_{i}] with leading coefficient in A_{0} = K, the rings A_{i} being recursively defined as the quotient ring A_{i} = A_{i−1}[X_{i}]/⟨p_{i}⟩. Though the A_{i} are not necessarily fields (they may have zero-divisors) we will call each one an algebraic tower of simple extensions of K. Since A_{i} is a finite dimensional K-algebra, an element of A_{i} is either a zero-divisor either invertible. Let us write P_{i} = K[X_{1}, …, X_{i}] for 1 ≤ i ≤ n+1 and P_{0} = K. For 1 ≤ i ≤ n we consider H_{i} the surjective canonical homomorphism from A_{i−1}[X_{i}] to A_{i} and F_{i} the surjective homomorphism from P_{i+1} to A_{i}[X_{i+1}] defined by

(i) F_{i}(X_{i+1}) = X_{i+1}

(ii) (∀p ∈ P_{i}) F_{i}(p) = \{ \begin{matrix}H_{1}(p) & if i = 1 \\ H_{i}(F_{i−1}(p)) & if i > 1 \end{matrix}

Let p̂_{1}, …, p̂_{n} be polynomials of P_{n} representing the p_{i}, that is such that p̂_{i} ∈ P_{i}\P_{i−1} and F_{i}(p̂_{i}) = p_{i} (we can assume that the leading coefficient of p̂_{i}, viewed as a polynomial in X_{i}, lies in K). Let I be the ideal generated by p̂_{1}, …, p̂_{n} in P_{n}, the ring P_{n}/I is isomorphic to A_{n}.

Let a and b in A_{n}[X_{n+1}] which have a gcd, let â and b̂ be representing a and b in P_{n}[X_{n+1}] (i.e. F_{n}(â) = a and F_{n}(b̂) = b). The classical method to compute such a gcd is to first compute a subresultant remainder sequence (r̂_{0}, r̂_{1}, …, r̂_{m}, r̂_{m+1}) of â and b̂ in P_{n}[X_{n+1}] and to search for possible gcds among the r̂_{i}. Let j be the biggest integer such that F_{n}(ĉ_{j}) ≠ 0, where ĉ_{j} is the leading coefficient of r̂_{j}. We write r_{j} = F_{n}(r̂_{j}) (using the specialization property of subresultants we know that r_{k} = 0 for k > j).

We then determine if F_{n}(ĉ_{j}) is invertible in A_{n}, if ĉ_{j} ∈ K this is the case and r_{j} is a gcd for a and b. Otherwise there exists an l such that ĉ_{j} ∈ P_{l} \ P_{l−1}. We compute a gcd of F_{l−1}(ĉ_{j}) and p_{l} in A_{l−1}[X_{l}] by recursively calling the method. If this gcd p′_{l} is of degree 0 in X_{l} we know that F_{n}(ĉ_{j}) is invertible in A_{n} and r_{j} is a gcd of a and b. Otherwise we have a factorization p_{l} = p′_{l}p′′_{l} in A_{l−1}[X_{l}], we let p′_{l} and p′′_{l} be such that p′_{l} = F_{l−1}(p′_{l}) and p′′_{l} = F_{l−1}(p′′_{l}) and we consider the ideals I′ and I′′ of P_{n} obtained from I by respectively substituting p′_{l} and p′′_{l} for p̂_{l}.

As we did for A_{n}, we can define the sequences A′_{l}, …, A′_{n} and A′′_{l}, …, A′′_{n} together with the surjective homomorphisms F′_{n} and F′′_{n} that will respectively enable to identify A′_{n} with P_{n}/I′ and A′′_{n} with P_{n}/I′′. In the tower P_{n}/I′′, F′′_{n}(ĉ_{j}) is invertible and F′′_{n}(r̂_{j}) is a gcd of F′′_{n}(â) and F′′_{n}(b̂). On the contrary in P_{n}/I′ we have F′′_{n}(r̂_{j}) = 0, and the gcd has to be found among the (r̂_{0}, r̂_{1}, …, r̂_{j−1}) searching again for the last with a non failing leading coefficient.

Despite the problem with the technical management of the discussion and of the recursion a new problem appears which is the prohibitive size of the r̂_{j}. Leading to the idea to replace computations in P_{n} by computations in A_{n}. If the ideal I is radical, the ring A_{n} is a product of fields, we were able to lift partial results (propositions 3 and 7).

3 Preliminaries

Notations 1 Let A be a ring (all rings considered here will be commutative with unit element) and E ⊆ A. We denote by IdA(E) the ideal of A generated by the elements of E, A/E the quotient ring A/IdA(E) and \overline{a}^{E} the residue class of an element a of A in A/E. If E is empty we state A/E = A. If E = {a_{1}, …, a_{n}} we will denote by ⟨a_{1}, …, a_{n}⟩_{A} (or simply ⟨a_{1}, …, a_{n}⟩) the ideal IdA(E). We will denote by nz(A) the multiplicatively closed subset of nonzero-divisors of A (this contains the group of invertible elements of A) and by q(A) the ring of fractions with numerators in A and denominators in nz(A). For a ∈ A and b ∈ nz(A), if there exists an element (necessarily unique) c such that a = bc we will denote it by a exquo b. Let p, q ∈ A[X] with p ≠ 0, we write mcoeff(p) for the coefficient of its highest degree monomial, and deg(p) this degree. We will say that p is quasi-monic if mcoeff(p) ∈ nz(A). When deg(p) > 0, we denote by prem(q, p) the pseudo-remainder of q by p.

For a module M over A and a multiplicatively closed subset S of nz(A), we denote by S^{−1}M the A-module of fractions with numerator in M and denominator in S. Every element l of S^{−1}M can be (non uniquely) decomposed into the form am/s where a ∈ A, m ∈ M and s ∈ S. We write numPart(l) = a, polPart(l) = m, numer(l) = am and denom(l) = s. If M is a polynomial ring over an integral domain, then two different values of polPart(l) generate the same ideal in the polynomial ring with coefficients over the fraction field of A. Furthermore, if A is factorial and if S is nz(A) then a, m and s can be uniquely chosen. Finally if A is a polynomial ring with coefficients over a field K and let L be a field containing K, for an ideal I of A, we will denote by V_{L}(I) (or simply V(I)) the affine variety of L^{n} associated to I.

3.1 Univariate Polynomial Gcds

Definition 1 Let A be a ring and p_{1}, p_{2}, g in A[X]. We say that g is a gcd of p_{1} and p_{2} if we have :

⟨p_{1}, p_{2}⟩q(A)[X] = ⟨g⟩q(A)[X]

Remark 1 If A is a field then we recover the usual gcd notion in A[X]. If A is factorial, g is a (usual) gcd if and only if g is a (definition 1) gcd and a divisor of both p_{1} and p_{2} in A[X]. If q(A)[X] is not principal, p_{1} and p_{2} do not necessarily have a definition 1gcd. The choice of this definition is to generalize usual gcd algorithms which all give a Bézout relation together with a pseudodivisor. Furthermore, the propositions 2 and 3 will justify this choice.

Remark 2 If p_{1} and p_{2} have two quasi-monic gcds g and g′ then there exists e, e′ ∈ nz(A) such that e g = e′ g′. In practice we will look for quasi-monic gcds as we will do when A is an algebraic tower of simple extensions of a field K. To do so, we will use the notions of ideal split and quasi-inverse, together with a generalization of the subresultant remainder sequences algorithm that we present now.

Definition 2 Let A be an integral domain, f an application from nz(A) into nz(A) and p_{1}, p_{2} two polynomials of A[X]. We consider the algorithm NewSub-ResGcd defined by

NewSubResGcd(p_{1},p_{2}, f:(nz(A) ↦ nz(A)) ) == if deg(p_{2}) > deg(p_{1}) then (p_{1},p_{2}) := (p_{2},p_{1}) δ := deg(p_{1}) - deg(p_{2}) ψ′ : A := -1 ; β′ :A := −1^{δ+1}

p_{2} := f(mcoeff(p_{2}))*p_{2}

α′ :A := mcoeff(p_{2})

while (deg(p_{2}) > 0) repeat p_{3} := prem(p_{1},p_{2}) exquo β′

p_{3} := f(mcoeff(p_{3}))*p_{3}

if δ > 0 then

ψ′ := (−α′)^{δ} exquo ψ′^{δ−1}

(p_{1} , p_{2}) := (p_{2} , p_{3}) if (deg(p_{2}) > 0) then

δ := deg(p_{1}) - deg (p_{2})
β′ := -α′ ψ′^{δ}
α′ := mcoeff(p_{2})

if p_{2} = 0 then return p_{1} else return p_{2}

Remark 3 The only difference with the original subresultant remainder sequences algorithm is that at each step we added a multiplication of the polynomial p_{i} by a constant (which is chosen by the function f). If f(x) = 1, we exactly have the original algorithm. Moreover if A is a field and if f(x) = 1/x we have the monic euclidean algorithm (where the polynomials are kept monic during computations).

Theorem 1 Let A be an integral domain. For every function f : nz(A) → nz(A), the NewSubResGcd terminates and computes a gcd as in definition 1.

Proof. ⊳ Next proposition will show that the algorithm is done in A[X], meaning that all divisions are exact divisions. It is clear that the algorithm terminates. It computes a gcd (as in definition 1) since at each step the polynomials p_{1} and p_{2} on one hand and the polynomials p_{2} and p_{3} on the other generate the same ideal in q(A)[X]. Moreover, if the last computed p_{2} is null, p_{1} generates this ideal, else this p_{2} does. ⊲

Proposition 1 Let F′_{k}, α′_{k}, β′_{k} and ψ′_{k} be the terms computed by NewSub-ResGcd and defined for k ≥ 3 as follow F′_{1} = p_{1}, λ_{2} = f(mcoeff(p_{2})), F′_{2} = λ_{2}p_{2}, α′_{2} = mcoeff(F′_{2}), δ_{k−2} = deg(F′_{k−2}) − deg(F′_{k−1}), ψ′_{3} = −1, β′_{3} = (−1)^{δ_{1}+1}, λ_{k} = f(mcoeff(prem(F′_{k−2}, F′_{k−1}))), λ_{k}prem(F′_{k−2}, F′_{k−1}) = β′_{k}F′_{k},

ψ′_{k+1} = \frac{(−α′_{k−1})^{δ_{k−2}}}{ψ′_{k}^{δ_{k−2}−1}} , β′_{k+1} = −α′_{k−1}ψ′_{k+1}^{δ_{k−1}}, and α′_{k} = mcoeff(F′_{k}). Then,

all the F′_{k} remain in A[X] and all the ψ′_{k} remain in A.

Proof.⊳ Let F_{1}, F_{2}, …, F_{k} be the polynomials computed by the original subresultant algorithm, α_{k} the leading coefficient of F_{k}; the β_{k} and ψ_{k} are given by

β_{3} = (−1)^{δ_{1}+1} and β_{k+1} = −α_{k−1}ψ_{k+1}^{δ_{k−1}} with ψ_{3} = −1 and ψ_{k+1} = \frac{(−α_{k−1})^{δ_{k−2}}}{ψ_{k}^{δ_{k−2}−1}} .

The β′_{k} and ψ′_{k} verify the same recurrence relation where α′_{k} (the leading coefficient of F′_{k}) replaces α_{k}. Let us first remark that F_{k} and F′_{k} are associated when they are interpreted as polynomials of q(A)[X]. Let us examine the beginning of the algorithm; we have F′_{2} = λ_{2}F_{2}, α′_{2} = λ_{2}α_{2}, ψ′_{3} = ψ_{3}, β′_{3} = β_{3}. We can write prem(F′_{1}, F′_{2}) = prem(F_{1}, λ_{2}F_{2}) = λ_{2}^{δ_{1}+1}prem(F_{1}, F_{2}) and thus:

F′_{3} = λ_{3}λ_{2}^{δ_{1}+1}F_{3}

since β′_{3} = β_{3}. We now consider the terms generally, putting: F′_{i} = μ_{i}F_{i} and writing relations in the fraction field of A we have:

λ_{i+2}prem(F′_{i}, F′_{i+1}) = β′_{i+2}F′_{i+2}
= β′_{i+2}μ_{i+2}F_{i+2}
= λ_{i+2}prem(μ_{i}F_{i}, μ_{i+1}F_{i+1})
= λ_{i+2}μ_{i}μ_{i+1}^{δ_{i}+1}β_{i+2}F_{i+2}

And thus β′_{i+2}μ_{i+2} = λ_{i+2}μ_{i}μ_{i+1}^{δ_{i}+1}β_{i+2} and, replacing the β by the ψ and since α′_{i} = μ_{i}α_{i}, we see that:

μ_{i+2}ψ′_{i+2}^{δ_{i}} = λ_{i+2}μ_{i+1}^{δ_{i}+1}ψ_{i+2}^{δ_{i}}  (1)

Meaning:

\frac{μ_{i+2}}{μ_{i+1}} = λ_{i+2}[\frac{μ_{i+1}ψ_{i+2}}{ψ′_{i+2}} ]^{δ_{i}}.  (2)

On another hand, if we induce recurrence relations on the ψ_{i}, we have:

\frac{μ_{i+1}ψ_{i+2}}{ψ′_{i+2}} = μ_{i+1}[\frac{α_{i}}{α′_{i}} ]^{δ_{i−1}}[\frac{ψ′_{i+1}}{ψ_{i+1}} ]^{δ_{i−1}−1}

= [\frac{ψ′_{i+1}}{ψ_{i+1}} ]^{δ_{i−1}−1} \frac{μ_{i+1}}{μ_{i}^{δ_{i−1}}}  (3)

but stating i → i−1 in (2) we find [\frac{ψ_{i+1}}{ψ′_{i+1}} ]^{δ_{i−1}} = \frac{λ_{i+1}μ_{i}^{δ_{i−1}+1}}{μ_{i+1}} which we substitute in (3) to obtain:

\frac{μ_{i+1}ψ_{i+2}}{ψ′_{i+2}} = \frac{λ_{i+1}μ_{i}^{δ_{i−1}+1}}{μ_{i+1}} μ_{i+1}[\frac{ψ_{i+1}}{μ_{i}ψ′_{i+1}} ]^{δ_{i−1}} = λ_{i+1} \frac{μ_{i}ψ_{i+1}}{ψ′_{i+1}}

and stating u_{i} = \frac{μ_{i}ψ_{i+1}}{ψ′_{i+1}} we have u_{i} = ∏_{j=2}^{j=i} λ_{j} since μ_{2} = u_{2} = λ_{2}. To show that computations remain in A it suffices to find an entire value for μ_{i}. We substitute the value of u_{i} in (2), obtaining:

\frac{μ_{i+2}}{μ_{i+1}} = λ_{i+2}u_{i+1}^{δ_{i}}  (4)

and thus μ_{i} remain in A and is divisible by u_{i}. It follows that ψ′_{i} is also in A (since ψ_{i} ∈ A). ⊲

Remark 4 We will adapt this algorithm using a D5-like process to the case where A is an algebraic tower of simple extensions and where we can no more assume that intermediate rings remain integral. To do so, we introduce the notions of quasi-inverse and split of an ideal that we present now.

3.2 Quasi-inverse

Definition 3 Let R be an integral domain and A an R-torsion-free ring, i.e. a ring containing A such that nz(R) ⊆ nz(A).. We say that a couple (y, r) ∈ A × R is an R-quasi-inverse (or simply quasi-inverse) if we have both

(i) xy = r (ii) x ≠ 0 ⟹ y ≠ 0

Remark 5 Let x ∈ A and (y, r) an R-quasi-inverse of x, we have

x ∉ nz(A) ⟺ r = 0.

If r is null, x is a zero-divisor in A. Conversely, let z ∈ A, z ≠ 0 be such that zx = 0, we have xyz = zr = 0. Since A is R-torsion-free, if r ≠ 0 then z = 0. A contradiction.

Remark 6 It follows that if x ∈ nz(A) then \frac{y}{r} is the inverse of x in q(A). If x ∉ nz(A) a quasi-inverse of x is every couple (y, 0), where xy = 0.

In the case of an algebraic tower of simple extensions, we will show how the computation of a quasi-inverse and that of a gcd resolve mutually. In section 4 we will return to the problem exposed in section 2. We will apply the NewSubResGcd algorithm where A is an algebraic tower of simple extensions using a D5-like process. To avoid fractions we will work with multivariate polynomials with coefficients in the integral domain R instead of its fraction field K. Thus, the parameter f (of the algorithm NewSubResGcd) applied to the leading coefficient c of an intermediate polynomial, if c is invertible, will return a quasi-inverse of c instead of an inverse. To compute f(c) we will use an extended version of the NewSubResGcd algorithm. Finally the leading coefficient of the intermediate polynomials i.e. the α′_{k}, and the β′_{k} and ψ′_{k} will remain in R. To understand better the efficiency of that choice, it may be interesting to have an interpretation of our method using determinantal polynomials. We leave it for a future paper.

3.3 Split of an Ideal

Definition 4 Let A_{1}, …, A_{n} be rings. The (Cartesian) product A_{1} × ⋯ × A_{n} has a ring structure, called product-ring if addition and multiplication are defined componentwise. From now on, every product of rings (and in particular of fields) will have this structure.

Proposition 2 Let A be a ring isomorphic to some product-ring A_{1} × ⋯ × A_{n}. Let p, q be in A[X]. Let h_{i} be the projection from A into A_{i} and f_{i} the homomorphism extending h_{i} to an homomorphism of A[X] into A_{i}[X] (stating f_{i}(X) = X).

If for each i the polynomials f_{i}(p) and f_{i}(q) have gcds (resp quasi-monic gcds) in A_{i}[X] then p and q have gcds (resp quasi-monic gcds) in A[X].

In particular if all the A_{i} are integral domains then every couple of polynomials (p, q) has gcds in A[X], if the A_{i} are furthermore Noetherian, then all the ideals of q(A)[X] are principal.

Definition 5 Let A be a ring and I an ideal of A. We call split every tuple S = (S_{1}, …, S_{n}) of ideals of A such that:

S_{1} ⋯ S_{n} ⊆ I ⊆ S_{1} ∩ ⋯ ∩ S_{n}

and we will write I ⟼ (S_{1}, …, S_{n}). The ideals S_{i} are called the components of the split S. The split is called proper if I is a proper subset of each of its components, it is called minimal if it is proper and if for every component S_{i} the (n − 1)-uple (S_{1}, … S_{j−1}, S_{j+1}, …, S_{n}) is not a split of I. Finally it is called unambiguous if for i ≠ j we have S_{i} + S_{j} = A.

Remark 7 Let S be a proper split of the ideal I, it has at least two components. If S is furthermore minimal then none of its components is A. Let us note that we can extract a minimal split from every split of an ideal I and that a minimal split can have components that compare with respect to inclusion. For that we can consider in K[X, Y], where K is a field, the split ⟨X^{2}, X + Y ⟩ ⟼ (⟨X, Y ⟩, ⟨X, Y ⟩). We can also verify that every minimal split of I has no multiple components if and only if I is radical.

Remark 8 Let us first note that if I ⟼ (S_{1}, S_{2}) and S_{2} ⟼ (S_{2,1}, S_{2,2}) are (unambiguous) splits then I ⟼ (S_{1}, S_{2,1}, S_{2,2}) is a (unambiguous) split. Let S = (S_{1}, …, S_{n}) be an unambiguous split of I. We have A/I ≅ A/S_{1} × ⋯ × A/S_{n}. Conversely if A/I is a product-ring (with no factor being A or the trivial ring) then I has unambiguous splits (which are proper and have no component equal to A). If A is furthermore Noetherian and if S is an unambiguous and proper split we can verify that S is minimal.

Remark 9 Let A is a polynomial ring over a field K, let L be an algebraic closure of K and let I ⟼ (S_{1}, …, S_{n}) we have:

VL(I) = ⋃_{i=1}^{n} VL(S_{i}).

Moreover if I is a zero dimensional non primary ideal then every minimal primary decomposition of I is an unambiguous split of I.

Remark 10 We can see that the ideal I is prime if and only if it has no proper splits. Let I be an ideal which is not prime and a, b ∈ A\I such that ab ∈ I. The couple S = (I + ⟨a⟩, I + ⟨b⟩) is a proper split of I that we will call fundamental. Let A be a Noetherian ring, replacing in S every component which is not a prime ideal by a fundamental split we obtain a split P = (P_{1}, …, P_{n}) where the P_{i} are prime ideals. Removing every redundant P_{i} we can assume P minimal. If A is Artinian then the P_{i} are maximal. If I is radical the P_{i} are pairwise different. Thus under the two hypothesis P is unambiguous and A/I is a product of fields. Combining with proposition 2 we have:

Proposition 3 Let A a finite type K-algebra over a field K and I a zero dimensional radical ideal of A, every couple of polynomials of (A/I)[X] has quasimonic gcds.

4 Quasi-inverse and Gcd Computations over an Algebraic Tower of Simple Extensions

4.1 Triangular Sets

Let R be an integral domain, K its fraction field, n a positive integer and V a set of n ordered variables X_{1} < X_{2} < ⋯ < X_{n}. For 1 ≤ i ≤ n, we write R_{i} = R[X_{1}, …, X_{i}] and P_{i} = K[X_{1}, …, X_{i}].

Notations 2 Let p ∈ R_{n}, p ≠ 0, we write deg(p, v) for the degree of p with respect to the variable v, we denote by var(p) the subset of variables v of V for which deg(p, v) > 0. For p ∉ R, we denote by mvar(p) the highest variable of var(p) and call it its main variable, we then write mdeg(p) = deg(p, mvar(p)). We call initial of p and denote by init(p) the leading coefficient of p as an univariate polynomial in mvar(p), we call tail of p and denote it by tail(p) the polynomial

defined by p = init(p) mvar(p)mdeg(p) + tail(p). For E ⊆ R_{n} we write var(E) = {v ∈ V | (∃p ∈ E) | deg(p, v) > 0}.

Definition 6 A subset T of R_{n} is called a triangular set is every polynomial of T is non-constant with initial in R and if p ↦ mvar(p) defines a bijection between T and var(T). We will say that v ∈ V is algebraic in T if v ∈ mvar(T).

Notations 3 Let T be a non-empty triangular set of R_{n}. We will call first(T) the polynomial of T with greatest main variable and rest(T) = T \ {first(T)}. Let v ∈ mvar(T), T_{v} will be the the polynomial of T such that mvar(p) = v. We define T_{v}^{−} = {p ∈ T | mvar(p) < v} and T_{v}^{+} = {p ∈ T | mvar(p) > v}. We will call degree of T the tuple deg(T) of IN^{n} defined by deg(T) = (d_{1}, …, d_{n}), where d_{i} = 0 if X_{i} ∉ var(T) and d_{i} = mdeg( T_{X_{i}}) otherwise. Finally for α = (α_{1}, …, α_{n}) in IN^{n} we write | α | = α_{1} + ⋯ + α_{n}.

Definition 7 Let a, b ∈ R_{n} such that b ∉ R, prem(a, b) and pquo(a, b) will be respectively the pseudo-remainder and pseudo-quotient of a by b when interpreting them as univariate polynomials in mvar(b). Let T be a triangular set of R_{n}, we call pseudo-remainder of a by T the polynomial prem(a, T) equal to a if T is empty and defined by prem(a, T) = prem(prem(a, first(T)), rest(T)) otherwise. An element is said to be T -reduced if prem(a, T) = a

Let a ∈ R_{n} and T = {p_{1}, …, p_{m}} a triangular set of R_{n}. Let l_{i} be the initial de p_{i}, E the set of these initials, S_{E} the multiplicatively stable part of nz(R) generated by E and M_{T} the R-submodule of R_{n} of elements that are T -reduced. There exist integers e_{1}, …, e_{m} and polynomials q_{1}, …, q_{m} of R_{n} such that:

l_{1}^{e_{1}} ⋯ l_{m}^{e_{m}}a = q_{1}p_{1} + ⋯ + q_{m}p_{m} + prem(p, T)  (5)

Notations 4 modulo(a, T) will be the element of S_{E}^{−1} M_{T} defined by

modulo(a, T) = prem(a, T)/(l_{1}^{e_{1}} ⋯ l_{m}^{e_{m}})

Every triangular set is a Gröbner basis for the pure lexicographical ordering and prem(a, T) is reduced with respect to T (in the Gröbner basis meaning). So modulo(a, T) is the normal form of a with respect to T (viewing a and T in P_{n}). Thus, the R-algebras R_{n}/T and S_{E}^{−1} M_{T} are isomorphic and \overline{a}^{T} identifies to modulo(a, T). Moreover modulo(a, T) computes more efficiently than using (5).

Notations 5 Let T = {p_{1}, …, p_{m}} be a triangular set of R_{n} with mvar(p_{i}) < mvar(p_{i+1}). We define reduce(T) = {p_{1}′, …, p_{m}′} with p_{1}′ = p_{1} and p_{i+1}′ = numer(modulo(p_{i+1}, {p_{1}′, …, p_{i}′})). Let E ⊆ R_{n} such that T ∪ E is a triangular set of R_{n}, we write T + E = reduce(T ∪ E) and say that T is auto-reduced if reduce(T) = T.

4.2 Algorithm Specifications

We have two kinds of algorithms. First, we have those which try to compute a gcd or a quasi-inverse modulo a triangular set T (we will define later this terminology) and may return a split of T (their names are suffixed with ElseSplit). Then we have those which compute a gcd or a quasi-inverse using the first ones; they return lists like [[r_{1}, T_{1}], …, [r_{m}, T_{m}]] where the T_{i} are triangular sets such that T ⟼ (T_{1}, …, T_{m}) and where r_{i} is the result modulo T_{i}.

To describe those algorithms we will first give their input and output specifications. For some algorithm called MethodWhichComputes working with objects a, b, T, …, the input specifications are denoted by H_{mwc}(a, b, T, …) and the output ones by S_{mwc}(a, b, T, …). Then, in the following subsections, we will give the corresponding procedures. Up to few modifications they are AXIOM programs. For that reason they may appear rather technical. But, for the same reason, as there is no mysterious routine they may easily allow an implementation in an other programming language.

Notations 6 Throughout this section T is an auto-reduced triangular set (a “a.r.t.s.” for short). We put var(T) = {v_{1}, …, v_{m}}, B = K[v_{1}, …, v_{m}] and A = B/T. Let v ∈ V and p, p_{1}, p_{2} ∈ R_{n}. We will denote by H_{qres}(p, T) the condition var(p) ⊆ var(T) and H_{srges}(p_{1}, p_{2}, v, T) the conjunction of:

(i) (∀w ∈ var(T)) w < v (ii) deg(p_{1}, v) ≥ deg(p_{2}, v) > 0 (iii) (var(p_{1}) ∪ var(p_{2})) \ {v} ⊆ var(T) (iv) modulo(p_{1}, T) = p_{1} and modulo(p_{2}, T) = p_{2}

Definition 8 We assume that H_{srges}(p_{1}, p_{2}, v, T) is satisfied. Let g ∈ R_{n} be T -reduced and satisfying var(g) ⊆ var(p_{1}) ∪ var(p_{2}). Since these polynomials identify to elements of A[v], we will say that g is a gcd modulo T of p_{1} and p_{2} if g is a gcd of p_{1} and p_{2} as in definition 1 with mcoeff(g) ∈ R. We now assume that H_{qres}(p, T) is satisfied. A couple (q, r) ∈ R_{n} × R is a quasi-inverse of p modulo T if q is T -reduced and (q, r) is a quasi-inverse as in definition 3.

Output specifications are the following:

(S_{qres}(T)) : For p ∈ R_{n}, if H_{qres}(p, T) then quasiRecipElseSplit (p, T) returns • either (q, r) ∈ R_{n} × R a quasi-inverse of p modulo T ,

• either two a.r.t.s. T_{1}, T_{2} such that T ⟼ (T_{1}, T_{2}). (S_{srges}(T)) : For every (p_{1}, p_{2}, v) ∈ R_{n}^{2} ×V, if H_{srges}(p_{1}, p_{2}, v, T) then subRes-

GcdElseSplit(p_{1}, p_{2}, v, T) returns

• either a T -reduced g ∈ R_{n} which is a gcd modulo T of p_{1} and p_{2},
• either two a.r.t.s. T_{1}, T_{2} such that T ⟼ (T_{1}, T_{2}).

(S_{esrges}(T)) : For every (p_{1}, p_{2}, v) ∈ R_{n}^{2} × V, if H_{srges}(p_{1}, p_{2}, v, T) then extendedSubResGcdElseSplit (p_{1}, p_{2}, v, T) returns

• either T -reduced (g, f, k) ∈ R_{n}^{3} such that modulo(fp_{1} + kp_{2}, T) = g, with g being a gcd modulo T of p_{1} and p_{2},

• either two a.r.t.s. T_{1}, T_{2} such that T ⟼ (T_{1}, T_{2}). (S_{srg}(T)) : For every (p_{1}, p_{2}, v) ∈ R_{n}^{2}×V, if H_{srges}(p_{1}, p_{2}, v, T) then subResGcd

(p_{1}, p_{2}, v, T) returns a list [[g_{1}, T_{1}], …, [g_{m}, T_{m}]] where g_{i} ∈ R_{n} and T_{i} are a.r.t.s. such that

• subResGcdElseSplit (p_{1}, p_{2}, v, T_{i}) returns g_{i}

• T ⟼ (T_{1}, …, T_{m}) (S_{c}(T)) : For every p ∈ R_{n}, if H_{qres}(p, T) then quasiRecip (p, T) returns a list

[[[p̂_{1}, ∥ p ∥_{1}], T_{1}], …, [p̂_{m}, ∥ p ∥_{m}], T_{m}]], where p̂_{i} ∈ R_{n}, and T_{i} is an a.r.t.s. such that

• quasiRecipElseSplit (p, T_{i}) returns (p̂_{i}, ∥ p ∥_{i})

• T ⟼ (T_{1}, …, T_{m})

We also have an operation called split? which takes as argument any result of the first three operations and returning true if and only if it is a split.

Finally when T is radical as an ideal of P_{n}, all computed splits will be unambiguous. Thus, in that case, the pairs appearing in the result produced by subResGcd (p_{1}, p_{2}, v, T) can be recombined to get a polynomial g which is a gcd modulo T of p_{1} and p_{2}. To do so, use the Chinese remainders algorithm and the extendedSubResGcdElseSplit algorithm. Look at the propositions and at their proofs in the next subsection to understand how this can be done.

4.3 The Algorithm QuasiRecipElseSplit

quasiRecipElseSplit (p, T) == p/s := modulo(p, T) p ∈ R ↪ return ([s, p]) u := mvar(p) esrges := extendedSubResGcdElseSplit ( T_{u}, p, u, T_{u}^{−}) if split?(esrges) then

[T_{1}, T_{2}] := esrges

return [T_{1} + T_{u} + T_{u}^{+}, T_{2} + T_{u} + T_{u}^{+}] else

[f, k, g] := esrges { we have: modulo(f T_{u} + k p, T_{u}^{−}) = g } if deg(g, u) > 0 then

q := pquo( T_{u}, g)

return [ T_{u}^{−} + {g} + T_{u}^{+}, T_{u}^{−} + {q} + T_{u}^{+}] else { we have: g ∈ nz(R) }

return [(k s), g]

Proposition 4 If S_{qres}(T) and S_{esrges}( T_{u}^{−}) hold and if quasiRecipElseSplit (p, T) is not a split of T, putting (p̂, ∥ p ∥) = quasiRecipElseSplit(p, T) we get:

(i) modulo(p, T) = 0 ⟺ ∥ p ∥ = 0 (ii) modulo(p, T) ≠ 0 ⟺ \overline{p}^{T} ∈ nz(A)

The proof of the previous proposition is easy. More generally our algorithms induce a constructive proof of the fact that if T is a radical ideal of P_{n} an element of A is either a zero-divisor either invertible. Furthermore, this statement shows that the computation of a quasi-inverse modulo T leads to that of a gcd modulo a triangular set.

Proposition 5 If the ideal generated by T in P_{n} is radical, if var(p) ⊆ var(T) and if \overline{p}^{T} ∈ nz(A) then it exists q ∈ P_{n} such that \overline{pq}^{T} = 1. Moreover the computation of q can be reduced to the following problem: for a, b ∈ R_{n} and w ∈ var(T), such that H_{srges}(a, b, w, T_{w}^{−}) holds, find u, v, d ∈ R_{n} with all variables except v being algebraic in T_{w}^{−}, d being a gcd modulo T_{w}^{−} of a and b and such that modulo(au + bv, T_{w}^{−}) = d.

Proof. ⊳ By induction on | deg(T) |. If | deg(T) | = 0 or if p ∈ R, we are done. Otherwise let u = mvar(p), W = var( T_{u}^{−}) B’ = K[W] and A’ = B’/ T_{u}^{−}. Since IdK[W]( T_{u}^{−}) is radical and zero dimensional there exists d ∈ B’[u] with:

⟨\overline{p} T − u, T_{u}⟩q(A’)[u] = ⟨\overline{d} T_{u}^{−}⟩q(A’)[u]  (6)

with init(\overline{d} T_{u}^{−}) ∈ nz(A’) (see prop. 3). Since \overline{p}^{T} ∈ nz(A) we can see that deg(d, u) = 0. By writing the Bézout relation induced by (6) and using induction hypothesis for T_{u}^{−} we finish the proof ⊲. From what we deduce (using prop. 3):

Proposition 6 If the ideal generated by T in P_{n} is radical and if H_{srges}(p_{1}, p_{2}, v, T) holds, then p_{1} and p_{2} have a gcd modulo T in R_{n}.

Proposition 7 Assume that S_{qres}(T) and S_{esrges}( T_{u}^{−}) hold, that the ideal generated by T in P_{n} is radical and that quasiRecipElseSplit (p, T) is a split (T_{1}, T_{2}) of T then, interpreting all ideals in P_{n}, this split is unambiguous.

Proof. ⊳ We use the algorithm notations and W, B’ and A’ as above. We show that IdP_{n}( T_{u}^{−}) + ⟨g, q⟩P_{n} = P_{n}. By prop. 6 there exists d ∈ B’[u] ∩ R_{n} with:

⟨\overline{g} T − u, \overline{q} T − u⟩q(A’)[u] = ⟨\overline{d} T_{u}^{−}⟩q(A’)[u]  (7)

and init(d) ∈ nz(R). So there exists α, β ∈ nz(A’) and g′, q′ ∈ B’[u] with

α\overline{g} T − u = \overline{dg′} T_{u}^{−} and β\overline{q} T − u = \overline{dq′} T_{u}^{−}. By S_{esrges}( T_{u}^{−}) together with the formula defining q, the polynomials g and q have their initials in nz(R). It

follows that the initials of \overline{g′} T_{u}^{−} and \overline{q′} T_{u}^{−} belong to nz(A’).

Since IdP_{n}(T) is radical we can verify that deg(g′, u) > 0 and deg(q′, u) > 0. Similarly, if we had deg(d, u) > 0, then the polynomial f = g′q′d would not be in

IdP_{n}(T) (since init(\overline{f} T_{u}^{−}) ∈ nz(A’) and deg(f, u) < deg( T_{u}, u)) but f^{2} would be inside. It follows that d ∈ nz(R).

We now finish writing the Bézout relation from (7) and using proposition 5 ⊲.

4.4 The Algorithms SubResGcdElseSplit and ExtendedSubResGcdElseSplit

Let v ∈ V and p′ ∈ R_{n} be T -reduced with (∀u ∈ var(T)) u < v and (var(p) \ {v}) ⊆ var(T). We define the normalizeElseSplit operation by :

normalizeElseSplit (p′, v, T) == c := mcoeff(p′, v) c ∈ R ↪ return p′ qres := quasiRecipElseSplit (c, T) split?(qres) ↪ return qres (ĉ, ∥ c ∥) := qres deg(p′, v) = 0 ↪ return ∥ c ∥

return polPart(modulo(∥ c ∥ mvar(p′)mdeg(p′) + ĉtail(p′), T))

Proposition 8 Assume S_{qres}(T) holds and normalizeElseSplit (p′, v, T) is not a split. Writing p′′ = normalizeElseSplit(p′, v, T) we have mcoeff(p′′, v) ∈ R and deg(p′, v) = deg(p′′, v).

This follows from proposition 4 and the algorithm subResGcdElseSplit is :

subResGcdElseSplit (p_{1}, p_{2}, v, T) == np2 := normalizeElseSplit (p_{2}, v, T) split?(np2) ↪ return np2 p_{2} := np2 δ := mdeg(p_{1}) - mdeg(p_{2}) ; ψ : R := −1 ; β : R := (−1)^{(δ+1)} p_{3} := numer(modulo(prem(p_{1}, p_{2}), T)) while (p_{3} ≠ 0) repeat

α : R := mcoeff(p_{2}, v)

p_{3} := p_{3} exquo β ; (p_{1},p_{2}) := (p_{2},p_{3}) np2 := normalizeElseSplit (p_{2}, v, T) split?(np2) ↪ return np2 p_{2} := np2 if deg(p_{2}, v) > 0

then if δ > 0 then newpsi := −α for i in 2..δ repeat

newpsi := (−α newpsi) exquo ψ ψ := newpsi

δ := mdeg(p_{1}) - mdeg(p_{2}) ; β := −α ψ^{δ} p_{3} := numer(modulo(prem(p_{1}, p_{2}), T))

else

p_{3} := 0

return p_{2}

Remark 11 The extendedSubResGcdElseSplit algorithm is the extended version of the previous algorithm. It uses variables l_{1}, l_{2}, u_{1}, u_{2}, w_{1} and w_{2} of S_{E}^{−1} M_{T} such that modulo(u_{1}a + w_{2}b, T) = l_{1}, modulo(u_{2}a + w_{2}b, T) = l_{2} and p_{i} = numer(l_{i}), where a and b are the input values of the polynomials p_{1} and p_{2} respectively. During the computations, the variables l_{1}, …, w_{2} are updated to maintain those relations. For a practical implementation, let us precise how we manage the fractions of S_{E}^{−1} M_{T}. Assume that R is a factorial ring with an effective gcd operation. Thus each element l of S_{E}^{−1} M_{T} has a canonical form, i.e. numPart(l) is the content of numer(l) and numPart(l) and denom(l) are relatively prime, using nz(R) instead of S_{E} (for efficiency). Then, we manage those fractions in a lazy way. More precisely, in the extendedSubResGcdElseSplit algorithm, fractions are not stored in their canonical form. (the exact divisions by β could fail). We only simplify the final fractions l_{2}, u_{2}, w_{2} before cleaning their denominators (i.e. putting the same denominator in those three fractions and removing it) to get the output value when it is not a split.

normalizeElseSplit (l, u, w, v, T) == c := mcoeff(polPart(l), v) c ∈ R ↪ return [l, u, w] ces := quasiRecipElseSplit (c, T) split?(ces) ↪ return ces (ĉ, ∥ c ∥) := ces (l′, u′, w′) := (modulo(c̄ l, T), modulo(ĉu, T), modulo(c̄ w, T)) return [l′, u′, w′]

extendedSubResGcdElseSplit (p_{1}, p_{2}, v, T) == (l_{1}, l_{2}) := (p_{1}/1, p_{2}/1)

(u_{1}, u_{2}) := (1/1, 0/1)
(w_{1}, w_{2}) := (0/1, 1/1)
luw_{2} := normalizeElseSplit (l_{2}, u_{2}, w_{2}, v, T)
split?(luw_{2}) ↪ return luw_{2}
[l_{2}, u_{2}, w_{2}] := luw_{2} ; p_{2} := numer(l_{2})
ψ := -1 ; δ := mdeg(p_{1}) - mdeg(p_{2}) ; β := (-1)**(δ+1)
[p_{3}, q_{3}] := [prem(p_{1}, p_{2}), pquo(p_{1}, p_{2})]
l_{3} := modulo(p_{3}, T)

while (l_{3} ≠ 0) repeat α := mcoeff(p_{2}, v) ; λ := α^{δ+1} l_{3} := (numer(l_{3}) exquo β)/denom(l_{3}) l_{4} := modulo(q_{3}, T) ; p_{3} := numer(l_{3}) (s_{1}, s_{2}) := (denom(l_{1}), denom(l_{2})) u_{3} := modulo(λ s_{1} u_{1} − l_{4} s_{2} u_{2}, T) u_{3} := (numer(u_{3}) exquo β)/denom(u_{3}) w_{3} := modulo(λ s_{1} w_{1} − l_{4} s_{2} w_{2}, T) w_{3} := (numer(w_{3}) exquo β)/denom(w_{3}) (l_{1}, l_{2}) := (l_{2}, l_{3}) (p_{1}, p_{2}) := (p_{2}, p_{3}) (u_{1}, u_{2}) := (u_{2}, u_{3}) (w_{1}, w_{2}) := (w_{2}, w_{3}) luw_{2} := normalizeElseSplit (l_{2}, u_{2}, w_{2}, v, T) split?(luw_{2}) ↪ return luw_{2} [l_{2}, u_{2}, w_{2}] := luw_{2} ; p_{2} := numer(l_{2}) if deg(p_{2}, v) > 0

then

if δ > 0 then newpsi := −α for i in 2..δ repeat

newpsi := (−α ∗ newpsi) exquo ψ ψ := newpsi

δ := mdeg(p_{1}) - mdeg(p_{2})

β := −α ψ^{δ}

[p_{3}, q_{3}] := [prem(p_{1}, p_{2}), pquo(p_{1}, p_{2})] l_{3} := modulo(p_{3}, T)

else

l_{3} := 0

return clearDenoms (u_{2}, w_{2}, l_{2})

4.5 The Algorithms SubResGcd and QuasiRecip

They deduce easily from previous ones managing the discussion. For instance:

subResGcd (p_{1}, p_{2}, v, T) == toSee := [ [ [p_{1}, p_{2}], T] ] ; toSave := [ ] while not empty? toSee repeat

[[a_{j}, b_{j}], T_{j}] := first toSee ; toSee := rest toSee res := subResGcdElseSplit (a_{j}, b_{j}, v, T_{j}) if not split?(res)

then

toSave := cons([res, T_{j}], toSave) else

for T in res repeat a_{j} := polPart(modulo(a_{j}, T)) ; b_{j} := polPart(modulo(b_{j}, T)) if (deg(a_{j}, v) = 0) or (deg(b_{j}, v) = 0)

then

toSave := cons([1, T_{j}], toSave) else

if mdeg(a_{j}) < mdeg(b_{j}) then (a_{j}, b_{j}) := (b_{j}, a_{j})
toSee := cons([ [a_{j}, b_{j}], T], toSee)

return toSave

4.6 Algorithms Correction

We now verify that the algorithms satisfy their output specifications.

Proposition 9 The algorithms quasiRecipElseSplit, subResultantGcdElseSplit and extendedSubResultantGcdElseSplit satisfy respectively S_{qres}(T), S_{srges}(T), and S_{esrges}(T) for all T.

Proof. ⊳ We saw that whenever S_{srges}(T) holds, S_{esrges}(T) also holds. It suffices to show by induction on | deg(T) | that S_{qres}(T) and S_{srges}(T) both hold. Let p, p_{1}, p_{2} in R_{n} and v in V such that H_{srges}(p_{1}, p_{2}, v, T) and H_{qres}(p, T) hold.

If | deg(T) | = 0 (T is empty), then from H_{qres}(p, T), p ∈ R and modulo(p, T) is p/1. So subResultantGcdElseSplit is the usual subresultant algorithm which satisfies S_{srges}(T).

On the contrary if | deg(T) | > 0, and using the algorithm notations we write p/s = modulo(p, T), let us look at quasiRecipElseSplit (p, T). We can verify that H_{esrges}( T_{u}, p, u, T_{u}^{−}) holds, thus S_{esrges}( T_{u}^{−}) applies.

If esrges is a “f.s.a.r.t.s.” (fundamental split into a.r.t.s.) of T_{u}, then quasi-RecipElseSplit (p, T) is also a f.s.a.r.t.s. of T.

If deg(g, u) > 0, we also obtain a f.s.a.r.t.s. of T since g pseudo-divises T_{u} modulo T_{u}^{−}. Since init(g) ∈ nz(R), there exists t ∈ nz(R) with modulo(gq, T_{u}^{−}) = t T_{u} and we have init(q) ∈ nz(R). Thus gq belongs to the ideal of P_{n} generated by T but none of them does.

Finally, if deg(g, u) = 0 and if a is the original input polynomial we have modulo(ask, T) = modulo(pk, T) = g and, since g ∈ nz(R) S_{qres}(T) holds.

We now deduce S_{srges}(T) by looking at subResGcdElseSplit (p_{1}, p_{2}, v, T). If at any step normalizeElseSplit (p_{2}, v, T) is a f.s.a.r.t.s., then the same holds

for subResGcdElseSplit (p_{1}, p_{2}, v, T). We will assume that this is not the case.

By induction hypothesis and since S_{qres}(T) holds, we are under assumptions of proposition 4 and proposotion 8 applies.

Thus the line p_{2} := np2 replaces p2 with p′_{2} having same degree and initial in R and these are associated as polynomials of q(A)[v]. Since the initals of the polynomials of T are in R, we have ⟨p_{1}, p_{2}⟩q(A)[v] = ⟨p_{2}, p_{3}⟩q(A)[X] and it follows that the returned p_{2} is a (definition 1) gcd of the original p_{1} and p_{2} .

Finally it is reduced modulo T since it is the result of a normalizeElseSplit (p_{2}, v, T) operation ⊲.

Let us remark that if the ideal generated by T in P_{n} is radical then splits eventually appearing during computations are unambiguous (by proposition 7).

4.7 Application to Zero Dimensional System Solving

Let I be a zero dimensional ideal of P_{n} given by a lexicographical Gröbner basis G sorted by increasing leading monomials. The lextriangular algorithm (see [12]) applied to G returns a split of I with every component being a triangular set.

It works managing two lists toSave and toSee. The first one is made of already built components, the second one is a list of triplets [T, v, H] where T is triangular set (under construction), v is the greatest variable algebraic in T and H is the sublist of G of those polynomials g such that mvar(g) > v.

To add the first polynomial p of H to T we determine if p is quasi-monic in (K[var(T)]/T) [w], where w is its main variable and ip is the initial of p. To do so, we run quasiRecip (ip, T); this leads to a discussion i.e. a list of pairs as described in the output specification of that operation.

For each alternative of the discussion if ip is a zero divisor, we forget p and proceed with the next polynomial of the list H. On the contrary, if ip is invertible modulo T, we add p to T and proceed replacing H by its polynomials with main variable bigger than w.

Correctness follows from a theorem of Gianni and Kalkbrenner (see [8, 10, 12]):

lextriangular G == toSee := [[[first(G)], mvar(first(G)), rest(G)]] toSave := [ ] while not empty? toSee repeat

[T, v, H] := first toSee toSee := rest toSee p := first H ; ip := init(p) lq := quasiRecip (ip, T) while not empty? lq repeat [[q̂, ∥ q ∥], T′] := first lq lq := rest lq if ∥ q ∥ = 0 then

toSee := cons([T′, v, rest(H)], toSee) else

newp := ∥ q ∥ mvar(p)mdeg(p) + q̂ tail(p) newp := polPart(numer(modulo(newp, T′))) newT := cons(newp, T′) newv := mvar(newp) newH := [g ∈ H | mvar(g) > newv] if empty? newH then

toSave := cons(newT, toSave) else

toSee := cons([newT, newv, newH], toSee)

return toSave Acknowledgments: we wish to thank D. Lazard and the referees for their hepfull suggestions and comments.

References

1. J. Backelin and R. Frberg. How we proved that there are exactly 924 cyclic 7-roots. In S. M. Watt, editor, Proc. ISSAC’91, pages 103–111. ACM, 1991.

2. B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck, 1965.

3. D. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms. Spinger-Verlag, 1991.

4. J. Della Dora, C. Discrescenzo, and D. Duval. About a new method method for computing in algebraic number fields. In Proc. EUROCAL 85 Vol. 2, volume 204 of Lect. Notes in Comp. Sci., pages 289–290. Springer-Verlag, 1985.

5. D. Duval. Questions Relatives au Calcul Formel avec des Nombres Algbriques. Universit de Grenoble, 1987. Thse d’Etat.

6. J.C. Faugère. Résolution des systèmes d’équations algébriques. Université Paris 6, 1994. Thse de Doctorat.

7. Richard D. Jenks and Robert S. Stutor. AXIOM, The Scientific Computation System. Springer-Verlag, 1992.

8. M. Kalkbrener. Solving systems of algebraic equations by using Gröbner basis. European Conference on Computer Algebra, Leipzig, GDR, 1987 (J. H. Davenport, ed.). Lecture Notes in Computer Science , 378:282–292, 1987.

9. M. Kalkbrener. A generalized euclidean algorithm for computing triangular representations of algebraic varieties. J. Symb. Comp., 15:143–167, 1993.

10. P. Gianni. Properties of Gröbner basis under specializations European Conference on Computer Algebra, Leipzig, GDR, 1987 (J. H. Davenport, ed.). Lecture Notes in Computer Science , 378:293–297, 1987.

11. D. Lazard. A new method for solving algebraic systems of positive dimension. Discr. Appl. Maths, 33:147–160, 1991.

12. D. Lazard. Solving zero-dimensional algebraic systems. J. Symb. Comp., 13:117– 132, 1992.

13. D. Lazard. Systems of algebraic equations (algorithms and complexity). In Eisenbud and Robbiano, editors, Proceedings of Cortona Conference. Cambridge University Press, 1993.

14. R. Loos. Generalized polynomial remainder sequences. In Symbolic and Algebraic Computation, pages 115–137. Spinger-Verlag, 1982.

15. B.L. van der Waerden. Algebra. Springer-Verlag, 1991. seventh edition.

This article was processed using the L^{A}TEX macro package with LLNCS style