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

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

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 - version of the 8/18/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.