Mark V. Sapir with contributions by Victor S. Guba and Mikhail V. Volkov Combinatorial algebra: syntax and semantics Springer Ole, Жene, (cid:23)xe i Rзqel-Hanne 1 Contents 1 Main definitions and basic facts...................................... 11 1.1 Sets............................................................... 11 1.2 Words............................................................. 13 1.2.1 The origin of words .......................................... 13 1.2.2 The free semigroup .......................................... 14 1.2.3 Orders on words ............................................. 15 1.2.4 Periodic words............................................... 16 1.3 Graphs............................................................ 19 1.3.1 Basic definitions ............................................. 19 1.3.2 Automata................................................... 19 1.3.3 Mealy automata ............................................. 21 1.3.4 Graphs in the sense of Serre .................................. 22 1.3.5 Inverse automata and foldings ................................ 22 1.4 Universal Algebra .................................................. 23 1.4.1 Basic definitions ............................................. 23 1.4.2 Free algebras in varieties ..................................... 30 1.4.3 The Garrett Birkhoff theorem................................. 31 1.4.4 Relatively free algebras may not know their ranks. The J´onsson–algebras ............................................ 31 1.4.5 Locally finite varieties........................................ 32 1.4.6 The Burnside problem for varieties of algebras ................. 33 1.4.7 Finitely based finite algebras.................................. 34 1.4.8 Inherently non-finitely based finite algebras: the link between finite and infinite ............................................ 35 1.5 Growth of algebras ................................................. 40 1.6 Symbolic Dynamics ................................................ 41 1.6.1 Basic definitions ............................................ 41 1.6.2 Subshifts.................................................... 42 1.6.3 Edge subshifts............................................... 46 1.7 Rewriting systems.................................................. 47 1.7.1 Basic definitions ............................................. 47 1.7.2 Confluence .................................................. 47 1.7.3 What if a rewriting system is not confluent? The art of Knuth–Bendix............................................... 51 1.7.4 String rewriting.............................................. 52 3 1.8 Presentations of semigroups......................................... 55 1.8.1 Semigroups and monoids: basic definitions ..................... 55 1.8.2 Free and non-free semigroups ................................. 56 1.8.3 A characterizationof free semigroups.......................... 57 1.8.4 Congruences, ideals and quotient semigroups................... 57 1.8.5 String rewriting and presentations............................. 58 1.8.6 The free group. The syntactic definition ....................... 61 1.8.7 The free group and ping-pong................................. 61 1.8.8 Free groups and rings of formal infinite linear combinations ..... 63 1.8.9 The growth function, growth series and Church–Rosser presentations ................................................ 64 1.8.10 The Cayley graphs........................................... 65 1.8.11 Cayley graphs, transition monoids of automata and syntactic monoids of languages......................................... 66 2 Words that can be avoided........................................... 69 2.1 An old example .................................................... 69 2.2 Proof of Thue’s theorem ............................................ 70 2.3 Square-free words .................................................. 71 2.4 kth power-free substitutions......................................... 73 2.5 Avoidable words.................................................... 74 2.5.1 Examples and simple facts.................................... 74 2.5.2 Fusions, free sets and free deletions............................ 75 2.5.3 The Bean–Ehrenfeucht–McNulty & Zimin theorem ............. 76 2.5.4 Simultaneous avoidability..................................... 79 2.6 Further reading and open problems.................................. 79 2.6.1 Square- and cube-free words .................................. 79 2.6.2 Avoidable words ............................................. 80 3 Semigroups ........................................................... 81 3.1 Structure of semigroups............................................. 82 3.1.1 Periodic semigroups.......................................... 83 3.1.2 Periodic semigroups with exactly one idempotent............... 83 3.1.3 Finite nil-semigroups......................................... 84 3.2 Free semigroups and varieties ....................................... 86 3.2.1 Free Rees factor-semigroups .................................. 86 3.2.2 A description of relatively free semigroups ..................... 86 3.3 The Burnside problem for varieties .................................. 87 3.3.1 Subshifts and semigroups..................................... 89 3.3.2 An application of subshifts to semigroups...................... 91 3.3.3 The completion of the proof of Theorem 3.3.4.................. 94 3.4 Brown’s theorem and uniformly recurrent words ...................... 99 3.5 Burnside problems and the finite basis property....................... 100 3.6 Inherently non-finitely based finite semigroups........................ 101 3.6.1 Some advanced semigroup theory ............................. 101 3.6.2 A description of inherently non-finitely based finite semigroups .. 106 3.7 Growth functions of semigroups ..................................... 114 3.7.1 The definition ............................................... 114 3.7.2 Chebyshev, Hardy–Ramanujan and semigroups of intermediate growth...................................................... 116 4 3.8 Inverse semigroups ................................................. 121 3.8.1 Basic facts about inverse semigroups .......................... 121 3.8.2 Identities of finite inverse semigroups, Zimin words, and subshifts 122 3.8.3 Inverse semigroups of bi-rooted inverse automata............... 124 3.9 Subshifts and automata. The road coloring problem................... 125 3.9.1 Synchronizing automata...................................... 125 3.9.2 The road coloring problem.................................... 126 3.9.3 An application of the road coloring theorem to a classification of subshifts of finite type ..................................... 134 3.10 Further reading and open problems.................................. 138 3.10.1 Other applications of Burnside properties...................... 138 3.10.2 Free semigroups in periodic varieties. The Brzozowskiproblem .. 139 3.10.3 The finite basis problem for semigroups........................ 140 3.10.4 The Burnside problem for varieties of monoids ................. 141 3.10.5 Identities of finite inverse semigroups.......................... 141 3.10.6 Growth functions of semigroups............................... 142 3.10.7 The road coloring and the Cˇerny´ conjecture.................... 143 4 Rings ................................................................. 145 4.1 The basic notions .................................................. 145 4.2 Free associative algebras ............................................ 147 4.3 Commuting elements in free associative algebras over a field ........... 147 4.4 Burnside-type problems for associative algebras....................... 149 4.4.1 Preliminaries ................................................ 149 4.4.2 Shirshov’s height theorem .................................... 152 4.4.3 Growth function of a ring satisfying a nontrivial identity ........ 156 4.4.4 Inherently non-finitely based varieties of rings.................. 156 4.4.5 The Dubnov–Ivanov–Nagata–Higmantheorem ................. 156 4.4.6 Golod counterexamples to the Kurosh problem................. 158 4.4.7 Zimin words and the Baer radical ............................. 161 4.5 The finite basis problem ............................................ 163 4.5.1 Basic facts about finite associative rings ....................... 163 4.5.2 Positive result. Identities of finite rings ........................ 166 4.5.3 Negative result .............................................. 170 4.6 Further reading .................................................... 173 4.6.1 The Kurosh problem......................................... 173 4.6.2 Identities of rings ............................................ 174 5 Groups................................................................ 175 5.1 Van Kampen diagrams ............................................. 176 5.1.1 Group presentations ......................................... 176 5.1.2 Van Kampen diagrams: the definition ......................... 176 5.1.3 Van Kampen diagrams and tilings. An elementary school problem and its non-elementary solution....................... 179 5.1.4 The three main methods of dealing with van Kampen diagrams: bands, Swiss cheese, and small cancelation ..................... 181 5.2 The Burnside problems for groups ................................... 195 5.2.1 Golod’s counterexampleto the unbounded Burnside problemfor groups ...................................................... 195 5.2.2 The Bounded Burnside problem. Positive results ............... 195 5 5.2.3 The Novikov–Adiantheorem.................................. 197 5.3 The finite basis problem for groups and rings......................... 213 5.3.1 An example of R. Bryant and Yu. Kleiman..................... 213 5.3.2 Construction of the algebra R used in Section 4.5.3............. 218 5.4 Groups and identities, Ab´ert’s criterium.............................. 223 5.5 Subgroups of free groups............................................ 225 5.5.1 The definition of a 2-complex and its fundamental group........ 225 5.5.2 Subgroups of free groups and inverse automata................. 227 5.6 Diagram groups.................................................... 230 5.6.1 The Squier complex of a string rewriting system................ 230 5.6.2 Diagrams as 2-dimensional words, diagram groups.............. 230 5.6.3 Diagram groups and Squier complexes......................... 232 5.6.4 Diagram groups. Examples ................................... 233 5.6.5 Combinatorics on diagrams................................... 233 5.6.6 The R.Thompson group F .................................... 238 5.6.7 Multilinear identities of non-associative algebras and elements of F ........................................................ 243 5.6.8 F is lawless ................................................. 243 5.6.9 F does not have non-cyclic free subgroups ..................... 244 5.6.10 Two Church–Rosser presentations of F ........................ 245 5.7 Growth of groups .................................................. 247 5.7.1 Similar groups have similar growth............................ 247 5.7.2 Commutative groups......................................... 248 5.7.3 Nilpotent groups............................................. 250 5.7.4 Grigorchuk’s group of intermediate growth..................... 257 5.8 Amenable groups................................................... 262 5.8.1 The free groups of orthogonal matrices and the Hausdorff– Banach–Tarskiparadox ...................................... 263 5.8.2 The first two definitions of amenability ........................ 266 5.8.3 Følner sets .................................................. 268 5.8.4 Groups with Tarski number 4................................. 272 5.8.5 Co-growth and the von Neumann–Day conjecture .............. 273 5.9 Further reading and open problems.................................. 279 5.9.1 Further applications of Olshanskii’s method.................... 279 5.9.2 Syntactic properties of hyperbolic groups ...................... 279 5.9.3 Some semantic properties of small cancelation groups........... 281 5.9.4 Open problems about hyperbolic group........................ 281 5.9.5 The Hanna Neumann conjecture .............................. 282 5.9.6 Diagram groups ............................................. 282 5.9.7 The R. Thompson group F ................................... 283 5.9.8 The finite basis problem for varieties of groups ................. 284 5.9.9 Inherently non-finitely based varieties of groups ................ 284 5.9.10 Amenable groups ............................................ 285 References ................................................................ 289 6 Introduction What is this book about Analyzing proofs of results about various algebraicobjects (groups,semigroups,rings), it is easy to notice two types of results: syntactic results involving words, automata, languages,andsemanticresultsinvolvingalgebraicpropertiesofsubalgebrasandhomo- morphic images, geometric properties of certain associated objects (graphs, manifolds, and more complicated metric spaces), dynamical properties of associated actions, etc. One of the goals of this book is to demonstrate deep connections between syntax and semantics and show how syntax and semantics interact when we study fundamental questions concerning algebras.These include the Burnside-type questions (what makes an algebra finite?), the questions about growth (how large is an infinite algebra?), the finite basis question (can this class of algebras be nicely described?). Theinteractionbetweensyntaxandsemanticsismutuallybeneficial.Sometimessyn- tax “helps”semantics.Forexample combinatoricsofwordsandtheir 2-dimensionalim- ages-diagrams-helpssolveBurnside-typeproblemsandshowthatcertainsemigroups, groups and rings are infinite or finite. On the other hand semantic information about algebraicstructureshelpsprovingthattheyhaveordonothavefinitebasesofidentities. Sometimes in order to prove syntactic results one needs to study semantic properties of associated objects. For example, in order to describe “avoidable identities” of semi- groups, one needs semantic properties of subshifts associated with certain infinite sets of words. What is in the book The book has five chapters. The first chapter contains basic general definitions from algebra, language theory and symbolic dynamics that are used in the book. The main recurrent topics of this book: Burnside problems, growth of algebras, the finite basis property are also introduced there. The second and third chapters contain results about avoidable words and identities, includingthedescriptionofsemigroupvarietieswheretheBurnsideproblemhaspositive solution. Although the results are about words, the methods are semantic: with every infinite semigroup, one can associate a certain subshift, and recurrence properties of that subshift are used to establish algebraic properties of the semigroup. The third 7 chapter containsTrahtman’srecent(but alreadyfamous) proofof the oldroadcoloring conjecture by Adler, Goodwyn and Weiss. The conjecture has its origin in dynamical systemsbuttheproofisbasicallysyntacticandbelongsessentiallytosemigrouptheory. Thethirdchapteralsocontainsapplicationsofroadcoloringtoclassificationofsubshifts of finite type. ThefourthchapterisabouttheBurnsideandgrowthpropertiesforassociativerings, and a big part of the fifth chapter is devoted to the same properties for groups. Inparticular,Chapter4includes shortproofsofthecelebratedShirshovheighttheo- rem, the classical result by Dubnov, Ivanov, Nagata and Higman about local finiteness of rings satisfying nil identities, the Kruse–L’vov theorem about finite bases of iden- tities of finite rings, and Belov-Kanel’s counterexample for the Specht problem (that problem was one of the main problems that inspired the whole theory of varieties of rings). Gelfand–Kirillov dimension of associative algebras with polynomial growth is also considered there. Chapter 5 starts with showing how to convert words that are equal to 1 in a group into 2-dimensional pictures — van Kampen diagram and back. Greendlinger’s theo- remabout Dehn–Greendlinger’salgorithmfor smallcancellationgroupsis provednext, which is followed by a discussion of various syntactic properties of hyperbolic groups. Grigorchuk’s example of a group of intermediate growth (a solution of Milnor’s prob- lem) and the Bass–Guivarc’hcomputationof the growthfunctions of finitely generated nilpotentgroupsarealsointhatchapter.Thechapteralsoincludes,forthefirsttime in theliterature,a“roadmap”ofaproof(duetoOlshanskii)ofoneofthemostimportant results in grouptheory:the Novikov–Adiantheoremthat there are infinite finitely gen- erated groups of finite exponent. The main goalof the roadmap is to give the reader a relatively shortand gentle introduction (the main ideas, methods, and “points of inter- est”) to the very difficult originalproof. Chapter 5 ends with a section about amenable groups. In particular, a solution (due to Adian) of the von Neuman–Day problem is explained there. One of our goals in the book is to show that different algebraic objects have quite similarsyntacticfeaturesandarestronglyrelated.Inordertodothatweuseseveraltools andobjectsas“recurringcharacters”throughoutthebook.Forexample,fullbinarytrees areused in describingterms of free non-associativealgebras,inone of the definitions of the R. Thompson group F, and in the proof that Grigorchuk’s group has intermediate growth. Zimin words play a crucial role in studying Burnside properties of semigroups, in the definition of Baer radical in rings, etc. Zimin words even appeared, at least in spirit, in Olshanskii’s proof of the Novikov–Adian theorem (Section 5.2.3) and as Zel’manov’s words in one of the important applications of Zel’manov’s solution of the restrictedBurnside problem.Uniformly recurrentwords (which have originin symbolic dynamics)areusedtostudyBurnside-typeandfinitebasispropertiesofsemigroupsand inversesemigroups.FiniteautomataofseveralkindsaswellasChurch–Rosserrewriting systems also appear throughout the book. This book is not only about results but also about methods. There are several“uni- versal” methods used in many proofs in the book. For example, rewriting systems are oftenusedtofindcanonicalformsofwordsandotherobjects.Thediversityofintercon- nected subjects discussedin the book is manifestedin the fact that this is one ofa very few books where both the ergodic theorem of George Birkhoff and the HSP theorem of Garrett Birkhoff are used (Theorems 3.9.14 and 1.4.27). 8 What is not in the book The main purpose of the book is to cover the foundations of combinatorialalgebraand several important applications. The largest area that is barely touched in the book is “Algorithmic problems in algebra”, in particular the word problem. The reason is that the area is so large that it requires a separate book (the survey by Kharlampovichand Sapir [178] is 250 pages long and does not even mention the most important results in the area obtained during the last 15 years). For whom is the book written I have tried to make the book self-contained.Basically any undergraduate student who tookstandardLinearAlgebraandAbstractAlgebraclassescanreadthisbook.Itaught courses based on this book for undergraduate as well as graduate students, and even a 6–week course on avoidable words (Chapters 1, 2, 3) for high school students in one of the Canada/USA Mathcamps. In short, no significant knowledge of mathematics is required. Nevertheless problem solving experience and certain mathematical maturity would definitely help reading the book. Exercises Thebookcontainsmorethan350exercises.Someofthemareeasy,othersarerelatively hard. Although I do not provide solutions,harder exercisescontainhints, which should helpfindsolutions.InsomecasesIdecidedthatitwouldbeinstructivetoletthereader prove a theorem on his/her own, so the proof is divided into a series of exercises, each of which is not too difficult. Also quite often I formulate a statement that is almost, but not quite, obvious. After such a statement I write “why?” or “prove it!”. These are little exercises,which help, I hope, understand the proofs better. These usually replace the phrases like “It is easy to see that...” and ”By a straightforward computation we obtain ...”, which are often used in mathematical texts and which I find intimidating. Theexercises“embedded”intheproofsinthebookcontaintechnicalstatementswhose proofscanbeskippedifthereaderwantstolearnthemainideasoftheproofsasopposed toallthedetailsofit.IfIgavedetailedproofsofalltheexercises,thebookwouldbecome twice or three times as long while containing essentially the same information. Further reading and open problems Chapters2-5endwithsections“Furtherreadingandopenproblems”.Thesearesurveys ofmainrecentresultsandopenproblemsintherelevantareas.Eachoftheopenproblem formulated there can be a topic of a PhD thesis. Acknowlegement. I would like to thank Miklos Ab´ert, Laurent Bartholdi, Alexei Belov-Kanel, George Bergman, Mikhail Ershov, Rostislav Grigorchuk, Yves Guivarc’h, 9