Computing an Equidimensional Decomposition of an Algebraic Variety by means of Geometric Resolutions

Grégoire Lecerf

Laboratoire GAGE, École polytechnique

F-91128 Palaiseau, France

lecerf@gage.polytechnique.fr

Abstract

Let f_{1}, …, f_{s} be polynomials in n variables over a field of characteristic zero and d be the maximum of their total degree. We propose a new probabilistic algorithm for computing a geometric resolution of each equidimensional part of the variety defined by the system f_{1} = ⋯ = f_{s} = 0. The returned resolutions are encoded by means of Straight-Line Programs and the complexity of the algorithm is polynomial in a geometric degree of the system. In the worst case this complexity is asymptotically polynomial in sd^{n}.

Introduction

Let k be a field of characteristic zero, f_{1}, …, f_{s} be s polynomials in k[x_{1}, …, x_{n}] and d be the maximum of their total degree. Let V = V(f_{1}, …, f_{s}) be the algebraic variety defined by the system f_{1} = ⋯ = f_{s} = 0 in the n dimensional affine space over an algebraic closure \overline{k} of k. We are interested in computing an exact description of V, from the computer algebra point of view.

Up to now, the best complexity upper bound known is asymptotically polynomial in sd^{n^{2}}: in [3] Chistov and Grigoriev present an algorithm with such a complexity for computing a decomposition of V into irreducible components; Giusti and Heintz give in [9] another method with the same complexity, moreover their decomposition into equidimensional parts is well-parallelizable; Elkadi and Mourrain propose in [4] a method based on Bézoutian matrices, their algorithm is probabilistic.

Our aim is to present an algorithm which computes a geometric resolution of each equidimensional part of the variety V with a complexity polynomial in some intrinsic degree of the system and, by the way, polynomial in sd^{n} in the worst case.

Our algorithm stores eliminating polynomials by means of Straight-Line Programs (SLP) without division; our method lies in the continuation of a series of papers initiated by Giusti, Heintz, Hägele, Morais, Montaña, Morgenstern and Pardo: in [7, 11] they give an algorithm for computing the isolated points solutions of any polynomial equation system with a complexity polynomial in an intrinsic degree of the system. In [12] we simplify and redesign the algorithm and explain how to implement it. Our aim is now to extend the theoretical method in order to compute not only the isolated roots but a description of all the components.

In the sequel, L represents the complexity of the given SLP encoding the input system f_{1}, …, f_{s}. When considering degrees of algebraic varieties we use Heintz’ degree [13], that is the sum of the degrees of all the isolated irreducible components appearing in a minimal decomposition of the variety.

Let t_{i,j} for 1 ≤ i ≤ n + 1 and 1 ≤ j ≤ s, be some new generic parameters taking their value in k. Let g_{i} be the generic linear combination ∑_{j=1}^{s} t_{i,j}f_{j}, for 1 ≤ i ≤ n + 1. We define the intermediate varieties V_{i} as V(g_{1}, …, g_{i}) for 0 ≤ i ≤ n + 1 and we define the intrinsic degree δ of the system as being the maximum of the degrees δ_{i} of V_{i}, 0 ≤ i ≤ n. Note that by convention V_{0} represents the whole space \overline{k}^{n}.

Theorem 1 There exist a dense open subset G of k^{(n+1)s} and a deterministic algorithm such that: if the values of the t_{i,j} are taken in G, it computes a minimal geometric resolution, encoded by SLP, of V with a non-uniform complexity polynomial in Lnsdδ, in terms of the number of arithmetic operations in k.

Let α be a positive integer, if Ω is a set of points of size 3α(d + 1)^{3n} in k, a random point t_{i,j} in Ω^{(n+1)s} belongs to G with probability of success at least 1 − (sn)^{c}/α for some universal positive constant c.

The definition of geometric resolutions is stated in the next section and the complexity model in §3.1. Note that δ is bounded by d^{n}, using the Bézout inequality [13].

The deterministic algorithm of the theorem admits a bounded error probabilistic counterpart in a uniform complexity model (see discussion in §3.1).

Our algorithm relies on the properties of the V_{i} and their relation with V; we adapt the results of [11] in order to perform splittings when irregular intersections occur. So the paper is organized as follows: we first recall the definition of a geometric resolution, then we describe the properties of the generic system g_{1} = ⋯ = g_{n+1} = 0 and the last part is devoted to the description of the algorithm and the proof of Theorem 1. Appendix 3.3 details a technical result contained in [11] but without an independent statement.

1 Definitions

Let W be a r-equidimensional algebraic variety and ℑ its annihilating ideal in k[x_{1}, …, x_{n}].

Let M be an invertible n×n square matrix with entries in k, we say that the new coordinates y = M^{−1}x are in Noether position with respect to W if the following two conditions hold: the variables y_{1}, …, y_{r} are free, which means that the canonical projection from W to the affine space generated by y_{1}, …, y_{r} is surjective, and the ring morphism

