TORIC INTERSECTION THEORY FOR AFFINE ROOT COUNTING^{1}

J. MAURICE ROJAS

This paper is dedicated to Basil Gordon on the occassion of his 2^{6\underline{th}} birthday.

Abstract. Given any polynomial system with fixed monomial term structure, we give explicit formulae for the generic number of roots with specified coordinate vanishing restrictions. For the case of affine space minus an arbitrary union of coordinate hyperplanes, these formulae are also the tightest possible upper bounds on the number of isolated roots. We also characterize, in terms of sparse resultants, precisely when these upper bounds are attained. Finally, we reformulate and extend some of the prior combinatorial results of the author on which subsets of coefficients must be chosen generically for our formulae to be exact.

Our underlying framework provides a new toric variety setting for computational intersection theory in affine space minus an arbitrary union of coordinate hyperplanes. We thus show that, at least for root counting, it is better to work in a naturally associated toric compactification instead of always resorting to products of projective spaces.

1. Introduction

We give a new toric variety context for convex geometric root counts for polynomial systems. Our results also improve prior extensions to affine space [Kho78, DK87, Roj92, Roj94, RW96, LW96, HS96] of the seminal works [Kus75, Ber75, Kus76, Kho77] on root counting in the algebraic torus. In addition to their combinatorial appeal, there has been growing excitement about these methods in the computational algebra community due to their efficiency and applicability in many industrial problems [PC94, Emi94, EC95, VGC96].

Let us begin with some notation: Let E_{1}, …, E_{n} be nonempty finite subsets of (ℕ ∪ {0})^{n}. For any e = (e_{1}, …, e_{n}) ∈ (ℕ ∪ {0})^{n} let x^{e} denote the monomial x_{1}^{e_{1}} ⋯ x_{n}^{e_{n}}. In this way we will let f_{1}, …, f_{n} be polynomials in the variables {x_{1}, …, x_{n}} with (algebraically independent) indeterminate coefficients, such that the set of exponent vectors occuring in f_{i} is precisely E_{i}. The set E_{i} is called the support of f_{i} and this representation specifies exactly which monomials can appear in f_{i}. All of our root counts will make maximal use of this monomial term information — not just the degrees of the f_{i}. A convenient short-hand will be the following: Let E:=(E_{1}, …, E_{n}) and F:=(f_{1}, …, f_{n}). Then E is the support of F and we call F an n×n indeterminate polynomial system. We also let C_{E} denote the vector (or sometimes the set) consisting of all the indeterminate coefficients of all the f_{i}. If we specialize some of the coefficients (that is, give them values chosen from some field)^{2} then we say that F has support contained in E.

1Submitted to the Journal of Pure and Applied Algebra. Also available on-line at http://www-math.mit.edu/~rojas. Date: October 27, 1996. 1991 Mathematics Subject Classification. Primary 14M25, 14N10; Secondary 12Y05, 14Q99, 52A39, 52B20, 52B55,

65F50, 65H10, 93B25, 93B27.

Key words and phrases. Mixed volume, generic, root, counting, affine, orbit, isolated, upper bound, sparse, polynomial system, resultant, homotopy, toric variety.

This research was completed at MSRI and partially funded by a Chateaubriand Fellowship, an NSF Mathematical Sciences Postdoctoral Research Fellowship, and NSF grant DMS-9022140.

2We will leave the case of more general specializations, e.g., non-trivial polynomial relations amongst the coefficients, for future work.

Let K be an algebraically closed field of arbitrary characteristic. For instance, K can be the complex numbers or the algebraic closure of a finite field. Also let |E| denote the sum of the cardinalities of the E_{i}. Our first definition focuses our attention on the generic number of roots a polynomial system has in a given region W, when the monomial term structure is determined by E.

Proposition and Definition 1. Let F be an n×n indeterminate polynomial system with support E, C_{E} the vector of coefficients of F, and W a constructible subset of K^{n}. For any C ∈ K^{|E|} let N_{K}(E; W; C) denote the number of roots of F |_{C_{E}=C} lying in W, counting multiplicities.^{3} Then there exists a proper algebraic subset Δ ⊂ K^{|E|}, depending on E and W, such that N_{K}(E; W; ·) is a constant function on K^{|E|} \Δ. We let N_{K}(E; W) denote the value of this constant function. We will also refer to N_{K}(E; W) as the generic value of N_{K}(E; W; ·) or the generic number of roots of F in W.

Definition 2. Let [a..b] be the set of integers {a, a+1, …, b} and for any (possibly empty) J ⊆[1..n] define O_{J}:={x∈K^{n} | x_{j} ≠0 ⟺ j ∈J}. We call O_{J} an orbit.

Note that O_{J} is a relatively open subset of a |J|-dimensional coordinate subspace of K^{n}.

Recall that the (n-dimensional) mixed volume, M(·), takes as input an n-tuple of nonempty compact convex sets in ℝ^{n} and always outputs a nonnegative real number [BF34, Grü69, Roj94, Sch94, HS95, EC95, DGH96, VGC96, DRS96].

Main Result. We will express N_{K}(E; W) in terms of mixed volume for W an arbitrary union of orbits, K algebraically closed, and any E. We will also give a computational algebraic criterion for precisely when this generic number of isolated roots is attained, i.e., explicit algebraic equations for Δ. Our algebraic criterion is then refined to a more practical computational result: a combinatorial classification of the sets of coefficients (subvectors of C_{E}) whose genericity guarantees that F indeed has exactly N_{K}(E; W) isolated roots lying in W, counting multiplicities.

The above result is contained in Main Theorems 1–3, the Affine Point Theorem II, and Corollary 1 of the next section. Examples of our main results appear in section 3 and the remaining sections are devoted to proving our main theorems. Two useful tools applied in our proofs may be of independent interest: the Antipodality Theorem ([Roj96d] and cf. section 5) and a toric variety version of Bernshtein’s Theorem (cf. section 5.1). The former tells us how curves behave at toric infinity, while the latter collects some folkloric facts relating Bernshtein’s famous theorem on root counting [Ber75] to intersection theory on toric varieties [Ful84b, Ful93].

2. Summary of Our Main Results

We will make the natural restriction of considering only those E for which N_{K}(E; W)<∞. Such E, which we will call W -nice, are completely characterized combinatorially in the appendix. It will also be helpful to describe certain subspace unions and cones concisely.

Definition 3. For any I ⊆[1..n] let Hyper(I)⊂K^{n} be the union of coordinate hyperplanes ⋃_{j∈I}{x | x_{j} = 0}. Also let Lin(I) ⊆ ℝ^{n} be the coordinate subspace generated by the subset {ê_{j} | j ∈ I} of the standard basis, and let σ_{I} be the cone defined by the intersection of Lin([1..n]\I) with the nonnegative orthant. Finally, let O denote the origin in whatever module we work in. In particular, Hyper(∅)=∅ and Lin(∅)=σ_{[1..n]} =O_{∅} = O.

3See remark 5 of section 3.2 for the definition of intersection multiplicity.

2.1. Explicit Formulae. We give the following recursive formula for N_{K}(E; W). Although perhaps cumbersome at first glance, our formula contains important intersection theoretic information that helps extend certain algorithms for solving polynomial systems [Roj96d] and is also quite practical in low dimensions (cf. section 3.3 and remark 12). Our result also generalizes, and makes more explicit, an algorithm for computing N_{ℂ}(E; ℂ^{n}) (for a smaller class of E) alluded to in [Kho78, DK87].

Main Theorem 1. Let K be any algebraically closed field and suppose E := (E_{1}, …, E_{n}) is an n-tuple of finite subsets of (ℕ ∪ {0})^{n} which is nice for W, where W is a union of orbits in K^{n}. Also, for all i, j ∈ [1..n], define m_{ij}:=min{y_{j} | (y_{1}, …, y_{n})∈E_{i}} and let m_{1}, …, m_{n} be the rows of the matrix [m_{ij}]. Then N_{K}(E; W) is precisely

∑_{J⊆[1..n]} ∑_{ρ:J^{c}↪[1..n]} [( ∏_{j∈J^{c}} m_{jρ(j)}) N_{K}(E_{(J,ρ)}; W ∩ Lin(ρ(J^{c})^{c}))] ,

where (·)^{c} denotes set-theoretic complement within [1..n], E_{(J,ρ)} :=((E_{i} − m_{i}) ∩ Lin(ρ(J^{c})^{c}) | i∈J), and N_{K}(∅; W) is defined as 1 or 0 according as W is O or ∅. Furthermore, if W = K^{n}\Hyper(I) for some I ⊆ [1..n], then N_{K}(E; W) is also the maximum number of isolated roots in W, counting multiplicities.

Remark 1. Our root counting formulae also hold when E is not nice for W, provided one counts embedded [Eis95, pg. 90] zero-dimensional components as well.

A simple example of the above formula is given in section 3.3 and its proof appears in section 6.2. Main Theorem 1 is recursive in the sense that every term on the right-hand side is a lowerdimensional or cornered [RW96] case of N_{K}(·). In particular, the following definition and main result take care of the “first” term N_{K}(E_{([1..n],·)}; W).

Definition 4. Call a k-tuple C:=(C_{1}, …, C_{k}) of nonempty subsets of ℝ^{n} cornered iff C_{i} lies in the nonnegative orthant and C_{i} ∩ {(y_{1}, …, y_{n})∈ℝ^{n} | y_{j} =0}≠∅ for all i∈[1..k] and j ∈[1..n]. Also, for any a_{1}, …, a_{k} ∈ℝ^{n}, define a∪C to be the k-tuple of convex hulls (Conv({a_{1}}∪C_{1}), …, Conv({a_{k}}∪ C_{k})).

Affine Point Theorem II. Fix I ⊆[1..n] and suppose E is an n-tuple of finite subsets of (ℕ∪{0})^{n} which is nice for K^{n}\Hyper(I) and cornered. For each i ∈ [1..n] let a_{i} ∈ E_{i} ∩ Lin(I) or set a_{i}:= O if E_{i} ∩ Lin(I) is empty. Then N_{K}(E; K^{n}\Hyper(I)) = M(a ∪ E) and this generic number is also the maximum number of isolated roots in K^{n}\Hyper(I), counting multiplicities. More generally, if E is instead nice for O_{J} and cornered, then N_{K}(E; O_{J}) = ∑_{J′⊇J}(−1)^{|J′\J|}M_{J′}, where M_{J′} is the mixed volume corresponding to the case W =K^{n}\Hyper(J′).

The above result is proved in section 6.1 and complements the author’s Affine Point Theorem I which first appeared in [RW96].

Remark 2. Note that proposition 1 directly implies that N_{K}(E; W) is additive with respect to disjoint unions in W. So we can compute N_{K}(E_{([1..n],·)}, W) for general W simply by summing various instances of the Affine Point Theorem II.

Remark 3. Separating into cornered and non-cornered cases also simplifies Khovanskii’s earlier notion of attached, weakly attached, and strongly attached hyperplanes [Kho78].

The reader need not be alarmed at the prospect of computing an alternating sum of mixed volumes since a more efficient way to compute N_{K}(E; O_{J}) is given by the following corollary of Main Theorem 1. This result, which generalizes a formula for N_{ℂ}(E; ℂ^{n} \Hyper(I)) due to Huber and Sturmfels [HS96], also seems to yield a more efficient way to compute N_{K}(E; W) for general W when n>2.

Corollary 1. Following the notation of Main Theorem 1, fix I ⊆ [1..n] and suppose E is nice for K^{n} \Hyper(I). Then N_{K}(E; K^{n} \Hyper(I)) = SM_{I^{c}}(E). Furthermore, if J ⊆ [1..n], E is instead O_{J}-nice, and Ω is a stable subdivision of E, then N_{K}(E; O_{J}) = ∑_{C} M(C), where the sum is over all stable cells C ∈Ω such that the inner normal of the lifted cell Ĉ has support J^{c}.

The quantity SM_{J}(E) is a new convex geometric entity called the J-stable mixed volume. We refer the reader to [HS96] for its definition, and to [HS95, HS96] for the definitions of subdivisions, lifted cells, and stable cells. The support of a vector is simply the set of indices corresponding to its nonzero coordinates. Corollary 1 is proved in section 6.2.

Better still, we can determine precisely when our formulae count the number of roots exactly, even when some of the coefficients are fixed and only a few coefficients are generic.

2.2. Algebraic and Combinatorial Criteria for Exactness. For any w ∈ℝ^{n}, let E_{i}^{w} be the set of points y ∈E_{i} which minimize the standard inner product w ·y. Similarly, for any polytope P ⊂ℝ^{n}, let P^{w} denote the face of P with inner normal w. Also let E^{w} := (E_{1}^{w}, …, E_{n}^{w}) and recall that a facet is a polytope face of codimension 1. A key innovation of Bernshtein’s seminal work on root counting is the algebraic condition he gave for his formula to be the exact number of roots. Sadly, this “second half” of Bernshtein’s Theorem is not sufficiently explored in the literature. So we give the following generalization, proved in section 6.3.

