Lab9-CSP.sagews

Cyclic sieving phenomenon

Math 737 - Lab 9

Let's look for cyclic sieving for rotation of bit strings (lists of zeros and ones)

First, let's look at the documentation for the CyclicSieving functions

CyclicSievingCheck?

File: /ext/sage/10.3/src/sage/misc/lazy_import.pyx
Docstring :
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

CyclicSievingPolynomial?

File: /ext/sage/10.3/src/sage/misc/lazy_import.pyx
Docstring :
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

Let's look at binary strings of length 4 with the action of rotation.

Run the commands below and figure out what each does.

F = finite_dynamical_systems.bitstring_rotation(4, ones = 2)
list(F.ground_set())
F.evolution()((0,1,1,0)) #it rotates the system in one step
F.orbits()
F.orbit_lengths()

[(1, 1, 0, 0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 1)] (1, 1, 0, 0) [[(0, 0, 1, 1), (0, 1, 1, 0), (1, 1, 0, 0), (1, 0, 0, 1)], [(0, 1, 0, 1), (1, 0, 1, 0)]] [4, 2]

Run the commands below to see how to make q-analogue polynomials

from sage.combinat.q_analogues import *
q_int(4) #This command gives the q - analogue of 4
q_factorial(4) #This command gives the q - analogue of 4!
q_binomial(4,2) #This command gives the q - binomial of (4,2)
q_multinomial((2,2,2)) #This command gives the q - multinomial of ((2,2)).

q^3 + q^2 + q + 1 q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1 q^4 + q^3 + 2*q^2 + q + 1 q^12 + 2*q^11 + 5*q^10 + 7*q^9 + 11*q^8 + 12*q^7 + 14*q^6 + 12*q^5 + 11*q^4 + 7*q^3 + 5*q^2 + 2*q + 1

Now run the cyclic sieving functions below. What do they tell you?

R.<q> = PolynomialRing(QQ)
CyclicSievingCheck(F.orbit_lengths(),None,q_binomial(4,2)) # This command checks whether the tripple exhibits the cyclic sieving phenomenon.
CyclicSievingPolynomial(F.orbit_lengths())  #Return the unique polynomial "q" of degree smaller than "order" such that the triple from above exhibits the Cyclic Sieving Phenomenon.

True q^3 + 2*q^2 + q + 2

Exercise 1: Describe what you learned about how the above commands work. Be sure to describe what each command does.

Exercise 2:

• Find two polynomials that exhibit cyclic sieving for length 8 binary strings with 4 ones under rotation: one polynomial by guessing a q-analogue and the other by using the function CyclicSievingPolynomial.

• How are these polynomials related?

• Guess what q-analogue polynomial exhibits cyclic sieving with length n binary strings with k ones under rotation.

SOLUTION TO EXERCISE 2

Exercise 3: Print the polynomials that are the q-analogues of the Catalan numbers $\frac{1}{n+1}\binom{2n}{n}$, for $n=2,3,4,5$.

Exercise 4: Verify that the set of standard Young tableaux of shape $(n,n)$ under promotion exhibits the CSP with the polynomial for Exercise 3 for $n=2,3,4,5$.

You can find this action by pressing tab in the block below.

finite_dynamical_systems.