SSL risotest.gi   Interaktion und
Portierbarkeitunbekannt

#############################################################################
##
#W  risotest.gi                GrpConst                    Hans Ulrich Besche
#W                                                               Bettina Eick
##

#############################################################################
##
#F  AddRandomTestInfosFEM( Finfo )
##
##  To the record Finfo, containing the frattinifree group Finfo.F, a number
##  of fields are added which are used to run the random isomorphism test 
##  of groups with the frattini-factor Finfo.F
##
InstallGlobalFunction( AddRandomTestInfosFEM, function( arg )
    local F, elms, orb, orbs, orbss, ord, typ, typs, ntyps, i, j, pos, poses,
          nposes, qual, size, spos, pcgs, Finfo, alter;

    Finfo := arg[ 1 ];
    if Length( arg ) > 1 then
        alter := arg[ 2 ];
    else
        alter := 1;
    fi;
    F := Finfo.F;
    size := Size( F );
    pcgs := Pcgs( F );
    Finfo.lmin := Length( MinimalGeneratingSet( F ) );
    Finfo.lgen := Length( pcgs );
    elms := AttributeValueNotSet( AsList, F );
    orbs := Orbits( F, elms );

    # the orbs will be classified according to the typ-information in typs
    # all elements of one typ are collected in one list in orbss
    typs := [];
    orbss := [];
    for orb in orbs do
        ord := Order( orb[ 1 ] );
        typ := [ ord, Length( orb ) ];
        i := 1;
        repeat
            Add( typ, orb[ 1 ] ^ Primes[ i ] in orb );
            i := i + 1;
        until Primes[ i ] > ord or i > 20;
        i := Position( typs, typ );
        if i = fail then
            Add( typs, typ );
            Add( orbss, ShallowCopy( orb ) );
        else
            Append( orbss[ i ], orb );
        fi;
    od;

    # create all sensible strategies for generator selection
    ntyps := Length( typs );
    poses := List( [ 2 .. ntyps ], x -> [ x ] );
    for i in [ 2 .. Finfo.lmin ] do
        nposes := [];
        for pos in poses do
            Append(nposes,List([pos[i-1]..ntyps],x->Concatenation(pos,[x])));
        od;
        poses := nposes;
    od;

    # sort the strategies according to the number of generating sets
    typs := List( orbss, Length );
    qual := List( poses, x-> Product( typs{ x } ) );
    SortParallel( qual, poses );

    # look up the first strategie which will generate the group
    for pos in poses do
        for i in [ 1 .. 16 ] do
            if size = Size( Group( List( pos, x-> Random( orbss[ x ])))) then
                if alter = 1 then
                    spos := Set( pos );
                    Finfo.geninds := List( spos, x->Number( pos, y->y=x ) );
                    for j in [ 1 .. Length( spos ) ] do
                        Finfo.(j) := List( orbss[ spos[ j ] ], x ->
                                     ExponentsOfPcElement( pcgs, x ) );
                    od;
                    Info( InfoRandIso, 4, "  F-strategy: ", Finfo.lmin,
                          " generators with ", Product( List( pos ),
                          x -> Length( orbss[ x ] ) ), " combinations" );
                    return;
                elif IsInt( alter ) then
                    alter := alter - 1 / 2;
                fi;
            fi;
        od;
        alter := Int( alter );
    od;

    Info( InfoWarning, 1, "AddRandomTestInfos called recursive" );
    AddRandomTestInfosFEM( Finfo );
end);