R := k[y_{1}, …, y_{r}] ⟶ k[y_{1}, …, y_{n}]/(f_{1}, …, f_{s}) =: B

defines an integral ring extension.

Let K be the field of fractions of R and B′ the finitedimensional K-vector space K ⊗ B. A linear form u is said to be a primitive element of W if its set of powers generates B′.

A geometric resolution of W is defined by:

• an invertible n × n square matrix M with entries in k such that the new coordinates y = M^{−1}x are in Noether position with respect to W;

• a primitive element u = λ_{r+1}y_{r+1} + ⋯ + λ_{n}y_{n} of W, with the λ_{j} in k;

• the minimal polynomial q(T) ∈ R[T] of u in B′, monic in T, with degree in T equal to the dimension of B′ and

• the parametrization of W by the zeros of q, given by polynomials

ρy_{r+1} − v_{r+1}(T), …, ρy_{n} − v_{n}(T),

where ρ is in R and the v_{j} are in R[T] with degree in T strictly less than the one of q and such that B′ is isomorphic to K[T]/(q(T), ρy_{r+1} − v_{r+1}(T), …, ρy_{n} − v_{n}(T)).

The total degree of q is bounded by deg(W) and those of ρ and the v_{j} can be bounded by deg(W)^{3} [12, 23].

If W is not equidimensional, we call a minimal geometric resolution a decomposition of W in W_{0} ∪W_{1} ∪⋯∪W_{n} such that W_{i} is either empty or an algebraic variety of codimension i and no component of any W_{j} is included in another one, each W_{j} being described by means of a geometric resolution.

2 Preparation Lemmas

The first part of our algorithm is incremental in the number of the g_{i}’s: we give geometric resolutions of V_{0}, V_{1}, …, V_{n+1} in sequence. The following lemmas give the properties of this sequence when the t_{i,j} are chosen generic enough.

The first lemma shows that the “interesting” successive intersections of the g_{i}’s are regular. Note that this lemma is a local version of [10, §3.4.1] of Giusti and Heintz (see also [13, 9]).

Lemma 1 For all i, 0 ≤ i ≤ n, for any t_{k,l} in k, 1 ≤ k ≤ i, 1 ≤ l ≤ s, there exists a nonzero polynomial P_{i+1} in \overline{k}[(T_{i+1,l})_{1≤l≤s}] of total degree bounded by d^{i} such that: for all t_{i+1,l}, 1 ≤ l ≤ s, P_{i+1}((t_{i+1,l})_{1≤l≤s}) ≠ 0 implies that for any irreducible component M of codimension i of the variety V_{i} the following alternative holds: M is in V or V(g_{i+1}) intersects M regularly.

Proof. Let M be an irreducible component of V_{i} of codimension i not included in V, so that there exists some m such that M is not included in the hypersurface defined by f_{m} = 0. We take a point C_{M} in M not in V(f_{m}). Let us associate such a point C_{M} to each irreducible component of V_{i} of codimension i not included in V. Let P_{i+1} be the polynomial defined by

∏_{M}(T_{i+1,1}f_{1}(C_{M}) + ⋯ + T_{i+1,s}f_{s}(C_{M})).

By construction P_{i+1} is not identically zero, has total degree bounded by d^{i} and has the required property. □

We apply incrementally the lemma: first we choose values for t_{1,1}, …, t_{1,s}, then for t_{2,1}, …, t_{2,s} and so on until t_{n+1,1}, …, t_{n+1,s}. The system of g_{i}’s we obtain satisfies the following property, denoted by R_{1} in the sequel:

R_{1}: for all i, 0 ≤ i ≤ n, an irreducible component of V_{i} of codimension i is either included in V or regularly intersected by g_{i+1}.

We now quantify the probability of success of this construction.

Proposition 1 Let α be a strictly positive integer, and Ω be a set of points of k of cardinal αd^{n}. A random choice of all the t_{i,j}, 1 ≤ i ≤ n + 1, 1 ≤ j ≤ s, in Ω^{(n+1)s} leads to polynomials g_{i} satisfying the property R_{1} with a probability at least 1 − (sn)^{c_{1}}/α, for some universal positive constant c_{1}.

Proof. Using Zippel-Schwartz’ zero test [24, 25], the probability that a point (t_{i+1,1}, …, t_{i+1,s}) chosen at random in Ω^{s} is not a zero of P_{i+1} is at least 1 − s/α. Thus the probability that some t_{i,j} chosen at random in Ω^{(n+1)s} define some g_{i} satisfying the property R_{1} is at least (1−s/α)^{n+1} ≥ 1 − s(n + 1)/α. □

In the sequel we denote by V_{i}^{P} (Pure codimension) the variety composed of the components of V_{i} of codimension i, by V_{i}^{R} (Regularly intersected) the ones of V_{i}^{P} being intersected regularly by g_{i+1} and V_{i}^{I} (Improper) the ones of V_{i}^{P} included in the hypersurface defined by g_{i+1} = 0.

