Opened 10 years ago
Closed 9 years ago
#11875 closed defect (duplicate)
Correct general brokenness of Farey symbols
Reported by: | davidloeffler | Owned by: | craigcitro |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | modular forms | Keywords: | modular subgroup |
Cc: | mraum, hmonien | Merged in: | |
Authors: | Reviewers: | David Loeffler | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
UPDATE: Subsequent work at #11709 has fixed the problems with Farey symbols, so this ticket can be closed as fixed when that is merged.
The new Farey symbols code from #11709 needs some serious work before it can be allowed into a production release of Sage.
As an absolute minimum, we should:
- Remove the file
sage.modular.arithgroup.noncongruence_example
(which makes outrageously false mathematical statements in its docstrings -- the "example noncongruence subgroup" is actually the congruence subgroupGammaH(8, [5])
-- and is implemented in a stupidly broken way with no doctests and no usable methods whatsoever).
- Bring doctest coverage for the Python and Cython files in
sage/modular/arithgroup/
back up to 100%, and make sure there areloads()
/dumps()
tests for all the classes.
- Make sure that the Farey symbol code works with all of the subclasses of
ArithmeticSubgroup
and add doctests to prove it.
- Add a warning in the documentation that commands like "index" and "generators" in Farey symbol code return the index, generators etc. of the image of the group in PSL2Z, whereas Sage's general design is to work with subgroups of SL2Z.
Change History (13)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
Here's a case where it crashes completely:
---------------------------------------------------------------------- | Sage Version 4.7.2.alpha3, Release Date: 2011-09-28 | | Type notebook() for the GUI, and license() for information. | ---------------------------------------------------------------------- ********************************************************************** * * * Warning: this is a prerelease version, and it may be unstable. * * * ********************************************************************** sage: G = ArithmeticSubgroup_Permutation(L = "(1,2,3)", R = "(1,2,4)") sage: FareySymbol(G) terminate called after throwing an instance of 'std::string' --------------------------------------------------------------------------- RuntimeError Traceback (most recent call last) /storage/masiao/sage-4.7.2.alpha3/devel/sage-main/sage/modular/arithgroup/<ipython console> in <module>() /storage/masiao/sage-4.7.2.alpha3/local/lib/python2.6/site-packages/sage/modular/arithgroup/farey_symbol.so in sage.modular.arithgroup.farey_symbol.Farey.__cinit__ (sage/modular/arithgroup/farey_symbol.cpp:1993)() 191 cdef int p 192 if hasattr(group, "level"): p=group.level() --> 193 sig_on() 194 if group == SL2Z: 195 self.this_ptr = new cpp_farey() RuntimeError: Aborted
comment:4 Changed 10 years ago by
Some more testing suggests that the above crash occurs for any group of index > 2 containing the element
[-1 1] [-1 0].
comment:5 Changed 10 years ago by
- Cc mraum added
comment:6 Changed 10 years ago by
- Milestone changed from sage-4.7.2 to sage-4.7.3
- Priority changed from blocker to major
comment:7 Changed 10 years ago by
- Cc hmonien added
Hi all,
the structural data of an arithmetic subgroup, that one needs to compute for the modular symbols "integrality algorithm", is more or less the same than what one needs for Farey symbols (for some discussion of the former, see http://groups.google.com/group/sage-nt/browse_thread/thread/a653b4498fa5cb67#).
FWIW, I have put some "needs work" code for that (pure Python, building upon the existing ArithmeticSubgroup? framework in Sage) at trac #10857.
It needs quite some polishing (especially a renaming and a complete reordering of the functions), but works for all arithmetic subgroups, features examples of non-congruence subgroups (taken elsewhere from Sage), and for certain classes of groups (Gamma, Gamma_1, Gamma_0) there are special algorithms that compute this structural data in linear time (w.r.t. to the subgroup index in SL2Z), not quadratic time (which is the generic case).
Explicitly, on my 2 GHz machine, the code there computed generators and coset representatives for Gamma(64) in about 17 seconds and for Gamma(128) in about 478 seconds.
Since then, I didn't find the time to continue the work on that code (if I had free time to spare for Sage, I'd rather review #5048, sigh), or else I would have finished e.g. the dummy "def z_farey_symbol_data(self):" there ...
My proposal for continuing with #11709 and this #11875 here, would be to separate off the "plotting" parts of #11709 (which I dearly would like to have ready in Sage), which seem to be uncontroversial, and get them into Sage.
Having done that, and Hartmut and Martin still being "on fire", the next step might be to do the reality check, whether using C++ for computing the Farey symbol structural data really gives the speed advantage, worth all the trouble not coding these algorithms directly in Python (or Cython).
Please don't get me wrong, you have my greatest respect for executing the addition of a new cpp file to the Sage library! There are probably lots of places in the Sage development documentation that could benefit from this experience, think not only of the last necessary patches from Leif, but also all this "module_list.py" stuff, let alone the .rst documentation (kudos to you for including pictures!!), and what not ...
comment:9 Changed 9 years ago by
- Milestone set to sage-5.0
- Status changed from new to needs_review
comment:10 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:11 Changed 9 years ago by
- Description modified (diff)
comment:12 Changed 9 years ago by
- Milestone changed from sage-5.0 to sage-duplicate/invalid/wontfix
- Reviewers set to David Loeffler
comment:13 Changed 9 years ago by
- Resolution set to duplicate
- Status changed from positive_review to closed
It gets worse :-(
Gamma_2
in the article by Kurth and Long) this code returns the wrong Farey symbol (corresponding to another completely different subgroup of index 6).