Opened 4 years ago
Closed 4 years ago
#20347 closed defect (fixed)
AssertionError in word problem for Farey symbols
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  group theory  Keywords:  bug 
Cc:  mmasdeu, davidloeffler, cremona, xguitart, hmonien  Merged in:  
Authors:  Marc Masdeu  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  f7620df (Commits)  Commit:  f7620dffbd92e05ecbdc42bcddcc62c072d81ef2 
Dependencies:  Stopgaps: 
Description
sage: G = ArithmeticSubgroup_Permutation(S2="(1,2)(3,4)",S3="(1,2,3)") sage: S = G.farey_symbol() sage: g1,g2 = S.generators() sage: S.word_problem(g1^3 * g2^2 * g1 * g2) Traceback (most recent call last): ... AssertionError: [1, 1, 1, 2, 1, 2] [ 5 12] [ 5 12] [18 43] [ 18 43]
The two matrices above should be equal but differs by 1
Change History (12)
comment:1 Changed 4 years ago by
 Branch set to u/mmasdeu/20347fareybugfix
 Commit set to 492c20d8ede348075e6f15df469b70bcce0929b6
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
I fixed the bug reported in the ticket. I have tested that it works for Gamma0, Gamma_1, and Gamma for levels up to 20, as well as for the group reported above. Below is the code that I used:
for N in range(1,20): print 'N = %s'%N for G in [Gamma0, Gamma1, Gamma]: GN = G(N) F = GN.farey_symbol() gens = F.generators() ngens = len(gens) for i in range(200): V = [ZZ.random_element(ngens) for _ in range(100)] g = prod([gens[V[i]] for i in range(len(V))]) wd = F.word_problem(g, output = 'syllables') g1 = prod([gens[i].matrix()**a for i,a in wd]) if g.matrix() !=g1: print GN, V, g,g1 assert 0
The reason for the bug was again in some discrepancies in sign that I was ignoring. I try hard to avoid doing the naive trick of keeping track of the matrix that the computed word represents (although this is precisely what the check=True flag does, which is enabled by default) and fixing the sign at the end.
comment:3 Changed 4 years ago by
Thanks for looking at it!
In _get_minus_one
it would be good to have a doctest for each branch of the if/else
. And looking at the code we really need a multiplicative_order
on SL2Z
elements (see #20373).
comment:4 Changed 4 years ago by
 Commit changed from 492c20d8ede348075e6f15df469b70bcce0929b6 to d4e97c957bb818d1f7e65c91c52aa0484fa606d7
Branch pushed to git repo; I updated commit sha1. New commits:
d4e97c9  Trac #20347: improved logic for _get_minus_one based on #20373, added tests.

comment:5 Changed 4 years ago by
I have added more doctests. Also, after looking at #20373 I have improved the logic of the function.
comment:7 Changed 4 years ago by
In _get_dict_of_gens
there is no need to create a variable ans
. Moreover, are you sure it is now worth it to keep it? The following code is very fast
gens_dict = {g:i+1 for i,g in enumerate(self.generators())}
comment:8 Changed 4 years ago by
 Commit changed from d4e97c957bb818d1f7e65c91c52aa0484fa606d7 to f7620dffbd92e05ecbdc42bcddcc62c072d81ef2
Branch pushed to git repo; I updated commit sha1. New commits:
f7620df  Trac #20347: removed a utility function.

comment:9 Changed 4 years ago by
I think that our time would be best used by performing tests to find bugs in the code. We can discuss about each line in the code if you that's what you want, but I will not modify it anymore unless there is a bug in it.
comment:10 Changed 4 years ago by
Everything is fine as well on some random subgroups obtained with
sage.modular.arithgroup.tests.random_odd_arithgroup sage.modular.arithgroup.tests.random_even_arithgroup
comment:11 Changed 4 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
comment:12 Changed 4 years ago by
 Branch changed from u/mmasdeu/20347fareybugfix to f7620dffbd92e05ecbdc42bcddcc62c072d81ef2
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Trac 20347: fixed word_problem bug in farey_symbol.