Contemporary Mathematics
Multivariate ultrametric root counting
Mart´ ın Avenda˜ no and Ashraf Ibrahim
Abstract. Let K be a field, complete with respect to a discrete non-archimedian
valuation and let k be the residue field. Consider a system F of n polynomial
equations in K
. . . , Xn
. Our first result is a reformulation of the
classical Hensel’s Lemma in the language of tropical geometry: we show suffi-
cient conditions (semiregularity at w) that guarantee that the first digit map
δ :

is a one to one correspondence between the solutions of F
with valuation w and the solutions in
of the initial form system
inw(F ). Using this result, we provide an explicit formula for the number of so-
lutions in
of a certain class of systems of polynomial equations (called
regular), characterized by having finite tropical prevariety, by having initial
forms consisting only of binomials, and by being semiregular at any point in
the tropical prevariety. Finally, as a consequence of the root counting formula,
we obtain the expected number of roots in (K∗) of univariate polynomials with
given support and random coefficients.
1. Introduction
The problem of counting the number of roots of univariate polynomials has
been studied for at least 400 years. The first result that we point out here, stated
by Descartes in 1637 [7], says that the number of positive roots (counted with
multiplicities) of a nonzero polynomial f R[x] is bounded by the number of sign
alternations in the sequence of coefficients of f. Over the reals, the problem of root
counting was finally solved by Sturm in 1829, who gave a simple algebraic procedure
to determine the exact (as opposed to an upper bound) number of real roots of a
polynomial f in a given interval [a, b]. The problem was consider settled for many
years until a interest in sparse polynomials began to grow. While Sturm’s technique
can count the exact number of roots of any polynomial, it is highly inefficient for
polynomials of high degree with only a few nonzero terms, and also failed to provide
any insight on the roots of such polynomials. On the other hand, Descartes’ rule
seems to be more natural for highly sparse polynomials: a simple consequence of
the rule is that the number of nonzero real roots of a polynomial is bounded by
1991 Mathematics Subject Classification. 11S05, 14T05.
Key words and phrases. Ultrametric fields, Hensel’s Lemma, Root counting, Tropical
Avenda˜ no was supported in part by NSF Grant DMS-0915245. Ibrahim was supported in part
by the AFOSR/NASA National Center for Hypersonic Research in Laminar-Turbulent Transition.
c 0000 (copyright holder)
Contemporary Mathematics
Volume 556, 2011
c 2011 American Mathematical Society
Previous Page Next Page