Cristian Lenart

Kirill Zainoulline

On Schubert calculus in elliptic cohomology

Keywords: Schubert classes, Bott-Samelson classes, elliptic cohomology, root polynomial, Kazhdan-Lusztig basis

An important combinatorial result in equivariant cohomology and K-theory Schubert calculus is represented by the formulas of Billey and Graham-Willems for the localization of Schubert classes at torus fixed points. These formulas work uniformly in all Lie types, and are based on the concept of a root polynomial. We define formal root polynomials associated with an arbitrary formal group law (and thus a generalized cohomology theory). We use these polynomials to simplify the approach of Billey and Graham-Willems, as well as to generalize it to connective K-theory and elliptic cohomology. Another result is concerned with defining a Schubert basis in elliptic cohomology (i.e., classes independent of a reduced word), using the Kazhdan-Lusztig basis of the corresponding Hecke algebra.

Résumé. Un résultat combinatoire important dans le calcul de Schubert pour la cohomologie et la K-théorie équivariante est représenté par les formules de Billey et Graham-Willems pour la localisation des classes de Schubert aux points fixes du tore. Ces formules sont uniformes pour tous les types de Lie, et sont basés sur le concept d'un polynôme de racines. Nous définissons les polynômes formels de racines associées à une loi arbitraire de groupe formel (et donc à une théorie de cohomologie généralisée). Nous utilisons ces polynômes pour simplifier les preuves de Billey et Graham-Willems, et aussi pour généraliser leurs résultats à la K-théorie connective et la cohomologie elliptique. Un autre résultat concerne la définition d'une base de Schubert dans cohomologie elliptique (c'est à dire, des classes indépendantes d'un mot réduit), en utilisant la base de Kazhdan-Lusztig de l'algèbre de Hecke correspondant.

Introduction

Modern Schubert calculus has been mostly concerned with the cohomology and K-theory (as well as their quantum deformations) of generalized flag manifolds G/B, where G is a connected complex semisimple Lie group and B a Borel subgroup; Kac-Moody flag manifolds have also been studied, but we will restrict ourselves here to the finite case. The basic results in Schubert calculus for other cohomology theories have only been obtained recently in [CZZ12, CZZ13, CZZ14, CPZ13, GR13, HHH05, HK11, KK13]. After this main theory has been developed, the next step is to give explicit formulas, thus generalizing well-known results in cohomology and K-theory, which are usually based on combinatorial structures. This paper is a contribution in this direction; for some of the related proofs, see [START_REF] Lenart | Towards generalized cohomology Schubert calculus via formal root polynomials[END_REF].

We focus on elliptic cohomology, more precisely, on the associated hyperbolic formal group law, which we view as the first case after K-theory in terms of complexity. (The correspondence between generalized cohomology theories and formal group laws is explained below.) The main difficulty beyond K-theory is the fact that the naturally defined cohomology classes corresponding to a Schubert variety depend on its chosen Bott-Samelson desingularization, and thus on a reduced word for the given Weyl group element (which is not the case in ordinary cohomology and K-theory, where we have naturally defined Schubert classes). Thus, one problem is to express combinatorially these so-called Bott-Samelson classes.

In this paper, we extend the combinatorial formulas for localizations of Schubert classes in (torus equivariant) cohomology and K-theory, which are due to Billey [START_REF] Billey | Kostant polynomials and the cohomology ring for G/B[END_REF] (cf. also [START_REF] Andersen | Representations of quantum groups at a pth root of unity and of semisimple groups in characteristic p: independence of p[END_REF]) and Graham-Willems [START_REF] Graham | Equivariant K-theory and Schubert varieties[END_REF][START_REF] Willems | Cohomologie et K-théorie équivariantes des variétés de Bott-Samelson et des variétés de drapeaux[END_REF], respectively. These formulas are based on the concept of a root polynomial. We define formal root polynomials, which correspond to an arbitrary formal group law. We explain the connection of these polynomials to the hyperbolic solution of the Yang-Baxter equation. We then show that, in the hyperbolic case, the formal root polynomials provide an efficient way to compute the transition matrix between two natural bases of the formal Demazure algebra. As a corollary, we derive in a simpler and uniform manner (i.e., in all Lie types, and for both ordinary cohomology and K-theory) the connective K-theory version of the formulas of Billey and Graham-Willems, which seems new. We also derive a duality result in connective K-theory, as well as other related results, and state a positivity conjecture.

Another result is concerned with defining a Schubert basis in elliptic cohomology (i.e., classes independent of a reduced word), using the Kazhdan-Lusztig basis of the corresponding Hecke algebra.

Background

We briefly recall the main results in Schubert calculus for generalized cohomology theories.

Complex oriented cohomology theories

A (one dimensional, commutative) formal group law over a commutative ring R is a formal power series

F (x, y) in R[[x, y]] satisfying F (x, y) = F (y, x) , F (x, 0) = x , F (x, F (y, z)) = F (F (x, y), z) . (1)
Let E * (•) be a complex oriented cohomology theory with base ring R = E * (pt). By [START_REF] Quillen | Elementary proofs of some results of cobordism theory using Steenrod operations[END_REF], this is equipped with a formal group law F (x, y) over R, which expresses the corresponding first Chern class, denoted c(•), of a tensor product of two line bundles L 1 and L 2 on a space X in terms of c(L 1 ) and c(L 2 ):

c(L 1 ⊗ L 2 ) = F (c(L 1 ), c(L 2 )) .
(2)

The reciprocal of Quillen's statement is false: there are formal group laws which do not come from complex oriented cohomology theories. However, if one translates and extends the axiomatics of oriented theories into the algebraic context, then to any formal group law one can associate the respective algebraic oriented cohomology theory [START_REF] Levine | Algebraic Cobordism[END_REF]. In this paper we work in the more general algebraic setting, so E * (•) stands for the respective algebraic oriented cohomology.

We refer to the (finite type) generalized flag variety G/B, and we let T be the corresponding maximal torus. We use freely the corresponding root system terminology. As usual, we denote the set of roots by Φ, the subsets of positive and negative roots by Φ + and Φ -, the simple roots and corresponding simple reflections by α i and s i (for i = 1, . . . , n, where n is the rank of the root system), the lattice of integral weights by Λ, the Weyl group by W , its longest element by w • , and its strong Bruhat order by ≤. For each w ∈ W , we have the corresponding Schubert variety X(w) := BwB. Given an arbitrary weight λ, let L λ be the corresponding line bundle over G/B, that is, L λ := G × B C -λ , where B acts on G by right multiplication, and the B-action on C -λ = C corresponds to the character determined by -λ.

We now consider the respective T -equivariant cohomology E * T (•) of spaces with a T -action, see e.g. [START_REF] Harada | Computation of generalized equivariant cohomologies of Kac-Moody flag varieties[END_REF]. Its base ring E * T (pt) can be identified (after completion) with the formal group algebra The universal formal group law corresponds to complex cobordism. In this paper we focus on elliptic cohomology, denoted Ell * (•), whose corresponding formal group law is that of an elliptic curve [START_REF]Elliptic cohomology. Geometry, applications, and higher chromatic analogues[END_REF]. More precisely, for an elliptic curve given in Tate coordinates by (1 -µ 1 t -µ 2 t 2 )s = t 3 , it is known that the respective formal group law is the hyperbolic one

S := R[[y λ ]] λ∈Λ /(y 0 , y λ+ν -F (y λ , y ν )) (3)
F h (x, y) = x + y -µ 1 xy 1 + µ 2 xy , defined over R = Z[µ 1 , µ 2 ] . (4)
The hyperbolic formal group law is, in fact, a very natural one from a topological perspective. It implicitly appeared in Hirzebruch's celebrated book [START_REF] Hirzebruch | Topological methods in algebraic geometry[END_REF] devoted to the proof of the Riemann-Roch theorem (cf. his earlier work). Indeed, the book is centered on the notion of a "(2-parameter) virtual generalized Todd genus". It turns out that the associated formal group law (via the one-to-one correspondence between genera and formal group laws) is precisely the one in (4).

Let us also mention some important special cases. In the trivial case µ 1 = µ 2 = 0, F h (x, y) = F a (x, y) is the additive group law, which corresponds to ordinary cohomology H * (•). If µ 2 = 0, and µ 1 = 1, resp. µ 1 is not specialized, then F h (x, y) = F m (x, y) is the corresponding version of the multiplicative formal group law, associated to K-theory, and connective K-theory, respectively.

Schubert and Bott-Samelson classes

Given a Weyl group element w, consider a reduced word I w = (i 1 , . . . , i l ) for it, so w = s i1 . . . s i l . There is a Bott-Samelson resolution of the corresponding Schubert variety X(w), which we denote by γ Iw : Γ Iw → X(w) → G/B. This determines a so-called Bott-Samelson class in E * T (G/B) via the corresponding pushforward map, namely (γ Iw ) ! (1). Here we let

ζ Iw := (γ I -1 w ) ! (1) , (5)
where I -1 w := (i l , . . . , i 1 ) is a reduced word for w -1 ; we use I w -1 , rather than I w , in order to simplify the correspondence with the setup in [START_REF] Billey | Kostant polynomials and the cohomology ring for G/B[END_REF][START_REF] Willems | Cohomologie et K-théorie équivariantes des variétés de Bott-Samelson et des variétés de drapeaux[END_REF], which is used in Sections 4 and 5. Note that ζ ∅ is the class of a point (where ∅ denotes the reduced word for the identity).

It is well-known that the Bott-Samelson classes are independent of the corresponding reduced words only for cohomology and K-theories (we can say that connective K-theory is the "last" case when this happens). In these cases, the Bott-Samelson classes are the Schubert classes, and they form bases of H * T (G/B) and K T (G/B) over the corresponding formal group algebra S, as w ranges over W . (More precisely, the Schubert classes in cohomology are the Poincaré duals to the fundamental classes of Schubert varieties, whereas in K-theory they are the classes of structure sheaves of Schubert varieties.) More generally, an important result in generalized cohomology Schubert calculus says that, by fixing a reduced word I w for each w, the Bott-Samelson classes {ζ Iw : w ∈ W } form an S-basis of E * T (G/B).

The formal Demazure algebra

Following [HMSZ13, §6] and [CZZ12, §3], consider the localization Q of S along all x α , for α ∈ Φ (note the change of notation, from y λ to x λ , cf. the convention at the beginning of Section 3.1), and define the twisted group algebra Q W to be the smash product

Q#R[W ], see [HMSZ13, Def. 6.1]. More precisely, as an R-module, Q W is Q ⊗ R R[W ],
while the multiplication is given by

qδ w • q δ w = q(wq )δ ww , q, q ∈ Q, w, w ∈ W. (6)
We denote δ i := δ si , x ±i := x ±αi , and x ±i±j := x ±αi±αj , for i, j ∈ {1, . . . , n}; similarly for the y variables (to be used later). Following [HMSZ13, Def. 6.2] and [START_REF] Calmès | Push-pull operators on the formal affine Demazure algebra and its dual[END_REF], we define in Q W :

X i := 1 x i δ i - 1 x i = 1 x i (δ i -1), Y i := X i + κ i = 1 x -i + 1 x i δ i = (1 + δ i ) 1 x -i , (7)
where

κ i := 1 x-i + 1 xi .
We call X i and Y i the Demazure and the push-pull element, respectively. The R-subalgebra D F of Q W generated by the elements of S and the elements {X i }, or {Y i }, is called the formal affine Demazure algebra. Its dual D F serves as an integral model for E * T (G/B) [START_REF] Calmès | Equivariant oriented cohomology of flag varieties[END_REF]. Relations in the algebra D F were given in [HMSZ13, Thm. 6.14] and [HMSZ13, Prop. 8.10]. In the case of the hyperbolic formal group law, these relations are: (a) For all i, we have

