EXTENSIONS AND CORRECTIONS FOR: “A CONVEX GEOMETRIC APPROACH TO COUNTING THE ROOTS OF A POLYNOMIAL SYSTEM^{1}”

J. MAURICE ROJAS

This paper is dedicated to the memory of Laxmi Patel.

Abstract. This brief note corrects some errors in the paper quoted in the title, highlights a combinatorial result which may have been overlooked, and points to further improvements in recent literature.

1. Introduction

This brief note contains important additional information relating to an earlier paper of the present author: “A Convex Geometric Approach to Counting the Roots of a Polynomial System,” Theoretical Computer Science 133 (1994), pp. 105-140 (henceforth referred to as [Roj94]). This paper gave various extensions of the seminal works [Kus75, Ber75, Kus76, Kho77] relating root counting for systems of polynomial equations to volumes of polyhedra. We will report (briefly) on the status of some of these extensions, and correct some errors appearing in [Roj94].

For the sake of brevity, we will not review any notation or definitions, since they are already amply covered in [Roj94] and the more recent [Roj96b]. However, we point out that the latter paper is readily available on-line at http://www-math.mit.edu/~rojas.

We begin, in the following section, by pointing out a combinatorial result from [Roj94] which seems to have gone ignored. (In particular, a special case of [Roj94, Corollary 3] was the main result of a paper completed in 1996 by another author!) In the next section we then discuss certain problems within root counting, for n × n polynomial systems, which are close (or not so close) to a satisfactory solution. We then provide a list of corrigenda for [Roj94] in the final section.

2. Filling and Counting

A combinatorial corollary of the results of [Roj94] gave the first known constructive solution of the filling problem for rational polytopes [Roj94, DRS96]. (This also resolves (for rational polytopes) a conjecture of Rolf Schneider on the mixed area measure [Sch94].) More explicitly, a combinatorial answer is given to the following question: Given an n-tuple of rational polytopes with positive mixed volume, which sub-n-tuples of rational polytopes have the same mixed volume? A partial answer is contained in Corollary 4 of [Roj94, Page 115] and a full answer appears in Corollary 9 on Page 136. The proof comes down to a carefully tailored application of Bernshtein’s Theorem [Ber75], contained in Lemmata 2–4 and Corollary 5 of [Roj94, Pages 121–123]. In particular, this convex geometric problem was first solved by an algebraic geometric result.

1The paper we are extending and correcting originally appeared in Theoretical Computer Science 133 (1994), pp.

105-140, Elsevier.

Date: October 30, 1996.

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

More importantly, the filling problem was shown to be equivalent to the (K^{∗})^{n}-counting problem. The latter problem was defined in [Roj94] as the classification of all subsets of coefficients of a given polynomial system (with fixed monomial term structure) whose genericity guarantees that the mixed volume bound is an exact root count. (The notion of (K^{∗})^{n}-counting was referred to as counting in [Roj94].) The equivalence of filling and (K^{∗})^{n}-counting is the content of Lemmata 2 and 3 of [Roj94].

Unfortunately, filling and counting were extended in an inelegant way in [Roj94]. This may have been the cause for the obscurement of filling and counting. For instance, a friend of the author’s (who will remain unnamed) wrote an entire paper based on a special case of Corollary 3 of [Roj94]. It is the author’s firm advice to ignore r-counting and (r, s, n)-filling (which are admittedly quite abstruse), and instead follow the improved construction of W-counting of [RW96, Roj96b].

It should also be remarked that an earlier solution to the (ℂ^{∗})^{n}-counting problem was incomplete: In [CR91], it was falsely asserted that the Vertex Coefficient Theorem gave a complete solution. This was later corrected in the latter author’s M.S. thesis [Roj91] and the complete solution seems to have first appeared in [Roj94, Lemmata 2 and 3]. Finally, we remark that (K^{∗})^{n}-counting is also a much simpler criterion than the ID cover of [CR91].

3. Extensions — Complete and Incomplete

Recall that (ℂ^{∗})^{n} := (ℂ\{0})^{n} is sometimes referred to as the (complex) algebraic torus. The BKK bound [Kus75, Ber75, Kus76, Kho77] was a beautiful result discovered almost two decades ago in a seminar of V. I. Arnold. This result gave an upper bound on the number of isolated roots in the algebraic torus (of n polynomial equations in n unknowns) in terms of volumes of n-dimensional polyhedra.

