Quelle  perm.gi   Sprache: unbekannt

#############################################################################
##
##  This file is part of recog, a package for the GAP computer algebra system
##  which provides a collection of methods for the constructive recognition
##  of groups.
##
##  This files's authors include Max Neunhöffer, Ákos Seress.
##
##  Copyright of recog belongs to its developers whose names are too numerous
##  to list here. Please refer to the COPYRIGHT file for details.
##
##  SPDX-License-Identifier: GPL-3.0-or-later
##
##
##  A collection of find homomorphism methods for permutation groups.
##
#############################################################################

#! @BeginChunk MovesOnlySmallPoints
#! If a permutation group moves only small points
#! (currently, this means that its largest moved point is at most 10),
#! then this method computes a stabilizer chain for the group via
#! <Ref Subsect="StabChain" Style="Text"/>.
#! This is because the most convenient way of solving constructive membership
#! in such a group is via a stabilizer chain.
#! In this case, the calling node becomes a leaf node of the composition tree.
#!
#! If the input group moves a large point (currently, this means a point
#! larger than 10), then this method returns <K>NeverApplicable</K>.
#! @EndChunk
BindRecogMethod(FindHomMethodsPerm, "MovesOnlySmallPoints",
"calculate a stabilizer chain if only small points are moved",
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
  if LargestMovedPoint(G) <= 10 then
      return FindHomMethodsPerm.StabChain(ri, G);
  fi;
  return NeverApplicable;
end);

#! @BeginChunk NonTransitive
#! If a permutation group <A>G</A> acts nontransitively then this method
#! computes a homomorphism to the action of <A>G</A> on the orbit of the
#! largest moved point. If <A>G</A> is transitive then the method returns
#! <K>NeverApplicable</K>.
#! @EndChunk
#! @BeginCode FindHomMethodsPerm.NonTransitive
BindRecogMethod(FindHomMethodsPerm, "NonTransitive",
"try to find non-transitivity and restrict to orbit",
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
    local hom,la,o;

    # test whether we can do something:
    if IsTransitive(G) then
        return NeverApplicable;
    fi;

    # compute orbit of the largest moved point
    la := LargestMovedPoint(G);
    o := Orb(G,la,OnPoints);
    Enumerate(o);
    # compute homomorphism into Sym(o), i.e, restrict
    # the permutation action of G to the orbit o
    hom := OrbActionHomomorphism(G,o);
    # TODO: explanation
    Setvalidatehomominput(ri, {ri,p} -> ForAll(o, x -> (x^p in o)));
    # store the homomorphism into the recognition node
    SetHomom(ri,hom);

    # TODO: explanation
    Setimmediateverification(ri, true);

    # indicate success
    return Success;
end);
#! @EndCode

#! @BeginChunk Imprimitive
#! If the input group is not known to be transitive then this method
#! returns <K>NotEnoughInformation</K>. If the input group is known to be transitive
#! and primitive then the method returns <K>NeverApplicable</K>; otherwise, the method
#! tries to compute a nontrivial block system. If successful then a
#! homomorphism to the action on the blocks is defined; otherwise,
#! the method returns <K>NeverApplicable</K>.
#! 
#! If the method is successful then it also gives a hint for the children of
#! the node by determining whether the kernel of the action on the
#! block system is solvable. If the answer is yes then the default value 20
#! for the number of random generators in the kernel construction is increased
#! by the number of blocks.
#! @EndChunk
BindRecogMethod(FindHomMethodsPerm, "Imprimitive",
"for a imprimitive permutation group, restricts to block system",
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
    local blocks,hom,pcgs,subgens;

    # Only look for primitivity once we know transitivity:
    # This ensures the right trying order even if the ranking is wrong.
    if not HasIsTransitive(G) then
        return NotEnoughInformation;
    fi;

    # We test for known non-primitivity:
    if HasIsPrimitive(G) and IsPrimitive(G) then
        return NeverApplicable;
    fi;

    RECOG.SetPseudoRandomStamp(G,"Imprimitive");

    # Now try to work:
    blocks := MaximalBlocks(G,MovedPoints(G));
    if Length(blocks) = 1 then
        SetIsPrimitive(G,true);
        return NeverApplicable;
    fi;

    # Find the homomorphism:
    hom := ActionHomomorphism(G,blocks,OnSets);
    Setvalidatehomominput(ri, {ri,p} -> OnSetsSets(blocks, p) = blocks);
    SetHomom(ri,hom);

    # Now we want to help recognising the kernel, we first check, whether
    # the restriction to one block is solvable, which would mean, that
    # the kernel is solvable and that a hint is in order:
    Setimmediateverification(ri,true);
    InitialDataForKernelRecogNode(ri).blocks := blocks;
    AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsPerm.PcgsForBlocks, 400);
    AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsPerm.BalTreeForBlocks, 200);
    findgensNmeth(ri).args[1] := Length(blocks)+3;
    findgensNmeth(ri).args[2] := 5;
    return Success;
