Quelle grppclat.gi Sprache: unbekannt

#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Alexander Hulpke.
##
## 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 declarations for the subgroup lattice functions for
## pc groups.
##

#############################################################################
##
#F InvariantElementaryAbelianSeries( <G>, <morph>, [ <N> ] )
## find <morph> invariant EAS of G (through N)
##
InstallGlobalFunction(InvariantElementaryAbelianSeries,function(arg)
local G,morph,N,s,p,e,i,j,k,ise,fine,cor;
 G:=arg[1];
 morph:=arg[2];
 fine:=false;
 if Length(arg)>2 then
 N:=arg[3];
 e:=[G,N];
 if Length(arg)>3 then
 fine:=arg[4];
 fi;
 if fine then
 e:=ElementaryAbelianSeries(e);
 else
 e:=ElementaryAbelianSeriesLargeSteps(e);
 fi;
 else
 N:=TrivialSubgroup(G);
 e:=DerivedSeriesOfGroup(G);
 e:=ElementaryAbelianSeriesLargeSteps(e);
 fi;
 s:=[G];
 i:=2;
 while i<=Length(e) do
 # intersect all images of normal subgroup to obtain invariant one
 # as G is invariant, we dont have to deal with special cases
 ise:=[e[i]];
 cor:=e[i];
 for j in ise do
 for k in morph do
 p:=Image(k,j);
 if not IsSubset(p,cor) then
 Add(ise,p);
 cor:=Intersection(cor,p);
 fi;
 od;
 od;
 Assert(1,HasElementaryAbelianFactorGroup(Last(s),cor));
 ise:=cor;
 Add(s,ise);
 p:=Position(e,ise);
 if p<>fail then
 i:=p+1;
 elif fine then
 e:=ElementaryAbelianSeries([G,ise,TrivialSubgroup(G)]);
 i:=Position(e,ise)+1;
 else
 e:=ElementaryAbelianSeriesLargeSteps([G,ise,TrivialSubgroup(G)]);
 i:=Position(e,ise)+1;
 fi;
 Assert(1,ise in e);
 od;
 return s;
end);

#############################################################################
##
#F InducedAutomorphism(<epi>,<aut>)
##
InstallGlobalFunction(InducedAutomorphism,function(epi,aut)
local f;
 f:=Range(epi);
 if HasIsConjugatorAutomorphism( aut ) and IsConjugatorAutomorphism( aut )
 and ConjugatorOfConjugatorIsomorphism( aut ) in Source( epi ) then
 aut:= ConjugatorAutomorphismNC( f,
 Image( epi, ConjugatorOfConjugatorIsomorphism( aut ) ) );
 else
 aut:= GroupHomomorphismByImagesNC(f,f,GeneratorsOfGroup(f),
 List(GeneratorsOfGroup(f),
 i->Image(epi,Image(aut,PreImagesRepresentative(epi,i)))));
 SetIsInjective(aut,true);
 SetIsSurjective(aut,true);
 fi;
 return aut;
end);

#############################################################################
##
#F InvariantSubgroupsElementaryAbelianGroup(<G>,<homs>[,<dims]) submodules
#F find all subgroups of el. ab. <G>, which are invariant under all <homs>
#F which have dimension in dims
##
InstallGlobalFunction(InvariantSubgroupsElementaryAbelianGroup,function(arg)
local g,op,a,pcgs,ma,mat,d,f,i,j,new,newmat,id,p,dodim,compldim,compl,dims,nm;
 g:=arg[1];
 op:=arg[2];
 if not IsElementaryAbelian(g) then
 Error("<g> must be a vector space");
 fi;
 if IsTrivial(g) then
 return [g];
 fi;
 pcgs:=Pcgs(g);
 d:=Length(pcgs);
 p:=RelativeOrderOfPcElement(pcgs,pcgs[1]);
 f:=GF(p);
 if Length(arg)=2 then
 dims:=[0..d];
 else
 dims:=arg[3];
 fi;

 if Length(dims)=0 then
 return [];
 fi;

 if Length(op)=0 then

 # trivial operation: enumerate subspaces
 # check which dimensions we'll need
 ma:=QuoInt(d,2);
 dodim:=[];
 compldim:=[];
 for i in dims do
 if i<=ma then
 AddSet(dodim,i);
 else
 AddSet(dodim,d-i);
 AddSet(compldim,d-i);
 fi;
 od;
 if d<3 then compldim:=[]; fi;
 dodim:=Maximum(dodim);

 # enumerate spaces
 id:= Immutable( IdentityMat(d, One(f)) );
 ma:=[[],[ShallowCopy(id[1])]];
 ConvertToMatrixRep(ma[2],f);
 # the complements to ma
 if d>1 then
 compl:=[ShallowCopy(id)];
 else
 compl:=[];
 fi;
 if d>2 then
 nm:=TriangulizedNullspaceMat(TransposedMat(id{[1]}));
 ConvertToMatrixRep(nm,f);
 Add(compl,nm);
 fi;
 for i in [2..d] do
 new:=[];
 for mat in ma do
 # subspaces of equal dimension
 for j in [0..p^Length(mat)-1] do
 if j=0 then
 # special case for subspace of higher dimension
 if Length(mat)<dodim then
 newmat:=Concatenation(mat,[id[i]]);
 ConvertToMatrixRep(newmat,f);
 else
 newmat:=false;
 fi;
 else
 # possible extension number d
 a:=CoefficientsQadic(j,p)*One(f);
 newmat:=List(mat,ShallowCopy);
 for j in [1..Length(a)] do
 newmat[j][i]:=a[j];
 od;
 ConvertToMatrixRep(newmat,f);
 fi;
 if newmat<>false then
 # we will need the space for the next level
 Add(new,newmat);

 # note complements if necc.
 if Length(newmat) in compldim then
 nm:=NullspaceMat(TransposedMat(newmat));
 ConvertToMatrixRep(nm,f);
 Add(compl,nm);
 #Add(compl,List(NullspaceMat(TransposedMat(newmat*One(f))),
 # i->List(i,IntFFE)));
 fi;
 fi;
 od;
 od;
 ma:=Concatenation(ma,new);
 od;

 ma:=Concatenation(ma,compl);

 # take only those of right dim
 ma:=Filtered(ma,i->Length(i) in dims);

 # convert to grps (noting also the triv. one)
 new:=ma;
 for i in [1..Length(new)] do
 #a:=SubgroupNC(Parent(g),List(i,j->Product([1..d],k->pcgs[k]^j[k])));
 ma:=new[i];
 a:=SubgroupNC(Parent(g),List(ma,
 j->PcElementByExponentsNC(pcgs,List(j,IntFFE))));
# a:=MySubgroupNC(Parent(g),List(i,j->PcElementByExponentsNC(pcgs,j)),
# IsFinite and IsSubsetLocallyFiniteGroup and
# IsSupersolvableGroup and IsNilpotentGroup and
# IsCommutative and IsElementaryAbelian);

 SetSize(a,p^Length(ma));
 if Size(a)=Size(g) then a:=g;fi;
 new[i]:=a;
 od;
 ma:=new;

 else

 # compute representation
 ma:=[];
 for i in op do
 mat:=[];
 for j in pcgs do
 Add(mat,ExponentsOfPcElement(pcgs,Image(i,j))*One(f));
 od;
 mat:=ImmutableMatrix(f,mat);
 Add(ma,mat);
 od;

 ma:=GModuleByMats(ma,f);
 mat:=MTX.BasesSubmodules(ma);

 ma:=[];
 for i in mat do
 Add(ma,SubgroupNC(Parent(g),
 List(i,j->PcElementByExponentsNC(pcgs,j))));
 #List(i,j->Product([1..d],k->pcgs[k]^IntFFE(j[k])))));
 od;
 fi;
 SortBy(ma,x->-Size(x));
 return ma;
end);

