TORIC GENERALIZED CHARACTERISTIC POLYNOMIALS

J. MAURICE ROJAS

Abstract. We illustrate an efficient new method for handling polynomial systems with degenerate solution sets. In particular, a corollary of our techniques is a new algorithm to find an isolated point in every excess component of the zero set (over an algebraically closed field) of any n by n system of polynomial equations. Since we use the sparse resultant, we thus obtain complexity bounds (for converting any input polynomial system into a multilinear factorization problem) which are close to cubic in the degree of the underlying variety — significantly better than previous bounds which were pseudo-polynomial in the classical Bézout bound. By carefully taking into account the underlying toric geometry, we are also able to improve the reliability of certain sparse resultant based algorithms for polynomial system solving.

1. Introduction

The rebirth of resultants, especially through the toric^{1} resultant [GKZ94], has begun to provide a much needed alternative to Gröbner basis methods for solving polynomial systems. Continuing this philosophy, we will present a new, fast and reliable, resultant-based method for handling certain degenerate polynomial systems. Simply put, we refine and generalize the generalized characteristic polynomial (GCP) [Can90, Shu93] to take sparsity into account. Furthermore, we introduce the concept of a twisted Chow form in order to completely avoid any degeneracies within our algorithm.

The importance of dealing with degenerate polynomial systems has been observed in earlier work on quantifier elimination over algebraically closed fields [CG84, Ren87, Can88]: Many reasonable algorithms fail catastrophically when presented with an n by n system having positive-dimensional zero set. When such is the case, it is of considerable benefit to the user to at least be given some sort of description of the zero-dimensional part of the zero set. This was a benefit of Canny’s original GCP, but he remarked [Can90, pg. 242] “For large, dense problems however, the resultant and GCP methods should be faster [than Gröbner algorithms].” Our construction, the toric GCP, promises to be much more competitive when applied to sparse systems in such a comparison.

Date: February 10, 1997.

This research was completed at MIT and was partially funded by an N.S.F. Mathematical Sciences Postdoctoral Fellowship. Research at MSRI is supported in part by NSF grant DMS-9022140.

1Other commonly used prefixes for this more modern generalization include: sparse, mixed, A-, and (A_{1}, …, A_{k})-.

Remark 1. It should be emphasized that perturbation methods for degenerate systems (such as the toric GCP) are of the greatest importance when working with exact arithmetic. However, floating point polynomial system solving also benefits from a complete and rigourous understanding of the potential degeneracies within exact arithmetic, e.g., [Sma87]. In any case, it is frequently the case in many applications that “real life” happens to land in a measure 0 exception which breaks an algorithm.

In what follows, we will frequently use multi-index notation in order to precisely control which monomial terms are allowed to appear in our polynomial systems.^{2} This notation, and in particular, supports and Newton polytopes, are amply detailed in earlier works of Emiris [Emi94], Huber [Hub96], Gelfand et. al. [GKZ90, GKZ94], Rojas [Roj94, Roj97b], Sturmfels [Stu93], and Verschelde [Ver96], to mention but a few authors and references.

Since what we will present is at heart a perturbation method, we will first need the following definition to construct certain polynomial systems in “general position.”

Definition 1. [Roj94, RW96] Given n-tuples D:=(D_{1}, …, D_{n}) and E:=(E_{1}, …, E_{n}) of nonempty finite subsets of ℤ^{n}, we say that D fills E iff (0) D_{i} ⊆ E_{i} for all i ∈ [n] and (1) M(D) = M(E). An irreducible fill is then simply a fill which is minimal with respect to n-tuple containment. If D or E is instead an n-tuple of polytopes in ℝ^{n}, then we will use the same definition.

In the above, M(E) denotes the mixed volume [BZ88, Sch94, EC95, DGH96] of the convex hulls of the E_{i}, and we use [j] for the set of integers {1, …, j}.

Our construction is summarized in the following definition and main result. (Henceforth, all of our polynomials and roots are to be considered over an algebraically closed field K.)

Definition 2. Suppose F is an n×n polynomial system with support contained in E and g(x) := ∑_{e∈A} u_{e}x^{e}, where the u_{e} are algebraically independent indeterminates and A⊂ℤ^{n} is nonempty and finite. Assume further that M(E)>0 and A has at least two elements. Letting D be an irreducible fill of E, F^{∗} := (∑_{e∈D_{i}} x^{e} | i ∈ [n]), and u:=(u_{e} | e∈A), define Ch_{A}(u):=Res_{(E,A)}(F, g) and H(u; s):=Res_{(E,A)}(F − sF^{∗}, g), where s is a new indeterminate. We call H a toric generalized characteristic polynomial for (F, A).

In the above, Res_{⋆}(·) denotes the toric resultant. Recall also that to any n-dimensional rational polytope P ⊂ ℝ^{n} one can associate its corresponding toric variety T_{P} [Dan78, KSZ92, Ful93, Roj97b].

2This is what we mean by sparsity, as opposed to working solely in terms of polynomial degrees.

Note that our notion overlaps the case of having very few monomial terms.

Main Theorem. Following the notation of definition 2, consider H as a polynomial in s with coefficients in K[u] and let F_{A}(u) be the coefficient of the lowest degree term of H. Also let P := ∑_{i=1}^{n} Conv(E_{i}), P̃:= P + Conv(A), and φ : TP̃ ⟶ ℙ_{K}^{|A|−1} the natural morphism defined by x ↦ [x^{e} | e ∈ A] (cf. section 4). Then F_{A} is a homogeneous polynomial, of degree M(E), with the following properties:

0. The constant term of H(s) is precisely Ch_{A}. In particular, letting Z be the zero set of F in TP̃, Ch_{A} ≡0 ⟺ φ(Z) is positive-dimensional.

1. If ζ ∈ TP̃ is an isolated root of F then F_{A} is divisible by ∑_{e∈A} c_{e}u_{e}, where [c_{e} | e∈A]=φ(ζ).

2. If a nonzero linear form ∑_{e∈A} c_{e}u_{e} divides F_{A} then [c_{e} | e∈A]=φ(ζ) for some root ζ ∈TP̃ of F.

