A noncommutative symmetric system over the Grossman-Larson Hopf algebra of labeled rooted trees

(1)

DOI 10.1007/s10801-007-0100-5

A noncommutative symmetric system over the Grossman-Larson Hopf algebra of labeled rooted trees

Wenhua Zhao

Received: 23 April 2007 / Accepted: 30 August 2007 / Published online: 25 September 2007

Abstract In this paper, we construct explicitly a noncommutative symmetric (NCS) system over the Grossman-Larson Hopf algebra of labeled rooted trees. By the universal property of theNCS system formed by the generating functions of certain noncommutative symmetric functions, we obtain a specialization of noncommutative symmetric functions by labeled rooted trees. Taking the graded duals, we also get a graded Hopf algebra homomorphism from the Connes-Kreimer Hopf algebra of labeled rooted forests to the Hopf algebra of quasi-symmetric functions. A connection of the coefficients of the third generating function of the constructed NCS system with the order polynomials of rooted trees is also given and proved.

Keywords Noncommutative symmetric functions·Grossman-Larson Hopf algebra·Connes-Kreimer Hopf algebras·Labeled rooted trees

1 Introduction

LetKbe any unital commutativeQ-algebra andAa unital associative but not necessarily commutativeK-algebra. Lett be a formal central parameter, i.e. it commutes with all elements of A, and A[[t]]the K-algebra of formal power series int with coefficients inA. ANCS(noncommutative symmetric)system overA(see Defini- tion2.1) by definition is a 5-tuple∈A[[t]]^×⁵which satisfies the defining equations (see Eqs.(2.1)–(2.5)) of the NCSFs (noncommutative symmetric functions) first introduced and studied in the seminal paper [10]. When the base algebra K is clear in the context, the ordered pair(A, )is also called aNCS system. In some sense,

W. Zhao (

⁾

Department of Mathematics, Illinois State University, Normal, IL 61790-4520, USA e-mail:wzhao@ilstu.edu

(2)

aNCS system over an associativeK-algebra can be viewed as a system of analogs inAof the NCSFs defined by Eqs.(2.1)–(2.5). For some general discussions on the NCS systems, see [28]. For a family ofNCS systems over differential operator algebras and their applications to the inversion problem, see [29] and [30]. For more studies on NCSFs, see [6,16–18,25] and [5].

One immediate but probably the most important example of the NCS systems is(NSym, )formed by the generating functions of the NCSFs defined in [10] by Eqs.(2.1)–(2.5)over the freeK-algebraNSymof NCSFs (see Sect.2). It serves as the universalNCS system over all associativeK-algebra (see Theorem2.6). More precisely, for any NCS system(A, ), there exists a unique K-algebra homomor- phismS:NSym→Asuch thatS^×⁵()=(here we have extended the homo- morphismStoS:NSym[[t]] →A[[t]]by the base extension).

The universal property of theNCS system(NSym, )can be applied as follows when aNCS system(A, )is given. Note that, as an important topic in the symmetric function theory, the relations or polynomial identities among various NCSFs have been worked out explicitly (see [10]). When we apply theK-algebra homomorphism S:NSym→Aguaranteed by the universal property of the system (NSym, )to these identities, they are transformed into identities among the corresponding elements of Ain the system. This will be a very effective way to obtain identities for certain elements of Aif we can show they are involved in aNCS system over A. On the other hand, if aNCS system(A, )has already been well-understood, the K-algebra homomorphismS:NSym→Ain return provides a specialization or realization [10,24] of NCSFs, which may provide some new understandings on NCSFs. For more studies on the specializations of NCSFs, see the references quoted above for NCSFs.

In this paper, we apply the gadget above to the Grossman-Larson Hopf algebra of labeled rooted trees. To be more precise, for any non-emptyW ⊆N⁺,¹letH^W_GL be the Grossman-Larson Hopf algebraH^W_GL [4,8,9,12] of rooted trees labeled by positive integers ofW. We first introduce five generating functions (see Eqs. (4.1)–

(4.4) and Eq. (4.15)) of certain elements ofH^W_GL and show that they form aNCS system^W_T overH^W_GL(see Theorem4.5). Then, by the universal property of theNCS system(NSym, )from NCSFs, we obtain a graded Hopf algebra homomorphism TW :NSym→H^W_GL, which gives a specialization of NCSFs byW-labeled rooted trees (see Theorem4.6). By taking the graded duals, we get a graded Hopf algebra homomorphismT_W^∗ :H^W_CK →QSymfrom the Connes-Kreimer Hopf algebraH^W_CK [4,8,9,15] to the Hopf algebraQSym of quasi-symmetric functions [11,20,24].

Later in [31], it will be shown that, when W =N⁺, the specialization TW above is actually an embedding and hence the Hopf algebra homomorphismT_W^∗ is onto.

Finally, we give a combinatorial interpretation of the constants θ_T (see Definition 4.2) of rooted treesT that appeared in the third componentd(t )˜ (see Eq.(4.15)) of theNCS system^W_T above. We show that, for each rooted treeT, the constantθ_T

1All constructions and results of this paper work equally well for any non-empty weighted setW, i.e. any non-empty setW with a fixed weight functionwt:W→N⁺such that, for anyk∈N⁺,wt⁻¹(k)is a finite subset ofW. But, for simplicity and convenience, we will always assume thatW is a non-empty subset ofN⁺.

(3)

coincides with the coefficient ofsin the order polynomial(B₋(T ), s)(see [24]), whereB₋(T )is the rooted forest obtained by cutting off the root ofT.

The arrangement of the paper is as follows. In Sect.2, we first recall the definition of theNCS systems [28]over theK-algebrasAand a result (see Proposition2.2) on theNCS systems whenAis further a bialgebra or Hopf algebra. We then recall the universal NCS system (NSym, ) formed by generating functions of certain NCSFs in [10]. The Hopf algebra structure ofNSymand the universal property of theNCS system(NSym, )(see Theorem2.6) will also be reviewed.

In Sect. 3, we first fix certain notation on rooted trees and recall the Connes- Kreimer Hopf algebra H^W_CK and the Grossman-Larson Hopf algebra H^W_GL of W- labeled rooted forests and rooted trees, respectively. Then, by using the duality between the Grossman-Larson Hopf algebra and the Connes-Kreimer Hopf algebra (see Theorem3.2), we prove a technic lemma, Lemma3.4, that will be crucial for our later arguments.

In Sect.4, we introduce five generating functions ofW-labeled rooted trees and show in Theorem4.5that they form aNCS system^W_T over the Grossman-Larson Hopf algebraH_GL^W . By the universal property of the system(NSym, ), we get a gradedK-Hopf algebra homomorphismTW :NSym→H^W_GL(see Theorem4.6). By taking the graded duals, we get a graded Hopf algebra homomorphismT_W^∗:H^W_CK→ QSymfrom the Connes-Kreimer Hopf algebraH^W_CK to the Hopf algebraQSymof quasi-symmetric functions (see Corollary4.7).

In Sect.5, we first recall the strict order polynomials and the order polynomials of finite posets (partially ordered sets). Then, by applying some of results proved in [26]

for the strict order polynomials of rooted forests and the well-known Reciprocity Relation (see Proposition 5.1) between the strict order polynomials and the order polynomials of finite posets, we show in Proposition 5.8that, for any T ∈ ¯T, the constantθ_T involved in the third component of theNCS system^W_T is same as the coefficient ofsof the order polynomial(B₋(T ), s)of the rooted forestB₋(T ).

Finally, two remarks are as follows. First, as we pointed out early, by applying the specializationTW:NSym→H_GL^W , we will get a host of identities for the rooted trees involved in theNCS system^W_T from the identities of the NCSFs in . We believe some of these identities are interesting, at least from a combinatorial point view. But, to keep this paper in a certain size, we have to ask the reader who is interested to do the translations via the Hopf algebra homomorphismTW:NSym→ H^W_GL. Secondly, some relations between theNCS system(H^W_GL, ^W_T)constructed in this paper and the NCS systems constructed in [29] over differential operator algebras will be further studied in the followed paper [31]. Some consequences of those relations to the inversion problem ([3] and [7]) and specializations of NCSFs will also be derived there. In particular, it will be shown that, with the label setW= N⁺, theK-Hopf algebra homomorphismTW :NSym→H^W_GL in Theorem 4.6is actually an embedding.

2 The universalNCS system from noncommutative symmetric functions In this section, we first recall the definition of theNCS systems [28] over associative algebras and some of the NCSFs (noncommutative symmetric functions) first intro-

(4)

duced and studied in the seminal paper [10]. We then discuss the universal property of the NCS system formed by the generating functions of these NCSFs. The main result that we will need later is Theorem2.6which was proved in [28]. For some general discussions on theNCS systems, see [28]. For more studies on NCSFs, see [6,16–18,25] and [5].

Let K be any unital commutativeQ-algebra² andA any unital associative but not necessarily commutativeK-algebra. Lett be a formal central parameter, i.e. it commutes with all elements ofA, andA[[t]]theK-algebra of formal power series in t with coefficients inA. First let us recall the following main notion of this paper.

Definition 2.1 ([28])For any unital associativeK-algebraA, a 5-tuple=(f (t ), g(t ),d(t ),h(t ),m(t ))∈A[[t]]^×⁵is said to be aNCS(noncommutative symmetric) system overAif the following equations are satisfied.

f (0)=1, (2.1)

f (−t )g(t )=g(t )f (−t )=1, (2.2)

e^{d(t )}=g(t ), (2.3)

dg(t )

dt =g(t )h(t ), (2.4)

dg(t )

dt =m(t )g(t ). (2.5)

When the base algebra K is clear in the context, we also call the ordered pair (A, )aNCS system. SinceNCS systems often come from generating functions of certain elements ofAthat are under the consideration, the components ofwill also be refereed as the generating functions of their coefficients.

AllK-algebrasAthat we are going to work on in this paper areK-Hopf algebras.

We will freely use some standard notions and results from the theory of bialgebras and Hopf algebras, which can be found in the standard text books [1,14] and [21].

For example, by a sequence of divided powers of a bialgebra or Hopf algebraAwe mean a sequence{cn|n≥0}of elements ofAsuch that, for anyn≥0, we have

c_n=

k≥0

c_k⊗c_n₋_k.

The following result proved in [28] later will be useful to us.

Proposition 2.2 Let (A, ) be a NCS system as above. Suppose A is further a K-bialgebra. Then the following statements are equivalent.

(a) The coefficients off (t )form a sequence of divided powers ofA.

(b) The coefficients ofg(t )form a sequence of divided powers ofA.

2For the reader who is mainly interested in the combinatorial aspects of the main results of this paper, the base fieldKthroughout this paper can be safely chosen to be the fieldQof rational numbers.

(5)

(c) One(hence also all)ofd(t ),h(t )andm(t )has all its coefficients primitive inA.

In the following remark, we would like to point out a connection of the notion of NCS systems with the notion of combinatorial Hopf algebras, which was first introduced by M. Aguiar, N. Bergeron and F. Sottile in [2].

Remark 2.3 First, as pointed out in Remark 2.17 in [28], whenAis a graded and connected Hopf algebra, and one of the statements of Proposition2.2holds, say statement (b). Furthermore assume in this case that the coefficients oft^m(m≥0)ofg(t )are homogeneous with gradingm. Then the data(A, g(t ))is equivalent to a combinatorial Hopf algebra structure on the graded dual Hopf algebraA^∗ofA. For more details of the equivalence above, see Remark 2.17 in [28].

Since all other components of are completely determined by g(t ) (see Lemma 2.5 of [28] or Theorem2.6below), the notion ofNCS systems under the conditions above is also equivalent to the notion of combinatorial Hopf algebras.

Therefore, from this point of view, the notion ofNCS systems generalizes the notion of combinatorial Hopf algebras to associative K-algebras A, since, forNCS systems overA,Adoes not have to be a bialgebra nor Hopf algebra and the equivalent conditions in Proposition2.2do not have to hold either.

On the other hand, we would also like to point out that the notion ofNCS emphasizes the whole package of five generating functions of elements ofAinstead of just one. In other words, it emphasizes solutions of the system of equations Eq. (2.1)–

(2.5). Even though, once one of the components of, sayg(t )again, is fixed, the other four will be given by the corresponding universal polynomials of NCSFs in coefficients ofg(t ) (see Theorem2.6below), it is very often not trivial at all what values of these universal polynomials are, or in other words, it is still far away from clear how to write down directly and explicitly the other four components of.

The main aim of this paper is to construct explicitly aNCS system^W_T over the Grossman-Larson Hopf algebraH^W_GLofW-labeled trees without using any universal polynomials of NCSFs. Once we get theNCS system^W_T explicitly, then, by The- orem2.6, these universal polynomials of NCSFs will be transformed into identities of coefficients of the corresponding components of^W_T (see Remark4.8). Another immediate consequence is that we also get a very “visualizable representation”, or more formally, a specialization of NCSFs byW-labeled rooted trees, which in return could be useful for studying and understanding certain properties of NCSFs.

Next, let us recall some of the NCSFs first introduced and studied in [10].

Let = {_m|m≥1} be a sequence of noncommutative free variables and NSym or K the free associative algebra generated by over K. For conve- nience, we also set₀=1. We denote byλ(t )the generating function of_m(m≥0), i.e. we set

λ(t ):=

m≥0

t^m_m=1+

k≥1

t^m_m. (2.6)

In the theory of NCSFs [10],_m (m≥0)is the noncommutative analog of the m^{t h} classical (commutative) elementary symmetric function and is called them^{t h} (noncommutative)elementary symmetric function.

(6)

To define some other NCSFs, we consider Eqs.(2.2)–(2.5)over the freeK-algebra NSymwithf (t )=λ(t ). The solutions forg(t ),d(t ),h(t ),m(t )exist and are unique, whose coefficients will be the NCSFs that we are going to define. Following the notation in [10] and [28], we denote the resulted 5-tuple by

:=(λ(t ), σ (t ), (t ), ψ (t ), ξ(t )) (2.7) and write the last four generating functions ofexplicitly as follows.

σ (t )=

m≥0

t^mS_m, (2.8)

(t )=

m≥1

t^m ^m

m , (2.9)

ψ (t )=

m≥1

t^m−¹_m, (2.10)

ξ(t )=

m≥1

t^m⁻¹_m. (2.11)

Now, for any m≥1, we define Sm to be them^{t h} (noncommutative)complete homogeneous symmetric function and m(resp._m) them^{t h}power sum symmetric function of the second (resp. first)kind. Note that, _m (m≥1) were denoted by _m^∗ in [10]. Due to Proposition2.5below, the NCSFs_m (m≥1)do not play an important role in the NCSF theory (see the comments in page 234 in [10]). But, in the context of some other problems, relations ofm’s with other NCSFs, especially, withm’s, are also important (see [30], for example). So here, following [28], we call_m∈NSym (m≥1)them^{t h}(noncommutative)power sum symmetric function of the third kind.

The following two propositions proved in [10] and [16] will be very useful for our later arguments.

Proposition 2.4 For any unital commutativeQ-algebraK, the free algebraNSym is freely generated by any one of the families of the NCSFs defined above.

Proposition 2.5 Letω be the anti-involution ofNSym which fixesm (m≥1).

Then, for anym≥1, we have

ω(S_m)=S_m, (2.12)

ω( _m)= m, (2.13)

ω(_m)=_m. (2.14)

Next, let us recall the following gradedK-Hopf algebra structure ofNSym. It has been shown in [10] thatNSymis the universal enveloping algebra of the free Lie algebra generated by_m (m≥1). Hence, it has aK-Hopf algebra structure as all

(7)

other universal enveloping algebras of Lie algebras do. Its co-unit:NSym→K, co-productand antipodeSare uniquely determined by

(_m)=0, (2.15)

(_m)=1⊗_m+_m⊗1, (2.16)

S(_m)= −_m, (2.17)

for anym≥1.

Next, we introduce the weight of NCSFs by setting the weight of any monomial ⁱm¹₁ⁱm²₂· · ·ⁱm^k_kto be_k

j=1ijmj. For anym≥0, we denote byNSym_[m]the vector subspace ofNSymspanned by the monomials ofof weightm. Then it is easy to see that

NSym=

m≥0

NSym_[_m_], (2.18)

which provides a grading forNSym.

Note that, it has been shown in [10], for anym≥1, the NCSFs S_m, _m, _m∈ NSym_[_m_]. By Proposition 2.5, this is also true for the NCSFs _m’s. By the facts above and Eqs. (2.15)–(2.17), it is also easy to check that, with the grading given in Eq. (2.18),NSym forms a gradedK-Hopf algebra. Its graded dual is given by the spaceQSymof quasi-symmetric functions, which were first introduced by I. Gessel [11] (see [20] and [24] for more discussions).

Now we come back to our discussions on theNCS systems. From the definitions of the NCSFs above, we see that(NSym, )obviously forms aNCS system. More importantly, as shown in Theorem 2.1 in [28], we have the following important theorem on theNCS system(NSym, ).

Theorem 2.6 LetAbe aK-algebra andaNCS system overA. Then,

(a) There exists a unique K-algebra homomorphism S :NSym→A such that S^×⁵()=.

(b) IfAis further aK-bialgebra(resp.K-Hopf algebra)and one of the equivalent statements in Proposition2.2holds for theNCS system, thenS:NSym→A is also a homomorphism ofK-bialgebras(resp.K-Hopf algebras).

Remark 2.7 By applying the similar arguments as in the proof of Theorem2.6, or simply taking the quotient over the two-sided ideal generated by the commutators of _m’s, it is easy to see that, over the category of commutative K-algebras, the universal NCS system is given by the generating functions of the corresponding classical(commutative)symmetric functions([19]).

3 The Grossman-Larson Hopf algebra and the Connes-Kreimer Hopf algebra LetK be any unital commutativeQ-algebra andW a non-empty subset of positive integers. In this section, we first fix some notations for unlabeled rooted trees and

(8)

W-labeled rooted trees that will be used throughout this paper. We then recall the Connes-Kreimer Hopf algebra and the Grossman-Larson Hopf algebra ofW-labeled forests andW-labeled rooted trees, respectively. Finally, by using the duality between the Grossman-Larson Hopf algebra and the Connes-Kreimer Hopf algebra (see The- orem3.2), we prove a technic lemma, Lemma3.4, that will play an important role in our later arguments.

First, let us fix the following notation which will be used throughout the rest of this paper.

Notation By a rooted tree we mean a finite 1-connected graph with one vertex des- ignated as its root. For convenience, we also view the empty set∅as a rooted tree and call it the emptyset rooted tree. The rooted tree with a single vertex is called the singleton and denoted by◦. There are natural ancestral relations between vertices.

We say a vertexwis a child of vertexvif the two are connected by an edge andw lies further from the root thanv. In the same situation, we sayvis the parent ofw.

A vertex is called a leaf if it has no children.

LetW⊆N⁺ be any non-empty subset of positive integers. AW-labeled rooted tree is a rooted tree with each vertex labeled by an element of W. If an element m∈W is assigned to a vertexv, thenmis called the weight of the vertexv. When we speak of isomorphisms between unlabeled (resp.W-labeled) rooted trees, we will always mean isomorphisms which also preserve the root (resp. the root and also the labels of vertices). We will denote byT(resp.T^W) the set of isomorphism classes of all unlabeled (resp.W-labeled) rooted trees. A disjoint union of any finitely many rooted trees (resp.W-labeled rooted trees) is called a rooted forest (resp.W-labeled rooted forest). We denote by F (resp.F^W) the set of unlabeled (resp. W-labeled) rooted forests.

With these notions in mind, we establish the following notation.

(1) For any rooted treeT ∈T^W, we set the following notation:

• rtT denotes the root vertex ofT andO(T )the set of all the children of rtT. We seto(T )= |O(T )|(the cardinal number of the setO(T )).

• E(T )denotes the set of edges ofT.

• V (T )denotes the set of vertices ofT andv(T )= |V (T )|.

• L(T )denotes the set of leaves ofT andl(T )= |L(T )|.

• For anyv∈V (T ), we define the height ofvto be the number of edges in the (unique) geodesic connectingv to rtT. The height ofT is defined to be the maximum of the heights of its vertices.

• For anyT ∈T^W andT = ∅,|T|denotes the sum of the weights of all vertices ofT. WhenT = ∅, we set|T| =0.

• For anyT ∈T^W, we denote by Aut(T ) the automorphism group ofT and α(T )the cardinal number of Aut(T ).

(2) Any subset ofE(T )is called a cut ofT. A cutC⊆E(T )is said to be admissible if no two different edges ofClie in the path connecting the root and a leaf. We denote byC(T )the set of all admissible cuts ofT. Note that, the empty subset

∅ ofE(T )andC= {e}for anye∈E(T )are always admissible cuts. We will

(9)

identify any edgee∈E(T )with the admissible cutC:= {e}and simply say the edgeeitself is an admissible cut ofT.

(3) For anyT ∈T^WwithT = ◦, letC∈C(T )be an admissible cut ofT with|C| = m≥1. Note that, after deleting the edges inCfromT, we get a disjoint union of m+1 rooted trees, sayT0,T1, . . . ,Tmwith rt(T )∈V (T0). We defineRC(T )= T₀∈T^W andP_C(T )∈F^W the rooted forest formed byT₁, . . . ,T_m.

(4) For any disjoint admissible cutsC1andC2, we say “C1lies aboveC2”, and write C1C2, ifC2⊆E(RC₁(T )). This merely says that all edges ofC2remain when we remove all edges ofC₁andP_C₁(T ). Note that this relation is not transitive.

When we writeC1 · · · C_r forC1, . . . , C_r∈C(T ), we will mean thatC_iC_j wheneveri < j.

(5) For anyT ∈T^W, we sayT is a chain if its underlying rooted tree is a rooted tree with a single leaf. We sayT is a shrub if its underlying rooted tree is a rooted tree of height 1. We sayT is primitive if its root has only one child. For anym≥1, we setHm,SmandPm to be the sets of the chains, shrubs and primitive rooted treesT of weight|T| =m, respectively.H,SandPare set to be the unions of Hm,SmandPm, respectively, for allm≥1.

For example, in the case whereW= {1}, which allows not to write the labels, we have

H=

⎧⎪

⎪⎨

⎪⎪

⎩ , ,

, ,

. . .

⎫⎪

⎪⎬

⎪⎪

⎭ ,

S= , ∨

, ∨

, ∨ . . .

,

P=

⎧⎪

⎪⎨

⎪⎪

⎩ ,

, ∨ ,

, ∨

,∨

, . . .

⎫⎪

⎪⎬

⎪⎪

⎭ .

For any non-emptyW⊆N⁺, we define the following operations forW-labeled rooted forests. For anyF ∈F^W which is disjoint union ofW-labeled rooted treesTi

(1≤i≤m), we setB₊(T₁, T₂,· · ·, T_m)the rooted tree obtained by connecting roots ofT_i (1≤i≤m)to a newly added root. We will keep the labels for the vertices of B₊(T1, T2,· · ·, Tm)fromTi’s, but for the root, we label it by 0. For convenience, we also fix the following short convention for the operationB₊. For the empty rooted tree∅, we setB₊(∅)to be the singleton labeled by 0. For anyTi∈T^W (1≤i≤m) andj_i≥1, the notationB₊(T₁^j¹, T₂^j²,· · ·, T_m^j^m)denotes the rooted tree obtained by applying the operationB₊toj1-copies ofT1;j2-copies ofT2; and so on. Later, for any unital Q-algebra K andm≥1, we will also extend the operation B₊ multi- linearly to a linear map B₊from

H^W_CK_×m

toH^W_GL, whereH^W_CK andH^W_GLat this moment are the vector spaces spanned overKby the elements ofT^W andB₊(T^W), respectively.

Now, we setT¯^W:= {B₊(F )|F ∈F^W}. Then,B₊:F^W→ ¯T^W becomes a bijec- tion. We denote byB₋: ¯T^W→F^W the inverse map ofB₊. More precisely, for any

(10)

T ∈ ¯T^W,B₋(T )is theW-labeled rooted forest obtained by cutting off the root ofT as well as all edges connecting to the root inT.

Note that, precisely speaking, elements ofT¯^Ware notW-labeled trees for 0∈W. But, if we setW¯ =W∪ {0}, then we can viewT¯^W as a subset ofW¯-labeled rooted trees T with the root rtT labeled by 0 and all other vertices labeled by non-zero elements ofW¯. We extend the definition of the weight for elements ofF^W to elements ofT¯^W by simply counting the weight of roots by zero. We setS¯^Wm :=B₊(S^Wm) (m≥ 1)andS¯^W:=B₊(S^W). We also defineH¯^W_m,P¯^W_m,H¯^W andP¯^W in the similar way.

Next we fix a unital commutativeQ-algebraKand a non-empty subset of positive integersW, and first recall the Connes-Kreimer Hopf algebras H_CK^W ofW-labeled rooted forests.

As aK-algebra, the Connes-Kreimer Hopf algebraH^W_CK is the free commutative algebra generated by formal variables {X_T |T ∈T^W}. Here, for convenience, we will still useT to denote the variable XT inH^W_CK. TheK-algebra product is given by the disjoint union. The identity element of this algebra, denoted by 1, is the free variableX_∅corresponding to the emptyset rooted tree∅. The coproduct:H^W_CK→ H^W_CK⊗H^W_CK is uniquely determined by setting

(1)=1⊗1, (3.1)

(T )=T ⊗1+

C∈C(T )

P_C(T )⊗R_C(T ). (3.2)

The co-unit:H_CK^W →K is theK-algebra homomorphism which sends 1∈H^W_CK to 1∈KandT to 0 for anyT ∈T^W withT = ∅. With the operations defined above and the grading given by the weight, the vector spaceH^W_CK forms a connected graded commutative bialgebra. Since any connected graded bialgebra is a Hopf algebra, there is a unique antipodeS:H^W_CK→H^W_CK that makesH^W_CK a connected graded commu- tativeK-Hopf algebra. For a formula for the antipode, see [8,9].

Next we recall the Grossman-Larson Hopf algebra of labeled rooted trees. As a vector space, the Grossman-Larson Hopf algebraH^W_GL is the vector space spanned by elements ofT¯^W overK. For anyT ∈ ¯T^W, we will still denote byT the vector in H^W_GLthat is corresponding toT. The algebra product is defined as follows.

For anyT , S∈ ¯T^W withT =B₊(T₁, T₂,· · ·, T_m), we setT ·S to be the sum of the rooted trees obtained by connecting the roots ofTi (1≤i≤m)to vertices ofSin all possiblem^v(S)different ways. Note that, the identity element with respect to this algebra product is given by the singleton◦ =B₊(∅). But we will denote it by 1.

To define the co-product:H^W_GL→H^W_GL⊗H^W_GL, we first set

(◦)= ◦ ⊗ ◦. (3.3)

Now letT ∈ ¯T^W withT = ◦, sayT =B₊(T1, T2,· · ·, T_m)withm≥1 andT_i ∈ T^W (1≤i≤m). For any non-empty subsetI⊆ {1,2,· · ·, m}, we denote byB₊(T_I) the rooted tree obtained by applying the B₊ operation to the rooted treesTi with i∈I. For convenience, whenI= ∅, we setB₊(T_I)=1. With this notation fixed, the

(11)

co-product forT is given by

(T )=

IJ={1,2,···,m}

B₊(T_I)⊗B₊(T_J). (3.4)

The co-unit:H^W_GL→Kis theK-algebra homomorphism which sends 1∈H^W_GL to 1∈KandT to 0 for anyT ∈ ¯T^W withT = ∅. With the operations defined above and the grading given by the weight, the vector spaceH^W_GLforms a graded commutative bialgebra. Therefore, there is a unique antipodeS:H^W_CK→H^W_CK that makes H^W_CK a gradedK-Hopf algebra. Actually, by the general recurrent formula, we can write down the antipode ofH_GL^W as follows.

Note that the singleton ◦ is a group-like element and S(◦)= ◦⁻¹= ◦. Now assume T = ◦and write T =B₊(T1, T2,· · ·, T_m) withm≥1 and T_i ∈T^W. Let I := {1,2,· · ·, m}. For 1≤r≤m, letPr be the set ofr-tuples(I₁, I₂,· · ·, I_r)of disjoint non-empty subsets ofI whose union isI. In other words,Pr is the set of all ordered partitions ofI intornon-empty subsets ofI.

Lemma 3.1 LetSdenote the antipode of the Grossman-Larson Hopf algebraH^W_GL ofW-labeled rooted trees. Then, for anyT ∈ ¯T^WwithT = ◦as above, we have

S(T )= m r=1

(−1)^r

(I1,···,Ir)∈Pr

B₊(T_I₁)B₊(T_I₂)· · ·B₊(T_I_r). (3.5)

Proof By the general recurrent formula for the antipode of connected cocommutative graded Hopf algebras, we know that the antipodeS ofH^W_GLsatisfies the following equation:

S(T )= −T −

(I,J )∈P2

S(B₊(T_I))B₊(T_J). (3.6)

Then it is easy to check directly that, for anyT ∈ ¯T^W,S(T )given by Eq. (3.5) does satisfy Eq. (3.6). Since the solution to Eq. (3.6) is unique, the antipodeSofH^W_GLis

actually given by Eq. (3.5).

Note that, from Eq. (3.4), it is easy to see that, a rooted treeT ∈ ¯T^Wis a primitive element of the Hopf algebraH^W_GL iff it is a primitive rooted tree in the sense that we defined before, namely the root ofT has one and only one child. It is noticeable that the set of primitiveW-labeled rooted trees is a basis of the space Prim(H^W_GL) of primitive elements of H^W_GL. Moreover, by the Milnor-Moore theorem, H^W_GL is isomorphic toU(Prim(H^W_GL)).

The relation between the Grossman-Larson Hopf algebraH^W_GL and the Connes- Kreimer Hopf algebraH^W_CK is given by the following important theorem, which was proved in [13] and [8,9].

(12)

Theorem 3.2 The Hopf algebrasH^W_GLandH_CK^W are graded dual to each other. The pairing is given by, for anyT ∈ ¯T^W andS∈F^W,

T , F =

0, ifT B₊(F ),

α(T ), ifT B₊(F ). (3.7) Furthermore, the following theorem on the algebra structure constants of H^W_GL was also proved in [13] and [8,9].

Theorem 3.3 For anyT, S∈ ¯T^W, We have T·S=

T∈ ¯T^W

C∈C(T ) B₊(P_C(T ))∼T,

R_C(T )∼S.

α(T)α(S)

α(T ) T . (3.8)

Note that, Eq. (3.8)suggests that it is much more convenient to work with the basis{VT :=T /α(T )|T ∈ ¯T^W}than the basis{T |T ∈ ¯T^W}. For example, in terms ofVT, Eq.(3.8)becomes

VT·VS=

T∈ ¯T^W

C∈C(T ) B₊(P_C(T ))∼T,

R_C(T )∼S.

VT. (3.9)

Finally, we extend Theorem3.3to a more general setting (see Lemma3.4below).

It can be viewed as a generalization of Lemma 2.8 in [26] which essentially is the case of Lemma3.4when only primitive rooted trees are involved. First, let us fix the following notation.

Let C =(C1, . . . , C_r)∈C(T )^×^r be a sequence of admissible cuts with C1

· · · C_r. We define a sequence of T_C,1 , . . . , T_C,r+ ₁∈ ¯T^W as follows: we first set T_C,1 =B₊(P_C₁(T ))and let S₁=R_C₁(T ). Note that C₂, . . . , C_r ∈C(S₁). We then setT_C,2 =B₊(P_C₂(S₁)) andS₂=R_C₂(S₁)and repeat this procedure until we get S_r =R_C_r(S_r₋₁)and then setT_C,r ₊₁=S_r. In the case that, eachC_i (1≤i≤r)con- sists of a single edge, sayei∈E(T ), we simply denoteT_C,i byTe_i.

Now we fix a positive integerrand lety= {y_T⁽ⁱ⁾|1≤i≤r;T ∈ ¯T^W}be a collec- tion of commutative formal variables.

Lemma 3.4 For anyr≥1, we have,

(T₁,...,T_r)∈(T¯^W)^r

y_T⁽¹⁾

1VT₁

· · · y_T^(r)

r VT_r

=

T∈ ¯T^W

C=(C₁,...,C_r₋₁)∈C(T )^r⁻¹ C₁···C_r₋₁

y_T⁽¹⁾

C,1· · ·y_T^(r)

C,r VT. (3.10)

(13)

Proof We denote the LHS of Eq. (3.10) byQand write it as

Q=

T∈ ¯T^W

y_TVT.

Then, by Eq. (3.7)y_T = Q, B₋(T ) for any T ∈ ¯T^W, whereB₋(T )is the forest obtained by deleting the root ofT. So:

y_T =

(T1,...,Tr)

y_T⁽¹⁾

1 · · ·y_T^(r)

r VT1. . .VTr, B₋(T )

=

(T1,...,Tr)

y_T⁽¹⁾

1 · · ·y_T^(r)

r VT1⊗(VT2· · ·VTr), (B₋(T ))

=

(T1,...,Tr)

y_T⁽¹⁾

1 · · ·y_T^(r)

r VT1⊗VT2⊗(VT3· · ·VTr), (I⊗)◦(B₋(T )),

whereIis the identity map ofH^W_CK. Repeating the process above:

=

(T1,...,Tr)

y_T⁽¹⁾

1 · · ·y_T^(r)

r VT1⊗ · · · ⊗VTr, (I^⊗^(r⁻²⁾⊗)◦ · · · ◦(B₋(T )). One the other hand, by definition of the coproduct ofH^W_CK and definition of, we have

(I^⊗^(r⁻²⁾⊗)◦ · · · ◦(I⊗)◦(B₋(T ))

=

C=(C₁,...,C_r₋₁)∈C(T )^r−1 C₁···C_r−1

B₋(T_C,1 )⊗. . .⊗B₋(T_C,r ).

Therefore, we get

y_T =

C=(C1,...,Cr−1)∈C(T )^r⁻¹ C1···Cr−1

y_T⁽¹⁾

C,1· · ·y_T^(r)

C,r.

4 ANCS system over the Grossman-Larson Hopf algebraH^W_GLofW-labeled rooted trees

In this section, for any non-emptyW⊆N⁺, we construct aNCS system^W_T over the Grossman-Larson Hopf algebraH^W_GL. First, let us introduce the following generating functions of certain elements of H^W_GL, which will be the components of theNCS system ^W_T corresponding to f (t ), g(t ), h(t ) andm(t ) according the notation in

(14)

Definition2.1.

f (t )˜ : =

T∈¯S^W

(−1)^{o(T )}^+|^T^|t^|^T^|VT =1+

T∈¯S^W T=◦

(−1)^{o(T )}^+|^T^|t^|^T^|VT, (4.1)

˜

g(t ): =

T∈ ¯T^W

t^|^T^|VT =1+

T∈ ¯T^W T=◦

t^|^T^|VT, (4.2)

h(t )˜ : =

T∈ ¯H^W

t^|T^|−¹β_TVT, (4.3)

m(t ): =

T∈ ¯P^W

t^|^T^|−¹γ_TVT, (4.4)

where, for anyT ∈ ¯H^W (resp.T ∈ ¯P^W),β_T (resp.γ_T) is the weight of the unique leaf (resp. the unique child of the root) ofT. Note that, for the singletonT = ◦, we have β_T =γ_T =0. Soh(0)˜ =m(0)=0.

For example, whenW= {1,2}, we have f (t )˜ =1+V¹ t+

V1∨1 −V²

t²+

V ∨11

1 −V

∨ 2 1

t³+ · · ·,

˜

g(t )=1+V¹t+

V² +V

∨ 1

1 +V

1 1

t²

+

⎛

⎝V

∨ 2

1 +V

1

2 +V

2

1 +V

∨11

1 +V

∨

1 1

1 +V ∨ ¹

1

1 +V

1 1 1

⎞

⎠t³+ · · ·,

h(t )˜ =V¹ +

V

1

1 +2V²

t+

⎛

⎝V

1 11 +2V

1

2 +V

2 1

⎞

⎠t²+ · · ·,

m(t )=V¹ +

V

1

1 +2V²

t+

⎛

⎝V

1

2 +2V

2

1 +V ∨ ¹

1

1 +V

1 1 1

⎞

⎠t²+ · · ·.

Note that, from Eq. (4.1), we have f (˜−t )=

T∈¯S^W

(−1)^{o(T )}t^|^T^|VT =1+

T∈¯S^W T=◦

(−1)^{o(T )}t^|^T^|VT. (4.5)

A different way to look at the generating functionf (˜ −t )is as follows.

For anym∈W, letκmdenote the singleton labeled bymand set κ(t ):=

m∈W

t^mκm. (4.6)

(15)

Lemma 4.1

f (˜ −t )=1+

d≥1

(−1)^d

d! B₊(κ(t )^d), (4.7) whereB₊(κ(t )^d)denotes the element obtained by applyingB₊tod-copies ofκ(t ).

Proof First, it is easy to see that, the only terms that can appear in the expansion of the RHS of Eq. (4.7) are shrubs. Secondly, from the definition of the operation B₊, we see thatB₊is symmetric and multi-linear in its components. Therefore, we can expand the termB₊(κ(t )^d)into a linear combination of rooted treesS∈ ¯T^W in a similar way as we expand the power(

m∈Wt^mu_m)^d for some free commutative variablesu_m(m∈W ).

Now, for any shrubS∈ ¯S^W withS= ◦, let {m_j∈W |1≤j ≤N}be the set of all labels of the leaves ofS. Leti_j≥1(1≤j ≤N )be the number of them_j-labeled leaves ofS. Then we have

o(S)=

1≤j≤N

ij, (4.8)

|S| =

1≤j≤N

i_jm_j, (4.9)

α(S)=

1≤j≤N

(i_j)!. (4.10)

Now let us consider the coefficientcS ofSin the linear expansion of the RHS of Eq. (4.7). By the observations in the first paragraph of the proof and Eqs.(4.8)-(4.10), it is easy to see that we have

cS=(−1)^o(S)t^|^S^| o(S)!

o(S) i₁,· · ·, i_N

=(−1)^o(S) t^|^S^|

1≤j≤N(i_j)!

=(−1)^o(S) t^|^S^| α(S),

which is same as the coefficient of S in f (˜−t ) sinceVS= _α(S)¹ S. Hence we are

done.

To define the generating function d(t )˜ for the third component of the under- constructionNCS system^W_T, we first need the following definition.

Definition 4.2

(a) We define a constantθ_T ∈Qfor each unlabeled rooted treeT as follows.