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 n<r1, let j be the smallest number such that n<r1. (a) If rl11 =n+1 and r1 =n, insert n+1 into T′ =Rj ,...,R and leave R unchanged. j j−1 2 k 1 (b) Otherwise, replace r1 with n and insert it into T′ =R ,...,R . j 2 k Aside from 2(a), this is the RSK insertion rule. For w = w ...w a word (not necessarily reduced), we 1 m define EG(w) = (P(w),Q(w)) via the following sequence of tableaux (see Figure 1 for an example). We obtain P1(w) by inserting am into the empty tableau. Then Pj(w) is obtained by inserting am−j+1 into Pj−1(w). Note we are inserting the entries of w from right to left. At each step, one additional box is added. In Q(w), the entry of each box records the time of the step in which it was added. From this, we canconcludethatQ(w) is a standardYoung tableau. Note the fourthinsertioninFigure 1follows2(a). For w is a reduced word of some σ, it is shown that the entries of P(w) are strictly increasing across rows and down columns in [1]. Additionally, we can recover σ from P(w) with no additional information. 2.2. Grassmannian permutations. Recallapermutationσ isGrassmannianifithasexactlyonedescent. We can then write σ =a1a2...akb1b2...bn−k where {ai}ki=1 and {bj}jn=−1k are increasing sequences with an−k >b1. 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 <w , we see v <v . (cid:3) i i+1 i i+1 i i+1 Let w be a reduced word of σ ∈S . We define the Little map LS(w). n (1) If w is a Grassmannian word, then LS(w)=Tab(w) (2) Ifw isnotaGrassmannianword,identifytheswaplocationiofthelastinversion(lexicographically) in σ and output LS(w↑ ). i It is a corollary of work in [4] and [5] that LS terminates. We then see that w 7→ LS(w) where LS(w) is a standardYoungtableau. Anexample canbe seeninFigure2,where the wordw is representedby its wiring diagram: an arrangement of horizontal, parallel wires spaced one unit apart, labelled 1 through n on the left-hand side, in which the letter in the word w are represented by crossings of wires. 3. The action of Coxeter-Knuth moves 3.1. Basics of Coxeter-Knuth moves. First introduced in [1], Coxeter-Knuth moves are perhaps the mostimportanttoolforstudyingEdelman-Greeneinsertion. Theyaremodificationsofthe secondandthird Coxeter relations. Let a<b<c and x be integers. The three Coxeter-Knuth moves are the modifications (1) acb↔cab (2) bac↔bca (3) x(x+1)x↔(x+1)x(x+1) applied to three consecutive entries of a reduced word. Let ww w ...w be a reduced word of σ and α 1 2 m i denote a Coxeter-Knuth move on the entries wi−1wiwi+1. Since a < b < c, if αi is of type one or two we have wα a reduced word of σ as well by the second Coxeter relation. If α is of type three then wα is a i i i reduced word of σ by the third Coxeter relation. We say two reduced words v and w are Coxeter-Knuth equivalent if there exists a sequence α ,α ,...,α of Coxeter-Knuth moves such that i1 i2 ik v =wα ...α . i1 ik Note that two Coxeter-Knuth equivalent reduced words must be correspond to reduced decompositions of the same permutation. We can see their action on wiring diagrams in Figure 3. 4 Figure 3. The three types of Coxeter-Knuth moves acting on wiring diagrams. (a) Type 1 (b) Type 2 (c) Type 3 Coxeter-Knuth moves play a role in the study of Edelman-Greene insertion analogous to that of Knuth moves in the study of RSK insertion. Theorem 3.1 (Theorem 6.24 in [1]). Let v and w be a reduced words. Then P(v)= P(w) if and only if v and w are Coxeter-Knuth equivalent. 3.2. Theaction ofCoxeter-Knuth moves onQ(w). InordertounderstandtherelationshipsofCoxeter- Knuth moves andLittle bumps, we must firstunderstand in greater detail how Coxeter-Knuthmoves relate to Edelman-Greeneinsertion. From Theorem3.1, we understandhow Coxeter-Knuthmovesrelate to P(w). We must also understand their actionon Q(w). For T a standardYoung tableauwith n entries, let Tt be i,j the Young tableau obtained by swapping the entries labeled n−i and n−j. Lemma 3.2. Let w =w1...wm be a reduced word and α be a Coxeter-Knuth move on wi−1wiwi+1. If α is a Coxeter-Knuth move of type one or three, then Q(wα)=Q(w)ti−1,i. If α is a Coxeter-Knuth move of type two, then α acts on Q(w) as above or i Q(wα)=Q(w)t . i,i+1 Proof. For w =w1...wm a reduced word we see w|i−1 =wi−1wi...wm is also a reduced word. Let αi be a Coxeter-Knuth move on wi−1wiwi+1. Then P(w|i−1)=P(w|i−1αi)=P(wαi |i−1) since they differ by a Coxeter-Knuth move. Since w1...wi−2 remain unmodified, they insert the same in both cases. Additionally, we see P(w | )=P(wα | ), so all changes in Q(w) must occur at the entries i+2 i i+2 labeled i−1,iand i+1. The remainder ofthis argumentis adaptedfromthe prooffor Theorem6.24in [1]. (1) Let α be a Coxeter-Knuthmove of type one. Then w inserts into the same spot in P(w | ) for i+1 i+2 both w and wαi. Since Q(w)6=Q(wαi), we see Q(wαi)=Q(w)ti−1,i. (2) Let α be a Coxeter-Knuth move of type three. This case is treated first as the case with moves of type two relies on it. We compare the insertion of x(x+1)x and (x+1)x(x+1) into the same row of P(w| ). Assume both x and x+1 bump an entry of the row. Let p denote the entry bumped i+2 by x, ǫ be the entry preceding p and ǫ be the entry following p. If p >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ǫ <x. Uponinsertingx(x+1)x 2 1 intotherow,weseethefirstxbumpsx+1,x+1bumpsx+2andthesecondxbumpsthex+1just inserted, so that (x+1)(x+2)(x+1) is inserted into the next row. Upon inserting (x+1)x(x+1) into the row, we see the first x+1 produces a special bump of x+2, the x bumps x+1 and the second x+1 bumps the x+2 remaining after the special bump, so that (x+2)(x+1)(x+2) is insertedintothenextrow. Thecasewhereǫ =xislefttothereader,andhasanidenticaloutcome. 1 If one of the three inserted letters does not bump an entry of the row, we see the largest entry k of the row must be less than x+1. As P(wα| ) is row and column strict, we see k < x, so x or i+1 x+1 would both insert at the end of the row. Thus Q(wα)=Q(w)ti−1,i. (3) LetαbeaCoxeter-Knuthmoveoftypetwo. Wecomparetheinsertionofwi−1wiwi+1andwi−1wiwi+1 into P(w|i+2) with wi < wi+1. In the first case, let wi+1 bump p, wi bump q and wi−1 bump r. ′ ′ ′ In the latter, let wi bump p, wi+1 bump q and wi−1 bump r , so that we compare the insertion ′ ′ ′ ′ of pqr and pq r into the next row. If p = p, we see Q(wα) = Q(w)ti−1,i as the first entry is ′ ′ ′ ′ inserted into the same spot. Assume p < p. The reader can verify that pqr and pq r differ by a 5 Figure 4. Transitional bumps for type one and two Coxeter-Knuthmoves. ↑ ↑ α α ↑ ↑ ′ ′ ′ Coxeter-Knuth move of type two unless p = q+1, so that c = p. In this case, pqr and pq r differ by a Coxeter-Knuth move of type three. If some letter does not bump an entry of the row, there are two possibilities. Let k be the largest entry of the row. If k < w , then w and w are inserted into the same position, so i i i+1 Q(wα) = Q(w)ti−1,i. If wi < k < wi+1, then wi+1 inserts on the end of the row and wi bumps the same entry of the row regardless of the order of insertion, so P(w| ) = P(wα| ). Therefore, i i Q(wα)=Q(w)t . i,i+1 (cid:3) 3.3. Coxeter-Knuth moves and Little bumps. We now set out to show that Coxeter-Knuth moves commute with Little bumps. This requires two results. The first is that the order we perform a Coxeter- Knuth move α and a Little bump ↑ does not affect the resulting reduced word. Lemma 3.3. Let w =w1...wm be a reduced word, α a Coxeter-Knuth move on wi−1wiwi+1, and ↑j,k be a Little bump begun at the swap between the j and kth trajectories. Then (wα)↑ =(w↑ )α. j,k j,k Proof. Letv =w↑ andv′ =(wα)↑ . RecallfromLemma 2.1andCorollary2.2thatw −v ∈{0,1}and j,k j,k j j v has the same descent structure of w. (1) Let α be a Coxeter-Knuthmove of the first type, i.e. wi−1wiwi+1 7→wiwi−1wi+1 with wi+1 strictly between wi−1 and wi. Since a Little bump decrements an entry of w by at most one, one can check that if wi+1 differs from wi or wi−1 by more than one, there is a Coxeter-Knuth move of type one on vi−1vivi+1. In the event that they differ by exactly one and the smallest entry is decremented, we see in Figure 4 that after the bump they differ by a Coxeter-Knuthmove of the third type. (2) Let α be a Coxeter-Knuth move of the second type, i.e. wi−1wiwi+1 7→ wi−1wi+1wi with wi−1 strictlybetweenw andw . SinceaLittlebumpdecrementsanentryofw byatmostone,onecan i+1 i check that if wi−1 differs from wi or wi+1 by more than one, there is a Coxeter-Knuthmove of type two on vi−1vivi+1. In the event that they differ by exactly one and the smallest entry is bumped, we see in Figure 5 that after the bump they differ by a Coxeter-Knuthmove of the third type. (3) Let α be a Coxeter-Knuth move of the third type. Note the middle entry cannot be bumped unless allthreeentriesarebumped. Intheeventfewerentries(butnotzero)arebumped,weseeinFigure5 that there will be a Coxeter-Knuth move of the first or second type remaining. WenextshowthattherestoftheLittlebumpproceedsinthesamemanneroncethecrossingsinvolvedin the Coxeter-Knuth move have been bumped. To see this, we need only observe that the last bumped swap is between the same two trajectories. This can be verified readily by examining Figures 4 and 5. The preceding argument assumes that the bumping path does not return to the crossings involvedin the Coxeter-Knuth move. It is possible that the bumping path passes through the crossings involved in the Coxeter-Knuth path twice (but no more than that, by Lemma 2.1). However, the same argument applies, 6 Figure 5. Transitional bumps for type three Coxeter-Knuth moves ↑ ↑ α α ↑ ↑ showing that all three crossings are bumped regardless of whether the Coxeter-Knuth move is performed before or after the bump. (cid:3) We now showthat the actionofa Coxeter-Knuthmove onQ(w) remainsthe same after applying a Little bump. Combined with Lemma 3.3, this shows that the order in which Coxeter-Knuth moves and Little bumps areperformedona reducedwordw does not effect either the resulting reducedwordor the resulting recording tableau. Lemma 3.4. Letw be a reduced word, α be a Coxeter-Knuth move and ↑ a Little bump. Then Q(wα) = Q(w)t if and only if Q(w ↑α)=Q(w ↑)t . i,i+1 i,i+1 Proof. By Lemma 3.2, we see α must exchange wi−1wiwi+1 or wiwi+1wi+2. We show the result in the case where α is a Coxeter-Knuth move on wi−1wiwi+1, so that α is a Coxeter-Knuth move of type two. The other outcome then follows. ′ ′ ′ Let w = wα. Then w| = w w w ...w and w | = w w w ...w are the parts of w and w i i i+1 i+2 n i i+1 i i+2 n ′ ′ respectivelytotherightofwi−1. ApplyingEdelman-Greeneinsertiontow|iandw |i,weseeP(w|i)=P(w |i) ′ and Q(w| )=Q(w | )t . Therefore, there exists a sequence of Coxeter-Knuth moves α ...α such that i i i,i+1 1 m ′ w| =w | α ...α . We then see i i 1 m ′ ′ Q(w ↑| )=Q((w α ...α )↑| )=Q((w ↑)α ...α | ) i 1 m i 1 m i ′ by Lemma 3.3. Therefore w ↑ | and w ↑ | differ solely at their first two positions and are Coxeter-Knuth i i ′ ′ equivalent, so we seeQ(w ↑ | ) and Q(w ↑ | ) have the same shape with Q(w ↑ | ) = Q(w ↑ | )t . Thus i i i i i,i+1 ′ ′ Q(w ↑) and Q(w ↑) vary in the same way as Q(w) and Q(w ). Since the inverse of a Little bump is a Little bump of the upside down word, where all Coxeter-Knuth move types are preserved, the converse holds as well. Therefore Q(wα) = Q(w)t if and only if Q(w ↑ i,i+1 α)=Q(w ↑)t . i,i+1 (cid:3) 4. Proof of Results 4.1. The Grassmannian case. Before proving Theorem 1.1, we need to establish the base case where w is a Grassmannian word. In order to do so, we must understand which entries are exchanging places with each swap. For w = w ...w a reduced word, we define σ = s s ...s where σ is the identity 1 m i w1 w2 wi 0 permutation. The kth trajectory of w is the sequence {σ (k)}m . For w a Grassmannian word of σ = i i=0 a1a2...akb1b2...bn−k,observethatthejthcolumnofTab(w)liststhetimesforallswapsfeaturingbj. Since allsuchswapsincreasethevalueofb ,wecanreconstructitstrajectoryfromthenumberandlocationofthese j swaps. Similarly,wecanreconstructthetrajectoryofeacha fromthek+1−ithrowofTab(w). Wewillfind i it convenient to identify the kth trajectory of a Grassmannian word with the indices {i ,i ,...,i } ⊂ [n] 1 2 tk of the swaps featuring k. Since insertion takes place from right to left, we label the entries such that i >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 permu- tation 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´ematique, 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