1.2. POLYHEDRAL BOUNDS 3
1.2. Polyhedral bounds
When N = n, the most fundamental bound on the number of complex solutions
is due to ezout: d is at most the product of the degrees of the polynomials fi.
When the polynomials have a sparse, or polyhedral structure, the smaller BKK
bound applies.
Integer vectors a = (a1,...,an) Zn are exponents for (Laurent) monomials
Zn
a
xa
:= x11
a
x22
a
· · · xnn
a
C[x1,...,xn,x1
−1
, . . . , xn
−1]
.
We will often identify a monomial with its exponent vector and thus will just call
elements of
Zn
monomials. Let A
Zn
be a finite set of monomials. A linear
combination
a∈A
caxa
ca R
of monomials from A is a sparse polynomial with support A. Sparse polynomials
naturally define functions on the complex torus
Tn
:=
(C∗)n.
A system (1.1) of
N = n polynomials in n variables, where each polynomial has support A, will be
called a system (of polynomials) with support A. These are often called unmixed
systems in contrast to mixed systems where each polynomial may have different
support. While sparse systems occur naturally—multilinear or multihomogeneous
polynomials are an example—they also occur in problem formulations for the simple
reason that we humans seek simple formulations of problems, and this often means
polynomials with few terms.
A fundamental result about unmixed systems is the Kushnirenko bound on
their number of complex solutions. The Newton polytope of a polynomial f with
support A is the convex hull ΔA of the set A of monomials of f. Write volume(Δ)
for the Euclidean volume of a polytope Δ.
Theorem 1.1 (Kushnirenko [10]). A system of n polynomials in n variables
with support A has at most n!volume(ΔA) isolated solutions in
(C∗)n,
and exactly
this number when the polynomials are generic polynomials with support A.
Bernstein generalized this to mixed systems. The Minkowski sum P +Q of two
polytopes in
Rn
is their pointwise sum as sets of vectors in
Rn.
Let P1,...,Pn
Rn
be polytopes. The volume
volume(t1P1 + t2P2 + · · · + tnPn)
is a homogeneous polynomial of degree n in the variables t1,...,tn [63, Exercise
15.2.6]. The mixed volume MV(P1,...,Pn) of P1,...,Pn is the coefficient of the
monomial t1 · · · tn in this polynomial.
Theorem 1.2 (Bernstein [11]). A system of n polynomials in n variables where
the polynomials have supports A1,..., An has at most MV(ΔA1 , . . . , ΔAn ) isolated
solutions in (C∗)n, and exactly this number when the polynomials are generic for
their given support.
Since MV(P1,...,Pn) = n!volume(P ) when P1 = · · · = Pn = P , this general-
izes Kushnirenko’s Theorem. We will prove these theorems in Chapters 3 and 4.
The bound of Theorem 1.1 and its generalization Theorem 1.2 is often called
the BKK bound for Bernstein, Khovanskii, and Kushnirenko [10].
Previous Page Next Page