Combinatorial formulas for double parabolic
R-polynomials

Justin Lambright and Mark Skandera

Lehigh University, Bethlehem, PA, USA

**Abstract.** The well-known *R*-polynomials in Z[q], which appear in Hecke algebra computations, are closely related to certain *modified R-polynomials* in N[q] whose coefficients have simple combinatorial interpretations. We generalize this second family of polynomials, providing combinatorial interpretations for expressions arising in a much broader class of computations. In particular, we extend results of Brenti, Deodhar, and Dyer to new settings which include parabolic Hecke algebra modules and the quantum polynomial ring.

**Résumé.** Les bien connues polynômes-R en Z[q], qui apparaissent dans les calcules d'algébre de Hecke, sont relationés à certaines polynômes-R modifiés en N[q], dont les coefficients ont simples interprétations combinatoires. Nous généralisons cette deuxième famille de polynômes, fournissant des interprétations combinatoires pour les expressions qui se posent dans une catégorie beaucoup plus vaste de calculs. En particulier, nous étendons des résultats de Brenti, Deodhar, et Dyer à des situations nouvelles, qui comprennent modules paraboliques pour l'algébre de Hecke, et l'anneau des polynômes quantiques.

**Resumen.** Los ilustres polinomios-R en Z[q], que aparecen en los cálculos del álgebra de Hecke, están relacionados con ciertos polinomios-R modificados en N[q], cuyos coeficientes tienen interpretaciones combinatorias sencillas. Generalizamos esta segunda familia de polinomios, proporcionando interpretaciones combinatorias para las expresiones que surgen en una clase de cálculos más amplia. En particular, se amplian unos resultados de Brenti, Deodhar, y Dyer a nuevas situaciones que incluyen los módulos parabólicos del álgebra de Hecke, y el anillo de polinomios cuánticos.

**Keywords:** Immanants, Kazhdan-Lusztig polynomials, quantum groups

# 1 Introduction

An important ingredient in the definition of Kazhdan and Lusztig's basis [KL79] for the Hecke algebra $H_n(q)$ of a Coxeter group $W$ is a map now known as the *bar involution*. Applying this involution to a natural basis of the algebra, one obtains a second basis, related to the first by polynomials $\{R_{u,v}(q) | u, v \in W\}$ in $Z[q]$ now known as *R-polynomials*. Alternatively, one may relate this second basis to the first by polynomials $\{\tilde{R}_{u,v}(q) | u, v \in W\}$ in $N[q]$ which we call *modified R-polynomials*. Coefficients of the modified R-polynomials and their combinatorial interpretations were studied by Brenti [Bre94], [Bre97a], [Bre97b], [Bre98], [Bre02], Deodhar [Deo85], and Dyer [Dye93].

Certain $\mathbb{C}[q^{\frac{1}{2}}, \tilde{q}^{\frac{1}{2}}]$-submodules of $H_n(q)$ called *double parabolic modules* inherit a bar involution from $H_n(q)$, and therefore inherit analogs of *R-polynomials* called *parabolic R-polynomials*. Also belonging
to $\mathbb{Z}[q]$, these parabolic $R$-polynomials appear in numerous papers, yet somehow have not received the modification and combinatorial interpretation granted to their nonparabolic syblings.

Related to the bar involutions on the type-A Hecke algebra and its parabolic modules is another involution on a certain noncommutative polynomial ring $\mathcal{A}(n; q)$ which we call the *quantum polynomial ring*. This last involution, also called the *bar involution*, is an important ingredient in the definition of a certain *dual canonical basis* of the quantum polynomial ring, related by Hopf algebra duality to Kashiwara's [Kas91] and Lusztig's [Lus90] canonical basis of $sl(n, \mathbb{C})$. Again, applying this involution to a natural basis of $\mathcal{A}(n; q)$, one obtains a second basis, related to the first by *inverse R-polynomials* and *inverse parabolic R-polynomials* (equivalently, by modifications of these).

To summarize, we have several algebras with the property that a natural basis and its bar image are related by a transition matrix whose entries are variations of $R$-polynomials. Using an elementary family of bases of $\mathcal{A}(n; q)$, we show that in all cases, the above entries have simple combinatorial interpretations in terms of walks in the Bruhat order. These interpretations enable us to express all double parabolic analogs of $R$-polynomials as sums of the nonparabolic polynomials. In all sections, we work specifically in type A, but many of our results carry over to Hecke algebras of other types.

In Section 2 we review definitions concerning the symmetric group $S_n$ and Hecke algebra $H_n(q)$ of type A. We define the bar involution on $H_n(q)$, $R$-polynomials, and modified $R$-polynomials. We also define double parabolic analogs of these, thus extending one of the two parabolic conventions appearing in the literature. These polynomials are easily seen to be sums of nonparabolic $R$-polynomials and modified $R$-polynomials. In Section 3, we define the quantum polynomial ring $\mathcal{A}(n; q)$, its bar involution, inverse $R$-polynomials, and modified inverse $R$-polynomials. We also define double parabolic analogs of these, thus extending the second of the two parabolic conventions appearing in the literature. These polynomials are *not* easily seen to be sums of nonparabolic inverse $R$-polynomials and modified inverse $R$-polynomials. In Section 4, we consider various bases of the so-called *immanant* subspace of $\mathcal{A}(n; q)$ and provide combinatorial interpretations for the transition matrices relating these to the natural basis of the subspace. These lead to interpretations in Section 5 for all variations of the $R$-polynomials mentioned above, and to our main result which expresses double parabolic inverse $R$-polynomials as sums of nonparabolic inverse $R$-polynomials.

## 2 The symmetric group and Hecke algebra

Let $S_n$ be the Coxeter group of type $A_{n-1}$, i.e., the symmetric group on $n$ letters. $S_n$ is generated by the standard adjacent transpositions $s_1, \dots, s_{n-1}$, subject to the relations

$$ 
\begin{align} 
s_i^2 &= e && \text{for } i = 1, \dots, n-1, \notag \\ 
s_i s_j s_i &= s_j s_i s_j && \text{for } |i-j| = 1, \tag{2.1} \\ 
s_i s_j &= s_j s_i && \text{for } |i-j| \ge 2. \notag 
\end{align} 
$$

A standard action of $S_n$ on rearrangements of the word $1 \cdots n$ is defined by letting $s_i$ swap the letters in positions $i$ and $i+1$,

$$ s_i \circ a_1 \cdots a_n = a_1 \cdots a_{i+1} a_i \cdots a_n. \tag{2.2} $$

For each element $v = s_{i_1} \cdots s_{i_l} \in S_n$, we define the *one-line notation* of $v$ to be the word $v_1 \cdots v_n = v \circ 1 \cdots n$. Thus the one-line notation of the identity permutation $e$ is $12 \cdots n$. Using this convention, the
one-line notation of vw is

$$ (vw)_1 \cdots (vw)_n = v \circ (w \circ 1 \cdots n) = w_{v_1} \cdots w_{v_n}. \qquad (2.3) $$

Let $\ell(w)$ be the minimum length of an expression for $w$ in terms of generators, and let $w_0$ denote the longest word in $\mathfrak{S}_n$. Let $\leq$ denote the Bruhat order on $\mathfrak{S}_n$, i.e., $v \leq w$ if every reduced expression for $w$ contains a reduced expression for $v$ as a subword.

The (Iwahori-)Hecke algebra $H_n(q)$ of $\mathfrak{S}_n$ is the $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-algebra generated by the set of (modified) natural generators, $\tilde{T}_{s_1}, \dots, \tilde{T}_{s_{n-1}}$, subject to the relations

$$ \begin{aligned} \tilde{T}_{s_i}^2 &= (q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}) \tilde{T}_{s_i} + 1 && \text{for } i = 1, \dots, n-1, \\ \tilde{T}_{s_i} \tilde{T}_{s_j} \tilde{T}_{s_i} &= \tilde{T}_{s_j} \tilde{T}_{s_i} \tilde{T}_{s_j} && \text{for } |i-j| = 1, \\ \tilde{T}_{s_i} \tilde{T}_{s_j} &= \tilde{T}_{s_j} \tilde{T}_{s_i} && \text{for } |i-j| \geq 2. \end{aligned} \qquad (2.4) $$

(We follow the notation of [Lus85], using modified generators $\tilde{T}_{s_i}$ instead of the more common generators $T_{s_i} = q^{\frac{1}{2}} \tilde{T}_{s_i}$.) If $s_{i_1} \cdots s_{i_l}$ is a reduced expression for $w \in \mathfrak{S}_n$ we define $\tilde{T}_w = \tilde{T}_{s_{i_1}} \cdots \tilde{T}_{s_{i_l}}$, where $\tilde{T}_e = 1$. It is known that the definition of $\tilde{T}_w$ does not depend upon the choice of a reduced expression for $w$. We shall call the elements $\{\tilde{T}_w \mid w \in \mathfrak{S}_n\}$ the (modified) natural basis of $H_n(q)$. For $u, v \in \mathfrak{S}_n$, we define $\epsilon_{u,v} = (-1)^{\ell(v)-\ell(u)}$ and $q_{u,v} = (q^{\frac{1}{2}})^{\ell(v)-\ell(u)}$.

An involutive automorphism on $H_n(q)$ commonly known as the bar involution is defined by

$$ \overline{q^{\frac{1}{2}}} = q^{\frac{1}{2}}, \quad \tilde{T}_w = (\tilde{T}_{w^{-1}})^{-1}. \qquad (2.5) $$

Taking the bar involution of an element of $H_n(q)$ and expanding in terms of the natural basis [KL79], we have

$$ \overline{\tilde{T}_w} = \sum_{v \leq w} \epsilon_{v,w} q_{v,w}^{-1} R_{v,w}(q) \tilde{T}_v, \qquad (2.6) $$

where $\{R_{v,w}(q) \mid v, w \in \mathfrak{S}_n\}$ are polynomials in $\mathbb{Z}[q]$, which are commonly called R-polynomials. Modifying the R-polynomials by

$$ q_{v,w}^{-1} R_{v,w}(q) = \tilde{R}_{v,w}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}) \qquad (2.7) $$

gives us the modified R-polynomials $\{\tilde{R}_{v,w}(q) \mid v, w \in \mathfrak{S}_n\}$, which belong to $\mathbb{N}[q]$. Thus we may rewrite (2.6) as

