Cyclic sieving

Uses your system voice; voice and rate in settings.

Snapshot

≈ 7 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

exhibits cyclic sieving, with evaluations at roots of unity counting the number of rectangular standard Young tableaux fixed by repeated applications of jeu de taquin promotion. 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. 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 20041. 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).

exhibits cyclic sieving, with evaluations at roots of unity counting the number of rectangular standard Young tableaux fixed by repeated applications of jeu de taquin promotion. 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. 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. 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). 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^3 . 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 .

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 , its action on \mathbb{C}(X) is given by 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 , 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 f(q)=\sum_{k\geq 0}m_kq^k , the triple (X,C_n,f(q)) exhibits the cyclic sieving phenomenon if and only if V\cong\bigoplus_{k\geq 0}m_kV^{(k)}.

Further examples

Words

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. 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 , where c is the long cycle (12\cdots n) . 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 \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. 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. 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. 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374935510 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Cyclic sieving” revision 1374935510 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL

Provenance

snapshot enwiki-001374935510 · captured 1789419665.0 · version history

Cite this page as: encyclopegia.org, “Cyclic sieving”, snapshot enwiki-001374935510. https://encyclopegia.org/a/cyclic-sieving