Opened 11 years ago
Closed 11 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 )
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
to the Sage library.
Attachments (3)
Change History (28)
comment:1 Changed 11 years ago by
- Component changed from PLEASE CHANGE to modular forms
- Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 11 years ago by
- Description modified (diff)
- Keywords group arithmetic linear group sl modular added
- Status changed from new to needs_review
comment:3 Changed 11 years ago by
- Description modified (diff)
comment:4 follow-up: ↓ 6 Changed 11 years ago by
- Status changed from needs_review to needs_work
- Work issues set to doctest failures
comment:5 Changed 11 years ago by
- Description modified (diff)
comment:6 in reply to: ↑ 4 Changed 11 years ago by
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 11 years ago by
- Status changed from needs_work to needs_review
- Work issues doctest failures deleted
comment:8 follow-up: ↓ 9 Changed 11 years ago by
- 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
ands
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: ↓ 10 Changed 11 years ago by
- 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: ↓ 11 Changed 11 years ago by
- 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 11 years ago by
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 ifself._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 11 years ago by
comment:12 Changed 11 years ago by
- Status changed from needs_work to needs_review
- Work issues amusing typo bug deleted
comment:13 Changed 11 years ago by
- 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 11 years ago by
- Milestone changed from sage-4.7.1 to sage-4.7.2
comment:15 Changed 11 years ago by
- Dependencies set to #10334, #10335
- Description modified (diff)
comment:16 Changed 11 years ago by
- 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
comment:17 follow-up: ↓ 18 Changed 11 years ago by
- 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 11 years ago by
- 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 11 years ago by
- 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.
comment:20 follow-up: ↓ 21 Changed 11 years ago by
- 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 11 years ago by
- 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 11 years ago by
- Milestone changed from sage-4.7.2 to sage-pending
comment:23 Changed 11 years ago by
- Milestone changed from sage-pending to sage-4.7.2
comment:24 Changed 11 years ago by
- Description modified (diff)
comment:25 Changed 11 years ago by
- Merged in set to sage-4.7.2.alpha3
- Resolution set to fixed
- Status changed from positive_review to closed
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:
Also, some gripes: