pith. sign in

arxiv: 2308.13913 · v5 · submitted 2023-08-26 · 🧮 math.NT · math.AG

Spectral Theory of Isogeny Graphs

Pith reviewed 2026-05-24 07:54 UTC · model grok-4.3

classification 🧮 math.NT math.AG
keywords isogeny graphssupersingular elliptic curvesRamanujan graphsadjacency matricesspectral graph theorymodular formsisogeny-based cryptography
0
0 comments X

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.

The paper proves an upper bound on the absolute values of the eigenvalues of the adjacency matrices for graphs whose vertices are supersingular elliptic curves, possibly with level structure, and whose edges are isogenies of prime degree. This bound implies that the graphs satisfy the Ramanujan condition for optimal spectral expansion. The authors further examine the asymptotic distribution of the eigenvalues, the number of connected components, the automorphism groups, and the relation of the graphs to modular forms.

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

These are editorial extensions of the paper, not claims the author makes directly.

  • 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

Figures reproduced from arXiv: 2308.13913 by Giulio Codogni, Guido Maria Lido.

Figure 1
Figure 1. Figure 1: This is an example of isogeny graph Gpp, ℓ, Hq with p “ 23, ℓ “ 3 and H “ xp 5 6 2 1 q,p 1 2 0 1 q,p 7 0 2 7 q,p 5 0 0 5 q,p 2 7 7 1 q,p 1 4 0 1 q,p 1 0 4 1 qy the only index 8 subgroup of GL2pZ{8Zq. Color indicates the elliptic curve, or equivalently the j-invariant. The level structure is given through a matrix: for each of the three elliptic curves we have chosen a (non-canonical) basis of the 8-torsion… view at source ↗
Figure 2
Figure 2. Figure 2: Numerical experiments on ηpp, ℓq References [1] D. Abramovich, M. Olsson and A. Vistoli, Twisted stable maps to tame Artin stacks, J. Algebraic Geom. 20 (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… view at source ↗
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.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

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)
  1. [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.
  2. [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)
  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

2 responses · 0 unresolved

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
  1. 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

  2. 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

0 steps flagged

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

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard theory of supersingular elliptic curves, their endomorphism rings being maximal orders in quaternion algebras, and the definition of the isogeny graph; no free parameters or invented entities are visible in the abstract.

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.
    This is the definition of the graphs whose adjacency matrices are studied; it is invoked in the first sentence of the abstract.
  • 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.
    This is the mathematical premise required for the eigenvalue bound to exist; it is the content of the main result statement.

pith-pipeline@v0.9.0 · 5606 in / 1510 out tokens · 33061 ms · 2026-05-24T07:54:32.941234+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation 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.lean reality_from_one_distinction unclear
    ?
    unclear

    Relation 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

58 extracted references · 58 canonical work pages

  1. [1]

    Abramovich, M

    D. Abramovich, M. Olsson and A. Vistoli, Twisted stable maps to tame Artin stacks, J. Algebraic Geom. 20 (2011)

  2. [2]

    Amor´ os, A

    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. [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. [4]

    Arpin, C

    S. Arpin, C. Camacho-Navarro, K. Lauter, J. Lim, K. Nelson, T. Scholl, J. & Sot´ akov´ a, Adventures in supersingularland. Experimental Mathematics, 32(2), 241-268. 38

  5. [5]

    Arpin, M

    S. Arpin, M. Chen, K. E. Lauter, R. Scheidler, K. E. Stange, and H. T. Nguyen Tran. Orientations and cycles in supersingular isogeny graphs. ArXiv 2022

  6. [6]

    A. O. L. Atkin and J. Lehner, Hecke operators on Γ 0pmq, Math. Ann. 185 (1970), 134–160. MR 268123

  7. [7]

    Basso, G

    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

  8. [8]

    Basso, G

    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, preprint version, https://eprint.iacr.org/2022/1469

  9. [9]

    De Feo, P

    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

  10. [10]

    Basso, L

    A. Basso, L. Maino, and G. Pope. FESTA: Fast Encryption from Supersingular Torsion Attacks. Cryptology ePrint Archive, Paper 2023/660, 2023

  11. [11]

    Bordenave, A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts, Ann

    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)

  12. [12]

    Bosch, W

    S. Bosch, W. L¨ utkebohmert, M. Raynaud, N´ eron models. Springer-Verlag, Berlin, 1990

  13. [13]

    Castryck and T

    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

  14. [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

  15. [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

  16. [16]

    Coleman and B

    R. Coleman and B. Edixhoven. On the semi-simplicity of up-operator on modular forms. Math. Ann, 310, 1988

  17. [17]

    Cowan, Computing newforms using supersingular isogeny graphs

    A. Cowan, Computing newforms using supersingular isogeny graphs. Res. number theory 8, 96 (2022)

  18. [18]

    Dartois, A

    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. [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. [20]

    Davidoff, P

    G. Davidoff, P. Sarnak and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs, Cambridge University Press, 2003

  21. [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

  22. [22]

    Deligne and M

    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)

  23. [23]

    Diamond and J

    F. Diamond and J. M. Shurman, A first course in modular forms. Vol. 228. New York: Springer, 2005

  24. [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

  25. [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. [26]

    Duparc and T

    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

  27. [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

  28. [28]

    Finol and E

    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. [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

  30. [30]

    De Feo, T

    L. De Feo, T. B. Fouotsa and L. Panny. Isogeny problems with level structure. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham: Springer Nature Switzerland, 2024

  31. [31]

    De Feo, D

    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...

  32. [32]

    De Feo, C

    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

  33. [33]

    De Feo, D

    L. De Feo, D. Jao, and J. Plˆ ut. Towards quantum-resistant cryptosystems from supersin- gular elliptic curve isogenies, Journal of Mathematical Cryptology, 8(3):209–247, 2014

  34. [34]

    Dobson and S

    S. Dobson and S. D. Galbraith, On the Degree-Insensitive SI-GDH problem and assump- tion, pre-print

  35. [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

  36. [36]

    Fulton, Intersection theory

    W. Fulton, Intersection theory. Vol. 2. Springer Science and Business Media, 2013. 40

  37. [37]

    Ghantous, S

    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

  38. [38]

    Hoory, N

    S. Hoory, N. Linial and A. Wigderson, Expander graphs and their application, Bullettin of the American Mathematical Socitety, Volume 43, Number 4, October 2006

  39. [39]

    Huang, T

    J. Huang, T. McKenzie and Horng-Tzer Yau, Ramanujan Property and Edge Universality of Random Regular Graphs, https://arxiv.org/abs/2412.20263 , 2025

  40. [40]

    Katz and B

    N.M. Katz and B. Mazur, Arithmetic moduli of elliptic curves, Annals of Mathematics Studies, Princeton University Press, 108 (1985)

  41. [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

  42. [42]

    Lubotzky, R

    A. Lubotzky, R. Phillips and P. Sarnak , Ramanujan graphs, Combinatorica 8 (1988), 261–277

  43. [43]

    Lei and K

    A. Lei and K. M¨ uller. On the zeta functions of supersingular isogeny graphs and modular curves. Archiv der Mathematik, Vol. 122, pp. 285-294, 2024

  44. [44]

    Lei and K

    A. Lei and K. M¨ uller. On towers of Isogeny graphs with full level structure. https:// arxiv.org/abs/2309.00524. 2023

  45. [45]

    Maino and C

    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

  46. [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

  47. [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,

  48. [48]

    Milne, Lectures on ´ etale cohomology, Available on-line at http://www.jmilne.org/ math/CourseNotes/LEC.pdf (2013)

    J.S. Milne, Lectures on ´ etale cohomology, Available on-line at http://www.jmilne.org/ math/CourseNotes/LEC.pdf (2013)

  49. [49]

    Miyake, Modular Forms

    T. Miyake, Modular Forms. Springer, Berlin (1989)

  50. [50]

    Nakagawa, H

    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

  51. [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

  52. [52]

    A. K. Pizer Ramanujan graphs and Hecke operator, Bulletin of the American Mathematical Society, Volume 23, Number 1, July 1990

  53. [53]

    Rebolledo and C

    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

  54. [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)

  55. [55]

    Robert, Breaking SIDH in polynomial time, Eurocrypt 2023

    D. Robert, Breaking SIDH in polynomial time, Eurocrypt 2023

  56. [56]

    J. P. Serre, Repartition asympotique des valeurs propres de l’operateur de Hecke Tp, J. Amer. Math. Soc. 10 (1997), 75-102

  57. [57]

    J. H. Silverman, The arithmetic of elliptic curves. Springer Science and Business Media, Vol. 106 (2009)

  58. [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