Proposition 2 For choices of t_{i,j} such that properties R_{1} holds, the varieties V_{i} satisfy the following properties.

1. For i ≥ 0, the minimal equidimensional decomposition of V_{i} is given by

V_{0}^{I} ∪ ⋯ ∪ V_{i−1}^{I} ∪ V_{i}^{P} .

2. The minimal decomposition of V into equidimensional

parts is

V_{0}^{I} ∪ V_{1}^{I} ∪ ⋯ ∪ V_{n}^{I}.

Proof. We prove the first point by induction on i. The case i = 0 is trivial, let us assume that the property is true for a given i ≥ 0. The variety V_{i+1} is the intersection of V_{i} by the hypersurface defined by g_{i+1}, the property R_{1} implies that all the V_{j}^{I}, 1 ≤ j ≤ i, are included in V, thus in the hypersurface defined by g_{i+1}. Hence V_{i+1} equals V_{0}^{I} ∪ ⋯ ∪ V_{i}^{I} ∪ V_{i}^{R} ∩ V(g_{i+1}). The variety V_{i+1}^{P} is then the union of the irreducible components of V_{i}^{R} ∩ V(g_{i+1}) not included in V_{0}^{I} ∪ ⋯ ∪ V_{i}^{I}. The property holds at i + 1.

For the second point, the inclusion of V_{0}^{I} ∪ V_{1}^{I} ∪ ⋯ ∪ V_{n}^{I} in V is a direct consequence of the property R_{1}. For the reverse inclusion, let M be an irreducible component of V of codimension i > 0. The variety M is included in V_{0}^{R}, let j be the greatest index such that M is included in V_{j}^{R} and not in V_{j+1}^{R}. Necessarily M is included in V_{j}^{R} ∩ V(g_{j+1}). If M is included in one of the V_{k}^{I} for a given k ≤ j we are done, otherwise M is included in V_{j+1}^{P}, and thus in V_{j+1}^{I}.□

Let us now turn to the question of the multiplicities of the components of the V_{i}. The next lemma is a weak local version of Bertini’s first theorem, the complete proof we give of our assertion has been inspired by Bertini’s original one as explained by Kleiman in [16]. This result is also a local version of [17, Proposition 37] or [23, Proposition 4.4].

Lemma 2 For each i, 0 ≤ i ≤ n, there exists a non zero polynomial Q_{i} in \overline{k}[(T_{k,l})_{1≤k≤i,1≤l≤s}] of total degree bounded by 3(d+1)^{3i} such that: for all t_{k,l} in k, 1 ≤ k ≤ i, 1 ≤ l ≤ s, Q_{i}((t_{i+1,l})_{1≤l≤s}) ≠ 0 implies that for any irreducible component M of codimension i of the variety V_{i} the following alternative holds: M is included in V or M is reduced with respect to g_{1}, …, g_{i}.

Proof. First we prove that when the t_{k,l} are generic the alternative holds.

In this proof R represents the polynomial ring k[(T_{k,l})_{1≤k≤i,1≤l≤s}], K its field of functions, G_{i} the polynomials T_{i,1}f_{1} + ⋯ + T_{i,s}f_{s}, for 1 ≤ i ≤ n. Let us now fix i in the range 0 … n, let r be n − i and M be an irreducible component of the variety defined by G_{1}, …, G_{i} in K[x_{1}, …, x_{n}]. Let us consider a geometric resolution of M: let y_{1}, …, y_{n} be the variables in Noether position, y = M^{−1}x, u the primitive element, q the minimal polynomial and the parametrization given by ρy_{j} = v_{j}(u), r + 1 ≤ j ≤ n. Let us assume that the component is multiple with respect to G_{1}, …, G_{i}. This means that there exist polynomials H_{1}, …, H_{i} in K(y_{1}, …, y_{r})[u], such that q is prime with one of them, say H_{k}, and such that

∑_{j=1}^{i} H_{j}grad(G_{j} ∘ M)(y_{1}, …, y_{r}, v_{r+1}(u)/ρ, …, v_{n}(u)/ρ)

has all its entries in the ideal (q), the gradient being considered with respect to the variables y_{r+1}, …, y_{n}. This implies that

∑_{j=1}^{i}(H_{j}(G_{j} ∘ M))(y_{1}, …, y_{r}, v_{r+1}(u)/ρ, …, v_{n}(u)/ρ)

belongs to the ideal generated by q^{2}. Let Y represent the vector (v_{r+1}(u)/ρ, …, v_{n}(u)/ρ). Differentiating the last expression with respect to T_{k,l} we get that

∑_{j=1}^{i} ( \frac{∂}{∂T_{k,l}} (H_{j}(y_{1}, …, y_{r}, Y)))(G_{j} ∘ M)(y_{1}, …, y_{r}, Y)

+ ∑_{j=1}^{i} H_{j}(y_{1}, …, y_{r}, Y)grad(G_{j}∘M)(y_{1}, …, y_{r}, Y)·( \frac{∂}{∂T_{k,l}} Y)

+ ∑_{j=1}^{i} H_{j}(y_{1}, …, y_{r}, Y)( \frac{∂}{∂T_{k,l}} (G_{j} ∘ M))(y_{1}, …, y_{r}, Y),

which is in (q). Since the two first terms are in (q), the last one is also in (q). But the last term A equals H_{k}(y_{1}, …, y_{r}, Y)( \frac{∂}{∂T_{k,l}} G_{k} ∘ M)(y_{1}, …, y_{r}, Y) and thus equals H_{k}(y_{1}, …, y_{r}, Y)(f_{l} ∘ M)(y_{1}, …, y_{r}, Y). Since H_{k}(y_{1}, …, y_{r}, Y) is invertible modulo q, this implies that f_{l}(y_{1}, …, y_{r}, Y) belongs to (q). This property is true for all l, we deduce that M is included in V, which achieves the first part of the proof.

We now prove constructively the existence of the desired polynomial Q_{i}. Let ℑ be the ideal generated by (G_{1}, …, G_{i}) in k[(T_{k,l})_{1≤k≤i,1≤l≤s}, x_{1}, …, x_{n}] and W be the corresponding variety.

Let M be an irreducible component of W and 𝔍 be its annihilating ideal.

First we consider the case 𝔍 ∩ R ≠ (0): if π denotes the canonical projection \overline{k}^{is} × \overline{k}^{n} ⟶ \overline{k}^{is}, \overline{π(W)} is contained in a hypersurface of degree bounded by the degree of M. Thus there exists a non zero polynomial F in 𝔍 ∩ R of total degree bounded by the degree of M. If t_{k,l} are such that F (t_{k,l}) ≠ 0 then 𝔍 + ((T_{k,l} − t_{k,l})_{1≤k≤i,1≤l≤s}) = (1).

Now consider the case 𝔍 ∩ R = (0). There exists a geometric resolution of 𝔍 in K[x_{1}, …, x_{n}]: let y_{j}, 1 ≤ j ≤ n, be the variables in Noether position, u the primitive element, q its minimal polynomial and ρ, v_{i} be the parametrization such that ρy_{j} = v_{j} for j ≥ n − i + 1 and

𝔍_{ϕψρ} = (q(u), ρy_{n−i+1} − v_{n−i+1}(u), …, ρy_{n} − v_{n}(u))_{ϕψρ},

where ψ is the discriminant of q with respect to u and ϕ the leading coefficient of q. Let t_{k,l} be such that ϕψρ(t) ≠ 0 then

𝔍 + ((T_{k,l} − t_{k,l})_{1≤k≤i,1≤l≤s})

= (q_{t}(u), ρ_{t}y_{n−i+1} − v_{t,n−i+1}(u), …, ρ_{t}y_{n} − v_{t,n}(u)),

where q_{t}, ρ_{t} and v_{t,j} represent respectively the values of q, ρ and the v_{j}, when the T_{k,l} are specialized at the t_{k,l}, for 1 ≤ k ≤ i, 1 ≤ l ≤ s. Since q_{t} is square free, the ideal 𝔍 + ((T_{k,l} − t_{k,l})_{1≤k≤i,1≤l≤s}) is reduced. Hence we let Q_{i} be one of the coefficients of ϕψρ with respect to the free variables y_{1}, …, y_{n−i}.

It remains to give a bound on the degrees of ϕ, ψ and ρ. According to the bound given by Schost in [20, Proposition 1], the polynomial q can be chosen to be a polynomial in R[y_{1}, …, y_{r}][u] of total degree bounded by the degree of M, and the total degree of ρ bounded by deg(M)^{3}. Since the degree of M is bounded by (d + 1)^{i}, the total degree of ϕψρ is bounded by 3(d + 1)^{3i}. □

We denote by R_{2} the following property:

R_{2}: for any irreducible component M of codimension i of the variety V_{i} the following alternative holds: M is included in V or M is reduced with respect to g_{1}, …, g_{i}.

Proposition 3 Let α be a strictly positive integer, and Ω be a set of points of k of cardinal 3α(d+1)^{3n}. A random choice of all the t_{i,j}, 1 ≤ i ≤ n + 1, 1 ≤ j ≤ s, in Ω^{(n+1)s} leads to polynomials g_{i} satisfying the property R_{2} with a probability at least 1 − (sn)^{c_{2}}/α, for a universal positive constant c_{2}.

Proof. Zippel-Schwartz’ zero test implies that a random choice of the t_{i,j} in the set Ω^{(n+1)s} is not a root of the product of all the Q_{i}, for 1 ≤ i ≤ n, with a probability at least 1 − (n + 1)^{2}s/α. □

3 Algorithm

In this section we assume that we have chosen values of the t_{i,j} such that g_{i}’s satisfies the properties R_{1} and R_{2}. In this situation we adapt the algorithm given in [11] in order to give a complete solution of the input system f_{1} = ⋯ = f_{s} = 0.

The algorithm is almost incremental. Indeed we would expect to compute resolutions of V_{i+1}^{I} and V_{i+1}^{R} from the one of V_{i}^{R}. But doing this way yields a recursive dependency between the V_{i}^{I} and thus an exponential factor in the complexity. Our strategy consists in computing first a resolution of the system, not necessarily minimal, and at the end we deduce a minimal one. The first task is called the incremental resolution and the second one the minimization.

For each i, 0 ≤ i ≤ n − 1, we define the variety V_{i+1}^{J} composed of the components of V_{i}^{R} ∩ V(g_{i+1}) which are included in the hypersurface defined by g_{i+2} = 0; in other words V_{i}^{R} ∩ V(g_{i+1}) is the (minimal) union of the components of V_{i+1}^{J} and the ones of V_{i+1}^{R}; moreover the variety V_{i+1}^{I} is included in V_{i+1}^{J}. By convention we define V_{0}^{J} to be V_{0}^{I}, so that the following set equalities hold:

V_{i} = V_{0}^{J} ∪ ⋯ ∪ V_{i}^{J} ∪ V_{i}^{R}, 0 ≤ i ≤ n,

V = V_{0}^{J} ∪ V_{1}^{J} ∪ ⋯ ∪ V_{n}^{J}.

Here is the outlook of the algorithm:

I. Incremental Resolution We compute geometric resolutions of each V_{i}^{J}, it is incremental in i: at the ith step we compute resolutions of V_{i+1}^{J} and V_{i+1}^{R} from the one of V_{i}^{R}. Each step divides into three parts:

1. Compression of the SLP of the geometric resolution of V_{i}^{R}.

2. Computation of the intersection of V_{i}^{R} by g_{i+1}.

3. Splitting V_{i}^{R} ∩ V(g_{i+1}) into V_{i+1}^{J} and V_{i+1}^{R}.

II. Minimization We compute the V_{i}^{I} using the equality

(∗)  V_{i}^{I} = \overline{V_{i}^{J}\ ∪_{0≤j<i} V_{j}^{J}},  0 ≤ i ≤ n.

Note that this formula for the V_{i}^{I} is not recursive.

The next subsections are devoted to the presentation of the complexity model we use, the description of each elementary block of the algorithm and a proof of Theorem 1.

3.1 Complexity Model

We assume that k is an effective field for which each elementary operation (addition, substraction, multiplication, division and equality test) has cost 1. The multivariate polynomials we use in our algorithm are stored by means of Straight-Line Programs (SLP) without test nor division, we refer to Strassen [21], von zur Gathen [6] or Heintz [14] for precise definitions.

The only non-trivial point when dealing with this data structure is equality checking (or zero testing). One can perform this task by evaluating the SLP at sufficiently many points. This is formalized in terms of correct test sequences of points with coordinates from k according to a theorem due to Heintz and Schnorr [15], which we recall for completeness.

Let D and L be two positive integers, and let us define the subset W (D, n, L) of polynomials of k[x_{1}, …, x_{n}], of degree at most D, which can be coded by a SLP with at most L arithmetic operations. Furthermore given a subset Γ of k, a family γ := {γ_{1}, …, γ_{m}} (with γ_{i} ∈ Γ) of m points in k^{n} is called a correct test sequence for W (D, n, L) if every polynomial in the latter vanishing on the points of γ is actually identically zero.

Theorem 2 [15] Given a subset Γ of k of cardinality #Γ = 2L(D + 1)^{2}, and a cardinality m := 6(L + n)(L + n + 1), the subset τ(D, n, L, Γ) ∈ Γ^{nm} of correct test sequences for W (D, n, L) satisfies:

#τ(D, n, L, Γ) ≥ (#Γ)^{nm}(1 − (#Γ)^{− \frac{m}{6}} ).

In other words, if we have precomputed all the correct test sequences needed for a fixed range of applications we have a polynomial time algorithm for testing the nullity of our SLP. In this sense we say that our complexity model is nonuniform. Finally, we say that all the operations (addition, multiplication, zero test) on SLP have a non-uniform complexity polynomial in their size and their number of variables.

All our results remain valid in a uniform complexity model if we replace correct test sequences by the probabilistic test given in [5] asserting that a SLP of size L can be tested to represent zero or not in time polynomial in L and n with a probability of failure uniformly bounded by 1/262144.

3.2 Incremental Resolution

Let us now turn to the description of the elementary blocks constituting the core of the loop of the first part of the algorithm.

Compression The compression technique is fundamental: it avoids the growth of the SLP representing the geometric resolution of the successive V_{i}^{R}. It is based on a Newton-Hensel iterator. We adapt the result [11, Lemma 5] to our situation:

Lemma 3 Let β be the size of a SLP encoding a geometric resolution of V_{i}^{R}, for i ≤ n, there exists a deterministic algorithm with a non-uniform complexity polynomial in βLsn deg(V_{i}^{R}) returning a SLP encoding a geometric resolution of V_{i}^{R} of size polynomial in Lsn deg(V_{i}^{R}).

