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
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}]]