Ordering the affine symmetric group

Alain Lascoux

C.N.R.S., Institut Gaspard Monge, Université de Marne-la-Vallée, 5 Bd Descartes, Champs sur Marne, 77454 Marne La Vallée Cedex 2 FRANCE Alain.Lascoux@univ-mlv.fr

Abstract. We review several descriptions of the affine symmetric group. We explicit the basis of its Bruhat order.

1 Introduction

For a group defined by generators, one has a notion of Cayley graph representing the succesive generation of elements of the group by product of generators. This is specially interesting in the case of a Coxeter group (W, S), S being the set of generators, because one has a length function which filters the elements of W according to the minimum length of the words in the generators of W which expresses them (words of minimum length are called reduced decompositions).

The Cayley graph of W naturally provides an ordering (the weak order) of W: w′ ≤ w iff any reduced decomposition of w′ is the left factor of at least one reduced decomposition of w, in other words, iff there is a path from w′ to w in the Cayley graph of W.

However, if one takes the group algebra of W instead of W, and a reduced decomposition [i, j, …, h] := s_{i}s_{j} ⋯ s_{h} of an element w, then one wants the order to be such that any expression of the type (1 + s_{i})(1 + s_{j}) ⋯ (1 + s_{h}) has leading term (with respect to the order) w.

In that case, it is clear that the expansion of (1 + s_{i}) ⋯ (1 + s_{h}) involves only the elements obtained by evaluating in W the subwords of [i, j, …, h]. One easily checks that the set of such elements is independent of the choice of a reduced decomposition of w (though the set of subwords is not).

Let us write w′ ≤ w (for the Bruhat order) iff there exists a decomposition of w′ which is a subword of a reduced decomposition of w. Let us also write [1, w] for the interval {w′ | 1 ≤ w′ ≤ w}, 1 being the identity element of W.

The above definition of the Bruhat order [2] is not very efficient, since one has much too many subwords of a reduced decomposition of w compared to the cardinality of [1, w].

Ehresmann[4] found another definition, in the case of the symmetric group, by using all the projections W ⟶^{p_{i}} W/W_{i} onto all the quotient spaces W/W_{i} ( W_{i}= maximal parabolic, i.e. group generated by the elements of S \ s_{i}). Ehresmann’s definition is

w′ ≤ w ⇔ p_{i}(w′) ≤ p_{i}(w) , i = 1, 2, …  (1)

Now, it makes sense because one has an easy description of the Bruhat order on W/W_{i} and of the projection. In the case of the symmetric group, W/W_{i}, as an ordered set, can be identified with the space of all partitions, the diagram of which are included in a fixed rectangle (the order on partitions being inclusion of diagrams).

This description has been generalized by Deodhar[3] to all Coxeter groups. In [12], M.P. Schützenberger and I gave another description. It uses a

notion which is valid for any ordered set X. One defines the basis B of X to be the following subset:

b ∈ B ⇔ ∃ x ∈ X, b is minimum in the complement of [1, x] . (2)

Given x ∈ X, let furthermore B(x) denote the set {b ∈ B, b ≤ x}. We have shown in [LS] that in the case X is finite, then

x ≤ y ⇔ B(x) ⊆ B(y) .  (3)

Now, it happens that in the case of a Coxeter group W the set B(w) is ”small” compared to [1, w] or to the set of subwords of a reduced decomposition of w ∈ W.

The bases of the symmetric group and of the hyperoctahedral group, as well as the map w ↦ B(w) are given in [12]. Geck and Kim [8] have determined the bases of all finite Coxeter groups.

The construction of bases passes to the quotient spaces W/W_{i} (and, as we have said, it is sufficient to treat only these spaces, because of (1)). For example, for the symmetric group 𝔖_{n}, its quotient 𝔖_{n}/𝔖_{m} × 𝔖_{r}, n = m + r, can be identified with the set of partitions contained in m^{r}, and its basis consists of all (non void) rectangular partitions i^{j}: i ≤ m, j ≤ r. The elements of the basis have in fact a geometrical meaning, being in correspondence with determinantal varieties [10].

