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

X±1,

1

. . . , Xn

±1

. Our first result is a reformulation of the

classical Hensel’s Lemma in the language of tropical geometry: we show suﬃ-

cient conditions (semiregularity at w) that guarantee that the first digit map

δ :

(K∗)n

→

(k∗)n

is a one to one correspondence between the solutions of F

in

(K∗)n

with valuation w and the solutions in

(k∗)n

of the initial form system

inw(F ). Using this result, we provide an explicit formula for the number of so-

lutions in

(K∗)n

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 coeﬃcients.

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 coeﬃcients 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 ineﬃcient 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

varieties.

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)

1

Contemporary Mathematics

Volume 556, 2011

c 2011 American Mathematical Society

1

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

X±1,

1

. . . , Xn

±1

. Our first result is a reformulation of the

classical Hensel’s Lemma in the language of tropical geometry: we show suﬃ-

cient conditions (semiregularity at w) that guarantee that the first digit map

δ :

(K∗)n

→

(k∗)n

is a one to one correspondence between the solutions of F

in

(K∗)n

with valuation w and the solutions in

(k∗)n

of the initial form system

inw(F ). Using this result, we provide an explicit formula for the number of so-

lutions in

(K∗)n

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 coeﬃcients.

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 coeﬃcients 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 ineﬃcient 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

varieties.

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)

1

Contemporary Mathematics

Volume 556, 2011

c 2011 American Mathematical Society

1