These upper bounds also possesed an extremely important property: they were the best possible, given only the monomial term structure. In other words, if one fixed which monomial terms appeared in a polynomial system, the resulting convex geometric formula would fail to be an exact root count only on a positive codimension algebraic subset of the coefficient space. (The terminology “generically exact” is also sometimes used in this respect.) Aside from a result of F. Minding for the case of two equations in two unknowns [Min41], this sort of optimality had never been attained by any previous upper bound.

Four natural extensions of the preceding result immediately come to mind:

1. Counting the exact number of roots (and not just a tight upper bound).

2. Extending to algebraically closed fields other than ℂ (and in particular, to positive characteristic).

3. Counting the number of roots in ℂ^{n} and in subregions other than (ℂ^{∗})^{n}.

4. Getting information about the higher (co)homology structure of other locally complete intersections.

We now briefly point out what has been done from 1994 to 1996 for these problems:

1. We first remark that there are now precise combinatorial and algebraic conditions for when the BKK bound fails to be an exact root count. Combinatorial conditions first appeared in [CR91] and were then further refined in [Roj94, RW96, Roj96b]; algebraic conditions first appeared in [Ber75] and were then refined in terms of the sparse resultant in [HS95] (as well as in independent work of the present author). The latter refinement was then extended further (and corrected) in [Roj96b].

There are, of course, many ways to count the exact number of roots directly with commutative algebra and Gröbner bases. For instance, a particularly nice approach (which works over ℝ as well) is a recent extension [PRS93] of Hermite’s method [Her56].

However, there are more recent methods based on toric geometry which make more refined use of the monomial term structure of a given problem. For example, [Roj96c] gives a new method, based on the sparse resultant, to count the exact number of roots in the algebraic torus. It is interesting to note that the original BKK bound (at worst) fails to be an exact root count on a codimension 1 subset of the space of coefficients. The method in [Roj96c] fails only on a codimension ≥ 2 subset, and an extension which always works has just been completed [Roj96d]. Thus, there are now convex geometric methods (augmented by the sparse resultant) to count the exact number of roots in (ℂ^{∗})^{n}. It is hoped that these methods will prove significantly faster for exact root counting than current Gröbner basis methods.

2. Convex geometric root counting can be done over any algebraically closed field — not just ℂ. This began with Danilov’s more abstract framework [Dan78] for the BKK bound, and was further refined in [Roj94] and [Roj96b]. The combinatorial and algebraic conditions for exactness of the BKK bound also hold over any algebraically closed field [Roj96b]. Finally, the aforementioned extensions of optimal upper bounds to exact root counts (via sparse resultants) work over any algebraically closed field as well.

3. It is indeed possible to get optimal convex geometric upper bounds on the number of roots in all of ℂ^{n}. This was first considered in [Kho78], for certain polynomial systems. Suboptimal upper bounds, valid for all polynomial systems, were then derived in [Roj94] and [RW96, LW96]. The last two papers gave, respectively, combinatorial and complex geometric conditions for when their convex geometric bounds were optimal. (It should also be noted that [RW96] gave tight upper bounds on the number of roots in affine space minus an arbitrary union of coordinate hyperplanes, over any algebraically closed field.) The first optimal bounds for ℂ^{n} minus an arbitrary union of coordinate hyperplanes, holding for all polynomial systems, appeared in [HS96]. In fact, their results held in greater generality: Any Boolean vanishing condition on the coordinates x = (x_{1}, …, x_{n}), e.g., (x_{1} = 0) ∧ (x_{3} ≠ 0) ∨ ⋯, was allowed and such roots could also be (generically) counted convex geometrically. These results were then extended to arbitary algebraically closed fields, and an alternative formula derived, in [Roj96b]. The preceding algebraic and combinatorial conditions for exactness were also extended to the case of affine space minus an arbitrary union of coordinate hyperplanes in the same paper.

4. Convex geometric upper bounds on the degree of certain positive-dimensional varieties were derived in [Roj94]. These results overlapped slightly with the deeper results of [DK87] on finding the mixed Hodge structure of a variety via convex geometry. For example, a special case of the latter work gave a convex geometric formula for the Euler characteristic of certain (generic) subvarieties of (ℂ^{∗})^{n}. Another often overlooked example is their (generically valid) computation of arithmetic genus via the number of lattice points in a polyhedron. Combined with [Roj96b], it now appears that the results of [DK87] can be completely extended to affine space and arbitrary algebraically closed fields. However, the question of finding precise algebraic or combinatorial conditions for when their more general formulae hold is still open.

In closing, we add that there are still (as of 1996) no proven convex geometric formulae for the maximal number of real roots. An important step toward this goal is the conjectural formula of Sturmfels [Stu91], later simplified by Itenberg and Roy [IR95], which attempts to generalize Descartes’ rule to higher dimensions. An interesting explicit formula for the expected number of real roots of certain random sparse polynomial systems appears in [Roj96a].

4. Corrections to [Roj94]

A Frequent Typo: In any places, nearby semicolons and commas should be reversed to correct the appearance of M(P, n), M(P; Δ_{s}, n − k), and M_{r}(P; Δ_{s}, n − k).

Page 117, Line -16: In general, the definition given for intersection multiplicity is only an upper bound. However, when W is a proper 0-dimensional component, the formula is exact and can be further simplified to the dimension (as a K-vector space) of the same R-module. To correctly define intersection multiplicity for a proper positive-dimensional component, it is necessary to use Tor(·) as in Serre’s construction [Ful84].

Page 118, Line 2: It should have been mentioned that throughout the paper, deg W actually means the degree

of the reduced variety defined by W.

Page 115, Line -1: The second to last sentence should end with “...in (ℂ^{∗})^{n}.”. Page 119, Line 15: Fact (2) is incorrect. The proper statement involves a related (canonically defined) intersection

of toric divisors and appears in [Roj96b, Corollary 2].

Page 119, Line 18: “...Supp(D_{i}) contains...”, not “...supported precisely on...” Page 119, Line 24: The line bundles O(D_{i}) are not ample in general. (I thank Professor William Fulton for

pointing this out to me.) However, through an algebraic homotopy argument, one can still obtain the “numerical ampleness” assertion of the final sentence of the proof. This is done in detail in the proof of Theorem 3 of [Roj96b].

Section 2.6 The results of this entire section are considerably simplified and improved in [RW96, HS96,

Roj96b].

Page 138, Line -15: “...when one goes...”, not “when goes”.

Reference [13]: ...is now entitled “How to Fill a Mixed Volume.”

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.

[CR91] Canny, John F. and Rojas, J. Maurice, “An Optimal Condition for Determining the Exact Number of Roots of a Polynomial System,” Proceedings of ISSAC ’91 (Bonn, Germany), ACM Press (1991), pp. 96–102.

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

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

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

[Her56] Hermite, C., “Sur le Nombre des Racines d’une Équation Algébrique Comprise Entre des Limites Données,” J. Reine Angew. Math., vol. 52, pp. 39–51 (1856).

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

[IR95] Itenberg, Ilya and Roy, Marie-Francoise, “Multivariate Descartes’ Rule,” Preprint (1995), IRMAR, Université de Rennes I, France.

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

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

[Min41] Minding, F., “Über die Bestimmung des Grades der durch Elimination hervorgehenden Gleichung,” J. Reine und Angew. Math. (1841), 22, pp. 178–183.

[PRS93] Pedersen, P., Roy, M.-F., and Szpirglas, A., “Counting Real Roots in the Multivariate Case,” Computational Algebraic Geometry, edited by Eyssette and Galligo, Progress in Mathematics 109, pp. 203–224, Birkhauser, 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.

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

[Roj96a] , “On the Average Number of Real Roots of Certain Random Sparse,” 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. (Also available on-line at

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

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

[Roj96c] , “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.

[Roj96d] , “Polynomial Equation Solving and Twisted Chow Forms,” 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.

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

[Stu91] Sturmfels, Bernd, “On the Number of Real Roots of a Sparse Polynomial System,” Hamiltonian and Gradient Flows: Algorithms and Control, (ed. A. Bloch), Fields Institute Communications, Vol. 3, American Math. Soc., Providence, RI, 1991, pp. 137–143.

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

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