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 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=\mathrm{i}\mathrm{d}$, where $\mathrm{i}\mathrm{d}$ 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[\genfrac{}{}{0ex}{}{n}{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[\genfrac{}{}{0ex}{}{n}{k}\right]}_{{\omega }_d}=\{\begin{array}{cc}\left(\genfrac{}{}{0ex}{}{n/d}{k/d}\right)& \text{if }d\mid k,\\ 0& \text{otherwise}.\end{array}$

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\le k\le 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=ℂ(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\le 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)=\sum _{k\ge 0}{m}_k{q}^k$, the triple $(X,C_n,f(q))$ exhibits the cyclic sieving phenomenon if and only if $$V\cong \underset{k\ge 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 $\mathrm{m}\mathrm{a}\mathrm{j}(w)$.

If $C_n$ acts on $W$ by rotating the letters of each word, and $$f(q)=\sum _{w\in W}{q}^{\mathrm{m}\mathrm{a}\mathrm{j}(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\le 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 $\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[\genfrac{}{}{0ex}{}{2n}{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+(\genfrac{}{}{0ex}{}{k}{2})}\frac{{\left[\genfrac{}{}{0ex}{}{n-1}{k}\right]}_q{\left[\genfrac{}{}{0ex}{}{2n-k}{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}^{\mathrm{maj}(\sigma )-j}$$ then $(S_{\lambda ,j},C_n,a_{\lambda ,j}(q))$ exhibits the cyclic sieving phenomenon.