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 efficient 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 coefficients in Fp). Using a
more unifying approach, more of these upper bounds for ordered fields, finite ex-
tensions of Qp, and Laurent series with coefficients 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
Previous Page Next Page