Affine Weyl groups as infinite permutations

Henrik Eriksson

Nada, KTH

S-100 44 Stockholm, Sweden

        henrik@nada.kth.se

Kimmo Eriksson

Dept. of Mathematics, KTH S-100 44 Stockholm, Sweden

                                           kimmo@math.kth.se

Submitted: January 4, 1996; Accepted: March 23, 1998.

Abstract We present a unified theory for permutation models of all the infinite families of finite and affine Weyl groups, including interpretations of the length function and the weak order. We also give new combinatorial proofs of Bott’s formula (in the refined version of Macdonald) for the Poincaré series of these affine Weyl groups.

1991 Mathematics Subject Classification. primary 20B35; secondary 05A15.

1 Introduction

The aim of this paper is to present a unified theory for permutation representations of the finite Weyl groups A_{n−1}, B_{n}, C_{n}, D_{n}, and the affine Weyl groups Ã_{n−1}, B̃_{n}, C̃_{n}, D̃_{n}.

Our starting point is the symmetric group S_{n}, the group of permutations of [1, …, n]. If S_{n} is presented as the group generated by adjacent transpositions, it is isomorphic to the Weyl group A_{n−1}, and we obtain well-known interpretations of several Coxeter group concepts in permutation language:

1. The Coxeter generators are the adjacent transpositions.

2. Reflections correspond to transpositions.

3. Length-decreasing reflections correspond to inversions.

4. The length of an element π is the number of inversions of π.

5. The weak order relation π ≤ σ holds if and only if the inversion set of π is included in the inversion set of σ.

We now introduce a mirror at the origin, reflecting the points 1 … n onto −1 … −n, and we consider permutations of −n … n that are mirror symmetric in the sense that they commute with the action of the mirror. The group of such permutations is isomorphic to the Weyl group C_{n}.

Reflection in the origin is a rigid transformation of ℤ and the same game can be played with any group of such rigid transformations. For instance, the translation n steps to the right generates a transformation group of translations by a multiple of n. The ℤ-permutations that commute with these rigid transformations are nperiodic and the group that they form is isomorphic to Ã_{n−1}. It turns out that for any group of rigid transformations, the group of ℤ-permutations that commute with these transformations will the one of the finite or affine AC-groups. To obtain the BD-groups we add one extra condition of ’local evenness’.

What should replace adjacent transpositions in these models? All rigid transformations of ℤ are either translations or reflections, translating or reflecting the fundamental interval 1 … n to other places. A transposition in the fundamental interval must also affect all these translated and reflected intervals accordingly. The result is what we call a class transposition where the class of a position in the fundamental interval is its orbit given by the rigid transformations. In the C_{n}-case, each class has two elements, {±k}, while in the Ã_{n−1}-case each class is infinite, {k + jn | j ∈ ℤ}.

With the class concept, we can extend most of the results for the symmetric group to all these ℤ-permutation groups. Without going into the precise definitions, our results can be summarized as follows:

1. The permutation groups defined by rigid transformations on ℤ (and conditions of local evenness) are isomorphic to the finite and affine ABCD-groups.

2. The Coxeter generators are the adjacent class transpositions.

3. Reflections correspond to class transpositions.

4. Length-decreasing reflections correspond to class inversions.

5. The length of an element π is the number of class inversions of π.

6. The weak order relation π ≤ σ holds if and only if the class inversion set of π is included in the class inversion set of σ.

7. The permutations are completely determined by their fundamental n-tuple [π_{1}, …, π_{n}]. For each group we determine how the results above can be (less elegantly) expressed in terms of the fundamental n-tuple.

Finally, as an application of our theory, we give new combinatorial proofs of Bott’s formulas for the Poincaré series of the affine groups Ã_{n}, B̃_{n}, C̃_{n}, D̃_{n}. In a sequel to this paper we shall present Bruhat order criteria for these permutation models.

2 Preliminaries on ℤ-permutations

An ordinary permutation, such as 231, may be interpreted as a co-ordinate permuting operator on ℝ^{3}, mapping a vector [x_{1}, x_{2}, x_{3}] to [x_{2}, x_{3}, x_{1}]. In analogy with this, a ℤ-permutation π is going to be an operator on ℝ^{ℤ}, mapping a vector […, x_{−1}, x_{0}, x_{1}, x_{2}, …] to […, x_{π_{−1}}, x_{π_{0}}, x_{π_{1}}, x_{π_{2}}, …].

In particular, […, −1, 0, 1, 2, …] ↦^{π} […, π_{−1}, π_{0}, π_{1}, π_{2}, …] and we shall identify the operator π with this π-vector.

We define the product πσ of two ℤ-permutations as the composite operator “first π, then σ”. From

[…, −1, 0, 1, 2, …] ↦^{π} […, π_{−1}, π_{0}, π_{1}, π_{2}, …] ↦^{σ} […, π_{σ_{−1}}, π_{σ_{0}}, π_{σ_{1}}, π_{σ_{2}}, …] we see

that (πσ)_{i} = π_{σ_{i}}.

Our mental picture of ℤ is going to be the set of integer points on the real axis. We will call these points positions. A ℤ-permutation π can be visualized as a distribution of values at the positions, defined by placing the value π_{i} at position i.

[figure: −1; 0; 1; 2; 3; 4; 5; 6; 7; π_{−1}; π_{0}; π_{1}; π_{2}; π_{3}; π_{4}; π_{5}; π_{6}; π_{7}]

But a ℤ-permutation can also be envisioned as an action, moving values from some positions to other positions. An important special case is the action of an adjacent transposition σ = (i i+1), which is to interchange the values at positions i and i+1. We will use pictures as the one below to portray the action of transpositions, in this case σ = (2 3).

[figure: −1; 0; 1; 2; 3; 4; 5; 6; 7]

Combining these models, we can interpret the multiplication rule (πσ)_{i} = π_{σ_{i}} as the action of σ on the π-vector of values.

2.1 Locally finite ℤ-permutations

If we view a permutation as a value-moving action, we can ask how many values that cross a given co-ordinate. For an ordinary permutation, it is clear that as many values pass from left to right as from right to left, and for the application in mind, we will use only ℤ-permutations with this property.

A ℤ-permutation π is locally finite if a finite number of values are moved from the negative half-axis to the nonnegative half-axis and the same number of values are moved in the other direction.

Reflection in the origin is not locally finite, for infinitely many values are moved from one side to the other. Translation n steps to the right is not locally finite either, for it moves n values from the left to the right but no values in the other direction.

Proposition 1 For any partition of ℤ into half-axes (−∞, m] and [m + 1, ∞), a locally finite ℤ-permutation π will move a finite number of values from the left to the right and the same number of values in the other direction.

Proof Otherwise, the interval [0, m] would have a net inflow or outflow of values, which is absurd. □

Proposition 2 If π and σ are locally finite ℤ-permutations, then so is the inverse π^{−1} and the product πσ. Thus, for every group of ℤ-permutations, the locally finite ℤ-permutations form a subgroup.

Proof Easy. □

2.2 Locally even ℤ-permutations

We say that a permutation is locally even at position m if it moves an even number of values from the left of m to the right of m. This sharpening of the local finiteness condition is needed in order for us to obtain representations of the groups of type D, B̃ and D̃.

3 The ABCD-families of Weyl groups

The classification of finite and affine Weyl groups (due to Coxeter in 1935) features the infinite families defined by the Coxeter graphs in the table below. For precise definitions and for Coxeter group theory in general, we refer to the book [13] by Humphreys.

Coxeter graphs encode groups as follows. The vertices are the generators of the group. Every generator s satisfies s^{2} = 1. All other relations in the group are of the kind (s_{i}s_{j})^{m(i,j)} = 1 for s_{i} ≠ s_{j}. The order m(i, j) is encoded in the graph by the label of the edge between s_{i} and s_{j}. If there is no edge, then the order is 2. If there is an unlabeled edge, then the order is 3.

3.1 Brief history of permutation representations

There are classical representations of A_{n−1} as the symmetric group S_{n}, and of C_{n} and D_{n} as signed permutations and even signed representations respectively.

In the last fifteen years, representations of the affine groups Ã_{n}, B̃_{n}, C̃_{n} and D̃_{n} by infinite periodic permutations have been presented. Lusztig [14] and Bédard [1] seem to be the first references for the permutation representations of Ã_{n} and C̃_{n} respectively (although none of them explicitly proves that these representations are faithful). These representations of Ã_{n} and C̃_{n} are used also by Shi [18]. In H.

[figure: A_{n−1}; s_{1}; s_{n−1}; …; Ã_{n−1}; s_{n}; …]

