# A Quantization of a theorem of Goulden and Jackson

Matjaž Konvalinka<fnref n="1" /> and Mark Skandera<fnref n="2" />†

**Abstract.** A theorem of Goulden and Jackson which gives interesting formulae for character immanants also implies MacMahon's Master Theorem. We quantize Goulden and Jackson's theorem to give formulae for quantum character immanants in such a way as to obtain a known quantization of MacMahon's Master Theorem due to Garoufalidis-Lê-Zeilberger. In doing so, we also quantize formulae of Littlewood, Merris and Watkins concerning induced character immanants.

**Résumé.** Le Théorème Master de MacMahon peut être vu comme un corollaire d'un résultat de Goulden et Jackson décrivant certaines formules satisfaites par les caractères immanants. Dans cet article, on obtient une version quantitative des formules de Goulden et Jackson, ce qui permet de donner une nouvelle preuve du résultat de Garoufalidis, Lê et Zeilberger sur la quantification du Théorème Master de MacMahon. Ce faisant, on arrive aussi à quantifier les formules de Littlewood, Merris et Watkins concernant les caractères immanants induits.

**Keywords:** immanants, Hecke algebra

## 1 Introduction

Among their abundant results expressing generating functions in terms of matrix traces and determinants, Goulden and Jackson (8) obtained several identities concerning polynomials

$$ \mathrm{Imm}_{\lambda}(x) = \sum_{w \in S_n} \chi^{\lambda}(w) x_{1,w_1} \cdots x_{n,w_n} $$

in $x = (x_{1,1}, \dots, x_{n,n})$ whose coefficients are given by irreducible characters $\chi^{\lambda}$ of $S_n$. We will call these polynomials *irreducible character immanants*. Using their identities, Goulden and Jackson gave new presentations of results of Littlewood and Young and proved a generalization of MacMahon's celebrated Master Theorem. Also giving new interpretations of Littlewood's results, Merris and Watkins (13) stated similar formulae for irreducible (and other) character immanants by summing products of permanents and determinants.

<footnote n="1">¹MIT Department of Mathematics, 77 Massachusetts Ave., Cambridge, MA 02139, USA</footnote>

<footnote n="2">²Lehigh University Department of Mathematics, 14 East Packer Ave., Bethlehem, PA 18015, USA</footnote>

<footnote>†Supported by NSF grant 0701227</footnote>
Many of the above results have natural noncommutative extensions. Following authors such as Cartier-Foata (1), Garoufalidis-Lê-Zeilberger (6) and Konvalinka-Pak (10), who have stated quantum analogs of the Master Theorem, we will state quantum analogs of results of Goulden-Jackson and Merris-Watkins. As a consequence, we will also obtain a new proof of a quantized Master Theorem which is stated in (6). We review the relevant classical and quantum algebras in Sections 2-4 and state our main results in Section 5-6.

## 2 The symmetric group, $\mathbb{C}[x_{1,1}, \dots, x_{n,n}]$, and immanant formulae

Let $S_n$ be the symmetric group, and let $s_1, \dots, s_{n-1}$ be the standard adjacent transpositions generating $S_n$ and 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}
$$

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. $$

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}$. Thus, the one-line notation of $s_1 s_2 \in S_3$ is 312. 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. Equivalently, $\ell(w)$ is the number of inversions in the one-line notation of $w$. 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.

The ring $\mathbb{C}[x_{1,1}, \dots, x_{n,n}]$ is naturally graded by degree. For each $r \in \mathbb{N}$, the space of degree-$r$ polynomials decomposes further into subspaces indexed by multisets of $[r] = \{1, \dots, r\}$. In particular, we will consider the immanant space $\text{span}_{\mathbb{C}}\{x_{1,w_1} \cdots x_{n,w_n} \mid w \in S_n\}$. For a function $f : S_n \to \mathbb{C}$, we follow (16) in defining the $f$-immanant to be the element

$$ \text{Imm}_f(x) = \sum_{w \in S_n} f(w)x_{1,w_1} \cdots x_{n,w_n} $$

of the immanant space. Defining the notation $x^{u,v} = x_{u_1,v_1} \cdots x_{u_n,v_n}$, and $x^w = x^{e,w} = x_{1,w_1} \cdots x_{n,w_n}$, we may rewrite the natural basis of the immanant space as $\{x^w \mid w \in S_n\}$.

Let $\lambda = (\lambda_1, \dots, \lambda_\ell)$ be an integer partition (with $\ell > 0$) and let $\lambda^\top$ denote the transpose (a.k.a conjugate) of the integer partition $\lambda$. (See (5).) Immanants $\text{Imm}_{\chi^\lambda}(x)$ constructed from the irreducible characters $\chi^\lambda : S_n \to \mathbb{R}$ of $S_n$ are usually abbreviated $\text{Imm}_\lambda(x)$,

$$ \text{Imm}_{\lambda}(x) = \sum_{w \in S_n} \chi^{\lambda}(w)x^{w}. \qquad (1) $$

It is well known that irreducible characters are class functions on $S_n$ in the sense that if $v$ and $w$ have the same cycle type in $S_n$, then $\chi^\lambda(v)$ and $\chi^\lambda(w)$ are equal. Equivalently, we have $\chi^\lambda(v) = \chi^\lambda(w)$ if
$v = uwu^{-1}$ for some $u \in S_n$. For each class function $f: S_n \to \mathbb{C}$, we will call the immanant $\mathrm{Imm}_f(x)$ a class immanant.

Class immanants which are somewhat better understood than irreducible character immanants correspond to characters $\{\epsilon^\lambda | \lambda \vdash n\}$ induced from the sign character of Young subgroups of $S_n$ and to characters $\{\eta^\lambda | \lambda \vdash n\}$ induced from the trivial character of Young subgroups of $S_n$. Indeed, we have quite simple formulas for these immanants in terms of determinants and permanents of submatrices of $x$ which we denote by $x_{I,J} = (x_{i,j})_{i \in I, j \in J}$. In particular, Littlewood (11) and Merris and Watkins (13) showed that for $\lambda = (\lambda_1, \dots, \lambda_\ell) \vdash n$, we have

$$ \mathrm{Imm}_{\epsilon^{\lambda}}(x) = \sum_{(I_1, \dots, I_{\ell})} \det(x_{I_1, I_1}) \cdots \det(x_{I_{\ell}, I_{\ell}}), \\ \mathrm{Imm}_{\eta^{\lambda}}(x) = \sum_{(I_1, \dots, I_{\ell})} \mathrm{per}(x_{I_1, I_1}) \cdots \mathrm{per}(x_{I_{\ell}, I_{\ell}}), \qquad (2) $$

where the sums are over all sequences $(I_1, \dots, I_\ell)$ of pairwise disjoint subsets of $[n]$ satisfying $|I_j| = \lambda_j$.

Each of the sets $\{\chi^\lambda | \lambda \vdash n\}$, $\{\eta^\lambda | \lambda \vdash n\}$, $\{\epsilon^\lambda | \lambda \vdash n\}$ forms a basis for the space of class functions on $S_n$. We may express the first basis in terms of the others by

$$ \chi^{\lambda} = \sum_{\mu} K_{\mu, \lambda}^{-1} \eta^{\mu} = \sum_{\mu} K_{\mu, \lambda}^{-1} \epsilon^{\mu}, \qquad (3) $$

and we therefore may express irreducible character immanants in terms of the induced character immanants by

$$ \mathrm{Imm}_{\lambda}(x) = \sum_{\mu} K_{\mu, \lambda}^{-1} \mathrm{Imm}_{\eta^{\mu}}(x) = \sum_{\mu} K_{\mu, \lambda}^{-1} \mathrm{Imm}_{\epsilon^{\mu}}(x). \qquad (4) $$

The coefficients appearing in these identities are called inverse Kostka numbers and may be defined by

$$ \det(\xi_{\lambda_i + j - i})_{i,j=1}^{\ell} = \sum_{\mu \vdash n} K_{\mu, \lambda}^{-1} \xi_{\mu_1} \cdots \xi_{\mu_\ell}, \qquad (5) $$

where $\{\xi_i | i > 0\}$ are commuting indeterminates, and where we define $\xi_0 = 1$, and $\xi_i = 0$ for $i \le -1$.

## 3 Goulden and Jackson's formulae

Goulden and Jackson identified three multivariate generating functions which are related to the irreducible character immanants $\{\mathrm{Imm}_\lambda(x) | \lambda \vdash n\}$. For the convenience of the reader, we will summarize results and proofs from (8, §2-3) in a way which will facilitate our quantum analogs in Section 5.

To begin, let $t$ be a variable, let $z = (z_1, \dots, z_n)$ be a sequence of $n$ variables, and let $\mathrm{diag}(z)$ be the $n \times n$ matrix whose diagonal entries are $z_1, \dots, z_n$. Define the sequences $(\alpha_k)_{k \in \mathbb{Z}}$, $(\beta_k)_{k \in \mathbb{Z}}$, $(\gamma_k)_{k \in \mathbb{Z}}$, $(\delta_k)_{k \in \mathbb{Z}}$ of polynomials in $\mathbb{Z}[z][x]$ by the generating functions

$$ \det(I + t \operatorname{diag}(z)x) = \sum_{k=0}^{n} \alpha_k t^k, \qquad \frac{1}{\det(I - t \operatorname{diag}(z)x)} = \sum_{k \ge 0} \beta_k t^k, \\ \mathrm{per}(I + t \operatorname{diag}(z)x) = \sum_{k=0}^{n} \gamma_k t^k, \qquad \frac{1}{\mathrm{per}(I - t \operatorname{diag}(z)x)} = \sum_{k \ge 0} \delta_k t^k, \qquad (6) $$
and by the requirement that polynomials with indices not appearing here be zero. Now define the $\lambda_1 \times \lambda_1$ matrices $A, D$ and the $\ell \times \ell$ matrices $B, C$ by

$$A = (\alpha_{\lambda_i^\top - i + j}), \quad B = (\beta_{\lambda_i - i + j}), \quad C = (\gamma_{\lambda_i - i + j}), \quad D = (\delta_{\lambda_i^\top - i + j}). \quad (7)$$

Summarizing the main results (8, Thm. 2.1, Cor. 2.3) on irreducible character immanants, we have the following.

**Theorem 3.1** The coefficients of $z_1 \cdots z_n$ in $\det(A), \det(B), \det(C)$ and $\det(D)$ are equal to $\mathrm{Imm}_{\lambda}(x)$.

Given a multiset $K = 1^{k_1} 2^{k_2} \cdots n^{k_n}$ with $k_1 + \cdots + k_n = r$, we define the $K, K$ generalized submatrix of $x$ to be the $r \times r$ matrix $x_{K,K}$ obtained from $x$ by repeating the $i$th row and column $k_i$ times each. (This is called the $K$-replication of $x$ in (8).) For example when $K = 1112$, we have $k_1 = 3, k_2 = 1$, and

$$x_{K,K} = \begin{bmatrix} x_{1,1} & x_{1,1} & x_{1,1} & x_{1,2} \\ x_{1,1} & x_{1,1} & x_{1,1} & x_{1,2} \\ x_{1,1} & x_{1,1} & x_{1,1} & x_{1,2} \\ x_{2,1} & x_{2,1} & x_{2,1} & x_{2,2} \end{bmatrix}.$$

From the preceding results, Goulden and Jackson (8, Thm. 3.3) derive MacMahon's Master Theorem (12) as follows.

**Theorem 3.2** The coefficients of $z_1^{k_1} \cdots z_n^{k_n}$ in $\det(I - \mathrm{diag}(z)x)^{-1}$ and

