# Relating Edelman-Greene insertion to the Little map

Zachary Hamaker<fnref n="1" /> and Benjamin Young<fnref n="2" />

**Abstract.** The Little map and the Edelman-Greene insertion algorithm, a generalization of the Robinson-Schensted correspondence, are both used for enumerating the reduced decompositions of an element of the symmetric group. We show the Little map factors through Edelman-Greene insertion and establish new results about each map as a consequence. In particular, we resolve some conjectures of Lam and Little.

**Résumé.** La correspondance de Little et l’algorithme d’Edelman-Greene généralisant la correspondance de Robinson-Schensted sont utilisés pour l’énumération des décompositions réduites associées aux éléments du groupe symétrique. Nous démontrons que la correspondance de Little peut être réduite à celle d’Edelman-Greene. En particulier, nous obtenons de nouvelle réponses à quelques conjectures de Lam et Little.

**Keywords:** Young tableaux; reduced decompositions in the symmetric group; Edelman-Greene insertion; Lascoux-Schützenberger tree; Knuth moves; Stanley symmetric functions

# 1 Introduction

## 1.1 Preliminaries

In this paper, we clarify the relationship between two algorithmic bijections, due respectively to Edelman and Greene (1987) and to Little (2003), both of which deal with reduced decompositions in the symmetric group, $S_n$. It is well known that $S_n$ can be viewed as a Coxeter group with the presentation

$$S_n = \langle s_1, s_2, \dots, s_{n-1} \mid s_i^2 = 1, s_i s_j = s_j s_i \text{ for } |i-j| \ge 2, s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1} \rangle$$

where $w_i$ can be viewed as the transposition $(i \ i+1)$. Let $\sigma = \sigma_1\sigma_2\dots\sigma_n \in S_n$. A reduced decomposition or reduced expression of $\sigma$ is a minimal-length sequence $s_{w_1}, s_{w_2}, \dots, s_{w_m}$ such that $\sigma = s_{w_1}s_{w_2}\dots s_{w_m}$. The word $w = w_1w_2\dots w_m$ is called a reduced word of $\sigma$. It is convenient to refer to a reduced decomposition by its corresponding reduced word and we will conflate the two often. The set of all reduced decompositions of $\sigma$ is denoted Red($\sigma$). An inversion in $\sigma$ is a pair $(i, j)$ with $i < j$ and $\sigma_i > \sigma_j$. Let $l(\sigma)$ be the number of inversions in $\sigma$. Since each transposition $s_i$ either introduces or removes an inversion, for $w = w_1\dots w_m$ a reduced word of $\sigma$, we see $m = l(\sigma)$.

<footnote n="1">¹Department of Mathematics, Dartmouth College, Hanover NH 03755, USA</footnote>

<footnote n="2">²Department of Mathematics, 1222 University of Oregon, Eugene OR 97403-1205, USA</footnote>
The enumerative theory of reduced decompositions was first studied in Stanley (1984), where using algebraic techniques it is shown for the reverse permutation $\sigma = n...21$ that

$$|\mathrm{Red}(\sigma)| = \frac{\binom{n}{2}!}{(2n-3)(2n-5)^2 \dots 5^{n-2}3^{n-2}} \quad (1)$$

This is the same as the number of standard Young tableaux with the staircase shape $\lambda = (n-1, n-2, \dots, 1)$. In addition, Stanley conjectured for arbitrary $\sigma \in S_n$ that $|\mathrm{Red}(\sigma)|$ can be expressed as the number of standard Young tableaux of various shapes (possibly with multiplicity). This conjecture was resolved in Edelman and Greene (1987) using a generalization of the Robinson-Schensted insertion algorithm, usually called *Edelman-Greene insertion*. Edelman-Greene insertion maps a reduced word $w$ to the pair of Young tableaux $(P(w), Q(w))$ where the entries of $P(w)$ are row-and-column strict and $Q(w)$ is a standard Young tableau. The same map also provides a bijective proof of (1), as there is only one possibility for $P(w)$.