[figure: B_{n}; s_{0}; s_{1}; …; 4; s_{n−1}; B̃_{n}; …; 4; s_{n}]

C_{n} = B_{n}  C̃_{n}  [figure: …; 4; 4; s_{n}]

[figure: D_{n}; s_{1}; s_{2}; …; s_{0}; s_{n−1}; D̃_{n}; …; s_{n}]

Table 1: ABCD-families of irreducible finite and affine Weyl groups

Eriksson’s doctoral thesis [11], permutation representations (with proofs) are given also for B̃_{n} and D̃_{n}, as well as related permutation models for the sporadic EF GHgroups and many other nameless groups.

Permutation interpretations of length, weak order and Bruhat order on Ã_{n} were recently given by Björner and Brenti [4], using another approach than ours.

3.2 The permutation representations of this paper

The present paper is mainly a thorough expansion and improvement of a few results from the second chapter of [11]. Instead of the case-by-case approach of [11], we here obtain the same permutation models for the ABCD-groups with unified proofs. In the same process we obtain general results on how to express the Coxeter generators, the length function, the descent set and the weak order for all these groups.

We also prove that a permutation π in any of these groups can be represented by its fundamental n-tuple [π_{1}, …, π_{n}]. Finally we investigate for each group how the results translate to this computationally more tractable representation.

4 Rigid groups and compatible groups

Translations and reflections are the only rigid transformations of ℤ. We denote by T_{n} a translation n steps to the right and by R_{m} a reflection with respect to m, which must be an integer or half-integer. A rigid group is a group of such rigid transformations.

The classification of rigid groups on ℤ is prehistoric, so the following proposition comes without credits.

Proposition 3 A nontrivial rigid group on ℤ is of one of three types: generated by one translation ⟨T_{n}⟩, generated by one reflection ⟨R_{m}⟩ or generated by two reflections ⟨R_{m}, R_{m′}⟩.

Proof Let n be the smallest nonnegative integer such that T_{n} is in the group and m the smallest nonnegative integer or half-integer such that R_{m} is in the group. If both n and m are undefined, the group is trivial {id}. If only n is defined, the group must be {T_{kn} | k ∈ ℤ}. If only m is defined, the group must be {R_{m}, id}, for a product of two reflections is a translation. If both are defined, the group must be {T_{kn}, R_{m}T_{kn} | k ∈ ℤ} which is ⟨R_{m}, R_{m′}⟩ for m′ = m + n/2. □

For each of these rigid groups, we are interested in the corresponding compatible ℤ-permutations, compatible in the sense that they commute with all transformations in the group.

Lemma 4 A ℤ-permutation π commutes with the translation T_{n} if and only if the periodicity relation π_{i+n} = π_{i} + n holds for all positions i. It commutes with the reflection R_{m} if and only if the mirror relation π_{i} = 2m−π_{2m−i} holds for all positions i.

Proof The value on position π_{i} is moved to position i by π and further to position i+n by T_{n}, then on to π_{i+n} by π^{−1} and finally to π_{i+n} − n by T_{n}^{−1}. Commutativity therefore means that π_{i} = π_{i+n} − n, as stated in the lemma. The mirror relation comes out similarly. □

If positions i and j belong to the same orbit, that is if some transformation in the rigid group maps i to j, then π_{i} determines π_{j} by one of these relations. Belonging to the same orbit is an equivalence relation i ∼ j, and we shall denote the equivalence class of the position i by ⟨i⟩. The π-value on any position in the class thus determines the values on all positions in the class.

It is easy to see what the orbits are for the three kinds of nontrivial rigid groups.

Proposition 5 For the three kinds of nontrivial rigid groups, the relation i ∼ j has the following significance:

⟨T_{n}⟩: i = j + kn for some k ∈ ℤ,

⟨R_{m}⟩: i = j or i + j = 2m,

⟨R_{m}, R_{m′}⟩: i = j + kn or i + j = 2m + kn for some k ∈ ℤ. (n is defined by m′ = m + n/2.)

The same classes are useful for values. In fact, π_{i} ∼ π_{j} if and only if i ∼ j. This is exactly what commutativity with the rigid transformations implies, so the following proposition holds true.

Proposition 6 Let ⟨i⟩ be a position class of a rigid group. Then, for any compatible ℤ-permutation π, the value class ⟨π_{i}⟩ consists of the π-values on the positions in ⟨i⟩.

4.1 Mirrors of types C and D

If we have the mirror relation π_{i} = 2m − π_{2m−i} for all positions i, we say that m is a mirror position. The mirror relation implies that m is a fixpoint under π.

Recall the definition of locally even: π is locally even at position m if it is an even number of values that is moved from the left of m to the right of m. We will apply this condition only at mirror positions. We say that a mirror m is of type D if we study only permutations that are locally even at m. Otherwise m is a mirror of type C.

4.2 Class transpositions and adjacent class transpositions

We can extend the relation ∼ of belonging to the same orbit to a relation on pairs of positions. Let ⟨(i_{1}, i_{2})⟩ denote the equivalence class of a pair (i_{1}, i_{2}) under ∼, that is, the orbit of (i_{1}, i_{2}) under the rigid group.

Say that a pair (i_{1}, i_{2}) of different positions is transposable (under the rigid group) if there exists at least one compatible ℤ-permutation π such that π_{i_{1}} = i_{2} and π_{i_{2}} = i_{1}. Evidently, a pair (i_{1}, i_{2}) cannot be transposable if either i_{1} or i_{2} is a mirror, since mirrors are always fixpoints of compatible permutations. It is also clear that (i_{1}, i_{2}) cannot be transposable if the rigid group has n-periodicity and i_{2} = i_{1} + kn for some integer k, since by periodicity we will have π_{i_{2}} = π_{i_{1}} + kn. In fact, these two simple conditions are both necessary and sufficient.

Proposition 7 For the three kinds of nontrivial rigid groups, transposability works as follows:

⟨T_{n}⟩: (i_{1}, i_{2}) is transposable iff i_{2} − i_{1} is not a multiple of n.

⟨R_{m}⟩: (i_{1}, i_{2}) is transposable iff neither position equals m.

⟨R_{m}, R_{m′}⟩: (i_{1}, i_{2}) is transposable iff neither position equals m + kn/2 and i_{2} − i_{1} is not a multiple of n. (n is defined by m′ = m + n/2.)

In order to prove this result, one can construct a compatible permutation where (i_{1}, i_{2}) is transposed if it satisfies all the conditions as follows. Define the class transposition ⟨(i_{1} i_{2})⟩ as the permutation in which every pair in ⟨(i_{1}, i_{2})⟩ is transposed:

⟨(i_{1} i_{2})⟩ = ∏_{(j_{1},j_{2})∈⟨(i_{1},i_{2})⟩}(j_{1} j_{2}).

It is easy to check that this permutation is well-defined and compatible with the rigid group, and we leave it to the reader.

Remark. If the midpoint m = (i_{1} + i_{2})/2 is a mirror of type D, then the class transposition ⟨(i_{1} i_{2})⟩, though compatible with the rigid group, does not belong to the subgroup of permutations that are locally even at m, since an odd number of values are moved from left to right of m.

4.3 Adjacent class transpositions

In the symmetric group, the adjacent transpositions are the Coxeter generators. We shall now define the analog of adjacent transpositions in our permutation groups.

Fix a rigid group and let G be the group of compatible permutations, or possibly the subgroup of locally even permutations if mirrors are of type D. We say that ⟨(i j)⟩ is an adjacent class transposition in G if either j is the smallest number greater than i, or i is the largest number less than j, such that ⟨(i j)⟩ is a class transposition in G.

The definition of adjacent class transpositions allows us to list all cases that can occur. For each case we give an illustration of the action of the class transposition in a small segment.

• If i and i + 1 are non-mirrors, then ⟨(i i+1)⟩ is adjacent.

[figure: i; i+1]

• If m is a mirror of type C, then ⟨(m−1 m+1)⟩ is adjacent.

• If m is a mirror of type D, then ⟨(m−1 m+2)⟩ is adjacent.

[figure: C; m−1; m+1] [figure: D; m−1; m+2]

Lemma 8 The three types of class transpositions above are the only adjacent class transpositions.

Proof Inspection. □

5 Representations of the ABCD-groups

For each of the rigid groups, the compatible ℤ-permutations form a group. These groups are closely connected to the ABCD-families of finite and affine Weyl groups. If the rigid group is the trivial group, ⟨T_{n}⟩, ⟨R_{m}⟩ or ⟨R_{m}, R_{m′}⟩, the compatible permutation groups will be isomorphic to Weyl groups of type A, Ã, C and C̃ respectively. If conditions of local evenness is added, we obtain the remaining groups, of type D, B̃ and D̃.

Postponing the proof of the faithfulness of the representations below, we shall define for each of the ABCD-groups a representation by ℤ-permutations. We like to call this family of groups George groups in honor of George Lusztig who invented the permutation representation S̃_{n} for Ã_{n−1}. A common characteristic of George groups will be that the action takes place in positions belonging to ⟨1⟩, ⟨2⟩, …, ⟨n⟩. Positions outside these n classes are fixed points for all ℤ-permutations involved. Another common feature will be that the action of s_{1} transposes positions 1 and 2, the action of s_{2} transposes positions 2 and 3 etc up to s_{n−1}.

5.1 The compatible groups: S_{n}, S̃_{n}, C_{n} and C̃_{n}

We start by listing the compatible groups to the four possible rigid groups (including the trivial rigid group).

5.1.1 Rigid group: trivial. The compatible group S_{n} represents A_{n−1}, n ≥ 2.

The standard representation of A_{n−1} by permutations of 1, 2, …, n can be viewed as the group of ℤ-permutations that leave everything outside the fundamental interval fixed. In this case, the rigid group is trivial, so every position has a class of its own.

[figure: s_{1}; s_{2}; s_{3}; s_{4}; 1; 2; 3; 4; 5; s_{1}]

Figure 1: The action of s_{1} in S_{5} as a simple transposition 5.1.2 Rigid group: ⟨T_{n}⟩. The compatible group S̃_{n} represents Ã_{n−1}, n ≥ 2.

Define S̃_{n} as the group of all locally finite ℤ-permutations compatible with the translation group ⟨T_{n}⟩.

Proposition 9 A ℤ-permutation π compatible with ⟨T_{n}⟩ is locally finite iff the following sum condition holds:

∑_{1}^{n} π_{i} = ∑_{1}^{n} i.

Proof Permutation of the values in the interval leaves the sum invariant. Whenever a value v is moved leftwards out of the interval, the value v + n enters from right and so the sum increases by n. And when a value v enters the interval from the left, the value v + n leaves the interval to the right, decreasing the sum by n. Local finiteness signifies that these two effects cancel. □

The group S̃_{n} is generated by the adjacent class transpositions s_{i} = ⟨(i i + 1)⟩, for i = 1, …, n.

[figure: 14; 13; 12; 11; 10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0; -14; -13; -12; -11; -10; -9; -8; -7; -6; -5; -4; -3; -2; -1]

Figure 2: The action of s_{1} ∈ S̃_{4} as a periodic transposition.

5.1.3 Rigid group: ⟨R_{0}⟩. The compatible group C_{n} represents C_{n}, n ≥ 2.

Define C_{n} as the group of permutations of [−n, …, n] compatible with the rigid group ⟨R_{0}⟩, so that π_{−i} = −π_{i} for all i. C_{n} is generated by s_{0} = ⟨(−1 1)⟩ = (−1 1) and, for i = 1, …, n − 1, s_{i} = ⟨(i i + 1)⟩ = (i i + 1)(−i − i − 1).

[figure: s_{3}; s_{3}; s_{0}; C; 4; s_{0}; s_{1}; s_{2}; s_{3}]

Figure 3: The actions of s_{3} and s_{0} in C_{4}

As a concrete example of computing in this model, consider the element s_{3}s_{0}. In C_{4}, this permutes the interval [−4, …, 4] as follows:

[−4, −3, −2, −1, 0, 1, 2, 3, 4] ⟶^{s_{3}} [−3, −4, −2, −1, 0, 1, 2, 4, 3]
⟶^{s_{0}} [−3, −4, −2, 1, 0, −1, 2, 4, 3].

5.1.4 Rigid group: ⟨R_{0}, R_{n+1}⟩. The compatible group C̃_{n} represents C̃_{n}, n ≥ 2.

Define C̃_{n} as the group of permutations of ℤ compatible with ⟨R_{0}, R_{n+1}⟩, so that π_{i} = −π_{−i} and π_{i} = 2n + 2 − π_{2n+2−i} for all i. There are n infinite classes: ⟨i⟩ = {±i + k(2n + 2) : k ∈ ℤ} for i = 1, …, n. C̃_{n} is generated by the class transpositions s_{0} = ⟨(−1 1)⟩ and s_{n} = ⟨(n n + 2)⟩ and, for i = 1, …, n − 1, s_{i} = ⟨(i i + 1)⟩.

[figure: C; C; C; C; s_{1}; s_{1}; s_{1}; s_{1}; s_{0}; s_{0}; s_{4}; s_{4}]
Figure 4: The actions of s_{0}, s_{1}, s_{4} ∈ C̃_{4} as transpositions on ℤ.

5.2 Locally even subgroups: D_{n}, B̃_{n} and D̃_{n}

There are three possible ways of obtaining subgroups of the above compatible groups by adding a condition of local evenness at mirror positions.

5.2.1 Subgroup of C_{n}, locally even at 0: D_{n} represents D_{n}, n ≥ 3.

Define D_{n} as the subgroup of C_{n} consisting of all permutations that are locally even at position zero. D_{n} is generated by the adjacent class transpositions s_{0} = ⟨(−1 2)⟩ and, for i = 1, …, n − 1, s_{i} = ⟨(i i + 1)⟩.

[figure: s_{3}; s_{3}; s_{0}; s_{0}; D; s_{0}; s_{1}; s_{2}; s_{3}]

Figure 5: The actions of s_{3} and s_{0} in D_{4}

Let us do the same example as for C_{4}. In D_{4}, the action of s_{3}s_{0} is:

[−4, −3, −2, −1, 0, 1, 2, 3, 4] ⟶^{s_{3}} [−3, −4, −2, −1, 0, 1, 2, 4, 3]
⟶^{s_{0}} [−3, −4, 1, 2, 0, −2, −1, 4, 3].

5.2.2 Subgroup of C̃_{n}, locally even at 0: B̃_{n} represents B̃_{n}, n ≥ 3.

Define B̃_{n} as the subgroup of C̃_{n} consisting of all permutations that are locally even at zero. The adjacent class transpositions are s_{0} = ⟨(−1 2)⟩ and s_{n} = ⟨(n n + 2)⟩ and, for i = 1, …, n − 1, s_{i} = ⟨(i i + 1)⟩.

5.2.3 Subgroup of B̃_{n}, locally even at n + 1: D̃_{n} represents D̃_{n}, n ≥ 4.

Define D̃_{n} as the subgroup of B̃_{n} consisting of all permutations that are locally even at position n + 1. The adjacent class transpositions are s_{0} = ⟨(−1 2)⟩ and s_{n} = ⟨(n − 1 n + 2)⟩ and, for i = 1, …, n − 1, s_{i} = ⟨(i i + 1)⟩.

6 Theory of George groups

In this section we will develop a theory for George groups, analogous to the theory for the symmetric group, with concepts such as inversions, inversion tables, length function, weak order, descents and reflections.

6.1 Class inversions in George groups

Let G be a George group. An inversion in a permutation π is a pair (π_{i}, π_{j}) such that i < j and π_{i} > π_{j}. If ⟨(i j)⟩ is a class transposition in G and (π_{i}, π_{j}) is an inversion in π ∈ G, then the class ⟨(π_{i}, π_{j})⟩ is a class inversion in π. If i < j, note that the inversion property π_{i} > π_{j} is respected both by periodicity, π_{i+n} > π_{j+n}, and by mirrors, π_{2m−j} > π_{2m−i}. Thus every pair in the class inversion ⟨(π_{i}, π_{j})⟩ is an inversion.

Example Consider the permutation π = [−2, 1, −3, 0, 3, −1, 2] in the George group C_{3}.

[figure: C; −3; −2; −1; 1; 2; 3; −2; 1; −3; 3; −1; 2]

There are seven inversions in π: (−2, −3), (1, −3), (1, 0), (1, −1), (0, −1), (3, −1) and (3, 2). However, there are only three class inversions:

⟨(3, 2)⟩ = {(−2, −3), (3, 2)},
⟨(1, −3)⟩ = {(1, −3), (3, −1)},
and ⟨(1, −1)⟩ = {(1, −1)}.

Hence, of the seven inversions we have five that are members of class inversions, while (1, 0) and (0, −1) are not, since no class transposition involves 0, the mirror position. □

We want to show that the adjacent class transpositions fill exactly the same role in George groups as the adjacent transpositions do in the symmetric group, in the following sense: adjacent transpositions create or resolve exactly one inversion, and if there exists any inversion then there exists an adjacent inversion.

Lemma 10 An adjacent class transposition ⟨(i j)⟩, i < j, affects (creates or resolves) exactly one class inversion.