$$\left(\sum_{j=1}^{n} x_{1,j} z_j\right)^{k_1} \cdots \left(\sum_{j=1}^{n} x_{n,j} z_j\right)^{k_n} \qquad (8)$$

are both equal to $\mathrm{per}(x_{K,K})/(k_1! \cdots k_n!)$.

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

# 4 The Hecke algebra and quantum polynomial ring

In order to state and prove quantum analogs of the results of Littlewood-Merris-Watkins and Goulden-Jackson, we review some facts about the relevant algebras.

The Hecke algebra $H_n(q)$ is the $\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$-algebra generated either by the set $\{T_{s_i} | 1 \le i \le n-1\}$ of natural generators, or equivalently by the set $\{\tilde{T}_{s_i} | 1 \le i \le n-1\}$ of modified natural generators, subject to the relations

$$ \begin{aligned} T_{s_i}^2 &= (q-1)T_{s_i} + q, & \tilde{T}_{s_i}^2 &= (q^{\frac{1}{2}} - q^{-\frac{1}{2}})\tilde{T}_{s_i} + 1, & \text{for } i=1, \dots, n-1, \\ T_{s_i} T_{s_j} T_{s_i} &= T_{s_j} T_{s_i} T_{s_j}, & \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, \\ T_{s_i} T_{s_j} &= T_{s_j} T_{s_i}, & \tilde{T}_{s_i} \tilde{T}_{s_j} &= \tilde{T}_{s_j} \tilde{T}_{s_i}, & \text{if } |i-j| \ge 2. \end{aligned} $$

The natural and modified natural generators are related by $\tilde{T}_{s_i} = q^{-\frac{1}{2}} T_{s_i}$. If $s_{i_1} \cdots s_{i_\ell}$ is a reduced expression for $w \in S_n$ we define

$$T_w = T_{s_{i_1}} \cdots T_{s_{i_\ell}}, \quad \tilde{T}_w = q^{-\frac{\ell}{2}} T_w = \tilde{T}_{s_{i_1}} \cdots \tilde{T}_{s_{i_\ell}}, \quad T_e = \tilde{T}_e = 1.$$
We shall call the elements {$T_w | w \in S_n$} and {$\tilde{T}_w | w \in S_n$} the natural basis and modified natural basis, respectively, of $H_n(q)$ as a $\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$-module. Specializing $H_n(q)$ at $q^{\frac{1}{2}} = 1$, we obtain the classical group algebra $\mathbb{C}[S_n]$ of the symmetric group.

One multiplies modified natural basis elements by recursively using either of the formulas

$$ \tilde{T}_{s_i} \tilde{T}_w = \begin{cases} \tilde{T}_{s_i w} & \text{if } s_i w > w, \\ \tilde{T}_{s_i w} + (q^{\frac{1}{2}} - q^{-\frac{1}{2}}) \tilde{T}_w & \text{if } s_i w < w, \end{cases} \\ \\ \tilde{T}_w \tilde{T}_{s_i} = \begin{cases} \tilde{T}_{w s_i} & \text{if } w s_i > w, \\ \tilde{T}_{w s_i} + (q^{\frac{1}{2}} - q^{-\frac{1}{2}}) \tilde{T}_w & \text{if } w s_i < w, \end{cases} \tag{9} $$

and thus obtains elements $c_{u,v}^w \in \mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$ occurring as coefficients in the expression

$$ \tilde{T}_u \tilde{T}_v = \sum_w c_{u,v}^w \tilde{T}_w. \tag{10} $$

By the symmetry of the formulae (9), one sees that $c_{u,v}^w = c_{v^{-1},u^{-1}}^{w^{-1}}$.

**Lemma 4.1** The coefficients {$c_{u,v}^w | u, v, w \in S_n$} satisfy $c_{u,v}^w = c_{v,w^{-1}}^{u^{-1}}$.

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

A second noncommutative $\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$-algebra is called the quantum polynomial ring $\mathcal{A}(n; q)$. It is generated by $n^2$ variables $x = (x_{1,1}, \dots, x_{n,n})$ representing matrix entries, subject to the relations

$$ \begin{align} x_{i,\ell}x_{i,k} &= q^{\frac{1}{2}}x_{i,k}x_{i,\ell}, \notag \\ x_{j,k}x_{i,k} &= q^{\frac{1}{2}}x_{i,k}x_{j,k}, \tag{11} \\ x_{j,k}x_{i,\ell} &= x_{i,\ell}x_{j,k}, \notag \\ x_{j,\ell}x_{i,k} &= x_{i,k}x_{j,\ell} + (q^{\frac{1}{2}} - q^{-\frac{1}{2}})x_{i,\ell}x_{j,k}, \notag \end{align} $$

for all indices $i < j$, $k < \ell$. The quantum polynomial ring often arises in conjunction with the quantum coordinate ring of $SL(n, \mathbb{C})$, which may be expressed as $\mathcal{O}_q SL(n, \mathbb{C}) \cong \mathcal{A}(n; q)/(\det(x; q) - 1)$, where

$$ \det(x; q) = \sum_{w \in S_n} (-q^{-\frac{1}{2}})^{\ell(w)} x_{1,w_1} \cdots x_{n,w_n} = \sum_{w \in S_n} (-q^{-\frac{1}{2}})^{\ell(w)} x_{w_1,1} \cdots x_{w_n,n} \tag{12} $$

is the quantum determinant. (We caution the reader that the second equality above is implied by the third relation in (11), and does not hold in an arbitrary noncommutative ring in $n^2$ variables.) 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}}, 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. It is easy to see that the monomials {$x^{u,v} | u, v \in S_n$} satisfy

