Quelle almostsimple.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
##
##
##  Code to recognise (simple) groups by their two largest element orders.
##  At least recognise the "natural" characteristic.
##
#############################################################################

# parses certain strings and numbers into a number
RECOG.ParseNumber := function( number, d, default )
  if IsInt(number) then
      return number;
  elif number = "logd" then
      return LogInt(d, 2);
  elif IsString(number) and EndsWith(number, "d") then
      return d * Int(number{[1..Length(number)-1]});
  fi;
  return default;
end;

# RECOG.MakeStabChainHint := function( chain, stdgens )
#   local b,bb,choice,dims,f,gens,grpnum,grps,i,j,lens,llens,m,name,names,nams,nrs,o,orblens,pts,r,size,slps;
#   f := FieldOfMatrixList(stdgens);
#   name := chain[1].name;
#   size := chain[1].order;
#   slps := [];
#   names := [];
#   dims := [];
#   orblens := [];
#   pts := [];
#   gens := stdgens;
#   repeat
#       Print("Working on ",name,"\n");
#       grps := [];
#       nams := [];
#       nrs := [];
#       for i in [1..Length(chain)] do
#           r := chain[i];
#           if IsBound(r.parent) and r.parent = name then
#               Add(grps,ResultOfStraightLineProgram(r.generators,gens));
#               Add(nams,r.name);
#               Add(nrs,i);
#           fi;
#       od;
#       if Length(grps) = 0 then break; fi;
#       Print("Considering subgroups: ",nams,"\n");
#       bb := [];
#       llens := [];
#       grpnum := [];
#       for i in [1..Length(grps)] do
#           # will be left by break in case of success
#           Print("  Considering ",nams[i],"\n");
#           m := GModuleByMats(grps[i],f);
#           if not MTX.IsIrreducible(m) then
#               b := List(MTX.BasesMinimalSubmodules(m),MutableCopyMat);
#               Sort(b,function(a,b) return Length(a) < Length(b); end );
#               Print("    Dimensions: ",List(b,Length),"\n");
#               lens := [];
#               for j in [1..Length(b)] do
#                   TriangulizeMat(b[j]);
#                   if Length(b[j]) = 1 then
#                       o := Orb(gens,b[j][1],OnLines,rec( report := 10000,
#                              treehashsize := 1000, storenumbers := true ));
#                   else
#                       o := Orb(gens,b[j],OnSubspacesByCanonicalBasis,
#                          rec( report := 10000, treehashsize := 1000,
#                               storenumbers := true ));
#                   fi;
#                   Enumerate(o);
#                   Print("    Found orbit of length ",Length(o),"\n");
#                   lens[j] := Length(o);
#               od;
#               Append(bb,b);
#               Append(llens,lens);
#               Append(grpnum,ListWithIdenticalEntries(Length(b),i));
#           else
#               Print("    Restriction is irreducible!\n");
#           fi;
#       od;
#       choice := 1;
#       Print("Dimensions: ",List(bb,Length),"\n");
#       Print("Orbit lengths: ",llens,"\n");
#       Error("now decide which orbit to take, set choice");
#       if choice > 0 then
#           i := grpnum[choice];
#           Add(names,nams[i]);
#           Add(dims,Length(bb[choice]));
#           name := nams[i];
#           gens := grps[i];
#           size := size / llens[choice];
#           Add(orblens,llens[choice]);
#           Add(slps,chain[nrs[i]].generators);
#           Add(pts,bb[choice]);
#       fi;
#   until size = 1 or choice = 0;
#   return rec( slps := slps, names := names, dims := dims, orblens := orblens,
#               pts := pts );
# end;

InstallGlobalFunction( DoHintedStabChain, function(ri,G,hint)
    local S,b,bra,c,cf,elm,finder,fu,gm,homs,m,max,maxes,maxgens,opt,s,stdgens;
    finder := AtlasProgram(hint.name,"find");
    if finder = fail then
        Info(InfoRecog,1,"Expected BBox finder for stdgens of ",hint.name,
             " not availabe!");
        Info(InfoRecog,1,"Check your AtlasRep installation!");
        return fail;
    fi;
    gm := Group(ri!.gensHmem);
    gm!.pseudorandomfunc := [rec(
       func := function(ri) return RandomElm(ri,"StdGens",true).el; end,
       args := [ri])];
    Info(InfoRecog,2,"Finding standard generators with bbox program...");
    stdgens := RunBBoxProgram(finder.program,gm,ri!.gensHmem,
                              rec( orderfunction := RECOG.ProjectiveOrder ) );
    if stdgens = fail or stdgens = "timeout" then
        Info(InfoRecog,2,"Stdgens finder did not succeed for ",hint.name);
        return fail;
    fi;
    stdgens := stdgens.gens;
    #Setslptostd(ri,SLPOfElms(stdgens));
    #SetStdGens(ri,StripMemory(stdgens));
    if IsBound(hint.usemax) then
        if IsBound(hint.brauercharelm) then
            elm := ResultOfStraightLineProgram(hint.brauercharelm,stdgens);
            bra := BrauerCharacterValue(elm!.el);
            maxes := hint.usemax{Filtered([1..Length(hint.usemax)],
                                          i->hint.brauercharvals[i] = bra)};
        else
            maxes := hint.usemax;
        fi;
        for max in maxes do
            s := AtlasProgram(hint.name,max);
            if s = fail then
                Info(InfoRecog,1,"Expected maximal subgroup slp of ",hint.name,
                     " not available!");
                Info(InfoRecog,1,"Check your AtlasRep installation!");
                return fail;
            fi;
            maxgens := ResultOfStraightLineProgram(s.program,
                                                   StripMemory(stdgens));
            m := GModuleByMats(maxgens,ri!.field);
            if MTX.IsIrreducible(m) then
                Info(InfoRecog,2,"Found irreducible submodule!");
                continue;
            fi;
            cf := List(MTX.CollectedFactors(m),x->x[1]);
            Sort(cf,function(a,b) return a.dimension < b.dimension; end);
            for c in cf do
                homs := MTX.Homomorphisms(c,m);
                if Length(homs) > 0 then
                    ConvertToMatrixRep(homs[1],ri!.field);
                    b := MutableCopyMat(homs[1]);
                    break;
                fi;
                # Some must be in the socle, so this terminates with break!
            od;
            TriangulizeMat(b);
            fu := function() return RandomElm(ri,"StabChain",true).el; end;
            opt := rec( Projective := true, RandomElmFunc := fu );
            if Length(b) = 1 then
                opt.Cand := rec( points := [b[1]], ops := [OnLines] );
            else
                opt.Cand := rec( points := [b],
                                 ops := [OnSubspacesByCanonicalBasis] );
            fi;
            gm := GroupWithGenerators(stdgens);
            opt.Size := hint.size;
            Info(InfoRecog,2,"Computing hinted stabilizer chain for ",
                 hint.name," ...");
            S := StabilizerChain(gm,opt);
            # Verify correctness by sifting original gens:
            # Actually, genss does not terminate if no group of this
            # size is found!
            ri!.stabilizerchain := S;
            Setslptonice(ri,SLPOfElms(StrongGenerators(S)));
            SetSize(ri,hint.size);
            ForgetMemory(S);
            Unbind(S!.opt.RandomElmFunc);
            Setslpforelement(ri,SLPforElementFuncsProjective.StabilizerChainProj);
            SetFilterObj(ri,IsLeaf);
            if IsBound(hint.issimple) then
                SetIsRecogInfoForSimpleGroup(ri,hint.issimple);
            fi;
            SetIsRecogInfoForAlmostSimpleGroup(ri,true);
            ri!.comment := hint.name;
            return true;
        od;
    fi;
    Info( InfoRecog, 2, "Got stab chain hint, not yet implemented!" );
    return fail;
  end );

InstallGlobalFunction( DoHintedLowIndex, function(ri,G,hint)
  local bas,d,fld,gens,hm,hom,i,numberrandgens,orb,orblenlimit,s,
        tries,triesinner,triesinnerlimit,trieslimit,x,y;

  Info(InfoRecog,2,"Got hint for group, trying LowIndex...");

  fld := ri!.field;
  d := ri!.dimension;
  if IsBound(hint.elordersstart) then
      i := 0;
      repeat
          i := i + 1;
          if i > 10000 then
              ErrorNoReturn("possible infinite loop in DoHintedLowIndex, ",
                            "wrong hints?");
          fi;
          x := PseudoRandom(G);
      until Order(x) in hint.elordersstart;
      x := [x];
  else
      x := [];
  fi;

  tries := 0;
  numberrandgens := RECOG.ParseNumber(hint.numberrandgens,d,2);
  triesinnerlimit := RECOG.ParseNumber(hint.triesforgens,d,"1d");
  trieslimit := RECOG.ParseNumber(hint.tries,d,10);
  orblenlimit := RECOG.ParseNumber(hint.orblenlimit,d,"4d");
  Info(InfoRecog,3,"Using numberrandgens=",numberrandgens,
       " triesinnerlimit=",triesinnerlimit," trieslimit=",trieslimit,
       " orblenlimit=",orblenlimit);

  repeat
      gens := ShallowCopy(x);
      triesinner := 0;
      if numberrandgens = Length(gens) then   # we have to make the hm module
          hm := GModuleByMats(gens,fld);
          if MTX.IsIrreducible(hm) then
              tries := tries + 1;
              continue;
          fi;
      else
          while Length(gens) < numberrandgens and
                triesinner < triesinnerlimit do
              y := PseudoRandom(G);
              Add(gens,y);
              triesinner := triesinner + 1;
              hm := GModuleByMats(gens,fld);
              if MTX.IsIrreducible(hm) then
                  Unbind(gens[Length(gens)]);
              fi;
          od;
      fi;
      if Length(gens) = numberrandgens then
          # We hope to have the maximal subgroup!
          bas := [MTX.ProperSubmoduleBasis(hm)];
          s := bas[1];
          while s <> fail do
              hm := MTX.InducedActionSubmodule(hm,s);
              s := MTX.ProperSubmoduleBasis(hm);
              Add(bas,s);
          od;
          Unbind(bas[Length(bas)]);
          s := bas[Length(bas)];
          for i in [Length(bas)-1,Length(bas)-2..1] do
              s := s * bas[i];
          od;
          # Now s is the basis of a minimal submodule, permute that:
          s := MutableCopyMat(s);
          TriangulizeMat(s);
          # FIXME: this will be unnecessary:
          ConvertToMatrixRep(s);
          Info(InfoRecog,2,"Found invariant subspace of dimension ",
               Length(s),", enumerating orbit...");
          if not IsBound(hint.subspacedims) or
             Length(s) in hint.subspacedims then
              #orb := RECOG.OrbitSubspaceWithLimit(G,s,orblenlimit);
              orb := Orb(G,s,OnSubspacesByCanonicalBasis,
                         rec(storenumbers := true,
                             hashlen := NextPrimeInt(2*orblenlimit)));
              Enumerate(orb,orblenlimit);
              if IsClosed(orb) then
                  hom := OrbActionHomomorphism(G,orb);
                  if Length(s) * Length(orb) = d then
                      # A block system!
                      InitialDataForKernelRecogNode(ri).t := Concatenation(orb);
                      InitialDataForKernelRecogNode(ri).blocksize := Length(s);
                      AddMethod(InitialDataForKernelRecogNode(ri).hints,
                                FindHomMethodsProjective.DoBaseChangeForBlocks,
                                2000);
                      Setimmediateverification(ri,true);
                      findgensNmeth(ri).args[1] := Length(orb)+3;
                      findgensNmeth(ri).args[2] := 5;
                      Info(InfoRecog,2,"Found block system with ",
                           Length(orb)," blocks.");
                  else
                      Info(InfoRecog,2,"Found orbit of length ",
                           Length(orb)," - not a block system.");
                  fi;
                  SetHomom(ri,hom);
                  Setmethodsforimage(ri,FindHomDbPerm);
                  return true;
              fi;
          else
              Info(InfoRecog,2,"Subspace dimension not as expected, ",
                   "not enumerating orbit.");
          fi;
      fi;
      tries := tries + 1;
  until tries > trieslimit;
  return fail;
end );

# We start a database of hints, whenever we discover a certain group, we
# can ask this database what to do:

RECOG.AlmostSimpleHints := rec();

# is called in almostsimple/hints.gi to create a database in
# RECOG.AlmostSimpleHints to store hints about almost simple groups.
# Currently just sporadic simple groups are contained.
InstallGlobalFunction( InstallAlmostSimpleHint,
  function( name, type, re )
    if not IsBound(RECOG.AlmostSimpleHints.(name)) then
        RECOG.AlmostSimpleHints.(name) := [];
    fi;
    re.type := type;
    Add( RECOG.AlmostSimpleHints.(name),re );
  end );

# FIXME: unused?
# TODO: this was likely used to generate the hints in almostsimple/hints.gi.
# Document this, and how to replicate the hints; move the code to a separate file.
# Indeed, ideally a user should be able to trivially regenerate the list of hints
# by running a script. Note that for that, we need to also explain how the arguments
# "reps" and "maxes" are chosen...
# Perhaps a full script is not possible; but then we should still explain how
# the hints where generated.
RECOG.ProduceTrivialStabChainHint := function(name,reps,maxes)
  local bad,f,g,gens,hint,list,m,o,prevdim,prevfield,r,range,res,ri,
        size,success,t,values,x;
  PrintTo(Concatenation("NEWHINTS.",name),"# Hints for ",name,":\n");
  prevdim := fail;
  prevfield := fail;
  for r in reps do
      Print("\nDoing representation #",r,"\n");
      gens := AtlasGenerators(name,r);
      g := Group(gens.generators);
      f := gens.ring;
      values := [];
      success := false;
      size := Size(CharacterTable(name));
      for m in [1..Length(maxes)] do
          Print("Doing maximal subgroup #",m,"\n");
          hint := rec( name := name, size := size, usemax := [m] );
          ri := RecogNode(rec(),g,true);
          t := Runtime();
          res := DoHintedStabChain(ri,g,hint);
          t := Runtime() - t;
          if res = true then
              o := ri!.stabilizerchain!.orb;
              x := o[1];
              if IsMatrix(x) then
                  Add(values,[Length(x)*QuoInt(Length(o)+99,100),Length(o)]);
              else
                  Add(values,[QuoInt(Length(o)+99,100),Length(o)]);
              fi;
              Print("value=",values[Length(values)]," time=",t," orblen=",
                    Length(o)," subspace=");
              ViewObj(x);
              Print("\n");
              success := true;
          else
              Add(values,[infinity,infinity]);
              Print("failure\n");
          fi;
      od;
      if success then
          if Size(f) = prevfield and Length(gens.generators[1]) = prevdim then
              AppendTo(Concatenation("NEWHINTS.",name),
                       ">>>SAME FIELD AND DIM\n");
          fi;
          list := ShallowCopy(maxes);
          SortParallel(values,list);
          bad := First([1..Length(values)],i->values[i][1] = infinity);
          if bad = fail or bad > 3 then
              if Length(values) > 3 then
                  range := [1..3];
              else
                  range := [1..Length(values)];
              fi;
          else
              range := [1..bad-1];
          fi;
          AppendTo(Concatenation("NEWHINTS.",name),
                "InstallAlmostSimpleHint( \"",name,"\", \"StabChainHint\",\n",
                "  rec( name := \"",name,"\", fields := [",
                Size(f),"], dimensions := [",Length(gens.generators[1]),
                "], \n       usemax := ",list{range},
                ", \n       size := ", size,
                ", atlasrepnrs := [",r,"], \n       values := ",
                values{range},"\n  ));\n");
      fi;
      prevfield := Size(f);
      prevdim := Length(gens.generators[1]);
  od;
end;

# FIXME: unused?
RECOG.DistinguishAtlasReps := function(name,rep1,rep2)
  local br1,br2,classes,gens1,gens2,guck1,guck2,l,lens,slps;
  classes := AtlasProgram(name,"cyclic").program;
  gens1 := GeneratorsWithMemory(AtlasGenerators(name,rep1).generators);
  gens2 := AtlasGenerators(name,rep2).generators;
  guck1 := ResultOfStraightLineProgram(classes,gens1);
  guck2 := ResultOfStraightLineProgram(classes,gens2);
  br1 := List(guck1,x->BrauerCharacterValue(x!.el));
  br2 := List(guck2,BrauerCharacterValue);
  l := Filtered([1..Length(br1)],i->br1[i]<>br2[i]);
  slps := List(guck1,SLPOfElm);
  lens := List(l,x->Length(LinesOfStraightLineProgram(slps[x])));
  SortParallel(lens,l);
  Print("brauercharelm := ",slps[l[1]],", brauercharvals := ",
        [br1[l[1]],br2[l[1]]],",\n");
end;

# This is for the released AtlasRep package:
if not IsBound(AGR_TablesOfContents) then
    AGR_TablesOfContents := fail;
    AGR_InfoForName := fail;
fi;

# FIXME: unused?
RECOG.PrintGenericStabChainHint := function ( n )
    local S,g,gens,nn,toc,tocs;
    tocs := AGR_TablesOfContents( "all" );
    nn := AGR_InfoForName( n )[2];
    toc := tocs[1].(nn);
    gens := AtlasGenerators( n, 1 ).generators;
    g := Group( gens );
    S := StabilizerChain( g );
    Print( "InstallAlmostSimpleHint( \"", n, "\", \"StabChainHint\",\n" );
    Print( "  rec( name := \"", n, "\", usemax := " );
    Print( Set( List( toc.maxes, x->x[2] ) ) );
    Print( ",\n       size := ", Size( S ), ",\n  ));\n" );
end;

# dimensions optionally
# subspacedims there or not
# elordersstart unbound ==> start with empty generator list
# if numberrandgens = "logd" then it will use LogInt(d,2)
# if triesforgens = "Xd" then it will use X * d (X a number as a string)
# if orblenlimit = "Xd" then it will use X * d (X a number as a string)
# L2 hint with doing the decision on the fly
#   depending on the ppd-Properties of L2(p)
# This means:
#   rec( numberrandgens := "logd", tries := 10, triesforgens := "1d",
#        orblenlimit := "4d" )
# is the standard low index.

