SOME NEW APPLICATIONS OF TORIC GEOMETRY

J. MAURICE ROJAS

Abstract. This paper reexamines univariate reduction from a toric geometric point of view. We begin by constructing a binomial variant of the u-resultant and then retailor the generalized characteristic polynomial to fully exploit sparsity in the monomial structure of any given polynomial system. We thus obtain a fast new algorithm for univariate reduction and a better understanding of the underlying projections. As a corollary, we show that a refinement of Hilbert’s Tenth Problem is decidable within single-exponential time. We also show how certain multisymmetric functions of the roots of polynomial systems can be calculated with sparse resultants.

1. Introduction

We give a new approach for combatting degeneracy problems which occur when reducing large polynomial systems to univariate polynomials. Taking a positive attitude, we will actually make use of these degeneracies to better understand polynomial system solving. We do this by applying new observations involving toric varieties to establish faster, more reliable algorithms for univariate reduction. Our techniques provide an intrinsic geometric setting for such reductions and fully exploit the sparsity of any polynomial system specified by its monomial term structure.

Algebraically reducing problems involving polynomial systems to simpler questions involving a single univariate polynomial is a technique which has been known for over a century, and has been applied with increasing efficiency in computational algebra over the last two decades. (For example, see [Laz81, KL92, PK95, GHMP95] and the references therein.) However, there are difficulties with this method which still have not been completely addressed. Three such problems are the following: A: Since univariate reduction corresponds to projecting the solution space onto a

projective line, the fiber over a point with finite coordinate might contain roots at infinity.

Date: February 10, 1997.

This research was partially funded by N.S.F. grant DMS-9022140 and an N.S.F. Mathematical Sciences Postdoctoral Fellowship.

Revision of an earlier version which appeared in Foundations of Computational Mathematics, selected papers of a conference, held at IMPA in Rio de Janeiro, January 1997, Felipe Cucker and Mike Shub (eds.), Springer-Verlag.

B: The univariate polynomial one reduces to might be identically zero, due to (1) degeneracies in the underlying projection, or (2) the presence of infinitely many roots.

C: Univariate reduction is still too slow for many problems of interest. We circumvent A by the technique of toric laminations. By constructing a generalization of Canny’s generalized characteristic polynomial (GCP) [Can90, Shu93] — the toric (or sparse) GCP — we can dispose of B_{2}. Our toric geometric approach also helps us better understand B_{1}. These two new techniques are contained in theorems 1–3 below.

Although problem B_{2} was solved earlier in [Ren87, Can90], the toric GCP greatly improves the complexity bounds given there. In particular, we address problem C by using the sparse resultant [GKZ90, EC95] throughout our development. Fast methods for polynomial system solving were derived via the sparse u-resultant in [Emi94, EC95] but problems A and B were not addressed there. Our approach to univariate reduction thus unifies the GCP with the the sparse u-resultant. Furthermore, we generalize both techniques to certain toric varieties [KKMS73, Ful93, Stu95].

One advantage of a toric variety setting is reducing the problem of exact root counting for polynomial systems, almost completely, to convex geometry. Generically sharp upper bounds on the number of (complex) isolated roots, in terms of mixed volume, first appeared just over two decades ago [Kus75]. These bounds have since been generalized to algebraically closed fields [Dan78, Roj97a] and to various subsets of affine space (other than the algebraic torus) [Kho78, HS96, Roj97a]. However, the following algorithm appears to be the first example of a convex geometric approach to counting the exact number of roots. (We will assume henceforth that all our polynomials and roots are considered over an algebraically closed ground field K.)

Theorem 1. Let F (x_{1}, …, x_{n}) be an n × n polynomial system with support E := (E_{1}, …, E_{n}) such that M(E) > 0. Also let P_{E} be the sum of the convex hulls of the E_{i}, and pick a ∈ ℤ^{n} \ {O} such that the segment [O, a] is not parallel to any facet of P_{E}. Define π_{a}(u_{+}, u_{−}) := Res_{E_{a}}(F, u_{+} + u_{−}x^{a}) where {u_{±}} is a pair of algebraically independent indeterminates and E_{a} := (E, {O, a}). Finally, let ε_{±} be the lowest exponent of u_{±} occurring in any monomial of π_{a}. Then F has exactly N := M(E) − ε_{+} − ε_{−} isolated roots (counting multiplicities) in (K^{∗})^{n}, provided N <∞.

In the above, Res_{⋆}(·) and M(·) respectively denote the sparse resultant and mixed volume [EC95, DGH96, Roj97a]. The key contributions of the above theorem are (a) fibering the solution space by maps more general than coordinate projections, and (b) making explicit use of roots at toric infinity when doing univariate reduction.

We may also calculate the number of distinct roots in a similar way.

