16
MART´
IN
AVENDA˜
NO AND ASHRAF IBRAHIM
contain any point (corresponding to a monomial of f) other than the vertices. In
addition to this, each lower binomial f
[w]
=
aXα+bXβ
must have either w v(π)Z,
or char(k) α−β, or δ(b/a) not a (α−β)-th power in
k∗.
Compared with the notion
of regularity given in [2, Def. 1], the definition in this paper includes a broader class
of polynomials, while the formula for the total number of roots in
K∗
provided in [2,
Thm. 4.4, Thm. 4.5] is the same as the formula implied by our Algorithm 2.
Consider a set A = {α1 · · · αt} Z with 2. Denote K[X]A the
set of polynomial supported by A, i.e. K[X]A = {
∑t
α∈A
aαXα
: = 0}. For
each f K[X]A we define the support of the Newton Polygon of f as the set
B = A : (α, v(aα)) lower hull of NP(f)}. The subset of the polynomials
in K[X]A with Newton Polygon supported at B is denoted K[X]A.
B
Note that we
always have {α1,αt} B A, and that K[X]A =
{α1,αt}⊆B⊆A
K[X]A.
B
The
discussion above is summarized in the following corollary.
Corollary 4.3. Let A = {α1 · · · αt} Z be a set with t 2 and
char(k) αj αi for all i = j. Let B = {α1 = β1 · · · β|B| = αt} A and take
f =

α∈A
aαXα
K[X]A.
B
Then
Trop(f) =
v(aβi+1 ) v(aβi )
βi+1 βi
: i = 1, . . . , |B| 1 ,
i.e. Trop(f) is the set of minus the slopes of the segments of NP(f). Moreover, f is
regular if and only if the points {(β, v(aβ)) : β B} are all vertices of the Newton
Polygon, and in this case, the number of roots of f in
K∗
is equal to
|B|−1
i=1
χ
v(π)Z
v(aβi+1 ) v(aβi )
βi+1 βi
Zk(δ(aβi+1
)Xβi+1
+ δ(aβi
)Xβi
) .
Finally, note that given a polynomial f K[X]A and a subset {α1,αt} B
A, it is possible to determine whether f belongs to K[X]A
B
by just testing a few
linear inequalities in the valuations of the coefficients: a point α A is in the
support of the Newton Polygon if and only if
v(aα) v(aα )
α α
α α
+ v(aα )
α α
α α
for all α , α A with α α α . Inspired by this simple test, we introduce the
set S(B/A) Rt defined as the set of all vectors (v1, . . . , vt) Rt such that
vi vj
αi αk
αj αk
+ vk
αj αi
αj αk
for all 1 j i k t if and only if αi B. This means that a polynomial
f K[X]A belongs to K[X]A
B
if and only if (v(aα1 ), . . . , v(aαt )) S(B/A). In the
analysis of random univariate polynomials of Section 6, we will need the Lebesgue
measure of the set S(B/A)∩[0,
1]t,
which will be denoted P (B/A). Roughly speak-
ing, P (B/A) is the probability that the set of points {(α1,v1),..., (αt, vt)}, where
vi U[0, 1] are independent random variables, has Newton Polygon supported at B.
From the form of the equations defining these sets, note that (v1, . . . , vt) S(B/A)
if and only if (av1 +b, . . . , avt +b) S(B/A) for all a, b R, i.e. these sets are invari-
ant under rescaling and translations. In particular, the measure of S(B/A) [a, b]t
is equal to (b a)tP (B/A).
16
Previous Page Next Page