{'fraction_non_alphanumeric': 0.06084925106499931, 'fraction_numerical': 0.015844441390682973, 'mean_word_length': 3.5399588246303573, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 39, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The cohomology ring of the real locus of the moduli space of stable curves of genus 0 with marked points

We compute the Poincare polynomial and the cohomology algebra with rational coefficeints of the manifold M_n of real points of the moduli space of algebraic curves of genus 0 with n labeled points. This cohomology is a quadratic algebra, and we conjecture that it is Koszul. We also compute the 2-local torsion in the cohomology of M_n. As was shown by E. Rains in arXiv:math/0610743 the cohomology of M_n does not have odd torsion, so that the above determines the additive structure of the integral homology and cohomology. Further, we prove that the rational homology operad of M_n is the operad of 2-Gerstenhaber algebras, which is closely related to the Hanlon-Wachs operad of 2-Lie algebras (generated by a ternary bracket). Finally, using Drinfeld's theory of quantization of coboundary Lie quasibialgebras, we show that a large series of representations of the quadratic dual Lie algebra L_n of H^*(M_n,Q) (associated to such quasibialgebras) factors through the the natural projection of L_n to the associated graded Lie algebra of the prounipotent completion of the fundamental group of M_n. This leads us to conjecture that the said projection is an isomorphism, which would imply a formula for lower central series ranks of the fundamental group. On the other hand, we show that the spaces M_n are not formal starting from n=6.


Introduction
Let M 0,n be the Deligne-Mumford compactification of the moduli space of algebraic curves of genus 0 with n labelled points. It is a smooth projective variety over Q ( [DM]) which parametrizes stable, possibly singular, curves of genus 0 with n labelled points. The geometry of this variety is very well understood; in particular, the cohomology ring of the manifold of complex points M 0,n (C) was computed by Keel [Keel], who also showed that it coincides with the Chow ring of M 0,n .
In this paper we will be interested in the topology of the manifold M n := M 0,n (R) of real points of this variety. There are a number of prior results concerning the topology of this manifold. Kapranov and Devadoss ([Kap], [Dev]) found a cell decomposition of M n , and Devadoss used it to determine its Euler characteristic. Davis-Januszkiewicz-Scott ([DJS]) found a presentation of the fundamental group Γ n of M n and proved that M n is a K(π, 1) space for this group. Nevertheless, the topology of M n is less well understood than that of M 0,n (C). In particular, the Betti numbers of M n have been unknown until present.
1.1. The cohomology of M n . In this paper, we completely determine the cohomology of M n with rational coefficients. In Definition 2.1, we give a presentation of the cohomology algebra H * (M n , Q) by generators and relations. Later in Theorem 6.4, we give a basis of this algebra and use this show that its Poincaré series equals P n (t) = 0≤k<(n−3)/2 (1 + (n − 3 − 2k) 2 t).
In particular, we show that the rank of H 1 (M n ) is n−1 3 which answers a question of Morava, [Mo,p.5]. 1 The variety M 0,n , and hence the manifold M n , has an action of the symmetric group S n which permutes the labelled points. In a subsequent paper, E.R. [R1] computes the character of the action of S n on H * (M n , Q).
The manifolds M n are not orientable for n ≥ 5, and in particular their cohomology groups are not free and contain 2-torsion. We determine the 2torsion in the cohomology, and show there is no 4-torsion. The cohomology of M n does not have odd torsion (this has been recently shown by E.R. [R2]), so our results give a description of the cohomology H * (M n , Z). Note that since M n is a K(π, 1)-space, this cohomology is also the cohomology of the group Γ n .
The description of the cohomology of M n has recently been generalized by E.R. [R2] to a computation of the integral homology of the real points of any de Concini-Procesi model coming from any real subspace arrangement (the manifold M n comes from the A n−2 hyperplane arrangement).
1.2. The operad structure. The collection of spaces M n forms a topological operad, since stable curves of genus 0 can be attached to each other at marked points, as described in section 2.4. Similarly, the homology H * (M n , Q) is an operad in the symmetric monoidal category of Z-graded Q-supervector spaces. This operad was first discussed by Morava [Mo], who suggested that it might be related to symplectic topology. Understanding this operad was one of the primary motivations for this work.
In Theorem 2.14, we show that this operad generated by a supercommutative associative product ab of degree 0 and skew-supercommutative ternary "2-bracket" [a, b, c], such that the 2-bracket is a derivation in each variable and satisfies a quadratic Jacobi identity in the space of 5-ary operations. Motivated by the Hanlon-Wachs theory of Lie 2-algebras [HW], we call this the operad of 2-Gerstenhaber algebras.
The structure of the homology operad of M 0,n (C) was determined by Konstevich and Manin ( [KM2], see also [Ge]); in this case the operad (called the operad of hypercommutative algebras) turns out to be infinitely generated.
1.3. The analogy with braid groups. We see that the space M 0,n (R) has very different topological properties from those of M 0,n (C). Indeed, M 0,n (R) is K(π, 1), its Poincaré polynomial has a simple factorization, its Betti numbers grow polynomially in n, and its homology is a finitely generated operad. In contrast, M 0,n (C) is simply connected, its Poincaré polynomial does not have a simple factorization, its Betti numbers grow exponentially, and its homology operad is infinitely generated.
On the other hand, the properties of the configuration space C n−1 = C n−1 ∆ of n − 1-tuples of distinct complex numbers are much more similar to those of M 0,n (R). It is a K(π, 1) space with Poincaré polynomial (1 + t) · · · (1 + (n − 2)t), so its Betti numbers grow polynomially. Also its homology operad is well known to be the operad of Gerstenhaber algebras, which has two binary generators. The analogy between M n and C n−1 and between their fundamental groups (the pure cactus group Γ n and the pure braid group P B n−1 ), discussed already in [Dev], [Mo], and [HK], is very useful and has been a source of inspiration for us while writing this paper.
1.4. The Lie algebra L n . One application of the computation of the cohomology ring is that it allows us to understand various Lie algebras associated to the group Γ n .
The cohomology algebra H * (M n , Q) is a quadratic algebra and thus we can consider its quadratic dual algebra U n , which is the universal enveloping algebra of a quadratic Lie algebra L n . Since we have a presentation of Λ n , we get a presentation of L n (see Proposition 3.1).
On the other hand, one can construct a Lie algebra L n directly from Γ n , by taking the associated graded of lower central series filtration and then quotienting by the 2-torsion. In Theorem 3.9, we construct a surjective homomorphism of graded Lie algebras ψ n : L n → L n . We expect that this homomorphism is actually an isomorphism, similarly to the braid group case.
We also expect that the algebra U n is Koszul. On the other hand, somewhat disappointingly, we show that for n ≥ 6 the Malcev Lie algebra of Γ n is not isomorphic to the degree completion of L n ⊗ Q, and in particular the spaces M n for n ≥ 6 are not formal. This fact reflects an essential difference between the pure cactus group and the pure braid group.
1.5. Relation to coboundary Lie quasibialgebras and quasiHopf algebras. The motivation for the conjecture that the map ψ n is an isomorphism comes from the theory of coboundary Lie quasibialgebras. Let g be a Lie algebra over a field of characteristic zero, with a coboundary Lie quasibialgebra structure ϕ ∈ (∧ 3 g) g ( [Dr1]). Let X 1 , · · · , X n−1 be representations of g. From the explicit form of generators and relations for L n , we show that L n acts on X 1 ⊗ · · · ⊗ X n−1 (see section 3.8).
On the other hand, Drinfeld showed in [Dr1] that any coboundary Lie quasibialgebra can be quantized to a coboundary quasiHopf algebra. The representation category of such a quasiHopf algebra is a coboundary category. The group Γ n acts on a tensor product Y 1 ⊗ · · · ⊗ Y n−1 in any coboundary monoidal category (see [HK] and section 3.4). From this, we get an action of L n on X 1 ⊗ · · · ⊗ X n−1 .
Theorem 3.12 shows that the action of L n on X 1 ⊗ · · · ⊗ X n−1 factors through the morphism ψ n and this action of L n .
The above statements are direct analogs of the corresponding results for pure braid groups and quasitriangular Lie quasibialgebras, as developed by Drinfeld in [Dr1,Dr2]. Moreover, the entire action of the braid group on tensor products can be recovered as the monodromy of the Knizhnik-Zamolodchikov connection. However, because of the non-formality of M n , at the moment we are pessimistic about the existence of an analogous result in our case.
1.6. Organization. The paper is organized as follows. Section 2 contains the statements of the main theorems describing H * (M n , Q). In section 3 we give additional results and conjectures, mostly concerning the Lie algebra L n . Section 4, 5 and 6 are devoted to the proof of the main theorem. First, in section 4, we prove that a certain algebra related to H * (M n , Q) has a basis indexed by "basic triangle forests" (combinatorial objects we introduce for this purpose). In section 5, we recall Keel's description of H * (M 0,n (C), Z) and use it to give an upper bound on the ranks of H * (M n , Q). Finally in section 6, we prove our main results concerning the cohomology ring of M n . in part by NSF Grant No. DMS-0401387. J.K. thanks the mathematics department of EPFL for hospitality. The work of J.K. was supported by NSERC and AIM. Finally, we would like to mention that at many stages of this work we made significant use of the Magma computer algebra system for algebraic computations.
2. The cohomology ring and the homology operad 2.1. The algebra Λ n . We begin by introducing an algebra which will turn out to be equal to the cohomology ring of M n over Q.
Definition 2.1. Λ n is the skew-commutative algebra generated over Z by elements ω ijkl , 1 ≤ i, j, k, l ≤ n, which are antisymmetric in ijkl, with defining relations (2.1) ω ijkl + ω jklm + ω klmi + ω lmij + ω mijk = 0, for any distinct i, j, k, l, m, p, In particular, Λ n is quadratic. We will also consider the algebras Λ n ⊗ R for commutative rings R. They are defined over R by the same generators and relations.
Remark. One can show (by a somewhat tedious calculation, which we did using the program "Magma") that 2 times (2.3) is in the ideal generated by (2.1) and (2.2). So this relation becomes redundant if 1/2 ∈ R.
The algebra Λ n has a natural action of S n .
Proof. An isomorphism Λ n [1] → ∧ 3 h n is given by We now switch to a different presentation of Λ n . In this presentation only the S n−1 -symmetry, rather than the full S n -symmetry, is apparent. However the presentation only contains quadratic relations.
Proposition 2.3. The algebra Λ n is isomorphic (in a natural way) to the skew-commutative algebra generated by ν ijk , 1 ≤ i, j, k ≤ n − 1 (antisymmetric in ijk) with defining relations Proof. Let Λ ′ n be the algebra defined as in the proposition. Define a homomorphism f : Λ ′ n → Λ n by the formula ν ijk → ω ijkn . By directly manipulating the relations, it is easy to see that this homomorphism is well defined. Using the 5-term linear relation (2.1), we can find an inverse for f . Thus f is an isomorphism.
The proof of this theorem is given in Section 6.
2.2. The real moduli space.
2.2.1. Stable curves. Recall [DM] that a stable curve of genus 0 with n labeled points is a finite union C of projective lines C 1 , ..., C p , together with labeled distinct points z 1 , ..., z n ∈ C such that the following conditions are satisfied (i) each z i belongs to a unique C j ; (ii) C i ∩ C j is either empty or consists of one point, and in the latter case the intersection is transversal; (iii) The graph of components (whose vertices are the lines C i and whose edges correspond to pairs of intersecting lines) is a tree; (iv) The total number of special points (i.e. marked points or intersection points) that belong to a given component C i is at least 3. So a stable curve must have at least 3 labeled points. A stable curve with 8 marked points.

6
An equivalence between two stable curves C = (C 1 , ..., C p , z 1 , ..., z n ) and C ′ = (C ′ 1 , ..., C ′ p , z ′ 1 , ..., z ′ n ) is an isomorphism of algebraic curves f : C → C ′ which maps z i to z ′ i for each i. Thus f reduces to a collection of p fractional linear maps f i : where σ is a permutation. It is easy to see that any equivalence of C to itself is the identity.
Over the real numbers, the projective lines are circles, so a stable curve is a "cactus-like" structure -a tree of circles with labeled points on them.
2.2.2. The moduli space M n . For n ≥ 3, let M n be the real locus of the Deligne-Mumford compactification of the moduli space of curves of genus zero with n marked points labeled 1, ..., n. In other words, M n is the set of equivalence classes of stable curves of genus 0 with n labeled points defined over R. Clearly, M n carries a natural (non-free) action of S n .
(i) M 3 is a point. (ii) M 4 is a circle. More precisely, the cross-ratio map defines an isomorphism M 4 → RP 1 . (iii) M 5 is a compact connected nonorientable surface of Euler characteristic −3, i.e. the connected sum of 5 real projective planes (see [Dev]).
The following theorem summarizes some of the known results about M n .
(i) M n is a connected, compact, smooth manifold of dimension n − 3. (ii) The Euler characteristic of M n is 0 for even n and Part (i) is well-known and appears in [Dev] and [DJS]. Part (ii) is due to Devadoss (see [Dev,Theorem 3.2.3]) and Gaiffi (see [Gai]) and comes from understanding the natural cell structure on M n . Part (iii) is due to Davis-Januszkiewicz-Scott [DJS]. It is proven by showing that M n is a Cat(0)-space.
2.3. The cohomology of M n . Let us now formulate the main result of this paper. To do so, note that for any ordered m-element subset S = {s 1 , ..., s m } of {1, ..., n} we have a natural map φ S : M n → M m , forgetting the points with labels outside S. More precisely, given a stable curve C with labeled points z 1 , ..., z n , φ S (C) is C with labeled points z s 1 , ..., z sm , in which the components that have fewer than 3 special points have been collapsed in an obvious way.
Thus for any commutative ring R we have a homomorphism of algebras φ * S : H * (M m , R) → H * (M n , R). For m = 4, M m is a circle, and we denote by ω S the image of the standard generator of H 1 (M 4 Proposition 2.7. Over any ring R in which 2 is invertible, the elements ω S satisfy the relations (2.1), (2.2).
Proof. It is sufficient to consider the case R = Z[1/2]. The skew-symmetry of ω S is obvious. Next, we check the quadratic relations (2.2). By considering the maps φ S for |S| = 5, it suffices to check this relation on M 5 . But H 2 (M 5 , Z) = Z/2Z because M 5 is non-orientable, so by the universal coefficient theorem The 5-term linear relation (2.1) may also be checked on M 5 . Since H 1 (M 5 , Z) is free over Z, it is sufficient to check the relation after tensoring with Q. As an S 5 -module, H 1 (M 5 , Q) is the tensor product of the permutation and sign representations. In particular, the 5-cycle has no invariants in this representation, and hence the 5-term relation holds.
Corollary 2.8. For any ring R in which 2 is invertible, we have a homomorphism of algebras Our main result is the following theorem.
Theorem 2.9. f Q n is an isomorphism. It then follows from Theorem 2.4 that the Poincaré polynomial of M n is P n (t). In the process, we also prove the following result. A description of the 2-torsion in H * (M n , Z) (which happens to be quite big) is given in Section 5.
The absence of 4-torsion in H * (M n , Z) allows us to sharpen the above statements as follows.
For any abelian group A, we denote by A 2 the 2-torsion in A.
Proposition 2.11. Over any ring R, the elements ω S satisfy the relations (2.1), (2.2), and (2.3) modulo 2-torsion. Hence, we have a homomorphism of algebras Proof. It is sufficient to consider the case R = Z. Relations (2.1) and (2.2) modulo 2-torsion are proved in the same way as in the case when 1 2 ∈ R. It remains to prove (2.3). Although the relation (2.3) is not in the ideal generated by the other relations (over Z), if we multiply it by 2, we obtain an element of this ideal, and thus the relation holds modulo 4-torsion. Since by Theorem 2.10, H * (M 6 , Z) has no 4-torsion 2 , the result follows. Now Theorem 2.9 can be strengthened as follows. Let Z 2 be the ring of 2-adic integers (we could equivalently consider the ring of 2-local integers).
Theorem 2.12. f Z 2 n is an isomorphism. In fact, one has the following stronger result.
Theorem 2.13. ( [R2]) H * (M n , Z) does not have odd torsion. In particular, f Z n is an isomorphism.
Remark. This theorem was conjectured in the first version of the present paper, on the basis of a computation by A.H. and John Morgan, who checked, using the blowup construction of M n , that the theorem holds for n ≤ 8. This conjecture was recently proved by E.R. as a special case of the main theorem of [R2].
2.4. The operad structure on the homology of M n . The spaces M n form a topological operad which was first studied by Devadoss, who called it the mosaic operad [Dev]. To define this operad, it is convenient to agree that each of the undefined moduli spaces M 1 and M 2 consists of one point. We will define a topological operad with a space of n-ary operations M (n) := M n+1 . We think of a point of M n+1 as an n-ary operation where the inputs sit at points 1, ..., n and the output is n + 1. The operad structure is defined by attaching curves at marked points. More explicitly, given p, q ≥ 0 and 1 ≤ j ≤ p, we have a "substitution" map γ jpq : M p+1 × M q+1 → M p+q given by attaching a curve C 1 with p + 1 marked points to a curve C 2 with q + 1 marked points by identifying the point j on the first curve with the point q + 1 on the second curve, and then adding q − 1 to the labels j + 1, . . . , p + 1 on C 1 and adding j − 1 to the labels of the points 1, ..., q on C 2 . The operad structure is obtained by iterating such maps.
Recall that a cyclic operad (see [GK]) is an operad P (•) in which the action of S n on P (n) extends to an action of S n+1 , compatible with the operad structure. In our case, S n+1 acts on M (n) = M n+1 in a natural way and thus M (•) is a cyclic operad.
Remark. For clarity, let us separately discuss special cases of the substitution map when p or q ≤ 1. If q = 1, or p = 1, γ jpq is the identity map. If q = 0, γ jpq : M p+1 → M p is the map of erasing the i-th point.
Since M (•) is a topological operad, the spaces O(n) := H * (M n+1 , Q) = (Λ n+1 ⊗ Q) * form an operad in the category of Z-graded supervector spaces. The following result determines the structure of this operad.
Algebras over this operad can be thought of as Lie 2-algebras with some additional structure. More precisely, we have the following result. Let Σ be the sign operad, which was introduced by Ginzburg-Kapranov [GiK]. Let HW denote the Hanlon-Wachs operad of Lie 2-algebras (see [HW]). It it generated by a skew-symmetric ternary operadtion satisfying the Jacobi identity Alt(τ • (τ ⊗ Id ⊗ Id)) = 0.
Remark. The reason for tensoring with Σ is that Hanlon and Wachs consider an odd supersymmetric ternary operation, while we need an odd superalternating ternary operation. As a result, the S n -representation on O ′ (n) is the tensor product of the S n representation on the Hanlon-Wachs operad HW (n) with the sign representation. However, the notions of O ′ -algebra and HW -algebra are essentially equivalent: one can go from one to the other by shifting by 1 the underlying Z-graded super vector space. Such a twisted version is briefly mentioned in the beginning of [HW].

2.5.
A few words on the proofs. Theorems 2.12 and 2.14 are proved simultaneously in section 6. The main idea is as follows, though for simplicity we give this outline over Q. First, in section 4, we introduce a twisted version of the ring Λ n . We find a basis for this ring and find its Hilbert series (Corollary 4.16). Then in section 5, we use known results about the cohomology of the complex moduli space in order to give an upper bound on the Betti numbers of M n (Corollary 5.8). In turns out that this upper bound exactly matches the dimensions of the graded pieces of Λ n . Hence the map f Q n : Λ n ⊗ Q → H * (M n , Q) is between two graded rings with the dimensions of the left side bounding the dimensions of the right side. So it suffices to prove that f n is injective. To do this, we use the operad structure on H * (M n , Q) to construct elements of H * (M n , Q) which pair "uppertriangularily" with the images under f n of our basis for Λ n .

Results and conjectures concerning Lie algebras
In this section we study the interplay between the cohomology ring of M n , its fundamental group Γ n , and theory of coboundary quasibialgebras. Of main interest to us are different Lie algebras which one can associate to the manifold M n and to its fundamental group Γ n . Much of what we do here is inspired by similar constructions of Kohno and Drinfeld in the configuration space/braid group setting.
3.1. The quadratic dual to Λ n and the Lie algebra L n .
Proposition 3.1. The quadratic dual Λ ! n of Λ n is the algebra U n generated over Z by µ ijk , 1 ≤ i, j, k ≤ n, which are antisymmetric in ijk, with defining relations (with the obvious action of S n−1 which extends to an action of S n ).
Proof. The equivalence of the first and second presentations of U n follows immediately by solving the linear relations for µ ijn .
To show that the algebra U n is dual to Λ n , it is convenient to use the S n−1invariant presentation of Λ n , which does not have linear relations. Recall Then the relations of Λ ! n are given by the formula [Ω, Ω] = 0. The above relations of U n are obtained from this equation by a direct calculation.
Let L n be the Lie algebra over Z generated by µ ijk with relations as above; we have U n = U (L n ). Thus, L n ⊗ Q is the rational holonomy Lie algebra of M n in the sense of Chen, see [PS].
Recall that a Z + -graded algebra A over a field k with Conjecture 3.2. The algebra Λ n ⊗ Q (or, equivalently, U n ⊗ Q) is Koszul. In particular, U n ⊗ Q has Hilbert series The second statement follows from the first by a general result about Koszul algebras.

Remarks.
(i) This conjecture is true for n ≤ 6, as in those degrees Λ n has a quadratic Gröbner basis, so is Koszul. (ii) The Hilbert series formula has been verified computationally in degree 3 for n ≤ 9.
Conjecture 3.3. U n and L n are free Z-modules.
Remark. Let A be a Z + -graded algebra over Z such that A[i] are finitely generated free Z-modules for all i. One may define A to be Koszul if for each j ≥ 1, Ext j A (Z, Z) is a free Z-module living in degree j. This is equivalent to saying that the algebras A/pA are Koszul for all primes p. Thus we may strengthen Conjectures 3.2 and 3.3 by conjecturing that Λ n and U n are Koszul over Z.

3.2.
Inductive nature of L n . Computations using the "Magma" program suggest that the nonconstant coefficients of the series P ! n (t)/P ! n+1 (t) are all negative and that the virtual is actually a character in all degrees. This suggests the following additional conjecture.

Conjecture 3.4.
(i) The kernel of the natural morphism U n+1 → U n (sending µ ijn to zero and µ ijk to themselves for i, j, k < n) is a free U n+1 -module.
(ii) The kernel of the natural morphism L n+1 → L n is a free Lie algebra (with infinitely many generators).
We note that the two statements of the conjecture become equivalent after extension of scalars from Z to Q. This follows from the following lemma.
Lemma 3.5. Let L be a N-graded Lie algebra acting on another N-graded Lie algebra F , both having finite dimensional graded pieces, and let L ⋉ F be their semidirect product. Then the following conditions are equivalent.
(i) F is a free Lie algebra.
Indeed, the equivalence follows by applying the Lemma for L = L n , F = ker(L n+1 → L n ) and L ⋉ F = L n+1 .
If F is a free Lie algebra, then it is freely generated by a graded subspace This implies that F is generated by G as a Lie algebra, and hence (by the Hilbert series consideration) that F is freely generated by G. Thus (ii) implies (i).
Remark. Note that since P ! n (t)/P ! n+2 (t) = 1 − (n − 1) 2 t, it is tempting to make a much more simple-looking conjecture, namely that the kernel of the homomorphism L n+2 → L n is a free Lie algebra generated by (n − 1) 2 generators in degree 1. This, unfortunately, is very far from being true, since the graded S n -character of the kernel of this homomorphism is not the same as that of a free Lie algebra (and in particular 1 − P ! n (g, t)/P ! n+2 (g, t) is a virtual character, which is not a character, and is not concentrated in degree 1).
3.3. The rational K(π, 1)-property. A connected topological space X is said to be rational K(π, 1) if its Q-completion is a K(π, 1)-space ( [BK]). Note that a K(π, 1)-space in the usual sense may not be a rational K(π, 1) space (e.g., the complement of the complex hyperplane arrangement of type D n ).
It is proved in [PY], Proposition 5.2, that for a connected topological space X with finite Betti numbers, if H * (X, Q) is a Koszul algebra then X is a rational K(π, 1) space. Thus Conjecture 3.2 implies Conjecture 3.6. The space M n is rational K(π, 1) in the sense of [BK].
It is also shown in [PY] that the Koszul property of H * (X, Q) and the rational K(π, 1) property of X are equivalent if X is a formal space. However, as we show below, the spaces M n are not formal for n ≥ 6.
3.4. The fundamental group Γ n of M n and coboundary categories. Let Γ n be the fundamental group of M n . To understand this group, we consider another group J n which is the orbifold fundamental group of the orbifold M n+1 /S n (the group S n leaves the point n + 1 fixed). There is a short exact sequence Furthermore, it is explained in [Dev, DJS, HK] that the group J n has the following presentation: it is generated by elements s p,q , 1 ≤ p < q ≤ n, with defining relations (i) s 2 p,q = 1; The above map J n → S n is defined by sending s p,q to the involution that reverses the interval [p, q] and keeps the indices outside of this interval fixed. The group J n is called the "cactus group" and it is analogous to the braid group.
One significance of this group J n comes from the theory of coboundary monoidal categories. Recall ( [Dr1], see also [HK]) that a coboundary monoidal category is a monoidal category C together with a commutor mor- (for simplicity we drop the associativity isomorphisms, assuming that the category is strict, and write c X, Let C be such a category, and let X 1 , . . . , X n be n objects in C. Then, as shown in [HK], every element g of the group J n defines a morphism X 1 ⊗ · · · ⊗ X n → X g(1) ⊗ · · · ⊗ X g(n) (here g(i) is the action of the image of g in S n on the index i). Namely, s p,q acts by The action of the cactus group on tensor products in coboundary monoidal categories is analogous to the action of the braid group on tensor products in braided monoidal categories.
For 1 ≤ p ≤ q < r ≤ n, let σ p,q,r = s p,r s p,q s q+1,r (we agree that s pp = 1). Clearly, such elements generate J n . The element σ p,q,r acts on X 1 ⊗ · · · ⊗ X n by c Xp⊗···⊗Xq,X q+1 ⊗···⊗Xr , and its inverse is given by σ −1 p,q,r = σ p,p+r−1−q,r . Now for 1 ≤ p ≤ q < r < m ≤ n, define b p,q,r,m = σ −1 p,q,r σ −1 p+r−q,r,m σ p,q,m It is easy to see that b p,q,r,m ∈ Γ n . It acts on the tensor product X 1 ⊗· · ·⊗X n by the morphism The significance of these elements is the following result.
Proposition 3.7. The conjugates of b p,q,r,m generate Γ n .
Proof. Consider the quotient G of J n−1 by the relations b p,q,r,m = 1. We claim that G is isomorphic to S n−1 . To show this, note that σ p,q,m for m > p + 1 can be expressed in G via elements Thus the group G is generated by σ p,p,p+1 = s p,p+1 , which are easily shown to satisfy the braid relations, as desired. Hence Γ n is generated by the conjugates of b p,q,r,m .
3.5. The first homology of M n .
Theorem 3.8. One has H 1 (M n Proof. For every triple i, j, k of distinct indices between 1 and n − 1, we have a submanifold of D ijk of M n (of codimension 1) which is the closure of the set of curves with two components, one containing the points i, j, k and the other containing the remaining labeled points. This submanifold is naturally isomorphic to M 4 × M n−2 = S 1 × M n−2 . The circle S 1 has a natural orientation, which depends on the cyclic ordering of i, j, k. Let µ ijk denote the image in H 1 (M n , Z) of the fundamental class of this circle. It is easy to see that µ ijk are skew-symmetric in the indices and are permuted in an obvious way by S n−1 . Let ν ijk ∈ H 1 (M n , Q) be the images of ν ijk under the map (2.4). Recall the map φ S from section 2.3. The composite and is constant otherwise. It follows that µ S , ν S ′ = ±δ S,S ′ and that the µ ijk are linearly independent over Q. It remains to show that the µ ijk for 1 ≤ i, j, k < n span H 1 (M n , Z)/H 1 (M n , Z) 2 (note that they do not span H 1 (M n , Z) which has a very big 2-torsion). To do so we will use the structure of the fundamental group Γ n .
By Proposition 3.7, the images of the b p,q,r,m in Γ n /[Γ n , Γ n ] generate Γ n /[Γ n , Γ n ]. So it suffices to show that each [b p,q,r,m ] can be written as a linear combination of the µ ijk . We claim that If n = 4, then Γ n = Z and the equality is exact (with only one term in the sum). If n = 5, then H 1 (M n , Z) = Z 4 ⊕ F 2 (since M 5 is the connected sum of 5 real projective planes) and it's therefore enough to check (3.2) over Q. To do so, we compute b p,q,r,m , ν ijk . Namely, we compose (3.1) with Consider now the case n > 5. It is easy to prove the following equalities: q+1,r,m b p,q,m+q−r−1,m σ q+1,r,m . Also, using the operad structure of M n and the case n = 5, we get that for any p ≤ ℓ < q, In particular, this gives a proof of Theorem 2.13 for H 1 (M n , Z).
3.6. The lower central series of Γ n . Let Γ p n be the p-th term of the lower central series of Γ n , and L ′ n be the associated graded Z-Lie algebra of this series, i.e. L ′ n = ⊕ ∞ p=1 Γ p n /Γ p+1 n . This is a Lie algebra graded by the positive integers, and it is generated in degree 1 by definition. Also we have a natural action of S n−1 on L ′ n , coming from the group J n−1 . We have L ′ n [1] = H 1 (M n , Z), so L ′ n has 2-torsion. Let us therefore consider the quotient Lie algebra L n = L ′ n /L ′ n 2 . It is generated by its degree 1 part, which by Theorem 3.8 is a free Z-module with basis µ ijk , i < j < k.
Theorem 3.9. There is a surjective S n−1 -equivariant homomorphism of graded Lie algebras ψ n : L n → L n , which maps µ ijk to µ ijk .
(i) ψ n is an isomorphism. In particular, (assuming Conjecture 3.3), L n is a free Z-module, and thus the only torsion in the lower central series of Γ n is 2-torsion.
In other words, the group Γ n is residually nilpotent.
3.7. The prounipotent completion. Let Γ n be the prounipotent (=Malcev) completion of Γ n (over Q). This is a prounipotent proalgebraic group. We can also define the proalgebraic group J n−1 = J n−1 × Γn Γ n . Let Lie Γ n be the Lie algebra of the group Γ n , which is called the Malcev Lie algebra of Γ n (see [PS] for a more general discussion about such Lie algebras). Let grLie Γ n be the associated graded of this Lie algebra with respect to the lower central series filtration. It is easy to see that grLie Γ n = L n ⊗ Q. Thus we have a surjective homomorphism ψ Q n : L n ⊗ Q → grLie Γ n , and we can make the Q-version of Conjecture 3.10: Conjecture 3.11.
(i) ψ Q n is an isomorphism. (ii) Γ n injects into its prounipotent completion.
Remark. Note that since Γ n is the fundamental group of an aspherical manifold, it is torsion free. This is a necessary condition for part (ii) of the conjecture.
3.8. Coboundary Lie quasibialgebras, quasiHopf algebras and representations of L n and Γ n . Recall [Dr1] that a coboundary Lie quasibialgebra is a Lie algebra g together with an element 4 ϕ ∈ (∧ 3 g) g . Given such a (g, ϕ) (over a field of characteristic zero), one can define a family of homomorphisms β n,g,ϕ : L n → U (g) ⊗n−1 , defined by the formula β n,g,ϕ (µ ijk ) = ϕ ijk . (Here ϕ ijk denotes the image of ϕ under the embedding g ⊗3 → U (g) ⊗n−1 which puts 1s in all factors other than i, j, k.) The invariance of ϕ implies that the quadratic relations of L n are preserved under this assignment.
Theorem 3.12. The representations β n,g,ϕ factor through L n .
Let C be the associated category (the objects are representations of g and the morphisms are power series in whose coefficients are morphisms of representations). This is a coboundary category and hence as explained in section 3.4, there is an action of Γ n on tensor products of objects. In fact, from Drinfeld's construction, this action comes from a map B n,g,ϕ : Γ n → 1 + 2 U (g) ⊗n−1 [[ ]]. This homomorphism factors through the prounipotent completion Γ n of Γ n , and thus defines a Lie algebra homomorphism B n,g,ϕ : Under this homomorphism, the image of the p-th term Lie Γ n p of the lower central series of Lie Γ n is contained in 2p U (g) ⊗n−1 [[ ]]. Therefore, we have a natural homomorphism B 0 n,g,ϕ : grLie Γ n → U (g) ⊗n−1 , defined by the formula B 0 n,g,ϕ (z) = −2p B n,g,ϕ (ẑ)mod , where z is of degree p andẑ is a lift of z. Now we claim that β n,g,ϕ = B 0 n,g,ϕ •ψ n . Both sides are invariant under the S n−1 -action, and thus it suffices to check the equality on the element µ 123 . This is straightforward to do by computing the 2 -part of B n,g,ϕ (b 1,1,2,3 ) using that Φ = 1 + 2 ϕ/3 + ....
Remark. This theorem gives supporting evidence for the above conjecture that ψ n is injective.
3.9. The non-formality of M n . Let L n ⊗ Q be the degree completion of L n ⊗ Q.
Proposition 3.13. For n ≥ 6, there does not exist an isomorphism ξ : Lie Γ n → L n ⊗ Q whose associated graded is the identity in degree 1.
Proof. It suffices to prove the statement for n = 6, since we have homomorphisms Γ n−1 → Γ n and Γ n → Γ n−1 whose composition is the identity map Γ n−1 → Γ n−1 , and similar homomorphisms for L n .
For n = 6, the statement was checked computationally using the "Magma" program.
Since Γ 6 is prounipotent over Q and S 5 is finite, this exact sequence is split. Thus we get J 5 = S 5 ⋉ Γ 6 , for some action of S 5 on Γ 6 . Now assume that an isomorphism ξ exists. Then all such isomorphisms form a torsor over a prounipotent group of unipotent automorphisms of the target, so by averaging we can choose ξ to be S 5 -invariant. Then ξ can be lifted to a homomorphism ξ ′ : J 5 → S 5 ⋉ exp( L 6 ⊗ Q). This can be restricted to a homomorphism ξ ′ : J 5 → S 5 ⋉ exp( L 6 ⊗ Q), which maps b 1,1,2,3 into exp(µ 123 + ...), where ... are higher order terms. Since J 5 is given by simple generators and relations, one is able to look for such homomorphisms using "Magma" (modulo m-th commutators for some m, to make the computations finite). The computation showed that already modulo the fourth commutators there is no such homomorphism under which the element b 1,1,2,3 goes to exp(µ 123 + higher terms). This implies the required statement.
In particular, the proposition implies that for n ≥ 6 the Malcev Lie algebra Lie Γ n of Γ n is not isomorphic to the degree completion of the rational holonomy Lie algebra L n ⊗ Q of M n , which means that the group Γ n is not 1-formal in the sense of [PS]. Therefore, by the results of [M, Su], M n is not a formal space in the sense of Sullivan (see e.g. [PS] for more explanations).
Remark. For n ≤ 5, the spaces M n are formal and the Malcev Lie algebra of Γ n is isomorphic to its associated graded.
3.10. The Drinfeld-Kohno Lie algebra. The Drinfeld-Kohno Lie algebra L n , defined for n > 2, is generated over Z by generators t ij = t ji for distinct indices 1 ≤ i, j ≤ n − 1, and relations [t ij , t ik + t jk ] = 0, [t ij , t kl ] = 0 for distinct i, j, k, l (see [Ko,Dr1,Dr2]). L n is a free Z-module (since it is an iterated semidirect product of free Lie algebras).
Kohno proved in [Ko] (using the Knizhnik-Zamolodchikov equations) that L n+1 ⊗ Q is the Lie algebra of the prounipotent completion of the pure braid group P B n . Let U n be the universal enveloping algebra of L n . The algebra U n ⊗ Q is Koszul, and is the quadratic dual of the Orlik-Solomon algebra OS n−1 , which is the cohomology algebra of the configuration space (see e.g. [Yuz2].) If g is a Lie algebra and Ω ∈ (S 2 g) g is an invariant element (i.e., (g, Ω) is a quasitriangular Lie quasibialgebra [Dr1]), then we have a homomorphism γ n,g,Ω : L n → U (g) ⊗n−1 given by γ n,g,Ω (t ij ) = Ω ij (this is analogous to β n,g,ϕ above). In the braid group setting, as L n is isomorphic to the Lie algebra of the prounipotent completion of P B n , the analogous statement to Theorem 3.12 is that the two different representations of L n agree (one comes from γ, the other from quantizing Ω).
3.11. Relation between L n and L n . We have a homomorphism of Lie algebras ξ n : L n → L n given by the formula ξ n (µ ijk ) = [t ij , t jk ]. Note that under this homomorphism, L n [1] is identified with L n [2]. It is clear that γ n,g,ω • ξ n = β n,g,ϕ , where ϕ = [Ω 12 , Ω 23 ].
Theorem 3.14. The map ξ Q n : L n ⊗ Q → L n ⊗ Q factors through L n ⊗ Q. Proof. Using Drinfeld's "unitarization" trick, one can define a homomorphism of prounipotent completions Ξ n : Γ n → P B n−1 (see [HK]). Namely, let B n−1 = B n−1 × P B n−1 P B n−1 . Then we can define a homomorphism Ξ n : J n−1 → B n−1 by setting Ξ n (σ p,q,r ) = β [p,q] At the Lie algebra level, Ξ n defines a homomorphism of filtered Lie algebras Lie Γ n → Lie P B n−1 . Taking the associated graded of this map, and using the fact that grLie Γ n = L n ⊗ Q, we obtain the required statement.

Remarks.
(i) Conjecture 3.15 implies Conjecture 3.11 (i) and Conjecture 3.3. (ii) Conjecture 3.15 also implies Conjecture 3.4, as we have natural morphisms L n+1 → L n , whose kernels are known to be free Lie algebras. On the other hand, by the Shirshov-Witt theorem, a Lie subalgebra of a free Lie algebra is free.

Poset homology and a twisted version of Λ n
We now leave this world of Lie algebras and turn to the task of proving our main theorem describing the cohomology ring. As a first step, we will examine our ring Λ n more closely. More precisely, we will consider a twisted version of Λ n which has close connections to the homology of the poset of odd set partitions (which in turn has close connections with the operad of Lie 2-algebras [HW]).

4.1.
Homology of the poset of odd set partitions. Given a poset P with bottom and top elements0 and1, there is an associated chain complex C * in whichC r+1 is the free Z-module spanned by chains By our convention, if0 =1 thenC 0 (P ) = Z andC r (P ) = 0 for r = 0. The (shifted reduced) homologyH * (P ) is defined to be the homology of this chain complex. If P doesn't have a top element, we defineH n (P ) :=H n+1 (P + ), where P + = P ⊔ {1}. Leth n (P ) be the rank ofH n (P ). Note that we have shifted the degrees of the chains from the usual convention, in order for the following to hold.
Proposition 4.1. If P and Q are posets with bottom and top and at least one ofH * (P ) andH * (Q) is free, theñ H * (P × Q) =H * (P ) ⊗H * (Q) as graded modules. In particular, the induced isomorphismH * (P × Q) → H * (Q × P ) is the standard exchange map for the tensor product of supermodules.
Here and below, as usual in homological algebra, the tensor product of supermodules is always taken in the symmetric monoidal category of supermodules, which means that the commutativity isomorphism is given by the formula v ⊗ w → (−1) deg(v) deg(w) w ⊗ v for homogeneous vectors v, w.
Proof. In terms of the order complex |∆(P )| of P , we havẽ where x is the midpoint of the edge between0 and1 (the local homology at that point). The result then follows from the Künneth formula for relative homology.
Let Π odd n denote the poset of partitions of {1, 2, . . . , n} in which each part has odd order.
Theorem 4.2. [Bj, CHR] The poset Π odd n is totally semimodular, and thus Cohen-Macaulay; that is, the homology of any closed interval in the poset is a free Z-module concentrated in the top degree.
In particular,H * (Π odd 2n+1 ) is concentrated in degree n, as isH * (Π odd 2n+2 ); note that as the latter does not naturally have a top element, it is thus implicitly added (and the degree shifted by 1). The further structure of these modules has been determined in [CHR].
In [Koz], Kozlov considers the following spectral sequence. Let P be a Cohen-Macaulay poset. The rank of an element x ∈ P is then the unique r such thatH r ([0, x]) = 0 (we take by convention that rank(0) = 0). Consider the filtration of the associated chain complex given by Namely, for our purposes, we consider chains of set partitions such that the coarsest (=biggest) partition in the chain has at least n − 2r parts. Then Kozlov observes that the associated spectral sequence looks like where the indices k, l run from 0 to rank(1) − 1. But this is 0 unless k = l, and thus the spectral sequence collapses on the E 2 page. Since the spectral sequence converges toH * (P ) and this is concentrated in the top degree, we find that E 2 k,l = 0 unless k = l = rank(1) − 1, in which case it equals the homology of P .
In other words, we obtain the following result.
Theorem 4.4. If P is a Cohen-Macaulay poset, the Whitney homology groups form a canonical exact sequence Remark. Note that W rank(1) =H * (P ) and W 0 = Z. If P has a bottom but not a top, we by convention do not include theH * (P ) term in W * (P ).
By construction, this exact sequence respects products when the reduced homology modules are free. The differential corresponding to this chain 21 complex acts on saturated chains (in which each step is a covering relation) by ∂ W (0 < x 1 < · · · < x r ) = (−1) r−1 (0 < x 1 < · · · < x r−1 ).
Note that since P is Cohen-Macaulay, only saturated chains appear in the Whitney homology.

4.2.
A twisted version of Λ. For a finite set S, letΛ(S) be the supercommutative Z-algebra with symmetric degree 1 generators τ ijk for i, j, k distinct elements of S, subject to the quadratic relations τ ijk τ jkl = 0 τ ijk τ klm + τ jkl τ lmi + τ klm τ mij + τ lmi τ ijk + τ mij τ jkl = 0. This is of course quite closely related to the S n -invariant presentation of Λ n+1 considered above, except for the change in symmetry of the generators. In fact, experimentation for small n immediately suggests that the two algebras have the same Hilbert series, a fact which we will confirm below.
A triangle graph is pair (V, E) where V is a finite set and E a subset of the set of three element subsets of V . V is called the set of vertices and E the set of edges. More generally, there is the notion of hypergraph, where subsets of any size are allowed.
Many notions from graph theory may be extended to triangle graphs. A path of length n in a triangle graph, from vertex x to a vertex y, is a sequence of edges e 1 , . . . , e n and vertices x = v 0 , . . . , v n = y with v i ∈ e i ∩ e i+1 for 0 < i < n, v 0 ∈ e 1 and v n ∈ e n . A cycle is a path of length greater than 1 from a vertex to itself which consists of distinct edges and vertices. A triangle forest is a triangle graph without any cycles and a connected triangle forest is called a triangle tree.
Given a monomial in the triples τ ijk , there is a natural triangle graph with vertex set S and with an edge for each variable. We can consider the associated partition of the set S into connected components. This gives a grading of the exterior algebra with respect to the lattice of partitions. That is, the product of the homogeneous components associated to two partitions π 1 , π 2 lies in the homogeneous component associated to their join. Since the ideal of relations ofΛ(S) is homogeneous with respect to this grading, Λ(S) inherits this grading. Thus for each partition π of S, we associate a corresponding spaceΛ[π] and we haveΛ(S) = The triangle graph for the monomial τ tlq τ pvn τ qik τ knw τ wsx τ mjr τ rou .
In particular, the structure of these homogeneous components is determined by the structure for partitions with a single part. For n = 5, we find the following.
Lemma 4.7. For any pair of distinct elements j, j ′ ∈ S,Λ[S] is spanned by monomials in which at least one triple contains {j, j ′ }.
Proof. Any monomial inΛ[S] corresponds to a connected triangle graph, and thus that triangle graph will contain a shortest path from j to j ′ . We proceed by induction on the length of that path, noting that if the path has length 1, we are done.
Assuming therefore that the length is greater than 1, let the shortest path begin by j, k, l. Then the monomial contains triples τ ijk τ klm for some i, m ∈ S. If we apply the quadratic relation, the resulting monomials all contain a triple joining j and l, and thus the length of the shortest path from j to j ′ in the new monomials has been decreased by 1. Proof. The same argument shows that we can reduce the cycle to length 2. But a cycle of length 2 is of the form τ ijk τ ijl = 0.
In other words, the triangle graph of any nonzero monomial inΛ(S) is a forest. This immediately implies that the grading by partitions refines the grading by degree.
Proof. Consider a nonvanishing monomial of degree d inΛ [π]. The incidence graph of its associated triangle graph has n + d vertices and 3d edges; since it is a forest, it must therefore have n − 2d connected components. Standard results on exponential generating functions then imply the following.
Corollary 4.11. Let f (u, t) be the generating function and let P (u, t) be the generating function where P n (t) is the Poincaré polynomial ofΛ n . Then P (u, t) = exp(f (u, t)).
Using Lemma 4.7 to its fullest, we can obtain the following spanning set ofΛ(S). Choose a total ordering on S.
Definition 4.12. We define basic triangle trees and forests as follows, by induction on the number of triangles.
1. A single point is a basic triangle tree. 2. A nontrivial triangle tree is basic iff the two smallest vertices are on a common triangle, and each of the three components after removing that triangle is basic. 3. A triangle forest is basic iff each component is basic.
For example, (4.1) is a basic triangle forest with respect to the usual order on the letter i, j, . . . , x.
Proposition 4.13. The algebraΛ(S) is spanned by the monomials associated to basic triangle forests.
Proof. This is a simple induction; by Lemma 4.7, any monomial associated to a tree can be expanded in terms of monomial associated to trees in which the two smallest vertices are on a common triangle, and similarly for the monomials associated to the subtrees.
If h(u) is the exponential generating function for basic trees, then we claim that h ′′ (u) = uh ′ (u) 3 . Indeed, the left-hand side is the exponential generating function for basic trees on n + 2 vertices, while the right-hand side corresponds to the following: a. A choice of element k ∈ {3, . . . , n + 2}
We will now show that basic triangle trees form a basis ofΛ[S] (and similarly for basic triangle forests andΛ(S)). As a consequence, arcsin(u) is also the exponential generating function for dimΛ [S].
Moreover, these abelian groups have bases indexed by basic triangle forests with component partition π.
Proof. Since bothΛ[π] andH * ([0, π]) are multiplicative under disjoint union of partitions, it is enough to treat the case |π| = 1, namely [0, π] = Π odd n . Given a triangle tree, any ordering of the triangles gives rise to a chain of set partitions; the k-th partition in the chain is the set of components of the subgraph spanned by the first k triangles. We thus obtain a mapΛ[1] → C * (Π odd n ), taking a tree to the alternating sum over the chains resulting from all orderings of the triangles. The five-term relation (and any tree multiple thereof) is annihilated by this map, so it is indeed well-defined.
We claim that the image of a tree is a cycle, and we thus obtain a welldefined map toH * (Π odd n ). Indeed, the operation of removing the l-th partition in a chain is nearly invariant under swapping the l-th and l + 1-st triangles, except that swapping the triangles gives rise to an overall sign.
Since the number of basic trees is equal to the rank of the free Z-modulẽ H * (Π odd n ) (by the remark following Proposition 4.13 and Theorem 4.3), the result will follow if we can exhibit a set of cochains such that the induced pairing with basic trees is triangular with unit diagonal. Note from the description of the map from trees to chains that the pairing of an elementary cochain (corresponding to a maximal chain in Π odd n ) with a triangle tree is ±1 or 0. Moreover, the pairing is nonzero precisely if there exists an ordering of the triangles in the tree corresponding to the same chain of odd set partitions.
First, some additional terminology. The "root" of a basic tree is the triangle containing the two minimal elements of its support. If we remove the root, we obtain three components; the one not containing one of the original minimal elements will be called the "stepchild". Given a basic tree T , size(T ) represents the size of its support, and we define rank(T ) := size(T ) − size(stepchild(T )) 2 .
Then if size(T ) = 2n + 1, we can associate a composition µ(T ) of n with first part rank(T ), second part the rank of its stepchild, and so forth. This then induces a partial order on basic trees by lexicographically ordering the associated compositions. Finally, we define the "keystone" of a basic tree as follows. If the stepchild of T is a single vertex, its keystone is simply the root. Otherwise, the keystone of T is the keystone of its stepchild.
Lemma 4.15. Let T be a basic triangle tree and F be the forest obtained by removing its keystone. Then any other basic tree T ′ containing F has µ(T ′ ) > µ(T ).
Proof. If the root of T was the keystone, so T had maximal composition n, then F consists of the component of 1, the component of 2, and a single isolated vertex k, and thus the only basic tree containing F is obtained by adjoining the triangle 12k, so the result holds in this case.
Otherwise, the root of T is still in F . If we remove it, we obtain a five tree forest, consisting of the component of 1, the component of 2, and three other components all contained in the stepchild of T . Now, T ′ is obtained from T by removing the keystone and adding another triangle instead. If that triangle meets the component of 1 or 2, the composition clearly increases. Otherwise, the result follows by induction applied to the stepchild of T . Now, for each basic forest F , we choose a triangle t F which is the keystone of some component. This then inductively gives rise to an ordering (t i ) n i=1 on the triangles of any tree T by letting t n := t T and t i−1 := t T \{t i ...tn} . Let α T be the sequence of set partitions obtained by successively adding t 1 , t 2 , etc, which we identify with the corresponding elementary cochain.
By Lemma 4.15, we can reconstruct the sequence of triangles from α T by taking at each step the triangle that minimizes the composition associated to the resulting tree. In other words, T is reconstructed from α T as the minimal tree having a nonzero (and thus unit) pairing with α T . This immediately gives us the desired triangularity. (1 + (n − 2 − 2k) 2 t).

26
Proof. The only thing remaining to show is that the exponential generating function implies the Hilbert series, or in other words that To this end, we observe that if t = −1/k 2 for a positive integer k, then But (4.2) is the sum of a polynomial of degree k and of a function satisfying f (u) = (−1) k+1 f (−u). Thus, if n − k is an even positive integer, we have d n du n P (u, −1/k 2 )| u=0 = 0. The coefficient of u n /n! in P (u, t) is therefore divisible by (1 + (n − 2i) 2 t) for 1 ≤ i < n/2. Since we know the degree of P n+1 (t), this determines the above expansion up to a constant which can be set via the limit P (u, 0) = exp(u).
Lemma 4.18. Under the isomorphism (4.3), the canonical differential on W * takes a forest monomial Proof. The action of the canonical differential is to remove the last element in the chain of partitions. This is equivalent to removing the last triangle in the ordering. Summing over the possible last triangles gives the stated result. This is the differential for the reduced homology of a simplicial complex, with a vertex for each triangle and a simplex for each basic forest.

The cohomology of the Bockstein
As a key step in determining the cohomology ring of M n , we will compute the cohomology of M n with coefficients in Z/4Z, modulo 2-torsion. To do so we will start with the cohomology ring of the complex moduli space M C n := M 0,n (C). In Theorem 5.5, we will use Keel's work to find an explicit basis for H * (M C n , Z) which is convenient for our purposes. We use this 27 cohomology ring to determine the cohomology of the real moduli space M n with coefficients in F 2 (Theorem 5.6). This mod 2 cohomology H * (M n , F 2 ) has a differential, the Bockstein, whose cohomology is the cohomology of M n with coefficients in Z/4Z, modulo 2-torsion. In Theorem 5.7, we compute the cohomology of this Bockstein differential and show that it is isomorphic toΛ({1, . . . , n − 1}) ⊗ F 2 . Thus the resulting Betti numbers give us the desired upper bound on the Betti numbers of M n (Corollary 5.8).
5.1. Cohomology of M C n . We begin by recalling the following presentation, due to Keel, of H * (M C n , Z). For our purposes, it will be useful to single out one of the marked points, and thus consider M C n+1 , with points marked 0, 1, . . . , n.
Theorem 5.1. [Keel] The commutative ring H * (M C n+1 , Z) is generated by elements (of degree 2) D S , one for each subset S ⊂ {0, 1, 2, . . . , n} with 2 ≤ |S| ≤ n − 1, subject to the following relations. dim(H 2k (M C n+1 , Z))t k u n n! satisfies the differential equation Remark. The class D S has a geometrical interpretation as the class of the divisor of M C n+1 consisting of singular genus 0 curves in which the removal of a singular point separates the points in S from the points not in S. Since On the other hand, by the definition of D {1,2,...,n} , we find that Π S = 0 whenever |S| = 2, and thus H 1 (M C n+1 , Z) is spanned by the elements Π S for |S| ≥ 3. There are 2 n − n 2 − n − 1 such elements, which equals the rank of H 1 (M C n+1 , Z), and thus the elements Π S for |S| ≥ 3 form a basis of H 1 (M C n+1 , Z), and generate the cohomology ring. Proposition 5.3. The elements Π S satisfy the following quadratic relation. For any subsets S, T ⊂ {1, 2, . . . , n} such that S ∩ T / ∈ {∅, S, T }, Proof. Note that the conditions on S and T imply 2 ≤ |S|, |T | ≤ n − 1. We have In particular, for any terms D U and D V in the respective sums, we have In other words, D U D V = 0 for any such pair, and the product of the two sums vanishes termwise.
Remark. When |T | = 2, we have Π T = 0. Since S ∪ T = S ∪ {i} for some i / ∈ S, is a special case of (5.2). More generally, it follows from an easy induction that for any disjoint sets S, T , We claim that (5.2) are the only relations satisfied by the Π S . To prove this, it will in fact be simplest to give a basis for the ring thus presented, and show that it is a free Z-module with the correct Hilbert series.
In fact, we can give a Gröbner basis for the ring, which will moreover be invariant under the S n action. We need one more set of relations, which can be deduced from (5.2).
Lemma 5.4. The elements Π S satisfy the following relation for all k ≥ 0. Let S 0 , S 1 , . . . , S k be disjoint sets, with union S; suppose moreover that |S i | ≥ 3 for 1 ≤ i ≤ k. Then Proof. For k = 0, this becomes the statement For k = 1 the claim is equivalent to (5.4), so let us assume that k ≥ 2. By applying (5.4) multiple times, we get and may thus assume S 0 = ∅. For k = 2, choose i ∈ S 2 and consider the known relation (5.7) (Π S 1 − Π S 1 ∪{i} )Π S 2 Π S 1 ∪{i} = 0.
By (5.2), we have Π S 2 Π S 1 ∪{i} = Π S 2 Π S 1 ∪S 2 + Π S 1 ∪{i} Π S 1 ∪S 2 − Π 2 S 1 ∪S 2 , so we can simplify (5.7) to For k > 2, let T = S 1 ∪ S 2 . We need to show that If we subtract from (5.8) the relation we find by setting Π T = Π S that the result is divisible by Π T − Π S . It is therefore divisible by and so is 0 by induction.
Theorem 5.5. The algebra H * (M C n+1 , Z) is freely spanned by monomials of the form |S|≥3 Π d S S satisfying the following conditions.
For each S such that d S > 0, let S 1 ,. . . , S k be the maximal proper subsets of S such that d S i > 0, disjoint by condition 1. Then Equivalently, the relations (5.2) and (5.5) form a Gröbner basis of (the ideal of relations of ) the cohomology ring H * (M C n+1 , Z) with respect to the grevlex order, relative to any ordering on the variables Π S extending inclusion.
Proof. Any monomial not satisfying the above conditions can be expanded in smaller monomials using the given relations; as a result, the "good" monomials span. The theorem will thus follow if we can show that they form a basis.
For this, we need simply count the monomials and show that we obtain the correct exponential generating function. Now, consider the exponential generating function C(u, t) of monomials with d {1,2,...,n} > 0, extended to include the constant 1 for n = 1. By standard manipulations of exponential generating functions, this satisfies C(u, t) = u + where m = k + |S| − i |S i | and l = d S . If we multiply by 1 − t and simplify, this becomes the functional equation exp(tC(u, t)) = 1 + tu + t 2 (exp(C(u, t)) − 1 − u). Now, the exponential generating function of all monomials (including 1 for n ≤ 2) is B(u, t) := exp(C(u, t)), and thus satisfies Differentiating with respect to u, we get .
Therefore B(u, t) − 1 − u satisfies the differential equation (5.1), and we indeed have the correct number of monomials.

Remark.
A similar Z-basis of H * (M C n+1 , Z) was given by Yuzvinsky [Yuz1], based on the generators D S for S ⊂ {1, 2, . . . , n}, |S| > 2, but otherwise the same. It differs in two important respects: first, while it respects a filtration by set partitions, it does not respect the grading by set partitions; and second, the associated Gröbner basis is more complicated. On the other hand, Yuzvinsky's basis is more amenable to computation of the Poincaré pairing.
One important consequence of this presentation is that there is a natural grading of H * (M C n+1 , Z) indexed by the lattice of set partitions of {1, 2, . . . , n}. Indeed, the hypergraphs associated to each monomial of each relation all have the same set of connected components; that set of connected components is the associated set partition. By inspection of the canonical monomials, we also find that the partitions that appear never have sets of size 2. 5.2. Cohomology with coefficients in F 2 . The above presentation for H * (M C n+1 , Z) immediately gives rise to a presentation for H * (M R n+1 , F 2 ), by the following result.
Theorem 5.6. There is a canonical isomorphism between H 2k (M C n+1 , F 2 ) and H k (M R n+1 , F 2 ) for each k, compatible with the ring structures. Proof. Indeed, Keel [Keel] showed that H * (M C n+1 , Z) is generated by algebraic divisors, all of which are in fact rational over R. It follows that M 0,n+1 is an "algebraically maximal" variety in the sense of [Kr] and thus the isomorphism follows from the main result of that paper.
Remark. Januszkiewicz (personal communication) has suggested another proof. One can construct M n+1 as an iterated blowup of projective n-space along the standard A n−1 hyperplane arrangement. The desired agreement of mod 2 cohomology holds for RP n and CP n and is preserved under blowing up of a linear subspace, and the result follows by induction.
See also [HHP] for a more general class of spaces satisfying this same relation to their real locus.
We denote the piece of H k (M R n+1 , F 2 ) indexed by the set partition π by Ξ k [π]; if π is a partition of a subset of {1, 2, . . . , n}, we adjoin singletons as necessary to make it a partition. We will also use Ξ * n to denote the entire cohomology ring H * (M R n+1 , F 2 ). 5.3. The Bockstein map and its cohomology. For any space X, consider the Bockstein map β : H * (X, Z/2Z) → H * (X, Z/2Z), which is the connecting map for the exact sequence The Bockstein is a differential. From the long exact sequence in cohomology, we see that its cohomology is isomorphic to the quotient of the mod 4 cohomology by the 2-torsion, This differential again corresponds to multiplication by Π {1,2,...,n} : it takes an element We may as well assume that x ∈ Π 2p+1 {1,...,n} Ξ * [π] for some partition π with 2p + 3 parts i.e. that x = Π 2p+1 {1,...,n} i Π π i y for some y. Multiplying by Π {1,...,n} , we use (5.5) to compute {1,...,n} j =i Π π j y modulo V 2p+4 . In particular, the d 2 differential is induced by the natural maps δ :="divide by Π π i " on each piece of π δ : H * β (V 1 /V 2 ) → H * −1 β (V 0 /V 1 ). So it suffices to prove that δ agrees with the canonical differential in its action onΛ. For this we proceed by induction, observing that it holds for Λ[{1, 2, 3}] (where both maps take τ 123 to 1), and that it acts as a derivation on trees. Indeed, using (5.2), we check that The theorem follows.
Let h k (X, Q) denote the k-th Betti number of a space X.
Corollary 5.8. We have the coefficient-wise upper bound Proof. Indeed, we have . . , n}), and the latter has the stated exponential generating function by Corollary 4.16.
A twisted version may also be of interest.
Corollary 5.9. Let β ′ be the twisted differential defined by Then there is a canonical isomorphism 6. The operad structure and the proof of the main results The main remaining step of the proof of the main theorem is to show that f Z n is split-injective. To do this we will use the operad structure to construct elements of the homology H * (M n ) which pair upper-triangularly with the images under f n of the basis vectors in Λ n . Along the way we will also determine the structure of the homology operad.
6.1. The cyclic (co)operad Λ. The collection of algebras Λ n forms a cyclic cooperad Λ. To describe this cyclic cooperad structure, it will be convenient to replace the index set {1, 2, . . . , n} by an arbitrary nonempty finite set. Thus let Λ S be the Z-algebra with antisymmetric generators ω ijkl for i, j, k, l ∈ S satisfying the relations (2.1), (2.2), (2.3). Similarly, let Λ(S) denote the Z-algebra with antisymmetric generators ν ijk for i, j, k ∈ S satisfying the relations of Λ |S|+1 .
Given nonempty finite sets S, T and a function f : S → T , define a function h t : Then we define a homomorphism (which will be the structure map of the cooperad) in degree one as follows: where each ω ijkl = 0 if two indices agree. (The superscripts are used merely to distinguish the generators of Λ T , denoted ω 0 ijkl , from the generators of each Λ f −1 (t) ⊔ {t} .) Note that this implies that at most one term appears on the right. (N.b., since we are defining the map on generators, the order of the tensor product is irrelevant. Also, if |f −1 (t)| < 3, we may freely omit the corresponding factor on the right, since Λ S = Z if 1 ≤ |S| ≤ 3.) This should be viewed as corresponding to the geometric operad map obtained by gluing together each pair of points labelled t.
The map ∆ f is easily seen to respect relation (2.1). For relation (2.2), we find that either one of the two generators maps to 0 or both map to elements of the same algebra; in either case, the relation automatically holds. To check relation (2.3), there's a few more cases. Either all the generators map to the same algebra, or at least one generator in each monomial maps to 0, or , f (p)}| = 4 (up to cyclic permutation of the indices). In either of the latter cases, the relation is easily verified.
Given another map g : T → U , we define for each u ∈ U a map Theorem 6.1. Given nonempty finite sets S, T , U and functions f : S → T , g : T → U , we have the identity (up to the symmetry of the tensor product). In other words, the maps ∆ f furnish the algebras Λ S with the structure of a cyclic cooperad in the category of superalgebras.
Proof. It suffices to check the relation on the generators of Λ S . And indeed, both sides map ω ijkl to The following proposition follows easily from definitions.
Proposition 6.2. The above cyclic cooperad structure is compatible with the natural map f Z 2 n : Λ n → H * (M n , Z 2 )/H * (M n , Z 2 ) 2 and the cyclic cooperad structure induced on cohomology by the cyclic operad structure of M n .
We now turn to the S n−1 -symmetric algebras Λ(S). If we add to S a new label ∞, we know by Proposition 2.3 that ν ijk → ω ijk∞ induces an isomorphism Λ(S) ∼ = Λ S ⊔ {∞} .
Given a function f : S → T , we can extend it to a function f : S ⊔ {∞} → T ⊔ {∞} by taking f (∞) = ∞. This then gives a map which we abusively denote ∆ f : This map then satisfies the axioms of a (noncyclic) operad. On the generators ν, we have Now, if we quotient by the augmentation ideal of Λ(T ), we obtain a map η f : Λ(S) → t∈T Λ(f −1 (t)).
Proposition 6.3. The map η f is a split surjection.
Proof. Indeed, for each t ∈ T , we have a map Λ(f −1 (t)) → Λ(S) induced from the inclusion map; taking the product of these maps gives the desired splitting.
If we ignore the product, the operad Λ # ′ (•) generated by τ with superantisymmetry and the 10-term relation is a twisted version of the Lie 2-algebra operad HW (•) discussed in [HW]. One of their main results is that HW (n) is isomorphic to H * (Π odd n ). It follows from Theorem 4.3 that the exponential generating function for dim (HW (n)) is arcsin(u √ t)/ √ t. Since the twisting just amounts to tensoring with the sign operad, the same generating function applies to our twisted operad. Using (6.2), any operation in Λ # can be expressed as a sum of operations where · is only used after τ . It follows that the exponential generating function for the number of additive generators of Λ # is bounded above by exp(arcsin(u √ t)/ √ t). Recall that by Corollary 4.16 this was also the exponential generating function for the ranks ofΛ n . A similar result holds for Λ n .
Theorem 6.4. The basic forests form a basis of Λ(S), which is thus a free Z-module. The corresponding exponential generating function is and the Hilbert series of Λ n is P n (t) = 0≤k<(n−3)/2 (1 + (n − 3 − 2k) 2 t).
Proof. The argument in Proposition 4.13 was purely combinatorial, and thus changing signs in the relations will have no effect. As a result, Λ(S) is also spanned by basic forests. Unfortunately, by twisting the S n action, we have destroyed the canonical isomorphism with partition homology, making the argument in Theorem 4.14 no longer valid. Recall that the main tool of Theorem 4.14 was a pairing between saturated chains of odd partitions and triangle trees. We can achieve the same effect using ternary forests and the operad structure.
To each saturated chain of odd partitions, we associate a ternary forest, with a node for each set that appears as the part of some partition in the chain. To each ternary tree U , let τ U ∈ Λ * (S) denote the result of composition of the operation τ according to the tree U ; we then extend this to forests using the product operation ·. Recall that to each triangle forest F , we have a monomial ν F ∈ Λ(S). Now given F a triangle forest and G a ternary forest, we can consider the pairing τ G , ν F .
The action of composition with τ (corresponding to a partition into three components) is such that a triangle forest has nonzero image iff there is a triangle in the forest that hits each component, while all other triangles are contained in a component; the action of composition with · is such that a triangle forest has nonzero image iff each component of the forest is contained in a component of the composition. In particular, the pairing between ternary forests and triangle forests takes on only the values ±1 and 0, nonzero iff there exists an ordering on the triangles inducing a partition chain with the given associated ternary forest. A triangle tree and a ternary tree that pair non-trivially.
By mimicking the proof of Theorem 4.14, with ternary forests instead of chains of odd partitions we obtain the result; note that the action of · is such that the pairing between forests with the same component partition is just (up to sign) the product of the pairings between the individual trees.
The proof of the theorem shows that the pairing between Λ # and Λ induces a surjective map Λ # → Hom(Λ, Z). Moreover, the number of additive generators of Λ # is bounded above by the rank of Λ. It follows that Λ # is torsion free and that the natural map Λ # → Λ * is an isomorphism. We conclude the following.
6.2. Determination of the cohomology ring. We are now in a position to prove our main theorems.
Theorem 6.6. The map f n : Λ n → H * (M n , Z)/H * (M n , Z) 2 is injective and splits as a map of Z-modules.
Proof. Recall that Λ n is a free Z module with basis of monomials ν F indexed by basic triangle forests F . It suffices to find a collection of elements in H * (M n , Z), also indexed by basic triangle forests which pair upper triangularily with the images f n (ν F ).
To do this we follow the proof of Theorem 4.14, or more precisely its modification in Theorem 6.4. In the proof of Theorem 4.14, for each basic triangle forest (more precisely, tree, but by the product structure, this extends to forests), we associated a saturated chain of set partitions, which paired with the desired property. In the proof of Theorem 6.4, we used this saturated chain of set partitions to build a ternary forest.
For each ternary tree U , we can consider a map g U : M d 4 → M n which is given by gluing curves according to the tree U . Let ρ U denote the image under the map g U of the fundamental class in H * (M n ). These elements ρ U are exactly what would be obtained by using U to specify a particular composition of the homology operad generator τ ∈ H 1 (M 4 , Q) (after tensoring with Q). More generally, for a ternary forest G, we consider the associated map g G : M d ′ 4 × M c → M n , where c is the number of components of G, first gluing together curves according to the component trees of the forest, then gluing their roots to M c . The class ρ G is then the image of the product of the fundamental class of M d 4 with the point class in M c , and again corresponds to the appropriate element of the homology operad. The pairing between ρ G and f n (ν F ) is again described combinatorially as in the proof of Theorem 6.4, and thus we again have the desired upper triangularity property.
In particular, we have constructed a collection of linear functionals on H * (M n , Z)/H * (M n , Z) 2 that, when evaluated on our basis of Λ n , produce 40 a triangular matrix with unit diagonal. Composing these functionals with the inverse of that upper triangular matrix produces a left inverse of f n . It follows that Λ n is a direct summand of H * (M n , Z)/H * (M n , Z) 2 .
So we can write H * (M n , Z)/H * (M n , Z) 2 = Λ n ⊕ B. At this point we do not know much about the complement B. Here we need the information from section 5.
Theorem 6.7. B is a product of odd torsion modules and H * (M n , Z) has no 4-torsion.
Proof. Let us split H * (M n , Z) (non-canonically) as H * (M n , Z) = F ⊕G⊕H⊕ I, where F is free, G is a product of odd torsion modules, H is a product of Z/2Z and I is a product of Z/2 k Z for k ≥ 2. Then, H * (M n , Z)/H * (M n , Z) 2 is isomorphic to F ⊕ G ⊕ I ′ where I ′ = I/I 2 . By Theorem 6.6, we see that the rk(F ) ≥ rk(Λ n ).
On the other hand, H * (M n , Z/4Z)/H * (M n , Z/4Z) 2 is an F 2 vector space of dimension rk(F ) plus twice the number of factors in I.
Hence we conclude that rk(F ) = rk(Λ n ) and that I = 0. Since I = 0, there is no 4-torsion. Also we see that the complement B is a product of odd torsion modules.
As a corollary of our proof we also see the following.
Corollary 6.9. H * (M n , Q) has a basis given by fundamental classes tensor point classes coming from maps M d 4 × M c → M n corresponding to basic triangle forests.