# Cyclic sieving

In combinatorial mathematics, cyclic sieving is a phenomenon in which an integer polynomial evaluated at certain roots of unity counts the rotational symmetries of a finite set. Given a family of cyclic sieving phenomena, the polynomials give a q-analogue for the enumeration of the sets, and often arise from an underlying algebraic structure, such as a representation.
The first study of cyclic sieving was published by Reiner, Stanton and White in 2004. The phenomenon generalizes the "q = −1 phenomenon" of John Stembridge, which considers evaluations of the polynomial only at the first and second roots of unity (that is, q = 1 and q = −1).

## Definition

For every positive integer $n$, let $\omega _{n}$ denote the primitive $n$th root of unity $e^{2\pi i/n}$.
Let $X$ be a finite set with an action of the cyclic group $C_{n}$, and let $f(q)$ be an integer polynomial. The triple $(X,C_{n},f(q))$ exhibits the cyclic sieving phenomenon (or CSP) if for every positive integer $d$ dividing $n$, the number of elements in $X$ fixed by the action of the subgroup $C_{d}$ of $C_{n}$ is equal to $f(\omega _{d})$. If $C_{n}$ acts as rotation by $2\pi /n$, this counts elements in $X$ with $d$-fold rotational symmetry.
Equivalently, suppose $\sigma :X\to X$ is a bijection on $X$ such that $\sigma ^{n}={\rm {id}}$, where ${\rm {id}}$ is the identity map. Then $\sigma$ induces an action of $C_{n}$ on $X$, where a given generator $c$ of $C_{n}$ acts by $\sigma$. Then $(X,C_{n},f(q))$ exhibits the cyclic sieving phenomenon if the number of elements in $X$ fixed by $\sigma ^{d}$ is equal to $f(\omega _{n}^{d})$ for every integer $d$.

## Example

Let $X$ be the 2-element subsets of $\{1,2,3,4\}$. Define a bijection $\sigma :X\to X$ which increases each element in the pair by one (and sends $4$ back to $1$). This induces an action of $C_{4}$ on $X$, which has an orbit $\{1,3\}\mapsto \{2,4\}\mapsto \{1,3\}$ of size two and an orbit $\{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(i)=0$ counts fixed points of $\sigma$, $f(-1)=2$ is the number of fixed points of $\sigma ^{2}$, and $f(i)=0$ is the number of fixed points of $\sigma$. Hence, the triple $(X,C_{4},f(q))$ exhibits the cyclic sieving phenomenon.
More generally, set $[n]_{q}:=1+q+\cdots +q^{n-1}$ and define the q-binomial coefficient by $\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 [2]_{q}[1]_{q}}}.$ which is an integer polynomial evaluating to the usual binomial coefficient at $q=1$. For any positive integer $d$ dividing $n$,
    $\left[{n \atop k}\right]_{\omega _{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,\dots ,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\leq k\leq n$.

## 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)$.
Let $V=\mathbb {C} (X)$ be the vector space over the complex numbers 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}$.
For a generator $c$ of $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(\omega _{n}^{d})=\chi (c^{d})$ for every $0\leq d<n$, where $\chi$ is the character of $V$.
This gives a method for determining $f(q)$. For every integer $k$, let $V^{(k)}$ be the one-dimensional representation of $C_{n}$ in which $c$ acts as scalar multiplication by $\omega _{n}^{k}$. For an integer polynomial f(q)=∑$_{k≥0}$m$_k$q$^k${\textstyle f(q)=\sum _{k\geq 0}m_{k}q^{k}}, the triple $(X,C_{n},f(q))$ exhibits the cyclic sieving phenomenon if and only if $V\cong \bigoplus _{k\geq 0}m_{k}V^{(k)}.$

## Further examples

Let $W$ be a finite set of words of the form $w=w_{1}\cdots 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 denoted ${\rm {maj}}(w)$.
If $C_{n}$ acts on $W$ by rotating the letters of each word, and $f(q)=\sum _{w\in W}q^{{\rm {maj}}(w)}$ then $(W,C_{n},f(q))$ exhibits the cyclic sieving phenomenon.
Let $\lambda$ be a partition of size $n$ with rectangular shape, and let $X_{\lambda }$ be the set of standard Young tableaux with shape $\lambda$. Jeu de taquin promotion gives an action of $C_{n}$ on $X$. Let $f(q)$ be the following q-analog of the hook length formula: $f_{\lambda }(q)={\frac {[n]_{q}\cdots [1]_{q}}{\prod _{(i,j)\in \lambda }[h(i,j)]_{q}}}.$ Then $(X_{\lambda },C_{n},f_{\lambda }(q))$ exhibits the cyclic sieving phenomenon. If $\chi _{\lambda }$ is the character for the irreducible representation of the symmetric group associated to $\lambda$, then $f_{\lambda }(\omega _{n}^{d})=\pm \chi _{\lambda }(c^{d})$ for every $0\leq d<n$, where $c$ is the long cycle $(12\cdots n)$.
If $Y$ is the set of semistandard Young tableaux of shape $\lambda$ with entries in $\{1,\dots ,k\}$, then promotion gives an action of the cyclic group $C_{k}$ on $Y_{\lambda }$. Define κ(λ)=∑$_i$(i−1)λ$_i${\textstyle \kappa (\lambda )=\sum _{i}(i-1)\lambda _{i}} and $g(q)=q^{-\kappa (\lambda )}s_{\lambda }(1,q,\dots ,q^{k-1}),$ where $s_{\lambda }$ is the Schur polynomial. Then $(Y,C_{k},g(q))$ exhibits the cyclic sieving phenomenon.
If $X$ is the set of non-crossing (1,2)-configurations of $\{1,\dots ,n-1\}$, then $C_{n-1}$ acts on these by rotation. Let $f(q)$ be the following q-analog of the $n$th Catalan number: $f(q)={\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q}.$ Then $(X,C_{n-1},f(q))$ exhibits the cyclic sieving phenomenon.
Let $X$ be the set of semi-standard Young tableaux of shape $(n,n)$ with maximal entry $2n-k$, where entries along each row and column are strictly increasing. If $C_{2n-k}$ acts on $X$ by $K$-promotion and $f(q)=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}}},$ then $(X,C_{2n-k},f(q))$ exhibits the cyclic sieving phenomenon.
Let $S_{\lambda ,j}$ be the set of permutations of cycle type $\lambda$ with exactly $j$ exceedances. Conjugation gives an action of $C_{n}$ on $S_{\lambda ,j}$, and if $a_{\lambda ,j}(q)=\sum _{\sigma \in S_{\lambda ,j}}q^{\operatorname {maj} (\sigma )-j}$ then $(S_{\lambda ,j},C_{n},a_{\lambda ,j}(q))$ exhibits the cyclic sieving phenomenon.