%%%%%%%%%%%%%%%%%%%%%
% OrderingAffine.tex  October 1, 1999
%%%    ZZ! uses Springer format  lncse.cls 
\documentclass[]{lncse} 

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage[matrix]{xypic}
\usepackage{epsf}
\usepackage{ifthen}

\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\mod{\rm{ mod }}
\def\s{\scriptstyle }
\def\ss{\sigma}
\def\a{\alpha}
\def\g{\gamma}
\def\l{\lambda}
\def\L{\Lambda}
\def\e{\epsilon}
\def\d{\partial}
\def\om{\omega}

\def\S{{\mathfrak S}}
\def\SS{\widetilde{\mathfrak S}}
\def\Sym{{\mathfrak Sym}}

\def\cS{{\cal S}}
\def\B{{\cal B}}
\def\C{{\cal C}}

\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\A{{\mathbb A}}

%\def\S{{\frak S}}
%\def\SS{\widetilde{\frak S}}
%\def\Sym{{\frak Sym}}

%\def\cS{{\cal S}}
%\def\B{{\cal B}}
%\def\C{{\cal C}}

%\def\N{{\Bbb N}}
%\def\Z{{\Bbb Z}}
%\def\A{{\Bbb A}}

\def\bu{$\bullet$\quad}
\def\Perm{\mathop{\rm Perm}}
\def\qed{\hfill\raise -2pt\hbox{\vrule
\vbox to 10pt{\hrule width 4pt \vfill\hrule}\vrule}}
\def\puce{\vskip 5mm\noindent {$\scriptstyle\bullet$}\kern 8pt}
\def\td{\bigtriangledown }
\def\tu{\bigtriangleup }
\def\ket{\triangleright}
\def\dm{\diamondsuit}
\def\hh{\heartsuit }
\def\sp{\spadesuit }

\catcode`\@=11
\def\petitematrice#1{\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}}

\def\moyennematrice#1{\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\   \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}}

%%% weintrauben
\newdimen\unit
\def\o{$\scriptscriptstyle{{\rm o}}$}
\def\put(#1,#2)#3{\raise#2\unit\rlap{\kern#1\unit #3}\ignorespaces}

\def\h{{\unit=1mm
\hbox {\put(2,1.2){'}
       \put(1,2)\o
       \put(2,2)\o
       \put(3,2)\o
       \put(1.5,1)\o
       \put(2.5,1)\o
       \put(2,0)\o\
}\kern 3.5 \unit}}

\newdimen\squaresize \squaresize=12pt
\newdimen\thickness \thickness=0.5pt

\def\square#1{\hbox{\vrule width \thickness
   \vbox to \squaresize{\hrule height \thickness\vss
      \hbox to \squaresize{\hss#1\hss}
   \vss\hrule height\thickness}
\unskip\vrule width \thickness}
\kern-\thickness}

\def\vsquare#1{\vbox{\square{$#1$}}\kern-\thickness}
\def\blank{\omit\hskip\squaresize}

\def\young#1{
\vbox{\smallskip\offinterlineskip
\halign{&\vsquare{##}\cr #1}}}



\def\s{\scriptstyle }
\catcode`@=11
\def\m@th{\mathsurround=\z@}
\def\smatrix#1{\null\,\vcenter{\baselineskip=8pt\m@th
    \ialign{\hfil$\s ##$\hfil&&\ \hfil$\s ##$\hfil\crcr
      \mathstrut\crcr\noalign{\kern-\baselineskip}
      #1\crcr\mathstrut\crcr\noalign{\kern-\baselineskip}}}\,}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

%\frontmatter          % for the preliminaries
%\mainmatter              % start of the contributions

\title{Ordering the affine symmetric group}
\author{Alain Lascoux}
\institute{ C.N.R.S., Institut Gaspard Monge,  
 Universit\'e de Marne-la-Vall\'ee,  \\
 5 Bd Descartes, Champs sur Marne,   
 77454 Marne La Vall\'ee Cedex 2 FRANCE \\
  Alain.Lascoux@univ-mlv.fr}

\maketitle


\begin{abstract}
 We review several descriptions of the affine symmetric group.
We explicit the basis of its Bruhat order. 
\end{abstract}


\section{Introduction}


For a group defined by generators, one has a notion of {\it Cayley graph} 
representing the succesive generation of elements of the group by product
of generators. This is specially interesting in the case of a Coxeter group
$(W,\cS)$, $\cS$ being the set of generators, because one has a length
function which filters the elements of $W$ according to the minimum length
of the words in the generators of $W$ which expresses them
(words of minimum length are called {\it reduced decompositions}).

The Cayley graph of $W$ naturally provides an ordering (the {\it weak order})
of $W$: $w'\leq w$ iff any reduced decomposition of $w'$ is the left factor
of at least one reduced decomposition of $w$, in other words, iff there
is a path from $w'$ to $w$ in the Cayley graph of $W$.

However, if one takes the group algebra of $W$ instead of $W$,
and a reduced decomposition $[i,j,\ldots, h]:= s_i s_j \cdots s_h$ of an
element $w$, then one wants the order to be such that any  expression 
of the type
$(1+s_i)(1+s_j)\cdots (1+s_h)$ has leading term (with respect to the order)
$w$.

In that case, it is clear that the expansion of $(1+s_i)\cdots (1+s_h)$
involves only the elements obtained by evaluating in $W$ the subwords 
of $[i,j,\ldots, h]$. One easily checks that the set of such elements
is independent of the choice of a reduced decomposition of $w$
(though the set of subwords is not).

Let us write $w'\leq w$ (for the {\it Bruhat order}) iff there exists 
a decomposition of $w'$ which is a subword of a reduced decomposition of
$w$.  Let us also write $[1,w]$ for the interval 
$\{ w'\, |\, 1\leq w' \leq w\}$, $1$ being the identity element of $W$.

The above definition of the Bruhat order \cite{Bo} is not very efficient, since 
one has much too many subwords of a reduced decomposition of $w$ compared
to the cardinality of $[1,w]$.

Ehresmann\cite{Eh} found another definition, in the case of the symmetric group,
by using all the projections 
$W  \buildrel p_i \over{\longrightarrow} W/W_i$ onto all the quotient
spaces $W/W_i$ ( $W_i$= maximal parabolic, i.e. group generated by the 
elements of $\cS \setminus s_i$).
Ehresmann's definition is 
\begin{equation}
 w'\leq w  \ \Leftrightarrow \ p_i(w') \leq p_i(w)\ ,  \ i=1,2,\ldots
