%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2018}
\articlenumber{81}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{pstricks,pst-node,graphicx}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Environments 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{xca}[theorem]{Exercise}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  MACROS for this particular document
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\inv}{\ensuremath\mathrm{inv}}
\newcommand{\coinv}{\ensuremath\mathrm{coinv}}
\newcommand{\maj}{\ensuremath\mathrm{maj}}
\newcommand{\comaj}{\ensuremath\mathrm{comaj}}

\newcommand{\Des}{\ensuremath\mathrm{Des}}
\newcommand{\des}{\ensuremath\mathrm{des}}
\newcommand{\wt}{\ensuremath\mathrm{wt}}

\newcommand{\SSYT}{\ensuremath\mathrm{SSYT}}
\newcommand{\SSKT}{\ensuremath\mathrm{SSKT}}
\newcommand{\SSKD}{\ensuremath\mathrm{SSKD}}

\newcommand{\key}{\ensuremath\kappa}


%%%%%%%%%%%%%%%%%%%%%%
% macreau for tableaux
%%%%%%%%%%%%%%%%%%%%%%
\newlength\cellsize \setlength\cellsize{10\unitlength}

\savebox2{%
\begin{picture}(10,10)
\put(0,0){\line(1,0){10}}
\put(0,0){\line(0,1){10}}
\put(10,0){\line(0,1){10}}
\put(0,10){\line(1,0){10}}
\end{picture}}

