FareySymbol

[hmonien]

FareySymbol is a fast implementation of the KFarey package for Sage.

The major changes done by me:

• created an object oriented coherent class interface

• implemented a C++ module with pyx interface

FareySymbol allows the calculation of properties of a general arithmetic subgroup. The use with the congruence subgroups Gamma0, Gamma1, GammaH is trivial. For a group not implemented in Sage, the "user" has to define a class with a __contains__(self, M) attribute which returns True or False depending on M being in the group or not.

The calculation of the generators, coset representation and genus of Gamma(32) takes 62.5 seconds on my laptop. Try this with Magma ... .

sage: time FareySymbol(Gamma(32))
FareySymbol(Congruence Subgroup Gamma(32))
Time: CPU 62.50 s, Wall: 62.52 s

---

Apply

1. trac-11709_farey_symbol-sage-5.0-without_png.patch
2. trac_11709-review.patch

When this ticket is merged, ticket #11875 can be closed as fixed.

[mraum]

That is great work! Not so many issues that I found; And really this is code of awesome readability.

The first major issue is the missing GPL header farey.cpp.

I will do the rest per line and file: farey.cpp: l.13 missing #include <algorithm> Did this really compile for you? That seems impossible. l.114 reverse the order of name and group (for consistency only). l.127 this is bad. Compare with l.114. The easiest will be to change the latter. l.147 change to = a[i]/b[i] - a[i-1]/b[i-1], since operator/ already constructs a new instance and hence it would be a wast to call the copy constructor. l.150 this is asking for trouble on Sun and other platforms. It would hurt to use int i, will it? l.154 add break; hereafter to make it a tiny bit faster. l.187 and l.188 use A = ... and B = ..., since again the copy constructor is not needed. l.203 like l.187f l.225 why don't you use throw like in l.260? l.264 move this directly behind the alternate version of paring_matrix, that is, l.247, to improve readability. l.290 and l.291 define one_half(1,2) and use this here. l.297 use one_half(1,2), which is a bit faster. l.314 again this is calling for trouble on Sun. Use int k? l.324 missing initialization c(paring.size(), 0);. l.426 delete this assertion? l.428 it is a shame that the compiler doesn't catch this, but again Sun won't like this. l.512 I'm not sure at all, but should this be NO, because already 1 represents a paired fraction? In that case you can remove the FREE label from the enum.

farey_symbols.pyx: l.5 the syntax is:

AUTHORS:

- Hartmut Monien (08 - 2011)

l.7 read C++. l.46 Why to use the underscore at the end of the line? l.50 Read G, because it is a mathematical symbol. l.61, l.191, l.214, and l.267 use Sequence(..., cr = True) to make the output more readable. l.103 use _repr_. l.109 sage: repr(FareySymbol?(Gamma0(23))) l.128, l.139, l.151, l.187, l.224, and l.281 missing full stop.

farey_symbol.h: You don't need this, but I think it would be best to use it to replace l.21ff in farey.cpp.

sl2z.hpp: l.25 and l.26 protected? otherwise it makes no sense to declare all the functions above as friend.

Tests: The tests are currently not sufficient to cover all cases the code treats. This the difference occures in farey.cpp,l.189ff, it would be sufficient to add tests like FareySymbol?(G). Please add tests for SL2Z, Gamma1(4) and GammaH(11, [2,7]) or any equivalent set of test cases.

I need to double check this agains Magma, and I will do this tomorrow. It would also be good to see, whether everything works fine on the Sun test cluster. I hope the patch bot will pick this up soon.

[mraum]

I verified this against Magma and everything is OK. While doing so, I noticed that the documentation of coset_reps should mention that you compute the left transversal.

I felt a bit pity that GammaH is currently not implemented in C++, and for this it is much slower. If you feel like it, please go ahead and implement it. Otherwise, we will open a follow up ticket, that describes this task.

[hmonien]

I have implemented the changes by Martin Raum - including the C++ version of GammaH.  I have added a number of doctests for SL2Z, Gamma1 and GammaH. 

The only undocumented feature is the possibility to define arbitrary subgroups of SL2Z by a helper class. I include an example "noncongruence_example.sage". How can that be doctested?

Otherwise the patch should be ready to go.

[mraum]

I will have a look at this soon.

Concerning the example class, I would change the description to something like "Simple example how to implement noncongruence groups for the FareySymbol? class."

Testing shouldn't be too difficult. In the class doc, test whether you can initialize the FareySymbols? and whether you can, say, compute the coset representatives. For all other methods just call it and verify the output. Definitely, by now, all functions that get into Sage need to be tested completely.

[hmonien]