#############################################################################
##
#F  PermGensGensFEM( famPcgs, specialPcgs, gens1, gens2 ) . . . . . . . local
##
InstallGlobalFunction( PermGensGensFEM, function( fam, spcgs, gens1, gens2 )
    local i, j, perm, l1, l2, elem1, elem2, indices, rel, g;

    if Size( Group( spcgs ) ) <> Size( Group( fam ) ) then
        Error( "PermGensGensFEM: spcgs should generate family group" );
    fi;
    gens1 := CodeGenerators( gens1, spcgs ).pcgs;
    gens2 := CodeGenerators( gens2, spcgs ).pcgs;
    l1 := [ gens1[ 1 ] ^ Order( gens1[ 1 ] ) ];
    l2 := [ l1[ 1 ] ];
    rel := RelativeOrders( gens1 );
    for i in Reversed( [ 1 .. Length( gens1 ) ] ) do
        elem1 := ShallowCopy( l1 );
        elem2 := ShallowCopy( l2 );
        for j in [ 1 .. rel[ i ] - 1 ] do
            Append( elem1, gens1[ i ] ^ j * l1 );
            Append( elem2, gens2[ i ] ^ j * l2 );
        od;
        l1 := elem1;
        l2 := elem2;
    od;
    rel := RelativeOrders( fam );
    indices := [];
    indices[ Length( rel ) ] := 1;
    for i in Reversed( [  2 .. Length( rel ) ] ) do
        indices[ i - 1 ] := indices[ i ] * rel[ i ];
    od;

    l1 := [ ]; l2 := [ ];
    for i in [ 1 .. Length( elem1 ) ] do
        Add( l1, ExponentsOfPcElement( fam, elem1[ i ] ) * indices  + 1 );
        Add( l2, ExponentsOfPcElement( fam, elem2[ i ] ) * indices  + 1 );
    od;

    perm := [];
    for i in [ 1 .. Length( l1 ) ] do
        perm[ l1[ i ] ] := l2[ i ];
    od;

    return PermList( perm );
end);

