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: sage-8.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:

Status badges

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 sage-support

Change History (21)

comment:1 Changed 4 years ago by dimpase

  • Authors set to Dima Pasechnik
  • Branch set to u/dimpase/codesizefix
  • Commit set to 69a1ae8bee93bae886058f6df3abb056d876439a

New commits:

69a1ae8fixed the wrong bound, and made sure docstrings are correctly formatted

comment:2 Changed 4 years ago by git

  • Commit changed from 69a1ae8bee93bae886058f6df3abb056d876439a to 3b80b3e310132ab06a1c71d1098a718ed198e284

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

4b90c16Remove deprecated_callable_import
aa16210Merge branch 'u/jdemeyer/deprecate_deprecated_callable_import' of trac.sagemath.org:sage into dev
73b06feMerge branch 'u/dimpase/codesizefix' of trac.sagemath.org:sage into dev
3b80b3efixed non-ascii and other typos

comment:3 Changed 4 years ago by dimpase

  • 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 git

  • Commit changed from 3b80b3e310132ab06a1c71d1098a718ed198e284 to b411d02a4bdd9d3a9cc22f75c8c0e6f97954d6a1

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

b411d02cleanup of Griesmer bound, docs and examples

comment:5 Changed 4 years ago by git

  • Commit changed from b411d02a4bdd9d3a9cc22f75c8c0e6f97954d6a1 to 179ac5e247e0eb8a090d0cf8cd22b203a8982f12

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

179ac5ecleanup of Griesmer bound, docs and examples

comment:6 Changed 4 years ago by dimpase

  • 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 jsrn

  • Branch changed from u/dimpase/codesizefix to u/jsrn/codesizefix

comment:8 Changed 4 years ago by jsrn

  • 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 and griesmer_upper_bound, I added such a check on all the relevant functions, which throws a ValueError on failure.
  • I fixed grammar, markup and some semantics in a number of doc-strings (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 sage-support: 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:

224b1beRemove rename_keyword deprecation warning (6 years old)
1ee9d38Basic parameter sanity check on more bounds
4b0a57eMore doc-string fixes
Last edited 4 years ago by jsrn (previous) (diff)

comment:9 Changed 4 years ago by dimpase

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 top-level 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 follow-up: Changed 4 years ago by 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.
  • MRRW bound is like Elias, I think.
  • Gilbert-Varshamov holds only for fields.
  • Griesmer holds only for fields, I believe.

Best, Johan

comment:11 in reply to: ↑ 10 Changed 4 years ago by dimpase

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.
  • Gilbert-Varshamov 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 well-written, 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 dimpase

  • 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:

af37ca3Merge branch 'u/jdemeyer/deprecate_deprecated_callable_import' of trac.sagemath.org:sage into codesizefix
bb33393Merge branch 'u/dimpase/codesizefix' of trac.sagemath.org:sage into codesizefix
5d2ee22Merge branch 'u/jsrn/codesizefix' of trac.sagemath.org:sage into codesizefix
e793a92added field_based and used it whenever needed

comment:13 Changed 4 years ago by git

  • Commit changed from e793a923f9dc7deaf85f325eb6f3e9c90b82011f to 228451d2512401669b68961aa0995c17b573ca52

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

228451dadjusted the top docs to talk about codes not only over fields

comment:14 Changed 4 years ago by git

  • Commit changed from 228451d2512401669b68961aa0995c17b573ca52 to e398f4c010ac0f3f7ae28626227d67300f656f11

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

18e9a46Merge branch 'u/jdemeyer/deprecate_deprecated_callable_import' of trac.sagemath.org:sage into devbeta6
e398f4cMerge branch 'u/dimpase/codesizefix' of trac.sagemath.org:sage into devbeta6

comment:15 Changed 4 years ago by dimpase

rebased over latest beta(6).

comment:16 Changed 4 years ago by git

  • Commit changed from e398f4c010ac0f3f7ae28626227d67300f656f11 to e258a2053f99656bc3ee079f796758039d994750

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

e258a20remove obsolete test

comment:17 Changed 4 years ago by jsrn

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 jsrn

  • 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 follow-up: Changed 4 years ago by dimpase

Thanks. I removed these tests, as they tested the same parameter-checking function all over again, something that looked excessive to me.

Last edited 4 years ago by dimpase (previous) (diff)

comment:20 in reply to: ↑ 19 Changed 4 years ago by jsrn

Replying to dimpase:

Thanks. I removed these tests, as they tested the same parameter-checking 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 doc-tests as black-box 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 vbraun

  • Branch changed from u/dimpase/codesizefix to e258a2053f99656bc3ee079f796758039d994750
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.