\documentclass[12pt]{amsart} \usepackage{amssymb,latexsym,epic} \headheight=6.15pt \textheight=574pt \textwidth=432pt \oddsidemargin=18.88pt \evensidemargin=18.88pt \topmargin=14.21pt \newlength{\fw} \settowidth{\fw}{{\footnotesize Fulton, William}} \newlength{\jmr} \settowidth{\jmr}{{\footnotesize Rojas, J. Maurice}} \newlength{\bernd} \settowidth{\bernd}{{\footnotesize Sturmfels, Bernd}} \newlength{\ioan} \settowidth{\ioan}{{\footnotesize Emiris, Ioannis Z.}} \newlength{\agk} \settowidth{\agk}{{\footnotesize Khovanskii, Askold G.}} \newlength{\gkz} \settowidth{\gkz}{{\footnotesize Gel'fand, I. M., Kapranov, M. M., and Zelevinsky, A. V.}} \newtheorem{cor}{Corollary} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{propdfn}{Proposition and Definition} \newtheorem{van}{Vanishing Theorem for Resultants} \renewcommand{\thevan}{\unskip} \newtheorem{thm}{Theorem} \newtheorem{rem}{Remark} \newtheorem{ex}{Example} \newtheorem{dfn}{Definition} \renewcommand{\qed}{$\blacksquare$} \newcommand{\relint}{\mathrm{RelInt}} \newcommand{\eps}{\varepsilon} \newcommand{\cA}{\mathcal{A}} \newcommand{\cD}{\mathcal{D}} \newcommand{\cE}{\mathcal{E}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cH}{\mathcal{H}} \newcommand{\cJ}{\mathcal{J}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cN}{\mathcal{N}} \newcommand{\cO}{\mathcal{O}} \newcommand{\cR}{\mathcal{R}} \newcommand{\cI}{\mathcal{I}} \newcommand{\cP}{\mathcal{P}} \newcommand{\cV}{\mathcal{V}} \newcommand{\cX}{\mathcal{X}} \newcommand{\supp}{\mathrm{Supp}} \newcommand{\conv}{\mathrm{Conv}} \newcommand{\affine}{\mathrm{Aff}} \newcommand{\init}{\mathrm{in}} \newcommand{\ev}{\mathrm{even}} \newcommand{\odd}{\mathrm{odd}} \newcommand{\thth}{{\underline{\mathrm{th}}}} \newcommand{\st}{{\underline{\mathrm{st}}}} \newcommand{\nd}{{\underline{\mathrm{nd}}}} \newcommand{\Pro}{\mathbb{P}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\bp}{\mathbf{\pi}} \newcommand{\gcp}{\cG\cC\cP} \newcommand{\ch}{\mathrm{char}} \newcommand{\Le}{\mathrm{Length}} \newcommand{\ord}{\mathrm{ord}} \newcommand{\area}{\mathrm{Area}} \newcommand{\spec}{\mathrm{Spec}} \newcommand{\divisor}{\mathrm{Div}} \newcommand{\codim}{\mathrm{codim}} \newcommand{\chow}{\mathrm{Chow}} \newcommand{\fan}{\mathrm{Fan}} \newcommand{\verte}{\mathrm{Vert}} \newcommand{\cone}{\mathrm{Cone}} \newcommand{\res}{\mathrm{Res}} \newcommand{\newt}{\mathrm{Newt}} \newcommand{\hyp}{\mathrm{Hyper}} \newcommand{\hilb}{\mathrm{\mathbf{Hilb}}} \newcommand{\Sn}{\mathcal{S}^{n-1}} \newcommand{\Zn}{\Z^n} \newcommand{\Zno}{\Z^n\!\setminus\!\{\bO\}} \newcommand{\Qn}{\Q^n} \newcommand{\Rn}{\R^n} \newcommand{\gln}{\G\bL_n} \newcommand{\glnz}{\gln(\Z)} \newcommand{\Cn}{\C^n} \newcommand{\Cs}{\C^*} \newcommand{\Rs}{\R^*} \newcommand{\Ks}{K^*} \newcommand{\Kn}{K^n} \newcommand{\Kni}{\Kn\!\setminus\!\hyp(I)} \newcommand{\Knj}{\Kn\!\setminus\!\hyp(\bar{J})} \newcommand{\Cni}{\Cn\!\setminus\!\hyp(I)} \newcommand{\Qns}{\Qn\!\setminus\!\{\bO\}} \newcommand{\Rsn}{{(\R^*)}^n} \newcommand{\Rns}{\Rn\!\setminus\!\{\bO\}} \newcommand{\Csn}{{(\C^*)}^n} \newcommand{\Ksn}{{(K^*)}^n} \newcommand{\Krn}{(K^*)^r \! \times \! K^{n-r}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cM}{\mathcal{M}} \newcommand{\cS}{\mathcal{S}} \newcommand{\cSM}{\cS\cM} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cF}{\mathcal{F}} \newcommand{\tF}{\widetilde{F}} \newcommand{\cT}{\mathcal{T}} \newcommand{\bO}{\mathbf{O}} \begin{document} \title[Some New Applications of Toric Geometry]{Some New Applications of Toric Geometry} \author{J. Maurice Rojas} \thanks{This research was partially funded by N.S.F. grant DMS-9022140 and an N.S.F. Mathematical Sciences Postdoctoral Fellowship.} \address{\hskip-\parindent Massachusetts Institute of Technology\\ Mathematics Department\\ 77 Mass. Ave.\\ Cambridge, MA \ 02139, U.S.A. } \date{\today} \thanks{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. } \begin{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. \end{abstract} \maketitle \section{Introduction} \label{sec:intro} 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 \cite{lazard,kaplak,pardokrick,fast} and the references therein.) However, there are difficulties with this method which {\em still}\/ have not been completely addressed. Three such problems are the following: \begin{itemize} \item[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.} \item[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.} \item[C:]{Univariate reduction is still too slow for many problems of interest.} \end{itemize} We circumvent A by the technique of {\em toric laminations}. By constructing a generalization of Canny's {\em generalized characteristic polynomial}\/ (GCP) \cite{gcp,mikebezout} --- the {\em toric}\/ (or {\em 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 \cite{renegar, gcp}, the toric GCP greatly improves the complexity bounds given there. In particular, we address problem C by using the {\em sparse resultant}\/ \cite{gkz90,isawres} throughout our development. Fast methods for polynomial system solving were derived via the {\em sparse $u$-resultant}\/ in \cite{emiphd,isawres} 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 {\em toric varieties}\/ \cite{kkms,tfulton,grobandpoly}. One advantage of a toric variety setting is reducing the problem of {\em exact}\/ root counting for polynomial systems, almost completely, to convex geometry. Generically sharp {\em upper bounds}\/ on the number of (complex) isolated roots, in terms of mixed volume, first appeared just over two decades ago \cite{kus75}. These bounds have since been generalized to algebraically closed fields \cite{dannie,toricint} and to various subsets of affine space (other than the algebraic torus) \cite{kho78,hsaff,toricint}. 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$.) \begin{thm} Let $F(x_1,\ldots,x_n)$ be an $n\!\times\!n$ polynomial system with support $E\!:=\!(E_1,\ldots,E_n)$ such that $\cM(E)\!>\!0$. Also let $P_E$ be the sum of the convex hulls of the $E_i$, and pick $a\!\in\!\Zno$ such that the segment $[\bO,a]$ is not parallel to any facet of $P_E$. Define $\bp_a(u_+,u_-)\!:=\!\res_{E_a}(F,u_+ +u_-x^a)$ where $\{u_\pm\}$ is a pair of algebraically independent indeterminates and $E_a\!:=\!(E,\{\bO,a\})$. Finally, let $\eps_\pm$ be the lowest exponent of $u_\pm$ occurring in any monomial of $\bp_a$. Then $F$ has {\em exactly} $\cN\!:=\!\cM(E)-\eps_+ -\eps_-$ isolated roots (counting multiplicities) in $\Ksn$, provided $\cN\!<\!\infty$. \end{thm} \noindent In the above, $\res_{\star}(\cdot)$ and $\cM(\cdot)$ respectively denote the sparse resultant and mixed volume \cite{isawres,mvcomplex,toricint}. 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 {\em toric}\/ infinity when doing univariate reduction. We may also calculate the number of {\em distinct}\/ roots in a similar way. \begin{cor} Following the notation and assumptions of theorem 1, let $\bp'_a(u_+,u_-)$ be the square-free part of $\bp_a(u_+,u_-)$. Also let $\eps'_\pm$ be the lowest exponent of $u_\pm$ occuring in $\bp'_a$. Then $F$ has {\em exactly} $\cN'\!:=\!\deg(\bp'_a)-\eps'_+-\eps'_-$ roots in $\Ksn$, provided $\cN'\!<\!\infty$ {\em and} the projection of roots $\{\zeta\!\in\!\Ksn \; | \; F(\zeta)\!=\!0\}\longrightarrow\{\zeta^a\}$ is injective. \end{cor} \noindent This corollary is proved alongside theorem 1 in section \ref{sec:chowtor}. By instead calculating a particular {\em coefficient}\/ of $\bp_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., \cite{zip}, are making this approach increasingly feasible. So let us at least give explicit formulae for the coefficients of $\bp_a$ in terms of multisymmetric functions. \begin{dfn} For any $w\!\in\!\Rns$, let $E^w_i$ be the set of points of $E_i$ having {\em minimal} inner product with $w$. Also, let $E^w\!:=\!(E^w_1,\ldots,E^w_n)$ and, when $w\!\in\!\Qns$, let $p_w\!\in\!\Zn$ be the first lattice point not equal to the origin encountered along the ray generated by $w$. Finally, let $L(E,a)$, the {\em ambiguity locus}, be the subvariety of $\cT_{P_E}\!\setminus\!\Ksn$ corresponding to the union of all faces of $P_E$ having an inner normal perpendicular to the segment $[\bO,a]$. \end{dfn} \begin{rem} The toric variety (over $K$), $\cT_P$, corresponding to a polytope $P$ is detailed in \cite{ksz92,tfulton,gkz94,grobandpoly,toricint}. Polynomial roots in a toric compactification are described (in a manner closest to our present framework) in \cite{toricint}. \end{rem} \begin{cor} \label{cor:multi} Following the notation of theorem 1, assume instead that $a$ is {\em any} point in $\Zno$ and $\eps_+,\eps_-\!<\!\infty$. Then $\bp_a$ is a homogeneous polynomial of degree $\cM(E)$ and, for any $d\!\in\!\{0,\ldots,\cM(E)-\eps_+-\eps_-\}$, the coefficient of $u^{d+\eps_-}_-u^{\cM(E)-d-\eps_+}_+$ in $\bp_a$ is precisely \[C \sum \prod\limits^d_{j=1} \zeta(j)^a, \] where $C\!\in\!\Ks$ is independent of $d$, the sum ranges over all cardinality $d$ multisets $\{\zeta(1),\ldots,\zeta(d)\}\!\subseteq\!Z_F$, and $Z_F$ is the multiset of roots of $F$ in $\Ksn\cup L(E,a)$. Furthermore, if $\eps_+\!=\!\eps_-\!=\!0$ then $C$ is precisely \[ (-1)^n\left(\prod\limits_w \res_{E^w}(F)^{-p_w\cdot a}\right), \] where the product ranges over all inner facet directions of $P_E$ having negative inner product with $a$. \qed \end{cor} \noindent Multisets are simply sets where repeated elements are allowed, and whose subsets have repetitions appropriately restricted \cite{gkp}. 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 $\bp_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 \cite{chowprod}.\footnote{We also need the fact that the Pedersen-Sturmfels formula, originally stated only over $\C$, remains true over a general algebraically closed field. This is proved in \cite{resvan}.} Moreover, since the sparse resultant is invariant under muliplication of the individual polynomials by a monomial, we can compare the coefficients of $\bp_a$ and $\bp_{-a}$ to obtain the following beautiful identity.\footnote{ Alicia Dickenstein pointed out the $K\!=\!\C$ 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 \ref{cor:multi}.} \begin{cor} Following the notation and assumptions of corollary \ref{cor:multi}, $\eps_+\!=\!\eps_-\!=\!0 \Longrightarrow$ \[ \prod\limits_{\zeta\in Z_F} (\zeta^a)= \prod\limits_w \res_{E^w}(F)^{p_w\cdot a} \] where the product ranges over {\em all} inner facet directions of $P_E$. \qed \end{cor} Recall that a {\em ridge}\/ is a polytope face of codimension $2$ \cite{ziegler}. Although the ``bad'' case of theorem 1 ($\cN\!=\!\infty$) is an annoyance, it is a small annoyance and can actually be made use of in certain cases. \begin{thm} \label{thm:ambi} Following the notation and assumptions of theorem 1, $\cN\!=\!\infty \Longleftrightarrow F$ has a root lying in $L(E,a)$ {\em or} infinitely many roots in $\Ksn$. Also, within the space of all systems with support contained in $E$, the $F$ with $\cN\!=\!\infty$ form a subvariety of codimension $\geq\!2$. \end{thm} \noindent Thus, if the roots of $F$ avoid the ambiguity locus, $F$ has infinitely many roots in $\Ksn \Longleftrightarrow \cN\!=\!\infty$. In particular, it follows directly from the definition of $L(E,a)$ that $\codim L(E,a)\!=\!2$, under the assumptions of theorem \ref{thm:ambi}. (Since $L(E,a)$ then corresponds to a finite set of ridges \cite{tfulton, toricint}.) 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 \cite{tgcp} and, to a certain extent, in the result we quote below. However it is worth noting that the roots of $F$ {\em always}\/ avoid $L(E,a)$ when $n\!<\!3$ and $E$ is the support of $F$ (cf.\ lemma \ref{lemma:once}). \begin{rem} 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 \ref{sec:ex}). Thus it is worthwhile to know something about $L(E,a)$. \end{rem} \begin{rem} \label{rem:egg} A correspondence useful for visualizing theorems 1 and 2 is to identify toric infinity ($\cT_P\!\setminus\!\Ksn$) with the boundary of the polytope $P$ (cf.\ definition \ref{dfn:toric}). Computing $\bp_a$ then amounts to splitting $\partial P_E$ into two signed halves, much like cracking an egg-shell. In particular, the half with sign $\pm$ consists precisely of those faces of $P_E$ having an inner normal with $\pm$ inner product with $a$. The ambiguity locus is then precisely the common boundary of these two halves. We will see later that $\bp_a$ can be viewed as a coordinatization of a particular rational map $\cT_{P_E} \dashrightarrow \Pro^1_K$. Thus, provided no roots lie in the ambiguity locus, $\eps_{\pm}$ is the sum of the intersection numbers of the roots of $F$ which lie in the $\pm$ half. \end{rem} A general way to deal with the existence of {\em infinitely}\/ many roots of $F$ within a given toric compactification is the following result announced below. \begin{thm} \cite{tgcp} Following the notation of theorem 1, suppose $g(x)\!:=\!\sum_{e\in A} u_e x^e$ where the $u_e$ are algebraically independent indeterminates and $A\!\subset\!\Zn$ is nonempty and finite. Suppose further that $\cP\!:=\!(P_1,\ldots,P_n)$ is an $n$-tuple of integral polytopes in $\Rn$ containing the support of $F$, and let $D$ be an irreducible fill of $\cP$. Setting $F^*\!:=\!(\sum_{e\in D_i} x^e \; | \; i\!\in\![1..n])$, define $\cH(s;u)\!:=\!\res_{(E,A)}(F-sF^*,g)$, where $s$ is a new indeterminate. Finally, considering $\cH$ as a polynomial in $s$ with coefficients in $K[u]$, let $\cF_A(u)$ be the coefficient of the lowest power term of $\cH$. Then $\cF_A$ is a homogeneous polynomial with the following properties: \begin{enumerate} \item{$\cF_A$ is divisible by $g(\zeta)$, for any root $\zeta\!\in\!\Ksn$ of $F$.} \item{If $\cP$ is compatible with $\conv(A)$, then $\cF_A$ has degree $\cM(\cP)$ and to every irreducible factor of $\cF_A$ there naturally corresponds a root of $F$ in $\cT_P$, where $P\!:=\!\sum P_i$.} \end{enumerate} We call $\cH$ a {\em toric} (or {\em sparse}) {\em generalized characteristic polynomial for $(F,A)$.} \qed \end{thm} The combinatorial portion of the above theorem can be explained as follows: We say that $D$ {\em fills}\/ $\cP$ iff $D\!:=\!(D_1,\ldots,D_n)$ satisfies $D_i\!\subseteq\!P_i$ for all $i\!\in\![1..n]$ and $\cM(D)\!=\!\cM(\cP)$ \cite{convexapp,rojaswang}. An {\em 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 \ref{sec:chowtor} and the toric GCP is briefly compared to the original GCP in section \ref{sec:toricgcp}. Combined with the toric variety version of Bernshtein's theorem \cite{toricint}, we see that the above theorem gives us a resultant-based 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 $\cF_A$ which do {\em 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 \ref{sec:ex}. Our results are also very useful for root counting over $\R$, $\Q$, and even $\Z$. For example, one can combine standard univariate techniques such as Sturm sequences \cite{glrr,marie1} with our preceding results to quickly count the number of real roots \cite{nash}. Better still, we can go to an even smaller ring: In section \ref{sec:hilbert} we will give a short proof (under some mild hypotheses) of the following refinement of Hilbert's Tenth Problem \cite{maty}. \begin{thm} \cite{resvan} \label{thm:hilbert} Consider, for any nonnegative integer $d$, the following collection of Diophantine systems:\\ {${\bf \hilb(d)}${\bf :}} Multivariate polynomial systems with integer coefficients and $d$-dimensional {\bf 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. \qed \end{thm} 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 \[(\star) \ \ \ \ \ \ \ \ \ (F,f_{n+1}) \mathrm{\ has \ a \ root \ in \ } \Ksn \Longrightarrow \res_{\bar{E}}(F,f_{n+1})\!=\!0\] (provided $\bar{E}\!=\!(E,E_{n+1})$ and $f_{n+1}$ is a polynomial over $K$ with support contained in $E_{n+1}\!\subset\!\Zn$). However, the converse assertion is \underline{{\bf not}}\/ always true. (The polynomial system $(x+y+1,x+y+2,x+y+3)$ with $\bar{E}\!=\!\{\bO,\hat{e}_1,\hat{e}_2\}^3$ gives a simple counter-example reducing to the vanishing of a $3\times 3$ determinant.) The correct statement in which {\em both}\/ implications hold seems to be known only folklorically, while the {\em unmixed}\/ case $E_1\!=\!\cdots\!=\!E_{n+1}\!=\!\cA$ (over $\C$) is contained in various recent works, e.g., \cite{ksz92,gkz94}. So we will make use of the following more general result. \begin{van} \cite{resvan} Suppose $f_i$ is a polynomial over $K$ with support {\em contained in}\/ $E_i\!\subset\!\Zn$ for all $i\!\in\![1..n+1]$. Then, provided \[\cM(E_1,\ldots,\widehat{E_i},\ldots,E_{n+1})>0\] for some $i\!\in\![1..n]$, \[\res_{\bar{E}}(f_1,\ldots,f_{n+1})\!=\!0 \Longleftrightarrow \bigcap\limits^{n+1}_{i=1} \cD_{P_{\bar{E}}}(f_i,\conv(E_i))\!\neq\! \emptyset,\] where $\bar{E}\!:=\!(E_1,\ldots,E_{n+1})$ and $P_{\bar{E}}\!:=\!\sum\limits^{n+1}_{i=1} \conv(E_i)$. \qed \end{van} \noindent In the above, $\cD_P(f_i,P_i)$ is the {\em toric effective divisor}\/ of $\cT_P$ corresponding to $(f_i,P_i)$ (cf.\ definition \ref{dfn:toric}). This result provides a geometric analogue, over a {\em general}\/ algebraically closed field, of the product formula for the sparse resultant \cite{chowprod}. 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 $\Ksn$. Although one could in principle reduce to various coordinate subspaces to perform ``sparse'' elimination theory in $\Kn$, such an approach runs into complications with intersection multiplicities on the coordinate hyperplanes and is really {\em not}\/ intrinsic to $\Kn$. We propose a more intrinsic (and efficient) approach to {\em affine elimination theory}\/ by defining a new resultant operator --- the {\em affine}\/ sparse resultant --- in \cite{aff}. Following this route, {\em 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 \cite{toricint,aff} and the complexity bound of theorem \ref{thm:hilbert} is further refined in the latter work. \section{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 \cite{isawres}. 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 \cite{gcp} that Gr\"obner 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 \cite{sparseelim}. (We also point out that \cite{sparseelim} 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. \cite{pardokrick,fast}. Our results fill in some toric geometry missing from their more algebraic framework. In particular, we propose that toric laminations, i.e., ``fibering'' $\cT_{P_E}$ by {\em toric}\/ projections (instead of fibering $\Ksn$ 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 \cite{resvan}. \section{Examples} % A lot of 19th century stuff has been (shamefully) forgotten... \label{sec:ex} We will give a $2\times 2$ example of our first two theorems. \subsection{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 $\{\bO,(3,0),(0,4)\}$ and $\{\bO,(4,0),(0,5)\}$. Clearly then the Newton polygons are two triangles and the segment $[\bO,(1,1)]$ is not parallel to any edge of the quadrilateral $P_E\!:=\!\conv(\bO,(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,\{\bO,(1,1)\})$ and the coefficients of $F$ have been replaced by algebraically independent indeterminates.\footnote{The 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.} To do this, we can use {\tt Maple} to calculate the Sylvester ($2\times 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 {\em 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 ($\star$) from the introduction \cite{sparseelim,resvan}.) The preceding computations, modulo typing, takes only fractions of a second on a Sun 4m Computeserver. From \cite{combiresult} we know that the sparse resultant itself should have degree $\cM(E_1,E_2)+\cM(E_1,\{\bO,a\})+ \cM(E_2,\{\bO,a\})\!=\!16+7+9\!=\!32$. (This calculation is easily done by hand via the general formula $\cM(E_1,E_2)\!=\!\area(\conv(E_1+E_2))- \area(\conv(E_1)) -\area(\conv(E_2))$ \cite{schneider,mvcomplex}.) So by factoring with {\tt Maple} (which takes just under $2$ seconds) we can isolate the sparse resultant and specialize coefficients to obtain \[ \bp_{(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}_+ \] \noindent So $\eps_+\!=\!7$, $\eps_-\!=0$, and theorem 1 tells us that $F$ has exactly $16-7\!=\!9$ roots, counting multiplicities, in $(\Cs)^2$. Furthermore, a one-line {\tt Maple} calculation shows that $\bp_{(1,1)}$ is irreducible over $\Q$. So corollary 1 (and basic Galois theory) tells us that the multiplicity of every root of $F$ in $(\Cs)^2$ is $1$. The roots of $F$ can also be counted via Gr\"obner 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 $\cT_{P_E}$ and corresponds precisely to the two lower-left edges of $P_E$ (cf.\ remark \ref{rem:egg} and definition \ref{dfn:toric}). Furthermore, the ambiguity locus consists of two distinct points which, due to the fact that $\bp_a$ is not identically $0$ (cf.\ theorem 2), the roots of $F$ have luckily avoided. Also $\eps_+\!=\!7 \Longrightarrow 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. %\subsection{Ambiguity Loci and Excess Components} %\label{sub:eg} %!!! ...cute linear examples... %... %\subsection{Excess Intersection Multiplicity via the Toric GCP} % ...my cool example...try elliptic curves?... \section{A Refinement of Hilbert's Tenth Problem} \label{sec:hilbert} We will present a concise proof of theorem 4 under the following three hypotheses: \begin{enumerate} \item{The instances of $\hilb(0)$ considered are $n\times n$ polynomial systems.} \item{The complex roots of an instance must have all coordinates nonzero.} \item{No instance can have a complex root at toric infinity.} \end{enumerate} 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., \cite[Main Theorem 2]{toricint}. The above hypotheses are present mainly for technical reasons and are removed in \cite{resvan}. They may also be removed with other recent techniques \cite{bpr,pardokrick,fast}, but through our toric techniques it is possible to obtain a general complexity bound with near {\em quadratic}\/ dependence on the mixed volume \cite{tgcp}. This would be the best asymptotic bound to date for solving Diophantine systems. \noindent {\bf Proof of Theorem 4:} First we outline our algorithm: \begin{itemize} \item[Step 1:]{Following the notation of theorem 3, let $A$ be the vertices of a standard $n$-simplex in $\Rn$ and $\cP$ the $n$-tuple of Newton polytopes of $F$. Form the polynomial $\cF_A$.} \item[Step 2:]{Using the Lenstra-Lenstra-Lovasz algorithm \cite{lll}, factor $\cF_A$ over $\Z$.} \item[Step 3:]{Any integral root $(z_1,\ldots,z_n)\!\in\!\Zn$ of $F$ corresponds precisely to an integral factor of $\cF_A$ of the form $u_\bO+z_1u_{\hat{e}_1}+\cdots+z_nu_{\hat{e}_n}$. } \end{itemize} Step 1 runs in time polynomial in the mixed volume, applying hypotheses (1) and (3), and the results of \cite{sparseelim,cxelim}. 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 \cite{resvan}. One also needs the fact that hypotheses (1) and (3) together imply that the complex zero set of $F$ in $\Ksn$ is zero-dimensional, but this is an immediate consequence of \cite[Corollary 3]{toricint}. We also point out that working more generally in terms of $\cF_A$ aids in later removing hypothesis (3) \cite{resvan}. 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 \cite{resvan}, and part (b) follows easily from the univariate case covered in \cite{lll}. That we can terminate as described in Step 3 follows immediately from hypothesis (2) and the Vanishing Theorem for Resultants. % Bound? \qed 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 $\bigcup^\infty_{d=0} \hilb(d)$ seems to be new. (In particular, Hilbert's Tenth Problem was originally stated as deciding the existence of a {\em single}\/ integral root for {\em one}\/ polynomial in several variables.) Although the results of \cite{jones} imply that $\hilb(8)$ is undecidable, nothing seems to be known about $\hilb(d)$ for $0\!0$ (resp.\ $w\cdot a\!<\!0$). More to the point, if $c\!\in\!\Ks$ then it follows similarly that $u_++cu_-$ divides $\bp_a$ iff some root of $F$ lies in the closure of the hypersurface $\{x^a\!=\!c\}$ in $\cT_{P_E}$. Furthermore, lemma 1 immediately implies that any two (distinct) hypersurfaces of this form must intersect precisely on the ambiguity locus. Thus $\bp_a$ can not be identically $0$ and we obtain that $\cN$ 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\}$, $\bp_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 $\cN\!=\!\infty$. Similarly, the existence of infinitely many roots of $F$ within $\Ksn$ implies that $\cN\!=\!\infty$ as well. Thus we are done with the first portion of the theorem. As for the codimension of the space of ``degenerate'' $F$ being $\geq\!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 \Longleftrightarrow$ the initial term system $\init_w(F)$ has a root in $\Ksn$ \cite[corollary 2]{toricint}. By the definition of $L(E,a)$, we can then conclude via theorem 1.3 of \cite{combiresult}. (Although the results of \cite{combiresult} are stated over the complex numbers, this is only a minor technicality: in this case, the results of \cite{toricint} immediately imply that we can apply theorem 1.3 over {\em any}\/ algebraically closed field.) As for the $F$ with infinitely many roots in $\Ksn$, assume temporarily that the coefficients of $F$ are algebraically independent indeterminates. That the $F$ with infinitely many roots in $\Ksn$ define a subvariety of codimension $\geq\!2$ must certainly be an old result. However, for completeness, we will give a quick proof: Following the notation of lemma \ref{lemma:forbid}, Hilbert's Irreducibility Theorem \cite{lang} readily implies that we can choose $\alpha,\beta,\gamma,\delta\!\in\!\Ks$ such that the polynomials $p(\alpha,\beta)$ and $p(\gamma,\delta)$ are relatively prime in $K[\cC_E]$. So, by lemma \ref{lemma:forbid}, these $F$ are indeed contained in a codimension $2$ subvariety: $\{ \cC_E \; | \; p(\alpha,\beta)\!=\!q(\gamma,\delta)\!=\!0 \}.$ \qed So in summary, computing $\bp_a$ amounts to laminating $\cT_{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 \ref{rem:egg}) the $\pm$ halves of $\partial P_E$. \noindent {\bf Proof of Theorem 1 and Corollary 1:} We need only state the preceding paragraph more algebraically. In particular, lemma \ref{lemma:chow} has already done this for us. We thus obtain that when $\cN\!<\!\infty$, the multiplicity of a factor $c_+u_++c_-u_-$ of $\bp_a$ is precisely the sum of the intersection numbers of the components of $\cD_{P_E}(F,\cP_E)$ lying in the fiber $\bar{\varphi}^{-1}([c_-:c_+])$. So $\cN$ (resp.\ $\cN'$) is indeed the exact number of roots, counting multiplicities (resp.\ {\em not}\/ counting multiplicities), of $F$ in $\Ksn$. \qed Note that it is actually possible for a positive-dimensional component of $\cD_{P_E}(F,\cP_E)$ lying at toric infinity to make a positive (finite) contribution to $\cN$ (or $\cN'$). This can be interpreted as an alternative way of associating an intersection number to an excess component \cite{ifulton}. %\noindent %{\bf Proof of Corollary 2:} Easy from lemma \ref{lemma:chow} and %the preceding proofs !!! %\section{Proofs of Our Lemmata} %\label{sec:lemma} %!!! \section{Toric Generalized Characteristic Polynomials} \label{sec:toricgcp} We will first comment briefly on the combinatorial preprocessing step. The following example illustrates a simple fundamental case. \setcounter{ex}{2} \begin{ex}[The ``Dense'' Case] Suppose $\cP$ is the $n$-tuple $(d_1\Delta,\ldots,d_n\Delta)$ where $\Delta\!\subset\!\Rn$ is the standard $n$-simplex and $d_i\!\in\!\N$ for all $i$. It is then easily verified that the $n$-tuple $D\!:=\!(\{\bO,d_1\hat{e}_1\},\ldots,\{\bO,d_n\hat{e}_n\})$ is an irreducible fill of $\cP$ \cite{convexapp,schneider}. Letting $A$ be the vertices of $\Delta$, theorem 3 then implies that $\cH$ is a variant (over a general algebraically closed field) of the original GCP applied to an $n\!\times\!n$ system of equations with degrees $d_1,\ldots,d_n$ \cite{gcp}. In particular, our $F-sF^*$ has $2n$ $s$-monomials, compared to $n$ $s$-monomials in Canny's $(f_1-sx^{d_1}_1,\ldots,f_n-sx^{d_n}_n)$. Note also that $\conv(A)$ and $P$ are homothetic and $\cT_P\!\cong\!\Pro^n_K$. 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. \end{ex} 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 {\em 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 $\cF_A$. For example, the following lemma implies that $F^*$ is sufficiently generic in a useful sense. \begin{lemma} Following the notation and assumptions of theorem 3, for any point $v$ lying in any $D_i$, there exists a $w\!\in\!\Rns$ such that $\{i\}$ is the unique essential subset of $D^w$ and $D^w_i\!=\!\{v\}$. In particular, $F^*$ has exactly $\cM(\cP)$ roots (counting multiplicities) in $\Ksn$. \qed \end{lemma} \noindent This lemma follows easily from the techniques of \cite{convexapp}, particularly section 2.5. Given that $F^*$ thus has maximally many isolated roots (counting multiplicities) and {\em no}\/ excess components in $\Ksn$, theorem 3 then follows easily from the Vanishing Theorem for Resultants and an algebraic homotopy argument. A similar homotopy technique appears in \cite{rojaswang, toricint}, and the dense case (with $K\!=\!\C$) is covered in \cite{gcp,mikebezout}. (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 $\cT_P$ is complex projective space. In closing, an important difference to note is that our present toric GCP is primarily suited for $\Ksn$, while the original GCP is mainly suited (in a non-sparse way) for affine space. To {\em completely}\/ generalize and improve the GCP in affine space, it is necessary to use the {\em affine}\/ sparse resultant and this is pursued further in \cite{aff}. For instance, by replacing the sparse resultant with the affine sparse resultant, and using {\em $\Kn$-counting}\/ \cite{toricint} instead of filling, we can actually recover Canny's GCP in the dense case. \section{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. \bibliographystyle{amsalpha} \begin{thebibliography}{A} \bibitem[BPR94]{bpr} Basu, S., Pollack, R., and Roy, M.-F., {\it ``On the Combinatorial and Algebraic Complexity of Quantifier Elimination,''} in Proc. IEEE Symp. Foundations of Comp. Sci., Santa Fe, New Mexico, 1994, to appear. \bibitem[Can90]{gcp} Canny, John F., {\it ``Generalised Characteristic Polynomials,''} J. Symbolic Computation (1990) 9, pp.\ 241--250. \bibitem[CS86]{arithgeom} Cornell, Gary and Silverman, Joseph H., {\it Arithmetic Geometry,} with contributions by M.\ Artin, et.\ al., Springer-Verlag, 1986. \bibitem[Dan78]{dannie} Danilov, V. I., {\it ``The Geometry of Toric Varieties,"} Russian Mathematical Surveys, 33 (2), pp.\ 97--154, 1978. \bibitem[DGH96]{mvcomplex} Dyer, M., Gritzmann, P., and Hufnagel, A., {\it ``On the Complexity of Computing Mixed Volumes,"} SIAM J. Comput., to appear (1996). \bibitem[DS95]{introchow} Dalbec, John, and Sturmfels, Bernd, {\it ``Introduction to Chow Forms,"} Invariant Methods in Discrete and Computational Geometry (Cura\c{c}ao, 1994), pp.\ 37--58, Kluwer Academic Publishers, Dordrecht, 1995. \bibitem[EC95]{isawres} Emiris, Ioannis Z. and Canny, John F., {\it ``Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume,''} Journal of Symbolic Computation, vol.\ 20 (1995), pp.\ 117--149. \bibitem[Emi94]{emiphd} Emiris, Ioannis Z., {\it ``Sparse Elimination and Applications in Kinematics,''} Ph.D. dissertation, Computer Science Division, U. C. Berkeley (December, 1994), available on-line at {\tt http://www.inria.fr/safir/SAFIR/Ioannis.html} \bibitem[Emi96]{cxelim} \underline{\hspace{\ioan}},~{\it ``On~the~Complexity~of~ Sparse~Elimination,''}~preprint, \mbox{INRIA},~March~1996,~available~ \hbox{on-line}~at~{\tt http://www.inria.fr/safir/SAFIR/Ioannis.html} \bibitem[Ful84]{ifulton} Fulton, William, {\it Intersection Theory,} Springer-Verlag, 1984. \bibitem[Ful93]{tfulton} \underline{\hspace{\fw}}, {\it Introduction to Toric Varieties}, Annals of Mathematics Studies, no.\ 131, Princeton University Press, Princeton, New Jersey, 1993. \bibitem[GHMP95]{fast} Giusti, M., Heintz, J., Morais, J. E., Pardo, L. M., {\it ``When Polynomial Systems Can Be `Solved' Fast?,'' } Proc. 11$^\thth$ 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. \bibitem[GKP94]{gkp} Graham, R. L., Knuth, D. E., and Patashnik, O., {\it Concrete Mathematics: A Foundation for Computer Science}, 2$^\nd$ edition, Addison-Wesley, 1994. \bibitem[GKZ90]{gkz90} Gel'fand, I. M., Kapranov, M. M., and Zelevinsky, A. V., {\it ``Discriminants of Polynomials in Several Variables and Triangulations of Newton Polytopes,"} Algebra and Analysis (translated from Russian) 2, pp.\ 1--62, 1990. \bibitem[GKZ94]{gkz94} \underline{\hspace{\gkz}}, {\it Discriminants, Resultants and Multidimensional Determinants,} Birkh\"auser, Boston, 1994. \bibitem[GLRR94]{glrr} Gonzalez, L., Lombardi, H., Recio, T., Roy, M.-F., {\it ``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. \bibitem[HS96]{hsaff} Huber, Birkett and Sturmfels, Bernd, {\it ``Bernshtein's Theorem in Affine Space,"} Discrete and Computational Geometry, to appear, 1996. \bibitem[Jon82]{jones} Jones, James P., {\it ``Universal Diophantine Equation,"} Journal of Symbolic Logic, 47 (3):549--571. \bibitem[Kho77]{khocompat} Khovanskii, A. G., {\it ``Newton Polyhedra and Toroidal Varieties,"} Functional Anal. Appl., 11 (1977), pp.\ 289--296. \bibitem[Kho78]{kho78} \underline{\hspace{\agk}}, {\it ``Newton Polyhedra and the Genus of Complete Intersections,"} Functional Analysis (translated from Russian), Vol. 12, No. 1, January--March (1978), pp.\ 51--61. \bibitem[KL92]{kaplak} Kapur, Deepak and Lakshman, Yagati N., {\it ``Elimination Methods: an Introduction,''} Symbolic and Numerical Computation for Artificial Intelligence, B. Donald et.\ al.\ (eds.), Academic Press, 1992. \bibitem[KKMS73]{kkms} Kempf, G., Knudsen, F., Mumford, D., Saint-Donat, B., {\it Toroidal Embeddings I}, Lecture Notes in Mathematics 339, Springer-Verlag, 1973. \bibitem[KSZ92]{ksz92} Kapranov, M. M., Sturmfels, B., and Zelevinsky, A. V., {\it ``Chow Polytopes and General Resultants,''} Duke Mathematical Journal, Vol. 67, No. 1, July, 1992, pp.\ 189--218. \bibitem[Kus75]{kus75} Kushnirenko, A. G., {\it ``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). \bibitem[Lan83]{lang} Lang, Serge, {\it Fundamentals of Diophantine Geometry,} Springer-Verlag, 1983. \bibitem[Laz81]{lazard} Lazard, D. {\it ``R\'esolution des Syst\`emes d'\'equations Alg\'ebriques,''} Theor. Comp. Sci. 15, pp.\ 146--156. \bibitem[LLL82]{lll} Lenstra, A. K., Lenstra, H. W., and Lov\'asz, L. {\it ``Factoring Polynomials with Rational Coefficients,''} Math. Ann. {\bf 261} (1982), pp.\ 515-534. \bibitem[Mat93]{maty} Matiyasevich, Yuri V., {\it Hilbert's Tenth Problem,} MIT Press, MIT, Cambridge, Massachusetts, 1993. \bibitem[PK95]{pardokrick} Pardo-Vasallo, Luis-Miguel and Krick, Teresa, {\it ``A Computational Method for Diophantine Approximation,''} to appear in Proc. MEGA '94, Birkh\"auser, Progress in Math. (1995). \bibitem[PS93]{chowprod} Pedersen, P. and Sturmfels, B., {\it ``Product Formulas for Sparse Resultants and Chow Forms,"} Mathematische Zeitschrift, 214: 377--396, 1993. \bibitem[Ren87]{renegar} Renegar, Jim, {\it ``On the Worst Case Arithmetic Complexity of Approximating Zeros of Systems of Polynomials,''} Technical Report, School of Operations Research and Industrial Engineering, Cornell University. \bibitem[Roj94]{convexapp} Rojas, J. Maurice, {\it ``A Convex Geometric Approach to Counting the Roots of a Polynomial System,"} Theoretical Computer Science (1994), vol.\ 133 (1), pp.\ 105--140. \bibitem[Roj97a]{toricint} \underline{\hspace{\jmr}}, {\it ``Toric Intersection Theory for Affine Root Counting,''} Journal of Pure and Applied Algebra, to appear. (Also available on-line at {\tt http://www-math.mit.edu/\~{}rojas} .) \bibitem[Roj97b]{nash} \underline{\hspace{\jmr}}, {\it ``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. \bibitem[Roj97c]{tgcp} \underline{\hspace{\jmr}}, {\it ``Toric Generalized Characteristic Polyomials,''} submitted to the Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation. (Also available on-line at {\tt http://www-math.mit.edu/\~{}rojas}.) \bibitem[Roj97d]{resvan} \underline{\hspace{\jmr}}, {\it ``When do Resultants Really Vanish? Applications to Diophantine Complexity,''} preprint, MIT (1997). \bibitem[Roj97e]{aff} \underline{\hspace{\jmr}}, {\it ``Affine Elimination Theory and Solving Certain Diophantine Systems Quickly,''} preprint, MIT (1997). \bibitem[Roy95]{marie1} Roy, Marie-Fran\c{c}oise {\it ``Basic Algorithms in Real Algebraic Geometry and their Complexity: from Sturm Theorem to the Existential Theory of Reals,''} preprint, IRMAR, Rennes, France, 1995. \bibitem[RW96]{rojaswang} Rojas, J. M., and Wang, Xiaoshen, {\it ``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 {\tt http://www-math.mit.edu/\~{}rojas}. \bibitem[Sch94]{schneider} Schneider, Rolf, {\it Convex Bodies: The Brunn-Minkowski Theory,} Encyclopedia of Mathematics and its Applications, v.\ 44, Cambridge University Press, 1994. \bibitem[Shu93]{mikebezout} Shub, Mike, {\it ``Some Remarks on B\'ezout's Theorem and Complexity Theory,} {}From Topology to Computation: Proceedings of the Smalefest, pp.\ 443--455, Springer-Verlag, 1993. \bibitem[Stu93]{sparseelim} Sturmfels, Bernd, {\it ``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. \bibitem[Stu94]{combiresult} \underline{\hspace{\bernd}}, {\it ``On the Newton Polytope of the Resultant,''} Journal of Algebraic Combinatorics, 3: 207--236, 1994. \bibitem[Stu95]{grobandpoly} \underline{\hspace{\bernd}}, {\it Gr\"obner Bases and Convex Polytopes,} Lectures presented at the Holiday Symposium at New Mexico State University, December 27--31, 1994. \bibitem[Zie95]{ziegler} Ziegler, Gunter M., {\it Lectures on Polytopes,} Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995. \bibitem[Zip93]{zip} Zippel, R., {\it Effective Polynomial Computation,} Kluwer Academic Publishers, Boston, 1993. \end{thebibliography} \end{document}