WikiJournal of Science/Affine symmetric group

Definitions

The affine symmetric group, ${\tilde{S}}_n$, may be equivalently defined as an abstract group by generators and relations, or in terms of concrete geometric and combinatorial models.

Algebraic definition

Dynkin diagrams for the affine symmetric groups on 2 and more than 2 generators

In terms of generators and relations, ${\tilde{S}}_n$ is generated by a set $$s_0,s_1,\dots ,s_{n-1}$$ of Template:Mvar elements that satisfy the following relations: when $n\ge 3$,

1. $s_i^2=1$ (the generators are involutions),
2. $s_i{s}_j=s_j{s}_i$ if Template:Mvar is not one of $i-1,i,i+1$, and
3. $s_i{s}_{i+1}{s}_i=s_{i+1}{s}_i{s}_{i+1}$.

In the relations above, indices are taken [[w:modular arithmetic|modulo Template:Mvar]], so that the third relation includes as a particular case $s_0{s}_{n-1}{s}_0=s_{n-1}{s}_0{s}_{n-1}$. (The second and third relation are sometimes called the braid relations.) When $n=2$, the affine symmetric group ${\tilde{S}}_2$ is the infinite dihedral group generated by two elements $s_0,s_1$ subject only to the relations $s_0^2=s_1^2=1$.Template:Sfnp

This definition endows ${\tilde{S}}_n$ with the structure of a Coxeter group, with the $s_i$ as Coxeter generating set. For $n\ge 3$, its Coxeter–Dynkin diagram is the Template:Mvar-cycle, while for $n=2$ it consists of two nodes joined by an edge labeled $\mathrm{\infty }$.Template:Sfnp

Geometric definition

When Template:Math, the space Template:Mvar is a two-dimensional plane and the reflections are across lines. The points of the type A root lattice are circled.

In the Euclidean space ${ℝ}^n$ with coordinates $(x_1,\dots ,x_n)$, the set Template:Mvar of points that satisfy the equation $x_1+x_2+\dots +x_n=0$ forms a (hyper)plane (an Template:Math-dimensional subspace). For every pair of distinct elements Template:Mvar and Template:Mvar of $\{1,\dots ,n\}$ and every integer Template:Mvar, the set of points in Template:Mvar that satisfy $x_i-x_j=k$ forms a plane in Template:Mvar, and there is a unique reflection of Template:Mvar that fixes this plane. Then the affine symmetric group can be realized geometrically as the collection of all maps from Template:Mvar to itself that arise by composing several of these reflections.Template:Sfnp

Inside Template:Mvar, the type A root lattice Template:Math is the subset of points with integer coordinates, that is, it is the set of all the integer vectors $(a_1,\dots ,a_n)$ such that $a_1+\dots +a_n=0$. Each of the reflections preserves this lattice, and so the lattice is preserved by the whole group. In fact, one may define ${\tilde{S}}_n$ to be the group of rigid transformations of Template:Mvar that preserve the lattice Template:Math.

These reflecting planes divide the space Template:Mvar into congruent simplicies, called alcoves.Template:Sfnp The situation when $n=3$ is shown at right; in this case, the root lattice is a triangular lattice, and the reflecting lines divide the plane into equilateral triangular alcoves. (For larger Template:Mvar, the alcoves are not regular simplices.)

Reflections and alcoves for the affine symmetric group. The fundamental alcove is shaded.

To translate between the geometric and algebraic definitions, fix an alcove and consider the Template:Mvar hyperplanes that form its boundary. For example, there is a unique alcove (the fundamental alcove) consisting of points $(x_1,\dots ,x_n)$ such that $x_1\ge x_2\ge \dots \ge x_n\ge x_1-1$, which is bounded by the hyperplanes $x_1-x_2=0$, $x_2-x_3=0$, ..., and $x_1-x_n=1$. (This is illustrated in the case $n=3$ at right.) For $i=1,\dots ,n-1$, one may identify the reflection through $x_i-x_{i+1}=0$ with the Coxeter generator $s_i$, and also identify the reflection through $x_1-x_n=1$ with the generator $s_0=s_n$.Template:Sfnp

Combinatorial definition

The affine symmetric group may be realized as a group of periodic permutations of the integers. In particular, say that a bijection $u:\mathbb{Z}\to \mathbb{Z}$ is an affine permutation if $u(x+n)=u(x)+n$ for all integers Template:Mvar and $u(1)+u(2)+\dots +u(n)=1+2+\dots +n$. (It is a consequence of the first property that the numbers $u(1),\dots ,u(n)$ must all be distinct modulo Template:Mvar.) Such a function is uniquely determined by its window notation $[u(1),\dots ,u(n)]$, and so affine permutations may also be identified with tuples $[u(1),\dots ,u(n)]$ of integers that contain one element from each congruence class modulo Template:Mvar and sum to $1+2+\dots +n$.Template:Sfnp

