%%  This article has been submitted and accepted for publication in
%%  THE FOATA FESTSCHRIFT, 
%%  a special issue of THE ELECTRONIC JOURNAL OF COMBINATORICS
%%  dedicated to DOMINIQUE FOATA at the occasion of his 60th birthday.
%%
%%  Author(s):		ANDERS BJOERNER AND FRANCESCO BRENTI
%%  Title:		AFFINE PERMUTATIONS OF TYPE $A$
%%  Date of submission:	August 17, 1995
%%  TeX version:	LaTeX
%%  File size (approx):	76 kB
%%  Number of pages:	29
%%  Author's email:	bjorner@math.kth.se
%%
%%  Additional files:	Postscript-files "Figure3.ps", Figure4.ps", "Figure5.ps"
%%
%%
\documentstyle[12pt,epsfig]{article}
\renewcommand{\baselinestretch}{1.3}
%\setlength{\topmargin}{0.0in}
%\setlength{\textheight}{23.0cm}
\setlength{\evensidemargin}{0.2in}
\setlength{\oddsidemargin}{0.5in}
%\setlength{\headsep}{0.1cm}
\setlength{\textwidth}{15cm}
\setlength{\parindent}{0.6cm}
\setlength{\unitlength}{1mm}
\newcounter{cms}
\newtheorem{th}{Theorem}[section]
\newtheorem{pro}[th]{Proposition}
\newtheorem{lem}[th]{Lemma}
\newtheorem{con}[th]{Conjecture}
\newtheorem{cor}[th]{Corollary}
\begin{document}
\pagestyle{myheadings} 
\markright{\sc the electronic journal of combinatorics 3 (2) (1996), \#R18\hfill} 
\thispagestyle{empty}
\begin{center}
{\Large \bf Affine Permutations of Type $A$}
 \vspace{0.8cm} \\
Anders Bj\"{o}rner\footnote{Partially supported by
 EC grant No. CHRX-CT93-0400} \\
Department of Mathematics \\
Kungl. Tekniska H\"{o}gskolan\\
 S-100 44  Stockholm, Sweden\vspace{0.5cm}\\
 Francesco Brenti\footnote{Part  of this work was carried
out while the author was a member of the Institute for
Advanced Study in Princeton, New Jersey, U.S.A., and was
partially  supported by
NSF grant DMS 9304580 and
 EC grant
No. CHRX-CT93-0400.} \\
Dipartimento di Matematica \\
Universit\'{a} degli Studi di Perugia \\
I-06123 Perugia, Italy \vspace{0.6cm} \\
{\small Submitted: August 17, 1995; Accepted: September 24, 1995}\\
\vspace{15pt}
{\em D\'{e}di\'{e} \`{a}
 D. Foata \`{a} l'occasion de ses soixante bougies}
\end{center}

\begin{abstract}
We study combinatorial properties, such as inversion table,
weak order and Bruhat order, for certain infinite 
permutations that realize the affine Coxeter group
$\tilde{A}_{n}$.
\end{abstract}
\section{Introduction}
Denote by $\tilde{S}_{n}$ the group (under composition) of all
bijections $\pi : {\bf Z} \rightarrow {\bf Z}$ such that $\pi (x)
+n= \pi (x+n)$, for all $x \in {\bf Z}$, and $\pi (1)+ \pi (2) +
\ldots + \pi (n) = \left( ^{^{n+1}}_{_{ \hspace{0.2cm} 2}} \right)$.
With respect to the adjacent transpositions $(i,i+1)$ (mod $n$),
$i=1,2, \ldots ,n$, this gives a realization of the affine Coxeter 
group $\tilde{A}_{n-1}$. This was pointed out by Lusztig 
\cite{L} and has also appeared in the work of Shi \cite{Sh}
and of H. and K. Eriksson \cite{HE,EE}.

In this paper we study combinatorial properties of such ``affine
permutations''. We define the {\em inversion table} of an affine
permutation and show that this gives a bijection between 
$\tilde{S} _{n}$ and certain integer sequences. A direct 
enumerative consequence is Bott's formula for the length 
generating function of $\tilde{A}_{n-1}$. Specialized to minimal 
coset representatives modulo the symmetric group $S_{n}$
we get a bijection between $\tilde{S}_{n}/ S_{n}$ and the
set of integer partitions with at most $n-1$ parts. 

In the later sections we give combinatorial rules for comparing affine
permutations in {\em weak order} and in {\em Bruhat order}. The 
former is done in terms of  containment of 
certain {\em inversion multigraphs}.
These are directed graphs whose indegree sequence is the inversion
table. For Bruhat order a somewhat more involved criterion is given,
which amounts to the containment of certain associated skew 
shapes and
which specializes to the well known ``tableau criterion'' for ordinary
permutations. 

Affine permutations of other types, giving combinatorial models for
some of the other affine Coxeter groups, have been studied by H. and K. 
Eriksson \cite{HE, EE}. 

\section{Notation and Preliminaries}
In this section we collect  some definitions,
notation and results that will be used in the rest of this work.
We let {\bf P} $\stackrel{\rm def}{=} \{ 1,2,3, \ldots \} $ ,
{\bf N}$ \stackrel{\rm def}{=} ${\bf P} $ \cup \{ 0 \} $, 
$\bf  Z$ be the ring of integers, and $\bf Q$ be the field of rational numbers.
For $a \in ${\bf N} we  let $[a] \stackrel{\rm def}{=}
\{ 1,2, \ldots , a \} $ (where $[0] \stackrel{\rm def}{=}
\emptyset $), and 
given $n, m \in {\bf Z}$, $n \leq m$, we let $[n,m]
\stackrel{\rm def}{=} \{ n,n+1, \ldots , m-1, m \}$. 
Given a set $A$ we denote its cardinality by $|A|$ and its
power set by ${\cal P}(A)$.  For $a \in {\bf Q}$ we let $\lfloor 
a \rfloor $ (respectively,
$\lceil a \rceil $) denote the largest integer $\leq a$ 
(respectively, smallest integer  $\geq a$), and $|a|$ be the
absolute value of $a$ (this should cause no confusion with
the notation $|A|$ used when $A$ is a set).


Given a set $T$ we  let $S(T)$ be the set of all bijections
$\pi : T \rightarrow T$, and $S_{n} \stackrel{\rm def}{=}S([n])$.
If $\sigma \in S_{n}$ 
then we write $\sigma = \sigma
_{1} \ldots \sigma _{n}$ to mean that $\sigma (i) =\sigma _{i}$,
for $i=1, \ldots ,n$.  Given
$\sigma , \tau \in S_{n}$ we let $\sigma  \tau \stackrel{\rm def}{=}
\sigma \circ \tau $ (composition of functions) so that, for example,
$(1,2)(2,3)=(1,2,3)$.

We will follow \cite{S}, Chap. 3, for notation and 
terminology concerning partially ordered sets. 

We will follow \cite{Hum} for general Coxeter groups notation
and terminology. 
In particular, given
a Coxeter system $(W,S)$ and $\sigma \in W$ we denote by $l
(\sigma )$ the length of $\sigma $ in $W$, with respect to $S$,
and we let
\[  D(\sigma ) \stackrel{\rm def}{=} \{ s \in S : \;
l(\sigma \, s) < l(\sigma ) \} \, . \]
We call $ D(\sigma )$ the {\em descent set} of $\sigma $.
We denote by $e$
the identity of $W$, and we let $T \stackrel{\rm def}{=}
\{ \sigma s \sigma ^{-1} : \sigma \in W, \; s \in S \}$ be the
set of reflections of $W$. 
Given $u \in W$ we let
\[ T_{u} \stackrel{\rm def}{=} \{ t \in T: \; l(ut)<l(u) \} \, . \]
We denote by ``$\leq$'' (respectively ``$\preceq $'') the 
{\em Bruhat order} (respectively (left) {\em weak order})
on $W$.
Recall (see, e.g., \cite{Hum}, \S 5.9) that this means that
$x \leq y$ (respectively, $x \preceq y$) if
and only if there exist $r \in {\bf N}$ and $t_{1},
\ldots , t_{r} \in T$ (respectively,  $\in S$) such
 that $ t_{r} \ldots  t_{1} \, x=y$ and 
$l (t_{i} \ldots t_{1} \, x) > l(t_{i-1} \ldots t_{1}x)$ for $i=1,
\ldots ,r$. For example, the Hasse diagram of the Bruhat order
on $S_{3}$ is shown in Figure 1, while that of its (left) weak
order is shown in Figure 2. The following result is well
known; see \cite{Hum} for part i) and \cite{Bj} or \cite{BW} for
part ii).
\begin{pro}
\label{2.1}
Let $(W,S)$ be a Coxeter system and $u,v \in W$. Then:
\begin{description}
\item[i)] $l(u)=|T_{u}|$;
\item[ii)] $u \preceq v$ if and only if $T_{u} \subseteq T_{v}$.
\end{description}
\end{pro}
\begin{center}
\begin{picture}(40,46)
\put(20,10){\line(1,1){10}}
\put(20,10){\line(-1,1){10}}
\put(10,20){\line(0,1){10}}
\put(10,30){\line(1,1){10}}
\put(20,40){\line(1,-1){10}}
\put(30,30){\line(0,-1){10}}
\put(10,20){\line(2,1){20}}
\put(10,30){\line(2,-1){20}}
\put(20,10){\circle*{2}}
\put(10,20){\circle*{2}}
\put(10,30){\circle*{2}}
\put(20,40){\circle*{2}}
\put(30,30){\circle*{2}}
\put(30,20){\circle*{2}}
\put(20,5){\makebox(0,0){123}}
\put(20,45){\makebox(0,0){321}}
\put(37,20){\makebox(0,0){213}}
\put(37,30){\makebox(0,0){312}}
\put(3,20){\makebox(0,0){132}}
\put(3,30){\makebox(0,0){231}}
\end{picture}
\end{center}
\begin{center}
Figure 1
\end{center}
\begin{center}
\begin{picture}(40,46)
\put(20,10){\line(1,1){10}}
\put(20,10){\line(-1,1){10}}
\put(10,20){\line(0,1){10}}
\put(10,30){\line(1,1){10}}
\put(20,40){\line(1,-1){10}}
\put(30,30){\line(0,-1){10}}
\put(20,10){\circle*{2}}
\put(10,20){\circle*{2}}
\put(10,30){\circle*{2}}
\put(20,40){\circle*{2}}
\put(30,30){\circle*{2}}
\put(30,20){\circle*{2}}
\put(20,5){\makebox(0,0){123}}
\put(20,45){\makebox(0,0){321}}
\put(37,20){\makebox(0,0){213}}
\put(37,30){\makebox(0,0){312}}
\put(3,20){\makebox(0,0){132}}
\put(3,30){\makebox(0,0){231}}
\end{picture}
\end{center}
\begin{center}
Figure 2
\end{center}
Given $J \subseteq S$ we let $W_{J}$ be the subgroup of $W$
generated by $J$ and
\[ W^{J} \stackrel{\rm def}{=} \{ w \in W : \; D(w) \subseteq S
\setminus J \} . \]
We call $W_{J}$ the {\em parabolic subgroup} generated by $J$
and $W^{J}$ the set of {\em minimal left coset representatives} of $W_{J}$.
We will often consider $W_{J}$ and $W^{J}$ as posets with the 
partial ordering induced by Bruhat order. Recall (see, e.g., \cite{Hum}, \S 1.10)
that given $u \in W$ and $J \subseteq S$ there exist unique 
elements $u_{J} \in W_{J}$ and $u^{J} \in W^{J}$ such that
\[ u = u^{J} \, u_{J} \]
and $l(u) = l(u_{J})+l(u^{J})$. The following result on Bruhat order will
be used in section~6.
\begin{th}[Deodhar \cite{D}]
\label{2.2}
Let $u,v \in W$ and ${\cal H} \subseteq {\cal P}(S)$, $\emptyset
\not \in {\cal H}$,
be such that
$ \bigcap _{J \in {\cal H}} J = \emptyset $. Then the following are
equivalent:
\begin{description}
\item[i)] $u \leq v$;
\item[ii)] $u^{J} \leq v^{J}$ for all $J \in {\cal H}$.
\end{description}
\end{th}

\section{Affine permutations}
For $n \in {\bf P}$ we let $\tilde{S}_{n}$ be the group of all bijections $\pi$
of $\bf Z$ in itself such that
\begin{equation}
\label{3.0.1}
 \pi (x+n) = \pi ( x ) +n , 
\end{equation}
for all $ x \in {\bf Z}$, and 
\begin{equation}
\label{3.0.2}
 \sum _{x=1}^{n} \pi (x ) = \left( ^{^{n+1}}_{_{\hspace{0.2cm} 2}}
\right) \, , 
\end{equation}
with composition as group operation. Clearly, such a $\pi $ is
uniquely determined by its values on $[n]$, and we write $\pi =
[a_{1}, \ldots , a_{n}]$ to mean that $ \pi (i) =a_{i}$ for $i=1, 
\ldots , n$, and call this the {\em window} notation of $\pi $.
For example, if $n=5$, $\pi  = [2,1,-2, 0, 14]$, and $\sigma = 
[15,-3,-2,4 ,1]$ then $\pi \sigma =[24, -4, -7, 0, 2 ]$. 
Note that, for all $\sigma \in \tilde{S}_{n}$ and $i,j \in {\bf Z}$,
\begin{equation}
\label{3.0.3}
\sigma (i) \not \equiv  \sigma (j) \; \;  \mbox{(mod $n$)}
\end{equation}
if and only if  $i \not \equiv j$ (mod $n$).

There is an alternative notation for the elements of $\tilde{S}_{n}$
which we will sometimes use. Given $\sigma \in \tilde{S}_{n}$
write 
\[ \sigma (i) = n \, r_{i} + k_{i} \]
where $r_{i} \in {\bf Z}$, and $k_{i} \in [n]$, for $i = 1, \ldots , n$.
Then, by (\ref{3.0.3}), $k_{1}, \ldots , k_{n}$ are a permutation of $[n]$,
and, by (\ref{3.0.2}), $\sum _{i=1}^{n} r_{i} =0$. We will then write 
\[ \sigma =(r_{1}, \ldots , r_{n} | \overline{\sigma }) \]
where $\overline{\sigma}  \in S_{n}$ is such that $\overline{\sigma}
(i)=k_{i}$ for $i=1, \ldots , n$.
For example, if $\sigma = [-4,1,-6,19] \in \tilde{S}_{4}$ then we also 
write $\sigma = (-2,0,-2,4|4,1,2,3)$ (so $\overline{\sigma } =4123$).
Note that if $\sigma =(r_{1}, \ldots , r_{n}| \overline{\sigma })$
and $\tau = (s_{1}, \ldots , s_{n}| \overline{\tau })$ then
\[ \sigma  \, \tau =(s_{1}+ r_{\overline{\tau }(1)}, \ldots , 
s_{n} + r _{\overline{\tau }(n)} | \overline{\sigma } \, \, 
\overline{\tau }) \]
and 
\[ \sigma ^{-1} = (-r _{ (\overline{\sigma })^{-1}(1)}, \ldots , 
-r_{(\overline{\sigma })^{-1}(n)} | (\overline{\sigma })^{-1} ) . \]
The group $\tilde{S}_{n}$ is clearly generated by $S 
\stackrel{\rm def}{=}
 \{ s_{1},s_{2},
\ldots  , s_{n} \} $ where $s_{i} \stackrel{\rm def}{=} [1,2,
\ldots ,i-1, i+1, i, i+2, \ldots , n]$ for $i=1, \ldots , n-1$ and
$s_{n} \stackrel{\rm def}{=} [0, 2,3, \ldots , n-1, n+1]$. 
For $\sigma \in \tilde{S}_{n}$ we let
\[ l_{\tilde{A}}(\sigma ) \stackrel{\rm def}{=} \mbox{min}
\{ r \in {\bf N}: \; \sigma = s_{i_{1}} \ldots s_{i_{r}} \; \;
\mbox{for some} \; \; i_{1}, \ldots , i_{r} \in [n] \} , \]
and
\[ \mbox{inv} _{\tilde{A}}(\sigma ) \stackrel{\rm def}{=}
\sum _{1 \leq i < j \leq n } \left| \left\lfloor \frac{\sigma (j) - 
\sigma (i)}{n} \right\rfloor \right| \, . \]
For example, if $ \sigma = [15, -3,-2,4,1] \in \tilde{S}_{5}$ then 
\begin{eqnarray*}
 \mbox{inv}_{\tilde{A}}(\sigma ) & = &
 \left| \left\lfloor \frac{-18}{5}
\right\rfloor \right| + \left| \left\lfloor \frac{-17}{5} \right\rfloor
\right|
+ \left| \left\lfloor \frac{-11}{5} \right\rfloor \right|
+  
\left| \left\lfloor \frac{-14}{5} \right\rfloor
\right|
+ \left| \left\lfloor \frac{1}{5} \right\rfloor \right| +
\left| \left\lfloor \frac{7}{5} \right\rfloor
\right| \\
& & 
+ \left| \left\lfloor \frac{4}{5} \right\rfloor \right| +
\left| \left\lfloor \frac{6}{5} \right\rfloor
\right|
+ \left| \left\lfloor \frac{3}{5} \right\rfloor \right| +
\left| \left\lfloor \frac{-3}{5} \right\rfloor
\right| = 17 \, .
\end{eqnarray*}
\begin{pro}[Shi \cite{Sh}]
\label{3.1}
Let $n \in {\bf P}$. Then
\begin{equation}
\label{3.1.1}
l_{\tilde{A}}(\sigma ) = \mbox{inv} _{\tilde{A}}(\sigma ) 
\end{equation}
for all $\sigma \in \tilde{S}_{n}$.
\end{pro}
{\bf Proof.} We prove first that
\begin{equation}
\label{3.1.2}
\mbox{inv}_{\tilde{A}} (\sigma ) \leq l _{\tilde{A}}(\sigma )
\end{equation}
for all $\sigma \in \tilde{S} _{n}$. It is easy to see that
\begin{eqnarray}
\mbox{inv}_{\tilde{A}} (\sigma s_{i}) & = & \mbox{inv} _{\tilde{A}}
(\sigma ) + \left| \left\lfloor \frac{\sigma (i) - \sigma (i+1)}{n}
\right\rfloor \right| - \left| \left\lfloor  \frac{\sigma (i+1)
- \sigma (i)}{n} \right\rfloor \right| \nonumber \\
\label{3.1.3}
& = & \mbox{inv}_{\tilde{A}} (\sigma ) - \mbox{sgn}(\sigma (i)
- \sigma (i+1)) , 
\end{eqnarray}
if $ i \in [n-1]$, and that
\begin{eqnarray}
\mbox{inv}_{\tilde{A}}(\sigma \, s_{n}) & = & \mbox{inv}_{\tilde{A}}
(\sigma ) - \sum _{1 \leq j \leq n-1} \left( \left| \left\lfloor
\frac{\sigma (j) - \sigma (1)}{n} \right\rfloor \right| + \left|
\left\lfloor \frac{\sigma (n) - \sigma (j)}{n} \right\rfloor
\right| \right) \nonumber \\
& + & \sum _{2 \leq j \leq n-1} \left( \left| \left\lfloor
\frac{\sigma (j) - \sigma (n)}{n} \right\rfloor  + 1
\right| + \left|
\left\lfloor \frac{\sigma (1) - \sigma (j)}{n} \right\rfloor
+ 1 \right| \right) \nonumber \\
& + & \left| \left\lfloor
\frac{\sigma (1) - \sigma (n)}{n} + 2 \right\rfloor  
\right|  \nonumber \\
\label{3.1.4}
& = & \mbox{inv}_{\tilde{A}} (\sigma ) + \left| \left\lfloor
\frac{\sigma (1) - \sigma (n)}{n}  \right\rfloor  + 2
\right|  - \left| \left\lfloor
\frac{\sigma (n) - \sigma (1)}{n}  \right\rfloor  
\right|  \\
& =  & \mbox{inv} _{\tilde{A}}(\sigma ) + \mbox{sgn}
\left( \frac{\sigma (1) - \sigma (n)}{n} +1 \right) .
\nonumber 
\end{eqnarray}
 Since inv$_{\tilde{A}}(e)=l_{\tilde{A}}(e)=0$, (\ref{3.1.3}) and (\ref{3.1.4}) 
prove (\ref{3.1.2}), as claimed. 

We now prove (\ref{3.1.1}) by induction on inv$_{\tilde{A}}(\sigma )$. If
inv$_{\tilde{A}}(\sigma )=0$ then $\left\lfloor \frac{\sigma
(j)- \sigma (i)}{n} \right\rfloor = 0$ for all $ 1 \leq i <j \leq
n$, and hence $ \sigma (1) < \sigma (2) < \ldots < \sigma (n)$
and $ \sigma (n) - \sigma (1) < n$. This implies that $\sigma (i)
= \sigma (1) +i-1$ for $i=1, \ldots , n$ and therefore, by (\ref{3.0.2}),
that $\sigma = e$, so that (\ref{3.1.1}) holds. So let $t \in {\bf N}$ and
$\sigma \in \tilde{S} _{n}$ be such that inv$_{\tilde{A}}
(\sigma ) =t+1$. Then $\sigma \neq e$ and hence there exists
$s \in S$ such that inv$_{\tilde{A}}(\sigma \, s)=t$ (otherwise
(\ref{3.1.3}) and (\ref{3.1.4}) would imply that $\sigma (1) < \sigma (2) < \ldots
< \sigma (n) < \sigma (1) +n$ and hence that $ \sigma = e$,
as noted above). This, by the induction hypothesis,
implies that $l_{\tilde{A}}(\sigma \, s) =t$ and hence that
$l_{\tilde{A}} (\sigma ) \leq t+1$.
Therefore $l_{\tilde{A}} (\sigma ) \leq $ inv$_{\tilde{A}}
(\sigma )$ and this, by (\ref{3.1.2}), concludes the induction
step and hence the proof. $\Box$

As a consequence  we obtain the following
simple combinatorial description of the ``descent set''
 of an element of $\tilde{S}_{n}$.
\begin{pro}
\label{3.2}
Let $n \in {\bf P}$ and $\sigma \in \tilde{S}_{n}$.
Then
\[ D(\sigma )=
\{ i \in [n]: \; l_{\tilde{A}}(\sigma \, s_{i})<
l_{\tilde{A}}(\sigma ) \} = \{ i \in [n] : \; \sigma (i) > \sigma (i+1)
\} . \]
\end{pro}
{\bf Proof.} By Proposition \ref{3.1} we have that
\[ \{ i \in [n]: \; l_{\tilde{A}}(\sigma \, s_{i})<
l_{\tilde{A}}(\sigma ) \}
= \{ i \in [n] : \; \mbox{inv}_{\tilde{A}} (\sigma
\, s_{i}) < \mbox{inv}_{\tilde{A}} (\sigma ) \} \, , \]
and the result follows from (\ref{3.1.3}) and (\ref{3.1.4}). $\Box$

Given $\pi \in \tilde{S}_{n}$ and $a, b \in {\bf Z}$ we say that $a$
is {\em to the left} of $b$ in $\pi$
if $\pi ^{-1}(a) < \pi ^{-1}(b)$.
The preceding two results enable us to give a simple proof of
the following fundamental fact.
\begin{pro}[Lusztig \cite{L}]
\label{3.3}
$(\tilde{S}_{n},S)$ is a Coxeter system of type $\tilde{A}_{n-1}$. 
\end{pro}
{\bf Proof. } We will show that the pair $(\tilde{S}_{n},S)$ satisfies
the Exchange Condition and this will imply, by  \cite{Hum},
\S 1.9, that $(\tilde{S}_{n},S)$ is a Coxeter system.
The computation of its type is straightforward. So let $i,i_{1},
\ldots , i_{p} \in [n]$ and suppose that 
\begin{equation}
\label{3.3.1}
 l_{\tilde{A}}(s_{i_{1}} \ldots s_{i_{p}}s_{i}) < l_
{\tilde{A}} (s_{i_{1}} \ldots s_{i_{p}}
) \, . 
\end{equation}
We want to show that there exists a $j \in [p]$ such that 
\begin{equation}
\label{3.3.2}
s_{i_{1}} \ldots s_{i_{p}}s_{i} =s_{i_{1}} \ldots \hat{s}_{i_{j}}
\ldots s_{i_{p}} \, , 
\end{equation}
($s_{i_{j}}$ omitted).
Let $w \stackrel{\rm def}{=} s_{i_{1}} \ldots s_{i_{p}}$, $b
\stackrel{\rm def}{=} w(i)$, and $a \stackrel{\rm def}{=}
w(i+1)$.
By Proposition \ref{3.2} we know that (\ref{3.3.1}) 
means that $b>a$. Therefore
$a$ is to the left of $b$ in the 
identity, but is to the right of $b$ in 
$w$. Hence there exists $j \in [p]$ such that $a$
is to the left of $b$ in  $s_{i_{1}}
\ldots s_{i_{j-1}}$ but $a$ is to the right of $b$ in  
 $s_{i_{1}} \ldots  s_{i_{j}}$.
Hence  $s_{i_{1}} \ldots \hat{s}_{i_{j}}
\ldots s_{i_{p}}$ and $s_{i_{1}} \ldots s_{i_{p}}$ are equal
except that $a+kn$ and
$b+kn$ are interchanged (for each $k \in {\bf Z}$)
and this, by the definitions of $w$,
$a$, and $b$, implies (\ref{3.3.2}). $\Box$

There are, of course, other ways to 
prove Proposition \ref{3.3}. For example, if we let
 $G$ be the subgroup of $\tilde{S}
_{n}$ generated by $\{ s_{1}, \ldots , s_{n-1} \}$ and $H$ be the
subgroup generated by $\{ g_{1}, \ldots , g_{n-1} \}$ where
\[ g_{i} \stackrel{\rm def}{=} [1,2, \ldots i-1,n+i, i+1-n,
i+2, \ldots ,n-1,n ] \]
for $i=1, \ldots , n-1$, then it is not hard to verify that
$G \cong S_{n}$, that $H \cong
{\bf Z}^{n-1}$, that $G$ normalizes $H$, that $G \cup H$ 
generates $\tilde{S}_{n}$, and that $G \cap H = \{ e \}$.
This shows that $\tilde{S}_{n}$ is the semidirect product
of $G$ and $H$ with respect to the action of $G$ on $H$
given by conjugation (this is sometimes also called the 
internal semidirect product). 
On the other hand, if we let 
 $(A_{n-1}$,  $\{ \bar{s}_{1}, \ldots , \bar{s}_{n-1} \} )$
be a Coxeter system of type $A_{n-1}$, $\Phi$ be its root system,
$\alpha _{1}, \ldots , \alpha _{n-1}$ its simple roots, and $L$
 the translation group generated by the coroots (in the 
canonical geometric representation of $A_{n-1}$, see 
\cite{Hum}, \S 5.3), 
then it is not difficult to show
 that there are unique group isomorphisms $
\varphi : G \rightarrow A_{n-1} $ and $\theta : H \rightarrow
L$ such that $\varphi (s_{i})= \bar{s}_{i}$ and $\theta (g_{i})
= \alpha _{i}$, for $i=1, \ldots , n-1$, and
 $\theta (s_{i} g_{j} s_{i})= \bar{s}_{i}(\alpha
_{j})$ for all $i,j \in [n-1]$. This shows that the conjugation action
of $G$ on $H$ corresponds, under the isomorphisms $\varphi$
and $\theta $, to the geometric action of $A_{n-1}$ on $L$, and
hence implies,  by Proposition 4.2 of \cite{Hum}, that $\tilde{S}_{n}$
is isomorphic to a Coxeter system of type
$\tilde{A}_{n-1}$ (and that
$s_{1}, \ldots , s_{n}$ are mapped to the Coxeter generators of 
$\tilde{A}_{n-1}$ under this isomorphism). 

We now describe combinatorially the set of reflections of
$(\tilde{S}_{n},S)$.
\begin{pro}
\label{3.4}
The set of reflections of $(\tilde{S}_{n},S)$ is
\[ \{ [ 1,2, \ldots , i-1,kn+j, i+1, \ldots , j-1, -kn+i,
j+1, \ldots , n]: \; 1 \leq i <j \leq n, k \in {\bf Z} \} . \]
\end{pro}
{\bf Proof.} Let $\pi \in \tilde{S}_{n}$, and $i \in [n]$. Then
we have that
\[ \pi s_{i} \pi ^{-1}(j) = \left\{ \begin{array}{lll}
j, & \mbox{if $j \not \equiv \pi (i), \pi (i+1)$} &  \mbox{(mod $n$),} \\
j - \pi (i) +  \pi (i+1),  & \mbox{if $ j \equiv \pi (i)$} & \mbox{(mod
 $n$),} \\
j- \pi (i+1) + \pi (i), & \mbox{if $j \equiv \pi (i+1)$} & 
\mbox{(mod $n$),}
\end{array} \right. \]
for if $j \equiv \pi (i)$ (mod $n$) then $ (\pi s_{i} \pi ^{-1})(j)
= (\pi s_{i} \pi ^{-1})(j - \pi (i) + \pi (i)) = j - \pi (i) + ( \pi s_{i}
\pi ^{-1} )(\pi (i)) = j - \pi (i) + \pi (i+1)$, and similarly if $ j 
\equiv \pi (i+1)$, and the thesis follows. $\Box$

For example, if $\pi = [15,-3,-2, 4,1]$ then $\pi s_{1} \pi ^{-1}
=[1,20,3,4,-13]$, $\pi s_{2} \pi ^{-1} = [1,3,2,4,5]$, $\pi s_{3}
\pi ^{-1} = [1,2,9,-2,5]$, $ \pi s_{4} \pi ^{-1} = [4,2,3,1,5]$ and
$\pi s_{5} \pi ^{-1} =[ 20,2,3,4,$ $-14]$. 

It is easy to  describe combinatorially the maximal parabolic subgroups and their minimal coset representatives in 
 the group $(\tilde{S}
_{n},S)$.
\begin{pro}
\label{3.5}
Let $n \in {\bf P}$, $i \in [n]$, and $J \stackrel{\rm def}{=} S \setminus
\{ s_{i} \}$. 
 Then:
\begin{description}
\item[i)] 
$
(\tilde{S}_{n})_{J} =  \{ \sigma  \in \tilde{S}_{n}: \;
\sigma_{|_{[i+1-n,i]}} \in  S([i+1-n,i]) \} $;
\item[ii)] 
$\tilde{S}_{n}^{J} = \{ \sigma \in \tilde{S}_{n}: \; 
\sigma (1) < \ldots < \sigma (i), \; \sigma (i+1) < \ldots <
\sigma (n+1) \}$. $\Box$
\end{description}
\end{pro}
In other words, the preceding result says that, given $\sigma
\in \tilde{S}_{n}$ and $J = S \setminus
\{ s_{i} \}$ ($i \in [n]$), then $\sigma \in (\tilde{S}_{n})_{J}$
(respectively, $\sigma \in \tilde{S}_{n}^{J}$) if and only if
$\sigma $, when restricted to $[i+1-n,i]$, is a permutation
of $[i+1-n,i]$ (respectively, if and only if $\sigma (i+1-n)<
\sigma (i+2-n)< \ldots < \sigma (i-1) < \sigma (i)$).

In the following we shall pay a lot of attention to the special case
$I= S \setminus \{ s_{n} \}$, and the symbol ``$I$'' will be
reserved for this particular set. Thus $(\tilde{S}_{n})_{I}$
is the subgroup of $\tilde{S}_{n}$ that permutes the set $[n]$,
so $(\tilde{S}_{n})_{I} \cong S_{n}$ gives a naturally embedded
copy of the symmetric group, and $\tilde{S}_{n}^{I}$
consists of those elements $\sigma = [a_{1}, \ldots , a_{n}]$
whose window is increasing: $a_{1} < \ldots < a_{n}$.

Due to the symmetry of $\tilde{A}_{n-1}$'s Coxeter diagram all maximal parabolic
subgroups are isomorphic, and in fact even conjugate. Thus there
is no lack of generality in confining attention to the special maximal parabolic
$(\tilde{S}_{n})_{I} \cong S_{n}$.

\section{Affine Inversion Tables}
It is a  well known fact that a permutation is uniquely
determined by its inversion table (see, e.g., \cite{S}, p. 21). In this section
we show that this result extends naturally to affine permutations.

Given $\sigma \in \tilde{S} _{n}$ and $j \in {\bf Z}$ we let
\begin{equation}
\label{4.0.1}
\mbox{Inv}_{j}(\sigma ) \stackrel{\rm def}{=} | \{ i \in {\bf P}: \;
j<i, \, \sigma (j) > \sigma (i) \} | ,
\end{equation}
and 
\[ \mbox{Inv} (\sigma ) \stackrel{\rm def}{=} (\mbox{Inv}_{1}
(\sigma ), \ldots , \mbox{Inv}_{n}(\sigma )) . \]
We call Inv$(\sigma )$ the {\em affine inversion table} of $\sigma $.
For example, if $\sigma =[5,3,-2] \in \tilde{S} _{3}$ then 
Inv$(\sigma )=(4,2,0)$. Note that (\ref{4.0.1}) implies that 
\[ \mbox{Inv}_{j} (\sigma ) = \mbox{Inv} _{j+n}(\sigma ) \]
for all $j \in {\bf Z}$, and
that if $ \sigma \in S_{n}$ (considered as   a subgroup of 
$\tilde{S} _{n}$ as above) then Inv$(\sigma )$ coincides
with the usual inversion table. 

The following two results give some 
elementary properties of Inv$(\sigma )$.
\begin{pro} 
\label{4.1}
Let $\sigma \in \tilde{S}_{n}$. Then:
\begin{description}
\item[i)] Inv$_{i}(\sigma) = {\displaystyle 
\sum _{j=1}^{i-1}} \left\lfloor \frac{\mbox{max}
(\sigma (i) - \sigma (j),0)}{n} \right\rfloor +
{\displaystyle \sum _{j=i+1}^{n}} \left\lfloor \frac{\mbox{
max}
(\sigma (i) - \sigma (j)+n,0)}{n} \right\rfloor $;
\item[ii)] $l_{\tilde{A}}
(\sigma ) = {\displaystyle \sum _{i=1}^{n} } \mbox{Inv}
_{i}(\sigma )$; 
\item[iii)] $\sigma (i) > \sigma (i+1)$ if and only if Inv$_{i}(\sigma )
> $ Inv$_{i+1}(\sigma )$,
for $i \in [n]$;
\item[iv)] there exists $i \in [n]$ such that Inv$_{i}(\sigma )=0$.
\end{description}
\end{pro}
{\bf Proof.} From (\ref{4.0.1}) we have that
\[ \mbox{Inv}_{i}(\sigma )
 = | \{ j \in [n] : \; j>i, \; \sigma (j) < \sigma (i) \} | 
+ \sum _{j=1}^{n} | \{ a \in {\bf P}: \; \sigma (j+an)< \sigma (i) \} | \]
and i) follows. Now ii) follows directly from i) and Proposition \ref{3.1}.
To prove iii) note that if $\sigma (i) < \sigma (i+1)$ then, by the
definition (\ref{4.0.1}), Inv$_{i}(\sigma ) \leq $ Inv$_{i+1}(\sigma )
$, while if $\sigma (i) > \sigma (i+1)$
then it is clear that Inv$_{i}(\sigma ) \geq $ Inv$_{i+1}(\sigma )
+1$. Finally, choosing $i \in [n]$ 
such that $\sigma (i) = $ min$\{ \sigma (1), \ldots , \sigma (n) \}$ 
proves iv). $\Box$

Given $\sigma \in S_{n}$ and $j \in [n]$ we will find it convenient
to let
\begin{equation}
\label{4.1.2}
\mbox{inv}_{j}(\sigma ) \stackrel{\rm def}{=}
| \{ k \in [n]: \; k<j, \; \sigma (k) > \sigma (j) \} | \, . 
\end{equation}
\begin{lem}
\label{4.2}
Let  $i \in [n]$,
and $ \sigma = (r_{1} , \ldots , r_{n}| \overline{\sigma })
 \in  \tilde{S} _{n}^{I}$. Then:
\begin{description}
\item[i)] Inv$_{i}(\sigma )=0$ if and only if $\sigma (i) < \sigma (1) +n$;
\item[ii)] $ \mbox{Inv}_{i} (\sigma ) = i \, r_{i} + {\displaystyle
\sum _{j=i+1}^{n}} r_{j}
- \mbox{inv}_{i} (\overline{\sigma })$.
\end{description}
In particular, Inv$_{n}(\sigma ) = \sigma (n)-n$.
\end{lem}
{\bf Proof.} We prove i) first.
We may clearly assume that $i \geq 2$. Suppose first 
that Inv$_{i}(\sigma )=0$. Then from i) of Proposition \ref{4.1}
we deduce in 
particular that
\[ \left\lfloor \frac{\mbox{max}(\sigma (i) - \sigma (1),0)}{n}
\right\rfloor =0 \]
and the result follows since $\sigma (1) < \sigma (i)$ by hypothesis.
Conversely, suppose that $\sigma (i)< \sigma (1)+n$. 
Then since $\sigma \in
\tilde{S}_{n}^{J}$ we deduce from Proposition \ref{3.5} that 
\[ \sigma (1) \leq \sigma (j) < \sigma (i) < \sigma (1)+n \]
for all $ j \in [i-1]$, and
$ \sigma (i) < \sigma (j) $
for all $ j \in [i+1,n]$.
Hence we have from i) of Proposition \ref{4.1} that
\[ \mbox{Inv}_{i} (\sigma ) = \sum _{j=1}^{i-1} \left\lfloor
\frac{\mbox{max}(\sigma (i)- \sigma (j),0)}{n} \right\rfloor
+ \sum _{j=i+1}^{n} \left\lfloor
\frac{\mbox{max}(\sigma (i)- \sigma (j)+n,0)}{n} \right\rfloor
=0.  \]
To prove ii) note that from i) of Proposition \ref{4.1} we conclude that
\begin{eqnarray*}
\mbox{Inv} _{i}(\sigma ) & = & \sum _{j=1}^{i-1} \left\lfloor
\frac{\sigma (i)-\sigma (j)}{n} \right\rfloor \\
& = &  \sum _{j=1}^{i-1} \left(
(r_{i}-r_{j}) + \left\lfloor \frac{\overline{\sigma }(i)-
\overline{\sigma }(j)}{n} \right\rfloor \right) \\
& = & (i-1) r_{i} - \sum _{j=1}^{i-1} r_{j} - \mbox{inv}_{i}(\overline{\sigma } )  \\
& = & i \,
r_{i} + \sum _{j=i+1}^{n} r_{j} - \mbox{inv}_{i}(\overline{\sigma }) ,
\end{eqnarray*}
as desired. $\Box$

We now introduce the basic operators that are the ``building blocks''
of our bijection between affine permutations and affine inversion tables.
Let $[a_{1}, \ldots , a_{n}] \in \tilde{S}_{n}^{I}$ and $i \in [2,n]$
be such that 
\[
 \{ r \in [n-1]: \; r+a_{i} \not \in \{ a_{i+1}, \ldots , a_{n} \}
\; (\mbox{mod} \; n), \; r+a_{i} < a_{i+1} \} \neq \emptyset . 
\]
We then define
\begin{equation}
\label{4.2.6}
 E_{i} ([a_{1}, \ldots , a_{n}] ) \stackrel{\rm def}{=} [a_{1}, \ldots , 
a_{j-1}, a_{j}-k, a_{j+1} , \ldots ,a_{i-1}, a_{i}+k,
a_{i+1}, \ldots ,a_{n}] 
\end{equation}
where 
\begin{equation}
\label{4.2.7}
k \stackrel{\rm def}{=} \mbox{min} \{ r \in [n-1] : \;
r+a_{i} \not \in \{ a_{i+1}, \ldots , a_{n} \} (\mbox{mod} \; n) ,
\; r+a_{i} < a_{i+1} \} 
\end{equation}
and $j$ is the unique element of $[i-1]$ such that $a_{j} \equiv a_{i}+k$
(mod $n$).

There is a combinatorially appealing way of describing the operators
$E_{i}$, which we now explain. We may clearly identify every element
$\sigma $ of $\tilde{S}_{n}^{I}$ with a subset $A$ of $\bf Z$, of size $n$,
such that any two elements of $A$ are not congruent modulo $n$ (just
take $A \stackrel{\rm def}{=} \{ \sigma (1), \ldots , \sigma (n) \}$).
Let us call (and think of) the elements of $A$ as ``chips''. Then the subset
of $\bf Z$ corresponding to $E_{i}(\sigma )$ is obtained simply by 
moving the $i$-th (from left to right, i.e. $i$-th smallest) element of $A$
as few steps as possible to the right so that it occupies a position that is 
not congruent to any of the elements of $A$ that are to its right, and then
moving the only chip to its left that occupies a position congruent to 
the one where the $i$-th chip has 
been moved to, a corresponding number of steps
to the left. 
Figure 3 illustrates this process for $n=4$, $\sigma = [-3,2,3,8]$ and
$i=3$. \vspace{0.5cm} \\
\psfig{figure=Figure3.ps}

\begin{center}
Figure 3
\end{center}


The next result gives the fundamental property of the operators $E_{i}$.
\begin{pro}
\label{4.3}
Let  $\sigma =[a_{1},
\ldots , a_{n}] \in  \tilde{S}_{n}^{I}$ and $i \in [n]$ be such that 
Inv$_{j}(\sigma )=0$ for all $j \in [i-1]$ and  either Inv$_{i}(\sigma ) <$ Inv$_{i+1}
(\sigma )$ or $i=n$.
Then:
\begin{description}
\item[i)] $\{ r \in [n-1]: \; r+a_{i}<a_{i+1}, \; r+a_{i} \not \in \{ a_{i+1},
\ldots , a_{n} \}$ (mod $n$)  $\} \neq \emptyset$, if $i<n$;
\item[ii)] $E_{i}(\sigma ) \in \tilde{S}_{n}^{I}$;
\item[iii)] 
\[
\mbox{Inv}_{t}(E_{i}(\sigma )) = \left\{ \begin{array}{ll} 
 \mbox{Inv}_{t}(\sigma ), & \mbox{if $t \in [n] \setminus \{ i \}$,} \\
\mbox{Inv}_{t} (\sigma )+1, & \mbox{if $t=i$.}
\end{array} \right. \]
\end{description}
\end{pro}
{\bf Proof.} Let 
\[ h \stackrel{\rm def}{=} \mbox{min} \{ g \in {\bf Z}: \;
a_{i}< g < a_{i+1} \; \mbox{and} \; \sigma ^{-1}(g)>0 \} \]
($h$ certainly exists since Inv$_{i}(\sigma ) <$ Inv$_{i+1}(\sigma )$).
 Since $a_{1}< \ldots < a_{n}$
this implies that $\sigma ^{-1}(h)>n$ and that $ h \equiv
 a_{j}$ (mod $n$) for some $j \leq
i$. Choosing $r \stackrel{\rm def}{=} h -a_{i}$ then proves i). Now let $k \in {\bf P}$
and $j \in [n]$ be defined as in (\ref{4.2.6}) and (\ref{4.2.7}) ($k$ exists by i)).  Then $a_{i}+k
\equiv a_{j}$ (mod $n$), and $a_{i}+r \in \{ a_{i+1}, \ldots , a_{n} \}$
(mod $n$) for all $ r \in [k-1]$. Hence $a_{j} - r \in \{ a_{i} , \ldots , a_{n}
\}$ (mod $n$) for all $r \in [k]$ and therefore  $a_{j-1} \not \in [a_{j}-k,
a_{j}-1]$, which proves ii). To prove iii) let
$r_{0} \in {\bf N}$ be such that 
\begin{equation}
\label{4.3.2}
a_{i}+k = a_{j}+r_{0}n . 
\end{equation}
Since $a_{j-1} <a_{j}-k$ (by ii))
we conclude from i) of Proposition \ref{4.1} that,
if $t \geq i+1$, then 
\begin{eqnarray}
\mbox{Inv}_{t}(E_{i}(\sigma )) - \mbox{Inv}_{t}(\sigma ) & = & 
\left\lfloor \frac{a_{t}-(a_{i}+k)}{n} \right\rfloor +
\left\lfloor \frac{a_{t}-(a_{j}-k)}{n} \right\rfloor -
\left\lfloor \frac{a_{t}-a_{i}}{n} \right\rfloor -
\left\lfloor \frac{a_{t}-a_{j}}{n} \right\rfloor  \nonumber \\
& = & \left\lfloor \frac{a_{t}-a_{j}-r_{0}n}{n} \right\rfloor +
\left\lfloor \frac{a_{t}-a_{i}+r_{0}n}{n} \right\rfloor  -
\left\lfloor \frac{a_{t}-a_{0}}{n} \right\rfloor -
\left\lfloor \frac{a_{t}-a_{j}}{n} \right\rfloor  \nonumber \\
%\label{}
& = & 0.
\end{eqnarray}
Now let $t \in [i-1]$. Then Inv$_{t}(\sigma )=0$ and this by Lemma \ref{4.2}
 implies that
$\sigma (t) < \sigma (1)+n $.
Now if $j \neq 1$ then
$ E_{i}(\sigma )(t) \leq \sigma (t) < \sigma (1) +n = E_{i}(\sigma ) (1)+n$,
and hence Inv$_{t}(E_{i}(\sigma ))=0$ by Lemma \ref{4.2}. 
If $j=1$ then we claim that
$ \sigma (t) < \sigma (1) -k+n $.
In fact, if $\sigma (t) = \sigma (1) +n-r$ for some $r \in [k]$ then $a_{t}
\equiv
 a_{1} -r \equiv a_{i} +k-r$ (mod $n$) 
by (\ref{4.3.2}) and this, by the definition (\ref{4.2.7}) of $k$,
implies that $a_{t} \in \{ a_{i}, a_{i+1}, \ldots ,a _{n} \} $ (mod $n$), which
is a contradiction. Hence 
$ E_{i} (\sigma )(t) = \sigma (t) < \sigma (1) -k+n = E_{i}(\sigma )(1)+n $
and this again implies that Inv$_{t}(E_{i}(\sigma ))=0$ by Lemma \ref{4.2}.
Also, if $m \in [i-1] \setminus  \{ j \} $ and $ d \in {\bf Z}$ is such that
\[ a_{i} < a_{m} + d \, n \]
then
\[ a_{i} < a_{m} +d \, n -k \]
(for if $r \in [k]$ is such that $a_{i} =a_{m} +dn-r$ then $a_{m} \equiv a_{i}+r$ (mod $n$)
and this, by the definition (\ref{4.2.7}) of $k$, implies that $a_{m} \in \{ a_{j} \}
\cup  \{ a_{i+1}
, \ldots , a_{n} \}$ (mod $n$), which is a contradiction). Therefore
\begin{equation}
\label{4.3.6}
\left\lfloor \frac{a_{i}-a_{m}+k}{n} \right\rfloor =
\left\lfloor \frac{a_{i}-a_{m}}{n} \right\rfloor 
\end{equation}
for $m \in [i-1] \setminus \{ j \}$. Finally, note that
\begin{equation}
\label{4.3.7}
\left\lfloor \frac{(a_{i}+k)-(a_{j}-k)}{n} \right\rfloor =
\left\lfloor \frac{r_{0}n+k}{n} \right\rfloor = r_{0} =
\left\lfloor \frac{r_{0}n-k}{n} \right\rfloor +1 =
\left\lfloor \frac{a_{i}-a_{j}}{n} \right\rfloor +1 \, . 
\end{equation}
Hence,
\begin{eqnarray*}
\mbox{Inv}_{i}(E_{i}(\sigma )) & = &  \sum _{m=1}^{i-1} 
\left\lfloor \frac{\mbox{max}(E_{i}(\sigma )(i)-E_{i}(\sigma )(m),0)}{n} \right\rfloor \\
& = &  
\left\lfloor \frac{\sigma (i)+k-(\sigma (j)-k)}{n} \right\rfloor +
\sum _{m \in [i-1] \setminus \{ j \} } 
\left\lfloor \frac{\sigma (i) +k-\sigma (m)}{n} \right\rfloor  \\
& = & 
\left\lfloor \frac{\sigma (i) - \sigma (j)}{n} \right\rfloor +1 
+ \sum _{ m \in [i-1] \setminus \{ j \} } 
\left\lfloor \frac{\sigma (i)-\sigma (m)}{n} \right\rfloor 
 \\
 & = & \mbox{Inv}_{i}(\sigma ) +1 
\end{eqnarray*}
by (\ref{4.3.6}), (\ref{4.3.7}), and i) of Proposition \ref{4.1}. $\Box$

We are now ready to prove  the first main result of this section.
\begin{th}
\label{4.4}
We have that
\[ \mbox{Inv} : \; \tilde{S}_{n}^{I} \rightarrow {\cal P} _{n-1} \]
is a bijection, where ${\cal P}_{n-1}$ is the set of all partitions of length
$\leq n-1$.
\end{th}
{\bf Proof.} Note first that if $\sigma \in \tilde{S} _{n}^{I}$ then, by 
Proposition \ref{3.5}, $\sigma (1) < \ldots < \sigma (n)$ and hence , by
iii) and iv) of Proposition \ref{4.1}, $0 =\mbox{Inv}_{1}(\sigma )
 \leq \mbox{Inv}_{2}(\sigma ) \leq \ldots \leq \mbox{Inv}_{n}(\sigma )
$, so 
that Inv$(\sigma ) \in {\cal P}_{n-1}$. 

Now let
$0 = \lambda _{1} \leq \lambda _{2} \leq \ldots \leq \lambda _{n}
$ be an element of ${\cal P}_{n-1}$.  We define
\[  {\cal C} (\lambda _{1}, \ldots , \lambda _{n}) \stackrel{\rm def}{=}
E_{2}^{\lambda _{2}} \ldots E_{n-1}^{\lambda _{n-1}} E_{n}^{\lambda _{n}}
([1,2, \ldots , n]) . \]
It is then clear from Proposition \ref{4.3}
 that ${\cal C}$ is well defined and that
\[ \mbox{Inv} ({\cal C}(\lambda _{1}, \ldots , \lambda _{n})) = (\lambda
_{1} , \ldots , \lambda _{n}) \]
for all $(\lambda _{1}, \ldots , \lambda _{n} ) \in {\cal P} _{n-1}$. To
complete the proof we therefore have to show that Inv$: \; \tilde{S}_{n}^{I}
\rightarrow {\cal P}_{n-1}$ is an injective map. 

So let $\sigma , \tau \in \tilde{S}_{n}^{I}$ and suppose that Inv$(\sigma ) =$ Inv$(\tau )$. Let
$\sigma = (r_{1}, \ldots , r_{n}| \overline{\sigma })$ and $\tau = 
(s_{1}, \ldots
,s_{n} | \overline{\tau })$. Then, by ii) of Lemma \ref{4.2}
(with $i=n$), we have that
\[ n \, r_{n} - \mbox{inv}_{n}(\overline{\sigma })=n \, s_{n} - 
\mbox{inv}_{n}(\overline{\tau }) \]
and hence (since inv$_{n}(\overline{\sigma })$, inv$_{n}(
\overline{\tau }) \in
[0,n-1]$) we conclude that $r_{n} =s_{n}$ and inv$_{n}(\overline{\sigma })
=$ inv$_{n}(\overline{\tau})$. Now from ii) of Lemma \ref{4.2}
  (with $i=n-1$) we 
conclude that
\begin{eqnarray*}
(n-1)r_{n-1} - \mbox{inv}_{n-1}(\overline{\sigma }) & = & \mbox{Inv}
_{n-1}(\sigma ) -r_{n} \\
& = & \mbox{Inv}_{n-1} (\tau ) -s_{n} \\
& = & (n-1)s_{n-1} - \mbox{inv}_{n-1} (\overline{\tau }) 
\end{eqnarray*}
and hence (since inv$_{n-1}(\overline{\sigma })$, inv$_{n-1}(\overline{\tau 
}) \in [0,n-2]$) that $r_{n-1}=s_{n-1}$ and  inv$_{n-1}(\overline{\sigma }
)=$ inv$_{n-1}(\overline{\tau})$. Continuing in this way we conclude that
$r_{i}=s_{i}$ and inv$_{i}(\overline{\sigma})=$ inv$_{i}(\overline{\tau})$
for all $i=1, \ldots , n$. Therefore, by the invertibility of the ordinary
inversion table for permutations (\cite{S}, p. 21), 
$\overline{\sigma } = \overline{\tau }$ and hence $\sigma
= \tau $.  $\Box$

We illustrate the preceding theorem with an example. Let $n=4$ and 
$\lambda = (1,2,4) \in {\cal P} _{3}$. Then we have from our definitions 
that
\begin{eqnarray*}
{\cal C}(1,2,4)  & = & E_{2}E_{3}^{2}E_{4}^{4}([1,2,3,4]) \\
& = & E_{2}E_{3}^{2} E_{4}^{3}([0,2,3,5]) \\
& = &  E_{2}E_{3}^{2}E^{2}_{4} ([0,1,3,6]) \\
& = & E_{2} E_{3}^{2} E_{4} ([0,1,2,7]) \\
& = & E_{2}E_{3}^{2} ([-1,1,2,8]) \\
& = & E_{2} E_{3} ([-2,1,3,8]) \\
& = & E_{2} ([-2,-1,5,8]) \\
& = & [-5,2,5,8] .
\end{eqnarray*}
Indeed, Inv$([-5,2,5,8])=(0,1,2,4)$. It is instructive to model  the computation
of ${\cal C} (1,2,4)$ by successively moving chips on $\bf Z$, as
explained above.

To prove our main result we now need one last technical fact.
For $i \in [n-1]$ and $(b_{1}, \ldots , b_{n}) \in {\bf N}^{n} \setminus
{\bf P}^{n}$ let
\[ D_{i} (b_{1}, \ldots , b_{n}) \stackrel{\rm def}{=}
\left\{ \begin{array}{ll}
(b_{1}, \ldots , b_{i-1}, b_{i+1},b_{i}-1, b_{i+2}, \ldots , b_{n}), 
&  \mbox{if $b_{i} > b_{i+1}$,} \\
(b_{1}, \ldots , b_{i-1},b_{i+1}+1,b_{i},b_{i+2}, \ldots , b_{n}), &
\mbox{if $b_{i} \leq b_{i+1}$.}
\end{array} \right. \]
Note that $D_{i} (b_{1}, \ldots , b_{n}) \in {\bf N}^{n} \setminus
{\bf P}^{n}$ and that $D_{i}^{2}=$ Id for every $i \in [n-1]$.
\begin{lem}
\label{4.5}
Let $\sigma \in \tilde{S}_{n}$ and $i \in [n-1]$. Then 
\[ \mbox{Inv}(\sigma s_{i}) = D_{i} (\mbox{Inv}(\sigma )) . \]
\end{lem}
{\bf Proof.} If $\mbox{Inv}_{i}(\sigma )
 \leq \mbox{Inv}_{i+1}(\sigma )
$ then (by iii) of Proposition \ref{4.1}) $\sigma (i) < \sigma
(i+1)$ and hence
\[ \mbox{Inv} _{j} (\sigma \, s_{i}) = \left\{ \begin{array}{ll}
\mbox{Inv}_{i}(\sigma ), & \mbox{if $j =i+1$,} \\
\mbox{Inv}_{i+1}(\sigma ) +1, & \mbox{if $j=i$,} \\
\mbox{Inv}_{j}(\sigma ), & \mbox{if $j \neq i , i+1$.}
\end{array} \right. \]
Similarly, if $\mbox{Inv}_{i}(\sigma )
> \mbox{Inv}_{i+1}(\sigma )
$ then $\sigma (i) > \sigma (i+1)$ and hence
\[ \mbox{Inv} _{j} (\sigma \, s_{i}) = \left\{ \begin{array}{ll}
\mbox{Inv}_{i}(\sigma )-1, & \mbox{if $j =i+1$,} \\
\mbox{Inv}_{i+1}(\sigma ) , & \mbox{if $j=i$,} \\
\mbox{Inv}_{j}(\sigma ), & \mbox{if $j \neq i, i+1$.}
\end{array} \right. \]
The result follows. $\Box$

We can now prove the main result of this section.
\begin{th}
\label{4.6}
The map Inv$: \; \tilde{S}_{n} \rightarrow {\bf N} ^{n} \setminus {\bf P}
^{n}$ is a bijection.
\end{th}
{\bf Proof.} Let $(b_{1}, \ldots , b_{n}) \in {\bf N}^{n} \setminus {\bf P}
^{n}$. It is then easy to see (e.g., by induction  on $\sum _{i=1}^{n}
b_{i}$) that  there exist $i_{1}, \ldots , i_{k} \in [n-1]$ such that
\[ D_{i_{k}} \ldots D_{i_{1}} (b_{1}, \ldots , b_{n}) \]
is nondecreasing. By Theorem \ref{4.4}
there exists $\sigma \in \tilde{S}_{n}^{I}$ 
 such that Inv$(\sigma )=D_{i_{k}} \ldots D_{i_{1}} (b_{1}$, $
\ldots , b_{n})$. Hence, by Lemma \ref{4.5}, 
\[ \mbox{Inv}(\sigma s_{i_{k}} \ldots s_{i_{1}}) = D_{i_{1}} \ldots D_{i_{k}}
D_{i_{k}} \ldots D_{i_{1}} (b_{1}, \ldots , b_{n}) = (b_{1}, \ldots , b_{n}) , \]
and this proves surjectivity.

To prove injectivity let $\sigma , \tau \in \tilde{S}_{n}$ be such that
Inv$(\sigma )= $ Inv$(\tau )=(b_{1}, \ldots , b_{n})$. Then, as noted above,
there exist $i_{1}, \ldots , i_{k} \in [n-1]$ such that
\[ D_{i_{k}} \ldots D_{i_{1}} (b_{1} , \ldots , b_{n}) \]
is nondecreasing.
But by Lemma \ref{4.5} we have that
\[ \mbox{Inv}(\sigma s_{i_{1}} \ldots s_{i_{k}}) =D_{i_{k}} \ldots D_{i_{1}}
(b_{1} , \ldots ,b_{n}) = \mbox{Inv} (\tau s_{i_{1}} \ldots 
s_{i_{k}}) . \]
Since $D_{i_{k}} \ldots D_{i_{1}}(b_{1}, \ldots , b_{n})$ is nondecreasing
we conclude by Proposition \ref{4.1} and Theorem \ref{4.4}
 that $\sigma s_{i_{1}} \ldots s_{i_{k}} = \tau s_{i_{1}}
\ldots s_{i_{k}}$, and the result follows. $\Box$

We illustrate the preceding theorem with an example. Let $n=4$, and
$(1,0,4,1) \in {\bf N}^{4} \setminus {\bf P}^{4}$. Then
\[ D_{1}D_{3} (1,0,4,1) =D_{1} (1,0,1,3)=(0,0,1,3) , \]
and since
\[
{\cal C} (0,0,1,3) = E^{0}_{2}E^{1}_{3}E^{3}_{4}([1,2,3,4])=[-2,1,4,7] , \]
we conclude that
\begin{eqnarray*}
(1,0,4,1) & = & D_{3}D_{1} (0,0,1,3) \\
& = & D_{3}D_{1} (\mbox{Inv}([-2,1,4,7])) \\
& = & \mbox{Inv}([-2,1,4,7]s_{1}s_{3}) \\
& = & \mbox{Inv}([1,-2,7,4]). 
\end{eqnarray*}
As an immediate consequence of Theorem \ref{4.6} we obtain the
following expression for the length-generating function of 
$\tilde{A}_{n-1}$, which is the type $A$ specialization of a formula
 by Bott \cite{Bo}, (see also \cite{Hum}, \S 8.9).
\begin{cor}
\label{4.u}
Let $n \in {\bf P}$. Then 
\[ \sum _{w \in \tilde{S}_{n}} x^{l(w)} = \frac{1+x+x^{2}+ \ldots + x^{n-1}}{(1-x)^{n-1}} = \prod_{i=1}^{n-1} \frac{1+x+ \ldots +x^{i}}{1-x^{i}} \]
\end{cor}
{\bf Proof.} By Theorem \ref{4.6} and ii) of Proposition \ref{4.1}
we have that
\[
\sum _{w \in \tilde{S}_{n}} x^{l(w)}  =  \sum _{\alpha \in {\bf N}^{n}
\setminus {\bf P}^{n}} x^{|\alpha |} = \sum _{\alpha \in {\bf N}^{n}}
x^{|\alpha |} - \sum _{ \alpha \in {\bf P}^{n}} x^{|\alpha |} 
 =  \frac{1}{(1-x)^{n}} - \frac{x^{n}}{(1-x)^{n}} ,
\]
and the first equality follows. The second one is elementary. $\Box$

Another combinatorial proof of Corollary \ref{4.u} appears in \cite{E-R}.

\section{Weak order and the Young lattice}
With an ordinary permutation $\pi \in S_{n}$ is associated its
{\em inversion graph} $G_{\pi }$. This is the graph on vertex set $
[n]$ having edges $(i,j)$ where
$i<j$ and $\pi (i) > \pi (j)$. Such graphs are characterized by the 
property that both $G_{\pi}$ and the complementary graph  $\overline{G
_{\pi }}$ are transitive (when all edges are oriented toward the 
greater of the adjacent nodes).
 Furthermore, $\pi \preceq \sigma $  in left weak order
if and only if $G_{\pi } \subseteq G_{\sigma }$. See \cite{Yo} for these facts. The last one is a special case of ii) of Proposition \ref{2.1}.

In this section we define  a directed {\em inversion multigraph}
$I_{\pi }$ for affine permutations $\pi \in \tilde{S}_{n}$, and we
show
that these graphs determine left weak order by inclusion. The problem of finding a 
graph-theoretic characterization of affine inversion multigraphs is left
open.

For $\pi \in \tilde{S}_{n}$ we let $I_{\pi }$ have $[n]$ as its set of vertices,
and we put an edge of weight (or multiplicity) $\left| \left\lfloor
\frac{\pi (j) - \pi (i)}{n} \right\rfloor \right| $ between $i$ and $j$ directed toward the node with highest $\pi$-value, for all $1 \leq i < j \leq n$.
Edges of multiplicity zero are deleted. For instance, the inversion multigraph
of $[-11,-2,15,11,2]$ is shown in Figure 4.
\begin{center}
\psfig{figure=Figure4.ps}

Figure 4
\end{center}
There is an obvious connection with the inversion tables used in 
Section 4.
\begin{lem}
\label{5.1}
Let $\pi \in \tilde{S}_{n}$. Then Inv$_{i}(\pi )$ is the indegree (number
of in-directed edges, counted with multiplicities) 
of node $i$ in the graph $I_{\pi }$. $\Box$
\end{lem}
Thus, Inv$(\pi )$ is in graph-theoretic terms the indegree sequence of 
$I_{\pi }$. Theorem  \ref{4.6} therefore implies the following.
\begin{cor}
\label{5.2}
An affine permutation $\pi $ is uniquely determined by its
inversion graph
$I_{\pi }$. $\Box$
\end{cor}
Now, define inclusion $I_{\pi } \subseteq I_{\sigma }$ of inversion graphs to  mean that each directed multiedge in $I_{\pi }$ occurs with the same
direction and greater or equal multiplicity in $I_{\sigma }$. 
\begin{th}
\label{5.3}
Let $\pi , \sigma \in \tilde{S}_{n}$. Then $\pi \preceq \sigma $ in left 
weak order if and only if $I_{\pi } \subseteq I_{\sigma }$.
\end{th}
{\bf Proof.} This is merely a combinatorial restatement of part ii) of 
Proposition \ref{2.1}. To see
this we must determine the set $T_{\pi }$ of reflections associated to $\pi $. These are of the following two kinds. For $1 \leq i < j \leq n $ let
$m(i,j) = \left| \left\lfloor \frac{\pi (j) - \pi (i)}{n} \right\rfloor \right|$.
\begin{description}
\item[1.] If $\pi (i) < \pi (j)$ and $m(i,j)>0$ then the reflections $t \in T$
such that $\pi t = [ \ldots , \pi (j) -kn, \ldots , \pi (i) +kn, \ldots ]$,
$ 1 \leq k \leq m(i,j)$, belong to $T_{\pi }$.
\item[2.] If $\pi (i) > \pi (j)$ then the reflections $t \in T$ such that 
$\pi \, t = [ \ldots , \pi (j) +kn, \ldots , \pi (i) -kn, \ldots ]$, $0 \leq k 
\leq m(i,j)-1$, belong to $T_{\pi }$.
\end{description}
We leave to the reader the easy verification (using Proposition 
\ref{3.1}) that these are the only
possible $t \in T$ for which $l(\pi \, t) < l(\pi )$, and that $T_{\pi} 
\subseteq T_{\sigma} $ if and only if $I_{\pi } \subseteq I_{\sigma }$.
$\Box$

It is now an  easy computation to check, for example, that $[-2,-3,11] \not \preceq 
[14,-8,0]$. The two inversion graphs are shown in Figure 5.
\begin{center}
\psfig{figure=Figure5.ps}
Figure 5
\end{center}
On the other hand, by Proposition \ref{6.6} one has that $[-2,-3,11]
\leq [14,-8,0]$ in Bruhat order.

If all ascents $\pi (i) < \pi (j)$, $i<j$, are large enough then the graph $I_{\pi}$ 
is complete, which has the following consequence.
\begin{cor}
\label{5.4}
If $\pi , \sigma \in \tilde{S}_{n} $ and no pair $1 \leq i < j \leq n$ satisfies
$0 < \pi (j) - \pi (i) <n$, then $\pi \preceq \sigma $ in left weak order implies
that $\pi $ and $\sigma $ have the same overall ascent/descent pattern 
(i.e.,  $\pi (j) - \pi (i)$ and $\sigma (j) -\sigma (i)$ have the same sign for 
all $1 \leq i<j \leq n$). $\Box$
\end{cor}

There is a natural partial order on the set ${\cal P} _{n-1}$ of partitions with at most $n-1$
parts, called the {\em Young lattice}, obtained by inclusion of their 
diagrams. This means that
\[ \lambda \leq \mu \Leftrightarrow \lambda _{1} \leq \mu _{1}
, \ldots , \lambda _{n-1} \leq \mu _{n-1} \]
for partitions $\lambda , \mu \in {\cal P} _{n-1}$, $0 \leq \lambda _{1}
\leq \ldots \leq \lambda _{n-1}$, $ 0 \leq \mu _{1} \leq \ldots \leq
\mu _{n-1}$.  Because of the bijection Inv$: \; \tilde{S}_{n}^{I} 
\rightarrow {\cal P} _{n-1}$ (Theorem \ref{4.4}) we can pull the Young 
lattice back to $\tilde{S}_{n}^{I}$ and obtain a third partial order, in 
addition to weak order and Bruhat order. Alternatively, we may, via the 
Inv bijection,  talk about weak order and Bruhat order on the set 
${\cal P}_{n-1}$ of length-restricted partitions. Either way, the three 
partial orders are related as follows, with strict inclusions.
\begin{th}
\label{5.5}
Weak order $\subseteq $ Young lattice $\subseteq $ Bruhat order.
\end{th}
{\bf Proof.} Let $\pi , \sigma \in \tilde{S}_{n}^{I}$. If $\pi \preceq
\sigma $
in weak order then $I_{\pi } \subseteq I_{\sigma }$, so by our 
definitions and
Lemma \ref{5.1}, Inv$(\pi ) \leq $ Inv$(\sigma )$ in Young lattice order.

Now, assume that Inv$(\pi ) < $ Inv$(\sigma )$ is a covering in the Young
lattice. Then the entries of Inv$(\pi )=(b_{1},b_{2}, \ldots , b_{n})$ and of
Inv$(\sigma ) = (c_{1},c_{2}, \ldots , c_{n})$ are identical in all positions 
except one, where $b_{i}+1=c_{i}$. In this
situation $\sigma = \pi \, t$ for some reflection $t$. 
This is most easily seen   using the map Inv$^{-1}= {\cal C}
: \; {\cal P}_{n-1} \rightarrow \tilde{S}_{n}^{I}$ defined in the proof of Theorem
\ref{4.4} and the combinatorial interpretation of ${\cal C}(b_{1},b_{2},
\ldots , b_{n}) = E_{2}^{b_{2}} \ldots E_{n} ^{b_{n}}([1,2, \ldots , n])
$ in terms of moving chips on the integer line $\bf Z$, explained in 
Section 4. In fact, let for brevity $\alpha \stackrel{\rm def}{=}
{\cal C} (0, \ldots , 0,b_{i}, \ldots , b_{n})$, and 
\[ k \stackrel{\rm def}{=} \mbox{min} \{ r \in [n-1]: \;
r+ \alpha (i) \not \in \{ \alpha (i+1), \ldots , \alpha (n) \} 
\; \; \mbox{(mod $n$)}, \; r+ \alpha (i)< \alpha (i+1) \} . \]
Then it's not hard to verify (we leave the details to the reader)
that, for any $a \in [2,i]$ and $b \in [0,c_{a-1}]$, the chip positions
 of 
${\cal C}(0, \ldots , 0,b,b_{a}, \ldots , b_{n})$ and 
${\cal C}(0, \ldots , 0,b,c_{a}, \ldots $, $c_{n})$ are equal except
that the $i$-th (from the left) chip of ${\cal C}(0, \ldots , 0,b,b_{a}, \ldots , b_{n})$ lies $k$ steps to the left of the $i$-th chip of 
${\cal C}(0, \ldots , 0,b,c_{a}, \ldots , c_{n})$, while the $j$-th
chip of ${\cal C}(0, \ldots , 0,b,b_{a}, \ldots , b_{n})$ lies $k$
steps to the right of the $j$-th chip of  ${\cal C}(0, \ldots , 0,b,c_{a}, \ldots $, $c_{n})$ (for some $j \in [i-1]$).

Since $l(\sigma )
= \sum c_{i} = \sum b_{i} +1 = l(\pi ) +1$ and $\sigma = \pi t$ this shows that $\pi < \sigma $ in
Bruhat order. By transitivity this implies that all Young lattice  relations 
are also Bruhat relations. $\Box$

\begin{center}
\begin{picture}(60,70)
\put(20,30){\line(2,1){5}}
\put(28,34){\line(2,1){4}}
\put(35,37.5){\line(2,1){5}}
\put(10,50){\line(2,1){5}}
\put(18,54){\line(2,1){4}}
\put(25,57.5){\line(2,1){5}}
\put(30,50){\line(2,1){5}}
\put(38,54){\line(2,1){4}}
\put(45,57.5){\line(2,1){5}}
\put(30,10){\line(0,1){10}}
\put(30,20){\line(-1,1){10}}
\put(30,20){\line(1,1){10}}
\put(20,30){\line(0,1){10}}
\put(40,30){\line(0,1){10}}
\put(20,40){\line(-1,1){10}}
\put(20,40){\line(1,1){10}}
\put(40,40){\line(-1,1){10}}
\put(40,40){\line(1,1){10}}
\put(10,50){\line(0,1){10}}
\put(30,50){\line(0,1){10}}
\put(50,50){\line(0,1){10}}
\put(10,60){\line(-1,1){5}}
\put(10,60){\line(1,1){5}}
\put(30,60){\line(-1,1){5}}
\put(30,60){\line(1,1){5}}
\put(50,60){\line(-1,1){5}}
\put(50,60){\line(1,1){5}}  
\put(30,10){\circle*{2}}
\put(30,20){\circle*{2}}
\put(20,30){\circle*{2}}
\put(40,30){\circle*{2}}
\put(20,40){\circle*{2}}
\put(40,40){\circle*{2}}
\put(10,50){\circle*{2}}
\put(30,50){\circle*{2}}
\put(50,50){\circle*{2}}
\put(10,60){\circle*{2}}
\put(30,60){\circle*{2}}
\put(50,60){\circle*{2}}
\put(30,5){\makebox(0,0){[1,2,3]}}
\put(37,18){\makebox(0,0){[0,2,4]}}
\put(12,30){\makebox(0,0){[0,1,5]}}
\put(48,30){\makebox(0,0){[-1,3,4]}}
\put(12,38){\makebox(0,0){[-1,1,6]}}
\put(48,38){\makebox(0,0){[-2,3,5]}}
\put(2,50){\makebox(0,0){[-1,0,7]}}
\put(22,50){\makebox(0,0){[-2,2,6]}}
\put(58,50){\makebox(0,0){[-3,4,5]}}
\put(2,58){\makebox(0,0){[-2,0,8]}}
\put(38,58){\makebox(0,0){[-3,2,7]}}
\put(58,58){\makebox(0,0){[-4,4,6]}}
\end{picture}
\end{center}
\begin{center}
Figure 6
\end{center}

Figure 6 illustrates left weak order on $\tilde{S}_{3}^{I}$ with the extra
relations of the Young lattice added as dotted lines. For the corresponding
picture of Bruhat order see Figure 9.  Enumerative properties of the 
weak order on $\tilde{S}_{3}^{I}$ (under the name ``Hex'') have been
investigated by Propp \cite{P}, Section 2, and Fomin \cite{F},
Example 2.7.1. Its dual (in the sense of Fomin) turns out to be Bruhat 
order on $\tilde{S}_{3}^{I}$ (with certain positive integral 
multiplicities). The higher posets $\tilde{S}_{n}^{I} $ ($n > 3$) have
to our knowledge not been investigated from this point of view.

Let ${\cal L} _{n,k}$ be the set of partitions with at most $k$ parts of size 
at most $n-k$. In other words, the partitions that fit into a
$k \times (n-k)$ rectangle. There is a well-known bijection 
\[ S_{n}^{J} \rightarrow {\cal L}_{n,k} , \]
where $S_{n}^{J} = S_{n}/(S_{k} \times S_{n-k})$ is the set of minimal coset representatives
of $S_{n}$ modulo the maximal parabolic subgroup $S_{k} \times S_{n-k}$.
Thus, one can talk about left weak order, Young lattice (containment of 
shapes) and Bruhat order also for $S_{n}^{J}$. The same inclusions hold,
however in this situation they are not strict. In fact, they all coincide,
as was remarked in \cite{Bj}, \S  4.9.

\section{Bruhat order}
The Bruhat ordering of $\tilde{S}_{n}$ will be characterized in terms of a 
certain encoding of group elements $\pi \in \tilde{S}_{n}$ as 
monotone
functions 
$\varphi _{\pi}: \; {\bf Z} \rightarrow {\bf Z}
$. We begin by discussing the basic properties of this
encoding. 

The following notation  will be used in this section, for given $n \in 
{\bf P}$:
\[ \begin{array}{lll}
 {[}a{]}^{+} & =  & \{ a+kn: \; k \in {\bf N} \} \\
 {[}a{]}^{+}_{<j}  & = &  [a]^{+} \cap \{ m \in {\bf Z}: \; m<j \} . 
\end{array} \]
For an arbitrary finite set $S \subseteq {\bf Z}$
and $j \in {\bf Z}$ define
\[  \varphi _{S }(j) = \sum _{a \in S} | [ a ] ^{+} _{<j}| =
\sum _{a \in S} \mbox{max} \left( 0, \left\lceil \frac{j-a}{n}
\right\rceil  \right) . \]
Hence, $\varphi _{S } (j)$ counts
the total number of integers less than $j$ that belong to some
right half congruence class of some element of $S$. 
If $\pi \in \tilde{S}_{n}$ then we will write $\varphi _{\pi } $ to mean
$\varphi _{\{ \pi (1), \ldots , \pi (n) \}}$.
The following property is immediate.
\begin{lem}
\label{6.1}
Let $\pi \in \tilde{S}_{n}$. Then $\varphi _{\pi }$ is a unit increase monotone 
function  on $\bf Z$, by which we mean that $0 \leq \varphi _{\pi }
(j+1) - \varphi _{\pi } (j) \leq 1$ for all $j \in {\bf Z}$. $\Box$
\end{lem}
We will now for a while assume that $\pi 
\in \tilde{S}_{n}^{I}$, i.e., that the window is increasing.
\begin{lem}
\label{6.2}
Let $\pi \in \tilde{S}^{I}_{n}$. Then:
\begin{description}
\item[i)] $\varphi _{\pi} (j) = \left\{  \begin{array}{ll}
0 , & \mbox{if $j \leq \pi (1)$,} \\
j-1, & \mbox{if $j > \pi (n)-n$;}
\end{array} \right. $
\item[ii)] $\varphi _{\pi } (j) > \left\{  \begin{array}{ll}
0 , & \mbox{if $ \pi (1)<j \leq 1$,} \\
j-1, & \mbox{if $1 \leq j \leq \pi (n)-n$.}
\end{array} \right. $
\item[iii)] $\pi $ is uniquely  determined by $\varphi _{\pi }$'s 
restriction  to  any interval $[x ,y]$ such that 
$\varphi _{\pi} (x) =0$ and $\varphi _{\pi} (y) =y-1$.
\end{description}
\end{lem}
{\bf Proof.} We begin by observing that
\[ \varphi _{e} (j) = \left\{  \begin{array}{ll}
0 , & \mbox{if $j \leq1$,} \\
j-1, & \mbox{if $j \geq1$,}
\end{array} \right. \]
for the identity element $e=[1,2, \ldots , n]$. Let $e = \pi _{0}
\lhd \pi _{1} \lhd  \ldots \lhd \pi _{s}
= \pi $ be a maximal chain in Bruhat order of $\tilde{S}_{n}^{I}$. Then,
by Proposition \ref{3.4}, each covering $\pi _{i} \lhd
\pi _{i+1}$ is of the form $\pi _{i} = [ \pi _{i}(1), \ldots , \pi _{i} (a),
\ldots , , \pi _{i}(b),
\ldots , \pi _{i}(n) ] \lhd [ \pi _{i}(1), \ldots , \pi _{i} (a)-s,
\ldots , \pi _{i} (b)+s, \ldots , \pi _{i} (n) ] = \pi _{i+1}$, for some
$1 \leq a < b \leq n $, $s \geq 1$, such that $\pi _{i} (a) -s \equiv
 \pi _{i} (b)$ (mod $n$). Thus, $\varphi _{\pi _{i+1}} \geq \varphi 
_{\pi _{i}}$ and $\varphi _{\pi _{i+1}}(j) =\varphi _{
\pi _{i}}(j)$ for all $ j \leq \pi _{i}(a)-s$ and $j > \pi _{i}(b)+s-n$.
 From this part  i) follows and also part ii) with nonstrict inequalities
``$\geq  0$''.  For the strict inequality  one checks that  $\varphi _{\pi } (\pi (n)-n)= \pi (n)-n$ and uses the
monotone unit increase property (Lemma \ref{6.1}).

Reading the values $\varphi _{\pi}(j)$, for $j=x,x+1, \ldots ,y$, we
record the $j$ where the function increases for the first time for each congruence
class modulo $n$. These positions (minus one) give the successive values
$\pi (1), \pi (2), \ldots , \pi (n)$, hence they determine $\pi $. $\Box$

We now come to the Bruhat order criterion for $\tilde{S}_{n}^{I}$, which
is the basic stepping stone to the general criterion.
\begin{th}
\label{6.3}
Let $\pi , \sigma \in \tilde{S}^{I}_{n}$. Then
the following conditions are equivalent:
\begin{description}
\item[i)] $\pi \leq \sigma $ in Bruhat order;
\item[ii)] $\varphi _{\pi } \leq \varphi _{\sigma }$;
\item[iii)] $\varphi _{\pi} (j) \leq \varphi _{\sigma }(j)$, for all $j$ such that
$\pi (1) < j \leq \pi (n)-n$ and $ j \in \bigcup _{i=1}^{n}
([\pi (i)]^{+} \cup [ \sigma (i) ]^{+})$.
\end{description}
\end{th}
{\bf Proof.} \\
i) $\Rightarrow $ ii). It suffices to check the inequality
for the case when $ \pi \lhd \sigma $ is a covering, and this 
was already done in the proof of Lemma \ref{6.2}. \\
ii) $\Rightarrow$ i). Let $\Phi (\pi , \sigma ) = \sum _{j \in {\bf Z}}
(\varphi _{\sigma}(j )-\varphi _{\pi}(j ))$. This is a finite quantity (by Lemma \ref{6.2}), 
and under hypothesis ii) we have that $\Phi (\pi , \sigma ) \geq 0$. The 
proof will be by induction on $\Phi (\pi , \sigma )$.

If $\Phi (\pi , \sigma )=0$ then $\varphi _{\pi }= \varphi _{\sigma }$
 and hence $\pi = \sigma $ by (iii) of Lemma \ref{6.2}.

Assume that $\Phi (\pi , \sigma ) > 0$. The plan is to find a reflection
$t \in  T$ such that $\pi < \pi \, t \in \tilde{S}_{n}^{I}$, $\varphi _{
\pi \, t} \leq \varphi _{\sigma }$, and $\Phi (\pi \, t,
\sigma ) < \Phi (\pi , \sigma )$.  Then by induction $\pi \, t < \sigma $, 
and we will be done.

Let $ k \geq 1$ be minimal such that $\pi (k) \neq \sigma (k)$. Then
$\sigma (k) < \pi (k)$, since $\varphi _{\pi } \leq \varphi _{
\sigma }$. Notice that $k<n$, since $\pi (n) = \left(
^{^{\scriptstyle n+1}}_{_{\scriptstyle \hspace{0.3cm} 2}} \right) -
\pi (1) - \ldots - \pi (n-1)$. Let
\[ c \stackrel{\rm def}{=} \mbox{max} \{ i \in [\sigma (k)]^{+}:
\; i < \pi (k)  \} . \]
Thus, $\sigma (k) \leq c < \pi (k) \leq c+n
$. Let $D = \{ z \in {\bf Z}| c \leq z <
\pi (k)$ and $z \not \equiv  \pi (i)$ (mod $n$)
for all $ 1 \leq i \leq k-1 \}$.
Note that  $D \neq \emptyset $ since $c \in D$.
Let
\begin{equation}
%\label{}
 u \stackrel{\rm def}{=} \mbox{min} \{ i \in {\bf P}: \;
\pi (p) - i n \in D \; \; \mbox{for some} \; \; p>k \} , 
\end{equation}
and 
\[ q \stackrel{\rm def}{=} \mbox{max}\{ p \in [k+1,n]: \;
\pi (p) - u n \in D \} . \]
Notice that this implies that
\begin{equation}
\label{6.3.4}
c \leq \pi (k+1) - un < \ldots < \pi (q-1) - un < \pi (q) - un < 
\pi (k) \leq c+n . 
\end{equation}
 Finally, let $t$ be the reflection such that 
\[ \pi \, t =[ \pi (1),
\ldots , \pi (q) - u \, n , \ldots , \pi (k) + u \, n ,
\ldots , \pi (n) ] , \]
with changes in the window of $\pi $ occurring only in the positions $k$
and $q$. The window of $\pi \, t$ is increasing (since $\pi (q+1)
-un \not \in D$ and hence $\pi (q+1)-un \geq \pi (k)$)
 and
$l(\pi t) > l(\pi )$ (in fact: $l(\pi \, t) = l(\pi )+1$).
Furthermore one sees that
\begin{equation}
\label{6.3.6}
\varphi _{\pi \, t}(j) = \left\{ \begin{array}{ll}
\varphi _{\pi} (j )+1,  & \mbox{if $j \in G$,} \\
\varphi _{\pi} (j ) , & \mbox{otherwise,}
\end{array} \right.
\end{equation}
where
\[ G \stackrel{\rm def}{=} \bigcup _{j=1}^{u} [\pi (q)-jn+1,
\pi (k)+(u-j) \, n ]. \]
 Hence, $\Phi (\pi  \, t , \sigma ) =  \Phi (\pi , \sigma ) -|G| =
\Phi (\pi , \sigma ) - u (\pi (k) +u \, n  - \pi (q)) < \Phi (\pi , 
\sigma  )$. So, to complete the argument it remains only to show that $
\varphi _{\pi \, t} \leq \varphi _{\sigma }$, which in
view of (\ref{6.3.6}) will follow from 
\begin{equation}
\label{6.3.8}
(\varphi _{\pi } )_{\mid _{G}} < (\varphi _{\sigma })_{\mid _{G}} .
\end{equation}
Fix $v \in [n]$, and let
$c_{v} = c +(u - v)n$ and $a_{v} = \pi (k) +(u - v)
n$. Note that, by (\ref{6.3.4}), 
\[ c_{v} \leq \pi (k+1) -vn < \ldots < \pi (q-1) - vn < \pi (q) -vn
< a_{v} \leq c_{v}+n . \]
 From this we deduce 
 that 
\begin{equation}
\label{6.3.10}
\varphi _{\pi }(c_{v}+1) < \varphi _{\sigma}(c_{v}+1),
\end{equation}
since $\varphi _{\pi }(c_{v}) \leq \varphi _{\sigma }(c_{v})$ and $ 
\varphi _{\sigma}(c_{v}+1)$ counts the new  element $c _{v} \in 
[ \sigma (k) ]^{+}$, which is  not counted by $\varphi _{\pi }(c_{v}+1
 )$. Furthermore, for $j \in [c_{v}+1,a_{v}-1]$, we have that
\begin{equation}
\label{6.3.11}
\varphi _{\sigma }(j+1 ) - \varphi _{\sigma }(j) = 
\left\{ \begin{array}{ll}
1, & \mbox{if $j \in \{ \sigma (1), \ldots , \sigma (k-1) \}$ (mod $n
$),} \\
\geq 0 , & \mbox{otherwise,}
\end{array} \right. 
\end{equation}
whereas
\begin{equation}
\label{6.3.12}
\varphi _{\pi }(j+1) - \varphi _{\pi }(j )
= \left\{ \begin{array}{ll}
1, & \mbox{if $j \in \{ \pi (1), \ldots , \pi (k-1) \}$ (mod $n
$),} \\
0, & \mbox{otherwise,} 
\end{array} \right. 
\end{equation}
with the ``$=0$'' part implied by the minimality of $u$.
But
 $\pi (i) = \sigma (i)$ for all $i \in [k-1]$, so (\ref{6.3.10}),
(\ref{6.3.11}) and (\ref{6.3.12})
imply that
\[ \varphi _{\pi }(j ) < \varphi _{\sigma }(j) , \]
for all $j \in  [c_{v}+1,a_{v}]$,
which contains the inequalities (\ref{6.3.8}). \\
ii) $\Leftrightarrow$ iii). The forward implication is clear. For the 
converse, observe that $\varphi _{\pi}(j) =0 \leq \varphi _{\sigma }
(j)
$ for $ j \leq \pi (1)$, and $\varphi _{\pi }(j) = j-1 \leq \varphi _{ 
\sigma }(j)$ for $ j> \pi (n) -n$ by Lemma \ref{6.2}, and that $\varphi _{\pi }(
j+1)
- \varphi _{\pi }(j) =0 = \varphi _{\sigma }(j+1 ) - \varphi _{\sigma 
}(j )$
unless $ j \in [ \pi (i)]^{+} \cup [\sigma (i)]^{+}$ for some $1 \leq
i \leq n$. $\Box$

The $\pi \leftrightarrow \varphi _{\pi }$ encoding of elements
of $\tilde{S}_{n}^{I}$ can be interpreted as associating a skew 
Ferrers diagram $F(\pi )$ with each $\pi \in \tilde{S}_{n}^{I}$.
Namely, let $F(\pi )$ be the set of boxes between the two graphs
$y = \varphi _{\pi }(\lceil x \rceil )$ and $y = \varphi _{e}(
\lceil x \rceil )$ in the $xy$-plane.
For example, if $\sigma = [ -4,4,6]$ then $y= \varphi _{\sigma }
(\lceil x \rceil )$
has the graph shown in Figure 7, and $F(\sigma )$ is shown in 
Figure 8. 
\begin{center}
\begin{picture}(50,35)(-30,-10)
\put(-30,0){\line(1,0){60}}
\put(0,-10){\line(0,1){35}}
\put(-20,0){\line(0,1){5}}
\put(-20,5){\line(1,0){15}}
\put(-5,5){\line(0,1){5}}
\put(-5,10){\line(1,0){15}}
\put(10,10){\line(0,1){5}}
\put(10,15){\line(1,0){10}}
\put(20,15){\line(0,1){5}}
\put(20,20){\line(1,0){5}}
\multiput(-25,-1)(5,0){10}{\line(0,1){2}}
\multiput(-1,5)(0,5){4}{\line(1,0){2}}
\put(5,2){\line(0,1){1}}
\put(5,4){\line(0,1){1}}
\put(10,5){\line(0,1){1}}
\put(10,7){\line(0,1){1}}
\put(10,9){\line(0,1){1}}
\put(15,10){\line(0,1){1}}
\put(15,12){\line(0,1){1}}
\put(15,14){\line(0,1){1}}
\put(5,5){\line(1,0){1}}
\put(7,5){\line(1,0){1}}
\put(9,5){\line(1,0){1}}
\put(10,10){\line(1,0){1}}
\put(12,10){\line(1,0){1}}
\put(14,10){\line(1,0){1}}
\put(-25,-5){\makebox(0,0){-5}}
\put(-20,-5){\makebox(0,0){-4}}
\put(-15,-5){\makebox(0,0){-3}}
\put(-10,-5){\makebox(0,0){-2}}
\put(-5,-5){\makebox(0,0){-1}}
\put(5,-5){\makebox(0,0){1}}
\put(10,-5){\makebox(0,0){2}}
\put(15,-5){\makebox(0,0){3}}
\put(20,-5){\makebox(0,0){4}}
\end{picture}
\end{center}
\begin{center}
Figure 7
\end{center}
\begin{center}
\begin{picture}(45,25)
\put(5,5){\line(1,0){25}}
\put(5,10){\line(1,0){30}}
\put(20,15){\line(1,0){20}}
\put(35,20){\line(1,0){5}}
\put(5,5){\line(0,1){5}}
\put(20,5){\line(0,1){10}}
\put(30,5){\line(0,1){10}}
\put(25,5){\line(0,1){10}}
\put(15,5){\line(0,1){5}}
\put(10,5){\line(0,1){5}}
\put(35,10){\line(0,1){10}}
\put(40,15){\line(0,1){5}}
\end{picture}
\end{center}
\begin{center}
Figure 8
\end{center}
Theorem \ref{6.3}
can now be interpreted as saying that Bruhat order on $
\tilde{S}_{n}^{I}$ is the same as the order by containment of
associated shapes:
\[ \pi \leq \sigma \Leftrightarrow F(\pi ) \subseteq F(\sigma ) . \]

There are simpler rules for Bruhat order on $\tilde{S}_{n}^{I}$ for
$n \leq 3$. The $n=2$ case is trivial: $\tilde{S}^{I}_{2} $ is a one-way
infinite chain isomorphic to $({\bf N}, \leq )$, and $\pi < \sigma $ in
$\tilde{S}_{2}^{I}$ (and in $\tilde{S}_{2}$) if and only if 
$l(\pi ) < l(\sigma )$. The $n=3$ case takes the following form.
\begin{pro}
\label{6.4}
Let $\pi , \sigma \in \tilde{S}_{3}^{I}$. Then
$\pi \leq \sigma$ if and only if $ \pi (1) \geq \sigma (1)$
and $\pi (3) \leq \sigma (3)$.
\end{pro}
{\bf Proof.}
This is of course a specialization of Theorem \ref{6.3}. 
However, it is not so easy to see that the inequalities here imply those
in part ii) of Theorem \ref{6.3}. A better alternative is to check that if $
\sigma (1) \leq \pi (1)$ and $\pi (3) \leq \sigma (3)$ for $\pi
\neq \sigma $, then some move is possible in the chip game position 
corresponding to
$\pi $ (see section 4) leading to a new position $\pi _{1}$
with $\sigma (1) \leq \pi _{1}(1) \leq \pi (1) $ and $\pi (3) \leq
\pi _{1}(3) \leq \sigma (3)$. Repeating this until equalities
are achieved leads to a Bruhat order chain $\pi \lhd
\pi _{1} \lhd \ldots \lhd \pi _{k} = \sigma$.~$\Box$

This simple rule is illustrated in Figure 9 showing Bruhat order of
$\tilde{S}_{3}^{I}$ up to length~5.
\begin{center}
\begin{picture}(60,70)
\put(30,10){\line(0,1){10}}
\put(30,20){\line(-1,1){10}}
\put(30,20){\line(1,1){10}}
\put(20,30){\line(0,1){10}}
\put(40,30){\line(0,1){10}}
\put(20,40){\line(-1,1){10}}
\put(20,40){\line(1,1){10}}
\put(40,40){\line(-1,1){10}}
\put(40,40){\line(1,1){10}}
\put(10,50){\line(0,1){10}}
\put(30,50){\line(0,1){10}}
\put(50,50){\line(0,1){10}}
\put(10,60){\line(-1,1){5}}
\put(10,60){\line(1,1){5}}
\put(30,60){\line(-1,1){5}}
\put(30,60){\line(1,1){5}}
\put(50,60){\line(-1,1){5}}
\put(50,60){\line(1,1){5}}
\put(30,10){\circle*{2}}
\put(30,20){\circle*{2}}
\put(20,30){\circle*{2}}
\put(40,30){\circle*{2}}
\put(20,40){\circle*{2}}
\put(40,40){\circle*{2}}
\put(10,50){\circle*{2}}
\put(30,50){\circle*{2}}
\put(50,50){\circle*{2}}
\put(10,60){\circle*{2}}
\put(30,60){\circle*{2}}
\put(50,60){\circle*{2}}
\put(20,30){\line(2,1){20}}
\put(40,30){\line(-2,1){20}}
\put(10,50){\line(2,1){20}}
\put(30,50){\line(-2,1){20}}
\put(30,50){\line(2,1){20}}
\put(50,50){\line(-2,1){20}}
\put(30,5){\makebox(0,0){[1,2,3]}}
\put(37,18){\makebox(0,0){[0,2,4]}}
\put(12,30){\makebox(0,0){[0,1,5]}}
\put(48,30){\makebox(0,0){[-1,3,4]}}
\put(12,38){\makebox(0,0){[-1,1,6]}}
\put(48,38){\makebox(0,0){[-2,3,5]}}
\put(2,50){\makebox(0,0){[-1,0,7]}}
\put(22,50){\makebox(0,0){[-2,2,6]}}
\put(58,50){\makebox(0,0){[-3,4,5]}}
\put(2,58){\makebox(0,0){[-2,0,8]}}
\put(38,58){\makebox(0,0){[-3,2,7]}}
\put(58,58){\makebox(0,0){[-4,4,6]}}
\end{picture}
\end{center}
\begin{center}
Figure 9
\end{center}

We are now ready to prove the general result for Bruhat order.
\begin{th}
\label{6.5}
Let $\pi , \sigma \in \tilde{S}_{n}$. Then the following are equivalent:
\begin{description}
\item[i)] $\pi \leq \sigma $ in Bruhat order;
\item[ii)] $\varphi _{\{ \pi (k+1), \ldots , \pi (k+n) \} } \leq
\varphi _{ \{ \sigma (k+1), \ldots , \sigma (k+n) \} }$ for all 
$k \in [0,n-1]$;
\item[iii)] $\varphi _{\{ \pi (k+1), \ldots , \pi (k+n) \} }(j) \leq
\varphi _{ \{ \sigma (k+1), \ldots , \sigma (k+n) \} } (j)$ for all 
$k \in [0,n-1]$ and all $ j \in [\mbox{min}_{1 \leq i \leq n}
\{ \pi (i) \} $, max$_{1 \leq i \leq n} \{ \pi (i) \} ]$.
\end{description}
\end{th}
{\bf Proof.} By Deodhar's criterion (Theorem \ref{2.2}) we have that $\pi
\leq \sigma $ if and only if $\pi ^{(i)} \leq \sigma^{(i)}$ for all 
$1 \leq i \leq n$, where $\pi ^{(i)}$ denotes the minimal coset representative of $\pi $ modulo $(\tilde{S}_{n})
_{S \setminus \{ s_{i} \} }$.
For $i=n$ this gives a reduction to the situation in Theorem
\ref{6.3}. Namely, $\pi ^{(n)}$ is the increasing rearrangement of the 
standard window $[\pi (1), \pi (2), \ldots , \pi (n)]$ and 
similarly for $\sigma ^{(n)}$, so what must be checked (according
to Theorem \ref{6.3}) is condition ii) for $k=0$.

For $i \neq n$ we get a reduction  to a situation equivalent to that in 
Theorem \ref{6.3}. Now $\pi ^{(i)}$ is the increasing rearrangement of the 
window $[ \pi (i+1) , \pi (i+2), \ldots , \pi (i+n)]$,
and Theorem \ref{6.3} leads to  condition ii) for $k=i$. $\Box$

Let us exemplify this rule for $\pi = [ 5,-3,4]$ and $\sigma = [-8
,11,3]$. It must be checked that
\[ \varphi _{\{ 5,-3,4 \} }(j) \leq \varphi _{ \{ -8,11,3 \} }(j)  \]
\[ \varphi _{\{ 8,-3,4 \} }(j) \leq \varphi _{ \{ -5,11,3 \} }(j)  \]
\[ \varphi _{\{ 8,0,4 \} }(j) \leq \varphi _{ \{ -5,14,3 \} }(j)  \]
for all $-3 \leq j \leq 5$. All these inequalities hold, so $\pi \leq
\sigma$. This can also be interpreted as containment for three
pairs of skew shapes, as explained in connection with Figure 8.
Of course, for $n=3$ there is a quicker algorithm. Namely, sort 
the 6 sets into increasing order and check pairwise
``containment'' as in Proposition \ref{6.4}. In this case we get
\[ [-3,4,5] \leq [-8,3,11] \]
\[ [-3,4,8] \leq [-5,3,11] \]
\[ [0,4,8] \leq [-5,3,14] . \]
This procedure can be formalized as follows.
\begin{pro}
\label{6.6}
Let $\pi , \sigma \in \tilde{S}_{3}$. Then $\pi \leq \sigma $ in
Bruhat order if and only if min$\{ \pi (i), \pi (i+1), \pi (i+2) \}
\geq $ min$\{ \sigma (i), \sigma (i+1) , \sigma (i+2) \}$ and 
max$\{ \pi (i) , \pi (i+1), \pi (i+2) \} \leq $ max$\{ \sigma (i),
\sigma (i+1), \sigma (i+2) \}$ for $i=1,2,3$. $\Box$
\end{pro}

Theorem \ref{6.5} gives a numerical algorithm for comparing elements
of $\tilde{S}_{n}$ in Bruhat order. If we disregard the time needed 
to compute the values
\[ \varphi _{\pi }(j) = \sum _{i=1}^{n} | [ \pi (i) ] ^{+}_{<j}| = \sum
_{i=1}^{n} \mbox{max} \left(
0, \left\lceil \frac{j- \pi (i)}{n} \right\rceil
\right) , \]
this algorithm requires
\[ n \, \mbox{max}_{1 \leq i , j \leq n} \{ \pi (i) - \pi (j)   \} \]
comparisons of such values to determine ``$\pi \leq \sigma $?''.
Specialized to elements of the symmetric group $S_{n} \subseteq  
\tilde{S}_{n}$ this gives a $O(n^{2})$ algorithm for deciding 
Bruhat order. This algorithm is in fact equivalent to the 
well-known ``tableau criterion'', due to Ehresmann \cite{Eh},
Lehmann \cite{Le} and (in the abstract form of Theorem \ref{2.2})
Deodhar \cite{D}. The tableau criterion, in the version that arises as a 
special case of Theorem \ref{6.5}, says that $\pi \leq \sigma $ (for two 
ordinary permutations $\pi$ and $\sigma $) if and only if, for all
$k$, the increasing rearrangement of $\pi (k+1) , \ldots , \pi (n)$
is entry by entry greater than or equal to the increasing rearrangement of $\sigma (k+1), \ldots , \sigma (n)$.
Equivalently, for all $k$, the increasing rearrangement of $\pi (1),
\ldots , \pi (k)$ is entry by entry less than
or equal to the increasing rearrangement of $\sigma (1), \ldots , 
\sigma (k)$, which is the usual form of the tableau criterion for
$S_{n}$.

\section{Final Comments}
We have seen that affine permutations have a combinatorial theory
that in many ways is parallel to the classical theory for ordinary
permutations. In fact, the resemblance is likely to go further
than what has been shown here. A few open questions that we find interesting are:
\begin{description}
\item[(7.1)] Can permutation statistics, such as {\em excedance},
 {\em major index}, {\em left-to-right minima},
etc. (see \cite{S}) be defined for affine
permutations so that interesting identities arise, similar to the classical results
of P. A. MacMahon, D. Foata, M. P. Sch\"{u}tzenberger and others
(see, e.g.,  \cite{Fo1}, \cite{Fo2}, \cite{FS},  
 and \cite{S})? In particular,
 is there a natural notion of ``major index'' for affine
permutations which is equidistributed with length on 
$\tilde{S}_{n}$?  Note that the obvious choice of defining
\[  \mbox{maj}(\sigma ) \stackrel{\rm def}{=} \sum _{i \in D(
\sigma )} i \]
for $\sigma \in \tilde{S}_{n}$ does not have this property since, for example, 
$| \{ \sigma \in \tilde{S}_{n}:$ maj$(\sigma ) =1 \} | = + \infty$
and maj$(\sigma ) \leq \left( ^{^{n+1}}_{_{ \hspace{0.2cm}
2}} \right)$ for all $\sigma \in \tilde{S}_{n}$. Also, it would
be interesting to investigate the cycle structure of affine
permutations.
\item[(7.2)] Can  affine inversion multigraphs be combinatorially
characterized? 
Note that if $I_{\pi }$ is the 
directed inversion multigraph of an affine permutation
$\pi \in \tilde{S}_{n}$ then $I_{\pi }$ has no antiparallel
edges and if $I_{\pi }$ has directed edges from $i$ to $j$
and from $j$ to $k$, with $1 \leq i < j < k \leq n$, then
$I_{\pi }$ has a directed edge from $i$ to $k$ and
\[ m(i,j) +m(j,k) \leq m(i,k) \leq m(i,j) +m(j,k)+1 , \]
where $m(a,b)$ denotes the
multiplicity of the directed edge $(a,b)$ for $a,b \in [n]$, $a
< b$.
\item[(7.3)] In \cite{Dyer} Dyer defines and studies the concept of a
``reflection order'' for a Coxeter system.  It would be
interesting to translate Dyer's definition into
the present permutation
 description of $\tilde{A}_{n}$, thus obtaining a 
combinatorial characterization of this concept for $\tilde{A}_{n}$.
Since  reflection orderings play a fundamental role in the computation 
of both the $R$-polynomials and the Kazhdan-Lusztig polynomials
 of a Coxeter system (see \cite{Dyer}, 
Corollary 3.4,
and \cite{BreLMS}, Theorem 4.5), this combinatorial characterization
could then yield simpler rules for the computation of these
polynomials for $\tilde{A}_{n}$.
\end{description}



\begin{thebibliography}{xx}
\bibitem{Bj}
A. Bj\"{o}rner, {\em Orderings of Coxeter groups}, in ``Combinatorics and
Algebra'', (ed. C. Greene), Contemporary Math. Series, Vol. 34, Amer. Math. 
Soc., 1984, pp. 175-195.

\bibitem{BW}
A. Bj\"{o}rner and M. Wachs, {\em Generalized quotients in 
Coxeter groups}, Trans. Amer. Math. Soc. {\bf 308} (1988),
1-37.

\bibitem{Bo}
R. Bott, {\em An application of the Morse theory to the topology
of Lie groups}, Bull. Soc. Math. France {\bf 84} (1956), 251-281.

\bibitem{BreLMS}
F. Brenti, {\em Combinatorial expansions of Kazhdan-Lusztig 
polynomials}, J. London Math. Soc., to appear.

\bibitem{D}
V. V. Deodhar, {\em Some characterizations of Bruhat ordering 
on a Coxeter group and determination of the relative M\"{o}bius
function}, Invent. Math. {\bf 39} (1977), 187-198.

\bibitem{Dyer}
M. Dyer, {\em Hecke algebras and shellings of Bruhat intervals},
Comp. Math. {\bf 89} (1993), 91-115.

\bibitem{E-R}
R. Ehrenborg and M. Readdy,
{\em Juggling and applications to $q$-analogues},  
Discrete Math., special issue on Algebraic Combinatorics, to appear.

\bibitem{Eh}
C. Ehresmann, {\em Sur la topologie de certains espaces
homog\`{e}nes}, Ann. Math. {\bf 35} (1934), 396-443.

\bibitem{HE}
H. Eriksson, {\em Computational and combinatorial aspects
of Coxeter groups}, Ph. D. Thesis, KTH, Stockholm, 1994.

\bibitem{EE}
H. Eriksson and K. Eriksson, {\em Affine Coxeter groups as 
infinite permutations} (extended abstract), in  ``Proceedings
of FPSAC' 95 conference'', Paris, 1995.

\bibitem{Fo1}
D. Foata, {\em On the Netto inversion number of a sequence},
Proc. Amer. Math. Soc. {\bf 19} (1968), 236-240.

\bibitem{Fo2}
D. Foata, {\em Distributions Eul\'{e}riennes et  Mahoniennes
sur le groupe des permutations}, in Higher Combinatorics
(M. Aigner, ed.), Reidel, Dordrecht/Boston, 1977.

\bibitem{FS}
D. Foata and M.-P. Sch\"{u}tzenberger, {\em Th\'{e}orie 
g\'{e}om\'{e}trique des polyn$\hat{o}$mes Eul\'{e}riens}, Lecture
Notes in Math., Vol. 138, Springer, Berlin, 1970.

\bibitem{F}
S. Fomin, {\em Duality of graded graphs}, J. Algebraic
Combinatorics {\bf 3} (1994), 357-404. 

\bibitem{Hum} 
J. E. Humphreys, {\em Reflection Groups and Coxeter Groups},
Cambridge Studies in Advanced Mathematics, No.29,
Cambridge Univ. Press, Cambridge,  1990.

\bibitem{Le}
E. L. Lehmann, {\em Some concepts of dependence}, Ann. 
Math. Statist. {\bf 37} (1966), 1137-1153.

\bibitem{L}
G. Lusztig, {\em Some examples of square integrable
representations of semisimple $p$-adic groups}, Trans.
Amer. Math. Soc. {\bf 277} (1983), 623-653.

\bibitem{P}
J. Propp, {\em Some variants of Ferrers diagrams}, J. Combin. 
Theory, Ser. A {\bf 52} (1989), 98-128.

\bibitem{Sh}
J. Shi, {\em The Kazhdan-Lusztig cells in certain affine
Weyl groups}, Lecture Notes in Math., Vol 1179, Springer,
Berlin, 1986.

\bibitem{S}
 R. P. Stanley,
{\em Enumerative Combinatorics }, Vol.1, Wadsworth and
Brooks/Cole, Monterey, CA, 1986. 

\bibitem{Yo}
T. Yanagimoto and M. Okamoto, {\em Partial orderings of permutations
and monotonicity of a rank correlation statistic}, Ann. Inst. Statist.
Math. {\bf 21} (1969), 489-506.
\vspace{0.6cm}
\end{thebibliography}
\end{document}







.
