\documentclass{amsart}
\usepackage{amssymb,latexsym,epic} 
\setlength{\textwidth}{6in}

\newlength{\fw}
\settowidth{\fw}{{\footnotesize Fulton, William}}
\newlength{\hs} 
\settowidth{\hs}{{\footnotesize Huber, Birkett and Sturmfels, Bernd}}
\newlength{\agk}
\settowidth{\agk}{{\footnotesize Khovanskii, Askold G.}}
\newlength{\agku}
\settowidth{\agku}{{\footnotesize Kushnirenko, A. G.}}
\newlength{\jmr}
\settowidth{\jmr}{{\footnotesize Rojas, J. Maurice}}
\newlength{\bernd}
\settowidth{\bernd}{{\footnotesize Sturmfels, Bernd}}


\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{prop}{Proposition}
\newtheorem{propdfn}[prop]{Proposition and Definition}
\newtheorem{prob}{Problem}
\newtheorem{main}{Main Theorem}
\newtheorem{maintwo}{Main Theorem 2} 
\renewcommand{\themaintwo}{\unskip}
\newtheorem{mainthree}{Main Theorem 3}
\renewcommand{\themainthree}{\unskip} 
\newtheorem{mres}{Main Result}
\renewcommand{\themres}{\unskip} 
\newtheorem{anti}{Antipodality Theorem}
\renewcommand{\theanti}{\unskip} 
\newtheorem{alg}{Algorithm}
\newtheorem{thm}{Theorem}
\newtheorem{afpi}{Affine Point Theorem I} 
\renewcommand{\theafpi}{\unskip}
\newtheorem{afpii}{Affine Point Theorem II}
\renewcommand{\theafpii}{\unskip} 
\newtheorem{curve}{Curve Selection Lemma}
\newtheorem{rem}{Remark}
\newtheorem{rems}{Remarks}
\newtheorem{ex}{Example}
\newtheorem{dfn}[prop]{Definition}

\newcommand{\gen}{\mathrm{gen}}
\newcommand{\sm}{\mathrm{sum}}
\newcommand{\eps}{\varepsilon}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\wcD}{\widetilde{\cD}}
\newcommand{\Ds}{\cD_{\mathrm{shift}}}
\newcommand{\Dc}{\cD_{\mathrm{corn}}}
\newcommand{\cE}{\mathcal{E}}
\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{\cY}{\mathcal{Y}}
\newcommand{\V}{\mathrm{Vol}}
\newcommand{\supp}{\mathrm{Supp}}
\newcommand{\conv}{\mathrm{Conv}}
\newcommand{\init}{\mathrm{in}}
\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{\G}{\mathbb{G}}
\newcommand{\bL}{\mathbb{L}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\No}{\N\cup\{0\}}
\newcommand{\Non}{(\No)^n}
\newcommand{\Z}{\mathbb{Z}}

\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{\relint}{\mathrm{RelInt}}
\newcommand{\fan}{\mathrm{Fan}}
\newcommand{\hyp}{\mathrm{Hyper}}
\newcommand{\lin}{\mathrm{Lin}}
\newcommand{\res}{\mathrm{Res}}
\newcommand{\newt}{\mathrm{Newt}}

