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

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.

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