Cyclic sieving

A q-analogue of the hook length formula exhibits cyclic sieving, with evaluations at roots of unity counting the number of rectangular standard Young tableaux fixed by repeated applications of jeu de taquin promotion.

In combinatorial mathematics, cyclic sieving is a phenomenon in which an integer polynomial evaluated at roots of unity counts the symmetries of the action of a cyclic group on a finite set.[1] Given a family of such phenomena, the polynomials give a q-analogue for the enumeration of the sets, often arising from an underlying algebraic structure such as a representation.

Definition

Let C_n be the cyclic group of order n acting on a finite set X, and suppose f(q) is a polynomial with integer coefficients. The triple (X, C_n, f(q)) exhibits the cyclic sieving phenomenon (or CSP) if for all positive integers d dividing n, the number of elements in X fixed by the subgroup C_d of C_n is equal to f(e^2πi/d). If C_n acts by rotation on the set X, then this counts elements with d-fold rotational symmetry.

Equivalently, if c is an element of order n in C_n, then f(e^2πid/n) counts the number of elements in X fixed by c^d for every integer d.

Example

Let X be the set of size-2 subsets of {1, 2, 3, 4}. The cyclic group C₄ acts on X by increasing each element by in the subset by one (where 4 is sent back to 1). This action splits X into an orbit

${\displaystyle \{1,3\}\mapsto \{2,4\}\mapsto \{1,3\}}$

of size two and an orbit

${\displaystyle \{1,2\}\mapsto \{2,3\}\mapsto \{3,4\}\mapsto \{1,4\}\mapsto \{1,2\}}$

of size four. If f(q) = 1 + q + 2q^2 + q^3 + q^4, then f(1) = 6 is the number of elements in X, f(-1) = 2 counts elements fixed by two iterations of the action, and f(i) = 0 counts elements fixed by one iteration. Hence, the triple (X, C₄, f(q)) exhibits the cyclic sieving phenomenon.

More generally, set ${\displaystyle [n]_{q}:=1+q+\cdots +q^{n-1}}$ and define the q-binomial coefficient by

${\displaystyle \left[{n \atop k}\right]_{q}={\frac {[n]_{q}\cdots [2]_{q}[1]_{q}}{[k]_{q}\cdots [2]_{q}[1]_{q}[n-k]_{q}\cdots [1]_{q}}}.}$

which is an integer polynomial evaluating to the usual binomial coefficient at q = 1. For any positive integer d dividing n,

${\displaystyle \left[{n \atop k}\right]_{e^{2\pi i/d}}={\begin{cases}\left({n/d \atop k/d}\right)&{\text{if }}d\mid k,\\0&{\text{otherwise}}.\end{cases}}}$

If X_n,k is the set of size-k subsets of {1, 2, ..., n} with C_n acting by increasing each element in the subset by one (and sending n back to 1), and if f_n,k(q) is the q-binomial coefficient above, then (X_n,k, C_n, f_n,k(q)) exhibits the cyclic sieving phenomenon for every 0 ≤ k ≤ n.[2]

In representation theory

The cyclic sieving phenomenon can be naturally stated in the language of representation theory. The group action of C_n on X is linearly extended to obtain a representation, and the decomposition of this representation into irreducibles determines the required coefficients of the polynomial f(q).[3]

Let V = C[X] be the vector space over the complex numbers C with a basis indexed by a finite set X. If the cyclic group C_n acts on X, then linearly extending each action turns V into a representation of C_n.

If c generates C_n, the linear extension of its action on X gives a permutation matrix [c], and the trace of [c]^d counts the elements of X fixed by c^d. In particular, the triple (X, C_n, f(q)) exhibits the cyclic sieving phenomenon if and only if f(e^2πid/n) = χ(c^d) for every integer d, where χ is the character of V.

This gives a method for determining the polynomial f(q). For every integer k, let V^(k) be the one-dimensional representation of C_n in which the generator c acts as scalar multiplication by e^2πik/n. For an integer polynomial

${\displaystyle f(q)=\sum _{i\geq 0}m_{i}q^{i},}$

the triple (X, C_n, f(q)) exhibits the cyclic sieving phenomenon if and only if

${\displaystyle V\cong \bigoplus _{i\geq 0}m_{i}V^{(i)}.}$

Further examples

Let W be a finite set of words of the form w = w₁w₂...w_n where each letter w_j is an integer and W is closed under permutation (that is, if w is in W, then so is any anagram of w). The major index of a word w is the sum of all indices j such that w_j > w_j+1, and is written as maj(w).

If C_n acts on W by rotating the letters of each word, and f(q) is the polynomial

${\displaystyle f(q)=\sum _{w\in W}q^{\rm {{maj}(w)}}}$

then (W, C_n, f(q)) exhibits the cyclic sieving phenomenon.[4]

---

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

---

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

---

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

---

Let ${\displaystyle S_{\lambda ,j}}$ be the set of permutations of cycle type λ and exactly j exceedances. 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.[8]

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. Reiner, V.; Stanton, D.; White, D. (2004). "The cyclic sieving phenomenon". Journal of Combinatorial Theory, Series A. 108 (1): 17–50. doi:10.1016/j.jcta.2004.04.009.
3. Sagan, Bruce (2011). The cyclic sieving phenomenon: a survey. Cambridge University Press. pp. 183–234.
4. Berget, Andrew; Eu, Sen-Peng; Reiner, Victor (2011). "Constructions for Cyclic Sieving Phenomena". SIAM Journal on Discrete Mathematics. 25 (3): 1297-1314. doi:10.1137/100803596.
5. Thiel, Marko (March 2017). "A new cyclic sieving phenomenon for Catalan objects". Discrete Mathematics. 340 (3): 426–9. arXiv:1601.03999. doi:10.1016/j.disc.2016.09.006. S2CID 207137333.
6. 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. S2CID 6294586.
7. 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. S2CID 18693328.
8. 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. S2CID 379574.

• Sagan, Bruce (2011). "The cyclic sieving phenomenon: a survey". In Chapman, Robin (ed.). Surveys in Combinatorics 2011. London Mathematical Society Lecture Note Series. Vol. 392. Cambridge University Press. pp. 183–233. ISBN 978-1-139-50368-6.