A Unified Construction of Coxeter Group Representations (II)

Ron M. Adin^{∗}^{§}  Francesco Brenti^{†}^{§}  Yuval Roichman^{‡}^{§}

November 30, 2005

Abstract

A unified axiomatic approach to the representation theory of Coxeter groups and their Hecke algebras was presented in [1]. Combinatorial aspects of this construction are studied in this paper. In particular, the symmetric group case is investigated in detail. The resulting representations are completely classified and include the irreducible ones.

1 Introduction

1.1 Outline

A unified axiomatic approach to the representation theory of Coxeter groups and their Hecke algebras was presented in [1]. This was carried out by a natural assumption on the representation matrices and avoiding a priori use of external concepts (such as Young tableaux).

Let (W, S) be a Coxeter system, and let K be a subset of W. Let 𝔽 be a suitable field of characteristic zero (e.g., the field ℂ(q) in the case of

∗Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900,

Israel. Email: radin@math.biu.ac.il

†Dipartimento di Matematica, Universitá di Roma “Tor Vergata”, Via della Ricerca Scientifica, 00133 Roma, Italy. Email: brenti@mat.uniroma2.it

‡Department of Mathematics and Statistics, Bar-Ilan University, Ramat-Gan 52900,

Israel. Email: yuvalr@math.biu.ac.il

§Research of all authors was supported in part by the Israel Science Foundation, founded by the Israel Academy of Sciences and Humanities; by EC’s IHRP Programme, within the Research Training Network “Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272; and by internal research grants from Bar-Ilan University.

the Iwahori-Hecke algebra), and let ρ be a representation of (the Iwahori-Hecke algebra of) W on the vector space V_{K} := span_{𝔽}{C_{w} | w ∈ K}, with basis vectors indexed by elements of K. We want to study the sets K and representations ρ which satisfy the following axiom:

(A) For any generator s ∈ S and any element w ∈ K there exist scalars a_{s}(w), b_{s}(w) ∈ 𝔽 such that

ρ_{s}(C_{w}) = a_{s}(w)C_{w} + b_{s}(w)C_{ws}.

If w ∈ K but ws ∉ K we assume b_{s}(w) = 0.

A pair (ρ, K) satisfying Axiom (A) is called an abstract Young (AY) pair; ρ is an AY representation, and K is an AY cell. If K ≠ ∅ and has no proper subset ∅ ⊂ K′ ⊂ K such that V_{K′} is ρ-invariant, then (ρ, K) is called a minimal AY pair. (This is much weaker than assuming ρ to be irreducible.)

Combinatorial aspects of this construction are studied in this paper. In particular, the symmetric group case is investigated in detail. The resulting representations are completely classified and include the irreducible ones.

In [1] it was shown that an AY representation of a simply laced Coxeter group is determined by a linear functional in the root space. In this paper it is shown that, furthermore, the values of the linear functional on the “boundary” of the AY cell determine the representation (see Theorem 4.7 below).

In Section 5 this result is used to characterize AY cells in the symmetric group. This characterization is then applied to show that every irreducible representation of S_{n} may be realized as a minimal abstract Young representation (see Theorem 5.11 below). AY representations of Weyl groups of type B are not determined by a linear functional. However, it is shown that a similar result holds for these group (Theorem 6.5 below).

Finally, we characterize the elements in π ∈ S_{n}, for which the interval [e, π] form a minimal AY cell, which carries an irreducible representation (see Theorem 7.9 below).

1.2 Main Results

In Section 4 it is shown that the action of the group W on the boundary of a cell determines the representation up to isomorphism.

Theorem 1.1 (see Theorem 4.7) Let (ρ, K) be a minimal AY pair for a simply laced Coxeter group W, where K is finite. Then the behavior of ρ at the boundary of K (i.e., the values a_{s}(w) for w ∈ K, s ∈ S, ws ∉ K) determines ρ up to isomorphism.

The proof combines continuity arguments with the reduction of AY representations to distinguished linear functionals, carried out in [1] (see Theorems 3.7 and 3.8 below).

AY cells in the symmetric group are characterized in Section 5.

Theorem 1.2 (see Theorem 5.9) Let K ⊆ S_{n} and let σ ∈ K. Then K is a minimal AY cell if and only if there exists a standard Young tableau Q of size n such that

σ^{−1}K = {π ∈ S_{n}| Q^{π} is standard},

where Q^{π} is the tableau obtained from Q by replacing each entry i by π(i).

The proof applies Theorem 1.1 together with Theorems 3.7 and 3.8 below. Theorem 1.2 is then used to prove the following.

Theorem 1.3 (see Corollary 5.12) The complete list of minimal AY representations of the symmetric group S_{n} is given (up to isomorphism) by the skew Specht modules S^{λ/μ}, where λ/μ is of order n and μ possibly empty.

In particular, every irreducible representation of the symmetric group S_{n} may be realized as a minimal abstract Young representation.

Combining this theorem with the combinatorial induction rule for minimal AY representations (Theorem 3.9 below) we prove

Theorem 1.4 (see Theorem 6.5) Every irreducible representation of the classical Weyl group B_{n} may be realized as a minimal abstract Young representation.

Definition 1.5 An element w ∈ W is a top element if the interval [e, w] is a minimal AY cell and any minimal AY representation on the interval [e, w] is irreducible.

The top elements of the symmetric group S_{n} are characterized in Section 7.

Theorem 1.6 (see Theorem 7.9) A permutation π ∈ S_{n} is a top element if and only if π is the column word of a row standard Young tableau (see Definition 7.7 below).

Note: Having the first version of the paper completed, we were told that equivalent results to Theorems 1.1 and 1.3, with entirely different proofs, appear in [14, 19].

2 Preliminaries

A Coxeter system is a pair (W, S) consisting of a group W and a set S of generators for W, subject only to relations of the form

(st)^{m(s,t)} = 1,

where m(s, s) = 1 and m(s, t) = m(t, s) ≥ 2 for s ≠ t in S. In case no relation occurs for a pair (s, t), we make the convention that m(s, t) = ∞. W is called a Coxeter group. If m(s, t) ≤ 3 for all s ≠ t then (W, S) is called simply laced. Throughout this paper we assume that the set S of generators is finite; the group W itself may be infinite.

Let (W, S) be a Coxeter system, and let X = X(W, S) be the corresponding Cayley graph (with generators acting on the right): its vertices are the elements of W, and x, y ∈ W are connected by an edge if and only if x^{−1}y ∈ S. X is a connected undirected graph. A subset K ⊆ W is called convex if, for any x, y ∈ K, all the geodesics (paths of shortest length) connecting x to y in X have all their vertices in K.

Let P be a poset, and let X be its undirected Hasse diagram. Thus X is an undirected graph which has P as a vertex set, with an edge {x, y} whenever x either covers or is covered by y. A subset K of P is called convex if, for any x, y ∈ K, all geodesics (shortest paths) connecting x to y in X have all their vertices in K.

Let P be a Coxeter group W with the right weak Bruhat order, namely the transitive closure of the relation

w < ws ⟺ w ∈ W, s ∈ S and ℓ(w) < ℓ(ws).

Clearly, K ⊆ W is convex in the right Cayley graph X(W, S) if and only if it is convex in the right weak Bruhat poset P.

Let T be the set of all reflections in W, and let A ⊆ T be any subset. The (left) A-descent set of an element w ∈ W is defined by

Des_{A}(w) := {t ∈ A | ℓ(tw) < ℓ(w)}.

For D ⊆ A ⊆ T, the corresponding generalized descent class is

W_{A}^{D} := {w ∈ W | Des_{A}(w) = D}.

These sets were studied by Tits [25, Ch. 2] and Björner-Wachs [4, 5]. Our notation follows [4].

