2023-06-12

## Cycle index polynomials

The cycle index polynomial (*Zyklenzeiger*) of a group $G$ was
introduced by G. Pólya in [Eq. (1,5), Pól37].
Let $G \subseteq \symS_n$ be a subgroup. The cycle index polynomial is defined
in terms of the powersum symmetric functions as the average

Let $\symS_n/G$ denote the set of let cosets of $G,$ and let $\symS_n$ act on $\setC[\symS_n/G].$ This makes $\setC[\symS_n/G]$ into an $\symS_n$-module, and its Frobenius characteristic is given by $\cyc_G(\xvec).$ In particular, $\cyc_G(\xvec)$ is Schur-positive. For more info on the cycle index polynomial, we refer to [LW19b].

**Conjecture (Foulkes Conjecture, [Fou50]).**

Let $X_{a,b}$ be the set of set-partitions of $\{1,2,\dotsc,ab\}$ into $a$ blocks of size $b.$ The symmetric group $S_{ab}$ act on $X_{a,b}$ in the obvious manner. Let $G_{a,b}$ be the stabilizer subgroup of some fixed element in $X_{a,b}$ under this action. Let

\[ \cyc_{G_{a,b}}(\xvec) = \sum_\lambda c_{\lambda,a,b}\; \schurS_\lambda(\xvec). \]Foukes conjecture states that whenever $a\leq b,$ then for all $\lambda,$ $c_{\lambda,a,b} \leq c_{\lambda,b,a}.$ This is equivalent with the statement that $ \completeH_b[\completeH_a]-\completeH_a[\completeH_b] $ is Schur-positive whenever $a \leq b.$ The notation here indicates plethysm.

See also https://arxiv.org/pdf/2008.13070.pdf.

## Lyndon symmetric functions

The Lyndon symmetric functions, also known as higher Lie characters in [AHR19], are described using the fundamental quasisymmetric functions:

\[ L_{\lambda}(\xvec) \coloneqq \sum_{\pi \in K_\lambda} \gessel_{n,D(w)}(\xvec) \]where $K_\lambda$ is the set of permutations in $\symS_n$ with cycle type $\lambda.$ See also [Def 1.5, AHR19] for a representation-theoretical definition,

The Lyndon symmetric functions are also covered in [p. 480, Sta01], and it was shown by Gessel–Reutenauer [Thm. 3.6, GR93], that we have

\begin{equation} L_{n}(\xvec) = \frac{1}{n} \sum_{d \mid n} \mu(d)\powerSum_{d}^{n/d}, \quad L_{n^k}(\xvec) = \completeH_k[L_{n}], \quad \text{ and } \quad L_{1^{m_1}2^{m_2}\dotsb}(\xvec) = L_{1^{m_1}} L_{2^{m_2}} \dotsm. \end{equation}These relations uniquely define the $L_{\lambda}(\xvec)$ where
we write $\lambda = 1^{m_1}2^{m_2}\dotsb.$
Moreover, since $L_{n}(\xvec)$ can be shown to be Schur-positive,
it follows that the Lyndon symmetric functions are also Schur positive.
A monomial expansion for $L_{\lambda}(\xvec)$ is given by summing over all
multisets of primitive necklaces whose sizes are given by $\lambda.$
Gesses then has a bijection which sends such multisets to
words of length $n$ whose *standardization permutation* is $\lambda.$

See also [Ex. 7.69c, Sta01] for some applications of Lyndon symmetric functions. In particular, T. Scharf shows that a certain character is

\[ \sum_{n\geq 0} \completeH_{n}\left[ \sum_{d\mid k} L_d \right]. \]**Problem (Thrall's problem).**

Find a combinatorial formula for the Schur expansion of $L_{\lambda}(\xvec).$

See the Youtube video GOCC 4/12/23 "A crystal base approach to Thrall's problem" for background and a possible approach to solving this problem.

**Problem (Yuval Roichman, FPSAC 2023).**

Prove that for any $\lambda \vdash n$

\[ \sum_{k=0}^n \langle L_{\lambda}, \schurS_{k,1^{n-k}} \rangle t^k \]is unimodal. This is [Conj. 7.13, AHR19].

**Problem.**

It is an open problem (Stanley, 2022) to find the (co)dimension of the span of the $L_\lambda,$ see 38:00 in https://www.youtube.com/watch?v=NDAzHTP3vOs.

The functions $L_{n}(\xvec)$ are Lie characters, see [Thm. 8.3, Reu93]. Richard Stanley discusses these also in these slides. One can show that

\[ L_{n}(\xvec) = \sum_{\lambda \vdash n} |\{T \in \SYT(n) : \maj(T) \equiv_n 1\}| \schurS_\lambda(\xvec). \]There is also the Whitehouse module, see [Sta]. Their Frobenius characteristic is

\[ \powerSum_{1} L_{n-1}(\xvec) - L_{n}(\xvec) \]so this is Schur-positive. Can we find a combinatorial proof that these are Schur-positive?

## References

- [AHR19] Ron M Adin, Pál Hegedüs and Yuval Roichman. Higher Lie characters and cyclic descent extension on conjugacy classes. arXiv e-prints, 2019.
- [Fou50] H. O. Foulkes. Concomitants of the quintic and sextic up to degree four in the coefficients of the ground form. Journal of the London Mathematical Society, s1-25(3):205–209, July 1950.
- [GR93] Ira M Gessel and Christophe Reutenauer. Counting permutations with given cycle structure and descent set. Journal of Combinatorial Theory, Series A, 64(2):189–215, November 1993.
- [LW19b] Nicholas A. Loehr and Gregory S. Warrington. Quasisymmetric and Schur expansions of cycle index polynomials. Discrete Mathematics, 342(1):113–127, January 2019.
- [Pól37] G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68(0):145–254, 1937.
- [Reu93] C. Reutenauer. Free lie algebras. LMS monographs, Clarendon Press, 1993.
- [Sta] Richard Stanley. The whitehouse representation. Online . Slides
- [Sta01] Richard P. Stanley. Enumerative Combinatorics: Volume 2. Cambridge University Press, First edition, 2001.