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
Previous Page Next Page