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

[math]\displaystyle{ \left[{n \atop k}\right]_q }[/math]

is the polynomial in q defined by

[math]\displaystyle{ \left[{n \atop k}\right]_q = \frac{\prod_{i = 1}^n (1 + q + q^2 + \cdots + q^{i - 1})}{\left(\prod_{i = 1}^k (1 + q + q^2 + \cdots + q^{i - 1})\right) \cdot \left(\prod_{i = 1}^{n - k} (1 + q + q^2 + \cdots + q^{i - 1})\right)}. }[/math]

It is easily seen that its value at q = 1 is the usual binomial coefficient [math]\displaystyle{ \binom{n}{k} }[/math], 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

[math]\displaystyle{ \{1, 3\} \to \{2, 4\} \to \{1, 3\} }[/math] (of size 2)

and

[math]\displaystyle{ \{1, 2\} \to \{2, 3\} \to \{3, 4\} \to \{1, 4\} \to \{1, 2\} }[/math] (of size 4).

One can show 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

[math]\displaystyle{ \left[{4 \atop 2}\right]_q = 1 + q + 2q^2 + q^3 + q^4; }[/math]

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).

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 [math]\displaystyle{ w_j\gt w_{j+1} }[/math]. Define the major index [math]\displaystyle{ \operatorname{maj}(w) }[/math] on words as the sum of all descents.

---

The triple [math]\displaystyle{ (X_n,C_{n-1},\frac{1}{[n+1]_q}\left[{2n \atop n}\right]_q) }[/math] exhibit a cyclic sieving phenomenon, where [math]\displaystyle{ X_n }[/math] 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 [math]\displaystyle{ (X,C,\frac{[n]!_q}{\prod_{(i,j)\in \lambda} [h_{ij}]_q}) }[/math] 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 [math]\displaystyle{ (X,C, q^{-\kappa(\lambda)}s_\lambda(1,q,q^2,\dotsc,q^{k-1} )) }[/math] exhibit the cyclic sieving phenomenon. Here, [math]\displaystyle{ \kappa(\lambda)=\sum_i (i-1)\lambda_i }[/math] 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 [math]\displaystyle{ 1,2,\dotsc,\ell }[/math] for some [math]\displaystyle{ \ell }[/math]. Let [math]\displaystyle{ Inc_k(2\times n) }[/math] denote the set of increasing tableau with two rows of length n, and maximal entry [math]\displaystyle{ 2n-k }[/math]. Then [math]\displaystyle{ (\operatorname{Inc}_k(2\times n),C_{2n-k}, q^{n+\binom{k}{2}} \frac{\left[{n-1 \atop k}\right]_q \left[{2n-k \atop n-k-1}\right]_q}{ [n-k]_q }) }[/math] exhibit the cyclic sieving phenomenon, where [math]\displaystyle{ C_{2n-k} }[/math] act via K-promotion.

---

Let [math]\displaystyle{ S_{\lambda,j} }[/math] be the set of permutations of cycle type λ and exactly j exceedances. Let [math]\displaystyle{ a_{\lambda,j}(q) = \sum_{\sigma \in S_{\lambda,j} }q^{\operatorname{maj}(\sigma)-\operatorname{exc}(\sigma)} }[/math], and let [math]\displaystyle{ C_n }[/math] act on [math]\displaystyle{ S_{\lambda,j} }[/math] by conjugation.

Then [math]\displaystyle{ (S_{\lambda,j}, C_n, a_{\lambda,j}(q)) }[/math] exhibit the cyclic sieving phenomenon.

Notes and references

• Sagan, Bruce (2011). "The cyclic sieving phenomenon: a survey". in Chapman, Robin. Surveys in Combinatorics 2011. London Mathematical Society Lecture Note Series. 392. Cambridge University Press. pp. 183–233. ISBN 978-1-139-50368-6. https://books.google.com/books?id=98-l4J34SFYC&pg=PA183.