Now, the notion of a basis can be extended to infinite sets X, when X satisfy some mild hypotheses.

Let us take an affine Coxeter group. Then one still has a length function, which allow to filter the group according to length. Let W^{ℓ} be the set of elements of length ≤ ℓ. If ℓ(w) ≤ ℓ, then the full interval [1, w] is contained in W^{ℓ}. Let B^{ℓ} be the basis of W^{ℓ}.

One has that B = ∪B^{ℓ} and one can check that

w′ ≤ w ⇔ B(w′) ⊆ B(w) .  (4)

In the following, we shall describe the basis of the affine symmetric group 𝔖̃_{n} and its Bruhat order.

2 The Affine Symmetric Group

Let n be an integer and 𝔖̃_{n} be the quotient of the infinite symmetric group (generated by s_{i}, i ∈ ℤ under the relations s_{i} = s_{i+n}), i ∈ ℤ. In other words, 𝔖̃_{n} is generated by s_{0}, … s_{n−1} satisfying the braid relations (with s_{n} := s_{0})

s_{i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1} , s_{i}s_{j} = s_{j}s_{i} , |i − j| ≅ 1̸ mod n , 0 ≤ i, j ≤ n − 1.(5)

The group 𝔖̃_{n} can be thought as acting on infinite vectors v = […, v_{i}, …], i ∈ ℤ: the generator s_{i} transposes in v components v_{i+kn}, v_{i+1+kn} for all k ∈ ℤ simultaneously. Usually, one takes vectors v such that v_{i+n} = v_{i} + n, i ∈ ℤ. Associating to the identity element the “vacuum vector”▷ : ▷_{i} = i, ∀i ∈ ℤ, then the orbit of ▷ is in bijection with 𝔖̃_{n} and one can code any element σ ∈ 𝔖̃_{n} by the image v = ▷ σ of ▷ under σ, or equivalently by the window [v_{1}, …, v_{n}].

In other words, elements of 𝔖̃_{n} can be coded by vectors in ℤ^{n}, starting from [1, 2, …, n], with the action

\begin{aligned}[⋯ v_{i}, v_{i+1} ⋯] s_{i} & = [⋯ v_{i}, v_{i+1} ⋯] , 1 ≤ i ≤ n − 1 \\ [v_{1} , …, v_{n}] s_{0} & = [v_{n} − n , …, v_{1} + n] . \end{aligned}  (6)

One has in fact many other choices to represent 𝔖̃_{n} by infinite vectors satisfying periodicity conditions. One can also modify the definition of “transposing two adjacent components”.

For example, let c(▷) be the infinite vector with all components equal to 0, and let c(σ) be the image of c(▷) under the action

[⋯ c_{j}, c_{j+1} ⋯] s_{i} = [⋯ c_{j+1} + 1, c_{j} ⋯] , 1 ≤ i ≤ n − 1, c_{i} ≤ c_{i+1}, ∀j ≅ i mod n . (7)

This action preserves equalities c_{j} = c_{j+n}, and once more, one can restrict vectors to their components 1, …, n. In that set-up, one has

[c_{1} , …, c_{n}] s_{0} = [c_{n} , …, c_{1} + 1] , c_{n} ≤ c_{1} .  (8)

Now, it is easy to check that the mapping 𝔖̃_{n} ∋ σ ↦ [c_{1}, …, c_{n}] ∈ ℕ^{n} is a bijection. It can be easily described without passing through a reduced decomposition of σ (cf. [1]).

