Advances in Affine Elimination Theory (draft)

J. Maurice Rojas^{1}

May 10, 1995

IRMAR Campus de Beaulieu 35042 Rennes cedex France

                       e-mail:  rojas@univ-rennes1.fr

Keywords: Mixed volume, exact root count, affine, orbit, isolated, upper bound, sparse, polynomial system, resultant, complexity, generic, homotopy, toric variety.

Abstract

Let K be an algebraically closed field of arbitrary characteristic. We consider the problem of computing intersection numbers of complete intersections in certain subsets of K^{n}. In more practical terms, part of our work gives the tightest possible upper bounds on the number of complex isolated roots of a polynomial system, given only which monomial terms appear. Furthermore, we obtain tight upper bounds on the number of isolated roots which can lie in a given coordinate subspace.

Our results refine and unify the classical Bézout theorems and the more recent mixed volume root counts of the Soviet school of Bernshtein, Khovanskii, and Kushnirenko. In particular, the higher dimensional and multihomogeneous Bézout theorems follow as special cases of our results, and the mixed volume root counts receive a definitive generalization to affine space. We also reformulate and extend some of the prior combinatorial results of the author on which subsets of coefficients must be chosen generically for our bounds to be exact.

Our methods are based on viewing the problem of root counting within a certain naturally defined toric variety, as opposed to the traditional view of working within projective space. We also describe the practical impact of our results on recent polyhedral methods for solving polynomial systems. Sparse resultant methods and homotopy methods both benefit from our results, and we propose a new “affine” resultant.

1This research was completed at IRMAR, Rennes and was funded by a Chateaubriand fellowship.