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
--
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