#############################################################################
##
#F ActionSubspacesElementaryAbelianGroup(,<G>[,<dims>])
##
## compute the permutation action of on the subspaces of the
## elementary abelian subgroup <G> of . Returns
## a list [<subspaces>,<action>], where <subspaces> is a list of all the
## subspaces (as groups) and <action> a homomorphism from in a
## permutation group, which is equal to the action homomrophism for the
## action of on <subspaces>. If <dims> is given, only subspaces of
## dimension <dims> are considered. Instead of <G> also a (modulo) pcgs
## may be given, in this case <subspaces> are pre-images of the subspaces.
##
InstallGlobalFunction(ActionSubspacesElementaryAbelianGroup,function(arg)
local P,g,op,act,a,pcgs,ma,mat,d,f,i,j,new,newmat,id,p,dodim,compldim,compl,
 dims,Pgens,Pcgens,Pu,perms,one,par,ker,kersz,pcelm,pccache,asz;

 P:=arg[1];
 if IsModuloPcgs(arg[2]) then
 pcgs:=arg[2];
 g:=Group(NumeratorOfModuloPcgs(pcgs));
 if not IsSubset(Parent(P),g) then # for matrix groups we need a parent here.
 par:=ClosureGroup(Parent(P),g);
 else
 par:=P;
 fi;
 Pu:=AsSubgroup(par,g);
 ker:=SubgroupNC(par,DenominatorOfModuloPcgs(pcgs));
 kersz:=Size(ker);
 else
 kersz:=1;
 g:=arg[2];
 par:=Parent(g);
 Pu:=Centralizer(P,g);
 if not IsElementaryAbelian(g) then
 Error("<g> must be a vector space");
 fi;
 if IsTrivial(g) then
 return [g];
 fi;

 pcgs:=Pcgs(g);
 fi;

 d:=Length(pcgs);
 p:=RelativeOrderOfPcElement(pcgs,pcgs[1]);
 f:=GF(p);
 one:=One(f);
 if Length(arg)=2 then
 dims:=[0..d];
 else
 dims:=arg[3];
 fi;

 if Length(dims)=0 then
 return [];
 fi;

 # find representatives generating the acting factor
 Pgens:=[];
 Pcgens:=GeneratorsOfGroup(Pu);
 while Size(Pu)<Size(P) do
 repeat
 i:=Random(P);
 until not i in Pu;
 Add(Pgens,i);
 Pu:=ClosureGroup(Pu,i);
 od;
 if Length(Pgens)>2 and Length(Pgens)>Length(SmallGeneratingSet(P)) then
 Pgens:=SmallGeneratingSet(P);
 fi;

 # compute representation
 op:=[];
 for i in Pgens do
 mat:=[];
 for j in pcgs do
 Add(mat,ExponentsConjugateLayer(pcgs,j,i)*One(f));
 od;
 mat:=ImmutableMatrix(f,mat);
 Add(op,mat);
 od;

 # and action on canonical bases
 #act:=function(bas,m)
 # bas:=bas*m;
 # bas:=List(bas,ShallowCopy);
 # TriangulizeMat(bas);
 # bas:=List(bas,IntVecFFE);
 # return bas;
 #end;
 if p=2 then
 act:=OnSubspacesByCanonicalBasisGF2;
 else
 act:=OnSubspacesByCanonicalBasis;
 fi;

 # enumerate subspaces
 # check which dimensions we'll need
 ma:=QuoInt(d,2);
 dodim:=[];
 compldim:=[];
 for i in dims do
 if i<=ma then
 AddSet(dodim,i);
 else
 AddSet(dodim,d-i);
 AddSet(compldim,d-i);
 fi;
 od;
 if d<3 then compldim:=[]; fi;
 dodim:=Maximum(dodim);

 # enumerate spaces
 id:= Immutable( IdentityMat(d, one) );
 ma:=[[],[id[1]]];
 # the complements to ma
 if d>1 then
 compl:=[ShallowCopy(id)];
 else
 compl:=[];
 fi;
 if d>2 then
 Add(compl,List(TriangulizedNullspaceMat(TransposedMat(id{[1]})),
 ShallowCopy));
 fi;
 for i in [2..d] do
 new:=[];
 for mat in ma do
 # subspaces of equal dimension
 for j in [0..p^Length(mat)-1] do
 if j=0 then
 # special case for subspace of higher dimension
 if Length(mat)<dodim then
 newmat:=Concatenation(mat,[id[i]]);
 else
 newmat:=false;
 fi;
 else
 # possible extension number d
 a:=CoefficientsQadic(j,p)*one;
 newmat:=List(mat,ShallowCopy);
 for j in [1..Length(a)] do
 newmat[j][i]:=a[j];
 od;
 fi;
 if newmat<>false then
 # we will need the space for the next level
 Add(new,Immutable(newmat));

 # note complements if necc.
 if Length(newmat) in compldim then
 a:=List(TriangulizedNullspaceMat(MutableTransposedMat(newmat)),
 ShallowCopy);
 Add(compl,Immutable(a));
 fi;
 fi;
 od;
 od;

 ma:=Concatenation(ma,new);
 od;

 ma:=Concatenation(ma,compl);

 # take only those of right dim
 ma:=Filtered(ma,i->Length(i) in dims);

 perms:=List(Pgens,i->());
 new:=[];
 for i in dims do
 mat:=Immutable(Set(Filtered(ma,j->Length(j)=i)));
 # compute action on mat
 if i>0 and i<d then
 for j in [1..Length(Pgens)] do
 #a:=Permutation(op[j],mat,act);
 a:=List([1..Length(mat)],k->PositionSorted(mat,act(mat[k],op[j])));
 a:=PermList(a);
 perms[j]:=perms[j]*a^MappingPermListList([1..Length(mat)],
 [Length(new)+1..Length(new)+Length(mat)]);
 od;
 fi;
 Append(new,mat);
 od;
 ma:=new;

 # convert to grps
 pccache:=[]; # avoid recerating different copies of same element
 pcelm:=function(vec)
 local e,p;
 e:=Immutable([vec]);
 p:=PositionSorted(pccache,e);
 if IsBound(pccache[p]) and pccache[p][1]=vec then
 return pccache[p][2];
 else
 e:=Immutable([vec,PcElementByExponentsNC(pcgs,vec)]);
 AddSet(pccache,e);
 return e[2];
 fi;
 end;

 new:=[];
 for i in ma do
 #a:=SubgroupNC(Parent(g),List(i,j->Product([1..d],k->pcgs[k]^j[k])));
 asz:=kersz*p^Length(i);
 if kersz=1 then
 a:=SubgroupNC(par,List(i,pcelm));
 else
 #a:=ClosureSubgroup(ker,List(i,pcelm):knownClosureSize:=asz);
 a:=SubgroupNC(par,Concatenation(GeneratorsOfGroup(ker),
 List(i,pcelm)));
 fi;
 SetSize(a,asz);
 Add(new,a);
 od;

 ma:= GroupByGenerators( perms, () );
 #Assert(1,Group(perms)=Action(P,new));

 op:=GroupHomomorphismByImagesNC(P,ma,Concatenation(Pcgens,Pgens),
 Concatenation(List(Pcgens,i->()),perms));
# Assert(1,Size(P)=Size(KernelOfMultiplicativeGeneralMapping(op))
# *Size(Image(op)));
 return [new,op];

end);

# test whether the c-conjugate of g is h-invariant, internal
BindGlobal( "HasInvariantConjugateSubgroup", function(g,c,h)
 # This should be done better!
 g:=ConjugateSubgroup(g,c);
 return ForAll(h,i->Image(i,g)=g);
end );

#############################################################################
##
#F SubgroupsSolvableGroup(<G>[,<opt>]) . classreps of subgrps of <G>,
## <homs>-inv. with options.
## Options are:
## actions: list of automorphisms: search for invariants
## funcnorm: N_G(actions) (speeds up calculation)
## normal: just search for normal subgroups
## consider: function(A,N,B,M) indicator function, whether
## complements of this type would be needed
## retnorm: return normalizers
##
InstallGlobalFunction(SubgroupsSolvableGroup,function(arg)
local g, # group
 isom, # isomorphism onto AgSeries group
 func, # automorphisms to be invariant under
 funcs, # <func>
 funcnorm, # N_G(funcs)
 efunc, # induced automs on factor
 efnorm, # funcnorm^epi
 e, # EAS
 len, # Length(e)
 start, # last index with EA factor
 i,j,k,l,
 m,kp, # loop
 kgens, # generators of k
 kconh, # complemnt conjugacy storage
 opt, # options record
 normal, # flag for 'normal' option
 consider, # optional 'consider' function
 retnorm, # option: return all normalizers
 f, # g/e[i]
 home, # HomePcgs(f)
 epi, # g -> f
 lastepi, # epi of last step
 n, # e[i-1]^epi
 fa, # f/n = g/e[i-1]
 hom, # f -> fa
 B, # subgroups of n
 ophom, # perm action of f on B (or false if not computed)
 a, # preimg. of group over n
 no, # N_f(a)
# aop, # a^ophom
# nohom, # ophom\rest no
 oppcgs, # acting pcgs
 oppcgsimg,# images under ophom
 ex, # external set/orbits
 bs, # b\in B normal under a, reps
 bsp, # bs index
 bsnorms, # respective normalizers
 b, # in bs
 bpos, # position in bs
 hom2, # N_f(b) -> N_f(b)/b
 nag, # AgGroup(n^hom2)
 fghom, # assoc. epi
 t,s, # dnk-transversals
 z, # Cocycles
 coboundbas,# Basis(OneCobounds)
 field, # GF(Exponent(n))
 com, # complements
 comnorms, # normalizers supergroups
 isTrueComnorm, # is comnorms the true normalizer or a supergroup
 comproj, # projection onto complement
 kgn,
 kgim, # stored decompositions, translated to matrix language
 kgnr, # assoc index
 ncom, # dito, tested
 idmat, # 1-matrix
 mat, # matrix action
 mats, # list of mats
 conj, # matrix action
 chom, # homom onto <conj>
 shom, # by s induced autom
 shoms, # list of these
 smats, # dito, matrices
 conjnr, # assoc. index
 glsyl,
 glsyr, # left and right side of eqn system
 found, # indicator for success
 grps, # list of subgroups
 ngrps, # dito, new level
 gj, # grps[j]
 grpsnorms,# normalizers of grps
 ngrpsnorms,# dito, new level
 bgids, # generators of b many 1's (used for copro)
 opr, # operation on complements
 xo; # xternal orbits

 g:=arg[1];
 if Length(arg)>1 and IsRecord(Last(arg)) then
 opt:=Last(arg);
 else
 opt:=rec();
 fi;

 # parse options
 retnorm:=IsBound(opt.retnorm) and opt.retnorm;

 # handle trivial case
 if IsTrivial(g) then
 if retnorm then
 return [[g],[g]];
 else
 return [g];
 fi;
 fi;

 normal:=IsBound(opt.normal) and opt.normal=true;
 if IsBound(opt.consider) then
 consider:=opt.consider;
 else
 consider:=false;
 fi;

 isom:=fail;

 # get automorphisms and compute their normalizer, if applicable
 if IsBound(opt.actions) then
 func:=opt.actions;
 hom2:= Filtered( func, HasIsConjugatorAutomorphism
 and IsInnerAutomorphism );
 hom2:= List( hom2, ConjugatorOfConjugatorIsomorphism );

 if IsBound(opt.funcnorm) then
 # get the func. normalizer
 funcnorm:=opt.funcnorm;
 b:=g;
 else
 funcs:= GroupByGenerators( Filtered( func,
 i -> not ( HasIsConjugatorAutomorphism( i ) and
 IsInnerAutomorphism( i ) ) ),
 IdentityMapping(g));
 IsGroupOfAutomorphismsFiniteGroup(funcs); # set filter
 if IsTrivial( funcs ) then
 b:=ClosureGroup(Parent(g),List(func,ConjugatorOfConjugatorIsomorphism));
 func:=hom2;
 else
 if IsSolvableGroup(funcs) then
 a:=IsomorphismPcGroup(funcs);
 else
 a:=IsomorphismPermGroup(funcs);
 fi;
 hom:=InverseGeneralMapping(a);
 IsTotal(hom); IsSingleValued(hom); # to be sure (should be set anyway)
 b:=SemidirectProduct(Image(a),hom,g);
 hom:=Embedding(b,1);
 funcs:=List(GeneratorsOfGroup(funcs),i->Image(hom,Image(a,i)));
 isom:=Embedding(b,2);
 hom2:=List(hom2,i->Image(isom,i));
 func:=Concatenation(funcs,hom2);
 g:=Image(isom,g);
 fi;

 # get the normalizer of <func>
 funcnorm:=Normalizer(g,SubgroupNC(b,func));
 func:=List(func,i->ConjugatorAutomorphism(b,i));
 fi;

 Assert(1,IsSubgroup(g,funcnorm));

 # compute <func> characteristic series
 e:=InvariantElementaryAbelianSeries(g,func);
 else
 func:=[];
 funcnorm:=g;
 e:=ElementaryAbelianSeriesLargeSteps(g);
 fi;

 if IsBound(opt.series) then
 e:=opt.series;
 else
 f:=DerivedSeriesOfGroup(g);
 if Length(e)>Length(f) and
 ForAll([1..Length(f)-1],i->IsElementaryAbelian(f[i]/f[i+1])) then
 Info(InfoPcSubgroup,1," Preferring Derived Series");
 e:=f;
 fi;
 fi;

# # check, if the series is compatible with the AgSeries and if g is a
# # parent group. If not, enforce this
# if not(IsParent(g) and ForAll(e,IsElementAgSeries)) then
# Info(InfoPcSubgroup,1," computing better series");
# isom:=IsomorphismAgGroup(e);
# g:=Image(isom,g);
# e:=List(e,i->Image(isom,i));
# funcnorm:=Image(isom,funcnorm);
#
# #func:=List(func,i->isom^-1*i*isom);
# hom:=[];
# for i in func do
# hom2:=GroupHomomorphismByImagesNC(g,g,g.generators,List(g.generators,
# j->Image(isom,Image(i,PreImagesRepresentative(isom,j)))));
# hom2.isMapping:=true;
# Add(hom,hom2);
# od;
# func:=hom;
# else
# isom:=false;
# fi;

 len:=Length(e);

 if IsBound(opt.groups) then
 start:=0;
 while start+1<=Length(e) and ForAll(opt.groups,i->IsSubgroup(e[start+1],i)) do
 start:=start+1;
 od;
 Info(InfoPcSubgroup,1,"starting index ",start);
 epi:=NaturalHomomorphismByNormalSubgroup(g,e[start]);
 lastepi:=epi;
 f:=Image(epi,g);
 grps:=List(opt.groups,i->Image(epi,i));
 if not IsBound(opt.grpsnorms) then
 opt:=ShallowCopy(opt);
 opt.grpsnorms:=List(opt.groups,i->Normalizer(e[1],i));
 fi;
 grpsnorms:=List(opt.grpsnorms,i->Image(epi,i));
 else
 # search the largest elementary abelian quotient
 start:=2;
 while start<len and IsElementaryAbelian(g/e[start+1]) do
 start:=start+1;
 od;

 # compute all subgroups there
 if start<len then
 # form only factor groups if necessary
 epi:=NaturalHomomorphismByNormalSubgroup(g,e[start]);
 LockNaturalHomomorphismsPool(g,e[start]);
 f:=Image(epi,g);
 else
 f:=g;
 epi:=IdentityMapping(f);
 fi;
 lastepi:=epi;
 efunc:=List(func,i->InducedAutomorphism(epi,i));
 grps:=InvariantSubgroupsElementaryAbelianGroup(f,efunc);
 Assert(1,ForAll(grps,i->ForAll(efunc,j->Image(j,i)=i)));
 grpsnorms:=List(grps,i->f);
 Info(InfoPcSubgroup,5,List(grps,Size),List(grpsnorms,Size));

 fi;

 for i in [start+1..len] do
 Info(InfoPcSubgroup,1," step ",i,": ",Index(e[i-1],e[i]),", ",
 Length(grps)," groups");
 # compute modulo e[i]
 if i<len then
 # form only factor groups if necessary
 epi:=NaturalHomomorphismByNormalSubgroup(g,e[i]);
 f:=Image(epi,g);
 else
 f:=g;
 epi:=IdentityMapping(g);
 fi;
 home:=HomePcgs(f); # we want to compute wrt. this pcgs
 n:=Image(epi,e[i-1]);

 # the induced factor automs
 efunc:=List(func,i->InducedAutomorphism(epi,i));
 # filter the non-trivial ones
 efunc:=Filtered(efunc,i->ForAny(GeneratorsOfGroup(f),j->Image(i,j)<>j));

 if Length(efunc)>0 then
 efnorm:=Image(epi,funcnorm);
 fi;

 if Length(efunc)=0 then
 ophom:=ActionSubspacesElementaryAbelianGroup(f,n);
 B:=ophom[1];
 Info(InfoPcSubgroup,2," ",Length(B)," normal subgroups");
 ophom:=ophom[2];

 ngrps:=[];
 ngrpsnorms:=[];
 oppcgs:=Pcgs(Source(ophom));
 oppcgsimg:=List(oppcgs,i->Image(ophom,i));
 ex:=[1..Length(B)];
 IsSSortedList(ex);
 ex:=ExternalSet(Source(ophom),ex,oppcgs,oppcgsimg,OnPoints);
 ex:=ExternalOrbitsStabilizers(ex);

 for j in ex do
 Add(ngrps,B[Representative(j)]);
 Add(ngrpsnorms,StabilizerOfExternalSet(j));
# Assert(1,Normalizer(f,B[j[1]])=ngrpsnorms[Length(ngrps)]);
 od;

 else
 B:=InvariantSubgroupsElementaryAbelianGroup(n,efunc);
 ophom:=false;
 Info(InfoPcSubgroup,2," ",Length(B)," normal subgroups");

 # note the groups in B
 ngrps:=SubgroupsOrbitsAndNormalizers(f,B,false);
 ngrpsnorms:=List(ngrps,i->i.normalizer);
 ngrps:=List(ngrps,i->i.representative);
 fi;

 # Get epi to the old factor group
 # as hom:=NaturalHomomorphism(f,fa); does not work, we have to play tricks
 hom:=lastepi;
 lastepi:=epi;
 fa:=Image(hom,g);

 hom:= GroupHomomorphismByImagesNC(f,fa,GeneratorsOfGroup(f),
 List(GeneratorsOfGroup(f),i->
 Image(hom,PreImagesRepresentative(epi,i))));
 Assert(2,KernelOfMultiplicativeGeneralMapping(hom)=n);

 # lift the known groups
 for j in [1..Length(grps)] do

 gj:=grps[j];
 if Size(gj)>1 then
 a:=PreImage(hom,gj);
 Assert(1,Size(a)=Size(gj)*Size(n));
 Add(ngrps,a);
 no:=PreImage(hom,grpsnorms[j]);

 Add(ngrpsnorms,no);

 if Length(efunc)>0 then
 # get the double cosets
 t:=List(DoubleCosets(f,no,efnorm),Representative);
 Info(InfoPcSubgroup,2," |t|=",Length(t));
 t:=Filtered(t,i->HasInvariantConjugateSubgroup(a,i,efunc));
 Info(InfoPcSubgroup,2,"invar:",Length(t));
 fi;

 # we have to extend with those b in B, that are normal in a
 if ophom<>false then
 #aop:=Image(ophom,a);
 #SetIsSolvableGroup(aop,true);

 if Length(GeneratorsOfGroup(a))>2 then
 bs:=SmallGeneratingSet(a);
 else
 bs:=GeneratorsOfGroup(a);
 fi;
 bs:=List(bs,i->Image(ophom,i));

 bsp:=Filtered([1..Length(B)],i->ForAll(bs,j->i^j=i)
 and Size(B[i])<Size(n));
 bs:=B{bsp};
 else
 bsp:=false;
 bs:=Filtered(B,i->IsNormal(a,i) and Size(i)<Size(n));
 fi;

 if Length(efunc)>0 and Length(t)>1 then
 # compute also the invariant ones under the conjugates:
 # equivalently: Take all equivalent ones and take those, whose
 # conjugates lie in a and are normal under a
 for k in Filtered(t,i->not i in no) do
 bs:=Union(bs,Filtered(List(B,i->ConjugateSubgroup(i,k^(-1))),
 i->IsSubset(a,i) and IsNormal(a,i) and Size(i)<Size(n) ));
 od;
 fi;

 # take only those bs which are valid
 if consider<>false then
 Info(InfoPcSubgroup,2," ",Length(bs)," subgroups lead to ");
 if bsp<>false then
 bsp:=Filtered(bsp,j->consider(no,a,n,B[j],e[i])<>false);
 IsSSortedList(bsp);
 bs:=bsp; # to get the 'Info' right
 else
 bs:=Filtered(bs,j->consider(no,a,n,j,e[i])<>false);
 fi;
 Info(InfoPcSubgroup,2,Length(bs)," valid ones");
 fi;

 if ophom<>false then
 #nohom:=List(GeneratorsOfGroup(no),i->Image(ophom,i));
 #aop:=SubgroupNC(Image(ophom),nohom);
 #nohom:=GroupHomomorphismByImagesNC(no,aop,
 # GeneratorsOfGroup(no),nohom);

 if Length(bsp)>0 then
 oppcgs:=Pcgs(no);
 oppcgsimg:=List(oppcgs,i->Image(ophom,i));
 ex:=ExternalSet(no,bsp,oppcgs,oppcgsimg,OnPoints);
 ex:=ExternalOrbitsStabilizers(ex);

 bs:=[];
 bsnorms:=[];
 for bpos in ex do
 Add(bs,B[Representative(bpos)]);
 Add(bsnorms,StabilizerOfExternalSet(bpos));
# Assert(1,Normalizer(no,B[bpos[1]])=Last(bsnorms));
 od;
 fi;

 else
 # fuse under the action of no and compute the local normalizers
 bs:=SubgroupsOrbitsAndNormalizers(no,bs,true);
 bsnorms:=List(bs,i->i.normalizer);
 bs:=List(bs,i->i.representative);
 fi;

Assert(1,ForAll(bs,i->ForAll(efunc,j->Image(j,i)=i)));

 # now run through the b in bs
 for bpos in [1..Length(bs)] do
 b:=bs[bpos];
 Assert(2,IsNormal(a,b));
 # test, whether we'll have to consider this case

# this test has basically be done before the orbit calculation already
# if consider<>false and consider(a,n,b,e[i])=false then
# Info(InfoPcSubgroup,2," Ignoring case");
# s:=[];

 # test, whether b is invariant
 if Length(efunc)>0 then
 # extend to dcs of bnormalizer
 s:=RightTransversal(no,bsnorms[bpos]);
 nag:=Length(s);
 s:=Concatenation(List(s,i->List(t,j->i*j)));
 z:=Length(s);
 #NOCH: Fusion
 # test, which ones are usable at all
 s:=Filtered(s,i->HasInvariantConjugateSubgroup(b,i,efunc));
 Info(InfoPcSubgroup,2," |s|=",nag,"-(m)>",z,"-(i)>",Length(s));
 else
 s:=[()];
 fi;

 if Length(s)>0 then
 nag:=InducedPcgs(home,n);
 nag:=nag mod InducedPcgs(nag,b);
# if Index(Parent(a),a.normalizer)>1 then
# Info(InfoPcSubgroup,2," normalizer index ",
# Index(Parent(a),a.normalizer));
# fi;

 z:=rec(group:=a,
 generators:=InducedPcgs(home,a) mod NumeratorOfModuloPcgs(nag),
 modulePcgs:=nag);
 OCOneCocycles(z,true);
 if IsBound(z.complement) and
 # normal complements exist, iff the coboundaries are trivial
 (normal=false or Dimension(z.oneCoboundaries)=0)
 then
 # now fetch the complements

 z.factorGens:=z.generators;
 coboundbas:=Basis(z.oneCoboundaries);
 com:=BaseSteinitzVectors(BasisVectors(Basis(z.oneCocycles)),
 BasisVectors(coboundbas));
 field:=LeftActingDomain(z.oneCocycles);
 if Size(field)^Length(com.factorspace)>100000 then
 Info(InfoWarning,1, "Many (",
 Size(field)^Length(com.factorspace),") complements!");
 fi;
 com:=Enumerator(VectorSpace(field,com.factorspace,
 Zero(z.oneCocycles)));
 Info(InfoPcSubgroup,3," ",Length(com),
 " local complement classes");

 # compute fusion
 kconh:=List([1..Length(com)],i->[i]);
 if i<len or retnorm then
 # we need to compute normalizers
 comnorms:=[];
 else
 comnorms:=fail;
 fi;

 if Length(com)>1 and Size(a)<Size(bsnorms[bpos]) then

 opr:=function(cyc,elm)
 local l,i;
 l:=z.cocycleToList(cyc);
 for i in [1..Length(l)] do
 l[i]:=(z.complementGens[i]*l[i])^elm;
 od;
 l:=CorrespondingGeneratorsByModuloPcgs(z.origgens,l);
 for i in [1..Length(l)] do
 l[i]:=LeftQuotient(z.complementGens[i],l[i]);
 od;
 l:=z.listToCocycle(l);
 return SiftedVector(coboundbas,l);
 end;

 xo:=ExternalOrbitsStabilizers(
 ExternalSet(bsnorms[bpos],com,opr));

 for k in xo do
 l:=List(k,i->Position(com,i));
 if comnorms<>fail then
 comnorms[l[1]]:=StabilizerOfExternalSet(k);
 isTrueComnorm:=false;
 fi;
 l:=Set(l);
 for kp in l do
 kconh[kp]:=l;
 od;
 od;

 elif comnorms<>fail then
 if Size(a)=Size(bsnorms[bpos]) then
 comnorms:=List(com,i->z.cocycleToComplement(i));
 isTrueComnorm:=true;
 comnorms:=List(comnorms,
 i->ClosureSubgroup(CentralizerModulo(n,b,i),i));
 else
 isTrueComnorm:=false;
 comnorms:=List(com,i->bsnorms[bpos]);
 fi;
 fi;

 if Length(efunc)>0 then
 ncom:=[];

 #search for invariant ones

 # force exponents corresponding to vector space

 # get matrices for the inner automorphisms
# conj:=[];
# for k in GeneratorsOfGroup(a) do
# mat:=[];
# for l in nag do
# Add(mat,One(field)*ExponentsOfPcElement(nag,l^k));
# od;
# Add(conj,mat);
# od;
 conj:=LinearOperationLayer(a,GeneratorsOfGroup(a),nag);

 idmat:=conj[1]^0;
 mat:= GroupByGenerators( conj, idmat );
 chom:= GroupHomomorphismByImagesNC(a,mat,
 GeneratorsOfGroup(a),conj);

 smats:=[];
 shoms:=[];

 fghom:=Concatenation(z.factorGens,GeneratorsOfGroup(n));
 bgids:=List(GeneratorsOfGroup(n),i->One(b));

 # now run through the complements
 for kp in [1..Length(com)] do

 if kconh[kp]=fail then
 Info(InfoPcSubgroup,3,"already conjugate");
 else

 l:=z.cocycleToComplement(com[kp]);
 # the projection on the complement
 k:=ClosureSubgroup(b,l);
 if Length(s)=1 and IsOne(s[1]) then
 # special case -- no conjugates
 if ForAll(efunc,x->ForAll(GeneratorsOfGroup(l),
 y->ImagesRepresentative(x,y) in k)) then
 l:=rec(representative:=k);
 if comnorms<>fail then
 if IsBound(comnorms[kp]) then
 l.normalizer:=comnorms[kp];
 else
 l.normalizer:=Normalizer(bsnorms[bpos],
 ClosureSubgroup(b,k));
 fi;
 fi;
 Add(ncom,l);

 # tag all conjugates
 for l in kconh[kp] do
 kconh[l]:=fail;
 od;
 fi;

 else
 # generic case

 comproj:= GroupHomomorphismByImagesNC(a,a,fghom,
 Concatenation(GeneratorsOfGroup(l),bgids));

 # now run through the conjugating elements
 conjnr:=1;
 found:=false;
 while conjnr<=Length(s) and found=false do
 if not IsBound(smats[conjnr]) then
 # compute the matrix action for the induced, jugated
 # morphisms
 m:=s[conjnr];
 smats[conjnr]:=[];
 shoms[conjnr]:=[];
 for l in efunc do
 # the induced, jugated morphism
 shom:= GroupHomomorphismByImagesNC(a,a,
 GeneratorsOfGroup(a),
 List(GeneratorsOfGroup(a),
 i->Image(l,i^m)^Inverse(m)));

 mat:=List(nag,
 i->One(field)*ExponentsOfPcElement(nag,
 Image(shom,i)));
 Add(smats[conjnr],mat);
 Add(shoms[conjnr],shom);
 od;
 fi;

 mats:=smats[conjnr];
 # now test whether the complement k can be conjugated to
 # be invariant under the morphisms to mats
 glsyl:=List(nag,i->[]);
 glsyr:=[];
 for l in [1..Length(efunc)] do
 kgens:=GeneratorsOfGroup(k);
 for kgnr in [1..Length(kgens)] do

 kgn:=Image(shoms[conjnr][l],kgens[kgnr]);
 kgim:=Image(comproj,kgn);
 Assert(2,kgim^-1*kgn in n);
 # nt part
 kgn:=kgim^-1*kgn;

 # translate into matrix terms
 kgim:=Image(chom,kgim);
 kgn:=One(field)*ExponentsOfPcElement(nag,kgn);

 # the matrix action
 mat:=idmat+(mats[l]-idmat)*kgim-mats[l];

 # store action and vector
 for m in [1..Length(glsyl)] do
 glsyl[m]:=Concatenation(glsyl[m],mat[m]);
 od;
 glsyr:=Concatenation(glsyr,kgn);

 od;
 od;

 # a possible conjugating element is a solution of the
 # large LGS
 l:= SolutionMat(glsyl,glsyr);
 if l <> fail then
 m:=Product([1..Length(l)],
 i->nag[i]^IntFFE(l[i]));
 # note that we found one!
 found:=[s[conjnr],m];
 fi;

 conjnr:=conjnr+1;
 od;

 # there is an invariant complement?
 if found<>false then
 found:=found[2]*found[1];
 l:=ConjugateSubgroup(ClosureSubgroup(b,k),found);
 Assert(1,ForAll(efunc,i->Image(i,l)=l));
 l:=rec(representative:=l);
 if comnorms<>fail then
 if IsBound(comnorms[kp]) then
 l.normalizer:=ConjugateSubgroup(comnorms[kp],found);
 else
 l.normalizer:=ConjugateSubgroup(
 Normalizer(bsnorms[bpos],
 ClosureSubgroup(b,k)), found);
 fi;
 fi;
 Add(ncom,l);

 # tag all conjugates
 for l in kconh[kp] do
 kconh[l]:=fail;
 od;

 fi;

 fi;

 fi; # if not already a conjugate

 od;

 # if invariance test needed
 else
 # get representatives of the fused complement classes
 l:=Filtered([1..Length(com)],i->kconh[i][1]=i);

 ncom:=[];
 for kp in l do
 m:=rec(representative:=
 ClosureSubgroup(b,z.cocycleToComplement(com[kp])));
 if comnorms<>fail then
 m.normalizer:=comnorms[kp];
 fi;
 Add(ncom,m);
 od;
 fi;
 com:=ncom;

 # take the preimages
 for k in com do

 Assert(1,ForAll(efunc,i->Image(i,k.representative)
 =k.representative));
 Add(ngrps,k.representative);
 if IsBound(k.normalizer) then
 if isTrueComnorm then
 Add(ngrpsnorms,k.normalizer);
 else
 Add(ngrpsnorms,Normalizer(k.normalizer,k.representative));
 fi;
 fi;
 od;
 fi;
 fi;
 od;

 fi;
 od;

 grps:=ngrps;
 grpsnorms:=ngrpsnorms;
 Info(InfoPcSubgroup,5,List(grps,Size),List(grpsnorms,Size));
 od;

 if isom<>fail then
 grps:=List(grps,j->PreImage(isom,j));
 if retnorm then
 grpsnorms:=List(grpsnorms,j->PreImage(isom,j));
 fi;
 fi;

 if retnorm then
 return [grps,grpsnorms];
 else
 return grps;
 fi;
end);