\newcommand\cellify[1]{\def\thearg{#1}\def\nothing{}%
\ifx\thearg\nothing\vrule width0pt height\cellsize depth0pt%
  \else\hbox to 0pt{\usebox2\hss}\fi%
  \vbox to 10\unitlength{\vss\hbox to 10\unitlength{\hss$_{#1}$\hss}\vss}}

\newcommand\tableau[1]{\vtop{\let\\=\cr
\setlength\baselineskip{-10000pt}
\setlength\lineskiplimit{10000pt}
\setlength\lineskip{0pt}
\halign{&\cellify{##}\cr#1\crcr}}}


%% define your title in the usual way
\title[Crystal graphs, key tabloids, and nonsymmetric Macdonald
polynomials]{Crystal graphs, key tabloids, and \\ nonsymmetric Macdonald
polynomials}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sami Assaf\thanks{\href{mailto:shassaf@usc.edu}{shassaf@usc.edu}. Work supported by a grant from the Simons Foundation (Award 524477, S.A.).}\addressmark{1} \and Nicolle S. Gonz\'{a}lez\thanks{\href{mailto:nesandov@usc.edu}{nesandov@usc.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, University of Southern California, 3620 S. Vermont Ave., Los Angeles, CA 90089-2532, U.S.A.}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We construct a Demazure crystal for nonsymmetric Macdonald polynomials specialized at $t=0$, giving a new proof that these specialized nonsymmetric Macdonald polynomials are graded sums of Demazure characters.}

%% put your French abstract here, or comment this out if you don't have one
% \resume{French version here (or omit).}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Macdonald polynomials, Demazure characters, crystal graphs}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{81-Assaf-Gonzalez}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Introduction}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:introduction}

Macdonald \cite{Mac88} defined symmetric functions with two parameters $P_{\lambda}(X;q,t)$ indexed by partitions as the unique symmetric function basis satisfying certain triangularity (with respect to monomials in the variables $X=x_1,x_2,\ldots$) and orthogonality (with respect to a generalized Hall inner product) conditions. The coefficients of $P_{\lambda}(X;q,t)$ when written as a sum of monomials are rational functions in the parameters $q$ and $t$. Based on hand computations for partitions up to size $8$, Macdonald conjectured that the \emph{Kostka--Macdonald coefficients} $K_{\lambda,\mu}(q,t)$ defined by expanding the \emph{integral form} $J_{\mu}(X;q,t)$, a scalar multiple of the original $P_{\lambda}(X;q,t)$, into the plethystic Schur basis, 
\begin{equation}
  J_{\mu}(X;q,t) = \sum_{\lambda} K_{\lambda,\mu}(q,t) s_{\lambda}[X(1-t)],
  \label{e:Klamu}
\end{equation}
are polynomials in $q$ and $t$ with nonnegative integer coefficients.

Inspired by Garsia and Procesi \cite{GP92}, Garsia and Haiman \cite{GH93} constructed a bi-graded module for the symmetric group and conjectured that the Frobenius character is
\begin{equation}
  H_{\mu}(X;q,t) = J_{\mu}[X/(1-t); q, t],
  \label{e:Hmu}
\end{equation}
thus the Kostka--Macdonald coefficients give the Schur function expansion
of $H_{\mu}(X;q,t)$. This conjecture gives a representation theoretic
interpretation for the Kostka--Macdonald polynomials as the graded
coefficients of the irreducible decomposition of these modules. Haiman
\cite{Hai01} resolved both conjectures by analyzing the isospectral
Hilbert scheme of points in a plane, ultimately showing that it is
Cohen--Macaulay (and Gorenstein). 

The nonsymmetric Macdonald polynomials $E_{a}(X;q,t)$, introduced by Opdam \cite{Opd95} and Macdonald \cite{Mac96}, are indexed by weak compositions and form a basis for the full polynomial ring. They generalize Macdonald polynomials in the sense that
\begin{eqnarray*}
  E_{\lambda_n,\lambda_{n-1},\ldots,\lambda_1}(x_1,\ldots,x_n;q,t) & = & P_{\lambda}(x_1,\ldots,x_n;q,t), \\ 
  E_{0^m \times a}(x_1,\ldots,x_m,0,\ldots,0;q,t) & = & P_{\mathrm{sort}(a)}(x_1,\ldots,x_m;q,t),
\end{eqnarray*}
where $0^m \times a$ denotes the composition obtained by prepending $m$ $0$'s to $a$.

Generalizing Haglund's elegant combinatorial formula for $H_{\mu}(X;q,t)$
\cite{Hag04,HHL05}, Haglund, Haiman, and Loehr \cite{HHL08} gave a combinatorial formula for $E_{a}(X;q,t)$ as
\begin{equation}
  E_{a}(X;q,t) = \sum_{\substack{T:a\rightarrow [n] \\ \mathrm{non-attacking}}} q^{\maj(T)} t^{\coinv(T)} X^{\wt(T)}
  \prod_{c \neq \mathrm{left}(c)} \frac{1-t}{1 - q^{\mathrm{leg}(c)+1} t^{\mathrm{arm}(c)+1}},
  \label{e:Ea}
\end{equation}
where the sum is over certain positive integer fillings $T$ of the diagram of the composition $a$ and $\coinv$ and $\maj$ are nonnegative integer statistics. In stark contrast with the symmetric case, there are no known (or even conjectured) positivity results for the nonsymmetric Macdonald polynomials.

Demazure \cite{Dem74} generalized the Weyl character formula to certain submodules generated by extremal weight spaces under the action of a Borel subalgebra of a Lie algebra. These \emph{Demazure characters} $\key_a$, where $a = w \cdot \lambda$, for $w$ a permutation acting on the coordinates of a partition $\lambda$, arose in connection with Schubert calculus \cite{Dem74a}, and, in type A, also form a basis of the polynomial ring. Recent work of Assaf and Searles \cite{AS18} indicates that the type A Demazure characters are the most natural pull backs of Schur functions to the polynomial ring, in the sense that the combinatorics of the former stabilizes to that of the latter. Therefore, in the search for polynomial analogs of Schur positivity statements for nonsymmetric Macdonald polynomials, the natural basis for comparison is the Demazure characters. Recently, Assaf \cite{Ass-H} proved that the specialization $E_{a}(X;q,0)$ is a nonnegative sum of Demazure characters, and that this nonnegativity precisely parallels the Schur expansion of $P_{\lambda}(X;0,t)$. While the proof is purely combinatorial, the resulting formula is difficult to work with and, in practice, requires computing the fundamental slide polynomial \cite{AS17} expansion of $E_{a}(X;q,0)$.

In this abstract, we present a new combinatorial proof of the Demazure positivity of $E_{a}(X;q,0)$ that provides a representation theoretic interpretation for $E_{a}(X;q,0)$ as the character of a graded Demazure module and results in an explicit combinatorial formula for the Demazure coefficients. Our proof proceeds by constructing crystal operators \cite{Kas91} on fillings of a diagram that we prove generate a Demazure crystal, generalizing a recent result of Assaf and Schilling \cite{AS-D}. In Section~\ref{sec:crystal}, we review crystal graphs and Demazure truncations of them. In Section~\ref{sec:macdonald}, we review the combinatorial model for nonsymmetric Macdonald polynomials. Bringing these two ideas together, in Section~\ref{sec:demazure}, we define our Demazure crystal and, in Section~\ref{sec:highest}, deduce from it a formula for the Demazure expansion of $E_{a}(X;q,0)$. For further details, see \cite{AG}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Crystal graphs}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:crystal}

Irreducible polynomial representation of the general linear group $\mathrm{GL}_n$ are naturally indexed by partitions $\lambda$ of length $n$ with a basis naturally indexed by \emph{semistandard Young tableaux of shape $\lambda$}. These are fillings of the diagram of $\lambda$ from the alphabet $\{1,2,\ldots,n\}$ such that entries weakly increase along rows and strictly increase up columns. For example, the semi-standard Young tableaux of shape $(2,2,1,0)$ are shown in Figure~\ref{fig:SSYT}.

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c}
      \tableau{3 \\ 2 & 3 \\ 1 & 1} &
      \tableau{3 \\ 2 & 4 \\ 1 & 1} &
      \tableau{4 \\ 2 & 4 \\ 1 & 1} &
      \tableau{4 \\ 3 & 4 \\ 1 & 1} &
      \tableau{4 \\ 3 & 3 \\ 1 & 1} &
      \tableau{3 \\ 2 & 3 \\ 1 & 2} &
      \tableau{3 \\ 2 & 4 \\ 1 & 2} &
      \tableau{4 \\ 2 & 4 \\ 1 & 2} &
      \tableau{4 \\ 3 & 4 \\ 1 & 2} &
      \tableau{4 \\ 3 & 3 \\ 1 & 2} \\ \\
      \tableau{3 \\ 2 & 4 \\ 1 & 3} &
      \tableau{4 \\ 2 & 4 \\ 1 & 3} &
      \tableau{4 \\ 3 & 4 \\ 1 & 3} &
      \tableau{4 \\ 3 & 4 \\ 2 & 2} &
      \tableau{4 \\ 3 & 3 \\ 2 & 2} &
      \tableau{4 \\ 3 & 4 \\ 2 & 3} &
      \tableau{4 \\ 2 & 3 \\ 1 & 2} &
      \tableau{4 \\ 2 & 3 \\ 1 & 1} &
      \tableau{4 \\ 2 & 2 \\ 1 & 1} &
      \tableau{3 \\ 2 & 2 \\ 1 & 1} 
    \end{array}
  \end{displaymath}
  \caption{\label{fig:SSYT}The semi-standard Young tableaux of shape $(2,2,1,0)$.}
\end{figure}

Let $\SSYT_n(\lambda)$ denote the set of semi-standard Young tableaux of shape $\lambda$ over the alphabet $\{1,2,\ldots,n\}$. To each semi-standard Young tableau $T$, we associate the weak composition $\wt(T)$ whose $i$th part is the number of entries of $T$ equal to $i$.

The \emph{Schur polynomials} are the characters of these irreducible representations. They may be defined as the generating polynomial for semi-standard Young tableaux, 
\begin{equation}
  s_\lambda(x_1,\ldots,x_n) = \sum_{T \in \SSYT_n(\lambda)} x_1^{\wt(T)_1} \cdots x_n^{\wt(T)_n}.
\end{equation}

Kashiwara \cite{Kas91} introduced the notion of crystal bases in his study of the representation theory of quantized universal enveloping algebras at $q=0$. A \emph{crystal graph} is a directed, colored graph with vertex set given by the crystal basis of a quantum group and directed edges given by deformations of the Chevalley generators. There is an explicit combinatorial construction of the crystal graph, with raising and lowering operators denoted by $e_i$ and $f_i$, respectively, that act on tableaux \cite{KN94,Lit95}.

\begin{figure}[ht]
  \begin{displaymath}
      \begin{array}{cccccc}
        & & \rnode{B8}{\tableau{3 \\ 2 & 2 \\ 1 & 1}} & & & \\[3\cellsize]
        & & \rnode{B7}{\tableau{3 \\ 2 & 3 \\ 1 & 1 }} & \rnode{c7}{\tableau{4 \\ 2 & 2 \\ 1 & 1 }} & & \\[3\cellsize]
        \rnode{a6}{\tableau{3 \\ 2 & 3 \\ 1 & 2}} & & & \rnode{c6}{\tableau{4 \\ 2 & 3 \\ 1 & 1}} & \rnode{C6}{\tableau{3 \\ 2 & 4 \\ 1 & 1}} & \\[3\cellsize]
        & \rnode{b5}{\tableau{4 \\ 2 & 3 \\ 1 & 2}} & \rnode{B5}{\tableau{3 \\ 2 & 4 \\ 1 & 2}} & \rnode{c5}{\tableau{4 \\ 3 & 3 \\ 1 & 1}} & & \rnode{d5}{\tableau{4 \\ 2 & 4 \\ 1 & 1}} \\[3\cellsize]
        & \rnode{b4}{\tableau{4 \\ 3 & 3 \\ 1 & 2}} & \rnode{B4}{\tableau{3 \\ 2 & 4 \\ 1 & 3}} & & \rnode{c4}{\tableau{4 \\ 2 & 4 \\ 1 & 2}} & \rnode{d4}{\tableau{4 \\ 3 & 4 \\ 1 & 1}} \\[3\cellsize]
        \rnode{a3}{\tableau{4 \\ 3 & 3 \\ 2 & 2}} & & & \rnode{c3}{\tableau{4 \\ 3 & 4 \\ 1 & 2}} & \rnode{C3}{\tableau{4 \\ 2 & 4 \\ 1 & 3}} & \\[3\cellsize]
        & & \rnode{b2}{\tableau{4 \\ 3 & 4 \\ 2 & 2}} & & \rnode{c2}{\tableau{4 \\ 3 & 4 \\ 1 & 3}} & \\[3\cellsize]
        & & \rnode{b1}{\tableau{4 \\ 3 & 4 \\ 2 & 3}} & & & 
      \end{array} \hspace{6\cellsize}
      \begin{array}{cccccc}
        & & \rnode{XB8}{\tableau{3 \\ 2 & 2 \\ 1 & 1}} & & & \\[3\cellsize]
        & & \rnode{XB7}{\tableau{3 \\ 2 & 3 \\ 1 & 1 }} & \rnode{Xc7}{\tableau{4 \\ 2 & 2 \\ 1 & 1 }} & & \\[3\cellsize]
        \rnode{Xa6}{\tableau{3 \\ 2 & 3 \\ 1 & 2}} & & & \rnode{Xc6}{\tableau{4 \\ 2 & 3 \\ 1 & 1}} & \rnode{XC6}{\tableau{3 \\ 2 & 4 \\ 1 & 1}} & \\[3\cellsize]
        & \rnode{Xb5}{\tableau{4 \\ 2 & 3 \\ 1 & 2}} & \rnode{XB5}{\tableau{3 \\ 2 & 4 \\ 1 & 2}} & \rnode{Xc5}{\tableau{4 \\ 3 & 3 \\ 1 & 1}} & & \rnode{Xd5}{\tableau{4 \\ 2 & 4 \\ 1 & 1}} \\[3\cellsize]
        & \rnode{Xb4}{\tableau{4 \\ 3 & 3 \\ 1 & 2}} & & & \rnode{Xc4}{\tableau{4 \\ 2 & 4 \\ 1 & 2}} & \rnode{Xd4}{\tableau{4 \\ 3 & 4 \\ 1 & 1}} \\[3\cellsize]
        \rnode{Xa3}{\tableau{4 \\ 3 & 3 \\ 2 & 2}} & & & \rnode{Xc3}{\tableau{4 \\ 3 & 4 \\ 1 & 2}} & & \\[3\cellsize]
        & & \rnode{Xb2}{\tableau{4 \\ 3 & 4 \\ 2 & 2}} & & & \\[3\cellsize]
        & & & & & \tableau{ & \\ & \\ & }
      \end{array}
    \psset{nodesep=2pt,linewidth=.15ex}
    \ncline[linecolor=orange]{<-}  {b1}{b2} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{b1}{c2} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {b2}{a3} %\ncput*{1}
    \ncline[linecolor=orange]{<-}  {c2}{C3} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{b2}{c3} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {c3}{b4} %\ncput*{1}
    \ncline[linecolor=blue]{<-} {C3}{B4} %\ncput*{1}
    \ncline[linecolor=orange]{<-}  {C3}{c4} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{a3}{b4} %\ncput*{3}
    \ncline[linecolor=purple]{<-}{c3}{d4} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {c4}{B5} %\ncput*{1}
    \ncline[linecolor=blue]{<-} {d4}{c5} %\ncput*{1}
    \ncline[linecolor=orange]{<-}  {b4}{b5} %\ncput*{2}
    \ncline[linecolor=orange]{<-}  {B4}{B5} %\ncput*{2}
    \ncline[linecolor=orange]{<-}  {d4}{d5} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{b4}{c5} %\ncput*{3}
    \ncline[linecolor=purple]{<-}{c4}{d5} %\ncput*{3}
    \ncline[linecolor=purple]{<-}{b5}{c6} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {B5}{a6} %\ncput*{1}
    \ncline[linecolor=orange]{<-}  {c5}{c6} %\ncput*{2}
    \ncline[linecolor=blue]{<-} {d5}{C6} %\ncput*{1}
    \ncline[linecolor=purple]{<-}{B5}{C6} %\ncput*{3}
    \ncline[linecolor=orange]{<-}  {c6}{c7} %\ncput*{2}
    \ncline[linecolor=blue]{<-} {C6}{B7} %\ncput*{1}
    \ncline[linecolor=purple]{<-}{a6}{B7} %\ncput*{3}
    \ncline[linecolor=orange]{<-}  {B7}{B8} %\ncput*{2}
    \ncline[linecolor=blue]{<-} {c7}{B8} %\ncput*{1}
    %
    \ncline[linecolor=blue]{<-} {Xb2}{Xa3} %\ncput*{1}
    \ncline[linecolor=purple]{<-}{Xb2}{Xc3} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {Xc3}{Xb4} %\ncput*{1}
    \ncline[linecolor=orange]{<-}  {XC3}{Xc4} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{Xa3}{Xb4} %\ncput*{3}
    \ncline[linecolor=purple]{<-}{Xc3}{Xd4} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {Xc4}{XB5} %\ncput*{1}
    \ncline[linecolor=blue]{<-} {Xd4}{Xc5} %\ncput*{1}
    \ncline[linecolor=orange]{<-}  {Xb4}{Xb5} %\ncput*{2}
    \ncline[linecolor=orange]{<-}  {XB4}{XB5} %\ncput*{2}
    \ncline[linecolor=orange]{<-}  {Xd4}{Xd5} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{Xb4}{Xc5} %\ncput*{3}
    \ncline[linecolor=purple]{<-}{Xc4}{Xd5} %\ncput*{3}
    \ncline[linecolor=purple]{<-}{Xb5}{Xc6} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {XB5}{Xa6} %\ncput*{1}
    \ncline[linecolor=orange]{<-}  {Xc5}{Xc6} %\ncput*{2}
    \ncline[linecolor=blue]{<-} {Xd5}{XC6} %\ncput*{1}
    \ncline[linecolor=purple]{<-}{XB5}{XC6} %\ncput*{3}
    \ncline[linecolor=orange]{<-}  {Xc6}{Xc7} %\ncput*{2}
    \ncline[linecolor=blue]{<-} {XC6}{XB7} %\ncput*{1}
    \ncline[linecolor=purple]{<-}{Xa6}{XB7} %\ncput*{3}
    \ncline[linecolor=orange]{<-}  {XB7}{XB8} %\ncput*{2}
    \ncline[linecolor=blue]{<-} {Xc7}{XB8} %\ncput*{1}
  \end{displaymath}
  \caption{\label{fig:crystal}The crystal $\mathcal{B}(2,2,1,0)$ (left) and the Demazure crystal $\mathcal{B}_{2431}(2,2,1,0)$ (right), with edges $f_1 \color{purple}\swarrow$, 
  $f_2 \color{orange}\downarrow$, $f_3 \color{blue}\searrow$ defined by the lowering operators.}
\end{figure}

For a semi-standard Young tableau $T$, let $T|_{\leq c}$ denote the first $c$ columns of $T$. Given a positive integer $1 \leq i<n$, define indices:
\begin{displaymath}
  m_i(T,c) = \wt(T|_{\leq c})_{i} - \wt(T|_{\leq c})_{i+1}, \hspace{3em}
  m_i(T) = \max_{c>0} \left( m_i(T,c) \right) . 
\end{displaymath}
Observe that if $m_i(T)>0$ and $c$ is the leftmost column that attains this maximum, then there is an $i$ and no $i+1$ in column $c$ of $T$.

\begin{definition}
  Given an integer $1 \leq i<n$, define the \emph{lowering operator} $f_i$ on semi-standard Young tableaux as follows: if $m_i(T) \leq 0$, then $f_i(T)=0$; otherwise, for $c$ the smallest index such that $m_i(T,c) = m_i(T)$, $f_i(T)$ changes the $i$ in column $c$ of $T$ to $i+1$.
  \label{def:lower}
\end{definition}

For example, Figure~\ref{fig:crystal} shows the lowering operators on $\SSYT_4(2,2,1,0)$.

%\begin{definition}
%  Given an integer $1 \leq i<n$, define the \emph{raising operator} $e_i$ on $\SSYT_n(\lambda)$ as follows: let $c$ be the rightmost column of $T$ $m_i(T,c) = m_i(T)$. If $c = \lambda_1$, then $e_i(T)=0$; otherwise, $e_i(T)$ changes the $i+1$ in column $c+1$ of $T$ to $i$.
%  \label{def:raise}
%\end{definition}
%
%The raising and lowering operators are inverses whenever both act nontrivially. 

Denote the highest weight crystal for a partition $\lambda$ by $\mathcal{B}(\lambda)$. Then
\begin{equation}
  \mathrm{ch} \mathcal{B}(\lambda) = \sum_{b \in \mathcal{B}(\lambda)} x_1^{\wt(b)_1} \cdots x_n^{\wt(b)_n} = s_{\lambda}(x_1,\ldots,x_n) ,
\end{equation}
which is the character of the irreducible representation of highest weight $\lambda$. 

Demazure \cite{Dem74} generalized the Weyl character formula to certain submodules generated by extremal weight spaces under the action of a Borel subalgebra of a Lie algebra. These \emph{Demazure characters} arose in connection with Schubert calculus \cite{Dem74a}. \emph{Demazure crystals} are certain truncations conjectured by Littelmann \cite{Lit95} and proved by Kashiwara \cite{Kas93} to generalize Demazure characters. Given a subset $X \subseteq \mathcal{B}(\lambda)$, we define $\mathfrak{D}_i$ by
\begin{equation}
  \mathfrak{D}_i X = \{ b \in \mathcal{B}(\lambda) \mid e_i^k(b) \in X \mbox{ for some } k \geq 0 \},
\end{equation}
where $e_i$ denotes the \emph{raising operator} satisfying $e_i(b) = b^{\prime}$ if and only if $f_i(b^{\prime})=b$ for all $b, b^{\prime} \in \mathcal{B}(\lambda)$.

These operators satisfy the braid relations for the symmetric group, and so for a permutation $w$ with reduced expression $w=s_{i_k} \cdots s_{i_1}$, we may define
\begin{equation}
  \mathcal{B}_w(\lambda) = \mathfrak{D}_{i_k} \cdots \mathfrak{D}_{i_1} \{ u_\lambda \},
  \label{e:BwL}
\end{equation}
where $u_\lambda$ is the highest weight element in $\mathcal{B}(\lambda)$; that is, $e_i(u_\lambda)=0$ for all $i$. For example, Figure~\ref{fig:crystal} shows the Demazure crystal for $w = 2431$ and $\lambda = (2,2,1,0)$.

\begin{theorem}[\cite{Kas93}]
  Given a weak composition $a$, the Demazure character $\key_a$ is given by
  \begin{equation}
    \key_a = \sum_{b \in \mathcal{B}_{w(a)}(\mathrm{sort}(a))} x_1^{\wt(b)_1} \cdots x_n^{\wt(b)_n} = \mathrm{ch} \mathcal{B}_{w(a)}(\mathrm{sort}(a)),
  \end{equation}
  where $\mathrm{sort}(a)$ is the partition sorting of $a$ and $w(a)$ is the shortest permutation that sorts $a$.  
  \label{thm:dem-crystal}
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Macdonald polynomials}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:macdonald}

Macdonald's symmetric functions $P_{\lambda}(X;q,t)$ \cite{Mac88} are two parameter generalizations of classical symmetric functions that simultaneously generalize the Hall--Littlewood symmetric functions $H_{\lambda}(X;t) = P_{\lambda}(X;0,t)$ and the Jack symmetric functions $J_{\lambda,\alpha}(X) = \lim_{t \rightarrow 1} P_{\lambda}(X;t^{\alpha},t)$. The nonsymmetric Macdonald polynomials $E_a(x_1,\ldots,x_n;q,t)$ were introduced by Opdam \cite{Opd95} and Macdonald \cite{Mac96}. The symmetric Macdonald polynomials are a special case of their nonsymmetric analogs, 
\begin{equation}
  E_{\lambda_n,\lambda_{n-1},\ldots,\lambda_1}(x_1,\ldots,x_n;q,t) = P_{\lambda}(x_1,\ldots,x_n;q,t).
\end{equation}

Haglund, Haiman and Loehr \cite{HHL08} gave a combinatorial formula for the monomial expansion of nonsymmetric Macdonald polynomials as follows.

Two cells of a diagram are \emph{attacking} if they lie in the same column or if they lie in adjacent columns with the cell on the left strictly higher than the cell on the right. A filling is \emph{non-attacking} if no two attacking cells have the same value.

Given a non-attacking filling $T$, define the major index of $T$, denoted by $\maj(T)$, to be the sum of the legs of all cells $c$ such that the entry in $c$ is strictly greater than the entry immediately to its left. A \emph{triple} is a collection of three cells with two row adjacent and either (Type I) the third cell is above the left and the lower row is strictly longer, or (Type II) the third cell is below the right and the higher row is weakly longer. The \emph{orientation} of a triple is determined by reading the entries of the cells from smallest to largest. A \emph{co-inversion triple} is a Type I triple oriented counterclockwise or a Type II triple oriented clockwise. For example, the filling $T$ in Figure~\ref{fig:key-fill} is non-attacking, with $\maj(T) = 2+1 = 3$ and $\coinv(T)=2$. 

\begin{figure}[ht]
  \begin{displaymath}
    \tableau{ 5 & 5 \\ \\ \\ 3 & 4 & 2 \\ 2 \\ 1 & 6 }
    \hspace{6\cellsize}
    \tableau{ 5 &  \\ \\ \\ 3 & 4 &  \\  \\  & }
    \hspace{-2\cellsize}
    \raisebox{-1.25\cellsize}{$\circlearrowleft$}
    \hspace{3\cellsize}
    \raisebox{-4\cellsize}{$\circlearrowright$}
    \hspace{-1\cellsize}
    \tableau{  &  \\ \\ \\ 3 & 4 &  \\  \\  & 6 }
  \end{displaymath}
  \caption{\label{fig:key-fill}A non-attacking filling of the diagram for $(2,1,3,0,0,2)$ with the two co-inversion triples noted to the right.}
\end{figure}

\begin{theorem}[\cite{HHL08}]
  The nonsymmetric Macdonald polynomial $E_{a}(x_1,\ldots,x_n;q,t)$ is given by
  \begin{equation}
    E_{a}(X;q,t) = \sum_{\substack{T:a\rightarrow [n] \\ \mathrm{non-attacking}}} q^{\maj(T)} t^{\coinv(T)} X^{\wt(T)}
    \prod_{c \neq \mathrm{left}(c)} \frac{1-t}{1 - q^{\mathrm{leg}(c)+1} t^{\mathrm{arm}(c)+1}} .
  \end{equation}
  \label{thm:mac}
\end{theorem}

We consider the specialization at $t=0$, in which case the product becomes $1$, and the only terms that survive are those $T$ with $\coinv(T)=0$. 

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c@{\hskip \cellsize}c}
      \vline\tableau{4 & 4 \\ 3 \\ 2 & 2 \\ & } & 
      \vline\tableau{4 & 4 \\ 3 \\ 2 & 1 \\ & } & 
      \vline\tableau{4 & 4 \\ 3 \\ 1 & 1 \\ & } & 
      \vline\tableau{4 & 4 \\ 2 \\ 1 & 1 \\ & } & 
      \vline\tableau{4 & 4 \\ 1 \\ 2 & 2 \\ & } & 
      \vline\tableau{4 & 3 \\ 3 \\ 2 & 2 \\ & } & 
      \vline\tableau{4 & 3 \\ 3 \\ 2 & 1 \\ & } & 
      \vline\tableau{4 & 3 \\ 3 \\ 1 & 1 \\ & } &
      \vline\tableau{4 & 3 \\ 2 \\ 1 & 1 \\ & } & 
      \vline\tableau{4 & 3 \\ 1 \\ 2 & 2 \\ & } \\ \\
      \vline\tableau{4 & 2 \\ 3 \\ 2 & 1 \\ & } & 
      \vline\tableau{4 & 2 \\ 3 \\ 1 & 1 \\ & } & 
      \vline\tableau{4 & 2 \\ 2 \\ 1 & 1 \\ & } &       
      \vline\tableau{3 & 3 \\ 2 \\ 1 & 1 \\ & } & 
      \vline\tableau{3 & 3 \\ 1 \\ 2 & 2 \\ & } & 
      \vline\tableau{3 & 2 \\ 2 \\ 1 & 1 \\ & } &
      \vline\tableau{4 & 4 \\ 2 \\ 1 & 3 \\ & } & 
      \vline\tableau{3 & 3 \\ 2 \\ 1 & 4 \\ & } & 
      \vline\tableau{3 & 2 \\ 2 \\ 1 & 4 \\ & } & 
      \vline\tableau{3 & 1 \\ 2 \\ 1 & 4 \\ & } 
    \end{array}
  \end{displaymath}
  \caption{\label{fig:SSKD}The semi-standard key tabloids of shape $(0,2,1,2)$.}
\end{figure}

\begin{definition}[\cite{Ass-H}]
  The \emph{semi-standard key tabloids of shape $a$}, denoted by $\SSKD(a)$, are the non-attacking fillings of the diagram of $a$ with no co-inversion triples.
  \label{def:tabloid}
\end{definition}

For example, the $20$ semi-standard key tabloids of shape $(0,2,1,2)$ are given in Figure~\ref{fig:SSKD}. With this terminology, the specialized nonsymmetric Macdonald polynomial is 
\begin{equation}
  E_{a}(x_1,\ldots,x_n;q,0) = \sum_{T \in \SSKD(a)} q^{\maj(T)} x_{1}^{\wt(T)_1} \cdots x_{n}^{\wt(T)_n} .
  \label{e:nsym-hall}
\end{equation}
Define the \emph{nonsymmetric Kostka--Foulkes polynomial} $K_{a,b}(q)$ by the expansion
\begin{equation}
  E_{b}(X;q,0) = \sum_{a} K_{a,b}(q) \key_{a}(X).
  \label{e:cKM}
\end{equation}
In \cite{Ass-H}, Assaf uses weak dual equivalence \cite{Ass-W} to prove $K_{a,b}(q) \in \mathbb{N}[q]$. 

\begin{theorem}[\cite{Ass-H}]
  The specialized nonsymmetric Macdonald polynomial $E_{a}(x_1,\ldots,x_n;q,0)$ is a positive graded sum of Demazure characters.
  \label{thm:HL-key}
\end{theorem}

While the proof in \cite{Ass-H} is combinatorial, the interpretation for
$K_{a,b}(q)$ comes as the $\maj$-weighted number of weak dual equivalence
classes on standard key tabloids of shape $b$ that have type $a$. This
requires computing each equivalence class in its entirety. Thus we desire
a direct formula analogous to that for the Kostka--Foulkes polynomials $K_{\lambda,\mu}(0,t)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Demazure crystal on key tabloids}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:demazure}

Generalizing the crystal constructions on Young tableaux, we give a new proof of Theorem~\ref{thm:HL-key} by constructing an explicit Demazure crystal on semi-standard key tabloids as follows. For a semi-standard key tabloid $T$, let $w(T)$ denote the word obtained by reading columns of $T$ right to left, and reading each column top to bottom. Given a positive integer $1 \leq i<n$ and a word $w$ of length $k$, define indices:
\begin{displaymath}
  M_i(w,j) = \wt(w_{j}\cdots w_{k})_{i+1} - \wt(w_{j}\cdots w_{k})_{i}, \hspace{2em}
  M_i(w) = \max_{j>0} \left( M_i(w,j) \right) . 
\end{displaymath}

%\vspace{-\baselineskip}

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{cccccc@{\hskip 4\cellsize}cc}
      & & \rnode{b1}{\vline\tableau{3 & 2 \\ 2 \\ 1 & 1 \\ & }} & & & & & \\[3.5\cellsize]
      & & \rnode{b2}{\vline\tableau{3 & 3 \\ 2 \\ 1 & 1 \\ & }} & & \rnode{c2}{\vline\tableau{4 & 2 \\ 2 \\ 1 & 1 \\ & }} & & & \\[3.5\cellsize]
      \rnode{a3}{\vline\tableau{3 & 3 \\ 1 \\ 2 & 2 \\ & }} & & & \rnode{c3}{\vline\tableau{4 & 3 \\ 2 \\ 1 & 1 \\ & }} & \rnode{C3}{\vline\tableau{4 & 2 \\ 3 \\ 1 & 1 \\ & }} & & & \rnode{X3}{\vline\tableau{3 & 1 \\ 2 \\ 1 & 4 \\ & }} \\[3.5\cellsize]
      & \rnode{b4}{\vline\tableau{4 & 3 \\ 1 \\ 2 & 2 \\ & }} & \rnode{B4}{\vline\tableau{4 & 2 \\ 3 \\ 2 & 1 \\ & }} & & \rnode{c4}{\vline\tableau{4 & 3 \\ 3 \\ 1 & 1 \\ & }} & \rnode{d4}{\vline\tableau{4 & 4 \\ 2 \\ 1 & 1 \\ & }} & \rnode{X4}{\vline\tableau{3 & 2 \\ 2 \\ 1 & 4 \\ & }} & \\[3.5\cellsize]
      & & \rnode{b5}{\vline\tableau{4 & 3 \\ 3 \\ 2 & 1 \\ & }} & \rnode{c5}{\vline\tableau{4 & 4 \\ 1 \\ 2 & 2 \\ & }} & & \rnode{d5}{\vline\tableau{4 & 4 \\ 3 \\ 1 & 1 \\ & }} & \rnode{X5}{\vline\tableau{3 & 3 \\ 2 \\ 1 & 4 \\ & }} & \\[3.5\cellsize]
      \rnode{a6}{\vline\tableau{4 & 3 \\ 3 \\ 2 & 2 \\ & }} & & & & \rnode{c6}{\vline\tableau{4 & 4 \\ 3 \\ 2 & 1 \\ & }} & & & \rnode{X6}{\vline\tableau{4 & 4 \\ 2 \\ 1 & 3 \\ & }} \\[3\cellsize]
      & & \rnode{b7}{\vline\tableau{4 & 4 \\ 3 \\ 2 & 2 \\ & }} & & & & & 
    \end{array}
    \psset{nodesep=2pt,linewidth=.15ex}
    \ncline[nodesepA=-2pt,linecolor=orange]{<-}  {b1}{b2} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{b1}{c2} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {b2}{a3} %\ncput*{1}
    \ncline[nodesepA=-2pt,linecolor=orange]{<-}  {c2}{C3} %\ncput*{2}
    \ncline[nodesepA=-2pt,linecolor=purple]{<-}{b2}{c3} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {c3}{b4} %\ncput*{1}
    \ncline[linecolor=blue]{<-} {C3}{B4} %\ncput*{1}
    \ncline[nodesepA=-2pt,linecolor=orange]{<-}  {C3}{c4} %\ncput*{2}
    \ncline[nodesepA=-2pt,linecolor=purple]{<-}{a3}{b4} %\ncput*{3}
    \ncline[linecolor=purple]{<-}{c3}{d4} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {c4}{b5} %\ncput*{1}
    \ncline[linecolor=blue]{<-} {d4}{c5} %\ncput*{1}
    \ncline[nodesepA=-2pt,linecolor=orange]{<-}  {B4}{b5} %\ncput*{2}
    \ncline[nodesepA=-2pt,linecolor=orange]{<-}  {d4}{d5} %\ncput*{2}
    \ncline[linecolor=purple]{<-}{b4}{c5} %\ncput*{3}
    \ncline[nodesepA=-2pt,linecolor=purple]{<-}{c4}{d5} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {b5}{a6} %\ncput*{1}
    \ncline[nodesepA=-2pt,linecolor=blue]{<-} {d5}{c6} %\ncput*{1}
    \ncline[linecolor=purple]{<-}{b5}{c6} %\ncput*{3}
    \ncline[linecolor=blue]{<-} {c6}{b7} %\ncput*{1}
    \ncline[linecolor=purple]{<-}{a6}{b7} %\ncput*{3}
    %
    \ncline[nodesepA=-2pt,linecolor=blue]{<-} {X3}{X4} %\ncput*{1}
    \ncline[nodesepA=-2pt,linecolor=orange]{<-}  {X4}{X5} %\ncput*{2}
    \ncline[nodesepA=-2pt,linecolor=purple]{<-}{X5}{X6} %\ncput*{3}
  \end{displaymath}
  \caption{\label{fig:demazure}The Demazure crystal for $E_{(0,2,1,2)}(X;q,0)$ on $\SSKD(0,2,1,2)$, with edges $e_1 \color{blue}\nearrow$, $e_2 \color{orange}\uparrow$, $e_3 \color{purple}\nwarrow$ defined by raising operators.}
\end{figure}

\vspace{-\baselineskip}

\begin{definition}
  Given an integer $1 \leq i<n$, define the \emph{raising operator} $e_i$ on $\SSKD(a)$ as follows: if $M_i(w(T)) \leq 0$, then $e_i(T)=0$; otherwise, for $j$ the largest index such that $M_i(w(T),j) = M_i(w(T))$, and letting $c$ be the column in which the letter of $T$ corresponding to $w_j$ lies, $e_i(T)$ changes all column-consecutive $i+1$s weakly right of column $c$ of $T$ to $i$ and simultaneously changes all $i$s in the affected columns to $i+1$s.
  \label{def:raise-key}
\end{definition}

For example, Figure~\ref{fig:demazure} shows the raising operators on $\SSKD(0,2,1,2)$. Note that, unlike the crystal operators on semi-standard Young tableaux, the raising operator $e_i$ on semi-standard key tabloids might change the relative order of $i$ and $i+1$ within a given column. For $e_i$ acting on $T$, we might change $i$ above $i+1$ in some column to $i+1$ above $i$. Whenever this happens for a semi-standard key tabloid $T$, we say that $e_i$ \emph{flips} $T$.

\begin{theorem}
  The raising operators are well-defined, $\maj$-preserving maps $e_i : \SSKD(a) \rightarrow \SSKD(a) \cup \{0\}$ that are invertible on the subset of tabloids $T$ such that $e_i(T) \neq 0$.
  \label{thm:well-defined}