Main Theorem 2. Following the notation of definitions 1 and 3 and Main Theorem 1, suppose W =K^{n}\Hyper(I) and that the coefficients of F have all been specialized to constants in K. Let S be the polytope ∑_{i=1}^{n} Conv(E_{i}). Then the following condition implies that F has exactly N_{K}(E; K^{n}\ Hyper(I)) roots, counting multiplicities, in K^{n}\Hyper(I): (a_{2}) ∏ Res_{E^{w}}(F)≠0, where the product is over all unit inner facet normals w ∈ℝ^{n}\σ_{I} of S, and (b_{2}) if n > 1 then for all J ⫋ [1..n] containing I, and all injections ρ : J^{c} ↪ [1..n] such that

ρ(J^{c}) ∩ I =∅ and ∏_{j∈J^{c}} m_{jρ(j)} > 0,

N_{K} (E_{(J,ρ)}; Lin(ρ(J^{c})^{c}) ∩ (K^{n}\Hyper(I)); C_{E}) = N_{K} (E_{(J,ρ)}; Lin(ρ(J^{c})^{c}) ∩ (K^{n}\Hyper(I))) .

Furthermore, the converse implication holds as well if N_{K}(E_{([1..n],·)}; K^{n}\Hyper(I))>0. In particular, (a_{2}) and (b_{2}) together imply that the zero set of F in K^{n}\Hyper(I) is zero-dimensional or empty.

The sparse resultant Res_{∗}(F) is described at length in [GKZ90, PS93, CE93, Stu94, GKZ94, EC95] and our notation is explained in section 6.3. Sharper criteria for the cases N_{K}(E_{([1..n],·)}; K^{n} \ Hyper(I))=0 are also discussed in section 6.3.

Remark 4. Parallel to Main Theorem 1, Main Theorem 2 is also recursive since for any ϑ⫋[1..n], Lin(ϑ) ∩ (K^{n} \Hyper(I)) can be naturally identified with the complement of a union of coordinate hyperplanes in K^{|ϑ|}.

Alternatively, we can give combinatorial criteria for exactness which are always sufficient and necessary. More precisely, let c_{i,e} denote the (indeterminate) coefficient of the x^{e} term of f_{i}. If an n-tuple D:=(D_{1}, …, D_{n}) satisfies D_{i} ⊆E_{i} for all i∈[1..n] then we simply abbreviate this as D ⊆E. For any such D define C_{D} ={c_{i,e} | i∈[1..n], e∈D_{i}}.

Definition 5. We say that D W -counts E iff (0) D ⊆ E, (1) D and E are nice for W, and (2) for any specialization over K of the coefficients C_{E} \C_{D}, a generic specialization of the remaining coefficients C_{D} suffices to make F have exactly N_{K}(E; W) roots lying in W, counting multiplicities.

So by proposition 1 we at least know that E always W -counts E if E is W -nice.

Define Supp(D) := {i | D_{i} ≠ ∅}, D ∩ Lin(J) = (D_{1} ∩ Lin(J), …, D_{n} ∩ Lin(J)), and D ∩ E^{w} := (D_{1} ∩E_{1}^{w}, …, D_{n} ∩E_{n}^{w}). Our final main theorem gives an exact convex geometric criterion for when D (K^{n}\Hyper(I))-counts E.

Main Theorem 3. Following the notation of definitions 1 and 3 and Main Theorem 1, suppose that W = K^{n}\Hyper(I) and let S be the polytope ∑_{i=1}^{n} Conv(E_{i}). Then D (K^{n}\Hyper(I))-counts E ⟺ one of the following exclusive conditions holds:

1. N_{K}(E; K^{n} \Hyper(I)) = 0 and for all J ⊆ [1..n] containing I, Supp(D ∩ Lin(J)) contains a subset essential for E ∩ Lin(J).

2. N_{K}(E; K^{n}\Hyper(I))>0 and

(a_{3}) for each face of S with an inner normal w ∈ℝ^{n}\σ_{I}, pick a single such w. Then for all of

these w, Supp(D ∩ E^{w}) contains a subset essential for E^{w}, and (b_{3}) if n > 1 then for all J ⫋ [1..n] containing I, and all injections ρ : J^{c} ↪ [1..n] such that

ρ(J^{c}) ∩ I =∅ and ∏_{j∈J^{c}} m_{jρ(j)} > 0, the |J|-tuple

((D_{i} − m_{i}) ∩ Lin(ρ(J^{c})^{c}) | i∈J)
W_{(J,ρ)}-counts E_{(J,ρ)}, where W_{(J,ρ)} :=Lin(ρ(J^{c})^{c}) ∩ (K^{n}\Hyper(I)).

The definition of essentiality, which is a combinatorial geometric condition, appears in the appendix. We thus obtain a recursive combinatorial condition for when the zero set of F in K^{n}\Hyper(I) consists of exactly N_{K}(E; K^{n}\Hyper(I)) points, counting multiplicities. Our final main theorem is proved in section 6.3 as well. Here we deal mainly with genericity conditions for global root counting, so we will leave the classification of O_{ϑ}-counting (when ϑ≠[1..n]) for another paper.

3. Examples

In the following examples, any mixed volume computation will follow easily (even by hand) from the definition or basic properties of the mixed volume [BF34, Grü69, Sch94]. In particular, it useful to recall the following formula for the n=2 case: M(P_{1}, P_{2})=Area(P_{1} + P_{2}) − Area(P_{1}) − Area(P_{2}).

3.1. Comparisons to the Generalized Bézout Theorems. Although mixed volume bounds can be hard to compute for some extremely large polynomial systems, they do have the advantage that they are always at least as good as any Bézout-type bound. Also, current mixed volume software is already fast enough to have been useful in many industrial problems, e.g., [Emi94, VGC96]. Here we will give an example of a family of polynomial systems whose mixed volume root counts are significantly better than any generalized Bézout bound.

However, let us first recall what is meant by a generalized Bézout bound. A good reference is [Wam92] so we will only quickly outline the most general (zero-dimensional) version of Bézout’s Theorem: Given a partition of {x_{1}, …, x_{n}} into sets of cardinality n_{1}, …, n_{λ}, the corresponding multihomogeneous Bézout Theorem gives an explicit formula for N_{K}(E; ℙ_{K}^{n_{1}}× ⋯ ×ℙ_{K}^{n_{λ}}) as a polynomial expression involving the degrees of the f_{i} with respect to the chosen sets of variables.^{4} Implicit in the grouping of variables chosen is an embedding K^{n} ↪ ℙ_{K}^{n_{1}}× ⋯ ×ℙ_{K}^{n_{λ}} and in this way we obtain an upper bound on N_{K}(E; K^{n}).

One can then try to group variables so that this method gives as tight an upper bound on N_{K}(E; K^{n}) as possible, but the following example shows that this bound can be very loose, no matter how one groups variables.

Example 1. (Spiky Newton Polytopes) Consider the indeterminate polynomial system F := (c_{10}+c_{11}x_{1}^{d}+c_{12}x_{2}+⋯+c_{1n}x_{n}, …, c_{n0}+c_{n1}x_{1}^{d}+c_{n2}x_{2}+⋯+c_{nn}x_{n}), where d∈ℕ and n ≥ 2. Clearly, the Newton polytopes of F are all identical and equal to the “spike” P := Conv(O, dê_{1}, ê_{2}, …, ê_{n}). The Affine Point Theorem II then tells us that N_{K}(E; K^{n}) = M(P, …, P) = n!Vol(P) = d, where E is the support of F.

4Polynomial roots in a toric compactification are described in sections 5 and 6.1, and are formalized in definition 17 and lemma 4. In particular, products of projective spaces are special cases of toric compacta.

However, the usual Bézout Theorem tells us that N_{K}(E; K^{n}) ≤ d^{n}. Can this be significantly improved by going to a multi-homogeneous version? The answer is “yes, but not enough:” the best one can do is N_{K}(E; K^{n}) ≤ nd. This bound can be obtained by using two groups of variables: {x_{1}} and {x_{2}, …, x_{n}}. That this is the best one can do with any multihomogeneous version of Bézout’s Theorem is most easily proved geometrically: It is easy to see that computing the optimal generalized Bézout bound is equivalent to finding a product of scaled standard simplices, with smallest volume, which contains P. (This reduction is described more explicitly, but in a different context, in [Roj96a].)

More generally, one can use Main Theorem 3 to determine when a particular Bézout Theorem generically matches (or exceeds) a mixed volume root count: One simply lets E be the n-tuple of vertex sets of the corresponding products of simplices, and lets D be the n-tuple of vertex sets of the Newton polytopes in question. From there, one checks the corresponding counting criterion (cf. definition 5).

3.2. Generic Local Intersection Multiplicity. Setting W = O in Main Theorem 1 we immediately obtain a method for computing the generic intersection multiplicity, at the origin, of a general sparse system of n polynomials in n unknowns. An alternative general algorithm, potentially more efficient in higher dimensions, is the special case J = ∅ of Corollary 1. For example, if F is a 2×2 polynomial system with cornered support E, we obtain from the Affine Point Theorem II that μ(O; F)=N_{K}(E; O)=M(O ∪ E) − M(E) for generic C_{E}. This last formula already generalizes an earlier result of Warren [War94, Theorem 3] for the unmixed case (E_{1} =E_{2}) over ℂ.

However, it is important to note that N_{K}(E; O) is not, in general, an upper bound on intersection multiplicity at the origin: For example, it is easily verified that the polynomial system (x + y^{2}, x + x^{2} + y^{2}) has an isolated root at O with multiplicity 4. (One simply notes that this system has no roots other than O and concludes by Bézout’s Theorem in ℙ_{K}^{2}.) However, setting E := ({(1, 0), (0, 2)}, {(1, 0), (2, 0), (0, 2)}), our last paragraph implies that N_{K}(E; O) = M(O ∪ E) − M(E)=4 − 2= 2.

Remark 5. More generally, if F is an n×n polynomial system over K, then the intersection multiplicity μ(ζ, F) of a zero-dimensional component ζ ∈ K^{n} of Z(F) can be defined as the dimension of the quotient ring \{\frac{r(x)}{s(x)} ∈ K(x) | gcd(r, s) = 1, s(ζ) ≠ 0\}/⟨F ⟩ as a K-vector space [Ful84b, Example 7.1.10 (b)]. For the purposes of definition 1, we will set μ(ζ, F) = +∞ when ζ lies in a positive-dimensional component of Z(F).

3.3. Our Main Theorems in Two Dimensions. Let n = 2 and consider the following bivariate polynomial system:

f_{1}(x, y) := α_{1}y^{2} + α_{2}y^{4} + α_{3}xy^{5} + α_{4}x^{2}y^{5} + α_{5}x^{2}y^{7} + α_{6}x^{4}y^{8}
f_{2}(x, y) := β_{1}x + β_{2}x^{2} + β_{3}xy + β_{4}x^{2}y + β_{5}x^{6}y^{2} + β_{6}x^{6}y^{3} + β_{7}x^{7}y^{3} + β_{8}x^{9}y^{5}

How do we get a tight upper bound on the number of isolated affine roots of F:=(f_{1}, f_{2})? One way is to set E:=Supp(F) and apply the Affine Point Theorem I [RW96]. In which case we obtain that F has no more than M(O∪E)=53 isolated roots. (It is also easily verified that the best generalized Bézout bound is (deg_{x} f_{1})(deg_{y} f_{2}) + (deg_{x} f_{2})(deg_{y} f_{1})=92.) However, it is clear that E is nice for K^{2} (by lemma 7 of the appendix) and not cornered, so let us see if Main Theorem 1 can do better. Figure 1 below clarifies the preceding (and upcoming) calculations.

Following the notation of Main Theorem 1, we obtain m_{1} = (0, 2), and m_{2} = (1, 0). So Main Theorem 1 asserts that

N_{K}(E; K^{2}) = N_{K}(E_{{1,2}}; K^{2}) + N_{K}({O, (0, 2)}, {0}×K) + 2N_{K}({O, (1, 0)}, K×{0}) + 2N_{K}(∅, O)
= 32 + N_{K}({0, 2}, K) + 2N_{K}({0, 1}, K) + 2.

[figure: E_{1} (⊇Supp(f_{1})); e_{1}; e_{2}; α_{1}; α_{2}; α_{3}; α_{4}; α_{5}; α_{6}; E_{2} (⊇Supp(f_{2})); e_{1}; e_{2}; β_{1}; β_{2}; β_{3}; β_{4}; β_{5}; β_{6}; β_{7}; β_{8}; S =Conv(E_{1} + E_{2}); e_{1}; e_{2}]

Figure 1. The sets E_{1}, E_{2}, and E_{1} + E_{2}, along with their underlying convex hulls. (The points of E_{1} and E_{2} are labelled according to their corresponding polynomial coefficients.) The subdivision of the Minkowski sum shows that, in this example, M(E) can actually be expressed as a single determinant.

(The last equality follows from the Affine Point Theorem II.) The remaining unknown terms add up to 4 (by the Affine Point Theorem II again, or simply the fundamental theorem of algebra), so we finally obtain the tight upper bound N_{K}(E; K^{2})=38.

We can also give a precise algebraic condition for when this F has exactly thirty eight affine roots, counting multiplicities. Applying Main Theorem 2 (and figure 1) to our example, we see that the only w we need worry about in condition (a_{2}) are (in counter-clockwise order) (−1, 2), (−1, −1), (−3, 2), (1, −2), and (3, −2). Furthermore, the corresponding sparse resultants are easily seen to be 1, 1, 1, α_{5}β_{8} − α_{6}β_{3}, and 1. (The papers [Stu92, PS93, Stu94] and the book [GKZ94] contain some very nice examples of how to compute low-dimensional sparse resultants.) Condition (b_{2}) then clearly specializes to two one-dimensional cases of condition (a_{2}). (More conservatively, the fundamental theorem of algebra could also be applied to (b_{2}).) So it is not hard to see that condition (b_{2}) is equivalent to α_{2} and β_{2} being nonzero. Since each individual term of the summation from Main Theorem 1 was positive, we thus obtain that F has exactly thirty eight affine roots, counting multiplicities, iff (α_{5}β_{8} − α_{6}β_{3})α_{1}α_{2}β_{2}β_{3}β_{8} ≠0.

Similarly, by Main Theorem 3 (and making use of figures 1 and 2 (cf. the appendix)) we obtain that the genericity of C_{D} implies F has exactly thirty eight affine roots (counting multiplicities) ⟺ C_{D} contains at least one coefficient from each of the following sets: {α_{1}, β_{2}}, {α_{1}}, {α_{1}, β_{5}}, {α_{1}}, {α_{8}}, {α_{6}, β_{8}}, {α_{5}, α_{6}},{β_{3}, β_{8}}, {α_{5}, β_{3}}, {β_{3}}, and {α_{2}, β_{3}} (in counter-clockwise order, from condition (a_{3})); and {α_{2}} and {β_{2}} (from condition (b_{3})). For example, regardless of how the other eight coefficients have been specialized, it suffices to choose the vector (α_{1}, α_{2}, α_{5}, β_{2}, β_{3}, β_{8}) ∈ K^{6} generically for F to have exactly thirty eight roots (counting multiplicities). In other words, D K^{2}-counts E, where D = ({(0, 2), (0, 4), (2, 7)}, {(2, 0), (1, 1), (9, 5)}). The dark points in figure 1 represent D.

4. Background and Terminology

Aside from a few variations, we will follow the same notation as [Roj94, EC95, RW96, HS96, VGC96]. In those papers one can also find some of the definitions below described at a more leisurely pace. We will also liberally quote, e.g., from [Grü69, Har77, Sha80, CLO92, Sch94], various simple facts from convex and algebraic geometry that we will use. However, for the convenience of the reader, we will review a few notions.

For any q_{1}, …, q_{n} ∈ℝ^{n}, let [q_{1}, …, q_{n}] denote the n×n matrix whose i\underline{th} column is q_{i}. It will be useful to recall the following facts concerning the Smith normal form of an integral matrix [Jac85, Chap. 3.7]

Proposition and Definition 6. [Ili89, HM91] An integral basis for ℝ^{n} is a vector space basis for ℝ^{n} which is also a ℤ-module basis for ℤ^{n}. Equivalently, a basis {u_{1}, …, u_{n}} for ℝ^{n} is integral iff [u_{1}, …, u_{n}]∈𝔾𝕃_{n}(ℤ). Such a basis respects a rational subspace L of ℝ^{n} iff {u_{1}, …, u_{dim L}} is a ℤmodule basis for L∩ℤ^{n}. Furthermore, given any rational bases for L and a complementary subspace, an integral basis for ℝ^{n} respecting L can be found within O(n^{11}) arithmetic operations.

Defining x^{U}:=(x_{1}^{u_{11}} ⋯ x_{n}^{u_{n1}}, …, x_{1}^{u_{1n}} ⋯ x_{n}^{u_{nn}}) for any n×n matrix U:=[u_{ij}] with integer entries, we then see that the above proposition tells us how we can find a monomial change of variables which converts a polynomial into a form involving as few variables as possible.

We will use Supp(f) and Newt(f) for, respectively, the support and Newton polytope (the convex hull of Supp(f)) of any f ∈ K′[x_{1}^{±1}, …, x_{n}^{±1}], where K′ := K[Λ] and Λ is any set of algebraically independent indeterminates.

Definition 7. For any weight w ∈ ℝ^{n} the initial term polynomial in_{w}(f)(x) is ∑_{e∈Supp(f)^{w}} c_{e}x^{e}. More generally, if B ⊇ Supp(f), we define the relativized initial term polynomial in_{w,B}(f)(x) := ∑_{e∈B^{w}∩Supp(f)} c_{e}x^{e}. Also, any c_{e} with e on the boundary of Newt(f) is called a boundary coefficient of f.

Alternatively, when w ∈ ℤ^{n}, we can simply substitute x ↦ t^{w}x := (t^{w_{1}}x_{1}, …, t^{w_{n}}x_{n}) into f and define in_{w}(f) as the coefficient of the term of lowest degree in t.

More generally, for any k × n polynomial system F (with constant or indeterminate coefficients), we define the initial term system in_{w}(F) to be (in_{w}(f_{1}), …, in_{w}(f_{k})). Also, if a k-tuple C := (C_{1}, …, C_{k}) satisfies C_{i} ⊇ Supp(f_{i}) for all i ∈ [1..k], then we say that C contains the support of F and we define the relativized initial term system in_{w,C}(F) to be (in_{w,C_{1}}(f_{1}), …, in_{w,C_{k}}(f_{k})). An especially important property of initial term systems is the following.

Proposition 8. [Roj94] Suppose F is an n×n indeterminate polynomial system with support E = (E_{1}, …, E_{n}). In particular, we assume that each E_{i} is nonempty. Then for generic C_{E} and any w ≠O, the polynomial system in_{w,C}(F) has no roots in (K^{∗})^{n}.

Note that for any polynomial system F with support contained in C, the set {in_{w,C}(F) | w ∈S^{n−1}} is finite: When Supp(f_{i}) = C_{i} for all i, we can construct a bijection between the set of initial term systems and the face lattice of Conv(∑ C_{i}), simply by picking a single inner normal w for each face.

There is a rich interplay between the combinatorial geometric structure of Newt(f) and the topology of the zero set of f and we will see again (in section 5 and beyond) that initial term polynomials are extremely valuable in this respect.

4.1. Algebraic Geometry. As usual, we will let Z(F) denote the zero scheme of F in K^{n}. We will make some use of algebraic cycles (e.g., finite formal ℤ-linear combinations of closed subvarieties of some toric variety), rational equivalence, and intersection theory, so let us also recall the following facts and definitions [Har77, Sha80, Ful84a, Ful84b, Ful93]:

1. For any cycle A, Supp(A) is the union of all closed subvarieties V such that the coefficient of V within A is nonzero. Also, a divisor is said to be effective iff all its coefficients are nonnegative.

2. There is a natural intersection product “∩” on the group of all cycles on a variety X giving this group a (commutative) ring structure called the Chow ring of X, Chow(X). This product is also compatible with rational equivalence [Ful84b, pp. 10, 15–17].

3. A 0-cycle on X is a cycle of the form D =∑ n_{ζ}{ζ} where each ζ is a point and n_{ζ} ∈ℤ. When X is complete, the homorphism from the group of 0-cycles on X to ℤ defined by ∑ n_{ζ}{ζ} ↦ ∑ n_{ζ} is invariant under rational equivalence and is called the degree map, deg(·).

4. Any intersection, D, of dim X many divisors in Chow(X) is rationally equivalent to some 0cycle, and thus has a well-defined (cycle class) degree. Furthermore, if each divisor is effective, the coefficient of any zero-dimensional component ζ of such an intersection is its intersection multiplicity, or intersection number, μ(ζ; D) [Ful84b, Example 7.1.10 (b)].

The most advanced prerequisites we will require from algebraic geometry will be the belief in certain theorems dealing with divisor intersections on toric varieties. Good general references are [Dan78, Oda88, Ful84b, Ful93]. The toric variety facts we’ll need are covered in the next section so we now state the main intersection theoretic result we’ll use.

Theorem 1. [Ful84b, Theorem 12.2] Suppose T is a complete n-dimensional variety over an algebraically closed field, and D_{1}, …, D_{n} are effective Cartier divisors such that each line bundle O(D_{i}) is generated by its sections. Also let D denote the intersection product of these divisors in Chow(T ). Then the intersection number of any distinguished component of D is nonnegative. Furthermore, if we let I denote the sum of the intersection numbers of the distinguished components of D, then

I ≤deg D,

and equality holds if D is zero-dimensional or empty.

Remark 6. See [Ful84b] for the definition of a distinguished component. For our purposes, suffice it to say that a zero-dimensional irreducible component is a distinguished component, and the converse holds as well when D is zero-dimensional or empty. Also, embedded [Eis95, pg. 90] zero-dimensional components are distinguished components.

Precise conditions for equality in the above inequality are subtle and difficult to find in the literature. However, we conjecture that equality always holds in the cases where we will apply this theorem. This has already been verified in a particular case, giving a refinement of Bézout’s Theorem over ℂ [Shu93].

4.2. Toric Varieties. We will assume the reader to be familiar with fans and the construction of toric varieties from fans and polytopes. Excellent references are [KKMS73, Dan78, Oda88, Ful93, GKZ94, Stu95].

Let T:=(K^{∗})^{n}, which is sometimes called the algebraic torus.

Definition 9. Let P ⊂ℝ^{n} be an n-dimensional rational polytope. We will associate to P its (inner) normal fan Fan(P) as follows: The rays of this fan are generated by the inner facet normals of P, and to each (not necessarily proper) face P^{w} of P we associate the cone σ_{w} generated by the rays corresponding to the facets containing P^{w}. Each σ_{w} is also called a (inner) normal cone of P.

It is useful to think of the duals of the cones of Fan(P) as “angle” cones. In fact, it easy to show that for any w there is a small ball B ⊂ℝ^{n}, centered at the origin, such that B ∩ σ_{w}^{∨} =B ∩ (P − v), for some v ∈RelIntP^{w}.

We will be working with the following class of toric varieties.

Definition 10. Following the notation of definition 9, we will let T_{P} be the toric variety over K corresponding to the normal fan of P. We call T_{P} the toric compactification of T corresponding to P.

It follows that T_{P} is n-dimensional, rational, projective, normal, integral, separated, and complete [Ful93]. The toric variety T_{P} also has a naturally embedded copy of T (cf. theorem 2). For certain P the toric variety T_{P} is also nonsingular but we will not need this fact. We will also say that any point of T_{P} \(K^{∗})^{n} is at infinity and sometimes refer to T_{P} \(K^{∗})^{n} as toric infinity. Since our polynomial systems will have a priori specified supports, F will usually have far fewer extraneous roots in an appropriately chosen T_{P} than in ℙ_{K}^{n}. Hence toric compactifications are the spaces where we will actually be counting roots of polynomial systems. Toward this end, it will be useful to recall the correspondence between the topology of T_{P} and the face structure of P. However, we will need a little more notation before stating this correspondence as a theorem.

Definition 11. Given any w ∈ℝ^{n}, we will use the following notation: U_{w} = Spec(K[x^{e} | e∈σ_{w}^{∨} ∩ ℤ^{n}]) =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 the face P^{w} of P 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} V_{w} = The closure of O_{w} in T_{P} p_{w} = The first integral point not equal to O met along the ray generated by w (when w ∈ℚ^{n}\{O})

Note that L_{w} is a face of the cone σ_{w}^{∨} so x_{w} is indeed well-defined. Also, recalling that a closed point in an affine toric variety can be identified with a semigroup homomorphism [Ful93, Chap. 1.3], it is clear that any point x∈O_{w} is completely determined by w and the (nonzero) values of x(·) on any ℤ-module basis of L_{w} ∩ ℤ^{n}. Note that our characterization of x_{w} is a slight variation of that of [Ful93] but is easily seen to be equivalent. In particular, our x_{w} is the same as Fulton’s x_{σ} when σ =σ_{w}.

Example 2. (Certain Cornered Polytopes) Suppose P is an n-dimensional rational polytope with a vertex v such that the edges emanating from v generate the nonnegative orthant as a cone. Suppose further that the coordinates of w are all nonnegative. Then O_{w} ≅O_{J}, where J =Supp(w)^{c}. In particular, we see that dim P^{w} = dim O_{w} = n − |Supp(w)| and dim σ_{w} = |Supp(w)|. Note that here x_{w} is the 0-1 vector with support Supp(w)^{c}. Furthermore, U_{(1,... ,1)} ≅ K^{n} so we can thus conclude that K^{n} embeds naturally within such a T_{P}. This example will be especially important in our approach to affine root counting.

Example 3. Suppose w, w′ ∈ℝ^{n}. Then, relative to T_{P}, the defining ideal I_{w′} ⊂K[x^{e} | e ∈ σ_{w}^{∨} ∩ ℤ^{n}] of V_{w′} ∩ U_{w} ⊂ U_{w} is K[x^{e} | e ∈(σ_{w}^{∨}\L_{w′})∩ℤ^{n}].

With our orbit notation in place, we can now state the following important result.