#############################################################################
##
#M CharacteristicSubgroups( <G> )
##
InstallMethod(CharacteristicSubgroups,"solvable, automorphisms",true,
 [IsGroup and IsSolvableGroup],0,
function(G)
local A,s;
 if AbelianRank(G)<5 then
 TryNextMethod();
 fi;
 A:=AutomorphismGroup(G);
 s:=SubgroupsSolvableGroup(G,rec(normal:=true,actions:=GeneratorsOfGroup(A)));
 return Filtered(s,x->IsCharacteristicSubgroup(G,x));
end);

#############################################################################
##
#M LatticeSubgroups(<G>) . . . . . . . . . . lattice of subgroups
##
InstallMethod(LatticeSubgroups,"elementary abelian extension",true,
 [IsGroup and IsFinite and CanComputeFittingFree],
 # want to be better than cyclic extension.
 1,
function(G)
local s,i,c,classes, lattice,map,GI;

 if Size(G)=1 or not IsSolvableGroup(G) then #or not CanEasilyComputePcgs(G) then
 TryNextMethod();
 fi;
 if not IsPcGroup(G) or IsPermGroup(G) then
 map:=IsomorphismPcGroup(G);
 GI:=Image(map,G);
 else
 map:=fail;
 GI:=G;
 fi;
 s:=SubgroupsSolvableGroup(GI,rec(retnorm:=true));
 classes:=[];
 for i in [1..Length(s[1])] do
 if map=fail then
 c:=ConjugacyClassSubgroups(G,s[1][i]);
 SetStabilizerOfExternalSet(c,s[2][i]);
 else
 c:=ConjugacyClassSubgroups(G,PreImage(map,s[1][i]));
 SetStabilizerOfExternalSet(c,PreImage(map,s[2][i]));
 fi;
 Add(classes,c);
 od;
 SortBy(classes, a -> Size(Representative(a)));

 # create the lattice
 lattice:=Objectify(NewType(FamilyObj(classes),IsLatticeSubgroupsRep),
 rec());
 lattice!.conjugacyClassesSubgroups:=classes;
 lattice!.group :=G;

 # return the lattice
 return lattice;

end);

