12

MART´

IN

AVENDA˜

NO AND ASHRAF IBRAHIM

Algorithm 1 Decide whether a system F = (f1, . . . , fn) of n polynomials in

K X1

±1,

. . . , Xn

±1

is semiregular at a given point w = (w1, . . . , wn) ∈

Rn.

In

case of semiregularity, print the number of solutions in

(K∗)n

with valuation vector

w.

1:

if w ∈

v(π)Zn

then

2:

print the system has no solutions in

(K∗)n

with valuation w

3:

return YES

4:

end if

5:

for i = 1, . . . , n do

6:

˜

f

i

← inw(fi)

7:

if

˜

f

i

is a monomial then

8:

print the system has no solutions in

(K∗)n

with valuation w

9:

return YES

10:

end if

11:

end for

12:

Jac(

˜)

F ← det(∂

˜

f

i

/∂Xj)

13:

if there is a solution of

˜

f 1(x) = · · · =

˜

fn(x) = Jac(

˜)(x)

F = 0 in

(k∗)n

then

14:

return NO

15:

end if

16:

s ← number of solutions of

˜

f

1

(x) = · · · =

˜

fn(x) = 0 in (k∗)n

17:

print the system has s solutions in (K∗)n with valuation w

18:

return YES

In case that only an estimation for the number of zeros is needed, the following

statement might be useful.

Corollary 3.6. Let F be a system of n polynomials in K X1

±1,

. . . , Xn

±1

. If

Trop(F ) is finite and F is semiregular at any w ∈ Trop(F ), then the number of

solutions of F in

(K∗)n

is

|ZK (F )| =

w∈Trop(F )∩v(π)Zn

|Zk(inw(F )| ≤ |Trop(F ) ∩

v(π)Zn|

·

|k∗|n

≤ |Trop(F )| ·

|k∗|n.

Note that when Trop(F ) is a finite set, then it has at most

n

i=1

(ti)

2

points,

where ti is the number of monomials of fi. Each Trop(fi) is contained in the union

of

(

ti

2

)

hyperplanes (see Lemma 2.1), and the intersection of n of these hyperplanes

(one in each Trop(fi)) determines at most one point in Trop(F ). In a

system F that satisfies the hypothesis of Corollary 3.6 has at most

(

t1

2

)particular,

· · ·

(

tn

2

)

|k∗|n

roots in (K∗)n, and all these roots are non-degenerate.

We conclude this section with a discussion of the univariate case. Consider

f =

∑t

i=1

aiXαi ∈ K[X]. In section 2, we showed that the tropical hypersurface of

f is the set of minus the slope of the segments of the lower hull of NP(f). For each

of these w ∈ Trop(f), the lower polynomial f

[w]

and initial form inw(f) are simply

the polynomials obtained by keeping only the terms with (αi, v(ai)) lying on the

segment of slope −w. For each w ∈ Trop(f), semiregularity at w means that either

w ∈ v(π)Z, in which case f has no solutions in

K∗

with valuation w, or inw(f)

has no degenerate zeros in

k∗.

In case of semiregularity at w ∈ Trop(f) ∩ v(π)Z,

our main result says that the number of roots of f in K∗ with valuation w and the

number of roots of inw(f) in k∗ coincide.

12

MART´

IN

AVENDA˜

NO AND ASHRAF IBRAHIM

Algorithm 1 Decide whether a system F = (f1, . . . , fn) of n polynomials in

K X1

±1,

. . . , Xn

±1

is semiregular at a given point w = (w1, . . . , wn) ∈

Rn.

In

case of semiregularity, print the number of solutions in

(K∗)n

with valuation vector

w.

1:

if w ∈

v(π)Zn

then

2:

print the system has no solutions in

(K∗)n

with valuation w

3:

return YES

4:

end if

5:

for i = 1, . . . , n do

6:

˜

f

i

← inw(fi)

7:

if

˜

f

i

is a monomial then

8:

print the system has no solutions in

(K∗)n

with valuation w

9:

return YES

10:

end if

11:

end for

12:

Jac(

˜)

F ← det(∂

˜

f

i

/∂Xj)

13:

if there is a solution of

˜

f 1(x) = · · · =

˜

fn(x) = Jac(

˜)(x)

F = 0 in

(k∗)n

then

14:

return NO

15:

end if

16:

s ← number of solutions of

˜

f

1

(x) = · · · =

˜

fn(x) = 0 in (k∗)n

17:

print the system has s solutions in (K∗)n with valuation w

18:

return YES

In case that only an estimation for the number of zeros is needed, the following

statement might be useful.

Corollary 3.6. Let F be a system of n polynomials in K X1

±1,

. . . , Xn

±1

. If

Trop(F ) is finite and F is semiregular at any w ∈ Trop(F ), then the number of

solutions of F in

(K∗)n

is

|ZK (F )| =

w∈Trop(F )∩v(π)Zn

|Zk(inw(F )| ≤ |Trop(F ) ∩

v(π)Zn|

·

|k∗|n

≤ |Trop(F )| ·

|k∗|n.

Note that when Trop(F ) is a finite set, then it has at most

n

i=1

(ti)

2

points,

where ti is the number of monomials of fi. Each Trop(fi) is contained in the union

of

(

ti

2

)

hyperplanes (see Lemma 2.1), and the intersection of n of these hyperplanes

(one in each Trop(fi)) determines at most one point in Trop(F ). In a

system F that satisfies the hypothesis of Corollary 3.6 has at most

(

t1

2

)particular,

· · ·

(

tn

2

)

|k∗|n

roots in (K∗)n, and all these roots are non-degenerate.

We conclude this section with a discussion of the univariate case. Consider

f =

∑t

i=1

aiXαi ∈ K[X]. In section 2, we showed that the tropical hypersurface of

f is the set of minus the slope of the segments of the lower hull of NP(f). For each

of these w ∈ Trop(f), the lower polynomial f

[w]

and initial form inw(f) are simply

the polynomials obtained by keeping only the terms with (αi, v(ai)) lying on the

segment of slope −w. For each w ∈ Trop(f), semiregularity at w means that either

w ∈ v(π)Z, in which case f has no solutions in

K∗

with valuation w, or inw(f)

has no degenerate zeros in

k∗.

In case of semiregularity at w ∈ Trop(f) ∩ v(π)Z,

our main result says that the number of roots of f in K∗ with valuation w and the

number of roots of inw(f) in k∗ coincide.

12