The density of polynomials of degree n over ℤ_{p} having exactly r roots in ℚ_{p}

Manjul Bhargava, John Cremona, Tom Fisher, and Stevan Gajović

March 26, 2021

Abstract We determine the probability that a random polynomial of degree n over ℤ_{p} has exactly r roots in ℚ_{p}, and show that it is given by a rational function of p that is invariant under replacing p by 1/p.

1 Introduction

Let f(x) = c_{n}x^{n} +c_{n−1}x^{n−1} +⋯+c_{0} be a random polynomial having coefficients c_{0}, c_{1}, …, c_{n} ∈ ℤ_{p}. In this paper, we determine the probability that f has a root in ℚ_{p}, and more generally the probability that f has exactly r roots in ℚ_{p}. More precisely, we normalise the additive p-adic Haar measure μ on the set of coefficients ℤ_{p}^{n+1} such that μ(ℤ_{p}^{n+1}) = 1, and determine the density μ(S_{r}) of the set S_{r} of degree n polynomials in ℤ_{p}[x] having exactly r roots in ℚ_{p}. We prove that this density μ(S_{r}) is given by a rational function ρ^{∗}(n, r; p) of p, which satisfies the remarkable identity

ρ^{∗}(n, r; p) = ρ^{∗}(n, r; 1/p)

for all n, r and p. We also prove that if X_{n}(p) is the random variable giving the number of ℚ_{p}-roots of a random polynomial f ∈ ℤ_{p}[x] of degree n, then the d-th moment of X_{n}(p) is independent of n provided that n ≥ 2d − 1.

Let us now more formally define the probabilities, expectations and generating functions required to state our main results. Fix a prime p and, for 0 ≤ r ≤ n, let ρ^{∗}(n, r) := ρ^{∗}(n, r; p) denote the density of polynomials of degree n over ℤ_{p} having exactly r roots in ℚ_{p}. This is also the probability that a binary form of degree n over ℤ_{p} has exactly r roots in ℙ^{1}(ℚ_{p}). For 0 ≤ d ≤ n, set

ρ(n, d) = ∑_{r=0}^{n} \binom{r}{d}ρ^{∗}(n, r).  (1)

Thus ρ(n, d) is the expected number of d-sets^{1} of ℚ_{p}-roots. For fixed n, determining ρ(n, d) for all d is equivalent to determining ρ^{∗}(n, r) for all r, via the inversion formula

ρ^{∗}(n, r) = ∑_{d=0}^{n}(−1)^{d−r}\binom{d}{r}ρ(n, d).  (2)

1We find it convenient to refer to a set of size d as a “d-set”.

Equations (1) and (2) are equivalent to the standard observation that a probability distribution is determined by its moments; the formulation in terms of d-sets is most convenient for our purposes.

Analogous to ρ(n, d), let α(n, d) (resp. β(n, d)) denote the expected number of d-sets of ℚ_{p}- roots of monic polynomials of degree n over ℤ_{p} (resp. monic polynomials of degree n over ℤ_{p} that reduce to x^{n} modulo p). Define the generating functions:

A_{d}(t) = (1 − t) ∑_{n=0}^{∞} α(n, d)t^{n};

B_{d}(t) = (1 − t) ∑_{n=0}^{∞} β(n, d)t^{n};

R_{d}(t) = (1 − t)(1 − pt) ∑_{n=0}^{∞}(p^{n} + p^{n−1} + ⋯ + 1)ρ(n, d)t^{n}.

Then we prove the following theorem.

Theorem 1. Let p be a prime number and n, d any integers such that 0 ≤ d ≤ n. Then:

(a) For fixed n and d, the expectations α(n, d; p), β(n, d; p) and ρ(n, d; p) are rational functions of p, which satisfy the identities:

ρ(n, d; p) = ρ(n, d; 1/p);  (3)
α(n, d; p) = β(n, d; 1/p).  (4)

(b) We have the following power series identities in two variables t and u:

∑_{d=0}^{∞} A_{d}(pt)u^{d} = (∑_{d=0}^{∞} B_{d}(t)u^{d})^{p};  (5)

∑_{d=0}^{∞} R_{d}(t)u^{d} = (∑_{d=0}^{∞} A_{d}(pt)u^{d}) (∑_{d=0}^{∞} B_{d}(t)u^{d}) = (∑_{d=0}^{∞} B_{d}(t)u^{d})^{p+1} ;  (6)

B_{d}(t) − tB_{d}(t/p) = Φ (A_{d}(t) − tA_{d}(pt)) ,  (7)

where Φ is the operator on power series that multiplies the coefficient of t^{n} by p^{−\binom{n}{2}}.

(c) The power series A_{d}, B_{d} and R_{d} are in fact polynomials of degree at most 2d. Moreover, we have α(n, d) = A_{d}(1) and β(n, d) = B_{d}(1) for n ≥ 2d, and ρ(n, d) = R_{d}(1) for n ≥ 2d − 1. Thus the expectations α(n, d), β(n, d), and ρ(n, d) are independent of n provided that n is sufficiently large relative to d.

We observe that A_{d} and B_{d} (for d = 0, 1, 2, …) are the unique power series satisfying the relations (5) and (7) together with the requirements that A_{d} and B_{d} are O(t^{d}), A_{0} = B_{0} = 1 and A_{1} and B_{1} are t + O(t^{2}). This last requirement is needed, since otherwise we could replace A_{d} and B_{d} by λ^{d}A_{d} and λ^{d}B_{d} where λ is a constant. This uniqueness statement is easily proved by induction on d and n. The power series R_{d} are then uniquely determined by (6).

While we have stated all our results above in terms of the ring ℤ_{p}, the generalisation to any complete discrete valuation ring with finite residue field (as considered in [3]) is immediate.

1.1 Relation to previous work

The study of the distribution of the number of zeros of random polynomials has a long and interesting history. Over the real numbers, the study goes back to at least Bloch and Pólya [2], who proved asymptotic bounds on the expected number of real zeros of polynomials of degree n that have coefficients independently and uniformly distributed in {−1, 0, 1}. Further significant advances on the problem were made by Littlewood and Offord [9, 10, 11] for various other distributions on the coefficients.

An exact formula for the expected number of real zeros of a random degree n polynomial over ℝ—whose coefficients are each identically, independently, and normally distributed with mean zero—was first determined in the landmark 1943 work of Kac [7], which influenced much of the extensive work to follow. In particular, in 1974, Maslova [12, 13] determined asymptotically all higher moments for the number of zeros of a random real Kac polynomial in the limit as the degree n tends to infinity. For excellent surveys of the literature and further related results and references regarding the number of real zeros of random real polynomials, see [15, §1.1] and [14, §1].

The corresponding problems and methods over p-adic fields were first considered by Evans [6], who determined, for suitably random families of d polynomials in d variables over ℤ_{p}, the expected number of common zeros in ℤ_{p}^{d}. In the case d = 1, these results were taken further by Buhler, Goldstein, Moews, and Rosenberg [3], Caruso [4], Limmer [8], Shmueli [16], and Weiss [17]. These papers were concerned primarily with determining the expected number of roots for polynomials of degree n over the p-adics, the n-th factorial moments for polynomials of degree n, or all moments for polynomials of degree n ≤ 3.

The current paper gives a method for computing all moments for the number of zeros of random p-adic polynomials of degree n in one variable for any degree n. Indeed, Theorem 1, together with the uniqueness statement that follows it, enables us to explicitly compute the probabilities and moments ρ^{∗}(n, r), ρ(n, d), α(n, d), and β(n, d) for any values of n, r, and d. We may similarly compute the analogues α^{∗}(n, r) and β^{∗}(n, r) of ρ^{∗}(n, r); i.e., α^{∗}(n, r) (resp. β^{∗}(n, r)) denotes the probability that a random monic polynomial of degree n (resp. monic polynomial reducing to x^{n} modulo p) has exactly r roots over ℚ_{p} (equivalently, ℤ_{p}). Indeed, the formulas (1) and (2) continue to hold when the symbol ρ is replaced by α (resp. β). In particular, we deduce from (2) that ρ^{∗}(n, r), α^{∗}(n, r), and β^{∗}(n, r) all satisfy the same symmetry properties (3) and (4) as their unstarred counterparts.