By restriction, it induces a bijection from 𝔖_{n} onto the set of vectors such that c_{1} ≤ n − 1, …, c_{n} ≤ 0. Such a vector is called the Lehmer code of the corresponding permutation σ [9] and encodes the “inversions”of σ. This is still true in the infinite case (cf. [1], [5]). Let us call scalar weight of c(σ) the sum c_{1} + ⋯ + c_{n}. Then the above action shows that the scalar weight increases by 1 if length increases, and thus the scalar weight of c(σ) is equal to the length ℓ(σ). Shi [14] gives another description of the length function, directly from the window of σ.

3 Quotient of 𝔖̃_{n} modulo 𝔖_{n}

Since all s_{i}’s play a symmetrical rôle, all quotient spaces of 𝔖̃_{n} modulo a maximal parabolic are isomorphic. Let us choose the finite symmetric group 𝔖_{n}, generated by s_{1}, …, s_{n−1}, as a maximal parabolic.

The unique element of minimum length of a class σ 𝔖_{n} is the unique element ζ of the class such that

ℓ(ζ s_{i}) < ℓ(ζ) ⇔ i = 0 .

Therefore, minimum elements are exactly those elements with (strictly) increasing window [v_{1}, …, v_{n}] : v_{1} < v_{1} < ⋯ < v_{n}.

From (2.3) one deduces that codes of such elements are (weakly) increasing vectors [c_{1}, c_{2}, …, c_{n}] such that c_{1} = 0, that is, are partitions of length ≤ n − 1.

Now, there is a third coding of 𝔖̃_{n}/𝔖_{n} by infinite vectors u, with periodicity u_{j+n} = u_{j} − 1, ∀j ∈ ℤ. It amounts to take origin vector such that [u_{1}, …, u_{n}] = [ 0, …, 0 ], and act by

\begin{matrix}[⋯ u_{i}, u_{i+1} ⋯] ⟶^{s_{i}} & [⋯ u_{i+1} , u_{i} ⋯] , 1 ≤ i ≤ n − 1 , \\ [u_{1}, …, u_{n}] ⟶^{s_{0}} & [u_{n} + 1, …, u_{1} − 1] . \end{matrix}  (9)

From a vector u in ℤ^{n} such that u_{1} + ⋯ + u_{n} = 0 (call weight such a vector), one can recover an element of 𝔖_{n}\𝔖̃_{n} as follows (the quotient is now on the left): one has to sort increasingly the vector [1 + nu_{1}, …, n + nu_{n}].

For example, n = 3, u = [7, −4, −3] gives the vector [22, −10, −6] = [1 + 3 × 7, 2 − 3 × 4, 3 − 3 × 3] which is sorted into [−10, −6, 22], and is an element of 𝔖̃_{3} of minimum length (of code [0, 1, 19]) in its coset modulo 𝔖_{3}.

B. Leclerc has shown me that it is more convenient, in the theory of roots of affine Weyl groups, to add an “imaginary root”and use “extended weights”which are vectors in ℤ^{n+1} : one takes for origin [0, …, 0] ∈ ℤ^{n+1} and the action is

\begin{matrix}[⋯ w_{i}, w_{i+1} ⋯] ⟶^{s_{i}} & [⋯ w_{i+1} , w_{i} ⋯] , 1 ≤ i ≤ n − 1 , \\ [w_{1}, …, w_{n}, w_{n+1}] ⟶^{s_{0}} & [w_{n} + 1, …, w_{1} − 1, w_{1} − w_{n} + w_{n+1} − 1] . \end{matrix} (10)

A weight u ∈ ℤ^{n} already has an unnecessary component, since the sum of components is zero : one can write u = x_{1}α_{1} + ⋯ + x_{n−1}α_{n−1}, the α_{i} being the simple roots [1, −1, 0, …, 0], …, [0, …, 0, 1, −1].

However, it happens that going to ℤ^{n+1} simplifies some constructions, the extra component having combinatorial interpretations.

4 n-Cores and Bruhat order

None of these three codings furnishes a description of the Bruhat order. Fortunately, Fock spaces and crystal graphs indicate a fourth one ([13], [11], [6]).

