Improve this page

See the cyclic sieving phenomenon page for the definition and related theorems.

#Words and permutations

#Words

Let \(X_n(\alpha)\) be the set of words of length \(n\) and content \(\alpha\); that is, each word has \(\alpha_i\) entries equal to \(i.\) Let the cyclic group \(\grpc_n\) act on \(X_n(\alpha)\) by cyclic shift, and let \[f_n(\alpha;q) \coloneqq \qbinom{n}{\alpha}_q = \sum_{w \in X_n(\alpha)} q^{\maj(w)} = \sum_{w \in X_n(\alpha)} q^{\inv(w)}.\] Then \((X_n(\alpha),\grpc_n,f_n(\alpha;q))\) exhibits the CSP, see [RSW04].

#Multisets

Let \(X_{n,k}\) be the set of \(k\)-multisets of \([n].\) Note that \(|X_{n,k}| = \binom{n+k-1}{k}.\) For \(n=3,\) \(k=2\) we have \[X = \{11,12,13,22,23,33 \}.\] Let \(\grpc_n = \langle g \rangle\) act on \(X_{n,k}\) by the cycle \(g=(123\dotsb n),\) so that \(g\circ 23 = 31 = 13\) in the example above. Then \[\left( X_{n,k}, \grpc_n, \qbinom{n+k-1}{k}_q \right)\] exhibits the CSP [RSW04].

D. Armstrong studies the bounded-multiplicity interpolation between subsets and multisets [Arm25]. Let \(X_{n,k}^{(b)}\) be the set of \(k\)-multisets of \([n]\) in which each element has multiplicity at most \(b-1,\) and let the long cycle act on the entries. Define \(h_k^{(b)}(z_1,\dotsc,z_n)\) by \[\sum_{k\geq 0} h_k^{(b)}(z_1,\dotsc,z_n)t^k \coloneqq \prod_{i=1}^{n} \left(1+z_i t+(z_i t)^2+\dotsb+(z_i t)^{b-1}\right).\] Under suitable coprimality and divisibility hypotheses, the specialization \(h_k^{(b)}(1,q,\dotsc,q^{n-1})\) gives cyclic sieving phenomena on \(X_{n,k}^{(b)}.\) This recovers the subset case when \(b=2\) and the ordinary multiset case in the limit \(b\to \infty.\)

#Binary words with a twist

Let \(X_n\) be the set of binary words and let \(\eta\) act on \(X_n\) by a twisted cyclic shift \[\eta(b_1,b_2,\dotsc,b_{n-1},b_n) = (1-b_n,b_1,b_2,\dotsc,b_{n-1}),\] which generates a cyclic group of order \(2n,\) so \(\langle \eta^2 \rangle\) is a cyclic group of order \(n.\) Then \[\left(X_n, \langle \eta^2 \rangle, \prod_{j=0}^{n-1}(1+q^j) \right)\] exhibits the cyclic sieving phenomenon. This is proved in [ALP19].

By adjusting the \(q\)-analogue a bit, one can show that \[\left(X_n, \langle \eta \rangle, \prod_{j=1}^{n}(1+q^j) \right)\] is an instance of CSP. Note that the \(q\)-binomial theorem implies that \(\prod_{j=1}^{n}(1+q^j) = \sum_{k=0}^n q^{\binom{k+1}{2}} \qbinom{n}{k}.\)

See also the example on subset-cyclic sieving, for restricting the set of words we act on.

S. Hopkins pointed out that this also follows from [RS12], with cyclic sieving on minuscule posets of type \(B\). The idea is to biject order ideals to binary words. This in turn is related to [Cor. 8.5, RSW04], by taking \(k=0\) in their statement.

#General words with a twist

We can generalize the twisted binary words CSP.

Definition

Let \(W(n,k)\) denote the set of words of length \(n\) with entries in \(\{1,2,\dotsc,k\}.\) Given \(w=(w_1,\dotsc,w_n) \in W(n,k),\) let \[\phi(w) \coloneqq (w_n+1,w_1,w_2,\dotsc,w_{n-1}),\] where the addition is taken modulo \(k.\) Note that \(\phi^{\circ n}(w) = w+1,\) and hence \(\phi\) generates a cyclic group of order \(nk.\)

Conjecture (Alexandersson, 2022).

For every \(n,k\geq 1,\) \[\left( W(n,k), \left\langle \phi \right\rangle, \prod_{j=1}^{n}\left(1+q^j+q^{2j}+q^{3j}+\dotsb+q^{(k-1)j}\right) \right)\] is a CSP-triple.

