RELATING EDELMAN-GREENE INSERTION TO THE LITTLE MAP ZACHARYHAMAKERANDBENJAMINYOUNG Abstract. We show that two algorithms for reduced words in the symmetric group, Edelman-Greene insertionandtheLittlebijection, areinprinciplethesamemap. Unifyingthetwoapproaches allowsusto 2 provenewpropertiesabouteachmap,andtoresolveseveralconjectures madebyLamandbyLittle. 1 0 2 ct 1. Introduction O 1.1. Preliminaries. In this paper, we clarify the relationship between two algorithmic bijections, due re- 6 spectively to Edelman-Greene [1] and to Little [5], both of which deal with reduced decompositions in the 2 symmetric group, S . It is well known that S can be viewed as a Coxeter group with the presentation n n O] Sn =hw1,w2,...,wn−1 |wi2 =1, wiwj =wjwi for |i−j|≥2, wiwi+1wi =wi+1wiwi+1i where w can be viewed as the transposition (i i+1). Let σ =σ σ ...σ ∈S . A reduced decomposition or C i 1 2 n n reduced expression of σ is a minimal-length sequence w ,w ,...,w such that σ =w w ...w . The . a1 a2 am a1 a2 am h word w =a a ...a is called a reduced word of σ. It is convenient to refer to a reduced decomposition by 1 2 m t a its corresponding reduced wordand we will conflate the two often. The set of all reduced decompositions of m σ is denoted Red(σ). An inversion in σ is a pair (i,j) with i < j and σ > σ . Let l(σ) be the number of i j [ inversions in σ. Since each transposition wi either introduces or removes an inversion, for w = a1...am a reduced word of σ, we see m=l(σ). 1 The enumerative theory of reduced decompositions were first studied in [7], where using algebraic tech- v niques it is shown for the reverse permutation σ =n...21 that 9 1 n ! 1 (1) |Red(σ)|= 2 . 7 (2n−3)(2n−(cid:0)5(cid:1))2...5n−23n−2 . 0 This is the same as the number of standard Young tableaux with the staircase shape λ = (n − 1,n − 1 2,...,1). Inaddition,Stanleyconjecturedforarbitraryσ ∈S that|Red(σ)|canbeexpressedasthenumber n 2 of standard Young tableaux of various shapes (possibly with multiplicity). This conjecture was resolved 1 in [1] using a generalization of the Robinson-Schensted insertion algorithm, usually called Edelman-Greene : v insertion. Edelman-Greene insertion maps a reduced word w to the pair of Young tableaux (P(w),Q(w)) i X where the entries of P(w) arerow-and-columnstrictand Q(w) is a standardYoung tableau. The same map also provides a bijective proof of (1), as there is only one possibility for P(w). r a Algebraictechniquesdevelopedin[4]canbeusedtocomputetheexactmultiplicityofeachshapeforgiven σ. A bijective realization of Lascoux and Schu¨tzenberger’s techniques in this setting is demonstrated in [5]. PermutationswithpreciselyonedescentarereferredtoasGrassmannian. Thereisasimplebijectionbetween reduced words of a Grassmannian permutation σ and standard Young tableaux of a shape determined by σ. The Little map worksby applying a sequence of modifications referredto as Little bumps to the reduced word w until the modified word’s corresponding permutation is Grassmannian so that it can be mapped to a standard Young tableau denoted LS(w). 1.2. Results. SincetheLittlemap’sintroduction,therehasbeenspeculationonitsrelationshiptoEdelman- Greeneinsertion. Intheappendixof[2],writtenbyLittle,Conjecture4.3.2assertsthatLS(w)=Q(w)when themapsarerestrictedtoreducedwordswhichrealizethereversepermutation. Similarcommentsaremade in [5]. We show the connection is much stronger than previously suspected: this equality is true for every permutation. Date:October 29,2012. 1 Theorem 1.1. Let w be a reduced word. Then Q(w)=LS(w). The proof is based on an argument from canonical form. We define the column word, a new reading word of P(w) that plays nice with both Edelman-Greene insertion and Little bumps. We then show the statement’s truth is invariant under Coxeter-Knuth moves, transformations that span the space of reduced words with identical P(w). Given Theorem 1.1, one might suspect the structure of the two maps is intimately related. Specifically, Conjecture2.5of[3]proposesthatLittlebumpsrelatetoEdelman-Greeneinsertioninawaythatisanalogous to the role dual Knuth transformations play for the Robinson-Schensted-Knuth algorithm. Let v and w be reduced words. We say v and w communicate if there exists a sequence of Little bumps changing v to w. This is an equivalence relation as Little bumps are invertible. Theorem 1.2 (Lam’s Conjecture). Let v and w be two reduced words. Then v and w communicate if and only if Q(v)=Q(w). 1.3. Structure of the paper. In the second section, we review those parts of [1, 5] which we need: we define Edelman-Greene insertion and the Little map, as well as generalized Little bumps. Additionally, we statesomepropertiesofthesemapsthatareimportanttoourwork. ThethirdsectiondefinesCoxeter-Knuth transformations and studies their interaction with Little bumps and action on Q(w). We conclude in the fourth section by proving our main results and resolving several conjectures of Little. 2. Two Maps 2.1. Edelman-Greene insertion. Inordertodefine Edelman-Greeneinsertion,we mustfirstdefine arule for inserting a number into a tableau. Let n ∈ N and T be a tableau with rows R ,R ,...,R where 1 2 k R =ri ≤ri ≤···≤ri . We define the insertion rule for Edelman-Greene insertion, following [1]. i 1 2 li (1) If n≥r1 or if R is empty, adjoin k to the end of R . l1 i i (2) If nb1. A word w is Grassmannian if it is the reduced wordof a Grassmannianpermutation. Fromthe Grassmannianwordw=w ...w we constructa 1 m tableau Tab(w) as follows. Index the columns of Tab(w) by b1,...,bn−k and the rows by ak,ak−1,...,a1. Since all inversions in σ feature an a and a b , each w in w represents the swap between an a and a b . i j l i j Forw , weenter m+1−l inthe columnindexedby a andb . Ifa swapswithb ,we seeit mustlaterswap l i j i j with each smaller b. This shows entries are increasing across rows. Likewise, if b swaps with a , it must j i later swap with each larger a so entries increase down columns. From this, we can conclude that Tab(w) is a standard Young tableau whose shape is determined by σ. For a given Grassmannian permutation σ, this map is a bijection as the process is easily reversed. Multiple Grassmannian permutations may correspond 2 Figure 1. Edelman-Greene insertion for w =4,2,1,2,3,2,4 P Q 4 4 P Q P Q 2 2 3 3 2 3 1 3 P Q 1 1 2 1 2 3 1 3 3 2 4 1 4 2 4 2 4 4 P Q P Q P =P(w) Q =Q(w) 5 5 6 6 7 7 1 3 1 3 1 2 1 3 1 2 4 1 3 7 2 2 2 3 2 6 2 3 2 6 3 4 3 4 3 4 4 5 4 5 4 5 Figure 2. The Little mapfor the reduceddecompositionw w w w w w w ofσ =35241. 4 2 1 2 3 2 4 The dashed crosses show the modifications made by the next Little bump. 1 1 1 2 2 2 2 2 1 1 1 3 3 3 3 3 2 2 2 1 4 4 4 4 2 2 3 1 2 2 5 5 3 3 4 4 1 1 6 6 3 3 2 2 1 5 2 2 4 4 3 3 3 6 1 3 4 5 5 5 5 1 1 4 5 6 6 6 6 3 3 1 5 4 4 4 4 4 4 1 6 5 5 5 5 5 5 5 Wiring diagram for w Wiring diagram for w↑ 7 1 1 1 2 2 2 2 2 2 2 2 1 3 3 3 3 1 4 6 3 3 3 3 1 1 5 5 7 1 3 7 4 4 5 5 5 5 1 7 5 2 6 5 5 4 4 4 7 7 1 3 4 6 7 7 7 7 4 4 4 2 5 7 6 6 6 6 6 6 6 Wiring diagram for w↑ ↑ Tab(w↑ ↑ )=LS(w) 7 7 7 7 3 to the same shape. However, they will only differ by some fixed points at the beginning and end of the permutation. 2.3. Little bumps and the Little map. We nowdescribethe methodin[5]fortransforminganarbitrary reduced wordinto the reducedwordof a Grassmannianpermutation. Let w=w ...w be a reduced word 1 m and w(i) =w1...wi−1wi+1...wm. We construct w(i−) = w1...wi−1(wi−1)wi+1...wm if wi >1 ((w1+1)...(wi−1+1)wi(wi+1+1)...(wm+1) if wi =1 by decrementing w by one or incrementing each other entry if w =1. i i Let w be a reduced word so that w(i) is also reduced. Note w(i−) may not be reduced, as w −1 may i swap the same values as some w with j 6= i. However, this is the only way w(i)− can fail to be reduced as j w(i) is reduced and we have added one additional swap. Removing w from w(i−), we obtain a new reduced j word w(i−)(j). Repeating this process of decrementation, we can construct w(i−)(j−) and so on until we are left with a reduced wordv =v ...v . We refer to this process as a Little bump beginning at position i and 1 m say v = w↑ , where i is the initial index the bump was started at. To see that this process terminates, we i refer to the following lemma. Lemma 2.1 (Lemma5,[5]). Let w be a reducedword suchthat w(i) is reduced. Let i ,i ,... be thesequence 1 2 of indices decremented in w↑ . Then the entries of i ,i ,... are unique. i 1 2 Since w is finite, we see the process terminates so that w↑ is well-defined. We highlight a property of i Little bumps observed in [5], that they preserve the descent structure of w. Corollary 2.2. Let w = w ...w and v = v ...v be a reduced words and ↑ be a Little bump such that 1 m 1 m v =w↑. Then v >v if and only if w >w for all i. i i+1 i i+1 Proof. Let w > w . As each w is decremented at most once, we see v ≥ v , but v 6= v . Thus i i+1 i i i+1 i i+1 v >v . By the same reasoning, if w x+1, we see x and x+1 1 2 are inserted into the same position, so Q(wα) =Q(w)ti−1,i. Let p =x+1. Since w|i+2 is reduced, ǫ =x+2. Therearetwopossibilities. We examinethecasewhereǫ i >···>i . 1 2 tk 7 Lemma 4.1. Let w = w ...w be a reduced decomposition of a Grassmannian permutation σ. Then 1 m Tab(w)=Q(w). Proof. Let σ = a1a2...an−kb1b2...bk be a Grassmannian permutation with sole descent an−kb1 and w = w ...w areduceddecompositionofσ. Notethetrajectoriesoftheb ’sarenon-intersectingasnotwoswap 1 m j with each other. We now show that when applying Edelman-Greene insertion to w, if w is in the trajectory of b , then k j wk will be inserted into the jth column of Pn+1−k(w) and each entry bumped during this insertion will in turn insert into the jth column. From this, we can conclude that Tab(w)=Q(w). If b has the only non-trivial trajectory amongst the b , then Q(w)=Tab(w) trivially: there is only one 1 j column in Tab(w). Assume there are multiple b with non-trivial trajectories. Let {i ,i ,...,i } be the j 1 2 t2 trajectoryof b . Note w =w +1. Then b has trajectory{l ,...,l } with t ≥t and l >i , i.e. the 2 ik ik+1 1 1 t1 1 2 k k kth from last swap featuring b comes later than the kth from last featuring b and so on. Inserting from 1 2 right to left, we see that upon inserting any w , we will have already inserted w . Therefore, w will it2 lt1 it2 be inserted into the second column as any previously inserted entry will be from the trajectory of b , and 1 thus insertinto the first column. When w is inserted, it too will insertinto the secondcolumnas w it2−1 lt1−1 will have been inserted into the first column. For identical reasons as before, w will remain in the second it2 column upon being bumped. We then see inductively that, unimpeded by other swaps, the trajectory of b 2 will insert one after another into the second column. The same argument applies to b and so on. Thus 3 Tab(w)=Q(w). (cid:3) 4.2. The column reading word. The onlyingredientmissingfromourargumentis a canonicalformthat is invariant under Little bumps. Definition 4.2. ForT aYoungtableauwithcolumnsC1,C2...,Cm whereCi =ci,ci,...,ci withci being 1 2 k j the(j,i)thentryofT. Wedefinethecolumnreading word ofT tobethewordτ(T)=CmCm−1...C1. Note if T is row and column strict then P(τ(T))=T and each column of Q(τ(T)) has consecutive entries. For w areducedword,we define τ(w) to be τ(P(w)). By the previousobservation,w andτ(w) areCoxeter-Knuth equivalent. One can think of the column reading word as closely related to the bottom-up reading word. Since insertion takes place from right to left, the column reading word is in some sense its transpose. Lemma 4.3. Let w be a reduced word and ↑ a Little bump on w. Then Q(τ(w))=Q(τ(w)↑). Proof. Let w be a reduced word, τ(w) = CmCm−1...C1 and τ(w)↑ = DmDm−1...D1 (note Dk is not a priori a column of P(τ(w)↑)). Since τ(w) and τ(w)↑ have the same descent structure, we see C1 and D1 insertidentically. Aseachentryofτ(w)↑ isdecrementedatmostonceandP(τ(w))isrowandcolumnstrict, we see dk ≤ck ≤dk+1≤dk+1, i i i i sodk+1 willnotbumpanydk withj ≤i. Therefore,anyentryofDk willstayinthekthcolumnofP(τ(w)↑) i j for all k, that is the entries of the kth column of P(τ(w)↑) are Dk. Thus τ(w)↑ is a column reading word with identical column sizes, so Q(τ(w))=Q(τ(w)↑). (cid:3) 4.3. Proof of Theorem 1.1 and its corollaries. Combining Lemma 4.3 with Lemmas 3.3 and 3.4, we can conclude the following: Theorem 4.4. Let w be a reduced word and ↑ be a Little bump on w. Then Q(w)=Q(w↑). Proof. Let w be a reduced word. There exists a sequence α ,α ,...,α of Coxeter-Knuth moves such that 1 2 k w =τ(w)α ...α . As Q(τ(w))=Q(τ(w)↑) by Lemma 4.3, we compute 1 k (2) Q(w)=Q(τ(w)α ...α )=Q((τ(w)↑)α ...α ) 1 k 1 k (3) =Q((τ(w)α ...α )↑)=Q(w↑) 1 k 8 where the third equality follows by Lemmas 3.3 and 3.4. (cid:3) Proof of Theorem 1.1. Let w be a reduced word and ↑ ,...,↑ be the sequence of canonical Little bumps. 1 k By Theorem 4.4 and Lemma 4.1, we see Q(w)=Q(w↑ ...↑ )=Tab(w↑ ...↑ )=LS(w). 1 k 1 k (cid:3) We now demonstrate severalcorollaries,including Lam’s Conjecture. The first is Conjecture 11 from [6], which first appeared as Conjecture 4.3.3 in the appendix of [2]. Corollary 4.5. Let w be a reduced word and let ↑ ,↑ ,...,↑ be any sequence of Little bumps such that 1 2 m v =w↑ ...↑ 1 m is a Grassmannian word. Then Tab(v)=LS(w). This follows from Theorem 4.4. We can extend this result further. Let λ be a partition with w a Grassmannian word of shape λ. The permutation σ associated to w can be characterized by the number of initial fixed points and terminalfixed points. A Grassmannianpermutationis minimal if it has no initial or terminal fixed points. Note the minimal Grassmannian permutation of a given shape is unique. Recall two reduced words communicate if there exists a sequence of Little bumps and inverse Little bumps changing one to the other. Proof of Theorem 1.2. Let v and w be reduced words. Suppose first that v and w communicate. Then by Theorem 4.4, we have that Q(v)=Q(w). Conversely,suppose that Q(v)=Q(w). By applying the Little map, w can be changedto the Grassman- ′ ′ ′ nian word w and v to the Grassmannian word v by a sequence of Little bumps. Since Q(w) =Q(w ) and ′ Q(v)=Q(v ), we canconclude that v andw communicate if Grassmannianpermutations ofthe sameshape communicate. To do this, we demonstrate a sequence of Little bumps that adds a fixed point at the end of an arbitrary Grassmannianpermutation, and another sequence that converts a fixed point at the beginning into one at the end. By converting any fixed points at the beginning into ones at the end, then removing thoseattheendviainversebumps,wegettheminimalGrassmannianpermutationofthatshape. Therefore, any Grassmannian permutation communicates with the minimal permutation of that shape. From this, we can conclude any two Grassmannian permutations with the same shape communicate. We now construct our sequence of Little bumps. Let σ = a1...akb1...bn−k be a Grassmannian permutation with an−kb1 its sole descent. Start a Little bump at the last swap featuring each bj, beginning b1, so that the firstbump begins between b and a . We will show this sequence of bumps decrements every entry 1 k in each trajectory exactly once. This is equivalent to decrementing each entry of w. If σ has initial fixed points,this willremoveone ofthem, leavingafixedpointatthe end. Ifσ hasno initialfixedpoint, this will leave w the same but add a fixed point to the end of σ. We now verify that our sequence works as described. First, we must verify that the swap locations at which we begin a Little bump are valid choices, that is that removing that swap from w leaves a reduced word. To see this, note that the first such swap chosen is the swap between a and b , the last swap in k 1 w. This bump will decrement every entry in the trajectory of b . After the first Little bump, the second 1 swap chosen is the last in the trajectory of b . Since the trajectories of all b with j > 2 are unaffected 2 j by the initial Little bump, this is the last swap for both b and a , so removing it leaves a reduced word. 2 k This bump will decrement every entry in the trajectory of b . Note because we have already decremented 2 the swaps in the trajectory of b and these trajectories were initially disjoint, they will remain disjoint after 1 the second Little bump. Applying this line of reasoning inductively, we see that each Little bump in the sequence is a valid Little bump which decrements every entry of eachtrajectory. We have now shown v and w communicate if Q(v)=Q(w). (cid:3) Additionally, we show how to embed Robinson-Schensted insertion and RSK in the Little map. In doing so, we recover the main results of [6] in a much simplified form. This embedding was first predicted as Conjecture 4.3.1 in the appendix of [2]. For w a word, let w~ be the reverse of w. 9 Theorem 4.6. Let σ = σ ...σ ∈ S , so that w(σ) = (2σ − 1)...(2σ − 1) is a reduced word, and 1 n n n 1 let RS(σ) = (P′(σ),Q′(σ)) be the output of Robinson-Schensted insertion applied to σ. Upon applying the transformation k 7→k−1/2 to the entries of LS(w), we obtain Q′(σ). We can obtain P′(σ) by applying the same transformation to LS(w(σ−1). Proof. Since LS(w) = Q(w) and there are no special bumps, Edelman-Greene insertion will perform the same insertion process on w as Robinson-Schensted insertion performs on σ. Therefore, upon applying the transformation k 7→ k−1/2, we see LS(w(σ)) = Q(w(σ)) = Q′(σ). Since RS(σ−1) = (Q′(σ),P′(σ)) (see e.g. [8]), we can obtain P′(σ) by applying the same transformation to LS(w(σ−1)). (cid:3) WecanembedRSKinRobinson-Schenstedinsertion(seeSection7of[6]foradescriptionofthisprocess), so Theorem 4.6 recovers an embedding of RSK into the Little map as well. References [1] P.EdelmanandC.Greene. Balancedtableaux. Advances inMathematics,63(1):42–99, 1987. [2] AdrianoGarsia.TheSagaofReduced Factorizations ofElementsof theSymmetricGroup.Labaratoiredecombanatoireet d’informatiquemathématique, 2002. [3] T.Lam.Stanleysymmetricfunctionsandpetersonalgebras.Arxiv preprint arXiv:1007.2871, 2010. [4] A. Lascoux and M.P. Schu¨tzenberger. Schubert polynomials and the littlewood-richardson rule. letters in mathematical physics,10(2):111–124, 1985. [5] D.P.Little.Combinatorialaspects ofthelascoux-schu¨tzenberger tree.Advances inMathematics,174(2):236–253, 2003. [6] D.P. Little. Factorization of the robinson–schensted–knuth correspondence. Journal of Combinatorial Theory, Series A, 110(1):147–168, 2005. [7] R.P.Stanley.Onthenumberofreduceddecompositions ofelements ofcoxeter groups.Eur. J. Comb.,5:359–372, 1984. [8] R.P.Stanley.Enumerative combinatorics, volume2.CambridgeUnivPr,2001. 10

Relating Edelman-Greene insertion to the Little map

Similar Relating Edelman-Greene insertion to the Little map