MULTIVARIATE ULTRAMETRIC ROOT COUNTING 19
α = β. Then, the probability that a random f K[X]A is not regular approches
zero as M ∞.
Proof. Let t = |A| and A = {α1,...,αt}. By Corollary 5.3, there are
hyperplanes H1,...,Hn
Rt
such that any polynomial f =
∑t
i=1
aiXαi
with
(v(a1), . . . , v(at)) ∪j=1Hj
n
is regular. In particular, it is enough to show that the
probability that a random f K[X]A has coefficients with valuation in ∪j=1Hjn
goes to zero as M ∞. Note that this probability does not depend on the distri-
butions D1 and D2. Moreover, since the valuation of the coefficients is selected at
random in the box ([−M, M] v(π)Z)t with uniform distribution, the probability
of being in the union of n hyperplanes is less than or equal to n/(2[M/v(π)] + 1)
(each hyperplane contains at most 1/(2[M/v(π)] + 1) of the points in the box). As
the size of the box increases, this probability approaches zero.
By Lemma 6.1, the probability that a random f K[X]A is regular approaches
1 as M goes to infinity. Besides, we have shown in Proposition 4.2 (or in Algo-
rithm 2) that the number of solutions of a regular system does not depend on the
tail of the coefficients. In particular, the value of E(A,D1,D2,K) does not depend
on D2, and for this reason, it will be simply written as E(A,D1,K).
Before stating the main result, we need to fix some notation. For any γ N, we
denote by Ek(γ, D1) the expected number of roots in k∗ of the binomial aXγ +b with
coefficients a, b k∗ chosen at random (independently) according to the distribution
D1. For instance, when k is algebraically closed, we have Ek(γ, D1) = γ regardless
of the distribution D1. If k is a finite field and D1 is the uniform distribution in
k∗,
then Ek(γ, D1) = 1, since the number of roots of

= −b/a is either zero or
gcd(|k∗|,
γ), and the latter happens only when −b/a is a γ-th power in
k∗
which
occurs with probability 1/
gcd(|k∗|,
γ). A similar situation arises in the case k = R
and D1 a distribution such that R
0
and R
0
have each probability 1/2: if γ is
odd, then

= −b/a has always one real root, and if γ is even, the number of
roots is either 0 or 2 depending on whether sgn(ab) is 1 or −1, but in both cases
we have Ek(γ, D1) = 1.
k D1 Ek(γ, D1)
k alg. closed any γ
k = R Prob(R
0
) = Prob(R
0
) = 1/2 1
|k| +∞ uniform in
k∗
1
Theorem 6.1. Let A = {α1 α2 · · · αt} Z finite with t 2. Assume that
char(k) = 0 or that char(k) is coprime to α β for any pair of elements α, β A
with α = β. Let D1 be a probability distribution in k∗. Then
E(A,D1,K) =
{α1,αt}⊆B⊆A
P (B/A)
|B|−1
i=1
Ek(βi+1 βi,D1)
βi+1 βi
where B = {α1 = β1 β2 · · · β|B| = αt}.
Proof. Let D2 be any probability distribution in 1 + M and let M 0.
Random polynomials f =

α∈A
aαXα K[X]A will be chosen according to D1,
D2 and M. For each subset B = {α1 = β1 · · · β|B| = αt} A, denote by
19
Previous Page Next Page