Minimum distance bounds for punctured codes

[David Lucas]

For now, we have the following design in mind:

Have a hidden variable _best_known_min_dist_lower_bound which is initialized to the return value of the first minimum distance computation done by the user. Then, thanks to a Sage decorator, it's updated every time a better bound is computed. Note that the true minimum distance is of course the best lower AND upper bound possible...

[Johan Rosenkilde]

Also, there is a method minimum_distance_lower_bound(). If _best_known_min_dist_lower_bound is set, then this is returned. Otherwise, some default minimum distance lower bound estimator is used (1 if a generic code is used).

Question: Let's say class A has A.bound1() and A.bound2(). Per default, A.minimum_distance_lower_bound() calls A.bound1(). Now the user calls a.bound2() for some a of class A. This returns, say, 5, and it sets _best_known_min_dist_lower_bound = 5. If the user now calls A.minimum_distance_lower_bound() this immediately returns 5. But let's say that, incidentally, a.bound1() would return 6. So if the user had not called A.bound2() first, the call to A.minimum_distance_lower_bound() would give a better result.

So the question is whether A.minimum_distance_lower_bound() should always call the default bound, and return the greater of this result and _best_known_min_dist_lower_bound. Of course, to avoid recomputing the default bound, a flag should be set somewhere.

[Johan Rosenkilde]

An obvious suggestion springs to mind: have a minimum_distance_upper_bound as well. This is interesting since there are several non-trivial upper-bounds for the minimum distance of various codes over small alphabet. There is also a very nice randomized algorithms for generating upper bounds for a given code.

Having such a function would allow checking whether the upper and lower bounds matched: in that case one has already found the true minimum distance. That could be embedded into minimum_distance() to avoid exponential work in this case. Moreover, even when they don't match, it might be possible to use the knowledge to reduce computation.

Simple Example: Say for a binary code that the lower bound is 5 while the upper bound is 6. If 5 was the minimum distance, then there would be a choice of 5 columns of the parity check matrix summing to zero. There are binom(n, 5) < n^5 possible choices of columns to check.

I'm not sure implementing this kind of stuff is a priority for the project. But the "framework" of minimum_distance_upper_bound and the simple fix in minimum_distance might be.

[Johan Rosenkilde]

Btw, when I say "fast" in my first comment, then I mean "fast by convention". It would be enforced purely as a convention, and a case-by-case basis for different code families should decide whether a given method is fast or not.

[David Lucas]

Specific instance on a more generic problem described in issue #150