Automorphic Forms, Group Theory and Graph ExpansionFebruary 9  13, 2004Problems Collected at the WorkshopOrganizing Committee
William Kantor
(University of Oregon)
Scientific BackgroundIn 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 (lambda_{1} is greater than 3/16). Some other important fruits of this interaction were the construction of Ramanujan graphs, using the JacquetLanglands 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 abovementioned areas in order to strengthen the ties between the fields and generate further collaborations. Topics to be included are: I. Ramanujan ComplexesIn 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 longstanding problems in graph theory. The graphs themselves are constructed grouptheoretically, as quotients of infinite regular trees (the BruhatTits building) by arithmetic subgroups of the padic group SL_{2}(Q_{p}) arising from quaternion algebras. Proving that they have the Ramanujan property requires deep results from arithmetic and the automorphic forms. One uses the JacquetLanglands 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 SL_{2}(Q_{p}) x SL_{2}(Q_{q}) has lead to interesting results on symbolic dynamical systems. Higher dimensional complexes can be constructed in an analogous manner from higher rank padic groups. This leads to a rich collection of remarkable finite complexes whose properties, however, are much more subtle than the onedimensional 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. Higherdimensional 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 groupsThe 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 nonabelian 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 ZigZag product') was applied to show that some finite groups (though not simple groups as of now) have nonuniform expansion properties. III. The Product Replacement AlgorithmThis is a commonly used algorithm to generate a pseudorandom 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 wellknown open problem in representation theory. IV. Zigzag ProductA direct combinatorial method to construct expanders was found recently using the ZigZag product. Beside its intrinsic interest, this may have applications to group theory. It was already observed that this product is closely connected to semidirect 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 representationtheoretic questions are connected with expansion properties of the groups. V. 3Manifolds and ExpandersThe LubotzkySarnak Conjecture asserts that compact hyperbolic 3manifold 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 3manifolds. Related Program
Information about a program in a related topic, Lie Groups, Representations and
Discrete Mathematics to be held in 20056 at the Institute for Advanced Study School of Mathematics can be found
at: SpeakersCristina 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) WenChing 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 SmirnovaNagnibeda (University of Geneva) Tim Steger (UNISS, Italy) Audrey Terras (University of California at San Diego) Salil Vadhan (Harvard University) Uzi Vishne (BarIlan 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) 
