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

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.

The first study of cyclic sieving was published by Reiner, Stanton and White in 2004.^[2] 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).^[3]

Definition

For every positive integer ${\displaystyle n}$, let ${\displaystyle \omega _{n}}$ denote the primitive ${\displaystyle n}$^th root of unity ${\displaystyle e^{2\pi i/n}}$.

Let ${\displaystyle X}$ be a finite set with an action of the cyclic group ${\displaystyle C_{n}}$, and let ${\displaystyle f(q)}$ be an integer polynomial. The triple ${\displaystyle (X,C_{n},f(q))}$ exhibits the cyclic sieving phenomenon (or CSP) if for every positive integer ${\displaystyle d}$ dividing ${\displaystyle n}$, the number of elements in ${\displaystyle X}$ fixed by the action of the subgroup ${\displaystyle C_{d}}$ of ${\displaystyle C_{n}}$ is equal to ${\displaystyle f(\omega _{d})}$. If ${\displaystyle C_{n}}$ acts as rotation by ${\displaystyle 2\pi /n}$, this counts elements in ${\displaystyle X}$ with ${\displaystyle d}$-fold rotational symmetry.

Equivalently, suppose ${\displaystyle \sigma :X\to X}$ is a bijection on ${\displaystyle X}$ such that ${\displaystyle \sigma ^{n}={\rm {id}}}$, where ${\displaystyle {\rm {id}}}$ is the identity map. Then ${\displaystyle \sigma }$ induces an action of ${\displaystyle C_{n}}$ on ${\displaystyle X}$, where a given generator ${\displaystyle c}$ of ${\displaystyle C_{n}}$ acts by ${\displaystyle \sigma }$. Then ${\displaystyle (X,C_{n},f(q))}$ exhibits the cyclic sieving phenomenon if the number of elements in ${\displaystyle X}$ fixed by ${\displaystyle \sigma ^{d}}$ is equal to ${\displaystyle f(\omega _{n}^{d})}$ for every integer ${\displaystyle d}$.

Example

Let ${\displaystyle X}$ be the 2-element subsets of ${\displaystyle \{1,2,3,4\}}$. Define a bijection ${\displaystyle \sigma :X\to X}$ which increases each element in the pair by one (and sends ${\displaystyle 4}$ back to ${\displaystyle 1}$). This induces an action of ${\displaystyle C_{4}}$ on ${\displaystyle X}$, which has 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 ${\displaystyle f(q)=1+q+2q^{2}+q^{3}+q^{4}}$, then ${\displaystyle f(1)=6}$ is the number of elements in ${\displaystyle X}$, ${\displaystyle f(i)=0}$ counts fixed points of ${\displaystyle \sigma }$, ${\displaystyle f(-1)=2}$ is the number of fixed points of ${\displaystyle \sigma ^{2}}$, and ${\displaystyle f(i)=0}$ is the number of fixed points of ${\displaystyle \sigma }$. Hence, the triple ${\displaystyle (X,C_{4},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 [2]_{q}[1]_{q}}}.}$$ which is an integer polynomial evaluating to the usual binomial coefficient at ${\displaystyle q=1}$. For any positive integer ${\displaystyle d}$ dividing ${\displaystyle n}$,