\newcommand{\Pc}{{P^\llcorner}} 
\newcommand{\wP}{{\widetilde{P}}} 
\newcommand{\Sn}{\mathcal{S}^{n-1}}
\newcommand{\Zn}{\Z^n}
\newcommand{\Qn}{\Q^n}
\newcommand{\Rn}{\R^n}
\newcommand{\Rno}{\R^{n-1}}
\newcommand{\Rni}{\Rn\!\setminus\!\sigma_I} 
\newcommand{\Rnoi}{\Rno\!\setminus\!\sigma_I} 
\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(J)}
\newcommand{\Knjp}{\Kn\!\setminus\!\hyp(J')} 
\newcommand{\Cni}{\Cn\!\setminus\!\hyp(I)} \newcommand{\bO}{{\bf O}}
\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{\cU}{\mathcal{U}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cF}{\mathcal{F}}
\newcommand{\tF}{\widetilde{F}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\wcT}{\widetilde{\cT}}

\begin{document}

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}

\title[Toric Intersection Theory for Affine Root Counting]{Toric
Intersection Theory for Affine Root Counting$^1$}
\footnotetext[1]{Submitted~to~the~Journal~of~Pure~and~Applied~Algebra.~Also~ 
\mbox{available}~\mbox{on-line}~at~{\tt http://www-math.mit.edu/\~{}rojas}.}

\author{J. Maurice Rojas}
\thanks{This research was completed at MSRI and partially funded by a
Chateaubriand Fellowship, an NSF Mathematical Sciences Postdoctoral 
Research Fellowship, and NSF grant DMS-9022140.}

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

\email{rojas@math.mit.edu} 

\subjclass{Primary 14M25, 14N10; Secondary 12Y05, 14Q99, 52A39, 52B20,
52B55, 65F50, 65H10, 93B25, 93B27}
%
% 14M25 = Toric Varieties, Newton Polytopes 
% 14N10 = Enumerative problems (combinatorial problems) 
%
% 12Y05 = Computational Aspects of Fields and Polynomials 
% 14Q99 = Computational Aspects of Algebraic Geometry 
% 52A39 = Mixed volumes and related topics 
% 52B20 = Lattice Polytopes
% 52B55 = Computational Aspects Related to Convexity 
% 65F50 = Sparse Matrices
% 65H10 = Systems (Nonlinear or Transcendental Equations) 
% 93B25 = Algebraic Methods
% 93B27 = Geometric (Algebraic Geometry) methods 
%
\keywords{Mixed volume, generic, root, counting, affine, orbit, isolated, upper
bound, sparse, polynomial system, resultant, homotopy, toric variety}

\date{October 27, 1996} 

\dedicatory{This paper is dedicated to Basil Gordon on the occassion of his
$2^{6\thth}$ birthday.}

\begin{abstract} 
Given any polynomial system with fixed monomial term structure, we give 
explicit formulae for the generic number of roots with specified 
coordinate vanishing restrictions. For the case of affine 
space minus an arbitrary union of coordinate hyperplanes, these formulae are 
also the tightest possible upper bounds on the number of isolated roots. We 
also characterize, in terms of sparse resultants, precisely when these upper 
bounds are attained. Finally, we reformulate and extend some of the prior 
combinatorial results of the author on which subsets of coefficients must be 
chosen generically for our formulae to be exact.

Our underlying framework provides a new toric variety setting for 
computational intersection theory in affine space minus an arbitrary union of 
coordinate hyperplanes. We thus show that, at least for root counting, it is 
better to work in a naturally associated toric compactification instead of 
always resorting to products of projective spaces. 
\end{abstract}

\maketitle

\section{Introduction}
\label{sec:intro}
We give a new toric variety context for convex geometric root counts 
for polynomial systems. Our results also improve prior extensions to affine 
space \cite{kho78,dankho,myprize,convexapp,rojaswang,liwang,hsaff} 
of the seminal works \cite{kus75,bernie,kus76,khocompat} on root counting 
in the algebraic torus. In addition to their combinatorial appeal, there has 
been growing excitement about these methods in the computational algebra 
community due to their efficiency and applicability in many industrial problems 
\cite{mobiorobo,emiphd,isawres,dynamiclift}.

\setcounter{footnote}{1}
Let us begin with some notation: Let $E_1,\ldots,E_n$ be nonempty finite
subsets of $\Non$. For any $e\!=\!(e_1,\ldots,e_n)\!\in\!\Non$ let $x^e$
denote the monomial $x^{e_1}_1\cdots x^{e_n}_n$. In this way we will let
$f_1,\ldots,f_n$ be polynomials in the variables $\{x_1,\ldots,x_n\}$ with
(algebraically independent) indeterminate coefficients, such that the set
of exponent vectors occuring in $f_i$ is precisely $E_i$. The set $E_i$ is
called the {\em support}\/ of $f_i$ and this representation specifies
exactly which monomials can appear in $f_i$. All of our root counts will
make maximal use of this monomial term information --- not just the degrees
of the $f_i$. A convenient short-hand will be the following: Let
$E\!:=\!(E_1,\ldots,E_n)$ and $F\!:=\!(f_1,\ldots,f_n)$. Then $E$ is the
{\it support}\/ of $F$ and we call $F$ an {\it $n\!\times\!n$ indeterminate
polynomial system.}\/ We also let $\cC_E$ denote the vector (or sometimes
the set) consisting of all the indeterminate coefficients of all the $f_i$.
If we {\it specialize}\/ some of the coefficients (that is, give them
values chosen from some field)\footnote{We will leave the case of 
more general specializations, e.g., non-trivial polynomial relations amongst 
the coefficients, for future work.} then we say that $F$ has support 
{\em contained}\/ in $E$.

Let $K$ be an algebraically closed field of arbitrary characteristic. For
instance, $K$ can be the complex numbers or the algebraic closure of a
finite field. Also let $|E|$ denote the sum of the cardinalities of the
$E_i$. Our first definition focuses our attention on the generic number of
roots a polynomial system has in a given region $W$, when the
monomial term structure is determined by $E$.

\begin{propdfn}
\label{big}
Let $F$ be an $n\!\times\!n$ indeterminate polynomial system with support
$E$, $\cC_E$ the vector of coefficients of $F$, and $W$ a constructible
subset of $\Kn$. For any $\cC\!\in\!K^{|E|}$ let $\cN_K(E;W;\cC)$ denote
the number of roots of $F|_{\cC_E=\cC}$ lying in $W$, counting
multiplicities.\footnote{See remark \ref{rem:fulton} of section 
\ref{sub:mult} for the definition of intersection multiplicity. } Then there 
exists a {\em proper} algebraic subset
$\Delta\!\subset\!K^{|E|}$, depending on $E$ and $W$, such that
$\cN_K(E;W;\cdot)$ is a constant function on $K^{|E|}\!\setminus\!\Delta$.
We let $\cN_K(E;W)$ denote the value of this constant function. We will
also refer to $\cN_K(E;W)$ as the {\em generic value} of $\cN_K(E;W;\cdot)$
or the {\em generic number of roots} of $F$ in $W$. \qed
\end{propdfn}

\begin{dfn}
Let $[a..b]$ be the set of integers $\{a,a+1,\ldots,b\}$ and for any
(possibly empty) $J\!\subseteq\![1..n]$ define $O_J\!:=\!\{x\!\in\!\Kn\; |
\; x_j\!\neq\!0 \Longleftrightarrow j\!\in\!J\}$. We call $O_J$ an {\em
orbit}. 
\end{dfn}
\noindent
Note that $O_J$ is a relatively open subset of a
$|J|$-dimensional coordinate subspace of $\Kn$. 

Recall that the ($n$-dimensional) mixed volume, $\cM(\cdot)$, takes as
input an $n$-tuple of nonempty compact convex sets in $\Rn$ and always
outputs a nonnegative real number
\cite{bonnie,grunbaum,convexapp,schneider,
polyhomo,isawres,mvcomplex,dynamiclift,drs}. 
\begin{mres}
We will express $\cN_K(E;W)$ in terms of mixed volume for $W$ an arbitrary
union of orbits, $K$ algebraically closed, and any $E$. We will also give a
computational algebraic criterion for precisely when this generic number of
isolated roots is attained, i.e., explicit algebraic equations for $\Delta$. 
Our algebraic criterion is then refined to a more practical computational 
result: a combinatorial classification of the sets of coefficients (subvectors 
of $\cC_E$) whose genericity guarantees that $F$ indeed has exactly 
$\cN_K(E;W)$ isolated roots lying in $W\!$, counting multiplicities.
\end{mres}

The above result is contained in Main Theorems 1--3, the Affine Point
Theorem II, and Corollary \ref{cor:stable}  
of the next section. Examples of our main results
appear in section \ref{sec:examples} and the remaining sections are devoted
to proving our main theorems. Two useful tools applied in our proofs may be
of independent interest: the Antipodality Theorem (\cite{aff} and cf.\
section \ref{sec:mom}) and a
toric variety version of Bernshtein's Theorem (cf.\ section \ref{sub:tv}).
The former tells us how curves behave at toric infinity, while the latter
collects some folkloric facts relating Bernshtein's famous theorem on root
counting \cite{bernie} to intersection theory on toric varieties
\cite{ifulton2,tfulton}.

\section{Summary of Our Main Results}
\label{sec:sum}
We will make the natural restriction of considering only those $E$ for
which $\cN_K(E;W)\!<\!\infty$. Such $E$, which we will call {\em
$W$-nice,}\/ are completely characterized combinatorially in the appendix. It 
will also be helpful to describe certain subspace unions and cones concisely.
\begin{dfn}
\label{dfn:lin}
For any $I\!\subseteq\![1..n]$ let $\hyp(I)\!\subset\!\Kn$ be the union
of coordinate hyperplanes $\bigcup_{j\in I} \{x \; |\\ 
x_j\!=\!0\}$. Also
let $\lin(I)\!\subseteq\!\Rn$ be the coordinate subspace generated by the
subset $\{\hat{e}_j \; | \; j\in I\}$ of the standard basis, and 
let $\sigma_I$ be the cone defined by the intersection of 
$\lin([1..n]\setminus I)$ with 
the nonnegative orthant. Finally, let $\bO$ denote the origin in whatever 
module we work in. In particular, $\hyp(\emptyset)\!=\!\emptyset$ and 
$\lin(\emptyset)\!=\!\sigma_{[1..n]}\!=\!O_\emptyset\!=\bO$.  
\end{dfn}

\subsection{Explicit Formulae}
We give the following recursive formula for $\cN_K(E;W)$. Although perhaps
cumbersome at first glance, our formula contains important intersection
theoretic information that helps extend certain algorithms for solving
polynomial systems \cite{aff} and is also quite practical in low dimensions 
(cf.\  section \ref{sub:mts} and remark \ref{rem:simple}). 
Our result also generalizes, and makes more explicit, an algorithm for 
computing $\cN_\C(E;\Cn)$ (for a smaller class of $E$) alluded to in 
\cite{kho78,dankho}. 
\begin{main}
\label{main:wow}
Let $K$ be any algebraically closed field and suppose
$E\!:=\!(E_1,\ldots,E_n)$ is an $n$-tuple of finite subsets of
$(\N\cup\{0\})^n$ which is nice for $W$, where $W$ is a union of orbits in
$\Kn$. Also, for all
$i,j\in [1..n]$, define $m_{ij}\!:=\!\min\{y_j\; | \; 
(y_1,\ldots,y_n)\!\in\!E_i \}$ and let $m_1,\ldots,m_n$ be the rows of the 
matrix $[m_{ij}]$. Then $\cN_K(E;W)$ is precisely
\[ \sum \limits_{J\subseteq [1..n]} \; 
\sum \limits_{\rho:J^c \hookrightarrow [1..n]} \left[
\left( \prod \limits_{j\in J^c} m_{j\rho(j)} \right)
\cN_K(E_{(J,\rho)};W\cap \lin(\rho(J^c)^c) ) \right], \]
where $(\cdot)^c$ denotes set-theoretic complement within $[1..n]$, 
$E_{(J,\rho)}\!:=\!((E_i-m_i)\cap\lin(\rho(J^c)^c) \; 
| \; i\!\in\!J)$, and $\cN_K(\emptyset;W)$ is defined as $1$ or $0$
according as $W$ is $\bO$ or $\emptyset$. Furthermore, if $W\!=\!\Kni$ for some
$I\!\subseteq\![1..n]$, then $\cN_K(E;W)$ is also the {\em maximum} 
number of isolated roots in $W$, counting multiplicities.
\end{main} 
\begin{rem}
\label{rem:disting}
Our root counting formulae also hold when $E$ is not nice 
for $W,$ provided one counts {\em embedded} \cite[pg.\ 90]{eisenbud} 
zero-dimensional components as well. 
\end{rem}
A simple example of the above formula is given in section \ref{sub:mts} and
its proof appears in section \ref{sub:chow}. Main Theorem 1 is recursive
in the sense that every term on the right-hand side is a  
lower-dimensional or {\em cornered}\/ \cite{rojaswang} case of
$\cN_K(\cdot)$. In particular, the following definition and main result
take care of the ``first'' term $\cN_K(E_{([1..n],\cdot)};W)$. 
\begin{dfn}
Call a $k$-tuple $C\!:=\!(C_1,\ldots,C_k)$ of nonempty subsets of 
$\Rn$ {\em cornered} iff $C_i$ lies in the nonnegative orthant and 
$C_i\cap\{(y_1,\ldots,y_n)\!\in\!\Rn \; | \; y_j\!=\!0\}\!\neq\!\emptyset$ for 
all $i\!\in\![1..k]$ and $j\!\in\![1..n]$. Also, for any 
$a_1,\ldots,a_k\!\in\!\Rn$, define $a\cup C$ to be the $k$-tuple of 
convex hulls $(\conv(\{a_1\}\cup C_1),\ldots,\conv(\{a_k\}\cup C_k))$.  
\end{dfn}
\begin{afpii} 
Fix $I\!\subseteq\![1..n]$ and suppose $E$ is an $n$-tuple of finite
subsets of $(\N\cup\{0\})^n$ which is nice for $\Kni$ and cornered. For
each $i\!\in\![1..n]$ let $a_i\!\in\!E_i\cap\lin(I)$ or set
$a_i\!:=\!\bO$ if $E_i\cap\lin(I)$ is empty. Then
$\cN_K(E;\Kni)=\cM(a\cup E)$ and this generic number is also the {\em
maximum} number of isolated roots in $\Kni$, counting multiplicities. More
generally, if $E$ is instead nice for $O_J$ and cornered, then
$\cN_K(E;O_J)\!=\!\sum_{J'\supseteq J} (-1)^{|J'\setminus J|}
\cM_{J'}$, where $\cM_{J'}$ is the mixed volume corresponding to
the case $W\!=\!\Kn\!\setminus\!\hyp(J')$. 
\end{afpii}
\noindent
The above result is proved in section \ref{sub:embed} and complements 
the author's Affine Point Theorem I which first appeared in \cite{rojaswang}.
\begin{rem}
Note that proposition 1 directly implies that $\cN_K(E;W)$ is additive 
with respect to disjoint unions in $W$. So we can compute 
$\cN_K(E_{([1..n],\cdot)},W)$ 
for general $W$ simply by summing various instances of the Affine Point 
Theorem II. 
\end{rem}
\begin{rem}
Separating into cornered and non-cornered cases also simplifies 
Khovanskii's earlier notion of attached, weakly attached, and strongly 
attached hyperplanes \cite{kho78}.
\end{rem}

The reader need not be alarmed at the prospect of computing an alternating
sum of mixed volumes since a more efficient way to compute $\cN_K(E;O_J)$
is given by the following corollary of Main Theorem 1. This result, which
generalizes a formula for $\cN_\C(E;\Cni)$ due to Huber and Sturmfels
\cite{hsaff}, also seems to yield a more efficient way to compute
$\cN_K(E;W)$ for general $W$ when $n\!>\!2$. 
\begin{cor}
\label{cor:stable}
Following the notation of Main Theorem \ref{main:wow}, fix
$I\!\subseteq\![1..n]$ and suppose $E$ is nice for $\Kni$. Then
$\cN_K(E;\Kni)=\cSM_{I^c}(E)$. Furthermore, if
$J\!\subseteq\![1..n]$, $E$ is instead $O_J$-nice, and $\Omega$ is a stable
subdivision of $E$, then $\cN_K(E;O_J)\!=\!\sum_C \cM(C)$, where the sum is 
over all stable cells $C\!\in\!\Omega$ such that the inner normal of the 
lifted cell $\widehat{C}$ has support $J^c$.
\end{cor}
\noindent
The quantity $\cSM_J(E)$ is a new convex geometric entity called the {\em
$J$-stable mixed volume}. We refer the reader to \cite{hsaff} for its
definition, and to \cite{polyhomo,hsaff} for the definitions of
subdivisions, lifted cells, and stable cells. The support of a vector is
simply the set of indices corresponding to its nonzero coordinates.
Corollary \ref{cor:stable} is proved in section \ref{sub:chow}.

Better still, we can determine precisely when our formulae count 
the number of roots exactly, even when some of the coefficients are fixed and 
only a few coefficients are generic. 

\subsection{Algebraic and Combinatorial Criteria for Exactness} For any
$w\!\in\!\Rn$, let $E^w_i$ be the set of points $y\!\in\!E_i$ which minimize
the standard inner product $w\cdot y$. Similarly, for any polytope
$P\!\subset\!\Rn$, let $P^w$ denote the face of $P$ with inner normal
$w$. Also let $E^w\!:=\!(E^w_1,\ldots,E^w_n)$ and recall that a {\em facet}\/ 
is a polytope face of codimension 1. A key innovation of Bernshtein's seminal
work on root counting is the algebraic condition he gave for his formula  
to be the {\em exact}\/ number of roots. Sadly, this ``second half'' of 
Bernshtein's Theorem is not sufficiently explored in the literature. So we 
give the following generalization, proved in section \ref{sub:algcond}.
\begin{main} 
\label{main:res}
Following the notation of definitions \ref{big} and \ref{dfn:lin} and Main 
Theorem \ref{main:wow}, suppose $W\!=\!\Kni$ and that the coefficients of $F$ 
have all been specialized to constants in $K$. Let $S$ be the polytope 
$\sum^n_{i=1}\conv(E_i)$. Then the following condition implies that $F$ has 
exactly $\cN_K(E;\Kni)$ roots, counting multiplicities, in $\Kni$:
\begin{itemize}
\item[(a$_2$)]{$\prod \res_{E^w}(F)\!\neq\!0$, where the product is over all 
unit inner facet normals $w\!\in\!\Rni$ of $S$, and }
\item[(b$_2$)]{if $n\!>\!1$ then for all $J\!\subsetneqq\![1..n]$ 
containing $I$, and all injections $\rho : J^c \hookrightarrow [1..n]$ such 
that $\rho(J^c)\cap I\!=\!\emptyset$ and $\prod_{j\in J^c} m_{j\rho(j)}>0$, 
\[ \cN_K\left(E_{(J,\rho)};\lin(\rho(J^c)^c)\cap(\Kni);\cC_E\right) = 
\cN_K\left(E_{(J,\rho)};\lin(\rho(J^c)^c)\cap(\Kni)\right).\]}
\end{itemize}
Furthermore, the converse implication holds as well if 
$\cN_K(E_{([1..n],\cdot)};\Kni)\!>\!0$. In particular, (a$_2$) and (b$_2$) 
together imply that the zero set of $F$ in $\Kni$ is zero-dimensional or empty. 
\end{main}
\noindent 
The sparse resultant $\res_*(F)$ is described at length in 
\cite{gkz90,chowprod,jandi1,
combiresult,gkz94,isawres} and our notation is explained in section 
\ref{sub:algcond}. Sharper criteria for the cases 
$\cN_K(E_{([1..n],\cdot)};\Kni)\!=\!0$ are also discussed in section 
\ref{sub:algcond}. 
\begin{rem}
Parallel to Main Theorem 1, Main Theorem 2 is also recursive since for any 
$\vartheta\!\subsetneqq\![1..n]$, $\lin(\vartheta)\cap(\Kni)$ can be naturally 
identified with the complement of a union of coordinate hyperplanes in 
$K^{|\vartheta|}$. 
\end{rem}

Alternatively, we can give combinatorial criteria for exactness 
which are always sufficient and necessary. More precisely, let $c_{i,e}$ 
denote the (indeterminate) coefficient of the $x^e$ term of $f_i$. If an 
$n$-tuple 
$D\!:=\!(D_1,\ldots,D_n)$ satisfies $D_i\!\subseteq\! E_i$ for all 
$i\!\in\![1..n]$ then we simply abbreviate this as $D\!\subseteq\!E$. For any 
such $D$ define $\cC_D\!=\!\{c_{i,e} \; | \; i\!\in\![1..n]$, $e\!\in\!D_i\}$.
\begin{dfn}
\label{dfn:count} 
We say that $D$ {\em $W$-counts} $E$ iff (0) $D\!\subseteq\!E$, (1) $D$ 
and $E$ are nice for $W$, and (2) for any specialization over $K$ of the
coefficients $\cC_E\!\setminus\!\cC_D$, a generic specialization of the
remaining coefficients $\cC_D$ suffices to make $F$ have exactly
$\cN_K(E;W)$ roots lying in $W$, counting multiplicities.
\end{dfn}
\noindent
So by proposition \ref{big} we at least know that $E$ always 
$W$-counts $E$ if $E$ is $W$-nice. 

Define $\supp(D)\!:=\!\{i \; | \; D_i\!\neq\!\emptyset\}$,
$D\cap\lin(J)\!=\!(D_1\cap\lin(J),\ldots,D_n\cap\lin(J))$, and $D\cap
E^w\!:=\!(D_1\cap E^w_1,\ldots,D_n\cap E^w_n)$. Our final main theorem
gives an exact convex geometric criterion for when $D$ $(\Kni)$-counts $E$. 
\begin{main} 
\label{main:count}
Following the notation of definitions \ref{big} and \ref{dfn:lin} and Main 
Theorem \ref{main:wow}, suppose that $W\!=\!\Kni$ and let 
$S$ be the polytope $\sum^n_{i=1}\conv(E_i)$. Then $D$ $(\Kni)$-counts $E 
\Longleftrightarrow$ one of the following exclusive conditions holds: 
\begin{enumerate}
\item{$\cN_K(E;\Kni)\!=\!0$ and for all $J\!\subseteq\![1..n]$ 
containing $I$, $\supp(D\cap\lin(J))$ contains a subset essential for 
$E\cap\lin(J)$.} 
\item{$\cN_K(E;\Kni)\!>\!0$ and 
\begin{itemize}
\item[(a$_3$)]{for each face of $S$ with an inner normal $w\!\in\!\Rni$, 
pick a single such $w$. Then 
for all of these $w$, $\supp(D\cap E^w)$ contains a subset essential for 
$E^w$, and }
\item[(b$_3$)]{if $n\!>\!1$ then for all $J\!\subsetneqq\![1..n]$ 
containing $I$, and all injections $\rho : J^c \hookrightarrow [1..n]$ such 
that $\rho(J^c)\cap I\!=\!\emptyset$ and $\prod_{j\in J^c} m_{j\rho(j)}>0$, 
the $|J|$-tuple  
\[ ((D_i-m_i)\cap \lin(\rho(J^c)^c) \; | \; i\!\in\!J) \]  
$W_{(J,\rho)}$-counts $E_{(J,\rho)}$, where 
$W_{(J,\rho)}\!:=\!\lin(\rho(J^c)^c)\cap(\Kni)$.}
\end{itemize}} 
\end{enumerate}
\end{main}
The definition of essentiality, which is a combinatorial geometric
condition, appears in the appendix. We thus obtain a recursive combinatorial 
condition for when the zero set of $F$ in $\Kni$ consists of exactly  
$\cN_K(E;\Kni)$ points, counting
multiplicities. Our final main theorem is proved in section \ref{sub:algcond} 
as well. Here we deal mainly with genericity conditions for {\em global}\/ 
root counting, so we will leave the classification 
of $O_\vartheta$-counting (when $\vartheta\!\neq\![1..n]$) for another paper. 

\section{Examples}
\label{sec:examples}
In the following examples, any mixed volume computation will follow easily
(even by hand) from the definition or basic properties of the mixed volume
\cite{bonnie,grunbaum,schneider}. In particular, it useful to recall
the following formula for the $n\!=\!2$ case: 
$\cM(P_1,P_2)\!=\!\area(P_1+P_2)-\area(P_1)-\area(P_2)$.
\subsection{Comparisons to the Generalized B\'{e}zout Theorems}
\label{sub:bez}
Although mixed volume bounds can be hard to compute for some extremely
large polynomial systems, they do have the advantage that they are always
at least as good as any B\'ezout-type bound. Also, current mixed volume
software is already fast enough to have been useful in many industrial
problems, e.g., \cite{emiphd,dynamiclift}. Here we will give an example of
a family of polynomial systems whose mixed volume root counts are
significantly better than any generalized B\'ezout bound.

However, let us first recall what is meant by a generalized B\'ezout bound.
A good reference is \cite{wam92} so we will only quickly outline the most
general (zero-dimensional) version of B\'ezout's Theorem: Given a partition
of $\{x_1,\ldots,x_n\}$ into sets of cardinality $n_1,\ldots,n_\lambda$, the 
corresponding {\em multihomogeneous}\/ B\'ezout Theorem gives an explicit 
formula for $\cN_K(E;\Pro^{n_1}_K\!\times \cdots \times\!\Pro^{n_\lambda}_K)$ 
as a polynomial expression involving the degrees of the $f_i$ with 
respect to the chosen sets of variables.\footnote{Polynomial roots in a 
toric compactification are 
described in sections \ref{sec:mom} and \ref{sub:embed}, and are formalized 
in definition \ref{dfn:shift} and lemma \ref{lemma:shift}. In particular, 
products of projective spaces are special cases of toric compacta. } 
Implicit in the grouping of variables chosen is an embedding $\Kn 
\hookrightarrow \Pro^{n_1}_K\!\times \cdots \times\!\Pro^{n_\lambda}_K$ and in 
this way we obtain an upper bound on $\cN_K(E;\Kn)$.

One can then try to group variables so that this method gives as tight
an upper bound on $\cN_K(E;\Kn)$ as possible, but the following example
shows that this bound can be very loose, no matter how one groups
variables.
\begin{ex}{\bf (Spiky Newton Polytopes)} Consider the indeterminate
polynomial system $F\!:=\!(c_{10}+c_{11}x^d_1+ c_{12}x_2+\cdots
+c_{1n}x_n,\ldots,c_{n0}+c_{n1}x^d_1+c_{n2}x_2+\cdots + c_{nn}x_n)$, where
$d\!\in\!\N$ and $n\geq 2$. Clearly, the Newton polytopes of $F$ are all
identical and equal to the ``spike''
$P\!:=\!\conv(\bO,d\hat{e}_1,\hat{e}_2,\ldots,\hat{e}_n)$. The Affine Point
Theorem II then tells us that $\cN_K(E;\Kn)=\cM(P,\ldots,P)=n!\V(P)=d$,
where $E$ is the support of $F$.

However, the usual B\'ezout Theorem tells us that $\cN_K(E;\Kn)\!\leq\!d^n$.
Can this be significantly improved by going to a multi-homogeneous version? 
The answer is ``yes, but not enough:'' the best one can do is
$\cN_K(E;\Kn)\!\leq\!nd$. This bound can be obtained by using two groups of
variables: $\{x_1\}$ and $\{x_2,\ldots,x_n\}$. That this is the best one
can do with any multihomogeneous version of B\'ezout's Theorem is most
easily proved geometrically: It is easy to see that computing the optimal
generalized B\'ezout bound is equivalent to finding a product of scaled
standard simplices, with smallest volume, which contains $P$. (This
reduction is described more explicitly, but in a different context, in
\cite{myaverage}.) 
\end{ex}

More generally, one can use Main Theorem 3 to determine when a particular
B\'ezout Theorem generically matches (or exceeds) a mixed volume root
count: One simply lets $E$ be the $n$-tuple of vertex sets of the
corresponding products of simplices, and lets $D$ be the $n$-tuple of
vertex sets of the Newton polytopes in question. {}From there, one checks
the corresponding {\em counting}\/ criterion (cf.\ definition 
\ref{dfn:count}). 

\subsection{Generic Local Intersection Multiplicity} 
\label{sub:mult}
Setting $W\!=\!\bO$ in
Main Theorem 1 we immediately obtain a method for computing the {\em
generic}\/ intersection multiplicity, at the origin, of a general sparse
system of $n$ polynomials in $n$ unknowns. An alternative general
algorithm, potentially more efficient in higher dimensions, is the special
case $J\!=\!\emptyset$ of Corollary \ref{cor:stable}. For example, if $F$
is a $2\!\times\!2$ polynomial system with {\em cornered}\/ support $E$, we
obtain from the Affine Point Theorem II that
$\mu(\bO;F)\!=\!\cN_K(E;\bO)\!=\!\cM(\bO\cup E)-\cM(E)$ for generic
$\cC_E$. This last formula already generalizes an earlier result of  
Warren \cite[Theorem 3]{warren} for the {\em unmixed}\/ case ($E_1\!=\!E_2$) 
over $\C$. 
% Arno'ld? Oda? 

However, it is important to note that $\cN_K(E;\bO)$ is {\em not}\/, in
general, an upper bound on intersection multiplicity at the origin: For 
example, it is 
easily verified that the polynomial system $(x+y^2,x+x^2+y^2)$ has an
isolated root at $\bO$ with multiplicity $4$. (One simply notes that this
system has no roots other than $\bO$ and concludes by B\'ezout's Theorem in
$\Pro^2_K$.) However, setting $E\!:=\!(\{(1,0),(0,2)\},\{(1,0),(2,0),
(0,2)\})$, our last paragraph implies that 
$\cN_K(E;\bO)\!=\!\cM(\bO\cup E)-\cM(E)\!=\!4-2\!=2$.
\begin{rem}
\label{rem:fulton}
More generally, if $F$ is an $n\!\times\!n$ polynomial system over $K$, 
then the intersection multiplicity $\mu(\zeta,F)$ of a zero-dimensional 
component $\zeta\!\in\!\Kn$ of $Z(F)$ can be defined as the dimension 
of the quotient ring $\{\frac{r(x)}{s(x)}\!\in\!K(x) \; | \; \gcd(r,s)\!=\!1, 
\; s(\zeta)\!\neq\!0\}/\langle F \rangle$ as a $K$-vector space 
\cite[Example 7.1.10 (b)]{ifulton2}. For the purposes of definition 
\ref{big}, we will set $\mu(\zeta,F)\!=\!+\infty$ when $\zeta$ lies 
in a {\em positive}-dimensional component of $Z(F)$. 
\end{rem}

\subsection{Our Main Theorems in Two Dimensions} 
\label{sub:mts}
Let $n\!=\!2$ and consider the following bivariate polynomial system: 
\begin{eqnarray*}
f_1(x,y) & := & \alpha_1 y^2 + \alpha_2 y^4 + \alpha_3 xy^5 + \alpha_4 x^2y^5 +
\alpha_5 x^2y^7 + \alpha_6 x^4y^8 \\
f_2(x,y) & := & \beta_1 x + \beta_2 x^2 + \beta_3 xy + \beta_4 x^2y +
\beta_5 x^6y^2 + \beta_6 x^6y^3 + \beta_7 x^7y^3 + \beta_8 x^9y^5 
\end{eqnarray*}
How do we get a tight upper bound on the number of isolated affine roots
of $F\!:=\!(f_1,f_2)$? One way is to set $E\!:=\!\supp(F)$ and apply the Affine
Point Theorem I \cite{rojaswang}. In which case we obtain that $F$ has no
more than $\cM(\bO\cup E)\!=\!53$ isolated roots. (It is also easily
verified that the best generalized B\'ezout bound is $(\deg_x f_1)(\deg_y
f_2)+(\deg_x f_2)(\deg_y f_1)\!=\!92$.) However, it is clear that $E$ is
nice for $K^2$ (by lemma \ref{lemma:wow} of the appendix) and not cornered, so 
let us see if Main Theorem 1 can do better. Figure \ref{fig:useful} below 
clarifies the preceding (and upcoming) calculations. 

%%%%
\begin{figure}[bth]
\begin{picture}(500,140)(-45,-10)

\put(0,0){
\begin{picture}(133,100)(0,0)
%% picture of the first support and Newton polygon
\put(18,29){$E_1$ ($\supseteq\!\supp(f_1)$)} 
\put(-10,0){\line(1,0){100}} \put(80,-7){$e_1$}
\put(0,-10){\line(0,1){100}} \put(-10,84){$e_2$}
\put(0,20){\circle*{3}} \put(2,19){$\alpha_1$}
 \put(0,20){\line(0,1){20}}
\put(0,40){\circle*{3}} \put(-12,40){$\alpha_2$}
 \put(0,40){\line(2,3){20}}
\put(10,50){\circle{3}} \put(5,44){$\alpha_3$}
\put(20,50){\circle{3}} \put(22,48){$\alpha_4$}
\put(20,70){\circle*{3}} \put(8,70){$\alpha_5$}
 \put(20,70){\line(2,1){20}}
\put(40,80){\circle{3}} \put(41,81){$\alpha_6$}
 \put(40,80){\line(-2,-3){40}}
\end{picture}}

\put(108,0){
\begin{picture}(133,100)(0,0)
% picture of the second support and Newton polygon
\put(3,45){$E_2$ ($\supseteq\!\supp(f_2)$)} 
\put(-10,0){\line(1,0){100}} \put(80,-7){$e_1$}
\put(0,-10){\line(0,1){100}} \put(-10,84){$e_2$}
\put(10,0){\circle{3}} \put(8,-9){$\beta_1$}
 \put(10,0){\line(0,1){10}} 
\put(20,0){\circle*{3}} \put(18,-9){$\beta_2$}
 \put(20,0){\line(2,1){40}}
\put(10,10){\circle*{3}} \put(5,14){$\beta_3$}
 \put(10,10){\line(2,1){80}}
\put(20,10){\circle{3}} \put(22,9){$\beta_4$}
\put(60,20){\circle{3}} \put(61,16){$\beta_5$}
 \put(60,20){\line(1,1){30}}
\put(60,30){\circle{3}} \put(51,24){$\beta_6$}
\put(70,30){\circle{3}} \put(72,27){$\beta_7$}
\put(90,50){\circle*{3}} \put(92,51){$\beta_8$}
\end{picture}}

\put(216,0){
\begin{picture}(133,100)(0,0)
% picture of the sum of the two supports, and its convex hull
\put(10,7){$S\!=\!\conv(E_1+E_2)$} 
\put(-10,0){\line(1,0){100}} \put(80,-7){$e_1$}
\put(0,-10){\line(0,1){100}} \put(-10,84){$e_2$}
\put(10,20){\circle{3}}
 \put(10,20){\line(1,0){10}}
\put(20,20){\circle{3}}
 \put(20,20){\line(2,1){40}}
\put(60,40){\circle{3}}
 \put(60,40){\line(1,1){30}}
\put(90,70){\circle{3}}
 \put(90,70){\line(2,3){40}}
\put(130,130){\circle{3}}
 \put(130,130){\line(-2,-1){100}}
\put(30,80){\circle{3}}
 \put(30,80){\line(-2,-3){20}} 
\put(10,50){\circle{3}}
 \put(10,50){\line(0,-1){30}} 
\put(110,120){\circle{3}} \put(110,110){\circle{3}} \put(110,100){\circle{3}}
\put(100,110){\circle{3}} \put(100,100){\circle{3}} \put(90,100){\circle{3}}
\put(90,90){\circle{3}} \put(80,100){\circle{3}} \put(90,80){\circle{3}}
\put(80,90){\circle{3}} \put(90,70){\circle{3}} \put(80,80){\circle{3}}
\put(80,70){\circle{3}} \put(70,80){\circle{3}} \put(60,90){\circle{3}}
\put(70,70){\circle{3}} \put(60,80){\circle{3}} \put(50,90){\circle{3}}
\put(60,70){\circle{3}} \put(50,80){\circle{3}} \put(70,50){\circle{3}}
\put(60,60){\circle{3}} \put(40,80){\circle{3}} \put(60,50){\circle{3}}
\put(40,70){\circle{3}} \put(30,80){\circle{3}} \put(60,40){\circle{3}}
\put(40,60){\circle{3}} \put(30,70){\circle{3}} \put(40,50){\circle{3}}
\put(30,60){\circle{3}} \put(30,50){\circle{3}} \put(20,60){\circle{3}}
\put(20,50){\circle{3}} \put(20,40){\circle{3}} \put(10,50){\circle{3}}
\put(20,30){\circle{3}} \put(10,40){\circle{3}} \put(20,20){\circle{3}}
\put(10,30){\circle{3}} \put(10,20){\circle{3}}
\dashline[50]{2}(10,30)(90,70)
\dashline[50]{2}(10,30)(50,90)
\end{picture}}

\end{picture} 

\caption{The sets $E_1$, $E_2$, and $E_1+E_2$, along with their underlying 
convex hulls. (The points of $E_1$ and $E_2$ are labelled according to their 
corresponding polynomial coefficients.) The subdivision of the Minkowski sum 
shows that, in this example, $\cM(E)$ can actually be expressed as a single 
determinant. } 
\label{fig:useful}

\end{figure}
%%% 

Following the notation of Main Theorem 1, we obtain 
$m_1\!=\!(0,2)$, and $m_2\!=\!(1,0)$. So Main Theorem 1 asserts that
\begin{eqnarray*}
\cN_K(E;K^2) & \!=\! & \cN_K(E_{\{1,2\}};K^2)+
\cN_K(\{\bO,(0,2)\},\{0\}\!\times\!K) + 
2\cN_K(\{\bO,(1,0)\},K\!\times\!\{0\}) + 2\cN_K(\emptyset,\bO)\\ 
& \!=\! & 32 + \cN_K(\{0,2\},K) + 2 \cN_K(\{0,1\},K) + 2. 
\end{eqnarray*}
(The last equality follows from the Affine Point Theorem II.) The remaining
unknown terms add up to $4$ (by the Affine Point Theorem II again, or simply
the fundamental theorem of algebra), so we finally obtain the tight upper 
bound $\cN_K(E;K^2)\!=\!38$. 

We can also give a precise algebraic condition for when this $F$ has {\em
exactly}\/ thirty eight affine roots, counting multiplicities. Applying
Main Theorem 2 (and figure \ref{fig:useful}) to our example,   
we see that the only $w$ we need worry about in condition (a$_2$) are (in 
counter-clockwise order) $(-1,2)$, $(-1,-1)$, $(-3,2)$, $(1,-2)$, and 
$(3,-2)$. Furthermore, the corresponding sparse resultants are easily seen to 
be $1$, $1$, $1$, $\alpha_5\beta_8-\alpha_6\beta_3$, and $1$. (The 
papers \cite{morea,chowprod,combiresult} and the book \cite{gkz94} 
contain some very nice examples of how to compute low-dimensional sparse
resultants.) Condition (b$_2$) then clearly specializes to two one-dimensional 
cases of condition (a$_2$). (More conservatively, the fundamental theorem of 
algebra could also be applied to (b$_2$).) So it is not hard to see that 
condition (b$_2$) is equivalent to $\alpha_2$ and $\beta_2$ being nonzero. 
Since each individual term of the summation from Main Theorem 1 was positive, 
we thus obtain that $F$ has exactly thirty eight affine roots, counting 
multiplicities, {\bf iff} 
$(\alpha_5\beta_8-\alpha_6\beta_3)\alpha_1\alpha_2\beta_2\beta_3
\beta_8\!\neq\!0$.

Similarly, by Main Theorem 3 (and making use of figures 
\ref{fig:useful} and \ref{fig:myfirst} (cf.\ the appendix)) we obtain that the 
genericity of $\cC_D$ implies $F$ has exactly thirty eight affine roots 
(counting multiplicities) $\Longleftrightarrow \cC_D$ contains at least one 
coefficient from {\em each}\/ of the following sets: 
$\{\alpha_1,\beta_2\}$, $\{\alpha_1\}$,
$\{\alpha_1,\beta_5\}$, $\{\alpha_1\}$, $\{\alpha_8\}$,
$\{\alpha_6,\beta_8\}$, $\{\alpha_5,\alpha_6\}$,$\{\beta_3,\beta_8\}$,
$\{\alpha_5,\beta_3\}$, $\{\beta_3\}$, and $\{\alpha_2,\beta_3\}$ (in 
counter-clockwise order, from condition (a$_3$)); and $\{\alpha_2\}$ and
$\{\beta_2\}$ (from condition (b$_3$)). For example, 
regardless of how the other eight coefficients have been
specialized, it suffices to choose the vector 
$(\alpha_1,\alpha_2,\alpha_5,\beta_2,\beta_3, \beta_8)\!\in\!K^6$ 
generically for $F$ to have exactly thirty eight roots (counting
multiplicities). In other words, $D$ $K^2$-counts $E$, where 
$D=(\{(0,2),(0,4),(2,7)\},\{(2,0),(1,1),(9,5)\})$. The dark points 
in figure \ref{fig:useful} represent $D$.

\section{Background and Terminology}
Aside from a few variations, we will follow the same notation as
\cite{convexapp,isawres,rojaswang,hsaff,dynamiclift}. In those papers one
can also find some of the definitions below described at a more leisurely
pace. We will also liberally quote, e.g., from
\cite{grunbaum,algeom,sha,clo,schneider}, various simple facts from
convex and algebraic geometry that we will use. However, for the
convenience of the reader, we will review a few notions.

For any $q_1,\ldots,q_n\!\in\!\Rn$, let $[q_1,\ldots,q_n]$ denote the
$n\!\times\!n$ matrix whose $i^\thth$ column is $q_i$. It will be useful to
recall the following facts concerning the Smith normal form of an
integral matrix \cite[Chap.\ 3.7]{jacobson1} 
\begin{propdfn}
\label{prop:sln}
\cite{unimod1,unimod2}
An {\em integral basis}\/ for $\Rn$ is a vector space basis for $\Rn$ which
is also a $\Z$-module basis for $\Zn$. Equivalently, a basis
$\{u_1,\ldots,u_n\}$ for $\Rn$ is integral iff
$[u_1,\ldots,u_n]\!\in\!\glnz$. Such a basis {\em respects}\/ a rational
subspace $L$ of $\Rn$ iff $\{u_1,\ldots,u_{\dim L}\}$ is a $\Z$-module
basis for $L\!\cap\!\Zn$. Furthermore, given any rational bases for $L$ and
a complementary subspace, an integral basis for $\Rn$ respecting $L$ can be
found within $O(n^{11})$ arithmetic operations. \qed 
\end{propdfn}
Defining $x^\cU\!:=\!(x^{u_{11}}_1\cdots
x^{u_{n1}}_n,\ldots,x^{u_{1n}}_1\cdots x^{u_{nn}}_n)$ for any
$n\!\times\!n$ matrix $\cU\!:=\![u_{ij}]$ with integer entries, we then see
that the above proposition tells us how we can find a {\em monomial}\/ change 
of variables which converts a polynomial into a form involving as few
variables as possible.

We will use $\supp(f)$ and $\newt(f)$ for, respectively, the support and
Newton polytope (the convex hull of $\supp(f)$) of any $f\!\in\!K'[x^{\pm
1}_1,\ldots,x^{\pm 1}_n]$, where $K'\!:=\!K[\Lambda]$ and $\Lambda$ is any set 
of algebraically independent indeterminates. 
\begin{dfn}
For any {\em weight} $w\!\in\!\Rn$ the {\em initial term
polynomial} $\init_w(f)(x)$ is $\sum_{e \in \supp(f)^w} c_e x^e$. More
generally, if $B\!\supseteq\!\supp(f)$, we define the {\em relativized}
initial term polynomial $\init_{w,B}(f)(x)\!:=\! \sum_{e \in B^w \cap
\supp(f)} c_e x^e$. Also, any $c_e$ with $e$ on the boundary of $\newt(f)$
is called a {\em boundary coefficient} of $f$. 
\end{dfn}
\noindent
Alternatively, when $w\!\in\!\Zn$, we can simply substitute $x \mapsto t^w
x\!:=\!(t^{w_1}x_1,\ldots,t^{w_n}x_n)$ into $f$ and define $\init_w(f)$ as
the coefficient of the term of {\em lowest}\/ degree in $t$.

More generally, for any $k\times n$ polynomial system $F$ (with constant
or indeterminate coefficients), we define the {\em initial term system}\/
$\init_w(F)$ to be $(\init_w(f_1),\ldots,\init_w(f_k))$. Also, if a 
$k$-tuple $C\!:=\!(C_1,\ldots,C_k)$ satisfies $C_i \! \supseteq \!
\supp(f_i)$ for all $i\!\in\![1..k]$, then we say that $C$ {\em contains the 
support of $F$}\/ and we define the {\em relativized}\/ initial term system
$\init_{w,C}(F)$ to be $(\init_{w,C_1}(f_1),\ldots,\init_{w,C_k}(f_k))$. An
especially important property of initial term systems is the following.
\begin{prop}
\cite{convexapp}
\label{prop:over}
Suppose $F$ is an $n\!\times\!n$ indeterminate polynomial system with support 
$E\!=\!(E_1,\ldots,E_n)$. In particular, we assume that each $E_i$ is nonempty. 
Then for generic $\cC_E$ and any $w\!\neq\!\bO$, the polynomial system 
$\init_{w,C}(F)$ has {\em no} roots in $\Ksn$. \qed 
\end{prop}
\noindent
Note that for any polynomial system $F$ with support contained in $C$, the
set $\{\init_{w,C}(F) \; | \;
w \!\in\! \Sn \}$ is finite: When $\supp(f_i)\!=\!C_i$ for all $i$, we can 
construct a bijection between the set of initial term systems and the face 
lattice of $\conv(\sum C_i)$, simply by picking a single inner normal $w$ for 
each face.

There is a rich interplay between
the combinatorial geometric structure of $\newt(f)$ and the topology of the
zero set of $f$ and we will see again (in section \ref{sec:mom} and beyond)
that initial term polynomials are extremely valuable in this respect.

\subsection{Algebraic Geometry}
\label{sub:algebraic}
As usual, we will let $Z(F)$ denote the zero scheme of $F$ in $\Kn$. We
will make some use of algebraic cycles (e.g., finite formal
$\Z$-linear combinations of closed subvarieties of some toric variety),
rational equivalence, and intersection theory, so let us also recall the
following facts and definitions \cite{algeom,sha,ifulton1,ifulton2,tfulton}: 

\begin{enumerate}
\item{For any cycle $\cA$, $\supp(\cA)$ is the union of all
closed subvarieties $V$ such that the coefficient of $V$ within $\cA$ is
nonzero. Also, a divisor is said to be {\em effective}\/ iff all its
coefficients are nonnegative. }
\item{There is a natural intersection product ``$\cap$'' on the group
of all cycles on a variety $\cX$ giving this group a (commutative) ring
structure called the {\em Chow ring}\/ of $\cX$, $\chow(\cX)$. This product
is also compatible with {\em rational equivalence} 
\cite[pp.\ 10, 15--17]{ifulton2}.}
\item{A {\em $0$-cycle}\/ on $\cX$ is a cycle of the form
$\cD\!=\!\sum n_\zeta \{\zeta\}$ where each $\zeta$ is a point and 
$n_\zeta\!\in\!\Z$. When $\cX$ is complete, the homorphism from the group of 
$0$-cycles on $\cX$ to 
$\Z$ defined by $\sum n_\zeta \{\zeta\}\mapsto\sum n_\zeta$ is invariant under 
rational equivalence and is called the {\em degree map}, $\deg(\cdot)$. } 

\item{Any intersection, $\cD$, of $\dim \cX$ many divisors in $\chow(\cX)$ 
is rationally equivalent to some $0$-cycle, and thus has a well-defined ({\em
cycle class}\/) degree. Furthermore, if each divisor is effective, the
coefficient of any zero-dimensional component $\zeta$ of such an
intersection is its {\em intersection multiplicity}, or {\em intersection
number}, $\mu(\zeta;\cD)$ \cite[Example 7.1.10 (b)]{ifulton2}.} 

\end{enumerate}

The most advanced prerequisites we will require from algebraic geometry
will be the belief in certain theorems dealing with divisor intersections
on toric varieties. Good general references are \cite{dannie,oda,ifulton2,
tfulton}. The toric variety facts we'll need are covered in the next
section so we now state the main intersection theoretic result we'll use.

\begin{thm}
\label{thm:intersect} \cite[Theorem 12.2]{ifulton2} Suppose $\cT$ is a
complete $n$-dimensional variety over an algebraically closed field, and
$\cD_1,\ldots,\cD_n$ are effective Cartier divisors such that each line
bundle $\cO(\cD_i)$ is generated by its sections. Also let $\cD$ denote the
intersection product of these divisors in $\chow(\cT)$. Then the
intersection number of any distinguished component of $\cD$ is nonnegative.
Furthermore, if we let $\cI$ denote the sum of the intersection numbers of
the distinguished components of $\cD$, then \[\cI\!\leq\!\deg \cD,\] and
equality holds if $\cD$ is zero-dimensional or empty. \qed
\end{thm}
\begin{rem}
See \cite{ifulton2} for the definition of a distinguished component. For
our purposes, suffice it to say that a zero-dimensional irreducible component 
is a distinguished component, and the converse holds as well when $\cD$ is
zero-dimensional or empty. Also, embedded \cite[pg.\ 90]{eisenbud} 
zero-dimensional components are distinguished components. 
\end{rem}
\noindent
Precise conditions for equality in the above inequality are subtle and
difficult to find in the literature. However, we conjecture that equality
always holds in the cases where we will apply this theorem. This has
already been verified in a particular case, giving a refinement of
B\'ezout's Theorem over $\C$ \cite{mikebezout}.


\subsection{Toric Varieties}
\label{sub:toric}
We will assume the reader to be familiar with fans and the
construction of toric varieties from fans and polytopes. Excellent
references are \cite{kkms,dannie,oda,tfulton,gkz94,grobandpoly}.

Let $T\!:=\!\Ksn$, which is sometimes called the {\em algebraic torus}.

\begin{dfn}
\label{dfn:polyfan}
Let $P\!\subset\!\Rn$ be an $n$-dimensional rational polytope. We will
associate to $P$ its {\em (inner) normal fan} $\fan(P)$ as follows: The rays of
this fan are generated by the inner facet normals of $P$, and to each (not
necessarily proper) face $P^w$ of $P$ we associate the cone $\sigma_w$
generated by the rays corresponding to the facets containing $P^w$. Each
$\sigma_w$ is also called a {\em (inner) normal cone} of $P$. 
\end{dfn}
\noindent
It is useful to think of the {\em duals} of the cones of $\fan(P)$ as
``angle'' cones. In fact, it easy to show that for any $w$ there is a small
ball $B\!\subset\!\Rn$, centered at the origin, such that
$B\cap\sigma^\vee_w\!=\!B\cap (P-v)$, for some $v\!\in\!\relint P^w$.

We will be working with the following class of toric varieties. 
\begin{dfn}
Following the notation of definition \ref{dfn:polyfan}, we will let $\cT_P$
be the toric variety over $K$ corresponding to the normal fan of $P$. We
call $\cT_P$ the {\em toric compactification} of $T$ corresponding to $P$.
\end{dfn}
It follows that $\cT_P$ is $n$-dimensional, rational, projective, normal,
integral, separated, and complete \cite{tfulton}. The toric variety $\cT_P$
also has a naturally embedded copy of $T$ (cf.\ theorem \ref{thm:orbit}). For 
certain $P$ the toric variety $\cT_P$ is also nonsingular but we will not need 
this fact. 
We will also say that any point of $\cT_P\!\setminus\!\Ksn$ is {\em at 
infinity} and sometimes refer to $\cT_P\!\setminus\!\Ksn$ as {\em toric 
infinity}. Since our polynomial systems will have a priori specified supports, 
$F$ will usually have far fewer extraneous roots in an appropriately chosen 
$\cT_P$ than in $\Pro^n_K$. Hence toric compactifications are the spaces where 
we will actually be counting roots of polynomial systems. Toward this end, it
will be useful to recall the correspondence between the topology of $\cT_P$  
and the face structure of $P$. However, we will need a little more 
notation before stating this correspondence as a theorem.
\begin{dfn}
\label{dfn:toric}
Given any $w\!\in\!\Rn$, we will use the following notation: 
\begin{itemize}
\item[$U_w=$]{$\spec(K[x^e \; | \; e\!\in\!\sigma^\vee_w\cap\Zn])=$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 the
face $P^w$ of $P$} 
\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[$V_w=$]{The closure of $O_w$ in $\cT_P$} 
\item[$p_w=$]{The first integral point {\em not} equal to $\bO$ met along the 
ray generated by $w$ (when $w\!\in\!\Qns$) } 
\end{itemize}
\end{dfn}
\noindent
Note that $L_w$ is a face of the cone $\sigma_w^\vee$ so $x_w$ is indeed
well-defined. Also, recalling that a closed point in an affine toric
variety can be identified with a semigroup homomorphism \cite[Chap.\
1.3]{tfulton}, it is clear that any point $x\!\in\!O_w$ is completely
determined by $w$ and the (nonzero) values of $x(\cdot)$ on any $\Z$-module
basis of $L_w\cap \Zn$. Note that our characterization of $x_w$ is a
slight variation of that of \cite{tfulton} but is easily seen to be
equivalent. In particular, our $x_w$ is the same as Fulton's $x_\sigma$
when $\sigma\!=\!\sigma_w$.
\begin{ex} {\bf (Certain Cornered Polytopes)} Suppose $P$ is an $n$-dimensional
rational polytope with a vertex ${\mathrm v}$ such that the edges
emanating from ${\mathrm v}$ generate the nonnegative orthant as a cone.
Suppose further that the coordinates of $w$ are all {\em non}\/negative.
Then $O_w\!\cong\!O_J$, where $J\!=\!\supp(w)^c$. In
particular, we see that $\dim P^w=\dim O_w=n-|\supp(w)|$ and $\dim \sigma_w
= |\supp(w)|$. Note that here $x_w$ is the 0-1 vector with support
$\supp(w)^c$. Furthermore, $U_{(1,\ldots,1)}\!\cong\!\Kn$ 
so we can thus conclude that $\Kn$ embeds naturally within such a $\cT_P$.
This example will be especially important in our approach to affine root
counting. 
\end{ex}
\begin{ex}
\label{ex:basic}
Suppose $w,w'\!\in\!\Rn$. Then, relative to $\cT_P$, the defining ideal
$I_{w'}\!\subset\!K[x^e \; | \; e \in \sigma^\vee_w \cap \Zn]$ of $V_{w'}
\cap U_w \subset U_w$ is $K[x^e \; | \; e\in
\!(\sigma^\vee_w\!\setminus\!L_{w'})\!\cap\!\Zn]$. 
\end{ex}

With our orbit notation in place, we can now state the following important
result.
\begin{thm}
\label{thm:orbit}
\cite[Chap.\ 3.1]{tfulton} 
The toric variety $\cT_P$ is the disjoint union $\coprod O_w$, where a
single inner normal $w$ is chosen for each (not necessarily proper) face of
$P$. Also, for all $w\in \Rn$,
\begin{enumerate}
\item{$\dim O_w = \dim V_w = \dim P^w$}
\item{$U_w=\coprod O_v$, where a single inner normal $v$ is chosen for each
(not necessarily proper) face containing $P^w$. In particular, $U_w$ is
always an $n$-dimensional open subvariety of $\cT_P$. }
\item{$O_w\!=\!\spec(K[x^e \; | \;
e\!\in\!L_w\!\cap\!\Zn])\!\cong\!(\Ks)^{\dim P^w}$.} 
\item{If $d\!=\!\dim
P^w$ then $V_w$ is isomorphic to any toric compactification of $(\Ks)^d$
corresponding to a polytope $Q\subset\R^d \subseteq\Rn$ which is
$\glnz$-similar to a translate of $P^w$. \qed}
\end{enumerate}
\end{thm}
\noindent 
In particular, there is an order-preserving correspondence 
between the faces (resp.\ face interiors) of $P$ and the 
orbit closures (resp.\ orbits) of $\cT_P$. Also, there is an 
order-{\em reversing}\/ correspondence between the affine 
charts of $\cT_P$ and the faces of $P$. The above result 
is also contained in \cite{ksz92,gkz94} but in the setting 
where $\cT_P$ is defined via an explicit projective embedding.  

Since toric compactifications will be the spaces in which we analyze the
roots of $F$, it will be useful to embed the support of $F$ within an
$n$-tuple of nonempty integral polytopes $\cP\!:=\!(P_1,\ldots,P_n)$ and 
define $P$ as a function of $\cP$.
We can then consider the roots of $F$ within $\cT_P$ as follows: Each
(nonzero) polynomial $f_i$ defines a Weil divisor $\divisor(f_i)$ in
$\cT_P$ \cite[Chap.\ 3.3]{tfulton}. The closure (in $\cT_P$) of the zero
scheme of $f_i$ in $\Ksn$ is a summand of $\divisor(f_i)$ and is the
portion of $\divisor(f_i)$ we are actually interested in. To isolate this
portion of $\divisor(f_i)$ we will add another specially defined divisor
(depending on $P$ and $P_i$) to $\divisor(f_i)$. This will cancel out the
negative part of $\divisor(f_i)$ but sometimes introduce extraneous
components. In any case, the zero scheme of $F$ in $\Ksn$ is thus embedded
in an intersection of effective divisors in $\cT_P$. In section
\ref{sub:chow} we will show
how to eliminate some of these extra components, modify $P$ so that  
$\cT_P$ has a naturally embedded copy of $\Kni$, and thus derive our method
for affine root counting. The construction of our divisors is detailed in
the next section. 

\section{The Importance of Roots at Toric Infinity} 
\label{sec:mom}
Here we point out two, more or less folkloric results on toric divisors.
Combined with the Antipodality Theorem \cite{aff}, these two results 
considerably simplify the proof of our toric compactification version 
(theorem \ref{thm:toric} in the next subsection) of the BKK bound 
\cite{bernie}. 

First we give the following definition to help us find the right $\cT_P$,
and the right divisor to add to $\divisor(f_i)$, for our root counting
theory to go through.
\begin{dfn}
\label{dfn:impo1}
Let $Q\!\subset\!\Rn$ be an {\em integral} polytope. We will say that a fan
$\cF$ is {\em compatible}\/ with $Q$ iff every normal cone of $Q$ is a
union of cones of $\cF$. We will also say that a {\em rational} polytope
$P\!\subset\!\Rn$ is {\em compatible} with $Q$ iff $\fan(P)$ is compatible 
with $Q$. Also, following the notation of definition \ref{dfn:toric}, we 
define the integer $\gamma_w(Q)\!:=\!-\min
\limits_{v\in Q} \{ v\!\cdot\! p_w\}$ for any $w\!\in\!\Qns$. 
\end{dfn}
\begin{ex}
\label{ex:compat}
It is easily shown that $\sum P_i$ is always compatible with $P_1,\ldots,P_n$. 
Compatibility was applied earlier in \cite{khocompat,tfulton} and the
terminology ``sufficiently fine decomposition'' was used in the first
reference. 
\end{ex}

Next we describe precisely which divisors we will be intersecting. 
\begin{dfn}
\label{dfn:impo2}
Assuming $P\!\subset\!\Rn$ is a rational polytope compatible with 
an integral polytope $Q\!\subset\!\Rn$, let $\cE_P(Q)\!:=\!\sum 
\gamma_{w}(Q) V_w$, where $w$
ranges over all the inner facet normals of $P$. We call $\cE_P(Q)$ {\em the
torus-invariant divisor of $\cT_P$ corresponding to $Q$.} Also, 
set $\cD_P(0,Q)\!:=\!\cT_P$ and, for any polynomial $f$ with 
$\emptyset\!\neq\!\supp(f)\!\subseteq\!Q$, define 
$\cD_P(f,Q)\!:=\!\divisor(f)+\cE_P(Q)$. 
\end{dfn}
\noindent
It follows by definition that $\cD_P(f,Q)$ is always effective
\cite{tfulton} and invariant under translations of $P$ and identical
translations of $Q$ and $f$. This turns out to be good for root counting in
$\Ksn$ but bad for root counting in $\Kn$. Hence we will modify the
definition of $\cD_P(f,Q)$ in section \ref{sub:chow}. 
\begin{dfn}
\label{dfn:intersect} 
Suppose $F\!=\!(f_1,\ldots,f_k)$ is a $k\!\times\!n$ polynomial system
over $K$ with support contained in a $k$-tuple of nonempty integral polytopes
$\cP\!=\!(P_1,\ldots,P_k)$. Then $P\!\subset\!\Rn$ is {\em compatible} 
with $\cP \Longleftrightarrow P$ is compatible with $P_1,\ldots,P_k$. 
Furthermore, when this is the case, we define $\cD_P(F,\cP)$ to be the 
intersection product $\bigcap^k_{i=1} \cD_P(f_i,P_i)\!\in\!\chow(\cT_P)$. 
\end{dfn}
It is easy to see that even as schemes 
$\Ksn\cap Z(F)\!=\!\Ksn\cap\cD_P(F,\cP)$ when $\dim P\!=\!n$. 
Also note that $\cD_P(f,Q)$ is precisely the closure $\overline{\Ksn\cap
Z(f)}$ in $\cT_P$ if $\newt(f)\!=\!Q$ and $\dim P\!=\!n$. 
By our last observation, we could just set $P_i\!:=\!\newt(f_i)$ for 
all $i$ in the construction of $\cD_P(F,\cP)$ in order 
to work directly with $\overline{\Ksn\cap Z(F)}$. However, this is not always
advantageous computationally and it actually behooves us to fully
understand the cases where $\newt(f_i)$ is not compatible with $P$ or
$\newt(f_i)\!\neq\!P_i$. One reason is that for precise {\em sparse}\/
affine root counting, it is necessary to know precisely what happens to 
$\divisor(f_i)$ as lots of coefficients of $F$ are specialized to $0$.

So let us now find explicitly the behavior of $\cD_P(F,\cP)$ within a
neighborhood of toric infinity. The following lemma, which is a direct
consequence of the development followed in \cite{tfulton} or \cite{gkz94}, 
shows us that $U_w\cap\cD_P(F,\cP)$ can be described by a relatively simple 
ideal.
\begin{lemma}
\label{lemma:once}
Let $w\!\in\!\Rn$. Then, following the notation of definitions \ref{dfn:toric} 
and \ref{dfn:intersect}, 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_1}f_1,\ldots,x^{b_k}f_k \rangle$, for any 
$b_1,\ldots,b_k\!\in\!\Zn$ such that $b_i+P^w_i\subseteq L_w$ for all 
$i\!\in\![1..k]$. 
\qed 
\end{lemma}
\noindent
Should one be so inclined, the intersection multiplicity of a component of
$\cD_P(F,\cP)$ can be computed by restricting to an appropriate chart $U_w$ 
and this lemma gives one an explicit coordinate ring to work in.

The following is a more computational version of the above lemma and is
easily proved by localization.
\begin{cor}
\label{cor:cool}
Following the notation of lemma \ref{lemma:once}, the underlying
topological spaces of
$O_w\cap\cD_P(F,\cP)$ and
\[\spec(K[x^e \; | \; e\in L_w\cap \Zn] / \langle \init_{w,b_1+P_1}(x^{b_1}
f_1),\ldots,\init_{w,b_k+P_k}(x^{b_k} f_k) \rangle)\]
are homeomorphic.

In particular, if $\{u_1,\ldots,u_n\}\!\subseteq\!L_w\cap \Zn$ is a
generating set, then the map defined by $x \mapsto (x(u_1),\ldots,x(u_n))$
is an isomorphism from $O_w$ onto a subvariety of $\Ksn$, and
$[z\!\in\!O_w\cap\cD_P(F,\cP) \Longleftrightarrow \init_{w,\cP}(F)$ 
vanishes at the point $(z(u_1),\ldots,z(u_n))]$. \qed 
\end{cor}

It is a frequent misconception that the last equivalence should begin with
$z\!\in\!O_w\cap\overline{\Ksn\cap Z(F)}$. This is false unless, for
instance, $P_i\!=\!\newt(f_i)$ for all $i$. (A simple counterexample is
$(n,P,f,w)\!:=\!(1,[0,2],x^2+x,1)$.)
Also, it is extremely important to note that the intersection multiplicity
of a component of $\cD_P(F,\cP)$ lying in $O_w$ can {\em not}\/ always be 
determined by this corollary when $w\!\neq\!\bO$. (Simply observe the 
case $P_1\!=\!P_2\!=\!P\!=\!3\conv\{\bO,\hat{e}_1,\hat{e}_2\}$,
$F\!=\!(x^3_1-x^2_1,x^3_2-x^2_2)$, and $w\!:=\!(1,1)$.) Thus there is a loss 
of information as we intersect with $O_w$ and pass from $F$ to its initial 
term systems.

The last two results thus tell us that the relativized initial term systems
$\init_{w,\cP}(F)$ (for $w\!\neq\!\bO$) describe the topological behavior
of a particular divisor intersection (canonically defined by $F$, $\cP$, 
and $P$) at a piece of toric infinity. This generalizes the classical 
construction of how the terms of highest total degree depict the closure of 
the zero scheme of $F$ at the projective hyperplane at infinity.

Our toric variety $\cT_P$ also gives us an interesting way to detect 
excess components in the zero set of $F$ in $\Ksn$. 
\begin{anti} \cite{aff}
Suppose $P\!\subset\!\Rn$ is an $n$-dimensional rational polytope, $Y$ is a
curve in $\Ksn$, and $\overline{Y}$ is the closure of $Y$ in $\cT_P$. Also,
identify $\{O_w\!\subset\!\cT_P \; | \; w\!\neq\!\bO\}$ with a partition of
$\Sn$ into {\em cells} by letting $w$ and $w'$ in $\Sn$ belong to the same
cell iff $O_w\!=\!O_{w'}$. Then
\begin{enumerate}
\item{$\overline{Y}$ must touch two (possibly identical) cells whose union
does not lie in any closed coordinate hemisphere. } 
\item{If $\overline{Y}$ touches a cell intersecting some open hemisphere $\cH$
then it must also touch a cell intersecting $\Sn\!\setminus\!\cH$. }
\end{enumerate}
Furthermore, $\overline{Y}$ must touch at least two topologically separated
cells. \qed
\end{anti}
\begin{rem}
The cells described above are in fact stereographic images of the facets of 
the dual (or polar) of $P$. 
\end{rem}

\subsection{A Toric Variety Version of Bernshtein's Theorem} \label{sub:tv}
Before stating our generalization of Bernshtein's Theorem, we point out a
very useful immediate corollary of the Antipodality Theorem and corollary 
\ref{cor:cool}. 
\begin{cor}
\label{cor:crux}
Following the notation of corollary \ref{cor:cool}, $\cD_P(F,\cP)$ has positive
dimension $\Longrightarrow \init_{w,\cP}(F)$ has a root in $\Ksn$ for some
$w\!\neq\!\bO$. \qed
\end{cor}
\noindent
D. N. Bernshtein proved the case of corollary \ref{cor:crux} where
$\Ksn\cap\cD_P(F,\cP)$ is positive-dimensional and $K\!=\!\C$ \cite{bernie}. 
His proof used an ingenious Puiseux series construction, but unfortunately
Puiseux series expansions are not always defined for algebraic curves over
a field of {\em positive}\/ characteristic. Hence our need for antipodality
theorems.

By combining the following lemma
with theorem \ref{thm:intersect}, we see that working within $\cT_P$ allows
us to reduce the computation of intersection numbers (generically) to the
evaluation of a mixed volume.

\begin{lemma}
\label{lemma:cartier} \cite[Chap.\ 5.4]{tfulton} Following the notation of
definitions \ref{dfn:impo2} and \ref{dfn:intersect}, the cycle class degree of 
$\cE_P(P_1) \cap \cdots \cap \cE_P(P_n) \in \chow(\cT_P)$ is precisely 
$\cM(E)$. Furthermore, for all $i$, the line bundle $\cO(\cD_P(f_i,P_i))$ is 
generated by its
sections. \qed 
\end{lemma}

Putting all our machinery together, we can derive the following toric
variety version of the BKK bound.
\begin{thm}
\label{thm:toric}
Suppose $F$ is an $n\!\times\!n$ polynomial system over $K$ with support
contained in an $n$-tuple $\cP$ of nonempty integral 
polytopes in $\Rn$. Further suppose that $P\!\subset\!\Rn$ is an 
$n$-dimensional rational polytope compatible with $\cP$. Then the 
zero scheme of $F$ in $\Ksn$ embeds naturally as a subscheme of the toric 
cycle $\cD_P(F,\cP)$ and:  
\begin{enumerate}
\item{If $\cD_P(F,\cP)$ is zero-dimensional or empty then $\cD(F,\cP)$ 
consists of exactly $\cM(\cP)$ points, counting multiplicities.} 
\item{If $\cD_P(F,\cP)$ is
positive-dimensional and $\cM(\cP)\!=\!0$ then $\cD_P(F,\cP)$ has {\em no}
zero-dimensional irreducible components in $\cT_P$.} 
\item{If $\cD_P(F,\cP)$ is positive-dimensional and $\cM(\cP)\!>\!0$ then 
$\cD_P(F,\cP)$ has strictly less than
$\cM(\cP)$ zero-dimensional irreducible components in $\cT_P$, counting
multiplicities.}
\end{enumerate}
\end{thm}
\begin{rem}
Assertion (3) appears to be new for the case $\ch K\!\neq\!0$.
The case $(K,P_1,\ldots,P_n)\!=\!(\C,\newt(f_1),\ldots, \newt(f_n))$ first
appeared in \cite{bernie} and was stated as a root count over $\Csn$
instead of $\cT_P$. Assertions (1) and (2) (over a general algebraically 
closed field) then appeared implicitly in \cite{dannie}, but this was not as 
well known as it should have been. 
\end{rem}
\noindent
{\bf Proof:} That $\Ksn\cap Z(F)$ embeds as a subscheme of $\cD_P(F,\cP)$ 
follows immediately from our previous observations regarding definitions 
\ref{dfn:impo2} and \ref{dfn:intersect}. 

Assertion (1) then follows 
immediately from theorem \ref{thm:intersect} and lemma \ref{lemma:cartier} 
since $\cD_P(f_i,P_i)$ and $\cE_P(P_i)$ are rationally equivalent. Assertion 
(2) follows similarly since the intersection multiplicity of a zero-dimensional 
irreducible component of $\cD_P(F,\cP)$ is positive \cite{ifulton2}. Fulton 
stated this concise argument in \cite{tfulton} for the 
case $K\!=\!\C$ and his proof has the added benefit that it is independent of 
the (algebraically closed) field where one is working.

For the last assertion (3) we will generalize a novel homotopy proof due to
D. N. Bernshtein \cite{bernie}. First note that if any $f_i$ is identically
zero then there can be no zero-dimensional components and we are done. Thus
we may assume that no $f_i$ is identically zero. Our generalization of
Bernshtein's argument can then be outlined as follows: 
\begin{itemize}
\item[(i)]{Pick a point $y\!\in\!O_w$, for some $w\!\in\!\Rns$, which lies in
a positive-dimensional component of $\cD_P(F,\cP)$.} 
\item[(ii)]{Construct a generic polynomial system $G$ with $n$-tuple of
Newton polytopes $\cP$ and distinguished root $z\!\in\!\Ksn$ such that
$F(z)\!\neq\!\bO$.}
\item[(iii)]{Construct a rational algebraic curve
$L\!\subset\!\cT_P\!\times\!\Pro^1_K$
with parameterization $\overline{l} : \Pro^1_K \longleftrightarrow L$ such
that $\overline{l}(0)\!=\!y$ and $\overline{l}(1)\!=\!z$.} 
\item[(iv)]{For all $i\!\in\![1..n]$, define
$h_i(x,t)\!\in\!K[t,x^{\pm 1}_1,\ldots,x^{\pm 1}_n]$ to be the polynomial
obtained by clearing denominators from the reduced form of the rational
function
$f_i(x)g_i(\overline{l}(t))-g_i(x)f_i(\overline{l}(t))$. Show that
$h_i(x,0)$ (resp.\ $h_i(x,1)$) is a nonzero scalar multiple of $f_i(x)$
(resp.\ $g_i(x)$). }
\item[(v)]{Let $H(x,t)\!:=\!(h_1(x,t),\ldots,h_n(x,t))$ and consider the
subscheme $Z\!:=\!\overline{(\Ksn\!\times\!K)\cap Z(H)}$ of
$\cT_P\!\times\!\Pro^1_K$. Show that $\cD_P(F,\cP)\cong
(\cT_P\!\times\!\{0\})\cap Z$. }
\item[(vi)]{Show that the natural $(n+1)^\st$ coordinate projection defined
on $\Ksn\!\times\!K$ extends to a proper morphism $\pi : 
\cT_P\!\times\!\Pro^1_K \longrightarrow \Pro^1_K$ with
$\pi(L)\!=\!\Pro^1_K$. }
\item[(vii)]{Define $\cY$ to be the union of all $1$-dimensional irreducible
components of $Z$ with surjective image under $\pi$. Show that the support
of the zero-dimensional part of $\cD_P(F,\cP)$ is contained in
$\supp((\cT_P\!\times\!\{0\})\cap \cY)$. } 
\item[(viii)]{Show that $\cY\!\cap\!(\cT_P\!\times\!\{0\})$ consists of exactly
$\cM(\cP)$ points, counting multiplicities. } 
\end{itemize}
Assuming the above steps, (3) then follows immediately since $y\!\in\!L$,
$L\!\subseteq\!\cY$, and thus
$y\!\in\!\supp(\cY\!\cap\!(\cT_P\!\times\!\{0\}))$, i.e., the
zero-dimensional part of $\cD_P(F,\cP)$ consists of strictly fewer than 
$\cM(\cP)$ points, counting multiplicities.

To complete our proof, we now proceed to prove each individual step.

\noindent
{\bf (i):} Easy, by the Antipodality Theorem.

\noindent
{\bf (ii):} By generic we will
specifically mean that $f_1,\ldots,f_n$ are all nonzero at all roots of $G$
in $\Ksn$ and that $G$ has exactly $\cM(\cP)$ roots in $\Ksn$ (counting
multiplicities). That such $G$ occur generically follows easily from
proposition \ref{prop:over}, corollary \ref{cor:crux}, assertion (1) (which
we've already proved), and the fact that the intersection of any two
generic conditions is again a generic condition.

\noindent
{\bf (iii):} We will first construct the parameterization $\overline{l}$
and then the corresponding complete curve $L$.

Since $y$ is completely determined by the (nonzero) values of $y(\cdot)$ on
any $\Z$-module basis of $L_w\cap\Zn$, let $\{u_1,\ldots,u_n\}$ be any
basis for $\Zn$ respecting $L_w\!\cap\!\Zn$. (Such a basis is guaranteed to
exist by proposition \ref{prop:sln}.) Let $\cU\!:=\![u_1,\ldots,u_n]$ and
$[v_1,\ldots,v_n]\!:=\!\cV\!:=\!\cU^{-1}$. By assumption $\cU\!\in\!\glnz$
so clearly $\cV\!\in\!\glnz$. Now let $l : \Ks \longrightarrow \Ksn$ be the
following parameterization of a toric line: \[ ((1-t)y^\cU + t z^\cU)^\cV
\]
where, quite naturally, $y^\cU\!:=\!(y(u_1),\ldots,y(u_n))$ and $t$ is a
new variable. Then it is easily verified that $l(1)\!=\!z$ (via the general
identity $(x^A)^B\!=\!x^{AB}$). Note that $l$ naturally defines a rational
function from $\Pro^1_K$ to $\cT_P\!\times\!\Pro^1_K$ via $[t\!:\!1]
\mapsto (l_1(t),\ldots,l_n(t))\!\times\![t\!:\!1]$. So by \cite[Prop.\
2.1]{silverman} this rational function extends uniquely to a morphism
$\overline{l}$. This is our desired $\overline{l}$ and, of course,
$\overline{l}(1)\!=\!z$.

Now let $L$ be the closure in $\cT_P\!\times\!\Pro^1_K$ of the subvariety of 
$(\Ks)^{n+1}$ defined by the ideal
\[ \langle (1-t)y(u_1) + tz^{u_1} - x^{u_1}, \ldots, (1-t)y(u_n) + tz^{u_n}
- x^{u_n} \rangle. \] 
It is then easily verified
that the hyperplane $\cT_P\!\times\!\{t_0\}$ intersects $L$ in the unique
point $l(t_0)\!\in\!\Ksn$ for all but finitely many $t_0\!\in\!K$. (Simply
solve the resulting binomial equation by exponentiating by $\cV$.) It is
also clear that $\cT_P\!\times\!\{t_0\}$ does not meet $L$ within
$\Ksn\!\times\!\{t_0\}$ for the
remaining values of $t_0$. Thus $L$ must indeed be a curve. Since $L$ is
closed, it must also be complete and equal to the graph of $\overline{l}$
in $\cT_P\!\times\!\Pro^1_K$. By corollary \ref{cor:cool} it easily follows
that $L\!\cap\!O_{(w,1)}\!=\!(z,0)$ (for $w$ as in (i)) and thus
$\overline{l}(0)\!=\!z$.

\noindent
{\bf (iv):} First note that the definition makes sense since we can just
substitute $l$ for $\overline{l}$. Now to verify that $h_i(x,t)$ satsifies
our desired properties, note that $l(t)^{u_i}\!=\!(1-t)y(u_i)+tz^{u_i}$ by
a straightforward calculation. If we define $d\!:=\!\dim L_w$ and write
$e\!=\!\alpha_1 u_1 + \cdots + \alpha_n u_n$, it then becomes clear that
$\ord_t(l(t)^e)\!=\!\alpha_{d+1}+\cdots+\alpha_n$. By changing the signs of
the columns of $\cU$ where necessary, we can then assume that
$w\!\cdot\!u_i\!\geq\!0$ for all $i\!\in\![1..n]$ and write
\[f_i(l(t))\!=\!t^{b_i}(\init_{w,P_i}(f_i)|_{x=(y(\pi_w(\hat{e}_1)),\ldots,
y(\pi_w(\hat{e}_n)))}+ \mathrm{higher \ order \ terms \ in \ } t)\]
\[g_i(l(t))\!=\!t^{b_i}(\init_{w,P_i}(g_i)|_{x=(y(\pi_w(\hat{e}_1)),\ldots,
y(\pi_w(\hat{e}_n)))}+ \mathrm{higher \ order \ terms \ in \ } t)\] where
$b_i\!\in\!\Z$ and $\pi_w : \Rn \longrightarrow L_w$ is the natural
projection defined by the basis $\cU$. In particular, note that
$t^{-b_i}f_i(l(t))|_{t=0}\!=\!0$ (by corollary \ref{cor:cool} and the
definition of $l$) and $t^{-b_i}g_i(l(t))|_{t=0}\!\neq\!0$ (by corollary
\ref{cor:cool} and the definition of $G$). Thus $h_i(x,t)\!=\!t^{-b_i} \kappa(t)
(f_i(x)g_i(l(t))-g_i(x)f_i(l(t)))$, for some $\kappa(t)\!\in\!K(t)$ satisfying
$\ord_t(\kappa)\!=\!0$. So we are done.

\noindent
{\bf (v):} First note that for any $\omega\!\in\!\R^{n+1}$, there is a
$b\!\in\!\Z^{n+1}$ such that $\newt(x^b h_i)$ touches every facet of the
cone $\sigma^\vee_\omega$. (This follows easily since all the $f_i$ are
nonzero and $G$ has $n$-tuple of Newton polytopes $\cP$.) Thus by
definition \ref{dfn:impo2},
$\overline{(\Ksn\!\times\!K)\cap Z(h_i)}\!=\!\cD_{P\times
[0,1]}(h_i,P_i\times [0,d_i])$, where $d_i$ is the $t$-degree of $h_i$.
Lemma \ref{lemma:once} then implies that
for any $w'\!\in\!\Rns$, the defining ideal of $Z\cap U_{(w',1)}$ is
generated by $x^{b_1}h_1,\ldots,x^{b_n}h_n$, for suitable
$b_1,\ldots,b_n\in\Zn$. By theorem \ref{thm:orbit} we know that
$\cT_P\!\times\!\{0\}\cong V_{\hat{e}_{n+1}}$, so by lemma \ref{lemma:once}
the defining ideal of
$(\cT_P\!\times\!\{0\})\cap U_{(w',1)}$ is principal and generated by $t$.
Since $h_i\!\equiv\!f_i \pmod{t}$, we thus see that the defining ideal of
$Z\!\cap\!(\cT_P\!\times\!\{0\})\!\cap\!U_{(w',1)}$ is generated by $t$ and
$x^{b_1}f_1,\ldots,x^{b_n}f_n$. Lemma \ref{lemma:once} then implies that
$\cD_P(F,\cP)\!\cap\!U_{w'}$ has a defining ideal with generators
$x^{b_1}f_1,\ldots,x^{b_n}f_n$. Patching together charts, we are done.

\noindent
{\bf (vi):} This follows easily from \cite[Chap.\ 2.4]{tfulton}.

\noindent
{\bf (vii:)} Clearly, any zero-dimensional irreducible component $\zeta$ of
$\cD_P(F,\cP)$ must be contained in some positive-dimensional irreducible 
component
$\Sigma$ of $Z$. If $\dim \Sigma\!>\!1$ then $\zeta$ must lie in a
positive-dimensional component of $\Sigma \cap (\cT_P\!\times\!\{0\})$ ---
a contradiction. Thus $\dim \Sigma\!=\!1$. Clearly $0\!\in\!\pi(\Sigma)$
and $\pi(\Sigma)\!\neq\!\{0\}$
so by properness we must have $\pi(\Sigma)\!=\!\Pro^1_K$. So $\Sigma$ must
be a component of $\cY$.

\noindent
{\bf (viii:)} Let $t_0\!\in\!\Pro^1_K$. If $\cY$ is irreducible then it
follows directly from the definition of intersection multiplicity that
$\sum \mu(\zeta)$, where $\zeta$ ranges over all zero-dimensional
irreducible components of $\cY\cap(\cT_P\times\{t_0\})$, is precisely the sum
of the ramification indices \cite{silverman} of $\pi^{-1}(t_0)$. The latter
number in turn is precisely the degree of the map $\pi$ and is thus
independent of the point $t_0$ \cite[Examples 4.3.7 and
7.1.15]{ifulton2}.\footnote{Note that in our definitions of ramification
index and degree, we are including the inseparability degree. This is
relevant when the characteristic of $K$ is positive.} If $\cY$ is reducible
then we can extend the definition of degree simply by summing the degrees
of $\pi|_{\cY_j}$ over all the irreducible components $\cY_j$ of $\cY$ and then
our preceding identity still holds.

Thus it suffices to compute $\sum \mu(\zeta)$ for {\em any}\/ $t_0$. In
particular, by construction,
we already know that this number is precisely $\cM(\cP)$ when $t_0\!=\!1$. \qed

The above theorem is quite useful for root counting in $\Ksn$ but still has
the nagging problem that it doesn't give the exact number of roots when the 
intersections are ill-behaved --- more precisely, when $\cD_P(F,\cP)$ 
intersects toric infinity.
However, our theorem (when combined with corollary \ref{cor:cool}) at least
provides us with a computational method for knowing exactly when this
happens. (Indeed, Main Theorem 2 is based on this very fact!) Also, when 
$\cD_P(F,\cP)$ is zero-dimensional, the precise number of 
roots, counting multiplicities, can {\em still}\/ be obtained as follows.
\begin{cor}
\label{cor:subtract}
Following the notation of theorem \ref{thm:toric}, suppose further that
$\cD_P(F,\cP)$ is zero-dimensional or empty. Let $\cI\!:=\!\sum \mu(\zeta)$ 
where the sum ranges over all components $\zeta$ of
$\cD_P(F,\cP)\!\setminus\!\Ksn$. Then the number of roots of 
$F$ in $\Ksn$ is precisely $\cM(\cP)\!-\!\cI$, counting multiplicities. \qed
\end{cor}
\noindent
This approach to {\em exact}\/ (as opposed to generic) root counting is
pursued further in \cite{lamina,resvan} and was independently 
suggested in \cite{msw95} (in the special case of multihomogeneous systems)
and \cite[pp.\ 180--185 and 215--216]{janphd} (not counting some intersection 
multiplicities). 

Intuitively, it is a weaker condition to require $\cD_P(F,\cP)$ to be
zero-dimensional than to require all the roots of $F$ to be isolated {\em
and}\/ lie in $\Ksn$. This statement is made more precise in the next
section and in section \ref{sub:algcond} we will also give a combinatorial
characterization of the stronger hypothesis.

Another natural question which still remains is how to extend our analysis
to other spaces --- for example, $\Kn$. We do this in the next section.
\begin{rem}
We point out that {\bf all} of the results of this section hold for more
general complete toric varieties as well --- in particular, toric varieties
corresponding to (compatible) complete fans. The modifications are minor
and we have omitted them simply because toric compacta corresponding to
polytopes are sufficiently powerful for our particular root counting
problems in affine space. 
\end{rem}
\begin{rem}
\label{poly}
A more elementary (but longer) proof of parts (1) and (2) of theorem
\ref{thm:toric} can be obtained by generalizing Huber and Sturmfels' proof
of Bernshtein's Theorem \cite{polyhomo} to arbitrary algebraically closed
fields: One first replaces the use of theorem \ref{thm:intersect} and lemma
\ref{lemma:cartier} in our intersection theoretic proof by the
combinatorics of {\em mixed subdivisions}. Then, the use of Puiseux series
in their proof is replaced by some algebraic curve theory \`a la the proof of 
(viii). The resulting polyhedral proof requires no more machinery than that 
already used in the proof of part (3). However, for the sake of brevity we 
will omit this alternative proof.
\end{rem}

\section{Proofs of Our Five Main Results} \label{sec:proofs}
We now expand our applications of toric compacta to root counting in affine
space. We will begin by proving the Affine Point Theorem II and then
proceed to prove Main Theorem 1, Corollary \ref{cor:stable}, and Main
Theorems 3 and 2. 

\subsection{Affine Embeddings}
\label{sub:embed}
Contrary to what one might expect, a toric compactification $\cT_P$ does
{\em not}\/ always contain a naturally embedded copy of $\Kn$. This
technicality forces us to require $P$ to satisfy an additional hypothesis
before we apply $\cT_P$ to root counting in $\Kn$. The following definition
is the first of our two main tricks for applying toric intersection theory
to affine root counting.

\begin{dfn}
\label{dfn:compat}
We say a rational polytope $P\!\subset\!\Rn$ is {\em cornered} iff
$\fan(P)$ contains the nonnegative orthant as one of its cones. More
generally, for any $I\!\subseteq\![1..n]$, $P$ is {\em $I$-cornered} iff 
$\sigma_I$ is one of the cones of $\fan(P)$ (following the 
notation of definition \ref{dfn:lin}). 
\end{dfn}
\noindent 
Note that cornering is different for polytopes and $k$-tuples of 
point sets: For polytopes, $\emptyset$-cornering is easily seen to be 
equivalent to a translate of $P$ being identical to the nonnegative orthant in 
a neighborhood of $\bO$. For a $k$-tuple $(C_1,\ldots,C_k)$, cornering refers 
to the {\em position}\/ of each $C_i$ within the nonnegative orthant 
$\sigma_\emptyset$.

Our last definition is well-motivated for the following reason. 
\begin{prop}
\label{prop:corn}
If $P\!\subset\!\Rn$ is $I$-cornered then $\cT_P$ has a naturally embedded
copy of $\Kni$. More precisely, for such a $\cT_P$, $\Kni\!\cong\!U_w$,
where $w$ is the 0-1 vector with support $I^c$. \qed
\end{prop}

We now show how to construct a special $I$-cornered $\Pc$ from any given 
$k$-tuple of polytopes in $\Rn$. 
\begin{alg}
\label{alg:corner} \ 
\begin{itemize}
\item[Input:]{A positive integer $n$, a $k$-tuple of {\em nonempty} integral 
polytopes $\cP\!=\!(P_1,\ldots,P_k)$ lying in the nonnegative orthant of $\Rn$, 
and a subset $I\!\subseteq\![1..n]$.} 
\item[Output:]{An $n$-dimensional rational polytope $\Pc\!\subset\!\Rn$, and 
points $a_1,\ldots,a_k\!\in\!\Zn$, such that $\Pc$ is $n$-dimensional, 
$I$-cornered and compatible with $a\cup \cP$.} 
\item[Description:]{
\begin{enumerate}
\item{For all $i\!\in\![1..k]$ and $j\!\in\![1..n]$, define
$m_{ij}\!:=\!\min \limits \{e_j \; | \; (e_1,\ldots,e_n)\!\in\!P_i\}$, and 
let $m_1,\ldots,m_k$ be the rows of the matrix $[m_{ij}]$.} 
\item{For each $i\!\in\![1..k]$ let $a_i\!\in\!P_i\cap\Zn\cap (m_i+\lin(I))$ or
set $a_i\!:=\!m_i$ if $P_i\!\cap\!(m_i+\lin(I))\!=\!\emptyset$.} 
\item{Define $Q\!:=\!\sum^k_{i=1} \conv(\{a_i\}\!\cup\!P_i)$. If 
$\dim Q\!<\!n$ then set $Q\!:=\!Q+\conv(\bO\cup \cB)$, where $\cB$ is a 
generic set of $n-\dim Q$ rational points in the nonnegative orthant (so that 
$\dim Q\!=\!n$). }
\item{For all $i\!\in\![1..k]$, let $\eps_i\!:=\!\frac{1}{2}\min 
\{ {\mathrm v}_i \}$, where the minimum ranges over all vertices 
${\mathrm v}\!=\!({\mathrm v}_1,\ldots,
{\mathrm v}_n)$ of $Q$ incident to (but not lying in)
$(\hyp(i)+\sum^n_{j=1} a_j)\cap Q$. } 
\item{Define $\Pc\!:=\!((\eps_1,\ldots,\eps_n)+\sigma^\vee_I)\cap 
Q$.\footnote{It is useful to note that the dual cone 
$\sigma^\vee_I$ is precisely $\bigcap \limits_{j\in I^c} 
\{(y_1,\ldots,y_n)\!\in\!\Rn \; | \; y_j\geq 0\}$.} } 
\end{enumerate} }
\end{itemize}
\end{alg}
{}From the last step of our construction it is easily verified that $\Pc$
is $I$-cornered. Also, since $Q$ is already $n$-dimensional and compatible with
$a\cup\cP$, it is clear that our choice of $(\eps_1,\ldots,\eps_n)$ keeps 
$\Pc$ $n$-dimensional and compatible with $a\cup\cP$. Thus 
intersecting a translate of $\sigma^\vee_I$ with $Q$ in step (5) is somewhat 
reminiscent of refining the fan of a polytope by, quoting 
\cite[pg.\ 190]{gkz94}, ``cutting out (as with a knife)$\ldots$ any face of 
codimension at least 2.'' 

As one may have
already guessed, $\Pc$ is especially useful for root counting in $\Kni$ and
the points $a_1,\ldots,a_k$ will also be quite important. As a warm-up, the
following lemma is easily verified from theorem \ref{thm:orbit}, definition
\ref{dfn:impo2}, and proposition \ref{prop:corn}. 
\begin{lemma}
\label{lemma:embed} 
Following the notation of definition \ref{dfn:intersect}, assume further 
that $P_1,\ldots,P_k$ all lie in the nonnegative orthant of $\Rn$. Fix 
$I\!\subseteq\![1..n]$ and define $a_1,\ldots,a_k$ and $\Pc$ via algorithm 
\ref{alg:corner}. Then $\cP$ cornered
$\Longrightarrow (\Kni)\cap Z(F)\!=\!(\Kni)\cap
\cD_\Pc(F,a\cup\cP)$ as schemes. Furthermore, if $\newt(f_i)\!=\!P_i$ for 
all $i$ as well, then 
$\overline{(\Kni)\cap Z(F)}\!=\!\cD_\Pc(F,a\cup\cP)$. \qed 
\end{lemma}
\noindent
We emphasize that $\Kni$ is {\bf not} always naturally embedded in $\cT_P$, 
hence our need for $\Pc$. Thus, under certain assumptions, the above lemma 
allows us to embed an affine hypersurface into a toric divisor. In fact, we can 
do even better: We are now in a position to apply our framework to proving the 
Affine Point Theorem II.

\noindent
{\bf Proof of the Affine Point Theorem II:} Focusing on the first part of
the theorem, the case $\cM(a\cup E)\!=\!0$ is easiest to prove so we
dispose of it first: By the author's Affine Point Theorem I
\cite{rojaswang}, we obtain that a polynomial system with support contained
in $E$ can have {\em no}\/ isolated roots in $\Kni$. Since $E$ is
$(\Kni)$-nice by assumption, we are done.

So let us now assume that $\cM(a\cup E)\!>\!0$. Set 
$\cP\!:=\!(\conv(E_1),\ldots,\conv(E_n))$ and, applying algorithm 1, define  
$\cD\!:=\!\cD_\Pc(F,a\cup \cP)$. We will need the following important fact: 
\[ \star: \ O_w\cap\cD\!=\!\emptyset \mathrm{ \ for \ all \ } w\!\in\!\Rni
\Longleftrightarrow [\cD\!\subset\!\Kni \mathrm{ \ and \ } \dim
\cD\!\leq\!0]. \] 
\noindent
That the left-hand side is equivalent to $\cD\!\subset\!\Kni$ follows
easily from theorem \ref{thm:orbit} and proposition \ref{prop:corn}.
Furthermore, it follows easily from part (2) of the Antipodality Theorem
and proposition \ref{prop:corn} that $\dim \cD\!>\!0 \Longrightarrow
O_w\cap\cD\!\neq\!\emptyset$ for some $w\!\in\!\Rni$. So $\star$ is true.

Now note that the left-hand side of $\star$ is generically true by
proposition \ref{prop:over} and corollary \ref{cor:cool}. So by theorem
\ref{thm:toric}, lemma \ref{lemma:embed}, and $\star$, all but the last
sentence of the Affine Point Theorem II is now verified. Note 
also that we may drop the assumption that $E$ be $(\Kni)$-nice, 
as long as we also count {\em embedded}\/ zero-dimensional components.  

To prove the final part, first note the following identity of weighted set
unions: 
\[ \dagger: \ O_J = (\Kn\!\setminus\!\hyp(J)) \setminus
\left( \bigcup\limits_{|J'\setminus J|=1} (\Knjp) \right) \cup \left(
\bigcup\limits_{|J'\setminus J|=2} (\Knjp) \right) \setminus \cdots \]
which terminates in the appropriate union or set difference according as
$n-|J|$ is even or odd. This follows easily from the principle of
inclusion-exclusion \cite{gkp} since, for any $\vartheta\!\subseteq\![1..n]$, 
$\Kn\!\setminus\!\hyp(\vartheta)$ is precisely the disjoint
union $\coprod_{\vartheta'\supseteq \vartheta} O_{\vartheta'}$. The key to 
proving our alternating mixed volume formula is then to simply find an 
intersection theoretic analogue of $\dagger$.

To do this we must work in a new {\em lifted}\/ compactification depending on 
$J$.  So let $P(J')$ denote the $\Pc$ corresponding to the $I\!=\!J'$ 
case of algorithm 1 and define $\wcT$ to be the toric compactification
corresponding to $\wP\!:=\!\sum_{J'\supseteq J} P(J')$. Also let
$a_1(J'),\ldots,a_n(J')$ respectively denote the integral points
$a_1,\ldots,a_n$ from the $I\!=\!J'$ case of algorithm 1. By example 
\ref{ex:compat}, $\wP$ is compatible with $a(J')\cup\cP$ for all 
$J'\!\supseteq\!J$, so 
define $\wcD(J')\!:=\!\cD_\wP(F,a(J')\cup\cP)$. Then, by \cite[Chap.\
2.4]{tfulton} and our construction, there is a proper morphism 
$\varphi : \wcT \twoheadrightarrow \cT_{P(J)}$ with no fibers of 
infinite cardinality. Similar to proposition \ref{prop:corn} and lemma 
\ref{lemma:embed}, it is also easily checked that 
$O_J\cap\varphi(\wcD(J))\!=\!O_J\cap Z(F)$.  

More importantly, it is easily verified from definition \ref{dfn:impo2} 
and expanding in $\chow(\wcT)$ that (as cycles) $\wcD(J'')$ is a 
{\em summand}\/ of $\wcD(J')$ for all
$J''\!\supseteq\!J'\!\supseteq\!J$. Also, it immediately follows from
theorem \ref{thm:toric} that $\deg \wcD(J')\!=\!\cM_{J'}$ for all
$J'\!\supseteq\!J$. So by inclusion-exclusion once again, we have the
following equality of cycles: \[ \varphi^{-1}(O_J)\cap \wcD(J) = \wcD(J) - 
\left( \sum\limits_{|J'\setminus J|=1}
\wcD(J') \right)
+ \left( \sum\limits_{|J'\setminus J|=2}
\wcD(J') \right)
- \cdots \]
provided $\varphi^{-1}(O_J)\cap \wcD(J)$ is zero-dimensional or 
empty.\footnote{We should remark that the left-hand intersection 
is {\em set}-theoretic, and {\em not}\/ a Chow product.} 
So then $\deg(\varphi^{-1}(O_J)\cap\wcD(J))$ is precisely our 
alternating mixed volume formula. Note that $\wcD(J)$ generically 
has exactly $\deg(\varphi^{-1}(O_J)\cap\wcD(J))$ points 
(counting multiplicities) in $\varphi^{-1}(O_J)$, by the portion of 
the Affine Point Theorem II that we've already proved and since 
$E$ is $O_J$-nice. The last cycle class degree is also precisely 
$\deg(O_J\cap\varphi(\wcD(J)))$ \cite[Example 7.1.9]{ifulton2}, so we are 
done. \qed

Of course, the assumption that $E$ be cornered is quite restrictive. We
relax this assumption in the following section by refining lemma
\ref{lemma:embed}, and then Main Theorem 1 follows easily by explicitly
expanding a different intersection product in the Chow ring of $\cT_\Pc$.

\subsection{Chow Rings and Main Theorem 1} 
\label{sub:chow}
Our second and final trick for applying special $\cT_P$'s to affine root
counting is a bit more abstract. Whereas our first trick (``cornering'') 
consisted of a convex geometric construction, the construction we give now 
amends a difficulty with the divisors $\cD_P(f,Q)$ we used earlier. In 
particular, for noncornered $(P_1,\ldots,P_n)$, it is possible that 
$\overline{(\Kni)\cap Z(f_i)}$ and $\cD_\Pc(f_i,\conv(\{a_i\}\cup P_i))$ 
differ in the coefficients corresponding to the coordinate hyperplanes. This 
is remedied by the following definition and lemma.

\begin{dfn}
\label{dfn:shift}
Following the notation of Main Theorem 1, definition \ref{dfn:toric}, and 
lemma \ref{lemma:embed}, define
$\cX_j\!:=\!V_{\hat{e}_j} \subset \cT_\Pc$ for any
$j\!\in\!I^c$. Also, set $\Ds(0,P_i)\!:=\!\cT_\Pc$ and, if 
$\supp(f_i)\!\neq\!\emptyset$, define $\Ds(f_i,P_i)\!:=\!\cD_\Pc(f_i,
\conv(\{a_i\}\cup P_i))+\sum_{j\in I^c} 
m_{ij}\cX_j \in \chow(\cT_\Pc)$. Finally, let $\Ds(F,\cP)\!:=\!\bigcap^k_{i=1} 
\Ds(f_i,P_i)\in\chow(\cT_\Pc)$. The {\em roots of $f_i$ within $\cT_\Pc$} 
are then, formally, $\Ds(f_i,\newt(f_i))$. 
\end{dfn}
\begin{lemma}
\label{lemma:shift}
Following the notation of definition \ref{dfn:shift}, $(\Kni)\cap
Z(F)=(\Kni)\cap\Ds(F,\cP)$ as schemes. Furthermore, if 
$\newt(f_i)\!=\!P_i$ then $\overline{(\Kni)\cap Z(f_i)}=\Ds(f_i,P_i)$, within 
$\cT_\Pc$. \qed
\end{lemma}
\noindent
In particular, for any $j\!\in\!I^c$, $\cX_j$ is the
closure of the hyperplane $\{ x \; | \; x_j=0\}\cap(\Kni)$ in $\cT_{\Pc}$.
Keeping this in mind, the proof of the lemma is then straightforward from
theorem \ref{thm:orbit}, proposition \ref{prop:corn}, and lemma
\ref{lemma:embed}. So by ``shifting'' our toric divisors, we now at last have 
a completely general way of embedding an affine hypersurface into a toric 
compactification. As an application, we will prove Main Theorem 1.

\noindent
{\bf Proof of Main Theorem 1:} Set $\cP\!:=\!(\conv(E_1),\ldots,\conv(E_n))$. 
We will first prove the case $W\!=\!\Kni$ and, to do so, it will clearly 
suffice to demonstrate the following two statements:
\begin{itemize}
\item[A$_{\deg}$: ]{$\cN_K(E;\Kni)\!=\!\deg\Ds(F,\cP)$. }
\item[A$_{\sm}$: ]{$\deg \Ds(F,\cP)$ is precisely the double summation stated 
in Main Theorem 1.}
\end{itemize}
Consider also the following auxiliary statement: 
\begin{itemize}
\item[A$_{\gen}$: ]{for fixed $E$ and generic $\cC_E$, $\Ds(F,\cP)$ is 
zero-dimensional and supported entirely within $\Kni$.} 
\end{itemize}
To prove A$_{\deg}$ and A$_{\sm}$, we will actually 
first prove $($A$_{\deg})\wedge($A$_{\gen})$ by induction on $n$, 
and then A$_{\sm}$ will follow easily. 

First note that by the definition of $\Ds(\cdot)$ we may formally expand
$\Ds(F,\cP)$ in $\chow(\cT_\Pc)$ as a polynomial in the
$\cX_j$. More explicitly, 
\[ \Ds(F,\cP)=\bigcap\limits^n_{i=1}\left(\cD_\Pc(f_i,\conv(\{a_i\}\cup P_i)) + 
\sum\limits_{j\in I^c} m_{ij}\cX_j\right)= \]
\[\sum \limits_{[1..n]\supseteq J\supseteq I} \; 
\sum \limits_{\rho:J^c \hookrightarrow [1..n]} \left[
\left( \prod \limits_{j\in J^c} m_{j\rho(j)} \right)
\left(\bigcap \limits_{i\in J}\cD_\Pc(f_i,\conv(\{a_i\}\cup P_i))\right)
\cap\left( \bigcap \limits_{j\in \rho(J^c)}\cX_j \right)\right] \]
This is where the shape of our asserted formula comes from. Note 
that $j\!\in\!I \Longrightarrow \cX_j\cap(\Kni)\!=\!\emptyset$, thus allowing 
the slight simplification of the outer summation.  

Now note that $\bigcap_{j\in \rho(J^c)} \cX_j$ is itself isomorphic 
to the toric variety corresponding to a face $P_{(J,\rho)}$ of $\Pc$,  
\`a la theorem \ref{thm:orbit}. In particular, letting 
$\cP_{(J,\rho)}\!:=\!((P_j-m_j)\cap\lin(\rho(J^c)^c) \; | \; 
j\!\in\!J)$, it easy to see that $P_{(J,\rho)}$ can occur as the output 
of the $(k,n,\cP,I)\!\rightsquigarrow\!(|J|,|J|,\cP_{(J,\rho)},
\rho(J^c)^c\cap I)$ case of algorithm 1. 

Let $F_{(J,\rho)}$ be the polynomial system obtained by 
setting the variables $\{x_j \; | \; j\!\in\!\rho(J^c)\}$ to
$0$ in the $|J|$-tuple $(x^{-m_{i1}}_1\cdots x^{-m_{in}}_nf_i \; | \; 
i\!\in\!J)$. Also note that 
$\bigcap_{j\in \vartheta}\hyp(j)\!=\!\lin(\vartheta^c)$ for any 
$\vartheta\!\subseteq\![1..n]$. We may then say that 
\[ \left( \bigcap 
\limits_{i\in J}\cD_\Pc(f_i,\conv(\{a_i\}\cup P_i))\right) 
\cap\left(\bigcap \limits_{j\in \rho(J^c)}\cX_j\right) \cong 
\Ds(F_{(J,\rho)},\cP_{(J,\rho)}) \] 
where the underlying compactification for the right-hand cycle is 
$\cT_{P_{(J,\rho)}}$. This last identity follows from definitions 
\ref{dfn:impo2} and \ref{dfn:shift}, and our preceding observations. 

Note that $E_{([1..n],\cdot)}$ is cornered. So then the proof of the Affine 
Point Theorem II (and definition \ref{dfn:impo2}) immediately implies that 
$\deg\cD_\Pc(F,a\cup\cP)\!=\!\cM(a\cup\cP)\!=\!\cN_K(E_{([1..n],\cdot)};\Kni)$ 
and, generically, $\cD_\Pc(F,a\cup\cP)$ is zero-dimensional and 
supported entirely within $\Kni$.  As for the remaining intersection terms 
with $J\!\neq\![1..n]$, our induction hypothesis (with $n\!=\!|J|$) implies 
that
\[\cN_K\left(E_J;\lin(\rho(J^c)^c)\cap(\Kni)\right)\!=\!\deg\Ds(F_{(J,\rho)},
\cP_{(J,\rho)}).\] 
Furthermore, our induction hypothesis also implies that, generically, 
$\Ds(F_{(J,\rho)},\cP_{(J,\rho)})$ is zero-dimensional and supported entirely 
within $\lin(\rho(J^c)^c)\cap(\Kni)$. 

Now note that our Chow expansion also immediately implies that 
\[
\supp(\Ds(F,\cP))\!=\!\bigcup_{I\subseteq J\subseteq[1..n]} \;  
\bigcup_{\rho:J^c\hookrightarrow [1..n]} \supp(\Ds(F_{(J,\rho)},\cP_{(J,\rho)})), \] 
modulo some isomorphisms fixing $\Kni$. Since a finite conjunction of generic
conditions is again a generic condition, we thus 
arrive at A$_{\gen}$.  

Recall that lemma \ref{lemma:shift} states 
that $(\Kni)\cap Z(F)$ is naturally embedded in $\Ds(F,\cP)$. Thus 
$\cN_K(E;\Kni)\!\leq\!\deg\Ds(F,\cP)$ and, by A$_{\gen}$, we arrive at 
A$_{\deg}$. Noting that the $n\!=\!1$ case of $($A$_{\deg})\wedge($A$_{\gen})$ 
is true simply via the fundamental theorem of algebra over $K$, our 
induction is complete. 

Finally, A$_{\sm}$ follows simply by taking degrees of 
both sides of our Chow expansion. Note also that our embedding, along with 
A$_{\deg}$, implies that $\cN_K(E;\Kni)$ is indeed the maximal number of 
isolated roots. So the case $W\!=\!\Kni$ is proved. 

The general case then follows easily from inclusion-exclusion, much like
our proof of the Affine Point Theorem II. This method goes through because
our asserted formula is additive with respect to disjoint unions in $W$, and 
already true for $W\!=\!\Kni$. \qed
\begin{rem}
Since our proof of Main Theorem 1 computes $\cN_K(E;W)$ as the degree 
of an algebraic cycle, remark \ref{rem:disting} is just a 
straightforward abstract extension of our preceding proof.
\end{rem}
\begin{rem}
\label{rem:simple}
The double summation of Main Theorem 1 can of course simplify considerably 
when $W$ is smaller than $\Kn$. For instance, there is only 1 term when 
$W\!=\!\Ksn$.  Also, it is a simple combinatorial exercise to show that the 
double summation of Main Theorem 1 has at most $\prod^n_{i=1} 
(|\supp(m_i)|+1)$ terms. Equality occurs, for example, when $W\!=\!\Kn$. 
Note also that by our recursive formula, the matrix $[m_{ij}]$ can be assumed to
have at most $1$ nonzero entry per column if 
$E$ is $W$-nice. So, by the fact that $(a+1)(b+1)\!\geq\!a+b+1$ for positive 
integers, we also obtain that our double summation has at most $2^n$ terms. 
Furthermore, this maximum is attained iff $[m_{ij}]$ has the same support as a 
permutation matrix.
\end{rem}
\begin{rem}
If one would like a formula closer to the number of {\em distinct} roots in
$\Kni$, a useful trick is the following: Use Main Theorem 1,
but replacing $[m_{ij}]$ with the 0-1 matrix having the same support. From
our last proof, it is easy to see that this new formula has the effect of
(generically) counting isolated roots lying on $\bigcup \limits_{J\supseteq 
I, \ |J|=n-1} O_J$ {\em without} multiplicity. Thus, if one continues 
to propogate this trick throughout the recursion of Main Theorem 1, 
we can count (omitting multiplicities due to inseparability degree) the 
generic number of distinct roots of $F$ in $W$. 
This is important because for many $E$, a sparse system with support contained 
in $E$ {\em always}\/ has roots of multiplicity $>\!1$ lying in 
$\Kn\!\setminus\!\Ksn$. 
\end{rem}

A useful corollary of our proof of Main Theorem 1 is the following concise
generalization of theorem \ref{thm:toric}. 
\begin{cor}
\label{cor:new}
Following the notation of lemma \ref{lemma:shift}, 
assume further that $k\!=\!n$ and $\cP\!=\!(\conv(E_1),\ldots,\\ 
\conv(E_n))$. Then $\cN_K(E;\Kni)\!=\!\deg \Ds(F,\cP)$. Furthermore, if both 
$\cN_K(E;\Kni)$ and $\dim \Ds(F,\cP)$ are positive, then $\Ds(F,\cP)$ has 
strictly less than $\cN_K(E;\Kni)$ zero-dimensional components, counting 
multiplicities. 
\end{cor}
\noindent
{\bf Proof:} The first portion follows immediately from our proof of the 
$W\!=\!\Kni$ case of Main Theorem 1. As for the remaining portion,  
by the Chow expansion from our last proof,  
it suffices to prove the cornered case and then simply mimic the earlier 
descent by induction. Since the cornered case of our present corollary is 
already contained in the $(\cP,P)\!\rightsquigarrow\!(a\cup\cP,P^\llcorner)$ 
case of theorem \ref{thm:toric}, we are done. \qed

So theorem \ref{thm:toric} is just the $I\!=\![1..n]$ case of 
collary \ref{cor:new}. In intersection theoretic terms, the above
result establishes the {\em numerical positivity}\/ \cite{ifulton2} of 
any positive-dimensional component of the new shifted cycle $\Ds(F,\cP)$. 
This will allow us to derive precise algebraic conditions for what ``generic'' 
means in the context of affine root counting.

Corollary \ref{cor:stable} then follows easily from Main Theorem 1 as follows: 

\noindent
{\bf Proof of Corollary \ref{cor:stable}:} Although Huber and Sturmfels did
not explicitly mention intersection multiplicities in \cite{hsaff}, an
examination of their proof of the stable mixed volume formula shows that 
multiplicities were at least included implicitly. In particular, we may
safely assume that the first portion of Corollary \ref{cor:stable} is true
for $K\!=\!\C$. The remaining portion (for $K\!=\!\C$) is already implicit
in Huber and Sturmfels' proof\footnote{Note that our $O_J$ is actually 
$O_{\{1,\ldots,n\}\setminus J}$ in the notation of \cite{hsaff}.} 
of the stable mixed volume formula, so we may safely assume that {\em all}\/ 
of Corollary \ref{cor:stable} is true for $K\!=\!\C$.

Generalizing to arbitrary algebraically closed $K$ is then almost trivial: 
The right-hand sides (of both asserted formulae) are clearly independent of
$K$. By Main Theorem 1 and the Affine Point Theorem II, the left-hand sides
are also independent of $K$, provided $K$ is algebraically closed. Since
both formulae are already true for $K\!=\!\C$, we are done. \qed

Similar to remark \ref{poly}, a more elementary (but longer) proof of
Corollary \ref{cor:stable} can be derived by generalizing Huber and Sturmfels' 
proof of their stable mixed formula. 

\subsection{Sparse Resultants, Roots at Infinity, and Main Theorems 2 and 
3} 
\label{sub:algcond} 
We conclude with an analysis of conditions under which 
our (global) generic root counts are exact. The conditions 
we give can be split into two types: algebraic and combinatorial. 
In the combinatorial case our conditions are always both sufficient and 
necessary, while in the algebraic case our criteria are always sufficient 
but fail to be necessary for certain systems which generically have no roots. 
However, we fully classify the cases where our algebraic criteria are 
necessary. These results will rely on the following 
technical result relating our shifted toric divisors with toric infinity. 
\begin{lemma}
\label{lemma:split}
Following the notation of the proof of Main 
Theorem 1, let $\cD_{[1..n]}$ ($\in\!\chow(\cT_\Pc)$) be the $J\!=\![1..n]$ 
term of the Chow expansion of $\Ds(F,\cP)$. Then the following conditions 
imply that $F$ has exactly $\cN_K(E;\Kni)$ roots, counting multiplicities, in 
$\Kni$: 
\begin{itemize}
\item[(a)]{$O_w\cap\cD_{[1..n]}\!=\!\emptyset$ 
for all $w\!\in\!\Rni$, and }    
\item[(b)]{if $n\!>\!1$ then for all $J\!\subsetneqq\![1..n]$ containing
$I$, and all injections $\rho : J^c \hookrightarrow [1..n]$ such that
$\rho(J^c)\cap I\!=\!\emptyset$ and $\prod_{j\in J^c} m_{j\rho(j)}>0$, 
\[\cN_K\left(E_{(J,\rho)};\lin(\rho(J^c)^c)\cap(\Kni);\cC_E\right)=
\cN_K\left(E_{(J,\rho)};\lin(\rho(J^c)^c)\cap(\Kni)\right).\]}
\end{itemize}
Furthermore, the converse implication holds as well if 
$\cN_K(E_{([1..n],\cdot)};\Kni)\!>\!0$. In particular, (a) and (b) 
together imply that the zero set of $F$ in $\Kni$ is zero-dimensional or 
empty. 
\end{lemma} 
\noindent
{\bf Proof of the Lemma:} 
Note that $\supp(\Ds(F,\cP))\!=\!\bigcup \supp(\Ds(F_{(J,\rho)},
\cP_{(J,\rho)}))$ where the union ranges over $([1..n],\cdot)$ and all pairs 
$(J,\rho)$ described above. This follows immediately from our Chow 
expansion from the proof of Main Theorem 1, and the fact that the 
terms with $\rho(J^c)\cap I$ nonempty or $\prod_{j\in J^c} m_{j\rho(j)}$ 
zero simply aren't there (by definition \ref{dfn:shift}). Recall also that 
$E_{([1..n],\cdot)}$ is cornered. So it suffices to prove the cornered case 
and descend by induction, just as we did in the proofs of Main Theorem 1 and 
corollary \ref{cor:new}. But the cornered case, minus 
the partial converse, is already contained in assertion $\star$ from our 
proof of the Affine Point Theorem II. One also observes that the 
$(\Longrightarrow)$ portion of $\star$ continues to hold even when 
$\cN_K(E;\Kni)\!=\!0$. So we are done. \qed 
\begin{rem}
\label{rem:fancy}
Note that the converse of the main assertion of lemma \ref{lemma:split} 
can fail if $\cN_K(E_{([1..n],\cdot)};\Kn\!\setminus\\
\hyp(I))\!=\!0$: Consider the 
polynomial system $F\!=\!(1+x,1+x,(1+x)(y+z)+1)$ where $E\!:=\!\supp(F)$ 
and note that condition (b) is violated when $w\!=\!(0,-1,-1)$. 
\end{rem}
\begin{rem}
\label{rem:fancier}
However, the converse doesn't always fail if 
$\cN_K(E_{([1..n],\cdot)};\Kni)\!=\!0$: For instance, the converse 
{\em always} holds for $n\!=\!2$ when $E\!=\!\supp(F)$. More generally,   
for any $n\!>\!2$, setting $f_1\!:=\!1$ and $E_1\!:=\!\{\bO\}$ gives 
an entire family of examples. Basically, when $\cN_K(E;\Kni)\!=\!0$, 
the converse of the main assertion of lemma \ref{lemma:split} fails precisely 
when $E$ is sufficiently complicated to allow specializations of $\cC_E$ where 
$F$ has roots at toric infinity while having {\em none} within $\Kni$. 
\end{rem}

We are now ready to prove Main Theorem 3.

\noindent 
{\bf Proof of Main Theorem 3:} We will first dispose of case (1) which 
is the easiest. Recall that $\Kni\!=\!\coprod_{J\supseteq I}
O_J$ and that a finite conjunction of generic conditions is again a
generic condition. Since $E$ is null for $\Kni$ (and thus for every 
$O_J$ with $J\!\supseteq\!I$) it suffices to show that 
our condition from case (1) is equivalent to $D\cap\lin(J)$ $O_J$-counting 
$E\cap\lin(J)$ for all $J\!\supseteq\!I$. This, in essence, is the statement 
of Lemma 3 of \cite{convexapp}. So case (1) is complete. 

As for case (2), note that $E^w$ depends only on the face $S^w$. So by 
corollary \ref{cor:cool}, the same is true of $O_w\cap\cD_{[1..n]}$. 
Then by lemma \ref{lemma:split}, the definition of 
$W$-counting, and since any finite conjunction of generic conditions is again 
a generic condition, we need only prove the case where $E$ is cornered 
and then descend by induction just as in three of our last four proofs. For 
$I\!=\!\emptyset$, the cornered case is just case (2) of Theorem 7 of 
\cite{rojaswang}. Applying algorithm 1, generalizing the proof 
there to arbitrary $I$ is simple. (In fact, the proof of 
\cite[Theorem 7]{rojaswang} already contains what is essentially the 
$I\!=\!\emptyset$ case of algorithm 1.) So we are done. \qed 

We now recall the {\em sparse resultant}\/ (also known as the 
{\em $(\cA_1,\ldots,\cA_k)$-resultant}, {\em mixed}\/ resultant, {\em 
Newton}\/ resultant, or {\em toric}\/ resultant), which is 
an extremely important operator on overdetermined polynomial systems. It is 
defined for any $k\!\times\!n$ {\bf indeterminate} polynomial system
$F$ with support $E$, provided that all the $E_i$ can be translated into a
common $(k\!-\!1)$-dimensional subspace of $\Rn$. Since we can always 
identify such a subspace with a rational hyperplane in $\R^k$, we will   
consider only the case of $n\!\times\!(n-1)$ systems and 
monomial transformations (involving an extra variable) of such systems. 

More explicitly, suppose $E$ is an $n$-tuple of nonempty finite subsets 
of $\Zn$ which can be translated into a common $(n\!-\!1)$-plane in $\Rn$. 
Then the sparse resultant, with respect to $E$, will be a (homogeneous) 
polynomial $\res_E(\cdot)$ in the coefficients $\cC_E$ satisfying the 
following property: If $\cC\!\in\!K^{|E|}$ and $F|_{\cC_E=\cC}$ has a root in 
$\Ksn$, then $\res_E(\cC)\!=\!0$. For 
fixed $E$, the polynomial $\res_E(\cdot)$ can then be {\bf defined} (up to a 
nonzero scalar multiple) as the unique polynomial in $\cC_E$ of least total 
degree satisfying this last property. The computation of 
$\res_E(\cdot)$ is a deep subject and we refer the reader to
\cite{gkz90,chowprod,jandi1,sz94, combiresult,gkz94,isawres,resvan} for
further background on sparse resultants.

For convenience, we will use $\res_E(F)$ in place of $\res_E(\cC)$ whenever
the coefficients of $F$ have been specialized to some $\cC\!\in\!K^{|E|}$.
We also point out the following important fact: $\res_E(F)\!=\!0$ does 
{\bf not} necessarily imply that $F$ has a root in $\Ksn$. The correct
statement, at least for initial term systems, is the following.
\begin{thm}
\cite{resvan}
\label{thm:resorbit}
Following the notation of theorem \ref{thm:toric}, suppose 
$\cP\!=\!(\conv(E_i) \; | \; i\!\in\![1..n])$ and $w$ is an inner
facet normal of $P$. Then $\res_{E^w}(F)\!=\!0
\Longleftrightarrow V_w\!\cap\!\cD_P(F,\cP)\!\neq\!\emptyset$. \qed 
\end{thm}
\begin{rem}
Since $\init_{w,E}(F)$ involves a subset of the coefficients $\cC_E$, we've
further simplified notation by writing $\res_{E^w}(F)$ in place of
$\res_{E^w}(\init_{w,E}(F))$. 
\end{rem}

Our algebraic condition for $F$ to have generically many roots 
is based on the above useful property of the sparse resultant.

\noindent
{\bf Proof of Main Theorem 2:} Recall from the proof of Main Theorem 
3 that $E^w$ and $O_w\cap\cD_{[1..n]}$ depend only on the face $S^w$.  
So then, by theorem \ref{thm:orbit}, $V_w\cap\cD_{[1..n]}$ also depends 
only on $S^w$. To conclude, by theorems \ref{thm:orbit} and \ref{thm:resorbit}, 
it is clear that conditions (a) and (b) of lemma \ref{lemma:split} are 
respectively equivalent to conditions (a$_2$) and (b$_2$) of Main Theorem 2. 
So we are done. \qed 
\begin{rem}
In practice, we would not actually construct the Minkowski 
sum $S$ stated in our last two main theorems. Instead, we would actually  
work with the individual normal fans of $\conv(E_1),\ldots,\\
\conv(E_n)$ and 
dynamically update the smallest common refinement necessary for our search 
space. The deeper stages in the recursion would then simply consist of 
slicing cones in the search fans by appropriate coordinate subspaces.  
\end{rem} 

The case $(K,I)\!=\!(\C,[1..n])$ of Main Theorem 2 was independently 
discovered and presented in \cite[Theorem 6.1]{polyhomo}. However, the 
statement there is false in the case where the mixed volume is zero: Simply 
consider the counter-example from remark \ref{rem:fancy}. Moreover, parallel 
to lemma \ref{lemma:split}, the converse of the main assertion of Main Theorem 
2 doesn't depend completely on the positivity of $\cN_K(E;\Kni)$: The examples 
given in remarks \ref{rem:fancy} and \ref{rem:fancier} also work here in an 
analogous way. Sharper computational conditions for exactness in the cases  
$\cN_K(E;\Kni)\!=\!0$ will be addressed in future work. 
\begin{rem} 
Following the notation of definition \ref{big}, we see that  
Main Theorem 2 allows us to express $\Delta$ as a union of 
hypersurfaces, via condition (a$_2$) and the recursion of condition 
(b$_2$). However, the {\em minimal} delta (containing 
all $\cC$ such that $F|_{\cC_E=\cC}$ does {\em not} have the 
generic number of roots) need not be a hypersurface or even an 
algebraic variety. In general, this ``generic counting discriminant'' is a 
{\em constructible} variety of codimension $>\!1$. However, we 
can at least explicitly compute the codimension by combining 
Main Theorem 2 with Theorem 1.3 of \cite{combiresult}. 
\end{rem}

``Sparse'' techniques have recently been applied quite succesfully to {\em 
solving}\/ many polynomial systems occuring in industrial problems
\cite{mobiorobo,emiphd,isawres,dynamiclift}. Software implementations of
resultant-based algorithms are also discussed in almost all of these
papers. Thus Main Theorem 2 presents another potentially useful 
application of the sparse resultant. 
 
\section{Acknowledgements}
\label{sec:acknowledgements}
The author would like to thank Marie-Francoise Roy for her kind 
support and hospitality during his visit to IRMAR in Rennes. 
He is also grateful to Paco Santos and Jie Tai Yu for shooting down 
his erroneous conjectures, and to Birk Huber, T. Y. Li, Bernd
Sturmfels, and Robert M. Williams for many valuable discussions. The author 
also thanks the referees from MEGA '96 for their valuable suggestions.  

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

\bibitem[Ber75]{bernie} Bernshtein, D. N., {\it ``The Number of Roots of a
System of Equations,"} Functional Analysis and its Applications (translated
from Russian), Vol. 9, No. 2, (1975), pp.\ 183--185.

\bibitem[BF34]{bonnie} Bonnessen, T. and Fenchel, W., {\it Convex Bodies,}
translated from German, TCS Associates, 1934.

\bibitem[CE93]{jandi1} Canny, John F. and Emiris, Ioannis Z., {\it ``An
Efficient Algorithm for the Sparse Mixed Resultant,''} Proceedings AAECC,
Puerto Rico, May, Lect. Notes in Comp. Science 263, pp.\ 89--104,
Springer-Verlag, 1993.

\bibitem[CLO92]{clo} Cox, D., Little, J., and O'Shea, D., {\it Ideals,
Varieties, and Algorithms,} Undergraduate Texts in Mathematics,
Springer-Verlag, 1992.

\bibitem[Dan78]{dannie} Danilov, V. I., {\it ``The Geometry of Toric
Varieties,"} Russian Mathematical Surveys, 33 (2), pp.\ 97--154, 1978.

\bibitem[DK87]{dankho} Danilov, V. I., and Khovanskii, A., {\it ``Newton
Polyhedra and an Algorithm for Computing Hodge-Deligne Numbers,"} Math.
USSR Ivzestiya, Vol.\ 29 (1987), No.\ 2.

\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[DRS96]{drs} Dalbec, J., Rojas, J. M., and Sturmfels, B., {\it
``How to Fill a Mixed Volume,"} manuscript, Massachusetts Institute of
Technology, 1996.

\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[Eis95]{eisenbud} Eisenbud, David, {\it ``Commutative Algebra 
with a View Toward Algebraic Geometry,''} Graduate Texts in Mathematics 
150, Springer-Verlag.  

\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[Ful84a]{ifulton1} Fulton, William, {\it Introduction to
Intersection Theory in Algebraic Geometry,} no.\ 54, Regional Conference
Series in Mathematics, American Mathematical Society, 1984.

\bibitem[Ful84b]{ifulton2} \underline{\hspace{\fw}}, {\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[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, 1--62, 1990.

\bibitem[GKZ94]{gkz94} Gel'fand, I. M., Kapranov, M. M., and Zelevinsky, A.
V., {\it Discriminants, Resultants and Multidimensional Determinants,}
Birkhauser, Boston, 1994.

\bibitem[Gr\"u69]{grunbaum} Gr\"unbaum, Branko, {\it Convex Polytopes},
Interscience, London, New York, Sydney, 1969.

\bibitem[Har77]{algeom} Hartshorne, Robin, {\it Algebraic Geometry,}
Springer-Verlag, 1977.

\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[HS96]{hsaff} \underline{\hspace{\hs}}, {\it ``Bernshtein's Theorem in 
Affine Space,"} Discrete and Computational Geometry, to appear, 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[Jac85]{jacobson1} Jacobson, Nathan, {\it Basic Algebra I}, 2$^\nd$
edition, W. H. Freeman and Company, 1985.

\bibitem[Kho77]{khocompat} Khovanskii, Askold 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[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 Polytope and General Resultants,"} Duke Mathematical Journal, 
Vol.\ 67, No.\ 1, pp.\ 189--218 (1992). 

\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[Kus76]{kus76} \underline{\hspace{\agku}}, {\it ``Newton Polytopes and 
the B\'ezout Theorem,"} Functional Analysis and its Applications (translated 
from Russian), vol.\ 10, no.\ 3, July--September (1976), pp.\ 82--83.

\bibitem[LW96]{liwang} Li, T. Y. and Wang, Xiaoshen, {\it ``The BKK Root
Count in $\Cn$,"} Mathematics of Computation, October, 1996. 

\bibitem[MSW95]{msw95} Morgan, A. P., Sommese, A. J., and Wampler, 
C. W., {\it ``A Product-Decomposition Theorem for Bounding B\'ezout Numbers,''} 
SIAM J. Numer. Anal., 32(4): 1308--1325, 1995. 

\bibitem[Mum76]{mum} Mumford, David {\it Algebraic Geometry I: Complex
Algebraic Varieties,} Springer-Verlag, 1976.

\bibitem[Oda88]{oda} Oda, Tadeo, {\it Convex Bodies and Algebraic Geometry: 
an Introduction to the Theory of Toric Varieties}, Springer-Verlag, 1988.

\bibitem[PC94]{mobiorobo} Parsons, David and Canny, J. F., {\it ``Geometric
Problems in Molecular Biology and Robotics,"} In Proceedings of the Second
International Conference on Intelligent Systems for Molecular Biology, Palo
Alto, CA, August, to appear (1994).

\bibitem[PS93]{chowprod} Pedersen, P. and Sturmfels, B., {\it ``Product
Formulas for Sparse Resultants and Chow Forms,"} Mathematische Zeitschrift,
214: 377--396, 1993.

\bibitem[Roj91]{myms} Rojas, J. Maurice, {\it ``An Optimal Condition for
Determining the Exact Number of Roots of a Polynomial System,"} M.S.
thesis, C.S. Division, U. C. Berkeley, 1991.

\bibitem[Roj92]{myprize} \underline{\hspace{\jmr}}, {\it ``When Can One Easily 
Find the Number of Roots of a Nonhomogeneous Polynomial System?,"} extended
abstract presented at the $40^\thth$ Annual Meeting of the Society for
Industrial and Applied Mathematics, Los Angeles, July 15--19, 1992.

\bibitem[Roj94]{convexapp} \underline{\hspace{\jmr}}, {\it ``A Convex Geometric
Approach to Counting the Roots of a Polynomial 
System,"} Theoretical Computer Science (1994), vol.\ 133 (1), pp.\ 105--140.
(Additional notes and corrections available on-line at {\tt 
http://www-math.mit.edu/\~{}rojas}.)

\bibitem[Roj96a]{myaverage} \underline{\hspace{\jmr}}, {\it ``On the Average 
Number of Real Roots of Certain Random Sparse 
Polynomial Systems,''} pp.\ 689--699, {\it The Mathematics of Numerical 
Analysis}, Lectures in Applied Mathematics, vol.\ 32 (1996), edited by Jim 
Renegar, Mike Shub, and Steve Smale, American Mathematical Society. 

\bibitem[Roj96b]{lamina} \underline{\hspace{\jmr}}, {\it ``Toric Laminations,   
Sparse Generalized Characteristic Polynomials,  
and a Refinement of Hilbert's Tenth Problem,''} Proceedings of the Rio de 
Janeiro Foundations of Computational Mathematics Conference (January 1997), 
Springer-Verlag, to appear. 

\bibitem[Roj96c]{resvan} \underline{\hspace{\jmr}}, {\it ``When do Resultants 
Really Vanish? Applications to Diophantine Complexity,''} manuscript, MIT. 

\bibitem[Roj96d]{aff} \underline{\hspace{\jmr}}, {\it ``Affine Elimination
Theory and Solving Certain Diophantine Equations Quickly,''} manuscript, MIT. 

\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[Sha80]{sha} Shafarevich, I. N., {\it Basic Algebraic Geometry,}
Springer study editions, Springer-Verlag, 1980.

\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[Sil86]{silverman} Silverman, Joseph, {\it The Arithmetic of
Elliptic Curves,} Springer Graduate Texts in Mathematics 106,
Springer-Verlag, 1986.

\bibitem[Stu92]{morea} Sturmfels, Bernd, {\it ``More Examples of 
$\cA$-Resultants,''} letter to Misha Kapranov, 1992.

\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[SZ94]{sz94} Sturmfels, B. and Zelevinsky, A., {\it ``Multigraded
Resultants of Sylvester Type''} Journal of Algebra, 163(1): 115--127, 1994.

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

\bibitem[VGC96]{dynamiclift} Verschelde, J., Gatermann, K., and Cools, R.,
{\it ``Mixed Volume Computation by Dynamic Lifting Applied to Polynomial
System Solving,"} Discrete and Computational Geometry, Vol.\ 16, 
No.\ 1, pp.\ 69--112 (1996).

\bibitem[Wam92]{wam92} Wampler, Charles W., {\it ``Bezout Number
Calculations for Multi-Homogeneous Polynomial Systems,''} Applied
Mathematics and Computation 51, pp.\ 143--157, 1992.

\bibitem[War94]{warren} Warren, {\it ``A Bound on the Implicit 
Degree of Polygonal B\'ezier Surfaces,''} Algebraic Geometry and 
its Applications, edited by Chandrajit L. Bajaj, pp.\ 513--525 

\end{thebibliography}

\section*{Appendix: Niceness and Genericity}
Here we briefly recount some earlier results on $W$-counting and some
related concepts. Some of the material below is covered at greater length
in \cite{convexapp} (for the case $I\!=\![1..n]$) and \cite{rojaswang} (for
the case $I\!=\!\emptyset$ and $E$ cornered). The paper \cite{combiresult}
is also a useful reference but deals more with the sparse resultant than
with root counting. The results below form the basis for our combinatorial
conditions for when a ``partially'' generic polynomial system has
generically many isolated roots in a given union of orbits. 

Recall that the {\em dimension}\/ of any $B\!\subseteq\!\Rn$, $\dim B$, is
the dimension of the smallest subspace of $\Rn$ containing a translate of
$B$. The following two definitions are fundamental to our development.
\begin{dfn}
Suppose $C\!:=\!(C_1,\ldots,C_n)$ is an
$n$-tuple of polytopes in $\Rn$ {\em 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\![1..n]$ is {\em essential} for $C$ (or $C$ {\em 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 {\em proper} $J'\!\subsetneqq\! J$.
\end{dfn}
\begin{dfn}
We say that $C$ {\em has an almost essential subset $J$}
$\Longleftrightarrow$ (0) $\supp(C)\!\supseteq\!J$, (1) $\dim(\sum_{j\in J}\\
C_j)=|J|$, and (2) $\dim(\sum_{j\in J'} C_j)\geq |J'|$ for all nonempty 
$J'\!\subseteq\! J$. Also, $\emptyset$ is defined to be almost essential for 
$C$ iff $\supp(C)\!=\!\emptyset$. 
\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. The following figure shows some
simple examples of essential subsets for $C$, for various $C$ in the case
$n\!=\!2$. It also worth noting that $J\cup\{j\}$ is essential for $C 
\Longrightarrow J$ is almost essential for $C$, provided
$|J\cup\{j\}|\!>\!|J|\!>\!0$. 

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

\put(-20,-50){
\begin{picture}(133,100)(0,0)
% picture of the first pair
\put(41,80){\circle*{3}} \put(38,85){$C_1$} \put(82,80){\circle*{3}}
\put(79,85){$C_2$} \put(45,50){$\{1\},\{2\}$}
\end{picture}}

\put(108,-50){
\begin{picture}(133,100)(0,0)
% picture of the second pair
\put(26,70){\line(1,1){30}}
\put(26,70){\circle*{3}} \put(56,100){\circle*{3}} \put(26,85){$C_1$}
\put(72,70){\line(1,1){30}}
\put(72,70){\circle*{3}} \put(102,100){\circle*{3}} \put(72,85){$C_2$}
\put(50,50){$\{1,2\}$}
\end{picture}}

\put(256,-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 third pair
\put(45,50){None}
\end{picture}}

\end{picture}

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

\end{figure}
%%% 

Making use of the fact that $\Kni$ is the disjoint union
$\coprod_{J\supseteq I} O_J$, our combinatorial results for
$(\Kni)$-counting and $(\Kni)$-niceness will follow easily upon
partitioning $\Kni$ into orbits. In particular, it will be useful to refine
$W$-niceness slightly as follows. 
\begin{dfn}
Suppose $E$ is an $n$-tuple of finite subsets of $(\N\cup\{0\})^n$. 
We then call $E$ {\em null} for $W \Longleftrightarrow$ a generic polynomial 
system with support contained in $E$ has {\em no} roots in $W$. 
\end{dfn}

For any $J\!\subseteq\![1..n]$, define
$E\cap\lin(J)\!:=\!(E_1\cap\lin(J),\ldots,E_n\cap\lin(J))$. We may now
quote the following useful result.
\begin{lemma}
\label{lemma:start}
\cite[Corollary 2]{rojaswang}
Suppose $E$ is an $n$-tuple of finite subsets of $(\N\cup\{0\})^n$. Then
$E$ is nice for $O_J \Longleftrightarrow E\cap\lin(J)$ has an almost
essential subset of cardinality $|J|$ or an essential subset. In
particular, $E$ is null for $O_J \Longleftrightarrow E\cap\lin(J)$ has an
essential subset. \qed 
\end{lemma}

The following characterization of $(\Kni)$-niceness then follows almost
immediately.
\begin{lemma}
\label{lemma:wow}
An $n$-tuple $E$ of finite subsets of $(\N\cup\{0\})^n$ is nice for $\Kni
\Longleftrightarrow$ for all $J\!\supseteq\!I$, $E\cap\lin(J)$ has an
almost essential subset of cardinality $|J|$ or an essential subset. In
particular, $E$ is null for $\Kni \Longleftrightarrow$ for all
$J\!\supseteq\!I$, $E\!\cap\!\lin(J)$ has an essential subset. \qed
\end{lemma}
\noindent
The characterization of $W$-niceness for $W$ an arbitrary union of orbits 
is then completely analogous. 

\end{document}