Proof Without loss of generality, let us assume that the class transposition ⟨(i j)⟩ is acting on the identity permutation. It is clear from inspection of our list of adjacent class transpositions (Section 4.3) that they create exactly one class inversion, namely ⟨(j, i)⟩. □

We will need the following characterization of adjacent class transpositions.

Lemma 11 A class transposition ⟨(i j)⟩ in G is adjacent if and only if

(1) there is no k between i and j such that both ⟨(i k)⟩ and ⟨(k j)⟩ are class transpositions in G; and

(2) if there is a period p, then |j − i| < p.

Proof The three adjacent class transpositions listed in Section 4.3 clearly satisfy the above conditions. For the other direction, it is easy to check that condition (1) is sufficient in all George groups except for S̃_{2} where the period is two. In this group the first condition is satisfied not only by adjacent pairs but also by e.g. (1, 4), (1, 6), (1, 8), etc, but the second condition then kicks into action. □

Lemma 12 If π ∈ G has a class inversion then it has an adjacent class inversion.

Proof Let (π_{i}, π_{j}) be a class inversion representative such that j − i is minimal. By the characterization of adjacency above, it is sufficient that we exclude two cases:

1. If there is some k between i and j such that both ⟨(i k)⟩ and ⟨(k j)⟩ are class transpositions in G; then either (π_{i}, π_{k}) or (π_{k}, π_{j}) is a class inversion representative, contradicting minimality of j − i.

2. If j − i is greater than the period n, then (π_{i}, π_{j−n}) is a class inversion representative that contradicts minimality of j − i.

□

6.2 The inversion table of a George group

Let G_{n} be a George group with n classes. Define I(π) as the set of class inversions in a permutation π ∈ G. Define the class inversion number by inv(π) = |I(π)|, the number of class inversions in π.

Our first aim is to show that inv(π) is always finite. Recall that the the interval [1, …, n] contains one representative of each class of values. For π ∈ G_{n} and 1 ≤ i < j ≤ n, define

I_{ij}^{L}(π) as the set of class inversions in π of the form ⟨(i, j′)⟩ where j′ is a periodic image of j;

I_{ij}^{R}(π) as the set of class inversions in π of the form ⟨(j′, i)⟩ where j′ is a periodic image of j.

For n ≥ j ≥ i ≥ 1, define

I_{ji}^{L}(π) as the set of class inversions in π of the form ⟨(i, j′)⟩ where j′ is a mirror image of j;

I_{ji}^{R}(π) as the set of class inversions in π of the form ⟨(j′, i)⟩ where j′ is a mirror image of j.

Define the inversion table of π by the numbers inv_{ij}(π) = |I_{ij}^{L}(π)| − |I_{ij}^{R}(π)|.

Example As an example of these definitions, consider as in our previous example the George group C_{3} and the permutation π = [−2, 1, −3, 0, 3, −1, 2]. In this group there is no periodicity, so the only periodic image of i is i itself, and the only mirror image of i is −i. The only non-empty inversion sets are inv_{11}^{L}, inv_{31}^{L} and inv_{23}^{R}, containing respectively ⟨(1, −1)⟩, ⟨(1, −3)⟩, and ⟨(3, 2)⟩. Hence, the inversion table is

\begin{matrix}1 & 0 & 0 \\ 0 & 0 & −1 \\ 1 & 0 & 0 \end{matrix}

□

Lemma 13 I(π) is the disjoint union of all I_{ij}^{L}(π) and I_{ij}^{R}(π) for i, j = 1, …, n. Furthermore, if I_{ij}^{L}(π) ≠ ∅ then I_{ij}^{R}(π) = ∅ and if I_{ij}^{R}(π) ≠ ∅ then I_{ij}^{L}(π) = ∅. The numbers inv_{ij}(π) are always finite, and

inv(π) = ∑_{i=1}^{n} ∑_{j=1}^{n} |inv_{ij}(π)|,

so inv(π) is also finite.

Proof Everything follows directly from the definitions except for finiteness of the numbers. If the group acts on a finite interval, then of course the number of inversions is finite. If it acts on ℤ then we use periodicity. For instance, by periodicity there is a greatest periodic image j′ > i in the class ⟨j⟩ such that π_{i}^{−1} > π_{j′}^{−1}, and hence I_{ij}^{R}(π) is a finite set. □

Since the number of class inversions is finite, and adjacent class transpositions resolve class inversions, we can express all permutations in a George group as products of adjacent class transpositions as shown below.

Theorem 14 A George group is generated by its adjacent class transpositions.

Proof The identity permutation is the only permutation with no class inversions. Suppose π has class inversion number inv(π) > 0. Then by Lemma 12 it has an adjacent class inversion ⟨(j, i)⟩ and hence we can write π = π′⟨(i j)⟩ where inv(π′) = inv(π) − 1 thanks to Lemma 10. Proceeding in this manner we eventually reach the identity, at which time we will have expressed π as a product of adjacent class transpositions. □

6.3 The length function and weak order on George groups

For a George group G, let S be the set of adjacent class transpositions. Define the length ℓ(π) of π ∈ G to be the smallest length of a word for π in the alphabet S. This is the usual definition of length in Coxeter groups. We will now give a convenient formula for the length in terms of the number of class inversions.

Theorem 15 The length ℓ(π) equals the class inversion number inv(π).

Proof By the proof of Theorem 14, there is a word for π of length inv(π). It is also shortest possible, since starting from the identity permutation (where the class inversion number is zero), each s ∈ S can at most increase the number of class inversions by one. □

For a George group G with generators S, define the weak order on G by σ ≤ π if there is a factorisation π = σs_{i_{1}}s_{i_{2}} ⋯ s_{i_{k}} where k = ℓ(π)−ℓ(σ) and all s_{i_{j}} belong to S. This is the usual definition of weak order in Coxeter groups. We shall now establish two weak order criteria. First, we claim that weak order is equivalent to inclusion order on the set of class inversions. Second, this translates to a computationally tractable condition on the inversion tables.

Theorem 16 For any George group G, the following three assertions are equivalent:

(1) π ≥ σ in the weak order on G.

(2) I(π) ⊇ I(σ)

(3) |inv_{ij}(π)| ≥ |inv_{ij}(σ)| and sgn inv_{ij}(π) = sgn inv_{ij}(σ) for all i, j = 1, …, n. (Zero is considered both positive and negative.)

Proof (1) ⇒ (2): Assume that π ≥ σ in the weak order, so π = σs_{i_{1}}s_{i_{2}} ⋯ s_{i_{k}} with ℓ(π) = ℓ(σ) + k. Then each multiplication by a generator introduces a new class inversion, but the class inversions already in I(σ) are not affected, so I(π) ⊇ I(σ).

(2) ⇒ (1): Assume that I(π) ⊇ I(σ) and show that there is a factorization π = π′s with ℓ(π) = ℓ(π′) + 1 and I(π′) ⊇ I(σ); induction would then give π ≥ σ. Let (π_{i}, π_{j}) be a representative of a class inversion in I(π) \ I(σ), such that π_{i} > π_{j}, i < j, and the difference j − i is minimal among such inversions. We can proceed much as in the proof of Lemma 12 to show that (i, j) is adjacent. Then the adjacent class transposition s = ⟨(i j)⟩ resolves the inversion (π_{i}, π_{j}) and affects no other class inversion, so π = π′s will do as our factorisation.

(2) ⇔ (3): We must show that

I_{ij}^{L}(π) ⊇ I_{ij}^{L}(σ)  ⟺  |I_{ij}^{L}(π)| ≥ |I_{ij}^{L}(σ)|,

(and analogously for I_{ij}^{R}). The right implication is trivial. For the other direction, we just observe that the set I_{ij}^{L}(π) is determined by its cardinality. E.g. if I_{ij}^{L}(π) has k elements, where i < j, then I_{ij}^{L}(π) = {(i, j), (i, j − p), (i, j − 2p), …, (i, j − (k − 1)p)} where p is the period. □

6.4 Descents and reflections in George groups

Let us briefly look at the interpretation of descent and reflection in our George groups. In an ordinary permutation, a descent is any occurrence of π_{i} > π_{i+1}, i.e. an adjacent inversion. In a general Coxeter group, a descent is defined as a length decreasing generator.

Define a class descent in π as an adjacent class inversion. Obviously, the class descents in π are in bijection with the set

D(π) = {s ∈ S | ℓ(πs) < ℓ(π)},

where S is the set of adjacent class transpositions, i.e. D(π) are the length decreasing generators.

By a reflection in a Coxeter group is meant an element that is conjugate to a Coxeter generator. In George groups, the reflections are then the class transpositions.

Lemma 17 A permutation t ∈ G is a class transposition iff t = σ^{−1}sσ for some generator s ∈ S and permutation σ ∈ G.

