Complexity Results for Triangular Sets

Éric Schost

Laboratoire GAGE, École polytechnique, 91128 Palaiseau Cedex, France

Abstract

We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positive-dimensional case. We reduce to dimension zero by placing the free variables in the base field, so the solutions can be represented by triangular sets with coefficients in a rational function field.

We give intrinsic-type bounds on the degree of the coefficients in such a triangular set, and on the degree of an associated degeneracy hypersurface. Then we show how to apply lifting techniques in this context, and point out the role played by the evaluation properties of the input system.

Our algorithms are implemented in Magma; we present three applications, relevant to geometry and number theory.

Key words: triangular sets, complexity, symbolic Newton operator

1 Introduction

This article studies the triangular representation of the solutions of a polynomial system. Our first focus is on complexity results and algorithms; we also present a series of applications that were treated with these techniques. To make things clear, let us first display a concrete example of a triangular set.

An example in ℚ[X_{1}, X_{2}]. Consider the polynomial system in ℚ[X_{1}, X_{2}]:

F_{1} = −X_{1}^{3}X_{2} + 2X_{1}^{2} − 4X_{1}X_{2}^{2} + 2X_{1}X_{2} − 2, F_{2} = X_{1}^{2}X_{2} − X_{1} + 4X_{2}^{2} − 2X_{2}.

  Email address: Eric.Schost@polytechnique.fr (Éric Schost).

Preprint submitted to Elsevier Science 27 March 2003

It admits the following Gröbner basis for the lexicographic order X_{1} < X_{2}:

\begin{aligned}T_{1} & = & X_{1}^{2} − 2, \\ T_{2} & = & X_{2}^{2} − \frac{1}{4}X_{1}. \end{aligned}

Since T_{1} is in ℚ[X_{1}] and T_{2} in ℚ[X_{1}, X_{2}], we say that (T_{1}, T_{2}) form a triangular set. In particular, T_{1} describes the projection of the zero-set of (F_{1}, F_{2}) on the X_{1}-axis.

From the field-theoretic point of view, the system (F_{1}, F_{2}) generates a prime zero-dimensional ideal, so ℚ → B := ℚ[X_{1}, X_{2}]/(F_{1}, F_{2}) defines a field extension. We let x_{1}, x_{2} be the images of X_{1}, X_{2} in B; then T_{1} is the minimal polynomial of x_{1} in ℚ → B and T_{2}, seen in ℚ(x_{1})[X_{2}], is the minimal polynomial of x_{2} in ℚ(x_{1}) → B.

Generalization and first complexity considerations. Consider now an arbitrary field 𝔎, \overline{𝔎} its algebraic closure, and a zero-dimensional variety 𝔚 ⊂ 𝔸^{n}(\overline{𝔎}) defined over 𝔎. For simplicity, we take 𝔚 irreducible over 𝔎; then just as above, the ideal defining 𝔚 admits the following Gröbner basis for the lexicographic order X_{1} < ⋯ < X_{n}:

T_{1}(X_{1}),
T_{2}(X_{1}, X_{2}),
⋮
T_{n}(X_{1}, …, X_{n}),

with T_{k} in 𝔎[X_{1}, …, X_{k}], and monic in X_{k}, for k ≤ n. We will use this as an intuitive definition of a triangular set for the rest of this informal introduction. Note that if 𝔚 is not irreducible, its defining ideal might not have such a triangular family of generators: several triangular sets may be necessary.

For k ≤ n, the family T_{1}, …, T_{k} describes the projection of 𝔚 on the affine subspace of coordinates X_{1}, …, X_{k}. In particular, as above, T_{1} is the minimal polynomial of X_{1} modulo the ideal defining 𝔚. This close link between projections and triangular representations is central in what follows.

Let us turn to complexity considerations. The product of the degrees of the polynomials T_{k} in their “main variable” Π_{k≤n} deg_{X_{k}} T_{k} equals the number of points in 𝔚, and bounds the total degree of each polynomial T_{k}. Thus, in terms of degrees in the variables X_{1}, …, X_{n}, there is not much more to say.

New questions arise when the base field 𝔎 is endowed with a “size” function: if 𝔎 is a rational function field, we may consider the degree of its elements; if 𝔎 is a number field, we can talk about the height of its elements. In this context, it becomes natural to ask how the size of the coefficients in T_{1}, …, T_{n} relates to some invariants measuring the “complexity” of the variety 𝔚. In view of the above remarks, a more accurate question is actually, for k ≤ n, the relation between the size of the coefficients in T_{1}, …, T_{k} and the complexity of the projection of 𝔚 on the subspace of coordinates X_{1}, …, X_{k}.

In this article, we focus on this question in the function field case. Here is the concrete situation from where the question originates.

Polynomial systems with parameters. A variety of problems can be described by polynomial systems involving free variables, or parameters. In such situations, we also often know that there are only finitely many solutions for a generic choice of the parameters.

In other words, we are considering systems that are zero-dimensional over the field of rational functions on some parameter space; triangular sets with rational functions coefficients can then be used to represent their solutions. The following applications motivated this approach; they are detailed in Section 8.

• Modular equations. In Gaudry and Schost [2002], we propose a definition of modular equations for hyperelliptic curves, with a view towards pointcounting applications. For a given curve, these equations come from the resolution of zero-dimensional polynomial systems, as the minimal polynomial of one of the unknowns. Thus, they can be obtained from a triangular set computation, as in the introductory example.

An interesting question is that of modular equations for a curve with generic coefficients, which can be precomputed and stored in a database. This was already done in the elliptic case, and is now done for a first hyperelliptic modular equation in the Magma package CrvHyp. This naturally raises the question of triangular sets with coefficients in a rational function field.

• Curves with split Jacobian. Curves of genus 2 with (2,2)-split Jacobian are of interest in number theory: over ℚ, torsion, rank and cardinality records are obtained for such curves, see Kulesz [1995, 1999], Howe et al. [2000]. Roughly speaking, these curves are characterized by the presence of elliptic quotients of degree 2 of their Jacobian.

We studied such curves in Gaudry and Schost [2001], and showed that the elliptic quotients can be read off triangular sets coming from the resolution of a suitable polynomial system. Classification questions require treating this question for curves with generic coefficients, which leads again to the problem of computing triangular sets over a rational function field.

• Implicitization. Finally, we will show that the implicit equation of a parametrized surface in ℝ^{3} can be obtained using the triangular representation.

Contrary to the above, this question is not a priori formalized in terms of a parametric system. Nevertheless, this question actually reduces to the computation of a minimal polynomial over the rational function field ℚ(x_{1}, x_{2}), which can be done using triangular sets.

These examples share the following property: only a partial information, such as a specific eliminating polynomial, is really wanted. We now see how triangular sets can answer this question with good complexity.

Overview of our results. The above discussion is formalized as follows: we consider a polynomial system F defined over a field K, depending on m parameters P_{1}, …, P_{m} and n unknowns X_{1}, …, X_{n}. Geometrically speaking, F defines a variety W of dimension m in 𝔸^{m+n}(\overline{K}) and generates a zerodimensional ideal, when extended over the field of rational functions on 𝔸^{m}(\overline{K}). Then its ”generic solutions” can be represented by a family of triangular sets with coefficients in this rational function field.

For this short overview, we assume that the generic solutions are represented by a single triangular set T_{1}, …, T_{n}. Using additional regularity hypotheses, we will answer the following questions: How do the degrees in this triangular set relate to geometric degrees? How accurately does this triangular set describe the solutions of the parametric system F? How fast can it be computed?

• Degree bounds. The coefficients of T_{1}, …, T_{n} are rational functions in the free variables P_{1}, …, P_{m}. We first show that their degrees are bounded by intrinsic geometric degrees, that is, independently of the Bézout number of the system F. Precisely, for k ≤ n, the coefficients of T_{1}, …, T_{k} have degree bounded in terms only of the degree of the projection W_{k} of W on the space of coordinates P_{1}, …, P_{m}, X_{1}, …, X_{k}. The precise bound is of order (deg W_{k})^{k}.

• Geometric degree of the degeneracy locus. A triangular set with coefficients in a rational function field describes generic solutions. Thus, there is an open subset in the parameter space where none of the denominators of these rational functions vanishes, and where their specialization gives a description the solutions of the parametric system F.

We show that the locus where the specialization fails is contained in an hypersurface whose degree is quadratic in the geometric degree of W. Note the difference with the above degree bounds, which are not polynomial in this degree. The analysis of the probabilistic aspects of our algorithms are based on this result.

• Algorithms. Triangular sets are useful for structured problems. For instance, all the above examples can be reduced to the computation of the first k polynomials T_{1}, …, T_{k}, for some k ≤ n. We give probabilistic algorithms for computing these polynomials, whose complexity is polynomial in the size of the output. Using the above upper bound, the complexity actually depends on the degree of the projection W_{k} of W on the space of coordinates P_{1}, …, P_{m}, X_{1}, …, X_{k}, but not on the degree of W itself.

Note nevertheless that our complexity results comprise an additional factor which is exponential in n, inherent to computations with triangular sets.

Following the series of articles Giusti et al. [1995, 1997, 1998], Heintz et al. [2000], Giusti et al. [2001], Heintz et al. [2001], our algorithms rely on symbolic Newton lifting techniques and the Straight-Line Program representation of polynomials. Their practical behavior matches their good complexity, as they enabled to solve problems that were otherwise out-of-reach.

Comparison with primitive elements techniques. This work is in the continuation of Schost [2003], which focuses on a representation by primitive element techniques, the geometric resolution, in a similar context. Caution must be taken when comparing the two approaches. They answer different questions; as such, their complexities cannot be compared directly, since they are stated in terms of different quantities.

We use again the above notation: the geometric object of interest is a variety W defined by polynomials in K[P_{1}, …, P_{m}, X_{1}, …, X_{n}], and for k ≤ n, W_{k} is its projection on the space of coordinates P_{1}, …, P_{m}, X_{1}, …, X_{k}.

The degree bound of the coefficients in a geometric resolution is linear in the degree of W. This is to be compared with the results for the triangular representation, which are not polynomial in this degree. On the other hand, triangular sets take into account the degrees of the successive projections W_{k}, which cannot be reached using a primitive element. These degrees can be arbitrarily smaller than the degree of W, making the interest of the triangular representation.

Consider now the algorithmic aspect. The algorithm in Schost [2003] computes a parametric geometric resolution with a complexity that depends on the degree of W. The algorithms proposed here compute k polynomials T_{1}, …, T_{k}, for any given k ≤ n; their complexity depends on the degree of the corresponding projection W_{k} of W on the space of coordinates (P_{1}, …, P_{m}, X_{1}, …, X_{k}), but not on the degree of W. Again, this suggests that triangular sets are of interest for problems with a structure, where projections might induce degree drops. We refer to Section 8 for a practical confirmation for several applications.

Related work. In dimension zero, a landmark paper for the triangular representation is Lazard [1992]. Our definition of triangular sets is inspired by the one given there, as is the treatment of more technical questions such as splitting and combining triangular sets.

In arbitrary dimension, several notions of triangular sets and algorithms exist, see Lazard [1991], Kalkbrener [1991], Maza [1997], Aubry [1999], Dellière [1999], Szanto [1999]. For a comparison of some of these approaches, see Aubry et al. [1999]; we also refer to the detailed survey of Hubert. Our choice to reduce the question to dimension zero over a field of rational functions yields algorithms with good complexity, and easy to implement. Yet, our output is not as strong as for instance that of Lazard [1991], Maza [1997], Dellière [1999]: ours is only generically valid.

Upper bounds on the degrees of the polynomials in a triangular set were given in Gallo and Mishra [1990] and Szanto [1999]; we recall these results in the next section. In particular, the approach of Gallo and Mishra [1990] inspired Theorem 1 below. We also use results from Schost [2003], which follow notably Sabia and Solernó [1996].

Lifting techniques for polynomial systems were introduced in Trinks [1985], Winkler [1988]. They were used again in the series of articles by Giusti, Heintz, Pardo and collaborators, Giusti et al. [1995, 1997, 1998], Heintz et al. [2000], Giusti et al. [2001], Heintz et al. [2001]. The conjoint use of the Straight-Line Program representation led there to algorithms with the best known complexity for primitive element representations. The present work is in the continuation of the above; see also the survey of Pardo [1995] for a historical presentation of the use of Straight-Line Programs in elimination theory. Finally, let us mention the results of Lecerf [2002], which extend lifting techniques to situations with multiplicities.

We note that the article Heintz et al. [2000] precedes Schost [2003] and the present work, and considers similar questions of parametric systems. Nevertheless, we noted in Schost [2003] that the geometric hypotheses made in that article are not satisfied in many “real life” applications, and this is again the case for the applications treated here.

It should be noted that our complexity statements are of an arithmetic nature, that is, we only estimate the number of base field operations. When the base field is the rational field, the notion of binary complexity will give a better description of the expected computation time. We have not developed this aspect, which requires arithmetic-geometric considerations. We refer to Krick and Pardo [1996], Giusti et al. [1997], Krick et al. [2001] where such ideas are presented.

This work is based on a shorter version published in Schost [2002]. The degree bounds given here are sharper. The whole analysis of the degeneracy locus and the subsequent error probability analyses for the algorithms are new. The complexity results are now precisely stated in terms of basic polynomial and power series arithmetic.

Acknowledgements. I wish to thank L.M. Pardo for his useful remarks on the first version of this paper.

2 Notation, Main Results

Triangular sets in dimension zero. We first define triangular sets over a ring R. Our definition is directly inspired by that of reduced triangular sets given in Lazard [1992]: a triangular set is a family of polynomials T = (T_{1}, …, T_{n}) in R[X_{1}, …, X_{n}] such that, for k ≤ n:

• T_{k} depends only on X_{1}, …, X_{k},

• T_{k} is monic in X_{k},

• T_{k} has degree in X_{j} less than the degree in X_{j} of T_{j}, for all j < k.

Let now 𝔎 be a field, \overline{𝔎} its algebraic closure and 𝔚 ⊂ 𝔸^{n}(\overline{𝔎}) a zero-dimensional variety. Recall that 𝔚 is defined over 𝔎 if its defining ideal in \overline{𝔎}[X_{1}, …, X_{n}] is generated by polynomials in 𝔎[X_{1}, …, X_{n}].

In this case, a family {T^{1}, …, T^{J}} of triangular sets with coefficients in 𝔎 represents the points of 𝔚 if the radical ideal defining 𝔚 in \overline{𝔎}[X_{1}, …, X_{n}] is the intersection of the ideals generated by T^{1}, …, T^{J}, and if for j ≠ j′, T^{j} and T^{j′} have no common zero.

In this situation, all ideals (T^{j}) are radical by the Chinese Remainder Theorem. We then relate the degrees of the polynomials in the family {T^{1}, …, T^{J}} and the cardinality of 𝔚:

• If 𝔚 is irreducible, the family {T^{1}, …, T^{J}} is actually reduced to a single triangular set T = (T_{1}, …, T_{n}) and the product Π_{k≤n} deg_{X_{k}} T_{k} is the cardinality of 𝔚. Here, deg_{X_{k}} T_{k} denotes the degree of T_{k} in the variable X_{k}.

• If 𝔚 is not irreducible, a family {T^{1}, …, T^{J}} satisfying our conditions exists but is not unique [Lazard, 1992, Proposition 2 and Remark 1]; now the sum ∑_{j≤J} Π_{k≤n} deg_{X_{k}} T_{k}^{j} is the cardinality of 𝔚. Hereafter, note that the superscript in the notation T_{k}^{j} does not denote a j-th power.

Note that it necessary to work over the algebraically closed field \overline{𝔎}, or more generally to impose separability conditions, to obtain equalities as above, relating the degrees in the triangular sets T or {T^{1}, …, T^{J}} and the number of points in the variety 𝔚.

The basic geometric setting. We now turn to more geometric considerations. All along this article, we fix a field K, \overline{K} its algebraic closure, and work in the affine space 𝔸^{m+n}(\overline{K}). We denote by P = P_{1}, …, P_{m} the first m coordinates in 𝔸^{m+n}(\overline{K}) and by X = X_{1}, …, X_{n} the last n coordinates. We use the notion of geometric degree of an arbitrary affine variety (not necessarily irreducible, nor even equidimensional), introduced in Heintz [1983].

In what follows, the affine space 𝔸^{m+n}(\overline{K}) is endowed with two families of projections. For k ≤ n, we define μ_{k} and π_{k} as follows; hereafter, p denotes a point in 𝔸^{m}(\overline{K}).

\begin{aligned}μ_{k} : & 𝔸^{m+n}(\overline{K}) & → & 𝔸^{m+k}(\overline{K}) & π_{k} : & 𝔸^{m+k}(\overline{K}) & → & 𝔸^{m}(\overline{K}) \\ & (p, x_{1}, …, x_{n}) & ↦ & (p, x_{1}, …, x_{k}) & & (p, x_{1}, …, x_{k}) & ↦ & p. \end{aligned}

