FEWNOMIAL BOUNDS FOR COMPLETELY MIXED POLYNOMIALSYSTEMSFR´ED´ERIC BIHAN AND FRANK SOTTILEAbstract. We give a bound for the number of real solutions to systems of n polynomialsin n variables, where the monomials appearing in different polynomials are distinct. Thisbound is smaller than the fewnomial bound if this structure of the polynomials is nottaken into account.IntroductionIn 1980, A. Khovanskii [8] showed that a system of n polynomials in n variables involvingl+n+1 distinct monomials has less than(1) 2(l+n2)(n + 1)l+nnon-degenerate positive solutions. This fundamental result established the principle thatthe number of real solutions to such a system should have an upper bound that dependsonly upon its number of terms. Such results go back to Descartes [7], whose rule of signsimplies that a univariate polynomial having l+1 terms has at most l positive zeroes. Thisprinciple was formulated by Kushnirenko, who coined the term “fewnomial” that has cometo describe results of this type.Khovanskii’s bound (1) is the specialization to polynomials of his bound for a moregeneral class of functions. Recently, the significantly lower bound of(2)e2+ 342(l2)nlwas shown [5] for polynomial fewnomial systems. This took advantage of some geometryspecific to polynomial systems, but was otherwise based on Khovanskii’s methods. Thesignificance of this bound is that it is sharp in the sense that for fixed l there are systemswith O(nl) positive solutions [4]. Modifying the proof [2] leads to the bound(3)e4+ 342(l2)nlfor the number of real solutions, when the differences of exponent vectors of the monomialsgenerate the integer lattice—this condition disallows trivial solutions that differ fromother solutions only by some predictable signs. Otherwise, if Λ ⊂ Znis generated by thedifferences of the exponents, then (3) is a bound for the number of real zeroes divided bythe order of the 2-torsion subgroup in Zn/Λ.These bounds hold in particular if each of the polynomials involve the same 1+l+nmonomials, which is referred to as an unmixed polynomial system. By Kushnirenko’sprinciple, we should expect a lower bound if not all monomials appear in every polynomial.2000 Mathematics Subject Classification. 14P99.Key words and phrases. fewnomials, sparse polynomial systems.Sottile supported by NSF grant DMS-0701050 and Texas A&M ITRAG.12 FR´ED´ERIC BIHAN AND FRANK SOTTILESuch an approach to fewnomial bounds, where we take into account differing structuresof the polynomials, was in fact the source of the first result in this subject. In 1978,Sevostyanov proved there is a function N(d, m) such that if the polynomial f(x, y) hasdegree d and the polynomial g(x, y) has m terms, then the system(4) f(x, y) = g(x, y) = 0has at most N(d, m) non-degenerate positive solutions. This result has unfortunatelynever been published†. A special case was recently refined by Avenda˜no [1], who showedthat if f is linear, then (4) has at most 6m−4 real solutions.Li, Rojas, and Wang [10] showed that a fewnomial system (4) where f has 3 terms willhave at most 2m− 2 positive solutions (when m = 3, the bound is lowered to 5). Moregenerally, they showed that the number of positive solutions to a system(5) g1(x1, . . . , xn) = g2(x1, . . . , xn) = · · · = gn(x1, . . . , xn) = 0is at most n + n2+ · · · + nm−1, when each of g1, . . . , gn−1is a trinomial and gnhas mterms. These bounds are significantly smaller than the corresponding bounds of [5], whicharee2+342(m−12)nm−1in both cases. Their methods require that at most one polynomial isnot a trinomial and apparently do not generalize. However, their results show that thefewnomial bound can be improved when the polynomials have additional structure.We take the first steps towards improving the fewnomial bounds (2) and (3) when thepolynomials have additional structure, but no limit on their numbers of monomials. Thatis, if the polynomial giin (5) has 2 + literms with li> 0, we seek bounds on the numberof non-degenerate positive solutions that are smaller in order than 2(l2)nl, where l+n+1 isthe total number of terms in all polynomials. Note that l ≤ l1+ · · · + ln. The reason forour choice of parameterization of these systems is that if some li= 0, there is a change ofvariables which reduces the number of variables, eliminates gifrom the list polynomials,and does not change the number of monomials in the other polynomials, nor the numberof positive solutions. A zero of a system of polynomial equation is non-degenerate if thedifferentials of the equations at that zero are linearly independent.Theorem 1. Suppose that each polynomial giin (5) has a constant term, but otherwiseall monomials are distinct, so that the system involves l+n+1 monomials where l =l1+ · · · + ln. If the sublattice of Znspanned by differences of exponent vectors has oddindex in Zn, then the number of non-degenerate non-zero real solutions (5) is at moste4+34· 2(l2)¡ll1,...,ln¢,and the number of those which are positive is at moste2+34· 2(l2)¡ll1,...,ln¢.The bounds of Theorem 1 are strictly smaller than those of [2, 5], fornl=X¡ll1,...,ln¢,the sum over all 0 ≤ liwith l1+ · · · + ln= l.In Theorem 1 the bound for positive solutions holds with no assumption on the indexof the sublattice spanned by differences of exponent vectors and holds even if we allow†A description of this and much more is found in Anatoli Kushnirenko’s letter to Sottile [9].FEWNOMIAL BOUNDS FOR COMPLETELY MIXED POLYNOMIAL SYSTEMS 3real-number exponents. We only need to prove this for n ≥ 2, as these bounds exceedDescartes’ bound when n = 1.We establish Theorem 1 by modifying the arguments of [2, 5]. In particular, we applya version of Gale duality [6] to replace the system of polynomials by a system of masterfunctions in the complement of a hyperplane arrangement in Rl, and then estimate thenumber of solutions by repeated applications of the Khovanskii-Rolle Theorem appliedto successive Jacobians of the system of master functions. This modification is not asstraightforward as we have just made it sound. First, the arguments we modify requirethat the hyperplane arrangement be in general position in RPl, but in the case here,the hyperplanes are arrangements of certain normal crossings divisors in the product ofprojective spaces RPl1× · · · × RPln. We exploit the special structure of chambers in thiscomplement, together with the multihomogenity of the Jacobians to obtain the