\end{equation}
Now, it makes sense because one has an easy description of the
Bruhat order on $W/W_i$ and of the projection. In the case of the symmetric
group, $W/W_i$, as an ordered set, can be identified with the space of all
partitions, the diagram of which are included in a fixed rectangle
(the order on partitions being inclusion of diagrams).

This description has been generalized by Deodhar\cite{De} to all Coxeter groups.

In \cite{LS}, M.P. Sch\"utzenberger and I gave another description. It uses 
a notion which is valid for any ordered set $X$.
One defines the basis $\B$ of $X$ to be the following subset:
\begin{equation}
 b\in \B \ \Leftrightarrow \ \exists\,  x\in X, \ b\ 
 {\rm is\ minimum\ in\ the\ complement\ of}\ [1,x]\ . 
\end{equation}
Given $x\in X$, let furthermore $\B(x)$ denote the set $\{ b\in\B,\, b\leq
x\}$. We have shown in [LS] that in the case  $X$ is finite, then
\begin{equation}
 x\leq y \ \Leftrightarrow \  \B(x) \subseteq \B(y) \ . 
\end{equation}
Now, it happens that in the case of a Coxeter group $W$ the set $\B(w)$ 
is "small" compared to $[1,w]$ or to the set of subwords of a reduced
decomposition of $w\in W$. 

The bases of the symmetric group and of the hyperoctahedral group, as
well as the map $w \mapsto \B(w)$ 
are given in \cite{LS}. Geck and Kim \cite{GK} have determined the bases of all
finite Coxeter groups. 

The construction of bases passes to the quotient spaces $W/W_i$ 
(and, as we have said, it is sufficient to treat only these spaces, 
because of (1)).
For example, for the symmetric group $\S_n$, its quotient 
$\S_n/\S_m\times \S_r$, $n=m+r$,  can be identified with the set of partitions
contained in $m^r $, and its basis consists of all (non void) rectangular
partitions $i^j$: $i\leq m$, $j\leq r$. The elements of the basis have in 
fact a geometrical meaning, being in correspondence with determinantal
varieties \cite{La}. 

Now, the notion of a basis can be extended to infinite sets $X$, when $X$
satisfy some mild hypotheses.

Let us take an affine Coxeter group. Then one still has a length function,
which allow to filter the group according to length. Let $W^{\ell}$
be the set of elements of length $\leq \ell$. If $\ell(w)\leq \ell$,
then the full interval $[1,w]$ is contained in $W^{\ell}$.
Let $\B^{\ell}$ be the basis of $W^{\ell}$.

One has that $\B= \cup \B^{\ell}$ and one can check that
\begin{equation}
  w'\leq w \ \Leftrightarrow \  \B(w') \subseteq \B(w) \ . 
\end{equation}
 

In the following, we shall describe the basis of the affine symmetric
group $\SS_n$ and its Bruhat order.


\section{The Affine Symmetric Group}

Let $n$ be an integer and $\SS_n$ be the quotient of the infinite symmetric
group (generated by $s_i,\, i \in \Z$ under the relations 
$s_i = s_{i+n})$, $i \in \Z$. In other words,  $\SS_n$ is generated 
by $s_0,\ldots s_{n-1}$ satisfying the braid relations (with $s_n:=s_0$)
\begin{equation}
 s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1} \; ,\;
s_i s_j = s_j s_i\; ,\; |i-j|\not\cong 1 \ \mod\; n \; ,\; 0\leq i,j\leq n-1 .
\end{equation}


The group $\SS_n$ can be thought as acting on infinite vectors 
$v= [\ldots, v_i, \ldots]$, $i\in \Z$:  
the generator $s_i$
transposes in $v$  components $v_{i+kn}, v_{i+1+kn}$ for all $k\in \Z$
simultaneously.   Usually, one takes vectors $v$ such that $v_{i+n}=v_i+n,
\, i\in \Z$. Associating to the
identity element the \lq\lq vacuum vector\rq\rq
 $\ket$ : $\ket_i=i$, $\forall i\in \Z$,
then the orbit of $\ket$ is in bijection with $\SS_n$ and
 one can code any element $\ss\in\SS_n$ by the image $v= \ket\, \ss$ 
of $\ket$ under $\ss$, or equivalently by 
the {\it window} $[v_1,\ldots, v_n]$.

In other words, elements of $\SS_n$ can be coded by vectors in $\Z^n$, 
starting from $[1,2,\ldots, n]$, with the action
\begin{equation}
\begin{array}{r@{\,}l}
 [\cdots v_i,v_{i+1} \cdots\, ]\, s_i &=  [\cdots v_i,v_{i+1} \cdots\, ]  \; ,
    \quad 1\leq i \leq n-1 \\[0cm] 
 [v_1\, ,\,  \ldots\, ,\, v_n]\, s_0 &= [v_n-n\, ,\, \ldots\, ,\, v_1+n]\; .   
\end{array}
\end{equation}


One has in fact many other choices to represent $\SS_n$ by infinite vectors
satisfying periodicity conditions. One can also modify the definition
of \lq\lq transposing two adjacent components\rq\rq. 

For example, let $c(\ket)$  be the infinite vector with all components
equal to 0, and let $c(\ss)$ be the image of $c(\ket)$ under the action
\begin{equation}
 [\cdots c_j,c_{j+1} \cdots\, ]\, s_i =  [\cdots c_{j+1}+1,c_j \cdots\, ]  \ ,
    1\leq i \leq n-1, c_i\leq c_{i+1}, \forall j\cong i\ mod \ n\ . 
\end{equation}
This action preserves equalities  $c_j=c_{j+n}$, and once more, one can 
restrict vectors to their components $1,\ldots, n$. In that set-up, one has
\begin{equation}
 [c_1\, ,\, \ldots\, ,\, c_n]\, s_0 = 
[c_n\, ,\, \ldots\, ,\, c_1+1] \ , c_n\leq c_1
\ . 
\end{equation}


Now, it is easy to check that the mapping $ \SS_n \ni \ss \mapsto 
 [c_1,\ldots, c_n]\in \N^n$ is a bijection. 
It can be easily described without passing through a reduced decomposition
of $\ss$ (cf. \cite{BB}).  

By restriction, it induces 
a bijection from $\S_n$ onto the set of vectors such that 
$c_1\leq n-1,\ \ldots,
c_n\leq 0$. 
Such a vector is called the {\it Lehmer code}
of the corresponding permutation $\ss$ \cite{Ke} and encodes the 
\lq\lq inversions\rq\rq
of $\ss$.  
This is still true in the infinite case (cf. \cite{BB}, \cite{Er}).  
Let us call {\it scalar weight}  of $c(\ss)$ the sum $c_1+\cdots +c_n$. 
Then the above action 
shows that the scalar weight increases by 1 if length increases, and thus 
the scalar weight of $c(\ss)$ is equal to the length $\ell(\ss)$.
Shi \cite{Sh} gives another description of the length function, 
directly from the window of $\ss$. 

\section{Quotient of $\SS_n$ modulo $\S_n$}

Since all $s_i$'s play a symmetrical r\^ole, all quotient spaces of $\SS_n$
modulo a maximal parabolic are isomorphic. Let us choose the finite 
symmetric group $\S_n$, generated by $s_1,\ldots, s_{n-1}$, as a maximal
parabolic.   

The unique element of minimum length of a class $\ss\, \S_n$ is
 the unique element $\zeta$ of the class such that 
$$\ell(\zeta\, s_i) < \ell(\zeta)\  \Leftrightarrow \ i=0\ .$$
Therefore, minimum elements are exactly those elements with 
(strictly) increasing window
$[v_1,\ldots, v_n]\; :\;  v_1<v_1<\cdots <v_n$.

 From (2.3) one deduces that codes of such elements are
(weakly) increasing vectors $[c_1,c_2,\ldots,c_n]$ such that $c_1=0$,
that is, are  partitions of length $\leq n-1$. 

Now, there is a third coding of $\SS_n/\S_n$ by infinite vectors $u$,
with periodicity $u_{j+n}= u_j-1$, $\forall j\in \Z$. 
It amounts to take origin vector such that $[u_1,\ldots,
u_n]=[\, 0,\ldots,0\, ]$, and act by 
\begin{equation}
\begin{array}{r@{\,}l}
 [\cdots u_i,u_{i+1} \cdots\, ]\; \buildrel s_i \over{\longrightarrow}\;
 & [\cdots u_{i+1}\, ,\,  u_i  \cdots\, ]  \ ,
    1\leq i \leq n-1\ , \\[2mm] 
 [u_1, \ldots, u_n]\; \buildrel s_0\over{\longrightarrow}\; 
& [u_n+1,  \ldots, u_1-1] \ .  
\end{array}
\end{equation}


 From a vector $u$ in $\Z^n$ such that $u_1+\cdots +u_n=0$
(call {\it weight} such a vector),
one can recover an element of $\S_n \backslash \SS_n$ as follows
(the quotient is now on the left):
one has to sort increasingly the vector
$[ 1+nu_1,\ldots, \, n+ nu_n]$.

For example, $n=3$, $u=
[7,-4,-3]$  gives the vector $[22,-10,-6]=
[1+3\times 7, 2-3\times 4, 3-3\times 3]$
which is sorted into $[-10,-6,22]$,
and is an element of $\SS_3$ of minimum length (of code $[0,1,19]$)
in its coset modulo $\S_3$.

B. Leclerc  has shown me that it is more convenient, in the theory of roots
of affine Weyl groups, to add an \lq\lq imaginary root\rq\rq and 
 use \lq\lq extended weights\rq\rq which are vectors
in $\Z^{n+1}$ : one takes for origin $[0,\ldots,0]\in \Z^{n+1}$
and the action is 
\begin{equation}
\begin{array}{r@{\;}l} 
 [\cdots w_i,w_{i+1} \cdots\, ]\; \buildrel s_i \over{\longrightarrow}\;
 & [\cdots w_{i+1}\, ,\,  w_i  \cdots\, ]  \ ,
    1\leq i \leq n-1\ , \\[2mm] 
 [w_1, \ldots, w_n,\, w_{n+1}]\; \buildrel s_0\over{\longrightarrow}\;
& [w_n+1,\ldots,\, w_1-1,\,  w_1-w_n+w_{n+1}-1] \ .  
\end{array}
\end{equation}


A weight $u\in \Z^n$ already has an unnecessary component, 
since the sum of components is zero :
one can write 
 $u=x_1\a_1+\cdots +x_{n-1}\a_{n-1}$, the $\a_i$ being the simple
roots $[1,-1,0,\ldots,0],\ldots,$
$ [0,\ldots,0,1,-1]$.

However, it happens that going to $\Z^{n+1}$ simplifies some constructions,
the extra component having combinatorial interpretations.

\section{$n$-Cores and Bruhat order}

None of these three codings furnishes a description of the Bruhat order.
Fortunately, Fock spaces and crystal graphs indicate a fourth one (\cite{MM},
\cite{LLT}, \cite{FLOTW}). 
Now one will represent elements of  $\SS_n/\S_n$ by partitions
which are {\it $n$-cores}, that is partitions such that one cannot
erase a border strip (also called outer ribbon)
 of length $n$ from their diagram (cf. \cite{JK}). 

One numbers diagonals of diagrams with the numbers (which are called
{\it colours})  $0,1,\ldots , n-1$ periodically,
the main diagonal being of colour 0.

