Regression: Irr runs into an error

[ThomasBreuer]

The following happens currently in the master branch:

gap> g:= DirectProduct( AlternatingGroup(5), SymmetricGroup(3) );;
gap> Irr( g );;
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `[]' on 2 arguments
The 2nd argument is 'fail' which might point to an earlier problem
 at /.../gap-master/gap/lib/methsel2.g:250 called from
[...]

git bisect says that the first bad commit is b6a4985.

[stevelinton]

I had a first look at this. The problem seems to come from the enumerator of a zero-dimensional vector space which does not recognise the regular empty list [] as lying in it. Specifically the NumberElement function returns fail.

gap> v := GF(5)^0;
( GF(5)^0 )
gap> e := Enumerator(v);
<enumerator of ( GF(5)^0 )>
gap> Position(e, []);
fail

It looks like the vector would previously have been converted in place into a compressed representation, but is now not. Obviously the enumerator should be fixed, but there is also the question of whether the commit introduces a performance hit by leaving some vectors in uncompressed format. While conversion in-place is a bad idea and one we should move away from, great care is needed to avoid unintended consequences.

[ThomasBreuer]

The empty list [] is not an element of the vector space GF(5)^0,
already because the family relation does not fit.
Thus [] does not appear in the enumerator of the vector space.
I think this behaviour is correct.

But Steve is right that the changed handling of conversions caused the regression.
If one really wants to use the ExtendedVectors concept when dealing with vectors of length zero
then the right place to fix the code would be the creation of the extended vectors.
Note that cutting off the last entry from a compressed vector of length 1 via {}
(which happens later, before the enumerator of the vector space gets asked)
returns a compressed vector of length zero, which behaves nicely.

So what about changing the function LiftConCandCenNonsolvGeneral in lib/clashom.gi,
for example as follows:

  # change reps to list of more general format
  nreps:=[];
  for x in reps do
    p:=rec(list:=x);
    p.vector:=ExponentsOfPcElement(Npcgs,LeftQuotient(h,x[2]))*One(field);
    p.exponents:=ShallowCopy(p.vector);
    ConvertToVectorRep(p.vector,field);
    p.vector:=p.vector*cg.projection;  # is not compressed if the result is empty
    Add(p.vector,One(field));              # and then also this vector is not compressed
# start new code
    ConvertToVectorRep(p.vector,field);  # make sure that the vector is compressed
# end new code
    Add(nreps,p);
  od;
  reps:=nreps;

[fingolfin]

Some remarks:

First off, I agree with the change for LiftConCandCenNonsolvGeneral suggested by @ThomasBreuer.

But I disagree with the statement that the empty list isn't an element of the vector space GF(5)^0. It is an element, and also is contained in its enumerator. Proof:

gap> v := GF(5)^0; e := Enumerator(v);
( GF(5)^0 )
<enumerator of ( GF(5)^0 )>
gap> Elements(v);
[ [  ] ]
gap> [] in Elements(v);
true
gap> e[1];
[  ]
gap> e[1] = [];
true

Yes, the family relation does not fit -- but IMHO that's a "bug" (or perhaps rather fundamental design flaw?) in the whole system of families on the one hand, which is in conflict with the idea of having a single empty list "for everything". To me, this is is akin to having strongly typed container objects (e.g. std::vector<int> in C++, which may only contain int elements), but then for some reason insisting that one the container is empty, it should loose its type. This is of course going to cause headaches, such as the one we are facing here (coincidentally, I just remembered that I brought up issues with 0-dimensional vector spaces on the GAP devel list August 20, 2012, with this example, amongst others:

gap> U:=GF(3)^0;
( GF(3)^0 )
gap> Zero(U);
[  ]
gap> Zero(U) in U;
false

Besides causing a general problem representing empty vectors as well as 0xn and mx0 matrices in GAP (which I hope will eventually be relieved somewhat by MatrixObj), it also has caused problems in other places E.g. there was a long standing bug in the orb package caused by the fact that the empty list is not a collection.

Back to the problem at hand: It is true that the change in b6a4985 exposed the issue, and I fully agree with @stevelinton that great care should be taken regarding the use of implicit conversions to compressed vector representation (both when adding such conversions, and when removing them). And I assure you that I did indeed spend considerable care and thought on that, not just in that commit, but also in all my others which replaced ConvertToVectorRep calls by ImmutableVector or other constructs. Though obviously, like everybody else, I quite regularly make mistakes, and having more people actively review those changes before they are merged would help hint hint ;-).

That said, in this particular case, I still stand by that particular change. I think removing the implicit conversion in NumberElement_ExtendedVectorsFF was correct. I also think that code which relies for its performance (or worse: its correctness) on others code by "accident" converting its vectors to a more efficient representations, is buggy, and should be fixed to perform the required conversion explicitly.

By coincidence and for unrelated reasons, I recently wrote some patches (not yet submitted) which fixed dealing with trivial vectors spaces in a few cases. I'll add a fix for the enumerator of trivial vector space and turn them into a proper PR. That will "also" fix this PR.

BTW, calling ConvertToVectorRep on an empty list does nothing. To get an empty compressed empty vector, one has to do what @ThomasBreuer suggested above and create a longer one and then form a sublist. While it'd be trivial to "fix" ConvertToVectorRep in this case, I would advise against it until somebody finds time to review the kernel code for compressed matrices to see that all of it actually handles such vectors correctly (i.e., does not crash or corrupt memory) -- considering that lots of code in GAP does not expect trivial groups / empty generators sets / empty bases etc., I'd not be surprised to see some booby traps hidden in that kernel code, too. Actually, screw that, I just had a look and it took me less than a minute to find proof for my suspicion:

gap> v:=[Z(2)]; ConvertToVectorRep(v, 2); v:=v{[]}; IsGF2VectorRep(v);
[ Z(2)^0 ]
2
<a GF2 vector of length 0>
true
gap> NUMBER_GF2VEC(v);
Segmentation fault: 11