#############################################################################
##
#F  RandomIsomorphismTestFEM( list, Finfo )
##
##  test groups generated by the frattini extension method on isomorphism
##
InstallGlobalFunction( RandomIsomorphismTestFEM, function( list, Finfo )
    local i, j, k, l, gi, ek, n, p,
          size, grps, spcgs, lgws, g, fams,
          elms, t, ord, orb, orbs, orbss, tnorbss, norbss, fsize, exts,
          pos, poses, genpos, typ, typs, ttyps, inds, 
          gensys, typscache, ngensets, misses, stmp,
          rem, mhits, hasAutos, disting, found, r, gens, code, perm, ident;

    size  := list[ 1 ].order;
    grps  := List( list, PcGroupCodeRec );
    fams  := List( grps, FamilyPcgs );
    spcgs := List( grps, SpecialPcgs );
    lgws  := List( spcgs, LGWeights );
    misses := List( list, x -> 0 );

    # return if LGWeights are different
    t := Set( lgws );
    if Length( t ) > 1 then
        Info( InfoRandIso, 3, " split ", Length( list ),
              " groups with LGWeights in ", Length( t ), " sublists" );
        return rec( subl := List( t,
                x->list{ Filtered( [1..Length(list)], y -> x=lgws[y] ) } ) );
    fi;

    # derive generator-system of the grps from Finfo
    exts := List( [ Finfo.lgen + 1 .. Length( fams[ 1 ] ) ],
                  x -> RelativeOrderOfPcElement( fams[1], fams[1][x] ) );
    exts := Cartesian( List( exts, x-> [ 0 .. x - 1 ] ) );
    fsize := Length( exts );
    gensys := List( list, x-> [] );
    typscache := List( list, x-> [] );
    n := Length( list );
    for gi in [ 1 .. n ]  do
        g := grps[ gi ];
        for i in [ 1 .. Length( Finfo.geninds ) ] do
            # investigation of the i-th generator type of g/phi(g) for the
            # gi-th group

            # properties of the conjugacy classes
            t := List( Finfo.(i), x-> List( exts, y ->
                  PcElementByExponentsNC( fams[gi], Concatenation( x, y ))));
            orbs := Orbits( g, Concatenation( t ) );
            typs := [];
            orbss := [];
            for orb in orbs do
                ord := Order( orb[ 1 ] );
                typ := [ ord, Length( orb ) ];
                j := 1;
                repeat
                    Add( typ, orb[ 1 ] ^ Primes[ j ] in orb );
                    j := j + 1;
                until Primes[ j ] > ord or j > 20;
                j := Position( typs, typ );
                if j = fail then
                    Add( typs, typ );
                    Add( orbss, [ orb ] );
                else
                    Add( orbss[ j ], orb );
                fi;
            od;
            SortParallel( typs, orbss );
            Add( typscache[ gi ], typs );

            # the fusion of the typs of conjugacy classes into elements
            # of g/phi(g)
            orbs := List( orbss, Concatenation );
            inds := Concatenation( List( [ 1 .. Length( orbs ) ],
                                x-> x + 0 * [ 1 .. Length( orbs[ x ] ) ] ) );
            elms := Concatenation( orbs );
            ttyps :=List(t,x->Collected(List(x,y->inds[ Position(elms,y)])));
            Add( typscache[ gi ], Collected( ttyps ) );

            # classify the conjugacy classes according to the fusion
            norbss := [];
            elms := Concatenation( t );
            for orbs in orbss do
                typs := [];
                tnorbss := [];
                for orb in orbs do
                    # all elements in the conjugacy class orb of g[gi] will
                    # fuse into the same conjugacy class of g/phi(g)
                    typ := ttyps[ 1+Int((Position(elms, orb[1])-1)/fsize) ];
                    p := Position( typs, typ );
                    if p = fail then 
                        Add( typs, typ );
                        Add( tnorbss, ShallowCopy( orb ) );
                    else
                        Append( tnorbss[ p ], orb );
                    fi;
                od;
                SortParallel( typs, tnorbss );
                Add( typscache[ gi ], typs );
                Append( norbss, tnorbss );
            od;
            inds := List( norbss, Length );
            Add( typscache[ gi ], inds );
            SortParallel( inds, norbss );

            # the images of the i-th generator type of g/phi(g) for the
            # gi-th group sorted according to their priority
            gensys[ gi ][ i ] := norbss;
        od;
    od;

    # look if the information collected in 'typscache' was identical
    t := Set( typscache );
    if Length( t ) > 1 then
        Info( InfoRandIso, 3, " split ", n,
              " groups with typscache in ", Length( t ), " sublists" );
        return rec( subl := List( t,
            x -> list{ Filtered( [1..Length(list)], y->x=typscache[y] ) } ));
    fi;

    # find a selection from the priorisation which will produce generating
    # sets for all groups
    genpos := Concatenation( List( [ 1 .. Length( Finfo.geninds ) ], 
                                x -> x + 0 * [ 1 .. Finfo.geninds[ x ] ] ) );
    poses := Cartesian( List( genpos, x -> [ 1..Length(gensys[1][x]) ] ) );
    inds  := List( poses, x -> Product( [ 1 .. Finfo.lmin ],
                   y -> Length( gensys[ 1 ][ genpos[ y ] ][ x[ y ] ] ) ) );
    SortParallel( inds, poses );

    # test them
    i := 0;
    repeat
        i := i + 1;
        pos := poses[ i ];
        gi := 0;
        repeat
            gi := gi + 1;
            j := 1;
            repeat
                if Size( Group( List( [ 1..Finfo.lmin ], x -> Random(
                        gensys[gi][genpos[x]][ pos[x] ] ) ) ) ) = size then
                    j := -1;
                else
                    j := j + 1;
                fi;
            until j > 12 or j < 0;
        until j > 12 or gi = n;
    until j < 0 or i = Length( poses );

    if j < 0 then 
        # remove all generators which are not from the chosen strategy
        gensys := List( gensys, x -> List( [ 1 .. Finfo.lmin ],
                                       y -> x[ genpos[ y ] ][ pos[ y ] ] ) );
    else
        Info( InfoRandIso, 1, "   no common generator strategy" );
        pos := List( pos, x -> 1 );
        gensys := List( gensys, x -> List( [ 1 .. Finfo.lmin ],
                                  y -> Concatenation( x[ genpos[ y ] ] ) ) );
    fi;

    ngensets := Product( gensys[ 1 ], Length );

    # start finding presentations
    r := List( list, x -> rec(
             hits := 0,
             codes := [] ) );
    mhits := 0;
    rem := n;
    hasAutos := false;
    disting := [ ];

    repeat
      for i in [ 1 .. n ] do
        if IsBound( r[ i ] ) then
          repeat
            gens := List( gensys[ i ], Random );
            stmp := Size( Group( gens ) );
            if stmp <> size then
              misses[ i ] := 1;
            fi;
          until stmp = size;
          code := CodeGenerators( gens, spcgs[ i ] );
          found := false;
          j := 0;
          repeat
            j := j + 1;
            if IsBound( r[ j ] ) then
              ek := Length( r[ j ].codes );
              if ek > 0 then
                k := 0;
                repeat 
                  k := k + 1;
                  found := r[ j ].codes[ k ].code = code.code;
                until found or k = ek;
              fi;
            fi;
          until found or j = n; 
          if found then
            if i = j then
              r[ i ].hits := r[ i ].hits + 1;
              mhits := Minimum( List( Compacted( r ), x -> x.hits ) );
              if not IsBound( r[i].codes[k].gens ) then
                r[i].codes[k].gens := gens;
              elif hasAutos then
                perm := PermGensGensFEM( fams[ i ], spcgs[ i ], gens, 
                                      r[ i ].codes[ k ].gens );
                if not perm in r[ i ].autos then
                  r[ i ].autos := Group( Concatenation( [ perm ],
                    GeneratorsOfGroup( r[ i ].autos ) ) );
                  r[ i ].autsize := Size( r[ i ].autos );
                  Info( InfoRandIso, 4, " autsize: ", r[ i ].autsize );
                fi;
              fi;
            else
              k := Minimum( i, j );
              l := Maximum( i, j );
              r[ k ].hits := 0;
              mhits := 0;
              Append( r[k].codes, List( r[l].codes, x->rec(code:=x.code) ) );
              Unbind( r[ l ] );
              rem := rem - 1;
            fi;
          else
            Add( r[ i ].codes, rec( code := code.code, gens := gens ) );
          fi;
        fi;
      od;

      if mhits >= 5 and not hasAutos then
        for i in [ 1 .. n ] do
          if IsBound( r[ i ] ) then
            r[ i ].autos := Group( () );
            r[ i ].autsize := 1;
          fi;
        od;
        hasAutos := true;
        Info( InfoRandIso, 4, " ngensets: ", ngensets );
      fi;

      if hasAutos then
        for i in [ 1 .. n ] do
          if rem > 1 and IsBound( r[ i ] ) then
            if Length( r[ i ].codes ) * r[ i ].autsize > ngensets then
              Error( "fatal Error in RandomIsomorphismTestFEM" );
            fi;
            ident := true;
            for j in [ 1 .. n ] do
              if ident and i <> j and IsBound( r[ j ] ) and 
                 LcmInt( r[ i ].autsize, r[ j ].autsize ) *
                       ( Length( r[ i ].codes ) + Length( r[ j ].codes ) )
                   + misses[ i ] <= ngensets then
                ident := false;
              fi;
            od;
            if ident then
              Info( InfoRandIso, 2,
                    " RandomIsomorphismTestFEM identifies group" );
              AddSet( disting, i );
              Unbind( r[ i ] );
              list[ i ].isUnique := true;
              rem := rem - 1;
            fi;
          fi;
        od;
        Info( InfoRandIso, 4, " orbs ",
              List( Compacted( r ), x -> Length( x.codes ) ) );
      fi;
      Info( InfoRandIso, 4, " ", List( Compacted( r ), x -> x.hits ) );
    until rem = 1 or mhits > 50;

    if rem > 1 then
        Info( InfoRandIso, 1, " ", rem,
              " candidates not separated by RandomIsomorphismTestFEM"); 
    fi;

    return rec( 
       rem := list{ Filtered( [ 1 .. n ], x-> IsBound( r[ x ] ) ) },
       unique := list{ disting } ); 
end);