To translate between the combinatorial and algebraic definitions, for $i=1,\dots ,n-1$ one may identify the Coxeter generator $s_i$ with the affine permutation that has window notation $[1,2,\dots ,i-1,i+1,i,i+2,\dots ,n]$, and also identify the generator $s_0=s_n$ with the affine permutation $[0,2,3,\dots ,n-2,n-1,n+1]$. More generally, every reflection (that is, a conjugate of one of the Coxeter generators) can be described uniquely as follows: for distinct integers Template:Mvar, Template:Mvar in $\{1,\dots ,n\}$ and arbitrary integer Template:Mvar, it maps Template:Mvar to Template:Math, maps Template:Mvar to Template:Math, and fixes all inputs not congruent to Template:Mvar or Template:Mvar modulo Template:Mvar.Template:Sfnp (In terms of the geometric definition, this corresponds to the reflection across the plane $x_i-x_j=k$. The correspondence between the geometric and combinatorial representations for other elements is discussed below.)

Representation as matrices

One may represent affine permutations as infinite periodic permutation matrices.Template:Sfnp If $u:\mathbb{Z}\to \mathbb{Z}$ is an affine permutation, one places the entry 1 at position $(i,u(i))$ in the infinite grid $\mathbb{Z}\times \mathbb{Z}$ for each integer Template:Mvar, and all other entries are equal to 0. Since Template:Mvar is a bijection, the resulting matrix contains exactly one 1 in every row and column. The periodicity condition on the map Template:Mvar ensures that the entry at position $(a,b)$ is equal to the entry at position $(a+n,b+n)$ for every pair of integers $(a,b)$. For example, a portion of matrix for the affine permutation $[2,0,4]\in {\tilde{S}}_3$ is shown below, with the conventions that 1s are replaced by •, 0s are omitted, rows numbers increase from top to bottom, column numbers increase from left to right, and the boundary of the box consisting of rows and columns 1, 2, 3 is drawn: $$\begin{array}{ccccccccc}& \bullet & & & & & & & \\ & & & & & & & & \\ & & & \bullet & & & & & \\ & & & & \bullet & & & & \\ & & \bullet & & & & & & \\ & & & & & & \bullet & & \\ & & & & & & & \bullet & \\ & & & & & \bullet & & & \end{array}$$

Relationship to the finite symmetric group

The affine symmetric group ${\tilde{S}}_n$ contains the finite symmetric group $S_n$ as both a subgroup and a quotient.

As a subgroup

There is a canonical way to choose a subgroup of ${\tilde{S}}_n$ that is isomorphic to the finite symmetric group $S_n$. In terms of the algebraic definition, this is the subgroup of ${\tilde{S}}_n$ generated by $s_1,\dots ,s_{n-1}$ (excluding the simple reflection $s_0=s_n$). Geometrically, this corresponds to the subgroup of transformations that fix the origin, while combinatorially it corresponds to the window notations for which $\{u(1),\dots ,u(n)\}=\{1,2,\dots ,n\}$ (that is, in which the window notation is the one-line notation of a finite permutation).Template:SfnpTemplate:Sfnp

If $u=[u(1),u(2),\dots ,u(n)]$ is the window notation of an element of this standard copy of $S_n\subset {\tilde{S}}_n$, its action on the hyperplane Template:Mvar in ${ℝ}^n$ is given by permutation of coordinates: $(x_1,x_2,\dots ,x_n)\cdot u=(x_{u(1)},x_{u(2)},\dots ,x_{u(n)})$. (In this article, the geometric action of permutations and affine permutations is on the right; thus, if Template:Mvar and Template:Mvar are two affine permutations, the action of Template:Math on a point is given by first applying Template:Mvar, then applying Template:Mvar.)

There are also many nonstandard copies of $S_n$ contained in ${\tilde{S}}_n$. A geometric construction is to pick any point Template:Mvar in Template:Math (that is, an integer vector whose coordinates sum to 0); the subgroup $({\tilde{S}}_n{)}_a$ of ${\tilde{S}}_n$ of isometries that fix Template:Mvar is isomorphic to $S_n$. The analogous combinatorial construction is to choose any subset Template:Mvar of $\mathbb{Z}$ that contains one element from each conjugacy class modulo Template:Mvar and whose elements sum to $1+2+\dots +n$; the subgroup $({\tilde{S}}_n{)}_A$ of ${\tilde{S}}_n$ of affine permutations that stabilize Template:Mvar is isomorphic to $S_n$.

As a quotient

There is a simple map (technically, a surjective group homomorphism) Template:Mvar from ${\tilde{S}}_n$ onto the finite symmetric group $S_n$. In terms of the combinatorial definition, it is to reduce the window entries modulo Template:Mvar to elements of $\{1,2,\dots ,n\}$, leaving the one-line notation of a permutation. The image $\pi (u)$ of an affine permutation Template:Mvar is called the underlying permutation of Template:Mvar.