We thus recover all previously known values of ρ^{∗}, α^{∗}, β^{∗}, ρ, α, and β, including that ρ(n, 1)=1 for all n (a result of Caruso [4]), that α(n, 1) = p/(p + 1) (a result of Shmueli [16]), and the values of ρ^{∗}(n, n) for all n (as determined by Buhler, Goldstein, Moews, and Rosenberg [3]).

1.2 Examples

We illustrate some particularly interesting cases of Theorem 1 below.

1.2.1 The expected number of roots of a random p-adic polynomial

By definition, the quantities ρ(n, 1), α(n, 1), and β(n, 1) represent the expected number of roots over ℚ_{p} of a random polynomial over ℤ_{p} of degree n, a random monic polynomial over ℤ_{p} of degree n, and a random monic polynomial over ℤ_{p} of degree n reducing to x^{n} (mod p), respectively.

Setting d = 1, we compute

A_{1}(t) = t − \frac{1}{p + 1}t^{2}, B_{1}(t) = t − \frac{p}{p + 1}t^{2}, R_{1}(t) = (p + 1)t − pt^{2}.

Therefore,

α(n, 1) = \{ \begin{matrix}1 & if n = 1, \\ \frac{p}{p + 1} & if n ≥ 2, \end{matrix} β(n, 1) = \{ \begin{matrix}1 & if n = 1, \\ \frac{1}{p + 1} & if n ≥ 2, \end{matrix}

and

ρ(n, 1) = 1 for all n ≥ 1,

This recovers, in particular, the aforementioned results of Caruso [4] and Shmueli [16] on the values of ρ(n, 1) and α(n, 1), respectively, who obtained them via quite different methods (though their methods are related to those used by Kac [7] cited above).

1.2.2 The second moment of the number of ℚ_{p}-roots of a random p-adic polynomial

Next, we determine the expected number of 2-sets (i.e., unordered pairs) of ℚ_{p}-roots of a polynomial over ℤ_{p} of degree n. Setting d = 2, we compute

2A_{2}(t) = (p/(p + 1))t^{2} − p(p + 1)(2p^{3} + p + 1)ηt^{3} + p^{4}ηt^{4},
2B_{2}(t) = (1/(p + 1))t^{2} − p(p + 1)(p^{3} + p^{2} + 2)ηt^{3} + p^{2}ηt^{4},
2R_{2}(t) = (p^{2} + p + 1)t^{2} − p(p + 1)^{3}(2p^{4} + 3p^{2} + 2)ηt^{3} + p^{2}(p + 1)^{2}(p^{4} + p^{2} + 1)ηt^{4},

where η = 1/((p + 1)^{2}(p^{4} + p^{3} + p^{2} + p + 1)). Therefore,

2α(n, 2) = \{ \begin{matrix}p/(p + 1) & if n = 2, \\ p^{3}(p^{3} + 1)η & if n = 3, \\ p^{3}(p^{3} + p + 1)η & if n ≥ 4, \end{matrix} 2β(n, 2) = \{ \begin{matrix}1/(p + 1) & if n = 2, \\ (p^{3} + 1)η & if n = 3, \\ (p^{3} + p^{2} + 1)η & if n ≥ 4, \end{matrix}

and

ρ(2, 2) = 1/2, 2ρ(n, 2) = (p^{2} + 1)^{2}/(p^{4} + p^{3} + p^{2} + p + 1) for all n ≥ 3.

There is no difficulty in extending these calculations to larger values of d.

1.2.3 The density of p-adic polynomials of degree n having r roots

Once we have computed the expectations ρ(n, d), α(n, d), and β(n, d), we may use (2) and its analogues for α and β to compute the probabilities ρ^{∗}(n, r), α^{∗}(n, r), and β^{∗}(n, r). Since the probability of a repeated root is zero, we always have ρ^{∗}(n, n − 1) = α^{∗}(n, n − 1) = β^{∗}(n, n − 1) = 0.

For n = 2 and 3, the probabilities ρ^{∗}(n, r) can already be deduced from results in [1], [3] and [4]. Namely, we have

ρ^{∗}(2, 0) = ρ^{∗}(2, 2) = 1/2,

and

ρ^{∗}(3, 0) = 2γ, ρ^{∗}(3, 1) = 1 − 3γ, ρ^{∗}(3, 3) = γ,

where

γ = \frac{(p^{2} + 1)^{2}}{6(p^{4} + p^{3} + p^{2} + p + 1)}.

For quartic polynomials in ℤ_{p}[x], the probability of having 0, 1, 2 or 4 roots in ℚ_{p} is given by

ρ^{∗}(4, 0) = \frac{δ}{8}(3p^{12} + 5p^{11} + 8p^{10} + 12p^{9} + 13p^{8} + 12p^{7} + 17p^{6} + 12p^{5} + 13p^{4} + 12p^{3} + 8p^{2} + 5p + 3),
ρ^{∗}(4, 1) = \frac{δ}{3}(p^{12} + 2p^{11} + 4p^{10} + 3p^{9} + 6p^{8} + 7p^{7} + 2p^{6} + 7p^{5} + 6p^{4} + 3p^{3} + 4p^{2} + 2p + 1),
ρ^{∗}(4, 2) = \frac{δ}{4}(p^{12} + 3p^{11} + 2p^{10} + 6p^{9} + 5p^{8} + 4p^{7} + 9p^{6} + 4p^{5} + 5p^{4} + 6p^{3} + 2p^{2} + 3p + 1),
ρ^{∗}(4, 4) = \frac{δ}{24}(p^{12} − p^{11} + 4p^{10} + 3p^{8} + 4p^{7} − p^{6} + 4p^{5} + 3p^{4} + 4p^{2} − p + 1),

where

δ = \frac{(p − 1)^{2}}{(p^{5} − 1)(p^{9} − 1)}.

The last of these probabilities, ρ^{∗}(4, 4), was determined in [3], where it is denoted r_{4}^{nm}. As predicted by Theorem 1(a), the sequence of coefficients in each numerator and in each denominator is palindromic. Again, there is no difficulty in computing ρ^{∗}(n, r) for larger values of n.

For n = 2 and 3, the probabilities α^{∗}(n, r) were computed by Limmer [8, p. 27] and Weiss [17, Theorem 5.3], who only considered primes p > n. Our work shows that the same formulas hold for all primes p. Namely, we have

α^{∗}(2, 0) = \frac{1}{2} \frac{p + 2}{p + 1}, α^{∗}(2, 2) = \frac{1}{2} \frac{p}{p + 1};
α^{∗}(3, 0) = \frac{1}{3} \frac{p^{4} + p^{3} + 3p^{2} + 3}{p^{4} + p^{3} + p^{2} + p + 1},
α^{∗}(3, 1) = \frac{1}{2} \frac{p^{5} + 3p^{4} + p^{3} + 2p^{2} + 2p}{(p + 1)(p^{4} + p^{3} + p^{2} + p + 1)},
α^{∗}(3, 3) = \frac{1}{6} \frac{p^{5} − p^{4} + p^{3}}{(p + 1)(p^{4} + p^{3} + p^{2} + p + 1)}.

For monic quartic polynomials in ℤ_{p}[x], the probability of having 0, 1, 2 or 4 roots in ℤ_{p} is given by

α^{∗}(4, 0) = \frac{1}{8} \frac{3p^{11} + 8p^{10} + 6p^{9} + 2p^{8} − 3p^{6} + 4p^{5} − 4p^{3} − 8p − 8}{(p + 1)^{2}(p^{9} − 1)},
α^{∗}(4, 1) = \frac{1}{3} \frac{p^{14} + 2p^{12} − 6p^{11} + 9p^{10} − 9p^{9} + 2p^{8} + 3p^{7} − 2p^{6} − 3p^{5} + 3p^{4} − 3p^{2} + 3p}{(p^{5} − 1)(p^{9} − 1)},
α^{∗}(4, 2) = \frac{1}{4} \frac{p^{16} + 2p^{15} − 4p^{14} + 2p^{13} + 2p^{12} − 6p^{11} + 4p^{10} + 2p^{9} − 6p^{8} + 2p^{7} + p^{6} − 2p^{5} + 2p^{3}}{(p + 1)^{2}(p^{5} − 1)(p^{9} − 1)} ,
α^{∗}(4, 4) = \frac{1}{24} \frac{p^{16} − 4p^{15} + 6p^{14} − 2p^{13} − 4p^{12} + 6p^{11} − 4p^{10} − 2p^{9} + 6p^{8} − 4p^{7} + p^{6}}{(p + 1)^{2}(p^{5} − 1)(p^{9} − 1)} .

By the analogue of (4) for α^{∗} and β^{∗}, we may obtain the values of β^{∗} from those of α^{∗} by substituting 1/p for p.

1.2.4 The density of p-adic polynomials that split completely

The quantities ρ(n, n) and α(n, n) represent the probabilities that a (general or monic) polynomial of degree n over ℤ_{p} splits completely over ℚ_{p}. These probabilities were previously computed by Buhler, Goldstein, Moews, and Rosenberg [3]. We may recover these probabilities from Theorem 1 as follows. If we replace A_{d}, B_{d}, and R_{d} by their coefficients of t^{d} (these being the terms of lowest degree in t), then Theorem 1(b) reduces to

∑_{n=0}^{∞} α(n, n)(pt)^{n} = (∑_{n=0}^{∞} β(n, n)t^{n})^{p}  (8)

∑_{n=0}^{∞}(p^{n} + p^{n−1} + ⋯ + 1)ρ(n, n)t^{n} = (∑_{n=0}^{∞} β(n, n)t^{n})^{p+1}  (9)

β(n, n) = p^{−\binom{n}{2}}α(n, n),  (10)

from which one can inductively compute ρ(n, n), α(n, n), and β(n, n) for all n. In [3], Buhler et al. write r_{n}^{nm}, r_{n}, and p^{n}s_{n} for ρ(n, n), α(n, n), and β(n, n), respectively. Our equations (8) and (9) appear as Equations (1-2) and (3-1) in their paper; and their Lemma 4.1(iv), which states that r_{n}(q) = r_{n}(1/q)q^{\binom{n}{2}}, follows by combining our general Equation (4) with (10). The explicit values of ρ(n, n) = ρ^{∗}(n, n), α(n, n) = α^{∗}(n, n) , and β(n, n) = β^{∗}(n, n) for n ≤ 4 were recorded in §1.2.3.

1.2.5 The density of p-adic polynomials with a root

We may also compute 1 − ρ^{∗}(n, 0), the probability that a polynomial of degree n over ℤ_{p} has at least one root over ℚ_{p}. Indeed, as a special case of (2), we have ρ^{∗}(n, 0) = ∑_{d=0}^{n}(−1)^{d}ρ(n, d), and likewise for the α’s and β’s. In terms of generating functions, we have

A^{∗}(t) := (1 − t) ∑_{n=0}^{∞} α^{∗}(n, 0)t^{n} = ∑_{d=0}^{∞}(−1)^{d}A_{d}(t)

B^{∗}(t) := (1 − t) ∑_{n=0}^{∞} β^{∗}(n, 0)t^{n} = ∑_{d=0}^{∞}(−1)^{d}B_{d}(t)

and

R^{∗}(t) := (1 − t)(1 − pt) ∑_{n=0}^{∞}(p^{n} + p^{n−1} + ⋯ + 1)ρ^{∗}(n, 0)t^{n} = ∑_{d=0}^{∞}(−1)^{d}R_{d}(t).

Specialising Theorem 1(b) by setting u = −1 gives

A^{∗}(pt) = B^{∗}(t)^{p}  (11)
R^{∗}(t) = A^{∗}(pt)B^{∗}(t) = B^{∗}(t)^{p+1}  (12)
B^{∗}(t) − tB^{∗}(t/p) = Φ(A^{∗}(t) − tB^{∗}(pt))  (13)

where Φ is as before.

We may therefore use (11) and (13) to recursively solve for α^{∗}(n, 0) and β^{∗}(n, 0), and then compute ρ^{∗}(n, 0) using (12). The explicit values of α^{∗}(n, 0), β^{∗}(n, 0), and ρ^{∗}(n, 0) for n ≤ 4 were recorded in §1.2.3.

1.2.6 Large p limits

We note that α(n, d), ρ(n, d), α^{∗}(n, r), and ρ^{∗}(n, r) are rational functions in p whose numerators and denominators have the same degree. Hence, for fixed n, d, and r, we may compute the limits of these functions as p tends to infinity. Meanwhile, β(n, d) and β^{∗}(n, r) are rational functions in p whose denominator has higher degree than the numerator in most cases. Thus, a correction factor of a power of p is needed to make the limit finite and nonzero. We have the following proposition.

Proposition 1.1. (a) Let 0 ≤ d ≤ n be integers, and let k = min(d + 1, n). Then

lim_{p→∞} α(n, d) = lim_{p→∞} ρ(n, d) = lim_{p→∞} p^{\binom{k}{2}}β(n, d) = \frac{1}{d!}.

(b) Let 0 ≤ r ≤ n be integers. Then

lim_{p→∞} ρ^{∗}(n, r) = lim_{p→∞} α^{∗}(n, r) = ∑_{d=0}^{n}(−1)^{d−r}\binom{d}{r}\frac{1}{d!} = \frac{1}{r!} ∑_{d=0}^{n−r}(−1)^{d} \frac{1}{d!}.

Hence, if we also let n → ∞, we obtain

lim_{n→∞} lim_{p→∞} ρ^{∗}(n, r) = lim_{n→∞} lim_{p→∞} α^{∗}(n, r) = \frac{1}{r!}e^{−1}.

(c) Finally, let 0 ≤ r ≤ n be integers, and let k = min(r + 1, n). If r ≠ n − 1 then

lim_{p→∞} p^{\binom{k}{2}}β^{∗}(n, r) = \frac{1}{r!}.

We prove these claims in Section 4.

1.3 A general conjecture

Theorem 1(a) naturally leads us to formulate a much more general conjecture. Namely, we conjecture that the density of polynomials of degree n over ℤ_{p} cutting out étale extensions of ℚ_{p} of degree n in which p has any given splitting type is a rational function of p satisfying the identities (3) and (4).

Recall that a splitting type of degree n is a tuple σ = (d_{1}^{e_{1}} d_{2}^{e_{2}} ⋯ d_{t}^{e_{t}}), where the d_{j} and e_{j} are positive integers satisfying ∑ d_{j}e_{j} = n. We allow repeats in the list of symbols d_{j}^{e_{j}}, but the order in which they appear does not matter. To make it clear when two splitting types are the same, we could for example order the pairs (d_{j}, e_{j}) lexicographically. Exponents e_{j} = 1 may be omitted.

For an étale extension K/ℚ_{p} of degree n, we define the symbol (K, p) to be the splitting type σ = (d_{1}^{e_{1}} d_{2}^{e_{2}} ⋯ d_{t}^{e_{t}}) if p factors in K as P_{1}^{e_{1}}P_{2}^{e_{2}} ⋯ P_{t}^{e_{t}}, where P_{1}, P_{2}, …, P_{t} are primes in K having residue field degrees d_{1}, d_{2}, …, d_{t}, respectively. We say that p has splitting type σ in K if (K, p) = σ.

We then make the following conjecture.

Conjecture 1.2. Let σ be any splitting type of degree n, and set

ρ(n, σ; p) := density of polynomials f ∈ ℤ_{p}[x] of degree n
such that K:=ℚ_{p}[x]/f(x) is étale over ℚ_{p} and (K, p) = σ,
α(n, σ; p) := density of monic polynomials f ∈ ℤ_{p}[x] of degree n
such that K:=ℚ_{p}[x]/f(x) is étale over ℚ_{p} and (K, p) = σ,
β(n, σ; p) := density of monic polynomials f ∈ ℤ_{p}[x] of degree n with f(x) ≡ x^{n} (mod p)
such that K:=ℚ_{p}[x]/f(x) is étale over ℚ_{p} and (K, p) = σ.

Then ρ(n, σ; p), α(n, σ; p), and β(n, σ; p) are rational functions of p and satisfy the identities:

ρ(n, σ; p) = ρ(n, σ; 1/p);  (14)
α(n, σ; p) = β(n, σ; 1/p).  (15)

We have proven that Conjecture 1.2 holds in the quadratic and cubic cases. For example,

ρ(2, (11); p) = 1/2
ρ(2, (2); p) = 1/2 − p/(p^{2} + p + 1)
ρ(2, (1^{2}); p) = p/(p^{2} + p + 1)
ρ(3, (111); p) = (1/6)(p^{4} + 2p^{2} + 1)/(p^{4} + p^{3} + p^{2} + p + 1)
ρ(3, (12); p) = (1/2)(p^{4} + 1)/(p^{4} + p^{3} + p^{2} + p + 1)
ρ(3, (3); p) = (1/3)(p^{4} − p^{2} + 1)/(p^{4} + p^{3} + p^{2} + p + 1)
ρ(3, (1^{2}1); p) = (p^{3} + p)/(p^{4} + p^{3} + p^{2} + p + 1)
ρ(3, (1^{3}); p) = p^{2}/(p^{4} + p^{3} + p^{2} + p + 1).

Note again that the numerators and denominators are all palindromic, and thus these expressions satisfy (14). Analogous formulas hold for the α’s and β’s that satisfy (15). In particular, these formulas hold for all p, including p = 2 and p = 3.

Theorem 1(a) may also be viewed as a special case of Conjecture 1.2, since the density ρ^{∗}(n, r; p) of polynomials of degree n over ℤ_{p} having exactly r roots over ℚ_{p} is simply the sum of the densities ρ(n, σ; p) over all splitting types σ having exactly r 1’s (and similarly for the α’s and β’s); thus if the equalities (14) and (15) hold for all ρ(n, σ; p), then they will also hold for ρ^{∗}(n, r) and ρ(n, d) (and similarly for the α’s and β’s), implying Theorem 1(a).

1.4 Methods and organization of the paper

In Section 2, we explain some preliminaries needed for the proof of Theorem 1, regarding counts of polynomials in 𝔽_{p}[x] having given factorization types, power series identities involving these counts, resultants of polynomials over ℤ_{p}, and explicit forms of Hensel’s lemma for polynomial factorization.

In Section 3, we then turn to the proof of Theorem 1. We first explain how Theorem 1(b) easily implies Theorem 1(a). To prove Theorem 1(b), we begin by writing the α(n, d) in terms of the β(n′, d′) for n′ ≤ n and d′ ≤ d. This involves considering how a monic polynomial over ℤ_{p} factors mod p and showing that the random variables given by the number of ℤ_{p}-roots above each 𝔽_{p}-root are independent. The answers may be expressed in terms of the generating functions A_{d} and B_{d} as

A_{1}(pt) = pB_{1}(t) ; A_{2}(pt) = pB_{2}(t) + \frac{1}{2}p(p − 1)B_{1}(t)^{2} ; A_{3}(pt) = pB_{3}(t) + p(p − 1)B_{1}(t)B_{2}(t) + \frac{1}{6}p(p − 1)(p − 2)B_{1}(t)^{3} ; ⋮  (16)

which may be expressed more succinctly in the form (5). We then explain how to write the β(n, d) in terms of the α(n′, d) for n′ ≤ n. This is proved by making substitutions of the form x ← px, and analysing the valuations of the resulting coefficients; the relation we obtain is expressed succinctly in the form (7). These two types of relations allow us then to recursively solve for the α’s and β’s. We then write the ρ’s in terms of the α’s and β’s, using another related independence result, and the relations we thereby obtain are expressed succinctly in the form (6), completing the proof of Theorem 1(b).

As previously noted, Theorem 1(b) gives a way to compute the power series A_{d}, B_{d} and R_{d} for each d. However, it does not seem to give any way of showing that these are in fact polynomials for all d. In establishing Theorem 1(c), we thus use a different technique to prove the stabilisation result for the α’s, or equivalently, that A_{d} is a polynomial of degree at most 2d. We could also give a similar proof of the corresponding result for the β’s, but there is no need, since it follows from that for the α’s, using either (4) or (16).

Once we have shown that A_{d} and B_{d} are polynomials of degree at most 2d, the same result for R_{d} then follows by (6). This is not sufficient to prove the stabilisation result for the ρ’s, since the definition of R_{d} involves additional factors. However, a variant of the ideas used to show that A_{d} is a polynomial also show that A_{d}(1) = A_{d}(p), and from this we deduce the stabilisation result for the ρ’s.

Finally, in Section 4, we prove the asymptotic results contained in §1.2.6.

2 Preliminaries

2.1 Basic notation

For a ring R, let R[x] denote the ring of univariate polynomials over R, and for n ≥ 0, let R[x]_{n} denote the subset of polynomials of degree at most n, and R[x]_{n}^{1} the subset of monic polynomials of degree n.

In the case R = ℤ_{p}, we identify ℤ_{p}[x]_{n}^{1} with ℤ_{p}^{n} via

x^{n} + ∑_{i=0}^{n−1} a_{i}x^{i} ↔ (a_{0}, a_{1}, …, a_{n−1}),

and thereby use the usual p-adic measure on subsets of ℤ_{p}[x]_{n}^{1} inherited via this identification.

For f ∈ ℤ_{p}[x], we denote by \overline{f} its image under reduction modulo p in 𝔽_{p}[x]. A polynomial with coefficients in ℤ_{p} is primitive if not all its coefficients are divisible by p, that is, if \overline{f} ≠ 0. For a primitive polynomial f ∈ ℤ_{p}[x], we define the reduced degree of f to be deg(\overline{f}). Hence deg(\overline{f}) ≤ deg(f), with equality if and only if the leading coefficient of f is a unit.

2.2 Counts involving splitting types of polynomials over 𝔽_{p}

We will require expressions for the number of monic polynomials in 𝔽_{p}[x] that factor as a product of irreducible polynomials with given degrees and multiplicities. These counts, and the corresponding probabilities for a random polynomial to have given factorization types, are collected in this subsection.

To this end, let S(n) denote the set of all splitting types of degree n. Thus, for example, S(2) = {(1 1), (1^{2}), (2)} has three elements, S(3) has five elements, and S(4) has 11.

We say that a monic polynomial f in 𝔽_{p}[x] of degree n has splitting type (d_{1}^{e_{1}} d_{2}^{e_{2}} ⋯ d_{t}^{e_{t}}) ∈ S(n) if it factors as f(x) = ∏_{j=1}^{t} f_{j}(x)^{e_{j}}, where the f_{j} are distinct irreducible monic polynomials over 𝔽_{p} with deg(f_{j}) = d_{j}. We write σ(f) for the splitting type of f, and N_{σ} for the number of monic polynomials in 𝔽_{p}[x] with splitting type σ.

If σ = (d), then we simply write N_{d} for N_{σ}. That is, N_{d} is the number of degree d irreducible monic polynomials in 𝔽_{p}[x]. Writing μ for the Möbius function, it is well known that

N_{d} = \frac{1}{d} ∑_{k|d} μ(k)p^{d/k}.

In general, for σ = (d_{1}^{e_{1}} d_{2}^{e_{2}} ⋯ d_{t}^{e_{t}}) ∈ S(n), we have

N_{σ} = ∏_{d=1}^{n} \binom{N_{d}}{m_{d}}\binom{m_{d}}{m_{d1} m_{d2} ⋯ m_{dn}},  (17)

where

m_{de} = m_{de}(σ) := #{s : d_{s}^{e_{s}} = d^{e}},

and

m_{d} = m_{d}(σ) := #{s : d_{s} = d} = ∑_{e=1}^{n} m_{de}.

Since there are p^{n} monic polynomials of degree n in 𝔽_{p}[x], the probability that a degree n monic polynomial f ∈ 𝔽_{p}[x] has splitting type σ, for σ ∈ S(n), is N_{σ}/p^{n}. This is evidently a rational function of p.

2.3 Power series identities involving N_{σ}

We now establish some power series identities involving the counts N_{σ} defined in the last section. Let x_{de} for d, e ≥ 1 be indeterminates. For a splitting type σ ∈ S(n) of degree n, let

x_{σ} = ∏_{d^{e}∈σ} x_{de}.

Polynomials in the x_{de} will be weighted by setting wt(x_{de}) = de. We set y_{0} = 1, and for n ≥ 1 define

y_{n} = ∑_{σ∈S(n)} N_{σ}x_{σ},

so that every monomial in y_{n} has weight n. We set x_{d0} = 1 for all d ≥ 1.

Proposition 2.1. We have the following identity in ℤ[{x_{de}}_{d,e≥1}][[t]]:

∑_{n=0}^{∞} y_{n}t^{n} = ∏_{d=1}^{∞} (∑_{e=0}^{∞} x_{de}t^{de})^{N_{d}} .  (18)

Proof. We must show that when the right hand side is multiplied out, the coefficient of t^{n} is y_{n}. The coefficient of t^{n} is a sum of monomials in the x_{de} of weight n. Each such product has the form x_{σ} for some σ ∈ S(n), and the number of times each monomial occurs is N_{σ}.

By specializing the x_{de}, we obtain the following corollary.

Corollary 2.2. We have the following identity in ℤ[[t]]:

(1 − pt)^{−1} = ∏_{d=1}^{∞}(1 − t^{d})^{−N_{d}}.  (19)

Proof. In (18), set x_{de} = 1 for all d, e. Then x_{σ} = 1, so y_{n} = p^{n}, and (19) follows.

Corollary 2.3. Let x_{e} for e ≥ 1 be indeterminates, and set x_{0} = 1. Then, in ℤ[x_{1}, x_{2}, …][[t]], we have:

∑_{n=0}^{∞} ∑_{σ∈S(n)} N_{σ} ( ∏_{1^{e}∈σ} x_{e}) t^{n} = (∑_{n=0}^{∞} x_{n}t^{n})^{p} (1 − t)^{p}(1 − pt)^{−1}.  (20)

Proof. In (18), set x_{1e} = x_{e}, and set x_{de} = 1 for all d ≥ 2. Then, by Corollary 2.2, we have

∏_{d=2}^{∞}(1 − t^{d})^{−N_{d}} = (1 − t)^{p}(1 − pt)^{−1},

yielding (20).

2.4 Resultants, coprime factorizations, and independence

2.4.1 Resultants

We begin with an observation about resultants of polynomials in ℤ_{p}[x] and their behavior upon reduction modulo p.

Lemma 2.4. Let f, g ∈ ℤ_{p}[x] have degrees m and n respectively.

1. If the leading coefficients of f and g are both units, then \overline{Res(f, g)} = Res(\overline{f}, \overline{g}).

2. If the leading coefficient a_{m} of f is a unit and d = deg(\overline{g}) < n, then \overline{Res(f, g)} = \overline{a_{m}}^{n−d} Res(\overline{f}, \overline{g}).

3. If the leading coefficients of f and g are both non-units, then \overline{Res(f, g)} = 0.

Proof. These are standard properties of resultants and may be seen by examination of the definition of Res(f, g) as the value of the (m + n) × (m + n) Sylvester determinant.

Corollary 2.5. Let f, g ∈ ℤ_{p}[x] have degrees m and n respectively. Then Res(f, g) is a unit if and only if at least one of the leading coefficients of f, g is a unit, and the reductions \overline{f}, \overline{g} are coprime.

Our reason to consider resultants is the following.

Lemma 2.6. Let R be a ring. For any d ≥ 1, we identify R[x]_{d}^{1} ≅ R^{d} and R[x]_{d} ≅ R^{d+1} as R-modules.

(a) The multiplication map R[x]_{m}^{1} × R[x]_{n}^{1} → R[x]_{m+n}^{1} has Jacobian given by Res(f, g).

(b) The multiplication map R[x]_{m}^{1} × R[x]_{n} → R[x]_{m+n} has Jacobian given by Res(f, g).

Proof. We first consider case (a), when both polynomials are monic. Let f(x) = x^{m} + ∑_{i=0}^{m−1} a_{i}x^{i}, g(x) = x^{n} + ∑_{j=0}^{n−1} b_{j}x^{j}, and h(x) = x^{m+n} + ∑_{k=0}^{m+n−1} c_{k}x^{k} be monic polynomials in R[x] having degrees m, n, and m + n respectively. If h(x) = f(x)g(x), then c_{k} = ∑_{i+j=k} a_{i}b_{j}, and the matrix of partial derivatives of the c_{k} with respect to the a_{i} and b_{j} is precisely the Sylvester matrix whose determinant is Res(f, g).

We next consider case (b), and assume that f(x) = x^{m} + ∑_{i=0}^{m−1} a_{i}x^{i} ∈ R[x]_{m}^{1} is monic while g(x) = ∑_{j=0}^{n} b_{j}x^{j} ∈ R[x]_{n} is not necessarily so. Let f(x)g(x) = ∑_{k=0}^{m+n} c_{k}x^{k}, and let M be the (m + n + 1) × (m + n + 1) matrix of partial derivatives of the c_{k} with respect to the a_{i} and b_{j}. Since c_{m+n} = b_{n}, the last row consists of 0’s except for the final entry which is 1. Expanding the determinant by the last row, we again obtain Res(f, g).

Corollary 2.7. Let A ⊂ ℤ_{p}[x]_{m}^{1}, B ⊂ ℤ_{p}[x]_{n}^{1} (resp. B ⊂ ℤ_{p}[x]_{n}), and AB ⊂ ℤ_{p}[x]_{m+n}^{1} (resp. AB ⊂ ℤ_{p}[x]_{m+n}) be measurable subsets such that multiplication induces a bijection

A × B → AB = {ab | a ∈ A, b ∈ B}.

If Res(a, b) ∈ ℤ_{p}^{∗} for all a ∈ A and b ∈ B, then this bijection is measure-preserving.

2.4.2 Coprime factorizations and Hensel lifting

We next recall Hensel’s lemma for polynomial factorizations in certain quantitative forms. The first is standard, and is stated as Lemma 2.3 in [3], while the variant is mentioned in [3, p. 24].

For f ∈ 𝔽_{p}[x]_{d}^{1}, we denote by P_{f} the set of polynomials in ℤ_{p}[x]_{d}^{1} that reduce to f modulo p; and for n ≥ d, we denote by P_{f}^{n} the set of polynomials in ℤ_{p}[x]_{n} that reduce to f modulo p.

Lemma 2.8. Suppose that g, h ∈ 𝔽_{p}[x] are monic and coprime. Then the multiplication map

P_{g} × P_{h} → P_{gh}  (21)

is a measure-preserving bijection.

Proof. Let f ∈ ℤ_{p}[x]_{n}^{1} be such that \overline{f} factors in 𝔽_{p}[x] as \overline{f} = gh. Then by Hensel’s lemma f factors uniquely in ℤ_{p}[x] as f = g̃h̃, where g̃ ∈ P_{g} and h̃ ∈ P_{h}. Therefore (21) is a bijection. The measurepreserving property holds by Corollaries 2.5 and 2.7.

The following variant will be used to handle polynomials f ∈ ℤ_{p}[x] whose leading coefficient is not a unit.

Lemma 2.9. For n ≥ m, the multiplication map

ℤ_{p}[x]_{m}^{1} × P_{1}^{n−m} → \{f ∈ ℤ_{p}[x]_{n} : \overline{f} ∈ 𝔽_{p}[x]_{m}^{1}\}  (22)

is a measure-preserving bijection.

Proof. Let f ∈ ℤ_{p}[x]_{n} be such that \overline{f} is monic of degree m. Then homogenising, applying Hensel’s lemma, and dehomogenising, shows that f factors uniquely in ℤ_{p}[x] as f = f_{1}f_{2} where f_{1} ∈ ℤ_{p}[x]_{m}^{1} and f_{2} ∈ P_{1}^{n−m}. Therefore, (22) is a bijection. The measure-preserving property again holds by Corollaries 2.5 and 2.7, since f_{1} is monic.

2.4.3 Independence lemmas

Finally, we may phrase Lemmas 2.8 and 2.9 as statements regarding the independence of suitable random variables.

Corollary 2.10. Let g, h ∈ 𝔽_{p}[x] be coprime monic polynomials. For f ∈ P_{gh}, let π_{1} and π_{2} denote the projections of P_{gh} onto P_{g} and P_{h}, respectively, under the bijection P_{gh} → P_{g} × P_{h}. Then the number of ℚ_{p}-roots of f ∈ P_{gh} is X + Y, where X, Y : P_{gh} → {0, 1, 2, …} are independent random variables distributed on f ∈ P_{gh} as the number of ℚ_{p}-roots of π_{1}(f) ∈ P_{g} and π_{2}(f) ∈ P_{h}, respectively.

Corollary 2.11. Let m ≤ n, and let

B_{m,n} := \{f ∈ ℤ_{p}[x]_{n} : \overline{f} ∈ 𝔽_{p}[x]_{m}^{1}\}.

For f ∈ B_{m,n}, let ψ_{1} and ψ_{2} denote the projections of B_{m,n} onto ℤ_{p}[x]_{m}^{1} and P_{1}^{n−m}, respectively, under the bijection B_{m,n} → ℤ_{p}[x]_{m}^{1}×P_{1}^{n−m}. Let X, Y : B_{m,n} → {0, 1, 2, …} be the random variables giving the numbers of roots of f ∈ B_{m,n} in ℤ_{p} and in ℚ_{p} \ ℤ_{p}, respectively. Then X and Y are independent random variables distributed on f ∈ B_{m,n} as the number of ℚ_{p}-roots of ψ_{1}(f)(x) ∈ ℤ_{p}[x]_{m}^{1} and of ψ_{2}(f)^{rev}(x) := x^{n−m}ψ_{2}(f)(1/x) ∈ P_{x^{n−m}}, respectively.

3 Proof of Theorem 1

3.1 Theorem 1(b) implies Theorem 1(a)

Theorem 1(b) allows us to compute α(n, d), β(n, d), and ρ(n, d) for any n and d. Indeed we use (5) and (7) to solve for the α’s and β’s, and then (6) to compute the ρ’s. The answers obtained are rational functions of p. The relation (5) is invariant under replacing t → t/p and switching p ↔ 1/p and A_{d} ↔ B_{d}, while the relation (7) is invariant under switching p ↔ 1/p and A_{d} ↔ B_{d}. The symmetry (4) then follows by induction on n and d, while (3) follows from (6).

3.2 Proof of Theorem 1(b)

3.2.1 Conditional expectations

The expectations α(n, d) and β(n, d) were defined in the introduction. To help evaluate them, we make the following additional definitions.

Definition 3.1. (i) For f ∈ 𝔽_{p}[x]_{n}^{1}, let α(n, d | f) denote the expected number of d-sets of ℚ_{p}-roots of a polynomial in P_{f} ⊂ ℤ_{p}[x]_{n}^{1}. Since P_{f} has relative density p^{−n} in ℤ_{p}[x]_{n}^{1}, we have

α(n, d) = p^{−n} ∑_{f∈𝔽_{p}[x]_{n}^{1}} α(n, d | f).  (23)

Also, β(n, d) = α(n, d | x^{n}).

(ii) For σ in S(n), let α(n, d | σ) be the expected number of d-sets of ℚ_{p}-roots of a polynomial in ℤ_{p}[x]_{n}^{1} whose mod p splitting type is σ. Thus

α(n, d) = p^{−n} ∑_{σ∈S(n)} N_{σ} α(n, d | σ),  (24)

and

α(n, d | σ) = N_{σ}^{−1} ∑_{f∈𝔽_{p}[x]_{n}^{1}: σ(f)=σ} α(n, d | f),  (25)

where σ(f) denotes the splitting type of f.

3.2.2 Writing the α’s in terms of the β’s

The aim of this subsection is to prove (5), the first part of Theorem 1(b).

Lemma 3.2. Let g, h ∈ 𝔽_{p}[x] be monic and coprime. Then

α(deg(gh), d | gh) = ∑_{d_{1}+d_{2}=d} α(deg(g), d_{1} | g) · α(deg(h), d_{2} | h),  (26)

where the sum is over all pairs (d_{1}, d_{2}) of nonnegative integers summing to d.

If, additionally, h has no roots in 𝔽_{p}, then

α(deg(gh), d | gh) = α(deg(g), d | g).

Proof. The lemma follows from Corollary 2.10 and the observation that if X and Y are independent random variables taking values in {0, 1, 2, …} then

𝔼\binom{X + Y}{d} = ∑_{d_{1}+d_{2}=d} 𝔼\binom{X}{d_{1}}𝔼\binom{Y}{d_{2}}.  (27)

Recall that β(n, d) = α(n, d | x^{n}) is the expected number of d-sets of roots of a monic polynomial of degree n which reduces to x^{n} modulo p. Using Lemma 3.2, we can express α(n, d | f) for monic f ∈ 𝔽_{p}[x]_{n} in terms of β(n′, d′) for appropriate n′, d′.

Lemma 3.3. Let σ = (1^{n_{1}} ⋯ 1^{n_{k}} ⋯) ∈ S(n) be a splitting type with exactly k = m_{1}(σ) powers of 1. Then

α(n, d | σ) = ∑_{d_{1}+···+d_{k}=d} ∏_{i=1}^{k} β(n_{i}, d_{i}).  (28)

Proof. Let f ∈ 𝔽_{p}[x]_{n}^{1} have splitting type σ. To evaluate α(n, d | f), we may ignore the factors of f of degree greater than 1, since if f = f_{1}f_{2} where σ(f_{1}) = (1^{n_{1}} ⋯ 1^{n_{k}}) and f_{2} has no linear factors, then α(n, d | f) = α(deg(f_{1}), d | f_{1}) by the last part of Lemma 3.2.

Now let f = ∏_{i=1}^{k} ℓ_{i}^{n_{i}}, where the ℓ_{i} are distinct, monic, and of degree 1. Using Lemma 3.2 repeatedly gives

α(n, d | f) = ∑_{d_{1}+···+d_{k}=d} ∏_{i=1}^{k} α(n_{i}, d_{i} | ℓ_{i}^{n_{i}}).

Finally, α(n_{i}, d_{i} | ℓ_{i}^{n_{i}}) = α(n_{i}, d_{i} | x^{n_{i}}) = β(n_{i}, d_{i}), since for fixed c ∈ ℤ_{p} the map g(x) ↦ g(x + c) is measure-preserving on monic polynomials in ℤ_{p}[x] of a given degree. Thus

α(n, d | f) = ∑_{d_{1}+···+d_{k}=d} ∏_{i=1}^{k} β(n_{i}, d_{i}),  (29)

and (28) now follows from (25) and (29).

Proof of Theorem 1(b), Equation (5). Let σ = (1^{n_{1}} ⋯ 1^{n_{k}} ⋯) ∈ S(n) be as in Lemma 3.3. Then, by (24) and Lemma 3.3, we have

α(n, d) = p^{−n} ∑_{σ∈S(n)} N_{σ} α(n, d | σ) = p^{−n} ∑_{σ∈S(n)} N_{σ} ∑_{d_{1}+···+d_{k}=d} ∏_{i=1}^{k} β(n_{i}, d_{i}).  (30)

Multiplying by u^{d} and summing over d gives

∑_{d=0}^{n} α(n, d)u^{d} = p^{−n} ∑_{σ∈S(n)} N_{σ} ∏_{1^{e}∈σ} (∑_{d=0}^{e} β(e, d)u^{d}) .

Multiplying by (pt)^{n}, summing over n, and using Corollary 2.3, we obtain

∑_{d=0}^{∞} (∑_{n=0}^{∞} α(n, d)(pt)^{n}) u^{d} = (∑_{d=0}^{∞} (∑_{n=0}^{∞} β(n, d)t^{n}) u^{d})^{p} (1 − t)^{p}(1 − pt)^{−1}.

Finally, multiplying both sides by 1 − pt yields (5).

3.2.3 Writing the ρ’s in terms of the α’s and β’s

The aim of this section is to prove (6), the second part of Theorem 1(b).

Recall that ρ(n, d) is the expected number of d-sets of ℚ_{p}-roots of polynomials f ∈ ℤ_{p}[x] of degree n. It is evident that this does not change if we restrict to primitive polynomials.

Let f ∈ ℤ_{p}[x] be a primitive polynomial of degree n. Let m = deg(\overline{f}) be the reduced degree of f. For fixed m with 0 ≤ m ≤ n, the density of primitive polynomials f ∈ ℤ_{p}[x]_{n} with reduced degree m is \frac{p−1}{p^{n+1}−1}p^{m}. Therefore, conditioning on the value of m, we have

ρ(n, d) = \frac{p − 1}{p^{n+1} − 1} ∑_{m=0}^{n} p^{m}ρ(n, d, m),  (31)

where ρ(n, d, m) is the expected number of d-sets of ℚ_{p}-roots of f as f ∈ ℤ_{p}[x]_{n} runs over polynomials of degree n with reduced degree m. This expectation does not change if we restrict to f whose reduction mod p is monic.

Equation (6) now follows from (31) and the following lemma.

Lemma 3.4. We have

ρ(n, d, m) = ∑_{d_{1}+d_{2}=d} α(m, d_{1}) · β(n − m, d_{2}).  (32)

Proof. This follows from Corollary 2.11 and (27).

3.2.4 Writing the β’s in terms of the α’s

The aim of this section is to prove (7), the third and last part of Theorem 1(b).

Fixing d, we put α_{n} := α(n, d) and β_{n} := β(n, d). In the following lemma, we express β_{n} in terms of α_{s} for s ≤ n.

Lemma 3.5. We have

β_{n} = p^{−\binom{n}{2}}α_{n} + (p − 1) ∑_{0≤s<r<n} p^{−\binom{r+1}{2}}p^{s}α_{s}.  (33)

Proof. Recall that β_{n} is the expected value of the random variable X distributed as the number of dsets of ℤ_{p}-roots of f ∈ P_{x^{n}}. All such roots must lie in pℤ_{p}, and thus correspond to ℤ_{p}-roots of f(px). To each f ∈ P_{x^{n}}, we associate a pair of integers (r, s) with 0 ≤ s ≤ r ≤ n as follows. Consider f(px), and let r be the largest integer such that p^{r} | f(px), so that 1 ≤ r ≤ n. Let s be the reduced degree of p^{−r}f(px). Then either 0 ≤ s < r < n, or s = r = n.

The relative density of the subset of f ∈ P_{x^{n}} such that p^{r} | f is p^{−\binom{r}{2}}, since for 0 ≤ i ≤ r−2 we require the coefficient of x^{i} in f to be divisible by p^{r−i} and not just by p. Given r < n, the condition that p^{−r}f(px) has reduced degree at least s imposes r−s−1 additional divisibility conditions, so the relative density of those f such that the reduced degree is exactly s is p^{−(r−s−1)}(1 − 1/p) = p^{s−r}(p − 1). Thus the relative density of f ∈ P_{x^{n}} with parameters (r, s) is given by p^{−\binom{r}{2}}p^{s−r}(p − 1) = p^{−\binom{r+1}{2}}p^{s}(p − 1) for 0 ≤ s < r < n. If r = n, then s = r, and therefore the density of f with parameters (n, n) is p^{−\binom{n}{2}}.

Given the values of r and s, the conditional expected value of X is α_{s}, independent of r, by Corollary 2.11. Hence β_{n} = p^{−\binom{n}{2}}α_{n} + ∑_{0≤s<r<n} p^{−\binom{r+1}{2}}p^{s}(p − 1)α_{s}.

Proof of (7). Taking Equation (33) for n and n − 1 and subtracting gives

p^{\binom{n}{2}}(β_{n} − β_{n−1}) = (α_{n} − p^{n−1}α_{n−1}) + (p − 1) ∑_{s=0}^{n−2} p^{s}α_{s}.  (34)

Now taking Equation (34) for n and n − 1 and again subtracting yields

p^{\binom{n}{2}}[(β_{n} − β_{n−1}) − p^{1−n}(β_{n−1} − β_{n−2})] = (α_{n} − α_{n−1}) − p^{n−1}(α_{n−1} − α_{n−2}),

and this indeed asserts the equality of the coefficient of t^{n} on both sides of (7).

We have completed the proof of Theorem 1(b).

Remark 3.6. Equations (30), (31), (32) and (33) are sufficient to compute the α’s, β’s and ρ’s. We were motivated to find the neater formulation in Theorem 1(b) by the desire to prove the p ↔ 1/p symmetries.

3.3 Proof of Theorem 1(c)

Consider a random polynomial of degree n in ℤ_{p}[x]. Let α̃(n, d) be the expected number of d-sets of roots in ℤ_{p}. Conditioning on the reduced degree and applying Corollary 2.11 shows that

α̃(n, d) = ∑_{m=0}^{n} (1 − \frac{1}{p}) \frac{1}{p^{m}} α(n − m, d) + \frac{1}{p^{n+1}} α̃(n, d).

This rearranges to give

α̃(n, d) = ∑_{m=0}^{n}(1 − p)p^{m}α(m, d) + p^{n+1}α̃(n, d).  (35)

In other words, α̃(n, d) is a weighted average of the α(m, d) for m ≤ n.

We now show that α(n, d) and α̃(n, d) are equal and independent of n, provided that n ≥ 2d. Let A_{n} = ℤ_{p}[X]_{n}^{1} denote the set of monic polynomials over ℤ_{p} of degree n, and B_{n} the set of

all polynomials of degree less than n. Then we have A_{n} = {X^{n} + h : h ∈ B_{n}}, and both A_{n} and B_{n} may be identified with ℤ_{p}^{n} and have measure 1. Let A_{n}^{split} be the subset of those f in A_{n} that split completely. The measure of A_{n}^{split} is α(n, n).

Now consider the multiplication map A_{d}^{split} × ℤ_{p}[x]_{n−d} → ℤ_{p}[x]_{n}, whose image is the set of f ∈ ℤ_{p}[x]_{n} with at least d roots in ℤ_{p}; in general, the number of preimages of f in ℤ_{p}[x]_{n} is equal to the number of d-sets of roots of f in ℤ_{p}. This implies that α̃(n, d) is the p-adic measure of the image of the multiplication map, viewed as a multiset. The change of variables from A_{d}^{split} × ℤ_{p}[x]_{n−d} to ℤ_{p}[x]_{n} introduces a Jacobian factor which, by Lemma 2.6, is just the resultant. Therefore,

α̃(n, d) = ∫_{g∈A_{d}^{split}} ∫_{h∈ℤ_{p}[x]_{n−d}} | Res(g, h)| dh dg.  (36)

Similarly, we have

α(n, d) = ∫_{g∈A_{d}^{split}} ∫_{h∈A_{n−d}} | Res(g, h)| dh dg.  (37)

The following lemma now proves the first part of Theorem 1(c), namely, that A_{d}(t) is a polynomial of degree at most 2d.

Lemma 3.7. The expectations α(n, d) and α̃(n, d) are equal and independent of n for n ≥ 2d.

Proof. By (36)and (37)it suffices to show that for each fixed g in A_{d}^{split}, the values of the inner integrals ∫_{h∈ℤ_{p}[x]_{n−d}} | Res(g, h)| dh and ∫_{h∈A_{n−d}} | Res(g, h)|dh are equal and independent of n for n ≥ 2d. Our argument is quite general, in that we only use that g is monic, not that it is split.

We assume that n ≥ 2d, and write each h ∈ ℤ_{p}[x]_{n−d} uniquely as h = qg+r with q ∈ ℤ_{p}[x]_{n−2d} and r ∈ B_{d}. This sets up a bijection (q, r) ↦ h = qg + r from ℤ_{p}[x]_{n−2d} × B_{d} to ℤ_{p}[x]_{n−d} (using here that n − d ≥ d). Now using Res(g, h) = Res(g, r), and the fact that our bijection has trivial Jacobian (the change of basis matrix is triangular with 1’s on the diagonal since g is monic), we deduce that

∫_{h∈ℤ_{p}[x]_{n−d}} | Res(g, h)|dh = ∫_{q∈ℤ_{p}[x]_{n−2d}} ∫_{r∈B_{d}} | Res(g, r)|drdq = ∫_{r∈B_{d}} | Res(g, r)|dr,

since the integral over q ∈ ℤ_{p}[x]_{n−2d} is just the measure of ℤ_{p}[x]_{n−2d} which is 1. In an identical manner, we have

∫_{h∈A_{n−d}} | Res(g, h)|dh = ∫_{q∈A_{n−2d}} ∫_{r∈B_{d}} | Res(g, r)|drdq = ∫_{r∈B_{d}} | Res(g, r)|dr.

Hence

α̃(n, d) = α(n, d) = ∫_{g∈A_{d}^{split}} ∫_{r∈B_{d}} | Res(g, r)| dr dg

for n ≥ 2d. The inner integral above clearly depends on g and d, but not on n.

We now turn to proving the remaining parts of Theorem 1(c). By Lemma 3.7, we have that A_{d}(t) is a polynomial of degree at most 2d. Thus, fixing any n ≥ 2d, we may write

A_{d}(t) = (1 − t) ∑_{m=0}^{n} α(m, d)t^{m} + α(n, d)t^{n+1}.  (38)

Lemma 3.7allows us to replace α̃(n, d) by α(n, d) in (35). Taking t = 1 in (38) shows that the left hand side of (35) is A_{d}(1). Taking t = p in (38) shows that the right hand side of (35) is A_{d}(p). Therefore, A_{d}(1) = A_{d}(p).

Since A_{d} is a polynomial of degree at most 2d, it follows by (5), or equally (4), that B_{d} is a polynomial of degree at most 2d. Directly from the definitions of A_{d} and B_{d}, these results are equivalent to the statements that α(n, d) = A_{d}(1) and β(n, d) = B_{d}(1) for all n ≥ 2d.

It follows by (6) that R_{d} is a polynomial of degree at most 2d. To prove the stabilisation result for the ρ(n, d), we use the fact we just proved that A_{d}(1) = A_{d}(p). It follows by (5), or equally (4), that B_{d}(1) = B_{d}(1/p). By (6), we then have R_{d}(1) = R_{d}(1/p). We may therefore write R_{d}(t) = R_{d}(1) + (1 − t)(1 − pt)F (t) where F has degree at most 2d − 2. Finally, from the definition of R_{d}, we have ρ(n, d) = R_{d}(1) for all n > deg(F).

This completes the proof of Theorem 1(c).

Remark 3.8. The values of the α̃(n, d), which may be computed from the α(n, d) using (35), may also be of independent interest. For example, the expectation α̃(n, 1) = p/(p + 1) is computed by Caruso [4], and also follows from the one-variable case of the work of Evans [6, Theorem 1.2].

4 Asymptotic results

In this section, we prove Proposition 1.1. The proof is essentially independent of our earlier results, although for convenience we will reference some of our earlier formulas. We begin with a well-known lemma (see, e.g., [5, p. 256] for a proof).

Lemma 4.1. Let f ∈ 𝔽_{p}[x] be a monic polynomial of degree n, and C ⊂ S_{n} a conjugacy class (i.e., a cycle type) corresponding to the partition d_{1} + ⋯ + d_{t} = n. Let λ(C, p) be the probability that f factors into irreducible polynomials of degrees d_{1}, …, d_{t}, respectively. Then λ(C, p) → |C|/n! as p → ∞.

If σ = (d_{1}^{e_{1}} d_{2}^{e_{2}} ⋯ d_{t}^{e_{t}}) ∈ S(n) is a splitting type of degree n, then by (17), we have that N_{σ} is a polynomial in p of degree ∑_{i=1}^{t} d_{i}. Therefore, if e_{i} > 1 for at least one i ∈ {1, 2, …, t}, then

lim_{p→∞} \frac{N_{σ}}{p^{n}} = 0.

By (24), to compute lim_{p→∞} α(n, d), it thus suffices to consider only σ ∈ S(n) that correspond to factorizations without multiple factors, i.e., to partitions d_{1} + ⋯ + d_{t} = n of n. It is sufficient to consider only those squarefree polynomials modulo p that have r ≥ d distinct roots (since all of these roots lift by Hensel’s lemma), where each such polynomial is weighted by \binom{r}{d}. By Lemma 4.1, we wish to count all permutations in S_{n} with r fixed points, where each such permutation is weighted by \binom{r}{d}. The total weighted number of such permutations is \binom{n}{d}(n − d)! = \frac{n!}{d!}, because we can choose d fixed points in {1, 2, …, n}, and then randomly permute the other n − d numbers. It follows that

lim_{p→∞} α(n, d) = \frac{1}{n!} \frac{n!}{d!} = \frac{1}{d!}.  (39)

By (31), we have lim_{p→∞} ρ(n, d) = lim_{p→∞} ρ(n, d, n). Either directly from the definitions, or as a special case of (32), we have ρ(n, d, n) = α(n, d). Therefore,

lim_{p→∞} ρ(n, d) = lim_{p→∞} α(n, d) = \frac{1}{d!},

proving Proposition 1.1(a) for ρ and α.

Using (2), and its analogue for α^{∗}, we then have

lim_{p→∞} ρ^{∗}(n, r) = lim_{p→∞} α^{∗}(n, r) = ∑_{d=0}^{n}(−1)^{d−r}\binom{d}{r}\frac{1}{d!} = \frac{1}{r!} ∑_{d=0}^{n−r}(−1)^{d} \frac{1}{d!},

proving Proposition 1.1(b).

To prove the large p limits involving β, we note that if d = n − 1 or d = n, then (33) is just

β(n, d) = p^{−\binom{n}{2}}α(n, d),

while if d < n − 1, then Equation (33) takes the shape

β(n, d) = p^{−\binom{d+1}{2}}α(d, d) + O(p^{−\binom{d+1}{2}−1}).

From the previous two equations and (39), we see that

lim_{p→∞} p^{\binom{n}{2}}β(n, n) = \frac{1}{n!} and lim_{p→∞} p^{\binom{d+1}{2}}β(n, d) = \frac{1}{d!} for d < n,

proving Proposition 1.1(a) for β.

The analogue of (2) for β^{∗} shows that for r ≤ n − 2, we have

lim_{p→∞} p^{\binom{r+1}{2}}β^{∗}(n, r) = \frac{1}{r!}.

Since β^{∗}(n, n) = β(n, n), this completes the proof of Proposition 1.1(c). Note that β^{∗}(n, n − 1) = 0, so there is no need to compute the limits in this case.

If we take r = 0 in Proposition 1.1, we see that

lim_{p→∞} ρ^{∗}(n, 0) = ∑_{d=0}^{n}(−1)^{d}/d!.

The reader may recognise this as the answer to the derangements problem, i.e., the probability that a random permutation on n letters has no fixed point. This is the case because, by Lemma 4.1, monic polynomials without ℚ_{p}-roots correspond, in the large p limit, to permutations without fixed points. Similarly, the limit lim_{p→∞} ρ^{∗}(n, r) = (1/r!) ∑_{d=0}^{n−r}(−1)^{d}/d! is equal to the probability that a random permutation on n letters has exactly r fixed points.

Acknowledgments

We thank the CMI-HIMR Summer School in Computational Number Theory held at the University of Bristol in June 2019, where this work began. We also thank Xavier Caruso for kindly sharing with us his unpublished lecture notes [4], and Hendrik Lenstra, Steffen Müller, Bjorn Poonen, Lazar Radičević, Arul Shankar, and Jaap Top for many helpful conversations.

The first author was supported by a Simons Investigator Grant and NSF grant DMS-1001828. The second author was supported by the Heilbronn Institute for Mathematical Research. The fourth author was supported in part by DFG-Grant MU 4110/1-1.

References

[1] M. Bhargava, J. E. Cremona, T. A. Fisher, N. G. Jones, and J. P. Keating, What is the probability that a random integral quadratic form in n variables has an integral zero?, Int. Math. Res.

Not. 2016, Issue 12 (2016), 3828–3848. https://doi.org/10.1093/imrn/rnv251  .

[2] A. Bloch and G. Pólya, On the roots of certain algebraic equations, Proc. Lond. Math. Soc. 33 (1932), 102–114.

[3] J. Buhler, D. Goldstein, D. Moews, and J. Rosenberg, The probability that a random monic p-adic polynomial splits, Exper. Math. 15:1 (2006), 21–32.

[4] X. Caruso, Where are the zeroes of a random p-adic polynomial?. Unpublished notes. Available

at http://xavier.toonywood.org/papers/publis/randompoly-talk.pdf  .

[5] S. D. Cohen, The distribution of polynomials over finite fields, Acta Arith. 17 (1970), 255–271.

[6] S. Evans, The expected number of zeros of a random system of p-adic polynomials, Elec. Comm. Prob. 11 (2006), 278–290.

[7] M. Kac, On the average number of real roots of a random algebraic equation, Bull. Math. Amer. Soc., 49 (1943), 314–320.

[8] D. J. Limmer, Measure-equivalence of quadratic forms, Ph.D. Thesis, Oregon State University, 1999.

[9] J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation (i), J. London Math. Soc. 13 (1938), 288–295.

[10] J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation (ii), Proc. Camb. Phil. Soc. 35 (1939), 133–148.

[11] J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation (iii), Rec. Math. [Mat. Sbornik] 54 (1943), 277–286.

[12] N. B. Maslova, On the variance of the number of real roots of random polynomials, Theory of Probability & Its Applications 19 (1974), 35–52.

[13] N. B. Maslova, On the distribution of the number of real roots of random polynomials, Theory of Probability & Its Applications 19 (1975), 461–473.

[14] O. Nguyen and V. Vu, Random polynomials: central limit theorems for the real roots,

arXiv:1904.04347v3 , Dec. 2020.

[15] A. Dembo, B. Poonen, Q. Shao, and O. Zeitouni, Random polynomials having few or no real zeros, J. Amer. Math. Soc. 15 (2002), 857–892.

[16] R. Shmueli, The expected number of roots over the field of p-adic numbers,

arXiv:2101.03561v1 , Jan. 2021.

[17] B. L. Weiss, Probabilistic Galois theory over p-adic fields, J. Number Theory 133:5 (2013), 1537– 1563.