Opened 2 years ago

Closed 2 years ago

# Coset graph of linear codes

Reported by: Owned by: gh-Ivo-Maffei major sage-9.2 graph theory linear_codes coset_graph dimpase, jsrn, caruso Ivo Maffei Dima Pasechnik N/A e8d16c8 e8d16c8305eafa58785cc45ab1b21c33b672f466

### Description

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

### comment:1 Changed 2 years ago by gh-Ivo-Maffei

• Status changed from new to needs_review

### comment:2 Changed 2 years ago by dimpase

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 2 years ago by dimpase

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

### comment:4 follow-up: ↓ 6 Changed 2 years 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 2 years ago by git

• Commit changed from e92dae9e771a0d04d1e0f4ca9d11e3299c6a990d to eeaeb0205df5c430b10bd31a908fa994c7decb56

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

 ​eeaeb02 `fixed typos`

### comment:6 in reply to: ↑ 4 Changed 2 years ago by dimpase

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 2 years ago by git

• Commit changed from eeaeb0205df5c430b10bd31a908fa994c7decb56 to d89d8a54b192d27acba1c9f34f7f12db005240d6

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

 ​d89d8a5 `improved def of coset graph`

### comment:8 Changed 2 years ago by dimpase

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

### comment:9 Changed 2 years ago by git

• Commit changed from d89d8a54b192d27acba1c9f34f7f12db005240d6 to 87c56f521949fbdfee3220cef1bc17db81337062

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

 ​87c56f5 `minor docstring change`

### comment:10 Changed 2 years ago by git

• Commit changed from 87c56f521949fbdfee3220cef1bc17db81337062 to e8d16c8305eafa58785cc45ab1b21c33b672f466

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

 ​e8d16c8 `fixed issue with basis computation; fixed bug with zero projections`

### comment:11 Changed 2 years ago by dimpase

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

looks good to me

### comment:12 Changed 2 years 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.