NSF Logo IPAM Logo UCLA Logo

Automorphic Forms, Group Theory and Graph Expansion

February 9 - 13, 2004

Schedule and Presentations

Program Poster PDF


Problems Collected at the Workshop

Organizing Committee

William Kantor (University of Oregon)
Alexander Lubotzky (Hebrew University, Jerusalem, Israel)
Jon Rogawski (UCLA)
Audrey Terras (University of California at San Diego)
Avi Wigderson (Institute for Advanced Studies, Princeton)

Scientific Background

In recent years, new and important connections have emerged between discrete subgroups of Lie groups, automorphic forms and arithmetic on the one hand, and questions in discrete mathematics, combinatorics, and graph theory on the other. One of the first examples of this interaction was the explicit construction of expanders (regular graphs with a high degree of connectedness) via Kazhdan's property T or via Selberg's theorem (lambda1 is greater than 3/16). Some other important fruits of this interaction were the construction of Ramanujan graphs, using the Jacquet-Langlands correspondence and Deligne's theorem on Hecke eigenvalues (Ramanujan conjecture), construction of new finitely presented simple groups via ergodic theory of lattices (a la Margulis) in a product of two trees, and a conceptual approach to the Product Replacement Algorithm of computational group theory (the convergence properties of the algorithm are related to question of whether automorphism groups of free groups have property T). In each of these cases, an unexpected application to discrete mathematics was found by using ideas from number theory, Lie groups, representation theory and ergodic theory. Applications flow in the reverse direction as well. A new combinatorial construction of expander graphs was used recently to resolve a group theoretic question on expansion in Cayley graphs. One reason these connections have been slow to emerge is that the fields involved are quite far apart, at least from the traditional viewpoint. People working in one side of the Lie Group/Discrete Math dichotomy are often not aware of the relevance of their work to the other side. Furthermore, each field has its own language and conceptual framework, so there is often a formidable language barrier to communication. This workshop will bring together mathematicians from several of the above-mentioned areas in order to strengthen the ties between the fields and generate further collaborations.

Topics to be included are:

I. Ramanujan Complexes

In the 1980's, results from the theory of automorphic forms were used to construct explicit families of Ramanujan graphs, that is, graphs for which Laplace eigenvalues satisfy strong inequalities. These constructions led to the solution of several long-standing problems in graph theory. The graphs themselves are constructed group-theoretically, as quotients of infinite regular trees (the Bruhat-Tits building) by arithmetic subgroups of the p-adic group SL2(Qp) arising from quaternion algebras. Proving that they have the Ramanujan property requires deep results from arithmetic and the automorphic forms. One uses the Jacquet-Langlands correspondence from the theory of automorphic forms to transport the problem to GL(2) and then invokes arithmetical results (work of Eichler and Deligne on the Ramanujan conjecture for classical modular forms). Work on the mixed case SL2(Qp) x SL2(Qq) has lead to interesting results on symbolic dynamical systems. Higher dimensional complexes can be constructed in an analogous manner from higher rank p-adic groups. This leads to a rich collection of remarkable finite complexes whose properties, however, are much more subtle than the one-dimensional Ramanujan graphs. This is already clear from the point of view of automorphic forms, where naive generalizations of the Ramanujan conjecture are know to be false and the correct formulations involve Langlands functoriality and the Arthur conjectures. Higher-dimensional have been pursued by a number of researchers. The natural starting point for further investigatations is the recent work of Lafforgue on GL(n) over function fields. It will provide a great deal of combinatorial information on these complexes.

II. Finite simple groups

The theory of arithmetic groups and representation theory of semisimple groups have led to results on the diameters and expansion properties of finite simple groups. For example, it has been shown that in every family of non-abelian finite simple groups there exists a bounded set of generators with a logarithmic diameter. While there is now a proof of this independent of representation theory, the only known proof for specific "natural" sets of generators, even for SL(2,p), relies on the celebrated Selberg Theorem on the eigenvalues of the Laplacian on arithmetic hyperbolic groups. The important question whether finite simple groups of bounded rank have uniform expansion properties is still open. A recent breakthrough in graph theory.('The Zig-Zag product') was applied to show that some finite groups (though not simple groups as of now) have non-uniform expansion properties.

III. The Product Replacement Algorithm

This is a commonly used algorithm to generate a pseudo-random element in a finite group. While the algorithm shows outstanding performance in practice, its theoretical explanation is still somewhat mysterious. It was shown recently that the convergence properties of the algorithm are related to the question of whether automorphism groups of various relative free groups have property T. This provides a new conceptual approach to understanding the algorithm and is a wonderful example in which a problem from discrete mathematics has given new life to a well-known open problem in representation theory.

IV. Zigzag Product

A direct combinatorial method to construct expanders was found recently using the Zig-Zag product. Beside its intrinsic interest, this may have applications to group theory. It was already observed that this product is closely connected to semi-direct product of groups and as mentioned in (II) this has been used to solve a group theoretic problem. Moreover, it raises questions on counting representations of finite groups and show how these representation-theoretic questions are connected with expansion properties of the groups.

V. 3-Manifolds and Expanders

The Lubotzky-Sarnak Conjecture asserts that compact hyperbolic 3-manifold groups, i.e. cocompact lattices in SL(2,C), do not have property 'tau'. This means that some of their finite Cayley graph quotients are not expanders. A recent manuscript of Lackenby (Oxford) shows that this conjecture may provide a path to prove the famous Virtual Hacken Conjecture for hyperbolic 3-manifolds.

Related Program

Information about a program in a related topic, Lie Groups, Representations and Discrete Mathematics to be held in 2005-6 at the Institute for Advanced Study School of Mathematics can be found at:



Cristina Ballantine (Holy Cross)
Donald Cartwright (University of Sydney)
Anton Deitmar (Exeter University)
Joel Friedman (University of British Columbia, Vancouver)
Alexander Gamburd (Stanford University)
Yair Glasner (University of Illinois)
Bruce Jordan (Baruch College, New York)
William Kantor (University of Oregon)
Wen-Ching Li (Pennsylvania State University)
Nathan (Nati) Linial (Hebrew University, Jerusalem, Israel)
Alexander Lubotzky (Hebrew University, Jerusalem, Israel)
Roy Meshulam (Technion, Haifa, Israel)
Shahar Mozes (Hebrew University, Jerusalem, Israel)
Igor Pak (Massachusetts Institute of Technology)
Jon Rogawski (UCLA)
Eyal Rozenman (Hebrew University, Jerusalem, Israel)
Beth Samuels (Yale University)
Peter Sarnak (Princeton University)
Tatiana Smirnova-Nagnibeda (University of Geneva)
Tim Steger (UNISS, Italy)
Audrey Terras (University of California at San Diego)
Salil Vadhan (Harvard University)
Uzi Vishne (Bar-Ilan University)
Avi Wigderson (Institute for Advanced Studies, Princeton)
David Zuckerman (University of Texas, Austin)
Andrzej Zuk (University of Chicago)

Contact Us:

Institute for Pure and Applied Mathematics (IPAM)
Attn: AGG2004
460 Portola Plaza
Los Angeles CA 90095-7121
Phone: 310 825-4755
Fax: 310 825-4756
Email: ipam@ucla.edu
Website: http://www.ipam.ucla.edu/programs/agg2004/

Home ] [ People ] [ Events ]  Programs  [ Visitor Info ]
Contact: (310)825-4755