2023-06-29
Symmetric functions
A function $f$ in $n$ variables is symmetric if for any permutation $w\in \symS_n,$ we have
\[ f(x_1,x_2,\dotsc,x_n) = f(x_{w(1)},x_{w(2)},\dotsc,x_{w(n)}). \]Below we list the most common families symmetric functions. These are all commonly used bases for the space of symmetric functions.
Here are a few great resources:
- M. Zabrocki's introduction to symmetric functions
- A. Prasad's introduction to Schur polynomials, published in [Pra19a].
Monomial symmetric functions
Given a partition $\lambda,$ we define the monomial symmetric functions as
\[ \monomial_\lambda(\xvec) = \sum_{\alpha \sim \lambda} \xvec^{\alpha} \]where $\alpha \sim \lambda$ if the parts of $\alpha$ is a rearrangement of the parts of $\lambda.$
The augmented monomial symmetric functions are defined as $\tilde{\monomial}_\lambda \coloneqq m_1!m_2!\dotsm m_n! \monomial_\lambda$ where $\lambda = (1^{m_1},2^{m_2},\dotsc).$ See [Mer15] for more background.
Elementary symmetric functions
The elementary symmetric functions are defined as follows:
\[ \elementaryE_k(\xvec) = \sum_{i_1 \lt i_2 \lt \dotsb \lt i_k } x_{i_1} \dotsm x_{i_k} = \monomial_{1^k}(\xvec), \qquad \elementaryE_\lambda(\xvec) = \elementaryE_{\lambda_1} \elementaryE_{\lambda_2} \dotsm \elementaryE_{\lambda_\ell} \]Complete homogeneous symmetric functions
Similar to the elementary symmetric functions, the complete homogeneous functions are defined as
\[ \completeH_k(\xvec) = \sum_{i_1 \leq i_2 \leq \dotsb \leq i_k } x_{i_1} \dotsm x_{i_k} = \sum_{\lambda \vdash k} \monomial_\lambda(\xvec), \qquad \completeH_\lambda(\xvec) = \completeH_{\lambda_1} \completeH_{\lambda_2} \dotsm \completeH_{\lambda_\ell} \]Powersum symmetric functions
The powersum symmetric functions are defined as
\[ \powerSum_k(\xvec) = x_{1}^k + x_2^k + x_3^k + \dotsb = \monomial_{(k)}(\xvec), \qquad \powerSum_\lambda(\xvec) = \powerSum_{\lambda_1} \powerSum_{\lambda_2} \dotsm \powerSum_{\lambda_\ell}. \]They serve as an orthogonal basis for the Hall inner product. We have the following product expansions [Sec. 1.4, Mac95] (see the preliminaries for the definition of $z_\lambda$).
\[ \prod_{i,j\geq 1}(1-x_i y_j)^{-1} = \sum_{\lambda} z_\lambda^{-1} \powerSum_\lambda(\xvec)\powerSum_\lambda(\yvec). \]and
\[ \prod_{i,j\geq 1}(1+x_i y_j) = \sum_{\lambda} (-1)^{|\lambda|-\length(\lambda)} z_\lambda^{-1} \powerSum_\lambda(\xvec)\powerSum_\lambda(\yvec). \]First note that
\begin{align} \prod_{i,j,k\geq 1}(1+x_i y_j z_k) &= \prod_{k\geq 1} \prod_{i,j\geq 1}(1+x_i (y_j z_k)) \\ &= \prod_{k\geq 1} \sum_{\lambda} (-1)^{|\lambda|-\length(\lambda)} z_\lambda^{-1} \powerSum_\lambda(\xvec)\powerSum_\lambda(\yvec z_k). \end{align}Now using that $\powerSum_\lambda(\yvec z_k) = z_k^{|\lambda|} \powerSum_\lambda(\yvec),$ we can easily deduce the statement.
There are two quasisymmetric refinements of the powersum symmetric functions given in [BDHMN20].
Let $L_n$ be the reverse lexicographic ordering of partitions. Then the following sum over any initial segment,
\[ \sum_{\lambda \in [1^n,\mu]} \powerSum_\lambda(x) \]is Schur-positive.
For some partial progress on S. Sundaram's conjecture, see these FPSAC 2019 proceedings.
Forgotten symmetric functions
Finally, there is a family of symmetric functions, $\forgotten_\lambda(\xvec),$ defined as $\forgotten_\lambda = \omega(\monomial_\lambda)$ (sometimes $(-1)^{|\lambda|-\length(\lambda)}\omega(\monomial_\lambda)$) where $\omega$ is the involution on symmetric functions. Note that $\langle \forgotten_\lambda, \elementaryE_\mu \rangle = \delta_{\lambda \mu}.$
It does not have as many applications as the other bases.
In [Ex. 7.9, Sta01], the following monomial expansion is given, where $\lambda \vdash n$ has $\ell$ parts:
\begin{equation}\label{eq:forgottenInMonomial} (-1)^{n-\ell} \forgotten_\lambda(\xvec) = \sum_{\mu} a_{\lambda\mu} \monomial_\mu(\xvec) \end{equation}where $a_{\lambda \mu}$ is the number of distinct permutations $(\alpha_1,\dotsc,\alpha_\ell)$ of $(\lambda_1,\dotsc,\lambda_\ell)$ such that
\[ \{ \alpha_1+ \dotsb + \alpha_i : i \in [\ell] \} \supseteq \{ \mu_1+ \dotsb + \mu_j : j \in \length(\mu) \}. \]Various identities
We have that
\[ \sum_{i=0}^n (-1)^i \elementaryE_i \completeH_{n-i} = \delta_{n,0}. \]Introducing
\[ E(z) = \sum_{k \geq 0} \elementaryE_k z^k, \quad P(z) = \sum_{k \geq 0} \powerSum_{k+1} z^k \text{ and } H(z) = \sum_{k \geq 0} \completeH_k z^k \]we get $E(-z)H(z)=1.$ Moreover,
\[ P(-t) = \frac{E'(t)}{E(t)}, \quad P(t) = \frac{H'(t)}{H(t)}. \]One can show that
\begin{align} H(z) = \exp\left( \sum_{k \geq 1} \frac{\powerSum_k }{k} z^k \right) \text{ and } E(-z) = \exp\left( - \sum_{k \geq 1} \frac{\powerSum_k }{k} z^k \right). \end{align}Another common identity is
\[ \prod_{i} \frac{1+t x_i}{1-t x_i} = \sum_{\lambda} t^{|\lambda|} 2^{\length(\lambda)} \monomial_{\lambda}(\xvec). \]Note that $\sum_{\lambda \vdash n} 2^{\length(\lambda)} \monomial_{\lambda}(\xvec)$ is the Schur's Q function $\schurQ_{(n)}(\xvec).$
We have, by using \eqref{eq:forgottenInMonomial}, that
\[ \sum_{\lambda \vdash n} \forgotten_\lambda(\xvec) = \monomial_{1^n}(\xvec), \qquad \sum_{\lambda \vdash n} \monomial_\lambda(\xvec) = \forgotten_{1^n}(\xvec). \]Newton identities and determinants
We have
\[ r \completeH_r = \sum_{k=1}^r \powerSum_k \completeH_{r-k} \text{ and } r \elementaryE_r = \sum_{k=1}^r (-1)^{k-1} \powerSum_k \elementaryE_{r-k}. \]The following determinant identities can be useful:
\[ n! \elementaryE_n = \begin{vmatrix} \powerSum_1 & 1 & 0 & \cdots \\ \powerSum_2 & \powerSum_1 & 2 & 0 & \cdots \\ \vdots && \ddots & \ddots \\ \powerSum_{n-1} & \powerSum_{n-2} & \cdots & \powerSum_1 & n-1 \\ \powerSum_n & \powerSum_{n-1} & \cdots & \powerSum_2 & \powerSum_1 \end{vmatrix}. \]We also have
\[ p_n = \begin{vmatrix} \elementaryE_1 & 1 & 0 & \cdots & \\ 2\elementaryE_2 & \elementaryE_1 & 1 & 0 & \cdots & \\ 3\elementaryE_3 & \elementaryE_2 & \elementaryE_1 & 1 & \cdots & \\ \vdots &&& \ddots & \ddots & \\ n\elementaryE_n & \elementaryE_{n-1} & \cdots & & \elementaryE_1 & \end{vmatrix}. \]Principal specializations
Given a symmetric function $f,$ we define the following principal specializations:
\[ \princSpec_k^q(f) = f(1,q,q^2,\dotsc,q^{k-1}) \qquad \princSpec_k^1(f) = f(\underbrace{1,1,\dotsc,1}_k) \qquad \princSpec(f) = f(1,q,q^2,\dotsc) \]The last specialization is a formal power series, and is called the stable principal specialization.
For example, consider $\powerSum_1(\xvec)=x_1+x_2+x_3+\dotsb.$ The stable principal specialization is
\[ \powerSum_1(1,q,q^2,\dotsc) = 1+q+q^2+\dotsb = \frac{1}{1-q}. \]In a similar manner, with $\powerSum_k(\xvec)=x_1^k + x_2^k + x_3^k + \dotsb,$ we find that
\[ \powerSum_k(1,q,q^2,\dotsc) = 1+q^k+q^{2k}+\dotsb = \frac{1}{1-q^k}. \]Since every symmetric function $f$ can be expressed in terms of power-sum symmetric functions, this gives one possible way for computing $\princSpec(f).$
Let $\lambda$ be a partition of $n$ with $\ell$ parts. Furthermore, let $m_i$ be the number of parts of size $i,$ and we use the notation of raising and falling factorials.
- $\princSpec_k^1(\monomial_\lambda) = \frac{(k)_{\ell}}{m_1!m_2!\dotsm m_\ell!}$
- $\princSpec_k^1(\powerSum_\lambda) = k^{\ell}$
- $\princSpec_k^1(\forgotten_\lambda) = (-1)^{n-\ell}\frac{(k)^{\ell}}{m_1!m_2!\dotsm m_\ell!}$
- $\princSpec_k^1(\completeH_\lambda) = \prod_{j=1}^\ell \frac{(k)^{\lambda_j}}{\lambda_j!}$
- $\princSpec_k^1(\elementaryE_\lambda) = \prod_{j=1}^\ell \frac{(k)_{\lambda_j}}{\lambda_j!}$
We also have
\[ \princSpec_k^q( \elementaryE_n ) = q^{\binom{n}{2}} \qbinom{k}{n}_q, \qquad \princSpec_k^q( \completeH_n ) = \qbinom{n+k-1}{n}_q \qquad \princSpec_k^q( \powerSum_n ) = \frac{1-q^{kn}}{1-q^n}. \]For reference and proofs, see e.g. [Ros02]. Warning! Note that she uses the non-standard notation $|\lambda|=m_1!m_2!\dotsm m_\ell!.$
We also have the following stable principal specializations, see [p. 303, Sta01] for details.
- $\princSpec(\powerSum_\lambda) = \prod_{j=1}^\ell \frac{1}{1-q^{\lambda_j}} $
- $\princSpec(\completeH_\lambda) = \prod_{j=1}^\ell \frac{1}{(1-q)(1-q^2)\dotsm (1-q^{\lambda_j})} $
- $\princSpec(\elementaryE_\lambda) = \prod_{j=1}^\ell \frac{q^{\binom{\lambda_j}{2}}}{(1-q)(1-q^2)\dotsm (1-q^{\lambda_j})} $
The combinatorics involving the elementary, powersum and complete homogeneous polynomials is studied in [O'S22], where various combinatorial sequences are shown to satisfy similar relations.
Sagan–Swanson show in [SS22] that $q$-Stirling numbers of type $B$ can be obtained as the following specialization:
\[ S_B(n,k;q) = \completeH_{n-k}\left([1]_q,[3],[5]_q,\dotsc,[2k+1]_q \right). \]They also show some other interesting identities.
Involution on symmetric functions
There is an involution $\omega$ on symmetric functions defined as $\omega(\elementaryE_\lambda) = \completeH_\lambda$ for all $\lambda.$ It acts on the power-sum symmetric functions and the Schur polynomials as
\[ \omega(\powerSum_\lambda) = (-1)^{|\lambda|-\length(\lambda)}\powerSum_\lambda \quad \text{ and } \quad \omega(\schurS_\lambda) = \schurS_{\lambda'}. \]This involution has natural extensions to quasisymmetric functions, by defining it on the Gessel quasisymmetric functions.
Transition matrices
There are combinatorial interpretations of the coefficients in the transition matrices between these bases. The reference [ER91] gives a comprehensive overview.
In the table below, we show the coefficients in the expansion
\[ \mathrm{v}_\lambda = \sum_{\mu} c_{\lambda \mu} \mathrm{u}_\mu, \]for different choices of bases $\{\mathrm{v}_\lambda\}$ and $\{\mathrm{u}_\lambda\}.$
$\;$ | $\completeH_\lambda$ | $\elementaryE_\lambda$ | $\schurS_\lambda$ | $\powerSum_\lambda$ | $\monomial_\lambda$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
$\completeH_\mu$ | $I$ | $(-1)^{n-\length(\mu)}|B_{\mu,\lambda}|$ | $(K_{\lambda,\mu})^{-1}$ | $(-1)^{\length(\mu)-\length(\lambda)}w(B_{\mu,\lambda})$ | $(IM_{\lambda,\mu})^{-1}$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
$\elementaryE_\mu$ | $(-1)^{n-\length(\mu)}|B_{\mu,\lambda}|$ | $I$ | $(K_{\lambda',\mu})^{-1}$ | $(-1)^{n-\length(\mu)}w(B_{\mu,\lambda})$ | $(BM_{\lambda,\mu})^{-1}$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
$\schurS_\mu$ | $K_{\lambda,\mu}$ | $K_{\lambda',\mu}$ | $I$ | $\chi_{\mu,\lambda}$ | $(K_{\lambda,\mu})^{-1}$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
$\powerSum_\mu$ | $|OB_{\mu,\lambda}|/z_\mu$ | $(-1)^{n-\length(\mu)}|OB_{\mu,\lambda}|/z_\mu$ | $\chi_{\lambda,\mu}/z_\mu$ | $I$ | $(-1)^{\length(\mu)-\length(\lambda)}w(B_{\lambda,\mu})/z_\mu$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
$\monomial_\mu$ | $IM_{\lambda,\mu}$ | $BM_{\lambda,\mu}$ | $K_{\lambda,\mu}$ | $|OB_{\lambda,\mu}|$ | $I$ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
We have that $BM_{\lambda,\mu}$ is the number of $01$-matrices with row sums given by $\lambda$ and column sums given by $\mu.$ Similarly, $IM_{\lambda,\mu}$ is the number of non-negative integer matrices with row sums given by $\lambda$ and column sums given by $\mu.$ Combinatorial interpretations for computing the matrices $(IM_{\lambda,\mu})^{-1}$ and $(BM_{\lambda,\mu})^{-1}$ are given in [KR06].
The coefficient $\chi_{\lambda,\mu}$ is a character value, and can be computed using the Murnaghan–Nakayama rule.
The coefficient $K_{\lambda,\mu}$ is a Kostka coefficient. Moreover, the entries in the inverse Kostka matrix, $(K_{\lambda,\mu})^{-1},$ have a combinatorial formula, see [ER90].
A special rim hook tabloid of shape $\lambda$ and type $\mu$ is a filling of $\lambda$ with rim hooks, such that each rim hook has at least one box in the first column. The sign of a rim hook is $(-1)^{r-1}$ where $r$ is the number of rows it spans, and the sign $\sign(T)$ of a special rim hook tabloid $T$ is the product of the signs of the rim hooks. We have that
\[ (K_{\lambda,\mu})^{-1} = \sum_{T \in \mathrm{RHT}(\lambda,\mu) } \sign(t) \]where $\mathrm{RHT}(\lambda,\mu)$ is the set of special rim hook tabloids with shape $\lambda$ and type $\mu.$
The coefficients $B_{\mu,\lambda}$ and $OB_{\mu,\lambda}$ may be computed by counting certain brick tabloids, see [ER91].
Positivity probabilities
In [PvW18], the authors describe the probability that a random symmetric function is monomial- schur- and elementary-positive, by comparing volumes of cones spanned by the basis elements.
Hopf algebra
The algebra of symmetric functions admit a Hopf algebra structure, where the coproduct is defined as
\[ \Delta( \elementaryE_k ) = \sum_{j=0}^k \elementaryE_j \otimes \elementaryE_{k-j} \]See Hopf algebras, symmetric functions and representations, by R. Cheng and Hopf algebras in combinatoris, D. Grinberg and V. Reiner.
References
- [BDHMN20] Cristina Ballantine, Zajj Daugherty, Angela Hicks, Sarah Mason and Elizabeth Niese. On quasisymmetric power sums. Journal of Combinatorial Theory, Series A, 175:105273, October 2020.
- [ER90] Ömer Eğecioğlu and Jeffrey B. Remmel. A combinatorial interpretation of the inverse Kostka matrix. Linear and Multilinear Algebra, 26(1-2):59–84, January 1990.
- [ER91] Ömer Eğecioğlu and Jeffrey B. Remmel. Brick tabloids and the connection matrices between bases of symmetric functions. Discrete Applied Mathematics, 34(1-3):107–120, November 1991.
- [KR06] Andrius Kulikauskas and Jeffrey Remmel. Lyndon words and transition matrices between elementary, homogeneous and monomial symmetric functions. The Electronic Journal of Combinatorics, 13(1), February 2006.
- [Mac95] Ian G. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, Second edition, 1995. With contributions by A. Zelevinsky, Oxford Science Publications
- [Mer15] Mircea Merca. Augmented monomials in terms of power sums. SpringerPlus, 4(1), November 2015.
- [O'S22] Cormac O'Sullivan. Symmetric functions and a natural framework for combinatorial and number theoretic sequences. arXiv e-prints, 2022.
- [Pra19a] Amritanshu Prasad. An introduction to schur polynomials. The Graduate Journal of Mathematics, 4(2):62–84, 2019.
- [PvW18] Rebecca Patrias and Stephanie van Willigenburg. The probability of positivity in symmetric and quasisymmetric functions. arXiv e-prints, 2018.
- [Ros02] Mercedes H. Rosas. Specializations of MacMahon symmetric functions and the polynomial algebra. Discrete Mathematics, 246(1-3):285–293, March 2002.
- [SS22] Bruce E. Sagan and Joshua P. Swanson. q-Stirling numbers in type B. arXiv e-prints, 2022.
- [Sta01] Richard P. Stanley. Enumerative Combinatorics: Volume 2. Cambridge University Press, First edition, 2001.
- [Sun18] Sheila Sundaram. On a positivity conjecture in the character table of $S_n$. arXiv e-prints, 2018.