2

MART´

IN

AVENDA˜

NO AND ASHRAF IBRAHIM

twice the number of its nonzero terms. Incidentally, it has been discovered recently

(see [1]) how to make Descartes’ rule count the exact number of real roots: the trick

is to multiply the polynomial by a high enough power of x + 1 before counting the

sign alternations. Unfortunately, this procedure destroys completely the sparseness

of the input polynomial.

In our search for a similar result over different fields, we decided to focus our at-

tention to complete fields with respect to a non-arquimedian valuation. There were

several results in this setting that indicate that an eﬃcient root counting technique

was feasible for these fields. The first of those results, obtained by H.W. Lenstra in

1999 [10], gives an upper bound for the number of nonzero roots in Qp (the field of

p-adic numbers) of a polynomial f ∈ Qp[x] as a function of the number of nonzero

terms of f. The second, obtained by B. Poonen in 1998 [11], gives a similar bound

over Fp((u)) (the field of formal Laurent series with coeﬃcients in Fp). Using a

more unifying approach, more of these upper bounds for ordered fields, finite ex-

tensions of Qp, and Laurent series with coeﬃcients in fields of characteristic zero,

were obtained by M. Avenda˜ no and T. Krick in 2011 [3].

In a previous paper (see [2]), we showed a root counting procedure for univariate

polynomials that do not destroy the sparsity of the given polynomial. The technique

uses a combination of Hensel’s Lemma and Newton Polygon to reduce root counting

to solving binomials over the residue field. The only drawback of this result is that

it works only with regular polynomials, which is an extensive class of polynomials

defined in that paper, but not for generic polynomials in the usual sense. In this

paper, we succeded to extend those results (root counting procedure and upper

bounds) to the multivariate setting, to provide a better understanding of the size

of the class of regular polynomials, and also estimates for the expected number of

zeros of random sparse polynomials. Our counting procedure uses basic tropical

geometry and a multivariate version of Hensel’s Lemma to reduce the problem to

solving binomial square systems over the residue field.

Our bound for the number of zeros of sparse multivariate square system of poly-

nomials should be compared with the bound obtained by J.M. Rojas in 2004 [14],

which can be regarded as the p-adic counterpart of A. Khovanskii’s theorem for

fewnomials over the reals [9], or as the extension of Lenstra’s estimates in the uni-

variate case [10]. Rojas showed that, over any finite extension K/Qp, any such

system of polynomials has at most 1 + (CK n(t −

n)3

log(t −

n))n

zeros, where t is

the total number of different exponents vectors appearing in polynomials and CK

is a computable constant that depends only on K. Our counting gives a stronger

bound, although only for regular systems:

Theorem 1.1. Let F = (f1, . . . , fn) be a

regular1

system of polynomials in

K X1

±1,

. . . , Xn ±1 . Assume that the residue field k is finite. Then the number of

zeros of F in (K∗)n is at most

(

t1

2

)

· · ·

(

tn

2

)

|k∗|n, where ti is the number of nonzero

monomials of fi.

This represents an improvement from roughly

t3n

to

t2n

in the case of regular

systems.

1see

definition 4.1.

2

MART´

IN

AVENDA˜

NO AND ASHRAF IBRAHIM

twice the number of its nonzero terms. Incidentally, it has been discovered recently

(see [1]) how to make Descartes’ rule count the exact number of real roots: the trick

is to multiply the polynomial by a high enough power of x + 1 before counting the

sign alternations. Unfortunately, this procedure destroys completely the sparseness

of the input polynomial.

In our search for a similar result over different fields, we decided to focus our at-

tention to complete fields with respect to a non-arquimedian valuation. There were

several results in this setting that indicate that an eﬃcient root counting technique

was feasible for these fields. The first of those results, obtained by H.W. Lenstra in

1999 [10], gives an upper bound for the number of nonzero roots in Qp (the field of

p-adic numbers) of a polynomial f ∈ Qp[x] as a function of the number of nonzero

terms of f. The second, obtained by B. Poonen in 1998 [11], gives a similar bound

over Fp((u)) (the field of formal Laurent series with coeﬃcients in Fp). Using a

more unifying approach, more of these upper bounds for ordered fields, finite ex-

tensions of Qp, and Laurent series with coeﬃcients in fields of characteristic zero,

were obtained by M. Avenda˜ no and T. Krick in 2011 [3].

In a previous paper (see [2]), we showed a root counting procedure for univariate

polynomials that do not destroy the sparsity of the given polynomial. The technique

uses a combination of Hensel’s Lemma and Newton Polygon to reduce root counting

to solving binomials over the residue field. The only drawback of this result is that

it works only with regular polynomials, which is an extensive class of polynomials

defined in that paper, but not for generic polynomials in the usual sense. In this

paper, we succeded to extend those results (root counting procedure and upper

bounds) to the multivariate setting, to provide a better understanding of the size

of the class of regular polynomials, and also estimates for the expected number of

zeros of random sparse polynomials. Our counting procedure uses basic tropical

geometry and a multivariate version of Hensel’s Lemma to reduce the problem to

solving binomial square systems over the residue field.

Our bound for the number of zeros of sparse multivariate square system of poly-

nomials should be compared with the bound obtained by J.M. Rojas in 2004 [14],

which can be regarded as the p-adic counterpart of A. Khovanskii’s theorem for

fewnomials over the reals [9], or as the extension of Lenstra’s estimates in the uni-

variate case [10]. Rojas showed that, over any finite extension K/Qp, any such

system of polynomials has at most 1 + (CK n(t −

n)3

log(t −

n))n

zeros, where t is

the total number of different exponents vectors appearing in polynomials and CK

is a computable constant that depends only on K. Our counting gives a stronger

bound, although only for regular systems:

Theorem 1.1. Let F = (f1, . . . , fn) be a

regular1

system of polynomials in

K X1

±1,

. . . , Xn ±1 . Assume that the residue field k is finite. Then the number of

zeros of F in (K∗)n is at most

(

t1

2

)

· · ·

(

tn

2

)

|k∗|n, where ti is the number of nonzero

monomials of fi.

This represents an improvement from roughly

t3n

to

t2n

in the case of regular

systems.

1see

definition 4.1.

2