# BUG: The following hint was added a long time ago, but it
# can lead to an infinite loop in DoHintedLowIndex, because
# elordersstart suggests searching for elements of order 31,
#  but no such elements are found.
# See also https://github.com/gap-system/recog/issues/6
# InstallAlmostSimpleHint( "L2(31)", "LowIndexHint",
#   rec( characteristics := [31], dimensions := [1,2,3],
#        elordersstart := [31], numberrandgens := 2, tries := 1,
#        triesforgens := 100, orblenlimit := 32, issimple := true ) );

# if hint in AlmostSimpleHints exists appropriate function is executed
InstallGlobalFunction( LookupHintForSimple,
  function(ri,G,name)
    local dim,f,hi,j,p,q;
    Info(InfoRecog,2,"Looking up hints for ",name,"...");
    if IsBound(RECOG.AlmostSimpleHints.(name)) then
        j := 1;
        hi := RECOG.AlmostSimpleHints.(name);
        f := ri!.field;
        p := Characteristic(f);
        q := Size(f);
        dim := ri!.dimension;
        while j <= Length(hi) do
            if (not IsBound(hi[j].characteristics) or
                p in hi[j].characteristics) and
               (not IsBound(hi[j].fields) or
                q in hi[j].fields) and
               (not IsBound(hi[j].dimensiondivs) or
                ForAny(hi[j].dimensiondivs,d->dim mod d = 0)) and
               (not IsBound(hi[j].dimensions) or
                dim in hi[j].dimensions) then
                # This hint is applicable!
                if hi[j].type = "LowIndexHint" then
                    return DoHintedLowIndex(ri,G,hi[j]);
                elif hi[j].type = "StabChainHint" then
                    return DoHintedStabChain(ri,G,hi[j]);
                # Put other hint types here!
                fi;
            fi;
            j := j + 1;
        od;
    fi;
    Info(InfoRecog,2,"No hint worked, giving up.");
    return fail;
end );

# checks whether the orbit of <vec> under g is not longer than bound
RECOG.shortorbit := function(vec,g,bound)
    local v, i, pos;
    v := StructuralCopy(vec);
    pos := PositionNonZero(vec);
    vec := vec / vec[pos];
    for i in [1..bound] do
        v := v * g;
        if v = v[pos] * vec then
            break;
        fi;
    od;
    return i;
end;

# Under the assumption that G is an almost simple group,
# attempt to guess the "natural" characteristic of the
# group based on the two or three maximal orders of group elements.
#
# Used by FindHomMethodsProjective.ThreeLargeElOrders.
RECOG.findchar:=function(ri,G,randelfunc)
    # randelfunc must be a function taking ri as one argument and returning
    # uniformly distributed random elements in G together with its
    # projective order (as for example below), or fail.
    local mat,vs,vec,bound,count,m1,m2,m3,g,order,list,last,r,p,d,pr;

    if randelfunc = fail then
        pr := ProductReplacer(GeneratorsOfGroup(G));
        randelfunc := function(ri)
          local el;
          el := Next(pr);
          return rec( el := el, order := ProjectiveOrder(el)[1] );
        end;
    fi;

    p := Characteristic(ri!.field);
    d := ri!.dimension;
    mat:=One(G);
    vs:=VectorSpace(GF(p),mat);
    repeat
        vec:=Random(vs);
    until not IsZero(vec);

    if RECOG.shortorbit(vec,Product(GeneratorsOfGroup(G)), 3*d) = 3*d then
        return p;
    fi;

    #find three largest element orders m1, m2, m3
    bound:=32*(LogInt(d,2))^2*6*4;
    count:=0;
    m1:=0;
    m2:=0;
    m3:=0;
    last:=0;
    repeat
        count:=count+1;
        r := randelfunc(ri);
        g := r.el;
        order:=r.order;
        if order >= 3*d then
            return p;
        elif order > m1 then
            m3:=m2;
            m2:=m1;
            m1:=order;
            last:=count;
        elif order<m1 and order>m2 then
            m3:=m2;
            m2:=order;
            last:=count;
        elif order<m2 and order>m3 then
            m3:=order;
            last:=count;
        fi;
    until count=bound or count>=2*last+50;

    #handle ambiguous cases
    if [m1,m2,m3] = [13,7,5] then
        return [[13,7, ["2B2",8]]];
    elif [m1,m2] = [13,8] then
        return [[13,8, ["l",3,3]]];
    elif [m1,m2,m3] = [13,7,6] then
        return [[13,7, ["l",2,13]]];
    elif [m1,m2,m3] = [13,12,6] then
        return [[13,12,["l",2,5]]];
    elif [m1,m2,m3] = [13,12,9] then
        return [[13,12,["G2",3]]];
    elif [m1,m2,m3] = [12,9,6] then
        return [[12,9,["u",4,2]]];
    elif [m1,m2,m3] = [12,9,8] then
        return [[12,9,["u",4,3]]];
    elif [m1,m2] = [5,3] then
        return [[ 5,3,["l",2,4]]];
    elif [m1,m2] = [5,4] then
        return [[5,4,["l",2,9]]];
    elif [m1,m2] = [7,4] then
        return [[7,4,["l",2,7]]];
    elif [m1,m2] = [15,13] then
        return [[15,13,["u",3,4]]];
    elif [m1,m2] = [30,20] then
        return [[30,20,["s",4,5]]];
    elif [m1,m2] = [30,24] then
        return [[30,24,["s",8,2]]];
    elif [m1,m2] = [63,60] then
        return [[63,60,["u",4,5]]];
    elif [m1,m2] = [91,85] then
        return [[91,85,["l",3,16]]];
    fi;

    list:=Filtered(RECOG.grouplist, x->x[1]=m1 and x[2]=m2);
    #one more ambiguous case
    if  Length(list) >=2 and (
        (list[1][3]{[1,2]}=["l",2] and list[2][3][1]="G2") or
        (list[2][3]{[1,2]}=["l",2] and list[1][3][1]="G2")) then
       if m3>m1/2 then
           return Filtered(list,x->x[3][1]="G2");
       else
           return Filtered(list,x->x[3][1]="l");
       fi;
    else
        return list;
    fi;

end;

# just called for PSL (in FindHomMethodsProjective.ThreeLargeElOrders),
# gives hints
RECOG.MakePSL2Hint := function( name, G )
  local d,defchar,f,p,q;
  f := DefaultFieldOfMatrixGroup(G);
  q := Size(f);
  p := Characteristic(f);
  d := DimensionOfMatrixGroup(G);
  defchar := Factors(name[3])[1];
  if p = defchar then
      return fail;
  fi;
  Info(InfoRecog,2,"Making hint for group ",name,"...");
  # we are in cross characteristic.
  # to be made better...
  return rec( elordersstart := [defchar], numberrandgens := 1, tries := 10,
              triesforgens := 3*(name[3]+1),
              orblenlimit := 3*(name[3]+1) );
end;

# is used in FindHomMethodsProjective.ComputeSimpleSocle
# it computes the non-abelian simple socle randomly (it might
# underestimates it)
# if called for an abelian group (even a group with nilpotence class smaller
# than 3?) it runs in an infinite loop
RECOG.simplesocle := function(ri,g)
  local x,y,comm,comm2,comm3,gensH;

  repeat
    x:=RandomElm(ri,"simplesocle",true).el;
  until not ri!.isone(x);

  repeat
    y:=RandomElm(ri,"simplesocle",true).el;
    comm:=Comm(x,y);
  until not ri!.isone(comm);

  repeat
    y:=RandomElm(ri,"simplesocle",true).el;
    comm2:=Comm(comm,comm^y);
  until not ri!.isone(comm2);

  repeat
    y:=RandomElm(ri,"simplesocle",true).el;
    comm3:=Comm(comm2,comm2^y);
  until not ri!.isone(comm3);

  gensH:=FastNormalClosure(g,[comm3],20);

  return gensH;
end;

#! @BeginChunk ComputeSimpleSocle
#! This method randomly computes the non-abelian simple socle and
#! stores it along with additional information if it is called for
#! an almost simple group. Once the non-abelian simple socle is
#! computed the function does not need to be called again for this
#! node and therefore returns <K>NeverApplicable</K>.
#! @EndChunk
BindRecogMethod(FindHomMethodsProjective, "ComputeSimpleSocle",
"compute simple socle of almost simple group",
function(ri,G)
  local x;
  RECOG.SetPseudoRandomStamp(G,"ComputeSimpleSocle");
  ri!.simplesocle := Group(RECOG.simplesocle(ri,G));
  ri!.simplesoclepr := ProductReplacer(ri!.simplesocle);
  ri!.simplesoclerand := EmptyPlist(100);
  Append(ri!.simplesoclerand,GeneratorsOfGroup(ri!.simplesocle));
  ri!.simplesoclerando := EmptyPlist(100);
  for x in ri!.simplesoclerand do
      Add(ri!.simplesoclerando,ProjectiveOrder(x)[1]);
  od;
  ri!.simplesoclerandp := 0;
  ri!.simplesocle!.pseudorandomfunc :=
       [rec( func := Next, args := [ri!.simplesoclepr] )];
  return NeverApplicable;
end);

# computes a random element in the non-abelian simple socle
# and its projective order
# first uses the random generator and afterwards generate
# a new random element
RECOG.RandElFuncSimpleSocle := function(ri)
  local el,ord;
  ri!.simplesoclerandp := ri!.simplesoclerandp + 1;
  if not IsBound(ri!.simplesoclerand[ri!.simplesoclerandp]) then
      el := Next(ri!.simplesoclepr);
      ri!.simplesoclerand[ri!.simplesoclerandp] := el;
      ord := ProjectiveOrder(el)[1];
      ri!.simplesoclerando[ri!.simplesoclerandp] := ord;
  else
      el := ri!.simplesoclerand[ri!.simplesoclerandp];
      ord := ri!.simplesoclerando[ri!.simplesoclerandp];
  fi;
  return rec( el := el, order := ord );
end;

#! @BeginChunk ThreeLargeElOrders
#! In the case when the input group <A>G</A><M> \le PGL(d,p^e)</M> is
#! suspected to be
#! simple but not alternating, this method takes the three
#! largest element orders from a sample of pseudorandom elements of
#! <A>G</A>. From these element orders, it tries to determine whether <A>G</A>
#! is of Lie type and the characteristic of <A>G</A> if it is of
#! Lie type. In the case when <A>G</A> is of Lie type of characteristic
#! different from <M>p</M>, the method also provides
#! a short list of the possible isomorphism types of <A>G</A>.
#!
#! This method assumes that its input is neither alternating nor sporadic and
#! that <Ref Func="ComputeSimpleSocle"/> has already been called.
#!
#! This recognition method is based on the paper <Cite Key="KS09"/>.
#! @EndChunk
BindRecogMethod(FindHomMethodsProjective, "ThreeLargeElOrders",
"recognise Lie type groups and get its characteristic",
function(ri,G)
  local hint,name,namecat,p,res;
  RECOG.SetPseudoRandomStamp(G,"ThreeLargeElOrders");
  ri!.simplesoclerandp := 0;
  p := RECOG.findchar(ri,ri!.simplesocle,RECOG.RandElFuncSimpleSocle);
  if p = Characteristic(ri!.field) then
      Info(InfoRecog,2,"ThreeLargeElOrders: defining characteristic p=",p);
      return false; # FIXME: false = NeverApplicable here really correct?
  fi;
  # Try all possibilities:
  Info(InfoRecog,2,"ThreeLargeElOrders: found ",p);
  for hint in p do
      Info(InfoRecog,2,"Trying ",hint);
      name := hint[3];
      if name[1] = "l" then  # Handle PSL specially
          if name[2] = 2 then
              hint := RECOG.MakePSL2Hint(name,G);
              if hint <> fail then
                  res := DoHintedLowIndex(ri,G,hint);
              else   # we use Pete Brooksbank's methods
                  return SLCR.FindHom(ri,G,2,name[3]);
              fi;
          else
              return SLCR.FindHom(ri,G,name[2],name[3]);
          fi;
      else
          if Length(name) = 3 then
              namecat := Concatenation(UppercaseString(name[1]),
                                       String(name[2]),
                                       "(",String(name[3]),")");
          else
              namecat := name[1];
          fi;
          res := LookupHintForSimple(ri,G,namecat);
      fi;
      if res = true then
          return Success;
      fi;
  od;
  Info(InfoRecog,2,"Did not succeed with hints, giving up...");
  return fail; # FIXME: fail = TemporaryFailure here really correct?
end);

# RECOG.DegreeAlternating := function (orders)
#     local   degs,  prims,  m,  f,  n;
#     degs := [];
#     prims := [];
#     for m in orders do
#         if m > 1 then
#             f := Collected(Factors(m));
#             Sort(f);
#             n := Sum(f, x->x[1]^x[2]);
#             if f[1][1] = 2 then n := n+2; fi;
#             AddSet(degs,n);
#             UniteSet(prims,Set(f,x->x[1]));
#         fi;
#     od;
#     return [degs, prims];
# end;
#
# RECOG.RecognizeAlternating := function (orders)
#     local   tmp,  degs,  prims,  mindeg,  p1,  p2,  i;
#    tmp := RECOG.DegreeAlternating (orders);
#    degs := tmp[1];
#    prims := tmp[2];
#    if Length(degs) = 0 then
#        return "Unknown";
#    fi;
#    mindeg := Maximum (degs);  # minimal possible degree
#
#    p1 := PrevPrimeInt (mindeg + 1);
#    p2 := PrevPrimeInt (p1);
#    if not p1 in prims or not p2 in prims then
#        return 0;
#    fi;
#    if mindeg mod 2 = 1 then
#        if not (mindeg in orders and  mindeg - 2 in orders) then
#            return 0;
#        fi;
#    else
#        if not mindeg - 1 in orders then
#            return 0;
#        fi;
#    fi;
#
#    for i in [3..Minimum (QuoInt(mindeg,2) - 1, 6)] do
#        if IsPrime (i) and IsPrime (mindeg - i) then
#            if not i * (mindeg - i) in orders then
#                return 0;
#            fi;
#        elif IsPrime (i) and IsPrime (mindeg - i -1) then
#            if not i * (mindeg - i - 1) in orders then
#                return 0;
#            fi;
#        fi;
#    od;
#    return mindeg;
# end;
#
# SLPforElementFuncsProjective.Alternating := function(ri,x)
#   local y,slp;
#   RecSnAnIsOne := IsOneProjective;
#   RecSnAnEq := IsEqualProjective;
#   y := FindImageAn(ri!.recogSnAnDeg,x,
#                    ri!.recogSnAnRec[2][1], ri!.recogSnAnRec[2][2],
#                    ri!.recogSnAnRec[3][1], ri!.recogSnAnRec[3][2]);
#   RecSnAnIsOne := IsOne;
#   RecSnAnEq := EQ;
#   if y = fail then return fail; fi;
#   slp := SLPforAn(ri!.recogSnAnDeg,y);
#   return slp;
# end;
#
# SLPforElementFuncsProjective.Symmetric := function(ri,x)
#   local y,slp;
#   RecSnAnIsOne := IsOneProjective;
#   RecSnAnEq := IsEqualProjective;
#   y := FindImageSn(ri!.recogSnAnDeg,x,
#                    ri!.recogSnAnRec[2][1], ri!.recogSnAnRec[2][2],
#                    ri!.recogSnAnRec[3][1], ri!.recogSnAnRec[3][2]);
#   RecSnAnIsOne := IsOne;
#   RecSnAnEq := EQ;
#   if y = fail then return fail; fi;
#   slp := SLPforSn(ri!.recogSnAnDeg,y);
#   return slp;
# end;
#
# FindHomMethodsProjective.AlternatingBBByOrders := function(ri,G)
#   local Gm,RecSnAnEq,RecSnAnIsOne,deg,limit,ordersseen,r;
#   if IsBound(ri!.projordersseen) then
#       ordersseen := ri!.projordersseen;
#   else
#       ordersseen := [];
#   fi;
#   limit := QuoInt(3*ri!.dimension,2);
#   while Length(ordersseen) <= limit do
#       Add(ordersseen,RECOG.ProjectiveOrder(PseudoRandom(G)));
#       if Length(ordersseen) mod 20 = 0 or
#          Length(ordersseen) = limit then
#           deg := RECOG.RecognizeAlternating(ordersseen);
#           Info(InfoRecog,2,ordersseen);
#           if deg > 0 then  # we strongly suspect Alt(deg):
#               # Switch blackbox recognition to projective:
#               Info(InfoRecog,2,"Suspect alternating or symmetric group of ",
#                    "degree ",deg,"...");
#               RecSnAnIsOne := IsOneProjective;
#               RecSnAnEq := IsEqualProjective;
#               Gm := GroupWithMemory(G);
#               r := RecogniseSnAn(deg,Gm,1/100);
#               RecSnAnIsOne := IsOne;
#               RecSnAnEq := EQ;
#               if r = fail or r[1] <> "An" then
#                   Info(InfoRecog,2,"AltByOrders: Did not find generators.");
#                   continue;
#               fi;
#               Info(InfoRecog,2,"Found Alt(",deg,")!");
#               ri!.recogSnAnRec := r;
#               ri!.recogSnAnDeg := deg;
#               SetSize(ri,Factorial(deg)/2);
#               Setslpforelement(ri,SLPforElementFuncsProjective.Alternating);
#               Setslptonice(ri,SLPOfElms(Reversed(r[2])));
#               ForgetMemory(r[2]);
#               ForgetMemory(r[3][1]);
#               SetFilterObj(ri,IsLeaf);
#               SetIsRecogInfoForSimpleGroup(ri,true);
#               return Success;
#           fi;
#       fi;
#   od;
#   return fail; # FIXME: fail = TemporaryFailure here really correct?
# end;