#Kreweras words

S. Hopkins and M. Rubey conjecture a CSP on the set of Kreweras words of length \(3n\) [HR21]. These are in bijection with linear extensions of a certain poset, and also with so-called Kreweras webs. The group action is promotion in the linear extensions, which is equivalent to rotation of the webs.

M. Gatzweiler and C. Krattenthaler prove positivity results for quotients of \(q\)-binomial coefficients which imply that the conjectural cyclic sieving polynomial for Kreweras words is indeed a polynomial with nonnegative integer coefficients [GK25].

#Lucas binary words

The following results are proved in [Gor19].

Let \(LW_{n}\) be the set of binary words of length \(n,\) such that there are no two consecutive ones, not even cyclically. We let \(\grpc_n\) act on \(LW_{n}\) by rotation. We note that \(|LW_{n}|= L_n,\) a Lucas number, A000032. Define the \(2\times 2\)-matrix \(A(x,t)\) with entries in \(\setZ[q,t]\) as \[A(x,t)\coloneqq \begin{bmatrix} 1 & t \\ x & 0 \end{bmatrix}\] and let \[|LW_{n}|_q \coloneqq \trace \left( A(q^{n-1},1) A(q^{n-2},1) \dotsm A(1,1) \right).\] This is a \(q\)-analogue of the Lucas number \(L_{n}.\) Then the following is a CSP-triple: \[\left( LW_n, \grpc_n, |LW_{n}|_q \right).\]

This result can be refined in the following manner. Let \(LW_{n,k}\subset LW_{n}\) be the subset of binary words with exactly \(k\) ones. Let \[|LW_{n,k}|_q \coloneqq [t^k] \trace \left( A(q^{n-1},t) A(q^{n-2},t) \dotsm A(1,t) \right).\] This is a \(q\)-analogue of \(|LW_{n,k}|\) and in fact, \[|LW_{n,k}|_q = \sum_{w \in LW_{n,k}} q^{\stat(w)} = q^{k^2-k}\qbinom{n-k+1}{k}_q - q^{n+(k-1)^2-k}\qbinom{n-k-1}{k-2}_q.\] where \(\stat(w) = \sum_{i=1}^n [w_i=1] (n-i),\) using the Iverson bracket. We have the CSP-triple \[\left( LW_{n,k}, \grpc_n, |LW_{n,k}|_q \right).\]

#Reduced words of \(w_0\) in type B

Let \(X_n\) be the set of all reduced words for the longest element in the type \(B_n\) Coxeter group. We can define major index on these. Let \(C_{n^2}\) act on such reduced words by rotation. Then \[\left( X_n, C_{n^2}, q^{-n\binom{n}{2}}\sum_{w \in X_n} q^{\maj(w)} \right)\] is a CSP-triple. The proof in [PS10] uses a bijection to \(n\times n\)-SYT and then the rectangular SYT CSP of B. Rhoades.

#Permutations of fixed type and exceedances

The following CSP is proved in [SSW11]. Let \(S_{\lambda,j} \subseteq \symS_n\) be the set of permutations of cycle type \(\lambda\) and exactly \(j\) exceedances. Let \(\grpc_n\) be generated by the long cycle \((1\,2\,3\,\dotsb\,n),\) and let it act on \(S_{\lambda,j}\) by conjugation. Define \[f_{\lambda,j}(q) \coloneqq \sum_{\pi \in S_{\lambda,j} } q^{\maj(\pi) - \exc(\pi)}.\] Then \((S_{\lambda,j}, \grpc_n, f_{\lambda,j}(q))\) is a CSP-triple.

#Permutations

The following CSP is a special case of the CSP on binary matrices. Let \(\symS_n\) be the set of permutations, seen as a list of pairs \(\{i,\pi(i)\},\) \(1 \leq i \leq n.\) We let \(C_n = \langle g \rangle\) act on such pairs by \(g \cdot \{i,\pi(i)\} = \{i+1,\pi(i)+1\},\) where addition is performed modulo \(n.\)

Then \[\left( \symS_n, C_n, \sum_{\lambda \vdash n} (f^{\lambda}(q))^2 \right)\] is a CSP-triple, where \(f^{\lambda}(q)\) is the \(q\)-analogue of the hook formula.

#Permutations of fixed shape

RSK gives a bijection between the set \(\SYT(\lambda) \times \SYT(\lambda)\) and permutations in \(\symS_n\) which insert to a pair of Young tableaux of shape \(\lambda.\) In [Thm. 44, APRU21], it is shown that there exists a cyclic group action of order \(n\) such that for any \(\lambda \vdash n,\) \[\left( \SYT(\lambda) \times \SYT(\lambda), C_n, \left(f^{\lambda}(q)\right)^2 \right)\] is a CSP-triple. The proof is existential, and does not give a natural action on the pairs of tableaux.

Problem

Find an explicit order-\(n\) action on \(\SYT(\lambda) \times \SYT(\lambda)\) which realizes this cyclic sieving phenomenon for arbitrary \(\lambda \vdash n.\)

Note that this refines the CSP on permutation matrices.

#Labelings of the path graph

The path graph \(P_n\) on \(n\) vertices has \(n!\) labelings, using labels from \(\setZ/n\setZ.\) The authors of [DMT23] study a version of promotion, named toric promotion. They introduce permutoric promotion, which is an operator determined by a permutation \(\pi\) in \(\symS_n.\) The role of \(\pi\) is to decide in which order to perform certain local toggles.

Permutoric promotion, \(\mathrm{TPro}_{\pi},\) acts on labelings with order \(d(n-d)\) where \(d\) is the number of descents of \(\pi^{-1}.\) They show that \[\left( \text{Labelings of $P_n$}, \mathrm{TPro}_{\pi}, n(d-1)!(n-d-1)! [n-d]_{q^d} \qbinom{n-1}{d-1}_q \right)\] is a CSP-triple.

Bibliography

  1. [ALP19]Per Alexandersson, Svante Linusson and Samu Potka. The cyclic sieving phenomenon on circular Dyck paths. The Electronic Journal of Combinatorics, 26:1–32, October 2019.
    .bib
    @article{AlexanderssonLinussonPotka2019,
  doi = {10.37236/8720},
  url2 = {https://doi.org/10.37236/8720},
  year = {2019},
  month = oct,
  publisher = {The Electronic Journal of Combinatorics},
  author = {Per Alexandersson and Svante Linusson and Samu Potka},
  title = {The Cyclic Sieving Phenomenon on Circular {D}yck Paths},
  journal = {The Electronic Journal of Combinatorics},
  volume = {26},
  paper = {P4.16},
  pages = {1--32}
}
  2. [APRU21]Per Alexandersson, Stephan Pfannerer, Martin Rubey and Joakim Uhlin. Skew characters and cyclic sieving. Forum of Mathematics, Sigma, 9:e41, 2021.
    .bib
    @article{AlexanderssonPfannererRubeyUhlin2020,
Author = {Per Alexandersson and Stephan Pfannerer and Martin Rubey and Joakim Uhlin},
Title = {Skew characters and cyclic sieving},
doi = {10.1017/fms.2021.11},
Year = {2021},
volume = {9},
pages = {e41},
publisher={Cambridge University Press},
journal = {Forum of Mathematics, Sigma}
}
  3. [Arm25]Drew Armstrong. Cyclic Sieving of Multisets with Bounded Multiplicity and the Frobenius Coin Problem. arXiv:2502.00378, 2025.
    .bib
    @article{Armstrong2025BoundedMultiplicityCSP,
  author = {Drew Armstrong},
  title = {Cyclic {S}ieving of {M}ultisets with {B}ounded {M}ultiplicity and the {F}robenius {C}oin {P}roblem},
  year = {2025},
  eprint = {2502.00378},
  url = {https://arxiv.org/abs/2502.00378},
  journal = {arXiv e-prints}
}
  4. [DMT23]Colin Defant, Rachana Madhukara and Hugh Thomas. Permutoric promotion: Gliding globs, sliding stones, and colliding coins. arXiv:2305.19961, 2023.
    .bib
    @article{DefantMadhukaraThomas2023x,
Author = {Colin Defant and Rachana Madhukara and Hugh Thomas},
Title = {Permutoric Promotion: Gliding Globs, Sliding Stones, and Colliding Coins},
Year = {2023},
Eprint = {2305.19961},
  url = {https://arxiv.org/abs/2305.19961},
journal = {arXiv e-prints}
}
  5. [GK25]Mona Gatzweiler and Christian Krattenthaler. A positivity conjecture for a quotient of $q$-binomial coefficients. arXiv:2502.06032, 2025.
    .bib
    @article{GatzweilerKrattenthaler2025x,
  author = {Mona Gatzweiler and Christian Krattenthaler},
  title = {A positivity conjecture for a quotient of {$q$}-binomial coefficients},
  year = {2025},
  eprint = {2502.06032},
  url = {https://arxiv.org/abs/2502.06032},
  journal = {arXiv e-prints}
}
  6. [Gor19]Ofir Gorodetsky. $q$-congruences, with applications to supercongruences and the cyclic sieving phenomenon. International Journal of Number Theory, May 2019.
    .bib
    @article{Gorodetsky2019,
  doi = {10.1142/s1793042119501069},
  url2 = {https://doi.org/10.1142/s1793042119501069},
  year = {2019},
  month = may,
  publisher = {World Scientific Pub Co Pte Lt},
  author = {Ofir Gorodetsky},
  title = {$q$-congruences, with applications to Supercongruences and the cyclic sieving phenomenon},
  journal = {International Journal of Number Theory}
}
  7. [HR21]Sam Hopkins and Martin Rubey. Promotion of Kreweras words. Selecta Mathematica, 28(1), 2021.
    .bib
    @article{HopkinsRubey2021,
  author = {Hopkins, Sam and Rubey, Martin},
  title = {Promotion of {K}reweras words},
  year = {2021},
  journal = {Selecta Mathematica},
  volume = {28},
  number = {1},
  publisher = {Springer Science and Business Media LLC},
  doi = {10.1007/s00029-021-00714-6},
  url = {http://dx.doi.org/10.1007/s00029-021-00714-6},
  issn = {1420-9020}
}
  8. [PS10]T. Kyle Petersen and Luis Serrano. Cyclic sieving for longest reduced words in the hyperoctahedral group. The Electronic Journal of Combinatorics, 17(1), April 2010.
    .bib
    @article{PetersenSerrano2010,
  doi = {10.37236/339},
  url2 = {https://doi.org/10.37236/339},
  year = {2010},
  month = apr,
  publisher = {The Electronic Journal of Combinatorics},
  volume = {17},
  number = {1},
  author = {T. Kyle Petersen and Luis Serrano},
  title = {Cyclic Sieving for Longest Reduced Words in the Hyperoctahedral Group},
  journal = {The Electronic Journal of Combinatorics}
}
  9. [RSW04]Victor Reiner, Dennis Stanton and Dennis E. White. The cyclic sieving phenomenon. Journal of Combinatorial Theory, Series A, 108(1):17–50, October 2004.
    .bib
    @article{ReinerStantonWhite2004, 
	title={The cyclic sieving phenomenon}, 
	volume={108}, 
	url2={http://dx.doi.org/10.1016/j.jcta.2004.04.009}, 
	DOI={10.1016/j.jcta.2004.04.009}, 
	number={1}, 
	journal={Journal of Combinatorial Theory, Series A}, 
	publisher={Elsevier BV}, 
	author={Victor Reiner and Dennis Stanton and Dennis E. White}, 
	year={2004}, 
	month = oct, 
	pages={17--50}
}
  10. [RS12]David B. Rush and XiaoLin Shi. On orbits of order ideals of minuscule posets. Journal of Algebraic Combinatorics, 37(3):545–569, June 2012.
    .bib
    @article{RushShi2012,
  doi = {10.1007/s10801-012-0380-2},
  url2 = {https://doi.org/10.1007/s10801-012-0380-2},
  year = {2012},
  month = jun,
  publisher = {Springer Nature},
  volume = {37},
  number = {3},
  pages = {545--569},
  author = {David B. Rush and XiaoLin Shi},
  title = {On orbits of order ideals of minuscule posets},
  journal = {Journal of Algebraic Combinatorics}
}
  11. [SSW11]Bruce E. Sagan, John Shareshian and Michelle L. Wachs. Eulerian quasisymmetric functions and cyclic sieving. Advances in Applied Mathematics, 46(1):536–562, January 2011.
    .bib
    @article{SaganShareshianWachs2011,
  doi = {10.1016/j.aam.2010.01.013},
  url2 = {https://doi.org/10.1016/j.aam.2010.01.013},
  year  = {2011},
  month = jan,
  publisher = {Elsevier {BV}},
  volume = {46},
  number = {1},
  pages = {536--562},
  author = {Bruce E. Sagan and John Shareshian and Michelle L. Wachs},
  title = {Eulerian quasisymmetric functions and cyclic sieving},
  journal = {Advances in Applied Mathematics}
}

I use cookies to detect website issues and track search terms.