Y 2 i = µ 1 Y i . ( 8
) (b) If α i , α ∨ j = 0, so that m ij = 2
, where m ij be the order of s i s j in W , then

Y i Y j = Y j Y i . ( 9
) (c) If α i , α ∨ j = α j , α ∨ i = -1, so that m ij = 3, then Y i Y j Y i -Y j Y i Y j = µ 2 (Y j -Y i ) . (10)
There are also more involved relations if m ij = 4 or m ij = 6, given in [HMSZ13, Prop. 6.8]. These relations as well as (10) are called twisted braid relations. In the case of ordinary cohomology and Ktheory, the twisted braid relations are the usual braid relations (since µ 2 = 0). Given a reduced word I w = (i 1 , . . . , i l ) for w ∈ W , define X Iw := X i1 . . . X i l and Y Iw := Y i1 . . . Y i l . By [START_REF] Calmès | Push-pull operators on the formal affine Demazure algebra and its dual[END_REF], if we fix a reduced word I w for each w ∈ W , then {X Iw : w ∈ W } and {Y Iw : w ∈ W } are bases of the free left Q-module Q W . Note that, in cohomology and K-theory, X Iw and Y Iw do not depend on the choice of the reduced word I w , so we can simply write X w and Y w .

A fundamental result in generalized cohomology Schubert calculus states that the Bott-Samelson classes ζ Iw , for I w = (i 1 , . . . , i l ), can be calculated recursively as follows (via the usual action of D F on the Borel model of E * T (G/B), see e.g. [START_REF] Ganter | Generalized Schubert calculus[END_REF]):

ζ Iw = Y i l . . . Y i1 ζ ∅ . (11)
By analogy with (11), we define the following classes:

ζ Iw := X i l . . . X i1 ζ ∅ , (12)
where ζ ∅ = ζ ∅ is the class of a point, and I w = (i 1 , . . . , i l ) is a reduced word for w, as above. Clearly, in ordinary cohomology we have ζ w = ζ w , because X i = Y i (and there is no dependence on I w ). In K-theory we have X i = Y i -1; for the geometric significance of the corresponding classes ζ w , we refer to Remark 4.7.

The GKM model of equivariant cohomology

In the GKM model, see e.g. [GKM98, GR13, HHH05, CPZ13], we embed E * T (G/B) into w∈W S, with pointwise multiplication. This comes from the embedding

i * : E * T (G/B) → w∈W E * T (pt) w∈W S , where (13)
i * := w∈W i * w , and i w : pt → G/B , with pt → w -1 . ( 14
)
There is a characterization of the image of this embedding, see e.g. [START_REF] Ganter | Generalized Schubert calculus[END_REF]. We denote the elements of w∈W S by (f w ) w∈W ; alternatively, we view them as functions f : W → S.

Formal root polynomials and their properties

In this section we define formal root polynomials by extending the definitions in [Bi99, Gr02, Wil04], and begin their study. The setup is the one above, so it corresponds to an arbitrary formal group law.

Definition and basic facts

Consider the ring Q W [[Λ]] F = S ⊗ R Q W ,
where the elements of S on the left (denoted by y's) commute with the elements of Q W . The formal root polynomials are elements of this ring which depend on a reduced word I w = (i 1 , . . . , i l ) for a Weyl group element w. In fact, we will define two formal root polynomials, corresponding to the Demazure and push-pull operators X i and Y i in (7). It is well-known that I w induces a so-called reflection order on the roots in Φ + ∩ wΦ -, namely

Φ + ∩ wΦ -= {α i1 , s i1 α i2 , . . . , s i1 . . . s i l-1 α i l } . ( 15
) Definition 3.1. The formal Y -root polynomial corresponding to I w is R Y Iw := l k=1 h Y i k (s i1 . . . s i k-1 α i k ), where h Y i (λ) := 1 -y λ Y i .
Similarly, we define the formal X-root polynomial by replacing h Y i (λ) with h X i (λ) := 1 + y -λ X i .

Based on Propositions 3.5, 3.6, 3.7, we deduce the following result.

Theorem 3.8. The root polynomial R Y Iw does not depend on the choice of I w if the underlying formal group law F (x, y) is the hyperbolic one; so we can write R Y w instead. The reciprocal holds if the corresponding root system contains a pair of simple roots α i , α j with m ij = 3. Remarks 3.9. (1) The first part of Theorem 3.8 appears as [Bi99, Theorem 2], resp. [Wil04, Theorem 5.2], in the case of the additive formal group law, resp. the multiplicative one.

(2) An alternative proof of the first part of Theorem 3.8, which is uniform for all Lie types, is given in Section 4.1.

Applications of formal root polynomials in the hyperbolic case

The coefficients of formal root polynomials

In this section we present our main application of formal root polynomials in the hyperbolic case, which is continued in the next section.

We start with an arbitrary formal group law F (x, y). Consider the root polynomials R Y Iw and R X Iw

as elements of Q W [[Λ]] F .
Recall that, after we fix a reduced word I v for each v ∈ W , the elements

{Y Iv : v ∈ W } and {X Iv : v ∈ W } form bases of the left S ⊗ R Q-module Q W [[Λ]] F . Definition 4.1. Let K Y (I v , I w ), resp. K X (I v , I w ), denote the coefficient of Y Iv in the expansion of R Y Iw , resp. the coefficient of X Iv in the expansion of R X Iw , i.e. R Y Iw = v≤w K Y (I v , I w ) Y Iv , R X Iw = v≤w K X (I v , I w ) X Iv . (17)
By analogy with the setup of [START_REF] Billey | Kostant polynomials and the cohomology ring for G/B[END_REF], we call K Y (I v , I w ) and K X (I v , I w ) (normalized) formal Kostant polynomials.

From now on, we assume that we are in the hyperbolic case, so by Theorem 3.8 we know that the root polynomials do not depend on the choice of a reduced word. However, we will not use this knowledge in this section, so we will continue to use the notation R Y Iw and R X Iw . Observe that the free left Q-module Q W also has a basis {δ w : w ∈ W }. Consider the following expansions, cf. [CZZ13, Lemmas 3.1 and 3.2]:

δ w = v≤w b Y w,Iv Y Iv , δ w = v≤w b X w,Iv X Iv (18)
for some coefficients b Y w,Iv and b X w,Iv in S (in x's). By applying the evaluation map ev to (17) and by using Lemma 3.3, we derive the following result. Here we use the sign change involution * on the formal group algebra S, given by y λ → y -λ (not to be confused with ev).

Theorem 4.2. In the hyperbolic case, we have in S:

b Y w,Iv = * (θ w K Y (I v , I w )) , b X w,Iv = * (K X (I v , I w )) .
In particular, K Y (I v , I w ) (resp. K X (I v , I w )), and hence R Y Iw (resp. R X Iw ), do not depend on the choice of I w , so we can use the notation K Y (I v , w) and R Y w (resp. K X (I v , w) and R X w ) in this case.

Remarks 4.3. (1) The formula in Theorem 4.2 relates the coefficients of the Y -root polynomial with the entries of the transformation matrix between two natural bases of the twisted formal group algebra; similarly for the X-root polynomial. This provides an efficient way to compute these matrices, see Example 4.4. For cohomology and K-theory, these matrices feature prominently in the work of Kostant-Kumar [KK90], as they encode information about the singularities of Schubert varieties; see [BL00, Chapter 7].

(2) Theorem 4.2 contains an alternative, type-independent proof to the first part of Theorem 3.8. Example 4.4. Consider the root system A 2 and the Lorentz formal group law, i.e., (4) with µ 1 = 0. For each permutation v = w • in S 3 we have a unique reduced word, and choose I w• = (1, 2, 1). Based on Example 3.2, while also noting that here κ i = 0, θ w = 1 (cf. Remark 3.4), and y -α = -y α , we have

δ w• = y 1 y 1+2 y 2 Y 1 Y 2 Y 1 + y 1 y 1+2 Y 1 Y 2 + y 2 y 1+2 Y 2 Y 1 + (y 1 + y 2 )Y 1 + y 1+2 Y 2 + 1 .
If we choose I w• = (2, 1, 2) instead, we need to adjust the above expansion by rewriting 10), and then collecting terms. Alternatively, we can avoid using the twisted braid relation by using the expression for R ) and going up in length. Corollary 4.6. For any formal group law, the coefficients p Iw Iu,Iv do not depend on the choice of I w , so we can write p w Iu,Iv = p Iw Iu,Iv . Hence, in the hyperbolic case, via Theorem 4.2, we are able to compute p w Iu,Iv in terms of the coefficients K Y (I v , w) of Y -root polynomials. This gives another application of these polynomials. We have completely similar results for the multiplication of the basis elements {X * Iw }.

Y 1 Y 2 Y 1 as Y 2 Y 1 Y 2 + µ 2 (Y 2 -Y 1 ) via (
Y (2,1,2) in Example 3.2. Note that, although R Y (1,2,1) = R Y (2,

Localization formulas in connective K-theory

We work in the setup of connective K-theory, whose formal group law is obtained by setting t := µ 1 and µ 2 = 0 in (4), cf. Section 2.1. Recall from Section 2.3 that the corresponding operators Y i and X i satisfy Y 2 i = tY i , X 2 i = -tX i , and the usual braid relations. We define the functions

ψ v := ( ζ vw• ) • , ξ v := (ζ vw• ) • , (19)
where, given a function f : W → S, we define f • : W → S by f • (w) := f (ww • ). The duality property, which holds for both cohomology and K-theory, says that there is a non-degenerate pairing

p ! (ζ v • * ψ w ) = p ! (Y v -1 ζ ∅ • X (w•v) -1 ( * ψ w• )) = δ v,w , (20)
where p ! is the degree map for cohomology and the Euler characteristic for K-theory.

The following formulas generalize the ones of Billey [START_REF] Billey | Kostant polynomials and the cohomology ring for G/B[END_REF], in cohomology, and Graham-Willems [START_REF] Graham | Equivariant K-theory and Schubert varieties[END_REF][START_REF] Willems | Cohomologie et K-théorie équivariantes des variétés de Bott-Samelson et des variétés de drapeaux[END_REF], in ordinary K-theory. They are proved by induction of (v). To state our result, consider a reduced word I w = (i 1 , . . . , i l ) for w, and recall the corresponding reflection order (15) on Φ + ∩ wΦ -, namely (β 1 , . . . , β l ) with β j := s i1 . . . s ij-1 α ij .

Theorem 4.8. In connective K-theory, we have ψ v (w) = θ w K Y (v, w). More explicitly, we have

ψ v (w) = θ w 1≤j1<...<j k ≤l (-1) k t k-(v) y βj 1 . . . y βj k , (21)
where (v) ≤ k ≤ l, and the summation ranges over the integer sequences 1 ≤ j 1 < . . . < j k ≤ l for which the corresponding subword (p 1 , . . . , p

k ) = (i j1 , . . . , i j k ) of I w is subject to Y p1 . . . Y p k = t k-(v) Y v . Similar results hold for ξ v .

The results of Billey and Graham-Willems revisited; duality in connective K-theory

The following result is an immediate consequence of Theorem 4.2 and the duality result for an arbitrary cohomology theory in [CZZ13, Theorem 12.4].

Theorem 4.9. The connective K-theory analogue of the duality (20) is equivalent to both formulas, for ψ v and ξ v , in Theorem 4.8.

Let us comment on this result. Based on the duality result (20) in cohomology and K-theory, we have a new proof of Theorem 4.8 in these cases, and hence of the formulas of Billey and Graham-Willems. This proof has the advantage of being very short, completely transparent, and uniform (in all Lie types and for both cohomology and K-theory). On the other hand, by reversing our reasoning, in connective K-theory we can rely on the proof of Theorem 4.8, and derive the analogue of the duality (20), which seems new.

Bott-Samelson classes in the hyperbolic case

In the previous section, we have considered two families of elements in E * T (G/B), namely the Bott-Samelson classes ζ Iv and X * Iv , both of which are viewed as functions from W to S (recall that X * Iv are evaluated at δ w , cf. the expansion (18)). It is not hard to see (by the duality argument in Section 4.3) that these families essentially concide in K-theory, but not beyond that, due to the dependence on the reduced word I v . Furthemore, in Theorem 4.2 we have been able to express X * Iv (δ w ) in the hyperbolic case based on formal root polynomials, thus generalizing the results of Billey and Willems in ordinary cohomology and K-theory. We now refer to the calculation of ζ Iv in the hyperbolic case, which turns out to be a above isomorphism. We now define our Schubert classes, which we call Kazhdan-Lusztig (KL-) Schubert classes. Definition 6.1. Consider the element S w in Ell * T (G/B) given by (t + t -1 ) -(w) Γ w -1 (ζ ∅ ) under the action of D F on the GKM model of Ell * T (G/B). Theorem 6.2. The KL-Schubert classes {S w : w ∈ W } form a basis of Ell * T (G/B). In the limit t → 0, the class S w becomes the Bott-Samelson class ζ w in K-theory, which coincides with the corresponding Schubert class.

We conjecture the following natural property for the KL-Schubert classes S w . Conjecture 6.3. If the Schubert variety X(w) is smooth, then the class [X(w)] in (22) coincides with S w .

We tested this conjecture on the computer. Moreover, we proved the special cases below. Theorem 6.4. Conjecture 6.3 is true in the following cases (which all correspond to non-singular Schubert varieties):

(1) in all types for w which is a product of distinct simple reflections;

(2) in all classical types A n-1 , B n , C n , D n , for w -1 , where w is a highest coset representative for W n /W n-1 (in particular, for w = w • , the longest element, we have S w• = 1).

Remark 6.5. Case (1) of Theorem 6.4 is easy, because the formal group law is not involved in the calculation of the respective classes. However, this no longer happens in case (2), which is therefore highly non-trivial.

of [ CPZ13 ,

 CPZ13 Def. 2.4]. The Weyl group acts on S by w(y λ ) := y wλ .

  Finally, note that the algebras Q W and D F act on the GKM model of E * T (G/B), cf. [GR13, Eq. (3.19), (3.20)]. Using this action, we can calculate the classes ζ Iw and ζ Iw recursively via (11) and (12), as the class ζ ∅ = ζ ∅ is known, see [GR13, Eq. (4.4)].

  1,2) , the expressions for them given in Example 3.2 are different. Let us now turn to a generalization of the cohomology and K-theory Schubert structure constants. Given a choice of reduced words I w , let Y * Iw in the dual Demazure algebra D F be the usual dual of Y Iw , see Section 2.3; these are not the Bott-Samelson classes in general (see Section 5). Let Y * Iu • Y * Iv = w≥u,v p Iw Iu,Iv Y * Iw be the expansion of the given product into the basis {Y * Iw } of D F . We follow the approach in Billey's paper [Bi99] related to the cohomology structure constants. We start by generalizing [Bi99, Lemma 5.3]. Proposition 4.5. The coefficients p Iw Iu,Iv can be computed recursively by b Y w,It , starting with w = u (for v ≤ u, p Iu Iu,Iv = b Y u,Iv

Remark 4. 7 .

 7 Consider ordinary K-theory, so t = 1. The evaluation ξ v (w) can be interpreted geometrically as i * ww• ([O vw• ]), where O u is the structure sheaf of the Schubert variety indexed by u (see Section 2.4). The Poincaré dual of the K-theory class ζ v = [O v ] is the class of the ideal sheaf of the Schubert variety indexed by v, which under i * w is mapped to * ψ v (w), see e.g. [KK90], [GK08, Prop. 2.1].

† Partially supported by the NSF grants DMS-1101264 and DMS-1362627; the hospitality and support of the Max-Planck-Institut für Mathematik in Bonn, where part of this work was carried out, are also gratefully acknowledged. ‡ Partially supported by the NSERC Discovery grant 385795-2010 and the Early Researcher Award (Ontario).

1365-8050

Example 3.2. For type A 2 and w = s i s j s i , I w = (i, j, i), we obtain (cf. the notation in Section 2.3)

Consider a ring homomorphism ev :

Furthermore, θ Iw does not depend on the choice of the reduced word I w for w, so we write θ w = θ Iw .

We will call θ w the normalizing parameter. Remark 3.4. In the ordinary cohomology case, the formal root polynomials coincide with those Billey [Bi99, Definition 2], and we have θ(λ) = 1. In the K-theory case, the Y -root polynomials coincide with those of Willems [Wil04, Section 5], and we have θ w = e ρ-wρ , where ρ = 1 2 α∈Φ + α, as usual.

Independence of choices of reduced words

We now provide necessary and sufficient conditions for the root polynomials R Y Iw and R X Iw to be independent of a choice of I w , hence generalizing the respective results of Billey [START_REF] Billey | Kostant polynomials and the cohomology ring for G/B[END_REF] and Willems [START_REF] Willems | Cohomologie et K-théorie équivariantes des variétés de Bott-Samelson et des variétés de drapeaux[END_REF]. For simplicity, we refer here only to the Y -root polynomial, and let

Proposition 3.6. Consider a root system containing a pair of simple roots α i , α j with m ij = 3, which we fix. Also assume that 2 is not a zero divisor in the coefficient ring R. Then the following are equivalent.

(a) The underlying formal group law is the hyperbolic one (4).

for all λ, ν ∈ Λ. We say that h i , h j satisfy the (type A) Yang-Baxter relation for all weights.

(c) We have

We say that h i , h j satisfy the (type A) Yang-Baxter relation for the corresponding simple roots.

Now recall from [START_REF] Billey | Kostant polynomials and the cohomology ring for G/B[END_REF][START_REF] Willems | Cohomologie et K-théorie équivariantes des variétés de Bott-Samelson et des variétés de drapeaux[END_REF] the Yang-Baxter relations of types B and G.

Proposition 3.7. Consider a root system containing a pair of simple roots α i , α j with m ij = 4 or m ij = 6, which we fix. Also assume that the underlying formal group law is the hyperbolic one. Then h i and h j satisfy the (type B, resp. type G) Yang-Baxter relation for all weights, cf. (16).

considerably harder problem. For simplicity, we denote the parameters in (4) by t := µ 1 and u := -µ 2 , so the underlying ring R is Z[t, u].

Based on the analogy with (21), as well as experimental evidence, we formulate the following positivity conjecture. To state it, consider v ≤ w, and let Φ + ∩ wΦ -= {β 1 , . . . , β l }; also let z i = y -βi .

(

) is a sum with positive coefficients of terms of the form

If the conjecture is true, it would be interesting to find the geometric reason for positivity.

A Schubert basis via the Kazhdan-Lusztig basis

An important open problem in Schubert calculus beyond K-theory is defining a Schubert basis, i.e., classes which are independent of a reduced word for the indexing Weyl group elements. The standard topological approach works if the Schubert variety X(w) is smooth, and the corresponding class [X(w)] has a simple formula; namely, by [START_REF] Ganter | Generalized Schubert calculus[END_REF][Eq. (5.3)], cf. also [BL00, Theorem 7.2.1], in the GKM model of E * T (G/B) (discussed in Section 2.4), we have:

for v ≤ w in the Weyl group W ; otherwise [X(w)] v = 0.

In general, an axiomatic approach (called "combinatorial forcing") was suggested in [START_REF] Ganter | Generalized Schubert calculus[END_REF]. We propose a different approach in equivariant elliptic cohomology, which uses the Kazhdan-Lusztig basis of the corresponding Hecke algebra, and provide support for it.

Instead of the usual generators T i of the Hecke algebra H of the Weyl group W , we use τ i := tT i , where t = q -1/2 . In (4) we set µ 1 = 1 and µ 2 = -(t + t -1 ) -2 = -u, so we let the base ring R be Z

R is isomorphic to the R-subalgebra of the corresponding formal Demazure algebra D F (see Section 2.3) generated by the elements Y i only; the isomorphism is given by τ i → (t + t -1 )Y i -t.

Consider the Kazhdan-Lusztig basis {γ w : w ∈ W } of H, given by

where π vw (t) are the Kazhdan-Lusztig polynomials (in terms of the classical notation, we have P vw (t) = t -( (w)-(v)-1) π vw (t)). For w ∈ W , denote by Γ w the element of D F which corresponds to γ w via the


Olya Mandelshtam
email: olya@math.berkeley.edu

Tableaux combinatorics for two-species PASEP probabilities

Keywords: PASEP, multispecies, tableaux

The goal of this paper is to provide a combinatorial expression for the steady state probabilities of the twospecies PASEP. In this model, there are two species of particles, one "heavy" and one "light", on a one-dimensional finite lattice with open boundaries. Both particles can hop into adjacent holes to the right and left at rates 1 and q. Moreover, when the heavy and light particles are adjacent to each other, they can switch places as if the light particle were a hole. Additionally, the heavy particle can hop in and out at the boundary of the lattice. Our first result is a combinatorial interpretation for the stationary distribution at q = 0 in terms of certain multi-Catalan tableaux. We provide an explicit determinantal formula for the steady state probabilities, as well as some general enumerative results for this case. We also describe a Markov process on these tableaux that projects to the two-species PASEP, and hence directly explains the connection between the two. Finally, we extend our formula for the stationary distribution to the q = 1 case, using certain two-species alternative tableaux.

Résumé. Le but de ce document est de fournir une expression combinatoire décrivant les probabilités de l'état d'équilibre de PASEP à deux espèces. Dans ce modèle, il existe deux espèces de particules, une "lourde" et une "légère", disposées sur un réseau fini unidimensionnel. Les deux particules peuvent sauter dans les trous adjacents à droite et à gauche, avec des probabilités proportionnelles à 1 et q. Par ailleurs, lorsque les particules lourdes et légères sont à côté l'une de l'autre, elles peuvent changer de place, comme si la particule légère était un trou. En outre, la particule lourde peut sauter dans et hors de la frontière du réseau. Notre premier résultat est une interprétation combinatoire de la distribution stationnaire dans le cas q = 0, en termes de certains tableaux "multi-Catalan". Nous proposons une formule explicite déterminantale pour les probabilités stationnaires, ainsi que plusieurs résultats énumératifs généraux pour ce cas. Nous décrivons aussi un processus de Markov sur ces tableaux, qui se projette sur le PASEP à deux espèces, et qui fournit donc directement une connexion entre les deux. Enfin, nous exprimons notre formule pour la distribution stationnaire dans le cas q = 1, en utilisant certains tableaux alternatifs de deux espèces.

Introduction

The Partially Asymmetric Simple Exclusion Process (PASEP) is a well-studied model that describes the dynamics of particles hopping on a finite one-dimensional lattice on n sites with open boundaries, with the rule that at most one particle hops at a time. Figure 1 shows the parameters of this process, with the Greek letters denoting the rates of the hopping particles. Processes of this flavor have been studied in many contexts, in particular for their connections to some very nice combinatorics. For instance, see [START_REF] Corteel | Tableaux combinatorics for the asymmetric exclusion process[END_REF] and the references therein. In this work we consider the two-species PASEP with "heavy" and "light" particles, which we call types 2 and 1 respectively. Both types of particles can hop to the right or left into an adjacent hole with rates 1 and q. Furthermore, heavy particles can enter from the left and exit on the right of the lattice, and they can treat the light particles as holes and swap places with them also at rates 1 and q. Since the light particles cannot enter or exit, their number stays fixed. In particular, when we fix the number of type 1 particles to be zero, we recover the original PASEP. The two-species process was studied by Uchiyama in [START_REF] Uchiyama | Two-Species Asymmetric Simple Exclusion Process with Open Boundaries[END_REF], and a Matrix Ansatz solution and corresponding matrices gave exact expressions for the steady state distribution of the system.

More formally, the two-species PASEP is a Markov chain, whose states are words of length n in the letters {D, E, A}, where D and A represent the particles of types 2 and 1, and E represents a hole. We also use the following notation for a state: locations are labeled 1 through n, and τ i ∈ {0, 1} and σ i ∈ {0, 1} are the particle indicators for particles 2 and 1 respectively, with the pair (τ, σ) representing a state. For example, the state AEDDA is represented by (τ, σ) = ((0, 0, 1, 1, 0), (1, 0, 0, 0, 1)). We write Prob((τ, σ)) or equivalently Prob(X) for X a word in {D, E, A} * to describe the steady state probability of state X.

Figure 2 shows the parameters of the two-species process. More precisely, the transitions in the Markov chain are the following, with X and Y arbitrary words in {D, E, A} * .

XAEY 1 q XEAY XDEY 1 q XEDY XDAY 1 q XADY EX α DX XD β XE
where by X u Y we mean that the transition from X to Y has probability u n+1 , n being the length of X (and also Y ). Due to (2.9) of [START_REF] Uchiyama | Two-Species Asymmetric Simple Exclusion Process with Open Boundaries[END_REF], the following Matrix Ansatz solution holds for the two-species PASEP: Theorem 1.1 (Uchiyama, 2008) Let (τ, σ) represent a state of the two-species PASEP of length n with r particles of type 1. Suppose there are matrices D,E, and A and vectors w| and |v which satisfy the following conditions

1 q 1 q 1 q β α
DE = D+E+qED, DA = A+qAD, AE = A+qEA, w|E = 1 α w|, D|v = 1 β |v then Prob((τ, σ)) = 1 Z n,r w| n i=1 τ i D + σ i A + (1 -τ i )(1 -σ i )E|v
where Z n,r is the coefficient of y r in w|(D

+ yA + E) n |v .
This result generalizes a previous Matrix Ansatz solution for the regular PASEP of Derrida et. al. in [START_REF] Derrida | Exact solution of a 1D asymmetric exclusion model using a matrix formulation[END_REF].

In his paper, Uchiyama provides matrices that satisfy the conditions of Theorem 1.1. These matrices contain terms that are neither positive or rational, but the matrix product yields steady state probabilities in the form of polynomials in α, β, and q with positive integer coefficients. Therefore we would hope for a combinatorial interpretation of these probabilities, with results akin to those of Corteel and Williams [START_REF] Corteel | Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials[END_REF] for the original PASEP. Such results could yield explicit general formulas for both the desired probabilities and the partition function. A combinatorial solution to the two-species problem could furthermore lead to a solution for a more general process, which would also be a stronger result than the one of [START_REF] Uchiyama | Two-Species Asymmetric Simple Exclusion Process with Open Boundaries[END_REF].

The goal of this paper is to provide some combinatorial solutions to this two-species problem for some special cases. In Section 2 of this paper, we describe certain tableaux which we call multi-Catalan tableaux that give an interpretation for the steady state distributions of the two-species PASEP at q = 0. In Section 3 we provide some enumerative results for the multi-Catalan tableaux. In Section 4 we describe a Markov process on the multi-Catalan tableaux that projects to the two-species PASEP at q = 0, and which gives another proof of our main result in Section 2. Finally, in Section 5 we define some more general multi-Catalan tableaux that give an interpretation for the steady state distributions of the two-species PASEP at q = 1.

Acknowledgement. I would like to thank Sylvie Corteel and Lauren Williams for suggesting this problem to me, and for their invaluable advice and support. The hospitality of LIAFA where this research was done, and the Chateaubriand Fellowship awarded by the Embassy of France in the United States that supported this stay in Paris are also gratefully acknowledged.

Multi-Catalan tableaux

The Multi-Catalan tableaux are inspired by the well-known "alternative tableaux" whose weight-generating functions provide the steady state probabilities for the states of the regular PASEP.

Definition 2.1 A multi-Catalan tableau of size n is a filling of a Young diagram of shape {n, n-1, . . . , 1} with the symbols α, β, and x as follows:

1. Every box on the diagonal must contain an α, β, or x.

2. A box that sees an α to its right and a β below must contain an α or β.

3.

A box that sees an α to its right and an x below must contain a β.

4.

A box that sees an x to its right and a β below must contain an α.

Every other box must be empty.

In the definition above, when we refer to the symbol that a box "sees" to its right or below, we mean the first symbol encountered in the same row or column, respectively. For example, in the first tableau of Figure 3, x is the first symbol that the β in the top row sees below it. Finally, note that Rule 5 implies that all boxes in the same row and left of a β must be empty, and also that all boxes in the same column and above an α must be empty.

Definition 2.2

The weight wt(T ) of a multi-Catalan tableau T the product of the α's and β's it contains.

Definition 2.3

The type of the tableau T is the word in {D, E, A} * that is read off from the diagonal from top to bottom, by assigning a D to α, an E to β, and an A to x.

Theorem 2.1 Consider the two-species PASEP on a lattice of n sites. Let X be a state described by a word in {D, E, A} n . Then the steady state probability of state X is

Prob(X) = 1 Z 0 n,r T wt(T ),
where the sum is over all multi-Catalan tableaux T such that type(T ) = X, and where Z 0 n,r = T wt(T ) for T ranging over multi-Catalan tableaux of size n whose type has exactly r A's. We show as an example all valid tableaux and their weights for the word DEEAE in Figure 3. Theorem 2.1 implies that

Prob(DEAEE) = 1 Z 0 5,1 α 4 β 4 + α 3 β 4 + α 2 β 4 .
Definition 2.4 A D-row is a row whose right-most box contains an α, and an A-row is one whose rightmost box contains an x. An E-column is a column whose bottom-most box contains a β, and an A-column is one whose bottom-most box contains an x. Then a DE box is one that lies in a D row and an E column, (and correspondingly for DA, AE, and AA boxes).

Note that we can ignore the rows with right-most box containing a β or columns with bottom-most box containing an α because they are automatically required to be empty according to Definition 2.1.

To connect back to the two-species TASEP, let a state of the TASEP be described by a word X in {D, E, A} n . Then we fill a Young diagram of shape {n, n -1, . . . , 1} as follows: from top to bottom, we fill the diagonal with symbols α, β, and x by reading the word X from left to right, and placing an α for a D, a β for an E, and an x for an A. Then any valid filling of the rest of the shape will result in a multi-Catalan tableau of type X.

Condensed multi-Catalan tableaux

We provide a condensed version of the characterization of the multi-Catalan tableaux, which offers a more natural proof of our results.

In Figure 4, we demonstrate by example the conversion from a staircase multi-Catalan tableau to a condensed multi-Catalan tableau. Specifically, we begin by drawing a lattice path with steps south and west by reading the diagonal of the staircase tableau from top to bottom. For an α, we draw a step south and label it with a D, for a β we draw a step west and label it with an E, and for an x we draw a pair of steps west and south and label them both with an A. The shape obtained will be the same as if we were to remove the diagonal from the staircase, and then collapse all the DE, DA, AE, and AA boxes. In the resulting tableau, a D-row now ends with an edge that has the label D, an A-row ends with an edge with the label A, and the E-and A-columns are analogous.

In general, to obtain a partition from a word X in {D, E, A} * , we apply the definition below.

Definition 2.5 The partition λ(X) associated to a word X is obtained by reading X from left to right, and drawing a step south for D, a step west for E, and a pair of steps west then south for A. This path with south and west steps is declared to be the southeast border of a Young diagram of shape λ(X). Since the staircase version of the multi-Catalan tableaux is in simple bijection with the condensed version, we will call them both multi-Catalan tableaux, and refer to them interchangeably.

We now give a proof of Theorem 2.1.

Proof (Theorem 2.1): The Matrix Ansatz of Theorem 1.1 implies that the steady state probabilities for the two-species PASEP satisfy certain recurrences (that in turn determine all probabilities). The strategy of our proof is to show that the weight generating function for multi-Catalan tableaux of fixed type satisfies the same recurrences.

We define a corner of the tableau to be a box that is both the right-most box of some row and the bottommost box of some column. We also define weight for a word X in {D, E, A} * by weight(X)

= T wt(T )
where the sum is over all multi-Catalan tableaux T such that type(T ) = X.

For a tableau of size n, we will choose any corner and remove either the row or column at that corner to reduce to a tableau of size n -1. Depending on whether the corner is of type DE, DA, or AE, we have one of the following three cases.

The chosen corner is a DE box. In this case, that box must contain either an α or a β, so we can decompose the tableau into two cases as in Figure 5. If that box contains an α, then all the boxes above it are empty, and so its entire column has no effect on the rest of the tableau. Thus any filling of this tableau can be obtained from a filling of a tableau with that column removed. Similarly, if that box contains a β, then the boxes to its left must be empty, and so its entire row has no effect on the rest of the tableau. Hence any filling of this tableau can be obtained from filling a tableau with that row removed. Let us represent the state of our tableau with the word XDEY , with X and Y arbitrary words in {D, E, A} * . Consequently, we have the sum of the weights of the fillings:

α n β n weight(XDEY ) = α n-1 β n-1 weight(XDY )(αβ) + α n-1 β n-1 weight(XEY )(αβ)
which matches the first Matrix Ansatz hypothesis. Here the factors of α n β n come from the coefficient that appears in the normalizing factor of a PASEP of size n.

The chosen corner is a DA box. In this case, that box necessarily contains a β, so the boxes to its left are empty and the entire row has no effect on the rest of the tableau. Thus we can describe this tableau in terms of a filling of the smaller tableau with that row removed. Let us represent the state of our tableau with the word XDAY , with X and Y arbitrary words in {D, E, A} * . Thus we obtain the sum of the weights of the fillings:

α n β n weight(XDAY ) = α n-1 β n-1 weight(XAY )(αβ),
which matches the second Matrix Ansatz hypothesis. The chosen corner is a AE box. This case is similar to the one above, except that there is necessarily an α in the corner box, which allows the entire column to be removed. Similar arguments check the transitions at the boundary.

3 Enumeration of multi-Catalan tableaux

Some enumerative results on regular Catalan tableaux were given in the author's work on the regular PASEP [START_REF] Mandelshtam | A determinantal formula for Catalan tableaux and TASEP probabilities[END_REF] that can be extended to the multi-Catalan tableaux. Building on these results, we can deduce the following.

Theorem 3.1 The number of multi-Catalan tableaux corresponding to a two-species PASEP at q = 0 of size n and with r particles of type 1 is

Z 0 n,r (α = β = 1) = 2(r + 1) n + r + 2 2n + 1 n -r .
Theorem 3.2 The number of two-species multi-Catalan tableaux corresponding to a two-species PASEP at q = 0 of size n and with r particles of type 1 and k particles of type 2 is

r + 1 n + 1 n + 1 k n + 1 .
Note that the expression in Theorem 3.1 is the convolution of Catalan numbers, and the expression in Theorem 3.2 is the convolution of Narayana numbers.

We define size(T ) to be the semiperimeter of the tableau T . Let G (α,β) (z) = T z size(T ) wt(T ) be the weight generating function for multi-Catalan tableaux T whose type has zero A's.

G (α,β) (z) = 1 1 -1 2α (1 - √ 1 -4zαβ) 1 1 -1 2β (1 - √ 1 -4zαβ) = 2α 2 β 2 (1 -z) + (αβ -α -β)(1 + √ 1 -4zαβ) 2(α 2 -α + z)(β 2 -β + z) . Note that G (1,1) (z) = 1-2z- √ 1-4z 2z 2
, which is the generating function for the Catalan numbers, enumerates the unweighted multi-Catalan tableaux of type with zero A's.

Theorem 3.3 Let M CT (α,β) (z, y) = T wt(T )z size(T ) y #A's in type(T ) , where T ranges over multi-Catalan tableaux. Then

M CT (α,β) (z, y) = G (α,β) (z) 1 -yG (1,1) (z)
.

It is easy to see that Theorem 3.1 follows from the above for α = β = 1.

For the next theorem, we make some more precise definitions to describe the structure of the multi-Catalan tableaux.

Definition 3.1 We represent a word X in {D, E, A} n with exactly r A's by a list of r + 1 words in {D,E} * , where each word of the list is the longest possible continuous sub-word of X that does not contain an A. We call this list of D-E sub-words (X 1 , . . . , X r+1 ). We then represent that list by a list of partitions Λ = (Λ 1 , . . . , Λ r+1 ), where the partition Λ i = λ(X i ) is the shape obtained from applying Definition 2.5 to the ith D-E word.

As an example for the above, the tableau in Figure 4 has type DDDEADEA, which can be rewritten as a list of three D-E words (DDDE, DE, ∅). Then the list of partitions is Λ = ((1, 1, 1), ( 1), (∅)).

For our final result in this section, we define the matrix A α,β λ = (A ij ) 1≤i,j≤k , where λ is some partition (λ 1 , . . . , λ k ), and

A ij = β j-i α λi-λj+1 λj+1 j-i + β λj+1 j-i+1 + β j-i α λi-λj λj -λj+1-1 =0 α λj --1 j-i-1 + β λj --1 j-i
.

From [START_REF] Mandelshtam | A determinantal formula for Catalan tableaux and TASEP probabilities[END_REF], weight(X) = det A α,β λ(X) for X a word in {D, E} * corresponding to state of the two-species PASEP with zero type 1 particles. Theorem 3.4 Consider the two-species PASEP of size n at q = 0, and a state X with exactly r type 1 particles. Let Λ = (Λ 1 , . . . , Λ r+1 ) be the list of partitions that corresponds to X according to Definition 3.1. Let Λ i have k i rows and m i columns. Then:

Prob(X) = 1 Z 0 n,r α n-m1 β n-kr+1 det A Λ1 (α, 1) det A Λr+1 (1, β) r i=2 det A Λi (1, 1)
where

Z 0 n,r = [z n y r ]M CT (α,β) (z, y) of Theorem 3.3.
4 A Markov chain on the multi-Catalan tableaux that projects to the two-species PASEP at q = 0

In this section we construct a Markov chain on the multi-Catalan tableaux that provides a second proof of Theorem 2.1 and generalizes the construction of Corteel and Williams from [START_REF] Corteel | A Markov chain on permutations which projects to the PASEP[END_REF]. We start by defining projection for Markov chains, from [6, Definition 3.20].

Definition 4.1 Let M and N be Markov chains on finite sets X and Y , and let F be a surjective map from X to Y . We say that M projects to N if the following properties hold:

• If x 1 , x 2 ∈ X with P rob M (x 1 → x 2 ) > 0, then P rob M (x 1 → x 2 ) = P rob N (F (x 1 ) → F (x 2 )).
• If y 1 and y 2 are in Y and P rob N (y 1 → y 2 ) > 0, then for each x 1 ∈ X such that F (x 1 ) = y 1 , there is a unique x 2 ∈ X such that F (x 2 ) = y 2 and P rob M (x 1 → x 2 ) > 0; moreover,

P rob M (x 1 → x 2 ) = P rob N (y 1 → y 2 ).
This means that: if M projects to N via the map F , then the steady state probability that N is in state y is equal to the sum of the steady state probabilities over all the states x ∈ {z ∈ X|F (z) = y}. In our case, N is the two-species PASEP at q = 0, and M is the Markov chain on the multi-Catalan tableaux which we describe below. Corteel and Williams defined a Markov chain on permutation tableaux (in bijection with alternative tableaux) that projects to the PASEP. In the two-species PASEP at q = 0, we have an analogous result using similar transitions. We describe the process by considering the cases of the possible transitions out of some multi-Catalan tableau T which corresponds to the two-species PASEP state X for which type(T ) = X. We begin with the transitions that don't involve particles entering or exiting at the boundary. A transition on state X at location i corresponds to a transition at the corner box in T that has its east edge precisely the ith edge of the southeast border (from top to bottom). Figure 7 shows a transition location in a two-species PASEP word X along with the corresponding corner of some multi-Catalan tableau of type X.

β D D E A A E A A D D E A E A
Now, to obtain a transition at the desired corner, we first strip off the labels on the boundary, then perform certain column or row removal and re-insertion, and finally reapply new labels. We describe the column/row procedure below for the two possible cases for the Greek symbol that corner box could contain. The corner contains a β. Remove the row containing the corner (which necessarily is a horizontal stack of empty boxes with a β on the right), cut off one of the empty boxes, and insert the row (with the β still at the right of it) in the bottom-most location possible so that the resulting shape is still a Young shape. Figure 8 (a) shows an example. If the row originally had a single box, cutting off a box means it becomes an empty row, and so it should be placed at the south end of the shape with the rest of the empty rows.

The corner contains an α. Remove the column containing the corner (which necessarily is a stack of empty boxes above an α), cut off one of the empty boxes, and insert the column (with the α still at the bottom of it) in the right-most location possible so that the resulting shape is still a Young shape. Figure 8 (b) shows an example. If the column originally had a single box, cutting off a box means it becomes an empty column, and so it should be placed at the east end of the shape with the rest of the empty columns.

Now we put the labels back on the edges of the boundary after exchanging the relevant two letters in the labelling word. For example, if the original state was DEA, and a type 2 particle hopped to get the state EDA, then the labels on the boundary change from DEA to EDA.

Transitions at the boundary. For an arbitrary PASEP word X in {D, A, E} * , we describe the transition that corresponds to the PASEP transition EX → DX on a tableau T of type EX. T must necessarily have at least one empty column on its right, so after stripping off the labels of the tableau, we remove the right-most empty column and instead insert a row with a β in its right-most box, of maximal possible length such that the semi-perimeter stays fixed, but at the lowest position possible for that length. Finally, we apply the labeling word DX to the boundary edges. The transition XD → XE is similar. The state diagram of a two-species PASEP at q = 0 of size 3 and with one particle of type 1. Here the words in {0,1,2} 3 represent the states, with 0 representing a hole, 1 representing particle 1, and 2 representing particle 2. Figure 9 shows an example of the transitions on all the states of size 3 with one particle of type 1.

Theorem 4.1 The Markov chain on multi-Catalan tableaux projects to the two-species PASEP at q = 0.

5 Two-species tableaux for q = 1 The goal of this section is to give a combinatorial formula for the two-species PASEP for q = 1. To this end, we define two-species alternative tableaux. Definition 5.1 A two-species alternative tableau of size n is a filling of a Young diagram of shape {n, . . . , 1} with the symbols α, α, β, β, q, q, u, û according to the rules below, which are shown in Figure 10.

• every box on the diagonal must contain an α, β, or x.

• a box that sees an α to its right and a β below must contain an α, β, or q.

• a box that sees an α to its right and a β below must contain an α or q.

• a box that sees an α to its right and a β below must contain a β or q.

• every box in the same column and above an α must contain a u, and every box in the same row and left of a β must contain a u.

• for every pair of α's and β's (α left of β) such that the number of A-rows and A-columns between them is not equal, put a u at the intersection of the α column and the β row.

• for every pair α's and β's (α left of β) such that the number of A-rows and A-columns between them is equal, we must put either a q or a û at the intersection of the α column and the β row.

• the placement of the q and û above must satisfy that there is no instance of q û û û or q û û q . • every other box must contain a u.

In these fillings, the u's are simply place-holders for the empty boxes, and the û's are place-holders that enforce valid placement of the q's. An easy way to construct these fillings is to place the Greek symbols and q's starting from the boxes closest to the diagonal and moving inwards. Once these symbols are placed everywhere possible, we define an α-column to be the boxes directly above an α, and a β-row to be the boxes directly to the left of a β. We then identify the boxes that lie at the intersections of the α-columns and the β-rows, and fill them appropriately with q's, û's, or u's. The rest of the tableau is automatically filled with u's. Definition 5.2 The type of the two-species alternative tableau is read off of the diagonal from top to bottom, by reading an α as D, a β as E, and an x as A. The weight of the tableau is the product of the symbols in the filling in the form of a monomial in α and β, where we set u = û = 1, α = α, β = β, and q = q = 1.

Fig. 1 :

 1 Fig. 1: The parameters of the PASEP.

Fig. 2 :

 2 Fig. 2: The parameters of the two-species PASEP. The black particles are of type 2, and the grey ones are of type 1.

Fig. 3 :

 3 Fig. 3: These are all possible multi-Catalan tableaux of type DEEAE. Their weights are α 4 β 4 , α 3 β 4 , and α 2 β 4 respectively.

Remark 2 . 1 Fig. 4 :

 214 Fig.4: The staircase multi-Catalan tableau on the left and its corresponding condensed multi-Catalan tableau on the right have type DDDEADEA and weight α 6 β 6 . The condensed tableau is precisely the collapsing together of the white boxes from the staircase tableau.

Fig. 5 :

 5 Fig. 5: The chosen corner is a DE box.

Fig. 6 :

 6 Fig. 6: (a) The chosen corner is a DA box or (b) the chosen corner is an AE box.

Fig. 7 :

 7 Fig. 7: The tableau corner involved in the transition DDEAEA → DEDAEA.

Fig. 8 :

 8 Fig.8: An example of the row removal and re-insertion procedure for the two possible cases in the transition corner.

  Fig.9: The state diagram of a two-species PASEP at q = 0 of size 3 and with one particle of type 1. Here the words in {0,1,2} 3 represent the states, with 0 representing a hole, 1 representing particle 1, and 2 representing particle 2.

Fig. 10 :

 10 Fig. 10: An illustration of the rules in Definition 5.1 for the filling of a two-species alternative tableau.

The following theorem is analogous to the main result of Section 2, Theorem 2.1.

Theorem 5.1 Consider the two-species PASEP at q = 1, and let X be a state represented by a word in {D, E, A} n with precisely r A's. Then the steady state probability of X is

where the sum is over all two-species alternative tableaux T such that type(T ) = X, and where Z 1 n,r = T wt(T ), for T ranging over all two-species alternative tableaux of size n whose type has exactly r A's.


Cristian Lenart

Arthur Lubovsky

A uniform realization of the combinatorial R-matrix

Keywords: Kirillov-Reshetikhin crystals, energy function, combinatorial R-matrix, quantum alcove model

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Kashiwara's crystals [START_REF] Kashiwara | On crystal bases of the q-analogue of universal enveloping algebras[END_REF] are colored directed graphs encoding the structure of certain bases (called crystal bases) of some representations of quantum groups U q (g) as q goes to zero (where g is a symmetrizable Kac-Moody Lie algebra). All highest weight representations have crystal bases/graphs. Beside them, an important class of crystals is represented by the Kirillov-Reshetikhin (KR) crystals [START_REF] Kirillov | Representations of Yangians and multiplicities of the inclusion of the irreducible components of the tensor product of representations of simple Lie algebras[END_REF]. They correspond to certain finite-dimensional modules for affine Lie algebras which are not of highest weight. A KR crystal is denoted B r,s , being labeled by an r × s rectangle, where the height r indexes a simple root of the corresponding finite root system and the width s is any positive integer. The importance of KR crystals stems from the fact that they are building blocks for the corresponding (infinite) highest weight crystals; indeed, the latter are realized as infinite tensor products of the former in the Kyoto path model, see, e.g., [START_REF] Hong | Introduction to Quantum Groups and Crystal Bases[END_REF]. Tensor products of KR crystals are endowed with a grading known as the energy function, which originates in the theory of solvable lattice models [HKO + 99]. There is a unique affine crystal isomorphism between two tensor products of KR crystals differing by a permutation of the tensor factors; it is called the combinatorial R-matrix.

The first author and Postnikov [START_REF] Lenart | Affine Weyl groups in K-theory and representation theory[END_REF][START_REF] Lenart | A combinatorial model for crystals of Kac-Moody algebras[END_REF] defined the so-called alcove model for highest weight crystals associated to a symmetrizable Kac-Moody algebra. This model is a discrete counterpart of the celebrated Littelmann path model [START_REF] Littelmann | Paths and root operators in representation theory[END_REF]. In [START_REF] Lenart | A generalization of the alcove model and its applications[END_REF] the authors generalize the alcove model. This generalization, called the quantum alcove model, has been shown in [LNS + 13b] to uniformly describe tensor products of column shape KR crystals for all untwisted affine types. By contrast, all the existing combinatorial models for KR crystals are type-specific; most of them correspond to the classical types, and are based on diagram fillings, i.e., on tableau models [START_REF] Fourier | Kirillov-Reshetikhin crystals for nonexceptional types[END_REF]. As far as the energy function is concerned, in the quantum alcove model it is computed uniformly and efficiently by a statistic called height [LNS + 13b], whereas an efficient computation based on the tableau models is only available in types A and C [START_REF] Lenart | From Macdonald polynomials to a charge statistic beyond type A[END_REF][START_REF] Lenart | Crystal energy via the charge in types A and C[END_REF].

In this paper we enhance the quantum alcove model by using it to give a uniform realization of the combinatorial R-matrix. The construction is based on certain combinatorial moves called quantum Yang-Baxter moves, which generalize their alcove model versions defined in [START_REF] Lenart | On the combinatorics of crystal graphs, I. Lusztig's involution[END_REF]. Note that, as far as existing realizations of the combinatorial R-matrix are concerned, they are limited in scope and type-specific. For instance, in terms of the tableau models, there is a construction in type A based on Schützenberger's jeu de taquin (sliding algorithm) on two columns [START_REF] Fulton | Young Tableaux[END_REF], whereas the extensions of this procedure to types B and C are involved and not transparent, see [START_REF] Lecouvey | Schensted-type correspondence, plactic monoid, and jeu de taquin for type Cn[END_REF][START_REF] Lecouvey | Schensted-type correspondences and plactic monoids for types Bn and Dn[END_REF]. By contrast, our construction is easy to formulate, and is related to more general concepts.

We also show that, like the alcove model, its quantum generalization does not depend on the choice of a sequence of roots called a λ-chain (or, equivalently, on the choice of a sequence of alcoves joining the fundamental one to a translation of it). Note that the similar statement for the Littelmann path model was proved in [START_REF] Littelmann | Paths and root operators in representation theory[END_REF] based on subtle continuous arguments, whereas the alcove model and its quantum generalization are discrete, so they are amenable to the use of the mentioned combinatorial methods. Due to space constraints we were unable to include any proofs in this extended abstract and instead refer the interested reader to [START_REF] Lenart | A uniform realization of the combinatorial R-matrix[END_REF].

Background

Root systems

Let g be a complex simple Lie algebra, and h a Cartan subalgebra, of rank r. Let Φ ⊂ h * be the corresponding irreducible root system, h * R ⊂ h * the real span of the roots, and Φ + ⊂ Φ the set of positive roots. We denote, as usual, the reflection corresponding to the root α by s α . Let α 1 , . . . , α r ∈ Φ + be the simple roots, and s i := s αi the simple reflections; the latter generate the Weyl group W . We denote •, • the non-degenerate scalar product on h * R induced by the Killing form. Given a root α, the corresponding coroot is α ∨ := 2α/ α, α . If α = i c i α i , then the height of α is given by ht(α) := i c i .

The weight lattice Λ consists of λ ∈ h * R with λ, α ∨ ∈ Z for any α ∈ Φ. The weight lattice Λ is generated by the fundamental weights ω 1 , . . . ω r , which form the dual basis to the basis of simple coroots, i.e., ω i , α ∨ j = δ ij . The set Λ + of dominant weights consists of λ ∈ Λ with λ, α ∨ ≥ 0 for any α ∈ Φ + .

Given α ∈ Φ and k ∈ Z, we denote by s α,k the reflection in the affine hyperplane

H α,k := {λ ∈ h * R : λ, α ∨ = k} . (1)
These reflections generate the affine Weyl group W aff for the dual root system Φ ∨ := {α ∨ | α ∈ Φ}. The hyperplanes H α,k divide the real vector space h * R into open regions, called alcoves. The fundamental alcove A • is given by

A • := λ ∈ h * R | 0 < λ, α ∨ < 1 for all α ∈ Φ + .
(2)

Weyl groups

Let W be the Weyl group of the root system Φ discussed above.

We denote this graph by QB(W ). We will sometimes refer to edges in QB(W ) where w ws α as up steps, and edges where w ¡ ws α as down steps. See Figure 1 for an example.

We recall an important topological property of QB(W ), called shellability, which was proved in [START_REF] Brenti | Mixed Bruhat operators and Yang-Baxter equations for Weyl groups[END_REF]. This is defined with respect to a reflection ordering on the positive roots [D93].

Theorem 2.1. [BFP99] Fix a reflection ordering on Φ + . For any pair of elements v, w ∈ W , there is a unique path from v to w in the quantum Bruhat graph QB(W ) such that its sequence of edge labels is strictly increasing (resp., decreasing) with respect to the reflection ordering.

Kirillov-Reshetikhin (KR) crystals

Given a symmetrizable Kac-Moody algebra g, a g-crystal is a non-empty set B together with maps e i , f i : B → B∪{0} for i ∈ I (where I indexes the simple roots corresponding to g, as usual, and 0 ∈ B),

f i (b 1 ⊗ b 2 ) := f i (b 1 ) ⊗ b 2 if ε i (b 1 ) ≥ ϕ i (b 2 ) b 1 ⊗ f i (b 2 ) otherwise, (4)
and similarly for e i . The highest weight crystal B(λ) of highest weight λ ∈ Λ + is a certain crystal with a unique element u λ such that e i (u λ ) = 0 for all i ∈ I and wt(u λ ) = λ. It encodes the structure of the crystal basis of the U q (g)-irreducible representation with highest weight λ as q goes to 0. A Kirillov-Reshetikhin (KR) crystal [KR90] is a finite crystal B r,s for an affine algebra, labeled by a rectangle of height r and width s, where r ∈ I \ {0} and s is any positive integer. We refer, throughout, to the untwisted affine types A

(1)

n-1 -G (1)
2 , and only consider column shape KR crystals B r,1 .

As an example, consider the KR crystal B r,1 of type A

(1) n-1 with r ∈ {1, 2, . . . , n -1}, for which we have a simple tableau model. As a classical type A n-1 crystal, B r,1 is isomorphic to the corresponding crystal B(ω r ). Recall that an element b ∈ B(ω r ) is represented by a strictly increasing filling of a height r column, with entries in [n] := {1, . . . , n}. There is a simple construction of the crystal operators on a tensor product of (column shape) KR crystals of type A

(1) n-1 , which is based on (4). We refer again to (column shape) KR crystals of arbitrary (untwisted) type. Let λ = (λ 1 ≥ λ 2 ≥ . . .) be a partition, and λ the conjugate partition. We define B ⊗λ := λ1 i=1 B λ i ,1 . More generally, given a composition p = (p 1 , . . . , p k ), we define B ⊗p := k i=1 B pi,1 . (In both cases, we assume that the corresponding column shape KR crystals exist.) We denote such a tensor product generically by B. Remarks 2.2. (1) It is known that B is connected as an affine crystal, but disconnected as a classical crystal (i.e., with the 0-arrows removed).

(2) Let p be a composition obtained from p by permuting its parts. There is an affine crystal isomorphism between B ⊗p and B ⊗p , unique by the previous remark, called the combinatorial R-matrix.

We need to distinguish certain arrows in B, related to affine Demazure crystals, as we shall explain.

Definition 2.3. An arrow b → f i (b) in B is called a Demazure arrow if i = 0, or i = 0 and ε 0 (b) ≥ 1. An arrow b → f i (b) in B is called a dual Demazure arrow if i = 0, or i = 0 and ϕ i (b) ≥ 2.
Remarks 2.4. (1) By Fourier-Littelmann [START_REF] Fourier | Tensor product structure of affine Demazure modules and limit constructions[END_REF], in simply-laced types, the tensor product of KR crystals B is isomorphic, as a classical crystal (discard the affine 0-arrows) with a certain Demazure crystal for the corresponding affine algebra. (Demazure modules are submodules of highest weight ones determined by a Borel subalgebra acting on an extremal weight vector.) Moreover, by [START_REF] Fourier | Demazure structure inside Kirillov-Reshetikhin crystals[END_REF], the 0-arrows in the latter correspond precisely to the Demazure arrows in B.

(2) In the case when all of the tensor factors in B are perfect crystals [HK00], B remains connected upon removal of the non-Demazure (resp. non-dual Demazure) 0-arrows.

(3) In the classical types, B k,1 is perfect as follows: in types A

(1)

n-1 and D

(1

)
n for all k, in type B

(1)

n only for k = n, and in type C

(1) n only for k = n (using the standard indexing of the Dynkin diagram); in other words, for all the Dynkin nodes in simply-laced types, and only for the nodes corresponding to the long roots in non-simply-laced types. It was conjectured in [HKO + 99] that the same is true in the exceptional types. In type G

(1) 2 this was confirmed in [START_REF] Yamane | Perfect crystals of Uq(G (1) 2 )[END_REF], while for types E

The quantum alcove model

In this section we recall the quantum alcove model, which is a model for KR crystals corresponding to a fixed untwisted affine Lie algebra g. This model is based on the combinatorics of the root system of the corresponding finite-dimensional Lie algebra g, so we use freely the notation in Section 2.1.

We say that two alcoves are adjacent if they are distinct and have a common wall. Given a pair of adjacent alcoves A and B, we write A β -→ B if the common wall is of the form H β,k and the root β ∈ Φ points in the direction from A to B. Definition 2.5. An alcove path is a sequence of alcoves (A 0 , A 1 , . . . , A m ) such that A j-1 and A j are adjacent, for j = 1, . . . , m. We say that an alcove path is reduced if it has minimal length among all alcove paths from A 0 to A m .

Let A λ = A • + λ be the translation of the fundamental alcove A • by the weight λ.

Definition 2.6. The sequence of roots (β 1 , β 2 , . . . , β m ) is called a λ-chain if

A 0 = A • -β1 -→ A 1 -β2 -→ • • • -βm -→ A m = A -λ (5)
is a reduced alcove path.

We now fix a dominant weight λ and an alcove path Π = (A 0 , . . . , A m ) from A 0 = A • to A m = A -λ . Note that Π is determined by the corresponding λ-chain Γ := (β 1 , . . . , β m ), which consists of positive roots. A specific choice of a λ-chain, called a lex λ-chain and denoted Γ lex , is given in [LP08, Proposition 4.2]; this choice depends on a total order on the simple roots.

Given the λ-chain Γ above, we let r i := s βi , and let r i be the affine reflection in the hyperplane containing the common face of A i-1 and A i , for i = 1, . . . , m; so r i := s βi,-li , where

l i := | {j < i ; β j = β i } |. We define l i := λ, β ∨ i -l i = | {j ≥ i ; β j = β i } |. Let J = {j 1 < j 2 < • • • < j s } ⊆ [m],
whose elements are called folding positions. We say that j i is a positive folding position if r j1 r j2 . . . r ji-1 < r j1 r j2 . . . r ji , and a negative folding position otherwise. We denote the positive folding positions by J + , and the negative ones by J -. We define the weight µ(J) and the height statistic by

µ = µ(J) := -r j1 r j2 . . . r js (-λ) , height(J) := j∈J - l j . ( 6
) Definition 2.7. A subset J = {j 1 < j 2 < • • • < j s } ⊆ [m]
(possibly empty) is admissible if we have the following path in QB(W ):

1 βj 1 -→ r j1 βj 2 -→ r j1 r j2 βj 3 -→ • • • βj s -→ r j1 r j2 • • • r js . (7)
We let A(Γ) be the collection of admissible subsets corresponding to the λ-chain Γ. When Γ is clear from the context, we may use the notation A(λ) instead.

Remark 2.8. If we restrict to admissible subsets for which the path (7) has no down steps, we recover the classical alcove model in [START_REF] Lenart | Affine Weyl groups in K-theory and representation theory[END_REF][START_REF] Lenart | A combinatorial model for crystals of Kac-Moody algebras[END_REF].

Combinatorial crystal operators f i and e i (where i indexes the simple roots corresponding to g) were constructed on A(Γ) and their properties were studied in [START_REF] Lenart | A generalization of the alcove model and its applications[END_REF]. In particular, the crystal operator f i applied to an admissible subset J adds a folding position to J, while at the same time possibly removing a folding position from J.

We summarize the results in [LNS + 13b, LNS + 12] about the applications of the quantum alcove model. (2) If the vertex b of B corresponds to J under the isomorphism in part (1), then the energy at b is given, up to a global constant, by -height(J).

Remark 2.10. The isomorphism in Theorem 2.9 (1) is canonical, so we identify the two crystals.

Specializing the quantum alcove model to type A

We start with the basic facts about the root system of type A n-1 . We can identify the space h * R with the quotient V := R n /R(1, . . . , 1), where R(1, . . . , 1) denotes the subspace in R n spanned by the vector (1, . . . , 1). Let ε 1 , . . . , ε n ∈ V be the images of the coordinate vectors in R n . The root system is Φ = {α ij := ε i -ε j : i = j, 1 ≤ i, j ≤ n}. The simple roots are α i = α i,i+1 , for i = 1, . . . , n-1. The weight lattice is Λ = Z n /Z(1, . . . , 1). The fundamental weights are ω i = ε 1 + . . . + ε i , for i = 1, . . . , n -1. A dominant weight λ = λ 1 ε 1 + . . . + λ n-1 ε n-1 is identified with the partition (λ 1 ≥ λ 2 ≥ . . . ≥ λ n-1 ≥ λ n = 0) having at most n -1 parts. Considering the Young diagram of the dominant weight λ as a concatenation of columns, whose heights are λ 1 , λ 2 , . . ., corresponds to expressing λ as ω λ 1 + ω λ 2 + . . . (as usual, λ is the conjugate partition to λ).

The Weyl group W is the symmetric group S n , which acts on V by permuting the coordinates ε 1 , . . . , ε n . Permutations w ∈ S n are written in one-line notation w = w(1) . . . w(n). For simplicity, we use the same notation (i, j) with 1 ≤ i < j ≤ n for the root α ij and the reflection s αij , which is the transposition t ij .

We now consider the specialization of the alcove model to type A. For any k = 1, . . . , n -1, we have the following ω k -chain, from A • to A -ω k , denoted by Γ(k):

((k, k + 1), (k, k + 2) , . . . , (k, n), (k -1, k + 1), (k -1, k + 2) , . . . , (k -1, n), . . . . . . . . . (1, k + 1), (1, k + 2) , . . . , (1, n)) . (8)
Fix a dominant weight λ, for which we use the partition notation above. We construct a λ-chain Γ = (β 1 , β 2 , . . . , β m ) as the concatenation Γ := Γ 1 . . . Γ λ1 , where Γ j = Γ(λ j ). Let J = {j 1 < • • • < j s } be a set of folding positions in Γ, not necessarily admissible, and let T be the corresponding list of roots of Γ, also viewed as transpositions. The factorization of Γ induces a factorization on T as T = T 1 T 2 . . . T λ1 . We denote by T 1 . . . T j the permutation obtained by composing the transpositions in T 1 , . . . , T j from left to right. For w ∈ W , written w = w 1 w 2 . . . w n , let w[i, j] = w i . . . w j .

Definition 2.11. Let π j = π j (T ) := T 1 . . . T j . We define the filling map, which associates with each J ⊆ [m] a filling of the Young diagram λ, by fill(J) = fill(T ) := C 1 . . . C λ1 , where

C i := π i [1, λ i ].
In other words, the columns C i of the Young diagram are filled top to bottom by the first λ i entries of the permutation π i . We define the sorted filling map sfill(J) by sorting ascendingly the columns of fill(J).

Theorem 2.12. [Len12, LL14] The map sfill is the unique affine crystal isomorphism between A(Γ) and the subgraph of B ⊗λ consisting of the dual Demazure arrows. In other words, given sfill(J) = b, there is a dual Demazure arrow b → f i (b) if and only if f i (J) = 0, and we have f i (b) = sfill(f i (J)). The map sfill also preserves weights, and translates the height statistic into the Lascoux-Schützenberger charge statistic on fillings.

There is a similar result in type

C [Len12], [LS13], [LL14, Section 4.2].

The main results

In this section we realize the combinatorial R-matrix in terms of the quantum alcove model, and show that this model is independent of the choice of a λ-chain. We start with a preview of the main result. Let p be the composition p = (p 1 , . . . , p k ), and let p = (p 1 , . . . , p k ) be a permutation of p. Let

B ⊗p := B p1,1 ⊗ • • • ⊗ B p k ,1 , B ⊗p := B p 1 ,1 ⊗ • • • ⊗ B p k ,1 Γ := Γ(p 1 ) • • • Γ(p k ) , Γ := Γ(p 1 ) • • • Γ(p 2 ) , (9)
where Γ(i) is an ω i -chain; thus, Γ and Γ are λ-chains, where λ := ω p1 + • • • + ω p k . We will show that A(Γ) and A(Γ ) are models for the isomorphic affine crystals B ⊗p and B ⊗p . Thus, we want to realize the combinatorial R-matrix as an affine crystal isomorphism between A(Γ) and A(Γ ).

Example 3.1. Consider type A 2 . Let p = (1, 2, 2, 1), p = (1, 2, 1, 2), so λ = (4, 2, 0). Then

B ⊗p = B 1,1 ⊗ B 2,1 ⊗ B 2,1 ⊗ B 1,1 B 1,1 ⊗ B 2,1 ⊗ B 1,1 ⊗ B 2,1 = B ⊗p .
We first note that in type A the combinatorial R-matrix can be realized by Schützenberger's jeu de taquin (sliding algorithm) on the last two columns, see [START_REF] Fulton | Young Tableaux[END_REF]. For example:

3 ⊗ 2 3 ⊗ 1 2 ⊗ 3 = 3 ⊗ 2 3 ⊗ 1 3 2 → 3 ⊗ 2 3 ⊗ 1 2 3 → 3 ⊗ 2 3 ⊗ 1 2 3 = 3 ⊗ 2 3 ⊗ 2 ⊗ 1 3 .
We now demonstrate how to realize the combinatorial R-matrix in the quantum alcove model. Let Γ and Γ be the λ-chains corresponding to p and p (the bars indicate the splittings into ω i -chains, cf. ( 9)):

Γ = ( (1, 2), (1, 3) | (2, 3), (1, 3) | (2, 3), (1, 3) | (1, 2), (1, 3) ) , Γ = ( (1, 2), (1, 3) | (2, 3), (1, 3) | (1, 2), (1, 3) | (2, 3), (1, 3) ) . (10)
In (10) we also showed (via the underlined positions) two admissible subsets: J = {1, 2, 3, 6, 7, 8} in A(Γ) and J = {1, 2, 3, 5, 7, 8} in A(Γ ). Here J is admissible as it corresponds to the path in QB(W ) shown in Figure 1a which starts at the identity and consists of the edges labeled 1, 2, 3, 2, 1, 2. The details of our construction will be given in Section 3.1 (see Example 3.3); for now, note that J will correspond to J via our construction. We recover the construction above in terms of jeu de taquin since

sfill(J) = 3 ⊗ 2 3 ⊗ 1 2 ⊗ 3 → 3 ⊗ 2 3 ⊗ 2 ⊗ 1 3 = sfill(J ) .
We construct a bijection between A(Γ) and A(Γ ) by generalizing the construction in [START_REF] Lenart | On the combinatorics of crystal graphs, I. Lusztig's involution[END_REF], which gives the bijection in the classical case, where admissible subsets correspond to saturated chains in Bruhat order. The bijection in [START_REF] Lenart | On the combinatorics of crystal graphs, I. Lusztig's involution[END_REF] is based on a sequence of operations called Yang-Baxter moves.

Quantum Yang-Baxter moves

This section contains our main constructions. We use freely the notation related to the quantum alcove model in Section 2.4. We consider segments of the λ-chain corresponding to Weyl subgroups of rank 2.

We start by recalling that there are only two reflection orderings on the positive roots corresponding to a dihedral Weyl group of order 2q, that is, a Weyl group of type A 1 ×A 1 , A 2 , C 2 , or G 2 (with q = 2, 3, 4, 6, respectively). Let Φ be the corresponding root system with simple roots α, β. The two reflection orderings on Φ + are given by the following sequence and its reverse:

β 1 := α, β 2 := s α (β), β 3 := s α s β (α), . . . , β q-1 := s β (α), β q := β . (11)
Fix λ ∈ Λ + . Consider an index set I := {1 < . . . < t < 1 < . . . < q < t + 1 < . . . < n}. Let Γ = {β i } i∈I be a λ-chain, denote r i := s βi as before, and define the sequence of roots Γ = {β i } i∈I by

β i = β q+1-i if i ∈ [q] β i if i ∈ I \ [q] . (12)
In other words, the sequence Γ is obtained from the λ-chain Γ by reversing a certain segment. Now assume that {β 1 , . . . , β q } are the positive roots (without repetition) of a rank two root subsystem Φ of Φ.

The corresponding dihedral reflection group W is a subgroup of the Weyl group W .

Proposition 3.2. [START_REF] Lenart | On the combinatorics of crystal graphs, I. Lusztig's involution[END_REF] (1) The sequence Γ is also a λ-chain, and the sequence (β 1 , . . . , β q ) is a reflection ordering of Φ + .

(2) We can obtain any λ-chain from any other λ-chain by moves of the form Γ → Γ .

Let us now map the admissible subsets in A(Γ) to those in A(Γ ). To this end, fix a reflection ordering of Φ + compatible with the above ordering (β 1 , . . . , β q ) of Φ; this clearly exists (take any reflection ordering of Φ + , and reverse it if needed). Now fix an admissible subset J = {j 1 < • • • < j s } in A(Γ). Define w(J) := r j1 r j2 • • • r js , and u := w(J ∩ {1, . . . , t}) , and w := w(J ∩ ({1, . . . , t} ∪ [q])) .

(13)

Note that, by the definition of A(Γ), we have a path in QB(W ) from u to w with increasing edge labels J ∩ [q] (here we identify an edge label β i with i, for i ∈ [q]). By the shellability property of QB(W ), that is, by Theorem 2.1, there is another path in QB(W ) from u to w whose edge labels (in Φ + ) increase with respect to the reverse of the reflection ordering considered above. In fact, by the proof of Theorem 2.1 in [START_REF] Brenti | Mixed Bruhat operators and Yang-Baxter equations for Weyl groups[END_REF], these edge labels are also in Φ + , since the edge labels of the first path had this property. Thus, by now identifying the label β i with i, we can view the edge labels of the new path as a subset of [q], which we denote by Y u,w (J ∩ [q]).

It is clear that we have a bijection Y : A(Γ) → A(Γ ) given by

Y (J) := (J\[q]) ∪ Y u,w (J ∩ [q]) . (14)
We call the moves J → Y (J) quantum Yang-Baxter moves. They generalize the Yang-Baxter moves in [START_REF] Lenart | On the combinatorics of crystal graphs, I. Lusztig's involution[END_REF], which correspond to saturated chains in the Bruhat order (i.e., there are no down steps).

Example 3.3. We continue Example 3.1. In (10) we obtain Γ from Γ by reversing the first three roots in the right half of Γ. We will use the conventions of this section and (re)label this segment of Γ by (β 1 , β 2 , β 3 ). We also let s 1 = s β1 and s 2 = s β3 . We have u = s 1 s 2 s 1 = 321, and w = s 2 = 213, in one line notation. In this case, we have Y u,w ({2, 3}) = {1, 3}, see Figure 1a. Hence Y ({1, 2, 3, 6, 7, 8}) = {1, 2, 3, 5, 7, 8}, where now the indexing corresponds to the entire λ-chain, cf. Example 3.1.

We now describe the quantum Yang-Baxter moves in types A 2 , C 2 , and B 2 ; type G 2 is more involved, but still manageable. Our description is in terms of the corresponding dihedral reflection group W , which is a subgroup of the Weyl group W above. The following result is based on [BFP99, Lemma 5.1].

Proposition 3.4. Given w ∈ W , let w be the minimum length representative of the coset wW , and write w = w w, where w ∈ W . Under the bijection w → w w between W and wW , every edge of the graph on wW induced from QB(W ) corresponds to an edge of QB(W ).

By Proposition 3.4, the map Y u,w used to define the quantum Yang-Baxter moves in (14) depends only on u and w, so we will denote it by Y u,w . Hence it suffices to focus on the quantum Bruhat graphs for the dihedral Weyl groups. The ones of type A 2 and C 2 are shown in Figure 1, where the edge labels correspond to the reflection ordering (11), and s 1 := s β1 , s 2 := s . The graph of type B 2 is identical with the one of type C 2 if we set β 1 = ε 2 (short root, like in type C 2 ), β 4 = ε 1 -ε 2 (long root), and s 1 := s β1 , s 2 := s β4 , as above. Let us now recall from [START_REF] Lenart | On the combinatorics of crystal graphs, I. Lusztig's involution[END_REF] the explicit description of the classical Yang-Baxter moves, i.e., of the map J → Y u,w (J) on subsets of [q], for u < w in W . Recall that J and Y u,w (J) correspond to saturated chains in Bruhat order from u to w, whose edge labels increase, resp. decrease, with respect to the reflection ordering (11); in fact, as explained in Section 3.1, an index i in J corresponds to the root/edge label β i , whereas an index i in Y u,w (J) corresponds to the root β i := β q+1-i , cf. (12). The classical moves can be described in a uniform way (i.e., for all types), and only in terms of a := (u) and b := (w), as shown in Figure 2. The non-classical quantum Yang-Baxter moves J → Y u,w (J) do not have a uniform description and are listed in Figure 3, by the corresponding starting vertex u. The top and bottom rows are the sequences J and Y u,w (J), respectively, while we also have to consider the reverse moves Y u,w (J) → J; the mentioned sequences correspond to paths in QB(W ), as explained in Section 3.1 (see also the convention related to the edge labels, which was recalled above, in connection to the classical moves). The symbol * is used to indicate the down edges in QB(W ).

s 1 s 2 s 1 s 1 s 2 s 2 s 1 s 1 s 2 1 1 3 2 1 3 3 1 3 2 1 2 1 3 1 3 β 1 = ε 1 -ε 2 β 3 = ε 2 -ε 3 (a) Type A 2 s 2 s 1 s 2 s 1 s 1 s 2 s 1 s 2 s 1 s 2 s 1 s 2 s 2 s 1 s 1 s 2 1 4 1 2 4 1 2 1 4 1 2 4 3 4 1 4 2 1 3 1 4 1 4 β 1 = ε 1 -ε 2 , β 4 = 2ε 2 (b) Type C 2
0: ∅ ↔ ∅ if a = b . Case 1.1: {1} ↔ {q} if 0 ≤ a = b -1 ≤ q -1 .
Case 1.2: {q -a} ↔ {a + 1} if 0 < a = b -1 < q -1 .

Case 2.1: {1, a + 2, a + 3, . . . , b} ↔ {a + 1, a + 2, . . . , b -1, q} if 0 ≤ a < a + 2 ≤ b < q .

Case 2.2: {1, a + 2, a + 3, . . . , b -1, q} ↔ {a + 1, a + 2, . . . , b} if 0 < a < a + 2 ≤ b ≤ q .

Case 3: [q] ↔ [q] if a = 0 and b = q .

Properties of the quantum Yang-Baxter moves

Using the same notation as in Section 3.1, we present the main properties of the quantum Yang-Baxter moves, concerning the quantities they preserve, and their interaction with the crystal operators. where the left hand sides are computed with respect to Γ, and the right hand sides with respect to Γ .

Theorem 3.6 below generalizes the similar result in [START_REF] Lenart | On the combinatorics of crystal graphs, I. Lusztig's involution[END_REF] for the classical Yang-Baxter moves.

Theorem 3.6. The crystal operators commute with the quantum Yang-Baxter moves, that is, f i is defined on an admissible subset J if and only if it is defined on Y (J), and we have Y (f i (J)) = f i (Y (J)).

  and wt : B → Λ. We require b = f i (b) if and only if b = e i (b ), and wt(f i (b)) = wt(b) -α i . The maps e i and f i are called crystal operators and are represented as arrows b → b = f i (b) colored i; thus they endow B with the structure of a colored directed graph. For b ∈ B, we set ε i (b) := max{k | e k i (b) = 0}, and ϕ i (b) := max{k | f k i (b) = 0}. Given two g-crystals B 1 and B 2 , we define their tensor product B 1 ⊗B 2 as follows. As a set, B 1 ⊗B 2 is the Cartesian product of the two sets. For b = b 1 ⊗b 2 ∈ B 1 ⊗B 2 , the weight function is simply wt(b) := wt(b 1 ) + wt(b 2 ). The crystal operators are given by

  by computer, based on a model closely related to the quantum alcove model [LNS + 13b].

  Theorem 2.9. [LNS + 13b] Consider a composition p = (p 1 , . . . , p k ) and the corresponding KR crystal B := k i=1 B pi,1 . Let λ := ω p1 + . . . + ω p k , and let Γ lex be a corresponding lex λ-chain.(1) The (combinatorial) crystal A(Γ lex ) is isomorphic to the subgraph of B consisting of the dual Demazure arrows, via a specific bijection which preserves the weights of the vertices.

Fig. 1 :

 1 Fig. 1: Quantum Bruhat graphs.

Case

Fig. 2 :Fig. 3 :

 23 Fig. 2: The classical Yang-Baxter moves.

Proposition 3. 5 .

 5 The quantum Yang-Baxter moves preserve the Weyl group element w( • ), as well as the weight µ( • ) and the height statistic (defined in (6)); in other words, we havew(J) = w(Y (J)) , µ(J) = µ(Y (J)) , height(J) = height(Y (J)) ,

  The length function on W is denoted by (•). The Bruhat order on W is defined by its covers w ws α , for α ∈ Φ + , if (ws α ) = (w) + 1. Define w ¡ ws α , for α ∈ Φ + , if (ws α ) = (w) -2ht(α ∨ ) + 1. The quantum Bruhat graph[START_REF] Brenti | Mixed Bruhat operators and Yang-Baxter equations for Weyl groups[END_REF] is the directed graph on W with edges labeled by positive roots w

α

-→ ws α for w ws α or w ¡ ws α .

† Partially supported by the NSF grants DMS-1101264 and DMS-1362627; the hospitality and support of the Max-Planck-Institut für Mathematik in Bonn, where part of this work was carried out, are also gratefully acknowledged.

‡ Supported by a GAANN grant from the US Department of Education.

1365-8050

Corollaries and conjectures

In this section we state some corollaries of the results in the previous section which are, in fact, the main results of the paper. We also discuss possible strengthenings of these results.

Theorem 3.6 and Proposition 3.5 immediately imply the following corollary (cf. also Proposition 3.2), which essentially says that the quantum alcove model is independent of the choice of a λ-chain.

Corollary 3.7. Given λ-chains Γ and Γ , there is an affine crystal isomorphism between A(Γ) and A(Γ ), realized by composing quantum Yang-Baxter moves; it preserves the weights and heights of the vertices.

By composing the explicit bijection between B ⊗p and A(Γ lex ) in Theorem 2.9 with an affine crystal isomorphism between A(Γ lex ) and A(Γ) realized by quantum Yang-Baxter moves (where Γ is an arbitrary λ-chain, see Corollary 3.7), we obtain the following strengthening of Theorem 2.9.

Corollary 3.8. Theorem 2.9 holds for any choice of a λ-chain, based on the bijection mentioned above. Remark 3.9. There are several ways to connect two λ-chains Γ to Γ via the moves in Proposition 3.2. A priori, the corresponding compositions of quantum Yang-Baxter moves give different affine crystal isomorphisms between A(Γ) and A(Γ ) in Corollary 3.7. Therefore, in Corollary 3.8 we have a collection of a priori different affine crystal isomorphisms between B ⊗p and A(Γ), for a fixed λ-chain Γ. All this is due to the fact that B ⊗p is not necessarily connected under the dual Demazure arrows, cf. Remark 2.2 (1) and Remark 2.4 (2). However, we make the following conjecture.

Conjecture 3.10. All the affine crystal isomorphisms between A(Γ) and A(Γ ) in Corollary 3.7 are identical. The same is true about the isomorphisms between B ⊗p and A(Γ) in Corollary 3.8. Remark 3.11. If all the tensor factors in B ⊗p are perfect crystals, then there is a unique affine crystal isomorphism between B ⊗p and A(Γ), by Remark 2.4 (2). Conjecture 3.10 then follows. Now let p be a composition and p a permutation of it. Recall the corresponding λ-chains Γ and Γ constructed in (9). By Corollary 3.8, we have affine crystal isomorphisms between B ⊗p and A(Γ), as well as between B ⊗p and A(Γ ). Also recall from Remark 2.2 (2) the combinatorial R-matrix B ⊗p ∼ = B ⊗p . The uniqueness property in Remark 3.11 leads to the following result.

Corollary 3.12. Suppose that all the tensor factors in B ⊗p are perfect crystals. Then the quantum Yang-Baxter moves realize the combinatorial R-matrix as an affine crystal isomorphism between A(Γ) and A(Γ ), in the sense mentioned above. Remark 3.13. For the general case of Corollary 3.12, we need to realize the non-dual Demazure 0-arrows in the quantum alcove model, cf. Theorem 2.9, and generalize Theorem 3.6 accordingly.