Noncommutative Symmetric Functions IV:

(1)

Noncommutative Symmetric Functions IV:

Quantum Linear Groups and Hecke Algebras at q = 0

DANIEL KROB dk@litp.ibp.fr

LIAFA (CNRS), Universit´e Paris 7, 2, place Jussieu, 75251 Paris Cedex 05, France

JEAN-YVES THIBON jyt@univ-mlv.fr

IGM, Universit´e de Marne-la-Vall´ee, 2, rue de la Butte-Verte, 93166 Noisy-le-Grand Cedex, France Received March 28 , 1996; Revised July 30, 1996

Abstract. We present representation theoretical interpretations of quasi-symmetric functions and noncommu- tative symmetric functions in terms of quantum linear groups and Hecke algebras at q=0. We obtain in this way a noncommutative realization of quasi-symmetric functions analogous to the plactic symmetric functions of Lascoux and Sch¨utzenberger. The generic case leads to a notion of quantum Schur function.

Keywords: quasisymmetric function, quantum group, Hecke algebra

1. Introduction

This paper, which is intended as a sequel to [6, 9, 21], is devoted to the representation theoretical interpretation of noncommutative symmetric functions and quasi-symmetric functions. These objects, which are two different generalizations of ordinary symmetric functions [9, 10], build up two Hopf algebras dual to each other, and have been shown to provide a Frobenius type theory for Hecke algebras of type A at q = 0, playing the same rˆole as the classical correspondence between symmetric functions and characters of symmetric groups [7] (which extends to the case of the generic Hecke algebra).

In the classical case, the interpretation of symmetric functions in terms of representations of symmetric groups is equivalent, via Schur-Weyl duality, to the fact that Schur functions are the characters of the irreducible polynomial representations of general linear groups.

Equivalently, instead of working with polynomial representations of GL(n), one can use comodules over the Hopf algebra of polynomial functions over GL(n)[11]. This Hopf algebra is known to admit interesting q-deformations (quantized function algebras; see [8]

for instance) to which Schur-Weyl duality can be extended for generic values of q, the symmetric group being replaced by the Hecke algebra.

The standard version of the quantum linear group is not defined for q =0. The theory of crystal bases [16], which allows to “take the limit q →0” in certain modules by working with renormalized operators modulo a lattice, describes the combinatorial aspects of the generic case, and provides illuminating interpretations of classical constructions such as the Robinson-Schensted correspondence, the Littlewood-Richardson rule and the plactic monoid [3, 17, 24, 26].

(2)

P1: RPS/PCY P2: MVG/ASH QC: MVG

Journal of Algebraic Combinatorics KL472-03-Krob August 6, 1997 10:34

340 KROB AND THIBON

However, another version exists [4] which plays an equivalent rˆole for generic values of q, but in which one can specialize q to 0. This specialization is quite different of what is obtained with crystal bases, and leads to an new interpretation of quasi-symmetric functions and noncommutative symmetric functions analogous to the interpretation of ordinary sym- metric functions as polynomial characters of GL(n). Moreover, this interpretation allows to give a realization of quasi-symmetric functions similar to the plactic interpretation of symmetric functions (see Section 6.2). The plactic algebra is here replaced by one of its quotients, and instead of ordinary Young tableaux one has to use skew tableaux of ribbon shape, and dual objects called quasi-ribbons, for which Schensted type algorithms can be constructed. In fact, most aspects of the classical theory can be adapted to this highly degenerate case. As this is an example of a non-semisimple case for which everything can be worked out explicitely, one can expect that this treatment could serve as a guide for understanding the more complicated degeneracies at roots of unity.

This paper is structured as follows. We first recall the basic definitions concerning noncommutative symmetric functions and quasisymmetric functions (Section 2) and review the Frobenius correspondence for the generic Hecke algebras (Section 3). Next we introduce the Dipper-Donkin version of the quantized function algebra of the space of n×n matrices (Section 4). We describe some interesting subspaces (Sections 4.5 and 4.6), and prove that the q = 0 specialization of the diagonal subalgebra is a quotient of the plactic algebra, which we call the hypoplactic algebra (Section 4.7). Next, we review the representation theory of the 0-Hecke algebra and its interpretation in terms of quasi-symmetric functions and noncommutative symmetric functions, providing the details which were omitted in [7].

