The affine symmetric groups are a family of mathematical structures that describe the symmetries of the number line and the regular triangular tiling of the plane, as well as related higher-dimensional objects. In addition to this geometric description, the affine symmetric groups may be defined in other ways: as collections of permutations (rearrangements) of the integers (..., −2, −1, 0, 1, 2, ...) that are periodic in a certain sense, or in purely algebraic terms as a group with certain generators and relations. They are studied in combinatorics and representation theory. A finite symmetric group consists of all permutations of a finite set. Each affine symmetric group is an infinite extension of a finite symmetric group. Many important combinatorial properties of the finite symmetric groups can be extended to the corresponding affine symmetric groups. Permutation statistics such as descents and inversions can be defined in the affine case. As in the finite case, the natural combinatorial definitions for these statistics also have a geometric interpretation. The affine symmetric groups have close relationships with other mathematical objects, including juggling patterns and certain complex reflection groups. Many of their combinatorial and geometric properties extend to the broader family of affine Coxeter groups.
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
One way of defining groups is by generators and relations. In this type of definition, generators are a subset of group elements that, when combined, produce all other elements. The relations of the definition are a system of equations that determine when two combinations of generators are equal. In this way, the affine symmetric group S ~ n {\displaystyle {\widetilde {S}}_{n}} is generated by a set
s 0 , s 1 , … , s n − 1 {\displaystyle s_{0},s_{1},\ldots ,s_{n-1}}
of n elements that satisfy the following relations: when n ≥ 3 {\displaystyle n\geq 3} ,
s i 2 = 1 {\displaystyle s_{i}^{2}=1} (the generators are involutions),
s i s j = s j s i {\displaystyle s_{i}s_{j}=s_{j}s_{i}} if j is not one of i − 1 , i , i + 1 {\displaystyle i-1,i,i+1} , indicating that for these pairs of generators, the group operation is commutative, and
s i s i + 1 s i = s i + 1 s i s i + 1 {\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 s 0 s n − 1 s 0 = s n − 1 s 0 s n − 1 {\displaystyle 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 {\displaystyle n=2} , the affine symmetric group S ~ 2 {\displaystyle {\widetilde {S}}_{2}} is the infinite dihedral group generated by two elements s 0 , s 1 {\displaystyle s_{0},s_{1}} subject only to the relations s 0 2 = s 1 2 = 1 {\displaystyle s_{0}^{2}=s_{1}^{2}=1} . These relations can be rewritten in the special form that defines the Coxeter groups, so the affine symmetric groups are Coxeter groups, with the s i {\displaystyle s_{i}} as their Coxeter generating sets. Each Coxeter group may be represented by a Coxeter–Dynkin diagram, in which vertices correspond to generators and edges encode the relations between them. For n ≥ 3 {\displaystyle n\geq 3} , the Coxeter–Dynkin diagram of S ~ n {\displaystyle {\widetilde {S}}_{n}} is the n-cycle (where the edges correspond to the relations between pairs of consecutive generators and the absence of an edge between other pairs of generators indicates that they commute), while for n = 2 {\displaystyle n=2} it consists of two nodes joined by an edge labeled ∞ {\displaystyle \infty } .
Geometric definition
In the Euclidean space R n {\displaystyle \mathbb {R} ^{n}} with coordinates ( x 1 , … , x n ) {\displaystyle (x_{1},\ldots ,x_{n})} , the set V of points for which x 1 + x 2 + ⋯ + x n = 0 {\displaystyle x_{1}+x_{2}+\cdots +x_{n}=0} forms a (hyper)plane, an (n − 1)-dimensional subspace. For every pair of distinct elements i and j of { 1 , … , n } {\displaystyle \{1,\ldots ,n\}} and every integer k, the set of points in V that satisfy x i − x j = k {\displaystyle x_{i}-x_{j}=k} forms an (n − 2)-dimensional subspace within V, and there is a unique reflection of V that fixes this subspace. Then the affine symmetric group S ~ n {\displaystyle {\widetilde {S}}_{n}} can be realized geometrically as a collection of maps from V to itself, the compositions of these reflections. Inside V, the subset of points with integer coordinates forms the root lattice, Λ. It is the set of all the integer vectors ( a 1 , … , a n ) {\displaystyle (a_{1},\ldots ,a_{n})} such that a 1 + ⋯ + a n = 0 {\displaystyle a_{1}+\cdots +a_{n}=0} . Each reflection preserves this lattice, and so the lattice is preserved by the whole group. The fixed subspaces of these reflections divide V into congruent simplices, called alcoves. The situation when n = 3 {\displaystyle n=3} is shown in the figure; in this case, the root lattice is a triangular lattice, the reflecting lines divide V into equilateral triangle alcoves, and the roots are the centers of nonoverlapping hexagons made up of six triangular alcoves.
To translate between the geometric and algebraic definitions, one fixes an alcove and consider the n hyperplanes that form its boundary. The reflections through these boundary hyperplanes may be identified with the Coxeter generators. In particular, there is a unique alcove (the fundamental alcove) consisting of points ( x 1 , … , x n ) {\displaystyle (x_{1},\ldots ,x_{n})} such that x 1 ≥ x 2 ≥ ⋯ ≥ x n ≥ x 1 − 1 {\displaystyle x_{1}\geq x_{2}\geq \cdots \geq x_{n}\geq x_{1}-1} , which is bounded by the hyperplanes x 1 − x 2 = 0 , {\displaystyle x_{1}-x_{2}=0,} x 2 − x 3 = 0 , {\displaystyle x_{2}-x_{3}=0,} ..., and x 1 − x n = 1 , {\displaystyle x_{1}-x_{n}=1,} illustrated in the case n = 3 {\displaystyle n=3} . For i = 1 , … , n − 1 {\displaystyle i=1,\ldots ,n-1} , one may identify the reflection through x i − x i + 1 = 0 {\displaystyle x_{i}-x_{i+1}=0} with the Coxeter generator s i {\displaystyle s_{i}} , and also identify the reflection through x 1 − x n = 1 {\displaystyle x_{1}-x_{n}=1} with the generator s 0 = s n {\displaystyle s_{0}=s_{n}} .
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 function u : Z → Z {\displaystyle u\colon \mathbb {Z} \to \mathbb {Z} } is an affine permutation if
it is a bijection (each integer appears as the value of u ( x ) {\displaystyle u(x)} for exactly one x {\displaystyle x} ),
u ( x + n ) = u ( x ) + n {\displaystyle u(x+n)=u(x)+n} for all integers x (the function is equivariant under shifting by n {\displaystyle n} ), and
u ( 1 ) + u ( 2 ) + ⋯ + u ( n ) = 1 + 2 + ⋯ + n = n ( n + 1 ) 2 {\displaystyle u(1)+u(2)+\cdots +u(n)=1+2+\cdots +n={\frac {n(n+1)}{2}}} , the n {\displaystyle n} th triangular number. For every affine permutation, and more generally every shift-equivariant bijection, the numbers u ( 1 ) , … , u ( n ) {\displaystyle u(1),\ldots ,u(n)} must all be distinct modulo n. An affine permutation is uniquely determined by its window notation [ u ( 1 ) , … , u ( n ) ] {\displaystyle [u(1),\ldots ,u(n)]} , because all other values of u {\displaystyle u} can be found by shifting these values. Thus, affine permutations may also be identified with tuples [ u ( 1 ) , … , u ( n ) ] {\displaystyle [u(1),\ldots ,u(n)]} of integers that contain one element from each congruence class modulo n and sum to 1 + 2 + ⋯ + n {\displaystyle 1+2+\cdots +n} . To translate between the combinatorial and algebraic definitions, for i = 1 , … , n − 1 {\displaystyle i=1,\ldots ,n-1} one may identify the Coxeter generator s i {\displaystyle s_{i}} with the affine permutation that has window notation [ 1 , 2 , … , i − 1 , i + 1 , i , i + 2 , … , n ] {\displaystyle [1,2,\ldots ,i-1,i+1,i,i+2,\ldots ,n]} , and also identify the generator s 0 = s n {\displaystyle s_{0}=s_{n}} with the affine permutation [ 0 , 2 , 3 , … , n − 2 , n − 1 , n + 1 ] {\displaystyle [0,2,3,\ldots ,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 i, j in { 1 , … , n } {\displaystyle \{1,\ldots ,n\}} and arbitrary integer k, it maps i to j − kn, maps j to i + kn, and fixes all inputs not congruent to i or j modulo n.
Representation as matrices
Affine permutations can be represented as infinite periodic permutation matrices. If u : Z → Z {\displaystyle u:\mathbb {Z} \to \mathbb {Z} } is an affine permutation, the corresponding matrix has entry 1 at position ( i , u ( i ) ) {\displaystyle (i,u(i))} in the infinite grid Z × Z {\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 ( a , b ) {\displaystyle (a,b)} is equal to the entry at position ( a + n , b + n ) {\displaystyle (a+n,b+n)} for every pair of integers ( a , b ) {\displaystyle (a,b)} . For example, a portion of the matrix for the affine permutation [ 2 , 0 , 4 ] ∈ S ~ 3 {\displaystyle [2,0,4]\in {\widetilde {S}}_{3}} is shown in the figure. In row 1, there is a 1 in column 2; in row 2, there is a 1 in column 0; and in row 3, there is a 1 in column 4. The rest of the entries in those rows and columns are all 0, and all the other entries in the matrix are fixed by the periodicity condition.
Relationship to the finite symmetric group The affine symmetric group S ~ n {\displaystyle {\widetilde {S}}_{n}} contains the finite symmetric group S n {\displaystyle S_{n}} of permutations on n {\displaystyle n} elements as both a subgroup and a quotient group. These connections allow a direct translation between the combinatorial and geometric definitions of the affine symmetric group.
As a subgroup There is a canonical way to choose a subgroup of S ~ n {\displaystyle {\widetilde {S}}_{n}} that is isomorphic to the finite symmetric group S n {\displaystyle S_{n}} . In terms of the algebraic definition, this is the subgroup of S ~ n {\displaystyle {\widetilde {S}}_{n}} generated by s 1 , … , s n − 1 {\displaystyle s_{1},\ldots ,s_{n-1}} (excluding the simple reflection s 0 = s n {\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 { u ( 1 ) , … , u ( n ) } = { 1 , 2 , … , n } {\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). If u = [ u ( 1 ) , u ( 2 ) , … , u ( n ) ] {\displaystyle u=[u(1),u(2),\ldots ,u(n)]} is the window notation of an element of this standard copy of S n ⊂ S ~ n {\displaystyle S_{n}\subset {\widetilde {S}}_{n}} , its action on the hyperplane V in R n {\displaystyle \mathbb {R} ^{n}} is given by permutation of coordinates: ( x 1 , x 2 , … , x n ) ⋅ u = ( x u ( 1 ) , x u ( 2 ) , … , x u ( n ) ) {\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 S n {\displaystyle S_{n}} contained in S ~ n {\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 ( S ~ n ) a {\displaystyle ({\widetilde {S}}_{n})_{a}} of S ~ n {\displaystyle {\widetilde {S}}_{n}} of isometries that fix a is isomorphic to S n {\displaystyle S_{n}} .
As a quotient There is a simple map (technically, a surjective group homomorphism) π from S ~ n {\displaystyle {\widetilde {S}}_{n}} onto the finite symmetric group S n {\displaystyle S_{n}} . In terms of the combinatorial definition, an affine permutation can be mapped to a permutation by reducing the window entries modulo n to elements of { 1 , 2 , … , n } {\displaystyle \{1,2,\ldots ,n\}} , leaving the one-line notation of a permutation. In this article, the image π ( u ) {\displaystyle \pi (u)} of an affine permutation u is called the underlying permutation of u. The map π sends the Coxeter generator s 0 = [ 0 , 2 , 3 , 4 , … , n − 2 , n − 1 , n + 1 ] {\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 [ n , 2 , 3 , 4 , … , n − 2 , n − 1 , 1 ] {\displaystyle [n,2,3,4,\ldots ,n-2,n-1,1]} and ( 1 n ) {\displaystyle (1\;n)} , respectively. The kernel of π is by definition 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 ⋅ n , 2 − a 2 ⋅ n , … , n − a n ⋅ n ] {\displaystyle [1-a_{1}\cdot n,2-a_{2}\cdot n,\ldots ,n-a_{n}\cdot n]} , where ( a 1 , a 2 , … , a n ) {\displaystyle (a_{1},a_{2},\ldots ,a_{n})} is an integer vector such that a 1 + a 2 + … + a n = 0 {\displaystyle a_{1}+a_{2}+\ldots +a_{n}=0} , that is, where ( a 1 , … , a n ) ∈ Λ {\displaystyle (a_{1},\ldots ,a_{n})\in \Lambda } . Geometrically, this kernel consists of the translations, 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, generated freely by the n − 1 vectors { ( 1 , − 1 , 0 , … , 0 ) , ( 0 , 1 , − 1 , … , 0 ) , … , ( 0 , … , 0 , 1 , − 1 ) } {\displaystyle \{(1,-1,0,\ldots ,0),(0,1,-1,\ldots ,0),\ldots ,(0,\ldots ,0,1,-1)\}} .
Connection between the geometric and combinatorial definitions
The affine symmetric group S ~ n {\displaystyle {\widetilde {S}}_{n}} has Λ as a normal subgroup, and is isomorphic to the semidirect product
S ~ n ≅ S n ⋉ Λ {\displaystyle {\widetilde {S}}_{n}\cong S_{n}\ltimes \Lambda }
of this subgroup with the finite symmetric group S n {\displaystyle S_{n}} , where the action of S n {\displaystyle S_{n}} on Λ is by permutation of coordinates. Consequently, every element u of S ~ n {\displaystyle {\widetilde {S}}_{n}} has a unique realization as a product
u = r ⋅ t {\displaystyle u=r\cdot t} where r {\displaystyle r} is a permutation in the standard copy of S n {\displaystyle S_{n}} in S ~ n {\displaystyle {\widetilde {S}}_{n}} and t {\displaystyle t} is a translation in Λ. This point of view allows for a direct translation between the combinatorial and geometric definitions of S ~ n {\displaystyle {\widetilde {S}}_{n}} : if one writes [ u ( 1 ) , … , u ( n ) ] = [ r 1 − a 1 ⋅ n , … , r n − a n ⋅ n ] {\displaystyle [u(1),\ldots ,u(n)]=[r_{1}-a_{1}\cdot n,\ldots ,r_{n}-a_{n}\cdot n]} where r = [ r 1 , … , r n ] = π ( u ) {\displaystyle r=[r_{1},\ldots ,r_{n}]=\pi (u)} and ( a 1 , a 2 , … , a n ) ∈ Λ {\displaystyle (a_{1},a_{2},\ldots ,a_{n})\in \Lambda } then the affine permutation u corresponds to the rigid motion of V defined by
( x 1 , … , x n ) ⋅ u = ( x r ( 1 ) + a 1 , … , x r ( n ) + a n ) . {\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: for each two alcoves, a unique group element takes one alcove to the other. Hence, making an arbitrary choice of alcove A 0 {\displaystyle A_{0}} places the group in one-to-one correspondence with the alcoves: the identity element corresponds to A 0 {\displaystyle A_{0}} , and every other group element g corresponds to the alcove A = A 0 ⋅ g {\displaystyle A=A_{0}\cdot g} that is the image of A 0 {\displaystyle A_{0}} under the action of g.
Example: n = 2
Algebraically, S ~ 2 {\displaystyle {\widetilde {S}}_{2}} is the infinite dihedral group, generated by two generators s 0 , s 1 {\displaystyle s_{0},s_{1}} subject to the relations s 0 2 = s 1 2 = 1 {\displaystyle 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 {\displaystyle s_{0}} and s 1 {\displaystyle s_{1}} . Combinatorially, the affine permutation s 1 {\displaystyle s_{1}} has window notation [ 2 , 1 ] {\displaystyle [2,1]} , corresponding to the bijection 2 k ↦ 2 k − 1 , 2 k − 1 ↦ 2 k {\displaystyle 2k\mapsto 2k-1,2k-1\mapsto 2k} for every integer k. The affine permutation s 0 {\displaystyle s_{0}} has window notation [ 0 , 3 ] {\displaystyle [0,3]} , corresponding to the bijection 2 k ↦ 2 k + 1 , 2 k + 1 ↦ 2 k {\displaystyle 2k\mapsto 2k+1,2k+1\mapsto 2k} for every integer k. Other elements have the following window notations:
s 0 s 1 ⋯ s 0 s 1 ⏞ 2 k factors = [ 1 + 2 k , 2 − 2 k ] , s 1 s