The map Template:Mvar sends the Coxeter generator $s_0=[0,2,3,4,\dots ,n-2,n-1,n+1]$ to the permutation whose one-line notation and cycle notation are $[n,2,3,4,\dots ,n-2,n-1,1]$ and $(1n)$, respectively. In terms of the Coxeter generators of $S_n$, this can be written as $\pi (s_0)=s_1{s}_2\cdots s_{n-2}{s}_{n-1}{s}_{n-2}\cdots s_2{s}_1$.

The kernel Template:Mvar is the set of affine permutations whose underlying permutation is the identity. The window notations of such affine permutations are of the form $[1-a_1\cdot n,2-a_2\cdot n,\dots ,n-a_n\cdot n]$, where $(a_1,a_2,\dots ,a_n)$ is an integer vector such that $a_1+a_2+\dots +a_n=0$, that is, where $(a_1,\dots ,a_n)\in \mathrm{\Lambda }$. Geometrically, this kernel consists of the translations, that is, the isometries that shift the entire space Template:Mvar without rotating or reflecting it. In an abuse of notation, the symbol Template:Math is used in this article for all three of these sets (integer vectors in Template:Mvar, affine permutations with underlying permutation the identity, and translations); in all three settings, the natural group operation turns Template:Math into an abelian group, generated freely by the Template:Math vectors $\{(1,-1,0,\dots ,0),(0,1,-1,\dots ,0),\dots ,(0,\dots ,0,1,-1)\}$.

Connection between the geometric and combinatorial definitions

Alcoves for ${\tilde{S}}_3$ labeled by affine permutations. An alcove Template:Mvar is labeled by the window notation for a permutation Template:Mvar if Template:Mvar sends the fundamental alcove (shaded) to Template:Mvar. Negative numbers are denoted by overbars.

The subgroup Template:Math is a normal subgroup of ${\tilde{S}}_n$, and one has an isomorphism $${\tilde{S}}_n\cong S_n⋉\mathrm{\Lambda }$$ between ${\tilde{S}}_n$ and the semidirect product of the finite symmetric group $S_n$ with Template:Math, where the action of $S_n$ on Template:Math is by permutation of coordinates. Consequently, identifying the finite symmetric group $S_n$ as its standard copy in ${\tilde{S}}_n$, one has that every element Template:Mvar of ${\tilde{S}}_n$ may be realized uniquely as a product $u=r\cdot t$ where $r\in S_n$ is a finite permutation and $t\in \mathrm{\Lambda }$.

This point of view allows for a direct translation between the combinatorial and geometric definitions of ${\tilde{S}}_n$: if one writes $[u(1),\dots ,u(n)]=[r_1-a_1\cdot n,\dots ,r_n-a_n\cdot n]$ where $r=[r_1,\dots ,r_n]=\pi (u)$ and $(a_1,a_2,\dots ,a_n)\in \mathrm{\Lambda }$ then the affine permutation Template:Mvar corresponds to the rigid motion of Template:Mvar defined by $$(x_1,\dots ,x_n)\cdot u=(x_{r(1)}+a_1,\dots ,x_{r(n)}+a_n).$$

Furthermore, as with every affine Coxeter group, the affine symmetric group acts transitively and freely on the set of alcoves. Hence, by making an arbitrary choice of alcove $A_0$, one may place the group in one-to-one correspondence with the alcoves: the identity element corresponds to $A_0$, and every other group element Template:Mvar corresponds to the alcove $A=A_0\cdot g$ that is the image of $A_0$ under the action of Template:Mvar. This identification for ${\tilde{S}}_3$ is illustrated at right.

Example: Template:Math

The affine symmetric group ${\tilde{S}}_2$ acts on the line Template:Mvar in the Euclidean plane. The reflections are through the dashed lines. The vectors of the root lattice Template:Math are marked.

Algebraically, ${\tilde{S}}_2$ is the infinite dihedral group, generated by two generators $s_0,s_1$ subject to the relations $s_0^2=s_1^2=1$. Every other element of the group can be written as an alternating product of copies of $s_0$ and $s_1$.

Combinatorially, the affine permutation $s_1$ has window notation $[2,1]$, corresponding to the bijection $2k\mapsto 2k-1,2k-1\mapsto 2k$ for every integer Template:Mvar. The affine permutation $s_0$ has window notation $[0,3]$, corresponding to the bijection $2k\mapsto 2k+1,2k+1\mapsto 2k$ for every integer Template:Mvar. Other elements have the following window notations:

• $\stackrel{2k\text{factors}}{\overbrace{s_0{s}_1\cdots s_0{s}_1}}=[1+2k,2-2k]$,
• $\stackrel{2k\text{factors}}{\overbrace{s_1{s}_0\cdots s_1{s}_0}}=[1-2k,2+2k]$,
• $\stackrel{2k+1\text{factors}}{\overbrace{s_0{s}_1\cdots s_0}}=[2+2k,1-2k]$,
• $\stackrel{2k+1\text{factors}}{\overbrace{s_1{s}_0\cdots s_1}}=[2-2(k+1),1+2(k+1)]$.

