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 := x11x22 a 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(ΔA 1 , . . . , ΔA n ) 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