Proof With s = ⟨(i j)⟩ and σ_{a} = i, σ_{b} = j we have σ^{−1}sσ = ⟨(a b)⟩. □

7 George groups and Weyl groups

The raison d’être for the George groups is of course that they are isomorphic to the ABCD-families of Weyl groups. We are now ready to prove this. In the next section we shall take the Weyl groups in turn and give specific interpretations of the results of the previous chapter.

To begin with, we must investigate what Coxeter relations there are between the generators of a George group G.

Lemma 18 If s and t are two adjacent class transpositions in a George group, then the order m(s, t) of st is

m(s, t) = 2 if s and t are disjoint;

[figure: t; s]

m(s, t) = ∞ if the period is 2 and s = ⟨(i i+1)⟩ and t = ⟨(i+1 i+2)⟩ for some i;

[figure: t; s; t; s]

m(s, t) = 3 if any period is ≥ 3 and s = ⟨(i i+1)⟩ and t = ⟨(i+1 i+2)⟩ for some i;

[figure: s; t]

m(s, t) = 3 if s = ⟨(i−1 i)⟩ and t = ⟨(i i+3)⟩ for some i (where i + 2 is a type D mirror);

m(s, t) = 2 if s = ⟨(i i+1)⟩ and t = ⟨(i i+3)⟩ for some i (where i + 2 is a type D mirror); m(s, t) = 4 if s = ⟨(i i+1)⟩ and t = ⟨(i+1 i+3)⟩ for some i (where i + 2 is a type

[figure: s; s; t; t; D]

[figure: s; s; t; t; D]

C mirror);

[figure: s; s; t; C]

Proof Inspection. □

A convenient way of proving that a group with generators is isomorphic to a Coxeter group is to use the following characterization of the weak order of a Coxeter group.

Theorem 19 (K. Eriksson [12]) For any Coxeter group (W, S) with Coxeter relations (st)^{m(s,t)} = 1 for s, t ∈ S, there exists a poset P, unique up to isomorphism, such that:

1. P has a least element ˆ0.

2. There are |S| elements covering ˆ0.

3. P admits an S-labeling of the edges of its Hasse diagram satisfying:

(a) No two edges incident to the same element of P have the same label.

(b) If there are two edges going upwards from p ∈ P with labels s and t, then they are the first edges of two upward going paths from p of length m(s, t) labeled alternatingly s and t. If m(s, t) < ∞ then these paths end in the same element, while if m(s, t) = ∞ the paths go on forever.

The poset P is isomorphic to the weak order on (W, S).

By this theorem we can prove that the weak order of a George group is isomorphic to the weak order of the Coxeter group with corresponding relations, and hence they are isomorphic as Coxeter systems.

Theorem 20 The George groups S_{n} (n ≥ 2), C_{n} (n ≥ 2), D_{n} (n ≥ 3), S_{n} (n ≥ 2), C̃_{n} (n ≥ 2), B̃_{n} (n ≥ 3), D̃_{n} (n ≥ 4), generated by the set of adjacent class transpositions, are all Coxeter groups.

Proof We shall check that the weak order on a George group G satisfies the conditions of the above theorem. Let S_{G} be the set of adjacent class transpositions in G.

1. The identity permutation is the least element.

2. The identity has no inversions so all |S_{G}| adjacent class transpositions will create inversions. Hence there are |S_{G}| elements covering the identity.

3. Every edge in the Hasse diagram of the weak order on G is between pairs π and πs for some s ∈ S_{G}. Label the edge by s. This is clearly an S_{G}-labeling satisfying that no two edges incident to the same element π have the same label. If there are two edges going upwards from π with labels s and t, then it is straightforward verification that they are the first edges of two upward going paths from π of length m(s, t) labeled alternatingly s and t, and that if m(s, t) < ∞ then these paths end in the same element, while if m(s, t) = ∞ the paths go on forever.

For example, take the case where s = ⟨(i i+1)⟩ and t = ⟨(i i+3)⟩ for some i where i + 2 is a type D mirror; this gives m(s, t) = 2. Both edges go upwards if both π_{i} > π_{i+1} and π_{i} > π_{i+3}. We get two joining alternating paths of length two:

[figure: […, π_{i}, π_{i+1}, D, π_{i+3}, π_{i+4}, …]; […, π_{i+1}, π_{i}, D, π_{i+4}, π_{i+3}, …]; […, π_{i+4}, π_{i+3}, D, π_{i+1}, π_{i}, …]; […, π_{i+3}, π_{i+4}, D, π_{i}, π_{i+1}, …]; s; t; t; s]
□

8 Inversion tables of George groups

We shall now follow up on the list of Section 5. For every George group we shall give a characterization of the fundamental n-tuple and compute explicit expressions for the inversion table, from which the length formula and the weak order criterion follows.

8.1 Compatible groups

8.1.1 George group S_{n}

The fundamental n-tuple is any permutation of [1, …, n]. The inversion table has inv_{ij} = −1 if i < j and π_{i}^{−1} > π_{j}^{−1}, zero otherwise. All other entries are zero. Thus the length function ℓ(π) is the number of ordinary inversions in π.

8.1.2 George group S̃_{n}

An n-tuple [π_{1}, …, π_{n}] is the fundamental n-tuple of a π ∈ S̃_{n} if and only if it can be written

[τ_{1} + k_{1}n, …, τ_{n} + k_{n}n]

where τ ∈ S_{n} and k_{1} + … + k_{n} = 0. The action of s_{i} on the fundamental n-tuple is s_{i} = (i i + 1) for i = 1, …, n − 1, while s_{n} gives [π_{n} − n, π_{2}, …, π_{n−1}, π_{1} + n]. The inversion table is given by