Now, take the diagram of a an $n$-core such that no corner box is of colour
$i$. Then the 
action of $s_i$, $i=0,\ldots, n-1$ on this diagram is to add
all possible boxes which are of colour $i$, in such a way that the
resulting object is still the diagram of a partition.
If there is at least one corner box of colour $i$, then the action
consists in  erasing
all peripheal boxes of colour $i$  such that one still gets a diagram
of a partition.

It is an easy combinatorics to check that   from an $n$-core one still gets
an $n$-core, and that the operation is involutive. Now, one does not
try to check the braid relations, because one takes the classics again 
(\cite{JK} p.78) 
and one sees that one can use, instead of an $n$-core, still another object
which is called {\it abacus}.

Let $\dm$ be a (decreasing) partition extended to infinity 
on the right by 0's:
$\dm= [\dm_1, \dm_2,\ldots, \dm_k, 0,0,\ldots]$. Let ${\cal A}$
be the set of numbers $\{ \dm_1-0, \dm_2-1, \dm_3-2,\ldots\}$
interpreted as balls
in an abacus of width $n$ and bi-infinite height, with places
numbered consecutively as follows:

\setbox2=\hbox{ $\scriptstyle level$}
\[
\begin{array}{cccccc}
 \vdots &\cdots &\vdots &\vdots &&\copy2 \\
          1-2n &\cdots  &-n-1 &-n  && {\scriptstyle -1}\\
           1-n&\cdots &1 &0    && {\scriptstyle 0}\\
           1&\cdots &n-1 &n   &&{\scriptstyle 1}\\
           n+1&\cdots &2n-1&2n  &&{\scriptstyle 2}\\
            \vdots & \cdots &\vdots &\vdots &&\vdots \\
\end{array} \ .
\]
Putting  balls in positions belonging to ${\cal A}$ gives by definition
the {\it $n$-abacus} of the partition $\dm$.

That $\dm$ be an $n$-core is equivalent to the fact that balls are vertically
packed upwards (\cite{JK} p.80).  

Reading  levels of bottom balls, one gets a vector in $u\in \Z^n$ such that
$u_1+\cdots +u_n=0$, that is, one gets a weight.
This construction is, indeed, a bijection between
weights in $\Z^n$ and $n$-cores or elements of $\S_n\backslash \SS_n$  or of
$\SS_n/\S_n$.   


For example, the  5-core $[4,2^3,1^4]$ 
gives by substraction the infinite vector
 $$[4,1,0,-1,-3,-4,-5,-6,-8,-9,\ldots]$$ 
and the abacus
\[
\begin{array}{ccccccc} &&&&&&\box2\\
 -14 &-13 &-12 &-11 &-10 &&{\scriptstyle -2} \\
            -9 & -8 & \cdot &-6 &-5 &&{\scriptstyle -1} \\
             -4 &-3 &\cdot &-1 &0 && {\scriptstyle 0}\\
              1 &\cdot &\cdot &4 &\cdot && {\scriptstyle 1}\\
\end{array} 
\]
the weight $[1,0,-2,1,0]$, the code $[0,1,2,2,4]$
and the element  $[-7,2,5,6,9]$ of $\SS_5/\S_5$.

For each of the different objects that have been given, the description of
the action of the simple generators $s_i$  allows to prove that the above
constructions are indeed bijections and that the elementary operations
represent the generators of $\SS_n$.

Now each of the objects that we have displayed 
will provide informations about the corresponding
element of the affine group, information which would sometimes not
have been easy to
get in another description, though all bijections here are elementary.
For example, it is amusing to look at what becomes the addition of
weights (plain addition of vectors) in terms of $n$-cores, or of codes.

Here is some example computed with ACE \cite{Ve}, 
where we give a chain of elements
of $\SS_4/\S_4$, with their code, the corresponding extended weight in $\Z^5$
and the $4$-core with its colours. The reader should beware that
simple transpositions act from the left on codes and on group elements,
and from the right on weights and cores.

\setbox2\hbox{$ \begin{array}{c} 
{\s Code}\\ {\s Group\ element}\\ {\s Ext.\, weight}\\ 
{\s Core}\\ \\ \\ \\ {\s Diagram}
\end{array} $}

\setbox30\hbox{$ \buildrel s_0 \over{\longrightarrow} $}
\setbox31\hbox{$ \buildrel s_1 \over{\longrightarrow} $}
\setbox33\hbox{$ \buildrel s_3 \over{\longrightarrow} $}

\[
 \raise  24pt \box2 \quad
\begin{array}{c}
 [0,1, 2, 7]\\[0pt]
 [-6, 1, 4, 11]\\[0pt] 
 [0, -2, 2, 0, -4] \\[0pt]
 [7, 4, 2, 2, 1, 1, 1]\\[3pt]
{\scriptstyle
\begin{array}{lllllll}
 \\ 2\\
 3\\      
 0\\        
 1& 2\\     
 2& 3\\
 3& 0& 1& 2\\
 0& 1& 2& 3& 0& 1& 2\\
\end{array}
}%
\end{array}
\quad 
\box31
\quad  
\begin{array}{c}
[0, 2, 2, 7]\\[0pt]
[-7, 2, 4, 11] \\[0pt]
[-2, 0, 2, 0, -4] \\[0pt]
[7, 4, 2, 2, 2, 1, 1, 1]\\[3pt]
{\scriptstyle
\begin{array}{lllllll}
 1\\
 2\\
 3\\
 0& 1\\
 1& 2\\
 2& 3\\
 3& 0& 1& 2\\
 0& 1& 2& 3& 0& 1& 2\\
\end{array}
}%
\end{array}
  \quad\copy33
\]
\[
\begin{array}{c}
[0, 2, 2, 8]\\[0pt]
[-7, 2, 3, 12]\\[0pt]
[-2, 0, 0, 2, -4]\\[0pt]
[8, 5, 2, 2, 2, 1, 1, 1]\\[3pt]
{\scriptstyle
\begin{array}{llllllll}
 \\ \\  1\\ 
 2\\ 
 3\\ 
 0& 1\\ 
 1& 2\\ 
 2& 3\\ 
 3& 0& 1& 2& 3\\ 
 0& 1& 2& 3& 0& 1& 2& 3\\ 
\end{array}
}%
\end{array}
\quad\box30\quad
\begin{array}{c}
[0, 2, 2, 9]\\[0pt]
[-8, 2, 3, 13]\\[0pt]
[3, 0, 0, -3, -9]\\[0pt]
[9, 6, 3, 2, 2, 2, 1, 1, 1]\\[3pt]
{\scriptstyle
\begin{array}{llllllllll}
 \\ 0\\
 1\\
 2\\
 3& 0\\
 0& 1\\
 1& 2\\
 2& 3& 0\\
 3& 0& 1& 2& 3& 0\\
 0& 1& 2& 3& 0& 1& 2& 3& 0\\
\end{array}
}%
\end{array}
\quad\box33\quad
\begin{array}{c}
[0, 2, 3, 9]\\[0pt]
[-9, 2, 4, 13]\\[0pt]
[3, 0, -3, 0, -9]\\[0pt]
[9, 6, 3, 3, 2, 2, 2, 1, 1, 1]\\[3pt]
{\scriptstyle
\begin{array}{llllllllll}
 3\\ 
 0\\ 
 1\\ 
 2& 3\\ 
 3& 0\\ 
 0& 1\\ 
 1& 2& 3\\ 
 2& 3& 0\\ 
 3& 0& 1& 2& 3& 0\\ 
 0& 1& 2& 3& 0& 1& 2& 3& 0\\ 
\end{array}
}%
\end{array}
\]

