Opened 8 years ago

Closed 7 years ago

#11422 closed enhancement (fixed)

modular subgroups

Reported by: vdelecroix Owned by: vdelecroix
Priority: major Milestone: sage-4.7.2
Component: modular forms Keywords: group, arithmetic, linear group, sl, modular
Cc: Merged in: sage-4.7.2.alpha3
Authors: Vincent Delecroix Reviewers: David Loeffler
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #10334, #10335 Stopgaps:

Description (last modified by leif)

This ticket aims to extend capability of the class ArithmeticSubgroup_Permutation in sage.modular.arithgroup_perm. This is now possible to deal with any subgroup of SL(2,Z) and many new methods are available (in particular equality of subgroups, conjugacy problem, ...)

I reimplement the method todd_coxeter of sage.modular.arithgroup.arithgroup_generic to be faster and with more output.

I also created a test file for arithmetic subgroup.

See details and documentation in the patch.


Apply

  1. trac_11422-sl2z_subgroups.patch
  2. trac_11422-reviewerfix.patch
  3. trac_11422_unpicklefix.patch

to the Sage library.

Attachments (3)

trac_11422-sl2z_subgroups.patch (110.8 KB) - added by vdelecroix 8 years ago.
trac_11422-reviewerfix.patch (1.7 KB) - added by davidloeffler 8 years ago.
apply over previous patch
trac_11422_unpicklefix.patch (995 bytes) - added by davidloeffler 8 years ago.
apply over the two preceding patches

Download all attachments as: .zip

Change History (28)

comment:1 Changed 8 years ago by vdelecroix

  • Component changed from PLEASE CHANGE to modular forms
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 8 years ago by vdelecroix

  • Description modified (diff)
  • Keywords group arithmetic linear group sl modular added
  • Status changed from new to needs_review

comment:3 Changed 8 years ago by vdelecroix

  • Description modified (diff)

comment:4 follow-up: Changed 8 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to doctest failures

This looks great -- I always meant to do some more work on this but never got around to it, and you are clearly much better equipped to do so than I. Sadly there are masses of doctest failures (48 of them on a clean 4.7.1.alpha3 build with just your patch applied). Almost all of them look like this:

TypeError: cycle_tuples() takes no keyword arguments

Also, some gripes:

  • The English is a bit ropey in some of the docstrings (e.g. "vue", "canonic").
  • Some more explanation of what a few of the functions are doing would be nice -- e.g. what is canonical about the canonical labels?

comment:5 Changed 8 years ago by vdelecroix

  • Description modified (diff)

comment:6 in reply to: ↑ 4 Changed 8 years ago by vdelecroix

Hello,

Thanks for starting to look at this.

Replying to davidloeffler:

This looks great -- I always meant to do some more work on this but never got around to it, and you are clearly much better equipped to do so than I. Sadly there are masses of doctest failures (48 of them on a clean 4.7.1.alpha3 build with just your patch applied). Almost all of them look like this:

TypeError: cycle_tuples() takes no keyword arguments

There was a dependancy problem with #10335 which is now in the description.

Also, some gripes:

  • The English is a bit ropey in some of the docstrings (e.g. "vue", "canonic").

I'm not a native speaker and it's not easy to find where the errors are. In the new version I will post in few minutes, I have tried to be attentive to the language.

  • Some more explanation of what a few of the functions are doing would be nice -- e.g. what is canonical about the canonical labels?

Could you be more precise ? In the new version, I expanded some of the documentations (especially the canonical labels).

comment:7 Changed 8 years ago by vdelecroix

  • Status changed from needs_work to needs_review
  • Work issues doctest failures deleted

comment:8 follow-up: Changed 8 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to corrections to docstrings

OK, I downloaded #10335 and its prerequisites and it works fine now.

Algorithm comments:

  • For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:
  • having a flag that remembers whether the group is already canonically labelled,
  • when that's not the case, caching the canonically labelled version.
  • At line 1019 of arithgroup.py, if check is True, won't this cause the check code to be run *twice*?

Corrections to docstrings:

In arithgroup_generic.py:

  • The docstring for the todd_coxeter method is a bit vague: I'd suggest that you specify a bit more precisely what the lists l and s mean. "The action of the parabolic elements" is misleading; you mean the action of the specific parabolic element [[1, 1],[0,1]] .
  • It is disrespectful to Todd and Coxeter to write their names in lowercase, as you do in the docstring for as_permutation_group -- better to write "This uses Todd-Coxeter enumeration".

