#17792 closed enhancement (fixed)
Word problem for FareySymbol
Reported by:  mmasdeu  Owned by:  

Priority:  major  Milestone:  sage6.7 
Component:  modular forms  Keywords:  farey symbol, SL2Z, word problem 
Cc:  xguitart, hmonien, cremona  Merged in:  
Authors:  Marc Masdeu  Reviewers:  Vincent Delecroix, John Cremona 
Report Upstream:  N/A  Work issues:  
Branch:  9083756 (Commits)  Commit:  
Dependencies:  Stopgaps: 
Description
This ticket implements the word problem for Farey symbols obtained for finite index subgroups of SL2Z.
Here is an example:
sage: F = Gamma0(30).farey_symbol() sage: gens = F.generators() sage: g = gens[3] * gens[10] * gens[8]**1 * gens[5] sage: g [628597 73008] [692130 80387] sage: wd = F.word_problem(g) sage: wd [4, 11, 9, 6]
While implementing it, I detected a bug in the LLT algorithm used, which was irrelevant with the existing functionality since some of the output of LLT algorithm was not used elsewhere.
Change History (25)
comment:1 Changed 4 years ago by
 Branch set to u/mmasdeu/17792farey_word_problem
 Commit set to 6d9c152c66ee11e73341e35ed1725a63d62b0cca
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
 Status changed from needs_review to needs_work
comment:3 Changed 4 years ago by
 Branch changed from u/mmasdeu/17792farey_word_problem to public/ticket/17792
 Commit changed from 6d9c152c66ee11e73341e35ed1725a63d62b0cca to 18e034409e8b62c81821e93132a11dd15d7fd432
comment:4 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:5 Changed 4 years ago by
 Milestone changed from sage6.5 to sage6.7
comment:6 followup: ↓ 7 Changed 4 years ago by
 Status changed from needs_review to needs_info
Why would you use a 1based answer while the Python is 0based. Couldn't you return a list of pairs (index, power)
. That would be much more convenient:
sage: wd = F.word_problem(g) sage: prod(F.gen(i)**j for i,j in wd) == g True
Vincent
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 4 years ago by
 Status changed from needs_info to needs_review
