Opened 3 years ago

Closed 3 years ago

#19462 closed enhancement (fixed)

LinearCode.is_projective

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.10
Component: coding theory Keywords:
Cc: jsrn, dlucas, dimpase Merged in:
Authors: Nathann Cohen Reviewers: Johan Sebastian Rosenkilde Nielsen, Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: fc7e509 (Commits) Commit: fc7e50975777e4f50e0c345cfdb0cf42f12740c5
Dependencies: Stopgaps:

Description

As the title says, this branch adds a very short function to LinearCode?.

Nathann

Change History (31)

comment:1 Changed 3 years ago by ncohen

  • Branch set to public/19462
  • Commit set to 7272942710a80866935ba073fe0e8697d7a3f137
  • Status changed from new to needs_review

New commits:

7272942trac #19462: LinearCode.is_projective

comment:2 Changed 3 years ago by was

Typo in this line: "[BS11] E, Byrne and A. Sneyd,". It should be "[BS11] E. Byrne and A. Sneyd"

comment:3 Changed 3 years ago by git

  • Commit changed from 7272942710a80866935ba073fe0e8697d7a3f137 to 4a8d9701a24ab0437ff4e8fbf517bb47443ef425

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

4a8d970trac #19462: Typo

comment:4 follow-up: Changed 3 years ago by vdelecroix

One simplification: Since your matrix has coefficient in a field, you can always normalize the rows. For each of them, choose the first coefficient which is nonzero, let say a and multiply your row by 1/a. It gives a canonical representative of the row. Then, you just have to check that your normalized columns are distinct.

There might be already some code to do that somewhere... let me check.

comment:5 in reply to: ↑ 4 Changed 3 years ago by ncohen

One simplification: Since your matrix has coefficient in a field

Why could I assume that the base ring is a field?

Nathann

comment:6 Changed 3 years ago by vdelecroix

Until you review #6452, they will be...

comment:7 Changed 3 years ago by ncohen

I do not understand, could you say explicitly why we may be allowed to assume that the base ring is a field?

comment:8 follow-up: Changed 3 years ago by vdelecroix

Currently in Sage you can only build linear codes over finite fields. The only tentative to generalize it (though only to the rings ZZ/nZZ) is #6452. Note that this ticket not add directly a new linear code function but rather focuses on having a nice class for submodules of (ZZ/nZZ)^r which is exactly what linear codes are about.

And wikipedia says that linear code are over finite fields.

EDIT: until the last paragraph where it is mentioned that some authors used linear code for code over rings.

Last edited 3 years ago by vdelecroix (previous) (diff)

comment:9 follow-up: Changed 3 years ago by vdelecroix

Anyway, you can do

if not self.base_ring() in Fields():
    raise NotImplementedError

And if your field is GF(2) it should even be faster.

Could you also add an example of non projective code?

comment:10 in reply to: ↑ 8 Changed 3 years ago by ncohen

The reason why I want to managed general rings is because the paper from which I took the definition (a link appears in the branch) explicitly mention rings. Thus I saw no reason to assume more.

Also, if we do assume that we have fields won't your patch -- that enables general rings for codes -- make this code invalid?

Nathann

comment:11 in reply to: ↑ 9 ; follow-up: Changed 3 years ago by ncohen

Anyway, you can do

if not self.base_ring() in Fields():
    raise NotImplementedError

And if your field is GF(2) it should even be faster.

Why on earth would you ask me to degrade my code to manage fields only, when it is meant to handle general rings and *you* tell me that rings will be supported by LinearCode? eventually?

Could you also add an example of non projective code?

If you want.. I have to find one though...

Nathann

comment:12 in reply to: ↑ 11 ; follow-up: Changed 3 years ago by vdelecroix

Replying to ncohen:

Anyway, you can do

if not self.base_ring() in Fields():
    raise NotImplementedError

And if your field is GF(2) it should even be faster.

Why on earth would you ask me to degrade my code to manage fields only, when it is meant to handle general rings and *you* tell me that rings will be supported by LinearCode? eventually?

Because checking duplicates in a list of size |size of the field| x nrows is longer than in a list of size nrows.

I have no idea whether linear code over rings will be one day supported... ticket #6452 is just a first step. And I was just mentioning it to make some advertisement. But nobody cares.

comment:13 in reply to: ↑ 12 ; follow-up: Changed 3 years ago by ncohen

Because checking duplicates in a list of size |size of the field| x nrows is longer than in a list of size nrows.

This is a good justification for a field-specific version of this 5-lines algorithm. Not a justification for not supporting rings at all.

I have no idea whether linear code over rings will be one day supported... ticket #6452 is just a first step. And I was just mentioning it to make some advertisement. But nobody cares.

I have no idea either, but unless it is written somewhere that we can assume fields only, you won't see me adding a code that assumes more than it should.

Nathann

comment:14 in reply to: ↑ 13 Changed 3 years ago by ncohen

And I was just mentioning it to make some advertisement. But nobody cares.

Try to advertise it to people who you think should care. I review patches in less than three years, but on the other hand my field is graph theory. I forgot all I ever knew about rings.

About this ticket: it seems that some part of the code 'assumes' that the ring is a field indeed:

sage: LinearCode(matrix.ones(IntegerModRing(6),5))
...
NotImplementedError: Echelon form not implemented over 'Ring of integers modulo 6'.

