Quelle  d247.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.
##
##  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
##
##
##  Handle the (projective) imprimitive, tensor and tensor-induced cases.
##
##  This implementation is inspired by Max Neunhöffer's habilitation thesis
##  [Neu09], and the variations D2, D4 and D7 of the Aschbacher cases. A
##  copy of the thesis is available online; see the bibliography.
##
#############################################################################

RECOG.InvolutionSearcher := function(pr,ord,tol)
  # pr a product replacer
  # ord a function computing the order
  # tol the number of tries
  local count,o,x;
  count := 0;
  repeat
      count := count + 1;
      x := Next(pr);
      o := ord(x);
      if IsEvenInt(o) then
          return x^(o/2);
      fi;
  until count > tol;
  return fail;
end;

RECOG.CentralisingElementOfInvolution := function(pr,ord,x)
  # x an involution in G
  local o,r,y,z;
  r := Next(pr);
  y := x^r;
  # Now x and y generate a dihedral group
  if x = y then
      return r;
  fi;
  z := x*y;
  o := ord(z);
  if IsEvenInt(o) then
      return z^(o/2);
  fi;
  return z ^ ((o+1)/2) * (r^-1);
end;

RECOG.InvolutionCentraliser := function(pr, ord, x, nr)
  # x is an involution in G.
  # Choose <nr> elements (with possible repeats) of the centraliser of <x>,
  # in the hope that they generate the centraliser.
  return Set([1..nr], i -> RECOG.CentralisingElementOfInvolution(pr, ord, x));
end;


# See https://www.math.rwth-aachen.de/~Max.Neunhoeffer/Publications/pdf/perth09_handout.pdf
RECOG.InvolutionJumper := function(pr,ord,x,tol,withodd)
  # x an involution in a group g, for which the product replacer pr produces
  # random elements, withodd is true or false, it switches the odd case on or
  # off, ord an order oracle
  local c,count,o,y,z;
  count := 0;
  repeat
      count := count + 1;
      y := Next(pr);
      c := Comm(x,y);
      o := ord(c);
      if o = 1 then
          continue;
      elif IsEvenInt(o) then
          return c^(o/2);
      elif not withodd then
          continue;
      fi;
      z := y*c^((o-1)/2);
      o := ord(z);
      if IsEvenInt(o) then
          return z^(o/2);
      fi;
  until count > tol;
  return fail;
end;

RECOG.DirectFactorsFinder := function(gens,facgens,k,eq)
  local equal,fgens,i,j,l,o,pgens,pr,z;
  fgens := [];
  pr := ProductReplacer(facgens);
  Add(fgens,Next(pr));
  Add(fgens,Next(pr));
  Add(fgens,Next(pr));
  if eq(fgens[1]*fgens[2],fgens[2]*fgens[1]) and
     eq(fgens[1]*fgens[3],fgens[3]*fgens[1]) then
      if eq(fgens[2]*fgens[3],fgens[3]*fgens[2]) then
          i := 0;
          while i <= 4 do
              Add(fgens,Next(pr),1);
              if ForAny([2..Length(fgens)],
                        j -> not eq(fgens[1]*fgens[j], fgens[j]*fgens[1])) then
                  break;
              fi;
              i := i + 1;
          od;
          if i > 4 then
              Info(InfoRecog,2,"D247: did not find non-commuting elements.");
              return fail;
          fi;
      else
          fgens{[1..2]} := fgens{[2,1]};
      fi;
  fi;

  equal := function(a,b)
    return ForAny(b, y -> not eq(a*y, y*a));
  end;

  # Enumerate orbit:
  o := [fgens];
  pgens := List([1..Length(gens)],j->EmptyPlist(k));
  i := 1;
  while i <= Length(o) do
    for j in [1..Length(gens)] do
      z := o[i][1]^gens[j];
      l := 1;
      while l <= Length(o) and not equal(z, o[l]) do
          l := l + 1;
      od;
      pgens[j][i] := l;
      if l > Length(o) then
        z := Concatenation([z],List(o[i]{[2..Length(o[i])]},x->x^gens[j]));
        Add(o,z);
        if Length(o) > k then
            Info(InfoRecog,1,
                 "Strange, found more direct factors than expected!");
            return fail;
        fi;
      fi;
    od;
    i := i + 1;
  od;

  if Length(o) < k then
      Info(InfoRecog,1,"Strange, found fewer direct factors than expected!");
      return fail;
  fi;

  pgens := List(pgens,PermList);
  if fail in pgens then
    return fail;
  fi;
  return [o,pgens];
