|
#############################################################################
##
## 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(<P>,<G>[,<dims>])
##
## compute the permutation action of <P> on the subspaces of the
## elementary abelian subgroup <G> of <P>. Returns
## a list [<subspaces>,<action>], where <subspaces> is a list of all the
## subspaces (as groups) and <action> a homomorphism from <P> in a
## permutation group, which is equal to the action homomrophism for the
## action of <P> 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);
[ Dauer der Verarbeitung: 0.13 Sekunden
(vorverarbeitet)
]
|