inv_{ij}(π) = \{ \begin{matrix}⌊\frac{π_{j}^{−1}−π_{i}^{−1}}{n} ⌋ & for i < j; \\ 0 & for i ≥ j, \end{matrix}

where ⌊x⌋ denotes the greatest integer less than or equal to x. The value π_{i}^{−1} can be obtained from the fundamental n-tuple as follows: if i = τ_{r}, then

i + k_{r}n = π_{r} ⇔ i = π_{r−k_{r}n} ⇔ π_{i}^{−1} = r − k_{r}n.

8.1.3 George group C_{n}

An n-tuple [π_{1}, …, π_{n}] is the fundamental n-tuple of a π ∈ C̃_{n} if and only if it is a signed permutation, that is, if [|π_{1}|, …, |π_{n}|] is a permutation of [1, …, n]. The action of s_{i} on the fundamental n-tuple is s_{i} = (i i+1) for i = 1, …, n − 1, while s_{0} changes the sign of the value at position 1.

The inversion table is given by

inv_{ij}(π) = \{ \begin{matrix}−1 & if i < j and π_{i}^{−1} > π_{j}^{−1}; \\ 1 & if i ≥ j and π_{i}^{−1} < π_{−j}^{−1}; \\ 0 & otherwise. \end{matrix}

In terms of the fundamental n-tuple of π, the length function ℓ(π) is the number of pairs (i, j) that are inversions, plus the number of pairs (−i, j) that are inversions, plus the number of negative values in the fundamental n-tuple.

8.1.4 George group C̃_{n}

An n-tuple [π_{1}, …, π_{n}] is the fundamental n-tuple of a π ∈ C̃_{n} if and only if it can be written

[τ_{1} + k_{1}(2n + 2), …, τ_{n} + k_{n}(2n + 2)]

where τ ∈ C_{n}. The action of s_{i} on the fundamental n-tuple is s_{i} = (i i + 1) for i = 1, …, n−1, while s_{0} gives [−π_{1}, π_{2}, …, π_{n−1}, π_{1}+n] and s_{n} gives [π_{1}, π_{2}, …, π_{n−1}, 2n+ 2 − π_{n}]. The inversion table is given by

inv_{ij}(π) = \{ \begin{matrix}⌊\frac{π_{j}^{−1}−π_{i}^{−1}}{2n+2} ⌋ & for i < j; \\ ⌊\frac{π_{j}^{−1}+π_{i}^{−1}}{2n+2} ⌋ & for i ≥ j. \end{matrix}

The value π_{i}^{−1} can be obtained from the fundamental n-tuple since if π_{r} = i+k_{r}(2n+ 2), then π_{i}^{−1} = r−k_{r}(2n+2) while if π_{r} = −i+k_{r}(2n+2), then π_{i}^{−1} = −r+k_{r}(2n+2).

8.2 Locally even subgroups

8.2.1 George group D_{n}

An n-tuple [π_{1}, …, π_{n}] is the fundamental n-tuple of a π ∈ D̃_{n} if and only if it is an even signed permutation, i.e. with an even number of negative values. The action of s_{i} on the fundamental n-tuple is s_{i} = (i i+1) for i = 1, …, n − 1, while s_{0} both changes the sign of and interchanges the values at positions 1 and 2.

The inversion table is given by

inv_{ij}(π) = \{ \begin{matrix}−1 & if i < j and π_{i}^{−1} > π_{j}^{−1}; \\ 1 & if i > j and π_{i}^{−1} < π_{−j}^{−1}; \\ 0 & otherwise. \end{matrix}

In terms of the fundamental n-tuple of π, the length function ℓ(π) is the number of pairs (i, j) that are inversions, plus the number of pairs (−i, j) that are inversions.

8.2.2 George group B̃_{n}

An n-tuple [π_{1}, …, π_{n}] is the fundamental n-tuple of a π ∈ B̃_{n} if and only if it can be written

[τ_{1} + k_{1}(2n + 2), …, τ_{n} + k_{n}(2n + 2)]

where τ ∈ C_{n} and the number ∑_{i=1}^{n} |⌊\frac{−π_{i}+n+1}{2n+2}⌋| is even. The action of s_{i} on the fundamental n-tuple is s_{i} = (i i+1) for i = 1, …, n−1, while s_{0} gives [−π_{2}, −π_{1}, π_{3}, …, π_{n}] and s_{n} gives [π_{1}, …, π_{n−2}, 2n + 2 − π_{n}, 2n + 2 − π_{n−1}]. The inversion table is given by

inv_{ij}(π) = \{ \begin{matrix}⌊\frac{π_{j}^{−1}−π_{i}^{−1}}{2n+2} ⌋ & for i < j; \\ ⌊\frac{π_{j}^{−1}+π_{i}^{−1}}{2n+2} ⌋ & for i > j; \\ ⌊\frac{π_{i}^{−1}}{2n+2}⌋ & for i = j. \end{matrix}

8.2.3 George group D̃_{n}

An n-tuple [π_{1}, …, π_{n}] is the fundamental n-tuple of a permutation π ∈ D̃_{n} if and only if it can be written

[τ_{1} + k_{1}(2n + 2), …, τ_{n} + k_{n}(2n + 2)]

where τ ∈ C_{n} and the numbers ∑_{i=1}^{n} |⌊\frac{−π_{i}+n+1}{2n+2}⌋| and ∑_{i=1}^{n} |⌊\frac{π_{i}}{2n+2}⌋| are both even. The action of s_{i} on the fundamental n-tuple is s_{i} = (i i+1) for i = 1, …, n−1, while s_{0} gives [−π_{2}, −π_{1}, π_{3}, …, π_{n}] and s_{n} gives [π_{1}, …, π_{n−2}, 2n + 2 − π_{n}, 2n + 2 − π_{n−1}]. The inversion table is given by

inv_{ij}(π) = \{ \begin{matrix}⌊\frac{π_{j}^{−1}−π_{i}^{−1}}{2n+2} ⌋ & for i < j; \\ ⌊\frac{π_{j}^{−1}+π_{i}^{−1}}{2n+2} ⌋ & for i > j; \\ 0 & for i = j. \end{matrix}

8.3 A conjecture on inversion tables

We have seen that the inversion table of a permutation in a George group determines the set of class inversions, and hence there is a unique permutation to each inversion table. A natural question to ask is how one can recognize if a given table of integers is the inversion table of a permutation. We conjecture a characterization.

Let us restrict the discussion to C̃_{n}; all cases look about the same. In C̃_{n} we have the inversion table

inv_{ij}(π) = \{ \begin{matrix}⌊\frac{π_{j}^{−1}−π_{i}^{−1}}{2n+2} ⌋ & for i < j; \\ ⌊\frac{π_{j}^{−1}+π_{i}^{−1}}{2n+2} ⌋ & for i ≥ j. \end{matrix}

Now a simple fact,

⌊x⌋ + ⌊y⌋ = ⌊x + y⌋(+1) =^{def} \{ \begin{matrix}⌊x + y⌋ & & or \\ ⌊x + y⌋ + 1 & , \end{matrix}

implies a lot of necessary conditions:

• inv_{ij} + inv_{jk} = inv_{ij}(+1) for i < j < k;

• inv_{ij} + inv_{ki} = inv_{kj}(+1) for i < j ≤ k;

• inv_{ik} + inv_{ji} = inv_{kj}(+1) for i ≤ j ≤ k and i < k;

• inv_{jk} + inv_{ji} = inv_{ki}(+1) for i ≤ j < k.

We conjecture that these necessary conditions are also sufficient. (Last minute note: Jian-Yi Shi [19] has just given an affirmative answer to this conjecture.)

9 Application: the length generating function

Bott (1956) gave a formula for length generating function of affine Weyl groups. Macdonald (and, independently, Reiner) refined the formula, taking into account also the number of times certain generators are used in a reduced word.

In this section we will show how the permutation models of the affine groups and our previous results about them can be applied to give combinatorial explanations to the refined version Bott’s formula. We start with some details about the formulas and their background and proceed with our approach.

9.1 Background

The Poincaré series W (q) of a Weyl group W is the length generating function, i.e.

W (q) =^{def} ∑_{w∈W} q^{ℓ(w)}.

For the finite and affine Weyl groups there are well-known expressions for the Poincaré series in terms of the so called exponents of the groups (see Humphreys [13]).

\begin{matrix}A_{n} & 1, 2, 3, …, n \\ B_{n}, C_{n} & 1, 3, 5, …, 2n − 1 \\ D_{n} & 1, 3, 5, …, 2n − 3, n − 1 \end{matrix}

Table 2: The exponents of the Weyl group families.

Theorem 21 If X_{n} is an irreducible finite Weyl group with exponents e_{1}, …, e_{n}, and X̃_{n} is the corresponding affine Weyl group, then the Poincaré series is

X_{n}(q) = (1 + q + … + q^{e_{1}})(1 + q + … + q^{e_{2}}) ⋯ (1 + q + … + q^{e_{n}})  (1)

for the finite group, and

X̃_{n}(q) = \frac{X_{n}(q)}{(1 − q^{e_{1}})(1 − q^{e_{2}}) ⋯ (1 − q^{e_{n}})},  (2)

for the affine group.

The finite case is easy, and Eq. 1 has a straightforward combinatorial proof for each group. The affine case has been considered much harder. We will refer to Eq.

(2) as Bott’s formula. It was proved by Bott [5] in 1956, as an application of Morse theory to the topology of Lie groups. Although there are several later proofs (see references in [13]), none of them catches the simple combinatorial flavor of the finite case. For the special case of Ã_{n}, though, there are at least two combinatorial proofs of Bott’s formula to be found in the literature, by Björner and Brenti [3] and by Ehrenborg and Readdy [9]. For the case of C̃_{n}, a very involved combinatorial proof follows from the work of Bousquet-Mélou and K. Eriksson [6].

9.2 The refined formula

Two Coxeter generators s and s′ are conjugated if they are connected in the Coxeter graph by a path of edges with odd labels. (Recall that no label means label 3, so it is odd.)

In general, the number of occurrences of a given generator s in a reduced word for w is not invariant but depends on the choice of the reduced word. However, the number of occurrences of generators from a given conjugacy class is indeed independent of the particular reduced word.

Bott’s formula was refined by Macdonald [15] and Reiner [17], taking into account not only the length ℓ(w) of an element but also the number of times each conjugacy class of generators is used in a reduced word for w. For the ABCD-families the refinement is is very easy to describe. Coxeter graphs of type A and D have no edges with even labels so there is only one conjugacy class and hence no refinement is possible. The Coxeter graph of B̃_{n} has one edge labeled 4, making the generator s_{0} a conjugacy class of its own. Similarly, the Coxeter graph of C̃_{n} has two edges labeled 4, so here both s_{0} and s_{n} constitute separate conjugacy classes.

Let a(w) and b(w) denote the number of occurrences of s_{0} and s_{n} respectively in a reduced word for w. Then the refined formula for the finite group is

B_{n}(q, t) = C_{n}(q, t)q^{ℓ(w)}t^{a(w)}
= (1 + tq)(1 + tq^{2}) ⋯ (1 + tq^{n})(1 + q)(1 + q + q^{2}) ⋯ (1 + q + … q^{n−1}).

As in Bott’s original formula, the series for the affine group can be expressed using the polynomial for the finite group. For C̃_{n} we have the additional parameter b(w) to consider.

Theorem 22 (Macdonald, Reiner) The following refined versions of Bott’s formula hold.

B̃_{n}(q, t)q^{ℓ(w)}t^{a(w)} = B_{n}(q, t)\frac{(1 + q)(1 + q^{2}) ⋯ (1 + q^{n−1})}{(1 − tq^{n})(1 − tq^{n+1}) ⋯ (1 − tq^{2n−1})}  (3)

and

C̃_{n}(q, t, u)q^{ℓ(w)}t^{a(w)}u^{b(w)} = C_{n}(q, t)\frac{(1 + uq)(1 + uq^{2}) ⋯ (1 + uq^{n})}{(1 − utq^{n+1})(1 − utq^{n+2}) ⋯ (1 − utq^{2n})}. (4)

9.3 Our approach

We will now show how the model of the affine groups Ã_{n−1}, B̃_{n}, C̃_{n} and D̃_{n} as infinite permutations can be used to give combinatorial proofs of the refined version of Bott’s formula for these cases.

Let the quotient X̃_{n}/X_{n} be identified with the set of its minimal coset representatives. Then the Poincaré series factorizes:

X̃_{n}(q) = X_{n}(q) · X̃_{n}/X_{n}(q),

so Bott’s formula can equivalently be stated as

X̃_{n}/X_{n}(q) = \frac{1}{(1 − q^{e_{1}})(1 − q^{e_{2}}) ⋯ (1 − q^{e_{n}})}.

This is the generating function for integer partitions into parts in {e_{1}, e_{2}, …, e_{n}}. We will describe bijections from quotient groups to sets of partitions, starting with Ã_{n}. Then the other bijections (for C̃_{n}, B̃_{n} and D̃_{n}) are all constructed basically in the same way, with slight modifications according to the different types of mirrors.

9.4 Proof of Bott’s formula for Ã_{n}

The parabolic subgroup A_{n} of Ã_{n} permutes the numbers within the position segment [1, n+1] (and (n+1)-periodically). Thus, the minimal coset representatives of Ã_{n}/A_{n} are the permutations in Ã_{n} that are increasing in the position segment [1, n+1]. Any such permutation that is not the identity must have a descent between positions n + 1 and n + 2, so the class adjacent transposition s_{n+1}, that switches positions (n + 1, n + 2) (and periodically) is length decreasing.

We shall now present a map λ from the above quotient to finite sequences of positive integers, such that ℓ(w) = |λ(w)| (the sum of the integers in the sequence).

Definition Let w be a minimal coset representative in Ã_{n}/A_{n}. We shall construct a finite sequence λ(w) = (δ_{1}, δ_{2}, …) of positive integers by sorting w (eventually reaching the identity permutation) in a certain way and recording the decrease in length for each step. When step i starts we will have the position segment [i, n + i] in increasing order and a descent between n + i and n + i + 1. In step i we move the number at position n + i + 1 as many positions to the left as needed, say δ_{i}, to have the position segment [i + 1, n + i + 1] in increasing order. We record for each step i the length decrease δ_{i}.

We give an example for Ã_{3} showing the segment [i, 3+i] in each step and recording the sequence of length decreases. By periodicity, the number to be moved into the segment is 4 plus the number at position i.

[−5, 1, 6, 8] ⟶^{δ_{1}=3} [−1, 1, 6, 8]
⟶^{δ_{2}=2} [1, 3, 6, 8]
⟶^{δ_{3}=2} [3, 5, 6, 8]
⟶^{δ_{3}=1} [5, 6, 7, 8]

□

Obviously, we have ℓ(w) = |λ(w)|. We shall now see what λ(w) must look like.

Lemma 23 λ is a bijection from Ã_{n}/A_{n} to the set of integer partitions into parts of sizes in {1, 2, 3, …, n}.

Proof In step i, we move the number x_{i} at position n + i + 1 to its proper place within the segment [i+1, n+i+1]. The length decrease δ_{i} is the number of positions that the number has been moved to the left, so 1 ≤ δ_{i} ≤ n. Since the permutation was increasing in the segment [i, n + i] and periodically, we know that after the ith step, the next number to be moved, x_{i+1} now at position n + i + 2, is greater than the one just moved. x_{i}, and will hence stop at a position to the right of it. Hence δ_{i} ≥ δ_{i+1}. This proves that λ(w) is a partition of the right kind.

It is furthermore easy to see that for any such partition λ = (δ_{1}, …, δ_{b}) the process is invertible. Start with the identity permutation and consider the segment [b + 1, n + b + 1]. After the number at position n + b + 1 − δ_{b} is moved δ_{b} positions to the right we now have an increasing segment [b, n + b]. Continue in this way for b steps and we will end up with a permutation whose segment [1, n + 1] is increasing, and hence is a member of Ã_{n}/A_{n}.

□

The exponents for A_{n} is 1, 2, …, n. Consequently, the above lemma proves Bott’s formula for Ã_{n}.

9.5 Proof of Bott’s formula for C̃_{n}

The parabolic subgroup C_{n} of C̃_{n} permutes the numbers within the position segment [−n, n] (and (2n+2)-periodically). Thus, the minimal coset representatives of C̃_{n}/C_{n} are the permutations in C̃_{n} that are increasing in the position segment [−n, n]. Any such permutation that is not the identity must have a descent between positions n and n + 1, so the class adjacent transposition s_{n}, that switches (n, n + 2) and periodically, is length decreasing.

As in the A case, we will obtain a bijective map λ from the quotient group to a certain set of integer partitions by recording the length decreases in each step a sorting procedure. Unlike the A case, we now have a fixed segment [−n, n] that we consider.

Definition Let w be a minimal coset representative in C̃_{n}/C_{n}. In each step of the sorting procedure we start with the length decreasing class adjacent transposition s_{n} that inserts the number at position n + 2 into the segment [−n, n]. Then we use only length decreasing class adjacent transpositions among s_{0}, …, s_{n−1} to get to the next minimal coset representative; in other words, we sort the segment [−n, n]. We record for each step i the length decrease δ_{i}.

We give an example for C̃_{2} showing the segment [−2, 2] in each step and recording the sequence of length decreases. The number to be moved into the segment is 6 plus the number at position −2.

[−17, −4, 0, 4, 17] ⟶^{δ_{1}=4} [−11, −4, 0, 4, 11]
⟶^{δ_{2}=4} [−5, −4, 0, 4, 5]
⟶^{δ_{3}=2} [−4, −1, 0, 1, 4]
⟶^{δ_{4}=1} [−2, −1, 0, 1, 2]
□

Lemma 24 λ is a bijection from C̃_{n}/C_{n} to the set of integer partitions with parts in {1, 2, …, 2n} and at most one part of each size up to n. If a(w) and b(w) denote the number of occurrences of s_{0} and s_{n} respectively in a reduced word for w, then the partition λ(w) will have a(w) parts greater than n and b(w) parts in total.

Proof In step i, we insert a number x_{i} into the segment [−n, n]. The length decrease δ_{i} is the number of non-mirror positions that the number has been moved to the left, so 1 ≤ δ ≤ 2n. Negative numbers will be moved to the left of position zero, giving δ ≥ n+1 (and using s_{0} once), while positive numbers will stop to the right of position zero, giving δ ≤ n (and not using s_{0}).

Since the permutation is increasing in the segment [−n, n] and periodically, we know that after the ith step, the next number to be moved, x_{i+1}, is greater than the one just moved, x_{i}, and will hence stop at a position to the right of it. Now we must distinguish two cases: If x_{i} was positive, then it will not move during the next step, so x_{i+1} will stop earlier than x_{i} did, wherefore δ_{i} > δ_{i+1}. However, if x_{i} was negative, then it will move one position to the left during the next step if x_{i+1} is moved past the positive mirror image of x_{i}; hence, the x_{i+1} might stop at the same position as the x_{i} did, so δ_{i} ≥ δ_{i+1}.

To conclude that λ(w) is a partition of the right kind, we must also verify that the number of parts greater than n is a(n) and that the total number of parts is b(n). But this is clear, as the generator s_{0} is used precisely once for every negative number that is inserted while s_{n} is used once in every step.

Finally, as in case A it is easy to verify that for any such partition λ the process is invertible.

□

The above lemma can be summed up in the following three-variable generating function identity:

C̃_{n}/C_{n}(q, t, u)q^{ℓ(w)}t^{a(w)}u^{b(w)} = \frac{(1 + uq)(1 + uq^{2}) ⋯ (1 + uq^{n})}{(1 − utq^{n+1})(1 − utq^{n+2}) ⋯ (1 − utq^{2n})}. (5)

This is of course equivalent with Eq. 4, the refined version of Bott’s formula for C̃_{n}.

9.6 Proof of Bott’s formula for B̃_{n}

The situation is the same for B̃_{n} as for C̃_{n}, except for the fact that s_{n} moves the number at position n + 2 directly to position n − 1, and simultaneously takes the number at position n + 3 to position n. Here it is necessary to separate two cases: the smallest number to the right of the mirror at n + 1 is of course at position n + 2, but the second smallest one may be either the number next to it, at position n + 3, or the number one period later, at position n + 2 + (2n + 2).

Definition Let w be a minimal coset representative in B̃_{n}/B_{n}. We shall sort w in two phases. The first phase continues as long the two smallest numbers to the right of the mirror at n + 1 are at positions n + 2 and n + 2 + (2n + 2). A step in the algorithm is to sort these two numbers into the segment in turn, and record their respective contributions to the length decrease, δ_{2i−1}, δ_{2i} in step i. Say that the first phase goes on for k steps.

In the second phase, the two smallest numbers to the right of the mirror at n + 1 are at positions n + 2 and n + 3. We record in each step i of the second phase the two length decreases δ_{2k+2i−1}, δ_{2k+2i} from sorting the two inserted numbers into the segment respectively, counting the use of s_{n} as contributing to δ_{2k+2i−1} and s_{n−1} as contributing to δ_{2k+2i}.

We give an example for B̃_{3} showing the segment [−3, 3] in each step and recording the sequence of length decreases. The numbers to be moved into the segment is 8 plus the numbers at positions −3 and −2.

First phase:

[−43, −14, −5, 0, 5, 14, 43] ⟶^{δ_{1}=5,δ_{2}=5} [−25, −14, −5, 0, 5, 14, 25]
⟶^{δ_{3}=5,δ_{4}=4} [−14, −9, −5, 0, 5, 9, 14]

Second phase:

[−14, −9, −5, 0, 5, 9, 14] ⟶^{δ_{5}=4,δ_{6}=3} [−6, −5, −1, 0, 1, 5, 6]
⟶^{δ_{7}=1,δ_{8}=0} [−3, −2, −1, 0, 1, 2, 3]
□

Lemma 25 λ is a bijection from B̃_{n}/B_{n} to the set of integer partitions with parts in {1, 2, …, 2n − 1} and at most one part of each size up to n − 1. If a(w) denote the number of occurrences of s_{0} in a reduced word for w, then the partition λ(w) will have a(w) parts greater than n − 1.

Proof In step i in the first phase, we take the numbers at positions n + 2 and n + 2 + (2n + 2), say x_{i} and x_{i} + (2n + 2), and inserts them into the segment [−n, n]. Since x_{i} + (2n + 2) is the second smallest element to right of n + 1, we know that x_{i} will be sorted to the leftmost position in the segment and hence its contribution to the length decrease is δ_{2i−1} = 2n − 1 (and not 2n, thanks to the jumping start). If then x_{i} + (2n + 2) is sorted to the leftmost position as well, phase two may go on; otherwise, it is easily verified that we must now shift to the second phase.

In the second phase we record in each step the movement of the two inserted numbers, which both, thanks to their jumping start, will be moved at most 2n − 2 times by class adjacent transpositions. Similarly, it takes only n switches for each of these numbers to reach to the negative side. Now we can copy the argument from the case of C̃_{n}/C_{n}.

□

The above lemma can be summed up in the following two-variable generating function identity:

B̃_{n}/B_{n}(q, t)q^{ℓ(w)}t^{a(w)} = \frac{(1 + q)(1 + q^{2}) ⋯ (1 + q^{n−1})}{(1 − tq^{n})(1 − tq^{n+1}) ⋯ (1 − tq^{2n−1})}.  (6)

This is equivalent with Eq. 3, the refined version of Bott’s formula for B̃_{n}.

9.7 Proof of Bott’s formula for D̃_{n}

The situation for D̃_{n} is similar to B̃_{n}, with the exception that also s_{0} is of type D, switching (−2, 1) and (−1, 2) and periodically. Here the parabolic subgroup D_{n} may sometimes not be able to sort the entire segment [−n, n]; the minimal coset representatives of D̃_{n}/D_{n} are the permutations in D̃_{n} that are increasing in the position segment [−n, n] except possibly in the subsegment [−1, 1]. Define the map λ in analogy with the previous section.

Lemma 26 λ is a bijection from D̃_{n}/D_{n} to the set of integer partitions with parts in {1, 2, …, 2n − 2} and at most one part of each size up to n − 2, and possibly with one of the parts of size n − 1 marked with a dot.

Proof The difference from the case of B̃_{n}/B_{n} is that now the numbers get to jump in the middle of the segment too. Hence, each will be moved at most 2n − 2 times in total, and it takes only n − 1 switches for each of these numbers to reach to the negative side, since s_{1} is not needed before using s_{0} in order to get to the negative side. However, if a number is positive and is to be placed directly to the right of zero, we will use s_{1} and record a “dotted” length decrease of n − 1. Now we can follow the argument of case B̃_{n}/B_{n}. .

□

The above lemma can be summed up in the following generating function identity:

D̃_{n}/D_{n}(q)q^{ℓ(w)} = \frac{(1 + q)(1 + q^{2}) ⋯ (1 + q^{n−1})}{(1 − q^{n−1})(1 − q^{n}) ⋯ (1 − q^{2n−2})}.  (7)

However, Bott’s formula demands another equality:

D̃_{n}/D_{n}(q) = \frac{1}{(1 − q^{1})(1 − q^{3}) ⋯ (1 − q^{2n−3})(1 − q^{n−1}} .  (8)

To see that the formulas (7) and (8) are equivalent we need one final bijection.

Lemma 27 We have the generating function identity

\frac{1}{(1 − q^{1})(1 − q^{3}) ⋯ (1 − q^{2n−3})} = \frac{(1 + q)(1 + q^{2}) ⋯ (1 + q^{n−1})}{(1 − q^{n})(1 − q^{n+1}) ⋯ (1 − q^{2n−2})}.

Equivalently, the set I of integer partitions into parts of sizes in {1, 3, …, 2n−3} is in bijection with the set J of integer partitions into parts of sizes in {1, 2, 3, …, 2n − 2} with at most one part of each size up to n − 1.

Proof A bijection can be described in the following way. As long as there are two equal parts of some size k ≤ n − 1, merge them into one part of size 2k. Clearly this process gives a map from I to J and it is a bijection since we have the following inverse map from J to I. As long as there is an even part 2k, split it into two parts of size k. □

References

[1] R. Bédard, Cells for two Coxeter groups, Comm. Algebra 14 (1986), 1253– 1286.

[2] A. Björner, Orderings of Coxeter groups, in Combinatorics and Algebra, Contemporary Math. 34, Amer. Math. Soc., 1984, pp. 175–195.

[3] A. Björner and F. Brenti, Affine permutations of type A, Electronic Journal of Combinatorics 3 no. 2 (1996), #R18.

[4] A. Björner and F. Brenti, Combinatorics of Coxeter groups, book manuscript draft, 1994.

[5] R. Bott, An application of the Morse theory to the topology of Lie-groups, Bull. Soc. Math. France 84 (1956), 251–281.

[6] M. Bousquet-Mélou and K. Eriksson, Lecture hall partitions, Ramanujan Journal, 1 (1997), 101–111.

[7] F. Brenti, q-Eulerian polynomials arising from Coxeter groups, European J. Combinatorics 15 (1994), 417–441.

[8] V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function, Invent. Math. 39 (1977), 187–198.

[9] R. Ehrenborg and M. Readdy, Juggling and applications to q-analogues, Discrete Math., 157 (1996), 107–125.

[10] C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. Math. 35 (1934), 396–443.

[11] H. Eriksson, Computational and combinatorical aspects of Coxeter groups, PhD thesis, KTH, Stockholm, Sweden, 1994.

[12] K. Eriksson, Polygon posets and the weak order of Coxeter groups, J. Algebraic Comb. 4 (1995), 233–252.

[13] J. Humphreys, Reflection groups and Coxeter groups, Cambridge Univ. Press, 1990.

[14] G. Lusztig, Some examples of square integrable representations of semisimple p-adic groups, Trans. Amer. Math. Soc. 277 (1983), 623–653.

[15] I. G. Macdonald, The Poincaré series of a Coxeter group, Math. Ann. 199 (1972) 161–174.

[16] R. Proctor, Classical Bruhat orders and lexicographic shellability, J. Algebra 77 (1982), 104–126.

[17] V. Reiner, The distribution of descents and length in a Coxeter group, Electronic Journal of Combinatorics 2 (1995), R25.

[18] J.Y. Shi, Some results relating two presentations of certain affine Weyl groups, J. Algebra 163 (1994), 235–257.

[19] J.Y. Shi, On two presentations of the affine Weyl groups of the classical types, preprint 1998.