2.i.a. The BKK Bound

Given polytopes P₁, P₂, ..., P_m in Rⁿ, their Minkowski sum is the pointwise sum

When there are n equal polytopes, the mixed volume is n! Vol(P), the normalized volume of the common Newton polytope P, and when the polytope P_i is a line segment of length d_i in the ith coordinate direction (so that P_i = New(f_i), where f_i is the polynomial given in (2.2)), the mixed volume is the Bézout number d₁d₂...d_n.

Given a list A = (P₁, P₂, ..., P_n) of polytopes in Rⁿ with vertices in the integral lattice Nⁿ, a sparse polynomial system with structure A is a system of polynomials (2.1) with New(f₁) = P₁. These sparse systems may have trivial solutions where some coordinates vanish. Thus we only consider solutions with non-zero complex coordinates. We have the following basic result on the number of solutions to such a sparse system of polynomials.

This result was developed in a series of papers by Kushnirenko [Ko], Bernstein [Be], and Khovanskii [Kh1]. For simplicity of exposition, we will largely restrict ourselves to the case when the polynomials all have the same Newton polytope P. The polyhedral homotopy algorithm of Huber and Sturmfels [HS] gives an effective demonstration of this BKK bound. It deforms the sparse system (2.1) into a system where the number of solutions is evident and is based upon Sturmfels's generalization  [Stu2] of Viro's method for constructing real varieties with controlled topology  [Vi]. We will describe it in Section 2.ii.c, after we give some examples and definitions.