A CONVEX GEOMETRIC APPROACH TO COUNTING THE ROOTS OF A POLYNOMIAL SYSTEM

Consider a polynomial system F=(f(1),...,f(n)) in n variables with complex coefficients. A standard way to bound the number of isolated roots of F in C-n is to multiply and add the degrees of the f(1) in a straightforward computation described explicitly by some variant of Bezout's theorem. Unfortunately, even if one knows a priori which monomial terms will appear, this upper bound can be far from exact. In practice, one frequently knows which monomial terms will appear in a polynomial system before one actually decides to count or approximate its roots, so a fast accurate root count which takes this additional information into account is vital. We propose a much tighter upper bound on the number of isolated roots of F in C-n, and give an explicit combinatorial geometric criterion for when it is exact. As a corollary we obtain a geometric characterization of the average-case computational complexity of root counting. Our root count is a formula derived from the theory of toric varieties and its computation involves finding the mixed volume of n shadowed polytopes in R(n). Our formula generalizes the BKK bound (Bernshtein, 1975; Kushnirenko, 1976; Khovanskii, 1978; Canny and Rojas, 1991) in four ways: (1) For any r epsilon{0,...,n}, our formula can be used to count the roots whose first r coordinates are nonzero. (The BKK bound only handles the r=n case.) As a corollary we obtain that for fixed n, all of these root counts (for generic F) can be done in time polynomial in the numbers of monomial terms of the f(1). (2) We refine Bernshtein's (1975) algebraic criterion for exactness of the BKK bound into a complete classification of the subsets of the coefficients of F whose genericity guarantees exactness in our generalized bound. (3) Our results are stated in terms of arbitrary algebraically closed fields of any characteristic. (The BKK bound was originally stated only over the complex numbers.) (4) We generalize all of the above to results on the number of (n - k)-dimensional components of the zero set of (f(1),...,f(k)) when k less than or equal to n.