Cyclic sieving phenomenon¶
Implementation of the Cyclic Sieving Phenomenon as described in Reiner, Stanton, White - The cyclic sieving phenomenon, Journal of Combinatorial Theory A 108 (2004)
We define the CyclicSievingPolynomial of a finite set S together with cyclic action cyc_act (of order n) to be the unique polynomial P(q) of order < n such that the triple ( S, cyc_act, P(q) ) exhibits the cyclic sieving phenomenon.
AUTHORS:
- Christian Stump
-
sage.combinat.cyclic_sieving_phenomenon.
CyclicSievingCheck
(L, cyc_act, f, order=None)¶ Returns True if the triple ( L, cyc_act, f ) exhibits the cyclic sieving phenomenon. If cyc_act is None, L is expected to obtain the orbit lengths.
INPUT:
- L – if cyc_act is None: list of orbit sizes, otherwise list of objects
- cyc_act – (default:None) function taking an element of L and returning an element of L (must define a bijection on L)
- order – (default:None) if set to an integer, this cyclic order of cyc_act is used (must be an integer multiple of the order of cyc_act)
- otherwise, the order of cyc_action is used
EXAMPLES:
sage: from sage.combinat.cyclic_sieving_phenomenon import * sage: from sage.combinat.q_analogues import q_binomial sage: S42 = [ Set(S) for S in subsets([1,2,3,4]) if len(S) == 2 ]; S42 [{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}] sage: cyc_act = lambda S: Set( i.mod(4)+1 for i in S) sage: cyc_act([1,3]) {2, 4} sage: cyc_act([1,4]) {1, 2} sage: p = q_binomial(4,2); p q^4 + q^3 + 2*q^2 + q + 1 sage: CyclicSievingPolynomial( S42, cyc_act ) q^3 + 2*q^2 + q + 2 sage: CyclicSievingCheck( S42, cyc_act, p ) True
-
sage.combinat.cyclic_sieving_phenomenon.
CyclicSievingPolynomial
(L, cyc_act=None, order=None, get_order=False)¶ Returns the unique polynomial p of degree smaller than order such that the triple ( L, cyc_act, p ) exhibits the CSP. If
cyc_act
is None,L
is expected to contain the orbit lengths.INPUT:
- L – if cyc_act is None: list of orbit sizes, otherwise list of objects
- cyc_act – (default:None) function taking an element of L and returning an element of L (must define a bijection on L)
- order – (default:None) if set to an integer, this cyclic order of cyc_act is used (must be an integer multiple of the order of cyc_act)
- otherwise, the order of cyc_action is used
- get_order – (default:False) if True, a tuple [p,n] is returned where p as above, and n is the order
EXAMPLES:
sage: from sage.combinat.cyclic_sieving_phenomenon import CyclicSievingPolynomial sage: S42 = [ Set(S) for S in subsets([1,2,3,4]) if len(S) == 2 ]; S42 [{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}] sage: cyc_act = lambda S: Set( i.mod(4)+1 for i in S) sage: cyc_act([1,3]) {2, 4} sage: cyc_act([1,4]) {1, 2} sage: CyclicSievingPolynomial( S42, cyc_act ) q^3 + 2*q^2 + q + 2 sage: CyclicSievingPolynomial( S42, cyc_act, get_order=True ) [q^3 + 2*q^2 + q + 2, 4] sage: CyclicSievingPolynomial( S42, cyc_act, order=8 ) q^6 + 2*q^4 + q^2 + 2 sage: CyclicSievingPolynomial([4,2]) q^3 + 2*q^2 + q + 2
TESTS:
We check that trac ticket #13997 is handled:
sage: CyclicSievingPolynomial( S42, cyc_act, order=8, get_order=True ) [q^6 + 2*q^4 + q^2 + 2, 8]
-
sage.combinat.cyclic_sieving_phenomenon.
orbit_decomposition
(L, cyc_act)¶ Returns the orbit decomposition of L by the action of cyc_act
INPUT:
- L – list
- cyc_act – function taking an element of L and returning an element of L (must define a bijection on L)
OUTPUT:
- a list of lists, the orbits under the cyc_act acting on L
EXAMPLES:
sage: from sage.combinat.cyclic_sieving_phenomenon import * sage: S42 = [ Set(S) for S in subsets([1,2,3,4]) if len(S) == 2 ]; S42 [{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3, 4}] sage: cyc_act = lambda S: Set( i.mod(4)+1 for i in S) sage: cyc_act([1,3]) {2, 4} sage: cyc_act([1,4]) {1, 2} sage: orbit_decomposition( S42, cyc_act ) [[{2, 4}, {1, 3}], [{1, 2}, {2, 3}, {3, 4}, {1, 4}]]