3. F_{A} splits completely into linear factors. In particular, under the correspondence of (2), we can explicitly find at least one root of F within every positivedimensional irreducible component of the zero set of F in TP̃.

We call F_{A} a toric perturbation of Ch_{A}.

A complete criterion for finding fills is given in theorem 1 of section 3 and some simple examples of filling (and our Main Theorem) appear in section 2. Compatibility is defined in section 4. There we also detail what is meant by the zero set of F in a toric variety.

Remark 2. Alternatively, if one wants to avoid filling, one can substitute for F^{∗} any polynomial system (with support contained in E) known to have exactly M(E) roots (counting multiplicities) in (K^{∗})^{n}. So one can also view filling as a deterministic way of explicitly constructing a “generic” polynomial system.

So how does one actually use the above theorem? One simple example is the sparse u-resultant [Emi94], which is simply a variant of the classical u-resultant [Van50]. It can be defined simply as Ch_{A}(u) where A is the vertex set of the standard n-simplex in ℝ^{n}. One useful (and easily verified) property of the sparse u-resultant is that F has a root ζ:=(ζ_{1}, …, ζ_{n})∈(K^{∗})^{n} ⟹ u_{0} + ζ_{1}u_{1} + ⋯ + ζ_{n}u_{n} divides Ch_{A}(u). So, assuming Ch_{A}(u) is not identically 0 (and that one has good software for toric resultants and multivariate factoring), one can find the isolated roots of F simply by factoring Ch_{A}(u). Thus the degenerate instances Ch_{A}(u)≡0 obstruct this reduction to factoring and our Main Theorem allows us to avoid this problem: Simply use F_{A}(u) instead of Ch_{A}(u).

Remark 3. An interesting “failure” for the classical u-resultant is the case where F has only finitely many roots in affine space, while having infinitely many in projective space. This is where the classical GCP is especially handy. For the toric GCP, the toric variety T_{P} plays the role of projective space. This is part of the philosophy of sparse elimination theory: working in a well chosen toric compactification (depending on F) leads to better algorithms than if one were to work only in projective space.

In particular, lifting to TP̃ helps us detect precisely when the sparse u-resultant is identicaly 0.

However, there is a stickier subtlety which occurs with the sparse u-resultant: It is possible for F to have only finitely many roots within T_{P} with Ch_{A}(u) still vanishing identically (cf. section 2.3). This is the motivation for twisted Chow forms, which are defined below, and pursued at much greater length in [Roj97c].

Corollary and Definition 3 (cf. section 4). Following the notation of our Main Theorem, pick A to be the vertices of a product of simplices with which P is compatible. We then call Ch_{A}(u) the twisted Chow form of the zero set of F with respect to A. Furthermore, a twisted Chow form does not vanish identically if F has only finitely many roots in T_{P}.

In particular, since our last construction implies that T_{Conv(A)} is a product of twisted projective spaces [Ful93], the coefficients of a twisted Chow form are actually multisymmetric functions [DS95, Roj97a] of projections (by φ) of roots of F (in T_{P}) onto this product. So twisted Chow forms generalize the u-resultant, the sparse u-resultant, and (suitably extended [Roj97c]) the Chow form of a projective variety [DS95]. Moreover, when combined with the Smith normal form [Ili89, HM91, HS95] and the toric GCP, twisted Chow forms give a considerably more reliable method for solving polynomial systems than the sparse u-resultant [Roj97c].

An important difference to note is that our present toric GCP is primarily suited for finding roots in (K^{∗})^{n}, while the original GCP is mainly suited (in a “non-sparse” way) for affine space. To completely generalize and improve the GCP in affine space, it is necessary to use the affine sparse resultant and this is pursued further in [Roj97e]. For instance, by replacing the sparse resultant with the affine sparse resultant, and using K^{n}-counting [Roj97b] instead of filling, we can actually recover Canny’s GCP in the dense case.

We close this introduction with a word on the computational complexity of computing the toric GCP. Neglecting preprocessing (finding an irreducible fill and finding a mixed subdivision in order to set up the toric resultant matrices [EC95]), recent work of Emiris, Morrain, and Pan [EP97, MP97] suggests that it is possible to find the perturbation F_{A} within a number of arithmetic steps^{3} which is close to cubic in M(E). (Indeed, Canny has pointed out [Can90] that the original GCP can be computed in time close to cubic in the Bézout bound, which would be a special case of time cubic in M(E).) Since M(E) is much smaller than the Bézout number for most polynomial systems [Roj94, Roj97b], these preliminary results suggest that the toric GCP has considerable potential for practical applications.

Let us now illustrate some of our theory.

3Although the possibility of “near-quadratic” algorithms for polynomial system solving is discussed in [EP97, MP97], neither paper discusses the case where the zero set of F is positivedimensional, which is our main concern here.

2. Examples

We begin with two small examples of filling. We then see applications of the toric GCP to some degenerate 2 × 2 and 3 × 3 polynomial systems. Finally, we see a brief comparison of the toric GCP to the original GCP.

2.1. Filling Squares and Cubes. For our first example, consider the pair of rectangles P:=([0, a]×[0, b], [0, c]×[0, d]) where a, b, c, and d are positive integers. Then it is easily verified (via theorem 1 of section 3) that the pair

D:=({(0, 0), (a, b)}, {(0, d), (c, 0)})

fills P. In this case, the mixed area of both pairs is easily checked to be ad+bc. Note also that D is a pair of oppositely slanting diagonals of our initial pair of rectangles (modulo taking convex hulls). Finally, it is easily checked that D is indeed irreducible, since the removal of any point of D results in a mixed area of 0.

For our second example, let P instead be a triple of standard cubes (so that the vertex set of each cube is simply {0, 1}^{3}). Then, using the criterion from theorem 1 once again, it is easily verified that the triple

D:=({(0, 0, 0), (1, 1, 1)}, {(1, 0, 0), (0, 1, 0), (0, 0, 1)}, {(1, 1, 0), (1, 0, 1), (0, 1, 1)})

fills P. Also, it is easily checked that the mixed volume of both triples is 6. Note that the triple D consists of a body diagonal and two oppositely oriented (but parallel) sub-triangles of the unit cube, modulo taking convex hulls. Finally, note that this D is irreducible as well by theorem 1. (This is also easily checked by one of the publically available software packages for mixed volume by Emiris, Huber, or Verschelde.)

2.2. A Degenerate 2 × 2 System. Consider the bivariate polynomial system F:= (1 + 2x − 2x^{2}y − 5xy + x^{2} + 3x^{3}y, 2 + 6x − 6x^{2}y − 11xy + 4x^{2} + 5x^{3}y). Letting E be the support of F, the reader can easily verify that M(E) = 4, and that the only roots of F are the points \{(1, 1), (\frac{1}{7}, \frac{7}{4})\} and the line \{−1\}×K (assuming charK ≠2).^{4} So it would appear that the u-resultant (and even the sparse u-resultant) will vanish identically and not give us any useful information about any of these roots. Let us see if perturbing the sparse u-resultant helps...

Note that by theorem 1, D:=({O, (3, 1)}, {(1, 1), (2, 0)}) is an irreducible fill of E. So applying our Main Theorem with this D (and A:= {(0, 0), (1, 0), (0, 1)}) one can compute with the use of Maple that H(u; s) is precisely

(u_{2}^{4} − u_{0}^{4} + u_{1}^{4} + 6u_{1}^{2}u_{2}^{2} − 4u_{1}u_{2}^{3} − 4u_{1}^{3}u_{2})s^{8}

+(−20u_{2}u_{0}^{3} − 20u_{2}^{3}u_{0} − 4u_{1}u_{0}^{3} + 36u_{1}^{2}u_{2}^{2} − 19u_{0}^{4} − 24u_{2}^{4} + 6u_{0}^{2}u_{1}u_{2}
+36u_{1}u_{2}^{3} + 36u_{1}^{4} − 12u_{0}u_{1}^{2}u_{2} − 9u_{1}^{2}u_{0}^{2} + 3u_{2}^{2}u_{0}^{2} + 36u_{0}u_{1}u_{2}^{2} − 4u_{0}u_{1}^{3} − 84u_{1}^{3}u_{2})s^{7}
+(−170u_{2}u_{0}^{3} − 394u_{1}^{3}u_{2} − 98u_{1}u_{0}^{3} − 98u_{0}^{2}u_{1}u_{2} − 20u_{0}^{4} + 220u_{2}^{4} + 370u_{2}^{3}u_{0}

4When charK =2, the second isolated root becomes an isolated root lying on the x-axis.

+14u_{0}u_{1}u_{2}^{2} − 110u_{0}u_{1}^{3} − 226u_{1}^{2}u_{0}^{2} − 354u_{1}^{2}u_{2}^{2} + 454u_{1}^{4} − 274u_{0}u_{1}^{2}u_{2} + 74u_{1}u_{2}^{3})s^{6}
+(−1612u_{0}^{2}u_{1}u_{2} + 1008u_{2}u_{0}^{3} + 903u_{0}^{4} − 624u_{1}u_{0}^{3} − 2632u_{2}^{3}u_{0} − 2104u_{0}u_{1}^{2}u_{2} − 970u_{2}^{4}

−1010u_{1}u_{2}^{3} + 418u_{1}^{3}u_{2} − 2104u_{0}u_{1}u_{2}^{2} − 642u_{1}^{2}u_{2}^{2} − 1547u_{1}^{2}u_{0}^{2} − 936u_{0}u_{1}^{3} − 1557u_{2}^{2}u_{0}^{2} + 2204u_{1}^{4})s^{5}

+(538u_{0}^{2}u_{1}u_{2} + 1271u_{0}^{4} + 12253u_{2}^{2}u_{0}^{2} + 6972u_{2}u_{0}^{3} + 1929u_{1}^{4} − 3075u_{1}^{2}u_{2}^{2} + 654u_{0}u_{1}u_{2}^{2}

+50u_{1}u_{0}^{3} + 2156u_{2}^{4} − 960u_{1}^{2}u_{0}^{2} − 2290u_{0}u_{1}^{3} + 132u_{1}u_{2}^{3} − 5344u_{0}u_{1}^{2}u_{2} − 1142u_{1}^{3}u_{2} + 8708u_{2}^{3}u_{0})s^{4}

+(4384u_{1}u_{0}^{3} − 24988u_{2}^{2}u_{0}^{2} − 1582u_{1}^{3}u_{2} − 6756u_{0}^{4} + 10884u_{0}u_{1}u_{2}^{2} + 3802u_{1}u_{2}^{3} + 15438u_{0}u_{1}^{2}u_{2}

+1024u_{0}u_{1}^{3} + 8324u_{1}^{2}u_{0}^{2} − 12826u_{2}^{3}u_{0} + 11270u_{0}^{2}u_{1}u_{2} − 6976u_{1}^{4} + 7164u_{1}^{2}u_{2}^{2} − 21326u_{2}u_{0}^{3} − 2408u_{2}^{4})s^{3}

+(3436u_{1}^{3}u_{2} + 3800u_{0}u_{1}^{3} + 7756u_{2}^{3}u_{0} − 3886u_{1}u_{2}^{3} + 1225u_{2}^{4} + 17059u_{2}^{2}u_{0}^{2} − 5984u_{1}^{2}u_{0}^{2}

+15708u_{2}u_{0}^{3} − 12232u_{0}u_{1}u_{2}^{2} + 5180u_{0}^{4} − 2091u_{1}^{2}u_{2}^{2} − 6828u_{0}u_{1}^{2}u_{2} + 1316u_{1}^{4} − 12700u_{0}^{2}u_{1}u_{2} − 4312u_{1}u_{0}^{3})s^{2}

+(−196u_{2}^{4} − 448u_{0}^{4} − 768u_{1}^{3}u_{2} + 512u_{1}^{2}u_{0}^{2} − 1288u_{2}^{3}u_{0}
−2436u_{2}^{2}u_{0}^{2} + 1920u_{0}u_{1}u_{2}^{2} + 1536u_{0}^{2}u_{1}u_{2} + 1024u_{0}u_{1}^{2}u_{2}
+384u_{1}u_{0}^{3} − 1792u_{2}u_{0}^{3} − 384u_{0}u_{1}^{3} + 768u_{1}u_{2}^{3} + 260u_{1}^{2}u_{2}^{2} − 64u_{1}^{4})\underline{s}.

(Sparse resultants of this size are quite amenable with the aid of Maple, following the technique of a similar computation in [Roj97a].) So our F_{A} is just the coefficient of s or s^{2} in this polynomial, according as charK ≠ 2 or charK = 2. To simplify our discussion, let us henceforth assume the former possibility.

Factoring with Maple, we obtain that F_{A} can be written as follows:

−4(u_{0} + u_{1} + u_{2})(28u_{0} + 4u_{1} + 49u_{2})(u_{0} − u_{1} + u_{2})(4u_{0} − 4u_{1} + u_{2})

In particular, given any factor above, the ratio of the coefficients of u_{i} and u_{0} is precisely the i\underline{th} coordinate of a corresponding root of F. Thus the first two factors correspond precisely to the two isolated roots we already know. As for the last two factors, note that they both give isolated points lying on the aforementioned line {−1}×K. This can be interpreted as assigning an excess intersection multiplicity of 2 to the line, so that the sum of all intersection numbers (of the irreducible components of the zero set of F in TP̃) is 4.

Note that the original GCP could have been used above but would have resulted in a u-form of degree 16 (the product of the degrees of f_{1} and f_{2}). Also, the corresponding version of H(·) is significantly larger, having 672 terms, compared to 110 for our above toric GCP.

2.3. Stranger Degeneracies. Here we give two examples showing how the sparse u-resultant can fail to find roots in T_{P}, even with the benefit of the toric GCP, unless some other construction (such as a twisted Chow form) is used.

First consider the parameterized bivariate system F := (a_{1}y + a_{2}x + a_{3}xy, b_{1}y + b_{2}x + b_{3}xy). Note that the mixed volume bound for this system is 1. The sparse u-resultant for this system is also easily found (using the same techniques as in our last example) to be:

(a_{3}^{2}b_{2}b_{1} + b_{3}^{2}a_{2}a_{1} − b_{3}a_{2}a_{3}b_{1} − b_{3}a_{3}b_{2}a_{1})u_{0}
+ (b_{1}^{2}a_{2}a_{3} − b_{1}b_{3}a_{2}a_{1} − b_{2}a_{1}a_{3}b_{1} + b_{2}b_{3}a_{1}^{2})u_{1}
+ (b_{1}b_{3}a_{2}^{2} − b_{2}a_{2}a_{3}b_{1} + b_{2}^{2}a_{3}a_{1} − b_{2}b_{3}a_{2}a_{1})u_{2}

In particular, we see that when

(a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3})=(0, 1, 2, 0, 1, 3).

the sparse u-resultant vanishes identically. For this specialization, it is also easy to see that F has only one root in T_{P}, and this root lies at the point of T_{P} corresponding to the vertex (0, 1) of P (cf. lemma 1 from section 4), following the notation of our Main Theorem. In fact, for this P, T_{P} ≅ ℙ_{K}^{2} and the vertex (0, 1) corresponds precisely to the point [x : y : z] = [1 : 0 : 0] in this particular copy of ℙ_{K}^{2} (z denoting an extra variable for homogenizing).

There are two ways of viewing this degeneracy (Ch_{A}(u)≡0 while F has only finitely many roots in T_{P}) of the sparse u-resultant. The first is pragmatic: One should not count this as a deficiency of the sparse u-resultant because we’ve cheated and set two of the coefficients of F to 0, thus changing the supports. (Our next example avoids this trick.) The second point of view is more geometric: By our Main Theorem, this particular sparse resultant must vanish due to the fact that our specialization of F results in the existence of infinitely many roots of F in TP̃. In fact, F vanishes on the 1-dimensional subvariety of TP̃ corresponding to the left-hand vertical edge of the hexagon P̃ (cf. section 4).

Going one dimension higher, consider instead the 3 × 3 system G, consisting of the following polynomials:

a_{1}yz + a_{2}xz + a_{3}xy + a_{4}xyz
b_{1}yz + b_{2}xz + b_{3}xy + b_{4}xyz
c_{1}yz + c_{2}xz + c_{3}xy + c_{4}xyz

Note that the mixed volume bound for this system is again 1.

Clearly, \frac{1}{xyz}G is a linear system in \{\frac{1}{x}, \frac{1}{y}, \frac{1}{z}\}. So by Cramer’s rule, we can express x, y, and z as ratios of 3 × 3 determinants in the coefficients. Combining this with the product formula for toric resultants [PS93] (and clearing denominators) we obtain that the sparse u-resultant of G is precisely^{5}

[423][143][124]u_{0} + [123][143][124]u_{1} + [123][423][124]u_{2} + [123][423][143]u_{3}

where the bracket [ijk] [DS95] is the 3 × 3 subdeterminant

|\begin{matrix}a_{i} & a_{j} & a_{k} \\ b_{i} & b_{j} & b_{k} \\ c_{i} & c_{j} & c_{k} \end{matrix}|

of the coefficient matrix of G. This compactly expressed resultant can be thought of as a semi-mixed Chow form — a toric resultant of a semi-mixed system [HS95], compressed in terms of suitable brackets.

Now consider the specialization of G to

yz + xz + 2xy + 3xyz
yz + xz + 4xy + 9xyz
yz + xz + 8xy + 27xyz

It is then easily verified that G has exactly one root in T_{P} ≅ℙ_{K}^{3}:

[x : y : z : w]=[1 : −1 : 0 : 0]

(w denoting an extra variable for homogenizing).^{6} More to the point, the sparse u-resultant vanishes identically for this specialization of G, even though G has no zero coefficients. Furthermore, one can easily check that the correspondence of (2) (from our Main Theorem) does not give us the root of G in T_{P}. (Using D := ({(0, 1, 1), (1, 1, 1)}, {(1, 0, 1), (1, 1, 1)}, {(1, 1, 0), (1, 1, 1)}), the coefficients of the u_{i} in F_{A} suggest the nonsensical root [0 : 0 : 5 : 21].)

To remedy this, we can use the twisted Chow form Ch_{A′}(u) with

A′:={(0, 1, 1), (1, 0, 1), (1, 1, 0), (1, 1, 1)}.

In particular, when the coefficients of G are unspecialized,

Ch_{A′}(u) = |\begin{matrix}a_{1} & a_{2} & a_{3} & a_{4} \\ b_{1} & b_{2} & b_{3} & b_{4} \\ c_{1} & c_{2} & c_{3} & c_{4} \\ u_{(0,1,1)} & u_{(1,0,1)} & u_{(1,1,0)} & u_{(1,1,1)} \end{matrix}|

5We also need the fact that the Pedersen-Sturmfels formula, originally stated only over ℂ, remains true over a general algebraically closed field. This is proved in [Roj97d].

6If charK ∈ {2, 3} then G will actually have infinitely many roots in T_{P}. So let us assume henceforth that charK ∉ {2, 3}. (It is easy to construct similar examples when charK ∈ {2, 3} as well.)

So under our last specialization, this becomes 12u_{(1,0,1)} − 12u_{(0,1,1)}. Thus the coordinates of the sole root of G in T_{Conv(A′)} ≅ℙ_{K}^{3} are precisely [1 : −1 : 0 : 0]. To conclude, by virtue of our (compatible) choice of A′, the natural embeddings of (K^{∗})^{3} into T_{P} and T_{Conv(A′)} are identical. This is how we’ve recovered our root in T_{P}.

In closing, note that in practice we would never actually compute H(u; s) — we would instead recover F_{A} via rapid and sophisticated interpolation techniques, e.g., [Zip93]. In particular, our calculations can be sped up tremendously with suitably specialized code.

2.4. The “Dense” Case. Our last example illustrates a simple fundamental case.

Suppose E is the n-tuple (d_{1}Δ, …, d_{n}Δ) where Δ ⊂ ℝ^{n} is the vertex set of the standard n-simplex in ℝ^{n} and d_{i} ∈ℕ for all i. It is then easily verified that the n-tuple D := ({O, d_{1}ê_{1}}, …, {O, d_{n}ê_{n}}) is an irreducible fill of E (cf. theorem 1). Letting A=Δ, we see that our polynomial H is a variant (over a general algebraically closed field) of the original GCP applied to an n×n system of polynomials with degrees d_{1}, …, d_{n} [Can90]. In particular, our F − sF^{∗} has 2n s-monomials, compared to the n s-monomials in Canny’s (f_{1} − sx_{1}^{d_{1}}, …, f_{n} − sx_{n}^{d_{n}}). Note also that Conv(A) and P are homothetic and T_{P} ≅ ℙ_{K}^{n}. Neglecting the extra s-monomials, setting d_{i} = 1 for all i, and suitably specializing the coefficients of g, we can then recover the usual characteristic polynomial of a matrix.

3. Filling

Here we briefly recount filling and some related concepts. Some of the material below is covered at greater length in [Roj94]. The paper [Stu94] is also a useful reference but deals more with the sparse resultant than with filling. The results below form the basis for our combinatorial approach to perturbing degenerate polynomial systems.

Let S^{n−1} ⊂ ℝ^{n} denote the unit (n − 1)-sphere centered at the origin. For any compact B ⊂ ℝ^{n} and any w ∈ ℝ^{n}, define B^{w} to be the set of x ∈ B where the innerproduct x·w is minimized. (Thus B^{w} is the intersection of B with its supporting hyperplane in the direction w.) We then define E^{w}:= (E_{1}^{w}, …, E_{n}^{w}) and D∩E^{w}:= (D_{1} ∩ E_{1}^{w}, …, D_{n} ∩ E_{n}^{w}).

Recall that the dimension of any B ⊆ℝ^{n}, dim B, is the dimension of the smallest subspace of ℝ^{n} containing a translate of B. The following definition is fundamental to our development.

Definition 4. Suppose C := (C_{1}, …, C_{n}) is an n-tuple of polytopes in ℝ^{n} or an n-tuple of finite subsets of ℝ^{n}. We will allow any C_{i} to be empty and say that a nonempty subset J ⊆ [n] is essential for C (or C has essential subset J) ⟺ (0) Supp(C) ⊇ J, (1) dim(∑_{j∈J} C_{j}) = |J| − 1, and (2) dim(∑_{j∈J′} C_{j}) ≥ |J′| for all nonempty proper J′ ⫋J.

Equivalently, J is essential for C ⟺ the |J|-dimensional mixed volume of (C_{j} | j ∈ J) is 0 and no smaller subset of J has this property. Figure 1 below shows some simple examples of essential subsets for C, for various C in the case n=2.

[figure: C_{1}; C_{2}; {1}, {2}; C_{1}; C_{2}; {1}; C_{1}; C_{2}; {1, 2}; C_{1}; C_{2}; None]

Figure 1. The essential subsets for 4 different pairs of plane polygons.

(The segments in the third pair are meant to be parallel.)

A basic fact about mixed volumes is that M(E)=0 ⟺ E has an essential subset, whenever Supp(E)=[n]. However, there is an even deeper connection between filling and essentiality:

Theorem 1. [Roj94, sec. 2.5] Suppose D and E are n-tuples of finite subsets of ℤ^{n} such that M(E) > 0. Then D fills E ⟺ for all w ∈ S^{n−1}, Supp(D ∩ E^{w}) contains a subset essential for E^{w}.

Remark 4. One certainly need not check infinitely many w. In fact, we need only check one w (just pick any inner normal) for each face of the polytope ∑_{i=1}^{n} Conv(E_{i}).

Filling is closely related to root counting for sparse polynomial systems, and this aspect is explored much further in [Roj94, RW96, Roj97b]. We also point out that the computational complexity of finding an irreducible fill is an open question. However, for n≤3, finding irreducible fills is quite simple and no harder (asymptotically) than finding a convex hull. (Using theorem 1, this follows as a simple geometric exercise.) In any event, the connection between fills and polynomial system solving (not to mention specialized resultants) appears to be new and, we hope, provides added incentive to investigate filling. Also, even if finding an irreducible fill is too hard, this step of our toric GCP construction need only be done once for a given family of problems, provided E remains fixed. The situation where the monomial term structure of a polynomial system remains fixed once and for all, and the coefficients may vary many thousands of times, actually occurs frequently in many practical contexts such as robot control or computational geometry.

4. Toric Geometry and the Proof of Our Main Theorem

Our notation is a slight variation of that used in [Ful93], and is described at greater length in [Roj97b]. We will assume the reader to be familiar with normal fans of polytopes and the construction of a toric variety from a fan or a finite point set [Ful93, GKZ94]. However, we will at least list our cast of main characters:

Definition 5. [Roj97b] Given any w ∈ℝ^{n}, we will use the following notation: T = The algebraic torus (K^{∗})^{n} P^{w} = The face of P with inner normal w σ_{w} = The closure of the cone generated by the inner normals of P^{w} U_{w} = The affine chart of T_{P} corresponding to the cone σ_{w} of Fan(P) L_{w} = The dim(P^{w})-dimensional subspace of ℝ^{n} parallel to P^{w} x_{w} = The point in U_{w} corresponding to the semigroup homomorphism σ_{w}^{∨} ∩ ℤ^{n} ⟶

{0, 1} mapping p ↦ δ_{w·p,0}, where δ_{ij} denotes the Kronecker delta O_{w} = The T -orbit of x_{w} = The T -orbit corresponding to RelIntP^{w}

E_{P} (Q) = The T -invariant Weil divisor of T_{P} corresponding to a polytope Q. Div(f) = The Weil divisor of T_{P} defined by a rational function f on (K^{∗})^{n}

D_{P} (f, Q) = Div(f) + E_{P} (Q) = The toric effective divisor of T_{P} corresponding to (f, Q) D_{P} (F, P) = The (nonnegative) cycle in the Chow ring of T_{P} defined by ⋂_{i=1}^{k} D_{P} (f_{i}, P_{i}), when-

ever P =(P_{1}, …, P_{k})

We will say that a polytope P is compatible with Q iff every cone of Fan(Q) is a union of cones of Fan(P) [Kho77, Ful93, Roj97b]. In particular, whenever F is an k × n polynomial system with support contained in E, we will define the zero set of F in T_{P} to be the toric cycle D_{P} (F, P), where P:=(Conv(E_{1}), …, Conv(E_{k})).

The following result will provide some necessary geometric intuition for specializing resultants.

Vanishing Theorem for Resultants. [Roj97d] Suppose f_{i} is a polynomial over K with support contained in E_{i} ⊂ℤ^{n} for all i∈[n + 1]. Then, provided

M(E_{1}, …, E_{i−1}, E_{i+1}, …, E_{n+1})>0

for some i∈[n + 1],

ResĒ(f_{1}, …, f_{n+1})=0 ⟺ ⋂_{i=1}^{n+1} DP̃(f_{i}, Conv(E_{i}))≠∅,

where Ē:=(E_{1}, …, E_{n+1}) and P̃:= ∑_{i=1}^{n+1} Conv(E_{i}).

Remark 5. This result provides a geometric analogue, over a general algebraically closed field, of the product formula for the sparse resultant [PS93].

We will also make frequent use of the natural correspondence between the face interiors {RelIntP^{w}} and the T -orbits {O_{w}} [KSZ92, Ful93, GKZ94]. The following lemma gives a more explicit algebraic analogy between the faces of P and the affine charts of T_{P}.

Lemma 1. [Roj97b, Sections 4.2–5.1] Suppose F is a k × n polynomial system over K with support contained in a k-tuple of integral polytopes P := (P_{1}, …, P_{k}) in ℝ^{n}. Assume further that P is a rational polytope in ℝ^{n}. Then the defining ideal in K[x^{e} | e ∈ σ_{w}^{∨} ∩ ℤ^{n}] of U_{w} ∩ D_{P} (F, P) is ⟨x^{b_{i}}f_{i} | for all i ∈ [k] and b_{i} ∈ ℤ^{n} such that b_{i} + P_{i} ⊂ σ_{w}^{∨}⟩.

Lifting (or projecting) from one toric variety to another is an important fundamental ideal we will also use. The following lemma follows directly from the development of [Ful93].

Lemma 2. Suppose P ⊂ ℝ^{n} is an n-dimensional rational polytope, and A is either a nonempty finite subset of ℤ^{n} or a rational polytope in ℝ^{n}. Assume further that P is compatible with Conv(A). Then there is a natural (surjective) proper morphism φ : T_{P} ↠ T_{A}. In particular, following the notation of this section, φ(D_{P} (F, P)) = D_{A}(F, P), where the latter cycle is the image of D_{Conv(A)}(F, P) under the natural proper morphism from T_{Conv(A)} to T_{A}.

Remark 6. Recall that T_{A} can be defined as the image of of TP̃ under the map φ from our Main Theorem. So, with this understanding, there is no ambiguity between our first and second φ.

To conclude our background, we will need the following lemma implying that F^{∗} is sufficiently generic in a useful sense.

Lemma 3. Suppose D is an irreducible fill of some n-tuple E. Then for any point v lying in any D_{i}, there exists a w ∈ℝ^{n}\{O} such that {i} is the unique essential subset of D^{w} and D_{i}^{w} ={v}. In particular, following the notation of our Main Theorem, F^{∗} has exactly M(P) roots (counting multiplicities) in (K^{∗})^{n}.

This lemma follows easily from the techniques of [Roj94], particularly section 2.5.

4.1. The Proof of Our Main Theorem. We first note that the well known results on the degree of ResĒ(f_{1}, …, f_{n+1}) with respect to the coefficients of different f_{i} [Stu94] remain true over any algebraically closed field. This follows easily from the formulation of the resultant for a collection of invertible sheafs on a projective variety [GKZ94]. In particular, the degree of H as a polynomial in s should be

∑_{i=1}^{n} M(E_{1}, …, E_{i−1}, E_{i+1}, …, E_{n}, A).

