wrong answers from codesize_upper_bound()

[dimpase]

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

Depends on #22796

CC: @johanrosenkilde @sagetrac-dlucas

Component: coding theory

Author: Dima Pasechnik

Branch/Commit: e258a20

Reviewer: Johan Rosenkilde

Issue created by migration from https://trac.sagemath.org/ticket/22961

[dimpase]

Commit: 69a1ae8

[dimpase]

Branch: u/dimpase/codesizefix

[dimpase]

Author: Dima Pasechnik

[dimpase]

New commits:

69a1ae8

fixed the wrong bound, and made sure docstrings are correctly formatted

[sagetrac-git]

Changed commit from 69a1ae8 to 3b80b3e

[sagetrac-git]

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 non-ascii and other typos

[dimpase]

comment:3

now the doctests pick up an error in codes.bounds.griesmer_upper_bound.
(related to the new meaning of / and %, I guess)

[dimpase]

Dependencies: #22796

[sagetrac-git]

Changed commit from 3b80b3e to b411d02

[sagetrac-git]

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

b411d02

cleanup of Griesmer bound, docs and examples

[sagetrac-git]

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

179ac5e

cleanup of Griesmer bound, docs and examples

[sagetrac-git]

Changed commit from b411d02 to 179ac5e

[dimpase]

comment:6

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

[johanrosenkilde]

Changed branch from u/dimpase/codesizefix to u/jsrn/codesizefix

[johanrosenkilde]

comment:8

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:

224b1be	Remove rename_keyword deprecation warning (6 years old)
1ee9d38	Basic parameter sanity check on more bounds
4b0a57e	More doc-string fixes

[johanrosenkilde]

Changed commit from 179ac5e to 4b0a57e

[dimpase]

comment:9

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.

[johanrosenkilde]

comment:10

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

[dimpase]

comment:11

Replying to @johanrosenkilde:

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.

[dimpase]

Changed branch from u/jsrn/codesizefix to u/dimpase/codesizefix

[dimpase]

comment:12

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

[dimpase]

Changed commit from 4b0a57e to e793a92

[sagetrac-git]

Changed commit from e793a92 to 228451d

[sagetrac-git]

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

228451d

adjusted the top docs to talk about codes not only over fields

[sagetrac-git]

Changed commit from 228451d to e398f4c

[sagetrac-git]

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

18e9a46	Merge branch 'u/jdemeyer/deprecate_deprecated_callable_import' of trac.sagemath.org:sage into devbeta6
e398f4c	Merge branch 'u/dimpase/codesizefix' of trac.sagemath.org:sage into devbeta6

[dimpase]

comment:15

rebased over latest beta(6).

[sagetrac-git]

Changed commit from e398f4c to e258a20

[sagetrac-git]

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

e258a20

remove obsolete test

[johanrosenkilde]

comment:17

Sorry, I've been away for a few days. I'll get back to this soon once I've popped my email stack...

[johanrosenkilde]

comment:18

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?

[johanrosenkilde]

Reviewer: Johan Rosenkilde

[dimpase]

comment:19

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

[johanrosenkilde]

comment:20

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.

[vbraun]

Changed branch from u/dimpase/codesizefix to e258a20