Adding consistency tests & fixing data issues

[fingolfin]

Inspired by #186 (comment) I thought this would be a good thing for a consistency test...

I think we should add this and other such tests somewhere. Ideally so that one can run them once, now, and fix issues; or run them on new tables as we add them. If they are fast enough we can also run them in PR CI tests, or at least in a daily cron job.

The first test inspired by the above, is this:

for nam in genchartab()
  println(nam)
  g = genchartab(nam)
  o = sum(nrchars(c)*degree(c)^2 for c in g)
  if o != order(g)
    println("  expected: ", order(g))
    println("    actual: ", o)
  end
end

It ends up reporting a few inconsistencies:

GU3
PGU3.2
PGU3.n2
PSU3.2
PSU3.n2
SU3.2
SU3.n2
2B2
Sz
uni2D4.0
  expected: q^30 - 2*q^28 + q^26 - q^24 + q^22 + q^20 - q^18 + q^16 - 2*q^14 + q^12
    actual: q^24 + q^22 + q^20 + 5*q^18 + 6*q^16 + 6*q^14 + 8*q^12 + 6*q^10 + 6*q^8 + 5*q^6 + q^4 + q^2 + 1
uni2D4.1
  expected: q^30 - 2*q^28 + q^26 - q^24 + q^22 + q^20 - q^18 + q^16 - 2*q^14 + q^12
    actual: q^24 + q^22 + q^20 + 5*q^18 + 6*q^16 + 6*q^14 + 8*q^12 + 6*q^10 + 6*q^8 + 5*q^6 + q^4 + q^2 + 1
2F4.1
  expected: 67108864*q0^52 - 33554432*q0^50 + 8388608*q0^46 - 8388608*q0^44 + 2097152*q0^42 + 1048576*q0^40 - 1048576*q0^38 + 262144*q0^36 + 131072*q0^34 - 131072*q0^32 + 32768*q0^30 - 8192*q0^26 + 4096*q0^24
    actual: 197132288//3*q0^52 - 142606336//3*q0^50 + 7340032*q0^48 + 67108864//3*q0^46 - 45875200//3*q0^44 - 3407872*q0^42 + 4980736*q0^40 + 2097152//3*q0^38 - 1228800*q0^36 - 1507328//3*q0^34 + 413696*q0^32 + 270336*q0^30 - 219136*q0^28 - 201728//3*q0^26 + 83200*q0^24 + 8192//3*q0^22 - 64832//3*q0^20 + 3264*q0^18 + 3904*q0^16 - 3872//3*q0^14 - 420*q0^12 + 752//3*q0^10 + 15*q0^8 - 28*q0^6 + 19//12*q0^4 + 7//4*q0^2
2F4.2
  expected: 67108864*q0^52 - 33554432*q0^50 + 8388608*q0^46 - 8388608*q0^44 + 2097152*q0^42 + 1048576*q0^40 - 1048576*q0^38 + 262144*q0^36 + 131072*q0^34 - 131072*q0^32 + 32768*q0^30 - 8192*q0^26 + 4096*q0^24
    actual: 197132288//3*q0^52 - 142606336//3*q0^50 + 7340032*q0^48 + 67108864//3*q0^46 - 45875200//3*q0^44 - 3407872*q0^42 + 4980736*q0^40 + 2097152//3*q0^38 - 1228800*q0^36 - 1507328//3*q0^34 + 413696*q0^32 + 270336*q0^30 - 219136*q0^28 - 201728//3*q0^26 + 83200*q0^24 + 8192//3*q0^22 - 64832//3*q0^20 + 3264*q0^18 + 3904*q0^16 - 3872//3*q0^14 - 420*q0^12 + 752//3*q0^10 + 15*q0^8 - 28*q0^6 + 19//12*q0^4 + 7//4*q0^2
Ree.1
  expected: 67108864*q0^52 - 33554432*q0^50 + 8388608*q0^46 - 8388608*q0^44 + 2097152*q0^42 + 1048576*q0^40 - 1048576*q0^38 + 262144*q0^36 + 131072*q0^34 - 131072*q0^32 + 32768*q0^30 - 8192*q0^26 + 4096*q0^24
    actual: 197132288//3*q0^52 - 142606336//3*q0^50 + 7340032*q0^48 + 67108864//3*q0^46 - 45875200//3*q0^44 - 3407872*q0^42 + 4980736*q0^40 + 2097152//3*q0^38 - 1228800*q0^36 - 1507328//3*q0^34 + 413696*q0^32 + 270336*q0^30 - 219136*q0^28 - 201728//3*q0^26 + 83200*q0^24 + 8192//3*q0^22 - 64832//3*q0^20 + 3264*q0^18 + 3904*q0^16 - 3872//3*q0^14 - 420*q0^12 + 752//3*q0^10 + 15*q0^8 - 28*q0^6 + 19//12*q0^4 + 7//4*q0^2
Ree.2
  expected: 67108864*q0^52 - 33554432*q0^50 + 8388608*q0^46 - 8388608*q0^44 + 2097152*q0^42 + 1048576*q0^40 - 1048576*q0^38 + 262144*q0^36 + 131072*q0^34 - 131072*q0^32 + 32768*q0^30 - 8192*q0^26 + 4096*q0^24
    actual: 197132288//3*q0^52 - 142606336//3*q0^50 + 7340032*q0^48 + 67108864//3*q0^46 - 45875200//3*q0^44 - 3407872*q0^42 + 4980736*q0^40 + 2097152//3*q0^38 - 1228800*q0^36 - 1507328//3*q0^34 + 413696*q0^32 + 270336*q0^30 - 219136*q0^28 - 201728//3*q0^26 + 83200*q0^24 + 8192//3*q0^22 - 64832//3*q0^20 + 3264*q0^18 + 3904*q0^16 - 3872//3*q0^14 - 420*q0^12 + 752//3*q0^10 + 15*q0^8 - 28*q0^6 + 19//12*q0^4 + 7//4*q0^2
2G2
ree
3D4.0
3D4.11
3D4.13
GL2
GU2
PGL2.0
PGL2.1
PSL2.0
PSL2.1
PSL2.3
SL2.0
SL2.1
GL3
PGL3.1
PGL3.n1
PSL3.1
PSL3.n1
SL3.1
SL3.n1
Sp4.0
uniCSp4.1
  expected: q^11 - q^10 - q^9 + q^8 - q^7 + q^6 + q^5 - q^4
    actual: q^8 + q^6 + 4*q^4 + q^2 + 1
CSp6.1
Sp6.0
uniCSp6.1
  expected: q^22 - q^21 - q^20 + q^19 - q^18 + q^17 + q^14 - q^13 + q^12 - q^11 - q^10 + q^9
    actual: q^18 + q^16 + 4*q^14 + 9*q^12 + 9*q^10 + 9*q^8 + 9*q^6 + 4*q^4 + q^2 + 1
uniSp6.0
  expected: q^21 - q^19 - q^17 + q^13 + q^11 - q^9
    actual: q^18 + q^16 + 4*q^14 + 9*q^12 + 9*q^10 + 9*q^8 + 9*q^6 + 4*q^4 + q^2 + 1
uniCSpin8.1
  expected: q^30 - 2*q^29 + 2*q^27 - 3*q^26 + 4*q^25 - q^24 - 2*q^23 + 3*q^22 - 4*q^21 + 3*q^20 - 2*q^19 - q^18 + 4*q^17 - 3*q^16 + 2*q^15 - 2*q^13 + q^12
    actual: q^24 + q^22 + 7*q^20 + 13*q^18 + 24*q^16 + 30*q^14 + 40*q^12 + 30*q^10 + 24*q^8 + 13*q^6 + 7*q^4 + q^2 + 1
uniSpin8.0
  expected: q^28 - q^26 - 2*q^24 + q^22 + 2*q^20 + q^18 - 2*q^16 - q^14 + q^12
    actual: q^24 + q^22 + 7*q^20 + 13*q^18 + 24*q^16 + 30*q^14 + 40*q^12 + 30*q^10 + 24*q^8 + 13*q^6 + 7*q^4 + q^2 + 1
uniuniF4p2
  expected: q^52 - q^50 - q^46 + q^42 - q^40 + 2*q^38 - q^36 + q^34 - q^30 - q^26 + q^24
    actual: q^48 + q^46 + q^44 + 6*q^42 + 14*q^40 + 14*q^38 + 42*q^36 + 47*q^34 + 68*q^32 + 92*q^30 + 111*q^28 + 104*q^26 + 150*q^24 + 104*q^22 + 111*q^20 + 92*q^18 + 68*q^16 + 47*q^14 + 42*q^12 + 14*q^10 + 14*q^8 + 6*q^6 + q^4 + q^2 + 1