\medskip 
For what concerns the Bruhat order, we shall see that we need  $n$-cores.
 Codes, which are also (increasing) partitions for minimum elements
in their coset modulo $\S_n$, would
not give (by inclusion) the proper order, but only a sub-order.
Bj\"orner and Brenti (\cite{BB}, th 6.3 and th.6.5) obtained a criterium 
describing the Bruhat order in 
terms of monotonous functions; it is equivalent to  the following proposition.

Let us denote by $\C$ the morphism from $\SS_n/\S_n$
(identified with the set of  elements of $\SS_n$ whicht are of minimum
length in their coset) onto $n$-cores.

\begin{proposition}
  Let $\ss,\omega \in \SS_n/\S_n$. Then $\ss \leq \omega$ iff
the diagram of $\C(\ss)$ is contained in the diagram of $\C(\om)$.
\end{proposition}

\begin{proof}
 Take any corner of the diagram of $\C(\om)$ and let $i$ be its colour.
Then $s_i\, \om <\om$ and one knows that (\cite{Bo}, \cite{De})
$$ \ss \leq \om  \ \Leftrightarrow  min(s_i\ss, \ss)    \leq s_i \om $$
Now, we have to compare two $n$-cores with less boxes, and as in the finite
case, we are finally reduced to know how to compare two elements of length
differing by 1.                  \qed
\end{proof}

\section{Basis of the Bruhat order}


When one needs to store huge sets of elements of the affine group, together
with
the information about the Bruhat order, then it is not efficient 
to also store the associated partitions ( for an element in $\SS_n$, we need
$n$ partitions, because we have  $n$ different projections $\SS_n \mapsto
\SS_n/\S_n$). 
It is well illustrated by
Geck and Kim \cite{GK}, in the finite case, that one has instead 
to use  the basis
of the order, as defined above. In this section we shall determine the
basis of $\SS_n/\S_n$. 

Let us first introduce some special $n$-cores.

Given two strictly positive numbers $p,q$ such that $p+q=n$,
a {\it $(p,q)$-staircase} is a partition $E$ such that the stairs of its
diagram
are all of heigth $p$ and width $q$, except for the top stair which is
of width $\leq q$ and the bottom stair which is of heigth $\leq p$. 

In other words, $E=[E_1,E_2,\ldots, E_k,0,\ldots]$, the non zero differences
$E_i-E_{i+1}$ are all equal to  $q$, except possibly for the last one 
$E_k-0$ which is such that $1\leq E_k\leq q$, and the partition conjugate
 to $E$ (obtained by transposing the axes)
satisfies the same conditions with $p$ instead of $q$.

Let us notice that all the corners of a staircase have the same colour,
and that, given (p,q) and a point in the Cartesian quadrant $\N\times \N$,
there existis one and only one $(p,q)$-staircase having this point as a corner.

Let ${\cal D}$ be the diagram of an $n$-core, and $\tu$ one of its corners.
$\td$ the maximal box of ${\cal D}$ on the first diagonal
of the same colour above (resp. below) 
the diagonal containing $\tu$ (if it exists). 
Define the {\it left-rectrix} (resp. {\it right-rectrix})
of ${\cal D}$
of {\it pivot} $\tu$ to be the staircase having $\tu$ and $\td$ as corners.
$n$-Cores which are too small to have two diagonals of the same colour 
are in fact staircases. Let us say in that case 
that they have only one rectrix which
coincide with themselves.  

For the 4-core $[5, 4, 3, 2, 1, 1, 1]$, here is an example of a
left-rectrix (figured by $\hh$'s):

\[
\begin{array}{lllll}
    2  \\  
    3\\ 
    0\\ 
    1 &2\\ 
    2 &3& 0\\ 
    3& 0 &1& 2\\ 
    0& 1& 2& 3& 0  
\end{array}
\quad \mapsto\quad
\begin{array}{lllll}
    2  \\ 
    3\\ 
    \td\\ 
    1 &2\\ 
    2 &3& \tu\\ 
    3& 0 &1& 2\\ 
    0& 1& 2& 3& 0  
\end{array}
\quad \mapsto\quad 
\begin{array}{lllll}
    2  \\ 
    3\\ 
    \hh\\ 
    \hh &2\\ 
     \hh &\hh& \hh\\ 
    \hh& \hh &\hh& 2\\ 
    \hh& \hh& \hh& \hh& \hh
\end{array}
\]
\smallskip 
Recalll that 
in the finite symmetric group case, cosets representatives are diagrams
contained in a rectangle; rectrices of a diagram ${\cal D}$ are the
maximal rectangular partitions contained in it \cite{LS}. Describing 
Bruhat order on a finite symmetric group essentially reduces to 
decomposing partitions into maximal rectangles. 

\begin{lemma}
 Let ${\cal D}$ be the diagram of an $n$-core. Then
${\cal D}$ is the supremum (with respect to inclusion of diagrams)
of its rectrices.
\end{lemma}
\begin{proof}
 Since ${\cal D}$ is contained in the supremum of any family
of diagrams such that each corner of  ${\cal D}$ is contained into at least
one
of them, it is sufficient (and immediate) to check that each
rectrix of  ${\cal D}$ is contained entirely in ${\cal D}$.     \qed
\end{proof}



In order to determine the basis of $\SS_n/\S_n$, we need some more properties
of staircases.

\begin{lemma}
Let ${\cal D}$ and ${\cal F}$ be diagrams of $n$-cores such that
${\cal D}$ is not a staircase and ${\cal D}$ 
is not included into  ${\cal F}$. Then there exists at least one staircase
$E$ in ${\cal D}$ such that $E \not \subset {\cal F}$. 
\end{lemma}
\begin{proof}
Take any corner $\clubsuit$ of ${\cal D}$ which does not belong to ${\cal F}$.
Then any staircase with corner  $\clubsuit$ and included into  ${\cal D}$
will do.  \qed 
\end{proof}


\begin{lemma}
 Let $E$ be $(p,q)$-staircase, having at least one internal corner
$\clubsuit$
 (i.e. a corner which is not on the first column, nor on the bottom row).
Let $\td$, $\tu$ be the east and south neighbour boxes of $\clubsuit$,
and let $E_{\td}$ be the $(n-1,1)$-staircase of corner $\td$
and $E_{\tu}$ be the $(1,n-1)$-staircase of corner  $\tu$.
 Let moreover $F$ be the partition which is the supremum of $E_{\td}$
and of $E_{\tu}$ (it is an $n$-core).

Then $E$ is minimum in the complementary
 of the interval $[\emptyset \, \leq F]$.
\end{lemma}


\begin{proof}
Suppose that an $n$-core $E'$ is strictly contained in $E$ and not in $F$.
Take a box of $E'$ which does not belong to $F$ and a staircase $E"$ 
contained in $E'$ of corner this box. Then $E"$ is not included in $F$. 
Therefore it is sufficient to prove that each staircase  $E"$ strictly
contained in $E$ is also contained in $F$.
 If $E"\subset E$ contains a box which is
an internal corner of $E$, then this box is a corner of  $E"$ and $E"=E$.
Therefore $E"$ avoids all internal corners of $E$, in particular $\clubsuit$.
But is is clear that the part of $E"$ which is right of $\clubsuit$
is contained in $E_{\tu}$, and that the part which is left of $\clubsuit$
is contained in $E_{\td}$. This implies that $E"\subseteq F$.  \qed
\end{proof}



For example, take the $(2,2)$-staircase $\h\; :=\,  [7,5,5,3,3,1,1]$,
choosing the corner pointed by $\clubsuit$, its diagonal
being figured by $\sp$'s:
\[  \raise -38 pt
\young{ 2\cr 3\cr 0& 1& 2\cr 1& 2& 3\cr 2& 3& 0& 1& 2\cr 3& 0& 1& 2& 3\cr
 0& 1& 2& 3& 0& 1& 2\cr }
 \kern 1 cm
\begin{array}{lllllll}
\h\\\h\\ \h&\td &\clubsuit\\
  \h&\sp &\tu\\
 \sp&\h&\h&\h&\h\\
 \h&\h&\h&\h&\h\\
  \h&\h&\h&\h&\h&\h&\h \\   
\end{array}
\]
Then any 4-core strictly contained in $\h$ is also contained in the 
4-core  
\[
F \; =\;  [12,9,6,3,\ 2,1,1,1] = \quad 
%\petitematrice{
{\renewcommand{\arraystretch}{0.8}
{\arraycolsep=1pt
\begin{array}{*{12}{l}}
\td\\  \td\\ \td\\  \td&\td \\ 
  \td &\sp &\tu\\ 
 \sp&\tu &\tu&\tu&\tu &\tu\\ 
 \tu&\tu&\tu &\tu&\tu &\tu &\tu &\tu &\tu\\ 
 \tu&\tu&\tu &\tu&\tu &\tu &\tu &\tu &\tu &\tu &\tu &\tu\\ 
\end{array}
}
}
\]

We have left aside the cores 
 having no internal corner,
that is {\it hook}-partitions. A case-by-case analysis which offers no
difficulty gives the following classification.

\begin{lemma}
 Partitions
 $$[1];\ [2],\ldots [n-1];\ [1^2],\ldots , [1^{n-1}]; \ [n,1], [2,1^{n-1}]$$
belong to the basis, but not the other hooks with $n+1$ boxes:
$[3,1^{n-2}], \ldots,\,  [n-1,1^2]$, though they are $(p,q)$-staircases.
\end{lemma}

\begin{sloppypar}
 For example, for $n=5$, the basis contains the hooks
$[1]; [2],[3],[4]$;
$[1^2],[1^3],[1^4]; [5,1], [2,1^3]$,
but not  $[3,1^3]$ nor $[4,1^2]$. Indeed, $[3,1,1,1]$ is the supremum of
$[3]$ and $[1,1,1,1]$, and $[4,1,1]$ is the supremum of $[4]$ and $[1,1,1]$.
\end{sloppypar}

In summary, one has the following characterization of the basis of
$\SS_n/\S_n$.

\begin{theorem}
 The basis of $\SS_n/\S_n$ for the Bruhat order consists in all
$(p,q)$-staircases, $p+q=n$, excepted the hooks $[3\, 1^{n-2}], \ldots,
[n-1,1,1]$.
\end{theorem}

We have now all the necessary tools to handle the
affine symmetric group together with its Bruhat order.
In particular, elements will be represented by the decomposition
of their associated cores into maximal sub-staircases.

For example, the $5$-core
$\h\; = [6, 6, 5, 4, 3^4, 2^4, 1^4]$, corresponding to the group element
$[-15, 2, 4, 11, 13]$, with code $[0, 3, 3, 7, 8]$ and length
21, is decomposed into the
following three staircases
\[
{\renewcommand{\arraystretch}{0.8}
{\arraycolsep=1pt
\begin{array}{*{12}{l}}
  0\\ 
  1\\ 
  2\\ 
  3\\ 
  4& 0\\ 
  0& 1\\ 
  1& 2\\ 
  2& 3\\ 
  3& 4& 0\\ 
  4& 0& 1\\ 
  0& 1& 2\\ 
  1& 2& 3\\ 
  2& 3& 4& 0\\ 
  3& 4& 0& 1& 2\\ 
  4& 0& 1& 2& 3& 4\\ 
  0& 1& 2& 3& 4& 0\\ 
\end{array}
}
}
 \quad = \qquad
{\renewcommand{\arraystretch}{0.8}
{\arraycolsep=1pt
\begin{array}{*{12}{l}}
  0\\ 
  1\\ 
  2\\ 
  3\\ 
  4& 0\\ 
  0& 1\\ 
  1& 2\\ 
  2& 3\\ 
  3& 4& 0\\ 
  4& 0& 1\\ 
  0& 1& 2\\ 
  1& 2& 3\\ 
  2& 3& 4& 0\\ 
  3& 4& 0& 1\\ 
  4& 0& 1& 2\\ 
  0& 1& 2& 3\\ 
\end{array}
}
}
\quad
\cup \quad
{\renewcommand{\arraystretch}{0.8}
{\arraycolsep=1pt
\begin{array}{*{12}{l}}
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  0& 1& 2\\ 
  1& 2& 3\\ 
  2& 3& 4\\ 
  3& 4& 0& 1& 2\\ 
  4& 0& 1& 2& 3\\ 
  0& 1& 2& 3& 4\\ 
\end{array}
}
}
 \quad
\cup \quad
{\renewcommand{\arraystretch}{0.8}
{\arraycolsep=1pt
\begin{array}{*{12}{l}}
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  \\ 
  2& 3& 4\\ 
  3& 4& 0\\ 
  4& 0& 1& 2& 3& 4\\ 
  0& 1& 2& 3& 4& 0\\ 
\end{array}
}
}
\]
For a  5-core to be bigger than $\h$ with respect to the Bruhat order, 
it is necessary and sufficient to be bigger than each of 
the above three staircases.

\smallskip 
As in the case of a finite symmetric group, one has to reduce the numbers 
of projections $\SS_n \mapsto \SS_n/\S_n$ or
 $\SS_n \mapsto \S_n\backslash \SS_n/\S_n$ to get an efficient coding
\cite{LS}.
We shall not go into these technicalities here. 
Let us just mention that in 
 the case of a finite symmetric group, we have used such a 
\lq\lq decomposition\rq\rq 
of a permutation into rectangular partitions 
to compute Kazhdan-Lusztig polynomials \cite{La}.  

\vfill\eject 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%    Graphes 
%\documentclass{report}

%\usepackage[matrix]{xypic}
%\usepackage{ifthen}

\newcommand{\fl}[1]{%
    \ifthenelse{\equal{#1}{1}}%
       {\ar@{-}[u]\ar@{{}{*}}[dl]\ar@2{-}[dr]}{}% rouge
    \ifthenelse{\equal{#1}{2}}%
       {\ar@2{-}[u]\ar@{-}[dl]\ar@{{}{*}}[dr]}{}% vert
    \ifthenelse{\equal{#1}{3}}%
       {\ar@{{}{*}}[u]\ar@2{-}[dl]\ar@{-}[dr]}{}% bleu
}
\def\ve#1#2#3{  \vbox{
    \vskip 0.15cm
    \hbox to 1.8cm{
      \hss
      ${#1#2#3}$
      \hss
    }
    \vskip 0.15cm
  }
}

\def\b{\bar }


%%%%%%%%%%%%%%%%%%%
%\begin{document}
%\thispagestyle{empty}

$$
\xymatrix@R=0.5cm@C=0.0cm{
    &               && *{\ve123}     &&                 &            \\
    &               && *{\ve024}\fl1 &&                 &            \\
              && *{\ve015}       && *{\ve{\b 1}34}       &&               \\
              && *{\ve{\b 1}16}\fl2   && *{\ve{\b 2}35}\fl3   &&               \\
    & *{\ve{\b 1}07}     && *{\ve{\b 2}26}     && *{\ve{\b 3}45}       &            \\
    & *{\ve{\b 2}08}\fl3 && *{\ve{\b 3}27}\fl1 && *{\ve{\b 4}46}\fl2   &            \\
*{\ve{\b 2}{\b 1}9}\ar@{-}[d] && *{\ve{\b 3}18}\ar@2{-}[d]&&
            *{\ve{\b 4}37}\ar@{{}{*}}[d] && *{\ve{\b 5}56}\ar@{-}[d] \\
*{\ve{\b 3}{\b 1}X}     &&   *{\ve{\b 4}19}     &&   *{\ve{\b 5}38}     
&& *{\ve{\b 6}57}   \\
}
$$
\centerline{\bf Cosets representatives for $n$=3}

$$
\xymatrix@R=0.5cm@C=0.0cm{
    &               && *{\ve000}     &&                 &            \\
    &               && *{\ve001}\fl1 &&                 &            \\
              && *{\ve101}       && *{\ve020}       &&               \\
              && *{\ve120}\fl2   && *{\ve300}\fl3   &&               \\
    & *{\ve022}     && *{\ve310}     && *{\ve004}       &            \\
    & *{\ve302}\fl3 && *{\ve014}\fl1 && *{\ve050}\fl2   &            \\
*{\ve033}\ar@{-}[d] && *{\ve204}\ar@2{-}[d]&&
                            *{\ve051}\ar@{{}{*}}[d] && *{\ve600}\ar@{-}[d] \\
*{\ve034}     &&   *{\ve250}     &&   *{\ve601}     && *{\ve007}   \\
}
$$
\centerline{\bf Codes} 

\vfill\eject


%   hexa_pds    Graphe avec les Poids etendus dans Z^4
\def\ve#1#2#3#4{  \vbox{
    \vskip 0.15cm
    \hbox to 1.8cm{
      \hss
      ${#1#2#3#4}$
      \hss
    }
    \vskip 0.15cm
  }
}


\def\b{\bar }

$$
\xymatrix@R=0.5cm@C=0.0cm{
    &               && *{\ve0000}     &&                 &            \\
    &               && *{\ve10{\b 1}{\b 1}}\fl1 &&                 &            \\
              && *{\ve01{\b 1}{\b 1}}       && *{\ve1{\b 1}0{\b 1}}       &&               \\
              && *{\ve0{\b 1}1{\b 1}}\fl2   && *{\ve{\b 1}10{\b 1}}\fl3   &&               \\
    & *{\ve2 {\b1}{\b1}{\b3}}     && *{\ve{\b1}01{\b1}}     &&
*{\ve11{\b2}{\b3}}       &            \\
    & *{\ve{\b 1}2{\b1}{\b3}}\fl3 && *{\ve20{\b2}{\b4}}\fl1 
&& *{\ve1{\b2}1{\b3}}\fl2   &            \\
*{\ve{\b1}{\b1}2{\b3} }\ar@{-}[d] && *{\ve02{\b2}{\b4}}\ar@2{-}[d]&&
          *{\ve2{\b2}0{\b4}}\ar@{{}{*}}[d] && *{\ve{\b2}11{\b3}}\ar@{-}[d] \\
*{\ve3{\b1}{\b2}{\b7}}     &&   *{\ve0{\b2}2{\b4} }     && 
  *{\ve{\b2}20{\b4} }     && *{\ve21{\b3}{\b7}}   \\
}
$$

\centerline{\bf Extended Weights}

\def\ve#1{  \vbox{
    \vskip 0.15cm
    \hbox to 1.8cm{
      \hss
      ${#1}$
      \hss
    }
    \vskip 0.15cm
  }
}

$$
\xymatrix@R=0.5cm@C=0.0cm{
    &               && *{\ve{0}}     &&                 &            \\
    &               && *{\ve{1}}\fl1 &&                 &            \\
              && *{\ve{2}}       && *{\ve{11}}       &&               \\
              && *{\ve{31}}\fl2   && *{\ve{211}}\fl3   &&               \\
    & *{\ve{42}}     && *{\ve{311}}     && *{\ve{2211}}       &            \\
    & *{\ve{531}}\fl3 && *{\ve{4211}}\fl1 && *{\ve{32211}}\fl2   &            \\
*{\ve{642}}\ar@{-}[d] && *{\ve{5311}}\ar@2{-}[d]&&
                     *{\ve{42211}}\ar@{{}{*}}[d] && *{\ve{332211}}\ar@{-}[d] \\
*{\ve{7531}}   &&   *{\ve{64211}}   &&   *{\ve{532211}}   && *{\ve{4332211}}   \\
}
$$

\centerline{\bf $3$-Cores}
\vfill\eject 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{References}{}
\bibitem{BB} A. Bj\"orner, F. Brenti, {\it Affine permutations of type $A$},
Electronic J. Comb. {\bf 3}\# R18 (1996).
\bibitem{Bo} N. Bourbaki, {\it Groupes et Alg\`ebres de Lie}, Fasc {\it 34},
 Hermann, Paris (1968).
\bibitem{De} V.V. Deodhar, {\it Some characterizations of Bruhat ordering on a
Coxeter group}, Invent. Math. {\bf 39} (1977) 187-198.
\bibitem{Eh}  C. Ehresmann, {\it Sur la topologie de certains espaces
homog\`enes},
Ann. Math. {\bf 35} (1934) 396-443.
\bibitem{Er} H. Eriksson, {\it Computational and combinatorial aspects of
Coxeter groups}, thesis, KTH, Stockholm (1994).
\bibitem{FLOTW} O. Foda, B. Leclerc, M. Okado, J-Y Thibon, T. Welsh,
 {\it Branching functions of $A^{(1)}_{n-1}$ and Jantzen-Seitz
problem for Ariki-Koike algebras},
Adv. in Maths {\bf 141} (1999) 322-365.
\bibitem{JK} James, A. Kerber, {\it The Representation Theory of the Symmetric
Group},
Encyclopedia of Mathematics,
Addisson-Wesley, Reading MA, (1991).
\bibitem{GK} M. Geck, S. Kim, {\it Bases for the Bruhat-Chevalley order on
all finite Coxeter groups}, J. of Algebra {\bf 197} (1997) 278--310.
\bibitem{Ke} A. Kerber, {\it Algebraic Combinatorics via finite group
actions},
Wissenschaftsverlag, Mannheim (1991).
\bibitem{La} A. Lascoux, , {\it Ordonner le groupe sym\'etrique: pourquoi
utiliser l'alg\`ebre de Iwahori-Hecke ?}, Congr\`es International
Berlin 1998, Documenta Mathematica, extra volume ICM 1998, III (1998)
355--364.
\bibitem{LLT} A. Lascoux, B. Leclerc et J.Y. Thibon,
{\it Crystal graphs and $q$-analogues of weight multiplicities for
root systems of type $A_n$},
 Letters in Math. Physics, {\bf  35} (1995) 359--374.
\bibitem{LS} A. Lascoux, M.P. Sch\"utzenberger,
{\it Treillis et bases des groupes de Coxeter}, 
Electronic J. of Comb. {\bf 3} \# R27 (1996).
\bibitem{MM} K.C. Misra, T. Miwa, {\it Crystal base of the basic
representation of
$U_q(\widehat{sl}_n)$},  Commun. Math. Phys., {\bf 134}, 1990, p.79-88.
\bibitem{Sh} Jian-Yi Shi, {\it The Kazhdan-Lusztig cells in certain affine
Weyl Groups}, Springer L.N. {\bf 1179} (1986).
\bibitem{Ve} S. Veigneau, {\it ACE, an algebraic environment for the computer
algebra system MAPLE},
{\tt http://phalanstere.univ-mlv.fr/$\sim$ace} (1998).
\end{thebibliography}
\end{document}