MIXED BRUHAT OPERATORS AND YANG-BAXTER EQUATIONS FOR WEYL GROUPS

FRANCESCO BRENTI, SERGEY FOMIN, AND ALEXANDER POSTNIKOV

1. Introduction

We introduce and study a family of operators which act in the group algebra of a Weyl group W and provide a multi-parameter solution to the quantum Yang-Baxter equations of the corresponding type. These operators are then used to derive new combinatorial properties of W, and to obtain new proofs of known results concerning the Bruhat order of W.

The paper is organized as follows. Section 2 is devoted to preliminaries on Coxeter groups and associated Yang-Baxter equations.

In Theorem 3.1 of Section 3, we describe our solution of these equations.

In Section 4, we consider certain limiting case of our solution, which leads to the quantum Bruhat operators. These operators play an important role in the explicit description of the (small) quantum cohomology ring of G/B.

Section 5 contains the proof of Theorem 3.1.

Section 6 is devoted to combinatorial applications of our operators. For an arbitrary element u ∈ W, we define a graded partial order on W called the tilted Bruhat order; this partial order has unique minimal element u. (The usual Bruhat order corresponds to the special case where u = e, the identity element.) We then prove that tilted Bruhat orders are lexicographically shellable graded posets whose every interval is Eulerian. This generalizes the well known results of D.-N. Verma, A. Björner, M. Wachs, and M. Dyer.

2. Coxeter groups and Yang-Baxter equations

We first recall some standard terminology and notation related to Coxeter groups. Missing details can be found in [5, 17]. Let (W, S) be a finite Coxeter system. Thus W is a finite Coxeter group generated by the set S of its simple reflections, which satisfy the relations (st)^{m(s,t)} = 1 , for s, t ∈ S. The parameters m(s, t) are nonnegative integers such that m(s, s) = 1 and m(s, t) = m(t, s) > 1 for s ≠ t.

For an element w ∈ W, an expansion w = s_{1} ⋯ s_{l} of minimal possible length l is called a reduced decomposition. The number l = ℓ(w) is the length of w. The elements of the set T = {wsw^{−1} : w ∈ W, s ∈ S} are the reflections of W.

Date: December 15, 1998 .

1991 Mathematics Subject Classification. Primary 05E15, Secondary 06A07, 14M15, 20F55.

Key words and phrases. Coxeter group, Weyl group, Bruhat order, Yang-Baxter equation, quantum cohomology, Eulerian poset, Möbius function.

The authors were supported in part by MSRI (NSF grant #DMS-9022140). The second author was also supported by NSF grant #DMS-9700927.

The Bruhat order on W is defined as follows: u ≤ v if and only if there exist t_{1}, …, t_{r} ∈ T such that t_{r} … t_{1} u = v and ℓ(t_{i} … t_{1} u) > ℓ(t_{i−1} … t_{1} u) for i = 1, …, r.

A subgroup W′ of W generated by a subset of T is called a reflection subgroup. The group W′ is again a Coxeter group, with a distinguished set S′ ⊂ W of canonical generators; see [10, 11] or [17, Section 8.2]. We will only be interested in the case where W′ is a dihedral reflection subgroup, i.e., S′ has two elements. A dihedral reflection subgroup is maximal if it is not contained in another such subgroup.

In this paper, we will mostly deal with the case where W is a Weyl group, with the associated root system Φ in a Euclidean space V. The group W acts in V by orthogonal transformations. Each root α ∈ Φ corresponds to an element s_{α} ∈ T, which acts as a reflection with respect to the hyperplane orthogonal to α. Simple roots correspond to the Coxeter generators in S. Dihedral reflection subgroups W′ ⊂ W are in one-to-one correspondence with rank 2 root subsystems Φ′ ⊂Φ. Such a subgroup is maximal if Φ′ is obtained by intersecting Φ with a two-dimensional plane. Canonical generators of W′ correspond to the simple roots of Φ′, i.e., to indecomposable positive roots in this subsystem.

Let W′ be a dihedral reflection subgroup of order 2k. Its canonical generators a and b satisfy \underbrace{ababa ⋯}_{k} = \underbrace{babab ⋯}_{k}. Thus the set of reflections T′ = T ∩ W′ consists

of k elements a, aba, ababa, …, babab, bab, b.

Let w_{o} be the longest element in W, and denote N = ℓ(w_{o}) = |T |. Following M. Dyer [13], we say that a bijection φ : T → {1, …, N} is a reflection ordering if, for any dihedral reflection subgroup W′ with canonical generators a and b, the sequence

φ(a), φ(aba), φ(ababa), …, φ(babab), φ(bab), φ(b)

is either increasing or decreasing. (It is enough to require this for every maximal dihedral subgroup.) Reflection orderings are in bijective correspondence with reduced decompositions of w_{o}, viz., φ is a reflection ordering if and only if there exists a reduced decomposition w_{o} = s_{1} … s_{N} such that

(2.1)  φ^{−1}(j) = s_{N}s_{N−1} … s_{j+1}s_{j}s_{j+1} … s_{N−1}s_{N}

for j = 1, … N. (See [13, Proposition 2.13].)

Definition 2.1. A family {R_{τ} }_{τ∈T} of elements of a monoid is called an (extensible) solution to the Yang-Baxter equations for W if for any dihedral reflection subgroup W′ of W with canonical generators a and b, we have

(2.2)  R_{a}R_{aba}R_{ababa} ⋯ R_{bab}R_{b} = R_{b}R_{bab} ⋯ R_{ababa}R_{aba}R_{a} .

In particular, if a, b ∈ T and ab = ba, then (2.2) becomes R_{a}R_{b} = R_{b}R_{a}.

The collection {R_{τ} }_{τ∈T} satisfying the Yang-Baxter equations (2.2) is sometimes called an (extensible) R-matrix (of the corresponding type).

Definition 2.1 makes sense for any (even infinite) Coxeter group. In the case of a Weyl group, equations (2.2), stated case by case in terms of the root system, were given by I. V. Cherednik (implicit in [7] and explicit in [8, Definition 2.1a]), along with a number of solutions. For example, the Yang-Baxter equation for a type A_{2} dihedral subgroup with canonical generators s_{α} and s_{β} can be written in the form R_{s_{α}}R_{s_{α+β}}R_{s_{β}} = R_{s_{β}}R_{s_{α+β}}R_{s_{α}} . Notice that the equations (2.2) do not depend on the choice of the root system; thus the type B_{n} and type C_{n} systems of Yang-Baxter equations are exactly the same.

Remark 2.2. The above definition has a weaker version (cf. Cherednik [8, Definition 2.2]), in which we only ask for (2.2) to be satisfied for every maximal dihedral subgroup. (This distinction is only relevant in non-simply-laced cases.) The stronger condition in Definition 2.1, however not needed for the general “Yang-Baxter machinery” to work, will actually be satisfied by all solutions constructed in this paper.

For the type A_{n−1} , the group W is the symmetric group S_{n}, the set T consists of all transpositions (ij) ∈ S_{n}, and the equations (2.2) are the celebrated (quantum) Yang-Baxter equations (see, e.g., [18]). Let us explain. Let R_{ij} be a shorthand for R_{(ij)} . Then (2.2) becomes

(2.3)  R_{ij}R_{kl} = R_{kl}R_{ij}  if i, j, k, l are distinct;
(2.4)  R_{ij}R_{ik}R_{jk} = R_{jk}R_{ik}R_{ij} if i < j < k.

Example 2.3. The first solution to the Yang-Baxter equations (2.3)–(2.4) was given by C. N. Yang in his pioneering paper [26]. Specifically, Yang observed that the elements

(2.5)  R_{ij} = 1 + \frac{(ij)}{x_{j} − x_{i}}

in the group algebra of the symmetric group S_{n} satisfy (2.3)–(2.4), for any choice of distinct parameters x_{1}, …, x_{n}. This solution generalizes to an arbitrary Weyl group as follows [7, 8]. Let ⟨ , ⟩ be the natural pairing of the vector spaces V and V^{∗}. Choose a vector x ∈ V^{∗} so that ⟨x, α⟩ ≠ 0 for any α ∈ Φ. Also let (κ_{α})_{α∈Φ} be a family of scalars invariant under the action of W on Φ. (In other words, the value of κ_{α} only depends on whether the root α is short or long, assuming Φ is irreducible.) For any positive root α, the corresponding Yang’s R-matrix is then given by

(2.6)  R_{s_{α}} = 1 + \frac{κ_{α} s_{α}}{⟨x, α⟩} .

We will say that two reflection orderings φ and φ′ of T are related by a flip if there is a maximal dihedral subgroup W′ with canonical generators a and b such that

φ(a) = φ′(b), φ(aba) = φ′(bab), …, φ(bab) = φ′(aba), φ(b) = φ′(a) ,

and moreover this sequence is an interval in {1, …, N}, and φ(τ) = φ′(τ) for all reflections τ ∉ W′.

Lemma 2.4. Any two reflection orderings are related by a sequence of flips.

Proof. Every two reduced decompositions of the element w_{o} ∈ W are related by a sequence of elementary Coxeter transformations

(2.7)  s_{1}s_{2} … s_{i} \underbrace{s t s t s …}_{k} s_{j} … s_{N} ⇝ s_{1}s_{2} … s_{i} \underbrace{t s t s t …}_{k} s_{j} … s_{N}

(see, e.g., [17, Section 8.1]). The reflection orderings that correspond to two reduced decompositions in (2.7) via (2.1) are related by a flip with respect to the dihedral subgroup generated by a = w^{−1}sw and b = w^{−1}tw, where w = s_{j} … s_{N}. This subgroup is maximal since it is conjugate to the maximal subgroup generated by simple reflections s and t. □

Lemma 2.4 implies the following useful property of the solutions of the Yang-Baxter equations.

Proposition 2.5. Let {R_{τ} } be a solution of the Yang-Baxter equations for a finite Coxeter group W, and let φ : T → {1, …, N} be a reflection ordering. Then the product R_{φ^{−1}(1)} ⋯ R_{φ^{−1}(N)} does not depend on the choice of φ.

3. Main result

Let k be a field of characteristic 0. Linear operators M_{τ} , τ ∈ T, acting in the group algebra k[W] of a Coxeter group W, are called mixed Bruhat operators if, for some families of scalars {p_{τ} } and {q_{τ} }, we have

(3.1)  M_{τ} (w) = \{ \begin{matrix}p_{τ} τw & if ℓ(τw) > ℓ(w), \\ q_{τ} τw & if ℓ(τw) < ℓ(w), \end{matrix}

for w ∈ W. We will be interested in finding solutions of the Yang-Baxter equations (2.2) that have the form

(3.2)  R_{τ} = 1 + εM_{τ} ,

where M_{τ} is given by (3.1), and ε is a formal variable. Although this problem is naturally stated for any Coxeter group, the family of solutions that we present below is constructed under the assumption that W is a Weyl group, and involves the associated root system Φ. Moreover, the solutions arising from root systems of types B and C (which correspond to the same Weyl group) are going to be different.

To describe our family of solutions of the Yang-Baxter equations (2.2) for a Weyl group W, we will need the following notion. A k-valued function E defined on the set of positive roots Φ^{+} is called multiplicative if, whenever α, β, α+β ∈ Φ^{+}, we have

(3.3)  E(α + β) = E(α) E(β) .

To construct such a function, simply assign arbitrary values to the simple roots, and then extend by multiplicativity. A typical example of a multiplicative function is given by

(3.4)  E(α) = e^{⟨α,x⟩} ,

where x is an arbitrary vector. Notice, however, that (3.4) does not allow for E(α) = 0, a possibility that we do not want to exclude.

Theorem 3.1. Let W be a Weyl group with associated root system Φ. Then the operators R_{τ} given by (3.1)–(3.2) satisfy the quantum Yang-Baxter equations (2.2), provided the parameters p_{τ} and q_{τ} are defined by

(3.5)  p_{s_{α}} = \frac{κ_{α}E_{1}(α)}{E_{1}(α) − E_{2}(α)} ,

(3.6)  q_{s_{α}} = \frac{κ_{α}E_{2}(α)}{E_{1}(α) − E_{2}(α)} ,

where (i) E_{1} and E_{2} are any multiplicative functions on the set of positive roots Φ^{+}

such that E_{1}(α) ≠ E_{2}(α) for every α ∈ Φ^{+}, and (ii) κ_{α} is a scalar whose value only depends on the length of α ∈ Φ^{+}.

The proof of Theorem 3.1 is given in Section 5.

Remark 3.2. The generalized Yang’s solution (2.6) can be obtained from the solution in Theorem 3.1 as a particular limiting case. Let κ_{α} = δ κ_{α}, where δ is a scalar. Fix a vector x ∈ V^{∗}, and set E_{1}(α) = e^{δ⟨α,x⟩} and E_{2}(α) = 1. Making these substitutions into (3.5)–(3.6) and taking the limit as δ → 0, we obtain p_{s_{α}} = q_{s_{α}} = \frac{κ_{α}}{⟨α, x⟩} , which means that the operators lim_{δ→0} M_{s_{α}} act by left multiplication by

\frac{κ_{α}s_{α}}{⟨α, x⟩}, as desired.

4. Rescaling. Quantum Bruhat operators

For the rest of the paper, W is a Weyl group with the root system Φ. We denote by Φ^{+} the set of positive roots.

In this section we discuss rescaling, a very simple yet sometimes helpful way of producing new solutions to the Yang-Baxter equations from the existing ones. We will show how rescaling of the mixed Bruhat operators leads in the limiting case to the construction of “quantum Bruhat operators” for an arbitrary Weyl group W. For the type A, these operators were introduced and studied in [15]; the definition was motivated by the quantum Monk formula [14] (cf. below in this section). In this paper, we are mostly concerned with combinatorial applications of these operators.

Suppose that {M_{τ} }_{τ∈T} is a family of mixed Bruhat operators such that the corresponding operators R_{τ} = 1 + εM_{τ} satisfy the Yang-Baxter equations (2.2). Let {γ_{w}}_{w∈W} be a collection of nonzero scalars. Define the rescaled operators M̃_{τ} by

M̃_{τ} (w) = \frac{γ_{τw}}{γ_{w}} M_{τ} (w) ; (4.1)

then the corresponding operators R̃_{τ} = 1 + εM̃_{τ} are again a solution to (2.2). This follows from the fact that M_{τ} (w) is always a scalar multiple of τw, and therefore M̃_{τ} = ΓM_{τ} Γ^{−1}, where Γ(v) = γ_{v}v for v ∈ W.

Let ht(α) denote the height of a positive root α, i.e., the sum of the coefficients in the expansion of α in the basis of simple roots. We observe that for any scalar h, the function α ↦ h^{ht(α)} is multiplicative.

Let δ ≠ 0 be a scalar parameter (eventually, we are going to take δ → 0), and let α ↦ E(α) be a multiplicative function. Let the parameters p_{τ} = p_{s_{α}} and q_{τ} = q_{s_{α}} of the mixed Bruhat operators M_{τ} be given by (3.5)–(3.6) with

\begin{aligned}κ_{α} & = & δ^{−1} , \\ E_{1}(α) & = & 1 , \\ E_{2}(α) & = & δ^{2ht(α)}E(α) . \end{aligned} (4.2)

Using the notation F ≈ G for lim_{δ→0} F/G = 1, we then obtain:

\begin{matrix}p_{s_{α}} ≈ δ^{−1} , \\ q_{s_{α}} ≈ δ^{2ht(α)−1}E(α) . \end{matrix} (4.3)

Now let the operators M̃_{τ} be given by (4.1) with γ_{w} = δ^{ℓ(w)}. Then

M̃_{τ} (w) = δ^{ℓ(τw)−ℓ(w)}M_{τ} (w) .

Combining this with (4.3) and (3.1) yields

(4.4)  M̃_{s_{α}}(w) ≈ \{ \begin{matrix}δ^{ℓ(s_{α}w)−ℓ(w)−1} s_{α}w & if ℓ(s_{α}w) > ℓ(w) ; \\ δ^{ℓ(s_{α}w)−ℓ(w)+2ht(α)−1}E(α) s_{α}w & if ℓ(s_{α}w) < ℓ(w) . \end{matrix}

In what follows, we will make use of the lemmas below.

Lemma 4.1. Any reflection τ has a symmetric reduced decomposition of the form τ = s_{1}s_{2} ⋯ s_{k−1}s_{k}s_{k−1} ⋯ s_{1} .

Proof. Induction on ℓ(τ). Note that the length of any reflection is odd. The statement of the lemma is obviously true when ℓ(τ) = 1. If ℓ(τ) ≥ 3, find a simple reflection s = s_{α} ≠ τ such that ℓ(sτ) = ℓ(τs) < ℓ(τ). Then 0 > τ(α) ≠ α, implying sτ(α) < 0. Hence ℓ(sτs) < ℓ(sτ) < ℓ(τ). By the inductive hypothesis, sτs posesses a symmetric reduced decomposition. It remains to add s on both sides of it. □

Lemma 4.2. Suppose that positive roots α and γ and a simple root β are such that α = s_{β}(γ) and ℓ(s_{α}) > ℓ(s_{γ}). Then α = mβ + γ, for a positive integer m. Moreover, m = 1 in the case of a simply-laced root system.

Proof. Note that ℓ(s_{α}) > ℓ(s_{γ}) ⟺ ℓ(s_{γ}s_{β}) > ℓ(s_{γ}) ⟺ s_{γ}(β) > 0 . It is therefore enough to verify the statement of the lemma for a rank two root system. (The only option in the simply-laced case is A_{2}.) The verification is straightfoward. □

Lemma 4.3. For any positive root α, we have ℓ(s_{α}) ≤ 2ht(α)−1. In the case of a simply-laced root system (the ADE case), ℓ(s_{α}) = 2ht(α)−1 for any positive root α.

Proof. Choose a symmetric reduced decomposition for s_{α} (cf. Lemma 4.1):

s_{α} = s_{1}s_{2} ⋯ s_{k−1}s_{k}s_{k−1} ⋯ s_{1} ,

and let β_{1}, …, β_{k} be the simple roots (not necessarily distinct) corresponding to the reflections s_{1}, …, s_{k}, respectively. Repeatedly applying Lemma 4.2, we obtain

\begin{aligned}α & = s_{1} ⋯ s_{k−1}(β_{k}) = s_{1} ⋯ s_{k−2}(m_{k−1}β_{k−1} + β_{k}) = ⋯ \\ & = m_{1}β_{1} + ⋯ + m_{k−1}β_{k−1} + β_{k} , \end{aligned}

where the coefficients m_{i} are positive integers. (In the simply-laced case, m_{i} = 1 for all i.) Thus ht(α) = (m_{1} + ⋯ + m_{k−1} + 1) ≥ k, while ℓ(s_{α}) = 2k − 1. □

By Lemma 4.3, both exponents of δ in (4.4) are nonnegative. Letting δ → 0, we obtain the quantum Bruhat operators Q_{τ} = lim_{δ→0} M̃_{τ} given by

(4.5)  Q_{s_{α}}(w) = \{ \begin{matrix}s_{α}w & if ℓ(s_{α}w) = ℓ(w) + 1 ; \\ E(α) s_{α}w & if ℓ(s_{α}w) = ℓ(w) − 2ht(α) + 1; \\ 0 & otherwise . \end{matrix}

In view of Lemma 4.3, the condition in the second line of (4.5) is equivalent to the pair of conditions ℓ(s_{α}w) = ℓ(w) − ℓ(s_{α}) and ℓ(s_{α}) = 2ht(α) − 1. The latter condition is redundant in the case of a simply-laced root system.

Since the operators Q_{τ} were obtained from the mixed Bruhat operators of Theorem 3.1 by specializing parameters, rescaling, and taking a limit, we have arrived at the following result.

Corollary 4.4. Let {Q_{τ} }_{τ∈T} be the quantum Bruhat operators defined by (4.5). Then the operators R_{τ} = 1 + εQ_{τ} satisfy the Yang-Baxter equations (2.2).

For the type A, it was noted in [15] that the operators Q_{τ} satisfy the classical Yang-Baxter equation, which is a slightly weaker statement than Corollary 4.4.

We will now briefly explain the connection between our quantum Bruhat operators and the quantum cohomology of the generalized flag manifold G/B. Here G is a semisimple connected complex Lie group associated with the dual root system Φ^{∨}, and B is a Borel subgroup in G. For each element w ∈ W, let [w] denote the Schubert class

[w] = [ \overline{(Bw^{−1}B)/B}] ∈ H^{2ℓ(w)}(G/B, ℤ) ,

viewed as an element of the small quantum cohomology ring QH^{∗}(G/B, ℤ). (The reader is referred to [16, 14] and references therein for relevant background.)

Let ℤ[q] denote the polynomial ring generated by the deformation parameters of the quantum cohomology. The map w ↦ [w] extends to a linear isomorphism ℤ[q][W] → QH^{∗}(G/B); for this isomorphism, we will use the same notation a ↦ [a].

The Coxeter generators s ∈ S correspond to the special Schubert classes [s]. Over ℤ[q], these classes generate the quantum cohomology ring.

Let the quantum Bruhat operators Q_{s_{α}} be given by (4.5), with the multiplicative function α ↦ E(α) defined by setting its values at simple roots to the corresponding deformation parameters of QH^{∗}(G/B). Then the “quantum Monk formula” for quantum multiplication of an arbitrary Schubert class [w] by a special Schubert class [s] can be written as

(4.6)  [w] ∗ [s] = ∑_{α>0} ⟨ω_{s}, α⟩ [Q_{s_{α}}(w)] ,

where ω_{s} denotes the fundamental weight corresponding to s. Equivalently,

(4.7) [w]∗[s] = ∑_{α>0} ; ℓ(ws_{α})=ℓ(w)+1⟨ω_{s}, α⟩ [ws_{α}] +  ∑_{α>0} ; ℓ(ws_{α})=ℓ(w)−2ht(α)+1⟨ω_{s}, α⟩ E(α) [ws_{α}] ,

For the type A case, formula (4.7) was obtained in [14]. For a general type, it was given by D. Peterson (reproduced in [6], without proof).

5. Proof of Theorem 3.1

5.1. Cosets modulo dihedral reflection subgroups. As a prerequisite for our proofs, we will need to understand the combinatorics of cosets modulo dihedral reflection subgroups, viewed as subposets of the Bruhat order. The following statement is known to hold for any Coxeter group (see Dyer [11]); in the special case of a Weyl group, it has a simple proof provided below.

Lemma 5.1. Let W′ be a reflection subgroup of W, and let S′ be its set of canonical generators. Then the Bruhat order on W′ (viewed as a Coxeter group with generating set S′) coincides with the partial order induced from the Bruhat order on W.

The Bruhat order on W′ is isomorphic to the partial order on any coset W′w (induced from the Bruhat order on W). More precisely, W′w has a unique minimal element w̃, and the map w′ ↦w′w̃ is an isomorphism of posets W′ and W′w =W′w̃.

The last statement can be rephrased as saying that for any w′ ∈ W′ and τ ∈ T ∩ W′, we have ℓ(τw′) < ℓ(w′) if and only if ℓ(τw′w̃) < ℓ(w′w̃).

Proof. For a positive root α and w ∈ W, the condition ℓ(s_{α}w) < ℓ(w) is equivalent to w^{−1}(α) < 0. Since the same criterion describes the covering relation in W′, the first part of the lemma follows. To prove the second part, choose w̃ to be the element of minimal length in W′w (if there are several such, pick any). Take any positive root α such that s_{α} ∈ T ∩ W′. Then ℓ(s_{α}w̃) > ℓ(w̃) and therefore w̃^{−1}(α) > 0. Thus w̃^{−1} maps every positive root that corresponds to a reflection in W′ into a positive root (and every negative into a negative). Hence

\begin{matrix}ℓ(s_{α}w′) < ℓ(w′) ⟺ (w′)^{−1}(α) < 0 ⟺ \\ ⟺ w̃^{−1}(w′)^{−1}(α) < 0 ⟺ ℓ(s_{α}w′w̃) < ℓ(w′w̃) , \end{matrix}

proving the last claim of the lemma. It then follows that w̃ is indeed the unique minimal element of the coset W′w. □

Let W′ be a dihedral reflection subgroup of W. (Thus W′ is of type A_{1} × A_{1} , A_{2} , B_{2} , or G_{2} .) Our goal is to check the Yang-Baxter equation (2.2) corresponding to W′ for the mixed Bruhat operators R_{τ} , assuming some special choice of parameters p_{τ} and q_{τ} . Notice that for any choice of parameters, the operators involved in that particular equation leave each subspace k[W′w] (the span of the right coset W′w) invariant. Thus the operators R_{τ} satisfy the equation in question if and only if so do the restrictions of these operators onto each of these invariant subspaces. In fact, it is enough to just consider the restrictions onto k[W′], for the following reason: the second part of Lemma 5.1 implies that for a coset W′w with the minimal element w̃, the linear isomorphism k[W′] → k[W′w] defined by w′ ↦ w′w̃ intertwines the actions of the operators R_{τ} on k[W′] and k[W′w], respectively.

Thus the verification of the Yang-Baxter equation associated with W′ for the mixed Bruhat operators R_{τ} boils down to verifying this equation for the restrictions of the operators participating in this particular equation onto the invariant subspace k[W′] (which has dimension 4, 6, 8, or 12). The action of these operators on k[W′] is in turn determined by the first part of Lemma 5.1: they act on k[W′] as if W′ were the whole Weyl group.

The case of W′ of type A_{1} ×A_{1} is easily verified: one checks directly that, for any choice of parameters, the mixed Bruhat operators R_{τ} and R_{σ} commute whenever the reflections τ and σ do. Thus we only need to take care of (2.2) in the cases where both sides involve at least three factors.

Let us summarize.

Proposition 5.2. The mixed Bruhat operators R_{τ} satisfy the Yang-Baxter equations (2.2) if and only if, for any reflection subgroup W′ ⊂ W of type A_{2} , B_{2} , or G_{2} , the corresponding Yang-Baxter equation is satisfied by the restrictions of the operators involved in that equation onto the invariant subspace k[W′].

Thus to prove Theorem 3.1, it remains to do so for W of types A_{2} , B_{2} , and G_{2} .

5.2. Type A_{2}. Suppose that W is the symmetric group S_{3} , and let a and b be its canonical Coxeter generators. The Bruhat order on W is given in Figure 1.

[figure: e; aba; a; ba; b; ab]

Figure 1. The Bruhat order on a reflection subgroup of type A_{2}

We should verify that the operators R_{τ} defined by (3.1)–(3.2) satisfy the quantum Yang-Baxter equation

(5.1)  R_{a}R_{aba}R_{b} = R_{b}R_{aba}R_{a}

(cf. (2.4)), provided the parameters p_{τ} and q_{τ} are given by (3.5)–(3.6). Substituting R_{τ} = 1+εM_{τ} , we observe that the terms of degrees 0 and 1 in ε are clearly the same on both sides of (5.1). Equating the quadratic terms gives the classical Yang-Baxter equation [18]

(5.2)  [M_{a} , M_{b}] = [M_{b} , M_{aba}] + [M_{aba} , M_{a}]

(here [A, B] = AB − BA stands for the commutator), while equating the cubic terms gives the quantum Yang-Baxter equation for the M_{τ}:

(5.3)  M_{a}M_{aba}M_{b} = M_{b}M_{aba}M_{a} if i < j < k.

Thus we have to check (5.2) and (5.3).

In the special case under consideration, the operators M_{a}, M_{b}, and M_{aba} = M_{bab} are readily computed from the definition (3.1). Specifically, in the linear basis of k[W] formed by the elements e, a, b, ab, ba, aba (in this order), they are given by the following matrices:

\begin{matrix}M_{a} = [ \begin{matrix}0 & q_{a} & 0 & 0 & 0 & 0 \\ p_{a} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & q_{a} & 0 & 0 \\ 0 & 0 & p_{a} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & q_{a} \\ 0 & 0 & 0 & 0 & p_{a} & 0 \end{matrix} ] , M_{b} = [ \begin{matrix}0 & 0 & q_{b} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & q_{b} & 0 \\ p_{b} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & q_{b} \\ 0 & p_{b} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & p_{b} & 0 & 0 \end{matrix} ] , \\ M_{aba} = [ \begin{matrix}0 & 0 & 0 & 0 & 0 & q_{aba} \\ 0 & 0 & 0 & q_{aba} & 0 & 0 \\ 0 & 0 & 0 & 0 & q_{aba} & 0 \\ 0 & p_{aba} & 0 & 0 & 0 & 0 \\ 0 & 0 & p_{aba} & 0 & 0 & 0 \\ p_{aba} & 0 & 0 & 0 & 0 & 0 \end{matrix} ] . \end{matrix} (5.4)

Substituting (5.4) into (5.2), we obtain, upon simplifications, the following system of equations:

\{ \begin{matrix}−q_{a}q_{b} + p_{b}q_{aba} + q_{aba}q_{a} & = & 0 ; \\ q_{a}q_{b} − q_{b}q_{aba} − q_{aba}p_{a} & = & 0 ; \\ p_{a}q_{b} − q_{b}p_{aba} − q_{aba}p_{a} & = & 0 ; \\ −q_{a}p_{b} + p_{b}q_{aba} + p_{aba}q_{a} & = & 0 ; \\ p_{a}p_{b} − q_{b}p_{aba} − p_{aba}p_{a} & = & 0 ; \\ −p_{a}p_{b} + p_{b}p_{aba} + p_{aba}q_{a} & = & 0 . \end{matrix} (5.5)

Making the same substitution into (5.3), we obtain a single equation q_{a}p_{aba}q_{b} = p_{a}q_{aba}p_{b}, which actually follows from (5.5); indeed, multiply the first equation in (5.5) by p_{aba}, the last one—by q_{aba}, and subtract.

It remains to check that (3.5)–(3.6) imply (5.5). First we note that all roots have the same length, so we may drop the subscript α in κ_{α}. Secondly, subtracting (3.6) from (3.5) yields

(5.6)  p_{τ} = q_{τ} + κ .

When we substitute p_{a} = q_{a} + κ, p_{b} = q_{b} + κ, and p_{aba} = q_{aba} + κ into the system of equations (5.5), it reduces to the single equation

(5.7)  q_{aba}(q_{a} + q_{b} + κ) = q_{a}q_{b} .

Let α and β be the positive roots corresponding to a and b, respectively. Then (5.7) becomes q_{s_{α+β}}(q_{s_{α}} + q_{s_{β}} + κ) = q_{s_{α}}q_{s_{β}} . Substituting (3.6) into this equation, we obtain

\begin{matrix}\frac{E_{2}(α+β)}{E_{1}(α+β)−E_{2}(α+β)} & (\frac{E_{2}(α)}{E_{1}(α)−E_{2}(α)} + \frac{E_{2}(β)}{E_{1}(β)−E_{2}(β)} + 1) \\ = \frac{E_{2}(α)}{E_{1}(α)−E_{2}(α)} \frac{E_{2}(β)}{E_{1}(β)−E_{2}(β)} , \end{matrix}

which is routinely checked using the fact that E_{1} and E_{2} are multiplicative (cf. (3.3)).

This completes the proof of Theorem 3.1 for the type A_{2} , and therefore for any “simply-laced” type.

It is possible to use equations (5.5) to provide a complete (albeit cumbersome) parametric description of all solutions of the Yang-Baxter equations of, say, type A. On the other hand, once we impose some relatively weak “nondegeneracy” restrictions on the parameters q_{τ} , the solution given by (3.5)–(3.6) becomes exhaustive. We state the corresponding result below, omitting a straightforward proof.

Proposition 5.3. Let W be a Weyl group of type A, D, or E. Let {q_{τ} }_{τ∈T} be a family of scalar parameters, let κ ∈ k be a constant, and let p_{τ} = q_{τ} + κ. Then the following are equivalent:

(a) the mixed Bruhat operators R_{τ} defined by (3.1)–(3.2) satisfy the Yang-Baxter equations (2.2);

(b) for any reflection subgroup W′ ⊂ W of type A_{2} with canonical generators a and b, we have (5.7);

(c) the parameters q_{τ} are given by (3.6), with the multiplicative functions E_{1} and E_{2} defined by setting E_{1}(α) = p_{s_{α}} and E_{2}(α) = q_{s_{α}} for every simple root α.

5.3. Types B_{2} and G_{2}. The proof in these cases will be similar to the type A_{2} . We begin by observing that formulas (3.5)–(3.6) imply

(5.8)  p_{s_{γ}} = q_{s_{γ}} + κ_{γ} , γ ∈ Φ^{+} ;

recall that κ_{γ} only depends on whether root γ is short or long; cf. (5.6).

Let a and b be the canonical generators of W. If W is of type B_{2} , then T = {a, aba, bab, b}. Using the elements e, a, b, ba, ab, aba, bab, abab (in this order) as a basis for k[W], we obtain the matrices

M_{a} = [ \begin{matrix}0 & q_{a} & 0 & 0 & 0 & 0 & 0 & 0 \\ p_{a} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & q_{a} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & q_{a} & 0 & 0 \\ 0 & 0 & p_{a} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & p_{a} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & q_{a} \\ 0 & 0 & 0 & 0 & 0 & 0 & p_{a} & 0 \end{matrix} ] , M_{b} = [ \begin{matrix}0 & 0 & q_{b} & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & q_{b} & 0 & 0 & 0 & 0 \\ p_{b} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & p_{b} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & q_{b} & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & q_{b} \\ 0 & 0 & 0 & 0 & p_{b} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & p_{b} & 0 & 0 \end{matrix} ] ,

and, in a similar way, the matrices M_{aba} and M_{bab}. Substituting these matrices into the type B_{2} Yang-Baxter equation

(1 + M_{a})(1 + M_{aba})(1 + M_{bab})(1 + M_{b}) = (1 + M_{b})(1 + M_{bab})(1 + M_{aba})(1 + M_{a}),

we obtain a system of equations for the 8 parameters p_{τ} and q_{τ} corresponding to τ ∈ T. Once we make the substitution (5.8), this system of equations collapses into the single equation

(5.9)  q_{a}q_{b} = q_{a}q_{aba} + q_{aba}q_{bab} + q_{bab}q_{b} + κ_{α}q_{aba} + κ_{β}q_{bab} ,

where, as before, α and β are the positive roots corresponding to a and b, respectively. Note that equation (5.9) is invariant under interchanging a and b (while simultaneously interchanging α and β). Therefore without loss of generality we may assume that α is short and β is long. Then aba and bab correspond to positive roots 2α + β (long) and α + β (short), respectively. Substituting (3.6) into (5.9) and factoring out κ_{α}κ_{β} , we obtain

\frac{E_{2}(α)}{E_{1}(α)−E_{2}(α)} \frac{E_{2}(β)}{E_{1}(β)−E_{2}(β)}
= \frac{E_{2}(α)}{E_{1}(α)−E_{2}(α)} \frac{E_{2}(2α+β)}{E_{1}(2α+β)−E_{2}(2α+β)} + \frac{E_{2}(2α+β)}{E_{1}(2α+β)−E_{2}(2α+β)} \frac{E_{2}(α+β)}{E_{1}(α+β)−E_{2}(α+β)}
+ \frac{E_{2}(α+β)}{E_{1}(α+β)−E_{2}(α+β)} \frac{E_{2}(β)}{E_{1}(β)−E_{2}(β)} + \frac{E_{2}(2α+β)}{E_{1}(2α+β)−E_{2}(2α+β)} + \frac{E_{2}(α+β)}{E_{1}(α+β)−E_{2}(α+β)} ,

which is easily checked using (3.3).

For the type G_{2} , we use (5.8) to express everything in terms of the 6 parameters q_{τ} and the 2 parameters κ_{γ} (for the short and long roots, respectively). Making a substitution into the Yang-Baxter equation of type G_{2} , we obtain two equations

\begin{matrix}q_{a}q_{b} = q_{a}q_{aba} + q_{aba}q_{ababa} + q_{ababa}q_{babab} + q_{babab}q_{bab} + q_{bab}q_{b} \\ +κ_{α}q_{aba} + κ_{α}q_{babab} + κ_{β}q_{bab} + κ_{β}q_{ababa} \end{matrix} (5.10)

and

\begin{matrix}−q_{a}q_{bab} + q_{a}q_{ababa} − q_{b}q_{aba} + q_{b}q_{babab} + q_{aba}q_{babab} + q_{bab}q_{ababa} \\ +q_{a}q_{b}q_{aba}q_{bab} − q_{a}q_{b}q_{aba}q_{ababa} − q_{a}q_{b}q_{bab}q_{babab} − q_{a}q_{b}q_{ababa}q_{babab} \\ +q_{a}q_{aba}q_{bab}q_{babab} + q_{b}q_{bab}q_{ababa}q_{babab} + q_{b}q_{aba}q_{bab}q_{ababa} \\ +q_{a}q_{aba}q_{ababa}q_{babab} + q_{aba}q_{bab}q_{ababa}q_{babab} \\ +κ_{α}(q_{ababa} − q_{a}q_{b}q_{babab} + q_{b}q_{aba}q_{bab} + q_{a}q_{aba}q_{babab} \\ +q_{aba}q_{bab}q_{babab} + q_{aba}q_{ababa}q_{babab}) \\ +κ_{β}(q_{babab} − q_{a}q_{b}q_{ababa} + q_{a}q_{aba}q_{bab} + q_{b}q_{bab}q_{ababa} \\ +q_{aba}q_{bab}q_{ababa} + q_{bab}q_{ababa}q_{babab}) \\ +κ_{α}^{2}q_{aba}q_{babab} + κ_{α}κ_{β}q_{aba}q_{bab} + κ_{β}^{2}q_{bab}q_{ababa} = 0 . \end{matrix} (5.11)

Similarly to the cases A_{2} and B_{2} , we then verify these identities using the substitution (3.6) (preferably with the help of a computer). □

6. Tilted Bruhat orders

We will now apply the results of Section 4 to the combinatorics of the Weyl group W. The following definition is motivated by the formula (4.5) for the quantum Bruhat operators. As before, Φ is a root system associated with W, and Φ^{+} denotes the set of positive roots.

Definition 6.1. Let D_{Φ} denote the directed graph whose vertices are the elements of W, and whose edges are of the form (u, s_{α}u), where u ∈ W, α ∈ Φ^{+}, and either ℓ(s_{α}u) = ℓ(u) + 1 or ℓ(s_{α}u) = ℓ(u) − 2ht(α) + 1.

Note that the digraph D_{Φ} depends on the root system Φ (and on the choice of the positive system Φ^{+} ⊂ Φ), not just on the Weyl group W. Thus, for example, digraphs of types B_{n} and C_{n} corresponding to dual root systems with the same Weyl group will be different.

Because of Lemma 4.3, the condition ℓ(s_{α}u) = ℓ(u)−2ht(α)+1 in Definition 6.1 is equivalent to ℓ(u) − ℓ(s_{α}u) = ℓ(s_{α}) = 2ht(α) − 1. We also remark that D_{Φ} is the directed graph with vertex set W whose adjacency matrix is the matrix of the operator ∑_{τ} Q_{τ} , where the Q_{τ} are given by (4.5) with E(α) = 1 for all α.

Once a reflection ordering φ for W is chosen, we label the edges of D_{Φ} by assigning label φ(τ) to an edge (u, v) with v = τu. We will write u →^{m} v to denote that (u, v) is an edge in D_{Φ} labelled by m.

Example 6.2. Consider a Weyl group of type B_{2} . This is the first instance where the condition ℓ(s_{α}) = 2ht(α) − 1 comes into play. Let a and b be the generators of W that correspond to the simple roots α (short) and β (long), respectively. Then the reflections a, b, and bab satisfy this condition, while aba does not (see Figure 2). The resulting graph D_{Φ}, for the reflection ordering a < aba < bab < b, is shown in Figure 3. Note that we disallow down-directed edges that correspond to multiplying by aba (on the left).

[figure: \begin{matrix}ht(α) = 1 \\ ℓ(a) = 1 \end{matrix}; \begin{matrix}ht(2α + β) = 3 \\ ℓ(aba) = 3 \end{matrix}; \begin{matrix}ht(α + β) = 2 \\ ℓ(bab) = 3 \end{matrix}; \begin{matrix}ht(β) = 1 \\ ℓ(b) = 1 \end{matrix}]

Figure 2. Root system B_{2}

[figure: e; a; ba; aba; b; ab; bab; w_{o}; 1; 4; 4; 1; 1; 4; 4; 1; 3; 2; 2; 3; 3; 3; 1 a; 2 aba; 3 bab; 4 b]

Figure 3. The digraph D_{Φ} for W of type B_{2}

Definition 6.3. For u, v ∈ W, let ℓ(u, v) denote the length of the shortest directed path in D_{Φ} from u to v. In particular, v ↦ ℓ(e, v) = ℓ(v) is the usual length function; moreover, ℓ(u, v) = ℓ(v) − ℓ(u) whenever u ≤ v in the Bruhat order. The tilted Bruhat order B_{Φ}(u) is the graded partial order on W defined by

w_{1} ⪯_{u} w_{2} ⟺^{def} ℓ(u, w_{1}) + ℓ(w_{1}, w_{2}) = ℓ(u, w_{2}) .

In other words, w_{1} ⪯_{u} w_{2} if and only if there exists a shortest path in D_{Φ} from u to w_{2} that passes through w_{1} .

We note that B_{Φ}(e) is the usual Bruhat order on W.

Any choice of reflection ordering induces edge labelling of the Hasse diagram of B_{Φ}(u) inherited from D_{Φ}. Figure 4 shows an example of a tilted Bruhat order which is not pure (i.e., does not have a unique maximal element ˆ1); here W is of type B_{2} , and we use the same conventions as in Figure 3.

A nonempty interval [w_{1} , w_{2}] in B_{Φ}(u) is called a tilted Bruhat interval between w_{1} and w_{2} . This interval does not depend on the choice of u (as long as w_{1} ⪯_{u} w_{2}), but on w_{1} and w_{2} alone, since

[w_{1} , w_{2}] = {w ∈ W : ℓ(w_{1}, w) + ℓ(w, w_{2}) = ℓ(w_{1} , w_{2})} ,

and moreover the induced partial order on [w_{1} , w_{2}] is independent on the choice of u, as long as w_{1} ⪯_{u} w_{2} . More precisely, [w_{1} , w_{2}] is the graded poset whose Hasse diagram is the minimal subgraph of D_{Φ} containing all directed paths from w_{1} to w_{2}

[figure: a; ba; ab; e; aba; bab; b; w_{o}; 1; 2; 4; 1; 2; 3; 4; 4; 1; 4; 1]

Figure 4. Tilted Bruhat order B_{Φ}(a) for W of type B_{2}

that have the smallest possible length. Note that this definition applies for any pair w_{1} , w_{2} ∈ W. In the special case where w_{1} ≤ w_{2} (in the ordinary Bruhat order), the notion of a tilted Bruhat interval specializes to the usual notion of an interval in the Bruhat order.

Figure 5 shows the tilted Bruhat intervals [ab, a] and [w_{o} , e] for W of type B_{2} , with the same notation as before. (The first of these intervals coincides with the tilted Bruhat order B_{Φ}(ab).) Notice that [w_{o} , e] is by no means dual to [e, w_{o}]=W.

[figure: ab; b; aba; bab; ba; e; w_{o}; a; 4; 3; 1; 3; 4; 1; 3; 4; 1; 3; 1; 4; w_{o}; a; bab; e; 3; 1; 1; 3]

Figure 5. Tilted Bruhat intervals [ab, a] and [w_{o}, e]

Our main combinatorial result is an extension of certain fundamental property of Bruhat orders to their “tilted analogues” introduced in Definition 6.3.

Theorem 6.4. Fix a reflection ordering φ in a Weyl group W.

1. For any pair of elements u, v ∈ W, there is a unique path from u to v in the directed graph D_{Φ} such that its sequence of labels is strictly increasing (resp. strictly decreasing).

2. The unique label-increasing (resp. label-decreasing) path from u to v in D_{Φ} has the smallest possible length ℓ(u, v). Moreover it is lexicographically minimal (resp. lexicographically maximal) among all shortest paths from u to v.

The proof of Theorem 6.4 is given at the end of this section.

In the terminology of [3], Theorem 6.4 asserts that the tilted Bruhat order (hence any tilted Bruhat interval [u, v]) is EL-shellable (hence CL-shellable), with the EL-shelling provided by any reflection ordering (and therefore by its reversal as well). In the case u = e, Theorem 6.4 specializes to EL-shellability theorem for the ordinary Bruhat orders, a result conjectured by Björner and proved by Dyer [13, Proposition 4.3]. (Dyer’s theorem holds for an arbitrary Coxeter group, with an appropriate generalization of the concept of a reflection ordering.)

Shellability can be used to compute the Möbius function [21] of the Bruhat order (ordinary or tilted). Recall [22] that a finite graded poset with ˆ0 and ˆ1 (resp. with ˆ0) is called Eulerian (resp. lower Eulerian) if its Möbius function is given by

μ(x, y) = (−1)^{rank(y)−rank(x)}

for any x ≤ y. This is equivalent to requiring that any interval [x, y] contains equal number of elements of even and odd rank.

A well known theorem of Verma [24, 25] (cf. also [2, 9, 19]) asserts that any interval in the Bruhat order of any Coxeter group is Eulerian. To our knowledge, no simple proof of this result is known, except for the special case x = e (see Lascoux [20, Lemma 1.13]). The story of Verma’s theorem is told in [17, p. 176]. Remarkably, it can be strengthened as follows: any Bruhat interval is actually a face poset of a shellable regular CW sphere (see Björner [1, Theorem 5.1] and Björner-Wachs [2, Theorem 4.2]); hence it is also Cohen-Macaulay [4].

All the statements mentioned in the preceding paragraph are implied by Dyer’s shellability theorem [13, Proposition 4.3]. Not surprisingly, our Theorem 6.4 can be used to extend these results to the tilted case.

Corollary 6.5. Each tilted Bruhat order B_{Φ}(u) of a Weyl group W is a lexicographically shellable lower Eulerian poset. As a consequence, any tilted Bruhat interval is a face poset of a shellable regular CW sphere. In particular, it is Eulerian and Cohen-Macaulay.

Proof. By [1, Proposition 4.5], Theorem 6.4 implies that [u, v] is a face poset of a regular CW sphere. Such posets are known to be both Eulerian and Cohen-Macaulay; see, e.g., Stanley [22, Section 1]. □

The Eulerian property can also be deduced directly from Theorem 6.4 as follows. By a simple counting argument (cf. [4, Corollary 2.3]), the values of the Möbius function can be computed from an EL-shelling by

μ(u, v) = (−1)^{rank(y)−rank(x)} · (number of label-decreasing chains from u to v) .

In our case, there is exactly one such chain, and the Eulerian property follows.

Proof of Theorem 6.4. We will first prove Part 1 of the theorem. As before, φ is a reflection ordering, N = ℓ(w_{o}), R_{τ} = 1 + εQ_{τ} for τ ∈ T, and the Q_{τ} are given by (4.5) with E(α) = 1.

We are going to eventually prove the following statement, which can be viewed as an algebraic reformulation of Theorem 6.4 (excluding the last statement of the latter).

Proposition 6.6. For any u ∈ W,

(6.1)  R_{φ^{−1}(1)} ⋯ R_{φ^{−1}(N)}(u) = ∑_{v∈W} ε^{ℓ(u,v)} v .

Part 1 of Theorem 6.4 is equivalent to the special case ε = 1 of (6.1), for the following reasons. We have already noted (see comments following Definition 6.1) that (u, v) is an edge in D_{Φ} if and only if v = Q_{τ} (u) for some τ ∈ T, in which case (u, v) is labelled by φ(τ). Thus the identity (6.1), with ε = 1, asserts existence and uniqueness of the label-decreasing path.

Let us denote by T the specialization of the operator R_{φ^{−1}(1)} ⋯ R_{φ^{−1}(N)} obtained by setting ε = 1. By Proposition 2.5 and Corollary 4.4, the operator T does not depend on the choice of reflection ordering φ.

We will identify an element w ∈ W with the linear operator u ↦ wu in k[W]. Let s ∈ S. Then (4.5), with ε = 1, gives Q_{s} = s, implying

(6.2)  (1 + Q_{s})s = 1 + Q_{s} .

Since there exists a reduced decomposition of w_{o} that ends in s, there also exists a reflection ordering φ such that φ^{−1}(N) = s (cf. (2.1)). Hence (6.2) implies that

T s = ( ∏_{i=1}^{N−1}(1 + Q_{φ^{−1}(i)})) (1 + Q_{s}) s = T .

It follows that, more generally, T w = T for all w ∈ W. Analogously one shows that wT = T for all w ∈ W. These equations can be interpreted as saying that the matrix of T in the basis W of k[W] is invariant under permutations of rows and columns. Hence there exists a constant c such that, for any u ∈ W,

T (u) = c ∑_{v∈W} v.

On the other hand, it is clear from the definition of the Q_{τ} that the coefficient of w_{o} in T (e) is ≤ 1, where e ∈ W is the identity element. Since c is obviously a positive integer, we conclude that c = 1, and Part 1 is proved.

To prove the rest, we will need the following lemma that generalizes the corresponding result for the ordinary Bruhat order (see, e.g., [13, Lemma 4.1]).

Lemma 6.7. Assume that

(6.3)  u, x, v ∈ W , u →^{k} x →^{l} v , k > l .

Then there exists a unique y ∈ W such that (cf. Figure 6)

(6.4)  u →^{m} y →^{n} v , l < n > m < k .

[figure: u; v; x; y; k; l; m; n; ∧; ∨; <; >]

Figure 6. Tilted Bruhat interval of length 2

Proof. Consider the dihedral group W′ generated by the reflections φ^{−1}(k) and φ^{−1}(l). Define the operators Q_{τ} and R_{τ} as in Theorem 6.4, and write down the Yang-Baxter equation (2.2) for W′, so that the order of the terms in the left-hand side was compatible with the reflection order φ. Thus the sequence of reflections appearing on the left-hand side is label-increasing, while the one in the right-hand side is label-decreasing. Apply the left-hand side to u, and take the coefficient of ε^{2}v. This will be the number of label-decreasing paths in D_{Φ} from u to v that have length 2 and stay within the coset W′u. We know one such path, namely u →^{k} x →^{l} v. By the Yang-Baxter equation, there should also be a label-increasing path of length 2 from u to v that stays within W′u; let us denote it by u →^{m} y →^{n} v. It remains to check that k > m and l < n. These two statements are completely analogous to each other, so we will only show how to prove the first one. Suppose that, on the contrary, k < m. (Obviously, k ≠ m, since otherwise x = y.) Then l < k < m < n, which in particular means that the four reflections labelled by l, k, m, n are all distinct. If W′ is of type A_{2} , this already brings the desired contradiction, since in that case there are only three reflections in W′. If W′ is of type B_{2} , with canonical generators a and b (say, φ(a) < φ(b), then there are four reflections in W′, and therefore l, k, m, n correspond to a, aba, bab, b, respectively. But this would imply that v = a·aba·u = b·bab·u, a contradiction. The remaining case W′ = W = G_{2} is checked directly. □

We can now complete the proof of Theorem 6.4 using an argument borrowed from [13]. Among all shortest paths in D_{Φ} from u to v, let

(6.5)  u = w_{1} → w_{2} → ⋯ → w_{d} = v

be the one whose label sequence is lexicographically minimal. To prove Part 2 of the theorem, we need to show is that this path is label-increasing. Suppose otherwise, i.e., for some i ∈ {2, …, d−1}, we have w_{i−1} →^{k} w_{i} →^{l} w_{i+1} with k > l. (We cannot have k = l since this would create a loop, and the path would not be shortest.) Then, by Lemma 6.7, there exists y ∈ W such that w_{i−1} →^{m} y →^{n} w_{i+1} and m < k. Thus replacing w_{i} by y in (6.5) produces a chain with lexicographically smaller sequence of labels—a contradiction. □

It remains to observe that Proposition 6.6 is a direct corollary of Theorem 6.4.

Acknowledgments

We are grateful to Andrei Zelevinsky for his fair and constructive criticism that brought about a substantial improvement over the original version. We also thank Anders Björner, Alain Lascoux, and Richard Stanley for useful comments and conversations. Part of our work was carried out while the first two authors were participating in the “Combinatorics” program at MSRI.

References

[1] A. Björner, Posets, regular CW complexes and Bruhat order, Europ. J. Combin. 5 (1984), 7–16.

[2] A. Björner and M. Wachs, Bruhat order of Coxeter groups and shellability, Adv. in Math. 43 (1982), 87–100.

[3] A. Björner and M. Wachs, On lexicographically shellable posets, Trans. Amer. Mth. Soc. 277 (1983), 323–341.

[4] A. Björner, A. M. Garsia, and R. P. Stanley, An introduction to Cohen-Macaulay partially ordered sets, in Ordered Sets (I. Rival, ed.), Reidel, 1982, 583–615.

[5] N. Bourbaki, Groupes et algèbres de Lie, Ch. IV-VI, Hermann, Paris, 1968.

[6] J. Carrell, Quantum cohomology of G/P. Notes from three lectures of Dale Peterson, preprint, 5 pp., 1996.

[7] I. V. Cherednik, Factorizing particles on a half line, and root systems, Teoret. Mat. Fiz. 61 (1984), no. 1, 35–44.

[8] I. V. Cherednik, Quantum Knizhnik-Zamolodchikov equations and affine root systems, Commun. Math. Phys. 150 (1992), 109–136.

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

[10] V. V. Deodhar, A note on subgroups generated by reflections in Coxeter groups Arch. Math. 53 (1989), 543–546.

[11] M. Dyer, Reflection subgroups of Coxeter systems, J. Algebra 135 (1990), 57–73.

[12] M. Dyer, On the “Bruhat graph” of a Coxeter system, Comp. Math. 78 (1991), 185–191.

[13] M. Dyer, Hecke algebras and shellings of Bruhat intervals, Comp. Math. 89 (1993), 91–115.

[14] S. Fomin, S. Gelfand, and A. Postnikov, Quantum Schubert polynomials, J. Amer. Math. Soc. 10 (1997), 565–596.

[15] S. Fomin and A. N. Kirillov, Quadratic algebras, Dunkl elements, and Schubert calculus, preprint CRM-2472, April 1997; to appear in Progress in Geometry.

[16] W. Fulton and R. Pandharipande, Notes on stable maps and quantum cohomology, preprint alg-geom/9608011.

[17] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Univ. Press, 1990.

[18] Yang-Baxter equation in integrable systems (M. Jimbo, ed.), Advanced Series in Mathematical Physics 10, World Scientific, 1989.

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

[20] A. Lascoux, Anneau de Grothendieck de la variété de drapeaux, The Grothendieck Festschrift, Vol. III, 1–34, Progr. Math. 88, Birkhäuser, 1990.

[21] G.-C. Rota, On the foundations of combinatorial theory I. Theory of Möbius functions, in: Gian-Carlo Rota on combinatorics, Birkhäuser, 1995, pp. 3–31.

[22] R. P. Stanley, A survey of Eulerian posets, in: Polytopes: abstract, convex and computational, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. 440 (1994), 301–333.

[23] R. P. Stanley, Enumerative Combinatorics, vol. 1, 2nd edition, Cambridge Univ. Press, 1997.

[24] D.-N. Verma, Möbius inversion for the Bruhat order on a Weyl group, Ann. Sci. École Norm. Sup. 4 (1971), 393–398.

[25] D.-N. Verma, A strengthening of the exchange property of Coxeter groups, preprint, 1972.

[26] C. N. Yang, Some exact results for the many-body problem in one dimension with repulsive delta-function interaction, Phys. Rev. Lett. 19 (1967), 1312–1314.

Dipartimento di Matematica, Universitá di Roma “Tor Vergata”, Via della Ricerca Scientifica, 00133 Roma, Italy

   E-mail address: brenti@mat.uniroma2.it

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

   E-mail address: fomin@math.mit.edu

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

   E-mail address: apost@math.mit.edu