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.[1]

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[{n \atop k}\right]_{q}

is the polynomial in q defined by

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

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

\{1,3\}\to \{2,4\}\to \{1,3\}

(of size 2)

and

\{1,2\}\to \{2,3\}\to \{3,4\}\to \{1,4\}\to \{1,2\}

(of size 4).

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

\left[{4 \atop 2}\right]_{q}=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 {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 $w_{j}>w_{j+1}$ . Define the major index $\operatorname {maj} (w)$ on words as the sum of all descents.

The triple $(X_{n},C_{n-1},{\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q})$ exhibit a cyclic sieving phenomenon, where $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 $(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 $(X,C,q^{-\kappa (\lambda )}s_{\lambda }(1,q,q^{2},\dotsc ,q^{k-1}))$ exhibit the cyclic sieving phenomenon. Here, $\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 $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 {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 $C_{2n-k}$ act via K-promotion.[5]

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

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

Notes and references

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
V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, Journal of Combinatorial Theory, Series A, Volume 108 Issue 1, October 2004, Pages 17–50
Thiel, Marko (March 2017). "A new cyclic sieving phenomenon for Catalan objects". Discrete Mathematics. 340 (3): 426–429. arXiv:1601.03999. doi:10.1016/j.disc.2016.09.006.
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.
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.
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.

Sagan, Bruce. The cyclic sieving phenomenon: a survey. Surveys in combinatorics 2011, 183–233, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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] V. Reiner, D. Stanton and D. White, The cyclic sieving phenomenon, Journal of Combinatorial Theory, Series A, Volume 108 Issue 1, October 2004, Pages 17–50

[3] Thiel, Marko (March 2017). "A new cyclic sieving phenomenon for Catalan objects". Discrete Mathematics. 340 (3): 426–429. arXiv:1601.03999. doi:10.1016/j.disc.2016.09.006.

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

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

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