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.[1]
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(e2πid/n) is the number of elements fixed by cd. 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.
is the polynomial in q defined by
It is easily seen that its value at q = 1 is the usual binomial coefficient , so it is a generating function for the subsets of {1, 2, ..., n} 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
and
One can show[2] that evaluating the q-binomial coefficient when q is an nth 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
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 {1, 3} and {2, 4} 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).
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 . Define the major index on words as the sum of all descents.
The triple exhibit a cyclic sieving phenomenon, where is the set of non-crossing (1,2)-configurations of [n − 1].[3]
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 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 exhibit the cyclic sieving phenomenon. Here, and sλ is the Schur polynomial.[4]
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 for some . Let denote the set of increasing tableau with two rows of length n, and maximal entry . Then exhibit the cyclic sieving phenomenon, where act via K-promotion.[5]
Let be the set of permutations of cycle type λ and exactly j exceedances. Let , and let act on by conjugation.
Then exhibit the cyclic sieving phenomenon.[6]