Theorem 2. [Ful93, Chap. 3.1] The toric variety T_{P} is the disjoint union ∐ O_{w}, where a single inner normal w is chosen for each (not necessarily proper) face of P. Also, for all w ∈ ℝ^{n},

1. dim O_{w} = dim V_{w} = dim P^{w}

2. U_{w} = ∐ O_{v}, where a single inner normal v is chosen for each (not necessarily proper) face containing P^{w}. In particular, U_{w} is always an n-dimensional open subvariety of T_{P}.

3. O_{w} =Spec(K[x^{e} | e∈L_{w}∩ℤ^{n}])≅(K^{∗})^{dim P^{w}}.

4. If d = dim P^{w} then V_{w} is isomorphic to any toric compactification of (K^{∗})^{d} corresponding to a polytope Q ⊂ ℝ^{d} ⊆ ℝ^{n} which is 𝔾𝕃_{n}(ℤ)-similar to a translate of P^{w}.

In particular, there is an order-preserving correspondence between the faces (resp. face interiors) of P and the orbit closures (resp. orbits) of T_{P}. Also, there is an order-reversing correspondence between the affine charts of T_{P} and the faces of P. The above result is also contained in [KSZ92, GKZ94] but in the setting where T_{P} is defined via an explicit projective embedding.

Since toric compactifications will be the spaces in which we analyze the roots of F, it will be useful to embed the support of F within an n-tuple of nonempty integral polytopes P:=(P_{1}, …, P_{n}) and define P as a function of P. We can then consider the roots of F within T_{P} as follows: Each (nonzero) polynomial f_{i} defines a Weil divisor Div(f_{i}) in T_{P} [Ful93, Chap. 3.3]. The closure (in T_{P}) of the zero scheme of f_{i} in (K^{∗})^{n} is a summand of Div(f_{i}) and is the portion of Div(f_{i}) we are actually interested in. To isolate this portion of Div(f_{i}) we will add another specially defined divisor (depending on P and P_{i}) to Div(f_{i}). This will cancel out the negative part of Div(f_{i}) but sometimes introduce extraneous components. In any case, the zero scheme of F in (K^{∗})^{n} is thus embedded in an intersection of effective divisors in T_{P}. In section 6.2 we will show how to eliminate some of these extra components, modify P so that T_{P} has a naturally embedded copy of K^{n}\Hyper(I), and thus derive our method for affine root counting. The construction of our divisors is detailed in the next section.

5. The Importance of Roots at Toric Infinity

Here we point out two, more or less folkloric results on toric divisors. Combined with the Antipodality Theorem [Roj96d], these two results considerably simplify the proof of our toric compactification version (theorem 3 in the next subsection) of the BKK bound [Ber75].

First we give the following definition to help us find the right T_{P}, and the right divisor to add to Div(f_{i}), for our root counting theory to go through.

Definition 12. Let Q⊂ℝ^{n} be an integral polytope. We will say that a fan F is compatible with Q iff every normal cone of Q is a union of cones of F. We will also say that a rational polytope P ⊂ℝ^{n} is compatible with Q iff Fan(P) is compatible with Q. Also, following the notation of definition 11, we define the integer γ_{w}(Q):=− min_{v∈Q}{v·p_{w}} for any w ∈ℚ^{n}\{O}.

Example 4. It is easily shown that ∑ P_{i} is always compatible with P_{1}, …, P_{n}. Compatibility was applied earlier in [Kho77, Ful93] and the terminology “sufficiently fine decomposition” was used in the first reference.

Next we describe precisely which divisors we will be intersecting.

Definition 13. Assuming P ⊂ℝ^{n} is a rational polytope compatible with an integral polytope Q⊂ℝ^{n}, let E_{P} (Q):=∑ γ_{w}(Q)V_{w}, where w ranges over all the inner facet normals of P. We call E_{P} (Q) the torus-invariant divisor of T_{P} corresponding to Q. Also, set D_{P} (0, Q):=T_{P} and, for any polynomial f with ∅≠Supp(f)⊆Q, define D_{P} (f, Q):=Div(f) + E_{P} (Q).

It follows by definition that D_{P} (f, Q) is always effective [Ful93] and invariant under translations of P and identical translations of Q and f. This turns out to be good for root counting in (K^{∗})^{n} but bad for root counting in K^{n}. Hence we will modify the definition of D_{P} (f, Q) in section 6.2.

Definition 14. Suppose F =(f_{1}, …, f_{k}) is a k×n polynomial system over K with support contained in a k-tuple of nonempty integral polytopes P = (P_{1}, …, P_{k}). Then P ⊂ ℝ^{n} is compatible with P ⟺ P is compatible with P_{1}, …, P_{k}. Furthermore, when this is the case, we define D_{P} (F, P) to be the intersection product ⋂_{i=1}^{k} D_{P} (f_{i}, P_{i})∈Chow(T_{P}).

It is easy to see that even as schemes (K^{∗})^{n}∩Z(F)=(K^{∗})^{n}∩D_{P} (F, P) when dim P =n. Also note that D_{P} (f, Q) is precisely the closure \overline{(K^{∗})^{n} ∩ Z(f)} in T_{P} if Newt(f) = Q and dim P = n. By our last observation, we could just set P_{i}:= Newt(f_{i}) for all i in the construction of D_{P} (F, P) in order to work directly with \overline{(K^{∗})^{n} ∩ Z(F)}. However, this is not always advantageous computationally and it actually behooves us to fully understand the cases where Newt(f_{i}) is not compatible with P or Newt(f_{i}) ≠ P_{i}. One reason is that for precise sparse affine root counting, it is necessary to know precisely what happens to Div(f_{i}) as lots of coefficients of F are specialized to 0.

So let us now find explicitly the behavior of D_{P} (F, P) within a neighborhood of toric infinity. The following lemma, which is a direct consequence of the development followed in [Ful93] or [GKZ94], shows us that U_{w} ∩ D_{P} (F, P) can be described by a relatively simple ideal.

Lemma 1. Let w ∈ ℝ^{n}. Then, following the notation of definitions 11 and 14, the defining ideal in K[x^{e} | e ∈ σ_{w}^{∨} ∩ ℤ^{n}] of U_{w} ∩ D_{P} (F, P) is ⟨x^{b_{1}}f_{1}, …, x^{b_{k}}f_{k}⟩, for any b_{1}, …, b_{k} ∈ ℤ^{n} such that b_{i} + P_{i}^{w} ⊆ L_{w} for all i∈[1..k].

Should one be so inclined, the intersection multiplicity of a component of D_{P} (F, P) can be computed by restricting to an appropriate chart U_{w} and this lemma gives one an explicit coordinate ring to work in.

The following is a more computational version of the above lemma and is easily proved by localization.

Corollary 2. Following the notation of lemma 1, the underlying topological spaces of O_{w} ∩D_{P} (F, P) and

Spec(K[x^{e} | e ∈ L_{w} ∩ ℤ^{n}]/⟨in_{w,b_{1}+P_{1}}(x^{b_{1}}f_{1}), …, in_{w,b_{k}+P_{k}}(x^{b_{k}}f_{k})⟩)

are homeomorphic.

In particular, if {u_{1}, …, u_{n}} ⊆ L_{w} ∩ ℤ^{n} is a generating set, then the map defined by x ↦ (x(u_{1}), …, x(u_{n})) is an isomorphism from O_{w} onto a subvariety of (K^{∗})^{n}, and [z ∈O_{w}∩D_{P} (F, P) ⟺ in_{w,P}(F) vanishes at the point (z(u_{1}), …, z(u_{n}))].

It is a frequent misconception that the last equivalence should begin with z ∈O_{w} ∩ \overline{(K^{∗})^{n} ∩ Z(F)}. This is false unless, for instance, P_{i} =Newt(f_{i}) for all i. (A simple counterexample is (n, P, f, w):= (1, [0, 2], x^{2} + x, 1).) Also, it is extremely important to note that the intersection multiplicity of a component of D_{P} (F, P) lying in O_{w} can not always be determined by this corollary when w ≠ O. (Simply observe the case P_{1} = P_{2} = P = 3Conv{O, ê_{1}, ê_{2}}, F = (x_{1}^{3} − x_{1}^{2}, x_{2}^{3} − x_{2}^{2}), and w:= (1, 1).) Thus there is a loss of information as we intersect with O_{w} and pass from F to its initial term systems.

The last two results thus tell us that the relativized initial term systems in_{w,P}(F) (for w ≠ O) describe the topological behavior of a particular divisor intersection (canonically defined by F, P, and P) at a piece of toric infinity. This generalizes the classical construction of how the terms of highest total degree depict the closure of the zero scheme of F at the projective hyperplane at infinity.

Our toric variety T_{P} also gives us an interesting way to detect excess components in the zero set of F in (K^{∗})^{n}.

Antipodality Theorem. [Roj96d] Suppose P ⊂ ℝ^{n} is an n-dimensional rational polytope, Y is a curve in (K^{∗})^{n}, and \overline{Y} is the closure of Y in T_{P}. Also, identify \{O_{w} ⊂T_{P} | w ≠O\} with a partition of S^{n−1} into cells by letting w and w′ in S^{n−1} belong to the same cell iff O_{w} =O_{w′}. Then

1. \overline{Y} must touch two (possibly identical) cells whose union does not lie in any closed coordinate hemisphere.

2. If \overline{Y} touches a cell intersecting some open hemisphere H then it must also touch a cell inter-

secting S^{n−1}\H. Furthermore, \overline{Y} must touch at least two topologically separated cells.

Remark 7. The cells described above are in fact stereographic images of the facets of the dual (or polar) of P.

5.1. A Toric Variety Version of Bernshtein’s Theorem. Before stating our generalization of Bernshtein’s Theorem, we point out a very useful immediate corollary of the Antipodality Theorem and corollary 2.

Corollary 3. Following the notation of corollary 2, D_{P} (F, P) has positive dimension ⟹ in_{w,P}(F) has a root in (K^{∗})^{n} for some w ≠O.

D. N. Bernshtein proved the case of corollary 3 where (K^{∗})^{n} ∩ D_{P} (F, P) is positive-dimensional and K =ℂ [Ber75]. His proof used an ingenious Puiseux series construction, but unfortunately Puiseux series expansions are not always defined for algebraic curves over a field of positive characteristic. Hence our need for antipodality theorems.

By combining the following lemma with theorem 1, we see that working within T_{P} allows us to reduce the computation of intersection numbers (generically) to the evaluation of a mixed volume.

Lemma 2. [Ful93, Chap. 5.4] Following the notation of definitions 13 and 14, the cycle class degree of E_{P} (P_{1}) ∩ ⋯ ∩ E_{P} (P_{n}) ∈ Chow(T_{P}) is precisely M(E). Furthermore, for all i, the line bundle O(D_{P} (f_{i}, P_{i})) is generated by its sections.

Putting all our machinery together, we can derive the following toric variety version of the BKK bound.

Theorem 3. Suppose F is an n×n polynomial system over K with support contained in an n-tuple P of nonempty integral polytopes in ℝ^{n}. Further suppose that P ⊂ ℝ^{n} is an n-dimensional rational polytope compatible with P. Then the zero scheme of F in (K^{∗})^{n} embeds naturally as a subscheme of the toric cycle D_{P} (F, P) and:

1. If D_{P} (F, P) is zero-dimensional or empty then D(F, P) consists of exactly M(P) points, counting multiplicities.

2. If D_{P} (F, P) is positive-dimensional and M(P) = 0 then D_{P} (F, P) has no zero-dimensional irreducible components in T_{P}.

3. If D_{P} (F, P) is positive-dimensional and M(P)>0 then D_{P} (F, P) has strictly less than M(P) zero-dimensional irreducible components in T_{P}, counting multiplicities.

Remark 8. Assertion (3) appears to be new for the case charK ≠ 0. The case (K, P_{1}, …, P_{n}) = (ℂ, Newt(f_{1}), …, Newt(f_{n})) first appeared in [Ber75] and was stated as a root count over (ℂ^{∗})^{n} instead of T_{P}. Assertions (1) and (2) (over a general algebraically closed field) then appeared implicitly in [Dan78], but this was not as well known as it should have been.

Proof: That (K^{∗})^{n} ∩ Z(F) embeds as a subscheme of D_{P} (F, P) follows immediately from our previous observations regarding definitions 13 and 14.

Assertion (1) then follows immediately from theorem 1 and lemma 2 since D_{P} (f_{i}, P_{i}) and E_{P} (P_{i}) are rationally equivalent. Assertion (2) follows similarly since the intersection multiplicity of a zero-dimensional irreducible component of D_{P} (F, P) is positive [Ful84b]. Fulton stated this concise argument in [Ful93] for the case K =ℂ and his proof has the added benefit that it is independent of the (algebraically closed) field where one is working.

For the last assertion (3) we will generalize a novel homotopy proof due to D. N. Bernshtein [Ber75]. First note that if any f_{i} is identically zero then there can be no zero-dimensional components and we are done. Thus we may assume that no f_{i} is identically zero. Our generalization of Bernshtein’s argument can then be outlined as follows:

(i) Pick a point y ∈O_{w}, for some w ∈ℝ^{n}\{O}, which lies in a positive-dimensional component of D_{P} (F, P).

