|
#############################################################################
##
## 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 functions using the trivial-fitting paradigm.
## They are representation independent and will work for permutation and
## matrix groups
##
InstallGlobalFunction(AttemptPermRadicalMethod,function(G,T)
local R;
if not IsPermGroup(G) then return fail;fi;
if not (HasFittingFreeLiftSetup(G) or HasSolvableRadical(G)) then
# do not force radical method if it was not tried
return false;
fi;
# used in assertions
if ValueOption("usebacktrack")=true then return false;
elif ValueOption("useradical")=true then return true;fi;
R:=SolvableRadical(G);
# any chance to apply it, and not too small?
if Size(R)=1 or Size(G)<10000 then return false; fi;
if T="CENT" then
# centralizer/element conjugacy -- degree compares well with radical
# factor, but
return NrMovedPoints(G)^2>Size(G)/Size(R);
else
# Task not yet covered
return fail;
fi;
end);
InstallMethod(DoFFSS,"generic",IsIdenticalObj,[IsGroup and IsFinite,IsGroup],0,
function(G,U)
local ffs,pcisom,rest,kpc,k,x,ker,r,pool,i,xx,pregens,iso;
ffs:=FittingFreeLiftSetup(G);
pcisom:=ffs.pcisom;
#rest:=RestrictedMapping(ffs.factorhom,U);
if IsPermGroup(U) and AssertionLevel()>1 then
rest:=GroupHomomorphismByImages(U,Range(ffs.factorhom),GeneratorsOfGroup(U),
List(GeneratorsOfGroup(U),x->ImagesRepresentative(ffs.factorhom,x)));
else
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
rest:=GroupHomomorphismByImagesNC(U,Range(ffs.factorhom),GeneratorsOfGroup(U),
List(GeneratorsOfGroup(U),x->ImagesRepresentative(ffs.factorhom,x)));
RUN_IN_GGMBI:=false;
fi;
Assert(1,rest<>fail);
if HasRecogDecompinfoHomomorphism(ffs.factorhom) then
SetRecogDecompinfoHomomorphism(rest,RecogDecompinfoHomomorphism(ffs.factorhom));
fi;
# in radical?
if ForAll(MappingGeneratorsImages(rest)[2],IsOne) then
ker:=U;
# trivial radical
if Length(ffs.pcgs)=0 then
k:=[];
else
k:=InducedPcgsByGeneratorsNC(ffs.pcgs,GeneratorsOfGroup(U));
fi;
elif Length(ffs.pcgs)=0 then
# no radical
ker:=TrivialSubgroup(G);
k:=ffs.pcgs;
else
iso:=IsomorphismFpGroup(Image(rest,U));
pregens:=List(GeneratorsOfGroup(Range(iso)),x->
PreImagesRepresentative(rest,PreImagesRepresentative(iso,x)));
# evaluate relators
pool:=List(RelatorsOfFpGroup(Range(iso)),
x->MappedWord(x,FreeGeneratorsOfFpGroup(Range(iso)),pregens));
# divide off original generators
Append(pool,List(GeneratorsOfGroup(U),x->x/
MappedWord(UnderlyingElement(ImagesRepresentative(iso,ImagesRepresentative(ffs.factorhom,x))),FreeGeneratorsOfFpGroup(Range(iso)),pregens)));
iso:=IsomorphismFpGroup(Image(rest,U));
pregens:=List(GeneratorsOfGroup(Range(iso)),x->
PreImagesRepresentative(rest,PreImagesRepresentative(iso,x)));
# evaluate relators
pool:=List(RelatorsOfFpGroup(Range(iso)),
x->MappedWord(x,FreeGeneratorsOfFpGroup(Range(iso)),pregens));
# divide off original generators
Append(pool,List(GeneratorsOfGroup(U),x->x/
MappedWord(UnderlyingElement(ImagesRepresentative(iso,ImagesRepresentative(ffs.factorhom,x))),FreeGeneratorsOfFpGroup(Range(iso)),pregens)));
pool:=List(pool,x->ImagesRepresentative(pcisom,x));
kpc:=SubgroupNC(Image(pcisom),pool);
pool:=List(SmallGeneratingSet(kpc),x->PreImage(pcisom,x));
# normal closure
for x in pool do
for i in GeneratorsOfGroup(U) do
xx:=x^i;
k:=ImagesRepresentative(pcisom,xx);
if not k in kpc then
kpc:=ClosureSubgroupNC(kpc,k);
Add(pool,xx);
fi;
od;
od;
# inv:=RestrictedInverseGeneralMapping(rest);
# pregens:=List(SmallGeneratingSet(Image(rest)),
# x->ImagesRepresentative(inv,x));
# it:=CoKernelGensIterator(inv);
# kpc:=TrivialSubgroup(Image(pcisom));
# while not IsDoneIterator(it) do
# x:=NextIterator(it);
# pool:=[x];
# for x in pool do
# xx:=ImagesRepresentative(pcisom,x);
# if not xx in kpc then
# kpc:=ClosureGroup(kpc,xx);
# for i in pregens do
# Add(pool,x^i);
# od;
# fi;
# od;
# #Print("|pool|=",Length(pool),"\n");
# od;
SetSize(U,Size(Image(rest))*Size(kpc));
k:=InducedPcgs(FamilyPcgs(Image(pcisom)),kpc);
k:=List(k,x->PreImagesRepresentative(pcisom,x));
k:=InducedPcgsByPcSequenceNC(ffs.pcgs,k);
ker:=SubgroupNC(G,k);
SetSize(ker,Size(kpc));
fi;
SetPcgs(ker,k);
SetKernelOfMultiplicativeGeneralMapping(rest,ker);
if Length(ffs.pcgs)=0 then
r:=[1];
else
r:=Concatenation(k!.depthsInParent,[Length(ffs.pcgs)+1]);
fi;
AddNaturalHomomorphismsPool(U,ker,rest);
r:=rec(parentffs:=ffs,
rest:=rest,
radical:=ker,
ker:=ker,
pcgs:=k,
serdepths:=List(ffs.depths,y->First([1..Length(r)],x->r[x]>=y))
);
return r;
end);
InstallGlobalFunction(FittingFreeSubgroupSetup,function(G,U)
local ffs,cache,rest,ker,k,r;
ffs:=FittingFreeLiftSetup(G);
# result cached?
if not IsBound(U!.cachedFFS) then
cache:=[];
U!.cachedFFS:=cache;
else
cache:=U!.cachedFFS;
fi;
r:=First(cache,x->IsIdenticalObj(x[1],ffs));
if r<>fail then
return r[2];
fi;
if IsIdenticalObj(G,U) or GeneratorsOfGroup(G)=GeneratorsOfGroup(U) then
rest:=ffs.factorhom;
ker:=ffs.radical;
k:=ffs.pcgs;
r:=[1..Length(k)];
r:=rec(parentffs:=ffs,
rest:=rest,
radical:=ker,
ker:=ker,
pcgs:=k,
serdepths:=List(ffs.depths,y->First([1..Length(r)],x->r[x]>=y))
);
else
r:=DoFFSS(G,U);
fi;
k:=r.pcgs;
rest:=r.rest;
Add(cache,[ffs,r]); # keep
if Length(k)=0 then
SetSize(U,Size(Image(rest)));
else
SetSize(U,Product(RelativeOrders(k))*Size(Image(rest)));
fi;
return r;
end);
InstallGlobalFunction(SubgroupByFittingFreeData,function(G,gens,imgs,ipcgs)
local ffs,hom,U,rest,ker,r,p,l,i,depths,pcisom,subsz,pcimgs;
ffs:=FittingFreeLiftSetup(G);
# get back to initial group -- dont induce of induce
while IsBound(ffs.inducedfrom) do
ffs:=ffs.inducedfrom;
od;
hom:=ffs.factorhom;
if Length(ffs.pcgs)=0 then
if Length(ipcgs)>0 then
Error("pc elements arise suddenly");
fi;
depths:=[];
elif not IsGeneralPcgs(ipcgs) then
ipcgs:=InducedPcgsByPcSequenceNC(ffs.pcgs,ipcgs);
fi;
if Length(ipcgs)>0 then
if not HasOneOfPcgs(ipcgs) then
SetOneOfPcgs(ipcgs,One(G));
fi;
depths:=IndicesEANormalSteps(ipcgs);
else
depths:=[];
fi;
# transfer the IndicesEANormalSteps
if ffs.pcgs<>ipcgs and HasIndicesEANormalSteps(ffs.pcgs) then
U:=IndicesEANormalSteps(ffs.pcgs);
if IsBound(ipcgs!.depthsInParent) then
r:=ipcgs!.depthsInParent;
else
r:=List(ipcgs,x->DepthOfPcElement(ffs.pcgs,x));
fi;
l:=[];
for i in U{[1..Length(U)-1]} do # last one is length+1
p:=PositionProperty(r,x->x>=i);
if p<>fail and p<=Length(ipcgs) and not p in l then
Add(l,p);
fi;
od;
Add(l,Length(ipcgs)+1);
SetIndicesEANormalSteps(ipcgs,l);
fi;
pcimgs:=List(ipcgs,x->ImagesRepresentative(ffs.pcisom,x));
ker:=SubgroupNC(G,List(MinimalGeneratingSet(Group(pcimgs,One(Range(ffs.pcisom)))),
x->PreImagesRepresentative(ffs.pcisom,x)));
SetPcgs(ker,ipcgs);
if Length(ipcgs)=0 then
SetSize(ker,1);
else
SetPcgs(ker,ipcgs);
SetSize(ker,Product(RelativeOrders(ipcgs)));
fi;
subsz:=Size(Group(imgs,One(Image(ffs.factorhom))))*Size(ker);
U:=SubgroupNC(G,Concatenation(gens,GeneratorsOfGroup(ker)));
SetSize(U,subsz);
gens:=Concatenation(gens,ipcgs);
imgs:=Concatenation(imgs,List(ipcgs,x->One(Range(hom))));
if IsPermGroup(U) and AssertionLevel()>1 then
rest:=GroupHomomorphismByImages(U,Range(hom),gens,imgs);
else
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
rest:=GroupHomomorphismByImagesNC(U,Range(hom),gens,imgs);
RUN_IN_GGMBI:=false;
fi;
Assert(1,rest<>fail);
if HasRecogDecompinfoHomomorphism(hom) then
SetRecogDecompinfoHomomorphism(rest,RecogDecompinfoHomomorphism(hom));
fi;
SetKernelOfMultiplicativeGeneralMapping(rest,ker);
if Length(ipcgs)=0 then
r:=[Length(ffs.pcgs)+1];
elif IsBound(ipcgs!.depthsInParent) then
r:=Concatenation(ipcgs!.depthsInParent,[Length(ffs.pcgs)+1]);
else
r:=Concatenation(List(ipcgs,x->DepthOfPcElement(ffs.pcgs,x)),
[Length(ffs.pcgs)+1]);
fi;
r:=rec(parentffs:=ffs,
rest:=rest,
radical:=ker,
ker:=ker,
pcgs:=ipcgs,
serdepths:=List(ffs.depths,y->First([1..Length(r)],x->r[x]>=y))
);
U!.cachedFFS:=[[ffs,r]];
# FittingFreeLiftSetup for U, if correct
if Size(SolvableRadical(Image(rest,U)))=1 then
if ipcgs=MappingGeneratorsImages(ffs.pcisom)[1] then
pcisom:=ffs.pcisom;
else
pcisom:=pcimgs;
if Length(ipcgs)>0 then
# work around error for special trivial group.
r:=Group(ipcgs,OneOfPcgs(ipcgs));
else
r:=SubgroupNC(G,ipcgs);
fi;
RUN_IN_GGMBI:=true;
pcisom:=GroupHomomorphismByImagesNC(r,
SubgroupNC(Range(ffs.pcisom),pcisom),
ipcgs,pcisom);
RUN_IN_GGMBI:=false;
fi;
r:=rec(inducedfrom:=ffs,
pcgs:=ipcgs,
depths:=depths,
pcisom:=pcisom,
radical:=ker,
factorhom:=rest
);
SetFittingFreeLiftSetup(U,r);
AddNaturalHomomorphismsPool(U,ker,rest);
fi;
return U;
end);
InstallGlobalFunction(FittingFreeElementarySeries,function(arg)
local G,A,wholesocle,ff,r,ser,fser,hom,q,s,d,act,o,i,j,a,perm,k;
G:=arg[1];
if Length(arg)>1 then
A:=arg[2];
wholesocle:=arg[3];
else
A:=TrivialSubgroup(G);
wholesocle:=false;
fi;
ff:=FittingFreeLiftSetup(G);
if IsSubset(G,A) then
# just use inner automorphisms...
A:=Group(List(GeneratorsOfGroup(G),x->InnerAutomorphismNC(G,x)));
fi;
r:=ff.radical;
if Size(r)=1 then
ser:=[r];
else
ser:=InvariantElementaryAbelianSeries(r,GeneratorsOfGroup(A));
fi;
if Size(r)<Size(G) then
ser:=Reversed(ser);
hom:=ff.factorhom;
q:=Image(hom);
s:=Socle(q);
d:=DirectFactorsFittingFreeSocle(q);
if wholesocle<>true then
# orbits on socle components
act:=List(GeneratorsOfGroup(A),x->InducedAutomorphism(hom,x));
o:=Orbits(Group(act,IdentityMapping(q)),d,
function(u,a) return Image(a,u);end);
fser:=[TrivialSubgroup(q)];
for i in o do
a:=Last(fser);
for j in i do
a:=ClosureGroup(a,j);
od;
Add(fser,a);
od;
else
fser:=[TrivialSubgroup(q),s];
fi;
for i in fser{[2..Length(fser)]} do
Add(ser,PreImage(hom,i));
od;
#Print("A",List(ser,Size),"\n");
# pker/S*
perm:=ActionHomomorphism(q,d,"surjective");
k:=PreImage(hom,KernelOfMultiplicativeGeneralMapping(perm));
if Size(s)<Size(KernelOfMultiplicativeGeneralMapping(perm)) then
s:=Last(ser);
hom:=NaturalHomomorphismByNormalSubgroupNC(k,s);
q:=Image(hom);
act:=List(GeneratorsOfGroup(A),x->InducedAutomorphism(hom,x));
fser:=InvariantElementaryAbelianSeries(q,act);
for i in fser{[1..Length(fser)-1]} do
Add(ser,PreImage(hom,i));
od;
fi;
#Print("B",List(ser,Size),"\n");
if Size(k)<Size(G) then
# G/Pker, recursive
hom:=NaturalHomomorphismByNormalSubgroupNC(G,k);
q:=Image(hom);
act:=List(GeneratorsOfGroup(A),x->InducedAutomorphism(hom,x));
A:=Group(act,IdentityMapping(q));
fser:=FittingFreeElementarySeries(q,A,wholesocle);
for i in fser{[Length(fser)-1,Length(fser)-2..1]} do
Add(ser,PreImage(hom,i));
od;
fi;
ser:=Reversed(ser);
fi;
#Print(List([1..Length(ser)-1],x->Size(ser[x])/Size(ser[x+1])),"\n");
return ser;
end);
#############################################################################
##
#M \in( <e>,<G> ) . . . . . . . . . . . . . . using TF method
##
InstallMethod( \in, "TF method, use tree",IsElmsColls,
[ IsMultiplicativeElementWithInverse,
IsGroup and IsFinite and HasFittingFreeLiftSetup], OverrideNice,
function(e, G)
local f;
f:=FittingFreeLiftSetup(G);
# permutation groups don't need the .csi component
if not IsBound(f.csi) then TryNextMethod();fi;
return e in f.csi.recog;
end );
#############################################################################
##
#M SolvableRadical( <G> ) . . . . . . . . . . . . . . using TF method
##
InstallMethod( SolvableRadical, "TF method, use tree",
[ IsGroup and IsFinite and HasFittingFreeLiftSetup], OverrideNice,
function(G)
local f;
f:=FittingFreeLiftSetup(G);
if not IsBound(f.radical) then TryNextMethod();fi;
return f.radical;
end );
# We will be in the situation that an IGS has been corrected only on the
# lowest level, i.e. the only obstacle to being an IGS is on the lowest
# level. Thus the situation is that of a vector space and we do not need to
# consider commutators and powers, but simply do a Gaussian elimination.
InstallGlobalFunction(TFMakeInducedPcgsModulo,function(pcgs,gens,ignoredepths)
local i,j,d,igs,g,a,l,al;
d:=[];
igs:=[];
l:=[];
for g in gens do
a:=DepthAndLeadingExponentOfPcElement(pcgs,g); al:=a[2]; a:=a[1];
#Print(a,"\n");
if not a in ignoredepths then
j:=1;
while j<=Length(d) do
if a<d[j] then
#insert
for i in [Length(d),Length(d)-1..j] do
d[i+1]:=d[i];
igs[i+1]:=igs[i];
l[i+1]:=l[i];
od;
d[j]:=a;
igs[j]:=g;
l[j]:=al;
j:=Length(d)+2; # pop
elif a=d[j] then
# conflict--divide off
g:=igs[j]/g^(l[j]/al mod RelativeOrders(pcgs)[a]);
a:=DepthAndLeadingExponentOfPcElement(pcgs,g); al:=a[2]; a:=a[1];
#Print("change ",a,"\n");
if a=d[j] then Error("clash!");fi;
if a in ignoredepths then
j:=Length(d)+2; # force ignore
fi;
else
j:=j+1;
fi;
od;
if j<Length(d)+2 then #we did not insert
Add(igs,g);
Add(d,a);
Add(l,al);
fi;
fi;
od;
IsRange(d);
#Print("Made IGS ",d," lendiff ",Length(gens)-Length(d),"\n");
return igs;
end);
# Orbit functions for multi-stage calculations
InstallGlobalFunction(OrbitsRepsAndStabsVectorsMultistage,
function(pcgs,pcgsimgs,pcisom,solvsz,solvtriv,gens,imgs,fgens,
factorhom,gpsz,actfun,domain)
local stabilizergen,st,stabrsub,stabrsubsz,ratio,subsz,sz,vp,stabrad,
stabfacgens,s,orblock,orb,rep,b,p,repwords,orpo,i,j,k,repword,
imgsinv,img,stabfac,reps,stage,genum,orbstabs,stabfacimg,
fgrp,solsubsz,failcnt,stabstack,relo,orbitseed;
orbitseed:=ValueOption("orbitseed");
stabilizergen:=function()
local im,i,fe,gpe;
if stage=1 then
Error("solv stage is gone");
#stabilizer in radical
if IsRecord(st) then st:=st.left/st.right;fi;
fe:=ImagesRepresentative(pcisom,st);
if not fe in stabrsub then
stabrsub:=ClosureGroup(stabrsub,fe);
stabrsubsz:=Size(stabrsub);
subsz:=stabrsubsz*Size(stabfac);
ratio:=gpsz/subsz/Length(orb);
if ratio=1 then vp:=Length(orb);fi;
Add(stabrad,st);
else
failcnt:=failcnt+1;
if IsInt(failcnt/50) then
Info(InfoFitFree,5,"failed ",failcnt," times, ratio ",EvalF(ratio),
", ",Length(stabrad)," gens\n");
fi;
fi;
else
# in radical factor, still it could be the identity
if Length(repword)>0 then
# build the factor group element
fe:=One(Image(factorhom));
for i in repword do
fe:=fe*fgens[i];
od;
for i in Reversed(repwords[p]) do
fe:=fe/fgens[i];
od;
if not fe in stabfac then
# not known -- add to generators
Add(stabfacimg,fe);
if IsRecord(st) then
if st.left<>fail then
Error("cannot happen");
st:=st.left/st.right;
else
gpe:=One(Source(factorhom));
for i in repwords[st.vp] do
gpe:=gpe*gens[i];
od;
gpe:=gpe*gens[st.genumr];
for i in Reversed(repwords[st.right]) do
gpe:=gpe/gens[i];
od;
# vector image under st
im:=orb[1];
for i in repwords[st.vp] do
im:=actfun(im,imgs[i]);
od;
im:=actfun(im,imgs[st.genumr]);
for i in Reversed(repwords[st.right]) do
im:=actfun(im,imgsinv[i]);
od;
fi;
# make sure st really stabilizes by dividing off solvable bit
st:=gpe/reps[orpo[Position(domain,im)]];
fi;
Add(stabfacgens,st);
stabfac:=ClosureGroup(stabfac,fe);
subsz:=stabrsubsz*Size(stabfac);
ratio:=gpsz/subsz/Length(orb);
if ratio=1 then vp:=Length(orb);fi;
Assert(1,GeneratorsOfGroup(stabfac)=stabfacimg);
fi;
fi;
fi;
# radical stabilizer element. TODO: Use PCGS to remove
# duplicates
end;
fgrp:=Group(fgens,One(Range(factorhom)));
imgsinv:=List(imgs,Inverse);
# now compute orbits, being careful to get stabilizers in steps
orbstabs:=[];
# use positions in bit list to know which ones are done
sz:=Length(domain);
b:=BlistList([1..sz],[]);
while sz>0 do
failcnt:=0;
if orbitseed<>fail then
# get seed number
p:=Position(domain,orbitseed);
else
# still orbits left to do
p:=Position(b,false);
fi;
orb:=[domain[p]];
orpo:=[];
orpo[p]:=1;
b[p]:=true;
sz:=sz-1;
reps:=[One(Source(factorhom))];
stabstack:=[];
stabrad:=[];
stabrsub:=solvtriv;
stabrsubsz:=Size(solvtriv);
stabfac:=TrivialSubgroup(fgrp);
subsz:=stabrsubsz*Size(stabfac);
stabfacgens:=[];
stabfacimg:=[];
repwords:=[[]];
# now do a two-stage orbit algorithm. first solvable, then via the
# factor group. Both times we can check that we have the correct orbit.
# ratio 1: full orbit/stab known, ratio <2 stab cannot grow any more.
ratio:=5;
vp:=1; # position in orbit to process
# solvable iteration
stage:=1;
for genum in [Length(pcgs),Length(pcgs)-1..1] do
relo:=RelativeOrders(pcisom!.sourcePcgs)[
DepthOfPcElement(pcisom!.sourcePcgs,pcgs[genum])];
img:=actfun(orb[1],pcgsimgs[genum]);
repword:=repwords[1];
p:=Position(domain,img);
if p>Length(b) or not b[p] then
# new orbit images
vp:=Length(orb)*(relo-1);
sz:=sz-vp;
for j in [1..vp] do
img:=actfun(orb[j],pcgsimgs[genum]);
p:=Position(domain,img);
b[p]:=true;
Add(orb,img);
orpo[p]:=Length(orb);
Add(reps,reps[j]*pcgs[genum]);
Add(repwords,repword);
od;
else
rep:=pcgs[genum]/reps[orpo[p]];
#if Order(rep)=1 then Error("HUH4"); fi;
Add(stabrad,rep);
#Print("increased ",stabrsubsz," by ",relo,"\n");
stabrsubsz:=stabrsubsz*relo;
subsz:=stabrsubsz;
ratio:=gpsz/subsz/Length(orb);
fi;
od;
stabrad:=Reversed(stabrad);
subsz:=stabrsubsz;
if solvsz>subsz*Length(orb) then
Error("processing stabstack solvable ", Length(stabrad));
s:=1;
while solvsz<>subsz*Length(orb) do
vp:=stabstack[s][1];
genum:=stabstack[s][2];
img:=orb[vp]*pcgsimgs[genum];
rep:=reps[vp]*pcgs[genum];
repword:=repwords[vp];
p:=Position(domain,img);
p:=orpo[p];
#st:=rep/reps[p];
st:=rec(left:=rep,right:=reps[p]);
stabilizergen();
s:=s+1;
od;
Info(InfoFitFree,5,"processed solvable ",s," from ",Length(stabstack));
fi;
subsz:=stabrsubsz;
solsubsz:=subsz;
orblock:=Length(orb);
Info(InfoFitFree,5,"solvob=",orblock);
# nonsolvable iteration: We act on orbits
stage:=2;
# ratio 1: full orbit/stab known, ratio <2 stab cannot grow any more.
ratio:=5;
vp:=1;
while vp<=Length(orb) do
for genum in [1..Length(gens)] do
img:=actfun(orb[vp],imgs[genum]);
repword:=Concatenation(repwords[vp],[genum]);
p:=Position(domain,img);
if not b[p] then
# new orbit image
Add(orb,img);
orpo[p]:=Length(orb);
#if rep<>fail then Add(reps,rep); fi;
Add(repwords,repword);
b[p]:=true;
for j in [1..orblock-1] do
img:=actfun(orb[vp+j],imgs[genum]);
p:=Position(domain,img);
if b[p] then Error("duplicate!");fi;
Add(orb,img);
orpo[p]:=Length(orb);
#if IsBound(reps[vp+j]) then
# Add(reps,reps[vp+j]*gens[genum]);
#fi;
# repwordslso needs to change!
Add(repwords,Concatenation(repwords[vp+j],[genum]));
b[p]:=true;
od;
sz:=sz-orblock;
ratio:=gpsz/subsz/Length(orb);
if ratio=1 then vp:=Length(orb);fi;
elif ratio>=2 then
# old orbit element -- stabilizer generator
# if ratio <2 the stabilizer cannot grow any more
p:=orpo[p];
st:=rec(left:=fail,vp:=vp,genumr:=genum,right:=p);
stabilizergen();
fi;
od;
vp:=vp+orblock; # jump in steps
od;
s:=1;
subsz:=stabrsubsz*Size(stabfac);
if gpsz<>subsz*Length(orb) then
Error("should not happen nonslv stabstack");
fi;
Info(InfoFitFree,4,"orblen=",Length(orb)," blocked ",orblock," left:",
sz," len=", Length(stabrad)," ",Length(stabfacgens));
#Assert(2,ForAll(GeneratorsOfGroup(stabsub),i->Comm(i,h*rep) in NT));
s:=rec(rep:=orb[1],len:=Length(orb),stabradgens:=stabrad,
stabfacgens:=stabfacgens,stabfacimgs:=stabfacimg,
stabrsub:=stabrsub,stabrsubsz:=stabrsubsz,subsz:=subsz
);
if orbitseed<>fail then
s.gens:=gens;
s.fgens:=fgens;
s.orbit:=orb;
s.orblock:=orblock;
s.reps:=reps;
s.repwords:=repwords;
sz:=0; # force bailout
else
# by construction, we seed each orbit with its smallest element
Assert(1,orb[1]=Minimum(orb));
fi;
Add(orbstabs,s);
od;
return orbstabs;
end);
InstallGlobalFunction(OrbitMinimumMultistage,
function(pcgs,pcgsimgs,gens,imgs,fgens,actfun,seed,orblen,stops)
#was: OrbitMinimumMultistage:=function(pcgs,pcgsimgs,gens,imgs,fgens,actfun,seed,orblen,stops)
local sel,orb,dict,reps,repwords,vp,img,cont,minpo,genum,rep,repword,p,
orblock,s,i,j;
orb:=[seed];
p:=DefaultHashLength;
DefaultHashLength:=4*orblen; # remember that we might need all orbit elements
if IsRowVector(seed) then
dict:=NewDictionary(seed,true,DefaultField(seed)^Length(seed));
else
dict:=NewDictionary(seed,true);
fi;
DefaultHashLength:=p;
AddDictionary(dict,seed,Length(orb));
reps:=[One(pcgs[1])];
repwords:=[[]];
# now do a two-stage orbit algorithm. first solvable, then via the
# factor group. Both times we can check that we have the correct orbit.
vp:=1;
img:=fail;
cont:=true;
minpo:=fail;
while vp<=Length(orb) and cont do
for genum in [Length(pcgs),Length(pcgs)-1..1] do
img:=actfun(orb[vp],pcgsimgs[genum]);
rep:=reps[vp]*pcgs[genum];
repword:=repwords[vp];
p:=LookupDictionary(dict,img);
if p=fail then
# new orbit element
Add(orb,img);
AddDictionary(dict,img,Length(orb));
Add(reps,rep);
Add(repwords,repword);
if img in stops then
minpo:=Length(orb);
cont:=false;
elif Length(orb)>=orblen then
cont:=false;
fi;
fi;
od;
vp:=vp+1;
od;
#if Length(orb)>Length(Set(orb)) then Error("EH");fi;
orblock:=Length(orb);
Info(InfoFitFree,5,"solvob=",orblock);
# nonsolvable iteration: We act on orbits
# these are the proper actors
sel:=Filtered([1..Length(gens)],x->Order(gens[x])>1);
vp:=1;
while vp<=Length(orb) and cont do
for genum in sel do
img:=actfun(orb[vp],imgs[genum]);
repword:=Concatenation(repwords[vp],[genum]);
p:=LookupDictionary(dict,img);
if p=fail then
# new orbit image
Add(orb,img);
AddDictionary(dict,img,Length(orb));
Add(repwords,repword);
if img in stops then
minpo:=Length(orb);
cont:=false;
fi;
for j in [1..orblock-1] do
img:=actfun(orb[vp+j],imgs[genum]);
Add(orb,img);
AddDictionary(dict,img,Length(orb));
Add(repwords,Concatenation(repwords[vp+j],[genum]));
if img in stops then
minpo:=Length(orb);
cont:=false;
fi;
od;
if Length(orb)>=orblen then cont:=false;fi;
fi;
od;
vp:=vp+orblock; # jump in steps
od;
if minpo=fail then
# guarantee minimum
p:=orb[1];minpo:=1;
for j in [2..Length(orb)] do
if orb[j]<p then
minpo:=j;p:=orb[j];
fi;
od;
fi;
# now find rep mapping to minimum
if Length(gens)=0 then
p:=One(pcgs[1]);
s:=();
else
p:=One(gens[1]);
s:=One(fgens[1]);
fi;
for i in repwords[minpo] do
p:=p*gens[i];
s:=s*fgens[i];
od;
i:=minpo mod orblock;
if i=0 then i:=orblock;fi;
p:=reps[i]*p;
p:=rec(elm:=p,felm:=s,min:=orb[minpo]);
return p;
end);
BindGlobal("SylowViaRadical",function(G,prime)
local ser,hom,s,fphom,sf,sg,sp,fp,d,head,mran,nran,mpcgs,ocr,len,pcgs,gens;
ser:=FittingFreeLiftSetup(G);
pcgs:=ser.pcgs;
len:=Length(pcgs);
hom:=ser.factorhom;
s:=SylowSubgroup(Image(hom),prime);
fphom:=IsomorphismFpGroup(s);
fp:=Image(fphom);
sf:=List(GeneratorsOfGroup(Image(fphom)),x->PreImagesRepresentative(fphom,x));
sg:=List(sf,x->PreImagesRepresentative(hom,x));
sp:=[];
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=GroupGeneralMappingByImagesNC(Group(sg,One(G)),fp,sg,
GeneratorsOfGroup(fp));
RUN_IN_GGMBI:=false;
for d in [2..Length(ser.depths)] do
mran:=[ser.depths[d-1]..len];
nran:=[ser.depths[d]..len];
head:=InducedPcgsByPcSequenceNC(pcgs,pcgs{mran});
mpcgs:=head mod
InducedPcgsByPcSequenceNC(pcgs,pcgs{nran});
if RelativeOrders(mpcgs)[1]=prime then
if d=Length(ser.depths) then
# last step, no presentation needed
Append(sp,mpcgs);
else
# extend presentation
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=LiftFactorFpHom(fphom,Source(fphom),false,mpcgs);
RUN_IN_GGMBI:=false;
fp:=Image(fphom);
sp:=Concatenation(sp,mpcgs);
fi;
else
ocr:=rec(group:=Group(Concatenation(head,sg,sp)),modulePcgs:=mpcgs);
ocr.factorfphom:=fphom;
OCOneCocycles(ocr,true);
gens:=GeneratorsOfGroup(ocr.complement);
sg:=gens{[1..Length(sg)]};
sp:=gens{[Length(sg)+1..Length(gens)]};
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=GroupGeneralMappingByImagesNC(ocr.complement,fp,gens,
GeneratorsOfGroup(fp));
RUN_IN_GGMBI:=false;
fi;
od;
return SubgroupByFittingFreeData(G,sg,sf,InducedPcgsByPcSequenceNC(pcgs,sp));
end);
InstallMethod(DirectFactorsFittingFreeSocle,"generic",true,
[IsGroup and IsFinite],0,
function(G)
local s,o,a,n,d,f,fn,j,b,i;
s:=Socle(G);
#try to split first according to orbits
if IsPermGroup(G) then
o:=Orbits(s,MovedPoints(s));
f:=[s]; #prefactors
for i in o do
fn:=[];
for j in f do
a:=Stabilizer(j,i,OnTuples);
if Size(a)=Size(j) or Size(a)=1 then
Add(fn,j);
else
b:=Centralizer(j,a);
Add(fn,a);
Add(fn,b);
fi;
od;
f:=fn;
od;
else
f:=[s];
fi;
d:=[];
for i in f do
if IsNonabelianSimpleGroup(i) then
Add(d,i);
else
n:=Filtered(NormalSubgroups(i),x->Size(x)>1);
# if G is not fitting-free it has a proper normal subgroup of
# prime-power order
if ForAny(n,IsPGroup) then
return fail;
fi;
n:=Filtered(n,IsNonabelianSimpleGroup);
Append(d,n);
fi;
od;
return d;
end);
BindGlobal("ClosureGroupQuick",function(G,U,V)
local o,C;
C:=SubgroupNC(G,Concatenation(GeneratorsOfGroup(U),GeneratorsOfGroup(V)));
o:=List([1..100],x->Order(PseudoRandom(C)));
Add(o,Size(U));
Add(o,Size(V));
if IsPermGroup(G) then
Append(o,List(Orbits(C,MovedPoints(G)),Length));
fi;
o:=Lcm(o);
if PrimeDivisors(Size(G))=PrimeDivisors(o) then
# all primes in -- useless
return G;
fi;
return C;
end);
# the ``all-halls'' function by brute force Sylow-combination search
BindGlobal("Halleen",function(arg)
local G,gp,p,r,s,c,i,a,prime,sy,k,b,dc,H,e,j,forbid;
G:=arg[1];
gp:=PrimeDivisors(Size(G));
if Length(arg)>1 then
r:=arg[2];
forbid:=Difference(gp,r);
p:=Intersection(gp,r);
else
forbid:=[];
p:=gp;
fi;
r:=List(p,x->[[x],[SylowSubgroup(G,x)]]); # real halls
s:=ShallowCopy(r); # real and potential halls to extend
c:=Combinations(p);
c:=Filtered(c,x->Length(x)>1 and Length(x)<Length(gp));
SortBy(c, Length);
for i in c do
a:=[];
# now build all new groups by extending the groups that were obtained
# for one prime less. We exclude the smallest prime, as it tends to have
# the largest sylow
prime:=i[1];
sy:=SylowSubgroup(G,prime);
k:=i{[2..Length(i)]};
# b are the groups constructed using the other primes
b:=First(s,x->x[1]=k);
if b=fail then b:=[];
else b:=b[2]; fi;
# those that already contain the prime Sylow just go on
e:=Filtered(b,x->1=Gcd(Index(G,x),prime));
# are any of these actually proper hall?
for H in e do
if IsSubset(i,Factors(Size(H))) then
Add(a,H);
fi;
od;
# the rest should be extended
b:=Filtered(b,x->1<Gcd(Index(G,x),prime));
Info(InfoLattice,1,"Try ",i," from ",k," ",Length(e)," ",Length(b));
for j in b do
dc:=DoubleCosetRepsAndSizes(G,Normalizer(G,sy),Normalizer(G,j));
#Print(Length(dc)," double cosets\n");
for k in dc do
#H:=ClosureGroup(j,sy^k[1]);
H:=ClosureGroupQuick(G,j,sy^k[1]);
# discard whole group and those that have all primes
if Index(G,H)>1 and not ForAll(gp,x->IsInt(Size(H)/x))
and not ForAny(forbid,x->IsInt(Size(H)/x)) then
if ForAll(e,x->H<>x) and
ForAll(e,x->RepresentativeAction(G,H,x)=fail) then
Add(e,H);
if IsSubset(i,Factors(Size(H))) then
if Length(Intersection(Factors(Index(G,H)),i))=0 then
Info(InfoLattice,2,"Found Hall",i," ",Size(H));
else
Info(InfoLattice,2,"Found ",i," ",Size(H));
fi;
Add(a,H);
else
Info(InfoLattice,2,"Too large ",i," ",Size(H));
fi;
fi;
fi;
od;
od;
Add(s,[i,e]);
if Length(a)>0 then
Add(r,[i,a]);
fi;
od;
return r;
end);
BindGlobal("HallsFittingFree",function(G,pi)
local s,d,c,act,o,i,j,h,p,hf,img,n,k,ns,all,hl,hcomp,
shall,t,thom,b,ntb,hom,dser,pcgs,
fphom,fp,gens,imgs,ocr,elabser,cgens,a,kim,r,z;
# get elementary abelian series from -> to
elabser:=function(from,to)
local ser,a,p;
ser:=[from];
while Size(from)>Size(to) do
a:=from;
from:=DerivedSubgroup(a);
if Size(from)=Size(a) then
# nonsolvable case
return ser;
fi;
p:=Factors(Index(a,from))[1];
from:=ClosureGroup(from,List(GeneratorsOfGroup(a),x->x^p));
Assert(2,HasElementaryAbelianFactorGroup(a,from) and Index(a,from)>1);
Add(ser,from);
od;
return ser;
end;
# needs to go higher
pi:=Set(pi);
if ForAny(pi,x->not IsPrimeInt(x)) then
Error("pi must be a set of primes");
fi;
pi:=Filtered(pi,x->IsInt(Size(G)/x));
if Length(pi)=0 then
return [TrivialSubgroup(G)];
elif false and Length(pi)=1 then
return [SylowSubgroup(G,pi[1])];
elif pi=PrimeDivisors(Size(G)) then
return [G];
fi;
s:=Socle(G);
d:=DirectFactorsFittingFreeSocle(G);
c:=[]; # conjugation info
act:=ActionHomomorphism(G,d);
t:=KernelOfMultiplicativeGeneralMapping(act);
img:=Image(act);
# compute Hall in factor
hf:=HallViaRadical(img,pi);
Info(InfoLattice,1,"Permact factor:",Length(hf)," hall subgroups");
if Length(hf)=0 then
# nothing in the factor
return [];
fi;
# compute b such that b/s is hall in t/s
thom:=NaturalHomomorphismByNormalSubgroupNC(t,s);
b:=HallSubgroup(Image(thom),pi);
b:=PreImage(thom,b);
ntb:=Normalizer(t,b); # likely equal to t or of small index, thus harmless
# also compute halls for socle
o:=Orbits(Image(act),[1..Length(d)]);
hl:=[];
for i in o do
p:=Intersection(Factors(Size(d[i[1]])),pi);
if Length(p)=0 then
h:=[,[TrivialSubgroup(d[i[1]])]];
else
h:=Halleen(d[i[1]],p);
h:=First(h,x->x[1]=p);
fi;
# TODO: Reduce via B-action
if h=fail then
return [];
fi;
h:=h[2];
Info(InfoLattice,2,"Socle factor size ",Size(d[i[1]]),": ",Length(h),
" Hall subgroups");
for j in i do
hl[j]:=Length(h);
od;
n:=List(h,x->Normalizer(d[i[1]],x));
c[i[1]]:=rec(orbit:=i,orbitpos:=1,rep:=One(G),component:=d[i[1]],hall:=h,
norm:=n);
for j in [2..Length(i)] do
c[i[j]]:=rec(orbit:=i,orbitpos:=j,
rep:=PreImagesRepresentative(act,
RepresentativeAction(Image(act),i[1],i[j])),
component:=d[i[j]],hall:=h, norm:=n);
od;
od;
# now form all halls in s
shall:=[];
for p in Cartesian(List(hl,x->[1..x])) do
h:=TrivialSubgroup(G);
hcomp:=[];
ns:=TrivialSubgroup(G);
for i in [1..Length(d)] do
hcomp[i]:=c[i].hall[p[i]]^c[i].rep;
h:=ClosureGroup(h,hcomp[i]);
ns:=ClosureGroup(ns,c[i].norm[p[i]]^c[i].rep);
od;
Add(shall,rec(hall:=h,hcomp:=hcomp,ns:=ns));
od;
if Length(shall)=0 then
return [];
fi;
Info(InfoLattice,1,Length(shall)," in socle");
# get elementary abelian series from ntb to b
dser:=elabser(ntb,b);
pcgs:=List([2..Length(dser)],x->ModuloPcgs(dser[x-1],dser[x]));
all:=[];
# run through halls in factor (and correct)
for i in hf do
if Size(i)>1 then
# replace hf's by complements
fphom:=IsomorphismFpGroup(i);
fp:=Range(fphom);
gens:=MappingGeneratorsImages(fphom);
imgs:=gens[2];gens:=gens[1];
gens:=List(gens,x->PreImagesRepresentative(act,x));
# adapt to normalize B
gens:=List(gens,x->x/RepresentativeAction(t,b^x,b));
# now do complements one by one
for j in [1..Length(pcgs)] do
h:=ClosureGroup(dser[j],gens);
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=GroupGeneralMappingByImagesNC(h,fp,
Concatenation(GeneratorsOfGroup(dser[j]),gens),
Concatenation(List(GeneratorsOfGroup(dser[j]),x->One(fp)),imgs));
RUN_IN_GGMBI:=false;
ocr:=rec(group:=h,modulePcgs:=pcgs[j],
factorfphom:=fphom);
OCOneCocycles(ocr,true);
gens:=GeneratorsOfGroup(ocr.complement);
od;
# lift presentation with b/s, if necessary
if Size(b)>Size(s) then
h:=ClosureGroup(b,gens);
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=GroupGeneralMappingByImagesNC(h,fp,
Concatenation(GeneratorsOfGroup(b),gens),
Concatenation(List(GeneratorsOfGroup(b),x->One(fp)),imgs));
RUN_IN_GGMBI:=false;
# get elementary abelian series from b to s
dser:=elabser(b,s);
pcgs:=List([2..Length(dser)],x->ModuloPcgs(dser[x-1],dser[x]));
for j in pcgs do
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=LiftFactorFpHom(fphom,Source(fphom),false,j);
RUN_IN_GGMBI:=false;
od;
gens:=MappingGeneratorsImages(fphom);
imgs:=gens[2];gens:=gens[1];
fp:=Image(fphom);
fi;
else
# trivial in factor -- continue with b
hom:=NaturalHomomorphismByNormalSubgroupNC(b,s);
fphom:=IsomorphismFpGroup(Image(hom));
fp:=Image(fphom);
gens:=MappingGeneratorsImages(fphom);
imgs:=gens[2];gens:=gens[1];
gens:=List(gens,x->PreImagesRepresentative(hom,x));
fi;
# now run through the candidates for Hall in S
for j in shall do
k:=j.hall;
# normalize k -- correct gens
cgens:=[];
h:=1;
while cgens<>fail and h<=Length(gens) do
a:=gens[h];
kim:=List(j.hcomp,x->x^a);
# reindex
kim:=kim{ListPerm(Image(act,a)^-1,Length(d))};
z:=1;
while a<>fail and z<=Length(d) do
r:=RepresentativeAction(d[z],kim[z],j.hcomp[z]);
if r<>fail then
a:=a*r;
else
a:=fail;
fi;
z:=z+1;
od;
if a<>fail then
Add(cgens,a);
else
cgens:=fail;
fi;
h:=h+1;
od;
if cgens<>fail and ForAll(cgens,IsOne) then
# degenerate case -- nothing in the factor, just use hall in s
Add(all,j.hall);
elif cgens<>fail then
# The s-class of k is fixed and cgens are generators for N_C(K),
# corresponding to gens (and imgs).
dser:=elabser(j.ns,j.hall);
pcgs:=List([2..Length(dser)],x->ModuloPcgs(dser[x-1],dser[x]));
# now do complement to NS(k)/k
for z in [1..Length(pcgs)] do
h:=ClosureGroup(dser[z],cgens);
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=GroupGeneralMappingByImagesNC(h,fp,
Concatenation(GeneratorsOfGroup(dser[z]),cgens),
Concatenation(List(GeneratorsOfGroup(dser[z]),x->One(fp)),
imgs));
RUN_IN_GGMBI:=false;
ocr:=rec(group:=h,modulePcgs:=pcgs[z],
factorfphom:=fphom);
OCOneCocycles(ocr,true);
cgens:=GeneratorsOfGroup(ocr.complement);
od;
if Size(Last(dser))>Size(j.hall) then
gens:=[];
for z in cgens do
b:=Order(z);
a:=Product(Filtered(Factors(b),x->x in pi));
c:=GcdRepresentation(a,b/a);
Add(gens,z^((b/a)*c[2]));
od;
h:=Group(gens);
Info(InfoLattice,2,"Coprimize to ",Size(h));
n:=NormalIntersection(j.ns,h);
if Size(n)>1 then
k:=NormalIntersection(k,h);
if Size(k)>1 then
Error("nonsolvable case with nontrivial k still to do");
fi;
# now work in sylow normalizer -- correct gens to normalize
a:=SylowSubgroup(n,2);
cgens:=[];
for z in gens do
Add(cgens,z->z*RepresentativeAction(n,a^z,a));
od;
h:=Group(cgens);
a:=ComplementClassesRepresentatives(h,NormalIntersection(n,h));
cgens:=GeneratorsOfGroup(h[1]);
else
cgens:=gens;
k:=TrivialSubgroup(G);
fi;
fi;
Add(all,ClosureGroup(k,cgens));
else
Info(InfoLattice,3,"does not work");
fi;
od;
od;
return all;
end);
InstallGlobalFunction(HallViaRadical,function(G,pi)
local ser,hom,s,fphom,sf,sg,sp,fp,d,head,mran,nran,mpcgs,ocr,len,pcgs,
gens,all,indu;
if ForAny(pi,x->not IsPrimeInt(x)) then
Error("pi must be a set of primes");
fi;
ser:=FittingFreeLiftSetup(G);
pcgs:=ser.pcgs;
len:=Length(pcgs);
hom:=ser.factorhom;
if Intersection(pi,Factors(Size(Image(hom))))=[] then
s:=HallSubgroup(Image(ser.pcisom),pi);
sp:=List(Pcgs(s),x->PreImage(ser.pcisom,x));
return [
SubgroupByFittingFreeData(G,[],[],InducedPcgsByGeneratorsNC(pcgs,sp))];
fi;
all:=[];
for s in HallsFittingFree(Image(hom),pi) do
fphom:=IsomorphismFpGroup(s);
fp:=Image(fphom);
sf:=List(GeneratorsOfGroup(Image(fphom)),x->PreImagesRepresentative(fphom,x));
sg:=List(sf,x->PreImagesRepresentative(hom,x));
sp:=[];
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=GroupGeneralMappingByImagesNC(Group(sg,One(G)),fp,sg,
GeneratorsOfGroup(fp));
RUN_IN_GGMBI:=false;
for d in [2..Length(ser.depths)] do
mran:=[ser.depths[d-1]..len];
nran:=[ser.depths[d]..len];
head:=InducedPcgsByPcSequenceNC(pcgs,pcgs{mran});
mpcgs:=head mod
InducedPcgsByPcSequenceNC(pcgs,pcgs{nran});
if RelativeOrders(mpcgs)[1] in pi then
if d=Length(ser.depths) then
# last step, no presentation needed
Append(sp,mpcgs);
else
# extend presentation
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=LiftFactorFpHom(fphom,Source(fphom),false,mpcgs);
RUN_IN_GGMBI:=false;
fp:=Image(fphom);
sp:=Concatenation(sp,mpcgs);
fi;
else
ocr:=rec(group:=Group(Concatenation(head,sg,sp)),modulePcgs:=mpcgs);
ocr.factorfphom:=fphom;
OCOneCocycles(ocr,true);
gens:=GeneratorsOfGroup(ocr.complement);
sg:=gens{[1..Length(sg)]};
sp:=gens{[Length(sg)+1..Length(gens)]};
RUN_IN_GGMBI:=true; # hack to skip Nice treatment
fphom:=GroupGeneralMappingByImagesNC(ocr.complement,fp,gens,
GeneratorsOfGroup(fp));
RUN_IN_GGMBI:=false;
fi;
od;
if Length(pcgs)>0 then
indu:=InducedPcgsByPcSequenceNC(pcgs,sp);
else
indu:=[];
fi;
Add(all,
SubgroupByFittingFreeData(G,sg,sf,indu));
od;
return all;
end);
#############################################################################
##
#M HallSubgroupOp( <G>, <pi> )
##
## Fitting free approach
##
InstallMethod( HallSubgroupOp, "fitting free",true,
[ IsGroup and IsFinite and CanComputeFittingFree,IsList ],
OverrideNice,
function(G,pi)
local l;
if CanEasilyComputePcgs(G) then
TryNextMethod(); # pcgs method is clearly better
fi;
l:=HallViaRadical(G,pi);
if Length(l)=1 then
return l[1];
elif Length(l)=0 then
return fail;
else
return l;
fi;
end);
#############################################################################
##
#M SylowSubgroupOp( <G>, <pi> )
##
## Fitting free approach
##
InstallMethod( SylowSubgroupOp, "fitting free",true,
[ IsGroup and IsFinite and CanComputeFittingFree,IsPosInt ],
OverrideNice,
function(G,pi)
local l;
if IsPermGroup(G) or IsPcGroup(G) then TryNextMethod();fi;
if Set(Factors(Size(G)))=[pi] then
SetIsPGroup(G,true);
SetPrimePGroup(G, pi);
return G;
fi;
l:=HallViaRadical(G,[pi]);
if Length(l)=1 then
SetIsPGroup(l[1],true);
SetPrimePGroup(l[1],pi);
return l[1];
else
Error("There can be only one class");
fi;
end);
InstallMethod(ChiefSeriesTF,"fitting free",true,
[IsGroup and CanComputeFittingFree ],0,
function(G)
local ff,i,j,c,q,a,b,prev,sub,m,k;
ff:=FittingFreeLiftSetup(G);
if Size(ff.radical)=Size(G) then
c:=[G];
else
if Size(ff.radical)=1 then
c:=ChiefSeries(G);
else
q:=Image(ff.factorhom,G);
a:=ChiefSeries(q);
c:=List(a,x->PreImage(ff.factorhom,x));
fi;
fi;
# go through the depths
prev:=ff.pcgs;
for i in [2..Length(ff.depths)] do
sub:=InducedPcgsByPcSequence(ff.pcgs,ff.pcgs{[ff.depths[i]..Length(ff.pcgs)]});
m:=prev mod sub;
k:=SubgroupNC(G,sub);
a:=LinearActionLayer(G,m);
a:=GModuleByMats(a,GF(RelativeOrders(m)[1]));
b:=MTX.BasesSubmodules(a);
b:=b{[2..Length(b)-1]}; # only intermnediate ones
if Length(b)>0 then
for j in Reversed(b) do
Add(c,ClosureSubgroupNC(k,List(j,x->PcElementByExponents(m,x))));
od;
fi;
Add(c,k);
prev:=sub;
od;
return c;
end);
[ Dauer der Verarbeitung: 0.46 Sekunden
(vorverarbeitet)
]
|
