Algebraic Structures on Typed Decorated Rooted Trees
Typically decorated trees are used by Bruned, Hairer, and Zambotti to describe a renormalisation process on stochastic PDEs. We here study the algebraic structures on these objects: multiple pre-Lie algebras and related operads (generalizing a result by Chapoton and Livernet), noncommutative and coc...
Saved in:
| Published in: | Symmetry, Integrability and Geometry: Methods and Applications |
|---|---|
| Date: | 2021 |
| Main Author: | |
| Format: | Article |
| Language: | English |
| Published: |
Інститут математики НАН України
2021
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/211441 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Algebraic Structures on Typed Decorated Rooted Trees. Loïc Foissy. SIGMA 17 (2021), 086, 28 pages |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859603287414669312 |
|---|---|
| author | Foissy, Loïc |
| author_facet | Foissy, Loïc |
| citation_txt | Algebraic Structures on Typed Decorated Rooted Trees. Loïc Foissy. SIGMA 17 (2021), 086, 28 pages |
| collection | DSpace DC |
| container_title | Symmetry, Integrability and Geometry: Methods and Applications |
| description | Typically decorated trees are used by Bruned, Hairer, and Zambotti to describe a renormalisation process on stochastic PDEs. We here study the algebraic structures on these objects: multiple pre-Lie algebras and related operads (generalizing a result by Chapoton and Livernet), noncommutative and cocommutative Hopf algebras (generalizing Grossman and Larson's construction), commutative and noncocommutative Hopf algebras (generalizing Connes and Kreimer's construction), bialgebras in cointeraction (generalizing Calaque, Ebrahimi-Fard, and Manchon's result). We also define families of morphisms and, in particular, we prove that any Connes-Kreimer Hopf algebra of typed and decorated trees is isomorphic to a Connes-Kreimer Hopf algebra of non-typed and decorated trees (the set of decorations of vertices being bigger), through a contraction process, and finally obtain the Bruned-Hairer-Zambotti construction as a subquotient.
|
| first_indexed | 2026-03-14T02:38:13Z |
| format | Article |
| fulltext |
Symmetry, Integrability and Geometry: Methods and Applications SIGMA 17 (2021), 086, 28 pages
Algebraic Structures on Typed Decorated
Rooted Trees
Löıc FOISSY
Univ. Littoral Côte d’Opale, UR 2597 LMPA, Laboratoire de Mathématiques Pures
et Appliquées Joseph Liouville, F-62100 Calais, France
E-mail: foissy@univ-littoral.fr
URL: https://loic.foissy.free.fr/pageperso/accueil.html
Received February 02, 2021, in final form September 12, 2021; Published online September 21, 2021
https://doi.org/10.3842/SIGMA.2021.086
Abstract. Typed decorated trees are used by Bruned, Hairer and Zambotti to give a des-
cription of a renormalisation process on stochastic PDEs. We here study the algebraic
structures on these objects: multiple pre-Lie algebras and related operads (generalizing
a result by Chapoton and Livernet), noncommutative and cocommutative Hopf algebras
(generalizing Grossman and Larson’s construction), commutative and noncocommutative
Hopf algebras (generalizing Connes and Kreimer’s construction), bialgebras in cointeraction
(generalizing Calaque, Ebrahimi-Fard and Manchon’s result). We also define families of
morphisms and in particular we prove that any Connes–Kreimer Hopf algebra of typed and
decorated trees is isomorphic to a Connes–Kreimer Hopf algebra of non-typed and decorated
trees (the set of decorations of vertices being bigger), through a contraction process, and
finally obtain the Bruned–Hairer–Zambotti construction as a subquotient.
Key words: typed tree; combinatorial Hopf algebras; pre-Lie algebras; operads
2020 Mathematics Subject Classification: 05C05; 16T30; 18D50; 17D25
1 Introduction
Bruned, Hairer and Zambotti used in [3, 5] typed trees in an essential way to give a systematic
description of a canonical renormalisation procedure of stochastic PDEs. Typed trees are rooted
trees in which edges are decorated by elements of a fixed set T of types. They also appear in
a context of low dimension topology in [20] (there, described as nested parentheses) and for the
description of combinatorial species in [1]. We here study several algebraic structures on these
trees, generalizing results of Connes and Kreimer [10], Chapoton and Livernet [9], Grossman
and Larson [14], Calaque, Ebrahimi-Fard and Manchon [7].
In the work of Bruned, Hairer and Zambotti, the considered trees are typed, with a finite set
of types denoted by L, and labeled. We here forget about the labels and study the algebraic
structures induced by types. We first define grafting products of trees, similar to the pre-Lie
product of [8]. For any type t, we obtain a pre-Lie product
t on the space gD,T of T -typed trees
whose vertices are decorated by elements of a set D. For example, if and are two types,
if a, b, c P D, then
a
b
c � a
cb
� a
b
c
, a
b
c � a
cb
� a
b
c
.
This paper is a contribution to the Special Issue on Algebraic Structures in Perturbative Quan-
tum Field Theory in honor of Dirk Kreimer for his 60th birthday. The full collection is available at
https://www.emis.de/journals/SIGMA/Kreimer.html
mailto:foissy@univ-littoral.fr
https://loic.foissy.free.fr/pageperso/accueil.html
https://doi.org/10.3842/SIGMA.2021.086
https://www.emis.de/journals/SIGMA/Kreimer.html
2 L. Foissy
Then gD,T , equipped with all these products, is a T -multiple pre-Lie algebra (Definition 3.1),
also called matching pre-Lie algebras in [25]: for any types t and t1, for any x, y, z P gD,T ,
x
t1 py
t zq � px
t1 yq
t z � x
t pz
t1 yq � px
t zq
t1 y.
This relation appears in [4]. We prove in Corollary 3.11 that it is the free T -multiple pre-Lie
algebra generated by D, generalizing the result of [9], first mentioned in [4, Proposition 4.21].
Consequently, we obtain a combinatorial description of the operad of T -multiple pre-Lie algebras
in terms of T -typed trees with indexed vertices (Theorem 3.17): for example,
1
2
�1 1
2
� 1
32
� 1
2
3
, 1
2
�2 1
2
� 1
2
3
.
We also give a desription of the Koszul dual operad and of its free algebras in Propositions 3.19
and 3.20, generalizing a result of [8].
For any family λ � pλtqtPT with a finite support, the product
λ �
°
λt
t is pre-Lie:
using the Guin–Oudom construction [21, 22], we obtain a Hopf algebraic structure HGLλ
D,T �
pSpgD,T q, �λ,∆q on the symmetric algebra generated by T -typed and D-decorated trees, that is
to say on the space of T -typed and D-decorated forests. The coproduct ∆ is given by partitions
of forests into two forests and the �λ product is given by grafting. For example,
a
b
�λ c � a
b
c � λ a
cb
� λ a
b
c
� λ a
cb
� λ a
b
c
.
In the non-typed case, we get back the Grossman–Larson Hopf algebra of trees [14]. Dually, we
obtain Hopf algebras HCKλ
D,T , generalizing the Connes–Kreimer Hopf algebra [10] of rooted trees.
For example,
∆CKλ
�
a
b �
� a
b
b 1� 1b a
b
� λ a b b,
∆CKλ
�
a
cb �
� a
cb
b 1� 1b a
cb
� λ a
b
b c � λ a
c
b b � λ2 a b b c,
∆CKλ
�
a
cb �
� a
cb
b 1� 1b a
cb
� λ a
b
b c � λ a
c
b b � λ λ a b b c.
This Hopf algebra satisfies a universal property in Hochschild cohomology, as does the Connes–
Kreimer’s Hopf algebra. We describe it in the simpler case where T is finite (Theorem 5.5).
We finally give a second coproduct δ on HCKλ
D,T , such that HCKλ
D,T is a Hopf algebra in the category
of pSpgD,T q,m, δq-right comodules, generalizing the result of [7]. This coproduct δ is given by
a contraction-extraction process. For example, in the non-decorated case,
δp q � b ,
δ
� �
� b � b ,
δ
� �
� b � 2 b � b ,
δ
� �
� b � b � b � b .
We are also interested in morphisms between these objects. We prove that if λ and µ are
both nonzero, then the pre-Lie algebras pgD,T ,
λq and pgD,T ,
µq are isomorphic (Corollary 4.8).
Algebraic Structures on Typed Decorated Rooted Trees 3
Consequently, if λ and µ are both nonzero, the Hopf algebras HGLλ
D,T and HGLµ
D,T are isomorphic;
dually, the Hopf algebras HCKλ
D,T and HCKµ
D,T are isomorphic (Corollary 5.7). Using Livernet’s
rigidity theorem [16] and a nonassociative permutative coproduct defined in Proposition 4.1,
we prove that if λ � 0, then pgD,T ,
λq is, as a pre-Lie algebra, freely generated by a family of
typed trees D1 � T pt0q
D,T satisfying a condition on the type of edges born from the root (Corol-
lary 4.2). As a consequence, the Hopf algebra HCKλ
D,T of typed and decorated trees is isomorphic
to a Connes–Kreimer Hopf algebra of non typed and decorated trees HCK
D1 , and an explicit
isomorphism is described with the help of contraction in Proposition 5.9.
This paper is organized as follows: the first section gives the basic definition of typed rooted
trees and enumeration results, when the number of types and decorations are finite. The second
section is about the T -multiple pre-Lie algebra structures on these trees and the underlying
operads. The freeness of the pre-Lie structures on typed decorated trees and its consequences
are studied in the third section. In the last section, the dual Hopf algebras HGLλ
D,T and HCKλ
D,T
are defined, studied and related to the constructions of Bruned, Hairer and Zambotti [3, 5]:
forgetting the labels, the two coproducts they use on a family of typed and partially decorated
trees are a subquotient of a the construction presented here.
Since the first version of this paper, written in 2018, multiple pre-Lie algebras have appeared
in [4, 6] in a context of SPDEs. When the set of types has more structures (for example a product
making it a commutative semigroup), then other possibilities for grafting products of typed trees
are studied in [13, 18, 25], giving other interesting structures on these objects.
Notation 1.1.
� We denote by K a commutative field of characteristic zero. All the objects (vector spaces,
algebras, coalgebras, pre-Lie algebras, . . . ) in this text will be taken over K.
� For any n P N, we denote by rns the set t1, . . . , nu.
� For any set T , we denote by KT the set of family λ � pλtqtPT of elements of K indexed
by T , and we denote by KpT q the set of elements λ P KT with a finite support. Note that
if T is finite, then KT � KpT q.
2 Typed decorated trees
2.1 Definition
Definition 2.1. Let D and T be two nonempty sets.
1. A D-decorated T -typed forest is a triple pF,dec, typeq, where
� F is a rooted forest. The set of its vertices is denoted by V pF q and the set of its
edges by EpF q.
� dec: V pF q ÝÑ D is a map.
� type: EpF q ÝÑ T is a map.
If the underlying rooted forest of F is connected, we shall say that F is a D-decorated
T -typed tree.
2. If pF,decF , typeF q and pG,decG, typeGq are two D-decorated T -typed forests, they are
isomorphic if there exists a rooted forest isomorphism f from F to G such that for any
vertex v of F , decGpfpvqq � decF pvq and for any edge e of F , typeGpfpeqq � typeF peq
3. For any finite set A, we denote by TT pAq the set of A-decorated T -typed trees T such
that V pT q � A and dec � IdA, and by FT pAq the set of A-decorated T -typed forests F
such that V pF q � A and dec � IdA.
4 L. Foissy
4. For any n ¥ 0, we denote by TD,T pnq the set of isomorphism classes of D-decorated T -
typed trees T such that |V pT q| � n and by FD,T pnq the set of isomorphism classes of
D-decorated T -typed forests F such that |V pF q| � n. We also put
TD,T �
§
n¥0
TD,T pnq, FD,T �
§
n¥0
FD,T pnq.
Example 2.2. We shall represent the decorations of the vertices by letters alongside them. If T
contains two elements, represented by and , then
FD,T p1q � t d , d P Du,
FD,T p2q �
"
a b , a
b
, a
b
, a, b P D
*
,
FD,T p3q �
#
a b c , a
b
c , a
b
c , a
cb
, a
cb
, a
cb
, a
b
c
, a
b
c
, a
b
c
, a
b
c
, a, b, c P D
+
.
Note that for any a, b, c P D,
a b � b a , a
cb
� a
bc
, a
cb
� a
bc
, a
cb
� a
bc
.
Moreover,
FD,T pr1sq � t 1 u,
FD,T pr2sq �
"
1 2 , 1
2
, 2
1
, 1
2
, 2
1
*
,
FD,T pr3sq �
$'''''''''''''''''&
'''''''''''''''''%
1 2 3 , 1
2
3 , 1
3
2 , 2
1
3 , 2
3
1 , 3
1
2 , 3
2
1 ,
1
2
3 , 1
3
2 , 2
1
3 , 2
3
1 , 3
1
2 , 3
2
1 ,
1
32
, 2
31
, 3
21
, 1
32
, 1
23
, 2
31
, 2
13
, 3
21
, 3
12
, 1
32
, 2
31
, 3
21
,
1
2
3
, 1
3
2
, 2
1
3
, 2
3
1
, 3
1
2
, 3
2
1
, 1
2
3
, 1
3
2
, 2
1
3
, 2
3
1
, 3
1
2
, 3
2
1
,
1
2
3
, 1
3
2
, 2
1
3
, 2
3
1
, 3
1
2
, 3
2
1
, 1
2
3
, 1
3
2
, 2
1
3
, 2
3
1
, 3
1
2
, 3
2
1
,/////////////////.
/////////////////-
.
Remark 2.3. If |T | � 1, all the edges of elements of FD,T have the same type: we work with
D-decorated rooted forests. In this case, we shall omit T in the indices describing the forests,
trees, spaces we are considering.
2.2 Enumeration
We assume here that D and T are finite, of respective cardinality D and T . For all n ¥ 0,
we put
tD,T pnq � |TT ,Dpnq|, fD,T pnq � |FT ,Dpnq|,
TD,T pXq �
8̧
n�1
tD,T pnqX
n, FD,T pXq �
8̧
n�0
fD,T pnqX
n.
Algebraic Structures on Typed Decorated Rooted Trees 5
As any element of FT ,D can be uniquely decomposed as the disjoint union of its connected
components, which are elements of TD,T , we obtain
FD,T pXq �
8¹
n�1
1
p1�XnqtD,T pnq
. (2.1)
We put T � tt1, . . . , tT u. For any d P D, we consider
Bd :
#
pFD,T q
T ÝÑ TD,T ,
pF1, . . . , FT q ÞÝÑ BdpF1, . . . , FT q,
where BdpF1, . . . , FT q is the tree obtained by grafting the forests F1, . . . , Fn on a common root
decorated by d; the edges from this root to the roots of Fi are of type ti for any 1 ¤ i ¤ T .
Then Bd is injective, homogeneous of degree 1, and moreover TD,T is the disjoint union of the
Bd
�
pFD,T q
T
�
, d P D. Hence,
TD,T pXq � DXpFD,T q
T � DX
8¹
n�1
1
p1�XnqtD,T pnqT
. (2.2)
Note that (2.2) allows to compute tD,T pnq by induction on n, and (2.1) allows to deduce fD,T pnq.
Lemma 2.4. For any n P N,
tD,T pnq �
tTD,1pnq
T
.
Proof. By induction on n. If n � 1, tD,T p1q � D and tTD,1p1q � TD, which gives the result.
Let us assume the result at all ranks k n. Then tD,T pnqT is the coefficient of Xn in
TDX
n�1¹
k�1
1
p1�XkqtD,T pkqT
� TDX
n�1¹
k�1
1
p1�XkqtTD,1pkq
,
which is precisely tTD,1pnq. ■
Example 2.5. We obtain
tD,T p1q � D,
tD,T p2q � D2T,
tD,T p3q �
D2T p3DT � 1q
2
,
tD,T p4q �
D2T
�
8D2T 2 � 3DT � 1
�
3
,
tD,T p5q �
D2T
�
125D3T 3 � 54D2T 2 � 31DT � 6
�
24
,
tD,T p6q �
D2T
�
162D4T 4 � 80D3T 3 � 45D2T 2 � 10DT � 3
�
15
,
tD,T p7q �
D2T
�
16807D5T 5 � 9375D4T 4 � 5395D3T 3 � 2025D2T 2 � 838DT � 120
�
720
.
We shall give tables of values of tD,T pkq in the appendix.
6 L. Foissy
3 Multiple pre-Lie algebras
We here fix a nonempty set T of edges types.
3.1 Definition
Definition 3.1. A T -multiple pre-Lie algebra is a family pV, p
tqtPT q, where V is a vector space
and for all t P T ,
t is a bilinear product on V such that
@t, t1 P T , @x, y, z P V, x
t1 py
t zq � px
t1 yq
t z � x
t pz
t1 yq � px
t zq
t1 y.
Remark 3.2. For any t P T , pV,
tq is a pre-Lie algebra. More generally, for any family
λ � pλtqtPT P KpT q, putting
λ �
°
λt
t, pV,
λq is a pre-Lie algebra.
Proposition 3.3. Let D be any set; we denote by gD,T the vector space generated by TD,T . For
any T, T 1 P TD,T , v P V pT q and t P T , we denote by T
pvq
t T 1 the D-decorated T -typed tree
obtained by grafting T 1 on v pthat is to say adding an edge between v and the root of T 1q, the
created edge being of type t. We then define a product
t on gD,T by
@T, T 1 P TD,T , T
t T
1 �
¸
vPV pT q
T
pvq
t T 1.
Then pgD,T , p
tqtPT q is a T -multiple pre-Lie algebra.
Proof. Let T , T 1, T 2 be elements of TD,T and t1, t2 P T .
pT
t1 T
1q
t2 T
2 � T
t1 pT
1
t2 T
2q
�
¸
vPV pT q,v1PV pT q\V pT 1q
�
T
pvq
t1 T 1
�
pv1q
t2 T 2 �
¸
vPV pT q,v1PV pT 1q
T
pvq
t1
�
T 1
pv1q
t2 T 2
�
�
¸
vPV pT q,v1PV pT q
�
T
pvq
t1 T 1
�
pv1q
t2 T 2�
¸
vPV pT q,v1PV pT 1q
�
T
pvq
t1 T 1
�
pv1q
t2 T 2� T
pvq
t1
�
T 1
pv1q
t2 T 2
�
�
¸
vPV pT q,v1PV pT q
�
T
pvq
t1 T 1
�
pv1q
t2 T 2
�
¸
vPV pT q,v1PV pT q
�
T
pv1q
t2 T 2
�
pvq
t1 T 1
� pT
t2 T
2q
t1 T
1 � T
t2 pT
2
t1 T
1q.
So gD,T is indeed a T -multiple pre-Lie algebra. ■
Example 3.4. If a, b, c P D and , P T ,
a
b
c � a
cb
� a
b
c
, a
b
c � a
cb
� a
b
c
.
3.2 Guin–Oudom extension of the pre-Lie products
Notation 3.5. Let pBtqtPT be a family of formal symbols indexed by T . For any vector space V ,
we denote
V `T � V bVectpBt, t P T q.
Then
V `T �
à
tPT
V b Bt.
In order to enlighten the notations, we write vBt instead of v b Bt for any v P V and for any
t P T .
Algebraic Structures on Typed Decorated Rooted Trees 7
Lemma 3.6. If for any t P T ,
t is a bilinear product on a vector space V , we define
:�
V `T �b2
ÝÑ V `T by
xBt
x
1Bt1 � px
t1 yqBt.
Then pV, p
tqtPT q is a T -multiple pre-Lie algebra if, and only if,
�
V `T ,
�
is a pre-Lie algebra.
Proof. Let x, x1, x2 P V , t, t1, t2 P T . Then
xBt
px
1Bt1
x
2Bt2q � pxBt
x
1Bt1q
x
2Bt2 �
�
px
t1 x
1q
t2 x
2 � x
t1 px
1
t2 x
2q
�
Bt,
which implies the result. ■
Notation 3.7. The symmetric algebra SpV q is given with its usual coproduct ∆, making it
a bialgebra:
@x P V, ∆pxq � xb 1� 1b x.
We shall use Sweedler’s notation: for any w P SpV q, ∆pwq �
°
wp1q b wp2q. The counit of this
coproduct is denoted by ε: this is the unique algebra morphism from SpV q to K sending any
v P V to 0.
Theorem 3.8. Let V be a T -multiple pre-Lie algebra. One can define a product
: SpV q b S
�
V `T � ÝÑ SpV q
in the following way: for any u, v P SpV q, w P S
�
V `T �, x P V , t P T ,
1
w � εpwq,
u
1 � u,
uv
w �
¸�
u
wp1q
��
v
wp2q
�
,
u
wpxBtq � pu
wq
t x� x
pw
t xq,
where
t is extended to SpV q b V and S
�
V `T �b V by the following: for any x1, . . . , xk, x P V ,
for any t1, . . . , tk P T ,
x1 � � �xk
t x �
ķ
i�1
x1 � � � pxi
t xq � � �xk,
px1Bt1q � � � pxkBtkq
t x �
ķ
i�1
px1Bt1q � � � ppxi
t xqBtiq � � � pxkBtkq.
Proof. Uniqueness. The last formula allows to compute x
w for any x P V and w P S
�
V `T �
by induction on the length of w; the other ones allow to compute u
w for any u P SpV q by
induction on the length on u. So this product
is unique.
Existence. Let us use the Guin–Oudom construction [21, 22] on the pre-Lie algebra V bT .
We obtain a product
defined on S
�
V `T � such that for any u, v, w P S
�
V `T �, x P V `T :
1
w � εpwq,
u
1 � u,
uv
w �
¸�
u
wp1q
��
v
wp2q
�
,
u
wx � pu
wq
x� x
pw
xq.
8 L. Foissy
Let f : T ÝÑ K be any nonzero map. We consider the surjective algebra morphism F : S
�
V `T �
ÝÑ SpV q, sending xBt to fptqx for any x P V , t P T . Its kernel is generated by the elements
Xt,t1x � pfpt1qBt�fptqBt1qx, where x P V and t, t1 P T . We denote by J the vector space generated
by the elements Xt,t1x. Let us prove that for any w P S
�
V `T �, J
w � J by induction on the
length n of w. If n � 0, we can assume that w � 1 and this is obvious. If n � 1, we can assume
that w � x1Bt2 . Then
Xt,t1x
w � pfpt1qBt � fptqBt1qx
t2 x
1 � Xt,1t1x
t2 x
1 P J.1
Let us assume the result at rank n� 1. We can assume that w � w1x1Bt, the length of w1 being
n� 1. For any x P J ,
x
w � px
w1q
x1 � x
pw1
x1q.
The length of w1 and w1
x1 is n�1, so x
w1 and x
pw1
x1q belong to J . From the case n � 1,
px
w1q
x1 P J , so x
w P J .
For any x P J , u, v P S
�
V `T �,
xu
v �
�
x
vp1q
�loooomoooon
PJ
�
u
vp2q
�
P KerpF q.
This proves that KerpF q
S
�
V `T � � KerpF q. Hence,
induces a product also denoted by
,
defined from SpV qbS
�
V bT � to SpV q. It is not difficult to show that it does not depend on the
choice of f and satisfies the required properties. ■
Definition 3.9. Let d P D, T1, . . . , Tk P TD,T , t1, . . . , tk P T . We denote by
Bd
� ¹
iPrks
TiBti
the T -typed D-decorated tree obtained by grafting T1, . . . , Tk on a common root decorated by d,
the edge between this root and the root of Ti being of type ti for any i. This defines a map
Bd : S
�
VectpTD,T q
`T � ÝÑ SpVectpTD,T qq.
Lemma 3.10. For any d P D, T1, . . . , Tk P TD,T , t1, . . . , tk P T ,
Bd
� ¹
iPrks
TiBti
� d
¹
iPrks
TiBti .
Proof. We write F �
±
iPrks TiBti : the integer k is unique and denoted by ℓpF q. We proceed
by induction on ℓpF q. If ℓpF q � 0, then F � 1 and d
1 � d � Bdp1q. let us assume the
result for any forest F 1 with ℓpF 1q � ℓpF q � 1. Putting k � ℓpF q, we can write F � F 1TBt, with
ℓpF 1q � ℓpF q � 1, T � Tk and t � tk. Then
d
F � p d
F 1q
TBt � d
pF 1
TBtq
� BdpF
1q
t T �BdpF
1
t T q
� BdpF
1TBtq �BdpF
1
t T q �BdpF
1
t T q
� BdpF q.
So the result holds for all forests. ■
Algebraic Structures on Typed Decorated Rooted Trees 9
Corollary 3.11. Let A be a T -multiple pre-Lie algebra and, for any d P D, ad P A. There exists
a unique T -multiple algebra morphism ϕ : gD,T ÝÑ A, such that for any d P D, ϕp d q � ad.
In other words, gT ,D is the free T -multiple pre-Lie algebra generated by D.
Proof. Uniqueness. Using the Guin–Oudom product and lemma 3.10, ϕ is the unique linear
map inductively defined by
ϕ
�
Bd
� ¹
iPrks
TiBti
� ad
¹
iPrks
ϕpTiqBti .
Existence. Let T, T 1 P TD,T and t P T . Let us prove that ϕpT
t T
1q � ϕpT q
t ϕpT
1q by
induction on n � |T |. If n � 1, we assume that T � d . Then T
t T
1 � BdpT
1Btq, so
ϕpT
t T
1q � ad
pϕpT
1qBt � ad
t ϕpT
1q � ϕpT q
t ϕpT
1q.
Let us assume the result at all ranks |T |. We put
T � Bd
� k¹
i�1
TiBti
.
By definition of the pre-Lie product of gD,T in terms of grafting,
T
T 1 � Bd
� k¹
i�1
TiBtiT
1Bt
�
ķ
j�1
Bd
�¹
i�j
TiBtipTj
t T
1qBtj
,
ϕpT
T 1q � ad
k¹
i�1
ϕpTiqBtiϕpT
1qBt �
ķ
j�1
ad
¹
i�j
ϕpTiqBtipϕpTj
t T
1qqBtj
� ad
k¹
i�1
ϕpTiqBtiϕpT
1qBt �
ķ
j�1
ad
¹
i�j
ϕpTiqBtipϕpTjq
t ϕpT
1qqBtj
� ad
k¹
i�1
ϕpTiqBtiϕpT
1qBt � ad
�� k¹
i�1
ϕpTiqBti
ϕpT 1qBt
�
�
ad
k¹
i�1
ϕpTiqBti
ϕpT 1qBt
� ϕpT q
t ϕpT
1q.
So ϕ is a T -multiple pre-Lie algebra morphism. ■
3.3 Operad of typed trees
We now describe an operad of typed trees, in the category of species. We refer to [2, 17, 19] for
notations and definitions on operads.
Notation 3.12. Let A be a finite set. If T P TT pAq and a P T :
1. The subtrees formed by the connected components of the set of vertices, descendants of a
(a excluded) are denoted by T
paq
1 , . . . , T
paq
na . The type of the edge from a to the root of T
paq
i
is denoted by ti.
2. The tree formed by the vertices of T which are not in T
paq
1 , . . . , T
paq
na , at the exception of a,
is denoted by T
paq
0 .
10 L. Foissy
Example 3.13. Let us consider the following tree:
T � d
c
b
a
e f g
h
i j k l
m
with a, . . . ,m P D, then
T
paq
0 � d
cb
,
T
paq
1 , . . . , T paqn
(
�
#
e , f
i
, g
j
m
, h
lk
+
.
Proposition 3.14. For any nonempty finite set A, we denote by PT pAq the vector space gene-
rated by TT pAq. We define a composition � on PT in the following way: for any T P TT pAq,
T 1 P TT pBq and a P A,
T �a T
1 �
¸
v1,...,vnaPV pT
1q
�
� � �
��
T
paq
0
pt0q
a1 T 1
�
pt1qv1 T
paq
1
�
� � �
�
ptna q
vna
T paqna
,
where a1 is the direct ascendant of a in T and t0 is the type of the edge between a1 and a. If a
is the root of T , by convention T
paq
0
pt0q
a1 T 1 � T 1. With this composition, PT is an operad in the
category of species.
Proof. Note that the tree
�
� � �
��
T
paq
0
pt0q
λ T 1
�
pt1q
v1 T
paq
1
�
� � �
�
pt
paq
na q
vna
Tna , which is shortly denoted
by T
pvq
λ T 1, is obtained in the following process:
1. Delete the branches T
paq
1 , . . . , T
paq
na coming from a in T . One obtains a tree T 2, and a is
a leaf of T 2.
2. Identify a P V pT 2q with the root of T 1. One obtains a tree T3.
3. Graft T
paq
1 on the vertex v1 of T
3v with an edge of type t1, . . . , graft T
paq
na on the vertex vna
of T3 with an edge of type tn. The obtained tree is T
pvq
λ T 1.
This obviously does not depend on the choice of the indexation of T
paq
1 , . . . , T
paq
na .
Let T P TT pAq, T
1 P TT pBq, T
2 P TT pCq.
� If a1, a2 P A, with a1 � a2, then
pT �a1 T
1q �a2 T
2 �
¸
v1PV pT 1qna1 ,v2PV pT 2qna2
�
T
pv1q
a1 T 1
�
pv2q
a2 T 2
�
¸
v1PV pT 1qna1 ,v2PV pT 2qna2
�
T
pv2q
a2 T 2
�
pv1q
a1 T 1
� pT �a2 T
2q �a1 T
1.
� If a1 P A and b2 P B, then
pT �a1 T
1q �b2 T
2 �
¸
v1PV pT 1qna1 ,v2PV pT 2qnb2
�
T
pv1q
a1 T 1
�
pv2q
b2 T 2
�
¸
v1PV pT 1qna1 ,v2PV pT 2qnb2
T
pv1q
a1
�
T 1
pv2q
b2 T 2
�
� T �a1 pT
1 �b2 T
2q.
Algebraic Structures on Typed Decorated Rooted Trees 11
Moreover, a
λ T � T for any tree T , and if a P V pT q, T
λ a T . So PT is indeed an operad
in the category of species. ■
Consequently, the family pPT pnqqn¥0 is an operad in the category of vector spaces, which we
denote by PT .
Example 3.15.
1
2
�1 1
2
� 1
32
� 1
2
3
, 1
2
�2 1
2
� 1
2
3
.
Remark 3.16. Another operad on typed trees is introduced in [11]. It is a typed version of the
operad of nonassociative, permutative operad of [16], and is different from ours.
In the non-typed case, this theorem is proved in [9]:
Theorem 3.17. The operad of T -multiple pre-Lie algebras is isomorphic to PT , via the iso-
morphism Φ sending, for any t P T ,
t to the tree 1
2
, where the edge is of type t.
Proof. The operad of T -multiple pre-Lie algebras is generated by the binary elements
t, t P T ,
with the relations
@t, t1 P T ,
t1 �2
t �
t �1
t1 � p
t �2
t1 �
t1 �1
tq
p23q,
where in the right side we used the action of the symmetric group S3 on T p3q, and more
specifically the action of the transposition p23q. Firstly, if t and t1 are elements of T , symbolized
by and , by the preceding example:
1
2
�1 1
2
� 1
2
�2 1
2
� 1
32
�
�
1
32 p23q
�
�
1
2
�1 1
2
� 1
2
�2 1
2 p23q
.
So the morphism ϕ exists. Let us prove that it is surjective: let T P TT pnq, we show that it
belongs to ImpΦq by induction on n. It is obvious if n � 1 or n � 2. Let us assume the result
at all ranks n. Up to a reindexation we assume that
T � B1pT1Bt1 � � �TkBtkq,
where for any 1 ¤ i j ¤ k, if x P V pTiq and y P V pTjq, then x y. We denote by T 1i the
standardization of Ti. By the induction hypothesis on n, T 1i P ImpΦq for all i. We proceed by
induction on k. The type tk will be represented in red. If k � 1, then
T � 1
2
�2 T1 P ImpΦq.
Let us assume the result at rank k � 1. We put T 1 � B1pT1Bt1 � � �Tk�1Btk�1
q. By the induction
hypothesis on n, T 1 P ImpΦq. Then
1
2
�1 T
1 � T � x,
where x is a sum of trees with n vertices, such that the fertility of the root is k � 1. Hence,
x P ImpΦq, so T P ImpΦq.
12 L. Foissy
Let D be a set. The morphism ϕ implies that the free PT-algebra generated by D, that is to
say gD,T , inherits a T -multiple pre-Lie algebra structure defined by
@x, y P gD,T , @ P T , x � y � 1
2
� pxb yq,
where � is the PT -algebra structure of gD,T . For any trees T , T 1 in TD,T , by definition of the
operadic composition of PT ,
T �t T
1 �
¸
vPV pT q
T
pvq
t T 1,
so �t �
t for any t. As pgD,T , p
tqtPT q is the free T -multiple pre-Lie algebra generated by D, Φ is
an isomorphism. ■
Remark 3.18. Let us assume that T is finite, of cardinality T . Then the components of PT are
finite-dimensional. As the number of rooted trees which vertices are the elements of rns is nn�1,
for any n ¥ 0 the dimension of PT pnq is T
n�1nn�1, and the formal series of PT is
fT pXq �
¸
n¥1
dimpPT pnqq
n!
Xn �
¸
n¥1
pTnqn�1
n!
Xn �
f1pTXq
T
.
3.4 Koszul dual operad
If T is finite, then PT is a quadratic operad. Its Koszul dual can be directly computed:
Proposition 3.19. The Koszul dual operad P !
T of PT is generated by �t, t P T , with the
relations
@t, t1 P T , �t1 �1 �t � �t �2 �t1 , �t1 �1 �t � p�t �1 �t1q
p23q.
The algebras on P !
T are called T -multiple permutative algebras. Such an algebra A is given with
the bilinear products �t, t P T , such that
@x, y, z P A, px �t yq �t1 z � x �t py �t1 zq, px �t yq �t1 z � px �t1 zq �t y.
In particular, for any t, �t is a permutative product.
Of course, the definition of T -multiple permutative algebras makes sense even if T is infinite.
Permutative algebras are introduced in [8]. If A is a T -multiple permutative algebra, then for
any pλtqtPT P KpT q, �a �
°
λt�t is a permutative product on A.
Proposition 3.20. Let V be a vector space. Then V b S
�
V `T � is given with a T -multiple
permutative algebra structure:
@t P T , v, v1 P V, w,w1 P S
�
V `T �, pv b wq �t pv
1 b w1q � v b ww1pv1Btq.
This T -multiple permutative algebra is denoted by PT pV q. For any T -multiple permutative
algebra V and any linear map ϕ : V ÝÑ A, there exists a unique morphism Φ: PT pV q ÝÑ A
such that for any v P V , Φpv b 1q � ϕpvq.
Algebraic Structures on Typed Decorated Rooted Trees 13
Proof. Let t, t1 P T , v, v, v2 P V , w, w1, w2 P S
�
V `T �.
pv b w �t v
1 b w1q �t1 v
2 b w2 � v b w �t pv
1 b w1 �t1 v
2 b w2q
� pv b w �t v
1 �t1 v
2 b w2q b w1
� v b ww1w2pv1Btqpv
2Bt1q,
so PT pV q is T -multiple permutative.
Existence of Φ. Let t1, . . . , tk P T , v, v1, . . . , vk P V . We inductively define Φpv b pv1Bt1q � � �
pvkBtkqq by
Φpv b 1q � ϕpvq,
Φpv b pv1Bt1q � � � pvkBtkqq � Φpv b pv1Bt1q � � � pvk�1Btk�1
qq �tk ϕpvkq if k ¥ 1.
Let us prove that this does not depend on the order chosen on the factors viBti by induction
on k. If k � 0 or 1, there is nothing to prove. Otherwise, if i k,
Φpv b pv1Bt1q � � � pvi�1Bti�1qpvi�1Bti�1q � � � pvkBtkqq �ti ϕpviq
� pΦpv b pv1Bt1q � � � pvi�1Bti�1qpvi�1Bti�1q � � � pvk�1Btk�1
qq �tk ϕpvkqq �ti ϕpviq
� pΦpv b pv1Bt1q � � � pvi�1Bti�1qpvi�1Bti�1q � � � pvk�1Btk�1
qq �ti ϕpviqq �tk ϕpvkq
� Φpv b pv1Bt1q � � � pvk�1Btk�1
qq �tk ϕpvkq
� Φpv b pv1Bt1q � � � pvkBtkqq.
So Φ is well-defined. Let us prove that Φ is a T -multiple permutative algebra morphism. Let
v, v1 P V , w, w1 � pv1Bt1q � � � pvkBtkq P S
�
V `T �, and t P T . Let us prove that Φpvbw�tv
1bw2q �
Φpv b wq �t Φpv
1 b w1q by induction on k. If k � 0,
Φpv b w �t v
1 b 1q � Φpv b wpv1Btqq
� Φpv b wq �t ϕpv
1q
� Φpv b wq �t Φpv
1 b 1q.
Otherwise, we put w2 � pv1Bt1q � � � pvk�1Btk�1
q. Then
Φpv b w �t v
1 b w1q � Φpv b ww2pv1BtqpvkBtkqq
� Φpv b ww2pv1Btqq �tk ϕpvkq
� Φpv b w �t v
1 b w2q �tk ϕpvkq
� pΦpv b wq �t Φpv
1 b w2qq �tk ϕpvkq
� Φpv b wq �t pΦpv
1 b w2q �tk ϕpvkqq
� Φpv b w1q �t Φpv
1 b w1q.
So Φ is a T -multiple permutative algebra morphism.
Uniqueness. For any v, v1, . . . , vk P V , t1, . . . , tk P T ,
v b pv1Bt1q � � � pvkBtkq � pv b pv1Bt1q � � � pvk�1Btk�1
qq �tk vk.
It is then easy to prove that PT pV q is generated by V b 1 as a T -multiple permutative algebra.
Consequently, Φ is unique. ■
14 L. Foissy
Remark 3.21.
1. We proved that PT pV q is freely generated by V , identified with V b 1. Consequently,
P !
T pnq has the same dimension as the multilinear component of V b S
�
V `T � with V �
VectpX1, . . . , Xnq, that is to say
Vect
�
Xi b pX1Bt1q � � � pXi�1Bti�1qpXi�1Bti�1q � � � pXnBtnq, 1 ¤ i ¤ n, tj P T
�
,
so
dimpP !
T pnqq � nTn�1.
The formal series of P !
T is
f !T pXq �
¸
n¥1
dimpP !
T pnqq
n!
Xn �
¸
n¥1
Tn�1
pn� 1q!
Xn � XexppTXq �
f !1pTXq
T
.
2. It is possible to prove that P !
T is a Koszul operad (and, hence, PT too) using the rewriting
method of [17].
4 Structure of the pre-Lie products
4.1 A nonassociative permutative coproduct
For all t P T , we define a coproduct ρt : gD,T ÝÑ gb2
D,T by
@T � Bd
� ¹
iPrks
TiBti
P TD,T , ρtpT q �
¸
jPrks
δt,tjBd
� ¹
iPrks, i�j
TiBti
b TjBt.
Proposition 4.1.
1. For all t, t1 P T , pρt b Idq � ρt1 � ppρt1 b Idq � ρtq
p23q, where in the right side we use the
classical action of the symmetric group S3 on gb3
D,T by permutations of the tensors, and
more specifically the action of the transposition p23q. With Sweedler’s notation for ρt, this
can be written, for any x P gD,T , as¸¸�
xp1qt1
�p1qt b �
xp1qt1
�p2qt b xp2qt1 �
¸¸�
xp1qt
�p1qt1 b xp2qt b
�
xp1qt
�p2qt1 .
2. For any x, y P gD,T , t, t
1 P T , with Sweedler’s notations ρtpxq �
°
xp1qt b xp2qt,
ρtpx
t1 yq � δt,t1xb y �
¸
xp1qt
t1 y b xp2qt �
¸
xp1qt b xp2qt
t1 y.
3. For any µ � pµtqtPT P KT , we put
ρµ �
¸
tPT
µtρt : gD,T ÝÑ gb2
D,T .
This makes sense, as any tree in TD,T does not vanish only under a finite number of ρt.
Then ρµ is a nonassociative permutative pNAPq coproduct; for any x, y P gD,T , by the
second point, using Sweedler’s notation for ρµ,
ρµpx
λ yq �
� ¸
tPT
λtµt
xb y �
¸
xp1qµ
λ y b xp2qµ �
¸
xp1qµ b xp2qµ
λ y.
In particular, if
°
tPT λtµt � 1, pgD,T ,
λ, ρµq is a NAP pre-Lie bialgebra in the sense
of [16].
Algebraic Structures on Typed Decorated Rooted Trees 15
Proof. 1. For any tree T ,
pρt b Idq � ρt1pT q �
¸
p,qPrks,p�q
δtp,tδtq ,t1Bd
� ¹
iPrks,i�p,q
TiBti
b TpBt b TqBt1 ,
which implies the result.
2. For any tree T , T 1,
ρtpT
t1 T
1q � ρt
�
Bd
� ¹
iPrks
TiBtiT
1Bt1
�
¸
iPrks
Bd
� ¹
jPrks,j�i
TjBtj pTi
t1 T
1qBti
� δt,t1Bd
� ¹
iPrks
TiBti
b T 1 �
¸
iPrks
δti,tBd
� ¹
jPrks,j�i
TjBtjT
1Bt1
b TiBt
�
¸
iPrks
δti,tBd
� ¹
jPrks,j�i
TjBtj
b pTi
t1 T
1qBt
�
¸
i�jPrks
δti,tBd
� ¹
pPrks,p�i,j
TpBtppTj
t1 T
1qBtj
b TiBt
� δt,t1T b T 1 �
¸
iPrks
δti,tBd
� ¹
jPrks,j�i
TjBtj
t1 T
1 b TiBt
�
¸
iPrks
δti,tBd
� ¹
jPrks,j�i
TjBtj
b Ti
t1 T
1Bt
� δt,t1T b T 1 � T p1qt
t1 T
1 b T p2qt � T p1qt b T p2qt
t1 T
1.
3. Obtained by summation. ■
Corollary 4.2. If λ P KpT q is nonzero, let us choose t0 P T such that λt0 � 0. The pre-Lie
algebra pgD,T ,
λq is freely generated by the set Tpt0qD,T of T -typed D-decorated trees T such that
there is no edge outgoing the root of T of type t0.
Proof. For any tree T , we denote by αT the number of edges outgoing the root of T of type T0.
Our aim is to prove that pgD,T ,
λq is freely generated by the trees T such that αT � 0. We define
a family of scalars pµtqtPT by
@t P T , µt �
$&
%
0 if t � t0,
1
λt0
if t � t0.
Note that ρµ � 1
λt0
ρt0 . By Proposition 4.1, pgD,T ,
λ, ρµq is a NAP pre-Lie bialgebra, so by
Livernet’s rigidity theorem [16], it is freely generated by Kerpρµq � Kerpρt0q. Obviously, if
αT � 0, T P Kerpρt0q. Let us consider x �
°
TPTD,T
xTT P Kerpρt0q. We consider the map
Υ:
#
gD,T b gD,T ÝÑ gD,T ,
T b T 1 ÞÝÑ T
rootpT q
t0
T 1.
By definition of ρt0 , for any tree T , Υ � ρt0pT q � αTT . Consequently,
0 � Υ � ρt0pxq �
¸
TPTD,T
xTαTT.
So if αT � 0, xT � 0, and x is a linear span of trees such that αT � 0: the set of trees T such
that αT � 0 is a basis of Kerpρt0q. ■
16 L. Foissy
If |D| � D and |T | � T , the number of elements of Tpt0qD,T of degree n is denoted by t1D,T pnq;
it does not depend on t0. By direct computations,
t1D,T p1q � D,
t1D,T p2q � D2pT � 1q,
t1D,T p3q �
D2pT � 1qp3DT �D � 1q
2
,
t1D,T p4q �
D2pT � 1q
�
16D2T 2 � 8D2T �D2 � 6DT � 3D � 2
�
6
.
In the particular case D � 1, T � 2, we recover sequence A005750 of the OEIS.
4.2 Pre-Lie algebra morphisms
Notation 4.3. Let T and T 1 be two sets of types. We denote byMT ,T 1pKq the space of matrices
M � pmt,t1qpt,t1qPT �T 1 , such that for any t1 P T 1, pmt,t1qtPT P KpT q. If T � T 1, we shall simply
write MT pKq. If M P MT ,T 1pKq and M 1 PMT 1,T 2pKq, then
MM 1 �
� ¸
t1PT 1
mt,t1m
1
t1,t2
pt,t2qPT �T 2
P MT ,T 2pKq.
If λ P KpT 1q and µ P KT , then
Mλ �
� ¸
t1PT 1
mt,t1λt1
tPT
P KpT q, MJµ �
� ¸
tPT
mt,t1µt
t1PT 1
P KT 1
.
In particular, MT pKq is an algebra, acting on KpT q on the left and on KT on the right.
Definition 4.4. Let M P MT ,T 1pKq. We define a map ΦM : HD,T 1 ÝÑ HD,T , sending F P
FD,T to the forest obtained by replacing typepeq by
°
tPT mt,typepeqt for any e P EpF q, F being
considered as linear in any of its edges. The restriction of ΦM to gD,T 1 is denoted by ϕM :
gD,T 1 ÝÑ gD,T .
Example 4.5. If T contains two elements, the first one represented by and the second one
by , if M �
�
α β
γ δ
, for any x, y, z P D,
ϕM
�
x
y �
� α x
y
� γ x
y
,
ϕM
�
x
y �
� β x
y
� δ x
y
,
ϕM
�
x
zy �
� αβ x
zy
� αδ x
zy
� βγ x
zy
� γδ x
zy
.
Remark 4.6. For any M P MT ,T 1pKq, M 1 P MT 1,T 2pKq, ΦM � ΦM 1 � ΦMM 1 .
Proposition 4.7. Let λ P KpT q, µ P KT and M P MT ,T 1pKq. Then ϕM is a pre-Lie morphism
from pgD,T 1 ,
λq to pgD,T ,
Mλq and a NAP coalgebra morphism from pgD,T 1 , ρMJµq to pgD,T , ρµq.
Proof. Let T, T 1 P TD,T . For any t P T , for any v P V pT q,
ϕM
�
T
pvq
t T 1
�
�
¸
t1PT
mt1,tϕM pT q
t1 ϕM pT 1q,
so
ϕM pT
λ T
1q �
¸
t,t1PT
mt1,tλtϕM pT q
t1 ϕM pT 1q � ϕM pT q
Mλ ϕM pT 1q.
We proved that ϕM is a pre-Lie algebra morphism from pgD,T 1 ,
λq to pgD,T ,
Mλq.
Algebraic Structures on Typed Decorated Rooted Trees 17
For any T P TD,T ,
ρt � ϕM pT q �
¸
t1PT
mt,t1pϕM b ϕM q � ρt1pT q,
so
ρµ � ϕM pT q �
¸
t,t1PT
mt,t1µtpϕM b ϕM q � ρt1pT q � pϕM b ϕM q � ρMJµpT q.
So ϕM : pgD,T 1 , ρMJµq ÝÑ pgD,T , ρµq is a NAP coalgebra morphism. ■
Corollary 4.8. For any λ P KpT q and µ P KT , such that
°
tPT λtµt � 1, for any t0 P T , the
NAP pre-Lie bialgebras pgD,T ,
λ, ρµq and pgD,T ,
t0 , ρt0q are isomorphic.
Proof. Let us denote by λp0q the element of KpT q defined by
λ
p0q
t � δt,t0 .
Note that for any M P MT pKq, invertible, ϕM : pgD,T ,
λp0q , ρMJµq ÝÑ pgD,T ,
Mλp0q , ρµq is
an isomorphism. In particular, for a well-chosen M , Mλp0q � λ; we can assume that λ � λp0q
without loss of generality. Then, by hypothesis, µt0 � 1. We define a matrixM P MT pKq in the
following way:
mt,t1 �
#
δt,t0 if t1 � t0,
δt,t1 � µt1δt,t0 otherwise.
Then M is invertible. Moreover, Mλp0q � λp0q and MJµ � λp0q. So ϕM is an isomorphism from
pgD,T ,
λp0q , ρλp0qq to pgD,T ,
λ, ρµq. ■
Proposition 4.9. Let λ P KpT q, and t0 P T . We define a pre-Lie algebra morphism ψt0 :
pgTpt0qD,T
,
q ÝÑ pgD,T ,
λq, sending T to T for any T P Tpt0qD,T . Then ψt0 is a pre-Lie algebra
isomorphism if, and only if, λt0 � 0.
Proof. If λt0 � 0, then by corollary 4.2, pgD,T ,
λq is freely generated by Tpt0qD,T , so ψt0 is
an isomorphism. If λt0 � 0, then it is not difficult to show that any tree T with two vertices,
with its unique edge of type t0, does not belong to Impψt0q. ■
5 Hopf algebraic structures
We here fix λ P KpT q.
5.1 Enveloping algebra of gD,T
Using again the Guin–Oudom construction, we obtain the enveloping algebra of pgD,T ,
λq.
We first identify the symmetric coalgebra SpgD,T q with the vector space generated by FD,T ,
which we denote by HD,T . Its product m is given by disjoint union of forests, its coproduct by
@T1, . . . , Tk P TD,T , ∆pT1 � � �Tnq �
¸
I�rns
¹
iPI
Ti b
¹
iRI
Ti.
We denote by
λ the Guin–Oudom extension of
λ to HD,T and �λ the associated associative
product.
18 L. Foissy
Theorem 5.1. For any F P FD,T , T1, . . . , Tn P TD,T ,
F
λ T1 � � �Tn �
¸
v1,...,vnPV pF q,
t1,...,tnPT
� ¹
iPrns
λti
�
� � �
�
F
pv1q
t1
T1
�
� � �
�
pvnq
tn Tn,
F �λ T1 � � �Tn �
¸
I�rns
�
F
λ
¹
iPI
Ti
¹
iRI
Ti.
The Hopf algebra pHD,T , �λ,∆q is denoted by HGLλ
D,T . Moreover, for any M P MT ,T 1pKq, for
any λ P KpT 1q, ΦM is a Hopf algebra morphism from HGLλ
D,T 1 to HGLMλ
D,T . The extension of ψt0 as
a Hopf algebra morphism from HGL
Tpt0qD,T
to HGLλ
D,T is denoted by Ψt0; it is an isomorphism if, and
only if, λt0 � 0.
In particular, if T � ttu and λt � 1, we recover the Grossman–Larson Hopf algebra [14].
5.2 Dual construction
Proposition 5.2. Let T P TD,T .
1. A cut c of T is a nonempty subset of EpT q; it is said to be admissible if any path in the
tree from the root to a leaf meets at most one edge in c. The set of admissible cuts of T is
denoted by AdmpT q.
2. If c is admissible, one of the connected components of T zc contains the root of c: we denote
it by RcpT q. The product of the other connected components of T zc is denoted by P cpT q.
Let λ P KT . We define a multiplicative coproduct ∆CKλ on the algebra pHD,T ,mq by
@T P TD,T , ∆CKλpT q � T b 1� 1b T �
¸
cPAdmpT q
�¹
ePc
λtypepeq
RcpT q b P cpT q.
Then
�
HD,T ,m,∆
CKλ
�
is a Hopf algebra, which we denote by HCKλ
D,T .
Proof. We first assume that λ P KpT q. Let us define a nondegenerate pairing x�,�y on HD,T
by
@F, F 1 P FD,T , xF, F 1y � δF,F 1sF ,
where sF is the number of symmetries of F . Let us consider three forests F , F 1, F 2. We put
F �
¹
TPTD,T
T λt , F 1 �
¹
TPTD,T
T a1T , F 2 �
¹
TPTD,T
T a2T .
Then
x∆pF q, F 1 b F 2y �
¸
a�b�c
¹
TPTD,T
λt!
µt!cT !
B ¹
TPTD,T
Tµt , F 1
FB ¹
TPTD,T
T cT , F 2
F
�
¸
a�b�c
δb,a1δc,a2
λt!
a1T !a
2
T !
sF 1sF 2 � δa,a1�a2
λt!
a1T !a
2
T !
a1T !a
2
T !s
a1T�a2T
T
� δa,a1�a2λt!s
λt
T � δF,F 1F 2sF
� xF, F 1F 2y.
Algebraic Structures on Typed Decorated Rooted Trees 19
Therefore,
@x, y, z P HD,T , x∆pxq, y b zy � xx, yzy.
Let F , G be two forests and T be a tree. Observe that if F is a forest with at least two trees,
then F �λ G does not contain any tree, so xF �λ G,T y � 0. If F � 1, then xF �λ G,T y � 0 if,
and only if, G � T ; moreover, x1 �λ T, T y � 1. If F is a tree, then
xF �λ G,T y � xF
λ G,T y.
Moreover, if F � BdpF
1q and G � T1 � � �Tk,
F
λ G �
¸
I�rks
¸
ptiqPT k
� ¹
iPrks
λti
Bd
�¹
iPI
TiBtiF
1
¹
iRI
TiBti
,
where
is the pre-Lie product on gTD,T induced by the T -multiplie pre-Lie structure. Conse-
quently, we can inductively define a coproduct ∆CKλ : HD,T ÝÑ HD,T b HD,T , multiplicative
for the product m, such that, if we denote for any tree T , ∆CKpT q � ∆pT q� 1bT , for any tree
T � BdpT1Bt1 � � �TkBtkq,
∆
CK
λ pT q � pBd b Idq
� ¹
iPrks
�
∆
CK
λ pTiqBti b 1� λti1b Ti
.
Then, for any x, y, z P HD,T ,
xx �λ y, zy �
@
xb y,∆CKλpzq
D
.
A quite easy induction on the number of vertices of trees proves that this coproduct is indeed the
one we define in the statement of the proposition. As x�,�y is nondegenerate,
�
HD,T ,m,∆
CKλ
�
is a Hopf algebra, dual to HGLλ
D,T .
In the general case, for any x P HD,T , there exists a finite subset T 1 of T such that x P HD,T 1 .
Putting λ1 � λ|T 1 , λ1 P KT 1
� KpT 1q, so�
∆CKλ b Id
�
�∆CKλpxq �
�
∆CKλ1 b Id
�
�∆CKλ1 pxq
�
�
Idb∆CKλ1
�
�∆CKλ1 pxq
�
�
Idb∆CKλ
�
�∆CKλpxq.
Hence, ∆λ is coassociative, and HCKλ
D,T is a Hopf algebra. ■
Example 5.3. Let us fix a subset T 1 of T and choose pλtqtPT such that
λt �
#
1 if t P T 1,
0 otherwise.
For any tree T P TD,T , let us denote by AdmT 1pT q the set of admissible cuts c of T such that
the type of any edge in c belongs to T 1. Then
∆CKλpT q � T b 1� 1b T �
¸
cPAdmT 1 pT q
RcpT q b P cpT q.
Remark 5.4.
1. If T � ttu and λt � 1, we recover the usual Connes–Kreimer Hopf algebra of D-decorated
rooted trees, which we denote by HCK
D , and its duality with the Grossman–Larson Hopf
algebra [10, 15, 23].
2. If T and D are finite, for any λ P KT , both HCKλ
D,T and HGLλ
D,T are graded Hopf algebras
(by the number of vertices), and their homogeneous components are finite-dimensional.
Via the pairing x�,�y, each one is the graded dual of the other.
20 L. Foissy
5.3 Hochschild cohomology of coalgebras
For the sake of simplicity, we assume that the set of types T is finite and we put T � tt1, . . . , tNu.
Let pC,∆q be a coalgebra and let pM, δL, δRq be a C-bicomodule. We define a complex, dual
to the Hochschild complex for algebras, in the following way:
1. For any n ¥ 0, Hn � L
�
M,Cbn
�
.
2. For any L P Hn,
bnpLq � pIdb Lq � δL �
ņ
i�1
p�1qi
�
Idbpi�1q b∆b Idbpn�iq
�
� L
� p�1qn�1pLb Idq � δR.
In particular, one-cocycles are maps L : M ÝÑ C such that
∆ � L � pIdb Lq � δL � pLb Idq � δR.
We shall consider in particular the bicomodule pM, δL, δRq such that
@x P C,
#
δLpxq � 1b x,
δRpxq � ∆pxq.
If C is a bialgebra, then MbN is also a bicomodule:
@xt P C,
$'''&
'''%
δL
� â
1¤i¤N
xi
� 1b
â
1¤i¤N
xi,
δR
� â
1¤i¤N
xi
�
â
1¤i¤N
x
p1q
i b
¹
1¤i¤N
x
p2q
i .
We denote by 1 � p1qtPT P KT , and we take C � HCK1
D,T . One can identify S
�
VectpTD,T q
`T �
and CbN , xδTi being identified with 1bpi�1q b x b 1bpn�iq for any x P TD,T and 1 ¤ i ¤ N .
Then for any d, Bd : C
bN ÝÑ C is a 1-cocycle. Moreover, there is a universal property, proved
in the same way as for the Connes–Kreimer’s one [10]:
Theorem 5.5. Let B be a commutative bialgebra and, for any d P D, let Ld : C
bN ÝÑ C be
a 1-cocycle:
@d P D, @xt P B, ∆ � Ld
� â
1¤i¤N
xi
� 1b
â
1¤i¤N
xi � Ld
� â
1¤i¤N
x
p1q
i
b
¹
1¤i¤N
x
p2q
i .
There exists a unique bialgebra morphism ϕ : HCK1
D,T ÝÑ C such that for any d P D, ϕ � Ld �
Bd � ϕ
bN .
5.4 Hopf algebra morphisms
Our aim is, firstly, to construct Hopf algebras morphisms between HCKλ
D,T and HCKµ
D,T ; secondly,
to construct Hopf algebra isomorphisms between HCKλ
D,T and HCK
D1 for a well-chosen D1.
Proposition 5.6. Let M P MT ,T 1pKq, λ P KT . Then ΦM : HCK
MJλ
D,T 1 ÝÑ HCKλ
D,T is a Hopf
algebra morphism.
Algebraic Structures on Typed Decorated Rooted Trees 21
Proof. ΦM is obviously an algebra morphism. Let T P TD,T .
∆λ � ΦM pT q � ΦM pT q b 1� 1b ΦM pT q
�
¸
cPAdmpT q
¹
ePc
� ¸
tPT
mt,typepeqλt
ΦM pRcpT qq b ΦM pP cpT qq
� ΦM pT q b 1� 1b ΦM pT q
�
¸
cPAdmpT q
¹
ePc
�
MJλ
�
typepeq
ΦM pRcpT qq b ΦM pP cpT qq
� pΦM b ΦM q �∆MJapT q.
So ΦM is a coalgebra morphism from HCK
MJλ
D,T 1 to HCKλ
D,T . ■
Corollary 5.7. Let λ, µ P KT , both nonzero. Then HCKλ
D,T and HCKµ
D,T are isomorphic Hopf
algebras.
Proof. There existsM P MT pKq, invertible, such thatMJλ � µ. Then ΦM is an isomorphism
between HCKµ
D,T and HCKλ
D,T . ■
Definition 5.8. Let us fix t0 P T . For any F P FD,T , we shall say that tT1, . . . , Tku�t0 F if the
following conditions hold:
� tT1, . . . , Tku is a partition of V pF q. Consequently, for any i P rks, Ti P FD,T , by restriction.
� For any i P rks, Ti P Tpt0qD,T .
If tT1, . . . , Tku�t0F , we denote by F {tT1, . . . , Tku the forest obtained by contracting Ti to a single
vertex for any i P rks, decorating this vertex by Ti, and forgetting the type of the remaining
edges. Then F {tT1, . . . , Tku is a T pt0q
D,T -decorated forest.
Proposition 5.9. Let λ P KT , t0 P T . Let us consider the map
Ψ�
t0 :
$''&
''%
HD,T ÝÑ HTpt0qD,T
,
F P FD,T ÞÝÑ
¸
tT1,...,Tku�t0F
� ¹
ePEpF qz\EpTiq
λtypepeq
F {tT1, . . . , Tku.
Then Ψ�
t0 is a Hopf algebra morphism from HCKλ
D,T to HCK
Tpt0qD,T
. It is an isomorphism if, and only
if, λt0 � 0.
Proof. First case. We first assume that D and T are finite. In this case, HCKλ
D,T is the graded
dual of HGLλ
D,T , with the Hopf pairing x�,�y; grading HTpt0qD,T
by the number of vertices of the
decorations, HCK
Tpt0qD,T
is the graded dual of HGL
Tpt0qD,T
. Moreover, Ψ�
t0 is the transpose of Ψt0 of Propo-
sition 4.9, so is a Hopf algebra morphism. If λt0 � 0, Ψt0 is an isomorphism, so Ψ�
t0 also is.
General case. Let x, y P HD,T . There exist finite D1, T 1, such that x, y P HD1,T 1 ; we can
assume that t0 P T 1. We denote by λ1 � λ|T 1 . Then, by the preceding case, denoting by Ψ1
t0 the
restriction of Ψ�
t0 to HD1,T 1 ,
Ψ�
t0pxyq � Ψ1
t0pxyq � Ψ1
t0pxqΨ
1
t0pyq � Ψ�
t0pxqΨ
�
t0pyq,
∆CKλ �Ψ�
t0pxq � ∆CKλ1 �Ψ1
t0pxq � pΨ1
t0 bΨ1
t0q �∆
CKλ1 pxq � pΨ�
t0 b�
t0q �∆
CKλpxq,
so Ψ is a Hopf algebra morphism.
22 L. Foissy
Let us assume that λt0 � 0. If Ψ�
t0pxq � 0, then Ψ1
t0pxq � 0. As a1t0 � 0, by the first case,
x � 0, so Ψ�
t0 is injective. Moreover, there exists z P HD1,T 1 , such that Ψ1
t0pzq � y; so Ψ�
t0pzq � y,
and Ψ�
t0 is surjective.
Let us assume that λt0 � 0. Let T be a tree with two vertices, such that its unique edge is
of type t0. As T R Tpt0qD,T , Φt0pT q has a unique term, given by the partition X � ttx1u, tx2uu,
where x1 and x2 are the vertices of T . Hence,
Ψ�
t0pT q � λt0T
1 � 0,
so Ψ�
t0 is not injective. ■
Example 5.10. Here, T contains two elements, and . In order to simplify, we omit the
decorations of vertices. We put
x � , y � , z � , u � , v � .
Applying Ψ� :
Ψ�
� �
� x , Ψ�
� �
� λ2 x
xx
,
Ψ�
� �
� λ x
x
, Ψ�
� �
� λ2 x
x
x
,
Ψ�
� �
� λ x
x
� y , Ψ�
� �
� λ λ x
x
x
� λ x
y
,
Ψ�
� �
� λ λ x
xx
� λ y
x
, Ψ�
� �
� λ λ x
x
x
� λ y
x
� u ,
Ψ�
� �
� λ2 x
xx
� 2λ y
x
� z , Ψ�
� �
� λ2 x
x
x
� λ y
x
� λ x
y
� v .
Remark 5.11. Although it is not indicated, Ψt0 and Ψ�
t0 depend on λ.
5.5 Bialgebras in cointeraction
By [12], for any λ P KpT q, the operad morphism θλ : PreLie ÝÑ PT , which send
to
λ, where
PreLie is the operad of pre-Lie algebras, induces a pair of cointeracting bialgebras for any finite
set D. By construction, the first bialgebra of the pair is HCKλ
D,T . Let us describe the second one.
Definition 5.12. Let F P FT ,D. We shall say that tT1, . . . , Tku � F if
1. tT1, . . . , Tku is a partition of V pF q. Consequently, for any i P rks, Ti P FD,T , by restriction.
2. For any i P rks, Ti P TD,T .
If tT1, . . . , Tku � F and dec: rks ÝÑ D, we denote by pF {tT1, . . . , Tku, decq the forest obtained
by contracting Ti to a single vertex, and decorating this vertex by decpiq, for all i P rks. This is
an element of FD,T .
Proposition 5.13. If D is finite, H1
D,T is the free commutative algebra generated by pairs pT, dq,
where T P TT ,D and d P D. The coproduct is given, for any F P FD,T , d P D, by
δpF, dq �
¸
tT1,...,Tku�F
¸
dec: rksÝÑD
ppF {tT1, . . . , Tku, decq, dq b pT1,decp1qq � � � pTk,decpkqq.
Algebraic Structures on Typed Decorated Rooted Trees 23
Then pH1
D,T ,m, δq is a bialgebra, and HCKλ
D,T is a coalgebra in the category of H1
D,T -comodules
via the coaction given, for any T P TD,T , by
δpT q �
¸
tT1,...,Tku�T
¸
dec: rksÝÑD
ppT {tT1, . . . , Tku,decq b pT1, decp1qq � � � pTk, decpkqq.
Corollary 5.14. Let us assume that D is given a semigroup law denoted by �. If F P FT ,D,
and tT1, . . . , Tku � F , then naturally Ti P TT ,D for any i and the T -typed forest F {tT1, . . . , Tku
is given a D-decoration, decorating the vertex obtained in the contradiction of Ti by the sum
of the decorations of the vertices of Ti. Then HD,T is given a second coproduct δ such that for
any F P FD,T ,
δpF q �
¸
tT1,...,Tku�F
F {tT1, . . . , Tku b T1 � � �Tk.
Then pHD,T ,m, δq is a bialgebra and HCKλ
D,T is a coalgebra in the category of HD,T -comodules via
the coaction δ.
Proof. We denote by I the ideal of H1
D,T generated by pairs pT, dq such that T P TD,T and
d P D, with
d �
¸
vPV pT q
decpvq.
The quotient H1
D,T {I is identified with HD,T , trough the surjective algebra morphism
ϖ :
$''&
''%
H1
D,T ÝÑ HD,T ,
pF, dq P FD,T �D ÞÝÑ
#
F if d �
°
vPV pF q decpvq,
0 otherwise.
Let us prove that I is a coideal. Let T P TT ,D, d P D, tT1, . . . , Tku � F , dec : rks ÝÑ D such
that ppT {tT1, . . . , Tku, decq, dq R I and for any i, pTi,decpiqq R I. Then
@i P rks,
¸
vPV pTiq
decpvq � decpiq,
ķ
i�1
decpiq � d.
Hence,
¸
vPV pT q
decpvq �
ķ
i�1
¸
vPV pTiq
decpvq �
ķ
i�1
decpiq � d,
so pT, dq R I. Consequently, if T P I, then ppT {tT1, . . . , Tku, decq, dq P I or at least one of the
pTi,decpiqq belongs to I. Hence,
δpIq � I bH1
D,T �H1
D,T b I.
So I is a coideal. The coproduct induced on HD,T by the morphism ϖ is precisely the one given
in the setting of this corollary. ■
24 L. Foissy
In particular, if D is reduced to a single element, denoted by �, if we give it its unique
semigroup structure (� � � � �), We obtain again the result of [7].
5.6 The Bruned–Hairer–Zambotti construction
We now consider the coproducts on typed trees in [3, Theorem 2.2.16], the first one with
ApF q � ApF q and the second one with ApF q � A�pF q of [3, Definition 2.4.1]. By definition
[3, Definition 2.26] of admissible subtrees, according to the notations we choose in this paper:
� Let L be a finite set of types. The considered trees are L-typed and the leaves are L-
decorated. Considering that the internal vertices of such a tree are in fact decorated by
an element 0 R L, these trees form a subset of TL\t0u,L which we denote by T1L.
� The first coproduct ∆� is given on any tree T P T1L by
∆�pT q �
¸
cPAdm1pT q
RcpT q b P cpT q,
where Adm1pT q is the set of admissible cuts of T such that the set of leaves of RcpT q
is a subset of leaves of T (note that automatically, the leaves of P cpT q are also leaves
of T ).
� The second coproduct is given on any tree T P T1L by
∆pT q �
¸
tT1,...,Tku�1T
T {tT1, . . . , Tku b T1 � � �Tk,
where the sum runs over all tT1, . . . , Tku � T such that the leaves of T {tT1, . . . , Tku are
leaves of T .
We denote byH1
L the subalgebra ofHL\t0u,L generated by T1L. Then pH1
L,m,∆�q and pH1
L,m, δq
are bialgebras.
Let us give to L any product � making it a commutative associative semigroup. We extend
this structure to L\ t0u by
@t P L\ t0u, 0� t � t� 0 � 0.
We take λt � 1 for any t P L \ t0u, and obtain with this data two coproducts ∆ and δ
on HL\t0u,L, the first one given by admissible cuts and the second one by contractions of sub-
trees. The subalgebra H2
L of HL\t0u,L generated by trees such that any internal vertex is
decorated by 0 (note that the leaves of such a tree are decorated by L\ t0u) is a subbialgebra
for both coproducts. We denote by I the ideal of H2
L generated by trees with at least one leaf
decorated by 0. Then it is a coideal for both coproducts, so the quotient algebra H2
L{I inherits
two coproducts, still denoted by ∆ and δ. This algebra is trivially identified with the algebra
generated by T1L, that is to say with H1
L. By construction of the different coproducts, this
identification is an isomorphism from the Hopf algebra pH2
L{I,∆q to pH1
L{I,∆�q and from the
Hopf algebra pH2
L{I, δq to pH1
L{I,∆q. In other words, the Bruned–Hairer–Zambotti construc-
tion of cointeracting bialgebras on typed trees is a subquotient of the construction presented
here.
Algebraic Structures on Typed Decorated Rooted Trees 25
6 Appendix
6.1 Values of tD,T pkq
For D � 1,
T zk 1 2 3 4 5 6 7 8
1 1 1 2 4 9 20 48 115
2 1 2 7 26 107 458 2058 9498
3 1 3 15 82 495 3144 20875 142773
4 1 4 26 188 1499 12628 111064 1006840
5 1 5 40 360 3570 37476 410490 4635330
6 1 6 57 614 7284 91566 1200705 16232820
7 1 7 77 966 13342 195384 2984142 46990952
8 1 8 100 1432 22570 377320 6578116 118238600
9 1 9 126 2028 35919 674964 13225632 267188229
10 1 10 155 2770 54465 1136402 24723000 554540590
For D � 2,
T zk 1 2 3 4 5 6 7 8
1 2 4 14 52 214 916 4116 18996
2 2 8 52 376 2998 25256 222128 2013680
3 2 12 114 1228 14568 183132 2401410 32465640
4 2 16 200 2864 45140 754640 13156232 236477200
5 2 20 310 5540 108930 2272804 49446000 1109081180
6 2 24 444 9512 224154 5606520 146204792 3930863232
7 2 28 602 15036 413028 12043500 366122190 11475005616
8 2 32 784 22368 701768 23373216 811575408 29052861280
9 2 36 990 31764 1120590 41969844 1638712716 65965167108
10 2 40 1220 43480 1703710 70875208 3073688160 137426005200
For D � 3,
T zk 1 2 3 4 5 6 7 8
1 3 9 45 246 1485 9432 62625 428319
2 3 18 171 1842 21852 274698 3602115 48698460
3 3 27 378 6084 107757 2024892 39676896 801564687
4 3 36 666 14268 336231 8409780 219307188 5896294848
5 3 45 1035 27690 814680 25444584 828506340 27812997990
6 3 54 1485 47646 1680885 62954766 2458069074 98947750662
7 3 63 2016 75432 3103002 135520812 6170116638 289616448690
8 3 72 2628 112344 5279562 263423016 13701398868 734709311208
9 3 81 3321 159678 8439471 473586264 27703353159 1670715963729
10 3 90 4095 218730 12842010 800524818 52018920345 3484841027040
26 L. Foissy
For D � 4,
T zk 1 2 3 4 5 6 7 8
1 4 16 104 752 5996 50512 444256 4027360
2 4 32 400 5728 90280 1509280 26312464 472954400
3 4 48 888 19024 448308 11213040 292409584 7861726464
4 4 64 1568 44736 1403536 46746432 1623150816 58105722560
5 4 80 2440 86960 3407420 141750416 6147376320 274852010400
6 4 96 3504 149792 7039416 351230688 18268531824 979612414944
7 4 112 4760 237328 13006980 756866096 45910215120 2871018269632
8 4 128 6208 353664 22145568 1472317056 102037088448 7290356719488
9 4 144 7848 502896 35418636 2648533968 206451156768 16590568445280
10 4 160 9680 689120 53917640 4479065632 387863411920 34625886677920
we find the following sequences of the OEIS [24]:
T zD 1 2 3 4
1 A0081 A038055 A038059 A136793
2 A00151 A136794
3 A006964
4 A052763
5 A052788
6 A246235
7 A246236
8 A246237
9 A246238
10 A246239
6.2 Values of t1D,T pkq
For D � 1,
T zk 1 2 3 4 5 6 7 8
1 1 0 0 0 0 0 0 0
2 1 1 3 10 39 160 702 3177
3 1 2 9 46 268 1660 10845 73270
4 1 3 18 124 963 7968 69236 621999
5 1 4 30 260 2525 26136 283528 3178696
6 1 5 45 470 5480 68096 885805 11904160
7 1 6 63 770 10479 151956 2304974 36110880
8 1 7 84 1176 18298 303296 5255964 94051770
9 1 8 108 1704 29838 556464 10845732 218239560
10 1 9 135 2370 46125 955872 20696076 462558987
Algebraic Structures on Typed Decorated Rooted Trees 27
For D � 2,
T zk 1 2 3 4 5 6 7 8
1 2 0 0 0 0 0 0 0
2 2 4 22 144 1090 8864 76162 678532
3 2 8 68 688 7886 96896 1250780 16713504
4 2 12 138 1888 29004 476736 8213588 146342376
5 2 16 232 4000 77060 1586304 34185344 761389360
6 2 20 350 7280 168670 4171744 107932710 2884827980
7 2 24 492 11984 324450 9370368 282934428 8822987856
8 2 28 658 18368 569016 18793600 648698792 23119514576
9 2 32 848 26688 930984 34609920 1344232416 53898191520
10 2 36 1062 37200 1442970 59627808 2573660298 114661732500
For D � 3,
T zk 1 2 3 4 5 6 7 8
1 3 0 0 0 0 0 0 0
2 3 9 72 705 7947 96588 1237728 16450389
3 3 18 225 3408 58347 1072224 20685195 413084610
4 3 27 459 9405 216081 5315112 136987407 3650993163
5 3 36 774 19992 576405 17763984 572991726 19100718828
6 3 45 1170 36465 1264950 46852884 1815034140 72635168880
7 3 54 1647 60120 2437722 105455952 4768982442 222723271080
8 3 63 2205 92253 4281102 211832208 10953036318 584744300226
9 3 72 2844 134160 7011846 390570336 22727284344 1365242802048
10 3 81 3564 187137 10877085 673533468 43560017892 2907844041231
For D � 4,
T zk 1 2 3 4 5 6 7 8
1 4 0 0 0 0 0 0 0
2 4 16 168 2192 32844 531200 9051376 159962784
3 4 32 528 10656 242792 5939968 152518064 4053650976
4 4 48 1080 29488 902100 29551104 1014147872 35989518528
5 4 64 1824 62784 2411024 98976256 4252211232 188790415552
6 4 80 2760 114640 5297820 261422336 13491005840 719200139360
7 4 96 3888 189152 10218744 588999936 35487727184 2208096700896
8 4 112 5208 290416 17958052 1184031744 81574704960 5802692175744
9 4 128 6720 422528 29428000 2184360960 169377005376 13557899008896
10 4 144 8424 589584 45668844 3768659712 324805399344 28894042642464
References
[1] Bergeron F., Labelle G., Leroux P., Combinatorial species and tree-like structures, Encyclopedia of Mathe-
matics and its Applications, Vol. 67, Cambridge University Press, Cambridge, 1998.
[2] Bremner M.R., Dotsenko V., Algebraic operads. An algorithmic companion, CRC Press, Boca Raton, FL,
2016.
https://doi.org/10.1017/CBO9781107325913
28 L. Foissy
[3] Bruned Y., Singular KPZ type equations, avalaible at https://tel.archives-ouvertes.fr/tel-01306427.
[4] Bruned Y., Chandra A., Chevyrev I., Hairer M., Renormalising SPDEs in regularity structures, J. Eur.
Math. Soc. (JEMS) 23 (2021), 869–947, arXiv:1711.10239.
[5] Bruned Y., Hairer M., Zambotti L., Algebraic renormalisation of regularity structures, Invent. Math. 215
(2019), 1039–1156, arXiv:1610.08468.
[6] Bruned Y., Manchon D., Algebraic deformation for SPDEs, arXiv:2011.05907.
[7] Calaque D., Ebrahimi-Fard K., Manchon D., Two interacting Hopf algebras of trees: a Hopf-algebraic ap-
proach to composition and substitution of B-series, Adv. in Appl. Math. 47 (2011), 282–308, arXiv:0806.2238.
[8] Chapoton F., Un endofoncteur de la catégorie des opérades, in Dialgebras and Related Operads, Lecture
Notes in Math., Vol. 1763, Springer, Berlin, 2001, 105–110.
[9] Chapoton F., Livernet M., Pre-Lie algebras and the rooted trees operad, Int. Math. Res. Not. 2001 (2001),
395–408, arXiv:math.QA/0002069.
[10] Connes A., Kreimer D., Hopf algebras, renormalization and noncommutative geometry, Comm. Math. Phys.
199 (1998), 203–242, arXiv:hep-th/9808042.
[11] Dotsenko V., Griffin J., Cacti and filtered distributive laws, Algebr. Geom. Topol. 14 (2014), 3185–3225,
arXiv:1109.5345.
[12] Foissy L., Algebraic structures associated to operads, arXiv:1702.05344.
[13] Foissy L., Generalized prelie and permutative algebras, arXiv:2104.00909.
[14] Grossman R., Larson R.G., Hopf-algebraic structure of combinatorial objects and differential operators,
Israel J. Math. 72 (1990), 109–117.
[15] Hoffman M.E., Combinatorics of rooted trees and Hopf algebras, Trans. Amer. Math. Soc. 355 (2003),
3795–3811, arXiv:math.CO/0201253.
[16] Livernet M., A rigidity theorem for pre-Lie algebras, J. Pure Appl. Algebra 207 (2006), 1–18,
arXiv:math.QA/0504296.
[17] Loday J.-L., Vallette B., Algebraic operads, Grundlehren der Mathematischen Wissenschaften, Vol. 346,
Springer, Heidelberg, 2012.
[18] Manchon D., Zhang Y., Free pre-Lie family algebras, arXiv:2003.00917.
[19] Markl M., Shnider S., Stasheff J., Operads in algebra, topology and physics, Mathematical Surveys and
Monographs, Vol. 96, Amer. Math. Soc., Providence, RI, 2002.
[20] Mathar R.J., Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077.
[21] Oudom J.-M., Guin D., Sur l’algèbre enveloppante d’une algèbre pré-Lie, C. R. Math. Acad. Sci. Paris 340
(2005), 331–336.
[22] Oudom J.-M., Guin D., On the Lie enveloping algebra of a pre-Lie algebra, J. K-Theory 2 (2008), 147–167,
arXiv:math.QA/0404457.
[23] Panaite F., Relating the Connes–Kreimer and Grossman–Larson Hopf algebras built on rooted trees, Lett.
Math. Phys. 51 (2000), 211–219, arXiv:math.QA/0003074.
[24] Sloane N.J.A., The on-line encyclopedia of integer sequences, http://oeis.org/.
[25] Zhang Y., Gao X., Guo L., Matching Rota–Baxter algebras, matching dendriform algebras and matching
pre-Lie algebras, J. Algebra 552 (2020), 134–170, arXiv:1909.10577.
https://tel.archives-ouvertes.fr/tel-01306427
https://doi.org/10.4171/jems/1025
https://doi.org/10.4171/jems/1025
https://arxiv.org/abs/1711.10239
https://doi.org/10.1007/s00222-018-0841-x
https://arxiv.org/abs/1610.08468
https://arxiv.org/abs/2011.05907
https://doi.org/10.1016/j.aam.2009.08.003
https://arxiv.org/abs/0806.2238
https://doi.org/10.1007/3-540-45328-8_4
https://doi.org/10.1155/S1073792801000198
https://arxiv.org/abs/math.QA/0002069
https://doi.org/10.1007/s002200050499
https://arxiv.org/abs/hep-th/9808042
https://doi.org/10.2140/agt.2014.14.3185
https://arxiv.org/abs/1109.5345
https://arxiv.org/abs/1702.05344
https://arxiv.org/abs/2104.00909
https://doi.org/10.1007/BF02764614
https://doi.org/10.1090/S0002-9947-03-03317-8
https://arxiv.org/abs/math.CO/0201253
https://doi.org/10.1016/j.jpaa.2005.10.014
https://arxiv.org/abs/math.QA/0504296
https://doi.org/10.1007/978-3-642-30362-3
https://arxiv.org/abs/2003.00917
https://doi.org/10.1090/surv/096
https://arxiv.org/abs/1603.00077
https://doi.org/10.1016/j.crma.2005.01.010
https://doi.org/10.1017/is008001011jkt037
https://arxiv.org/abs/math.QA/0404457
https://doi.org/10.1023/A:1007600216187
https://doi.org/10.1023/A:1007600216187
https://arxiv.org/abs/math.QA/0003074
http://oeis.org/
https://doi.org/10.1016/j.jalgebra.2020.02.011
https://arxiv.org/abs/1909.10577
1 Introduction
2 Typed decorated trees
2.1 Definition
2.2 Enumeration
3 Multiple pre-Lie algebras
3.1 Definition
3.2 Guin–Oudom extension of the pre-Lie products
3.3 Operad of typed trees
3.4 Koszul dual operad
4 Structure of the pre-Lie products
4.1 A nonassociative permutative coproduct
4.2 Pre-Lie algebra morphisms
5 Hopf algebraic structures
5.1 Enveloping algebra of g D,T
5.2 Dual construction
5.3 Hochschild cohomology of coalgebras
5.4 Hopf algebra morphisms
5.5 Bialgebras in cointeraction
5.6 The Bruned–Hairer–Zambotti construction
6 Appendix
6.1 Values of t D,T(k)
6.2 Values of t' D,T(k)
References
|
| id | nasplib_isofts_kiev_ua-123456789-211441 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1815-0659 |
| language | English |
| last_indexed | 2026-03-14T02:38:13Z |
| publishDate | 2021 |
| publisher | Інститут математики НАН України |
| record_format | dspace |
| spelling | Foissy, Loïc 2026-01-02T08:34:25Z 2021 Algebraic Structures on Typed Decorated Rooted Trees. Loïc Foissy. SIGMA 17 (2021), 086, 28 pages 1815-0659 2020 Mathematics Subject Classification: 05C05; 16T30; 18D50; 17D25 arXiv:1811.07572 https://nasplib.isofts.kiev.ua/handle/123456789/211441 https://doi.org/10.3842/SIGMA.2021.086 Typically decorated trees are used by Bruned, Hairer, and Zambotti to describe a renormalisation process on stochastic PDEs. We here study the algebraic structures on these objects: multiple pre-Lie algebras and related operads (generalizing a result by Chapoton and Livernet), noncommutative and cocommutative Hopf algebras (generalizing Grossman and Larson's construction), commutative and noncocommutative Hopf algebras (generalizing Connes and Kreimer's construction), bialgebras in cointeraction (generalizing Calaque, Ebrahimi-Fard, and Manchon's result). We also define families of morphisms and, in particular, we prove that any Connes-Kreimer Hopf algebra of typed and decorated trees is isomorphic to a Connes-Kreimer Hopf algebra of non-typed and decorated trees (the set of decorations of vertices being bigger), through a contraction process, and finally obtain the Bruned-Hairer-Zambotti construction as a subquotient. en Інститут математики НАН України Symmetry, Integrability and Geometry: Methods and Applications Algebraic Structures on Typed Decorated Rooted Trees Article published earlier |
| spellingShingle | Algebraic Structures on Typed Decorated Rooted Trees Foissy, Loïc |
| title | Algebraic Structures on Typed Decorated Rooted Trees |
| title_full | Algebraic Structures on Typed Decorated Rooted Trees |
| title_fullStr | Algebraic Structures on Typed Decorated Rooted Trees |
| title_full_unstemmed | Algebraic Structures on Typed Decorated Rooted Trees |
| title_short | Algebraic Structures on Typed Decorated Rooted Trees |
| title_sort | algebraic structures on typed decorated rooted trees |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/211441 |
| work_keys_str_mv | AT foissyloic algebraicstructuresontypeddecoratedrootedtrees |