Note in particular that π_{n} maps the whole space 𝔸^{m+n}(\overline{K}) to 𝔸^{m}(\overline{K}).

The main geometric object is a m-dimensional variety W ⊂ 𝔸^{m+n}(\overline{K}). Our first results are of an intrinsic nature, so we do not need an explicit reference to a defining polynomial system. The assumptions on W follow the description made in the introduction:

Assumption 1 Let {W^{j}}_{j≤J} denote the irreducible components of W. We assume that for j ≤ J:

(1) the image π_{n}(W^{j}) is dense in 𝔸^{m}(\overline{K}).

(2) the extension \overline{K}(P_{1}, …, P_{m}) → \overline{K}(W^{j}) is separable.

Assumption 1.1 implies that the fibers of the restriction of π_{n} to each component of W are generically finite; this justifies treating the first m coordinates as distinguished variables and calling them parameters. Assumption 1.2 is of a more technical nature, and will help to avoid many difficulties; it is always satisfied in characteristic zero.

Under Assumption 1, we can define the generic solutions of the variety W. Let J ⊂ \overline{K}[P, X] be the radical ideal defining W and J_{P} its extension in \overline{K}(P)[X]. We call generic solutions of W the roots of J_{P}, which are in finite number.

We now refer to the previous paragraph, taking 𝔎 = \overline{K}(P), and for 𝔚 the finite set of generic solutions. Using Assumption 1.2, the ideal J_{P} remains radical in \overline{𝔎}[X], so the generic solutions are indeed defined over 𝔎 = \overline{K}(P). Thus, they can be represented by a family of triangular sets in \overline{K}(P)[X]; our purpose in this article is to study their complexity properties, and provide algorithms to compute with them.

Let us immediately note some particular cases:

• If W is irreducible, a single triangular set is enough to represent its generic solutions.

• If W is defined over K, it can be written W = ∪_{j≤J}W^{j}, where for all j, W^{j} is defined over K, and the defining ideal of W^{j} is prime in K[P, X]. Then the generic solutions of each W^{j} are represented by a triangular set in K(P)[X]; the generic solutions of W are represented by their reunion.

Projections of W. Before presenting the main results, we introduce some notation related to W and its successive projections. Let k be in 1, …, n. First of all, we denote by X_{≤k} the first k variables X_{1}, …, X_{k}; if T is a triangular set, T_{≤k} is the sub-family T_{1}, …, T_{k}.

We denote by W_{k} ⊂ 𝔸^{m+k}(\overline{K}) the closure of μ_{k}(W), so in particular W_{n} coincides with W. It is a routine check that for all k, W_{k} satisfies Assumption 1 as well.

Let J_{k} ⊂ \overline{K}[P, X_{≤k}] be the ideal defining W_{k}, and J_{P,k} its extension in \overline{K}(P)[X_{≤k}]. Under Assumption 1.1, J_{P,k} coincides with J_{P} ∩\overline{K}(P)[X_{≤k}]. Thus if the generic solutions of W are defined by a triangular set T, J_{P,k} is generated by T_{≤k}.

For p in 𝔸^{m}(\overline{K}), we denote by W_{k}(p) the fiber π_{k}^{−1}(p) ∩ W_{k} and by D_{k} the generic cardinality of the fibers W_{k}(p).

Finally, let B_{k} be the quotient \overline{K}(P)[X_{≤k}]/J_{P,k}; by Assumption 1.2, the extension \overline{K}(P) → B_{k} is a product of separable field extensions. Using the separability, B_{k} has dimension D_{k}, by Proposition 1 in Heintz [1983].

Degree bounds. With this notation, we now present our main results. We assume that the generic solutions of W are represented by a triangular set T = (T_{1}, …, T_{n}) in K(P)[X]. In view of the above remarks, this is not a strong limitation: if this assumption is not satisfied, as soon as W is defined over K, the following upper bounds apply to all the K-defined irreducible components of W.

As mentioned in the preamble, the degree bounds of T in the X variables are easily dealt with: for all k ≤ n, the product Π_{i≤k} deg_{X_{i}} T_{i} is the dimension of B_{k} over \overline{K}(P), that is, the generic cardinality D_{k} of the fibers W_{k}(p).

We will thus concentrate on the dependence with respect to the P variables. For k ≤ n, the polynomial T_{k} depends only on the variables X_{1}, …, X_{k}, and has coefficients in K(P) = K(P_{1}, …, P_{m}). It is then natural to relate the degrees of these coefficients to the degree of the projection of W on the space of coordinates P_{1}, …, P_{m}, X_{1}, …, X_{k}, that is, W_{k}.

This is the object of our first theorem. In all that follows, we call degree of a rational function the maximum of the degrees of its numerator and denominator.

Theorem 1 Let W be a variety satisfying Assumption 1, and suppose that the generic solutions of W are represented by a triangular set T in K(P)[X]. For k ≤ n, all coefficients in T_{k} have degree bounded by (2k^{2} + 2)^{k}(deg W_{k})^{2k+1}.

This result improves those of Gallo and Mishra [1990] and Szanto [1999] for respectively Ritt-Wu’s and Kalkbrener’s unmixed representations. If W is given as the zero-set of a system of n equations of degree d, then Gallo-Mishra’s bound is 2n(8n)^{2n}d(d + 1)^{4n^{2}} and Szanto’s is d^{O(n^{2})}.

With this notation, the Bézout inequality (Theorem 1 in Heintz [1983]) implies that the degree of W_{k} is at most d^{n} for all k. Thus according to Theorem 1, for k ≤ n, in a worst-case scenario the coefficients in the polynomial T_{k} have degree bounded by (2k^{2}+2)^{k}d^{2kn+n}. Hence the estimate is better for low indices k than for higher indices; this contrasts with the previous results, which gave the same bounds for all T_{k}.

For the worst case k = n, our estimates are within the class d^{2n^{2}+o(n^{2})}, to be compared with Gallo and Mishra’s bound of d^{4n^{2}+o(n^{2})}. Any of these bounds are polynomial in d^{n^{2}}; we do not know if this is sharp.

More importantly, Theorem 1 reveals that the degrees of the coefficients of T are controlled by the intrinsic geometric quantities deg W_{k}, rather than by the degrees of a defining polynomial system. For instance, this indicates a good behavior with respect to decomposition, e.g. into irreducible. Also, these degrees may be bounded a priori: in the example presented in Subsection 8.3, the Bézout bound is 1024, but an estimate based on the semantics of the problem gives deg W_{k} ≤ 80.

Degree of the degeneracy locus. We still assume that the generic solutions of W are represented by a triangular set T = (T_{1}, …, T_{n}) in K(P)[X]. Since the coefficients of T are rational functions, there exists an open subset of the parameter space where they can be specialized, and give a description of the fibers of π_{n}. Theorem 2 below gives an upper bound on the degree of an hypersurface where this specialization fails.

Theorem 2 Let W be a variety satisfying Assumption 1, and suppose that the generic solutions of W are represented by a triangular set T in K(P)[X]. There exists a polynomial Δ_{W} ∈ \overline{K}[P] of degree at most (3n deg W +n^{2}) deg W such that, if p ∈ 𝔸^{m}(\overline{K}) does not cancel Δ_{W}:

(1) p cancels no denominator in the coefficients of (T_{1}, …, T_{n}). We denote by (t_{1}, …, t_{n}) ⊂ \overline{K}[X] these polynomials with coefficients specialized at p.

(2) (t_{1}, …, t_{n}) is a radical ideal. Let Z_{n} ⊂ 𝔸^{n}(\overline{K}) be the zero-set of the polynomials (t_{1}, …, t_{n}); then the fiber W_{n}(p) is \{p\} × Z_{n} ⊂ 𝔸^{m+n}(\overline{K}).

Just as Theorem 1, this result is of an intrinsic nature, since it depends only on geometric quantities. Nevertheless, in strong contrast with the previous result, these bounds are polynomial in the geometric degree of W.

In particular, Theorem 2 shows that the reunion of the zero-sets of all denominators of the coefficients of T is contained in an hypersurface of degree bounded polynomially in terms of the degree of W. Thus, the zero-set of any such denominator has degree bounded by the same quantity. Theorem 1 does not give such a polynomial bound for the degrees of the denominators. Were the upper bounds of Theorem 1 to be sharp, this would indicate that these denominators are (high) powers of polynomials of moderate degree.

Algorithms. The above results are purely geometric, and independent of any system of generators. For algorithmic considerations, we now assume that W is given as the zero-set of a polynomial system F = F_{1}, …, F_{n} in K[P, X]. We make the additional assumption that the Jacobian determinant with respect to X is invertible on a dense subset of W. Then Assumption 1 is satisfied, and we consider the problem of computing triangular sets that represent the generic solutions of W.

The underlying paradigm is that solving a zero-dimensional system over K by means of triangular sets is a well-solved task. Thus, the basic idea is first to specialize the indeterminates P in the system F, and solve the corresponding system in the remaining variables X, by means of triangular sets in K[X]. A lifting process then produces triangular sets with coefficients in a formal power series ring, from which we can recover the required information.

Our first contribution treats the case when W is irreducible: its generic solutions are then represented by a single triangular set T = (T_{1}, …, T_{n}), and we propose a probabilistic algorithm that computes T_{1}, …, T_{k} for any k. If W is not irreducible, we compute the minimal polynomial of X_{1} modulo the extended ideal (F_{1}, …, F_{n}) in \overline{K}(P)[X], using similar techniques.

We do not treat the general question of computing a whole family of triangular sets when W is not irreducible. From the practical point of view, this might not be a strong restriction: our results cover all the applications that we had to treat.

We use the following complexity notations:

• We suppose that F is given by a Straight-Line Program of size L, and that F_{1}, …, F_{n} have degree bounded by d.

• We say that f is in O_{log} (g) if there exists a constant a such that f is in O(g log(g)^{a}) — this is sometimes also expressed by the notation f ∈ O˜ (g).

• M(D) denotes the cost of the multiplication of univariate polynomials of degree D, in terms of operations in the base ring. M(D) can be taken in O(D log D log log D), using the algorithm of Schönhage and Strassen [1971].

We denote by C_{0} a universal constant such that for any ring R, any integer D and any monic polynomial T in R[X] of degree D, all operations (+, ×) in R[X]/(T) can be done in at most C_{0}M(D) operations, see Chapter 9 in [von zur Gathen and Gerhard, 1999].

We assume that there exists constants C_{1} and α such that M(D)M(D′) ≤ C_{1}M(DD′) log(DD′)^{α} holds for all D, D′. This assumption is satisfied for all commonly used multiplication algorithms.

• M_{s}(D, M) denotes the cost of M-variate series multiplication at precision D. This can be taken less than M((2D + 1)^{M}) using Kronecker’s substitution. If the base field has characteristic zero, this complexity becomes linear in the size of the series, up to logarithmic factors; see [Lecerf and Schost, 2003, Theorem 1].

We assume that there exists a constant C_{2} < 1 such that M_{s}(D, M) ≤ C_{2}M_{s}(2D, M) holds for all D and M. This is the case for all commonly used estimates, for instance for the ones mentioned above.

Apart from the above constants, the complexities below are stated in terms of the degrees 𝔇_{k} of the rational functions that appear in the output, and the number D_{n}. This number was defined earlier as the generic cardinality of the fibers W_{n}(p); it is thus the generic number of solutions of the parametric system F.

Theorem 3 Assume that W is irreducible. Let p, p′ be in K^{m}; assume that a description of the zeros of the systems F(p, X), F(p′, X) by triangular sets is known. For k ≤ n, let 𝔇_{k} be the maximum of the degrees of the coefficients of T_{1}, …, T_{k}. Then T_{1}, …, T_{k} can be computed within

O_{log} ((nL+n^{3})(C_{0}C_{1})^{n}M(D_{n})M_{s}(4𝔇_{k}, m)+km^{2}D_{n}M(𝔇_{k})M_{s}(4𝔇_{k}, m−1))

operations in K. The algorithm chooses 3m − 1 values in K, including the coordinates of p and p′. If Γ is a subset of K, and these values are chosen in Γ^{3m−1}, then the algorithm fails for at most 50n(k^{2} + 2)^{3k}d^{6kn+4n}|Γ|^{3m−2} choices.

Theorem 4 Let p, p′ be in K^{m}; assume that a description of the zeros of the systems F(p, X), F(p′, X) by triangular sets which define prime ideals in K[X] is known.

Let M_{1} ∈ \overline{K}(P)[U] be the minimal polynomial of X_{1} modulo the extended ideal (F_{1}, …, F_{n}) in \overline{K}(P)[X], and 𝔇_{1} the maximum of the degrees of its coefficients. Then M_{1} can be computed within

O_{log} ((nL + n^{3})(C_{0}C_{1})^{n}M(D_{n})M_{s}(4𝔇_{1}, m) + m^{2}D_{n}M(𝔇_{1})M_{s}(4𝔇_{1}, m − 1))

operations in K. The algorithm chooses 3m − 1 values in K, including the coordinates of p and p′. If Γ is a subset of K, and these values are chosen in Γ^{3m−1}, then the algorithm fails for at most 50nd^{4n}|Γ|^{3m−2} choices.

These complexities are polynomial with respect to the possible number of monomials in the output. The exponential terms (C_{0}C_{1})^{n} reflect the cost of computing modulo a triangular set with n elements.

Using Theorem 1, the above complexities are bounded in terms only of the degrees of the varieties W_{k} (for Theorem 3) and W_{1} (for Theorem 4). Triangular sets are thus useful when a partial information is required: they avoid taking the whole degree of the variety W into account, as would be the case using primitive element techniques.

Finally, note that we could give an alternative formulation for the estimates of probabilities. Referring for instance to Theorem 4, a probability of success greater than 1−ε can be obtained as soon as all random choices are made in a subset Γ of cardinality greater than 50nd^{4n}/ε, assuming a uniform probability distribution.

Organization of the paper. Section 3 presents some auxiliary results for a primitive element representation, the geometric resolution, that are used later. In Section 4, we prove Theorem 1. Section 5 gives technical results that are used in Section 6 for proving Theorem 2. Our algorithms are presented in Section 7, and their applications are detailed in Section 8.

3 Geometric Resolutions

Our complexity results rely on another representation of the solutions of a polynomial system, the geometric resolution. We introduce this notion in Subsection 3.1. In Subsection 3.2, we present the complexity results that are used later; Subsection 3.3 is devoted to prove one of them.

3.1 Definition

The geometric resolution is a representation of a zero-dimensional variety by means of primitive element techniques. It was introduced under this denomination in Giusti et al. [1995, 1997, 1998, 2001]. See also Gianni and Mora [1989], Alonso et al. [1996], Rouillier [1999] for the use of primitive elements and related techniques for polynomial systems.

We first give the definition in a general setting. Let 𝔎 be any field and 𝔍 a radical zero-dimensional ideal of 𝔎[X_{1}, …, X_{N}]. Then a geometric resolution of the extension 𝔎 → 𝔎[X_{1}, …, X_{N}]/𝔍, if it exists, consists in:

• a primitive element 𝔘 = ∑_{i=1}^{N} u_{i}X_{i} of the extension 𝔎 → 𝔎[X_{1}, …, X_{N}]/𝔍,

• its monic minimal polynomial Q ∈ 𝔎[U],

• a parametrization of the variables X_{i} in terms of the primitive element.

In the separable case, when Q has no multiple root, it factors over an algebraic closure of 𝔎 as Π(U − 𝔘(p)), where p runs over the zero-set of 𝔍.

We use two different kinds of parametrizations for the algebraic variables. The first one takes the form

Q′(𝔘)X_{1} = V_{1}(𝔘), … Q′(𝔘)X_{N} = V_{N}(𝔘);

it makes sense as soon as Q′ is invertible modulo Q, i.e. in the separable case. The second type has the form

X_{1} = W_{1}(𝔘), … X_{N} = W_{N}(𝔘).

Even if the latter parametrization seems more natural, better complexity bounds are obtained for the former kind, as we will soon see. In any case, the polynomials Q, V_{i} and W_{i} have coefficients in the base field 𝔎.

Let us return to our specific problem, and consider again the m-dimensional variety W ⊂ 𝔸^{m+n}(\overline{K}). With the notation of the introduction, we will use geometric resolutions in the following contexts:

• We use the denomination parametric resolution when the base field is the rational function field \overline{K}(P), that is, to describe some generic solutions. We give complexity results for this situation in the next subsection.

• Given k ≤ n and a point p in 𝔸^{m}(\overline{K}) such that the fiber W_{k}(p) is finite, we may consider a geometric resolution of the points in W_{k}(p). This means that we will consider polynomials q, w_{1}, …, w_{k} in \overline{K}[U], such that q has no multiple root, and such that the X-coordinates of the points in W_{k}(p) are defined by q(𝔘) = 0 and X_{1} = w_{1}(𝔘), …, X_{k} = w_{k}(𝔘).

