2021-10-13

## 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].

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

**Theorem (Y. Roichman, 1997).**

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.

**Theorem.**

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:*

*The James–Kerber branching rule:*

*R. Holmes recursion*, $m \geq 2$:

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:*

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 stable Grassman Grothendieck polynomials have a Murnaghan–Nakayama rule.

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

## References

- [Ath15] Christos A. Athanasiadis. Power sum expansion of chromatic quasisymmetric functions. The Electronic Journal of Combinatorics, 22(2):1–9, April 2015.
- [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.
- [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.
- [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.