Cycle index polynomials and higher Lie characters

2026-08-17 Improve this page

#Cycle index polynomials

The cycle index polynomial (Zyklenzeiger) of a group $G$ was introduced by G. Pólya in [Po37, Eq. (1,5)]. Let $G \subseteq \symS_n$ be a subgroup. The cycle index polynomial is defined in terms of the power-sum symmetric functions as the average \[\cyc_G(\xvec) \coloneqq \frac{1}{|G|} \sum_{\pi \in G} \powerSum_{\type(\pi)}(\xvec).\]

Example

For $G=\symS_3,$ the cycle types are distributed as follows: one identity element of type $1^3,$ three transpositions of type $21,$ and two three-cycles of type $3.$ Hence \[\cyc_{\symS_3}(\xvec) = \frac{1}{6}\powerSum_{111} +\frac{1}{2}\powerSum_{21} +\frac{1}{3}\powerSum_{3}.\] Since \[\schurS_3 = \frac{1}{6}\powerSum_{111} +\frac{1}{2}\powerSum_{21} +\frac{1}{3}\powerSum_{3},\] we get $\cyc_{\symS_3}=\schurS_3.$ This matches the fact that $\setC[\symS_3/\symS_3]$ is the trivial representation.

Let $\symS_n/G$ denote the set of left 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 information on the cycle index polynomial, we refer to [LW19].

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 $\symS_{ab}$ acts 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).\] Foulkes conjecture states that if $a\leq b,$ then for all $\lambda,$ $c_{\lambda,a,b} \leq c_{\lambda,b,a}.$ This is equivalent to the statement that $\completeH_b[\completeH_a]-\completeH_a[\completeH_b]$ is Schur-positive whenever $a \leq b.$ The notation here indicates plethysm.

#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,\DES(\pi)}(\xvec)\] where $K_\lambda$ is the set of permutations in $\symS_n$ with cycle type $\lambda.$ See also [AHR19, Def. 1.5] for a representation-theoretic definition.

The Lyndon symmetric functions are also covered in [Sta01, p. 480], and it was shown by I. Gessel and C. Reutenauer [GR93, Thm. 3.6] that we have \[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.\] 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. More generally, K. Hou proves Sundaram’s bounded-interval higher-Lie positivity conjecture: for every $M,n\geq1,$ \[\sum_{\substack{d\mid n\\d\leq M}} L_{n/d}[\powerSum_d]\] is Schur-positive [Hou26]. Consequently, $\prod_{r=1}^{M}(1-\powerSum_r)^{-1}$ is Schur-positive. The same paper gives a counterexample to the proposed refinement in which the factors are separated by congruence class. A monomial expansion for $L_{\lambda}(\xvec)$ is given by summing over all multisets of primitive necklaces whose sizes are given by $\lambda.$ I. Gessel then gives a bijection from such multisets to words of length $n$ whose standardization permutation has cycle type $\lambda.$

See also [Sta01, Ex. 7.69c] 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].\]

M. Lee defines a Frobenius transform from symmetric functions to symmetric power series [Lee23]. Its Schur-basis matrix entries are restriction coefficients for polynomial representations of general linear groups, while the inverse of its finite-degree part has elementary-basis coefficients counted by words with constraints on their Lyndon factorizations. This gives another natural appearance of Lyndon-type symmetric functions in representation-theoretic transition matrices.

Problem (Thrall’s problem).

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

For background and a possible approach to this problem, see the GOCC lecture [Com23].

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 [AHR19, Conj. 7.13].

Problem

It is an open problem, discussed by R. P. Stanley in [Sta21], to find the (co)dimension of the span of the $L_\lambda.$

The functions $L_{n}(\xvec)$ are Lie characters, see [Reu93, Thm. 8.3]. R. Stanley discusses these also in [Sta]. 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]. Its 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?

For a different connection between symmetric-group character formulas and cycle factorizations, K. Trokowska and P. Śniady give a bijection between certain trees in Stanley’s character formula and minimal factorizations of a cycle [TS24].

Bibliography

[AHR19]Ron M Adin, Pál Hegedüs and Yuval Roichman. Higher Lie characters and cyclic descent extension on conjugacy classes. arXiv:1909.04460, 2019.

.bib

@ARTICLE{AdinHegedusRoichman2019x,
  title = {Higher {L}ie characters and cyclic descent extension on conjugacy classes},
  author = {Adin, Ron M and Heged{\"{u}}s, P{\'{a}}l and Roichman, Yuval},
  year = {2019},
  Eprint = {1909.04460},
  url = {https://arxiv.org/abs/1909.04460},
  journal = {arXiv e-prints}
}

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

.bib

@article{Foulkes1950,
  doi = {10.1112/jlms/s1-25.3.205},
  url2 = {https://doi.org/10.1112/jlms/s1-25.3.205},
  year = {1950},
  month = jul,
  publisher = {Wiley},
  volume = {s1-25},
  number = {3},
  pages = {205--209},
  author = {H. O. Foulkes},
  title = {Concomitants of the Quintic and Sextic Up To Degree Four in the Coefficients of the Ground Form},
  journal = {Journal of the London Mathematical Society}
}

[Com23]GOCC Combinatorics. GOCC 4/12/2023 “a crystal base approach to Thrall’s problem”. 2023. Video lecture

.bib

@misc{GOCC2023ThrallProblem,
  author = {{GOCC Combinatorics}},
  title = {{GOCC} 4/12/2023 ``A Crystal Base Approach to {Thrall}'s Problem''},
  year = {2023},
  url = {https://www.youtube.com/watch?v=bQc6D0aAu0M},
  note = {Video lecture}
}

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

.bib

@article{GesselReutenauer1993,
  doi = {10.1016/0097-3165(93)90095-p},
  url2 = {https://doi.org/10.1016/0097-3165(93)90095-p},
  year = {1993},
  month = nov,
  publisher = {Elsevier {BV}},
  volume = {64},
  number = {2},
  pages = {189--215},
  author = {Ira M Gessel and Christophe Reutenauer},
  title = {Counting permutations with given cycle structure and descent set},
  journal = {Journal of Combinatorial Theory,  Series A}
}

[GS25]Gutiérrez and Michał Szwej. A proof of the $q$-Foulkes conjecture for Gaussian coefficients when $a$ divides $c$. arXiv:2507.06220, 2025.

.bib

@article{GutierrezSzwej2025x,
Author = {{\'{A}}lvaro Guti{\'{e}}rrez and Micha{\l} Szwej},
Title = {A proof of the $q$-{F}oulkes conjecture for {G}aussian coefficients when $a$ divides $c$},
Year = {2025},
Eprint = {2507.06220},
  url = {https://arxiv.org/abs/2507.06220},
journal = {arXiv e-prints}
}

[Hou26]Kesen Hou. A Proof of Sundaram’s Bounded-Interval Higher Lie Positivity Conjecture. arXiv:2607.12749v1, 2026.

.bib

@article{Hou2026x,
  author = {Kesen Hou},
  title = {A {P}roof of {S}undaram's {B}ounded-{I}nterval {H}igher {L}ie
    {P}ositivity {C}onjecture},
  year = {2026},
  eprint = {2607.12749v1},
  url = {https://arxiv.org/abs/2607.12749v1},
  journal = {arXiv e-prints}
}

[Lee23]Mitchell Lee. The Frobenius transform of a symmetric function. arXiv:2307.06678, 2023.

.bib

@article{Lee2023x,
  author = {Mitchell Lee},
  title = {The {F}robenius transform of a symmetric function},
  year = {2023},
  eprint = {2307.06678},
  url = {https://arxiv.org/abs/2307.06678},
  journal = {arXiv e-prints}
}

[LW19]Nicholas A. Loehr and Gregory S. Warrington. Quasisymmetric and Schur expansions of cycle index polynomials. Discrete Mathematics, 342(1):113–127, January 2019.

.bib

@article{LoehrWarrington2019,
  doi = {10.1016/j.disc.2018.09.008},
  url2 = {https://doi.org/10.1016/j.disc.2018.09.008},
  year = {2019},
  month = jan,
  publisher = {Elsevier {BV}},
  volume = {342},
  number = {1},
  pages = {113--127},
  author = {Nicholas A. Loehr and Gregory S. Warrington},
  title = {Quasisymmetric and {S}chur expansions of cycle index polynomials},
  journal = {Discrete Mathematics}
}

[Po37]G. Pólya. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68(0):145–254, 1937.

.bib

@article{Polya1937,
  doi = {10.1007/bf02546665},
  url2 = {https://doi.org/10.1007/bf02546665},
  year = {1937},
  publisher = {International Press of Boston},
  volume = {68},
  number = {0},
  pages = {145--254},
  author = {G. P{\'{o}}lya},
  title = {Kombinatorische {A}nzahlbestimmungen f{\"{u}}r {G}ruppen,  {G}raphen und chemische {V}erbindungen},
  journal = {Acta Mathematica}
}

[Reu93]C. Reutenauer. Free lie algebras. LMS monographs. Clarendon Press, 1993.

.bib

@book{Reutenauer1993,
  title={Free Lie Algebras},
  author={Reutenauer, C.},
  isbn={9780198536796},
  lccn={lc92027318},
  series={LMS monographs},
  year={1993},
  publisher={Clarendon Press}
}

[Sta01]Richard P. Stanley. Enumerative Combinatorics: Volume 2. Cambridge University Press, First, 2001.

.bib

@book{StanleyEC2,
    author = {Richard P. Stanley},
    title = {Enumerative {C}ombinatorics: {V}olume 2},
    publisher = {Cambridge University Press},
    year = {2001},
    edition = {First},
    isbn = {0521789877},
    doi = {10.1017/CBO9780511609589}
}

[Sta21]Richard P. Stanley. FPSAC 2021: Richard Stanley. 2021. Video lecture

.bib

@misc{StanleyFPSAC2021,
  author = {Richard P. Stanley},
  title = {{FPSAC} 2021: {Richard Stanley}},
  year = {2021},
  url = {https://www.youtube.com/watch?v=NDAzHTP3vOs},
  note = {Video lecture}
}

[Sta]Richard Stanley. The Whitehouse representation. Online, 0. Slides

.bib

@misc{StanleyWhitehouse,
  author = {Richard Stanley},
  title = {The {W}hitehouse representation},
  howpublished = {Online},
  year = {},
  note = {Slides},
  url = {https://math.mit.edu/~rstan/transparencies/whouse.pdf}
}

[Te20]Tétreault. Recurrence relation for plethysm. arXiv:2008.13070, 2020.

.bib

@article{Tetreault2020x,
Author = {{\'{E}}tienne T{\'{e}}treault},
Title = {Recurrence relation for plethysm},
Year = {2020},
Eprint = {2008.13070},
  url = {https://arxiv.org/abs/2008.13070},
journal = {arXiv e-prints}
}

[TS24]Karolina Trokowska and Piotr Śniady. Bijection between trees in Stanley character formula and factorizations of a cycle. The Electronic Journal of Combinatorics, 31(1):P1.23, 2024.

.bib

@article{TrokowskaSniady2024,
  author = {Karolina Trokowska and Piotr {\'S}niady},
  title = {Bijection between trees in {S}tanley character formula and factorizations of a cycle},
  journal = {The Electronic Journal of Combinatorics},
  volume = {31},
  number = {1},
  pages = {P1.23},
  year = {2024},
  doi = {10.37236/11577}
}