Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.
| Download
GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
Project: cocalc-sagemath-dev-slelievre
Views: 418346#############################################################################
##
#W clashom.gi GAP library Alexander Hulpke
##
##
#Y (C) 1999 School Math and Comp. Sci., University of St Andrews, Scotland
#Y Copyright (C) 2002,2013 The GAP Group
##
## This file contains functions that compute the conjugacy classes of a
## finite group by homomorphic images.
## Literature: A.H: Conjugacy classes in finite permutation groups via
## homomorphic images, MathComp
##
# get classes from classical group if possible.
BindGlobal("ClassesFromClassical",function(G)
local H,hom,d,cl;
if IsPermGroup(G) and (IsNaturalAlternatingGroup(G) or
IsNaturalSymmetricGroup(G)) then
return ConjugacyClasses(G); # there is a method for this
fi;
if not IsSimpleGroup(PerfectResiduum(G)) then
return fail;
fi;
d:=DataAboutSimpleGroup(PerfectResiduum(G));
if d.idSimple.series<>"L" then
return fail;
fi;
hom:=EpimorphismFromClassical(G);
if hom=fail then
return fail;
fi;
# so far matrix classes only implemented for GL/SL
if not (IsNaturalGL(Source(hom)) or IsNaturalSL(Source(hom))) then
return fail;
fi;
cl:=ClassesProjectiveImage(hom);
if HasConjugacyClasses(G) then
cl:=ConjugacyClasses(G); # will have been set
elif G=Image(hom) then
cl:=ConjugacyClasses(Image(hom)); # will have been set
else
Info(InfoWarning,1,"Weird class storage");
return fail;
fi;
return cl;
end);
#############################################################################
##
#F ClassRepsPermutedTuples(<g>,<ran>)
##
## computes representatives of the colourbars with colours selected from
## <ran>.
BindGlobal("ClassRepsPermutedTuples",function(g,ran)
local anz,erg,pat,pat2,sym,nrcomp,coldist,stab,dc,i,j,k,sum,schieb,lstab,
stabs,p;
anz:=NrMovedPoints(g);
sym:=SymmetricGroup(anz);
erg:=[];
stabs:=[];
for nrcomp in [1..anz] do
# all sorted colour distributions
coldist:=Combinations(ran,nrcomp);
for pat in OrderedPartitions(anz,nrcomp) do
Info(InfoHomClass,3,"Pattern: ",pat);
# compute the partition stabilizer
stab:=[];
sum:=0;
for i in pat do
schieb:=MappingPermListList([1..i],[sum+1..sum+i]);
sum:=sum+i;
stab:=Concatenation(stab,
List(GeneratorsOfGroup(SymmetricGroup(i)),j->j^schieb));
od;
stab:=Subgroup(sym,stab);
dc:=List(DoubleCosetRepsAndSizes(sym,stab,g),i->i[1]);
# compute expanded pattern
pat2:=[];
for i in [1..nrcomp] do
for j in [1..pat[i]] do
Add(pat2,i);
od;
od;
for j in dc do
# the new bar's stabilizer
lstab:=Intersection(g,ConjugateSubgroup(stab,j));
p:=Position(stabs,lstab);
if p=fail then
Add(stabs,lstab);
else
lstab:=stabs[p];
fi;
# the new bar
j:=Permuted(pat2,j);
for k in coldist do
Add(erg,[List(j,i->k[i]),lstab]);
od;
od;
od;
od;
return erg;
end);
#############################################################################
##
#F ConjugacyClassesSubwreath(<F>,<M>,<n>,<autT>,<T>,<Lloc>,<comp>,<emb>,<proj>)
##
InstallGlobalFunction(ConjugacyClassesSubwreath,
function(F,M,n,autT,T,Lloc,components,embeddings,projections)
local clT, # classes T
lcl, # Length(clT)
clTR, # classes under other group (autT,centralizer)
fus, # class fusion
sci, # |centralizer_i|
oci, # |reps_i|
i,j,k,l, # loop
pfus, # potential fusion
op, # operation of F on components
ophom, # F -> op
clF, # classes of F
clop, # classes of op
bars, # colour bars
barsi, # partial bars
lallcolors,# |all colors|
reps,Mproj,centralizers,centindex,emb,pi,varpi,newreps,newcent,
newcentindex,centimages,centimgindex,C,p,P,selectcen,select,
cen,eta,newcentlocal,newcentlocalindex,d,dc,s,t,elm,newcen,shift,
cengen,b1,ore,
# as in paper
colourbar,newcolourbar,possiblecolours,potentialbars,bar,colofclass,
clin,clout,
etas, # list of etas
opfun, # operation function
r,rp, # op-element complement in F
cnt,
brp,bcen,
centralizers_r, # centralizers of r
newcent_r,# new list to buid
centrhom, # projection \rest{centralizer of r}
localcent_r, # image
cr,
isdirprod,# is just M a direct product
genpos, # generator index
genpos2,
gen, # generator
stab, # stabilizer
stgen, # local stabilizer generators
trans,
repres,
img,
limg,
con,
pf,
orb, # orbit
orpo, # orbit position
minlen, # minimum orbit length
remainlen,#list of remaining lengths
gcd, # gcd of remaining orbit lengths
stabtrue,
diff,
possible,
combl,
smacla,
smare,
ppos,
maxdiff,
again, # run orbit again to get all
trymap, # operation to try
skip, # skip (if u=ug)
ug, # u\cap u^{gen^-1}
scj, # size(centralizers[j])
dsz; # Divisors(scj);
Info(InfoHomClass,1,
"ConjugacyClassesSubwreath called for almost simple group of size ",
Size(T));
isdirprod:=Size(M)=Size(autT)^n;
# classes of T
clT:=ClassesFromClassical(T);
if clT=fail then
clT:=ConjugacyClassesByRandomSearch(T);
fi;
clT:=List(clT,i->[Representative(i),Centralizer(i)]);
lcl:=Length(clT);
Info(InfoHomClass,1,"found ",lcl," classes in almost simple");
clTR:=List(clT,i->ConjugacyClass(autT,i[1]));
# possible fusion under autT
fus:=List([1..lcl],i->[i]);
for i in [1..lcl] do
sci:=Size(clT[i][2]);
# we have taken a permutation representation that prolongates to autT!
oci:=CycleStructurePerm(clT[i][1]);
# we have tested already the smaller-# classes
pfus:=Filtered([i+1..lcl],j->CycleStructurePerm(clT[j][1])=oci and
Size(clT[j][2])=sci);
pfus:=Difference(pfus,fus[i]);
if Length(pfus)>0 then
Info(InfoHomClass,3,"possible fusion ",pfus);
for j in pfus do
if clT[j][1] in clTR[i] then
fus[i]:=Union(fus[i],fus[j]);
# fuse the entries
for k in fus[i] do
fus[k]:=fus[i];
od;
fi;
od;
fi;
od;
fus:=Set(fus); # throw out duplicates
colofclass:=List([1..lcl],i->PositionProperty(fus,j->i in j));
Info(InfoHomClass,2,"fused to ",Length(fus)," colours");
# get the allowed colour bars
ophom:=ActionHomomorphism(F,components,OnSets,"surjective");
op:=Image(ophom);
lallcolors:=Length(fus);
bars:=ClassRepsPermutedTuples(op,[1..lallcolors]);
Info(InfoHomClass,1,"classes in normal subgroup");
# inner classes
reps:=[One(M)];
centralizers:=[M];
centindex:=[1];
colourbar:=[[]];
Mproj:=[];
varpi:=[];
for i in [1..n] do
Info(InfoHomClass,1,"component ",i);
barsi:=Set(Immutable(List(bars,j->j[1]{[1..i]})));
emb:=embeddings[i];
pi:=projections[i];
Add(varpi,ActionHomomorphism(M,Union(components{[1..i]}),"surjective"));
Add(Mproj,Image(varpi[i],M));
newreps:=[];
newcent:=[];
newcentindex:=[];
centimages:=[];
centimgindex:=[];
newcolourbar:=[];
etas:=[]; # etas for the centralizers
# fuse centralizers that become the same
for j in [1..Length(centralizers)] do
C:=Image(pi,centralizers[j]);
p:=Position(centimages,C);
if p=fail then
Add(centimages,C);
p:=Length(centimages);
fi;
Add(centimgindex,p);
# #force 'centralizers[j]' to have its base appropriate to the component
# # (this will speed up preimages)
# cen:=centralizers[j];
# d:=Size(cen);
# cen:=Group(GeneratorsOfGroup(cen),());
# StabChain(cen,rec(base:=components[i],size:=d));
# centralizers[j]:=cen;
# etas[j]:=ActionHomomorphism(cen,components[i],"surjective");
od;
Info(InfoHomClass,2,Length(centimages)," centralizer images");
# consider previous centralizers
for j in [1..Length(centimages)] do
# determine all reps belonging to this centralizer
C:=centimages[j];
selectcen:=Filtered([1..Length(centimgindex)],k->centimgindex[k]=j);
Info(InfoHomClass,2,"Number ",j,": ",Length(selectcen),
" previous centralizers to consider");
# 7'
select:=Filtered([1..Length(centindex)],k->centindex[k] in selectcen);
# Determine the addable colours
if i=1 then
possiblecolours:=[1..Length(fus)];
else
possiblecolours:=[];
#for k in select do
# bar:=colourbar[k];
k:=1;
while k<=Length(select)
and Length(possiblecolours)<lallcolors do
bar:=colourbar[select[k]];
potentialbars:=Filtered(bars,j->j[1]{[1..i-1]}=bar);
UniteSet(possiblecolours,
potentialbars{[1..Length(potentialbars)]}[1][i]);
k:=k+1;
od;
fi;
for k in Union(fus{possiblecolours}) do
# double cosets
if Size(C)=Size(T) then
dc:=[One(T)];
else
Assert(1,IsSubgroup(T,clT[k][2]));
Assert(1,IsSubgroup(T,C));
dc:=List(DoubleCosetRepsAndSizes(T,clT[k][2],C),i->i[1]);
fi;
for t in selectcen do
# continue partial rep.
# #force 'centralizers[j]' to have its base appropriate to the component
# # (this will speed up preimages)
# if not (HasStabChainMutable(cen)
# and i<=Length(centralizers)
# and BaseStabChain(StabChainMutable(cen))[1] in centralizers[i])
# then
# d:=Size(cen);
# cen:= Group( GeneratorsOfGroup( cen ), One( cen ) );
# StabChain(cen,rec(base:=components[i],size:=d));
# #centralizers[t]:=cen;
# fi;
cen:=centralizers[t];
if not IsBound(etas[t]) then
if Number(etas,i->IsBound(i))>500 then
for d in
Filtered([1..Length(etas)],i->IsBound(etas[i])){[1..500]} do
Unbind(etas[d]);
od;
fi;
etas[t]:=ActionHomomorphism(cen,components[i],"surjective");
fi;
eta:=etas[t];
select:=Filtered([1..Length(centindex)],l->centindex[l]=t);
Info(InfoHomClass,3,"centralizer nr.",t,", ",
Length(select)," previous classes");
newcentlocal:=[];
newcentlocalindex:=[];
for d in dc do
for s in select do
# test whether colour may be added here
bar:=Concatenation(colourbar[s],[colofclass[k]]);
bar:=ShallowCopy(colourbar[s]);
Add(bar,colofclass[k]);
MakeImmutable(bar);
#if ForAny(bars,j->j[1]{[1..i]}=bar) then
if bar in barsi then
# new representative
elm:=reps[s]*Image(emb,clT[k][1]^d);
if elm in Mproj[i] then
# store the new element
Add(newreps,elm);
Add(newcolourbar,bar);
if i<n then # we only need the centralizer for further
# components
newcen:=ClosureGroup(Lloc,
List(GeneratorsOfGroup(clT[k][2]),g->g^d));
p:=Position(newcentlocal,newcen);
if p=fail then
Add(newcentlocal,newcen);
p:=Length(newcentlocal);
fi;
Add(newcentlocalindex,p);
else
Add(newcentlocalindex,1); # dummy, just for counting
fi;
#else
# Info(InfoHomClass,5,"not in");
fi;
#else
# Info(InfoHomClass,5,bar,"not minimal");
fi;
# end the loops from step 9
od;
od;
Info(InfoHomClass,2,Length(newcentlocalindex),
" new representatives");
if i<n then # we only need the centralizer for further components
# Centralizer preimages
shift:=[];
for l in [1..Length(newcentlocal)] do
P:=PreImage(eta,Intersection(Image(eta),newcentlocal[l]));
p:=Position(newcent,P);
if p=fail then
Add(newcent,P);
p:=Length(newcent);
fi;
shift[l]:=p;
od;
# move centralizer indices to global
for l in newcentlocalindex do
Add(newcentindex,shift[l]);
od;
fi;
# end the loops from step 6,7 and 8
od;
od;
od;
centralizers:=newcent;
centindex:=newcentindex;
reps:=newreps;
colourbar:=newcolourbar;
# end the loop of step 2.
od;
Info(InfoHomClass,1,Length(reps)," classreps constructed");
# further fusion among bars
newreps:=[];
Info(InfoHomClass,2,"computing centralizers");
for bar in bars do
b1:=Immutable(bar[1]);
select:=Filtered([1..Length(reps)],i->colourbar[i]=b1);
if Length(select)>1 then
Info(InfoHomClass,2,"test ",Length(select)," classes for fusion");
fi;
newcentlocal:=[];
for i in [1..Length(select)] do
if not ForAny(newcentlocal,j->reps[select[i]] in j) then
#AH we could also compute the centralizer
C:=Centralizer(F,reps[select[i]]);
Add(newreps,[reps[select[i]],C]);
if i<Length(select) and Size(bar[2])>1 then
# there are other reps with the same bar left and the bar
# stabilizer is bigger than M
if not IsBound(bar[2]!.colstabprimg) then
# identical stabilizers have the same link. Therefore store the
# preimage in them
bar[2]!.colstabprimg:=PreImage(ophom,bar[2]);
fi;
# any fusion would take place in the stabilizer preimage
# we know that C must fix the bar, so it is the centralizer there.
r:=ConjugacyClass(bar[2]!.colstabprimg,reps[select[i]],C);
Add(newcentlocal,r);
fi;
fi;
od;
od;
Info(InfoHomClass,1,"fused to ",Length(newreps)," inner classes");
clF:=newreps;
clin:=ShallowCopy(clF);
Assert(1,Sum(clin,i->Index(F,i[2]))=Size(M));
clout:=[];
# outer classes
clop:=Filtered(ConjugacyClasses(op),i->Order(Representative(i))>1);
for k in clop do
Info(InfoHomClass,1,"lifting class ",Representative(k));
r:=PreImagesRepresentative(ophom,Representative(k));
# try to make r of small order
rp:=r^Order(Representative(k));
rp:=RepresentativeAction(M,Concatenation(components),
Concatenation(OnTuples(components[1],rp^-1),
Concatenation(components{[2..n]})),OnTuples);
if rp<>fail then
r:=r*rp;
else
Info(InfoHomClass,2,
"trying random modification to get large centralizer");
cnt:=LogInt(Size(autT),2)*10;
brp:=();
bcen:=Size(Centralizer(F,r));
repeat
rp:=Random(M);
cengen:=Size(Centralizer(M,r*rp));
if cengen>bcen then
bcen:=cengen;
brp:=rp;
cnt:=LogInt(Size(autT),2)*10;
else
cnt:=cnt-1;
fi;
until cnt<0;
r:=r*brp;
Info(InfoHomClass,2,"achieved centralizer size ",bcen);
fi;
Info(InfoHomClass,2,"representative ",r);
cr:=Centralizer(M,r);
# first look at M-action
reps:=[One(M)];
centralizers:=[M];
centralizers_r:=[cr];
for i in [1..n] do;
newreps:=[];
newcent:=[];
newcent_r:=[];
opfun:=function(a,m)
return Comm(r,m)*a^m;
end;
for j in [1..Length(reps)] do
scj:=Size(centralizers[j]);
dsz:=0;
centrhom:=ActionHomomorphism(centralizers_r[j],components[i],
"surjective");
localcent_r:=Image(centrhom);
Info(InfoHomClass,4,i,":",j);
Info(InfoHomClass,3,"acting: ",Size(centralizers[j])," minimum ",
Int(Size(Image(projections[i]))/Size(centralizers[j])),
" orbits.");
# compute C(r)-classes
clTR:=[];
for l in clT do
Info(InfoHomClass,4,"DC",Index(T,l[2])," ",Index(T,localcent_r));
dc:=DoubleCosetRepsAndSizes(T,l[2],localcent_r);
clTR:=Concatenation(clTR,List(dc,i->l[1]^i[1]));
od;
orb:=[];
for p in [1..Length(clTR)] do
repres:=PreImagesRepresentative(projections[i],clTR[p]);
if i=1 or isdirprod
or reps[j]*RestrictedPermNC(repres,components[i])
in Mproj[i] then
stab:=Centralizer(localcent_r,clTR[p]);
if Index(localcent_r,stab)<Length(clTR)/10 then
img:=Orbit(localcent_r,clTR[p]);
#ensure Representative is in first position
if img[1]<>clTR[p] then
genpos:=Position(img,clTR[p]);
img:=Permuted(img,(1,genpos));
fi;
else
img:=ConjugacyClass(localcent_r,clTR[p],stab);
fi;
Add(orb,[repres,PreImage(centrhom,stab),img,localcent_r]);
fi;
od;
clTR:=orb;
#was:
#clTR:=List(clTR,i->ConjugacyClass(localcent_r,i));
#clTR:=List(clTR,j->[PreImagesRepresentative(projections[i],
# Representative(j)),
# PreImage(centrhom,Centralizer(j)),
# j]);
# put small classes to the top (to be sure to hit them and make
# large local stabilizers)
Sort(clTR,function(a,b) return Size(a[3])<Size(b[3]);end);
Info(InfoHomClass,3,Length(clTR)," local classes");
cengen:=GeneratorsOfGroup(centralizers[j]);
#cengen:=Filtered(cengen,i->not i in localcent_r);
while Length(clTR)>0 do
# orbit algorithm on classes
stab:=clTR[1][2];
orb:=[clTR[1]];
#repres:=RestrictedPermNC(clTR[1][1],components[i]);
repres:=clTR[1][1];
trans:=[One(M)];
select:=[2..Length(clTR)];
orpo:=1;
minlen:=Size(orb[1][3]);
possible:=false;
stabtrue:=false;
pf:=infinity;
maxdiff:=Size(T);
again:=0;
trymap:=false;
ug:=[];
# test whether we have full orbit and full stabilizer
while Size(centralizers[j])>(Sum(orb,i->Size(i[3]))*Size(stab)) do
genpos:=1;
while genpos<=Length(cengen) and
Size(centralizers[j])>(Sum(orb,i->Size(i[3]))*Size(stab)) do
gen:=cengen[genpos];
skip:=false;
if trymap<>false then
orpo:=trymap[1];
gen:=trymap[2];
trymap:=false;
elif again>0 then
if not IsBound(ug[genpos]) then
ug[genpos]:=Intersection(centralizers_r[j],
ConjugateSubgroup(centralizers_r[j],gen^-1));
fi;
if again<500 and ForAll(GeneratorsOfGroup(centralizers_r[j]),
i->i in ug[genpos])
then
# the random elements will give us nothing new
skip:=true;
else
# get an element not in ug[genpos]
repeat
img:=Random(centralizers_r[j]);
until not img in ug[genpos] or again>=500;
gen:=img*gen;
fi;
fi;
if not skip then
img:=Image(projections[i],opfun(orb[orpo][1],gen));
smacla:=select;
if not stabtrue then
p:=PositionProperty(orb,i->img in i[3]);
ppos:=fail;
else
# we have the stabilizer and thus are only interested in
# getting new elements.
ppos:=PositionProperty(select,
i->Size(clTR[i][3])<=maxdiff and img in clTR[i][3]);
if ppos=fail then
p:="ignore"; #to avoid the first case
else
ppos:=select[ppos]; # get the right value
p:=fail; # go to first case
fi;
fi;
if p=fail then
if ppos=fail then
p:=First(select,
i->Size(clTR[i][3])<=maxdiff and img in clTR[i][3]);
else
p:=ppos;
fi;
RemoveSet(select,p);
Add(orb,clTR[p]);
#change the transversal element to map to the representative
con:=trans[orpo]*gen;
limg:=opfun(repres,con);
con:=con*PreImagesRepresentative(centrhom,
RepresentativeAction(localcent_r,
Image(projections[i],limg),
Representative(clTR[p][3])));
Assert(1,Image(projections[i],opfun(repres,con))
=Representative(clTR[p][3]));
Add(trans,con);
for stgen in GeneratorsOfGroup(clTR[p][2]) do
Assert( 1, IsOne( Image( projections[i],
opfun(repres,con*stgen/con)/repres ) ) );
stab:=ClosureGroup(stab,con*stgen/con);
od;
# compute new minimum length
if Length(select)>0 then
remainlen:=List(clTR{select},i->Size(i[3]));
gcd:=Gcd(remainlen);
diff:=minlen-Sum(orb,i->Size(i[3]));
if diff<0 then
# only go through this if the orbit actually grew
# larger
minlen:=Sum(orb,i->Size(i[3]));
repeat
if dsz=0 then
dsz:=DivisorsInt(scj);
fi;
while not minlen in dsz do
# minimum gcd multiple to get at least the
# smallest divisor
minlen:=minlen+
(QuoInt((First(dsz,i->i>=minlen)-minlen-1),
gcd)+1)*gcd;
od;
# now try whether we actually can add orbits to make up
# that length
diff:=minlen-Sum(orb,i->Size(i[3]));
Assert(1,diff>=0);
# filter those remaining classes small enough to make
# up the length
smacla:=Filtered(select,i->Size(clTR[i][3])<=diff);
remainlen:=List(clTR{smacla},i->Size(i[3]));
combl:=1;
possible:=false;
if diff=0 then
possible:=fail;
fi;
while gcd*combl<=diff
and combl<=Length(remainlen) and possible=false do
if NrCombinations(remainlen,combl)<100 then
possible:=ForAny(Combinations(remainlen,combl),
i->Sum(i)=diff);
else
possible:=fail;
fi;
combl:=combl+1;
od;
if possible=false then
minlen:=minlen+gcd;
fi;
until possible<>false;
fi; # if minimal orbit length grew
Info(InfoHomClass,5,"Minimum length of this orbit ",
minlen," (",diff," missing)");
fi;
if minlen*Size(stab)=Size(centralizers[j]) then
#Assert(1,Length(smacla)>0);
maxdiff:=diff;
stabtrue:=true;
fi;
elif not stabtrue then
# we have an element that stabilizes the conjugacy class.
# correct this to an element that fixes the representative.
# (As we have taken already the centralizer in
# centralizers_r, it is sufficient to correct by
# centralizers_r-conjugation.)
con:=trans[orpo]*gen;
limg:=opfun(repres,con);
con:=con*PreImagesRepresentative(centrhom,
RepresentativeAction(localcent_r,
Image(projections[i],limg),
Representative(orb[p][3])));
stab:=ClosureGroup(stab,con/trans[p]);
if Size(stab)*2*minlen>Size(centralizers[j]) then
Info(InfoHomClass,3,
"true stabilizer found (cannot grow)");
minlen:=Size(centralizers[j])/Size(stab);
maxdiff:=minlen-Sum(orb,i->Size(i[3]));
stabtrue:=true;
fi;
fi;
if stabtrue then
smacla:=Filtered(select,i->Size(clTR[i][3])<=maxdiff);
if Length(smacla)<pf then
pf:=Length(smacla);
remainlen:=List(clTR{smacla},i->Size(i[3]));
Info(InfoHomClass,3,
"This is the true orbit length (missing ",
maxdiff,")");
if Size(stab)*Sum(orb,i->Size(i[3]))
=Size(centralizers[j]) then
maxdiff:=0;
elif Sum(remainlen)=maxdiff then
Info(InfoHomClass,2,
"Full possible remainder must fuse");
orb:=Concatenation(orb,clTR{smacla});
select:=Difference(select,smacla);
else
# test whether there is only one possibility to get
# this length
if Length(smacla)<20 and
Sum(List([1..Minimum(Length(smacla),
Int(maxdiff/gcd+1))],
x-> NrCombinations(smacla,x)))<10000 then
# get all reasonable combinations
smare:=[1..Length(smacla)]; #range for smacla
combl:=Concatenation(List([1..Int(maxdiff/gcd+1)],
i->Combinations(smare,i)));
# pick those that have the correct length
combl:=Filtered(combl,i->Sum(remainlen{i})=maxdiff);
if Length(combl)>1 then
Info(InfoHomClass,3,"Addendum not unique (",
Length(combl)," possibilities)");
if (maxdiff<10 or again>0)
and ForAll(combl,i->Length(i)<=5) then
# we have tried often enough, now try to pick the
# right ones
possible:=false;
combl:=Union(combl);
combl:=smacla{combl};
genpos2:=1;
smacla:=[];
while possible=false and Length(combl)>0 do
img:=Image(projections[i],
opfun(clTR[combl[1]][1],cengen[genpos2]));
p:=PositionProperty(orb,i->img in i[3]);
if p<>fail then
# it is!
Info(InfoHomClass,4,"got one!");
# remember the element to try
trymap:=[p,(cengen[genpos2]*
PreImagesRepresentative(
RestrictedMapping(projections[i],
centralizers[j]),
RepresentativeAction(
orb[p][4],
img,Representative(orb[p][3])) ))^-1];
Add(smacla,combl[1]);
combl:=combl{[2..Length(combl)]};
if Sum(clTR{smacla},i->Size(i[3]))=maxdiff then
# bingo!
possible:=true;
fi;
fi;
genpos2:=genpos2+1;
if genpos2>Length(cengen) then
genpos2:=1;
combl:=combl{[2..Length(combl)]};
fi;
od;
if possible=false then
Info(InfoHomClass,4,"Even test failed!");
else
orb:=Concatenation(orb,clTR{smacla});
select:=Difference(select,smacla);
Info(InfoHomClass,3,"Completed orbit (hard)");
fi;
fi;
else
combl:=combl[1];
orb:=Concatenation(orb,clTR{smacla{combl}});
select:=Difference(select,smacla{combl});
Info(InfoHomClass,3,"Completed orbit");
fi;
fi;
fi;
fi;
fi;
else
Info(InfoHomClass,5,"skip");
fi; # if not skip
genpos:=genpos+1;
od;
orpo:=orpo+1;
if orpo>Length(orb) then
Info(InfoHomClass,3,"Size factor:",EvalF(
(Sum(orb,i->Size(i[3]))*Size(stab))/Size(centralizers[j])),
" orbit consists of ",Length(orb)," suborbits, iterating");
orpo:=1;
again:=again+1;
fi;
od;
Info(InfoHomClass,2,"Stabsize = ",Size(stab),
", centstabsize = ",Size(orb[1][2]));
clTR:=clTR{select};
Info(InfoHomClass,2,"orbit consists of ",Length(orb)," suborbits,",
Length(clTR)," classes left.");
Info(InfoHomClass,3,List(orb,i->Size(i[2])));
Info(InfoHomClass,4,List(orb,i->Size(i[3])));
# select the orbit element with the largest local centralizer
orpo:=1;
p:=2;
while p<=Length(orb) do
if IsBound(trans[p]) and Size(orb[p][2])>Size(orb[orpo][2]) then
orpo:=p;
fi;
p:=p+1;
od;
if orpo<>1 then
Info(InfoHomClass,3,"switching to orbit position ",orpo);
repres:=opfun(repres,trans[orpo]);
#repres:=RestrictedPermNC(clTR[1][1],repres);
stab:=stab^trans[orpo];
fi;
Assert(1,ForAll(GeneratorsOfGroup(stab),
j -> IsOne( Image(projections[i],opfun(repres,j)/repres) )));
# correct stabilizer to element stabilizer
Add(newreps,reps[j]*RestrictedPermNC(repres,components[i]));
Add(newcent,stab);
Add(newcent_r,orb[orpo][2]);
od;
od;
reps:=newreps;
centralizers:=newcent;
centralizers_r:=newcent_r;
Info(InfoHomClass,2,Length(reps)," representatives");
od;
select:=Filtered([1..Length(reps)],i->reps[i] in M);
reps:=reps{select};
reps:=List(reps,i->r*i);
centralizers:=centralizers{select};
centralizers_r:=centralizers_r{select};
Info(InfoHomClass,1,Length(reps)," in M");
# fuse reps if necessary
cen:=PreImage(ophom,Centralizer(k));
newreps:=[];
newcentlocal:=[];
for i in [1..Length(reps)] do
bar:=CycleStructurePerm(reps[i]);
ore:=Order(reps[i]);
newcentlocal:=Filtered(newreps,
i->Order(Representative(i))=ore and
i!.elmcyc=bar);
if not ForAny(newcentlocal,j->reps[i] in j) then
C:=Centralizer(cen,reps[i]);
# AH can we use centralizers[i] here ?
Add(clF,[reps[i],C]);
Add(clout,[reps[i],C]);
bar:=ConjugacyClass(cen,reps[i],C);
bar!.elmcyc:=CycleStructurePerm(reps[i]);
Add(newreps,bar);
fi;
od;
Info(InfoHomClass,1,"fused to ",Length(newreps)," classes");
od;
Assert(1,Sum(clout,i->Index(F,i[2]))=Size(F)-Size(M));
Info(InfoHomClass,2,Length(clin)," inner classes, total size =",
Sum(clin,i->Index(F,i[2])));
Info(InfoHomClass,2,Length(clout)," outer classes, total size =",
Sum(clout,i->Index(F,i[2])));
Info(InfoHomClass,3," Minimal ration for outer classes =",
EvalF(Minimum(List(clout,i->Index(F,i[2])/(Size(F)-Size(M)))),30));
Info(InfoHomClass,1,"returning ",Length(clF)," classes");
Assert(1,Sum(clF,i->Index(F,i[2]))=Size(F));
return clF;
end);
InstallGlobalFunction(ConjugacyClassesFittingFreeGroup,function(G)
local cs, # chief series of G
i, # index cs
cl, # list [classrep,centralizer]
hom, # G->G/cs[i]
M, # cs[i-1]
N, # cs[i]
subN, # maximan normal in M over N
csM, # orbit of nt in M under G
n, # Length(csM)
T, # List of T_i
Q, # Action(G,T)
Qhom, # G->Q and F->Q
S, # PreImage(Qhom,Stab_Q(1))
S1, # Action of S on T[1]
deg1, # deg (s1)
autos, # automorphism for action
arhom, # autom permrep list
Thom, # S->S1
T1, # T[1] Thom
w, # S1\wrQ
wbas, # base of w
emb, # embeddings of w
proj, # projections of wbas
components, # components of w
reps, # List reps in G for 1->i in Q
F, # action of G on M/N
Fhom, # G -> F
FQhom, # Fhom*Qhom
genimages,# G.generators Fhom
img, # gQhom
gimg, # gFhom
act, # component permcation to 1
j,k, # loop
C, # Ker(Fhom)
clF, # classes of F
ncl, # new classes
FM, # normal subgroup in F, Fhom(M)
FMhom, # M->FM
dc, # double cosets
jim, # image of j
Cim,
CimCl,
p,
l,lj,
l1,
elm,
zentr,
onlysizes,
good,bad,
lastM;
onlysizes:=ValueOption("onlysizes");
# we assume the group has no solvable normal subgroup. Thus we get all
# classes by lifts via nonabelian factors and can disregard all abelian
# factors.
# we will give classes always by their representatives in G and
# centralizers by their full preimages in G.
cs:= ChiefSeriesOfGroup( G );
# the first step is always simple
if HasAbelianFactorGroup(G,cs[2]) then
# try to get the largest abelian factor
i:=2;
while i<Length(cs) and HasAbelianFactorGroup(G,cs[i+1]) do
i:=i+1;
od;
cs:=Concatenation([G],cs{[i..Length(cs)]});
# now cs[1]/cs[2] is the largest abelian factor
cl:=List(RightTransversal(G,cs[2]),i->[i,G]);
else
# compute the classes of the simple nonabelian factor by random search
hom:=NaturalHomomorphismByNormalSubgroupNC(G,cs[2]);
cl:=ConjugacyClasses(Image(hom));
cl:=List(cl,i->[PreImagesRepresentative(hom,Representative(i)),
PreImage(hom,StabilizerOfExternalSet(i))]);
fi;
lastM:=cs[2];
for i in [3..Length(cs)] do
# we assume that cl contains classreps/centralizers for G/cs[i-1]
# we want to lift to G/cs[i]
M:=cs[i-1];
N:=cs[i];
Info(InfoHomClass,1,i,":",Index(M,N),"; ",Size(N));
if HasAbelianFactorGroup(M,N) then
Info(InfoHomClass,2,"abelian factor ignored");
else
# nonabelian factor. Now it means real work.
# 1) compute the action for the factor
# first, we obtain the simple factors T_i/N.
# we get these as intersections of the conjugates of the subnormal
# subgroup
csM:=CompositionSeries(M); # stored attribute
if not IsSubset(csM[2],N) then
# the composition series goes the wrong way. Now take closures of
# its steps with N to get a composition series for M/N, take the
# first proper factor for subN.
n:=3;
subN:=fail;
while n<=Length(csM) and subN=fail do
subN:=ClosureGroup(N,csM[n]);
if Index(M,subN)=1 then
subN:=fail; # still wrong
fi;
n:=n+1;
od;
else
subN:=csM[2];
fi;
if IsNormal(G,subN) then
# only one -> Call standard process
Fhom:=fail;
# is this an almost top factor?
if Index(G,M)<10 then
Thom:=NaturalHomomorphismByNormalSubgroupNC(G,subN);
T1:=Image(Thom,M);
S1:=Image(Thom);
if Size(Centralizer(S1,T1))=1 then
deg1:=NrMovedPoints(S1);
Info(InfoHomClass,2,
"top factor gives conjugating representation, deg ",deg1);
Fhom:=Thom;
fi;
else
Thom:=NaturalHomomorphismByNormalSubgroupNC(M,subN);
T1:=Image(Thom,M);
fi;
if Fhom=fail then
autos:=List(GeneratorsOfGroup(G),
i->GroupHomomorphismByImagesNC(T1,T1,GeneratorsOfGroup(T1),
List(GeneratorsOfGroup(T1),
j->Image(Thom,PreImagesRepresentative(Thom,j)^i))));
# find (probably another) permutation rep for T1 for which all
# automorphisms can be represented by permutations
arhom:=AutomorphismRepresentingGroup(T1,autos);
S1:=arhom[1];
deg1:=NrMovedPoints(S1);
Fhom:=GroupHomomorphismByImagesNC(G,S1,GeneratorsOfGroup(G),arhom[3]);
fi;
C:=KernelOfMultiplicativeGeneralMapping(Fhom);
F:=Image(Fhom,G);
clF:=ClassesFromClassical(F);
if clF=fail then
clF:=ConjugacyClassesByRandomSearch(F);
fi;
clF:=List(clF,j->[Representative(j),StabilizerOfExternalSet(j)]);
else
csM:=Orbit(G,subN); # all conjugates
n:=Length(csM);
if n=1 then
Error("this cannot happen");
T:=M;
fi;
T:=Intersection(csM{[2..Length(csM)]}); # one T_i
if Length(GeneratorsOfGroup(T))>5 then
T:=Group(SmallGeneratingSet(T));
fi;
T:=Orbit(G,T); # get all the t's
# now T[1] is a complement to csM[1] in G/N.
# now compute the operation of G on M/N
Qhom:=ActionHomomorphism(G,T,"surjective");
Q:=Image(Qhom,G);
S:=PreImage(Qhom,Stabilizer(Q,1));
# find a permutation rep. for S-action on T[1]
Thom:=NaturalHomomorphismByNormalSubgroupNC(T[1],N);
T1:=Image(Thom);
if not IsSubset([1..NrMovedPoints(T1)],
MovedPoints(T1)) then
Thom:=Thom*ActionHomomorphism(T1,MovedPoints(T1),"surjective");
fi;
T1:=Image(Thom,T[1]);
autos:=List(GeneratorsOfGroup(S),
i->GroupHomomorphismByImagesNC(T1,T1,GeneratorsOfGroup(T1),
List(GeneratorsOfGroup(T1),
j->Image(Thom,PreImagesRepresentative(Thom,j)^i))));
# find (probably another) permutation rep for T1 for which all
# automorphisms can be represented by permutations
arhom:=AutomorphismRepresentingGroup(T1,autos);
S1:=arhom[1];
deg1:=NrMovedPoints(S1);
Thom:=GroupHomomorphismByImagesNC(S,S1,GeneratorsOfGroup(S),arhom[3]);
T1:=Image(Thom,T[1]);
# now embed into wreath
w:=WreathProduct(S1,Q);
wbas:=DirectProduct(List([1..n],i->S1));
emb:=List([1..n+1],i->Embedding(w,i));
proj:=List([1..n],i->Projection(wbas,i));
components:=WreathProductInfo(w).components;
# define isomorphisms between the components
reps:=List([1..n],i->
PreImagesRepresentative(Qhom,RepresentativeAction(Q,1,i)));
genimages:=[];
for j in GeneratorsOfGroup(G) do
img:=Image(Qhom,j);
gimg:=Image(emb[n+1],img);
for k in [1..n] do
# look at part of j's action on the k-th factor.
# we get this by looking at the action of
# reps[k] * j * reps[k^img]^-1
# 1 -> k -> k^img -> 1
# on the first component.
act:=reps[k]*j*(reps[k^img]^-1);
# this must be multiplied *before* permuting
gimg:=ImageElm(emb[k],ImageElm(Thom,act))*gimg;
gimg:=RestrictedPermNC(gimg,MovedPoints(w));
od;
Add(genimages,gimg);
od;
F:=Subgroup(w,genimages);
if AssertionLevel()>0 then
Fhom:=GroupHomomorphismByImages(G,F,GeneratorsOfGroup(G),genimages);
Assert(1,fail<>Fhom);
else
Fhom:=GroupHomomorphismByImagesNC(G,F,GeneratorsOfGroup(G),genimages);
fi;
C:=KernelOfMultiplicativeGeneralMapping(Fhom);
Info(InfoHomClass,1,"constructed Fhom");
# 2) compute the classes for F
if n>1 then
#if IsPermGroup(F) and NrMovedPoints(F)<18 then
# # the old Butler/Theissen approach is still OK
# clF:=[];
# for j in
# Concatenation(List(RationalClasses(F),DecomposedRationalClass)) do
# Add(clF,[Representative(j),StabilizerOfExternalSet(j)]);
# od;
#else
FM:=F;
for j in components do
FM:=Stabilizer(FM,j,OnSets);
od;
clF:=ConjugacyClassesSubwreath(F,FM,n,S1,
Action(FM,components[1]),T1,components,emb,proj);
#fi;
else
FM:=Image(Fhom,M);
Info(InfoHomClass,1,
"classes by random search in almost simple group");
clF:=ClassesFromClassical(F);
if clF=fail then
clF:=ConjugacyClassesByRandomSearch(F);
fi;
clF:=List(clF,j->[Representative(j),StabilizerOfExternalSet(j)]);
fi;
fi; # true orbit of T.
Assert(1,Sum(clF,i->Index(F,i[2]))=Size(F));
Assert(1,ForAll(clF,i->Centralizer(F,i[1])=i[2]));
# 3) combine to form classes of sdp
# the length(cl)=1 gets rid of solvable stuff on the top we got ``too
# early''.
if IsSubgroup(N,KernelOfMultiplicativeGeneralMapping(Fhom)) then
Info(InfoHomClass,1,
"homomorphism is faithful for relevant factor, take preimages");
if Size(N)=1 and onlysizes=true then
cl:=List(clF,i->[PreImagesRepresentative(Fhom,i[1]),Size(i[2])]);
else
cl:=List(clF,i->[PreImagesRepresentative(Fhom,i[1]),
PreImage(Fhom,i[2])]);
fi;
else
Info(InfoHomClass,1,"forming subdirect products");
FM:=Image(Fhom,lastM);
FMhom:=RestrictedMapping(Fhom,lastM);
if Index(F,FM)=1 then
Info(InfoHomClass,1,"degenerated to direct product");
ncl:=[];
for j in cl do
for k in clF do
# modify the representative with a kernel elm. to project
# correctly on the second component
elm:=j[1]*PreImagesRepresentative(FMhom,
LeftQuotient(Image(Fhom,j[1]),k[1]));
zentr:=Intersection(j[2],PreImage(Fhom,k[2]));
Assert(2,ForAll(GeneratorsOfGroup(zentr),
i->Comm(i,elm) in N));
Add(ncl,[elm,zentr]);
od;
od;
cl:=ncl;
else
# first we add the centralizer closures and sort by them
# (this allows to reduce the number of double coset calculations)
ncl:=[];
for j in cl do
Cim:=Image(Fhom,j[2]);
CimCl:=Cim;
#CimCl:=ClosureGroup(FM,Cim); # should be unnecessary, as we took
# the full preimage
p:=PositionProperty(ncl,i->i[1]=CimCl);
if p=fail then
Add(ncl,[CimCl,[j]]);
else
Add(ncl[p][2],j);
fi;
od;
Qhom:=NaturalHomomorphismByNormalSubgroupNC(F,FM);
Q:=Image(Qhom);
FQhom:=Fhom*Qhom;
# now construct the sdp's
cl:=[];
for j in ncl do
lj:=List(j[2],i->Image(FQhom,i[1]));
for k in clF do
# test whether the classes are potential mates
elm:=Image(Qhom,k[1]);
if not ForAll(lj,i->RepresentativeAction(Q,i,elm)=fail) then
#l:=Image(Fhom,j[1]);
if Index(F,j[1])=1 then
dc:=[()];
else
dc:=List(DoubleCosetRepsAndSizes(F,k[2],j[1]),i->i[1]);
fi;
good:=0;
bad:=0;
for l in j[2] do
jim:=Image(FQhom,l[1]);
for l1 in dc do
elm:=k[1]^l1;
if Image(Qhom,elm)=jim then
# modify the representative with a kernel elm. to project
# correctly on the second component
elm:=l[1]*PreImagesRepresentative(FMhom,
LeftQuotient(Image(Fhom,l[1]),elm));
zentr:=PreImage(Fhom,k[2]^l1);
zentr:=Intersection(zentr,l[2]);
Assert(2,ForAll(GeneratorsOfGroup(zentr),
i->Comm(i,elm) in N));
Info(InfoHomClass,4,"new class, order ",Order(elm),
", size=",Index(G,zentr));
Add(cl,[elm,zentr]);
good:=good+1;
else
Info(InfoHomClass,5,"not in");
bad:=bad+1;
fi;
od;
od;
Info(InfoHomClass,4,good," good, ",bad," bad of ",Length(dc));
fi;
od;
od;
fi; # real subdirect product
fi; # else Fhom not faithful on factor
# uff. That was hard work. We're finally done with this layer.
lastM:=N;
fi; # else nonabelian
Info(InfoHomClass,1,"so far ",Length(cl)," classes computed");
od;
if Length(cs)<3 then
Info(InfoHomClass,1,"Fitting free factor returns ",Length(cl)," classes");
fi;
Assert( 1, Sum( List( cl, pair -> Size(G) / Size( pair[2] ) ) ) = Size(G) );
return cl;
end);
## Lifting code, using new format and compatible with matrix groups
#############################################################################
##
#F FFClassesVectorSpaceComplement( <N>, <p>, <gens>, <howmuch> )
##
## This function creates a record containing information about a complement
## in <N> to the span of <gens>.
##
# field, dimension, subgenerators (as vectors),howmuch
BindGlobal("FFClassesVectorSpaceComplement",function(field,r, Q,howmuch )
local zero, one, ran, n, nan, cg, pos, i, j, v;
one:=One( field); zero:=Zero(field);
ran:=[ 1 .. r ];
n:=Length( Q ); nan:=[ 1 .. n ];
cg:=rec( matrix :=[ ],
one :=one,
baseComplement:=ShallowCopy( ran ),
commutator :=0,
centralizer :=0,
dimensionN :=r,
dimensionC :=n );
if n = 0 or r = 0 then
cg.inverse:=NullMapMatrix;
cg.projection :=IdentityMat( r, one );
cg.needed :=[];
return cg;
fi;
for i in nan do
cg.matrix[ i ]:=Concatenation( Q[ i ], zero * nan );
cg.matrix[ i ][ r + i ]:=one;
od;
TriangulizeMat( cg.matrix );
pos:=1;
for v in cg.matrix do
while v[ pos ] = zero do
pos:=pos + 1;
od;
RemoveSet( cg.baseComplement, pos );
if pos <= r then cg.commutator :=cg.commutator + 1;
else cg.centralizer:=cg.centralizer + 1; fi;
od;
if howmuch=1 then
return Immutable(cg);
fi;
cg.needed :=[ ];
cg.projection :=IdentityMat( r, one );
# Find a right pseudo inverse for <Q>.
Append( Q, cg.projection );
Q:=MutableTransposedMat( Q );
TriangulizeMat( Q );
Q:=TransposedMat( Q );
i:=1;
j:=1;
while i <= r do
while j <= n and Q[ j ][ i ] = zero do
j:=j + 1;
od;
if j <= n and Q[ j ][ i ] <> zero then
cg.needed[ i ]:=j;
else
# If <Q> does not have full rank, terminate when the bottom row
# is reached.
i:=r;
fi;
i:=i + 1;
od;
if IsEmpty( cg.needed ) then
cg.inverse:=NullMapMatrix;
else
cg.inverse:=Q{ n + ran }
{ [ 1 .. Length( cg.needed ) ] };
cg.inverse:=ImmutableMatrix(field,cg.inverse,true);
fi;
if IsEmpty( cg.baseComplement ) then
cg.projection:=NullMapMatrix;
else
# Find a base change matrix for the projection onto the complement.
for i in [ 1 .. cg.commutator ] do
cg.projection[ i ][ i ]:=zero;
od;
Q:=[ ];
for i in [ 1 .. cg.commutator ] do
Q[ i ]:=cg.matrix[ i ]{ ran };
od;
for i in [ cg.commutator + 1 .. r ] do
Q[ i ]:=ListWithIdenticalEntries( r, zero );
Q[ i ][ cg.baseComplement[ i-r+Length(cg.baseComplement) ] ]
:=one;
od;
cg.projection:=cg.projection ^ Q;
cg.projection:=cg.projection{ ran }{ cg.baseComplement };
cg.projection:=ImmutableMatrix(field,cg.projection,true);
fi;
return cg;
end);
#############################################################################
##
#F VSDecompCentAction( <N>, <h>, <C>, <howmuch> )
##
## Given a homomorphism C -> N, c |-> [h,c], this function determines (a) a
## vector space decomposition N = [h,C] + K with projection onto K and (b)
## the ``kernel'' S < C which plays the role of C_G(h) in lemma 3.1 of
## [Mecky, Neub\"user, Bull. Aust. Math. Soc. 40].
##
BindGlobal("VSDecompCentAction",function( pcgs, h, C, field,howmuch )
local i, tmp, v,x,cg;
i:=One(field);
x:=List( C, c -> ExponentsOfPcElement(pcgs,Comm( h, c ) )*i);
#Print(Number(x,IsZero)," from ",Length(x),"\n");
cg:=FFClassesVectorSpaceComplement(field,Length(pcgs),x,howmuch);
tmp:=[ ];
for i in [ cg.commutator + 1 ..
cg.commutator + cg.centralizer ] do
v:=cg.matrix[ i ];
tmp[ i - cg.commutator ]:=PcElementByExponentsNC( C,
v{ [ cg.dimensionN + 1 ..
cg.dimensionN + cg.dimensionC ] } );
od;
Unbind(cg.matrix);
cg.cNh:=tmp;
return cg;
end);
#############################################################################
##
#F LiftClassesEANonsolvGeneral( <H>,<N>,<NT>,<cl> )
##
BindGlobal("LiftClassesEANonsolvGeneral",
function( H, Npcgs, cl, hom, pcisom,solvtriv,fran)
local classes, # classes to be constructed, the result
correctingelement,
field, # field over which <N> is a vector space
one,
h, # preimage `cl.representative' under <hom>
cg,
cNh, # centralizer of <h> in <N>
C, gens, # preimage `Centralizer( cl )' under <hom>
r, # dimension of <N>
ran, # constant range `[ 1 .. r ]'
aff, # <N> as affine space
imgs, M, # generating matrices for affine operation
orb, # orbit of affine operation
rep,# set of classes with canonical representatives
c, i, # loop variables
PPcgs,denomdepths,
reduce,
corr,
correctionfactor,
stabfac,
stabfacgens,
stabfacimg,
stabrad,
sz,gpsz,subsz,solvsz,
orblock,
stage,
b,j,
p,vp,genum,
st,gpe,
fe,epi,
repword,repwords,radidx,img,
radrange,farange,
ratio,
reps,
deno,docorrect,
k,failcnt,orpo,
stabilizergen,stabstack,
comm,s,stab;# for class correction
correctingelement:=function(h,rep,fe)
local comm;
comm:=Comm( h, fe ) * Comm( rep, fe );
comm:= ExponentsOfPcElement(Npcgs,comm)*one;
ConvertToVectorRep(comm,field);
comm := List(comm * cg.inverse,Int);
comm:=PcElementByExponentsNC
( Npcgs, Npcgs{ cg.needed }, -comm );
fe:=fe*comm;
return fe;
end;
h := cl[1];
field := GF( RelativeOrders( Npcgs )[ 1 ] );
one:=One(field);
PPcgs:=ParentPcgs(NumeratorOfModuloPcgs(Npcgs));
denomdepths:=ShallowCopy(DenominatorOfModuloPcgs(Npcgs)!.depthsInParent);
Add(denomdepths,Length(PPcgs)+1); # one
# Determine the subspace $[h,N]$ and calculate the centralizer of <h>.
#cNh := ExtendedPcgs( DenominatorOfModuloPcgs( N!.capH ),
# VSDecompCentAction( N, h, N!.capH ) );
#oldcg:=KernelHcommaC(Npcgs,h,NumeratorOfModuloPcgs(Npcgs),2);
#cg:=VSDecompCentAction( Npcgs, h, NumeratorOfModuloPcgs(Npcgs),field,2 );
cg:=VSDecompCentAction( Npcgs, h, Npcgs,field,2 );
#Print("complen =",Length(cg.baseComplement)," of ",cg.dimensionN,"\n");
#if Length(Npcgs)>5 then Error("cb"); fi;
cNh:=cg.cNh;
r := Length( cg.baseComplement );
ran := [ 1 .. r ];
# Construct matrices for the affine operation on $N/[h,N]$.
Info(InfoHomClass,4,"space=",Size(field),"^",r);
if Size(field)^r>3*10^8 then Error("too large");fi;
aff := ExtendedVectors( field ^ r );
gens:=Concatenation(cl[2],Npcgs,cl[3]); # all generators
#if ForAny(gens,x->Order(x)=1) then Error("HUH2"); fi;
gpsz:=cl[5];
solvsz:=cl[6];
radidx:=Length(Npcgs)+Length(cl[2]);
imgs := [ ];
for c in gens do
M := [ ];
for i in [ 1 .. r ] do
M[ i ] := Concatenation( ExponentsConjugateLayer( Npcgs,
Npcgs[ cg.baseComplement[ i ] ] , c )
* cg.projection, [ Zero( field ) ] );
od;
M[ r + 1 ] := Concatenation( ExponentsOfPcElement
( Npcgs, Comm( h, c ) ) * cg.projection,
[ One( field ) ] );
M:=ImmutableMatrix(field,M);
Add( imgs, M );
od;
#if Size(field)^r>10^7 then Error("BIG");fi;
# now compute orbits, being careful to get stabilizers in steps
#orbreps:=[];
#stabs:=[];
orb:=OrbitsRepsAndStabsVectorsMultistage(gens{[1..radidx]},
imgs{[1..radidx]},pcisom,solvsz,solvtriv,
gens{[radidx+1..Length(gens)]},
imgs{[radidx+1..Length(gens)]},cl[4],hom,gpsz,OnRight,aff);
classes:=[];
deno:=DenominatorOfModuloPcgs(Npcgs);
for b in orb do
rep := PcElementByExponentsNC( Npcgs, Npcgs{ cg.baseComplement },
b.rep{ ran } );
#Assert(2,ForAll(GeneratorsOfGroup(stabsub),i->Comm(i,h*rep) in NT));
stabrad:=ShallowCopy(b.stabradgens);
#Print("startdep=",List(stabrad,x->DepthOfPcElement(PPcgs,x)),"\n");
#if ForAny(stabrad,x->Order(x)=1) then Error("HUH3"); fi;
stabfacgens:=b.stabfacgens;
stabfacimg:=b.stabfacimgs;
# correct generators. Partially in Pc Image
if Length(cg.needed)>0 then
stabrad:=List(stabrad,x->correctingelement(h,rep,x));
# must make proper pcgs -- correction does not preserve that
stabrad:=TFMakeInducedPcgsModulo(PPcgs,stabrad,denomdepths);
# we change by radical elements, so the images in the factor don't
# change
stabfacgens:=List(stabfacgens,x->correctingelement(h,rep,x));
fi;
correctionfactor:=Characteristic(field)^Length(cg.needed);
subsz:=b.subsz/correctionfactor;
c := [h * rep,stabrad,stabfacgens,stabfacimg,subsz,
b.stabrsubsz/correctionfactor];
Assert(3,Size(Group(Concatenation(DenominatorOfModuloPcgs(Npcgs),
stabrad,stabfacgens)))=subsz);
Add(classes,c);
od;
return classes;
end);
#############################################################################
##
#F LiftClassesEANonsolvCentral( <H>, <N>, <cl> )
##
# the version for pc groups implicitly uses a pc-group orbit-stabilizer
# algorithm. We can't do this but have to use a more simple-minded
# orbit/stabilizer approach.
BindGlobal("LiftClassesEANonsolvCentral",
function( H, Npcgs, cl,hom,pcisom,solvtriv,fran )
local classes, # classes to be constructed, the result
field, # field over which <Npcgs> is a vector space
o,
n,r, # dimensions
space,
com,
comms,
mats,
decomp,
reduce,
gens,
radidx,
stabrad,stabfacgens,stabfacimg,stabrsubsz,relo,orblock,fe,st,
orb,rep,reps,repword,repwords,p,stabfac,img,vp,genum,gpsz,
subsz,solvsz,i,j,
v,
h, # preimage `cl.representative' under <hom>
C, # preimage `Centralizer( cl )' under <hom>
w, # coefficient vectors for projection along $[h,N]$
c; # loop variable
field := GF( RelativeOrders( Npcgs )[ 1 ] );
h := cl[1];
#reduce:=ReducedPermdegree(C);
#if reduce<>fail then
# C:=Image(reduce,C);
# Info(InfoHomClass,4,"reduced to deg:",NrMovedPoints(C));
# h:=Image(reduce,h);
# N:=ModuloPcgs(SubgroupNC(C,Image(reduce,NumeratorOfModuloPcgs(N))),
# SubgroupNC(C,Image(reduce,DenominatorOfModuloPcgs(N))));
# fi;
# centrality still means that conjugation by c is multiplication with
# [h,c] and that the complement space is generated by commutators [h,c]
# for a generating set {c|...} of C.
field:=GF(RelativeOrders(Npcgs)[1]);
n:=Length(Npcgs);
o:=One(field);
stabrad:=Concatenation(cl[2],Npcgs);
radidx:=Length(stabrad);
stabfacgens:=cl[3];
stabfacimg:=cl[4];
gpsz:=cl[5];
subsz:=gpsz;
solvsz:=cl[6];
stabfac:=TrivialSubgroup(Image(hom));
gens:=Concatenation(stabrad,stabfacgens); # all generators
# commutator space basis
comms:=List(gens,c->o*ExponentsOfPcElement(Npcgs,Comm(h,c)));
List(comms,x->ConvertToVectorRep(x,field));
space:=List(comms,ShallowCopy);
TriangulizeMat(space);
space:=Filtered(space,i->i<>Zero(i)); # remove spurious columns
com:=BaseSteinitzVectors(IdentityMat(n,field),space);
# decomposition of vectors into the subspace basis
r:=Length(com.subspace);
if r>0 then
# if the subspace is trivial, everything stabilizes
decomp:=Concatenation(com.subspace,com.factorspace)^-1;
decomp:=decomp{[1..Length(decomp)]}{[1..r]};
decomp:=ImmutableMatrix(field,decomp);
# build matrices for the affine action
mats:=[];
for w in comms do
c:=IdentityMat(r+1,o);
c[r+1]{[1..r]}:=w*decomp; # translation bit
c:=ImmutableMatrix(field,c);
Add(mats,c);
od;
#subspace affine enumerator
v:=ExtendedVectors(field^r);
# orbit-stabilizer algorithm solv/nonsolv version
#C := Stabilizer( C, v, v[1],GeneratorsOfGroup(C), mats,OnPoints );
# assume small domain -- so no bother with bitlist
orb:= [v[1]];
reps:=[One(gens[1])];
repwords:=[[]];
stabrad:=[];
stabrsubsz:=Size(solvtriv);
vp:=1;
for genum in [radidx,radidx-1..1] do
relo:=RelativeOrders(pcisom!.sourcePcgs)[
DepthOfPcElement(pcisom!.sourcePcgs,gens[genum])];
img:=orb[1]*mats[genum];
repword:=repwords[vp];
p:=Position(orb,img);
if p=fail then
for j in [1..Length(orb)*(relo-1)] do
img:=orb[j]*mats[genum];
Add(orb,img);
Add(reps,reps[j]*gens[genum]);
Add(repwords,repword);
od;
else
rep:=gens[genum]/reps[p];
Add(stabrad,rep);
stabrsubsz:=stabrsubsz*relo;
fi;
od;
stabrad:=Reversed(stabrad);
Assert(1,solvsz=stabrsubsz*Length(orb));
#nosolvable part
orblock:=Length(orb);
vp:=1;
stabfacgens:=[];
stabfacimg:=[];
while vp<=Length(orb) do
for genum in [radidx+1..Length(gens)] do
img:=orb[vp]*mats[genum];
rep:=reps[vp]*gens[genum];
repword:=Concatenation(repwords[vp],[genum-radidx]);
p:=Position(orb,img);
if p=fail then
Add(orb,img);
Add(reps,rep);
Add(repwords,repword);
for j in [1..orblock-1] do
img:=orb[vp+j]*mats[genum];
#if img in orb then Error("HUH");fi;
Add(orb,img);
Add(reps,reps[vp+j]*gens[genum]);
# repword stays the same!
Add(repwords,repword);
od;
else
st:=rep/reps[p];
if Length(repword)>0 then
# build the factor group element
fe:=One(Image(hom));
for i in repword do
fe:=fe*cl[4][i];
od;
for i in Reversed(repwords[p]) do
fe:=fe/cl[4][i];
od;
if not fe in stabfac then
# not known -- add to generators
Add(stabfacgens,st);
Add(stabfacimg,fe);
stabfac:=ClosureGroup(stabfac,fe);
fi;
fi;
fi;
od;
vp:=vp+orblock;
od;
subsz:=stabrsubsz*Size(stabfac);
else
stabrsubsz:=solvsz;
fi;
if Length(com.factorspace)=0 then
classes :=[[h,stabrad,stabfacgens,stabfacimg,subsz,stabrsubsz]];
else
classes:=[];
# enumerator of complement
v:=field^Length(com.factorspace);
for w in v do
c := [h * PcElementByExponentsNC( Npcgs,w*com.factorspace),
stabrad,stabfacgens,stabfacimg,subsz,stabrsubsz];
#if reduce<>fail then
# Add(classes,[PreImagesRepresentative(reduce,c[1]),
# PreImage(reduce,c[2])]);
# else
Assert(3,c[6]
=Size(Group(Concatenation(c[2],DenominatorOfModuloPcgs(Npcgs)))));
Add(classes,c);
# fi;
od;
fi;
# Assert(1,ForAll(classes,i->i[1] in H and IsSubset(H,i[2])));
return classes;
end);
#############################################################################
##
#F LiftClassesEATrivRep
##
BindGlobal("LiftClassesEATrivRep",
function( H, Npcgs, cl, fants,hom, pcisom,solvtriv)
local classes, # classes to be constructed, the result
h,field,one,solvsz,radidx,gens,imgs,M,bas,
gpsz,c,i,npcgsact,usent,dim,found,nsgens,ntgens,nsimgs,mo,
basis, ssidx,cpidx,compl,pcgsimgs,pcgssel,
sel,pcgs,fasize,nsfgens,fgens,a,norb,fstab,rep,reps,frep,freps,
orb,p,rsgens,el,img,j,basinv,newo,orbslev,ssd,result,o,subs,orbsub,
sgens,sfgens,z,minvecs,orpo,norpo,maxorb,
IteratedMinimizer,OrbitMinimizer,Minimizer,miss;
npcgsact:=function(c)
local M,i;
M := [ ];
for i in [ 1 .. dim ] do
M[ i ] := ExponentsConjugateLayer( Npcgs,
Npcgs[ i ] , c )*one;
od;
M:=ImmutableMatrix(field,M);
return M;
end;
pcgs:=MappingGeneratorsImages(pcisom)[1];
field:=GF(RelativeOrders(Npcgs)[1]);
one:=One(field);
dim:=Length(Npcgs);
# action of group
h := cl[1];
gens:=Concatenation(cl[2],Npcgs,cl[3]); # all generators
fgens:=Concatenation(ListWithIdenticalEntries(
Length(Npcgs)+Length(cl[2]),One(Range(hom))),cl[4]);
gpsz:=cl[5];
solvsz:=cl[6];
radidx:=Length(Npcgs)+Length(cl[2]);
imgs := [ ];
for c in gens do
Add( imgs, npcgsact(c));
od;
sel:=Filtered([1..Length(imgs)],x->Order(imgs[x])>1);
usent:=0;
found:=0;
while usent<Length(fants) do
usent:=usent+1;
nsfgens:=NormalIntersection(fants[usent],Group(cl[4]));
fasize:=Size(nsfgens);
nsfgens:=SmallGeneratingSet(nsfgens);
nsgens:=List(nsfgens,x->PreImagesRepresentative(hom,x));
nsimgs:=List(Concatenation(pcgs,nsgens),npcgsact);
mo:=GModuleByMats(nsimgs,field);
if not MTX.IsIrreducible(mo) then
# split space as direct sum under normal sub -- clifford Theory
o:=MTX.BasesMinimalSubmodules(mo);
if Length(o)>50 then
o:=o{Set(List([1..50],x->Random([1..Length(o)])))};
fi;
for i in Filtered([1..Length(o)],
x->(mo.dimension mod Length(o[x])=0) and Length(o[x])>found) do
# subspace and images as orbit
bas:=o[i];
ssd:=Length(bas);
if found<ssd and Size(field)^ssd<3*10^7 then
Info(InfoHomClass,2,"Trying subspace ",ssd," in ",mo.dimension);
orbsub:=Orbit(Group(imgs{sel}),bas,OnSubspacesByCanonicalBasis);
if Length(orbsub)*Length(bas)<>Length(bas[1]) then
subs:=MTX.InducedActionSubmodule(mo,bas);
subs:=MTX.Homomorphisms(subs,mo);
orbsub:=Filtered(subs,x->x in orbsub);
fi;
if Length(orbsub)*Length(bas)=Length(bas[1]) and
RankMat(Concatenation(orbsub))=Length(bas[1]) then
found:=ssd;
el:=[orbsub,bas,fasize,nsgens,nsimgs,nsfgens,mo];
subs:=List([1..Length(orbsub)],x->[(x-1)*ssd+1..x*ssd]);
bas:=ImmutableMatrix(field,Concatenation(orbsub)); # this is the new basis
basinv:=bas^-1;
Assert(1,basinv<>fail);
else
Info(InfoHomClass,3,"failed ",Length(orbsub));
fi;
fi;
od;
fi;
od;
if found=0 then
Info(InfoHomClass,3,"basic case");
#Error("BASIC");
return fail;
else
ssd:=found;
#el is [orbsub,bas,fasize,nsgens,nsimgs,nsfgens,mo];
orbsub:=el[1];
bas:=el[2];
fasize:=el[3];
nsgens:=el[4];
nsimgs:=el[5];
nsfgens:=el[6];
mo:=el[7];
Info(InfoHomClass,2,"Using subspace ",ssd," in ",mo.dimension);
subs:=List([1..Length(orbsub)],x->[(x-1)*ssd+1..x*ssd]);
bas:=ImmutableMatrix(field,Concatenation(orbsub)); # this is the new basis
basinv:=bas^-1;
fi;
imgs:=List(imgs,x->bas*x*basinv); # write wrt new basis
# now determine N-orbits, stepwise
solvtriv:=Subgroup(Range(pcisom),
List(DenominatorOfModuloPcgs(Npcgs),x->ImagesRepresentative(pcisom,x)));
orb:=[rec(len:=1,rep:=Zero(bas[1]),
stabfacgens:=nsgens,
stabfacimgs:=nsfgens,
# only generators in factor
stabradgens:=Filtered(pcgs,x->not x in DenominatorOfModuloPcgs(Npcgs)),
stabrsubsz:=Size(Image(pcisom)),
subsz:=fasize*Product(RelativeOrders(pcgs))
)];
orbslev:=[];
maxorb:=1;
for i in [1..Length(subs)] do
norb:=[];
el:=Elements(VectorSpace(field,IdentityMat(Length(bas),field){subs[i]}));
for o in orb do
newo:= OrbitsRepsAndStabsVectorsMultistage(
o.stabradgens,List(o.stabradgens,x->bas*npcgsact(x)*basinv),
pcisom,o.stabrsubsz,solvtriv,
o.stabfacgens,List(o.stabfacgens,x->bas*npcgsact(x)*basinv),
o.stabfacimgs,hom,o.subsz,OnRight,
el);
for j in newo do
if j.len>maxorb then maxorb:=j.len;fi;
if i>1 then
j.len:=j.len*o.len;
j.rep:=Concatenation(o.rep{[1..(i-1)*ssd]},j.rep{[(i-1)*ssd+1..Length(j.rep)]});
MakeImmutable(j.rep);
fi;
Add(norb,j);
od;
od;
Info(InfoHomClass,3,"Level ",i," , ",Length(norb)," orbits");
orb:=norb;
Add(orbslev,ShallowCopy(orb));
od;
IteratedMinimizer:=function(vec,allcands)
local i,stops,a,cands,mapper,fmapper,stabfacgens,stabradgens,stabfacimgs,
range,lcands,lvec;
cands:=allcands;
mapper:=One(Source(hom));
fmapper:=One(Range(hom));
stabfacgens:=nsgens;
stabfacimgs:=nsfgens;
stabradgens:=pcgs;
for i in [1..Length(subs)] do
range:=[1..i*ssd];
lcands:=Filtered(orbslev[i],
x->ForAny(cands,y->y.rep{range}=x.rep{range}));
lvec:=Concatenation(vec{range},Zero(vec{[i*ssd+1..Length(vec)]}));
result:=OrbitMinimumMultistage(stabradgens,
List(stabradgens,x->bas*npcgsact(x)*basinv),
pcisom,0,0, # solvable size not needed
stabfacgens,
List(stabfacgens,x->bas*npcgsact(x)*basinv),
stabfacimgs,
hom,0, #gpsz not needed
OnRight,lvec,maxorb,#Maximum(List(lcands,x->x.len)),
Set(List(lcands,x->x.rep)));
a:=First(lcands,x->x.rep{range}=result.min{range});
mapper:=mapper*result.elm;
fmapper:=fmapper*result.felm;
vec:=vec*bas*npcgsact(result.elm)*basinv; # map vector to so far canonical
# not all classes are feasible
Assert(1,ForAny(cands,x->x.rep{range}=vec{range}));
cands:=Filtered(cands,x->x.rep{range}=vec{range});
stabradgens:=a.stabradgens;
stabfacgens:=a.stabfacgens;
stabfacimgs:=a.stabfacimgs;
od;
if Length(cands)<>1 then Error("nonunique");fi;
return rec(elm:=mapper,felm:=fmapper,min:=vec,nclass:=cands[1]);
end;
pcgsimgs:=List(pcgs,x->bas*npcgsact(x)*basinv);
pcgssel:=Filtered([1..Length(pcgs)],x->not IsOne(pcgsimgs[x]));
nsimgs:=List(nsgens,x->bas*npcgsact(x)*basinv);
OrbitMinimizer:=function(vec,allcands)
local a;
if false and allcands[1].len>1 then
Error();
fi;
a:=OrbitMinimumMultistage(pcgs,pcgsimgs,pcisom,0,0,
nsgens,nsimgs,nsfgens,hom,0,
OnRight,vec,allcands[1].len,minvecs);
a.nclass:=First(allcands,x->x.rep=a.min);
return a;
end;
orpo:=NewDictionary(orb[Length(orb)].rep,true,field^Length(orb[1].rep));
for p in [1..Length(orb)] do
AddDictionary(orpo,orb[p].rep,p);
od;
# now do an orbit algorithm on orb. As the orbit is short no need for
# two-step.
newo:=[];
while Length(orb)>0 do
# pick new one
p:=First([1..Length(orb)],x->IsBound(orb[x]));
norb:=[orb[p]];
norpo:=[];
norpo[p]:=1;
el:=Filtered(orb,x->x.len=orb[p].len);
minvecs:=Set(List(el,x->x.rep));
#el:=orbslev[3];
if orb[p].len>30000 then
Minimizer:=IteratedMinimizer;
else
Minimizer:=OrbitMinimizer;
fi;
# as Rad <=N we can assume that the radical part of the stabilizer
# is known
rsgens:=ShallowCopy(orb[p].stabradgens);
a:=Difference([1..Length(gens)],sel);
sgens:=Concatenation(orb[p].stabfacgens,gens{a});
sfgens:=Concatenation(orb[p].stabfacimgs,fgens{a});
fstab:=Group(sfgens);
reps:=[One(Source(hom))];
freps:=[One(Range(hom))];
Unbind(orb[p]);
# factor missing from stop
miss:=cl[5]/(norb[1].len*Size(fstab)*norb[1].stabrsubsz);
i:=1;
while i<=Length(norb) and miss>1 do
for j in sel do
img:=OnRight(norb[i].rep,imgs[j]);
img:=Minimizer(img,el);
rep:=reps[i]*gens[j]*img.elm;
frep:=freps[i]*fgens[j]*img.felm;
p:=LookupDictionary(orpo,img.min);
#p:=PositionProperty(norb,x->x.rep=img.min);
if p=fail then
Error("unknown minimum");
elif IsBound(norpo[p]) then
# old point
p:=norpo[p];
if miss>=2 then
Assert(1,norb[i].rep*imgs[j]*bas*npcgsact(img.elm)*basinv=norb[p].rep);
#Print("A",i," ",j," ",Length(el),"\n");
# old point -- stabilize
a:=frep/freps[p];
if not a in sfgens then
Add(sgens,rep/reps[p]);
Add(sfgens,a);
miss:=miss*Size(fstab);
fstab:=ClosureGroup(fstab,a);
miss:=miss/Size(fstab);
#Print("miss1:",EvalF(miss)," ",i," of ",Length(norb),"\n");
fi;
fi;
else
#Print("B",i," ",j," ",Length(el),"\n");
# new point
#p:=PositionProperty(orb,x->x.rep=img.min);
Assert(1,norb[i].rep*imgs[j]*bas*npcgsact(img.elm)*basinv=orb[p].rep);
Add(norb,orb[p]);
norpo[p]:=Length(norb);
Add(reps,rep);
Add(freps,frep);
miss:=miss*(Length(norb)-1)/Length(norb);
#Print("miss3:",EvalF(miss)," ",i," of ",Length(norb),"\n");
# add conjugate stabilizer
#Append(rsgens,List(orb[p].stabradgens,x->rep*x/rep));
for z in [1..Length(orb[p].stabfacgens)] do
a:=frep*orb[p].stabfacimgs[z]/frep;
if not a in fstab then
Add(sgens,rep*orb[p].stabfacgens[z]/rep);
Add(sfgens,a);
miss:=miss*Size(fstab);
fstab:=ClosureGroup(fstab,a);
miss:=miss/Size(fstab);
#Print("miss2:",miss,"\n");
fi;
od;
Unbind(orb[p]);
fi;
od;
i:=i+1;
od;
if miss<>1 then
# something is dodgy -- fallback to the default algorithm
return fail;Error("HEH?");fi;
Info(InfoHomClass,3,"Fused ",Length(norb),"*",norb[1].len," ",
Number(orb,x->IsBound(x))," left");
Assert(0,ForAll(rsgens,x->norb[1].rep*bas*npcgsact(x)*basinv=norb[1].rep));
Assert(0,ForAll(sgens,x->norb[1].rep*bas*npcgsact(x)*basinv=norb[1].rep));
#if ForAny(rsgens,x->Order(x)=1) then Error("HUH5"); fi;
a:=[h*PcElementByExponents(Npcgs,norb[1].rep*bas),rsgens,sgens,sfgens,
cl[5]/Length(norb)/norb[1].len, norb[1].stabrsubsz];
#rsgens:=List(rsgens,x->ImageElm(pcisom,x));
#if rsgens<>InducedPcgsByGenerators(FamilyPcgs(Range(pcisom)),rsgens) then
# Error("nonpcgs!");
#fi;
Add(newo,a);
od;
return newo;
end);
InstallGlobalFunction(ConjugacyClassesViaRadical,function (G)
local r, #radical
f, # G/r
hom, # G->f
pcgs,mpcgs, #(modulo) pcgs
pcisom,
gens,
ser, # series
radsize,len,ntrihom,
mran,nran,fran,
central,
fants,
d,
solvtriv,
M,N, # normal subgrops
ind, # indices
i, #loop
new, # new classes
cl,ncl; # classes
# it seems to be cleaner (and avoids deferring abelian factors) if we
# factor out the radical first. (Note: The radical method for perm groups
# stores the nat hom.!)
ser:=FittingFreeLiftSetup(G);
radsize:=Product(RelativeOrders(ser.pcgs));
len:=Length(ser.pcgs);
if radsize=1 then
cl:=ConjugacyClassesFittingFreeGroup(G:onlysizes:=false);
ncl:=[];
for i in cl do
r:=ConjugacyClass(G,i[1],i[2]);
Add(ncl,r);
od;
return ncl;
fi;
pcgs:=ser.pcgs;
pcisom:=ser.pcisom;
fants:=[];
# store centralizers as rep, centralizer generators in radical,
# centralizer generators with nontrivial
# radfactor image, corresponding radfactor images
# the generators in the radical do not list the generators of the
# current layer after immediate lifting.
if radsize=Size(G) then
# solvable case
hom:=ser.factorhom;
d:=MappingGeneratorsImages(hom);
mran:=Filtered([1..Length(d[2])],x->not IsOne(d[2][x]));
cl:=[[One(G),[],d[1]{mran},d[2]{mran},Size(G),Size(G)]];
else
# nonsolvable
if radsize>1 then
hom:=ser.factorhom;
ntrihom:=true;
f:=Image(hom);
# we need centralizers
cl:=ConjugacyClassesFittingFreeGroup(f:onlysizes:=false);
fants:=Filtered(NormalSubgroups(f),x->Size(x)>1 and Size(x)<Size(f));
else
if IsPermGroup(G) then
hom:=SmallerDegreePermutationRepresentation(G);
ntrihom:=not IsOne(hom);;
else
hom:=IdentityMapping(G);
ntrihom:=false;
fi;
f:=Image(hom);
cl:=ConjugacyClassesFittingFreeGroup(f);
fi;
if ntrihom then
ncl:=[];
for i in cl do
new:=[PreImagesRepresentative(hom,i[1])];
if not IsInt(i[2]) then
Add(new,[]); # no generators in radical yet
gens:=SmallGeneratingSet(i[2]);
Add(new,
List(gens,x->PreImagesRepresentative(hom,x)));
Add(new,gens);
#TODO: PreImage groups?
#Add(new,PreImage(hom,i[2]));
Add(new,radsize*Size(i[2]));
Add(new,radsize);
fi;
Add(ncl,new);
od;
cl:=ncl;
fi;
fi;
Assert(3,ForAll(cl,x->x[6]=Size(Group(Concatenation(x[2],pcgs)))));
for d in [2..Length(ser.depths)] do
#M:=ser[i-1];
#N:=ser[i];
mran:=[ser.depths[d-1]..len];
nran:=[ser.depths[d]..len];
fran:=[mran,nran];
mpcgs:=InducedPcgsByPcSequenceNC(pcgs,pcgs{mran}) mod
InducedPcgsByPcSequenceNC(pcgs,pcgs{nran});
central:= ForAll(GeneratorsOfGroup(G),
i->ForAll(mpcgs,
j->DepthOfPcElement(pcgs,Comm(i,j))>=ser.depths[d]));
# abelian factor, use affine methods
Info(InfoHomClass,1,"abelian factor ",d,": ",
Product(RelativeOrders(ser.pcgs){mran}), "->",
Product(RelativeOrders(ser.pcgs){nran})," central:",central);
ncl:=[];
solvtriv:=Subgroup(Range(pcisom),
List(DenominatorOfModuloPcgs(mpcgs),x->ImagesRepresentative(pcisom,x)));
for i in cl do
#Assert(2,ForAll(GeneratorsOfGroup(i[2]),j->Comm(i[1],j) in M));
if (central or ForAll(Concatenation(i[2],i[3]),
i->ForAll(mpcgs,
j->DepthOfPcElement(pcgs,Comm(i,j))>=ser.depths[d])) ) then
Info(InfoHomClass,3,"central step");
new:=LiftClassesEANonsolvCentral(G,mpcgs,i,hom,pcisom,solvtriv,fran);
elif Length(fants)>0 and Order(i[1])=1 then
# special case for trivial representetive
new:=LiftClassesEATrivRep(G,mpcgs,i,fants,hom,pcisom,solvtriv);
if new=fail then
new:=LiftClassesEANonsolvGeneral(G,mpcgs,i,hom,pcisom,solvtriv,fran);
fi;
else
new:=LiftClassesEANonsolvGeneral(G,mpcgs,i,hom,pcisom,solvtriv,fran);
fi;
#Assert(3,ForAll(new,x->x[6]
# =Size(Group(Concatenation(x[2],DenominatorOfModuloPcgs(mpcgs))))));
#if ForAny(new,x->x[2]<>TFMakeInducedPcgsModulo(pcgs,x[2],nran)) then Error("HUH6");fi;
#Print(List(new,x->List(x[2],y->DepthOfPcElement(pcgs,y))),"\n");
#Assert(1,ForAll(new, i->ForAll(GeneratorsOfGroup(i[2]),j->Comm(j,i[1]) in N)));
ncl:=Concatenation(ncl,new);
Info(InfoHomClass,2,Length(new)," new classes (",Length(ncl)," total)");
od;
cl:=ncl;
Info(InfoHomClass,1,"Now: ",Length(cl)," classes (",Length(ncl)," total)");
od;
if Order(cl[1][1])>1 then
# the identity is not in first position
Info(InfoHomClass,2,"identity not first, sorting");
Sort(cl,function(a,b) return Order(a[1])<Order(b[1]);end);
fi;
Info(InfoHomClass,1,"forming classes");
ncl:=[];
for i in cl do
if IsInt(i[2]) then
r:=ConjugacyClass(G,i[1]);
SetSize(r,Size(G)/i[2]);
else
d:=SubgroupByFittingFreeData(G,i[3],i[4],i[2]);
Assert(1,Size(d)=i[5]);
Assert(2,Centralizer(G,i[1])=d);
SetSize(d,i[5]);
r:=ConjugacyClass(G,i[1],d);
SetSize(r,Size(G)/i[5]);
fi;
Add(ncl,r);
od;
# as this test is cheap, do it always
if Sum(ncl,Size)<>Size(G) then
Error("wrong classes");
fi;
cl:=ncl;
return cl;
end);
#############################################################################
##
#F LiftConCandCenNonsolvGeneral( <H>,<N>,<NT>,<cl> )
##
BindGlobal("LiftConCandCenNonsolvGeneral",
function( H, Npcgs, reps, hom, pcisom,solvtriv,fran)
local nreps, # new reps to be constructed, the result
correctingelement,
minvec,
cano, # element that will be canonical
cl,
field, # field over which <N> is a vector space
one,
h, # preimage `cl.representative' under <hom>
cg,
cNh, # centralizer of <h> in <N>
C, gens, # preimage `Centralizer( cl )' under <hom>
r, # dimension of <N>
ran, # constant range `[ 1 .. r ]'
aff, # <N> as affine space
imgs, M, # generating matrices for affine operation
orb, # orbit of affine operation
rep,# set of classes with canonical representatives
c, i, # loop variables
PPcgs,denomdepths,
reduce,
corr,
correctionfactor,
censize,cenradsize,
stabfac,
stabfacgens,
stabfacimgs,
stabrad,
sz,gpsz,subsz,solvsz,
orblock,
stage,
b,j,x,
minimal,minstab,mappingelm,
p,vp,genum,
st,gpe,
fe,epi,
repword,repwords,radidx,img,
radrange,farange,
ratio,
deno,docorrect,
k,failcnt,orpo,
stabilizergen,stabstack,
sel,
comm,s,stab;# for class correction
correctingelement:=function(h,rep,fe)
local comm;
comm:=Comm( h, fe ) * Comm( rep, fe );
comm:= ExponentsOfPcElement(Npcgs,comm)*one;
ConvertToVectorRep(comm,field);
comm := List(comm * cg.inverse,Int);
comm:=PcElementByExponentsNC
( Npcgs, Npcgs{ cg.needed }, -comm );
fe:=fe*comm;
return fe;
end;
mappingelm:=function(orb,pos)
local mc,mcf,i;
mc:=One(Source(hom));
mcf:=One(Range(hom));
for i in orb.repwords[pos] do
mc:=mc*orb.gens[i];
mcf:=mcf*orb.fgens[i];
od;
i:=pos mod orb.orblock;
if i=0 then i:=orb.orblock;fi;
mc:=orb.reps[i]*mc;
return [mc,mcf];
end;
# all reps given must have the same canonical representative on the level
# above. So they also all have the same centralizer and we can use this.
cl:=reps[1];
h := cl[3];
field := GF( RelativeOrders( Npcgs )[ 1 ] );
one:=One(field);
PPcgs:=ParentPcgs(NumeratorOfModuloPcgs(Npcgs));
denomdepths:=ShallowCopy(DenominatorOfModuloPcgs(Npcgs)!.depthsInParent);
Add(denomdepths,Length(PPcgs)+1); # one
# Determine the subspace $[h,N]$ and calculate the centralizer of <h>.
#cNh := ExtendedPcgs( DenominatorOfModuloPcgs( N!.capH ),
# VSDecompCentAction( N, h, N!.capH ) );
#oldcg:=KernelHcommaC(Npcgs,h,NumeratorOfModuloPcgs(Npcgs),2);
#cg:=VSDecompCentAction( Npcgs, h, NumeratorOfModuloPcgs(Npcgs),field,2 );
cg:=VSDecompCentAction( Npcgs, h, Npcgs,field,2 );
#Print("complen =",Length(cg.baseComplement)," of ",cg.dimensionN,"\n");
#if Length(Npcgs)>5 then Error("cb"); fi;
cNh:=cg.cNh;
r := Length( cg.baseComplement );
ran := [ 1 .. r ];
# Construct matrices for the affine operation on $N/[h,N]$.
Info(InfoHomClass,4,"space=",Size(field),"^",r);
if Size(field)^r>3*10^8 then Error("too large");fi;
aff := ExtendedVectors( field ^ r );
# Format for cl is:
# 1:Element, 2: Conjugate element, 3: Element that will be canonical
# in factor, 4:conjugator, 5:cenpcgs,
# 6:cenfac, 7:cenfacimgs, 8:censize, 9:cenfacsize
gens:=Concatenation(cl[5],Npcgs,cl[6]); # all generators
#if ForAny(gens,x->Order(x)=1) then Error("HUH2"); fi;
gpsz:=cl[8];
solvsz:=cl[8]/cl[9];
radidx:=Length(Npcgs)+Length(cl[5]);
imgs := [ ];
for c in gens do
M := [ ];
for i in [ 1 .. r ] do
M[ i ] := Concatenation( ExponentsConjugateLayer( Npcgs,
Npcgs[ cg.baseComplement[ i ] ] , c )
* cg.projection, [ Zero( field ) ] );
od;
M[ r + 1 ] := Concatenation( ExponentsOfPcElement
( Npcgs, Comm( h, c ) ) * cg.projection,
[ One( field ) ] );
M:=ImmutableMatrix(field,M);
Add( imgs, M );
od;
#if Size(field)^r>10^7 then Error("BIG");fi;
# now compute orbits, being careful to get stabilizers in steps
#orbreps:=[];
#stabs:=[];
# change reps to list of more general format
nreps:=[];
for x in reps do
p:=rec(list:=x);
p.vector:=ExponentsOfPcElement(Npcgs,LeftQuotient(h,x[2]))*One(field);
p.exponents:=ShallowCopy(p.vector);
ConvertToVectorRep(p.vector,field);
p.vector:=p.vector*cg.projection;
Add(p.vector,One(field));
Add(nreps,p);
od;
reps:=nreps;
nreps:=[];
sel:=[1..Length(reps)];
while Length(sel)>0 do
p:=sel[1]; # the one to do
RemoveSet(sel,p);
orb:=OrbitsRepsAndStabsVectorsMultistage(gens{[1..radidx]},
imgs{[1..radidx]},
pcisom,solvsz,solvtriv,
gens{[radidx+1..Length(gens)]},
imgs{[radidx+1..Length(gens)]},reps[p].list[7],hom,gpsz,OnRight,
aff:orbitseed:=reps[p].vector);
orb:=orb[1];
# find minimal element, mapper, stabilizer of minimal element
minvec:=Minimum(orb.orbit);
minimal:=mappingelm(orb,Position(orb.orbit,minvec));
# get the real minimum, including N-Orbit
corr:=ExponentsOfPcElement(Npcgs,
LeftQuotient(h,reps[p].list[2]^minimal[1]));
corr:=PcElementByExponentsNC(Npcgs,Npcgs{cg.needed},-corr*cg.inverse);
minimal[1]:=minimal[1]*corr; # real minimizer
# element that will be the canonical representative in the factor (tail
# zeroed out)
corr:=ExponentsOfPcElement(Npcgs,
LeftQuotient(h,reps[p].list[2]^minimal[1]));
cano:=h*PcElementByExponents(Npcgs,corr);
# this will not be a pcgs, but we induce later anyhow
stabrad:=List(orb.stabradgens,x->x^minimal[1]);
stabfacgens:=List(orb.stabfacgens,x->x^minimal[1]);
stabfacimgs:=List(orb.stabfacimgs,x->x^minimal[2]);
censize:=orb.subsz;
cenradsize:=orb.stabrsubsz;
# correct generators. Partially in Pc Image
if Length(cg.needed)>0 then
rep:=LeftQuotient(h,reps[p].list[2]^minimal[1]);
stabrad:=List(stabrad,x->correctingelement(h,rep,x));
# must make proper pcgs -- correction does not preserve that
stabrad:=TFMakeInducedPcgsModulo(PPcgs,stabrad,denomdepths);
# we change by radical elements, so the images in the factor don't
# change
stabfacgens:=List(stabfacgens,x->correctingelement(h,rep,x));
correctionfactor:=Characteristic(field)^Length(cg.needed);
censize:=censize/correctionfactor;
cenradsize:=cenradsize/correctionfactor;
fi;
# Format for cl is:
# 1:Element, 2: Conjugate element, 3: Element that will be canonical
# in factor, 4:conjugator, 5:cenpcgs,
# 6:cenfac, 7:cenfacimgs, 8:censize, 9:cenfacsize
Add(nreps,[reps[p].list[1],
reps[p].list[2]^minimal[1],
cano,
reps[p].list[4]*minimal[1],
stabrad,stabfacgens,stabfacimgs,
censize,censize/cenradsize]);
for cl in sel do
b:=Position(orb.orbit,reps[cl].vector);
if b<>fail then
RemoveSet(sel,cl);
# now find rep mapping 1 here
b:=mappingelm(orb,b);
b:=[LeftQuotient(b[1],minimal[1]),
LeftQuotient(b[2],minimal[2])];
# get the real minimum, including N-Orbit
corr:=ExponentsOfPcElement(Npcgs,
LeftQuotient(h,reps[cl].list[2]^b[1]));
corr:=PcElementByExponentsNC(Npcgs,Npcgs{cg.needed},corr*cg.inverse);
b[1]:=b[1]/corr; # real minimizer
# Format for cl is:
# 1:Element, 2: Conjugate element, 3: Element that will be canonical
# in factor, 4:conjugator, 5:cenpcgs,
# 6:cenfac, 7:cenfacimgs, 8:censize, 9:cenfacsiz
Add(nreps,[reps[cl].list[1],
reps[cl].list[2]^b[1],
cano,
reps[cl].list[4]*b[1],
stabrad,stabfacgens,stabfacimgs,
censize,censize/cenradsize]);
elif ValueOption("conjugacytest")=true then
# in conj test this would mean fail
return fail;
fi;
od;
od;
return nreps;
end);
# canonical rep/centralizer
BindGlobal("TFCanonicalClassRepresentative",function (G,candidates)
local r, #radical
f, # G/r
hom, # G->f
prereps, # fixed factor class reps preimages
pcgs,mpcgs, #(modulo) pcgs
pcisom,
gens,
ser, # series
radsize,len,ntrihom,
mran,nran,fran,
central,
#fants,
reps,
nreps,
fr,
conj,
d,
solvtriv,
select,sel,pos,
M,N, # normal subgrops
ind, # indices
i,j, #loop
new, # new classes
classrange,
cl,ncl; # classes
# it seems to be cleaner (and avoids deferring abelian factors) if we
# factor out the radical first. (Note: The radical method for perm groups
# stores the nat hom.!)
ser:=FittingFreeLiftSetup(G);
radsize:=Product(RelativeOrders(ser.pcgs));
len:=Length(ser.pcgs);
pcgs:=ser.pcgs;
pcisom:=ser.pcisom;
#fants:=fail;
# store centralizers as rep, centralizer generators in radical,
# centralizer generators with nontrivial
# radfactor image, corresponding radfactor images
# the generators in the radical do not list the generators of the
# current layer after immediate lifting.
if radsize=Size(G) then
# solvable case
hom:=ser.factorhom;
d:=MappingGeneratorsImages(hom);
mran:=Filtered([1..Length(d[2])],x->not IsOne(d[2][x]));
# elm, elmconj, canonical factor, conjugator, cenpcgs,cenfac,cenfacimgs,censize,cenfacsiz
reps:=List(candidates,x->[x,x,One(G),One(G),[],d[1]{mran},d[2]{mran},Size(G),Size(G)]);
else
# nonsolvable
if radsize>1 then
hom:=ser.factorhom;
ntrihom:=true;
f:=Image(hom);
# we need centralizers
#fants:=Filtered(NormalSubgroups(f),x->Size(x)>1 and Size(x)<Size(f));
else
if IsPermGroup(G) then
hom:=SmallerDegreePermutationRepresentation(G);
ntrihom:=not IsOne(hom);;
else
hom:=IdentityMapping(G);
ntrihom:=false;
fi;
f:=Image(hom);
fi;
if not IsBound(f!.someClassReps) then
f!.someClassReps:=[ConjugacyClass(f,One(f))]; # identity first
fi;
if HasConjugacyClasses(f) and
Length(f!.someClassReps)<Length(ConjugacyClasses(f)) then
# expand the list of stored factor classes for once.
cl:=Filtered(ConjugacyClasses(f),x-> not ForAny(f!.someClassReps,
y->Order(Representative(x))=Order(Representative(y))
and Representative(y) in x));
Append(f!.someClassReps,cl);
fi;
cl:=f!.someClassReps;
classrange:=[1..Length(cl)];
r:=ValueOption("candidatenums");
if r<>fail and HasConjugacyClasses(G) then
# candidatenums gives the numbers of some classes in G that should be
# tried first (as they likely contain the element). Us this to reduce
# conjugacy test in factor.
if not IsBound(G!.radicalfactorclassmap) then
G!.radicalfactorclassmap:=[];
fi;
fr:=G!.radicalfactorclassmap;
for i in Filtered(r,x->not IsBound(fr[x])) do
# compute images that are not yet known
d:=ImagesRepresentative(hom,Representative(ConjugacyClasses(G)[i]));
j:=First([1..Length(cl)],x->IsBound(cl[x]) and d in cl[x]);
if j<>fail then
fr[i]:=j;
fi;
od;
r:=Filtered(r,x->IsBound(fr[x]));
r:=Set(fr{r}); # class numbers in factor
classrange:=Concatenation(r,
Filtered(classrange,x->not x in r));
fi;
nreps:=[];
for i in candidates do
fr:=ImagesRepresentative(hom,i);
conj:=fail;
j:=0;
while conj=fail and j<Length(classrange) do
j:=j+1;
if Order(fr)=Order(Representative(cl[classrange[j]])) then
conj:=RepresentativeAction(f,fr,Representative(cl[classrange[j]]));
fi;
od;
if conj=fail then
# not yet found, and classes of f were not known -- store this rep
# image as canonical one for future use.
j:=j+1;
Add(cl,ConjugacyClass(f,fr));
conj:=One(f);
else
j:=classrange[j];
fi;
# store fixed preimages of reps to avoid any impact of homomorphism.
if not IsBound(f!.classpreimgs) then
f!.classpreimgs:=[];
fi;
prereps:=f!.classpreimgs;
if not IsBound(prereps[j]) then
prereps[j]:=PreImagesRepresentative(hom,Representative(cl[j]));
fi;
r:=PreImagesRepresentative(hom,conj);
d:=GeneratorsOfGroup(Centralizer(cl[j]));
# Format for cl is:
# 1:Element, 2: Conjugate element, 3: Element that will be canonical
# in factor, 4:conjugator, 5:cenpcgs,
# 6:cenfac, 7:cenfacimgs, 8:censize, 9:cenfacsize
Add(nreps,[i,i^r,prereps[j],r,[],
List(d,x->PreImagesRepresentative(hom,x)),d,
radsize*Size(Centralizer(cl[j])), Size(Centralizer(cl[j]))]);
od;
reps:=nreps;
fi;
for d in [2..Length(ser.depths)] do
#M:=ser[i-1];
#N:=ser[i];
mran:=[ser.depths[d-1]..len];
nran:=[ser.depths[d]..len];
fran:=[mran,nran];
mpcgs:=InducedPcgsByPcSequenceNC(pcgs,pcgs{mran}) mod
InducedPcgsByPcSequenceNC(pcgs,pcgs{nran});
central:= ForAll(GeneratorsOfGroup(G),
i->ForAll(mpcgs,
j->DepthOfPcElement(pcgs,Comm(i,j))>=ser.depths[d]));
# abelian factor, use affine methods
Info(InfoHomClass,1,"abelian factor ",d,": ",
Product(RelativeOrders(ser.pcgs){mran}), "->",
Product(RelativeOrders(ser.pcgs){nran})," central:",central);
nreps:=[];
solvtriv:=Subgroup(Range(pcisom),
List(DenominatorOfModuloPcgs(mpcgs),x->ImagesRepresentative(pcisom,x)));
select:=[1..Length(reps)];
while Length(select)>0 do
pos:=select[1];
sel:=Filtered(select,x->reps[x][3]=reps[pos][3]);
if ValueOption("conjugacytest")=true and Length(sel)<>2 then
return fail;
fi;
Info(InfoHomClass,2,Length(sel),"in candidate group");
select:=Difference(select,sel);
new:=LiftConCandCenNonsolvGeneral(G,mpcgs,reps{sel},hom,pcisom,solvtriv,fran);
# conj test
if new=fail then
return new;
fi;
Append(nreps,new);
od;
reps:=nreps;
od;
# arrange back to same ordering as before.
nreps:=[];
for i in candidates do
Add(nreps,First(reps,x->IsIdenticalObj(x[1],i)));
od;
return nreps;
end);
#############################################################################
##
#M Centralizer( <G>, <e> ) . . . . . . . . . . . . . . using TF method
##
InstallMethod( CentralizerOp, "TF method:elm",IsCollsElms,
[ IsGroup and IsFinite and HasFittingFreeLiftSetup,
IsMultiplicativeElementWithInverse ], OVERRIDENICE,
function( G, e )
if IsPermGroup(G) or IsPcGroup(G) then TryNextMethod();fi;
if not e in G then
# TODO: form larger group containing e.
TryNextMethod();
fi;
e:=TFCanonicalClassRepresentative(G,[e])[1];
if e=fail then TryNextMethod();fi;
return SubgroupByFittingFreeData(G,e[6],e[7],e[5]);
end );
#############################################################################
##
#M Centralizer( <G>, <e> ) . . . . . . . . . . . . . . using TF method
##
InstallMethod( CentralizerOp, "TF method:subgroup",IsIdenticalObj,
[ IsGroup and IsFinite and HasFittingFreeLiftSetup,
IsGroup and IsFinite and HasGeneratorsOfGroup],
2*OVERRIDENICE,
function( G, S )
local c,e;
if IsPermGroup(G) or IsPcGroup(G) then TryNextMethod();fi;
c:=G;
for e in GeneratorsOfGroup(S) do
c:=Centralizer(c,e);
od;
return c;
end );
#############################################################################
##
#M RepresentativeAction( <G>, <d>, <e>, <act> ) . . . . . using TF method
##
InstallOtherMethod( RepresentativeActionOp, "TF Method on elements",
IsCollsElmsElmsX,
[ IsGroup and IsFinite and HasFittingFreeLiftSetup,
IsMultiplicativeElementWithInverse,
IsMultiplicativeElementWithInverse, IsFunction ],
OVERRIDENICE,
function ( G, d, e, act )
local c;
if IsPermGroup(G) or IsPcGroup(G) then TryNextMethod();fi;
if not (d in G and e in G) then
# TODO: form larger group containing e.
TryNextMethod();
fi;
if act=OnPoints then #and d in G and e in G then
c:=TFCanonicalClassRepresentative(G,[d,e]:conjugacytest);
if c=fail then
return fail;
else
if c[1][2]=c[2][2] then
return c[1][4]/c[2][4]; # map via canonicals
else
return fail; # not conjugate
fi;
fi;
fi;
TryNextMethod();
end);
#############################################################################
##
#M ConjugacyClasses( <G> ) . . . . . . . . . . . . . . . . . . of perm group
##
InstallMethod( ConjugacyClasses, "perm group", true,
[ IsPermGroup and IsFinite],OVERRIDENICE,
function( G )
local cl;
if IsNaturalSymmetricGroup(G) or IsNaturalAlternatingGroup(G) then
# there are better methods for Sn/An
TryNextMethod();
fi;
cl:=ConjugacyClassesForSmallGroup(G);
if cl<>fail then
return cl;
elif IsSimpleGroup( G ) then
cl:=ClassesFromClassical(G);
if cl=fail then
cl:=ConjugacyClassesByRandomSearch( G );
fi;
return cl;
else
return ConjugacyClassesViaRadical(G);
fi;
end );
#############################################################################
##
#M ConjugacyClasses( <G> ) . . . . . . . . . . . . . . . . . . of perm group
##
InstallMethod( ConjugacyClasses, "TF Method", true,
[ IsGroup and IsFinite and HasFittingFreeLiftSetup],OVERRIDENICE,
function(G)
if IsPermGroup(G) or IsPcGroup(G) then TryNextMethod();fi;
return ConjugacyClassesViaRadical(G);
end);
#############################################################################
#
# old code, kept for comparison
#############################################################################
##
#F GeneralStepClEANSNonsolv( <H>,<N>,<NT>,<cl> )
##
BindGlobal("GeneralStepClEANSNonsolv",function( H, N,NT, cl )
local classes, # classes to be constructed, the result
field, # field over which <N> is a vector space
one,
h, # preimage `cl.representative' under <hom>
cNh, # centralizer of <h> in <N>
C, gens, # preimage `Centralizer( cl )' under <hom>
r, # dimension of <N>
ran, # constant range `[ 1 .. r ]'
aff, # <N> as affine space
xset, # affine operation of <C> on <aff>
eo, # xorbits/stabilizers
imgs, M, # generating matrices for affine operation
orb, # orbit of affine operation
rep,# set of classes with canonical representatives
c, i, # loop variables
reduce,
stabsub,
comm,s,stab;# for class correction
#NT:=AsSubgroup(H,NT);
C := cl[2];
field := GF( RelativeOrders( N )[ 1 ] );
one:=One(field);
h := cl[1];
reduce:=ReducedPermdegree(C);
if reduce<>fail then
C:=Image(reduce,C);
Info(InfoHomClass,4,"reduced to deg:",NrMovedPoints(C));
h:=Image(reduce,h);
NT:=Image(reduce,NT);
N:=ModuloPcgs(SubgroupNC(C,Image(reduce,NumeratorOfModuloPcgs(N))),NT);
fi;
# Determine the subspace $[h,N]$ and calculate the centralizer of <h>.
#cNh := ExtendedPcgs( DenominatorOfModuloPcgs( N!.capH ),
# KernelHcommaC( N, h, N!.capH ) );
N!.capH:=N;
cNh:=KernelHcommaC( N, h, N!.capH,2 );
r := Length( N!.subspace.baseComplement );
ran := [ 1 .. r ];
# Construct matrices for the affine operation on $N/[h,N]$.
aff := ExtendedVectors( field ^ r );
if IsSolvableGroup(C) then
gens:=Pcgs(C);
else
gens:=GeneratorsOfGroup(C);
fi;
imgs := [ ];
for c in gens do
M := [ ];
for i in [ 1 .. r ] do
M[ i ] := Concatenation( ExponentsConjugateLayer( N,
N[ N!.subspace.baseComplement[ i ] ] , c )
* N!.subspace.projection, [ Zero( field ) ] );
od;
M[ r + 1 ] := Concatenation( ExponentsOfPcElement
( N, Comm( h, c ) ) * N!.subspace.projection,
[ One( field ) ] );
M:=ImmutableMatrix(field,M);
Add( imgs, M );
od;
xset := ExternalSet( C, aff, gens, imgs );
classes := [ ];
# NC is safe
stabsub:=ClosureSubgroupNC(NT,cNh);
SetActionKernelExternalSet(xset,stabsub);
eo:=ExternalOrbitsStabilizers( xset );
for orb in eo do
rep := PcElementByExponentsNC( N, N{ N!.subspace.baseComplement },
Representative( orb ){ ran } );
Assert(2,ForAll(GeneratorsOfGroup(stabsub),i->Comm(i,h*rep) in NT));
# filter those we don't get anyhow.
stab:=Filtered(GeneratorsOfGroup(StabilizerOfExternalSet(orb)),
i->not i in stabsub);
comm := [ ];
for s in [ 1 .. Length( stab ) ] do
comm[ s ] := ExponentsOfPcElement( N,
Comm( rep, stab[ s ] ) * Comm( h, stab[ s ] ) )*one;
od;
comm:=ImmutableMatrix(field,comm);
comm := comm * N!.subspace.inverse;
for s in [ 1 .. Length( comm ) ] do
stab[ s ] := stab[ s ] / PcElementByExponentsNC
( N, N{ N!.subspace.needed }, comm[ s ] );
#( N!.capH, N!.capH{ N!.subspace.needed }, comm[ s ] );
Assert(2,Comm(h*rep,stab[s]) in NT);
od;
# NC is safe
stab:=ClosureSubgroupNC(stabsub,stab);
if IsSolvableGroup(C) then
SetIsSolvableGroup(stab,true);
fi;
c := [h * rep,stab];
Assert(2,ForAll(GeneratorsOfGroup(stab),i->Comm(i,c[1]) in NT));
if reduce<>fail then
Add(classes,[PreImagesRepresentative(reduce,c[1]),
PreImage(reduce,c[2])]);
else
Add(classes,c);
fi;
od;
Assert(1,ForAll(classes,i->i[1] in H and IsSubset(H,i[2])));
return classes;
end);
# new version, no subspace
#############################################################################
##
#F GeneralStepCanEANSNonsolv( <H>,<N>,<NT>,<C>,<reps> )
##
## canonical rep
BindGlobal("GeneralStepCanEANSNonsolv",function( H, N,NT, C,h,reps,repo,nostab )
local SchreierVectorProduct, field, one, r, ran, gens, imgs, M, invimgs, repvec, repgps, newreps, aff, sel, i, repsofi, orb, rep, dict, q, stab, sti, stabgens, p, img, mi, os, a, mipo, mimap, map, ngrp, c, j;
SchreierVectorProduct:=function(n)
local w,q,a;
w:=One(C);
while n<>1 do
q:=rep[n];
w:=gens[q]*w;
n:=LookupDictionary(dict,orb[n]*invimgs[q]);
od;
return w;
end;
#NT:=AsSubgroup(H,NT);
field := GF( RelativeOrders( N )[ 1 ] );
one:=One(field);
#reduce:=ReducedPermdegree(C);
#if reduce<>fail then
# C:=Image(reduce,C);
# Info(InfoHomClass,4,"reduced to deg:",NrMovedPoints(C));
# h:=Image(reduce,h);
# NT:=Image(reduce,NT);
# N:=ModuloPcgs(SubgroupNC(C,Image(reduce,NumeratorOfModuloPcgs(N))),NT);
#fi;
r := Length(N);
ran := [ 1 .. r ];
# Construct matrices for the affine operation on $N/[h,N]$.
gens:=Filtered(GeneratorsOfGroup(C),i->not i in NT);
if Length(gens)>20 then
gens:=Filtered(SmallGeneratingSet(C),i->not i in NT);
fi;
imgs := [ ];
for c in gens do
M := [ ];
for i in ran do
#M[i]:=Concatenation(ExponentsConjugateLayer(N,N[i],c)*one,[Zero(field)]);
M[i]:=Concatenation(ExponentsOfPcElement(N,N[i]^c)*one,[Zero(field)]);
od;
M[r+1]:=Concatenation(ExponentsOfPcElement(N,Comm(h,c))*one,[One(field)]);
M:=ImmutableMatrix(field,M);
Add( imgs, M );
od;
invimgs:=List(imgs,Inverse);
# get vectors for reps
repvec:=List(repo,i->Concatenation(
ExponentsOfPcElement(N,LeftQuotient(h,reps[i][1]))*one,[one]));
for i in repvec do
ConvertToVectorRep(i,field);
od;
repgps:=[];
newreps:=[];
aff:=field^(r+1);
sel:=[1..Length(repo)];
while Length(sel)>0 do
i:=sel[1];
repsofi:=reps[repo[i]];
RemoveSet(sel,i);
# since we want representatives as well, recode the orbit algorithm.
orb:=[repvec[i]];
rep:=[0];
dict:=NewDictionary(repvec[i],true,aff);
AddDictionary(dict,repvec[i],1);
# get stabilizing generators
q:=gens{Filtered([1..Length(gens)],i->orb[1]*imgs[i]=orb[1])};
if q=gens or nostab then
stab:=C;
else
stab:=ClosureGroup(NT,q);
fi;
sti:=5;
if nostab then sti:=-1;fi;
stabgens:=[];
p:=1;
while p<=Length(orb) do
for j in [1..Length(gens)] do
img:=orb[p]*imgs[j];
q:=LookupDictionary(dict,img);
if q=fail then
Add(orb,img);
AddDictionary(dict,img,Length(orb));
Add(rep,j);
elif Size(C)/Size(stab)>Length(orb) then
if sti=0 then
Add(stabgens,[p,j,q]);
if Random([1..QuoInt(Length(orb),5)])=1 then
os:=Random([1..Length(stabgens)]);
mi:=stabgens[os];
stabgens[os]:=stabgens[Length(stabgens)];
Unbind(stabgens[Length(stabgens)]);
os:=Size(stab);
stab:=ClosureGroup(stab,SchreierVectorProduct(mi[1])*gens[mi[2]]
/ SchreierVectorProduct(mi[3]));
if Size(stab)>os then
sti:=1;
fi;
fi;
else
os:=Size(stab);
stab:=ClosureGroup(stab,SchreierVectorProduct(p)*gens[j]
/ SchreierVectorProduct(q));
if Size(stab)=os then
sti:=sti-1;
fi;
fi;
fi;
od;
p:=p+1;
od;
# add missing schreier gens
a:=Size(C)/Length(orb);
while Size(stab)<a and not nostab do
os:=Random([1..Length(stabgens)]);
mi:=stabgens[os];
stabgens[os]:=stabgens[Length(stabgens)];
Unbind(stabgens[Length(stabgens)]);
stab:=ClosureGroup(stab,SchreierVectorProduct(mi[1])*gens[mi[2]]
/ SchreierVectorProduct(mi[3]));
od;
Info(InfoHomClass,3,"Orbit length ",Length(orb),
" with ",Length(gens)," generators");
mi:=Minimum(orb); # the ``canonical'' rep.
mipo:=LookupDictionary(dict,mi);
mimap:=SchreierVectorProduct(mipo); # element moving starter to minimal
map:=mimap;
stab:=stab^map; # stabilize minimal element
mi:=PcElementByExponentsNC(N,mi{ran});
Assert(1,ForAll(GeneratorsOfGroup(stab),x->Comm(x,h*mi) in NT));
ngrp:=[[repo[i]],h*mi,stab];
Add(repgps,ngrp);
newreps[repo[i]]:=[repsofi[1]^map,repsofi[2]*map,Length(repgps)];
Assert(1,LeftQuotient(h*mi*One(NT),repsofi[1]^map) in NT);
for i in ShallowCopy(sel) do
q:=LookupDictionary(dict,repvec[i]);
if q<>fail then
RemoveSet(sel,i);
repsofi:=reps[repo[i]];
Add(ngrp[1],repo[i]);
map:=LeftQuotient(SchreierVectorProduct(q),mimap);
newreps[repo[i]]:=[repsofi[1]^map,repsofi[2]*map,Length(repgps)];
Assert(1,LeftQuotient(h*mi,repsofi[1]^map) in NT);
fi;
od;
od;
return [repgps,newreps];
end);
#############################################################################
##
#F CentralStepClEANSNonsolv( <H>, <N>, <cl> )
##
# the version for pc groups implicitly uses a pc-group orbit-stabilizer
# algorithm. We can't do this but have to use a more simple-minded
# orbit/stabilizer approach.
BindGlobal("CentralStepClEANSNonsolv",function( H, N, cl )
local classes, # classes to be constructed, the result
f, # field over which <N> is a vector space
o,
n,r, # dimensions
space,
com,
comms,
mats,
decomp,
reduce,
v,
h, # preimage `cl.representative' under <hom>
C, # preimage `Centralizer( cl )' under <hom>
w, # coefficient vectors for projection along $[h,N]$
c; # loop variable
C:=cl[2];
h := cl[1];
reduce:=ReducedPermdegree(C);
if reduce<>fail then
C:=Image(reduce,C);
Info(InfoHomClass,4,"reduced to deg:",NrMovedPoints(C));
h:=Image(reduce,h);
N:=ModuloPcgs(SubgroupNC(C,Image(reduce,NumeratorOfModuloPcgs(N))),
SubgroupNC(C,Image(reduce,DenominatorOfModuloPcgs(N))));
fi;
# centrality still means that conjugation by c is multiplication with
# [h,c] and that the complement space is generated by commutators [h,c]
# for a generating set {c|...} of C.
f:=GF(RelativeOrders(N)[1]);
n:=Length(N);
o:=One(f);
# commutator space basis
comms:=List(GeneratorsOfGroup(C),c->o*ExponentsOfPcElement(N,Comm(h,c)));
List(comms,x->ConvertToVectorRep(x,f));
space:=List(comms,ShallowCopy);
TriangulizeMat(space);
space:=Filtered(space,i->i<>Zero(i)); # remove spurious columns
com:=BaseSteinitzVectors(IdentityMat(n,f),space);
# decomposition of vectors into the subspace basis
r:=Length(com.subspace);
if r>0 then
# if the subspace is trivial, everything stabilizes
decomp:=Concatenation(com.subspace,com.factorspace)^-1;
decomp:=decomp{[1..Length(decomp)]}{[1..r]};
decomp:=ImmutableMatrix(f,decomp);
# build matrices for the affine action
mats:=[];
for w in comms do
c:=IdentityMat(r+1,o);
c[r+1]{[1..r]}:=w*decomp; # translation bit
c:=ImmutableMatrix(f,c);
Add(mats,c);
od;
#subspace affine enumerator
v:=ExtendedVectors(f^r);
C := Stabilizer( C, v, v[1],GeneratorsOfGroup(C), mats,OnPoints );
fi;
Assert(1,Size(cl[2])/Size(C)=Size(f)^r);
if Length(com.factorspace)=0 then
if reduce<>fail then
classes:=[[PreImagesRepresentative(reduce,h),PreImage(reduce,C)]];
else
classes:=[[h,C]];
fi;
else
classes:=[];
# enumerator of complement
v:=f^Length(com.factorspace);
for w in v do
c := [h * PcElementByExponentsNC( N,w*com.factorspace),C ];
if reduce<>fail then
Add(classes,[PreImagesRepresentative(reduce,c[1]),
PreImage(reduce,c[2])]);
else
Add(classes,c);
fi;
od;
fi;
Assert(1,ForAll(classes,i->i[1] in H and IsSubset(H,i[2])));
return classes;
end);
BindGlobal("ConjugacyClassesViaRadical_Old",function (G)
local r, #radical
f, # G/r
hom, # G->f
pcgs,mpcgs, #(modulo) pcgs
ser, # series
M,N, # normal subgrops
ind, # indices
i, #loop
new, # new classes
cl,ncl; # classes
# it seems to be cleaner (and avoids deferring abelian factors) if we
# factor out the radical first. (Note: The radical method for perm groups
# stores the nat hom.!)
ser:=PermliftSeries(G);
pcgs:=ser[2];
ser:=ser[1];
r:=ser[1];
if Size(r)<Size(G) then
if Size(r)>1 then
hom:=NaturalHomomorphismByNormalSubgroupNC(G,r);
f:=Image(hom);
# we need centralizers
cl:=ConjugacyClassesFittingFreeGroup(f:onlysizes:=false);
else
hom:=SmallerDegreePermutationRepresentation(G); # old code
f:=Image(hom);
cl:=ConjugacyClassesFittingFreeGroup(f);
fi;
if not IsOne(hom) then
ncl:=[];
for i in cl do
new:=[PreImagesRepresentative(hom,i[1])];
if not IsInt(i[2]) then
Add(new,PreImage(hom,i[2]));
fi;
Add(ncl,new);
od;
cl:=ncl;
fi;
else
cl:=[[One(G),G]];
fi;
for i in [2..Length(ser)] do
M:=ser[i-1];
N:=ser[i];
# abelian factor, use affine methods
Info(InfoHomClass,1,"abelian factor: ",Size(M),"->",Size(N));
if pcgs=false then
mpcgs:=ModuloPcgs(M,N);
else
mpcgs:=pcgs[i-1] mod pcgs[i];
fi;
ncl:=[];
for i in cl do
Assert(2,ForAll(GeneratorsOfGroup(i[2]),j->Comm(i[1],j) in M));
if ForAll(GeneratorsOfGroup(i[2]),
i->ForAll(mpcgs,j->Comm(i,j) in N)) then
Info(InfoHomClass,3,"central step");
new:=CentralStepClEANSNonsolv(G,mpcgs,i);
else
new:=GeneralStepClEANSNonsolv(G,mpcgs,AsSubgroup(G,N),i);
fi;
Assert(1,ForAll(new,
i->ForAll(GeneratorsOfGroup(i[2]),j->Comm(j,i[1]) in N)));
Info(InfoHomClass,2,Length(new)," new classes");
ncl:=Concatenation(ncl,new);
od;
cl:=ncl;
Info(InfoHomClass,1,"Now: ",Length(cl)," classes");
od;
if Order(cl[1][1])>1 then
# the idenity is not in first position
Info(InfoHomClass,2,"identity not first, sorting");
Sort(cl,function(a,b) return Order(a[1])<Order(b[1]);end);
fi;
Info(InfoHomClass,1,"forming classes");
ncl:=[];
for i in cl do
if IsInt(i[2]) then
r:=ConjugacyClass(G,i[1]);
SetSize(r,Size(G)/i[2]);
else
Assert(1,Centralizer(G,i[1])=i[2]);
r:=ConjugacyClass(G,i[1],i[2]);
fi;
Add(ncl,r);
od;
cl:=ncl;
# temporary fix for wrong centralizers -- this code will go away anyhow
# in next release
if Sum(ncl,Size)<>Size(G) then
ncl:=List(ncl,x->ConjugacyClass(G,Representative(x)));
if Sum(ncl,Size)<>Size(G) then
Error("wrong classes");
fi;
fi;
return ncl;
end);
#############################################################################
##
#E