18
MART´
IN
AVENDA˜
NO AND ASHRAF IBRAHIM
three or more monomials is
f1w]. [
The point w is the unique solution of the sys-
tem (5.1) for some α1,β1 A1,...,αn,βn An, and in particular, the monomi-
als aα1
(1)
Xα1
and aβ1
(1)
Xβ1
are in
f1w]. [
Since
f1w] [
has three or more terms, there
exists γ1 A1 \ {α1,β1} such that the term aγ1
(1)
Xγ1
is in
f1w]. [
The equation
v(aγ1
(1)
) + γ1 · w = v(aα1
(1)
) + α1 · w, where w is the unique solution of (5.1) expressed
as a linear function of v(aα1
(1)
), v(aβ1
(1)
), . . . ,
v(aαn)),v(aβn)) (n (
n
gives a non-trivial linear
equation for the valuation of the coefficients of F , thus restricting μ to a hyperplane
(that depends only on the choice of α1,β1,γ1,...,αn,βn). We conclude by taking
the union of all these possible hyperplanes.
According to Algorithm 2, a system F can fail to be regular for three different
reasons (see lines 3, 8 and 17): when the tropical prevariety is not finite, when
some lower polynomial has more than two terms, or when char(k) divides the
determinant of certain invertible matrices. By Theorem 5.2, the first two do not
occur for tropically generic systems, and in particular, if char(k) = 0, then any
tropically generic system is regular. The same idea works for any characteristic
coprime to all the determinants that can arise in the test in line 16.
Corollary 5.3. Let A1,..., An
Zn
be nonempty finite sets. Assume that
char(k) = 0 or that char(k) is coprime to the determinant of all invertible matrices
M = [α1 β1; . . . ; αn βn] with αi,βi Ai for i = 1, . . . , n. Then, any trop-
ically generic system of polynomials F = (f1, . . . , fn) in K X1
±1,
. . . , Xn
±1
with
supp(fi) = Ai for i = 1, . . . , n is regular.
6. The expected number of roots of a random polynomial
In this section we restrict the discussion to univariate polynomials. Let A Z
be a nonempty finite set. Assume that the characteristic of the residue field is either
zero or coprime to α β for all α, β A with α = β. This assumption ensures,
by Corollary 5.3, that any tropically generic polynomial f K[X] with support
A is regular. Since we have an explicit formula for the number of roots of regular
polynomials in
K∗,
we should be able to obtain the expected number of roots of f
in
K∗,
provided that we select the coefficients of f at random with a distribution
that produces tropically generic polynomials with probability 1.
Let D1 be a probability distribution on k∗, let D2 be a probability distribution
on 1+M, and let M 0. We will select elements in K∗ at random by selecting their
valuation uniformly in [−M, M]∩v(π)Z, their first digit according to D1, and their
tail in 1 + M according to D2. This procedure induces a probability distribution
in K∗ that extends to a distribution in K[X]A = {f K[X] : supp(f) = A}.
Denote by E(A,D1,D2,M,K) the expected number of roots in K∗ of a polynomial
f K[X]A chosen at random with this distribution. Since the number of roots of
these polynomials can not exceed their degree, we have that E(A,D1,D2,M,K)
maxα,β∈A β|. The main goal of this section is to find the value of
E(A,D1,D2,K) = lim
M→∞
E(A,D1,D2,M,K)
for several fields K and probability distributions D1 and D2.
Lemma 6.1. Consider the probability distribution in K[X]A induced by D1, D2,
and M 0. Assume that char(k) is zero or coprime to α β for all α, β A with
18
Previous Page Next Page