end);

#! @BeginChunk PcgsForBlocks
#! This method is called after a hint is set in
#! <C>FindHomMethodsPerm.</C><Ref Subsect="Imprimitive" Style="Text"/>.
#! Therefore, the group <A>G</A> preserves a non-trivial block system.
#! This method checks whether or not the restriction of <A>G</A> on one block
#! is solvable.
#! If so, then <C>FindHomMethodsPerm.</C><Ref Subsect="Pcgs" Style="Text"/> is
#! called, and otherwise <K>NeverApplicable</K> is returned.
#! @EndChunk
BindRecogMethod(FindHomMethodsPerm, "PcgsForBlocks",
"TODO",
function(ri, G)
  local blocks,pcgs,subgens;
  blocks := ri!.blocks;   # we know them from above!
  subgens := List(GeneratorsOfGroup(G),g->RestrictedPerm(g,blocks[1]));
  pcgs := Pcgs(Group(subgens));
  if pcgs <> fail then
      # We now know that the kernel is solvable, go directly to
      # the Pcgs method:
      return FindHomMethodsPerm.Pcgs(ri,G);
  fi;
  # We have failed, let others do the work...
  return NeverApplicable;
end);

#! @BeginChunk BalTreeForBlocks
#! This method creates a balanced composition tree for the kernel of an
#! imprimitive group. This is guaranteed as the method is just called
#! from <C>FindHomMethodsPerm.</C><Ref Subsect="Imprimitive" Style="Text"/>
#! and itself. The homomorphism for the split in the composition tree used is
#! induced by the action of <A>G</A> on
#! half of its blocks.
#! @EndChunk
BindRecogMethod(FindHomMethodsPerm, "BalTreeForBlocks",
"TODO",
function(ri, G)
  local blocks,cut,hom,lowerhalf,nrblocks,o,upperhalf,l,n,seto;

  blocks := ri!.blocks;

  # We do exactly the same as in the non-transitive case, however,
  # we restrict to about half the blocks and pass our knowledge on:
  nrblocks := Length(blocks);
  if nrblocks = 1 then
      # this might happen during the descent into the tree
      return NeverApplicable;
  fi;
  cut := QuoInt(nrblocks,2);  # this is now at least 1
  lowerhalf := blocks{[1..cut]};
  upperhalf := blocks{[cut+1..nrblocks]};
  o := Concatenation(upperhalf);
  # The order of 'o' in the homom must align with InitialDataForImageRecogNode(ri).blocks below
  hom := ActionHomomorphism(G,o);

  # Make a set so checking validatehomominput is faster
  seto := Immutable(Set(o));
  Setvalidatehomominput(ri, {ri,p} -> ForAll(o, x -> x^p in seto));
  SetHomom(ri,hom);
  Setimmediateverification(ri,true);
  findgensNmeth(ri).args[1] := 3+cut;
  findgensNmeth(ri).args[2] := 5;
  if nrblocks - cut > 1 then
      l := Length(upperhalf[1]);
      n := Length(upperhalf);
      InitialDataForImageRecogNode(ri).blocks := List([1..n],i->[(i-1)*l+1..i*l]);
      AddMethod(InitialDataForImageRecogNode(ri).hints, FindHomMethodsPerm.BalTreeForBlocks, 200);
  fi;
  if cut > 1 then
      InitialDataForKernelRecogNode(ri).blocks := lowerhalf;
      AddMethod(InitialDataForKernelRecogNode(ri).hints, FindHomMethodsPerm.BalTreeForBlocks, 200);
  fi;
  return Success;
end);