Corollary 1. Following the notation and assumptions of theorem 1, let π′_{a}(u_{+}, u_{−}) be the square-free part of π_{a}(u_{+}, u_{−}). Also let ε′_{±} be the lowest exponent of u_{±} occuring in π′_{a}. Then F has exactly N′:=deg(π′_{a}) − ε′_{+} − ε′_{−} roots in (K^{∗})^{n}, provided N′ <∞ and the projection of roots {ζ ∈(K^{∗})^{n} | F (ζ)=0} ⟶ {ζ^{a}} is injective.

This corollary is proved alongside theorem 1 in section 5.

By instead calculating a particular coefficient of π_{a}, we can actually compute certain multisymmetric functions of the roots of F and thus do more than just count the number of isolated roots. Admittedly, such a computation can be rather difficult, but recent advances in interpolation techniques, e.g., [Zip93], are making this approach increasingly feasible. So let us at least give explicit formulae for the coefficients of π_{a} in terms of multisymmetric functions.

Definition 1. For any w ∈ℝ^{n}\{O}, let E_{i}^{w} be the set of points of E_{i} having minimal inner product with w. Also, let E^{w}:=(E_{1}^{w}, …, E_{n}^{w}) and, when w ∈ℚ^{n}\{O}, let p_{w} ∈ ℤ^{n} be the first lattice point not equal to the origin encountered along the ray generated by w. Finally, let L(E, a), the ambiguity locus, be the subvariety of T_{P_{E}} \ (K^{∗})^{n} corresponding to the union of all faces of P_{E} having an inner normal perpendicular to the segment [O, a].

Remark 1. The toric variety (over K), T_{P}, corresponding to a polytope P is detailed in [KSZ92, Ful93, GKZ94, Stu95, Roj97a]. Polynomial roots in a toric compactification are described (in a manner closest to our present framework) in [Roj97a].

Corollary 2. Following the notation of theorem 1, assume instead that a is any point in ℤ^{n}\{O} and ε_{+}, ε_{−} < ∞. Then π_{a} is a homogeneous polynomial of degree M(E) and, for any d∈{0, …, M(E) − ε_{+} − ε_{−}}, the coefficient of u_{−}^{d+ε_{−}}u_{+}^{M(E)−d−ε_{+}} in π_{a} is precisely

C ∑ ∏_{j=1}^{d} ζ(j)^{a},

where C ∈ K^{∗} is independent of d, the sum ranges over all cardinality d multisets {ζ(1), …, ζ(d)} ⊆ Z_{F}, and Z_{F} is the multiset of roots of F in (K^{∗})^{n} ∪ L(E, a). Furthermore, if ε_{+} =ε_{−} =0 then C is precisely

(−1)^{n} (∏_{w} Res_{E^{w}}(F)^{−p_{w}·a}) ,

where the product ranges over all inner facet directions of P_{E} having negative inner product with a. ■

Multisets are simply sets where repeated elements are allowed, and whose subsets have repetitions appropriately restricted [GKP94]. For example, if Z_{F} contains −1 as a root of multiplicity 5, then no subset of Z_{F} can have more than five −1’s. So in essence, the coefficients of π_{a} (when suitably normalized) are just elementary symmetric functions of a-monomials of certain roots of F.

The above corollary follows easily from theorem 1 and the Pedersen-Sturmfels product formula [PS93].^{1} Moreover, since the sparse resultant is invariant under muliplication of the individual polynomials by a monomial, we can compare the coefficients of π_{a} and π_{−a} to obtain the following beautiful identity.^{2}

Corollary 3. Following the notation and assumptions of corollary 2, ε_{+} =ε_{−} =0 ⟹

∏_{ζ∈Z_{F}}(ζ^{a}) = ∏_{w} Res_{E^{w}}(F)^{p_{w}·a}

where the product ranges over all inner facet directions of P_{E}. ■

Recall that a ridge is a polytope face of codimension 2 [Zie95]. Although the “bad” case of theorem 1 (N =∞) is an annoyance, it is a small annoyance and can actually be made use of in certain cases.

Theorem 2. Following the notation and assumptions of theorem 1, N = ∞ ⟺ F has a root lying in L(E, a) or infinitely many roots in (K^{∗})^{n}. Also, within the space of all systems with support contained in E, the F with N = ∞ form a subvariety of codimension ≥2.

Thus, if the roots of F avoid the ambiguity locus, F has infinitely many roots in (K^{∗})^{n} ⟺ N = ∞. In particular, it follows directly from the definition of L(E, a) that codimL(E, a) = 2, under the assumptions of theorem 2. (Since L(E, a) then corresponds to a finite set of ridges [Ful93, Roj97a].)

We can completely avoid amiguity loci by replacing the binomial u_{+} + u_{−}x^{a} in our preceding results with another specially chosen indeterminate polynomial. This is detailed further in [Roj97c] and, to a certain extent, in the result we quote below. However it is worth noting that the roots of F always avoid L(E, a) when n<3 and E is the support of F (cf. lemma 1).