# abbreviation stands for "homomorphism fully deleted permutation module";
# returns a permutation
RECOG.HomFDPM := function(data,x)
  local r;
  r := RECOG.FindPermutation(data.cob*x*data.cobi,data.fdpm);
  if r = fail then
      return fail;
  fi;
  return r[2];
end;

#! @BeginChunk AltSymBBByDegree
#! This method is a black box constructive (?) recognition of alternating
#! and symmetric groups.
#!
#! This algorithm is probably based on the paper <Cite Key="BLGN+05"/>.
#! @EndChunk
# subroutines are in AnSnOnFDPM.gi and also paper reference
BindRecogMethod(FindHomMethodsProjective, "AltSymBBByDegree",
"try BB recognition for dim+1 and/or dim+2 if sensible",
function(ri,G)
  local GG,Gm,RecSnAnEq,RecSnAnIsOne,d,deg,f,fact,hom,newgens,o,orders,p,primes,
        r,totry;
  RECOG.SetPseudoRandomStamp(G,"AltSymBBByDegree");
  d := ri!.dimension;
  orders := RandomOrdersSeen(ri);
  if Length(orders) = 0 then
      orders := [RandomElmOrd(ri,"AltSym",false).order];
  fi;
  primes := Filtered(Primes,x->x <= d+2);
  for o in orders do
      fact := FactorsTD(o,primes);
      if Length(fact[2]) <> 0 then
          Info(InfoRecog,2,"AltSym: prime factor of order excludes A_n");
          return NeverApplicable;
      fi;
  od;
  f := ri!.field;
  # We first try the deleted permutation module method:
  if d >= 6 then
      Info(InfoRecog,3,"Trying deleted permutation module method...");
      r := RECOG.RecogniseFDPM(G,f,1/10);
      if r <> fail and IsRecord(r) then
          # Now make a homomorphism object:
          newgens := List(GeneratorsOfGroup(G),
                          x->RECOG.HomFDPM(r,x));
          if not fail in newgens then
              GG := GroupWithGenerators(newgens);
              hom := GroupHomByFuncWithData(G,GG,RECOG.HomFDPM,r);

              SetHomom(ri,hom);
              Setmethodsforimage(ri,FindHomDbPerm);

              ri!.comment := "FDPM";
              return Success;
          fi;
      fi;
      Info(InfoRecog,3,"Deleted permutation module method failed.");
  fi;

  return TemporaryFailure;    # do not try any more now

# TODO: try out an example that should need this;
#  e.g. start with A_n on k-subsets, k >= 2, then go to perm mats...
#

# FIXME: there is dead code below...

#   p := Characteristic(f);
#   totry := EmptyPlist(2);
#   if (d+1) mod p <> 0 and d+1 > 10 then
#       Add(totry,d+1);
#   fi;
#   if (d+2) mod p = 0 and d+2 > 10 then
#       Add(totry,d+2);
#   fi;
#
#   for deg in totry do
#       Info(InfoRecog,3,"Looking for Alt/Sym(",deg,")...");
#       RecSnAnIsOne := IsOneProjective;
#       RecSnAnEq := IsEqualProjective;
#       Gm := GroupWithMemory(G);
#       r := RecogniseSnAn(deg,Gm,1/100);
#       RecSnAnIsOne := IsOne;
#       RecSnAnEq := EQ;
#       if r = fail then
#           Info(InfoRecog,2,"AltSym: deg=",deg,": did not find generators.");
#           continue;
#       fi;
#       if r[1] = "An" then
#           Info(InfoRecog,2,"Found Alt(",deg,")!");
#           ri!.recogSnAnRec := r;
#           ri!.recogSnAnDeg := deg;
#           SetSize(ri,Factorial(deg)/2);
#           Setslpforelement(ri,SLPforElementFuncsProjective.Alternating);
#           Setslptonice(ri,SLPOfElms(Reversed(r[2])));
#           ForgetMemory(r[2]);
#           ForgetMemory(r[3][1]);
#           SetFilterObj(ri,IsLeaf);
#           SetIsRecogInfoForSimpleGroup(ri,true);
#           ri!.comment := "Alt";
#           return Success;
#       else   # r[1] = "Sn"
#           Info(InfoRecog,2,"Found Sym(",deg,")!");
#           ri!.recogSnAnRec := r;
#           ri!.recogSnAnDeg := deg;
#           SetSize(ri,Factorial(deg));
#           Setslpforelement(ri,SLPforElementFuncsProjective.Symmetric);
#           Setslptonice(ri,SLPOfElms(Reversed(r[2])));
#           ForgetMemory(r[2]);
#           ForgetMemory(r[3][1]);
#           SetFilterObj(ri,IsLeaf);
#           SetIsRecogInfoForAlmostSimpleGroup(ri,true);
#           ri!.comment := "Sym";
#           return Success;
#       fi;
#   od;
#   return TemporaryFailure;
end);

# Looking at element orders to determine which sporadic it could be:

# The following may have been generated by RECOG.MakeSporadicsInfo.
# RECOG.SporadicsElementOrders[i] contains all appearing element orders
# in the sporadic simple group RECOG.SporadicsNames[i].
# RECOG.SporadicsElementOrders[i][j] contains an element order of the
# sporadic simple group RECOG.SporadicsNames[i] with
# probability RECOG.SporadicsProbabilities[i][j].
# RECOG.SporadicsSizes[i] is the size of the sporadic simple group
# RECOG.SporadicsNames[i].
# RECOG.SporadicsKillers contain orders that appear relatively often.
RECOG.SporadicsElementOrders :=
[ [ 1,2,3,5,6,7,10,11,15,19 ],[ 1,2,3,4,5,6,8,11 ],
  [ 1,2,3,4,5,6,8,10,11 ],
  [ 1,2,3,4,5,6,8,9,10,12,15,17,19 ],
  [ 1,2,3,4,5,6,7,8,11,14,15,23 ],[ 1,2,3,4,5,6,7,8,11 ],
  [ 1,2,3,4,5,6,7,8,10,12,15 ],
  [ 1,2,3,4,5,6,7,8,10,12,14,15,17,21,28 ],
  [ 1,2,3,4,5,6,7,8,10,12,13,14,15,16,20,24,26,29 ],
  [ 1,2,3,4,5,6,7,8,10,11,12,15,20 ],
  [ 1,2,3,4,5,6,7,8,10,11,12,14,15,21,23 ],
  [ 1,2,3,4,5,6,7,8,10,11,12,14,15,16,20,21,22,23,24,28,
      29,30,31,33,35,37,40,42,43,44,66 ],
  [ 1,2,3,4,5,6,7,8,10,11,12,14,15,16,19,20,28,31 ],
  [ 1,2,3,4,5,6,7,8,9,10,12,13,14,15,18,19,20,21,24,27,
      28,30,31,36,39 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,30 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,19,20,21,22,25,30, 35,40 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,21,22,24,25,
      28,30,31,33,37,40,42,67 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,20,21,22,23,24,30
     ],[ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,18,20,23,24,28,30 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,18,20,21,24 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,30 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,
      23,24,26,28,30,33,35,36,39,40,42,60 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,
      22,23,24,26,27,28,30,35,36,39,42,60 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,
      22,23,24,26,27,28,29,30,33,35,36,39,42,45,60 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
      21,22,23,24,25,26,27,28,30,31,32,33,34,35,36,38,39,40,
      42,44,46,47,48,52,55,56,60,66,70 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,
      21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,38,39,
      40,41,42,44,45,46,47,48,50,51,52,54,55,56,57,59,60,62,
      66,68,69,70,71,78,84,87,88,92,93,94,95,104,105,110,119 ]
    ,[ 1,2,3,4,5,6,8,10,11,12 ],
  [ 1,2,3,4,5,6,7,8,10,11,12,14 ],
  [ 1,2,3,4,5,6,7,8,10,11,12,14,15,20,30 ],
  [ 1,2,3,4,5,6,7,8,10,12,14,15,24 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,20,22,24,30 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,28,30,40 ],
  [ 1,2,3,4,5,6,7,8,10,12,14,15,16,17,20,21,24,28,30,42 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,14,15,18,19,20,21,22,24,
      25,28,30,35,40,42,44,60 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,21,22,24,30,36,42 ],
  [ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,20,21,
      22,23,24,26,27,28,29,30,33,34,35,36,39,40,42,45,46,54,60,66,70,78,84 ],
  [ 1,2,3,4,5,6,7,8,10,11,12,14,15,16,19,20,22,24,28,30,
      31,38,56 ],[ 1,2,3,4,5,6,8,9,10,12,15,17,18,19,24,34 ]
    ,[ 1,2,3,4,5,6,8,10,12,13,16 ],
  [ 1,2,3,4,5,6,8,10,12,13,16,20 ] ];