Now one will represent elements of 𝔖̃_{n}/𝔖_{n} by partitions which are n-cores, that is partitions such that one cannot erase a border strip (also called outer ribbon) of length n from their diagram (cf. [7]).

One numbers diagonals of diagrams with the numbers (which are called colours) 0, 1, …, n − 1 periodically, the main diagonal being of colour 0.

Now, take the diagram of a an n-core such that no corner box is of colour i. Then the action of s_{i}, i = 0, …, n−1 on this diagram is to add all possible boxes which are of colour i, in such a way that the resulting object is still the diagram of a partition. If there is at least one corner box of colour i, then the action consists in erasing all peripheal boxes of colour i such that one still gets a diagram of a partition.

It is an easy combinatorics to check that from an n-core one still gets an n-core, and that the operation is involutive. Now, one does not try to check the braid relations, because one takes the classics again ([7] p.78) and one sees that one can use, instead of an n-core, still another object which is called abacus.

Let ♢ be a (decreasing) partition extended to infinity on the right by 0’s: ♢ = [♢_{1}, ♢_{2}, …, ♢_{k}, 0, 0, …]. Let A be the set of numbers {♢_{1} − 0, ♢_{2} − 1, ♢_{3} − 2, … } interpreted as balls in an abacus of width n and bi-infinite height, with places numbered consecutively as follows:

\begin{matrix}⋮ & ⋯ & ⋮ & ⋮ & level \\ 1 − 2n & ⋯ & −n − 1 & −n & −1 \\ 1 − n & ⋯ & 1 & 0 & 0 \\ 1 & ⋯ & n − 1 & n & 1 \\ n + 1 & ⋯ & 2n − 1 & 2n & 2 \\ ⋮ & ⋯ & ⋮ & ⋮ & ⋮ \end{matrix} .

Putting balls in positions belonging to A gives by definition the n-abacus of the partition ♢.

That ♢ be an n-core is equivalent to the fact that balls are vertically packed upwards ([7] p.80).

Reading levels of bottom balls, one gets a vector in u ∈ ℤ^{n} such that u_{1} + ⋯ + u_{n} = 0, that is, one gets a weight. This construction is, indeed, a bijection between weights in ℤ^{n} and n-cores or elements of 𝔖_{n}\𝔖̃_{n} or of 𝔖̃_{n}/𝔖_{n}.

For example, the 5-core [4, 2^{3}, 1^{4}] gives by substraction the infinite vector

[4, 1, 0, −1, −3, −4, −5, −6, −8, −9, …]

and the abacus

level
−14 −13 −12 −11 −10 −2
−9 −8 · −6 −5 −1
−4 −3 · −1 0  0
1 · · 4 ·  1

the weight [1, 0, −2, 1, 0], the code [0, 1, 2, 2, 4] and the element [−7, 2, 5, 6, 9] of 𝔖̃_{5}/𝔖_{5}.

For each of the different objects that have been given, the description of the action of the simple generators s_{i} allows to prove that the above constructions are indeed bijections and that the elementary operations represent the generators of 𝔖̃_{n}.

Now each of the objects that we have displayed will provide informations about the corresponding element of the affine group, information which would sometimes not have been easy to get in another description, though all bijections here are elementary. For example, it is amusing to look at what becomes the addition of weights (plain addition of vectors) in terms of n-cores, or of codes.

Here is some example computed with ACE [15], where we give a chain of elements of 𝔖̃_{4}/𝔖_{4}, with their code, the corresponding extended weight in ℤ^{5} and the 4-core with its colours. The reader should beware that simple transpositions act from the left on codes and on group elements, and from the right on weights and cores.

