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

职业：扩展图：算术、群论和组合学之间的相互作用

• 批准号: 0645807
• 负责人: Alexander Gamburd
• 金额: $ 40万
• 依托单位: University of California-Santa Cruz
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-07-01 至 2013-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0645807&HistoricalAwards=false
• 关键词: CAREER; Expander; Graphs; Interactions; between

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.

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