The asymptotic distribution of Elkies primes for reductions of abelian varieties is Gaussian

Basic Information

• Paper ID: 2411.18171
• Title: The asymptotic distribution of Elkies primes for reductions of abelian varieties is Gaussian
• Authors: Alexandre Benoist, Jean Kieffer
• Classification: math.NT (Number Theory)
• Publication Date: November 26, 2024 (arXiv v2: November 25, 2025)
• Paper Link: https://arxiv.org/abs/2411.18171

Abstract

This paper generalizes the concept of Elkies primes for elliptic curves to abelian varieties with real multiplication (RM), and proves that: for an abelian variety $A$ with RM over a number field whose Galois representation has large image, the count of Elkies primes (within an appropriate range) for $A$ reduced modulo prime ideals weakly converges to a Gaussian distribution centered around the expected value. This result refines and generalizes the work of Shparlinski and Sutherland for non-CM elliptic curves, and has important implications for analyzing the complexity of the SEA point-counting algorithm for abelian surfaces over finite fields.

Research Background and Motivation

1. Problem Background

The SEA Algorithm and Elkies Primes: The Schoof-Elkies-Atkin (SEA) algorithm is an efficient algorithm for computing the number of points $\#E(\mathbb{F}_q)$ on an elliptic curve $E$ over a finite field $\mathbb{F}_q$. For a prime $\ell$, if there exists an $\ell$-isogeny defined over $\mathbb{F}_q$, then $\ell$ is called an Elkies prime for $E$. The SEA algorithm is more efficient when there are sufficiently many small Elkies primes, since the Elkies method can be applied to determine $\#E(\mathbb{F}_q) \bmod \ell$.

Prior Work:

• Shparlinski and Sutherland proved that on average there are sufficiently many Elkies primes, considering either all elliptic curves over a fixed $\mathbb{F}_q$ or reductions of a fixed non-CM elliptic curve modulo primes
• Quantitative results for higher-dimensional cases (abelian varieties) are lacking

2. Research Significance

• Algorithm Complexity Analysis: Understanding the distribution of Elkies primes is crucial for evaluating the overall complexity of the SEA algorithm
• Theoretical Significance: Reveals deep connections between Galois representations and isogeny structures
• Generalization Value: Extends from elliptic curves (dimension 1) to abelian varieties of arbitrary dimension

3. Limitations of Existing Methods

• Shparlinski-Sutherland results only provide bounds on moments, not a complete characterization of the distribution
• Only consider elliptic curves ($g=1$), not higher-dimensional cases
• Do not account for real multiplication structure

4. Research Motivation

Through numerical experiments (Section 5), the authors observed that the distribution of Elkies primes exhibits a very smooth Gaussian form, which motivated them to attempt a theoretical proof of Gaussian convergence (Theorem 1.1).

Core Contributions