Also each coefficient of H(s) should be a homogeneous polynomial (in the u_{e}) of degree M(E). These two assertions of course include the opening statement of our Main Theorem (on the degree and homogeneity of F_{A}), but they will follow only upon showing that H is not identically 0.

To see this, note that lemma 1 and the Vanishing Theorem for Resultants readily imply that the coefficient of the highest power of s in H is precisely Res_{(E,A)}(F^{∗}, g). (Simply check the zero set of F −sF^{∗} in TP̃ at s=∞.) By lemma 3, and the Vanishing Theorem once more, we see that this polynomial in the u_{e} is not identically 0. So H≢0 and we’ve finished the simplest part of our proof.

Part (0) of our Main Theorem follows similarly: One need only consider the unspecialized resultant polynomial Res_{(E,A)}(F, g) and observe the terms of degree 0 in s as we specialize coefficients to obtain F − sF^{∗}. The statement on the vanishing of Ch_{A} then follows easily from lemma 2 (since P̃ is compatible with Conv(A)) and the Vanishing Theorem: We obtain that φ(Z) is positive-dimensional iff Ch_{A} has infinitely many distinct divisors of the form ∑_{e∈A} c_{e}u_{e}. In particular, corollary 3 follows as a special case of (0) since P compatible with Conv(A) ⟹ T_{P} =TP̃. Note that (1), (2), and (3) also follow almost trivially, provided Ch_{A} is not identically 0.

To properly handle the cases of (1), (2), and (3) where we are actually working with a non-trivial toric perturbation, let us first construct two important toric cycles: Let Z̄ be the zero set of F −sF^{∗} in TP̃ ×ℙ_{K}^{1} and Z̄_{+}^{∨} the zero set of H(u; s) in ℙ_{K}^{|A|−1} ×ℙ_{K}^{1}. Then it is easily observed that Z = Z̄ ∩ (TP̃ × {0}). Also, it can be shown [Roj97b, Section 5.1] that Z̄ contains an algebraic curve C (possibly reducible), with surjective projection onto the second factor of TP̃ × ℙ_{K}^{1}, obeying the following property: C ∩ (TP̃ × {0}) contains the zero-dimensional part of Z, and consists of exactly M(E) points (counting multiplicities). (In fact, Z̄ ∩(TP̃ ×{s_{0}})=C ∩(TP̃ ×{s_{0}}) for almost all s_{0} ∈ ℙ_{K}^{1}.) Furthermore, by slightly modifying step (i) of the proof of the toric variety version of Bernshtein’s theorem [Roj97b, Section 5.1], one can show that C intersects every positive-dimensional irreducible component of Z. (One also needs to use the definition of intersection multiplicity of an irreducible component W as the number of curve branches intersecting W in a 1-parameter deformation.)

The proof of the rest of our main theorem will reduce to establishing a precise correspondence between the factors of F_{A} and the points of φ(C ∩ (TP̃ × {0})). To complete this connection, we need only observe that Z̄_{+}^{∨} is a very special kind of hypersurface, closely related to Z̄.

In particular, if k is the least power of s in H, observe that Z̄_{+}^{∨} and the zero set of \frac{H}{s^{k}} in ℙ_{K}^{|A|−1} × ℙ_{K}^{1} differ only by the presence of the hyperplane ℙ_{K}^{|A|−1} × {0}. The second zero set does not contain this hyperplane, so let’s call the second zero set Z̄^{∨}. Then by lemmata 1 and 2, and the Vanishing Theorem for Resultants, dim[Z̄ ∩(TP̃ ×{s_{0}})]=0 implies the following equivalence: H(H_{φ(ζ)}; s_{0})=0 ⟺ ζ ∈Z̄ ∩ (TP̃×{s_{0}}), where H_{p} is the hyperplane dual to the point p.^{7} Now dim[Z̄ ∩(TP̃ ×{∞})]=0 by construction. Hence dim[Z̄ ∩(TP̃ ×{s_{0}})]=0 for almost all s_{0} ∈ℙ_{K}^{1}, by Main Theorem 2 of [Roj97b]. So ψ^{∨}(C) is an open subset of Z̄^{∨}, where we define ψ^{∨}(C):={(y, s_{0}) | y ∈H_{φ(ζ)} ; ζ ∈ C ∩ (TP̃ × \{s_{0}\}) ; s_{0} ∈ ℙ_{K}^{1}\}. Therefore, since φ is a proper map, \frac{H}{s^{k}} must vanish on all of ψ^{∨}(C). In particular,

7So if p:=[p_{e} | e∈A]∈ℙ_{K}^{|A|−1} then H_{p}:={[y_{e} | e∈A]∈ℙ_{K}^{|A|−1} | ∑_{e∈A} p_{e}y_{e} =0}.

F_{A}(u)=α · ∏_{ζ∈C∩(TP̃×{0})} (∑_{e∈A} c_{ζ,e}u_{e})

where α∈K^{∗}, [c_{ζ,e} | e∈A]:=φ(ζ), and the product counts intersection multiplicities.

Continuing our main proof, (1), (2), and (3) follow immediately from our last formula and our preceding observations.

Note that our algebraic proof avoids the use of limiting arguments that were present in [Can90]. Thus our result is equally valid when K has positive characteristic.

References

[BZ88] Burago, Yu. D. and Zalgaller, V. A., Geometric Inequalities, Grundlehren der mathematischen Wissenschaften 285, Springer-Verlag (1988).

[Can88] Canny, John F., “Some Algebraic and Geometric Computations in PSPACE,” Proc. 20\underline{th} ACM Symp. Theory of Computing, Chicago (1988).

[Can90] , “Generalised Characteristic Polynomials,” J. Symbolic Computation (1990) 9, pp. 241–250.

[CG84] Chistov, A. L., and Grigoriev, Dima Yu, “Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields,” Lect. Notes Comp. Sci. 176, Springer-Verlag (1984).

[Dan78] Danilov, V. I., “The Geometry of Toric Varieties,” Russian Mathematical Surveys, 33 (2), pp. 97–154, 1978.