Note that the size of the output is independent of β.

Intersection The second step is also taken from [11, Proposition 15]. It consists in computing a resolution of the intersection of V_{i}^{R} by the hypersurface defined by the equation g_{i+1} = 0.

Lemma 4 Let β be the size of a SLP of a geometric resolution of V_{i}^{R}, there exists a deterministic algorithm with a non-uniform complexity polynomial in βLsnd deg(V_{i}^{R}) which computes a geometric resolution of V_{i}^{R} ∩ V(g_{i+1}) encoded by a SLP of size polynomial in βLsnd deg(V_{i}^{R}).

Splitting From a resolution of V_{i}^{R} ∩ V(g_{i+1}) we want to compute its decomposition into V_{i+1}^{R} and V_{i+1}^{J}.

Lemma 5 Let β be the size of the SLP encoding a geometric resolution of V_{i}^{R} ∩ V(g_{i+1}), there exists a deterministic algorithm of non-uniform complexity polynomial in βLnsd deg(V_{i}^{R} ∩ V(g_{i+1})) which computes geometric resolutions of V_{i+1}^{R} and V_{i+1}^{J} encoded by a SLP of size polynomial in βLnsd deg(V_{i}^{R} ∩ V(g_{i+1})).

Proof. We apply directly Proposition 4 of the appendix with the equation of g_{i+2}. □

Let us introduce C to represent the expression Lnsdδ. First we note that the degrees of all the varieties V_{i}^{J} appearing during the resolution process are bounded by dδ. At each step of the loop, the compression produces a SLP of size bounded by C^{O(1)}, after the intersection we also get a SLP bounded by C^{O(1)}, and the same holds for the splitting. This induces that each step of the loop has a complexity at most polynomial in C and that the computed SLP of the V_{i}^{J} have size polynomial in C.

3.3 Minimization

Let us turn to the second part of the algorithm: from the resolutions of the V_{i}^{J} computed above, we want to compute resolutions of the V_{i}^{I}. Using equality (∗), it is enough to remove the components of V_{i}^{I} which are included in V_{0}^{J} ∪ ⋯ ∪ V_{i−1}^{J}. First we show that testing if a point belongs to an algebraic variety is equivalent to testing the nullity of the Chow form of the variety at the given point, then we give an algorithm for computing the Chow form of an equidimensional variety from a geometric resolution.

Let W be an r-equidimensional variety given by a geometric resolution: y denotes the variables in Noether position, y = M^{−1}x, u the primitive element, q the minimal polynomial, ρ and v_{j} the parametrizations, such that ρy_{j} = v_{j}(u), j > r. Let B represent k[W] and B′ be k(y_{1}, …, y_{r}) ⊗ B.

Let Λ_{r+1}, …, Λ_{n} be new generic parameters, and χ(y_{1}, …, y_{r}, T) the characteristic polynomial of the endomorphism of multiplication by the generic linear form U = Λ_{r+1}y_{r+1} + ⋯ + Λ_{n}y_{n}, in B′. The polynomial χ is called the Chow form of W, it is polynomial in the y_{i} and the Λ_{i}, monic in T, square free, its total degree in the y_{i} does not exceed the degree of W and its total degree in the y_{i} and Λ_{i} does not exceed 2 deg(W); moreover χ(u) = 0 holds in B [12, Corollary 2].

Lemma 6 A point P = (P_{1}, …, P_{n}) of \overline{k}^{n} belongs to W (in the coordinates y) if and only if χ(P_{1}, …, P_{r}, U(P)) is zero.

Proof. First, if P belongs to W the Chow form vanished at P. Reciprocally, let P be a point such that χ(P_{1}, …, P_{r}, U(P)) is zero. Let π denotes the canonical projection onto the free variables, using the theorem concerning the multiplicity of a specialization [19, p.89] the specialization of χ leads to the formula

χ(P_{1}, …, P_{r}, T) = ∏_{i=1}^{N}(T − Z_{i})^{m_{i}},

where the Z_{i} are the point of π^{−1}(P_{1}, …, P_{r}) of multiplicity m_{i}. This implies that there exists i such that U(P) = Z_{i}; since the Z_{i} are independent of the Λ_{j}, necessarily P equals Z_{i}. □

Let β be the size of the SLP encoding the given geometric resolution of W, we are able to compute χ quite easily as a SLP depending on the Λ_{i} and the free variables.

Lemma 7 There exists a deterministic algorithm which computes a SLP of the Chow form χ of W of size polynomial in nβ deg(W), the non-uniform complexity is polynomial in the same quantity.

Proof. Let D be the dimension of B′ and M_{i} be the multiplication matrices of the ρx_{i} for r + 1 ≤ i ≤ n, in the basis 1, u, …, u^{D−1}. The matrix Λ_{r+1}M_{r+1} + ⋯ + Λ_{n}M_{n} is the multiplication matrix by ρU, let Ψ(T) be its characteristic polynomial, then χ(T) equals Ψ(ρT)/ρ^{D}, this division is exact. Since the matrices have size D × D and D is at most the degree of W, their construction can be done with a complexity polynomial in nβ deg(W). We use Berkowitz’ algorithm [2, 1] to compute the characteristic polynomial and “Vermeidung von Divisionen” [22] to compute the exact division, this yields the claimed complexity. □

We are now ready to explain the minimization method. Let M be a component of one the V_{i}^{J} for i > 0, testing whether M is included in one of the V_{j}^{J} with j < i is equivalent to testing if a Zariski dense subset of M is included or not. Let y, u, q, ρ, v be the components of a geometric resolution of M and χ be the Chow form of V_{j}^{J} expressed in the variables y. The condition of the above lemma can be restated as: M is included in V_{j}^{J} if and only if χ(y_{1}, …, y_{n−i}, v_{n−i+1}(u)/ρ, …, v_{n}(u)/ρ) reduces to zero modulo q or not (in k(y_{1}, …, y_{n−i})[T]).

Lemma 8 Let β_{j} be the size of the SLP encoding a geometric resolution of V_{j}^{J}, for 0 ≤ j ≤ n, and D_{j} be the degree of V_{j}^{J}, there exists a deterministic algorithm with non-uniform complexity polynomial in n(β_{1}D_{1} + ⋯ + β_{i}D_{i}) which computes a geometric resolution of V_{i}^{I} of size polynomial in the same quantity.

Proof. With the above notations, χ_{j}, the Chow form of V_{j}^{J} can be computed in time polynomial in nβ_{j}D_{j}. Proposition 4 of the appendix applied on the product of the χ_{j}, j < i, yields the claimed complexity. □.

Proof of Theorem 1 Let C still be Lnsdδ. Since the output of the first part of the algorithm is polynomial in C and the degrees of all the V_{i}^{J} are bounded by dδ, the minimization part is also polynomial in C. This proves the first part of Theorem 1. For the second part, it suffices to put together the probabilities that the election of the t_{i,j} leads to a sequence of g_{i} satisfying the properties R_{1} and R_{2} of Propositions 1 and 3.

Appendix: Splitting a Resolution

Let W be an equidimensional variety of codimension i, given by a geometric resolution encoded by a SLP of size β. Let h be a polynomial in k[x_{1}, …, x_{n}], we explain in this section how one can split the given geometric resolution into two parts, one for the components of W included in the hypersurface defined by h = 0 and the other for the rest.

Let r = n − i and the notations of the geometric resolution be:

• M represents an invertible matrix with entries in k, the coordinates in Noether position are y = M^{−1}x: the variables y_{1}, …, y_{r} are free.

• u = λ_{r+1}y_{r+1} + ⋯ + λ_{n}y_{n} is the primitive element, the λ_{i} are in k.

• q is the minimal polynomial of u, monic in u.

• ρy_{j} = v_{j}(u), for r+1 ≤ j ≤ n are the parametrizations, ρ is polynomial in the free variables and the v_{j} are polynomial in the free variables and u.

Let A(y_{1}, …, y_{r}, u) denote

h ∘ M(y_{1}, …, y_{r}, v_{r+1}(u)/ρ, …, v_{n}(u)/ρ),

q_{1}(u) be the greatest common divisor of A and q in k(y_{1}, …, y_{r})[u], and let q_{2} = q/q_{1}. Since q is monic and polynomial in the free variables, q_{1} and q_{2} are also monic and polynomial in the free variables. We set GR_{i} the geometric resolution defined by M, u, q_{i}, ρ and the remainders of the v_{j} modulo q_{i}, for i = 1, 2. The resolution GR_{1} (respectively GR_{2}) is a geometric resolution of the components W_{1} (respectively W_{2}) of W included (respectively not included) in the hypersurface defined by h = 0. Our aim is now to give a bound on the size of the SLP of the GR_{i} in function of β.

Proposition 4 Let L_{h} be the size of the SLP encoding h, d_{h} a bound on the total degree of h, booth GR_{1} and GR_{2} can be computed by a deterministic algorithm in non-uniform time polynomial in nL_{h}d_{h}β deg(W). The sizes of the resulting SLP are polynomial in nL_{h}d_{h}β deg(W).

Proof. Let H be the homogenized polynomial with respect to the new variable y_{0} of h ∘ M can be computed in time polynomial in nL_{h}d_{h}, the resulting SLP having size also polynomial in nL_{h}d_{h}. Now let B = H(ρ, ρy_{1}, ldots, ρy_{r}, v_{r+1}(u), …, v_{n}(u)), B is proportional to A up to a ρ^{d_{h}} and its SLP is polynomial in nL_{h}d_{h}β. Using [11, Lemma 10] the greatest common divisor of B and q can be computed in time polynomial in nL_{h}βd_{h}β deg(W), this gives q_{1} and q_{2}. □

Conclusion

Our algorithm for computing a minimal geometric resolution of an algebraic variety gives as a byproduct the degree of the variety, and if we are looking for an irreducible decomposition it is sufficient to factorize the minimal polynomials of the computed geometric resolutions.