1. Concept Generalization: Extends the definition of Elkies primes from elliptic curves to abelian varieties with real multiplication, defined as primes for which there exists a $\mathbb{F}_q$-rational maximal isotropic subgroup stable under the RM structure
2. Main Theorem (Theorem 1.1): Under GRH, proves that the normalized Elkies prime counting function $X_{P,L}(p) = \frac{N_e(p,L) - \alpha_h \#\mathcal{P}_K(L,2L)}{\sqrt{\alpha_h(1-\alpha_h)\#\mathcal{P}_K(L,2L)}}$ weakly converges to the standard Gaussian distribution, where $\alpha_h$ is a theoretical probability constant
3. Exact Asymptotics of Moments (Theorem 1.2): Provides exact asymptotic formulas for all moments $E(X^k_{P,L})$, with error terms explicitly depending on $L,P$
4. Counting Formula (Proposition 3.7): Determines the exact asymptotic size of the set of split matrices $S_{2h,\mathbb{F}_q}(\lambda_0)$ in the symplectic group $\mathrm{GSp}_{2h}(\mathbb{F}_q)$: $\#S_{2h,\mathbb{F}_q}(\lambda_0) = \alpha_h q^{f(h)-1} + O_h(q^{f(h)-2})$ where $f(h) = 2h^2+h+1$
5. Application Value: First quantitative result showing that on average there are sufficiently many Elkies primes for the SEA algorithm in higher dimensions (particularly dimension 2)

Detailed Methodology

Task Definition

Input:

• A polarized abelian variety $A$ of dimension $g$ over a number field $F$, with real multiplication by an order $O$ in the ring of integers of a totally real field $K$ (of degree $d$)
• Parameters $P, L \in \mathbb{R}^+$, where $P \gg L^n$ for all positive integers $n$

Output:

• A distribution function $X_{P,L}$ on the set of prime ideals $\mathcal{P}_F(P,2P)$, characterizing the count of Elkies primes for each reduction $A_p$

Constraints:

• Large Galois image assumption: there exists sufficiently large $n$ such that $\hat{\rho}_n(G_F) \supseteq \mathrm{Sp}_{2h}(O \otimes \hat{\mathbb{Z}}_{\geq n})$
• GRH (Generalized Riemann Hypothesis)

Method Architecture

Step 1: Galois Representation Characterization (Section 2)

For a prime ideal $\mathfrak{l}$ and prime $p$, the Elkies property is characterized through the following equivalence:

Lemma 2.5: $\mathfrak{l}$ is an Elkies prime for $A_p$ if and only if there exists a maximal isotropic subspace of $A[\mathfrak{l}]$ as an $(O/\mathfrak{l}O)$-vector space that is $\mathbb{F}_p$-rational

Proposition 2.10: $\mathfrak{l}$ is an Elkies prime for $A_p$ if and only if the image of the Frobenius element $\sigma_p$ under the Galois representation $\rho_{\mathfrak{l}}$ belongs to the set of split matrices: $\rho_{\mathfrak{l}}(\sigma_p) \in S_{2h,O/\mathfrak{l}O}(N_{F/\mathbb{Q}}(p))$

This transforms the number-theoretic problem into a matrix counting problem in the symplectic group.

Step 2: Counting in the Symplectic Group (Section 3)

Key Definition 2.8: A matrix $m \in \mathrm{GSp}_{2h}(k)$ is called split if it stabilizes some maximal isotropic subspace of $k^{2h}$

Lemma 3.1: $m$ is split if and only if $m$ is conjugate to a block upper triangular matrix $\begin{pmatrix} w & \star \\ 0 & \lambda(m)w^{-\top} \end{pmatrix}$

Propositions 3.3-3.5: Establish the relationship between splitness and characteristic polynomials:

• $m$ split $\Rightarrow$ $\chi_m = P\tilde{P}^{\lambda_0}$ (a certain dual form)
• When $\chi_m$ is squarefree, the converse also holds (Proposition 3.4)
• In general, the converse also holds (Proposition 3.5, using Jordan decomposition and induction)

Counting Core (Proposition 3.7): Computes $\#S_{2h,\mathbb{F}_q}(\lambda_0)$ through the following steps:

1. Decompose $S_{2h,\mathbb{F}_q}(\lambda_0) = S^{\text{sqf}}_{2h,\mathbb{F}_q}(\lambda_0) \sqcup S^{\text{nsqf}}_{2h,\mathbb{F}_q}(\lambda_0)$ (squarefree and non-squarefree)
2. The non-squarefree part contributes $O_h(q^{f(h)-2})$ (Lemma 3.8, using Lang-Weil theorem)
3. Squarefree part:
   • Classify by characteristic polynomial decomposition $P_1 \cdots P_r \cdot \tilde{P}_1^{\lambda_0} \cdots \tilde{P}_r^{\lambda_0}$ (where $\deg P_i = d_i$ and $(d_1,\ldots,d_r)$ is a partition of $h$)
   • Each conjugacy class has size $\frac{\#\mathrm{GSp}_{2h}(\mathbb{F}_q)}{(q-1)\prod_i(q^{d_i}-1)}$ (Lemma 3.10)
   • Count conjugacy classes through combinatorics of irreducible polynomials
   • Summation yields the main term $\alpha_h q^{f(h)-1}$

Step 3: Application of Čebotarev Density Theorem (Section 4)

Moment Expression: $E(X^k_{P,L}) = \frac{1}{\#\mathcal{P}_F(P,2P) \cdot \sigma^k} \sum_{p \in \mathcal{P}_F(P,2P)} \sum_{\mathfrak{l}_1,\ldots,\mathfrak{l}_k \in \mathcal{P}_K(L,2L)} \delta_{p,\mathfrak{l}_1 \cdots \mathfrak{l}_k}$

where $\delta_{p,L} = (1-\alpha_h)$ if $L$ is Elkies, otherwise $-\alpha_h$

Key Decomposition: Classify the summation by the form of $\mathfrak{l}_1 \cdots \mathfrak{l}_k$ as $a^2 b$ (where $b$ is squarefree with $j$ distinct prime factors), defining $Q_{k,j}$

Small Term Estimate (Proposition 4.1): For $L = \mathfrak{l}_1 \cdots \mathfrak{l}_r$ (product of distinct primes): $\sum_{p \in \mathcal{P}_F(P,2P)} \delta_{p,L} = O_{A,r}\left(\frac{P}{\log(P)L^r} + L^{f(h)r}P^{1/2}\log(P)\right)$

The proof uses the effective Čebotarev density theorem (Serre, depending on GRH), counting Frobenius elements falling in specific conjugacy classes in the extension field $F(A[L])/F$

Main Term Estimate (Proposition 4.4): For $(l_1,\ldots,l_{2\nu}) \in Q'_{2\nu,0}$ (where $2\nu$ primes consist of exactly $\nu$ distinct primes each appearing twice): $\sum_{p} \delta_{p,l_1 \cdots l_{2\nu}} = (\alpha_h(1-\alpha_h))^\nu \frac{P}{\log(P)} + O_{A,\nu}\left(\frac{P}{\log(P)L} + L^{f(h)\nu}P^{1/2}\log(P)\right)$

Combinatorial Argument (Lemma 4.3): $\#Q'_{2\nu,0} = M_{2\nu} \frac{L^\nu}{\log(L)^\nu} + O_\nu\left(\frac{L^{\nu-1}}{\log(L)^{\nu-1}}\right)$ where $M_{2\nu} = (2\nu-1)!! = (2\nu-1)(2\nu-3)\cdots 3 \cdot 1$ is the $2\nu$-th moment of the standard Gaussian distribution

Step 4: Asymptotic Analysis (Section 4.4)

Odd Moments ($k=2\nu+1$): All terms are small terms, yielding $E(X^k_{P,L}) = O_{A,k}\left(\frac{1}{L^{1/2}\log(L)^{1/2}} + \frac{L^{k(2h^2+h+3/2)}\log(P)^2}{\log(L)^{k/2}P^{1/2}}\right) \to 0$

Even Moments ($k=2\nu$): Main term comes from $Q'_{2\nu,0}$: $E(X^k_{P,L}) = M_{2\nu} + O_{A,k}\left(\frac{1}{L^{1/2}\log(L)^{1/2}} + \frac{L^{k(2h^2+h+3/2)}\log(P)^2}{\log(L)^{k/2}P^{1/2}}\right)$

By the method of moments (Billingsley Theorem 30.2), convergence of all moments to Gaussian moments implies weak convergence.

Technical Innovations

1. Complete Solution to Symplectic Group Counting: First exact asymptotic count of split matrices in $\mathrm{GSp}_{2h}(\mathbb{F}_q)$, handling the difficult case where the characteristic polynomial has repeated factors (complete proof of Proposition 3.5)
2. Treatment of RM Structure: Through the $O$-linear Weil pairing form $\psi_\ell$ (Lemma 2.1), reduces the problem to the standard symplectic group, cleverly exploiting the decomposition $O/\ell O = \prod_{\mathfrak{l}|\ell} O/\mathfrak{l}O$
3. Precise Control of Moments: Not only proves convergence but provides explicit error terms, which is more refined than the upper bounds of Shparlinski-Sutherland
4. Application of Large Galois Image: Systematically uses Serre's open image theorem and its RM generalization (Theorem 2.13), ensuring the Galois group contains the full symplectic group, enabling effective application of Čebotarev's theorem

Experimental Setup

Dataset

The authors use SageMath for numerical experiments, selecting the non-CM elliptic curve with Cremona label 11a3: $E: y^2 + y = x^3 - x^2 \quad \text{defined over} \quad \mathbb{Q}$

Parameter Ranges:

• $L \in \{25, 100, 250\}$ (fixed ranges) or $L \in [20, 500]$ (varying range)
• $P \in [10^3, 5 \times 10^6]$ or fixed $P = 10^5, 10^7$

Evaluation Metrics

1. Second Moment: $\frac{1}{\pi(2P)-\pi(P)} \sum_{p \in \mathcal{P}_{\mathbb{Q}}(P,2P)} \left(N_e(p,L) - \frac{\pi(2L)-\pi(L)}{2}\right)^2$
2. Distribution Histogram: Frequency distribution of $N_e(p,L)$ over $n \in [0, \pi(2L)-\pi(L)+1]$
3. Comparison with Naive Model: Moments of binomial distribution $B(\pi(2L)-\pi(L), 1/2)$ with moment $\frac{\pi(2L)-\pi(L)}{4}$

Implementation Details

• SageMath 10.3
• Code is open-source in the arXiv source files
• For each $(P,L)$ pair, iterate over all primes $p \in (P, 2P]$ and $\ell \in (L, 2L]$, checking whether $\ell$ is an Elkies prime for $E_p$ (by testing whether $t^2-4q$ is a quadratic residue modulo $\ell$, where $t$ is the Frobenius trace)

Experimental Results

Main Results

Figure 1 (Second Moment vs. $P$):

• Fix $L \in \{25, 100, 250\}$, $P$ grows from $10^3$ to $5 \times 10^6$
• Observe rapid convergence of second moment to a finite limit depending on $L$
• Convergence rate slightly slows as $L$ increases, consistent with theoretical prediction of $O(L^{-1/2})$ error term

Figure 2 (Distribution Shape):

• Histogram of $N_e(p,L)$ distribution (blue) vs. theoretical Gaussian curve (red) for $L=250, P=10^7$
• High agreement between the two, confirming the Gaussian distribution hypothesis
• Expected value $\mu = \frac{\pi(2L)-\pi(L)}{2} \approx 27$, standard deviation $\sigma \approx 5.2$

Figure 3 (Model Verification):

• Fix $P=10^5$, $L$ varies from 20 to 500
• Actual second moment (blue line) vs. naive model prediction $\frac{\pi(2L)-\pi(L)}{4}$ (red line)
• Good agreement when $L \ll \sqrt{P}$
• Deviation appears when $L > \sqrt{P}$, consistent with theoretical requirement $P \gg L^n$

Experimental Findings

1. Intuitive Evidence for Gaussianity: The "very smooth" nature of the distribution was the key observation motivating the authors to pursue theoretical proof
2. Validity of Naive Model: The independence assumption (each $\ell$ has 50% probability of being Elkies) gives correct main term when $P \gg L$, validating the theoretical value $\alpha_1 = 1/2$
3. Criticality of Parameter Range: $L \sim \sqrt{P}$ is the critical point where theory and experiment begin to diverge, consistent with the condition $P \gg L^n$ in Theorem 1.2
4. Convergence Rate: Numerical experiments show convergence faster than the theoretical error term $O(L^{-1/2}\log(L)^{-1/2})$, suggesting the actual error may have a better bound

Related Work

Main Research Directions

1. Elkies Primes for Elliptic Curves:
   • Schoof (1995): Original SEA algorithm work
   • Shparlinski-Sutherland (2014, 2015): Average results for all curves over fixed $\mathbb{F}_q$; moment bounds for fixed non-CM curves modulo primes
   • Shparlinski (2015): Study of products of small Elkies primes
2. Large Image of Galois Representations:
   • Serre (1985-86): Open image theorem for elliptic curves
   • Ribet (1976): Galois action on abelian varieties with real multiplication
   • Chi (1992): $\ell$-adic and $\lambda$-adic representations
   • Banaszak-Gajda-Krasoń (2006): Image for type I and II abelian varieties
3. Point Counting Algorithms:
   • Kieffer (2022): SEA algorithm on abelian surfaces
   • Brooks-Jetchev-Wesolowski (2017): Isogeny graphs for ordinary abelian varieties

Advantages of This Work Over Related Work

1. Dimensional Generalization: Extends from $g=1$ (elliptic curves) to abelian varieties of arbitrary dimension $g$
2. Structural Generalization: Handles real multiplication structure (RM), covering a broader class of abelian varieties
3. Result Refinement:
   • Shparlinski-Sutherland only provide moment bounds; this work gives exact asymptotics
   • Proves complete distribution convergence (weak convergence), not just moment estimates
4. Theoretical Deepening:
   • Completely solves the counting problem for split matrices in symplectic groups (including non-squarefree case)
   • Establishes equivalence between characteristic polynomials and splitness (Proposition 3.5)
5. Algorithm Application: First quantitative results on average complexity of higher-dimensional SEA algorithm

Conclusions and Discussion

Main Conclusions

1. Theorem 1.1 (Main Theorem): Under GRH and large Galois image assumption, the normalized Elkies prime count $X_{P,L}$ weakly converges to $\mathcal{N}(0,1)$
2. Theorem 1.2 (Moment Formula): All moments $E(X^k_{P,L})$ converge to Gaussian moments $M_k$, with error $O_{A,k}\left(\frac{1}{L^{1/2}\log(L)^{1/2}} + \frac{L^{k(2h^2+h+3/2)}\log(P)^2}{\log(L)^{k/2}P^{1/2}}\right)$
3. Algorithm Significance: On average, there are sufficiently many Elkies primes to run the SEA algorithm (satisfying Kieffer 2022's Definition 3.7)
4. Probabilistic Interpretation: $\alpha_h$ is the theoretical probability that $\mathfrak{l}$ is an Elkies prime for $A_p$ (specific values given in Table 1)

Limitations

1. Dependence on GRH: All quantitative results depend on the Generalized Riemann Hypothesis; unconditional proof remains open
2. Large Galois Image Assumption:
   • Requires $\mathrm{End}_{\mathbb{Q}}(A) = O$ (Proposition 2.12)
   • Only has sufficient conditions when $d=1$ and $g \in \{2,6\}$ or $h=g/d$ is odd (Theorem 2.13)
   • Verification of this assumption may be difficult in general cases
3. Parameter Range Restriction: Requires $P \gg L^n$ for all $n$, meaning $P$ must be much larger than any polynomial in $L$
4. Fixed Reduction Case Unresolved: The distribution for all abelian varieties over a fixed $\mathbb{F}_q$ (analogous to Shparlinski-Sutherland 2014) remains unresolved, as it requires controlling the class number
5. Real Multiplication Restriction: Does not address complex multiplication (CM) or general abelian varieties without additional structure

Future Directions

1. Removing GRH: Seek unconditional proofs or weaker assumptions
2. Extension to CM Case: Study Elkies prime distribution for complex multiplication abelian varieties
3. Fixed Finite Field Case:
   • Control class number in Frobenius trace distribution
   • May require new analytic number theory techniques
4. Higher-Order Error Terms: Improve error estimates in Theorem 1.2; numerical experiments suggest faster actual convergence
5. Non-Main Term Analysis: Study contribution of $Q_{k,j}$ ($j>0$), possibly revealing finer structure
6. Algorithm Implementation:
   • Apply theoretical results to practical SEA algorithm implementation
   • Optimize higher-dimensional point counting algorithms

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Skillfully combines algebraic geometry (abelian varieties, isogenies), number theory (Galois representations, Čebotarev theorem), and combinatorics (matrix counting)
   • Proof of Proposition 3.5 (complete equivalence between characteristic polynomials and splitness) is technically strong, filling a gap in the literature
2. Result Completeness:
   • Not only proves convergence but provides explicit error terms and formulas for all moments
   • Exact asymptotics in Proposition 3.7 (main term + secondary term) provide solid foundation for subsequent applications
3. Generalization Value:
   • Natural generalization from elliptic curves to arbitrary-dimensional abelian varieties
   • Framework applicable to other isogeny problems
4. Experimental Verification:
   • Section 5 numerical experiments intuitively demonstrate theoretical predictions
   • Clear figures verify theory for $h=1$ case
5. Writing Quality:
   • Clear structure: Section 2 reviews background, Section 3 counts, Section 4 proves main theorem
   • Symbol table (Table 2) convenient for readers
   • Clear hierarchy of lemmas-propositions-theorems

Weaknesses

1. Strong Technical Assumptions:
   • GRH dependence limits unconditional validity of results
   • Verification of large Galois image is difficult in general (Theorem 2.13 only covers partial cases)
2. Missing High-Dimensional Numerical Experiments:
   • Section 5 only verifies $g=1$ (elliptic curve) case
   • Lacks numerical evidence for $g=2$ (abelian surfaces), which is crucial for algorithm applications
3. Error Terms May Not Be Tight:
   • Numerical experiments suggest actual convergence is faster than theoretical error $O(L^{-1/2})$
   • Room for improvement may exist
4. Fixed Field Case Unaddressed:
   • Problem raised but unresolved (end of Introduction Section 1.2)
   • Lacks preliminary results or discussion in this direction
5. Dependence on Symplectic Group Counting:
   • Proof of Proposition 3.7 depends on Gauss irreducible polynomial counting formula and Lang-Weil theorem
   • May have some threshold for non-specialist readers

Impact

1. Contribution to Field:
   • Theoretical: First exact distribution theory for Elkies primes in higher dimensions, filling important gap
   • Algorithmic: Provides theoretical foundation for complexity analysis of higher-dimensional SEA algorithm
   • Methodological: Symplectic group matrix counting techniques may apply to other problems (e.g., distribution of Atkin primes)
2. Practical Value:
   • Guides parameter selection in abelian surface cryptography
   • Evaluates expected running time of point counting algorithms
3. Reproducibility:
   • Code open-sourced (arXiv source files)
   • Numerical experiment parameters explicit, easy to reproduce
   • Theoretical proofs detailed, key lemmas fully argued
4. Follow-up Research:
   • Proposition 3.5 may inspire characterization of other symplectic group subsets
   • Method framework generalizable to other isogeny types (Atkin primes, Volcanos)

Applicable Scenarios

1. Cryptography:
   • Parameter generation for abelian variety-based cryptosystems
   • Evaluate point counting algorithm efficiency for specific parameters
2. Computational Number Theory:
   • Complexity prediction when implementing higher-dimensional SEA algorithm
   • Optimize isogeny computation strategies
3. Theoretical Research:
   • Tool for studying relationships between Galois representations and isogenies
   • Generalization to other algebraic varieties (e.g., K3 surfaces)
4. Teaching:
   • Exemplary case of intersection of algebraic geometry, number theory, and probability theory
   • Concrete application of symplectic group representation theory

References

Key references include:

1. Serre (1985-86, 1981): Open image theorem for elliptic curves and applications of Čebotarev density theorem
2. Shparlinski-Sutherland (2014, 2015): Prior work on Elkies prime distribution for elliptic curves
3. Kieffer (2022): SEA algorithm for abelian surfaces, direct application of this paper's results
4. Chi (1992), Banaszak-Gajda-Krasoń (2006): Large image theorems for Galois representations of RM abelian varieties
5. Lang-Weil (1954): Point count estimates for algebraic varieties over finite fields
6. Billingsley (1995): Theoretical foundation of method of moments and weak convergence

Summary: This paper represents important progress in isogeny theory for abelian varieties. Through elegant symplectic group counting and Galois representation analysis, it establishes for the first time a Gaussian distribution law for Elkies primes in higher dimensions. Although depending on GRH and the large Galois image assumption, the theoretical framework is complete and proofs are rigorous, with important value for algorithm complexity analysis and cryptographic applications. Numerical experiments strongly support theoretical results, demonstrating the authors' deep understanding of the problem.