Bounds in coding theory are still a mess

[Peter Mueller]

The functions and their docs in codes.bounds.* still seem to be a mess (as they have been since many years now). Here a few findings from a recent attempt to use them in class:

(1) If the code parameters are n = length, d = minimum distance, and q = size of the alphabet, there seems to be no system about the order of the arguments n, q, and d in these functions. For instance plotkin_upper_bound and others expect the arguments in the order n, q, d, while codesize_upper_bound and others expect the arguments in the order n, d, q.

(2) To make the inconsistencies in (1) even worse, the docs of many of these functions *do not* tell the order of the arguments; instead one has to look into the source code, or figure it out with small examples.

(3) Even if  there is a doc which tells about the arguments, then it may contain some other nonsense.  For instance hamming_upper_bound says that q is the size of a field, while this bound actually holds for any finite alphabet of size q.

(4) Again, there seem to be wrong bounds. For instance,  codesize_upper_bound(19,10,2) yields 8, while there are easy examples of size 16, and it is known that there are even codes of size 20. Looking into the source code reveals that codesize_upper_bound erroneously uses the Griesmer bound, which works for linear codes only.

I'm not sure how to fix the mess in (1) without breaking compatibility. Maybe a solution could be to enhance these functions with keyword arguments.

-- Peter Mueller

[Dima Pasechnik]

this is now https://trac.sagemath.org/ticket/22961

[Johan S. H. Rosenkilde]

'Peter Mueller' via sage-support writes:

> The functions and their docs in codes.bounds.* still seem to be a mess (as

> they have been since many years now). (...)

Indeed, these bounds are a catastrophe. Names, order of parameters, and
documentation is sorely lacking. In particular, none of the docs
describe whether the bounds hold for only linear codes or not.

A way around the incompatibility issues is to completely replace the
functions with a new set of functions with a more well-designed
interface. For instance, each of the bounds can be used as bounds for
any one of the code parameters, instead of just the dimension. Perhaps
someone could think of a clever interface to allow this. Is there any
precedence elsewhere in Sage?

Then the entire current module could just be deprecated.

> (4) Again, there seem to be wrong bounds. For instance,
> codesize_upper_bound(19,10,2) yields 8, while there are easy examples of
> size 16, and it is known that there are even codes of size 20. Looking into
> the source code reveals that codesize_upper_bound erroneously uses the
> Griesmer bound, which works for linear codes only.

The doc here is clearly very lacking. I think it makes sense to allow
querying only for linear codes (over fields), as the focus of Sage's
current functionality is firmly based here. A parallel set of functions
(or by using optional arguments etc.) could then support non-linear
codes over fields, or even codes over rings.

There's also #16393 (https://trac.sagemath.org/ticket/16393), but I
would suggest going much further in redesign than suggested there. And
of course, the very old patch currently there is completely out of date.

Best,
Johan

[Dima Pasechnik]

On Tuesday, May 9, 2017 at 9:41:46 AM UTC+1, Johan S. H. Rosenkilde wrote:

'Peter Mueller' via sage-support writes:

> The functions and their docs in codes.bounds.* still seem to be a mess (as
> they have been since many years now). (...)

Indeed, these bounds are a catastrophe. Names, order of parameters, and
documentation is sorely lacking. In particular, none of the docs
describe whether the bounds hold for only linear codes or not.

Not that more recent additions to sage/coding are perfect, I recall spending time untangling the mess on

https://trac.sagemath.org/ticket/20787

more or less completely on my own,  which gives a good example on how not to re-implement old functionality ;-)

How about we document what's undocumented on https://trac.sagemath.org/ticket/22961

before deciding what to do then?

(most of the stuff is on wikipedia, it's just trivial addition of links)

 

A way around the incompatibility issues is to completely replace the
functions with a new set of functions with a more well-designed
interface. For instance, each of the bounds can be used as bounds for
any one of the code parameters, instead of just the dimension. Perhaps
someone could think of a clever interface to allow this. Is there any
precedence elsewhere in Sage?

providing new interfaces to existing functions, but not replacing the code, seems more meaningful

Then the entire current module could just be deprecated.

> (4) Again, there seem to be wrong bounds. For instance,
>  codesize_upper_bound(19,10,2) yields 8, while there are easy examples of
> size 16, and it is known that there are even codes of size 20. Looking into
> the source code reveals that codesize_upper_bound erroneously uses the
> Griesmer bound, which works for linear codes only.

The doc here is clearly very lacking. I think it makes sense to allow
querying only for linear codes (over fields), as the focus of Sage's
current functionality is firmly based here.

Most of these code bounds are more general than linear.

While it might be that the focus of seemingly completed ACTIS INRIA Sage coding theory project

was about linear codes, I don't think any special bias towards linear codes is appropriate.

Something we should do, I think, is to provide as much of what, currently hardly updated any more, http://codetables.de/

provides in Sage. You know, it has these infamous "missing entries", cf e.g. the red-shaded part of

 http://codetables.de/BKLC/Tables.php?q=4&n0=1&n1=256&k0=1&k1=256

for which perhaps Sage can fill in gaps.

I checked that Sage can improve some upper bounds in these tables, and provide more entries, but the maintainer 

of http://codetables.de/ was not replying to my emails suggesting to fix this (perhaps, he waits for Magma people to 

help him instead :-))

Dima

[Johan S. H. Rosenkilde]

> Not that more recent additions to sage/coding are perfect, I recall
> spending time untangling the mess on
> https://trac.sagemath.org/ticket/20787
> more or less completely on my own, which gives a good example on how not
> to re-implement old functionality ;-)

Did I personally offend you? Because it seems you're trying to offend me
- mentioning a completely unrelated ticket, which I, mind, had nothing
to do with. IMHO it is quite evident that the code quality, doc quality
and functionality of sage/coding went up a lot during ACTIS.

> How about we document what's undocumented

> ...

Luckily we're each allowed to work on what we personally find rewarding.

> providing new interfaces to existing functions, but not replacing the code,
> seems more meaningful

"meaningful" is subjective. If you want to improve Sage with a minimal
effort, sure you're right. But there's multiple reasons for replacing
the code completely. It has a crappy interface, it's not well-written,
and my suggestion would enhance it's functionality a lot.

> Most of these code bounds are more general than linear.
> While it might be that the focus of seemingly completed ACTIS INRIA Sage
> coding theory project
> was about linear codes, I don't think any special bias towards linear codes
> is appropriate.

Either you misunderstand me or you're attacking me again; I'll assume
the first. ACTIS was about *algebraic* constructions and especially
efficient decoding - we mostly didn't care at all about general bounds
or general linear/non-linear codes (which were, functionality-wise in an
OK shape already).

There are bounds for general codes, and bounds for only linear codes.
All I'm suggesting is to have, aside from "best-code-bounds" *also* to
have a function for "best-linear-code-bounds", and stuff like that. If
you call that a bias towards linear code, then yes, I definitely think
that's appropriate, considering the major advantages and prevalence of
linear codes.

> Something we should do, I think, is to provide as much of what, currently
> hardly updated any more, http://codetables.de/

> ...

Note that codetables.de has constructive lower bounds, on top of the
upper-bounds. Replacing codetables.de is a *huge* undertaking -
especially the constructions - requiring Nathann'esque ardour. I
completely agree that it would be great if Sage had this, but it's
hardly on the same scale as improving the small set of bounds we
currently support in Sage (which we'd need in any case).

Best,
Johan

[Dima Pasechnik]

On Wednesday, May 10, 2017 at 8:47:21 AM UTC+1, Johan S. H. Rosenkilde wrote:

> Not that more recent additions to sage/coding are perfect, I recall
> spending time untangling the mess on
> https://trac.sagemath.org/ticket/20787
> more or less completely on my own,  which gives a good example on how not
> to re-implement old functionality ;-)

Did I personally offend you? Because it seems you're trying to offend me
- mentioning a completely unrelated ticket, which I, mind, had nothing
to do with.

Please note that that "completely unrelated" ticket was fixing the work of your and David (?) GSoC mentee.

