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) 2 (n + 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 → x2, i 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].

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.