%% Affine Weyl groups as infinite permutations, by H. and K. Eriksson %% A 30 pages LaTeX document. \documentclass[12pt]{article} \usepackage{latexsym,epsfig,amssymb} \textheight 215mm \textwidth 152mm \hoffset -8mm \voffset -6mm % theorems and such \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{observation}[theorem]{Observation} \newenvironment{example}{\mbox{\sc Example} }{\qed} \newenvironment{remark}{\mbox{\sc Remark} }{} \newcommand{\qed}{\hfill \mbox{ $\Box$} \medskip\noindent} \newenvironment{proof}{\noindent\mbox{\sc Proof} }{\qed} \newenvironment{definition}{\par\medskip\noindent\mbox{\sc Definition} }{\qed} \newcommand{\mZ}{{\mathbb Z}} \newcommand{\DEF}{\stackrel {\mathrm{def}}{=}} \newcommand{\dotminus}{\stackrel{_\bullet}{\raisebox{0pt}[0.1pt][0pt]{$-$}}} \newcommand{\sgn}{\mathop{\rm sgn}} \newcommand{\INV}{\mathrm{INV}} \newcommand{\inv}{\mathrm{inv}} \newcommand{\wt}{\widetilde} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \newcommand{\cS}{{\cal S}} \newcommand{\cB}{{\cal B}} \newcommand{\cC}{{\cal C}} \newcommand{\cD}{{\cal D}} \begin{document} \title {{ Affine Weyl groups as infinite permutations }} \author{\hspace{12mm} \parbox{7cm}{ {\sc Henrik Eriksson} \\ {\small Nada, KTH \\ S-100 44 Stockholm, Sweden\\ {\tt henrik@nada.kth.se} }} \parbox{7cm}{ {\sc Kimmo Eriksson} \\ {\small Dept. of Mathematics, KTH \\ S-100 44 Stockholm, Sweden\\ {\tt kimmo@math.kth.se} }}} \bigskip \date{\small Submitted: January 4, 1996; Accepted: March 23, 1998.} \maketitle \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 5 (1998), \#R18\hfill} \thispagestyle{empty} \begin{abstract} We present a unified theory for permutation models of all the infinite families of finite and affine Weyl groups, including interpretations of the length function and the weak order. We also give new combinatorial proofs of Bott's formula (in the refined version of Macdonald) for the Poincar\'e series of these affine Weyl groups. \par {\bf 1991 Mathematics Subject Classification.} primary 20B35; secondary 05A15. \end{abstract} \section{Introduction} \label{secA} The aim of this paper is to present a unified theory for permutation representations of the finite Weyl groups $A_{n-1}$, $B_n$, $C_n$, $D_n$, and the affine Weyl groups $\wt A_{n-1}$, $\wt B_n$, $\wt C_n$, $\wt D_n$. Our starting point is the symmetric group $S_n$, the group of permutations of $[1,\dots,n]$. If $S_n$ is presented as the group generated by adjacent transpositions, it is isomorphic to the Weyl group $A_{n-1}$, and we obtain well-known interpretations of several Coxeter group concepts in permutation language: \begin{enumerate} \item The Coxeter generators are the adjacent transpositions. \item Reflections correspond to transpositions. \item Length-decreasing reflections correspond to inversions. \item The length of an element $\pi$ is the number of inversions of $\pi$. \item The weak order relation $\pi \le \sigma$ holds if and only if the inversion set of $\pi$ is included in the inversion set of $\sigma$. \end{enumerate} % %6. The Bruhat order relation $\pi \le \sigma$ holds if and only if %the ``tableau criterion'' is satisfied: every initial segment of the %permutation $\pi$, when sorted, is componentwise less than or equal to %the corresponding sorted initial segment of $\sigma$. \noindent We now introduce a mirror at the origin, reflecting the points $1\ldots n$ onto $-\!1\ldots -\!\!n$, and we consider permutations of $-\!n\ldots n$ that are mirror symmetric in the sense that they commute with the action of the mirror. The group of such permutations is isomorphic to the Weyl group $C_n$. Reflection in the origin is a rigid transformation of $\mathbb Z$ and the same game can be played with any group of such rigid transformations. For instance, the translation $n$ steps to the right generates a transformation group of translations by a multiple of $n$. The $\mathbb Z$-permutations that commute with these rigid transformations are $n$-periodic and the group that they form is isomorphic to $\wt A_{n-1}$. It turns out that for any group of rigid transformations, the group of $\mathbb Z$-permutations that commute with these transformations will the one of the finite or affine $AC$-groups. To obtain the $BD$-groups we add one extra condition of 'local evenness'. What should replace adjacent transpositions in these models? All rigid transformations of $\mathbb Z$ are either translations or reflections, translating or reflecting the fundamental interval $1\ldots n$ to other places. A transposition in the fundamental interval must also affect all these translated and reflected intervals accordingly. The result is what we call a {\em class transposition} where the class of a position in the fundamental interval is its orbit given by the rigid transformations. In the $C_n$-case, each class has two elements, $\{\pm k\}$, while in the $\wt A_{n-1}$-case each class is infinite, $\{k+jn \mid j\in\mathbb Z\}$. With the class concept, we can extend most of the results for the symmetric group to all these $\mathbb Z$-permutation groups. Without going into the precise definitions, our results can be summarized as follows: \begin{enumerate} \item The permutation groups defined by rigid transformations on $\mathbb Z$ (and conditions of local evenness) are isomorphic to the finite and affine $ABCD$-groups. \item The Coxeter generators are the adjacent class transpositions. \item Reflections correspond to class transpositions. \item Length-decreasing reflections correspond to class inversions. \item The length of an element $\pi$ is the number of class inversions of $\pi$. \item The weak order relation $\pi \le \sigma$ holds if and only if the class inversion set of $\pi$ is included in the class inversion set of $\sigma$. %\item The Bruhat order relation $\pi \le \sigma$ holds if and only if a %certain dot count comparison criterion on the permutations $\pi$ and $\sigma$ %is satisfied. This criterion specializes to the tableau %criterion for the symmetric group. \item The permutations are completely determined by their fundamental $n$-tuple $[\pi_1,\dots,\pi_n]$. For each group we determine how the results above can be (less elegantly) expressed in terms of the fundamental $n$-tuple. \end{enumerate} Finally, as an application of our theory, we give new combinatorial proofs of Bott's formulas for the Poincar{\'e} series of the affine groups $\wt A_n$, $\wt B_n$, $\wt C_n$, $\wt D_n$. In a sequel to this paper we shall present Bruhat order criteria for these permutation models. \section{Preliminaries on $\mZ$-permutations} An ordinary permutation, such as $2 3 1$, may be interpreted as a co-ordinate permuting operator on ${\mathbb R}^3$, mapping a vector $[x_1,x_2,x_3]$ to $[x_2,x_3,x_1]$. In analogy with this, a $\mZ$-permutation $\pi$ is going to be an operator on ${\mathbb R}^{\mathbb Z}$, mapping a vector $[\ldots,x_{-1},x_0,x_1,x_2,\ldots]$ to $[\ldots,x_{\pi_{-1}},x_{\pi_0},x_{\pi_1},x_{\pi_2},\ldots]$. In particular, $[\ldots,-1,0,1,2,\ldots]\stackrel{\pi}{\mapsto}[\ldots,\pi_{-1},\pi_0,\pi_1,\pi_2,\ldots]$ and we shall identify the operator $\pi$ with this $\pi$-vector. We define the product $\pi\sigma$ of two $\mZ$-permutations as the composite operator ``first $\pi$, then $\sigma$''. From\\ $[\ldots,-1,0,1,2,\ldots]\stackrel{\pi}{\mapsto} [\ldots,\pi_{-1},\pi_0,\pi_1,\pi_2,\ldots]\stackrel{\sigma}{\mapsto} [\ldots,\pi_{\sigma_{-1}},\pi_{\sigma_0},\pi_{\sigma_1},\pi_{\sigma_2},\ldots]$ we see that $(\pi\sigma)_i=\pi_{\sigma_i}$. Our mental picture of $\mZ$ is going to be the set of integer points on the real axis. We will call these points {\em positions}. A $\mZ$-permutation $\pi$ can be visualized as a distribution of {\em values} at the positions, defined by placing the value $\pi_i$ at position $i$. \begin{center} \addtolength{\unitlength}{1.8pt} \begin{picture}(130,15)(-67,-10) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{1.4}} \put(-30,0){\circle*{1.4}} \put(-20,0){\circle*{1.4}} \put(-10,0){\circle*{1.4}} \put(0,0){\circle*{1.4}} \put(40,0){\circle*{1.4}} \put(30,0){\circle*{1.4}} \put(20,0){\circle*{1.4}} \put(10,0){\circle*{1.4}} \scriptsize \put(-40,-4){\makebox(0,0){$-1$}} \put(-30,-4){\makebox(0,0){$0$}} \put(-20,-4){\makebox(0,0){$1$}} \put(-10,-4){\makebox(0,0){$2$}} \put(0,-4){\makebox(0,0){$3$}} \put(10,-4){\makebox(0,0){$4$}} \put(20,-4){\makebox(0,0){$5$}} \put(30,-4){\makebox(0,0){$6$}} \put(40,-4){\makebox(0,0){$7$}} \boldmath \put(-40,3){\makebox(0,0){$\pi_{-1}$}} \put(-30,3){\makebox(0,0){$\pi_0$} } \put(-20,3){\makebox(0,0){$\pi_1$}} \put(-10,3){\makebox(0,0){$\pi_2$}} \put(0,3){\makebox(0,0){$\pi_3$}} \put(10,3){\makebox(0,0){$\pi_4$}} \put(20,3){\makebox(0,0){$\pi_5$} } \put(30,3){\makebox(0,0){$\pi_6$}} \put(40,3){\makebox(0,0){$\pi_7$}} \end{picture} \end{center}\vspace{-5mm} \noindent But a $\mZ$-permutation can also be envisioned as an {\em action}, moving values from some positions to other positions. An important special case is the action of an adjacent transposition $\sigma=(i \ \ i\!+\!1)$, which is to interchange the values at positions $i$ and $i\!+\!1$. We will use pictures as the one below to portray the action of transpositions, in this case $\sigma=(2\ \ 3)$. \begin{center} \addtolength{\unitlength}{1.8pt} \begin{picture}(130,15)(-67,-10) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{1.4}} \put(-30,0){\circle*{1.4}} \put(-20,0){\circle*{1.4}} \put(-10,0){\circle*{1.4}} \put(0,0){\circle*{1.4}} \put(40,0){\circle*{1.4}} \put(30,0){\circle*{1.4}} \put(20,0){\circle*{1.4}} \put(10,0){\circle*{1.4}} \scriptsize \put(-40,-4){\makebox(0,0){$-1$}} \put(-30,-4){\makebox(0,0){$0$}} \put(-20,-4){\makebox(0,0){$1$}} \put(-10,-4){\makebox(0,0){$2$}} \put(0,-4){\makebox(0,0){$3$}} \put(10,-4){\makebox(0,0){$4$}} \put(20,-4){\makebox(0,0){$5$}} \put(30,-4){\makebox(0,0){$6$}} \put(40,-4){\makebox(0,0){$7$}} \thicklines \put( -5,0){\oval(10,8)[t]} \end{picture} \end{center}\vspace{-5mm} \noindent Combining these models, we can interpret the multiplication rule $(\pi\sigma)_i =\pi_{\sigma_i}$ as the action of $\sigma$ on the $\pi$-vector of values. \subsection{Locally finite $\mZ$-permutations} If we view a permutation as a value-moving action, we can ask how many values that cross a given co-ordinate. For an ordinary permutation, it is clear that as many values pass from left to right as from right to left, and for the application in mind, we will use only $\mZ$-permutations with this property. A $\mZ$-permutation $\pi$ is {\em locally finite} if a finite number of values are moved from the negative half-axis to the nonnegative half-axis and the same number of values are moved in the other direction. Reflection in the origin is not locally finite, for infinitely many values are moved from one side to the other. Translation $n$ steps to the right is not locally finite either, for it moves $n$ values from the left to the right but no values in the other direction. \begin{proposition} For any partition of $\mZ$ into half-axes $(-\infty,m]$ and $[m\!+\!1,\infty)$, a locally finite $\mZ$-permutation $\pi$ will move a finite number of values from the left to the right and the same number of values in the other direction. \end{proposition} \begin{proof} Otherwise, the interval $[0,m]$ would have a net inflow or outflow of values, which is absurd. \end{proof} \begin{proposition} If $\pi$ and $\sigma$ are locally finite $\mZ$-permutations, then so is the inverse $\pi^{-1}$ and the product $\pi\sigma$. Thus, for every group of $\mZ$-permutations, the locally finite $\mZ$-permutations form a subgroup. \end{proposition} \begin{proof} Easy. \end{proof} \subsection{Locally even $\mZ$-permutations} We say that a permutation is {\em locally even at position $m$ } if it moves an even number of values from the left of $m$ to the right of $m$. This sharpening of the local finiteness condition is needed in order for us to obtain representations of the groups of type $D$, $\wt B$ and $\wt D$. \section{The $ABCD$-families of Weyl groups}\label{s:prelim} The classification of finite and affine Weyl groups (due to Coxeter in 1935) features the infinite families defined by the Coxeter graphs in the table below. For precise definitions and for Coxeter group theory in general, we refer to the book \cite{Hu} by Humphreys. \begin{table}[htb]\centering\addtolength{\unitlength}{0.9pt} \begin{tabular}{|lc @{\hspace{30pt}}|lc@{\hspace{30pt}}|} \hline \raisebox{12pt}{$ A_{n-1}$} & \begin{picture}(30,25)(10,-10) \put(10,0){\circle{4}} \put(8,-6){$s_1$} \put(38,-6){$s_{n-1}$} \put(20,-0.3){$\ldots$} \put(40,0){\circle{4}} \put(32,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \end{picture} & \raisebox{12pt}{$\wt A_{n-1}$} & \begin{picture}(30,25)(10,-5) \put(10,0){\circle{4}} \put(25,10){\circle{4}} \put(23,14){$s_n$} \put(20,-0.3){$\ldots$} \put(40,0){\circle{4}} \put(32,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \put(11.5,1){\line(3,2){12}}\put(38.5,1){\line(-3,2){12}} \end{picture} \\ \hline \raisebox{12pt}{$ B_n$} & \begin{picture}(40,25)(0,-10) \put( 0,0){\circle{4}} \put(10,0){\circle{4}} \put(-2,-6){$s_0$} \put(8,-6){$s_1$} \put(20,-0.3){$\ldots$} \put(4,1){$\scriptstyle 4$} \put(40,0){\circle{4}} \put(32,0){\line(1,0){6}} \put(38,-6){$s_{n-1}$} \put( 2,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \end{picture} & \raisebox{12pt}{$\wt B_n$} & \begin{picture}(50,25)(0,-15) \put( 0,0){\circle{4}} \put(10,0){\circle{4}} \put(20,-0.3){$\ldots$} \put(4,1){$\scriptstyle 4$} \put(40,0){\circle{4}} \put(32,0){\line(1,0){6}} \put( 2,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \put(40,-2){\line(0,-1){6}}\put(40,-10){\circle{4}} \put(44,-11){$s_{n}$} \put(50,0){\circle{4}} \put(42,0){\line(1,0){6}} \end{picture} \\ \hline \raisebox{12pt}{$ C_n=B_n$} & \begin{picture}(40,25)(0,-10) \end{picture} & \raisebox{12pt}{$\wt C_n$} & \begin{picture}(50,25)(0,-10) \put( 0,0){\circle{4}} \put(10,0){\circle{4}} \put(20,-0.3){$\ldots$} \put( 4,1){$\scriptstyle 4$} \put(40,0){\circle{4}} \put(44,1){$\scriptstyle 4$} \put(50,0){\circle{4}} \put(42,0){\line(1,0){6}} \put(48,-6){$s_{n}$} \put( 2,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \put(32,0){\line(1,0){6}} \end{picture} \\ \hline \raisebox{12pt}{$ D_n$} & \begin{picture}(40,25)(0,-15) \put( 0,0){\circle{4}} \put(10,0){\circle{4}} \put(-2,4){$s_{1}$} \put(8,4){$s_{2}$} \put(20,-0.3){$\ldots$} \put(10,-10){\circle{4}} \put(14,-11){$s_{0}$} \put(38,4){$s_{n-1}$} \put(40,0){\circle{4}} \put(32,0){\line(1,0){6}} \put( 2,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \put(10,-2){\line(0,-1){6}} \end{picture} & \raisebox{12pt}{$\wt D_n$} & \begin{picture}(50,25)(0,-15) \put( 0,0){\circle{4}} \put(10,0){\circle{4}} \put(20,-0.3){$\ldots$} \put(40,-10){\circle{4}} \put(40,0){\circle{4}} \put(10,-10){\circle{4}} \put(50,0){\circle{4}} \put(42,0){\line(1,0){6}} \put( 2,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \put(32,0){\line(1,0){6}} \put(44,-11){$s_{n}$} \put(10,-2){\line(0,-1){6}} \put(40,-2){\line(0,-1){6}} \end{picture} \\ \hline \end{tabular} \caption{$ABCD$-families of irreducible finite and affine Weyl groups} \label{coxfin} \end{table} Coxeter graphs encode groups as follows. The vertices are the generators of the group. Every generator $s$ satisfies $s^2=1$. All other relations in the group are of the kind $(s_is_j)^{m(i,j)}=1$ for $s_i\neq s_j$. The order $m(i,j)$ is encoded in the graph by the label of the edge between $s_i$ and $s_j$. If there is no edge, then the order is 2. If there is an unlabeled edge, then the order is 3. \subsection{Brief history of permutation representations} There are classical representations of $A_{n-1}$ as the symmetric group $S_n$, and of $C_n$ and $D_n$ as signed permutations and even signed representations respectively. %The meaning of length, weak order and Bruhat order for signed %permutations is less well-known, but it has been around for a while. %See Bj{\"o}rner and Brenti \cite{BB1} for length and weak order, %and Proctor \cite{Pr} for Bruhat order. In the last fifteen years, representations of the affine groups $\wt A_n$, $\wt B_n$, $\wt C_n$ and $\wt D_n$ by infinite periodic permutations have been presented. Lusztig \cite{Lu} and B\'edard \cite{Be} seem to be the first references for the permutation representations of $\wt A_n$ and $\wt C_n$ respectively (although none of them explicitly proves that these representations are faithful). These representations of $\wt A_n$ and $\wt C_n$ are used also by Shi \cite{Sh}. In H.\ Eriksson's doctoral thesis \cite{HE}, permutation representations (with proofs) are given also for $\wt B_n$ and $\wt D_n$, as well as related permutation models for the sporadic $EFGH$-groups and many other nameless groups. Permutation interpretations of length, weak order and Bruhat order on $\wt A_n$ were recently given by Bj{\"o}rner and Brenti \cite{BB2}, using another approach than ours. \subsection{The permutation representations of this paper} The present paper is mainly a thorough expansion and improvement of a few results from the second chapter of \cite{HE}. Instead of the case-by-case approach of \cite{HE}, we here obtain the same permutation models for the $ABCD$-groups with unified proofs. In the same process we obtain general results on how to express the Coxeter generators, the length function, the descent set and the weak order for all these groups. We also prove that a permutation $\pi$ in any of these groups can be represented by its fundamental $n$-tuple $[\pi_1,\dots,\pi_n]$. Finally we investigate for each group how the results translate to this computationally more tractable representation. \section{Rigid groups and compatible groups} Translations and reflections are the only rigid transformations of $\mZ$. We denote by $T_n$ a translation $n$ steps to the right and by $R_m$ a reflection with respect to $m$, which must be an integer or half-integer. A {\em rigid group} is a group of such rigid transformations. The classification of rigid groups on $\mZ$ is prehistoric, so the following proposition comes without credits. \begin{proposition} A nontrivial rigid group on $\mZ$ is of one of three types: generated by one translation $\langle T_n\rangle$, generated by one reflection $\langle R_m\rangle$ or generated by two reflections $\langle R_m,R_{m'}\rangle$. \end{proposition} \begin{proof} Let $n$ be the smallest nonnegative integer such that $T_n$ is in the group and $m$ the smallest nonnegative integer or half-integer such that $R_m$ is in the group. If both $n$ and $m$ are undefined, the group is trivial $\{\mbox{id}\}$. If only $n$ is defined, the group must be $\{T_{kn}\mid k\in\mZ\}$. If only $m$ is defined, the group must be $\{R_m,\mbox{id}\}$, for a product of two reflections is a translation. If both are defined, the group must be $\{T_{kn},R_mT_{kn} \mid k\in\mZ\}$ which is $\langle R_m,R_{m'}\rangle$ for $m'=m+n/2$. \end{proof} For each of these rigid groups, we are interested in the corresponding {\em compatible} $\mZ$-permutations, compatible in the sense that they commute with all transformations in the group. \begin{lemma}\label{lemmarelations} A $\mZ$-permutation $\pi$ commutes with the translation $T_n$ if and only if the periodicity relation $\pi_{i+n}=\pi_i+n$ holds for all positions $i$. It commutes with the reflection $R_m$ if and only if the mirror relation $\pi_{i}=2m-\pi_{2m-i}$ holds for all positions $i$. \end{lemma} \begin{proof} The value on position $\pi_i$ is moved to position $i$ by $\pi$ and further to position $i\!+\!n$ by $T_n$, then on to $\pi_{i+n}$ by $\pi^{-1}$ and finally to $\pi_{i+n}-n$ by $T^{-1}_n$. Commutativity therefore means that $\pi_i=\pi_{i+n}-n$, as stated in the lemma. The mirror relation comes out similarly. \end{proof} If positions $i$ and $j$ belong to the same orbit, that is if some transformation in the rigid group maps $i$ to $j$, then $\pi_i$ determines $\pi_j$ by one of these relations. Belonging to the same orbit is an equivalence relation $i\sim j$, and we shall denote the equivalence class of the position $i$ by $\la i \ra$. The $\pi$-value on any position in the class thus determines the values on all positions in the class. It is easy to see what the orbits are for the three kinds of nontrivial rigid groups. \begin{proposition} For the three kinds of nontrivial rigid groups, the relation $i\sim j$ has the following significance: \begin{description} \item[$\langle T_n\rangle$:] $i=j+kn$ for some $k\in\mZ$, \item[$\langle R_m\rangle$:] $i=j$ or $i+j=2m$, \item[$\langle R_m,R_{m'}\rangle$:] $i=j+kn$ or $i+j=2m+kn$ for some $k\in\mZ$. ($n$ is defined by $m'=m+n/2$.) \end{description} \end{proposition} \noindent The same classes are useful for values. In fact, $\pi_i\sim\pi_j$ if and only if $i\sim j$. This is exactly what commutativity with the rigid transformations implies, so the following proposition holds true. \begin{proposition} Let $\la i \ra$ be a position class of a rigid group. Then, for any compatible $\mZ$-permutation $\pi$, the value class $\la\pi_i\ra$ consists of the $\pi$-values on the positions in $\la i \ra$. \end{proposition} \subsection{Mirrors of types $C$ and $D$} If we have the mirror relation $\pi_{i}=2m-\pi_{2m-i}$ for all positions $i$, we say that $m$ is a {\em mirror} position. The mirror relation implies that $m$ is a fixpoint under $\pi$. Recall the definition of locally even: $\pi$ is locally even at position $m$ if it is an even number of values that is moved from the left of $m$ to the right of $m$. We will apply this condition only at mirror positions. We say that a mirror $m$ is of {\em type D} if we study only permutations that are locally even at $m$. Otherwise $m$ is a mirror of {\em type C}. \subsection{Class transpositions and adjacent class transpositions} We can extend the relation $\sim$ of belonging to the same orbit to a relation on pairs of positions. Let $\la (i_1,i_2) \ra$ denote the equivalence class of a pair $(i_1,i_2)$ under $\sim$, that is, the orbit of $(i_1,i_2)$ under the rigid group. Say that a pair $(i_1,i_2)$ of different positions is {\em transposable} (under the rigid group) if there exists at least one compatible $\mZ$-permutation $\pi$ such that $\pi_{i_1}=i_2$ and $\pi_{i_2}=i_1$. Evidently, a pair $(i_1,i_2)$ cannot be transposable if either $i_1$ or $i_2$ is a mirror, since mirrors are always fixpoints of compatible permutations. It is also clear that $(i_1,i_2)$ cannot be transposable if the rigid group has $n$-periodicity and $i_2=i_1+kn$ for some integer $k$, since by periodicity we will have $\pi_{i_2}=\pi_{i_1}+kn$. In fact, these two simple conditions are both necessary and sufficient. \begin{proposition} For the three kinds of nontrivial rigid groups, transposability works as follows: \begin{description} \item[$\langle T_n\rangle$:] $(i_1,i_2)$ is transposable iff $i_2-i_1$ is not a multiple of $n$. \item[$\langle R_m\rangle$:] $(i_1,i_2)$ is transposable iff neither position equals $m$. \item[$\langle R_m,R_{m'}\rangle$:] $(i_1,i_2)$ is transposable iff neither position equals $m+kn/2$ and $i_2-i_1$ is not a multiple of $n$. ($n$ is defined by $m'=m+n/2$.) \end{description} \end{proposition} In order to prove this result, one can construct a compatible permutation where $(i_1,i_2)$ is transposed if it satisfies all the conditions as follows. Define the {\em class transposition} $\la (i_1\ \ i_2)\ra$ as the permutation in which every pair in $\la (i_1,i_2) \ra$ is transposed: $$\la (i_1 \ \ i_2)\ra = \prod_{(j_1,j_2)\in \la (i_1,i_2) \ra} (j_1 \ \ j_2).$$ It is easy to check that this permutation is well-defined and compatible with the rigid group, and we leave it to the reader. {\bf Remark. } If the midpoint $m=(i_1+i_2)/2$ is a mirror of type $D$, then the class transposition $\la (i_1 \ \ i_2)\ra$, though compatible with the rigid group, does not belong to the subgroup of permutations that are locally even at $m$, since an odd number of values are moved from left to right of $m$. \subsection{Adjacent class transpositions}\label{sc:adjacent} In the symmetric group, the adjacent transpositions are the Coxeter generators. We shall now define the analog of adjacent transpositions in our permutation groups. Fix a rigid group and let $G$ be the group of compatible permutations, or possibly the subgroup of locally even permutations if mirrors are of type D. We say that $\la (i\ \ j)\ra$ is an {\em adjacent class transposition} in $G$ if either $j$ is the smallest number greater than $i$, or $i$ is the largest number less than $j$, such that $\la (i\ \ j)\ra$ is a class transposition in $G$. The definition of adjacent class transpositions allows us to list all cases that can occur. For each case we give an illustration of the action of the class transposition in a small segment. \begin{itemize} \item If $i$ and $i+1$ are non-mirrors, then $\la(i \ \ i\!+\!1)\ra$ is adjacent. \begin{center} \addtolength{\unitlength}{0.8pt} \begin{picture}(130,40)(-67,-20) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{2.0}} \put(-30,0){\circle*{2.0}} \put(-20,0){\circle*{2.0}} \put(-10,0){\circle*{2.0}} \put(40,0){\circle*{2.0}} \put(30,0){\circle*{2.0}} \put(20,0){\circle*{2.0}} \put(10,0){\circle*{2.0}} \scriptsize \put(30,-7){\makebox(0,0){$i$}} \put(40,-7){\makebox(0,0){$i\!+\!\!1$}} \thicklines \put( 35,0){\oval(10,8)[t]} \put(-35,0){\oval(10,8)[t]} \put( 0,15){\line(0,-1){30}} \end{picture} \end{center} \item If $m$ is a mirror of type $C$, then $\la(m\!-\!1 \ \ m\!+\!1)\ra$ is adjacent. \begin{center} \addtolength{\unitlength}{0.8pt} \begin{picture}(130,40)(-67,-20) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{2.0}} \put(-30,0){\circle*{2.0}} \put(-20,0){\circle*{2.0}} \put(-10,0){\circle*{2.0}} \put(40,0){\circle*{2.0}} \put(30,0){\circle*{2.0}} \put(20,0){\circle*{2.0}} \put(10,0){\circle*{2.0}} \put(-2,16){$C$} \scriptsize \put(-10,-7){\makebox(0,0){$m\!-\!1$}} \put(10,-7){\makebox(0,0){$m\!+\!\!1$}} \thicklines \put( 0,0){\oval(20,18)[t]} \put( 0,15){\line(0,-1){30}} \end{picture} \end{center} \item If $m$ is a mirror of type $D$, then $\la(m\!-\!1 \ \ m\!+\!2)\ra$ is adjacent. \begin{center} \addtolength{\unitlength}{0.8pt} \begin{picture}(130,40)(-67,-20) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{2.0}} \put(-30,0){\circle*{2.0}} \put(-20,0){\circle*{2.0}} \put(-10,0){\circle*{2.0}} \put(40,0){\circle*{2.0}} \put(30,0){\circle*{2.0}} \put(20,0){\circle*{2.0}} \put(10,0){\circle*{2.0}} \put(-2,16){$D$} \scriptsize \put(-10,-7){\makebox(0,0){$m\!-\!1$}} \put(20,-7){\makebox(0,0){$m\!+\!\!2$}} \thicklines \put( 5,0){\oval(30,28)[t]} \put( -5,0){\oval(30,28)[t]} \put( 0,15){\line(0,-1){30}} \end{picture} \end{center} \end{itemize} \begin{lemma}\label{lm:all} The three types of class transpositions above are the only adjacent class transpositions. \end{lemma} \begin{proof} Inspection. \end{proof} \section{Representations of the $ABCD$-groups} \label{sc:list} For each of the rigid groups, the compatible $\mZ$-permutations form a group. These groups are closely connected to the $ABCD$-families of finite and affine Weyl groups. If the rigid group is the trivial group, $\la T_n\ra$, $\la R_m \ra$ or $\la R_m,R_{m'} \ra$, the compatible permutation groups will be isomorphic to Weyl groups of type $A$, $\wt A$, $C$ and $\wt C$ respectively. If conditions of local evenness is added, we obtain the remaining groups, of type $D$, $\wt B$ and $\wt D$. Postponing the proof of the faithfulness of the representations below, we shall define for each of the $ABCD$-groups a representation by $\mZ$-permutations. We like to call this family of groups {\em George groups} in honor of George Lusztig who invented the permutation representation $\wt \cS_n$ for $\wt A_{n-1}$. A common characteristic of George groups will be that the action takes place in positions belonging to $\la 1\ra,\la 2\ra,\ldots,\la n\ra$. Positions outside these $n$ classes are fixed points for all $\mZ$-permutations involved. Another common feature will be that the action of $s_1$ transposes positions 1 and 2, the action of $s_2$ transposes positions 2 and 3 etc up to $s_{n-1}$. \subsection{The compatible groups: $\cS_n$, $\wt \cS_n$, $\cC_n$ and $\wt \cC_n$} We start by listing the compatible groups to the four possible rigid groups (including the trivial rigid group). \subsubsection{Rigid group: trivial. The compatible group $\cS_n$ represents $A_{n-1}$, $n\ge 2$.} The standard representation of $A_{n-1}$ by permutations of $1,2,\ldots,n$ can be viewed as the group of $\mZ$-permutations that leave everything outside the fundamental interval fixed. In this case, the rigid group is trivial, so every position has a class of its own. \begin{figure}[h] \addtolength{\unitlength}{0.4pt} \begin{center} \begin{picture}(130,20)(-0,0) \put(80,0){\circle{4}} \put(82,0){\line(1,0){16}} \put(78,-6){$s_1$} \put(100,0){\circle{4}} \put(102,0){\line(1,0){16}} \put(98,-6){$s_2$} \put(120,0){\circle{4}} \put(122,0){\line(1,0){16}} \put(118,-6){$s_3$} \put(140,0){\circle{4}} \put(138,-6){$s_4$} \put(-50,0){\vector(1,0){110}} \put(-40,0){\circle*{2.3}} \put(-42,3){1} \put(-20,0){\circle*{2.3}} \put(-22,3){2} \put( 0,0){\circle*{2.3}} \put( -2,3){3} \put(40,0){\circle*{2.3}} \put( 18,3){4} \put(20,0){\circle*{2.3}} \put( 38,3){5} \put(-25,-13){$s_1$} \thicklines \put(-30,0){\oval(20,18)[b]} \end{picture} \end{center} \caption{The action of $s_1$ in $\cS_5$ as a simple transposition} \end{figure} \subsubsection{Rigid group: $\la T_n \ra$. The compatible group $\wt \cS_n$ represents $\wt A_{n-1}$, $n\ge 2$.} Define $\wt \cS_n$ as the group of all locally finite $\mZ$-permutations compatible with the translation group $\la T_n\ra$. \begin{proposition} A $\mZ$-permutation $\pi$ compatible with $\la T_n\ra$ is locally finite iff the following sum condition holds: $$ \sum_1^n \pi_i = \sum_1^n i. $$ \end{proposition} \begin{proof} Permutation of the values in the interval leaves the sum invariant. Whenever a value $v$ is moved leftwards out of the interval, the value $v+n$ enters from right and so the sum increases by $n$. And when a value $v$ enters the interval from the left, the value $v+n$ leaves the interval to the right, decreasing the sum by $n$. Local finiteness signifies that these two effects cancel. \end{proof} The group $\wt \cS_n$ is generated by the adjacent class transpositions $s_i=\la (i\ \ i+1)\ra$, for $i=1,\dots,n$. \begin{figure}[h] \begin{center} \addtolength{\unitlength}{0.4pt} \begin{picture}(300,20)(-151,-5) \put(-150,0){\vector(1,0){300}} \scriptsize \put( 139,3){\makebox(0,0){ 14}} \put( 129,3){\makebox(0,0){ 13}} \put( 119,3){\makebox(0,0){ 12}} \put( 109,3){\makebox(0,0){ 11}} \put( 99,3){\makebox(0,0){ 10}} \put( 89,3){\makebox(0,0){ 9}} \put( 79,3){\makebox(0,0){ 8}} \put( 69,3){\makebox(0,0){ 7}} \put( 59,3){\makebox(0,0){ 6}} \put( 49,3){\makebox(0,0){ 5}} \put( 39,3){\makebox(0,0){ 4}} \put( 29,3){\makebox(0,0){ 3}} \put( 19,3){\makebox(0,0){ 2}} \put( 9,3){\makebox(0,0){ 1}} \put(-1,3){\makebox(0,0){ 0}} \put(-140,3){\makebox(0,0){-14}} \put(-130,3){\makebox(0,0){-13}} \put(-120,3){\makebox(0,0){-12}} \put(-110,3){\makebox(0,0){-11}} \put(-100,3){\makebox(0,0){-10}} \put(-90,3){\makebox(0,0){-9}} \put(-80,3){\makebox(0,0){-8}} \put(-70,3){\makebox(0,0){-7}} \put(-60,3){\makebox(0,0){-6}} \put(-50,3){\makebox(0,0){-5}} \put(-40,3){\makebox(0,0){-4}} \put(-30,3){\makebox(0,0){-3}} \put(-20,3){\makebox(0,0){-2}} \put(-10,3){\makebox(0,0){-1}} \thicklines \put( 15,0){\oval(10,8)[b]} \put( 65,0){\oval(10,8)[b]} \put(115,0){\oval(10,8)[b]} \put(-85,0){\oval(10,8)[b]} \put(-35,0){\oval(10,8)[b]} \put(-135,0){\oval(10,8)[b]} \end{picture} \end{center} \caption{The action of $s_1\in\wt{\cS}_4$ as a periodic transposition.} \end{figure} \noindent \subsubsection{Rigid group: $\la R_0 \ra$. The compatible group $\cC_n$ represents $C_{n}$, $n\ge 2$.} Define $\cC_n$ as the group of permutations of $[-n,\dots,n]$ compatible with the rigid group $\la R_0 \ra$, so that $\pi_{-i}=-\pi_{i}$ for all $i$. $\cC_n$ is generated by $s_0=\la (-1 \ \ 1)\ra = (-1 \ \ 1)$ and, for $i=1,\dots,n-1$, $s_i=\la (i\ \ i+1)\ra = (i \ \ i+1)(-i \ \ -i-1)$. \begin{figure}[tbh] \addtolength{\unitlength}{0.4pt} \begin{center} \begin{picture}(130,40)(-67,-20) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{2.3}} \put(-30,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(40,0){\circle*{2.3}} \put(30,0){\circle*{2.3}} \put(20,0){\circle*{2.3}} \put(10,0){\circle*{2.3}} \put(33,6){$s_3$} \put(-37,6){$s_3$} \put(2,-12.5){$s_0$} \thicklines \put( 35,0){\oval(10,8)[t]} \put(-35,0){\oval(10,8)[t]} \put( 0,0){\oval(20,18)[b]} \put( 0,15){\line(0,-1){30}} \put(-2,16){$C$} \end{picture} \addtolength{\unitlength}{0.6pt} \begin{picture}(40,15)(0,-15) \put( 0,0){\circle{4}} \put(10,0){\circle{4}} \put(20,0){\circle{4}} \put(4,1){$\scriptstyle 4$} \put(30,0){\circle{4}} \put(22,0){\line(1,0){6}} \put( 2,0){\line(1,0){6}} \put(12,0){\line(1,0){6}} \put(-3,-5){$s_0$} \put(7,-5){$s_1$} \put(17,-5){$s_2$} \put(27,-5){$s_3$} \end{picture} \end{center} \caption{The actions of $s_3$ and $s_0$ in $\cC_4$}\label{C4} \end{figure} As a concrete example of computing in this model, consider the element $s_3s_0$. In $\cC_4$, this permutes the interval $[-4,\dots,4]$ as follows: \begin{eqnarray*} [-4,-3,-2,-1,0,1,2,3,4] & {\stackrel {s_3}{\longrightarrow}} & [-\!3,-\!4,-\!2,-\!1,0,1,2,4,3] \\ & {\stackrel {s_0}{\longrightarrow}} & [-\!3,-\!4,-\!2,1,0,-\!1,2,4,3]. \end{eqnarray*} \subsubsection{Rigid group: $\la R_0, R_{n+1} \ra$. The compatible group $\wt \cC_n$ represents $\wt C_{n}$, $n\ge 2$.} Define $\wt \cC_n$ as the group of permutations of $\mZ$ compatible with $\la R_0, R_{n+1} \ra$, so that $\pi_{i}=-\pi_{-i}$ and $\pi_{i}=2n+2-\pi_{2n+2-i}$ for all $i$. There are $n$ infinite classes: $\la i \ra = \{\pm i+k(2n+2) : k\in \mZ\}$ for $i=1,\dots,n$. $\wt \cC_n$ is generated by the class transpositions $s_0=\la (-1 \ \ 1)\ra$ and $s_n=\la (n \ \ n+2)\ra$ and, for $i=1,\dots,n-1$, $s_i=\la (i\ \ i+1)\ra$. \begin{figure}[htb] \addtolength{\unitlength}{0.5pt} \begin{picture}(280,40)(-145,-20) \put(-80,0){\vector(1,0){220}} \put( 130,0){\circle*{2}} \put( 120,0){\circle*{2}} \put( 110,0){\circle*{2}} \put( 100,0){\circle*{2}} \put( 90,0){\circle*{2}} \put( 80,0){\circle*{2}} \put( 70,0){\circle*{2}} \put( 60,0){\circle*{2}} \put( 50,0){\circle*{2}} \put( 40,0){\circle*{2}} \put( 30,0){\circle*{2}} \put( 20,0){\circle*{2}} \put( 10,0){\circle*{2}} \put( 0,0){\circle*{2}} \put( -70,0){\circle*{2}} \put( -60,0){\circle*{2}} \put( -50,0){\circle*{2}} \put( -40,0){\circle*{2}} \put( -30,0){\circle*{2}} \put( -20,0){\circle*{2}} \put( -10,0){\circle*{2}} \thicklines \put( 15,0){\oval(10,8)[t]} \put(-15,0){\oval(10,8)[t]} \put( 85,0){\oval(10,8)[t]} \put(115,0){\oval(10,8)[t]} \put( 0,0){\oval(20,15)[b]} \put( 50,0){\oval(20,15)[b]} \put(-50,0){\oval(20,15)[b]} \put(100,0){\oval(20,15)[b]} \put(-50,15){\line(0,-1){30}} \put( 0,15){\line(0,-1){30}} \put(100,15){\line(0,-1){30}} \put( 50,15){\line(0,-1){30}} \put(-52,16){$C$} \put(-2,16){$C$} \put(98,16){$C$} \put(48,16){$C$} \put(14,6){$s_1$} \put(84,6){$s_1$} \put(114,6){$s_1$} \put(-17,6){$s_1$} \put( 1,-11.5){$s_0$} \put(101,-11.5){$s_0$} \put(-49,-11.5){$s_4$} \put(51,-11.5){$s_4$} \end{picture} \caption{The actions of $s_0,s_1,s_4 \in \wt{\cC}_4$ as transpositions on $\mZ$.} \end{figure} \subsection{Locally even subgroups: $\cD_n$, $\wt \cB_n$ and $\wt \cD_n$} There are three possible ways of obtaining subgroups of the above compatible groups by adding a condition of local evenness at mirror positions. \subsubsection{Subgroup of $\cC_n$, locally even at 0: $\cD_n$ represents $D_{n}$, $n\ge 3$.} Define $\cD_n$ as the subgroup of $\cC_n$ consisting of all permutations that are locally even at position zero. $\cD_n$ is generated by the adjacent class transpositions $s_0=\la (-1 \ \ 2)\ra$ and, for $i=1,\dots,n-1$, $s_i=\la (i\ \ i+1)\ra$. \begin{figure}[tbh] \addtolength{\unitlength}{0.4pt} \begin{center} \begin{picture}(130,40)(-67,-20) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{2.3}} \put(-30,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(40,0){\circle*{2.3}} \put(30,0){\circle*{2.3}} \put(20,0){\circle*{2.3}} \put(10,0){\circle*{2.3}} \put(33,6){$s_3$} \put(-37,6){$s_3$} \put(-23.5,-11){$s_0$} \put( 18,-11){$s_0$} \thicklines \put( 35,0){\oval(10,8)[t]} \put(-35,0){\oval(10,8)[t]} \put( 5,0){\oval(30,28)[b]} \put( -5,0){\oval(30,28)[b]} \put( 0,15){\line(0,-1){30}} \put(-2,16){$D$} \end{picture} \addtolength{\unitlength}{0.6pt} \begin{picture}(40,15)(0,-15) \put( 20,-10){\circle{4}} \put(10,0){\circle{4}} \put(20,0){\circle{4}} \put(30,0){\circle{4}} \put(22,0){\line(1,0){6}} \put( 20,-2){\line(0,-1){6}} \put(12,0){\line(1,0){6}} \put(17,-15){$s_0$} \put(7,4){$s_1$} \put(17,4){$s_2$} \put(27,4){$s_3$} \end{picture} \end{center} \caption{The actions of $s_3$ and $s_0$ in $\cD_4$}\label{D4} \end{figure} Let us do the same example as for $C_4$. In $D_4$, the action of $s_3s_0$ is: \begin{eqnarray*} [-4,-3,-2,-1,0,1,2,3,4] & {\stackrel {s_3}{\longrightarrow}} & [-3,-4,-2,-1,0,1,2,4,3] \\ & {\stackrel {s_0}{\longrightarrow}} & [-3,-4,1, 2, 0,-2,-1,4,3]. \end{eqnarray*} \subsubsection{Subgroup of $\wt \cC_n$, locally even at 0: $\wt \cB_n$ represents $\wt B_{n}$, $n\ge 3$.} Define $\wt \cB_n$ as the subgroup of $\wt \cC_n$ consisting of all permutations that are locally even at zero. The adjacent class transpositions are $s_0=\la (-1 \ \ 2)\ra$ and $s_n=\la (n \ \ n+2)\ra$ and, for $i=1,\dots,n-1$, $s_i=\la (i\ \ i+1)\ra$. \subsubsection{Subgroup of $\wt \cB_n$, locally even at $n+1$: $\wt \cD_n$ represents $\wt D_{n}$, $n\ge 4$.} Define $\wt \cD_n$ as the subgroup of $\wt \cB_n$ consisting of all permutations that are locally even at position $n+1$. The adjacent class transpositions are $s_0=\la (-1 \ \ 2)\ra$ and $s_n=\la (n-1 \ \ n+2)\ra$ and, for $i=1,\dots,n-1$, $s_i=\la (i\ \ i+1)\ra$. \section{Theory of George groups} In this section we will develop a theory for George groups, analogous to the theory for the symmetric group, with concepts such as inversions, inversion tables, length function, weak order, descents and reflections. \subsection{Class inversions in George groups} Let $G$ be a George group. An {\em inversion} in a permutation $\pi$ is a pair $(\pi_i,\pi_j)$ such that $i\pi_j$. If $\la (i\ \ j)\ra$ is a class transposition in $G$ and $(\pi_i,\pi_j)$ is an inversion in $\pi\in G$, then the class $\la (\pi_i, \pi_j) \ra$ is a {\em class inversion} in $\pi$. If $i\pi_j$ is respected both by periodicity, $\pi_{i+n}> \pi_{j+n}$, and by mirrors, $\pi_{2m-j} > \pi_{2m-i}$. Thus every pair in the class inversion $\la (\pi_i, \pi_j) \ra$ is an inversion. \begin{example} Consider the permutation $\pi=[-2,1,-3,0,3,-1,2]$ in the George group $\cC_3$. \begin{center} \addtolength{\unitlength}{1.8pt} \begin{picture}(130,25)(-67,-10) \put(-40,0){\vector(1,0){80}} \put(-30,0){\circle*{1.4}} \put(-20,0){\circle*{1.4}} \put(-10,0){\circle*{1.4}} \put(0,0){\circle*{1.4}} \put(30,0){\circle*{1.4}} \put(20,0){\circle*{1.4}} \put(10,0){\circle*{1.4}} \thicklines \put( 0,8){\line(0,-1){16}} \put(-2,9){$C$} \scriptsize \put(-30,-4){\makebox(0,0){$-3$}} \put(-20,-4){\makebox(0,0){$-2$}} \put(-10,-4){\makebox(0,0){$-1$}} % \put(0,-4){\makebox(0,0){$0$}} \put(10,-4){\makebox(0,0){$1$}} \put(20,-4){\makebox(0,0){$2$}} \put(30,-4){\makebox(0,0){$3$}} \boldmath \put(-30,3){\makebox(0,0){$-2$} } \put(-20,3){\makebox(0,0){$1$}} \put(-10,3){\makebox(0,0){$-3$}} % \put(0,3){\makebox(0,0){$0$}} \put(10,3){\makebox(0,0){$3$}} \put(20,3){\makebox(0,0){$-1$} } \put(30,3){\makebox(0,0){$2$}} \end{picture} \end{center}\vspace{-5mm} There are seven inversions in $\pi$: $(-2,-3)$, $(1,-3)$, $(1,0)$, $(1,-1)$, $(0,-1)$, $(3,-1)$ and $(3,2)$. However, there are only three class inversions: \begin{eqnarray*} \la (3,2)\ra &=& \{(-2,-3),(3,2)\}, \\ \la (1,-3)\ra &=& \{(1,-3),(3,-1)\}, \\ \mbox{ and } \la (1,-1)\ra &=& \{(1,-1)\}. \end{eqnarray*} Hence, of the seven inversions we have five that are members of class inversions, while $(1,0)$ and $(0,-1)$ are not, since no class transposition involves 0, the mirror position. \end{example} We want to show that the adjacent class transpositions fill exactly the same role in George groups as the adjacent transpositions do in the symmetric group, in the following sense: adjacent transpositions create or resolve exactly one inversion, and if there exists any inversion then there exists an adjacent inversion. \begin{lemma}\label{lm:adjacent} An adjacent class transposition $\la (i \ \ j) \ra$, $ii$ in the class $\la j \ra$ such that $\pi^{-1}_i > \pi^{-1}_{j'}$, and hence $I^R_{ij}(\pi)$ is a finite set. \end{proof} Since the number of class inversions is finite, and adjacent class transpositions resolve class inversions, we can express all permutations in a George group as products of adjacent class transpositions as shown below. \begin{theorem}\label{pr:gen} A George group is generated by its adjacent class transpositions. \end{theorem} \begin{proof} The identity permutation is the only permutation with no class inversions. Suppose $\pi$ has class inversion number $\inv(\pi)>0$. Then by Lemma \ref{lm:inv-adjinv} it has an adjacent class inversion $\la (j,i)\ra$ and hence we can write $\pi=\pi'\la(i\ \ j)\ra$ where $\inv(\pi')=\inv(\pi)-1$ thanks to Lemma \ref{lm:adjacent}. Proceeding in this manner we eventually reach the identity, at which time we will have expressed $\pi$ as a product of adjacent class transpositions. \end{proof} \subsection{The length function and weak order on George groups} For a George group $G$, let $S$ be the set of adjacent class transpositions. Define the {\em length} $\ell(\pi)$ of $\pi\in G$ to be the smallest length of a word for $\pi$ in the alphabet $S$. This is the usual definition of length in Coxeter groups. We will now give a convenient formula for the length in terms of the number of class inversions. \begin{theorem} The length $\ell(\pi)$ equals the class inversion number $\inv(\pi)$. \end{theorem} \begin{proof} By the proof of Theorem \ref{pr:gen}, there is a word for $\pi$ of length $\inv(\pi)$. It is also shortest possible, since starting from the identity permutation (where the class inversion number is zero), each $s\in S$ can at most increase the number of class inversions by one. \end{proof} For a George group $G$ with generators $S$, define the {\em weak order} on $G$ by $\sigma\le \pi$ if there is a factorisation $\pi=\sigma s_{i_1}s_{i_2}\cdots s_{i_k}$ where $k=\ell(\pi)-\ell(\sigma)$ and all $s_{i_j}$ belong to $S$. This is the usual definition of weak order in Coxeter groups. We shall now establish two weak order criteria. First, we claim that weak order is equivalent to inclusion order on the set of class inversions. Second, this translates to a computationally tractable condition on the inversion tables. \begin{theorem} For any George group $G$, the following three assertions are equivalent: \begin{description} \item[(1)] $\pi\ge\sigma$ in the weak order on $G$. \item[(2)] $I(\pi)\supseteq I(\sigma)$ \item[(3)] $|\inv_{ij}(\pi)|\ge |\inv_{ij}(\sigma)|$ and $\sgn \inv_{ij}(\pi) = \sgn \inv_{ij}(\sigma)$ for all $i,j=1,\dots,n$. (Zero is considered both positive and negative.) \end{description} \end{theorem} \begin{proof} (1) $\Rightarrow$ (2): Assume that $\pi\ge \sigma$ in the weak order, so $\pi=\sigma s_{i_1}s_{i_2}\cdots s_{i_k}$ with $\ell(\pi)=\ell(\sigma)+ k$. Then each multiplication by a generator introduces a new class inversion, but the class inversions already in $I(\sigma)$ are not affected, so $I(\pi) \supseteq I(\sigma)$. (2) $\Rightarrow$ (1): Assume that $I(\pi) \supseteq I(\sigma)$ and show that there is a factorization $\pi=\pi's$ with $\ell(\pi) = \ell(\pi')+1$ and $I(\pi')\supseteq I(\sigma)$; induction would then give $\pi\ge \sigma$. Let $(\pi_i,\pi_j)$ be a representative of a class inversion in $I(\pi) \setminus I(\sigma)$, such that $\pi_i >\pi_j$, $i\pi_{i+1}$, i.e. an adjacent inversion. In a general Coxeter group, a descent is defined as a length decreasing generator. Define a {\em class descent} in $\pi$ as an adjacent class inversion. Obviously, the class descents in $\pi$ are in bijection with the set $$D(\pi)=\{s \in S \mid \ell(\pi s)<\ell(\pi)\},$$ where $S$ is the set of adjacent class transpositions, i.e. $D(\pi)$ are the length decreasing generators. By a reflection in a Coxeter group is meant an element that is conjugate to a Coxeter generator. In George groups, the reflections are then the class transpositions. \begin{lemma} A permutation $t\in G$ is a class transposition iff $t=\sigma^{-1} s \sigma$ for some generator $s\in S$ and permutation $\sigma \in G$. \end{lemma} \begin{proof} With $s = \la (i \ \ j) \ra$ and $\sigma_a = i, \sigma_b=j$ we have $\sigma^{-1} s \sigma = \la (a \ \ b) \ra$. \end{proof} \section{George groups and Weyl groups} The {\em raison d'\^etre} for the George groups is of course that they are isomorphic to the ABCD-families of Weyl groups. We are now ready to prove this. In the next section we shall take the Weyl groups in turn and give specific interpretations of the results of the previous chapter. To begin with, we must investigate what Coxeter relations there are between the generators of a George group $G$. \begin{lemma} If $s$ and $t$ are two adjacent class transpositions in a George group, then the order $m(s,t)$ of $st$ is \begin{description} \item[\boldmath $m(s,t)=2$] if $s$ and $t$ are disjoint; \addtolength{\unitlength}{0.4pt} \begin{center} \begin{picture}(130,8)(-67,-1) \put(-50,0){\vector(1,0){100}} \put(-40,0){\circle*{2.3}} \put(-30,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(0,0){\circle*{2.3}} \put(40,0){\circle*{2.3}} \put(30,0){\circle*{2.3}} \put(20,0){\circle*{2.3}} \put(10,0){\circle*{2.3}} \put(33,6){$t$} \put(-37,6){$s$} \thicklines \put( 35,0){\oval(10,8)[t]} \put(-35,0){\oval(10,8)[t]} % \put( 0,0){\oval(20,18)[b]} % \put( 0,15){\line(0,-1){30}} \end{picture} \end{center} \item[\boldmath $m(s,t)=\infty$] if the period is 2 and $s=\la (i\ \ i\!+\!1)\ra$ and $t=\la (i\!+\!1 \ \ i\!+\!2)\ra$ for some $i$; \begin{center} \begin{picture}(60,8)(-57,-1) \put(-50,0){\vector(1,0){60}} \put(-40,0){\circle*{2.3}} \put(-30,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(0,0){\circle*{2.3}} \put(-7,6){$t$} \put(-17,6){$s$} \put(-27,6){$t$} \put(-37,6){$s$} \thicklines \put( -5,0){\oval(10,8)[t]} \put(-15,0){\oval(10,8)[t]} \put(-25,0){\oval(10,8)[t]} \put(-35,0){\oval(10,8)[t]} % \put( 0,0){\oval(20,18)[b]} % \put( 0,15){\line(0,-1){30}} \end{picture} \end{center} \item[\boldmath $m(s,t)=3$] if any period is $\ge 3$ and $s=\la (i\ \ i\!+\!1)\ra$ and $t=\la (i\!+\!1 \ \ i\!+\!2)\ra$ for some $i$; \begin{center} \begin{picture}(60,8)(-57,-1) \put(-50,0){\vector(1,0){60}} \put(-40,0){\circle*{2.3}} \put(-30,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(0,0){\circle*{2.3}} \put(-17,6){$s$} \put(-27,6){$t$} \thicklines \put(-15,0){\oval(10,8)[t]} \put(-25,0){\oval(10,8)[t]} % \put( 0,0){\oval(20,18)[b]} % \put( 0,15){\line(0,-1){30}} \end{picture} \end{center} \item[\boldmath $m(s,t)=3$] if $s=\la (i\!-\!1 \ \ i)\ra$ and $t=\la (i\ \ i\!+\!3)\ra$ for some $i$ (where $i+2$ is a type $D$ mirror); \begin{center} \begin{picture}(90,30)(-47,-18) \put(-40,0){\vector(1,0){80}} \put(30,0){\circle*{2.3}} \put(-30,0){\circle*{2.3}} \put(20,0){\circle*{2.3}} \put(10,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(0,0){\circle*{2.3}} \put(-27,6){$s$} \put(23,6){$s$} \put(-22,-8){$t$} \put(20,-8){$t$} \put(-2,11){$D$} \thicklines \put(-25,0){\oval(10,8)[t]} \put(25,0){\oval(10,8)[t]} \put(-5,0){\oval(50,18)[b]} \put(5,0){\oval(50,18)[b]} \put( 0,10){\line(0,-1){20}} \end{picture} \end{center} \item[\boldmath $m(s,t)=2$] if $s=\la (i\ \ i\!+\!1)\ra$ and $t=\la (i\ \ i\!+\!3)\ra$ for some $i$ (where $i+2$ is a type $D$ mirror); \begin{center} \begin{picture}(70,30)(-37,-18) \put(-30,0){\vector(1,0){60}} \put(20,0){\circle*{2.3}} \put(10,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(0,0){\circle*{2.3}} \put(-17,6){$s$} \put(13,6){$s$} \put(-21,-8){$t$} \put(19,-8){$t$} \put(-2,11){$D$} \thicklines \put(-15,0){\oval(10,8)[t]} \put(15,0){\oval(10,8)[t]} \put(-5,0){\oval(30,18)[b]} \put(5,0){\oval(30,18)[b]} \put( 0,10){\line(0,-1){20}} \end{picture} \end{center} \item[\boldmath $m(s,t)=4$] if $s=\la (i\ \ i\!+\!1)\ra$ and $t=\la (i\!+\!1 \ \ i\!+\!3)\ra$ for some $i$ (where $i+2$ is a type $C$ mirror); \begin{center} \begin{picture}(70,40)(-37,-18) \put(-30,0){\vector(1,0){60}} \put(20,0){\circle*{2.3}} \put(10,0){\circle*{2.3}} \put(-20,0){\circle*{2.3}} \put(-10,0){\circle*{2.3}} \put(0,0){\circle*{2.3}} \put(-17,6){$s$} \put(13,6){$s$} \put(-4,6){$t$} \put(-2,11){$C$} \thicklines \put(-15,0){\oval(10,8)[t]} \put(15,0){\oval(10,8)[t]} \put(0,0){\oval(20,8)[t]} \put( 0,10){\line(0,-1){20}} \end{picture} \end{center} \end{description} \end{lemma} \begin{proof} Inspection. \end{proof} A convenient way of proving that a group with generators is isomorphic to a Coxeter group is to use the following characterization of the weak order of a Coxeter group. \begin{theorem}[K. Eriksson \cite{KE}] For any Coxeter group $(W,S)$ with Coxeter relations $(st)^{m(s,t)}=1$ for $s,t\in S$, there exists a poset $P$, unique up to isomorphism, such that: \begin{enumerate} \itemsep=0mm \item $P$ has a least element $\hat 0$. \item There are $|S|$ elements covering $\hat 0$. \item $P$ admits an $S$-labeling of the edges of its Hasse diagram satisfying: \begin{enumerate} \itemsep=0mm \item No two edges incident to the same element of $P$ have the same label. \item If there are two edges going upwards from $p\in P$ with labels $s$ and $t$, then they are the first edges of two upward going paths from $p$ of length $m(s,t)$ labeled alternatingly $s$ and $t$. If $m(s,t)<\infty$ then these paths end in the same element, while if $m(s,t)=\infty$ the paths go on forever. \end{enumerate} \end{enumerate} The poset $P$ is isomorphic to the weak order on $(W,S)$. \end{theorem} By this theorem we can prove that the weak order of a George group is isomorphic to the weak order of the Coxeter group with corresponding relations, and hence they are isomorphic as Coxeter systems. \begin{theorem} The George groups $\cS_n$ ($n\ge 2$), $\cC_n$ ($n\ge 2$), $\cD_n$ ($n\ge 3$), $\cS_n$ ($n\ge 2$), $\wt \cC_n$ ($n\ge 2$), $\wt \cB_n$ ($n\ge 3$), $\wt \cD_n$ ($n\ge 4$), generated by the set of adjacent class transpositions, are all Coxeter groups. \end{theorem} \begin{proof} We shall check that the weak order on a George group $G$ satisfies the conditions of the above theorem. Let $S_G$ be the set of adjacent class transpositions in $G$. \begin{enumerate} \itemsep=0mm \item The identity permutation is the least element. \item The identity has no inversions so all $|S_G|$ adjacent class transpositions will create inversions. Hence there are $|S_G|$ elements covering the identity. \item Every edge in the Hasse diagram of the weak order on $G$ is between pairs $\pi$ and $\pi s$ for some $s\in S_G$. Label the edge by $s$. This is clearly an $S_G$-labeling satisfying that no two edges incident to the same element $\pi$ have the same label. If there are two edges going upwards from $\pi$ with labels $s$ and $t$, then it is straightforward verification that they are the first edges of two upward going paths from $\pi$ of length $m(s,t)$ labeled alternatingly $s$ and $t$, and that if $m(s,t)<\infty$ then these paths end in the same element, while if $m(s,t)=\infty$ the paths go on forever. For example, take the case where $s=\la (i\ \ i\!+\!1)\ra$ and $t=\la (i\ \ i\!+\!3)\ra$ for some $i$ where $i+2$ is a type $D$ mirror; this gives $m(s,t)=2$. Both edges go upwards if both $\pi_i>\pi_{i+1}$ and $\pi_i>\pi_{i+3}$. We get two joining alternating paths of length two: \begin{center}\addtolength{\unitlength}{1.8pt} \begin{picture}(100,50)(-50,0) \put(0,0){\makebox(0,0){$[\dots,\pi_i,\pi_{i+1},D,\pi_{i+3}, \pi_{i+4},\dots]$}} \put(-40,20){\makebox(0,0){$[\dots,\pi_{i+1},\pi_{i},D,\pi_{i+4}, \pi_{i+3},\dots]$}} \put(0,40){\makebox(0,0){$[\dots,\pi_{i+4},\pi_{i+3},D,\pi_{i+1}, \pi_{i},\dots]$}} \put(40,20){\makebox(0,0){$[\dots,\pi_{i+3},\pi_{i+4},D,\pi_{i}, \pi_{i+1},\dots]$}} \put( -3,5){\line(-4,1){40}} \put(-15,10){\makebox(0,0){$s$}} \put( -3,35){\line(-4,-1){40}} \put( 15,10){\makebox(0,0){$t$}} \put( 3,5){\line(4,1){40}} \put(-15,30){\makebox(0,0){$t$}} \put( 3,35){\line(4,-1){40}} \put( 15,30){\makebox(0,0){$s$}} \end{picture} \end{center} \end{enumerate} \end{proof} \section{Inversion tables of George groups} We shall now follow up on the list of Section \ref{sc:list}. For every George group we shall give a characterization of the fundamental $n$-tuple and compute explicit expressions for the inversion table, from which the length formula and the weak order criterion follows. \subsection{Compatible groups} \subsubsection{George group $\cS_n$} The fundamental $n$-tuple is any permutation of $[1,\dots,n]$. The inversion table has $\inv_{ij} = -1$ if $i\pi^{-1}_j$, zero otherwise. All other entries are zero. Thus the length function $\ell(\pi)$ is the number of ordinary inversions in $\pi$. \subsubsection{George group $\wt \cS_n$} An $n$-tuple $[\pi_1,\dots,\pi_n]$ is the fundamental $n$-tuple of a $\pi\in \wt \cS_n$ if and only if it can be written $$[\tau_1+k_1n,\dots,\tau_n+k_nn]$$ where $\tau\in \cS_n$ and $k_1+\dots + k_n=0$. The action of $s_i$ on the fundamental $n$-tuple is $s_i = (i \ \ i+1)$ for $i=1,\dots,n-1$, while $s_n$ gives $[\pi_n-n,\pi_2,\dots,\pi_{n-1},\pi_1+n]$. The inversion table is given by $$ \inv_{ij}(\pi) = \left\{ \begin{array}{ll} \lfloor {\pi_j^{-1}-\pi_i^{-1} \over n} \rfloor & \mbox{ for } i \pi_j^{-1}; \\ 1 & \mbox{ if } i\ge j \mbox{ and } \pi_i^{-1} < \pi_{-j}^{-1}; \\ 0 & \mbox{ otherwise. } \\ \end{array}\right. $$ In terms of the fundamental $n$-tuple of $\pi$, the length function $\ell(\pi)$ is the number of pairs $(i,j)$ that are inversions, plus the number of pairs $(-i,j)$ that are inversions, plus the number of negative values in the fundamental $n$-tuple. \subsubsection{George group $\wt \cC_n$} An $n$-tuple $[\pi_1,\dots,\pi_n]$ is the fundamental $n$-tuple of a $\pi\in \wt \cC_n$ if and only if it can be written $$[\tau_1+k_1(2n+2),\dots,\tau_n+k_n(2n+2)]$$ where $\tau\in \cC_n$. The action of $s_i$ on the fundamental $n$-tuple is $s_i = (i \ \ i+1)$ for $i=1,\dots,n-1$, while $s_0$ gives $[-\pi_1,\pi_2,\dots,\pi_{n-1},\pi_1+n]$ and $s_n$ gives $[\pi_1,\pi_2,\dots,\pi_{n-1},2n+2-\pi_n]$. The inversion table is given by $$ \inv_{ij}(\pi) = \left\{ \begin{array}{ll} \lfloor {\pi_j^{-1}-\pi_i^{-1} \over 2n+2} \rfloor & \mbox{ for } i \pi_j^{-1}; \\ 1 & \mbox{ if } i> j \mbox{ and } \pi_i^{-1} < \pi_{-j}^{-1}; \\ 0 & \mbox{ otherwise. } \\ \end{array}\right. $$ In terms of the fundamental $n$-tuple of $\pi$, the length function $\ell(\pi)$ is the number of pairs $(i,j)$ that are inversions, plus the number of pairs $(-i,j)$ that are inversions. \subsubsection{George group $\wt \cB_n$} An $n$-tuple $[\pi_1,\dots,\pi_n]$ is the fundamental $n$-tuple of a $\pi\in \wt \cB_n$ if and only if it can be written $$[\tau_1+k_1(2n+2),\dots,\tau_n+k_n(2n+2)]$$ where $\tau\in \cC_n$ and the number $\sum_{i=1}^{n} | \lfloor {-\pi_i +n+1 \over 2n+2} \rfloor |$ is even. The action of $s_i$ on the fundamental $n$-tuple is $s_i = (i \ \ i+1)$ for $i=1,\dots,n-1$, while $s_0$ gives $[-\pi_2,-\pi_1,\pi_3,\dots,\pi_{n}]$ and $s_n$ gives $[\pi_1,\dots,\pi_{n-2}, 2n+2-\pi_n,2n+2-\pi_{n-1}]$. The inversion table is given by $$ \inv_{ij}(\pi) = \left\{ \begin{array}{ll} \lfloor {\pi_j^{-1}-\pi_i^{-1} \over 2n+2} \rfloor & \mbox{ for } ij; \\ \lfloor {\pi_i^{-1} \over 2n+2} \rfloor & \mbox{ for } i=j. \\ \end{array}\right. $$ \subsubsection{George group $\wt \cD_n$} An $n$-tuple $[\pi_1,\dots,\pi_n]$ is the fundamental $n$-tuple of a permutation $\pi\in \wt \cD_n$ if and only if it can be written $$[\tau_1+k_1(2n+2),\dots,\tau_n+k_n(2n+2)]$$ where $\tau\in \cC_n$ and the numbers $\sum_{i=1}^{n} | \lfloor {-\pi_i +n+1 \over 2n+2} \rfloor |$ and $\sum_{i=1}^{n} | \lfloor {\pi_i \over 2n+2} \rfloor |$ are both even. The action of $s_i$ on the fundamental $n$-tuple is $s_i = (i \ \ i+1)$ for $i=1,\dots,n-1$, while $s_0$ gives $[-\pi_2,-\pi_1,\pi_3,\dots,\pi_{n}]$ and $s_n$ gives $[\pi_1,\dots,\pi_{n-2}, 2n+2-\pi_n,2n+2-\pi_{n-1}]$. The inversion table is given by $$ \inv_{ij}(\pi) = \left\{ \begin{array}{ll} \lfloor {\pi_j^{-1}-\pi_i^{-1} \over 2n+2} \rfloor & \mbox{ for } ij; \\ 0 & \mbox{ for } i=j. \\ \end{array}\right. $$ \subsection{A conjecture on inversion tables} We have seen that the inversion table of a permutation in a George group determines the set of class inversions, and hence there is a unique permutation to each inversion table. A natural question to ask is how one can recognize if a given table of integers is the inversion table of a permutation. We conjecture a characterization. Let us restrict the discussion to $\wt \cC_n$; all cases look about the same. In $\wt \cC_n$ we have the inversion table $$ \inv_{ij}(\pi) = \left\{ \begin{array}{ll} \lfloor {\pi_j^{-1}-\pi_i^{-1} \over 2n+2} \rfloor & \mbox{ for } i \delta_{i+1}$. However, if $x_i$ was negative, then it will move one position to the left during the next step if $x_{i+1}$ is moved past the positive mirror image of $x_i$; hence, the $x_{i+1}$ might stop at the same position as the $x_i$ did, so $\delta_i\ge \delta_{i+1}$. To conclude that $\lambda(w)$ is a partition of the right kind, we must also verify that the number of parts greater than $n$ is $a(n)$ and that the total number of parts is $b(n)$. But this is clear, as the generator $s_0$ is used precisely once for every negative number that is inserted while $s_n$ is used once in every step. Finally, as in case $A$ it is easy to verify that for any such partition $\lambda$ the process is invertible. \end{proof} The above lemma can be summed up in the following three-variable generating function identity: \begin{equation} {\wt C}_n/C_n(q,t,u) \def \sum_{w\in {\wt C}_n/C_n} q^{\ell(w)}t^{a(w)}u^{b(w)} = \frac{(1+uq)(1+uq^2)\cdots(1+uq^n)} {(1-utq^{n+1})(1-utq^{n+2})\cdots (1-utq^{2n})}. \end{equation} This is of course equivalent with Eq. \ref{eq:cqtu}, the refined version of Bott's formula for $\wt C_n$. \subsection{Proof of Bott's formula for $\wt B_n$} The situation is the same for $\wt B_n$ as for $\wt C_n$, except for the fact that $s_n$ moves the number at position $n+2$ directly to position $n-1$, and simultaneously takes the number at position $n+3$ to position $n$. Here it is necessary to separate two cases: the smallest number to the right of the mirror at $n+1$ is of course at position $n+2$, but the second smallest one may be either the number next to it, at position $n+3$, or the number one period later, at position $n+2+(2n+2)$. \begin{definition} Let $w$ be a minimal coset representative in $\wt B_n/B_n$. We shall sort $w$ in two phases. The first phase continues as long the two smallest numbers to the right of the mirror at $n+1$ are at positions $n+2$ and $n+2+(2n+2)$. A step in the algorithm is to sort these two numbers into the segment in turn, and record their respective contributions to the length decrease, $\delta_{2i-1},\delta_{2i}$ in step $i$. Say that the first phase goes on for $k$ steps. In the second phase, the two smallest numbers to the right of the mirror at $n+1$ are at positions $n+2$ and $n+3$. We record in each step $i$ of the second phase the two length decreases $\delta_{2k+2i-1}, \delta_{2k+2i}$ from sorting the two inserted numbers into the segment respectively, counting the use of $s_n$ as contributing to $\delta_{2k+2i-1}$ and $s_{n-1}$ as contributing to $\delta_{2k+2i}$. We give an example for $\wt B_3$ showing the segment $[-3,3]$ in each step and recording the sequence of length decreases. The numbers to be moved into the segment is $8$ plus the numbers at positions $-3$ and $-2$. First phase: \begin{eqnarray*} [-43, -14, -5, 0, 5, 14, 43] & {\stackrel{\delta_1=5, \delta_2=5}{\longrightarrow}} & [-25, -14, -5, 0, 5, 14, 25] \\ & {\stackrel{\delta_3=5, \delta_4=4}{\longrightarrow}} & [-14, -9, -5, 0, 5, 9, 14] \end{eqnarray*} Second phase: \begin{eqnarray*} [-14, -9, -5, 0, 5, 9, 14] & {\stackrel{\delta_5=4, \delta_6=3}{\longrightarrow}} & [-6, -5, -1, 0, 1, 5, 6] \\ & {\stackrel{\delta_7=1, \delta_8=0}{\longrightarrow}} & [-3, -2, -1, 0, 1, 2, 3] \end{eqnarray*} \end{definition} \begin{lemma}\label{lm:B-Bott} $\lambda$ is a bijection from $\wt B_n/B_n$ to the set of integer partitions with parts in $\{1,2,\ldots,2n-1\}$ and at most one part of each size up to $n-1$. If $a(w)$ denote the number of occurrences of $s_0$ in a reduced word for $w$, then the partition $\lambda(w)$ will have $a(w)$ parts greater than $n-1$. \end{lemma} \begin{proof} In step $i$ in the first phase, we take the numbers at positions $n+2$ and $n+2+(2n+2)$, say $x_i$ and $x_i+(2n+2)$, and inserts them into the segment $[-n,n]$. Since $x_i+(2n+2)$ is the second smallest element to right of $n+1$, we know that $x_i$ will be sorted to the leftmost position in the segment and hence its contribution to the length decrease is $\delta_{2i-1}=2n-1$ (and not $2n$, thanks to the jumping start). If then $x_i+(2n+2)$ is sorted to the leftmost position as well, phase two may go on; otherwise, it is easily verified that we must now shift to the second phase. In the second phase we record in each step the movement of the two inserted numbers, which both, thanks to their jumping start, will be moved at most $2n-2$ times by class adjacent transpositions. Similarly, it takes only $n$ switches for each of these numbers to reach to the negative side. Now we can copy the argument from the case of $\wt C_n/C_n$. \end{proof} The above lemma can be summed up in the following two-variable generating function identity: \begin{equation} {\wt B_n}/B_n(q,t) \def \sum_{w\in {\wt B_n}/B_n} q^{\ell(w)}t^{a(w)} = \frac{(1+q)(1+q^2)\cdots(1+q^{n-1})} {(1-tq^{n})(1-tq^{n+1})\cdots (1-tq^{2n-1})}. \end{equation} This is equivalent with Eq. \ref{eq:bqt}, the refined version of Bott's formula for $\wt B_n$. \subsection{Proof of Bott's formula for $\wt D_n$} The situation for $\wt D_n$ is similar to $\wt B_n$, with the exception that also $s_0$ is of type $D$, switching $(-2,1)$ and $(-1,2)$ and periodically. Here the parabolic subgroup $D_n$ may sometimes not be able to sort the entire segment $[-n,n]$; the minimal coset representatives of $\wt D_n/D_n$ are the permutations in $\wt D_n$ that are increasing in the position segment $[-n,n]$ except possibly in the subsegment $[-1,1]$. Define the map $\lambda$ in analogy with the previous section. \begin{lemma}\label{lm:D-Bott} $\lambda$ is a bijection from $\wt D_n/D_n$ to the set of integer partitions with parts in $\{1,2,\ldots,2n-2\}$ and at most one part of each size up to $n-2$, and possibly with one of the parts of size $n-1$ marked with a dot. \end{lemma} \begin{proof} The difference from the case of $\wt B_n/B_n$ is that now the numbers get to jump in the middle of the segment too. Hence, each will be moved at most $2n-2$ times in total, and it takes only $n-1$ switches for each of these numbers to reach to the negative side, since $s_1$ is not needed before using $s_0$ in order to get to the negative side. However, if a number is positive and is to be placed directly to the right of zero, we will use $s_1$ and record a ``dotted'' length decrease of $n-1$. Now we can follow the argument of case $\wt B_n/B_n$. . \end{proof} The above lemma can be summed up in the following generating function identity: \begin{equation}\label{eq:dq} {\wt D_n}/D_n(q) \def \sum_{w\in {\wt D_n}/D_n} q^{\ell(w)} = \frac{(1+q)(1+q^2)\cdots(1+q^{n-1})} {(1-q^{n-1})(1-q^{n})\cdots (1-q^{2n-2})}. \end{equation} However, Bott's formula demands another equality: \begin{equation}\label{eq:dq2} {\wt D_n}/D_n(q) = \frac{1} {(1-q^{1})(1-q^{3})\cdots (1-q^{2n-3})(1-q^{n-1}}. \end{equation} To see that the formulas (\ref{eq:dq}) and (\ref{eq:dq2}) are equivalent we need one final bijection. \begin{lemma}\label{lm:partition} We have the generating function identity \[ \frac{1}{(1-q^{1})(1-q^{3})\cdots (1-q^{2n-3})} = \frac{(1+q)(1+q^2)\cdots(1+q^{n-1})}{(1-q^{n})(1-q^{n+1})\cdots (1-q^{2n-2})}. \] Equivalently, the set $I$ of integer partitions into parts of sizes in $\{1,3,\ldots,2n-3\}$ is in bijection with the set $J$ of integer partitions into parts of sizes in $\{1,2,3,\ldots,2n-2\}$ with at most one part of each size up to $n-1$. \end{lemma} \begin{proof} A bijection can be described in the following way. As long as there are two equal parts of some size $k\le n-1$, merge them into one part of size $2k$. Clearly this process gives a map from $I$ to $J$ and it is a bijection since we have the following inverse map from $J$ to $I$. As long as there is an even part $2k$, split it into two parts of size $k$. \end{proof} \newpage \begin{thebibliography}{ABC} \bibitem{Be} R. B\'edard, Cells for two Coxeter groups, {\em Comm. Algebra} {\bf 14} (1986), 1253--1286. \bibitem{Bj} A. Bj{\"o}rner, Orderings of Coxeter groups, in {\em Combinatorics and Algebra}, Contemporary Math. {\bf 34}, Amer. Math. Soc., 1984, pp. 175--195. \bibitem{BB1} A. Bj{\"o}rner and F. Brenti, Affine permutations of type $A$, {\em Electronic Journal of Combinatorics} {\bf 3} no. 2 (1996), \#R18. \bibitem{BB2} A. Bj{\"o}rner and F. Brenti, {\em Combinatorics of Coxeter groups}, book manuscript draft, 1994. \bibitem{Bo} R. Bott, An application of the Morse theory to the topology of Lie-groups, {\em Bull. Soc. Math. France} {\bf 84} (1956), 251--281. \bibitem{BE} M. Bousquet-M{\'e}lou and K. Eriksson, Lecture hall partitions, {\em Ramanujan Journal}, {\bf 1} (1997), 101--111. \bibitem{Bre} F. Brenti, $q$-Eulerian polynomials arising from Coxeter groups, {\em European J. Combinatorics} {\bf 15} (1994), 417--441. \bibitem{De} V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative M{\"o}bius function, {\em Invent. Math.} {\bf 39} (1977), 187--198. \bibitem{ER} R. Ehrenborg and M. Readdy, Juggling and applications to $q$-analogues, {\em Discrete Math.}, {\bf 157} (1996), 107--125. \bibitem{Eh} C. Ehresmann, Sur la topologie de certains espaces homog\`enes, {\em Ann. Math.} {\bf 35} (1934), 396--443. \bibitem{HE} H. Eriksson, {\em Computational and combinatorical aspects of Coxeter groups}, PhD thesis, KTH, Stockholm, Sweden, 1994. \bibitem{KE} K. Eriksson, Polygon posets and the weak order of Coxeter groups, {\it J. Algebraic Comb.} {\bf 4} (1995), 233--252. \bibitem{Hu} J. Humphreys, {\em Reflection groups and Coxeter groups}, Cambridge Univ. Press, 1990. \bibitem{Lu} G. Lusztig, Some examples of square integrable representations of semisimple $p$-adic groups, {\em Trans. Amer. Math. Soc.} {\bf 277} (1983), 623--653. \bibitem{Ma} I. G. Macdonald, The Poincar\'e series of a Coxeter group, {\em Math. Ann.} {\bf 199} (1972) 161--174. \bibitem{Pr} R.\ Proctor, Classical Bruhat orders and lexicographic shellability, {\em J. Algebra} {\bf 77} (1982), 104--126. \bibitem{Re} V.\ Reiner, The distribution of descents and length in a Coxeter group, {\em Electronic Journal of Combinatorics} {\bf 2} (1995), R25. \bibitem{Sh} J.Y. Shi, Some results relating two presentations of certain affine Weyl groups, {\em J. Algebra} {\bf 163} (1994), 235--257. \bibitem{JYS} J.Y. Shi, On two presentations of the affine Weyl groups of the classical types, preprint 1998. \end{thebibliography} \end{document}