$$ x^{s_i u, v} = \begin{cases} x^{u, s_i v} & \text{if } s_i u > u \text{ and } s_i v > v, \text{ or if } s_i u < u \text{ and } s_i v < v, \\ x^{u, s_i v} + (q^{\frac{1}{2}} - q^{-\frac{1}{2}}) x^{u, v} & \text{if } s_i u > u \text{ and } s_i v < v, \\ x^{u, s_i v} - (q^{\frac{1}{2}} - q^{-\frac{1}{2}}) x^{u, v} & \text{if } s_i u < u \text{ and } s_i v > v. \end{cases} \tag{13} $$
Thus for all $w \in S_n$ we have the identity $x^{e,w} = x^{w^{-1},e}$. On the other hand, we do not in general have the equality of $x^{w,v}$ and $x^{w^{-1},v^{-1}}$.

$\mathcal{A}(n; q)$ has a natural grading by degree, $\mathcal{A}(n; q) = \bigoplus_{r \ge 0} \mathcal{A}_r$, where $\mathcal{A}_r$ is the $\mathbb{C}[q^{\frac{1}{2}}, 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\}$ of bases of the homogeneous components $\{\mathcal{A}_r | r \ge 0\}$.

We may further decompose each homogeneous component $\mathcal{A}_r$ by considering pairs $(K, M)$ of multisets of integers. Thus we obtain the multigrading

$$ \mathcal{A}_r = \bigoplus_{\substack{K,M \\ |K|=|M|=r}} \mathcal{A}_{K,M}, \qquad (14) $$

where $\mathcal{A}_{K,M}$ is the $\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$-span of monomials whose row indices and column indices (with multiplicity) are equal to the multisets $K$ and $M$, respectively. Just as the $\mathbb{Z}$-graded components $\mathcal{A}_r$ and $\mathcal{A}_s$ satisfy $\mathcal{A}_r \mathcal{A}_s \subset \mathcal{A}_{r+s}$, the multigraded components $\mathcal{A}_{K,M}$ and $\mathcal{A}_{K',M'}$ satisfy $\mathcal{A}_{K,M} \mathcal{A}_{K',M'} \subset \mathcal{A}_{K \cup K', M \cup M'}$, where $\cup$ denotes the *multiset union* of two multisets,

$$ 1^{k_1} \cdots n^{k_n} \cup 1^{k'_1} \cdots n^{k'_n} = \underset{\text{def}}{1^{k_1+k'_1} \cdots n^{k_n+k'_n}}. $$

Thus $\mathcal{A}_{[n],[n]}$ is the $\mathbb{C}[q^{\frac{1}{2}}, 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 S_n\}, $$

which we will again write as $\{x^{e,w} = x^w | w \in S_n\}$. We will call elements of this submodule *quantum immanants*. In particular, for any $\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$-linear function $f: H_n(q) \to \mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$, we define the *quantum f-immanant*

$$ \mathrm{Imm}_f(x; q) = \sum_{w \in S_n} f(\tilde{T}_w) x^w. $$

One important quantum immanant is the quantum determinant,

$$ \det(x; q) = \sum_{w \in S_n} (-q^{-\frac{1}{2}})^{\ell(w)} x^w, $$

which corresponds to the Hecke algebra sign character $\chi_q^{1^n} : \tilde{T}_w \mapsto (-q^{-\frac{1}{2}})^{\ell(w)}$. Another is the quantum permanent

$$ \mathrm{per}(x; q) = \sum_{w \in S_n} (q^{\frac{1}{2}})^{\ell(w)} x^w, $$

which corresponds to the Hecke algebra trivial character $\chi_q^n : \tilde{T}_w \mapsto (q^{\frac{1}{2}})^{\ell(w)}$.

# 5 Formulae for quantum character immanants

In analogy to the $S_n$ irreducible character immanants, we will construct quantum immanants $\mathrm{Imm}_{\chi_q^{\lambda}}(x; q)$ from the irreducible characters $\chi_q^{\lambda}: H_n(q) \to \mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$ of $H_n(q)$, and we will abbreviate these
Imm$_{λ}$(x; q),

$$
\mathrm{Imm}_{\lambda}(x; q) = \sum_{w \in S_n} \chi_q^{\lambda}(\tilde{T}_w) x^w = \sum_{w \in S_n} \chi_q^{\lambda}(T_w) (-q^{-\frac{1}{2}})^{\ell(w)} x^w. \quad (15)
$$

Two examples, as we have mentioned, are the quantum determinant and quantum permanent. Note that a Hecke algebra character $\chi_q$ (i.e., the trace of any matrix representation) is not an $S_n$-class function in the sense that $\chi_q(\tilde{T}_v)$ and $\chi_q(\tilde{T}_{u^{-1}vu})$ are not in general equal (equivalently, $\chi_q(T_v)$ and $\chi_q(T_{u^{-1}vu})$ are not in general equal). On the other hand, $\chi_q$ is a class function in the sense one would expect: we have
$\chi_q(\tilde{T}_v) = \chi_q(\tilde{T}_u^{-1}\tilde{T}_v\tilde{T}_u)$.

Class functions on $H_n(q)$ are completely determined by their values on natural basis elements $T_v$ for which $v$ has the cycle notation of the form

$$
\gamma_{\mu} = (1, 2, \dots, \mu_1)(\mu_1 + 1, \mu_1 + 2, \dots, \mu_2) \dots
$$

for some composition $\mu$. This fact facilitates the creation of character tables and formulae as in (9), (14), and motivates the use of a second basis for $\mathcal{A}_{[n],[n]}$. For a permutation $w$ with cycle notation

$$
(i_1^1, \dots, i_{m_1}^1)(i_1^2, \dots, i_{m_2}^2) \dots,
$$

where $i_1^j$ is the smallest element of the $j$-th cycle and $i_1^1 < i_1^2 < \dots$, define

$$
x_w = x_{i_1^1, i_2^1, \dots, i_{m_1}^1} x_{i_1^2, i_2^2, \dots, i_{m_2}^2} x_{i_1^3, i_2^3, \dots, i_{m_3}^3} \dots
$$

For example, $x_{45213} = x_{1,4}x_{4,1}x_{2,5}x_{5,3}x_{3,2}$. The monomials $\{x_w \mid w \in S_n\}$ form a basis of $\mathcal{A}_{[n],[n]}$ and reconcile the difference between $S_n$-class functions and $H_n(q)$-class functions as follows.

**Lemma 5.1** Let $f : H_n(q) \to \mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$ be an $H_n(q)$-class function. Then we have

$$
\mathrm{Imm}_f(x; q) = \sum_{w \in S_n} f(\tilde{T}_{\gamma_{\mu(w)}})x_w,
$$

where $\mu(w)$ is the cycle type of $w$.

**Proof:** Omitted.

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

In particular, the coordinates of Imm$_{λ}$(x; q) with respect to the basis {$x_w | w \in S_n$} are class functions on S_n in the usual sense.

Quantum analogs of the immanants $\{\mathrm{Imm}_{e\lambda}(x) | \lambda \vdash n\}$ and $\{\mathrm{Imm}_{\eta\lambda}(x) | \lambda \vdash n\}$ correspond to characters $\{e_q^\lambda | \lambda \vdash n\}$ and $\{\eta_q^\lambda | \lambda \vdash n\}$ induced from the sign character and trivial character of Hecke algebras of Young subgroups of $S_n$.

Let $J$ be a subset of the standard generators $\{s_1, \dots, s_{n-1}\}$ of $W = S_n$ and let $W_J$ be the correspond-
ing parabolic subgroup of $W$. Let $W/W_J$ be the set of cosets of the form $uW_J$. Each such coset is an
interval in the Bruhat order and thus has a unique minimal element and a unique maximal element. Let
$W_J^-$ be the set of minimal representatives of cosets in $W/W_J$. It is well known that we have

$$
\begin{align*}
W_{-}^{J} &= \{w \in S_n \mid ws_i > w \text{ for all } s_i \in J\} \\
&= \{w \in S_n \mid siw^{-1} > w^{-1} \text{ for all } s_i \in J\} \tag{16} \\
&= \{w \mid i \text{ appears before } i+1 \text{ in } w_1 \cdots w_n \text{ for all } s_i \in J\} \\
&= \{w \mid w_i^{-1} < w_{i+1}^{-1} \text{ for all } s_i \in J\}.
\end{align*}
$$
To prove quantum analogs of the formulae (2), we consider elements of $H_n(q)$ which are often used in conjunction with parabolic subalgebras. (See, e.g., (2), (3), (4).) For each permutation $u \in W_-$, define the Hecke algebra elements

$$T_{uW_J} = \tilde{T}_u \sum_{y \in W_J} (-q^{-\frac{1}{2}})^{\ell(y)} \tilde{T}_y, \quad T'_{uW_J} = \tilde{T}_u \sum_{y \in W_J} (q^{\frac{1}{2}})^{\ell(y)} \tilde{T}_y. \qquad (17)$$

Note that if $J = \emptyset$ then each coset $W/W_J$ is a single element $u \in S_n$ and we have $T'_{uW_J} = T_{uW_J} = \tilde{T}_u$.

The elements (17) are used to construct induced representations as follows. Given a partition $\lambda = (\lambda_1, \dots, \lambda_\ell)$ of $n$, choose any rearrangement $\nu = (\nu_1, \dots, \nu_\ell)$ of $\lambda$ and define the subset $J$ of generators of $S_n$ by

$$J = \{s_1, \dots, s_{n-1}\} \setminus \{s_{\nu_1}, s_{\nu_1+\nu_2}, \dots, s_{\nu_1+\dots+\nu_{\ell-1}}\}. \qquad (18)$$

Letting $H_n(q)$ act by left multiplication on the $\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]$-spans of coset sums