RECOG.SporadicsProbabilities :=
[ [ 1/175560,1/120,1/30,1/15,1/6,1/7,1/5,1/11,2/15,3/19 ],
  [ 1/7920,1/48,1/18,1/8,1/5,1/6,1/4,2/11 ],
  [ 1/95040,3/320,5/108,1/16,1/10,1/4,1/4,1/10,2/11 ],
  [ 1/50232960,1/1920,49/9720,1/96,1/15,1/24,1/8,1/9,1/5,1/12,2/15,
      2/17,2/19 ],
  [ 1/10200960,1/2688,1/180,1/32,1/15,1/12,1/7,1/8,2/11,1/7,2/15,
      2/23 ],[ 1/443520,1/384,1/36,3/32,1/5,1/12,2/7,1/8,2/11 ],
  [ 1/604800,3/640,31/1080,1/96,7/150,1/8,1/7,1/8,3/10,1/12,2/15 ],
  [ 1/4030387200,17/322560,2/945,1/84,1/300,1/18,95/4116,1/16,1/20,
      1/6,5/28,1/15,2/17,4/21,1/14 ],
  [ 1/145926144000,283/22364160,1/2160,17/5120,13/3000,1/48,1/28,
      11/192,3/40,1/8,1/52,3/28,1/15,1/8,3/20,1/12,3/52,2/29 ],
  [ 1/44352000,11/23040,1/360,19/960,17/375,5/72,1/7,3/16,1/10,2/11,
      1/12,1/15,1/10 ],
  [ 1/244823040,19/107520,11/3780,1/48,1/60,1/12,1/21,1/16,1/20,
      1/11,1/6,1/7,2/15,2/21,2/23 ],
  [ 1/86775571046077562880,13/21799895040,1/2661120,53/1576960,1/6720,
      2311/2661120,1/420,31/7680,13/960,133/31944,1/32,5/84,1/30,
      1/32,1/80,1/21,13/264,1/23,1/24,1/14,1/29,1/30,3/31,1/33,
      2/35,3/37,1/20,1/21,3/43,1/44,1/33 ],
  [ 1/460815505920,1/161280,1/3240,79/20160,1/180,1/72,29/1372,1/16,
      1/20,1/11,1/36,1/28,2/45,1/4,3/19,1/10,1/14,2/31 ],
  [ 1/90745943887872000,1/92897280,13603/1719506880,257/1935360,1/3000,
      67/25920,1/1176,5/384,5/648,1/120,25/432,1/39,1/56,1/15,5/72,
      1/19,1/20,1/21,1/6,1/9,1/28,1/15,2/31,1/12,2/39 ],
  [ 1/898128000,1/40320,31/29160,1/96,31/750,11/360,1/7,1/8,2/27,
      1/30,2/11,1/12,1/7,1/15,1/15 ],
  [ 1/273030912000000,131/473088000,59/1632960,23/46080,16913/31500000,
      1/192,1/420,9/320,1/27,431/12000,1/22,17/144,1/28,13/180,2/19,
      3/20,1/21,1/22,2/25,1/12,2/35,1/20 ],
  [ 1/51765179004000000,1/39916800,15401/2694384000,1/20160,601/2250000,
      1291/362880,1/168,1/80,1/54,73/3600,1/33,5/288,1/168,28/1125,
      1/18,1/40,1/21,1/11,1/8,1/25,1/28,1/45,5/31,2/33,2/37,1/20,
      1/21,3/67 ],
  [ 1/495766656000,179/31933440,631/2449440,1/1440,1/250,373/12960,
      1/42,1/24,1/54,1/15,1/11,1/18,1/14,1/10,1/18,1/10,1/21,1/11,
      2/23,1/12,1/30 ],
  [ 1/42305421312000,523/743178240,1/116640,139/120960,1/500,79/12960,
      1/56,5/192,1/54,1/20,1/11,2/27,5/56,1/10,1/16,1/18,1/10,
      2/23,1/12,1/28,1/10 ],
  [ 1/448345497600,151/23224320,661/1959552,103/23040,7/1800,187/10368,
      1/84,5/96,1/27,3/40,1/11,31/288,2/13,1/28,1/9,1/9,1/20,2/21,
      1/24 ],
  [ 1/64561751654400,4297/7357464576,11419/176359680,181/276480,1/600,
      9121/933120,1/42,17/384,5/108,1/24,1/11,79/864,2/13,1/14,1/30,
      1/16,7/108,1/20,1/21,1/11,1/24,1/30 ],
  [ 1/4157776806543360000,39239/12752938598400,7802083/4035109478400,
      1061/11612160,1433/15120000,198391/69672960,2/2205,79/23040,1/216,
      109/9600,1/66,10949/207360,1/156,1/42,277/5400,1/32,1/24,
      37/480,17/252,1/22,2/23,25/288,1/52,1/14,13/120,1/33,1/35,
      1/36,2/39,1/40,1/84,1/60 ],
  [ 1/4089470473293004800,407161/129123503308800,161281/148565394432,
      239/5806080,1/25200,1036823/705438720,1/840,1/128,127/17496,
      11/1200,1/44,529/12960,1/39,5/168,1/72,1/16,1/17,13/216,1/30,
      1/42,3/44,2/23,1/16,1/13,1/27,1/28,7/120,1/35,1/18,2/39,
      1/42,1/60 ],
  [ 1/1255205709190661721292800,6439/1032988026470400,144613199/
        4412392214630400,25/6967296,1/907200,159797/564350976,67/123480,
      11/4608,1189/1049760,7/4800,1/132,4741/311040,1/234,5/168,
      103/16200,1/32,1/17,11/288,1/48,17/252,1/44,2/23,7/72,1/26,
      1/27,1/28,2/29,1/24,2/33,1/35,1/24,4/117,5/84,2/45,1/60 ],
  [ 1/4154781481226426191177580544000000,
      34727139371/281639525236291462496256000,160187/10459003768012800,
      56445211/3060705263616000,1873/11088000000,7216687/1418939596800,
      1/564480,18983/123863040,5/34992,667/2688000,1/1320,12629/3732480,
      1/312,871/564480,31/3600,1/96,1/68,7/432,1/38,323/12000,1/252,
      5/264,1/23,19/432,1/25,3/104,1/27,5/224,67/1200,2/31,1/32,
      1/66,3/68,1/70,5/108,1/38,1/39,1/20,1/36,1/44,1/23,2/47,
      1/48,1/52,1/55,1/56,1/30,1/66,1/70 ],
  [ 1/808017424794512875886459904961710757005754368000000000,
      952987291/132953007399245638117682577408000000,
      1309301528411/299423045898886400305790976000,
      228177889/1608412858851262464000,361177/34128864000000000,
      352968797/83672030144102400,16369/1382422809600,80467/177124147200,
      7/18895680,1270627/532224000000,1/1045440,20669/313528320,
      31/949104,9/250880,8611/40824000,1/3072,1/2856,91/139968,1/1140,
      2323/1152000,907/370440,3/3520,1/276,167/13824,1/250,1/208,
      1/162,3/392,1/87,529/43200,1/93,1/64,5/1188,1/136,31/2100,
      1/48,1/76,25/702,49/1600,1/41,1/56,1/176,1/135,3/92,1/47,
      1/96,1/50,1/51,3/104,1/54,1/110,5/112,1/57,2/59,41/720,1/31,
      1/44,1/68,2/69,3/140,2/71,1/26,1/28,2/87,1/44,1/46,2/93,
      1/47,2/95,1/52,1/105,1/110,2/119 ],
  [ 1/190080,17/1920,5/216,3/32,1/20,5/24,1/8,3/20,1/11,1/4 ],
  [ 1/887040,29/8960,1/72,7/96,1/10,1/8,1/7,1/8,1/10,1/11,1/12,1/7
     ],[ 1/88704000,11/21504,1/720,7/240,17/750,17/240,1/14,1/8,1/6,
      1/11,1/12,1/14,1/30,1/5,1/30 ],
  [ 1/1209600,103/26880,31/2160,11/192,7/300,7/48,1/14,5/48,3/20,
      5/24,1/14,1/15,1/12 ],
  [ 1/1796256000,67/887040,31/58320,17/2880,31/1500,31/720,1/14,5/48,
      1/27,7/60,1/11,7/72,1/14,1/30,1/10,1/11,1/12,1/30 ],
  [ 1/896690995200,16081/2554675200,661/3919104,1031/322560,7/3600,
      2879/103680,1/168,53/1440,1/54,89/1200,1/22,65/576,1/13,3/56,
      1/18,1/16,1/18,1/40,1/21,1/22,19/144,1/28,1/30,1/20 ],
  [ 1/8060774400,23/387072,1/945,9/1120,1/600,473/7560,95/8232,7/96,
      1/24,1/8,19/168,1/30,1/8,1/17,1/20,2/21,1/12,1/28,1/30,1/21 ]
    ,[ 1/546061824000000,7057/25546752000,59/3265920,119351/177408000,
      16913/63000000,2497/362880,1/840,21/640,1/54,691/24000,1/44,
      101/1440,5/168,13/360,1/18,1/19,743/6000,1/42,1/44,1/8,1/25,
      1/28,7/120,1/35,1/10,1/42,1/22,1/60 ],
  [ 1/129123503308800,10781/17517772800,11419/352719360,329/414720,
      1/1200,46757/4354560,1/84,1/32,5/216,17/400,1/22,295/2592,1/13,
      1/12,1/60,1/16,29/216,1/20,1/42,1/22,1/8,1/20,1/36,1/42 ],
  [ 1/2510411418381323442585600,352149857/65431527572688076800,
      144613199/8824784429260800,12091/4180377600,1/1814400,
      20115929623/65368773550080,67/246960,13/7680,1189/2099520,97/67200,
      1/264,282547/13063680,1/468,31/1680,103/32400,1/32,1/34,
      4153/139968,41/2400,17/504,7/264,1/23,7/96,5/156,1/54,2/21,
      1/29,11/240,1/33,1/34,1/70,31/432,2/117,1/40,11/168,1/45,
      1/23,1/54,1/60,1/33,1/70,1/39,1/84 ],
  [ 1/921631011840,401/67415040,1/6480,79/40320,1/360,17/720,29/2744,
      43/672,7/120,1/22,1/72,5/56,1/45,1/8,3/38,1/20,1/22,1/12,
      1/28,1/15,1/31,3/38,1/14 ],
  [ 1/100465920,91/195840,49/19440,1/64,1/30,11/144,5/48,1/18,1/10,
      1/8,1/15,1/17,1/6,1/19,1/12,1/17 ],
  [ 1/17971200,23/30720,1/108,11/384,1/50,1/12,3/16,1/10,1/6,2/13,
      1/4 ],
  [ 1/35942400,23/61440,1/216,37/1280,1/100,1/24,3/16,1/20,
      1/4,1/13,1/4,1/10 ] ];
