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

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

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.