3.2 Application to Parametric Situations

Our first complexity statement concerns the existence and the complexity of a parametric resolution for the varieties W_{k} (see Section 2 for the definition); we use it in the next section for proving Theorem 1. It is a slight extension of Proposition 2 in Schost [2003], which itself is inspired by Giusti et al. [1995] and Sabia and Solernó [1996].

Recall that for k ≤ n, B_{k} is the quotient algebra \overline{K}(P)[X_{≤k}]/J_{P,k}, where J_{P,k} is the extension of the ideal defining W_{k} in \overline{K}(P)[X]; D_{k} is the dimension of B_{k} as a \overline{K}(P)-vector space.

Proposition 1 Let k be in 1, …, n. There exists (u_{1}, …, u_{k}) in \overline{K}^{k} such that 𝔘 = ∑_{i=1}^{k} u_{i}X_{i} is a primitive element of B_{k}. Moreover, for any such primitive element, there exist polynomials Q_{k}, V_{1}, …, V_{k} in \overline{K}(P)[U] such that:

• Q_{k} has degree D_{k} and V_{1}, …, V_{k} have degree less than D_{k}.

• Q_{k} is the minimal polynomial of 𝔘 in B_{k}, and has no multiple root.

• The following relations hold in B_{k}:

Q′_{k}(𝔘)X_{1} = V_{1}(𝔘), … Q′_{k}(𝔘)X_{k} = V_{k}(𝔘).

• Let 𝔔_{k}, 𝔙_{1}, …, 𝔙_{k} be the polynomials Q_{k}, V_{1}, …, V_{k} multiplied by the LCM of all denominators of their coefficients. Then the total degrees of these polynomials, seen in \overline{K}[P, U], are bounded by deg W_{k}.

A parametric resolution describes generic solutions, as it has coefficients in the rational function field \overline{K}(P); thus it can be specialized on an open subset of the parameter space. The following proposition gives an upper bound on the degree of an hypersurface where the specialization fails. This result is used in Section 6 for proving Theorem 2.

Proposition 2 Let 𝔘 = ∑_{i=1}^{n} u_{i}X_{i} be a primitive element of B_{n}, Q_{n} its minimal polynomial and W_{1}, …, W_{n} the polynomials in \overline{K}(P)[U] of degree less than D_{n} such that the following relations hold in B_{n}:

X_{1} = W_{1}(𝔘), … X_{n} = W_{n}(𝔘).

There exists a polynomial δ_{W} in \overline{K}[P] of degree at most (2nD_{n} + n^{2}) deg W such that, if p ∈ 𝔸^{m}(\overline{K}) does not cancel δ_{W}:

(1) p cancels no denominator in the coefficients of Q_{n}, W_{1}, …, W_{n}. We let q_{n}, w_{1}, …, w_{n} be these polynomials with coefficients specialized at p.

(2) The polynomials q_{n}, w_{1}, …, w_{n} form a geometric resolution for the fiber W_{n}(p).

(3) For k ≤ n, the fiber W_{k}(p) has D_{k} points.

(4) For k ≤ n, W_{k}(p) coincides with the projection μ_{k} (W_{n}(p)).

The last part of this section is devoted to prove this proposition.

3.3 Proof of Proposition 2

The following proposition is a particular case of Proposition 1 in Schost [2003], which follows Proposition 1 in Sabia and Solernó [1996]. It leads to Corollary 1, which itself gives the proof of Proposition 2.

Proposition 3 Let k be in 1, …, n. For i ≤ k, let φ_{i} be the map

\begin{aligned}φ_{i} : & 𝔸^{m+k}(\overline{K}) & → & 𝔸^{m+1}(\overline{K}) \\ & (p, x_{1}, …, x_{k}) & ↦ & (p, x_{i}), \end{aligned}

and let M_{i} ∈ \overline{K}[P, U] be a squarefree polynomial defining the closure of φ_{i}(W_{k}). Consider the polynomial M_{i} in \overline{K}[P][U] and let N_{i} ∈ \overline{K}[P] be its leading coefficient. Then G_{i} = M_{i}/N_{i} ∈ \overline{K}(P)[U] is the monic minimal polynomial of X_{i} in B_{k}.

Corollary 1 Let k in 1, …, n, 𝔘 = ∑_{i=1}^{k} u_{i}X_{i} a primitive element of B_{k}, Q_{k} its minimal polynomial and W_{1}, …, W_{k} the polynomials in \overline{K}(P)[U] of degree less than D_{k} such that the following relations hold in B_{k}:

X_{1} = W_{1}(𝔘), … X_{k} = W_{k}(𝔘).

There exists a polynomial δ_{k} in \overline{K}[P] of degree at most (2D_{k} + k) deg W_{k} such that, if p ∈ 𝔸^{m}(\overline{K}) does not cancel δ_{k}:

• p cancels no denominator in the coefficients of Q_{k}, W_{1}, …, W_{k}. We let q_{k}, w_{1}, …, w_{k} be these polynomials with coefficients specialized at p.

• The fiber W_{k}(p) is finite and has D_{k} points; q_{k}, w_{1}, …, w_{k} is a geometric resolution for this fiber. In particular, q_{k} has no multiple root.

Proof. Let us first exclude the infinite fibers. We use the same notations as in Proposition 3: for i ≤ k, G_{i} is the minimal polynomial of X_{i} in B_{k}. Then G_{i} can be written M_{i}/N_{i}, where M_{i} is primitive in \overline{K}[P][U], and N_{i} ∈ \overline{K}[P] is its leading coefficient. Using the previous proposition, N_{i} has degree at most deg W_{k}.

Let N ∈ \overline{K}[P] be the product of all N_{i}, for i ≤ k; then N has degree at most k deg W_{k}. Corollary 14.6 and the proof of Theorem 14.4 in [Eisenbud, 1996] show that if p does not cancel N, then the fiber W_{k}(p) is finite. Then by Proposition 1 in Heintz [1983], this fiber has at most D_{k} points. We now suppose that we are in this situation.

Let f be a polynomial in the ideal J_{k} ⊂ \overline{K}[P, X_{≤k}] defining W_{k}. Then f belongs to the extension J_{P,k} ⊂ \overline{K}(P)[X_{≤k}] so there exist polynomials (g_{1}, …, g_{k+1}) in \overline{K}(P)[X_{≤k}] such that f = ∑_{i=1}^{k} g_{i}(X_{i} − W_{i}(𝔘)) + g_{n+1}Q_{k}(𝔘). Let us now suppose that p cancels no denominator in the coefficients of Q_{k}, W_{1}, …, W_{k}. Then p cancels no denominator in the previous equality. Specializing the variables P at p shows that f(p, X_{≤k}) is in the ideal (q_{k}(𝔘), X_{1} − w_{1}(𝔘), …, X_{k} − w_{k}(𝔘)). Thus the zero-set of these polynomials is contained in the fiber W_{k}(p).

Finally, suppose that p does not cancel the discriminant of Q_{k}, which is a nonzero polynomial by Proposition 1. Then q_{k} has D_{k} distinct roots; since W_{k}(p) has cardinality at most D_{k}, we conclude that q_{k}, w_{1}, …, w_{k} is a geometric resolution for the fiber W_{k}(p), as requested.

With the notations of Proposition 1, p satisfies the last conditions if it does not cancel the determinant δ of the Sylvester matrix associated to 𝔔_{k} and its derivative. We take δ_{k} = Nδ; the degree estimates of Proposition 1 conclude the proof of the corollary. □

We now conclude the proof of Proposition 2. Let δ_{W} be the product of all δ_{k}, for k ≤ n. The estimates D_{k} ≤ D_{n} and deg W_{k} ≤ deg W_{n} prove points 1, 2, 3 of the proposition. To prove the last point, we note that the projection μ_{k}(W_{n}(p)) is contained in W_{k}(p) for all p; thus it is enough to exhibit conditions under which their cardinalities coincide.

Let 𝔘 be a linear form ∑_{i=1}^{n} u_{i}X_{i} which generates B_{n}, Q_{n} its minimal polynomial and W_{1}, …, W_{n} the polynomials in \overline{K}(P)[U] such that the relations X_{1} = W_{1}(𝔘), …, X_{n} = W_{n}(𝔘) hold in B_{n}.

Consider also k ≤ n, 𝔘′ = ∑_{i=1}^{k} u′_{i}X_{i} a linear form which generates B_{k} and Q_{k} its minimal polynomial. Then Q_{k} is the minimal polynomial of ∑_{i=1}^{k} u′_{i}W_{i} modulo Q_{n} and has degree D_{k}.

Let p be in 𝔸^{m}(\overline{K}) and suppose that p cancels neither δ_{k} nor δ_{n}. Then by Corollary 1, W_{k}(p) has cardinality D_{k}. We now prove that the projection μ_{k}(W_{n}(p)) has cardinality D_{k}, which will prove Proposition 2. To this effect, we apply Corollary 1 twice.

• Applied for index k, this shows that p cancels no denominator in the coefficients of Q_{k}, and that the specialized polynomial q_{k} has D_{k} distinct roots.

• For index n, Corollary 1 shows that p cancels no denominator in the coefficients of Q_{n}, W_{1}, …, W_{n} and the specialized polynomials q_{n}, w_{1}, …, w_{n} form a geometric resolution for the fiber W_{n}(p). Let Ξ be the characteristic polynomial of ∑_{i=1}^{k} u′_{i}W_{i} modulo Q_{n}. Then p cancels no denominator in the coefficients of Ξ; specializing these coefficients at p yields the characteristic polynomial χ of ∑_{i=1}^{k} u′_{i}w_{i} modulo q_{n}.

We now conclude the proof. Since Q_{k} is the square-free part of Ξ and q_{k} has D_{k} distinct roots, χ has D_{k} distinct roots. But this number of roots is precisely the cardinality of μ_{k}(W_{n}(p)), so the proposition is proven. □

4 Degree Bounds: Proof of Theorem 1

In this section, we suppose that the generic solutions of W are represented by a triangular set T = (T_{1}, …, T_{n}) in K(P)[X]. For k ≤ n, recall that W_{k} ⊂ 𝔸^{m+k}(\overline{K}) is the closure of the projection μ_{k}(W). We now prove that all coefficients in T_{k} have degree bounded by (2k^{2} + 2)^{k}(deg W_{k})^{2k+1}.

The proof goes as follows: we first apply Proposition 1 to W_{k}, deducing the existence of a suitable parametric resolution. Applying Proposition 4 given below, we obtain Bézout equalities of low degree relating this parametric resolution and the triangular set (T_{1}, …, T_{k}). Inspired by [Gallo and Mishra, 1990], we conclude by turning these relations into a linear system for the coefficients of (T_{1}, …, T_{k}), from which Theorem 1 follows.

First, we present the Bézout identities we will use. The following proposition is Lemma 5 in Krick et al. [1997]; similar results can be seen in Giusti et al. [1997], originating from Giusti et al. [1995].

Proposition 4 Let 𝔎 be a field, and let (F_{1}, …, F_{k}) be a regular sequence in 𝔎[X_{1}, …, X_{k}]. Let d be a bound on the degrees of the polynomials F, and δ the maximum of the degrees of the varieties V(F_{1}, …, F_{k}), for i = 1, …, k − 1.

For i = 0, …, k − 1, let B_{k}^{i} be the quotient

𝔎[X_{1}, …, X_{k}]/(F_{1}, …, F_{k−i}).

Assume that the extension 𝔎[X_{1}, …, X_{i}] → B_{k}^{i} is integral and that the jacobian of (F_{1}, …, F_{k−i}) with respect to (X_{i+1}, …, X_{k}) is a non-zero divisor in B_{k}^{i}. Then if H belongs to (F_{1}, …, F_{k}), there exists polynomials (S_{1}, …, S_{k}) in 𝔎[X_{1}, …, X_{k}] such that

H = S_{1}F_{1} + ⋯ + S_{k}F_{k}

and, for i = 1, …, k, deg S_{i}F_{i} ≤ 2k^{2}dδ + δ max{deg H, d}.

With this proposition, we can prove Theorem 1. As before, we denote by J_{k} and J_{P,k} the ideal defining W_{k} in \overline{K}[P, X_{≤k}] and its extension in \overline{K}(P)[X_{≤k}]. By Proposition 1, there exist u_{1}, …, u_{k} in \overline{K}, and a family of polynomials Q_{k}, V_{1}, …, V_{k} in \overline{K}(P)[U] such that the ideal J_{P,k} is generated by

(Q_{k}(𝔘), Q′_{k}(𝔘)X_{k} − V_{k}(𝔘), …, Q′_{k}(𝔘)X_{1} − V_{1}(𝔘)) ,

where 𝔘 is the linear form ∑_{i=1}^{k} u_{k}X_{k}. Without loss of generality, we can assume that the coefficient u_{k} is not zero. Then, the following family generates the ideal J_{P,k} as well:

R : (Q_{k}(𝔘), Q′_{k}(𝔘)X_{k−1} − V_{k−1}(𝔘), …, Q′_{k}(𝔘)X_{1} − V_{1}(𝔘)) .

We will consider the following families R_{i} in \overline{K}(P)[X_{≤k}], for 0 ≤ i ≤ k − 2:

R_{i} : (Q_{k}(𝔘), Q′_{k}(𝔘)X_{k−1} − V_{k−1}(𝔘), …, Q′_{k}(𝔘)X_{i+1} − V_{i+1}(𝔘)) ,

and R_{k−1} = (Q_{k}(𝔘)). We now check the hypotheses of Proposition 4 for R_{i}, with 𝔎 = \overline{K}(P).

• By Proposition 1, Q′_{k} is invertible modulo Q_{k} so each equation Q′_{k}(𝔘)X_{i} − V_{i}(𝔘) can be written X_{i} − W_{i}(𝔘) modulo Q_{k}(𝔘), for some polynomial W_{i} in \overline{K}(P)[U]. This shows that R_{i} is a regular sequence.

• For i in 0, …, k − 1, we define the ring B_{k}^{i} as \overline{K}(P)[X_{≤k}]/R_{i}. Since the coefficient u_{k} is not zero, we deduce that for i in 0, …, k − 1, B_{k}^{i} is an integral extension of \overline{K}(P)[X_{1}, …, X_{i}].

• Finally, the jacobian determinant of R_{i} with respect to X_{i+1}, …, X_{k} is a constant multiple of (k − 1 − i)-th power of Q′_{k}(𝔘), so it is invertible in B_{k}^{i}.

Thus, the hypotheses of Proposition 4 are satisfied; then we need some degree estimates to apply this proposition. Since the variables P are in the base field 𝔎 = \overline{K}(P), we estimate all degrees in terms of the variables X_{≤k} only. By Proposition 1, the degrees of all polynomials in R are bounded by D_{k} ≤ deg W_{k}. The varieties V(R_{i}) are cylinders built upon zero-dimensional varieties of degree at most deg W_{k} over \overline{𝔎}, so their degree is at most deg W_{k}.

The polynomials in R are in \overline{K}(P)[U], but we need equalities involving polynomials in \overline{K}[P][U]. Let thus 𝔔_{k}, 𝔙_{1}, …, 𝔙_{k} be the polynomials Q_{k}, V_{1}, …, V_{k} multiplied by the LCM of the denominators of their coefficients. These polynomials satisfy the same properties as Q_{k}, V_{1}, …, V_{k}. In particular, for i ≤ k, there exist S_{0,i}, …, S_{k−1,i} in \overline{K}(P)[X_{≤k}] such that the following equality holds in \overline{K}(P)[X_{≤k}]:

T_{i} = S_{0,i}𝔔_{k}(𝔘) + ∑_{j=1}^{k−1} S_{j,i}(𝔔′_{k}(𝔘)X_{i} − 𝔙_{i}(𝔘))  (1)

Let us fix i, and apply Proposition 4. Our conventions on the elements of a triangular set show that the degree of T_{i} in X_{≤k} is at most deg W_{k}. Proposition 4 then shows that the degree in X_{≤k} of each summand in (1) can be taken at most 2k^{2}(deg W_{k})^{2} + (deg W_{k})^{2} = (2k^{2} + 1)(deg W_{k})^{2}.

The conclusion is now similar to that of Gallo and Mishra [1990]. Writing T_{i} = X_{i}^{d_{i}} + R_{i}, with deg_{X_{j}} R_{j} < d_{j} for all j ≤ i, identity (1) can be rewritten

X_{i}^{d_{i}} = −R_{i} + S_{0,i}𝔔_{k}(𝔘) + ∑_{j=1}^{k−1} S_{j,i}(𝔔′_{k}(𝔘)X_{i} − 𝔙_{i}(𝔘)).

This can be rewritten as a linear system in the coefficients of R_{i}, S_{0,i}, …, S_{k−1,i}.