G2.01
G2.02
G2.101
G2.103
G2.111
G2.113
G2.121
G2.123
uniGL2
  expected: q^4 - q^3 - q^2 + q
    actual: q^2 + 1
uniGL3
  expected: q^9 - q^8 - q^7 + q^5 + q^4 - q^3
    actual: q^6 + q^4 + 2*q^3 + q^2 + 1
uniGL4
  expected: q^16 - q^15 - q^14 + 2*q^11 - q^8 - q^7 + q^6
    actual: q^12 + q^10 + 2*q^9 + 4*q^8 + 2*q^7 + 4*q^6 + 2*q^5 + 4*q^4 + 2*q^3 + q^2 + 1
uniGL5
  expected: q^25 - q^24 - q^23 + q^20 + q^19 + q^18 - q^17 - q^16 - q^15 + q^12 + q^11 - q^10
    actual: q^20 + q^18 + 2*q^17 + 4*q^16 + 6*q^15 + 7*q^14 + 8*q^13 + 12*q^12 + 12*q^11 + 14*q^10 + 12*q^9 + 12*q^8 + 8*q^7 + 7*q^6 + 6*q^5 + 4*q^4 + 2*q^3 + q^2 + 1
uniGL6
  expected: q^36 - q^35 - q^34 + q^31 + 2*q^29 - q^27 - q^26 - q^25 - q^24 + 2*q^22 + q^20 - q^17 - q^16 + q^15
    actual: q^30 + q^28 + 2*q^27 + 4*q^26 + 6*q^25 + 12*q^24 + 12*q^23 + 21*q^22 + 26*q^21 + 37*q^20 + 40*q^19 + 55*q^18 + 52*q^17 + 61*q^16 + 60*q^15 + 61*q^14 + 52*q^13 + 55*q^12 + 40*q^11 + 37*q^10 + 26*q^9 + 21*q^8 + 12*q^7 + 12*q^6 + 6*q^5 + 4*q^4 + 2*q^3 + q^2 + 1
uniGL7
  expected: q^49 - q^48 - q^47 + q^44 + q^42 + q^41 - q^39 - q^38 - 2*q^37 + 2*q^33 + q^32 + q^31 - q^29 - q^28 - q^26 + q^23 + q^22 - q^21
    actual: q^42 + q^40 + 2*q^39 + 4*q^38 + 6*q^37 + 12*q^36 + 18*q^35 + 26*q^34 + 38*q^33 + 57*q^32 + 76*q^31 + 107*q^30 + 132*q^29 + 170*q^28 + 204*q^27 + 241*q^26 + 272*q^25 + 308*q^24 + 326*q^23 + 345*q^22 + 348*q^21 + 345*q^20 + 326*q^19 + 308*q^18 + 272*q^17 + 241*q^16 + 204*q^15 + 170*q^14 + 132*q^13 + 107*q^12 + 76*q^11 + 57*q^10 + 38*q^9 + 26*q^8 + 18*q^7 + 12*q^6 + 6*q^5 + 4*q^4 + 2*q^3 + q^2 + 1
uniGL8
  expected: q^64 - q^63 - q^62 + q^59 + q^57 + q^55 - q^53 - 2*q^52 - q^51 - q^49 + q^48 + q^47 + 2*q^46 + q^45 + q^44 - q^43 - q^41 - 2*q^40 - q^39 + q^37 + q^35 + q^33 - q^30 - q^29 + q^28
    actual: q^56 + q^54 + 2*q^53 + 4*q^52 + 6*q^51 + 12*q^50 + 18*q^49 + 33*q^48 + 44*q^47 + 72*q^46 + 102*q^45 + 156*q^44 + 208*q^43 + 298*q^42 + 386*q^41 + 520*q^40 + 646*q^39 + 827*q^38 + 990*q^37 + 1210*q^36 + 1390*q^35 + 1616*q^34 + 1788*q^33 + 1996*q^32 + 2110*q^31 + 2254*q^30 + 2294*q^29 + 2352*q^28 + 2294*q^27 + 2254*q^26 + 2110*q^25 + 1996*q^24 + 1788*q^23 + 1616*q^22 + 1390*q^21 + 1210*q^20 + 990*q^19 + 827*q^18 + 646*q^17 + 520*q^16 + 386*q^15 + 298*q^14 + 208*q^13 + 156*q^12 + 102*q^11 + 72*q^10 + 44*q^9 + 33*q^8 + 18*q^7 + 12*q^6 + 6*q^5 + 4*q^4 + 2*q^3 + q^2 + 1
