Recursion depth trap for due to level 3 assertion in characteristic polynomial of matrix code

[jackschmidt]

There is an issue in the characteristic polynomial of matrix routine as called by the meat-axe as called by the conjugacy classes code for permutation groups. This is in master and 4.8.8, but requires assertions turned on, to level 3, so I'm not sure if it is considered a real issue. I think the fix is simple though.

Reproducer:

SetAssertionLevel(3);
ConjugacyClasses(WreathProduct(SymmetricGroup(2),SymmetricGroup(5)));

Line with the problem (polynomial versus coefficient list):

Maybe this line is wrong (lib/matrix.gi line 466 in 4.8.8, line 479 in 4.10.0, line 476 in master):

    Assert(3, IsZero(Value(cp,imat)));

brk> cp;
[ Z(2)^0 ]
brk> imat;
<an immutable 1x1 matrix over GF2>

cp is not a polynomial. Maybe it is a coefficient list of a polynomial?

More log:

The functions before the loop are:

Value( f, x, One( x ) ) at /home/jack/gap/lib/ratfunul.gi:1154 called from
Value( cp, imat ) at /home/jack/gap/lib/matrix.gi:476 called from
CharacteristicPolynomialMatrixNC( DefaultFieldOfMatrix( mat ), mat, 1 ) at /home/jack/gap/lib/matrix.gi:671 called from
CharacteristicPolynomial( mm ) at /home/jack/gap/lib/matrix.gi:4412 called from
x ^ f[2] at /home/jack/gap/lib/ratfunul.gi:1119 called from
Value( f, x, One( x ) ) at /home/jack/gap/lib/ratfunul.gi:1154 called from
Value( cp, imat ) at /home/jack/gap/lib/matrix.gi:476 called from
CharacteristicPolynomialMatrixNC( F, M, 1 ) at /home/jack/gap/lib/meataxe.gi:913 called from
SMTX.SMCoRaEl( matrices, ngens, newgenlist, dim, F ) at /home/jack/gap/lib/meataxe.gi:1036 called from
SMTX.IrreducibilityTest( module ) at /home/jack/gap/lib/meataxe.gi:1233 called from
SMTX.IsIrreducible( cmod ) at /home/jack/gap/lib/meataxe.gi:1955 called from
SMTX.CollectedFactors( m ) at /home/jack/gap/lib/meataxe.gi:3059 called from
MTX.BasesMinimalSubmodules( mo ) at /home/jack/gap/lib/clashom.gi:2062 called from
LiftClassesEATrivRep( G, mpcgs, i, fants, hom, pcisom, solvtriv ) at /home/jack/gap/lib/clashom.gi:2471 called from
ConjugacyClassesViaRadical( G ) at /home/jack/gap/lib/clashom.gi:3080 called from
<function "unknown">( <arguments> )
 called from read-eval loop at *errin*:1

Output:

 ┌───────┐   GAP 4.10dev-1607-g344ae6f of today
 │  GAP  │   https://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-default64-kv6
 Configuration:  gmp 6.1.2, GASMAN, readline
 Loading the library and packages ...
 Packages:   AClib 1.3.1, Alnuth 3.1.0, AtlasRep 1.5.1, AutoDoc 2018.09.20, AutPGrp 1.10, Browse 1.8.8, Carat 2.2.3, 
             CRISP 1.4.4, Cryst 4.1.18, CrystCat 1.1.8, CTblLib 1.2.2, FactInt 1.6.2, FGA 1.4.0, GAPDoc 1.6.2, IO 4.5.4, 
             IRREDSOL 1.4, LAGUNA 3.9.1, Polenta 1.3.8, Polycyclic 2.14, PrimGrp 3.3.2, RadiRoot 2.8, ResClasses 4.7.1, 
             SmallGrp 1.3, Sophus 1.24, SpinSym 1.5, TomLib 1.2.7, TransGrp 2.0.4, utils 0.61
 Try '??help' for help. See also '?copyright', '?cite' and '?authors'
gap> ConjugacyClasses(WreathProduct(SymmetricGroup(2),SymmetricGroup(5)));
[ ()^G, (9,10)^G, (1,2)(9,10)^G, (1,2)(3,4)(9,10)^G, (1,2)(3,4)(5,6)(9,10)^G, (1,2)(3,4)(5,6)(7,8)(9,10)^G, (7,9)(8,10)^G, 
  (7,10,8,9)^G, (1,2)(7,9)(8,10)^G, (1,2)(7,10,8,9)^G, (1,2)(3,4)(7,9)(8,10)^G, (1,2)(3,4)(7,10,8,9)^G, 
  (1,2)(3,4)(5,6)(7,9)(8,10)^G, (1,2)(3,4)(5,6)(7,10,8,9)^G, (5,7,9)(6,8,10)^G, (5,7,10,6,8,9)^G, (1,2)(5,7,9)(6,8,10)^G, 
  (1,2)(5,7,10,6,8,9)^G, (1,2)(3,4)(5,7,9)(6,8,10)^G, (1,2)(3,4)(5,7,10,6,8,9)^G, (3,5)(4,6)(7,9)(8,10)^G, 
  (3,5)(4,6)(7,10,8,9)^G, (1,2)(3,5)(4,6)(7,9)(8,10)^G, (1,2)(3,5)(4,6)(7,10,8,9)^G, (3,5,4,6)(7,10,8,9)^G, 
  (1,2)(3,5,4,6)(7,10,8,9)^G, (3,5,7,9)(4,6,8,10)^G, (3,5,7,10,4,6,8,9)^G, (1,2)(3,5,7,9)(4,6,8,10)^G, 
  (1,2)(3,5,7,10,4,6,8,9)^G, (1,3)(2,4)(5,7,9)(6,8,10)^G, (1,3)(2,4)(5,7,10,6,8,9)^G, (1,3,2,4)(5,7,9)(6,8,10)^G, 
  (1,3,2,4)(5,7,10,6,8,9)^G, (1,3,5,7,9)(2,4,6,8,10)^G, (1,3,5,7,10,2,4,6,8,9)^G ]