Algebraic techniques developed in Lascoux and Schützenberger (1985) can be used to compute the exact multiplicity of each shape for given $\sigma$. A bijective realization of Lascoux and Schützenberger's techniques in this setting is demonstrated in Little (2003). Permutations with precisely one descent are referred to as *Grassmannian*. There is a simple bijection between reduced words of a Grassmannian permutation $\sigma$ and standard Young tableaux of a shape determined by $\sigma$. The Little map works by applying a sequence of modifications referred to 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

Since the Little map's introduction, there has been speculation on its relationship to Edelman-Greene insertion. In the appendix of Garsia (2002), written by Little, Conjecture 4.3.2 asserts that $LS(w) = Q(w)$ when the maps are restricted to reduced words which realize the reverse permutation. Similar comments are made in Little (2003). We show the connection is much stronger than previously suspected: this equality is true for every permutation.

**Theorem 1.1** Let $w$ be a reduced word. Then

$$Q(w) = \mathrm{LS}(w).$$

The proof is based on an argument from canonical form. We define the *column word*, a 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, Conjecture 2.5 of Lam (2010) proposes that Little bumps relate to Edelman-Greene insertion in a way that is analogous 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 Edelman and Greene (1987); Little (2003) which we need: we define Edelman-Greene insertion and the Little map, as well as generalized Little bumps. Additionally, we state some properties of these maps that are important to our work. The third section defines Coxeter-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. Due to space considerations, several proofs have been omitted. The curious reader may find these details in Hamaker and Young (2012).

# 2 Two Maps

## 2.1 Edelman-Greene insertion

In order to define Edelman-Greene insertion, we must first define a rule for inserting a number into a tableau. Let $n \in \mathbb{N}$ and $T$ be a tableau with rows $R_1, R_2, \dots, R_k$ where $R_i = r_1^i \le r_2^i \le \dots \le r_{l_i}^i$. We define the insertion rule for Edelman-Greene insertion, following Edelman and Greene (1987).

1. If $n \ge r_{l_1}^1$ or if $R_i$ is empty, adjoin $k$ to the end of $R_i$.

2. If $n < r_{l_1}^1$, let $j$ be the smallest number such that $n < r_j^1$.

(a) If $r_j^1 = n+1$ and $r_{j-1}^1 = n$, insert $n+1$ into $T' = R_2, \dots, R_k$ and leave $R_1$ unchanged.

(b) Otherwise, replace $r_j^1$ with $n$ and insert it into $T' = R_2, \dots, R_k$.

Aside from 2(a), this is the RSK insertion rule. For $w = w_1 \dots w_m$ a word (not necessarily reduced), we define $EG(w) = (P(w), Q(w))$ via the following sequence of tableaux (see Figure 1 for an example). We obtain $P_1(w)$ by inserting $w_m$ into the empty tableau. Then $P_j(w)$ is obtained by inserting $w_{m-j+1}$ into $P_{j-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 can conclude that $Q(w)$ is a standard Young tableau. Note the fourth insertion in Figure 1 follows 2(a). For $w$ is a reduced word of some $\sigma$, it is shown that the entries of $P(w)$ are strictly increasing across rows and down columns in Edelman and Greene (1987). Additionally, we can recover $\sigma$ from $P(w)$ with no additional information.

## 2.2 Grassmannian permutations

Recall a permutation $\sigma$ is Grassmannian if it has exactly one descent. We can then write

$$ \sigma = a_1 a_2 \dots a_k b_1 b_2 \dots b_{n-k} $$

where $\{a_i\}_{i=1}^k$ and $\{b_j\}_{j=1}^{n-k}$ are increasing sequences with $a_k > b_1$. A word $w$ is *Grassmannian* if it is the reduced word of a Grassmannian permutation. From the Grassmannian word $w = w_1 \dots w_m$ we construct a tableau $\text{Tab}(w)$ as follows. Index the columns of $\text{Tab}(w)$ by $b_1, \dots, b_{n-k}$ and the rows by $a_k, a_{k-1}, \dots, a_1$. Since all inversions in $\sigma$ feature an $a_i$ and a $b_j$, each $w_l$ in $w$ represents the swap between an $a_i$ and a $b_j$. For $w_l$, we enter $m+1-l$ in the column indexed by $a_i$ and $b_j$. If $a_i$ swaps with $b_j$, we see it must later swap with each smaller $b$. This shows entries are increasing across rows.
<figure><img src="image_1.png" /><figcaption>Fig. 1: Edelman-Greene insertion for $w = 4, 2, 1, 2, 3, 2, 4$</figcaption></figure>

Likewise, if $b_j$ swaps with $a_i$, it must later swap with each larger $a$ so entries increase down columns. From this, we can conclude that $\mathrm{Tab}(w)$ is a standard Young tableau whose shape is determined by $\sigma$. For a given Grassmannian permutation $\sigma$, this map is a bijection as the process is easily reversed. Multiple Grassmannian permutations may correspond 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 now describe the method in Little (2003) for transforming an arbitrary reduced word into the reduced word of a Grassmannian permutation. Let $w = w_1 \dots w_m$ be a reduced word and $w^{(i)} = w_1 \dots w_{i-1} w_{i+1} \dots w_m$. We construct

$$w^{(i-)} = \begin{cases} w_1 \dots w_{i-1} (w_i - 1) w_{i+1} \dots w_m & \text{if } w_i > 1 \\ (w_1 + 1) \dots (w_{i-1} + 1) w_i (w_{i+1} + 1) \dots (w_m + 1) & \text{if } w_i = 1 \end{cases}$$

by decrementing $w_i$ by one or incrementing each other entry if $w_i = 1$.

Let $w$ be a reduced word so that $w^{(i)}$ is also reduced. Note $w^{(i-)}$ may not be reduced, as $w_i - 1$ may swap the same values as some $w_j$ with $j \neq i$. However, this is the only way $w^{(i-)}$ can fail to be reduced as $w^{(i)}$ is reduced and we have added one additional swap. Removing $w_j$ from $w^{(i-)}$, we obtain a new reduced 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 word $v = v_1 \dots v_m$. We refer to this process as a *Little bump* beginning at position $i$ and say $v = w^{\uparrow}_i$, where $i$ is the initial index the bump was started at. To see that this process terminates, we refer to the following lemma.

**Lemma 2.1 (Lemma 5, Little (2003))** Let $w$ be a reduced word such that $w^{(i)}$ is reduced. Let $i_1, i_2, \dots$ be the sequence of indices decremented in $w^{\uparrow}_i$. Then the entries of $i_1, i_2, \dots$ are unique.

Since $w$ is finite, we see the process terminates so that $w^{\uparrow}_i$ is well-defined. We highlight a property of Little bumps observed in Little (2003), that they preserve the descent structure of $w$.

**Corollary 2.2** Let $w = w_1 \dots w_m$ and $v = v_1 \dots v_m$ be a reduced words and $\uparrow$ be a Little bump such that $v = w^{\uparrow}$. Then $v_i > v_{i+1}$ if and only if $w_i > w_{i+1}$ for all $i$.
<figure><img src="image_2.png" /><figcaption>**Fig. 2:** The Little map for the reduced decomposition $w_4w_2w_1w_2w_3w_2w_4$ of $\sigma = 35241$. The dashed crosses show the modifications made by the next Little bump.</figcaption></figure>

**Proof:** Let $w_i > w_{i+1}$. As each $w_i$ is decremented at most once, we see $v_i \ge v_{i+1}$, but $v_i \ne v_{i+1}$. Thus $v_i > v_{i+1}$. By the same reasoning, if $w_i < w_{i+1}$, we see $v_i < v_{i+1}$. $\square$

Let $w$ be a reduced word of $\sigma \in S_n$. We define the Little map $\text{LS}(w)$.

1. If $w$ is a Grassmannian word, then $\text{LS}(w) = \text{Tab}(w)$

2. If $w$ is not a Grassmannian word, identify the swap location $i$ of the last inversion (lexicographically) in $\sigma$ and output $\text{LS}(w\upharpoonright_i)$.

It is a corollary of work in Lascoux and Schützenberger (1985) and Little (2003) that LS terminates. We then see that $w \mapsto \text{LS}(w)$ where $\text{LS}(w)$ is a standard Young tableau. An example can be seen in Figure 2, where the word $w$ is represented by 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.
<figure><img src="image_3.png" /><figcaption>Fig. 3: The three types of Coxeter-Knuth moves acting on wiring diagrams.</figcaption></figure>

# 3 The action of Coxeter-Knuth moves

## 3.1 Basics of Coxeter-Knuth moves

First introduced in Edelman and Greene (1987), Coxeter-Knuth moves are perhaps the most important tool for studying Edelman-Greene insertion. They are modifications of the second and third Coxeter relations. Let $a < b < c$ and $x$ be integers. The three Coxeter-Knuth moves are the modifications

$$1. \ acb \leftrightarrow cab$$

$$2. \ bac \leftrightarrow bca$$

$$3. \ x(x+1)x \leftrightarrow (x+1)x(x+1)$$

applied to three consecutive entries of a reduced word. Let $w = w_1w_2...w_m$ be a reduced word of $\sigma$ and $\alpha_i$ denote a Coxeter-Knuth move on the entries $w_{i-1}w_iw_{i+1}$. Since $a < b < c$, if $\alpha_i$ is of type one or two we have $w\alpha_i$ a reduced word of $\sigma$ as well by the second Coxeter relation. If $\alpha_i$ is of type three then $w\alpha_i$ is a reduced word of $\sigma$ by the third Coxeter relation. We say two reduced words $v$ and $w$ are *Coxeter-Knuth equivalent* if there exists a sequence $\alpha_{i_1}, \alpha_{i_2}, ..., \alpha_{i_k}$ of Coxeter-Knuth moves such that

$$v = w\alpha_{i_1}...\alpha_{i_k}.$$

Note that two Coxeter-Knuth equivalent reduced words must correspond to reduced decompositions of the same permutation. We can see their action on wiring diagrams in Figure 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 Edelman and Greene (1987))** 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 The action of Coxeter-Knuth moves on $Q(w)$

In order to understand the relationships of Coxeter-Knuth moves and Little bumps, we must first understand in greater detail how Coxeter-Knuth moves relate to Edelman-Greene insertion. From Theorem 3.1, we understand how Coxeter-Knuth moves relate to $P(w)$. We must also understand their action on $Q(w)$. For $T$ a standard Young tableau with $n$ entries, let $Tt_{i,j}$ be the Young tableau obtained by swapping the entries labeled $n-i$ and $n-j$.
**Lemma 3.2** Let $w = w_1...w_m$ be a reduced word and $\alpha$ be a Coxeter-Knuth move on $w_{i-1}w_iw_{i+1}$. If $\alpha$ is a Coxeter-Knuth move of type one or three, then

$$Q(w\alpha) = Q(w)t_{i-1,i}.$$

If $\alpha$ is a Coxeter-Knuth move of type two, then $\alpha_i$ acts on $Q(w)$ as above or

$$Q(w\alpha) = Q(w)t_{i,i+1}.$$

The proof of Lemma 3.2 is based on and can be recovered with little additional effort from the argument presented for Theorem 6.24 in Edelman and Greene (1987). We omit the proof for space considerations.

## 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 $\alpha$ and a Little bump $\uparrow$ does not affect the resulting reduced word.

**Lemma 3.3** Let $w = w_1...w_m$ be a reduced word, $\alpha$ a Coxeter-Knuth move on $w_{i-1}w_iw_{i+1}$, and $\uparrow_{j,k}$ be a Little bump begun at the swap between the j and kth trajectories. Then

$$(w\alpha)\uparrow_{j,k} = (w\uparrow_{j,k})\alpha.$$

**Proof:** Let $v = w\uparrow_{j,k}$ and $v' = (w\alpha)\uparrow_{j,k}$. Recall from Lemma 2.1 and Corollary 2.2 that $w_j - v_j \in \{0, 1\}$ and $v$ has the same descent structure of $w$.

