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

DMS-0600975PI：Rostislav GrigorchukCo-Pi：Zoran Sunik提出者致力于代数、动力学、拓扑和分析中的各种问题，这些问题的解可以使用自动机群来获得。特别地，包括关于顺从性的Day-von Neumann型和Greanlie型问题，关于Cayley图和Schreier图的增长性的Milnor型问题，谱考虑，包括与随机游动、扩张器和Ramanujan图有关的Kesten-von Neumann-Serre谱测度和自相似测度等，考虑和研究了自动机群的代数和算法性质，如刚无限，自同构动力学，同余子群性质，极大和弱极大子群，子群结构，特征子群，L-表示，共轭问题，同构问题等。研究了自动机群的几何性质。这些性质包括Cayley图的几何，更一般地，Schreier图，扩展性质，在根树和三次复形上的作用以及各种有限条件。进一步，研究了自动机群的渐近性质。这些性质包括增长性、柔和性、Kazhdan的性质T、谱性质、L2上同调等。特别关注著名的组合问题，即Hanoi Towers问题。通过构造起重整化群作用的群(Hanoi Towers群)，提出者设计了一个代数方法来解决这个问题。基于2个字母的3状态自动机群的完全分类是被期望的。自相似的概念是所有时间和种群的数学中最基本和最有成果的思想之一。在过去的几十年里，它确立了自己在诸如分形几何、动力系统和统计物理等领域的中心概念。最近，主要通过提出者及其合作者的工作，自相似也开始在代数中发挥作用，首先是在群论中。近年来，群论中与自相似研究有关的方法已成功地应用于解决许多数学上长期存在的公开问题和猜想(一般Burnside问题、关于增长的Milnor问题、关于可修饰性的Day-von Neumann问题、关于宽度有限的Zelmanov问题、Atiyah强猜想等等)。自动机群构成了一类自相似群，对自动机群的研究具有进一步延续这一积极趋势的无限潜力。除了在几个数学领域的基础研究方面的进展外，建议的研究还应用于计算机科学(扩展器是算法去随机化和可靠网络设计中不可或缺的工具)、编码和信息理论(自动机可以用来构造具有极好特性的代码)和组合博弈论(提出者使用有限自动机群对一些最突出的组合问题进行建模)。

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