Let G be the number of monomials in k variables of degree at most (2k^{2} + 1)(deg W_{k})^{2}, and G′ ≤ G the number of unknown coefficients in R_{i}. Then we write the system Mu = v, where u is the vector of the kG + G′ unknown coefficients of R_{i}, S_{0,i}, …, S_{k−1,i} and v is the zero vector, except for one entry equal to 1, corresponding to the coefficient of X_{i}^{d_{i}}. The matrix M has G rows and kG + G′ columns, and its entries are either the constant 1, or the coefficients of 𝔔_{k}, 𝔔′_{k}, 𝔙_{1}, …, 𝔙_{n}. These are polynomials in P of degree at most deg W_{k}, by Proposition 1.

The coefficients of R_{i} are uniquely determined, due to our degree constraints for a triangular set. Consequently, by Rouché-Fontené’s Theorem, these coefficients can be expressed as quotients of determinants of size at most G, with entries that are polynomials in P of degree at most deg W_{k}. Then their numerators and denominators have degree at most G deg W_{k}.

This concludes the proof of Theorem 1: since G is bounded from above by ((2k^{2} + 1)(deg W_{k})^{2} + 1)^{k}, G deg W_{k} is bounded by (2k^{2} + 2)^{k}(deg W_{k})^{2k+1}. □

5 Preliminaries for Theorem 2

This section is devoted to present intermediate results that are used in Section 6 for proving Theorem 2; they are independent of our general discussion on the variety W and its generic solutions. In Subsection 5.1, we discuss a notion of specialization of a Greatest Common Divisor defined modulo a triangular set in \overline{K}(P)[X]. In Subsection 5.2, we define the operations of splitting and recombining triangular sets, following [Lazard, 1992].

5.1 Specializing Greatest Common Divisors

Let T = (T_{1}, …, T_{n}) be a triangular set in \overline{K}(P)[X]; we let B be the quotient \overline{K}(P)[X]/T and suppose that B is a field. Thus, the notion of GCD of two polynomials in B[U] is well-defined; we now inspect its specialization properties.

Let thus p be a point in 𝔸^{m}(\overline{K}) which cancels no denominator in the coefficients of T. We denote by t the polynomials T, where all coefficients are specialized at p, and let 𝔟 be the quotient \overline{K}[X]/t. We suppose that t defines a radical ideal, so 𝔟 is the product of fields 𝔟 ≃ \overline{K}^{D}, for some integer D.

The following proposition exhibits conditions under which the GCD of two polynomials in B[U] specializes well. Since 𝔟 is the product of fields \overline{K}^{D}, we denote by ψ_{ℓ} the ℓ-th coordinate map 𝔟 → \overline{K}, for ℓ ≤ D; it extends to a map 𝔟[U] → \overline{K}[U].

Proposition 5 Let F, G be polynomials in B[U], with G monic, and H ∈ B[U] their monic GCD. Suppose that p ∈ 𝔸^{m}(\overline{K}) cancels no denominator in the coefficients of F, G. Denote by f, g in 𝔟[U] the polynomials F, G with coefficients specialized at p. Then:

(1) p cancels none of the denominators of the coefficients of H; h then denotes the polynomial H with all coefficients specialized at p.

(2) For ℓ ≤ D, the degree of gcd(ψ_{ℓ}(f), ψ_{ℓ}(g)) is at least the degree of H.

Suppose that for ℓ ≤ D, the degree of gcd(ψ_{ℓ}(f), ψ_{ℓ}(g)) is the degree of H. Then:

3. For ℓ ≤ D, ψ_{ℓ}(h) equals gcd(ψ_{ℓ}(f), ψ_{ℓ}(g)).

4. Let Q, R in B[U] be the cofactors for the Bézout equality QF + RG = H. Then p cancels none of the denominators of the coefficients of Q, R. Let q, r in 𝔟[U] denote these polynomials with coefficients specialized at p. Then for ℓ ≤ D, ψ_{ℓ}(q), ψ_{ℓ}(r) are the cofactors for the Bézout equality of ψ_{ℓ}(f), ψ_{ℓ}(g).

Proof. We use a classical local-global argument; thus, we suppose without loss of generality that p = 0, and proceed to work in the power series ring \overline{K}[[P]] and its fraction field \overline{K}((P)) instead of the rational function field \overline{K}(P). We let S denote the reduction modulo the maximal ideal of \overline{K}[[P]]; S extends to specialization maps \overline{K}[[P]][U] → \overline{K}[U] and \overline{K}[[P]]^{n} → \overline{K}^{n}.

We use below Theorems 6.26 and 6.55 from von zur Gathen and Gerhard [1999] in the ring \overline{K}[[P]][U]. These results are stated for a prime ideal in an Euclidean base ring, but they extend verbatim to the UFD \overline{K}[[P]] and its maximal ideal. We start by proving two auxiliary results.

Lifting the coordinate functions. Let x^{1}, …, x^{D} be the D distinct roots of t in \overline{K}^{n}. Then for ℓ ≤ D, the polynomials ψ_{ℓ}(f), ψ_{ℓ}(g) are obtained by specializing P at 0 and X at x^{ℓ} in F, G. Using the points x^{ℓ}, we proceed to lift the splitting of 𝔟 into a splitting of B.

By assumption, none of the denominators in T vanishes at zero, so we denote by \overline{T} the image of these polynomials in \overline{K}[[P]][X]. Since 𝔟 is a product of field extensions and \overline{K} is algebraically closed, we deduce that the jacobian determinant of t is invertible in 𝔟, so Hensel’s Lemma applies. We obtain the existence of X^{1}, …, X^{D} in \overline{K}[[P]]^{n} that cancel \overline{T}, and such that S(X^{ℓ}) = x^{ℓ} for ℓ ≤ D.

Enumeration shows that these are all the roots of \overline{T} in an algebraic closure of \overline{K}((P)), thus \overline{K}((P))[X]/\overline{T} is the product of D copies of \overline{K}((P)). For ℓ ≤ D, let Ψ_{ℓ} be the field embedding B → \overline{K}((P)) that maps (X mod T) to X^{ℓ}. It extends to a map B[U] → \overline{K}((P))[U].

An interpolation result. Let z be in B. Let us suppose that all values Ψ_{ℓ}(z) are in the subring \overline{K}[[P]] of \overline{K}((P)). We now prove that no coefficient of z on the canonical basis of B vanishes at zero; this result is used twice below.

The coefficients of z are obtained as follows. We denote by z = [z_{1}, …, z_{D}]^{t} the column vector of the coordinates of z in the canonical basis, and Ψ(z) the column vector [Ψ_{1}(z), …, Ψ_{D}(z)]. Then these vectors are related by the relation Vz = Ψ(z), where we now describe the matrix V.

The matrix V is a generalized Vandermonde Matrix associated to X^{1}, …, X^{D}, see Mourrain and Ruatta [2002]. Its entries are the values taken by X^{1}, …, X^{D} on all monomials of the canonical basis; thus its determinant is in \overline{K}[[P]]. Since the entries of Ψ(z) are in \overline{K}[[P]], it is enough to prove that the constant term of det(V) is non zero to conclude. This term is the determinant of the analogous Vandermonde matrix associated to the points x^{1}, …, x^{D} in \overline{K}^{n}. But by Proposition 4.6 in Mourrain and Ruatta [2002], this determinant is not zero, q.e.d.

Concluding the proof. For ℓ ≤ D, Ψ_{ℓ}(H) is gcd(Ψ_{ℓ}(F), Ψ_{ℓ}(G)), since Ψ_{ℓ} embeds B into \overline{K}((P)). Our assumptions on F, G show that Ψ_{ℓ}(F) and Ψ_{ℓ}(G) are in the subring \overline{K}[[P]][U] of \overline{K}((P))[U], thus so is their monic GCD. Using the above interpolation result, this proves the first statement of the proposition.

By construction, S(Ψ_{ℓ}(F)) = ψ_{ℓ}(f) and S(Ψ_{ℓ}(G)) = ψ_{ℓ}(g). Since Ψ_{ℓ}(G) is monic, Theorem 6.26 in von zur Gathen and Gerhard [1999] shows that the degree of gcd(ψ_{ℓ}(f), ψ_{ℓ}(g)) is at least the degree of gcd(Ψ_{ℓ}(F), Ψ_{ℓ}(G)) = deg H. This proves the second statement.

We suppose now that gcd(ψ_{ℓ}(f), ψ_{ℓ}(g)) has degree d for all ℓ. Using again Theorem 6.26 in von zur Gathen and Gerhard [1999], we see that gcd(ψ_{ℓ}(f), ψ_{ℓ}(g)) is the specialization S(Ψ_{ℓ}(H)). Since none of the coefficients of H vanishes at zero, this can be obtained by first letting P = 0 in H, then evaluating at x^{ℓ}. This is our third statement.

Finally, for ℓ ≤ D, the equality Ψ_{ℓ}(Q)Ψ_{ℓ}(F)+Ψ_{ℓ}(R)Ψ_{ℓ}(G) = Ψ_{ℓ}(H) holds. Using our assumption on the degree of gcd(ψ_{ℓ}(f), ψ_{ℓ}(g)), Theorem 6.55 in von zur Gathen and Gerhard [1999] shows that Ψ_{ℓ}(Q), Ψ_{ℓ}(R) are in \overline{K}[[P]][U], and that their images by S are the cofactors for the Bézout equality of ψ_{ℓ}(f), ψ_{ℓ}(g). Applying again the above interpolation result concludes the proof. □

5.2 Splitting and Combining Triangular Sets

Our second, and last, intermediate result presents the basic ways of splitting and combining triangular sets. The first paragraph closely follows [Lazard, 1992], and we give it again for completeness. In a second time, as a corollary of Proposition 5, we show how to specialize the process of combining two triangular sets; this result is used in Subsection 6.3. In the sequel, superscripts do not indicate powers.

The general case. Let 𝔎 be a field, X = X_{1}, …, X_{n} and T a triangular set in 𝔎[X]. Let us fix k ≤ n and suppose that B_{k} = 𝔎[X_{≤k}]/T_{≤k} is a field. We now define the splitting of T as a family of triangular sets T^{1}, …, T^{J} in 𝔎[X]; it is denoted by Split(T).

Let us write T_{k+1} = Π_{j=1}^{J}T_{k+1,j} the factorization of T_{k+1} into irreducibles in the polynomial ring B_{k}[X_{k+1}] (with repetitions allowed). We can then define T^{j}, for j ≤ J. For i ≤ k, we take T_{i}^{j} = T_{i}. For index k + 1, we take T_{k+1}^{j} = T_{k+1,j}. For i > k + 1, we define T_{i}^{j} as T_{i} with coefficients reduced modulo T_{k+1,j}.

In the converse direction, let T^{1} and T^{2} be two triangular sets in 𝔎[X], and suppose that there exists k ≤ n such that:

• T_{≤k}^{1} = T_{≤k}^{2} and B_{k} = 𝔎[X_{≤k}]/T_{≤k}^{1} is a field;

• T_{k+1}^{1} and T_{k+1}^{2} are coprime in B_{k}[X_{k+1}];

• for i > k + 1, T_{i}^{1} and T_{i}^{2} have the same degree in the variable X_{i} (recall that they are monic in X_{i} by definition).

Then we say that T^{1} and T^{2} can be combined. We define their combination, the triangular set T, as follows: T_{i} = T_{i}^{1} = T_{i}^{2} for i ≤ k and T_{k+1} = T_{k+1}^{1}T_{k+1}^{2}. For i > k+1, we now define T_{i} using an explicit form of the Chinese Remainder Theorem.

Let us consider T_{i}^{1} and T_{i}^{2} as multivariate polynomials in X_{k+2}, …, X_{n} with coefficients in B_{k}[X_{k+1}]. With this point of view, let M be any monomial in X_{k+2}, …, X_{n} and c_{1} and c_{2} its coefficients in respectively T_{i}^{1} and T_{i}^{2}. Let U_{1}, U_{2} be the Bézout coefficients, so that U_{1}T_{k+1}^{1} +U_{2}T_{k+1}^{2} = 1. Then we define c(M) = c_{2}U_{1}T_{k+1}^{1} + c_{1}U_{2}T_{k+1}^{2} and T_{i} is the sum of the terms c(M)M, taken for all monomials M.

Under the above assumptions, T is a triangular set: for i > k + 1, the polynomials T_{i}^{1} and T_{i}^{2} have the same degree in X_{i} and are monic in X_{i}, so that T_{i} is monic in X_{i} as well (for i ≤ k + 1, this is obviously also the case). The ideal generated by T is the sum of those defined by T^{1} and T^{2}; splitting T gives back T^{1} and T^{2}.

Application to parametric situations. We now consider the particular case 𝔎 = \overline{K}(P). Let T^{1}, T^{2} be triangular sets in \overline{K}(P)[X] and suppose that T^{1}, T^{2} can be combined, for some k ≤ n. Let T be their combination, as defined above. Let p be in 𝔸^{m}(\overline{K}), which cancels no denominator in the coefficients of T^{1}, T^{2}, and denote t^{1}, t^{2} these triangular sets with coefficients specialized at p.

The next proposition shows how the recombination can be specialized at the point p; we will use it in Subsection 6.3. The proof is a direct consequence of point 4 in Proposition 5, and the definition of T given in the previous paragraph.

Proposition 6 Assume that the triangular sets t_{≤k+1}^{1} and t_{≤k+1}^{2} define radical ideals in \overline{K}[X_{≤k+1}] with no common solution. Then p cancels none of the denominators of the coefficients of T. If t denotes the triangular set T with all coefficients specialized at p, then t generates the sum of the ideals generated by t^{1}, t^{2}, so in particular it generates a radical ideal.

6 Specialization Properties: Proof of Theorem 2

We now return to our original complexity questions: we consider again the variety W, that satisfies Assumption 1, and suppose that its generic solutions are represented by a triangular set T = (T_{1}, …, T_{n}). We now consider bounding the degree of a degeneracy hypersurface associated to T:

There exists a polynomial Δ_{W} ∈ \overline{K}[P] of degree at most (3n deg W +n^{2}) deg W such that, if p ∈ 𝔸^{m}(\overline{K}) does not cancel Δ_{W}:

(1) p cancels no denominator in the coefficients of (T_{1}, …, T_{n}). We denote by (t_{1}, …, t_{n}) these polynomials with coefficients specialized at p.

(2) (t_{1}, …, t_{n}) is a radical ideal. Let Z_{n} ⊂ 𝔸^{n}(\overline{K}) be the zero-set of the polynomials (t_{1}, …, t_{n}); then W_{n}(p) equals \{p\} × Z_{n} ⊂ 𝔸^{m+n}(\overline{K}).

The proof consists in specializing all steps of a conversion algorithm from a geometric resolution to a triangular set. In Subsection 6.1, we give such an algorithm, which computes the triangular set T from a parametric resolution associated to W. The algorithm works over the base field \overline{K}(P), and applies when W is irreducible. In Subsection 6.2, we show how to specialize all steps of this algorithm at a point p in 𝔸^{m}(\overline{K}), under suitable geometric conditions. In Subsection 6.3, we drop the irreducibility assumption and quantify the geometric conditions, giving the proof of Theorem 2.

6.1 A Conversion Algorithm

Let J the ideal defining W, and J_{P} its extension in \overline{K}(P)[X]. By assumption, J_{P} is generated by the triangular set T. Let B_{n} be the quotient \overline{K}(P)[X]/T. As described in Section 2, for k ≤ n, we define the quotient B_{k} as \overline{K}(P)[X_{≤k}]/T_{≤k} and denote by D_{k} its dimension. We suppose that W is irreducible, so the field extensions \overline{K}(P) → B_{n} is separable, by Assumption 1, thus so are all intermediate extensions.

Propositions 1 and 2 show that \overline{K}(P) → B_{n} admits the parametric resolution Q(𝔘) = 0 and X_{1} = W_{1}(𝔘), …, X_{n} = W_{n}(𝔘), where 𝔘 is a linear combination of the variables X; we now show how to compute the triangular set T starting from Q, W_{1}, …, W_{n}. Consider the following sequence:

(1) Initialization: let A_{0} = \overline{K}(P), R_{0} = Q, S_{0} = 0.

(2) Loop: for k in 1, …, n do • Let S_{k} = MinimalPolynomial(W_{k}) in A_{k−1}[U]/R_{k−1}(U).

• Let A_{k} = A_{k−1}[X_{k}]/S_{k}(X_{k}), and x_{k} the image of X_{k} in A_{k}.

• Let R_{k} = gcd(x_{k} − W_{k}(U), R_{k−1}(U)) in A_{k}[U].

Proposition 7 shows that this algorithm computes the polynomials T_{k}. Actually, we must take into account the polynomials R_{k} as well; for consistency we also take T_{0} = 0 and B_{0} = \overline{K}(P).

Proposition 7 For k = 0, …, n, the following holds:

(1) S_{k} = T_{k}, so that A_{k} coincides with the quotient B_{k} defined above.

