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).
For every positive integer , let denote the primitive <sup>th</sup> root of unity .
Let be a finite set with an action of the cyclic group , and let be an integer polynomial. The triple exhibits the cyclic sieving phenomenon (or CSP) if for every positive integer dividing , the number of elements in fixed by the action of the subgroup of is equal to . If acts as rotation by , this counts elements in with -fold rotational symmetry.
Equivalently, suppose is a bijection on such that , where is the identity map. Then induces an action of on , where a given generator of acts by . Then exhibits the cyclic sieving phenomenon if the number of elements in fixed by is equal to for every integer .
Let be the 2-element subsets of . Define a bijection which increases each element in the pair by one (and sends back to ). This induces an action of on , which has an orbit
of size two and an orbit
of size four. If , then is the number of elements in , counts fixed points of , is the number of fixed points of , and is the number of fixed points of . Hence, the triple exhibits the cyclic sieving phenomenon.
More generally, set and define the q-binomial coefficient by
which is an integer polynomial evaluating to the usual binomial coefficient at . For any positive integer dividing ,
If is the set of size- subsets of with acting by increasing each element in the subset by one (and sending back to ), and if is the q-binomial coefficient above, then exhibits the cyclic sieving phenomenon for every .
The cyclic sieving phenomenon can be naturally stated in the language of representation theory. The group action of on is linearly extended to obtain a representation, and the decomposition of this representation into irreducibles determines the required coefficients of the polynomial .
Let be the vector space over the complex numbers with a basis indexed by a finite set . If the cyclic group acts on , then linearly extending each action turns into a representation of .
For a generator of , its action on is given by a permutation matrix , and the trace of counts the elements of fixed by . In particular, the triple exhibits the cyclic sieving phenomenon if and only if for every , where is the character of .
This gives a method for determining . For every integer , let be the one-dimensional representation of in which acts as scalar multiplication by . For an integer polynomial , the triple exhibits the cyclic sieving phenomenon if and only if
Let be a finite set of words of the form where each letter is an integer and is closed under permutation (that is, if is in , then so is any anagram of ). The major index of a word is the sum of all indices such that , and is denoted .
If acts on by rotating the letters of each word, and
then exhibits the cyclic sieving phenomenon.
Let be a partition of size with rectangular shape, and let be the set of standard Young tableaux with shape . Jeu de taquin promotion gives an action of on . Let be the following q-analog of the hook length formula:
Then exhibits the cyclic sieving phenomenon. If is the character for the irreducible representation of the symmetric group associated to , then for every , where is the long cycle .
If is the set of semistandard Young tableaux of shape with entries in , then promotion gives an action of the cyclic group on . Define and
where is the Schur polynomial. Then exhibits the cyclic sieving phenomenon.
If is the set of non-crossing (1,2)-configurations of , then acts on these by rotation. Let be the following q-analog of the <sup>th</sup> Catalan number:
Then exhibits the cyclic sieving phenomenon.
Let be the set of semi-standard Young tableaux of shape with maximal entry , where entries along each row and column are strictly increasing. If acts on by -promotion and
then exhibits the cyclic sieving phenomenon.
Let be the set of permutations of cycle type with exactly exceedances. Conjugation gives an action of on , and if
then exhibits the cyclic sieving phenomenon.