Geometrically, the space Template:Mvar is the line with equation $x+y=0$ in the Euclidean plane ${ℝ}^2$. The root lattice inside Template:Mvar consists of those pairs $(a,-a)$ for integral Template:Mvar. The Coxeter generator $s_1$ acts on Template:Mvar by reflection across the line $x=y$ (that is, across the origin); the generator $s_0$ acts on Template:Mvar by reflection across the line $x=y+1$ (that is, across the point $(\frac{1}{2},-\frac{1}{2})$. It is natural to identify the line Template:Mvar with the real line ${ℝ}^1$, by sending the point $(x,-x)$ to the real number Template:Math. With this identification, the root lattice consists of the even integers; the fundamental alcove is the interval Template:Math; the element $(s_1{s}_0{)}^k$ acts by translation by Template:Mvar for any integer Template:Mvar; and the reflection $s_1(s_0{s}_1{)}^k$ reflects across the point Template:Math for any integer Template:Mvar.

Permutation statistics and permutation patterns

Many permutation statistics and other features of the combinatorics of finite permutations can be extended to the affine case.

Descents, length, and inversions

The length $\ell (g)$ of an element Template:Mvar of a Coxeter group Template:Mvar is the smallest number Template:Mvar such that Template:Mvar can be written as a product $g=s_{i_1}\cdots s_{i_k}$ of Template:Mvar Coxeter generators of Template:Mvar.Template:Sfnp

Geometrically, the length of an element Template:Mvar in ${\tilde{S}}_n$ is the number of reflecting hyperplanes that separate $A_0$ and $A_0\cdot g$, where $A_0$ is the fundamental alcove (the simplex bounded by the reflecting hyperplanes of the Coxeter generators $s_0,s_1,\dots ,s_{n-1}$). (In fact, the same is true for any affine Coxeter group.)Template:Sfnp

Combinatorially, the length of an affine permutation is encoded in terms of an appropriate notion of inversions. In particular, one has for an affine permutation Template:Mvar thatTemplate:Sfnp $$\ell (u)=\mathrm{\#}\{(i,j):i\in \{1,\dots ,n\},i<j,\text{ and }u(i)>u(j)\}.$$ Alternatively, it is the number of equivalence classes of pairs $(i,j)\in \mathbb{Z}\times \mathbb{Z}$ such that $i<j$ and $u(i)>u(j)$ under the equivalence relation $(i,j)\equiv (i^{\prime },j^{\prime })$ if $(i-i^{\prime },j-j^{\prime })=(kn,kn)$ for some integer Template:Mvar.

The generating function for length in ${\tilde{S}}_n$ isTemplate:SfnpTemplate:Sfnp $$\sum _{g\in {\tilde{S}}_n}{q}^{\ell (g)}=\frac{1-q^n}{(1-q{)}^n}.$$

Similarly, one may define an affine analogue of descents in permutations: say that an affine permutation Template:Mvar has a descent in position Template:Mvar if $u(i)>u(i+1)$. (By periodicity, Template:Mvar has a descent in position Template:Mvar if and only if it has a descent in position $i+kn$ for all integers Template:Mvar.)Template:Sfnp

Algebraically, the descents corresponds to the right descents in the sense of Coxeter groups; that is, Template:Mvar is a descent of Template:Mvar if and only if $\ell (u\cdot s_i)<\ell (u)$.Template:Sfnp The left descents (that is, those indices Template:Mvar such that $\ell (s_i\cdot u)<\ell (u)$ are the descents of the inverse affine permutation $u^{-1}$; equivalently, they are the values Template:Mvar such that Template:Mvar occurs before Template:Math in the sequence $\dots ,u(-2),u(-1),u(0),u(1),u(2),\dots$.

Geometrically, Template:Mvar is a descent of Template:Mvar if and only if the fixed hyperplane of $s_i$ separates the alcoves $A_0$ and $A_0\cdot u$.

Because there are only finitely many possibilities for the number of descents of an affine permutation, but infinitely many affine permutations, it is not possible to naively form a generating function for affine permutations by number of descents (an affine analogue of Eulerian polynomials).Template:Sfnp One possible resolution is to consider affine descents (equivalently, cyclic descents) in the finite symmetric group $S_n$.Template:Sfnp Another is to consider simultaneously the length and number of descents of an affine permutation. The generating function for these statistics over ${\tilde{S}}_n$ simultaneously for all Template:Mvar is $$\sum _{n\ge 1}\frac{x^n}{1-q^n}\sum _{w\in {\tilde{S}}_n}{t}^{\mathrm{des}(w)}{q}^{\ell (w)}={\left[\frac{x\cdot \frac{\partial }{\partial x}\log (\exp (x;q))}{1-t\exp (x;q)}\right]}_{x\mapsto x\frac{1-t}{1-q}}$$ where Template:Math is the number of descents of the affine permutation Template:Mvar and $\exp (x;q)=\sum _{n\ge 0}\frac{x^n(1-q{)}^n}{(1-q)(1-q^2)\cdots (1-q^n)}$ is the [[w:q-exponential|Template:Mvar-exponential function]].Template:Sfnp

Cycle type and reflection length

Any bijection $u:\mathbb{Z}\to \mathbb{Z}$ partitions the integers into a (possibly infinite) list of (possibly infinite) cycles: for each integer Template:Mvar, the cycle containing Template:Mvar is the sequence $(\dots ,u^{-2}(i),u^{-1}(i),i,u(i),u^2(i),\dots )$ where exponentiation represents functional composition. For example, the affine permutation in ${\tilde{S}}_5$ with window notation $[6,3,2,0,4]$ contains the two infinite cycles $(\dots ,-9,-4,1,6,11,\dots )$ and $(\dots ,10,9,5,4,0,-1,-5\dots )$ as well as infinitely many finite cycles $(5k+2,5k+3)$ for each $k\in \mathbb{Z}$. Cycles of an affine permutation correspond to cycles of the underlying permutation in an obvious way: in the example above, with underlying permutation $[1,3,2,5,4]=(1)(23)(45)$, the first infinite cycle corresponds to the cycle (1), the second corresponds to the cycle (45), and the finite cycles all correspond to the cycle (23).

For an affine permutation Template:Mvar, the following conditions are equivalent: all cycles of Template:Mvar are finite, Template:Mvar has finite order, and the geometric action of Template:Mvar on the space Template:Mvar has at least one fixed point.Template:Sfnp

The reflection length ${\ell }_R(u)$ of an element Template:Mvar of ${\tilde{S}}_n$ is the smallest number Template:Mvar such that there exist reflections $r_1,\dots ,r_k$ such that $u=r_1\cdots r_k$. (In the symmetric group, reflections are transpositions, and the reflection length of a permutation Template:Mvar is $n-c(u)$, where $c(u)$ is the number of cycles of Template:Mvar.Template:Sfnp) In Template:Harv, the following formula was proved for the reflection length of an affine permutation Template:Mvar: for each cycle of Template:Mvar, define the weight to be the integer k such that consecutive entries congruent modulo Template:Mvar differ by exactly Template:Math. (For example, in the permutation $[6,3,2,0,4]$ above, the first infinite cycle has weight 1 and the second infinite cycle has weight −1; all finite cycles have weight 0.) Form a tuple of cycle weights of Template:Mvar (counting translates of the same cycle by multiples of Template:Mvar only once), and define the nullity $\nu (u)$ to be the size of the smallest set partition of this tuple so that each part sums to 0. (In the example above, the tuple is $(1,-1,0)$ and the nullity is 2, since one can take the partition $(1,-1),(0)$.) Then the reflection length of Template:Mvar is $${\ell }_R(u)=n-2\nu (u)+c(\pi (u)),$$ where $\pi (u)$ is the underlying permutation of Template:Mvar.Template:Sfnp

For every affine permutation Template:Mvar, there is a choice of subgroup Template:Mvar of ${\tilde{S}}_n$ such that $W\cong S_n$, ${\tilde{S}}_n=W⋉\mathrm{\Lambda }$, and for the standard form $u=w\cdot t$ implied by this semidirect product, one has ${\ell }_R(u)={\ell }_R(w)+{\ell }_R(t)$.Template:Sfnp

Fully commutative elements and pattern avoidance

A reduced word for an element Template:Mvar of a Coxeter group is a tuple $(s_{i_1},\dots ,s_{i_{\ell (g)}})$ of Coxeter generators of minimum possible length such that $g=s_{i_1}\cdots s_{i_{\ell (g)}}$.Template:Sfnp The element Template:Mvar is called fully commutative if one can transform any reduced word into any other by sequentially swapping pairs of factors that commute.Template:Sfnp For example, in the finite symmetric group $S_4$, the element $2143=(12)(34)$ is fully commutative, since its two reduced words $(s_1,s_3)$ and $(s_3,s_1)$ can be connected by swapping commuting factors, but $3214=(13)(2)(4)$ is not fully commutative because there is no way to reach the reduced word $(s_2,s_1,s_2)$ starting from the reduced word $(s_1,s_2,s_1)$ by commutations.

Template:Harvtxt proved that in the finite symmetric group $S_n$, a permutation is fully commutative if and only if it avoids the permutation pattern 321, that is, if and only if its one-line notation contains no three-term decreasing subsequence. In Template:Harv, this result was extended to affine permutations: an affine permutation Template:Mvar is fully commutative if and only if there do not exist integers $i<j<k$ such that $u(i)>u(j)>u(k)$.Template:Efn

It has also been shown that the number of affine permutations avoiding a single pattern Template:Mvar is finite if and only if Template:Mvar avoids the pattern 321,Template:Sfnp so in particular there are infinitely many fully commutative affine permutations. These were enumerated by length in Template:Harv.

Parabolic subgroups and other structures

The parabolic subgroups of ${\tilde{S}}_n$ and their coset representatives offer a rich combinatorial structure. Other aspects of the affine symmetric group, such as its Bruhat order and representation theory, may also be understood via combinatorial models.

Parabolic subgroups, coset representatives

Abacus diagram of the affine permutation [−5, 0, 6, 9].

A standard parabolic subgroup of a Coxeter group is a subgroup generated by a subset of its Coxeter generating set. The maximal parabolic subgroups are those that come from omitting a single Coxeter generator. In ${\tilde{S}}_n$, all maximal parabolic subgroups are isomorphic to the finite symmetric group $S_n$. The subgroup generated by the subset $\{s_0,\dots ,s_{n-1}\}\setminus \{s_i\}$ consists of those affine permutations that stabilize the interval $[i+1,i+n]$, that is, that map every element of this interval to another element of the interval.Template:Sfnp

The non-maximal parabolic subgroups of ${\tilde{S}}_n$ are all isomorphic to parabolic subgroups of $S_n$, that is, to a Young subgroup $S_{a_1}\times \cdots \times S_{a_k}$ for some positive integers $a_1,\dots ,a_k$ with sum Template:Mvar.

For a fixed element Template:Mvar of $\{0,\dots ,n-1\}$, let $J=\{s_0,\dots ,s_{n-1}\}\setminus \{s_i\}$ be the maximal proper subset of Coxeter generators omitting $s_i$, and let $({\tilde{S}}_n{)}_J$ denote the parabolic subgroup generated by Template:Mvar. Every coset $g\cdot ({\tilde{S}}_n{)}_J$ has a unique element of minimum length. The collection of such representatives, denoted $({\tilde{S}}_n{)}^J$, consists of the following affine permutations:Template:Sfnp $$({\tilde{S}}_n{)}^J=\{u\in {\tilde{S}}_n:u(i-n+1)<u(i-n+2)<\dots <u(i-1)<u(i)\}.$$

In the particular case that $J=\{s_1,\dots ,s_{n-1}\}$, so that $({\tilde{S}}_n{)}_J\cong S_n$ is the standard copy of $S_n$ inside ${\tilde{S}}_n$, the elements of $({\tilde{S}}_n{)}^J\cong {\tilde{S}}_n/S_n$ may naturally be represented by abacus diagrams: the integers are arranged in an infinite strip of width Template:Mvar, increasing sequentially along rows and then from top to bottom; integers are circled if they lie directly above one of the window entries of the minimal coset representative. For example, the minimal coset representative $u=[-5,0,6,9]$ is represented by the abacus diagram at right. To compute the length of the representative from the abacus diagram, one adds up the number of uncircled numbers that are smaller than the last circled entry in each column. (In the example shown, this gives $5+3+0+1=9$.)Template:Sfnp

Other combinatorial models of minimum-length coset representatives for ${\tilde{S}}_n/S_n$ can be given in terms of core partitions (integer partitions in which no hook length is divisible by Template:Mvar) or bounded partitions (integer partitions in which no part is larger than Template:Math). Under these correspondences, it can be shown that the weak Bruhat order on ${\tilde{S}}_n/S_n$ is isomorphic to a certain subposet of Young's lattice.Template:SfnpTemplate:Sfnp

Bruhat order

The Bruhat order on ${\tilde{S}}_n$ has the following combinatorial realization. If Template:Mvar is an affine permutation and Template:Mvar and Template:Mvar are integers, define $u[i,j]$ to be the number of integers Template:Mvar such that $a\le i$ and $u(a)\ge j$. (For example, with $u=[2,0,4]\in {\tilde{S}}_3$, one has $u[3,1]=3$: the three relevant values are $a=0,1,3$, which are respectively mapped by Template:Mvar to 1, 2, and 4.) Then for two affine permutations Template:Mvar, Template:Mvar, one has that $u\le v$ in Bruhat order if and only if $u[i,j]\le v[i,j]$ for all integers Template:Mvar, Template:Mvar.Template:Sfnp

Representation theory and an affine Robinson–Schensted correspondence

In the finite symmetric group, the Robinson–Schensted correspondence gives a bijection between the group and pairs $(P,Q)$ of standard Young tableaux of the same shape. This bijection plays a central role in the combinatorics and the representation theory of the symmetric group. For example, in the language of Kazhdan–Lusztig theory, two permutations lie in the same left cell if and only if their images under Robinson–Schensted have the same tableau Template:Mvar, and in the same right cell if and only if their images have the same tableau Template:Mvar. In Template:Harv, J.-Y. Shi showed that left cells for ${\tilde{S}}_n$ are indexed instead by tabloids,Template:Efn and in Template:Harv he gave an algorithm to compute the tabloid analogous to the tableau Template:Mvar for an affine permutation. In Template:Harv, the authors extended Shi's work to give a bijective map between ${\tilde{S}}_n$ and triples $(P,Q,\rho )$ consisting of two tabloids of the same shape and an integer vector whose entries satisfy certain inequalities. Their procedure uses the matrix representation of affine permutations and generalizes the shadow construction of Template:Harvtxt.

Inverse realizations

Alcoves for ${\tilde{S}}_3$ labeled by affine permutations, inverse to the labeling above.

In some situations, one may wish to consider the action of the affine symmetric group on $\mathbb{Z}$ or on alcoves that is inverse to the one given above.Template:Efn We describe these alternate realizations now.

In the combinatorial action of ${\tilde{S}}_n$ on $\mathbb{Z}$, the generator $s_i$ acts by switching the values Template:Mvar and Template:Math. In the inverse action, it instead switches the entries in positions Template:Mvar and Template:Math. Similarly, the action of a general reflection will be to switch the entries at positions Template:Math and Template:Math for each Template:Mvar, fixing all inputs at positions not congruent to Template:Mvar or Template:Mvar modulo Template:Mvar.Template:Sfnp (In the finite symmetric group $S_n$, the analogous distinction is between the active and passive forms of a permutation.)

In the geometric action of ${\tilde{S}}_n$, the generator $s_i$ acts on an alcove Template:Mvar by reflecting it across one of the bounding planes of the fundamental alcove Template:Math. In the inverse action, it instead reflects Template:Mvar across one of its own bounding planes. From this perspective, a reduced word corresponds to an alcove walk on the tesselated space Template:Mvar.

Relationship to other mathematical objects

The affine symmetric group is closely related to a variety of other mathematical objects.

Juggling patterns

The juggling pattern 441 visualized as an arc diagram: the height of each throw corresponds to the length of an arc; the two colors of nodes are the left and right hands of the juggler. This pattern has four crossings, which repeat periodically.

The juggling pattern 441. Template:Attrib

In Template:Harv, a correspondence is given between affine permutations and juggling patterns encoded in a version of siteswap notation.Template:Sfnp Here, a juggling pattern of period Template:Mvar is a sequence $(a_1,\dots ,a_n)$ of nonnegative integers (with certain restrictions) that captures the behavior of balls thrown by a juggler, where the number $a_i$ indicates the length of time the Template:Mvarth throw spends in the air (equivalently, the height of the throw).Template:Efn The number Template:Mvar of balls in the pattern is the average $b=\frac{a_1+\dots +a_n}{n}$.Template:Sfnp The Ehrenborg–Readdy correspondence associates to each juggling pattern $𝐚=(a_1,\dots ,a_n)$ of period Template:Mvar the function $w_{𝐚}:\mathbb{Z}\to \mathbb{Z}$ defined by $$w_{𝐚}(i)=i+a_i-b,$$ where indices of the sequence a are taken modulo Template:Mvar. Then $w_{𝐚}$ is an affine permutation in ${\tilde{S}}_n$, and moreover every affine permutation arises from a juggling pattern in this way.Template:Sfnp Under this bijection, the length of the affine permutation is encoded by a natural statistic in the juggling pattern: one has $$\ell (w_{𝐚})=(b-1)n-\mathrm{cross}(𝐚),$$ where $\mathrm{cross}(𝐚)$ is the number of crossings (up to periodicity) in the arc diagram of a. This allows an elementary proof of the generating function for affine permutations by length.Template:Sfnp

For example, the juggling pattern 441 (illustrated at right) has $n=3$ and $b=\frac{4+4+1}{3}=3$. Therefore, it corresponds to the affine permutation $w_{441}=[1+4-3,2+4-3,3+1-3]=[2,3,1]$. The juggling pattern has four crossings, and the affine permutation has length $\ell (w_{441})=(3-1)\cdot 3-4=2$.

Similar techniques can be used to derive the generating function for minimal coset representatives of ${\tilde{S}}_n/S_n$ by length.Template:Sfnp

Complex reflection groups

In a finite-dimensional real inner product space, a reflection is a linear transformation that fixes a linear hyperplane pointwise and negates the vector orthogonal to the plane. This notion may be extended to vector spaces over other fields. In particular, in a complex inner product space, a reflection is a unitary transformation Template:Mvar of finite order that fixes a hyperplane.Template:Efn This implies that the vectors orthogonal to the hyperplane are eigenvectors of Template:Mvar, and the associated eigenvalue is a complex root of unity. A complex reflection group is a finite group of linear transformations on a complex vector space generated by reflections.

The complex reflection groups were fully classified by Template:Harvtxt: each complex reflection group is isomorphic to a product of irreducible complex reflection groups, and every irreducible either belongs to an infinite family $G(m,p,n)$ (where Template:Mvar, Template:Mvar, and Template:Mvar are positive integers such that Template:Mvar divides Template:Mvar) or is one of 34 other (so-called "exceptional") examples. The group $G(m,1,n)$ is the generalized symmetric group: algebraically, it is the wreath product $(\mathbb{Z}/m\mathbb{Z})\wr S_n$ of the cyclic group $\mathbb{Z}/m\mathbb{Z}$ with the symmetric group $S_n$. Concretely, the elements of the group may be represented by monomial matrices (matrices having one nonzero entry in every row and column) whose nonzero entries are all Template:Mvarth roots of unity. The groups $G(m,p,n)$ are subgroups of $G(m,1,n)$, and in particular the group $G(m,m,n)$ consists of those matrices in which the product of the nonzero entries is equal to 1.

In Template:Harv, Shi showed that the affine symmetric group is a generic cover of the family $\{G(m,m,n):m\ge 1\}$, in the following sense: for every positive integer Template:Mvar, there is a surjection ${\pi }_m$ from ${\tilde{S}}_n$ to $G(m,m,n)$, and these maps are compatible with the natural surjections $G(m,m,n)\twoheadrightarrow G(p,p,n)$ when $p\mid m$ that come from raising each entry to the Template:Mathth power. Moreover, these projections respect the reflection group structure, in that the image of every reflection in ${\tilde{S}}_n$ under ${\pi }_m$ is a reflection in $G(m,m,n)$; and similarly when $m>1$ the image of the standard Coxeter element $s_0\cdot s_1\cdots s_{n-1}$ in ${\tilde{S}}_n$ is a Coxeter element in $G(m,m,n)$.Template:Sfnp

Affine Lie algebras

Each affine Coxeter group is associated to an affine Lie algebra, a certain infinite-dimensional non-associative algebra with unusually nice representation-theoretic properties. In this association, the Coxeter group arises as a group of symmetries of the root space of the Lie algebra (the dual of the Cartan subalgebra).Template:Sfnp In the classification of affine Lie algebras, the one associated to ${\tilde{S}}_n$ is of (untwisted) type $A_{n-1}^{(1)}$, with Cartan matrix $\left[\begin{array}{cc}2& -2\\ -2& 2\end{array}\right]$ for $n=2$ and $$\left[\begin{array}{cccccc}2& -1& 0& \cdots & 0& -1\\ -1& 2& -1& \cdots & 0& 0\\ 0& -1& 2& \cdots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & 2& -1\\ -1& 0& 0& \cdots & -1& 2\end{array}\right]$$ (a circulant matrix) for $n>2$.Template:Sfnp

Like other Kac–Moody algebras, affine Lie algebras satisfy the Weyl–Kac character formula, which expresses the characters of the algebra in terms of their highest weights.Template:Sfnp In the case of affine Lie algebras, the resulting identities are equivalent to the Macdonald identities. In particular, for the affine Lie algebra of type $A_1^{(1)}$, associated to the affine symmetric group ${\tilde{S}}_2$, the corresponding Macdonald identity is equivalent to the Jacobi triple product.Template:Sfnp

Extended affine symmetric group

The affine symmetric group is a subgroup of the extended affine symmetric group. The extended group is isomorphic to the wreath product $\mathbb{Z}\wr S_n$. Its elements are extended affine permutations: bijections $u:\mathbb{Z}\to \mathbb{Z}$ such that $u(x+n)=u(x)+n$ for all integers Template:Mvar. Unlike the affine symmetric group, the extended affine symmetric group is not a Coxeter group. However, it has a natural generating set that extends the Coxeter generating set for ${\tilde{S}}_n$: the shift operator $\tau$ whose window notation is $\tau =[2,3,\dots ,n,n+1]$ generates the extended group with the simple reflections, subject to the additional relations $\tau s_i{\tau }^{-1}=s_{i+1}$.Template:Sfnp

Combinatorics of other affine Coxeter groups

The geometric action of the affine symmetric group ${\tilde{S}}_n$ places it naturally in the family of affine Coxeter groups, all of which have a similar geometric action. The combinatorial description of the ${\tilde{S}}_n$ may also be extended to many of these groups: in Template:Harv, an axiomatic description is given of certain permutation groups acting on $\mathbb{Z}$ (the "George groups", in honor of George Lusztig), and it is shown that they are exactly the "classical" Coxeter groups of finite and affine types A, B, C, and D. Thus, the combinatorial interpretations of descents, inversions, etc., carry over in these cases.Template:Sfnp Abacus models of minimum-length coset representatives for parabolic quotients have also been extended to this context.Template:Sfnp

Acknowledgements

The author thanks the three referees for their many helpful comments, and Max Glick for his help with the less technical summary. The work of the author was supported in part by a Simons Collaboration Grant (634530).

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation