Cyclic sieving

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

The first study of cyclic sieving was published by Reiner, Stanton and White in 2004.^[2] The phenomenon generalizes the "q = −1 phenomenon" of John Stembridge, which considers evaluations of the polynomial only at the first and second roots of unity (that is, q = 1 and q = −1).^[3]

Definition

For every positive integer $n$ , let $\omega _{n}$ denote the primitive $n$ ^th root of unity $e^{2\pi i/n}$ .

Let $X$ be a finite set with an action of the cyclic group $C_{n}$ , and let $f(q)$ be an integer polynomial. The triple $(X,C_{n},f(q))$ exhibits the cyclic sieving phenomenon (or CSP) if for every positive integer $d$ dividing $n$ , the number of elements in $X$ fixed by the action of the subgroup $C_{d}$ of $C_{n}$ is equal to $f(\omega _{d})$ . If $C_{n}$ acts as rotation by $2\pi /n$ , this counts elements in $X$ with $d$ -fold rotational symmetry.

Equivalently, suppose $\sigma :X\to X$ is a bijection on $X$ such that $\sigma ^{n}={\rm {id}}$ , where ${\rm {id}}$ is the identity map. Then $\sigma$ induces an action of $C_{n}$ on $X$ , where a given generator $c$ of $C_{n}$ acts by $\sigma$ . Then $(X,C_{n},f(q))$ exhibits the cyclic sieving phenomenon if the number of elements in $X$ fixed by $\sigma ^{d}$ is equal to $f(\omega _{n}^{d})$ for every integer $d$ .

Example

Let $X$ be the 2-element subsets of $\{1,2,3,4\}$ . Define a bijection $\sigma :X\to X$ which increases each element in the pair by one (and sends $4$ back to $1$ ). This induces an action of $C_{4}$ on $X$ , which has an orbit $\{1,3\}\mapsto \{2,4\}\mapsto \{1,3\}$ of size two and an orbit $\{1,2\}\mapsto \{2,3\}\mapsto \{3,4\}\mapsto \{1,4\}\mapsto \{1,2\}$ of size four. If $f(q)=1+q+2q^{2}+q^{3}+q^{4}$ , then $f(1)=6$ is the number of elements in $X$ , $f(i)=0$ counts fixed points of $\sigma$ , $f(-1)=2$ is the number of fixed points of $\sigma ^{2}$ , and $f(i)=0$ is the number of fixed points of $\sigma$ . Hence, the triple $(X,C_{4},f(q))$ exhibits the cyclic sieving phenomenon.

More generally, set $[n]_{q}:=1+q+\cdots +q^{n-1}$ and define the q-binomial coefficient by $\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 [2]_{q}[1]_{q}}}.$ which is an integer polynomial evaluating to the usual binomial coefficient at $q=1$ . For any positive integer $d$ dividing $n$ ,

\left[{n \atop k}\right]_{\omega _{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,\dots ,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))$ exhibits the cyclic sieving phenomenon for every $0\leq k\leq n$ .^[4]

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

Let $V=\mathbb {C} (X)$ be the vector space over the complex numbers 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}$ .

For a generator $c$ of $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))$ exhibits the cyclic sieving phenomenon if and only if $f(\omega _{n}^{d})=\chi (c^{d})$ for every $0\leq d<n$ , where $\chi$ is the character of $V$ .

This gives a method for determining $f(q)$ . For every integer $k$ , let $V^{(k)}$ be the one-dimensional representation of $C_{n}$ in which $c$ acts as scalar multiplication by $\omega _{n}^{k}$ . For an integer polynomial ${\textstyle f(q)=\sum _{k\geq 0}m_{k}q^{k}}$ , the triple $(X,C_{n},f(q))$ exhibits the cyclic sieving phenomenon if and only if $V\cong \bigoplus _{k\geq 0}m_{k}V^{(k)}.$

Further examples

Let $W$ be a finite set of words of the form $w=w_{1}\cdots w_{n}$ where each letter $w_{j}$ is an integer and $W$ is closed under permutation (that is, if $w$ is in $W$ , then so is any anagram of $w$ ). The major index of a word $w$ is the sum of all indices $j$ such that $w_{j}>w_{j+1}$ , and is denoted ${\rm {maj}}(w)$ .

If $C_{n}$ acts on $W$ by rotating the letters of each word, and $f(q)=\sum _{w\in W}q^{{\rm {maj}}(w)}$ then $(W,C_{n},f(q))$ exhibits the cyclic sieving phenomenon.^[6]

Let $\lambda$ be a partition of size $n$ with rectangular shape, and let $X_{\lambda }$ be the set of standard Young tableaux with shape $\lambda$ . Jeu de taquin promotion gives an action of $C_{n}$ on $X$ . Let $f(q)$ be the following q-analog of the hook length formula: $f_{\lambda }(q)={\frac {[n]_{q}\cdots [1]_{q}}{\prod _{(i,j)\in \lambda }[h(i,j)]_{q}}}.$ Then $(X_{\lambda },C_{n},f_{\lambda }(q))$ exhibits the cyclic sieving phenomenon. If $\chi _{\lambda }$ is the character for the irreducible representation of the symmetric group associated to $\lambda$ , then $f_{\lambda }(\omega _{n}^{d})=\pm \chi _{\lambda }(c^{d})$ for every $0\leq d<n$ , where $c$ is the long cycle $(12\cdots n)$ .^[7]

If $Y$ is the set of semistandard Young tableaux of shape $\lambda$ with entries in $\{1,\dots ,k\}$ , then promotion gives an action of the cyclic group $C_{k}$ on $Y_{\lambda }$ . Define ${\textstyle \kappa (\lambda )=\sum _{i}(i-1)\lambda _{i}}$ and $g(q)=q^{-\kappa (\lambda )}s_{\lambda }(1,q,\dots ,q^{k-1}),$ where $s_{\lambda }$ is the Schur polynomial. Then $(Y,C_{k},g(q))$ exhibits the cyclic sieving phenomenon.^[8]

If $X$ is the set of non-crossing (1,2)-configurations of $\{1,\dots ,n-1\}$ , then $C_{n-1}$ acts on these by rotation. Let $f(q)$ be the following q-analog of the $n$ ^th Catalan number: $f(q)={\frac {1}{[n+1]_{q}}}\left[{2n \atop n}\right]_{q}.$ Then $(X,C_{n-1},f(q))$ exhibits the cyclic sieving phenomenon.^[9]

Let $X$ be the set of semi-standard Young tableaux of shape $(n,n)$ with maximal entry $2n-k$ , where entries along each row and column are strictly increasing. If $C_{2n-k}$ acts on $X$ by $K$ -promotion and $f(q)=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}}},$ then $(X,C_{2n-k},f(q))$ exhibits the cyclic sieving phenomenon.^[10]

Let $S_{\lambda ,j}$ be the set of permutations of cycle type $\lambda$ with exactly $j$ exceedances. Conjugation gives an action of $C_{n}$ on $S_{\lambda ,j}$ , and if $a_{\lambda ,j}(q)=\sum _{\sigma \in S_{\lambda ,j}}q^{\operatorname {maj} (\sigma )-j}$ then $(S_{\lambda ,j},C_{n},a_{\lambda ,j}(q))$ exhibits the cyclic sieving phenomenon.^[11]

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.
^ Stembridge, John (1994). "Some hidden relations involving the ten symmetry classes of plane partitions". Journal of Combinatorial Theory, Series A. 68 (2): 372-409. doi:10.1016/0097-3165(94)90112-0. hdl:2027.42/31216.
^ 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.
^ Sagan, Bruce (2011). The cyclic sieving phenomenon: a survey. Cambridge University Press. pp. 183–234. ISBN 978-1-139-50368-6.
^ Berget, Andrew; Eu, Sen-Peng; Reiner, Victor (2011). "Constructions for Cyclic Sieving Phenomena". SIAM Journal on Discrete Mathematics. 25 (3): 1297-1314. arXiv:1004.0747. doi:10.1137/100803596.
^ Madonald, Ian (1995). Symmetric Functions and Hall Polynomials. Oxford: Oxford University Press. ISBN 9780198534891.
^ 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.
^ 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.
^ 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.

[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] Stembridge, John (1994). "Some hidden relations involving the ten symmetry classes of plane partitions". Journal of Combinatorial Theory, Series A. 68 (2): 372-409. doi:10.1016/0097-3165(94)90112-0. hdl:2027.42/31216.

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

[5] Sagan, Bruce (2011). The cyclic sieving phenomenon: a survey. Cambridge University Press. pp. 183–234. ISBN 978-1-139-50368-6.

[6] Berget, Andrew; Eu, Sen-Peng; Reiner, Victor (2011). "Constructions for Cyclic Sieving Phenomena". SIAM Journal on Discrete Mathematics. 25 (3): 1297-1314. arXiv:1004.0747. doi:10.1137/100803596.

[7] Madonald, Ian (1995). Symmetric Functions and Hall Polynomials. Oxford: Oxford University Press. ISBN 9780198534891.

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Fahrer / Team für die Suche eingeben: