COUNTING ROOTS OF POLYNOMIAL SYSTEMS (over algebraically closed fields)

A beautiful discovery made just over two decades ago has resulted in some deep connections between convex geometry and polynomial systems. This began with work of A. Kouchnirenko, David N. Bernstein, and A. Khovanskii relating the ``average'' number of complex roots of a sparse polynomial system with, of all things, mixed volumes of polytopes. Part of my recent work deals with refining and generalizing this combinatorial approach to polynomial systems.

One paper of mine (which finally appeared after an excruciating publications delay) gives a definitive generalization of these mixed volume root counts to characteristic p and affine space, including new formula for generic *local* intersection multiplicity. ``Toric Intersection Theory for Affine Root Counting,'' Journal of Pure and Applied Algebra, to appear, is now on-line. You can download a DVI version or the Postscript version. This paper also presents some foundational material which is useful for sparse elimination theory in affine space.

A slightly older paper provides part of the framework necessary for the new tricks in the above paper. ``Counting Affine Roots Via Pointed Newton Polytopes'' (with Xiaoshen Wang, Journal of Complexity, vol. 12 (June 1996), pp. 116-133) gives an explicit formula for the average number of complex roots of a particular fundamental class of sparse polynomial systems. Again, the results are stated for arbitrary algebraically closed fields, as opposed to earlier work which focused on the complex numbers. (The on-line version also corrects some typos in the printed version.)

However, my most recent paper deals with the question of counting the exact number of real (or complex) roots, as opposed to getting generically exact upper bounds. A fast algorithm, based on toric resultants, appears in ``Intrinsic Near Quadratic Complexity Bounds for Real Multivariate Root Counting''.

Going further back, ``A Convex Geometric Approach to Counting the Roots of a Polynomial System'' (Theoretical Computer Science, vol. 133 (1), pp. 105-140, October, 1994) gives a combinatorial refinement of Bernshtein's algebraic condition for the exactness of his mixed volume formula. An interesting corollary of this refinement is a complete classification of the sub-n-tuples which preserve the mixed volume of a given n-tuple of polytopes.

It should also be noted that the results of ``A Convex Geometric Approach...'' generalize an earlier paper I wrote with John Canny: ``An Optimal Condition for Determining the Exact Number of Roots of a Polynomial System'' (Proceedings of the International Symposium on Symbolic and Algebraic Computation, July 15--17 (1991), Bonn, Germany).