With our experience in implementing algorithms using SLP [8, 12, 18] we expect to have soon an implementation of the method presented here.

References

[1] Abdeljaoued, J. Algorithmes rapides pour le Calcul du Polynôme Caractéristique. PhD thesis, Université de Franche Comté, Besançon, France, 1997.

[2] Berkowitz, S. J. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters 18 (1984), 147–150.

[3] Chistov, A. L., and Grigoriev, D. Y. Subexponential time solving systems of algebraic equations. LOMI preprint E-9-83, E-10-83, Steklov Institute, Leningrad, 1983.

[4] Elkadi, M., and Mourrain, B. A new algorithm for the geometric decomposition of a variety. In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation (1999), S. Dooley, Ed.

[5] Fitchas, N., Giusti, M., and Smietanski, F. Sur la complexité du théorème des zéros. In Approximation and Optimization in the Caribbean II, Proceedings 2nd Int. Conf. on Non-Linear Optimization and Approximation, J. Guddat, Ed., vol. 8 of Approximation and Optimization. Peter Lange Verlag, Frankfurt am Main, 1995, pp. 247–329.

[6] Gathen von zur, J. Parallel arithmetic computations: a survey. In Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science (Bratislava, Czechoslovakia, Aug. 1986), B. R. J. Gruska and J. Wiedermann, Eds., vol. 233 of LNCS, Springer, pp. 93–112.

[7] Giusti, M., Hägele, K., Heintz, J., Morais, J. E., Montaña, J. L., and Pardo, L. M. Lower bounds for diophantine approximation. Journal of Pure and Applied Algebra 117,118 (1997), 277–317. Proceedings of MEGA’96.

[8] Giusti, M., Hägele, K., Lecerf, G., Marchand, J., and Salvy, B. The projective noether Maple package: Computing the dimension of a projective variety. GAGE laboratory, manuscript, 1998.

http://www.gage.polytechnique.fr/gage/notes/1998.html.

[9] Giusti, M., and Heintz, J. Algorithmes - disons rapides - pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionelles. In Proceedings of MEGA’90 (1991), T. Mora and C. Traverso, Eds., vol. 94 of Progress in Mathematics, Birkhäuser, pp. 169–194.

[10] Giusti, M., and Heintz, J. La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial. In Computational Algebraic Geometry and Commutative Algebra (1993), D. Eisenbud and L. Robbiano, Eds., vol. XXXIV of Symposia Matematica, Cambridge University Press, pp. 216–256.

[11] Giusti, M., Heintz, J., Morais, J. E., Morgenstern, J., and Pardo, L. M. Straight–line programs in geometric elimination theory. J. of Pure and App. Algebra 124 (1998), 101–146.

[12] Giusti, M., Lecerf, G., and Salvy, B. A Gröbner free alternative for polynomial system solving. Journal of Complexity (2000). To appear.

[13] Heintz, J. Definability and fast quantifier elimination in algebraically closed fields. Theor. Comput. Sci. 24, 3 (1983), 239–277.

[14] Heintz, J. On the computational complexity of polynomials and bilinear mappings. A survey. In Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-5 (1989), vol. 356 of LNCS, Springer, pp. 269–300.

[15] Heintz, J., and Schnorr, C. P. Testing polynomials which are easy to compute. In Logic and Algorithmic (1982), vol. 30 of Monographie de l’Enseignement Mathématique, pp. 237–254.

[16] Kleiman, S. L. Bertini and his two fundamental theorems. In Rendiconti del circolo matematico di Palmero (1997).

[17] Krick, T., and Pardo, L. M. Une approche informatique pour l’approximation diophantienne. C. R. Acad. Sci. Paris 318, 1 (1994), 407–412.

[18] Lecerf, G. Kronecker version 0.1, July 1999.

http://kronecker.medicis.polytechnique.fr/.

[19] Samuel, P. Méthodes d’algèbre abstraite en géométrie algébrique, 2nd ed. Springer-Verlag, 1967.

[20] Schost, E. Computing parametric geometric resolutions. GAGE laboratory, manuscript submitted to IS-SAC’2000, January 2000.

http://www.gage.polytechnique.fr/gage/notes/2000.html.

[21] Strassen, V. Berechnung und Programm. I, II. Acta Informatica 1, 4 (1972), 320–355; ibid. 2(1), 64–79 (1973).

[22] Strassen, V. Vermeidung von divisionen. Crelle J. Reine Angew. Math, 264 (1973), 182–202.

[23] T. Krick, L. P., and Sombra, M. Sharp estimates for the arithmetic Nullstellensatz. December 1999.

[24] Zippel, R. Probabilistic algorithms for sparse polynomials. In Proceedings EUROSAM’ 79 (1979), no. 72 in LNCS, Springer, pp. 216–226.

[25] Zippel, R. Effective Polynomial Computation. Kluwer Academic Publishers, 1993.