In Section 6, we introduce a notion of noncommutative character for Aq(n)-comodules, and prove that these characters live in the diagonal subalgebra. For generic q, the characters of irreducible comodules are quantum analogues of Schur functions. For q=0, we show that hypoplactic analogues of the fundamental quasi-symmetric functions FI (quasi-ribbons) can be obtained as the characters of irreducible A0(n)comodules, and give a similar construction for the ribbon Schur functions. These constructions lead to degenerate versions of the Robinson-Schensted correspondence, which are discussed in Section 7.

2. Noncommutative symmetric functions and quasi-symmetric functions

2.1. Noncommutative symmetric functions

The algebra of noncommutative symmetric functions [9] is the free associative algebra Sym = QhS1,S2, . . .i generated by an infinite sequence of noncommutative indetermi- nates Sk, called the complete symmetric functions. One defines S^I=Si₁Si₂ · · · Si_r for any composition I=(i1,i2, . . . ,ir)∈(N^∗)^r. The family(S^I)is a linear basis of Sym. Although it is convenient to define Sym as an abstract algebra, a useful realisation can be obtained by taking an infinite alphabet A = {a1,a2, . . .}and defining its complete homogeneous symmetric functions by

−→Y

i≥1

(1−tai)⁻¹=X

n≥0

tⁿSn(A) (1)

(3)

Although these elements are not symmetric for the usual action of permutations on the free algebra, they are invariant under the Lascoux-Sch¨utzenberger action of the symmetric group [23], which can now be interpreted as a particular case of Kashiwara’s action of the Weyl group on the U_q(sln)-crystal graph of the tensor algebra [24].

The set of all compositions of a given integer n is equipped with the reverse refinement order, denoted¹. For instance, the compositions J of 4 such that J¹(1,2,1)are exactly (1, 2, 1), (3, 1), (1, 3) and (4). The ribbon Schur functions(R_I)can then be defined by

S^I =X

J¹I

RJ or RI =X

J¹I

(−1)^`(^I^)−`(^J⁾S^J,

where`(I)denotes the length of I . The family(RI)is another homogeneous basis of Sym.

The commutative image of a noncommutative symmetric function F is the ordinary symmetric function f obtained by applying to F the algebra morphism which maps Snto the complete homogeneous function hn(our notations for commutative symmetric functions will be those of [28]). The ribbon Schur function R_I is then mapped to the corresponding ordinary ribbon Schur function, which will be denoted by r_I.

Ordinary symmetric functions are endowed with an extra product∗, called the internal product, which corresponds to the multiplication of central functions on the symmetric group. A noncommutative analog of this product can be defined, the character ring ofS_n being replaced by its descent algebra [35] (see also below) .

Recall that i is said to be a descent ofσ∈Sn ifσ (i) > σ(i +1). The set Des(σ )of these integers is called the descent set ofσ. If I =(i1, . . . ,ir)is a composition of n, one associates with it the subset D(I)= {d1, . . . ,dr−1}of [1,n−1] defined by dk=i1+ · · · +ik

for k∈[1,r−1]. Let DI be the sum inZ[Sn] of all permutations with descent set D(I). As shown by Solomon [35], the DI form a basis of a subalgebra ofZ[Sn] called the descent algebra ofSnand denoted by6n. One can define an isomorphism of graded vector spaces

α: Sym=M

n≥0

Sym_n →6=M

n≥0

6n

by settingα(R_I)= D_I. Observe thatα(S^I)is then equal to D_⊆_I, i.e., to the sum of all permutations ofS_nwhose descent set is contained in D(I).

2.2. Quasi-symmetric functions

As proved in [29] (see also [9]), the algebra of noncommutative symmetric functions is in natural duality with the algebra of quasi-symmetric functions, introduced by Gessel in [10]. Let X= {x1,x2, . . . ,xn · · ·}be a totally ordered set of commutative indeterminates.

An element f ∈ C[X ] is said to be a quasi-symmetric function if for each composition K =(k1, . . . ,km)all the monomials x_i^k₁¹x_i^k₂²· · ·x_i^k_m^m with i1 <i2 <· · ·<imhave the same coefficient in f . The quasi-symmetric functions form a subalgebra QSym ofC[X ].

One associates with a composition I =(i₁, . . . ,i_m)the quasi-monomial function

MI = X

j₁<···<j_m

xⁱ_j¹

1· · ·xⁱ_j^m

m.

(4)

342 KROB AND THIBON

The family of quasi-monomial functions is clearly a basis of QSym. Another important basis of QSym is formed by quasi-ribbon functions which are defined by

FI =X

I¹J

MJ,

e.g., F122= M122+M1112+M1211+M11111. The pairingh·,·ibetween Sym and QSym [29] is then defined byhS^I,MJi =δIJor equivalently byhRI,FJi =δIJ. This duality is essentially equivalent to the noncommutative Cauchy identity

−→Y

i≥1

Ã_−→

Y

j≥1

(1−xiaj)⁻¹

!

=X

I

FI(X)RI(A), (2)

and can also be interpreted as the canonical duality between Grothendieck groups asociated to 0-Hecke algebras [7] (see Section 5).

3. Hecke algebras and their representations

3.1. Hecke algebras

The Hecke algebra HN(q)of type AN−1is theC(q)-algebra generated by N−1 elements (Ti)i=1,N−1with relations





T_i²=(q−1)Ti+q for i ∈[1,N−1], TiTi+1Ti=Ti+1TiTi+1 for i ∈[1,N −2], TiTj =TjTi for |i− j|>1.

The Hecke algebra HN(q)is a deformation of theC-algebra of the symmetric groupSN

(obtained for q =1). For generic complex values of q, it is isomorphic toC[SN] (and hence semi-simple) except when q =0 or when q is a root of unity. The first relation is often replaced by

T_i²=(q−q⁻¹)Ti+1 (3)

which is invariant under the substitution q → −q⁻¹ and is more convenient for working with Kazhdan-Lusztig polynomials and canonical bases. However the convention adopted here, i.e.,

T_i²=(q−1)T_i+q, (4)

is the natural one when q is interpreted as the cardinality of a finite field and H_N(q)as the endomorphism algebra of the permutation representation of GL_N(Fq)on the set on complete flags [14]. Moreover one can specialize q = 0 in relation (4). In the modular representation theory of GLN(Fq), the Hecke algebra corresponding to this specialization

(5)

occurs when q is a power of the characteristic of the ground field. For this reason, among others, it is interesting to consider the 0-Hecke algebra HN(0) which is theC-algebra obtained by specialization of the generic Hecke algebra H_N(q)at q =0. This algebra is therefore presented by





T_i²= −Ti for i ∈[1,N −1], TiTi+1Ti=Ti+1TiTi+1 for i ∈[1,N −2], TiTj =TjTi for |i− j|>1.

The representation theory of HN(0)was investigated by Norton who obtained a fairly complete picture [31]. Important specific features of the type A are described by Carter in [1]. The 0-Hecke algebra can also be realized as an algebra of operators acting on the equivariant Grothendieck ring of the flag manifold [22].

3.2. The Frobenius correspondence

We will see that the 0-Hecke algebra is the right object for giving a representation theoretical interpretation of noncommutative symmetric functions and of quasi-symmetric functions.

To emphasize the parallel with the well-known correspondence between representations of the symmetric group and symmetric functions, we first recall the main points of the classical theory.

Let Sym be the ring of symmetric functions and let R[S]= M

N≥0

R[SN]

be the ring of equivalence classes of finitely generated C[SN]-modules (with sum and product corresponding to direct sum and induction product). We know from the work of Frobenius that the character theory of the symmetric groupS_N can be described in terms of the characteristic mapF: R[S]→Sym which sends the class of a Specht module V_λ to the Schur function s_λ. The first point is thatFis a ring homomorphism. That is,

F³

[U⊗V ] ↑^S_S^N+M

N×SM

´=F([U ])F([V ])

for a SN-module U and a SM-module V . The second one is the character formula, which can be stated as follows: for any finite dimensionalSN-module V , the value of the chararacter of V on a permutation of the conjugacy class labelled by the partitionµis equal to the scalar product

χ(µ)= hF(V),p_µi

where p_µis the product of power sums p_µ₁· · ·p_µ_r.

This theory can be extended to the Hecke algebra H_N(q)when q is neither 0 nor a root of unity. The characteristic map is independent of q, and still maps the q-Specht module

(6)

344 KROB AND THIBON

V_λ(q)to the Schur function s_λ. The induction formula remains valid and the character formula has to be modified as follows (see [2, 18, 19, 32, 36, 37]). Define for a partition µ=(µ1, µ2, . . . , µr)of N the element

wµ=¡

σ1· · ·σµ1−1

¢¡σµ1+1· · ·σµ1+µ2−1

¢· · ·¡

σµ1+···+µr−1+1· · ·σN−1

¢

(whereσiis the elementary transposition(i i+1)). The character formula for HN(q)gives the valueχ_µ^λon T_w_µof the character of the irreducible q-Specht module V_λ(q). It reads

χ_µ^λ=tr_V_λ₍_q₎¡ T_w_µ¢

= hF(V_λ(q)),C_µ(q)i = hs_λ,C_µ(q)i

where C_µ(q)=(q−1)^l^(µ)h^µ((q −1)X)(inλ-ring notation, h^µ((q −1)X)denotes the image of the homogeneous symmetric function h^µ(X)under the ring homomorphism p_k 7→

(q^k−1)p_k).

4. The quantum coordinate ring Aq(n)

4.1. Tensor representations of HN(q) Let E= {e₁, . . . ,e_n}be a finite set and let

V = Mn

i=1

C(q)ei

be theC(q)-vector space with basis(ei). For v=ek₁⊗· · ·⊗ek_N ∈V^⊗^Nand i ∈[1,N−1], we define v^σⁱ by setting

v^σⁱ =ek₁⊗ · · ·ek_i−1⊗ek_i+1⊗ek_i⊗ek_i+2⊗ · · · ⊗ek_N.

Following [4, 5, 15], one defines a right action of HN(q)on V^⊗^N by





v·Ti =v^σⁱ if ki <ki+1, v·T_i =qv if k_i =k_i₊₁, v·T_i =qv^σⁱ +(q−1)v if k_i >k_i₊₁. This is a variant of Jimbo’s action [15] itself defined by





v·Ti =q¹^/²v^σⁱ if ki <ki+1, v·Ti =qv if ki =ki+1, v·Ti =q¹^/²v^σⁱ+(q−1)v if ki >ki+1.

(7)

Let(e_i^∗)1≤i≤n be the basis of V^∗dual to the basis(ei)of V . The dual (right) action of HN(q)on(V^∗)^⊗^Nis given by





v^∗·T_i =q(v^∗)^σⁱ if k_i <k_i₊₁, v^∗·T_i =qv^∗ if k_i =k_i₊₁, v^∗·T_i =(v^∗)^σⁱ +(q−1)v^∗ if k_i >k_i₊₁.

Example 4.1 Let V =C(q)e1⊕C(q)e2. The matrices describing the right action of T1

on V ⊗V and on V^∗⊗V^∗in the canonical bases of these spaces are

Rˇ=







q 0 0 0

0 0 q 0

0 1 q−1 0

0 0 0 q





, Rˇ^∗ =







q 0 0 0

0 0 1 0

0 q q−1 0

0 0 0 q





.

We also need the left actions of HN(q)on V^⊗^N and(V^∗)^⊗^N defined by

½Ti·v= −qv·T_i⁻¹ = −v·Ti+(q−1)v, T_i·v^∗= −qv^∗·T_i⁻¹= −v^∗·T_i+(q−1)v^∗. Equivalently, for v=e_k₁⊗ · · · ⊗e_k_N ∈(V)^⊗^N and v^∗=e_k^∗

1⊗ · · · ⊗e^∗_k

N ∈(V^∗)^⊗^N,





Ti·v= −v^σⁱ+(q−1)v, Ti·v^∗= −q(v^∗)^σⁱ+(q−1)v^∗ if ki <ki+1, Ti·v= −v, Ti·v^∗= −v^∗ if ki =ki+1, Ti·v= −qv^σⁱ, Ti·v^∗= −(v^∗)^σⁱ if ki >ki+1.

4.2. The Hopf algebra Aq(n)

The quantum group Aq(n)is theC(q)-algebra generated by the n²elements(xi j)1≤i,j≤n

subject to the defining relations





xj kxil =q xilxj k for i < j, k≤l, x_{i k}x_il=x_ilx_{i k} for every i,k,l, x_jlx_{i k}−x_{i k}x_jl =(q−1)x_ilx_{j k} for i < j, k<l.

This algebra is a quantization of the Hopf algebra of polynomial functions on the variety of n×n matrices introduced by Dipper and Donkin in [4]. It is not isomorphic to the classical quantization of Faddeev-Reshetikin-Takhtadzhyan [8], and although for generic values of q both versions play essentially the same rˆole, an essential difference is that the Dipper-Donkin algebra is defined for q =0.

Aq(n)is a Hopf algebra with comultiplication1defined by 1(xi j)=

Xn k=1

xi k⊗xk j.

(8)

346 KROB AND THIBON

Moreover one can define a left coactionδof Aq(n)on V^⊗^Nby δ(e_i)=

Xn j=1

x_{i j}⊗e_j

and the following property shows that A_q(n)is related to the Hecke algebras in a similar way as GL_nand the symmetric groups.

Proposition 4.2 [4] The left coactionδof A_q(n)on V^⊗^N commutes with the right action of H_N(q)on V^⊗^N. That is,the following diagram is commutative

V^⊗^N ^δ^⊗N → A_q(n)⊗V^⊗^N

h

↓ ↓

Id⊗h

V^⊗^N → A_q(n)⊗V^⊗^N

δ^⊗N

for every element h∈HN(q)considered as an endomorphism of V^⊗^N.

This property still holds for q =0. Thus, for any h ∈ HN(0), V^⊗^Nh will be a sub- A0(n)-comodule of V^⊗^N. This is this property which will allow us to define a plactic-like realization of quasi-symmetric functions. For later reference, note that the defining relations of A0(n)are





xj kxil =0 for i < j, k≤l, xi kxil =xilxi k for every i,k,l, xjlxi k=xi kxjl−xilxj k for i < j, k<l.

(5)

4.3. Some notations for the elements of Aq(n)

Each generator xi jof Aq(n)will be identified with a two row array and with an element of V ⊗V^∗modulo certain relations as described below:

x_{i j} =

·i j

¸

=e_i⊗e^∗_j.

For i=(i1, . . . ,ir), j =(j1, . . . ,jr)∈ [1,n]^r, let ei =ei1⊗ · · · ⊗eir and e^∗_j =e^∗_j₁⊗ · · ·

⊗e^∗_j

r. One can then identify the monomial x_ij =x_i₁_j₁· · ·x_i_r_j_r of A_q(n)with the two row array

·i1 i2 · · · ir

j1 j2 · · · jr

¸ ,

(9)

itself regarded as the class of the tensor ei⊗e_j^∗∈T^r(V ⊗V^∗)modulo the relations (e_i⊗e^∗_j ≡e^σ_i^r ⊗(e_j^∗·T_r) for each r such that i_r >i_r₊₁,

e_i⊗e^∗_j ≡e_i⊗(e^∗_j)^σ^r for each r such that i_r =i_r₊₁. (6) These relations are equivalent to

ei⊗e_j^∗≡ −Tr ·ei⊗(e^∗_j)^σ^r for each r such that jr ≤ jr+1. (7) 4.4. Linear bases of Aq(n)

For every i=(i1, . . . ,ir)∈[1,n]^r, let I(i)∈Nⁿbe defined by I(i)p=Card{i_k,k∈[1,r ],i_k= p}

for p∈[1,n]. For I,J ∈Nⁿ, set Aq(I,J)= X

I(i)=I,I(j)=J

C(q)xij.

Observe that(A_q(I,J))I,J∈Nⁿ defines a grading of A_q(n)compatible with multiplication.

A monomial basis compatible with this grading is constructed in [4]. The basis vectors, which are labelled by matrices M=(m_{i j})1≤i,j≤n ∈Mn(N)are

xM =¡

x₁₁^m¹¹x₁₂^m¹²· · ·x_1n^m¹ⁿ¢

· · ·¡

x_n1^mⁿ¹x_n2^mⁿ²· · ·x_nn^mⁿⁿ¢

∈ Aq(n).

It will be useful to introduce another monomial basis(x^M)of Aq(n), labelled by the same matrices, and defined by

x^M=¡

x_1n^m¹ⁿx^m_2n²ⁿ· · ·x_nn^mⁿⁿ¢

· · ·¡

x₁₁^m¹¹x₂₁^m²¹ · · · x_n1^mⁿ¹¢

∈ Aq(n).

Proposition 4.3 For any q∈C,the family(x^M)M∈Mn(N)is a homogeneous linear basis of Aq(n).

Proof: It is clearly sufficient to prove that each basis element x_M can be expressed in terms of the x^N. Using the array and tensor notations, such an element can be represented by

x_M =

·· · · i₁ i₂ · · ·

· · · j1 j2 · · ·

¸

=e_i⊗e^∗_j,

where j1 is the maximal element of the second row of this array and where i1 ≤ i2. The maximality of j1and relation (7) imply

xM =(−1)^`(σ)T_σei⊗ej =

µ(−1)^l^(σ)T_σ Id

¶

·

·i1 · · · i2 · · · j1 · · · j2 · · ·

¸

(10)

348 KROB AND THIBON

for some permutationσ. By induction on the length of xM, there exists some other permu- tationτ such that

xM =

µ(−1)^l^(τ)T_τ Id

¶

·

·i1 · · · ir · · · k1 · · · ks

j1 · · · j1 · · · 1 · · · 1

¸ .

Going back to the definition of the left action of HN(q)and to relations (6), this implies that xMis aZ[q]-linear combination of elements of the form

·i1 · · · ir · · · k1 · · · ks

n · · · n · · · 1 · · · 1

¸ ,

from which the conclusion follows immediately. 2

4.5. The standard subspace of Aq(n)

The restrictions to the standard component of A_q(n)of the transition matrices between the two bases(x_M)and(x^M)have an interesting description.

Definition 4.4 The standard subspace Sq(n)of Aq(n)is Sq(n)=Aq(1ⁿ,1ⁿ)= M

σ∈Sn

C(q)x_σ

where x_σ =x1σ (1)x2σ (2)· · ·xnσ(n)forσ ∈Sn.

The following result is an immediate consequence of Proposition 4.3.

Proposition 4.5 One has Sq(n)= M

σ∈Sn

C(q)x^σ

where x^σ =x_σ(n)n · · · x_{σ (}2)2x_{σ (}1)1.

The elements of the transition matrices between the two bases(x_σ)_σ∈Sn and(x^σ)_σ∈Sn

of Sq(n)are R-polynomials. Recall that the family(R_τ,σ(q))_σ,τ∈Sn of R-polynomials is defined by

(T_σ−1)⁻¹=ε(σ)q⁻^l^{(σ )} X

τ≤σ

ε(τ)R_τ,σ(q)T_τ∈Hn(q)

forσ ∈S_n (cf. [13]). The R-polynomial R_τ,σ(q)is inZ[q], has degree l(σ)−l(τ)and its constant term isε(σ τ).

(11)

Proposition 4.6 The bases(x^σ)and(x_σ)are related by x^σ =X

τ≤σ

R_τ,σ(q)x_ωτ and x_σ =X

τ≤σ

R_τ,σ(−q)x^ωτ

whereω=(n n−1· · ·1)and where≤is the Bruhat order.

Proof: In the notation of Section 4.3, we can write x^σ =e_σ⊗e_ω^∗ =e^σ₁₂_···_n⊗e^∗_ω≡e12···n⊗e^∗_ω·T_σ−1

≡e12···n⊗(−q)^l^{(σ )}T_σ⁻₋₁¹ ·e^∗_ω≡ e12···n⊗ ÃX

τ≤σ

ε(τ)R_τ,σ(q)T_τ

!

·e_ω^∗

≡e12···n⊗ ÃX

τ≤σ

R_τ,σ(q)e_ωτ^∗

!

=X

τ≤σ

R_τ,σ(q)x_ωτ.

The second relation can be proved in the same way. 2

Corollary 4.7 In A₀(n),one has x^σ =X

τ≤σ

ε(στ)x_ωτ and x_σ =X

τ≤σ

ε(σ τ)x_ωτ.

4.6. Decomposition of left and right standard subspaces at q=0

In the array notation, the standard subspace is spanned by arrays whose both rows are permutations. If one requires one row to be a fixed permutationσ, one obtains the left and right subcomodules of Aq(n)which are independent ofσfor generic q, but not for q=0.

Definition 4.8 The left and right standard subspaces of Aq(n), respectively denoted by Lq(n)and Rq(n), are defined by

Lq(n)= M

J=(j1,...,jn)∈Nⁿ

C(q)x1,j₁x2,j₂· · ·xn,j_n, Rq(n)= M

I=(i₁,...,i_r)∈N^r

C(q)xi_n,n· · ·xi₂,2xi₁,1.

We associate with a permutationσ ∈Snthe subspaces of Aq(n) Lq(n;σ)= X

J=(j1,...,jn)∈Nⁿ

C(q)x_σ(1),j₁x_σ(2),j₂· · ·x_σ(n),j_n, R_q(n;σ)= X

I=(i₁,...,i_r)∈N^r

C(q)x_i_n_,σ(_n₎· · ·x_i₂_,σ(₂₎x_i₁_,σ(₁₎.

For generic q, all the left (resp. right) subspaces are the same.

(12)

350 KROB AND THIBON

Proposition 4.9 If q ∈Cis nonzero and not a root of unity, Lq(n;σ )=Lq(n) and Rq(n;σ )=Rq(n).

Proof: Using the tensor notation of Section 4.3, we can write

e_σ⊗e^∗_J =e^σ₁₂_···_n⊗e^∗_J ≡e₁₂_···_n⊗e^∗_J·T_σ−1≡(e₁₂_···_n⊗e^∗_J)·(Id⊗T_σ−1)

for every J ∈Nⁿ, so that Lq(n;σ) ⊂ Lq(n). Moreover the asumptions on q imply that T_σ−1is invertible. The previous relation can therefore be read as

e₁₂_..._n⊗e^∗_J ≡(e_σ⊗e^∗_J)·(Id⊗(T_σ−1)⁻¹),

from which we get that L_q(n)⊂ L_q(n;σ ). The second equality is obtained in the same

way. 2

When q = 0, the subspaces L0(n;σ )and R0(n;σ )are not equal to L0(n)and R0(n). However, the proof of Proposition 4.9 shows that L0(n;σ)⊂L0(n)and R0(n;σ)⊂R0(n). The subspaces L0(n;σ )(resp. R0(n;σ )are right (resp. left) sub- A0(n)-comodules of L0(n) (resp. R0(n)), of which they form a filtration with respect to the weak order on the symmetric group. To prove this, let us introduce some notations. We associate to an integer vector I =(i₁, . . . ,i_n)ofNⁿthe two sets

Inv(I)= {(k,l),1≤k<l ≤n−1,ik>il}, Pos(I)= {(k,l),1≤k<l ≤n−1,i_k<i_l}.

Proposition 4.10 For every permutationσ ∈Sn,one has L0(n;σ )= M

J=(j1,...,jn) Inv(σ)⊂Inv(J)

Cx_{σ (}1),j₁· · ·x_σ(n),j_n,

R0(n;σ )= M

I=(i₁,...,i_n) Pos(I)⊂Pos(σ)

Cxi_n,σ(n)· · ·xi₁,σ(1).

Proof: We only show the first identity, the second one being proved in the same way.

Lemma 4.11 Let l≥1 be such thatσ(i) > σ (i+l)and ji≤ ji+l. Then,in A0(n) x_{σ (}i),j_i· · ·x_σ(i+l),j_i+l =0.

Proof of the lemma: The result is obvious when l=1. Let then l≥2 and suppose that the result holds for l−1. Two cases are to be considered.

1) σ(i+l−1) > σ(i+l). If ji+l−1≤ ji+l, one clearly has

x_σ(i),j_i· · ·x_σ(i+l),j_i+l =x_{σ (}i),j_i· · ·x_σ(i+l−1),j_i+l−1x_{σ (}i+l),j_i+l =0.

(13)

On the other hand, if ji+l−1> ji+l, we can write

x_σ(_i_),_j_i· · ·x_σ(_i₊_l_),_j_i+l =x_σ(_i_),_j_i· · ·x_σ(_i₊_l_),_j_i+lx_{σ (}_i₊_l₋₁_),_j_i+l−1

−x_σ(i),j_i· · ·x_{σ (}i+l),j_i+l−1x_σ(i+l−1),j_i+l. We have here ji ≤ ji+l−1so that the right hand side is zero, as required.

2) σ(i+l−1) < σ (i+l). Thusσ (i) > σ (i+l−1)and we just have to check the case j_i > j_i₊_l₋₁. Then, j_i₊_l₋₁< j_i₊_lso that

x_σ(i),j_i· · ·x_σ(i+l),j_i+l =x_σ(i),j_i· · ·x_σ(i+l),j_i+lx_{σ (}i+l−1),j_i+l−1

+x_σ(i),ji· · ·x_{σ (}i+l−1),j_i+lx_{σ (}i+l),j_i+l−1,

which is indeed zero by induction. 2

It follows from the lemma that L0(n;σ) = X

J=(j₁,...,j_n) Inv(σ )⊂Inv(J)

Cx_{σ (}1),j₁· · ·x_{σ (}n),j_n,

and it remains to prove that the sum is direct. Let J=(j1, . . . ,jn)∈Nⁿsuch that Inv(σ)⊂ Inv(J). Using the same argument as in the proof of Proposition 4.6 we can write

x_{σ (}1),j₁· · ·x_σ(n),j_n =e_σ⊗e^∗_J=e^σ₁₂_···_n⊗e^∗_J≡e12···n⊗(e^∗_J·T_σ−1)

=X

τ≤σ

ε(σ τ)e₁₂_···_n⊗e_J_·τ

where≤is the Bruhat order onSnand J·τ =(j_τ(1), . . . ,j_τ(n)). This last formula clearly shows that the family(x_σ(1),j1· · ·x_{σ (}n),jn)Inv(σ)⊂Inv(J)is free. 2 We can now prove that the “left cells” L₀(n;σ)form a filtration of the right comodule L₀(n)with respect to the weak order.

Proposition 4.12 Letσ ∈ Sn and let i ∈ [1,n−1] such thatσ(i) > σ (i +1). Then L0(n;σ)is strictly included into L0(n;σ σi).

Proof: The inclusion L0(n;σ )⊂L0(n;σ σi)is immediate. Thus it suffices to show that this inclusion is strict. One can easily construct an element x∈L0(n;σ σi)of the form x=

· · · x_σ(_i₊₁_),_kx_{σ (}_i_),_k· · ·Using the formalism of Section 4.3, one checks that(T_i⊗Id)·x=

−x6=0. On the other hand,(T_i⊗Id)·L₀(n;σ )=0. Thus x∈/ L₀(n;σ). 2

4.7. The diagonal subalgebra and the quantum pseudoplactic algebra

Definition 4.13 The quantum diagonal algebra1q(n)is the subalgebra of Aq(n)gener- ated by x11, . . . ,xnn.

(14)

352 KROB AND THIBON

The character theory of Aq(n)-comodules described in Section 6 will show that the noncommutative algebra1q(n)contains a subalgebra isomorphic to the algebra of ordinary symmetric polynomials, exactly as in the case of the plactic algebra.

Definition 4.14 Let A be a totally ordered alphabet. The quantum pseudoplactic algebra PPl_q(A)is the quotient ofC(q)hAiby the relations





qaab−(q+1)aba+baa=0 for a<b, qabb−(q+1)baa+bba=0 for a<b, cab−acb−bca+bac=0 for a<b<c.

The third relation is the Lie relation [[a,c],b]=0 where [x,y] is the usual commutator xy−yx. For q =1, the first two relations become [a,[a,b]]=[b,[b,a]]=0 and PPl1(A) is the universal enveloping algebra of the Lie algebra defined by these relations.

It should be noted that the classical plactic algebra is not obtained by any specialization of PPl_q(A). The motivation for the introduction of PPl_q(A)comes from the following conjecture.

Conjecture 4.15 Let A = {a1, . . . ,an}be a totally ordered alphabet of cardinality n.

For generic q,the mappingϕ: ai →xiiinduces an isomorphism between PPlq(A)and the diagonal algebra1q(n).

Our conjecture is stated for generic values of q, i.e., when q is considered as a free variable, or avoiding a discrete set inC. It is clearly not true for arbitrary complex values of q. For example, for q = 1, the diagonal algebra11(n)is an algebra of commutative polynomials. The diagonal algebra at q=0 is also particularly interesting, and its structure will be investigated in the forthcoming section.

4.8. The hypoplactic algebra

Let again A be a totally ordered alphabet. We recall that the plactic algebra on A is the C-algebra Pl(A), quotient ofChAiby the relations

½aba=baa, bba=bab for a<b, acb=cab, bca=bac for a<b<c.

These relations, which were obtained by Knuth [20], generate the equivalence relation identifying two words which have the same P-symbol under the Robinson-Schensted cor- respondence. Though Schensted had shown that the construction of the P-symbol is an associative operation on words, the monoid structure on the set of tableaux has been mostly studied by Lascoux and Sch¨utzenberger [23] under the name ‘plactic monoid’. These au- thors showed, for example, that the Littlewood-Richardson rule is essentially equivalent to the fact that plactic Schur functions, defined as sums of all tableaux with a given shape, are the basis of a commutative subalgebra of the plactic algebra. This point of view is now