\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram} \usepackage{pict2e} \usepackage{multirow,multicol,mathtools} \usepackage{tikz} \usepackage{ytableau} \usepackage[all,cmtip]{xy} \usepackage{young} \newlength\circlesize \setlength\circlesize{.33333333\textwidth} \newcommand*\circled[1]{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=2pt] (char) {#1};}} \setcounter{MaxMatrixCols}{20} %\allowdisplaybreaks[1] \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\PP}{\mathbb{P}} \newcommand{\longsquiggly}{\xymatrix{{}\ar@{~>}[r]&{}}} \newcommand{\SYT}{\mathsf{SYT}} \DeclareMathOperator{\SSYT}{SSYT} \DeclareMathOperator{\ShST}{ShST} \DeclareMathOperator{\std}{std} \DeclareMathOperator{\rectify}{rect} \DeclareMathOperator{\wt}{wt} \DeclareMathOperator{\OG}{OG} \DeclareMathOperator{\Gr}{Gr} \DeclareMathOperator{\row}{row} \DeclareMathOperator{\col}{col} \DeclareMathOperator{\sliderm}{slide} \DeclareMathOperator{\HIGH}{HIGH} \DeclareMathOperator{\GL}{GL} \newcommand{\B}{\mathcal{B}} \newcommand{\defn}[1]{\emph{#1}} \newcommand{\east}[1]{\ensuremath{\xrightarrow{\ #1\ }}} \newcommand{\west}[1]{\ensuremath{\xleftarrow{\ #1\ }}} \newcommand{\north}[1]{\ensuremath{\big \uparrow \!\text{\raisebox{.1ex}{\scriptsize $#1$}}}} \newcommand{\south}[1]{\ensuremath{\big \downarrow \!\text{\raisebox{.1ex}{\scriptsize $#1$}}}} \newcommand{\stepnorth}[2]{\vector(0,1){.92}\put(-.23,.4){\scriptsize$#1$}\put(0,1){#2}} \newcommand{\stepnorthA}[2]{\vector(0,1){.92}\put(.05,.4){\scriptsize$#1$}\put(0,1){#2}} \newcommand{\stepnorthshiftW}[2]{\put(-.08,0){\vector(0,1){.95}\put(-.23,.4){\scriptsize$#1$}}\put(0,1){#2}} \newcommand{\stepnorthshiftE}[2]{\put(.08,0){\vector(0,1){.95}\put(.05,.4){\scriptsize$#1$}}\put(0,1){#2}} \newcommand{\stepsouth}[2]{\vector(0,-1){.92}\put(.05,-.6){\scriptsize$#1$}\put(0,-1){#2}} \newcommand{\stepsouthA}[2]{\vector(0,-1){.92}\put(-.23,-.6){\scriptsize$#1$}\put(0,-1){#2}} \newcommand{\stepsouthshiftE}[2]{\put(.08,0){\vector(0,-1){.92}\put(.05,-.6){\scriptsize$#1$}}\put(0,-1){#2}} \newcommand{\stepsouthshiftW}[2]{\put(-.08,0){\vector(0,-1){.92}\put(-.23,-.6){\scriptsize$#1$}}\put(0,-1){#2}} \newcommand{\stepeast}[2]{\vector(1,0){.92}\put(.4,-.25){\scriptsize$#1$}\put(1,0){#2}} \newcommand{\stepeastA}[2]{\vector(1,0){.92}\put(.4,.05){\scriptsize$#1$}\put(1,0){#2}} \newcommand{\stepeastshiftS}[2]{\put(0,-.08){\vector(1,0){.92}\put(.4,-.25){\scriptsize$#1$}}\put(1,0){#2}} \newcommand{\stepeastshiftN}[2]{\put(0,.08){\vector(1,0){.92}\put(.4,.05){\scriptsize$#1$}}\put(1,0){#2}} \newcommand{\stepwest}[2]{\vector(-1,0){.92}\put(-.5,.05){\scriptsize$#1$}\put(-1,0){#2}} \newcommand{\stepwestA}[2]{\vector(-1,0){.92}\put(-.5,-.25){\scriptsize$#1$}\put(-1,0){#2}} \newcommand{\stepwestshiftN}[2]{\put(0,.08){\vector(-1,0){.92}\put(-.5,.05){\scriptsize$#1$}}\put(-1,0){#2}} \newcommand{\stepwestshiftS}[2]{\put(0,-.08){\vector(-1,0){.92}\put(-.5,-.25){\scriptsize$#1$}}\put(-1,0){#2}} \setlength{\unitlength}{2.4em} %%%%%%%%% 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 %%%1 \author{\firstname{Maria} \lastname{Gillespie}} \address{Department of Mathematics\\ Colorado State University \\ Fort Collins, CO, USA} \email{Maria.Gillespie@colostate.edu} %%% %%%2 \author{\firstname{Jake} \lastname{Levinson}} \address{Department of Mathematics\\ University of Washington \\ Seattle, WA, USA} \email{jlev@uw.edu} %%% %%%3 \author{\firstname{Kevin} \lastname{Purbhoo}} \address{Department of Combinatorics and Optimization\\ University of Waterloo\\ Waterloo, ON, Canada} \email{kpurbhoo@uwaterloo.ca} \thanks{The first author was supported by the NSF MSPRF grant PDRF 1604262. The second author was supported by a Rackham Predoctoral Fellowship and by NSERC grant PDF-502633. The third author was supported by NSERC grant RGPIN-355462.} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Sujet \keywords{Combinatorial crystals, shifted Young tableaux, symmetric function theory, orthogonal Grassmannian.} \subjclass{05E99, 05E05} %%%%% Gestion \DOI{10.5802/alco.110} \datereceived{2018-07-26} \daterevised{2020-01-13} \dateaccepted{2020-01-14} %%%%% Titre et résumé \title [A crystal-like structure on shifted tableaux] {A crystal-like structure on shifted tableaux} \begin{abstract} We introduce coplactic raising and lowering operators $E'_i$, $F'_i$, $E_i$, and $F_i$ on shifted skew semistandard tableaux. We show that the primed operators and unprimed operators each independently form type A Kashiwara crystals (but not Stembridge crystals) on the same underlying set and with the same weight functions. When taken together, the result is a new kind of ``doubled crystal'' structure that recovers the combinatorics of type B Schubert calculus: the highest-weight elements of our crystals are precisely the shifted Littlewood--Richardson tableaux, and their generating functions are the (skew) Schur $Q$-functions. We also give a new criterion for such tableaux to be ballot. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \section{Introduction} A \emph{crystal base} is a set $\B$ along with certain raising and lowering operators $E_i,F_i:\B\to \B\cup \{\varnothing\}$, functions $\varphi_i,\varepsilon_i:\B\to\mathbb{Z}\cup \{-\infty\}$, and a weight map $\wt:\B\to \Lambda$ where $\Lambda$ is a weight lattice of some Lie type. The subscripts $i$ range over an index set $I$ corresponding to the simple roots of the root system of $\Lambda$, and the operators $E_i$ and $F_i$ raise and lower the values of $\varphi_i,\varepsilon_i,\wt$ according to the corresponding root vectors. Crystal bases were first introduced by Kashiwara~\cite{Kashiwara} in the context of the representation theory of the quantized universal enveloping algebra $U_q(\mathfrak{g})$ of a Lie algebra $\mathfrak{g}$ at $q=0$. Since then, their connections to tableau combinatorics, symmetric function theory, and other aspects of representation theory have made crystal operators and crystal bases the subject of much recent study. (See~\cite{Schilling} for an excellent recent overview of crystal base theory.) \subsection{Ordinary tableau crystals}\label{sec:ordinary} The type A crystal base theory can be described entirely in terms of semistandard Young tableaux. Let $\B = \SSYT(\lambda/\mu,n)$ be the set of all semistandard Young tableaux of a given skew shape $\lambda/\mu$ and with entries from $\{1,\ldots,n\}$ for some fixed $n$. If $T\in \B$, let $w$ be its row reading word, formed by reading the rows of $T$ from bottom to top. The functions $E_i$ and $F_i$ on $\B$ are defined directly in terms of the reading word $w$, as follows. First replace each $i$ in $w$ with a right parentheses and each $i+1$ in $w$ with a left parentheses. For instance, if $w=112212112$ and $i=1$, the sequence of brackets is $))(()())($. After maximally pairing off the parentheses, $E_i(T)$ is formed by changing the first unpaired $i+1$ to $i$, and $F_i(T)$ is formed by changing the last unpaired $i$ to $i+1$ (they are defined to be $\varnothing$ if the operation is impossible.) \[ \varnothing\ \xleftarrow{\ E\ }\ \ ))\underline{(()())})\ \ \xleftarrow{\ E\ }\ w = ))\underline{(()())}(\ \ \xrightarrow{\ F\ }\ \ )(\underline{(()())}(\ \ \xrightarrow{\ F\ }\ \ ((\underline{(()())}(\ \ \xrightarrow{\ F\ }\ \varnothing \] The functions $\varphi_i(T)$ and $\varepsilon_i(T)$ can be defined as the smallest $k$ for which $F_i^k(T)=\varnothing$ or $E_i^k(T)=\varnothing$ respectively, and the weight function $\wt(T)$ is simply the weight vector $(m_j)$ where $m_j$ is the number of $j$'s that occur in $T$. In the case where the tableaux are of straight shape, with entries in $\{1,2\}$, the action simplifies to the following natural chain structure: \begin{center} \includegraphics{figures/typeAcrystal2.pdf} \end{center} One important property of the $E_i$ and $F_i$ operations is that they are \emph{coplactic}, that is, they commute with all sequences of jeu de taquin slides. Thus, if we perform the same outwards jeu de taquin slide on the three tableaux above (in the second row, for example), the crystal operators must act in the same way, as shown: \begin{center} \includegraphics{figures/typeAcrystal3.pdf} \end{center} \looseness-1 In this sense the operations $E_i$ and $F_i$ are in fact the \emph{unique} coplactic operators that give the natural connected chain structure on rectified shapes containing only $i$, $i+1$. Notably, Littlewood--Richardson skew tableaux (those that rectify to the highest weight tableau of a given shape) are precisely those for which $E_i(T) = \varnothing$ for all $i$. Finally, it can be shown that the connected components $C$ of \emph{any} tableau crystal have weights \[ \sum_{T\in C}x^{\wt(T)}=s_\nu, \] where $\nu$ is the common rectification shape of every $T \in C$, and $s_\nu$ is the corresponding Schur function. Thus, decomposing the tableau crystal $\B = \SSYT(\lambda/\mu,n)$ into its connected components recovers the Schur expansion of the skew Schur function \[ s_{\lambda/\mu}=\sum_\nu c^{\lambda}_{\mu\nu}s_\nu. \] (See~\cite{Schilling} and~\cite{vanLeeuwen} for more thorough introductions to the above notions of crystals, coplacticity, and jeu de taquin.) \subsection{Shifted tableaux; results of this paper} In contrast to the elegance of crystal operators on ordinary semistandard tableaux, similar structures using \emph{shifted tableaux} have proven more complex. In representation theory, prior work first used semistandard decomposition tableaux~\cite{GJKKK,Serrano}, then shifted tableaux~\cite{AO,CK,GHSP,Hiroshima} to understand the quantum queer superalgebra $\mathfrak{q}(n)$, though the corresponding crystal operators are not direct analogues of the coplactic operators in type A. Shifted tableaux also arise in the context of projective representations of the symmetric group~\cite{Stembridge}, and in Schubert calculus in types B and C~\cite{Pragacz}, pertaining to the Schur P polynomials~\cite{Cho, Shimozono}. Nevertheless, representation-theoretic considerations are not the sole reason to study shifted tableaux. The coplactic structure on these tableaux extends the dual equivalence relation on standard tableaux, which plays a key role in the Littlewood--Richardson rule in Schubert calculus. In this paper, motivated by a related geometric problem (see Section~\ref{sec:applications}), we give an explicit description of a coplactic, crystal-like structure on the set of shifted tableaux. This structure is non-isomorphic to the structures described above, notably to $\mathfrak{q}(n)$ crystals, though both structures share many properties. A key enumerative difference is that the crystals described in this paper have as characters the Schur Q polynomials, whereas the representation-theoretic crystals described above have the \emph{dual} characters, the Schur P polynomials. For ``straight'' (non-skew) shifted tableaux on the alphabet $\{1',1,2',2\}$, there is a natural organization of the tableaux of a given shape (Figure~\ref{fig:two-row}), similar to the $F_1$ chains shown above for ordinary tableaux. Namely, if the tableau has two rows, the first row may or may not contain a $2'$, giving two ``chains'' linked by the operators $F_1$ and $F_1'$. If instead $\lambda$ has only one row, the tableau cannot contain a $2'$, so there is only one chain's worth of tableaux. In this case $F_1=F_1'$. \begin{figure}[htb]\centering \includegraphics[width=.9\linewidth]{figures/two-row2.pdf} \vspace{1cm} \includegraphics[width=.85\linewidth]{figures/one-row2.pdf} \caption{\label{fig:two-row}The crystals of the form $\ShST(\lambda,2)$ are ``two-row'' and ``one-row'' diagrams, organizing the tableaux into ``doubled'' crystals. \emph{Above}: the tableaux of shapes $(4,1)$ and $(3)$. Wherever an arrow is missing, the corresponding operator is not defined. Reversing the arrows gives the partial inverses $E_1$ and $E_1'$.} \end{figure} As is the case with ordinary jeu de taquin, the uniqueness of shifted rectification (and more precisely, Haiman's theory of shifted dual equivalence, see~\cite{Haiman}) implies that these definitions uniquely extend to coplactic operators on all shifted skew tableaux, giving such tableaux a crystal-like structure. However, a direct description that does not rely on performing shifted jeu de taquin --- analogous to the pairing-parentheses description of $E$ and $F$ on ordinary tableaux --- is far from obvious. The main purpose of this paper is to exhibit a simple combinatorial description --- depending only on a tableau's reading word --- of the coplactic operators $E_i,E_i',F_i,F_i'$. (The combinatorial definitions require new notation which will be developed in later sections; see Definitions~\ref{def:primed-operators} and~\ref{def:F}.) \looseness-1 Our main results are as follows. Let $\lambda\mk/\Mk\mu$ be a shifted skew shape and let~$\ShST\mk(\lambda\mk/\mk\mk\mu,\mk n)$ be the set of shifted semistandard tableaux on the alphabet $\{1' < 1 < 2' < 2 < \cdots < n' < n\}.$ \begin{theorem}\label{thm:main} Let $F_i,F'_i$ \textup{(}$i = 1, \ldots, n-1$\textup{)} on $\ShST(\lambda/\mu,n)$ be the lowering operators defined in Definitions~\ref{def:F} and~\ref{def:primed-operators} respectively, with partial inverse \textup{(}raising\textup{)} operators $E_i, E'_i$. Then these operators have the following properties: \begin{enumerate}[label={(\roman*)}] \item %[(i)] The tableaux $E_i(T)$, $F_i(T)$ are computed by transforming certain \emph{critical substrings} \textup{(}see Definition~\ref{def:F}\textup{)} in the reading word of $T$. \item %[(ii)] They are coplactic for shifted jeu de taquin. \item %[(iii)] The highest-weight elements \textup{(}those for which $E_i(T) = E_i'(T) = \varnothing$ for all $i$\textup{)} are precisely the type B Littlewood--Richardson tableaux. \item %[(iv)] Let $\B$ be the induced graph on $\ShST(\lambda/\mu,n)$. Then each connected component of $\B$ has a \emph{unique} highest-weight element. \end{enumerate} \end{theorem} Consequently, decomposing $\ShST(\lambda/\mu,n)$ into its connected components yields an isomorphism of crystals \[ \ShST(\lambda/\mu,n)\ \cong\ \bigsqcup_\nu \ShST(\nu,n)^{f_{\nu,\mu}^\lambda}, \] where $f_{\nu,\mu}^\lambda$ is the coefficient of the Schur $Q$-function $Q_\nu$ in the expansion of the skew Schur $Q$-function $Q_{\lambda/\mu}$. Taking generating functions (weighting a vertex of weight $\gamma$ by $2^{\#\{i:\gamma_i\neq 0\}}$) recovers the skew type B Littlewood--Richardson rule, \[ Q_{\lambda/\mu}(x_1, \ldots, x_n) = \sum_\nu f_{\nu,\mu}^\lambda Q_\nu(x_1, \ldots, x_n). \] The crystal structure also gives an automatic proof of symmetry for $Q_\lambda$ (Corollary~\ref{cor:symmetry-schurQ}). Despite these connections to the type B Littlewood--Richardson rule, our crystal is not a type B crystal. Instead, it has the following ``doubled'' type A structure, based on considering the actions of the primed and unprimed operators separately. \begin{theorem}\label{thm:main-doubled-typeA} The operators $F_i,E_i,F'_i,E'_i$ commute whenever compositions are defined. Moreover, $F_i,E_i$ and $F'_i,E'_i$ independently satisfy the type A Kashiwara crystal axioms, using the same auxiliary functions $\varepsilon_i,\varphi_i,\wt$ on $\ShST(\lambda/\mu,n)$. \end{theorem} \begin{rema} The two Kashiwara crystals generated by the $F_i,E_i$ or the $F_i',E_i'$ operators do not satisfy the Stembridge axioms for type A, and therefore are not crystals in the sense of the representation theory of $U_q(\mathfrak{sl}_n)$. In particular, they are not \emph{seminormal}: the auxiliary functions $\varepsilon_i$ and $\varphi_i$ do not measure the distances to the ends of an $F_i$-chain, but rather the \emph{total} distance to the end of a \textup{(}possibly two-row\textup{)} $F_i$/$F_i'$ chain, as in Figure~\ref{fig:two-row}. \end{rema} While the crystals discussed in this paper are not Stembridge crystals, they are uniquely determined by a small list of axioms analogous to the Stembridge axioms~\cite{Stembridge-typeA}. These are discussed at length in a companion paper by the first two authors~\cite{GL-axioms}. \subsubsection{Lattice walks and critical strings} The key construction underlying the definitions of $E_i, F_i$ is to associate, to each word $w$ in the alphabet $\{i',i,i{+}1',i{+}1\}$, a first-quadrant \emph{lattice walk}, beginning at the origin. See Figure~\ref{fig:lattice-walk-intro} for an example. This walk determines the rectification shape of $w$: \begin{theorem} The length and the coordinates of the endpoint of the lattice walk of a word $w$ in the alphabet $\{i',i,i{+}1',i{+}1\}$ determine the shape and weight of $\rectify(w)$. \end{theorem} The walk also encodes a variety of other information about $w$ in a convenient way (precise statements are given in Corollary~\ref{cor:initial-subwords-dual} and Lemma~\ref{lem:circling}). As an additional corollary, we obtain a new criterion for a word to be \defn{ballot}, that is, for $\rectify(w)$ to be a type B Littlewood--Richardson tableau, having shape equal to its weight. This characterization in terms of the lattice walk differs from existing characterizations of ballot words (see~\cite{Stembridge}) in that it only requires reading through $w$ once, rather than twice (backwards-and-forwards). We also say a word is \defn{anti-ballot} if its rectification shape is equal to the vector obtained by reversing the coordinates of the weight vector. \begin{theorem} \label{thm:lattice-walk-main} Let $w$ be a word in the alphabet $\{1',1, \ldots, n',n\}$. Then $w$ is ballot if and only if each of its lattice walks (for $i=1, \ldots, n-1$) ends on the $x$-axis; it is anti-ballot if and only if each lattice walk ends on the $y$-axis. \end{theorem} \begin{figure}[htb]\centering \begin{tabular}{cc} \setlength{\unitlength}{3em} \ \ \begin{picture}(5,3)(0,0) \multiput(0,0)(0,0.2){16}{\line(0,1){0.1}} \multiput(0,0)(0.2,0){17}{\line(1,0){0.1}} \put(0,1.2){\circle*{0.1}} \put(0,1.2){\vector(0,1){.7}\vector(1,0){.7}} \put(-0.265,1.95){\small{$2$,$2'$}} \put(0.4,1.3){\small{$1$,$1'$}} % \put(1.4,0){\circle*{0.1}} \put(1.4,0){\vector(0,1){.7}\vector(1,0){.7}} \put(1.5,0.6){\small{2,2'}} \put(2.0,0.1){\small{1,1'}}% % \put(2.8,2.2){\circle*{0.1}} \put(2.8,2.2){\vector(0,1){.7}\vector(1,0){.7}} \put(2.8,2.2){\vector(0,-1){.7}} \put(2.8,2.2){\vector(-1,0){.7}} \put(2.7,2.95){\small{$2$}} \put(3.5,2.1){\small{$1'$}} \put(2.7,1.2){\small{$1$}} \put(1.85,2.1){\small{$2'$}} \end{picture} & \ \ \begin{picture}(3,3)(0,0) \setlength{\unitlength}{3em} \stepnorth{2}{% \stepeast{1}{% \stepeast{1'}{% \stepsouthshiftW{1}{% \stepnorthA{2'}{% \stepnorthA{2}{% \stepwestshiftS{2'}{% \stepeastA{1'}{% \stepeastA{1'}{% }}}}}}}}} \put(0,0){\circle*{0.15}} \put(3,2){\circle{0.15}} \multiput(0,0)(0,0.2){15}{\line(0,1){0.1}} \multiput(0,-0.02)(0.2,0){15}{\line(1,0){0.1}} \end{picture} \end{tabular} \caption{The \emph{lattice walk} of a word $w = w_1 w_2 \cdots w_n \in \{1', 1, 2', 2\}^n$. In the interior of the first quadrant, each letter corresponds to a cardinal direction. Along the axes, primed and unprimed letters behave the same way. \emph{Right:} The walk for $w=211'12'22'1'1'$ ends at the point $(3,2)$.\label{fig:lattice-walk-intro}} \end{figure} The lattice walk is similar to the bracketing rule for the ordinary crystal operators: the arrows that occur far from the $x$- or $y$-axis ``cancel'' in opposite pairs, and the transformation is done on the remaining subword. In particular, the operators $E_i,F_i$ are defined in terms of transforming \emph{critical substrings} of $w$: certain specific types of substring, which are required to occur when the lattice walk passes close to either the $x$- or $y$-axis. \subsection{Applications and future work} \label{sec:applications} The results in this paper were developed for the purpose of understanding the topology of Schubert curves in the odd orthogonal Grassmannian $\OG(n,2n+1)$. A Schubert curve is an algebraic curve, defined over $\RR$ as an intersection of Schubert varieties relative to certain special flags. Every Schubert curve comes with a branched covering map to $\PP^1$. The monodromy of this map over the real locus encodes information about the curve; in particular, it completely determines the topology of real Schubert curves. In prior work \cite{GillespieLevinson}, the first two authors computed the topology of real Schubert curves in the ordinary Grassmannian $\Gr(k,n)$. They showed that each point in the fibre of covering map is encoded by a tableau, and the monodromy is described by a coplactic operation on these tableaux, which can be written in terms of the usual crystal operators. The development of the operators $F_i,F'_i,E_i,E'_i$ in this paper was motivated by the analogous geometric question in the orthogonal Grassmannian. In a subsequent paper~\cite{GLP} we show that our operators can be used to define a combinatorial algorithm for computing the monodromy of this covering map in type B. Notably, the coplactic property (which distinguishes our crystals from the similar $\mathfrak{q}(n)$ crystals) arises directly from the geometry. This application has influenced the choices and conventions that are used in this paper. For example, there are several variations on the definition of shifted tableaux; the class of shifted tableaux that we work with comes naturally from considering the Pieri rule on $\OG (n,2n+1)$. Although this work is largely geared toward this specific geometric application, we believe that this new combinatorial structure on shifted tableaux will also be useful more broadly. \looseness-1 Our crystals also recover the combinatorics of the Schur $Q$-functions, giving new proofs of their symmetry and of the type B Littlewood--Richardson rule. Since this application is not the goal of this paper, our proof of Theorem~\ref{thm:main} (in particular coplacticity of the operators $E,F$) takes advantage of existing theory, and therefore, in reality, these arguments are somewhat circuituous. Nevertheless, it is possible to prove Theorem~\ref{thm:main} in such a way that one obtains a genuinely new, direct proof of the type B Littlewood--Richardson rule, analogous to one of the nicer proofs in type A. More generally, it should be possible to use this crystal structure to find the explicit expansion of a combinatorially defined Schur $Q$-positive symmetric function in terms of Schur $Q$-functions. To this end, the first two authors have found explicit axioms, similar to Stembridge's~\cite{Stembridge-typeA} for crystals of simply-laced root systems~\cite{GL-axioms}. These axioms provide necessary and sufficient local criteria for determining whether or not a doubled crystal structure is isomorphic $\ShST(\nu,n)$. One can thereby show that a generating function is Schur $Q$-positive by introducing operators on the underlying set satisfying these axioms. The analogous method in type A has been applied successfully in~\cite{Morse-Schilling} for certain affine Stanley symmetric functions. \subsection{Structure of the paper} The paper is organized as follows. We set notation in Section~\ref{sec:notation}, then in Section~\ref{sec:primed-ops} we introduce the primed operators $E_i',F_i'$ and prove that they are coplactic. In Section~\ref{sec:walks}, we introduce the lattice walk and prove Theorem~\ref{thm:lattice-walk-main}. In Section~\ref{sec:unprimed-ops}, we define the unprimed operators $E_i,F_i$ on words, show that they are well-defined on tableaux and are coplactic, and complete the proof of Theorem~\ref{thm:main}. In Section~\ref{sec:crystal}, we study the joint crystal structure determined by the primed and unprimed operators and prove Theorem~\ref{thm:main-doubled-typeA}. Finally, in Section~\ref{sec:characters}, we prove the statements about the Schur $Q$-functions. %\subsection{Acknowledgments} \section{Background and Notation}\label{sec:notation} \subsection{Strings and words} Let $w = w_1w_2 \dots w_n$ be a string in symbols\break $\{1',1,2',2,3',3,\ldots\}$. We will normally assume that the first occurrence of $\{i,i'\}$ in $w$ is $i$, for each $i\in \{1,2,3,\ldots\}$. Informally, we adopt the convention that the first $i$ can be treated as $i'$ for the purposes of any rule we state, and if any operation produces a string where the first symbol among $\{i,i'\}$ is $i'$, then we will implicitly change it to $i$. We make this rigorous as follows. \begin{defi} Let $w$ be a string in symbols $\{1',1,2',2,3',3,\ldots\}$. The \emph{first $i$ or $i'$} of $w$ is the leftmost entry which is either equal to $i$ or $i'$. The \emph{canonical form} of $w$ is the string formed by replacing the first $i$ or $i'$ (if it exists) with $i$ for all $i\in \{1,2,3,\ldots\}$. We say two strings $w$ and $v$ are \emph{equivalent} if they have the same canonical form; note that this is an equivalence relation. \end{defi} \begin{defi} A \emph{word} is an equivalence class $\hat{w}$ of the strings $v$ equivalent to $w$. If $w$ is in canonical form, we say that $w$ is the \emph{canonical representative} of the word $\hat{w}$. We often call the other words in $\hat{w}$ \emph{representatives} of $\hat{w}$ or of $w$. The \emph{weight} of $w$ is the vector $\wt (w) = (n_1, n_2, \ldots ),$ where $n_i$ is the total number of $(i)$s and $(i')$s in $w$. \end{defi} \begin{exam} The canonical form of the word $1'1'2'112'$ is $11'2112'$. The set of all representatives of $11'2112'$ is $\{1'1'2'112',11'2'112',1'1'2112',11'2112'\}$. Note that the word $11'1$ only has two distinct representatives instead of four. \end{exam} Given an operator $A:T\to S$ defined on some subset $T\subseteq S$, we will say $A$ is a \emph{partial operator} on $S$, and write $A : S \to S$. We write $A(s)=\varnothing$ when $A$ is not defined on $s$ (\ie $s\not\in T$). Our raising and lowering operators will be partial operators on words. \subsection{Shifted tableaux and jeu de taquin} Recall that a \emph{strict partition} is a strictly-decreasing sequence of positive integers, $\lambda=(\lambda_1 > \cdots > \lambda_k)$. We say that $|\lambda|=\sum \lambda_i$ is the \emph{size} of $\lambda$, and the entries $\lambda_i$ are the \emph{parts} of $\lambda$. The \emph{shifted Young diagram} of $\lambda$ is the partial grid of squares in which the $i$-th row contains $\lambda_i$ boxes and is shifted to the right $i$ steps, as in the example shown below. A \emph{(shifted) skew shape} is a difference $\lambda/\mu$ of two partition diagrams, formed by removing the squares of $\mu$ from the diagram of $\lambda$, if $\mu$ is contained in $\lambda$. \begin{center} \includegraphics{figures/shifted-partition.pdf} \hspace{1cm} \includegraphics{figures/shifted-partition3.pdf} \end{center} A \emph{shifted semistandard Young tableau} is a filling of the boxes with entries from the alphabet $\{1'<1<2'<2<3'<3<\cdots \}$ such that the entries are weakly increasing down columns and across rows, and such that primed entries can only repeat in columns, and unprimed only in rows. The \emph{(row) reading word} of such a tableau is the word formed by concatenating the rows from bottom to top (in the example below, the reading word is $3111'21'12'$). The \emph{weight} of $T$ is the vector $\wt (T) = (n_1, n_2, \ldots)$, where $n_i$ is the total number of $(i)$s and $(i')$s in $T$. \begin{center} \includegraphics{figures/shifted-semistandard.pdf} \end{center} The notion of \emph{jeu de taquin} for shifted tableaux is similar to jeu de taquin for usual tableaux: an \emph{inner jeu de taquin slide} is the process of choosing an empty inner corner of the skew tableau and choosing either the entry to its right or below it to slide into the empty square so as to keep the tableau semistandard, then repeating the process with the new empty square, and so on until the empty square is an outer corner. An \emph{outer jeu de taquin slide} is the reverse process, starting with an outer corner and sliding boxes outwards. There are two exceptions to the sliding rules: if an outer slide moves an $i$ down into the diagonal and then another $i$ to the right on top of it, that $i$ becomes primed (and vice versa for the corresponding inner slide), as shown below. \begin{center} \includegraphics{figures/special-slide.pdf} \end{center} Similarly, if an outer slide moves an $i$ down into the diagonal, then moves an $i'$ to the right on top of it, the $i$ becomes primed. \begin{center} \includegraphics{figures/special-slide-Worley.pdf} \end{center} We write $\rectify(T)$ or $\rectify(w)$ to denote the jeu de taquin \emph{rectification} of any shifted semistandard tableau $T$ with reading word $w$; this is well-defined in~\cite{Sagan,Worley}. We say that $T$ is \emph{Littlewood--Richardson}, and $w$ is \emph{ballot}, if for every $i$, the $i$-th row of $\rectify(T)$ consists entirely of $(i)$s. \begin{defi} Let $T$ be a semistandard shifted skew tableau with reading word $w$. We say that $T$ is in \emph{canonical form} if $w$ is, and use the same conventions for tableaux as for words: a tableau $T$ in canonical form is identified with the set of \emph{representatives} of $T$, tableaux formed by possibly priming the first $i$ in reading order for each $i$; two tableaux are \emph{equivalent} if they have the same shape and reading their words are equivalent; the set of all representatives of $T$ is the equivalence class of $T$, denoted $\hat T$. \end{defi} We note that switching representatives commutes with jeu de taquin, so instead of working with equivalence classes of tableaux, we will normally assume our tableaux are in canonical form. Shifted semistandard tableaux are used to define the Schur $Q$-functions. Equivalence classes of tableaux, on the other hand, arise in formulas involving multiplication of Schur $P$-functions. We elaborate in Section~\ref{sec:characters}. Our motivation for studying crystal strutures is connected to the latter, and so we will be mainly concerned with equivalence classes of tableaux. The main property that we wish our operators $E_i$, $E'_i$, $F_i$, $F'_i$ to satisfy is \emph{coplacticity}. \begin{defi} An operation on canonical shifted tableaux (or on their reading words) is \emph{coplactic} if it commutes with all shifted jeu de taquin slides. \end{defi} \begin{defi} The \emph{standardization} of a word $w$ is the word $\std(w)$ formed by replacing the letters in order with $1,2,\ldots,n$ from least to greatest, breaking ties by reading order for unprimed entries and by reverse reading order for primed entries. The standardization of a shifted tableau $T$ is the standard shifted tableau $\std(T)$ formed by standardizing its reading word and performing the same changes on the corresponding letters of the tableau. \end{defi} \begin{exam} The standardization of the word $1121'22'1'11$ is the word $348297156$. Note that this is the same as the standardization of every representative of the word, and in general standardization is well-defined independently of the representative. \end{exam} \begin{prop}\label{prop:standardization} A filling $T$ of a shifted skew shape is semistandard if and only if $\std(T)$ is a standard shifted tableau. \end{prop} \begin{proof} The forward direction is clear. For the reverse direction, suppose $\std(T)$ is a standard shifted tableau. We need to check that any two adjacent entries satisfy the semistandard condition. If $x$ is just left of $y$, then $x0$ and there exists a representative $u$ of $w$ in which there is no $2'$ after the last $1$, then $F'(w)$ is obtained by changing the last $1$ to a $2'$ in~$u$. Otherwise $F'(w) = \varnothing$. The word $E'(w)$ is defined similarly with the roles of $1$ and $2'$ reversed: if $\wt(w)_2>0$ and there is no $1$ after the last $2'$ in some representative $u$, change the last $2'$ to a~$1$ in $u$. Otherwise $E'(w) = \varnothing$. \end{prop} \begin{proof} Since $F'$ is the unique operator that preserves standardization and lowers the weight, say from $(a,b)$ to $(a-1,b+1)$, we see from the construction in the proof of Lemma~\ref{lem:unstandardize} that the entry that changes weight is precisely the entry that standardizes to $a$. This is the last $1$ in reading order, and changing it to a $2'$ is the only potential way to preserve standardization. In order for it to do so, it must also be to the right of the last $2'$ in reading order (under any possible representative). The analysis is similar for $E'$. \end{proof} \begin{rema} In Proposition~\ref{prop:explicit-definitions-primed}, if $F'(w)$ is defined then it is in fact defined on the canonical representative. However, this is not the case for $E'$. For instance, if $w=1121'22$ then there is no $2'$ in the canonical form, but in the representative $112'1'22$ the last $2'$ is to the right of the last $1$, and $E'(w)=1111'22$. As another example, if $v=22'11'$, then in canonical form the last $2'$ is to the left of the last $1$, but in the representative $22'1'1'$ it is not as there is no $1$. In this case we have $E'(v)=211'1'$, and the canonical forms of $v$ and $E'(v)$ differ by two letters, not one. \end{rema} This also allows us to describe the action on straight shifted tableaux $T$. \begin{prop} \label{prop:rect-primed-action} If $T$ has one row, $E'(T)$ \textup{(}respectively $F'(T)$\textup{)} is obtained by changing the leftmost $2$ to a $1$ \textup{(}respectively, the rightmost $1$ to a $2$\textup{)}, if possible; otherwise it is $\varnothing$. If $T$ has two rows and its first row contains a $2'$, then $E'(T)$ is obtained by changing the $2'$ to a $1$, and $F'(T) = \varnothing$. If the first row does not contain a $2'$, $E'(T) = \varnothing$ and $F'(T)$ is obtained by changing the rightmost $1$ to a $2'$. \end{prop} \begin{exam} Here are some maximal chains for $F'$: \begin{gather*} 12211' \xrightarrow{F'} 1222'1' \xrightarrow{F'} \varnothing \\ 1111'1' \xrightarrow{F'} 1121'1' \xrightarrow{F'} 1221'1' \xrightarrow{F'} 22211' \xrightarrow{F'} 2222'1 \xrightarrow{F'} 2222'2' \xrightarrow{F'} \varnothing \end{gather*} \end{exam} We conclude this section with a note on the lengths of chains in the primed operators. The maximal chains for $F'$ will normally have length $1$ (as in the first example above). We get longer chains (as in the second example above) if and only if $\rectify(w)$ has only one row. \begin{prop}\label{lem:maxchains} A maximal chain for $F'$ has length greater than $1$ if and only if $\rectify(w)$ has one row \textup{(}and at least two boxes\textup{)}. Moreover, when $\rectify(w)$ has two rows, $F'(w) = \varnothing$ iff $E'(w) \neq \varnothing$ iff $\rectify(w)$ contains a $2'$ in its first row. \end{prop} \begin{proof} By coplacticity, it suffices to show this for the reading word of a straight shifted tableau. Then we apply the previous Proposition. \end{proof} \section{The lattice walk of a word}\label{sec:walks} \looseness-1 The first step in defining the more involved operators $F(w)$ and $E(w)$ is to associate, to each word $w$, a lattice walk in the first quadrant of the plane. This walk is a sequence \[ P_0(w), P_1(w), \ldots, P_n(w) \] of points in $\NN \times \NN$, starting with $P_0(w) = (0,0)$. We specify the walk by assigning a step to each $w_i$, $i=1, \dots, n$; any choice of representative of $w$ will give the same walk. Each step will be one of the four principal direction vectors: \[ \east{~~} \ =\ (1,0) \qquad \west{~~} \ =\ (-1,0) \qquad \north{} \ =\ (0,1) \qquad \south{} \ =\ (0,-1)\,. \] $P_i(w)$ is (as usual) the sum of the steps assigned to $w_1, \dots, w_i$. We define the walk inductively, as follows. Suppose $i >0$, and we have assigned steps to $w_1, \dots, w_{i-1}$, so $P_0(w), \dots,P_{i-1}(w)$ have been defined. Write $P_{i-1}(w) = (x_{i-1},y_{i-1})$. We assign the step to $w_i$ according to Figure~\ref{fig:directions}, with two cases based on whether or not the step starts on one of the $x$ or $y$ axes. See Figure~\ref{fig:lattice-walk-intro}. We will generally write the label each step of the walk by the letter $w_i$, so as to represent both the word and its walk on the same diagram. \begin{figure}[htb]\centering \begin{tabular}{|c|cccc|} \hline $x_iy_i=0$ & \east{1'} & \east{1} & \north{2'} & \north{2} \\[.8ex] \hline $x_iy_i\neq0$ &\east{1'} & \south{1} & \west{2'} & \north{2} \\[.8ex] \hline \end{tabular} \caption{\label{fig:directions} The directions assigned to each of the letters $w_i=1'$, $1$, $2'$, or $2$ according to whether the location of the walk just before $w_i$ starts on the axes ($x_iy_i=0$) or not.} \end{figure} \begin{exam} \label{ex:walk} Here is the walk for $w = 1221'1'111'1'2'2222'2'11'1$. \begin{center} \begin{picture}(5,4.8)(0,-0.2) %\begin{picture}(5,4.2)(0,0) \multiput(0,0)(0,0.2){22}{\line(0,1){0.1}} \multiput(0,0)(0.2,0){27}{\line(1,0){0.1}} \put(0,0){\circle*{0.13}} \put(4,2){\circle{0.13}} \stepeast{1}{% \stepnorth{2}{% \stepnorth{2}{% \stepeast{1'}{% \stepeast{1'}{% \stepsouth{1}{% \stepsouth{1}{% \stepeast{1'}{% \stepeast{1'}{% \stepnorth{2'}{% \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepwest{2'}{% \stepwest{2'}{% \stepsouth{1}{% \stepeast{1'}{% \stepsouth{1}{% }}}}}}}}}}}}}}}}}} \end{picture} \end{center} \end{exam} \begin{prop} The walk for $\eta(w)$ is the reflection of the walk for $w$ over the line $y=x$. \end{prop} \begin{proof} This is clear by the symmetry of the lattice walk operations. \end{proof} The key property of this lattice walk is that its length, $n$, and its endpoint, $P_n(w) = (x_n, y_n)$, tell us almost everything about the rectification tableau $\rectify(w)$. Note that $\rectify(w)$ is a straight shifted tableau with at most two rows. \begin{theorem}\label{thm:rectification} The shape of $\rectify(w)$ is $\lambda = (\lambda_1, \lambda_2)$, where \begin{align*} \lambda_1 &= \tfrac{1}{2}(n+x_n+y_n) = \#\big\{\ \north{} \text{ and/or } \east{} \text{ steps in the walk\ }\big\}, \\ \lambda_2 &= \tfrac{1}{2}(n-x_n-y_n) = \#\big\{\west{} \text{ and/or } \south{} \text{ steps in the walk\ }\big\}, \end{align*} Moreover, there are $\tfrac{1}{2}(n+x_n-y_n)$ $(1)$s in the first row; there is at most one $2'$, and the remaining entries in the tableau are all $(2)$s. \end{theorem} \begin{coro} The shape of $\rectify(w)$ has only one row iff all steps in the walk are $\east{~}$ or $\north{}$. \end{coro} As an additional corollary, we obtain a new criterion for ballotness: \begin{coro} \label{cor:ballot-walk-criterion} A word $w$ is ballot if and only if for all $i$, the lattice walk of the subword $w_i$ consisting of the letters $i,i',i+1,i+1'$ has $y_n = 0$, that is, ends on the $x$-axis. Similarly $w$ is anti-ballot \textup{(}\ie $\eta(w)$ is a ballot word\textup{)} if and only if $x_n = 0$ for all $i$. \end{coro} \begin{proof} It is well-known that a word is ballot if and only if each subword $w_i$ is ballot (see~\cite{Stembridge}, for instance). By definition, $w_i$ is ballot if and only if the first row of $\rectify(w_i)$ consists only of $(1)$s (after replacing $i',i \leadsto 1',1$ and $i+1',(i+1) \leadsto 2',2$). By Theorem~\ref{thm:rectification}, this says $\tfrac{1}{2}(n+x_n-y_n) = \tfrac{1}{2}(n+x_n+y_n)$, that is, $y_n=0$. \end{proof} Our proof uses the rules of shifted Knuth equivalence, as developed in~\cite{Sagan} and~\cite{Worley}. Using our primed notation, their shifted Knuth moves are as follows. \begin{defi} Two words $w$ and $v$ are \emph{shifted Knuth equivalent} if they differ by a sequence of elementary shifted Knuth moves on adjacent letters, consisting of either: \begin{itemize} \item $bac\leftrightarrow bca$ where under the standardization ordering we have $a0$. If $x=0$, then $a=2'$ contributes $\north{}$ in both cases; if instead $x>0$, then in both cases $a=2'$ occurs off the axes, hence gives $\west{}$. \end{enonce*} \begin{enonce*}[remark]{Case 3} $\{a,c\} = \{1,2\}$ or $\{1',2'\}$. By applying $\eta$, it suffices to consider $\{1,2\}$. If the pivot is on the left, then it must be $2'$ or $2$, so again $y>0$ and the reasoning is exactly as in Case 2 but for $a=1$ rather than $a=2'$. If the pivot is on the right, then it is $b=1$ or $2'$, and we show that the location of the walk just before $b$ is unchanged under $acb\leftrightarrow cab$. If $y>0$, the arrow $a=1$ is $\south{}$ in both cases. If instead $y=0$ (and so $x \ne 0$ since the location is not the origin), the individual steps change; see Figure~\ref{fig:knuthmove-switch12} for the remaining possibilities. \begin{figure}[htb]\centering %\begin{picture}(1,1)(0,0.4) \begin{picture}(1,1.5)(0,0.0) \multiput(-0.2,0)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(1,0){\circle{0.2}} \stepnorth{2}{% \stepsouthshiftE{1}{% \stepeast{1}}} \end{picture} $\longsquiggly$ %\begin{picture}(1,1)(0,0.4) \begin{picture}(1,1.5)(0,0.0) \multiput(-0.2,0)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(1,0){\circle{0.2}} \stepeast{1}{% \stepnorthshiftW{2}{% \stepsouth{1}}} \end{picture} \hspace{2cm} %\begin{picture}(1,1)(0,0.4) \begin{picture}(1,1.5)(0,0.0) \multiput(-0.2,0)(0.2,0){6}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(0,1){\circle{0.2}} \stepnorthshiftW{2}{% \stepsouth{\ 1,2'}{% \put(0.1,0){\rlap{\stepnorth{}}} }} \end{picture} $\longsquiggly$ %\begin{picture}(1,1)(0,0.4) \begin{picture}(1,1.5)(0,0.0) \multiput(-0.2,0)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(0,1){\circle{0.2}} \stepeast{1}{% \stepnorth{2}{% \stepwest{2'}}} \end{picture} \caption{The unique Knuth moves where switching a $1,2$ pair alters the individual steps of the walk. In both cases, the walk begins with $x>0, y=0$. \emph{Left}: The move $211 \leftrightarrow 121$. \emph{Right}: The move $212' \leftrightarrow 122'$.} \label{fig:knuthmove-switch12} \end{figure} \end{enonce*} \begin{enonce*}[remark]{Case 4} $\{a,c\} = \{1,2'\}$. The standardization order forces the pivot to be on the right, and it must be $b = 1$ or $2'$. By applying $\eta$, we may assume $b=1$. If $x>1$ and $y>1$, both $a,c$ steps occur off the axes, so we're done; otherwise the path changes in five different ways depending on whether $x,y$ are variously $0$ or $1$ (see Figure~\ref{fig:knuthmove-switch12'}).\qedhere \end{enonce*} \end{proof} \begin{figure}[htb]\centering $x=0, y\geq 1$: \hspace{0.1cm} \begin{picture}(1,1)(0,0.4) \multiput(0,-0.2)(0,0.2){7}{\line(0,1){0.1}} \put(0,0){\circle*{0.2}} \put(1,0){\circle{0.2}} \put(0.20,0.23){\scriptsize{$1,2',1$}} \put(0,-0.1){\stepeast{}{% \put(0,0.1){\stepwest{}{% \put(0,0.1){\stepeast{}}}}}} \end{picture} \hspace{0.3cm}$\longsquiggly$\hspace{0.3cm} \begin{picture}(1,1)(0,0.4) \multiput(-0.03,-0.2)(0,0.2){7}{\line(0,1){0.1}} \put(0,0){\circle*{0.2}} \put(1,0){\circle{0.2}} \put(-0.3,0.4){\scriptsize{2'}} \stepnorth{}{% \stepeast{1}{% \put(0,0){\stepsouth{1}}% }} \end{picture} \vspace{1cm} \\ $x\geq 1, y=0$: \hspace{0.1cm} \begin{picture}(1,1)(0,0.4) \multiput(-0.2,0)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(1,0){\circle{0.2}} \stepeast{1}{% \stepnorthshiftW{2'}{% \stepsouth{1}}} \end{picture} \hspace{0.5cm}$\longsquiggly$\hspace{0.5cm} \begin{picture}(1,1)(0,0.4) \multiput(-0.2,0)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(1,0){\circle{0.2}} \stepnorth{2'}{% \stepsouthshiftE{1}{% \stepeast{1}}} \end{picture} \vspace{1cm} \\ $x=1,y>1$: \hspace{0.2cm} \begin{picture}(1,1)(-1,-0.6) \multiput(-1,-1.2)(0,0.2){7}{\line(0,1){0.1}} \put(0,0){\circle*{0.2}} \put(0,-1){\circle{0.2}} \stepsouth{1}{% \stepwestshiftN{2'}{% \stepeast{1}}} \end{picture} \hspace{0.3cm}$\longsquiggly$\hspace{0.3cm} \begin{picture}(1,1)(-1,-0.6) \multiput(-1,-1.2)(0,0.2){7}{\line(0,1){0.1}} \put(0,0){\circle*{0.2}} \put(0,-1){\circle{0.2}} \stepwest{2'}{% \stepeastshiftS{1}{% \rlap{\stepsouth{1}} }} \end{picture} \vspace{1cm} \\ $x>1,y=1$: \hspace{0.2cm} \begin{picture}(1,1)(0,-0.6) \multiput(-0.3,-1)(0.2,0){7}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(0,-1){\circle{0.2}} \put(-0.1,0){\stepsouth{}{% \put(0.1,0){\stepnorth{}{% \put(0.1,0){\rlap{\stepsouth{1,2',1}}}}}}} \end{picture} \hspace{0.1cm}$\longsquiggly$\hspace{1cm} \begin{picture}(1,1)(0,-0.6) \multiput(-1.2,-1)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(0,-1){\circle{0.2}} \stepwest{2'}{% \stepsouth{1}{% \stepeast{1}}} \end{picture} \vspace{1cm} \\ \hspace{0.5cm} $(x,y) = (1,1)$:\hspace{1.2cm} \begin{picture}(1,1)(0,-0.6) \multiput(-1,-1.2)(0,0.2){7}{\line(0,1){0.1}} \multiput(-1.2,-1)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(0,-1){\circle{0.2}} \put(-0.1,0){\stepsouth{}{% \put(0.1,0){\stepnorth{}{% \put(0.1,0){\rlap{\stepsouth{1,2',1}}}}}}} \end{picture} \hspace{0.1cm}$\longsquiggly$\hspace{1cm} \begin{picture}(1,1)(0,-0.6) \multiput(-1,-1.2)(0,0.2){7}{\line(0,1){0.1}} \multiput(-1.2,-1)(0.2,0){8}{\line(1,0){0.1}} \put(0,0){\circle*{0.2}} \put(0,-1){\circle{0.2}} \stepwest{2'}{% \stepeastshiftS{1}{% \rlap{\stepsouth{1}}}} \end{picture} \caption{Effects\vrule height 15pt depth 0pt width0pt\ on the walk of the Knuth move $12'1 \leftrightarrow 2'11$. There are five cases in which the individual steps change; the starting point $\bullet$ must have at least one coordinate equal to $1$ or $0$ (but is assumed not be $(0,0)$).} \label{fig:knuthmove-switch12'} \end{figure} \begin{proof}[Proof of Theorem~\ref{thm:rectification}] By Proposition~\ref{prop:walks}, it suffices to check the statement for words of straight shifted tableaux. In particular, $w$ has the form $2^a 1^a w'$, where $w' = 1^b (2')2^*$, and the $2'$ is optional unless $b=0$, in which case it is required. Let $c$ be the number of $2'/2$s in this suffix, so that $n = 2a + b + c$ and the shape of the tableau is $(a+b+c,a)$. Unwinding the desired statements, we wish to show that the endpoint is $(b,c)$. If $a=0$, the walk simply moves $b$ steps right and $c$ steps up. If $a>0$, the $2^a1^a$ prefix consists of $a$ steps $\north{}$, one step $\east{}$ and $a-1$ steps $\south{}$, ending at $(1,1)$. Then, if $b>0$, the walk moves down and along the $x$-axis to $(b,0)$, then up for the remaining $2'$ and/or $2$ steps to $(b,c)$. If instead $b=0$, the suffix is just $w' = 2'2^{c-1}$, so the walk moves left and up the $y$-axis, ending at $(0,c)$. In all cases the endpoint is $(b,c)$ as desired. \end{proof} Finally, we compute the effects of $E',F'$ on the endpoint of the lattice walk. \begin{prop} \label{prop:primed-lattice-endpoint} Applying $F'$ changes precisely one step of the lattice walk, either from $\east{}$ to $\north{}$ or from $\south{}$ to $\west{}$. Consequently, it shifts the endpoint by $(-1,+1)$. For $E'$, the action is reversed. \end{prop} \begin{proof} Since $F'$ and $E'$ are partial inverses, it suffices to prove the statement about $F'$. Consider a representative of $w$ in which the last $1$ is to the right of the last $2'$, and suppose this $1$ is the $i$-th letter, $w_i$. Then by Proposition~\ref{prop:explicit-definitions-primed}, $F'(w)$ is formed by changing $w_i$ to $2'$ and canonicalizing. The first $i-1$ steps of the walk are unchanged (since canonicalization does not change the direction of any arrow and nothing else changed), and the arrow $w_i$ changes as stated depending on whether it is on an axis. Finally, because $w_i$ is the last $1$ and is to the right of the last $2'$, every letter after $w_i$ is either $1'$ or $2$, so the later steps' directions are unchanged as well. \end{proof} Finally, we show that, despite the special rules governing the axes, the shape of a walk does not change drastically if we shift its start point: \begin{prop}[Bounded error] \label{lem:bounded-error} Let $w$ be a word; consider the walk for $w$ beginning at an arbitrary starting point $(x_0,y_0)$, not necessarily the origin. \looseness-1 If we shift the start by either $\west{}$ or $\north{}$, then the endpoint also shifts by \emph{either} $\west{}$ or $\north{}$. \looseness-1 Similarly, if we shift the start by $\east{}$ or $\south{}$, the endpoint also shifts by $\emph{either}$ $\east{}$ or~$\south{}$. \end{prop} \begin{proof} \looseness-1 We prove the first statement; the second follows by applying $\eta$. Working inductively, it suffices to show that, for a single letter $a \in \{1',1,2',2\}$, if we shift its starting point by either $\west{}$ or $\north{}$, then its endpoint also shifts by either $\west{}$ or $\north{}$. This is clear if $a = 1'$ or $2$, or if the shift does not move the starting point on or off the axes. We check the other cases. If we shift the starting point of $a$ by $\north{}$ off of the $x$-axis (and we are not on the $y$-axis), we see for both $a = 1,2'$ that the endpoint shifts overall by $\west{}$: \begin{center} \begin{picture}(0,1)(0,0) \put(0,1){\circle{0.2}} \multiput(-0.3,0)(0.2,0){4}{\line(1,0){0.1}} \put(0.45,0.4){$\leadsto$} \stepnorth{2'}{} \end{picture} \hspace{2cm} \begin{picture}(0,0.5)(0,-1) \multiput(-0.3,-1)(0.2,0){4}{\line(1,0){0.1}} \put(-1,0){\circle{0.2}} \stepwest{2'}{} \end{picture} \hspace{2cm} \begin{picture}(0,1)(0,0) \multiput(-0.3,0)(0.2,0){4}{\line(1,0){0.1}} \put(1,0){\circle{0.2}} \put(1.3,0.4){$\leadsto$} \stepeast{1}{} \end{picture} \hspace{2cm} \begin{picture}(0,0.5)(0,-1) \multiput(-0.3,-1)(0.2,0){4}{\line(1,0){0.1}} \put(0,-1){\circle{0.2}} \stepsouth{1}{} \end{picture} \end{center} Similarly, if $a$ moves $\west{}$ onto the $y$-axis (and was not already on the $x$-axis), in both cases $a = 1,2'$ the endpoint shifts (overall) by $\north{}$. \end{proof} \begin{coro} \label{cor:concat-ballot} A concatenation of ballot words is ballot. \end{coro} \begin{proof} Suppose $w_1, w_2$ are ballot, and let $(x_1,0)$, $(x_2,0)$ be the endpoints of their lattice walks. Then, in the lattice walk for $w_1w_2$, the $w_2$ portion begins at $(x_1,0)$ rather than the origin. By Proposition~\ref{lem:bounded-error}, its new endpoint moves $x_1$ steps down and/or right, but clearly can only move right. Thus the endpoint of $w_1w_2$ is at $(x_1+x_2,0)$. \end{proof} %%%%%%%%%%%%%%%% \section{The operators \texorpdfstring{$E$}{E} and \texorpdfstring{$F$}{F}}\label{sec:unprimed-ops} As in the previous section, throughout this section we assume that $w$ is a word consisting only of letters from $\{1',1,2',2\}$, and for simplicity we use the following notation. \begin{defi} Define $E=E_1$, $F=F_1$ and $\eta = \eta_1$. \end{defi} There are several parts to this section: we first define $E$ and $F$ and show that they are partial inverses, then prove the main theorem (that $E$ and $F$ are coplactic) in several steps. We show that the operators preserve semistandardness; we then show that they preserve the dual equivalence class of $T$, and finally that they are coplactic. %%%%%%%%%%%%%%%% \subsection{Critical substrings and definition of \texorpdfstring{$E$}{E} and \texorpdfstring{$F$}{F}}\label{sec:EFdefinition} \begin{defi} If $w$ is a word and $u = w_k w_{k+1} \dots w_l$ is a substring of some representative of $w$, we say $u$ is a \emph{substring} of the word $w$. We say $(x,y) = P_{k-1}(w)$ is the \defn{location} of $u$. \end{defi} \begin{defi} We say that $u$ is an \defn{$F$-critical substring} if certain conditions on $u$ and its location are met. There are five types of $F$-critical substring. Each row of the first table in Figure~\ref{fig:criticals} describes one type, and a transformation that can be performed on that type. % For example, the first row indicates that $u$ is a critical substring of type 1F if $u$ is of the form $1(1')^*2'$ and the location $(x,y)$ satisfies $y=0$ or $y=1,\, x \geq 1$. The ``steps'' column shows, in each case, what the direction of the corresponding steps in the walk must be. This is redundant information, as it can be deduced from the ``substring'' and ``location'' conditions; we include it because it is useful for reference. \end{defi} \begin{figure}[htb]\centering \begin{tabular}{|c|c|c|c|c|} \hline \multirow{2}{*}{Type} & \multicolumn{3}{c|}{Conditions} & \multirow{2}{*}{Transformation} \\ & \multicolumn{1}{c}{Substring}& \multicolumn{1}{c}{Steps} & Location & \\\hline \hline \multirow{2}{*}{1F} & \multirow{2}{*}{$u = 1(1')^*2'$} & \east{1} ~ \east{1'} ~ \north{2'} & $y=0$ & \multirow{2}{*}{$u \to 2'(1')^*2$} \\[.5ex]\cline{3-4} & & \south{1} ~ \east{1'} ~ \north{2'} & $y=1$, $x \geq 1$ & \\[.5ex]\hline \multirow{2}{*}{2F} & \multirow{2}{*}{$u = 1(2)^*1'$} & \east{1} ~ \north{2} ~ \east{1'} & $x = 0$ & \multirow{2}{*}{$u \to 2'(2)^*1$} \\[.5ex]\cline{3-4} && \south{1} ~ \north{2} ~ \east{1'} & $x = 1$, $y \geq 1$ & \\[.5ex]\hline 3F & $u = 1$ & \east{1} & $y = 0$ & $u \to 2$ \\\hline 4F & $u = 1'$ & \east{1'} & $x = 0$ & $u \to 2'$ \\\hline \multirow{2}{*}{5F} & $u = 1$ & \south{1} & \multirow{2}{*}{$x=1$, $y \geq 1$} & \multirow{2}{*}{undefined} \\[.5ex]\cline{2-3} & $u=2'$ & \west{2'} && \\\hline \end{tabular} \vspace{0.5cm} \begin{tabular}{|c|c|c|c|c|} \hline \multirow{2}{*}{Type} & \multicolumn{3}{c|}{Conditions} & \multirow{2}{*}{Transformation} \\ & \multicolumn{1}{c}{Substring}& \multicolumn{1}{c}{Steps} & Location & \\\hline \hline \multirow{2}{*}{1E} & \multirow{2}{*}{$u = 2'(2)^*1$} & \north{2'} ~ \north{2} ~ \east{1} & $x=0$ & \multirow{2}{*}{$u \to 1(2)^*1'$} \\[.5ex]\cline{3-4} & & \west{2'} ~ \north{2} ~ \east{1} & $x=1$, $y \geq 1$ & \\[.5ex]\hline \multirow{2}{*}{2E} & \multirow{2}{*}{$u = 2'(1')^*2$} & \north{2'} ~ \east{1'} ~ \north{2} & $y = 0$ & \multirow{2}{*}{$u \to 1(1')^*2'$} \\[.5ex]\cline{3-4} && \west{2'} ~ \east{1'} ~ \north{2} & $y = 1$, $x \geq 1$ & \\[.5ex]\hline 3E & $u = 2'$ & \north{2'} & $x = 0$ & $u \to 1'$ \\[.5ex]\hline 4E & $u = 2$ & \north{2} & $y = 0$ & $u \to 1$ \\[.5ex]\hline \multirow{2}{*}{5E} & $u = 1$ & \south{1} & \multirow{2}{*}{$y=1$, $x \geq 1$} & \multirow{2}{*}{undefined} \\[.5ex]\cline{2-3} & $u=2'$ & \west{2'} && \\\hline \end{tabular} \caption{\label{fig:criticals} Above, the table of $F$-critical substrings and their transformations. Below, the table of $E$-critical substrings and their transformations. Here $a(b)^*c$ means any string of the form $abb \dots bc$, including $ac$, $abc$, $abbc$, \etc} \end{figure} \begin{rema} All the conditions on the starting location are on the lines $y=0$, $y=1$, $x=0$, or $x=1$. Critical substrings can only occur when the walk touches one of these four lines, which corresponds to the initial subword $w_1w_2 \dots w_{k-1}$ being either ballot, anti-ballot, or close to one of these. (See Figure~\ref{fig:criticals}.) \end{rema} We define (by abuse of notation) the \emph{final} $F$-critical substring $u$ of $w$ as follows: we take $u$ with the highest possible starting index, and take the longest in the case of a tie. If there is still a tie (from different representatives of $w$, see \eg Remark~\ref{rmk:tie-for-final}), we take any such $u$. \begin{defi}\label{def:F} We define the word $F(w)$ as follows. We fix a representative $v$ containing the final critical substring $u$, and transform $u$ (in $v$) according to its type. The resulting word (\ie after canonicalizing) does not depend on the choices, if any, of $u$ or $v$. If the type is 5F, or if $w$ has no $F$-critical substrings, then $F(w)$ is undefined; we write $F(w) = \varnothing$. We then define $E = \eta \circ F \circ \eta$. There is a corresponding notion of $E$-critical substrings, and transformation rules for each, given by the second table in Figure~\ref{fig:criticals}. This table is obtained by applying $\eta$ to every rule in the table for $F$ (swapping $1' \leftrightarrow 2$, $1 \leftrightarrow 2'$, and $x \leftrightarrow y$). \end{defi} \begin{rema} \label{rmk:tie-for-final} There is one case where the final critical substring $u$ has different types in different representatives: if $u$ is the first letter of $w$. In this case $u$ counts as both $1$ (3F) and $1'$ (4F). In this case, both outputs represent the same word $F(w)$. \end{rema} \begin{rema} By definition, the critical substring is selected from among all possible representatives of $w$. In general, we cannot use an arbitrary representative. For example, if $w = 212$, the final $E$-critical substring is $2'1'2$ (type 2E) from a different representative, giving $E(w) = 11'2' = 11'2$ (after canonicalizing). By contrast, the only $E$-critical substring of the canonical form of $w$ is the first letter $2$ (type 4E), which (incorrectly) transforms to $112$, which is not equivalent to $11'2$. \end{rema} \begin{rema} It is not hard to show that the final $F$-critical substring or $E$-critical substring may alternatively be defined as the one having the rightmost \emph{ending} position in the word. However, we use the starting position and break ties by length since it makes the rules easier to state and work with. \end{rema} \begin{rema} The proofs in this section make heavy use of every part of the definition of $F$: the substrings, locations and transformation rules, and the use of the \emph{final} critical string. The reader may find it helpful to make a copy of Figure~\ref{fig:criticals} for reference. \end{rema} \begin{exam} \label{exa:apply-F} Let $w=1221'1'111'1'2'2222'2'11'1$ be the word in Example~\ref{ex:walk}. There are four $F$-critical substrings: \begin{itemize} \item the substring $w_1 = 1$ is critical of type 3F (and 4F in a different representative), \item the substring $w_1w_2 = 12'$ (in a different representative) is type 1F, \item the substring $w_1 \cdots w_4 = 1221'$ is type 2F, \item the substring $w_7 \cdots w_{10} = 11'1'2'$ is type 1F. \end{itemize} The last of these is final, so to obtain $F(w)$ we use transformation 1F and change $11'1'2'$ to $2'1'1'2$. We may continue to apply $F$ until it is undefined, reaching the end of the $F$-chain. The result is shown in Figure~\ref{fig:F-on-walks}. \begin{figure}[htb]\centering \setlength{\unitlength}{2.5em} \begin{picture}(4,5)(0,0) \multiput(0,0)(0,0.2){32}{\line(0,1){0.1}} \multiput(0,0)(0.2,0){22}{\line(1,0){0.1}} \put(0,0){\circle*{0.13}} \put(3,3){\circle{0.13}} \stepeast{1}{% \stepnorth{2}{% \stepnorth{2}{% \stepeast{1'}{% \stepeast{1'}{% \stepsouth{1}{% \stepwestshiftN{2'}{% \stepeast{1'}{% \stepeast{1'}{% \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepwest{2'}{% \stepwest{2'}{% \stepsouth{1}{% \stepeast{1'}{% \stepsouth{1}{% }}}}}}}}}}}}}}}}}} \end{picture} \hspace{1.5cm} \begin{picture}(3,6)(0,0) \multiput(0,0)(0,0.2){32}{\line(0,1){0.1}} \multiput(0,0)(0.2,0){19}{\line(1,0){0.1}} \put(0,0){\circle*{0.13}} \put(2,4){\circle{0.13}} \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepeast{1'}{% \stepeast{1'}{% \stepsouth{1}{% \stepwestshiftN{2'}{% \stepeast{1'}{% \stepeast{1'}{% \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepwest{2'}{% \stepwest{2'}{% \stepsouth{1}{% \stepeast{1'}{% \stepsouth{1}{% }}}}}}}}}}}}}}}}}} \end{picture}\hspace{2cm} \begin{picture}(3.5,6)(0,0) \multiput(0,0)(0,0.2){32}{\line(0,1){0.1}} \multiput(0,0)(0.2,0){19}{\line(1,0){0.1}} \put(0,0){\circle*{0.13}} \put(1,5){\circle{0.13}} \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepeast{1'}{% \stepeast{1'}{% \stepsouth{1}{% \stepwestshiftN{2'}{% \stepeast{1'}{% \stepeast{1'}{% \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepnorth{2}{% \stepwest{2'}{% \stepwest{2'}{% \stepwest{2'}{% \stepeastshiftS{1}{% \stepsouth{1}{% }}}}}}}}}}}}}}}}}} \end{picture} \caption{\label{fig:F-on-walks} Successive applications of the operator $F$ to the word $w$ of Examples~\ref{exa:apply-F} and~\ref{ex:walk}. From left to right, $F(w)$, $F(F(w))$, $F(F(F(w)))$; we have $F^{(4)}(w) = \varnothing$. Note that each application of $F$ shifts the endpoint by $(-1,+1)$.} \end{figure} \end{exam} Thanks to the symmetry operator $\eta$, it often suffices to prove statements for $F$ in order to obtain statements for $E$. For ease of exposition, we always opt (when possible) to prove the statements for $F$, not $E$. \subsection{\texorpdfstring{$E$}{E} and \texorpdfstring{$F$}{F} are partial inverses} We now show that $E$ and $F$ are partial inverses: \begin{prop}\label{prop:inverses} For words $w,w'$, we have $w' = F(w)$ if and only if $E(w') = w$. Moreover, when this holds: \begin{enumerate}[label={(\roman*)}] \item %[(i)] The final $E$-critical substring of $F(w)$ is the transformation of the final $F$-critical substring of $w$, and vice versa. \item %[(ii)] The operations $E$ and $F$ invert one another case-by-case: $1E \leftrightarrow 2F$, $2E \leftrightarrow 1F$, $3E \leftrightarrow 4F$, $4E \leftrightarrow 3F$. \end{enumerate} \end{prop} It is clear that the case-by-case transformation rules invert one another; the main challenge is to show that no new critical strings are created later in the word. It will suffice (by applying $\eta$) to show that $F(E(w)) = w$ whenever $E(w) \ne \varnothing$. We first make the following observation about the effects of $E,F$ on the substrings of $w$ not containing critical strings. Let $s$ be a substring $w_k \cdots w_l$ of $w$. Write $(x_i,y_i)$ for the location of the walk just before the letter $w_i$. \begin{lemma} \label{lem:shifting-walks-F} Suppose $x_k\ge 1$ and $(x_k,y_k)\neq (1,0)$. The following are equivalent: \begin{enumerate}[label={(\roman*)}] \item\label{lemma5.12_i} %[(i)] There are no $F$-critical substrings in the portion of $w$ corresponding to $s$ and no type 1F critical substrings whose last letter $2'$ is in $s$; \item\label{lemma5.12_ii} %[(ii)] The walk of the string $s$, but starting from $(x_k-1,y_k+1)$, has locations $(x_i-1,y_i+1)$ for each $i = k, \ldots, l+1$ \textup{(}this also implies $x_i > 0$ for these $i$\textup{)}. \end{enumerate} \end{lemma} In other words, shifting the starting location of $s$ by $(-1,+1)$ results in shifting that entire portion of the walk by $(-1,+1)$. \begin{proof} \ref{lemma5.12_ii} $\Rightarrow$~\ref{lemma5.12_i}: Suppose for contradiction that $s$ contains an $F$-critical substring or the last letter of a 1F. It is straightforward to check that shifting by $(-1,+1)$ alters the walk for critical strings of type 1F (in particular the last letter $2'$ always changes direction), second kind of 2F (the first letter changes direction), and 5F, giving a contradiction. For 3F, the same is true unless the location is $(1,0)$; but we assumed $s$ does not start at $(1,0)$ and so there is a letter prior to the $1$ in $s$. Since $x_k>0$ this letter must be a $1$ in location $(1,1)$, giving a 5F in $s$. The other two critical strings (first kind of 2F; 4F) always begin in location $x=0$, whereas our walk has $x_i > 0$ throughout. \ref{lemma5.12_i} $\Rightarrow$~\ref{lemma5.12_ii}: Suppose there are no $F$-critical substrings in $s$. Then first, note that any $\east{}$ arrows starting at $y=0$ in $s$ are $1'$ and not $1$ (so as to avoid 3F substrings) and if there were a $\north{}$ arrow starting at $y=0$, then it is a $2$. Indeed, if the $\north{}$ is $w_i=2'$, let $j0$. With this as a base case, we induct on $i$ to show~\ref{lemma5.12_ii} for $k\le i\le l$. It suffices to show that either $x_i=1$ and $w_i\in \{1',2\}$, or $x_i\ge 2$, since if $y_i=0$ then we are done since $w_i=1'$ or $2$ by the above argument, and if $y_i>0$ then $w_i$ either doesn't change or starts off the axes both before and after the shift. Assume these conditions hold for $i-1$. Then $x_i\ge 1$ since we can't move left from the position $x_{i-1}=1$. If $x_i=1$ and $w_i\in \{1,2'\}$ then $y\ge 1$ (from analyzing $x_{i-1}$ and $w_{i-1}$) and we have a 5F critical substring, a contradiction. Thus either $x_i=1$ and $w_i\in \{1',2\}$, or $x_i\ge 2$, as desired. \end{proof} We immediately obtain the counterpart of this lemma by applying $\eta$. (Recall that the walk of $\eta(w)$ is obtained by reflecting the walk of $w$ over the line $y=x$, and the $E$-critical substrings of $w$ of type 1E through 5E correspond to the $F$-critical substrings of $\eta(w)$ of type 1F through 5F.) \begin{lemma} \label{lem:shifting-walks-E} Suppose $y_k\ge 1$ and $(x_k,y_k)\neq (0,1)$. The following are equivalent: \begin{enumerate}[label={(\roman*)}] \item %[(i)] There are no $E$-critical substrings in the portion of $w$ corresponding to $s$ and no type 1E critical substrings whose last letter $1$ is in $s$; \item %[(ii)] The walk of $s$, but starting from $(x_k+1,y_k-1)$, has locations $(x_i+1,y_i-1)$ for each $i = k, \ldots, l+1$ \textup{(}this also implies $y_i > 0$\textup{)}. \end{enumerate} \end{lemma} We now use these two lemmas repeatedly to prove that $E$ and $F$ are partial inverses. \begin{proof}[Proof of Proposition~\ref{prop:inverses}] It suffices to show (by applying $\eta$) that $E(F(w)) = w$ whenever $F(w)$ is defined. So, suppose $F(w)$ is defined and let $v=F(w)$ where $u=w_k,\ldots, w_l$ is the final $F$-critical substring of $w$, changed to $v_k,\ldots, v_l$. It suffices to show $v$ has no later $E$-critical substrings. \begin{enonce*}[remark]{Case 1} Suppose $u=w_k,\ldots,w_l=1(1')^\ast 2'$ has type 1F. Then there are no later $F$-critical substrings (nor endings of 1F critical substrings) among the tail $w_{l+1},\ldots,w_n$, and clearly $w_{l+1}$ does not start at $(1,0)$ or on the $y$-axis, so by Lemma~\ref{lem:shifting-walks-F}, the tail can be shifted by $(-1,+1)$. Then, by Lemma~\ref{lem:shifting-walks-E}, there are no $E$-critical substrings in $v_{l+1} \cdots v_n$. It now remains to check that there are no $E$-critical substrings starting in $v_{k+1} \cdots v_l = (1')^*2$. But an inspection of the definition of $E$ shows that the only possibility is a 4E at $v_l$ (since $v_k=2'$ and therefore $v_l=2$ cannot be represented as $2'$). But $v_k=2'$ makes $y=0$ impossible before $v_l$, and we're done. \end{enonce*} \begin{enonce*}[remark]{Case 2} Suppose $u=w_k,\ldots,w_l=1(2)^\ast 1'$ is type 2F. Then $w_l=1'$ starts at a location not at $x=0$ or $(1,0)$ except when the location just before $w_k$ is $(1,1)$ and $l=k+1$, and in any case $w_{l+1}$ starts at a valid location for Lemma~\ref{lem:shifting-walks-F}. So, as in Case 1, applying Lemmas~\ref{lem:shifting-walks-F} and~\ref{lem:shifting-walks-E} we find that $v_{l+1},\ldots,v_n$ has no $E$-critical substrings, and no longer 1E criticals start among $v_k,\ldots,v_l$. There are clearly no $E$-critical substrings of type 3E, 4E, or 5E starting after the first letter of $v_k,\ldots,v_{l}=2'(2)^\ast 1$ since the locations of the letters involved are not valid for these types. Finally, the only way that a later 2E can start among $v_k,\ldots,v_l$ is if $v_k=2'$ starts the substring, $l=k+1$, and $v_l=v_{k+1}=1$ is the first $1$ or $1'$ of the word so that it counts as a $1'$ in the 2E critical substring. For this to happen the $1$ must start on the $y$-axis and by the 2E location conditions this means $v_k=v_1$ starts at $(0,0)$. But then the 2E critical substring $v_1,\ldots,v_m=21(1')^\ast 2$ changes to $1(1')^\ast 2$ starting at $(0,0)$ in $w$, which counts as a later 1F, a contradiction. \end{enonce*} \begin{enonce*}[remark]{Case 3} Suppose $u=w_k=1$ is type 3F. As long as $(x_k,y_k)\neq (0,0)$, the tail $w_{k+1},\ldots, w_{n}$ has a valid starting location for Lemma~\ref{lem:shifting-walks-F}, and so by the same arguments as in the previous two cases (since $u$ cannot be extended to a longer 1F) we see that $v_{k+1},\ldots,v_n$ has no later $E$-critical substrings. In addition $v_k=2$ (a type 4E critical) is not the start of a longer 2E critical substring since then $v_k=2=2'$ is the first $2$ or $2'$ in $v$, and so the first $2$ after it in the 2E critical substring is the first $2$ or $2'$ in $w$, creating a 1F critical substring in $w$ starting at $w_k$. Otherwise, if $(x_k,y_k)=(0,0)$ (and so $k=1$) we see that the next entry $w_2$ starts on an axis in both $w$ and $v$, and hence does not change direction. The tail starting from $w_3$ also starts in a valid location for Lemma~\ref{lem:shifting-walks-F}, so the tail can be shifted and by Lemma~\ref{lem:shifting-walks-E} the corresponding tail in $v$ has no $E$-critical substrings. Any $E$-critical substring starting at $v_2$ must be a 1E or 3E with $v_2=2'$, but then $w_1w_2=12'$ is a 1F critical substring in $w$, a contradiction. Finally, suppose there is a longer 1E or 2E critical substring starting at $v_1=2=2'$. If it is 1E of the form $2'(2)^\ast 1$ with at least one $2$ in $(2)^\ast$, then $w$ starts with $1(2)^\ast 1$ and the last $1$ is a type 5F critical substring, a contradiction. If it is $2'1$ then $w$ starts $11$ and $w_2$ is a later $F$-critical, also a contradiction. Finally if it is 2E of the form $2'(1')^\ast 2$ then $w$ starts $1(1')^\ast 2$ and this is a longer 1F critical substring (since the first $2$ counts as $2'$). \end{enonce*} \begin{enonce*}[remark]{Case 4} Suppose $u=w_k=1'$ is type 4F. Note that the only location for which the tail $w_{k+1},\ldots,w_{n}$ does not satisfy the conditions of Lemma~\ref{lem:shifting-walks-F} is when the $1'$ arrow starts from $(0,0)$ and so $k=1$. But this is identical to the analysis in Case 3 since in this situation $u$ is both a 3F and 4F critical substring. So it suffices to consider the case when the tail of $w$ starts off-axes. By Lemmas~\ref{lem:shifting-walks-F} and~\ref{lem:shifting-walks-E} there are no $E$-criticals among $v_{k+1},\ldots,v_n$. To check that no longer $E$-criticals start from $v_k=2'$, note that 1E types are eliminated by Lemma~\ref{lem:shifting-walks-E} and 2E types are in the wrong starting location.\qedhere \end{enonce*} \end{proof} \subsection{Interaction with the endpoint of the lattice walk} The operators $E,F$ have well-behaved interactions with the shape and endpoint of the lattice walk. We state two useful facts, which follow from Lemmas~\ref{lem:shifting-walks-F} and~\ref{lem:shifting-walks-E}. \begin{coro}\label{cor:F-on-walk} The operation $F$ changes the direction of precisely one step in the walk, either from $\south{}$ to $\west{~~}$ or from $\east{~~}$ to $\north{}$. In particular, the endpoint changes by $(-1,+1)$. For $E$, the statement is reversed. \end{coro} \begin{coro} \label{cor:initial-subwords-dual} The sum of the coordinates of the $k$th position in the walk is unchanged for all $k$ by $F$ and $E$. It follows that the rectification shape of any initial subword of $w$ is an invariant for $F$ and $E$. \end{coro} We also give an alternate criterion for when $E,F$ are defined, in terms of the lattice walk rather than strings. We will use this in our proof that $E,F$ are coplactic. \begin{prop} \label{prop:alternate-definedness} Let $w$ be a word and let $(x,y)$ be the endpoint of $w$'s lattice walk. \begin{enumerate}[label={(\roman*)}] \item\label{prop5.16_i} %[(i)] If $x=0$, then $F(w)$ is undefined. \item\label{prop5.16_ii} %[(ii)] If $x = 1$ and the walk does not contain a $\south{}$ or $\west{}$ step, then $F(w)$ is defined. \item\label{prop5.16_iii} %[(iii)] If $x=1$ and the walk contains a $\south{}$ or $\west{}$ step, then $F(w)$ is defined if and only if $F'(w)$ is undefined. \item\label{prop5.16_iv} %[(iv)] If $x \geq 2$, then $F(w)$ is defined. \end{enumerate} The statement for $E$ is given by applying $\eta$ \textup{(}switching $x \leftrightarrow y$ and $F' \leftrightarrow E'$\textup{)}. \end{prop} \begin{lemma} \label{lem:xgeq2-Fcritical} Suppose some step $w_i$ of $w$ has $x=0$, and $x \geq 2$ at some later point \textup{(}possibly the endpoint\textup{)}. Then there is an $F$-critical string in the suffix $w_i w_{i+1} \cdots$. \end{lemma} \begin{proof}%[Proof of Lemma] First, skipping any immediate $\north{}$ steps, we may assume $w_i = 1'$ or $1$. If $w_i = 1'$, it is type 4F. This includes the case where $w_i$ is the first $1$ of $w$ (since it counts as both), so in the case $w_i = 1$ we may assume $y>0$. Let $w_j$ be the next letter that is not $2$ ($w_j$ exists because the endpoint does not have $x=1$). If $w_j = 1'$, $w_i \cdots w_j$ is 2F. If $w_j = 1$ or $2'$, then $w_j$ is 5F. \end{proof} \begin{proof}[Proof of Proposition~\ref{prop:alternate-definedness}] For~\ref{prop5.16_i}, we have $F(w) = \varnothing$ because the endpoint cannot shift by $(-1,+1)$. For~\ref{prop5.16_ii}, by inspection, $w$ has a single $1$, which counts as a 4F-critical string and is final. For~\ref{prop5.16_iii} and~\ref{prop5.16_iv}, the first $1$ of $w$ again counts as 4F, so $F$ will be undefined if and only if the final critical string is type 5F. We consider~\ref{prop5.16_iii} and~\ref{prop5.16_iv} separately. \ref{prop5.16_iii}: We show that the final $F$-critical string is a 5F if and only if the last $1$ or $2'$ in $w$ is a $1$ (that is, $F'$ is defined). $(\Rightarrow)$: Suppose the final critical string $w_i$ has type 5F. If $w_i = 1$, let $w_j$ be the next letter that is not $2$. Then $w_j$ cannot be $1$ (type 5F or 3F, depending on whether $y=0$), $1'$ (type 2F), or $2'$ (type 5F or 1F, depending on whether $y=0$). So $w_j$ cannot exist and the entire suffix contains only $(2)$s. If $w_i = 2'$ instead, then $x=0$ after it, so by Lemma~\ref{lem:xgeq2-Fcritical} we must have $x \leq 1$ for the remainder of the word. But then $x=0$ immediately after the last $2'$ of $w$, and there must be a $1$ or $1'$ later to reach $x=1$ at the endpoint. But it cannot be $1'$ (type 4F), hence is a $1$ as desired. $(\Leftarrow)$: Suppose the last $1$ or $2'$ is $w_i = 1$ at location $(x_i,y_i)$. Since all further steps are $1'$ (right) and $2$ (up), we must have $x_i=0$ or $1$. Either way, $x_{i+1}=1$, so in fact the suffix is just $(2)^*$. If $x_i=1$, then $w_i$ is type 5F and we're done. If $x_i=0$, consider the largest index $j < i$ such that $x_j=1$ ($j$ exists because the walk must be off-axes at some point if it has a $\south{}$ or $\west{}$ step). Then $w_j = 2'$ is 5F-critical and is final by inspection. \ref{prop5.16_iv} Suppose $x \geq 2$ and the final $F$-critical string $w_i$ has type 5F. If $w_i = 2'$, Lemma~\ref{lem:xgeq2-Fcritical} gives a later critical string (since $x_{i+1}=0$), so we must have $w_i = 1$. Let $w_j$ be the next letter that is not $2$, which must exist because the endpoint has $x \geq 2$. But we cannot have $w_j = 1'$ (type 2F) or $1$ (type 3F or 5F, depending on whether $y=0$) or $2'$ (type 1F or 5F, depending on whether $y=0$), a contradiction. \end{proof} As a corollary, we take the first step toward showing that $E$ and $F$ are coplactic: \begin{coro} \label{cor:Fdefinedness-knuth} Let $w, w'$ be Knuth equivalent. Then $F(w)$ is defined iff $F(w')$ is defined. \end{coro} \begin{proof} By Proposition~\ref{prop:alternate-definedness}, whether $F$ is defined depends only on the endpoint of the walk, whether the walk contains any $\south{}$ or $\west{}$ steps, and whether $F'$ is defined. This data is preserved under Knuth moves by Propositions~\ref{prop:primed-coplactic} and~\ref{prop:walks} and Theorem~\ref{thm:rectification}. \end{proof} Finally, we obtain a characterization of ballotness depending only on our operators: \begin{prop} \label{prop:ballot-iff-killed} A word $w$ in the alphabet $\{1',1,2',2\}$ is ballot if and only if $E(w) = E'(w) = \varnothing$. It is anti-ballot if and only if $F(w) = F'(w) = \varnothing$. \end{prop} \begin{proof} We prove the anti-statement. If both are undefined, Proposition~\ref{prop:alternate-definedness} shows that the endpoint has $x=0$, hence $w$ is anti-ballot by Corollary~\ref{cor:ballot-walk-criterion}. Conversely, if $w$ is anti-ballot, the endpoint has $x=0$. Then $F$ and $F'$ must be undefined because either would cause the endpoint to shift by $(-1,+1)$. \end{proof} \subsection{The operators \texorpdfstring{$E$}{E} and \texorpdfstring{$F$}{F} on tableaux} Let $T$ be a skew, shifted semistandard tableaux with entries in $\{1',1,2',2\}$. We define $E(T), F(T)$ by applying $E,F$ to the row reading word of $T$. (We will see later, Proposition~\ref{prop:rows-columns}, that using the column word results in the same action.) The main claim of this subsection is that this gives a well-defined action on \emph{semistandard} tableaux: \begin{theorem} \label{thm:FE-semistandard} The tableaux $F(T), E(T)$ are semistandard \textup{(}when defined\textup{)}. \end{theorem} We first show the following. Let $a,b \in T$ with $b$ just below $a$. \begin{lemma} \label{lem:special-ssyt-cases} If the lattice walk has $y=0$ at $a$, then $b=1$ or $1'$. Next, suppose $y=0$ at $b$, and $a \in \{1,2'\}$, and there is a $1$ somewhere before $a$ in reading order. Then there is a 5E-critical string in $a$'s row. \end{lemma} \begin{proof} Let $k$ be the number of $(2')$s and $(2)$s to the left of $b$. If the leftmost is not on the diagonal, then there are at most $k$ $(1)$s to the left of $a$; otherwise, there may be $(k+1)$ $(1)$s, but the first contributes $\east{}$ to the walk. Now if $b \in \{2',2\}$, then we have $y \geq k+1$ in the walk just after $b$, hence $y \geq k+1$ at the end of $b$'s row. But then we have at most $k$ downwards steps prior to $a$, contradicting the condition $y=0$. For the second statement, let $k$ be the number of $(2)$s to the right of $b$ (by semistandardness, $b \geq 2'$ and every entry to its right is a $2$). Then from $a$ to the end of the upper row, there are at least $k$ $(1)$s (including $a$ itself if $k>0$), followed by an entry $a' \in \{1,2'\}$: \[ \begin{ytableau} a \\ b & 2 & 2 & 2 \end{ytableau} \qquad \leadsto \qquad \begin{ytableau} 1 & 1 & 1 & a' & \cdots \\ b & 2 & 2 & 2 \end{ytableau} \] We claim that $x \geq 1, y \leq k+1$ at $a$. Hence $a'$ or some entry before it has $y=1$, giving a 5E-critical string. The condition on $y$ is clear because $y=k+1$ at the end of $b$'s row, and any entry to the left of $a$ is $1$ or $1'$. As for $x$: if $x=0$ at $b$, then $b$ is the first letter of the word, so (by our assumption on $a$) there must be a single $1$ to the left of $a$, giving an initial $\east{}$ step. Otherwise $x \geq 1$ at $b$, hence at the end of $b$'s row, hence at $a$. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:FE-semistandard}] We use the representatives for $T$ and $F(T)$ in which the final $F$-critical string appeared, not necessarily the canonical form. In particular, $F(T)$ has the same entries as $T$ except for the first and last letters of the final $F$-critical string. Note that changing representatives never violates semistandardness. Let $a,b$ be adjacent squares in $T$: $\raisebox{0cm}{\small \begin{ytableau}a&b\end{ytableau}}$ \ or \ $\raisebox{.5\height}{\small \begin{ytableau}a\\ b\end{ytableau}}$. Let $a',b'$ be the corresponding squares in $F(T)$ or $E(T)$. If neither square changes, there is nothing to check. If both squares change, they must be the first and last letters of a 1F or 2F critical string and, by semistandardness of $T$, must take the form \[ \raisebox{-.25\height}{\begin{ytableau}1 & 2'\end{ytableau}}\ \xrightarrow{\ 1F\ }\ \raisebox{-.25\height}{\begin{ytableau}2' & 2\end{ytableau}} \qquad \text{or} \qquad \raisebox{.25\height}{\begin{ytableau}1' \\ 1\end{ytableau}} \ \xrightarrow{\ 2F\ }\ \raisebox{.25\height}{\begin{ytableau}1 \\ 2'\end{ytableau}} \] In these cases we see that semistandardness is preserved. Next, suppose $a$ changes and $b$ does not. For $E(T)$, we're done because the new value always has $a' < a$. For $F(T)$, we have $a' > a$, so there are a few cases. \emph{Horizontal case for $F$}. If $a = 1' \leadsto 1$ or $2' \leadsto 2$ (1F and 2F, last letters), $b$ is large enough ($b \geq 1$ or $2$) because $T$ is semistandard. If $a = 1 \leadsto 2'$ (1F and 2F, first letters), we cannot have $b=2'$ by the definition of the substring (and our assumption that $b$ does not change), so $b=2$ as desired. Finally, if $a = 1 \leadsto 2$ (3F) or $a = 1' \leadsto 2'$ (4F), suppose $b \in \{1,2'\}$. Then $b$ or $ab$ gives a later or longer 1F, 3F or 5F critical string (depending on which coordinates are zero at $a$). \emph{Vertical case for $F$}. First, if $a = 1 \leadsto 2'$ (1F and 2F, first letter), we have $b \geq 2'$ by semistandardness. Next, if $a = 2' \leadsto 2$ (1F, last letter) or $1 \leadsto 2$ (3F), Lemma~\ref{lem:special-ssyt-cases} forces $b \ne 1',1$ (note that $y=0$ at $a$), so in fact $b$ cannot exist. Finally, if $a = 1' \leadsto 1$ (2F, last letter) or $1' \leadsto 2'$ (4F), suppose $b \in \{1',1\}$. Since $x=0$ at $a$, $b$ cannot be the preceding letter (and $a$ is leftmost in its row), so $b$ has an entry $c$ to its right, with an entry $d$ above it. By semistandardness, $d \in \{1,2'\}$, giving a later 5F (note that $y\ne0$ since $a$ is not the first letter of the word). This completes this case. Finally, suppose $b$ changes and $a$ does not. For $F(T)$, there is nothing to check because $b' > b$. In $E(T)$, we have $b' < b$, so there are a few cases. \emph{Horizontal case for $E$}. If $b = 2' \leadsto 1$ (1E and 2E, first letters), then $a \leq 1$ since $T$ is semistandard. If $b = 2 \leadsto 2'$ (2E, last letter), then $a = 1'$ from the definition of the substring. If $b = 1 \leadsto 1'$ (1E, last letter) then the substring instead indicates $a=2$. This violates semistandardness, so in fact $a$ cannot exist. If $b = 2' \leadsto 1'$ (3E), observe that, since $x=0$ at $b$, we can't have $a \in \{1,1'\}$. So, by semistandardness, $a$ again does not exist. Lastly, if $b = 2 \leadsto 1$ (4E), then $a \notin \{2',2\}$ since we must have $y=0$ at $b$. \emph{Vertical case for $E$}. If $b = 2 \leadsto 2'$ or $1 \leadsto 1'$ (1E and 2E, last letter), then $a$ is small enough since $T$ is semistandard. In all remaining cases, we have $b \in \{2',2\} \leadsto b' \in \{1',1\}$. We know $a \ne 2$ by semistandardness, but we need to show $a = 1'$. So, assume for contradiction that $a \in \{1,2'\}$; we will find various later $E$-critical strings. First, suppose $b = 2 \leadsto 1$ (4E). There can't be a $1$ or $1'$ prior to $a$ in reading order, since Lemma~\ref{lem:special-ssyt-cases} would then find a 5E-critical string in the row of $a$ (since $y=0$ at~$b$). But if there are no $(1)$s or $(1')$s before $b$ clearly $x=0$ at $b$ as well, so $b$ is the first letter of the word and counts as a final 3E in a different representative of $T$; we deal with it below. In the remaining cases, $b = 2'$. If there is an entry $\tilde{a}$ to $a$'s left, semistandardness forces $\tilde{a} = 1'$ or $1$, and the square below $\tilde{a}$ (to $b$'s left) to be empty. So in fact Lemma~\ref{lem:special-ssyt-cases} applies again ($\tilde{a}$ and $b$ are on the diagonal, so $b$ is the first letter of the word and has location $y=0$). So we may assume $a$ is leftmost in its row and $b \cdots a = 2' (2)^* a$. \looseness-1 If $b = 2' \leadsto 1'$ (3E), then either $a=1$, making $b \cdots a = 2' (2)^*1$ type 1E-critical, or $a=2'$ and is itself 3E-critical. If $b = 2' \leadsto 1$ (1E, first letter), then $a$ must be the final $1$ of the 1E string. But this contradicts our assumption that $a$ did not change in $F(T)$. Finally, suppose $b = 2' \leadsto 1$ (2E, first letter). If the location has $x \geq 2$ at $b$, then in fact the same counting argument as in Lemma~\ref{lem:special-ssyt-cases} shows that $x \geq 1$ and $y \leq k+1$ at $a$ (where $k$ is the number of $(2)$s to the right of $b$), yielding a 5E-critical string in $a$'s row. Otherwise, $b$'s location is either $(0,0)$ or $(1,1)$. Either way, note that the 2E must be just $2'2$, with a $2$ to the right of $b$, which forces $a=1$ by semistandardness. Thus $b\cdots a = 2'(2)^*1$ is 1E-critical. \end{proof} Having shown that our operators are well-defined on tableaux, our remaining goal is to show that they are coplactic (Theorem~\ref{thm:coplactic}). Before proceeding, we end this section with some final details on the interaction of $E,F$ with the tableau structure. We first describe the action of $E$ and $F$ on straight shifted tableaux. \begin{prop} \label{prop:rect-unprimed-action} Let $T$ be a straight shifted semistandard tableau with entries $\{1',1,2',2\}$. If $T$ has no $2'$ in the first row, then $F$ changes the rightmost $1$ to a $2$ \textup{(}or gives $\varnothing$ if this breaks semistandardness\textup{)}, and $E$ changes the leftmost $2$ in the first row to a $1$ \textup{(}or gives $\varnothing$ if there is no such $2$\textup{)}. If $T$ has a $2'$ in the first row, then $F$ changes the substring $12'$ to $2'2$ \textup{(}or gives $\varnothing$ if this breaks semistandardness\textup{)}, and $E$ does the opposite \textup{(}or gives $\varnothing$ if there is no $2$\textup{)}. \end{prop} \begin{proof} We prove the claim about $F$, since $E$ is just the inverse. The word of $T$ is either $1^a2^b$, or $2^a1^b2^c$ with $b>a>0$, or $2^a1^b2'2^c$ with $b \geq a > 0$. In the case $1^a2^b$, if $b>0$, the substring $12$ is type 1F, becoming $22$ (after canonicalizing). If $b=0$, the last $1$ is type 3F. In the case $2^a1^b2^c$, the final $1$ is type 5F if $b=a+1$ and type 3F otherwise. Similarly, in the case $2^a1^b2'2^c$, the substring $2'$ is type 5F if $b=a$; otherwise the substring $12'$ is type 1F. (The edge cases $b=a+1$ and $b=a$, leading to 5F critical strings, are also the cases where semistandardness would break.) \end{proof} We also show that our use of row words rather than column words was harmless. We prove this \emph{assuming} $E$ and $F$ are coplactic (and do not use this statement in the proof of that fact). Recall that $\etaT$ is the operation on tableaux corresponding to the map $\eta$ on words. \begin{prop} \label{prop:rows-columns} Let $w, v$ be the row and column reading words of a tableau $T$. Then applying $F$ to $w$ changes the entries of $T$ in the same way as applying $F$ to $v$. \end{prop} \begin{proof} Let $\tilde{F}(T)$ be obtained by applying $F$ to $v$. Note that if $T$ is a shifted straight shape, then $\tilde{F}(T) = F(T)$ by inspection from Proposition~\ref{prop:rect-unprimed-action}. We now claim that $\tilde{F}$ preserves semistandardness and is coplactic; hence $\tilde{F}(T) = F(T)$ for all tableaux $T$. To show this, we recall the action $\etaT$ on tableaux (Definition~\ref{def:eta-on-T}), and we observe that $\tilde{F}(T) = \etaT \circ E \circ \etaT(T)$. The two desired properties hold for $\etaT$ by Remark~\ref{rmk:row-col-eta} and for $E$ by Theorems~\ref{thm:FE-semistandard} and~\ref{thm:coplactic}, hence they hold for the composition. \end{proof} \subsection{Compatibility with dual equivalence} In this section, we show $F(T)$ and $E(T)$ are shifted dual equivalent to $T$ (when defined). We first recall the notion of dual equivalence in terms of mixed insertion and shifted RSK. We follow the conventions used in~\cite{Sagan}; for convenience, we extend the usual definition from standard to semistandard shifted tableaux. \begin{defi} For letters $a$ and $b$ in $\{1'<1<2'<2<3'<3<\cdots\}$, we say that $a\prec_{\row} b$ if either $a$ is a primed letter and $a\le b$, or if $a$ is unprimed and $a1$, and $w_1, \ldots, w_{i-1} \in \{2',2\}$, \item\label{condition4} $w_i=1$ or $2'$, and $i > j$, where $w_j$ is the first downwards or leftwards step of the lattice walk of $w$, and the most recent $1$ or $2'$ before $w_i$ is a $2'$. \textup{(}Equivalently, if $i > j$ and $F'(w_1, \ldots, w_{i-1}) = \varnothing$.\textup{)} \end{enumerate} \end{lemma} \begin{proof} At step $i-1$ of the RSK process, the recording tableau $P$ is a one or two-row tableau of one of the forms illustrated in Figure~\ref{fig:two-row}. Let $R_1$ and $R_2$ be the two (possibly empty) rows of $P$. Then the only two possibilities for the entry $i$ being circled in $Q$ is if the insertion of $w_i$ into $P$ either bumps out the first entry of $R_1$, or bumps an entry into $R_2$ which in turn bumps out its first entry. First we analyze the cases in which $w_i$ bumps out the first entry of $R_1$. If $w_i=1'$ it cannot be the first entry of the word (since $w$ is in canonical form) and is always less than the first entry in $\prec_{\row }$ order, hence always bumps it. This gives condition~\ref{condition1}. If $w_i=1$ or $2'$, it bumps out the first entry of $R_1$ if and only if $i>1$ and there are no $(1)$s already in $R_1$. Equivalently, there should be no $(1)$s or $(1')$s among $w_1, \ldots, w_{i-1}$, since such entries will always end up in $R_1$. This gives condition~\ref{condition2}. Finally, $w_i=2$ can never bump out the very first entry in $R_1$. Now, we consider when the insertion of $w_i$ can bump an entry $b$ in $R_1$ to row $R_2$, and $b$ in turn bumps out the first entry of $R_2$ (which must be a $2$ by semistandardness). This never occurs if $w_i=1'$, because the algorithm switches to column insertion immediately, nor if $w_i=2$, since then $w_i$ is placed at the end of $R_1$. So suppose $w_i=1$ or $2'$ and $w_i$ bumps out an entry $b$ that is not at the start of row $R_1$. Then $w_i$ is circled iff $b=2'$ (by definition of $\prec_{\row }$). Recall also that there can be at most one $2'$ in $R_1$ (in which case it is the entry $b$ and is bumped out), and this occurs if and only if $P$ has two nonempty rows and $F'(P)=\varnothing$. We are left with determining when this situation occurs. First note that $P$ has two rows if and only if the walk has at least one downwards or leftwards step, by Theorem~\ref{thm:rectification}. Let $w_j$ be the first such step. Once $w_j$ is inserted (it is never circled), the insertion tableau $P$ has a $2'$ in $R_1$ if and only if $w_j=2'$. Let $w_i$ be the next $1$ or $2'$ after $w_j$. Then we see that $i$ is circled if and only if $w_j=2'$, and when step $i$ is complete, $R_1$ contains a $2'$ if and only if $w_i=2'$. Continuing this argument to the right gives condition~\ref{condition4}. \end{proof} The following was shown in~\cite{Haiman}, which we use in this paper as the \emph{definition} of shifted dual equivalence. \begin{prop}[{\cite[Lemma~2.11 and Theorem~2.12]{Haiman}}] \label{prop:Haiman1} Two shifted standard tableaux of the same skew shape are dual equivalent if and only if their row words have the same mixed-insertion recording tableau. \end{prop} While the above proposition is only stated for standard tableaux, note that our expanded definition of mixed insertion above is compatible with standardization of tableaux, and so by Lemma~\ref{lem:unstandardize} it also holds for semistandard tableaux. We now show: \begin{prop} When defined, $F(w)$ and $E(w)$ are dual equivalent to $w$. \end{prop} \begin{proof} It suffices to show that, under mixed insertion, $F(w)$ has the same circled recording tableau as $w$. We first show this when the final $F$-critical string has type 1F or 3F. It then follows for 2F and 4F by applying $\eta$ and Proposition~\ref{prop:inverses} (see Remark~\ref{rmk:eta-words-dual}). By Corollary~\ref{cor:initial-subwords-dual}, the insertion tableaux $P_{w}$ and $P_{F(w)}$ have the same shape at every step of the insertion process. Therefore the recording tableaux $Q_{w}$ and $Q_{F(w)}$ are the same if we ignore the circling. We are left with showing that $Q_{w}$ and $Q_{F(w)}$ have the same circled entries. \begin{enonce*}[remark]{Case 1F} Suppose the final $F$-critical substring $u$ in $w$ is type 1F, so $u=1(1')^\ast 2'$ with starting location either $y=0$ or $y=1$, $x\ge 1$. Then $u$ changes to $s=2'(1')^\ast 2$ in $F(T)$. Clearly the circlings prior to $u$ in reading order are unchanged, and the $(1')$s are circled indices in both $u$ and $s$. Any later circlings are also unchanged because, in both $u$ and $s$, the last $1$ or $2'$ in these substrings is a $2'$. We next check that $u_1=1$ is a circled index if and only if $s_1=2'$ is. First note that $u_1$ satisfies condition~\ref{condition2} of Lemma~\ref{lem:circling} if and only if $s_1$ does. For condition~\ref{condition4}, note that the index $j$ of the first downwards or leftwards step in the walk is preserved by $F$, by Corollary~\ref{cor:F-on-walk}. Thus $i$ is uncircled if $i \leq j$; if instead $i > j$, then $i$ is circled if and only if the previous $1$ or $2'$ is a $2'$. Finally, since the $2'$ in $u$ follows $u_1=1$, its index is uncircled by conditions~\ref{condition2} and~\ref{condition4}. The corresponding $2$ in $s$ is also uncircled because $(2)$s are never circled. \end{enonce*} \begin{enonce*}[remark]{Case 3F} Suppose the final $F$-critical substring $u$ of $w$ is type 3F, so $u=1$, becoming $s=2$ in $F(T)$. Let $j$ be the index of the first downwards or leftwards step in the walk. Note that $i \ne j$ because $y=0$ at $u$, and if $j$ does not exist then we're done by Lemma~\ref{lem:circling}. First, $u$ itself cannot satisfy condition~\ref{condition2} of Lemma~\ref{lem:circling} because it starts at $y=0$. For condition~\ref{condition4}, if $i < j$, $i$ is uncircled, and changing $u$ to $s$ does not affect the circling of any later letters (because $w_j$ will be a $1$ or $2'$). If $i > j$, the walk must have had $y>0$ at some point prior to $u$. To reach $y=0$ at $u$, the last $1$ or $2'$ before $u$ must have been a downwards $1$, with no $(2')$s (or $(2)$s) between it and $u$. But then $u=1$ is an uncircled index (as is $s=2$), and changing $u$ to $s$ does not affect the circling of any later letters.\qedhere \end{enonce*} \end{proof} \begin{coro} \label{cor:FE-dual-equiv} When defined, $F(T)$ and $E(T)$ are dual equivalent to $T$. \end{coro} \begin{proof} We have shown that $T$ and $F(T)$ are semistandard tableaux of the same skew shape, and that their row words have the same mixed-insertion recording tableau. The result now follows by Proposition~\ref{prop:Haiman1}. \end{proof} \subsection{Coplacticity} We now use the machinery we have developed to prove the main result of this paper, that $F$ and $E$ are coplactic. We also require the following result of Haiman~\cite{Haiman}: \begin{prop}[{\cite[Theorem 2.13]{Haiman}}] \label{prop:Haiman2} A skew shifted tableau is uniquely determined by its shape, dual equivalence class, and jeu de taquin equivalence class \textup{(}rectification\textup{)}. \end{prop} \begin{theorem}\label{thm:coplactic} The operations $F$ and $E$ are coplactic. \end{theorem} \begin{proof} Let $T$ be a tableau and let $S$ be obtained from $T$ by a JDT slide. If $F(T) = F(S) = \varnothing$, there is nothing to show, so assume $F(T) \ne \varnothing$. By Corollary~\ref{cor:Fdefinedness-knuth}, $F(S) \ne \varnothing$ as well. Let $\sliderm(F(T))$ be the tableau obtained from $F(T)$ by the slide initiated in the same square. We show $\sliderm(F(T)) = F(S)$. Note that this also automatically proves the claim for tableaux on larger alphabets, since any JDT slide restricts to a JDT slide on the $(i,i+1)$-strip of a tableau. First, since $F(T)$ is dual equivalent to $T$, they slide to dual equivalent tableaux, so $\sliderm(F(T))$ is dual equivalent to $S$ and so also to $F(S)$. By Proposition~\ref{prop:Haiman2}, it suffices to show that $\sliderm(F(T))$ and $F(S)$ also have the same rectification. Observe next that $F(S)$ and $\sliderm(F(T))$ have the same weight and rectification shape, by Theorem~\ref{thm:rectification} and Corollary~\ref{cor:F-on-walk}. This leaves at most two possibilities for their rectifications (see the diagrams in Figure~\ref{fig:two-row}). In the case with two possibilities, the rectification shape has two rows and the distinguishing feature is whether or not $F'$ is defined, that is, whether or not the last $1$ or $2'$ in the word is a $2'$ (equivalently, appending a $1$ or $2'$ to the word should add a circled entry in the recording tableau). By the analysis in the proofs of Lemma~\ref{lem:circling} and Corollary~\ref{cor:FE-dual-equiv}, this property is invariant under $F$. So, the following are equivalent: \[ %\begin{center} \begin{tabular}{rll} $F'$ defined on $F(S)$ & $\Leftrightarrow F'$ defined on $S$ & (Corollary~\ref{cor:FE-dual-equiv})\\ & $\Leftrightarrow F'$ defined on $T$ & ($F'$ is coplactic)\\ & $\Leftrightarrow F'$ defined on $F(T)$ & (Corollary~\ref{cor:FE-dual-equiv})\\ & $\Leftrightarrow F'$ defined on $\sliderm(F(T))$ & ($F'$ is coplactic). \end{tabular} %\end{center} \] Therefore, $F(S)$ and $\sliderm(F(T))$ have the same rectification, as desired. \end{proof} \noindent In the proof above, we showed that (in the case where $\rectify(T)$ has two rows) $F'$ is defined on $T$ if and only if it is defined on $F(T)$. In fact more is true: \begin{prop} \label{prop:commutes} The operations $F, F', E, E'$ commute whenever both possible compositions are defined. \end{prop} \begin{proof} By coplacticity, it suffices to prove this statement for words of straight shifted tableaux. The statement then follows from Propositions~\ref{prop:rect-primed-action} and~\ref{prop:rect-unprimed-action}. (See Figure~\ref{fig:two-row} for an illustration.) \end{proof} \begin{rema} In fact $F\circ F'$ is defined on $w$ if and only if $F'\circ F$ is defined, and likewise with $E$ and $E'$. For $\{F,E'\}$ and $\{F',E\}$, the statement is instead that if both operators are defined on $w$, then so are both compositions. \end{rema} We also note that $F$ and $F'$ (and likewise $E$ and $E'$) coincide if and only if the rectification shape of the word has one row. \begin{coro} If $\rectify(w)$ has only one row, then $F(w) = F'(w)$ and $E(w) = E'(w)$. Otherwise, \textup{(}when defined\textup{)} $F(w)$ has the same number of primed symbols as $w$, and $F'(w)$ has one more primed symbol than $w$, which shows that they are different. \end{coro} \section{Doubled crystal structure}\label{sec:crystal} We now consider the joint combinatorial structure built out of the primed and unprimed operators on words and tableaux from an arbitrary alphabet. Our main goal is to prove Theorem~\ref{thm:main-doubled-typeA} on this ``doubled'' crystal structure. \subsection{Extending the alphabet: \texorpdfstring{$E_i$}{Ei}, \texorpdfstring{$E'_i$}{E'i}, \texorpdfstring{$F_i$}{Fi}, and \texorpdfstring{$F'_i$}{F'i}} We extend our operators to words and tableaux in the infinite alphabet \[ \{1',1,2',2,3',3,\ldots\}. \] \begin{defi} We define $E_1$, $E'_1$, $F_1$, and $F'_1$ to be the result of applying the operators $E$, $E'$, $F$, and $F'$ respectively to the subword consisting of letters $1',1,2',2$. We similarly define $E_i$, $E'_i$, $F_i$, and $F'_i$ to be the analogous operators on the restriction of the word to the letters $\{i,i+1,i',i+1'\}$. \end{defi} \begin{exam} We have $F_1(2112'3)=212'23$ and $F_2(2112'3)=31123$. \end{exam} We therefore have a sort of ``doubled crystal'' structure on tableaux of a given shape and rectification shape. Two examples are shown in Figure~\ref{fig:crystal}. \begin{figure}[htb]\centering \includegraphics[height=8cm]{figures/crystalB.pdf} \hspace{1cm} \includegraphics[height=8cm]{figures/crystalB-new3.pdf} \caption{\label{fig:crystal} \emph{Left:} The crystal graph for $\lambda = (3,1)$ with operators $F_i$, $F_i'$ for $i\in\{1,2\}$. The $F_1$ and $F_1'$ arrows are respectively the red solid and dashed arrows (pointing leftwards), and $F_2$ and $F_2'$ are the blue solid and dashed arrows (pointing rightwards). \emph{Right:} The graph structure underlying the crystal for $\lambda = (4,2,1)$, with vertices arranged according to their weight (``clustered'' vertices have the same weight).} \end{figure} \begin{defi} Let $\ShST(\lambda/\mu,m)$ be the set of all shifted semistandard tableaux of shape $\lambda/\mu$ in the alphabet $\{1',1,\ldots,m',m\}$ in canonical form. \end{defi} \begin{prop} \label{prop:tableau-crystals} The unique element $T \in \ShST(\lambda,m)$ for which $E_i(T) = E'_i(T) = \varnothing$ for all $i$ is the tableau $T_{\HIGH}$, whose $i$-th row has all entries equal to $i$ \textup{(}for all $i$\textup{)}. It follows that every element of $\ShST(\lambda,m)$ can be obtained from every other by some sequence of operations $E_i$, $E_i'$, $F_i$, and $F_i'$ \textup{(}for various $i\in \{1,\ldots,m-1\}$\textup{)}. \end{prop} We call the graph associated to $\ShST(\lambda,m)$ a \emph{shifted tableau crystal}. We will give a more precise definition in the next section. \begin{proof} Let $T \in \ShST(\lambda,m)$ be any tableau. It suffices to transform $T$ to $T_{\HIGH }$ using a sequence of $E_i,E_i'$ operators. If $T \ne T_{\HIGH }$, let $i$ be the smallest integer such that the $i$-th row contains an entry larger than $i$. Let $j$ be the largest entry of row $i$. The $(j-1,j)$ subword of $w$ is not ballot (since its last letter is $j$ or $j'$), hence by Proposition~\ref{prop:ballot-iff-killed}, at least one of $E_{j-1}(T)$ or $E'_{j-1}(T)$ is nonzero and has higher weight. Since the set of possible weights is finite and $T_{\HIGH }$ is the unique tableau with weight $\lambda$, and this weight is highest, we must reach $T_{\HIGH }$ after a composition of finitely-many $E'$ and $E$ operators for various indices. \end{proof} The shifted tableaux crystals are ``universal'' in the following sense. Let $S$ be any finite set of words or tableaux in the alphabet $\{1',1, \ldots, m', m\}$, closed under $E_i, E'_i, F_i$ and $F'_i$ for $i = 1, \ldots, m-1$. (The main examples are $S = \ShST(\lambda/\mu,m)$, or the set of all words of a given length.) We will call $S$ a \emph{shifted word crystal}. Consider the graph structure on $S$ with edges labeled $i,i'$ corresponding to these operators. \begin{coro} \label{cor:unique-highest-weight} Each connected component of $S$ has a unique highest-weight element $s^*$, and is isomorphic, as a weighted, edge-labeled graph, to the shifted tableau crystal $\ShST(\lambda,m)$, where $\lambda = \wt (s^*)$. \end{coro} \begin{proof} We may assume $S$ is connected. By coplacticity, $S$ has the same weighted, labeled graph structure as the shifted tableau crystal obtained by replacing each $w \in S$ by its rectification. The statement now follows from Proposition~\ref{prop:tableau-crystals}. \end{proof} A more precise statement is that the connected components of $S$ are shifted dual equivalence classes. \begin{coro} Each connected component of $\B=\ShST(\lambda/\mu,m)$, or of a shifted word crystal, is a shifted dual equivalence class. \end{coro} \begin{proof} Since the crystal operators are coplactic, any two elements in the same connected component are dual equivalent. Then, by Corollary~\ref{cor:unique-highest-weight}, the connected component contains the unique Littlewood--Richardson element of the dual equivalence class. Thus, conversely, if two elements are dual equivalent, they are connected (via the highest-weight element). \end{proof} \subsection{Embedded type A Kashiwara crystals} We now show that the primed and unprimed operators, considered independently, form type A Kashiwara crystals. We first recall the definition of an abstract Kashiwara crystal over the $\GL_m$ root system. (Note: these are defined for general root systems in~\cite{Kashiwara}, and we state the restricted definition below.) \begin{defi} An (abstract) \emph{Kashiwara crystal} (for $\GL _m$) is a nonempty set $\B$ together with maps \[ \begin{gathered} e_i,f_i:\B\to \B\cup \{\varnothing\}, \\ \varepsilon_i,\varphi_i:\B\to \mathbb{Z}\cup \{-\infty\}, \\ \wt:\B\to \mathbb{Z}^m \end{gathered} \] where $i\in \{1,\ldots,m-1\}$, satisfying the following axioms. \begin{enumerate}[label = K\arabic*., ref=K\arabic*] \item\label{defi6.7_K1} %[K1.] If $X,Y\in \B$ then $e_i(X)=Y$ if and only if $f_i(Y)=X$. If this is the case then \begin{align*} \varepsilon_i(Y)&=\varepsilon_i(X)-1 \\ \varphi_i(Y)&=\varphi_i(X)+1 \\ \wt (Y)&=\wt (X)+\alpha_i \end{align*} where $\alpha_i$ is the weight vector $(0,0,\ldots,0,1,-1,0,0,\ldots,0)$ having $1$ in the $i$th position and $-1$ in the $(i+1)$st position. \item\label{defi6.7_K2} %[K2.] For any $i\in \{1,\ldots,m-1\}$ and any $X\in \B$, we have \[ \varphi_i(X)=\langle \wt (X),\alpha_i\rangle+\varepsilon_i(X) \] where $\langle,\rangle$ is the standard dot product on vectors. \item\label{defi6.7_K3} %[K3.] If $\varphi_i(X)=-\infty$ then $\varepsilon_i(X)=-\infty$ and vice versa. Moreover if this is the case then $e_i(X)=f_i(X)=\varnothing$. \end{enumerate} \end{defi} \noindent We will use the same auxiliary functions for two overlapping crystal structures. \begin{defi}\label{def:crystal} Let $\B=\ShST(\lambda/\mu,m)$. For $T\in \B$, we let $\wt (T)$ be the weight, and for $i=1, \ldots, m-1$ we let \[ (\varphi_i(T),\varepsilon_i(T)) := (x^{(i)},y^{(i)}) \] be the coordinates of the endpoint of the $i,i+1$ lattice walk associated to $T$.\end{defi} \begin{prop} The data of Definition~\ref{def:crystal}, with $e_i=E_i$ and $f_i=F_i$ \textup{(}or $e_i=E'_i$ and $f_i=F'_i$\textup{)}, satisfies the axioms of a Kashiwara crystal. \end{prop} \begin{proof} Since $-\infty$ is not an output of either $\varepsilon_i$ or $\varphi_i$, we do not need to check axiom~\ref{defi6.7_K3}. For axiom~\ref{defi6.7_K1}, we know that $E_i$ and $F_i$ are partial inverses, as are $E'_i, F'_i$. The claim about the weight function follows from the definitions, and the claims about $\varphi_i,\varepsilon_i$ are just Corollary~\ref{cor:F-on-walk} (for $E_i,F_i$) and Proposition~\ref{prop:primed-lattice-endpoint} (for $E_i', F_i'$). Finally, axiom~\ref{defi6.7_K2} follows directly from the definition of the lattice walk: we have \begin{align*} \langle \wt (T),\alpha_i\rangle &= \wt(T)_i-\wt(T)_{i+1} \\ &= \#\{i',i \text{ steps}\} - \#\{i+1',i+1 \text{ steps}\}, \end{align*} and we wish to show that this difference is equal to \[ \varphi_i(T)-\varepsilon_i(T) = x^{(i)}-y^{(i)}. \] But each $i$ or $i'$ step either increments $x$ or decrements $y$, and each $i+1$ or $i+1'$ does the opposite. Thus Axiom~\ref{defi6.7_K2} is satisfied. \end{proof} \section{Characters and Schur \texorpdfstring{$Q$}{Q}-functions}\label{sec:characters} We now define characters of our crystals, recovering many of the combinatorial properties of Schur $Q$-functions (and their duals, Schur $P$-functions). \begin{defi} The \emph{character} of a word $\hat{w}$, or of a tableau $T$ with reading word $\hat{w}$,~is \[ \chi(T):=\sum_{w\in \hat{w}}x^{\wt (w)}, \] where $x^{\alpha}=x_1^{\alpha_1}x_2^{\alpha_2}\cdots $ for any tuple $\alpha$. This is just $2^{\ell(\wt (w))}x^{\wt (\hat{w})}$, where $\ell(\wt (w))$ is the number of nonzero parts of $\wt (w)$. The \emph{character} of a collection of words or tableaux is the sum of the characters of its entries. \end{defi} The Schur $Q$-functions and Schur $P$-functions are certain specializations of Hall--Littlewood polynomials which live in $\Lambda_{\mathbb{Q}}(X)=\Lambda_{\mathbb{Q}}(x_1,x_2,\ldots)$, the ring of symmetric functions over $\mathbb{Q}$ (see~\cite{Macdonald} for a thorough introduction to symmetric function theory). More precisely, they are dual bases for the subring $\Gamma\subset \Lambda_{\QQ}(X)$ generated by the odd-degree power sum symmetric functions \[ p_k(X)=x_1^k+x_2^k+x_3^k+\cdots,\hspace{1cm} k=1,3,5,7,\ldots. \] (See~\cite{Stembridge}.) First defined by Schur~\cite{Schur}, the Schur $Q$- and $P$-functions were later shown to exhibit the following combinatorial formulas in~\cite{Stembridge}. \begin{defi} Let $\lambda/\mu$ be a shifted skew shape. Define $\ShST_Q(\lambda/\mu,m)$ to be the set of all (not necessarily canonical) shifted semistandard tableaux of shape $\lambda/\mu$ in alphabet $\{1',1,\ldots,m',m\}$. Also define $\ShST_P(\lambda/\mu,m)$ to be the set of all shifted semistandard tableaux of shape $\lambda/\mu$ with entries from the alphabet $\{1',1,\ldots,m',m\}$ in which primes are not allowed on the staircase diagonal. The tableaux in $\ShST_Q(\lambda/\mu,m)$ and $\ShST_P(\lambda/\mu,m)$ are not assumed to be in a canonical form, \ie $i'$ is allowed at the start of the $i,i'$-subword. \end{defi} \begin{defi}\label{def:SchurQ} The \emph{Schur $Q$-function} $Q_{\lambda/\mu}$ is the symmetric function given by \[ Q_{\lambda/\mu}(X)=\sum_{T\in \ShST_Q(\lambda/\mu)} x^{\wt (T)}. \] For straight shifted shapes $\lambda$, the \emph{Schur $P$-function} $P_{\lambda}$ is given by \[ P_{\lambda}(X)=\sum_{T\in \ShST_P(\lambda)} x^{\wt (T)}. \] \end{defi} \begin{prop} The character of $\B_{\lambda/\mu} = \ShST(\lambda/\mu)$ is the Schur $Q$-function $Q_{\lambda/\mu}(x)$. In other words, we have \[ Q_{\lambda/\mu}=\sum_{T\in \B_{\lambda/\mu}} \chi(T). \] \end{prop} \begin{proof} This follows immediately from the definition of the character, Definition~\ref{def:SchurQ}, and Proposition~\ref{prop:tableau-crystals}. \end{proof} A skew shifted tableau is \defn{Littlewood--Richardson} if it is in canonical form and its reading word is ballot (or equivalently, if it is highest weight for the operators $E_i,E_i'$). It was shown in~\cite{Stembridge} that the Schur $Q$-functions satisfy the following Littlewood--Richardson rule: \[ Q_\mu Q_\nu=\sum 2^{\ell(\mu)+\ell(\nu)-\ell(\lambda)}f^{\lambda}_{\mu\nu}Q_\lambda \] where $f^{\lambda}_{\mu\nu}$ is the number of skew shifted Littlewood--Richardson tableaux of shape $\lambda/\mu$ and weight $\nu$. It is easy to see that this is equivalent to the rule \[ P_\mu P_\nu=\sum f^{\lambda}_{\mu\nu}P_\lambda \] as well. Since $Q$ and $P$ are dual under the Hall inner product on $\Lambda_\mathbb{Q}$, these coefficients also appear in the expansion of skew Schur $Q$-functions in terms of straight shapes: \begin{equation} \label{eqn:skew-LR-schurQ} Q_{\lambda/\mu} = \sum_\nu f_{\mu\nu}^\lambda Q_\nu. \end{equation} \begin{rema} The definitions of Schur $P$- and $Q$-functions involve skew shifted semistandard tableaux that are not required to be in canonical form. The importance of canonical form is seen when considering multiplication of Schur $P$-functions. Most naturally, the canonical form condition appears in the iterated Pieri rule for Schur $P$-functions: \[ P_\mu P_{a_1} \dots P_{a_m} = \sum_\lambda L^{\lambda/\mu}_{(a_1,\dots,a_m)} P_\lambda \,, \] where $L^{\lambda/\mu}_{(a_1,\dots,a_m)}$ is the number of shifted semistandard tableaux in canonical form, of shape $\lambda/\mu$, in the alphabet $\{1',1,\ldots,m',m\}$, with weight $(a_1,...,a_m)$. Likewise, the definition of skew shifted Littlewood--Richardson tableau requires the tableau to be in canonical form. \end{rema} By Corollary~\ref{cor:unique-highest-weight} and~\ref{prop:ballot-iff-killed}, our crystal graphs give a combinatorial interpretation of this last equation in terms of the connected components of the crystal for shape $\lambda/\mu$. \begin{coro} By decomposing $\B=\ShST(\lambda/\mu,m)$ into its connected components, we get an isomorphism \[ \ShST(\lambda/\mu,m) = \bigsqcup_\nu \ShST(\nu,m)^{f_{\mu,\nu}^\lambda}. \] Comparing characters recovers equation~\eqref{eqn:skew-LR-schurQ}. \end{coro} We also obtain a new combinatorial proof of symmetry of the Schur $Q$-functions. \begin{coro} \label{cor:symmetry-schurQ} The function $Q_{\lambda/\mu}(x_1,x_2,\ldots)$ is symmetric in the variables $x_i$. \end{coro} \begin{proof} It suffices to show that $Q_{\lambda/\mu}$ is symmetric under swapping $x_i,x_{i+1}$ for each $i$. Consider the crystal $\B=\ShST(\lambda/\mu)$ whose character is $Q_{\lambda/\mu}$, and consider only the operators $F_i$ and $F_i'$ for a single fixed value of $i$. These operators decompose $\B$ into a disjoint union of two-row and one-row diagrams for $F_i,F_i'$. Within a given such diagram, the weights $x^{\wt(T)}$ of the entries $T$ are constant except for the exponents of $x_i$ and $x_{i+1}$. Factoring out the other variables, we see that in two-row diagrams, we obtain a symmetric sum of monomials \[ 4x_i^a x_{i+1}^b+8x_i^{a-1}x_{i+1}^{b+1}+\cdots+ 8x_i^{b+1}x_{i+1}^{a-1}+4x_i^{b}x_{i+1}^a \] for some $a$ and $b$, and in one-row diagrams we obtain a symmetric sum of monomials \[ 2x_i^a x_{i+1}^b + 4x_i^{a-1}x_{i+1}^{b+1}+\cdots+ 4x_i^{b+1}x_{i+1}^{a-1}+2x_i^{b}x_{i+1}^a. \] Thus the entire polynomial is symmetric in $x_i$ and $x_{i+1}$ as desired. \end{proof} \longthanks{We thank Richard Green, Anne Schilling, David Speyer, John Stembridge and Mark Haiman for helpful conversations pertaining to this work. Computations in Sage~\cite{sagemath} were also useful for analyzing the combinatorics of the operators.} \bibliographystyle{amsplain-ac} \bibliography{ALCO_Gillespie_207} \end{document}