end;

RECOG.DirectFactorsAction := function(data,el)
  local equal,i,j,res,z,o,eq;

  eq := data.eq;
  o := data.o;

  equal := function(a,b)
    return ForAny(b, y -> not eq(a*y, y*a));
  end;

  res := EmptyPlist(Length(o));
  for i in [1..Length(o)] do
    z := o[i][1]^el;
    j := 1;
    while j <= Length(o) and not equal(z, o[j]) do
        j := j + 1;
    od;
    if j <= Length(o) then
      Add(res,j);
    else
      return fail;
    fi;
  od;
  return PermList(res);
end;

RECOG.IsPower := function(d)
  local f, e, g, l, dd;
  # Intended for small d
  f := Collected(Factors(d));
  e := List(f,x->x[2]);
  g := Gcd(e);
  d := DivisorsInt(g);
  d := d{[2..Length(d)]};
  l := EmptyPlist(Length(d));
  for dd in d do
    Add(l,[Product(f,x->x[1]^(x[2]/dd)),dd]);
  od;
  return l;
end;

RECOG.SortOutReducibleNormalSubgroup :=
  function(ri,G,ngens,m)
    # ngens generators for a proper normal subgroup, m a reducible
    # MeatAxe module with generators ngens.
    # This function takes care of the cases to construct a reduction.
    # Only call this with absolutely irreducible G!
    # Only call this if we already know that G is not C3!

    local H,a,basis,collf,conjgensG,f,hom,homcomp,homs,homsimg,kro,o,r,subdim;

    f := ri!.field;
    collf := MTX.CollectedFactors(m);
    if Length(collf) = 1 then    # only one homogeneous component!
        if MTX.Dimension(collf[1][1]) = 1 then
            # If we get here, the computed normal closure cannot be normal
            # since if m were semisimple, then all generators would be scalar
            # which they were not. So we conclude that FastNormalClosure
            # did not compute the full normal closure and for the moment
            # give up.
            # Usually this should have been caught by using projective orders.
            Info(InfoRecog,2,"D247:Scalar subgroup, FastNormalClosure must ",
                 "have made a mistake!");
            return TemporaryFailure;
        fi;
        Info(InfoRecog,2,"D247:Restriction to normal subgroup is homogeneous.");
        if not MTX.IsAbsolutelyIrreducible(collf[1][1]) then
            ErrorNoReturn("Is this really possible??? G acts absolutely irred!");
        fi;
        homs := MTX.Homomorphisms(collf[1][1],m);
        basis := Concatenation(homs);
# FIXME: This will go:
        ConvertToMatrixRep(basis,Size(f));
        subdim := MTX.Dimension(collf[1][1]);
        r := rec(t := basis, ti := basis^-1,
                 blocksize := MTX.Dimension(collf[1][1]));
        # Note that we already checked for semilinear, so we know that
        # the irreducible N-submodule is absolutely irreducible!
        # Now we believe to have a tensor decomposition:
        conjgensG := List(GeneratorsOfGroup(G),x->r.t * x * r.ti);
        kro := List(conjgensG,g->RECOG.IsKroneckerProduct(g,r.blocksize));
        if not ForAll(kro, k -> k[1]) then
            Info(InfoRecog,1,"VERY, VERY, STRANGE!");
            Info(InfoRecog,1,"False alarm, was not a tensor decomposition.");
            ErrorNoReturn("This should never have happened (346), tell Max.");
        fi;

        H := GroupWithGenerators(conjgensG);
        hom := GroupHomByFuncWithData(G,H,RECOG.HomDoBaseChange,r);
        SetHomom(ri,hom);

        # Hand down information:
        InitialDataForImageRecogNode(ri).blocksize := r.blocksize;
        InitialDataForImageRecogNode(ri).generatorskronecker := kro;
        AddMethod(InitialDataForImageRecogNode(ri).hints,
                  FindHomMethodsProjective.KroneckerProduct,
                  4000);
        # This is an isomorphism:
        findgensNmeth(ri).method := FindKernelDoNothing;
        ri!.comment := "D4TensorDec";
        return Success;
    fi;
    Info(InfoRecog,2,"D247:Using action on the set of homogeneous components",
           " (",Length(collf)," elements)...");
    # Now find a homogeneous component to act on it:
    homs := MTX.Homomorphisms(collf[1][1],m);
    if Length(homs) = 0 then
        Info(InfoRecog,2,"Restricted module not semisimple ==> not normal");
        return TemporaryFailure;
    fi;
    homsimg := BasisVectors(Basis(VectorSpace(f,Concatenation(homs))));
    homcomp := MutableCopyMat(homsimg);
