CRISP pcgs error

[hungaborhorvath]

The following code is a rewriting of the original DirectFactorsOfGroup code as

1. to only check direct factors from a given list. This is supposed to enhance speed because after a direct factor is obtained, one does not need to recompute normal subgroups of the factor, but rather pull them from the list;
2. it checks trivial intersection of two normal subgroups by checking if a (generator of a) minimal normal subgroup (again, given by a list) is in both normal subgroups. Again, this should be significantly faster if MinimalNormalSubgroups are computed at the beginning, compared to always intersecting the two normal subgroups.

However, testing shows that on a 96-element group it gives only two direct factors, rather than the correct three, if_CRISP_is_used. Without CRISP it gives the correct result.

The code:

DeclareOperation( "IsTrivialNormalIntersectionInList",[IsList, IsGroup, IsGroup]);
DeclareGlobalFunction( "DirectFactorsOfGroupFromList", [IsGroup, IsList, IsList]);

#############################################################################
##
#M IsTrivialNormalIntersectionInList( , , ) . . . . generic method
##
InstallMethod( IsTrivialNormalIntersectionInList,
"if minimal normal subgroups are computed",
[ IsList, IsGroup, IsGroup ],

function( L, U, V )
local gs;

gs:= List(L, N -> GeneratorsOfGroup(N)[1]);
return ForAll(gs, g -> not g in U or not g in V);

end);

InstallGlobalFunction( DirectFactorsOfGroupFromList,

function ( G, NList, MinList )

local  gs, Ns, MinNs, NNs, MinNNs, facts, sizes, i, j, s1, s2;

if not IsFinite(G) then TryNextMethod(); fi;
Ns := ShallowCopy(NList);
MinNs := ShallowCopy(MinList);
gs := GeneratorsOfGroup(Socle(G));
Ns := Filtered(Ns, N -> not IsSubset(N, gs));
sizes := List(Ns,Size);
SortParallel(sizes,Ns);
for s1 in Difference(Set(sizes),[Size(G),1]) do
  i := PositionSet(sizes,s1);
  s2 := Size(G)/s1;
  if s1 <= s2 then 
    repeat
      if s2 > s1 then
        j := PositionSet(sizes,s2);
        if j = fail then break; fi;
      else 
        j := i + 1;
      fi;
      while j <= Size(sizes) and sizes[j] = s2 do
        if IsTrivialNormalIntersectionInList(MinList,Ns[i],Ns[j]) then
        # Ns[i] is the smallest direct factor, hence direct irreducible
        # we keep from Ns only the subgroups of Ns[j] having size min. s1
          NNs := Filtered(Ns, N -> Size(N) >= s1 and s2 mod Size(N) = 0 
                                            and IsSubset(Ns[j], N)); 
          MinNNs := Filtered(MinNs, N -> s2 mod Size(N) = 0 
                                            and IsSubset(Ns[j], N)); 
          return Union([ Ns[i] ], DirectFactorsOfGroupFromList(Ns[j], 
                    NNs, MinNNs));
        fi;
        j := j + 1;
      od;
      i := i + 1;
    until i>=Size(sizes) or sizes[i] <> s1;
  fi;
od;
return [ G ];

end );

With CRISP I have only two direct factors.

 ┌───────┐   GAP v4.7.8-469-g23ff54d of 2015-10-30 17:11:41 (CET)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
 Packages:   CRISP 1.3.9, GAPDoc 1.5.1
 Try '?help' for help. See also  '?copyright' and  '?authors'
gap> Read("Df.g");
gap> G := Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ]);
Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)
(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ])
gap> DirectFactorsOfGroupFromList(G, NormalSubgroups(G), MinimalNormalSubgroups(G));
[ "permutation group of size 48 with 5 generators", Group([ (3,4)(20,21) ]) ]

The problem with CRISP does not always happen, but if I rerun it, then about every second time it appears. Without CRISP the result is always 3 direct factors, that are isomorphic, but not always the same three:

 ┌───────┐   GAP v4.7.8-469-g23ff54d of 2015-10-30 17:11:26 (CET)
 │  GAP  │   http://www.gap-system.org
 └───────┘   Architecture: x86_64-pc-linux-gnu-gcc-default64
 Libs used:  gmp, readline
 Loading the library and packages ...
 Components: trans 1.0, prim 2.1, small* 1.0, id* 1.0
 Packages:   GAPDoc 1.5.1
 Try '?help' for help. See also  '?copyright' and  '?authors'
gap> Read("Df.g");
gap> G := Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ]);
Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)
(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ])
gap> DirectFactorsOfGroupFromList(G, NormalSubgroups(G), MinimalNormalSubgroups(G));
[ "permutation group of size 24 with 4 generators", Group([ (3,4)(20,21) ]), 
  Group([ (3,4)(10,11) ]) ]
gap> G := Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ]);
Group([ (6,7)(8,9)(10,11)(12,13)(14,15)(16,17)(18,19)(20,21)(22,23)
(24,25), (3,4)(6,8)(13,15)(16,18)(23,25), (8,9)(12,13)(16,17)(20,21)(24,25) ])
gap> DirectFactorsOfGroupFromList(G, NormalSubgroups(G), MinimalNormalSubgroups(G));
[ Group([ (8,9)(10,11)(12,13)(16,17)(24,25), (7,9,8)(12,13,14)(16,19,17)
  (22,24,25), (6,7)(8,9)(12,13)(14,15)(16,17)(18,19)(22,23)(24,25) ]), 
  Group([ (3,4)(20,21) ]), Group([ (3,4)(10,11) ]) ]

Burkhard observed in issue #160 that if one sets the assertion level to 1, a CRISP routine detects an inconsistency: a modulo pcgs returns wrong exponents, e.g., at the break caused by the assertion, enter

ExponentsOfPcElement (gpcgs, gpcgs[1]);

which will return [0,0] instead of [1,0].

Could someone please diagnose this? The above code would be crucial for a new DirectFactorsOfGroup code, but currently I cannot test it properly. Thank you.

Edit: apparently "permutation group of size 24 with 4 generators" and "permutation group of size 48 with 5 generators" are not visible if I put them between smaller and bigger signs as they appear in GAP output. I put them inside apostrophes.

[fingolfin]

I took the liberty of editing your submission slightly for readability.

[fingolfin]

To anybody reading this: Please note that issue #160 actually already has some discussion on this (@hungaborhorvath it would have saved me some time if you had mentioned that ;-). In particluar, @bh11 did some tests which indicate that this may be a regression on the master branch, as it does not occur with stable-4.7.

[fingolfin]

I used git bisect in the old (private :-/) Mercurial repository for GAP, and tracked the issue down to a merge commit by @hulpke:

changeset:   20228:ad9b55b190cd
branch:      ah/feature
parent:      20225:246fc2f508e8
parent:      20227:e8598d3f2134
user:        Alexander Hulpke <[email protected]>
date:        Thu Sep 04 10:19:04 2014 -0600
description:
Merge default.

The issue occurs in neither parent, it seems. So I looked at the diff to the previous state of the master branch, and some guessing finally lead me to this commit:

changeset:   20192:1744d5f040c8
user:        Alexander Hulpke <[email protected]>
date:        Sun Aug 31 12:35:10 2014 -0600
files:       lib/pcgsind.gi
description:
Added method to inherit IndicesNormalSteps.


diff --git a/lib/pcgsind.gi b/lib/pcgsind.gi
--- a/lib/pcgsind.gi
+++ b/lib/pcgsind.gi
@@ -1692,4 +1692,31 @@ end );

 #############################################################################
 ##
+#M  IndicesNormalSteps( <ipcgs> )
+##
+InstallMethod(IndicesNormalSteps,"inherit from parent",true,
+  [IsInducedPcgs and HasParentPcgs],0,
+function(pcgs)
+local l,i,p,ind,a,b,d;
+  p:=ParentPcgs(pcgs);
+  if not HasIndicesNormalSteps(p) then
+    TryNextMethod();
+  fi;
+  d:=pcgs!.depthsInParent;
+  ind:=[];
+  a:=1;
+  for i in IndicesNormalSteps(p) do
+    b:=First([a..Length(d)],x->d[x]>=i);
+    if b<>fail then
+      if not b in ind then
+   Add(ind,b);
+      fi;
+      a:=b;
+    fi;
+  od;
+  return ind;
+end);
+
+#############################################################################
+##
 #E  pcgsind.gi     . . . . . . . . . . . . . . . . . . . . . . . . . . ends here

Reversing that commit (i.e. removing that method) resolves the problem.

So perhaps that method does something wrong. Or maybe it is perfectly right, but something else relies on it not being there. Or...??? Perhaps @hulpke knows more?

[hungaborhorvath]

Thank you for editing my post, I have no idea how to properly format or post here. I even mentioned issue 160 in my original post, but apparently, it was not readable because of the formatting. Sorry.

[fingolfin]

@hungaborhorvath You did mention issue #160 in your original post, and it was quite readable (BTW: the way to make it into a hyperlink is to add a hash sign # in front of th enumber. More information on this and other styling options can be found by clicking the Styling with Markdown is suported link which is shown over the text entry field).

My point just was: What you wrote didn't make clear to methat behind this link I would find additional information on this issue, and the start of a full discussion of it; the fact that the link comes after dozens of lines of text doesn't help. So perhaps starting the report like this would have helped: "The following problem has already been discussed at issue #160, but since that issue is really about something else, I decided to open a new issue for it."

Anyway, this is really not important :). Let me stick to the more importan point: Thank you for taking the time to report an issue! I hope we'll be able to resolve it.

[hulpke]

@fingolfin I don't see an problem in the code of mine you quote. It simply copies the indices at while el. ab. layers start from a parent, if the parent has such indices stored. (This was necessary to deal efficiently with subgroups in some situations. Please do not remove it.)
If you want I will add an assertion that tests that the indices are OK.

I'm not sure about the logic of blaming this library routine: Without the package the calculation works OK. With the package it runs in an error. The library change thus exposes an issue in the package.

(CRISP is providing alternate methods for some PCGS functions that also have code in the library. I am not sure whether these are really needed. If they are more efficient I would argue that they should be in the library and not in a package, as the current setup makes it easy to get such inconsistencies.)

[fingolfin]

@hulpke Sorry for being unclear, I never meant to say or suggest that the above commit is at fault, nor that it shold be undone. And in particular, I did not mean to assign any kind of blame, least of all to you!

But I think knowing about the involement of this commit in the issue at hand is helpful for debugging it. After all, we have an issue that does not occur without CRISP, but also not with CRISP and GAP 4.7. And now we know which change in GAP 4.7 -> 4.8 triggers the issue. This is purely a matter of determining the facts.

Now that we know that temporarily removing that GAP method (in your local copy of the code, I mean, not the repository) avoids the issue, I hope this can help @bh11 to debug it and find the true cause.

Finally I also think that it is risky that CRISP modifies library functions for PCGS'es the way it does; it necessarily relies on internal APIs; and this makes it likely that there will be breakage whenver the library PCGS code gets changed. So on the long run, I think it would be useful to change that. But this is likely not something that can be done quickly, and fixing this issue would be nice on the short run, too.

[bh11]

@fingolfin It's not true that CRISP relies on internal GAP APIs - it exclusively only uses documented GAP functionality to create new pcgs when needed, and also installs a few new methods for existing documented operations. I can see nothing wrong with that.

Since the bug mainifests itself in GAP code which I don't understand (with a modulo pcgs created by CRISP using standard library methods), I currently don't see how I can make any progress.