1. Let $\alpha$ be a Coxeter-Knuth move of the first type, i.e. $w_{i-1}w_iw_{i+1} \mapsto w_iw_{i-1}w_{i+1}$ with $w_{i+1}$ strictly between $w_{i-1}$ and $w_i$. Since a Little bump decrements an entry of $w$ by at most one, one can check that if $w_{i+1}$ differs from $w_i$ or $w_{i-1}$ by more than one, there is a Coxeter-Knuth move of type one on $v_{i-1}v_iv_{i+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-Knuth move of the third type.

2. Let $\alpha$ be a Coxeter-Knuth move of the second type, i.e. $w_{i-1}w_iw_{i+1} \mapsto w_{i-1}w_{i+1}w_i$ with $w_{i+1}$ strictly between $w_{i+1}$ and $w_i$. Since a Little bump decrements an entry of $w$ by at most one, one can check that if $w_{i+1}$ differs from $w_i$ or $w_{i+1}$ by more than one, there is a Coxeter-Knuth move of type two on $v_{i-1}v_iv_{i+1}$. In the event that they differ by exactly one and the smallest entry is bumped, we see in Figure 4 that after the bump they differ by a Coxeter-Knuth move of the third type.

3. Let $\alpha$ be a Coxeter-Knuth move of the third type. Note the middle entry cannot be bumped unless all three entries are bumped. In the event fewer entries (but not zero) are bumped, we see in Figure 4 that there will be a Coxeter-Knuth move of the first or second type remaining.

We next show that the rest of the Little bump proceeds in the same manner once the crossings involved in 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.
<figure><img src="image_4.png" /><figcaption>Fig. 4: Transitional bumps for Coxeter-Knuth moves of all three types.</figcaption></figure>

The preceding argument assumes that the bumping path does not return to the crossings involved in 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, showing that all three crossings are bumped regardless of whether the Coxeter-Knuth move is performed before or after the bump.

□

We now show that the action of a Coxeter-Knuth move on $Q(w)$ remains the same after applying a Little bump. Combined with Lemma 3.3, this shows that the order in which Coxeter-Knuth moves and Little bumps are performed on a reduced word $w$ does not effect either the resulting reduced word or the resulting recording tableau.

**Lemma 3.4** Let $w$ be a reduced word, $\alpha$ be a Coxeter-Knuth move and $\uparrow$ a Little bump. Then $Q(w\alpha) = Q(w)t_{i,i+1}$ if and only if $Q(w\uparrow\alpha) = Q(w\uparrow)t_{i,i+1}$.

The proof of Lemma 3.4 reduces to a simple observation. The only problematic case is when $\alpha$ is a Coxeter-Knuth move on $w_{i-1}w_iw_{i+1}$ of type two that acts on $Q(w)$ as $t_{i,i+1}$. Here, the truncated word
$w|_i = w_i w_{i+1} w_{i+2} \dots w_n$ and $w\alpha|_i = w_{i+1} w_i w_{i+2} \dots w_n$ have the same insertion tableau. Therefore, they are related by Coxeter-Knuth moves, and the action of this sequence of moves can be shown to be preserved by Little bumps. We omit the details of this argument.

# 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_1 \dots w_m$ a reduced word, we define $\sigma_i = s_{w_1} s_{w_2} \dots s_{w_i}$ where $\sigma_0$ is the identity permutation. The $k$th trajectory of $w$ is the sequence $\{\sigma_i(k)\}_{i=0}^m$. For $w$ a Grassmannian word of $\sigma = a_1 a_2 \dots a_k b_1 b_2 \dots b_{n-k}$, observe that the $j$th column of $\mathrm{Tab}(w)$ lists the times for all swaps featuring $b_j$. Since all such swaps increase the value of $b_j$, we can reconstruct its trajectory from the number and location of these swaps. Similarly, we can reconstruct the trajectory of each $a_i$ from the $k+1-i$th row of $\mathrm{Tab}(w)$. We will find it convenient to identify the $k$th trajectory of a Grassmannian word with the indices $\{i_1, i_2, \dots, i_{t_k}\} \subset [n]$ of the swaps featuring $k$. Since insertion takes place from right to left, we label the entries such that $i_1 > i_2 > \dots > i_{t_k}$.

**Lemma 4.1** Let $w = w_1 \dots w_m$ be a reduced decomposition of a Grassmannian permutation $\sigma$. Then $\mathrm{Tab}(w) = Q(w)$.

The proof of Lemma 4.1 follows by showing that for $\sigma = a_1 a_2 \dots a_{n-k} b_1 b_2 \dots b_k$ a Grassmannian permutation with sole descent $a_{n-k} b_1$, the trajectory of each $b_j$ will insert into the $j$th column. This is shown inductively, as the trajectory of each $b_i$ will block off the trajectory of $b_{i+1}$. The entries of $b_{i+1}$ must then be inserted further to the right of entries in $b_i$. A trajectory unobstructed will insert into a single column, so we can conclude each trajectory will insert one at a time into its own column. We omit the details of this argument.

## 4.2 The column reading word

The only ingredient missing from our argument is a canonical form that is invariant under Little bumps.

**Definition 4.2** For $T$ a Young tableau with columns $C^1, C^2, \dots, C^m$ where $C^i = c_1^i, c_2^i, \dots, c_k^i$ with $c_j^i$ being the $(j, i)$th entry of $T$. We define the column reading word of $T$ to be the word

$$ \tau(T) = C^m C^{m-1} \dots C^1. $$

If $T$ is row and column strict then $P(\tau(T)) = T$ and each column of $Q(\tau(T))$ has consecutive entries. For $w$ a reduced word, we define $\tau(w)$ to be $\tau(P(w))$. By the previous observation, $w$ and $\tau(w)$ are Coxeter-Knuth equivalent.

For example, the tableau in Figure 2 has columns 1245, 36 and 7, so its column word is 7361245. 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 $\uparrow$ a Little bump on $w$. Then

$$ Q(\tau(w)) = Q(\tau(w)\uparrow). $$
**Proof:** Let $w$ be a reduced word, $\tau(w) = C^m C^{m-1} \dots C^1$ and $\tau(w)\uparrow = D^m D^{m-1} \dots D^1$ (note $D^k$ is not a priori a column of $P(\tau(w)\uparrow)$). Since $\tau(w)$ and $\tau(w)\uparrow$ have the same descent structure, we see $C^1$ and $D^1$ insert identically. As each entry of $\tau(w)\uparrow$ is decremented at most once and $P(\tau(w))$ is row and column strict, we see

$$d_i^k \le c_i^k \le d_i^k + 1 \le d_i^{k+1},$$

so $d_i^{k+1}$ will not bump any $d_j^k$ with $j \le i$. Therefore, any entry of $D^k$ will stay in the $k$th column of $P(\tau(w)\uparrow)$ for all $k$, that is the entries of the $k$th column of $P(\tau(w)\uparrow)$ are $D^k$. Thus $\tau(w)\uparrow$ is a column reading word with identical column sizes, so $Q(\tau(w)) = Q(\tau(w)\uparrow)$.

□

## 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 $\uparrow$ be a Little bump on $w$. Then

$$Q(w) = Q(w\uparrow).$$

**Proof:** Let $w$ be a reduced word. There exists a sequence $\alpha_1, \alpha_2, \dots, \alpha_k$ of Coxeter-Knuth moves such that $w = \tau(w)\alpha_1 \dots \alpha_k$. As $Q(\tau(w)) = Q(\tau(w)\uparrow)$ by Lemma 4.3, we compute

$$Q(w) = Q(\tau(w)\alpha_1 \dots \alpha_k) = Q((\tau(w)\uparrow)\alpha_1 \dots \alpha_k) \quad (2)$$

$$= Q((\tau(w)\alpha_1 \dots \alpha_k)\uparrow) = Q(w\uparrow) \quad (3)$$

where the third equality follows by Lemmas 3.3 and 3.4.

□

**Proof of Theorem 1.1:** Let $w$ be a reduced word and $\uparrow_1, \dots, \uparrow_k$ be the sequence of canonical Little bumps. By Theorem 4.4 and Lemma 4.1, we see

$$Q(w) = Q(w\uparrow_1 \dots \uparrow_k) = \mathrm{Tab}(w\uparrow_1 \dots \uparrow_k) = \mathrm{LS}(w).$$

□

We now demonstrate several consequences, including Lam's Conjecture. The first is Conjecture 11 from Little (2005), which first appeared as Conjecture 4.3.3 in the appendix of Garsia (2002).

**Corollary 4.5** Let $w$ be a reduced word and let $\uparrow_1, \uparrow_2, \dots, \uparrow_m$ be any sequence of Little bumps such that

$$v = w\uparrow_1 \dots \uparrow_m$$

is a Grassmannian word. Then $\mathrm{Tab}(v) = \mathrm{LS}(w)$.

This follows from Theorem 4.4. We can extend this result further. Let $\lambda$ be a partition with $w$ a Grassmannian word of shape $\lambda$. The permutation $\sigma$ associated to $w$ can be characterized by the number of initial fixed points. A Grassmannian permutation is minimal if it has no initial fixed points. Note the minimal Grassmannian permutation of a given shape is unique in $S_\infty$. Recall two reduced words communicate if there exists a sequence of Little bumps and inverse Little bumps changing one to the other.
<figure><img src="image_5.png" /><figcaption>Fig. 5: Removing a fixed point from the Grassmannian word $w = 7523645$ via the canonical sequence of bumps.</figcaption></figure>

**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 canonical sequence of Little bumps, $w$ can be changed to the Grassmannian word $w'$ and $v$ to the Grassmannian word $v'$. Since Little bumps are invertible, $Q(w) = Q(w')$ and $Q(v) = Q(v')$, we can conclude that $v$ and $w$ communicate if Grassmannian permutations of the same shape communicate. To show this, we demonstrate a sequence of Little bumps that will remove a fixed point at the beginning of an arbitrary Grassmannian permutation. Let $\sigma = a_1 \dots a_k b_1 \dots b_{n-k}$ be a Grassmannian permutation with $a_k b_1$ its sole descent. Our sequence is constructed by initiating a little bump at the last swap featuring each $b_j$, beginning with $b_1$. See Figure 5 for an example. 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.
☐

Additionally, we show how to embed Robinson-Schensted insertion and RSK in the Little map. In doing so, we recover the main results of Little (2005) in a much simplified form. This embedding was first predicted as Conjecture 4.3.1 in the appendix of Garsia (2002). For $w$ a word, let $\tilde{w}$ be the reverse of $w$.

**Theorem 4.6** Let $\sigma = \sigma_1 \dots \sigma_n \in S_n$, so that $w(\sigma) = (2\sigma_n - 1) \dots (2\sigma_1 - 1)$ is a reduced word, and let $RS(\sigma) = (P'(\sigma), Q'(\sigma))$ be the output of Robinson-Schensted insertion applied to $\sigma$. Upon applying the transformation $k \mapsto k - 1/2$ to the entries of $LS(w)$, we obtain $Q'(\sigma)$. We can obtain $P'(\sigma)$ by applying the same transformation to $LS(w(\sigma^{-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 $\sigma$. Therefore, upon applying the transformation $k \mapsto k - 1/2$, we see $LS(w(\sigma)) = Q(w(\sigma)) = Q'(\sigma)$. Since $RS(\sigma^{-1}) = (Q'(\sigma), P'(\sigma))$ (see e.g. Stanley (2001)), we can obtain $P'(\sigma)$ by applying the same transformation to $LS(w(\sigma^{-1}))$.

☐

We can embed RSK in Robinson-Schensted insertion (see Section 7 of Little (2005) for a description of this process), so Theorem 4.6 recovers an embedding of RSK into the Little map as well.

## References

P. Edelman and C. Greene. Balanced tableaux. *Advances in Mathematics*, 63(1):42–99, 1987.

A. Garsia. *The Saga of Reduced Factorizations of Elements of the Symmetric Group*. Laboratoire de combinatoire et d'informatique mathématique, 2002.

Z. Hamaker and B. Young. Relating Edelman-Greene insertion to the Little map. *arXiv preprint arXiv:1210.7119*, 2012.

T. Lam. Stanley symmetric functions and Peterson algebras. *Arxiv preprint arXiv:1007.2871*, 2010.

A. Lascoux and M. Schützenberger. Schubert polynomials and the Littlewood-Richardson rule. *letters in mathematical physics*, 10(2):111–124, 1985.

D. Little. Combinatorial aspects of the Lascoux-Schützenberger tree. *Advances in Mathematics*, 174(2): 236–253, 2003.

D. P. Little. Factorization of the Robinson–Schensted–Knuth correspondence. *Journal of Combinatorial Theory, Series A*, 110(1):147–168, 2005.

R. Stanley. On the number of reduced decompositions of elements of Coxeter groups. *Eur. J. Comb.*, 5: 359–372, 1984.

R. Stanley. *Enumerative Combinatorics*, volume 2. Cambridge Univ Pr, 2001.