The following theorem is a consequence of [25, Theorem 2.19 ]. See [4, Theorem 5.3] and [5, Proposition 6.2].

Theorem 2.1 (Tits) A subset K of W is convex under right weak Bruhat order if and only if K = W_{A}^{D} for suitable subsets D ⊆ A ⊆ T.

Definition 2.2 Let A ⊆ T. Define a symmetric relation ↔_{A} on W by

w ↔_{A} ws ⟺ wsw^{−1} ∉ A,

and let ∼_{A} be the transitive closure of ↔_{A}. The A-cell K_{A}(w) of an element w ∈ W is the equivalence class of w under ∼_{A}.

In geometric terms, these equivalence classes are the connected components of the Cayley graph X(W, S) after deleting all the edges {w, ws} with wsw^{−1} ∈ A.

Theorem 2.3 [1, Theorem 4.10] Let u, v ∈ W. Then

u ∼_{A} v ⟺ Des_{A}(u) = Des_{A}(v).

Let V be the root space of a Coxeter system (W, S). Thus V is a vector space over ℝ with a basis {α_{s} | s ∈ S} indexed by the group generators. A symmetric bilinear form B is defined on V by

B(α_{s}, α_{t}) := − cos \frac{π}{m(s, t)} (∀s, t ∈ S)

(interpreted to be −1 in case m(s, t) = ∞). For each generator s ∈ S define a linear map σ_{s} : V → V by

σ_{s}(v) := v − 2B(v, α_{s})α_{s} (∀v ∈ V).

This yields a faithful B-preserving action σ of W on V (see, e.g., [10]), and defines the corresponding root system

Φ := {σ_{w}(α_{s}) | w ∈ W, s ∈ S} ⊆ V.

Let T be the set of all conjugates of generators; its elements are called reflections of W, and elements of S are called simple reflections. There is a bijection between reflections in T and positive roots in Φ, given by t = wsw^{−1} ⟷ α_{t} = σ_{w}(α_{s}) (provided that ℓ(w) < ℓ(ws)).

Throughout the paper ⟨ , ⟩ is an arbitrary positive definite bilinear form on V.

Let λ be a partition of n, and let ρ^{λ} be the corresponding irreducible representation of S_{n} (on the Specht module S^{λ}). Let {v_{Q} | Q standard Young tableau of shape λ} be the basis of S^{λ} obtained from the basis of polytabloids by the Gram-Schmidt process (see [11, §25]). Let Q be a standard Young tableau. If k ∈ {1, …, n} is in box (i, j) of Q then the content of k in Q is

c(k) := j − i.

The kth hook-distance is defined as

h(k) := c(k + 1) − c(k) (1 ≤ k ≤ n − 1).

Finally, let Q^{s_{i}} be the tableau obtained from Q by interchanging i and i+1.

Theorem 2.4 (Classical Young Orthogonal Form) [11, §25.4] In the above notations,

ρ^{λ}(s_{i})(v_{Q}) = \frac{1}{h(i)} v_{Q} + \sqrt{1 − \frac{1}{h(i)^{2}}} v_{Q^{s_{i}}} .

This setting is generalized naturally to skew shapes λ/μ. Standard Young tableaux of shape λ/μ, hook distances on these tableaux and skew Specht modules S^{λ/μ} are defined analogously. In particular,

Theorem 2.5 (Classical Young Orthogonal Form for Skew Specht Modules) Let {v_{Q} | Q standard Young tableau of shape λ/μ} be the basis of the skew Specht module S^{λ/μ} obtained by the Gram-Schmidt process from the polytabloid basis. Then

ρ^{λ/μ}(s_{i})(v_{Q}) = \frac{1}{h(i)} v_{Q} + \sqrt{1 − \frac{1}{h(i)^{2}}} v_{Q^{s_{i}}} .  (1)

Proof. (Due to J. Stembridge [24]; see also [9].) Matrices determined by (1) must satisfy the Coxeter relations of S_{n}, because the same is true when the skew tableaux are completed to full tableaux of non-skew shape. Therefore they define a representation of S_{n}, which we denote Y^{λ/μ}. Upon restricting the action of S_{n} to S_{k} × S_{n−k} (where n = |λ|, k = |μ|), Y^{λ} decomposes into the direct sum ⨁_{{μ⊆λ | |μ|=k}} Y^{μ} ⊗ Y^{λ/μ}. On the other hand, Specht modules have exactly the same decomposition. This follows, for example, from the corresponding identity on Schur functions [23, (7.66)] (using the inverse Frobenius image). Since Y^{λ} ≅ S^{λ}, Y^{λ/μ} must be isomorphic to S^{λ/μ}. □

The classical Weyl group of type B, B_{n}, is a Coxeter system with S = {s_{i}| 0 ≤ i < n}, m(0, 1) = 4, m(i, i + 1) = 3 for 1 ≤ i < n and m(i, j) = 2 otherwise. The irreducible representations of B_{n} are indexed by pairs of partitions (λ, μ), where λ is a partition of some 0 ≤ k ≤ n and μ is a partition of n − k. A basis of an irreducible representation of shape (λ, μ) may be indexed by all pairs (P, Q) of standard Young tableaux of shapes λ and μ, where P is a tableau on a subset of k letters from {1, …, n} and Q is a tableau on the complementary subset of letters. There exist a basis, such that the following Young form holds (see, e.g, [17]).

Theorem 2.6 (Classical Young Orthogonal Form for B_{n}) Denote the above basis elements by v_{(P,Q)}. Then for 1 ≤ i < n − 1,