# FIXME: This will go:
ConvertToMatrixRep(homcomp,Size(f));
    TriangulizeMat(homcomp);
    o := Orb(G,homcomp,OnSubspacesByCanonicalBasis,rec(storenumbers := true));
    Enumerate(o,QuoInt(ri!.dimension,Length(homcomp)));
    if not IsClosed(o) then
        Info(InfoRecog,2,"D247:Obviously did not get normal subgroup!");
        return TemporaryFailure;
    fi;

    # NOTE: here we switch from matrix to permutation group recognition!
    # Here is an example triggering this:
    #
    # gap> n:=7;; G:=AlternatingGroup(n);;
    # gap> gens:=List(GeneratorsOfGroup(G),g->PermutationMat(g,n)) * Z(5);;
    # gap> gens[1][1][2] := -gens[1][1][2];; gens[2][7][5] := -gens[2][7][5];;
    # gap> H2:=Group(gens);; ri:=RecognizeGroup( H2 );
    # gap> Grp(ImageRecogNode(ri));
    # <matrix group with 2 generators>
    # gap> Grp(ImageRecogNode(ImageRecogNode(ri)));
    # Group([ (1,2,3,4,5,6,7), (1,2,3) ])

    a := OrbActionHomomorphism(G,o);
    SetHomom(ri,a);
    Setmethodsforimage(ri,FindHomDbPerm);
    ri!.comment := "D2Imprimitive";
    Setimmediateverification(ri,true);
    findgensNmeth(ri).args[1] := Length(o)+6;
    findgensNmeth(ri).args[2] := 4;
    return Success;
  end;

RECOG.SortOutReducibleSecondNormalSubgroup :=
  function(ri,G,nngens,mm)
    # nngens generators for a proper normal subgroup of a proper
    # irreducible normal subgroup, mm a reducible MeatAxe module with
    # generators nngens.
    # This function takes care of the cases to construct a reduction
    # if we have a D7 case.
    # Only call this with absolutely irreducible G!
    # Only call this if we already know that G is not C3!
    # Only call this if the upper normal subgroup was still irreducible!

    local H,collf,dim,hom,mult,orb,subdim;

    collf := MTX.CollectedFactors(mm);
    if Length(collf) = 1 then
        subdim := MTX.Dimension(collf[1][1]);
        dim := MTX.Dimension(mm);
        mult := First([2..20],i->subdim^i = dim);
        if mult <> fail then
            orb := RECOG.DirectFactorsFinder(GeneratorsOfGroup(G),
                                             nngens,mult,ri!.isequal);
            if orb <> fail then
                H := GroupWithGenerators(orb[2]);
                hom := GroupHomByFuncWithData(G,H,
                           RECOG.DirectFactorsAction,
                           rec( o := orb[1], eq := ri!.isequal) );
                SetHomom(ri,hom);
                Setmethodsforimage(ri,FindHomDbPerm);
                Info(InfoRecog,2,"D247: Success, found D7 with action",
                     " on ",mult," direct factors.");
                ri!.comment := "D7TensorInduced";
                return Success;
            else
                Info(InfoRecog,2,"D247: Did not find direct factors!");
            fi;
        else
            Info(InfoRecog,2,"D247: Submodule dimension no root!");
        fi;
    else
        Info(InfoRecog,2,"D247: Restriction not homogeneous!");
    fi;
    return fail; # FIXME: fail = TemporaryFailure here really correct?
  end;

