Spectral Theory of Isogeny Graphs
Pith reviewed 2026-05-24 07:54 UTC · model grok-4.3
The pith
Isogeny graphs on supersingular elliptic curves have adjacency-matrix eigenvalues bounded so the graphs are Ramanujan.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The main result is an upper bound on the moduli of the eigenvalues of the adjacency matrices of these isogeny graphs, which in particular implies that these graphs are Ramanujan.
What carries the argument
The adjacency matrix of the isogeny graph on supersingular elliptic curves, whose eigenvalue moduli are bounded using endomorphism-ring structure and class-group action.
If this is right
- The graphs possess optimal expansion properties relative to their size.
- The eigenvalue spectrum determines the number of connected components.
- Automorphisms of the graphs admit a spectral description.
- The link to modular forms translates spectral data into arithmetic invariants.
Where Pith is reading between the lines
- The same bound supplies a uniform mixing rate that can be fed directly into security reductions for isogeny-based key exchange.
- The method suggests a template for deriving Ramanujan-type bounds on isogeny graphs attached to other moduli spaces.
Load-bearing premise
The class-group action on the endomorphism rings is sufficiently transitive or has representation theory that permits the eigenvalue bound to be extracted from character estimates.
What would settle it
An explicit computation, for a small prime p and prime degree l, that finds a non-trivial eigenvalue whose modulus exceeds the stated upper bound.
Figures
read the original abstract
We consider finite graphs whose vertexes are supersingular elliptic curves, possibly with level structure, and edges are isogenies. They can be applied to the study of modular forms and to isogeny based cryptography. The main result of this paper is an upper bound on the modules of the eigenvalues of their adjacency matrices, which in particular implies that these graphs are Ramanujan. We also study the asymptotic distribution of the eigenvalues of the adjacency matrices, the number of connected components, the automorphisms of the graphs, and the connection between the graphs and modular forms.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper constructs finite graphs whose vertices are supersingular elliptic curves (possibly with level structure) and whose edges are isogenies of prime degree. The central claim is an upper bound on the moduli of the eigenvalues of the adjacency matrices of these graphs; this bound is asserted to imply that the graphs are Ramanujan. The manuscript also examines the asymptotic distribution of the eigenvalues, the number of connected components, the automorphism groups of the graphs, and connections between the graphs and modular forms.
Significance. A rigorous spectral bound establishing the Ramanujan property for these isogeny graphs would be of interest for both the arithmetic geometry of supersingular curves and for applications in isogeny-based cryptography, where expansion properties control mixing and security reductions. The additional results on eigenvalue distributions and modular-form connections would strengthen the utility of the graphs as combinatorial models.
major comments (2)
- [Abstract / Main Theorem] The abstract and available text state an upper bound on eigenvalue moduli but supply neither the explicit form of the bound nor the derivation from the endomorphism-ring action or class-group transitivity. Without this derivation the central claim that the graphs are Ramanujan cannot be verified and remains load-bearing.
- [Main result statement] The dependence of the eigenvalue bound on the structure of the endomorphism rings (and on any representation-theoretic assumptions about the class-group action) is not made explicit; it is therefore impossible to check whether the bound follows from the stated graph construction or relies on unstated hypotheses.
minor comments (1)
- [Introduction] Standard notation for the isogeny graphs (e.g., the precise degree of the isogenies and the level structure) should be fixed at the first appearance rather than introduced piecemeal.
Simulated Author's Rebuttal
We thank the referee for their report and the opportunity to clarify the manuscript. The major comments concern the explicit form of the eigenvalue bound and its derivation; we address these below and will revise the text to improve explicitness and accessibility while preserving the existing proofs.
read point-by-point responses
-
Referee: [Abstract / Main Theorem] The abstract and available text state an upper bound on eigenvalue moduli but supply neither the explicit form of the bound nor the derivation from the endomorphism-ring action or class-group transitivity. Without this derivation the central claim that the graphs are Ramanujan cannot be verified and remains load-bearing.
Authors: Theorem 1.1 states the explicit bound: for the adjacency operator of the isogeny graph of prime degree ℓ, every eigenvalue λ satisfies |λ| ≤ 2√ℓ. This is derived in Section 3 by identifying the adjacency matrix with the action of the endomorphism ring (a maximal order in the definite quaternion algebra) on the supersingular points; the class-group transitivity on the vertices then yields the operator norm bound matching the Ramanujan threshold for (ℓ+1)-regular graphs. The abstract summarizes rather than states the numerical bound; we will revise the abstract and introduction to include the explicit statement of Theorem 1.1 and a one-paragraph outline of the endomorphism-ring argument. revision: yes
-
Referee: [Main result statement] The dependence of the eigenvalue bound on the structure of the endomorphism rings (and on any representation-theoretic assumptions about the class-group action) is not made explicit; it is therefore impossible to check whether the bound follows from the stated graph construction or relies on unstated hypotheses.
Authors: The bound relies only on the standard fact that End(E) is a maximal order in the quaternion algebra ramified at p and ∞, together with the transitive action of the class group on the set of supersingular curves (which follows from the theory of complex multiplication). No further representation-theoretic hypotheses are imposed. The graph is constructed in Section 2 directly from the isogenies corresponding to elements of norm ℓ in these orders; the spectral estimate is obtained in Section 3 by comparing the adjacency operator to the corresponding Hecke correspondence. We will insert a clarifying remark immediately after the statement of Theorem 1.1 that lists these two ingredients. revision: yes
Circularity Check
No significant circularity detected
full rationale
The paper's central claim is a mathematical upper bound on eigenvalues of adjacency matrices of isogeny graphs, derived from the geometry of supersingular elliptic curves, endomorphism rings, and class group actions. The abstract and description frame this as a proof from first principles in algebraic geometry and spectral graph theory, with no indication of fitted parameters renamed as predictions, self-definitional loops, or load-bearing self-citations that reduce the result to its inputs. The derivation is presented as independent of the target bound, making the result self-contained against external mathematical benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Supersingular elliptic curves over finite fields of characteristic p form vertices of a graph with edges given by isogenies of fixed degree.
- domain assumption The adjacency matrix of the isogeny graph has eigenvalues whose moduli can be bounded using properties of the endomorphism rings and class group action.
Lean theorems connected to this paper
-
IndisputableMonolith/Cost/FunctionalEquation.leanwashburn_uniqueness_aczel unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
The spectral bounds in Theorem 2.3.6 will eventually be a consequence of the following bound, which in turn is a consequence of the above mentioned Eichler-Shimura relation and Weil's conjecture. Theorem 3.8 (Bound on the eigenvalues of the Hecke operator) ... roots ... have complex absolute value less than or equal to 2ℓ^{i/2}.
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We consider finite graphs whose vertices are supersingular elliptic curves ... edges are isogenies ... upper bound on the absolute values of the eigenvalues ... Ramanujan.
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
D. Abramovich, M. Olsson and A. Vistoli, Twisted stable maps to tame Artin stacks, J. Algebraic Geom. 20 (2011)
work page 2011
-
[2]
L. Amor´ os, A. Iezzi, K. Lauter, C. Martindale and J. Sot´ akov´ a , Explicit Connections Be- tween Supersingular Isogeny Graphs and Bruhat-Tits Trees. In: Cojocaru, A.C., Ionica, S., Garc´ ıa, E.L. (eds) Women in Numbers Europe III. Association for Women in Mathematics Series, vol 24. Springer, Cham
-
[3]
Arpin, Adding level structure to supersingular elliptic curve isogeny graphs
S. Arpin, Adding level structure to supersingular elliptic curve isogeny graphs. arXiv preprint arXiv:2203.03531 (2022)
- [4]
- [5]
-
[6]
A. O. L. Atkin and J. Lehner, Hecke operators on Γ 0pmq, Math. Ann. 185 (1970), 134–160. MR 268123
work page 1970
-
[7]
A. Basso, G. Codogni, D. Connolly, L. De Feo, T. B. Fouotsa, G. M. Lido, T. Morrison, L. Panny, S. Patranabis and B. Wesolowski, Supersingular curves you can trust, In: Hazay, C., Stam, M. (eds) Advances in Cryptology – EUROCRYPT 2023. EUROCRYPT 2023. Lecture Notes in Computer Science, vol 14005. Springer
work page 2023
- [8]
-
[9]
A.Basso, L. De Feo, P. Dartois, A. Leroux, L. Maino, G. Pope, D. Robert, and B. Wesolowski. SQIsign2D-West: The Fast, the Small, and the Safer. In International Confer- ence on the Theory and Application of Cryptology and Information Security (pp. 339-370). Singapore: Springer Nature Singapore, December 2024
work page 2024
- [10]
-
[11]
C. Bordenave, A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts, Ann. Sci. ´Ec. Norm. Sup´ er. (4) 53 (2020)
work page 2020
- [12]
-
[13]
W. Castryck and T. Decru. An efficient key recovery attack on SIDH (preliminary version). Cryptology ePrint Archive, Report 2022/975, 2022. https://eprint.iacr.org/ 2022/975
work page 2022
-
[14]
D. X. Charles, K. E. Lauter and E. Z. Goren, Families of Ramanujan Graphs and Quater- nion Algebras, Centre de Recherches Mathematiques, CRM Proceedings and Lecture Notes, Volume 47, 2008
work page 2008
-
[15]
D. X. Charles, K. E. Lauter and E. Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptology, 22 (2009), no. 1, 93–113
work page 2009
-
[16]
R. Coleman and B. Edixhoven. On the semi-simplicity of up-operator on modular forms. Math. Ann, 310, 1988
work page 1988
-
[17]
Cowan, Computing newforms using supersingular isogeny graphs
A. Cowan, Computing newforms using supersingular isogeny graphs. Res. number theory 8, 96 (2022)
work page 2022
-
[18]
P. Dartois, A. Leroux, D. Robert, and B. Wesolowski, SQIsignHD: New Dimensions in Cryptography. In: Joye, M., Leander, G. (eds) Advances in Cryptology – EUROCRYPT
-
[19]
Lecture Notes in Computer Science, vol 14651
EUROCRYPT 2024. Lecture Notes in Computer Science, vol 14651. Springer, Cham. https://doi.org/10.1007/978-3-031-58716-0 1 (2024)
-
[20]
G. Davidoff, P. Sarnak and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs, Cambridge University Press, 2003
work page 2003
-
[21]
Deligne, La conjecture de Weil : I , Publications Mathematiques de l’ IHES, Volume 43 (1974), p
P. Deligne, La conjecture de Weil : I , Publications Mathematiques de l’ IHES, Volume 43 (1974), p. 273-307 39
work page 1974
-
[22]
P. Deligne and M. Rapoport, Les sch´ emas de modules des courbes elliptiques. In Modular Functions of One Variable II, Springer Lecture Notes in Mathematics 349 (1973)
work page 1973
-
[23]
F. Diamond and J. M. Shurman, A first course in modular forms. Vol. 228. New York: Springer, 2005
work page 2005
-
[24]
V. Dose, G. Lido, and P. Mercuri, Automorphisms of Cartan modular curves of prime and composite level, Algebra Number Theory 16 (2022), no. 6, 1423–1461
work page 2022
-
[25]
V. Dose, G. Lido, P. Mercuri and C. Stirpe, Modular curves with many points over finite fields, Journal of Algebra, 2023, ISSN 0021-8693, https://doi.org/10.1016/j.jalgebra.2023.07.013.,
-
[26]
M. Duparc and T. B. Fouotsa. SQIPrime: A dimension 2 variant of SQISignHD with non- smooth challenge isogenies. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 396-429). Singapore: Springer Nature Singapore, December 2024
work page 2024
-
[27]
Emerton, Supersingular elliptic curves, theta series and weight two modular forms, J
M. Emerton, Supersingular elliptic curves, theta series and weight two modular forms, J. Amer. Math. Soc. 15 (2002), no. 3, 671-714
work page 2002
-
[28]
G. Finol and E. Florit, Isogeny database, available at https://isogenies.enricflorit. com/index.html, DOI: https://zenodo.org/doi/10.5281/zenodo.4303870
-
[29]
T. B. Fouotsa, T. Moriya and C. Petit, M-SIDH and MD-SIDH: Countering SIDH At- tacks by Masking Information. In: Hazay, C., Stam, M. (eds) Advances in Cryptology - EUROCRYPT 2023. EUROCRYPT 2023 Lecture Notes in Computer Science, vol 14008. Springer, Cham
work page 2023
- [30]
-
[31]
L. De Feo, D. Kohel, A. Leroux, C. Petit, & B. Wesolowski. SQISign: compact post-quantum signatures from quaternions and isogenies. In Advances in Cryptol- ogy–ASIACRYPT 2020: 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I 26 (pp. 64-93). Sp...
work page 2020
-
[32]
L. De Feo, C. Guilhem, T. B. Fouotsa, P. Kutas, A. Leroux, C. Petit, J. Silva, and B. Wesolowski. S´ eta: Supersingular encryption from torsion attacks. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part IV, volume 13093 of LNCS, pages 249–278. Springer, Heidelberg, December 2021
work page 2021
- [33]
-
[34]
S. Dobson and S. D. Galbraith, On the Degree-Insensitive SI-GDH problem and assump- tion, pre-print
-
[35]
Friedman, A proof of Alon’s second eigenvalue conjecture and related problems
J. Friedman, A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc., 195(910) 2008
work page 2008
-
[36]
W. Fulton, Intersection theory. Vol. 2. Springer Science and Business Media, 2013. 40
work page 2013
-
[37]
W. Ghantous, S. Katsumata, F. Pintore, and M. Veroni, Collisions in Supersingular Isogeny Graphs and the SIDH-based Identification Protocol, IACR Cryptol. ePrint Arch. 2021 (2021): 1051
work page 2021
- [38]
- [39]
-
[40]
N.M. Katz and B. Mazur, Arithmetic moduli of elliptic curves, Annals of Mathematics Studies, Princeton University Press, 108 (1985)
work page 1985
-
[41]
Kohel, Endomorphism rings of elliptic curves over finite fields
D. Kohel, Endomorphism rings of elliptic curves over finite fields. Ph.D. Thesis, University of California, Berkeley, December, 1996
work page 1996
-
[42]
A. Lubotzky, R. Phillips and P. Sarnak , Ramanujan graphs, Combinatorica 8 (1988), 261–277
work page 1988
- [43]
- [44]
-
[45]
L. Maino and C. Martindale. An attack on SIDH with arbitrary starting curve. Cryptology ePrint Archive, Report 2022/1026, 2022. https://eprint.iacr.org/2022/ 1026
work page 2022
-
[46]
McKay, The expected eigenvalue distribution of a large regular graph
B.D. McKay, The expected eigenvalue distribution of a large regular graph. Linear Algebra Appl., 40, 1981
work page 1981
-
[47]
Mestre, La m´ ethode des graphes
J–F. Mestre, La m´ ethode des graphes. Exemples et applications, Proceedings of the in- ternational conference on class numbers and fundamental units of algebraic number fields (Katata, 1986), Nagoya University, pp. 217–242,
work page 1986
-
[48]
J.S. Milne, Lectures on ´ etale cohomology, Available on-line at http://www.jmilne.org/ math/CourseNotes/LEC.pdf (2013)
work page 2013
- [49]
-
[50]
K. Nakagawa, H. Onuki, W. Castryck, M. Chen, R. Invernizzi, G. Lorenzon, & F. Ver- cauteren. SQIsign2D-East: A new signature scheme using 2-dimensional isogenies. In In- ternational Conference on the Theory and Application of Cryptology and Information Security, pp. 272-303. Singapore: Springer Nature Singapore, December 2024
work page 2024
-
[51]
A. Page, B. Wesolowski. The Supersingular Endomorphism Ring and One Endomorphism Problems are Equivalent. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer Nature Switzerland, 2024
work page 2024
-
[52]
A. K. Pizer Ramanujan graphs and Hecke operator, Bulletin of the American Mathematical Society, Volume 23, Number 1, July 1990
work page 1990
-
[53]
M. Rebolledo and C. Wuthrich, A moduli interpretation for the non-split Cartan modular curve. Glasg. Math. J. 60.2 (2018), p. 411-434 41
work page 2018
-
[54]
Ribet, On modular representations of GalpQ{Qq arising from modular forms
K.A. Ribet, On modular representations of GalpQ{Qq arising from modular forms. Invent Math 100, 431–476 (1990)
work page 1990
-
[55]
Robert, Breaking SIDH in polynomial time, Eurocrypt 2023
D. Robert, Breaking SIDH in polynomial time, Eurocrypt 2023
work page 2023
-
[56]
J. P. Serre, Repartition asympotique des valeurs propres de l’operateur de Hecke Tp, J. Amer. Math. Soc. 10 (1997), 75-102
work page 1997
-
[57]
J. H. Silverman, The arithmetic of elliptic curves. Springer Science and Business Media, Vol. 106 (2009)
work page 2009
-
[58]
L. Trevisan, Lecture Notes on Graph Partitioning, Expanders and Spectral Methods, 2017, https://lucatrevisan.github.io/books/expanders-2016.pdf, licensed under the Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License 42
work page 2017
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.