Setwise stabiliser and random Schreier-Sims

[PoslavskySV]

I am new to GAP and I would like to find setwise stabiliser for some permutation group. While playing with genss, I've found the following potential issue. Consider the code:

while true do
   g := PrimitiveGroup(9, 5);
   actual := SetwiseStabilizer(g, OnPoints, [3]).setstab;
   expected := Stabilizer(g, 3);
   if actual <> expected then
       Error("Not equal.");
   fi;
od;

The above code throws exception at some iteration, while it should not. If I understand correctly, this is because SetwiseStabilizer function uses randomised Schreier-Sims to construct BSGS, and there is a probability to obtain incomplete BSGS, so backtrack search fails. Is it possible to specify group order to SetwiseStabilizer, so it will use randomised Schreier-Sims with known order and will always produce valid BSGS and backtrack search will always complete?

[markuspf]

Dear PoslavskySV

On Mon, Jan 05, 2015 at 05:54:08AM -0800, PoslavskySV wrote:

I am new to GAP and I would like to find setwise stabiliser for some
permutation group. While playing with genss, I've found the following potential
issue. Consider the code:

while true do
g := PrimitiveGroup(9, 5);
actual := SetwiseStabilizer(g, OnPoints, [3]).setstab;
expected := Stabilizer(g, 3);
if actual <> expected then
Error("Not equal.");
fi;
od;

The above code throws exception at some iteration, while it should not. If I
understand correctly, this is because SetwiseStabilizer function uses
randomised Schreier-Sims to construct BSGS, and there is a probability to
obtain incomplete BSGS, so backtrack search fails. Is it possible to specify
group order to SetwiseStabilizer, so it will use randomised Schreier-Sims with
known order and will always produce valid BSGS and backtrack search will always
complete?

Examining the results of SetwiseStabilizer, the group size is correct (144), even
when the result of the stabilizer computation isn't. I'll have
to look more closely as to why genss seems to be missing a generator from the
result.

As far as I can see there is no way to pass the size of the group directly
into SetwiseStabilizer, and I'll also have to look whether the group size
(which is known from the start) is used for verification in the stabilizer
chain code.

Cheers,
Markus

[PoslavskySV]

Dear Markus,

Thank you very much for quick response! I'll follow closely the updates of this issue.

Best,
Stanislav

[fingolfin]

So I added a change which resolves this particular issue, and which will be in the next genss release. However, I am concerned that my change is simply hiding a deeper issue. In particular, I am wondering whether the code computing the stabilizer chain is buggy or not. If anybody knows more about the internals of genss and wants to chime in, that would be great. Here are the details:

I tried the given example in slightly modified form and recorded the output of SetwiseStabilizer for one of the problematic case in the variable sw. The stabilizer chain looks right on the surface, but something is fishy:

gap> S := sw.S;
<stabchain size=144 orblen=9 layer=1 SchreierDepth=3>
 <stabchain size=16 orblen=8 layer=2 SchreierDepth=3>
  <stabchain size=2 orblen=2 layer=3 SchreierDepth=1>
gap> Size(Group(S!.orb!.gens));
144
gap> Size(Group(S!.stab!.orb!.gens));
8
gap> Size(Group(S!.stab!.stab!.orb!.gens));
2

So, the generators in orb!.stab in the second layer seems to be missing something. Alas:

gap> Size(Group(Concatenation(S!.stab!.orb!.gens,S!.stab!.stab!.orb!.gens)));
16

It is not hard to see how this can happen in the code... What is harder to tell (for me, at least) is whether this is a bug or not!

I mean, of course those generators give the orbit, so they are generators of the orbit. They are also generator for that layer of the stabilizer chain. So, perhaps the above is actually just fine.
But perhaps not -- as far as I could tell, there is no clear documentation for the semantics of S!.orb!.gens in genss.

There is a lot of code using orb!.gens directly, and it is not always clear what its assumptions regarding orb!.gens are. There is at least one case where they are potentially wrong:

InstallGlobalFunction( GENSS_FindGensStabilizer,
  function( S, pt, opt )
    # Assumes that S is a correct stabilizer chain for the group generated by
    # its gens (in S!.orb!.gens) and that pt lies in the first orbit S!.orb.
    # Finds an SLP to express generators of the stabilizer of pt in
    # the group in terms of the gens.
    local gens,g,pos,mgens,word,cosetrep,invgens,pr,stabgens,size,stabsize,
          randel,newpt,ptpos,ptcosetrep,el,SS,stab,i;
    gens := S!.orb!.gens;
    g := GroupWithGenerators(gens);
    SetSize(g,Size(S));

If this function is ever called with the subchain SS:=S!.stab, then the group g created here is invalid. Then again, GENSS_FindGensStabilizer is an undocumented global function which nothing seems to be using (I grepped through all GAP packages in my GAP installation and could find no reference to it). So perhaps it never meant to be called with a layer of a stab chain other than the top layer...?

And perhaps we should just remove that function? :)

Finally, for the record, what was / is the connection to the problem at hand? Well, SetwiseStabilizer contained this code:

  gens := [];
  SS := S;
  for i in [1..Length(M)] do
      if SS = false then break; fi;
      if M[i] = SS!.orb[1] then SS := SS!.stab; fi;
  od;
  if SS = false then
      gens := [];
  else
      gens := ShallowCopy(SS!.orb!.gens);
  fi;
  # These are now the generators of the pointwise stabilizer!
  # We add to them as we go.

So if your set M happens to be pointwise fixed by a group in the stabilizer chain, we immediately add those generators. Alas, of course in our "bad" case, that list of generators is incomplete.

To fix this, I changed it to add the generators for the lower layers, too. (Which is a common requirement when dealing with stabilizer chains, so it felt natural... but, as explained above, I am left somewhat uncertain about the whole thing).