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

扩展器是在计算机科学中广泛使用的高度连通的稀疏图。在80年代中期，Marguis、Lubotzky、Phillips和Sarnak利用自同构形式理论的深刻结果(Selberg的3/16定理，证明了Ramanujann猜想)，给出了关于非常特殊的生成元选择的有限群的Cayley图的扩张器的显式构造。卢博茨基和韦斯提出的一个基本问题是，在多大程度上，作为一个扩张者家族是这两个群体的属性，与发电机的选择无关。首席研究员的第一个项目将致力于解决这个问题，并使用最近从加法组合学开发的工具来构建新的健壮的扩张器家族。首席研究员的第二个项目建立在最近与Bourain和Sarnak的合作基础上，其中使用扩展器来获得关于算术级数中关于素数的Dirichlet定理的非阿贝尔推广的新的筛选结果。在第二个项目中讨论的一般问题涉及筛选由有限多项式映射生成的群的轨道上的素数(或几乎素数)；组合Brun筛子的应用关键取决于与轨道相关的“同余图”的展开性质。首席研究员的第三个项目致力于从统一的观点研究与膨胀图有关的一个基本猜想和量子混沌理论中的一个基本猜想。扩展图理论中的一个基本猜想断言，许多群族都是关于随机选择的生成元(随机生成元的独立猜想)的扩展。量子混沌中的一个基本猜想，由Bohigas，Giannoni和Shmit提出，断言量子化的混沌哈密顿的本征值的行为类似于适当的随机矩阵集合中的典型成员的频谱。这两种猜想都可以被视为断言，确定性构造的频谱“一般”的行为类似于大型随机矩阵的频谱：“在整体中”(量子Chaos猜想)和“在频谱的边缘”(独立猜想)。主要研究人员将致力于在群环中元素的谱的背景下证明这些猜想。扩展器是高度连接的稀疏图，广泛应用于计算机科学，从并行计算到复杂性理论和密码学等领域。七十年代初，在Pinsker观察到随机稀疏图是扩张器之后，Marguis给出了扩张器的第一个显式群论构造；在八十年代末，Marguis，Lubotzky，Phillips和Sarnak使用深入的数论结果构造了著名的Ramanujan图(从谱的角度看最优扩张器)。在接下来的几年里，膨胀机的应用范围和深度大大增加；在过去十年中，出现了几条全新的和意想不到的发展路线，该领域经历了爆炸性的增长。首席研究员计划开展三个项目，以扩充器为中心，涉及算术、群论和组合学之间的互惠互动。第一个项目致力于使用最近从加性组合数学中开发的工具来构建新的健壮的扩张器家族。在第二个项目中，扩充器将被用来获得新的筛选结果，从而部分偿还计算机科学对数论的欠债。第三个项目致力于研究扩展图与随机矩阵之间的联系。首席研究员将指导研究生对与上述三个项目相关的问题的研究，并将设计和教授加法组合学和随机矩阵理论的研究生课程，以及一门致力于扩展图的应用和构造的本科课程。他还将指导本科生的研究项目，包括数值实验、数据分析、背景阅读和理论工作。此外，首席研究员将组织会议，将旧金山湾区的研究人员和研究生聚集在一起，进行为期一天的演讲和非正式讨论，从而在研究和教育方面进行长期合作。

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 Ramanujanconjectures) 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 ChaosConjecture) 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.