Some Hopf Algebras of Trees 2 0 0 Pepijn van der Laan 2 [email protected] n a Mathematisch Instituut, Universiteit Utrecht J 8 Decemeber 9, 2001 ] A Q 1 Introduction . h t a m IntheliteratureseveralHopfalgebrasthatcanbedescribedintermsoftrees [ have been studied. This paper tries to answer the question whether one can 3 understand some of these Hopf algebras in terms of a single mathematical v construction. 4 4 Werecall theHopfalgebraofrootedtrees asdefinedbyConnesandKreimer 2 6 in [3]. Apart from its physical relevance, it has a universal property in 0 1 Hochschild cohomology. We generalize the operadic construction by Mo- 0 erdijk [13] of this Hopf algebra to more general trees (with colored edges), / h and prove a universal property in coalgebra Hochschild cohomology. For a t a Hopf operad P, the construction is based on the operad P[λ ] obtained from m n : P by adjoining a free n-ary operation. v i For a specific multi-parameter family of Hopf algebras obtained in this way, X r we give explicit formulas for the (a priori inductively defined) comultiplica- a tion and for the Lie bracket underlying the dual . Some special cases yield natural examples of pre-Lie and dendriform (and thus associative) algebras. We apply these results to construct some known Hopf algebras of trees. No- tably, the Loday-Ronco Hopf algebra of planar binary trees [11], and the Brouder-Frabetti pruning Hopf algebra [1]. The author plans to discuss the simplicial algebra structure on the set of initial algebras with free n-ary operation P for an operad P with multi- n plication in future work, together with some relations of the P[λ ] to the n algebra Hochschild complex. The author is grateful to Ieke Moerdijk for suggesting the Hopf P-algebras P and their simplicial structure and for motivating as well as illuminating n discussions, and to Lo¨ıc Foissy and Maria Ronco for pointing out errors in previous versions of this manuscript. 1 Some Hopf algebras of trees 2 2 Preliminaries This section fixes notation on trees and describes some results of Connes and Kreimer[3], and Chapoton and Livernet [2] that motivated this paper. Rootedtreestareisomorphismclassesoffinitepartiallyorderedsetswhich (i). have a minimal element r (∀x6= r : r < x); we call r the root, and (ii). satisfy the tree condition that (y 6= z) ∧ (y < x) ∧ (z < x) implies (y < z)∨(z <y). The elements of a tree are called vertices. A pair of vertices v < w is called an edge if there is no vertex x such that v < x < w. Thenumber of vertices of a tree t is denoted by |t|. A path from x to y in a tree is a sequence (x ) i i of elements x= x > x > ... > x > x = y of maximal length. We will n n−1 1 0 say that x is above y in a tree if there is a path from x to y. Thus we may depict a rooted tree as a finite directed graph, with one terminal vertex, the root. A vertex is called a leaf if there is no other vertex above it. A vertex is an internal vertex if it is not a leaf. We draw trees the natural way, with the root downwards. An automorphism of a tree t is an automorphism of the partially ordered set. A forest is a finite, partially ordered set satisfying only property (ii) of the above. Aforestalwaysisadisjointunionoftrees,itsconnectedcomponents. Arootedtreecanbepicturedasatreewithunlabeledverticesanduncolored edges. A forest is a set of these. In the sequel we need trees with colored edges. That is, there is a function from the set of edges to a fixed set of colors. Vertices can be labeled as well (i.e. there is a function from the set of vertices to a fixed set of labels). Also trees with a linear ordering on the incoming edges at each vertex are used. A colored forest is a linearly ordered set of colored trees. An automorphism of a colored tree is an automorphism of the underlying tree compatible with the coloring of the edges. We consider two operations on trees: cutting and grafting. Let s and t be trees and let v ∈ t be a vertex of t. Define s◦ t to be the tree that as a v set is the disjoint union of s and t endowed with the ordering obtained by adding the edge v < r . This operation is called grafting s onto v. When s using trees with colored edges, we write s◦i t for grafting s onto v by an v edge of color i. For trees with labeled vertices, grafting preserves the labels. The operation of grafting s on t is visualized below. Acutinatreetisasubsetofthesetofedgesoft. Acutisadmissibleiffor each leaf m of t the unique path m > ... > x > x > r to the root contains 2 1 Some Hopf algebras of trees 3 r s v Figure 1: grafting s on t at most one edge of the cut. Removing the edges in a cut c yields a forest. We denote by Rc(t) the connected component of this forest containing the root and by Pc(t) the complement of Rc(t). We denote the set of admissible cuts of t by C(t). For colored and labeled trees, cutting preserves the colors of edges that arenot cutand labels of vertices. Theleft picturebelow shows an admissible cut, whereas the cut on the right is not admissible. Figure 2: an admissible cut (left) and a non-admissible cut (right) We describe the Hopf algebra H of rooted trees (defined in Connes- R Kreimer [3]) as follows. Let k be a field. The set of rooted trees and the empty set generate a Hopf algebra over k. As an algebra it is the polynomial algebra in formal variables t, one for each rooted tree. Thus H R is spannedby forests. Multiplication correspondstotaking thedirect union. The algebra H is of course commutative. The unit is the empty tree. R Comultiplication ∆ is defined on rooted trees t and extended as a algebra homomorphism: ∆(t)= X Pc(t)⊗Rc(t), c∈C(t) where the sum is over admissible cuts. The counit ε : H → k takes value R 1 on the empty tree and 0 on other trees. The Hopf algebra H is Z-graded with respect to the number of vertices in R forests. The homogeneous elements of degree m are products t ·...·t of 1 n trees, such that |t | = m. Both the product and the coproduct preserve P i the grading. Some Hopf algebras of trees 4 Denote by V∗ the graded dual of a graded vector space V: V∗ = M(Vn)∗, n the direct sum of the duals of the spaces of homogeneous elements. A basis for (H )∗ is {D | |t | = n}, the dual basis to the basis for (H ) R n t1·...·tk Pi i R n given by products of trees. Of course, H∗ is a cocommutative Hopf algebra, R with comultiplication k ∆(Dt1·...·tk) = X X Dtσ−1(1),...,tσ−1(i) ⊗Dtσ−1(i+1),...,tσ−1(k), i=0σ∈S(i,k−i) where S(i,k−i) is the set of (i,k−i)-shuffles in S . We sum over these to k avoid repetition of terms in the right hand side. The primitive elements are those dual to (single) rooted trees. As proved by Connes and Kreimer [3], the Lie algebra which has H∗ as its R universal enveloping algebra is the linear span of rooted trees with the Lie bracket [Dt,Ds]= X(n(t,s,u)−n(s,t,u))Du, u where n(t,s,u) is the number of admissible cuts c of u such that Pc(u) = t and Rc(u) = s. Chapoton and Livernet [2] show that this is the Lie algebra associated to the free pre-Lie algebra on one generator (cf. section 7 for details). 3 Operads 3.1 Convention For the rest of this paper, we restrict to the category of vector spaces over a fixed field k, but the general theory carries over to any symmetric monoidal category with countable coproducts and quotients of actions by finite groups on objects (cf. Moerdijk [13]). Let kS denote the group algebra of the permutation group S on n ob- n n jects. An operad P in this paper will mean an operad with unit. Thus an operad consists of a collection of right kS -modules P(n), together with an n associative, kS -equivariant composition n γ : P(n)⊗P(m )⊗...⊗P(m )−→ P(m +...+m ), 1 n 1 n such that there exists an identity id : k → P(1) with the obvious property and a unit u: k → P(0), which need not be an isomorphism. The existence Some Hopf algebras of trees 5 of the unit map is the only change with respect to the usual definition of an operad (consult Krizand May [8], or Ginzburgand Kapranov [7], or Getzler and Jones [6]). Following Getzler and Jones [6] we define an operad with multiplicationasanoperadtogether withanassociative elementµ ∈ P(2). The category of pointed vector spaces has as objects vector spaces V with a base point u: k → V. Morphisms are base point preserving k-linear maps. We use notation 1 := u(1). There are some canonical functors: The forgetfulfunctortovector spaceswillbeusedimplicitly. Thefreeassociative algebra functor T on a pointed vector space V is left adjoint to the forgetful functor from unital associative algebras to pointed vector spaces. ForanypointedvectorspaceV,thereisanoperadEnd suchthatEnd (n)= V V Hom (V⊗n,V). The pointed structure of V is only used to to define k u : k → End(V)(0), the elements of Hom (V⊗n,V) need not preserve the k basepoint. AP-algebra structureonV isamapof operads(i.e. preserving relevant structure) from P to End . Equivalently, a P-algebra is a vector V space V together with linear maps γ : P(n)⊗ (V⊗m1 ⊗...⊗V⊗mn) −→ V⊗m1+...mn, V kSn compatible with composition in P and unit in the natural sense. 3.2 Example Let k be the operad, with k(0) = k = k(1) and k(n) = 0, otherwise (with u = id). Algebras for k are pointed vector spaces. The operad k is the initial operad in our setting. WedenotebyComtheoperadwithasalgebrasunitalcommutative algebras. This operad satisfies Com(n) = k for all n (where u : k → k is the identity map). Likewise Ass is the operad satisfying Ass(n)= kS , the group algebra of S , n n as a right S -module. The Ass-algebras are unital associative algebras. An n operad with multiplication is an operad P together with a map of operads from Ass to P. Amapofoperadsϕ :P → Qinducesanobviousfunctorϕ∗ :Q-Alg → P-Alg. This functor has a left adjoint ϕ : P-Alg → Q-Alg. Let P be any operad ! and let i : k → P be the unique inclusion of operads. Then i is the unitary ! free P-algebra functor. Let P bean operad. We can form the operad P[λ ] by adjoining a freen-ary n operation to P(n). Algebras for P[λ ] are just P-algebras A endowed with n a linear map α : A⊗n → A. The reader familiar with the collections (cf. Getzler and Jones [6], or Ginzburg and Kapranov [7]), will recognize P[λ ] n Some Hopf algebras of trees 6 as the coproduct of operads P[λn]= P⊕kFEn of P and the free operad FE on the collection E defined by E (n)= kS n n n n and E (m) = 0 for m 6= n. n Denote the initial P[λ ]-algebra P[λ ](0) by P . For any P[λ ]-algebra n n n n (A,α), there is by definition an unique P-algebra morphism γ such that the following diagram commutes. P⊗n λn // P n n γ⊗n γ (cid:15)(cid:15) (cid:15)(cid:15) A⊗n α //A The operad P[λ ] can be described in terms of planar trees. A planar tree is n understood to have a linear ordering on the incoming edges at each vertex and might have external edges. There is a linear ordering on all external edges. An element of P[λ ](m) can berepresented by atree with m external n edges and each vertex v with n incoming edges labeled either by an element of P(n) or by λ . We identify two such representing trees if they can be n reduced to the same tree using edge contractions implied by composition in P, equivariance with respect to the kS -action at each internal vertex v and n kS -equivariance at the external edges. The initial P[λ ]-algebra P[λ ](0) m n n is described by such trees without external edges. 3.3 Example Let P = Com. The initial algebra C = Com[λ ](0) can n n be described as the free commutative algebra on trees with edges colored by {1,... ,n} (and no ordering on the edges). A bijection T is given by induction on the number of applications of λ as follows. T(1) = 1 = ∅, and T(λ(1,... ,1)) = r (the one vertex tree), and T(λ(x ,... ,x ) is the tree 1 n obtained from the forest x ·...·x by adjoining a new root and connecting 1 n the roots of each tree in x to the new root by an edge of color i. Figure 3 i shows (twice) the tree T(λ(x,λ(xx,1)λ(x,1))) in C , where x = λ(1,1). 2 1 1 1 1 1 1 1 2 2 1 2 2 Figure 3: trees not equal in A , but equal in C 2 2 Some Hopf algebras of trees 7 3.4 Example Let P = Ass. The initial algebra A = Ass[λ ](0) can be n n described as the free associative algebra on trees with edges colored by {1,... ,n} and at each vertex the incoming edges of each color endowed with a linear ordering. Equivalently, we could say, a linear ordering on all incoming edges extending the ordering on the colors. A bijection is given by the map T with the same inductive definition as in the pre- vious example, but using associative multiplication. In the associative case, the two trees in figure 3 are not identified. The tree to the right in figure 3 is T(λ(x,λ(x,1)λ(xx,1))) in A , while the tree to the left is 2 T(λ(x,λ(xx,1)λ(x,1))) (where x = λ(1,1)). 3.5 Example LetP = k. Thenk = k[λ ](0)canbeidentifiedwiththefree n n vector space on trees (not forests, but possibly empty) with edges labeled by {1,... ,n} and at most one incoming edge of each color at each vertex. For the relation to n-ary trees, see section 8. 4 Hopf Operads A Hopf operad (cf. Getzler and Jones [6], and also Moerdijk [13]) is an operad in the category of coalgebras over k. Thus, a Hopf operad P is a (k linear) operad together with a morphisms k ←ε− P(n)−∆→ P(n)⊗P(n), such that∆andεsatisfy theusualaxioms of acoalgebra: ∆is coassociative and ε is a counit for ∆ (cf. Sweedler [15]), and such that the composition γ of the operad is a coalgebra morphism. Moreover, ∆ should be compatible with the kS -action, where P(n)⊗P(n) is a kS - module via the diagonal n n coproduct. For any Hopf operad P, the tensor product of two P-algebras is a P-algebra again. A Hopf P-algebra A is a P-algebra A in the category of (counital!) coalge- bras. Note that we can not use the description of algebras in terms of the endomorphism operad in the category of coalgebras, since coalgebra homo- morphisms do not form a linear space. In this generality it is not natural to consider antipodes. A Hopf Ass-algebra is just a bialgebra. Let ϕ :Q → P be a map of Hopf operads. The map ϕ induces functors ϕ∗ :P-Alg → Q-Alg and ϕ¯∗ : P-HopfAlg → Q-HopfAlg. The map ϕ∗ has a left adjoint ϕ (we work with k-vector spaces). Note that ! ϕ∗(k) = k and for P-algebras A and B we have ϕ∗(A⊗B) = ϕ∗(A)⊗ϕ∗(B) Some Hopf algebras of trees 8 (the map ϕ is compatible with ∆). Using this observation, conclude that the adjunction induces algebra mapsϕ(k) = ϕϕ (k) → k and ϕ(A⊗B)→ ! ! ∗ ! ϕ(ϕ∗ϕA⊗ ϕ∗ϕB) → ϕ(A) ⊗ ϕ(B). These maps serve to show that ϕ ! ! ! ! ! ! lifts to a left adjoint ϕ¯ :Q-HopfAlg −→ P-HopfAlg ! of ϕ¯∗. Let P be a Hopf operad. The aim of this section is to state a general result on Hopf operad structures on P[λ ]. We use the notations λ = λ and n n P = P[λ ](0) when no confusion can arise. n n Let (A,α) be a P[λ ]-algebra and let σ ,σ : A⊗n → A be a pair of linear n 1 2 maps and define for each such pair a map (σ ,σ ) :(A⊗A)⊗n → A⊗A by 1 2 (σ ,σ ) = (σ ⊗α +α ⊗σ )◦τ, 1 2 1 n n 2 where τ is the n-fold twist map which identifies (A⊗A)⊗n with A⊗n⊗A⊗n by the symmetry of the tensor product. For vector spaces V ,... ,V , the 1 2n map τ is the natural map τ :V ⊗...⊗V 7→ V ⊗...V ⊗V ⊗V ...⊗V 1 2n 1 2n−1 2 4 2n induced by the symmetry (in the dg case this involves some signs). We now list some results for linear maps σ that define a Hopf algebra i structure on P but do not extend to P[λ ]. The results in this section are n n obtained along the same lines as the results in Moerdijk [13]. Our approach is more general in the sense that Moerdijk considered only the case n = 1. Let (P ,λ ) be the initial P[λ ]-algebra. For any pair of n-ary linear n n n maps σ ,σ there is a unique P[λ ]-algebra morphism (P ,λ ) → (P ⊗ 1 2 n n n n P ,(σ ,σ )). That is, a unique P-algebra morphism such that n 1 2 P⊗n λ // P n n ∆⊗n ∆ (cid:15)(cid:15) (cid:15)(cid:15) (P ⊗P )⊗n(σ1,σ2)//P ⊗P n n n n commutes. Define ε : P → k as the unique P[λ]-algebra morphism n (P ,λ ) → (k,0), which extends ε : P(0) → k. The following proposition n n is a generalization of Moerdijks construction [13]. The proof is completely analogous. 4.1 Proposition Let n ∈ N, λ and P be defined as above. Let σ : n n i P⊗n → P for i= 1,2 be linear maps. If σ satisfies n n i ǫ◦σ = ǫ⊗n, and i (σ ⊗σ )◦τ ◦∆⊗n = ∆◦σ ; i i i Some Hopf algebras of trees 9 then there exists a unique Hopf-P algebra structure on P extending the Hopf n P-algebra structure on P(0) such that ∆◦λ = (σ ,σ )◦τ◦∆⊗n and ε◦λ = 0. 1 2 In the following examples |t| denotes the number of applications of λ in an n element t ∈ P[λ ](m), for any m. In the case P= Ass, or P = Com, or P = k n this corresponds to counting the number of vertices in a tree. 4.2 Example Let P be a Hopf operad. We consider the case n= 1. |t| i) For any q ,q ∈ k, the endomorphisms σ (t) = q t define a coassociative 1 2 i i Hopf P-algebra structure on P (cf. Moerdijk [13] for the initial algebra). 1 ii) Suppose that P is a Hopf operad with multiplication. For any q ,q ∈ k, 1 2 the endomorphisms σ (t) = q|t|r|t| define a Hopf P-algebra structure on P . i i 1 (Here r is λ(1), and powers are with respect to the multiplication in P.) 4.3 Example Let P be a Hopf operad with multiplication. For any choice of q ∈ k for all j ≤ n, the maps ij σ (t ,... ,t ) = q|t1|·...·q|tn|t ·...·t i 1 n i1 in 1 n (where i= 1,2) give a Hopf P-algebra structure on P . n 5 Cohomology IntheprevioussectionweconstructedHopfoperadstructuresonP[λ ]. This n section aims to describe the relation of these Hopf operads and Hochschid cohomology for coalgebras. Let A be a Hopf Ass-algebra, and let C∗ be the graded vector space, which (p) in degree q is Hom (A⊗p,A⊗q). For ϕ ∈ Hom (A⊗p,A⊗q) we define a dif- k k ferential by the formula q dϕ = (µ(p)⊗ϕ)◦τ ◦∆⊗p+X(−1)i∆(i) ◦ϕ+(−1)q+1(ϕ⊗µ(p))◦τ ◦∆⊗p, i=1 where∆ (x ⊗...⊗x ) = (x ⊗...⊗∆(x )⊗...⊗x ). Thisisthecoalgebra- (i) 1 q 1 i q Hochschild complex with respect to the left and right coaction of A on A⊗p given by (µ(p)⊗id)◦τ ◦∆ : A⊗p −→ A⊗A⊗p (or with (id⊗µ(p)), where µ(p) is the unique p-fold application of µ. This complex (for p,q > 0) is the p-th column in the bicomplex used by Lazarev andMovshev[9]tocomputewhattheycallthecohomologyofaHopalgebra. Some Hopf algebras of trees 10 Let P be a Hopf operad, and let A be a Hopf P-algebra, let p ≥ 1 and σ ,σ :A⊗p → A be coalgebra morphisms. Then 1 2 (σ ⊗id)◦τ ◦∆⊗p :Ap → A⊗A⊗p and 1 (id⊗σ )◦τ ◦∆⊗p :Ap → A⊗p⊗A 2 define a left and a right coaction of A on Ap and we can define the complex q C with the boundary d . We can write the differential explicitly as σ1σ2 σ1σ2 q dϕ = (σ1⊗ϕ)◦τ ◦∆p+X(−1)i∆(i)◦ϕ+(−1)q+1(ϕ⊗σ2)◦τ ◦∆p. i=1 This is the Hochschild boundary with respect to these coactions. The coho- mology of this complex will be denoted H∗ (A). σ1σ2 Let P be a Hopf operad. A natural n-twisting function ϕ is a map from Hopf P-algebras B to coalgebra maps ϕ(B) : B⊗n → B, such that the map ϕ commutes with augmented P-algebra morphisms f : A → B (i.e. f ◦σ(A) = σ(B) ◦f⊗n for i = 1,2). i i (B) If σ and σ are natural p-twisting functions such that σ satisfies the 1 2 i conditions from 4.1 for any Hopf P algebra B; then H∗ (B) is defined for σ1σ2 any Hopf-P algebra B, and natural in B. Let(B,β)beaHopf P-algebra. Thenβ isa1-cocycleinthe(σ ,σ )-complex 1 2 iff (σ ⊗β)∆−∆β+(β ⊗σ )∆ = 0. 1 1 5.1 Example LetPbeaHopfoperad. Thenσ = p ∈ P(n)definesanatural n-twisting function. More generally, if σ = (ε⊗k⊗p)τ for some p ∈ P(n−k) and some τ ∈ S , then σ defines a natural n-twisting function. n WenowcharacterizetheuniversalpropertyoftheHopfP-algebraP . Again n this is a direct generalization of Moerdijk [13]. 5.2 Theorem Let (σ ,σ ) be a pair of natural twisting functions of Hopf 1 2 P-algebras, satisfying the conditions of Theorem 4.1 and endow P with the n induced Hopf P-algebra structure. For every Hopf P-algebra B, there is a one-one correspondence between (i). Hopf P-algebra maps c : P → B that lift to a map (P ,λ) → (B,β) β n n of P[λ ]-algebras and n (ii). cocycles β in the (σ ,σ )-twisted complex of B. 1 2