#############################################################################
##
#F ReducedByIsomorphismsFEM( list, Finfo )
##
InstallGlobalFunction( ReducedByIsomorphismsFEM, function( list, Finfo )

   local i, tlist;

   # the trivial cases of isomorphism searching
   if Length( list ) = 0 then
      return list;
   fi;
   if Length( list ) = 1 then
      list[1].isUnique := true;
      return list; 
   fi;

   Info( InfoRandIso, 2, "  reduce ", Length(list), " groups " );

   # split up in sublist
   list := SplitUpSublistsByFpFunc( list );
   if ForAll( list, IsRecord ) then 
      return list;
   fi;

   if not IsBound( Finfo.lmin ) then 
       AddRandomTestInfosFEM( Finfo );
   fi;

   # loop over all sublists
   i := 1;
   repeat 
      if IsRecord( list[ i ] ) then
         i := i + 1;
      elif Length( list[ i ] ) = 1 then
         list[ i ] := list[ i ][ 1 ];
         list[ i ].isUnique := true;
         i := i + 1;
      else
         Info( InfoRandIso, 2, " randiso on ", Length( list[ i ] ),
               " groups of size ", list[ i ][ 1 ].order, ", block ", i, "/",
               Length( list ) );
         list[ i ] := RandomIsomorphismTestFEM( list[ i ], Finfo );
         if IsBound( list[ i ].subl ) then
             Append( list, list[ i ].subl{[ 2 .. Length( list[ i ].subl )]});
             list[ i ] := list[ i ].subl[ 1 ];
         else
             Append( list, list[ i ].unique );
             list[ i ] := list[ i ].rem;
             if Length( list[ i ] ) = 1 then
                 list[ i ] := list[ i ][ 1 ];
                 list[ i ].isUnique := true;
             fi;
             i := i + 1;
         fi;
      fi;
   until i > Length( list );

   tlist := Filtered( list, IsList );
   Sort( tlist, function( x, y ) return Length(x) < Length(y); end );

   return Concatenation( Filtered( list, IsRecord ), tlist );
end);