[DGH96] Dyer, M., Gritzmann, P., and Hufnagel, A., “On the Complexity of Computing Mixed Volumes,” SIAM J. Comput., to appear (1996).

[DS95] Dalbec, John, and Sturmfels, Bernd, “Introduction to Chow Forms,” Invariant Methods in Discrete and Computational Geometry (Curaçao, 1994), pp. 37–58, Kluwer Academic Publishers, Dordrecht, 1995.

[Emi94] Emiris, Ioannis Z., “Sparse Elimination and Applications in Kinematics,” Ph.D. Dissertation, Computer Science Division, U. C. Berkeley (December, 1994), available on-line at

http://www.inria.fr/safir/SAFIR/Ioannis.html

[EC95] Emiris, Ioannis Z. and Canny, John F., “Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume,” Journal of Symbolic Computation, vol. 20 (1995), pp. 117– 149.

[EP97] Emiris, Ioannis Z. and Pan, Victor Y., “The Structure of Sparse Resultant Matrices,” preprint, 1997.

[Ful84] Fulton, William, Intersection Theory, Springer-Verlag, 1984.

[Ful93] , Introduction to Toric Varieties, Annals of Mathematics Studies, no. 131, Princeton University Press, Princeton, New Jersey, 1993.

[GKZ90] Gel’fand, I. M., Kapranov, M. M., and Zelevinsky, A. V., “Discriminants of Polynomials in Several Variables and Triangulations of Newton Polytopes,” Algebra and Analysis (translated from Russian) 2, pp. 1–62, 1990.

[GKZ94] , Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston, 1994.

[HM91] Hafner, James L. and McCurley, Kevin S., “Asymptotically Fast Triangularization of Matrices Over Rings,” SIAM Journal on Computing, 20 (1991), no. 6, pp. 1068–1083.

[HS95] Huber, Birkett and Sturmfels, Bernd, “A Polyhedral Method for Solving Sparse Polynomial Systems,” Mathematics of Computation, 64, pp. 1541–1555, 1995.

[Hub96] Huber, Birk, “Solving Sparse Polynomial Systems,” Ph.D. Dissertation, Department of Mathematics, Cornell University (1996).

[Ili89] Iliopoulos, Costas S., “Worst Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix,” SIAM Journal on Computing, 18 (1989), no. 4, pp. 658–669.

[Kho77] Khovanskii, A. G., “Newton Polyhedra and Toroidal Varieties,” Functional Anal. Appl., 11 (1977), pp. 289–296.

[KKMS73] Kempf, G., Knudsen, F., Mumford, D., Saint-Donat, B., Toroidal Embeddings I, Lecture Notes in Mathematics 339, Springer-Verlag, 1973.

[KSZ92] Kapranov, M. M., Sturmfels, B., and Zelevinsky, A. V., “Chow Polytopes and General Resultants,” Duke Mathematical Journal, Vol. 67, No. 1, July, 1992, pp. 189–218.

[MP97] Morrain, Bernard and Pan, Victor Y. “Solving Special Polynomial Systems by Using Structured Matrices and Algebraic Residues,” Foundations of Computational Mathematics, selected papers of a conference, held at IMPA in Rio de Janeiro, January 1997, Springer-Verlag (1997).

[PS93] Pedersen, P. and Sturmfels, B., “Product Formulas for Sparse Resultants and Chow Forms,” Mathematische Zeitschrift, 214: 377–396, 1993.

[Ren87] Renegar, Jim, “On the Worst Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials,” Technical Report, School of Operations Research and Industrial Engineering, Cornell University.

[Roj94] Rojas, J. Maurice, “A Convex Geometric Approach to Counting the Roots of a Polynomial System,” Theoretical Computer Science (1994), vol. 133 (1), pp. 105–140.

[Roj97a] “Toric Laminations, Sparse Generalized Characteristic Polynomials, and a Refinement of Hilbert’s Tenth Problem,” Foundations of Computational Mathematics, selected papers of a conference, held at IMPA in Rio de Janeiro, January 1997, Springer-Verlag (1997).

[Roj97b] “Toric Intersection Theory for Affine Root Counting,” Journal of Pure and Applied Algebra, to appear. (Also available on-line at

http://www-math.mit.edu/~rojas.)

[Roj97c] “Solving Polynomial Equations via Twisted Chow Forms,” preprint, MIT (1997).

[Roj97d] “When do Resultants Really Vanish? Applications to Diophantine Complexity,” preprint, MIT (1997).

[Roj97e] “Affine Elimination Theory and Solving Certain Diophantine Systems Quickly,” preprint, MIT (1997).

[RW96] Rojas, J. M., and Wang, Xiaoshen, “Counting Affine Roots of Polynomial Systems Via Pointed Newton Polytopes,” Journal of Complexity, vol. 12, June (1996), pp. 116–133.

[Sch94] Schneider, Rolf, Convex Bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and its Applications, v. 44, Cambridge University Press, 1994.

[Shu93] Shub, Mike, “Some Remarks on Bézout’s Theorem and Complexity Theory, From Topology to Computation: Proceedings of the Smalefest, pp. 443–455, Springer-Verlag, 1993.

[Sma87] Smale, Steve, “The Topology of Algorithms I,” Journal of Complexity, 3 (1987), pp. 81–89.

[Stu93] Sturmfels, Bernd, “Sparse Elimination Theory,” In D. Eisenbud and L. Robbiano, editors, Proc. Computat. Algebraic Geom. and Commut. Algebra 1991, pages 377–396, Cortona, Italy, 1993, Cambridge Univ. Press.

[Stu94] , “On the Newton Polytope of the Resultant,” Journal of Algebraic Combinatorics, 3: 207–236, 1994.

[Van50] van der Waerden, B. L., Modern Algebra, 3\underline{rd} edition, F. Ungar, New York.

[Ver96] Verschelde, Jan, “Homotopy Continuation Methods for Solving Polynomial Systems,” Doctoral Dissertation, Katholieke Universiteit Leuven, Leuven, Belgium, May 1996.

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

Massachusetts Institute of Technology, Mathematics Department, 77 Mass. Ave., Cambridge, MA 02139, U.S.A.