Affine symmetric group

The affine symmetric group is a mathematical structure that describes the symmetries of the number line and the regular triangular tesselation of the plane, as well as related higher-dimensional objects. It is an infinite extension of the symmetric group, which consists of all permutations (rearrangements) of a finite set. In addition to its geometric description, the affine symmetric group may be defined as the collection of permutations 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. These different definitions allow for the extension of many important properties of the finite symmetric group to the infinite setting, and are studied as part of the fields of combinatorics and representation theory.
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.
In terms of generators and relations, the affine symmetric group formula_1 is generated by a set
formula_2
of elements that satisfy the following relations: when formula_3,
In the relations above, indices are taken modulo, so that the third relation includes as a particular case formula_8. (The second and third relation are sometimes called the braid relations.)
When formula_9, the affine symmetric group formula_10 is the infinite dihedral group generated by two elements formula_11 subject only to the relations formula_12.
This definition endows formula_13 with the structure of a Coxeter group, with the formula_14 as Coxeter generating set. For formula_15, its Coxeter–Dynkin diagram is the -cycle, while for formula_9 it consists of two nodes joined by an edge labeled formula_17.
Geometric definition.
In the Euclidean space formula_18 with coordinates formula_19, the set of points that satisfy the equation formula_20 forms a (hyper)plane (an -dimensional subspace). For every pair of distinct elements and of formula_21 and every integer , the set of points in that satisfy formula_22 forms a plane in , and there is a unique reflection of that fixes this plane. Then the affine symmetric group can be realized geometrically as the collection of all maps from to itself that arise by composing several of these reflections.
Inside , the "type A root lattice" is the subset of points with integer coordinates, that is, it is the set of all the integer vectors formula_23 such that formula_24. Each of the reflections preserves this lattice, and so the lattice is preserved by the whole group. In fact, one may define formula_1 to be the group of rigid transformations of that preserve the lattice .
These reflecting planes divide the space into congruent simplicies, called "alcoves". The situation when formula_26 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 , the alcoves are not regular simplices.)
To translate between the geometric and algebraic definitions, fix an alcove and consider the hyperplanes that form its boundary. For example, there is a unique alcove (the "fundamental alcove") consisting of points formula_19 such that formula_28, which is bounded by the hyperplanes formula_29, formula_30, ..., and formula_31. (This is illustrated in the case formula_26 at right.) For formula_33, one may identify the reflection through formula_34 with the Coxeter generator formula_14, and also identify the reflection through formula_31 with the generator formula_37.
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 formula_38 is an "affine permutation" if formula_39 for all integers and formula_40. (It is a consequence of the first property that the numbers formula_41 must all be distinct modulo .) Such a function is uniquely determined by its "window notation" formula_42, and so affine permutations may also be identified with tuples formula_42 of integers that contain one element from each congruence class modulo and sum to formula_44.
To translate between the combinatorial and algebraic definitions, for formula_33 one may identify the Coxeter generator formula_14 with the affine permutation that has window notation formula_47, and also identify the generator formula_37 with the affine permutation formula_49. More generally, every reflection (that is, a conjugate of one of the Coxeter generators) can be described uniquely as follows: for distinct integers , in formula_21 and arbitrary integer , it maps to , maps to , and fixes all inputs not congruent to or modulo . (In terms of the geometric definition, this corresponds to the reflection across the plane formula_51. 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. If formula_52 is an affine permutation, one places the entry 1 at position formula_53 in the infinite grid formula_54 for each integer , and all other entries are equal to 0. Since is a bijection, the resulting matrix contains exactly one 1 in every row and column. The periodicity condition on the map ensures that the entry at position formula_55 is equal to the entry at position formula_56 for every pair of integers formula_55. For example, a portion of matrix for the affine permutation formula_58 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:
formula_59
Relationship to the finite symmetric group.
The affine symmetric group formula_1 contains the finite symmetric group formula_61 as both a subgroup and a quotient.
As a subgroup.
There is a canonical way to choose a subgroup of formula_1 that is isomorphic to the finite symmetric group formula_61.
In terms of the algebraic definition, this is the subgroup of formula_1 generated by formula_65 (excluding the simple reflection formula_66). Geometrically, this corresponds to the subgroup of transformations that fix the origin, while combinatorially it corresponds to the window notations for which formula_67 (that is, in which the window notation is the one-line notation of a finite permutation).
If formula_68 is the window notation of an element of this standard copy of formula_69, its action on the hyperplane in formula_70 is given by permutation of coordinates: formula_71. (In this article, the geometric action of permutations and affine permutations is on the right; thus, if and are two affine permutations, the action of on a point is given by first applying , then applying .)
There are also many nonstandard copies of formula_61 contained in formula_1. A geometric construction is to pick any point in (that is, an integer vector whose coordinates sum to 0); the subgroup formula_74 of formula_1 of isometries that fix is isomorphic to formula_61. The analogous combinatorial construction is to choose any subset of formula_77 that contains one element from each conjugacy class modulo and whose elements sum to formula_44; the subgroup formula_79 of formula_1 of affine permutations that stabilize is isomorphic to formula_61.
As a quotient.
There is a simple map (technically, a surjective group homomorphism) from formula_1 onto the finite symmetric group formula_61. In terms of the combinatorial definition, it is to reduce the window entries modulo to elements of formula_84, leaving the one-line notation of a permutation. The image formula_85 of an affine permutation is called the "underlying permutation" of .
The map sends the Coxeter generator formula_86 to the permutation whose one-line notation and cycle notation are formula_87 and formula_88, respectively. In terms of the Coxeter generators of formula_61, this can be written as formula_90.
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 formula_91, where formula_92 is an integer vector such that formula_93, that is, where formula_94. Geometrically, this kernel consists of the translations, that is, the isometries that shift the entire space 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 , 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 vectors formula_95.
Connection between the geometric and combinatorial definitions.
The subgroup is a normal subgroup of formula_1, and one has an isomorphism
formula_97
between formula_1 and the semidirect product of the finite symmetric group formula_61 with , where the action of formula_61 on is by permutation of coordinates. Consequently, identifying the finite symmetric group formula_61 as its standard copy in formula_1, one has that every element of formula_1 may be realized uniquely as a product 
formula_104 where formula_105 is a finite permutation and formula_106.
This point of view allows for a direct translation between the combinatorial and geometric definitions of formula_1: if one writes formula_108 where formula_109 and formula_110 then the affine permutation corresponds to the rigid motion of defined by 
formula_111
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 formula_112, one may place the group in one-to-one correspondence with the alcoves: the identity element corresponds to formula_112, and every other group element corresponds to the alcove formula_114 that is the image of formula_112 under the action of . This identification for formula_116 is illustrated at right.
Example:.
Algebraically, formula_10 is the infinite dihedral group, generated by two generators formula_11 subject to the relations formula_12. Every other element of the group can be written as an alternating product of copies of formula_120 and formula_121.
Combinatorially, the affine permutation formula_121 has window notation formula_123, corresponding to the bijection formula_124 for every integer . The affine permutation formula_120 has window notation formula_126, corresponding to the bijection formula_127 for every integer . Other elements have the following window notations:
Geometrically, the space is the line with equation formula_132 in the Euclidean plane formula_133. The root lattice inside consists of those pairs formula_134 for integral . The Coxeter generator formula_121 acts on by reflection across the line formula_136 (that is, across the origin); the generator formula_120 acts on by reflection across the line formula_138 (that is, across the point formula_139. It is natural to identify the line with the real line formula_140, by sending the point formula_141 to the real number . With this identification, the root lattice consists of the even integers; the fundamental alcove is the interval ; the element formula_142 acts by translation by for any integer ; and the reflection formula_143 reflects across the point for any integer .
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" formula_144 of an element of a Coxeter group is the smallest number such that can be written as a product formula_145 of Coxeter generators of .
Geometrically, the length of an element in formula_1 is the number of reflecting hyperplanes that separate formula_112 and formula_148, where formula_112 is the fundamental alcove (the simplex bounded by the reflecting hyperplanes of the Coxeter generators formula_150). (In fact, the same is true for any affine Coxeter group.)
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 that
formula_151
Alternatively, it is the number of equivalence classes of pairs formula_152 such that formula_153 and formula_154 under the equivalence relation formula_155 if formula_156 for some integer .
The generating function for length in formula_1 is
formula_158
Similarly, one may define an affine analogue of descents in permutations: say that an affine permutation has a descent in position if formula_159. (By periodicity, has a descent in position if and only if it has a descent in position formula_160 for all integers .)
Algebraically, the descents corresponds to the "right descents" in the sense of Coxeter groups; that is, is a descent of if and only if formula_161. The left descents (that is, those indices such that formula_162 are the descents of the inverse affine permutation formula_163; equivalently, they are the values such that occurs before in the sequence formula_164.
Geometrically, is a descent of if and only if the fixed hyperplane of formula_14 separates the alcoves formula_112 and formula_167.
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). One possible resolution is to consider affine descents (equivalently, cyclic descents) in the finite symmetric group formula_61. Another is to consider simultaneously the length and number of descents of an affine permutation. The generating function for these statistics over formula_1 simultaneously for all is
formula_170
where is the number of descents of the affine permutation and formula_171 is the -exponential function.
Cycle type and reflection length.
Any bijection formula_52 partitions the integers into a (possibly infinite) list of (possibly infinite) cycles: for each integer , the cycle containing is the sequence formula_173 where exponentiation represents functional composition. For example, the affine permutation in formula_174 with window notation formula_175 contains the two infinite cycles
formula_176 and 
formula_177
as well as infinitely many finite cycles formula_178 for each formula_179. Cycles of an affine permutation correspond to cycles of the underlying permutation in an obvious way: in the example above, with underlying permutation formula_180, 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 , the following conditions are equivalent: all cycles of are finite, has finite order, and the geometric action of on the space has at least one fixed point.
The "reflection length" formula_181 of an element of formula_1 is the smallest number such that there exist reflections formula_183 such that formula_184. (In the symmetric group, reflections are transpositions, and the reflection length of a permutation is formula_185, where formula_186 is the number of cycles of .) In , the following formula was proved for the reflection length of an affine permutation : for each cycle of , define the "weight" to be the integer "k" such that consecutive entries congruent modulo differ by exactly . (For example, in the permutation formula_187 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 (counting translates of the same cycle by multiples of only once), and define the "nullity" formula_188 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 formula_189 and the nullity is 2, since one can take the partition formula_190.) Then the reflection length of is 
formula_191
where formula_85 is the underlying permutation of .
For every affine permutation , there is a choice of subgroup of formula_1 such that formula_194, formula_195, and for the standard form formula_196 implied by this semidirect product, one has formula_197.
Fully commutative elements and pattern avoidance.
A "reduced word" for an element of a Coxeter group is a tuple formula_198 of Coxeter generators of minimum possible length such that formula_199. The element is called "fully commutative" if one can transform any reduced word into any other by sequentially swapping pairs of factors that commute. For example, in the finite symmetric group formula_200, the element formula_201 is fully commutative, since its two reduced words formula_202 and formula_203 can be connected by swapping commuting factors, but formula_204 is not fully commutative because there is no way to reach the reduced word formula_205 starting from the reduced word formula_206 by commutations.
 proved that in the finite symmetric group formula_61, 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 , this result was extended to affine permutations: an affine permutation is fully commutative if and only if there do not exist integers formula_208 such that formula_209.
It has also been shown that the number of affine permutations avoiding a single pattern is finite if and only if avoids the pattern 321, so in particular there are infinitely many fully commutative affine permutations. These were enumerated by length in .
Parabolic subgroups and other structures.
The parabolic subgroups of formula_1 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.
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 formula_1, all maximal parabolic subgroups are isomorphic to the finite symmetric group formula_61. The subgroup generated by the subset formula_213 consists of those affine permutations that stabilize the interval formula_214, that is, that map every element of this interval to another element of the interval.
The non-maximal parabolic subgroups of formula_1 are all isomorphic to parabolic subgroups of formula_61, that is, to a Young subgroup formula_217 for some positive integers formula_218 with sum .
For a fixed element of formula_219, let formula_220 be the maximal proper subset of Coxeter generators omitting formula_14, and let formula_222 denote the parabolic subgroup generated by . Every coset formula_223 has a unique element of minimum length. The collection of such representatives, denoted formula_224, consists of the following affine permutations:
formula_225
In the particular case that formula_226, so that formula_227 is the standard copy of formula_61 inside formula_1, the elements of formula_230 may naturally be represented by "abacus diagrams": the integers are arranged in an infinite strip of width , 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 formula_231 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 formula_232.)
Other combinatorial models of minimum-length coset representatives for formula_233 can be given in terms of core partitions (integer partitions in which no hook length is divisible by ) or bounded partitions (integer partitions in which no part is larger than ). Under these correspondences, it can be shown that the weak Bruhat order on formula_234 is isomorphic to a certain subposet of Young's lattice.
Bruhat order.
The Bruhat order on formula_1 has the following combinatorial realization. If is an affine permutation and and are integers, define
formula_236
to be the number of integers such that formula_237 and formula_238. (For example, with formula_239, one has formula_240: the three relevant values are formula_241, which are respectively mapped by to 1, 2, and 4.) Then for two affine permutations , , one has that formula_242 in Bruhat order if and only if formula_243 for all integers , .
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 formula_244 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 , and in the same right cell if and only if their images have the same tableau . In , J.-Y. Shi showed that left cells for formula_1 are indexed instead by "tabloids", and in he gave an algorithm to compute the tabloid analogous to the tableau for an affine permutation. In , the authors extended Shi's work to give a bijective map between formula_1 and triples formula_247 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 .
Inverse realizations.
In some situations, one may wish to consider the action of the affine symmetric group on formula_248 or on alcoves that is inverse to the one given above. We describe these alternate realizations now.
In the combinatorial action of formula_1 on formula_248, the generator formula_14 acts by switching the "values" and . In the inverse action, it instead switches the entries in "positions" and . Similarly, the action of a general reflection will be to switch the entries at "positions" and for each , fixing all inputs at positions not congruent to or modulo . (In the finite symmetric group formula_61, the analogous distinction is between the "active" and "passive" forms of a permutation.)
In the geometric action of formula_1, the generator formula_14 acts on an alcove by reflecting it across one of the bounding planes of the fundamental alcove . In the inverse action, it instead reflects across one of "its own" bounding planes. From this perspective, a reduced word corresponds to an "alcove walk" on the tesselated space .
Relationship to other mathematical objects.
The affine symmetric group is closely related to a variety of other mathematical objects.
Juggling patterns.
In , a correspondence is given between affine permutations and juggling patterns encoded in a version of siteswap notation. Here, a juggling pattern of period is a sequence formula_23 of nonnegative integers (with certain restrictions) that captures the behavior of balls thrown by a juggler, where the number formula_256 indicates the length of time the th throw spends in the air (equivalently, the height of the throw). The number of balls in the pattern is the average formula_257. The Ehrenborg–Readdy correspondence associates to each juggling pattern formula_258 of period the function formula_259 defined by
formula_260
where indices of the sequence a are taken modulo . Then formula_261 is an affine permutation in formula_1, and moreover every affine permutation arises from a juggling pattern in this way. Under this bijection, the length of the affine permutation is encoded by a natural statistic in the juggling pattern: one has
formula_263
where formula_264 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.
For example, the juggling pattern 441 (illustrated at right) has formula_26 and formula_266. Therefore, it corresponds to the affine permutation formula_267. The juggling pattern has four crossings, and the affine permutation has length formula_268.
Similar techniques can be used to derive the generating function for minimal coset representatives of formula_233 by length.
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 of finite order that fixes a hyperplane. This implies that the vectors orthogonal to the hyperplane are eigenvectors of , 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 : each complex reflection group is isomorphic to a product of irreducible complex reflection groups, and every irreducible either belongs to an infinite family formula_270 (where , , and are positive integers such that divides ) or is one of 34 other (so-called "exceptional") examples. The group formula_271 is the generalized symmetric group: algebraically, it is the wreath product formula_272 of the cyclic group formula_273 with the symmetric group formula_61. 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 th roots of unity. The groups formula_270 are subgroups of formula_271, and in particular the group formula_277 consists of those matrices in which the product of the nonzero entries is equal to 1.
In , Shi showed that the affine symmetric group is a "generic cover" of the family formula_278, in the following sense: for every positive integer , there is a surjection formula_279 from formula_1 to formula_277, and these maps are compatible with the natural surjections formula_282 when formula_283 that come from raising each entry to the th power. Moreover, these projections respect the reflection group structure, in that the image of every reflection in formula_1 under formula_279 is a reflection in formula_277; and similarly when formula_287 the image of the standard Coxeter element formula_288 in formula_1 is a Coxeter element in formula_290.
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). In the classification of affine Lie algebras, the one associated to formula_1 is of (untwisted) type formula_292, with Cartan matrix formula_293 for formula_294 and
formula_295
(a circulant matrix) for formula_296.
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. 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 formula_297, associated to the affine symmetric group formula_10, the corresponding Macdonald identity is equivalent to the Jacobi triple product.
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 formula_299. Its elements are "extended affine permutations": bijections formula_38 such that formula_39 for all integers . 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 formula_1: the "shift operator" formula_303 whose window notation is formula_304 generates the extended group with the simple reflections, subject to the additional relations formula_305.
Combinatorics of other affine Coxeter groups.
The geometric action of the affine symmetric group formula_1 places it naturally in the family of affine Coxeter groups, all of which have a similar geometric action. The combinatorial description of the formula_1 may also be extended to many of these groups: in , an axiomatic description is given of certain permutation groups acting on formula_248 (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. Abacus models of minimum-length coset representatives for parabolic quotients have also been extended to this context.