RECOG.SporadicsNames :=
[ "J1","M11","M12","J3","M23","M22","J2","He","Ru","HS","M24",
  "J4","ON","Th","McL","HN","Ly","Co3","Co2","Suz","Fi22","Co1",
  "Fi23","Fi24'","B","M","M12.2","M22.2","HS.2","J2.2","McL.2","Suz.2",
  "He.2","HN.2","Fi22.2","Fi24'.2","ON.2","J3.2","2F4(2)'","2F4(2)'.2"];
RECOG.SporadicsSizes :=
[ 175560,7920,95040,50232960,10200960,443520,604800,4030387200,
  145926144000,44352000,244823040,86775571046077562880,460815505920,
  90745943887872000,898128000,273030912000000,51765179004000000,
  495766656000,42305421312000,448345497600,64561751654400,
  4157776806543360000,4089470473293004800,1255205709190661721292800,
  4154781481226426191177580544000000,
  808017424794512875886459904961710757005754368000000000,190080,887040,
  88704000,1209600,1796256000,896690995200,8060774400,546061824000000,
  129123503308800,2510411418381323442585600,921631011840,100465920,
  17971200,35942400 ];
RECOG.SporadicsKillers :=
[ [[ 5,7 ]],[[ 5,7 ]],[[ 6,7 ]],[[ 11,9 ]],[[ 10,9 ]],[[ 5,7 ]],[[ 7,9 ]],
  [[ 11,14 ]],[[ 14,15 ]],[[ 10,8 ]],[[ 12,11 ]],[[ 29,20,26,23 ]],
  [[ 15,14 ]],[[ 20,19 ]],[[ 13,11 ]],[[ 12,16 ]],[[ 19,23 ]],[[ 11,14,16 ]],
  [[ 17,14,21 ]],[[ 15,13 ]],[ [ 18 .. 22 ] ],
  [ [ 26 .. 32 ],[ 25 .. 32 ] ],[ [ 28 .. 32 ],[ 27 .. 32 ] ],
  [ [ 27 .. 35 ],[ 29 .. 35 ],[ 27,29,34 ] ],  # the latter is for Fi23
  [ [ 31 .. 49 ],[ 40,41,42,43,44,45,46,48,49 ] ], # the latter is agains Fi23
  [ [ 32 .. 73 ],[ 61 .. 73 ] ],[[ 6,10 ]],[[ 7,12 ]],[[ 9,14 ]],[[ 9,10 ]],
  [[ 15,8,10 ]],[[ 13,12,21 ]],[[ 11,13,10 ]],[[ 25,17,20 ]],
  [[ 21,17 ],[23,24]],   # the latter is to distinguish Fi22.2 and Fi22
  [[ 35,32,23,26 ],[ 36,37,38,40,41,42,43 ]], # the latter is for Fi23
  [[ 18,12,14 ]],[[ 10,13 ]],[[ 7,11 ]],[[ 9,11 ]] ];
RECOG.SporadicsWorkers := [];
# Removed to avoid dependency on unpublished package gensift:
#RECOG.SporadicsWorkers[2] := SporadicsWorkerGenSift;   # M11
# and same for: M12, M22, J2, HS, Ly, Co3, Co2

# RECOG.MakeSporadicsInfo := function(name)
#   local ct,i,index,killers,o,orders,p,pos,prob,probs,probscopy,sum;
#   ct := CharacterTable(name);
#   orders := Set(OrdersClassRepresentatives(ct));
#   probs := [];
#   for o in orders do
#       prob := 0;
#       pos := Positions(OrdersClassRepresentatives(ct),o);
#       for p in pos do
#           prob := prob + 1/SizesCentralizers(ct)[p];
#       od;
#       Add(probs,prob);
#   od;
#   index := [1..Length(orders)];
#   probscopy := ShallowCopy(probs);
#   SortParallel(probscopy,index);
#   sum := probscopy[Length(orders)];
#   i := Length(orders);
#   repeat
#       i := i - 1;
#       sum := sum + probscopy[i];
#   until sum > 1/4;
#   killers := index{[i..Length(orders)]};
#   return rec( size := Size(ct), orders := orders,
#               probabilities := probs, killers := killers, name := name );
# end;

# returns a number (the projective order of <m>?) if the order is smaller than
# 120 otherwise fail
RECOG.RuleOutSmallProjOrder := function(m)
  local l,o,v;
  if IsPerm(m) then
      o := Order(m);
      if o > 119 then
          return fail;
      fi;
      return o;
  fi;
  v := ShallowCopy(m[1]);
  Randomize(v);
  ORB_NormalizeVector(v);
  o := Orb([m],v,OnLines,rec( hashlen := 300, report := 0 ));
  Enumerate(o,121);
  if not IsClosed(o) then
      return fail;
  fi;
  l := Length(o);
  Randomize(v);
  ORB_NormalizeVector(v);
  o := Orb([m],v,OnLines,rec( hashlen := 300, report := 0 ));
  Enumerate(o,121);
  if not IsClosed(o) then
      return fail;
  fi;
  l := Lcm(l,Length(o));
  if l > 119 then
      return fail;
  fi;
  return l;
end;

#! @BeginChunk SporadicsByOrders
#! This method returns a list of sporadic simple groups that <A>G</A>
#! possibly could be. Therefore it checks whether
#! <A>G</A> has elements of orders that do not appear in sporadic
#! groups and otherwise checks whether the most common ("killer") orders
#! of the sporadic groups appear.
#! Afterwards it creates hints that come out of a table for the sporadic
#! simple groups.
#! @EndChunk
BindRecogMethod(FindHomMethodsProjective, "SporadicsByOrders",
"generate a few random elements and compute the proj. orders",
function(ri,G)
  local count,gens,i,j,jj,k,killers,l,limit,o,ordersseen,pp,r,raus,res,x;

  RECOG.SetPseudoRandomStamp(G,"SporadicsByOrders");

  l := [1..Length(RECOG.SporadicsNames)];
  pp := 0*l;
  ordersseen := [];
  count := 0;
  gens := GeneratorsOfGroup(G);
  limit := 120+Length(gens);
  for i in [1..limit] do
      if i <= Length(gens) then
          r := rec( el := gens[i] );
      else
          r := RandomElm(ri,"SporadicsByOrders",false);
      fi;
      o := RECOG.RuleOutSmallProjOrder(r.el);
      if o = fail then
          Info(InfoRecog,2,"Ruled out all sporadic groups.");
          return NeverApplicable;
      elif i <= Length(gens) then
          r.order := OrderFunc(ri)(r.el);
      else
          GetElmOrd(ri,r);
      fi;
      o := r.order;
      x := r.el;
      AddSet(ordersseen,o);
      Info(InfoRecog,3,"Found order: ",String(o,3)," (element #",i,")");
      l := Filtered(l,i->o in RECOG.SporadicsElementOrders[i]);
      if l = [] then
          Info(InfoRecog,2,"Ruled out all sporadic groups.");
          return NeverApplicable;
      fi;
      # Throw out improbable ones:
      j := 1;
      while j <= Length(l) do
          if Length(l) = 1 then
              limit := 1/1000;
          else
              limit := 1/400;
          fi;
          jj := l[j];
          raus := false;
          # check whether orders appear in killers
          for k in [1..Length(RECOG.SporadicsElementOrders[jj])] do
              if not RECOG.SporadicsElementOrders[jj][k] in ordersseen and
                 (1-RECOG.SporadicsProbabilities[jj][k])^i < limit then
                  Info(InfoRecog,3,"Have thrown out ",RECOG.SporadicsNames[jj],
                       " (did not see order ",
                       RECOG.SporadicsElementOrders[jj][k],")");
                  raus := true;
                  break;
              fi;
          od;
          if not raus and IsBound(RECOG.SporadicsKillers[jj]) then
            for killers in RECOG.SporadicsKillers[jj] do
              if Intersection(ordersseen,
                              RECOG.SporadicsElementOrders[jj]{killers})=[]
                 and (1-Sum(RECOG.SporadicsProbabilities[jj]{killers}))^i
                     < 10^-3 then
                  raus := true;
                  break;
                  Info(InfoRecog,3,"Have thrown out ",RECOG.SporadicsNames[jj],
                       " (did not see orders in ",
                       RECOG.SporadicsElementOrders[jj]{killers},")");
              fi;
            od;
          fi;
          if raus then
              Remove(l,j);
          else
              j := j + 1;
          fi;
      od;
      if l = [] then
          Info(InfoRecog,2,"Ruled out all sporadic groups.");
          return NeverApplicable;
      elif Length(l) = 1 then
        count := count + 1;
        if count >= 9 then
          Info(InfoRecog,2,"I guess that this is the sporadic simple group ",
               RECOG.SporadicsNames[l[1]],".");
          break;
        fi;
      fi;
      if Length(l) < 6 then
          Info(InfoRecog,2,"Possible sporadics left: ",
               RECOG.SporadicsNames{l}," i=",i);
      else
          Info(InfoRecog,2,"Possible sporadics left: ",Length(l)," i=",i);
      fi;
  od;
  if ValueOption("DEBUGRECOGSPORADICS") <> fail then
      return RECOG.SporadicsNames{l};
  fi;
  for i in [1..Length(l)] do
      Info(InfoRecog,2,"Trying hint for ",RECOG.SporadicsNames[l[i]],"...");
      res := LookupHintForSimple(ri,G,RECOG.SporadicsNames[l[i]]);
      if res = true then
          return Success;
      fi;
      if IsBound(RECOG.SporadicsWorkers[l[i]]) then
          Info(InfoRecog,2,"Calling its installed worker...");
          res := RECOG.SporadicsWorkers[l[1]](RECOG.SporadicsNames[l[i]],
                                        RECOG.SporadicsSizes[l[i]],ri,G);
          if res = true then
              return Success;
          fi;
      fi;
      Info(InfoRecog,2,"This did not work.");
  od;
  return false; # FIXME: false = NeverApplicable here really correct?
end);