Though that is apparently because the 'rank' function is only implemented on fields. This notion exists on rings too, doesn't it? Though I expect that the definition would be pretty nasty :-/

'on the paper', however:

sage: LinearCode(matrix.ones(IntegerModRing(3),5))
Linear code of length 5, dimension 1 over Ring of integers modulo 3

That's cheating, however, for

sage: IntegerModRing(3).is_field()
True

Nathann

comment:15 follow-up: Changed 3 years ago by ncohen

All of a sudden, however, I wonder about something... Given that the generator matrix is automatically replaced by a generator matrix with full rank, can this function return anything but 'True'?

Nathann

comment:16 in reply to: ↑ 15 Changed 3 years ago by vdelecroix

Replying to ncohen:

All of a sudden, however, I wonder about something... Given that the generator matrix is automatically replaced by a generator matrix with full rank, can this function return anything but 'True'?

Anyway, you should return

return len(set(RM)) == M.nrows()

to fit with the definition in the paper.

comment:17 Changed 3 years ago by vdelecroix

And then

sage: sage: C = codes.LinearCode(matrix(GF(2),[[1,0,1],[1,1,1]]))
sage: sage: C.is_projective()
False

comment:18 Changed 3 years ago by ncohen

True. That got lost in the successive workaround of this mutable/immutable mess >_<

Nathann

comment:19 Changed 3 years ago by git

  • Commit changed from 4a8d9701a24ab0437ff4e8fbf517bb47443ef425 to 017089a65dc9ef2087762007590d43cde1832240

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

017089atrac #19462: Bugfix+doctest

comment:20 Changed 3 years ago by vdelecroix

dedicated version for fields at public/19462-bis.

comment:21 follow-up: Changed 3 years ago by jsrn

LinearCode is beyond broken for rings. That the object cannot even be constructed is only the tip of the iceberg. The ZZ/pZZ-modules that Vincent implemented can form a base of a type of code over ring later on, but that will not inherit from LinearCode or AbstractLinearCode since there field assumption is everywhere. I don't know how much code sharing will be possible, but I doubt too much non-trivial code.

Also, I don't think it's high on anyone's list of priorities...

I've also been discussing with David to change LinearCode so it doesn't mention rings anymore. It's stupid since they're clearly not supported.

So I agree with Vincent that it's nicer to have code run in linear time rather than quadratic.

Moreover, I don't even think your code is correct over rings. Consider the following generator matrix over ZZ mod 6:

[ 1 2 0 ] [ 1 2 1 ]

This is clearly not projective since 2*c1 = c2. But your code would compare

set([ c1 * (ZZ mod 6) ]) = { (0,0), (1, 1), (2,2), ..., (5,5) } set([ c2 * (ZZ mod 6) ]) = { (0,0), (2,2), (4,4) }

Thus the check at the end would succeed, and you return True.

comment:22 in reply to: ↑ 21 Changed 3 years ago by vdelecroix

Replying to jsrn:

This is clearly not projective since 2*c1 = c2.

In the definition given in reference by Nathann, the condition is that R c1 != R c2... but of course, the definition is non-ambiguous over a field.

Vincent

comment:23 follow-up: Changed 3 years ago by jsrn

Ah, I see. Ok, so the code seems correct then :-)

But that's not what's usually understood by "linearly independent", I believe. If you, Nathann, insist on retaining the ring stuff, I suggest the definition be written out in full in the docstring (noone is going to look up a definition he believes he knows from high school).

Best, Johan

comment:24 in reply to: ↑ 23 Changed 3 years ago by dimpase

Replying to jsrn:

Ah, I see. Ok, so the code seems correct then :-)

But that's not what's usually understood by "linearly independent", I believe. If you, Nathann, insist on retaining the ring stuff, I suggest the definition be written out in full in the docsring (noone is going to look up a definition he believes he knows from high school).

yeah, I agree - even if one's high school linear algebra virginity has been lost to irresistible charms of commutative algebra, it's still quite unusual definition.

comment:25 Changed 3 years ago by git

  • Commit changed from 017089a65dc9ef2087762007590d43cde1832240 to 03f759a5326645822fc56e0156487bcf4238fde0

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

47d566dTrac 19461: optimized code for fields
03f759atrac #19462: Enforce the unwritten assumption

comment:26 Changed 3 years ago by vdelecroix

And actually in the reference Nathann gave, they consider codes over non-commutative finite rings! Which is indeed infinitely more general.

Nathann, for this version of the code, since you switched to a field implementation, could you adapt the documentation?

comment:27 Changed 3 years ago by git

  • Commit changed from 03f759a5326645822fc56e0156487bcf4238fde0 to 11e0f8295faa3497ad753728e2402932c2e4f362

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

11e0f82trac #19462: ring->field

comment:28 Changed 3 years ago by git

  • Commit changed from 11e0f8295faa3497ad753728e2402932c2e4f362 to fc7e50975777e4f50e0c345cfdb0cf42f12740c5

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

fc7e509trac #19462: ring->field

comment:29 Changed 3 years ago by vdelecroix

  • Reviewers set to Johan Sebastian Rosenkilde Nielsen, Vincent Delecroix
  • Status changed from needs_review to positive_review

Good to go!

comment:30 Changed 3 years ago by ncohen

Thanks,

Nathann

comment:31 Changed 3 years ago by vbraun

  • Branch changed from public/19462 to fc7e50975777e4f50e0c345cfdb0cf42f12740c5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.