Opened 10 years ago

Closed 10 years ago

#10994 closed defect (duplicate)

Bug in permutation_automorphism_group for linear codes

Reported by: tfeulner Owned by: wdj
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: coding theory Keywords:
Cc: rlm Merged in:
Authors: Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

The method permutation_automorphism_group gives different results for the two options method="gap"and method="partition":

sage: C = HammingCode(6, GF(2)).dual_code()
sage: G1 = C.permutation_automorphism_group(method="gap") # requires optional GAP package Guava
sage: G2 = C.permutation_automorphism_group(method="partition")
sage: G1 == G2 # requires optional GAP package Guava
False  # <-------- should be equal!

The application of ticket:10153 indicates that the problem is caused by method="partition".

Change History (4)

comment:1 Changed 10 years ago by rlm

Thomas also points out that the code only checks minimal weight vectors:

        if algorithm=="partition":
            from sage.groups.perm_gps.partn_ref.refinement_matrices import MatrixStruct
            stop = 0                                          # only stop if all gens are autos
            for i in range(1,len(nonzerowts)):
                if stop == 1:
                    break
                wt = nonzerowts[i]
                Cwt = [c for c in self if hamming_weight(c)==wt] # ridiculously slow!!
                MS = MatrixSpace(F,len(Cwt),n)
                Cwords_wt = MS(Cwt)
                M = MatrixStruct(Cwords_wt)
                autgp = M.automorphism_group()
                if autgp[0] == []:
                    return PermutationGroup([()])
                L = [[j+1 for j in autgp[0][i]] for i in range(len(autgp[0]))]
                G = PermutationGroup([Sn(x) for x in L])
                return G

This code is, frankly, terrible. I figured out after a bit of searching that this was introduced into sage at #4320 by David Joyner. Michael Abshoff gave the ticket a positive review based on a misunderstood conversation we had. I did not sufficiently examine the code to vouch for it, but I think he wanted to get it merged anyway.

If one looks at the code before that ticket, one sees the true intention of the algorithm which was a bit butchered at #4320.

Related to this is ticket #11032, which is specific to the binary case. I'll fix both of these to do the right thing, since I'm probably in the best position to do so. In fact, I think I'm going to suggest we remove automorphism_group_binary_code completely since we now have all cases.

comment:2 Changed 10 years ago by rlm

See #11033, which will fix this problem.

comment:3 Changed 10 years ago by rlm

After applying #10871 and #11033:

sage: C = HammingCode(6, GF(2)).dual_code()
sage: time G1 = C.permutation_automorphism_group(algorithm="gap")
CPU times: user 1.71 s, sys: 0.04 s, total: 1.76 s
Wall time: 24.39 s
sage: time G2 = C.permutation_automorphism_group(method="partition")
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.04 s
sage: G1 == G2
True

comment:4 Changed 10 years ago by jdemeyer

  • Authors Thomas Feulner deleted
  • Milestone set to sage-duplicate/invalid/wontfix
  • Resolution set to duplicate
  • Reviewers set to Robert Miller
  • Status changed from new to closed
Note: See TracTickets for help on using tickets.