ρ^{λ,μ}(s_{i})v_{(P,Q)} = \{ \begin{matrix}\frac{1}{h(i)} v_{(P,Q)} + \sqrt{1 − \frac{1}{h(i)^{2}}} v_{(P,Q)}^{s_{i}} , & if i,i+1 are in same tableaux; \\ v_{(P,Q)}^{s_{i}} & i,i+1 are in different tableaux, \end{matrix}

where (P, Q)^{s_{i}} is the pair of be the tableaux obtained from (P, Q) by interchanging i and i + 1, and

ρ^{λ,μ}(s_{0})v_{(P,Q)} = \{ \begin{matrix}v_{(P,Q)}, & if 1 ∈ P; \\ −v_{(P,Q)}, & if 1 ∈ Q. \end{matrix}

3 Abstract Young Cells and Representations

This section surveys the results from [1], which will be used in this paper. Recall the definition of AY cells and representations from the introduction.

Observation 3.1 [1, Observation 3.3] Every nonempty AY cell is a left translate of an AY cell containing the identity element of W.

Proposition 3.2 [1, Corollary 4.4] Every minimal AY cell is convex (in the right Cayley graph X(W, S) or, equivalently, under right weak Bruhat order). In particular, b_{s}(w) ≠ 0 whenever s ∈ S and w, ws ∈ K.

Important examples of AY cells are (standard) descent classes.

Surprisingly, Axiom (A) leads to very concrete matrices, whose entries are essentially inverse linear.

In [1] it is shown that, under mild conditions, Axiom (A) is equivalent to the following more specific version. Here T is the set of all reflections in W.

(B) For any reflection t ∈ T there exist scalars ȧ_{t}, ḃ_{t}, ä_{t}, b̈_{t} ∈ 𝔽 such that, for all s ∈ S and w ∈ K:

ρ_{s}(C_{w}) = \{ \begin{matrix}ȧ_{wsw^{−1}}C_{w} + ḃ_{wsw^{−1}}C_{ws}, & if ℓ(w) < ℓ(ws); \\ ä_{wsw^{−1}}C_{w} + b̈_{wsw^{−1}}C_{ws}, & if ℓ(w) > ℓ(ws). \end{matrix}

If w ∈ K and ws ∉ K we assume that ḃ_{wsw^{−1}} = 0 (if ℓ(w) < ℓ(ws)) or

b̈_{wsw^{−1}} = 0 (if ℓ(w) > ℓ(ws)).

Theorem 3.3 [1, Theorem 5.2] Let (ρ, K) be a minimal AY pair for the Iwahori-Hecke algebra of (W, S). If a_{s}(w) = a_{s′}(w′) ⟹ b_{s}(w) = b_{s′}(w′) (∀s, s′ ∈ S, w, w′ ∈ K), then ρ satisfies Axiom (B).

Theorem 3.4 [1, Theorem 11.1] The coefficients ȧ_{t} determine all the character values.

The assumption regarding the coefficients b_{s}(w) in Theorem 3.3 is merely a normalization condition. Theorem 3.3 shows that the coefficients a_{s}(w) and b_{s}(w) in Axiom (A) depend only on the reflection wsw^{−1} ∈ T and on the relation between w and ws in right weak Bruhat order. It turns out that for simply laced Coxeter groups the coefficients ȧ_{t} are given by a linear functional.

Definition 3.5 For a convex subset K ⊆ W define:

T_{K} := {wsw^{−1} | s ∈ S, w ∈ K, ws ∈ K},
T_{∂K} := {wsw^{−1} | s ∈ S, w ∈ K, ws ∉ K}.

Definition 3.6 (K-genericity) Let K be a convex subset of W containing the identity element. A vector f in the root space V is K-generic if:

(i) For all t ∈ T_{K},

⟨f, α_{t}⟩ ∉ {0, 1, −1}.

(ii) For all t ∈ T_{∂K},

⟨f, α_{t}⟩ ∈ {1, −1}.

(iii) If w ∈ K, s, t ∈ S, m(s, t) = 3 and ws, wt ∉ K then

⟨f, α_{wsw^{−1}}⟩ = ⟨f, α_{wtw^{−1}}⟩ (= ±1).

By Observation 3.1, we may assume that id ∈ K.

Theorem 3.7 [1, Theorem 7.4] Let (W, S) be an irreducible simply laced Coxeter system, and let K be a convex subset of W containing the identity element. Let ⟨ , ⟩ be an arbitrary positive definite bilinear form on the root space V. If f ∈ V is K-generic then

ȧ_{t} := \frac{1}{⟨f, α_{t}⟩} (∀t ∈ T_{K} ∪ T_{∂K}),

together with ä_{t}, ḃ_{t} and b̈_{t} satisfying

ȧ_{t} + ä_{t} = 1
ḃ_{t} · b̈_{t} = (1 − ȧ_{t})(1 − ä_{t})

define a representation ρ such that (ρ, K) is a minimal AY pair satisfying Axiom (B).

Various normalizations for ḃ_{t} and b̈_{t} are possible: symmetric (b̈_{t} = ḃ_{t}), seminormal (b̈_{t} = 1), row stochastic (ȧ_{t}+ḃ_{t} = ä_{t}+b̈_{t} = 1), etc. [1, Subsection 5.2]. By Theorem 3.4, all these normalizations give isomorphic representations.

Replacing ⟨f, α_{t}⟩ by its q-analogue [⟨f, α_{t}⟩]_{q} gives representations of the Iwahori-Hecke algebra H_{q}(W) [1, Theorem 8.4].

The following theorem is complementary.

Theorem 3.8 [1, Theorem 7.5] Let (W, S) be an irreducible simply laced Coxeter system and let K be a subset of W containing the identity element. If (ρ, K) is a minimal AY pair satisfying Axiom (B) and ȧ_{t} ≠ 0 (∀t ∈ T_{K}) then there exists a K-generic f ∈ V such that

ȧ_{t} = \frac{1}{⟨f, α_{t}⟩} (∀ t ∈ T_{K} ∪ T_{∂K}).

The following combinatorial rule for induction of AY representations is analogous to the one for Kazhdan-Lusztig representations, proved by Barbasch and Vogan for Weyl groups [3, Prop. 3.15] and by Geck for Coxeter groups [8]. For other closely related results see [22, 7, 20].

Theorem 3.9 [1, Theorem 9.3] Let (W, S) be a finite Coxeter system, P = ⟨J⟩ (J ⊆ S) a parabolic subgroup, and W^{J} the set of all representatives of minimal length of the right cosets of P in W. Let (ψ, D) be a minimal AY pair for P. Then

1. DW^{J} is a minimal AY cell for W.

2. The induced representation ψ ↑_{P}^{W} is isomorphic to an AY representation on V_{DW^{J}}.

Remark 3.10 By [1, Lemma 9.7], for every s ∈ S and r ∈ W^{J} either rs ∈ W^{J}, or rs ∉ W^{J} and rs = pr, where p ∈ J. Then, by the proof of Theorem [1, Theorem 9.3], the representation matrix of the generators in the resulting induced representation is given by

ρ_{s}(C_{mr}) = \{ \begin{matrix}C_{mrs}, & if rs ∈ W^{J}; \\ a_{p}(m)C_{mr} + b_{p}(m)C_{mrs}, & otherwise, \end{matrix}

where the coefficients a_{p} and b_{p} are given by the AY representation ψ; namely, ψ_{p}(C_{m}) = a_{p}(m)C_{m} + b_{p}(m)C_{mp}.

4 Boundary Conditions

In this section it is shown that the action of the group W on the boundary of a minimal AY cell determines the representation up to isomorphism.

Definition 4.1 Let w ∈ W, and let f be an arbitrary vector in the root space V of W.

(1) Define

K_{w}^{f} := K_{A_{f}} (w),

where the notation K_{A}(w) is as in Definition 2.2 and

A_{f} := {t ∈ T | ⟨f, α_{t}⟩ ∈ {1, −1}}.

(2) If f is K_{w}^{f}-generic (as in Definition 3.6) then the corresponding AY representation of W (as in Theorem 3.7), with the symmetric normalization b̈_{t} = ḃ_{t} (∀t ∈ T_{K_{w}^{f}}), will be denoted ρ_{w}^{f} (or just ρ^{f} in case there is no ambiguity).

Remark 4.2 By Theorem 3.4, the representation ρ_{w}^{f} is independent of the normalization (up to isomorphism).

Definition 4.3 Let W be a Coxeter group, and let V be its root space. A basic (affine) hyperplane in V has the form

H_{t,ε} := {f ∈ V | ⟨f, α_{t}⟩ = ε},

for some t ∈ T and ε ∈ {1, −1}.

A basic (proper) flat in V is an intersection (other than ∅ or V) of basic hyperplanes.

For a basic flat L, let

A = A_{L} := { t ∈ T | L ⊆ H_{t,ε} for some ε ∈ {1, −1} }.

Then {W_{A}^{D} | D ⊆ A} (see Section 2 for the definition of W_{A}^{D}) is a partition of W into convex subsets, called the L-partition of W.

Note that, for the two “improper” flats:

L = ∅ ⟹ A_{L} = T
L = V ⟹ A_{L} = ∅

Theorem 4.4 Let W be a simply laced Coxeter group. Let L be a basic flat in V, and fix a nonempty finite convex set K in the L-partition of W. Then, for any two elements v, v′ ∈ K and any two K-generic vectors f, f′ ∈ L, K_{v}^{f} = K_{v′}^{f′} = K and the representations ρ_{v}^{f} and ρ_{v′}^{f′} are isomorphic.

Proof. First of all,

f ∈ L ⟺ ⟨f, α_{t}⟩ = ±1 (∀t ∈ A_{L}) ⟺ A_{L} ⊆ A_{f}

and therefore, for any K in the L-partition of W and any v ∈ K,

K_{v}^{f} ⊆ K.

If f is also K-generic then ⟨f, α_{t}⟩ ≠ ±1 for all t ∈ T_{K}, so that K_{v}^{f} = K.

Now choose f_{0} ∈ L, and let {f_{1}, …, f_{k}} be a basis for the linear subspace L − f_{0} of V. Each f ∈ L has a unique expression as

f = f_{0} + r_{1}f_{1} + … + r_{k}f_{k},

where r_{1}, …, r_{k} ∈ ℝ. For any t ∈ T_{K} ∪ T_{∂K}, ⟨f, α_{t}⟩ is a linear combination of 1, r_{1}, …, r_{k}, and is nonzero if f is K-generic. Thus, for any v ∈ K and K-generic f ∈ L, each entry of the matrix ρ_{v}^{f}(s) (∀s ∈ S) is a rational function of r_{1}, …, r_{k}; and the same therefore holds for each entry of ρ_{v}^{f}(w) (∀w ∈ W) and for the character values Tr(ρ_{v}^{f}(w)). Note that these rational functions (unlike the actual values of r_{1}, …, r_{k}) do not depend on the choice of v and f, even though the set L^{gen} of all K-generic f ∈ L may be disconnected (see example below). By discreteness of the character values and continuity of the rational function, each character value is constant in each connected component of L^{gen}, and at the same time represented by one rational function throughout L^{gen}. It is therefore the same constant for all f ∈ L^{gen} (and v ∈ K), as claimed. □

Example 4.5 Take W = S_{3} = ⟨s_{1}, s_{2}⟩ (type A_{2}) and the basic flat L = {f ∈ V | ⟨f, α_{s_{1}s_{2}s_{1}}⟩ = −1}. Then A = {s_{1}s_{2}s_{1}}, and we may choose K = {id, s_{1}, s_{2}}. In that case, T_{K} = {s_{1}, s_{2}} and T_{∂K} = {s_{1}s_{2}s_{1}} = A. L is an affine line in V ≅ ℝ^{2}, and the K-generic points in L form five disjoint open intervals (three of them bounded). For any K-generic vector f ∈ L and any v ∈ K, ρ_{v}^{f} is the 3-dimensional representation isomorphic to the direct sum of the sign representation and the unique irreducible 2dimensional representation of S_{3}.

An important special case is L = V (K = W).

Theorem 4.6 Let W be a finite simply laced Coxeter group, and let f ∈ V be W -generic (i.e., ⟨f, α_{t}⟩ ∉ {0, 1, −1}, ∀t ∈ T). Then, for any v ∈ W, the representation ρ_{v}^{f} on V_{W} is isomorphic to the regular representation of W.

Proof. Fix v ∈ W (and ignore it in the notation). For all but finitely many values of μ ∈ ℝ, the vector μf ∈ V is also W -generic. The representations ρ^{μf} and ρ^{f} are equivalent, by Theorem 4.4. On the other hand, if |μ| → ∞ then

a_{s}^{(μf)}(w) = \frac{±1}{⟨μf, α_{wsw^{−1}}⟩} → 0 (∀s ∈ S, w ∈ W))

and consequently b_{s}^{(μf)}(w) → 1. The representation matrices of ρ^{(μf)}(s) (∀s ∈ S), and thus also those of ρ^{(μf)}(w) (∀w ∈ W), tend to those of the regular representation. The character of ρ^{f} is thus the character of the regular representation. □

Theorem 4.4 may be reformulated as follows.

Theorem 4.7 Let (ρ, K) be a minimal AY pair for a simply laced Coxeter group W, where K is finite. Then the behavior of ρ at the boundary of K (i.e., the values a_{s}(w) for w ∈ K, s ∈ S, ws ∉ K) determines ρ up to isomorphism.

5 Minimal Cells for S_{n}

In this section we assume that q = 1, and show that integer-valued K-generic vectors for W = S_{n} lead to standard Young tableaux (of skew shape). The analysis for general q is similar. Theorem 4.4 is then applied to give a complete characterization of minimal AY cells of S_{n}. Finally, it is shown that all irreducible representations of S_{n} are minimal AY.

5.1 Identity Cells and Tableaux

In this subsection we study minimal AY cells K ∈ S_{n}. By Observation 3.1, every minimal AY cell is a translate of a minimal AY cell containing the identity; thus we may assume that id ∈ K.

For a vector v = (v_{1}, …, v_{n}) ∈ ℝ^{n} denote

Δ v := (v_{2} − v_{1}, …, v_{n} − v_{n−1}) ∈ ℝ^{n−1}.

For a (skew) standard Young tableau T denote c(k) := j − i, where k is the entry in row i and column j of T. Call cont(T) := (c(1), …, c(n)) the content vector of T, and call Δ cont(T) the derived content vector of T.

Note that for W = S_{n} we may identify the root space

V ≅ {(v_{1}, …, v_{n}) ∈ ℝ^{n} | v_{1} + … + v_{n} = 0}.

The positive root α_{ij} ∈ V corresponding to the transposition (i, j) ∈ S_{n} may be identified with the vector ε_{i} − ε_{j} (1 ≤ i < j ≤ n), where {ε_{1}, …, ε_{n}} is the standard basis of ℝ^{n}. The coordinates of a vector f ∈ V will always be taken with respect to the ordered basis (ε_{1} − ε_{2}, …, ε_{n−1} − ε_{n})

Recall the notations K_{w}^{f} and ρ_{w}^{f} from Definition 4.1.

Theorem 5.1 Let f ∈ V have integer coordinates. Then: (ρ_{id}^{f}, K_{id}^{f}) is a minimal AY pair for W = S_{n} if and only if there exists a standard skew Young tableau T of size n such that

Δ f = Δ cont(T).

The proof of Theorem 5.1 relies on the following lemmas.

Lemma 5.2 Let f ∈ V have integer coordinates and assume that f is K_{id}^{f}- generic. If i < j and ⟨f, α_{ij}⟩ ∈ {0, 1, −1} then w^{−1}(i) < w^{−1}(j) for all w ∈ K_{id}^{f}.

Proof. The claim clearly holds for w = id. It thus suffices to show that if w, ws ∈ K_{id}^{f} (s ∈ S) then w^{−1}(j) − w^{−1}(i) and (ws)^{−1}(j) − (ws)^{−1}(i) have the same sign.

Since s is an adjacent transposition, say s = (t, t + 1) (1 ≤ t ≤ n − 1), the two signs differ if and only if {w^{−1}(i), w^{−1}(j)} = {t, t + 1}. This implies that (i, j) = wsw^{−1} ∈ T_{K_{id}^{f}}. Thus ⟨f, α_{ij}⟩ ∉ {0, 1, −1}, by K_{id}^{f}-genericity of f. This contradicts the assumption. □

Lemma 5.3 Let f ∈ V be an arbitrary vector. Then f is K_{id}^{f}-generic if and only if, for all 1 ≤ i < j ≤ n:

⟨f, α_{ij}⟩ = 0 ⟹ ∃ r_{1}, r_{2} ∈ [i + 1, j − 1] s.t. ⟨f, α_{ir_{1}}⟩ = −⟨f, α_{ir_{2}}⟩ = 1. (2)

Proof. Let K := K_{id}^{f}. A - (necessity). Note that, since f is K-generic,

⟨f, α_{ij}⟩ = 0 ⟹ (i, j) ∉ T_{K} ∪ T_{∂K}.  (3)

Consider the set

Z := {(i, j) | 1 ≤ i < j ≤ n, ⟨f, α_{ij}⟩ = 0}.

We shall prove that

(i, j) ∈ Z ⟹ ∃ r_{1}, r_{2} ∈ [i + 1, j − 1] such that ⟨f, α_{ir_{1}}⟩ = ⟨f, α_{r_{2}j}⟩ = 1.

The proof will proceed by induction on j − i, the height of the root α_{ij}.

Assume first that j − i = 1. Then (i, j) = (i, i + 1) ∈ S. Since id ∈ K, S ⊆ T_{K} ∪ T_{∂K}. This contradicts (3) above.

For the induction step, assume that (i, j) ∈ Z with j − i > 1 and that the claim is true for all reflections in Z with smaller heights. Choose w ∈ K such that d_{w} := |w^{−1}(j) − w^{−1}(i)| is minimal. Note that, by Lemma 5.2, actually d_{w} = w^{−1}(j) − w^{−1}(i) > 0.

If d_{w} = 1 then there exists 1 ≤ t ≤ n−1 such that w(t) = i and w(t+1) = j, so that (i, j) = w(t, t + 1)w^{−1} ∈ T_{K} ∪ T_{∂K}, which is a contradiction to(3).

Thus d_{w} ≥ 2.

Define 1 ≤ r_{1}, r_{2} ≤ n by w^{−1}(r_{1}) = w^{−1}(i)+1 and w^{−1}(r_{2}) = w^{−1}(j)−1. By minimality of d_{w}, ⟨f, α_{ir_{1}}⟩ = ±1 and ⟨f, α_{r_{2}j}⟩ = ±1. Since ⟨f, α_{ij}⟩ = 0, we have ⟨f, α_{ir_{2}}⟩ = −⟨f, α_{r_{2}j}⟩ = ±1 and ⟨f, α_{r_{1}j}⟩ = −⟨f, α_{ir_{1}}⟩ = ±1. By Lemma 5.2, w^{−1}(i) < w^{−1}(r_{1}) < w^{−1}(j) implies i < r_{1} < j and similarly for r_{2}.

If ⟨f, α_{ir_{1}}⟩ = ⟨f, α_{r_{2}j}⟩ = 1 or ⟨f, α_{ir_{1}}⟩ = ⟨f, α_{r_{2}j}⟩ = −1 we are done. We can thus assume, with no loss of generality, that ⟨f, α_{ir_{1}}⟩ = −⟨f, α_{r_{2}j}⟩ = 1 and r_{1} ≤ r_{2}.

If r_{1} = r_{2} then w^{−1}(j) − w^{−1}(i) = 2. Denote t := w^{−1}(i). Then ⟨f, α_{w(t,t+1)w^{−1}}⟩ = ⟨f, α_{ir_{1}}⟩ = 1 and ⟨f, α_{w(t+1,t+2)w^{−1}}⟩ = ⟨f, α_{r_{1}j}⟩ = −1. This contradicts condition (iii) of K-genericity (Definition 3.6). Therefore r_{1} < r_{2}. Thus

⟨f, α_{r_{1}r_{2}}⟩ = ⟨f, α_{ij}⟩ − ⟨f, α_{ir_{1}}⟩ − ⟨f, α_{r_{2}j}⟩ = 0.

Since r_{2} − r_{1} < j − i, by the induction hypothesis there exists r_{1} < r_{3} < r_{2} such that ⟨f, α_{r_{1}r_{3}}⟩ = −1. Thus ⟨f, α_{ir_{3}}⟩ = 0 (and ⟨f, α_{r_{3}j}⟩ = 0). Again, by the induction hypothesis, there exist i < r_{4}, r_{5} < r_{3} such that ⟨f, α_{ir_{4}}⟩ = ⟨f, α_{r_{5}r_{3}}⟩ = 1. Noting that ⟨f, α_{r_{5}r_{3}}⟩ = ⟨f, α_{r_{5}j}⟩ completes the proof that condition (2) is necessary.

B - (sufficiency).

Assume now that f ∈ V satisfies condition (2). Condition (ii) of Definition 3.6 holds by the definition of K_{id}^{f}. Assume that ⟨f, α_{ij}⟩ = 0. By condition (2) and Lemma 5.2, there exist i < r_{1} < r_{2} < j such that w^{−1}(i) < w^{−1}(r_{1}) < w^{−1}(r_{2}) < w^{−1}(j) for all w ∈ K. Thus w^{−1}(j) − w^{−1}(i) > 2, and this implies conditions (i) and (iii) of K-genericity as follows :

For condition (i), if w, ws ∈ K, s = (t, t + 1) ∈ S and ⟨f, α_{wsw^{−1}}⟩ = 0 then, denoting i := w(t), j := w(t + 1) we get i < j and ⟨f, α_{ij}⟩ = 0, so that w^{−1}(j) − w^{−1}(i) = 1 contradicting our conclusion above.

For condition (iii), if w ∈ K, ws, wt ∉ K, s = (k, k + 1) and t = (k + 1, k + 2) then denote i := w(k), r := w(k + 1), j := w(k + 2). Then i < r < j and ⟨f, α_{wsw^{−1}}⟩ = ±1, ⟨f, α_{wtw^{−1}}⟩ = ±1. If ⟨f, α_{wsw^{−1}}⟩ ≠ ⟨f, α_{wtw^{−1}}⟩ then ⟨f, α_{wsw^{−1}}⟩ + ⟨f, α_{wtw^{−1}}⟩ = 0, that is ⟨f, α_{ir}⟩ + ⟨f, α_{rj}⟩ = 0 or equivalently ⟨f, α_{ij}⟩ = 0, and again w^{−1}(j) − w^{−1}(i) > 2 by our conclusion above. □

Lemma 5.4 A vector c = (c_{1}, …, c_{n}) ∈ ℤ^{n} is a content vector for some skew standard Young tableaux if and only if for all 1 ≤ i < j ≤ n

c_{i} = c_{j} ⟹ ∃ r_{1}, r_{2} ∈ [i+1, j −1] such that c_{r_{1}} = c_{i}+1 and c_{r_{2}} = c_{i}−1. (4)

Proof. It is clear that if (c_{1}, …, c_{n}) is the content vector of some skew standard Young tableaux T then the condition is satisfied.

Conversely, let (c_{1}, …, c_{n}) ∈ ℤ^{n} be such that (4) holds. We will show that there exists a skew standard Young tableau T such that cont(T) = (c_{1}, …, c_{n}). We proceed by induction on n, the existence of T being clear if n ≤ 2. By the induction hypothesis, there exists a skew standard Young tableau T′ of shape λ/μ such that cont(T′) = (c_{1}, …, c_{n−1}). If c_{n} ≠ c_{ℓ} for all ℓ ∈ [n − 1] then one can add a box containing n into the c_{n}-th diagonal of T′, outside λ, to obtain a skew standard Young tableau T such that cont(T) = (c_{1}, …, c_{n}). Otherwise, let

k := max{ℓ ∈ [n − 1] : c_{ℓ} = c_{n}}.

By our hypothesis there exist r_{1}, r_{2} ∈ [k + 1, n − 1] such that c_{r_{1}} = c_{k} + 1 and c_{r_{2}} = c_{k} − 1. If k is in box (i, j) of T′ then r_{1} must be in box (i, j + 1), and r_{2} in box (i + 1, j). Box (i + 1, j + 1) of T′ is empty, since k is maximal. Placing n in box (i + 1, j + 1) yields a skew standard Young tableau T such that cont(T) = (c_{1}, …, c_{n}), as desired. □

Proof of Theorem 5.1. Combine Lemma 5.3 with Lemma 5.4. □

5.2 Cell Elements and Tableaux

By Theorem 5.1, a minimal AY cell (containing the identity) for S_{n} is defined by a sum zero vector f ∈ ℤ^{n} such that Δ f = Δ cont(T) ∈ ℤ^{n−1} for some standard Young tableaux T of skew shape. We will show that there is a bijection between the elements of K_{id}^{f} and the standard Young tableaux of the same shape as T.

Let T be a standard Young tableau (of skew shape), and let f ∈ ℤ^{n} be a sum zero vector with Δ f := Δ cont(T) ∈ ℤ^{n−1}. View f as a vector in V, and consider the corresponding cell K_{id}^{f}.

Theorem 5.5 For any π ∈ S_{n},

π ∈ K_{id}^{f} ⟺ the tableau T^{π} is standard,

where T^{π} is the tableau obtained from T by replacing each entry i by π(i) (1 ≤ i ≤ n).

Corollary 5.6 The size of K_{id}^{f} is equal to the number of standard Young tableaux of the same shape as T.

Theorem 5.5 follows from the following observation.

Observation 5.7 For a standard Young tableau T and any 1 ≤ i < n, exactly one of the following 3 cases holds:

(1) i + 1 is adjacent to i in the same row of T, and then

Δ cont(T)_{i} = 1.

(2) i + 1 is adjacent to i in the same column of T, and then

Δ cont(T)_{i} = −1.

(3) i + 1 and i are not in the same row or column of T, and then

|Δ cont(T)_{i}| ≥ 2.

Note that i + 1 and i cannot be in the same diagonal of T: Δ cont(T)_{i} ≠ 0.

Lemma 5.8 Assume that π ∈ K_{id}^{f} and T^{π} is standard. Then, for any 1 ≤ i < n:

πs_{i} ∈ K_{id}^{f} ⟺ T^{πs_{i}} is standard.

Proof. Consider π ∈ K_{id}^{f} and 1 ≤ i < n. Then:

\frac{1}{ȧ_{πs_{i}π^{−1}}} = ⟨f, α_{πs_{i}π^{−1}}⟩ = ⟨f, α_{(π(i),π(i+1))}⟩ = ±Δ cont(T^{π})_{i},  (5)

where “±” is the sign of π(i + 1) − π(i). Thus

ȧ_{πs_{i}π^{−1}} ≠ ±1 ⟺ Δ cont(T^{π})_{i} ≠ ±1.

Since π ∈ K_{id}^{f}, it follows that

ȧ_{πs_{i}π^{−1}} ≠ ±1 ⟺ πs_{i} ∈ K_{id}^{f}.

By Observation 5.7, this means that πs_{i} ∈ K_{id}^{f} if and only if i and i + 1 are not in the same row or column of T^{π}. Thus, for π ∈ K_{id}^{f} with T^{π} standard:

πs_{i} ∈ K_{id}^{f} ⟺ T^{πs_{i}} is standard.

□

The proof of Theorem 5.5 is now clear. □

In contrast to Kazhdan-Lusztig theory, where the bijection between cell elements and tableaux is given by the RSK algorithm, the above bijection between elements of the cell K_{id}^{f} and tableaux is extremely simple.

A complete characterization of minimal AY cells for S_{n} now follows.

Theorem 5.9 Let K be a nonempty subset of the symmetric group S_{n}, and let σ ∈ K. Then K is a minimal AY cell if and only if there exists a standard Young tableau Q such that

σ^{−1}K = {π ∈ S_{n}| Q^{π} is standard},

where Q^{π} is the tableau obtained from Q by replacing each entry i by π(i).

Proof. First observe that any basic flat of the symmetric group contains an integer valued vector. Combining this observation with Theorem 4.4 and Observation 3.1 allow one to reduce the discussion to minimal AY identity cells, determined by integer valued linear functionals. Theorem 5.1 completes the proof. □

5.3 Young Orthogonal Form

This subsection contains explicit representation matrices, which are deduced from the previous analysis. In particular, it is shown that all irreducible S_{n}-representations may be obtained from our construction (Theorem 5.11 below).

Let K ⊆ S_{n} be a convex set and let f be an integer K-generic vector. Consider the S_{n}-representation ρ_{id}^{f}. By Corollary 5.6, a basis of the representation space of ρ_{id}^{f} may be indexed by the set of standard Young tableaux of a certain shape.

Corollary 5.10 (Young Orthogonal Form for Skew Shapes) Let T be a skew standard Young tableau of shape λ/μ (μ possibly empty), let f = Δ cont(T), and let ρ := ρ_{id}^{f}. Then the ρ-action of the generators in on a basis indexed by tableaux is given by

ρ_{s_{i}}(Q) = \frac{1}{h(i)}Q + \sqrt{1 − \frac{1}{h(i)^{2}}} Q^{s_{i}},

where h(i) := c(i + 1) − c(i) in Q, and Q^{s_{i}} is the tableau obtained from Q by interchanging i and i + 1.

Proof. Combine Theorem 3.8 with Theorem 5.5 and equation (5), noticing that, by definition, h(i) = Δ cont(T)_{i}. □

Theorem 5.11 Let λ/μ be a skew shape of order n (μ possibly empty) and let T be a standard Young tableau of shape λ/μ. If f = Δ cont(T) then

ρ_{id}^{f} ≅ S^{λ/μ},

where S^{λ/μ} is the skew Specht module corresponding to λ/μ.

Proof. For a skew shape λ/μ the representation matrices of the generators in Corollary 5.10 are identical to those given by the classical Young orthogonal form (Theorem 2.5). □

Corollary 5.12 The complete list of minimal AY representations of the symmetric group S_{n} is given (up to isomorphism) by the skew Specht modules S^{λ/μ}, where λ/μ is of order n (and μ possibly empty).

In particular, every irreducible representation of the symmetric group S_{n} may be realized as a minimal abstract Young representation.

6 The Irreducibles Representations of B_{n} are AY

We begin with the following lemma.

Lemma 6.1 Let (W, S) be a finite Coxeter system and let J_{1}, J_{2} be disjoint subsets of S. Let (K_{1}, ρ_{1}), (K_{2}, ρ_{2}) be minimal AY pairs of W_{J_{1}}, W_{J_{2}} respectively, and let W^{J_{1}∪J_{2}} be the set of representatives of minimal length of the right cosets of the parabolic subgroup W_{J_{1}∪J_{2}} in W. Then

(K_{1}K_{2}W^{J_{1}∪J_{2}}, ρ_{1} ⊗ ρ_{2} ↑_{W_{J_{1}}×W_{J_{2}}}^{W})

is a minimal AY pair of W.

Proof. By the definition of a minimal AY pair, (K_{1}K_{2}, ρ_{1} ⊗ρ_{2}) is a minimal AY pair of W_{J_{1}}W_{J_{2}} = W_{J_{1}∪J_{2}}. The lemma now follows from Theorem 3.9.

□

Let λ be a partition of k, μ be a partition of n−k, and let P be a standard Young tableau of shape λ on the letters 1, …, k and Q be a standard Young tableau of shape μ on the letters k +1, …, n. Denote by S_{[i,j]} the symmetric group on the letters i, i + 1, …, j. Then

Corollary 6.2 The subset of all shuffles of permutations from

{π ∈ S_{[1,k]}| P^{π} is standard}

with permutations from

{σ ∈ S_{[k+1,n]}| Q^{σ} is standard}

is a minimal AY cell in S_{n}, which carries a minimal AY representation isomorphic to the outer product S^{λ} ⊗ S^{μ} ↑_{S_{k}×S_{n−k}}^{S_{n}}.

Proof. Denote by Ω_{k,n} the set of all shuffles of 1, ⋯, k with k + 1, ⋯, n. It is well known that Ω_{k,n} is the set of all representatives of minimal length of right cosets of S_{[1,k]} × S_{[k+1,n]} in S_{n}. The set considered in the corollary is the product

{π ∈ S_{[1,k]}| P^{π} is standard} · {σ ∈ S_{[k+1,n]}| Q^{σ} is standard} · Ω_{k}.

The corollary now follows from Lemma 5.8 and Theorem 5.11 together with Lemma 6.1.

□

Denote the subset of all shuffles considered in Corollary 6.2 by B_{P,Q} and the associated AY representation by ρ. The representation matrices of the Coxeter generators of S_{n} on V_{B_{P,Q}} are given by

Corollary 6.3

ρ_{s_{i}}C_{π} = \{ \begin{matrix}C_{πs_{i}}, & if π(i) ≤ k < π(i + 1) \\ & or π(i + 1) ≤ k < π(i); \\ \frac{1}{h(π,i))}C_{π} + \sqrt{1 − \frac{1}{h(π,i))^{2}}} C_{πs_{i}} & otherwise, \end{matrix}

where h(π, i)) := c(π(i + 1)) − c(π(i)) in P if both π(i) and π(i + 1) are ≤ k, and in Q if both are > k.

Proof. By Remark 3.10, noticing that if π = mr, where m ∈ S_{[1,k]} ×S_{[k+1,n]} and r is a shuffle in Ω_{k,n} then rs_{i} ∈ Ω_{k,n} if and only if π^{−1}(i) ≤ k < π^{−1}(i+1) or π^{−1}(i+1) ≤ k < π^{−1}(i). The coefficients in the second case are determined, by Remark 3.10 together with Theorem 5.1 and Corollary 5.10, by the content vectors of P and Q.

□

We will show, now, that the subset B_{P,Q} ⊆ S_{n} is a minimal AY cell in B_{n}, when S_{n} is embedded in B_{n} as a maximal parabolic subgroup.

Proposition 6.4 The subset B_{P,Q} ⊆ B_{n} is a minimal AY representation of B_{n}, where the action of the simple reflections s_{i}, 1 ≤ i < n, is determined as in Corollary 6.3 and the action of s_{0} is determined by

ρ_{s_{0}}C_{π} = \{ \begin{matrix}C_{π}, & if π(1) ≤ k; \\ −C_{π}, & otherwise. \end{matrix}

Proof. By Corollaries 6.2 and 6.3 it suffices to verify the relations involving s_{0}. Clearly, ρ_{s_{0}} commutes with ρ_{s_{i}} for all i > 1 as π(1) = πs_{i}(1) for all i > 1. To verify the relation (ρ_{s_{0}}ρ_{s_{1}})^{4} = 1 we have to check four cases:

(1) If π(1) and π(2) are ≤ k then both C_{π} and C_{πs_{1}} are invariant under ρ_{s_{0}}, thus (ρ_{s_{0}}ρ_{s_{1}})^{2}C_{π} = ρ_{s_{1}}^{2}C_{π} = 1.

(2) If π(1) and π(2) are > k then both C_{π} and C_{πs_{1}} are eigenvectors of ρ_{s_{0}} with eigenvalue −1, thus again (ρ_{s_{0}}ρ_{s_{1}})^{2}C_{π} = ρ_{s_{1}}^{2}C_{π} = 1.

(3) If π(1) ≤ k and π(2) > k then ρ_{s_{0}}C_{π} = C_{π} and ρ_{s_{0}}C_{πs_{1}} = −C_{πs_{1}}, thus

(ρ_{s_{0}}ρ_{s_{1}})^{2}C_{π} = ρ_{s_{0}}ρ_{s_{1}}ρ_{s_{0}}C_{πs_{1}} = −ρ_{s_{0}}ρ_{s_{1}}C_{πs_{1}} = −ρ_{s_{0}}C_{π} = −C_{π}.

Hence, (ρ_{s_{0}}ρ_{s_{1}})^{4}C_{π} = C_{π}.

(4) The case π(1) > k and π(2) ≤ k is similar to Case (3) and is left to the reader.

□

We deduce

Theorem 6.5 The irreducible representation of the classical Weyl group B_{n} are minimal AY.

Proof. As before, Let λ be a partition of k and let μ be a partition of n−k, let P be a standard Young tableau of shape λ on the letters 1, …, k and Q be a standard Young tableau of shape μ on the letters k + 1, …, n. There is a natural bijection between all pairs of standard Young tableaux of shapes λ and μ and elements in the subset B_{P,Q} : (P, Q)^{π} ⟷ π^{−1}, where (P, Q)^{π} is the ordered pair of tableau obtained from (P, Q) by replacing each entry i by π(i). The Young Form presented in Proposition 6.4 is identical to the classical one given in Theorem 2.6, along this bijection.

□

7 Top Elements

7.1 Intervals and Convexity

Proposition 7.1 All intervals in the weak Bruhat poset are convex.

Proof. Let [v, w] be an interval in the right weak Bruhat poset of a Coxeter group W. By [2, Proposition 3.1.3], for every element u ∈ W:

u ∈ [v, w] ⟺ Des_{T} (v) ⊆ Des_{T} (u) ⊆ Des_{T} (w).

Thus, the interval [v, w] is the generalized descent class W_{A}^{D} with D = Des_{T} (v) and A = (T \ Des_{T} (w)) ∪ Des_{T} (v). Tits’ result (Theorem 2.1) completes the proof. □

It should be noted that intervals in the strong Bruhat poset are not necessarily convex.

Problem 7.2 Characterize partial orders on W for which all intervals are convex.

The following is a reformulation of a remarkable theorem due to Kriloff and Ram (and based on results of Loszoncy [15]).

Theorem 7.3 [14, Theorem 5.2] Let W be a crystallographic reflection group. Then every minimal AY cell is a left translate of an interval (in the right weak Bruhat poset).

Remark 7.4 By Observation 3.1, one can assume that the intervals are of the form [e, w].

In [1, Corollary 4.4(i)] we proved that every minimal AY cell in a simply laced (???) Coxeter group is convex (in the right weak Bruhat poset). Combining Theorem 7.3 with Proposition 7.1 gives

Corollary 7.5 Let W be a crystallographic reflection group. Then every minimal AY cell is convex (in the right weak Bruhat poset).

7.2 Top Elements in S_{n}

Definition 7.6 An element w ∈ W is a top element if the interval [e, w] is a minimal AY cell and any minimal AY representation on the interval [e, w] is irreducible.

The top elements of the symmetric group S_{n} are characterized in this subsection.

Definition 7.7 Let T be a skew standard Young tableau.

1. T is a row (column) tableau if and only if the entries in row (column) j are bigger than the entries in all preceding rows (columns).

2. The row word of T is obtained by reading T row by row from right to left. The column word of T is obtained by reading T column by column from bottom to top.

Example 7.8 The tableau

1 2 3 4 5

is a row tableau. Its row word is the permutation [3, 2, 1, 5, 4] ∈ S_{5} and its column word is [4, 1, 5, 2, 3] ∈ S_{5}.

There is a bijection between top elements of S_{n} and partitions of n. More explicitly:

Theorem 7.9 A permutation π ∈ S_{n} is a top element if and only if π is the column word of a row standard Young tableau of shape λ, where λ is a partition of n.

To prove this theorem we need the following lemma.

Lemma 7.10 Let Q be a standard Young tableau of order n. The set {π ∈ S_{n}| Q^{π} is standard} is an interval in the right weak Bruhat order if and only if Q is either row or column tableau. The maximal element in the interval is the column (resp. row) word of the tableau.

Proof. Denote B_{Q} := {π ∈ S_{n}| Q^{π} is standard}.

First, we prove the easy direction. Assume that Q is a row tableau. By Theorems 5.9 and 3.2, B_{Q} is convex. Thus, to prove that B_{Q} is an interval it suffices to show that there is a unique element π ∈ B_{Q}, such that πs ∉ B_{Q} for all s ∉ Des(π). Indeed, if σ ∈ B_{Q} and Q^{σ} is not the column tableau then there exists i (1 ≤ i ≤ n − 1) such that i + 1 is southwest of i in Q^{σ}. In this case, σs_{i} ∈ B_{Q} and ℓ(σs_{i}) > ℓ(σ). If σ ∈ B_{Q} and Q^{σ} is the column tableau then there is no i (1 ≤ i ≤ n − 1) such that i + 1 is southwest of i in Q^{σ}. In this case, if σs_{i} ∈ B_{Q} then ℓ(σs_{i}) < ℓ(σ). We conclude that the unique maximum σ is the column word of the row tableau Q.

Similarly, for column tableau Q.

Now we prove the opposite direction. Assume that Q is a not a row or column tableau. We will show that B_{Q} has at least two local maximums. Thus, B_{Q} is not an interval.

If the standard Young tableau Q is a not a row or column tableau then Q is of at least two rows and two columns. Without loss of generality, the letter 2 is in the first row (i.e., at (1, 2)). Then the letter at (λ′_{1}, 1) is bigger than 2.

To find the first local maximum, start with π ∈ B_{Q}, such that Q^{π} is a column tableau and proceed “up” in B_{Q}. Observe that each step in this process is a right multiplication by s_{i} such that the resulting permutation is in B_{Q} and longer. To satisfy this, i and i + 1 could not be in same row or column in Q^{π} (where at each step we substitute πs_{i} := π). Also, the letter of Q in the box of i in Q^{π} must be bigger than the letter of Q in the box of i + 1 in Q^{π}. The letter in (1, 2) is the minimal one in the subtableau consisting all columns except the first one. Thus cannot move along the process. We conclude Claim 1. For every j, 1 ≤ j ≤ λ′_{1} +1, the position of the letter j is invariant under this process. For j ≤ λ′_{1} the position is (j, 1); the position of λ′_{1} + 1 is (1, 2).

Thus, we obtained one maximal element, which is determined by a tableau with 1, ..., λ′_{1} in the first column.

As Q is not a row tableau there exists a minimal row j for which the letter in Q in (j, λ_{j}) is bigger than the letter in (j + 1, 1). To find the second local maximum, start with a permutation in B_{Q} determined by the standard Young tableau of same shape as Q, in which the first letters are placed in the subshape {(a, b)| b ≤ λ_{j}} in a lexicographic order, and the rest are placed in the remaining “upper right corner” in lexicographic order. We proceed “up” as before; namely, by a right multiplication by s_{i} such that the resulting permutation is in B_{Q} and longer. Claim 2. The set of boxes in which the letters 1, ..., j ·λ_{j} −1 are located (in the resulting tableau) and the location of j · λ_{j} and j · λ_{j} + 1 are invariant under this process.

To verify this, it suffices to show that the location of j ·λ_{j} +1 is invariant under this process. Indeed, notice that as long as j · λ_{j} + 1 is in the box (j + 1, 1) j · λ_{j} must be located in (j, λ_{j}) (as it cannot switch with j · λ_{j} − 1 which is located either in same row or column of j · λ_{j}). But the letters in Q in (j + 1, 1) and (j, λ_{j}) are in inverse order; thus replacing j · λ_{j} + 1 with j · λ_{j} will shorten the permutation (and is not “up”!).

We also cannot replace j · λ_{j} + 1 with j · λ_{j} + 2. To verify this notice that j · λ_{j} + 2 has three possible locations during our process: (j + 1, 2), (j + 2, 1) and (1, λ_{j} + 1). If it is located in (j + 1, 2) it is in same row of j · λ_{j} + 1 and thus switching them gives a nonstandard tableau; thus sends us out of B_{Q}. If it is located in (j + 2, 1) it is in same column of j · λ_{j} + 1 and thus switching them sends us out of B_{Q}. So, we may assume that j · λ_{j} + 2 is located in (1, λ_{j} + 1). In this case j > 1 and by the definition of j the letter in Q in (1, λ_{j} + 1) is less than the letter in Q in (2, 1), which is, in turn, less than the letter in (j + 1, 1). Thus we cannot switch j · λ_{j} + 1 and j · λ_{j} + 2 in this case too.

To complete the proof, notice that the letter at (λ′_{1}, 1) in the first maximal tableau is λ′_{1}, while in the second maximal tableau it is bigger. Thus the processes determine two different maximal tableaux. □

Proof of Theorem 7.9. By Corollary 5.12, the derived content vector of a standard Young tableau of shape λ/μ gives an irreducible representation if and only if μ is the empty partition. This fact together with Theorem 5.9 imply that σ ∈ S_{n} is a top element if and only if [e, σ] = {π ∈ S_{n} | Q^{π} is standard} for some standard tableau Q. Lemma 7.10 completes the proof. □

References

[1] R. M. Adin, F. Brenti and Y. Roichman, A unified construction of Coxeter group representations (I), Adv. Appl. Math., to appear, arXiv math.RT/0309364.

[2] A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Springer Verlag, to appear.

[3] D. Barbasch and D. Vogan, Primitive ideals and orbital integrals in complex exceptional groups, J. Algebra 80 (1983), 350–382.

[4] A. Björner and M. Wachs, Generalized quotients in Coxeter groups, Trans. Amer. Math. Soc. 308 (1988), 1–37.

[5] A. Björner and M. Wachs, Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A 58 (1991), 85–114.

[6] R. Dipper and G. D. James, Representations of Hecke algebras of general linear groups, Proc. London Math. Soc. 52 (1986), 20–52.

[7] A. M. Garsia and J. Remmel, Shuffles of permutations and the Kronecker product, Graphs and Combinatorics 1 (1985), 217–263.

[8] M. Geck, On the induction of Kazhdan-Lusztig cells, Bull. London Math. Soc. 35 (2003), 608–614.

[9] C. Greene, A rational-function identity related to the Murnaghan-Nakayama formula for the characters of S_{n}, J. Alg. Combin. (1992), 235–255.

[10] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Adv. Math. 29, Cambridge Univ. Press, Cambridge, 1990.

[11] G. D. James, The Representation Theory of the Symmetric Groups, Lecture Notes in Math. 682, Springer-Verlag, 1978.

[12] G. D. James and A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Math. and its Appl. 16, Addison-Wesley, 1981.

[13] D. Kazhdan and G. Lusztig, Representations of Coxeter groups and Hecke algebras, Invent. Math. 53 (1979), 165–184.

[14] C. Kriloff and A. Ram, Representations of graded Hecke algebras, Rep. Theory 6 (2002), 31–69.

[15] J. Loconczy, Standard Young tableaux in the Weyl group setting, J. Algebra 220 (1999), 255–260.

[16] A. Okounkov and A. M. Vershik, A new approach to representation theory of symmetric groups, Selecta Math. (N. S.) 2 (1996), 581–605.

[17] I. A. Pushkarev, On the theory of representations of the wreath products of finite groups and symmetric groups, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov (POMI) 240 (1997), Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 2, 229–244, 294–295; translation in J. Math. Sci. (New York) 96 (1999), 3590–3599.

[18] A. Ram, Affine Hecke algebras and generalized standard Young tableaux, J. Algebra 230 (2003), 367–415.

[19] A. Ram, Skew representations are irreducible, Contemp. Math. 325 (2003), 161–189.

[20] Y. Roichman, Induction and restriction of Kazhdan-Lusztig cells, Adv. Math. 134 (1998), 384–398.

[21] B. E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms & Symmetric Functions, Wadsworth and Brooks/Cole, Monterey, CA, 1991.

[22] M. P. Schützenberger, La correspondence de Robinson, In: Combinatoire du Groupe Symmetrique, Lecture Notes in Math. 579, pp. 59–113, Springer-Verlag, 1977.

[23] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Studies in Adv. Math. 62, Cambridge Univ. Press, Cambridge, 1999.

[24] J. Stembridge, personal communication, 2004.

[25] J. Tits, Buildings of Spherical Type and Finite BN-Pairs, Lecture Notes in Math. 386, Springer-Verlag, Berlin and New-York, 1974.

[26] A. Vershik, Local algebras and a new version of Young’s orthogonal form, in: Topics in Algebra, Banach Center Publications, Vol. 26 Part 2, PWN-Polish Scientific Publications, Warsaw 1990, 467–473.