Next: 2.iii.c. Kushnirenko's Conjecture
Up: 2.iii. Real Solutions to Sparse Polynomial Systems
Previous: 2.iii.a. Constructive Lower Bounds

## 2.iii.b. Fewnomial Upper Bounds

These definitions, constructions, and results apply to what have come to be known as fewnomial systems. A fewnomial is a polynomial f with few monomials--the monomials of f are members of some set A not necessarily equal to the lattice points within its convex hull. In particular, the results of Section 2.iii.a give lower bounds on the maximum number of real solutions r(A) to a system of fewnomials whose monomials are from A. Here, we use a regular triangulation Aw of the point set A induced from a lifting function w : A --> Q.

When n = 1, consider the binomial (a fewnomial) system

xd - 1   =   0 .

This has d complex solutions. We similarly expect that the number of complex solutions to a fewnomial system to be equal to the BKK bound. The above binomial system has either 1 or 2 real solutions, and so the number of real solutions to a fewnomial system should be less than the BKK bound. The question is: How much less?

Khovanskii [Kh1,Kh2] established a very general result concerning systems where each fi is a polynomial function of the monomials xa for a in A. He proves that the number of real solutions to such a system is at most 2n2N(n+1)#A, where N is #A(#A-1)/2 (= #A choose 2), and #A is the number of monomials in A. When the polynomial functions are linear, they are polynomials with monomials from A, and hence we have Khovanskii's fewnomial bound.

2n2N(n+1)#A

While this bound seems outrageously large, it does not depend upon the volume of the convex hull of A, but rather on the algebraic complexity--the ambient dimension n and the size #A of A. That such a bound exists at all was revolutionary.

We compare this complexity bound to the combinatorial upper bound (2.6) on the number of real solutions to a lifted fewnomial system (2.4) in the limit as t approaches 0. The invariant e(F) of a facet of the regular triangulation Aw of A is at most n. Thus

 r   is at most 2n times the number of facets Aw

Since a facet involves n+1 points from A, this is in turn bounded by
 2n times the binomial coeffecient .
This bound is typically much lower than Khovanskii's bound. For example, consider two trinomials in two variables. Here n=2, and after multiplying each equation by a suitable monomial, we have #A= 5. Thus we have Khovanskii's fewnomial bound

r(A)   is at most   22 210 35   =   995,328 .

In contrast, a triangulation of 5 points in the plane has at most 5 simplices

and so the bound r for limiting lifted systems involving the same 5 monomials is 22 5   =   20 .

Next: 2.iii.c. Kushnirenko's Conjecture
Up: 2.iii. Real Solutions to Sparse Polynomial Systems
Previous: 2.iii.a. Constructive Lower Bounds