Order Structure on the Algebra of Permutations and of Planar Binary Trees
JEAN-LOUIS LODAY [email protected]
Institut de Recherche Math´ematique Avanc´ee, CNRS et Universit´e Louis Pasteur 7 rue R. Descartes, 67084 Strasbourg Cedex, France
MAR´IA O. RONCO [email protected]
Departamento de Matem´atica, Ciclo B´asico Com´un, Universidad de Buenos Aires Pab. 3, Ciudad Universitaria, Nu˜nez, (1428) Buenos-Aires, Argentina
Received October 17, 2000; Revised June 4, 2001; Accepted September 7, 2001
Abstract. LetXnbe either the symmetric group onnletters, the set of planar binaryn-trees or the set of vertices of the (n−1)-dimensional cube. In each case there exists a graded associative product on
n≥0K[Xn]. We prove that it can be described explicitly by using the weak Bruhat order onSn, the left-to-right order on planar trees, the lexicographic order in the cube case.
Keywords: planar binary tree, order structure, weak Bruhat order, algebra of permutations, dendriform algebra
Introduction
LetSnbe the symmetric group acting onnletters. In [6] Malvenuto and Reutenauer showed that the shuffle product induces a graded associative product, denoted∗, on the graded space K[S∞] :=
n≥0K[Sn] (hereK is a field). By using the weak Bruhat order onSnwe give a closed formula for the product of basis elements as follows. Letσ ∈ Spandτ ∈ Sq be two permutations. We define two operations called respectively ‘over’ and ‘under’:
σ/τ =σ ×τ ∈Sp+q and σ\τ =ξp,q·σ×τ ∈Sp+q,
whereξp,q is the permutation whose image is (q+1 q+2. . .q+p 1 2. . .q).
It turns out thatσ/τ ≤σ\τfor the weak Bruhat order ofSp+q. We prove that the product
∗onK[S∞] is given on the generators by the sum of all permutations in betweenσ/τ and σ\τ:
σ ∗τ =
σ/τ≤ω≤σ\τ
ω. (1)
LetYnbe the set of planar binary trees withninterior vertices (so the number of elements inYn is the Catalan number n!(n(2n)!+1)!). In [4] it is shown that there is a graded associative product on the graded spaceK[Y∞] :=
n≥0K[Yn] induced by the “dendriform algebra”
structure ofK[Y∞]. We give a closed formula for the product of basis elements as follows.
There is a partial order onYninduced by❅❅❅❅ <❅❅❅❅❅❅ . Letu ∈Ypandv∈Yqbe two planar binary trees. We define two operations called respectively ‘over’ and ‘under’ as follows.
The elementu/v ∈Yp+q (resp.u\v ∈Yp+q) is obtained by identifying the root ofu with the left most leaf ofv(resp. the right most leaf ofu with the root ofv). It turns out that u/v≤u\vfor the ordering ofYp+q. We prove that the product∗onK[Y∞] is given on the generators by
u∗v=
u/v≤t≤u\v
t. (2)
Let us mention that these operations ‘over’ and ‘under’ on planar binary trees appear in the theory of renormalisation, cf. [2].
Observe that, sinceYndoes not bear a group structure (unlikeSn), the product∗is defined in [5] by a recursive formula. So, a priori, the explicit computation of a productu∗vneeds the computation of many terms. The above formula greatly simplifies this computation.
Let Qn = {±1}n−1. There is a graded associative product on the graded vector space K[Q∞] :=
n≥0K[Qn], where K[Qn] is identified with the Solomon descent algebra (cf. [5, 6]). It is in fact a Hopf algebra called the algebra of noncommutative symmetric functions, which is dual to the algebra of quasi-symmetric functions, cf. [3]. We give a closed formula for the product of basis elements as follows. There is a partial order onQn
induced by−1<+1. Let∈ Qpandδ∈ Qq. We define two operations called respectively
‘over’ and ‘under’ as follows:/δ:=(,−1, δ)∈ Qp+q and\δ :=(,+1, δ) ∈ Qp+q. It is immediate that/δ ≤\δfor the ordering of Qp+q. We prove that the product∗on K[Q∞] is given on the generators by
∗δ=
/δ≤α≤\δ
α=/δ+\δ. (3)
In [5] we constructed explicit maps Sn ψn
→Yn φn
→ Qn
(see also [8], p. 24) and we observed that they are in fact restrictions of cellular maps from the cube to the Stasheff polytope and from the Stasheff polytope to the permutohedron respectively. Moreover, we showed that, after dualization and linear extension, the maps
K[Q∞]→φ∗ K[Y∞]→ψ∗ K[S∞]
are injective homomorphisms of graded associative algebras. We take advantage of this result to deduce formulas (2) and (3) from formula (1).
The content of this paper is as follows. In the first part (Sections 1, 2 and 3) we deal with the partial orders onSn,YnandQnrespectively, and we show that the mapsψnandφnare compatible with the orders. In the second part (Sections 4, 5 and 6) we prove formulas (1), (2) and (3). In the case of the symmetric group and in the case of planar binary trees the
algebras K[S∞] and K[Y∞] have a more refined structure: they are dendriform algebras (cf. [4]). We show that in both cases the products≺andcan also be formulated in terms of the order structure.
In this paper we apply some results about Coxeter groups to the particular case of the symmetric groups. For the convenience of the reader we recall them in the Appendix.
We thank the referees for their careful reading and valuable suggested improvements of the submitted version.
Convention. The vector space overQgenerated by the set Xis denotedQ[X]. The linear dualQ[X]∗ is identified withQ[X] under the identification of the basis with its dual. The image of a permutationσ ∈Snis denoted by (σ(1)σ(2). . . σ(n)).
1. Weak Bruhat order on the symmetric groupSn
Let (W,S) be the Coxeter group (Sn,{s1, . . . ,sn−1}), where Sn is the symmetric group acting on{1, . . . ,n}, andsi is the transposition ofi andi +1. We denote by·the group law ofSn and by 1n the unit. In this section we compare the weak Bruhat order onSn and the shuffles by applying the result of the Appendix. We also introduce in 1.9 the operations
‘over’/and ‘under’\fromSp×Sq toSp+q that are to be used in the Appendix.
For any permutationω∈ Sn, its lengthl(ω) is the smallest integerksuch thatωcan be written as a product ofk generators:ω = si1·si2 ·. . .·sik. Observe that the length of a permutation counts the number of inversions of its image.
By definition, a permutationσ ∈ Snhas adescentati, 1≤i ≤n−1, ifσ(i)> σ(i+1).
The set ofdescents of a permutationσisDesc(σ) := {si|σ has a descent ati}. Hence, for any subset J⊆ {s1, . . . ,sn−1}the set
XnJ:= {σ ∈Sn |l(σ ·si)>l(σ),for allsi ∈ J}
described in the Appendix is the set of all permutations σ ∈ Sn such thatDesc(σ) ⊆ {s1, . . . ,sn−1} \J.
In order to simplify the notation, we denote the subset{s1, . . . ,sp−1,sp+1, . . . ,sp+q−1} of{s1, . . . ,sp+q−1}by{sp}c. The setX{ps+p}qcis the set of all (p,q)-shuffles ofSp+q, that is
Sh(p,q) := {σ ∈Sp+q |σ(1)<· · ·< σ(p) and σ(p+1)<· · ·< σ(p+q)}.
There exists a canonical inclusionι:Sp×Sq →Sp+q, which maps the generatorsi ofSp
tosiinSp+q, and the generatorsjofSqtosj+pinSp+q. In other words we let a permutation ofSpact on{1, . . . ,p}and we let a permutation ofSqact on{p+1, . . . ,p+q}. In what follows we identifySp×Sqwith its image inSp+q.
Observe that, forJ= {sp}c, the standard parabolic subgroupW{sp}cdefined in the Appendix is preciselySp×SqinSp+q.
Proposition A.2 of the Appendix takes the following form for the Coxeter groupSn: Lemma 1.1 Let p,q ≥1.
(a) For anyσ ∈ Sp+qthere exist unique elementsξ ∈Sh(p,q)andω∈ Sp×Sqsuch that σ =ξ·ω.
(b) For anyξ ∈ Sh(p,q)and anyω ∈ Sp ×Sq the length ofξ ·ω ∈ Sp+q is the sum:
l(ξ·ω)=l(ξ)+l(ω).
(c) There exists a longest element in Sh(p,q),denotedξp,q,andξp,q =(q+1 q+2 . . . q+p 1 2. . .q).
Definition 1.2 Forn ≥ 1, theweak ordering(also calledweak Bruhat order) on Sn is defined as follows:
ω≤σinSn, if there existsτ ∈ Sn such thatσ =τ ·ω withl(σ)=l(τ)+l(ω).
The set of permutations Sn, equipped with the weak ordering is a partially ordered set, with minimal element 1n, and maximal element the cycleωn0:=(n n−1. . . 2 1) (cf. [1]).
For instance, forn=2 we get 12→s1
and forn=3 we get 13
s2 s1
↓ ↓
s1s2 s2s1
s1s2s1
sinces1s2s1=s2s1s2. Herea→bmeansa<b.
Forn≥1 and 1≤i≤ j ≤n−1, letci,j∈ Snbe the permutation:
ci,j :=si·si+1·. . .·sj.
Givenω∈ Sh(p,q), it is easy to check that, ifω=1p+q, then there exist integersl ≥0, 1≤i1<i2 <· · ·<il+1≤ p+q−1, andik≤ p+k−1, for 1≤k≤l+1, such that:
ω=cil+1,p+l·cil,p+l−1·. . .·ci1,p. Under this notation one has
ξp,q =cq,p+q−1·cq−1,p+q−2·. . .·c1,p.
Corollary A.4 of the Appendix and Lemma 1.1 imply the following result:
Lemma 1.3 Let p,q ≥ 1be two integers. The longest element of the set Sh(p,q) (all (p,q)-shuffles)isξp,q. Moreover,one has
Sh(p,q)= {ω∈Sp+q |ω≤ξp,q}.
Lemma 1.4 Ifσ, σ∈ Sp andτ, τ∈ Sqare permutations verifyingσ ≤σandτ ≤τ, thenσ×τ ≤σ×τ.
Proof: The permutationsσ ×τ andσ×τbelong to the subgroupSp×Sq ofSp+q. Since σ ≤ σ andτ ≤ τ, there existδ ∈ Sp and ∈ Sq such thatσ = δ·σ and τ=·τ, withl(σ)=l(δ)+l(σ) andl(τ)=l()+l(τ).
One hasσ×τ=δ·σ×·τ =(δ×)·(σ×τ), withl(σ×τ)=l(σ)+l(τ)= l(δ×)+l(σ×τ).
Lemma 1.5 Let p and q be two nonnegative integers,and letσ ∈ Spandτ ∈Sq be two permutations. Ifω1andω2are two elements of Sh(p,q)such thatω1< ω2,then
ω1·(σ×τ)< ω2·(σ×τ).
Proof: The result follows immediately from Lemma 1.1.
Definition 1.6 Thegrafting ofσ ∈ Spandτ ∈ Sq is the permutationσ ∨τ ∈ Sp+q+1
given by:
(σ∨τ)(i) :=
σ(i) if 1≤i ≤ p,
p+q+1 if i =p+1,
τ(i−p−1)+p if p+2≤i ≤ p+q+1.
It is easily seen that,
σ∨τ =(σ ×τ×11)·sq+p·sq+p−1·. . .·sp+1, forσ ∈Spandτ ∈Sq.
Lemma 1.7 Ifσ ≤σin Spandτ ≤τin Sq,thenσ∨τ ≤σ∨τin Sp+q+1.
Proof: Supposeσ=·σandτ=δ·τ, for some∈Spandδ∈Sqsuch thatl(σ)=l() +l(σ) andl(τ)=l(δ)+l(τ). Clearly,σ∨τ=(×δ×11)·(σ∨τ).
The permutationsσ ×τ ×11andσ×τ×11 belong to the subgroupSp+q ×S1 of Sp+q+1.
It is immediate to check thatl((sp+1 ·. . .·sp+q)·si) > l(sp+1·. . .·sp+q), for any 1≤i ≤ p+q−1, that issp+1·. . .·sp+q ∈Sh(p+q,1). Sincesp+1. . .sp+q =cp+1,p+q, by Lemma 1.1 one hasl((sp+1·. . .·sp+q)·ω)=q+l(ω), for anyω∈Sp+q×S1. So
l(σ∨τ)=l((σ∨τ)−1)=l(σ)+l(τ)+q
=l()+l(δ)+l(σ)+l(τ)+q
=l(×δ×11)+l(σ∨τ).
Proposition 1.8 Letσ ∈ Snbe a permutation such thatσ(i)=n,for some1≤i ≤n.
There exist unique elementsσl ∈Si−1, σr ∈Sn−i andγ ∈Sh(i−1,n−i)such that:
σ =(γ×11)·(σl∨σr).
Proof: Sinceσ(i)=n, the elementσmay be written asσ =σ·sn−1·sn−2·. . .·si, with σ∈Sn−1×S1andl(σ)=l(σ)+n−i.
Lemma 1.1 implies that there exist unique elements∈Sh(i −1,n−i +1) andδ ∈ Si−1×Sn−i+1, such thatσ=·δ. Since the permutationsn−1does not appear in a reduced expression ofσ, the following assertions hold:
– the elementis of the form=γ ×11for someγ ∈ Sh(i−1,n−i).
– the elementδbelongs toSi−1×Sn−i×S1. So,δ =σl×σr×11, for uniqueσl ∈Si−1
andσr ∈ Sn−i.
Finally, we get thatσ =(γ ×11)·(σl∨σr). The uniqueness ofγ,σl andσr follows easily.
Definition 1.9 Forp,q≥1, the operations ‘over’/and ‘under’\fromSp×SqtoSp+q, are defined as follows:
σ/τ :=σ×τ, and σ\τ :=ξp,q·(σ×τ), forσ ∈Spandτ ∈Sq.
Sinceσ ×τ ∈ Sp×Sq, for anyσ ∈ Spandτ ∈ Sq, andξp,q ∈ Sh(p,q), the following relation holds:
σ/τ ≤σ\τ.
Lemma 1.10 The operations/and\are associative.
Proof: Letσ ∈ Sp,τ ∈ Sqandδ∈Sr. It is clear that (σ×τ)×δ=σ×τ ×δ=σ×(τ ×δ).
The formula above and the equality
ξp+q,r·(ξp,q×1r)=ξp,q+r ·(1p×ξq,r) imply that the operation\is associative too.
2. Weak ordering on the set of planar binary trees
Forn≥1, letYndenote the set of planar binary trees withnvertices:
Y0 = {|}, Y1=
❅❅
❅
❅ , Y2=
❅❅
❅
❅ ,❅❅❅❅❅❅ , Y3=
❅❅
❅
❅ ,❅❅ ❅❅❅❅ ,❅❅❅❅❅❅ ,❅❅❅❅❅❅❅ ,❅❅❅❅❅❅ ❅❅❅ . Thegrafting of ap-treeuand aq-treevis the (p+q+1)-treeu∨vobtained by joining the roots ofuandvto a new vertex and create a new root. For any treet there exist unique treestlandtr such thatt =tl∨tr. As a result we haveYn=
p+q+1=nYp×Yq.
Definition 2.1 Let≤be theweak orderingonYngenerated transitively by the following relations:
(a) ifu≤u∈Ypandv≤v∈Yq, thenu∨v≤u∨vinYp+q+1, (b) ifu∈Yp,v∈Yqandw∈Yr, then (u∨v)∨w≤u∨(v∨w).
The pair (Yn,≤) is a poset.
Definition 2.2 The operations ‘over’/and ‘under’\fromYp×Yq toYp+q are defined as follows:
– u/vis the tree obtained by identifying the root ofuwith the left most leaf ofv, – u\vis the tree obtained by identifying the right most leaf ofuwith the root ofv,
❅❅
❅❅
❅❅
❅u
u/v= v ❅❅❅
❅❅
❅❅
❅❅
❅❅
uv u\v=
It is immediate to check that/and\are associative.
Equivalently these operations can be defined recursively as follows:
– t/|:=t =:|\tandt\|:=t =:|/tfort ∈Yn, – foru=ul∨urandv=vl∨vr one has
u/v:=(u/vl)∨vr, and u\v:=ul∨(ur\v).
Lemma 2.3 For any trees u∈Ypandv∈Yq one has u/v≤u\v.
Proof: This is an immediate consequence of condition (b) of Definition 2.1.
The surjective mapψn : Sn → Yn considered in [5] (see also [8] p. 24) is defined as follows:
– ψ0([ ])= | ∈Y0, – ψ1(11)=❅❅❅❅ ∈Y1,
– the image of a permutationσ ∈Snis made of two sequences of integers: the sequence on the left ofnand the sequence on the right ofnin (σ(1), . . . , σ(n)). These permutations are precisely the ones appearing in Proposition 1.8. Observe that one of them may be empty. By relabelling the integers in each sequence so that only consecutive integers (starting with 1) appear, one gets two permutations σl andσr. For instance (341625) gives the two sequences (341) and (25), which, after relabelling, give (231) and (12).
Recursivelyψn(σ) is defined asψp(σl)∨ψq(σr).
Notation Forn≥1, letSt be the subset ofSnsuch that a permutationσ ∈Snbelongs to St if and only ifψn(σ)=t, i.e.
St :=ψn−1(t)⊂Sn.
This subset admits the following description in terms of shuffles.
Forn=1, one hasS
❅❅
❅
❅ := {11} =S1.
Forn≥2, lett=tl∨tr, withtl ∈Yqandtr ∈Ypandq+p=n−1. We have St = {(γ×11)·(σ∨τ)|γ ∈Sh(p,q), σ ∈ Stl andτ ∈ Str},
for 1 ≤q ≤n−2. Ifq =0, thenS|∨tr = {| ∨σ, forσ ∈ Str}. And, ifq =n−1, then Stl∨| = {σ∨ |, forσ ∈Stl}.
For instance whenn =2,S❅❅❅❅ := {12}andS❅❅❅❅❅❅ := {s1}.
Definition 2.4 Forn≥0, let Min and Max be the maps fromYnintoSndefined as follows:
• Forn=1, Min(❅❅❅❅ ) :=11 =: Max(❅❅❅❅ ).
• Forn=2, Min(❅❅❅❅ ) :=12 =: Max(❅❅❅❅ ), and Min(❅❅❅❅❅❅ ) :=s1=: Max(❅❅❅❅❅❅ ).
• Forn≥3, lett =tl∨tr, withtl∈Yqandtr ∈Ypandp+q =n−1.
The permutations Min(t) and Max(t) are defined as follows:
– If 1 ≤ q ≤ n−2, then Min(t) := Min(tl)∨Min(tr), and Max(t) := (ξq,p ×11)· (Max(tl)∨Max(tr)).
– Ifq=0, then Min(t) :=ξn−1,1·(11×Min(tr)) and Max(t) :=ξn−1,1·(11×Max(tr)).
– Ifq=n−1, then Min(t) :=Min(tl)×11and Max(t) :=Max(tl)×11. Clearly, Min(t) and Max(t) belong toSt, for any treet ∈Yn.
Theorem 2.5 Let n ≥1and t ∈Yn. The following equality holds:
St = {ω∈ Sn|Min(t)≤ω≤Max(t)}.
Proof: Supposet =tl∨tr, withtl ∈Yq,tr ∈Yq andn=q+p+1.
Step 1. Letγandγbe elements ofSh(p,q) such thatγ ≤γ. Suppose thatσ ≤σinSp
andτ ≤τinSq.
Lemma 1.7 implies thatσ∨τ ≤σ∨τ. Now,γ×11andγ×11belong toSh(p,q+1), andσ∨τ andσ∨τare elements ofSp×Sq+1; from Lemma 1.1 one gets,
(γ×11)·(σ∨τ)≤(γ×11)·(σ∨τ).
For anyγ ∈Sh(p,q), Lemma 1.3 states that 1p+q ≤γ ≤ξp,q. It follows that allω∈St
satisfies Min(t)≤ω≤Max(t).
Step 2. Conversely, letω∈Sn be such that Min(t)≤ω≤Max(t).
Since Min(t) ≤ ω, there exists ω1 ∈ Sn such that ω = ω1 ·sp+q ·. . .·sp+1, with l(ω)=l(ω1)+l(sp+q· · ·. . .·sp+1)=l(ω1)+q.
By Lemma 1.1, there exist unique elementsω2∈Sh(p,q+1) andω3∈Sp×Sq+1, such thatω1=ω2·ω3, withl(ω1)=l(ω2)+l(ω3).
Sinceω≤Max(t), there existsδ∈ Snsuch that (ξp,q×11)·(Max(tl)×Max(tr)×11)=δ·ω1, withl(ξp,q)+l(Max(tl))+l(Max(tr))=l(δ)+l(ω1).
The permutationsp+qdoes not appear in a reduced expression ofω1. So,ω2∈Sh(p,q+1) andω2(n)=n, which implies thatω2≤ξp,q×11.
On the other hand, the elementω3∈Sp×Sq+1andsp+qdoes not appear in a reduced de- composition ofω3. So,ω3∈Sp×Sq×S1. Consequentlyω3is of the formω3 =σ4×τ4×11, for unique permutationsσ4∈Spandτ4∈ Sq. Moreover, the inequalities
(Min(tl)×Min(tr)×11)·sp+q·. . .·sp+1
≤ω2·(σ4×τ4×11)·sp+q·. . .·sp+1
≤(ξp,q×11)·(Max(tl)×Max(tr)×11)·sp+q ·. . .·sp+1
imply
Min(tl)×Min(tr)×11≤ω2·(σ4×τ4×11)
≤(ξp,q×11)·(Max(tl)×Max(tr)×11).
Since 1n≤ω2 ≤ξp,q×11inSh(p,q+1), by applying Lemma 1.5 we get Min(tl)×Min(tr)≤σ4×τ4 ≤Max(tl)×Max(tr).
The elementsσ4andτ4satisfy that Min(tl)≤σ4≤Max(tl) and Min(tr)≤τ4 ≤Max(tr).
A recursive argument states thatσ4∈Stl andτ4∈Str, and the proof is complete.
Corollary 2.6 The weak ordering of Sninduces a partial order≤B on Yn. This order is compatible withψn :Sn →Yn:
σ ≤τ ⇒ψn(σ)≤B ψn(τ).
Proposition 2.7 The order≤Binduced by the weak order on Yncoincides with the order≤ of Definition2.1.
Proof: We want to see that the order≤Bsatisfies conditions (a) and (b) of Definition 2.1.
Givent ∈Yn andw ∈Ymrecall that, for anyσ ∈ Stand anyτ ∈ Sw, the permutation σ ∨τ belongs toSt∨w. Lemma 1.7 implies that≤B verifies condition (a).
Lett ∈Yn,u ∈Yrandw∈Ymbe three trees. Suppose thatσ ∈ St,δ ∈Su andτ ∈ Sw. One has that (σ∨δ)∨τbelongs toS(t∨u)∨w, whileσ∨(δ∨τ) belongs toSt∨(u∨w). To prove condition (b), it suffices to check that (σ∨δ)∨τ ≤σ ∨(δ∨τ) inSn+r+m+2.
Now, an easy calculation shows that:
(σ∨δ)∨τ =(σ ×δ×11×τ ×11)·sn+r+m+1·. . .·sn+r+2·sn+r·. . .·sn+1, and
σ∨(δ∨τ)=(σ ×δ×τ ×12)·sn+r+m·. . .·sn+r+1·sn+r+m+1·. . .·sn+1. We need to show that (σ ×δ×11 ×τ ×11)·sn+r+m+1 ·. . .·sn+r+2 is smaller than (σ ×δ×τ ×12)·sn+r+m·. . .·sn+r+1·sn+r+m+1·. . .·sn+r+1. We use the relation
sn+r+m·. . .·sn+r+1·sn+r+m+1·. . .·sn+r+1
= sn+r+m+1·. . .·sn+r+1· sn+r+m+1·. . .·sn+r+2. We have to prove that
(σ×δ×11×τ×11)≤(σ×δ×τ×12)·sn+r+m+1·. . .·sn+r+1; which is a consequence of the formula:
(11×τ×11)≤(τ ×12)·sm+1·. . .·s1, for any τ ∈Sm, m≥1. (2.6.1) To prove (2.6.1) it suffices to check that
l(sm+1·. . .·s1·(11×τ ×11))=m+1+l(11×τ×11).
This is clearly the case sincesm+1·. . .·s1is inSh(1,m+1) and 11×τ×11belongs to S1×Sm+1. To end the proof, it suffices to observe that
(τ ×12)·sm+1·. . .·s1=sm+1·. . .·s1·(11×τ ×11), for any τ ∈Sm, m≥0.
Corollary 2.8 The mapψn:Sn→Ynis a morphism of posets.
Theorem 2.9 Letσ ∈ Spandτ ∈Sqbe two permutations. The following equalities hold:
ψp+q(σ/τ)=ψp(σ)/ψq(τ) and ψp+q(σ\τ)=ψp(σ)\ψq(τ).
Proof: Inσ/τ =σ×τ, under the mapSp×Sq →Sp+q, the symbols permuted byσare strictly smaller and all to the left of the symbols permuted byτ. Hence under the definition ofψnas given after Lemma 2.3, one hasψp+q(σ ×τ)=ψp(σ)/ψq(τ). The proof of the other case is symmetric.
3. Weak ordering on the set of vertices of the hypercube
Forn ≥ 2, let Qn := {+1,−1}n−1 be the set of vertices of the hypercube. There is a surjective map φn : Yn → Qn, which is defined as follows. First we label the interior leaves from left to right by 1,2, . . . ,n−1. Second, we putφn(t)=(1, . . . , n−1), where i is−1 when the stem of theith leaf oft is right oriented (more precisely SW-NE), and +1 when it is left oriented (more precisely SE-NW). We take into account only the interior leaves oft, since the orientation of the two extreme ones does not depend ont. For instance φ2(❅❅❅❅❅❅ )=(+1) andφ2(❅❅❅❅ )=(−1). By conventionQ1= {(−1)1}andφ1(❅❅❅❅ )=(−1)1.
We considerQ2as the partially ordered setQ2 := {−1<+1}.
Definition 3.1 The set Qn of vertices of the hypercube is a partially ordered set for the order:
≤η if and only if i ≤ηi, for all 1≤i≤n−1.
We denote by (−1)nthe minimal element ofQn, and by (+1)nits maximal element.
Definition 3.2 Given an element=(1, . . . , p−1)∈Qpand an elementη=(η1, . . . , ηq−1)∈ Qq thegraftingofandη, denoted∨η, is the element ofQp+q+1given by:
∨η:=(1, . . . , p−1,−1,+1, η1, . . . , ηq−1).
The operations over/and under\fromQp×QqtoQp+q are defined by /η:=(1, . . . , p−1,−1, η1, . . . , ηq−1),
\η:=(1, . . . , p−1,+1, η1, . . . , ηq−1).
Remark 3.3 It is easily seen that the mapsφnpreserve the operations grafting∨, over/, and under\.
Lemma 3.4 Let t be an element of Ynsuch that its i th leaf points to the right,for some 1 ≤i ≤n−1. Ifwis another tree in Yn such thatw≤ t,then the i th leaf ofwis right oriented too.
Proof: The result is obvious forn ≤2.
Since the order≤onYnis transitively generated by the relations given in Definition 2.1, it suffices to show that the assertion is true for the situations described in (a) and (b) of this Definition.
For (a): Ifw=wl∨wr andt =tl∨tr, withwl≤tlandwr ≤tr, then the results is an immediate consequence of the inductive hypothesis.
For (b): Supposew =(u∨v)∨sandt =u∨(v∨s), for someu ∈Yp,v ∈Yq and s ∈ Yr. Ifq ≥1, then thekth leaf ofwis oriented in the same direction that thekth leaf oft, for all 1≤k≤n−1.
Ifq=0, then thekth leaf ofwis oriented in the same direction that thekth leaf oft, for allk= p+2. And the (p+2)th leaf ofwis right oriented, while (p+2)th leaf oftis left oriented.
Proposition 3.5 For all n≥1and all∈ Qnthere exist two trees in Yn,denotedmin() andmax()respectively,such that the inverse image ofbyφn:Yn→ Qnsatisfies:
φ−1()= {t ∈Yn |min()≤t ≤max()}.
Proof: Step 1. The inverse imageφn−1((−1)n) of the minimal element ofQnis the minimal tree an of Yn which has all its leaves pointing to the right. Similarly, the inverse image φn−1((+1)n) of the maximal element of Qn is the maximal treezn ofYn which has all its leaves pointing to the left. So, the theorem is obviously true for∈ {(−1)n,(+1)n}if we define:
min((−1)n) :=an =: max((−1)n), and min((+1)n) :=zn=: max((+1)n).
If /∈ {(−1)n; (+1)n}, we define max and min recursively, as follows:
(a) If1= −1 there existk≥1 and∈Qn−ksuch that=(−1)k/. Define min() :=
ak/min().
If1= +1, there existk≥2 and∈ Qn−ksuch that=(+1)k/. Define min() := zk/min().
(b) If n−1 = −1, there exist k ≥ 2 and ∈ Qn−k such that = \(−1)k. Define max() :=max()\ak.
If n−1 = +1, there exist k ≥ 1 and ∈ Qn−k such that = \(+1)k. Define max() :=max()\zk.
Step 2. It is easy to prove, by induction onn, that ift∈φ−n1(), then min()≤t ≤max().
Conversely, lett be a tree such that min() ≤ t ≤ max(). Since min() ≤ t, Lemma 3.4 implies that the ith leaf oft is left oriented, for alli such that i = +1. Similarly, t ≤max() and Lemma 3.4 imply that theith leaf oft is right oriented, for allisuch that i = −1. So,tbelongs toφ−1n ().
Corollary 3.6 For n ≥2,the order of Yninduces a partial order≤B on Qn. This order is compatible withφn :Yn → Qn.
Proposition 3.7 The order≤Bof Qn coincides with the order≤of Definition3.1.
Proof: Ifw andt are two trees inYn such that w ≤ t, then Lemma 3.4 implies that φn(w)≤φn(t). It proves that if≤B ηinQn, then≤η.
To prove that≤ηinQnimplies that≤B η, it suffices to show that
(1, . . . , p−1,−1, p+1, . . . , n−1)≤B (1, . . . , p−1,+1, p+1, . . . , n−1),
for all 1≤ p≤n−1 and all elementsi ∈ {−1,+1}, 1≤i≤n−1, i = p. Consider the elementκ :=(1, . . . , p−1) in Qp, and the elementρ :=(p+1, . . . , n−1)∈ Qn−p. Let t ∈Ypbe a tree inφ−1p (κ) andw∈Yn−pbe a tree inφ−1n−p(ρ). It is easy to check that
φn(t/w)=(1, . . . , p−1,−1, p+1, . . . , n−1) and φn(t\w)=(1, . . . , p−1,+1, p+1, . . . , n−1).
Since Lemma 2.3 states thatt/w≤t\winYn, one gets the result.
Corollary 3.8 The mapφn:Yn →Qnis a morphism of posets.
(See also [8], p.24.)
4. The graded algebra of permutations Q[S∞] Consider the graded vector spaceQ[S∞] :=
n≥0Q[Sn], equipped with the shuffle prod- uct∗defined by:
σ∗τ :=
x∈Sh(p,q)
x·(σ×τ), for σ ∈Sp and τ ∈Sq.
In [6], C. Malvenuto and C. Reutenauer prove that (Q[S∞],∗) is an associative algebra over Q. We denote byQ[S∞] the augmentation ideal.
Theorem 4.1 Letσ ∈Sp andτ ∈ Sqbe two permutations. The productσ∗τ is the sum of all permutationsω∈Sp+q verifying
σ ×τ ≤ω≤ξp,q·(σ×τ),in other words:
σ∗τ =
σ/τ≤ω≤σ\τ
ω.
Proof: Lemma 1.5 implies that
σ×τ ≤δ·(σ×τ)≤ξp,q·(σ×τ), for any δ∈ Sh(p,q).
Suppose thatω∈ Sp+qsatisfiesσ×τ ≤ω≤ξp,q·(σ×τ). Letω1∈Sp+qbe such that ω=ω1·(σ×τ). It is obvious that 1p+q ≤ω1.
Sinceω ≤ ξp,q·(σ ×τ), the definition of the weak ordering implies that there exists ∈Sp+q such thatξp,q·(σ×τ)=·ω1·(σ×τ), withl(ξp,q)=l()+l(ω1). It implies, by Lemma 1.3, thatω1 ∈Sh(p,q). This completes the proof of the Theorem.
Definition 4.2 Forp,q ≥0, the subsetsSh1(p,q) andSh2(p,q) ofSh(p,q) are defined by:
Sh1(p,q) := {ω∈ Sh(p,q)|ω(p+q)= p+q}, and Sh2(p,q) := {ω∈ Sh(p,q)|ω(p)= p+q}.
Remark 4.3 The setSh(p,q) is the disjoint union ofSh1(p,q) andSh2(p,q). Moreover, one has that
Sh1(p,q)= {ω×11|ω∈Sh(p,q−1)} =Sh(p,q−1)×11; and Sh2(p,q)= {(ω×11)·(1p−1∨1q)|ω∈Sh(p−1,q)}
=(Sh(p−1,q)×11)·(1p−1∨1q).
Definition 4.4 The products≺andinQ[S∞] are defined as follows:
σ ≺τ :=
ω∈Sh2(p,q)
ω·(σ ×τ), and
σ τ :=
ω∈Sh1(p,q)
ω·(σ ×τ),
forσ ∈Spandτ ∈Sq.
From Remark 4.3 one gets that the associative product∗ofQ[S∞] satisfies σ∗τ =σ ≺τ +σ τ, forσ, τ ∈Q[S∞].
Proposition 4.5 The operations≺andsatisfy the relations (i) (a≺b)≺c=a ≺(b≺c)+a ≺(bc),
(ii) a(b≺c)=(a b)≺c,
(iii) a(bc)=(a ≺b)c+(a b)c,
for any a,b,c∈Q[S∞]. HenceQ[S∞]is a dendriform algebra(as defined in[4] ).
Proof: This is a consequence of the associativity property of the shuffle together with an inspection about the first element of the image of the permutations.
The products≺andmay also be described in terms of the order≤as follows.
Proposition 4.6 For anyσ ∈ Spand anyτ ∈Sq,one has:
σ ≺τ =
(1p−1∨1q)·(σ×τ)≤ω≤σ\τ
ω,
and
σ τ =
σ/τ≤ω≤(ξp,q−1×11)·(σ×τ)
ω .