uniGU2
  expected: q^4 + q^3 - q^2 - q
    actual: q^2 + 1
uniGU3
  expected: q^9 + q^8 - q^7 + q^5 - q^4 - q^3
    actual: q^6 + q^4 - 2*q^3 + q^2 + 1
uniGU4
  expected: q^16 + q^15 - q^14 - 2*q^11 - q^8 + q^7 + q^6
    actual: q^12 + q^10 - 2*q^9 + 4*q^8 - 2*q^7 + 4*q^6 - 2*q^5 + 4*q^4 - 2*q^3 + q^2 + 1
uniGU5
  expected: q^25 + q^24 - q^23 - q^20 + q^19 - q^18 - q^17 + q^16 - q^15 - q^12 + q^11 + q^10
    actual: q^20 + q^18 - 2*q^17 + 4*q^16 - 6*q^15 + 7*q^14 - 8*q^13 + 12*q^12 - 12*q^11 + 14*q^10 - 12*q^9 + 12*q^8 - 8*q^7 + 7*q^6 - 6*q^5 + 4*q^4 - 2*q^3 + q^2 + 1
uniGU6
  expected: q^36 + q^35 - q^34 - q^31 - 2*q^29 + q^27 - q^26 + q^25 - q^24 + 2*q^22 + q^20 + q^17 - q^16 - q^15
    actual: q^30 + q^28 - 2*q^27 + 4*q^26 - 6*q^25 + 12*q^24 - 12*q^23 + 21*q^22 - 26*q^21 + 37*q^20 - 40*q^19 + 55*q^18 - 52*q^17 + 61*q^16 - 60*q^15 + 61*q^14 - 52*q^13 + 55*q^12 - 40*q^11 + 37*q^10 - 26*q^9 + 21*q^8 - 12*q^7 + 12*q^6 - 6*q^5 + 4*q^4 - 2*q^3 + q^2 + 1
uniGU7
  expected: q^49 + q^48 - q^47 - q^44 - q^42 + q^41 - q^39 + q^38 - 2*q^37 + 2*q^33 - q^32 + q^31 - q^29 + q^28 + q^26 + q^23 - q^22 - q^21
    actual: q^42 + q^40 - 2*q^39 + 4*q^38 - 6*q^37 + 12*q^36 - 18*q^35 + 26*q^34 - 38*q^33 + 57*q^32 - 76*q^31 + 107*q^30 - 132*q^29 + 170*q^28 - 204*q^27 + 241*q^26 - 272*q^25 + 308*q^24 - 326*q^23 + 345*q^22 - 348*q^21 + 345*q^20 - 326*q^19 + 308*q^18 - 272*q^17 + 241*q^16 - 204*q^15 + 170*q^14 - 132*q^13 + 107*q^12 - 76*q^11 + 57*q^10 - 38*q^9 + 26*q^8 - 18*q^7 + 12*q^6 - 6*q^5 + 4*q^4 - 2*q^3 + q^2 + 1
