MULTIVARIATE ULTRAMETRIC ROOT COUNTING 15

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

K X1

±1,

. . . , Xn

±1

is regular. In case of regularity, it prints the number of solutions

in

(K∗)n.

1:

compute Trop(F ) ← Trop(f1) ∩ · · · ∩ Trop(fn)

2:

if |Trop(F )| = ∞ then

3:

return NO

4:

end if

5:

s ← 0

6:

for all w ∈ Trop(F ) do

7:

if

f1w],...,fnw] [ [

are not all binomials then

8:

return NO

9:

else

10:

write each

fi[w]

as

aiXαi

−

biXβi

for i = 1, . . . , n.

11:

M ← [α1 − β1; . . . ; αn − βn]

12:

compute the Smith Normal Form PDQ of M

13:

ρ ← (δ(b1/a1), . . . ,

δ(bn/an))P

−1

14:

if w ∈

v(π)Zn

and ρi is a di-th power in

k∗

for all i = 1, . . . , n then

15:

if char(k) | d1 · · · dn then

16:

return NO

17:

else

18:

ei ← |{ξ ∈

k∗

:

ξdi

= 1}| for i = 1, . . . , n

19:

s ← s +

n

i=1

ei

20:

end if

21:

end if

22:

end if

23:

end for

24:

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

25:

return YES

Algorithm 2 is presented above in pseudo-code with the maximum generality,

in order to match the notation and logic behind Proposition 4.2. In any real imple-

mentation of the algorithm, the test in line 15 and the formula in line 19, should

be replaced by some specific instructions depending on the field k.

• When k is a finite field of cardinality q = |k|, the test in line 15 can

be rewritten as

ρiq−1)/ ( gcd(q−1,di)

= 1, and line 19 can be replaced by

ei ← gcd(q − 1, di).

• When k is algebraically closed, line 15 can be simply skipped, since this

tests always yields true, and line 19 becomes ei ← di, or more simply,

line 20 becomes s ← s + | det(M)| and line 19 is deleted.

• When char(k) = 0, the test made in line 16 is not necessary, since by

Lemma 4.2, the matrix M in line 11 has non-zero determinant, and there-

fore d1 · · · dn = det(D) = | det(M)| = 0.

In the univariate case, regular polynomials are very easy to describe. First of

all, the tropical hypersurface of a univariate polynomial is always finite. Moreover,

for each w in the tropical set, the lower polynomial f

[w]

contains all the monomials

aXα of f such that the point (α, v(a)) lies on the lower edge of NP(f) with slope

w. This means that, in order to have regularity, the lower edges of NP(f) must not

15

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

K X1

±1,

. . . , Xn

±1

is regular. In case of regularity, it prints the number of solutions

in

(K∗)n.

1:

compute Trop(F ) ← Trop(f1) ∩ · · · ∩ Trop(fn)

2:

if |Trop(F )| = ∞ then

3:

return NO

4:

end if

5:

s ← 0

6:

for all w ∈ Trop(F ) do

7:

if

f1w],...,fnw] [ [

are not all binomials then

8:

return NO

9:

else

10:

write each

fi[w]

as

aiXαi

−

biXβi

for i = 1, . . . , n.

11:

M ← [α1 − β1; . . . ; αn − βn]

12:

compute the Smith Normal Form PDQ of M

13:

ρ ← (δ(b1/a1), . . . ,

δ(bn/an))P

−1

14:

if w ∈

v(π)Zn

and ρi is a di-th power in

k∗

for all i = 1, . . . , n then

15:

if char(k) | d1 · · · dn then

16:

return NO

17:

else

18:

ei ← |{ξ ∈

k∗

:

ξdi

= 1}| for i = 1, . . . , n

19:

s ← s +

n

i=1

ei

20:

end if

21:

end if

22:

end if

23:

end for

24:

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

25:

return YES

Algorithm 2 is presented above in pseudo-code with the maximum generality,

in order to match the notation and logic behind Proposition 4.2. In any real imple-

mentation of the algorithm, the test in line 15 and the formula in line 19, should

be replaced by some specific instructions depending on the field k.

• When k is a finite field of cardinality q = |k|, the test in line 15 can

be rewritten as

ρiq−1)/ ( gcd(q−1,di)

= 1, and line 19 can be replaced by

ei ← gcd(q − 1, di).

• When k is algebraically closed, line 15 can be simply skipped, since this

tests always yields true, and line 19 becomes ei ← di, or more simply,

line 20 becomes s ← s + | det(M)| and line 19 is deleted.

• When char(k) = 0, the test made in line 16 is not necessary, since by

Lemma 4.2, the matrix M in line 11 has non-zero determinant, and there-

fore d1 · · · dn = det(D) = | det(M)| = 0.

In the univariate case, regular polynomials are very easy to describe. First of

all, the tropical hypersurface of a univariate polynomial is always finite. Moreover,

for each w in the tropical set, the lower polynomial f

[w]

contains all the monomials

aXα of f such that the point (α, v(a)) lies on the lower edge of NP(f) with slope

w. This means that, in order to have regularity, the lower edges of NP(f) must not

15