gap> SetAssertionLevel(3);
gap> ConjugacyClasses(WreathProduct(SymmetricGroup(2),SymmetricGroup(5)));
Error, recursion depth trap (5000) in
  Characteristic( gens ) at /home/jack/gap/lib/ffe.gi:1075 called from 
DefaultRingByGenerators( arg[1] ) at /home/jack/gap/lib/ring.gi:413 called from
DefaultRing( coeff ) at /home/jack/gap/lib/ratfun1.gi:45 called from
LaurentPolynomialByExtRepNC( fam, cofs, val, ind ) at /home/jack/gap/lib/ratfunul.gi:42 called from
LaurentPolynomialByCoefficients( fam, cofs, 0, ind ) at /home/jack/gap/lib/ratfunul.gi:87 called from
UnivariatePolynomialByCoefficients( fam, cp, ind ) at /home/jack/gap/lib/matrix.gi:467 called from
...  at *stdin*:3
you may 'return;'
brk> 

[jackschmidt]

Sorry. cp is a polynomial at the time. There are many variables named cp, and the break loop was displaying a different one. Commenting out the Assert(IsZero(Value(cp,imat))); fixes the recursion depth trap, but I don't actually see anything wrong with that line.

So I don't see how to fix the problem, other than disabling a reasonable test.

[olexandr-konovalov]

Just to note that GAP regression tests use assertion level 2, hence it's not surprising that level 3 assertions are not tested regularly and some unexpected issues may arise.

[fingolfin]

If you look at some more of the backtrace, you can see what's happening:

brk> Where(50);
GF( Characteristic( gens ), DegreeFFE( gens ) ) at GAPROOT/lib/ffe.gi:1075 called from
DefaultRingByGenerators( arg[1] ) at GAPROOT/lib/ring.gi:413 called from
DefaultRing( coeff ) at GAPROOT/lib/ratfun1.gi:45 called from
LaurentPolynomialByExtRepNC( fam, cofs, val, ind ) at GAPROOT/lib/ratfunul.gi:42 called from
LaurentPolynomialByCoefficients( fam, cofs, 0, ind ) at GAPROOT/lib/ratfunul.gi:87 called from
UnivariatePolynomialByCoefficients( fam, cp, ind ) at GAPROOT/lib/matrix.gi:467 called from
CharacteristicPolynomialMatrixNC( DefaultFieldOfMatrix( mat ), mat, 1 ) at GAPROOT/lib/matrix.gi:671 called from
CharacteristicPolynomial( mm ) at GAPROOT/lib/matrix.gi:4412 called from
x ^ f[2] at GAPROOT/lib/ratfunul.gi:1119 called from
Value( f, x, One( x ) ) at GAPROOT/lib/ratfunul.gi:1154 called from
Value( cp, imat ) at GAPROOT/lib/matrix.gi:476 called from
CharacteristicPolynomialMatrixNC( DefaultFieldOfMatrix( mat ), mat, 1 ) at GAPROOT/lib/matrix.gi:671 called from
CharacteristicPolynomial( mm ) at GAPROOT/lib/matrix.gi:4412 called from
x ^ f[2] at GAPROOT/lib/ratfunul.gi:1119 called from
Value( f, x, One( x ) ) at GAPROOT/lib/ratfunul.gi:1154 called from
Value( cp, imat ) at GAPROOT/lib/matrix.gi:476 called from
CharacteristicPolynomialMatrixNC( DefaultFieldOfMatrix( mat ), mat, 1 ) at GAPROOT/lib/matrix.gi:671 called from
CharacteristicPolynomial( mm ) at GAPROOT/lib/matrix.gi:4412 called from
x ^ f[2] at GAPROOT/lib/ratfunul.gi:1119 called from

So to evaluate the polynomial, it uses the ^ operator, but that tries to optimize what it does by using the characteristic polynomial...

[hulpke]

So basically this is an issue where the assertion as-is not not work.

I'm changing the title as it is an issue in matrix/polynomial code and not in conjugacy classes.