In arithgroup_perm.py:

  • "point of vue" --> "point of view" in the module docstring (as I pointed out above)
  • Again in that docstring, you make it sound like all four of L, R, S2 and S3 are needed to generate the modular group -- explain that the "three couples which are of main interest" are of interest because each pair of elements generates the whole group.
  • The "todo" list will look bizzarre: some LaTeX formatting is needed for the second item
  • Line 328: "generator" --> "generators"
  • Line 630 "numerotation" --> "numbering"
  • 640: "defines" --> "define", "renumerote" --> "renumber" (the nonexistent word "numerote" appears twice more in the next few lines)
  • 744: "Returns the smallest label among rooted label" -- do you seriously expect that anyone will have the foggiest clue what this means?
  • 749: "canonic" --> "canonical". This occurs all over the place. Fix them all.
  • 810: needs more explanation of what the argument j0 does.
  • 812: "renumerotation" --> "renumbering" again.
  • 908: "does not permutes" --> "does not permute"
  • 947: "at the first times" --> "at the first time"

That's as far as I've got so far -- other duties call.

comment:9 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by vdelecroix

  • Status changed from needs_work to needs_review
  • Work issues corrections to docstrings deleted

Thanks for the detailed report.

Algorithm comments:

  • For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:
  • having a flag that remembers whether the group is already canonically labelled,
  • when that's not the case, caching the canonically labelled version.

Totally right. I choose to add an attribute _canonical_label_group when the group with canonical renumbering has been computed.

  • At line 1019 of arithgroup.py, if check is True, won't this cause the check code to be run *twice*?

I don't think so. The function call is called only once, the contains method does not call the constructor and the init method of ArithmeticSubgroupElement? does not care about wheter or not the element is in the subgroup "parent" given as argument.

Corrections to docstrings:

I made the corrections.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 8 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to amusing typo bug

Replying to vdelecroix:

Algorithm comments:

  • For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:
  • having a flag that remembers whether the group is already canonically labelled,
  • when that's not the case, caching the canonically labelled version.

Totally right. I choose to add an attribute _canonical_label_group when the group with canonical renumbering has been computed.

There is an amusingly subtle bug here.

At line 769, the code sets the attribute _canonical_labelel_group, which is clearly a typo. This means that a subsequent hasattr check for _canonical_label_group returns False, leading to the following:

sage: S2 = "(1,2)(3,4)(5,6)"
sage: S3 = "(1,3,5)(2,4,6)"
sage: G = ArithmeticSubgroup_Permutation(S2=S2,S3=S3)
sage: H = G.relabel(inplace=False)
sage: G.has_canonical_labels()
False

I don't think this is what you intended, is it?

The reason I said it's complicated is that naming the method "has_canonical_labels" is slightly misleading. I would have assumed that "G.has_canonical_labels() == True" means that the labels G is using are the canonical ones. Although it's not what you intended, the typo has meant that the function is now *almost* doing what I feel the name suggests it should do! ("Almost" because it might return False in some cases even if the labels actually are the canonical ones.)

I would advocate correcting the typo at line 769 but also changing the has_canonical_labels function so it does what I said, i.e. so returns True if and only if self._canonical_rooted_labels() == range(self.index()), with a docstring to match.

  • At line 1019 of arithgroup.py, if check is True, won't this cause the check code to be run *twice*?

I don't think so.

You're right, of course; sorry.

comment:11 in reply to: ↑ 10 Changed 8 years ago by vdelecroix

Replying to davidloeffler:

Replying to vdelecroix:

Algorithm comments:

  • For permutation subgroups, almost all calculations are done with a relabelled version, but this is generated anew every time! I'd suggest:
  • having a flag that remembers whether the group is already canonically labelled,
  • when that's not the case, caching the canonically labelled version.

Totally right. I choose to add an attribute _canonical_label_group when the group with canonical renumbering has been computed.

There is an amusingly subtle bug here.

Hopefully, you find that crazy bug! Thanks! I had a supplementary doctest for this method.

I would advocate correcting the typo at line 769 but also changing the has_canonical_labels function so it does what I said, i.e. so returns True if and only if self._canonical_rooted_labels() == range(self.index()), with a docstring to match.

I removed the function has_canonical_labels which is not useful at all.

Changed 8 years ago by vdelecroix

comment:12 Changed 8 years ago by vdelecroix

  • Status changed from needs_work to needs_review
  • Work issues amusing typo bug deleted

comment:13 Changed 8 years ago by davidloeffler

  • Reviewers set to David Loeffler
  • Status changed from needs_review to positive_review

Excellent -- good stuff. Positive review. Sadly this is probably too late for 4.7.1, but it should get into 4.7.2.

(Now I will have to rebase #5048, and not for the first time. I should stop giving positive reviews to patches that conflict with my own ;-) )

comment:14 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:15 Changed 8 years ago by jdemeyer

  • Dependencies set to #10334, #10335
  • Description modified (diff)

comment:16 Changed 8 years ago by davidloeffler

  • Status changed from positive_review to needs_work
  • Work issues set to to_even_subgroup problem

Hang on, there's something wrong with to_even_subgroup.

sage: H = ArithmeticSubgroup_Permutation(S2 = '(1,4,11,14)(2,7,12,17)(3,5,13,15)(6,9,16,19)(8,10,18,20)', S3 = '(1,2,3,11,12,13)(4,5,6,14,15,16)(7,8,9,17,18,19)(10,20)')
sage: G = H.to_even_subgroup()
sage: H.is_subgroup(G)
False

Changed 8 years ago by davidloeffler

apply over previous patch

comment:17 follow-up: Changed 8 years ago by davidloeffler

  • Status changed from needs_work to needs_review

Here's a patch. The problem was the use of a python set type: you can certainly enumerate sets, but you shouldn't expect the enumeration order to be consistent! I changed the code slightly to use lists, combining two loops into one.

Vincent: if you're happy with my change, you can restore the positive review.

comment:18 in reply to: ↑ 17 Changed 8 years ago by vdelecroix

  • Status changed from needs_review to positive_review
  • Work issues to_even_subgroup problem deleted

Replying to davidloeffler:

Here's a patch. The problem was the use of a python set type: you can certainly enumerate sets, but you shouldn't expect the enumeration order to be consistent! I changed the code slightly to use lists, combining two loops into one.

Vincent: if you're happy with my change, you can restore the positive review.

Thanks for debugging (it seems that you're using the code... cool!).

comment:19 Changed 8 years ago by davidloeffler

  • Status changed from positive_review to needs_work

Hang on, this isn't good:

sage -t -long -force_lib "devel/sage/sage/structure/sage_object.pyx"
**********************************************************************
File "/storage/masiao/sage-4.7.1.alpha4/devel/sage/sage/structure/sage_object.pyx", line 1077:
    sage: sage.structure.sage_object.unpickle_all()  # (4s on sage.math, 2011)
Expected:
    Successfully unpickled ... objects.
    Failed to unpickle 0 objects.
Got: 
     * unpickle failure: load('/home/masiao/.sage/temp/selmer/23062/dir_2/pickle_jar/_class__sage_modular_arithgroup_arithgroup_perm_ArithmeticSubgroup_Permutation__.sobj')
    Failed:
    _class__sage_modular_arithgroup_arithgroup_perm_ArithmeticSubgroup_Permutation__.sobj
    Successfully unpickled 586 objects.
    Failed to unpickle 1 objects.
**********************************************************************
1 items had failures:
   1 of   7 in __main__.example_25
***Test Failed*** 1 failures.
For whitespace errors, see the file /home/masiao/.sage//tmp/.doctest_sage_object.py
         [8.2 s]

This is because sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation was a class before and is now a factory function, so Python doesn't know how to unpickle pickled objects of that class.

Changed 8 years ago by davidloeffler

apply over the two preceding patches

comment:20 follow-up: Changed 8 years ago by davidloeffler

  • Status changed from needs_work to needs_review

It turns out the unpickling problems can be sorted out by ensuring that sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation can be called with two positional arguments corresponding to L and R. All tests now pass on my system.

comment:21 in reply to: ↑ 20 Changed 8 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Replying to davidloeffler:

It turns out the unpickling problems can be sorted out by ensuring that sage.modular.arithgroup.arithgroup_perm.ArithmeticSubgroup_Permutation can be called with two positional arguments corresponding to L and R. All tests now pass on my system.

All tests and backward compatibility with pickling also pass on my computer. I put a positive review.

comment:22 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.7.2 to sage-pending

comment:23 Changed 7 years ago by davidloeffler

  • Milestone changed from sage-pending to sage-4.7.2

comment:24 Changed 7 years ago by leif

  • Description modified (diff)

comment:25 Changed 7 years ago by leif

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