$$ \overline{\tilde{T}_w} = \sum_{v \leq w} \epsilon_{v,w} \tilde{R}_{v,w}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}) \tilde{T}_v. \qquad (2.8) $$

Often appearing in the literature are $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-submodules of $H_n(q)$ spanned by sums of natural basis elements corresponding to cosets of $\mathfrak{S}_n$. For a subset $I$ of generators of $\mathfrak{S}_n$, the subgroup $W_I$ of $\mathfrak{S}_n$ generated by $I$ is said to be *parabolic*. Note that we have $W_\emptyset = \{e\}$ and $W_{\{s_1, \dots, s_{n-1}\}} = \mathfrak{S}_n$.

Two parabolic subgroups $W_I$ and $W_J$ partition $\mathfrak{S}_n$ into double cosets of the form $W_I w W_J$. If $J = \emptyset$ or $I = \emptyset$, these cosets are denoted $W_I w$ and $w W_J$, respectively. Thus, ordinary single cosets are special cases of double cosets. It is known that each double coset is an interval in the Bruhat order, containing a
unique maximal element and a unique minimal element. Denote the collections of maximal and minimal coset representatives by $W_+^{I,J}$ and $W_-^{I,J}$, respectively. Denote the longest element of a subgroup $W_I$ by $w_0^I$.

The $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-submodule of $H_n(q)$ corresponding to parabolic subgroups $W_I, W_J$ and their double cosets $W_I w W_J$ is the span of certain double coset sums. For each permutation $w \in W_+^{I,J}$, define the element

$$ \tilde{T}'_{W_I w W_J} = \sum_{v \in W_I w W_J} (-q^{\frac{1}{2}})^{\ell(w) - \ell(v)} \tilde{T}_v. \qquad (2.9) $$

Let $H'_{I,J}$ denote the submodule of $H_n(q)$ spanned by these elements,

$$ H'_{I,J} = \operatorname{span}_{\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]} \{ \tilde{T}'_{W_I w W_J} \mid w \in W_+^{I,J} \}. \qquad (2.10) $$

The bar involution on $H_n(q)$ induces a bar involution on $H'_{I,J}$. Curtis [Cur85] and Du [Du94] showed that the elements $\{\tilde{T}'_{W_I w W_J} \mid w \in W_+^{I,J}\}$ form a basis of $H'_{I,J}$. Expanding this basis in terms of the natural basis, Du showed that we have

$$ \overline{\tilde{T}'_{W_I w W_J}} = \sum_{\substack{v \in W_+^{I,J} \\ v \le w}} (q^{\frac{1}{2}})^{\ell(w) - \ell(v)} R_{v,w}^{I,J} (q^{-1}) \tilde{T}'_{W_I v W_J}, \qquad (2.11) $$

where $\{R_{v,w}^{I,J} \mid v, w \in W_+^{I,J}\}$ are polynomials belonging to $\mathbb{Z}[q]$. When $I = \emptyset$ or $J = \emptyset$, we call these single parabolic R-polynomials and if neither are empty we call them double parabolic R-polynomials. Douglass [Dou90] and Deodhar [Deo87] looked at the single parabolic R-polynomials, while Du was probably the first to mention the double parabolic versions. Applying the bar involution to both sides of (2.9) and comparing terms, one sees that double parabolic R-polynomials are related to ordinary R-polynomials by

$$ R_{u,w}^{I,J}(q) = \sum_{v \in W_I w W_J} R_{v,w}(q). \qquad (2.12) $$

It is often necessary to factor a permutation $w$ in $\mathfrak{S}_n$ in terms of elements of $W_I, W_J$, and a minimal or maximal representative of the coset $W_I w W_J$. For instance, each element $v$ of a single coset $W_I v$ has a unique factorization $v = uw$ with $u \in W_I$ and $v \in W_-^{I,\emptyset}$. Similarly, each element $v$ of a single coset $v W_J$ has a unique factorization $v = wu$ with $u \in W_J$ and $v \in W_-^{\emptyset,J}$. Factorization in double cosets is a bit more complicated. For $v \in W_I w W_J$, there is not always a unique $h \in W_I$ and $k \in W_J$ such that $v = h w k$. On the other hand, we can define a canonical factorization in terms of a third parabolic subgroup of $\mathfrak{S}_n$. For every $u \in W_-^{I,J}$ we define a set of generators

$$ K' = K'(u) = \{s_i \in I \mid s_i u = u s_j \text{ for some } s_j \in J\}, \qquad (2.13) $$

By definition $W_{K'}$ is contained in $W_I$ and thus we can construct single cosets of the form $wW_{K'}$ within $W_I$. As before, there are unique maximal and minimal representatives for each coset $wW_{K'} \subset W_I$. Denote the sets of maximal and minimal coset representatives by $(W_I)^{\emptyset, K'}$ and $(W_I)^{\emptyset, K'}$, respectively. It follows that for $u \in W_-^{I,J}$ each double coset factors as

$$ W_I u W_J = (W_I)^{\emptyset, K'} W_{K'} u W_J. \qquad (2.14) $$
In other words each element $v$ of the double coset $W_I u W_J$ has a unique factorization $v = v_{-}^{I} uv^{J}$ satisfying

$$v_{-}^{I} \in (W_I)^{\emptyset, K'}, \quad v^{J} \in W_J. \qquad (2.15)$$

Furthermore the length of the word is the sum of the lengths of the factors.

## 3 The quantum polynomial ring

For each $n > 0$, let the quantum polynomial ring $\mathcal{A}(n; q)$ be the noncommutative $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{-1}{2}}]$-algebra generated by $n^2$ variables $x = (x_{1,1}, \dots, x_{n,n})$ representing matrix entries, subject to the relations

$$ \begin{aligned} x_{i,\ell}x_{i,k} &= q^{\frac{1}{2}}x_{i,k}x_{i,\ell}, \\ x_{j,k}x_{i,k} &= q^{\frac{1}{2}}x_{i,k}x_{j,k}, \\ x_{j,k}x_{i,\ell} &= x_{i,\ell}x_{j,k}, \\ x_{j,\ell}x_{i,k} &= x_{i,k}x_{j,\ell} + (q^{\frac{1}{2}} - \bar{q}^{\frac{-1}{2}})x_{i,\ell}x_{j,k}, \end{aligned} \qquad (3.1) $$

for all indices $1 \le i < j \le n$ and $1 \le k < \ell \le n$. $\mathcal{A}(n; q)$ often arises in conjunction with the quantum group $\mathcal{O}_q(\mathrm{SL}(n, \mathbb{C}))$. In particular, we have

$$ \mathcal{O}_q(\mathrm{SL}(n, \mathbb{C})) \cong \mathcal{A}(n; q) / (\det_q(x) - 1), \qquad (3.2) $$

where

$$ \det_q(x) = \sum_{w \in \mathfrak{S}_n} (-\bar{q}^{\frac{1}{2}})^{\ell(w)} x_{1,w_1} \cdots x_{n,w_n} \qquad (3.3) $$

is the quantum determinant. Notice that $\mathcal{A}(n; 1)$ is the commutative polynomial ring $\mathbb{C}[x_{1,1}, \dots, x_{n,n}]$.

We can use the relations above to convert any monomial into a linear combination of monomials in lexicographic order. Thus as a $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{-1}{2}}]$-module, $\mathcal{A}(n; q)$ is spanned by monomials in lexicographic order. $\mathcal{A}(n; q)$ has a natural grading by degree,

