Correct general brokenness of Farey symbols

[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 subgroup GammaH(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 are loads()/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.

[David Loeffler]

It gets worse :-(

• For SL2Z, the code returns a malformed Farey symbol with too many vertices (there are 2 rational vertices, so the side-pairing data should be a list of length 3, but it has only 2 entries). This can be fixed by removing the entry "1" from the Farey symbol.

• For the unique index 2 subgroup of PSL2Z (denoted by 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).

[David Loeffler]

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

[David Loeffler]

Some more testing suggests that the above crash occurs for any group of index > 2 containing the element

[-1 1]
[-1 0].

[Georg S. Weber]

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

[Jeroen Demeyer]

Milestone sage-4.7.3 deleted