\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram} \OneNumberAllTheorems \usepackage[all]{xy} \usepackage{youngtab} \usepackage{ytableau} \usepackage{young} \usepackage{tikz}%,varwidth} \usetikzlibrary{arrows,petri,topaths} \usepackage{xcolor} %%%%%%blackboard letters \newcommand{\bP}{\mathbb{Z}_+} %:Sym definitions \DeclareMathOperator{\sym}{Sym} %:Qsym definitions \DeclareMathOperator{\qsym}{QSym} \newcommand{\qs}{{\mathcal{S}}} % quasisymmetric schurs %:Nsym definitions \newcommand{\ncsa}{\mathbf{s}_{\alpha}} \newcommand{\ncsb}{\mathbf{s}_{\beta}} \newcommand{\ncsg}{\mathbf{s}_{\gamma}} %%%%%%%%%%%% posets %\newcommand{\btr}{\blacktriangleright} \newcommand{\Lc}{\mathcal{L}_{c}} % Composition poset %: compositions and tableaux \newcommand\partitionof[1]{\widetilde{#1}} \newcommand\reverse[1]{{#1}^r} \newcommand{\set}{\mathsf{set}} % for sets corresponding to compositions \newcommand{\cont}[1]{\mathsf{cont}(#1)} % for content \newcommand{\rect}[1]{\mathsf{rect}(#1)} % rectification \newcommand{\colform}[1]{\mathsf{colform}(#1)} %column form \DeclareMathOperator{\Frankrm}{Frank} \DeclareMathOperator{\Franktabrm}{FrankTab} \newcommand{\frank}[1]{\Frankrm(#1)} % set of frank tableaux \newcommand{\lrfrank}[1]{\Frankrm(#1)} % set of LR frank words \newcommand{\lrfranktab}[1]{\Franktabrm(#1)} % tableaux from frank words \newcommand{\rot}[1]{\mathsf{rotate}(#1)} % rotated partition by 180 \newcommand{\addt}{\mathfrak{t}} % box-adding operator \newcommand{\suchthat}{\mid} \newcommand{\cskew}{{/\!\!/}}% for skew composition shapes % sets of tableaux% \DeclareMathOperator{\YT}{YT} \DeclareMathOperator{\LRT}{LRT} %Left LR tableaux \DeclareMathOperator{\SCT}{SCT} \DeclareMathOperator{\CT}{CT} \newcommand{\ptab}{\mathsf{P}} % P-tableau \newcommand{\qtab}{\mathsf{Q}} % Q-tableau \newcommand{\sh}{\mathsf{shape}} % underlying shape \DeclareMathOperator{\nsym}{NSym} \definecolor{darkbrown}{rgb}{0.0, 0.0, 1.0} \newcommand{\bemph}[1]{\textcolor{darkbrown}{\emph{#1}}} % the weird shade of brown \newcommand{\mbP}{\bP^{*}} % free monoid on positive integers \newcommand{\sgrp}[1]{\mathfrak{S}_{#1}} % symmetric group \newcommand{\crw}[1]{\mathsf{rw}(#1)} % row reading word \newcommand{\stan}[1]{\mathsf{stan}(#1)} % standardization of tableau \newcommand{\pskew}{/} % skew \newcommand{\cgw}[1]{\mathsf{gw}(#1)} % growth word \newcommand{\sort}{\mathsf{sort}} \newcommand{\evac}{\mathsf{evac}} %% Authors according to amsart's syntax + distinction between Given %% and Proper names: %%%%%%%%% a placer avant \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Auteur \author{\firstname{Edward} \lastname{Richmond}} \address{Oklahoma State University\\ Department of Mathematics\\ Stillwater\\ OK 74708, USA} %% e-mail address \email{edward.richmond@okstate.edu} \author{\firstname{Vasu} \lastname{Tewari}} \address{University of Pennsylvania\\ Department of Mathematics\\ Philadelphia\\ PA 19104, USA} \email{vvtewari@math.upenn.edu} %%%%% Sujet \keywords{Crystal operator, Littlewood--Richardson coefficient, noncommutative symmetric function, symmetric function, Schur function.} \subjclass{05E05, 05A05, 05E10, 20C30} %%%%% Gestion \DOI{10.5802/alco.155} \datereceived{2019-08-19} \daterevised{2020-08-11} \dateaccepted{2020-10-06} %%%%% Titre et résumé \title [Noncommutative LR coefficients and crystal reflections] {Noncommutative LR coefficients and crystal reflection operators} \begin{abstract} We relate noncommutative Littlewood--Richardson coefficients of Bessenrodt--Luoto--van~Willigenburg to classical Littlewood--Richardson coefficients via crystal reflection operators. A key role is played by the combinatorics of frank words. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Quasisymmetric Schur functions, introduced by Haglund--Luoto--Mason--van~Willigenburg~\cite{HLMvW}, form a prominent basis for the Hopf algebra of quasisymmetric functions $\qsym$. The quasisymmetric Schur function indexed by the composition $\alpha$, denoted by $\qs_{\alpha}$, is obtained by summing monomials attached to semistandard composition tableaux of shape $\alpha$. This is reminiscent of the definition of Schur functions as sums of monomials corresponding to semistandard Young tableaux. As the name suggests, quasisymmetric Schur functions share many properties with classical Schur functions, and Mason's map $\rho$~\cite{Ma} connects the combinatorics of composition tableaux to that of Young tableaux. Understanding analogues of Schur functions and their generalizations has long been a theme in algebraic combinatorics; see~\cite{Al,AHM,AS,BBSSZ,MPS,Se} for recent work in this context. \looseness-1 The Hopf algebra of noncommutative symmetric functions $\nsym$, introduced in the seminal paper~\cite{GKLLRT}, is Hopf-dual to $\qsym$ as shown by Malvenuto--Reutenauer~\cite{MaRe}. Bessenrodt--Luoto--van~Willigenburg~\cite{BLvW} studied the dual basis elements $\ncsa$ corresponding to quasisymmetric Schur functions. The resulting functions, also indexed by compositions, are called noncommutative Schur functions. The inclusion of the Hopf algebra of symmetric functions $\sym$ into $\qsym$ induces a projection $\chi:\nsym\twoheadrightarrow \sym$. This projection maps noncommutative Schur functions to classical Schur functions, and justifies the name of the former. The structure constants $C_{\alpha\beta}^{\gamma}$ that arise in \begin{align}\label{eqn:noncommutative lr coefficients introduction} \ncsa\cdot\ncsb=\sum_{\gamma}C_{\alpha\beta}^{\gamma}\, \ncsg \end{align} are called noncommutative Littlewood--Richardson (LR) coefficients. These coefficients turn out to be nonnegative integers that refine the classical LR coefficients $c_{\nu\mu}^{\lambda}$ that arise in the product of Schur functions \begin{align}\label{eqn:classical lr coefficients introduction} s_{\nu}\cdot s_{\mu}=\sum_{\lambda}c_{\nu\mu}^{\lambda}\, s_{\lambda}. \end{align} More precisely, suppose $\nu$ and $\mu$ are partitions that rearrange to compositions $\alpha$ and $\beta$ respectively. Applying $\chi$ to both sides in~\eqref{eqn:noncommutative lr coefficients introduction} and comparing the result with~\eqref{eqn:classical lr coefficients introduction} implies %that \begin{align}\label{eqn: nc lr refines lr introduction} c_{\nu\mu}^{\lambda}=\sum_{\gamma}C_{\alpha\beta}^{\gamma} \end{align} where the sum on the right runs over all compositions $\gamma$ that rearrange to $\lambda$. Among the numerous combinatorial interpretations of $c_{\nu\mu}^{\lambda}$, the one we focus on states that $c_{\nu\mu}^{\lambda}$ counts LR tableaux of shape $\lambda/\mu$ and content $\nu$. Our primary goal in this article is to describe the summands on the right hand side in \eqref{eqn: nc lr refines lr introduction} in terms of LR tableaux. To this end, crystal reflection operators are key. To state our result, we introduce the necessary notation briefly. The reader is referred to Section~\ref{sec:background} for details. Given a composition $\alpha$, we denote the partition underlying $\alpha$ by $\sort(\alpha)$. Let $\LRT(\lambda,\mu,\nu)$ be the set of LR tableaux of shape $\lambda/\mu$ and content $\nu$. Given a permutation $\sigma$, let $\LRT^{\sigma}(\lambda,\mu,\nu)$ be the set of tableaux obtained by applying the crystal reflection operators corresponding to a reduced word of $\sigma$. Let $\alpha\coloneqq \sigma\cdot \nu$, and let $\beta$ be any composition that satisfies $\sort(\beta)=\mu$. On applying the map $\rho_{\beta}^{-1}$ (which sends Young tableaux to composition tableaux,~\cite[Chapter~4]{LMvW}) to elements in $\LRT^{\sigma}(\lambda,\mu,\nu)$, we obtain the disjoint decomposition \begin{align}\label{eqn:skew LR disjoint} \LRT^{\sigma}(\lambda,\mu,\nu)=\coprod_{\gamma}X_{\alpha\beta}^{\gamma}, \end{align} where $X_{\alpha\beta}^{\gamma}$ consists of all tableaux $T\in \LRT^{\sigma}(\lambda,\mu,\nu)$ whose outer shape under $\rho_{\beta}^{-1}$ is given by the composition $\gamma$ . Under this setup, our main theorem states the following. \begin{theorem}\label{thm:intro_main_1} The noncommutative LR coefficient $C_{\alpha\beta}^{\gamma}$ equals the cardinality of $X_{\alpha\beta}^{\gamma}$. \end{theorem} The upshot of Theorem~\ref{thm:intro_main_1} is that starting from $\LRT(\lambda,\mu,\nu)$, we can compute \emph{all} noncommutative LR coefficients $C_{\alpha\beta}^{\gamma}$, where $\alpha$ dictates the choice of crystal reflections to be performed and $\beta$ determines the generalized $\rho$ map to be applied. We also interpret Theorem~\ref{thm:intro_main_1} in terms of chains in Young's lattice indexed by certain frank words and obtain a rule for $C_{\alpha\beta}^{\gamma}$ involving box-adding operators on compositions. In the case where $\alpha$ is either a partition or reverse partition, our interpretations yield the two LR rules in~\cite{BTvW}. For an example demonstrating Theorem~\ref{thm:intro_main_1}, see Subsection~\ref{subsec:illustrating main results}. Note that LR coefficients can be interpreted as the number of lattice points in an appropriate convex polytope/cone~\cite{PV}. Since Theorem~\ref{thm:intro_main_1} describes noncommutative LR coefficients by refining the set of LR tableaux, it is natural to ask if noncommutative LR coefficients count lattice points in some refinement of the corresponding polytope/cone. Data suggest that the analogue of the saturation conjecture, famously resolved by Knutson and Tao~\cite{KnTa}, holds for noncommutative LR coefficients as well. In fact~\eqref{eqn: nc lr refines lr introduction} tells us that saturation of noncommutative LR coefficients implies that of the classical counterparts. This motivates studying these constants from a polytopal perspective, which is why the authors were interested in a statement like Theorem~\ref{thm:intro_main_1} in the first place. \subsection*{Outline of the article} Section~\ref{sec:background} sets up all the necessary combinatorial background. Section~\ref{sec:main_result} describes our central result along with examples. Section~\ref{subsec:growth_and_frank} introduces growth words and frank words. Section~\ref{subsec:proof_outline} presents an outline of our proof strategy given its technical nature. Section~\ref{subsec:skew shape compatibility} identifies LR tableaux with certain distinguished frank words called compatible words, drawing upon work by Remmel--Shimozono~\cite{RS3}. In Section~\ref{subsec:symmetric group action frank words}, we describe the Lascoux--Sch{\"u}tzenberger symmetric group action on frank words. Section~\ref{subsec:sym_actions_tableaux_words} relates crystal reflections acting on LR tableaux to the aforementioned action restricted to compatible words. Section~\ref{sec:back to CT} relates the results in Section~\ref{sec:Frank words} back to noncommutative LR coefficients. We conclude our article with Corollary~\ref{cor:box-adding and LR coefficients}, which reinterprets our combinatorial interpretation for noncommutative LR coefficients in terms of box-adding operators on compositions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Background}\label{sec:background} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% To keep this section brief, we assume knowledge of combinatorial structures and algorithms arising in symmetric functions theory such as partitions, skew shapes, Young tableaux, Robinson--Schensted--Knuth insertion and jeu-de-taquin. The reader is referred to standard texts~\cite{Fu,Sa,St} for further information. \looseness-1 Regarding notions relevant to the theory of quasisymmetric Schur functions, we adhere to the notation and conventions in~\cite{LMvW}. \emph{We emphasize that what we call quasisymmetric Schur functions in this article are the Young quasisymmetric Schur functions in~\cite{LMvW}.} This choice, although cosmetic as both the functions are related via a simple involution, has its benefits. The tableau objects that we consider in the quasisymmetric/noncommutative setting align with the more prevalent notion of Young tableaux rather than reverse tableaux. Furthermore, it is the Young quasisymmetric Schurs that decompose the dual immaculate quasisymmetric functions~\cite{BBSSZ} positively as shown recently in~\cite{AHM}, thereby connecting two well-studied quasisymmetric analogues of Schurs. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Words} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Throughout, we denote the set of positive integers by $\bP$. Given $n\in \bP$, define $[n]:=\{1,\dots,n\}$. Furthermore, set $[0]:=\emptyset$. Let $\mbP$ denote the set of all words in the alphabet $\bP$. Consider $w=w_1\cdots w_n\in \mbP$. We call $n$ the \bemph{length} of $w$ and denote it by $|w|$. The word $w_n\cdots w_1$ is denoted by $\reverse{w}$. We say that $w$ is \bemph{reverse-lattice} if every suffix of $w$ contains at least as many $i$'s as $i+1$'s for all $i\in \bP$. Let $\sgrp{n}$ be the permutation group on $[n]$ and denote the longest element in $\sgrp{n}$ by $w_0^{(n)}$, or simply by $w_0$ if $n$ is clear from context. The permutation $\sigma\in\sgrp{n}$ acts on a sequence $\lambda=(\lambda_1,\dots,\lambda_n)$ by $\sigma\cdot \lambda=(\lambda_{\sigma^{-1}(1)},\dots, \lambda_{\sigma^{-1}(n)})$. Note that this is a right action. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Compositions and partitions} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% A finite list of nonnegative integers $\alpha = (\alpha _1, \ldots , \alpha _\ell)$ is called a \bemph{weak composition}. If $\alpha_i>0$ for all $1\leq i\leq\ell$, then $\alpha$ is called a \bemph{composition}. If, in addition, we have $\alpha _1\geq \cdots \geq\alpha _\ell >0$, then $\alpha$ is called a \bemph{partition}. Given $\alpha=(\alpha_1, \ldots , \alpha_\ell)$ we call the $\alpha _i$ the \bemph{parts} of $\alpha$ and the sum of the $\alpha_i$, denoted by $|\alpha|$, is called the \bemph{size} of $\alpha$. We denote the number of parts of $\alpha$ by $\ell(\alpha$) and call it the \bemph{length} of $\alpha$. The unique composition of length and size zero is denoted by $\varnothing$. We denote the composition $(\alpha_{\ell},\dots, \alpha_1)$ by $\reverse{\alpha}$. Also, denote the transpose of a partition $\lambda$ by $\lambda^t$. The reader is warned that on occasion we will suppress commas and parentheses when writing our compositions. The \bemph{composition diagram} of $\alpha=(\alpha_1,\ldots,\alpha_{\ell})$ is the left-justified array of boxes with $\alpha_i$ boxes in row $i$ from the bottom. If $\alpha$ is a partition, then the composition diagram of $\alpha$ coincides with the Young diagram of $\alpha$ in French notation. See Figure~\ref{fig:comp_diagram} for the composition diagram of $(2,1,3)$. \begin{figure}[htb]\centering \ytableausetup{mathmode,boxsize=1em} \ydiagram{3,1,2} \vspace*{-1mm} \caption{The composition diagram of $(2,1,3)$.} \label{fig:comp_diagram} \vspace*{-1mm} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Young tableaux} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% A \bemph{Young tableau} $T$ (henceforth YT) of \bemph{skew shape} $\lambda/\mu$ is a filling of the boxes of $\lambda/ \mu$ with positive integers so that entries along the rows increase weakly read from left to right and entries along the columns increase strictly read from bottom to top. If the entries in $T$ are all distinct and belong to $[|\lambda/\mu|]$, then we call $T$ a \bemph{standard Young tableau} (henceforth SYT.) We denote the set of YTs of shape $\lambda/\mu$ by $\YT(\lambda/\mu)$. If $T$ is a YT with maximal entry $m$, then the \bemph{content} of $T$, denoted by $\cont{T}$, is the weak composition $(\alpha_1,\dots,\alpha_m)$ where $\alpha_i$ for $1\leq i\leq m$ counts the instances of $i$ in $T$. \looseness-1 The \bemph{standardization} of $T$, denoted by $\stan{T}$, is obtained by replacing the $\alpha_i$ entries in $T$ equal to $i$ by the integers $1+\sum_{j=1}^{i-1}\alpha_j$ through $\sum_{j=1}^{i}\alpha_j$ from left to right. \begin{figure}[htb]\centering \vspace*{-1mm} \ytableausetup{mathmode, boxsize=1em} \begin{ytableau} 2\\1& 2& 2\\*(gray!20) & *(gray!20) & 1 & 2 & 3 & 3\\ *(gray!20) & *(gray!20) & *(gray!20) & *(gray!20) & 1 & 2 & 4 \end{ytableau} \hspace{5mm} $\xrightarrow{\makebox[1.5cm]{{\sf stan}}}$\hspace{5mm} \begin{ytableau} 4\\1& 5& 6\\*(gray!20) & *(gray!20) & 2 & 7 & 9 & 10\\ *(gray!20) & *(gray!20) & *(gray!20) & *(gray!20) & 3 & 8 & 11 \end{ytableau} \vspace*{-1mm} \caption{A Young tableau and its standardization.} \label{fig: growth word} \vspace*{-1mm} \end{figure} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Composition tableaux} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% To define composition tableaux, we need an analogue of Young's lattice. The \bemph{Young composition poset} $\Lc$ is the poset on compositions where the partial order $<_c$ is obtained by taking the transitive closure of the cover relation $\lessdot_c$ defined next. Let $\beta=(\beta_1,\ldots,\beta_m)$. Then $ \beta \lessdot_c \alpha$ if exactly one of the following conditions holds. \begin{itemize} \item $\alpha=(\beta_1,\ldots,\beta_m,1)$. \item $\alpha=(\beta_1,\ldots,\beta_k+1,\ldots,\beta_m)$ for some $k$ where $\beta_k\neq \beta_i$ for all $i>k$. \end{itemize} The reader may check that, for instance, the compositions covering $(2,1,3,2)$ in $\Lc$ are $(2,1,3,2,1)$, $(2,2,3,2)$, $(2,1,3,3)$ and $(2,1,4,2)$. \begin{rema}\label{rem:alternate definition partial order L_c}\emph{ The definition of {$\lessdot_c $} implies that $\beta<_c \alpha$ if and only if for every $\beta_i\geq \beta_j$ where $i>j$ we have $\alpha_i\geq \alpha_j$.} \end{rema} If $\beta <_{c} \alpha$ and $\beta$ is drawn in the bottom left corner of $\alpha$, then the \bemph{skew composition shape} $\alpha \cskew \beta$ is defined to be the array of boxes that belong to $\alpha$ but not to $\beta$. We refer to $\alpha$ and $\beta$ as the \bemph{outer shape} and \bemph{inner shape} respectively. If the inner shape is $\varnothing$, then instead of writing $\alpha \cskew \varnothing$ we simply write $\alpha$. The \bemph{size} of $\alpha\cskew \beta$, denoted by $\vert \alpha\cskew\beta\vert$, is $\vert \alpha\vert-\vert\beta\vert$. A \bemph{composition tableau} (abbreviated to $\CT$) $\tau$ of \bemph{shape} $\alpha \cskew \beta$ is a filling $ \tau: \alpha\cskew \beta \longrightarrow \bP $ that satisfies the following conditions. \begin{enumerate} \item\label{sect2.4_1} The entries in each row increase weakly from left to right. \item\label{sect2.4_2} The entries in the leftmost column increase strictly from bottom to top. \item\label{sect2.4_3} For any configuration in $\tau$ of the type in Figure~\ref{fig:triple configuration}, if $a\leq c$ then $b\cdots > w_n$. Given a nonempty word $w\in \mbP$, consider its factorization $w^{(1)}w^{(2)}\cdots w^{(m)}$ where each $w^{(i)}$ is a maximal column word (necessarily nonempty). We call $w$ an \bemph{$m$-column word}. The \bemph{column form} of $w$ is the composition $\colform{w}\coloneqq(|w^{(1)}|,\dots,|w^{(m)}|) $. \begin{defi}[Frank word] We say that $w$ is \bemph{frank} if $\ptab(w)$ is of shape $\lambda^{t}$ where $\lambda=\sort(\colform{w})$. Given a composition $\alpha$, we define $\frank{\alpha}$ to be the set of frank words $w$ satisfying $\colform{w}=\alpha$. \end{defi} A remarkable feature of frank words is that one knows the shape of the P-tableau without performing jeu-de-taquin. As an example of a frank word, consider $w= \framebox{432}\hspace{1mm}\framebox{32} \hspace{1mm} \framebox{6531}$. It is a $3$-column word with $\colform{w}=(3,2,4)$. For clarity, we put frames around maximal column words. Figure~\ref{fig:w is frank} depicts $\ptab(w)$. Note that the shape underlying it is $(4,3,2)^t$. Therefore, $w\in \frank{(3,2,4)}$. \begin{figure}[htb]\centering \ytableausetup{mathmode,boxsize=1em} \begin{ytableau} 4\\3 & 6\\2 & 3 & 5\\1 & 2 & 3 \end{ytableau} \caption{The insertion tableau corresponding to $w=\framebox{432}\hspace{1mm} \framebox{32} \hspace{1mm} \framebox{6531}$.} \label{fig:w is frank} \end{figure} %%%%%%%%%%%%%%%%%%%%%%% \subsection{Outline of proof}\label{subsec:proof_outline} %%%%%%%%%%%%%%%%%%%%%%% Given the technical nature of our argument, we give a brief overview of our strategy toward establishing Theorem~\ref{thm:main result 1}. \begin{enumerate} \item\label{sect4.2_1} Given a skew shape $\lambda/\mu$ and a composition $\alpha\vDash |\lambda|-|\mu|$, we consider the distinguished subset of $\frank{\alpha}$ comprising $\lambda/\mu$-compatible frank words. \item\label{sect4.2_2} The main result of this section, Proposition~\ref{prop:sigma-LR and frank}, identifies these words as precisely the growth words of tableaux in $\LRT^{\sigma}(\lambda,\mu,\nu)$ where $\nu$ satisfies $\sort(\alpha)=\nu$. To arrive at this result, we study a symmetric group action on frank words and establish that it really is the crystal reflection action in disguise. This is the content of Subsections~\ref{subsec:symmetric group action frank words} and~\ref{subsec:sym_actions_tableaux_words}. \item\label{sect4.2_3} Lemma~\ref{lem: rect stan equaling Q} then states that the rectification of a Young tableau may be described in terms of its growth word using Sch{\"u}tzenberger's evacuation. \item\label{sect4.2_4} Finally, Proposition~\ref{prop:crystal action permutes parts} establishes that applying $\rho^{-1}$ to $\rect{\stan{T}}$ for $T$ an element in $\LRT^{\sigma}(\lambda,\mu,\nu)$ does indeed give the canonical tableau of shape $\sigma\cdot \nu$. From this, Theorem~\ref{thm:main result 1} follows. \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{\texorpdfstring{$\lambda/\mu$}{lskewm}-compatible frank words and LR tableaux} \label{subsec:skew shape compatibility} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{defi}\label{def:compatible} Given partitions $\lambda,\mu$ such that $\mu\subseteq \lambda$ and a composition $\alpha$, we say that $w\in \frank{\alpha}$ is \bemph{$\lambda/\mu$-compatible} if for every suffix $w'$ of $w$, we have that $\cont{w'}+\mu^t$ is a partition and that $\cont{w}+\mu^t=\lambda^t$. Set \begin{align*} \lrfrank{\lambda,\mu,\alpha}\coloneqq\{w\in\frank{\alpha}\suchthat \text{ $w$ is $\lambda/\mu$-compatible}\}. \end{align*} \end{defi} \noindent Definition~\ref{def:compatible} may be interpreted as saying that $w\in \frank{\alpha}$ is $\lambda/\mu$-compatible if it is the growth word of a Young tableau of shape $\lambda/\mu$. Observe that we must have $\alpha\vDash |\lambda|-|\mu|$. As an example, note that $w=\framebox{621}\hspace{1mm} \framebox{76432} \in \frank{\alpha}$ is $\lambda/\mu$-compatible for $\lambda=76422$, $\mu=5521$, and $\alpha=35$. The reader can easily verify that $w$ is the growth word of the tableau in Figure~\ref{fig:phi of w}. Note further that this tableau is an LR tableau. There is an intimate link between LR tableaux and compatible words. To understand this link we go via an intermediate tableau object. Given $w\in \lrfrank{\lambda,\mu,\alpha}$, let $w^{(1)}\cdots w^{(m)}$ be its maximal column word factorization where $m\coloneqq\ell(\alpha)$. Construct a Young tableau $\phi(w)$ of shape $\lambda/\mu$ and content $\reverse{\alpha}$ as follows: Let $\lambda^{(0)}\coloneqq\lambda$ and inductively define $\lambda^{(i)}$ for $1\leq i\leq m$ to be such that $\lambda^{(i-1)}/\lambda^{(i)}$ is a horizontal strip with boxes in columns given by letters appearing in $w^{(i)}$. Subsequently, fill the boxes of the horizontal strips $\lambda^{(i-1)}/\lambda^{(i)}$ with $m+1-i$ to obtain $\phi(w)$. Note that $\lambda^{(m)}$ is $\mu$ and that $\phi(w)$ does indeed belong to $\YT(\lambda/\mu)$. Figure~\ref{fig:phi of w} gives an example. \begin{figure}[htb]\centering \ytableausetup{mathmode,boxsize=1em} \begin{ytableau} *(red!40)2 & *(red!40)2\\ *(gray!20) & *(blue!50)1\\ *(gray!20) & *(gray!20) & *(blue!50)1 & *(blue!50)1\\ *(gray!20) & *(gray!20) & *(gray!20) & *(gray!20) &*(gray!20) & *(red!40)2\\ *(gray!20) & *(gray!20) & *(gray!20) & *(gray!20) &*(gray!20) & *(blue!50)1 & *(blue!50)1 \end{ytableau} \caption{The tableau $\phi(w)$ corresponding to $\framebox{\textcolor{red}{621}} \hspace{1mm}\framebox{\textcolor{blue}{76432}}$.} \label{fig:phi of w} \end{figure} Define \begin{align} \lrfranktab{\lambda,\mu,\alpha}\coloneqq\{\phi(w)\suchthat w\in \lrfrank{\lambda,\mu,\alpha}\}. \end{align} Our next lemma establishes that $\LRT(\lambda,\mu,\nu)=\lrfranktab{\lambda,\mu, \reverse{\nu}}$. \begin{lemma}\label{lem:LR tableaux and LRfranktab} Let $\lambda,\mu$ and $\nu$ be partitions such that $\mu\subseteq \lambda$ and $|\nu|=|\lambda/\mu|$. We have \[ \LRT(\lambda,\mu,\nu)=\lrfranktab{\lambda,\mu, \reverse{\nu}}. \] \end{lemma} \begin{proof} Let $w\in \lrfrank{\lambda,\mu, \reverse{\nu}}$. As $\colform{w}=\reverse{\nu}$ and $w$ is frank, we know that $w$ is the reading word of a tableau of skew shape $\rot{\nu^t}$, which is obtained from the shape $\nu$ by a $180^{\circ}$ rotation. It follows that $\phi(w)\in \LRT({\lambda,\mu,\nu})$. This establishes $ \lrfranktab{\lambda,\mu, \reverse{\nu}}\subseteq \LRT(\lambda,\mu,\nu)$. The opposite inclusion follows since the reading word of an LR tableau is reverse-lattice. In particular, the growth word of any $T\in \LRT(\lambda,\mu,\nu)$ is the reading word of a YT of skew shape $\rot{\nu^t}$. \end{proof} Figure~\ref{fig:cgw of LR tableaux} depicts growth words of LR tableaux in Figure~\ref{fig:LR-examples} as reading words of YTs of skew shape $\rot{\nu^t}$. Here $\lambda=76432$, $\mu=644$ and $\nu=431$. \begin{figure}[htb]\centering \ytableausetup{mathmode,boxsize=1em} \begin{ytableau} *(red!30)2& *(blue!50)3 & *(magenta!80)7\\ *(gray!20) & *(blue!50)2 & *(magenta!80)6\\ *(gray!20) & *(blue!50)1 & *(magenta!80)5\\ *(gray!20) & *(gray!20) & *(magenta!80)1 \end{ytableau} \hspace{10mm} \begin{ytableau} *(red!30)2 & *(blue!50)6 & *(magenta!80)7\\ *(gray!20) & *(blue!50)3 & *(magenta!80)5\\ *(gray!20) & *(blue!50)1 & *(magenta!80)2\\ *(gray!20) & *(gray!20) & *(magenta!80)1 \end{ytableau} \hspace{10mm} \begin{ytableau} *(red!30)3 & *(blue!50)6 & *(magenta!80)7\\ *(gray!20) & *(blue!50)2 & *(magenta!80)5\\ *(gray!20) & *(blue!50)1 & *(magenta!80)2\\ *(gray!20) & *(gray!20) & *(magenta!80)1 \end{ytableau} \caption{Growth words of LR tableaux are frank words.} \label{fig:cgw of LR tableaux} \end{figure} Now that we have established elements of $\lrfranktab{\lambda,\mu,\reverse{\nu}}$ as LR tableaux in the usual sense, it remains to understand the case where $\reverse{\nu}$ is replaced by an arbitrary composition. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{A symmetric group action on frank words}\label{subsec:symmetric group action frank words} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% We proceed to describe a symmetric group action on frank words that we subsequently connect to the symmetric group action on Young tableaux via crystal reflections described earlier. This new action is best understood by focusing on 2-column frank words, very much in the manner that crystal reflections are understood by acting on consecutive letters. Let $A$ denote the set of 2-column frank words. Consider $w\in A$ and let $\colform{w}=(\beta_1,\beta_2)$. Thus, $w$ may be identified as the reading word of a tableau $T$ of shape $(\beta_1,\beta_2)^t$ if $\beta_1\geq \beta_2 $ or of a tableau $T$ of shape $(\beta_2,\beta_2)^t/(\beta_2-\beta_1)^t$ if $\beta_1<\beta_2$; see~\cite[Appendix~2]{RS1}. If the former holds, define $\iota(w)$ to be the reading word of the unique tableau $ T'$ of shape $(\beta_1,\beta_1)^t/(\beta_1-\beta_2)^t$ that is jdt-equivalent to $T$ (obtained by performing jeu-de-taquin slides within the rectangle $(\beta_1,\beta_1)^t$). If the latter holds, define $\iota(w)$ to be the reading word of the unique tableau $ T'$ of shape $(\beta_2,\beta_1)^t$ that is jdt-equivalent to $T$. Clearly, $\iota$ is an involution on $A$. Equally importantly, $w$ and $\iota(w)$ are Knuth-equivalent. For instance, jdt-equivalence of tableaux in Figure~\ref{fig:jdt on two columns} implies that \[ \iota(\framebox{76421} \hspace{1mm} \framebox{632})=\framebox{621}\hspace{1mm}\framebox{76432}. \] \begin{figure}[htb]\centering \ytableausetup{mathmode,boxsize=1em} \begin{ytableau} 7\\6\\4 & 6\\2 & 3\\1&2 \end{ytableau} $\longrightarrow$ \begin{ytableau} 7\\6&6\\2& 4\\1 & 3\\\none&2 \end{ytableau} $\longrightarrow$ \begin{ytableau} 6 & 7\\2 & 6\\1 & 4\\\none & 3\\\none & 2 \end{ytableau} \caption{Establishing $\iota(\framebox{76421}\hspace{1mm}\framebox{632})=\framebox{621} \hspace{1mm} \framebox{76432}$ by jeu-de-taquin.} \label{fig:jdt on two columns} \end{figure} We employ the involution $\iota$ to construct the desired symmetric group action. Let $\lambda$ be a partition and let $m\coloneqq\ell(\lambda)$. Define \[ \mathcal{F}_{\lambda}\coloneqq \coprod_{\sort(\beta)=\lambda}\frank{\beta}. \] Following~\cite{LS2}, define an action of $\sgrp{m}$ on $\mathcal{F}_{\lambda}$ by describing the action of the generator $s_i$ for $1\leq i\leq m-1$ as follows: Let $w^{(1)}\cdots w^{(m)}$ be the maximal column word factorization of $w\in \mathcal{F}_{\lambda}$. Let $v^{(i)}v^{(i+1)}\coloneqq\iota(w^{(i)}w^{(i+1)})$ and define $v=w^{(1)}\cdots w^{(i-1)}v^{(i)}v^{(i+1)}w^{(i+2)}\cdots w^{(m)}$. Observe that $\sort(\colform{v})=\lambda$. As $v$ and $w$ are Knuth-equivalent, we infer that $v\in \mathcal{F}_{\lambda}$. %Thus, we infer that $v$ is equal to $\crw{T'}$ for some $T'\in \frank{s_i\cdot \alpha}$. We define $v$ to be $s_i(w)$. This given, we may define $\sigma(w)$ for any $\sigma\in \mathfrak{S}_m$ by picking a reduced word for $\sigma$. Figure~\ref{fig:s_3_orbit} depicts the $\mathfrak{S}_3$-orbit of the frank word $\framebox{4321}\hspace{1mm} \framebox{632}\hspace{1mm} \framebox{53}\in \mathcal{F}_{432}$. We have chosen to represent the action on words via their tableau representatives. In particular, each column when read from top to bottom gives a maximal column word in the maximal column word factorization. Each $s_i$ performs a ``local'' jeu-de-taquin on two columns. \begin{figure}[htb]\centering \begin{tikzpicture}%[inner sep=0in,outer sep=0in] \node (t) at (-6,0) { \ytableausetup{mathmode,boxsize=1em} \begin{ytableau} 4\\3 & 6\\2 & 3 & 5\\1 & 2 & 3 \end{ytableau}}; \node (t1) at (-3,2) { \begin{ytableau} 4 & 6\\ 3 & 3\\ 2 & 2 & 5\\ \none & 1 & 3 \end{ytableau}}; \node (t2) at (-3,-2) { \begin{ytableau} 4 \\ 3 \\ 2 & 3 & 6\\ 1 & 2 & 5\\ \none & \none & 3 \end{ytableau}}; \node (t12) at (0,2) { \begin{ytableau} 4\\ 3 & 3 & 6\\ 2 & 2 & 5\\ \none & \none & 3\\ \none & \none & 1 \end{ytableau}}; \node (t21) at (0,-2) { \begin{ytableau} 3 & 4\\ 2 & 3 & 6\\ \none & 2 & 5\\ \none & 1 & 3 \end{ytableau}}; \node (t121) at (3,0) { \begin{ytableau} 3 & 4 & 6\\ 2 & 3 & 5\\ \none & 2 & 3\\ \none & \none & 1 \end{ytableau}}; \draw[very thick,red] (t)--(t1) node [midway, above] {$s_1$};; \draw[very thick,blue] (t)--(t2)node [midway, below] {$s_2$}; \draw[very thick,red] (t2)--(t21) node [midway, below] {$s_1$}; \draw[very thick,blue] (t1)--(t12)node [midway, above] {$s_2$}; \draw[very thick,red] (t12)--(t121)node [midway, above] {$s_1$}; \draw[very thick,blue] (t21)--(t121)node [midway, below] {$s_2$}; \end{tikzpicture} \caption{The $\mathfrak{S}_3$-orbit of $\framebox{4321}\hspace{1mm} \framebox{632}\hspace{1mm} \framebox{53}$. } \label{fig:s_3_orbit} \end{figure} \subsection{Relating the two symmetric group actions}\label{subsec:sym_actions_tableaux_words} Our next lemma connects the action of crystal reflection operators on $\lrfranktab{\lambda,\mu,\alpha}$ to the symmetric group action on $\lambda/\mu$-compatible frank words in $\lrfrank{\lambda,\mu,\alpha}$. \begin{lemma}\label{lem:commuting action} Consider $w\in \lrfrank{\lambda,\mu,\alpha}$ and $i$ satisfying $1\leq i\leq \ell(\alpha)-1$. We have that $s_i(\phi(w))=\phi(s_{\ell(\alpha)-i}(w))$. \end{lemma} \begin{proof} Without loss of generality, we may assume that $\alpha$ has two parts. Suppose $\alpha=(p,q)\vDash n$. Assume $w=w^{(1)}w^{(2)}$ where $|w^{(1)}|=p$ and $|w^{(2)}|=q$. We want to show that $s_1(\phi(w))=\phi(\iota(w))$. Assume $p\cdots > a_{p}$ and $b_1 > \cdots > b_{q}$. As $w$ is frank, it is the reading word of a Young tableau of skew shape $\rot{(q,p)^{t}}$. Thus, $a_i\leq b_i$ for $1\leq i\leq p$. \looseness-1 Instead of computing $\iota(w)$ by rectifying the appropriate two-columned tableau, one may perform successive Schensted column insertions of the numbers $a_p$ down to $a_1$ starting from the single-columned tableau with column word $w^{(2)}$. See Figure~\ref{fig:iota via column insertion} for an example. Compare with Figure~\ref{fig:jdt on two columns} which established the same fact using jeu-de-taquin. \begin{figure}[htb]\centering \ytableausetup{mathmode,boxsize=1em} \begin{ytableau} 7\\6\\4\\3\\2 \end{ytableau} $\longrightarrow $ \begin{ytableau} 7\\6\\4\\3\\*(blue!50)1 & *(red!30)2 \end{ytableau} $ \longrightarrow$ \begin{ytableau} 7\\6\\4\\*(blue!50)2 & *(red!30)3\\1 & 2 \end{ytableau} $ \longrightarrow$ \begin{ytableau} 7\\*(blue!50)6\\4 & *(red!30)6\\2 & 3\\1 & 2 \end{ytableau} \caption{Establishing that $\iota(\framebox{621} \hspace{1mm} \framebox{76432})=\framebox{76421}\hspace{1mm}\framebox{632}$ by column-inserting 1,2, and 6 into the single-columned tableau with reading word $76432$. Blue boxes show the entries being inserted whereas red boxes contain the entries bumped.}\label{fig:iota via column insertion} \end{figure} In each intermediate step of this column insertion procedure, the number $a_i$ being inserted into the current tableau bumps a distinct element from $\{b_1,\dots, b_q\}$. Furthermore this bumped entry is guaranteed to be strictly greater than the entries in the second column in the current tableau. Therefore, the insertion tableau is completely determined by the entries that get bumped. More precisely, for $i$ from $p$ down to $1$, define the integer ${\sf m}(i)$ recursively as follows. We define ${\sf m}(p)$ to be the largest integer $j$ such that $a_p\leq b_{j}$. Subsequently, for $i=p-1,\dots,1$, define ${\sf m}(i)$ to be the largest integer $j$ such that $j<{\sf m}(i+1) $ and $a_i\leq b_{j}$. Observe that in our Schensted column-insertion procedure, the entry $a_i$ bumps $b_{{\sf m}(i)}$. Therefore, the set of entries that get bumped is $\{b_{{\sf m}(i)}\suchthat 1\leq i\leq p\}$. For the example in Figure~\ref{fig:iota via column insertion}, we have ${\sf m}(3)=5$, ${\sf m}(2)=4$ and ${\sf m}(1)=2$. Therefore the set of entries that get bumped is $\{b_5,b_4,b_2\}=\{2,3,6\}$. \looseness-1 Consider $\crw{\phi(w)}=u_1\cdots u_n$. The word $v\coloneqq v_1\cdots v_n$ obtained by recording the column to which each $u_i$ belongs gives us the weakly increasing arrangement of letters in $w$. Furthermore, for $1\leq i\leq p$ (respectively $1\leq i\leq q$) the letter in $v$ corresponding to the $i$th $2$ (respectively 1) from the left in $\crw{\phi(w)}$ is equal to $a_i$ (respectively $b_i$). Recall that the crystal reflection operator $s_1$ acting on $\phi(w)$ begins by pairing each $2$ in $\crw{\phi(w)}$ to the closest unpaired $1$ to its right. Equivalently, in our current context, a $2$ corresponding to $a_i$ for some $1\leq i\leq p$ gets paired with the $1$ in $\crw{\phi(w)}$ corresponding to $b_{{\sf m}(i)}$. We infer that the unpaired $1$s in $\crw{\phi(w)}$ correspond to those $b_j$ that are not bumped. These are precisely the $b_j$ that determine which $1$s in $\phi(w)$ turn into $2$s in computing $s_1(\phi(w))$. Thus we infer that $s_1(\phi(w))=\phi(\iota(w))$. This establishes the claim in the case $p