Over Christmas, David Craven asked me to make a 12474 dimensional representation of 3.F22 over GF(25), which needed to be chopped out of 78 x 5643 = 440,154, all over GF(25). I managed to do this, albeit with a bit of luck, on the St. Andrews machine ‘lovelace’, but it highlighted the difficulty of finding singular elements of the group algebra over such a large field.
This problem was, of course, noticed – and solved – in 1994 by Holt and Rees. The basic idea is to compute the characteristic polynomial of some element of the group algebra, then find the roots of that to determine a suitable scalar to subtract.
I have described in this blog some – as yet unimplemented – ideas as to how to compute the characteristic polynomial at a large scale. I still haven’t done that! What I have done is to write a characteristic polynomial program zcp in the old, obvious way – single core working one vector at a time, with a view to be able to play with it, at least in small dimensions. Also, this program will ultimately be zcp1, available to test a good implementation if and when I get round to it. I have also written a program zhr to find the roots of a polynomial, again with no intelligence – it just tries every root in turn.
To try it out, I computed, on my laptop, a few representations of L3(193) mod 193, and found that it works just fine. For such large fields there seems to be no need to do any multiplications to make group algebra elemens. Using two generators a1=(010 001 100) and a2=(110 010 001) it was always sufficient to use a1 + x.a2 – y, where the method is to make a1 + x.a2, find the characteristic polynomial of that, then find the roots of that to determine y. Most values of x seemed to produce a value of y or two, which was all that was needed.
Once the dimension got above a couple of thousand, the characteristic polynomial step started to take a while – 28 seconds for 2160, for example – so there remains a need for a better characteristic polynomial program. Also to find the roots of that polynomial over the field 37249 (193^2) took 2.3 seconds, so for huge fields, this program will also be a problem.
Nevertheless, a start has been made.