Strongly explicit Ramanujan 2-lift towers via Hilbert modular forms
Abstract
Expander graphs have been central objects of study for over fifty years. Ramanujan graphs attain the asymptotically optimal nontrivial adjacency-eigenvalue threshold for infinite fixed-degree families. The original arithmetic constructions by Lubotzky-Phillips-Sarnak (1988) and Margulis (1988), and the iterative $2$-lift method of Bilu-Linial (2006) provide different approaches to Ramanujan graph constructions. Motivated by work on Mealy automata, we combine both approaches to give the following new arithmetic construction. For every prime p≡ 1pmod 17, we construct a infinite tower of (p+1)-regular non-bipartite Ramanujan graphs on 2n vertices, with label-preserving $2$-lifts between consecutive levels. These construction is strongly explicit: for fixed p, a neighbor or lift sign is computable in Op(n3) bit operations. The construction uses fixed algebraic $2$-adic transformations, specified by finite data computable in preprocessing depending only on p. The main number-theoretic tool is Blasius's Ramanujan-Petersson theorem for Hilbert modular forms, applied through the Jacquet-Langlands correspondence to obtain the sharp bound |λ|≤2√p for every nontrivial adjacency eigenvalue of our (p+1)-regular graphs. The transformations preserve $2$-adic distance, which gives the binary covers and an explicit formula for their signings.
Related
- Eta-Quotient Representations for a Three Parameter Family of Modular Functions Associated with the Rogers-Ramanujan Continued Fraction
- Analytical Evaluation of Ramanujan Series for 1/π via Degree-2, Degree-3, Degree-7, and Degree-19 Modular Transformations
- On the Ramanujan-Ligozat modular unit
- The strong Ramanujan bound for Drinfeld modular forms
- Character sums on an oriented singer conic and explicit Ramanujan double covers
BibTeX
@misc{kharlampovich2026strongly,
title = {{Strongly explicit Ramanujan 2-lift towers via Hilbert modular forms}},
author = {Olga Kharlampovich and Igor Pak and Alina Vdovina},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.39485},
eprint = {2610.39485},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.39485},
}
RIS
TY - UNPB
TI - Strongly explicit Ramanujan 2-lift towers via Hilbert modular forms
AU - Olga Kharlampovich
AU - Igor Pak
AU - Alina Vdovina
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.39485
UR - https://arxiv.org/abs/2610.39485
AB - Expander graphs have been central objects of study for over fifty years. Ramanujan graphs attain the asymptotically optimal nontrivial adjacency-eigenvalue threshold for infinite fixed-degree families. The original arithmetic constructions by Lubotzky-Phillips-Sarnak (1988) and Margulis (1988), and the iterative $2$-lift method of Bilu-Linial (2006) provide different approaches to Ramanujan graph constructions. Motivated by work on Mealy automata, we combine both approaches to give the following new arithmetic construction. For every prime p≡ 1pmod 17, we construct a infinite tower of (p+1)-regular non-bipartite Ramanujan graphs on 2^n vertices, with label-preserving $2$-lifts between consecutive levels. These construction is strongly explicit: for fixed p, a neighbor or lift sign is computable in O_p(n^3) bit operations. The construction uses fixed algebraic $2$-adic transformations, specified by finite data computable in preprocessing depending only on p. The main number-theoretic tool is Blasius's Ramanujan-Petersson theorem for Hilbert modular forms, applied through the Jacquet-Langlands correspondence to obtain the sharp bound |λ|≤2√p for every nontrivial adjacency eigenvalue of our (p+1)-regular graphs. The transformations preserve $2$-adic distance, which gives the binary covers and an explicit formula for their signings.
ER -