Opened 8 years ago

Closed 7 years ago

#13771 closed enhancement (fixed)

Canonical Forms and Automorphism Groups of linear codes

Reported by: tfeulner Owned by: wdj
Priority: major Milestone: sage-6.1
Component: coding theory Keywords: linear code, canonical form, automorphism group, semilinear equivalent
Cc: okazymyrov, dimpase, mmarco Merged in:
Authors: Thomas Feulner Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: u/tfeulner/ticket/13771 (Commits) Commit: ae9acc60bd7368bda5771a4f2e7b6051934bc2d4
Dependencies: #13726, #15576 Stopgaps:

Description (last modified by tfeulner)

Two linear codes C, C' over a finite field F of length n are equivalent, if there is

  • a permutation pi in Sn
  • a multiplication vector phi in F*n (F* the unit group)
  • an automorphism alpha of F

with C' = (phi, pi, alpha) C and the action is defined via

(phi, pi, alpha) (c0, ..., cn-1) = ( alpha( cpi(0)) phi0-1 , ... , alpha( cpi(n-1)) phin-1-1 )

This patch adds an algorithm for calculating a unique representative within the equivalence class of a given linear code. Furthermore, it computes the automorphism group of the code as a byproduct.

Finally, it can also deal with the action of subgroups of the semimonomial group.


Apply:

  1. #13726
  1. trac_13771-canonical_forms_linear_code.patch

Attachments (1)

trac_13771-canonical_forms_linear_code.patch (147.0 KB) - added by tfeulner 7 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 Changed 8 years ago by tfeulner

  • Description modified (diff)

comment:2 Changed 8 years ago by tfeulner

  • Keywords linear code canonical form automorphism group semilinear equiavelent added

comment:3 Changed 8 years ago by tfeulner

  • Keywords equivalent added; equiavelent removed

comment:4 Changed 8 years ago by tfeulner

  • Dependencies changed from #6391, #13726, #13723, #13417 to #13588, #13726, #13723, #13417
  • Description modified (diff)
  • Milestone changed from sage-5.6 to sage-5.7
  • Status changed from new to needs_review

comment:5 Changed 8 years ago by tfeulner

  • Dependencies changed from #13588, #13726, #13723, #13417 to #13726
  • Description modified (diff)

comment:6 Changed 7 years ago by okazymyrov

  • Cc okazymyrov added

comment:7 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 7 years ago by tfeulner

rebased upon #13726

comment:9 follow-up: Changed 7 years ago by wdj

Does this patch apply to 5.13.b0?

sage: hg_sage.patch("/home/wdj/sagefiles/sage-5.13.beta0/trac_13771-canonical_forms_linear_code.patch")

followed by sage -b gives