(ii) Construct a generic polynomial system G with n-tuple of Newton polytopes P and distin-

guished root z ∈(K^{∗})^{n} such that F (z)≠O. (iii) Construct a rational algebraic curve L ⊂ T_{P} ×ℙ_{K}^{1} with parameterization \overline{l} : ℙ_{K}^{1} ⟷ L such

that \overline{l}(0)=y and \overline{l}(1)=z. (iv) For all i∈[1..n], define h_{i}(x, t)∈K[t, x_{1}^{±1}, …, x_{n}^{±1}] to be the polynomial obtained by clearing

denominators from the reduced form of the rational function f_{i}(x)g_{i}(\overline{l}(t))−g_{i}(x)f_{i}(\overline{l}(t)). Show that h_{i}(x, 0) (resp. h_{i}(x, 1)) is a nonzero scalar multiple of f_{i}(x) (resp. g_{i}(x)).

(v) Let H(x, t) := (h_{1}(x, t), …, h_{n}(x, t)) and consider the subscheme Z:= \overline{((K^{∗})^{n}×K) ∩ Z(H)} of T_{P} ×ℙ_{K}^{1}. Show that D_{P} (F, P) ≅ (T_{P} ×{0}) ∩ Z.

(vi) Show that the natural (n+1)\underline{st} coordinate projection defined on (K^{∗})^{n}×K extends to a proper morphism π : T_{P} ×ℙ_{K}^{1} ⟶ ℙ_{K}^{1} with π(L)=ℙ_{K}^{1}.

(vii) Define Y to be the union of all 1-dimensional irreducible components of Z with surjective image under π. Show that the support of the zero-dimensional part of D_{P} (F, P) is contained in Supp((T_{P} ×{0}) ∩ Y).

(viii) Show that Y ∩(T_{P} ×{0}) consists of exactly M(P) points, counting multiplicities. Assuming the above steps, (3) then follows immediately since y ∈ L, L ⊆ Y, and thus y ∈ Supp(Y ∩ (T_{P} ×{0})), i.e., the zero-dimensional part of D_{P} (F, P) consists of strictly fewer than M(P) points, counting multiplicities.

To complete our proof, we now proceed to prove each individual step. (i): Easy, by the Antipodality Theorem. (ii): By generic we will specifically mean that f_{1}, …, f_{n} are all nonzero at all roots of G in (K^{∗})^{n} and that G has exactly M(P) roots in (K^{∗})^{n} (counting multiplicities). That such G occur generically follows easily from proposition 8, corollary 3, assertion (1) (which we’ve already proved), and the fact that the intersection of any two generic conditions is again a generic condition. (iii): We will first construct the parameterization \overline{l} and then the corresponding complete curve L.

Since y is completely determined by the (nonzero) values of y(·) on any ℤ-module basis of L_{w} ∩ℤ^{n}, let {u_{1}, …, u_{n}} be any basis for ℤ^{n} respecting L_{w} ∩ℤ^{n}. (Such a basis is guaranteed to exist by proposition 6.) Let U := [u_{1}, …, u_{n}] and [v_{1}, …, v_{n}] := V := U^{−1}. By assumption U ∈ 𝔾𝕃_{n}(ℤ) so clearly V ∈𝔾𝕃_{n}(ℤ). Now let l : K^{∗} ⟶ (K^{∗})^{n} be the following parameterization of a toric line:

((1 − t)y^{U} + tz^{U})^{V}

where, quite naturally, y^{U} := (y(u_{1}), …, y(u_{n})) and t is a new variable. Then it is easily verified that l(1)=z (via the general identity (x^{A})^{B} =x^{AB}). Note that l naturally defines a rational function from ℙ_{K}^{1} to T_{P}×ℙ_{K}^{1} via [t:1] ↦ (l_{1}(t), …, l_{n}(t))×[t:1]. So by [Sil86, Prop. 2.1] this rational function extends uniquely to a morphism \overline{l}. This is our desired \overline{l} and, of course, \overline{l}(1)=z.

Now let L be the closure in T_{P} ×ℙ_{K}^{1} of the subvariety of (K^{∗})^{n+1} defined by the ideal

⟨(1 − t)y(u_{1}) + tz^{u_{1}} − x^{u_{1}}, …, (1 − t)y(u_{n}) + tz^{u_{n}} − x^{u_{n}}⟩.

It is then easily verified that the hyperplane T_{P} ×{t_{0}} intersects L in the unique point l(t_{0})∈(K^{∗})^{n} for all but finitely many t_{0} ∈K. (Simply solve the resulting binomial equation by exponentiating by V.) It is also clear that T_{P} ×{t_{0}} does not meet L within (K^{∗})^{n}×{t_{0}} for the remaining values of t_{0}. Thus L must indeed be a curve. Since L is closed, it must also be complete and equal to the graph of \overline{l} in T_{P} ×ℙ_{K}^{1}. By corollary 2 it easily follows that L∩O_{(w,1)} = (z, 0) (for w as in (i)) and thus \overline{l}(0)=z. (iv): First note that the definition makes sense since we can just substitute l for \overline{l}. Now to verify that h_{i}(x, t) satsifies our desired properties, note that l(t)^{u_{i}} =(1−t)y(u_{i})+tz^{u_{i}} by a straightforward calculation. If we define d:= dim L_{w} and write e = α_{1}u_{1} + ⋯ + α_{n}u_{n}, it then becomes clear that ord_{t}(l(t)^{e}) = α_{d+1} + ⋯ + α_{n}. By changing the signs of the columns of U where necessary, we can then assume that w·u_{i} ≥0 for all i∈[1..n] and write

f_{i}(l(t))=t^{b_{i}}(in_{w,P_{i}}(f_{i})|_{x=(y(π_{w}(ê_{1})),... ,y(π_{w}(ê_{n})))} + higher order terms in t)
g_{i}(l(t))=t^{b_{i}}(in_{w,P_{i}}(g_{i})|_{x=(y(π_{w}(ê_{1})),... ,y(π_{w}(ê_{n})))} + higher order terms in t)

where b_{i} ∈ℤ and π_{w} : ℝ^{n} ⟶ L_{w} is the natural projection defined by the basis U. In particular, note that t^{−b_{i}}f_{i}(l(t))|_{t=0} =0 (by corollary 2 and the definition of l) and t^{−b_{i}}g_{i}(l(t))|_{t=0} ≠0 (by corollary 2 and the definition of G). Thus h_{i}(x, t)=t^{−b_{i}}κ(t)(f_{i}(x)g_{i}(l(t)) − g_{i}(x)f_{i}(l(t))), for some κ(t)∈K(t) satisfying ord_{t}(κ)=0. So we are done. (v): First note that for any ω ∈ℝ^{n+1}, there is a b∈ℤ^{n+1} such that Newt(x^{b}h_{i}) touches every facet of the cone σ_{ω}^{∨}. (This follows easily since all the f_{i} are nonzero and G has n-tuple of Newton polytopes P.) Thus by definition 13, \overline{((K^{∗})^{n}×K) ∩ Z(h_{i})} = D_{P ×[0,1]}(h_{i}, P_{i} × [0, d_{i}]), where d_{i} is the t-degree of h_{i}. Lemma 1 then implies that for any w′ ∈ℝ^{n}\{O}, the defining ideal of Z ∩ U_{(w′,1)} is generated by x^{b_{1}}h_{1}, …, x^{b_{n}}h_{n}, for suitable b_{1}, …, b_{n} ∈ ℤ^{n}. By theorem 2 we know that T_{P} ×{0} ≅ Vê_{n+1}, so by lemma 1 the defining ideal of (T_{P} × {0}) ∩ U_{(w′,1)} is principal and generated by t. Since h_{i} ≡ f_{i} (mod t), we thus see that the defining ideal of Z ∩(T_{P} ×{0})∩U_{(w′,1)} is generated by t and x^{b_{1}}f_{1}, …, x^{b_{n}}f_{n}. Lemma 1 then implies that D_{P} (F, P)∩U_{w′} has a defining ideal with generators x^{b_{1}}f_{1}, …, x^{b_{n}}f_{n}. Patching together charts, we are done. (vi): This follows easily from [Ful93, Chap. 2.4]. (vii:) Clearly, any zero-dimensional irreducible component ζ of D_{P} (F, P) must be contained in some positive-dimensional irreducible component Σ of Z. If dim Σ>1 then ζ must lie in a positivedimensional component of Σ ∩ (T_{P} ×{0}) — a contradiction. Thus dim Σ=1. Clearly 0∈π(Σ) and π(Σ)≠{0} so by properness we must have π(Σ)=ℙ_{K}^{1}. So Σ must be a component of Y. (viii:) Let t_{0} ∈ ℙ_{K}^{1}. If Y is irreducible then it follows directly from the definition of intersection multiplicity that ∑ μ(ζ), where ζ ranges over all zero-dimensional irreducible components of Y ∩ (T_{P} × {t_{0}}), is precisely the sum of the ramification indices [Sil86] of π^{−1}(t_{0}). The latter number in turn is precisely the degree of the map π and is thus independent of the point t_{0} [Ful84b, Examples 4.3.7 and 7.1.15].^{5} If Y is reducible then we can extend the definition of degree simply by summing the degrees of π|_{Y_{j}} over all the irreducible components Y_{j} of Y and then our preceding identity still holds.

Thus it suffices to compute ∑ μ(ζ) for any t_{0}. In particular, by construction, we already know that this number is precisely M(P) when t_{0} =1.

The above theorem is quite useful for root counting in (K^{∗})^{n} but still has the nagging problem that it doesn’t give the exact number of roots when the intersections are ill-behaved — more precisely, when D_{P} (F, P) intersects toric infinity. However, our theorem (when combined with corollary 2) at least provides us with a computational method for knowing exactly when this happens. (Indeed, Main Theorem 2 is based on this very fact!) Also, when D_{P} (F, P) is zero-dimensional, the precise number of roots, counting multiplicities, can still be obtained as follows.

Corollary 4. Following the notation of theorem 3, suppose further that D_{P} (F, P) is zero-dimensional or empty. Let I:= ∑ μ(ζ) where the sum ranges over all components ζ of D_{P} (F, P)\(K^{∗})^{n}. Then the number of roots of F in (K^{∗})^{n} is precisely M(P)−I, counting multiplicities.

This approach to exact (as opposed to generic) root counting is pursued further in [Roj96b, Roj96c] and was independently suggested in [MSW95] (in the special case of multihomogeneous systems) and [Ver96, pp. 180–185 and 215–216] (not counting some intersection multiplicities).

Intuitively, it is a weaker condition to require D_{P} (F, P) to be zero-dimensional than to require all the roots of F to be isolated and lie in (K^{∗})^{n}. This statement is made more precise in the next section and in section 6.3 we will also give a combinatorial characterization of the stronger hypothesis.

Another natural question which still remains is how to extend our analysis to other spaces — for example, K^{n}. We do this in the next section.

Remark 9. We point out that all of the results of this section hold for more general complete toric varieties as well — in particular, toric varieties corresponding to (compatible) complete fans. The modifications are minor and we have omitted them simply because toric compacta corresponding to polytopes are sufficiently powerful for our particular root counting problems in affine space.

Remark 10. A more elementary (but longer) proof of parts (1) and (2) of theorem 3 can be obtained by generalizing Huber and Sturmfels’ proof of Bernshtein’s Theorem [HS95] to arbitrary algebraically closed fields: One first replaces the use of theorem 1 and lemma 2 in our intersection theoretic proof by the combinatorics of mixed subdivisions. Then, the use of Puiseux series in their proof is replaced by some algebraic curve theory à la the proof of (viii). The resulting polyhedral proof requires no more machinery than that already used in the proof of part (3). However, for the sake of brevity we will omit this alternative proof.

5Note that in our definitions of ramification index and degree, we are including the inseparability degree. This is relevant when the characteristic of K is positive.

6. Proofs of Our Five Main Results

We now expand our applications of toric compacta to root counting in affine space. We will begin by proving the Affine Point Theorem II and then proceed to prove Main Theorem 1, Corollary 1, and Main Theorems 3 and 2.

6.1. Affine Embeddings. Contrary to what one might expect, a toric compactification T_{P} does not always contain a naturally embedded copy of K^{n}. This technicality forces us to require P to satisfy an additional hypothesis before we apply T_{P} to root counting in K^{n}. The following definition is the first of our two main tricks for applying toric intersection theory to affine root counting.

Definition 15. We say a rational polytope P ⊂ℝ^{n} is cornered iff Fan(P) contains the nonnegative orthant as one of its cones. More generally, for any I ⊆ [1..n], P is I-cornered iff σ_{I} is one of the cones of Fan(P) (following the notation of definition 3).

Note that cornering is different for polytopes and k-tuples of point sets: For polytopes, ∅-cornering is easily seen to be equivalent to a translate of P being identical to the nonnegative orthant in a neighborhood of O. For a k-tuple (C_{1}, …, C_{k}), cornering refers to the position of each C_{i} within the nonnegative orthant σ_{∅}.

Our last definition is well-motivated for the following reason.

Proposition 16. If P ⊂ℝ^{n} is I-cornered then T_{P} has a naturally embedded copy of K^{n}\Hyper(I). More precisely, for such a T_{P}, K^{n}\Hyper(I)≅U_{w}, where w is the 0-1 vector with support I^{c}.

