Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#17792 closed enhancement (fixed)

Word problem for FareySymbol

Reported by: mmasdeu Owned by:
Priority: major Milestone: sage-6.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 mmasdeu

  • Branch set to u/mmasdeu/17792-farey_word_problem
  • Commit set to 6d9c152c66ee11e73341e35ed1725a63d62b0cca
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

Doc does not build, see patchbot report.

Error building the documentation.
Traceback (most recent call last):
OSError: [arithgrou] docstring of
sage.modular.arithgroup.farey_symbol.Farey.get_pmats_to_gens:11:
WARNING: Literal block expected; none found.

comment:3 Changed 4 years ago by chapoton

  • Branch changed from u/mmasdeu/17792-farey_word_problem to public/ticket/17792
  • Commit changed from 6d9c152c66ee11e73341e35ed1725a63d62b0cca to 18e034409e8b62c81821e93132a11dd15d7fd432

I have made sure that the doc builds, and also cleaned the file a little bit.


New commits:

72d3a9dMerge branch 'u/mmasdeu/17792-farey_word_problem' into 6.7.b0
18e0344trac #17792 make sure doc builds + general pep8 cleanup of the file

comment:4 Changed 4 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:5 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.5 to sage-6.7

comment:6 follow-up: Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_info

Why would you use a 1-based answer while the Python is 0-based. 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 ; follow-up: Changed 4 years ago by mmasdeu

  • 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 1-based approach is essential here no matter how much you like 0-based languages :-).

Also, you can always do something like:

sage: wd = F.word_problem(g)
sage: prod(F.gen(i-1) if i > 0 else F.gen(-i-1)**-1 for i in wd) == g
True

Replying to vdelecroix:

Why would you use a 1-based answer while the Python is 0-based. 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:8 in reply to: ↑ 7 ; follow-up: Changed 4 years ago by vdelecroix

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 1-based approach is essential here no matter how much you like 0-based 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 1-based). 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(i-1) if i > 0 else F.gen(-i-1)**-1 for i in wd) == g
True

Very elegant and very natural!

Vincent

comment:9 in reply to: ↑ 8 ; follow-up: Changed 4 years ago by mmasdeu

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 1-based). 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 1-based, 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 = [(a-1,len(list(g))) if a > 0 else (-a-1,-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. Replacing gen 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:

  1. Again, the user might want the more "raw" data, which we threw away.
  2. 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 vdelecroix

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 0-based. Moreover, if you want something useful to program morphisms, it would be better if 0-based, 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 0-based to 1-based, 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 1-based... 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 vdelecroix

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 hmonien

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 mmasdeu

  • 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 nearly-optimal solution...

comment:14 Changed 4 years ago by cremona

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 1-based or 0-based 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 0-basing 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 mmasdeu

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 cremona

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 mmasdeu

  • Branch changed from public/ticket/17792 to u/mmasdeu/17792-farey-wordproblem
  • Commit changed from 18e034409e8b62c81821e93132a11dd15d7fd432 to 3de10d68173dc99937c52af0cc5df5b8e2b2017a

New commits:

612a62bTrac 17792: Fixed bug in LLT algorithm, added word problem functionality.
e4c740atrac #17792 make sure doc builds + general pep8 cleanup of the file
3de10d6Trac #17792: Added methods word_problem, tietze, syllables and corresponding documentation.

comment:18 Changed 4 years ago by mmasdeu

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

Thank you all for the constructive comments!

comment:19 Changed 4 years ago by vdelecroix

  • 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 with 1,2,3,... and -1,-2,-3,... as it was (the current tietze)
  • "gens_index": as pairs (i,+1) or (i,-1) where i is the generator (the current syllabes)
  • "gens": as pairs (m,+1) or (m,-1) where m 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 git

  • Commit changed from 3de10d68173dc99937c52af0cc5df5b8e2b2017a to 908375633e44d67fa3991bf0f7c4e2cc381dbef1

Branch pushed to git repo; I updated commit sha1. New commits:

9083756Trac #17792: Modified according to suggestions of vdelecroix.

comment:21 follow-up: Changed 4 years ago by mmasdeu

  • 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 vdelecroix

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 cremona

  • 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 follow-ups.

comment:24 Changed 4 years ago by vbraun

  • Branch changed from u/mmasdeu/17792-farey-wordproblem to 908375633e44d67fa3991bf0f7c4e2cc381dbef1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:25 Changed 4 years ago by kcrisman

  • Commit 908375633e44d67fa3991bf0f7c4e2cc381dbef1 deleted
  • Reviewers changed from Vincent Delacroix, John Cremona to Vincent Delecroix, John Cremona
Note: See TracTickets for help on using tickets.