\documentclass[12pt,notitlepage]{amsart} 
\usepackage{amssymb,epic,latexsym} 
\headheight=6.15pt
\textheight=574pt
\textwidth=432pt
\oddsidemargin=18.88pt
\evensidemargin=18.88pt
\topmargin=14.21pt

\newlength{\fw}
\settowidth{\fw}{{Fulton, William}}
\newlength{\jmr}
\settowidth{\jmr}{{Rojas, J. Maurice}}
\newlength{\jfc}
\settowidth{\jfc}{{Canny, John F.}}
\newlength{\bernd}
\settowidth{\bernd}{{Sturmfels, Bernd}}
\newlength{\ioan}
\settowidth{\ioan}{{Emiris, Ioannis Z.}}
\newlength{\agk}
\settowidth{\agk}{{Khovanskii, Askold G.}}
\newlength{\gkz}
\settowidth{\gkz}{{Gel'fand, I. M., Kapranov, M. M., and
Zelevinsky, A. V.}}

\newtheorem{cor}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{dfn}{Definition}
\newtheorem{cordfn}[dfn]{Corollary and Definition}
\newtheorem{van}{Vanishing Theorem for Resultants} 
\renewcommand{\thevan}{\unskip}
\newtheorem{main}{Main Theorem} 
\renewcommand{\themain}{\unskip}
\newtheorem{thm}{Theorem}
\newtheorem{rem}{Remark}	
\newtheorem{ex}{Example}

\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{\chooo}{\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{\rd}{{\underline{\mathrm{rd}}}}
\newcommand{\st}{{\underline{\mathrm{st}}}}
\newcommand{\nd}{{\underline{\mathrm{nd}}}}
\newcommand{\Pro}{\mathbb{P}}
\newcommand{\Pa}{\Pro^{|A|-1}_K}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\bp}{\pi} 
\newcommand{\fii}{\varphi} 
\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{\choo}{\mathrm{Ch}}
\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{\qed}{$\blacksquare$}
\newcommand{\Krn}{(K^*)^r \! \times \! K^{n-r}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cS}{\mathcal{S}}
\newcommand{\wP}{{\widetilde{P}}} 
\newcommand{\bZ}{{\bar{Z}}} 
\newcommand{\hZ}{\bar{Z}^\vee_+} 
\newcommand{\dZ}{\bar{Z}^\vee} 
\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{Toric Generalized Characteristic Polynomials} 

\author{J. Maurice Rojas}
\thanks{This research was completed at MIT and was 
partially funded by an N.S.F. Mathematical Sciences Postdoctoral Fellowship.
Research at MSRI is supported in part by NSF grant DMS-9022140.}

\address{\hskip-\parindent
Massachusetts Institute of Technology\\
	 Mathematics Department\\
         77 Mass. Ave.\\
         Cambridge, MA \ 02139, U.S.A. } 


\date{\today}

\begin{abstract}
We illustrate an efficient new method for handling polynomial systems with 
degenerate solution sets. In particular, a corollary of our techniques 
is a new algorithm to find an isolated point in every excess component 
of the zero set (over an algebraically closed field) of any $n$ by $n$ 
system of polynomial equations. Since we use the sparse resultant, we 
thus obtain complexity bounds (for converting any input 
polynomial system into a multilinear factorization problem) which are close to 
cubic in the degree of the underlying variety --- significantly better 
than previous bounds which were pseudo-polynomial in the classical B\'ezout 
bound. By carefully taking into account the underlying toric 
geometry, we are also able to improve the reliability 
of certain sparse resultant based algorithms for polynomial system 
solving.
\end{abstract} 

\maketitle

\section{Introduction}
\label{sec:intro}
The rebirth of resultants, especially through the {\bf 
toric}\footnote{Other commonly used prefixes for this more modern 
generalization include: sparse, mixed, $\cA$-, and $(\cA_1,\ldots,\cA_k)$-.} 
resultant 
\cite{gkz94}, has begun to provide a much needed alternative to 
Gr\"obner basis methods for solving polynomial systems. Continuing 
this philosophy, we will present a new, fast and reliable, resultant-based 
method for handling certain degenerate polynomial systems. Simply put, 
we refine and generalize the {\bf generalized characteristic polynomial} 
(GCP) \cite{gcp,mikebezout} to take {\bf sparsity}\/ into account. Furthermore, 
we introduce the concept of a {\bf twisted Chow form} in order to 
completely avoid any degeneracies within our algorithm. 

The importance of dealing with degenerate polynomial systems has 
been observed in earlier work on quantifier elimination over 
algebraically closed fields \cite{chigo,renegar,pspace}: 
Many reasonable algorithms fail catastrophically when 
presented with an $n$ by $n$ system having positive-dimensional zero 
set. When such is the case, it is of considerable benefit to the 
user to at least be given some sort of description of the zero-dimensional  
part of the zero set. This was a benefit of Canny's original 
GCP, but he remarked \cite[pg.\ 242]{gcp} ``For large, 
dense problems however, the resultant and GCP methods should be faster 
[than Gr\"obner algorithms].'' Our construction, 
the {\bf toric GCP}, promises to be much more competitive when applied 
to {\bf sparse} systems in such a comparison.

\begin{rem}
It should be emphasized that perturbation methods for degenerate 
systems (such as the toric GCP) are of the greatest importance 
when working with {\bf exact} arithmetic. However, floating point 
polynomial system solving also benefits from a complete and rigourous 
understanding of the potential degeneracies within exact arithmetic, e.g., 
\cite{smale87}. In any case, it is frequently the case in many applications 
that ``real life'' happens to land in a measure $0$ exception which breaks an 
algorithm.
\end{rem}

In what follows, we will frequently use multi-index notation in 
order to precisely control which monomial terms are allowed to appear in 
our polynomial systems.\footnote{This is what we mean by sparsity, 
as opposed to working solely in terms of polynomial degrees. Note 
that our notion overlaps the case of having very few monomial terms.} 
This notation, and in particular, 
{\bf supports} and {\bf Newton polytopes}, are amply detailed 
in earlier works of Emiris \cite{emiphd}, Huber \cite{birkphd}, Gelfand 
et.\ al.\ \cite{gkz90,gkz94}, Rojas \cite{convexapp,toricint}, 
Sturmfels \cite{sparseelim}, and Verschelde \cite{janphd}, to mention 
but a few authors and references. 

Since what we will present is at heart a perturbation method, we 
will first need the following definition to construct certain 
polynomial systems in ``general position.'' 
\begin{dfn}
\cite{convexapp,rojaswang}
Given $n$-tuples $D\!:=\!(D_1,\ldots,D_n)$ and $E\!:=\!(E_1,\ldots,E_n)$ 
of nonempty finite subsets of $\Zn$, we say that $D$ 
{\bf fills} $E$ iff (0) $D_i\!\subseteq\!E_i$ for all 
$i\!\in\![n]$ and (1) $\cM(D)\!=\!\cM(E)$. 
An {\bf irreducible} fill is then simply a fill which is minimal with respect 
to $n$-tuple containment. If $D$ or $E$ is instead an $n$-tuple of 
polytopes in $\Rn$, then we will use the same definition. 
\end{dfn}
In the above, $\cM(E)$ denotes the {\bf mixed volume} 
\cite{buza,schneider,isawres,mvcomplex}
of the convex hulls of the $E_i$, and we use $[j]$ for the set of 
integers $\{1,\ldots,j\}$.

Our construction is summarized in the following definition and 
main result. (Henceforth, all of our polynomials and roots are to be 
considered over an algebraically closed field $K$.) 
\begin{dfn} 
\label{dfn:main1}
Suppose $F$ is an $n\!\times\!n$ polynomial system with support contained 
in $E$ and $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. 
Assume further that $\cM(E)\!>\!0$ and $A$ has at least two elements. 
Letting $D$ be an irreducible fill of $E$, $F^*\!:=\!(\sum_{e\in D_i} x^e \; | 
\; i\!\in\![n])$, and $u\!:=\!(u_e \; | \; e\!\in\!A)$, define 
${\boldsymbol \choo_A(u)}\!:=\!\res_{(E,A)}(F,g)$ and 
${\boldsymbol \cH(u;s)}\!:=\!\res_{(E,A)}(F-sF^*,g)$, where $s$ is a new 
indeterminate. We call $\cH$ a {\bf toric} {\bf generalized 
characteristic polynomial for $\mathbf{(F,A)}$.} 
\end{dfn}
\noindent
In the above, $\res_\star(\cdot)$ denotes the toric resultant. Recall 
also that to any $n$-dimensional rational polytope $P\!\subset\!\Rn$ one can 
associate its corresponding {\bf toric variety} $\cT_P$ 
\cite{dannie,ksz92,tfulton,toricint}.
\begin{main}
Following the notation of definition \ref{dfn:main1}, 
consider $\cH$ as a polynomial in $s$ with coefficients in $K[u]$ and let 
${\boldsymbol \cF_A(u)}$ be the coefficient of the lowest degree term of 
$\cH$. Also let $P\!:=\!\sum^n_{i=1}\conv(E_i)$, $\wP\!:=\!P+\conv(A)$, and 
$\fii : \cT_\wP \longrightarrow \Pa$ the natural morphism defined 
by  $x \mapsto [x^e \; | \; e\!\in\!A]$ (cf.\ section \ref{sec:chowtor}). Then 
$\cF_A$ is a homogeneous polynomial, of degree $\cM(E)$, with the following 
properties:
\begin{enumerate}
\addtocounter{enumi}{-1}
\item{The constant term of $\cH(s)$ is precisely $\choo_A$. In particular, 
letting $Z$ be the zero set of $F$ in $\cT_\wP$, $\choo_A\!\equiv\!0 
\Longleftrightarrow \fii(Z)$ is positive-dimensional. } 
\item{If $\zeta\!\in\!\cT_\wP$ is an isolated root of $F$ then 
$\cF_A$ is divisible by $\sum_{e\in A} c_e u_e$, where 
$[c_e \; | \; e\!\in\!A]\!=\!\fii(\zeta)$.}  
\item{If a nonzero linear form $\sum_{e\in A} c_e u_e$ divides 
$\cF_A$ then $[c_e \; | \; e\!\in\!A]\!=\!\fii(\zeta)$ for {\bf some} root 
$\zeta\!\in\!\cT_\wP$ of $F$.}
\item{$\cF_A$ splits completely into linear factors. In particular, under the 
correspondence of (2), we can explicitly find at least one root of $F$ within 
every positive-dimensional irreducible component of the zero set of $F$ in 
$\cT_\wP$.}
\end{enumerate} 
We call $\cF_A$ a {\bf toric perturbation} of $\choo_A$. 
\end{main} 
A complete criterion for finding fills is given in theorem \ref{thm:me} 
of section \ref{sec:fill} and some simple examples of filling 
(and our Main Theorem) appear in section \ref{sec:ex}. Compatibility is 
defined in section \ref{sec:chowtor}. There we 
also detail what is meant by the zero set of $F$ in a toric variety.  
\begin{rem}
Alternatively, if one wants to avoid filling, one can substitute for $F^*$ 
any polynomial system 
(with support contained in $E$) {\bf known} to have exactly $\cM(E)$ 
roots (counting multiplicities) in $\Ksn$. So one can also view filling as a 
deterministic way of explicitly constructing a ``generic'' polynomial system. 
\end{rem}

So how does one actually use the above theorem? One simple example 
is the {\bf sparse $\mathbf{u}$-resultant} \cite{emiphd}, which is simply a 
variant of the classical $u$-resultant \cite{vdv}. It can be defined simply
as $\choo_A(u)$ where $A$ is the vertex set of the standard $n$-simplex in 
$\Rn$. One useful (and easily verified) property of the sparse $u$-resultant 
is that $F$ has a root $\zeta\!:=\!(\zeta_1,\ldots,\zeta_n)\!\in\!\Ksn 
\Longrightarrow u_0+\zeta_1u_1+\cdots+\zeta_nu_n$ divides $\choo_A(u)$. So, 
assuming $\choo_A(u)$ is not identically $0$ (and that one has good software 
for toric resultants and multivariate factoring), one can find the 
isolated roots of $F$ simply by factoring $\choo_A(u)$. Thus the degenerate 
instances $\choo_A(u)\!\equiv\!0$ obstruct this reduction to factoring 
and our Main Theorem allows us to avoid this problem: Simply use 
$\cF_A(u)$ instead of $\choo_A(u)$. 
\begin{rem}
An interesting ``failure'' for the classical $u$-resultant 
is the case where $F$ has only finitely many roots in affine space, 
while having infinitely many in projective space. This is where 
the classical GCP is especially handy. For the toric GCP, the 
toric variety $\cT_P$ plays the role of projective space. 
This is part of the philosophy of sparse elimination theory: 
working in a well chosen toric compactification (depending 
on $F$) leads to better algorithms than if one were to work only in 
projective space. In particular, {\bf lifting} to $\cT_\wP$ helps 
us detect precisely when the sparse $u$-resultant is identicaly $0$. 
\end{rem}

However, there is a stickier subtlety which occurs with 
the sparse $u$-resultant: It is possible for $F$ to 
have only finitely many roots within $\cT_P$ with 
$\choo_A(u)$ {\bf still} vanishing identically (cf.\ section 
\ref{sub:stranger}). This is the motivation for {\bf twisted Chow forms}, 
which are defined below, and pursued at much greater length in \cite{twist}.
\begin{cordfn}[cf.\ section \ref{sec:chowtor}]
\label{dfn:twist} 
Following the notation of our Main Theorem, pick $A$ 
to be the vertices of a product of simplices with which $P$ is compatible. 
We then call $\choo_A(u)$ the {\bf twisted Chow form} of the zero set of $F$ 
{\bf with respect to $A$}. Furthermore, a twisted Chow form does {\bf not} 
vanish identically if $F$ has only finitely many roots in $\cT_P$. \qed 
\end{cordfn}
In particular, since our last construction implies that $\cT_{\conv(A)}$ 
is a product of {\bf twisted} projective spaces \cite{tfulton}, 
the coefficients of a twisted Chow form are actually multisymmetric 
functions \cite{introchow,rio} of projections (by $\fii$) of roots of $F$ 
(in $\cT_P$) onto this product. So twisted Chow forms generalize the 
$u$-resultant, the sparse $u$-resultant, and (suitably extended \cite{twist}) 
the Chow form of a projective variety \cite{introchow}. Moreover, when 
combined with the {\bf Smith normal form} \cite{unimod1,unimod2,polyhomo} and 
the toric GCP, twisted Chow forms give a considerably more reliable method for 
solving polynomial systems than the sparse $u$-resultant \cite{twist}. 

An important difference to note is that our present toric GCP is 
primarily suited for finding roots in $\Ksn$, while the original GCP is mainly 
suited (in a ``non-sparse'' way) for affine space. To {\bf completely} 
generalize and improve the GCP in affine space, it is necessary 
to use the {\bf 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 {\bf $\Kn$-counting} \cite{toricint} instead of 
filling, we can actually recover Canny's GCP in the dense case. 

We close this introduction with a word on the computational complexity 
of computing the toric GCP. Neglecting  preprocessing (finding an 
irreducible fill and finding a mixed subdivision in order to 
set up the toric resultant matrices \cite{isawres}), recent work of 
Emiris, Morrain, and Pan \cite{emipan,moripan} suggests that it is possible
to find the perturbation $\cF_A$ within a number of arithmetic 
steps\footnote{Although the 
possibility of ``near-quadratic'' algorithms for polynomial system solving 
is discussed in \cite{emipan,moripan}, neither paper discusses the case where 
the zero set of $F$ is positive-dimensional, which is our main concern 
here.} which is close to {\bf cubic} in $\cM(E)$. (Indeed, Canny has 
pointed out \cite{gcp} that the original GCP can be computed in time 
close to cubic in the B\'ezout bound, which would be a special case 
of time cubic in $\cM(E)$.) Since $\cM(E)$ is much smaller than 
the B\'ezout number for most polynomial systems \cite{convexapp,toricint}, 
these preliminary results suggest that the toric 
GCP has considerable potential for practical applications. 

Let us now illustrate some of our theory.

\section{Examples}  
\label{sec:ex} 
We begin with two small examples of filling. We then see 
applications of the toric GCP to some degenerate $2 \times 2$ and $3 \times
3$ polynomial systems. Finally, we see a brief comparison of the toric 
GCP to the original GCP. 

\subsection{Filling Squares and Cubes}
For our first example, consider the pair of rectangles 
$\cP\!:=\!([0,a]\!\times\![0,b],[0,c]\!\times\![0,d])$ where
$a$, $b$, $c$, and $d$ are positive integers. Then it 
is easily verified (via theorem \ref{thm:me} of section 
\ref{sec:fill}) that the pair $$D\!:=\!(\{(0,0),(a,b)\},\{(0,d),(c,0)\})$$
fills $\cP$. In this case, the mixed area of both pairs is easily 
checked to be $ad+bc$. Note also that $D$ is a pair of oppositely 
slanting diagonals of our initial pair of rectangles (modulo 
taking convex hulls). Finally, it is easily checked that $D$ is 
indeed irreducible, since the removal of any point of $D$ results in a 
mixed area of $0$. 

For our second example, let $\cP$ instead be a triple of 
standard cubes (so that the vertex set of each cube is simply 
$\{0,1\}^3$). Then, using the criterion from theorem \ref{thm:me} 
once again, it is easily verified that the triple 
\[ D\!:=\!(\{(0,0,0),
(1,1,1)\},\{(1,0,0),(0,1,0),(0,0,1)\},\{(1,1,0),(1,0,1),(0,1,1)\}) \] 
fills $\cP$. Also, it is easily checked that the mixed volume of  
both triples is $6$. Note that the triple $D$ 
consists of a body diagonal and two oppositely oriented (but  
parallel) sub-triangles of the unit cube, modulo taking convex hulls. 
Finally, note that this $D$ is irreducible as well by theorem \ref{thm:me}. 
(This is also easily checked by one of the publically available software 
packages for mixed volume by Emiris, Huber, or Verschelde.)

\subsection{A Degenerate $2\times 2$ System} 
Consider the bivariate polynomial system 
$F\!:=\!(1+2x-2x^2y-5xy+x^2+3x^3y,2+6x-6x^2y-11xy+4x^2+5x^3y)$. 
Letting $E$ be the support of $F$, the reader can easily verify that 
$\cM(E)\!=\!4$, and that the only roots of $F$ are the points 
$\{(1,1),(\frac{1}{7},\frac{7}{4})\}$ and the line $\{-1\}\!\times\!K$ 
(assuming $\ch K\!\neq\!2$).\footnote{When $\ch K\!=\!2$, the 
second isolated root becomes an isolated root lying on the $x$-axis.} So
it would appear that the $u$-resultant (and even the sparse 
$u$-resultant) will vanish identically and not give us any useful 
information about any of these roots. Let us see if perturbing 
the sparse $u$-resultant helps...

Note that by theorem \ref{thm:me}, $D\!:=\!(\{\bO,(3,1)\},\{(1,1),(2,0)\})$ is 
an irreducible fill of $E$. So applying our Main Theorem with this $D$ (and 
$A\!:=\!\{(0,0),(1,0),(0,1)\}$) one can compute with the use of {\tt Maple} 
that $\cH(u;s)$ is precisely 
\scriptsize
\[ 
(u_2^4-u_0^4+u_1^4+6u_1^2u_2^2-4u_1u_2^3-4u_1^3u_2) \mathbf{s^8} 
\]
\[+(-20u_2u_0^3-20u_2^3u_0- 4u_1u_0^3+36u_1^2u_2^2-19u_0^4-24u_2^4 
+6u_0^2u_1u_2 \]
\[ +36u_1u_2^3+36u_1^4-12u_0u_1
^2u_2-9u_1^2u_0^2+3u_2^2u_0^2+36u_0u_1u_2^2-4u_0u_1^3-84u_1^3u_2)\mathbf{s^7}\]
\[ +(-170u_2
u_0^3-394u_1^3u_2-98u_1u_0^3-98u_0^2u_1u_2-20u_0^4+220u_2^4+370u_2^3u_0\] 
\[
+14u_0u_1
u_2^2-110u_0u_1^3-226u_1^2u_0^2-354u_1^2u_2^2+454u_1^4-274u_0u_1^2u_2+
74u_1u_2^3)\mathbf{s^6}\]
\[ +(-1612u_0^2u_1u_2+1008u_2u_0^3+903u_0^4-624u_1u_0^3-2632u_2^3u_0-2104u_0
u_1^2u_2-970u_2^4\]
\[ -1010u_1u_2^3 +418u_1^3u_2 -2104u_0u_1u_2^2-642u_1^2u_2^2-1547
u_1^2u_0^2-936u_0u_1^3-1557u_2^2u_0^2+2204u_1^4)\mathbf{s^5}\]
\[ +(538u_0^2u_1u_2+1271u_0^4+
12253u_2^2u_0^2+6972u_2u_0^3+1929u_1^4-3075u_1^2u_2^2+654u_0u_1u_2^2\] 
\[+50u_1u_0^3 +2156u_2^4-960u_1^2u_0^2-2290u_0u_1^3+132u_1u_2^3-
5344u_0u_1^2u_2-1142u_1^3u_2+8708u_2^3u_0)\mathbf{s^4} \] 
\[ +(4384u_1u_0^3-24988u_2^2u_0^2-1582u_1^3u_2-6756u_0^4+10884u_0
u_1u_2^2+3802u_1u_2^3+15438u_0u_1^2u_2\] 
\[ 
+1024u_0u_1^3+8324u_1^2u_0^2-12826u_2^3
u_0+11270u_0^2u_1u_2-6976u_1^4+7164u_1^2u_2^2-21326u_2u_0^3-2408u_2^4)
\mathbf{s^3}\]
\[ +(3436
u_1^3u_2+3800u_0u_1^3+7756u_2^3u_0-3886u_1u_2^3+1225u_2^4+17059u_2^2u_0^2-5984
u_1^2u_0^2\]
\[ +15708u_2u_0^3-12232u_0u_1u_2^2+5180u_0^4-2091u_1^2u_2^2-6828u_0u_1^2
u_2+1316u_1^4-12700u_0^2u_1u_2-4312u_1u_0^3)\mathbf{s^2} \] 
\normalsize
\[ +(-196u_2^4-448u_0^4-768u_1^3u_2 +512u_1^2u_0^2-1288u_2^3u_0\]
\[ -2436u_2^2u_0^2+1920u_0u_1u_2^2 +1536u_0^2u_1u_2+1024 u_0u_1^2u_2\] 
\[ +384u_1u_0^3-1792u_2u_0^3-384u_0u_1^3+768u_1u_2^3+260u_1^2u_2^2-64
u_1^4)\mathbf{\underline{s}.} \]  
(Sparse resultants of this size are quite amenable with the 
aid of {\tt Maple}, following the technique of a similar computation in 
\cite{rio}.) So our $\cF_A$ is just the coefficient of $s$ or $s^2$ in this 
polynomial, according as $\ch K\!\neq\!2$ or $\ch K\!=\!2$. To simplify our 
discussion, let us henceforth assume the former possibility. 

Factoring with {\tt Maple}, we obtain that $\cF_A$ can be written as
follows:
\[ -4(u_0+u_1+u_2)(28u_0+4u_1+49u_2)(u_0-u_1+u_2)(4u_0-4u_1+u_2) 
\] 
In particular, given any factor above, the ratio of the coefficients 
of $u_i$ and $u_0$ is precisely the $i^\thth$ coordinate of a corresponding 
root of $F$. Thus the first two factors correspond precisely to the 
two isolated roots we already know.  As for the last two factors, 
note that they both give isolated points lying on the aforementioned 
line  $\{-1\}\!\times\! K$. This can be interpreted as assigning 
an {\bf excess intersection multiplicity} of $2$ to the line, so that
the sum of all intersection numbers (of the irreducible components of 
the zero set of $F$ in $\cT_\wP$) is $4$.

Note that the original GCP could have been used above but 
would have resulted in a $u$-form of degree $16$ (the product 
of the degrees of $f_1$ and $f_2$). Also, the corresponding 
version of $\cH(\cdot)$ is significantly larger, having 672 terms, 
compared to 110 for our above toric GCP. 

\subsection{Stranger Degeneracies}
\label{sub:stranger}
Here we give two examples showing how the sparse $u$-resultant 
can fail to find roots in $\cT_P$, even with the benefit of the toric GCP, 
unless some other construction (such as a twisted Chow form) is used.  

First consider the parameterized bivariate system 
$F\!:=\!(a_1y+a_2x+a_3xy,b_1y+b_2x+b_3xy)$. Note that 
the mixed volume bound for this system is $1$. The sparse 
$u$-resultant for this system is also easily found  
(using the same techniques as in our last example) to 
be: 
\begin{eqnarray*}
& & (a_3^2b_2b_1+b_3^2a_2a_1-b_3a_2a_3b_1-b_3a_3b_2a_1)u_0 \\
&+& (b_1^2a_2a_3-b_1b_3a_2a_1-b_2 a_1a_3b_1+b_2b_3a_1^2)u_1 \\
&+& (b_1b_3a_2^2-b_2a_2a_3b_1+b_2^2a_3a_1-b_2b_3a_2a_1)u_2 
\end{eqnarray*}
In particular, we see that when 
\[(a_1,a_2,a_3,b_1,b_2,b_3)\!=\!(0,1,2,0,1,3).\] 
the sparse $u$-resultant vanishes identically.  For this specialization, it is 
also easy to see that $F$ has only {\bf one} root in $\cT_P$, and this root 
lies at the point of $\cT_P$ corresponding to the vertex $(0,1)$ of $P$ (cf.\ 
lemma \ref{lemma:once} from section \ref{sec:chowtor}), following 
the notation of our Main Theorem. In fact, 
for this $P$, $\cT_P\!\cong\!\Pro^2_K$ and the vertex $(0,1)$ 
corresponds precisely to the point $[x:y:z]\!=\![1:0:0]$ in this particular 
copy of $\Pro^2_K$ ($z$ denoting an extra variable for homogenizing).  

There are two ways of viewing this degeneracy ($\choo_A(u)\!\equiv\!0$ while 
$F$ has only finitely many roots in $\cT_P$) of the sparse $u$-resultant. 
The first is pragmatic: One should not count this as a deficiency of the 
sparse $u$-resultant because we've cheated and set two of 
the coefficients of $F$ to $0$, thus changing the supports. 
(Our next example avoids this trick.) The second point of view 
is more geometric: By our Main Theorem, this particular sparse resultant {\bf 
must} vanish due to the fact that our specialization of $F$ results in the 
existence of infinitely many roots of $F$ in $\cT_\wP$. In fact, $F$ 
vanishes on the $1$-dimensional subvariety of $\cT_\wP$ corresponding 
to the left-hand vertical edge of the hexagon $\wP$ (cf.\ section 
\ref{sec:chowtor}). 

Going one dimension higher, consider instead the $3\times 3$ 
system $G$, consisting of the following polynomials:
\begin{eqnarray*}
a_1yz+a_2xz+a_3xy+a_4xyz \\
b_1yz+b_2xz+b_3xy+b_4xyz \\
c_1yz+c_2xz+c_3xy+c_4xyz \\ 
\end{eqnarray*}
Note that the mixed volume bound for this system is again $1$. 

Clearly, $\frac{1}{xyz}G$ is a linear system in $\{\frac{1}{x},
\frac{1}{y},\frac{1}{z}\}$. So by Cramer's rule, we can express 
$x$, $y$, and $z$ as ratios of $3\times 3$ determinants in the 
coefficients. Combining this with the product formula for toric resultants 
\cite{chowprod} (and clearing denominators) we obtain that the sparse 
$u$-resultant of $G$ is precisely\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}.}
\[ [423][143][124]u_0+[123][143][124]u_1+[123][423][124]u_2
+[123][423][143]u_3 \]
where the {\bf bracket} $[ijk]$ \cite{introchow} is the 
$3\times 3$ subdeterminant
\[
\begin{vmatrix} a_i & a_j & a_k \\ b_i & b_j & b_k \\ 
		c_i & c_j & c_k \end{vmatrix}
\]
of the coefficient matrix of $G$. This compactly expressed 
resultant can be thought of as a {\bf semi-mixed} Chow form --- 
a toric resultant of a semi-mixed system \cite{polyhomo}, 
compressed in terms of suitable brackets.  

