Next: 2.ii. The Polyhedral Homotopy Algorithm
Up: 2. Polynomial Systems

# 2.i. Sparse Polynomial Systems

Perhaps the most obvious structure of a system of n polynomials in n variables

 f1(x1,...,xn)  =  f2(x1,...,xn)  =  ...  =  fn(x1,...,xn)  =  0 , (2.1)

is the list of total degrees of the polynomials f1, f2, ..., fn. For such a system, we have the degree or Bézout upper bound, which is a consequence of the refined Bézout Theorem of Fulton and MacPherson [Fu1, §1.23].

Theorem 2.1 (Bézout Bound)   The system (2.1), where the polynomial fi has total degree di := deg fi, has at most d1d2...dn isolated complex solutions.

The Bézout bound on the number of real solutions is sharp. For example, if

 fi   =   (xi-1) (xi-2)...(xi-di) (2.2)

then the system (2.1) has d1d2...dn real solutions. The reader is invited to construct systems with the minimum possible number (0 or 1) of real solutions.

A system of polynomial equations with only simple solutions, but with fewer solutions than the Bézout bound is called deficient. For example, fewer monomials in the polynomials lead to fewer solutions. We make this idea more precise. A monomial (or rather its exponent vector) is a point of Nn. The convex hull of the monomials in f is its Newton polytope, New(f), a polytope with integral vertices. The terms of f are indexed by the lattice points in its Newton polytope.

Figure 1 displays the monomials (dots) and Newton polytopes of the polynomials

 f = 1 + x - y + xyz4 g = 1 + x - y + 3z - z3 + 2z4

Subsections

Next: 2.ii. The Polyhedral Homotopy Algorithm
Up: 2. Polynomial Systems