Algebraic extensions in large characteristic broken

[frankluebeck]

Observed behaviour

After updating the master branch (to commit cd0a8a743) some of my currently developed code was broken. This could be traced back to:

gap> F := GF(2305843009213693967);
GF(2305843009213693967)
gap> xx := Indeterminate(F, "xx");; pol := xx^2 + One(F);;
gap> F2 := AlgebraicExtension(F, pol);
<field of size 5316911983139663560790518517532197089>
gap> a := Random(F2);
ZmodpZObj(38949595212977430,2305843009213693967)*a+ZmodpZObj(20384525485352021\
80,2305843009213693967)
gap> a![1];
[ ZmodpZObj( 2038452548535202180, 2305843009213693967 ), 
  ZmodpZObj( 38949595212977430, 2305843009213693967 ) ]
gap> b := a*a;
ZmodpZObj(1878660435820231628,2305843009213693967)*a+ZmodpZObj(718878163927484\
220,2305843009213693967)
gap> b![1];
<vector mod 2305843009213693967: [ 718878163927484220, 1878660435820231628 ]>
gap> c := b*b;
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for `ProductCoeffs' on 2 arguments at /export/home/luebeck/gap4/lib/methsel2.g:249 called from
ProductCoeffs( x![1], y![1] ) at /export/home/luebeck/gap4/lib/algfld.gi:490 called from
<function "* AlgElm*AlgElm">( <arguments> )
 called from read-eval loop at *stdin*:8
type 'quit;' to quit to outer loop
brk> 

Expected behaviour

Obvious...

As a temporary work around I'm now using:

gap> F := GF(2305843009213693967);
GF(2305843009213693967)
gap> xx := Indeterminate(F, "xx");; pol := xx^2 + One(F);;
gap> F2 := AlgebraicExtension(F, pol);
<field of size 5316911983139663560790518517532197089>
gap> fam := ElementsFamily(FamilyObj(F2));;
gap> fam!.reductionMat := List(fam!.reductionMat,List);              # Change back to list of lists!
[ [ ZmodpZObj( 2305843009213693966, 2305843009213693967 ), 
      ZmodpZObj( 0, 2305843009213693967 ) ] ]
gap> a := Random(F2);
ZmodpZObj(916323485000143507,2305843009213693967)*a+ZmodpZObj(2081735496398424\
69,2305843009213693967)
gap> a![1];
[ ZmodpZObj( 208173549639842469, 2305843009213693967 ), 
  ZmodpZObj( 916323485000143507, 2305843009213693967 ) ]
gap> b := a*a;
ZmodpZObj(2295539192544313348,2305843009213693967)*a+ZmodpZObj(638890405124559\
141,2305843009213693967)
gap> b![1];
[ ZmodpZObj( 638890405124559141, 2305843009213693967 ), 
  ZmodpZObj( 2295539192544313348, 2305843009213693967 ) ]
gap> c := b*b;
ZmodpZObj(571502177093693745,2305843009213693967)*a+ZmodpZObj(1624918548219283\
527,2305843009213693967)

I suspect (but have not checked the details) that the problem comes from a commit around bfa0889cb30411fca, maybe @hulpke can have a look?

I noticed the following with "vectors" of ZmodnZ numbers:

F := GF(2305843009213693967);
v := Vector(F, [Random(F),Random(F)]);
IsVector(v); # true
IsVector(v[1]); # true,  REALLY???
IsList(v); # false (should be true as for compact vectors)
Append(v,v); # method missing
Add(v, Random(F)); # method missing
ProductCoeffs(v,v); # method missing (same for other XXXCoeffs)

[hulpke]

Just a missing ProductCoeffs method -- easily fixed.

[frankluebeck]

Yes, your proposed method avoids the error on b*b in my example.

But problems remain, e.g.: a*b or a/b or b/b still run into errors.

My impression is that the code for IsZmodnZVectorRep and IsZmodnZMatrixRep is not yet ready to be used for polynomials or elements in algebraic extensions. In principle I agree that these new representations can be useful in terms of space and time efficiency. But there seem to be various methods missing (e.g.. there should be (good) methods for all XXXCoeffs operations), and some code should be better tested to avoid losses in efficiency. For example, looking at the code it was easy to detect the following problem:

gap> p := 2305843009213693967;;
gap> F := GF(2305843009213693967);;
gap> mat := RandomMat(200, 200, F);;
gap> nmat:=NewMatrix(IsZmodnZMatrixRep,F,200,mat);
<200x200-matrix mod 2305843009213693967>
gap> DeterminantMat(mat);time;
ZmodpZObj( 1697001943616928143, 2305843009213693967 )
2783
gap> DeterminantMat(nmat);time;  # works on integer matrix!
ZmodpZObj( 1697001943616928143, 2305843009213693967 )
31401

Your proposed method for ProductCoeffs has two problems: Its result is no longer in IsZmodnZVectorRep and it also makes the code slower, here is an example (and a suggestion for a better method):

gap> p := 2305843009213693967;;
gap> F := GF(2305843009213693967);;
gap> l := List([1..200],i->Random(F));;
gap> vl := NewVector(IsZmodnZVectorRep, F, l);
<vector mod 2305843009213693967 of length 200>
gap> for i in [1..50] do ProductCoeffs(l,l); od; time;
1771
gap> for i in [1..50] do ProductCoeffs(vl,vl); od; time;
3406
gap> IsZmodnZVectorRep(ProductCoeffs(vl,vl));
false
gap> prco := function(vl, vr)
>   local R, ipr;
>   R :=  BaseDomain(vl);
>   ipr := ProductCoeffs(vl![2], vr![2]) mod Size(R);
>   return NewVector(IsZmodnZVectorRep, R, ipr);
> end;;
gap> for i in [1..50] do prco(vl,vl); od; time;
222
gap> IsZmodnZVectorRep(prco(vl,vl));
true

[hulpke]

But problems remain, e.g.: a*b or a/b or b/b still run into errors.

My impression is that the code for IsZmodnZVectorRep and IsZmodnZMatrixRep is not yet ready to be used for polynomials or elements in algebraic extensions. In principle I agree that these new representations can be useful in terms of space and time efficiency. But there seem to be various methods missing (e.g.. there should be (good) methods for all XXXCoeffs operations), and some code should be better tested to avoid losses in efficiency.

Dear @frankluebeck

I completely agree. What I have is a band-aid at best, and a not very good one at it.

What it would require is a person with motivation, knowledge, and easily produced examples to go through these examples to fix them. I think you have all of these qualities, and would be eminently capable of fixing these issues to produce ultimately faster code. Let me know, and I will drop my patch.

Otherwise, the only workaround I would likely get to in the next weeks would be to turn off the use of vectors for polynomials, if the ring is Z/nZ.

[frankluebeck]

I reopen this and refer you to my last comment above. The commit 376343e1114480a957cdd54e942fec24fe769b56 does not resolve the problem reported here. I can have a look at the code for IsZmodnZVectorRep and IsZmodnZMatrixRep at some later stage, but not now. To resolve the problem temporarily I still suggest the workaround mentioned in the opening report: is should be avoided that the fam!.reductionMat in a family for an algebraic extension is in the IsZmodnZMatrixRep. I don't know where and why this happens, and there might be several places where something similar happens.

[fingolfin]

I believe this properly resolved for now; if I am wrong, please reopen.

[frankluebeck]

Yes, as far as I can see this is resolved for the moment.

At some stage it may become sensible to encode elements in algebraic extensions of large characteristic using IsZmodnZVectorRep. But that needs some work in various places.