** 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* mo*nomials*--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 **A**_{w} of the point
set **A** induced from a lifting function
*w* : **A** --> **Q**.
When *n* = 1, consider the binomial (a fewnomial) system

*x*^{d} - 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 *f*_{i} is a *polynomial* function of the
monomials *x*^{a} for *a* in **A**.
He proves that the number of real solutions to such a system is at most
2^{n}2^{N}(*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.

2^{n}2^{N}(*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
**A**_{w} of **A** is at most *n*.
Thus

*r* is at most 2^{n} times the number of facets
**A**_{w} |

Since a facet involves *n*+1 points from **A**, this is in turn bounded
by
2^{n} 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
2^{2} 2^{10} 3^{5}
= 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 2^{2} 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