Top Qs
Timeline
Chat
Perspective
Cyclic sieving
From Wikipedia, the free encyclopedia
Remove ads
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]
Remove ads
Definition
For every positive integer , let denote the primitive th root of unity .
Let be a finite set with an action of the cyclic group , and let be an integer polynomial. The triple exhibits the cyclic sieving phenomenon (or CSP) if for every positive integer dividing , the number of elements in fixed by the action of the subgroup of is equal to . If acts as rotation by , this counts elements in with -fold rotational symmetry.
Equivalently, suppose is a bijection on such that , where is the identity map. Then induces an action of on , where a given generator of acts by . Then exhibits the cyclic sieving phenomenon if the number of elements in fixed by is equal to for every integer .
Remove ads
Example
Let be the 2-element subsets of . Define a bijection which increases each element in the pair by one (and sends back to ). This induces an action of on , which has an orbit of size two and an orbit of size four. If , then is the number of elements in , counts fixed points of , is the number of fixed points of , and is the number of fixed points of . Hence, the triple exhibits the cyclic sieving phenomenon.
More generally, set and define the q-binomial coefficient by which is an integer polynomial evaluating to the usual binomial coefficient at . For any positive integer dividing ,
If is the set of size- subsets of with acting by increasing each element in the subset by one (and sending back to ), and if is the q-binomial coefficient above, then exhibits the cyclic sieving phenomenon for every .[4]
Remove ads
In representation theory
The cyclic sieving phenomenon can be naturally stated in the language of representation theory. The group action of on is linearly extended to obtain a representation, and the decomposition of this representation into irreducibles determines the required coefficients of the polynomial .[5]
Let be the vector space over the complex numbers with a basis indexed by a finite set . If the cyclic group acts on , then linearly extending each action turns into a representation of .
For a generator of , the linear extension of its action on gives a permutation matrix , and the trace of counts the elements of fixed by . In particular, the triple exhibits the cyclic sieving phenomenon if and only if for every , where is the character of .
This gives a method for determining . For every integer , let be the one-dimensional representation of in which acts as scalar multiplication by . For an integer polynomial , the triple exhibits the cyclic sieving phenomenon if and only if
Remove ads
Further examples
Let be a finite set of words of the form where each letter is an integer and is closed under permutation (that is, if is in , then so is any anagram of ). The major index of a word is the sum of all indices such that , and is denoted .
If acts on by rotating the letters of each word, and then exhibits the cyclic sieving phenomenon.[6]
Let be a partition of size with rectangular shape, and let be the set of standard Young tableaux with shape . Jeu de taquin promotion gives an action of on . Let be the following q-analog of the hook length formula: Then exhibits the cyclic sieving phenomenon. If is the character for the irreducible representation of the symmetric group associated to , then for every , where is the long cycle .[7]
If is the set of semistandard Young tableaux of shape with entries in , then promotion gives an action of the cyclic group on . Define and where is the Schur polynomial. Then exhibits the cyclic sieving phenomenon.[8]
If is the set of non-crossing (1,2)-configurations of , then acts on these by rotation. Let be the following q-analog of the th Catalan number: Then exhibits the cyclic sieving phenomenon.[9]
Let be the set of semi-standard Young tableaux of shape with maximal entry , where entries along each row and column are strictly increasing. If acts on by -promotion and then exhibits the cyclic sieving phenomenon.[10]
Let be the set of permutations of cycle type with exactly exceedances. Conjugation gives an action of on , and if then exhibits the cyclic sieving phenomenon.[11]
Remove ads
Notes and references
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads