Factorable Monoids: Resolutions and Homology via Discrete Morse Theory DISSERTATION zur Erlangung des Doktorgrades (Dr. rer. nat.) der Mathematisch-Naturwissenschaftlichen Fakult¨at der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn vorgelegtvon A l e x a n d e r H e ß aus Mannheim Bonn, M¨arz 2012 Angefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen Fakult¨at der Rheinischen Friedrich-Wilhelms-Universit¨at Bonn 1. Gutachter: Prof. Dr. Carl-Friedrich B¨odigheimer 2. Gutachter: Prof. Dr. Wolfgang Lu¨ck Tag der Promotion: 12. Juni 2012 Erscheinungsjahr: 2012 2 Zusammenfassung DieseArbeitistimBereichderkombinatorischeGruppen-bzw. Monoidtheorieeinzuord- nen. Fu¨r Monoide X, die mit einer sogenannten Faktorabilit¨atsstruktur versehen sind, konstruieren wir freie Aufl¨osungen von Z u¨ber dem Monoidring ZX, die deutlich kleiner sind als die Baraufl¨osung. Damit erweitern wir Resultate aus [Vis11] und [Wan11]. Wir geben außerdem einige Berechnungsbeispiele. Unser Hauptwerkzeug ist die diskrete Morsetheorie nach Forman [For98]. Faktorabilit¨at hat ihren Ursprung in der Berechnung von Homologiegruppen von Mo- dulr¨aumen Riemannscher Fl¨achen. Diese Modulr¨aume lassen eine rein kombinatorische Beschreibung durch symmetrische Gruppen zu, siehe [B¨od90], [B¨od], [Ebe], [ABE08]. Dadurch ist es mo¨glich, Homologiegruppen mit Hilfe von Computerprogrammen zu be- stimmen, so geschehen bspw. in [ABE08], [Wan11], [Meh11]. Bei diesen Berechnungen tritt ein interessantes Ph¨anomen zu Tage, na¨mlich kollabiert der Barkomplex der symmetrischen Gruppen zu einem deutlich kleineren Kettenkom- plex. Um diese Beobachtung zu erkl¨aren, fu¨hrt [Vis11] den Begriff der faktorablen Gruppe ein. EinefaktorableGruppeisteinTripelbestehendauseinerGruppeG,einemErzeugenden- system S sowie einer Faktorisierungsabbildungη : G→ G×S. Das Bild dasman hierbei vor Augen haben sollte ist, dass η von einem Gruppenelement einen Erzeuger abspaltet. In[Wan11]wirdeineVerallgemeinerung diesesBegriffsaufMonoidevorgeschlagen. Dort werden, aufbauend auf [Vis11], kleine Kettenkomplexe zur Berechnung der Homologie rechtsku¨rzbarer, faktorabler Monoide mit endlichem Erzeugendensystem konstruiert. Der von uns gewa¨hlte Zugang zu Faktorabilit¨at ist konzeptioneller. Dies erlaubt einer- seits, die Faktorisierungsabbildung η als diskrete Morsefunktion auf der Barauflo¨sung zu interpretieren. Daraus werden unter anderem geometrische und homologische Endlich- keitsaussagen gewonnen. Andererseits ermo¨glicht unsere Herangehensweise, faktorable Monoide in den Kontext von Termersetzungssystemen (siehe z.B. [Coh97]) einzuordnen. Der Aufbau dieser Arbeit ist wie folgt. In Kapitel 1 rekapitulieren wir ausfu¨hrlich diskrete Morsetheorie und einige ihrer Varianten. In Kapitel 2 geben wir unsere Defi- nition von faktorablem Monoid. Kapitel 3 zeigt, wie man aus Faktorabilit¨atsstrukturen “kleine” Aufl¨osungen gewinnt und wie dieses Resultat die Konstruktionen in [Vis11] und [Wan11] vereinheitlicht und verallgemeinert. In Kapitel 4 pra¨sentieren wir eine Anwendung und berechnen Homologiegruppen von sogenannten Thompsonmonoiden. Dies beinhaltet insbesondere eine Neuberechnung der Homologie der Thompsongruppe F selbst (vgl. [CFP96], [BG84]) sowie verwandter Gruppen F (vgl. [Bro92], [Ste92]). n,∞ 3 Contents Introduction 7 Preliminaries on monoids 17 1 Discrete Morse theory and rewriting systems 21 1.1 Discrete Morse theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.1.1 Simplicial collapse . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.1.2 Algebraic collapse . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.1.3 Labelled graphs and matchings . . . . . . . . . . . . . . . . . . . . 26 1.1.4 Based chain complexes and incidence graphs . . . . . . . . . . . . 28 1.1.5 Discrete gradient flow and invariant chains . . . . . . . . . . . . . 30 1.1.6 Reduced gradient flow and essential chains . . . . . . . . . . . . . 33 1.1.7 Historical Remarks & References . . . . . . . . . . . . . . . . . . . 37 1.2 Rewriting Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.2.1 Reminder on bar constructions . . . . . . . . . . . . . . . . . . . . 38 1.2.2 Noetherian matchings on the normalized bar resolution . . . . . . 42 1.2.3 Rewriting Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1.2.4 Brown’s proof of the Anick–Groves–Squier Theorem . . . . . . . . 44 1.3 A new proof of a Theorem by Charney–Meier–Whittlesey . . . . . . . . . 47 2 Factorability 53 2.1 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1.1 Generating sets and filtrations . . . . . . . . . . . . . . . . . . . . 53 2.1.2 Factorable groups . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.1.3 Weakly factorable monoids . . . . . . . . . . . . . . . . . . . . . . 59 2.1.4 The Visy complex . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.1.5 The recognition principle . . . . . . . . . . . . . . . . . . . . . . . 63 2.2 Factorable monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.2.1 Definition and classification . . . . . . . . . . . . . . . . . . . . . . 65 2.2.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 2.2.3 Finite sequences and monoid actions . . . . . . . . . . . . . . . . . 72 2.3 The monoids P and Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 n n 2.3.1 The monoids P . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 n 2.3.2 The monoids Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 n 2.3.3 Smallness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 2.3.4 A new description of κ . . . . . . . . . . . . . . . . . . . . . . . . 89 n 5 Contents 3 The Visy resolution 93 3.1 A noetherian matching on E X . . . . . . . . . . . . . . . . . . . . . . . . 93 ∗ 3.1.1 The matching µ and ZX-compatibility . . . . . . . . . . . . . . . . 93 3.1.2 Coherent sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.1.3 Noetherianity of µ . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.2 Computing the differential θ∞◦∂ . . . . . . . . . . . . . . . . . . . . . . . 103 3.2.1 Θ∞ and coherent sequences . . . . . . . . . . . . . . . . . . . . . . 103 3.2.2 Θ∞ and right-most, reduced, small sequences . . . . . . . . . . . . 106 3.3 Z-coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 3.3.1 The E1-page revisited . . . . . . . . . . . . . . . . . . . . . . . . . 113 3.3.2 κ is an isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . 117 3.4 Connection to Rewriting Systems . . . . . . . . . . . . . . . . . . . . . . . 118 4 Applications to generalized Thompson groups and monoids 125 4.1 Homology of groups via homology of monoids . . . . . . . . . . . . . . . . 125 4.2 Braid factorability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.2.1 The monoids Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 n 4.2.2 A class of braid factorable monoids . . . . . . . . . . . . . . . . . . 133 4.3 Thompson monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 t 4.3.1 Factorability of (p,q) . . . . . . . . . . . . . . . . . . . . . . . . 139 m t T 4.3.2 Embedding (p,q) into (p,q) . . . . . . . . . . . . . . . . . . 142 m m 4.4 Reducing the Visy complexes V t (p,q) . . . . . . . . . . . . . . . . . . . 144 ∗ m 4.4.1 Notational conventions . . . . . . . . . . . . . . . . . . . . . . . . . 145 4.4.2 Describing the differential ∂V . . . . . . . . . . . . . . . . . . . . . 146 ∗ 4.4.3 A perfect matching on V t (p,q) . . . . . . . . . . . . . . . . . . . 147 ∗ m 4.4.4 Perfectness of µ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 4.5 Homological results on Thompson monoids . . . . . . . . . . . . . . . . . 155 4.5.1 Homological dimension. . . . . . . . . . . . . . . . . . . . . . . . . 155 4.5.2 The homology of Thompson monoids . . . . . . . . . . . . . . . . . 156 t t 4.5.3 A remark on the monoids (1,q),..., (q,q) . . . . . . . . . . . 159 m m This research was funded by the Deutsche Forschungsgemeinschaft within the graduate program “Homotopy and Cohomology” (GRK 1150). 6 Introduction Group homology is an important invariant in many algebraically flavoured branches of mathematics. Thehomology of a groupG with coefficients in a ZG-moduleM is defined as H (G;M) := TorZG(Z;M), ∗ ∗ where Z has the trivial ZG-module structure. To compute these Tor-groups, we need to find a projective resolution of Z over ZG. The normalized inhomogeneous bar resolution E G, for short bar resolution of G, serves ∗ as such. Tensoring with Z, we obtain a well-known model for the homology of G, the bar complex B G := E G⊗ Z. As a Z-module, each B G is freely generated by tuples ∗ ∗ ZG n [g |...|g ] with g 6= 1 for all i. n 1 i In practice, the bar complex is too huge to do homology computations straight away. It is therefore convenient to take into account potential extra structureon G. For example, the existence of a finite complete rewriting system for G gives rise to a free resolution of Zoffinitetype, seee.g.[Ani86], [Squ87], [Gro90], [Bro92]andthesurveyarticles [NR93], [Coh97]. More specifically, in [CMW04] Garside structures are used to construct finite free resolutions. The notion of factorability should be considered as lying somewhere between Garside structures and complete rewriting systems. This will be made precise later. The upshot is that if G is equipped with a reasonable factorability structure, then one can explicitly write down a free resolution which is considerably smaller than the bar resolution and thus more amenable to computation. Before going into details, we briefly discuss a collapsing phenomenon that has first been observed for symmetric groups and that motivated the notion of factorability. Denote by S the k-th symmetric group. Let T ⊂ S be the generating set of all trans- k k positions. The word length ℓ with respect to T gives rise to a filtration by subcomplexes of the bar complex B S . More precisely, define F B S to be the Z-module freely ∗ k h n k generated by all tuples [σ |...|σ ] with σ 6= id and ℓ(σ )+...+ℓ(σ ) ≤ h. Since ℓ is n 1 i n 1 subadditive, the filtration levels F B S are indeed subcomplexes of B S . Note that h ∗ k ∗ k F B S = 0 for ∗ < 0 or ∗ >h. h ∗ k Thefollowing observation isdueto Visy[Vis11]. Itmarksthestartingpointofthestudy of factorability. 7 Introduction Proposition (Visy) The complex of filtration quotients F B S /F B S , h ∗ k h−1 ∗ k 0 //F B S /F B S //... //F B S /F B S //0 (∗) h h k h−1 h k h 0 k h−1 0 k has homology concentrated in top-degree ∗ = h. Let us reformulate this observation in terms of spectralsequences. F B S is an increas- • ∗ k ing filtration by chain complexes, and hence there is an associated homology spectral se- quence, cf. Weibel [Wei94, §5.4]. More precisely, we have E0 = F B S /F B S . p,q p p+q k p−1 p+q k Note that our spectral sequence lives in the fourth quadrant. The chain complexes of filtration quotients F B S /F B S in (∗) occur as (shifted) h ∗ k h−1 ∗ k columns(E0 ,d0 )of thisspectralsequence. Visy’s observation isthereforeequiva- h,∗−h h,∗−h lent to saying that the homology of each column is concentrated in degree 0. In particu- lar, the E1-page consists of a single chain complex (E1 ,d1 ), and our spectral sequence ∗,0 ∗,0 collapses on the E2-page. · · · · · · · · · · · · · · · · · · Sh·ifte·d co·mp·lex·of t·he · · · · · · · · · · · · h-thfiltrationquotients · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ∗ ∗ ∗ ∗ ∗ · · · · ∗ ∗ ∗ ∗ ∗ · · · · · · ∗ ∗ ∗ · · · · · · · · · · · · · · · · ∗ ∗ · · · · · · · · · · · · · · · · · ∗ · · · · · · · · · · · · · · · · · · · · · · · · · · · TheE0-page. The E1-page. Clearly, the complex (E1 ,d1 ) is a model for the homology of G, cf. Weibel [Wei94, ∗,0 ∗,0 §5.5], and it is considerably smaller than the bar complex. The notion of factorability has been introduced to explain this collapsing phenomenon andtogiveadescriptionofthecomplex(E1 ,d1 ). Wenowoutlinetheoriginaldefinition ∗,0 ∗,0 by Visy [Vis11]. A factorable group consists of the following data. A discrete group G, a generating set S ⊂ G which is closed under taking inverses, and a splitting map η : G → G × G, g 7→ (g,g′). The element g′ is called the prefix of g and g is called the remainder of g. Denote by ℓ the word length with respect to S. We say that η is a factorization map for the pair (G,S) if it satisfies the following axioms: (F1) g = g·g′. (F2) ℓ(g) = ℓ(g)+ℓ(g′). (F3) If g 6= 1 then g′ ∈ S. 8 We remark that if η is a factorization map, then iteratively applying η to the remainder we obtain a normal form, i.e. a section G → S∗ of the canonical projection S∗ → G, where S∗ denotes the free group over S. The triple (G,S,η) is called a factorable group if the factorization map η satisfies (gt)′ = (g′t)′ for all pairs (g,t) ∈G×S with ℓ(gt) = ℓ(g)+ℓ(t). This latter property should be regardedasacompatibility condition aboutprefixesof products. Theintuition behindit isthatfactorability assurestheexistenceofparticularly nicenormalforms. Forexample, if (G,S,η) is factorable, then the image of the induced normal form G → S∗ is closed under taking subwords. To get an idea of what this has to do with the spectral sequence situation, we remark that the factorization map η can be thought of as encoding a collapsing chain homotopy on each vertical complex (E0 ,d0 ). p,∗ p,∗ Ourprototypicalexample(S ,T),thek-thsymmetricgrouptogetherwiththegenerating k set of all transpositions, can be endowed with a factorability structure as follows. By (F2) we must have η(id) = (id,id). Let σ ∈ S be a non-trivial permutation and denote k bymitslargestnon-fixedpoint. Asprefixσ′ wetakethetranspositionτ = (m σ−1(m)). The remainder is then given by σ = σ ◦τ. For example, in cycle notation, (124) ∈ S 4 is mapped to ((12),(24)). Visy [Vis11] showed that (S ,T,η) is a factorable group. k Further interesting examples including alternating groups, dihedral groups and certain Coxeter groups can be found in the works of Ozornova [Ozo], Rodenhausen [Rod], [Rod11] and Visy [Vis11]. Also, free and direct products (or, more generally, graph products) as well as semidirect products of factorable groups are again factorable, cf. [Rod] and [Vis11]. We now briefly survey the results of Visy [Vis11] and Wang [Wan11] in findingsmall ho- mologymodelsforfactorablegroups. Recallfrompage8thespectralsequenceassociated to the generating set S for the group G. Theorem(Visy)If (G,S,η) isafactorable group thenthe homology of each vertical complex (E0 ,d0 ) is concentrated in degree 0. p,∗ p,∗ In other words, the E1-page of the spectral sequence consists of a single chain complex (E1 ,d1 ). To describe this complex, Visy introduces the complex (V ,∂V) together ∗,0 ∗,0 ∗ ∗ with an embedding of chain complexes κ: (V ,∂V) −→ (E1 ,d1 ). ∗ ∗ ∗,0 ∗,0 He also proves that κ is surjective for symmetric groups with the above factorability structure. Wang [Wan11] uses a clever counting argument to conclude the following: Theorem (Wang) Let (G,S,η) be a factorable group. If S is finite then κ is an isomophism. There is an obvious generalization of the notion of factorability to monoids, and Wang in loc. cit. points out that her Theorem still holds when the group G is replaced by a right-cancellative monoid. 9 Introduction The works of Visy and Wang investigate the homological behavior mentioned above from the perspective of factorability of groups or monoids. One aim of this thesis is to study factorability in a far broader context and to provide a conceptual treatment for it, putting it in perspective with rewriting systems and discrete Morse theory. To this end, we first equivalently reformulate factorability of groups in terms of actions of monoids P and Q . This point of view suggests a notion of factorability for monoids which is n n slightly stronger than the one used by Wang. The advantage of our approach is that now a factorability structure on a monoid gives rise to a discrete Morse function on its bar complex. A discrete Morse function f on a cell complex K assigns to every (open) cell of K a natural number, providing a partition of the cells of K into regular and critical ones. As in classical Morse theory, a discrete Morse function induces a discrete gradient flow, and along this flow we can collapse K onto a complex that is built up from the critical cells. This latter complex is called the discrete Morse complex associated to f. Here we are mostly interested in an algebraic version of discrete Morse theory, where the objects of study are based chain complexes. LargepartsofthisthesisaredevotedtostudyingtheMorsecomplexassociatedtothebar resolution and the bar complex of a factorable monoid. For example, as an immediate consequence, we obtain geometric and homological finiteness properties of factorable monoids. A more detailed analysis will reveal that our discrete Morse complex coincides with Visy’s complex (V ,∂V) and furthermore that, with our stronger notion of factorable ∗ ∗ monoid, the map κ is always an isomorphism. Moreover, we will find that κ has an interpretation in the world of discrete Morse theory. Note that here we are only concerned with one factorable group at a time. Another interesting direction in thestudy of factorability takes into account families of factorable groups. This has applications in the computation of the homology of moduli spaces of Riemann surfaces. Before discussing the organization of this thesis, let us briefly report on this connection. Let Fm be a Riemann surface of genus g with one boundary curve and m marked g,1 points (“punctures”). B¨odigheimer’s Hilbert Uniformization provides a finite double complex Q that computes thehomology of themodulispace Mm of Fm. Thisdouble •,• g,1 g,1 complex has a description in terms of the family of symmetric groups equipped with the aforementioned factorability structure. For further reading see [ABE08], [B¨od90], [B¨od], [Ebe], [Vis11], [Wan11]. Let (G(k),S(k),η(k)) be a factorable group for every k ≥ 0. Recall that for each of these factorable groups we have an associated spectral sequence, and we are now aiming for obtaining connecting homomorphisms between the respective E0-pages. To this end, we arrange the sets underlying the groups G(k) in a semisimplicial set. That is, for every 10