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:

Status badges

Description (last modified by nthiery)

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)

trac_8500_number_transitive_group-nb.patch (11.0 KB) - added by nborie 12 years ago.
trac_8500_number_transitive_group-review-nt.patch (19.2 KB) - added by nthiery 12 years ago.
trac_8500_number_transitive_group-review-nb.patch (1.4 KB) - added by nborie 12 years ago.
trac_8500_transitive_groups-final.patch (16.0 KB) - added by nthiery 12 years ago.
Apply only this one

Download all attachments as: .zip

Change History (27)

comment:1 Changed 12 years ago by nborie

  • Status changed from new to needs_review

comment:2 Changed 12 years ago by nborie

  • Status changed from needs_review to needs_work

comment:3 Changed 12 years ago by nborie

  • 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 nborie

  • Cc sage-combinat added
  • Status changed from needs_work to needs_review

comment:5 Changed 12 years ago by nthiery

  • Authors set to Nicolas Borie
  • Status changed from needs_review to needs_work

Wow,that was quick, thanks!

I browsed through the patch, which looks good. Some minor comments before I do the final review:

  • Keep number_of_transitive_groups a private function (i.e. not in all.py)

comment:6 follow-up: Changed 12 years ago by nborie

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

Replying to nborie:

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 nborie

  • Status changed from needs_work to needs_review

comment:9 Changed 12 years ago by nborie

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 nborie

  • Description modified (diff)

Changed 12 years ago by nborie

comment:11 Changed 12 years ago by nborie

  • Description modified (diff)

I just update the patch : I forgot some # optional. Done..

comment:12 Changed 12 years ago by nthiery

  • 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 nborie

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

comment:14 follow-up: Changed 12 years ago by nborie

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 nthiery

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

Changed 12 years ago by nthiery

Apply only this one

comment:16 Changed 12 years ago by nthiery

  • Description modified (diff)
  • Keywords groups added; group removed

comment:17 follow-up: Changed 12 years ago by jhpalmieri

  • 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: Changed 12 years ago by nthiery

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 jhpalmieri

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 rbeezer

  • 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 rbeezer

  • 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 nthiery

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 mhansen

  • Merged in set to sage-4.4.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.