Algebraic, combinatorial, spectral and algorithmic properties of groups generated by finite automata

有限自动机生成的群的代数、组合、谱和算法特性

• 批准号: 0600975
• 负责人: Rostislav Grigorchuk
• 金额: $ 19.24万
• 依托单位: Texas A&M Research Foundation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-01 至 2009-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0600975&HistoricalAwards=false
• 关键词: Algebraic; combinatorial; spectral; algorithmic; properties

DMS-0600975PI: Rostislav GrigorchukCo-PI: Zoran SunikThe proposers work on various problems in Algebra, Dynamics, Topology and Analysis that have algebraic roots and whose solution can be obtained by using automaton groups. In particular, this includes problems of Day-von Neumann type and Greanleaf type on amenability, Milnor type questions on growth in Cayley and Schreier graphs, spectral considerations, including Kesten-von Neumann-Serre spetral measures and self-similar measures related to random walks, expanders and Ramanujan graphs, etc. Algebraic and algorithmic properties of automaton group, such as just-infiniteness, dynamics of automorphisms, the congruence subgroup property, maximal and weakly maximal subgroups, subgroup structure, characteristic subgroups, L-presentations, conjugacy problem, isomorphism problem, etc., are considered and studied. Attention is paid to the geometric properties of automaton groups. Such properties include the geometry of the Cayley and, more generally, Schreier graphs, expanding properties, actions on rooted trees and cubic complexes and various finiteness conditions. Further, asymptotic properties of automaton groups are studied. Such properties include growth, amenability, Property T of Kazhdan, spectral properties, L2-cohomology, etc. A special attention is paid to the famous combinatorial problem know as Hanoi Towers Problem. The proposers have devised an algebraic approach to this problem by constructing groups (Hanoi Towers groups) that serve the role of renormalization groups. A complete classification of 3-state automaton groups over a 2-letter alphabet is expected.The idea of self-similarity is one of the most basic and fruitful ideas in mathematics of all times and populations. In the last few decades it established itself as the central notion in areas such as fractal geometry, dynamical systems, and statistical physics. Recently, mainly through the work of the proposers and their collaborators, self-similarity started playing a role in algebra as well, first of all in group theory. The methods developed in relation to the study of self-similarity in group theory have been successfully applied in recent years in the solution of many longstanding open problems and conjectures in mathematics (General Burnside problem, Milnor Problem on growth, Day-von Neumann Problem on amenability, Zelmanov Problem on finiteness of width, Atiyah Strong Conjecture, to name a few). The proposed study of automaton groups, which constitute a class of self-similar groups, has unlimited potential for further continuation of this positive trend. In addition to advancements in basic research in several areas of mathematics the proposed research has applications in computer science (expanders are indispensable tool in algorithm de-randomization and reliable network design), coding and information theory (automata can be used to construct codes with extremely good characteristics), and combinatorial game theory (the proposers have modeled some of the most outstanding combinatorial problems by using finite automaton groups).

DMS-0600975PI: Rostislav GrigorchukCo-PI: Zoran sunik这些人研究代数、动力学、拓扑和分析中的各种问题，这些问题都有代数根，并且可以通过自动机群来求解。特别是，这包括关于可迁就性的日-冯-诺伊曼型和格林利夫型问题，关于Cayley图和Schreier图中生长的Milnor型问题，谱的考虑，包括Kesten-von Neumann- serre谱测度和与随机游走、扩展和Ramanujan图相关的自相似测度等。研究了自动机群的代数和算法性质，如刚无穷性、自同构的动力学、同余子群性质、极大和弱极大子群、子群结构、特征子群、l -表示、共轭问题、同构问题等。关注自动机群的几何性质。这些性质包括Cayley的几何，更一般地说，Schreier图，展开性质，在有根树和立方复体上的作用以及各种有限条件。进一步研究了自动机群的渐近性质。这些性质包括生长性、适应性、哈兹丹性质T、光谱性质、l2 -上同性等。特别注意著名的组合问题，即河内塔问题。作者设计了一种代数方法来解决这个问题，通过构造群（河内塔群）来服务于重整化群的角色。期望在2个字母的字母表上对3状态自动机组进行完整的分类。自相似思想是古往今来数学中最基本、最富有成果的思想之一。在过去的几十年里，它在诸如分形几何、动力系统和统计物理等领域确立了自己的中心概念。最近，主要是通过提出者和他们的合作者的工作，自相似性开始在代数中发挥作用，首先是在群论中。近年来，与群理论中自相似性研究相关的方法已成功地应用于解决数学中许多长期开放的问题和猜想（一般Burnside问题，关于增长的Milnor问题，关于适应性的Day-von Neumann问题，关于宽度有限的Zelmanov问题，Atiyah Strong猜想，仅举几例）。自动机群构成了一类自相似群，提出的自动机群研究对于进一步延续这一积极趋势具有无限的潜力。除了在几个数学领域的基础研究取得进展外，提议的研究还应用于计算机科学（扩展器是算法去随机化和可靠网络设计中不可或缺的工具）、编码和信息论（自动机可以用来构造具有极好特征的代码）和组合博弈论（提议者通过使用有限自动机群对一些最突出的组合问题进行建模）。