# WikiJournal Preprints/Affine symmetric group

Open access • Publication charge free • Public peer review

<meta name='citation_doi' value=>

## Article information

Author: Joel Brewster Lewis[a][i]

Lewis, J.

## Abstract

In mathematics, the affine symmetric group is a group that arises in combinatorics and representation theory. It is an infinite extension of the symmetric group ${\displaystyle S_{n}}$ of all permutations of a finite set. It may be defined in algebraic, geometric, or combinatorial terms; these definitions extend many important properties and constructions associated with ${\displaystyle S_{n}}$ to the infinite setting.

## Definitions

The affine symmetric group 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, ${\displaystyle {\widetilde {S}}_{n}}$ is generated by a set

${\displaystyle s_{1},\ldots ,s_{n}}$
of n elements that satisfy the following relations: when ${\displaystyle n\geq 3}$,

1. ${\displaystyle s_{i}^{2}=1}$ (the generators are involutions),
2. ${\displaystyle s_{i}s_{j}=s_{j}s_{i}}$ if j is not one of ${\displaystyle i-1,i,i+1}$, and
3. ${\displaystyle s_{i}s_{i+1}s_{i}=s_{i+1}s_{i}s_{i+1}}$.

In the relations above, indices are taken modulo n, so that the third relation includes as a particular case ${\displaystyle s_{n}s_{1}s_{n}=s_{1}s_{n}s_{1}}$. (The second and third relation are sometimes called the braid relations.) When ${\displaystyle n=2}$, the affine symmetric group ${\displaystyle {\widetilde {S}}_{2}}$ is the infinite dihedral group generated by two elements ${\displaystyle s_{1},s_{2}}$ subject only to the relations ${\displaystyle s_{1}^{2}=s_{2}^{2}=1}$.[1]

This definition endows ${\displaystyle {\widetilde {S}}_{n}}$ with the structure of a Coxeter group, with the ${\displaystyle s_{i}}$ as Coxeter generating set. For ${\displaystyle n\geq 3}$, its Coxeter–Dynkin diagram is the n-cycle, while for ${\displaystyle n=2}$ it consists of two nodes joined by an edge labeled ${\displaystyle \infty }$.[2]

### Geometric definition

When n = 3, the space V 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 ${\displaystyle \mathbb {R} ^{n}}$ with coordinates ${\displaystyle (x_{1},\ldots ,x_{n})}$, the set V of points that satisfy the equation ${\displaystyle x_{1}+x_{2}+\ldots +x_{n}=0}$ form a (hyper)plane (an (n − 1)-dimensional subspace). For every distinct elements i and j of ${\displaystyle \{1,\ldots ,n\}}$ and every integer k, the set of points in V that satisfy ${\displaystyle x_{i}-x_{j}=k}$ form a plane in V, and there is a unique reflection of V that fixes this plane. Then the affine symmetric group can be realized geometrically as the collection of all maps from V to itself that arise by composing several of these reflections.[3]

Inside V, the type A root lattice Λ is the subset of points with integer coordinates, that is, it is the set of all the integer vectors ${\displaystyle (a_{1},\ldots ,a_{n})}$ such that ${\displaystyle a_{1}+\ldots +a_{n}=0}$. Each of the reflections preserves this lattice, and so the lattice is preserved by whole the group. In fact, one may define ${\displaystyle {\widetilde {S}}_{n}}$ to be the group rigid transformations of V that preserve the lattice Λ.

These reflecting planes divide the space V into congruent simplicies, called alcoves.[4] The situation when ${\displaystyle 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 n, 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 n hyperplanes that form its boundary. For example, there is a unique alcove (the fundamental alcove) consisting of points ${\displaystyle (x_{1},\ldots ,x_{n})}$ such that ${\displaystyle x_{1}\geq x_{2}\geq \dots \geq x_{n}\geq x_{1}-1}$, which is bounded by the hyperplanes ${\displaystyle x_{1}-x_{2}=0}$, ${\displaystyle x_{2}-x_{3}=0}$, ..., and ${\displaystyle x_{1}-x_{n}=1}$. (This is illustrated in the case ${\displaystyle n=3}$ at right.) For ${\displaystyle i=1,\ldots ,n-1}$, one may identify the reflection through ${\displaystyle x_{i}-x_{i+1}=0}$ with the Coxeter generator ${\displaystyle s_{i}}$, and also identify the reflection through ${\displaystyle x_{1}-x_{n}=1}$ with the generator ${\displaystyle s_{0}=s_{n}}$.[4]

### Combinatorial definition

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

To translate between the combinatorial and algebraic definitions, for ${\displaystyle i=1,\ldots ,n-1}$ one may identify the Coxeter generator ${\displaystyle s_{i}}$ with the affine permutation that has window notation ${\displaystyle [1,2,\ldots ,i-1,i+1,i,i+2,\ldots ,n]}$, and also identify the generator ${\displaystyle s_{0}=s_{n}}$ with the affine permutation ${\displaystyle [0,2,3,\ldots ,n-2,n-1,\ldots ,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 i, j in ${\displaystyle \{1,\ldots ,n\}}$ and arbitrary integer k, it maps i to jkn, maps j to i + kn, and fixes all inputs not congruent to i or j modulo n.[6] (In terms of the geometric definition, this corresponds to the reflection across the plane ${\displaystyle 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.[7] If ${\displaystyle u:\mathbb {Z} \to \mathbb {Z} }$ is an affine permutation, one places the entry 1 at position ${\displaystyle (i,u(i))}$ in the infinite grid ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ for each integer i, and all other entries are equal to 0. Since u is a bijection, the resulting matrix contains exactly one 1 in every row and column. The periodicity condition on the map u ensures that the entry at position ${\displaystyle (a,b)}$ is equal to the entry at position ${\displaystyle (a+n,b+n)}$ for every pair of integers ${\displaystyle (a,b)}$. For example, a portion of matrix for the affine permutation ${\displaystyle [2,0,4]\in {\widetilde {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:

${\displaystyle {\begin{array}{cccc|ccc|cccc}&&\bullet &&&&&&&\\\bullet &&&&&&&&&\\&&&&\bullet &&&&&\\\hline &&&&&\bullet &&&&\\&&&\bullet &&&&&&\\&&&&&&&\bullet &&\\\hline &&&&&&&&\bullet &\\&&&&&&\bullet &&&\end{array}}}$

## Relationship to the finite symmetric group

The affine symmetric group ${\displaystyle {\widetilde {S}}_{n}}$ contains the finite symmetric group ${\displaystyle S_{n}}$ as both a subgroup and a quotient.

### As a subgroup

There is a canonical way to choose a subgroup of ${\displaystyle {\widetilde {S}}_{n}}$ that is isomorphic to the finite symmetric group ${\displaystyle S_{n}}$. In terms of the algebraic definition, this is the subgroup of ${\displaystyle {\widetilde {S}}_{n}}$ generated by ${\displaystyle s_{1},\ldots ,s_{n-1}}$ (excluding the simple reflection ${\displaystyle 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 ${\displaystyle \{u(1),\ldots ,u(n)\}=\{1,2,\ldots ,n\}}$ (that is, in which the window notation is the one-line notation of a finite permutation).[8][3]

If ${\displaystyle u=[u(1),u(2),\ldots ,u(n)]}$ is the window notation of an element of this standard copy of ${\displaystyle S_{n}\subset {\widetilde {S}}_{n}}$, its action on the hyperplane is given by permutation of coordinates: ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})\cdot u=(x_{u(1)},x_{u(2)},\ldots ,x_{u(n)})}$. (In this article, the geometric action of permutations and affine permutations is on the right; thus, if u and v are two affine permutations, the action of uv on a point is given by first applying u, then applying v.)

There are also many nonstandard copies of ${\displaystyle S_{n}}$ contained in ${\displaystyle {\widetilde {S}}_{n}}$. A geometric construction is to pick any point a in Λ (that is, an integer vector whose coordinates sum to 0); the subgroup ${\displaystyle ({\widetilde {S}}_{n})_{a}}$ of ${\displaystyle {\widetilde {S}}_{n}}$ of isometries that fix a is isomorphic to ${\displaystyle S_{n}}$. The analogous combinatorial construction is to choose any subset A of ${\displaystyle \mathbb {Z} }$ that contains one element from each conjugacy class modulo n and whose elements sum to ${\displaystyle 1+2+\ldots +n}$; the subgroup ${\displaystyle ({\widetilde {S}}_{n})_{A}}$ of ${\displaystyle {\widetilde {S}}_{n}}$ of affine permutations that fix A is isomorphic to ${\displaystyle S_{n}}$.

### As a quotient

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

The map π sends the Coxeter generator ${\displaystyle s_{0}=[0,2,3,4,\ldots ,n-2,n-1,n+1]}$ to the permutation whose one-line notation and cycle notation are ${\displaystyle [n,2,3,4,\ldots ,n-2,n-1,1]}$ and ${\displaystyle (1\;n)}$. In terms of the Coxeter generators of ${\displaystyle S_{n}}$, this can be written ${\displaystyle \pi (s_{0})=s_{1}s_{2}\cdots s_{n-2}s_{n-1}s_{n-2}\cdots s_{2}s_{1}}$.

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

### Connection between the geometric and combinatorial definitions

Alcoves for ${\displaystyle {\widetilde {S}}_{3}}$ labeled by affine permutations. An alcove A is labeled by the window notation for a permutation u if u sends the fundamental alcove (shaded) to A. Negative numbers are denoted by overbars.

The subgroup Λ is a normal subgroup of ${\displaystyle {\widetilde {S}}_{n}}$, and one has an isomorphism

${\displaystyle {\widetilde {S}}_{n}\cong S_{n}\ltimes \Lambda }$
between ${\displaystyle {\widetilde {S}}_{n}}$ and the semidirect product of the finite symmetric group ${\displaystyle S_{n}}$ with Λ, where the action of ${\displaystyle S_{n}}$ on Λ is by permutation of coordinates. Consequently, identifying the finite symmetric group ${\displaystyle S_{n}}$ as its standard copy in ${\displaystyle {\widetilde {S}}_{n}}$, one has that every element u of ${\displaystyle {\widetilde {S}}_{n}}$ may be realized uniquely as a product ${\displaystyle u=r\cdot t}$ where ${\displaystyle r\in S_{n}}$ is a finite permutation and ${\displaystyle t\in \Lambda }$.

This point of view allows for a direct translation between the combinatorial and geometric definitions of ${\displaystyle {\widetilde {S}}_{n}}$: if one writes ${\displaystyle [u(1),\ldots ,u(n)]=[r_{1}-a_{1}\cdot n,\ldots ,r_{n}-a_{n}\cdot n]}$ where ${\displaystyle r=[r_{1},\ldots ,r_{n}]=\pi (u)}$ and ${\displaystyle (a_{1},a_{2},\ldots ,a_{n})\in \Lambda }$ then the affine permutation u corresponds to the rigid motion of V defined by

${\displaystyle (x_{1},\ldots ,x_{n})\cdot u=\left(x_{r(1)}+a_{1},\ldots ,x_{r(n)}+a_{n}\right).}$

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 ${\displaystyle A_{0}}$, one may place the group in one-to-one correspondence with the alcoves: the identity element corresponds to ${\displaystyle A_{0}}$, and every other group element g corresponds to the alcove ${\displaystyle A=A_{0}\cdot g}$ that is the image of ${\displaystyle A_{0}}$ under the action of g. This identification for ${\displaystyle {\widetilde {S}}_{3}}$ is illustrated at right.

### Example: n = 2

The affine symmetric group ${\displaystyle {\widetilde {S}}_{2}}$ acts on the line V in the Euclidean plane. The reflections are through the dashed lines. The vectors of the root lattice Λ are marked.

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

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

• ${\displaystyle \overbrace {s_{0}s_{1}\cdots s_{0}s_{1}} ^{2k\,{\text{factors}}}=[1+2k,2-2k]}$,
• ${\displaystyle \overbrace {s_{1}s_{0}\cdots s_{1}s_{0}} ^{2k\,{\text{factors}}}=[1-2k,2+2k]}$,
• ${\displaystyle \overbrace {s_{0}s_{1}\cdots s_{0}} ^{2k+1\,{\text{factors}}}=[2+2k,1-2k]}$,
• ${\displaystyle \overbrace {s_{1}s_{0}\cdots s_{1}} ^{2k+1\,{\text{factors}}}=[2-2(k+1),1+2(k+1)]}$.

Geometrically, the space V is the line with equation ${\displaystyle x+y=0}$ in the Euclidean plane ${\displaystyle \mathbb {R} ^{2}}$. The root lattice inside V consists of those pairs ${\displaystyle (a,-a)}$ for integral a. The Coxeter generator ${\displaystyle s_{1}}$ acts on V by reflection across the line ${\displaystyle x=y}$ (that is, across the origin); the generator ${\displaystyle s_{0}}$ acts on V by reflection across the line ${\displaystyle x=y+1}$ (that is, across the point ${\displaystyle \left({\tfrac {1}{2}},-{\tfrac {1}{2}}\right)}$. It is natural to identify the line V with the real line ${\displaystyle \mathbb {R} ^{1}}$, by sending the point ${\displaystyle (x,-x)}$ to the real number 2x. With this identification, the root lattice consists of the even integers; the fundamental alcove is the interval [0, 1]; the element ${\displaystyle (s_{1}s_{0})^{k}}$ acts by translation by k for any integer k; and the reflection ${\displaystyle s_{1}(s_{0}s_{1})^{k}}$ reflects across the point k for any integer k.

## Descents, length, and inversions

The length ${\displaystyle \ell (g)}$ of an element g of a Coxeter group G is the smallest number k such that g can be written as a product ${\displaystyle g=s_{i_{1}}\cdots s_{i_{k}}}$ of k Coxeter generators of G.[9]

Geometrically, the length of an element g in ${\displaystyle {\widetilde {S}}_{n}}$ is the number of reflecting hyperplanes that separate ${\displaystyle A_{0}}$ and ${\displaystyle A_{0}\cdot g}$, where ${\displaystyle A_{0}}$ is the fundamental alcove (the simplex bounded by the reflecting hyperplanes of the Coxeter generators ${\displaystyle s_{1},\ldots ,s_{n}}$). (In fact, the same is true for any affine Coxeter group.)[10]

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 u that[11]

${\displaystyle \ell (u)=\#\left\{(i,j)\colon i\in \{1,\ldots ,n\},iu(j)\right\}.}$
Alternatively, it is the number of equivalence classes of pairs ${\displaystyle (i,j)\in \mathbb {Z} \times \mathbb {Z} }$ such that ${\displaystyle i and ${\displaystyle u(i)>u(j)}$ under the equivalence relation ${\displaystyle (i,j)\equiv (i',j')}$ if ${\displaystyle (i-i',j-j')=(kn,kn)}$ for some integer k.

The generating function for length in ${\displaystyle {\widetilde {S}}_{n}}$ is[12][13]

${\displaystyle \sum _{g\in {\widetilde {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 u has a descent in position i if ${\displaystyle u(i)>u(i+1)}$. (By periodicity, u has a descent in position i if and only if it has a descent in position ${\displaystyle i+kn}$ for all integers k.)[14]

Algebraically, the descents corresponds to the right descents in the sense of Coxeter groups; that is, i is a descent of u if and only if ${\displaystyle \ell (u\cdot s_{i})<\ell (u)}$.[14] The left descents (that is, those indices i such that ${\displaystyle \ell (s_{i}\cdot u)<\ell (u)}$ are the descents of the inverse affine permutation ${\displaystyle u^{-1}}$; equivalently, they are the values i such that i occurs before i − 1 in the sequence ${\displaystyle \ldots ,u(-2),u(-1),u(0),u(1),u(2),\ldots }$.

Geometrically, i is a descent of u if and only if the fixed hyperplane of ${\displaystyle s_{i}}$ separates the alcoves ${\displaystyle A_{0}}$ and ${\displaystyle A_{0}\cdot u}$.

## 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 ${\displaystyle {\widetilde {S}}_{n}}$, all maximal parabolic subgroups are isomorphic to the finite symmetric group ${\displaystyle S_{n}}$. The subgroup generated by the subset ${\displaystyle \{s_{1},\ldots ,s_{n}\}\smallsetminus \{s_{i}\}}$ consists of those affine permutations that stabilize the interval ${\displaystyle [i+1,i+n]}$, that is, that map every element of this interval to another element of the interval.[14]

The non-maximal parabolic subgroups of ${\displaystyle {\widetilde {S}}_{n}}$ are all isomorphic to parabolic subgroups of ${\displaystyle S_{n}}$, that is, to a Young subgroup ${\displaystyle S_{a_{1}}\times \cdots \times S_{a_{k}}}$ for some positive integers ${\displaystyle a_{1},\ldots ,a_{k}}$ with sum n.

For a fixed element i of ${\displaystyle \{1,\ldots ,n\}}$, let ${\displaystyle J=\{s_{1},\ldots ,s_{n}\}\smallsetminus \{s_{i}\}}$ be the maximal proper subset of Coxeter generators omitting ${\displaystyle s_{i}}$, and let ${\displaystyle ({\widetilde {S}}_{n})_{J}}$ denote the parabolic subgroup generated by J. Every coset ${\displaystyle g\cdot ({\widetilde {S}}_{n})_{J}}$ has a unique element of minimum length. The collection of such representatives, denoted ${\displaystyle ({\widetilde {S}}_{n})^{J}}$, consists of the following affine permutations:[14]

${\displaystyle ({\widetilde {S}}_{n})^{J}=\left\{u\in {\widetilde {S}}_{n}\colon u(i-n+1)

In the particular case that ${\displaystyle J=\{s_{1},\ldots ,s_{n-1}\}}$, so that ${\displaystyle ({\widetilde {S}}_{n})_{J}\cong S_{n}}$ is the standard copy of ${\displaystyle S_{n}}$ inside ${\displaystyle {\widetilde {S}}_{n}}$, the elements of ${\displaystyle ({\widetilde {S}}_{n})^{J}\cong {\widetilde {S}}_{n}/S_{n}}$ may naturally be represented by abacus diagrams: the integers are arranged in an infinite strip of width n, 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 ${\displaystyle 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 ${\displaystyle 5+3+0+1=9}$.)[15]

## Cycle type and reflection length

Any bijection ${\displaystyle u:\mathbb {Z} \to \mathbb {Z} }$ partitions the integers into a (possibly infinite) list of (possibly infinite) cycles: for each integer i, the cycle containing i is the sequence ${\displaystyle (\ldots ,u^{-2}(i),u^{-1}(i),i,u(i),u^{2}(i),\ldots )}$ where exponentiation represents functional composition. For example, the affine permutation in ${\displaystyle {\widetilde {S}}_{4}}$ with window notation ${\displaystyle [5,2,0,3]}$ contains the two infinite cycles ${\displaystyle (\ldots ,-7,-3,1,5,9,\ldots )}$ and ${\displaystyle (\ldots ,8,7,4,3,0,-1,-4,-5\ldots )}$ as well as infinitely many finite cycles ${\displaystyle (4k+2)}$ for each ${\displaystyle 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 ${\displaystyle [1,2,4,3]=(1)(2)(34)}$, the first infinite cycle corresponds to the cycle (1), the second corresponds to the cycle (34), and the finite cycles all correspond to the cycle (2).

For an affine permutation u, the following conditions are equivalent: all cycles of u are finite, u has finite order, and the geometric action of u on the space V has at least one fixed point.[16]

The reflection length ${\displaystyle \ell _{R}(u)}$ of an element u of ${\displaystyle {\widetilde {S}}_{n}}$ is the smallest number k such that there exist reflections ${\displaystyle r_{1},\ldots ,r_{k}}$ such that ${\displaystyle u=r_{1}\cdots r_{k}}$. (In the symmetric group, reflections are transpositions, and the reflection length of a permutation u is ${\displaystyle n-c(u)}$, where ${\displaystyle c(u)}$ is the number of cycles of u.[17]) In (Lewis et al. 2019), the following formula was proved for the reflection length of an affine permutation u: for each cycle of u, define the weight to be the integer k such that consecutive entries congruent modulo n differ by exactly kn. (For example, in the permutation ${\displaystyle [5,2,0,3]}$ 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 u (counting translates of the same cycle by multiples of n only once), and define the nullity ${\displaystyle \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 ${\displaystyle (1,-1,0)}$ and the nullity is 2, since one can take the partition ${\displaystyle (1,-1),(0)}$.) Then the reflection length of u is

${\displaystyle \ell _{R}(u)=n-2\nu (u)+c(\pi (u)),}$
where ${\displaystyle \pi (u)}$ is the underlying permutation of u.[18]

For every affine permutation u, there is a choice of subgroup W of ${\displaystyle {\widetilde {S}}_{n}}$ such that ${\displaystyle W\cong S_{n}}$, ${\displaystyle {\widetilde {S}}_{n}=W\ltimes \Lambda }$, and for the standard form ${\displaystyle u=w\cdot t}$ implied by this semidirect product, one has ${\displaystyle \ell _{R}(u)=\ell _{R}(w)+\ell _{R}(t)}$.[19]

## Bruhat order

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

## Juggling patterns

In (Ehrenborg & Readdy 1996), a bijection is given between affine permutations and juggling patterns encoded in a version of siteswap notation. Under this bijection, the length of the affine permutation is encoded by a natural statistic in the juggling pattern (the number of times pairs of balls "cross" in a certain sense), which allows an elementary proof of the generating function for affine permutations by length. Similar techniques can be used to derive the generating function for minimal coset representatives of ${\displaystyle {\widetilde {S}}_{n}/S_{n}}$ by length.[21]

## Fully commutative elements and pattern avoidance

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

Billey, Jockusch & Stanley (1993) proved that in the finite symmetric group ${\displaystyle 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 (Hanusa & Jones 2010), this result was extended to affine permutations: an affine permutation u is fully commutative if and only if there do not exist integers ${\displaystyle i such that ${\displaystyle u(i)>u(j)>u(k)}$.

It has also been shown that the number of affine permutations avoiding a single pattern p is finite if and only if p avoids the pattern 321.[23]

## 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 ${\displaystyle (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 Q, and in the same right cell if and only if their images have the same tableau P. In (Shi 1986), J.-Y. Shi showed that left cells for ${\displaystyle {\widetilde {S}}_{n}}$ are indexed instead by tabloids[a], and in Shi (1991) he gave an algorithm to compute the tabloid analogous to the tableau P for an affine permutation. In (Chmutov, Pylyavskyy & Yudovina 2018), the authors extended Shi's work to give a bijective map between ${\displaystyle {\widetilde {S}}_{n}}$ and triples ${\displaystyle (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 Viennot (1977).

## Relationship to 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 T of finite order that fixes a hyperplane.[b] In particular, this implies that the vectors orthogonal to the hyperplane are eigenvectors of T, and the associated eigenvalue is a complex root of unity. A complex reflection group is a finite subgroup of a complex vector space generated by reflections.

The complex reflection groups were fully classified by Shephard & Todd (1954): each complex reflection group is isomorphic to a product of irreducible complex reflection groups, and every irreducible either belongs to an infinite family ${\displaystyle G(m,p,n)}$ (where m, p, and n are positive integers such that p divides m) or is one of 34 other (so-called "exceptional") examples. The group ${\displaystyle G(m,1,n)}$ is the generalized symmetric group: algebraically, it is the wreath product ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )\wr S_{n}}$ of the cyclic group ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ with the symmetric group ${\displaystyle 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 mth roots of unity. The groups ${\displaystyle G(m,p,n)}$ are subgroups of ${\displaystyle G(m,1,n)}$, and in particular the group ${\displaystyle G(m,m,n)}$ consists of those matrices in which the product of the nonzero entries is equal to 1.

In (Shi 2002), Shi showed that the affine symmetric group is a generic cover of the family ${\displaystyle \left\{G(m,m,n)\colon m\geq 1\right\}}$, in the following sense: for every positive integer m, there is a surjection ${\displaystyle \pi _{m}}$ from ${\displaystyle {\widetilde {S}}_{n}}$ to ${\displaystyle G(m,m,n)}$, and these maps are compatible with the natural surjections ${\displaystyle G(m,m,n)\twoheadrightarrow G(p,p,n)}$ when ${\displaystyle p\mid m}$ that come from raising each entry to the m/pth power. Moreover, these projections respect the reflection group structure, in that the image of every reflection in ${\displaystyle {\widetilde {S}}_{n}}$ under ${\displaystyle \pi _{m}}$ is a reflection in ${\displaystyle G(m,m,n)}$; and similarly when ${\displaystyle m>1}$ the image of the standard Coxeter element ${\displaystyle s_{0}\cdot s_{1}\cdots s_{n}}$ in ${\displaystyle {\widetilde {S}}_{n}}$ is a Coxeter element in ${\displaystyle G(m,m,n)}$.[24]

## 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 ${\displaystyle \mathbb {Z} \wr S_{n}}$. Its elements are extended affine permutations: bijections ${\displaystyle u\colon \mathbb {Z} \to \mathbb {Z} }$ such that ${\displaystyle u(x+n)=u(x)+n}$ for all integers x. 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 ${\displaystyle {\widetilde {S}}_{n}}$: the shift operator ${\displaystyle \tau }$ whose window notation is ${\displaystyle \tau =[2,3,\ldots ,n,n+1]}$ generates the extended group with the simple reflections, subject to the additional relations ${\displaystyle \tau s_{i}\tau ^{-1}=s_{i+1}}$.[7]

## Notes

1. In a standard Young tableau, entries increase across rows and down columns; in a tabloid, they increase across rows, but there is no column condition.
2. In some sources, unitary reflections are called pseudoreflections.

## References

• Billey, Sara C.; Jockusch, William; Stanley, Richard P. (1993), "Some Combinatorial Properties of Schubert Polynomials", J. Algeb. Comb., 2: 345–374, doi:10.1023/A:1022419800503
• Björner, Anders; Brenti, Francesco (1996), "Affine permutations of type A", Electron. J. Combin., 3 (2): R18, doi:10.37236/1276
• Björner, Anders; Brenti, Francesco (2005), Combinatorics of Coxeter groups, Springer, ISBN 978-3540-442387
• Chmutov, Michael; Pylyavskyy, Pavlo; Yudovina, Elena (2018), "Matrix-ball construction of affine Robinson-Schensted correspondence", Selecta Math. (N.S.), 24 (2): 667–750, doi:10.1007/s00029-018-0402-6
• Clark, Eric; Ehrenborg, Richard (2011), "Excedances of affine permutations", Advances in Applied Mathematics, 46: 175–191, doi:10.1016/j.aam.2009.12.006
• Crites, Andrew (2010), "Enumerating pattern avoidance for affine permutations", Electron. J. Combin., 17 (1): R127, doi:10.37236/399
• Ehrenborg, Richard; Readdy, Margaret (1996), "Juggling and applications to q-analogues", Discrete Math., 157: 107–125, doi:10.1016/S0012-365X(96)83010-X
• Hanusa, Christopher R.H.; Jones, Brant C. (2010), "The enumeration of fully commutative affine permutations", Eur. J. Comb., 31 (5): 1342–1359, doi:10.1016/j.ejc.2009.11.010
• Humphreys, James E. (1990), Reflection groups and Coxeter groups, Cambridge University Press, ISBN 0-521-37510-X
• Lewis, Joel Brewster (2020), A note on the Hurwitz action on reflection factorizations of Coxeter elements in complex reflection groups
• Lewis, Joel Brewster; McCammond, Jon; Petersen, T. Kyle; Schwer, Petra (2019), "Computing reflection length in an affine Coxeter group", Trans. Amer. Math. Soc., 371: 4097–4127, doi:10.1090/tran/7472
• Shephard, G. C.; Todd, J. A. (1954), "Finite unitary reflection groups", Canad. J. Math., 6: 274–304, doi:10.4153/CJM-1954-028-3
• Shi, Jian-Yi (1986), Kazhdan–Lusztig cells of certain affine Weyl groups, Lecture Notes in Mathematics, 1179, Springer, ISBN 3-540-16439-1
• Shi, Jian-Yi (1991), "The generalized Robinson–Schensted algorithm on the affine Weyl group of type An−1", J. Algebra, 139 (2): 364–394, doi:10.1016/0021-8693(91)90300-W
• Shi, Jian-Yi (2002), "Certain imprimitive reflection groups and their generic versions", Trans. Amer. Math. Soc., 354 (5): 2115–2129, doi:10.1090/S0002-9947-02-02941-0
• Stembridge, John (1996), "On the Fully Commutative Elements of Coxeter Groups", J. Alg. Comb., 5: 353–385, doi:10.1007/BF00193185
• Viennot, G. (1977), "Une forme géométrique de la correspondance de Robinson-Schensted", in Foata, Dominique (ed.), Combinatoire et représentation du groupe symétrique, Lecture Notes in Mathematics, 579, Springer, pp. 29–58, doi:10.1007/BFb0090008, ISBN 978-3-540-08143-2