Affine symmetric group
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 of the integers 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 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 is generated by a setof elements that satisfy the following relations: when,
- ,
- if is not one of, indicating that for these pairs of generators, the group operation is commutative, and
- .
These relations can be rewritten in the special form that defines the Coxeter groups, so the affine symmetric groups are Coxeter groups, with the 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, the Coxeter–Dynkin diagram of is the -cycle, while for it consists of two nodes joined by an edge labeled.
Geometric definition
In the Euclidean space with coordinates, the set of points for which forms a (hyper)plane, an -dimensional subspace. For every pair of distinct elements and of and every integer, the set of points in that satisfy forms an -dimensional subspace within, and there is a unique reflection of that fixes this subspace. Then the affine symmetric group can be realized geometrically as a collection of maps from to itself, the compositions of these reflections.Inside, the subset of points with integer coordinates forms the root lattice,. It is the set of all the integer vectors such that. Each reflection preserves this lattice, and so the lattice is preserved by the whole group.
The fixed subspaces of these reflections divide into congruent simplices, called alcoves. The situation when is shown in the figure; in this case, the root lattice is a triangular lattice, the reflecting lines divide 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 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 consisting of points such that, which is bounded by the hyperplanes ..., and illustrated in the case. For, one may identify the reflection through with the Coxeter generator, and also identify the reflection through with the generator.
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 is an affine permutation if- it is a bijection,
- for all integers, and
- , the th triangular number.
To translate between the combinatorial and algebraic definitions, for one may identify the Coxeter generator with the affine permutation that has window notation, and also identify the generator with the affine permutation. More generally, every reflection can be described uniquely as follows: for distinct integers, in and arbitrary integer, it maps to, maps to, and fixes all inputs not congruent to or modulo.
Representation as matrices
Affine permutations can be represented as infinite periodic permutation matrices. If is an affine permutation, the corresponding matrix has entry 1 at position in the infinite grid 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 is equal to the entry at position for every pair of integers. For example, a portion of the matrix for the affine permutation 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 contains the finite symmetric group of permutations on 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 that is isomorphic to the finite symmetric group.In terms of the algebraic definition, this is the subgroup of generated by . Geometrically, this corresponds to the subgroup of transformations that fix the origin, while combinatorially it corresponds to the window notations for which .
If is the window notation of an element of this standard copy of, its action on the hyperplane in is given by permutation of coordinates:.
There are also many nonstandard copies of contained in. A geometric construction is to pick any point in ; the subgroup of of isometries that fix is isomorphic to.
As a quotient
There is a simple map from onto the finite symmetric group. In terms of the combinatorial definition, an affine permutation can be mapped to a permutation by reducing the window entries modulo to elements of, leaving the one-line notation of a permutation. In this article, the image of an affine permutation is called the underlying permutation of.The map sends the Coxeter generator to the permutation whose one-line notation and cycle notation are and, 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, where is an integer vector such that, that is, where. Geometrically, this kernel consists of the translations, 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 ; in all three settings, the natural group operation turns into an abelian group, generated freely by the vectors.
Connection between the geometric and combinatorial definitions
The affine symmetric group has as a normal subgroup, and is isomorphic to the semidirect productof this subgroup with the finite symmetric group, where the action of on is by permutation of coordinates. Consequently, every element of has a unique realization as a product
where is a permutation in the standard copy of in and is a translation in.
This point of view allows for a direct translation between the combinatorial and geometric definitions of : if one writes where and then the affine permutation corresponds to the rigid motion of defined by
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 places the group in one-to-one correspondence with the alcoves: the identity element corresponds to, and every other group element corresponds to the alcove that is the image of under the action of.
Example:
Algebraically, is the infinite dihedral group, generated by two generators subject to the relations. Every other element of the group can be written as an alternating product of copies of and.Combinatorially, the affine permutation has window notation, corresponding to the bijection for every integer. The affine permutation has window notation, corresponding to the bijection for every integer. Other elements have the following window notations:
Geometrically, the space on which acts is a line, with infinitely many equally spaced reflections. It is natural to identify the line with the real line, with reflection around the point, and with reflection around the point. In this case, the reflection reflects across the point for any integer, the composition translates the line by, and the composition translates the line by.
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 of an element of a Coxeter group is the smallest number such that can be written as a product of Coxeter generators of.Geometrically, the length of an element in is the number of reflecting hyperplanes that separate and, where is the fundamental alcove.
Combinatorially, the length of an affine permutation is encoded in terms of an appropriate notion of inversions: for an affine permutation, the length is
Alternatively, it is the number of equivalence classes of pairs such that and under the equivalence relation if for some integer.
The generating function for length in is
Similarly, there is an affine analogue of descents in permutations: an affine permutation has a descent in position if.
Algebraically, the descents corresponds to the right descents in the sense of Coxeter groups; that is, is a descent of if and only if. The left descents are the descents of the inverse affine permutation ; equivalently, they are the values such that occurs before in the sequence.
Geometrically, is a descent of if and only if the fixed hyperplane of separates the alcoves and
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. One possible resolution is to consider affine descents in the finite symmetric group. Another is to consider simultaneously the length and number of descents of an affine permutation. The multivariate generating function for these statistics over simultaneously for all is
where is the number of descents of the affine permutation and is the -exponential function.
Cycle type and reflection length
Any bijection partitions the integers into a list of cycles: for each integer, the cycle containing is the sequence where exponentiation represents functional composition.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 of an element of is the smallest number such that there exist reflections such that. 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. Form a tuple of cycle weights of, and define the nullity to be the size of the smallest set partition of this tuple so that each part sums to 0. Then the reflection length of is
where is the underlying permutation of.
For every affine permutation, there is a choice of subgroup of such that,, and for the standard form implied by this semidirect product, the reflection lengths are additive, that is,.
Fully commutative elements and pattern avoidance
A reduced word for an element of a Coxeter group is a tuple of Coxeter generators of minimum possible length such that. The element is called fully commutative if any reduced word can be transformed into any other by sequentially swapping pairs of factors that commute. For example, in the finite symmetric group, the element is fully commutative, since its two reduced words and can be connected by swapping commuting factors, but is not fully commutative because there is no way to reach the reduced word starting from the reduced word by commutations.proved that in the finite symmetric group, 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 such 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 and their coset representatives offer a rich combinatorial structure. Other aspects of affine symmetric groups, such as their 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, all maximal parabolic subgroups are isomorphic to the finite symmetric group. The subgroup generated by the subset consists of those affine permutations that stabilize the interval, that is, that map every element of this interval to another element of the interval.
For a fixed element of, let be the maximal proper subset of Coxeter generators omitting, and let denote the parabolic subgroup generated by. Every coset has a unique element of minimum length. The collection of such representatives, denoted, consists of the following affine permutations:
In the particular case that, so that is the standard copy of inside, the elements of 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 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.
Other combinatorial models of minimum-length coset representatives for can be given in terms of core partitions or bounded partitions. Under these correspondences, it can be shown that the weak Bruhat order on is isomorphic to a certain subposet of Young's lattice.
Bruhat order
The Bruhat order on has the following combinatorial realization. If is an affine permutation and and are integers, defineto be the number of integers such that and. Then for two affine permutations,, one has that in Bruhat order if and only if 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 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, Jian-Yi Shi showed that left cells for 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 and triples 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, introduced in.Inverse realizations
In some situations, one may wish to consider the action of the affine symmetric group on or on alcoves that is inverse to the one given above. These alternate realizations are described below.In the combinatorial action of on, the generator 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 geometric action of, the generator 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 tessellated space.
Relationship to other mathematical objects
The affine symmetric groups are 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 of nonnegative integers that captures the behavior of balls thrown by a juggler, where the number indicates the length of time the th throw spends in the air. The number of balls in the pattern is the average. The Ehrenborg-Readdy correspondence associates to each juggling pattern of period the function defined bywhere indices of the sequence a are taken modulo. Then is an affine permutation in, 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:
where is the number of crossings 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 has and. Therefore, it corresponds to the affine permutation. The juggling pattern has four crossings, and the affine permutation has length.
Similar techniques can be used to derive the generating function for minimal coset representatives of 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 or is one of 34 other examples. The group is the generalized symmetric group: algebraically, it is the wreath product of the cyclic group with the symmetric group. Concretely, the elements of the group may be represented by monomial matrices whose nonzero entries are all th roots of unity. The groups are subgroups of, and in particular the group 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, in the following sense: for every positive integer, there is a surjection from to, and these maps are compatible with the natural surjections when 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 under is a reflection in ; and similarly when the image of the standard Coxeter element in is a Coxeter element in.
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. In the classification of affine Lie algebras, the one associated to is of type, with Cartan matrix for andfor.
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, associated to the affine symmetric group, the corresponding Macdonald identity is equivalent to the Jacobi triple product.
Braid group and group-theoretic properties
Coxeter groups have a number of special properties not shared by all groups. These include that their word problem is decidable and that they are linear groups.Each Coxeter group is associated to an Artin-Tits group, which is defined by a similar presentation that omits relations of the form for each generator. In particular, the Artin-Tits group associated to is generated by elements subject to the relations for, where as before the indices are taken modulo . Artin-Tits groups of Coxeter groups are conjectured to have many nice properties: for example, they are conjectured to be torsion-free, to have trivial center, to have solvable word problem, and to satisfy the conjecture. These conjectures are not known to hold for all Artin-Tits groups, but in it was shown that has these properties. In the case of the affine symmetric group, these proofs make use of an associated Garside structure on the Artin-Tits group.
Artin-Tits groups are sometimes also known as generalized braid groups, because the Artin-Tits group of the symmetric group is the braid group on strands. Not all Artin-Tits groups have a natural representation in terms of geometric braids. However, the Artin-Tits group of the hyperoctahedral group does have such a representation: it is given by the subgroup of the braid group on strands consisting of those braids for which a particular strand ends in the same position it started in, or equivalently as the braid group of strands in an annular region. Moreover, the Artin-Tits group of the hyperoctahedral group can be written as a semidirect product of with an infinite cyclic group. It follows that may be interpreted as a certain subgroup consisting of geometric braids, and also that it is a linear group.