Cyclic sieving phenomenon#

Implementation of the Cyclic Sieving Phenomenon as described by Reiner, Stanton, and White in [RSW2004].

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

REFERENCES:

[RSW2004]

Reiner, Stanton, White - The cyclic sieving phenomenon, Journal of Combinatorial Theory A 108 (2004)

sage.combinat.cyclic_sieving_phenomenon.CyclicSievingCheck(L, cyc_act, f, order=None)[source]#

Return whether the triple (L, cyc_act, f) exhibits the cyclic sieving phenomenon.

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) bijective function from L to 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 = Subsets([1,2,3,4], 2)
sage: def cyc_act(S): return 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

>>> from sage.all import *
>>> from sage.combinat.cyclic_sieving_phenomenon import *
>>> from sage.combinat.q_analogues import q_binomial
>>> S42 = Subsets([Integer(1),Integer(2),Integer(3),Integer(4)], Integer(2))
>>> def cyc_act(S): return Set(i.mod(Integer(4)) + Integer(1) for i in S)
>>> cyc_act([Integer(1),Integer(3)])
{2, 4}
>>> cyc_act([Integer(1),Integer(4)])
{1, 2}
>>> p = q_binomial(Integer(4),Integer(2)); p
q^4 + q^3 + 2*q^2 + q + 1
>>> CyclicSievingPolynomial( S42, cyc_act )
q^3 + 2*q^2 + q + 2
>>> CyclicSievingCheck( S42, cyc_act, p )
True
sage.combinat.cyclic_sieving_phenomenon.CyclicSievingPolynomial(L, cyc_act=None, order=None, get_order=False)[source]#

Return the unique polynomial p of degree smaller than order such that the triple (L, cyc_act, p) exhibits the Cyclic Sieving Phenomenon.

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) bijective function from L to 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 is as above, and n is the order

EXAMPLES:

sage: from sage.combinat.cyclic_sieving_phenomenon import CyclicSievingPolynomial
sage: S42 = Subsets([1,2,3,4], 2)
sage: def cyc_act(S): return 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

>>> from sage.all import *
>>> from sage.combinat.cyclic_sieving_phenomenon import CyclicSievingPolynomial
>>> S42 = Subsets([Integer(1),Integer(2),Integer(3),Integer(4)], Integer(2))
>>> def cyc_act(S): return Set(i.mod(Integer(4)) + Integer(1) for i in S)
>>> cyc_act([Integer(1),Integer(3)])
{2, 4}
>>> cyc_act([Integer(1),Integer(4)])
{1, 2}
>>> CyclicSievingPolynomial(S42, cyc_act)
q^3 + 2*q^2 + q + 2
>>> CyclicSievingPolynomial(S42, cyc_act, get_order=True)
[q^3 + 2*q^2 + q + 2, 4]
>>> CyclicSievingPolynomial(S42, cyc_act, order=Integer(8))
q^6 + 2*q^4 + q^2 + 2
>>> CyclicSievingPolynomial([Integer(4),Integer(2)])
q^3 + 2*q^2 + q + 2
sage.combinat.cyclic_sieving_phenomenon.orbit_decomposition(L, cyc_act)[source]#

Return the orbit decomposition of L by the action of cyc_act.

INPUT:

  • L – list

  • cyc_act – bijective function from L to 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 = Subsets([1,2,3,4], 2); S42
Subsets of {1, 2, 3, 4} of size 2
sage: def cyc_act(S): return Set(i.mod(4) + 1 for i in S)
sage: cyc_act([1,3])
{2, 4}
sage: cyc_act([1,4])
{1, 2}
sage: orbits = orbit_decomposition(S42, cyc_act)
sage: sorted([sorted(orb, key=sorted) for orb in orbits], key=len)
[[{1, 3}, {2, 4}], [{1, 2}, {1, 4}, {2, 3}, {3, 4}]]

>>> from sage.all import *
>>> from sage.combinat.cyclic_sieving_phenomenon import *
>>> S42 = Subsets([Integer(1),Integer(2),Integer(3),Integer(4)], Integer(2)); S42
Subsets of {1, 2, 3, 4} of size 2
>>> def cyc_act(S): return Set(i.mod(Integer(4)) + Integer(1) for i in S)
>>> cyc_act([Integer(1),Integer(3)])
{2, 4}
>>> cyc_act([Integer(1),Integer(4)])
{1, 2}
>>> orbits = orbit_decomposition(S42, cyc_act)
>>> sorted([sorted(orb, key=sorted) for orb in orbits], key=len)
[[{1, 3}, {2, 4}], [{1, 2}, {1, 4}, {2, 3}, {3, 4}]]