Cyclic sieving

In combinatorial mathematics, cyclic sieving is a phenomenon by which evaluating a generating function for a finite set at roots of unity counts symmetry classes of objects acted on by a cyclic group.

Definition

Let ''C'' be a cyclic group generated by an element ''c'' of order ''n''. Suppose ''C'' acts on a set ''X''. Let ''X''(''q'') be a polynomial with integer coefficients. Then the triple (''X'', ''X''(''q''), ''C'') is said to exhibit the cyclic sieving phenomenon (CSP) if for all integers ''d'', the value ''X''(''e''^{2''id''/''n''}) is the number of elements fixed by ''c''^''d''. In particular ''X''(1) is the cardinality of the set ''X'', and for that reason ''X''(''q'') is regarded as a generating function for ''X''.

Examples

The ''q''-binomial coefficient

:$\left$rightq

is the polynomial in ''q'' defined by

:$\left$rightq = \frac.

It is easily seen that its value at ''q'' = 1 is the usual binomial coefficient $\binom$, so it is a generating function for the subsets of of size ''k''. These subsets carry a natural action of the cyclic group ''C'' of order ''n'' which acts by adding 1 to each element of the set, modulo ''n''. For example, when ''n'' = 4 and ''k'' = 2, the group orbits are

: $\ \to \ \to \$ (of size 2)

and

: $\ \to \ \to \ \to \ \to \$ (of size 4).

One can show that evaluating the ''q''-binomial coefficient when ''q'' is an ''n''th root of unity gives the number of subsets fixed by the corresponding group element.

In the example ''n'' = 4 and ''k'' = 2, the ''q''-binomial coefficient is

: $\left$rightq = 1 + q + 2q^2 + q^3 + q^4;

evaluating this polynomial at ''q'' = 1 gives 6 (as all six subsets are fixed by the identity element of the group); evaluating it at ''q'' = −1 gives 2 (the subsets and are fixed by two applications of the group generator); and evaluating it at ''q'' = ±''i'' gives 0 (no subsets are fixed by one or three applications of the group generator).

List of cyclic sieving phenomena

In the Reiner–Stanton–White paper, the following example is given:

Let α be a composition of ''n'', and let ''W''(''α'') be the set of all words of length ''n'' with α_i
letters equal to ''i''. A ''descent'' of a word ''w'' is any index ''j'' such that $w_j>w_$.
Define the major index $\operatorname(w)$ on words as the sum of all descents.

----

The triple $(X_n,C_,\frac\left$rightq) exhibit a cyclic sieving phenomenon, where $X_n$ is the set of non-crossing (1,2)-configurations of 'n'' − 1

----

Let ''λ'' be a rectangular partition of size ''n'', and let ''X'' be the set of standard Young tableaux
of shape ''λ''. Let ''C'' = ''Z''/''nZ'' act on ''X'' via promotion. Then $(X,C,\frac)$ exhibit the cyclic sieving phenomenon. Note that the polynomial is a ''q''-analogue of the hook length formula.

Furthermore, let ''λ'' be a rectangular partition of size ''n'', and let ''X'' be the set of semi-standard Young tableaux of shape ''λ''. Let ''C'' = ''Z''/''kZ'' act on ''X'' via ''k''-promotion.
Then $(X,C, q^s_\lambda(1,q,q^2,\dotsc,q^ ))$
exhibit the cyclic sieving phenomenon. Here, $\kappa(\lambda)=\sum_i (i-1)\lambda_i$
and ''s''_λ is the Schur polynomial.

----

An increasing tableau is a semi-standard Young tableau, where both rows and columns are strictly increasing,
and the set of entries is of the form $1,2,\dotsc,\ell$ for some $\ell$.
Let $Inc_k(2\times n)$ denote the set of increasing tableau with two rows of length ''n'',
and maximal entry $2n-k$. Then
$(\operatorname_k(2\times n),C_, q^ \frac)$
exhibit the cyclic sieving phenomenon, where $C_$ act via ''K''-promotion.

----

Let $S_$ be the set of permutations of cycle type ''λ'' and exactly ''j'' excedances.
Let $a_(q) = \sum_q^$,
and let $C_n$ act on $S_$ by conjugation.

Then $(S_, C_n, a_(q))$ exhibit the cyclic sieving phenomenon.

Notes and references

*
{{refend

Combinatorics
Generating functions