Cyclic sieving

In combinatorial mathematics, cyclic sieving is a phenomenon by which evaluating a generating function for a finite set at roots of unity counts symmetry classes of objects acted on by a cyclic group.[1]

Definition

Let C be a cyclic group generated by an element c of order n. Suppose C acts on a set X. Let X(q) be a polynomial with integer coefficients. Then the triple (X, X(q), C) is said to exhibit the cyclic sieving phenomenon (CSP) if for all integers d, the value X(e^2πid/n) is the number of elements fixed by c^d. In particular X(1) is the cardinality of the set X, and for that reason X(q) is regarded as a generating function for X.

Examples

The q-binomial coefficient

${\displaystyle \left[{n \atop k}\right]_{q}}$

is the polynomial in q defined by

${\displaystyle \left[{n \atop k}\right]_{q}={\frac {\prod _{i=1}^{n}(1+q+q^{2}+\cdots +q^{i-1})}{\left(\prod _{i=1}^{k}(1+q+q^{2}+\cdots +q^{i-1})\right)\cdot \left(\prod _{i=1}^{n-k}(1+q+q^{2}+\cdots +q^{i-1})\right)}}.}$

It is easily seen that its value at q = 1 is the usual binomial coefficient ${\displaystyle {\binom {n}{k}}}$, so it is a generating function for the subsets of {1, 2, ..., n} of size k. These subsets carry a natural action of the cyclic group C of order n which acts by adding 1 to each element of the set, modulo n. For example, when n = 4 and k = 2, the group orbits are

${\displaystyle \{1,3\}\to \{2,4\}\to \{1,3\}}$ (of size 2)

and

${\displaystyle \{1,2\}\to \{2,3\}\to \{3,4\}\to \{1,4\}\to \{1,2\}}$ (of size 4).

One can show[2] that evaluating the q-binomial coefficient when q is an nth root of unity gives the number of subsets fixed by the corresponding group element.

In the example n = 4 and k = 2, the q-binomial coefficient is

${\displaystyle \left[{4 \atop 2}\right]_{q}=1+q+2q^{2}+q^{3}+q^{4};}$

evaluating this polynomial at q = 1 gives 6 (as all six subsets are fixed by the identity element of the group); evaluating it at q = −1 gives 2 (the subsets {1, 3} and {2, 4} are fixed by two applications of the group generator); and evaluating it at q = ±i gives 0 (no subsets are fixed by one or three applications of the group generator).

List of cyclic sieving phenomena

In the Reiner–Stanton–White paper, the following example is given:

Let α be a composition of n, and let W(α) be the set of all words of length n with α_i letters equal to i. A descent of a word w is any index j such that ${\displaystyle w_{j}>w_{j+1}}$. Define the major index ${\displaystyle \operatorname {maj} (w)}$ on words as the sum of all descents.

---

The triple ${\displaystyle (X_{n},C_{n-1},{\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q})}$ exhibit a cyclic sieving phenomenon, where ${\displaystyle X_{n}}$ is the set of non-crossing (1,2)-configurations of [n − 1]. [3]

---

Let λ be a rectangular partition of size n, and let X be the set of standard Young tableaux of shape λ. Let C = Z/nZ act on X via promotion. Then ${\displaystyle (X,C,{\frac {[n]!_{q}}{\prod _{(i,j)\in \lambda }[h_{ij}]_{q}}})}$ exhibit the cyclic sieving phenomenon. Note that the polynomial is a q-analogue of the hook length formula.

Furthermore, let λ be a rectangular partition of size n, and let X be the set of semi-standard Young tableaux of shape λ. Let C = Z/kZ act on X via k-promotion. Then ${\displaystyle (X,C,q^{-\kappa (\lambda )}s_{\lambda }(1,q,q^{2},\dotsc ,q^{k-1}))}$ exhibit the cyclic sieving phenomenon. Here, ${\displaystyle \kappa (\lambda )=\sum _{i}(i-1)\lambda _{i}}$ and s_λ is the Schur polynomial. [4]

---

An increasing tableau is a semi-standard Young tableau, where both rows and columns are strictly increasing, and the set of entries is of the form ${\displaystyle 1,2,\dotsc ,\ell }$ for some ${\displaystyle \ell }$. Let ${\displaystyle Inc_{k}(2\times n)}$ denote the set of increasing tableau with two rows of length n, and maximal entry ${\displaystyle 2n-k}$. Then ${\displaystyle (\operatorname {Inc} _{k}(2\times n),C_{2n-k},q^{n+{\binom {k}{2}}}{\frac {\left[{n-1 \atop k}\right]_{q}\left[{2n-k \atop n-k-1}\right]_{q}}{[n-k]_{q}}})}$ exhibit the cyclic sieving phenomenon, where ${\displaystyle C_{2n-k}}$ act via K-promotion.[5]

---

Let ${\displaystyle S_{\lambda ,j}}$ be the set of permutations of cycle type λ and exactly j excedances. Let ${\displaystyle a_{\lambda ,j}(q)=\sum _{\sigma \in S_{\lambda ,j}}q^{\operatorname {maj} (\sigma )-\operatorname {exc} (\sigma )}}$, and let ${\displaystyle C_{n}}$ act on ${\displaystyle S_{\lambda ,j}}$ by conjugation.

Then ${\displaystyle (S_{\lambda ,j},C_{n},a_{\lambda ,j}(q))}$ exhibit the cyclic sieving phenomenon. [6]

Notes and references

1. Reiner, Victor; Stanton, Dennis; White, Dennis (February 2014), "What is... Cyclic Sieving?" (PDF), Notices of the American Mathematical Society, 61 (2): 169–171, doi:10.1090/noti1084
2. V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, Journal of Combinatorial Theory, Series A, Volume 108 Issue 1, October 2004, Pages 17–50
3. Thiel, Marko (March 2017). "A new cyclic sieving phenomenon for Catalan objects". Discrete Mathematics. 340 (3): 426–429. arXiv:1601.03999. doi:10.1016/j.disc.2016.09.006.
4. Rhoades, Brendon (January 2010). "Cyclic sieving, promotion, and representation theory". Journal of Combinatorial Theory, Series A. 117 (1): 38–76. arXiv:1005.2568. doi:10.1016/j.jcta.2009.03.017.
5. Pechenik, Oliver (July 2014). "Cyclic sieving of increasing tableaux and small Schröder paths". Journal of Combinatorial Theory, Series A. 125: 357–378. arXiv:1209.1355. doi:10.1016/j.jcta.2014.04.002.
6. Sagan, Bruce; Shareshian, John; Wachs, Michelle L. (January 2011). "Eulerian quasisymmetric functions and cyclic sieving". Advances in Applied Mathematics. 46 (1–4): 536–562. arXiv:0909.3143. doi:10.1016/j.aam.2010.01.013.

• Sagan, Bruce. The cyclic sieving phenomenon: a survey. Surveys in combinatorics 2011, 183–233, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011.