Remark 2. The existence of infinitely many roots of F at toric infinity and the existence of a root of F within the ambiguity locus are independent in general (cf. section 3). Thus it is worthwhile to know something about L(E, a).

Remark 3. A correspondence useful for visualizing theorems 1 and 2 is to identify toric infinity (T_{P}\(K^{∗})^{n}) with the boundary of the polytope P (cf. definition 2). Computing π_{a} then amounts to splitting ∂P_{E} into two signed halves, much like cracking an egg-shell. In particular, the half with sign ± consists precisely of those faces of P_{E} having an inner normal with ± inner product with a. The ambiguity locus is then precisely the common boundary of these two halves. We will see later that π_{a} can be viewed as a coordinatization of a particular rational map T_{P_{E}} −−→ ℙ_{K}^{1}. Thus, provided no roots lie in the ambiguity locus, ε_{±} is the sum of the intersection numbers of the roots of F which lie in the ± half.

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

2Alicia Dickenstein pointed out the K = ℂ of the above formula (due to Cattani, Dickenstein and Sturmfels) to the author at the conference where this paper was presented. Shortly after, the author realized that this formula could also follow easily from corollary 2.

A general way to deal with the existence of infinitely many roots of F within a given toric compactification is the following result announced below.

Theorem 3. [Roj97c] Following the notation of theorem 1, suppose g(x):=∑_{e∈A} u_{e}x^{e} where the u_{e} are algebraically independent indeterminates and A ⊂ ℤ^{n} is nonempty and finite. Suppose further that P:= (P_{1}, …, P_{n}) is an n-tuple of integral polytopes in ℝ^{n} containing the support of F, and let D be an irreducible fill of P. Setting F^{∗}:= (∑_{e∈D_{i}} x^{e} | i ∈ [1..n]), define H(s; u) := Res_{(E,A)}(F − sF^{∗}, g), where s is a new indeterminate. Finally, considering H as a polynomial in s with coefficients in K[u], let F_{A}(u) be the coefficient of the lowest power term of H. Then F_{A} is a homogeneous polynomial with the following properties:

1. F_{A} is divisible by g(ζ), for any root ζ ∈(K^{∗})^{n} of F.

2. If P is compatible with Conv(A), then F_{A} has degree M(P) and to every irreducible factor of F_{A} there naturally corresponds a root of F in T_{P}, where P:=∑ P_{i}.

We call H a toric (or sparse) generalized characteristic polynomial for (F, A). ■

The combinatorial portion of the above theorem can be explained as follows: We say that D fills P iff D := (D_{1}, …, D_{n}) satisfies D_{i} ⊆ P_{i} for all i ∈ [1..n] and M(D) = M(P) [Roj94, RW96]. An irreducible fill is then simply a fill which is minimal with respect to n-tuple containment. Finding such a D amounts to a combinatorial preprocessing step which need only be done once for a given set of problems, provided E is fixed. Compatibility is defined in section 5 and the toric GCP is briefly compared to the original GCP in section 6. Combined with the toric variety version of Bernshtein’s theorem [Roj97a], we see that the above theorem gives us a resultantbased method to work with the isolated roots of a sparse polynomial system, even in the presence of infinitely many roots. Furthermore, the roots defined by F_{A} which do not correspond to any isolated root of F can be usefully interpreted as contributions from the excess components.

We apply our main theorems to some simple examples in section 3. Our results are also very useful for root counting over ℝ, ℚ, and even ℤ. For example, one can combine standard univariate techniques such as Sturm sequences [GLRR94, Roy95] with our preceding results to quickly count the number of real roots [Roj97b]. Better still, we can go to an even smaller ring: In section 4 we will give a short proof (under some mild hypotheses) of the following refinement of Hilbert’s Tenth Problem [Mat93].

Theorem 4. [Roj97d] Consider, for any nonnegative integer d, the following collection of Diophantine systems:

Hilb(d): Multivariate polynomial systems with integer coefficients and d-dimensional complex solution set. Then there is an algorithm which, given any instance of Hilb(0), finds all integer solutions, or certifies that there are none, within single-exponential time. ■

All of the above results stem from an observation on the vanishing of the sparse resultant. In particular, one basic property of the sparse resultant is that

(⋆) (F, f_{n+1}) has a root in (K^{∗})^{n} ⟹ ResĒ(F, f_{n+1})=0

(provided Ē =(E, E_{n+1}) and f_{n+1} is a polynomial over K with support contained in E_{n+1} ⊂ ℤ^{n}). However, the converse assertion is \underline{not} always true. (The polynomial system (x + y + 1, x + y + 2, x + y + 3) with Ē ={O, ê_{1}, ê_{2}}^{3} gives a simple counterexample reducing to the vanishing of a 3 × 3 determinant.) The correct statement in which both implications hold seems to be known only folklorically, while the unmixed case E_{1} =⋯=E_{n+1} =A (over ℂ) is contained in various recent works, e.g., [KSZ92, GKZ94]. So we will make use of the following more general result.

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

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

for some i∈[1..n],

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

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

In the above, D_{P} (f_{i}, P_{i}) is the toric effective divisor of T_{P} corresponding to (f_{i}, P_{i}) (cf. definition 2). This result provides a geometric analogue, over a general algebraically closed field, of the product formula for the sparse resultant [PS93].

We close this introduction with an important note:

In addition to the applications we have presented, our approach to univariate reduction provides a first step toward an intrinsic method for root finding in the algebraic torus (K^{∗})^{n}. Although one could in principle reduce to various coordinate subspaces to perform “sparse” elimination theory in K^{n}, such an approach runs into complications with intersection multiplicities on the coordinate hyperplanes and is really not intrinsic to K^{n}. We propose a more intrinsic (and efficient) approach to affine elimination theory by defining a new resultant operator — the affine sparse resultant — in [Roj97e]. Following this route, all of our main theorems generalize easily to root finding in affine space minus an arbitrary union of coordinate hyperplanes. This is pursued in greater depth in [Roj97a, Roj97e] and the complexity bound of theorem 4 is further refined in the latter work.

2. Related Work

We point out a few important recent approaches to elimination theory which can profit from our results.

From an applied angle, our observations on degeneracies and handling polynomial systems with infinitely many roots nicely complement the work of Emiris and Canny [EC95]. In particular, their sparse resultant based algorithms for polynomial system solving can now be made to work even when problem B occurs. Also, an added benefit of working torically (as opposed to the classical approach of working in projective space) is the increased efficiency of the sparse resultant: the resulting matrix calculations (for polynomial system solving) are much smaller and faster. In particular, whereas it was remarked in [Can90] that Gröbner basis methods are likely to be faster than the GCP for sparse polynomial systems, the toric GCP appears to be far more competitive in such a comparison.

From a more theoretical point of view, our focus on univariate reduction is a useful addition to Sturmfels’ foundational work on sparse elimination theory in the large [Stu93]. (We also point out that [Stu93] provides a wonderfully clear introduction to some of the toric variety techniques we refer to.)

Going further into the intersection of algebraic geometry and complexity theory, there is a beautiful new approach to elimination theory founded by the school of Heintz, et. al. [PK95, GHMP95]. Our results fill in some toric geometry missing from their more algebraic framework. In particular, we propose that toric laminations, i.e., “fibering” T_{P_{E}} by toric projections (instead of fibering (K^{∗})^{n} by coordinate projections), can enhance their methods. For example, although their formulation in terms of straight-line programs is extremely general, it appears that their complexity bounds can be significantly improved with our techniques in the case of polynomial systems which are “sparse” in the specified supports sense we use here. This is explored further in [Roj97d].

3. Examples

We will give a 2 × 2 example of our first two theorems.

3.1. Root Counting with Sparse Resultants. Let n=2 and consider the bivariate polynomial system F:=(x^{3} + y^{4} − 1, x^{4} + y^{5} − 1). Also let E_{1} and E_{2} respectively be the supports {O, (3, 0), (0, 4)} and {O, (4, 0), (0, 5)}. Clearly then the Newton polygons are two triangles and the segment [O, (1, 1)] is not parallel to any edge of the quadrilateral P_{E} := Conv(O, (7, 0), (0, 9), (4, 4)). So we can set a := (1, 1) and apply theorem 1 to count the roots of F.

We are now ready to compute the sparse resultant Res_{E_{a}}(F, u_{+} + u_{−}xy), where E_{a}:=(E_{1}, E_{2}, {O, (1, 1)}) and the coefficients of F have been replaced by algebraically independent indeterminates.^{3} To do this, we can use Maple to calculate the Sylvester (2 × 1) resultants of the pairs (f_{2}, u_{+} + u_{−}xy) and (f_{1}, u_{+} + u_{−}xy), eliminating the variable y. Let us respectively call these resultants f_{−1} and f_{−2}. Using the Sylvester resultant one last time on (f_{−1}, f_{−2}) to eliminate x, we arrive at a multiple of the sparse resultant we are looking for. (This fact follows easily from the characterization of the sparse resultant as the (nonzero) polynomial of lowest total degree satisfying property (⋆) from the introduction [Stu93, Roj97d].)

The preceding computations, modulo typing, takes only fractions of a second on a Sun 4m Computeserver. From [Stu94] we know that the sparse resultant itself should have degree M(E_{1}, E_{2}) + M(E_{1}, {O, a}) + M(E_{2}, {O, a}) = 16 + 7 + 9 = 32. (This calculation is easily done by hand via the general formula M(E_{1}, E_{2}) = Area(Conv(E_{1} + E_{2})) − Area(Conv(E_{1})) − Area(Conv(E_{2})) [Sch94, DGH96].) So by factoring with Maple (which takes just under 2 seconds) we can isolate the sparse resultant and specialize coefficients to obtain

