Sage: Ticket #8500: Add the set of TransitiveGroups
https://trac.sagemath.org/ticket/8500
<p>
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.
</p>
<p>
This allows a user to do:
</p>
<pre class="wiki">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
</pre><p>
This requires the optional database_gap which contains all the
transitive permutation groups of degree <= 30. Therefore, in practice,
the enumeration stops with a <a class="missing wiki">NonImplementedError?</a> at degree 30.
</p>
<p>
Depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/8524" title="defect: DisjointUnionEnumeratedSets should have a private __classcall__ method (closed: fixed)">#8524</a>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8500
Trac 1.1.6nborieThu, 11 Mar 2010 21:34:28 GMTstatus changed
https://trac.sagemath.org/ticket/8500#comment:1
https://trac.sagemath.org/ticket/8500#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketnborieFri, 12 Mar 2010 07:23:26 GMTstatus changed
https://trac.sagemath.org/ticket/8500#comment:2
https://trac.sagemath.org/ticket/8500#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketnborieFri, 12 Mar 2010 23:49:40 GMTdescription, summary changed
https://trac.sagemath.org/ticket/8500#comment:3
https://trac.sagemath.org/ticket/8500#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8500?action=diff&version=3">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Add number_of_transitive_group function</em> to <em>Add the set of TransitiveGroups</em>
</li>
</ul>
TicketnborieFri, 12 Mar 2010 23:58:11 GMTstatus changed; cc set
https://trac.sagemath.org/ticket/8500#comment:4
https://trac.sagemath.org/ticket/8500#comment:4
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>cc</strong>
<em>sage-combinat</em> added
</li>
</ul>
TicketnthierySat, 13 Mar 2010 09:01:48 GMTstatus changed; author set
https://trac.sagemath.org/ticket/8500#comment:5
https://trac.sagemath.org/ticket/8500#comment:5
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>author</strong>
set to <em>Nicolas Borie</em>
</li>
</ul>
<p>
Wow,that was quick, thanks!
</p>
<p>
I browsed through the patch, which looks good. Some minor comments before I do the final review:
</p>
<ul><li>Change "trac 8500 Add the finite enumerated set of <a class="missing wiki">TransitiveGroups?</a>" to "<a class="closed ticket" href="https://trac.sagemath.org/ticket/8500" title="enhancement: Add the set of TransitiveGroups (closed: fixed)">#8500</a> Add the enumerated set of <a class="missing wiki">TransitiveGroups?</a>"
</li></ul><ul><li>Keep number_of_transitive_groups a private function (i.e. not in all.py)
</li></ul><ul><li><a class="missing wiki">TransitiveGroups?</a>() would better model the mathematical set of all transitive groups, even if this is only partially implemented. Hence <a class="missing wiki">TransitiveGroups?</a>() should be in <a class="missing wiki">InfiniteEnumeratedSets?</a> (and therefore <a class="missing wiki">TransitiveGroups?</a>().cardinality() will return infinity). As a side effect, the #long time should not be needed anymore for the <a class="missing wiki">TestSuite?</a>(<a class="missing wiki">TransitiveGroups?</a>()).run().
</li></ul><ul><li>You may actually want to implement <a class="missing wiki">TransitiveGroups?</a>() as a <a class="missing wiki">DisjointUnionOfEnumeratedSets?</a>, which should essentially do all the work for you.
</li></ul><ul><li>
</li></ul>
TicketnborieSat, 13 Mar 2010 09:18:40 GMT
https://trac.sagemath.org/ticket/8500#comment:6
https://trac.sagemath.org/ticket/8500#comment:6
<p>
Hi,
</p>
<ul><li>Commit message : will do!
</li></ul><ul><li>Private function : Why not? There is no reference page built for permgroup_named.py... It will be used by the very private club...
</li></ul><ul><li>Ok, Do you prefer a <a class="missing wiki">StopIteration?</a> or a <a class="missing wiki">NotImplementedError?</a> for the <span class="underline">iter</span> method ?
</li></ul><ul><li><a class="missing wiki">DisjointUnionOfEnumeratedSets?</a>????? 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....))
</li></ul><p>
Thanks for these advises...
</p>
TicketnthierySat, 13 Mar 2010 11:38:57 GMT
https://trac.sagemath.org/ticket/8500#comment:7
https://trac.sagemath.org/ticket/8500#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8500#comment:6" title="Comment 6">nborie</a>:
</p>
<blockquote class="citation">
<ul><li>Ok, Do you prefer a <a class="missing wiki">StopIteration?</a> or a <a class="missing wiki">NotImplementedError?</a> for the <span class="underline">iter</span> method ?
</li></ul></blockquote>
<p>
Hmm, I guess <a class="missing wiki">NotImplementedError?</a>. And I assume that should be what occurs by default with <a class="missing wiki">DisjointUnionOfEnumeratedSets?</a>.
</p>
<blockquote class="citation">
<ul><li><a class="missing wiki">DisjointUnionOfEnumeratedSets?</a>????? 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....))
</li></ul></blockquote>
<p>
Note: you'll have a micro-issue with classcall, which Florent is supposed to fix shortly (he stumbled into it yesterday.
</p>
<p>
Oh, by the way: what gap is providing you is actually an unrank function (see enumeratedSets). You just need to implement <a class="missing wiki">TransitiveGroups?</a>(3).unrank(5), and <span class="underline">iter</span> will be provided to you for free.
</p>
<blockquote class="citation">
<p>
Thanks for these advises...
</p>
</blockquote>
<p>
You are welcome!
</p>
TicketnborieMon, 15 Mar 2010 12:28:58 GMTstatus changed
https://trac.sagemath.org/ticket/8500#comment:8
https://trac.sagemath.org/ticket/8500#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketnborieMon, 15 Mar 2010 13:38:29 GMT
https://trac.sagemath.org/ticket/8500#comment:9
https://trac.sagemath.org/ticket/8500#comment:9
<p>
I included all yours recommendations. I just didn't remove the # long time for the test :
<a class="missing wiki">TestSuite?</a>(<a class="missing wiki">TransitiveGroups?</a>()).run()
Even it is now an Infinite Enumerated Set, the test still need around 20 seconds.
</p>
TicketnborieMon, 15 Mar 2010 14:37:17 GMTdescription changed
https://trac.sagemath.org/ticket/8500#comment:10
https://trac.sagemath.org/ticket/8500#comment:10
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8500?action=diff&version=10">diff</a>)
</li>
</ul>
TicketnborieMon, 15 Mar 2010 15:02:07 GMTattachment set
https://trac.sagemath.org/ticket/8500
https://trac.sagemath.org/ticket/8500
<ul>
<li><strong>attachment</strong>
set to <em>trac_8500_number_transitive_group-nb.patch</em>
</li>
</ul>
TicketnborieMon, 15 Mar 2010 15:03:08 GMTdescription changed
https://trac.sagemath.org/ticket/8500#comment:11
https://trac.sagemath.org/ticket/8500#comment:11
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8500?action=diff&version=11">diff</a>)
</li>
</ul>
<p>
I just update the patch : I forgot some # optional. Done..
</p>
TicketnthierySun, 18 Apr 2010 20:00:19 GMTattachment set
https://trac.sagemath.org/ticket/8500
https://trac.sagemath.org/ticket/8500
<ul>
<li><strong>attachment</strong>
set to <em>trac_8500_number_transitive_group-review-nt.patch</em>
</li>
</ul>
TicketnthierySun, 18 Apr 2010 20:01:54 GMTreviewer set
https://trac.sagemath.org/ticket/8500#comment:12
https://trac.sagemath.org/ticket/8500#comment:12
<ul>
<li><strong>reviewer</strong>
set to <em>Nicolas M. Thiéry</em>
</li>
</ul>
<p>
All test pass on Sage 4.3.4 and 4.4-alpha0.
</p>
<p>
That will be a useful feature! Thanks for handling this!
</p>
<p>
Please check my reviewer's patch, and if it's fine, go ahead and set a positive review.
</p>
TicketnborieSun, 18 Apr 2010 21:30:33 GMT
https://trac.sagemath.org/ticket/8500#comment:13
https://trac.sagemath.org/ticket/8500#comment:13
<p>
I applied the two patches with the dependency. Everything is ok except the sentence in the doc of the class <a class="missing wiki">TransitiveGroupsAll?</a>, the set is not finite!
</p>
<pre class="wiki">sage.groups.perm_gps.permgroup_named.TransitiveGroupsAll¶
The finite set of all transitive groups.
</pre><p>
That's my fault from my patch... Who fix that ? modulo the two letter "in" before finite, it is a positive review....
</p>
TicketnborieMon, 19 Apr 2010 08:06:22 GMTattachment set
https://trac.sagemath.org/ticket/8500
https://trac.sagemath.org/ticket/8500
<ul>
<li><strong>attachment</strong>
set to <em>trac_8500_number_transitive_group-review-nb.patch</em>
</li>
</ul>
TicketnborieMon, 19 Apr 2010 08:16:51 GMT
https://trac.sagemath.org/ticket/8500#comment:14
https://trac.sagemath.org/ticket/8500#comment:14
<p>
I clearly set a positive review on your reviewer patch!
</p>
<p>
I had a failure in :
sage -t sage/groups/perm_gps/permgroup_named.py --optional --long
</p>
<pre class="wiki">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
</pre><p>
Thus I propose you a final patch (very easy to review) with a fix of the doc of <a class="missing wiki">TransitiveGroupsAll?</a> and a move of an assert on the index of a transitive group.
</p>
<p>
Now, all tests long and optional passes. I hope we don't leave any error in the doc too.
</p>
TicketnthieryMon, 19 Apr 2010 17:25:31 GMTstatus changed
https://trac.sagemath.org/ticket/8500#comment:15
https://trac.sagemath.org/ticket/8500#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8500#comment:14" title="Comment 14">nborie</a>:
</p>
<blockquote class="citation">
<p>
I clearly set a positive review on your reviewer patch!
</p>
</blockquote>
<p>
Ok, thanks for checking!
</p>
<blockquote class="citation">
<p>
I had a failure in :
sage -t sage/groups/perm_gps/permgroup_named.py --optional --long
</p>
</blockquote>
<p>
Oops, I let that one slip through. Thanks for the report!
</p>
<blockquote class="citation">
<p>
Thus I propose you a final patch (very easy to review) with a fix of the doc of <a class="missing wiki">TransitiveGroupsAll?</a> and a move of an assert on the index of a transitive group.
</p>
</blockquote>
<p>
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.
</p>
<p>
With this the patch is good to go. Positive review. Thanks for your work on this!
</p>
<p>
I'll now fold the two patches together and upload the final version here.
</p>
TicketnthieryMon, 19 Apr 2010 17:28:43 GMTattachment set
https://trac.sagemath.org/ticket/8500
https://trac.sagemath.org/ticket/8500
<ul>
<li><strong>attachment</strong>
set to <em>trac_8500_transitive_groups-final.patch</em>
</li>
</ul>
<p>
Apply only this one
</p>
TicketnthieryMon, 19 Apr 2010 17:33:14 GMTkeywords, description changed
https://trac.sagemath.org/ticket/8500#comment:16
https://trac.sagemath.org/ticket/8500#comment:16
<ul>
<li><strong>keywords</strong>
<em>groups</em> added; <em>group</em> removed
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8500?action=diff&version=16">diff</a>)
</li>
</ul>
TicketjhpalmieriThu, 22 Apr 2010 02:08:05 GMTstatus changed
https://trac.sagemath.org/ticket/8500#comment:17
https://trac.sagemath.org/ticket/8500#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/8549" title="enhancement: Implements cycle index for permutation groups, toward Polya enumeration (closed: fixed)">#8549</a>, all tests pass. If I apply <em>both</em> patches, though, then on my Mac (OS X 10.6.3), I get a doctest failure:
</p>
<pre class="wiki">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]
</pre>
TicketnthieryThu, 22 Apr 2010 06:25:34 GMT
https://trac.sagemath.org/ticket/8500#comment:18
https://trac.sagemath.org/ticket/8500#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8500#comment:17" title="Comment 17">jhpalmieri</a>:
</p>
<blockquote class="citation">
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/8549" title="enhancement: Implements cycle index for permutation groups, toward Polya enumeration (closed: fixed)">#8549</a>, all tests pass. If I apply <em>both</em> patches, though, then on my Mac (OS X 10.6.3), I get a doctest failure:
</p>
</blockquote>
<p>
Ouch?!?!? How can two patches that add isolated features possibly break something so unrelated???
</p>
<p>
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?
</p>
<p>
Thanks!
</p>
TicketjhpalmieriThu, 22 Apr 2010 22:02:35 GMT
https://trac.sagemath.org/ticket/8500#comment:19
https://trac.sagemath.org/ticket/8500#comment:19
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8500#comment:18" title="Comment 18">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Ouch?!?!? How can two patches that add isolated features possibly break something so unrelated???
</p>
</blockquote>
<p>
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 <a class="ext-link" href="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"><span class="icon"></span>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</a> for a list. Of course, none of those touch the file schemes/hyperelliptic_curves/hyperelliptic_finite_field.py, either. At least <a class="closed ticket" href="https://trac.sagemath.org/ticket/8496" title="enhancement: Implement canonical heights for elliptic curves over number fields (closed: fixed)">#8496</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/8505" title="defect: random points on elliptic curve misses half the group (closed: fixed)">#8505</a>, and <a class="closed ticket" href="https://trac.sagemath.org/ticket/8557" title="enhancement: is_singular method for projective plane curves (closed: fixed)">#8557</a> have something to do with schemes...
</p>
<blockquote class="citation">
<p>
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?
</p>
</blockquote>
<p>
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.
</p>
TicketrbeezerSat, 29 May 2010 04:56:26 GMTstatus changed
https://trac.sagemath.org/ticket/8500#comment:20
https://trac.sagemath.org/ticket/8500#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
I asked Jason Grout via IRC to test <a class="closed ticket" href="https://trac.sagemath.org/ticket/8500" title="enhancement: Add the set of TransitiveGroups (closed: fixed)">#8500</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/8549" title="enhancement: Implements cycle index for permutation groups, toward Polya enumeration (closed: fixed)">#8549</a> on hyperelliptic_finite_field.py with OSX 10.6 and the file passed tests. Slightly edited IRC discussion.
</p>
<pre class="wiki">[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
</pre><p>
Same combination passed all long tests on 64-bit Ubuntu 9.04, in addition to the one file passing tests for Mike Hansen.
</p>
<p>
I ran long tests on <code>devel/sage/sage/groups/perm_gps/permgroup_named.py</code> with the gap database installed and it all passed tests.
</p>
<p>
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.
</p>
<p>
Rob
</p>
TicketrbeezerSat, 29 May 2010 04:57:14 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/8500#comment:21
https://trac.sagemath.org/ticket/8500#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Nicolas M. Thiéry</em> to <em>Nicolas M. Thiéry, Jason Grout</em>
</li>
</ul>
TicketnthieryMon, 31 May 2010 10:53:25 GMT
https://trac.sagemath.org/ticket/8500#comment:22
https://trac.sagemath.org/ticket/8500#comment:22
<p>
I just tried on bsd.sagemath.org, with 4.4.2 and just those two patches, and all test pass as well.
</p>
TicketmhansenSat, 05 Jun 2010 22:28:58 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/8500#comment:23
https://trac.sagemath.org/ticket/8500#comment:23
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.4.4.alpha0</em>
</li>
</ul>
Ticket