# Now to the small base groups using stabilizer chains:

# The GAP manual suggests that the labels at each level of a stabiliser chain
# are identical GAP objects, but it does not promise this.
# This function tests whether the stabiliser chain has this property, and
# gives an error if not.
DoSafetyCheckStabChain := function(S)
  while IsBound(S.stabilizer) do
      if not IsIdenticalObj(S.labels, S.stabilizer.labels) then
          ErrorNoReturn("Alert! labels not identical on different levels!");
      fi;
      S := S.stabilizer;
  od;
end;

#! @BeginChunk StabChain
#! This is the randomized &GAP; library function for computing a stabiliser
#! chain. The method selection process ensures that this function is called
#! only with small-base inputs, where the method works efficiently.
#! @EndChunk
BindRecogMethod(FindHomMethodsPerm, "StabChain",
"for a permutation group using a stabilizer chain",
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
     local Gmem,S,si;

     # We know transitivity and primitivity, because there are higher ranked
     # methods checking for them!

     # Calculate a stabilizer chain:
     Gmem := GroupWithMemory(G);
     if HasStabChainMutable(G) or HasStabChainImmutable(G) or HasSize(G) then
         si := Size(G);
         S := StabChainOp(Gmem,rec(random := 900,size := si));
     else
         S := StabChainOp(Gmem,rec(random := 900));
     fi;
     DoSafetyCheckStabChain(S);
     Setslptonice(ri,SLPOfElms(S.labels));
     StripStabChain(S);
     SetNiceGens(ri,S.labels);
     MakeImmutable(S);
     ri!.stabilizerchain := S;
     Setslpforelement(ri,SLPforElementFuncsPerm.StabChain);
     SetFilterObj(ri,IsLeaf);
     SetSize(G,SizeStabChain(S));
     SetSize(ri,SizeStabChain(S));
     ri!.Gnomem := G;
     return Success;
end);

SLPforElementFuncsPerm.StabilizerChainPerm := function(ri,x)
  local r;
  r := SiftGroupElementSLP(ri!.stabilizerchain,x);
  return r.slp;
end;

#! @BeginChunk StabilizerChainPerm
#! TODO
#! @EndChunk
# TODO: merge FindHomMethodsPerm.StabilizerChainPerm and  FindHomMethodsProjective.StabilizerChainProj ?
BindRecogMethod(FindHomMethodsPerm, "StabilizerChainPerm",
Concatenation(
    "for a permutation group using a stabilizer chain via the ",
    "<URL Text=\"genss package\">",
    "https://gap-packages.github.io/genss/",
    "</URL>"),
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
  local Gm,S;
  Gm := Group(ri!.gensHmem);
  Gm!.pseudorandomfunc := [rec(
     func := function(ri) return RandomElm(ri,"StabilizerChainPerm",true).el; end,
     args := [ri])];
  S := StabilizerChain(Gm);
  SetSize(ri,Size(S));
  SetSize(Grp(ri),Size(S));
  ri!.stabilizerchain := S;
  Setslptonice(ri,SLPOfElms(StrongGenerators(S)));
  ForgetMemory(S);
  Setslpforelement(ri,SLPforElementFuncsPerm.StabilizerChainPerm);
  SetFilterObj(ri,IsLeaf);
  return Success;
end);

# creates recursively a word for <g> using the Schreier tree labels
# from the stabilizer chain <S>
WordinLabels := function(word,S,g)
  local i,point,start;
  if not (IsBound(S.orbit) and IsBound(S.orbit[1])) then
      return fail;
  fi;
  start := S.orbit[1];
  point := start^g;
  while point <> start do
      if not IsBound(S.translabels[point]) then
          return fail;
      fi;
      i := S.translabels[point];
      g := g * S.labels[i];
      point := point^S.labels[i];
      Add(word,i);
  od;
  # now g is in the first stabilizer
  if g <> S.identity then
      if not IsBound(S.stabilizer) then
          return fail;
      fi;
      return WordinLabels(word,S.stabilizer,g);
  fi;
  return word;
