LinearCode.is_projective

[ncohen]

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

Nathann

[ncohen]

New commits:

​7272942

trac #19462: LinearCode.is_projective

[was]

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

[git]

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

​4a8d970

trac #19462: Typo

[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.

[ncohen]

One simplification: Since your matrix has coefficient in a field

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

Nathann

[vdelecroix]

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

[ncohen]

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

[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.

[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?

[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

[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

[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.

[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

[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

[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

[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.

[vdelecroix]

And then

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

[ncohen]

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

Nathann

[git]

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

​017089a

trac #19462: Bugfix+doctest

[vdelecroix]

dedicated version for fields at public/19462-bis.

[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.

[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

[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

[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.

[git]

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

​47d566d	Trac 19461: optimized code for fields
​03f759a	trac #19462: Enforce the unwritten assumption

[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?

[git]

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

​11e0f82

trac #19462: ring->field

[git]

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

​fc7e509

trac #19462: ring->field

[vdelecroix]

Good to go!

[ncohen]

Thanks,

Nathann