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 B´ 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 coeﬃcient 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].