Explicit construction of optimal expanding graphs using number theory
Strongly explicit Ramanujan 2-lift towers via Hilbert modular forms
Discrete Mathematics
Summary
Expander graphs are special networks with strong connectivity, useful in computing and communications. The authors found a new way to build infinite families of these graphs that meet the best possible standards (called Ramanujan graphs) using advanced number theory. Their construction is explicit, meaning you can efficiently identify connections between nodes. This is done by combining previous mathematical methods and applying properties of special algebraic forms to get strong guarantees about the graphs' quality.
What this means in practice
- •For network architects: Construct large communication networks with optimal connectivity and minimal latency using explicit Ramanujan graph designs.
- •For cryptography engineers: Design cryptographic protocols relying on expander graphs with provable spectral properties optimized through number-theoretic constructions.
Authors
Olga Kharlampovich, Igor Pak, Alina Vdovina
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\equiv 1\pmod {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 $|λ|\leq2\sqrt 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.