Quelle  grpnames.gi   Sprache: Shell

#############################################################################
##
##  This file is part of GAP, a system for computational discrete algebra.
##  This file's authors include Gábor Horváth, Stefan Kohl, Markus Püschel, Sebastian Egner.
##
##  Copyright of GAP belongs to its developers, whose names are too numerous
##  to list here. Please refer to the COPYRIGHT file for details.
##
##  SPDX-License-Identifier: GPL-2.0-or-later
##
##  This file contains a method for determining structure descriptions for
##  given finite groups and implementations of related functionality.
##
##  The purpose of this method is to give a human reader a rough impression
##  of the group structure -- it does neither determine the group up to
##  isomorphism (this would make the description for larger groups quite long
##  and difficult to read) nor is it usually the only ``sensible''
##  description for a given group.
##
##  The code has been translated, simplified and extended by Stefan Kohl
##  from GAP3 code written by Markus Püschel and Sebastian Egner.
##


#############################################################################
##
#M  IsTrivialNormalIntersectionInList( <L>, <U>, <V> ) . . . . generic method
##
InstallGlobalFunction( IsTrivialNormalIntersectionInList,

  function( MinNs, U, V )
    local N, g;

    for N in MinNs do
      g := First(GeneratorsOfGroup(N), g -> g<>One(N));
      if g <> fail and g in U and g in V then
        return false;
      fi;
    od;
    return true;
  end);

#############################################################################
##
#M  IsTrivialNormalIntersection( <G>, <U>, <V> ) . . . . . . . generic method
##

InstallMethod( IsTrivialNormalIntersection,
               "if minimal normal subgroups are computed", IsFamFamFam,
               [ IsGroup and HasMinimalNormalSubgroups, IsGroup, IsGroup ],

  function( G, U, V )
    local N, g;

    for N in MinimalNormalSubgroups(G) do
      g := First(GeneratorsOfGroup(N), g -> g<>One(N));
      if g <> fail and g in U and g in V then
        # found a nontrivial common element
        return false;
      fi;
    od;
    # if U and V intersect nontrivially, then their intersection must contain
    # a minimal normal subgroup, and therefore both U and V contains any of
    # its generators
    return true;
  end);

InstallMethod( IsTrivialNormalIntersection,
               "generic method", IsFamFamFam,
               [ IsGroup, IsGroup, IsGroup ],

  function( G, U, V )

    return IsTrivial(NormalIntersection(U, V));
  end);

#############################################################################
##
#M  UnionIfCanEasilySortElements( <L1>[, <L2>, ... ] ) . . . . generic method
##
InstallGlobalFunction( UnionIfCanEasilySortElements,

  function( arg )

    if ForAll(arg, CanEasilySortElements) then
      return Union(arg);
    else
      return Concatenation(arg);
    fi;
  end);

#############################################################################
##
#M  AddSetIfCanEasilySortElements( <list>[, <obj> ) . . . . . generic method
##
InstallGlobalFunction( AddSetIfCanEasilySortElements,

  function( list, obj )

    if CanEasilySortElements( list ) and IsSet( list ) then
      AddSet( list, obj );
    else
      Add( list, obj );
    fi;
  end);

#############################################################################
##
#M  NormalComplement( <G>, <N> ) . . . . . . . . . . . generic method
##
InstallMethod( NormalComplement,
               "generic method", IsIdenticalObj, [ IsGroup,  IsGroup ],

  function( G, N )

    # if <N> is trivial then the only complement is <G>
    if IsTrivial(N) then
      return G;

    # if <G> and <N> are equal then the only complement is trivial
    elif G = N  then
      return TrivialSubgroup(G);

    elif not (IsSubgroup(G, N) and IsNormal(G, N)) then
      Error("N must be a normal subgroup of G");

    else
      return NormalComplementNC(G, N);
    fi;
  end);

InstallMethod( NormalComplementNC,
               "generic method", IsIdenticalObj, [ IsGroup,  IsGroup ],

  function( G, N )

    local F,    # G/N
          DfF,  # Direct factors of F=G/N
          gF,   # element of F=G/N
          g,    # element of G corresponding to gF
          x,    # element of G
          i,    # running index
          l,    # list for storing stuff
          b,    # elements of abelian complement
          C,    # Center of G
          S,    # Subgroup of C
          r,    # RationalClass of C
          R,    # right coset
          gens, # generators of subgroup of C
          B,    # complement to N
          T,    # = [C_G(N), G] = 1 x B'
          Gf,   # = G/T = N x B/B'
          Nf,   # = NT/T
          Bf,   # abelian complement to Nf in Gf ( = B/B')
          nat,
          BfF;  # Direct factors of Bf

    # if <N> is trivial then the only complement is <G>
    if IsTrivial(N) then
      return G;

    # if <G> and <N> are equal then the only complement is trivial
    elif G = N  then
      return TrivialSubgroup(G);

    # if G/N is abelian
    elif HasAbelianFactorGroup(G, N) then
      nat:=NaturalHomomorphismByNormalSubgroupNC(G,N);
      #F := FactorGroupNC(G, N);
      F:=Image(nat,G);
      b := [];
      l := [];
      i:=0;
      for gF in IndependentGeneratorsOfAbelianGroup(F) do
        i := i+1;
        g := PreImagesRepresentative(nat, gF);
        R := RightCoset(N, g);
        # DirectFactorsOfGroup already computed Center and RationalClasses
        # when calling NormalComplement
        if HasCenter(G) and HasRationalClasses(Center(G)) then
          l := [];
          C := Center(G);
          for r in RationalClasses(C) do
            if Order(Representative(r)) = Order(gF) then
              for x in Set(r) do
                if x in R then
                  l := [x];
                  break;
                fi;
              od;
            fi;
          od;
          # Intersection(l, R) can take a long time
          l := First(l, ReturnTrue);
        # if N is big, then Center is hopefully small and fast to compute
        elif HasCenter(G) or Size(N) > Index(G, N) then
          C := Center(G);
          # it is enough to look for the Order(gF)-part of C
          gens := [];
          for x in IndependentGeneratorsOfAbelianGroup(C) do
            Add(gens, x^(Order(x)/GcdInt(Order(x), Order(gF))));
          od;
          S := SubgroupNC(C, gens);
          if Size(S) > Size(N) then
            # Intersection(S, R) can take a long time
            l := First(R, x -> Order(x) = Order(gF) and x in S);
          else
            # Intersection(C, R) can take a long time
            l := First(S, x -> Order(x) = Order(gF) and x in R);
          fi;
        # N is small, then looping through its elements might be more
        # efficient than computing the Center
        else
          l := First(R, x -> Order(x) = Order(gF)
                          and IsCentral(G, SubgroupNC(G, [x])));
        fi;
        if l <> fail then
          b[i] := l;
        else
          return fail;
        fi;
      od;
      B := SubgroupNC(G, b);
      return B;

    # if G/N is not abelian
    else
      T := CommutatorSubgroup(Centralizer(G, N), G);
      if not IsTrivial(T) and IsTrivialNormalIntersection(G, T, N) then
        #Gf := FactorGroupNC(G, T);
        #Nf := Image(NaturalHomomorphism(Gf), N);
        nat:=NaturalHomomorphismByNormalSubgroupNC(G, T);
        Gf:=Image(nat,G);
        Nf:=Image(nat,N);
        # not quite sure if this check is needed
        if HasAbelianFactorGroup(Gf, Nf) then
          Bf := NormalComplementNC(Gf, Nf);
          if Bf = fail then
            return fail;
          else
            B := PreImage(nat, Bf);
            return B;
          fi;
        else
          return fail;
        fi;
      else
        return fail;
      fi;
    fi;
  end);

#############################################################################
##
#M  DirectFactorsOfGroup( <G> ) . . . . . . . . . . . . . . .  generic method
##
InstallMethod(DirectFactorsOfGroup,
            "for direct products if normal subgroups are computed", true,
            [ IsGroup and HasDirectProductInfo and HasNormalSubgroups ], 0,

  function(G)
    local i, info, Ns, MinNs, H, Df, DfNs, DfMinNs, N, g, gs;

    Ns := NormalSubgroups(G);
    MinNs := MinimalNormalSubgroups(G);
    Df := [];
    info := DirectProductInfo(G).groups;
    for i in [1..Length(info)] do
      H := Image(Embedding(G,i),info[i]);
      DfMinNs := Filtered(MinNs, N ->IsSubset(H, N));
      if Length(DfMinNs) = 1 then
        # size of DfMinNs is an upper bound to the number of components of H
        Df := UnionIfCanEasilySortElements(Df, [H]);
      else
        DfNs := Filtered(Ns, N ->IsSubset(H, N));
        gs := [ ];
        for N in DfMinNs do
          g := First(GeneratorsOfGroup(N), g -> g<>One(N));
          if g <> fail then
            AddSetIfCanEasilySortElements(gs, g);
          fi;
        od;
        # normal subgroup containing all minimal subgroups cannot have complement in H
        DfNs := Filtered(DfNs, N -> not IsSubset(N, gs));
        Df := UnionIfCanEasilySortElements(Df,
                            DirectFactorsOfGroupFromList(H, DfNs, DfMinNs));
      fi;
    od;
    return Df;
  end);

InstallMethod(DirectFactorsOfGroup, "for direct products", true,
                      [ IsGroup and HasDirectProductInfo ], 0,

  function(G)
    local i, info, Ns;

    Ns := [];
    info := DirectProductInfo(G).groups;
    for i in [1..Length(info)] do
      Ns := UnionIfCanEasilySortElements(Ns,
                        DirectFactorsOfGroup(Image(Embedding(G,i),info[i])));
    od;
    return Ns;
  end);

InstallMethod(DirectFactorsOfGroup, "if normal subgroups are computed", true,
                      [ IsGroup and HasNormalSubgroups ], 0,

  function(G)
    local Ns, MinNs, GGd, g, N, gs;

    Ns := NormalSubgroups(G);
    MinNs := MinimalNormalSubgroups(G);

    if Length(MinNs)= 1 then
      # size of MinNs is an upper bound to the number of components
      return [ G ];
    fi;

    if IsSolvableGroup(G) then
      GGd := CommutatorFactorGroup(G);
      if IsCyclic(GGd) and IsPrimePowerInt(Size(GGd)) then
        # G is direct indecomposable, because has a unique maximal subgroup
        return [ G ];
      fi;
    else
      GGd := CommutatorFactorGroup(G);
      # if GGd is not cyclic of prime power size then there are at least two
      # maximal subgroups
      if (IsTrivial(GGd) or (IsCyclic(GGd) and IsPrimePowerInt(Size(GGd))))
        and Length(MaximalNormalSubgroups(G))= 1 then
        # size of MaximalNormalSubgroups is an upper bound to the number of
        # components
        return [ G ];
      fi;
    fi;

    gs := [ ];
    for N in MinNs do
      g := First(GeneratorsOfGroup(N), g -> g<>One(N));
      if g <> fail then
        AddSetIfCanEasilySortElements(gs, g);
      fi;
    od;
    # normal subgroup containing all minimal subgroups cannot have complement
    Ns := Filtered(Ns, N -> not IsSubset(N, gs));

    return DirectFactorsOfGroupFromList(G, Ns, MinNs);
  end);

InstallMethod(DirectFactorsOfGroup, "generic method", true,
                        [ IsGroup ], 0,
  function(G)

    local Gd,       # G'
          GGd,      # G/G'
          C,        # Center(G)
          D,        # Intersection(C, Gd)
          Ns,       # list of normal subgroups
          MinNs,    # list of minimal normal subgroups
          gs,       # list containing one generator for each MinNs
          g,        # group element
          N,        # (possible) component of G, containing g
          B;        # (possible) complement of G in N

    # for abelian groups return the canonical decomposition
    if IsTrivial(G) then
      return [G];
    elif IsAbelian(G) then
      Ns := [];
      for g in IndependentGeneratorsOfAbelianGroup(G) do
        Ns := UnionIfCanEasilySortElements(Ns, [SubgroupNC(G, [g])]);
      od;
      return Ns;
    fi;

    if not IsFinite(G) then TryNextMethod(); fi;

    # the KN method performs slower in practice, only called if forced
    if ValueOption("useKN") = true then
      return DirectFactorsOfGroupByKN(G);
    fi;

    # nilpotent groups are direct products of Sylow subgroups
    if IsNilpotentGroup(G) then
      if not IsPGroup(G) then
        Ns := [ ];
        for N in SylowSystem(G) do
          Ns := UnionIfCanEasilySortElements(Ns, DirectFactorsOfGroup(N));
        od;
        return Ns;
      elif IsCyclic(Center(G)) then
        # G is direct indecomposable, because has a unique minimal subgroup
        return [ G ];
      fi;
    # nonabelian p-groups cannot have a unique maximal subgroup
    elif IsSolvableGroup(G) then
      GGd := CommutatorFactorGroup(G);
      if IsCyclic(GGd) and IsPrimePowerInt(Size(GGd)) then
        # G is direct indecomposable, because has a unique maximal subgroup
        return [ G ];
      fi;
    fi;

    # look for abelian cyclic component from the center
    C := Center(G);
    # abelian cyclic components have trivial intersection with the commutator
    Gd := DerivedSubgroup(G);
    D := Intersection(C, Gd);
    for g in RationalClasses(C) do
      N := Subgroup(C, [Representative(g)]);
      if not IsTrivial(N) and IsTrivialNormalIntersection(C, D, N) then
        B := NormalComplementNC(G, N);
        # if B is a complement to N
        if B <> fail then
          return UnionIfCanEasilySortElements( DirectFactorsOfGroup(N),
                                                  DirectFactorsOfGroup(B));
        fi;
      fi;
    od;

    # all components are nonabelian
    if IsCyclic(Gd) and IsPrimePowerInt(Size(Gd)) then
      # if A and B are two nonabelian components, then
      # A' and B' must be nontrivial
      # this can only help for some metabelian groups
      return [ G ];
    fi;

    if not IsTrivial(C) and HasAbelianFactorGroup(G, C)
      and Length(DirectFactorsOfGroup(G/C)) < 4 then
      # if A and B are two nonabelian components,
      # where A/Center(A) and B/Center(B) are abelian, then
      # A/Center(A) and B/Center(B) must have at least two components each
      return [ G ];
    fi;

    # if everything else fails, compute all normal subgroups
    Ns := NormalSubgroups(G);
    if IsNilpotentGroup(G) then
        # minimal normal subgroups are central in nilpotent groups
        MinNs := MinimalNormalSubgroups(Center(G));
    else
      # MinimalNormalSubgroups seems to compute faster after NormalSubgroups
      MinNs := MinimalNormalSubgroups(G);
    fi;

    if Length(MinNs)= 1 then
      # size of MinNs is an upper bound to the number of components
      return [ G ];
    fi;

    if not IsSolvableGroup(G) then
      GGd := CommutatorFactorGroup(G);
      # if GGd is not cyclic of prime power size then there are at least two
      # maximal subgroups
      if (IsTrivial(GGd) or (IsCyclic(GGd) and IsPrimePowerInt(Size(GGd))))
        and Length(MaximalNormalSubgroups(G))= 1 then
        # size of MaximalNormalSubgroups is an upper bound to the number of
        # components
        return [ G ];
      fi;
    fi;

    gs := [ ];
    for N in MinNs do
      g := First(GeneratorsOfGroup(N), g -> g<>One(N));
      if g <> fail then
        AddSetIfCanEasilySortElements(gs, g);
      fi;
    od;
    # normal subgroup containing all minimal subgroups cannot have complement
    Ns := Filtered(Ns, N -> not IsSubset(N, gs));

    return DirectFactorsOfGroupFromList(G, Ns, MinNs);
  end);

InstallMethod(CharacteristicFactorsOfGroup, "generic method", true,
                        [ IsGroup ], 0,
function(G)
local Ns,MinNs,sel,a,sz,j,gs,g,N;

  Ns := ShallowCopy(CharacteristicSubgroups(G));
  SortBy(Ns,Size);
  MinNs:=[];
  sel:=[2..Length(Ns)-1];
  while Length(sel)>0 do
    a:=sel[1];
    sz:=Size(Ns[a]);
    RemoveSet(sel,sel[1]);
    Add(MinNs,Ns[a]);
    for j in ShallowCopy(sel) do
      if Size(Ns[j])>sz and Size(Ns[j]) mod sz=0 and IsSubset(Ns[j],Ns[a]) then
        RemoveSet(sel,j);
      fi;
    od;
  od;

  if Length(MinNs)= 1 then
    # size of MinNs is an upper bound to the number of components
    return [ G ];
  fi;

  gs := [ ];
  for N in MinNs do
    g := First(GeneratorsOfGroup(N), g -> g<>One(N));
    if g <> fail then
      AddSetIfCanEasilySortElements(gs, g);
    fi;
  od;
  # normal subgroup containing all minimal subgroups cannot have complement
  Ns := Filtered(Ns, N -> not IsSubset(N, gs));

  return DirectFactorsOfGroupFromList(G, Ns, MinNs);
end);

InstallGlobalFunction( DirectFactorsOfGroupFromList,

  function ( G, NList, MinList )

    local g, N, gs, Ns, MinNs, NNs, MinNNs, facts, sizes, i, j, s1, s2;

    if Length(MinList)=1 then
      # size of MinList is an upper bound to the number of components
      return [ G ];
    fi;

    Ns := ShallowCopy(NList);
    MinNs := ShallowCopy(MinList);
    gs := [ ];
    for N in MinNs do
      g := First(GeneratorsOfGroup(N), g -> g<>One(N));
      if g <> fail then
        AddSetIfCanEasilySortElements(gs, g);
      fi;
    od;
    # normal subgroup containing all minimal subgroups cannot have complement
    Ns := Filtered(Ns, N -> not IsSubset(N, gs));
    sizes := List(Ns,Size);
    SortParallel(sizes,Ns);
    for s1 in Difference(Set(sizes),[Size(G),1]) do
      i := PositionSet(sizes,s1);
      s2 := Size(G)/s1;
      if s1 <= s2 then
        repeat
          if s2 > s1 then
            j := PositionSet(sizes,s2);
            if j = fail then break; fi;
          else
            j := i + 1;
          fi;
          while j <= Size(sizes) and sizes[j] = s2 do
            if IsTrivialNormalIntersectionInList(MinList,Ns[i],Ns[j]) then
            # Ns[i] is the smallest direct factor, hence direct irreducible
            # we keep from Ns only the subgroups of Ns[j] having size min. s1
              NNs := Filtered(Ns{[i..j]}, N -> Size(N) >= s1
                              and s2 mod Size(N) = 0 and IsSubset(Ns[j], N));
              MinNNs := Filtered(MinNs, N -> s2 mod Size(N) = 0
                                                and IsSubset(Ns[j], N));
              return UnionIfCanEasilySortElements( [ Ns[i] ],
                          DirectFactorsOfGroupFromList(Ns[j], NNs, MinNNs));
            fi;
            j := j + 1;
          od;
          i := i + 1;
        until i>=Size(sizes) or sizes[i] <> s1;
      fi;
    od;
    return [ G ];
  end );

