# An immanant formulation of the dual canonical basis of the quantum polynomial ring

Mark Skandera¹ and Justin Lambright²

¹² Lehigh University Department of Mathematics, 14 East Packer Ave., Bethlehem, PA 18015, USA

**Abstract.** We show that dual canonical basis elements of the quantum polynomial ring in $n^2$ variables can be expressed as specializations of dual canonical basis elements of 0-weight spaces of other quantum polynomial rings. Our results rely upon the natural appearance in the quantum polynomial ring of Kazhdan-Lusztig polynomials, $R$-polynomials, and certain single and double parabolic generalizations of these.

**Résumé.** Nous démontrons que des éléments de la base canonique duale de l'anneau quantique des polynômes en $n^2$ variables peuvent s'exprimer en termes des spécialisations d'éléments de la base canonique duale des espaces de poids 0 d'autres anneaux quantiques. Nos résultats dependent fortement de l'apparition naturelle des polynômes de Kazhdan-Lusztig, des $R$-polynômes, et de certaines généralisations simplement et doublement parapoliques de ces polynômes dans l'anneau quantique.

**Keywords:** Dual canonical basis, immanant, Kazhdan-Lusztig polynomial, Hecke algebra, quantum polynomial ring

## 1 Introduction

Contributing to research concerning the Quantum Yang-Baxter Equation and its applications, Drinfeld [6] and Jimbo [9] introduced quantum analogs of classical enveloping algebras of Lie algebras. These quantized enveloping algebras belong to a family of Hopf algebras now known as *quantum groups*. Lusztig [13] and Kashiwara [10] advanced the representation theory of quantized enveloping algebras by introducing *canonical* (or *crystal*) bases for the algebras, which then led to definitions of *dual canonical* bases for other quantum groups, and even for algebras which are not quantum groups. In particular, the dual canonical basis for the quantum group $O_q SL_n(\mathbb{C})$ can be readily expressed in terms of Du's [7] *dual canonical basis* for the quantum polynomial ring $\mathcal{A}(n; q)$, which is not a quantum group.

In the above algebras, (dual) canonical bases are realted to several natural bases by transition matrices whose entries $C[q^{1/2}, q^{-1/2}]$-linear combinations of certain polynomials in $\mathbb{Z}[q]$. These polynomials, which had appeared earlier in Kazhdan and Lusztig's work on Coxeter group and Hecke algebra representations [11] are called *Kazhdan-Lusztig polynomials* and *R-polynomials*. Even some such linear combinations, which can be defined in terms of single and double cosets of parabolic subgroups of Coxeter groups, had appeared earlier too. Specifically, those defined in terms of single parabolic cosets had
appeared explicitly in the work of Douglass [5] and Deodhar [3]. These single parabolic analogs of Kazhdan-Lusztig and R-polynomials later assumed a prominent place in the literature, usually appearing in conjunction with single parabolic analogs of Hecke algebras. They appeared less frequently in conjunction with $\mathcal{A}(n; q)$, where they also arise naturally. On the other hand, the double parabolic analogs, some of which had appeared implicitly in the work of Curtis [2] even before the papers of Douglass and Deodhar, virtually escaped mention elsewhere in the literature.

We give a very brief overview of the natural appearances of double-parabolic Kazhdan-Lusztig and R-polynomials of type A in Hecke algebra modules and in the quantum polynomial ring $\mathcal{A}(n; q)$. In particular, we use the polynomials to give a new formulation of the dual canonical basis of $\mathcal{A}(n; q)$ and show that this is equivalent to Du's formulation [7].

In Sections 2-3, we consider the Hecke algebra $H_n(q)$ and parabolic generalizations. In Section 4, we introduce the quantum polynomial ring $\mathcal{A}(n; q)$ and a duality which relates it to the earlier defined parabolic $H_n(q)$-modules. In Section 5, we apply the above duality to the zero-weight space (or immanant space) of $\mathcal{A}(n; q)$, to demonstrate some occurrences of (non-parabolic) Kazhdan-Lusztig and R-polynomials in this space. Some of these results appear (sadly) to be new. Finally, in Section 6, we discuss some brief appearances of double-parabolic Kazhdan-Lusztig and R-polynomials in the literature, and prove some additional results. In particular, we consider Du's formulation of the dual canonical basis of $\mathcal{A}(n; q)$ in terms of double-parabolic Kazhdan-Lusztig polynomials, and state an equivalent formulation which combines ordinary Kazhdan-Lusztig polynomials with row and column repetition within matrices. This result shows that one can understand all multigraded components of the dual canonical basis of $\mathcal{A}(n; q)$ in terms of zero-weight spaces of all quantum polynomial rings.

## 2 The symmetric group and Hecke algebra

The most basic results of Kazhdan and Lusztig [11] may be expressed in terms of the symmetric group $S_n$ and Hecke algebra $H_n(q)$ of type A.

Let $s_1, \dots, s_{n-1}$ be the standard adjacent tranpositions generating $S_n$, satisfying the relations