$$\operatorname{span}_{\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]} \{T_{uW_J} | u \in W_{-}^{J}\}, \quad \operatorname{span}_{\mathbb{C}[q^{\frac{1}{2}}, q^{-\frac{1}{2}}]} \{T'_{uW_J} | u \in W_{-}^{J}\}, \qquad (19)$$

we obtain the $H_n(q)$ modules corresponding to induction of the sign and trivial characters (respectively) of the Young subalgebras of type $\lambda$. For each $w \in S_n$, the two matrices representing $\tilde{T}_w$ have entries indexed by permutations $u, v \in W_-^J$, which we describe as follows.

**Lemma 5.2** Fix $w$ in $S_n$ and $u, v$ in $W_-^J$. For the above constructions of the induced sign and trivial $H_n(q)$ modules, the $u, v$ entries of the matrices representing $\tilde{T}_w$ are equal to the coefficients of $\tilde{T}_w$ in $\tilde{T}_u T_{W_J} \tilde{T}_{v^{-1}}$ and $\tilde{T}_u T'_{W_J} \tilde{T}_{v^{-1}}$ respectively.

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

From this fact, we obtain the following Hecke algebra “generating functions” for induced characters.

**Lemma 5.3** Let $\lambda, \nu$ and $J$ be as above. Then we have

$$\sum_{v \in W_{-}^{J}} \tilde{T}_{v} T_{W_{J}} \tilde{T}_{v^{-1}} = \sum_{w \in S_{n}} \epsilon_{q}^{\lambda}(\tilde{T}_{w}) \tilde{T}_{w}, \quad \sum_{v \in W_{-}^{J}} \tilde{T}_{v} T'_{W_{J}} \tilde{T}_{v^{-1}} = \sum_{w \in S_{n}} \eta_{q}^{\lambda}(\tilde{T}_{w}) \tilde{T}_{w}.$$

**Proof:** Using Lemma 5.2 and summing over diagonal matrix entries, we obtain the desired equalities. $\square$

These Hecke algebra generating functions in turn are related to quantum immanants by the actions of $H_n(q)$ on $\mathcal{A}_{[n],[n]}$ defined by

$$\tilde{T}_{s_i} \circ x^{e,v} = x^{s_i,v} = \begin{cases} x^{e,s_i v} & \text{if } s_i v > v, \\ x^{e,s_i v} + (q^{\frac{1}{2}} - q^{-\frac{1}{2}})x^{e,v} & \text{if } s_i v < v, \end{cases} \qquad (20) \\ x^{e,v} \circ \tilde{T}_{s_i} = x^{v^{-1},e} \circ \tilde{T}_{s_i} = x^{v^{-1},s_i} = \begin{cases} x^{e,vs_i} & \text{if } vs_i > v, \\ x^{e,vs_i} + (q^{\frac{1}{2}} - q^{-\frac{1}{2}})x^{e,v} & \text{if } vs_i < v. \end{cases}$$

A straightforward but tedious computation shows that the left and right actions commute. By the definitions, it is easy to see that we have $\tilde{T}_v \circ x^{e,e} = x^{e,e} \circ \tilde{T}_v = x^{e,v}$ for all $v \in S_n$. On the other hand, we do not in general have the equality of $\tilde{T}_v \circ x^{e,w}$ and $x^{e,w} \circ \tilde{T}_v$. One consequence of the definitions (20) is the following formula.
**Lemma 5.4** For all $v \in W_{-}^J$, $y \in W_J$, we have $\tilde{T}_v \circ x^e, y \circ \tilde{T}_{v^{-1}} = x^{v^{-1}, yv^{-1}}$.

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

Now we quantize the formulae (2) as follows.

**Theorem 5.5** Let $\lambda = (\lambda_1, \dots, \lambda_\ell)$ be a partition of $n$ and fix any rearrangement $\nu = (\nu_1, \dots, \nu_\ell)$ of $\lambda$. Then we have

$$ \mathrm{Imm}_{\epsilon_q^{\lambda}}(x;q) = \sum_{(I_1, \dots, I_{\ell})} \det(x_{I_1, I_1}; q) \cdots \det(x_{I_{\ell}, I_{\ell}}; q), \qquad (21) $$

$$ \mathrm{Imm}_{\eta_q^{\lambda}}(x;q) = \sum_{(I_1, \dots, I_{\ell})} \mathrm{per}(x_{I_1, I_1}; q) \cdots \mathrm{per}(x_{I_{\ell}, I_{\ell}}; q), $$

where the sums are over all sequences $(I_1, \dots, I_\ell)$ of pairwise disjoint subsets of $[n]$ satisfying $|I_j| = \nu_j$.

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

Just as inverse Kostka numbers describe the expansions of induced sign and trivial characters of $S_n$ in terms of irreducible $S_n$ characters, these numbers also describe the expansions of induced sign and trivial characters of $H_n(q)$ in terms of irreducible $H_n(q)$ characters. (No “quantum analog” of inverse Kostka numbers is needed for this purpose. See (7, §9.1.9).) Specifically we have

$$ \chi_q^{\lambda} = \sum_{\mu} K_{\mu, \lambda}^{-1} \eta_{q}^{\mu} = \sum_{\mu} K_{\mu, \lambda}^{-1} \epsilon_{q}^{\mu}. \qquad (22) $$

Now let us quantize the Goulden-Jackson generating functions (6). Letting $t$ and $z = (z_1, \dots, z_n)$ be commuting variables and letting $x = (x_{1,1}, \dots, x_{n,n})$ be noncommuting variables satisfying the relations of the quantum polynomial ring $\mathcal{A}(n; q)$, we define the sequences $(\alpha_k)_{k \in \mathbb{Z}}$, $(\beta_k)_{k \in \mathbb{Z}}$, $(\gamma_k)_{k \in \mathbb{Z}}$, $(\delta_k)_{k \in \mathbb{Z}}$ of polynomials in $\mathcal{A}(n; q)[z]$ the generating functions

$$ \det(I + t \operatorname{diag}(z)x; q) = \sum_{k=0}^{n} \alpha_k t^k, \qquad \frac{1}{\det(I - t \operatorname{diag}(z)x; q)} = \sum_{k \ge 0} \beta_k t^k, \qquad (23) $$

$$ \mathrm{per}(I + t \operatorname{diag}(z)x; q) = \sum_{k=0}^{n} \gamma_k t^k, \qquad \frac{1}{\mathrm{per}(I - t \operatorname{diag}(z)x; q)} = \sum_{k \ge 0} \delta_k t^k, $$

and again by the requirement that polynomials with indices not appearing here be zero. In terms of these sequences, define the $\lambda_1 \times \lambda_1$ matrices $A, D$ and the $\ell \times \ell$ matrices $B, C$ as before,

$$ A = (\alpha_{\lambda_i^T - i + j}), \quad B = (\beta_{\lambda_i - i + j}), \quad C = (\gamma_{\lambda_i - i + j}), \quad D = (\delta_{\lambda_i^T - i + j}). \qquad (24) $$

To provide a quantum analog of Theorem 3.1, we must evaluate some form of the determinant at the matrices defined in (24). We will work in the quotient

$$ R = \mathcal{A}(n; q)[z]/(z_1^2, \dots, z_n^2) $$

and will take classical determinants of the matrices $A, B, C, D$. The following commutative properties of the sequences defined in (23) justify our use of $R$ and of the classical determinant.
**Proposition 5.6** The polynomials {$\alpha_k | k \in \mathbb{Z}$} in $\mathcal{A}(n; q)[z]$ commute modulo the ideal $(z_1^2, \dots, z_n^2)$, as do the polynomials in each of the sets {$\beta_k | k \in \mathbb{Z}$}, {$\gamma_k | k \in \mathbb{Z}$}, {$\delta_k | k \in \mathbb{Z}$}.

**Proof:** Omitted. □

**Theorem 5.7** Computing in $R$, we have that the coefficients of $z_1 \cdots z_n$ in the nonquantum determinants $\det(A)$, $\det(B)$, $\det(C)$, and $\det(D)$ are all equal to $\mathrm{Imm}_\lambda(x; q)$.

**Proof:** Omitted. □

For each nonnegative integer $k$, define the quantum analog of $k$ by $(k)_q = 1 + q^{\frac{1}{2}} + q^{\frac{2}{2}} + \cdots + q^{\frac{k-1}{2}}$ and the quantum factorial function ! by $k)_q! = (1)_q \cdot (2)_q \cdots (k)_q$. Note that the evaluation of the above expressions at $q^{\frac{1}{2}} = 1$ gives the classical nonnegative integers and factorial function.

