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

点击翻译按钮获取中文摘要

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