$$ 
\begin{aligned}
s_i^2 &= 1, && \text{for } i = 1, \dots, n-1, \\
s_i s_j s_i &= s_j s_i s_j, && \text{if } |i-j| = 1, \\
s_i s_j &= s_j s_i, && \text{if } |i-j| \ge 2.
\end{aligned} 
\quad (1) 
$$

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. \quad (2) $$

For each element $v = s_{i_1} \cdots s_{i_\ell} \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, denoting the identity permutation of $S_n$ by $e$, the one-line notation of $e$ is $12 \cdots n$. Using this convention, the one-line notation of $vw$ is $(vw)_1 \cdots (vw)_n = v \circ (w \circ e) = w_{v_1} \cdots w_{v_n}$. We will denote the one-line notation of $v^{-1} = s_{i_\ell} \cdots s_{i_1}$ by $v_1^{-1} \cdots v_n^{-1}$. Let $\ell(w)$ be the minimum length of an expression for $w$ in terms of the generators, and let $w_0$ denote the longest permutation in $S_n$. Let $\le$ denote the Bruhat order on $S_n$, i.e., $v \le w$ if every reduced expression for $w$ contains a reduced expression for $v$ as a subword.
A deformation of $\mathfrak{S}_n$ known as the Hecke algebra $H_n(q)$ is the $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-algebra generated by the set $\{\tilde{T}_{s_i} | 1 \le i \le n-1\}$ of (modified) natural generators, 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{if } |i-j| = 1, \\ \tilde{T}_{s_i} \tilde{T}_{s_j} &= \tilde{T}_{s_j} \tilde{T}_{s_i}, & \text{if } |i-j| \ge 2. \end{aligned} \quad (3) $$

(We follow [12].) If $s_{i_1} \cdots s_{i_\ell}$ 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_\ell}}$, and $\tilde{T}_e = 1$. We shall call the elements $\{\tilde{T}_w | w \in \mathfrak{S}_n\}$ the natural basis of $H_n(q)$ as a $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-module. Specializing $H_n(q)$ at $q^{\frac{1}{2}} = 1$, we recover the classical group algebra $\mathbb{C}[\mathfrak{S}_n]$ of the symmetric group. We remark that basis elements often denoted in the literature by $\{T_w | w \in \mathfrak{S}_n\}$ are related to our basis elements by $\tilde{T}_w = \bar{q}^{-\frac{\ell(w)}{2}} T_w$. We will find it convenient to define the notation

$$ \begin{aligned} [n] &= \{1, \dots, n\}, \\ \epsilon_{u,v} &= (-1)^{\ell(v)-\ell(u)}, \quad q_{u,v} = (q^{\frac{1}{2}})^{\ell(v)-\ell(u)}. \end{aligned} \quad (4) $$

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

$$ \bar{q} = q^{-1}, \quad \tilde{T}_w = (\tilde{T}_{w^{-1}})^{-1}. \quad (5) $$

It is straightforward to check that the elements $\{\tilde{T}_{s_i} | 1 \le i \le n-1\}$ generate $H_n(q)$. Expanding the basis $\{\tilde{T}_w | w \in S_n\}$ in terms of the natural basis [11], we have

$$ \tilde{T}_w = \sum_{v \le w} q_{v,w} R_{v,w} (q^{-1}) \tilde{T}_v, \quad (6) $$

where $\{R_{v,w}(q) | v, w \in \mathfrak{S}_n\}$ are polynomials belonging to $\mathbb{Z}[q]$, and commonly called R-polynomials.