$$ \mathcal{A}(n; q) = \bigoplus_{r \ge 0} \mathcal{A}_r(n; q), \qquad (3.4) $$

where $\mathcal{A}_r(n; q)$ consists of the homogeneous degree $r$ polynomials within $\mathcal{A}(n; q)$. Furthermore, we may decompose each homogeneous component $\mathcal{A}_r(n; q)$ by considering pairs $(L, M)$ of multisets of $r$ integers, written as weakly increasing sequences $1 \le \ell_1 \le \cdots \le \ell_r \le n$, and $1 \le m_1 \le \cdots \le m_r \le n$. Let $\mathcal{A}_{L,M}(n; q)$ be the $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{-1}{2}}]$-span of monomials whose row indices and column indices (with multiplicity) are equal to the multisets $L$ and $M$, respectively. This leads to the multigrading

$$ \mathcal{A}(n; q) = \bigoplus_{r \ge 0} \bigoplus_{L, M} \mathcal{A}_{L, M}(n; q). \qquad (3.5) $$

The graded component $\mathcal{A}_{[n],[n]}(n; q)$ is spanned by the monomials

$$ \{x_{1,w_1} \cdots x_{n,w_n} \mid w \in \mathfrak{S}_n\}. \qquad (3.6) $$
Defining $x^{u,v} = x_{u_1,v_1} \cdots x_{u_n,v_n}$ for any $u, v \in \mathfrak{S}_n$, we may express the above basis as $\{x^{e,w} | w \in \mathfrak{S}_n\}$. We will call elements of this submodule (quantum) immanants and we will call the module itself the (immanant space) of $\mathcal{A}(n; q)$.

In general, $\mathcal{A}_{L,M}(n; q)$ is the $\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$-submodule of $\mathcal{A}(n; q)$ spanned by the monomials

$$ \{x_{\ell_1, m_{w_1}} \cdots x_{\ell_r, m_{w_r}} \mid w \in \mathfrak{S}_r\} = \{(x_{L,M})^{e,w} \mid w \in \mathfrak{S}_r\}, \quad (3.7) $$

where the generalized submatrix $x_{L,M}$ of $x$ is defined by

$$ x_{L,M} = \begin{bmatrix} x_{\ell_1, m_1} & x_{\ell_1, m_2} & \cdots & x_{\ell_1, m_r} \\ x_{\ell_2, m_1} & x_{\ell_2, m_2} & \cdots & x_{\ell_2, m_r} \\ \vdots & \vdots & \ddots & \vdots \\ x_{\ell_r, m_1} & x_{\ell_r, m_2} & \cdots & x_{\ell_r, m_r} \end{bmatrix}. \quad (3.8) $$

An involutive automorphism on $\mathcal{A}(n; q)$ commonly known as the *bar involution* is defined by $\overline{q^{\frac{1}{2}} = \overline{q^{\frac{1}{2}}, \overline{x_{i,j}} = x_{i,j}}$ and

$$ \overline{x_{a_1,b_1} \cdots x_{a_r,b_r}} = (q^{\frac{1}{2}})^{\alpha(a) - \alpha(b)} x_{a_r,b_r} \cdots x_{a_1,b_1}, \quad (3.9) $$

where $\alpha(a)$ is the number of pairs $i < j$ for which $a_i = a_j$. Equivalently, for $x_{a_1,b_1} \cdots x_{a_r,b_r} \in \mathcal{A}_{L,M}(n; q)$, we have

$$ \overline{x_{a_1,b_1} \cdots x_{a_r,b_r}} = q_{w_0^J, w_0^I} x_{a_r,b_r} \cdots x_{a_1,b_1}, \quad (3.10) $$

where

$$ I = I(L) = \{s_i \in \mathfrak{S}_r \mid \ell_i = \ell_{i+1}\} \quad (3.11) $$

$$ J = J(M) = \{s_j \in \mathfrak{S}_r \mid m_j = m_{j+1}\}. \quad (3.11) $$

In the immanant space, the bar involution reduces to

$$ \overline{x^{e,v}} = x_{n,v_n} \cdots x_{1,v_1} = x^{w_0,w_0v}. \quad (3.12) $$

Taking the bar involution of an element of $\mathcal{A}_{[n],[n]}(n; q)$ and expanding in terms of the natural basis, we have

$$ \overline{x^{e,v}} = \sum_{w \ge v} q_{v,w}^{-1} S_{v,w}(q) x^{e,w}, \quad (3.13) $$

where $\{S_{v,w}(q) | v, w \in \mathfrak{S}_n\}$ are polynomials in $\mathbb{Z}[q]$, which we call *inverse R-polynomials*. Modifying these polynomials by

$$ q_{v,w}^{-1} S_{v,w}(q) = \tilde{S}_{v,w}(q^{\frac{1}{2}} - \overline{q^{\frac{1}{2}}}) \quad (3.14) $$

gives us the *modified inverse R-polynomials* $\{\tilde{S}_{v,w}(q) | v, w \in \mathfrak{S}_n\}$, which belong to $\mathbb{N}[q]$. Thus we may rewrite (3.13) as

$$ \overline{x^{e,v}} = \sum_{w \ge v} \tilde{S}_{v,w} (q^{\frac{1}{2}} - \overline{q^{\frac{1}{2}}}) x^{e,w}. \quad (3.15) $$

In an arbitrary multigraded component $\mathcal{A}_{L,M}(n; q)$ of $\mathcal{A}(n; q)$, for $v \in W_+^{I,J}$ we have

$$ (\overline{x_{L,M}})^{e,v} = \sum_{\substack{w \in W_+^{I,J} \\ w \ge v}} \epsilon_{v,w} q_{v,w} S_{v,w}^{I,J}(q^{-1}) x^{e,w}, \quad (3.16) $$
where {$S_{v,w}^{I,J}(q) | v, w \in W_{+}^{I,J}$} are polynomials in $\mathbb{Z}[q]$, which we call *parabolic inverse R-polynomials*. Modifying these polynomials in an analogous way as in the immanant space creates some difficulty, since they must be expressed as functions of two variables, $q^{\frac{1}{2}} - q^{-\frac{1}{2}}$ and $q^{-\frac{1}{2}}$. The algebraic relationship between these two variables causes problems when we try to define *modified parabolic inverse R-polynomials* in a manner analogous to (3.14). Instead for all $v, w \in W_{+}^{I,J}$, given any reduced expression $s_{i_1} \cdots s_{i_k}$ for $u$, let us define the polynomials $\{\tilde{S}_{v,w}^{I,J}(q_1, q_2) \in \mathbb{N}[q_1, q_2] \mid v, w \in W_{+}^{I,J}\}$ to be the polynomials whose coefficient of $q_1^a q_2^b$ is equal to the number of sequences $(\pi^{(0)}, \dots, \pi^{(k)})$ of permutations satisfying

$$1. \pi^{(0)} = w_0 v, \pi^{(k)} \in W_I w W_J,$$

$$2. \pi^{(j)} \in \{\pi^{(j-1)}, s_{i_j} \pi^{(j-1)}\} \text{ for } j = 1, \dots, k,$$

$$3. \pi^{(j)} = s_{i_j} \pi^{(j-1)} \text{ if } s_{i_j} \pi^{(j-1)} > \pi^{(j-1)},$$

$$4. \pi^{(j)} = \pi^{(j-1)} \text{ for exactly } a \text{ indices } j,$$

$$5. \ell(w) - \ell(\pi^{(k)}) = b.$$

It will be shown later that this definition will lead to

$$\overline{(x_{L,M})^{e,v}} = \sum_{\substack{w \in W_{+}^{I,J} \\ w \ge v}} \tilde{S}_{v,w}^{I,J}(q^{\frac{1}{2}} - q^{\frac{-1}{2}}, q^{\frac{-1}{2}}) x^{e,w}, \qquad (3.17)$$

and therefore

$$\epsilon_{v,w} q_{v,w} S_{v,w}^{I,J}(q^{-1}) = \tilde{S}_{v,w}^{I,J}(q^{\frac{1}{2}} - q^{\frac{-1}{2}}, q^{\frac{-1}{2}}), \qquad (3.18)$$

as desired.

Unlike the double parabolic R-polynomials {$R_{v,w}^{I,J}(q) | v, w \in W_{+}^{I,J}$}, the double parabolic inverse R-polynomials {$S_{v,w}^{I,J}(q) | v, w \in W_{+}^{I,J}$} can not readily be written as sums of nonparabolic polynomials {$S_{v,w}(q) | v, w \in \mathfrak{S}_n$}. That is, we know of no identity in $\mathcal{A}_{L,M}(n; q)$ analogous Equation (2.9) which might lead to an analog of Equation (2.12) for inverse parabolic R-polynomials. While actions of $H_n(q)$ on submodules of $\mathcal{A}(n; q)$ corresponding to $L = [n]$ or $M = [n]$ can help produce identities for polynomials of the forms $S_{u,v}^{I,\emptyset}(q)$ and $S_{u,v}^{\emptyset,J}(q)$, this method fails in the general double parabolic setting.

Nevertheless, we will succeed in expressing a polynomial $\tilde{S}_{v,w}^{I,J}(q)$ in terms of nonparabolic polynomials. To do so we will consider various bases of the immanant space $\mathcal{A}_{[n],[n]}(n; q)$.

# 4 A family of bases for the quantum immanant space

Working in the quantum immanant space $\mathcal{A}_{[n],[n]}(n; q)$, one often obtains a monomial of the form $x^{u,v}$ and wishes to express it in terms of the natural basis. The relations (3.1) imply that we have

$$x^{u,v} \in x^{e,u^{-1}v} + \sum_{w > u^{-1}v} \mathbb{N}[q^{\frac{1}{2}} - q^{\frac{-1}{2}}] x^{e,w}. \qquad (4.1)$$

It follows that for each permutation $u \in \mathfrak{S}_n$, the set $\{x^{u,v} | v \in \mathfrak{S}_n\}$ is a basis for $\mathcal{A}_{[n],[n]}(n; q)$. Indeed the natural basis and barred natural basis are special cases corresponding to $u = e$ and $u = w_0$, respectively.
To state transition matrices relating all of these bases to the natural basis, let us define polynomials $p_{u,v,w}(q)$ in $\mathbb{N}[q]$ by the equations

$$x^{u,v} = \sum_{w \ge u-1,v} p_{u,v,w}(q^{\frac{1}{2}} - q^{\frac{-1}{2}})x^{e,w}. \quad (4.2)$$

Apparently we have the special cases

$$p_{e,v,w}(q) = \begin{cases} 1 & \text{if } v = w \\ 0 & \text{otherwise,} \end{cases} \qquad p_{w_0,w_0v,w}(q) = \tilde{S}_{v,w}(q). \quad (4.3)$$

The polynomials $\{p_{u,v,w}(q) | u, v, w \in \mathfrak{S}_n\}$ have an elementary combinatorial interpretation. The following result generalizes those of Deodhar [Deo85] and Dyer [Dye93], for the special case $u = w_0$.

**Theorem 4.1** Given any reduced expression $s_{i_1} \cdots s_{i_\ell}$ for $u$, the coefficient of $q^k$ in $p_{u,v,w}(q)$ is equal to the number of sequences $(\pi^{(0)}, \dots, \pi^{(\ell)})$ of permutations satisfying

1. $\pi^{(0)} = v, \pi^{(\ell)} = w$.

2. $\pi^{(j)} \in \{s_{i_j} \pi^{(j-1)}, \pi^{(j-1)}\}$ for $j = 1, \dots, \ell$.

3. $\pi^{(j)} = s_{i_j} \pi^{(j-1)}$ if $s_{i_j} \pi^{(j-1)} > \pi^{(j-1)}$.

4. $\pi^{(j)} = \pi^{(j-1)}$ for exactly $k$ values of $j$.

**Proof:** Omitted. $\square$

<figure><img src="image_1.png" /></figure>

These sequences of permutations can be thought of as walks in the Bruhat order from $v$ to $w$, with steps up, steps down, and repeated vertices constrained by the fixed reduced expression for $u$. We remark that since the definition (4.2) does not depend on the chosen reduced expression for $u$, Theorem 4.1 implies several sets of walks in the Bruhat order are equinumerous.

**Problem 4.2** Find bijections between the sets of walks in Theorem 4.1 which correspond to different reduced expressions for $u$.

An alternate basis for the immanent space consists of the monomials

$$\{x^{w^{-1},e} | w \in \mathfrak{S}_n\}. \quad (4.4)$$

Using this fact, we obtain the following identity.

**Proposition 4.3** For all $u, v, w \in \mathfrak{S}_n$, we have

$$p_{v,u,w^{-1}}(q) = p_{u,v,w}(q). \quad (4.5)$$

**Proof:** Omitted. $\square$

<figure><img src="image_2.png" /></figure>

Theorem 4.1 then implies that two sets of walks in the Bruhat order are equinumerous.

**Problem 4.4** Find a bijective proof of the identity in Proposition 4.3.
A straightforward argument shows that the polynomials {$p_{u,v,w}(q) | u, v, w \in \mathfrak{S}_n$} also describe the expansions of certain products of natural basis elements of $H_n(q)$.

**Corollary 4.5** For $u, v$ in $\mathfrak{S}_n$, we have

$$ \tilde{T}_{u^{-1}}\tilde{T}_{v} = \sum_{w \ge u^{-1}v} p_{u,v,w}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}})\tilde{T}_{w}. \qquad (4.6) $$

**Proof:** Omitted. $\square$

# 5 Main results

The double parabolic inverse R-polynomials {$S_{v,w}^{I,J}(q) | u, v \in W_{+}^{I,J}$} and the modified double parabolic inverse R-polynomials {$\tilde{S}_{v,w}^{I,J}(q_1, q_2) | u, v \in W_{+}^{I,J}$} satisfy

$$ \begin{aligned} S_{u,w}^{I,J}(q) &= \sum_{v \in W_I w W_J} \epsilon_{v,w} q_{v,w}^2 S_{u,v}(q), \\ \tilde{S}_{u,w}^{I,J}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}) &= \sum_{v \in W_I w W_J} q_{v,w}^{-1} \tilde{S}_{u,v}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}). \end{aligned} \qquad (5.1) $$

As we have already mentioned, these identities are not easily seen unless $I = \emptyset$ or $J = \emptyset$. Following the results in Section 4, we will obtain these identities by considering various bases of $\mathcal{A}_{L,M}(n; q)$.

The relations (3.1) imply that we have

$$ (x_{L,M})^{u,v} \in q^{\frac{k}{2}} (x_{L,M})^{e,u^{-1}v} + \sum_{\substack{w \in W_{+}^{I,J} \\ w > u^{-1}v}} \mathbb{N}[q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}] (x_{L,M})^{e,w}. \qquad (5.2) $$