\end{theorem}

We also consider the \emph{lowering operators}, denoted by $f_i$, satisfying $f_i(T^{\prime})=T$ if and only if $e_i(T) = T^{\prime}$ for all $T, T^{\prime} \in \SSKD(a)$. We similarly say that $f_i$ \emph{flips} $T$ if within some column $f_i$ changes $i+1$ above $i$ to become $i$ above $i+1$.

In the case of semi-standard key tabloids with $\maj = 0$, i.e. the semi-standard key \emph{tableaux} \cite{Ass-H} that correspond to Mason's semi-skyline augmented fillings \cite{Mas09}, the raising operators in Definition~\ref{def:raise-key} are precisely those defined by Assaf and Schilling \cite{AS-D} in connection with Schubert polynomials.

Identifying each semi-standard key tabloid of shape $a$ with the diagram in the plane obtained by placing all cells with entry $i$ into row $i$, the semi-standard key tableaux are precisely the diagrams that arise by applying Kohnert's algorithm \cite{Koh91} to the composition diagram for $a$ \cite{Ass-W}. We define a \emph{rectification map} that sends an arbitrary diagram to a Kohnert diagram, which back at the level of tabloids, sends a semi-standard key tabloid to a semi-standard key tableau. This rectification map, illustrated in Figure~\ref{fig:rectify}, commutes with the raising operators, allowing us to give a bijective proof of the following using the Demazure crystal of Assaf and Schilling \cite{AS-D} on semi-standard key tableaux.

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{ccccccc}
      \vline\tableau{4 & 4 \\ 2 \\ 1 & 3 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\color{purple} e_3}{\longrightarrow}$} &
      \vline\tableau{3 & 3 \\ 2 \\ 1 & 4 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\color{orange} e_2}{\longrightarrow}$} &
      \vline\tableau{3 & 2 \\ 2 \\ 1 & 4 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\blue e_1}{\longrightarrow}$} &
      \vline\tableau{3 & 1 \\ 2 \\ 1 & 4 \\ & } \\
      \downarrow & & 
      \downarrow & & 
      \downarrow & & 
      \downarrow \\
      \vline\tableau{\times & \times \\ & \times \\ \times \\ \times} & &
      \vline\tableau{ & \times \\ \times & \times \\ \times \\ \times} & &
      \vline\tableau{ & \times \\ \times \\ \times & \times \\ \times} & &
      \vline\tableau{ & \times \\ \times \\ \times \\ \times & \times} \\
      \downarrow & & 
      \downarrow & & 
      \downarrow & & 
      \downarrow \\
      \vline\tableau{\times & \times \\ \times \\ \times \\ \times} & &
      \vline\tableau{ \times \\ \times & \times \\ \times \\ \times} & &
      \vline\tableau{ \times \\ \times \\ \times & \times \\ \times} & &
      \vline\tableau{ \times \\ \times \\ \times \\ \times & \times} \\
      \downarrow & & 
      \downarrow & & 
      \downarrow & & 
      \downarrow \\
      \vline\tableau{4 & 4 \\ 3 \\ 2 \\ 1 } & \raisebox{-1\cellsize}{$\stackrel{\color{purple} e_3}{\longrightarrow}$} &
      \vline\tableau{4 & 3 \\ 3 \\ 2 \\ 1 } & \raisebox{-1\cellsize}{$\stackrel{\color{orange} e_2}{\longrightarrow}$} &
      \vline\tableau{4 & 2 \\ 3 \\ 2 \\ 1 } & \raisebox{-1\cellsize}{$\stackrel{\blue e_1}{\longrightarrow}$} &
      \vline\tableau{4 & 1 \\ 3 \\ 2 \\ 1 } 
    \end{array}
  \end{displaymath}
  \caption{\label{fig:rectify}Examples of the rectification algorithm from semi-standard key tabloids, to diagrams, to Kohnert diagram (via rectification), to semi-standard key tableaux.}
\end{figure}

\begin{theorem}
  The raising operators define a Demazure crystal graph on $\SSKD(a)$. In particular, their generating polynomial $E_a(x_1,\ldots,x_n;q,0)$ is a graded sum of Demazure characters.
  \label{thm:mac-crystal}
\end{theorem}

For example, from Figure~\ref{fig:demazure}, we see that
\[ E_{(0,2,1,2)}(X;q,0) = \key_{(0,2,1,2)}(X) + q \key_{(1,1,1,2)}(X). \]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\section{Highest weights}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:highest}

A connected crystal graph $\mathcal{B}$ has a unique highest weight element $Y$ characterized by the property $e_i(Y) = 0$ for all $i$. Moreover, a component with highest weight element $Y$ is isomorphic to the highest weight crystal $\mathcal{B}(\lambda)$. In terms a characters, this becomes
\begin{equation}
  \mathrm{ch}\mathcal{B} = \sum_{b \in \mathcal{B}} x_1^{\wt(b)_1} \cdots x_n^{\wt(b)_n} = \sum_{\substack{Y\in\mathcal{B} \\ e_i(Y)=0 \ \forall \ i}} s_{\wt(Y)}(x_1,\ldots,x_n) .
\end{equation}

For Demazure crystal graphs, each connected component still has a unique highest weight element characterized as the unique element killed by all raising operators. Given our explicit raising operators on semi-standard key tabloid, these are easy to compute. For example, the six highest weight semi-standard key tabloids of shape $(0,3,0,2)$ are shown in Figure~\ref{fig:highest}, indicating that the Demazure crystal has six connected components and the Demazure expansion of $E_{(0,3,0,2)}(X;q,0)$ has six terms. Moreover, the $q$-weight of these terms is easily determined by the simple major index statistic.

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c}
      \vline\tableau{2 & 2 \\ & \\ 1 & 1 & 1 \\ & } & 
      \vline\tableau{2 & 3 \\ & \\ 1 & 1 & 1 \\ & } & 
      \vline\tableau{2 & 2 \\ & \\ 1 & 1 & 3 \\ & } & 
      \vline\tableau{2 & 1 \\ & \\ 1 & 3 & 2 \\ & } & 
      \vline\tableau{2 & 3 \\ & \\ 1 & 1 & 4 \\ & } & 
      \vline\tableau{2 & 4 \\ & \\ 1 & 3 & 1 \\ & } 
    \end{array}
  \end{displaymath}
  \caption{\label{fig:highest}The highest weights for the Demazure crystal for $E_{(0,3,0,2)}(X;q,0)$.}
\end{figure}

As powerful as highest weight elements are, they fall short of determining the truncation permutation $w$ for the given Demazure crystal. In particular, every Demazure truncation of $\mathcal{B}(\lambda)$ has the same highest weight. However, each $\mathcal{B}_w(\lambda)$ has a unique \emph{Demazure lowest weight element} $Z$ determined by $\wt(Z) \leq \wt(T)$ for all $T$ on the same connected component. While it is true that $f_i(Z)=0$ for all $i$, this property alone does not uniquely characterize it. For example, the tableau with reading word $42412$ in the Demazure crystal $\mathcal{B}_{2431}(2,2,1,0)$ shown in Figure~\ref{fig:crystal} is killed by all of the lowering operators, but it is not the global lowest weight element. In order to determine the \emph{Demazure lowest weight} $a$, given by $w \cdot \lambda$, we have the following algorithm to determine the Demazure lowest weight element from a given highest weight element.

For the following definition, given a semi-standard key tabloid $T$ and an index $i$, set $s_i(T) = f_i^{k}(T)$ where $k$ is maximal such that $f_i^k(T) \neq 0$. 