We call an element $g$ of $H_n(q)$ bar-invariant if it satisfies $\bar{g} = g$. Kazhdan and Lusztig showed [11] that $H_n(q)$ has a unique basis of bar-invariant elements $\{C'_v(q) | v \in \mathfrak{S}_n\}$ with

$$ C'_v(q) \in \tilde{T}_v + \sum_{u<v} \bar{q}^{\frac{1}{2}} \mathbb{Z}[\bar{q}^{\frac{1}{2}}] \tilde{T}_u. \quad (7) $$

Expanding $C'_v(q)$ in terms of the natural basis, we have

$$ C'_v(q) = \sum_{u \le v} q_{u,v}^{-1} P_{u,v}(q) \tilde{T}_v, \quad (8) $$

where $\{P_{u,v}(q) | u, v \in \mathfrak{S}_n\}$ are polynomials belonging to $\mathbb{Z}[q]$ (in fact, to $\mathbb{N}[q]$). Call this basis the (sign-less) Kazhdan-Lusztig basis for $H_n(q)$. Observe that (7) is equivalent to the conditions that $P_{u,u}(q) = 1$ for all $u$, $P_{u,v}(q) = 0$ for $u \not\le v$, and $\deg P_{u,v}(q) \le \frac{1}{2}(\ell(v) - \ell(u) - 1)$ for $u < v$.

Uniqueness of this basis [11, Sec. 2.2] follows from rewriting the condition $\overline{C'_w(q)} = C'_w(q)$ as

$$ q_{u,w} P_{u,w}(q^{-1}) - q_{u,w}^{-1} P_{u,w}(q) = \sum_{u < v \le w} q_{u,v}^{-1} R_{u,v}(q) q_{v,w}^{-1} P_{v,w}(q) \quad \text{for all } u \le w. \quad (9) $$
In particular, there is a unique solution $P_{u,v}(q)$ satisfying this equation, when all other polynomials appearing are known. Existence of the basis [11, Sec. 2.2] follows from a recursive definition involving the function

$$ \mu(u, v) = \underset{\text{def}}{=} \begin{cases} \text{coefficient of } q^{(\ell(v)-\ell(u)-1)/2} \text{ in } P_{u,v}(q), & \text{if } u < v, \\ 0, & \text{otherwise.} \end{cases} \qquad (10) $$

In particular, assuming that for some $v$ we have defined bar-invariant elements $\{C'_{u}(q) | u \le v\}$ satisfying the condition (7), we choose $s$ so that $v < sv$ and define

$$ C'_{sv}(q) = C'_{s}(q)C'_{v}(q) - \sum_{\substack{u \le v \\ su \le u}} \mu(u, v)C'_{u}(q). \qquad (11) $$

One then verifies that $C'_{sv}(q)$ also is bar-invariant and satisfies (7).

### 3 Parabolic generalizations of $H_n(q)$

Many of the concepts and results summarized in Section 2 generalize to a parabolic setting and were first stated by Curtis [2], Deodhar [3],[4], Douglass [5], and Du [8].

Let $I$ and $J$ be subsets of the standard generators of $W = \mathfrak{S}_r$ and let $W_I, W_J$ be the corresponding parabolic subgroups of $W$. Define $W_\emptyset = \{e\}$. Let $W_I \setminus W/W_J$ be the set of double cosets of the form $W_I w W_J$. It is well known that each such double coset is an interval in the Bruhat order and thus has a unique minimal element and a unique maximal element. Let $W_+^{I,J}$ be the set of maximal representatives of cosets in $W_I \setminus W/W_J$ and let $W_-^{I,J}$ be the set of minimal coset representatives. Let $w_0^I$ and $w_0^J$ be the longest elements in $W_I, W_J$. We have

$$ W_+^{I,J} = \{w \mid s_i w < w, ws_j < w \text{ for all } s_i \in I, s_j \in J\} \qquad (12) $$

We may define a Bruhat order on $W_I \setminus W/W_J$ in terms of maximal coset representatives $v, w \in W_+^{I,J}$: $W_I w W_J \le W_I w W_J$ if and only if $v \le w$. Equivalently, by [5, Lem. 2.2], we may define this order in terms of minimal coset representatives.

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_{v,w}^{-1} \tilde{T}_v. \qquad (13) $$

Note that if $I = \emptyset$ and $J = \emptyset$, then each coset $W_I w W_J$ in $W_I \setminus W/W_J$ is simply $w \in S_n$ and we have $\tilde{T}'_{W_I w W_J} = \tilde{T}_w$. 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}}, q^{\frac{-1}{2}}]} \{ \tilde{T}'_{W_I w W_J} \mid w \in W_+^{I,J} \}. \qquad (14) $$

The bar involution on $H_n(q)$ induces a bar involution on $H'_{I,J}$. Curtis [2, Sec. 1] showed the elements $\{\tilde{T}_{W_I w W_J} | v \in W_+^{I,J}\}$ to form a basis of $H'_{I,J}$, and Du [8, Sec. 1] showed that we have

$$ \tilde{T}_{W_I w W_J} = \sum_{u \le v} q_{u,v} R_{u,v}^{I,J} (q^{-1}) \tilde{T}_v, \qquad (15) $$
where {$R_{u,v}^{I,J}(q) | u, v \in W_{+}^{I,J}$} are polynomials belonging to $\mathbb{Z}[q]$. This was probably the first mention in the literature of double-parabolic R-polynomials, although Deodhar [3, Sec. 2] and Douglass [5, Sec. 3] had earlier considered the single-parabolic cases in which $I = \emptyset$ or $J = \emptyset$. It follows 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_{u,v}(q). \qquad (16)$$

Curtis [2, Thm. 1.10] showed that the set {$C'_{v}(q) | v \in W_{+}^{I,J}$} forms a bar-invariant basis of $H'_{I,J}$ and satisfies

$$C'_{v}(q) \in \tilde{T}'_{W_I v W_J} + \sum_{\substack{u \in W_{+}^{I,J} \\ u < v}} \bar{q}^{\frac{1}{2}} \mathbb{Z}[\bar{q}^{\frac{1}{2}}] \tilde{T}'_{W_I u W_J}. \qquad (17)$$

In particular, he showed that the expansion of $C'_{v}(q)$ in terms of the natural basis of $H'_{I,J}$ is

$$C'_{v}(q) = \sum_{\substack{u \in W_{+}^{I,J} \\ u \le v}} q_{u,v}^{-1} P_{u,v}(q) \tilde{T}'_{W_I u W_J}, \qquad (18)$$

where {$P_{u,v}(q) | u, v \in W_{+}^{I,J}$} are simply the Kazhdan-Lusztig polynomials indexed by pairs of permutations in $W_{+}^{I,J}$. To prove uniqueness, one rewrites the condition $\overline{C'_{w}(q)} = C'_{w}(q)$ as

$$q_{u,w} P_{u,w}(q^{-1}) - q_{u,w}^{-1} P_{u,w}(q) = \sum_{u < v \le w} q_{u,v}^{-1} R_{u,v}^{I,J}(q) q_{v,w}^{-1} P_{v,w}(q) \quad \text{for all } u \in W_{+}^{I,J}, u \le w. \qquad (19)$$

In particular, there is a unique solution $P_{u,w}(q)$ satisfying this equation, when all other polynomials appearing are known. In this context, the Kazhdan-Lusztig polynomials are sometimes called *parabolic Kazhdan-Lusztig polynomials*.

We remark that Deodhar [4] chose to name these polynomials (in the single parabolic cases) in terms of *minimal coset representatives*, rather than *maximal coset representatives*. As many other authors followed suit, one sees in the literature that the most common indexing of Kazhdan-Lusztig polynomials in a parabolic setting does not match the original indexing due to Kazhdan and Lusztig [11]. In particular, Deodhar [3], [4] associated the parameter $-1$ to the Kazhdan-Lusztig and R-polynomials above (when $I = \emptyset$ and $v, w \in W_{+}^{\emptyset, J}$), denoting $P_{v,w}(q)$ and $R_{v,w}^{\emptyset, J}(q)$ by $P_{vw^{J}, ww^{J}}^{J}(q)$ and $R_{vw^{J}, ww^{J}}^{J}(q)$, respectively. Douglas [5] associated the parameter $u = q$ to the same polynomials, denoting them $P_{vW_{J}, wW_{J}}(q)$ and $R_{vW_{J}, wW_{J}}(q)$, respectively.

# 4 The quantum polynomial ring

A second noncommutative ring called the *quantum polynomial ring* $\mathcal{A}(n; q)$, can be used to express the quantum group $\mathcal{O}_q SL(n, \mathbb{C})$, the quantum coordinate ring of $SL(n, \mathbb{C})$, as a quotient.

The ring $\mathcal{A}(n; q)$ is generated as an $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-algebra 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 (20)$$
for all indices $i < j, k < \ell$. We have the isomorphism $\mathcal{O}_q SL(n, \mathbb{C}) \cong \mathcal{A}(n; q)/(\det_q(x) - 1)$, where

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

is the quantum determinant. Specializing $\mathcal{A}(n; q)$ at $q^{\frac{1}{2}} = 1$, we obtain the commutative polynomial ring $\mathbb{C}[x_{1,1}, \dots, x_{n,n}]$.

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, and we can use the relations above to convert any other monomial to this standard form. $\mathcal{A}(n; q)$ has a natural grading by degree,

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

where $\mathcal{A}_r(n; q)$ is the $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-span of all monomials of total degree $r$. Furthermore, the natural basis $\{x_{1,1}^{a_{1,1}} \cdots x_{n,n}^{a_{n,n}} | a_{1,1}, \dots, a_{n,n} \in \mathbb{N}\}$ of $\mathcal{A}(n; q)$ is a disjoint union

$$ \bigcup_{r \ge 0} \{x_{1,1}^{a_{1,1}} \cdots x_{n,n}^{a_{n,n}} | a_{1,1} + \cdots + a_{n,n} = r\} \qquad (23) $$

of bases of the homogeneous components $\{\mathcal{A}_r(n; q) | r \ge 0\}$. We may further decompose each homogeneous component $\mathcal{A}_r(n; q)$ by considering pairs $(K, M)$ of multisets of $r$ integers, written as weakly increasing sequences $1 \le k_1 \le \cdots \le k_r \le n$, and $1 \le m_1 \le \cdots \le m_r \le n$. This leads to the multigrading

$$ \mathcal{A}(n; q) = \bigoplus_{r \ge 0} \mathcal{A}_r(n; q) = \bigoplus_{r \ge 0} \bigoplus_{K, M} \mathcal{A}_{K, M}(n; q), \qquad (24) $$

where the last direct sum is over pairs $(K, M)$ of $r$-element multisets of $[n]$, and $\mathcal{A}_{K,M}(n; q)$ is 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 $K$ and $M$, respectively. Thus the graded component $\mathcal{A}_{[n],[n]}(n; q)$ is the $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-submodule of $\mathcal{A}(n; q)$ spanned by the monomials

$$ \{x_{1,w_1} \cdots x_{n,w_n} | w \in \mathcal{S}_n\}. \qquad (25) $$

Defining $x_{u_1,v_1} \cdots x_{u_n,v_n}$ for any $u, v \in \mathcal{S}_n$, we may express the above basis as $\{x^{e,w} | w \in \mathcal{S}_n\}$. We will call elements of this submodule (quantum) immanants. In particular, for any $\mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$-linear function $f : H_n(q) \to \mathbb{C}[q^{\frac{1}{2}}, \bar{q}^{\frac{1}{2}}]$, we define the quantum f-immanant

$$ \mathrm{Imm}_f(x) = \sum_{w \in \mathcal{S}_n} f(\tilde{T}_w) x^w. \qquad (26) $$

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

$$ \{x_{k_1, m_{w_1}} \cdots x_{k_r, m_{w_r}} | w \in \mathcal{S}_r\} = \{(x_{K,M})^{e,w} | w \in \mathcal{S}_r\}, \qquad (27) $$
where the generalized submatrix $x_{K,M}$ of $x$ is defined by

$$x_{K,M} = \begin{bmatrix} x_{k_1,m_1} & x_{k_1,m_2} & \cdots & x_{k_1,m_r} \\ x_{k_2,m_1} & x_{k_2,m_2} & \cdots & x_{k_2,m_r} \\ \vdots & \vdots & \ddots & \vdots \\ x_{k_r,m_1} & x_{k_r,m_2} & \cdots & x_{k_r,m_r} \end{bmatrix}. \qquad (28)$$

Note that variables in the monomials (27) do not necessarily appear in lexicographic order, e.g.,

$$(x_{112,123}) = \begin{bmatrix} x_{1,1} & x_{1,2} & x_{1,3} \\ x_{1,1} & x_{1,2} & x_{1,3} \\ x_{2,1} & x_{2,2} & x_{2,3} \end{bmatrix}, \quad (x_{112,123})^{e,321} = x_{1,3}x_{1,2}x_{2,1}. \qquad (29)$$

It is easy to see that the monomials $\{(x_{K,M})^{u,v} | u, v \in \mathfrak{S}_r\}$ satisfy

$$(x_{K,M})^{s_i u, v} = \begin{cases} (x_{K,M})^{u, s_i v} & \text{if } k_{u_i} < k_{u_{i+1}} \text{ and } m_{v_i} < m_{v_{i+1}}, \\ q^{\frac{1}{2}}(x_{K,M})^{u, s_i v} = (x_{K,M})^{u, v} & \text{or if } k_{u_i} > k_{u_{i+1}} \text{ and } m_{v_i} > m_{v_{i+1}}, \\ q^{-\frac{1}{2}}(x_{K,M})^{u, s_i v} = (x_{K,M})^{u, v} & \text{or if } k_{u_i} = k_{u_{i+1}} \text{ and } m_{v_i} = m_{v_{i+1}}, \\ (x_{K,M})^{u, s_i v} + (q^{\frac{1}{2}} - q^{-\frac{1}{2}})(x_{K,M})^{u, v} & \text{if } k_{u_i} < k_{u_{i+1}} \text{ and } m_{v_i} > m_{v_{i+1}}, \\ (x_{K,M})^{u, s_i v} - (q^{\frac{1}{2}} - q^{-\frac{1}{2}})(x_{K,M})^{u, v} & \text{if } k_{u_i} > k_{u_{i+1}} \text{ and } m_{v_i} < m_{v_{i+1}}. \end{cases} \quad (30)$$

An $r$-element multiset $M = m_1 \cdots m_r$ on $[n]$, for any $r$, determines a subset $I = \iota(M)$ of generators

$$\iota(M) = \{s_i | m_i = m_{i+1}\} \qquad (31)$$

of $\mathfrak{S}_r$. Let $K, M$ be $r$-element multisets of $[n]$, and define subsets $I = \iota(K)$, $J = \iota(M)$ of generators of $\mathfrak{S}_r$. Since the dimension of $\mathcal{A}_{K,M}(n;q)$ is less than $n!$ (unless $K = M = [n]$, or equivalently, if $I = J = \emptyset$), the spanning set (27) is not in general linearly independent. We may construct a basis for $\mathcal{A}_{K,M}(n;q)$ by using just one permutation $w$ from each coset in $W_I \setminus W/J$. In particular,

$$\mathcal{A}_{K,M}(n;q) = \operatorname{span}_{\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]} \{(x_{K,M})^{e,w} | w \in W_{+}^{I,J}\}. \qquad (32)$$

Thus for each pair $(K, M)$ of $r$-element multisets of $[n]$ satisfying $\iota(K) = I$, $\iota(M) = J$, we have $\dim \mathcal{A}_{K,M}(n;q) = \dim H'_{I,J}$. Define the bilinear form $\langle \cdot, \cdot \rangle : \mathcal{A}_{K,M}(n;q) \times H'_{I,J} \to \mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$ by

$$\langle (x_{K,M})^{e,v}, \tilde{T}'_{W_I w W_J} \rangle = \delta_{v,w}, \qquad (33)$$

where we assume that $v, w$ belong to $W_{+}^{I,J}$. This pairing of elements in $\mathcal{A}_{K,M}(n;q)$ with sums of elements in $H_n(q)$ is the beginning of a striking similarity between the two algebras. We explore this similarity further in Sections 5-6.
## 5 Duality between $H_n(q)$ and the immanant space $\mathcal{A}_{[n],[n]}(n; q)$

Many of the concepts and results summarized in Section 2 have analogs in the immanant space $\mathcal{A}_{[n],[n]}(n; q)$ of $\mathcal{A}(n; q)$, but are not easily found in the literature.

Analogous to the bar involution on $H_n(q)$ is an involution on $\mathcal{A}(n; q)$ again called the bar involution and again denoted $g \mapsto \bar{g}$. Following Brundan [1], we define this second bar involution by $\bar{q} = q^{-1}$, $\bar{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}, \qquad (34) $$

where $\alpha(a)$ is the number of pairs $i < j$ for which $a_i = a_j$. It is easy to see that the bar involution is well defined, i.e., that it respects the defining relations of $\mathcal{A}(n; q)$. We remark that the above bar involution differs by a power of $\bar{q}^{\frac{1}{2}}$ from those used by Du [8] and Zhang [16].

The restriction of this involution to $\mathcal{A}_{[n],[n]}(n; q)$ may be described by $\overline{x^{u,v}} = x^{w_0u,w_0v}$, i.e.,

$$ \overline{x_{u_1,v_1} \cdots x_{u_n,v_n}} = x_{u_n,v_n} \cdots x_{u_1,v_1}. \qquad (35) $$

It is easy to see that the elements $\{\overline{x^{e,v}} | v \in \mathfrak{S}_n\}$ form a basis of $\mathcal{A}_{[n],[n]}(n; q)$. Expressing these elements in terms of the natural basis, we have

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

where $\{S_{v,w}(q) | v, w \in \mathfrak{S}_n\}$ belong to $\mathbb{Z}[q]$. We will call these the S-polynomials.

**Proposition 5.1** For all $u, v \in \mathfrak{S}_n$ we have $q_{u,v}^{-1} S_{u,v}(q) = \epsilon_{u,v} \overline{q_{u,v}^{-1} R_{u,v}(q)}$.

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

In fact, since $\overline{q_{u,v}^{-1} R_{u,v}(q)} = \epsilon_{u,v} \overline{q_{u,v}^{-1} R_{u,v}(q)}$, we have $S_{u,v}(q) = R_{u,v}(q)$, but only the fact stated in the proposition will generalize nicely in Section 6. By the inversion formula [11, Sec. 3]

$$ \sum_{u \le v \le w} \epsilon_{u,v} S_{u,v}(q) R_{v,w}(q) = \delta_{u,w}, \qquad (37) $$

the bar involutions are compatible with the bilinear form on $\mathcal{A}_{[n],[n]}(n; q) \times H_n(q)$ defined in (33).

**Corollary 5.2** For all $u, v \in \mathfrak{S}_n$, we have $\langle \overline{x^{e,v}}, \overline{T_v} \rangle = \delta_{u,v}$.

Studying Lusztig's work [13] on canonical bases and other authors' work relating these to quantized Schur algebras and $\mathcal{A}(n; q)$, Du [7] defined a basis of $\mathcal{A}_{[n],[n]}(n; q)$ consisting of bar-invariant elements which we shall denote $\{\mathrm{Imm}_v(x) | v \in \mathfrak{S}_n\}$, which satisfy

$$ \mathrm{Imm}_v(x) \in x^{e,v} + \sum_{w>v} \overline{q^{\frac{1}{2}} Z[\overline{q^{\frac{1}{2}}}] x^{e,w}}. \qquad (38) $$

Writing $\mathrm{Imm}_v(x)$ in terms of the natural basis as

$$ \mathrm{Imm}_v(x) = \sum_{w \ge v} \epsilon_{v,w} \overline{q_{v,w}^{-1} Q_{v,w}(q)} x^{e,w}, \qquad (39) $$
we have that {$Q_{v,w}(q) | v, w \in W$} are precisely the inverse Kazhdan-Lusztig polynomials

$$Q_{v,w}(q) = P_{w_0 w, w_0 v}(q) = P_{ww_0, vw_0}(q) \quad (40)$$

defined in [11, Sec. 3], [12]. Note that $\mathrm{Imm}_v(x)$ is the $f$-immanant (26) corresponding to the function $f_v : \tilde{T}_w \mapsto \epsilon_{v,w} q_{e,v}^{-1} Q_{v,w}(q)$, and that $\mathrm{Imm}_e(x) = \det_q(x)$. (See also definitions in [1], [16] and nonquantum analogs in [14].) Observe that Equation (38) is equivalent to the conditions that $Q_{u,u}(q) = 1$ for all $u$, $Q_{u,v}(q) = 0$ for $u \not\le v$, and $\deg Q_{u,v}(q) \le \frac{1}{2}(\ell(v) - \ell(u) - 1)$ for $u < v$.

Uniqueness of this basis follows from rewriting the condition $\overline{\mathrm{Imm}}_v(x) = \mathrm{Imm}_v(x)$ as

$$q_{u,w}Q_{u,w}(q^{-1}) - q_{u,w}^{-1}Q_{u,w}(q) = \sum_{u<v\le w} q_{u,v}^{-1}S_{u,v}(q)q_{v,w}^{-1}Q_{v,w}(q) \quad \text{for all } u \le w. \quad (41)$$

In particular, there is a unique solution $Q_{u,w}(q)$ satisfying this equation, when all other polynomials appearing are known. Existence of the basis follows from a recursive definition involving the function $\mu$ defined in (10), or simply from the definitions in Equations (39)-(40) and a computation verifying bar invariance.

By the inversion formula for Kazhdan-Lusztig polynomials [11, Sec. 3]

$$\sum_{u \le v \le w} \epsilon_{u,v} Q_{u,v}(q) P_{v,w}(q) = \delta_{u,w}, \quad (42)$$

we therefore have for all $u, v \in \mathfrak{S}_n$ that

$$\langle \mathrm{Imm}_u(x), C'_v(q) \rangle = \delta_{u,v}, \quad (43)$$

and the basis of immanants {$\mathrm{Imm}_v(x) | v \in \mathfrak{S}_n$} for $\mathcal{A}_{[n],[n]}(n; q)$ is dual to the Kazhdan-Lusztig basis {$C'_v(q) | v \in \mathfrak{S}_n$} of $H_n(q)$.

# 6 Main results

Just as many properties of $H_n(q)$ generalize to a parabolic setting, the analogs of these properties for the immanant space $\mathcal{A}_{[n],[n]}(n; q)$ generalize to other multigraded components of $\mathcal{A}(n; q)$. We summarize these, paying particular attention to their role in defining the dual canonical basis of $\mathcal{A}(n; q)$, and providing a new, alternative formulation of this basis in Theorem 6.4.

Fix multisets $K, M$ of $[n]$ and use Equation (31) to define subsets $I = \iota(K), J = \iota(M)$ of generators of $\mathfrak{S}_r$. It is easy to see that the elements {$\{ (x_{K,M})^{e,v} | v \in \mathfrak{S}_n \}$} form a basis of $\mathcal{A}_{K,M}(n; q)$. Expressing these elements in terms of the natural basis, we have

$$\overline{(x_{K,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_{K,M})^{e,w} \quad (44)$$

where {$S_{v,w}^{I,J}(q) | v, w \in \mathfrak{S}_n$} belong to $\mathbb{Z}[q]$. Call these the *parabolic S-polynomials*.

Double-parabolic S-polynomials are related to ordinary S-polynomials by the following identity.
**Theorem 6.1** For all $u, w \in W_+^{I,J}$ we have

$$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 (45)$$

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

These polynomials also may be expressed in terms of double-parabolic R-polynomials as follows.

**Theorem 6.2** For all $u, v \in W_+^{I,J}$ we have $q_{u,v}^{-1} S_{u,v}^{I,J}(q) = \epsilon_{u,v} q_{u,v}^{-1} R_{u,v}^{I,J}(q)$. Furthermore, the matrix of double-parabolic S-polynomials inverts the matrix of double-parabolic R-polynomials in the sense that

$$\sum_{u \le v \le w} \epsilon_{u,v} S_{u,v}^{I,J}(q) R_{v,w}^{I,J}(q) = \delta_{u,w}. \qquad (46)$$

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

Thus the two bar involutions are compatible with the bilinear form on $\mathcal{A}_{K,M}(n; q) \times H'_{I,J}$ defined in (33).

**Corollary 6.3** For all $u, v \in W_+^{I,J}$, we have $\overline{(x_{K,M})^{e,u}, \tilde{T}'_{W_I w W_J}} = \delta_{u,v}$.

Du [7] formulates the dual canonical basis of $\mathcal{A}(n; q)$, as a union of bases of the multigraded components in Equation (24). The basis of the multigraded component $\mathcal{A}_{K,M}(n; q)$ consists of bar-invariant elements $\{\mathrm{Imm}_v^{K,M}(x) | v \in W_+^{I,J}\}$ satisfying

$$\mathrm{Imm}_v^{K,M}(x) \in (x_{K,M})^{e,v} + \sum_{\substack{w \in W_+^{I,J} \\ w > v}} q_w^{-1/2} \mathbb{Z}[q_w^{-1/2}] (x_{K,M})^{e,w}. \qquad (47)$$

Writing $\mathrm{Imm}_v^{K,M}(x)$ in terms of the natural basis of $\mathcal{A}_{K,M}(n; q)$ as

$$\mathrm{Imm}_v^{K,M}(x) = \sum_{\substack{w \in W_+^{I,J} \\ w \ge v}} \epsilon_{v,w} q_{v,w}^{-1} Q_{v,w}^{I,J}(q) (x_{K,M})^{e,w}, \qquad (48)$$

Du showed that the polynomials $\{Q_{v,w}(q) | v, w \in W\}$ are alternating sums of inverse Kazhdan-Lusztig polynomials

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

(See also [1], [16].) Observe that Equation (47) is equivalent to the conditions that $Q_{u,u}^{I,J}(q) = 1$ for all $u \in W_+^{I,J}$, $Q_{u,v}^{I,J}(q) = 0$ for $u \not\le v$, and $\deg Q_{u,v}^{I,J}(q) \le \frac{1}{2}(\ell(v) - \ell(u) - 1)$ for $u < v$.

Uniqueness of this basis follows from rewriting the condition $\overline{\mathrm{Imm}_v^{K,M}(x)} = \mathrm{Imm}_v^{K,M}(x)$ as

$$q_{u,w} Q_{u,w}^{I,J}(q^{-1}) - q_{u,v}^{-1} Q_{u,v}^{I,J}(q) = \sum_{\substack{v \in W_+^{I,J} \\ u < v \le w}} q_{u,v}^{-1} S_{u,v}^{I,J}(q) q_{v,w}^{-1} Q_{v,w}^{I,J}(q) \quad \text{for all } u \le w, u, w \in W_+^{I,J}. \qquad (50)$$
In particular, there is a unique solution $Q_{u,v}^{I,J}(q)$ satisfying this equation, when all other polynomials
appearing are known. Existence of the basis follows from the definitions in Equations (48), (49) and a
computation verifying bar-invariance. By the inversion formula [7, Sec. 1] for double-parabolic inverse
Kazhdan-Lusztig polynomials

$$
\sum_{\substack{v \in W_{+}^{I,J} \\ u \le v \le w}} \epsilon_{u,v} Q_{u,v}^{I,J}(q) P_{v,w}(q) = \delta_{u,w}, \qquad (51)
$$

we therefore have for all $u, v \in W_{+}^{I,J}$ that

$$
\langle \mathrm{Imm}_u^{K,M}(x), C'_v(q) \rangle = \delta_{u,v}, \qquad (52)
$$

and the subset of dual canonical basis elements {$\mathrm{Imm}_v^{K,M}(x) | v \in W_+^{I,J}$} belonging to $\mathcal{A}_{K,M}(n;q)$ is
dual to the Kazhdan-Lusztig basis {$C'_v(q) | v \in W_+^{I,J}$} of $\mathrm{H}'_{I,J}$.

Using all of the above facts about double-parabolic Kazhdan-Lusztig, R-, and S- polynomials, we can
now state and prove our main result, which expresses dual canonical basis elements for any multigraded
component of $\mathcal{A}(n; q)$ in terms of ordinary (inverse) Kazhdan-Lusztig polynomials.

**Theorem 6.4** Fix multisets $K, M$ and let $I = \iota(K)$. $J = \iota(M)$. For $v \in W_+^{I,J}$ we have

$$
\mathrm{Imm}_v^{K,M}(x) = \mathrm{Imm}_v(x_{K,M}). \qquad (53)
$$

**Proof:** Omitted.

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

This result generalizes the non-quantum immanant formulation in [15] of the dual canonical basis for
$\mathbb{C}[x_{1,1}, \dots, x_{n,n}]$, and shows that one can express the dual canonical basis of $\mathcal{A}(n; q)$ in terms of zero-
weight spaces of the quantum polynomial rings $\{\mathcal{A}(r; q) | r \ge 0\}$.

We remark that Deodhar [3], [4] associated the parameter $q$ to the inverse Kazhdan-Lusztig and $S$-polynomials above (when $I = \emptyset$ and $v, w \in W_+^{\emptyset, J}$), denoting $Q_{v,w}(q)$ and $S_{v,w}^{\emptyset, J}(q)$ by $\tilde{P}_{w_0vw_0^J, w_0ww_0^J}^J(q)$ and $\tilde{R}_{vw_0^J, ww_0^J}^J(q)$, respectively. Douglas [5] associated the parameter $-1$ to the same polynomials, denoting them $\tilde{P}_{w_0vW_J, w_0wW_J}(q)$ and $\tilde{R}_{vW_J, wW_J}(q)$, respectively.

**References**

[1] J. BRUNDAN. Dual canonical bases and Kazhdan-Lusztig polynomials. *J. Algebra*, **306**, 1 (2006) pp. 17–46.

[2] C. W. CURTIS. On Lusztig's isomorphism theorem for Hecke algebras. *J. Algebra*, **92**, 2 (1985) pp. 348–365.

[3] V. DEODHAR. On some geometric aspects of Bruhat orderings. II. The parabolic analogue of Kazhdan-Lusztig polynomials. *J. Algebra*, **111**, 2 (1987) pp. 483–506.

[4] V. DEODHAR. Duality in parabolic set up for questions in Kazhdan-Lusztig theory. *J. Algebra*, **142**, 1 (1991) pp. 201–209.
[5] J. M. DOUGLASS. An inversion formula for relative Kazhdan-Lusztig polynomials. *Comm. Algebra*, **18**, 2 (1990) pp. 371–387.

[6] V. G. DRINFELD. Hopf algebras and the quantum Yang-Baxter equation. *Dokl. Akad. Nauk. SSSR*, **283**, 5 (1985) pp. 1060–1064.

[7] J. DU. Canonical bases for irreducible representations of quantum $GL_n$. *Bull. London Math. Soc.*, **24**, 4 (1992) pp. 325–334.

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

[9] M. JIMBO. A $q$-difference analogue of $U(g)$ and the Yang-Baxter equation. *Lett. Math. Phys.*, **10**, 1 (1985) pp. 63–69.

[10] M. KASHIWARA. On crystal bases of the $Q$-analog of universal enveloping algebras. *Duke Math. J.*, **63** (1991) pp. 465–516.

[11] D. KAZHDAN AND G. LUSZTIG. Representations of Coxeter groups and Hecke algebras. *Invent. Math.*, **53** (1979) pp. 165–184.

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

[13] G. LUSZTIG. Canonical bases arising from quantized enveloping algebras. *J. Amer. Math. Soc.*, **3** (1990) pp. 447–498.

[14] B. RHOADES AND M. SKANDERA. Kazhdan-Lusztig immanants and products of matrix minors. *J. Algebra*, **304**, 2 (2006) pp. 793–811.

[15] M. SKANDERA. On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations. *J. Pure Appl. Algebra*, **212** (2008).

[16] H. ZHANG. On dual canonical bases. *J. Phys. A*, **37**, 32 (2004) pp. 7879–7893.