Bug in CosetLeadersMatFFE

[osj1961]

For matrices with entries in 8-bit fields, this function can return a list of coset leaders w/ missing entries.
A minimal example is

gap> M := One(GF(4))*[[1,0,Z(4)],[0,1,Z(4)^2]];
[ [ Z(2)^0, 0*Z(2), Z(2^2) ], [ 0*Z(2), Z(2)^0, Z(2^2)^2 ] ]
gap> L := CosetLeadersMatFFE(M,GF(4));
[ [ 0*Z(2), 0*Z(2), 0*Z(2) ],, [ 0*Z(2), Z(2^2), 0*Z(2) ], 
  [ 0*Z(2), Z(2)^0, 0*Z(2) ],, [ 0*Z(2), Z(2)^0, Z(2^2) ], 
  [ 0*Z(2), Z(2^2), Z(2^2) ], [ 0*Z(2), 0*Z(2), Z(2^2) ], 
  [ Z(2^2), 0*Z(2), 0*Z(2) ], [ 0*Z(2), 0*Z(2), Z(2)^0 ], 
  [ 0*Z(2), Z(2^2)^2, Z(2)^0 ], [ 0*Z(2), Z(2)^0, Z(2)^0 ], 
  [ Z(2)^0, 0*Z(2), 0*Z(2) ] ]

where the 2nd and 5th entries of L are unbound.

I discovered this issue in trying to track down a problem with the covering radius computation for error-correcting codes in the Guava package. It could well be the case that Guava is the only place where this function is used. If so, it would seem to be reasonable to remove this function from GAP and recreate the functionality in Guava. (I've done exactly that as a stop-gap measure for the latest Guava release - but my hack loses the faster approach available for 8-bit fields.) If, on the other hand, other parties are also using this function it should be repaired.

[fingolfin]

Nothing in the GAP library uses it, and the only distributed GAP package using it is guava. Its documentation is also clearly written by and for people with a background in coding theory. Before being able to work on a fix, I'd have to first find a suitable text book to translate the documentation into terms I understand.

That said, I'd be happy to review and merge a fix.

BTW there is only a GAP method for CosetLeadersMatFFE. So I don't quite see why you'd loose access to optimizations for 8-bit matrices -- unless you mean that the actual bug is in some kernel helper function?

Ah looking at the code there are kernel helper functions COSET_LEADERS_INNER_8BITS and COSET_LEADERS_INNER_GF2 -- are you saying one of those is buggy? Of course these functions are now entirely undocumented, making it even more "appealing" to try and debug them sigh

[osj1961]

You're right about it being in the kernel helper function.
I copied the code into a local version that I could play with more easily, and
discovered that if I shunted the actual work to the CosetLeaderInner function (as
opposed to COSET_LEADERS_INNER_8BITS) everything resolved...

I'm just assuming that the 8BITS version goes faster than the generic algorithm...

        if q = 2 then
            tofind := tofind - COSET_LEADERS_INNER_GF2( vl, weight,
                              tofind, leaders);
        #elif ok8 then
        #    Print(tofind, "\n");
        #    tofind := tofind - COSET_LEADERS_INNER_8BITS( vl, weight,
        #                      tofind, leaders, felts);
        else
            #Print(tofind, "\n");
            tofind := tofind - CosetLeadersInner(vl, v, w, weight, 1,
                              rrecord, felts, q, tofind);
        fi;

The coding theory jargon can be offputting. In the case we're looking at a "code" C is just the null space of
a kxn matrix over F. For every vector v in F^k there is a "coset of the code" that is the set of all solutions to the
(non-homogeneous) system. So that corresponds to the terminology in group theory, with the code filling the role
of the subgroup and v+C is a coset. A "coset leader" is a vector in v+C with minimal weight (number of non-zero entries) -- unfortunately, there can be many such...

Pragmatically, I think the C code in COSET_LEADERS_INNER_8BITS must be following the same algorithm as the GAP code
in CosetLeadersInner. If they could be traced in parallel to one another it would be helpful. Also the commented out Print() statements I added above for debugging told an interesting story -- "tofind" is the number of elements in F^k for which we haven't yet found a corresponding coset leader.

Without the hack above we get

gap> C:=ReedSolomonCode(7,4);
a cyclic [7,4,4]2..3 Reed-Solomon code over GF(8)
gap> H := CheckMat(C);
[ [ Z(2)^0, Z(2^3)^6, Z(2^3)^6, Z(2^3)^3, Z(2^3), 0*Z(2), 0*Z(2) ], 
  [ 0*Z(2), Z(2)^0, Z(2^3)^6, Z(2^3)^6, Z(2^3)^3, Z(2^3), 0*Z(2) ], 
  [ 0*Z(2), 0*Z(2), Z(2)^0, Z(2^3)^6, Z(2^3)^6, Z(2^3)^3, Z(2^3) ] ]
gap> GuavaCosetLeadersMatFFE(H,GF(8));;
511
462
gap>

But with the 8BITS portion bypassed it's

gap> GuavaCosetLeadersMatFFE(H,GF(8));;
511
462
21
gap> 

So it looks like the 8BITS call is just not finishing the last bit...