Implementation of the Cyclic Sieving Phenomenon

[stumpc5]

This patch implements the Cyclic Sieving Phenomenon (CSP) as described in

Reiner, Stanton, White - The cyclic sieving phenomenon, JCTA108 (2004)

Given a finite set S and a cyclic action cyc_act on S, the method CyclicSievingPolynomial( S, cyc_act ) returns the unique polynomial P of order < n such that the triple ( S, cyc_act, P ) exhibits the CSP. The method CyclicSievingCheck( S, cyc_act, P ) checks if this triple exhibits the CSP.

Component: combinatorics

Keywords: Cyclic Sieving Phenomenon

Author: Christian Stump

Reviewer: Frédéric Chapoton

Merged: sage-4.8.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/10155

[stumpc5]

comment:2

I added another possibility to give only the orbit sizes to obtain the polynomial P.

[fchapoton]

comment:3

Is there a reason why there are two patches here ? The buildbot gets confused.

Same thing for the patch Ticket #10065 on posets.

[stumpc5]

comment:4

Replying to @fchapoton:

Is there a reason why there are two patches here ? The buildbot gets confused.

Same thing for the patch Ticket #10065 on posets.

I can override only files with the same name and not delete any (is that true?). So when the name changes, or if I forget to mark the box, the file stays there forever. I am happy to learn about a way to get around that.

For both tickets, only the youngest file contains the newest version of the patch.

[fchapoton]

comment:5

You should modify the header of your patch : add something like

#10155 Implementation of the Cyclic Sieving Phenomenon

Then the buildbot will be slightly more happy.

[stumpc5]

comment:6

Replying to @fchapoton:

Then the buildbot will be slightly more happy.

done, thanks...

[fchapoton]

comment:9

This seems good enough. I will soon give a positive review if minor corrections are made.

1. at start of the patch, before AUTHORS, there is a broken (not complete) sentence.

2. I am not happy with the name of the procedures.

What about CyclicSieving_find and CyclicSieving_test ?

or CyclicSievingPolynomial and CyclicSievingCheck ?

or some mix of that..

3. You could use R.gen() instead of R.gens()[0] (at least twice)

4. in CyclicSieving, you can use keys to compute n, instead of calling .keys() again

5. in orbit_decomposition, there misses the OUTPUT: a list of lists, the orbits under cyc_act acting on L

6. why do you need to import QQ ? because of q-analogues ? coercion may work with ZZ, maybe..

[stumpc5]

Attachment: trac_10155-cyclic_sieving_phenomenon-cs.patch.gz

[stumpc5]

comment:10

Salut Fred --

Thanks for looking at this patch! I made the changed 1:1 according to your suggestions.

Best, Christian

[fchapoton]

comment:11

Hello, Christian. 

You did not answer my point 6. Do you really need QQ ?

Best, Fred

[stumpc5]

comment:12

Replying to @fchapoton:

You did not answer my point 6. Do you really need QQ ?

I use it when defining the polynomial:

R = QQ['q']

Or did you think of doing that differently?

[fchapoton]

comment:13

Replying to @stumpc5:

Replying to @fchapoton:

You did not answer my point 6. Do you really need QQ ?

I use it when defining the polynomial: R = QQ[['q']] Or did you think of doing that differently ?

What about using

R = ZZ['q']

instead ?

[stumpc5]

comment:14

Replying to @fchapoton:

Replying to @stumpc5:

Replying to @fchapoton:

What about using

R = ZZ['q']

I don't know why, but the mod operation on R(f) does not work in that case. I had a quick look but didn't see the reason right away...

As the QQ doesn't really do anything negative (or does it?), I think we should just leave it.

Best, Christian

[fchapoton]

comment:15

ok, I agree that this is a minor point, and I give a positive review. (It seems that the patchbot is currently useless, so I do not require a green light from the bot)

[fchapoton]

Reviewer: Frédéric Chapoton

[jdemeyer]

Merged: sage-4.7.3.alpha0

[jdemeyer]

Milestone sage-4.7.3 deleted

[jdemeyer]

Changed merged from sage-4.7.3.alpha0 to sage-4.8.alpha0