2022-12-06
The Murnaghan–Nakayama rule
The expansion of Schur polynomials in the power-sum basis gives the irreducible characters of the symmetric group as coefficients:
\begin{equation*} \schurS_\lambda(\xvec) = \sum_{\mu} \frac{\chi^{\lambda}_{\mu}}{z_\mu} \powerSum_{\mu}(\xvec) = \sum_{\mu} \frac{\powerSum_{\mu}(\xvec)}{z_\mu} \sum_{T \in \BST(\lambda,\mu)} (-1)^{\mathrm{ht}(T)} \end{equation*}where the sum is taken over border strip tableaux of shape $\lambda$ and weight $\mu.$
Another way to phrase the Murnaghan–Nakaygama rule is the following:
\begin{equation*} \powerSum_r(\xvec) \schurS_\lambda(\xvec) = \sum_{\mu} (-1)^{\mathrm{ht}(\mu/\lambda)} \schurS_\mu(\xvec) \end{equation*}where the sum ranges over all $\mu$ such that $\mu/\lambda$ is a border-strip with $r$ boxes. The combinatorial rule was first stated in [Mur37Nak40].
A completely combinatorial proof of the Murnaghan–Nakayama rule is provided in [Men19], which uses only a sign-reversing involution for the proof.
We can also write the power-sum expansion as the average
\begin{equation*} \schurS_\lambda(\xvec) = \frac{1}{n!} \sum_{\sigma \in \symS_n} \chi^{\lambda}(\sigma) \powerSum_{\text{type}(\sigma)}(\xvec). \end{equation*}The characters $\chi^{\lambda}_{\mu}$ also show up in the Schur expansion of power-sum symmetric functions.
\begin{equation*} \powerSum_\mu(\xvec) = \sum_{\lambda} \chi^{\lambda}_{\mu} \schurS_{\lambda}(\xvec). \end{equation*}This is a consequence of the fact that the characters are orthogonal (so that inverting a transition matrix is more or less a transposition).
Yet another way to compute $\chi^{\lambda}_{\mu}$ is by taking the coefficient of $\prod_{i=1}^k x_i^{\lambda_i + \ell -i}$ in
\[ \prod_{i \lt j} (x_i - x_j ) \; \cdot \; \powerSum_{\mu}(x_1,\dotsc,x_\ell), \]where $\ell$ is at least the number of parts of $\lambda.$
Formulas for $\chi^{\lambda}_{\mu}$
Murnaghan–Nakayama recursion
One can reformulate the Murnaghan–Nakayama rule as a recursive rule, see e.g. [2.4.4, JK84].
Let $\lambda \vdash n$ and $\mu \vdash n-m.$
\[ \chi^{\lambda}(\mu,m) = \sum_{\nu} (-1)^{\mathrm{ht}(\lambda /\nu)} \chi^{\nu}(\mu) \]where the sum ranges over all $\nu$ such that $\lambda/\nu$ is a border-strip of size $m.$
Y. Roichman's formula
Y. Roichman has an alternative way of expressing the coefficients $\chi^{\lambda}_{\mu}.$ This generalizes to so-called Kazhdan–Lusztig characters, see [Roi97] and [Roi99].
We have that
\[ \chi^{\lambda}_{\mu} = \sum_{Q \in \SYT(\lambda)} \mathrm{weight}_\mu(Q) \]where
\[ \mathrm{weight}_\mu(Q) \coloneqq \prod_{\substack{1 \leq i \leq n \\ i \notin B(\mu)}} f_\mu(i,Q), \quad B(\mu) \coloneqq \{ \mu_1 + \dotsb + \mu_r : 1\leq r \leq \length(\mu)\} \]and
\[ f_\mu(i,Q) \coloneqq \begin{cases} -1 &\text{ if $i+1$ is southwest of $i$} \\ 0 &\text{ if $i+1$ is northeast of $i,$ $i+2$ southwest of $i+1$ and $i+1 \notin B(\mu)$} \\ 1 & \text{ otherwise}. \end{cases} \]Another way to phrase this, is due to C. Athanasiadis [Prop. 3.2, Ath15] and is as follows.
Let $\lambda$ be a partition of $n.$ Then the expansion of the Schur function $\schurS_{\lambda}$ into power sum symmetric functions is given by
\begin{align}\label{eq:schurRoichmanPexp} \schurS_\lambda(\xvec) = \sum_{\mu \vdash n} % \frac{\powerSum_\mu(\xvec)}{z_\mu} % \sum_{\substack{ T \in \SYT(\lambda) \\ \DES(T) \in U_\mu }} (-1)^{\DES(T) \setminus S_\mu} \,, \end{align}where $S_\mu$ and $U_\mu$ are defined here.
R. Holmes' recursion
R. Holmes [Hol17] generalizes a results by James and Kerber [2.4.3, JK84]. This gives a recursive method of computing $\chi^{\lambda}_{\mu}.$ The interesting aspect of this recursion is that one computes characters of $\symS_n$ by only relying on characters values for $\symS_{n-1}$ (and not smaller groups as with the Murnaghan–Nakayama recursion).
The following set of relations are enough to compute all $\chi^{\lambda}_{\mu}.$ Here, $\lambda \vdash n$ and we always assume that the arguments to $\chi$ are partitions of the same size, and $\epsilon_i$ denotes the unit vector with $1$ at the $i^\thsup$ coordinate.
Special case of the Murnaghan–Nakayama rule:
\[ \chi^{\lambda}_{(n)} = \begin{cases} (-1)^{n-\lambda_1} & \text{ if $\lambda$ is a hook} \\ 0 &\text{ otherwise}. \end{cases} \]The James–Kerber branching rule:
\[ \chi^{\lambda}_{(\mu,1)} = \sum_{\substack{ 1 \leq i \leq \length(\lambda) \\ \lambda_i \gt \lambda_{i+1} }} \chi^{\lambda - \epsilon_i}_{\mu}. \]R. Holmes recursion, $m \geq 2$:
\[ \chi^{\lambda}_{(\mu,m)} = \frac{1}{m-1} \left[ \sum_{\substack{ 1 \leq i \leq \length(\lambda) \\ \lambda_i \gt \lambda_{i+1} }} (\lambda_i - i) \chi^{\lambda - \epsilon_i}_{(\mu,m-1)} - \sum_{\substack{ 1 \leq j \leq \length(\mu) \\ \mu_{j-1} \gt \mu_{j} }} M_j \cdot \mu_j \cdot \chi^{\lambda}_{(\mu+\epsilon_j,m-1)} \right]. \]In the second sum, we use the convention that $\mu_0 = \infty$ and $M_j$ denotes the number of parts equal to $\mu_j$ in the partition $(\mu,m-1).$
To speed up computation, one can also add the following special case.
Hook formula case:
\[ \chi^{\lambda}_{(1^n)} = f^\lambda \]where $f^\lambda$ is the number of standard Young tableaux of shape $\lambda.$ This quantity can be computed using the hook formula.
Variants of the Murnaghan–Nakayama rule
The following families have a Murnaghan–Nakayama rule.
- the stable Grassman Grothendieck polynomials.
- the $k$-Schur polynomials.
- $K\text{-}k$-Schur functions, see [Ngu22].
- Cylindric Schur functions (cylindric Hecke characters), see [Lem. 5.3, Kor20].
Quantum Murnaghan–Nakayama rule
A quantum version of the Murnaghan–Nakayama rule. Here, one multiplies the Schur function with a $q$-deformation of the power-sum symmetric functions. These deformations are equal to the Hall–Littlewood $P$-funtions, indexed by one-part partitions. The paper has several conjectured generalizations of Murnaghan–Nakayama rules for Hall–Littlewood $P$-functions.
Plethystic Murnaghan–Nakayama rule
A rule for computing the coefficients in the expansion
\[ \schurS_\mu \cdot (\powerSum_r[\completeH_m]) = \sum_{\lambda \vdash rm+|\mu|} (-1)^{\mathrm{ht}_r(\lambda/\mu)} \schurS_{\lambda} \]is given by M. Wildon [Wil16]. See also [Wil18] for a more general result.
Murnaghan–Nakayama rule for Chern classes of Schubert cells
In [FGX22], the authors give a Pieri rule and a Murnaghan–Nakayama rule for Chern classes of Schubert cells.
References
- [Ath15] Christos A. Athanasiadis. Power sum expansion of chromatic quasisymmetric functions. The Electronic Journal of Combinatorics, 22(2):1–9, April 2015.
- [FGX22] Neil J. Y. Fan, Peter L. Guo and Rui Xiong. Pieri and Murnaghan–Nakayama type rules for Chern classes of Schubert cells. arXiv e-prints, 2022.
- [Hol17] Randall R. Holmes. A recursion formula for the irreducible characters of the symmetric group. arXiv e-prints, 2017.
- [JK84] Gordon James and Adalbert Kerber. The representation theory of the symmetric group. Cambridge University Press, 1984.
- [Kor20] Christian Korff. Cylindric hecke characters and Gromov–Witten invariants via the asymmetric six-vertex model. Communications in Mathematical Physics, 381(2):591–640, December 2020.
- [Men19] Anthony Mendes. The combinatorics of rim hook tableaux. Australas. J Comb., 73:132–148, 2019.
- [Mur37] Francis D. Murnaghan. The characters of the symmetric group. Amer. J. Math., 59:739–753, 1937.
- [Nak40] Tadashi Nakayama. On some modular properties of irreducible representations of a symmetric group. I and II. Jap. J. Math., 17:165–184, 411–423, 1940.
- [Ngu22] Duc-Khanh Nguyen. A generalization of the Murnaghan–Nakayama rule for $k$-$k$-Schur and $k$-Schur functions. arXiv e-prints, 2022.
- [Roi97] Yuval Roichman. A recursive rule for Kazhdan–Lusztig characters. Advances in Mathematics, 129(1):25–45, July 1997.
- [Roi99] Yuval Roichman. Characters of the symmetric groups: formulas, estimates and applications. In Emerging Applications of Number Theory. Springer New York, 1999.
- [Wil16] Mark Wildon. A combinatorial proof of a plethystic Murnaghan–Nakayama rule. SIAM Journal on Discrete Mathematics, 30(3):1526–1533, January 2016.
- [Wil18] Mark Wildon. A generalized SXP rule proved by bijections and involutions. Annals of Combinatorics, 22(4):885–905, November 2018.