[ChrisJefferson]

@bh11 : Can you provide an example of this bug, where CRISP is not loaded (so extract the pcgs)? Sorry if this already exists, and I've missed it!

[fingolfin]

@bh11: To quote the CRIPS source code, file lib/pcgscache.gi:

#M  InducedPcgs (<pcgs>, <grp>)
##
##  WARNING: this function replaces the standard library function - if this
##  library function changes, presumably also this function will have to be
##  changed. Also it uses the undocumented attribute HomePcgs.

UPDATE: Aha, but it turns out that this file is not loaded at all.

[bh11]

Just had a look at IndicesNormalSteps: imo, this method is wrong because it does not check if additional indices become normal in the smaller group. I'm not sure how this is related to the bug, CRISP doesn't use "IndicesNormalSteps".

[bh11]

@fingolfin: The pcgs cache code has long been moved into the main GAP library (to avoid the mentioned problems). It's only there in CRISP to provide backward compatibility with GAP 4.4, and does not load in recent versions of GAP. But probably it's a good idea to get rid of it altogether, and to drop GAP 4.4 compatibility.

[hulpke]

I've looked more at the bug and tried to find where things diverge. Luckily it seems the different PCGS methods -- though I still think it is not a good idea to have this in a package -- seem to be unrelated.

A binary search through the code of CRISP indicates that the error arises through its method for Socle -- in the course of the calculation the sole of a permutation group of order 48 is computed wrongly as of order 2, while it has order 8. This depends on the group already having stored some information, so it cannot be easily isolated.

Looking at the code in CRISP, it calls it for a particular ChiefSeries of the group. There is no guarantee that for a group the chief series stored agrees with a stored PCGS or its IndicesNormalSteps, but it might be always happen to be true for PC groups. It does not hold for the permutation group in question.

Indeed, if I slightly edit the method to ensure PCGS and series compatibility:

InstallMethod (SolvableSocleComponents,
  "for solvable group", true, 
  [IsGroup and IsFinite and CanEasilyComputePcgs],
  0,
  function( G )
local ser,pcgs;
      if IsTrivial (G) then
        return [];
      else
        p:=Pcgs(G); 
        ser:=EANormalSeriesByPcgs(p); # old code used `ChiefSeries'
        return SolvableSocleComponentsBySeries (G, ser);
      fi;
  end);

the problem vanishes. I suspect that is the cause.

[bh11]

@hulpke: No, the code in SolvableSocleComponents makes no assumption about ser and any pcgs. Indeed, this is a very common situation in CRISP. EANormalSeriesByPcgs, otoh, isn't guaranteed to return a chief series, and will therefore not work in general.

[hulpke]

@bh11 Ah -- I have used `IndicesNormalSteps' to not require maximum refinement (but give layer steps at which lifting is possible). I will have to separate this into another attribute that does not require this maximal refinement.

[bh11]

@hulpke: Seems that, indeed, the new IndicesNormalSteps method is the cause of the problem. It's being used (by some function in the GAP library) just before the problem arises. There seems to be an unwritten (?) convention that all IndicesXXX functions for pcgs add a last entry denoting the trivial subgroup (i.e., Length(pcgs)+1). Adding such an entry in your method already suffices to get rid of the bug.

Btw., do you really have to introduce a new attribute? There are lots of IndicesXXX attributes available which are intended as more efficient replacements of IndicesNormalSteps and which can be "inherited" by induced pcgs using code like yours.

[hulpke]

I have replaced uses of IndicesNormalSteps' (which is ill defined and already labelled in parts of the library asobsolete') with IndicesEANormalSteps in my code that inherits PCGS and used the fitting-free method. I presume that will remove the problem.

[bh11]

Looks good to me – the bug is gone.

[fingolfin]

For future reference, the commit fixing this was ee365a4

@bh11 @hulpke Thank you very much for talking this out and resolving it.