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α

: aα = 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 coeﬃcients: 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

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α

: aα = 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 coeﬃcients: 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