# #############################################################################
# ##
# #M NormalSubgroups(<G>) . . . . . . . . . . list of normal subgroups
# ##
# InstallMethod(NormalSubgroups,"elementary abelian extension",true,
# [CanEasilyComputePcgs],0,
# function(G)
# local n;
# n:=SubgroupsSolvableGroup(G,rec(
# actions:=List(GeneratorsOfGroup(G),i->InnerAutomorphism(G,i)),
# normal:=true));
#
# # sort the normal subgroups according to their size
# SortBy(n, Size);
#
# return n;
# end);

#############################################################################
##
#F SizeConsiderFunction(<size>) returns auxiliary function for
## 'SubgroupsSolvableGroup' that allows one to discard all subgroups whose
## size is not divisible by <size>
##
InstallGlobalFunction(SizeConsiderFunction,function(size)
 return function(c,a,n,b,m)
 return IsInt(Size(a)/Size(n)*Size(b)*Size(m)/size);
 end;
end);

#############################################################################
##
#F ExactSizeConsiderFunction(<size>) returns auxiliary function for
## 'SubgroupsSolvableGroup' that allows one to discard all subgroups whose
## size is not <size>
##
InstallGlobalFunction(ExactSizeConsiderFunction,function(size)
 return function(c,a,n,b,m)
 local result;
 result:=IsInt(Size(a)/Size(n)*Size(b)*Size(m)/size)
 and not (Size(a)/Size(n)*Size(b))>size;
 return result;
 end;
end);

BindGlobal("ElementaryAbelianConsider",
function(c,a,n,b,m)
 return HasElementaryAbelianFactorGroup(a,n) and
 ForAll(GeneratorsOfGroup(a),x->ForAll(GeneratorsOfGroup(b),y->Comm(x,y)
 in m));
end);

Quelle grppclat.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.46 Sekunden (vorverarbeitet) ]