The symmetric functions catalog

An overview of symmetric functions and related topics

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:

\[ \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 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