Grothendieck bialgebras, Partition lattices, and symmetric functions in noncommutative variables

Grothendieck bialgebras, Partition lattices, and symmetric functions in noncommutative variables N. Bergeron∗1, C. Hohlweg∗2,M.Rosas ∗1, and M. Zabrocki∗1. ∗1Department of Mathematics and Statistics, York University Toronto, Ontario M3J 1P3, Canada. [email protected], [email protected], [email protected] ∗2The Fields Institute 222 College Street Toronto, Ontario, M5T 3J1, Canada. [email protected] Submitted: Jul 14, 2005; Accepted: Jul 19, 2006; Published: Aug 25, 2006 Mathematics Subject Classifications: 05E05, 05E10, 16G10, 20C08. Abstract We show that the Grothendieck bialgebra of the semi-tower of partition lattice algebras is isomorphic to the graded dual of the bialgebra of symmetric functions in noncommutative variables. In particular this isomorphism singles out a canonical new basis of the symmetric functions in noncommutative variables which would be an analogue of the Schur function basis for this bialgebra. Introduction Combinatorial Hopf algebras are graded connected Hopf algebras equipped with a multiplicative linear functional ζ:H→kcalled a character (see [1]). Here we assume that k is a field of characteristic zero. There has been renewed interest in these spaces in recent papers (see for example [3, 4, 6, 11, 13] and the references therein). One particularly interesting aspect of recent work has been to realize a given combinatorial Hopf algebra as the Grothendieck Hopf algebra of a tower of algebras. The prototypical example is the Hopf algebra of symmetric functions viewed, via the Frobenius characteristic map, as the Grothendieck Hopf algebras of the modules of all ∗This work is supported in part by CRC and NSERC. It is the results of a working seminar at Fields Institute with the active participation of T. MacHenry, M. Mishna, H. Li and L. Sabourin the electronic journal of combinatorics 13 (2006), #R75 1 symmetric group algebras kSnfor n≥0. The multiplication is given via induction from kSn⊗kSmto kSn+mand the comultiplication is the sum over rof the restriction from kSnto kSr⊗kSn−r. The tensor product of modules defines a third operation on symmetric functions usually referred to as the internal multiplication or the Kronecker product [16, 22]. The Schur symmetric functions are then canonically defined as the Frobenius image of the simple modules. There are many more examples of this kind of connection (see [5, 12, 15]). Here we are interested in the bialgebra structure of the symmetric functions in noncommutative variables [7, 8, 9, 17, 21] and the goal of this paper is to realize it as the Grothendieck bialgebra of the modules of the partition lattice algebras. We denote by NCSym =Ld≥0NCSymdthe algebra of symmetric functions in noncommutative variables, the product is induced from the concatenation of words. This is a Hopf algebra equipped with an internal comultiplication. The space NCSymdis the subspace of series in the noncommutative variables x1,x 2,... with homogeneous degree dthat are invariants by any finite permutation of the variables. The algebra structure of NCSym was first introduced in [21] where it was shown to be a free noncommutative algebra. This algebra was used in [9] to study free powers of noncommutative rings. More recently, a series of new bases was given for this space, lifting some of the classical bases of (commutative) symmetric functions [17]. The Hopf algebra structure was uncovered in [2, 7, 8] along with other fundamental algebraic and geometric structures. The (external) comultiplication ∆: NCSymd→LNCSymk⊗NCSymd−kis graded and gives rise to a structure of a graded Hopf algebra on NCSym. The algebra NCSym also has an internal comultiplication ∆:NCSymd→NCSymd⊗NCSymdwhich is not graded. The algebra NCSym with the comultiplication ∆is only a bialgebra (not graded) and is different from the previous graded Hopf structure. After investigating the Hopf algebra structure of NCSym, it is natural to ask if there exists a tower of algebras {An}n≥0such that the Hopf algebra NCSym corresponds to the Grothendieck bialgebra (or Hopf) algebra of the An-modules. This was the 2004-2005 question for our algebraic combinatorics working seminar at Fields Institute where the research for this article was done. Our answer involves the partition lattice algebras (kΠn,∧)and(kΠn,∨) (as well as the Solomon-Tits algebras [10, 18, 20]). For each one, with finite modules we can define a tensor product of kΠnmodules and a restriction from kΠnmodule to kΠk⊗kΠn−k modules. This allows us to place on LnG0(kΠn), the Grothendieck ring of the kΠn, a bialgebra structure (but not a Hopf algebra structure). We then define a bialgebra isomorphism LnG0(kΠn)→NCSym∗. We call this map the Frobenius characteristic map of the partition lattice algebras. This singles out a unique canonical basis of NCSym (up to automorphism) corresponding to the simple modules of the kΠn. Our paper is divided into 4 sections as follows. In section 1 we recall the definition and structure of NCSym. We then state our first theorem claiming the existence of a basis xof NCSym defined by certain algebraic properties. The proof of it will be postponed to section 4. In section 2 we recall the definition and structure of the partition lattice algebras kΠnwith the product given by the lattice operation ∧and define their modules. the electronic journal of combinatorics 13 (2006), #R75 2 We then introduce a structure of a semi-tower of algebras (i.e. we have a non-unital embedding ρn,m :kΠn⊗kΠm→kΠn+mof algebras) on the partition lattice algebras and show that it induces a bialgebra structure on its Grothendieck ring. Our second theorem states that this Grothendieck bialgebra is dual to NCSym. The classes of simple modules correspond then to the basis x. In view of the work of Brown [10] we remark that this can also be done with the semi-tower of Solomon-Tits algebras. In section 3 we build the same construction with the lattice algebras kΠnwith the product ∨.Withthistower of algebras (i.e. ρn,m is a unital morphism of algebras) we find that the Grothendieck bialgebra is again dual to NCSym, but this time the classes of simple modules correspond to the monomial basis of NCSym. In section 4 we give the proof of our first theorem and show the basis canonically defined in section 2 corresponds to the simple modules of the kΠn. In light of the Frobenius characteristic of section 2, the basis can be interpreted as an analogue of the Schur functions for NCSym and providing an answer to an open question of [17]. 1NCSym and the basis {xA} We recall the basic definition and structure of NCSym. Most of it can be found in [7, 8]. A set partition Aof mis a set of non-empty subsets A1,A 2,...,A k⊆[m]={1,2,...,m} such that Ai∩Aj=∅for i6=jand A1∪A2∪···∪Ak=[m]. The subsets Aiare called the parts of the set partition and the number of non-empty parts the length of A, denoted by `(A). There is a natural mapping from set partitions to integer partitions given by λ(A)=(|A1|,|A2|,...,|Ak|), where the list is then sorted so that the integers are listed in weakly decreasing order to form a partition. We shall use `(λ) to refer to the length (the number of parts) of the partition and |λ| is the size of the partition (the sum of the sizes of the parts), while ni(λ)shallreferto the number of parts of the partition of size i.WedenotebyΠ mthe set of set partitions of m. The number of set partitions is given by the Bell numbers. These can be defined by the recurrence B0=1andBn=Pn−1 i=0 n−1 iBi. For a set S={s1,s 2,...,s k}of integers siand an integer nwe use the notation S+nto represent the set {s1+n, s2+n,...,s k+n}.ForA∈Πmand B∈Πrset partitions with parts Ai,1≤i≤`(A)andBi,1≤i≤`(B) respectively, we set A|B={A1,A 2,...,A `(A),B 1+m, B2+m,...,B `(B)+m}, therefore A|B∈Πm+rand this operation is noncommutative in the sense that, in general, A|B6=B|A. When writing examples of set partitions, whenever the context allows it, we will use a more compact notation. For example, {{1,3,5},{2},{4}} will be represented by {135.2.4}. Although there is no order on the parts of a set partition, we will impose an implied order such that the parts are arranged by increasing value of the smallest element in the subset. This implied order will allow us to reference the ith parts of the set partition without ambiguity. There is a natural lattice structure on the set partitions of a given n. We define for A, B ∈Πnthat A≤Bif for each Ai∈Athere is a Bj∈Bsuch that Ai⊆Bj(otherwise stated, that Ais finer than B). The set of set partitions of [n] with this order forms a the electronic journal of combinatorics 13 (2006), #R75 3 poset with rank function given by nminus the length of the set partition. This poset has a unique minimal element 0n={1.2. ... .n}and a unique maximal element 1n={12 ...n}. The largest element smaller than both Aand Bis denoted A∧B={Ai∩Bj:1≤i≤`(A),1≤j≤`(B)} while the smallest element larger than Aand Bis denoted A∨B. The lattice (Πn,∧,∨) is called the partition lattice. Example 1.1 Let A={138.24.5.67}and B={1.238.4567}.Aand Bare not comparable in the inclusion order on set partitions. We calculate that A∧B={1.2.38.4.5.67}and A∨B={12345678}. When a collection of disjoint sets of positive integers is not a set partition because the union of the parts is not [n] for some n, we may lower the values in the sets so that they keep their relative values so that the resulting collection is a set partition (of an m<n). This operation is referred to as the ‘standardization’ of a set of disjoint sets Aand the resulting set partition is denoted st(A). Now for A∈Πmand S⊆{1,2,...,`(A)}with S={s1,s 2,...,s k}, we define AS= st({As1,A s2,...,A sk}) which is a set partition of |As1|+|As2|+...+|Ask|.Byconvention A{} is the empty set partition. Example 1.2 If A={1368.2.4.579},thenA{1,4}={1246.357}. For n≥0, consider a set Xnof non-commuting variables x1,x 2,...,x nand the polynomial algebra RXn=khx1,x 2,...,x niin these non-commuting variables. There is a natural Snaction on the basis elements defined by σ(xi1xi2···xik)=xσ(i1)xσ(i2)···xσ(ik). Let xi1xi2···ximbe a monomial in the space RXn.Wesaythatthetypeofthismonomial is a set partition A∈Πmwith the property that ia=ibif and only if aand bare in the same block of the set partition. This set partition is denoted as ∇(i1,i 2,...,i m)=A. Notice that the length of ∇(i1,i 2,...,i m) is equal to the number of different values which appear in (i1,i 2,...,i m). The vector space NCSym(n)is defined as the linear span of the elements mA[Xn]= X ∇(i1,i2,...,im)=A xi1xi2···xim for A∈Πm, where the sum is over all sequences with 1 ≤ij≤n.Fortheemptyset partition, we define by convention m{}[Xn]=1.If`(A)>nwe must have that mA[Xn]= 0. Since for any permutation σ∈Sn,∇(i1,i 2,...,i m)=∇(σ(i1),σ(i2),...,σ(im)), we have that σmA[Xn]=mA[Xn]. In fact, mA[Xn] is the sum of all elements in the orbit of a monomial of type Aunder the action of Sn. Therefore NCSym(n)is the space of Sninvariants in the noncommutative polynomial algebra RXn. For instance, m{13.2}[X4]= x1x2x1+x1x3x1+x1x4x1+x2x1x2+x2x3x2+x2x4x2+x3x1x3+x3x2x3+x3x4x3+x4x1x4+ x4x2x4+x4x3x4. the electronic journal of combinatorics 13 (2006), #R75 4 As in the classical case, where the number of variables is usually irrelevant as long as it is big enough, we want to consider that we have an infinite number of non-commuting variables. Since NCSym(n)inherits from khx1,x 2,...,x nia graded algebra structure, we consider, for any m≥n, the homomorphism of graded algebras khx1,...,x mi→khx1,...,x ni that sends variables xn+1,...,x mto zero and the remaining ones to themselves. This map restricts to a surjective homomorphism ρm,n :NCSym(m)→NCSym(n), that sends mA[Xm] to mA[Xn]. The family {NCSym(n):n≥1}together with the homomorphisms ρm,n forms an inverse system in the category of graded algebras. Let NCSym be its inverse limit in this category. We call NCSym the algebra of symmetric functions in an infinite number of non-commuting variables. For each set partition Athere exits an unique element mAwhose projection to each NCSym(n)is mA[Xn]. These elements are called monomial symmetric functions in an infinite number of non-commuting variables. If we decompose NCSym as the sum of its graded pieces, NCSym =M d≥0 NCSymd, then the monomial symmetric functions mA,withA`[d], is a linear basis of NCSymd. Here we forget any reference to the variables x1,x 2,...and think of elements in NCSym as noncommutative symmetric functions. The degree of a basis element mAis given by |A|=dand the product map µ:NCSymd⊗NCSymm−→ NCSymd+mis defined on the basis elements mA⊗mBby µ(mA⊗mB):= X C∈Πd+m C∧1d|1m=A|B mC.(1) This is a lift of the multiplication in NCSym(n). The graded algebra NCSym is in fact a Hopf algebra with the following comultiplication ∆:NCSymd−→ Ld k=0 NCSymk⊗NCSymd−kwhere ∆(mA)= X S⊆[`(A)] mAS⊗mASc(2) and Sc=[`(A)] −S. The counit is given by :NCSym →Qwhere (m{})=1and (mA) = 0 for all A∈Πnfor n>0. More details on this Hopf algebra structure are found in [7, 8]. The algebra NCSym was originally considered by Wolf [21] in extending the fundamental theorem of symmetric functions to this algebra and later by Bergman and Cohn [9]. More recently Rosas and Sagan [17] considered this space to define natural bases which are analogous to bases of the (commutative) symmetric functions. More progress in understanding this space was made in [7, 8] where it was considered as a Hopf algebra. In the Hopf algebra Sym of (commutative) symmetric functions, the comultiplication corresponds to the plethysm f[X]7→ f[X+Y]. It was established in [7] that the comultiplication in NCSym corresponds to a noncommutative plethysm F[X]7→ F[X+Y], where the electronic journal of combinatorics 13 (2006), #R75 5 X+Yis the alphabet (totally ordered set of non-commuting variables) corresponding to the disjoint union of Xand Y, together with the total order obtained from Xand Y placing all Yafter all X.(Thatis,x<yfor all xin Xand all yin Y.) The Hopf algebra Sym has more structure. There is a second comultiplication corresponding to the plethysm f[X]7→ f[XY] (see [16, 22]). This second operation is often referred to as the internal comultiplication or Kronecker comultiplication. We end this section describing for NCSym the analog of this internal comultiplication. This description is also considered in [2]. For the Hopf algebra NCSym we define a second (internal) comultiplication ∆:NCSymd−→ NCSymd⊗NCSymd by ∆(mA)= X B∧C=A mB⊗mC.(3) This operation corresponds to a noncommutative plethysm F[X]7→ F[XY]. More precisely, assume that we have two countable alphabet X=x1,x 2,... and Y=y1,y 2,.... Then, XY =x1y1,x 1y2,...,x iyj,..., totally ordered using the lexicographic order. That is, xy < zw if and only if (x<z)or(x=zand y<w) for all x, z in Xand all y,w in Y. We conclude that the transformation F[X]7→ F[XY ] sends F(x1,x 2,...)to F(x1y1,x 1y2,...,x 2y1,x 2y2,...). If we let the xi’s commute with the yj’s then we have that F[XY] can be expanded in the form F[XY]=PF1,i[X]F2,i[Y]. We can then define the operation ∆(F)=XF1,i ⊗F2,i. Equation (3) gives the result of this when F=mA. Clearly this operation is a morphism for the multiplication, thus NCSym with ∆and the multiplication operation of equation (1) forms a bialgebra. But it is not a Hopf algebra as it does not have an antipode. We are now in position to state our first main theorem. Remark: In order to define the sum and product of two alphabets, X+Yand XY, on the inverse limit of khx1, ..., xni, it is necessary to introduce a total order on each of them. On the other hand, when we restrict ourselves to elements of Sym,the result is independent of the particular choice of total order we made. Theorem 1.3 There is a basis {xA:A∈Πn,n≥0}of NCSym such that (i) xAxB=xA|B. (ii) ∆(xC)= X A∨B=C xA⊗xB. The proof of this theorem is technical and we differ it to Section 4. We are convinced that the basis {xA:A∈Πn,n ≥0}is central in the study of NCSym and should have many fascinating properties. We plan to study this basis further in future work. For now, we prefer to develop the representation theory that will motivate our result. the electronic journal of combinatorics 13 (2006), #R75 6 2 Grothendieck bialgebra of the Semi-tower (Π,∧)= Ln≥0(kΠn,∧). In this section we consider the partition lattice algebras. For a fixed nconsider the vector space (kΠn,∧) formally spanned by the set partitions of n. The multiplication is given by the operation ∧on set partitions and with the unit 1n={1,2,...,n}.Weremark that for all d,wehavethatkΠdis isomorphic as a vector space to NCSymdvia the pairing A↔mA. Moreover, it is straightforward to check using equation (3) that ∆is dual to ∧as operators. It is well known that (kΠn,∧) is a commutative semisimple algebra (see [19, Theorem 3.9.2]). To see this, one considers the algebra kΠn={f:Π n→k}which is clearly commutative and semisimple. We then define the map δ≥:(kΠn,∧)→kΠn A7→ δA≥, where δA≥(B)=1ifA≥Band 0 otherwise. Next check that δA∧B≥=δA≥δB≥which shows that δ≥is an isomorphism of algebras. The primitive orthogonal idempotents of kΠnare given by the functions δA=defined by δA=(B)=1ifA=Band 0 otherwise. We have that δA≥=PB≤AδB=. This implies, using M¨obius inversion, that the primitive orthogonal idempotents of (kΠn,∧)aregiven by eA=X B≤A µ(B,A)B, (4) where µis the M¨obius function of the partially ordered set Πn.Since(kΠn,∧)iscommutative and semisimple, we have that the simple (kΠn,∧)-modules of this algebra are the one dimensional spaces VA=kΠn∧eA. Here the action is given by the left multiplication C∧eA=eAif C≥A, 0 otherwise. (5) This follows from the corresponding identity in kΠnconsidering δ≥Cδ=A. We now let G0(kΠn,∧) denote the Grothendieck group of the category of finite dimensional (kΠn,∧)-modules. This is the vector space spanned by the equivalence classes of simple (kΠn,∧)-modules under isomorphisms. We also consider K0(kΠn,∧) the Grothendieck group of the category of projective (kΠn,∧)-modules. Since (kΠn,∧) is semisimple, the space G0(kΠn,∧)andK0(kΠn,∧) are equal as vector spaces as they are both linearly spanned by the elements VAfor A∈Πn. We then set K0(Π,∧)=Ln≥0K0(kΠn,∧). Given two finite (kΠn,∧) modules Vand W, we can form the (kΠn,∧)-module V⊗W with the diagonal action (it is an action since a semigroup algebra is a bialgebra for the coproduct A→A⊗A). We denote this (kΠn,∧)-module by VW(to avoid confusion with the tensor product of a (kΠn,∧)-module and a (kΠm,∧)-module). the electronic journal of combinatorics 13 (2006), #R75 7 Lemma 2.1 Given two simple (kΠn,∧)-module VAand VB, VAVB=VA∨B.(6) proof: Let C∈Πnact on eA⊗eB. From equation (5) we get C∧(eA⊗eB)= (C∧eA)⊗(C∧eB)=eA⊗eBif and only if C≥Aand C≥B,thatisC≥A∨B.If not, we get C∧(eA⊗eB) = 0. We conclude that the map eA⊗eB7→ eA∨Bis the desired isomorphism in equation (6).  We would like to define on G0(Π,∧)=Ln≥0G0(kΠn,∧) a graded multiplication and a graded comultiplication corresponding to induction and restriction. For this we need a few more tools. Lemma 2.2 The linear map ρn,m :(kΠn,∧)⊗(kΠm,∧)→(kΠn+m,∧)defined by ρn,m(A⊗B)=A|B is injective and multiplicative. Moreover, ρk+n,m ◦(ρk,n ⊗Id)=ρk,n+m◦(Id ⊗ρn,m)for all k, n and m. proof: Let A={A1,...,A r},B={B1,...,B s}be set partitions in Πn,andC= {C1,...,C t}and D={D1,...,D u}be set partitions in Πm. We remark that for all i, j, we have Ai∩(Dj+n)=∅and (Ci+n)∩Bj=∅.Since(Ci+n)∩(Dj+n)=(Ci∩Dj)+n, we have (A|C)∧(B|D)=Ai∩Bj1≤i≤r 1≤j≤s ∪(Ci+n)∩(Dj+n)1≤i≤t 1≤j≤u =(A∧B)(C∧D), and this shows that ρn,m is multiplicative. The injectivity of this map is clear from the fact that ρn,m maps distinct basis elements into distinct basis elements. The last identity of the lemma follows from the associativity of the operation “|” We define a semi-tower (Ln≥0An,{φn,m}) to be a direct sum of algebras along with a family of injective non-unital homomorphisms of algebras φn,m :An⊗Am→An+m. A tower in the sense defined in the recent literature [5, 12, 15] is a semi-tower with the additional constraint that φn,m(1n,1m)=1n+m(i.e. that φn,m is a unital embedding of algebras). Define the pair (Π,∧)=Ln≥0(kΠn,∧),{ρn,m}which is a semi-tower of the algebras (kΠn,∧). We remark that (Π,∧) is a graded algebra with the multiplication ρn,m(A, B)=A|Bwhich is associative (but non-commutative) and has a unit given by the emptyset partition ∅∈Π0. Moreover, each of the homogeneous components (kΠn,∧) of Πare themselves algebras with the multiplication ∧, and Lemma 2.2 gives the relationship between the two operations. At this point we need to stress that ρn,m is not a unital embedding of algebras and hence (Π,∧) is not a tower of algebras. The algebra (kΠn,∧)hasaunitgivenby1n={12 ...n}, the electronic journal of combinatorics 13 (2006), #R75 8 but ρn,m(1n⊗1m)6=1n+m. The tower of algebras considered in the recent literature [5, 12, 15] all have the property that the corresponding ρn,m are (unital) embeddings of algebras. This is the reason we call our construction a semi-tower rather than a tower. The motivation for defining a tower of algebras is to allow one to induce and restrict modules of these algebras and ultimately to define on its Grothendieck ring a Hopf algebra structure. Here the fact that we have only a semi-tower causes some problems in defining restriction of modules. Yet we can still define a weaker version of restriction in our situation. Let Aand Bbe two finite dimensional algebras and let ρ:A→Bbe a multiplicative injective linear map. Given a finite B-module M, we define ResρM={m∈M:ρ(1A)m=m}⊆M. In the case where ρis an embedding of algebras this definition agrees with the traditional one. More on this general theory will be found in [14] but here we focus our attention on (Π,∧). Lemma 2.3 For k≤nand a simple (kΠn,∧)-module VA∈G0(kΠn,∧), Resρk,n−kVA=(VAif A=B|Cfor B∈Πkand C∈Πn−k 0otherwise. proof: We have that ρn,m(1k⊗1n−k)∧eA=(1k|1n−k)∧eA=eAif 1k|1n−k≥A,and0 otherwise. The condition 1k|1n−k≥Ais equivalent to A=B|Cwhere A|1,...,k =Band A|k+1,...,n+k=C. We can now define a graded comultiplication on G0(Π,∧) using our definition of restriction. For V∈G0(kΠn,∧)let ∆(V)= n X k=0 Resρk,n−kV. (7) It follows from Lemmas 2.2 that this operation is coassociative. For a simple module VA∈G0(kΠn,∧), Lemma 2.3 gives us ∆(VA)= X A=B|C VB⊗VC.(8) Now we extend to G0(Π,∧) by setting VAVB=0ifVAand VBare not of the same degree. Proposition 2.4 (G0(Π,∧),,∆) is a bialgebra. proof: Let A, B ∈Πn. By equation (6), it is sufficient to prove that ∆(VA∨B)= ∆(VA)∆(VB). Using equation (2.3) we can easily reduce the problem to the following assertion: there are C∈Πk,D∈Πn−ksuch that A∨B=C|Dif and only if there are the electronic journal of combinatorics 13 (2006), #R75 9 Lemma 4.2 (i) xAxB=xA|B (ii) ∆(xC)= X A∨B=C xA⊗xB. proof: Using the same argument as in Lemma 2.5 we have xAxB=X C≤AX D≤B µ(C, A)µ(D, B)pCpD =X C≤AX D≤B µ(C, A)µ(D, B)pC|D=X E≤A|B µ(E,A|B)pE=xA|B. This shows the first identity. For the second, the left hand side of (ii) is ∆(xC)=X E≤C µ(E,C)∆(pE)=X E≤C µ(E,C)pE⊗pE,(19) and the right hand side is X A∨B=C xA⊗xB=X A∨B=CX E≤A F≤B µ(E,A)µ(F, B)pE⊗pF. Let us isolate the coefficient of pE⊗pFinthesumaboveweget TC E,F =X E≤A≤C F≤B≤CX A∨B=C µ(E,A)µ(F, B) (20) =X F≤B≤C X E≤A≤C A∨B=C µ(E,A) µ(F, B). By symmetry (interchanging the role of Eand Fif needed), we may assume that F6<E. In [19], Corollary 3.9.3 is dual to the following statement X A≤1n A∨B=1n µ(0n,A)=µ(0n,1n)ifB=0n, 0 otherwise. where, as usual, 0n={1.2. ... .n}. This implies that the sum of in bracket in equation (20) is equal to X E≤A≤C A∨B=C µ(E,A)=µ(E,C)ifB=E, 0 otherwise. (21) the electronic journal of combinatorics 13 (2006), #R75 16 This follows from the fact that µis multiplicative and in general the interval [E,C]⊆Πnis isomorphic to a cartesian product of (smaller) partition lattices (see Example 3.9.4 in [19]). If we substitute this back in equation (20) we have two cases to consider. When F6=E,our assumption that F6<Eprohibits the possibility that F≤B=E.Thuswemustalways have B6=Eand in this case TC E,F = 0. When F=E, the only value of Bwhere equation (21) does not vanish is when B=E=Fand we get TC E,E =µ(E,C)µ(E,E)=µ(E,C). If we compare this to equation (19) we conclude our proof of (ii).  Notice that the character of the module (the trace of the matrix representing the action of kΠn)VBfrom formula (5) is given by the formula χVB(A)=δB≤(A)whenA∈kΠn acts on VB. We observe that equation (18) for xAyields pA=X B≤A xB=X B χVB(A)xB. This means that the characters for the simple modules for (Π,∧) are encoded in the change of basis coefficients between the pand xbasis. Similarly, the character of the module WBwhen acted on by the element A∈kΠn are given by the formula χWB(A)=δB≥(A) from equation (11). Of course the defining relation of the pbasis from equation (17) shows that pA=X B χWB(A)mB. We observe in this formula that the characters of the simple modules of (Π,∨) are encoded in the change of basis coefficients between the pand mbasis. Both these formulas are in fairly close analogy with the formula for the expansion for the power basis in the Schur basis in the algebra of the symmetric functions. There the change of basis coefficients are the characters of the simple modules of the symmetric group. This shows that the p-basis which was defined by Rosas and Sagan [17] does represent the analogue of the power basis in the algebra of the symmetric functions and the xand the mbases encode in their coefficients the characters of the modules that they represent. Remark 4.3 One could also define a third algebra (kΠn,@) where A@B=δA=BAand construct the simple modules as we have done here for (kΠn,∧)and(kΠn,∨). This same construction shows that the simple modules of this algebra satisfy a tensor product, induction and restriction operations which make the Grothendieck ring (of the category of the finite dimensional projective modules) for this algebra isomorphic again to NCSym as a bialgebra where the simple modules behave as the elements pA∈NCSym and pAis defined in (17). the electronic journal of combinatorics 13 (2006), #R75 17 Remark 4.4 Summary of bases in NCSym. The mbasis: mAmB=X C∧(1n|1k)=A|B mC ∆(mA)= X S⊆[`(A)] mAS⊗mASc ∆(mA)= X B∧C=A mB⊗mC The pbasis: pApB=pA|B ∆(pA)= X S⊆[`(A)] pAS⊗pASc ∆(pA)=pA⊗pA The xbasis: xAxB=xA|B ∆(xA)= X B∨C=A xB⊗xC It would be interesting to find a formula for ∆(xA). References [1] M. Aguiar, N. Bergeron and F. Sottile,Combinatorial Hopf Algebras and Generalized Dehn-Sommerville Relations, Compositio Mathematica 142 (2006) 1-30. [2] M. Aguiar and S. Mahajan,Coxeter groups and Hopf algebras, Fields Institute Monographs, Volume 23 (2006), AMS, Providence, RI. [3] M. Aguiar and F. Sottile,Structure of the Malvenuto-Reutenauer Hopf algebra of permutations, Advances in Mathematics, 191 n2 (2005) 225-275. [4] P. Baumann and C. Hohlweg,A Solomon’s theory for the wreath products Go Sn, To appear at Transaction of the American Mathematical Society, 64p. ArXiv math.CO/0503011. [5] N. Bergeron, F. Hivert and J.-Y. Thibon,The peak algebra and the Hecke- Clifford algebras at q= 0, Journal of Combinatorial Theory, Series A, 107, 1, (2004), 1–19. [6] N. Bergeron, S. Mykytiuk, F. Sottile, and S. van Willigenburg,Pieri Operations on Posets, Journal of Combinatorial Theory, Series A, 91 (2000), 84–110. the electronic journal of combinatorics 13 (2006), #R75 18 [7] N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki,Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables,toappearatthe Canadian Journal of Mathematics, ArXiv math.CO/0502082. [8] N. Bergeron and M. Zabrocki,The Hopf Algebra of symmetric functions in non-commuting variables is free and cofree, submitted. ArXiv math.CO/0509265. [9] G. Bergman and P. Cohn,Symmetric elements in free powers of rings, Journal of the London Mathematical Society, 21 1969 525–534. [10] K. S. Brown,Semigroups, rings, and Markov chains, Journal of Theoretical Probabability, 13 (2000), no. 3, 871–938. [11] G. Duchamp, F. Hivert and J. Y. Thibon,Noncommutative symmetric functions. VI. Free quasi-symmetric functions and related algebras, International Journal of Algebra and Computation 12 (2002), no. 5, 671–717. [12] F. Hivert, J.-C. Novelli and J.-Y. Thibon,Representation theory of the 0- Ariki-Koike-Shoji algebras. To appear (2005). ArXiv math.CO/0407218. [13] M. E. Hoffman,Quasi-shuffle products, Journal of Algebraic Combinatorics, 11 (2000), no. 1, 49–68. [14] L. Huilan,Thesis, York University, in preparation. [15] D. Krob and J.-Y. Thibon,Noncommutative symmetric functions IV: Quantum linear groups and Hecke algebras at q= 0, Journal of Algebraic Combinatorics 6 (1997), 339–376. [16] I. Macdonald,Symmetric Functions and Hall Polynomials, Oxford Univ. Press, 1995, second edition. [17] M. Rosas and B. Sagan,Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), 215-232. [18] M. Schocker,The module structure of the Solomon-Tits algebra of the symmetric group, Journal of Algebra 301 (2006), No. 2, 554–586. [19] R. Stanley,Enumerative Combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, 49. Cambridge University Press, Cambridge, 1997. [20] J. Tits,Two properties of Coxeter complexes. Appendix to “A Mackey formula in the group ring of a Coxeter group” (Journal of Algebra 41 (1976), no. 2, 255–264) by Louis Solomon, Journal of Algebra 41 (1976), no. 2, 265–268. [21] M. C. Wolf,Symmetric functions of non-commutative elements, Duke Mathematical Journal 2(1936), 626–637. [22] A. V. Zelevinsky,Representations of finite classical groups: a Hopf algebra approach, Springer Lecture Notes 869, Springer-Verlag, Berlin-New York (1981). the electronic journal of combinatorics 13 (2006), #R75 19