CAREER: Expander Graphs: Interactions between Arithmetic, Group Theory and Combinatorics

University Of California-Santa Cruz, Santa Cruz CA

Investigators

Abstract

Expanders are highly-connected sparse graphs widely used in computer science. In the mid-eighties Margulis, Lubotzky, Phillips and Sarnak used deep results from the theory of automorphic forms (Selberg's 3/16 theorem, proved Ramanujan conjectures) to give explicit constructions of expanders as Cayley graphs of finite groups with respect to very special choices of generators. A basic problem, formulated by Lubotzky and Weiss, is to what extent being an expander family is a property of the groups alone, independent of the choice of generators. The first project of the principal investigator will be devoted to addressing this problem and constructing new robust families of expanders using recently developed tools from additive combinatorics. The second project of the principal investigator builds on the recent joint work with Bourgain and Sarnak, in which expanders were used to obtain novel sieving results towards non-abelian generalizations of Dirichlet's theorem on primes in arithmetic progressions. The general problem addressed in the second project involves sieving for primes (or almost-primes) on an orbit of a group generated by finitely many polynomial maps; application of combinatorial Brun sieve depends crucially on the expansion property of the "congruence graphs" associated with the orbit. The third project of the principal investigator is devoted to studying from a unified point of view one of the basic conjectures pertaining to expander graphs and one of the basic conjectures in the theory of Quantum Chaos. A basic conjecture in the theory of expander graphs asserts that many families of groups are expanding with respect to random choices of generators (Independence Conjecture for random generators). A basic conjecture in Quantum Chaos, formulated by Bohigas, Giannoni, and Shmit, asserts that the eigenvalues of a quantized chaotic Hamiltonian behave like the spectrum of a typical member of the appropriate ensemble of random matrices. Both conjectures can be viewed as asserting that a deterministically constructed spectrum "generically" behaves like the spectrum of a large random matrix: "in the bulk" (Quantum Chaos Conjecture) and at the "edge of the spectrum" (Independence Conjecture). The principal investigator will work on proving these conjectures in the context of the spectra of elements in group rings. Expanders are highly-connected sparse graphs widely used in Computer Science, in areas ranging from parallel computation to complexity theory and cryptography. In the early seventies, following Pinsker's observation that random sparse graphs are expanders, Margulis gave the first explicit group-theoretic construction of expanders; in the late eighties Margulis, Lubotzky, Phillips and Sarnak constructed celebrated Ramanujan graphs (optimal expanders from spectral point of view) using deep number-theoretic results. In the ensuing years the scope and depth of applications of expanders has dramatically increased; over the past decade several completely new and unexpected lines of development have emerged and the field has undergone explosive growth. The principal investigator plans to pursue three projects centered on expanders and involving mutually beneficial interactions between arithmetic, group theory and combinatorics. The first project is devoted to constructing new robust families of expanders using recently developed tools from additive combinatorics. In the second project expanders will be used to obtain novel sieving results, thus partially repaying the debt of computer science to number theory. The third project is devoted to studying connections between expander graphs and random matrices. The principal investigator will direct research by graduate students on the problems related to the three projects described above and will design and teach graduate courses in additive combinatorics and random matrix theory, as well as an undergraduate course devoted to applications and constructions of expander graphs. He will also direct undergraduate research projects, involving a mix of numerical experimentation, analyzing data, background reading, and theoretical work. In addition, the principal investigator will organize meetings bringing together Bay Area researchers and graduate students for a day of talks and informal discussions, leading to long-term collaborations in research and education.