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: sage-7.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 mmasdeu

  • Branch set to u/mmasdeu/20347-farey-bugfix
  • Commit set to 492c20d8ede348075e6f15df469b70bcce0929b6
  • Status changed from new to needs_review

New commits:

492c20dTrac 20347: fixed word_problem bug in farey_symbol.

comment:2 Changed 4 years ago by mmasdeu

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 vdelecroix

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 git

  • Commit changed from 492c20d8ede348075e6f15df469b70bcce0929b6 to d4e97c957bb818d1f7e65c91c52aa0484fa606d7

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

d4e97c9Trac #20347: improved logic for _get_minus_one based on #20373, added tests.

comment:5 Changed 4 years ago by mmasdeu

I have added more doctests. Also, after looking at #20373 I have improved the logic of the function.

comment:6 Changed 4 years ago by vdelecroix

  • Authors set to Marc Masdeu

(just putting your name in Author to make the patchbot happier)

comment:7 Changed 4 years ago by vdelecroix

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 git

  • Commit changed from d4e97c957bb818d1f7e65c91c52aa0484fa606d7 to f7620dffbd92e05ecbdc42bcddcc62c072d81ef2

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

f7620dfTrac #20347: removed a utility function.

comment:9 Changed 4 years ago by mmasdeu

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 vdelecroix

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 vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:12 Changed 4 years ago by vbraun

  • Branch changed from u/mmasdeu/20347-farey-bugfix to f7620dffbd92e05ecbdc42bcddcc62c072d81ef2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.