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

G o hendieck bialgeb as, Pa i ion la ices, and symme ic unc ions in noncommu a i e a iables N. Be ge on∗1, C. Hohlweg∗2,M.Rosas ∗1, and M. Zab ocki∗1. ∗1Depa men o Ma hema ics and S a is ics, Yo k Uni e si y To on o, On a io M3J 1P3, Canada. be ge on@ma hs a .yo ku.ca, m [email protected], zab ocki@ma hs a .yo ku.ca ∗2The Fields Ins i u e 222 College S ee To on o, On a io, M5T 3J1, Canada. chohlweg@ ields.u o on o.ca Submi ed: Jul 14, 2005; Accep ed: Jul 19, 2006; Published: Aug 25, 2006 Ma hema ics Subjec Classi ica ions: 05E05, 05E10, 16G10, 20C08. Abs ac We show ha he G o hendieck bialgeb a o he semi- owe o pa i ion la ice algeb as is isomo phic o he g aded dual o he bialgeb a o symme ic unc ions in noncommu a i e a iables. In pa icula his isomo phism singles ou a canonical new basis o he symme ic unc ions in noncommu a i e a iables which would be an analogue o he Schu unc ion basis o his bialgeb a. In oduc ion Combina o ial Hop algeb as a e g aded connec ed Hop algeb as equipped wi h a mul i- plica i e linea unc ional ζ:H→kcalled a cha ac e (see [1]). He e we assume ha k is a ield o cha ac e is ic ze o. The e has been enewed in e es in hese spaces in ecen pape s (see o example [3, 4, 6, 11, 13] and he e e ences he ein). One pa icula ly in e es ing aspec o ecen wo k has been o ealize a gi en combina o ial Hop algeb a as he G o hendieck Hop algeb a o a owe o algeb as. The p o o ypical example is he Hop algeb a o symme ic unc ions iewed, ia he F obenius cha ac e is ic map, as he G o hendieck Hop algeb as o he modules o all ∗This wo k is suppo ed in pa by CRC and NSERC. I is he esul s o a wo king semina a Fields Ins i u e wi h he ac i e pa icipa ion o T. MacHen y, M. Mishna, H. Li and L. Sabou in he elec onic jou nal o combina o ics 13 (2006), #R75 1 symme ic g oup algeb as kSn o n≥0. The mul iplica ion is gi en ia induc ion om kSn⊗kSm o kSn+mand he comul iplica ion is he sum o e o he es ic ion om kSn o kS ⊗kSn− . The enso p oduc o modules de ines a hi d ope a ion on symme ic unc ions usually e e ed o as he in e nal mul iplica ion o he K onecke p oduc [16, 22]. The Schu symme ic unc ions a e hen canonically de ined as he F obenius image o he simple modules. The e a e many mo e examples o his kind o connec ion (see [5, 12, 15]). He e we a e in e es ed in he bialgeb a s uc u e o he symme ic unc ions in noncommu a i e a iables [7, 8, 9, 17, 21] and he goal o his pape is o ealize i as he G o hendieck bialgeb a o he modules o he pa i ion la ice algeb as. We deno e by NCSym =Ld≥0NCSymd he algeb a o symme ic unc ions in non- commu a i e a iables, he p oduc is induced om he conca ena ion o wo ds. This is a Hop algeb a equipped wi h an in e nal comul iplica ion. The space NCSymdis he subspace o se ies in he noncommu a i e a iables x1,x 2,... wi h homogeneous deg ee d ha a e in a ian s by any ini e pe mu a ion o he a iables. The algeb a s uc u e o NCSym was i s in oduced in [21] whe e i was shown o be a ee noncommu a i e algeb a. This algeb a was used in [9] o s udy ee powe s o noncommu a i e ings. Mo e ecen ly, a se ies o new bases was gi en o his space, li ing some o he classical bases o (commu a i e) symme ic unc ions [17]. The Hop algeb a s uc u e was unco e ed in [2, 7, 8] along wi h o he undamen al algeb aic and geome ic s uc u es. The (ex e nal) comul iplica ion ∆: NCSymd→LNCSymk⊗NCSymd−kis g aded and gi es ise o a s uc u e o a g aded Hop algeb a on NCSym. The algeb a NCSym also has an in e nal comul iplica ion ∆:NCSymd→NCSymd⊗NCSymdwhich is no g aded. The algeb a NCSym wi h he comul iplica ion ∆is only a bialgeb a (no g aded) and is di e en om he p e ious g aded Hop s uc u e. A e in es iga ing he Hop algeb a s uc u e o NCSym, i is na u al o ask i he e exis s a owe o algeb as {An}n≥0such ha he Hop algeb a NCSym co esponds o he G o hendieck bialgeb a (o Hop ) algeb a o he An-modules. This was he 2004-2005 ques ion o ou algeb aic combina o ics wo king semina a Fields Ins i u e whe e he esea ch o his a icle was done. Ou answe in ol es he pa i ion la ice algeb as (kΠn,∧)and(kΠn,∨) (as well as he Solomon-Ti s algeb as [10, 18, 20]). Fo each one, wi h ini e modules we can de ine a enso p oduc o kΠnmodules and a es ic ion om kΠnmodule o kΠk⊗kΠn−k modules. This allows us o place on LnG0(kΠn), he G o hendieck ing o he kΠn, a bialgeb a s uc u e (bu no a Hop algeb a s uc u e). We hen de ine a bialgeb a isomo phism LnG0(kΠn)→NCSym∗. We call his map he F obenius cha ac e is ic map o he pa i ion la ice algeb as. This singles ou a unique canonical basis o NCSym (up o au omo phism) co esponding o he simple modules o he kΠn. Ou pape is di ided in o 4 sec ions as ollows. In sec ion 1 we ecall he de ini ion and s uc u e o NCSym. We hen s a e ou i s heo em claiming he exis ence o a basis xo NCSym de ined by ce ain algeb aic p ope ies. The p oo o i will be pos poned o sec ion 4. In sec ion 2 we ecall he de ini ion and s uc u e o he pa i ion la ice algeb as kΠnwi h he p oduc gi en by he la ice ope a ion ∧and de ine hei modules. he elec onic jou nal o combina o ics 13 (2006), #R75 2 We hen in oduce a s uc u e o a semi- owe o algeb as (i.e. we ha e a non-uni al embedding ρn,m :kΠn⊗kΠm→kΠn+mo algeb as) on he pa i ion la ice algeb as and show ha i induces a bialgeb a s uc u e on i s G o hendieck ing. Ou second heo em s a es ha his G o hendieck bialgeb a is dual o NCSym. The classes o simple modules co espond hen o he basis x. In iew o he wo k o B own [10] we ema k ha his can also be done wi h he semi- owe o Solomon-Ti s algeb as. In sec ion 3 we build he same cons uc ion wi h he la ice algeb as kΠnwi h he p oduc ∨.Wi h his owe o algeb as (i.e. ρn,m is a uni al mo phism o algeb as) we ind ha he G o hendieck bialgeb a is again dual o NCSym, bu his ime he classes o simple modules co espond o he monomial basis o NCSym. In sec ion 4 we gi e he p oo o ou i s heo em and show he basis canonically de ined in sec ion 2 co esponds o he simple modules o he kΠn. In ligh o he F obe- nius cha ac e is ic o sec ion 2, he basis can be in e p e ed as an analogue o he Schu unc ions o NCSym and p o iding an answe o an open ques ion o [17]. 1NCSym and he basis {xA} We ecall he basic de ini ion and s uc u e o NCSym. Mos o i can be ound in [7, 8]. A se pa i ion Ao mis a se o non-emp y subse s A1,A 2,...,A k⊆[m]={1,2,...,m} such ha Ai∩Aj=∅ o i6=jand A1∪A2∪···∪Ak=[m]. The subse s Aia e called he pa s o he se pa i ion and he numbe o non-emp y pa s he leng h o A, deno ed by `(A). The e is a na u al mapping om se pa i ions o in ege pa i ions gi en by λ(A)=(|A1|,|A2|,...,|Ak|), whe e he lis is hen so ed so ha he in ege s a e lis ed in weakly dec easing o de o o m a pa i ion. We shall use `(λ) o e e o he leng h ( he numbe o pa s) o he pa i ion and |λ| is he size o he pa i ion ( he sum o he sizes o he pa s), while ni(λ)shall e e o he numbe o pa s o he pa i ion o size i.Wedeno ebyΠ m he se o se pa i ions o m. The numbe o se pa i ions is gi en by he Bell numbe s. These can be de ined by he ecu ence B0=1andBn=Pn−1 i=0 n−1 iBi. Fo a se S={s1,s 2,...,s k}o in ege s siand an in ege nwe use he no a ion S+n o ep esen he se {s1+n, s2+n,...,s k+n}.Fo A∈Πmand B∈Π se pa i ions wi h pa s Ai,1≤i≤`(A)andBi,1≤i≤`(B) espec i ely, we se A|B={A1,A 2,...,A `(A),B 1+m, B2+m,...,B `(B)+m}, he e o e A|B∈Πm+ and his ope a ion is noncommu a i e in he sense ha , in gene al, A|B6=B|A. When w i ing examples o se pa i ions, whene e he con ex allows i , we will use a mo e compac no a ion. Fo example, {{1,3,5},{2},{4}} will be ep esen ed by {135.2.4}. Al hough he e is no o de on he pa s o a se pa i ion, we will impose an implied o de such ha he pa s a e a anged by inc easing alue o he smalles elemen in he subse . This implied o de will allow us o e e ence he i h pa s o he se pa i ion wi hou ambigui y. The e is a na u al la ice s uc u e on he se pa i ions o a gi en n. We de ine o A, B ∈Πn ha A≤Bi o each Ai∈A he e is a Bj∈Bsuch ha Ai⊆Bj(o he wise s a ed, ha Ais ine han B). The se o se pa i ions o [n] wi h his o de o ms a he elec onic jou nal o combina o ics 13 (2006), #R75 3 pose wi h ank unc ion gi en by nminus he leng h o he se pa i ion. This pose has a unique minimal elemen 0n={1.2. ... .n}and a unique maximal elemen 1n={12 ...n}. The la ges elemen smalle han bo h Aand Bis deno ed A∧B={Ai∩Bj:1≤i≤`(A),1≤j≤`(B)} while he smalles elemen la ge han Aand Bis deno ed A∨B. The la ice (Πn,∧,∨) is called he pa i ion la ice. Example 1.1 Le A={138.24.5.67}and B={1.238.4567}.Aand Ba e no compa able in he inclusion o de on se pa i ions. We calcula e ha A∧B={1.2.38.4.5.67}and A∨B={12345678}. When a collec ion o disjoin se s o posi i e in ege s is no a se pa i ion because he union o he pa s is no [n] o some n, we may lowe he alues in he se s so ha hey keep hei ela i e alues so ha he esul ing collec ion is a se pa i ion (o an m<n). This ope a ion is e e ed o as he ‘s anda diza ion’ o a se o disjoin se s Aand he esul ing se pa i ion is deno ed s (A). Now o A∈Πmand S⊆{1,2,...,`(A)}wi h S={s1,s 2,...,s k}, we de ine AS= s ({As1,A s2,...,A sk}) which is a se pa i ion o |As1|+|As2|+...+|Ask|.Bycon en ion A{} is he emp y se pa i ion. Example 1.2 I A={1368.2.4.579}, henA{1,4}={1246.357}. Fo n≥0, conside a se Xno non-commu ing a iables x1,x 2,...,x nand he poly- nomial algeb a RXn=khx1,x 2,...,x niin hese non-commu ing a iables. The e is a na u al Snac ion on he basis elemen s de ined by σ(xi1xi2···xik)=xσ(i1)xσ(i2)···xσ(ik). Le xi1xi2···ximbe a monomial in he space RXn.Wesay ha he ypeo hismonomial is a se pa i ion A∈Πmwi h he p ope y ha ia=ibi and only i aand ba e in he same block o he se pa i ion. This se pa i ion is deno ed as ∇(i1,i 2,...,i m)=A. No ice ha he leng h o ∇(i1,i 2,...,i m) is equal o he numbe o di e en alues which appea in (i1,i 2,...,i m). The ec o space NCSym(n)is de ined as he linea span o he elemen s mA[Xn]= X ∇(i1,i2,...,im)=A xi1xi2···xim o A∈Πm, whe e he sum is o e all sequences wi h 1 ≤ij≤n.Fo heemp yse pa i ion, we de ine by con en ion m{}[Xn]=1.I `(A)>nwe mus ha e ha mA[Xn]= 0. Since o any pe mu a ion σ∈Sn,∇(i1,i 2,...,i m)=∇(σ(i1),σ(i2),...,σ(im)), we ha e ha σmA[Xn]=mA[Xn]. In ac , mA[Xn] is he sum o all elemen s in he o bi o a monomial o ype Aunde he ac ion o Sn. The e o e NCSym(n)is he space o Sn- in a ian s in he noncommu a i e polynomial algeb a RXn. Fo ins ance, m{13.2}[X4]= x1x2x1+x1x3x1+x1x4x1+x2x1x2+x2x3x2+x2x4x2+x3x1x3+x3x2x3+x3x4x3+x4x1x4+ x4x2x4+x4x3x4. he elec onic jou nal o combina o ics 13 (2006), #R75 4 As in he classical case, whe e he numbe o a iables is usually i ele an as long as i is big enough, we wan o conside ha we ha e an in ini e numbe o non-commu ing a i- ables. Since NCSym(n)inhe i s om khx1,x 2,...,x nia g aded algeb a s uc u e, we con- side , o any m≥n, he homomo phism o g aded algeb as khx1,...,x mi→khx1,...,x ni ha sends a iables xn+1,...,x m o ze o and he emaining ones o hemsel es. This map es ic s o a su jec i e homomo phism ρm,n :NCSym(m)→NCSym(n), ha sends mA[Xm] o mA[Xn]. The amily {NCSym(n):n≥1} oge he wi h he homomo phisms ρm,n o ms an in e se sys em in he ca ego y o g aded algeb as. Le NCSym be i s in e se limi in his ca ego y. We call NCSym he algeb a o symme ic unc ions in an in ini e numbe o non-commu ing a iables. Fo each se pa i ion A he e exi s an unique elemen mAwhose p ojec ion o each NCSym(n)is mA[Xn]. These elemen s a e called monomial symme ic unc ions in an in ini e numbe o non-commu ing a iables. I we decompose NCSym as he sum o i s g aded pieces, NCSym =M d≥0 NCSymd, hen he monomial symme ic unc ions mA,wi hA`[d], is a linea basis o NCSymd. He e we o ge any e e ence o he a iables x1,x 2,...and hink o elemen s in NCSym as noncommu a i e symme ic unc ions. The deg ee o a basis elemen mAis gi en by |A|=dand he p oduc map µ:NCSymd⊗NCSymm−→ NCSymd+mis de ined on he basis elemen s mA⊗mBby µ(mA⊗mB):= X C∈Πd+m C∧1d|1m=A|B mC.(1) This is a li o he mul iplica ion in NCSym(n). The g aded algeb a NCSym is in ac a Hop algeb a wi h he ollowing comul iplica ion ∆:NCSymd−→ Ld k=0 NCSymk⊗NCSymd−kwhe e ∆(mA)= X S⊆[`(A)] mAS⊗mASc(2) and Sc=[`(A)] −S. The couni is gi en by :NCSym →Qwhe e (m{})=1and (mA) = 0 o all A∈Πn o n>0. Mo e de ails on his Hop algeb a s uc u e a e ound in [7, 8]. The algeb a NCSym was o iginally conside ed by Wol [21] in ex ending he unda- men al heo em o symme ic unc ions o his algeb a and la e by Be gman and Cohn [9]. Mo e ecen ly Rosas and Sagan [17] conside ed his space o de ine na u al bases which a e analogous o bases o he (commu a i e) symme ic unc ions. Mo e p og ess in unde s anding his space was made in [7, 8] whe e i was conside ed as a Hop alge- b a. In he Hop algeb a Sym o (commu a i e) symme ic unc ions, he comul iplica ion co esponds o he ple hysm [X]7→ [X+Y]. I was es ablished in [7] ha he comul i- plica ion in NCSym co esponds o a noncommu a i e ple hysm F[X]7→ F[X+Y], whe e he elec onic jou nal o combina o ics 13 (2006), #R75 5 X+Yis he alphabe ( o ally o de ed se o non-commu ing a iables) co esponding o he disjoin union o Xand Y, oge he wi h he o al o de ob ained om Xand Y placing all Ya e all X.(Tha is,x<y o all xin Xand all yin Y.) The Hop algeb a Sym has mo e s uc u e. The e is a second comul iplica ion co e- sponding o he ple hysm [X]7→ [XY] (see [16, 22]). This second ope a ion is o en e e ed o as he in e nal comul iplica ion o K onecke comul iplica ion. We end his sec ion desc ibing o NCSym he analog o his in e nal comul iplica ion. This desc ip ion is also conside ed in [2]. Fo he Hop algeb a NCSym we de ine a second (in e nal) comul iplica ion ∆:NCSymd−→ NCSymd⊗NCSymd by ∆(mA)= X B∧C=A mB⊗mC.(3) This ope a ion co esponds o a noncommu a i e ple hysm F[X]7→ F[XY]. Mo e p e- cisely, assume ha we ha e wo coun able alphabe X=x1,x 2,... and Y=y1,y 2,.... Then, XY =x1y1,x 1y2,...,x iyj,..., o ally o de ed using he lexicog aphic o de . Tha is, xy < zw i and only i (x<z)o (x=zand y<w) o all x, z in Xand all y,w in Y. We conclude ha he ans o ma ion F[X]7→ F[XY ] sends F(x1,x 2,...) o F(x1y1,x 1y2,...,x 2y1,x 2y2,...). I we le he xi’s commu e wi h he yj’s hen we ha e ha F[XY] can be expanded in he o m F[XY]=PF1,i[X]F2,i[Y]. We can hen de ine he ope a ion ∆(F)=XF1,i ⊗F2,i. Equa ion (3) gi es he esul o his when F=mA. Clea ly his ope a ion is a mo phism o he mul iplica ion, hus NCSym wi h ∆and he mul iplica ion ope a ion o equa ion (1) o ms a bialgeb a. Bu i is no a Hop algeb a as i does no ha e an an ipode. We a e now in posi ion o s a e ou i s main heo em. Rema k: In o de o de ine he sum and p oduc o wo alphabe s, X+Yand XY, on he in e se limi o khx1, ..., xni, i is necessa y o in oduce a o al o de on each o hem. On he o he hand, when we es ic ou sel es o elemen s o Sym, he esul is independen o he pa icula choice o o al o de we made. Theo em 1.3 The e is a basis {xA:A∈Πn,n≥0}o NCSym such ha (i) xAxB=xA|B. (ii) ∆(xC)= X A∨B=C xA⊗xB. The p oo o his heo em is echnical and we di e i o Sec ion 4. We a e con inced ha he basis {xA:A∈Πn,n ≥0}is cen al in he s udy o NCSym and should ha e many ascina ing p ope ies. We plan o s udy his basis u he in u u e wo k. Fo now, we p e e o de elop he ep esen a ion heo y ha will mo i a e ou esul . he elec onic jou nal o combina o ics 13 (2006), #R75 6 2 G o hendieck bialgeb a o he Semi- owe (Π,∧)= Ln≥0(kΠn,∧). In his sec ion we conside he pa i ion la ice algeb as. Fo a ixed nconside he ec o space (kΠn,∧) o mally spanned by he se pa i ions o n. The mul iplica ion is gi en by he ope a ion ∧on se pa i ions and wi h he uni 1n={1,2,...,n}.We ema k ha o all d,weha e ha kΠdis isomo phic as a ec o space o NCSymd ia he pai ing A↔mA. Mo eo e , i is s aigh o wa d o check using equa ion (3) ha ∆is dual o ∧as ope a o s. I is well known ha (kΠn,∧) is a commu a i e semisimple algeb a (see [19, Theo em 3.9.2]). To see his, one conside s he algeb a kΠn={ :Π n→k}which is clea ly commu a i e and semisimple. We hen de ine he map δ≥:(kΠn,∧)→kΠn A7→ δA≥, whe e δA≥(B)=1i A≥Band 0 o he wise. Nex check ha δA∧B≥=δA≥δB≥which shows ha δ≥is an isomo phism o algeb as. The p imi i e o hogonal idempo en s o kΠna e gi en by he unc ions δA=de ined by δA=(B)=1i A=Band 0 o he wise. We ha e ha δA≥=PB≤AδB=. This implies, using M¨obius in e sion, ha he p imi i e o hogonal idempo en s o (kΠn,∧)a egi en by eA=X B≤A µ(B,A)B, (4) whe e µis he M¨obius unc ion o he pa ially o de ed se Πn.Since(kΠn,∧)iscommu- a i e and semisimple, we ha e ha he simple (kΠn,∧)-modules o his algeb a a e he one dimensional spaces VA=kΠn∧eA. He e he ac ion is gi en by he le mul iplica ion C∧eA=eAi C≥A, 0 o he wise. (5) This ollows om he co esponding iden i y in kΠnconside ing δ≥Cδ=A. We now le G0(kΠn,∧) deno e he G o hendieck g oup o he ca ego y o ini e di- mensional (kΠn,∧)-modules. This is he ec o space spanned by he equi alence classes o simple (kΠn,∧)-modules unde isomo phisms. We also conside K0(kΠn,∧) he G o hendieck g oup o he ca ego y o p ojec i e (kΠn,∧)-modules. Since (kΠn,∧) is semisimple, he space G0(kΠn,∧)andK0(kΠn,∧) a e equal as ec o spaces as hey a e bo h linea ly spanned by he elemen s VA o A∈Πn. We hen se K0(Π,∧)=Ln≥0K0(kΠn,∧). Gi en wo ini e (kΠn,∧) modules Vand W, we can o m he (kΠn,∧)-module V⊗W wi h he diagonal ac ion (i is an ac ion since a semig oup algeb a is a bialgeb a o he cop oduc A→A⊗A). We deno e his (kΠn,∧)-module by VW( o a oid con usion wi h he enso p oduc o a (kΠn,∧)-module and a (kΠm,∧)-module). he elec onic jou nal o combina o ics 13 (2006), #R75 7 Lemma 2.1 Gi en wo simple (kΠn,∧)-module VAand VB, VAVB=VA∨B.(6) p oo : Le C∈Πnac on eA⊗eB. F om equa ion (5) we ge C∧(eA⊗eB)= (C∧eA)⊗(C∧eB)=eA⊗eBi and only i C≥Aand C≥B, ha isC≥A∨B.I no , we ge C∧(eA⊗eB) = 0. We conclude ha he map eA⊗eB7→ eA∨Bis he desi ed isomo phism in equa ion (6).  We would like o de ine on G0(Π,∧)=Ln≥0G0(kΠn,∧) a g aded mul iplica ion and a g aded comul iplica ion co esponding o induc ion and es ic ion. Fo his we need a ew mo e ools. Lemma 2.2 The linea map ρn,m :(kΠn,∧)⊗(kΠm,∧)→(kΠn+m,∧)de ined by ρn,m(A⊗B)=A|B is injec i e and mul iplica i e. Mo eo e , ρk+n,m ◦(ρk,n ⊗Id)=ρk,n+m◦(Id ⊗ρn,m) o all k, n and m. p oo : Le A={A1,...,A },B={B1,...,B s}be se pa i ions in Πn,andC= {C1,...,C }and D={D1,...,D u}be se pa i ions in Πm. We ema k ha o all i, j, we ha e Ai∩(Dj+n)=∅and (Ci+n)∩Bj=∅.Since(Ci+n)∩(Dj+n)=(Ci∩Dj)+n, we ha e (A|C)∧(B|D)=Ai∩Bj1≤i≤ 1≤j≤s ∪(Ci+n)∩(Dj+n)1≤i≤ 1≤j≤u =(A∧B)(C∧D), and his shows ha ρn,m is mul iplica i e. The injec i i y o his map is clea om he ac ha ρn,m maps dis inc basis elemen s in o dis inc basis elemen s. The las iden i y o he lemma ollows om he associa i i y o he ope a ion “|” We de ine a semi- owe (Ln≥0An,{φn,m}) o be a di ec sum o algeb as along wi h a amily o injec i e non-uni al homomo phisms o algeb as φn,m :An⊗Am→An+m. A owe in he sense de ined in he ecen li e a u e [5, 12, 15] is a semi- owe wi h he addi ional cons ain ha φn,m(1n,1m)=1n+m(i.e. ha φn,m is a uni al embedding o algeb as). De ine he pai (Π,∧)=Ln≥0(kΠn,∧),{ρn,m}which is a semi- owe o he al- geb as (kΠn,∧). We ema k ha (Π,∧) is a g aded algeb a wi h he mul iplica ion ρn,m(A, B)=A|Bwhich is associa i e (bu non-commu a i e) and has a uni gi en by he emp yse pa i ion ∅∈Π0. Mo eo e , each o he homogeneous componen s (kΠn,∧) o Πa e hemsel es algeb as wi h he mul iplica ion ∧, and Lemma 2.2 gi es he ela- ionship be ween he wo ope a ions. A his poin we need o s ess ha ρn,m is no a uni al embedding o algeb as and hence (Π,∧) is no a owe o algeb as. The algeb a (kΠn,∧)hasauni gi enby1n={12 ...n}, he elec onic jou nal o combina o ics 13 (2006), #R75 8 bu ρn,m(1n⊗1m)6=1n+m. The owe o algeb as conside ed in he ecen li e a u e [5, 12, 15] all ha e he p ope y ha he co esponding ρn,m a e (uni al) embeddings o algeb as. This is he eason we call ou cons uc ion a semi- owe a he han a owe . The mo i a ion o de ining a owe o algeb as is o allow one o induce and es ic modules o hese algeb as and ul ima ely o de ine on i s G o hendieck ing a Hop algeb a s uc u e. He e he ac ha we ha e only a semi- owe causes some p oblems in de ining es ic ion o modules. Ye we can s ill de ine a weake e sion o es ic ion in ou si ua ion. Le Aand Bbe wo ini e dimensional algeb as and le ρ:A→Bbe a mul iplica i e injec i e linea map. Gi en a ini e B-module M, we de ine ResρM={m∈M:ρ(1A)m=m}⊆M. In he case whe e ρis an embedding o algeb as his de ini ion ag ees wi h he adi ional one. Mo e on his gene al heo y will be ound in [14] bu he e we ocus ou a en ion on (Π,∧). Lemma 2.3 Fo k≤nand a simple (kΠn,∧)-module VA∈G0(kΠn,∧), Resρk,n−kVA=(VAi A=B|C o B∈Πkand C∈Πn−k 0o he wise. p oo : We ha e ha ρn,m(1k⊗1n−k)∧eA=(1k|1n−k)∧eA=eAi 1k|1n−k≥A,and0 o he wise. The condi ion 1k|1n−k≥Ais equi alen o A=B|Cwhe e A|1,...,k =Band A|k+1,...,n+k=C. We can now de ine a g aded comul iplica ion on G0(Π,∧) using ou de ini ion o es ic ion. Fo V∈G0(kΠn,∧)le ∆(V)= n X k=0 Resρk,n−kV. (7) I ollows om Lemmas 2.2 ha his ope a ion is coassocia i e. Fo a simple module VA∈G0(kΠn,∧), Lemma 2.3 gi es us ∆(VA)= X A=B|C VB⊗VC.(8) Now we ex end  o G0(Π,∧) by se ing VAVB=0i VAand VBa e no o he same deg ee. P oposi ion 2.4 (G0(Π,∧),,∆) is a bialgeb a. p oo : Le A, B ∈Πn. By equa ion (6), i is su icien o p o e ha ∆(VA∨B)= ∆(VA)∆(VB). Using equa ion (2.3) we can easily educe he p oblem o he ollowing asse ion: he e a e C∈Πk,D∈Πn−ksuch ha A∨B=C|Di and only i he e a e he elec onic jou nal o combina o ics 13 (2006), #R75 9 Lemma 4.2 (i) xAxB=xA|B (ii) ∆(xC)= X A∨B=C xA⊗xB. p oo : Using he same a gumen as in Lemma 2.5 we ha e 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 he i s iden i y. Fo he second, he le hand side o (ii) is ∆(xC)=X E≤C µ(E,C)∆(pE)=X E≤C µ(E,C)pE⊗pE,(19) and he igh hand side is X A∨B=C xA⊗xB=X A∨B=CX E≤A F≤B µ(E,A)µ(F, B)pE⊗pF. Le us isola e he coe icien o pE⊗pFin hesumabo ewege 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 symme y (in e changing he ole o Eand Fi needed), we may assume ha F6<E. In [19], Co olla y 3.9.3 is dual o he ollowing s a emen X A≤1n A∨B=1n µ(0n,A)=µ(0n,1n)i B=0n, 0 o he wise. whe e, as usual, 0n={1.2. ... .n}. This implies ha he sum o in b acke in equa ion (20) is equal o X E≤A≤C A∨B=C µ(E,A)=µ(E,C)i B=E, 0 o he wise. (21) he elec onic jou nal o combina o ics 13 (2006), #R75 16 This ollows om he ac ha µis mul iplica i e and in gene al he in e al [E,C]⊆Πnis isomo phic o a ca esian p oduc o (smalle ) pa i ion la ices (see Example 3.9.4 in [19]). I we subs i u e his back in equa ion (20) we ha e wo cases o conside . When F6=E,ou assump ion ha F6<Ep ohibi s he possibili y ha F≤B=E.Thuswemus always ha e B6=Eand in his case TC E,F = 0. When F=E, he only alue o Bwhe e equa ion (21) does no anish is when B=E=Fand we ge TC E,E =µ(E,C)µ(E,E)=µ(E,C). I we compa e his o equa ion (19) we conclude ou p oo o (ii).  No ice ha he cha ac e o he module ( he ace o he ma ix ep esen ing he ac ion o kΠn)VB om o mula (5) is gi en by he o mula χVB(A)=δB≤(A)whenA∈kΠn ac s on VB. We obse e ha equa ion (18) o xAyields pA=X B≤A xB=X B χVB(A)xB. This means ha he cha ac e s o he simple modules o (Π,∧) a e encoded in he change o basis coe icien s be ween he pand xbasis. Simila ly, he cha ac e o he module WBwhen ac ed on by he elemen A∈kΠn a e gi en by he o mula χWB(A)=δB≥(A) om equa ion (11). O cou se he de ining ela ion o he pbasis om equa ion (17) shows ha pA=X B χWB(A)mB. We obse e in his o mula ha he cha ac e s o he simple modules o (Π,∨) a e encoded in he change o basis coe icien s be ween he pand mbasis. Bo h hese o mulas a e in ai ly close analogy wi h he o mula o he expansion o he powe basis in he Schu basis in he algeb a o he symme ic unc ions. The e he change o basis coe icien s a e he cha ac e s o he simple modules o he symme ic g oup. This shows ha he p-basis which was de ined by Rosas and Sagan [17] does ep esen he analogue o he powe basis in he algeb a o he symme ic unc ions and he xand he mbases encode in hei coe icien s he cha ac e s o he modules ha hey ep esen . Rema k 4.3 One could also de ine a hi d algeb a (kΠn,@) whe e A@B=δA=BAand cons uc he simple modules as we ha e done he e o (kΠn,∧)and(kΠn,∨). This same cons uc ion shows ha he simple modules o his algeb a sa is y a enso p oduc , induc ion and es ic ion ope a ions which make he G o hendieck ing (o he ca ego y o he ini e dimensional p ojec i e modules) o his algeb a isomo phic again o NCSym as a bialgeb a whe e he simple modules beha e as he elemen s pA∈NCSym and pAis de ined in (17). he elec onic jou nal o combina o ics 13 (2006), #R75 17 Rema k 4.4 Summa y o 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 I would be in e es ing o ind a o mula o ∆(xA). Re e ences [1] M. Aguia , N. Be ge on and F. So ile,Combina o ial Hop Algeb as and Gene alized Dehn-Somme ille Rela ions, Composi io Ma hema ica 142 (2006) 1-30. [2] M. Aguia and S. Mahajan,Coxe e g oups and Hop algeb as, Fields Ins i u e Monog aphs, Volume 23 (2006), AMS, P o idence, RI. [3] M. Aguia and F. So ile,S uc u e o he Mal enu o-Reu enaue Hop algeb a o pe mu a ions, Ad ances in Ma hema ics, 191 n2 (2005) 225-275. [4] P. Baumann and C. Hohlweg,A Solomon’s heo y o he w ea h p oduc s Go Sn, To appea a T ansac ion o he Ame ican Ma hema ical Socie y, 64p. A Xi ma h.CO/0503011. [5] N. Be ge on, F. Hi e and J.-Y. Thibon,The peak algeb a and he Hecke- Cli o d algeb as a q= 0, Jou nal o Combina o ial Theo y, Se ies A, 107, 1, (2004), 1–19. [6] N. Be ge on, S. Myky iuk, F. So ile, and S. an Willigenbu g,Pie i Ope a ions on Pose s, Jou nal o Combina o ial Theo y, Se ies A, 91 (2000), 84–110. he elec onic jou nal o combina o ics 13 (2006), #R75 18 [7] N. Be ge on, C. Reu enaue , M. Rosas and M. Zab ocki,In a ian s and Coin a ian s o he Symme ic G oup in Noncommu ing Va iables, oappea a he Canadian Jou nal o Ma hema ics, A Xi ma h.CO/0502082. [8] N. Be ge on and M. Zab ocki,The Hop Algeb a o symme ic unc ions in non-commu ing a iables is ee and co ee, submi ed. A Xi ma h.CO/0509265. [9] G. Be gman and P. Cohn,Symme ic elemen s in ee powe s o ings, Jou nal o he London Ma hema ical Socie y, 21 1969 525–534. [10] K. S. B own,Semig oups, ings, and Ma ko chains, Jou nal o Theo e ical P ob- ababili y, 13 (2000), no. 3, 871–938. [11] G. Duchamp, F. Hi e and J. Y. Thibon,Noncommu a i e symme ic unc- ions. VI. F ee quasi-symme ic unc ions and ela ed algeb as, In e na ional Jou nal o Algeb a and Compu a ion 12 (2002), no. 5, 671–717. [12] F. Hi e , J.-C. No elli and J.-Y. Thibon,Rep esen a ion heo y o he 0- A iki-Koike-Shoji algeb as. To appea (2005). A Xi ma h.CO/0407218. [13] M. E. Ho man,Quasi-shu le p oduc s, Jou nal o Algeb aic Combina o ics, 11 (2000), no. 1, 49–68. [14] L. Huilan,Thesis, Yo k Uni e si y, in p epa a ion. [15] D. K ob and J.-Y. Thibon,Noncommu a i e symme ic unc ions IV: Quan um linea g oups and Hecke algeb as a q= 0, Jou nal o Algeb aic Combina o ics 6 (1997), 339–376. [16] I. Macdonald,Symme ic Func ions and Hall Polynomials, Ox o d Uni . P ess, 1995, second edi ion. [17] M. Rosas and B. Sagan,Symme ic Func ions in Noncommu ing Va iables, T ansac ions o he Ame ican Ma hema ical Socie y, 358 (2006), 215-232. [18] M. Schocke ,The module s uc u e o he Solomon-Ti s algeb a o he symme ic g oup, Jou nal o Algeb a 301 (2006), No. 2, 554–586. [19] R. S anley,Enume a i e Combina o ics, Vol. 1, Camb idge S udies in Ad anced Ma hema ics, 49. Camb idge Uni e si y P ess, Camb idge, 1997. [20] J. Ti s,Two p ope ies o Coxe e complexes. Appendix o “A Mackey o mula in he g oup ing o a Coxe e g oup” (Jou nal o Algeb a 41 (1976), no. 2, 255–264) by Louis Solomon, Jou nal o Algeb a 41 (1976), no. 2, 265–268. [21] M. C. Wol ,Symme ic unc ions o non-commu a i e elemen s, Duke Ma hema - ical Jou nal 2(1936), 626–637. [22] A. V. Zele insky,Rep esen a ions o ini e classical g oups: a Hop algeb a ap- p oach, Sp inge Lec u e No es 869, Sp inge -Ve lag, Be lin-New Yo k (1981). he elec onic jou nal o combina o ics 13 (2006), #R75 19