π_{(1,1)}(u_{+}, u_{−}) = Res_{E_{a}}(x^{3} + y^{4} − 1, x^{4} + y^{5} − 1, u_{+} + u_{−}xy) =

20u_{−}^{9}u_{+}^{7} + 31u_{−}^{8}u_{+}^{8} + 12u_{−}^{7}u_{+}^{9} + 14u_{−}^{5}u_{+}^{11} + 14u_{−}^{4}u_{+}^{12} + 7u_{−}^{3}u_{+}^{13} − 9u_{−}^{2}u_{+}^{14} + u_{−}u_{+}^{15} + u_{+}^{16}

So ε_{+} = 7, ε_{−} = 0, and theorem 1 tells us that F has exactly 16 − 7 = 9 roots, counting multiplicities, in (ℂ^{∗})^{2}. Furthermore, a one-line Maple calculation shows that π_{(1,1)} is irreducible over ℚ. So corollary 1 (and basic Galois theory) tells us that the multiplicity of every root of F in (ℂ^{∗})^{2} is 1.

The roots of F can also be counted via Gröbner basis methods but the toric geometry in this example is rather nice to observe. In particular, the coordinate cross {xy = 0} is naturally embedded in T_{P_{E}} and corresponds precisely to the two lower-left edges of P_{E} (cf. remark 3 and definition 2). Furthermore, the ambiguity locus consists of two distinct points which, due to the fact that π_{a} is not identically 0 (cf. theorem 2), the roots of F have luckily avoided. Also ε_{+} =7 ⟹ F has precisely 7 roots, counting multiplicities, on the coordinate cross. The latter fact can also be easily checked with a little commutative algebra.

We have included timing information solely for illustrative purposes. In particular, our calculations can be sped up tremendously with suitably specialized code.

4. A Refinement of Hilbert’s Tenth Problem

We will present a concise proof of theorem 4 under the following three hypotheses:

1. The instances of Hilb(0) considered are n × n polynomial systems.

2. The complex roots of an instance must have all coordinates nonzero.

3The published version of this paper contains an erroneous computation (due to a software error) of this resultant. This was observed by John Dalbec at the conference where this paper was presented, and the calculation below is due to him. The author is deeply indebted to Professor Dalbec’s astute observation.

3. No instance can have a complex root at toric infinity.

Note that (1) and (2) are of a combinatorial nature: they restrict the number and dimensions of the supports, as well as their intersections with the coordinate subspaces. On the other hand, (3) is of a more algebraic nature and, when the supports are fixed, is easily shown to fail only on a codimension 1 subvariety of polynomial systems, e.g., [Roj97a, Main Theorem 2].

The above hypotheses are present mainly for technical reasons and are removed in [Roj97d]. They may also be removed with other recent techniques [BPR94, PK95, GHMP95], but through our toric techniques it is possible to obtain a general complexity bound with near quadratic dependence on the mixed volume [Roj97c]. This would be the best asymptotic bound to date for solving Diophantine systems. Proof of Theorem 4: First we outline our algorithm:

Step 1: Following the notation of theorem 3, let A be the vertices of a standard n-simplex

in ℝ^{n} and P the n-tuple of Newton polytopes of F. Form the polynomial F_{A}. Step 2: Using the Lenstra-Lenstra-Lovasz algorithm [LLL82], factor F_{A} over ℤ. Step 3: Any integral root (z_{1}, …, z_{n}) ∈ ℤ^{n} of F corresponds precisely to an integral

factor of F_{A} of the form u_{O} + z_{1}uê_{1} + ⋯ + z_{n}uê_{n}.

Step 1 runs in time polynomial in the mixed volume, applying hypotheses (1) and (3), and the results of [Stu93, Emi96]. In fact, we are merely computing a “sparse” variant of the u-resultant in Step 1. To prove this (and the fact that this sparse u-resultant is not identically 0) one uses slightly more general versions of theorems 1 and 2 [Roj97d]. One also needs the fact that hypotheses (1) and (3) together imply that the complex zero set of F in (K^{∗})^{n} is zero-dimensional, but this is an immediate consequence of [Roj97a, Corollary 3]. We also point out that working more generally in terms of F_{A} aids in later removing hypothesis (3) [Roj97d].

To see that Step 2 runs within time single-exponential in the input size, one need only observe that (a) the coefficient growth in the sparse u-resultant calculation can be reasonably bounded, and (b) the LLL-algorithm runs within time single-exponential in n and polynomial in the bit-sizes of the coefficients of F. Part (a) is detailed in [Roj97d], and part (b) follows easily from the univariate case covered in [LLL82].

That we can terminate as described in Step 3 follows immediately from hypothesis (2) and the Vanishing Theorem for Resultants. ■

We conclude this section with some brief notes on related work.

First, we point out the rather surprising fact that restructuring Hilbert’s Tenth Problem as the union ⋃_{d=0}^{∞} Hilb(d) seems to be new. (In particular, Hilbert’s Tenth Problem was originally stated as deciding the existence of a single integral root for one polynomial in several variables.) Although the results of [Jon82] imply that Hilb(8) is undecidable, nothing seems to be known about Hilb(d) for 0 < d < 8. We find this shocking, considering the vast effort within arithmetic geometry to use complex geometric invariants in Diophantine problems, e.g., Falting’s theorem and the deep conjectures of Lang and Vojta [CS86].

We also point out that Hilb(0) being a single-exponential problem may not be so new: Teresa Krick and Luis-Miguel Pardo-Vasallo have pointed out to the author that theorem 4 can also be readily derived from [PK95, GHMP95]. (Indeed, such an argument could have also been derived directly from [LLL82] and [Ren87] in 1987.) Pardo-Vasallo has also pointed out that Marie-Françoise Roy lectured in 1995 on a similar result, presumably derived from [BPR94]. Nevertheless, optimal bounds are open territory; not to mention the 6-long gap in the status of Hilb(d).

5. Toric Varieties and Sparse Resultants

Our notation is a slight variation of that used in [Ful93], and is described at greater length in [Roj97a]. We will assume the reader to be familiar with normal fans of polytopes and the construction of a toric variety from a fan [Ful93, GKZ94]. However, we will at least list our cast of main characters: Definition 2. [Roj97a] Given any w ∈ℝ^{n}, we will use the following notation: T = The algebraic torus (K^{∗})^{n} P^{w} = The face of P with inner normal w σ_{w} = The closure of the cone generated by the inner normals of P^{w} U_{w} = The affine chart of T_{P} corresponding to the cone σ_{w} of Fan(P) L_{w} = The dim(P^{w})-dimensional subspace of ℝ^{n} parallel to P^{w} x_{w} = The point in U_{w} corresponding to the semigroup homomorphism σ_{w}^{∨} ∩ ℤ^{n} ⟶

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

E_{P} (Q) = The T -invariant Weil divisor of T_{P} corresponding to a polytope Q with which P

is compatible

Div(f) = The Weil divisor of T_{P} defined by a rational function f on (K^{∗})^{n} D_{P} (f, Q) = Div(f) + E_{P} (Q) = The toric effective divisor of T_{P} corresponding to (f, Q) D_{P} (F, P) = The (nonnegative) cycle in the Chow ring of T_{P} defined by ⋂_{i=1}^{n} D_{P} (f_{i}, P_{i})

We will say that a polytope P (resp. an n-tuple P) is compatible with Q iff every cone of Fan(Q) is a union of cones of Fan(P) (resp. a union of cones of Fan(P_{i}) for each i) [Kho77, Roj97a]. We will also make frequent use of the natural correspondence between the face interiors {RelIntP^{w}} and the T -orbits {O_{w}} [KSZ92, Ful93, GKZ94]. The following lemma gives a more explicit algebraic analogy between the vertices of P and the maximal affine charts of T_{P}. Lemma 1. [Roj97a] Suppose F is a k × n polynomial system over K with support contained in a k-tuple of integral polytopes P:= (P_{1}, …, P_{k}) in ℝ^{n}. Assume further that P is a rational polytope in ℝ^{n} compatible with P. Then 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]. ■

Theorems 1 and 2 will follow easily from the Vanishing Theorem for Resultants via following two lemmata below.

Lemma 2. Following the notation of theorem 1, define

P_{E}:=(Conv(E_{1}), …, Conv(E_{n})).

Then the map x ↦ x^{a} extends to a proper morphism ϕ_{a} : T_{P_{E}}\L(E, a) ⟶ ℙ_{K}^{1}. Also, if D_{P_{E}}(F, P_{E}) has zero-dimensional intersection with (K^{∗})^{n} and avoids the ambiguity locus, then π_{a} is, up to a nonzero constant multiple, the Chow form of the subvariety ϕ_{a}(D_{P_{E}}(F, P_{E})) of ℙ_{K}^{1}. ■

Lemma 3. Following the notation of theorem 1, pick points a(1), …, a(n−1) ∈ ℤ^{n} which together generate a hyperplane in ℝ^{n} which is not parallel to any facet of P_{E}. Then F has infinitely many roots in (K^{∗})^{n} ⟹ the polynomial p(u_{+}, u_{−}):=∏_{i=1}^{n−1} π_{a(i)} is identically 0. ■

Sufficiently armed, let us now prove theorem 2. Proof of Theorem 2: Suppose that F has no roots within L(E, a) and only finitely many roots within (K^{∗})^{n}. Then it follows from lemma 2 that u_{+} (resp. u_{−}) divides π_{a} iff F has a root in some torus orbit O_{w} with w·a > 0 (resp. w · a < 0). More to the point, if c ∈ K^{∗} then it follows similarly that u_{+} + cu_{−} divides π_{a} iff some root of F lies in the closure of the hypersurface {x^{a} = c} in T_{P_{E}}. Furthermore, lemma 1 immediately implies that any two (distinct) hypersurfaces of this form must intersect precisely on the ambiguity locus. Thus π_{a} can not be identically 0 and we obtain that N is finite.

Now assume that F has a root in the ambiguity locus. Then, by the Vanishing Theorem for Resultants and what we’ve just learned about the hypersurface {x^{a} =c}, π_{a} must be divisible by infinitely many distinct binomials of the form u_{+} + cu_{−}. So the existence of a root of F within the ambiguity locus implies that N =∞. Similarly, the existence of infinitely many roots of F within (K^{∗})^{n} implies that N =∞ as well. Thus we are done with the first portion of the theorem.

As for the codimension of the space of “degenerate” F being ≥2, first consider the F which have a root on the ambiguity locus. These F actually form a codimension 2 subvariety. To see this, first note that F has a root in O_{w} ⟺ the initial term system in_{w}(F) has a root in (K^{∗})^{n} [Roj97a, corollary 2]. By the definition of L(E, a), we can then conclude via theorem 1.3 of [Stu94]. (Although the results of [Stu94] are stated over the complex numbers, this is only a minor technicality: in this case, the results of [Roj97a] immediately imply that we can apply theorem 1.3 over any algebraically closed field.)

As for the F with infinitely many roots in (K^{∗})^{n}, assume temporarily that the coefficients of F are algebraically independent indeterminates. That the F with infinitely many roots in (K^{∗})^{n} define a subvariety of codimension ≥2 must certainly be an old result. However, for completeness, we will give a quick proof: Following the notation of lemma 3, Hilbert’s Irreducibility Theorem [Lan83] readily implies that we can choose α, β, γ, δ ∈K^{∗} such that the polynomials p(α, β) and p(γ, δ) are relatively prime in K[C_{E}]. So, by lemma 3, these F are indeed contained in a codimension 2 subvariety: {C_{E} | p(α, β)=q(γ, δ)=0}. ■

So in summary, computing π_{a} amounts to laminating T_{P_{E}} with hypersurfaces of the form \overline{\{c_{+}x^{a} =c_{−}\}}. These laminae all intersect at the ambiguity locus, and toric infinity is precisely the union of the two degenerate laminae corresponding to (cf. remark 3) the ± halves of ∂P_{E}. Proof of Theorem 1 and Corollary 1: We need only state the preceding paragraph more algebraically. In particular, lemma 2 has already done this for us. We thus obtain that when N < ∞, the multiplicity of a factor c_{+}u_{+} + c_{−}u_{−} of π_{a} is precisely the sum of the intersection numbers of the components of D_{P_{E}}(F, P_{E}) lying in the fiber φ̄^{−1}([c_{−} : c_{+}]). So N (resp. N′) is indeed the exact number of roots, counting multiplicities (resp. not counting multiplicities), of F in (K^{∗})^{n}. ■

Note that it is actually possible for a positive-dimensional component of D_{P_{E}}(F, P_{E}) lying at toric infinity to make a positive (finite) contribution to N (or N′). This can be interpreted as an alternative way of associating an intersection number to an excess component [Ful84].

6. Toric Generalized Characteristic Polynomials

We will first comment briefly on the combinatorial preprocessing step. The following example illustrates a simple fundamental case.

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

We point out that the computational complexity of finding an irreducible fill is an open question. However, the connection between fills and polynomial system solving (not to mention specialized resultants) appears to be new and, we hope, provides added incentive to investigate filling. Also, even if finding a fill is difficult, this step need only be done once for a given family of problems, provided E remains fixed. The situation where the monomial term structure of a polynomial system is fixed once and for all (and the coefficients may vary thousands of times) actually occurs frequently in many practical contexts, such as robot control or computational geometry.

In any event, the toric GCP is an algebraic perturbation method and irreducible fills provide a combinatorial means of inducing “general position” into the roots of F_{A}. For example, the following lemma implies that F^{∗} is sufficiently generic in a useful sense.

Lemma 4. Following the notation and assumptions of theorem 3, for any point v lying in any D_{i}, there exists a w ∈ ℝ^{n} \{O} such that {i} is the unique essential subset of D^{w} and D_{i}^{w} = {v}. In particular, F^{∗} has exactly M(P) roots (counting multiplicities) in (K^{∗})^{n}. ■

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