We now show how to construct a special I-cornered P^{⌞} from any given k-tuple of polytopes in ℝ^{n}.

Algorithm 1. Input: A positive integer n, a k-tuple of nonempty integral polytopes P = (P_{1}, …, P_{k}) lying in the

nonnegative orthant of ℝ^{n}, and a subset I ⊆[1..n].

Output: An n-dimensional rational polytope P^{⌞} ⊂ ℝ^{n}, and points a_{1}, …, a_{k} ∈ ℤ^{n}, such that P^{⌞} is

n-dimensional, I-cornered and compatible with a ∪ P.

Description: 1. For all i∈[1..k] and j ∈[1..n], define m_{ij}:=min{e_{j} | (e_{1}, …, e_{n})∈P_{i}}, and let m_{1}, …, m_{k}

be the rows of the matrix [m_{ij}].

2. For each i∈[1..k] let a_{i} ∈P_{i} ∩ ℤ^{n} ∩ (m_{i} + Lin(I)) or set a_{i}:=m_{i} if P_{i}∩(m_{i} + Lin(I))=∅.

3. Define Q:=∑_{i=1}^{k} Conv({a_{i}}∪P_{i}). If dim Q<n then set Q:=Q + Conv(O ∪ B), where B is a generic set of n − dim Q rational points in the nonnegative orthant (so that dim Q=n).

4. For all i ∈ [1..k], let ε_{i} := \frac{1}{2} min\{v_{i}\}, where the minimum ranges over all vertices v = (v_{1}, …, v_{n}) of Q incident to (but not lying in) (Hyper(i) + ∑_{j=1}^{n} a_{j}) ∩ Q.

5. Define P^{⌞}:=((ε_{1}, …, ε_{n}) + σ_{I}^{∨}) ∩ Q.^{6}

From the last step of our construction it is easily verified that P^{⌞} is I-cornered. Also, since Q is already n-dimensional and compatible with a ∪ P, it is clear that our choice of (ε_{1}, …, ε_{n}) keeps P^{⌞} n-dimensional and compatible with a ∪ P. Thus intersecting a translate of σ_{I}^{∨} with Q in step (5) is somewhat reminiscent of refining the fan of a polytope by, quoting [GKZ94, pg. 190], “cutting out (as with a knife)… any face of codimension at least 2.”

6It is useful to note that the dual cone σ_{I}^{∨} is precisely ⋂_{j∈I^{c}}{(y_{1}, …, y_{n})∈ℝ^{n} | y_{j} ≥ 0}.

As one may have already guessed, P^{⌞} is especially useful for root counting in K^{n}\Hyper(I) and the points a_{1}, …, a_{k} will also be quite important. As a warm-up, the following lemma is easily verified from theorem 2, definition 13, and proposition 16.

Lemma 3. Following the notation of definition 14, assume further that P_{1}, …, P_{k} all lie in the nonnegative orthant of ℝ^{n}. Fix I ⊆ [1..n] and define a_{1}, …, a_{k} and P^{⌞} via algorithm 1. Then P cornered ⟹ (K^{n}\Hyper(I)) ∩ Z(F) = (K^{n}\Hyper(I)) ∩ D_{P^{⌞}}(F, a ∪ P) as schemes. Furthermore, if Newt(f_{i})=P_{i} for all i as well, then \overline{(K^{n}\Hyper(I)) ∩ Z(F)}=D_{P^{⌞}}(F, a ∪ P).

We emphasize that K^{n}\Hyper(I) is not always naturally embedded in T_{P}, hence our need for P^{⌞}. Thus, under certain assumptions, the above lemma allows us to embed an affine hypersurface into a toric divisor. In fact, we can do even better: We are now in a position to apply our framework to proving the Affine Point Theorem II. Proof of the Affine Point Theorem II: Focusing on the first part of the theorem, the case M(a ∪ E) = 0 is easiest to prove so we dispose of it first: By the author’s Affine Point Theorem I [RW96], we obtain that a polynomial system with support contained in E can have no isolated roots in K^{n}\Hyper(I). Since E is (K^{n}\Hyper(I))-nice by assumption, we are done.

So let us now assume that M(a ∪ E) > 0. Set P := (Conv(E_{1}), …, Conv(E_{n})) and, applying algorithm 1, define D:=D_{P^{⌞}}(F, a ∪ P). We will need the following important fact:

⋆ : O_{w} ∩ D =∅ for all w ∈ℝ^{n}\σ_{I} ⟺ [D ⊂K^{n}\Hyper(I) and dim D ≤0].

That the left-hand side is equivalent to D ⊂K^{n}\Hyper(I) follows easily from theorem 2 and proposition 16. Furthermore, it follows easily from part (2) of the Antipodality Theorem and proposition 16 that dim D >0 ⟹ O_{w} ∩ D ≠∅ for some w ∈ℝ^{n}\σ_{I}. So ⋆ is true.

Now note that the left-hand side of ⋆ is generically true by proposition 8 and corollary 2. So by theorem 3, lemma 3, and ⋆, all but the last sentence of the Affine Point Theorem II is now verified. Note also that we may drop the assumption that E be (K^{n}\Hyper(I))-nice, as long as we also count embedded zero-dimensional components.

To prove the final part, first note the following identity of weighted set unions:

† : O_{J} = (K^{n}\Hyper(J)) \ ( ⋃_{|J′\J|=1}(K^{n}\Hyper(J′))) ∪ ( ⋃_{|J′\J|=2}(K^{n}\Hyper(J′))) \ ⋯

which terminates in the appropriate union or set difference according as n − |J| is even or odd. This follows easily from the principle of inclusion-exclusion [GKP94] since, for any ϑ⊆[1..n], K^{n}\Hyper(ϑ) is precisely the disjoint union ∐_{ϑ′⊇ϑ} O_{ϑ′}. The key to proving our alternating mixed volume formula is then to simply find an intersection theoretic analogue of †.

To do this we must work in a new lifted compactification depending on J. So let P (J′) denote the P^{⌞} corresponding to the I =J′ case of algorithm 1 and define T̃ to be the toric compactification corresponding to P̃ := ∑_{J′⊇J} P (J′). Also let a_{1}(J′), …, a_{n}(J′) respectively denote the integral points a_{1}, …, a_{n} from the I =J′ case of algorithm 1. By example 4, P̃ is compatible with a(J′) ∪ P for all J′ ⊇J, so define D̃(J′):=DP̃(F, a(J′) ∪ P). Then, by [Ful93, Chap. 2.4] and our construction, there is a proper morphism φ : T̃ ↠ T_{P (J)} with no fibers of infinite cardinality. Similar to proposition 16 and lemma 3, it is also easily checked that O_{J} ∩ φ(D̃(J))=O_{J} ∩ Z(F).

More importantly, it is easily verified from definition 13 and expanding in Chow(T̃) that (as cycles) D̃(J′′) is a summand of D̃(J′) for all J′′ ⊇J′ ⊇J. Also, it immediately follows from theorem 3 that deg D̃(J′) = M_{J′} for all J′ ⊇ J. So by inclusion-exclusion once again, we have the following equality of cycles:

φ^{−1}(O_{J}) ∩ D̃(J) = D̃(J) − ( ∑_{|J′\J|=1} D̃(J′)) + ( ∑_{|J′\J|=2} D̃(J′)) − ⋯

provided φ^{−1}(O_{J}) ∩ D̃(J) is zero-dimensional or empty.^{7} So then deg(φ^{−1}(O_{J}) ∩ D̃(J)) is precisely our alternating mixed volume formula. Note that D̃(J) generically has exactly deg(φ^{−1}(O_{J})∩D̃(J)) points (counting multiplicities) in φ^{−1}(O_{J}), by the portion of the Affine Point Theorem II that we’ve already proved and since E is O_{J}-nice. The last cycle class degree is also precisely deg(O_{J} ∩φ(D̃(J))) [Ful84b, Example 7.1.9], so we are done.

Of course, the assumption that E be cornered is quite restrictive. We relax this assumption in the following section by refining lemma 3, and then Main Theorem 1 follows easily by explicitly expanding a different intersection product in the Chow ring of T_{P^{⌞}}.

6.2. Chow Rings and Main Theorem 1. Our second and final trick for applying special T_{P} ’s to affine root counting is a bit more abstract. Whereas our first trick (“cornering”) consisted of a convex geometric construction, the construction we give now amends a difficulty with the divisors D_{P} (f, Q) we used earlier. In particular, for noncornered (P_{1}, …, P_{n}), it is possible that \overline{(K^{n}\Hyper(I)) ∩ Z(f_{i})} and D_{P^{⌞}}(f_{i}, Conv(\{a_{i}\} ∪ P_{i})) differ in the coefficients corresponding to the coordinate hyperplanes. This is remedied by the following definition and lemma.

Definition 17. Following the notation of Main Theorem 1, definition 11, and lemma 3, define X_{j} := Vê_{j} ⊂ T_{P^{⌞}} for any j ∈ I^{c}. Also, set D_{shift}(0, P_{i}) := T_{P^{⌞}} and, if Supp(f_{i}) ≠ ∅, define D_{shift}(f_{i}, P_{i}) := D_{P^{⌞}}(f_{i}, Conv({a_{i}} ∪ P_{i})) + ∑_{j∈I^{c}} m_{ij}X_{j} ∈ Chow(T_{P^{⌞}}). Finally, let D_{shift}(F, P) := ⋂_{i=1}^{k} D_{shift}(f_{i}, P_{i}) ∈ Chow(T_{P^{⌞}}). The roots of f_{i} within T_{P^{⌞}} are then, formally, D_{shift}(f_{i}, Newt(f_{i})).

Lemma 4. Following the notation of definition 17, (K^{n} \Hyper(I)) ∩ Z(F) = (K^{n} \Hyper(I)) ∩ D_{shift}(F, P) as schemes. Furthermore, if Newt(f_{i})=P_{i} then \overline{(K^{n}\Hyper(I)) ∩ Z(f_{i})} = D_{shift}(f_{i}, P_{i}), within T_{P^{⌞}}.

In particular, for any j ∈I^{c}, X_{j} is the closure of the hyperplane {x | x_{j} = 0}∩(K^{n}\Hyper(I)) in T_{P^{⌞}}. Keeping this in mind, the proof of the lemma is then straightforward from theorem 2, proposition 16, and lemma 3. So by “shifting” our toric divisors, we now at last have a completely general way of embedding an affine hypersurface into a toric compactification. As an application, we will prove Main Theorem 1. Proof of Main Theorem 1: Set P := (Conv(E_{1}), …, Conv(E_{n})). We will first prove the case W =K^{n}\Hyper(I) and, to do so, it will clearly suffice to demonstrate the following two statements:

A_{deg}: N_{K}(E; K^{n}\Hyper(I))=deg D_{shift}(F, P). A_{sum}: deg D_{shift}(F, P) is precisely the double summation stated in Main Theorem 1.

Consider also the following auxiliary statement:

A_{gen}: for fixed E and generic C_{E}, D_{shift}(F, P) is zero-dimensional and supported entirely within K^{n}\Hyper(I).

To prove A_{deg} and A_{sum}, we will actually first prove (A_{deg}) ∧ (A_{gen}) by induction on n, and then A_{sum} will follow easily.

7We should remark that the left-hand intersection is set-theoretic, and not a Chow product.

First note that by the definition of D_{shift}(·) we may formally expand D_{shift}(F, P) in Chow(T_{P^{⌞}}) as a polynomial in the X_{j}. More explicitly,

D_{shift}(F, P) = ⋂_{i=1}^{n} (D_{P^{⌞}}(f_{i}, Conv({a_{i}} ∪ P_{i})) + ∑_{j∈I^{c}} m_{ij}X_{j}) =

∑_{[1..n]⊇J⊇I} ∑_{ρ:J^{c}↪[1..n]} [( ∏_{j∈J^{c}} m_{jρ(j)}) (⋂_{i∈J} D_{P^{⌞}}(f_{i}, Conv({a_{i}} ∪ P_{i}))) ∩ ( ⋂_{j∈ρ(J^{c})} X_{j})]

This is where the shape of our asserted formula comes from. Note that j ∈I ⟹ X_{j}∩(K^{n}\Hyper(I))= ∅, thus allowing the slight simplification of the outer summation.

Now note that ⋂_{j∈ρ(J^{c})} X_{j} is itself isomorphic to the toric variety corresponding to a face P_{(J,ρ)} of P^{⌞}, à la theorem 2. In particular, letting P_{(J,ρ)} :=((P_{j} − m_{j}) ∩ Lin(ρ(J^{c})^{c}) | j ∈J), it easy to see that P_{(J,ρ)} can occur as the output of the (k, n, P, I)⇝(|J|, |J|, P_{(J,ρ)}, ρ(J^{c})^{c} ∩ I) case of algorithm 1.

Let F_{(J,ρ)} be the polynomial system obtained by setting the variables {x_{j} | j ∈ρ(J^{c})} to 0 in the |J|-tuple (x_{1}^{−m_{i1}} ⋯ x_{n}^{−m_{in}}f_{i} | i ∈ J). Also note that ⋂_{j∈ϑ} Hyper(j) = Lin(ϑ^{c}) for any ϑ ⊆ [1..n]. We may then say that

