Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

%_ **************************************************************************
%_ * The TeX source for AMS journal articles is the publishers TeX code     *
%_ * which may contain special commands defined for the AMS production      *
%_ * environment.  Therefore, it may not be possible to process these files *
%_ * through TeX without errors.  To display a typeset version of a journal *
%_ * article easily, we suggest that you retrieve the article in DVI,       *
%_ * PostScript, or PDF format.                                             *
%_ **************************************************************************
% Date: 5-SEP-2002
\controldates{17-SEP-2002,17-SEP-2002,17-SEP-2002,17-SEP-2002}

\RequirePackage[warning,log]{snapshot}
\documentclass{era-l}
\issueinfo{8}{05}{}{2002}
\dateposted{September 19, 2002}
\pagespan{35}{46}
\PII{S 1079-6762(02)00103-8}
\copyrightinfo{2002}{American Mathematical Society}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{texdraw}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}
\newtheorem{case}{Case}


\theoremstyle{definition}
\newtheorem{df}[thm]{Definition}
\newtheorem{ex}[thm]{Example}



\begin{document}
\title[Quantum Affine Algebras, Combinatorics of Young Walls]{Quantum affine
algebras, combinatorics of Young walls, and global bases}
\author{Seok-Jin Kang}
\address{School of Mathematics, Korea Institute for
Advanced Study, Seoul 130-012, Korea}
\email{sjkang@kias.re.kr}

\author{Jae-Hoon Kwon}
\address{School of Mathematics, Korea Institute for
Advanced Study, Seoul 130-012, Korea}
\email{jhkwon@kias.re.kr}
\begin{thanks}
{This research was supported by KOSEF Grant \# 98-0701-01-05-L and
the Young Scientist Award, Korean Academy of Science and
Technology.}
\end{thanks}

\subjclass[2000]{Primary 17B37; Secondary 17B10}

\keywords{Quantized universal enveloping algebra, crystal basis, global basis}

\commby{Efim Zelmanov}

\date{December 14, 2001}

\begin{abstract}
We construct the Fock space representation of quantum affine
algebras using combinatorics of Young walls. We also show that the
crystal basis of the Fock space representation can be realized as
the abstract crystal consisting of proper Young walls. We then
generalize Lascoux-Leclerc-Thibon algorithm to obtain an effective
algorithm for constructing the global bases of basic
representations.
\end{abstract}

\maketitle

\section{Introduction}
Let $U_q(\mathfrak{g})$ be a quantum affine algebra of type
$A_n^{(1)}$, $A_{2n-1}^{(2)}$, $D_n^{(1)}$, $A_{2n}^{(2)}$,
$D_{n+1}^{(2)}$ and $B_n^{(1)}$, and let $\Lambda$ be a dominant
integral weight of level 1. In \cite{Kang}, Kang introduced a new
family of combinatorial objects called the {\it Young walls}. The
Young walls consist of colored blocks with various shapes built on
a given {\it ground state wall} $Y_{\Lambda}$ and can be viewed as
generalizations of (colored) Young diagrams.

The rules and patterns for building Young walls and the action of
Kashiwara operators are given explicitly in terms of combinatorics
of Young walls. Then the set ${\mathcal Y}(\Lambda)$ of {\it proper
Young walls} becomes an abstract crystal for the quantum affine
algebra $U_q(\mathfrak{g})$, and the subcrystal ${\mathcal
Y}_{\circ}(\Lambda)$ consisting of {\it reduced proper Young
walls} is isomorphic to the crystal $B(\Lambda)$ of the
basic representation $V(\Lambda)$.

In this paper, we construct the {\it Fock space representation}
${\mathcal F }(\Lambda)$ of $U_q(\mathfrak{g})$ in a purely combinatorial
way. More precisely, we take ${\mathcal F }(\Lambda)$ to be the
$\mathbb{Q}(q)$-vector space spanned by the proper Young walls,
and define the $U_q(\mathfrak{g})$-module action on ${\mathcal
F}(\Lambda)$ using combinatorics of Young walls. Then ${\mathcal
F}(\Lambda)$ becomes an integrable $U_q(\mathfrak{g})$-module in the
category ${\mathcal O}^{int}$. The Fock space ${\mathcal F}(\Lambda)$ can
be regarded as the $q$-deformed wedge space arising from a level 1
perfect representation \cite{KMPY}.

We also show that the crystal of ${\mathcal F}(\Lambda)$
coincides with the abstract crystal ${\mathcal Y}(\Lambda)$ consisting
of proper Young walls. Thus, we get an explicit decomposition of
the Fock space ${\mathcal F}(\Lambda)$ into a direct sum of
irreducible highest weight modules over $U_q(\mathfrak{g})$ by
locating the maximal vectors in the $U_q(\mathfrak{g})$-crystal ${\mathcal
Y}(\Lambda)$.

Finally, we generalize Lascoux-Leclerc-Thibon algorithm \cite{LLT} to obtain
an effective algorithm for constructing the global basis
$G(\Lambda)$ of the basic representation $V(\Lambda)$. To each
reduced proper Young wall $Y\in {\mathcal Y}_{\circ}(\Lambda)$, the
corresponding global basis element $G(Y)$ can be expressed as a
linear combination of proper Young walls whose coefficient
polynomials form an upper triangular matrix with the diagonal entries 1.
We expect that there exist some interesting algebraic structures such that the
irreducible modules at some specializations are parametrized by
the reduced proper Young walls and that the decomposition matrices
are determined by the polynomials giving the global basis
elements.

\section{Quantum affine algebras}
Let $I=\{\,0,1,\ldots,n\,\}$ be an index set and let $(A,
P^{\vee}, P, \Pi^{\vee}, \Pi)$ be an affine Cartan datum:
\begin{itemize}
\item[(i)] $A=(a_{ij})_{i,j\in I}$ is a generalized Cartan matrix of
{\it affine type},
\item[(ii)] $P^{\vee}=\mathbb{Z}h_0 \oplus
\cdots \oplus \mathbb{Z}h_n \oplus \mathbb{Z}d$ is the {\it dual
weight lattice},
\item[(iii)] $P=\{\,\lambda\in
\mathfrak{h}^*\,|\,\lambda(P^{\vee})\subset \mathbb{Z}\,\}$ is the
{\it weight lattice}, where
$\mathfrak{h}=\mathbb{Q}\otimes_{\mathbb{Z}}P^{\vee}$ is the {\it
Cartan subalgebra},
\item[(iv)] $\Pi^{\vee}=\{\,h_i\,|\,i\in I\,\}$ is the set of {\it simple
coroots},
\item[(v)] $\Pi=\{\,\alpha_i\,|\,i\in I\,\}$ is the set of {\it simple
roots} defined by $\alpha_j(h_i)=a_{ij}$,
$\alpha_j(d)=\delta_{0,j}$ ($i,j\in I$).
\end{itemize}

Set $P^+=\{\,\lambda\in P\,|\,\lambda(h_i)\in\mathbb{Z}_{\geq
0}\,\text{for all $i\in I$}\,\}$. The elements of $P^+$ are called
the {\it dominant integral weights}.

To each affine Cartan datum, we can  associate an infinite-dimensional
Lie algebra $\mathfrak{g}$ called the {\it affine
Kac-Moody algebra}. The {\it canonical central element} and the
{\it null root} of $\mathfrak{g}$ will be expressed as $c=\sum_{i=0}^n
c_i h_i$ and $\delta=\sum_{i=0}^n d_i \alpha_i$, respectively,
where $c_i$ and $d_i$ ($i\in I$) are positive integers given in
\cite{Kac90}. The {\it fundamental weights} $\Lambda_i$ ($i\in I$)
are the linear functionals defined by
$\Lambda_i(h_j)=\delta_{ij}$, $\Lambda_i(d)=0$ ($i,j\in I$).

We denote by $q^h$ ($h\in P^{\vee}$) the basis elements of the
group algebra $\mathbb{Q}(q)[P^{\vee}]$ with the multiplication
$q^h q^{h'}=q^{h+h'}$ ($h,h'\in P^{\vee}$). Let $(\,|\,)$ be a
nondegenerate symmetric bilinear form on $\mathfrak{h}^*$ satisfying
$\frac{2(\alpha_i|\alpha_j)}{(\alpha_i|\alpha_i)}=a_{ij}$ for
$i,j\in I$. Set $q_i=q^{\frac{(\alpha_i|\alpha_i)}{2}}$,
$K_i=q^{\frac{(\alpha_i|\alpha_i)}{2}h_i}$,
$[k]_i=\frac{q_i^k-q_i^{-k}}{q_i-q_i^{-1}}$ and
$[n]_i!=\prod_{k=1}^n[k]_i$. We also use the notation
$e_i^{(n)}=e_i^n/[n]_i!$ and $f_i^{(n)}=f_i^n/[n]_i!$.

The {\it quantum affine algebra $U_q(\mathfrak{g})$} is the
associative algebra with $1$ over $\mathbb{Q}(q)$ generated by
$e_i$, $f_i$ ($i\in I$) and $q^h$ ($h\in P^{\vee}$) subject to the
defining relations given, for example, in \cite{Kash}. In this
paper, we will focus on the quantum affine algebras of type
$A_n^{(1)}$, $A_{2n-1}^{(2)}$, $D_n^{(1)}$, $A_{2n}^{(2)}$,
$D_{n+1}^{(2)}$ and $B_n^{(1)}$.

\section{Crystal bases}
Recall that the category ${\mathcal O}^{int}$ consists of
$U_q(\mathfrak{g})$-modules $M$ satisfying the properties:
\begin{itemize}
\item[(i)] $M=\bigoplus_{\lambda\in P}M_{\lambda}$, where
$M_{\lambda}=\{\, v\in M\,|\,q^h v=q^{\lambda(h)}v\ \text{for all
$h\in P^{\vee} $}\,\}$,
\item[(ii)] for each $i\in I$, $M$ is a direct sum of finite-dimensional
irreducible $U_{(i)}$-modules, where $U_{(i)}=\langle e_i,f_i,
K_i^{\pm} \rangle \cong U_q(\mathfrak{sl}_2)$,
\item[(iii)] for any $v\in M$, there exists $l\geq 1$ such that
$e_{i_1}\cdots e_{i_l}v=0$ for any $i_1,\dots, i_l\in I$.
\end{itemize}
For each $i\in I$, every element $u\in M_{\lambda}$ can be written
uniquely as $u=\sum_{k\geq 0}f_i^{(k)}u_k$, where $k\geq
-\lambda(h_i)$ and $ u_k\in \text{ker}\,e_i \cap
M_{\lambda+k\alpha_i}$. The {\it Kashiwara operators} are the
endomorphisms $\tilde{e}_i$ and $\tilde{f}_i$ on $M$ defined by
\begin{equation}
\tilde{e}_i u=\sum_{k\geq 1}f_i^{(k-1)}u_k, \ \ \tilde{f}_i
u=\sum_{k\geq 0}f_i^{(k+1)}u_k.
\end{equation}
Let $\mathbb{A}_0=\{\,f/g\in\mathbb{Q}(q)\,|\,f,g\in\mathbb{Q}[q],
g(0)\neq 0 \,\}$ be the localization of $\mathbb{Q}[q]$ at $q=0$.
\begin{df}\label {crystal basis}{\rm
A {\it crystal basis} of $M$ is a pair $(L,B)$, where
\begin{itemize}
\item[{\rm (i)}] $L$ is a free $\mathbb{A}_0$-module of $M$ such that
$M\cong\mathbb{Q}(q)\otimes_{\mathbb{A}_0}L$,
\item[{\rm (ii)}] $B$ is a $\mathbb{Q}$-basis of $L/qL$,
\item[{\rm (iii)}] $L=\bigoplus_{\lambda\in P}L_{\lambda}$, where $L_{\lambda}=L\cap M_{\lambda}$,
\item[{\rm (iv)}] $B=\bigsqcup_{\lambda\in P}B_{\lambda}$, where
$B_{\lambda}=B\cap(L_{\lambda}/qL_{\lambda})$,
\item[{\rm (v)}] $\tilde{e}_iL\subset L$, $\tilde{f}_iL\subset L$ for all
$i\in I$,
\item[{\rm (vi)}] $\tilde{e}_iB\subset B\cup\{0\}$, $\tilde{f}_iB\subset
B\cup\{0\}$ for all $i\in I$,
\item[{\rm (vii)}] for $i\in I$ and $b,b'\in B$, $\tilde{f}_ib=b'$ if and
only if $b= \tilde{e}_ib'$.
\end{itemize}}
\end{df}
The set $B$ becomes a colored oriented graph, called the {\it
crystal graph}, with the arrows defined by
$b\stackrel{i}{\rightarrow}b'$ if and only if $\tilde{f}_i b=b'$.



By extracting the properties of crystal graphs, we can define the
notion of {\it abstract crystals} \cite{Kash93,Kash94}. An {\it
affine crystal} is a set $B$ together with the maps ${\rm wt} :
B\rightarrow P$, $\varepsilon_i, \varphi_i : B\rightarrow
\mathbb{Z}\cup\{-\infty\}$, $\tilde{e}_i,\tilde{f}_i :
B\rightarrow B\cup\{0\}$ satisfying the conditions given in
\cite{Kash93,Kash94}.





\begin{thm}[\cite{Kash}] \mbox{}
\begin{itemize}
\item[{\rm (a)}] Let $V(\lambda)$ be the irreducible highest weight
$U_q(\mathfrak{g})$-module with highest weight $\lambda\in P^+$ and
highest weight vector $u_{\lambda}$. Let $L(\lambda)$ be the free
$\mathbb{A}_0$-submodule of $V(\lambda)$ spanned by the vectors of
the form $\tilde{f}_{i_1}\cdots\tilde{f}_{i_r}u_{\lambda}$ {\rm
(}$i_k\in I$, $r\in\mathbb{Z}_{\geq0}${\rm )} and set
\begin{equation*}
B(\lambda)=\{\,\tilde{f}_{i_1}\cdots\tilde{f}_{i_r}u_{\lambda}+qL(\lambda)\in
L(\lambda)/qL(\lambda)\,\}\backslash\{0\}.
\end{equation*}
Then $(L(\lambda),B(\lambda))$ is a crystal basis of $V(\lambda)$,
and every crystal basis of $V(\lambda)$ is isomorphic to
$(L(\lambda),B(\lambda))$.
\item[{\rm (b)}] Define a $\mathbb{Q}$-algebra automorphism of
$U_q(\mathfrak{g})$ by $\overline{e}_i=e_i$, $\overline{f}_i=f_i$,
$\overline{q^h}=q^{-h}$ and $\overline{q}=q^{-1}$ for $i\in I$ and
$h\in P^{\vee}$. Set $\mathbb{A}=\mathbb{Q}[q,q^{-1}]$ and let
$V(\lambda)^{\mathbb{A}}=U^-_{\mathbb{A}}(\mathfrak{g})u_{\lambda}$,
where $U^-_{\mathbb{A}}(\mathfrak{g})$ is the $\mathbb{A}$-subalgebra
of $U_q(\mathfrak{g})$ generated by $f^{(n)}_i$ {\rm ($i\in I$,
$n\in\mathbb{Z}_{\geq 0}$)}. Then there exists a unique
$\mathbb{A}$-basis $G(\lambda)=\{\,G(b)\,|\,b\in B(\lambda)\,\}$
of $V(\lambda)^{\mathbb{A}}$ such that
\begin{equation*}
G(b)\equiv b \mod {qL(\lambda)}\quad \text{and} \quad
\overline{G(b)}=G(b)
\end{equation*}
for all $b\in B(\lambda)$.
\end{itemize}
\end{thm}
The basis $G(\lambda)$ is called the {\it global basis} or {\it
canonical basis} of $V(\lambda)$ associated with the crystal graph
$B(\lambda)$.

\section{Combinatorics of Young walls}
We briefly review the notion of {\it Young walls} and their
combinatorics introduced by Kang \cite{Kang}. The Young walls are
built of colored blocks of three different shapes.

%\[
%\includegraphics{era103el-fig-1}
%\]
\vskip 5mm

\renewcommand{\arraystretch}{1.6}
\begin{center}
\begin{tabular}{c|c|c|c|c|c}
% after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
Type & Shape & Width & Thickness & Height & Volume \\
\hline I & \raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(-10 0)\lvec(0
0)\lvec(0 10)\lvec(-10 10)\lvec(-10 0) \move(0 0)\lvec(5 5)\lvec(5
15)\lvec(-5 15)\lvec(-10 10) \move(0 10)\lvec(5 15)
\end{texdraw}
} $=$ \raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(-10 0)\lvec(0
0)\lvec(0 10)\lvec(-10 10)\lvec(-10 0)
\end{texdraw}}
 & 1 & 1 & 1 & 1 \\
II & \raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(0 0)\lvec(10
0)\lvec(10 5)\lvec(0 5)\lvec(0 0) \move(10 0)\lvec(15 5)\lvec(15
10)\lvec(5 10)\lvec(0 5) \move(10 5)\lvec(15 10)
\end{texdraw}
} $=$ \raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \textref h:C v:C \move(0
0)\lvec(10 0)\lvec(10 5)\lvec(0 5)\lvec(0 0)
\end{texdraw}
}
& 1 & 1 & $\frac{1}{2}$ & $\frac{1}{2}$ \\
III &

\raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(-10 0)\lvec(0
0)\lvec(0 10)\lvec(-10 10)\lvec(-10 0) \move(0 0)\lvec(2.5
2.5)\lvec(2.5 12.5)\lvec(-7.5 12.5)\lvec(-10 10) \move(0
10)\lvec(2.5 12.5) \lpatt(0.3 1) \move(0 0)\lvec(-2.5
-2.5)\lvec(-12.5 -2.5)\lvec(-10 0)
\end{texdraw}
} $=$ \raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(-10 0)\lvec(0
0)\lvec(0 10)\lvec(-10 0) \lpatt(0.3 1)\move(-10 0)\lvec(-10
10)\lvec(0 10)
\end{texdraw}}
, \hskip 2mm \raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(-10 0)\lvec(0
0)\lvec(0 10)\lvec(-10 10)\lvec(-10 0) \move(0 0)\lvec(2.5
2.5)\lvec(2.5 12.5)\lvec(-7.5 12.5)\lvec(-10 10) \move(0
10)\lvec(2.5 12.5) \lpatt(0.3 1) \move(2.5 2.5)\lvec(5 5)\lvec(2.5
5)
\end{texdraw}
} $=$ \raisebox{-0.4\height}{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(-10 0)\lvec(-10
10)\lvec(0 10)\lvec(-10 0)\lpatt(0.3 1)\move(-10 0)\lvec(0
0)\lvec(0 10)
\end{texdraw}
}

& 1 & $\frac{1}{2}$ & 1 & $\frac{1}{2}$ \\

\end{tabular}
\renewcommand{\baselinestretch}{1}
\end{center}
\renewcommand{\arraystretch}{1}

\vskip 5mm

Given a dominant integral weight $\Lambda$ of level 1, i.e.
$\Lambda(c)=1$, we fix a frame $Y_{\Lambda}$ called the {\it
ground state wall} of weight $\Lambda$ and on this frame, we build
a wall of thickness less than or equal to one unit. The rules for
building the walls are as follows:
\begin{itemize}
\item[(1)] The colored blocks should be stacked in columns. No block can
be placed on top of a column of half-unit thickness.
\item[(2)] Except for the right-most column, there should be no free
space to the right of any block.
\item[(3)] The colored blocks should be stacked in a specified pattern
which is determined by the type of the quantum affine algebra and $\Lambda$.
\end{itemize}

The coloring of blocks, description of ground state walls and the
patterns for building the walls are given in \cite{Kang}. For
example, if $\mathfrak{g}=B^{(1)}_3$, and $\Lambda=\Lambda_0$, we will
use the colored blocks
%\[
%\includegraphics{era103el-fig-2}
%\]
%
%\noindent to build the walls on the ground state wall
%\[
%\includegraphics{era103el-fig-3}
%\]
%
%\noindent following the pattern:
%\[
%\includegraphics{era103el-fig-4}
%\]
\vskip 3mm \hskip 4cm
\raisebox{-0.33\height}[0.69\height][0.35\height]{%
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(0 0)\lvec(10
0)\lvec(10 10)\lvec(0 10)\lvec(0 0) \move(10 0)\lvec(12.5
2.5)\lvec(12.5 12.5)\lvec(2.5 12.5)\lvec(0 10) \move(10
10)\lvec(12.5 12.5) \htext(3 3){$_0$}
\end{texdraw}%
} \hskip 5mm
\raisebox{-0.33\height}[0.69\height][0.35\height]{%
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(0 0)\lvec(10
0)\lvec(10 10)\lvec(0 10)\lvec(0 0) \move(10 0)\lvec(12.5
2.5)\lvec(12.5 12.5)\lvec(2.5 12.5)\lvec(0 10) \move(10
10)\lvec(12.5 12.5) \htext(3 3){$_1$}
\end{texdraw}%
} \hskip 5mm \raisebox{-0.33\height}[0.69\height][0.35\height]{
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(0 0)\lvec(10
0)\lvec(10 10)\lvec(0 10)\lvec(0 0) \move(10 0)\lvec(15 5)\lvec(15
15)\lvec(5 15)\lvec(0 10) \move(10 10)\lvec(15 15) \htext( 3
3){$_2$}
\end{texdraw}
} \hskip 5mm
\raisebox{-0.33\height}[0.69\height][0.35\height]{%
\begin{texdraw}
\drawdim em \setunitscale 0.1 \linewd 0.5 \move(0 0)\lvec(10
0)\lvec(10 5)\lvec(0 5)\lvec(0 0) \move(10 0)\lvec(15 5)\lvec(15
10)\lvec(5 10)\lvec(0 5) \move(10 5)\lvec(15 10) \htext(3 1){\tiny
$3$}
\end{texdraw}%
}\vskip 3mm

\noindent to build the walls on the ground state wall
$Y_{\Lambda_0} = \raisebox{-0.3\height}{\begin{texdraw} \drawdim
em \setunitscale 0.1 \linewd 0.5 \move(-42 0)\lvec(0 0)\lvec(2.5
2.5)\lvec(2.5 12.5)\lvec(-39.5 12.5) \move(-42 10)\lvec(0 10)
\move(0 0)\lvec(0 10)\lvec(2.5 12.5) \move(-10 0)\lvec(-10
10)\lvec(-7.5 12.5) \move(-20 0)\lvec(-20 10)\lvec(-17.5 12.5)
\move(-30 0)\lvec(-30 10)\lvec(-27.5 12.5) \move(-40 0)\lvec(-40
10)\lvec(-37.5 12.5) \move(0 0)\lvec(-2.5 -2.5)\lvec(-44.5 -2.5)
\move(-10 0)\rlvec(-2.5 -2.5) \move(-20 0)\rlvec(-2.5 -2.5)
\move(-30 0)\rlvec(-2.5 -2.5) \move(-40 0)\rlvec(-2.5 -2.5)
\htext(-7 3){$_1$} \htext(-17 3){$_0$} \htext(-27 3){$_1$}
\htext(-37 3){$_0$}
\end{texdraw}} = \raisebox{-0.3\height}{\begin{texdraw} \drawdim
em \setunitscale 0.1 \linewd 0.5 \move(-5 0)\lvec(40 0)\lvec(40
10)\lvec(-5 10)\move(0 0)\rlvec(0 10)\move(10 0)\rlvec(0
10)\lvec(0 0)\move(20 0)\rlvec(0 10)\lvec(10 0)\move(30 0)\rlvec(0
10)\lvec(20 0)\move(40 10)\lvec(30 0) \htext(5
1){{\tiny$0$}}\htext(15 1){{\tiny$1$}}\htext(25
1){{\tiny$0$}}\htext(35 1){{\tiny$1$}}
\end{texdraw}}$ \ \ following the pattern:

\vskip 2mm \hskip 4cm
\begin{texdraw}\drawdim em \setunitscale 0.15 \linewd 0.5

\move(-10 0)\lvec(40 0)\move(-10 10)\lvec(40 10)\move(-10
20)\lvec(40 20)\move(-10 30)\lvec(40 30)\move(-10 40)\lvec(40
40)\move(-10 50)\lvec(40 50)\move(0 0)\lvec(0 55)\move(10
0)\lvec(10 55)\move(20 0)\lvec(20 55)\move(30 0)\lvec(30
55)\move(40 0)\lvec(40 55)\move(-10 25)\lvec(40 25)

\move(10 10)\lvec(0 0)\lvec(10 0)\lvec(10 10)\lfill f:0.8

\move(20 10)\lvec(10 0)\lvec(20 0)\lvec(20 10)\lfill f:0.8

\move(30 10)\lvec(20 0)\lvec(30 0)\lvec(30 10)\lfill f:0.8

\move(40 10)\lvec(30 0)\lvec(40 0)\lvec(40 10)\lfill f:0.8

\move(10 50)\lvec(0 40)

\move(20 50)\lvec(10 40)

\move(30 50)\lvec(20 40)

\move(40 50)\lvec(30 40)

\htext(2 6){\tiny$1$} \htext(16 2){\tiny $1$} \htext(22 6){\tiny
$1$}\htext(36 2){\tiny $1$}

\htext(6 2){\tiny $0$} \htext(12 6){\tiny $0$} \htext(26 2){\tiny
$0$}\htext(32 6){\tiny $0$}

\htext(2 46){\tiny $1$} \htext(16 42){\tiny $1$} \htext(22
46){\tiny $1$}\htext(36 42){\tiny $1$}

\htext(6 42){\tiny $0$} \htext(12 46){\tiny $0$} \htext(26
42){\tiny $0$}\htext(32 46){\tiny $0$}

\htext(3 13){$_2$}\htext(13 13){$_2$}

\htext(23 13){$_2$}\htext(33 13){$_2$}

