On the support of the free Lie algebra the Schutze

arXiv:0807.3519v1[math.CO]22Jul2008OnthesupportofthefreeLiealgebra:theSch¨utzenbergerproblemsIoannisC.Michos∗DepartmentofMathematicsandStatistics,UniversityofCyprus,P.O.Box20537,CY-1678,Nicosia,CyprusAbstractM.-P.Sch¨utzenbergeraskedtodeterminethesupportofthefreeLiealgebraLZm(A)onafinitealphabetAovertheringZmofintegersmodmandallpairsoftwinandanti-twinwords,i.e.,wordsthatappearwithequal(resp.opposite)coefficientsineachLiepolynomial.WecharacterizethecomplementofthesupportofLZm(A)inA∗asthesetofwordswsuchthatmdividesallthecoefficientsappearinginthemonomialsofl∗(w),wherel∗istheadjointendomorphismoftheleftnormedLiebracketinglofthefreeLiering.Thiscanberephrased,forwordsoflengthn,intermsoftheactionoftheleftnormedmulti-linearLiebracketinglnofLZm(A)-viewedasanelementofthegroupringofthesymmetricgrouponnletters-onλ-tabloids,whereλisapartitionofn.Calculatingl∗(w)viaallfactorsofwoffixedlengthandtheshuffleproduct,werecovertheresultofDuchampandThibon(1989)forthesupportofthefreeLieringinamuchmorenaturalway.Weconjecturethattwowordsuandvofcommonlengthn1whichlieinthesupportofthefreeLieringaretwin(resp.anti-twin)ifandonlyifeitheru=vornisoddandu=˜v(resp.nisevenandu=˜v),where˜vdenotesthereversalofthewordv,andweprovethatitsufficestoshowthisonlyinthecasewhere|A|=2.RepresentingawordwintwolettersbythesubsetIof[n]={1,2,...,n}consistingofthepositionsthatoneofthelettersoccursinw,thecomputationofl∗(w)leadsustothenotionofthePascaldescentpolynomialpn(I),aparticularcommutativemulti-linearpolynomialwhichisequaltoasignedbinomialcoefficientwhen|I|=1.Weprovidearecursionformulaforitandshowthatifm∤Pi∈I(−1)i−1`n−1i−1´thenwliesinthesupportofLZm(A).Keywords:FreeLiealgebras,Pascaltrianglemodm,shuffleproduct,setpartitions,λ-tabloids1IntroductionLetAbeafinitealphabet,A∗bethefreemonoidonAandA+=A∗\{ǫ}bethefreesemigrouponA,withǫdenotingtheemptyword.Forawordw∈A∗let|w|denoteitslength,|w|adenotethenumberofoccurrencesofthelettera∈Ainwandletalph(w)bethesetoflettersactuallyoccurringinw.LetKbeacommutativeringwithunity.FormostofourpurposesK=Zm,theringZ/(m)ofintegersmodmforanon-negativeintegerm.LetKhAibethefreeassociativealgebraonAoverK.Itselementsarethepolynomialsonnon-commutingvariablesfromAandcoefficientsfromK.EachpolynomialP∈KhAiiswrittenintheformP=Pw∈A∗(P,w)w,where(P,w)denotesthecoefficientofthewordwinP.GiventwopolynomialsP,Q∈KhAi,theirLieproductistheLiebracket[P,Q]=PQ−QP.InthiswayKhAiisgivenaLiestructure.ThefreeLiealgebraLK(A)onAoverKisthenequaltotheLiesubalgebraofKhAigeneratedbyA.WhenKistheringofrationalintegersZ,LK(A)isalsoknownasthefreeLiering.ALiemonomialisanelementofLK(A)formedbyLieproductsoftheelementsa∈A.ALiepolynomialisalinearcombinationofLiemonomials,i.e.,anarbitraryelementofLK(A).ThesupportofLK(A)isthesubsetofA∗consistingofthosewordsthatappear(withanonzerocoefficient)insomeLiepolynomial.Apairofwordsu,viscalledtwin(respectivelyanti-twin)ifbothwordsappearwithequal(respectivelyopposite)coefficientsineachLiepolynomialoverK.M.-P.Sch¨utzenbergerhadposedthefollowingproblems(privatecommunicationwithG.Duchamp):∗E-mailaddresses:[e-mail],[e-mail]freeLieringLZ(A).Problem1.2.DeterminethesupportofLZm(A),form1.Problem1.3.Determineallthetwinandanti-twinpairsofwordswithrespecttoLZ(A).Problem1.4.Determineallthetwinandanti-twinpairsofwordswithrespecttoLZm(A),form1.InviewoftheseproblemsSch¨utzenbergerconsidered,foreachwordw∈A∗,thesmallestnon-negativeinteger-whichwedenotebyc(w)-thatappearsasacoefficientofwinsomeLiepolynomialoverZ.Foreachnon-negativeintegermhealsodefinedandtriedtocharacterizethelanguageLmofallwordswithc(w)=m;considering,inparticular,thecasesm=0andm=1(see[11,§1.6.1]).Form=0thelanguageL0isclearlyequaltothecomplementofthesupportofthefreeLieringLZ(A)inA∗,sinceawordwdoesnotappearinanyLiepolynomialoverZifandonlyifc(w)=0.DuchampandThibongaveacompleteanswertoProblem1.1in[3]andprovedthatL0consistsofallwordswwhichareeitherapoweranofalettera,withexponentn1,orapalindrome(i.e.,aworduequaltoitsreversal,denotedby˜u)ofevenlength.Thenon-trivialpartoftheirworkwastoshowthateachwordnotofthepreviousformliesinthesupportofLZ(A)andthiswasachievedbyaconstructionofanadhocfamilyofLiepolynomials.Thisresultwasextendedin[2]-undercertainconditions-totraces,i.e.,partiallycommutativewords(see[1]foranexpositionoftracetheory)insteadofnoncommutativeones,andthecorrespondingfreepartiallycommutativeLiealgebra(alsoknownasgraphLiealgebra).Form=1allLyndonwordsonA(formoreonthissubjectseee.g.,[7,§5.1and§5.3])lieinL1sincetheelementPwoftheLyndonbasisofLZ(A)thatcorrespondstothestandardfactorizationofagivenLyndonwordwisequaltowplusalinearcombinationofgreaterwords-withrespecttothelexicographicorderinginA+-ofthesamelengthasw[7,Lemma5.3.2].Ontheotherhand,thereexistnonLyndonwordswhichalsolieinL1.Forexample,onecancheckthattheworda2b2a-whichisclearlynonLyndonasitstartsandendswiththesameletter-appearswithcoefficientequalto−1intheLiemonomialPa3b2=[a,[a,[[a,b],b]]]andtherefore(−Pa3b2,a2b2a)=1.InSection2werelateProblems1.1upto1.4withthenotionoftheadjointendomorphisml∗ofthele