(2) R_{k} is the minimal polynomial of 𝔘 over the subfield B_{k} of B_{n}, so B_{n} = B_{k}[U]/R_{k}(U).

Proof. Let us denote by P_{k} the above assertions. Their validity for k = 0 is immediate. For k = 1, …, n, we prove that P_{k−1} implies P_{k}. This is an immediate consequence of the following lemma.

Lemma 1 Let A → B be a separable field extension, such that B = A[U]/R, with R irreducible, and denote by u the image of U in B. Let W be in A[U], x = W (u) in B and P the minimal polynomial of x over A. Let C = A[X]/P be the subfield A(x) ⊂ B. Then the minimal polynomial of u over C is the GCD of R(U) and W (U) − x in C[U].

Proof. Let S ∈ C[U] be the minimal polynomial of u over C. Since R(u) = 0, S divides R. Similarly, since x = W (u), S divides W − x, so S divides the GCD of (R, W − x) in C[U]. To conclude, it is enough to show that S and gcd(R, W −x) have the same degree. From the field inclusions A → C → B, we deduce that the degree of S is deg R/ deg P. Let us prove that gcd(R, W − x) has degree deg R/ deg P too.

Let χ be the characteristic polynomial of W in B; since P is irreducible, χ is a power of P. We consider an algebraic closure \overline{A} of A and write the factorizations in \overline{A}[U]:

R = ∏_{k=1}^{deg R}(U − u_{k}), χ = ∏_{k=1}^{deg R}(X − W (u_{k})), P = ∏_{j=1}^{deg P}(X − w_{j}).

Then all w_{j} are distinct since B is separable, so for j in 1, …, deg P, there are precisely deg R/ deg P roots u_{k} of R such that W (u_{k}) = w_{j}. Let now \overline{C} be the quotient \overline{A}[X]/P. Then \overline{C} is not a field, but a product of fields Π_{j=1}^{deg P} C_{j}. All C_{j} are isomorphic to \overline{A}, and the image of X in C_{j} is w_{j}.

Let us embed C = A[X]/P into one of these fields, for instance C_{1}. Then the GCD of R and W − x has the same degree when it is considered in C[U] or C_{1}[U], and we conclude the proof by estimating its degree in C_{1}[U]. Indeed, the degree of gcd(R, W −x) in C_{1}[U] is the number of roots u_{k} of R, such that W (u_{k}) = w_{1}. By the remarks above, this number is deg R/ deg P. □

We can then prove Proposition 7. Assuming P_{k−1}, we see that A_{k−1} is the subfield B_{k−1} = \overline{K}(P)(x_{1}, …, x_{k−1}), and that B_{n} is B_{k−1}[U]/R_{k−1}(U). Thus the minimal polynomial of W_{k} in B_{k−1}[U]/R_{k−1}(U) is indeed T_{k}; this prove point 1 for P_{k}. Applying the above lemma concludes the proof, taking B_{k−1} → B_{k} → B_{n} for the fields A → C → B mentioned in the lemma. □

6.2 Step-by-step Specialization of the Algorithm

Let p be in 𝔸^{m}(\overline{K}). We now prove that each step of the previous algorithm can be specialized at p: under suitable geometric conditions, none of the denominators that appear vanishes at p, and specializing the variables P at p gives the requested output. We refer to Section 2 for the definition of the notation used here, notably of the projections μ_{k}.

Proposition 8 Assume that p ∈ 𝔸^{m}(\overline{K}) is such that:

(1) p cancels no denominator in the coefficients of Q, W_{1}, …, W_{n}. We denote by q, w_{1}, …, w_{n} the polynomials of \overline{K}[U] obtained by specializing all coefficients in Q, W_{1}, …, W_{n} at p.

(2) For k ≤ n, the fiber W_{k}(p) has D_{k} points.

(3) The polynomials q, w_{1}, …, w_{n} form a geometric resolution for the fiber W_{n}(p).

(4) For k ≤ n, W_{k}(p) coincides with the projection μ_{k} (W_{n}(p)).

Then p cancels no denominator in (T_{1}, …, T_{n}). Denote by (t_{1}, …, t_{n}) the polynomials (T_{1}, …, T_{n}) with coefficients specialized at p. Then (t_{1}, …, t_{n}) is a radical ideal. Let Z_{n} ⊂ 𝔸^{n}(\overline{K}) be the zero-set of (t_{1}, …, t_{n}); then W_{n}(p) equals {p} × Z_{n}.

Proof. Let us first recall how the polynomials T = (T_{1}, …, T_{n}) are obtained. Let B_{0} = \overline{K}(P) and R_{0} = Q. Then, using Proposition 7, for k ≤ n, T_{k}, B_{k}, R_{k} are defined as follows:

• T_{k} is the minimal polynomial of W_{k} in B_{k−1}[U]/R_{k−1}(U);

• B_{k} is the quotient field B_{k−1}[X_{k}]/T_{k}(X_{k});

• R_{k} is the GCD of x_{k} − W_{k}(U) and R_{k−1}(U) in B_{k}[U].

We now prove that each step of this algorithm can be specialized at p, in a suitable sense: for k in 1, …, n, all coefficients in T_{1}, …, T_{k}, R_{k} will be specialized at p, which will define a quotient 𝔟_{k} analogous to B_{k}. The quotient 𝔟_{k} will not be a field; hence, some care is needed as to giving a precise meaning to notions such as minimal polynomial or GCD over 𝔟_{k}.

More precisely, we prove the following properties by induction. Properties 𝔄_{n} and 𝔅_{n} are enough to prove the proposition, but we actually need to handle the last property to make the recursion work. In the sequel, superscripts do not indicate powers.

𝔄_{k} : p cancels no denominator in the coefficients of T_{1}, …, T_{k}; then t_{1}, …, t_{k}

denote these polynomials with coefficients specialized at p. 𝔅_{k} : The ideal (t_{1}, …, t_{k}) of \overline{K}[X_{≤k}] is radical. Let Z_{k} ⊂ 𝔸^{k}(\overline{K}) be its zeroset; then W_{k}(p) coincides with {p} × Z_{k}.

We let 𝔟_{k} be the quotient \overline{K}[X_{≤k}]/(t_{1}, …, t_{k}). Then 𝔟_{k} is the product of D_{k} copies of \overline{K}, by Hypothesis 2. For j ≤ D_{k}, we denote by ϕ_{j} the j-th coordinate function 𝔟_{k} → \overline{K}. This function maps X_{1}, …, X_{k} to some values x_{1}^{(j)}, …, x_{k}^{(j)}, and we denote by p_{k}^{(j)} the point of W_{k}(p) with coordinates (p, x_{1}^{(j)}, …, x_{k}^{(j)}). The map ϕ_{j} also extends to a map between polynomial rings 𝔟_{k}[U] → \overline{K}[U].

ℭ_{k} : p cancels no denominator in the coefficients of R_{k}. We let r_{k} ∈ 𝔟_{k}[U] denote this polynomial with coefficients specialized at p, and for j ≤ D_{k}, let r_{k,j} be ϕ_{j}(r_{k}) in \overline{K}[U]. Then r_{k,j} is Π(U − 𝔘(p)), the product being taken on all points p in W_{n}(p) such that μ_{k}(p) = p_{k}^{(j)}.

The validity for k = 0 is obvious; we now suppose that 𝔄_{k−1}, 𝔅_{k−1}, ℭ_{k−1} are satisfied, and prove their validity at step k. By assumption, we come equipped with a quotient 𝔟_{k−1} = \overline{K}[X_{≤k−1}]/(t_{1}, …, t_{k−1}), which is a product of D_{k−1} copies of \overline{K}. For j ≤ D_{k−1}, we denote by ϕ_{j} the j-th coordinate map 𝔟_{k−1} → \overline{K} and its extension 𝔟_{k−1}[U] → \overline{K}[U].

Proof of 𝔄_{k}. Let χ be the characteristic polynomial of W_{k} in the quotient B_{k−1}[U]/R_{k−1}(U). Our hypotheses show that p cancels no denominator in the coefficients of χ. Since χ is a power of the minimal polynomial T_{k} of W_{k}, p cancels no denominator in the coefficients of T_{k}. This proves 𝔄_{k}; we let t_{k} ∈ 𝔟_{k−1}[U] be the polynomial T_{k} with all coefficients specialized at p.

Proof of 𝔅_{k}. By definition, R_{k−1} divides T_{k}(W_{k}) in B_{k−1}[U]. Let S ∈ B_{k−1}[U] be the quotient, satisfying the equality T_{k}(W_{k}) = R_{k−1}S. Then p cancels no denominator in the coefficients of S, and we let s be S with coefficients specialized at p. Then the equality t_{k}(w_{k}) = r_{k−1}s holds in 𝔟_{k−1}[U]. For j ≤ D_{k−1}, let t_{k,j}, w_{k,j}, s_{j} in \overline{K}[U] be the images of t_{k}, w_{k}, s by ϕ_{j}. The relation t_{k,j}(w_{k,j}) = r_{k−1,j}s_{j} shows that all roots of r_{k−1,j} cancel t_{k,j}(w_{k,j}).

Let Z_{k} ⊂ 𝔸^{k}(\overline{K}) be the zero-set of (t_{1}, …, t_{k}). We first prove that \{p\} × Z_{k} contains the fiber W_{k}(p). Let p_{k} = (p, x_{1}, …, x_{k}) be a point in W_{k}(p); we thus want to prove that (t_{1}, …, t_{k}) vanish at (x_{1}, …, x_{k}).

By Hypothesis 4, there exist p in W_{n}(p) such that μ_{k}(p) = p_{k}. Since μ_{k−1}(p) is in W_{k−1}(p), there exists j ≤ D_{k−1} such that (x_{1}, …, x_{k−1}) = (x_{1}^{(j)}, …, x_{k−1}^{(j)}). In particular, (x_{1}, …, x_{k−1}) cancel (t_{1}, …, t_{k−1}). By Hypothesis 3, w_{k} (𝔘(p)) equals x_{k}. Then by property ℭ_{k−1}, r_{k−1,j} vanishes at 𝔘(p), so by the above discussion, t_{k,j} vanishes at x_{k}. Thus {p} × Z_{k} contains W_{k}(p).

We finally prove that these sets coincide. For j ≤ k, t_{j} has the same degree as T_{j}, so the quotient \overline{K}[X_{≤k}]/(t_{1}, …, t_{k}) has the same dimension as the quotient \overline{K}(P)[X_{≤k}]/(T_{1}, …, T_{k}). This dimension is D_{k}, so it equals the cardinality of W_{k}(p) by Hypothesis 2. We deduce that {p}×Z_{k} equals W_{k}(p) and (t_{1}, …, t_{k}) is radical. This proves 𝔅_{k}.

Setting up the new quotient. Let 𝔟_{k} be the quotient

𝔟_{k} = \overline{K}[X_{1}, …, X_{k}]/(t_{1}, …, t_{k}) = 𝔟_{k−1}[X_{k}]/t_{k} ≃ \overline{K}^{D_{k}}.

For ℓ ≤ D_{k}, let us denote by ψ_{ℓ} the ℓ-th coordinate function 𝔟_{k} → \overline{K}. This function maps X_{1}, …, X_{k} to some values x_{1}^{(ℓ)}, …, x_{k}^{(ℓ)}, such that the coordinates of the corresponding point in W_{k}(p) are (p, x_{1}^{(ℓ)}, …, x_{k}^{(ℓ)}). It extends to a map 𝔟_{k}[U] → \overline{K}[U]. From now on we consider the polynomial r_{k−1} in 𝔟_{k}[U], and its images r_{k−1,ℓ} = ψ_{ℓ}(r_{k−1}) in \overline{K}[U]. Similar notations hold for w_{k} and w_{k,ℓ}.

Proof of ℭ_{k}. We now turn to the last step, the specialization of the GCD computation. Let ℓ ≤ D_{k} and (p, x_{1}^{(ℓ)}, …, x_{k}^{(ℓ)}) the coordinates of the corresponding point in W_{k}(p). The definition of r_{k−1} shows that r_{k−1,ℓ} factors as the product Π(U −𝔘(p)), taken on all points in W_{n}(p) whose first coordinates are (p, x_{1}^{(ℓ)}, …, x_{k−1}^{(ℓ)}). Let r_{k,ℓ} be the GCD of w_{k,ℓ}(U) − x_{k}^{(ℓ)} and r_{k−1,ℓ}(U). Then r_{k,ℓ} is the product Π(U − 𝔘(p)), taken on all points p in W_{n}(p) such that μ_{k}(p) = (p, x_{1}^{(ℓ)}, …, x_{k}^{(ℓ)}).

We apply Proposition 5, that describes the specialization properties of GCD’s. The first part of the proposition shows that for all ℓ, the degree of r_{k,ℓ} is at least the degree of R_{k}. We now proceed to prove that these degrees are actually equal.

Using the above characterization, the product of the polynomials r_{k,ℓ} for ℓ ≤ D_{k} is Π(U −𝔘(p)), taken on all points in W_{n}(p). By hypothesis 2, it has degree D_{n}. On the other hand, since there are D_{k} polynomials r_{k,ℓ}, their product has degree at least D_{k} deg R_{k} by the previous reasoning, with equality if and only if they all have degree deg R_{k}. But the definition of D_{k} and R_{k} shows that D_{k} deg R_{k} = D_{n}. Thus all polynomials r_{k,ℓ} necessarily have degree deg R_{k}.

We can then apply the first and third points of Proposition 5: p cancels no denominator in R_{k}; if r_{k} denotes this polynomial with all coefficients specialized at p, then ψ_{ℓ}(r_{k}) = r_{k,ℓ}. This is precisely the content of assertion ℭ_{k}. □

6.3 Dropping the Irreducibility Condition

Up to now, we assumed that W was irreducible. We now drop this assumption, and prove Theorem 2:

There exists a polynomial Δ_{W} ∈ \overline{K}[P] of degree at most (3n deg W +n^{2}) deg W such that, if p ∈ 𝔸^{m}(\overline{K}) does not cancel Δ_{W}:

(1) p cancels no denominator in the coefficients of (T_{1}, …, T_{n}). We denote by (t_{1}, …, t_{n}) these polynomials with coefficients specialized at p.

(2) (t_{1}, …, t_{n}) is a radical ideal. Let Z_{n} ⊂ 𝔸^{n}(\overline{K}) be the zero-set of the polynomials (t_{1}, …, t_{n}); then W_{n}(p) equals \{p\} × Z_{n} ⊂ 𝔸^{m+n}(\overline{K}).

The proof relies on Proposition 9 below. The fact that W is not irreducible anymore requires further work, and the introduction of new objects associated to W and its irreducible components.

• Recall that the generic solutions of W are represented by the triangular set T in \overline{K}(P)[X].

• We write W = ∪_{j≤J}W^{j}, where W^{j} is irreducible, and for j ≤ J, let T^{j} be the triangular set in \overline{K}(P)[X] that represents the generic solutions of W^{j}.

• For k ≤ n and j ≤ J, we denote by W_{k}^{j} the closure of μ_{k}(W_{k}). Not all W_{k}^{j} may be distinct; we let J_{k} ≤ J be the number of distinct varieties among them. We suppose without loss of generality that W_{k}^{1}, …, W_{k}^{J_{k}} are a system of representatives of the distinct varieties among W_{k}^{1}, …, W_{k}^{J}.

• For p in 𝔸^{m}(\overline{K}) and j ≤ J, we define W_{k}^{j}(p) as the fiber π_{k}^{−1}(p) ∩ W_{k}^{j}.

Proposition 9 Assume that p ∈ 𝔸^{m}(\overline{K}) is such that:

(1) For k ≤ n, and j, j′ ≤ J_{k} with j ≠ j′, W_{k}^{j}(p) ∩ W_{k}^{j′}(p) is empty.

(2) p satisfies the assumptions of Proposition 8 for all varieties W^{j}, j ≤ J.

Then p cancels no denominator in the coefficients of (T_{1}, …, T_{n}). Denote by (t_{1}, …, t_{n}) these polynomials with coefficients specialized at p. Then the ideal (t_{1}, …, t_{n}) is a radical ideal. If Z_{n} ⊂ 𝔸^{n}(\overline{K}) denotes its zero-set, W_{n}(p) equals {p} × Z_{n}.

Before proving the proposition, we deduce the proof of Theorem 2; this simply amounts to quantify all conditions given in the proposition.

• For k ≤ n and j, j′ ≤ J_{k}, with j ≠ j′, Hypothesis 1 is satisfied if p avoids a hypersurface of degree at most deg W_{k}^{j} deg W_{k}^{j′}. Taking all k, j, j′ into account, we bound the sum of these degrees by n(deg W)^{2}.

• For j ≤ J, using Propositions 2 and 8, Hypothesis 2 is satisfied when p avoids a hypersurface of degree at most (2n deg W^{j} + n^{2}) deg W^{j}. The sum

of these degrees is bounded by (2n deg W + n^{2}) deg W.