uniGU8
  expected: q^64 + q^63 - q^62 - q^59 - q^57 - q^55 + q^53 - 2*q^52 + q^51 + q^49 + q^48 - q^47 + 2*q^46 - q^45 + q^44 + q^43 + q^41 - 2*q^40 + q^39 - q^37 - q^35 - q^33 - q^30 + q^29 + q^28
    actual: q^56 + q^54 - 2*q^53 + 4*q^52 - 6*q^51 + 12*q^50 - 18*q^49 + 33*q^48 - 44*q^47 + 72*q^46 - 102*q^45 + 156*q^44 - 208*q^43 + 298*q^42 - 386*q^41 + 520*q^40 - 646*q^39 + 827*q^38 - 990*q^37 + 1210*q^36 - 1390*q^35 + 1616*q^34 - 1788*q^33 + 1996*q^32 - 2110*q^31 + 2254*q^30 - 2294*q^29 + 2352*q^28 - 2294*q^27 + 2254*q^26 - 2110*q^25 + 1996*q^24 - 1788*q^23 + 1616*q^22 - 1390*q^21 + 1210*q^20 - 990*q^19 + 827*q^18 - 646*q^17 + 520*q^16 - 386*q^15 + 298*q^14 - 208*q^13 + 156*q^12 - 102*q^11 + 72*q^10 - 44*q^9 + 33*q^8 - 18*q^7 + 12*q^6 - 6*q^5 + 4*q^4 - 2*q^3 + q^2 + 1

[fingolfin]

The moment I pressed "submit" it finished "CSp6", reported a few more inconsistencies and then did run into another instance of that error, this time for "G2".

I've narrowed down the error and will post it as a separate issue.

[fingolfin]

The uni tables I believe are tables which are incomplete and only include unipotent characters. Thus some difference is to be expected. And the 2F4 = Ree issues are the same as issue #117.

So we are in a good state. We could add this as test, just modified to skip tables starting with uni and the 2F4 / Ree tables.

[SoongNoonien]

The uni tables I believe are tables which are incomplete and only include unipotent characters. Thus some difference is to be expected.

Yes, exactly.

We could add this as test, just modified to skip tables starting with uni and the 2F4 / Ree tables.

We import all the tables anyway so adding this should be easy.

How long did it take to finish on your machine?

[fingolfin]

Two minutes for this:

@time for nam in genchartab()
  # skip tables containing only unipotent character types
  startswith(nam, "uni") && continue

  # workaround issue #117
  startswith(nam, "2F4") && continue
  startswith(nam, "Ree") && continue

  println(nam)
  g = genchartab(nam)
  o = sum(nrchars(c)*degree(c)^2 for c in g)
  if o != order(g)
    println("  expected: ", order(g))
    println("  actual: ", o)
  end
end

By far the slowest is CSp6.1. It takes 90 seconds, so the rest is just 30 seconds.

[SoongNoonien]

Should we skip CSp6.1 then?

[fingolfin]

Sure. But we should add a comment saying why we skip it. I just had a look, it seems this is by far the largest table, the file is ~1.6 MB (next largest is Sp6.0 with just ~360kb. It seems simply loading it takes 88 seconds and allocates 120 GB memory (not all at once, luckily):

julia> @time T = genchartab("CSp6.1");
 88.196819 seconds (526.69 M allocations: 118.594 GiB, 14.42% gc time, 0.06% compilation time)

Seems most of this is for simplification: if I change

function (R::GenericCycloRing)(f::Dict{UPolyFrac, UPoly}; simplify::Bool=true)

by switching the default value to false. Then loading is down to 18 seconds, memory to 8GB:

julia> @time T = genchartab("CSp6.1");
 17.917337 seconds (61.72 M allocations: 14.663 GiB, 15.66% gc time, 2.11% compilation time: 84% of which was recompilation)

So on the one hand we probably should switch to JSON eventually. But on the other hand, I really wonder if we can't optimize the simplification rules.

For example, if there is a single summand and the numerator or denominator is 1, we don't need to simplify, do we?

It also seems pointless to re-compute substitute and substitute_inv again and again; perhaps they could be cached in the ring next to the congruence (setcongruence could store it there).

And then it turns out FracElem is rather inefficient; its numerator and denominator methods by default try to canonicalise again and again. And then even hashing them takes time

function Base.hash(a::FracElem, h::UInt)
   b = 0x8a30b0d963237dd5%UInt
   # We canonicalise before hashing
   return xor(b, hash(numerator(a, true), h), hash(denominator(a, true), h), h)
end

and we have

julia> @time hash(gp, zero(UInt))
  0.000016 seconds (32 allocations: 3.734 KiB)

But the majority work is spent in evaluate.

[SoongNoonien]

It seems simply loading it takes 88 seconds and allocates 120 GB memory (not all at once, luckily)

Ok, but this is done already in the tests. So computing the order is just 12 seconds.

[SoongNoonien]

I've added the group order test in #196 and it seems to be fast enough.