Now we obtain the following quantized Master Theorem, which first appeared in (6, Thm. 1).

**Theorem 5.8** Let $K = 1^{k_1} \cdots n^{k_n}$ be an $r$-element multiset of $[n]$. Let $y = (y_1, \dots, y_n)$ be a vector of quasicommuting variables satisfying $y_j y_i = q^{\frac{1}{2}} y_i y_j$ if $i < j$, let $z = (z_1, \dots, z_n)$ be a vector of commuting variables, and let $y$ and $z$ commute with $x$. Then we have that the coefficient of $z_1^{k_1} \cdots z_n^{k_n}$ in $\det(I - \mathrm{diag}(z)x; q)^{-1}$ and the coefficient of $y_1^{k_1} \cdots y_n^{k_n}$ in $(\sum_{j=1}^n x_{1,j} y_j)^{k_1} \cdots (\sum_{j=1}^n x_{n,j} y_j)^{k_n}$ are both equal to $\mathrm{per}(x_{K,K}; q)/((k_1)_q! \cdots (k_n)_q!)$.

**Proof:** Omitted. □

# 6 Combinatorial interpretation of characters of the Hecke algebra

Theorem 5.5 can be used to (re)prove the combinatorial interpretation of $\eta_q^\lambda(\tilde{T}_{\gamma_\mu})$ (given implicitly by Ram (14, Theorem 4.1)), $\epsilon_q^\lambda(\tilde{T}_{\gamma_\mu})$ and $\chi_q^\lambda(\tilde{T}_{\gamma_\mu})$ (given by Ram and Remmel (15, Theorem 3)).

We proved in Theorem 5.5 that

$$ 
\begin{aligned}
\eta_q^\lambda(\tilde{T}_{\gamma_\mu}) &= [x^w] \mathrm{Imm}_{\eta_q^\lambda} x = \sum_{(I_1, \dots, I_p)} [x^w] \mathrm{per}(x_{I_1}; q) \cdots \mathrm{per}(x_{I_p}; q) = \\
&= \sum_{\pi \in S_m} q^{(\ell(\pi) - \ell(\sigma))/2} [x^w] x_{\sigma_1, \pi_1} x_{\sigma_2, \pi_2} \cdots x_{\sigma_n, \pi_n} = \sum_{\pi \in S_m} q^{(\ell(\pi) - \ell(\sigma))/2} [x^w] x_{\sigma, \pi},
\end{aligned}
$$

where $\pi = w\sigma$, $w \in S_J$, $\sigma \in W_J^J$ (such $w$ and $\sigma$ are unique).

Take a permutation $\pi \in S_m$. Denote by $\mathcal{J}$ the $r$-tuple $(J_1, \dots, J_r)$ of multisets $J_k$ so that $J_k$ contains a copy of $j$ for every $i$ with $\lambda_1 + \dots + \lambda_{j-1} < i \le \lambda_1 + \dots + \lambda_j$ and $\mu_1 + \dots + \mu_{k-1} < \pi^{-1}(i) \le \mu_1 + \dots + \mu_k$. Clearly, $J_k$ has $\mu_k$ elements, and there are $\lambda_j$ copies of $j$ in $\cup J_k$.

**Theorem 6.1** Take $w = \gamma_\mu$ for some composition $\mu$. The map $\varphi = \varphi_{\lambda,\mu}: \pi \mapsto \mathcal{J}$ is a bijection between the set of $\pi$ with $[x^w]a_{\sigma,\pi} \ne 0$ and the set of $r$-tuples $\mathcal{J} = (J_1, \dots, J_r)$ of multisets $J_k$ for which $|J_k| = \mu_k$ and for which $\cup J_k$ contains $\lambda_j$ copies of $j$. Furthermore, in this case

$$ q^{\ell(\pi) - \ell(\sigma)} [x^w] a_{\sigma, \pi} = q^{(r-m)/2} q^{\sum_{j=N-(J_j)} (q-1) \sum_{j=N-(J_j)} 2}, $$
where $N_+(J) = |\{j < r : i_j = i_{j+1}\}|$, $N_-(J) = |\{j < r : i_j < i_{j+1}\}|$ for $J = (i_1, \dots, i_r)$.
**Proof:** Omitted. □

The theorem immediately yields a combinatorial description of $\eta_q^\lambda$ and $\epsilon_q^\lambda$. In order to prove the combinatorial description of the irreducible characters $\chi_q^\lambda$, we need the following. Note that this result was already proved in (15), see equation (22) and the remark following it.

Recall that a border strip is a connected skew shape with no $2 \times 2$ square. Equivalently, a skew shape $\lambda/\mu$ is a border strip if and only if $\lambda_i = \mu_{i-1} + 1$ for $i \ge 2$. The height $\text{ht}$ of a border strip is one less than the number of rows, and the width $\text{wt}$ is one less than the number of columns. The ordinary Murnaghan-Nakayama rule states that for any partition $\mu$ and $r \in \mathbb{N}$, we have $s_\mu \cdot p_r = \sum_\lambda (-1)^{\text{ht}(\lambda/\mu)} s_\lambda$, where the sum is over all partitions $\lambda \supseteq \mu$ for which $\lambda/\mu$ is a border strip of size $r$.

Define a broken border strip to be a (not necessarily connected) skew shape with no $2 \times 2$ square. Equivalently, a skew shape $\lambda/\mu$ is a broken border strip if and only if $\lambda_i \le \mu_{i-1} + 1$ for $i \ge 2$. A broken border strip $\lambda/\mu$ is a union of a finite number, $\text{st}(\lambda/\mu)$, of border strips. Denote by $\text{ht}(\lambda/\mu)$ the sum of heights of these strips and by $\text{wt}(\lambda/\mu)$ the sum of widths of these tableaux.

**Theorem 6.2 (quantum Murnaghan-Nakayama rule)** For any partition $\mu$ and $r \in \mathbb{N}$ we have

$$s_{\mu} \cdot \bar{p}_{r} = \sum_{\lambda} (-1)^{\text{ht}(\lambda/\mu)} q^{\text{wt}(\lambda/\mu)} (q-1)^{\text{st}(\lambda/\mu)-1} s_{\lambda}, \qquad (25)$$

where the sum runs over all partitions $\lambda \supseteq \mu$ for which $\lambda/\mu$ is a broken border strip of size $r$.

**Proof:** Omitted. □

A broken border strip tableau of shape $\lambda/\mu$ and type $\alpha$ is an assignment of positive integers to the squares of $\lambda/\mu$ such that every row and column is weakly increasing, the integer $i$ appears $\alpha_i$ times, and the set of squares occupied by $i$ forms a broken border strip or is empty. The weight of a broken border strip $b$ is weight $b = (-1)^{\text{ht}(b)} q^{\text{wt}(b)} (q-1)^{\text{st}(b)-1}$, and the weight $T$ of a broken border strip tableau $T$ is the product of weights of its non-empty broken border strips.

**Theorem 6.3** We have

$$\begin{align*}
\eta_q^\lambda(T_{\gamma_\mu}) &= \sum q^{\sum_j N=(J_j)} (q-1)^{\sum_j N<(J_j)}, \\
\epsilon_q^\lambda(T_{\gamma_\mu}) &= \sum (-1)^{\sum_j N=(J_j)} (q-1)^{\sum_j N<(J_j)}, \\
\chi_q^\lambda(T_{\gamma_\mu}) &= \sum_T \text{weight } T,
\end{align*}$$

where the first two sums are over $r$-tuples $(J_1, \dots, J_r)$ of multisets $J_j$ with $|J_j| = \mu_j$ and for which $\cup J_k$ contains $\lambda_j$ copies of $j$, and the last sum is over broken border strip tableaux $T$ of shape $\lambda$ and type $\mu$.

**Proof:** Omitted. □

# 7 Acknowledgments

The authors are grateful to Mahir Can, Pavel Etingof, Charlie Johnson, Alexander Kleschev, Bernard Leclerc, Andrew Mathas, Arun Ram, Brendon Rhoades and Doron Zeilberger for helpful conversations.
References

[1] P. CARTIER AND D. FOATA. *Problèmes combinatoires de commutation et réarrangements*. Lecture Notes in Mathematics, No. 85. Springer-Verlag, Berlin (1969).

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

[3] C. W. CURTIS, N. IWAHORI, AND R. KILMOYER. Hecke algebras and characters of parabolic type of finite groups with $(B, N)$-pairs. *Inst. Hautes Études Sci. Publ. Math.*, **40** (1971) pp. 81–116.

[4] J. M. DOUGLASS. An inversion formula for relative Kazhdan-Luszig polynomials. *Comm. Algebra*, **18**, 2 (1990) pp. 371–387.

[5] W. FULTON. *Young Tableaux; With Applications to Representation Theory and Geometry*, vol. 35 of *London Mathematical Society Student Texts*. Cambridge University Press, New York (1997).

[6] S. GAROUFALIDIS, T. T. Q. LÊ, AND D. ZEILBERGER. The quantum MacMahon master theorem. *Proc. Natl. Acad. Sci. USA*, **103**, 38 (2006) pp. 13928–13931 (electronic).

[7] M. GECK AND G. PFEIFFER. *Characters of finite Coxeter groups and Iwahori-Hecke algebras*, vol. 21 of *London Mathematical Society Monographs. New Series*. The Clarendon Press Oxford University Press, New York (2000).

[8] I. P. GOULDEN AND D. M. JACKSON. Immanants, Schur functions, and the MacMahon master theorem. *Proc. Amer. Math. Soc.*, **115**, 3 (1992) pp. 605–612.

[9] R. C. KING AND B. G. WYBOURNE. Representations and traces of the Hecke algebras $H_n(q)$ of type $A_{n-1}$. *J. Math. Phys.*, **33**, 1 (1992) pp. 4–14.

[10] M. KONVALINKA AND I. PAK. Non-commutative extensions of the MacMahon master theorem. *Adv. Math.*, **215**, 1 (2007) pp. 29–61.

[11] D. E. LITTLEWOOD. *The Theory of Group Characters and Matrix Representations of Groups*. Oxford University Press, New York (1940).

[12] P. MACMAHON. *Combinatory Analysis*, vol. 1 and 2. Cambridge Univ. Press, Cambridge (1915).

[13] R. MERRIS AND W. WATKINS. Inequalities and identities for generalized matrix functions. *Linear Algebra Appl.*, **64** (1985) pp. 223–242.

[14] A. RAM. A Frobenius formula for the characters of the Hecke algebras. *Invent. Math.*, **106**, 3 (1991) pp. 461–488.

[15] A. RAM, J. REMMEL. Applications of the Frobenius formulas for the characters of the symmetric group and the Hecke algebras of type A. *J. Algebraic Combin.*, **6** (1997), no. 1, pp. 59–87

[16] R. STANLEY. Positivity problems and conjectures. In *Mathematics: Frontiers and Perspectives* (V. ARNOLD, M. ATIYAH, P. LAX, AND B. MAZUR, eds.). American Mathematical Society, Providence, RI (2000), pp. 295–319.