Opened 10 years ago

Closed 10 years ago

# Bug in permutation_automorphism_group for linear codes

Reported by: Owned by: tfeulner wdj major sage-duplicate/invalid/wontfix coding theory rlm Robert Miller N/A

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

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