Now consider the specialization of $G$ to 
\begin{eqnarray*}
yz+xz+2xy+3xyz \\ 
yz+xz+4xy+9xyz \\
yz+xz+8xy+27xyz \\
\end{eqnarray*}
It is then easily verified that $G$ has exactly one 
root in $\cT_P\!\cong\!\Pro^3_K$: 
\[ [x:y:z:w]\!=\![1:-1:0:0] \]
($w$ denoting an extra variable for homogenizing).\footnote{
If $\ch K\!\in\!\{2,3\}$ then $G$ will actually have infinitely 
many roots in $\cT_P$. So let us assume henceforth that 
$\ch K\!\not\in\!\{2,3\}$. (It is easy to construct similar examples when 
$\ch K\!\in\!\{2,3\}$ as well.)} 
More to the point, the sparse $u$-resultant vanishes identically 
for this specialization of $G$, even though $G$ has no zero coefficients.  
Furthermore, one can easily check that the correspondence of (2) (from 
our Main Theorem) does {\bf not} give us the root of $G$ in $\cT_P$. 
(Using $D\!:=\!(\{(0,1,1),(1,1,1)\},
\{(1,0,1),(1,1,1)\},\{(1,1,0),(1,1,1)\})$, the coefficients of 
the $u_i$ in $\cF_A$ suggest the nonsensical root $[0:0:5:21]$.)  

To remedy this, we can use the twisted Chow form $\choo_{A'}(u)$ with 
$$A'\!:=\!\{(0,1,1),(1,0,1),(1,1,0),(1,1,1)\}.$$ In particular, 
when the coefficients of $G$ are unspecialized, 
\[ \choo_{A'}(u)=\begin{vmatrix} a_1 & a_2 & a_3 & a_4\\ 
			    b_1 & b_2 & b_3 & b_4\\
			    c_1 & c_2 & c_3 & c_4\\
			    u_{(0,1,1)} & u_{(1,0,1)} & u_{(1,1,0)} 
			    & u_{(1,1,1)} \\ \end{vmatrix} \]
So under our last specialization, this becomes 
$12u_{(1,0,1)}-12u_{(0,1,1)}$. Thus the coordinates of the sole root of $G$ 
in $\cT_{\conv(A')}\!\cong\!\Pro^3_K$ are precisely $[1:-1:0:0]$. To 
conclude, by virtue of our (compatible) choice of $A'$, the natural embeddings 
of $(\Ks)^3$ into $\cT_P$ and $\cT_{\conv(A')}$ are identical. This is how 
we've recovered our root in $\cT_P$. 

In closing, note that in practice we would never actually 
compute $\cH(u;s)$ --- we would instead recover $\cF_A$ 
via rapid and sophisticated interpolation techniques, e.g., 
\cite{zip}. In particular, our calculations can be sped up tremendously 
with suitably specialized code. 

\subsection{The ``Dense'' Case}
\label{sub:dense}
Our last example illustrates a simple fundamental case.

Suppose $E$ is the $n$-tuple $(d_1\Delta,\ldots,d_n\Delta)$
where $\Delta\!\subset\!\Rn$ is the vertex set of the standard 
$n$-simplex in $\Rn$ 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 $E$ (cf.\ theorem \ref{thm:me}). Letting 
$A\!=\!\Delta$, we see that our polynomial $\cH$ is a variant (over 
a general algebraically closed field) of the original
GCP applied to an $n\!\times\!n$ system of polynomials with degrees
$d_1,\ldots,d_n$ \cite{gcp}. In particular, our $F-sF^*$ has $2n$
$s$-monomials, compared to the $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.

\section{Filling}
\label{sec:fill}
Here we briefly recount filling and some
related concepts. Some of the material below is covered at greater length
in \cite{convexapp}. The paper \cite{combiresult}
is also a useful reference but deals more with the sparse resultant than
with filling. The results below form the basis for our combinatorial 
approach to perturbing degenerate polynomial systems.  

Let $\Sn\!\subset\!\Rn$ denote the unit $(n\!-\!1)$-sphere centered at the
origin. For any compact $B\!\subset\!\Rn$ and any $w\!\in\!\Rn$, define
$B^w$ to be the set of $x\!\in\!B$ where the inner-product $x\!\cdot\! w$ is
minimized. (Thus $B^w$ is the intersection of $B$ with its supporting
hyperplane in the direction $w$.) We then define
$E^w\!:=\!(E^w_1,\ldots,E^w_n)$ and
$D\!\cap\!E^w\!:=\!(D_1 \cap E^w_1,\ldots,D_n \cap E^w_n)$.

Recall that the {\bf dimension} of any $B\!\subseteq\!\Rn$, $\dim B$, is
the dimension of the smallest subspace of $\Rn$ containing a translate of
$B$. The following definition is fundamental to our development.
\begin{dfn}
Suppose $C\!:=\!(C_1,\ldots,C_n)$ is an
$n$-tuple of polytopes in $\Rn$ {\bf or} an $n$-tuple of finite subsets of
$\Rn$. We will allow any $C_i$ to be empty and say that a nonempty subset
$J\!\subseteq\![n]$ is {\bf essential} for $C$ (or $C$ {\bf has
essential subset $J$}) $\Longleftrightarrow$ (0) $\supp(C)\!\supseteq\!J$,
(1) $\dim(\sum_{j\in J} C_j)=|J|-1$, and (2) $\dim(\sum_{j\in J'} C_j)\geq
|J'|$ for all nonempty {\bf proper} $J'\!\subsetneqq\! J$.
\end{dfn}

Equivalently, $J$ is essential for $C \Longleftrightarrow$ the
$|J|$-dimensional mixed volume of $(C_j \; | \; j\!\in\!J)$ is $0$ and no
smaller subset of $J$ has this property. Figure \ref{fig:myfirst} below shows 
some simple examples of essential subsets for $C$, for various $C$ in the case
$n\!=\!2$. 

%%%%
\begin{figure}[bth]
\begin{picture}(410,70)(-35,-5)

\put(-80,-50){
\begin{picture}(133,100)(0,0)
% picture of the first pair
\put(51,80){\circle*{3}} \put(45,85){$C_1$} 
\put(72,80){\circle*{3}} \put(69,85){$C_2$} 
\put(42,50){$\{1\},\{2\}$}
\end{picture}}

\put(24,-50){
\begin{picture}(133,100)(0,0)
% picture of the second pair
\put(51,80){\circle*{3}} \put(45,85){$C_1$}
\put(62,70){\line(1,1){30}}
\put(62,70){\circle*{3}} \put(92,100){\circle*{3}} \put(79,77){$C_2$}
\put(60,50){$\{1\}$}
\end{picture}}

\put(145,-50){
\begin{picture}(133,100)(0,0)
% picture of the third pair
\put(36,70){\line(1,1){30}}
\put(36,70){\circle*{3}} \put(66,100){\circle*{3}} \put(36,85){$C_1$}
\put(62,70){\line(1,1){30}}
\put(62,70){\circle*{3}} \put(92,100){\circle*{3}} \put(79,77){$C_2$}
\put(45,50){$\{1,2\}$}
\end{picture}}

\put(276,-50){
\put(26,100){\line(1,-1){30}}
\put(26,100){\circle*{3}} \put(56,70){\circle*{3}} \put(43,85){$C_1$}
\put(72,70){\line(0,1){30}}
\put(72,70){\circle*{3}} \put(72,100){\circle*{3}} \put(74,85){$C_2$}
\begin{picture}(133,100)(0,0)
% picture of the fourth pair
\put(45,50){None}
\end{picture}}

\end{picture}

\caption{The essential subsets for 4 different pairs of plane polygons. 
(The segments in the third pair are meant to be parallel.) } 
\label{fig:myfirst}

\end{figure}
%%% 

A basic fact about mixed volumes is that $\cM(E)\!=\!0 \Longleftrightarrow
E$ has an essential subset, whenever $\supp(E)\!=\![n]$.
However, there is an even deeper connection between filling and 
essentiality:
\begin{thm} \cite[sec.\ 2.5]{convexapp}
\label{thm:me}
Suppose $D$ and $E$ are $n$-tuples of finite subsets of $\Zn$ such that
$\cM(E)\!>\!0$. Then $D$ fills $E
\Longleftrightarrow$ for all $w\!\in\!\Sn$, $\supp(D\cap E^w)$
contains a subset essential for $E^w$. \qed 
\end{thm}
\begin{rem}
One certainly need not check infinitely many $w$. In fact, we
need only check one $w$ (just pick any inner normal) for each face of
the polytope $\sum^n_{i=1} \conv(E_i)$.
\end{rem}

Filling is closely related to root counting for sparse polynomial 
systems, and this aspect is explored much further in
\cite{convexapp,rojaswang,toricint}. 
We also point out that the computational complexity of finding an irreducible 
fill is an open question. However, for $n\!\leq\!3$, finding 
irreducible fills is quite simple and no harder (asymptotically) than finding 
a convex hull. (Using theorem \ref{thm:me}, this follows as a simple 
geometric exercise.) In any event, 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 an irreducible fill is too hard, this 
step of our toric GCP construction need 
only be done {\bf once} for a given family of problems, provided
$E$ remains fixed. The situation where the monomial term structure of a
polynomial system remains fixed once and for all, and the coefficients may vary
many thousands of times, actually occurs frequently in many practical 
contexts such as robot control or computational geometry.

\section{Toric Geometry and the Proof of Our Main Theorem} 
\label{sec:chowtor} 
Our notation is a slight variation of that used in 
\cite{tfulton}, and is described at greater length in \cite{toricint}. 
We will assume the reader to be familiar with normal fans of polytopes and  
the construction of a toric variety from a fan or a finite point set 
\cite{tfulton,gkz94}. However, we will at least list our cast of main 
characters:
\begin{dfn} \cite{toricint} 
\label{dfn:toric}
Given any $w\!\in\!\Rn$, we will use the following notation:
\begin{itemize}
\item[$T=$]{The algebraic torus $\Ksn$}
\item[$P^w=$]{The face of $P$ with inner normal $w$} 
\item[$\sigma_w=$]{The closure of the cone generated by the inner normals of 
$P^w$} 
\item[$U_w=$]{The affine chart of $\cT_P$ corresponding to the cone
$\sigma_w$ of $\fan(P)$} 
\item[$L_w=$]{The $\dim(P^w)$-dimensional subspace of $\Rn$ parallel to $P^w$} 
\item[$x_w=$]{The point in $U_w$ corresponding to the semigroup
homomorphism $\sigma^\vee_w\cap\Zn \longrightarrow \{0,1\}$ mapping $p
\mapsto \delta_{w\cdot p,0}$, where $\delta_{ij}$ denotes the Kronecker
delta}  
\item[$O_w=$]{The $T$-orbit of $x_w=$ The $T$-orbit corresponding to $\relint 
P^w$} 
\item[$\cE_P(Q)=$]{The $T$-invariant Weil divisor of $\cT_P$ corresponding to 
a polytope $Q$.} 
\item[$\divisor(f)=$]{The Weil divisor of $\cT_P$ defined by 
a rational function $f$ on $\Ksn$} 
\item[$\cD_P(f,Q)=$]{$\divisor(f)+\cE_P(Q)=$ The toric effective divisor of 
$\cT_P$ corresponding to $(f,Q)$} 
\item[$\cD_P(F,\cP)=$]{The (nonnegative) cycle in the Chow ring of 
$\cT_P$ defined by $\bigcap^k_{i=1} \cD_P(f_i,P_i)$, whenever 
$\cP\!=\!(P_1,\ldots,P_k)$} 
\end{itemize}
\end{dfn}
We will say that a polytope $P$ is {\bf compatible} with $Q$ iff every cone 
of $\fan(Q)$ is a union of cones of $\fan(P)$ \cite{khocompat,tfulton,
toricint}. In particular, whenever $F$ is an $k\times n$ polynomial system with 
support contained in $E$, we will define the {\bf zero set of $\mathbf{F}$ in 
$\mathbf{\cT_P}$} to be the toric cycle $\cD_P(F,\cP)$, 
where $\cP\!:=\!(\conv(E_1),\ldots,\conv(E_k))$. 

The following result will provide some necessary geometric intuition 
for specializing resultants. 
\begin{van} \cite{resvan} 
Suppose $f_i$ is a polynomial over $K$ with support contained in 
$E_i\!\subset\!\Zn$ for all $i\!\in\![n+1]$. Then, provided 
$$\cM(E_1,\ldots,E_{i-1},E_{i+1},\ldots,E_{n+1})\!>\!0$$
for some $i\!\in\![n+1]$, 
\[\res_{\bar{E}}(f_1,\ldots,f_{n+1})\!=\!0 \Longleftrightarrow 
\bigcap\limits^{n+1}_{i=1} \cD_\wP(f_i,\conv(E_i))\!\neq\!
\emptyset,\]
where $\bar{E}\!:=\!(E_1,\ldots,E_{n+1})$ and 
$\wP\!:=\!\sum\limits^{n+1}_{i=1} \conv(E_i)$. \qed 
\end{van}
\begin{rem}
This result provides a geometric analogue, over a {\bf general} 
algebraically closed field, of the product formula for the sparse resultant 
\cite{chowprod}. 
\end{rem}

We will also make frequent use of the natural correspondence 
between the face interiors $\{\relint P^w\}$ and the $T$-orbits 
$\{O_w\}$ \cite{ksz92,tfulton,gkz94}. The following lemma gives a more 
explicit algebraic analogy between the faces of $P$ and the affine 
charts of $\cT_P$.  
\begin{lemma} \cite[Sections 4.2--5.1]{toricint}
\label{lemma:once}
Suppose $F$ is a $k\times n$ polynomial system over $K$ with support 
contained in a $k$-tuple of integral polytopes $\cP\!:=\!(P_1,\ldots,P_k)$ in 
$\Rn$. Assume further that $P$ is a rational polytope in $\Rn$. 
Then the defining ideal in $K[x^e \; | \; e\in\sigma^\vee_w\cap \Zn]$ of 
$U_w\cap \cD_P(F,\cP)$ is $\langle x^{b_i}f_i \; | \;$ for all 
$i\!\in\![k]$ and $b_i\!\in\!\Zn$ such that $b_i+P_i\subset\sigma^\vee_w 
\rangle$. \qed
\end{lemma} 

Lifting (or projecting) from one toric variety to another is an important 
fundamental ideal we will also use. The following lemma follows directly from 
the development of \cite{tfulton}.
\begin{lemma}
\label{lemma:lift}
Suppose $P\!\subset\!\Rn$ is an $n$-dimensional rational polytope, and 
$A$ is either a nonempty finite subset of $\Zn$ {\bf or} a rational 
polytope in $\Rn$. Assume further that $P$ is compatible with $\conv(A)$. Then 
there is a natural (surjective) proper morphism $\fii : \cT_P 
\twoheadrightarrow \cT_A$. In particular, following the notation of this 
section, $\fii(\cD_P(F,\cP))\!=\!\cD_A(F,\cP)$, where the latter cycle is the 
image of $\cD_{\conv(A)}(F,\cP)$ under the natural proper morphism from 
$\cT_{\conv(A)}$ to $\cT_A$. 
\end{lemma} 
\begin{rem}
Recall that $\cT_A$ can be defined as the image of of $\cT_\wP$ under 
the map $\fii$ from our Main Theorem. So, with this understanding, 
there is no ambiguity between our first and second $\fii$. 
\end{rem} 

To conclude our background, we will need the following lemma implying 
that $F^*$ is sufficiently generic in a useful sense. 
\begin{lemma}
\label{lemma:gen}
Suppose $D$ is an irreducible fill of some $n$-tuple $E$. Then 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, 
following the notation of our Main Theorem, $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. 

\subsection{The Proof of Our Main Theorem}
We first note that the well known results on the degree 
of $\res_{\bar{E}}(f_1,\ldots,f_{n+1})$ with respect to the coefficients 
of different $f_i$ \cite{combiresult} remain true over any algebraically 
closed field. This follows easily from the formulation of the resultant for 
a collection of invertible sheafs on a projective variety \cite{gkz94}. 
In particular, the degree of $\cH$ as a polynomial in $s$ should be 
\[ \sum\limits^n_{i=1} \cM(E_1,\ldots,E_{i-1},E_{i+1},\ldots,E_n,A).\] 
Also each coefficient of $\cH(s)$ 
should be a homogeneous polynomial (in the $u_e$) of degree $\cM(E)$. 
These two assertions of course include the opening statement of our Main 
Theorem (on the degree and homogeneity of $\cF_A$), but they will follow 
only upon showing that $\cH$ is not identically $0$. 

To see this, note that lemma \ref{lemma:once} and the Vanishing 
Theorem for Resultants readily imply that the coefficient of 
the {\bf highest} power of $s$ in $\cH$ is precisely 
$\res_{(E,A)}(F^*,g)$. (Simply check the zero set of $F-sF^*$ in 
$\cT_\wP$ at $s\!=\!\infty$.) By lemma \ref{lemma:gen}, and the Vanishing 
Theorem once more, we see that this polynomial in the $u_e$ is not identically 
$0$. So $\cH\!\not\equiv\!0$ and we've finished the simplest part 
of our proof. 

Part (0) of our Main Theorem follows similarly: One need only 
consider the {\bf unspecialized} resultant polynomial $\res_{(E,A)}(F,g)$ 
and observe the terms of degree $0$ in $s$ as we specialize coefficients 
to obtain $F-sF^*$. The statement on the vanishing of $\choo_A$ 
then follows easily from lemma \ref{lemma:lift} (since $\wP$ is 
compatible with $\conv(A)$) and the Vanishing Theorem: We obtain  
that $\fii(Z)$ is positive-dimensional iff $\choo_A$ has infinitely 
many distinct divisors of the form $\sum_{e\in A}c_eu_e$. In particular, 
corollary \ref{dfn:twist} follows as a special case of (0) since $P$ 
compatible with $\conv(A) \Longrightarrow \cT_P\!=\!\cT_\wP$. Note 
that (1), (2), and (3) also follow almost trivially, {\bf provided}
$\choo_A$ is not identically $0$. 

To properly handle the cases of (1), (2), and (3) where we are actually 
working with a non-trivial toric perturbation, let us first construct 
two important toric cycles: Let $\bZ$ be the zero set of $F-sF^*$ 
in $\cT_\wP\times\Pro^1_K$ and $\hZ$ the zero set of $\cH(u;s)$ in 
$\Pa\times\Pro^1_K$. Then it is 
easily observed that $Z\!=\!\bZ\cap (\cT_\wP\times\{0\})$. 
Also, it can be shown \cite[Section 5.1]{toricint} that $\bZ$ contains an 
algebraic curve $C$ (possibly reducible), with surjective projection onto the 
second factor of $\cT_\wP\times\Pro^1_K$, obeying the following property: 
$C\cap(\cT_\wP\times\{0\})$ contains the zero-dimensional part of $Z$, and 
consists of exactly $\cM(E)$ points (counting multiplicities). (In 
fact, $\bZ\cap(\cT_\wP\times\{s_0\})\!=\!C\cap(\cT_\wP\times\{s_0\})$ 
for almost all $s_0\!\in\!\Pro^1_K$.) Furthermore, by 
slightly modifying step (i) of the proof of the toric variety version 
of Bernshtein's theorem \cite[Section 5.1]{toricint}, one can show 
that $C$ intersects every positive-dimensional irreducible component of 
$Z$. (One also needs to use the definition of intersection 
multiplicity of an irreducible component $W$ as the number of curve 
branches intersecting $W$ in a 1-parameter deformation.) 

The proof of the rest of our main theorem will reduce to establishing 
a precise correspondence between the factors of $\cF_A$ and the points 
of $\fii(C\cap(\cT_\wP\times\{0\}))$. To complete this connection, we need 
only observe that $\hZ$ is a very special kind of hypersurface, closely 
related to $\bZ$. 

In particular, if $k$ is the least power of $s$ in $\cH$, observe that
$\hZ$ and the zero set of $\frac{\cH}{s^k}$ in $\Pa\times\Pro^1_K$ differ only 
by the presence of the hyperplane $\Pa\times\{0\}$. The second zero 
set does {\bf not} contain this hyperplane, so let's call the second 
zero set $\dZ$. Then by lemmata \ref{lemma:once} and 
\ref{lemma:lift}, and the Vanishing Theorem for Resultants, $\dim [\bZ\cap 
(\cT_\wP\times\{s_0\})]\!=\!0$ implies the following equivalence: 
$\cH(H_{\fii(\zeta)};s_0)\!=\!0 \Longleftrightarrow 
\zeta\!\in\!\bZ\cap (\cT_\wP\!\times\!\{s_0\})$, where 
$H_p$ is the hyperplane dual to the point $p$.\footnote{So if 
$p\!:=\![p_e \; | \; e\!\in\!A]\!\in\!\Pa$ then $H_p\!:=\!\{[y_e \; | \; 
e\!\in\!A]\!\in\!\Pa \; | \; \sum_{e\in A} p_ey_e\!=\!0\}$.} Now 
$\dim [\bZ\cap (\cT_\wP\times\{\infty\})]\!=\!0$ by construction. Hence 
$\dim [\bZ\cap (\cT_\wP\times\{s_0\})]\!=\!0$ for almost all 
$s_0\!\in\!\Pro^1_K$, by Main Theorem 2 of \cite{toricint}. So 
$\psi^\vee(C)$ is an open subset of $\dZ$, where we define 
$\psi^\vee(C)\!:=\!\{(y,s_0) \; | \; y\!\in\!H_{\fii(\zeta)} \ ; \  
\zeta\!\in\!C\cap(\cT_\wP\times\{s_0\}) \ ; \ s_0\!\in\!\Pro^1_K\}$. Therefore, 
since $\fii$ is a proper map, $\frac{\cH}{s^k}$ must vanish on {\bf all} of 
$\psi^\vee(C)$. In particular, 
\[ \cF_A(u)\!=\!\alpha\cdot\!\!\!\prod\limits_{\zeta\in 
C\cap(\cT_\wP\times\{0\})} \left(\sum\limits_{e\in A} c_{\zeta,e}u_e\right) 
\]
where $\alpha\!\in\!\Ks$, $[c_{\zeta,e} \; | \;
e\!\in\!A]\!:=\!\fii(\zeta)$, and the product counts intersection 
multiplicities.  

Continuing our main proof, (1), (2), and (3) follow immediately 
from our last formula and our preceding observations. \qed  

Note that our algebraic proof avoids the use of limiting 
arguments that were present in \cite{gcp}. Thus our result 
is equally valid when $K$ has positive characteristic. 

\bibliographystyle{amsalpha}
\begin{thebibliography}{A}

\bibitem[BZ88]{buza} Burago, Yu. D. and Zalgaller, V. A., {\it
Geometric Inequalities,} Grundlehren der mathematischen Wissenschaften 285,
Springer-Verlag (1988).

\bibitem[Can88]{pspace} Canny, John F., {\it ``Some Algebraic 
and Geometric Computations in PSPACE,''} Proc.\ 20$^\thth$ ACM 
Symp.\ Theory of Computing, Chicago (1988). 

\bibitem[Can90]{gcp} \underline{\hspace{\jfc}}, {\it ``Generalised 
Characteristic Polynomials,''} J.\ Symbolic Computation (1990) 9, pp.\ 
241--250. 

\bibitem[CG84]{chigo} Chistov, A. L., and Grigoriev, Dima Yu, {\it 
``Complexity of Quantifier Elimination in the Theory of Algebraically 
Closed Fields,''} Lect.\ Notes Comp.\ Sci.\ 176, Springer-Verlag (1984). 

\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[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[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[EP97]{emipan} Emiris, Ioannis Z. and Pan, Victor Y., {\it 
``The Structure of Sparse Resultant Matrices,''} preprint, 1997.

\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[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[HM91]{unimod2} Hafner, James L. and McCurley, Kevin S., {\it
``Asymptotically Fast Triangularization of Matrices Over Rings,''} SIAM
Journal on Computing, 20 (1991), no.\ 6, pp.\ 1068--1083.

\bibitem[HS95]{polyhomo} Huber, Birkett and Sturmfels, Bernd, {\it ``A
Polyhedral Method for Solving Sparse Polynomial Systems,"} Mathematics of
Computation, 64, pp.\ 1541--1555, 1995.

\bibitem[Hub96]{birkphd} Huber, Birk, {\it ``Solving Sparse Polynomial
Systems,''} Ph.D. Dissertation, Department of Mathematics, Cornell University 
(1996). 

\bibitem[Ili89]{unimod1} Iliopoulos, Costas S., {\it ``Worst Case
Complexity Bounds on Algorithms for Computing the Canonical Structure of
Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer
Matrix,"} SIAM Journal on Computing, 18 (1989), no.\ 4, pp.\ 658--669.

\bibitem[Kho77]{khocompat} Khovanskii, A. G., {\it ``Newton Polyhedra and
Toroidal Varieties,"} Functional Anal.\ Appl., 11 (1977), pp.\ 289--296.

\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[MP97]{moripan} Morrain, Bernard and Pan, Victor Y. {\it ``Solving
Special Polynomial Systems by Using Structured Matrices and Algebraic 
Residues,''} Foundations of Computational Mathematics,
selected papers of a conference, held at IMPA in Rio de Janeiro, January
1997, Springer-Verlag (1997).  

\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]{rio} \underline{\hspace{\jmr}} {\it ``Toric 
Laminations, Sparse Generalized Characteristic Polynomials, and a Refinement 
of Hilbert's Tenth Problem,''} Foundations of Computational Mathematics,
selected papers of a conference, held at IMPA in Rio de Janeiro, January
1997, Springer-Verlag (1997).   

\bibitem[Roj97b]{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[Roj97c]{twist} \underline{\hspace{\jmr}} {\it ``Solving Polynomial
Equations via Twisted Chow Forms,''} preprint, MIT (1997). 

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

\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[Sma87]{smale87} Smale, Steve, {\it ``The Topology of Algorithms I,''}
Journal of Complexity, {\bf 3} (1987), pp.\ 81--89.  

\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[Van50]{vdv} van der Waerden, B. L., {\it Modern Algebra,} 
3$^\rd$ edition, F.\ Ungar, New York.

\bibitem[Ver96]{janphd} Verschelde, Jan, {\it ``Homotopy Continuation
Methods for Solving Polynomial Systems,"} Doctoral Dissertation, Katholieke
Universiteit Leuven, Leuven, Belgium, May 1996.

\bibitem[Zip93]{zip} Zippel, R., {\it Effective Polynomial Computation,} 
Kluwer Academic Publishers, Boston, 1993. 

\end{thebibliography}

\end{document} 
