Opened 5 years ago
Closed 5 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 5 years ago by
- Branch set to public/19462
- Commit set to 7272942710a80866935ba073fe0e8697d7a3f137
- Status changed from new to needs_review
comment:2 Changed 5 years ago by
Typo in this line: "[BS11] E, Byrne and A. Sneyd,". It should be "[BS11] E. Byrne and A. Sneyd"
comment:3 Changed 5 years ago by
- Commit changed from 7272942710a80866935ba073fe0e8697d7a3f137 to 4a8d9701a24ab0437ff4e8fbf517bb47443ef425
Branch pushed to git repo; I updated commit sha1. New commits:
4a8d970 | trac #19462: Typo
|
comment:4 follow-up: ↓ 5 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
Until you review #6452, they will be...
comment:7 Changed 5 years ago by
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: ↓ 10 Changed 5 years ago by
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.
comment:9 follow-up: ↓ 11 Changed 5 years ago by
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 5 years ago by
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: ↓ 12 Changed 5 years ago by
Anyway, you can do
if not self.base_ring() in Fields(): raise NotImplementedErrorAnd 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: ↓ 13 Changed 5 years ago by
Replying to ncohen:
Anyway, you can do
if not self.base_ring() in Fields(): raise NotImplementedErrorAnd 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: ↓ 14 Changed 5 years ago by
Because checking duplicates in a list of size
|size of the field| x nrows
is longer than in a list of sizenrows
.
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 5 years ago by
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: ↓ 16 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
True. That got lost in the successive workaround of this mutable/immutable mess >_<
Nathann
comment:19 Changed 5 years ago by
- Commit changed from 4a8d9701a24ab0437ff4e8fbf517bb47443ef425 to 017089a65dc9ef2087762007590d43cde1832240
Branch pushed to git repo; I updated commit sha1. New commits:
017089a | trac #19462: Bugfix+doctest
|
comment:20 Changed 5 years ago by
dedicated version for fields at public/19462-bis
.
comment:21 follow-up: ↓ 22 Changed 5 years ago by
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 5 years ago by
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: ↓ 24 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
- Commit changed from 017089a65dc9ef2087762007590d43cde1832240 to 03f759a5326645822fc56e0156487bcf4238fde0
comment:26 Changed 5 years ago by
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 5 years ago by
- Commit changed from 03f759a5326645822fc56e0156487bcf4238fde0 to 11e0f8295faa3497ad753728e2402932c2e4f362
Branch pushed to git repo; I updated commit sha1. New commits:
11e0f82 | trac #19462: ring->field
|
comment:28 Changed 5 years ago by
- Commit changed from 11e0f8295faa3497ad753728e2402932c2e4f362 to fc7e50975777e4f50e0c345cfdb0cf42f12740c5
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
fc7e509 | trac #19462: ring->field
|
comment:29 Changed 5 years ago by
- Reviewers set to Johan Sebastian Rosenkilde Nielsen, Vincent Delecroix
- Status changed from needs_review to positive_review
Good to go!
comment:30 Changed 5 years ago by
Thanks,
Nathann
comment:31 Changed 5 years ago by
- Branch changed from public/19462 to fc7e50975777e4f50e0c345cfdb0cf42f12740c5
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
trac #19462: LinearCode.is_projective