1.3. Upper bounds
While the number of complex roots of a univariate polynomial is typically equal
to its degree, the number of real roots depends upon the length of the expression
for the polynomial. Indeed, by Descartes’s rule of signs [34] (see Section 2.1), a
univariate polynomial with m+1 terms has at most m positive roots, and thus at
most 2m nonzero real roots. For example, the polynomial xd a with a = 0 has
0, 1, or 2 real roots, but always has d complex roots. Khovanskii generalized this
type of bound to multivariate polynomials with his fundamental fewnomial bound.
Theorem 1.3 (Khovanskii [83]). A system of n polynomials in n variables
having a total of 1+l+n distinct monomials has at most
nondegenerate positive solutions.
There are two reasons for this restriction to positive solutions. Most funda-
mentally is that Khovanskii’s proof requires this restriction. This restriction also
excludes the following type of trivial zeroes: Under the substitution xi xi
positive solution becomes
real solutions, one in each of the
orthants. More
subtle substitutions lead to similar trivial zeroes which differ from the positive
solutions only by some sign patterns.
This is the first of many results verifying the principle of Bernstein and Kush-
nirenko that the topological complexity of a set defined by real polynomials should
depend on the number of terms in the polynomials and not on the degrees of the
polynomials. Khovanskii’s work was also a motivation for the notion of o-minimal
structures [160, 113]. The main point of Khovanskii’s theorem is the existence of
such a bound and not the actual bound itself.
Nevertheless, it raises interesting questions about such bounds. For each l, n
1, we define the Khovanskii number X(l, n) to be the maximum number of nonde-
generate positive solutions to a system of n polynomials in n variables with 1+l+n
monomials. Khovanskii’s Theorem gives a bound on X(l, n), but that bound is
enormous. For example, when l = n = 2, the bound is 5184. Because of this,
Khovanskii’s bound was expected to be far from sharp. Despite this expectation,
the first nontrivial improvement was only given in 2003.
Theorem 1.4 (Li, Rojas, and Wang [94]). Two trinomials in two variables
have at most five nondegenerate positive solutions.
This bound is sharp. Haas [64] had shown that the system of two trinomials
in x and y
11y =
11x = 0 ,
has five positive solutions.
Since we may multiply one of the trinomials in (1.3) by an arbitrary monomial
without changing the solutions, we can assume that the two trinomials (1.3) share
a common monomial, and so there are at most 3+3 1 = 5 = 2+2+1 monomials
between the two trinomials, and so two trinomials give a fewnomial system with
l = n = 2. While five is less than 5184, Theorem 1.4 does not quite show that
X(2, 2) = 5 as two trinomials do not constitute a general fewnomial system with
l = n = 2. Nevertheless, Theorem 1.4 gave strong evidence that Khovanskii’s
fewnomial bound may be improved. Such an improved bound was given in [17].
Previous Page Next Page