This concludes the proof of Theorem 2. Thus, we can concentrate on proving Proposition 9 above. We use the notions of splitting and combining triangular sets, introduced in Subsection 5.2.

Starting from T, the following process computes the family {T^{1}, …, T^{J}}. Let F_{0} be {T}. For k = 1, …, n, we define inductively the families of triangular sets F_{k} as follows: F_{k} is the reunion of the families Split(S), for S in F_{k−1}. Note that at step k, the splitting is done by factoring the k-th polynomial of each triangular set in S. Then the following property is straightforward to prove for k ≤ n:

F_{k} has precisely J_{k} elements, which we denote by T^{1,k}, …, T^{J_{k},k}. Besides, up to reordering, we can assume that for j ≤ J_{k}, the generic solutions of W_{k}^{j} are represented by the ideal generated by T_{≤k}^{j,k} in \overline{K}(P)[X_{≤k}].

The idea for proving Proposition 9 is to go all the way back from {T^{1}, …, T^{J}} to T, since Proposition 8 will enable to specialize the coefficients of all polynomials in {T^{1}, …, T^{J}}. To this effect, we prove the following properties by decreasing induction on k. Note that properties 𝔄_{0} and 𝔅_{0} do prove Proposition 9.

𝔄_{k} : For j ≤ J_{k}, p cancels no denominator in the coefficients of the polynomials in T^{j,k}. We let t^{j,k} be the polynomials in T^{j,k} with coefficients specialized at p.

𝔅_{k} : Let Z_{k}^{j} be the zero-set of t^{j,k} in 𝔸^{n}(\overline{K}) and Z_{k} their reunion for j =

1, …, J_{k}. Then W_{n}(p) is \{p\} × Z_{k} ⊂ 𝔸^{m+n}(\overline{K}). ℭ_{k} : For j ≠ j′, the ideals generated by t_{≤k}^{j,k} and t_{≤k}^{j′,k} in \overline{K}[X_{≤k}] are radical

and have no common zero.

Let us first take k = n. By Hypothesis 2, we can apply Proposition 8 to the varieties W_{j}, j ≤ J, obtaining properties 𝔄_{n} and 𝔅_{n}. Property ℭ_{n} is then a consequence of Hypothesis 1. Thus, the induction is initiated; let us now assume that 𝔄_{k+1}, 𝔅_{k+1} and ℭ_{k+1} hold, and study step k.

Consider j ≤ J_{k}, and the triangular set T^{j,k} in F_{k}. By definition, the result of Split(T^{j,k}) is a family of triangular sets that all belong to F_{k+1}. Without loss of generality, we assume that these are T^{1,k+1}, …, T^{N,k+1}, for some integer N. Then T^{j,k} is obtained by successively recombining T^{1,k+1}, …, T^{N,k+1} using the Chinese Remainder Theorem, see Subsection 5.2.

By assumption 𝔄_{k+1}, p cancels no denominator in T^{1,k+1}, …, T^{N,k+1}; we denote t^{1,k+1}, …, t^{N,k+1} these triangular sets with coefficients specialized at p. Let us first consider the recombination of t^{1,k+1} and t^{2,k+1}. We have t_{≤k}^{1,k+1} = t_{≤k}^{2,k+1} and by assumption ℭ_{k+1}, t_{≤k+1}^{1,k+1} and t_{≤k+1}^{2,k+1} generate radical ideals with no common zero in \overline{K}[X_{≤k+1}]. Thus we can apply Proposition 6 to recombine them.

Iterating this argument, we see that p cancels no denominator in T^{j,k}, and denote by t^{j,k} its specialization. Then t^{j,k} defines a radical ideal, which is the sum of those generated by t^{1,k+1}, …, t^{N,k+1}.

Taking all j into account, we deduce 𝔄_{k} and 𝔅_{k}. Let us prove ℭ_{k}; for simplicity, we show that t_{≤k}^{1,k} and t_{≤k}^{2,k} are coprime in \overline{K}[X_{≤k}]. We know that T_{≤k}^{1,k} defines the generic solutions of W_{k}^{1}. Since t_{≤k}^{1,k} is the specialization of T_{≤k}^{1,k} at p, it describes the fiber W_{k}^{1}(p). The similar reasoning holds for W_{k}^{2}, so the conclusion follows from Hypothesis 1. □

7 Lifting Techniques

We have now proven our various degree estimates, and turn to algorithmic considerations. Thus, we have to be more specific on the definition of the geometric objects: the input is now a polynomial system F = F_{1}, …, F_{n} in K[P, X]. For complexity statements, we suppose that F is given by a Straight-Line Program of size L, and that d is a bound on the degrees of the polynomials F.

Let W ⊂ 𝔸^{m+n}(\overline{K}) be the zero-set of F. We assume that the jacobian determinant of F with respect to X is invertible on a dense subset of W. Then Lazard’s lemma (see [Boulier et al., 1995, Lemma 2] and [Morrison, 1999, Proposition 3.2]) implies that W satisfies Assumption 1. Thus its generic solutions are represented by a family of triangular sets; in this section, we present some algorithms for computing with these triangular sets.

We first treat the case when W is irreducible; then its generic solutions are represented by a single triangular set T in K(P)[X]. Theorem 3 below gives an algorithm for computing this triangular set by lifting techniques. See the introduction for the genesis of such ideas.

Recall that M(D) denotes the complexity of univariate polynomial multiplication in degree D over any ring and M_{s}(D, M) the complexity of M-variate power series multiplications truncated in total degree D. The constants C_{0}, C_{1} are defined in the introduction; D_{n} is the generic number of solutions of the systems F(p, X), for p in 𝔸^{m}(\overline{K}).

Assume that W is irreducible. Let p, p′ be in K^{m}; assume that a description of the zeros of the systems F(p, X), F(p′, X) by triangular sets is available. For k ≤ n, let 𝔇_{k} be the maximum of the degrees of the coefficients of T_{1}, …, T_{k}.

Then T_{1}, …, T_{k} can be computed within

O_{log} ((nL+n^{3})(C_{0}C_{1})^{n}M(D_{n})M_{s}(4𝔇_{k}, m)+km^{2}D_{n}M(𝔇_{k})M_{s}(4𝔇_{k}, m−1))

operations in K. The algorithm chooses 3m − 1 values in K, including the coordinates of p and p′. If Γ is any subset of K, and these values are chosen in Γ^{3m−1}, then the algorithm fails for at most 50n(k^{2} + 2)^{3k}d^{6kn+4n}|Γ|^{3m−2} choices.

In the general case, we show to recover an eliminating polynomial for the variable X_{1} using these techniques. Precisely, let J be the ideal (F_{1}, …, F_{n}), J_{P} its extension in \overline{K}(P)[X] and B the quotient \overline{K}(P)[X]/J_{P}. Then Theorem 4 addresses the question of computing the minimal polynomial M_{1} of X_{1} in B.

Let p, p′ be in K^{m}; assume that a description of the zeros of the systems F(p, X), F(p′, X) by triangular sets which define prime ideals in K[X] is known. Let 𝔇_{1} be the maximum of the degrees of the coefficients of M_{1}. Then M_{1} can be computed within

O_{log} ((nL + n^{3})(C_{0}C_{1})^{n}M(D_{n})M_{s}(4𝔇_{1}, m) + m^{2}D_{n}M(𝔇_{1})M_{s}(4𝔇_{1}, m − 1))

operations in K. The algorithm chooses 3m − 1 values in K, including the coordinates of p and p′. If Γ is a subset of K, and these values are chosen in Γ^{3m−1}, then the algorithm fails for at most 50nd^{4n}|Γ|^{3m−2} choices.

This section is organized as follows. Some basic algorithms are described in Subsection 7.1. In Subsection 7.2, we treat the irreducible case; the minimal polynomial computation is addressed in Subsection 7.3.

7.1 Sketch of the Algorithms and Additional Subroutines

The algorithms underlying Theorems 3 and 4 can be sketched as follows:

(1) Choose a generic value p in K^{m} and compute a family of triangular sets that represent the solutions of the specialized system F(p, X).

(2) Apply a lifting process, to compute triangular sets with coefficients in the power series ring centered at p.

(3) When the precision of the power series is high enough, use a rational reconstruction process to recover triangular sets with coefficients in K(P).

We now give more details on some of these points: the computation of a triangular set in K[X], the complexity of an operation (+, ×) modulo a triangular set, and the complexity of the rational reconstruction of a rational function.

Initial resolution. The first task is to compute a family of triangular sets r^{1}, …, r^{Q} in K[X] that represent the solutions of the specialized system F(p, X). In Subsection 7.3.2, we also ask that all triangular sets r^{1}, …, r^{Q} define prime ideals in K[X].

This routine is called Solve(F, p). To this effect, we may use zero-dimension-al solving procedures of Lazard [1992], Dellière [1999], Aubry et al. [1999] … Since the complexities of such algorithms are not well known, we do not take the cost of this phase into account in the complexity estimates. Note that the cost of the lifting phase is predominant in practice.

Computing modulo a triangular set. Let T = (T_{1}, …, T_{n}) be a triangular set with coefficients in a ring R. The quotient B := R[X]/T is built as the succession of n monogeneous extensions of R. We use this point of view to estimate the complexity of an operation in B.

With the notation of Section 2, all operations (+, ×) modulo a single polynomial of degree D require at most C_{0}M(D) base ring operations. We deduce that for any triangular set T = (T_{1}, …, T_{n}) in R[X_{1}, …, X_{n}], the operations (+, ×) can be done modulo T in at most C_{0}^{n}Π_{k≤n}M (deg_{X_{k}}T_{k}) operations in R. See also [Langemyr, 1990] for similar considerations.

Rational reconstruction. In the end of the lifting process, we need to recover some rational functions in K(P) = K(P_{1}, …, P_{m}) from their power series expansion. We now present our solution to deal with this question.

If r is a power series in K[[P_{1}, …, P_{m}]] of precision 2D + 1, we look for a rational function p/q, with q(0) ≠ 0 and p, q of degree at most D, of which r is the power series expansion. Finding such a rational function, if it exists, amounts to solve a linear system for the coefficients of p and q. When m = 1, a faster solution exists, based on Padé approximant computations. In [Schost, 2003, Proposition 6], we introduced a probabilistic extension of this algorithm:

Proposition 10 Suppose that there exist (p, q) of degrees at most D, such that r is the Taylor expansion of p/q at precision 2D+1, and q(0) ≠ 0. We can compute p/q by a probabilistic algorithm within O_{log} (m^{2}M(D)M_{s}(2D, m − 1)) operations in K. The algorithm chooses m − 1 values in K. The choices that lead to an error belong to an hypersurface of 𝔸^{m−1}(\overline{K}) of degree at most 2D(2D + 1)^{2}.

7.2 The Irreducible Case

In this subsection, we assume that W is irreducible, so its generic solutions are represented by a triangular set T = (T_{1}, …, T_{n}). For fixed k ≤ n, we now show how to compute (T_{1}, …, T_{k}) by lifting techniques. We first present the elementary lifting step; then we give the full algorithm. The complexity and probability analyses will prove Theorem 3.

7.2.1 The Basic Lifting Step

Let p be a point in the parameter space K^{m}, such that:

H_{1} : The jacobian determinant of F(p, X) with respect to X is invertible on

all solutions of the system F(p, X). H_{2} : p does not cancel the polynomial Δ_{W} defined in Theorem 2.

Up to a change of variables, we can assume that p = 0. Let A be the mvariate power series ring K[[P]] and 𝔪 its maximal ideal. Using Theorem 2, hypothesis H_{2} shows that all coefficients in T admit power series expansions in A; for κ ≥ 0, we denote by T mod 𝔪^{2^{κ}} the triangular set obtained by reducing all coefficients of T modulo 𝔪^{2^{κ}}.

In this paragraph, we show how to compute the sequence T mod 𝔪^{2^{κ}}. The initial value is t = T mod 𝔪, which we assume to know.

By definition of T, there exists a n×n matrix A with entries in K(P)[X] such that F = AT, where T is seen as the column-vector [T_{1}, …, T_{n}]^{t}, and F as [F_{1}, …, F_{n}]^{t}. Since all polynomials in T are monic in their main variable, all denominators in the entries of A admit power series expansions in A. Thus, we can now consider F, T, A with entries in A[X]. Using Theorem 2, we then rephrase hypotheses H_{1} and H_{2} as follows:

H′_{1} : The jacobian determinant of F with respect to X is invertible in K[X]/t. H′_{2} : There exists a n×n matrix A with entries in A[X] such that the equality

F = AT holds.

Our main result is the following proposition. We denote Lift(T, F) the subroutine which performs the underlying computations.

Proposition 11 Suppose that hypotheses H′_{1} and H′_{2} hold for the triangular set T. Let κ > 0, and suppose that T mod 𝔪^{2^{κ}} is known. Then T mod 𝔪^{2^{κ+1}} can be computed within

O ((nL + n^{3})C_{0}^{n}M_{s}(2^{κ+1}, m)Π_{k≤n}M (deg_{X_{k}}T_{k}))

base field operations.

Proof. The proof follows from an explicit formula given in Schost [2003]. Stating this result requires some new notation.

• Let A_{κ} = A/𝔪^{2^{κ+1}} and τ = (τ_{1}, …, τ_{n}) be a triangular set in A_{κ}[X] such that τ = T mod 𝔪^{2^{κ}}. We denote by Q_{κ} the quotient A_{κ}[X]/(τ_{1}, …, τ_{n}).

• Let F_{κ} be the image of F in Q_{κ}[X], Jac(τ) and Jac(F_{κ}) the jacobian matrices of τ and F computed in the matrix algebra over Q_{κ}.

In [Schost, 2003, Proposition 4], we prove the following points. First, Jac(F_{κ}) is invertible in the matrix algebra over Q_{κ}. Let δ = (δ_{1}, …, δ_{n}) be the product Jac(τ)Jac(F_{κ})^{−1}F_{κ} and δ̃ its canonical preimage in A_{κ}[X]. In this situation, T mod 𝔪^{2^{κ+1}} is given by τ + δ̃ in A_{κ}[X].

We now complete the complexity analysis. From the previous subsection, the operations (+, ×) in Q_{κ} require C_{0}^{n}Π_{k≤n}M (deg_{X_{k}}T_{k}) operations in A_{κ}. All operations in A_{κ} require M_{s}(2^{κ+1}, m) base field operations, so the operations (+, ×) in Q_{κ} take C_{0}^{n}M_{s}(2^{κ+1}, m)Π_{k≤n}M (deg_{X_{k}}T_{k}) operations in K.

Let us now estimate how many operations in Q_{κ} are necessary. Algorithm Lift requires to compute F_{κ}, Jac(F_{κ}) and Jac(τ), to invert Jac(F_{κ}) and matrix-vector multiplications. Computing F_{κ} and Jac(F_{κ}) amounts to evaluate the system F and its jacobian in Q_{κ}. Using the algorithm of Baur and Strassen [1983], this takes O(nL) operations in Q_{κ}, where L is the complexity of evaluation of the system F.

The inverse of Jac(F_{κ}) is computed by induction on κ by Hensel’s Lemma. Thus the only inversion is done for κ = 0, and can be done in K[X]/t, according to Proposition 11: all other inverses are obtained by matrix multiplication over Q_{κ} and take O(n^{3}) operations in Q_{κ}. The other costs are negligible before the previous quantities, concluding the complexity analysis. □

7.2.2 Main Algorithm

The main algorithm follows the lines given in Subsection 7.1. We choose a generic point p in K^{m}, so the specialization of T at p gives a description of the solutions of the system F(p, X). We require that Solve(F, p) outputs a single triangular set r, which is thus the specialization of T at p. Then, we apply the above lifting process to r. We use an additional subroutine denoted Stop, which is described below.

Computing a triangular set by lifting techniques Input: The system F, p, p′ in K^{m} Output: The polynomials T_{1}, …, T_{k}. r ← Solve(F, p) r′ ← Solve(F, p′)

       while not(Finished) do

r ← Lift(r, F)

Finished,T_{1}, …, T_{k} ← Stop(r, r′)

       end while

return T_{1}, …, T_{k}

The subroutine Stop first tries to compute a rational reconstruction of all the coefficients in r_{1}, …, r_{k}, yielding polynomials R_{1}, …, R_{k}. Even if the reconstruction is possible, it might not coincide with T_{1}, …, T_{k}, if we have stopped the lifting too early. Thus we use a witness value p′: we compute a description r′ = r′_{1}, …, r′_{n} of the solutions of the system F(p′, X). Stop tests if the specialization of R_{1}, …, R_{k} at p′ is r′_{1}, …, r′_{k}. If the reconstruction is possible and the test is passed, Stop outputs true and R_{1}, …, R_{k}; else it returns false.