\begin{matrix}Code \\ Group element \\ Ext. weight \\ Core \\ Diagram \end{matrix} [0, 1, 2, 7] ; [−6, 1, 4, 11] ; [0, −2, 2, 0, −4] ; [7, 4, 2, 2, 1, 1, 1] ; 2 3 0 1 2 2 3 3 0 1 2 0 1 2 3 0 1 2 ⟶^{s_{1}}  [0, 2, 2, 7] ; [−7, 2, 4, 11] ; [−2, 0, 2, 0, −4] ; [7, 4, 2, 2, 2, 1, 1, 1] ; 1 2 3 0 1 1 2 2 3 3 0 1 2 0 1 2 3 0 1 2 ⟶^{s_{3}}

[0, 2, 2, 8] ; [−7, 2, 3, 12] ; [−2, 0, 0, 2, −4] ; [8, 5, 2, 2, 2, 1, 1, 1] ; 1 2 3 0 1 1 2 2 3 3 0 1 2 3 0 1 2 3 0 1 2 3 ⟶^{s_{0}}  [0, 2, 2, 9] ; [−8, 2, 3, 13] ; [3, 0, 0, −3, −9] ; [9, 6, 3, 2, 2, 2, 1, 1, 1] ; 0 1 2 3 0 0 1 1 2 2 3 0 3 0 1 2 3 0 0 1 2 3 0 1 2 3 0 ⟶^{s_{3}}  [0, 2, 3, 9] ; [−9, 2, 4, 13] ; [3, 0, −3, 0, −9] ; [9, 6, 3, 3, 2, 2, 2, 1, 1, 1] ; 3 0 1 2 3 3 0 0 1 1 2 3 2 3 0 3 0 1 2 3 0 0 1 2 3 0 1 2 3 0

For what concerns the Bruhat order, we shall see that we need n-cores. Codes, which are also (increasing) partitions for minimum elements in their coset modulo 𝔖_{n}, would not give (by inclusion) the proper order, but only a sub-order. Björner and Brenti ([1], th 6.3 and th.6.5) obtained a criterium describing the Bruhat order in terms of monotonous functions; it is equivalent to the following proposition.

Let us denote by C the morphism from 𝔖̃_{n}/𝔖_{n} (identified with the set of elements of 𝔖̃_{n} whicht are of minimum length in their coset) onto n-cores.

Proposition 1. Let σ, ω ∈ 𝔖̃_{n}/𝔖_{n}. Then σ ≤ ω iff the diagram of C(σ) is contained in the diagram of C(ω).

Proof. Take any corner of the diagram of C(ω) and let i be its colour. Then s_{i} ω < ω and one knows that ([2], [3])

σ ≤ ω ⇔ min(s_{i}σ, σ) ≤ s_{i}ω

Now, we have to compare two n-cores with less boxes, and as in the finite case, we are finally reduced to know how to compare two elements of length differing by 1.

5 Basis of the Bruhat order

When one needs to store huge sets of elements of the affine group, together with the information about the Bruhat order, then it is not efficient to also store the associated partitions ( for an element in 𝔖̃_{n}, we need n partitions, because we have n different projections 𝔖̃_{n} ↦ 𝔖̃_{n}/𝔖_{n}). It is well illustrated by Geck and Kim [8], in the finite case, that one has instead to use the basis of the order, as defined above. In this section we shall determine the basis of 𝔖̃_{n}/𝔖_{n}.

Let us first introduce some special n-cores.

Given two strictly positive numbers p, q such that p + q = n, a (p, q)- staircase is a partition E such that the stairs of its diagram are all of heigth p and width q, except for the top stair which is of width ≤ q and the bottom stair which is of heigth ≤ p.

In other words, E = [E_{1}, E_{2}, …, E_{k}, 0, …], the non zero differences E_{i} − E_{i+1} are all equal to q, except possibly for the last one E_{k} − 0 which is such that 1 ≤ E_{k} ≤ q, and the partition conjugate to E (obtained by transposing the axes) satisfies the same conditions with p instead of q.

