The Distribution of Group Structures

on Elliptic Curves over Finite Prime Fields

Ernst-Ulrich Gekeler

Received: April 12, 2006

Communicated by Peter Schneider

Abstract. We determine the probability that a randomly chosen elliptic curve E/𝔽_{p} over a randomly chosen prime field 𝔽_{p} has an ℓ-primary part E(𝔽_{p})[ℓ^{∞}] isomorphic with a fixed abelian ℓ-group H_{α,β}^{(ℓ)} = ℤ/ℓ^{α} × ℤ/ℓ^{β}.

Probabilities for “|E(𝔽_{p})| divisible by n”, “E(𝔽_{p}) cyclic” and expectations for the number of elements of precise order n in E(𝔽_{p}) are derived, both for unbiased E/𝔽_{p} and for E/𝔽_{p} with p ≡ 1 (ℓ^{r}).

2000 Mathematics Subject Classification: 11 N 45, 11 G 20, 11 S 80 Keywords and Phrases: Elliptic curves over finite fields, group structures, counting functions

1. Introduction

Given an elliptic curve E over the finite field 𝔽_{q} with q elements, the set E(𝔽_{q}) of rational points forms an abelian group, which satisfies

(1.1)  |E(𝔽_{q}) − (q + 1)| ≤ 2q^{1/2} (Hasse)

and

(1.2)  E(𝔽_{q}) ≅ ℤ/m × ℤ/n

with well-defined numbers m, n and m|n. Our aim is to study the statistics of such group structures if E/𝔽_{q} varies through an infinite family F. In the present article, we consider

(1.3)

F = {𝔽_{p}-isomorphism classes of elliptic

curves E/𝔽_{p} over finite prime fields 𝔽_{p}}

but note that a similar study may be performed for elliptic curves E/𝔽_{q} over arbitrary finite fields, or for E/𝔽_{q} where q runs through the powers of the fixed prime number p.

Given any algebraic property (A) of E/𝔽_{p} (or any subset A of F), we define its “probability” in F as

(1.4)  P (F, A) := lim_{x→∞} \frac{|\{E/𝔽_{p} ∈ F | p ≤ x, E/𝔽_{p} has property A\}|}{|\{E/𝔽_{p} ∈ F | p ≤ x\}|},

provided the limit exists. Then P (F, ·) is a “content” on F, i.e., it satisfies the usual axioms of a probability measure except that the condition of σadditivity (= countable additivity) is relaxed to finite additivity. In a similar fashion, we may define other notions of probability theory for F, for example the conditional probability P (F, A|B) for property A under condition B, or the expectation E(F, f) for a function f on F.

It is obvious from (1.1) that P (F, A) = 0 for any property like

(A)  E(𝔽_{p}) ≅ ℤ/m × ℤ/n with m, n fixed ;

i.e., such probabilities are meaningless. Instead, the typical question we will deal with is:

1.5 Question: Let a prime number ℓ and a finite abelian ℓ-group

H = H_{α,β}^{(ℓ)} = ℤ/ℓ^{α} × ℤ/ℓ^{β}

with 0 ≤ α ≤ β be given. How likely (cf. (1.4)) is it that the ℓ-primary part E(𝔽_{p})[ℓ^{∞}] of E(𝔽_{p}) is isomorphic with H, if E/𝔽_{p} is randomly chosen in F?

(Instead of fixing one prime ℓ and the finite ℓ-group H, we could fix a finite set L of primes and a finite abelian L-group H of rank less or equal to 2, and ask for the probability that the L-part of E(𝔽_{p}) is isomorphic with H.)

In Theorem 3.15, using results of E. Howe [7], we show that the corresponding P (F, “E(𝔽_{p})[ℓ^{∞}] ≅ H_{α,β}^{(ℓ)}”) always exists, and give its value, along with an error term O_{ℓ,α,β}(x^{−1/2}). As prescribed by Serre’s “Čebotarev theorem” ([8], Theorem 7), that probability agrees with the (non-vanishing) Haar volume g^{(ℓ)}(α, β) of a certain subset X^{(ℓ)}(α, β) of GL(2, ℤ_{ℓ}). The relevant Haar measures are provided by Theorem 2.3, the proof of which forms the contents of section 2.

Actually, we will see in section 4 that P (F, ·) defines a probability measure (in the usual sense, that is, even σ-additive) on the discrete set of isomorphism classes of abelian groups of shape H_{α,β}^{(ℓ)} = ℤ/ℓ^{α} × ℤ/ℓ^{β} (0 ≤ α ≤ β), and that these measures for varying primes ℓ are stochastically independent.

We use the preceding to derive (both without restrictions on p, or under congruence conditions for p) the exact values of

(a) the probability P (F, “n| |E(𝔽_{p})”) that |E(𝔽_{p})| is divisible by the fixed natural number n (Proposition 5.1, Corollary 5.2);

(b) the expectation E(F, κ_{n}) for the number κ_{n}(E(𝔽_{p})) of elements of precise order n in E(𝔽_{p}) (Proposition 5.6);

(c) the probability P (F, “E(𝔽_{p}) is cyclic”) of cyclicity of E(𝔽_{p}) (Theorem 5.9).

Items (a) and (c) are related to results of Howe (Theorem 1.1 of [5]) and S.G. Vladut (Theorem 6.1 of [7]), the difference being that the cited authors consider elliptic curves E over one fixed finite field 𝔽_{q}, while (a),(b),(c) are results averaged over all 𝔽_{p} (or all 𝔽_{p} where p lies in some arithmetic progression).

Given E/𝔽_{p} and a prime number ℓ different from p, we let F_{ℓ} = F_{ℓ}(E/𝔽_{p}) be its Frobenius element, an element of GL(2, ℤ_{ℓ}) well-defined up to conjugation (ℤ_{ℓ} = ℓ-adic integers). Its characteristic polynomial χ_{F_{ℓ}}(X) = X^{2} − tr(F_{ℓ})X + det(F_{ℓ}) satisfies

(1.6)  det(F_{ℓ}) = p, tr(F_{ℓ}) = p + 1 − |E(𝔽_{p})|;

in particular, it has integral coefficients independent of ℓ. It is related with the group structure on E(𝔽_{p}) through

(1.7)  E(𝔽_{p})[ℓ^{∞}] ≅ cok(F_{ℓ} − 1),

where “cok” is the cokernel of a matrix regarded as an endomorphism on ℤ_{ℓ}×ℤ_{ℓ} (see e.g. [3], appendix, Proposition 2).

In order to avoid technical problems irrelevant for our purposes, we exclude for the moment the primes p = 2 and 3 from our considerations, that is, F = {E/𝔽_{p} | p ≥ 5 prime}. Then we define