# Data for the function NameSporadic
RECOG.NameSporadicData := MakeImmutable([
    rec(name := "M11",
        maximalOrdersOverset := [5, 6, 8, 11],
        maximalOrdersSubset := [],
        length := 4),
    rec(name := "M12",
        maximalOrdersOverset := [6, 8, 10, 11],
        maximalOrdersSubset := [],
        length := 4),
    rec(name := "M22",
        maximalOrdersOverset := [5, 6, 7, 8, 11],
        maximalOrdersSubset := [],
        length := 5),
    rec(name := "M23",
        maximalOrdersOverset := [6, 8, 11, 14, 15, 23],
        maximalOrdersSubset := [11, 14, 15, 23]),
    rec(name := "M24",
        maximalOrdersOverset := [8, 10, 11, 12, 14, 15, 21, 23],
        maximalOrdersSubset := [11, 21, 23]),
    rec(name := "J1",
        maximalOrdersOverset := [6, 7, 10, 11, 15, 19],
        maximalOrdersSubset := [11, 15, 19]),
    rec(name := "J2",
        maximalOrdersOverset := [7, 8, 10, 12, 15],
        maximalOrdersSubset := [7, 12, 15]),
    rec(name := "J3",
        maximalOrdersOverset := [8, 9, 10, 12, 15, 17, 19],
        maximalOrdersSubset := [15, 17, 19]),
    rec(name := "HS",
        maximalOrdersOverset := [7, 8, 10, 11, 12, 15, 20],
        maximalOrdersSubset := [11, 20]),
    rec(name := "McL",
        maximalOrdersOverset := [8, 9, 11, 12, 14, 30],
        maximalOrdersSubset := [11, 14, 30]),
    rec(name := "Suz",
        maximalOrdersOverset := [11, 13, 14, 15, 18, 20, 21, 24],
        maximalOrdersSubset := [11, 13]),
    rec(name := "Ru",
        maximalOrdersOverset := [14, 15, 16, 20, 24, 26, 29],
        maximalOrdersSubset := [26, 29]),
    rec(name := "Co3",
        maximalOrdersOverset := [14, 18, 20, 21, 22, 23, 24, 30],
        maximalOrdersSubset := [22, 23, 24, 30]),
    rec(name := "Co2",
        maximalOrdersOverset := [11, 16, 18, 20, 23, 24, 28, 30],
        maximalOrdersSubset := [16, 23, 28, 30]),
    rec(name := "Co1",
        maximalOrdersOverset := [16, 22, 23, 24, 26, 28, 33, 35, 36, 39, 40, 42, 60],
        maximalOrdersSubset := [33, 42]),
    rec(name := "ON",
        maximalOrdersOverset := [11, 12, 15, 16, 19, 20, 28, 31],
        maximalOrdersSubset := [19, 28, 31]),
    rec(name := "Fi22",
        maximalOrdersOverset := [13, 14, 16, 18, 20, 21, 22, 24, 30],
        maximalOrdersSubset := [13, 24, 30]),
    rec(name := "He",
        maximalOrdersOverset := [8, 10, 12, 15, 17, 21, 28],
        maximalOrdersSubset := [17, 28]),
    rec(name := "Ly",
        maximalOrdersOverset := [18, 22, 24, 25, 28, 30, 31, 33, 37, 40, 42, 67],
        maximalOrdersSubset := [31, 67]),
    rec(name := "J4",
        maximalOrdersOverset := [16, 23, 24, 28, 29, 30, 31, 33, 35, 37, 40, 42, 43, 44, 66],
        maximalOrdersSubset := [37, 43]),
    rec(name := "Fi23",
        maximalOrdersOverset := [13, 14, 16, 17, 22, 23, 24, 26, 27, 28, 35, 36, 39, 42, 60],
        maximalOrdersSubset := [17, 23]),
    rec(name := "Fi24'",
        maximalOrdersOverset := [16, 17, 22, 23, 24, 26, 27, 28, 29, 33, 35, 36, 39, 42, 45, 60],
        maximalOrdersSubset := [17, 29]),
    rec(name := "Th",
        maximalOrdersOverset := [19, 20, 21, 24, 27, 28, 30, 31, 36, 39],
        maximalOrdersSubset := [19, 31, 39]),
]);
#! @BeginChunk NameSporadic
#! This method returns a list of sporadic simple groups that the group
#! underlying <A>ri</A> could be. It does not recognise extensions of sporadic
#! simple groups nor the Monster and the Baby Monster group. It is based on the
#! Magma v2.24.10 function <C>RecognizeSporadic</C>.
#! @EndChunk
# TODO G is unused
BindRecogMethod(FindHomMethodsProjective, "NameSporadic",
"generate maximal orders",
function(ri, G)
    local orders, setOfOrders, maximalOrders, isMaximal,
        namesOfPossibleSporadics, res, i, j, data, name;
    orders := [];
    #do we need SetPseudoRandomStamp?
    for i in [1 .. 500] do
        Add(orders, RandomElmOrd(ri, "NameSporadic", false).order);
    od;
    # Compute maximal orders. Maximal in the sense that it does not divide the
    # order of another group element.
    setOfOrders := AsSet(orders);
    # All orders we look for are <= 66.
    if setOfOrders[Length(setOfOrders)] > 67 then
        return NeverApplicable;
    fi;
    maximalOrders := [];
    for i in [1..Length(setOfOrders)] do
        isMaximal := true;
        for j in [i+1..Length(setOfOrders)] do
            if setOfOrders[j] mod setOfOrders[i] = 0 then
                isMaximal := false;
                break;
            fi;
        od;
        if isMaximal then
            Add(maximalOrders, setOfOrders[i]);
        fi;
    od;
    namesOfPossibleSporadics := [];
    for data in RECOG.NameSporadicData do
        if IsBound(data.length) and not Length(maximalOrders) = data.length then
            continue;
        fi;
        if IsSubset(maximalOrders, data.maximalOrdersSubset)
                and IsSubset(data.maximalOrdersOverset, maximalOrders) then
            Add(namesOfPossibleSporadics, data.name);
        fi;
    od;
    # HN works a bit differently
    if IsSubset([9, 12, 14, 19, 21, 22, 25, 30, 35, 40], maximalOrders)
            and (IsSubset(maximalOrders, [19]) or IsSubset(maximalOrders, [21]))
    then
        Add(namesOfPossibleSporadics, "HN");
    fi;
    if ValueOption("DEBUGRECOGSPORADICS") <> fail then
        return namesOfPossibleSporadics;
    fi;
    for name in namesOfPossibleSporadics do
        Info(InfoRecog, 2, "Trying hint for ", name,
             "...");
        res := LookupHintForSimple(ri, Grp(ri), name);
        if res = true then return Success; fi;
        Info(InfoRecog, 2, "This did not work.");
    od;
    return NeverApplicable;
end);

Quelle almostsimple.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.38 Sekunden (vorverarbeitet) ]