${\displaystyle \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 ${\displaystyle X_{n,k}}$ is the set of size-${\displaystyle k}$ subsets of ${\displaystyle \{1,\dots ,n\}}$ with ${\displaystyle C_{n}}$ acting by increasing each element in the subset by one (and sending ${\displaystyle n}$ back to ${\displaystyle 1}$), and if ${\displaystyle f_{n,k}(q)}$ is the q-binomial coefficient above, then ${\displaystyle (X_{n,k},C_{n},f_{n,k}(q))}$ exhibits the cyclic sieving phenomenon for every ${\displaystyle 0\leq k\leq n}$.^[4]

In representation theory

The cyclic sieving phenomenon can be naturally stated in the language of representation theory. The group action of ${\displaystyle C_{n}}$ on ${\displaystyle X}$ is linearly extended to obtain a representation, and the decomposition of this representation into irreducibles determines the required coefficients of the polynomial ${\displaystyle f(q)}$.^[5]

Let ${\displaystyle V=\mathbb {C} (X)}$ be the vector space over the complex numbers with a basis indexed by a finite set ${\displaystyle X}$. If the cyclic group ${\displaystyle C_{n}}$ acts on ${\displaystyle X}$, then linearly extending each action turns ${\displaystyle V}$ into a representation of ${\displaystyle C_{n}}$.

For a generator ${\displaystyle c}$ of ${\displaystyle C_{n}}$, the linear extension of its action on ${\displaystyle X}$ gives a permutation matrix ${\displaystyle [c]}$, and the trace of ${\displaystyle [c]^{d}}$ counts the elements of ${\displaystyle X}$ fixed by ${\displaystyle c^{d}}$. In particular, the triple ${\displaystyle (X,C_{n},f(q))}$ exhibits the cyclic sieving phenomenon if and only if ${\displaystyle f(\omega _{n}^{d})=\chi (c^{d})}$ for every ${\displaystyle 0\leq d<n}$, where ${\displaystyle \chi }$ is the character of ${\displaystyle V}$.

This gives a method for determining ${\displaystyle f(q)}$. For every integer ${\displaystyle k}$, let ${\displaystyle V^{(k)}}$ be the one-dimensional representation of ${\displaystyle C_{n}}$ in which ${\displaystyle c}$ acts as scalar multiplication by ${\displaystyle \omega _{n}^{k}}$. For an integer polynomial ${\textstyle f(q)=\sum _{k\geq 0}m_{k}q^{k}}$, the triple ${\displaystyle (X,C_{n},f(q))}$ exhibits the cyclic sieving phenomenon if and only if $${\displaystyle V\cong \bigoplus _{k\geq 0}m_{k}V^{(k)}.}$$

Further examples

Let ${\displaystyle W}$ be a finite set of words of the form ${\displaystyle w=w_{1}\cdots w_{n}}$ where each letter ${\displaystyle w_{j}}$ is an integer and ${\displaystyle W}$ is closed under permutation (that is, if ${\displaystyle w}$ is in ${\displaystyle W}$, then so is any anagram of ${\displaystyle w}$). The major index of a word ${\displaystyle w}$ is the sum of all indices ${\displaystyle j}$ such that ${\displaystyle w_{j}>w_{j+1}}$, and is denoted ${\displaystyle {\rm {maj}}(w)}$.

If ${\displaystyle C_{n}}$ acts on ${\displaystyle W}$ by rotating the letters of each word, and $${\displaystyle f(q)=\sum _{w\in W}q^{{\rm {maj}}(w)}}$$ then ${\displaystyle (W,C_{n},f(q))}$ exhibits the cyclic sieving phenomenon.^[6]

---

Let ${\displaystyle \lambda }$ be a partition of size ${\displaystyle n}$ with rectangular shape, and let ${\displaystyle X_{\lambda }}$ be the set of standard Young tableaux with shape ${\displaystyle \lambda }$. Jeu de taquin promotion gives an action of ${\displaystyle C_{n}}$ on ${\displaystyle X}$. Let ${\displaystyle f(q)}$ be the following q-analog of the hook length formula: $${\displaystyle f_{\lambda }(q)={\frac {[n]_{q}\cdots [1]_{q}}{\prod _{(i,j)\in \lambda }[h(i,j)]_{q}}}.}$$ Then ${\displaystyle (X_{\lambda },C_{n},f_{\lambda }(q))}$ exhibits the cyclic sieving phenomenon. If ${\displaystyle \chi _{\lambda }}$ is the character for the irreducible representation of the symmetric group associated to ${\displaystyle \lambda }$, then ${\displaystyle f_{\lambda }(\omega _{n}^{d})=\pm \chi _{\lambda }(c^{d})}$ for every ${\displaystyle 0\leq d<n}$, where ${\displaystyle c}$ is the long cycle ${\displaystyle (12\cdots n)}$.^[7]

If ${\displaystyle Y}$ is the set of semistandard Young tableaux of shape ${\displaystyle \lambda }$ with entries in ${\displaystyle \{1,\dots ,k\}}$, then promotion gives an action of the cyclic group ${\displaystyle C_{k}}$ on ${\displaystyle Y_{\lambda }}$. Define ${\textstyle \kappa (\lambda )=\sum _{i}(i-1)\lambda _{i}}$ and $${\displaystyle g(q)=q^{-\kappa (\lambda )}s_{\lambda }(1,q,\dots ,q^{k-1}),}$$ where ${\displaystyle s_{\lambda }}$ is the Schur polynomial. Then ${\displaystyle (Y,C_{k},g(q))}$ exhibits the cyclic sieving phenomenon.^[8]

---

If ${\displaystyle X}$ is the set of non-crossing (1,2)-configurations of ${\displaystyle \{1,\dots ,n-1\}}$, then ${\displaystyle C_{n-1}}$ acts on these by rotation. Let ${\displaystyle f(q)}$ be the following q-analog of the ${\displaystyle n}$^th Catalan number: $${\displaystyle f(q)={\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q}.}$$ Then ${\displaystyle (X,C_{n-1},f(q))}$ exhibits the cyclic sieving phenomenon.^[9]

---

Let ${\displaystyle X}$ be the set of semi-standard Young tableaux of shape ${\displaystyle (n,n)}$ with maximal entry ${\displaystyle 2n-k}$, where entries along each row and column are strictly increasing. If ${\displaystyle C_{2n-k}}$ acts on ${\displaystyle X}$ by ${\displaystyle K}$-promotion and $${\displaystyle 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 ${\displaystyle (X,C_{2n-k},f(q))}$ exhibits the cyclic sieving phenomenon.^[10]

---

Let ${\displaystyle S_{\lambda ,j}}$ be the set of permutations of cycle type ${\displaystyle \lambda }$ with exactly ${\displaystyle j}$ exceedances. Conjugation gives an action of ${\displaystyle C_{n}}$ on ${\displaystyle S_{\lambda ,j}}$, and if $${\displaystyle a_{\lambda ,j}(q)=\sum _{\sigma \in S_{\lambda ,j}}q^{\operatorname {maj} (\sigma )-j}}$$ then ${\displaystyle (S_{\lambda ,j},C_{n},a_{\lambda ,j}(q))}$ exhibits the cyclic sieving phenomenon.^[11]