InstallGlobalFunction(DirectFactorsOfGroupByKN,

  function(G)

    local Ns,       # list of some direct components
          i,        # running index
          Gd,       # derived subgroup G'
          p,        # prime
          N,        # (possible) component of G
          B,        # complement of G in N
          K,        # normal subgroup
          prodK,    # product of normal subgroups
          Z1,       # contains a (unique) component with trivial center
          g,a,b,    # elements of G
          C,        # Center(G)
          D,        # Intersection(C, Gd)
          Cl,       # all conjugacy classes of G
          Clf,      # filtered list of conjugacy classes of G
          c1,c2,c3, # conjugacy class of G
          com,      # true if c1 and c2 commute, false otherwise
          prod,     # product of c1 and c2
          RedCl,    # reducible conjugacy classes of G
          IrrCl,    # irreducible conjugacy classes of G
          preedges, # pre-edges of the non-commuting graph
          edges,    # final edges of the non-commuting graph
          e,        # one edge of the non-commuting graph
          comp,     # components of the non-commuting graph
          DfZ1,     # nonabelian direct factors of Z1
          S1;       # index set corresponding to first component

    # for abelian groups return the canonical decomposition
    if IsTrivial(G) then
      return [G];
    elif IsAbelian(G) then
      Ns := [];
      for g in IndependentGeneratorsOfAbelianGroup(G) do
        Ns := UnionIfCanEasilySortElements(Ns, [SubgroupNC(G, [g])]);
      od;
      return Ns;
    fi;

    # look for abelian cyclic component from the center
    C := Center(G);
    # abelian cyclic components have trivial intersection with the commutator
    Gd := DerivedSubgroup(G);
    D := Intersection(C, Gd);
    for g in RationalClasses(C) do
      N := Subgroup(C, [Representative(g)]);
      if not IsTrivial(N) and IsTrivialNormalIntersection(C, D, N) then
        B := NormalComplementNC(G, N);
        # if B is a complement to N
        if B <> fail then
          return UnionIfCanEasilySortElements( DirectFactorsOfGroup(N),
                                                    DirectFactorsOfGroup(B));
        fi;
      fi;
    od;

    # all components are nonabelian
    # !!! this can (and should) be made more efficient later !!!
    # instead of conjugacy classes we should calculate by normal subgroups
    # generated by 1 element
    Cl := Set(ConjugacyClasses(G));
    RedCl := Set(Filtered(Cl, x -> Size(x) = 1));
    Clf := Difference(Cl, RedCl);
    preedges := [];
    for c1 in Clf do
      for c2 in Clf do
        com := true;
        prod := [];
        if c1 <> c2 then
          for a in c1 do
            for b in c2 do
              g := a*b;
              if g<>b*a then
                com := false;
                AddSetIfCanEasilySortElements(preedges, [c1, c2]);
                break;
              else
                AddSetIfCanEasilySortElements(prod, g);
              fi;
            od;
            if not com then
              break;
            fi;
          od;
          if com and Size(prod) = Size(c1)*Size(c2) then
            a := Representative(c1);
            b := Representative(c2);
            c3 := ConjugacyClass(G, a*b);
            if Size(c3)=Size(prod) then
              AddSetIfCanEasilySortElements(RedCl, c3);
            fi;
          fi;
        fi;
      od;
    od;
    IrrCl := Difference(Clf, RedCl);

    # need to remove edges corresponding to reducible classes
    edges := ShallowCopy(preedges);
    for e in preedges do
      if Intersection(e, RedCl) <> [] then
        RemoveSet(edges, e);
      fi;
    od;

    # now we create the graph components of the irreducible class graph
    # as an equivalence relation
    # this is not compatible with and not using the grape package
    comp := EquivalenceRelationPartition(
              EquivalenceRelationByPairsNC(IrrCl, edges));

    # replace classes in comp by their representatives
    comp := List(comp, x-> Set(x, Representative));

    # now replace every list by their generated normal subgroup
    Ns := List(comp, x-> NormalClosure(G, SubgroupNC(G, x)));
    Ns := UnionIfCanEasilySortElements(Ns);
    if IsTrivial(C) or Size(Ns)=1 then
      return Ns;
    fi;

    # look for the possible direct components from Ns
    # partition to two sets, consider both
    for S1 in IteratorOfCombinations(Ns) do
      if S1 <> [] and S1<>Ns then
        prodK := TrivialSubgroup(G);
        for K in S1 do
          prodK := ClosureGroup(prodK, K);
        od;
        Z1 := Centralizer(G, prodK);
        # Z1 is nonabelian <==> contains a nonabelian factor
        if not IsAbelian(Z1) then
          N := First(DirectFactorsOfGroupByKN(Z1), x-> not IsAbelian(x));
          # not sure if IsNormal(G, N) should be checked

          # this certainly can be done better,
          # because we basically know all possible normal subgroups
          # but it suffices for now
          B := NormalComplement(G, N);
          if B <> fail then
            # N is direct indecomposable by construction
            return UnionIfCanEasilySortElements([N],
                                                  DirectFactorsOfGroupByKN(B));
          fi;
        fi;
      fi;
    od;

    # if no direct component is found
    return [ G ];
  end);


#############################################################################
##
#M  SemidirectDecompositions( <G> ) . . . . . . . . . . . . .  generic method
##
InstallGlobalFunction(SemidirectDecompositionsOfFiniteGroup, function( arg )

  local  G, Ns, fullNs, method, NHs, i, N, H, NH; #, sizes;

  method := "all";
  if Length(arg) = 1 and IsGroup(arg[1]) then
    G := arg[1];
    fullNs := true;
  elif Length(arg) = 2 and IsGroup(arg[1]) and arg[2] in ["all",
                                                          "any", "str"] then
    G := arg[1];
    method := arg[2];
    fullNs := true;
  elif Length(arg) = 2 and IsGroup(arg[1]) and IsList(arg[2])
      and ForAll( Set(arg[2]), N ->
                              IsSubgroup(arg[1], N) and IsNormal(arg[1], N))
      then
    G := arg[1];
    Ns := ShallowCopy(arg[2]);
    fullNs := false;
  elif Length(arg) = 3 and IsGroup(arg[1]) and IsList(arg[2])
      and ForAll( Set(arg[2]), N ->
                              IsSubgroup(arg[1], N) and IsNormal(arg[1], N))
      and arg[3] in ["all", "any", "str"] then
    G := arg[1];
    Ns := ShallowCopy(arg[2]);
    method := arg[3];
    fullNs := false;
  else
    Error("usage: SemidirectDecompositionsOfFiniteGroup(<G> [, <Ns>] [, <mthd>])");
  fi;

  if HasSemidirectDecompositions(G) then
    NHs := [ ];
    for NH in SemidirectDecompositions(G) do
      N := NH[1];
      H := NH[2];
      if method in [ "any", "str" ] and not IsTrivial(N)
        and not IsTrivial(H) and
        ( not IsBound(Ns) or N in Ns ) then
        return [ N, H ];
      elif method="all" and
        ( not IsBound(Ns) or N in Ns ) then
        AddSetIfCanEasilySortElements(NHs, [ N, H ]);
      fi;
    od;
    if method in [ "any", "str" ] then
      return fail;
    elif method = "all" then
      return NHs;
    fi;
  fi;

  if method in [ "any", "str" ] then
    if HasSemidirectProductInfo(G) then
      N := Image(Embedding(G, 2));
      H := Image(Embedding(G, 1));
      if not IsTrivial(N) and not IsTrivial(H) and
        ( not IsBound(Ns) or N in Ns ) then
        return [ N, H ];
      fi;
    fi;
    N := NormalHallSubgroupsFromSylows(G, "any");
    if N <> fail then
      # by the Schur-Zassenhaus theorem there must exist a complement
      if method = "any" then
        H := ComplementClassesRepresentatives(G, N)[1];
        return [ N, H ];
      # only the isomorphism type of the complement is interesting
      elif method = "str" then
        Assert(1, Length( ComplementClassesRepresentatives(G, N) ) > 0);
        return [ N, G/N ];
      fi;
    fi;
  fi;

  # simple groups have no nontrivial normal subgroups
  if IsSimpleGroup(G) then
    if method in [ "any", "str" ] then
      return fail;
    elif method = "all" then
      return [ [TrivialSubgroup(G), G], [G, TrivialSubgroup(G)] ];
    fi;
  fi;

  if not IsBound(Ns) then
    Ns := ShallowCopy(NormalSubgroups(G));
  fi;
# does not seem to make things faster
#  if method in [ "any", "str" ] then
#    sizes := List(Ns, Size);
#    SortParallel(sizes, Ns);
#    Ns := Reversed(Ns);
#  fi;

  NHs := [ ];
  for N in Ns do
    if not IsSolvableGroup(N) and not HasSolvableFactorGroup(G, N) then
      # compute subgroup lattice, currently no other method for complement
      ConjugacyClassesSubgroups(G);;
    fi;
    H := ComplementClassesRepresentatives(G, N);
    if Length(H)>0 then
      if method in ["any", "str"] and not IsTrivial(N)
                                  and not IsTrivial(H[1]) then
        return [ N, H[1] ];
      else
        for i in [1..Length(H)] do
          AddSetIfCanEasilySortElements( NHs, [ N, H[i] ] );
        od;
      fi;
    fi;
  od;
  if method in [ "any", "str" ] then
    # no nontrivial decompositions exist
    if fullNs then
      SetSemidirectDecompositions(G,
                      [ [TrivialSubgroup(G), G], [G, TrivialSubgroup(G)] ]);
    fi;
    return fail;
  else
    if fullNs then
      SetSemidirectDecompositions(G, NHs);
    fi;
    return NHs;
  fi;
end);

