From Schensted to Pólya

Submitted by Dennis White

Suppose $G$ is a finite permutation group acting on $[n] := \{1,2,\ldots,n\}$ . Let $C_{\rho}$ denote the conjugacy class of permutations of type $\rho$ in symmetric group $S_n$ . Let $\chi^{\lambda}(\rho)$ be the $\lambda$ irreducible $S_n$ character evaluated at the conjugacy class $C_{\rho}$ .

Define

$\displaystyle K_{\lambda,G} := \sum_{\rho} \frac{|G\cap C_{\rho}|}{|G|} \chi^{\lambda}(\rho)$

In fact, $K_{\lambda,G}$ is the number of occurrences of the irreducible $\lambda$ in the induction of the trivial character of $G$ up to $S_n$ , or, by Frobenius reciprocity, the dimension of the $G$ -fixed space inside the $S_n$ -irreducible corresponding to $\lambda$ .

It is therefore an integer and

$K_{\lambda,G} \leq f^{\lambda}$

where $f^{\lambda}$ is the number of standard Young tableaux (SYT) of shape $\lambda$ .

OPAC-024. Interpret $K_{\lambda,G}$ as a subset of SYT of shape $\lambda$ .

The group $G$ then acts (Pólya action) on colorings of $[n]$ . For a partition $\mu$ , let $\Delta_{\mu}$ be the orbits of $\mu$ -colorings of $[n]$ , that is, the orbits in which color $i$ appears $\mu_i$ times. It follows from Pólya’s Theorem that

$\displaystyle (*) \quad \quad \quad|\Delta_{\mu}| = \sum_{\lambda} K_{\lambda,\mu}K_{\lambda,G}$

where $K_{\lambda,\mu}$ , the Kostka number, counts the number of semistandard Young tableaux (SSYT) of type $\mu$ and shape $\lambda$ .

Alternatively (see [1]), compute the dimension of the $\mu$ -weight space inside the $G$ -fixed space of the $GL(V)$ -representation on $V^{\otimes n}$ in two ways, either directly or via Schur-Weyl duality.

OPAC-025. Give a Schensted-like proof of Equation (*).

Example 1. If $G = S_{\nu} = S_{\nu_1} \times S_{\nu_2} \times \cdots$ (a Young subgroup), then $K_{\lambda,G}=K_{\lambda,\nu}$ and

$\displaystyle |\Delta_\mu| = \sum_{\lambda} K_{\lambda,\mu} K_{\lambda,\nu}$ .

The tableaux in OPAC-024 are then the standarization tableaux of the SSYT and the Schensted-like proof is the Robinson-Schensted-Knuth correspondence (RSK).

Example 2. We say $i$ is a descent in SYT $T$ if $i$ lies in a row above $i+1$ in $T$ . Define

$\displaystyle \mathrm{maj}(T) := \sum_{i \textrm{ descent of } T} i$ .

If $G = Z_n$ , the cyclic group of order $n$ , acting on $[n]$ , then the tableaux of OPAC-024 are those SYT $T$ such that $\mathrm{maj}(T)$ is a multiple of $n$ . See [1]. However, usual Schensted applied to these tableaux does not produce orbit representatives for the Pólya action, so OPAC-025 is unresolved.

Example 3. The techniques in [1] can also be used to solve OPAC-024 if $G = Z_{n-1}$ acting on $[n]$ .

Example 4. Also solved in [1] is the case where $G$ is the alternating subgroup of a Young subgroup. If $G$ is the alternating subgroup of $S_{\nu}$ , then $K_{\lambda,G} = K_{\lambda,\nu} + K_{\lambda',\nu}$ . Here, $\lambda'$ denotes the conjugate of $\lambda$ . The solution to OPAC-025 uses a small modification to the standardization argument for the RSK algorithm for the Young subgroup case.

Example 5. In fact, suppose $G\times H$ acts on $[a+b]$ , with $G$ acting on $[a]$ and $H$ on $[b]$ (using a different alphabet). Suppose we know that $U$ is a solution tableau (shape $\lambda$ ) to OPAC-024 for $G$ in $S_{a}$ and $V$ is a solution tableau (shape $\rho$ ) for $H$ in $S_b$ (again, different alphabet). Then let $\mu$ be a partition larger than $\lambda$ and $\rho$ with $|\mu| = a + b$ . Construct a tableau $X$ of shape $\mu$ as follows. Let $Q$ be a SYT of shape $\rho$ such that the lattice word of $Q$ fits $\mu/\lambda$ (and so is counted by the Littlewood-Richardson coefficient). The portion of $X$ in $\lambda$ is $U$ . The portion of $X$ in $\mu/\lambda$ is the Schensted word corresponding to the pair $(V,Q)$ (see [1] for details; see also [3]). Of course, this idea may be extended to longer direct products.

Example 6. Applying Example 5 to Example 2 and using the fact that jeu de taquin preserves the descent set (see [2, Ch. 7 Appendix 1]), it follows that the tableaux $X$ can be chosen to be those tableaux whose $\mathrm{maj}$ in the two portions of the tableau ( $\lambda$ and $\mu/\lambda$ ) are divisible by $a$ and $b$ , respectively. Care must be taken that the alphabets in each portion are $[a]$ and $[b]$ respectively, even though the second alphabet is larger than the first.

We note in passing that while it is easy to show that if $H$ is conjugate to a subgroup of $G$ , then $K_{\lambda,G} \leq K_{\lambda,H}$ for all $\lambda$ , the converse is not true. In fact, $S_6$ contains two non-conjugate Klein 4-groups each of which has three elements of type $2^21^2$ and one element of type $1^6$ .

References:

[1] V. Reiner and D. White, Some notes on Pólya’s theorem, Kostka numbers and the RSK correspondence, unpublished (2019). Available online here.

[2] R. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

[3] D. White, Some connections between the Littlewood-Richardson rule and the construction of Schensted, J. Combin. Theory Ser. A 30 (1981), 237–247. DOI: 10.1016/0097-3165(81)90020-0

Share this:

Related

Leave a comment Cancel reply