What you say makes a lot of sense, but the representation used here is quite standard in other implementations of finitely presented groups (AFAIK), and also in Sage. It's called Tietze representation, see http://www.sagemath.org/doc/reference/groups/sage/groups/finitely_presented.html. Since unfortunately 0 = 0, the 1based approach is essential here no matter how much you like 0based languages :).
Also, you can always do something like:
sage: wd = F.word_problem(g) sage: prod(F.gen(i1) if i > 0 else F.gen(i1)**1 for i in wd) == g True
Replying to vdelecroix:
Why would you use a 1based answer while the Python is 0based. Couldn't you return a list of pairs
(index, power)
. That would be much more convenient:sage: wd = F.word_problem(g) sage: prod(F.gen(i)**j for i,j in wd) == g TrueVincent
comment:8 in reply to: ↑ 7 ; followup: ↓ 9 Changed 4 years ago by
Replying to mmasdeu:
What you say makes a lot of sense, but the representation used here is quite standard in other implementations of finitely presented groups (AFAIK), and also in Sage. It's called Tietze representation, see http://www.sagemath.org/doc/reference/groups/sage/groups/finitely_presented.html. Since unfortunately 0 = 0, the 1based approach is essential here no matter how much you like 0based languages :).
Quoting Sage in order to prove that you are right is wrong ;) This Tietze representation is AFAIK something internal to GAP system (which is 1based). IMHO The fact that we used it as a non hidden attribute in free group is wrong. I did not find any mathematical reference mentioning "Tietze representation".
When somebody calls "word problem" he/she is even expecting a list of generators! Using the (possibly more compact) list of (gen, power)
is fine. Replacing gen
with its index is already a little bit of a hack. Replacing gen
with its index plus one is too much for calling it word_problem
. IMHO, the best would be a Factorization
object
sage: sage: F.<x,y> = FreeGroup() sage: f = Factorization([(x,2), (y,3), (x,1), (y,1)], sort=False) sage: f x^2 * y^3 * x * y sage: for i,j in f: ....: print i,j x 2 y 3 x 1 y 1
For matrices, the representation is ugly, but this can be easily fixed to be something like
sage: m1 = SL2Z([1,1,0,1]) sage: m2 = SL2Z([1,0,1,1]) sage: f = Factorization([(m1,2),(m2,3),(m1,2)], sort=False) sage: f # this is currently ugly [1 1]^2 * [1 0]^3 * [1 1]^2 [0 1] [1 1] [0 1] sage: prod(f) # this does work [5 8] [3 5]
I would be happy to fix the Factorization._repr_
if you like this solution.
Also, you can always do something like:
sage: wd = F.word_problem(g) sage: prod(F.gen(i1) if i > 0 else F.gen(i1)**1 for i in wd) == g True
Very elegant and very natural!
Vincent
comment:9 in reply to: ↑ 8 ; followup: ↓ 10 Changed 4 years ago by
Replying to vdelecroix:
Quoting Sage in order to prove that you are right is wrong ;) This Tietze representation is AFAIK something internal to GAP system (which is 1based). IMHO The fact that we used it as a non hidden attribute in free group is wrong. I did not find any mathematical reference mentioning "Tietze representation".
Both GAP and Magma use this representation (yes, they are both are 1based, also). In any case, converting back and forth consists of two one liners:
sage: gapway = [sgn(a)*(i + 1) for i,a in yourway for _ in range(abs(a))] sage: yourway = [(a1,len(list(g))) if a > 0 else (a1,len(list(g))) for a,g in groupby(gapway)]
When somebody calls "word problem" he/she is even expecting a list of generators! Using > the (possibly more compact) list of
(gen, power)
is fine. Replacinggen
with its index is already a little bit of a hack.
I am not so sure about this. Magma users get a "Tietze" list when they do the word problem for (say) units of quaternion orders. It is the one that comes out naturally out of any kind of "reduction" algorithm (like the one done in Farey symbols) and it might be good for input into other functions, so I would advocate for avoiding the extra processing.
A list of the type (gen,power) is unlikely to be more compact as soon as you have more than two generators, also.
I like your Factorization alternative, but I see two problems with it:
 Again, the user might want the more "raw" data, which we threw away.
 Suppose you have a group homomorphism defined by the images of the generators, which you stored in a list. How would you evaluate this homomorphism on a given group element? Well, you call the word_problem function, and then you still need to keep doing linear searches on your list of generators to figure out their index. This information was known to the
word_problem
method and you just threw it away...
I would be happy to fix the
Factorization._repr_
if you like this solution.
What about having a word_problem
method and a factor
method? The first one can be as it is now, the factor
could output a Factorization
object exactly like you suggest, which would be good for visualizing but maybe not so much for programming.
Very elegant and very natural!
I do agree ;).
comment:10 in reply to: ↑ 9 Changed 4 years ago by
Replying to mmasdeu:
Replying to vdelecroix:
Definitely, it would be good to have several output forms available. Though I do not agree on the way it has to be. First of all, I think that any function that is accessible by user (i.e. not starting with a _
and with default options) should be 0based. Moreover, if you want something useful to program morphisms, it would be better if 0based, isn't it?
From the name word_problem
I would expect a function that gives me precisely the Factorization that I proposed. If you want a more raw level function, which is useful, it would better be .word_problem(raw=True)
or ._as_prod_of_gens()
. The name factor
is not common (or please give a reference) and is moreover used for elements not parents
sage: 18.factor() 2 * 3^2 sage: ZZ.factor(18) ... AttributeError
I would keep factor
for factorization over PID or possibly as an alias for .word_problem
.
Answering your remark for 0based to 1based, I know that these are one liners and I know how to do. But
 it is additional code
 the code is ugly
 it can be avoided
Note that we interface both pari (the library) and libgap which are 1based... but
sage: p = pari("[1,2,3]") sage: p[1] 2 sage: p = libgap.eval("[1,2,3]") sage: p[1] 2
versus
GP/PARI CALCULATOR Version 2.8.0 ? l = [1,2,3]; ? l[1] %4 = 1
and
GAP, Version 4.7.7 gap> l := [1,2,3];; gap> l[1]; 1
Why is that? Because it is natural as we are using Python (and sometimes C)!
Vincent
comment:11 Changed 4 years ago by
Alternatively, for raw data you can use 1
for the inverse of 0
. But then, please make sure that the following would work
sage: F.<x,y> = FreeGroup() sage: F.gen(1) x^1 sage: F.gen(2) y^1
I do not find it very elegant though.
comment:12 Changed 4 years ago by
The notation should be consistent with the one used for arithgroup_perm. Either change both or make it consistent with arithgroup_perm. One reason why I did not advertise the functionality in the FareySymbol? was that the output of the word problem is that it is inconsistent with the output of sl2z_word_problem ... . Probably one should replace this as well but I would check the timing before removing that part.
comment:13 Changed 4 years ago by
 Cc cremona added
I don't really think this should be dragged on too much, but here is another example of how Sage works which contradicts some of the examples above:
sage: F = FreeGroup(2) sage: F Free Group on generators {x0, x1} sage: F([1]) x0
I agree though with the above comment that it should be consistent with sl2z_word_problem. Maybe a flag in the word_problem
method is a nearlyoptimal solution...
comment:14 Changed 4 years ago by
I agreed with Marc to take a look at this ticket, and now I have done so I am almost regretting it! We surely all agree that the functionality exposed here is something we definitely all want to have aceesible to Sage users. The only issues are (1) whether to use 1based or 0based numbering for the generator indices; and (2) whether the word_problem / factorization function should return the actual generators as matrices, or their indices.
Is that a fiar summary of where we are so far?
In reply to Marc's worry about having to do a lot of linear searches to find out which generator a given generator is, it would be possible to have a dict of { gens[i]:i } pairs instead.
There could be two options to the word_problem function. One could return a list of (gen, exponent) pairs where gen is an actual matrix. One could return a list of (index, exponent) pairs. The only option where 0basing causes difficulties is where what is returned is a simple list of signed indices where +i means the i'th gen while i means its inverse (and i=0 is not allowed). To me this looks like a technical internal representation which need not be exposed to the user.
I am only (so far) trying to clarify the remaining issues. Have I managed that?
comment:15 Changed 4 years ago by
Thank you John for the putting things in perspective. After looking at how FinitelyPresentedGroup?
and
FreeGroup?
work:
sage: F = FreeGroup(2) sage: a = F([1,2,1]); a x0*x1*x0 sage: a.syllables() ((x0, 1), (x1, 1), (x0, 1)) sage: a.Tietze() (1, 2, 1)
I think that the best alternative is to provide three methods: Tietze
,
syllables
, and
word_problem
. The outputs would be respectively a tuple of integers, a tuple of pairs of integers, and a tuple of pairs (gen,exp) as has been suggested. The documentation will refer to each other, and Tietze will be cached and used by the other two. This will make the outputs compatible with what already exists in Sage.
Please let me know if that seems a reasonable solution and I will implement it.
comment:16 Changed 4 years ago by
That sounds very reasonable to me. Just to make sure of the details:
Tietze  should probably no be capitalised, and returns a list of signed nonzero integers referring to indices of generators based at 1;
syllables  the first integer in each pair is a generator index, based at 0 or 1?
word_problem  no indices are returned so no ambiguity.
I feel that a group theorist should be involved here, so after you have implemented this we could perhaps ask (a friendly) one. For the last function, it seems odd to me to call a function "word_problem" when the function *solves* the word probem!
comment:17 Changed 4 years ago by
 Branch changed from public/ticket/17792 to u/mmasdeu/17792fareywordproblem
 Commit changed from 18e034409e8b62c81821e93132a11dd15d7fd432 to 3de10d68173dc99937c52af0cc5df5b8e2b2017a
comment:18 Changed 4 years ago by
I have implemented what I suggested (with tietze not capitalized, even if this clashes with another use in Sage).
If I see a friendly senior computational number theorist around I will ask what he thinks of the solution we have found. For now, I set the ticket to needsreview.
Thank you all for the constructive comments!
comment:19 Changed 4 years ago by
 Status changed from needs_review to needs_work
Hello,
When you construct a tuple, there is no need to construct a list first! You can replace
tuple([X for Y in Z])
by
tuple(X for Y in Z)
I actually do not like so much the fact the three methods do actually exactly the same job and are called differently... Why not adding an argument to tietze
or word_problem
to choose the output type? Can be
"standard"
: just with1,2,3,...
and1,2,3,...
as it was (the currenttietze
)"gens_index"
: as pairs(i,+1)
or(i,1)
wherei
is the generator (the currentsyllabes
)"gens"
: as pairs(m,+1)
or(m,1)
wherem
is one of the generator (the current `word_problem).
In the case of word_problem
above wouldn't it be better to output a list of matrices (that can be either a generator or inverse of a generator)?
The public method get_pmats_to_gens
is not appropriate if it has to be public. The names must be complete: paring_matrices_to_gens_table
or something similar. Again, why is this method 1
based if there gens
in the name? Call it pairing_matrices_to_tietze_index
but do not mention gens
if it has to be 1
based.
Still in get_pmats_to_gens
, why not using cached_method
if you need to cache the result? By the way, is there really a need to make it cached?
Still in get_pmats_to_gens
, this try/except
blocks are ugly. Moreover, doing l.index
is a linear search through a list. So I would rather do
gens_dict = {g:i for i,g in enumerate(self.generators())} ans = [] for pm in self.pairing_matrices(): if pm in gens_dict: ans.append(gens_dict[pm]) continue m = pm if m in gens_dict: ans.append(gens_dict[m]) continue m = ~pm if m in gens_dict: ans.append(gens_dict[m]) continue m = m if m in gens_dict: ans.append(gens_dict[m]) continue raise RuntimeError("this should not happen, right?") return ans
Vincent
comment:20 Changed 4 years ago by
 Commit changed from 3de10d68173dc99937c52af0cc5df5b8e2b2017a to 908375633e44d67fa3991bf0f7c4e2cc381dbef1
Branch pushed to git repo; I updated commit sha1. New commits:
9083756  Trac #17792: Modified according to suggestions of vdelecroix.

comment:21 followup: ↓ 22 Changed 4 years ago by
 Status changed from needs_work to needs_review
I have just pushed a new version. Some comments:
1) In the timings I had, it look like it was faster to create the tuple out of the list instead of the generator expression. But I have changed it as you proposed.
2) I have reverted back to one single function as you proposed. The output is as both John and myself had decided: the exponents can be any nonzero integer, not just +1 or 1. I have applications for this kind of output and so may have other potential users.
3) I use now cached_method instead manual caching. I changed the try/except blocks with a more elegant solution (I think it is better than what you suggest which also doesn't work because matrices in SL2Z do not have a unary "", since it uses half the queries in a dictionary).
I do hope that this is close to finished!
comment:22 in reply to: ↑ 21 Changed 4 years ago by
Hello,
Replying to mmasdeu:
1) In the timings I had, it look like it was faster to create the tuple out of the list instead of the generator expression. But I have changed it as you proposed.
Looks strange! I do not understand why [i for i in l]
should be faster than tuple(i for i in l)
...
2) I have reverted back to one single function as you proposed. The output is as both John and myself had decided: the exponents can be any nonzero integer, not just +1 or 1. I have applications for this kind of output and so may have other potential users.
Thanks.
3) I use now cached_method instead manual caching. I changed the try/except blocks with a more elegant solution (I think it is better than what you suggest which also doesn't work because matrices in SL2Z do not have a unary "", since it uses half the queries in a dictionary).
Nice. Do you know why SL2Z matrices do not have a unary 
?
Vincent
comment:23 Changed 4 years ago by
 Reviewers set to Vincent Delacroix, John Cremona
 Status changed from needs_review to positive_review
I am happy with this now, and think we should accept it, leaving further issues to followups.
comment:24 Changed 4 years ago by
 Branch changed from u/mmasdeu/17792fareywordproblem to 908375633e44d67fa3991bf0f7c4e2cc381dbef1
 Resolution set to fixed
 Status changed from positive_review to closed
comment:25 Changed 4 years ago by
 Commit 908375633e44d67fa3991bf0f7c4e2cc381dbef1 deleted
 Reviewers changed from Vincent Delacroix, John Cremona to Vincent Delecroix, John Cremona
Doc does not build, see patchbot report.