(1.8)  w(E/𝔽_{p}) = 2|Aut_{𝔽_{p}}(E/𝔽_{p})|^{−1} = \{ \begin{matrix}\frac{1}{3}, p ≡ 1 (3), j(E) = 0 \\ \frac{1}{2}, p ≡ 1 (4), j(E) = 12^{3} \\ 1 , otherwise. \end{matrix}

Thus in “most” cases, w(E/𝔽_{p}) = 1. For well-known philosophical reasons not addressed here, we will count subsets of F not by ordinary cardinality, but by cardinality weighted with w. That is, for a finite subset F′ of F, we define its weighted cardinality as

(1.9)  |F′|^{∗} = ∑_{E/𝔽_{p}∈F′} w(E/𝔽_{p}).

Then we have for example

(1.10)  |{E/𝔽_{p}}|^{∗} = 2p

for the number^{∗} of isomorphism classes of elliptic curves over a fixed prime field 𝔽_{p}. Accordingly, we redefine probabilities P (F, A) as in (1.4), replacing ordinary “| |” by weighted cardinalities “| |^{∗}”. Of course, it doesn’t matter whether or not we include the finite number of E/𝔽_{p} with p = 2, 3 into F.

With each E/𝔽_{p} ∈ F, we associate its total Frobenius element

F (E/𝔽_{p}) = (…, F_{ℓ}(E/𝔽_{p}), …) ∈ Π_{ℓ prime}GL(2, ℤ_{ℓ})

(well-defined up to conjugation, and neglecting for the moment the question of the p-component of F). As usual, we let

ℤ̂ = lim_{\overleftarrow{N∈ℕ}} ℤ/N = ∏_{ℓ prime} ℤ_{ℓ}

be the profinite completion of ℤ. Then GL(2, ℤ̂) = ∏ GL(2, ℤ_{ℓ}) is a compact group provided with a canonical projection “(modN)” onto GL(2, ℤ/N) for each N ∈ ℕ.

Led by the Čebotarev and other equidistribution theorems or conjectures, in particular, the “Cohen-Lenstra philosophy” [2], we make the following hypothesis:

(H) The series (F (E/𝔽_{p}))_{E/𝔽_{p}∈F} is equidistributed in GL(2, ℤ̂).

In more detailed terms, this means:

(1.11) Given N ∈ ℕ and any conjugacy class C in GL(2, ℤ/N), the limit

lim_{x→∞} \frac{|\{E/𝔽_{p} ∈ F | F (E/𝔽_{p})(modN) lies in C and p ≤ x\}|^{∗}}{|\{E/𝔽_{p} ∈ F | p ≤ x\}|^{∗}}

exists and equals |C|/|GL(2, ℤ/N)|.

Note that in the form just given, the hypothesis does not require specifying the p-component of F (E/𝔽_{p}), since for given N and C we may omit the finite number of terms indexed by E/𝔽_{p} with p|N without changing the limit. Note also that the number of E/𝔽_{p} with w(E/𝔽_{p}) ≠ 1 over a fixed 𝔽_{p} is uniformly bounded, and is therefore negligible for large p. That is, though (1.11) appears to be the “right” formula, the limit (provided it exists) doesn’t change upon replacing weighted by unweighted cardinalities.

Now (H) may be derived from the general “Čebotarev theorem” (Theorem 7 of [8]) of Serre, applied to the moduli scheme of elliptic curves endowed with a level-N structure, and also from Theorem 3.1 of [1]. We thus regard (H) as established, although our proofs are independent of its validity.

In [6], we studied the frequency of E/𝔽_{p} with a fixed Frobenius trace tr(E/𝔽_{p}) ∈ ℤ. The results (loc. cit., Theorems 5.5 and 6.4) turned out to be those expected by (H) (and other known properties of E/𝔽_{p}, like the result of [2]). On the other hand, (H) in the form (1.11) applied to prime powers N = ℓ^{n} along with (1.7) predicts that for each group H_{α,β}^{(ℓ)} = ℤ/ℓ^{α} × ℤ/ℓ^{β}, the prob-

ability P (F, “E(𝔽_{p})[ℓ^{∞}] ≅ H_{α,β}^{(ℓ)}”) equals the Haar volume in GL(2, ℤ_{ℓ}) of

{γ ∈ GL(2, ℤ_{ℓ}) | cok(γ − 1) ≅ H_{α,β}^{(ℓ)}}. Our Theorem 3.15 states an effective version of that identity, i.e., including the error term.

Notation. Apart from standard mathematical symbols, we use the following notation.

ℕ = {1, 2, 3, …}, ℕ_{0} = {0, 1, 2, …} and ℙ = {2, 3, 5, …} denote the sets of natural, of non-negative integral, of prime numbers, respectively, and |X| the cardinality of the set X. For m, n ∈ ℕ, “m|n” means “m divides n” and “m∥n” that m is an exact divisor of n, i.e., m|n and m is coprime with n/m.

ℤ/n is the residue class group ℤ/nℤ, and for each abelian group A and n ∈ ℕ, A[n] = {x ∈ A | nx = 0}. Further, for ℓ ∈ ℙ, A[ℓ^{∞}] = ⋃_{r∈ℕ} A[ℓ^{r}].

The symbols p and ℓ always stand for primes, and e.g. “∑_{p≤x} ⋯ ” means the sum over all primes p ≤ x.

If f and g are functions defined on suitable subsets of ℝ, then

f ∼ g :⇔ lim_{x→∞} f(x)/g(x) = 1;

f = O(g) :⇔ there exists a constant C > 0 such that f(x) ≤ Cg(x). We write f = O_{α,β}(g) to indicate that C might depend on the parameters α, β, …

2. Some Haar measures in GL(2, ℤ_{ℓ}).

In the present section, we calculate the volumes with respect to Haar measure of certain subsets of GL(2, ℤ_{ℓ}) relevant for our purposes.

(2.1) Fix a prime number ℓ, and let

M = Mat(2, ℤ_{ℓ}) be the ring of 2 × 2-matrices over ℤ_{ℓ}, and
G = GL(2, ℤ_{ℓ}), with normalized Haar measures μ on M and

ν on G, respectively.

For each natural number n, we put

M_{n} = Mat(2, ℤ/ℓ^{n}) and G_{n} = GL(2, ℤ/ℓ^{n}).

By abuse of language, and if the context allows for no ambiguity, we often write “a” for the image of a ∈ ℤ_{ℓ} (or of a ∈ ℤ/ℓ^{m} with m ≥ n) in ℤ/ℓ^{n}, etc. The reduction mapping a ⟼ \overline{a} : ℤ_{ℓ} ⟶ 𝔽_{ℓ} = ℤ/ℓ and everything derived from it will be denoted by a bar, e.g. γ ⟼ \overline{γ} : M ⟶ M_{1}. Finally, v_{ℓ} denotes both the ℓ-adic valuation on ℤ_{ℓ} and the truncated valuation ℤ/ℓ^{n} ⟶ {0, 1, …, n}.

(2.2) The possible ℓ-torsion of an elliptic curve over a finite field is of shape

H = H_{α,β} = H_{α,β}^{(ℓ)} = ℤ/ℓ^{α} × ℤ/ℓ^{β},

where 0 ≤ α ≤ β are well-defined by H. (We omit some ℓ’s in the notation.) For reasons explained in the introduction, we are interested in the volumes (with respect to ν) of the subsets

X(α, β) = {γ ∈ G | cok(γ − 1) ≅ H_{α,β}}

and

X_{r}(α, β) = {γ ∈ G | cok(γ − 1) ≅ H_{α,β}, v_{ℓ}(det(γ) − 1) = r}

of G. Here cok(δ) = ℤ_{ℓ}^{2}/δ(ℤ_{ℓ}^{2}) is the module determined by the matrix δ ∈ M. We will show:

2.3 Theorem.

(i) Given α, β ∈ ℕ_{0} with α ≤ β, we have vol_{ν}(X(α, β)) = g(α, β) with

g(α, β) = \frac{ℓ^{3}−2ℓ^{2}−ℓ+3}{(ℓ^{2}−1)(ℓ−1)}, 0 = α = β
\frac{ℓ^{2}−ℓ−1}{(ℓ−1)ℓ}ℓ^{−β}, 0 = α < β
ℓ^{−4α},  0 < α = β
\frac{ℓ+1}{ℓ}ℓ^{−β−3α}, 0 < α < β .

(ii) Given α ≤ β and r ∈ ℕ_{0}, X_{r}(α, β) is empty if r < α. Otherwise, vol_{ν}(X_{r}(α, β)) is given by the following table.

\begin{matrix}vol_{ν}(X_{r}(α, β)) & r = α & r > α \\ 0 = α = β & (\frac{ℓ−2}{ℓ−1})^{2} & \frac{ℓ^{2}−ℓ−1}{ℓ^{2}−1}ℓ^{−r} \\ 0 = α < β & \frac{ℓ−2}{ℓ−1}ℓ^{−β} & \frac{ℓ−1}{ℓ}ℓ^{−β−r} \\ 0 < α = β & \frac{ℓ^{2}−ℓ−1}{ℓ^{2}−1}ℓ^{−4α} & \frac{ℓ}{ℓ+1}ℓ^{−3α−r} \\ 0 < α < β & ℓ^{−β−3α} & \frac{ℓ+1}{ℓ}ℓ^{−β−2α−r} \end{matrix}

We need some preparations to prove the theorem. We start with three simple observations, stated without proof, where we always assume that 0 ≤ α ≤ β.

(2.4) For δ ∈ M we have the equivalence

cok(δ) ≅ H_{α,β} ⇔ δ ≡ 0 (ℓ^{α}), δ ≢ 0 (ℓ^{α+1}) and
v_{ℓ}(det δ) = α + β.

(2.5) If δ ∈ M satisfies cok(δ) ≅ H_{α,β} and δ ≡ δ′(ℓ^{n}) with n > β then cok(δ′) ≅ H_{α,β}.

As a consequence we get:

(2.6) If n > β then

vol_{μ}{δ ∈ M | cok(δ) ≅ H_{α,β}} = ℓ^{−4n}|{δ ∈ M_{n} | cok(δ) ≅ H_{α,β}}|.

That number is easy to determine.

2.7 Proposition.

\begin{aligned}vol_{μ}\{δ ∈ M | cok(δ) ≅ H_{α,β}\} & = & (1 − ℓ^{−1})(1 − ℓ^{−2})ℓ^{−4α}, & 0 ≤ α = β \\ & & (1 − ℓ^{−2})^{2}ℓ^{−β−3α}, & 0 ≤ α < β. \end{aligned}

Proof. In view of (2.4) and the bijection δ ⟼ ℓ^{−α}δ of {δ ∈ M_{n} | cok(δ) ≅ H_{α,β}} with {ϵ ∈ M_{n−α} | cok(ϵ) ≅ H_{0,β−α}}, valid for n > β, the proof boils down to counting of matrices ϵ in M_{n−α} with \overline{ϵ} ≠ 0 and given value of v_{ℓ}(det ϵ). We omit the details. □

2.8 Remark. The volume of {δ ∈ Mat(n, ℤ_{ℓ}) | cok(δ) ≅ H} has been calculated by Friedman and Washington in full generality, i.e., for arbitrary n and abelian ℓ-groups H (see Proposition 3.1 of [5]). In our special case however, it is less complicated to apply the simple proof scheme given above than to extract (2.7) from the general result.

Similar to (2.6) we have

(2.9)

vol_{ν}(X(α, β)) = |G_{n}|^{−1}|{γ ∈ G_{n} | cok(γ − 1) ≅ H_{α,β}}|

and

vol_{ν}(X_{r}(α, β)) = |G_{n}|^{−1}|{γ ∈ G_{n} | cok(γ − 1) ≅ H_{α,β},
v_{ℓ}(det(γ) − 1) = r}|,

where n > β in the first and n > max(β, r) in the second case.

Note that

(2.10)  |G_{n}| = |G_{1}|ℓ^{4(n−1)} = (ℓ^{2} − 1)(ℓ − 1)ℓ^{4n−3}.

Thus (2.3) will be established as soon as we determine the numerators in (2.9).

Let γ ∈ G with residue class \overline{γ} ∈ G_{1} = GL(2, 𝔽_{ℓ}) be given, and suppose that cok(γ − 1) ≅ H_{α,β} with 0 ≤ α ≤ β.

2.11 Lemma. We have

(I) 0 = α = β ⇔ 1 is not an eigenvalue of \overline{γ}. There are ℓ(ℓ^{3} − 2ℓ^{2} − ℓ + 3) such elements \overline{γ} ∈ G_{1}, among which there are ℓ(ℓ^{2} − ℓ − 1) with determinant 1;

(II) 0 = α < β ⇔ \overline{γ} − 1 has rank 1 ⇔ \overline{γ} is conjugate to \binom{1 1}{0 1} (case IIa) or

\overline{γ} is conjugate to \binom{1 0}{0 d} with d ∈ 𝔽_{ℓ} − \{0, 1\} (case IIb). There are ℓ^{2} − 1 (case IIa) and (ℓ + 1)ℓ(ℓ − 2) (case IIb) such \overline{γ} ∈ G_{1};

(III) 0 < α ≤ β ⇔ \overline{γ} = 1.

Proof. For δ = γ − 1 we have cok(δ)/ℓ cok(δ) = cok(\overline{δ}), and thus the equivalences are obvious. Now the centralizer of \binom{1 1}{0 1} (resp. of \binom{1 0}{0 d}) in G_{1} consists of the matrices of shape \binom{a b}{0 a} (resp. the diagonal matrices) in G_{1}, from which we find the numbers of \overline{γ} subject to condition IIa (resp. IIb) and, finally, of \overline{γ} subject to I. There are ℓ^{3} − ℓ elements \overline{γ} of determinant 1, of which ℓ^{2} − 1 (resp. 1) are of type II (resp. III), thus ℓ^{3} − ℓ^{2} − ℓ of type I. □

Next, we need a series of lemmas that count numbers of matrices in M_{n} with various properties.

2.12 Lemma. (i) The number of \overline{δ} ∈ M_{1} such that det(\overline{δ}) ≠ 0 equals ℓ(ℓ^{2} − 1)(ℓ − 1). A share of ℓ · (ℓ^{2} − 1)^{−1}, i.e., precisely ℓ^{2}(ℓ − 1) of them, satisfy tr(\overline{δ}) = 0.

126 Ernst-Ulrich Gekeler

(ii) The number of 0 ≠ \overline{δ} ∈ M_{1} such that det(\overline{δ}) = 0 equals (ℓ − 1)(ℓ + 1)^{2}. A share of (ℓ + 1)^{−1}, i.e., precisely ℓ^{2} − 1 of them, satisfy tr(\overline{δ}) = 0. Proof. Omitted. □ 2.13 Lemma. Let n ∈ ℕ and δ_{n} ∈ M_{n} = Mat(2, ℤ/ℓ^{n}) be given, and suppose that

tr(δ_{n}) + det(δ_{n}) ≡ 0 (ℓ^{n}).

Then there are precisely ℓ^{3} elements δ_{n+1} ∈ M_{n+1} such that δ_{n+1} ≡ δ_{n}(ℓ^{n}) and

tr(δ_{n+1}) + det(δ_{n+1}) ≡ 0 (ℓ^{n+1}).

Proof. Writing δ_{n} = \binom{a b}{c d} with a, b, c, d ∈ ℤ/ℓ^{n}, we have

(∗)  a + d + ad − bc = 0.

If \overline{a} ≠ −1, we write the left hand side as d(1 + a) + a − bc, choose arbitrary lifts ã, b̃, c̃ of a, b, c in ℤ/ℓ^{n+1} and solve for d̃ such that (∗) holds for ã, b̃, c̃, d̃. If \overline{a} = −1 but \overline{d} ≠ −1, we may exchange the parts of a and d. If both \overline{a} and \overline{d} equal −1 then \overline{b}\overline{c} = −1, we may arbitrarily choose lifts ã, b̃, d̃ of a, b, d and solve for c̃. In any case, we get precisely ℓ^{3} matrices δ_{n+1} = (\begin{matrix}ã & b̃ \\ c̃ & d̃ \end{matrix}) ∈ M_{n+1} as required. □ 2.14 Lemma. Let 0 < β < n and \overline{d} ∈ 𝔽_{ℓ}−\{0\} be fixed. The number of matrices δ = \binom{a b}{c d} ∈ M_{n} such that \overline{δ} = \binom{0 0}{0 \overline{d}} and v_{ℓ}(ad − bc) = β is (ℓ − 1)ℓ^{4n−4−β}. Proof. For each of the (ℓ − 1)ℓ^{n−1−β} possible values of “det” in ℤ/ℓ^{n} with v_{ℓ}(det) = β, the quantities b, c and d may be freely chosen subject to \overline{b} = 0 = \overline{c} and d ≡ \overline{d}(ℓ), and then a = d^{−1}(det +bc). □ 2.15 Lemma. Let t, u ∈ ℤ/ℓ^{n} be given with \overline{t} = 0 = \overline{u}. There are precisely (ℓ^{2} − 1)ℓ^{2(n−1)} elements ϵ = \binom{a b}{c d} of M_{n} such that \overline{ϵ} ≠ 0, tr(ϵ) = t and det(ϵ) = u. Proof. Choose a ∈ ℤ/ℓ^{n}, which determines d = t − a. If \overline{a} ≠ 0 then \overline{d} ≠ 0, and we may freely choose b ∈ (ℤ/ℓ^{n})^{∗} and solve for c in

(∗)  ad − u = bc.

If \overline{a} = 0 then \overline{d} = 0, either b or c is invertible, and we may solve for the other one in (∗). Counting the number of possible choices yields the stated value. □ Now we are ready for the Proof of Theorem 2.3. At several occasions, we will use the trivial identity

(1)  det(1 + δ) = 1 + tr(δ) + det(δ)

for 2 × 2-matrices δ. Among other things, it implies (together with (2.4)) that X_{r}(α, β) is empty for r < α. Case 0 = α = β From (2.9), putting n = 1, and (2.11), we see after a little calculation that the volumes of X(0, 0) and X_{0}(0, 0) are as asserted. Let \overline{γ} = 1+\overline{δ} ∈ G_{1} be such that \overline{δ} also belongs to G_{1}. By (2.11), there are precisely ℓ(ℓ^{2}− ℓ − 1) such \overline{γ} with determinant 1, i.e., using (1), such that tr(\overline{δ}) + det(\overline{δ}) = 0. By induction on n, using (2.13), we see that among the ℓ^{4(n−1)} lifts γ_{n} = 1+δ_{n} of \overline{γ} to G_{n}, there are precisely ℓ^{3(n−1)} that satisfy det(γ_{n}) ≡ 1 (ℓ^{n}), if n ≥ 2. For r ≥ 1 and n := r + 1, (2.9) yields

Documenta Mathematica 11 (2006) 119–142

vol(X_{r}(0, 0)) = \frac{ℓ(ℓ^{2} − ℓ − 1)ℓ^{3(r−1)}(ℓ^{4} − ℓ^{3})}{(ℓ^{2} − 1)(ℓ − 1)l^{4r+1}} = \frac{ℓ^{2} − ℓ − 1}{ℓ^{2} − 1}ℓ^{−r}.

Case 0 = α < β According to (2.4) and (2.9), we have for n > β

vol(X(0, β)) = |G_{n}|^{−1}|\{γ ∈ G_{n} | \overline{γ} ≠ 1, v_{ℓ}(det(γ − 1)) = β\}|.

Any γ = 1 + δ as above satisfies (see (2.11)):

• \overline{γ} ∈ G_{1} is conjugate to \binom{1 1}{0 1}, which happens ℓ^{2} − 1 times, or
• \overline{γ} is conjugate to \binom{1 0}{0 d′}, which happens (ℓ + 1)ℓ(ℓ − 2) times.

Thus we have to count the number of lifts γ ∈ G_{n} of \overline{γ} such that v_{ℓ}(det(γ−1)) = β, i.e., of lifts δ of \overline{δ} with v_{ℓ}(det δ) = β. Clearly, that number is invariant under conjugation, so we may assume that

• \overline{γ} = \binom{1 1}{0 1}, i.e., \overline{δ} = \binom{0 1}{0 0}, or
• \overline{γ} = \binom{1 0}{0 d′}, i.e., \overline{δ} = \binom{0 0}{0 d} with d = d′ − 1 ∈ 𝔽_{ℓ} − \{0, −1\}.

In both cases, Lemma 2.14 (after possibly permuting the rows of \overline{δ}) yields the same number (ℓ − 1)ℓ^{4n−4−β} of lifts of the wanted type. Therefore,

\begin{aligned}vol(X(0, β)) & = & |G_{n}|^{−1}[ℓ^{2} − 1 + (ℓ + 1)ℓ(ℓ − 2)](ℓ − 1)ℓ^{4n−4−β} \\ & = & \frac{ℓ^{2}−ℓ−1}{(ℓ−1)ℓ}ℓ^{−β}. \end{aligned}

In order to find vol(X_{r}(0, β)), we must determine the number of lifts γ as above that moreover satisfy

det γ ≡ 1 (ℓ^{r}), ≢ 1 (ℓ^{r+1}), where r < n, i.e., n > max(β, r).

Suppose r > 0 and \overline{γ} conjugate to \binom{1 1}{0 1}, without restriction, \overline{γ} = \binom{1 1}{0 1}, \overline{δ} = \binom{0 1}{0 0}. The number of lifts is the number of δ = \binom{a b}{c d} ∈ M_{n} such that

(2) a ≡ c ≡ d ≡ 0, b ≡ 1 (ℓ)
(3) a + d + ad − bc = tr(δ) + det(δ) ≡ 0 (ℓ^{r}), ≢ 0 (ℓ^{r+1})
(4) v_{ℓ}(det δ) = β

hold. Now there are

• (ℓ − 1)ℓ^{n−β−1} choices of det(δ) subject to (4);

• ℓ^{n−1} free choices for a and b each subject to (2);

• (ℓ − 1)ℓ^{n−r−1} choices for d compatible with (2), (3) and the choices made of det(δ) and a, which together determine c = b^{−1}(ad − det(δ)). Therefore, \overline{γ} has (ℓ−1)^{2}ℓ^{4(n−1)−r−β} lifts of the wanted type. If, on the other hand, \overline{γ} is conjugate to \binom{1 0}{0 d′} with d′ ≠ 0, 1, then any lift γ satisfies det(γ) ≢ 1 (ℓ^{r}). Hence

vol(X_{r}(0, β)) = |G_{n}|^{−1}(ℓ^{2} − 1)(ℓ − 1)^{2}ℓ^{4(n−1)−r−β} = \frac{ℓ−1}{ℓ}ℓ^{−β−r}.

Suppose r = 0 . If \overline{γ} is unipotent, no lifts of the wanted type exist. Thus let \overline{γ} = \binom{1 0}{0 d′} with d′ ∈ 𝔽_{ℓ} − \{0, 1\}. Any lift γ ∈ G_{n} of \overline{γ} satisfies det(γ) ≢ 1 (ℓ), so we have for n > β

vol(X_{0}(0, β)) = |G_{n}|^{−1}(ℓ + 1)ℓ(ℓ − 2)(ℓ − 1)ℓ^{4n−4−β} = \frac{ℓ−2}{ℓ−1}ℓ^{−β}.

It remains to treat the

Case 0 < α ≤ β . Here, for n > β,

vol(X(α, β)) = |G_{n}|^{−1}|\{γ ∈ M_{n} | \overline{γ} = 1, cok(γ − 1) ≅ H_{α,β}\}|.

The condition on γ = 1 + δ is equivalent with \overline{δ} = 0, cok(δ) ≅ H_{α,β}, i.e., with cok(δ′) ≅ H_{α−1,β−1} for δ′ := ℓ^{−1}δ ∈ M_{n−1}. The number of such δ′ is given by (2.6) and (2.7), and yields the stated result for vol(X(α, β)).

Now to find vol(X_{r}(α, β)), where r ≥ α, we need to analyze the condition

(5) cok(δ) ≅ H_{α,β}, det(1 + δ) ≡ 1 (ℓ^{r}), ≢ 1 (ℓ^{r+1}) for δ ∈ M_{n} and n > max(β, r). Note that cok(δ) ≅ H_{α,β} implies δ ≡ 0 (ℓ^{α}), ≢ 0 (ℓ^{α+1}). Thus, letting ϵ := ℓ^{−α}δ ∈ M_{n−α}, (5) is equivalent with (6) \overline{ϵ} ≠ 0, v_{ℓ}(det ϵ) = β − α, tr(ϵ) + ℓ^{α} det(ϵ) ≡ 0 (ℓ^{r−α}),

≢ 0 (ℓ^{r−α+1}).

Suppose α = β . If r = α then (6) is equivalent with ϵ ∈ G_{n−α}, tr(\overline{ϵ}) ≠ 0, and the volume of X_{α}(α, α) comes out by (2.9) along with (2.12), putting n = α+1.

Each of the ℓ^{2}(ℓ − 1) elements δ = δ_{α+1} ∈ M_{α+1} subject to

cok(δ) ≅ H_{α,α}, tr(δ) ≡ 0 (ℓ^{α+1})

has precisely ℓ^{3(n−α−1)} lifts δ_{n} to M_{n} (n ≥ α + 1) such that

tr(δ_{n}) + det(δ_{n}) ≡ 0 (ℓ^{n}),

by (2.13). Therefore, for r > α ,

|{δ ∈ M_{r+1} | cok(δ) ≅ H_{α,α}, tr(δ) + det(δ) ≡ 0 (ℓ^{r}), ≢ 0 (ℓ^{r+1})}|
= ℓ^{2}(ℓ − 1)ℓ^{3(r−α−1)}(ℓ^{4} − ℓ^{3}),

which together with (2.9) yields the stated result for vol(X_{r}(α, α)).

Suppose α < β . By virtue of Lemma 2.15, we have for r > α and n > max(β, r):

|\{ϵ ∈ M_{n−α} | \overline{ϵ} ≠ 0, v_{ℓ}(det ϵ) = β − α, tr(ϵ) + ℓ^{α} det(ϵ) ≡ 0 (ℓ^{r−α}),
≢ 0 (ℓ^{r−α+1})}|
= (ℓ^{2} − 1)ℓ^{2(n−α−1)} | {(t, u) ∈ ℤ/ℓ^{n} × ℤ/ℓ^{n} | (t, u) subject to (7)}|

with the condition

(7) \overline{t} = 0 = \overline{u}, v_{ℓ}(u) = β − α, t + ℓ^{α}u ≡ 0 (ℓ^{r−α}), ≢ 0 (ℓ^{r−α+1}). For the number of these pairs (t, u), we find (ℓ − 1)^{2}ℓ^{2n−β−r−2}, which yields vol(X_{r}(α, β)) for r > α. Finally,

vol(X_{α}(α, β)) = vol(X(α, β)) − ∑_{r>α} vol(X_{r}(α, β)),

which allows to fill in the last missing entry in the statement of Theorem 2.3. □

(2.16) Put X_{r} := {γ ∈ G | v_{ℓ}(det(γ) − 1) = r}. We have the obvious formula

\begin{aligned}vol_{ν}(X_{r}) & = & \frac{ℓ−2}{ℓ−1}, & r = 0 \\ & & ℓ^{−r}, & r > 0. \end{aligned}

Then we may interpret Theorem 2.3 as follows. Define for 0 ≤ α ≤ β, r ≥ 0 and (r, ℓ) ≠ (0, 2):

(2.17)  g_{r}(α, β) := \frac{vol_{ν}(X_{r}(α, β))}{vol_{ν}(X_{r})},

and recall that g(α, β) = vol_{ν}(X(α, β)). Then

g(α, β) = probability of γ ∈ G to satisfy cok(γ − 1) ≅ ℤ/ℓ^{α} × ℤ/ℓ^{β}

and

g_{r}(α, β) = probability for the same event under the
assumption v_{ℓ}(det(γ) − 1) = r.

2.18 Corollary. The conditional probability g_{r}(α, β) is zero if r < α, and otherwise is given by the table below, where the two entries marked with “∗” are undefined for ℓ = 2.

\begin{matrix}g_{r}(α, β) & r = α & r > α \\ 0 = α = β & \frac{ℓ−2}{ℓ−1} ∗ & \frac{ℓ^{2}−ℓ−1}{ℓ^{2}−1} \\ 0 = α < β & ℓ^{−β} ∗ & \frac{ℓ−1}{ℓ}ℓ^{−β} \\ 0 < α = β & \frac{ℓ^{2}−ℓ−1}{ℓ^{2}−1}ℓ^{−3α} & \frac{ℓ}{ℓ+1}ℓ^{−3α} \\ 0 < α < β & ℓ^{−β−2α} & \frac{ℓ−1}{ℓ}ℓ^{−β−2α} \end{matrix}

That is, we have g_{r}(α, β) = π_{r}(α, β)ℓ^{−β−2α} with some factor π_{r}(α, β) ∈ \{0, \frac{ℓ−2}{ℓ−1}, \frac{ℓ^{2}−ℓ−1}{ℓ^{2}−1}, \frac{ℓ−1}{ℓ}, \frac{ℓ}{ℓ+1}, 1\}. Note that

(2.19) π_{r}(α, α) increases if r = α is replaced with r > α. On the other hand, if α is less than β then π_{r}(α, β) decreases upon enlarging r from α to r > α. In any case, g_{r}(α, β) is independent of r as long as r > α.

3. Probabilities of group structures.

We first summarize some results of E. Howe from [7], which will play a crucial role.

(3.1) Define the multiplicative arithmetic functions φ and ψ through their values on prime powers ℓ^{α}, α ≥ 1:

φ(ℓ^{α}) = ℓ^{α−1}(ℓ − 1), ψ(ℓ^{α}) = ℓ^{α−1}(ℓ + 1),

i.e., φ is the Euler function. Further, given a prime number p ≥ 5 and m, n ∈ ℕ with m|n, put

w_{p}(m, n) = \frac{1}{2} ∑_{E(𝔽_{p})[n]≅ℤ/m×ℤ/n} w(E/𝔽_{p}),

where E runs through the 𝔽_{p}-isomorphism classes of elliptic curves over 𝔽_{p} with the property that E(𝔽_{p})[n] ≅ ℤ/m × ℤ/n. Up to the factor \frac{1}{2} (introduced to be in keeping with [7]), w_{p}(m, n) is a weighted cardinality | |^{∗} in the sense of (1.9). Howe defines the approximation

(3.2)  ŵ_{p}(m, n) = p\frac{ψ(n/m)}{mφ(n)ψ(n)} ∏_{ℓ|gcd(n,p−1)/m} (1 − ℓ^{−1}),

where ℓ runs through the prime divisors of gcd(n, p − 1)/m, if m|p − 1, and ŵ_{p}(m, n) = 0 otherwise. Note that

(3.3)  p^{−1}w_{p}(1, 1) = p^{−1}ŵ_{p}(1, 1) = 1.

On p. 245 of [7], he obtains the inequality

(3.4)  |w_{p}(m, n) − ŵ_{p}(m, n)| ≤ C(m, n)p^{1/2}

with the constant

C(m, n) = (1/12 + 5/6\sqrt{2})ψ(n/m)2^{ω(n)}

independent of p. Here ω(n) := number of different prime divisors of n. Briefly,

w_{p}(m, n) = ŵ_{p}(m, n) + O_{m,n}(p^{1/2}).

It is obvious that the 2-variable function p^{−1}ŵ_{p}(m, n) localizes, that is

(3.5)  p^{−1}ŵ_{p}(m, n) = ∏_{ℓ} p^{−1}ŵ_{p}(ℓ^{α_{ℓ}}, ℓ^{β_{ℓ}})

if m = ∏_{ℓ} ℓ^{α_{ℓ}}, n = ∏_{ℓ} ℓ^{β_{ℓ}}, 0 ≤ α_{ℓ} ≤ β_{ℓ} with pairwise different prime numbers ℓ. The factors on the right hand side are simple functions of ℓ, α_{ℓ}, β_{ℓ} and

r(p, ℓ) := r ∈ ℕ_{0} such that ℓ^{r}∥p − 1,

i.e., the dependence on p is via r(p, ℓ) only. We therefore define for 0 ≤ α ≤ β:

(3.6)  h_{r}^{(ℓ)}(α, β) := p^{−1}ŵ_{p}(ℓ^{α}, ℓ^{β}),

where r = r(p, ℓ). It vanishes for r < α; otherwise, its values are given by the following table.

3.7 Table for h_{r}^{(ℓ)}(α, β).

r = α  r > α
0 = α = β 1 1
0 = α < β \frac{ℓ}{ℓ−1}ℓ^{−β}  ℓ^{−β}
0 < α = β \frac{ℓ^{2}}{ℓ^{2}−1}ℓ^{−3α}  \frac{ℓ}{ℓ+1}ℓ^{−3α}
0 < α < β \frac{ℓ}{ℓ−1}ℓ^{−β−2α} ℓ^{−β−2α}

Fix ℓ, α and β for the moment, and let

H = H_{α,β}^{(ℓ)} = ℤ/ℓ^{α} × ℤ/ℓ^{β}.

From the above, replacing w_{p} by its approximation ŵ_{p}, and taking (1.9) into account, we may regard

h_{r}^{(ℓ)}(α, β) ≈ \frac{|\{E/𝔽_{p} | E(𝔽_{p})[ℓ^{β}] ≅ H\}|^{∗}}{|\{E/𝔽_{p}\}|^{∗}}

as the probability that a randomly chosen E/𝔽_{p} (with our fixed p subject to r(p, ℓ) = r) satisfies “E(𝔽_{p})[ℓ^{β}] ≅ H”. The associated probability of “E(𝔽_{p})[ℓ^{∞}] ≅ H” is

(3.8)  \begin{aligned}g_{r}^{(ℓ)}(α, β) & := & h_{r}^{(ℓ)}(α, β) − h_{r}^{(ℓ)}(α, β + 1), \\ & & r = 0 or r > 0, α < β \\ & = & h_{r}^{(ℓ)}(α, α) − h_{r}^{(ℓ)}(α, α + 1) − h_{r}^{(ℓ)}(α + 1, α + 1), \\ & & r > 0, α = β \end{aligned}

since, e.g., the event “E(𝔽_{p})[ℓ^{∞}] ≅ ℤ/ℓ^{α} × ℤ/ℓ^{β}” for α < β is equivalent with: “E(𝔽_{p})[ℓ^{β}] ≅ ℤ/ℓ^{α} × ℤ/ℓ^{β}” but not “E(𝔽_{p})[ℓ^{β+1}] ≅ ℤ/ℓ^{α} × ℤ/ℓ^{β+1}”.

More precisely, we get from (3.4) that

(3.9)  \frac{|\{E/𝔽_{p} | E(𝔽_{p})[ℓ^{∞}] ≅ H\}|^{∗}}{|\{E/𝔽_{p}\}|^{∗}} = g_{r}^{(ℓ)}(α, β) + O_{ℓ,α,β}(p^{−1/2}),

where the constant implied by the O-symbol depends only on ℓ, α, β (and may easily be determined). Evaluating (3.8) by means of (3.7), which requires a number of case distinctions, we find:

(3.10) The present g_{r}^{(ℓ)}(α, β) agrees with the conditional probability (where ℓ, α, β are fixed) g_{r}(α, β) defined in (2.17) and described by the table in (2.18).

So far, p has been fixed. Letting p vary subject to r(p, ℓ) = r with some fixed r and taking (1.10) into account yields for p ≤ x ∈ ℝ:

(3.11)  \begin{matrix}|\{E/𝔽_{p} ∈ F | p ≤ x, r(p, ℓ) = r, E(𝔽_{p})[ℓ^{∞}] ≅ H\}|^{∗} \\ = 2g_{r}^{(ℓ)}(α, β) ∑ p + O_{ℓ,α,β}(∑ p^{1/2}), \end{matrix}

where the sum in both cases ranges through

{p ∈ ℙ | p ≤ x, r(p, ℓ) = r} = {p ≤ x | ℓ^{r}∥p − 1}.

(Strictly speaking, we had to assume that p ≥ 5, but including p = 2, 3 doesn’t change the asymptotic behavior. Thus we will neglect from now on the restriction of p ≥ 5.)

We need a well-known fact from analytic number theory, an explicit reference of which is nonetheless difficult to find.

3.12 Proposition. Let γ > −1 be a real number and a, m coprime natural numbers. Then

∑_{{p≤x prime \atop p≡a (m)}} p^{γ} ∼ \frac{1}{φ(m)} \frac{1}{1 + γ} \frac{x^{1+γ}}{log x} ,

where “∼” denotes asymptotic equivalence.

Proof (sketch). Note that the assertion includes the prime number theorem (γ = 0, m = 1) and Dirichlet’s theorem on primes in arithmetic progressions (γ = 0). The general case (γ > −1 arbitrary) results from the case γ = 0 by Abel summation (see the instructions and notation given in [9] pp. 3,4) of the series ∑_{n≤x} a_{n}b(n) with

a_{n} = \{ \begin{matrix}1, & n ≡ a(m), n prime \\ 0, & otherwise, \end{matrix}

and the C^{1}-function b with b(x) = x^{γ}. □

In particular,

∑_{{p≤x \atop r(p,ℓ)=r}} p^{1/2} ∼ \frac{2}{3}(\frac{1}{φ(ℓ^{r})} − \frac{1}{φ(ℓ^{r+1})})\frac{x^{3/2}}{log x},

so the expression in (3.11) becomes

2g_{r}^{(ℓ)}(α, β) ∑ p + (\frac{1}{φ(ℓ^{r})} − \frac{1}{φ(ℓ^{r+1})})O_{ℓ,α,β}(\frac{x^{3/2}}{log x}).

Applying (3.12) also to the first sum ∑ p in (3.11) yields

(3.13)  \frac{|\{E/𝔽_{p} | p ≤ x, r(p, ℓ) = r, E(𝔽_{p})[ℓ^{∞}] ≅ H\}|^{∗}}{|\{E/𝔽_{p} | p ≤ x, r(p, ℓ) = r\}|^{∗}} ; = g_{r}^{(ℓ)}(α, β) + O_{ℓ,α,β}(x^{−1/2}),

where the implied constant depends only on ℓ, α, β but not on r. Apart from the condition “r(p, ℓ) = r”, this expresses g_{r}^{(ℓ)}(α, β) as a probability in the sense of (1.4). It remains to evaluate

P \{F, “E(𝔽_{p})[ℓ^{∞}] ≅ H”) = lim_{x→∞} \frac{|\{E/𝔽_{p} | p ≤ x, E(𝔽_{p})[ℓ^{∞}] ≅ H\}|^{∗}}{|\{E/𝔽_{p} | p ≤ x\}|^{∗}} .

It is tempting to calculate it via the conditional probabilities g_{r}^{(ℓ)}(α, β) simply as

∑_{r≥0}(\frac{1}{φ(ℓ^{r})} − \frac{1}{φ(ℓ^{r+1})})g_{r}^{(ℓ)}(α, β),

Documenta Mathematica 11 (2006) 119–142

where \frac{1}{φ(ℓ^{r})} − \frac{1}{φ(ℓ^{r+1})} = vol_{ν}(X_{r}) (see (2.16)) is the probability of p to satisfy r(p, ℓ) = r. This will turn out to be true, but requires reversing the order in which we evaluate a double limit, and needs to be justified.

We have

\begin{matrix}|\{E/𝔽_{p} | p ≤ x, E(𝔽_{p})[ℓ^{∞}] ≅ H\}|^{∗} \\ = ∑_{r≥0}[2g_{r}^{(ℓ)}(α, β) ∑_{{p≤x \atop r(p,ℓ)=r}} p + (\frac{1}{φ(ℓ^{r+1})} − \frac{1}{φ(ℓ^{r+1})})O_{ℓ,α,β}(\frac{x^{3/2}}{log x})]. \end{matrix}

Now g_{r}^{(ℓ)}(α, β) = 0 if r < α and g_{r}^{(ℓ)}(α, β) = g_{α+1}^{(ℓ)}(α, β) for r > α. Therefore, the above is

2g_{α}^{(ℓ)}(α, β) ∑_{{p≤x \atop r(p,ℓ)=α}} p + 2g_{α+1}^{(ℓ)}(α, β) ∑_{{p≤x \atop r(p,ℓ)>α}} p + O_{ℓ,α,β}(x^{3/2}/ log x).

From (3.12) and (2.17) we find that

2g_{α}^{(ℓ)}(α, β) ∑_{{p≤x \atop r(p,ℓ)=α}} p ∼ vol_{ν}(X_{α}(α, β))x^{2}/ log x,
2g_{α+1}^{(ℓ)}(α, β) ∑_{{p≤x \atop r(p,ℓ)>α}} p ∼ \frac{ℓ}{ℓ−1}vol_{ν}(X_{α+1}(α, β))x^{2}/ log x.

Comparing with (2.3) yields in all the four cases

vol_{ν}(X_{α}(α, β)) + \frac{ℓ}{ℓ−1}vol_{ν}(X_{α+1}(α, β)) = g^{(ℓ)}(α, β).

Thus, dividing by |{E/𝔽_{p} | p ≤ x}|^{∗} = 2 ∑_{p≤x} p ∼ x^{2}/ log x, we finally get

(3.14)  \frac{|\{E/𝔽_{p} | p ≤ x, E(𝔽_{p})[ℓ^{∞}] ≅ H\}|^{∗}}{|\{E/𝔽_{p} | p ≤ x\}|^{∗}} = g^{(ℓ)}(α, β) + O_{ℓ,α,β}(x^{− \frac{1}{2}} ).

Hence, in fact

P (F, “E(𝔽_{p})[ℓ^{∞}] ≅ H”) = g^{(ℓ)}(α, β) = vol_{ν}(X(α, β)),

where X(α, β) = X^{(ℓ)}(α, β) is the ℓ-adic set defined in (2.2).

We may summarize our results (3.13) and (3.14) as follows.

3.15 Theorem. Let a prime number ℓ and 0 ≤ α ≤ β be given.

(i) The probability P (F, “E(𝔽_{p})[ℓ^{∞}] ≅ ℤ/ℓ^{α} × ℤ/ℓ^{β}”) in the sense of (1.4) exists and equals the value g^{(ℓ)}(α, β) given in (2.3).

(ii) Fix moreover a non-negative integer r. The conditional probability P (F, “E(𝔽_{p})[ℓ^{∞}] ≅ ℤ/ℓ^{α} × ℤ/ℓ^{β}” | “ℓ^{r}∥p − 1”) for “E(𝔽_{p})[ℓ^{∞}] ≅ ℤ/ℓ^{α} × ℤ/ℓ^{β}” under the assumption “ℓ^{r}∥p − 1” exists and equals the value of g_{r}^{(ℓ)}(α, β) given in (2.18).

In both cases the error terms are O_{ℓ,α,β}(x^{−1/2}).

Note that the probabilities thus found are those predicted by the hypothesis (H) formulated in the introduction.

3.16 Example. We consider the probability that the 2-part of E(𝔽_{p}) is isomorphic with H = ℤ/4 × ℤ/4 under congruence conditions for p. According to (3.15), it is

1/3 · 2^{−6} for p ≡ 5 (8)

and increases to

2/3 · 2^{−6} for p ≡ 1 (8).

If we replace H by H′ = ℤ/4 × ℤ/8, the probability is

2^{−7} for p ≡ 5 (8)

and decreases to

2^{−8} for p ≡ 1 (8).

4. The probability spaces.

Theorem 3.15 has the drawback that it relies on the ad hoc notion (1.4) of probability and does not involve probability spaces in the ordinary sense. Here we will remedy this defect and put (3.15) in the framework of “ordinary” probability theory.

(4.1) For what follows, we fix a prime ℓ and put 𝔛^{(ℓ)} for the set of all pairs (H, r), where H is a group of shape ℤ/ℓ^{α} × ℤ/ℓ^{β} with 0 ≤ α ≤ β and α ≤ r ∈ ℕ_{0}. Hence elements of 𝔛^{(ℓ)} correspond bijectively to triples (α, β, r) ∈ ℕ_{0}^{3} with α ≤ min(β, r), which we often use as an identification. By (2.3), the function

P^{(ℓ)} : (α, β, r) ⟼ vol_{ν}(X_{r}^{(ℓ)}(α, β))

turns 𝔛^{(ℓ)} into a discrete probability space (d.p.s.). (By a d.p.s. we understand a countable set provided with a probability measure in which each non-empty subset is measurable with positive volume.)

Given (H_{α,β}^{(ℓ)}, r) = (α, β, r) ∈ 𝔛^{(ℓ)}, we define

A_{α,β,r} := {E/𝔽_{p} ∈ F | E(𝔽_{p})[ℓ^{∞}] ≅ H_{α,β}^{(ℓ)}, r(p, ℓ) = r}.

We further let 𝔄^{(ℓ)} be the σ-algebra of subsets of F generated by all the sets A_{α,β,r}. Hence the elements of 𝔄^{(ℓ)} are the subsets A_{𝔜} of F, where 𝔜 is an arbitrary (finite or countably infinite) subset of 𝔛^{(ℓ)} and

A_{𝔜} = ⋃_{(α,β,r)∈𝔜} A_{α,β,r} (disjoint union).

4.2 Proposition. For each subset 𝔜 of 𝔛^{(ℓ)}, the limit P (F, A_{𝔜}) as in (1.4) exists, and is given as ∑_{(α,β,r)∈𝔜} P (F, A_{α,β,r}).

Here P (F, A_{α,β,r})  =  P (F, “E(𝔽_{p})[ℓ^{∞}] ≅ H_{α,β}^{(ℓ)}, r(p, ℓ) = r”)  =

vol_{ν}(X_{r}^{(ℓ)}(α, β)) by (3.15).

Proof. We must check the identity

(?)  \begin{matrix}lim & x→∞ & \frac{|\{E/𝔽_{p}∈F | p≤x, (E(𝔽_{p})[ℓ^{∞}], r(p,ℓ))∈𝔜\}|^{∗}}{|\{E/𝔽_{p}∈F | p≤x\}|^{∗}} \\ = ∑_{(α,β,r)∈𝔜} P (F, A_{α,β,r}), \end{matrix}

which is obvious from (3.15) if 𝔜 is finite. Let f_{𝔜}(x) be the argument of the limit in the left hand side of (?). Then for each finite subset 𝔜_{0} of 𝔜,

lim ; inf_{x→∞}f_{𝔜}(x) ≥ ∑_{(α,β,r)∈𝔜_{0}} P (F, A_{α,β,r}),

thus

lim ; inf_{x→∞}f_{𝔜}(x) ≥ ∑_{(α,β,r)∈𝔜} P (F, A_{α,β,r}).

If 𝔜^{c} denotes the complement 𝔛^{(ℓ)} − 𝔜 of 𝔜, we have A_{𝔜^{c}} = F − A_{𝔜} and f_{𝔜^{c}}(x) = 1 − f_{𝔜}(x). Thus reversing the parts of 𝔜 and 𝔜^{c} yields

lim ; sup_{x→∞}f_{𝔜}(x) ≤ ∑_{(α,β,r)∈𝔜} P (F, A_{α,β,r}).

□

As a consequence of (4.2), the function P (F, ·) is countably additive on 𝔄^{(ℓ)} and therefore a probability measure. The following is then obvious.

4.3 Corollary. The σ-algebra 𝔄^{(ℓ)} provided with its probability measure P (F, ·) is canonically isomorphic with the discrete probability space (𝔛^{(ℓ)}, P^{(ℓ)}).

It is easy to generalize the preceding to cover the case of events that involve a finite number of primes ℓ. Thus let L ⊂ ℙ be a finite set of primes. The cartesian product

𝔛^{(L)} = ∏_{ℓ∈L} 𝔛^{(ℓ)}

provided with the product measure P^{(L)} is itself a d.p.s. On the other hand, given x = (α_{ℓ}, β_{ℓ}, r_{ℓ})_{ℓ∈L} ∈ 𝔛^{(L)}, we define

A_{x} := {E/𝔽_{p} ∈ F | ∀ℓ ∈ L : E(𝔽_{p})[ℓ^{∞}] ≅ H_{α_{ℓ},β_{ℓ}}^{(ℓ)}, r(p, ℓ) = r_{ℓ}}

and let 𝔄^{(L)} be the σ-algebra in F generated by all the A_{x}, x ∈ 𝔛^{(L)}. Then 𝔄^{(L)} = {A_{𝔜} | 𝔜 ⊂ 𝔛^{(L)}} with the obvious definition A_{𝔜} := ⋃_{x∈𝔜} A_{x}.

4.4 Proposition.

(i) For x = (α_{ℓ}, β_{ℓ}, r_{ℓ})_{ℓ∈L} ∈ 𝔛^{(L)},

P (F, A_{x}) = ∏_{ℓ∈L} P (F, A_{α_{ℓ},β_{ℓ},r_{ℓ}})

holds.

(ii) For each subset 𝔜 of 𝔛^{(L)}, the limit P (F, A_{𝔜}) exists, and is given as ∑_{x∈𝔜} P (F, A_{x}).

Proof. (i) is a formal consequence of (3.4), (3.5) and (3.15). We omit the details. The proof of (ii) is then identical to that of (4.2). □

As in the case of one single prime, (4.4)(ii) implies that P (F, ·) is a probability measure on A^{(L)}. In view of (4.4)(i) we get:

4.5 Corollary. The σ-algebra 𝔄^{(L)} provided with its probability measure P (F, ·) is canonically isomorphic with the d.p.s. (𝔛^{(L)}, P^{(L)}). In particular, the restrictions of P (F, ·) to the various 𝔄^{(ℓ)} (ℓ ∈ L) are stochastically independent on 𝔄^{(L)}.

4.6 Remark. For a number of reasons, no simple generalizations of (4.4) and (4.5) to infinite subsets L ⊂ ℙ are in sight. For example, the union ⋃_{L_{0}∈L finite} 𝔄^{(L_{0})} is not a σ-algebra, ∏_{ℓ∈L} 𝔛^{(ℓ)} is uncountable, and problems on the convergence of infinite products and their commutation with limits arise. Therefore, events in F that involve an infinite number of primes ℓ are a priori not covered by the above, and are more difficult to study. In (5.9), we investigate a significant instance of such an event, namely the property of cyclicity of E(𝔽_{p}).

5. Some applications.

We use the preceding results to derive probabilities/expectations associated with some elementary properties of E/𝔽_{p} ∈ F.

We start with divisibility by a fixed n ∈ ℕ.

5.1 Proposition. Let a prime power ℓ^{a} and r ∈ ℕ_{0} be given.

(i) The probability that ℓ^{a} divides |E(𝔽_{p})| equals

P (F, “ℓ^{a} | |E(𝔽_{p})|”) = ℓ^{−a} \frac{ℓ^{3} − ℓ − ℓ^{2−a}}{(ℓ^{2} − 1)(ℓ − 1)}.

(ii) The conditional probability for the same event under the assumption ℓ^{r}∥p − 1 equals

\begin{matrix}P (F, “ℓ^{a} | |E(𝔽_{p})|” | “ℓ^{r}∥p − 1”) & = \\ ℓ^{−a} \frac{ℓ}{ℓ−1}, & r < a/2 \\ ℓ^{−a} \frac{ℓ^{2}+ℓ−ℓ^{1−(a−1)/2}}{ℓ^{2}−1} , & r > a/2, a odd \\ ℓ^{−a} \frac{ℓ^{2}+ℓ−ℓ^{1−a/2}}{ℓ^{2}−1} , & r ≥ a/2, a even. \end{matrix}

Proof. By virtue of (4.2), P (F, “ℓ^{a} | |E(𝔽_{p})|”) exists and is given by ∑ g^{(ℓ)}(α, β), where 0 ≤ α ≤ β and α + β ≥ a. The conditional probability in (ii) is given by the same expression, but g^{(ℓ)}(α, β) replaced by g_{r}^{(ℓ)}(α, β).

The stated formulae result from a lengthy but elementary calculation using (2.3) and (2.18), which will be omitted. □

5.2 Corollary. For arbitrary n ∈ ℕ with factorization n = ∏ ℓ^{a_{ℓ}} into primes ℓ, P (F, “n | |E(𝔽_{p})|”) is given by

n^{−1} ∏_{ℓ|n} \frac{ℓ^{3} − ℓ − ℓ^{2−a_{ℓ}}}{(ℓ^{2} − 1)(ℓ − 1)}.

Note that all the probabilities figuring in (5.1) and (5.2) are slightly larger than n^{−1}, the value naively expected. The probability of “n | |E(𝔽_{q})|” over a fixed field 𝔽_{q} (i.e., the share of those E/𝔽_{q} with the divisibility property) has been determined by Howe in [7].

(5.3) For any function f : F ⟶ ℝ, we define the expectation E(F, f) (provided the limit exists) as

E(F, f) = lim_{x→∞} \frac{∑ f(E/𝔽_{p})w(E/𝔽_{p})}{|\{E/𝔽_{p} ∈ F | p ≤ x\}|^{∗}} ,

where the sum in the numerator is over all objects E/𝔽_{p} ∈ F with p ≤ x. Restricting the domain F (for example by requiring congruence conditions on p), we may also define the expectation of f on subsets F′ of F. Given a prime number ℓ, we call f

• of type ℓ, if f(E/𝔽_{p}) depends only on E(𝔽_{p})[ℓ^{∞}];

• weakly of type ℓ, if f(E/𝔽_{p}) depends only on E(𝔽_{p})[ℓ^{∞}] and r(p, ℓ). If these conditions hold, we regard f as a function on the set of groups of shape H_{α,β}^{(ℓ)} (or on the set 𝔛^{(ℓ)}, respectively), see (4.1). More concretely, ℓ being fixed, f is a function on pairs (α, β) with 0 ≤ α ≤ β if it is of type ℓ, and is a function on triples (α, β, r) with 0 ≤ α ≤ min(β, r) if it is weakly of type ℓ.

5.4 Lemma.

(i) Suppose that f is bounded and of type ℓ. Then E(F, f) is defined and agrees with the sum

∑_{{α,β∈ℕ_{0} \atop α≤β}} f(α, β)g^{(ℓ)}(α, β).

(ii) Suppose that f is bounded and weakly of type ℓ, and let r ∈ ℕ_{0} be given. Then the expectation E(F, f, “ℓ^{r}∥p − 1”) of f on {E/𝔽_{p} | ℓ^{r}∥p − 1} is defined and agrees with

∑_{{α,β∈ℕ_{0} \atop α≤min(β,r)}} f(α, β, r)g_{r}^{(ℓ)}(α, β).

Proof. We restrict to showing (i); the proof of (ii) is similar. Let E be the value of the absolutely convergent sum

∑_{0≤α≤β} f(α, β)g^{(ℓ)}(α, β),

and let ϵ > 0 be given. In view of the absolute convergence, there exists a finite subset 𝔜 ⊂ {(α, β) ∈ ℕ_{0} × ℕ_{0} | α ≤ β} such that

∑_{(α,β)∉𝔜} |f(α, β)|g^{(ℓ)}(α, β) < \frac{ϵ}{3}.

Let n = |𝔜| and let x_{0} be chosen sufficiently large such that for each (α, β) ∈ 𝔜 and each x ≥ x_{0}, we have

|f(α, β)| | g^{(ℓ)}(α, β) − \frac{|\{E/𝔽_{p} ∈ F | p ≤ x, E(𝔽_{p})[ℓ^{∞}] ≅ H_{α,β}^{(ℓ)}\}|^{∗}}{|\{E/𝔽_{p} ∈ F | p ≤ x\}|^{∗}} | ≤ ϵ/3n.

Then for x ≥ x_{0},

| ∑_{(α,β)∈𝔜} f(α, β)\frac{|\{E/𝔽_{p} | p ≤ x, E(𝔽_{p})[ℓ^{∞}] ≅ H_{α,β}^{(ℓ)}\}|^{∗}}{|\{E/𝔽_{p} | p ≤ x\}|^{∗}} − E| < 2ϵ/3

holds. According to (4.2), and since f(α, β) is bounded, we find x_{1} such that for x ≥ x_{1}, we have

∑_{(α,β)∉𝔜} |f(α, β)|\frac{|\{E/𝔽_{p} | p ≤ x, E(𝔽_{p})[ℓ^{∞}] ≅ H_{α,β}^{(ℓ)}\}|^{∗}}{|\{E/𝔽_{p} | p ≤ x\}|^{∗}} < ϵ/3.

Thus for x ≥ max(x_{0}, x_{1}),

\frac{∑_{p≤x} f(E/𝔽_{p})w(E/𝔽_{p})}{|\{E/𝔽_{p} | p ≤ x\}|^{∗}}

differs by less than ϵ from E. □

We apply (5.4) to the function κ_{n} : F ⟶ ℝ defined by

(5.5) κ_{n}(E/𝔽_{p}) = number of points of precise order n in E(𝔽_{p}) for n ∈ ℕ.

5.6 Proposition. Let a prime power n = ℓ^{a} and a non-negative integer r be given. The expectation E(F, κ_{n}, “ℓ^{r}∥p − 1”) for κ_{n} on {E/𝔽_{p} | ℓ^{r}∥p−1} exists and equals 1 independently of r. Thus the total expectation E(F, κ_{n}) exists on F and equals 1.

Proof. κ_{n} is bounded by n^{2} = ℓ^{2a} and of type ℓ, thus by (5.4),

E(F, κ_{n}, “ℓ^{r}∥p − 1”) = ∑_{{α,β∈ℕ_{0} \atop α≤min(β,r)}} κ_{n}(α, β)g_{r}^{(ℓ)}(α, β).

Now κ_{n}(α, β) = number of elements of precise order ℓ^{a} in ℤ/ℓ^{α} × ℤ/ℓ^{β} is easily determined; we refrain from writing down the result. Evaluating after that the right hand side above is an elementary but - due to the numerous cases - laborious exercise in summing multiple geometric series. In each of the cases, the result turns out to 1. □

5.7 Corollary. For each natural number n, the expectation E(F, κ_{n}) exists and equals 1.

Proof. Since only the finitely many prime divisors ℓ of n are involved and κ_{n} is multiplicative in n, (4.4) allows to reduce the general case to (5.6). We omit the details. □

5.8 Remark. The just established results on E(F, κ) are “formal facts” that can be seen by “pure thought”, and avoiding the extended calculations with the values of g_{r}^{(ℓ)}(α, β). Namely, taking into account that κ_{n}(E/𝔽_{p}) equals the number of fixed points of Frobenius on the points of precise order n of E(\overline{𝔽}_{p}), (5.7) is almost immediate from (H) and Burnside’s lemma. I owe that hint to Bas Edixhoven [4].

We conclude with determining the asymptotic probability of the property “E(𝔽_{p}) is a cyclic group”. Since it cannot be studied entirely in the framework of the probability spaces 𝔄^{(L)} or 𝔛^{(L)} of section 4 with finite sets of primes, some more preparations are needed. We will finally prove the following.

5.9 Theorem. The probability P (F, “E(𝔽_{p}) is cyclic”) exists and is given by

∏_{ℓ prime}(1 − \frac{1}{(ℓ^{2}−1)ℓ(ℓ−1)}) ≈ 0.81377.

5.10 Remark. Vladut in [10] described the share of the cyclic ones among all the E/𝔽_{q} over the fixed finite field 𝔽_{q}. It depends strongly on the prime decomposition of q − 1. In contrast, (5.9) is an average over all primes p = q, which balances local fluctuations.

We first determine the probability of local cyclicity.

5.11 Lemma. Fix a prime number ℓ and r ≥ 0.

(i) The probability P (F, “E(𝔽_{p})[L^{∞}] is cyclic”) equals

τ_{ℓ} := 1 − \frac{1}{(ℓ^{2}−1)ℓ(ℓ−1)}.

(ii) The conditional probability under the assumption r(p, ℓ) = r for E(𝔽_{p})[ℓ^{∞}] to be cyclic equals 1 if r = 0 and

σ_{ℓ} := 1 − \frac{1}{(ℓ^{2}−1)ℓ}

if r > 0.

Proof. By (4.2), the first value is given by ∑_{β≥0} g^{(ℓ)}(α, β), the second one by

∑_{β≥0} g_{r}^{(ℓ)}(0, β). □

For any λ ∈ ℝ, we call E(𝔽_{p}) λ-cyclic if its ℓ-parts are cyclic for each prime ℓ ≤ λ. From the lemma and (4.4) we get:

5.12 Corollary. P (F, “E(𝔽_{p}) is λ-cyclic”) = ∏_{ℓ≤λ} τ_{ℓ}.

Hence (5.9) is established as soon as we have ensured that the limit for λ ⟶ ∞ commutes with the limit underlying the definition (1.4) of P (F, ·).

Since cyclicity implies λ-cyclicity, at least

lim ; sup_{x→∞} \frac{|\{E/𝔽_{p} ∈ F | p ≤ x, E(𝔽_{p}) cyclic\}|^{∗}}{|\{E/𝔽_{p} ∈ F | p ≤ x\}|^{∗}} ≤ ∏_{ℓ prime} τ_{ℓ}

holds. Thus we must find lower estimates for the left hand side. Put for each prime p

(5.13)  c(p) := ∏_{ℓ|p−1} σ_{ℓ}.

Then it is an easy consequence of (3.4) and the inclusion/exclusion principle (see Theorem 6.1 of [10]) that for each ϵ > 0 and each fixed prime p, we have

|{E/𝔽_{p} | E(𝔽_{p}) cyclic}|^{∗} = 2pc(p) + O_{ϵ}(p^{1/2+ϵ}).

Hence

(5.14) |{E/𝔽_{p} ∈ F | p ≤ x, E(𝔽_{p}) cyclic}|^{∗} = 2 ∑_{p≤x} pc(p) + O_{ϵ}(∑_{p≤x} p^{1/2+ϵ}).

5.15 Lemma. Suppose that the average

C := lim_{x→∞} π(x)^{−1} ∑_{p≤x} c(p)

exists, where π(x) ∼ x/ log x is the prime number function. Then

2 ∑_{p≤x} pc(p) ∼ Cx^{2}/ log x

and therefore P (F, “E(𝔽_{p}) is cyclic”) = C.

Proof. Let (a_{n})_{n∈ℕ} be the series defined by a_{n} = c(p) if n = p ∈ ℙ and a_{n} = 0 otherwise, and A(x) = ∑_{n≤x} a_{n} = ∑_{p≤x} c(p). Abel summation with b(x) = x yields

∑_{p≤x} pc(p) = xA(x) − ∫_{1}^{x} A(s)ds ∼ 1/2 Cx^{2}/ log x,

since by assumption, A(x) ∼ Cx/ log x and any primitive F of x/ log x satisfies F ∼ 1/2 x^{2}/ log x. The last assertion follows from (5.14) and

∑_{p≤x} p^{1/2+ϵ} ∼ \frac{1}{3/2 + ϵ}x^{3/2+ϵ}/ log x.

□

We are left to verifying the hypothesis of (5.15), which no longer involves elliptic curves. Put

(5.16)  \begin{aligned}c_{λ}(p) & = & ∏_{ℓ|p−1, ℓ≤λ} σ_{ℓ} \\ C_{λ}(x) & = & π(x)^{−1} ∑_{p≤x} c_{λ}(p) \\ C(x) & = & π(x)^{−1} ∑_{p≤x} c(p), \end{aligned}

the quantity whose limit we need to find. Now, since c_{λ}(p) depends only on the class of p modulo n := ∏_{ℓ≤λ} ℓ, Dirichlet’s theorem implies that for λ fixed,

(5.17)

C_{λ} := lim_{x→∞} C_{λ}(x) = average of c_{λ} over (ℤ/n)^{∗}
= ∏_{ℓ≤λ} (average of σ̃_{ℓ} over (ℤ/ℓ)^{∗}) = ∏_{ℓ≤λ} τ_{ℓ}.

Here σ̃_{ℓ}(x) = σ_{ℓ}, (σ̃_{ℓ}(x) = 1) if x ≡ 1, (x ≢ 1) modulo ℓ, respectively (see Lemma 5.11(ii)).

In view of c(p) ≤ c_{λ}(p), we have for each λ

lim ; sup_{x→∞}C(x) ≤ C_{λ},

hence

lim sup C(x) ≤ ∏_{ℓ prime} τ_{ℓ}.

5.18 Claim. We have in fact

C := lim_{x→∞} C(x) = ∏_{ℓ prime} τ_{ℓ}.

Proof of claim. Let λ_{0} ∈ ℝ and ϵ > 0 be given. Choose x_{0} large enough such that for x ≥ x_{0}

|C_{λ_{0}}(x) − C_{λ_{0}}| < ϵ

holds. For such x and λ ≥ λ_{0}, we have

C_{λ}(x) ≥ ( ∏_{λ_{0}<ℓ≤λ} σ_{ℓ})C_{λ_{0}}(x) > ( ∏_{λ_{0}<ℓ≤λ} σ_{ℓ})(C_{λ_{0}} − ϵ).

Letting λ ⟶ ∞, we find

C(x) ≥ ( ∏_{ℓ>λ_{0}} σ_{ℓ})(C_{λ_{0}} − ϵ)

for each x ≥ x_{0}, and therefore

lim ; inf_{x→∞}C(x) ≥ ( ∏_{ℓ>λ_{0}} σ_{ℓ})C_{λ_{0}} = ∏_{ℓ≤λ_{0}} τ_{ℓ} ∏_{ℓ>λ_{0}} σ_{ℓ}.

Since this holds for any λ_{0}, and σ_{ℓ} ≤ τ_{ℓ} for each ℓ, we finally get

lim ; inf_{x→∞}C(x) ≥ ∏_{ℓ prime} τ_{ℓ},

i.e., the claim. Together with (5.15), this also concludes the proof of Theorem 5.9. □

References

[1] J.D. Achter: The distribution of class groups of function fields. J. Pure and Appl. Algebra 204 (2006), 316–333.

[2] B.J. Birch: How the number of points of an elliptic curve over a fixed prime field varies. J. London Math. Soc. 43 (1968), 57–60.

[3] H. Cohen–H.W. Lenstra, Jr.: Heuristics on class groups of number fields. In: Lecture Notes in Mathematics 1068, 33–62, Springer–Verlag 1984.

[4] B. Edixhoven: personal communication.

[5] E. Friedman–L.C. Washington: On the distribution of divisor class groups of curves over a finite field. In: Théorie des Nombres/Number Theory Laval 1987 (J.-M. De Koninck–C. Levesque eds.), De Gruyter 1989.

[6] E.-U. Gekeler: Frobenius distributions of elliptic curves over finite prime fields. Int. Math. Res. Notices 37 (2003), 1999–2018.

[7] E.W. Howe: On the group orders of elliptic curves over finite fields. Comp. Math. 85 (1993), 229–247.

[8] J-P. Serre: Zeta and L functions. Arithmetical Algebraic Geometry, 82–92, Harper and Row 1965.

[9] G. Tenenbaum: Introduction à la théorie analytique et probabiliste des nombres. Soc. Math. France 1995.

[10] S.G. Vladut: Cyclicity statistics for elliptic curves over finite fields. Finite Fields Appl. 5 (1999), 13–25.

Ernst-Ulrich Gekeler FR 6.1 Mathematik Universität des Saarlandes D-66041 Saarbrücken Germany gekeler@math.uni-sb.de