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 coeﬃcients 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 coeﬃcients 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

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 coeﬃcients 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 coeﬃcients 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