Opened 4 months ago

Closed 4 months ago

#30253 closed enhancement (fixed)

Coset graph of linear codes

Reported by: gh-Ivo-Maffei Owned by:
Priority: major Milestone: sage-9.2
Component: graph theory Keywords: linear_codes coset_graph
Cc: dimpase, jsrn, caruso Merged in:
Authors: Ivo Maffei Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: e8d16c8 (Commits) Commit: e8d16c8305eafa58785cc45ab1b21c33b672f466
Dependencies: Stopgaps:

Description

Added method to the AbstractLinearCode class to compute the coset graph of a linear code.

Change History (12)

comment:1 Changed 4 months ago by gh-Ivo-Maffei

  • Cc dimpase added
  • Status changed from new to needs_review

comment:2 Changed 4 months ago by dimpase

  • Cc jsrn caruso added

hamming -> Hamming

Also: we have abstract linear codes, to which you can attach different metrics. E.g. there are rank codes (on matrices, with distance being the rank of the difference), already implemented in Sage. So it would be good to have this implemented there too.

Provide a definition of the coset graph.

One day we should have additive codes (to have cosets of C, it suffices to have C an additive subgroup), so that we can also implement coset graphs for them, see e.g. https://arxiv.org/abs/1806.07069

comment:3 Changed 4 months ago by dimpase

What kind of graph does this correspond to in terms of the dual to C code?

comment:4 follow-up: Changed 4 months ago by gh-Ivo-Maffei

First of all, I'm not sure the algorithm used is the best one. I could simply compute the cosets of C and work with their representatives, but I have a feeling it will be slower. That said, I think the algorithm relies on C being a set of vectors. In Sagemath MatrixSpace is not a subtype of VectorSpace so I think this function will have issues if the vectors are actually matrices.

A definition for the coset graph is provided in the docstring: "the vertices are the cosets and 2 cosets are adjacent if they have representatives that differ in one coordinate".
I haven't found any LinearRankMetricCode in Sagemath that doesn't use vectors, so I could just move the cosetGraph method to AbstractLinearCodeNoMetric. However, if you wish to use a different definition of coset graph that uses a more general metric, then we need a substantially different implementation (still doable).

As far as the dual code is concerned, if I get it right the dual code of C is the orthogonal complement of C which is not a direct sum complement of C if we use a non positive-definite bilinear form. So I don't see many connections when the base field is finite. For instance:

sage: C = codes.GolayCode(GF(3))
sage: U = C.dual_code()
sage: U == C
True

comment:5 Changed 4 months ago by git

  • Commit changed from e92dae9e771a0d04d1e0f4ca9d11e3299c6a990d to eeaeb0205df5c430b10bd31a908fa994c7decb56

Branch pushed to git repo; I updated commit sha1. New commits:

eeaeb02fixed typos

comment:6 in reply to: ↑ 4 Changed 4 months ago by dimpase

Replying to gh-Ivo-Maffei:

First of all, I'm not sure the algorithm used is the best one. I could simply compute the cosets of C and work with their representatives, but I have a feeling it will be slower.

I think working in a complement space, as you did, is good.

That said, I think the algorithm relies on C being a set of vectors. In Sagemath MatrixSpace is not a subtype of VectorSpace so I think this function will have issues if the vectors are actually matrices.

A definition for the coset graph is provided in the docstring: "the vertices are the cosets and 2 cosets are adjacent if they have representatives that differ in one coordinate".

maybe something like "the vertices are the cosets of C, considered as a subgroup of the additive group of the ambient vector space, and two cosets are adjacent if they have representatives that differ in exactly one coordinate".

I haven't found any LinearRankMetricCode in Sagemath that doesn't use vectors, so I could just move the cosetGraph method to AbstractLinearCodeNoMetric.

hmm, no, as there is no metric at all, whereas you do use the Hamming metric.

However, if you wish to use a different definition of coset graph that uses a more general metric, then we need a substantially different implementation (still doable).

As far as the dual code is concerned, if I get it right the dual code of C is the orthogonal complement of C which is not a direct sum complement of C if we use a non positive-definite bilinear form. So I don't see many connections when the base field is finite.

you're right, sorry for noise at this point.

comment:7 Changed 4 months ago by git

  • Commit changed from eeaeb0205df5c430b10bd31a908fa994c7decb56 to d89d8a54b192d27acba1c9f34f7f12db005240d6

Branch pushed to git repo; I updated commit sha1. New commits:

d89d8a5improved def of coset graph

comment:8 Changed 4 months ago by dimpase

the (direct sum) complement -> a (direct sum) complement (it's certainly not unique)

comment:9 Changed 4 months ago by git

  • Commit changed from d89d8a54b192d27acba1c9f34f7f12db005240d6 to 87c56f521949fbdfee3220cef1bc17db81337062

Branch pushed to git repo; I updated commit sha1. New commits:

87c56f5minor docstring change

comment:10 Changed 4 months ago by git

  • Commit changed from 87c56f521949fbdfee3220cef1bc17db81337062 to e8d16c8305eafa58785cc45ab1b21c33b672f466

Branch pushed to git repo; I updated commit sha1. New commits:

e8d16c8fixed issue with basis computation; fixed bug with zero projections

comment:11 Changed 4 months ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

looks good to me

comment:12 Changed 4 months ago by vbraun

  • Branch changed from u/gh-Ivo-Maffei/coset_graph to e8d16c8305eafa58785cc45ab1b21c33b672f466
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.