Lubotzky–Phillips–Sarnak

Lubotzky–Phillips–Sarnak
Name	Lubotzky–Phillips–Sarnak
Field	Graph theory, Number theory, Representation theory
Introduced	1988
Authors	Alexander Lubotzky, Ronald C. Phillips, Peter Sarnak

Lubotzky–Phillips–Sarnak is a family of explicit regular graphs introduced in 1988 that provided the first infinite constructions of optimal expanders known as Ramanujan graphs in many degrees, linking graph theory with deep results from automorphic forms, adelic methods, and arithmetic groups. The construction draws on interactions among modular forms, quaternion algebras, Petersson trace formula, and the Jacquet–Langlands correspondence, producing Cayley graphs of finite groups that achieve extremal spectral bounds predicted by the Alon–Boppana bound. These graphs have influenced research in combinatorics, theoretical computer science, cryptography, and spectral graph theory.

Introduction

The Lubotzky–Phillips–Sarnak construction arose from a collaboration of Alexander Lubotzky, Ronald C. Phillips, and Peter Sarnak, motivated by questions posed by Alon and Boppana on eigenvalue gaps and by conjectures of Ramanujan and results of Deligne on eigenvalues of Hecke operators. Using arithmetic of quaternion algebras over Q and congruence subgroups of PGL2 over local fields, the authors produced families of explicit regular graphs whose nontrivial spectrum lies within the spectral radius of the universal cover Bruhat–Tits tree except for the trivial eigenvalue. The construction bridged tools from Langlands program, representation theory of GL2, and classical modular curve theory.

Construction of LPS Graphs

LPS graphs are built as Cayley graphs of finite groups such as PSL2(Fp) or PGL2(Fp) using generating sets arising from norm-one elements in maximal orders of certain quaternion algebras ramified at prescribed places. The method selects a prime p and a fixed prime q with prescribed quadratic residue relations, leveraging arithmetic of Legendre symbols and properties of Hilbert symbols. Vertices correspond to cosets of congruence subgroups of arithmetic lattices in PGL2(Qp), while edges correspond to multiplication by generators related to solutions of norm equations in the Hurwitz order or other maximal orders. The explicit nature of the generating sets permits efficient combinatorial descriptions analogous to Cayley graphs studied for S_n and A_n.

Spectral Properties and Ramanujan Graphs

LPS graphs realize the Ramanujan property by ensuring that all nontrivial eigenvalues of the adjacency operator lie in the interval predicted by the spectral measure of the universal cover, the (q+1)-regular tree or Bruhat–Tits tree. The proof uses deep results: Deligne’s proof of the Weil conjectures, the Jacquet–Langlands correspondence, and bounds for matrix coefficients in automorphic representations, connecting with the Petersson trace formula and consequences of Selberg trace formula. These inputs control the eigenvalues of Hecke operators acting on spaces of Maass forms or holomorphic modular forms, transferring spectral bounds to finite graphs and matching the Alon–Boppana bound asymptotically.

Applications in Computer Science and Number Theory

LPS graphs have been applied to explicit constructions in expander graph theory with consequences for network design, derandomization, and complexity theory including work related to PCP theorems, error-correcting codes, and hash function design in cryptography. They inform constructions in pseudo-randomness and are used in algorithms for sparse matrix preconditioning and rapid mixing of Markov chaines. In number theory, LPS constructions illuminate congruence subgroup properties of arithmetic lattices, interactions with Galois representations, and examples in the study of sieve theory and distribution of primes via expansion properties of Cayley graphs of SL2(Z/nZ).

Generalizations and Related Constructions

Subsequent work generalized LPS methods to produce Ramanujan graphs and complexes using higher-rank groups such as PGLn and SLn, yielding Ramanujan complexes built from Bruhat–Tits buildings; notable approaches include work by M.V. Nori, Amitay and Lubotzky collaborators, and explicit constructions by Marcus, Spielman, Srivastava via interlacing polynomials producing bipartite Ramanujan graphs for all degrees. The Morgenstern construction extended LPS ideas to non-prime powers, while Li and Conway-type approaches connected with lattice sphere packings. The theory connects to constructions of expanders from Kazhdan groups, Margulis expanders, and Selberg’s eigenvalue conjecture considerations.

Historical Context and Contributors

The LPS paper arose in the context of a surge of interest in explicit expanders driven by Margulis and developments in automorphic forms and the Langlands program. Principal contributors include Alexander Lubotzky, Phillips, and Sarnak with foundational background from Selberg, Deligne, Jacquet, Langlands, Iwaniec, Piatetski-Shapiro, and others. Later influential researchers expanding the theory include Lubotzky again, Morgenstern, Margulis, Friedman, Hoory, Linial, Wigderson, Spielman, Micheletti, and Marcus, Spielman, Srivastava. The impact spans institutions such as Institute for Advanced Study, Princeton University, Hebrew University of Jerusalem, Massachusetts Institute of Technology, and Tel Aviv University, and influenced conferences in combinatorics and number theory throughout the late 20th and early 21st centuries.

Category:Expander graphs