Update ThrowAwayFixedPoints

[ssiccha]

Also lets ThrowAwayFixedPoints create a homomorphism if the input group is primitive and has fixed points.

Fixes #190.

[codecov[bot]]

Codecov Report

Merging #191 (6d37718) into master (f4cf7d3) will decrease coverage by 0.07%. The diff coverage is 100.00%.

:exclamation: Current head 6d37718 differs from pull request most recent head bca52ef. Consider uploading reports for the commit bca52ef to get more accurate results

@@            Coverage Diff             @@
##           master     #191      +/-   ##
==========================================
- Coverage   77.76%   77.69%   -0.08%     
==========================================
  Files          37       37              
  Lines       17497    17342     -155     
==========================================
- Hits        13606    13473     -133     
+ Misses       3891     3869      -22     

Impacted Files	Coverage Δ
gap/base/methsel.gd	100.00% <ø> (ø)
gap/perm.gi	97.74% <100.00%> (-0.03%)	:arrow_down:
gap/perm/largebase.gi	82.44% <100.00%> (+0.06%)	:arrow_up:
gap/base/hack.g	82.14% <0.00%> (-7.86%)	:arrow_down:
gap/base/recognition.gi	69.51% <0.00%> (-1.40%)	:arrow_down:
gap/projective/d247.gi	75.07% <0.00%> (-1.28%)	:arrow_down:
gap/projective/almostsimple.gi	65.60% <0.00%> (-0.77%)	:arrow_down:
gap/projective.gi	88.41% <0.00%> (-0.66%)	:arrow_down:
gap/projective/findnormal.gi	77.74% <0.00%> (-0.37%)	:arrow_down:
gap/matrix.gi	91.06% <0.00%> (-0.09%)	:arrow_down:
... and 9 more

[ssiccha]

So, on the upside this fixes #190. On the downside recognition of a large base primitive groups with fixed points takes 20 seconds compared to 2 seconds for an isomorphic group but without fixed points.

Here is an example run:

gap> S23OnSets := Action(SymmetricGroup(23), Combinations([1 .. 23], 2), OnSets);;
gap> jellyGroup2 := WreathProductProductAction(S23OnSets, Group((1,2)));;
gap> n := NrMovedPoints(jellyGroup2);
64009
gap> ri2 := RecogniseGroup(jellyGroup2); time;
F pts= 64009  0        
<recoginfo LargeBasePrimitive
 F:<recoginfo Imprimitive
    F:<recoginfo Pcgs Size=2>
    K:<recoginfo BalTreeForBlocks
       F:<recoginfo Giant AlmostSimple Size=25852016738884976640000>
       K:<recoginfo ThrowAwayFixedPoints
          F:<recoginfo Giant AlmostSimple Size=25852016738884976640000>
          K:<trivial kernel>>>
 K:<trivial kernel>
1891
gap> random := Random(SymmetricGroup(5 * QuoInt(n,2)));;
gap> jellyGroup2Conj := jellyGroup2 ^ random;;
gap> ri2Conj := RecogniseGroup(jellyGroup2Conj); time;
F pts=160018  0         
<recoginfo ThrowAwayFixedPoints
 F:<recoginfo LargeBasePrimitive
    F:<recoginfo Imprimitive
       F:<recoginfo Pcgs Size=2>
       K:<recoginfo BalTreeForBlocks
          F:<recoginfo Giant AlmostSimple Size=25852016738884976640000>
          K:<recoginfo ThrowAwayFixedPoints
             F:<recoginfo Giant AlmostSimple Size=25852016738884976640000>
             K:<trivial kernel>>>
    K:<trivial kernel>
 K:<trivial kernel>
22211

I'm looking into a profile now and it seems like two things make this so slow

• the IsPrimitive check I added is super expensive because computing the blocks takes ages
• the multiplication of group elements with memory becomes very expensive, in the sense of that it gets executed very often

[ssiccha]

Hm, apparently the IsPrimitive call in the second level of the tree, that is directly after applying ThrowAwayFixedPoints for the first time, takes super long.

[ssiccha]

@fingolfin I just pushed a version that I think does the trick. The tests I added take roughly 17 seconds on my machine. Do you think that is too much for the quick testsuite?

[ssiccha]

Hmm, does this brake something in tst/working/quick/ProjLowIndex.tst?

[ssiccha]

The test-suite ran into a failure in ProjLowIndex.tst. I was able to reproduce that on my machine by executing tst/testquick.g. However, I also ran ProjLowIndex.tst a thousand times both with the current master branch and with this PR just to make sure, that this PR does not by some weird quirk introduce a regression. With this PR the test fails three out of a thousand times. In master it fails four out of a thousand times.

So by a big coincidence, when arriving at ProjLowIndex.tst in the test suite this PR exactly hit a random state, such that the group in ProjLowIndex.tst is recognized incorrectly.

I have thus changed the test in PermLargeBasePrimitive.tst to use a smaller group. Which has the benefit that a) the test runs quicker and b) ProjLowIndex.tst also passes again.

[ssiccha]

@fingolfin I have adjusted and integrated your suggestion into the documentation of LargeBasePrimitive. I've also added a short explanation to the documentation of ThrowAwayFixedPoints. Could you have a look again to see whether it is now clear how large base primitive groups with fixed points are handled?