New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Correct general brokenness of Farey symbols #11875
Comments
This comment has been minimized.
This comment has been minimized.
comment:2
It gets worse :-(
|
comment:3
Here's a case where it crashes completely:
|
comment:4
Some more testing suggests that the above crash occurs for any group of index > 2 containing the element
|
comment:7
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 ... |
Milestone sage-4.7.3 deleted |
This comment has been minimized.
This comment has been minimized.
Reviewer: David Loeffler |
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.
See this sage-devel thread.
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.
CC: @sagetrac-mraum @monien
Component: modular forms
Keywords: modular subgroup
Reviewer: David Loeffler
Issue created by migration from https://trac.sagemath.org/ticket/11875
The text was updated successfully, but these errors were encountered: