Opened 4 years ago
Closed 4 years ago
#22961 closed defect (fixed)
wrong answers from codesize_upper_bound()
Reported by:  dimpase  Owned by:  

Priority:  major  Milestone:  sage8.0 
Component:  coding theory  Keywords:  
Cc:  jsrn, dlucas  Merged in:  
Authors:  Dima Pasechnik  Reviewers:  Johan Rosenkilde 
Report Upstream:  N/A  Work issues:  
Branch:  e258a20 (Commits, GitHub, GitLab)  Commit:  e258a2053f99656bc3ee079f796758039d994750 
Dependencies:  #22796  Stopgaps: 
Description
with the default method, codesize_upper_bound()
erroneously uses the bound only valid for linear codes.
sage: codes.bounds.codesize_upper_bound(19,10,2,algorithm="LP") # OK 20 sage: codes.bounds.codesize_upper_bound(19,10,2,algorithm="gap") # OK 20 sage: codes.bounds.codesize_upper_bound(19,10,2) # Not OK 8
see sagesupport
Change History (21)
comment:1 Changed 4 years ago by
 Branch set to u/dimpase/codesizefix
 Commit set to 69a1ae8bee93bae886058f6df3abb056d876439a
comment:2 Changed 4 years ago by
 Commit changed from 69a1ae8bee93bae886058f6df3abb056d876439a to 3b80b3e310132ab06a1c71d1098a718ed198e284
Branch pushed to git repo; I updated commit sha1. New commits:
4b90c16  Remove deprecated_callable_import

aa16210  Merge branch 'u/jdemeyer/deprecate_deprecated_callable_import' of trac.sagemath.org:sage into dev

73b06fe  Merge branch 'u/dimpase/codesizefix' of trac.sagemath.org:sage into dev

3b80b3e  fixed nonascii and other typos

comment:3 Changed 4 years ago by
 Dependencies set to #22796
now the doctests pick up an error in codes.bounds.griesmer_upper_bound
.
(related to the new meaning of / and %, I guess)
comment:4 Changed 4 years ago by
 Commit changed from 3b80b3e310132ab06a1c71d1098a718ed198e284 to b411d02a4bdd9d3a9cc22f75c8c0e6f97954d6a1
Branch pushed to git repo; I updated commit sha1. New commits:
b411d02  cleanup of Griesmer bound, docs and examples

comment:5 Changed 4 years ago by
 Commit changed from b411d02a4bdd9d3a9cc22f75c8c0e6f97954d6a1 to 179ac5e247e0eb8a090d0cf8cd22b203a8982f12
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
179ac5e  cleanup of Griesmer bound, docs and examples

comment:6 Changed 4 years ago by
 Status changed from new to needs_review
Only the changes on src/sage/coding/code_bounds.py
have to be reviewed.
Apart from the bugfix, I've streamlined the code of Griesmer bound, and added some more sanity checks, docs and doctests. (previously the loop in Griesmer bound did not terminate on weird inputs, etc).
comment:7 Changed 4 years ago by
 Branch changed from u/dimpase/codesizefix to u/jsrn/codesizefix
comment:8 Changed 4 years ago by
 Commit changed from 179ac5e247e0eb8a090d0cf8cd22b203a8982f12 to 4b0a57e3495b937e78c4cf60df1271c6dc024d0c
Hi Dima,
I agree with your fixes. I took the liberty to slightly extend the scope of this ticket even more:
 Inspired by your parameter checks in
codesize_upper_bound
andgriesmer_upper_bound
, I added such a check on all the relevant functions, which throws aValueError
on failure.
 I fixed grammar, markup and some semantics in a number of docstrings (I went through them all, but I might of course have missed some errors).
 I removed the 6 year old argument deprecation warning on some functions.
Could you review my changes?
Further, I'm actually motivated to take this opportunity to fix the other annoying thing that was brought up on sagesupport: the n, q, d
vs. n, d, q
argument order. Let's say we agreed on n, d, q
order  then we could in this ticket modify the relevant functions thusly:
def gilbert_lower_bound(n,d,q, old_params=True): r""" ... """ if old_params: deprecation("The old parameter order `n, q, d` is deprecated and will be changed to `n, d, q`. To use the new parameter order and remove this warning, use `sage.codes.bounds.gilbert_lower_bound(n, d, q, old_params=False)`.") d,q = q,d (...)
After the deprecation period is over, we can remove the if
statement.
I can do the change if you agree. Also, do we agree that n, d, q
is better than n, q, d
? It seems the former is also used in the Delsarte bounds.
Best, Johan
New commits:
224b1be  Remove rename_keyword deprecation warning (6 years old)

1ee9d38  Basic parameter sanity check on more bounds

4b0a57e  More docstring fixes