#! @BeginChunk D247
#! TODO
#! @EndChunk
BindRecogMethod(FindHomMethodsProjective, "D247",
"play games to find a normal subgroup",
function(ri, G)
  # We try to produce an element of a normal subgroup by playing
  # tricks.
  local CheckNormalClosure,f,i,res,x,ispower;

  RECOG.SetPseudoRandomStamp(G,"D247");

  CheckNormalClosure := function(x)
    # This is called with an element that we hope lies in a normal subgroup.
    local H,a,basis,collf,conjgensG,count,dim,hom,homcomp,homs,homsimg,i,
          kro,m,mm,mult,ngens,nngens,o,orb,pr,r,subdim,y,z;
    ngens := FastNormalClosure(G,[x],4);
    m := GModuleByMats(ngens,f);
    if MTX.IsIrreducible(m) then
        if not ispower then
            Info(InfoRecog,4,"Dimension is no power!");
            return fail; # FIXME: fail = TemporaryFailure here really correct?
        fi;
        # we want to look for D7 here, using the same trick again:
        count := 0;
        #n := GroupWithGenerators(ngens);
        pr := ProductReplacer(ngens);
        y := RECOG.InvolutionJumper(pr,RECOG.ProjectiveOrder,x,200,false);
        if y = fail then
            return TemporaryFailure;
        fi;
        for i in [1..3] do
            z := RECOG.InvolutionJumper(pr,RECOG.ProjectiveOrder,y,200,false);
            if z <> fail then y := z; fi;
        od;
        nngens := FastNormalClosure(ngens,[y],2);
        mm := GModuleByMats(nngens,f);
        if not MTX.IsIrreducible(mm) then
            return RECOG.SortOutReducibleSecondNormalSubgroup(ri,G,nngens,mm);
        fi;
        return fail; # FIXME: fail = TemporaryFailure here really correct?
    fi;
    if InfoLevel(InfoRecog) >= 2 then Print("\n"); fi;
    Info(InfoRecog,2,"D247: Seem to have found something!");
    return RECOG.SortOutReducibleNormalSubgroup(ri,G,ngens,m);
  end;

  Info(InfoRecog,2,"D247: Trying the involution jumper 9 times..."); # FIXME: don't hardcode '9'
  f := ri!.field;
  ispower := Length(RECOG.IsPower(ri!.dimension)) > 0;
  x := RECOG.InvolutionSearcher(ri!.pr,RECOG.ProjectiveOrder,100);
  if x = fail then
      Info(InfoRecog,2,"Did not find an involution! Giving up.");
      return TemporaryFailure;
  fi;

  for i in [1..9] do
      if InfoLevel(InfoRecog) >= 2 then Print(".\c"); fi;
      res := CheckNormalClosure(x);
      if res in [true,false] then
          return res;
      fi;
      x := RECOG.InvolutionJumper(ri!.pr,RECOG.ProjectiveOrder,x,100,true);
      if x = fail then
          if InfoLevel(InfoRecog) >= 2 then Print("\n"); fi;
          Info(InfoRecog,2,"Involution Jumper failed, giving up!");
          return TemporaryFailure;
      fi;
  od;
  res := CheckNormalClosure(x);
  if res in [true,false] then
      return res;
  fi;
  if InfoLevel(InfoRecog) >= 2 then Print("\n"); fi;
  Info(InfoRecog,2,"D247: Did not find normal subgroup, giving up.");
  return TemporaryFailure;
end);

#! @BeginChunk PrototypeForC2C4
#! TODO/FIXME: PrototypeForC2C4 is not used anywhere
#! @EndChunk
BindRecogMethod(FindHomMethodsProjective, "PrototypeForC2C4",
"TODO",
function(ri, G)
  # We try to produce an element of a normal subgroup by playing
  # tricks.
  local CheckNormalClosure,f,m,res,ngens,l;

  RECOG.SetPseudoRandomStamp(G,"PrototypeForC2C4");
  f := ri!.field;

  CheckNormalClosure := function(x)
    # This is called with an element that we hope lies in a normal subgroup.
    local m,ngens;
    ngens := FastNormalClosure(G,x,4);
    m := GModuleByMats(ngens,f);
    if not IsIrreducible(m) then
        Info(InfoRecog,2,"Proto: Seem to have found something!");
        return RECOG.SortOutReducibleNormalSubgroup(ri,G,ngens,m);
    else
        return fail;
    fi;
  end;

  Info(InfoRecog,2,"Proto: Starting to work...");

  # Make some elements l which have good chances to be in a normal subgroup
  # ...
  # Then do:
  res := CheckNormalClosure(l);
  if res = true then
      Info(InfoRecog,2,"Proto: Found a reduction.");
      return true;
  fi;

  Info(InfoRecog,2,"Proto: Did not find normal subgroup, giving up.");
  return fail;
end);