#18548: Fix a bug introduced in #17792
-------------------------------------+-------------------------------------
Reporter: mmasdeu | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: modular forms | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/mmasdeu/18548-fix_farey_word_problem|
fa32ed11968c4d04f79893eef732e36d6ad73d3e
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by mmasdeu):
* cc: cremona (added)
* status: new => needs_review
* branch: => u/mmasdeu/18548-fix_farey_word_problem
* commit: => fa32ed11968c4d04f79893eef732e36d6ad73d3e
Old description:
> Ticket #17792 implemented the solution for the word problem for
> congruence subgroups of (P)SL2(Z). However, the element represented by
> the output word sometimes differs from the original element by at most
> one generator.
>
> Here is an example:
> {{{
> sage: G = Gamma0(10)
> sage: F = G.farey_symbol()
> sage: g = G([-701,-137,4600,899])
> sage: word = F.word_problem(g, output = 'syllables')
> sage: g1 = prod(F.generators()[i]**a for i,a in word)
> sage: g == g1 or g * G([-1,0,0,-1]) == g1
> False # Should be True
> }}}
>
> This ticket solves this. I have ran the code below to test:
> {{{
> for N in range(2,500):
> G = Gamma0(N)
> print "N = %s"%N
> gens = G.generators()
> F = G.farey_symbol()
> i = 0
> I = G([1,0,0,1])
> E = G([-1,0,0,-1])
> while i < 200:
> c = ZZ.random_element(1000)
> d = ZZ.random_element(1000)
> if gcd(c*N,d) > 1:
> continue
> i += 1
> _,a,b = xgcd(d,-c * N)
> g = G([a,b,c*N,d])
> wd = F.word_problem(g, output = 'syllables')
> g1 = prod(gens[j]**n for j,n in wd)
> assert g * g1**-1 == I or g * g1**-1 == E
> }}}
> (and also a modification to check Gamma_1(N).
New description:
Ticket #17792 implemented the solution for the word problem for congruence
subgroups of (P)SL2(Z). However, the element represented by the output
word sometimes differs from the original element by at most one generator.
Here is an example:
{{{
sage: G = Gamma0(10)
sage: F = G.farey_symbol()
sage: g = G([-701,-137,4600,899])
sage: word = F.word_problem(g, output = 'syllables')
sage: g1 = prod(F.generators()[i]**a for i,a in word)
sage: g == g1 or g * G([-1,0,0,-1]) == g1
False # Should be True
}}}
This ticket solves this. I have ran the code below to test:
{{{
for N in range(2,500):
G = Gamma0(N)
print "N = %s"%N
gens = G.generators()
F = G.farey_symbol()
i = 0
I = G([1,0,0,1])
E = G([-1,0,0,-1])
while i < 200:
c = ZZ.random_element(1000)
d = ZZ.random_element(1000)
if gcd(c*N,d) > 1:
continue
i += 1
_,a,b = xgcd(d,-c * N)
g = G([a,b,c*N,d])
wd = F.word_problem(g, output = 'syllables')
g1 = prod(gens[j]**n for j,n in wd)
assert g * g1**-1 == I or g * g1**-1 == E
}}}
(and also a modification to check Gamma_1(N).
PS: I also publicly apologise for being careless about this before. I did
have code to fix this behaviour, but it was in an external sage script:
this made the indirect tests pass.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/18548#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
