Implementation of Farey symbols

[vdelecroix]

Hello,

There is a nice code for computing Farey symbols of arithmetic groups
(see [1] and [2]). My question is about implementation. There are
basically two ways of describing a subgroup of SL(2,Z). Either by
providing a membership test (ie a __contains__ method) or by giving a
Shreier graph for some system of generators. The former implementation
is used for congruence subgroups while the latter provides a way to
describe any arithmetic group (see
sage.modular.arithgroup.arithgroup_perm).

The current implementation of Farey symbols relies on membership test
which costs a lot for a group given by its Shreier graph (we first
decompose the matrix in standard generators of SL(2,Z) via continued
fraction and then test if the word is a loop in the Shreier graph). My
question is whether it is possible to adapt the current implementation
of the computation of Farey symbols to the case of a group given by
its Shreier graph ?

Best,
Vincent

[1] http://trac.sagemath.org/sage_trac/ticket/11709
[2] http://trac.sagemath.org/sage_trac/ticket/11875

[Georg S. Weber]

 Hi,

as usual my apoplogies for not having so really much time to work on Sage lately (for quite some time now, to be honest).
I hadn't heard of the terminus "Schreier Graph" before, but I think that the Wikipedia article "http://en.wikipedia.org/wiki/Schreier_coset_graph"
hits the mark.

Using these terms (and some "hand-waving"), I'll to give an answer to the question of Vincent.

So one has given some finite index (say "n") subgroup Gamma of SL2Z by an explicit enumeration of its cosets
("right" cosets?! I always mess uo these right/left notions ...);
where we suppose that the number of the coset representing Gamma itself is "1" (or at least known);
together with a finite number of generators of SL2Z
(two generators suffice, but there are several "canonical" choices),
and how these act as permutations on the n cosets.

The first step would be to translate this to a permutation presentation (on the same set, with the same numbering)
of S := SL2Z([0, -1, 1, 0]) and Z := SL2Z([0, -1, 1, -1]); these two matrices (also) generate SL2Z.

The second step would be to re-enumerate the cosets in a certain "balanced" way. Loooking at the Schreier graph corresponding to S and Z, this "balanced" just means that one runs through the vertices in such a way that those with least distance (in the graph-theoretic sene) to the coset "1" (representing Gamma itself) come first --- along the way, one stores for each coset its distance to "1".

My observation that Hartmut mentioned is that in the congruence subgroup case, one often (e.g. in the Gamma0(N), Gamma(1), Gamma(N) cases) can loop through each of the sets vertices of equal distance to "1" in such a way, that each step only needs O(1) and not O(n). But having a pre-existing "complete" S-Z-permutation presentation already available (and in this step "only" having to "balance" the enumeration), this observation seems to hold, too!

As soon one has produced such a balanced S-Z-permutation presentation, one can read off more or less immediately the Farey symbol, as well as the (some) fundamental domain of Gamma. Up to doing the details of the algorithm right, exactly those S-transpositions where both cosets have equal distance to "1", are non-degenerate gluing edges of the respective fundamental domain/number-labelled pairs of edges of the Farey symbol, each such pair adding one generator (of infinite order) of Gamma. The degenerate 2-cycles and 3-cycles (corresponding to "edges glued to themselves") also add one generator each (of finite order), i.e. one "black" resp. "white" labelled edge to the Farey symbols.

To get the values of the cusps and the correct sequential ordering (of the edges) of the Farey symbol, one has simply to run once through the "border edges" (of the fundamental domain), as a third step.

All in all, each of theses three steps seems O(n) to me, which definitely sounds better than having to go the way of membership testing (possibly in some inner loop of the algorithm, which would give an O(n^2) estimation).

This idea of "balancing" is already existing in the algorithmical approach I posted at http://trac.sagemath.org/sage_trac/ticket/10857 one and a half years ago --- but as mentioned already, you won't find the notion of "Schreier graph" in my comments there (rather some "dual" graph, where the cosets are not the vertices, but the edges, and the vertices representing either S-relations (2-cycles, if non-degenerate) or Z-relations (3-cycles, if non-degenerate) --- I hope this attempt of an explanation is helpful, if you look at the code there).

One other advantage of such "balanced" (rather: "S-Z-balanced") enumerations of cosets is, that it allows for the notion of "(S-Z-)balanced" sets of generators. I think that this point of view might allow for an algorithm that, given some arbitrary finite set of matrices of SL2Z, produces as output a "balanced" (again finite) set of generators (of the subgroup of SL2Z generated by the given set of matrices), and along the way (in a finite total running time!) whether the subgroup of SL2Z generated by this set has finite index (or not), and if it is finite, the index; along with an "S-Z-balanced" permutation representation, and a Farey-Symbol (generalized to the case of "finitely-generated-but-of-inifinite-index" subgroups of SL2Z).
But *attention* I still have to produce some (any) code/rigorous proof to verify this claim, sorry.

So yes, the current state of "finitely generated supgroups of SL2Z (GL2Z ?!?)" handling in Sage definitely could be improved IMHO. As I first noted here (and elsewhere), I dearly would like to produce that code myself (Cythonized, and what not), but failed miserably up to now. (I managed instead to review some code of David Loeffler some time ago, but even for such reviews I didn't find the time recently. Sigh.)

So everyone please feel free to open up a further discussion thread on "sage-nt" (where this should belong to), and I do hope to be able to add some comments every now and then. (I have given up the hope to be able to personally meet some of you, at some Sage Days or so.)


Cheers,
Georg