InstallMethod( SemidirectDecompositions,
               "generic method", true, [ IsGroup and IsFinite ], 0,

  function( G )
    return SemidirectDecompositionsOfFiniteGroup(G);
  end );

RedispatchOnCondition( SemidirectDecompositions, true,
    [ IsGroup ],
    [ IsFinite ], 0);

#############################################################################
##
#M  DecompositionTypesOfGroup( <G> ) . . . . . . . . . . . . . generic method
##
InstallMethod( DecompositionTypesOfGroup,
               "generic method", true, [ IsGroup ], 0,

  function ( G )

    local  AG, a,  # abelian invariants; an invariant
           CS,     # conjugacy classes of non-(1-or-G) subgroups
           H,      # a subgroup (possibly normal)
           N,      # a normal subgroup
           T,      # an isom. type
           TH, tH, # isom. types for H, a type
           TN, tN, # isom. types for N, a type
           DTypes; # the decomposition types

    if not IsFinite(G) then TryNextMethod(); fi;

    DTypes := [ ];

    # abelian special case
    if IsAbelian(G) then
      AG := AbelianInvariants(G);
      if Length(AG) = 1 then DTypes := Set([AG[1]]); else
        T := ["x"];
        for a in AG do Add(T,a); od;
        DTypes := Set([T]);
      fi;
      return DTypes;
    fi;

    # brute force enumeration
    CS  := ConjugacyClassesSubgroups( G );
    CS  := CS{[2..Length(CS)-1]};
    for N in Filtered(List(Reversed(CS),Representative),
                      N -> IsNormal(G,N)) do
      for H in List(CS, Representative) do # Lemma1 (`SemidirectFactors...')
        if    Size(H)*Size(N) = Size(G)
          and IsTrivial(NormalIntersection(N,H))
        then
          # recursion (exponentially) on (semi-)factors
          TH := DecompositionTypesOfGroup(H);
          TN := DecompositionTypesOfGroup(N);
          if IsNormal(G,H)
          then
            # non-trivial G = H x N
            for tH in TH do
              for tN in TN do
                T := [ ];
                if   IsList(tH) and tH[1] = "x"
                then Append(T,tH{[2..Length(tH)]});
                else Add(T,tH); fi;
                if   IsList(tN) and tN[1] = "x"
                then Append(T,tN{[2..Length(tN)]});
                else Add(T,tN); fi;
                Sort(T);
                AddSet(DTypes,Concatenation(["x"],T));
              od;
            od;
          else
            # non-direct, non-trivial G = H semidirect N
            for tH in TH do
              for tN in TN do
                AddSet(DTypes,[":",tH,tN]);
              od;
            od;
          fi;
        fi;
      od;
    od;

    # default: a non-split extension
    if Length(DTypes) = 0 then DTypes := Set([["non-split",Size(G)]]); fi;

    return DTypes;
  end );

#############################################################################
##
#M  IsDihedralGroup( <G> ) . . . . . . . . . . . . . . . . . . generic method
##

BindGlobal( "DoComputeDihedralGenerators", function(G)
    local  Zn, G1, T, n, t, s, i;

    if Size(G) mod 2 <> 0 then return fail; fi;
    n := Size(G)/2;

    # find a normal subgroup of G of type Zn
    if n mod 2 <> 0 then
      # G = < s, t | s^n = t^2 = 1, s^t = s^-1 >
      # ==> Comm(s, t) = s^-1 t s t = s^-2 ==> G' = < s^2 > = < s >
      Zn := DerivedSubgroup(G);
      if not ( IsCyclic(Zn) and Size(Zn) = n ) then return fail; fi;
    else # n mod 2 = 0
      # G = < s, t | s^n = t^2 = 1, s^t = s^-1 >
      # ==> Comm(s, t) = s^-1 t s t = s^-2 ==> G' = < s^2 >
      G1 := DerivedSubgroup(G);
      if not ( IsCyclic(G1) and Size(G1) = n/2 ) then return fail; fi;
      # G/G1 = {1*G1, t*G1, s*G1, t*s*G1}
      T := RightTransversal(G,G1);
      i := 1;
      repeat
        Zn := ClosureGroup(G1,T[i]);
        i  := i + 1;
      until i > 4 or ( IsCyclic(Zn) and Size(Zn) = n );
      if not ( IsCyclic(Zn) and Size(Zn) = n ) then return fail; fi;
    fi; # now Zn is normal in G and Zn = < s | s^n = 1 >

    # choose t in G\Zn and check dihedral structure
    repeat t := Random(G); until not t in Zn;
    if not (Order(t) = 2 and ForAll(GeneratorsOfGroup(Zn),s->t*s*t*s=s^0))
    then return fail; fi;

    # choose generator s of Zn
    repeat s := Random(Zn); until Order(s) = n;
    return [t,s];
end );

InstallMethod( IsDihedralGroup,
               "for a group",
               true,
               [ IsGroup and IsFinite ], 0,
function(G)
    local gens;

    gens := DoComputeDihedralGenerators(G);
    if gens = fail then
        return false;
    else
        SetDihedralGenerators(G, gens);
    fi;
    return true;
end);

InstallMethod( DihedralGenerators,
               "for a group",
               [ IsGroup and IsFinite ],
function(G)
    local gens;

    gens := DoComputeDihedralGenerators(G);
    SetIsDihedralGroup(G, gens <> fail);
    if gens = fail then
        ErrorNoReturn("G is not a dihedral group");
    fi;
    return gens;
end);

#############################################################################
##
#M  IsDicyclicGroup( <G> ) . . . . . . . . . . . . . . . . . . generic method
#M  IsGeneralizedQuaternionGroup( <G> )  . . . . . . . . . . . generic method
##
BindGlobal( "DoComputeDicyclicGenerators", function(G)
    local  N,    # size of G
           n,    # N/2
           a,    # N/4
           G1,   # derived subgroup of G
           T,    # transversal of G/G1
           i,    # counter
           Zn,   # cyclic normal subgroup of index 2 in G
           t, s, # canonical generators of the dicyclic group
           gens;

    N := Size(G);
    if N mod 4 <> 0 then return fail; fi;
    n := N/2;
    a := n/2;

    # G = <t, s | s^(2a) = 1, t^2 = s^a, s^t = s^-1>
    # ==> Comm(s, t) = s^-1 t s t = s^-2 ==> G' = < s^2 >
    G1 := DerivedSubgroup(G);
    if not ( IsCyclic(G1) and Size(G1) = a ) then return fail; fi;

    # find a normal subgroup of G of type Zn
    # G/G1 = {1*G1, t*G1, s*G1, t*s*G1}
    T := RightTransversal(G, G1);
    i := 1;
    repeat
      Zn := ClosureGroup(G1,T[i]);
      i  := i + 1;
    until i > 4 or ( IsCyclic(Zn) and Size(Zn) = n );
    if not ( IsCyclic(Zn) and Size(Zn) = n ) then return fail; fi;

    # now Zn is normal in G and Zn = < s | s^n = 1 >
    # choose t in G\Zn and check quaternion structure
    repeat t := Random(G); until not t in Zn;
    if not (Order(t) = 4 and ForAll(GeneratorsOfGroup(Zn), s->s^t*s = s^0))
    then return fail; fi;

    # choose generator s of Zn
    repeat s := Random(Zn); until Order(s) = n;
    gens:= [ t, s ];
    SetDicyclicGenerators( G, gens );
    return gens;
end );

