#8549 closed enhancement (fixed)
Implements cycle index for permutation groups, toward Polya enumeration
Reported by: | nborie | Owned by: | nborie |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.4 |
Component: | combinatorics | Keywords: | permutation groups, cycle index, Polya enumeration |
Cc: | sage-combinat | Merged in: | sage-4.4.4.alpha0 |
Authors: | Nicolas Borie, Nicolas M. Thiéry | Reviewers: | Nicolas M. Thiéry, Nicolas Borie, Rob Beezer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Let G a permutation group. Each permutation of G has a cycle type. The goal of this ticket is to add a method for permutation group which returns a symmetric function in the monomial symmetric functions whose terms are the numbers of permutation in G having the cycle type (Partition) indexing the corresponding monomial.
Attachments (1)
Change History (17)
comment:1 Changed 12 years ago by
- Description modified (diff)
- Summary changed from Add a cycle enumerator for Permutation Group to Add a cycle enumerator polynomial for Permutation Group
comment:2 Changed 12 years ago by
- Status changed from new to needs_review
comment:3 Changed 12 years ago by
- Summary changed from Add a cycle enumerator polynomial for Permutation Group to Implements cycle index for permutation groups, toward Polya enumeration
comment:4 Changed 12 years ago by
After face to face discussion, this patch is ready for review!
comment:5 Changed 12 years ago by
- Cc nthiery removed
- Keywords groups index Polya added
- Reviewers set to Nicolas M. Thiéry, Nicolas Borie
- Status changed from needs_review to positive_review
comment:6 Changed 12 years ago by
- Status changed from positive_review to needs_work
If I apply "trac_8549_cycle_enumerator-nb.patch" on top of 4.4.alpha1, all tests pass. If I instead apply the patch from #8500, all tests pass. If I apply both patches, though, then I get a doctest failure:
sage -t -long "devel/sage/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py" ********************************************************************** File "/Applications/sage_builds/sage-4.4.alpha1/devel/sage/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py", line 315: sage: len(C.points()) Exception raised: Traceback (most recent call last): File "/Applications/sage_builds/sage-4.4.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Applications/sage_builds/sage-4.4.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Applications/sage_builds/sage-4.4.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_6[7]>", line 1, in <module> len(C.points())###line 315: sage: len(C.points()) File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py", line 327, in points self.__points = self._points_fast_sqrt() # this is fast using Zech logarithms File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py", line 239, in _points_fast_sqrt points.append(self.point([x, v+sqrtD, one], check=True)) File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/scheme.py", line 256, in point return self._point_class(self, v, check=check) File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/algebraic_scheme.py", line 196, in _point_class return self.__A._point_class(*args, **kwds) File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/projective_space.py", line 535, in _point_class return morphism.SchemeMorphism_projective_coordinates_field(*args, **kwds) File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/morphism.py", line 608, in __init__ X.codomain()._check_satisfies_equations(v) File "/Applications/sage_builds/sage-4.4.alpha1/local/lib/python/site-packages/sage/schemes/generic/algebraic_scheme.py", line 465, in _check_satisfies_equations raise TypeError, "Coordinates %s do not define a point on %s"%(list(v),self) TypeError: Coordinates [7*a + 9, 2*a + 2, 1] do not define a point on Hyperelliptic Curve over Finite Field in a of size 11^2 defined by y^2 + (x^2 + 2)*y = x^5 + x + 10 ********************************************************************** 1 items had failures: 1 of 8 in __main__.example_6 ***Test Failed*** 1 failures. For whitespace errors, see the file /Users/palmieri/.sage//tmp/.doctest_hyperelliptic_finite_field.py [8.2 s]
comment:7 follow-up: ↓ 8 Changed 12 years ago by
I'm sorry, I forgot to say that I've only seen this on a Mac (OS X 10.6.3). On sage.math, all tests pass.
comment:8 in reply to: ↑ 7 Changed 12 years ago by
Replying to jhpalmieri:
I'm sorry, I forgot to say that I've only seen this on a Mac (OS X 10.6.3). On sage.math, all tests pass.
#8500 and #8549 together pass all long tests on 64-bit Ubuntu 9.04. I also saw Mike Hansen at Sage Days 21 test just the file sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py
with both patches and it passed all tests as well. I'll be working on a review at some point today.
comment:9 Changed 12 years ago by
Nicolas(s),
This is a nice addition, and I can already think of a use for it in a classroom example.
Some small comments/suggestions:
- One small bit of language, in
Here are the cycle index of some permutation groups
I would write the plural as "cycle indices." Nicely written otherwise.
- Would there be some way to qualify a value for the parent keyword as being legitimate? For example, with
D=DihedralGroup(7)
,14*D.cycle_index(parent=QQ)
goes boom. It doesn't seem that there is a simple type to test on (but maybe I'm wrong on this), but it does look like parent need only implement term() and sum(). Would it work to put something likeparent.term(Partition([1]), 1)
in a try/except block?
- Documentation.
(a) Do you want to add this into the reference manual?
(b) Last doctest block needs a preceding "::" to make it render as verbatim.
(c) Two instances of "cycle_type" near the top print weird due to the underscore.
Important stuff: builds and passes long tests, works as advertised. So I'm ready to give this a positive review subject to the above minor items.
Rob
comment:10 Changed 12 years ago by
See #8500 for the results of further OSX testing on this combination.
comment:11 Changed 12 years ago by
- Reviewers changed from Nicolas M. Thiéry, Nicolas Borie to Nicolas M. Thiéry, Nicolas Borie, Robert Beezer
Hi,
I just wrote a quick patch in the queue implementing the requested changes, and adding FinitePermutationGroups? to the ref manual where it was missing. Nicolas, please double check, fold, and reupload.
Changed 12 years ago by
comment:12 Changed 12 years ago by
- Status changed from needs_work to needs_review
Thanks very much for these fix.
All tests pass for sage, all tests long and optionnal pass for the finite_permutation_groups, the doc is well built... New comments for parent argument make also more clear the doc.
Positive Review from me. Thanks you Rob for pointing improvements and fix.
comment:13 Changed 12 years ago by
- Status changed from needs_review to positive_review
comment:14 Changed 12 years ago by
I change two times the status of this patch but I precise the last change come from Nicolas Thiéry.
This positive review is also modulo the comment
If I apply "trac_8549_cycle_enumerator-nb.patch" on top of 4.4.alpha1, all tests pass. If I instead apply the patch from #8500, all tests pass. If I apply both patches, though, then I get a doctest failure
I currently have no possible access to any OS X machine. All my tests was computing from Ubuntu machines.
comment:15 Changed 12 years ago by
- Merged in set to sage-4.4.4.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:16 Changed 12 years ago by
- Reviewers changed from Nicolas M. Thiéry, Nicolas Borie, Robert Beezer to Nicolas M. Thiéry, Nicolas Borie, Rob Beezer
This should allow to do some plethysm very easily.
Suggestion welcome to improve the latex math line and make it more nice and understandable.