Installing c_lib
scons: `install' is up to date.
Updating Cython code....
missing cimport in module 'sage.groups.semimonomial_transformations.semimonomial_transformation': sage/coding/codecan/codecan.pxd
Compiling sage/coding/codecan/codecan.pyx because it changed.

...

Compiling sage/sets/disjoint_set.pyx because it depends on sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi.
Cythonizing sage/coding/codecan/autgroup_can_label.pyx
Cythonizing sage/coding/codecan/codecan.pyx

Error compiling Cython file:
------------------------------------------------------------
...
from sage.groups.perm_gps.permgroup_element cimport PermutationGroupElement
from sage.groups.semimonomial_transformations.semimonomial_transformation cimport SemimonomialTransformation
^

etc

comment:10 in reply to: ↑ 9 Changed 7 years ago by tfeulner

Replying to wdj:

Does this patch apply to 5.13.b0?

It must be 5.13.b1. At least for the patchbot it seems to work, except for some old-style doctest continuation errors.

comment:11 follow-up: Changed 7 years ago by jdemeyer

Why don't you test the exception directly, instead of working with a try/except clause? It is possible to doctest exceptions:

            sage: # something raising an exception
            Traceback (most recent call last):
            ...
            NotImplementedError

comment:12 follow-up: Changed 7 years ago by vbraun

  • Cc dimpase mmarco added

Interface-wise, it would be nice to expose the different styles of automorphism groups from linear code as

    @cached_method
    def automorphism_group(self, morphisms="semilinear"):
       ...

and return the actual automorphism group, not a list of generators and order. For that, you'd have to implement subgroups of the semimonomial transformation groups as a parent, but that ought to be easy: Just derive from the parent and override as necessary. We probably should have some infrastructure to make subgroups easier to construct (but that is material for another ticket). Then you wouldn't need _canonize.

The implementation looks good to me, can anybody who is actually working on something related to coding theory have a look?

comment:13 Changed 7 years ago by dimpase

Could you explain what

Finally, it can also deal with the action of subgroups of the semimonomial group.

means? E.g. can you find the canonical form which does not take the ring automorphisms into account? (This would be natural is some settings, I suppose).

comment:14 follow-up: Changed 7 years ago by vbraun

If you look at the docstring of class LinearCodeAutGroupCanLabel then you'll see. There is just permutations and only linear maps as subgroups, but currently you need to dig into the innards to construct them.

comment:15 in reply to: ↑ 14 Changed 7 years ago by dimpase

Replying to vbraun:

If you look at the docstring of class LinearCodeAutGroupCanLabel then you'll see. There is just permutations and only linear maps as subgroups, but currently you need to dig into the innards to construct them.

If the same algorithm works for any (or some other nontrivial well-defined class, e.g. the normal subgroups) of the subgroups of the semimonomial group, then there should be a proper interface for this exposed.

comment:16 in reply to: ↑ 12 Changed 7 years ago by tfeulner

Replying to vbraun:

Interface-wise, it would be nice to expose the different styles of automorphism groups from linear code as

    @cached_method
    def automorphism_group(self, morphisms="semilinear"):
       ...

You are right, it would be nice to distinguish these different notions of equivalence in automorhpism_group and also in canonical_representative. I will change that. There is also the possibility to restrict the permutational part of the action to Young subgroups. This is non-standard, should I provide an interface for that, too?

Then you wouldn't need _canonize.

My algorithm computes the canonical representative and the automorphism group at the same time. Therefore I thought that I have to implement the method _canonize, which guarantees that the computation is carried out only once. But I think, I should define

     @cached_method
     def _canonize(self, equivalence="semilinear"):
     ...

instead and automorphism_group and canonical_representative need not to be cached.

and return the actual automorphism group, not a list of generators and order. For that, you'd have to implement subgroups of the semimonomial transformation groups as a parent ...

I agree, but I am not sure how difficult this task will become. I am not working in academia anymore, so I am not sure if I will find enough time. Maybe we could open a seperate ticket with someone else being responsible?

comment:17 in reply to: ↑ 11 Changed 7 years ago by tfeulner

Replying to jdemeyer:

Why don't you test the exception directly, instead of working with a try/except clause? It is possible to doctest exceptions:

            sage: # something raising an exception
            Traceback (most recent call last):
            ...
            NotImplementedError

I have no idea, why I did this... I changed it.

The new version also provides an interface to the algorithm started for different notions of equivalence.

comment:18 Changed 7 years ago by vbraun

My point with the automorphism_group was mainly that its bad to make backwards-incompatible changes. If we implement the various subgroups properly then we would want to return the actual group and not a pair (generators, order). Its perfectly fine to leave that for future work, of course. How about we call it automorphism_group_gens or something like that, then we can in the future implement automorphism_group returning an actual group.

Apart from that looks good... Dima, did you take a look at the code?

comment:19 follow-up: Changed 7 years ago by darij

Just saw this mentioned on sage-combinat-devel; sorry I can't be of any actual help, so I thought I'll just drop a few remarks...

tfeulner: Given that you reference your thesis in the code, wouldn't it make sense to put it online on, say, arXiv?

I don't understand what _cyclic_shift is supposed to do. What is being cycled? If you want to get a cyclic permutation, why the + 1's in:

 	122	        x[p[i - 1]] = p[i] + 1 
 	123	    x[p[len(p) - 1]] = p[0] + 1 

"quadrupel" should be "quadruple".

 	45	    For every `i \in \{0, \ldots, n-1\}` 
 	46	    there is a group `G^{(i)}` and a surjective group homomorphism `f^{(i)}: G 
 	47	    \rightarrow G^{(i)}` such that `(f^{(i)}, \Pi^{(i)})` is a homomorphism of 
 	48	    group actions where `\Pi^{(i)}: X^n \rightarrow X` is the projection to 
 	49	    the `i`-th coordinate.

Isn't this a rather complicated way to say that the action of G \rtimes \{id\} on X^n is given by a direct product of several G-sets X ? I agree that the above is more precise, but can't you at least get rid of the G^{(i)} by assuming it to be G right away?

Changed 7 years ago by tfeulner

comment:20 in reply to: ↑ 19 Changed 7 years ago by tfeulner

Replying to darij:

Thanks for your comments, darij and Volker. I have changed the corresponding lines in the new patch.

tfeulner: Given that you reference your thesis in the code, wouldn't it make sense to put it online on, say, arXiv?

At the moment, it is getting reviewed. The final version will be published online by the university, maybe in about three months.

comment:21 Changed 7 years ago by tfeulner

Some weeks passed, I just want to bring this ticket back to your minds.

comment:22 follow-up: Changed 7 years ago by vbraun

Dima, are you reviewing this ticket?

If not then I'll merge it, code looks good and is better than what we have (i.e. nothing).

comment:23 in reply to: ↑ 22 Changed 7 years ago by dimpase

Replying to vbraun:

Dima, are you reviewing this ticket?

If not then I'll merge it, code looks good and is better than what we have (i.e. nothing).

No, I am not. Please merge this.

comment:24 follow-up: Changed 7 years ago by vbraun

Does not apply to the latest Sage-6, please rebase.

Build sage-git and then run

sage -dev import-patch --url http://trac.sagemath.org/raw-attachment/ticket/13771/trac_13771-canonical_forms_linear_code.patch

comment:25 Changed 7 years ago by tfeulner

  • Dependencies changed from #13726 to #13726, #15576

Dear Volker,

Thanks for this decision.

Before rebasing this ticket, I will work on #15576 and see if some changes will be necessary.

comment:26 Changed 7 years ago by tfeulner

  • Branch set to u/tfeulner/ticket/13771
  • Created changed from 11/28/12 12:07:14 to 11/28/12 12:07:14
  • Modified changed from 12/26/13 09:47:42 to 12/26/13 09:47:42

comment:27 in reply to: ↑ 24 Changed 7 years ago by tfeulner

  • Commit set to ae9acc60bd7368bda5771a4f2e7b6051934bc2d4

Replying to vbraun:

rebased to sage-6.1.beta2


New commits:

ae9acc6Rebased on sage-6.1.beta2
82d2c10# User Thomas Feulner <thomas.feulner@uni-bayreuth.de>

comment:28 Changed 7 years ago by vbraun

  • Reviewers set to Volker Braun

comment:29 Changed 7 years ago by vbraun

  • Resolution set to fixed
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.