Cyclic Sieving Phenomenon

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^$.

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$, where $\rm$ 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 $\$. 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
$\\mapsto\\mapsto\$
of size two and an orbit
$\ \mapsto \ \mapsto \ \mapsto \ \mapsto \$
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 q:=1+q+\cdots+q^ and define the ''q''-binomial coefficient by
$\left$rightq = \frac.
which is an integer polynomial evaluating to the usual binomial coefficient at $q=1$. For any positive integer $d$ dividing $n$,
:$\left$right = \begin\left(\right)&\textd\mid k,\\
0 & \text.\end

If $X_$ is the set of size-$k$ subsets of $\$ with $C_n$ acting by increasing each element in the subset by one (and sending $n$ back to $1$), and if $f_(q)$ is the ''q''-binomial coefficient above, then $(X_,C_n,f_(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(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 /math>, and the trace of 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, where $\chi$ is the character of $V$.

This gives a method for determining $f(q)$. For every integer $k$, let $V^$ 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_m_kq^k$, the triple $(X,C_n,f(q))$ exhibits the cyclic sieving phenomenon if and only if
$V\cong\bigoplus_m_kV^.$

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_$, and is denoted $(w)$.

If $C_n$ acts on $W$ by rotating the letters of each word, and
$f(q)=\sum_q^$
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.$
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, where $c$ is the long cycle $(12\cdots n)$.

If $Y$ is the set of semistandard Young tableaux of shape $\lambda$ with entries in $\$, 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^s_\lambda(1,q,\dots,q^),$
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 $\$, then $C_$ acts on these by rotation. Let $f(q)$ be the following ''q''-analog of the $n$^th Catalan number:
$f(q)=\frac\left$rightq.
Then $(X,C_,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_$ acts on $X$ by $K$-promotion and
$f(q)=q^ \frac,$
then $(X,C_,f(q))$ exhibits the cyclic sieving phenomenon.

----

Let $S_$ be the set of permutations of cycle type $\lambda$ with exactly $j$ exceedances. Conjugation gives an action of $C_n$ on $S_$, and if
$a_(q)=\sum_q^$
then $(S_, C_n, a_(q))$ exhibits the cyclic sieving phenomenon.

Notes and references

{{reflist

Combinatorics
Generating functions