%% 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(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 \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 \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 \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}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} 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 \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 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{]}^{+}_{ \pi (n)-n$;} \end{array} \right. $ \item[ii)] $\varphi _{\pi } (j) > \left\{ \begin{array}{ll} 0 , & \mbox{if $ \pi (1) \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 $kk \} , \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) ] ^{+}_{