(⋂_{i∈J} D_{P^{⌞}}(f_{i}, Conv({a_{i}} ∪ P_{i}))) ∩ ( ⋂_{j∈ρ(J^{c})} X_{j}) ≅ D_{shift}(F_{(J,ρ)}, P_{(J,ρ)})

where the underlying compactification for the right-hand cycle is T_{P_{(J,ρ)}}. This last identity follows from definitions 13 and 17, and our preceding observations.

Note that E_{([1..n],·)} is cornered. So then the proof of the Affine Point Theorem II (and definition 13) immediately implies that deg D_{P^{⌞}}(F, a ∪ P) = M(a ∪ P) = N_{K}(E_{([1..n],·)}; K^{n} \Hyper(I)) and, generically, D_{P^{⌞}}(F, a ∪ P) is zero-dimensional and supported entirely within K^{n}\Hyper(I). As for the remaining intersection terms with J ≠[1..n], our induction hypothesis (with n=|J|) implies that

N_{K} (E_{J}; Lin(ρ(J^{c})^{c}) ∩ (K^{n}\Hyper(I)))=deg D_{shift}(F_{(J,ρ)}, P_{(J,ρ)}).

Furthermore, our induction hypothesis also implies that, generically, D_{shift}(F_{(J,ρ)}, P_{(J,ρ)}) is zerodimensional and supported entirely within Lin(ρ(J^{c})^{c}) ∩ (K^{n}\Hyper(I)).

Now note that our Chow expansion also immediately implies that

Supp(D_{shift}(F, P))= ⋃_{I⊆J⊆[1..n]} ⋃_{ρ:J^{c}↪[1..n]} Supp(D_{shift}(F_{(J,ρ)}, P_{(J,ρ)})),

modulo some isomorphisms fixing K^{n}\Hyper(I). Since a finite conjunction of generic conditions is again a generic condition, we thus arrive at A_{gen}.

Recall that lemma 4 states that (K^{n} \Hyper(I)) ∩ Z(F) is naturally embedded in D_{shift}(F, P). Thus N_{K}(E; K^{n}\Hyper(I))≤deg D_{shift}(F, P) and, by A_{gen}, we arrive at A_{deg}. Noting that the n=1 case of (A_{deg}) ∧ (A_{gen}) is true simply via the fundamental theorem of algebra over K, our induction is complete.

Finally, A_{sum} follows simply by taking degrees of both sides of our Chow expansion. Note also that our embedding, along with A_{deg}, implies that N_{K}(E; K^{n} \Hyper(I)) is indeed the maximal number of isolated roots. So the case W =K^{n}\Hyper(I) is proved.

The general case then follows easily from inclusion-exclusion, much like our proof of the Affine Point Theorem II. This method goes through because our asserted formula is additive with respect to disjoint unions in W, and already true for W =K^{n}\Hyper(I).

Remark 11. Since our proof of Main Theorem 1 computes N_{K}(E; W) as the degree of an algebraic cycle, remark 1 is just a straightforward abstract extension of our preceding proof.

Remark 12. The double summation of Main Theorem 1 can of course simplify considerably when W is smaller than K^{n}. For instance, there is only 1 term when W = (K^{∗})^{n}. Also, it is a simple combinatorial exercise to show that the double summation of Main Theorem 1 has at most ∏_{i=1}^{n}(|Supp(m_{i})| + 1) terms. Equality occurs, for example, when W = K^{n}. Note also that by our recursive formula, the matrix [m_{ij}] can be assumed to have at most 1 nonzero entry per column if E is W -nice. So, by the fact that (a + 1)(b + 1)≥a + b + 1 for positive integers, we also obtain that our double summation has at most 2^{n} terms. Furthermore, this maximum is attained iff [m_{ij}] has the same support as a permutation matrix.

Remark 13. If one would like a formula closer to the number of distinct roots in K^{n} \Hyper(I), a useful trick is the following: Use Main Theorem 1, but replacing [m_{ij}] with the 0-1 matrix having the same support. From our last proof, it is easy to see that this new formula has the effect of (generically) counting isolated roots lying on ⋃_{J⊇I, |J|=n−1} O_{J} without multiplicity. Thus, if one

continues to propogate this trick throughout the recursion of Main Theorem 1, we can count (omitting multiplicities due to inseparability degree) the generic number of distinct roots of F in W. This is important because for many E, a sparse system with support contained in E always has roots of multiplicity >1 lying in K^{n}\(K^{∗})^{n}.

A useful corollary of our proof of Main Theorem 1 is the following concise generalization of theorem 3.

Corollary 5. Following the notation of lemma 4, assume further that k =n and P =(Conv(E_{1}), …, Conv(E_{n})). Then N_{K}(E; K^{n} \ Hyper(I)) = deg D_{shift}(F, P). Furthermore, if both N_{K}(E; K^{n} \ Hyper(I)) and dim D_{shift}(F, P) are positive, then D_{shift}(F, P) has strictly less than N_{K}(E; K^{n} \ Hyper(I)) zero-dimensional components, counting multiplicities.

Proof: The first portion follows immediately from our proof of the W =K^{n}\Hyper(I) case of Main Theorem 1. As for the remaining portion, by the Chow expansion from our last proof, it suffices to prove the cornered case and then simply mimic the earlier descent by induction. Since the cornered case of our present corollary is already contained in the (P, P)⇝(a ∪ P, P^{⌞}) case of theorem 3, we are done.

So theorem 3 is just the I = [1..n] case of collary 5. In intersection theoretic terms, the above result establishes the numerical positivity [Ful84b] of any positive-dimensional component of the new shifted cycle D_{shift}(F, P). This will allow us to derive precise algebraic conditions for what “generic” means in the context of affine root counting.

Corollary 1 then follows easily from Main Theorem 1 as follows: Proof of Corollary 1: Although Huber and Sturmfels did not explicitly mention intersection multiplicities in [HS96], an examination of their proof of the stable mixed volume formula shows that multiplicities were at least included implicitly. In particular, we may safely assume that the first portion of Corollary 1 is true for K =ℂ. The remaining portion (for K =ℂ) is already implicit in Huber and Sturmfels’ proof^{8} of the stable mixed volume formula, so we may safely assume that all of Corollary 1 is true for K =ℂ.

Generalizing to arbitrary algebraically closed K is then almost trivial: The right-hand sides (of both asserted formulae) are clearly independent of K. By Main Theorem 1 and the Affine Point Theorem II, the left-hand sides are also independent of K, provided K is algebraically closed. Since both formulae are already true for K =ℂ, we are done.

8Note that our O_{J} is actually O_{{1,... ,n}\J} in the notation of [HS96].

Similar to remark 10, a more elementary (but longer) proof of Corollary 1 can be derived by generalizing Huber and Sturmfels’ proof of their stable mixed formula.

6.3. Sparse Resultants, Roots at Infinity, and Main Theorems 2 and 3. We conclude with an analysis of conditions under which our (global) generic root counts are exact. The conditions we give can be split into two types: algebraic and combinatorial. In the combinatorial case our conditions are always both sufficient and necessary, while in the algebraic case our criteria are always sufficient but fail to be necessary for certain systems which generically have no roots. However, we fully classify the cases where our algebraic criteria are necessary. These results will rely on the following technical result relating our shifted toric divisors with toric infinity.

Lemma 5. Following the notation of the proof of Main Theorem 1, let D_{[1..n]} (∈Chow(T_{P^{⌞}})) be the J = [1..n] term of the Chow expansion of D_{shift}(F, P). Then the following conditions imply that F has exactly N_{K}(E; K^{n}\Hyper(I)) roots, counting multiplicities, in K^{n}\Hyper(I):

(a) O_{w} ∩ D_{[1..n]} =∅ for all w ∈ℝ^{n}\σ_{I}, and

(b) if n > 1 then for all J ⫋ [1..n] containing I, and all injections ρ : J^{c} ↪ [1..n] such that ρ(J^{c}) ∩ I =∅ and ∏_{j∈J^{c}} m_{jρ(j)} > 0,

N_{K} (E_{(J,ρ)}; Lin(ρ(J^{c})^{c}) ∩ (K^{n}\Hyper(I)); C_{E}) = N_{K} (E_{(J,ρ)}; Lin(ρ(J^{c})^{c}) ∩ (K^{n}\Hyper(I))) .

Furthermore, the converse implication holds as well if N_{K}(E_{([1..n],·)}; K^{n}\Hyper(I))>0. In particular,

(a) and (b) together imply that the zero set of F in K^{n}\Hyper(I) is zero-dimensional or empty.

Proof of the Lemma: Note that Supp(D_{shift}(F, P)) = ⋃ Supp(D_{shift}(F_{(J,ρ)}, P_{(J,ρ)})) where the union ranges over ([1..n], ·) and all pairs (J, ρ) described above. This follows immediately from our Chow expansion from the proof of Main Theorem 1, and the fact that the terms with ρ(J^{c}) ∩ I nonempty or ∏_{j∈J^{c}} m_{jρ(j)} zero simply aren’t there (by definition 17). Recall also that E_{([1..n],·)} is cornered. So it suffices to prove the cornered case and descend by induction, just as we did in the proofs of Main Theorem 1 and corollary 5. But the cornered case, minus the partial converse, is already contained in assertion ⋆ from our proof of the Affine Point Theorem II. One also observes that the (⟹) portion of ⋆ continues to hold even when N_{K}(E; K^{n} \ Hyper(I)) = 0. So we are done.

Remark 14. Note that the converse of the main assertion of lemma 5 can fail if N_{K}(E_{([1..n],·)}; K^{n}\ Hyper(I))=0: Consider the polynomial system F =(1+x, 1+x, (1+x)(y+z)+1) where E:=Supp(F) and note that condition (b) is violated when w =(0, −1, −1).

Remark 15. However, the converse doesn’t always fail if N_{K}(E_{([1..n],·)}; K^{n} \Hyper(I)) = 0: For instance, the converse always holds for n = 2 when E = Supp(F). More generally, for any n > 2, setting f_{1} := 1 and E_{1} := {O} gives an entire family of examples. Basically, when N_{K}(E; K^{n} \ Hyper(I)) = 0, the converse of the main assertion of lemma 5 fails precisely when E is sufficiently complicated to allow specializations of C_{E} where F has roots at toric infinity while having none within K^{n}\Hyper(I).

We are now ready to prove Main Theorem 3. Proof of Main Theorem 3: We will first dispose of case (1) which is the easiest. Recall that K^{n} \ Hyper(I) = ∐_{J⊇I} O_{J} and that a finite conjunction of generic conditions is again a generic condition. Since E is null for K^{n}\Hyper(I) (and thus for every O_{J} with J ⊇ I) it suffices to show that our condition from case (1) is equivalent to D ∩ Lin(J) O_{J}-counting E ∩ Lin(J) for all J ⊇ I. This, in essence, is the statement of Lemma 3 of [Roj94]. So case (1) is complete.

As for case (2), note that E^{w} depends only on the face S^{w}. So by corollary 2, the same is true of O_{w} ∩ D_{[1..n]}. Then by lemma 5, the definition of W -counting, and since any finite conjunction of generic conditions is again a generic condition, we need only prove the case where E is cornered and then descend by induction just as in three of our last four proofs. For I =∅, the cornered case is just case (2) of Theorem 7 of [RW96]. Applying algorithm 1, generalizing the proof there to arbitrary I is simple. (In fact, the proof of [RW96, Theorem 7] already contains what is essentially the I = ∅ case of algorithm 1.) So we are done.

We now recall the sparse resultant (also known as the (A_{1}, …, A_{k})-resultant, mixed resultant, Newton resultant, or toric resultant), which is an extremely important operator on overdetermined polynomial systems. It is defined for any k×n indeterminate polynomial system F with support E, provided that all the E_{i} can be translated into a common (k−1)-dimensional subspace of ℝ^{n}. Since we can always identify such a subspace with a rational hyperplane in ℝ^{k}, we will consider only the case of n×(n − 1) systems and monomial transformations (involving an extra variable) of such systems.

More explicitly, suppose E is an n-tuple of nonempty finite subsets of ℤ^{n} which can be translated into a common (n−1)-plane in ℝ^{n}. Then the sparse resultant, with respect to E, will be a (homogeneous) polynomial Res_{E}(·) in the coefficients C_{E} satisfying the following property: If C ∈ K^{|E|} and F |_{C_{E}=C} has a root in (K^{∗})^{n}, then Res_{E}(C) = 0. For fixed E, the polynomial Res_{E}(·) can then be defined (up to a nonzero scalar multiple) as the unique polynomial in C_{E} of least total degree satisfying this last property. The computation of Res_{E}(·) is a deep subject and we refer the reader to [GKZ90, PS93, CE93, SZ94, Stu94, GKZ94, EC95, Roj96c] for further background on sparse resultants.

For convenience, we will use Res_{E}(F) in place of Res_{E}(C) whenever the coefficients of F have been specialized to some C ∈ K^{|E|}. We also point out the following important fact: Res_{E}(F) = 0 does not necessarily imply that F has a root in (K^{∗})^{n}. The correct statement, at least for initial term systems, is the following.