\htext(3 33){$_2$}\htext(13 33){$_2$}

\htext(23 33){$_2$}\htext(33 33){$_2$}

\htext(3 21){$_3$}\htext(13 21){$_3$}

\htext(23 21){$_3$}\htext(33 21){$_3$}

\htext(3 26){$_3$}\htext(13 26){$_3$}

\htext(23 26){$_3$}\htext(33 26){$_3$}

\end{texdraw}

\medskip

A wall built on $Y_{\Lambda}$ following the above rules is called
a {\it Young wall on $Y_{\Lambda}$}, for the heights of its
columns are weakly decreasing as we proceed from right to left. We
often write $Y=(y_k)_{k=0}^{\infty}=(\dots,y_2,y_1,y_0)$ as an
infinite sequence of its columns.
\begin{df}\mbox{ }
{\rm
\begin{itemize}
\item[{\rm (1)}] A column of a Young wall is called a {\it full
column} if its height is a multiple of the unit length and its top
is of unit thickness.
\item[{\rm (2)}] For quantum affine algebras of type $A_{2n-1}^{(2)}$,
$D_n^{(1)}$, $A_{2n}^{(2)}$, $B_n^{(1)}$ and $D_{n+1}^{(2)}$, a
Young wall is said to be {\it proper} if none of the full columns
have the same heights.
\item[{\rm (3)}] For quantum affine algebras of type $A_n^{(1)}$, every
Young wall is defined to be {\it proper}.
\end{itemize}}
\end{df}
We will denote by ${\mathcal Y}(\Lambda)$ the set of all proper Young
walls on $Y_{\Lambda}$.

\newpage

\begin{df}{\rm Let $Y$ be a proper Young wall on $Y_{\Lambda}$.
\begin{itemize}
\item[{\rm (1)}] A block of color $i$ (in short, $i$-block) in $Y$ is called a {\it removable
$i$-block} if $Y$ remains a proper Young wall after removing the
block.
\item[{\rm (2)}] A place in $Y$ is called an {\it admissible $i$-slot} if
one may add an $i$-block to obtain another proper Young wall.
\item[{\rm (3)}] A column in $Y$ is said to be {\it $i$-removable
{\rm(}resp. $i$-admissible{\rm )}} if there is a removable
$i$-block {\rm (}resp. an admissible $i$-slot{\rm )} in that
column.
\end{itemize}}
\end{df}

We now define the {\it abstract Kashiwara operators}
$\tilde{E}_i$, $\tilde{F}_i$ on ${\mathcal Y}(\Lambda)$ as follows.
Fix $i\in I$ and let $Y=(y_k)_{k=0}^{\infty}$ be a proper Young
wall on $Y_{\Lambda}$.
\begin{itemize}
\item[(1)] To each column $y_k$ of $Y$, we assign
\begin{equation*}
\begin{cases}
-- & \text{if $y_k$ is twice $i$-removable,} \\
- & \text{if $y_k$ is once $i$-removable but not $i$-admissible,} \\
-+ & \text{if $y_k$ is once $i$-removable and once
$i$-admissible,} \\
+ & \text{if $y_k$ is once $i$-admissible but not $i$-removable,}
\\
++ & \text{if $y_k$ is twice $i$-admissible,} \\
\ \ \cdot & \text{otherwise}.
\end{cases}
\end{equation*}
\item[(2)] From this sequence of $+$'s and $-$'s, we cancel out
every $(+,-)$-pair to obtain a finite sequence of $-$'s followed
by $+$'s, reading from left to right. This finite sequence
$(-\cdots-,+\cdots+)$ is called the {\it $i$-signature} of $Y$.
\item[(3)] We define $\tilde{E}_i Y$ to be the proper Young wall obtained
from $Y$ by removing the $i$-block corresponding to the right-most
$-$ in the $i$-signature of $Y$. We define $\tilde{E}_i Y=0$ if
there is no $-$ in the $i$-signature of $Y$.
\item[(4)] We define $\tilde{F}_i Y$ to  be the proper Young wall obtained
from $Y$ by adding an $i$-block to the column corresponding to
the left-most $+$ in the $i$-signature of $Y$. We define
$\tilde{F}_i Y=0$ if there is no $+$ in the $i$-signature of $Y$.
\end{itemize}

Next, we define
\begin{equation*}
\begin{split}
{\rm wt}(Y)&=\Lambda-\sum_{i\in I}k_i\alpha_i \in P, \\
\varepsilon_i(Y)&=\text{the number of $-$'s in the $i$-signature of $Y$}, \\
\varphi_i(Y)&=\text{the number of $+$'s in the $i$-signature of
$Y$},
\end{split}
\end{equation*}
where $k_i$ denotes the number of $i$-blocks in $Y$ that have been
added to $Y_{\Lambda}$.
\begin{prop}[\cite{Kang}]
The set ${\mathcal Y}(\Lambda)$ together with the maps ${\rm wt}$,
$\varepsilon_i$, $\varphi_i$, $\tilde{E}_i$ and $\tilde{F}_i$ {\rm
($i\in I$)} becomes an affine crystal.
\end{prop}

Let $\delta=d_0\alpha_0+\cdots +d_n\alpha_n$ be the null root of
$U_q(\mathfrak{g})$, and set $a_i=d_i$ if $\mathfrak{g}\neq
D^{(2)}_{n+1}$, $a_i=2d_i$ if $\mathfrak{g}=D^{(2)}_{n+1}$. The part
of a column with $a_i$-many $i$-blocks for each $i\in I$ in some
cyclic order is called a {\it $\delta$-column}. A $\delta$-column
in a proper Young wall is called {\it removable} if it can be removed to
yield another proper Young wall.
\begin{df}{\rm
A proper Young wall $Y$ is said to be {\it reduced} if none of its
columns contain a removable $\delta$-column.}
\end{df}

Let ${\mathcal Y}_{\circ}(\Lambda)\subset{\mathcal Y}(\Lambda) $ be the
set of all reduced proper Young walls on $Y_{\Lambda}$. Then we
have:
\begin{thm}[\cite{Kang}]
The set ${\mathcal Y}_{\circ}(\Lambda)$ is an affine crystal.
Moreover, there exists an affine crystal isomorphism ${\mathcal
Y}_{\circ}(\Lambda) \stackrel{\sim}{\longrightarrow} B(\Lambda)$,
where $B(\Lambda)$ is the crystal of the basic
representation $V(\Lambda)$.
\end{thm}

\begin{rem}{\rm
If $H_N(q)$ is a Hecke algebra of type $A_{N -1}$ with $q$ a
primitive $n$th root of unity, then the irreducible
representations of $H_N(q)$ are parametrized by the set of reduced
proper Young walls of type $A_n^{(1)}$ with $N$ blocks \cite{DJ}.
We expect that there exist some interesting algebraic structures
whose irreducible representations (at some specialization) are
parametrized by reduced proper Young walls. In \cite{BK}, Brundan
and Kleshchev verified our speculation by showing that the
irreducible representations of the Heck-Clifford superalgebra
$H_N(q)$ with $q$ a primitive\linebreak $(2n+1)$th root of unity are
parametrized by the set of reduced proper Young walls of type
$A_{2n}^{(2)}$ with $N$ blocks. }
\end{rem}

\section{Fock space representation}
Let ${\mathcal F}(\Lambda)=\bigoplus_{Y\in {\mathcal
Y}(\Lambda)}\mathbb{Q}(q)Y$ be the $\mathbb{Q}(q)$-vector space
with a basis ${\mathcal Y}(\Lambda)$. The goal of this section is to
define a $U_q(\mathfrak{g})$-module structure on ${\mathcal F}(\Lambda)$,
the {\it Fock space representation of $U_q(\mathfrak{g})$}. Moreover,
we also show that the affine crystal ${\mathcal Y}(\Lambda)$ is
exactly the crystal of ${\mathcal F}(\Lambda)$.

For this purpose, we need to define the action of $e_i$, $f_i$
($i\in I$) and $q^h$ ($h\in P^{\vee}$) on proper Young walls in
${\mathcal Y}(\Lambda)$. Let $Y=(y_k)_{k=0}^{\infty}$ be a proper
Young wall on $Y_{\Lambda}$. We denote by $|y_k|$ the number of
blocks in $y_k$ added to $Y_{\Lambda}$. Then the {\it associated
partition} is defined to be
$|Y|=(\dots,|y_k|,\dots,|y_1|,|y_0|)$. For
$Y=(y_k)_{k=0}^{\infty},Z=(z_k)_{k=0}^{\infty}$ in ${\mathcal
Y}(\Lambda)$, we define $|Y|\unrhd|Z|$ if and only if
$\sum_{k=l}^{\infty}|y_k|\geq\sum_{k=l}^{\infty}|z_k|$ for all
$l\geq 0$.

The action of $q^h$ ($h\in P^{\vee}$) on $Y\in {\mathcal Y}(\Lambda)$
is easily defined by $q^h Y=q^{{\rm wt}(Y)(h)}$. We
now focus on the action of $e_i$ and $f_i$ on $Y$ ($i\in I$).

\begin{case} Suppose that the $i$-blocks are
of type I.
\end{case}

If $b$ is a removable $i$-block in $y_k$ of $Y$, then let
$Y_R(b)=(y_{k-1},\dots,y_{1},y_0)$ be the wall consisting of the
columns lying on the right of $b$, and set
$R_i(b;Y)=\varphi_i(Y_R(b))-\varepsilon_i(Y_R(b))$. (The wall
$Y_R(b)$ should be regarded as a $U_{(i)}$-crystal, where no block
can be added on $y_l$ for $l\geq k$.) We denote by $Y\nearrow b$
the Young wall obtained by removing $b$ from $Y$. Then we define
\begin{equation}
e_i\,Y=\sum_{b}q_i^{-R_i(b;Y)}(Y\nearrow b),
\end{equation}
 where $b$ runs over all removable $i$-blocks
in $Y$.

On the other hand, if $b$ is an admissible $i$-slot in $y_k$ of
$Y$, then let $Y_L(b)=(\dots,y_{k+2},y_{k+1})$ be the Young wall
consisting of the columns in $Y$ lying on the left of $b$, and set
$L_i(b;Y)=\varphi_i(Y_L(b))-\varepsilon_i(Y_L(b))$. (The wall
$Y_L(b)$ may be a proper Young wall on another ground state wall
$Y_{\Lambda'}$.) We denote by $Y\swarrow b$ the Young wall
obtained by adding an $i$-block at $b$. Then we define
\begin{equation}
f_i\,Y=\sum_{b}q_i^{L_i(b;Y)}(Y\swarrow b),
\end{equation}
where $b$ runs over all admissible $i$-slots in $Y$.

\begin{case} Suppose that the $i$-blocks are
of type II (in this case, $q=q_i$).
\end{case}

Let $b$ be a removable $i$-block in $y_k$ of $Y$. If the
$i$-signature of $y_k$ is $--$, or if the $i$-signature of $y_k$
is $-$ and there is another $i$-block below $b$, define $Y\nearrow
b$ to be the Young wall obtained by removing $b$ from $Y$. If the
$i$-signature of $y_k$ is $-+$, or if the $i$-signature of $y_k$
is $-$ and there is no $i$-block below $b$, define $Y\nearrow
b=q^{-1}(1-(-q^2)^{l(b)+1})Z$, where $Z$ is the Young wall
obtained by removing $b$ from $Y$ and $l(b)$ is the number of
$y_l$'s with $lk$ such that $|y_l|=|y_k|$. That is
%\[
%\includegraphics{era103el-fig-6}
%\]

\hskip 4cm $Y=$\raisebox{-0.5\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\move(-30 -20)\lvec(-30 0)\lvec(-10 0)\lvec(-10 10)\lvec(50
10)\lvec(50 30)\lvec(65 30)\lvec(65 -20)\lvec(-30 -20)

\move(0 10)\lvec(0 -20)\htext(-24 -14){$Y_L(b)$}

\move(40 15) \lvec(40 20)\lvec(50 20)

\move(0 10) \lvec(0 15) \lvec(10 15)\lvec(10 10)\lvec(0 10)\lfill
f:0.8

\move(10 10)\lvec(10 15)\lvec(50 15)\lvec(50 10)\lvec(10 10)
\lfill f:0.8

\move(30 10) \lvec(30 15) \move(40 10) \lvec(40 15) \htext(15
11){$\cdots$}

\move(55 0) \arrowheadtype t:F \arrowheadsize l:4 w:2 \avec(43 17)

\htext(60 -3){$_b$}

\move(0 15)\clvec(2 20)(13 20)(15 20)

\move(40 15)\clvec(38 20)(27 20)(25 20)

\htext(16 18){$_{l(b)}$}
\end{texdraw}}
\vskip 0.5cm

\hskip 1cm$Y\swarrow b=$\raisebox{-0.5\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\move(-30 -20)\lvec(-30 0)\lvec(-10 0)\lvec(-10 10)\lvec(50
10)\lvec(50 30)\lvec(65 30)\lvec(65 -20)\lvec(-30 -20)

\move(40 15) \lvec(40 20)\lvec(50 20)\lvec(50 15)\lfill f:0.8

\move(0 10) \lvec(0 15) \lvec(10 15)\lvec(10 10)\lvec(0 10)\lfill
f:0.8

\move(10 10)\lvec(10 15)\lvec(50 15)\lvec( 50 10)\lvec(10 10)
\lfill f:0.8

\move(30 10) \lvec(30 15) \move(40 10) \lvec(40 15) \htext(15
11){$\cdots$}

\htext(-90 0){$\dfrac{(1-(-q^2)^{l(b)+1})}{q}\times$}
\end{texdraw}}\vskip 5mm

In either case, set $Y_L(b)=(\dots,y_{l+2},y_{l+1})$, where $l$
is the integer such that $|y_{l+1}|<|y_l|=|y_{l-1}|=\cdots=|y_k|$,
and let $L_i(b;Y)=\varphi_i(Y_L(b))-\varepsilon_i(Y_L(b))$. Then
we define
\begin{equation}
f_i\,Y=\sum_{b}q_i^{L_i(b;Y)}(Y\swarrow b),
\end{equation}
where $b$ runs over all admissible $i$-slots
in $Y$.


\begin{case} Suppose that the $i$-blocks are
of type III.
\end{case}


If $b$ is a removable $i$-block in $y_k$ of $Y$, then we define
$Y\nearrow b$ to be the Young wall obtained by removing $b$ from
$Y$. We also consider the following $i$-block $b$ in $y_k$ of $Y$,
which we call a {\it virtually removable $i$-block}.

\medskip
%\[
%\includegraphics{era103el-fig-7}
%\]
%\noindent In this case, we define $Y\nearrow b$ to be
%\[
%\includegraphics{era103el-fig-8}
%\]
\begin{center}
\raisebox{-0.4\height}{\begin{texdraw}\fontsize{9}{9} \drawdim em
\setunitscale 0.1 \linewd 0.5

\move(0 -20)\lvec(0 0)\lvec(10 0)\lvec(10 10)\lvec(60 10)\lvec(60
30)\lvec(70 30)\lvec(70 40)\lvec(90 40)\lvec(90 -20)\lvec(0 -20)

\move(60 10)\lvec(60 -20)

\move(10 10)\lvec(20 20)\lvec(20 10)\lvec(10 10)\lfill f:0.8

\move(20 10)\lvec(30 20)\lvec(30 10)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(60 10)\lvec(50 10)\lfill f:0.8

\htext(65 10){$Y_R(b)$}

\htext(37 14){$_{\cdots}$}

\move(67 3) \arrowheadtype t:F \arrowheadsize l:4 w:2 \avec(57 13)

\htext(70 0){$_b$}

\move(24 5)\clvec(16 5)(13 5)(10 10)

\move(36 5)\clvec(44 5)(47 5)(50 10)

\htext(26 2){$_{l(b)}$}
\end{texdraw}}\hskip 1cm or
\hskip .7cm\raisebox{-0.4\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\move(0 -20)\lvec(0 0)\lvec(10 0)\lvec(10 10)\lvec(60 10)\lvec(60
30)\lvec(70 30)\lvec(70 40)\lvec(90 40)\lvec(90 -20)\lvec(0 -20)

\move(60 10)\lvec(60 -20)

\htext(65 10){$Y_R(b)$}

\move(10 10)\lvec(20 20)\lvec(10 20)\lvec(10 10)\lfill f:0.8

\move(20 10)\lvec(30 20)\lvec(20 20)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(50 20)\lvec(50 10)\lfill f:0.8

%\move(30 20)\lvec(30 10)

\htext(37 14){$_{\cdots}$}

\move(67 3) \arrowheadtype t:F \arrowheadsize l:4 w:2 \avec(53 17)

\htext(70 0){$_b$}

\move(24 5)\clvec(16 5)(13 5)(10 10)

\move(36 5)\clvec(44 5)(47 5)(50 10)

\htext(26 2){$_{l(b)}$}
\end{texdraw}}
\end{center}

\medskip

\noindent In this case, we define $Y\nearrow b$ to be

\medskip

\begin{center}
\raisebox{-0.4\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\htext(-30 10){${(-q_i)^{l(b)}\times}$}

\move(0 -20)\lvec(0 0)\lvec(10 0)\lvec(10 10)\lvec(60 10)\lvec(60
30)\lvec(70 30)\lvec(70 40)\lvec(90 40)\lvec(90 -20)\lvec(0 -20)

\move(20 10)\lvec(30 20)\lvec(20 20)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(50 20)\lvec(50 10)\lfill f:0.8

%\move(30 20)\lvec(30 10)

\htext(37 14){$_{\cdots}$}
\end{texdraw}} \hskip 5mm and
\raisebox{-0.4\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\htext(-30 10){${(-q_i)^{l(b)}\times}$}

\move(0 -20)\lvec(0 0)\lvec(10 0)\lvec(10 10)\lvec(60 10)\lvec(60
30)\lvec(70 30)\lvec(70 40)\lvec(90 40)\lvec(90 -20)\lvec(0 -20)

\move(20 10)\lvec(30 20)\lvec(30 10)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(60 10)\lvec(50 10)\lfill f:0.8

%\move(50 20)\lvec(50 10)

\htext(37 14){$_{\cdots}$}

\end{texdraw}}
\end{center}

\medskip

\noindent respectively, where $l(b)$ is given in the above figure.
In either case, set $Y_R(b)=(y_{k-1},\dots,y_{0})$ and
$R_i(b;Y)=\varphi_i(Y_R(b))-\varepsilon_i(Y_R(b))$. Then we define
\begin{equation}
e_i\,Y=\sum_{b}q_i^{-R_i(b;Y)}(Y\nearrow b),
\end{equation}
 where $b$ runs over all removable and
virtually removable $i$-blocks in $Y$.

On the other hand, if $b$ is an admissible $i$-slot in $y_k$ of
$Y$, then we define $Y\swarrow b$ to be the Young wall obtained by
adding an $i$-block at $b$. We also consider the following
$i$-slot $b$ in $y_k$ of $Y$, which we call a {\it virtually
admissible $i$-slot}

\medskip

%\[
%\includegraphics{era103el-fig-9}
%\]
%In this case, we define $Y\swarrow b$ to be
%\[
%\includegraphics{era103el-fig-10}
%\]
\begin{center}
\raisebox{-0.4\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\move(-20 -20)\lvec(-20 0)\lvec(0 0)\lvec(0 10)\lvec(60
10)\lvec(60 30)\lvec(75 30)\lvec(75 -20)\lvec(-20 -20)

\move(10 10)\lvec(10 -20)\htext(-14 -14){$Y_L(b)$}

\move(10 10)\lvec(10 20)\lvec(20 20)

\move(10 10)\lvec(20 20)\lvec(20 10)\lvec(10 10)\lfill f:0.8

\move(20 10)\lvec(30 20)\lvec(30 10)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(60 10)\lvec(50 10)\lfill f:0.8

%\move(50 20)\lvec(50 10)

\htext(37 14){$_{\cdots}$}

\move(3 27) \arrowheadtype t:F \arrowheadsize l:4 w:2 \avec(13 17)

\htext(0 30){$_b$}

\move(34 5)\clvec(26 5)(23 5)(20 10)

\move(46 5)\clvec(54 5)(57 5)(60 10)

\htext(36 2){$_{l(b)}$}
\end{texdraw}}\hskip 1cm or
\hskip 1cm\raisebox{-0.4\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\move(-20 -20)\lvec(-20 0)\lvec(0 0)\lvec(0 10)\lvec(60
10)\lvec(60 30)\lvec(75 30)\lvec(75 -20)\lvec(-20 -20)

\move(10 10)\lvec(10 -20)\htext(-14 -14){$Y_L(b)$}

\move(10 10)\lvec(20 20)\lvec(10 20)\lvec(10 10)\lfill f:0.8

\move(20 10)\lvec(30 20)\lvec(20 20)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(50 20)\lvec(50 10)\lfill f:0.8

\htext(37 14){$_{\cdots}$}

\move(3 27) \arrowheadtype t:F \arrowheadsize l:4 w:2 \avec(17 13)

\htext(0 30){$_b$} \move(34 5)\clvec(26 5)(23 5)(20 10)

\move(46 5)\clvec(54 5)(57 5)(60 10)

\htext(36 2){$_{l(b)}$}
\end{texdraw}}
\end{center}

\medskip

\noindent In this case, we define $Y\swarrow b$ to be

\medskip

\begin{center}
\raisebox{-0.4\height}{
\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\htext(-40 10){${(-q_i)^{l(b)}\times}$}

\move(-20 -20)\lvec(-20 0)\lvec(0 0)\lvec(0 10)\lvec(60
10)\lvec(60 30)\lvec(75 30)\lvec(75 -20)\lvec(-20 -20)

\move(10 10)\lvec(20 20)\lvec(10 20)\lvec(10 10)\lfill f:0.8

\move(20 10)\lvec(30 20)\lvec(20 20)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(50 20)\lvec(50 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(60 10)\lvec(50 10)\lfill f:0.8

%\move(30 20)\lvec(30 10)

\htext(37 14){$_{\cdots}$}

\end{texdraw}}\hskip 10mm or
\hskip 2mm \raisebox{-0.4\height}{\begin{texdraw}\fontsize{9}{9}
\drawdim em \setunitscale 0.1 \linewd 0.5

\htext(-40 10){${(-q_i)^{l(b)}\times}$}

\move(-20 -20)\lvec(-20 0)\lvec(0 0)\lvec(0 10)\lvec(60
10)\lvec(60 30)\lvec(75 30)\lvec(75 -20)\lvec(-20 -20)


\move(10 10)\lvec(20 20)\lvec(20 10)\lvec(10 10)\lfill f:0.8

\move(20 10)\lvec(30 20)\lvec(30 10)\lvec(20 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(60 10)\lvec(50 10)\lfill f:0.8

\move(50 10)\lvec(60 20)\lvec(50 20)\lvec(50 10)\lfill f:0.8

%\move(50 20)\lvec(50 10)

\htext(37 14){$_{\cdots}$}

\end{texdraw}}
\end{center}


\medskip


\noindent respectively, where $l(b)$ is given in the above figure. In either
case, set $Y_L(b)=(\dots,y_{k+2},y_{k+1})$ and
$L_i(b;Y)=\varphi_i(Y_L(b))-\varepsilon_i(Y_L(b))$. Then we define
\begin{equation}
f_i\,Y=\sum_{b}q_i^{L_i(b;Y)}(Y\swarrow b),
\end{equation}
 where $b$ runs over all admissible and
virtually admissible $i$-slots in $Y$.

With these actions, we can verify that all the defining relations
for the quantum affine algebra $U_q(\mathfrak{g})$ are satisfied. The
verification is quite lengthy and based on the case-by-case check
argument (see \cite{KK} for the details). Hence we obtain:

\begin{thm}
The Fock space ${\mathcal F}(\Lambda)$ is an integrable
$U_q(\mathfrak{g})$-module in the category ${\mathcal O}^{int}$.
\end{thm}

It still remains to show that the affine crystal ${\mathcal
Y}(\Lambda)$ is the crystal of ${\mathcal F}(\Lambda)$. Let
${\mathcal L}(\Lambda)=\bigoplus_{Y\in{\mathcal Y}(\Lambda)}\mathbb{A}_0
Y$. It is easy to see that the pair $({\mathcal L}(\Lambda),{\mathcal
Y}(\Lambda))$ satisfies the first four conditions in Definition
\ref{crystal basis}. For the remaining three conditions, the main step
is to show that the Kashiwara operators on ${\mathcal Y}(\Lambda)$
induced by the $U_q(\mathfrak{g})$-module action on ${\mathcal
F}(\Lambda)$ coincide with the abstract Kashiwara operators on
${\mathcal Y}(\Lambda)$ given in Section~4. The proof of this step is
based on the crystal basis theory for $U_q(\mathfrak{sl}_2)$-modules
and the tensor product rule.

\begin{thm}\label {crystal basis for Fock space}
The pair $({\mathcal L}(\Lambda),{\mathcal Y}(\Lambda))$ is a crystal
basis of the Fock space ${\mathcal F}(\Lambda)$, where ${\mathcal
Y}(\Lambda)$ is the affine crystal given in Section 4.
\end{thm}

Using Theorem \ref{crystal basis for Fock space}, one can
decompose the Fock space ${\mathcal F}(\Lambda)$ into a direct sum of
irreducible highest weight modules over $U_q(\mathfrak{g})$ by
locating the maximal vectors in the affine crystal ${\mathcal
Y}(\Lambda)$.
\begin{cor}
\begin{equation}
{\mathcal F}(\Lambda)=
\begin{cases}
\bigoplus_{m=0}^{\infty}V(\Lambda-m\delta)^{\oplus p(m)}
& \text{if $\mathfrak{g}\neq D^{(2)}_{n+1}$,} \\
\bigoplus_{m=0}^{\infty}V(\Lambda-2m\delta)^{\oplus p(m)} &
\text{if $\mathfrak{g}= D^{(2)}_{n+1}$.}
\end{cases}
\end{equation}
\end{cor}


\section{Generalized LLT algorithm}
In this section, we generalize Lascoux-Leclerc-Thibon algorithm to
obtain an effective algorithm for constructing the global basis
$G(\Lambda)$ of the basic representation $V(\Lambda)$. Note that
$V(\Lambda)$ is realized as the $U_q(\mathfrak{g})$-submodule of
${\mathcal F}(\Lambda)$ generated by $Y_{\Lambda}$ and that the
crystal $B(\Lambda)$ of $V(\Lambda)$ is isomorphic to the
affine crystal ${\mathcal Y}_{\circ}(\Lambda)$ consisting of reduced
proper Young walls. Thus our goal is the following: for each
reduced proper Young wall $Y\in {\mathcal Y}_{\circ}(\Lambda)$, we
would like to find an algorithm for the corresponding global basis
element $G(Y)$ as a linear combination of proper Young walls in
${\mathcal Y}(\Lambda)$.

First, we describe the action of $f_i^{(r)}$ ($i\in I$) on ${\mathcal
Y}(\Lambda)$. For a proper Young wall $Y\in {\mathcal Y}(\Lambda)$,
write
\begin{equation}
f_i^{(r)}Y=\sum_{\substack{Z\in {\mathcal Y}(\Lambda) \\ {\rm
wt}(Z)={\rm wt}(Y)-r\alpha_i }}Q_{Y,Z}(q)Z,
\end{equation}
where $Q_{Y,Z}(q)\in \mathbb{Q}(q)$. For each $Z=(z_k)_{k=0}^{\infty}\in
\mathcal{Y}(\Lambda)$ with $Q_{Y,Z}(q)\neq 0$, there exists a unique
sequence of Young walls $Y=Y^{(0)},Y^{(1)},\dots,Y^{(r)}=Z$ such
that
\begin{itemize}
\item[(i)] $c_{k+1}Y_{k+1}=Y_{k}\swarrow b_{k+1}$ for a (virtually)
admissible $i$-slot $b_{k+1}$ of $Y_{k}$ and
$c_{k+1}\in\mathbb{Z}[q,q^{-1}]$,
\item[(ii)] $b_{k+1}$ is placed on $b_k$ or to the right of $b_k$.
\end{itemize}

We suppose that $b_k$ is located in the $i_k$th column
of $Y_{k-1}$ ($1\leq k\leq r$). Let $Q_{Y^{(k)},Y^{(k+1)}}(q)$ be
the coefficient of $Y^{(k+1)}$ in the expression of $f_iY^{(k)}$,
and define
\begin{equation}
Q^{\circ}_{Y,Z}(q)=\prod_{k=0}^{r-1}Q_{Y^{(k)},Y^{(k+1)}}(q)\in\mathbb{Z}[q,q^{-1}].
\end{equation}

If the $i$-blocks are of type ${\rm II}$, consider
\begin{equation*}
\begin{split}
J_1&=\{\,k\,|\,b_{k-1} \text{ is beneath } b_k\,\}, \\
J_2&=\{\,k\,|\,\text{there exists an $i$-block {\rm(}$\neq
b_{k-1}${\rm )} beneath $b_k$}\,\}, \\
J_3&=\{\,k\,|\,\text{there exists no $i$-block on and beneath
$b_k$}\,\}, \\
S&=\{\,k\in J_2\,|\,k-1\in J_3 \text{ and }
|z_{i_{k-1}}|=|z_{i_k}|-1\,\}.
\end{split}
\end{equation*}
Put $l=|J_1|$, $m=|J_2|$ and $n=|J_3|$. Note that $2l+m+n=r$. For
each $k\in S$, set $d_k=qc_k$.

\begin{lem}\label {QYZ} For $Y\in{\mathcal Y}(\Lambda)$, suppose
that $Q_{Y,Z}(q)\neq 0$ and ${\rm wt}(Z)={\rm wt}(Y)-r\alpha_i$
with $r\geq 1$ and $i\in I$. Let $\Box$ be the type of the
$i$-colored blocks. Then we have
\begin{equation}\label {qyz}
Q_{Y,Z}(q)=
\begin{cases}
Q^{\circ}_{Y,Z}(q)q_i^{\binom{r}{2}} & \text{ if $\Box={\rm I,
III}$}, \\
Q^{\circ}_{Y,Z}(q) \dfrac{q^{\sigma(l,m,n)}}{[2]^{l}\prod_{k\in
S}d_k} & \text{ if $\Box={\rm II}$},
\end{cases}
\end{equation}
where
$\sigma(l,m,n)=4\binom{l}{2}+\binom{m}{2}+\binom{n}{2}+2l(m+n)+mn$.
In particular, $Q_{Y,Z}(q)\in\mathbb{Z}[q,q^{-1}]$.
\end{lem}

Next, for a reduced proper Young wall $Y\in{\mathcal
Y}_{\circ}(\Lambda)$, choose the left-most column $y_l$ such that
$|y_l|\neq 0$ and denote by $b$ the top of $y_l$. Then, since $Y$
is reduced, $b$ must be a removable block of color, say, $i$.
Remove $b$ from $Y$ and denote by $Y_1$ the resulting Young wall
(if $y_l$ is twice $i$-removable, remove two $i$-blocks from
$y_l$). If $Y_1$ is reduced, we stop there and set
$\overline{Y}=Y_1$. If $Y_1$ is not reduced, then take the next
$i$-removable block in $y_{l-1}$ and remove it from $Y_1$ to get
$Y_2$ (if $y_{l-1}$ is twice $i$-removable, remove two $i$-blocks
from $y_{l-1}$). We continue this process from left to right until
we get a reduced proper Young wall and denote it by
$\overline{Y}$. Suppose $\overline{Y}$ is obtained by removing
$r$-many $i$-blocks from $Y$. If we write
$f_i^{(r)}\overline{Y}=\sum_Z Q_{\overline{Y},Z}(q)Z$, then by
Lemma \ref{QYZ}, it is easy to verify that
$Q_{\overline{Y},Y}(q)=1$.

By repeating the above process, we obtain a sequence of reduced
proper Young walls $\{Y^{(k)}\}_{k=0}^N$, where $Y^{(0)}=Y$,
$Y^{(1)} = \overline{Y^{(0)}} = \overline{Y}$, $\dots$,
$Y^{(k+1)}=\overline{Y^{(k)}}$, $\dots$,
$Y^{(N)}=\overline{Y^{(N-1)}} = Y_{\Lambda}$. Suppose that
$Y^{(k+1)}=\overline{Y^{(k)}}$ is obtained by removing $r_{k+1}$-many
$i_{k+1}$-blocks from $Y^{(k)}$ ($0\leq k\leq N-1$). Then we
define
\begin{equation}
A(Y)=f_{i_1}^{(r_1)}\cdots f_{i_N}^{(r_N)}Y_{\Lambda}\in
V(\Lambda)^{\mathbb{A}}.
\end{equation}
By definition, we have $\overline{A(Y)}=A(Y)$. Write
$A(Y)=\sum_{Z\in{\mathcal Y}(\Lambda)} A_{Y,Z}(q)Z,$ where
$A_{Y,Z}(q)\in \mathbb{Q}(q)$. Then the coefficients $A_{Y,Z}(q)$
satisfy the following properties:

\begin{prop}\label {AYZ}\mbox{}
\begin{itemize}
\item[{\rm (a)}] $A_{Y,Z}(q)\in \mathbb{Z}[q,q^{-1}]$.
\item[{\rm (b)}] $A_{Y,Z}(q)=0 \text{ unless } |Y|\unrhd |Z|$.
\item[{\rm (c)}] $A_{Y,Z}(q)\neq 0$ and $|Y|=|Z|$ imply $Y=Z$ and
$A_{Y,Y}(q)=1$.
\end{itemize}
\end{prop}

Recall that there exists a lexicographic ordering $>$ on the set
of partitions. For the proper Young walls with the same associated
partition, we fix an arbitrary total ordering $\succ$. We now
introduce a total ordering $>$ on the set ${\mathcal Y}(\Lambda)$ as
follows: we define $Y>Z$ if either $|Y|>|Z|$ or $|Y|=|Z|$ and $Y
\succ Z$. Note that if $|Y|\unrhd|Z|$ and $|Y|\neq|Z|$, then
$Y>Z$.

By Proposition \ref{AYZ}, $A(\Lambda)=\{\,A(Y)\,|\,Y\in {\mathcal
Y}_{\circ}(\Lambda)\,\}$ are linearly independent over
$\mathbb{Q}(q)$. Hence it is a $\mathbb{Q}(q)$-basis of
$V(\Lambda)$. We claim that $A(\Lambda)$ is actually an
$\mathbb{A}$-basis of $V(\Lambda)^{\mathbb{A}}$.

For a reduced proper Young wall $Y\in {\mathcal Y}_{\circ}(\Lambda)$,
consider the corresponding global basis element
\begin{equation}
G(Y)=\sum_{Z\in{\mathcal Y}(\Lambda)} G_{Y,Z}(q)Z.
\end{equation}
Since $G(\Lambda)$ is an $\mathbb{A}$-basis of
$V(\Lambda)^{\mathbb{A}}$, $G(Y)$ is an $\mathbb{A}$-linear
combination of the vectors $f_{i_1}^{(r_1)}\cdots
f_{i_N}^{(r_N)}Y_{\Lambda}$. Hence Lemma \ref{QYZ} implies
$G_{Y,Z}(q)\in\mathbb{Q}[q,q^{-1}]$. Since $G(Y)\equiv Y
\mod q{\mathcal L}(\Lambda)$, we may assume that
$G_{Y,Z}(q)\in\mathbb{Q}[q]$ and $G_{Y,Z}(q)\in q\mathbb{Q}[q]$
unless $Y=Z$. Write $G(Y)=\sum_{W\in {\mathcal Y}_{\circ}(\Lambda)}
H_{Y,W}(q)A(W)$, where $H=(H_{Y,W}(q))_{Y,W\in{\mathcal
Y}_{\circ}(\Lambda)}$ is the basis change matrix from $A(\Lambda)$
to $G(\Lambda)$ over $\mathbb{Q}(q)$.

Since $\overline{G(Y)}=G(Y)$ and $\overline{A(W)}=A(W)$ for all
$Y,W\in{{\mathcal Y}_{\circ}(\Lambda)}$, we get
$H_{Y,W}(q)=H_{Y,W}(q^{-1})$. Consider $G=(G_{Y,Z}(q))$,
$H=(H_{Y,W}(q))$ and $A=(A_{W,Z}(q))$, which are square matrices
indexed by ${\mathcal Y}_{\circ}(\Lambda)$ in decreasing total
ordering. Since $G=HA$ and $A$ is upper unit-triangular, we have
$H=GA^{-1}$, which implies $H_{Y,W}(q)\in\mathbb{A}$. Hence we
obtain:
\begin{prop}
$A(\Lambda)= \{\,A(Y)\,|\,Y\in {\mathcal Y}_{\circ}(\Lambda)\,\}$ is
an $\mathbb{A}$-basis of $V(\Lambda)^{\mathbb{A}}$.
\end{prop}

Recall that $G(Y)=\sum_{W\in {\mathcal
Y}_{\circ}(\Lambda)}H_{Y,W}(q)A(W),$ and let $W$ be the Young wall
which is maximal among the ones with $H_{Y,W}(q)\neq 0$ with
respect to the total ordering $>$. By the maximality of $W$ and
Proposition \ref{AYZ} (b), we have
$G_{Y,W}(q)=H_{Y,W}(q)A_{W,W}(q)=H_{Y,W}(q)$. Since
$G_{Y,W}(q)\in\mathbb{Q}[q]$ and
$G_{Y,W}(q)=H_{Y,W}(q)=H_{Y,W}(q^{-1})=G_{Y,W}(q^{-1})$,
$G_{Y,W}(q)$ must be a constant.
Moreover, since $G(Y)\equiv Y \mod q\mathcal{L}(\Lambda)$, we
conclude that $Y=W$ and $G_{Y,Y}(q)=H_{Y,Y}(q)=1$. Therefore, by
Proposition \ref{AYZ} (b), we can write
\begin{equation}\label {GYZ}
G(Y)=\sum_{Y\geq W}H_{Y,W}(q)A(W)=Y+\sum_{Y>Z}G_{Y,Z}(q)Z.
\end{equation}
Now, we can apply the algorithm for computing $G(Y)$ as was done
in \cite{LLT}. Fix a weight $\lambda\leq \Lambda$, and let
$Y_1>\cdots>Y_l$ be all the reduced proper Young walls in ${\mathcal
Y}_{\circ}(\Lambda)_{\lambda}$. Note that \eqref{GYZ} implies
$G(Y_l)=A(Y_l)$. Suppose that we have computed
$G(Y_{k+1}),\dots,G(Y_l)$. Also, from \eqref{GYZ}, $A(Y_k)$ is an
$\mathbb{A}$-linear combination of
$G(Y_k),G(Y_{k+1}),\dots,G(Y_l)$. For $k+1\leq s\leq l$, if the
coefficient of $Y_s$ in
$A(Y_{k})-\sum_{p=k+1}^{s-1}\gamma_p(q)G(Y_p)$ (or $A(Y_k)$ if
$s=k+1$) is $\sum_{i=0}^ra_iq^{-i}+\sum_{j=1}^{r'}b_jq^j$, then
define $\gamma_{s}(q)=\sum_{i=1}^{r}a_i(q^i +q^{-i}) + a_0$. Then
we obtain
\begin{equation*}
G(Y_k)=A(Y_k)-\gamma_{k+1}(q)G(Y_{k+1})-\cdots-\gamma_l(q)G(Y_l).
\end{equation*}
To summarize, we have \vspace*{-1mm}
\begin{thm} For a reduced proper Young wall $Y\in{\mathcal
Y}_{\circ}(\Lambda)$, the above algorithm yields the corresponding
global basis element
\begin{equation}
G(Y)=\sum_{Z\in{\mathcal Y}(\Lambda)}G_{Y,Z}(q)Z.
\end{equation}

\vspace*{-1mm}

\noindent Moreover, the coefficients $G_{Y,Z}(q)$ satisfy the
following conditions\,{\rm :}
\begin{itemize}
\item[{\rm (i)}] $G_{Y,Z}(q)\in\mathbb{Z}[q]$, \item[{\rm (ii)}]
$G_{Y,Z}(q)=0$ unless $|Y|\unrhd|Z|$,\nopagebreak[4]
\nopagebreak[4]\item[{\rm(iii)}] $G_{Y,Y}(q)=1$ and $G_{Y,Z}(0)=0$
if $Y\neq Z$.
\end{itemize}
\end{thm}

\begin{thebibliography}{10}
\bibitem{BK} J. Brundan, A. Kleshchev, {\em Hecke-Clifford superalgebras,
crystals of type $A^{(2)}_{2n}$ and modular branching rules for
$\hat{S}_n$}, Represent. Theory \textbf{5} (2001), 317--403
(electronic).
\MR{2002j:17024}
\bibitem{DJ} R. Dipper, G. James, {\em Representations of Hecke algebras
of general linear groups},  Proc. London Math. Soc. {\bf 52}
(1986), 20--52.
\MR{88b:20065}
\bibitem{Kac90} V. G. Kac, {\em Infinite-dimensional Lie algebras},
Cambridge University Press, 3rd
ed., Cambridge, 1990.
\MR{92k:17038}
\bibitem{Kang} S.-J. Kang, {\em Crystal bases for quantum affine Lie algebras
and combinatorics of Young walls},  RIM-GARC preprint (2000) {\bf
00-2}, Seoul National University, to appear in Proc. London Math.
Soc.
\bibitem{KK} S.-J. Kang, J.-H. Kwon, {\em Fock space
representations of quantum affine algebras and generalized
Lascoux-Leclerc-Thibon algorithm}, math.QA/0208204.
\bibitem{Kash} M. Kashiwara, {\em On crystal bases of the $q$-analogue
of universal enveloping algebras}, Duke Math. J. {\bf 63} (1991),
465--516.
\MR{93b:17045}
\bibitem{Kash93} M. Kashiwara, {\em Crystal bases and Littelmann's
refined Demazure character formula}, Duke Math. J. {\bf 71}
(1993), 839--858.
\MR{95b:17019}
\bibitem{Kash94} M. Kashiwara, {\em Crystal bases of modified
quantized enveloping algebras}, Duke Math. J. {\bf 73} (1994),
383--413.
\MR{95c:17024}
\bibitem{KMPY} M. Kashiwara, T. Miwa, J.-U. H. Petersen, C. M. Yung,
{\em Perfect crystals and $q$-deformed Fock space}, Selecta Math.
{\bf 2} (1996), 415--499.
\MR{98f:17012}
\bibitem{LLT} A. Lascoux, B. Leclerc, J.-Y. Thibon, {\em Hecke algebras at
roots of unity and crystal bases of quantum affine algebras},
Comm. Math. Phys. {\bf 181} (1996), 205--263.
\MR{97k:17019}
\bibitem{Lusz} G. Lusztig, {\em Canonical bases arising from quantized
enveloping algebras}, J. Amer. Math. Soc. {\bf 3} (1990), 447--498.
\MR{90m:17023}
\end{thebibliography}

\end{document}