FareySymbol

[monien]

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. attachment: trac-11709_farey_symbol-sage-5.0-without_png.patch
2. attachment: trac_11709-review.patch

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

Depends on #5048
Depends on #11601

CC: @vbraun

Component: modular forms

Keywords: Farey symbol

Author: Hartmut Monien

Reviewer: Martin Raum, Leif Leonhardy, David Loeffler

Merged: sage-5.0.beta9

Issue created by migration from https://trac.sagemath.org/ticket/11709

[sagetrac-mraum]

comment:3

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

[sagetrac-mraum]

Reviewer: Martin Raum

[sagetrac-mraum]

comment:5

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.

[monien]

Attachment: noncongruence_example.sage.gz

[monien]

comment:6

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.

[sagetrac-mraum]

comment:7

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.

[monien]

comment:8

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.

[sagetrac-mraum]

comment:9

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.

[monien]

comment:10

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.

[monien]

comment:11

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.

[monien]

Attachment: trac_11709_farey_symbol.patch.gz

Attachment: fun_gamma_3.png

[monien]

Attachment: fun_gamma0_11.png

[monien]

Attachment: fun_gamma0_23.png

[monien]

comment:12

Attachment: pairing.png

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.

[sagetrac-mraum]

comment:13

Attachment: trac-11709_farey_symbol-v4.patch.gz

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.

[monien]

comment:14

Attachment: trac-11709_farey_symbol.patch.gz

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

[sagetrac-mraum]

comment:15

Attachment: trac-11709_farey_symbol-v6.patch.gz

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

[loefflerd]

comment:33

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!

[sagetrac-mraum]

comment:34

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!

[loefflerd]

comment:35

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.

[loefflerd]

comment:36

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?

[loefflerd]

comment:37

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.

[loefflerd]

comment:38

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

(for the patchbot)

[loefflerd]

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

[loefflerd]

Attachment: trac-11709_farey_symbol-sage-5.0.patch.gz

IGNORE THIS -- uploaded by mistake

[loefflerd]

Attachment: trac_11709-review.2.patch.gz

Attachment: trac_11709-review.patch.gz

Reviewer patch; apply over the rebased v5.0 patch

[loefflerd]

comment:39

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.

[loefflerd]

Dependencies: #5048, #11601

[sagetrac-mraum]

comment:41

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.

[sagetrac-mraum]

comment:42

Attachment: trac-11709_farey_symbol-sage-5.0-without_png.patch.gz

[loefflerd]

comment:43

OK, I can live with that.

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

[loefflerd]

comment:44

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?

[monien]

comment:45

Replying to @loefflerd:

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.

[loefflerd]

comment:46

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!

[monien]

comment:47

Okay then - done!

[jdemeyer]

Merged: sage-5.0.beta9