4 1. OVERVIEW

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

2(l+n)(n

2

+

1)l+n

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

2,

each

positive solution becomes

2n

real solutions, one in each of the

2n

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

(1.3)

10x106

+

11y53

− 11y =

10y106

+

11x53

− 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].