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 )
Two linear codes C, C' over a finite field F of length n are equivalent, if there is
- a permutation pi in S_{n}
- 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) (c_{0}, ..., c_{n-1}) = ( alpha( c_{pi(0)}) phi_{0}^{-1} , ... , alpha( c_{pi(n-1)}) phi_{n-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:
Attachments (1)
Change History (30)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Keywords linear code canonical form automorphism group semilinear equiavelent added
comment:3 Changed 8 years ago by
- Keywords equivalent added; equiavelent removed
comment:4 Changed 8 years ago by
- 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
- Dependencies changed from #13588, #13726, #13723, #13417 to #13726
- Description modified (diff)
comment:6 Changed 7 years ago by
- Cc okazymyrov added
comment:7 Changed 7 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:8 Changed 7 years ago by
comment:9 follow-up: ↓ 10 Changed 7 years ago by
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
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: ↓ 17 Changed 7 years ago by
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: ↓ 16 Changed 7 years ago by
- 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
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: ↓ 15 Changed 7 years ago by
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
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
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
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
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: ↓ 20 Changed 7 years ago by
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
comment:20 in reply to: ↑ 19 Changed 7 years ago by
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
Some weeks passed, I just want to bring this ticket back to your minds.
comment:22 follow-up: ↓ 23 Changed 7 years ago by
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
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: ↓ 27 Changed 7 years ago by
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
- 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
- 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
- Commit set to ae9acc60bd7368bda5771a4f2e7b6051934bc2d4
comment:28 Changed 7 years ago by
- Reviewers set to Volker Braun
comment:29 Changed 7 years ago by
- Resolution set to fixed
- Status changed from needs_review to closed
rebased upon #13726