It follows that for each permutation $u \in \mathfrak{S}_n$, the set {$(x_{L,M})^{u,v} | u^{-1}v \in W_{+}^{I,J}$} is a basis for $\mathcal{A}_{L,M}(n; q)$. Indeed the natural basis and barred natural basis are special cases corresponding to $u = e$ and $u = w_0$, respectively.

To state transition matrices relating all of these bases to the natural basis, for all $u \in \mathfrak{S}_n$, $v \in W_{-}^{\emptyset, J}$ and $w \in W_{+}^{I,J}$, given any reduced expression $s_{i_1} \cdots s_{i_k}$ for $u$, let us define the Laurent polynomials $p_{u,v,w}^{I,J}(q_1, q_2)$ to be the polynomials whose coefficient of $q_1^a q_2^b$ is equal to the number of sequences $(\pi^{(0)}, \dots, \pi^{(k)})$ of permutations satisfying

1. $\pi^{(0)} = v$, $\pi^{(k)} \in W_I w W_J$,

2. $\pi^{(j)} \in \{s_{i_j} \pi^{(j-1)}, \pi^{(j-1)}\}$ for $j = 1, \dots, k$,

3. $\pi^{(j)} = s_{i_j} \pi^{(j-1)}$ if $s_{i_j} \pi^{(j-1)} > \pi^{(j-1)}$,

4. $\pi^{(j)} = \pi^{(j-1)}$ for exactly $a$ values of $j$,

5. $\ell(w_{-}^{I}) - \ell((\pi^{(k)})_{-}^{I}) - \ell((\pi^{(k)})^{J}) + \ell(u^{I}) = b$.
We remark that this definition of $p_{u,v,w}^{I,J}(q_1, q_2)$ depends upon the chosen reduced expression for $u$, unlike our definition (4.2) of $p_{u,v,w}(q)$. Nevertheless, we will suppress this dependence from the notation.

These sequences of permutations can be thought of as walks in the Bruhat order from $v$ to any permutation in $W_I w W_J$, with steps up, steps down, and repeated vertices constrained by the fixed reduced expression for $u$. Apparently we have the special cases

$$p_{e,v,w}^{I,J}(q_1, q_2) = \begin{cases} 1 & \text{if } v = w \\ 0 & \text{otherwise,} \end{cases} \qquad p_{w_0,w_0v,w}(q_1, q_2) = q_2^{\ell(w_0^I) - \ell(w_0^J)} \tilde{S}_{v,w}^{I,J}(q_1, q_2). \quad (5.3)$$

Using the relations (3.1) and facts about double cosets of $\mathfrak{S}_n$, we can show that certain transition matrices consist of the polynomials $\{p_{u,v,w}^{I,J}(q_1, q_2) \mid u \in \mathfrak{S}_n, v \in W_{-}^{\emptyset,J}, w \in W_{+}^{I,J}\}$ evaluated at $q_1 = q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}$ and $q_2 = \bar{q}^{\frac{1}{2}}$.

**Theorem 5.1** For $u \in \mathfrak{S}_n$, any reduced expression for $u$, and $v \in W_{-}^{\emptyset,J}$,

$$(x_{L,M})^{u,v} = \sum_{w \in W_{+}^{I,J}} p_{u,v,w}^{I,J}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}})(x_{L,M})^{e,w}. \quad (5.4)$$

**Proof:** Omitted. $\square$

**Problem 5.2** Modify the definition of $p_{u,v,w}^{I,J}(q_1, q_2)$ to include all $v \in \mathfrak{S}_n$ in such a way that Theorem 5.1 holds for all $u, v \in \mathfrak{S}_n$.

The combinatorial definition above leads to the following identity connecting the parabolic and non-parabolic polynomials.

**Corollary 5.3** For all $u, v \in \mathfrak{S}_n$ and $w \in W_{+}^{I,J}$,

$$p_{u,v,w}^{I,J}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}) = \sum_{z \in W_I w W_J} (\bar{q}^{\frac{1}{2}})^{\ell(w_0^I w_0^{K'}) - \ell(z_-^I) - \ell(z^J) + \ell(u^I)} p_{u,v,z}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}). \quad (5.5)$$

**Proof:** Omitted. $\square$

Now, using Equation (5.3) and Theorem 5.1 we can derive the desired identity (3.17) relating double parabolic inverse $R$-polynomials and modified double parabolic inverse $R$-polynomials.

**Theorem 5.4** For all $v \in W_{+}^{I,J}$

$$\overline{(x_{L,M})^{e,v}} = \sum_{\substack{w \in W_{+}^{I,J} \\ w \ge v}} \tilde{S}_{v,w}^{I,J}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}})(x_{L,M})^{e,w}. \quad (5.6)$$

**Proof:** Omitted. $\square$

Finally, using the previous theorem along with Theorem 4.1 and Equations (4.3) and (5.3) we can derive the desired identity (5.1) relating double parabolic and nonparabolic inverse $R$-polynomials.
**Theorem 5.5** The double parabolic inverse R-polynomials {$S_{v,w}^{I,J}(q) | u, v \in W_{+}^{I,J}$} and their modifications {$\tilde{S}_{v,w}^{I,J}(q_1, q_2) | u, v \in W_{+}^{I,J}$} satisfy

$$ S_{u,w}^{I,J}(q) = \sum_{v \in W_I w W_J} \epsilon_{v,w} q_{v,w}^2 S_{u,v}(q), \qquad (5.7) \\ \tilde{S}_{u,w}^{I,J}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}) = \sum_{v \in W_I w W_J} q_{v,w}^{-1} \tilde{S}_{u,v}(q^{\frac{1}{2}} - \bar{q}^{\frac{1}{2}}). $$

**Proof:** Omitted. □

## References

[Bre94] Francesco Brenti. A combinatorial formula for Kazhdan-Lusztig polynomials. *Invent. Math.*, 118(2):371–394, 1994.

[Bre97a] Francesco Brenti. Combinatorial expansions of Kazhdan-Lusztig polynomials. *J. London Math. Soc.*, 55(2):448–472, 1997.

[Bre97b] Francesco Brenti. Combinatorial properties of the Kazhdan-Lusztig R-polynomials for $S_n$. *Adv. Math.*, 126(1):21–51, 1997.

[Bre98] Francesco Brenti. Kazhdan-Lusztig and R-polynomials from a combinatorial point of view. *Discrete Math.*, 193(1-3):93–116, 1998. Selected papers in honor of Adriano Garsia (Taormina, 1994).

[Bre02] Francesco Brenti. Kazhdan-Lusztig and R-polynomials, Young's lattice, and Dyck partitions. *Pacific J. Math.*, 207(2):257–286, 2002.

[Cur85] Charles W. Curtis. On Lusztig's isomorphism theorem for Hecke algebras. *J. Algebra*, 92(2):348–365, 1985.

[Deo85] Vinay V. Deodhar. On some geometric aspects of Bruhat orderings. I. A finer decomposition of Bruhat cells. *Invent. Math.*, 79(3):499–511, 1985.

[Deo87] Vinay Deodhar. On some geometric aspects of Bruhat orderings. II. The parabolic analogue of Kazhdan-Lusztig polynomials. *J. Algebra*, 111(2):483–506, 1987.

[Dou90] J. M. Douglass. An inversion formula for relative Kazhdan-Lusztig polynomials. *Comm. Algebra*, 18(2):371–387, 1990.

[Du94] Jie Du. IC bases and quantum linear groups. In *Algebraic groups and their generalizations: quantum and infinite-dimensional methods* (University Park, PA, 1991), volume 56 of Proc. Sympos. Pure Math, pages 135–148. Amer. Math. Soc., Providence, RI, 1994.

[Dye93] M. J. Dyer. Hecke algebras and shellings of Bruhat intervals. *Compositio Math.*, 89:91–115, 1993.
[Kas91] M. Kashiwara. On crystal bases of the $Q$-analog of universal enveloping algebras. *Duke Math. J.*, 63:465–516, 1991.

[KL79] D. Kazhdan and G. Lusztig. Representations of Coxeter groups and Hecke algebras. *Invent. Math.*, 53:165–184, 1979.

[Lus85] G. Lusztig. Cells in affine Weyl groups. In *Algebraic Groups and Related Topics (Kyoto/Nagoya 1983)*, volume 6 of *Adv. Stud. Pure Math*, pages 255–287. North-Holland, Amsterdam, 1985.

[Lus90] G. Lusztig. Canonical bases arising from quantized enveloping algebras. *J. Amer. Math. Soc.*, 3:447–498, 1990.