Given that F^{∗} thus has maximally many isolated roots (counting multiplicities) and no excess components in (K^{∗})^{n}, theorem 3 then follows easily from the Vanishing Theorem for Resultants and an algebraic homotopy argument. A similar homotopy technique appears in [RW96, Roj97a], and the dense case (with K = ℂ) is covered in [Can90, Shu93]. (However, toric variety language was not used in the last two works.) Thus, the usual GCP is (almost) the special case of the toric GCP where T_{P} is complex projective space.

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

7. Acknowledgements

The main results of this paper were presented during a visit of the author at City University of Hong Kong. The author thanks Steve Smale for his invitation, warm hospitality, and even warmer beach hikes. Special thanks go to John Dalbec for pointing on an error in an earlier version of section 3, and to Robert L. Williams for his encouragement and keen commentary. The author also thanks his former roommates Jean-Pierre Dedieu and Gregorio Malajovich for their input, but most of all for not getting too mad at him for not washing the dishes.

Work on this paper began at MSRI and concluded at MIT. The author thanks both institutions for their support, and especially Marsh Borg at MSRI for her kind assistance.

References

[BPR94] Basu, S., Pollack, R., and Roy, M.-F., “On the Combinatorial and Algebraic Complexity of Quantifier Elimination,” in Proc. IEEE Symp. Foundations of Comp. Sci., Santa Fe, New Mexico, 1994, to appear.

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

[CS86] Cornell, Gary and Silverman, Joseph H., Arithmetic Geometry, with contributions by M. Artin, et. al., Springer-Verlag, 1986.

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

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

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

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

[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

[Emi96] , “On the Complexity of Sparse Elimination,” preprint,

INRIA, March 1996, available on-line at http://www.inria.fr/safir/SAFIR/Ioannis.html

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

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

[GHMP95] Giusti, M., Heintz, J., Morais, J. E., Pardo, L. M., “When Polynomial Systems Can Be ‘Solved’ Fast?,” Proc. 11\underline{th} International Symposium, AAECC-11, Paris, France, July 17-22, 1995, G. Cohen, M. Giusti and T. Mora, eds., Springer LNCS 948 (1995) pp. 205–231.

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

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

[GLRR94] Gonzalez, L., Lombardi, H., Recio, T., Roy, M.-F., “Sturm-Habicht Sequence, Determinants and Real Roots of Univariate Polynomials,” Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, B. Caviness and J. Johnson, Eds., Springer-Verlag, Wien, New York, 1994, to appear.

[HS96] Huber, Birkett and Sturmfels, Bernd, “Bernshtein’s Theorem in Affine Space,” Discrete and Computational Geometry, to appear, 1996.

[Jon82] Jones, James P., “Universal Diophantine Equation,” Journal of Symbolic Logic, 47 (3):549– 571.

[Kho77] Khovanskii, A. 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.

[KL92] Kapur, Deepak and Lakshman, Yagati N., “Elimination Methods: an Introduction,” Symbolic and Numerical Computation for Artificial Intelligence, B. Donald et. al. (eds.), Academic Press, 1992.

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

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

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

[Lan83] Lang, Serge, Fundamentals of Diophantine Geometry, Springer-Verlag, 1983.

[Laz81] Lazard, D. “Résolution des Systèmes d’équations Algébriques,” Theor. Comp. Sci. 15, pp. 146–156.

[LLL82] Lenstra, A. K., Lenstra, H. W., and Lovász, L. “Factoring Polynomials with Rational Coefficients,” Math. Ann. 261 (1982), pp. 515-534.

[Mat93] Matiyasevich, Yuri V., Hilbert’s Tenth Problem, MIT Press, MIT, Cambridge, Massachusetts, 1993.

[PK95] Pardo-Vasallo, Luis-Miguel and Krick, Teresa, “A Computational Method for Diophantine Approximation,” to appear in Proc. MEGA ’94, Birkhäuser, Progress in Math. (1995).

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

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

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

[Roj97a] , “Toric Intersection Theory for Affine Root Counting,” Journal of Pure and Applied Algebra, to appear. (Also available on-line at http://www-math.mit.edu/~rojas .)

[Roj97b] , “A New Approach to Counting Nash Equilibria,” Proceedings of the Conference on Computational Intelligence for Financial Engineering, Manhattan, New York, March 23–25, 1997, to appear.

[Roj97c] , “Toric Generalized Characteristic Polyomials,” submitted to the Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation. (Also

available on-line at http://www-math.mit.edu/~rojas.)

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

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

[Roy95] Roy, Marie-Françoise “Basic Algorithms in Real Algebraic Geometry and their Complexity: from Sturm Theorem to the Existential Theory of Reals,” preprint, IRMAR, Rennes, France, 1995.

[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, also

available on-line at http://www-math.mit.edu/~rojas.

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

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

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

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

[Zie95] Ziegler, Gunter M., Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.

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

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