end;

# creates a straight line program for an element <g> using the
# Schreier tree labels from the stabilizer chain <S>
SLPinLabels := function(S,g)
  local i,j,l,line,word;
  word := WordinLabels([],S,g);
  if word = fail then
      return fail;
  fi;
  line := [];
  i := 1;
  while i <= Length(word) do
      # Find repeated labels:
      j := i+1;
      while j < Length(word) and word[j] = word[i] do
          j := j + 1;
      od;
      Add(line,word[i]);
      Add(line,j-i);
      i := j;
  od;
  l := Length(S!.labels);
  if Length(word) = 0 then
      return StraightLineProgramNC([[1, 0]], l);
  fi;
  return StraightLineProgramNC([line, [l + 1, -1]], l);
end;


SLPforElementFuncsPerm.StabChain :=
  function( ri, g )
    # we know that ri!.stabilizerchain is an immutable StabChain and
    # ri!.stronggensslp is bound to a slp that expresses the strong generators
    # in that StabChain in terms of the GeneratorsOfGroup(Grp(ri)).
    return SLPinLabels(ri!.stabilizerchain,g);
  end;

StoredPointsPerm := function(p)
  # Determines, as a permutation of how many points p is stored.
  local s;
  s := SIZE_OBJ(p) - GAPInfo.BytesPerVariable;
  if IsPerm4Rep(p) then
      return s/4;   # permutation stored with 4 bytes per point
  elif IsPerm2Rep(p) then
      return s/2;   # permutation stored with 2 bytes per point
  fi;
  ErrorNoReturn("StoredPointsPerm: input is not an internal permutation");
end;

#! @BeginChunk ThrowAwayFixedPoints
#! This method defines a homomorphism of a permutation group
#! <A>G</A> to the action on the moved points of <A>G</A> if
#! <A>G</A> has any fixed points, and is either known to be primitive or the
#! ratio of fixed points to moved points exceeds a certain threshold. If <A>G</A>
#! has fixed points but is not primitive, then it returns
#! <K>NotEnoughInformation</K> so that it may be called again at a later time.
#! In all other cases, it returns <K>NeverApplicable</K>.
#! <P/>
#!
#! In the current setup, the
#! homomorphism is defined if the number <M>n</M> of moved
#! points is at most <M>1/3</M> of the largest moved point of <A>G</A>,
#! or <M>n</M> is at most half of the number of points on which
#! <A>G</A> is stored internally by &GAP;.
#! <P/>
#!
#! The fact that this method returns <K>NotEnoughInformation</K> if <A>G</A>
#! has fixed points but does not know whether it is primitive, is important for
#! the efficient handling of large-base primitive groups by
#! <Ref Func="LargeBasePrimitive"/>.
#! @EndChunk
#
#  A technical explanation of why we use a threshold for the ratio of fixed
#  points to moved points, this is technical so it does not go into the manual:
#  The reason we do not just always discard fixed points is that it also incurs
#  a cost, so we only try to do it when it seems worthwhile to do so.
#
#  Suppose the group G is not known to be primitive. Then we still
#  apply this method if one of the following two criterion is met:
#  - the largest moved point of G is three or more times larger than the number
#    n of actually moved points
#  - there is a generator of G whose internal storage reserves space for a
#    number of moved points which is two or more times larger than n. Note that
#    even for a simple transposition (1,2), for technical reasons it can happen
#    that GAP internally stores it with the same size as a permutation moving a
#    million points; this is wasteful, and the second criterion tries to deal
#    with this.

BindRecogMethod(FindHomMethodsPerm, "ThrowAwayFixedPoints",
"try to find a huge amount of (possible internal) fixed points",
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
      # Check, whether we can throw away fixed points
      local gens,nrStoredPoints,n,largest,isApplicable,o,hom;

      gens := GeneratorsOfGroup(G);
      nrStoredPoints := Maximum(List(gens,StoredPointsPerm));
      n := NrMovedPoints(G);
      largest := LargestMovedPoint(G);
      # If isApplicable is true, we definitely are applicable.
      isApplicable := 3*n <= largest or 2*n <= nrStoredPoints
        or (HasIsPrimitive(G) and IsPrimitive(G) and n < largest);
      # If isApplicable is false, we might become applicable if G figures out
      # that it is primitive.
      if not isApplicable then
          if not HasIsPrimitive(G) and n < largest then
              return NotEnoughInformation;
          else
              return NeverApplicable;
          fi;
      fi;
      o := MovedPoints(G);
      hom := ActionHomomorphism(G,o);
      SetHomom(ri,hom);
      Setvalidatehomominput(ri, {ri,p} -> IsSubset(o, MovedPoints(p)));

      # Initialize the rest of the record:
      findgensNmeth(ri).method := FindKernelDoNothing;

      return Success;
end);

#! @BeginChunk Pcgs
#! This is the &GAP; library function to compute a stabiliser chain for a
#! solvable permutation group. If the method is successful then the calling
#! node becomes a leaf node in the recursive scheme. If the input group is
#! not solvable then the method returns <K>NeverApplicable</K>.
#! @EndChunk
BindRecogMethod(FindHomMethodsPerm, "Pcgs",
"use a Pcgs to calculate a stabilizer chain",
rec(validatesOrAlwaysValidInput := true),
function(ri, G)
    local GM,S,pcgs;
    GM := Group(ri!.gensHmem);
    GM!.pseudorandomfunc := [rec(
       func := function(ri) return RandomElm(ri,"PCGS",true).el; end,
       args := [ri])];
    pcgs := Pcgs(GM);
    if pcgs = fail then
        return NeverApplicable;
    fi;
    S := StabChainMutable(GM);
    DoSafetyCheckStabChain(S);
    Setslptonice(ri,SLPOfElms(S.labels));
    StripStabChain(S);
    SetNiceGens(ri,S.labels);
    MakeImmutable(S);
    ri!.stabilizerchain := S;
    Setslpforelement(ri,SLPforElementFuncsPerm.StabChain);
    SetFilterObj(ri,IsLeaf);
    SetSize(G,SizeStabChain(S));
    SetSize(ri,SizeStabChain(S));
    ri!.Gnomem := G;
    return Success;
end);


# The following commands install the above methods into the database:
#! @BeginCode AddMethod_Perm_FindHomMethodsGeneric.TrivialGroup
AddMethod(FindHomDbPerm, FindHomMethodsGeneric.TrivialGroup, 300);
#! @EndCode

AddMethod(FindHomDbPerm, FindHomMethodsPerm.ThrowAwayFixedPoints, 100);

AddMethod(FindHomDbPerm, FindHomMethodsGeneric.FewGensAbelian, 99);

AddMethod(FindHomDbPerm, FindHomMethodsPerm.Pcgs, 97);

AddMethod(FindHomDbPerm, FindHomMethodsPerm.MovesOnlySmallPoints, 95);

#! @BeginCode AddMethod_Perm_FindHomMethodsPerm.NonTransitive
AddMethod(FindHomDbPerm, FindHomMethodsPerm.NonTransitive, 90);
#! @EndCode

AddMethod(FindHomDbPerm, FindHomMethodsPerm.Giant, 80);

AddMethod(FindHomDbPerm, FindHomMethodsPerm.Imprimitive, 70);

AddMethod(FindHomDbPerm, FindHomMethodsPerm.LargeBasePrimitive, 60);

AddMethod(FindHomDbPerm, FindHomMethodsPerm.StabilizerChainPerm, 55);

AddMethod(FindHomDbPerm, FindHomMethodsPerm.StabChain, 50);


# Note that the last one will always succeed!

[ Dauer der Verarbeitung: 0.33 Sekunden  (vorverarbeitet)  ]