\begin{definition}
  Given a highest weight element $Y$ of the Demazure crystal on $\SSKD(a)$, the corresponding \emph{Demazure lowest weight element} $Z$ is constructed by letting $Z_0 = Y$, and for $m\geq 0$ defining $Z_{m+1}$ as follows. Find indices $i \leq j \leq k$ such that
  \begin{itemize}\addtolength{\itemsep}{-0.5\baselineskip}
  \item $j$ is minimal such that $f_j(Z_{m}) \neq 0$ and not a flip;
  \item $k$ is maximal and then $i$ is minimal such that $s_i s_{i+1} \cdots s_k (Z_{m})$ acts nontrivially and has no flips at each step.
  \end{itemize}
  Then set $Z_{m+1} = s_i s_{i+1} \cdots s_k (Z_{m})$. Stop when no such $j$ exists. 
  \label{def:lowest}
\end{definition}

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{ccccccccccc}
      \vline\tableau{2 & 1 \\ \\ 1 & 3 & 2 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\color{purple}f_3}{\longrightarrow}$} &
      \vline\tableau{2 & 1 \\ \\ 1 & 4 & 2 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\color{orange}f_2^2}{\longrightarrow}$} &
      \vline\tableau{3 & 1 \\ \\ 1 & 4 & 3 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\color{blue}f_1^2}{\longrightarrow}$} &
      \vline\tableau{3 & 2 \\ \\ 2 & 4 & 3 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\color{purple}f_3}{\longrightarrow}$} &
      \vline\tableau{3 & 2 \\ \\ 2 & 4 & 4 \\ & } & \raisebox{-1\cellsize}{$\stackrel{\color{orange}f_2}{\longrightarrow}$} &
      \vline\tableau{3 & 3 \\ \\ 2 & 4 & 4 \\ & } 
    \end{array}
  \end{displaymath}
  \caption{\label{fig:Dem-low}Computing the Demazure lowest weight for the given highest weight.}
\end{figure}

For example, in Figure~\ref{fig:Dem-low}, we take $Z_0$ to be the leftmost tabloid. Then $j=2$, and so $k=3$ and $i=1$, giving $Z_1 = s_1 s_2 s_3 (Z_0)$, which is the fourth from the left tabloid. Continuing the algorithm, we have $j=3$, and so $k=3$ and $i=2$, giving $Z_2 = s_2 s_3 (Z_1)$, which is the rightmost tabloid and also the Demazure lowest weight.

Figure~\ref{fig:lowest} shows the six Demazure lowest weights of the Demazure crystal on $\SSKD(0,3,0,2)$ corresponding to the highest weights in Figure~\ref{fig:highest}.

\begin{figure}[ht]
  \begin{displaymath}
    \begin{array}{c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c@{\hskip 2\cellsize}c}
      \vline\tableau{4 & 4 \\ & \\ 2 & 2 & 2 \\ & } & 
      \vline\tableau{3 & 4 \\ & \\ 2 & 2 & 2 \\ & } & 
      \vline\tableau{4 & 3 \\ & \\ 2 & 2 & 4 \\ & } & 
      \vline\tableau{3 & 3 \\ & \\ 2 & 4 & 4 \\ & } & 
      \vline\tableau{1 & 3 \\ & \\ 2 & 2 & 4 \\ & } & 
      \vline\tableau{2 & 3 \\ & \\ 1 & 4 & 4 \\ & } 
    \end{array}
  \end{displaymath}
  \caption{\label{fig:lowest}The Demazure lowest weights for the Demazure crystal for $E_{(0,3,0,2)}(X;q,0)$.}
\end{figure}

Using this notion, we have the following explicit expansion.

\begin{theorem}
  The specialized nonsymmetric Macdonald polynomial $E_{a}(X;q,0)$ is given by
  \begin{equation}
    E_{a}(X;q,0) = \sum_{\substack{Z\in\SSKD(a) \\ Z \ \mathrm{Demazure} \ \mathrm{lowest} \ \mathrm{weight}}} q^{\maj(Z)} \key_{\wt(Z)}(X).
  \end{equation}
  In particular, the nonsymmetric Kostka--Foulkes polynomial $K_{a,b}(q)$ is given by
  \begin{equation}
    K_{a,b}(q) = \#\{ Z \in \SSKD(b) \mid Z \ \mbox{Demazure lowest weight with} \ \wt(Z)=a \}.
  \end{equation}
\end{theorem}

For example, from Figure~\ref{fig:lowest}, we see that
\begin{eqnarray*}
  E_{(0,3,0,2)}(X;q,0) & = & \key_{(0,3,0,2)}(X) + q \key_{(0,3,1,1)}(X) + q \key_{(0,2,1,2)}(X) \\
  & & + q^2 \key_{(0,1,2,2)}(X) + q^2 \key_{(1,2,1,1)}(X) + q^3 \key_{(1,1,1,2)}(X).
\end{eqnarray*}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%\section{Affine Demazure operators}
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\label{sec:affine}
%
%The connection between specializations of nonsymmetric Macdonald polynomials and Demazure characters began with Sanderson \cite{San00} who used the theory of nonsymmetric Macdonald polynomials in type A to construct an affine Demazure module with graded character $P_{\mu}(X;q,0)$, similar to the construction of Garsia and Procesi \cite{GP92} for Hall-Littlewood symmetric functions $P_{\mu}(X;0,t)$. Therefore, it is natural to look for an affine Demazure crystal structure on the underlying combinatorial objects. For example, the affine edges of an affine Demazure crystal connecting the two components of the finite Demazure crystal for $E_{(0,2,1,2)}(X;q,0)$ are shown in Figure~\ref{fig:affine}. 
%
%\begin{figure}[ht]
%  \begin{displaymath}
%    \begin{array}{ccccccccccc}
%      \vline\tableau{4 & 3 \\ 2 \\ 1 & 1 \\ & \\\hline } & \stackrel{\displaystyle e_0}{\longrightarrow} &
%      \vline\tableau{4 & 4 \\ 2 \\ 1 & 3 \\ & \\\hline } & \stackrel{\displaystyle e_3}{\longrightarrow} &
%      \vline\tableau{3 & 3 \\ 2 \\ 1 & 4 \\ & \\\hline } & \stackrel{\displaystyle e_2}{\longrightarrow} &
%      \vline\tableau{3 & 2 \\ 2 \\ 1 & 4 \\ & \\\hline } & \stackrel{\displaystyle e_1}{\longrightarrow} &
%      \vline\tableau{3 & 1 \\ 2 \\ 1 & 4 \\ & \\\hline } & \stackrel{\displaystyle e_0}{\longrightarrow} &
%      \vline\tableau{4 & 4 \\ 3 \\ 2 & 1 \\ & \\\hline } 
%    \end{array}
%  \end{displaymath}
%\caption{\label{fig:affine}The Demazure crystal operators $e_1, e_2, e_3$ on non-attacking fillings of $\mathbb{D}(0,2,1,2)$ with $\mathrm{coinv}=0$, $\mathrm{maj}=1$ (middle four), and the affine Demazure crystal operator $e_0$ connecting to non-attacking fillings with $\mathrm{coinv}=0=\mathrm{maj}$ (outer two).}
%\end{figure}
%

%\acknowledgements{\lipsum[20]}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