Let us notice that all the corners of a staircase have the same colour, and that, given (p,q) and a point in the Cartesian quadrant ℕ × ℕ, there existis one and only one (p, q)-staircase having this point as a corner.

Let D be the diagram of an n-core, and △ one of its corners. ▽ the maximal box of D on the first diagonal of the same colour above (resp. below) the diagonal containing △ (if it exists). Define the left-rectrix (resp. rightrectrix) of D of pivot △ to be the staircase having △ and ▽ as corners. n-Cores which are too small to have two diagonals of the same colour are in fact staircases. Let us say in that case that they have only one rectrix which coincide with themselves.

For the 4-core [5, 4, 3, 2, 1, 1, 1], here is an example of a left-rectrix (figured by ♡’s):

2 3 0 1 2 2 3 0 3 0 1 2 0 1 2 3 0 ↦ \begin{matrix}2 \\ 3 \\ ▽ \\ 1 & 2 \\ 2 & 3 & △ \\ 3 & 0 & 1 & 2 \\ 0 & 1 & 2 & 3 & 0 \end{matrix} ↦ \begin{matrix}2 \\ 3 \\ ♡ \\ ♡ & 2 \\ ♡ & ♡ & ♡ \\ ♡ & ♡ & ♡ & 2 \\ ♡ & ♡ & ♡ & ♡ & ♡ \end{matrix}

Recalll that in the finite symmetric group case, cosets representatives are diagrams contained in a rectangle; rectrices of a diagram D are the maximal rectangular partitions contained in it [12]. Describing Bruhat order on a finite symmetric group essentially reduces to decomposing partitions into maximal rectangles.

Lemma 2. Let D be the diagram of an n-core. Then D is the supremum (with respect to inclusion of diagrams) of its rectrices.

Proof. Since D is contained in the supremum of any family of diagrams such that each corner of D is contained into at least one of them, it is sufficient (and immediate) to check that each rectrix of D is contained entirely in D.

In order to determine the basis of 𝔖̃_{n}/𝔖_{n}, we need some more properties of staircases.

Lemma 3. Let D and F be diagrams of n-cores such that D is not a staircase and D is not included into F. Then there exists at least one staircase E in D such that E ⊄ F.

Proof. Take any corner ♣ of D which does not belong to F. Then any staircase with corner ♣ and included into D will do.

Lemma 4. Let E be (p, q)-staircase, having at least one internal corner ♣ (i.e. a corner which is not on the first column, nor on the bottom row). Let ▽, △ be the east and south neighbour boxes of ♣, and let E_{▽} be the (n − 1, 1)- staircase of corner ▽ and E_{△} be the (1, n − 1)-staircase of corner △. Let moreover F be the partition which is the supremum of E_{▽} and of E_{△} (it is an n-core).

Then E is minimum in the complementary of the interval [∅ ≤ F].

Proof. Suppose that an n-core E′ is strictly contained in E and not in F. Take a box of E′ which does not belong to F and a staircase E” contained in E′ of corner this box. Then E” is not included in F. Therefore it is sufficient to prove that each staircase E” strictly contained in E is also contained in F. If E” ⊂ E contains a box which is an internal corner of E, then this box is a corner of E” and E” = E. Therefore E” avoids all internal corners of E, in particular ♣. But is is clear that the part of E” which is right of ♣ is contained in E_{△}, and that the part which is left of ♣ is contained in E_{▽}. This implies that E” ⊆ F.

For example, take the (2, 2)-staircase ’^{o}^{o}^{o}^{o}^{o} o := [7, 5, 5, 3, 3, 1, 1], choosing the corner pointed by ♣, its diagonal being figured by ♠’s:

2 3_{0 1 2}_{1 2 3}_{2 3 0 1 2}_{3 0 1 2 3}_{0 1 2 3 0 1 2} ’ ooo oo o

’ ooo oo o
’^{o}^{o}^{o}^{o}^{o} o ▽ ♣
’^{o}^{o}^{o}^{o}^{o} o ♠ △
♠ ’^{o}^{o}^{o}^{o}^{o} o ’^{o}^{o}^{o}^{o}^{o} o ’^{o}^{o}^{o}^{o}^{o} o ’^{o}^{o}^{o}^{o}^{o} o
’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o
’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o

Then any 4-core strictly contained in ’^{o}^{o}^{o}^{o}^{o} o is also contained in the 4-core

F = [12, 9, 6, 3, 2, 1, 1, 1] = \begin{matrix}▽ \\ ▽ \\ ▽ \\ ▽ & ▽ \\ ▽ & ♠ & △ \\ ♠ & △ & △ & △ & △ & △ \\ △ & △ & △ & △ & △ & △ & △ & △ & △ \\ △ & △ & △ & △ & △ & △ & △ & △ & △ & △ & △ & △ \end{matrix}

We have left aside the cores having no internal corner, that is hookpartitions. A case-by-case analysis which offers no difficulty gives the following classification.

Lemma 5. Partitions

[1]; [2], … [n − 1]; [1^{2}], …, [1^{n−1}]; [n, 1], [2, 1^{n−1}]

belong to the basis, but not the other hooks with n+1 boxes: [3, 1^{n−2}], …, [n− 1, 1^{2}], though they are (p, q)-staircases.

For example, for n = 5, the basis contains the hooks [1]; [2], [3], [4]; [1^{2}], [1^{3}], [1^{4}]; [5, 1], [2, 1^{3}], but not [3, 1^{3}] nor [4, 1^{2}]. Indeed, [3, 1, 1, 1] is the supremum of [3] and [1, 1, 1, 1], and [4, 1, 1] is the supremum of [4] and [1, 1, 1].

In summary, one has the following characterization of the basis of 𝔖̃_{n}/𝔖_{n}.

Theorem 6. The basis of 𝔖̃_{n}/𝔖_{n} for the Bruhat order consists in all (p, q)- staircases, p + q = n, excepted the hooks [3 1^{n−2}], …, [n − 1, 1, 1].

We have now all the necessary tools to handle the affine symmetric group together with its Bruhat order. In particular, elements will be represented by the decomposition of their associated cores into maximal sub-staircases.

For example, the 5-core ’^{o}^{o}^{o}^{o}^{o} o = [6, 6, 5, 4, 3^{4}, 2^{4}, 1^{4}], corresponding to the group element [−15, 2, 4, 11, 13], with code [0, 3, 3, 7, 8] and length 21, is decomposed into the following three staircases

0 1 2 3 4 0 0 1 1 2 2 3 3 4 0 4 0 1 0 1 2 1 2 3 2 3 4 0 3 4 0 1 2 4 0 1 2 3 4 0 1 2 3 4 0 =  0 1 2 3 4 0 0 1 1 2 2 3 3 4 0 4 0 1 0 1 2 1 2 3 2 3 4 0 3 4 0 1 4 0 1 2 0 1 2 3 ∪ 0 1 2 1 2 3 2 3 4 3 4 0 1 2 4 0 1 2 3 0 1 2 3 4 ∪ 2 3 4 3 4 0 4 0 1 2 3 4 0 1 2 3 4 0

For a 5-core to be bigger than ’^{o}^{o}^{o}^{o}^{o} o with respect to the Bruhat order, it is necessary and sufficient to be bigger than each of the above three staircases.

As in the case of a finite symmetric group, one has to reduce the numbers of projections 𝔖̃_{n} ↦ 𝔖̃_{n}/𝔖_{n} or 𝔖̃_{n} ↦ 𝔖_{n}\𝔖̃_{n}/𝔖_{n} to get an efficient coding [12]. We shall not go into these technicalities here. Let us just mention that in the case of a finite symmetric group, we have used such a “decomposition”of a permutation into rectangular partitions to compute Kazhdan-Lusztig polynomials [10].

[figure: 123; 024; _{• • • • • •}; 015; ¯134; ¯116; _{••••••}; ¯235; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; ¯107; ¯226; ¯345; ¯208; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; ¯327; _{••••••}; ¯446; _{••••••}; ¯2¯19; ¯318; ¯437; • • • •; ¯556; ¯3¯1X; ¯419; ¯538; ¯657]

Cosets representatives for n=3

[figure: 000; 001; _{••••••}; 101; 020; 120; _{••••••}; 300; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; 022; 310; 004; 302; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; 014; _{••••••}; 050; _{••••••}; 033; 204; 051; • • • •; 600; 034; 250; 601; 007]

Codes

[figure: 0000; 10¯1¯1; _{••••••}; 01¯1¯1; 1¯10¯1; 0¯11¯1; _{••••••}; ¯110¯1; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; 2¯1¯1¯3; ¯101¯1; 11¯2¯3; ¯12¯1¯3; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; 20¯2¯4; _{••••••}; 1¯21¯3; _{••••••}; ¯1¯12¯3; 02¯2¯4; 2¯20¯4; • • • •; ¯211¯3; 3¯1¯2¯7; 0¯22¯4; ¯220¯4; 21¯3¯7]

Extended Weights

[figure: 0; 1; _{••••••}; 2; 11; 31; _{••••••}; 211; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; 42; 311; 2211; 531; \begin{matrix}• \\ • \\ • \\ • \end{matrix}; 4211; _{••••••}; 32211; _{••••••}; 642; 5311; 42211; • • • •; 332211; 7531; 64211; 532211; 4332211]

3-Cores

References

1. A. Björner, F. Brenti, Affine permutations of type A, Electronic J. Comb. 3# R18 (1996).

2. N. Bourbaki, Groupes et Algèbres de Lie, Fasc 34, Hermann, Paris (1968).

3. V.V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group, Invent. Math. 39 (1977) 187-198.

4. C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. Math. 35 (1934) 396-443.

5. H. Eriksson, Computational and combinatorial aspects of Coxeter groups, thesis, KTH, Stockholm (1994).

6. O. Foda, B. Leclerc, M. Okado, J-Y Thibon, T. Welsh, Branching functions of A_{n−1}^{(1)} and Jantzen-Seitz problem for Ariki-Koike algebras, Adv. in Maths 141 (1999) 322-365.

7. James, A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Mathematics, Addisson-Wesley, Reading MA, (1991).

8. M. Geck, S. Kim, Bases for the Bruhat-Chevalley order on all finite Coxeter groups, J. of Algebra 197 (1997) 278–310.

9. A. Kerber, Algebraic Combinatorics via finite group actions, Wissenschaftsverlag, Mannheim (1991).

10. A. Lascoux, , Ordonner le groupe symétrique: pourquoi utiliser l’algèbre de Iwahori-Hecke ?, Congrès International Berlin 1998, Documenta Mathematica, extra volume ICM 1998, III (1998) 355–364.

11. A. Lascoux, B. Leclerc et J.Y. Thibon, Crystal graphs and q-analogues of weight multiplicities for root systems of type A_{n}, Letters in Math. Physics, 35 (1995) 359–374.

12. A. Lascoux, M.P. Schützenberger, Treillis et bases des groupes de Coxeter, Electronic J. of Comb. 3 # R27 (1996).

13. K.C. Misra, T. Miwa, Crystal base of the basic representation of U_{q}(ŝl_{n}), Commun. Math. Phys., 134, 1990, p.79-88.

14. Jian-Yi Shi, The Kazhdan-Lusztig cells in certain affine Weyl Groups, Springer L.N. 1179 (1986).

15. S. Veigneau, ACE, an algebraic environment for the computer algebra

system MAPLE, http://phalanstere.univ-mlv.fr/∼ace (1998).