Opened 12 years ago
Closed 12 years ago
#8500 closed enhancement (fixed)
Add the set of TransitiveGroups
Reported by: | nborie | Owned by: | nborie |
---|---|---|---|
Priority: | major | Milestone: | sage-4.4.4 |
Component: | group theory | Keywords: | transitive groups |
Cc: | sage-combinat | Merged in: | sage-4.4.4.alpha0 |
Authors: | Nicolas Borie | Reviewers: | Nicolas M. Thiéry, Jason Grout |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch implements the finite enumerated set of transitive permutation groups of a given degree, and the infinite enumerated set of all transitive permutation groups. The later is built as a disjoint union of the former.
This allows a user to do:
sage: TransitiveGroups(4).cardinality() sage: for G in TransitiveGroups(i): ... any_test(G) # any test over all transitive groups of a given degree sage: for G in TransitiveGroups(): ... other_test(G) # test over all transitive groups
This requires the optional database_gap which contains all the transitive permutation groups of degree <= 30. Therefore, in practice, the enumeration stops with a NonImplementedError? at degree 30.
Depends on #8524.
Attachments (4)
Change History (27)
comment:1 Changed 12 years ago by
- Status changed from new to needs_review
comment:2 Changed 12 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 12 years ago by
- Description modified (diff)
- Summary changed from Add number_of_transitive_group function to Add the set of TransitiveGroups
comment:4 Changed 12 years ago by
- Cc sage-combinat added
- Status changed from needs_work to needs_review
comment:5 Changed 12 years ago by
- Status changed from needs_review to needs_work
comment:6 follow-up: ↓ 7 Changed 12 years ago by
Hi,
- Commit message : will do!
- Private function : Why not? There is no reference page built for permgroup_named.py... It will be used by the very private club...
- Ok, Do you prefer a StopIteration? or a NotImplementedError? for the iter method ?
- DisjointUnionOfEnumeratedSets?????? I don't know this toy but I already like the name. Will play with it (and hope it is robust (like children, when I play....))
Thanks for these advises...
comment:7 in reply to: ↑ 6 Changed 12 years ago by
Replying to nborie:
- Ok, Do you prefer a StopIteration? or a NotImplementedError? for the iter method ?
Hmm, I guess NotImplementedError?. And I assume that should be what occurs by default with DisjointUnionOfEnumeratedSets?.
- DisjointUnionOfEnumeratedSets?????? I don't know this toy but I already like the name. Will play with it (and hope it is robust (like children, when I play....))
Note: you'll have a micro-issue with classcall, which Florent is supposed to fix shortly (he stumbled into it yesterday.
Oh, by the way: what gap is providing you is actually an unrank function (see enumeratedSets). You just need to implement TransitiveGroups?(3).unrank(5), and iter will be provided to you for free.
Thanks for these advises...
You are welcome!
comment:8 Changed 12 years ago by
- Status changed from needs_work to needs_review
comment:9 Changed 12 years ago by
I included all yours recommendations. I just didn't remove the # long time for the test : TestSuite?(TransitiveGroups?()).run() Even it is now an Infinite Enumerated Set, the test still need around 20 seconds.
comment:10 Changed 12 years ago by
- Description modified (diff)
Changed 12 years ago by
comment:11 Changed 12 years ago by
- Description modified (diff)
I just update the patch : I forgot some # optional. Done..
Changed 12 years ago by
comment:12 Changed 12 years ago by
- Reviewers set to Nicolas M. Thiéry
All test pass on Sage 4.3.4 and 4.4-alpha0.
That will be a useful feature! Thanks for handling this!
Please check my reviewer's patch, and if it's fine, go ahead and set a positive review.
comment:13 Changed 12 years ago by
I applied the two patches with the dependency. Everything is ok except the sentence in the doc of the class TransitiveGroupsAll?, the set is not finite!
sage.groups.perm_gps.permgroup_named.TransitiveGroupsAll¶ The finite set of all transitive groups.
That's my fault from my patch... Who fix that ? modulo the two letter "in" before finite, it is a positive review....
Changed 12 years ago by
comment:14 follow-up: ↓ 15 Changed 12 years ago by
I clearly set a positive review on your reviewer patch!
I had a failure in : sage -t sage/groups/perm_gps/permgroup_named.py --optional --long
sage -t --optional --long "devel/sage-review/sage/groups/perm_gps/permgroup_named.py" ********************************************************************** File "/opt/sage/devel/sage-review/sage/groups/perm_gps/permgroup_named.py", line 884: sage: TransitiveGroup(5,0) # requires optional database_gap Expected: Traceback (most recent call last): ... AssertionError: n should be in {1,..,5} Got: Traceback (most recent call last): ... assert n > 0 AssertionError
Thus I propose you a final patch (very easy to review) with a fix of the doc of TransitiveGroupsAll? and a move of an assert on the index of a transitive group.
Now, all tests long and optional passes. I hope we don't leave any error in the doc too.
comment:15 in reply to: ↑ 14 Changed 12 years ago by
- Status changed from needs_review to positive_review
Replying to nborie:
I clearly set a positive review on your reviewer patch!
Ok, thanks for checking!
I had a failure in : sage -t sage/groups/perm_gps/permgroup_named.py --optional --long
Oops, I let that one slip through. Thanks for the report!
Thus I propose you a final patch (very easy to review) with a fix of the doc of TransitiveGroupsAll? and a move of an assert on the index of a transitive group.
I merged your doc fix in my patch. For the assertion, I fixed the doctest instead. The message is not as nice, but using assert n>0 has the (admittedly limited) advantage of failing even if the database is not there.
With this the patch is good to go. Positive review. Thanks for your work on this!
I'll now fold the two patches together and upload the final version here.
comment:16 Changed 12 years ago by
- Description modified (diff)
- Keywords groups added; group removed
comment:17 follow-up: ↓ 18 Changed 12 years ago by
- Status changed from positive_review to needs_work
If I apply "trac_8500_transitive_groups-final.patch" on top of 4.4.alpha1, all tests pass. If I instead apply the patch from #8549, all tests pass. If I apply both patches, though, then on my Mac (OS X 10.6.3), 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:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 12 years ago by
Replying to jhpalmieri:
If I apply "trac_8500_transitive_groups-final.patch" on top of 4.4.alpha1, all tests pass. If I instead apply the patch from #8549, all tests pass. If I apply both patches, though, then on my Mac (OS X 10.6.3), I get a doctest failure:
Ouch?!?!? How can two patches that add isolated features possibly break something so unrelated???
I am totally clueless on how to attack this. Is there a mac somewhere online where I could login to play around? Is the gap-database installed on that mac?
Thanks!
comment:19 in reply to: ↑ 18 Changed 12 years ago by
Replying to nthiery:
Ouch?!?!? How can two patches that add isolated features possibly break something so unrelated???
I don't know, but it was quite repeatable: apply either patch first, no doctest failure, then apply the second one, and boom. (Although it took me a little while to track down that two independent tickets seemed to be causing the problem.) I just confirmed this on a second mac. It seems to require 4.4.alpha1, not 4.4.alpha0, so it must also be related to one of the tickets already merged there: see http://trac.sagemath.org/sage_trac/query?order=priority&col=id&col=summary&col=status&col=type&col=priority&col=milestone&col=component&merged=%7Esage-4.4.alpha1 for a list. Of course, none of those touch the file schemes/hyperelliptic_curves/hyperelliptic_finite_field.py, either. At least #8496, #8505, and #8557 have something to do with schemes...
I am totally clueless on how to attack this. Is there a mac somewhere online where I could login to play around? Is the gap-database installed on that mac?
As far as I know, bsd.math.washington.edu is a mac which is used for Sage development. You will need a separate account on it: an account on sage.math doesn't automatically give you one on bsd.math. Ask William (or maybe Tom Boothby?) about that.
comment:20 Changed 12 years ago by
- Status changed from needs_work to needs_review
I asked Jason Grout via IRC to test #8500 and #8549 on hyperelliptic_finite_field.py with OSX 10.6 and the file passed tests. Slightly edited IRC discussion.
[21:34] <rbeezer> jason-: ping [21:34] <jason-> pong [21:35] <rbeezer> could you do a simple OSX 10.6 test? [21:35] <rbeezer> #8500, #8549, apply one patch from each, then [21:35] <rbeezer> sage -t -long "devel/sage/sage/schemes/hyperelliptic_curves/hyperelliptic_finite_field.py" [21:35] <rbeezer> ??? [21:36] <jason-> Let me see [21:37] <rbeezer> thanks - this particular combo is holding up both tickets [21:39] <jason-> all tests passed! [21:40] <rbeezer> thanks [21:41] <jason-> rbeezer: that's osx 10.6
Same combination passed all long tests on 64-bit Ubuntu 9.04, in addition to the one file passing tests for Mike Hansen.
I ran long tests on devel/sage/sage/groups/perm_gps/permgroup_named.py
with the gap database installed and it all passed tests.
Given that this seemed ready for a positive review and now passes tests on the OSX combination, I am going to set this to positive review and add Jason to the reviewer list.
Rob
comment:21 Changed 12 years ago by
- Reviewers changed from Nicolas M. Thiéry to Nicolas M. Thiéry, Jason Grout
- Status changed from needs_review to positive_review
comment:22 Changed 12 years ago by
I just tried on bsd.sagemath.org, with 4.4.2 and just those two patches, and all test pass as well.
comment:23 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
Wow,that was quick, thanks!
I browsed through the patch, which looks good. Some minor comments before I do the final review: