Cyclic sieving

For every positive integer $n$, let $\backslash omega\_n$ denote the primitive $n$^th root of unity $e^\{2\backslash 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(\backslash omega\_d)$. If $C\_n$ acts as rotation by $2\backslash pi/n$, this counts elements in $X$ with $d$-fold rotational symmetry.

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

Let $X$ be the 2-element subsets of $\backslash \{1,\; 2,\; 3,\; 4\backslash \}$. Define a bijection $\backslash sigma:X\backslash 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

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

of size two and an orbit

$$\backslash \{1,\; 2\backslash \}\; \backslash mapsto\; \backslash \{2,\; 3\backslash \}\; \backslash mapsto\; \backslash \{3,\; 4\backslash \}\; \backslash mapsto\; \backslash \{1,\; 4\backslash \}\; \backslash mapsto\; \backslash \{1,\; 2\backslash \}$$

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 $\backslash sigma$, $f(-1)=2$ is the number of fixed points of $\backslash sigma^2$, and $f(i)=0$ is the number of fixed points of $\backslash sigma$. Hence, the triple $(X,C\_4,f(q))$ exhibits the cyclic sieving phenomenon.

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

$$\backslash left[\{n\; \backslash atop\; k\}\backslash right]\_q\; =\; \backslash frac\{[n]\_q\backslash cdots\; [2]\_q[1]\_q\}\{[k]\_q\backslash cdots\; [2]\_q[1]\_q[n-k]\_q\backslash 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$,

:

0 & \text{otherwise}.\end{cases}

If $X\_\{n,k\}$ is the set of size-$k$ subsets of $\backslash \{1,\backslash dots,n\backslash \}$ 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\backslash leq\; k\backslash leq\; n$.{{cite journal |first1=V. |last1=Reiner |first2=D. |last2=Stanton |first3=D. |last3=White |title=The cyclic sieving phenomenon |journal=Journal of Combinatorial Theory, Series A |volume=108 |issue=1 |pages=17–50 |year=2004 |doi=10.1016/j.jcta.2004.04.009 |doi-access=free }}

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)$.{{cite book |last1=Sagan |first1=Bruce |title=The cyclic sieving phenomenon: a survey |date=2011 |publisher=Cambridge University Press |pages=183–234 | isbn=978-1-139-50368-6}}

Let $V=\backslash 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(\backslash omega\_n^d)=\backslash chi(c^d)$ for every

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 $\backslash omega\_n^k$. For an integer polynomial $f(q)=\backslash sum\_\{k\backslash geq\; 0\}m\_kq^k$, the triple $(X,C\_n,f(q))$ exhibits the cyclic sieving phenomenon if and only if

$$V\backslash cong\backslash bigoplus\_\{k\backslash geq\; 0\}m\_kV^\{(k)\}.$$

Let $W$ be a finite set of words of the form $w=w\_1\backslash 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 $\{\backslash rm\{maj\}\}(w)$.

If $C\_n$ acts on $W$ by rotating the letters of each word, and

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

then $(W,C\_n,f(q))$ exhibits the cyclic sieving phenomenon.{{cite journal |last1=Berget |first1=Andrew |last2=Eu |first2=Sen-Peng |last3=Reiner |first3=Victor |title=Constructions for Cyclic Sieving Phenomena |journal=SIAM Journal on Discrete Mathematics |date=2011 |volume=25 |issue=3 |page=1297-1314 |doi=10.1137/100803596|arxiv=1004.0747 }}

----

Let $\backslash lambda$ be a partition of size $n$ with rectangular shape, and let $X\_\backslash lambda$ be the set of standard Young tableaux with shape $\backslash 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\_\backslash lambda(q)=\backslash frac\{[n]\_q\backslash cdots\; [1]\_q\}\{\backslash prod\_\{(i,j)\backslash in\; \backslash lambda\}\; [h(i,j)]\_q\}.$$

Then $(X\_\backslash lambda,C\_n,f\_\backslash lambda(q))$ exhibits the cyclic sieving phenomenon. If $\backslash chi\_\backslash lambda$ is the character for the irreducible representation of the symmetric group associated to $\backslash lambda$, then $f\_\backslash lambda(\backslash omega\_n^d)=\backslash pm\backslash chi\_\backslash lambda(c^d)$ for every

If $Y$ is the set of semistandard Young tableaux of shape $\backslash lambda$ with entries in $\backslash \{1,\backslash dots,k\backslash \}$, then promotion gives an action of the cyclic group $C\_k$ on $Y\_\backslash lambda$. Define $\backslash kappa(\backslash lambda)=\backslash sum\_i(i-1)\backslash lambda\_i$ and

$$g(q)=q^\{-\backslash kappa(\backslash lambda)\}s\_\backslash lambda(1,q,\backslash dots,q^\{k-1\}),$$

where $s\_\backslash lambda$ is the Schur polynomial. Then $(Y,C\_k,g(q))$ exhibits the cyclic sieving phenomenon.{{cite journal|last1=Rhoades|first1=Brendon|title=Cyclic sieving, promotion, and representation theory|journal=Journal of Combinatorial Theory, Series A|date=January 2010|volume=117|issue=1|pages=38–76|doi=10.1016/j.jcta.2009.03.017|arxiv=1005.2568|s2cid=6294586}}

----

If $X$ is the set of non-crossing (1,2)-configurations of $\backslash \{1,\backslash dots,n-1\backslash \}$, 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)=\backslash frac\{1\}\{[n+1]\_q\}\backslash left[\{2n\; \backslash atop\; n\}\backslash right]\_q.$$

Then $(X,C\_\{n-1\},f(q))$ exhibits the cyclic sieving phenomenon.{{cite journal|last1=Thiel|first1=Marko|title=A new cyclic sieving phenomenon for Catalan objects|journal=Discrete Mathematics|date=March 2017|volume=340|issue=3|pages=426–9|doi=10.1016/j.disc.2016.09.006|arxiv=1601.03999|s2cid=207137333}}

----

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+\backslash binom\{k\}\{2\}\}\; \backslash frac\{\backslash left[\{n-1\; \backslash atop\; k\}\backslash right]\_q\; \backslash left[\{2n-k\; \backslash atop\; n-k-1\}\backslash right]\_q\}\{\; [n-k]\_q\},$$

then $(X,C\_\{2n-k\},f(q))$ exhibits the cyclic sieving phenomenon.{{cite journal|last1=Pechenik|first1=Oliver|title=Cyclic sieving of increasing tableaux and small Schröder paths|journal=Journal of Combinatorial Theory, Series A|date=July 2014|volume=125|pages=357–378|doi=10.1016/j.jcta.2014.04.002|arxiv=1209.1355|s2cid=18693328}}

----

Let $S\_\{\backslash lambda,j\}$ be the set of permutations of cycle type $\backslash lambda$ with exactly $j$ exceedances. Conjugation gives an action of $C\_n$ on $S\_\{\backslash lambda,j\}$, and if

$$a\_\{\backslash lambda,j\}(q)=\backslash sum\_\{\backslash sigma\; \backslash in\; S\_\{\backslash lambda,j\}\; \}q^\{\backslash operatorname\{maj\}(\backslash sigma)-j\}$$

then $(S\_\{\backslash lambda,j\},\; C\_n,\; a\_\{\backslash lambda,j\}(q))$ exhibits the cyclic sieving phenomenon.{{cite journal|last1=Sagan|first1=Bruce|last2=Shareshian|first2=John|last3=Wachs|first3=Michelle L.|title=Eulerian quasisymmetric functions and cyclic sieving|journal=Advances in Applied Mathematics|date=January 2011|volume=46|issue=1–4|pages=536–562|doi=10.1016/j.aam.2010.01.013|arxiv=0909.3143|s2cid=379574}}

{{reflist}}

Category:Combinatorics

Category:Generating functions