Opened 6 years ago

Closed 5 years ago

Last modified 5 years ago

#10155 closed enhancement (fixed)

Implementation of the Cyclic Sieving Phenomenon

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-4.8
Component: combinatorics Keywords: Cyclic Sieving Phenomenon
Cc: Merged in: sage-4.8.alpha0
Authors: Christian Stump Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by chapoton)

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.

Attachments (1)

trac_10155-cyclic_sieving_phenomenon-cs.patch (6.7 KB) - added by stumpc5 6 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 6 years ago by stumpc5

  • Status changed from new to needs_review

comment:2 Changed 6 years ago by stumpc5

  • Description modified (diff)

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

comment:3 follow-up: Changed 6 years ago by chapoton

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

Same thing for the patch Ticket #10065 on posets.

comment:4 in reply to: ↑ 3 Changed 6 years ago by stumpc5

Replying to chapoton:

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.

comment:5 follow-up: Changed 6 years ago by chapoton

  • Owner changed from sage-combinat to (none)

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.

comment:6 in reply to: ↑ 5 Changed 6 years ago by stumpc5

Replying to chapoton:

Then the buildbot will be slightly more happy.

done, thanks...

comment:7 Changed 6 years ago by stumpc5

  • Milestone set to sage-4.7.1

comment:8 Changed 6 years ago by stumpc5

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:9 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

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..

comment:10 Changed 6 years ago by stumpc5

  • Status changed from needs_work to needs_review

Salut Fred --

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

Best, Christian

comment:11 follow-up: Changed 5 years ago by chapoton

Hello, Christian. 

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

Best, Fred

comment:12 in reply to: ↑ 11 ; follow-up: Changed 5 years ago by stumpc5

Replying to chapoton:

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?

comment:13 in reply to: ↑ 12 ; follow-up: Changed 5 years ago by chapoton

Replying to stumpc5:

Replying to chapoton:

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

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

What about using

R = ZZ['q']

instead ?

comment:14 in reply to: ↑ 13 Changed 5 years ago by stumpc5

Replying to chapoton:

Replying to stumpc5:

Replying to chapoton:

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

comment:15 Changed 5 years ago by chapoton

  • Description modified (diff)
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

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)

comment:16 Changed 5 years ago by jdemeyer

  • Milestone changed from sage-4.7.2 to sage-4.7.3

comment:17 Changed 5 years ago by jdemeyer

  • Merged in set to sage-4.7.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:18 Changed 5 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:19 Changed 5 years ago by jdemeyer

  • Merged in changed from sage-4.7.3.alpha0 to sage-4.8.alpha0
  • Milestone set to sage-4.8
Note: See TracTickets for help on using tickets.