(and part of it was David's himself, IIRC).

Saying that you have nothing to do with it is, hmm, strange to me, sorry. 

And you guys just fell totally silent there. 

It's nothing to do with offending or anything, it's just matter of responsibility of all the Sage developers

that has to be taken seriously, otherwise we will end up with a lot of broken code.

 

IMHO it is quite evident that the code quality, doc quality
and functionality of sage/coding went up a lot during ACTIS.

I have no doubt about this, sure it was overall a great addition. 

> How about we document what's undocumented
> ...

Luckily we're each allowed to work on what we personally find rewarding.

> providing new interfaces to existing functions, but not replacing the code,
> seems more meaningful

"meaningful" is subjective. If you want to improve Sage with a minimal
effort, sure you're right. But there's multiple reasons for replacing
the code completely. It has a crappy interface, it's not well-written,
and my suggestion would enhance it's functionality a lot.

this is the usual error of open-source projects: "let's not fix our old bugs, but just

rewrite it is all from scratch".  

This is a very hard undertaking, and the example of that "completely unrelated" ticket

shows it all too well; few copies and pastes without thinking it all over, and, oops,

a hard to find bug:

https://trac.sagemath.org/ticket/20787#comment:24

Instead, I would say, adding more doctests and docs, auditing the old code and fixing

it if needed (some of it is more or less literal translation into Python of old GAP Guava package,

and reads quite non-Pythonic), is much more sensible.

I did a bit of this on https://trac.sagemath.org/ticket/22961 (ready for review now)

 

> Most of these code bounds are more general than linear.
> While it might be that the focus of seemingly completed ACTIS INRIA Sage
> coding theory project
> was about linear codes, I don't think any special bias towards linear codes
> is appropriate.

Either you misunderstand me or you're attacking me again; I'll assume
the first. ACTIS was about *algebraic* constructions and especially
efficient decoding - we mostly didn't care at all about general bounds
or general linear/non-linear codes (which were, functionality-wise in an
OK shape already).

There are bounds for general codes, and bounds for only linear codes.
All I'm suggesting is to have, aside from "best-code-bounds" *also* to
have a function for "best-linear-code-bounds", and stuff like that. If
you call that a bias towards linear code, then yes, I definitely think
that's appropriate, considering the major advantages and prevalence of
linear codes.

I suppose I misunderstood; sorry.

Yes, sure, this would be a great addition; by the way, we have ready to be

used bounds functionality for additive codes as well.

 

> Something we should do, I think, is to provide as much of what, currently
> hardly updated any more, http://codetables.de/
> ...

Note that codetables.de has constructive lower bounds, on top of the
upper-bounds. Replacing codetables.de is a *huge* undertaking -
especially the constructions - requiring Nathann'esque ardour. I
completely agree that it would be great if Sage had this, but it's
hardly on the same scale as improving the small set of bounds we
currently support in Sage (which we'd need in any case).

As long as no new code constructions have to be added, this is more of

database-thing problem, easier than https://doi.org/10.1007/s10623-016-0264-x

where we did add lots of tricky constructions.

[Johan S. H. Rosenkilde]

Dima Pasechnik writes:
> Please note that that "completely unrelated" ticket was fixing the work of
> your and David (?) GSoC mentee.
> (and part of it was David's himself, IIRC).
> Saying that you have nothing to do with it is, hmm, strange to me, sorry.
> And you guys just fell totally silent there.
> It's nothing to do with offending or anything, it's just matter of
> responsibility of all the Sage developers
> that has to be taken seriously, otherwise we will end up with a lot of
> broken code.

The ticket was opened by our GSoC student in the warmup but he left it
unfinished (and unmerged) since he began his proper GSoC project. I was
not really involved with that. David decided to finish the ticket, which
it seems he did too hastily. When ACTIS was over, David mostly stopped
contributing to Sage (he got a new job); this is normal. Daniel Augot,
who had never himself before contributed to Sage, attempted to finish
the ticket during Review Days 3, with a lot of help from you. New
developers needing help with debugging is normal. No obviously broken
code was ever introduced into Sage.

> this is the usual error of open-source projects: "let's not fix our old
> bugs, but just rewrite it is all from scratch".

Generalisation. Sometimes that judgement is an error, sometimes it's
not.

> This is a very hard undertaking, and the example of that "completely
> unrelated" ticket
> shows it all too well; few copies and pastes without thinking it all over,
> and, oops,
> a hard to find bug:
> https://trac.sagemath.org/ticket/20787#comment:24

The bug came from one of the ways that #20787 *improved* Sage's
capabilities wrt. Golay codes, by hard-coding some of the
expensive-to-compute properties. It did not come from cut-and-pasting of
old code.

> Instead, I would say, adding more doctests and docs, auditing the old code
> and fixing
> it if needed (some of it is more or less literal translation into Python of
> old GAP Guava package,
> and reads quite non-Pythonic), is much more sensible.
> I did a bit of this on https://trac.sagemath.org/ticket/22961 (ready for
> review now)

I'm still not arguing that wouldn't be good things to do, and you're
welcome to do them. I was merely suggesting something I found would add
more functionality to Sage.

> As long as no new code constructions have to be added, this is more of
> database-thing problem, easier than
> https://doi.org/10.1007/s10623-016-0264-x
> where we did add lots of tricky constructions.

AFAIK we are missing numerous code constructions and code manipulations.
To properly supersede codetables.de, we would also need the search
algorithm for finding good derived codes from base constructions.

Best,
Johan


Dima Pasechnik writes:

> On Wednesday, May 10, 2017 at 8:47:21 AM UTC+1, Johan S. H. Rosenkilde
> wrote:
>>
>> > Not that more recent additions to sage/coding are perfect, I recall
>> > spending time untangling the mess on
>> > https://trac.sagemath.org/ticket/20787

>> <https://www.google.com/url?q=https%3A%2F%2Ftrac.sagemath.org%2Fticket%2F20787&sa=D&sntz=1&usg=AFQjCNExN2h8OYzl3Fgqcq_SzWWgz8_PZg>

[Dima Pasechnik]

On Wednesday, May 10, 2017 at 12:17:25 PM UTC+1, Johan S. H. Rosenkilde wrote:

Dima Pasechnik writes:
> Please note that that "completely unrelated" ticket was fixing the work of
> your and David (?) GSoC mentee.
> (and part of it was David's himself, IIRC).
> Saying that you have nothing to do with it is, hmm, strange to me, sorry.
> And you guys just fell totally silent there.
> It's nothing to do with offending or anything, it's just matter of
> responsibility of all the Sage developers
> that has to be taken seriously, otherwise we will end up with a lot of
> broken code.

The ticket was opened by our GSoC student in the warmup but he left it
unfinished (and unmerged) since he began his proper GSoC project. I was
not really involved with that. David decided to finish the ticket, which
it seems he did too hastily. When ACTIS was over, David mostly stopped
contributing to Sage (he got a new job); this is normal. Daniel Augot,
who had never himself before contributed to Sage, attempted to finish
the ticket during Review Days 3, with a lot of help from you. New
developers needing help with debugging is normal. No obviously broken
code was ever introduced into Sage.

Well, it was an old doctest that made sure this error was caught.  A close call.

> this is the usual error of open-source projects: "let's not fix our old
> bugs, but just rewrite it is all from scratch".  

Generalisation. Sometimes that judgement is an error, sometimes it's
not.

Unless there is a majority, or even better, a consensus, for doing this,

I'd much prefer improving the existing code. It's much more incremental,

and thus less error-prone (although more boring, of course).

 

> This is a very hard undertaking, and the example of that "completely
> unrelated" ticket
> shows it all too well; few copies and pastes without thinking it all over,
> and, oops,
> a hard to find bug:
> https://trac.sagemath.org/ticket/20787#comment:24

The bug came from one of the ways that #20787 *improved* Sage's
capabilities wrt. Golay codes, by hard-coding some of the
expensive-to-compute properties. It did not come from cut-and-pasting of
old code.

Did I say "old code" here? No. It was copying and pasting high degree polynomials from somewhere

I have no idea about, see the removed function weight_enumerator() in

https://git.sagemath.org/sage.git/commit/?id=6bf9d4b11523aaf7fcf69dc73d87352eefb29a8b 

> Instead, I would say, adding more doctests and docs, auditing the old code
> and fixing
> it if needed (some of it is more or less literal translation into Python of
> old GAP Guava package,
> and reads quite non-Pythonic), is much more sensible.
> I did a bit of this on https://trac.sagemath.org/ticket/22961 (ready for
> review now)

I'm still not arguing that wouldn't be good things to do, and you're
welcome to do them. I was merely suggesting something I found would add
more functionality to Sage.

> As long as no new code constructions have to be added, this is more of
> database-thing problem, easier than
> https://doi.org/10.1007/s10623-016-0264-x
> where we did add lots of tricky constructions.

AFAIK we are missing numerous code constructions and code manipulations.
To properly supersede codetables.de, we would also need the search
algorithm for finding good derived codes from base constructions.

Well, yes, we need something like "best_code_sage_knows(*,linear=True)" function

for a given set of parameters.

IMHO much more urgent project than redoing from scratch what already is there. 

 

Cheers,

Dima

[Johan S. H. Rosenkilde]

>>
>> Generalisation. Sometimes that judgement is an error, sometimes it's
>> not.
>>
>
> Unless there is a majority, or even better, a consensus, for doing this,
> I'd much prefer improving the existing code. It's much more incremental,
> and thus less error-prone (although more boring, of course).

I think it's useless to discuss this further. I see your point, though
it would be stronger if the current code was better tested and of higher
quality to begin with. I don't know if you see my point, but it's not
important; if I get motivated enough to implement what I'm thinking
about, it will bring about new useful functionality as well, so with
proper testing it should be merged in Sage.

>> AFAIK we are missing numerous code constructions and code manipulations.
>> To properly supersede codetables.de, we would also need the search
>> algorithm for finding good derived codes from base constructions.
>>
>
> Well, yes, we need something like "best_code_sage_knows(*,linear=True)"
> function
> for a given set of parameters.

What I mean is that "the best code Sage knows" could be e.g. a BCH code
punctured somewhere, then extended, then Plotkin-summed with something
and then the dual of that. See e.g.
(http://codetables.de/BKLC/BKLC.php?q=2&n=24&k=17). Finding exactly that
sequence of code modifiers requires some sort of worklist algorithm
where the currently best known codes are applied all known modifiers.
The same is true for the lower and upper bounds of Brouwer's tables.

> IMHO much more urgent project than redoing from scratch what already is
> there.

You pointedly keep missing my point, but oh well...

[Dima Pasechnik]

On Thursday, May 11, 2017 at 1:01:41 PM UTC+1, Johan S. H. Rosenkilde wrote:

>>
>> Generalisation. Sometimes that judgement is an error, sometimes it's
>> not.
>>
>
> Unless there is a majority, or even better, a consensus, for doing this,
> I'd much prefer improving the existing code. It's much more incremental,
> and thus less error-prone (although more boring, of course).

I think it's useless to discuss this further. I see your point, though
it would be stronger if the current code was better tested and of higher
quality to begin with. I don't know if you see my point, but it's not
important; if I get motivated enough to implement what I'm thinking
about, it will bring about new useful functionality as well, so with
proper testing it should be merged in Sage.

>> AFAIK we are missing numerous code constructions and code manipulations.
>> To properly supersede codetables.de, we would also need the search
>> algorithm for finding good derived codes from base constructions.
>>
>
> Well, yes, we need something like "best_code_sage_knows(*,linear=True)"
> function
> for a given set of parameters.

What I mean is that "the best code Sage knows" could be e.g. a BCH code
punctured somewhere, then extended, then Plotkin-summed with something
and then the dual of that. See e.g.
(http://codetables.de/BKLC/BKLC.php?q=2&n=24&k=17). Finding exactly that
sequence of code modifiers requires some sort of worklist algorithm
where the currently best known codes are applied all known modifiers.

Correct me if I am wrong, but at least in this particular example the discovery of the code is done

purely it terms of the parameters; e.g. Plotkin sum of [n,k,d] and [n,k',d'] is a [2n,k+k',min(2d,d')],

similarly for taking duals and shortening.

So this is merely some kind of recursive building (with memoisation) of codes from "primitive" building blocks, similar

to what is done in sage.combinat.designs and in combinat.matrices.hadamard_matrix

Looks doable; not trivial, but doable nevertheless.

One would however need to extend the catalog of "primitive" constructions too, unless they are already there under different names, e.g. cyclic codes (of even length, too)

specified directly by parameters rather than by more special data, etc.