Cyclic sieving

In combinatorial mathematics, cyclic sieving is a phenomenon in which an integer polynomial evaluated at roots of unity counts the symmetries of the action of a cyclic group on a finite set. ^[1] Given a family of such phenomena, the polynomials give a q-analogue for the enumeration of the sets, often arising from an underlying algebraic structure such as a representation.

Definition

Let C_n be the cyclic group of order n acting on a finite set X, and suppose f(q) is a polynomial with integer polynomial coefficients. The triple (X, C_n, f(q)) exhibits the cyclic sieving phenomenon (or CSP) if for all positive integers d dividing n, the number of elements in X fixed by the subgroup C_d of C_n is equal to f(e^2πi/d). If C_n acts by rotation on the set X, then this counts elements with d-fold rotational symmetry.

Equivalently, if c is an element of order n in C_n, then f(e^2πid/n) counts the number of elements in X fixed by c^d for every integer d.

Example

Let X be the set of size-2 subsets of {1, 2, 3, 4}. The cyclic group C₄ acts on X by increasing each element by in the subset by one (where 4 is sent back to 1). This action splits X into an orbit

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

of size two and an orbit

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

of size four. If f(q) = 1 + q + 2q² + q³ + q⁴, then f(1) = 5 is the number of elements in X, f(-1) = 2 counts elements fixed by two iterations of the action, and f(i) = 0 counts elements fixed by one iteration. Hence, the triple (X, C₄, f(q)) satisfies the cyclic sieving phenomenon.

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

${\displaystyle \left[{n \atop k}\right]_{q}={\frac {[n]_{q}\cdots [2]_{q}[1]_{q}}{[k]_{q}\cdots [2]_{q}[1]_{q}[n-k]_{q}\cdots [1]_{q}}}.}$

which is an integer polynomial which evaluates to the usual binomial coefficient at q = 1. In fact, for any positive integer d dividing n,

${\displaystyle \left[{n \atop k}\right]_{e^{2\pi i/d}}={\begin{cases}\left({n/d \atop k/d}\right)&{\text{if }}d\mid k,\\0&{\text{otherwise}}.\end{cases}}}$

If X_n,k is the set of size-k subsets of {1, 2, ..., n} 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)) satisfies the cyclic sieving phenomenon for every 0 ≤ k ≤ n. ^[2]

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

---

The triple ${\displaystyle (X_{n},C_{n-1},{\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q})}$ exhibit a cyclic sieving phenomenon, where ${\displaystyle X_{n}}$ 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 ${\displaystyle (X,C,{\frac {[n]!_{q}}{\prod _{(i,j)\in \lambda }[h_{ij}]_{q}}})}$ 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 ${\displaystyle (X,C,q^{-\kappa (\lambda )}s_{\lambda }(1,q,q^{2},\dotsc ,q^{k-1}))}$ exhibit the cyclic sieving phenomenon. Here, ${\displaystyle \kappa (\lambda )=\sum _{i}(i-1)\lambda _{i}}$ 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 ${\displaystyle 1,2,\dotsc ,\ell }$ for some ${\displaystyle \ell }$. Let ${\displaystyle Inc_{k}(2\times n)}$ denote the set of increasing tableau with two rows of length n, and maximal entry ${\displaystyle 2n-k}$. Then ${\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}}})}$ exhibit the cyclic sieving phenomenon, where ${\displaystyle C_{2n-k}}$ act via K-promotion. ^[5]

---

Let ${\displaystyle S_{\lambda ,j}}$ be the set of permutations of cycle type λ and exactly j exceedances. Let ${\displaystyle a_{\lambda ,j}(q)=\sum _{\sigma \in S_{\lambda ,j}}q^{\operatorname {maj} (\sigma )-\operatorname {exc} (\sigma )}}$, and let ${\displaystyle C_{n}}$ act on ${\displaystyle S_{\lambda ,j}}$ by conjugation.

Then ${\displaystyle (S_{\lambda ,j},C_{n},a_{\lambda ,j}(q))}$ exhibit the cyclic sieving phenomenon. ^[6]

In representation theory

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). ^[7]

Let V = C[X] be the vector space over the complex numbers C 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.

If c generates 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)) satisfies the cyclic sieving phenomenon if and only if f(e^2πid/n) = χ(c^d) for every integer d, where χ is the character of V.

This gives a method for determining the polynomial f(q). For every integer k, let V^(k) be the one-dimensional representation of C_n in which the generator c acts as scalar multiplication by e^2πik/n. For an integer polynomial

${\displaystyle f(q)=\sum _{i\geq 0}m_{i}q^{i},}$

the triple (X, C_n, f(q)) satisfies the cyclic sieving phenomenon if and only if

${\displaystyle V\cong \bigoplus _{i\geq 0}m_{i}V^{(i)}.}$

Notes and references

1. Reiner, Victor; Stanton, Dennis; White, Dennis (February 2014). "What is... Cyclic Sieving?" (PDF). Notices of the American Mathematical Society . 61 (2): 169–171. doi:10.1090/noti1084.
2. Reiner, V.; Stanton, D.; White, D. (2004). "The cyclic sieving phenomenon". Journal of Combinatorial Theory, Series A. 108 (1): 17–50. doi: 10.1016/j.jcta.2004.04.009 .
3. Thiel, Marko (March 2017). "A new cyclic sieving phenomenon for Catalan objects". Discrete Mathematics. 340 (3): 426–9. arXiv: 1601.03999 . doi:10.1016/j.disc.2016.09.006. S2CID   207137333.
4. Rhoades, Brendon (January 2010). "Cyclic sieving, promotion, and representation theory". Journal of Combinatorial Theory, Series A. 117 (1): 38–76. arXiv: 1005.2568 . doi:10.1016/j.jcta.2009.03.017. S2CID   6294586.
5. Pechenik, Oliver (July 2014). "Cyclic sieving of increasing tableaux and small Schröder paths". Journal of Combinatorial Theory, Series A. 125: 357–378. arXiv: 1209.1355 . doi:10.1016/j.jcta.2014.04.002. S2CID   18693328.
6. Sagan, Bruce; Shareshian, John; Wachs, Michelle L. (January 2011). "Eulerian quasisymmetric functions and cyclic sieving". Advances in Applied Mathematics. 46 (1–4): 536–562. arXiv: 0909.3143 . doi:10.1016/j.aam.2010.01.013. S2CID   379574.
7. Sagan, Bruce (2011). The cyclic sieving phenomenon: a survey. Cambridge University Press. pp. 183–234.

• Sagan, Bruce (2011). "The cyclic sieving phenomenon: a survey". In Chapman, Robin (ed.). Surveys in Combinatorics 2011. London Mathematical Society Lecture Note Series. Vol. 392. Cambridge University Press. pp. 183–233. ISBN   978-1-139-50368-6.