Bug in permutation_automorphism_group for linear codes

[sagetrac-tfeulner]

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".

CC: @rlmill

Component: coding theory

Reviewer: Robert Miller

Issue created by migration from https://trac.sagemath.org/ticket/10994

[rlmill]

comment:1

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.

[rlmill]

comment:2

See #11033, which will fix this problem.

[rlmill]

comment:3

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

[jdemeyer]

Changed author from Thomas Feulner to none

[jdemeyer]

Reviewer: Robert Miller