comment:9 Changed 4 years ago by
Thanks for looking into this. I think that the check on the parameters of codesize_upper_bound()
introduced in 1ee9d38 is too hard. Indeed, some of these bounds do not need q
being a prime power. (This must also be reflected in the toplevel documentation in the file; I suppose I overlooked this at some point in the past).
E.g. Delsarte's bound does not need it; q
is merely the size of the alphabet in this context. It remains to be seen which other bounds do not need this; Singleton bound for sure does not. I can't tell immediately about everything else.
I will add an extra parameter to _check_n_q_d(n, q, d)
so that the check on q
being a prime power can be disabled, and will use it sparingly.
comment:10 followup: ↓ 11 Changed 4 years ago by
Good point. For the other bounds, what I know is:
 Hamming bound holds for any alphabet size.
 I think Elias holds for any size, but it is presented in e.g. Roth's Introduction to Coding Theory as an asymptotic bound. I don't know if there are caveats when using it for finite values of n and d.
 MRRW bound is like Elias, I think.
 GilbertVarshamov holds only for fields.
 Griesmer holds only for fields, I believe.
Best, Johan
comment:11 in reply to: ↑ 10 Changed 4 years ago by
Replying to jsrn:
Good point. For the other bounds, what I know is:
 Hamming bound holds for any alphabet size.
 I think Elias holds for any size, but it is presented in e.g. Roth's Introduction to Coding Theory as an asymptotic bound. I don't know if there are caveats when using it for finite values of n and d.
yes, this looks correct to me, although indeed it's mostly used to bound the information ratio asymptotically.
 MRRW bound is like Elias, I think.
 GilbertVarshamov holds only for fields.
from the proof given in
https://en.wikipedia.org/wiki/Gilbert%E2%80%93Varshamov_bound
I don't see why it needs to be over a field.
There is also a section named An improvement in the prime power case
.
(I agree it's not wellwritten, in the beginning they start talking about
code over a field, only to have that section later on :))
 Griesmer holds only for fields, I believe.
yes.
comment:12 Changed 4 years ago by
 Branch changed from u/jsrn/codesizefix to u/dimpase/codesizefix
 Commit changed from 4b0a57e3495b937e78c4cf60df1271c6dc024d0c to e793a923f9dc7deaf85f325eb6f3e9c90b82011f
here are the changes in line with the latest comments.
New commits:
af37ca3  Merge branch 'u/jdemeyer/deprecate_deprecated_callable_import' of trac.sagemath.org:sage into codesizefix

bb33393  Merge branch 'u/dimpase/codesizefix' of trac.sagemath.org:sage into codesizefix

5d2ee22  Merge branch 'u/jsrn/codesizefix' of trac.sagemath.org:sage into codesizefix

e793a92  added field_based and used it whenever needed

comment:13 Changed 4 years ago by
 Commit changed from e793a923f9dc7deaf85f325eb6f3e9c90b82011f to 228451d2512401669b68961aa0995c17b573ca52
Branch pushed to git repo; I updated commit sha1. New commits:
228451d  adjusted the top docs to talk about codes not only over fields

comment:14 Changed 4 years ago by
 Commit changed from 228451d2512401669b68961aa0995c17b573ca52 to e398f4c010ac0f3f7ae28626227d67300f656f11
comment:15 Changed 4 years ago by
rebased over latest beta(6).
comment:16 Changed 4 years ago by
 Commit changed from e398f4c010ac0f3f7ae28626227d67300f656f11 to e258a2053f99656bc3ee079f796758039d994750
Branch pushed to git repo; I updated commit sha1. New commits:
e258a20  remove obsolete test

comment:17 Changed 4 years ago by
Sorry, I've been away for a few days. I'll get back to this soon once I've popped my email stack...
comment:18 Changed 4 years ago by
 Reviewers set to Johan Rosenkilde
 Status changed from needs_review to positive_review
It looks good and all tests pass. You removed a number of the "meaningless parameters are rejected" test blocks that I added. Not that I really mind, but why did you do that?
comment:19 followup: ↓ 20 Changed 4 years ago by
Thanks. I removed these tests, as they tested the same parameterchecking function all over again, something that looked excessive to me.
comment:20 in reply to: ↑ 19 Changed 4 years ago by
Replying to dimpase:
Thanks. I removed these tests, as they tested the same parameterchecking function all over again, something that looked excessive to me.
OK, that's a fair argument. My motivation for having them was thinking of the doctests as blackbox testing, i.e. if you didn't know that the functions were actually each implemented with exactly the same check, you would put a test for each of them. Now, if someone comes along and completely reimplements one of the functions, he might inadvertently remove the _check
call, and now  oops  no test.
I won't insist on putting them back however.
comment:21 Changed 4 years ago by
 Branch changed from u/dimpase/codesizefix to e258a2053f99656bc3ee079f796758039d994750
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
fixed the wrong bound, and made sure docstrings are correctly formatted