Complexity analysis. Let 𝔇_{k} be the maximal degree in P of the coefficients in T_{1}, …, T_{k}. Then the lifting must be run to precision 2^{p+1}, with p = ⌈log_{2}(𝔇_{k})⌉, so that 2^{p+1} ≤ 4𝔇_{k}. From Proposition 11, the cost of the last lifting step is within O ((nL + n^{3})C_{0}^{n}M_{s}(4𝔇_{k}, m)Π_{k≤n}M (deg_{X_{k}}T_{k})) operations in K. We now use our assumptions on the functions M and M_{s} to deduce a simpler estimate on the total cost.

• Since the inequality M(D)M(D′) ≤ C_{1}M(DD′) log(DD′)^{α} holds for all D, D′, Π_{k≤n}M (deg_{X_{k}}T_{k}) is bounded by C_{1}^{n}M(Π_{k≤n}deg_{X_{k}}T_{k}), up to logarithmic factors.

• Since there exists C_{2} < 1 such that M_{s}(D, M) ≤ C_{2}M_{s}(2D, M) holds for all D, M, the whole cost of the lifting is equivalent to the cost of the last step.

Recall that Π_{k≤n}deg_{X_{k}}T_{k} coincides with the generic degree D_{n}; then using the above remarks, the whole cost of the lifting phase is seen to be within O_{log} ((nL + n^{3})(C_{0}C_{1})^{n}M(D_{n})M_{s}(4𝔇_{k}, m)) .

It remains to study the cost of the rational reconstruction. There are at most kD_{n} coefficients to reconstruct. From Proposition 10, each reconstruction costs O_{log} (m^{2}M(𝔇_{k})M_{s}(4𝔇_{k}, m − 1)) operations in K; this concludes the complexity analysis.

Probability analysis. The algorithm chooses 3m−1 values in the base field: the 2m coordinates of the points p and p′, and m − 1 values γ for the rational reconstruction. Suppose that these values are chosen in the box Γ^{3m−1}, where Γ is a given subset of K. We now estimate the number of choices that lead to success, using Zippel-Schwartz’ Lemma from Zippel [1979] and Schwartz [1980].

Recall that this lemma states that given any subset Γ of K, the number of zeros of a ℓ-variate polynomial of degree D in Γ^{ℓ} ⊂ K^{ℓ} is at most D|Γ|^{ℓ−1}.

• Let us first suppose that the point p does not cancel the polynomial Δ_{W} from Theorem 2, and that the jacobian determinant of F is invertible everywhere on the fiber above p. Then by Proposition 11, the lifting can be initiated.

By Theorem 2 and Zippel-Schwartz’s Lemma, the first condition excludes at most (3n(deg W)^{2} + n^{2} deg W)|Γ|^{m−1} values of p, which give rise to (3n(deg W)^{2} + n^{2} deg W)|Γ|^{3m−2} points in Γ^{3m−1}. Similarly, the second condition excludes at most nd deg W|Γ|^{3m−2} points, since the intersection of W with the zero-set of the jacobian determinant has degree at most nd deg W.

• We suppose that p′ does not cancel the polynomial Δ_{W}, so r′ is the specialization of T at p′. As above, this excludes at most (3n(deg W)^{2} + n^{2} deg W)|Γ|^{3m−2} points.

• We then exclude the possibility that the lifting stops too early. This is the case if for some κ < ⌈log_{2}(𝔇_{k})⌉, the reconstruction of all rational functions in r is possible, yielding a triangular set R ≠ T, whose specialization at p′ nevertheless coincides with r′.

Let us fix p. Then the coefficients of T and R are rational functions of degrees at most 𝔇_{k} and 2^{κ−1}, so the points p′ where their specializations coincide are contained in an hypersurface of 𝔸^{m}(\overline{K}) of degree at most 𝔇_{k} + 2^{κ−1}.

Taking all possible κ < ⌈log_{2}(𝔇_{k})⌉ into consideration shows that for fixed p, p′ must avoid an hypersurface in 𝔸^{m}(\overline{K}) of degree at most 𝔇_{k}(⌈log_{2}(2𝔇_{k}+ 1)⌉ + 2), which excludes 𝔇_{k}(⌈log_{2}(2𝔇_{k} + 1)⌉ + 2)|Γ|^{m−1} values of p′. Letting p and γ vary, this removes at most 𝔇_{k}(⌈log_{2}(2𝔇_{k} + 1)⌉ + 2)|Γ|^{3m−2} points in Γ^{3m−1}.

• The algorithm can now only fail at the last rational reconstruction. Let us fix p. By Proposition 10, each rational reconstruction requires to choose m − 1 values outside of an hypersurface of degree at most 4𝔇_{k}(2𝔇_{k} + 1)^{2}. Since there are at most kD_{n} such reconstructions to perform, this discriminates at most 4kD_{n}𝔇_{k}(2𝔇_{k} + 1)^{2}|Γ|^{m−2} values of γ. Letting p and γ vary, this removes at most 4kD_{n}𝔇_{k}(2𝔇_{k} + 1)^{2}|Γ|^{3m−2} points in Γ^{3m−1}.

We sum all these estimates, and use the inequalities D_{n} ≤ deg W ≤ d^{n} and 𝔇_{k} ≤ (2k^{2} + 2)^{k}d^{2kn+n} from Theorem 1. After some rewriting and simplifying, we see that the above restrictions discriminate at most 50n^{3}(k^{2} + 2)^{3k}d^{6kn+4n}|Γ|^{3m−2} points in Γ^{3m−1}. This concludes the probability analysis of Theorem 3.

7.3 Computing a Minimal Polynomial

We now drop the irreducibility assumption made above. Recall that we denote by J the ideal (F_{1}, …, F_{n}) and by J_{P} its extension in \overline{K}(P)[X]. Let M_{1} ∈ K(P)[U] be the minimal polynomial of X_{1} modulo J_{P}. In this subsection, we show how to compute M_{1} by lifting techniques, thus proving Theorem 4.

We first relate this minimal polynomial to triangular sets. Write the decomposition of W = ∪_{j≤J}W^{j}, corresponding to the prime decomposition of J in K[P, X] and let T^{j} be the triangular set that describes the generic solutions of W^{j}, for j ≤ J. The first polynomials T_{1}^{1}, …, T_{1}^{J} may not be all distinct; without loss of generality, we assume that T_{1}^{1}, …, T_{1}^{K} are representatives of the distinct polynomials among them, for some K ≤ J.

By construction, T^{1}, …, T^{K} define prime ideals in K(P)[X], so T_{1}^{1}, …, T_{1}^{K} are irreducible in K(P)[X_{1}]. Since they are pairwise distinct, they are pairwise coprime in both K(P)[X_{1}] and \overline{K}(P)[X_{1}]. We deduce that their product is M_{1}.

Our lifting process does not yield directly the triangular sets T^{j}. Indeed, the input is a resolution of a specialization of F: its irreducible components may not be the traces of those of W, since specialization may induce additional factorizations. Thus, we first address the question of lifting in presence of factorization, and deduce the proof of Theorem 4 in a second time.

7.3.1 Factorized Lifting

We fix some j ≤ J and let T^{j} be the triangular set which describes the generic solutions of W^{j}. Let p be a point in K^{m} such that:

H_{1} : p does not cancel the polynomial Δ_{W^{j}} from Theorem 2. H_{2} : The jacobian determinant of F(p, X) with respect to X is invertible on

all solutions of the system F(p, X).

For simplicity, we drop the superscript in T^{j}, writing T instead. We assume without loss of generality that p = 0 and let t be the specialization of T at 0. The following proposition shows that the lifting techniques apply to any factor of t, which is required to prove Theorem 4. We use the notation of Subsection 7.2.1, writing A for the power series ring K[[P]] and 𝔪 for its maximal ideal.

Proposition 12 Let r be a triangular set in K[X] such that the ideal generated by r contains t. Then there exists a triangular set R in A[X] such that the specialization R mod 𝔪 is r, and the ideal generated by R contains T. The approximations R mod 𝔪^{2^{κ}} can be computed with the complexity given in Proposition 11.

Proof. We first deduce the last statement from the existence of the triangular set R. Indeed, suppose that R is such that R mod 𝔪 = r, and T = BR for some matrix B. Since Hypotheses H′_{1} and H′_{2} hold for T, these equalities show that they hold for R too, so Proposition 11 applies, as requested. Thus, we concentrate on proving the existence of the triangular set R, and begin by treating a particular case.

A particular case. Let us first suppose that there exists k ≤ n such that the following holds. Let B denote A[X_{≤k−1}]/T_{≤k−1} and 𝔫 the ideal of B induced by 𝔪+(T_{1}, …, T_{k−1}). Thus, the quotient B/𝔫 is K[X_{≤k−1}]/t_{≤k−1}. Our assumption is:

• r_{≤k−1} = t_{≤k−1};

• there exists a polynomial q_{k} in B/𝔫 [X_{k}] such that t_{k} = q_{k}r_{k} holds in B/𝔫 [X_{k}];

• for j in k + 1, …, n, we see t_{j} as a polynomial in the variables X_{k+1}, …, X_{j} with coefficients in B/𝔫 [X_{k}], and assume that r_{j} is obtained by reducing all these coefficients modulo r_{k}.

Since A is complete with respect to the 𝔪-adic topology, B is complete with respect to the 𝔫-adic topology. Hypotheses H′_{1} and H′_{2} imply that the derivative of t_{k} with respect to X_{k} is invertible in B/𝔫 [X_{k}]/(t_{k}). Hensel’s Lemma then shows that there exists Q_{k} and R_{k} in B such that T_{k} = Q_{k}R_{k} holds in B[X_{k}] and r_{k} = R_{k} mod 𝔫. The polynomial R_{k} is defined in B[X_{k}], but we may identify it to its canonical preimage in A[X_{1}, …, X_{k}] ⊂ A[X_{1}, …, X_{n}].

For j < k, we define R_{j} = T_{j}. For j > k, we define R_{j} as follows. We see T_{j} as polynomial in the variables X_{k+1}, …, X_{j} with coefficients in B[X_{k}], and define R_{j} by reducing all these coefficients modulo R_{k}. As such, this polynomial is a multivariate polynomial in X_{k+1}, …, X_{j} with coefficients in A[X_{1}, …, X_{k}] modulo T_{1}, …, T_{k−1}, R_{k}, but as above, we may identify it with its canonical preimages in A[X_{1}, …, X_{n}]. Through this identification, r = R mod 𝔪.

We then prove the existence of a matrix B such that the equality T = BR holds, by successively constructing its lines.

• For j < k, we have T_{j} = R_{j}, so we take a line composed only of 0’s, with 1 at entry j.

• Let us now take j = k. The equality T_{k} = Q_{k}R_{k} in B[X_{k}] can be rewritten in A[X_{1}, …, X_{k}] as T_{k} = Q_{k}R_{k} + S_{k}, where S_{k} is in the ideal (T_{1}, …, T_{k−1}) = (R_{1}, …, R_{k−1}). This enables to define the k-th line of B.

• Finally, we take j > k. Then R_{j} is such that R_{j} = T_{j} with all coefficients reduced modulo R_{k} in B[X_{k}]. Thus, T_{j} = R_{j} + s_{j}, where s_{j} is in the ideal generated by R_{k} in B[X_{k}, …, X_{j}]. From the definition of B, this can be rewritten as T_{j} = R_{j} + S_{j} in A[X_{1}, …, X_{j}], where S_{j} is in the ideal (T_{1}, …, T_{k−1}, R_{k}) = (R_{1}, …, R_{k}).

This enables to complete the definition of B, from which the proposition follows.

The general case. Let k be the least integer such that r_{k} ≠ t_{k}; if r = t, we take k = n + 1. We prove by induction on k that if T satisfies hypotheses H′_{1}, H′_{2}, and t = T mod 𝔪 belongs to the ideal generated by r, then there exists a triangular set R such that r = R mod 𝔪, and a n × n matrix B with entries in A[X] such that T = BR. We call this property P_{k}; P_{n+1} is obvious, so we suppose that k ≤ n and that P is proved for k + 1, …, n + 1.

Since t_{k} is in the ideal generated by r, we deduce that r_{k} divides t_{k} in the polynomials ring over K[X_{≤k−1}]/t_{≤k−1}. We then define a triangular set s in K[X] as follows. We take s_{1}, …, s_{k} = r_{1}, …, r_{k}, and for j > k we define s_{j} as t_{j} with all coefficient reduced modulo s_{k}. Thus T and s satisfy the hypotheses of the previous paragraphs, which enables to define a triangular set S and a matrix B such that T = BS and s = S mod 𝔪.

The triangular set S satisfies hypotheses H′_{1} and H′_{2}. For j > k, s_{j} − t_{j} is in the ideal generated by r. Since t_{j} is in this ideal, s_{j} is in this ideal too. Consequently, we can apply our induction argument on S and r, since now s and r coincide at least up to index k. This shows the existence of a triangular set R and a matrix B′ such that S = B′R, and R mod 𝔪 = r. Thus, T = BB′R. This shows P_{k}, which proves the proposition. □

7.3.2 Main Algorithm

The main algorithm follows again the lines given Subsection 7.1; we start by choosing a generic enough point in the parameter space. Precisely, we let p be a point in K^{m} such that:

H_{1} : p does not cancel the polynomial δ_{W} from Proposition 2. H_{2} : p cancels none of the polynomials Δ_{W^{j}} from Theorem 2.

H_{3} : the jacobian determinant of F with respect to X is invertible on all solutions of the system F(p, X).

From these hypotheses, we deduce that T^{1}, …, T^{J} can be specialized at p, and that the specializations t^{1}, …, t^{J} describe the solutions of F(p, X). Unfortunately, there is no guarantee that the routine Solve(F, p) will precisely compute these specializations, since undesired factorizations may occur. We now show how to bypass this difficulty.

Let r^{1}, …, r^{Q} triangular sets that describe the solutions of F(p, X), and define prime ideals in K[X]. Then for all i, there exists j such that t^{j} is in the ideal defined by r^{i}. Using hypotheses H_{2} and H_{3}, Proposition 12 shows that the lifting process can be applied to r^{i}, yielding a triangular set R^{i} in K[[P]][X]. The following proposition shows that these are enough to compute the polynomial M_{1}.

Proposition 13 Reorder r^{1}, …, r^{Q} so that r_{1}^{1}, …, r_{1}^{q} are representatives of the distinct polynomials among r_{1}^{1}, …, r_{1}^{Q}, for some q ≤ Q. Then Π_{i≤q}R_{1}^{i} = M_{1} in K[[P]][X_{1}].

Proof. We first show that R_{1}^{1}, …, R_{1}^{Q} are irreducible in K[[P]][X_{1}]. Suppose that R_{1}^{i} = GH in K[[P]][X_{1}]. Since R_{1}^{i} is monic, we may suppose that G and H are monic. Then r_{1}^{i} = (G mod 𝔪)(H mod 𝔪). Since r_{1}^{i} is irreducible, it follows that for instance G mod 𝔪 is a unit. Since G is monic, G is the constant 1, so R_{1}^{i} is irreducible.

The polynomials R_{1}^{1}, …, R_{1}^{q} are all pairwise distinct, hence pairwise coprime, since they are irreducible. Since each of them divides one of the polynomials T_{1}^{j}, each of them divides M_{1}. Thus Π_{i≤q}R_{1}^{i} divides M_{1}. The degree of Π_{i≤q}R_{1}^{i} is the degree of Π_{i≤q}r_{1}^{i}, i.e. the cardinality of μ_{1}(W_{n}(p)). Using hypothesis H_{1} and Proposition 2, we see that it coincides with the generic degree D_{1}, that is, the degree of M_{1}. Thus, Π_{i≤q}R_{1}^{i} = M_{1}. □

This is the basis of the following algorithm. The subroutine Stop computes the product of all polynomials r_{1}^{i}, and if possible, a rational reconstruction of all coefficients of the product. This gives a polynomial M, on which we apply a probabilistic check: as before, we test whether M specializes on the minimal polynomial of X_{1} for a randomly chosen witness p′. As in the previous subsection, this routine is denoted by Stop; the computation of minimal polynomial of X_{1} for the specialization value p′ is denoted by MinimalPolynomial(F, p′).

Computing a minimal polynomial

Input: The system F, two points p, p′ Output: The minimal polynomial M_{1}. r^{1}, …, r^{q} ← Solve(F, p)

       m′ ← MinimalPolynomial(F, p′)
       while not(Finished) do

for i in 1, …, q do

r^{i} ← Lift(r^{i}, F)

Finished,M_{1} ← Stop(r^{1}, …, r^{q}, m′)

       end while
       return M_{1}

The complexity and probability analyses strictly follow those of Subsection 7.2. The only notable differences are that we now take hypotheses H_{1}, H_{2} and H_{3} into account, and that the coefficients of M_{1} are of degree bounded by d^{n}, according to Proposition 3. We leave the details of the computation to the reader.

8 Applications

To conclude this article, we present three applications of our algorithms, coming from geometry, number theory and cryptography.

The algorithms are implemented in Magma. They outperformed the builtin functions on all these examples, so we rather focus on comparing times with the approach through primitive element techniques presented in Schost [2003]. This confirms the advantage of triangular techniques for problems such as presented here, where only a partial information is required.

For all these examples, the probabilistic aspect was not a problem. When verification was possible, it never revealed an error. Further, in many situations, problem-specific arguments can show that the output is correct once it is computed.

All computations were done on a Compaq XP/1000 EV6 from the MEDICIS

resource center, see http://www.medicis.polytechnique.fr/.

8.1 Implicitization

Let φ_{i} = N_{i}/D_{i} (i = 1, 2, 3) be a triple of rational functions in ℚ(X_{1}, X_{2}). Take D = lcm(D_{1}, D_{2}, D_{3}) and let φ be the map

\begin{aligned}φ : & ℝ^{2} − V (D) & → & ℝ^{3} \\ & x & ↦ & (φ_{1}(x), φ_{2}(x), φ_{3}(x)) . \end{aligned}

We suppose that φ is not degenerate, in the sense that its image has dimension 2 as a constructible set. Then the problem of implicitization consists in computing an equation M defining the closure V of the image of φ. This question has attracted a lot of attention, notably because of its relevance for Computer Aided Geometric Design, see Cox [2001], d’Andréa [2001], Ruatta [2002], Busé et al. [2002], Busé and Jouanolou [2002] and references therein.

Many of these solutions are based on suitable resultant formulas. We here propose a solution that inherits the good complexity of the above algorithms, applies in all generality and is quite practical. We note the obvious generalization to n-space; nevertheless we stick to dimension 2 for simplicity.

Consider the polynomial system

F = {D_{i}(X_{1}, X_{2})Y_{i} − N_{i}(X_{1}, X_{2}) (i = 1, 2, 3), D(X_{1}, X_{2})Z − 1}

in ℚ[Y_{1}, Y_{2}, Y_{3}, X_{1}, X_{2}, Z], let W ⊂ 𝔸^{6}(ℂ) be its zero-set and V the projection of W on the subspace of coordinates Y_{1}, Y_{2}, Y_{3}. What we are looking for is an equation defining the closure of V.

Without loss of generality, we suppose that the projection of V is dense in the space 𝔸^{2}(ℂ) of coordinates Y_{1}, Y_{2}; then Sard’s Theorem shows that the Jacobian determinant of F with respect to Y_{3}, X_{1}, X_{2}, Z is invertible on all points of W above some open subset of 𝔸^{2}(ℂ). Since W is irreducible, this Jacobian determinant is thus invertible on a dense subset of W, so we can apply the previous results.

Let us see the equation M in ℚ[Y_{1}, Y_{2}][Y_{3}]. By Proposition 3, the minimal polynomial of Y_{3} modulo the ideal generated by F in ℂ(Y_{1}, Y_{2})[Y_{3}, X_{1}, X_{2}, Z] is M, divided by its leading coefficient. Thus, we can apply Theorem 4 and use the underlying algorithm to compute M.

From the practical viewpoint, the additional variable Z introduced for applying Rabinovicz’ trick burdens the computation. Referring to the proof of Proposition 11, the special shape of the system F shows that the lifting phase can be done using only the system

F̃ = {D_{i}(X_{1}, X_{2})Y_{i} − N_{i}(X_{1}, X_{2}) (i = 1, 2, 3)}

in ℚ[Y_{1}, Y_{2}, Y_{3}, X_{1}, X_{2}]. This reflects the local nature of lifting techniques.

We illustrate the method on an example from invariant theory [Bershenko-Kogan, 2000], with

φ_{1} = \frac{1}{3} \frac{X_{1}X_{2}^{2} + X_{2}^{2} + X_{2} + X_{1}^{2}X_{2} − 6X_{1}X_{2} + X_{1} + X_{1}^{2}}{X_{1}X_{2}} ,
φ_{2} = −\frac{1}{9} \frac{(X_{2} − 1 + X_{1})(−X_{2} − 1 + X_{1})(−X_{2} + 1 + X_{1})}{X_{1}X_{2}},
φ_{3} = \frac{1}{36} \frac{(X_{1} + 1)^{2}(X_{2} + 1)^{2}(P (X_{1}) + P (X_{2}) + X_{1}X_{2}^{3} − X_{1}^{2}X_{2}^{2} + X_{2}X_{1}^{3})^{2}}{X_{1}^{2}X_{2}^{2}(X_{1} + X_{2} + 1)^{4}}

and P (X) = X + 2X^{2} + X^{3}. In Schost [2003], we treated this example using a minimal polynomial computation modulo a parametric geometric resolution, that is, primitive element techniques; this took 7 minutes. The time now drops to 20 seconds using triangular sets.

8.2 Genus 2 Curves with (2,2)-split Jacobian

Genus 2 curves with Jacobian (2,2)-isogeneous to a product of elliptic curves appear frequently in number theory: rank and torsion records are obtained for such curves, see Kulesz [1995, 1999], Howe et al. [2000]. In Gaudry and Schost [2001], we give an explicit classification of such situations, using the algorithms presented here. We now describe part of the necessary computations.

Isomorphism classes of genus 2 (resp. elliptic) curves are classified by their Igusa invariants j_{1}, j_{2}, j_{3} (resp. by their j-invariant). There exists a polynomial T (J_{1}, J_{2}, J_{3}) such that a genus 2 curve has (2,2)-split Jacobian if and only if its Igusa invariants cancel T; then the j-invariants of the underlying elliptic curves are the roots of a polynomial of degree 2, whose coefficients are rational functions of j_{1}, j_{2}, j_{3}. We are thus looking for this polynomial, together with the polynomial T.

A genus 2 curve with (2,2)-split Jacobian admits the equation

y^{2} = x^{6} + ax^{4} + bx^{2} + 1;

its Igusa invariants are then rational functions J_{1}(a, b), J_{2}(a, b), J_{3}(a, b). The underlying elliptic curves are isomorphic to the curves

y^{2} = x^{3} + ax^{2} + bx + 1;

their j-invariant is a rational function J(a, b). Let thus F be the system obtained in ℚ[j_{1}, j_{2}, j_{3}, j, a, b, Z] after canceling denominators in

{j − J(a, b), j_{1} − J_{1}(a, b), j_{2} − J_{2}(a, b), j_{3} − J_{3}(a, b)}

and removing the zero-set of the denominators of J, J_{1}, J_{2}, J_{3} by using Rabinovicz’ trick with the variable Z. Just as in the previous subsection, we note that the lifting can done without using the variable Z.

We take j_{1}, j_{2} for parameters, and work in ℚ(j_{1}, j_{2})[j_{3}, j, a, b, Z] modulo the ideal generated by F. This ideal is prime of dimension zero, so its solutions are represented by a triangular set in ℚ(j_{1}, j_{2})[j_{3}, j, a, b, Z]. The first polynomial T_{1} ∈ ℚ(j_{1}, j_{2})[j_{3}] is the relation T mentioned above, which was already known to Mestre [1990]. As requested, the second polynomial T_{2} ∈ ℚ(j_{1}, j_{2})[j_{3}, j] gives j in terms of j_{1}, j_{2}, j_{3} when the denominators of its coefficients do not vanish.

We use the algorithm of Subsection 7.2. The polynomial T_{1} is computed in 22 seconds, and T_{1}, T_{2} in 140 seconds. As a comparison, using the algorithm of Schost [2003], computing a representation by primitive element requires more than 400 seconds. This illustrates again the interest of the “triangular” approach, when only a partial information is wanted.

8.3 Modular Equations

In Gaudry and Schost [2002], modular equations for hyperelliptic curves are defined. Over a finite base field, they aim at simplifying the problem of pointcounting in the Jacobian of such curves, a question of first importance for hyperelliptic cryptosystems, see Gaudry [2000].

In fixed genus, modular equations are univariate polynomials indexed by a prime ℓ. Given a hyperelliptic curve C and a prime ℓ, the ℓ-th modular equation partly describes the structure of the ℓ-torsion divisors in the Jacobian of C; its factorization pattern gives information on the cardinality of the Jacobian of C modulo ℓ.

The ℓ-torsion divisors form a finite group G_{ℓ}, and are solutions of an algebraic system, in suitable coordinates. Introducing a well-chosen function t_{ℓ} on G_{ℓ}, the modular equation becomes the minimal polynomial Ξ_{ℓ} of t_{ℓ} modulo G_{ℓ}.

Computing Ξ_{ℓ} for a generic curve is done using the algorithm of Subsection 7.3.

We treated the 3-torsion in genus 2; the corresponding system has 3 equations in 3 unknowns X_{1}, X_{2}, X_{3} and 3 parameters P_{1}, P_{2}, P_{3} which parameterize curves of genus 2. The output Ξ_{3} ∈ ℚ(P_{1}, P_{2}, P_{3})[T] is computed within 4.5 hours; for comparison, it takes more than 20 hours to compute a representation by a primitive element. The polynomial Ξ_{3} is now used within Magma’s hyperelliptic curves package CrvHyp.

References

M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeros, multiplicities and idempotents for zero-dimensional systems. In Proceedings of MEGA’94, volume 143 of Progress in Mathematics, pages 1–15. Birkhäuser, 1996.

P. Aubry. Ensembles triangulaires de polynômes et résolution de systèmes

algébriques. Implantation en Axiom. PhD thesis, Université Paris VI, 1999. P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets.

Journal of Symbolic Computation, 28(1,2):45–124, 1999. W. Baur and V. Strassen. The complexity of partial derivatives. Theoretical

Computer Science, 22:317–330, 1983. I. Bershenko-Kogan. Inductive approach to Cartan’s Moving Frame Method

with applications to classical invariant theory. PhD thesis, University of Minesotta, 2000.

F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Representation for the radical of a finitely generated differential ideal. In Proceedings ISSAC’95, pages 158–166. ACM Press, 1995.

L. Busé, D. Cox, and C. d’Andréa. Implicitization of surfaces in ℙ^{3} in the

presence of base points. Preprint math.AG/0205251, 2002. L. Busé and J.-P. Jouanolou. On the closed image of a rational map and the

implicitization problem. Preprint math.AG/0210096, 2002. D. Cox. Equations of parametric curves and surfaces via syzygies. Contem-

porary Mathematics, 286:1–20, 2001. C. d’Andréa. Resultants and moving surfaces. Journal of Symbolic Computa-

tion, 31(5):585–602, 2001. S. Dellière. Triangularisation de systèmes constructibles — Application à

l’évaluation dynamique. PhD thesis, Université de Limoges, 1999. D. Eisenbud. Commutative Algebra with a view toward Algebraic Geometry,

volume 150 of Graduate Texts in Mathematics. Springer, 1996. G. Gallo and B. Mishra. Efficient algorithms and bounds for Wu-Ritt charac-

teristic sets. In Proceedings of MEGA’90, volume 94 of Progress in Mathematics, pages 119–142. Birkhäuser, 1990.

P. Gaudry. Algorithmique des courbes hyperelliptiques et applications à la

cryptologie. PhD thesis, École polytechnique, 2000. P. Gaudry and É. Schost. On the invariants of the quotients of the Jacobian

of a curve of genus 2. In Proceedings of AAECC-14, volume 2227 of Lecture

Notes in Computer Science, pages 373–386. Springer, 2001. P. Gaudry and É. Schost. Modular equations for hyperelliptic curves.

Manuscript, École polytechnique, France, 2002. P. Gianni and T. Mora. Algebraic solution of systems of polynomial equations

using Gröbner bases. In Proceedings of AAECC-5, volume 356 of Lecture Notes in Computer Science, pages 247–257. Springer, 1989.

M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for Diophantine approximation. Journal of Pure and Applied Algebra, 117,118:277–317, 1997.

M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straightline programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101–146, 1998.

M. Giusti, J. Heintz, J.-E. Morais, and L. M. Pardo. When polynomial equation systems can be solved fast? In Proceedings of AAECC-11, volume 948 of Lecture Notes in Computer Science, pages 205–231. Springer, 1995.

M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial

system solving. Journal of Complexity, 17(1):154–211, 2001. J. Heintz. Definability and fast quantifier elimination in algebraically closed

fields. Theoretical Computer Science, 24(3):239–277, 1983. J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein. Deformation

techniques for efficient polynomial equation solving. Journal of Complexity, 16:70–109, 2000.

J. Heintz, G. Matera, and A. Waissbein. On the time-space complexity of geometric elimination procedures. Applicable Algebra in Engineering, Communication and Computing, 11:239–296, 2001.

E. Howe, F. Leprévost, and B. Poonen. Large torsion subgroups of split Jacobians of curves of genus two or three. Forum Mathematicum, 12:315–364, 2000.

É. Hubert. Notes on triangular sets and triangulation-decomposition algorithms I: Polynomial systems. In Symbolic and Numerical Scientific Computations. Springer. To appear.

M. Kalkbrener. Three contributions to elimination theory. PhD thesis, Kepler

University, Linz, 1991. T. Krick and L. M. Pardo. A computational method for Diophantine approxi-

mation. In Proceedings of MEGA’94, volume 143 of Progress in Mathematics, pages 193–254. Birkhäuser, 1996.

T. Krick, L. M. Pardo, and M. Sombra. Sharp estimates for the arithmetic

Nullstellensatz. Duke Math. Journal, 109:521–598, 2001. T. Krick, J. Sabia, and P. Solernó. On intrinsic bounds in the Nullstellensatz.

Applicable Algebra in Engineering, Communication and Computing, 8:125– 134, 1997.

L. Kulesz. Courbes algébriques de genre 2 possédant de nombreux points

rationnels. C. R. Acad. Sci. Paris, 321:91–94, 1995. L. Kulesz. Application de la méthode de Dem’janenko-Manin à certaines

familles de courbes de genre 2 et 3. Journal of Number Theory, 76:130–146, L. Langemyr. Algorithms for a multiple algebraic extension. In Proceed-

ings of MEGA’90, volume 94 of Progress in Mathematics, pages 235–248. Birkhäuser, 1990.

D. Lazard. A new method for solving algebraic systems of positive dimension.

Discrete Applied Mathematics, 33:147–160, 1991. D. Lazard. Solving zero-dimensional algebraic systems. Journal of Symbolic

Computation, 13(2):117–133, 1992. G. Lecerf. Quadratic Newton iteration for systems with multiplicity. Founda-

tions of Computational Mathematics, 2:247–293, 2002. G. Lecerf and É. Schost. Fast multivariate power series multiplication in char-

acteristic zero. SADIO Electronic Journal on Informatics and Operations Research., 2003. To appear.

M. Moreno Maza. Calculs de pgcd au-dessus des tours d’extensions simples et résolution des systèmes d’équations algébriques. PhD thesis, Université Paris VI, 1997.

J.-F. Mestre. Construction de courbes de genre 2 à partir de leurs modules. In Proceedings of MEGA’90, volume 94 of Progress in Mathematics, pages 313–334. Birkhäuser, 1990.

S. Morrison. The differential ideal [P] : M^{∞}. Journal of Symbolic Computa-

tion, 28(4/5):631–656, 1999. B. Mourrain and O. Ruatta. Relation between roots and coefficients, interpo-

lation and application to system solving. Journal of Symbolic Computation, 33(5):679–699, 2002.

L. M. Pardo. How lower and upper complexity bounds meet in elimination theory. In Proceedings of AAECC-11, volume 948 of Lecture Notes in Computer Science, pages 33–69. Springer, 1995.

F. Rouillier. Solving zero-dimensional systems through the Rational Univariate Representation. Applicable Algebra in Engineering, Communication and Computing, 9(5):433–461, 1999.

O. Ruatta. Dualité algébrique, structures et applications. PhD thesis, École

doctorale Mathématiques et Informatique de Marseille, 2002. J. Sabia and P. Solernó. Bounds for traces in complete intersections and

degrees in the Nullstellensatz. Applicable Algebra in Engineering, Communication and Computing, 6:353–376, 1996.

A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Com-

puting, 7:281–292, 1971. É. Schost. Degree bounds and lifting techniques for triangular sets. In Pro-

ceedings of ISSAC 02, pages 238–245. ACM Press, 2002. É. Schost. Computing parametric geometric resolutions. Applicable Algebra

in Engineering, Communication and Computing, 13:349–393, 2003. J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial

identities. Journal of the ACM, 27(4):701–717, 1980. A. Szanto. Computation with polynomial systems. PhD thesis, Cornell Uni-

versity, 1999.

W. Trinks. On improving approximate results of Buchberger’s algorithm by Newton’s method. In Proceedings of EUROCAL’85, volume 204 of Lecture Notes in Computer Science, pages 608–611. Springer-Verlag, 1985.

J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge

University Press, 1999. F. Winkler. A p-adic approach to the computation of Gröbner bases. Journal

of Symbolic Computation, 6(2/3):287–304, 1988. R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings

of EUROSAM’79, volume 72 of Lecture Notes in Computer Science, pages 216–226. Springer, 1979.