BindGlobal( "DoComputeGeneralisedQuaternionGenerators",
    function( G )
    local N, gens;

    N:= Size( G );
    if not ( IsEvenInt( N ) and IsPrimePowerInt( N ) and N >= 8 ) then
      return fail;
    elif HasDicyclicGenerators( G ) then
      return DicyclicGenerators( G );
    fi;
    gens:= DoComputeDicyclicGenerators( G );
    if gens <> fail then
      SetGeneralisedQuaternionGenerators( G, gens );
    fi;
    return gens;
    end );

InstallMethod( IsDicyclicGroup,
    "for a finite group",
    [ IsGroup and IsFinite ],
    G -> DoComputeDicyclicGenerators( G ) <> fail );

InstallMethod( IsGeneralisedQuaternionGroup,
    "for a finite group",
    [ IsGroup and IsFinite ],
    G -> DoComputeGeneralisedQuaternionGenerators( G ) <> fail );

InstallMethod( DicyclicGenerators,
    "for a finite group",
    [ IsGroup and IsFinite ],
    function(G)
    local gens;

    gens:= DoComputeDicyclicGenerators(G);
    SetIsDicyclicGroup( G, gens <> fail );
    if gens = fail then
      ErrorNoReturn( "G is not a dicyclic group");
    fi;
    return gens;
    end);

InstallMethod( GeneralisedQuaternionGenerators,
    "for a finite group",
    [ IsGroup and IsFinite ],
function(G)
    local gens;

    gens := DoComputeGeneralisedQuaternionGenerators(G);
    SetIsGeneralisedQuaternionGroup(G, gens <> fail);
    if gens = fail then
        ErrorNoReturn("G is not a generalised quaternion group");
    fi;
    return gens;
end);


#############################################################################
##
#M  IsQuasiDihedralGroup( <G> ) . . . . . . . . . . . . . . .  generic method
##
InstallMethod( IsQuasiDihedralGroup,
               "generic method", true, [ IsGroup ], 0,

  function ( G )

    local  N,    # size of G
           k,    # ld(N)
           n,    # N/2
           G1,   # derived subgroup of G
           Zn,   # cyclic normal subgroup of index 2 in G
           T,    # transversal of G/G1
           t, s, # canonical generators of the quasidihedral group
           i;    # counter

    if not IsFinite(G) then TryNextMethod(); fi;

    N := Size(G);
    k := LogInt(N, 2);
    if not( 2^k = N and k >= 4 ) then return false; fi;
    n := N/2;

    # G = <t, s | s^(2^n) = t^2 = 1, s^t = s^(-1 + 2^(n-1))>.
    # ==> Comm(s, t) = s^-1 t s t = s^(-2+2^(n-1))
    # ==> G' = < s^(-2+2^(n-1)) >, |G'| = n/2.
    G1 := DerivedSubgroup(G);
    if not ( IsCyclic(G1) and Size(G1) = n/2 ) then return false; fi;

    # find a normal subgroup of G of type Zn
    # G/G1 = {1*G1, t*G1, s*G1, t*s*G1}
    T := RightTransversal(G, G1);
    i := 1;
    repeat
      Zn := ClosureGroup(G1,T[i]);
      i  := i + 1;
    until i > 4 or ( IsCyclic(Zn) and Size(Zn) = n );
    if not ( IsCyclic(Zn) and Size(Zn) = n ) then return false; fi;

    # now Zn is normal in G and Zn = < s | s^n = 1 >
    # now remain only the possibilities for the structure:
    #   dihedral, quaternion, quasidihedral
    repeat t := Random(G); until not t in Zn;

    # detect cases: dihedral, quaternion
    if   ForAll(GeneratorsOfGroup(Zn), s -> s^t*s = s^0)
    then return false; fi;

    # choose t in Zn of order 2
    repeat
      t := Random(G);
    until not( t in Zn and Order(t) = 2 ); # prob = 1/4

    # choose generator s of Zn
    repeat s := Random(Zn); until Order(s) = n;

    SetQuasiDihedralGenerators(G,[t,s]);
    return true;
  end );

#############################################################################
##
#M  IsAlternatingGroup( <G> ) . . . . . . . . . . . . . . . .  generic method
##
##  This method additionally sets the attribute `AlternatingDegree' in case
##  <G> is isomorphic to a natural alternating group.
##
InstallMethod( IsAlternatingGroup,
               "generic method", true, [ IsGroup ], 0,

  function ( G )

    local  n, ids, info;

    if not IsFinite(G) then TryNextMethod(); fi;

    if IsNaturalAlternatingGroup(G) then return true;fi;
    if Size(G) < 60 then
      if Size(G) = 1 then
        SetAlternatingDegree(G,0); return true;
      elif Size(G) = 3 then
        SetAlternatingDegree(G,3); return true;
      elif Size(G) = 12 and IdGroup(G) = [ 12, 3 ] then
        SetAlternatingDegree(G,4); return true;
      else return false; fi;
    fi;

    if not IsSimpleGroup(G) then return false; fi;

    info := IsomorphismTypeInfoFiniteSimpleGroup(G);
    if   info.series = "A"
    then SetAlternatingDegree(G,info.parameter); return true;
    else return false; fi;
  end );

#############################################################################
##
#M  AlternatingDegree( <G> ) generic method, dispatch to `IsAlternatingGroup'
##
InstallMethod( AlternatingDegree,
               "generic method, dispatch to `IsAlternatingGroup'",
               true, [ IsGroup ], 0,

  function ( G )
    if not IsFinite(G) then TryNextMethod(); fi;
    if IsNaturalAlternatingGroup(G) then return DegreeAction(G); fi;
    if not IsAlternatingGroup(G) then return fail; fi;
    if HasAlternatingDegree(G) then return AlternatingDegree(G); fi;

    if Size(G) = 1 then return 0;
    elif Size(G) = 3 then return 3;
    elif Size(G) = 12 then return 4;
    else return IsomorphismTypeInfoFiniteSimpleGroup(G).parameter;
    fi;
  end );

#############################################################################
##
#M  IsNaturalAlternatingGroup( <G> ) . . . . . . .  for non-permutation group
##
InstallOtherMethod( IsNaturalAlternatingGroup, "for non-permutation group",
                    true, [ IsGroup ], 0,

  function ( G )
    if not IsFinite(G) then TryNextMethod(); fi;
    if not IsPermGroup(G) then return false; else TryNextMethod(); fi;
  end );

#############################################################################
##
#M  IsSymmetricGroup( <G> ) . . . . . . . . . . . . . . . . .  generic method
##
##  This method additionally sets the attribute `SymmetricDegree' in case
##  <G> is isomorphic to a natural symmetric group.
##
InstallMethod( IsSymmetricGroup,
               "generic method", true, [ IsGroup ], 0,

  function ( G )

    local  G1;

    if IsNaturalSymmetricGroup(G) then return true;fi;
    if not IsFinite(G) then TryNextMethod(); fi;

    # special treatment of small cases
    if Size(G)<=2 then SetSymmetricDegree(G,Size(G)); return true;
    elif Size(G)=6 and not IsAbelian(G) then
      SetSymmetricDegree(G,3);
      return true;
    fi;

    G1 := DerivedSubgroup(G);
    if   not (IsAlternatingGroup(G1) and Index(G,G1) = 2)
      # this requires deg>=4
      or not IsTrivial(Centralizer(G,G1))
      or Size(G) = 720 and IdGroup(G) <> [ 720, 763 ]
    then return false; fi;
    SetSymmetricDegree(G,AlternatingDegree(G1));
    return true;
  end );

#############################################################################
##
#M  IsNaturalSymmetricGroup( <G> ) . . . . . . . .  for non-permutation group
##
InstallOtherMethod( IsNaturalSymmetricGroup, "for non-permutation group",
                    true, [ IsGroup ], 0,

  function ( G )
    if not IsFinite(G) then TryNextMethod(); fi;
    if not IsPermGroup(G) then return false; else TryNextMethod(); fi;
  end );

#############################################################################
##
#M  SymmetricDegree( <G> ) . . generic method, dispatch to `IsSymmetricGroup'
##
InstallMethod( SymmetricDegree,
               "generic method, dispatch to `IsSymmetricGroup'",
               true, [ IsGroup ], 0,

  function ( G )
    if not IsFinite(G) then TryNextMethod(); fi;
    if IsNaturalSymmetricGroup(G) then return DegreeAction(G); fi;
    if not IsSymmetricGroup(G) then return fail; fi;
    # calling IsSymmetricGroup may have computed the SymmetricDegree##  Copyright of GAP belongs to its developers, whose names are too numerous
##  The purpose of this method is to give a human reader a rough impression

    # special treatment of small cases
    java.lang.StringIndexOutOfBoundsException: Range [0, 6) out of bounds for length 2
      return Size(G);
    elifSizeG=6 then
      #############################################################################
    fi;
###
  end );

#############################################################################
##
#F  SizeGL(  <n>, <q> )
##
InstallGlobalFunction( SizeGL,

  function ( n, q )

    local N, qn, k;

    N  := 1;
    qn := q^n;
    for k in [0..n-1] do
      N := N * (qn - q^k);
    od;
Njava.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 13
  end );

#############################################################################
##
#F  SizeSL(  <n>, <q> )
##
InstallGlobalFunction( SizeSL,

  function ( n, q )

    local N,  kjava.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19

    N  := 1;
    qn := q^n;
    for k in [0..n-1] do
      N := N * (qn - q^k);
#############################################################################
    return N/(q - 1);
  end );

#############################################################################
##
#F  SizePSL(  <n>, <q> )
##
InstallGlobalFunction##

  function ( n, q )

    ##

    N: 1;
    qn : q^n;
    for k 
      N := N * (qn - q^k);
    od;
    return list, bj)java.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 23
  end"generic method", IsIdenticalObj, [ IsGroup,  IsGroup ],

#############################################################################
##
#F  LinearGroupParameters(  <N>  )
##
InstallGlobalFunction( LinearGroupParameters,

  function ( N )

    local  
           npeSL      # list of possible [n, p, e] for a SL
           npePSL,     # list of possible [n, p, e] for a PSL
           n, p, e,    # N = Size(GL(n, p^e))
           pe, p2, ep # p^ep is maximal prime power divisor of N
           e2         # a divisor of ep
           x, r,   end);

    if not IsPosInt(N) then Error("<N> must be positive integer"); fi;

    # Formeln:
    # |GL(n, q)|  = Product(q^n - q^k : k in [0..n-1])
    # |SL(n, q)|  = |GL(n, q)| / (q - 1)
 F,    # G/N
    #   mit q = p^e f"ur p prim, e >= 1, n >= 1.

    # Betrachte N = |GL(n,q)|. Dann gilt f"ur n >= 2
    #   (1) nu_p(N) = e * Binomial(n,2) und
    #   (2) (q - 1)^n teilt N.
    npeGL :  ] npeSL: [ ];npePSL:= [ ;
    if N = 1 then
      return rec( npeGL := npeGL, npeSL := npeSL, npePSL := npePSL );
    fi;
    for           ,# Subgroup of C
      p  := pe[ ,    
      ep : pe[2]

     # find e, n such that (1) e*Binomial(n,2) = ep
Nf,

          nat,
        # <==> 8 ep/e + 1 = (2 n - 1)^2
        x := 8(N) then
        r := RootIntx,);
        if r^2 = x then
      return TrivialSubgroup();

          # decide it
          G := SizeGL(n, p^elif  )
                #F := FactorGroupNC(G, N);
           N=G/^e-1)then(peSL n,p,e);fi;
ifN=G(pe -1)GcdInt(^e-1,n)) then
            Add(npePSL, [n, p, e]);
          fi
        fi;
      od;
    od;
    returnC : Center(G);
  end );

#############################################################################
##
#M  IsPSL( <G> )
##
InstallMethod( IsPSL,
"generic method for finite ",true,  IsGroup , 0,

  function (  break

    local   fi;

    if           # Intersection(l, R) can take a long time

    if Size(G)>12 and not elif HasCenter(G) or SizeN)>Index( N)
      return false;
    fi;

    # check if G has appropriate size
    npes :=             Add(gensx^Order()GcdInt(Order(gF)));
    if Length(npes) = Size) then

    # more than one npe-triple should only#Intersection(C, R) can take a long time
# occurin  cases || in [60, 168, 20160]
    ifLength(npes)>1 and not( Size()  [60, 168, 20160 )
    then Error("algebraic panic! probably npe does not# efficient than computing the Center

    # set the parameters
    npe : npes[1];

    # catch the cases:
    #   PSL(2, 2) ~= S3, PSL(2, 3) ~= A4,
    # in which the PSL is not simple

    # PSL(2, 2)
    if npes[1] = [2, 2, 1] then
ifIsAbelianG)thenreturnfalse java.lang.StringIndexOutOfBoundsException: Index 44 out of bounds for length 44
      nat=G );

    
    elif npes[1# not quite sure if this check is needed
      if Size(DerivedSubgroup()< 4 then return false;fi;
      SetParametersOfGroupViewedAsPSL(,) return true;

   # PSL(3, 4) / PSL(4, 2)
elifnpes= [ 4 2,1]  , 2    
         IdGroup(G,) =[,]thennpe = 1]java.lang.StringIndexOutOfBoundsException: Index 70 out of bounds for length 70
      elifIdGroup(ylowSubgroup(,2)) =[,242 then npe =npes[]; fijava.lang.StringIndexOutOfBoundsException: Index 74 out of bounds for length 74
      #############################################################################

    # other cases
    else
      if not IsSimpleGroup(G) then return false; fi;
      SetParametersOfGroupViewedAsPSL(G,npe); return true;
    fi;
  end );

#############################################################################
##
#M  PSLDegree( <G> ) . . . . . . . . . . . . generic method for finite groups
##
InstallMethod( PSLDegree,
               "generic method for finite groups", true, [[IsGroup and HasDirectProductInfo and HasNormalSubgroups ], 0,

   function (G )
    if not IsFinite(G) then TryNextMethod(); fijava.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
     not IsPSL( then return fail; fi;
    return ParametersOfGroupViewedAsPSL(G)[1];
  end );

#############################################################################
##
#M  PSLUnderlyingField( <G> ) . . . . . . .  generic method for finite groups
##
InstallMethod( PSLUnderlyingField,
              generic method for finite groups", true,  IsGroup

  function ( G )
    ifnot (G)thenTryNextMethod(); fi;
    ifnot IsPSL(G then return fail ;
    return GF(ParametersOfGroupViewedAsPSL(G)[2]g         g :(GeneratorsOfGroup(),g- g<>One()java.lang.StringIndexOutOfBoundsException: Index 59 out of bounds for length 59
  end );

#############################################################################
##
#M  IsSL( <G> ) . . . . . . . . . . . . . .  generic method for finite groups
##
InstallMethod        Df : UnionIfCanEasilySortElements(Df,
               "generic                             DirectFactorsOfGroupFromList(H, DfNs, DfMinNs));

  functionjava.lang.StringIndexOutOfBoundsException: Index 7 out of bounds for length 7

local  ,#
            # centre of G

=java.lang.StringIndexOutOfBoundsException: Range [43, 40) out of bounds for length 44

    # check if G has appropriate size
    npes
    ifLength()=0then return false; fi;

    # more than one npe-triple should never occur
    if Length(npes) > 1 then
      Error("algebraic 
    fi;
    npes : if(=1 then

    
    #   SL(2, 2) ~= S3, SL(2, 3)
#     FactorGroupPSL is simple

    # SL(2, 2)
      ;
      if       # if GGd
      if (IsTrivial(GGd) or)java.lang.StringIndexOutOfBoundsException: Range [63, 62) out of bounds for length 75

    # SL(2, 3)  GeneratorsOfGroupN)  >g>One);
    elif  [, 3, ] 
      (G) > java.lang.StringIndexOutOfBoundsException: Range [44, 43) out of bounds for length 61
      SetParametersOfGroupViewedAsSL(G,npes); java.lang.StringIndexOutOfBoundsException: Index 52 out of bounds for length 49

    # other cases, in which the contained PSL is simple
    else

      # calculate the centre C of G, which should have the
      # size gcd(n, p^e - 1), and if so, check if G/C (which
      # should be the corresponding PSL) is simplejava.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 26
      C          ,#
      (C > Gcd(npes[1,npes[2]npes[3] - 1)
        or not IsSimpleGroupB# (possible) complement of G in N
        or Size(G)/2 in List(java.lang.StringIndexOutOfBoundsException: Range [69, 42) out of bounds for length 69
then return false;fi
java.lang.StringIndexOutOfBoundsException: Index 70 out of bounds for length 65
     then false;fi;
     SetParametersOfGroupViewedAsSL(G,npes); return true;
    fi;
  );

#############################################################################
##
#M  SLDegree( <G> ) . . . . . . . . . . . .  generic method for finite groups
##
hod(SLDegree,
               "generic method for finite java.lang.StringIndexOutOfBoundsException: Range [8, 48) out of bounds for length 11

java.lang.StringIndexOutOfBoundsException: Range [11, 10) out of bounds for length 16
       java.lang.StringIndexOutOfBoundsException: Range [18, 17) out of bounds for length 58
    if G then   ;
    java.lang.StringIndexOutOfBoundsException: Range [6, 5) out of bounds for length 9
    # abelian cyclic components have trivial intersection with the commutator
ViewedAsSL()1;
  end );

#############################################################################
##
#M  SLUnderlyingField( <G> ) . . . . . . . . generic method for finite groups
##
InstallMethod( SLUnderlyingField,
               "generic method for fi

  function(G)
    if not IsFinite(G) then TryNextMethod(); fi;
    if not IsSL      # A' and B' must be nontrivial
    if   HasIsNaturalSL(G) and java.lang.StringIndexOutOfBoundsException: Index 34 out of bounds for length 19
    then return FieldOfMatrixGroup(G); fi;
    return GF(ParametersOfGroupViewedAsSL(G)[2]^ParametersOfGroupViewedAsSL(G)[3]);
java.lang.StringIndexOutOfBoundsException: Index 47 out of bounds for length 8

#############################################################################
##
#M  IsGL( <G> )
##
InstallMethod# if everything else fails, compute all normal subgroups
               "generic method for finite groups", true, [ IsGroup ], 0,

  function ( G )

    local  npes,  # list of possible GL-parameters
            subgroupofG
java.lang.StringIndexOutOfBoundsException: Index 76 out of bounds for length 32

    if not    ifLength(MinNs)=1 then

    if not IsSolvableGroup(G) 
    npes (Size(G))npeGL;
    if Length(npes) = 0 then return false; fi;

    # more than one npe-triple should never occur
    if (npes) > 1  then
      Error("algebraic panic! this should not upperbound to the number of
    ;
    npes := npes[1];

    # catch the cases:
    #   GL(2, 2) ~= S3, GL(2, 3)
    # in which the contained group PSL is not simple

    # GL(2, 2)
    if npes = [2, 2, 1] then
      (G)    fi;
      SetParametersOfGroupViewedAsGL(G,npes); return true;

    # GL(2, 3)
    elifnpes  [, 3,,1] then
      endjava.lang.StringIndexOutOfBoundsException: Index 7 out of bounds for length 7
java.lang.StringIndexOutOfBoundsException: Range [38, 36) out of bounds for length 58

    # other cases, in which contained PSL is simple
    java.lang.StringIndexOutOfBoundsException: Range [4, 1) out of bounds for length 20

      # calculate the derived subgroup which should be the
      # corresponding SL of index p^e - 1
      G1od
      IndexG )< [2^npes3] 1 thenfalse;fijava.lang.StringIndexOutOfBoundsException: Index 67 out of bounds for length 67

      # calculate the centre C1 of G1, which should have theGeneratorsOfGroupN) g  g<>();
      # size gcd(n, p^e - 1), and if so, check if G1/C1
      # (which should be the corresponding PSL) is simple
      C1 := Centre(G1);
      ifNs = Ns  >  java.lang.StringIndexOutOfBoundsException: Range [39, 38) out of bounds for length 47
        notIsSimpleGroupG1/C1)
      then java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
      if   java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 0
      then returnfalse;fi;
      etParametersOfGroupViewedAsGL,pes); true
    fi;
  end );

#############################################################################
##
#M  GLDegree( <G> ) . . . . . . . . . . . .  generic method for finite groups
##
InstallMethod 
               "generic method forfinite groups", true, [ IsGroup ], 0,

  java.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9
    if not (, N->not N ))java.lang.StringIndexOutOfBoundsException: Index 49 out of bounds for length 49
      IsGL then return fail;fijava.lang.StringIndexOutOfBoundsException: Index 40 out of bounds for length 40
    if   HasIsNaturalGL(G) and IsNaturalGL(G)
    then return DimensionOfMatrixGroup(G); fi;
      i : PositionSet(sizes,s1);
  end );

#############################################################################
##
#M  GLUnderlyingField( <G> ) . . . . . . . . generic method for finite groups
##
InstallMethod( GLUnderlyingField,
               "generic method for finite groups", true, [ IsGroup ], 0,

  function          while  =Size) and [j =do
    if not IsFinite(G) then TryNextMethod(); fi;
    if not IsGL(G) then return fail; fi;
    if   HasIsNaturalGL(G) and IsNaturalGL(G)
    then return FieldOfMatrixGroup(G); fi;
    GF(()2^(G)[];
  end );

#############################################################################
##
#M  StructureDescription( <G> ) . . . . . . . . . for abelian or finite group
##
BindGlobal( "SD_insertsep", # function to join parts of name
(strs, sep, brack)

      local  short,s ijava.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25

      short :=    ;

      if strs = [] then return ""; fi;
      strs :
      if java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
        for i in [1..Length(       
ifIntersectionstrs[i],rack) > ""
          then strs[i] := Concatenation("K,        
        od;
      fi;
      s := strs[1];
          D,#
        s,# filtered list of conjugacy classes of G
      od;
      if short then RemoveCharactersRedCl    # reducible conjugacy classes of G
      preed,# pre-edges of the non-commuting graph
java.lang.StringIndexOutOfBoundsException: Index 10 out of bounds for length 9

java.lang.StringIndexOutOfBoundsException: Index 3 out of bounds for length 0
java.lang.StringIndexOutOfBoundsException: Index 18 out of bounds for length 18
       =0or  =infinitythen
        return "Z";
      fi;
      return Concatenation("C",String(n));
    end);

BindGlobal( "java.lang.StringIndexOutOfBoundsException: Index 27 out of bounds for length 19
    function  cycsizes

        short, g, d, k, j, n;

      short := ValueOption("short") = true;
      if short then return ;fijava.lang.StringIndexOutOfBoundsException: Index 40 out of bounds for length 40
      RemoveCharacters(name," ");
        cycsizes : (cycsizes;
        for n in cycsizes do
          d =n1]  : [2;
          fijava.lang.StringIndexOutOfBoundsException: Index 11 out of bounds for length 11
          if d =#!!this can(nd should be more later !!
            d     
          elseRedCl := Filtered(Cl, x - (x)  1));
            d= ]java.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19
          java.lang.StringIndexOutOfBoundsException: Index 13 out of bounds for length 13
          if k > 1 then
            for j in Reversed(g:*;
              name := ReplacedString(name,SD_insertsep                com := alse;
                        (j)));
            od;
          fiAddSetIfCanEasilySortElements(rod g)java.lang.StringIndexOutOfBoundsException: Index 55 out of bounds for length 55
        od;
      RemoveCharacters(name,"C");
              fi;
    );

BindGlobal( "java.lang.StringIndexOutOfBoundsException: Index 48 out of bounds for length 36

  function (G 

    local  cycsizes;     # sizes of cyclic factors of G

    
    if IsTrivial(G) then return       odjava.lang.StringIndexOutOfBoundsException: Index 9 out of bounds for length 9

         =ShallowCopy();
    cycsizes := AbelianInvariants(G);
    cycsizes = ReversedElementaryDivisorsMat(DiagonalMat(cycsizes)));
    cycsizes := Filtered(cycsizes,n->n<>1);
    od;
                                        " ,"",)
  end );

              EquivalenceRelationByPairsNC(IrrCl )java.lang.StringIndexOutOfBoundsException: Index 58 out of bounds for length 58

  function ( G )

        Ns: comp- (G G x))java.lang.StringIndexOutOfBoundsException: Index 61 out of bounds for length 61
           series,       # series of simple groups
           parameter;    # parameters of G in series

    # special case abelian group
    if IsAbelian(ifS1 <[] and andS1<Ns 

    # special case alternating group
sAlternatingGroup(G)
    then return Concatenation("A",String(AlternatingDegree(G))); fi;

    # special case PSLN : ((Z1), x> not IsAbelianx));
    if IsPSL()then
       ("PSL(",String((),,,
                                  String(Size(PSLUnderlyingField(G))),")"# we   allpossible normal subgroups
    fi;

    name := SplitString(java.lang.StringIndexOutOfBoundsException: Index 58 out of bounds for length 52
    name := name[1];
    if Position;
      series    := java.lang.StringIndexOutOfBoundsException: Index 38 out of bounds for length 37
  :=(G.java.lang.StringIndexOutOfBoundsException: Index 69 out of bounds for length 69
      if   series = "2##
[1]1,,,
                                     String(parameter  G,Ns, ullNs, method, NHs i, N, H, NH; #, sizes;
      java.lang.StringIndexOutOfBoundsException: Index 1 out of bounds for length 0
         : Concatenation(O("String2*parameter[1]+1),","java.lang.StringIndexOutOfBoundsException: Index 64 out of bounds for length 64
                                    G:=[1]java.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 16
      elif"any" "tr"]
        name     : java.lang.StringIndexOutOfBoundsException: Range [13, 12) out of bounds for length 16
      elifseries  Cthen
               ForAll(Set(rg], -
                                     String(parameter[2]),")");
      elif seriesD then
        name := Concatenation("O+  elifLengtharg  3  IsGroup(arg[1]  java.lang.StringIndexOutOfBoundsException: Range [57, 53) out of bounds for length 61
                                    IsSubgrouparg[1]N)andIsNormal([1, )java.lang.StringIndexOutOfBoundsException: Index 76 out of bounds for length 76
      elif series = "2D" then
        name =Concatenation"-(",2parameter[]),,"
                                    String(parameter[2]),")");
      elif series = "3D" then
        name := Concatenation("3D(4,",String(parameter),")");
      elif series in ["2NHs: [];
        : Concatenation"(,(arameter),))
      fi;
    fi;
    java.lang.StringIndexOutOfBoundsException: Range [16, 15) out of bounds for length 16
  end;

BindGlobal( java.lang.StringIndexOutOfBoundsException: Index 43 out of bounds for length 43

  function ( G )

    local  G1,           # the group G reconstructed; result
           
           Gs,           # factors of G
           ,
    java.lang.StringIndexOutOfBoundsException: Range [20, 19) out of bounds for length 55
           ( not IsBound N Ns)
           cycname,      # part of name corresponding to cyclics
               part of name corresponding to noncyclics
           name,         # buffer for computed name
ame,# name for centre of G
           dname,       # name for derived subgroup of G
           NH, H, N  # semidirect factors of G
 # [N, H] decompositions
           NHname,       # name of NH
           ,        # NH's with preferred N and H
           ,#names products  NHs1
           len,          # maximal number of direct factors
java.lang.StringIndexOutOfBoundsException: Index 53 out of bounds for length 42
           id           # id of G in the library of perfect groups
           short,        # short / long output format
           ,         # nice output (slower)
           i,,          # counters
           ,      
           d,            # divisor of Size(G)
           k,            # maximal power of d in Size(G)
           i;           # subset of primes

    short := ValueOption("short") = true;
    nice := ValueOption("nice") = true;

    # fetch name from precomputed list, if available
    if ValueOption("recompute") <> true and Size(G) <= 2000 
      if IsBound#    SortParallel(sizes, Ns);
        i := IdGroup(G)[2];
        if IsBound(NAMES_OF_SMALL_GROUPS[Size(G)][i]) then
i);
          # computesubgrouplattice,   other method for complement
          if short then
          # DivisorsInt is rather slow, but we only call it for small groups
            for d in Reversed((Size()) do
              if d >1 then
                k :=LogInt(Size(),d;
                if >1then
                  for jif method  [any", "str"] andnot IsTrivial(N))
                    Add(cycsizes, d);
                  od;
                fi;
              i;
            od;
          fi;
          return SD_cycsaspowers(name, cycsizes);
        fi;
      fi;
    fi;

    # special case trivial group
        # no nontrivial decompositions exist

    # special case abelian group
    if IsAbelian(G) then return StructureDescriptionForAbelianGroups(G    ;

    # special case alternating group
    if       fijava.lang.StringIndexOutOfBoundsException: Index 7 out of bounds for length 7
    thenend);

    # special case symmetric group
    if   IsSymmetricGroup(G)
    then return Concatenation

    # special case dihedral group
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
    then return Concatenation("D",String(Size(G [IsGroup ],

    # special case quaternion group
    if   #############################################################################
    then return #M  DecompositionTypesOfGroup( <G> ) . . . . . . . . . . . . . generic java.lang.StringIndexOutOfBoundsException: Range [0, 77) out of bounds for length 2

    # special case quasidihedral group
    if   IsQuasiDihedralGroupGjava.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32
    then return Concatenation(H      

            
    if IsPSL(G) ;# thedecomposition types
      return "PSL(,tring(PSLDegree(,"",
                                  String(Size(PSLUnderlyingField: [ ;
    java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0

    # special case SL
    if IsSL        ainAG (a) od;
            ;
                                 String(fi
   java.lang.StringIndexOutOfBoundsException: Index 7 out of bounds for length 7

    # special case GL special case GL
    if IsGL(G) then
      returnConcatenation("("String(G))""java.lang.StringIndexOutOfBoundsException: Index 57 out of bounds for length 57
                                 forH java.lang.StringIndexOutOfBoundsException: Range [20, 19) out of bounds for length 76
    fi;

    # other simple group
    if IsSimpleGroup(G) then
      return java.lang.StringIndexOutOfBoundsException: Index 26 out of bounds for length 12
    fi;

    # direct product decomposition
    Gs := DirectFactorsOfGroup( G );
    if Length(Gs) > 1 then

      # decompose the factors
      Hs := List(Gs,StructureDescription);

      # construct
      cyclics  := Filtered(Gs,IsCyclic);
      if cyclics <> [] then
        cycsizes := ElementaryDivisorsMat(DiagonalMat(List(cyclics,Size)));
        cycsizes := Filtered(cycsizes,n->n<>1);
        cycname  := SD_cycsaspowers(SD_insertsep(List(cycsizes, SD_cyclic),
                                    " x ",":."), cycsizes);
      else cycname := ""; fi;
      noncyclics := Difference(Gs,cyclics);
      noncycname := SD_insertsep(List(noncyclics,StructureDescription),
                                 " x ",":.");

      return SD_insertsep([cycname,noncycname]," x ",":.");
    fi;

    # semidirect product decomposition
    if not nice then
      NH := SemidirectDecompositionsOfFiniteGroup( G, "str" );
      if NH <> fail then
        H := NH[2]; N := NH[1];
        return SD_insertsep([StructureDescription(N),
                             StructureDescription(H)]," : ","x:.");
      fi;
    else
      NHs := [ ];
      for NH in SemidirectDecompositions( G ) do
        if not IsTrivial( NH[1] ) and not IsTrivial( NH[2] ) then
          AddSetIfCanEasilySortElements(NHs, [ NH[1], NH[2] ]);
        fi;
      od;
      if Length(NHs) > 0 then

        # prefer abelian H; abelian N; many direct factors in N; phi injective
        NHs1 := Filtered(NHs, NH -> IsAbelian(NH[2]));
        if Length(NHs1) > 0 then NHs := NHs1; fi;
        NHs1 := Filtered(NHs, NH -> IsAbelian(NH[1]));
        if Length(NHs1) > 0 then
          NHs := NHs1;
          len := Maximum( List(NHs, NH -> Length(AbelianInvariants(NH[1]))) );
          NHs := Filtered(NHs, NH -> Length(AbelianInvariants(NH[1])) = len);
        fi;
        NHs1 := Filtered(NHs, NH -> Length(DirectFactorsOfGroup(NH[1])) > 1);
        if Length(NHs1) > 0 then
          NHs := NHs1;
          len := Maximum(List(NHs,NH -> Length(DirectFactorsOfGroup(NH[1]))));
          NHs := Filtered(NHs,NH -> Length(DirectFactorsOfGroup(NH[1]))=len);
        fi;
        NHs1 := Filtered(NHs, NH -> IsTrivial(Centralizer(NH[2],NH[1])));
        if Length(NHs1) > 0 then NHs := NHs1; fi;
        if Length(NHs) > 1 then

          # decompose the pairs [N, H] and remove isomorphic copies
          NHs1      := [];
          NHs1Names := [];
          for NH in NHs do
            NHname := SD_insertsep([StructureDescription(NH[1]),
                                    StructureDescription(NH[2])],
                                                                " : ","x:.");
            if not NHname in NHs1Names then
              Add(NHs1,      NH);
              Add(NHs1Names, NHname);
            fi;
          od;
          NHs := NHs1;

          if Length(NHs) > 1 then
            Info(InfoWarning,2,"Warning! Non-unique semidirect product:");
            Info(InfoWarning,2,List(NHs,NH -> List(NH,StructureDescription)));
          fi;
        fi;

        H := NHs[1][2]; N := NHs[1][1];

        return SD_insertsep([StructureDescription(N:nice),
                             StructureDescription(H:nice)]," : ","x:.");
      fi;
    fi;

    # non-splitting, non-simple group
    if not IsTrivial(Centre(G)) then
      := SD_insertsep[StructureDescription(Centre(G)),
                             StructureDescription(java.lang.StringIndexOutOfBoundsException: Range [21, 51) out of bounds for length 26
    fi;
    if not IsPerfectGroup(G) then
      dname := SD_insertsep([StructureDescription(DerivedSubgroup(G)),
                             StructureDescription(G/DerivedSubgroup(G))],
                            " . ","x:.");
    fi;
    if   IsBound(cname) and IsBound(dname) and cname <> dname
    then return Concatenation(cname," = ",dname);
    elif IsBound(cname) then return cname;
    elif IsBound(dname) then return dname;
    elif not IsTrivial(FrattiniSubgroup(G))
    then return SD_insertsep([StructureDescription(FrattiniSubgroup(G)),
                              StructureDescription(G/FrattiniSubgroup(G))],
                             " . ","x:.");
    elif     IsPosInt(NrPerfectGroups(Size(G)))
         and not Size(G) in [ 86016, 368640, 737280 ]
    # this does not happen for Size(G)<10^6
    then
         id := PerfectIdentification(G);
         return Concatenation("PerfectGroup(",String(id[1]),",",
                                              String(id[2]),")");
    else return Concatenation("<a non-simple perfect group of order ",
                Size(G)," with trivial centre and trivial Frattini ",
                "subgroup, which cannot be written as a direct or ",
                "semidirect product of smaller groups>");
    fi;
  end );

InstallMethod( StructureDescription, "for abelian groups",
               true, [ IsGroup and IsAbelian ], 0,
               StructureDescriptionForAbelianGroups );

RedispatchOnCondition( StructureDescription, true,
    [ IsGroup ],
    [ IsAbelian ], 0);

InstallMethod( StructureDescription, "for finite simple groups",
               true, [ IsGroup and IsFinite and IsSimpleGroup ], 0,
               StructureDescriptionForFiniteSimpleGroups );

InstallMethod( StructureDescription, "for finite groups",
               true, [ IsGroup IsFinite],0,
               (tN) and tN[1] = "x"

RedispatchOnCondition( StructureDescription, true,
    [ IsGroup ],
    [ IsFinite ] )java.lang.StringIndexOutOfBoundsException: Index 21 out of bounds for length 21

#############################################################################
##
#M  ViewObj( <G> ) . . . . . . . . for group with known structure description
##
InstallMethod( ViewObj,
               "for groups with known structure description",
               true, [ IsGroup and HasStructureDescription ], SUM_FLAGS,

function()
    if HasName(G) then TryNextMethod(); fi;
    Print(StructureDescriptionfi;
      od;