Theorem 4. [Roj96c] Following the notation of theorem 3, suppose P = (Conv(E_{i}) | i ∈ [1..n]) and w is an inner facet normal of P. Then Res_{E^{w}}(F)=0 ⟺ V_{w}∩D_{P} (F, P)≠∅.

Remark 16. Since in_{w,E}(F) involves a subset of the coefficients C_{E}, we’ve further simplified notation by writing Res_{E^{w}}(F) in place of Res_{E^{w}}(in_{w,E}(F)).

Our algebraic condition for F to have generically many roots is based on the above useful property of the sparse resultant. Proof of Main Theorem 2: Recall from the proof of Main Theorem 3 that E^{w} and O_{w} ∩ D_{[1..n]} depend only on the face S^{w}. So then, by theorem 2, V_{w} ∩ D_{[1..n]} also depends only on S^{w}. To conclude, by theorems 2 and 4, it is clear that conditions (a) and (b) of lemma 5 are respectively equivalent to conditions (a_{2}) and (b_{2}) of Main Theorem 2. So we are done.

Remark 17. In practice, we would not actually construct the Minkowski sum S stated in our last two main theorems. Instead, we would actually work with the individual normal fans of Conv(E_{1}), …, Conv(E_{n}) and dynamically update the smallest common refinement necessary for our search space. The deeper stages in the recursion would then simply consist of slicing cones in the search fans by appropriate coordinate subspaces.

The case (K, I) = (ℂ, [1..n]) of Main Theorem 2 was independently discovered and presented in [HS95, Theorem 6.1]. However, the statement there is false in the case where the mixed volume is zero: Simply consider the counter-example from remark 14. Moreover, parallel to lemma 5, the converse of the main assertion of Main Theorem 2 doesn’t depend completely on the positivity of N_{K}(E; K^{n} \Hyper(I)): The examples given in remarks 14 and 15 also work here in an analogous way. Sharper computational conditions for exactness in the cases N_{K}(E; K^{n}\Hyper(I))=0 will be addressed in future work.

Remark 18. Following the notation of definition 1, we see that Main Theorem 2 allows us to express Δ as a union of hypersurfaces, via condition (a_{2}) and the recursion of condition (b_{2}). However, the minimal delta (containing all C such that F |_{C_{E}=C} does not have the generic number of roots) need not be a hypersurface or even an algebraic variety. In general, this “generic counting discriminant” is a constructible variety of codimension > 1. However, we can at least explicitly compute the codimension by combining Main Theorem 2 with Theorem 1.3 of [Stu94].

“Sparse” techniques have recently been applied quite succesfully to solving many polynomial systems occuring in industrial problems [PC94, Emi94, EC95, VGC96]. Software implementations of resultant-based algorithms are also discussed in almost all of these papers. Thus Main Theorem 2 presents another potentially useful application of the sparse resultant.

7. Acknowledgements

The author would like to thank Marie-Francoise Roy for her kind support and hospitality during his visit to IRMAR in Rennes. He is also grateful to Paco Santos and Jie Tai Yu for shooting down his erroneous conjectures, and to Birk Huber, T. Y. Li, Bernd Sturmfels, and Robert M. Williams for many valuable discussions. The author also thanks the referees from MEGA ’96 for their valuable suggestions.

References

[Ber75] Bernshtein, D. N., “The Number of Roots of a System of Equations,” Functional Analysis and its Applications (translated from Russian), Vol. 9, No. 2, (1975), pp. 183–185.

[BF34] Bonnessen, T. and Fenchel, W., Convex Bodies, translated from German, TCS Associates, 1934.

[CE93] Canny, John F. and Emiris, Ioannis Z., “An Efficient Algorithm for the Sparse Mixed Resultant,” Proceedings AAECC, Puerto Rico, May, Lect. Notes in Comp. Science 263, pp. 89–104, Springer-Verlag, 1993.

[CLO92] Cox, D., Little, J., and O’Shea, D., Ideals, Varieties, and Algorithms, Undergraduate Texts in Mathematics, Springer-Verlag, 1992.

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

[DK87] Danilov, V. I., and Khovanskii, A., “Newton Polyhedra and an Algorithm for Computing Hodge-Deligne Numbers,” Math. USSR Ivzestiya, Vol. 29 (1987), No. 2.

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

[DRS96] Dalbec, J., Rojas, J. M., and Sturmfels, B., “How to Fill a Mixed Volume,” manuscript, Massachusetts Institute of Technology, 1996.

[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.

[Eis95] Eisenbud, David, “Commutative Algebra with a View Toward Algebraic Geometry,” Graduate Texts in Mathematics 150, Springer-Verlag.

[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.

[Ful84a] Fulton, William, Introduction to Intersection Theory in Algebraic Geometry, no. 54, Regional Conference Series in Mathematics, American Mathematical Society, 1984.

[Ful84b] , Intersection Theory, Springer-Verlag, 1984.

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

[GKP94] Graham, R. L., Knuth, D. E., and Patashnik, O., Concrete Mathematics: A Foundation for Computer Science, 2\underline{nd} edition, Addison-Wesley, 1994.

[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, 1–62, 1990.

[GKZ94] Gel’fand, I. M., Kapranov, M. M., and Zelevinsky, A. V., Discriminants, Resultants and Multidimensional Determinants, Birkhauser, Boston, 1994.

[Grü69] Grünbaum, Branko, Convex Polytopes, Interscience, London, New York, Sydney, 1969.

[Har77] Hartshorne, Robin, Algebraic Geometry, Springer-Verlag, 1977.

[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.

[HS96] , “Bernshtein’s Theorem in Affine Space,” Discrete and Computational Geometry, to appear, 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.

[Jac85] Jacobson, Nathan, Basic Algebra I, 2\underline{nd} edition, W. H. Freeman and Company, 1985.

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

[Kho78] , “Newton Polyhedra and the Genus of Complete Intersections,” Functional Analysis (translated from Russian), Vol. 12, No. 1, January–March (1978), pp. 51–61.

[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 Polytope and General Resultants,” Duke Mathematical Journal, Vol. 67, No. 1, pp. 189–218 (1992).

[Kus75] Kushnirenko, A. G., “A Newton Polytope and the Number of Solutions of a System of k Equations in k Unknowns,” Usp. Matem. Nauk., 30, No. 2, pp. 266–267 (1975).

[Kus76] , “Newton Polytopes and the Bézout Theorem,” Functional Analysis and its Applications (translated from Russian), vol. 10, no. 3, July–September (1976), pp. 82–83.

[LW96] Li, T. Y. and Wang, Xiaoshen, “The BKK Root Count in ℂ^{n},” Mathematics of Computation, October, 1996.

[MSW95] Morgan, A. P., Sommese, A. J., and Wampler, C. W., “A Product-Decomposition Theorem for Bounding Bézout Numbers,” SIAM J. Numer. Anal., 32(4): 1308–1325, 1995.

[Mum76] Mumford, David Algebraic Geometry I: Complex Algebraic Varieties, Springer-Verlag, 1976.

[Oda88] Oda, Tadeo, Convex Bodies and Algebraic Geometry: an Introduction to the Theory of Toric Varieties, Springer-Verlag, 1988.

[PC94] Parsons, David and Canny, J. F., “Geometric Problems in Molecular Biology and Robotics,” In Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology, Palo Alto, CA, August, to appear (1994).

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

[Roj91] Rojas, J. Maurice, “An Optimal Condition for Determining the Exact Number of Roots of a Polynomial System,” M.S. thesis, C.S. Division, U. C. Berkeley, 1991.

[Roj92] , “When Can One Easily Find the Number of Roots of a Nonhomogeneous Polynomial System?,” extended abstract presented at the 40\underline{th} Annual Meeting of the Society for Industrial and Applied Mathematics, Los Angeles, July 15–19, 1992.

[Roj94] , “A Convex Geometric Approach to Counting the Roots of a Polynomial System,” Theoretical Computer Science (1994), vol. 133 (1), pp. 105–140. (Additional notes and corrections available on-line at

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

[Roj96a] , “On the Average Number of Real Roots of Certain Random Sparse Polynomial Systems,” pp. 689–699, The Mathematics of Numerical Analysis, Lectures in Applied Mathematics, vol. 32 (1996), edited by Jim Renegar, Mike Shub, and Steve Smale, American Mathematical Society.

[Roj96b] , “Toric Laminations, Sparse Generalized Characteristic Polynomials, and a Refinement of Hilbert’s Tenth Problem,” Proceedings of the Rio de Janeiro Foundations of Computational Mathematics Conference (January 1997), Springer-Verlag, to appear.

[Roj96c] , “When do Resultants Really Vanish? Applications to Diophantine Complexity,” manuscript, MIT.

[Roj96d] , “Affine Elimination Theory and Solving Certain Diophantine Equations Quickly,” manuscript, MIT.

[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.

[Sha80] Shafarevich, I. N., Basic Algebraic Geometry, Springer study editions, Springer-Verlag, 1980.

[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.

[Sil86] Silverman, Joseph, The Arithmetic of Elliptic Curves, Springer Graduate Texts in Mathematics 106, Springer-Verlag, 1986.

[Stu92] Sturmfels, Bernd, “More Examples of A-Resultants,” letter to Misha Kapranov, 1992.

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

[Stu95] , Gröbner Bases and Convex Polytopes, Lectures presented at the Holiday Symposium at New Mexico State University, December 27–31, 1994.

[SZ94] Sturmfels, B. and Zelevinsky, A., “Multigraded Resultants of Sylvester Type” Journal of Algebra, 163(1): 115–127, 1994.

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

[VGC96] Verschelde, J., Gatermann, K., and Cools, R., “Mixed Volume Computation by Dynamic Lifting Applied to Polynomial System Solving,” Discrete and Computational Geometry, Vol. 16, No. 1, pp. 69–112 (1996).

[Wam92] Wampler, Charles W., “Bezout Number Calculations for Multi-Homogeneous Polynomial Systems,” Applied Mathematics and Computation 51, pp. 143–157, 1992.

[War94] Warren, “A Bound on the Implicit Degree of Polygonal Bézier Surfaces,” Algebraic Geometry and its Applications, edited by Chandrajit L. Bajaj, pp. 513–525

Appendix: Niceness and Genericity

Here we briefly recount some earlier results on W -counting and some related concepts. Some of the material below is covered at greater length in [Roj94] (for the case I = [1..n]) and [RW96] (for the case I =∅ and E cornered). The paper [Stu94] is also a useful reference but deals more with the sparse resultant than with root counting. The results below form the basis for our combinatorial conditions for when a “partially” generic polynomial system has generically many isolated roots in a given union of orbits.

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 two definitions are fundamental to our development.

Definition 18. 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 ⊆ [1..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.

Definition 19. We say that C has an almost essential subset J ⟺ (0) Supp(C)⊇J, (1) dim(∑_{j∈J} C_{j}) = |J|, and (2) dim(∑_{j∈J′} C_{j}) ≥ |J′| for all nonempty J′ ⊆ J. Also, ∅ is defined to be almost essential for C iff Supp(C)=∅.

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. The following figure shows some simple examples of essential subsets for C, for various C in the case n = 2. It also worth noting that J ∪ {j} is essential for C ⟹ J is almost essential for C, provided |J ∪ {j}|>|J|>0.

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

Figure 2. The essential subsets for 3 different pairs of plane polygons. (The segments in the middle pair are meant to be parallel.)

Making use of the fact that K^{n} \ Hyper(I) is the disjoint union ∐_{J⊇I} O_{J}, our combinatorial results for (K^{n}\Hyper(I))-counting and (K^{n}\Hyper(I))-niceness will follow easily upon partitioning K^{n}\Hyper(I) into orbits. In particular, it will be useful to refine W -niceness slightly as follows.

Definition 20. Suppose E is an n-tuple of finite subsets of (ℕ ∪ {0})^{n}. We then call E null for W ⟺ a generic polynomial system with support contained in E has no roots in W.

For any J ⊆ [1..n], define E ∩ Lin(J) := (E_{1} ∩ Lin(J), …, E_{n} ∩ Lin(J)). We may now quote the following useful result.

Lemma 6. [RW96, Corollary 2] Suppose E is an n-tuple of finite subsets of (ℕ ∪ {0})^{n}. Then E is nice for O_{J} ⟺ E ∩ Lin(J) has an almost essential subset of cardinality |J| or an essential subset. In particular, E is null for O_{J} ⟺ E ∩ Lin(J) has an essential subset.

The following characterization of (K^{n}\Hyper(I))-niceness then follows almost immediately.

Lemma 7. An n-tuple E of finite subsets of (ℕ ∪ {0})^{n} is nice for K^{n}\Hyper(I) ⟺ for all J ⊇I, E ∩ Lin(J) has an almost essential subset of cardinality |J| or an essential subset. In particular, E is null for K^{n}\Hyper(I) ⟺ for all J ⊇I, E∩Lin(J) has an essential subset.

The characterization of W -niceness for W an arbitrary union of orbits is then completely analogous.

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

   E-mail address: rojas@math.mit.edu