#############################################################################
##
#F ReducedByIsomorphismsFEMAnother( list, frec, level )
##
## The function `ReducedByIsomorphismsFEM' always uses the first strategy
## for the elements of the frattinifactor choiced by `AddRandomTestInfosFEM'.
## If these (and `DistinguishGroups') have failed, this function can try
## alternative elements of the frattinifactor. The function is useful e.g.
## for some groups of size 1728.
BindGlobal( "ReducedByIsomorphismsFEMAnother", function( list, frec, level )

   local i, tlist, Finfo;

   Finfo := rec( F := PcGroupCodeRec( frec ) );
   AddRandomTestInfosFEM( Finfo, level );

   # loop over all sublists
   i := 1;
   repeat 
      if IsRecord( list[ i ] ) then
         i := i + 1;
      elif Length( list[ i ] ) = 1 then
         list[ i ] := list[ i ][ 1 ];
         list[ i ].isUnique := true;
         i := i + 1;
      else
         Info( InfoRandIso, 2, " another randiso on ", Length( list[ i ] ),
               " groups of size ", list[ i ][ 1 ].order, ", block ", i, "/",
               Length( list ) );
         list[ i ] := RandomIsomorphismTestFEM( list[ i ], Finfo );
         if IsBound( list[ i ].subl ) then
             Append( list, list[ i ].subl{[ 2 .. Length( list[ i ].subl )]});
             list[ i ] := list[ i ].subl[ 1 ];
         else
             Append( list, list[ i ].unique );
             list[ i ] := list[ i ].rem;
             if Length( list[ i ] ) = 1 then
                 list[ i ] := list[ i ][ 1 ];
                 list[ i ].isUnique := true;
             fi;
             i := i + 1;
         fi;
      fi;
   until i > Length( list );

   tlist := Filtered( list, IsList );
   Sort( tlist, function( x, y ) return Length(x) < Length(y); end );

   return Concatenation( Filtered( list, IsRecord ), tlist );
end );

[ Verzeichnis aufwärts0.54unsichere Verbindung  Übersetzung europäischer Sprachen durch Browser  ]