Added an example for noncongruence groups in "noncongruence_example.py" (including a reference to a paper investigating this example - published 2010). Added a doctest of the noncongruence generators. 

[mraum]

With very minor changes, which I have done myself, this can get a positive review. There is only one thing, that I am sceptical about. For sl2z you changed the definition for *= and /=. I wonder why, because the old definition was correct and the new one seems not.

[hmonien]

Added a few checks for user code. The user subgroup is now check for a __contains__ member and if this member returns bool. Removed some unnecessary code: the rep member of farey_symbol etc.. Cleaned up the code for the special case of SL2Z which now gives the correct coset and generators.

Revised the SL2Z.hpp file: changed member function get_a(), get_b() ... to a(), b(), c(), ... . Is the definition of SL2Z *= and /= correct now?

Added two file sage/plot/hyperbolic_arc.py and sage/plot/hyperbolic_triangle.py for plots in the hyperbolic plane.

Added member fundamental_domain() to FareySymbol? which plots the fundamental domain. 

[hmonien]

Added hyperbolic_arc and hyperbolic_triangle to documentation in sage.plot. Fixed const in SL2Z.cpp. Pruned the documentation so that sage --docbuild --jsmath reference html actually works. I am still not happy with the treatment of linebreaks in the documentation ... . It would be nice to add at least one plot of a fundamental domain, i.e. Gamma0(23),  to the documentation. 

[hmonien]

The documentation for FareySymbol? is now seriously enhanced. It includes several figures which are not included in the patch (since it does not handle binary files) but included separately. The png files should go to the directory doc/en/reference/media/modular/arithgroup which of course has to be created. 

[mraum]

I have created a patch that incorporates the pictures. Btw. to create such a patch simply type

hg add *.png

in the corresponding directory. Then commit. Don't be irritated by the v4. I internally relabelled different versions of the patch, and I cannot overwrite your uploads.

I have changed some lines where you have put your name twice in the author section. It is common in Sage to put a list there, to provide the possibility to include further authors, which later might contribute.

The one thing that is irritating is the SL2Z case. Obviously, PSL is not a subgroup of SL, so it does not make sense to talk about indices. Also the index of SL2 in SL2, as a matter of fact, is 1. In the current implemntation generators() equals cosets(), which cannot be right. Am I missing anything, that you intent to implement?

Since you know provide the SL2 generators explicitly, I wonder why you don't use 0,1],[-1,0? and 1,1],[0,1?, which are the most common used generators. Clearly, your choice is perfectly possible; I just wonder.

[hmonien]

Changes as discussed. Hope for the best ... .

[mraum]

Yes, finally this work gets a positive review. The only change I made is to adapt the commit message to comply with the standards.

[leif]

Please leave the Dependencies field empty if the ticket doesn't depend on any other.

[leif]

Crucial six-character patch. Otherwise Sage won't build from scratch. Independent of the other patch; apply to the Sage library.

[leif]

Attached a reviewer patch such that building Sage from scratch will work.

[leif]

Apply on top of the other patch(es), to the Sage library.

[leif]

Attached another patch adding "# -*- coding: UTF-8 -*-", because one file contains non-ASCII characters, which leads to:

...
Updating modification times for the documentation...
sage -docbuild --update-mtimes reference html
...
Traceback (most recent call last):
...
    from farey_symbol import Farey as FareySymbol
  File "farey_symbol.pyx", line 42, in init sage.modular.arithgroup.farey_symbol (sage/modular/arithgroup/farey_symbol.cpp:4918)
  File ".../local/lib/python2.6/site-packages/sage/modular/arithgroup/noncongruence_example.py", line 35
SyntaxError: Non-ASCII character '\xe2' in file .../local/lib/python2.6/site-packages/sage/modular/arithgroup/noncongruence_example.py on line 36, but no encoding declared; see http://www.python.org/peps/pep-0263.html for details
...

[leif]

Follow-up ticket: #11875

[jdemeyer]

Milestone sage-4.7.3 deleted

[hmonien]

This patch replaces in one file all the previous patches

[hmonien]

Since many things have changed in 4.7.2 I have decided to lump everything in one new patch.

FareySymbol? has been checked for special cases (not implemented in the KFarey package) including the unique index two subgroup. It now handles gracefully subgroups which contain SL2Z([-1, 1, -1, 0]). 

The drawing of the fundamental domain has been changed slightly. The coloring of the pairing has been changed to include the first and last side.

The current algorithm for calculating the FareySymbol? is O(n^2) where n is the index of the subgroup which is the general case. This could be improved to O(n) for Gamma0, Gamma1 and Gamma as Georg Weber pointed out. The current algorithm runs for about a second to calculate all properties of the FareySymbol? for Gamma(16) with index 1536. This is probably satisfactory at the moment (and still much faster than Magma). 

The documentation has been corrected.

[davidloeffler]

I tried installing trac-11709_farey_symbol-sage-4.8.patch this on the latest Sage beta (5.0.beta6), which brought up a couple of minor issues:

(1) There was a conflict in sage/modular/all.py (easily fixable, caused by #11601 merged in 5.0.beta1). Other than that, the patch applies OK.

(2) Building gave a curious warning:

----------------------------------------------------------
sage: Building and installing modified Sage library files.


Installing c_lib
scons: `install' is up to date.
Updating Cython code....
Building modified file sage/modular/arithgroup/farey_symbol.pyx.
setup.py:650: UserWarning: could not find dependency <string> included in /storage/masiao/sage-5.0.beta6/local/lib/python/site-packages/Cython/Includes/libcpp/string.pxd. I will assume it is a system C/C++ header.
  warnings.warn(msg+' I will assume it is a system C/C++ header.')
setup.py:650: UserWarning: could not find dependency <vector> included in /storage/masiao/sage-5.0.beta6/local/lib/python/site-packages/Cython/Includes/libcpp/vector.pxd. I will assume it is a system C/C++ header.
  warnings.warn(msg+' I will assume it is a system C/C++ header.')
Executing 1 command (using 1 thread)
python `which cython` --cplus --old-style-globals --disable-function-redefinition --embed-positions --directive cdivision=True,autotestdict=False,fast_getattr=True -I/storage/masiao/sage-5.0.beta6/devel/sage-main -o sage/modular/arithgroup/farey_symbol.cpp sage/modular/arithgroup/farey_symbol.pyx
sage/modular/arithgroup/farey_symbol.pyx --> /storage/masiao/sage-5.0.beta6/local/lib/python2.7/site-packages//sage/modular/arithgroup/farey_symbol.pyx
Time to execute 1 command: 3.33421301842 seconds
Finished compiling Cython code (time = 5.61644482613 seconds)

Other than that, it looks pretty good -- thanks for your work on this! I'm running the test suite now. If everything goes OK I'll upload my rebase of the patch.

[davidloeffler]

This bothers me a bit:

sage: all([x in Gamma1(4) for x in FareySymbol(Gamma1(4)).generators()])
False

If G is odd, the generators that get returned are arbitrary liftings of generators of the projective image of G, so they won't generally be in G.

Also, I don't like this:

sage: FareySymbol(Gamma0(4)).generators()
[[1 1]
[0 1], [ 3 -1]
[ 4 -1]]

These elements do *not* generate Gamma0(4); they generate an index 2 odd subgroup of Gamma0(4) (which one can check is congruence of level 8, using the functions added by ticket #11601).

I'd like to request the following changes:

• Make sure the "generators" are really in G when G is odd.

• If G is even and has no torsion, pad the list of generators with -1. Otherwise, make sure representatives of the torsion generators are chosen so the subgroup they generate contains -1.

• I'd also suggest we rewire the "generators" method of the top-level arithmetic subgroup class to use Hartmut's new code by default, with the old code as an optional fall-back.

• While we're at it, it would be nice to have a "farey_symbol" method of arithmetic subgroups as an alternative to the constructor function.

[davidloeffler]

Sorry, "if G is even and has no torsion" is nonsense -- I meant "if G is even and has no elliptic points", i.e.~if the projective image of G is torsionfree.

[hmonien]

I added some code to "init_generators" to fix both problems. I agree that it would be good to rewire the generators of the top-level arithmetic subgroup class. It would be even better to implement Webers O(n) algorithm for generators of the congruence subgroups to "farey.cpp" (requires some work).

[schilly]

My concern on the mailing list was that there are binary files (png images) in the patch. There should never be any binary files included ever. Including the plot commands itself would be nice, though.

[hmonien]

Replying to schilly:

My concern on the mailing list was that there are binary files (png images) in the patch. There should never be any binary files included ever. Including the plot commands itself would be nice, though.

If there is a way to include svg's in the documentation let me know. I would be happy to change png -> svg.

[schilly]

Replying to hmonien:

If there is a way to include svg's in the documentation let me know. I would be happy to change png -> svg.

well, i like the idea, but i don't think producing the latex/pdf output via sphinx is able to render this. apart from that you can start a new thread on sage-devel on that, curious what others think about this.

[davidloeffler]

I've uploaded a new patch which is almost 100% identical to Hartmut's but with a tiny change so it applies to the current v5.0 beta; and a reviewer patch, which makes changes to the existing classes so generators calls Hartmut's code by default (while still falling back to the old code when necessary).

The only significant change I've made concerns the output of "generators" for even subgroups with elliptic points of order 3 but not of order 2. Rather than adding -1 on to the end of the generators list, I've modified the code so it returns generators of order 6 for the odd self-paired sides; so now the list of generators is genuinely minimal. I also had to tinker with the signal handling slightly to get rid of a tedious crash when doctesting.

If Hartmut or anyone else is willing to sign off on my patch, I think this is ready to go in.

[davidloeffler]

Sorry, "(while still falling back to the old code when necessary)" should have been "(while having an option to fall back to the old code)" -- it's never necessary!

[mraum]

I can have a look at the patch on the week end or next week. Anyway I was going to make a comment on the generators, which I haven't done for lake of time: I am absolutely sure that the Farey symbols should correspond to PSL(2, ZZ). Any work on the generators, like the issues that you, David, pointed out before, should be dealt with in the class for arithmetic groups.

I guess from your comment, that you did this in part. But in my opinion this should be a separate ticket. There is a lot of work to be done.

Btw. if anybody has time to sign this off before the weekend: Go ahead!

[davidloeffler]

I just realised that the patch breaks a line in William's old 2008 Bordeaux slides which are included as part of the documentation. The slides complain about Farey symbols not being implemented, so I've added a comment explaining that they are now implemented and changed the doctest.

[davidloeffler]

Wait a minute, here's a bug.

sage: G = ArithmeticSubgroup_Permutation(S2="(1,2,3,4)",S3="(1,3)(2,4)")
sage: gens = FareySymbol(G).generators(); [x.matrix() for x in gens]
[
[1 2]  [ 0 -1]  [ 1 -1]
[0 1], [ 1 -1], [ 1  0]
]
sage: gens[0] in G
False

This has the disastrous consequence that G.is_congruence() returns False, even though G is actually congruence (of level 4).

For some reason, the mechanism that checks whether the potential generator is actually in the group, and if not flips its sign, doesn't seem to be working for this particular group G. It seems to work for all the other ones I've tried though. Hartmut: any thoughts?

[davidloeffler]

I found out what was wrong. This G is a lifting to SL2Z of the unique index 2 subgroup of PL2Z, which is handled separately as a special case in the code. The updated reviewer patch I've just uploaded fixes this, so these two special cases are both handled correctly.

[davidloeffler]

Apply trac-11709_farey_symbol-sage-5.0.patch, trac_11709-review.patch

(for the patchbot)

[davidloeffler]

Hartmut's patch but rebased to 5.0 and with trailing whitespace removed

[davidloeffler]

IGNORE THIS -- uploaded by mistake

[davidloeffler]

Reviewer patch; apply over the rebased v5.0 patch

[davidloeffler]

Apply trac-11709_farey_symbol-sage-5.0.patch, trac_11709-review.patch

(for the patchbot).

Sorry for the noise, but a patchbot run highlighted a failure in ell_rational_field.py (a doctest that relied, for some absurd reason, on a specific matrix being the 5th generator of Gamma0(15)), and also it was complaining about trailing whitespace in the patch, so I dealt with that.

[mraum]

Everything is OK with the changes. I should remark that I am not so happy with including -I as a generator in case the SL(2,Z) subgroup passed to Farey symbols makes this necessary. To me Farey symbols have to to with SL(2, Z) as much as SL(2, Z) has to do with its metaplectic cover. But since -I in PSL is just I, it is not wrong. I just think it's not very clean.

I made one single change. Following the discussion at sage-devel, I removed all fundamental domain pictures. I kept the one for pairings, though, because it seems necessary to understand what is meant by [(0,5), ...].

If you are OK with this, please give this a positive review.

[davidloeffler]

OK, I can live with that.

Apply trac-11709_farey_symbol-sage-5.0-without_png.patch, trac_11709-review.patch

[davidloeffler]

The mess you get when you print a list of SL2Z elements, as in many of the doctests here, bothered me enough that I found a fix: see #12658. Any takers for a review?

[hmonien]

Replying to davidloeffler:

The mess you get when you print a list of SL2Z elements, as in many of the doctests here, bothered me enough that I found a fix: see #12658. Any takers for a review?

Good idea!

Just a comment on removing the figures. Any of the png files took approximately 8k. If one wants to get rid of binary files then one simple way would be to have figures in svg which costs about 32k for each file + a pdf file (again binary and 8k) for creating the latex documentation. I think the additional storage needed for the figures is minimal and in fact I would like to see more of them in the documentation.

[davidloeffler]

You may be right, but let's have a separate ticket for that: I don't want the code here to wait any longer before it goes in!

[hmonien]

Okay then - done!