|
#############################################################################
##
## 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 the implementation of the Dixon-Schneider algorithm
##
#############################################################################
##
#F FingerprintPerm( <D>, <el>, <i>, <j>, <orbitJ>, <representatives>)
#F Entry i,j of the matrix of el in the permutation representation of G
##
BindGlobal( "FingerprintPerm", function(D,el,orbitJ,representatives)
local x,a,cycle,cycles;
a:=0;
#cycles:=Cycles(el,D.group.orbit);
cycles:=Cycles(el,MovedPoints(D.group));
for cycle in cycles do
x:=cycle[1];
if x^(el*representatives[x]) in orbitJ then
a:=a+Length(cycle);
fi;
od;
return a;
end );
#############################################################################
##
#F IdentificationPermGroup(<D>,<el>) . . . . . class invariants for el in G
##
## The class invariant consists of the cycle structure and - if computation
## might improve results - of the Fingerprint of the permutation
##
BindGlobal("CheapIdentificationPermGroup",function(D,el)
local s,t,i,l; # guter Programmier s t i l !
s:=CycleStructurePerm(el);
s:=ShallowCopy(s);
if not IsPerfectGroup(D.group) then
Add(s,CanonicalRightCosetElement(DerivedSubgroup(D.group),el));
fi;
t:=ShallowCopy(s);
if t in D.centmulCandidates then
Add(s,"c");
l:=First(D.centmulMults,i->i[1]=t);
for i in l{[2..Length(l)]} do
s:=Concatenation(s,CycleStructurePerm(
el*D.classreps[i]));
od;
fi;
if t in D.fingerprintCandidates then
Add(s,-FingerprintPerm(D,el,D.fingerprintOrbitStabilizer,
D.fingerprintRepresentatives));
fi;
return s;
end);
BindGlobal("IdentificationPermGroup",function(D,el)
local s,l;
s:=CheapIdentificationPermGroup(D,el);
if IsBound(D.usefitfree) and not s in D.nocanonize then
l:=First(D.faclaimg,x->x[1]=s);
l:=TFCanonicalClassRepresentative(D.group,[el]:candidatenums:=l[2]);
Add(s,l[1][2]);
fi;
return s;
end);
#############################################################################
##
#F RationalIdentificationPermGroup( <D>, <el> ) galois-fix class invariant
##
## When trying to use cheap identifications, we cannot use all
## identification routines: For example galois conjugated elements must be
## multiplied by the *galois conjugate* of the central element!
##
BindGlobal( "RationalIdentificationPermGroup", function(D,el)
return CycleStructurePerm(el);
end );
#############################################################################
##
#M DxPreparation(<G>)
## Set up some functions. Also test, whether calculating fingerprints and
## multiplication by central elements might improve the quick
## identification
##
InstallMethod(DxPreparation,"perm",true,[IsPermGroup,IsRecord],0,
function(G,D)
local k,structures,ambiguousStructures,i,j,p,cem,ces,z,t,cen,a,
c,s,f,fc,fs,fos,fr,enum;
D.identification:=IdentificationPermGroup;
D.cheapIdentification:=CheapIdentificationPermGroup;
D.rationalidentification:=RationalIdentificationPermGroup;
D.ClassMatrixColumn:=StandardClassMatrixColumn;
if IsDxLargeGroup(G) then
D.ClassElement:=ClassElementLargeGroup;
else
enum:=Enumerator(G);
D.enum:=enum;
D.ClassElement:=ClassElementSmallGroup;
D.classMap:=ListWithIdenticalEntries(Size(G),D.klanz);
for j in [1..D.klanz-1] do
for i in Orbit(G,D.classreps[j]) do
D.classMap[Position(enum,i)]:=j;
od;
od;
fi;
D.fingerprintCandidates:=[];
D.centmulCandidates:=[];
D.permdegree:=LargestMovedPoint(G);
k:=D.klanz;
if IsDxLargeGroup(G) then
# test, if cyclestructure yields no perfect result
structures:=[];
ambiguousStructures:=[];
for i in [1..k] do
s:=IdentificationPermGroup(D,D.classreps[i]);
if not s in structures then
Add(structures,s);
elif not s in ambiguousStructures then
Add(ambiguousStructures,s);
fi;
od;
if ambiguousStructures<>[] then
# Centre multiplication test
cem:=[];
cen:=[];
for i in [2..Length(D.classes)] do
if D.classiz[i]=1 then
Add(cen,i);
fi;
od;
if cen<>[] then
for s in ambiguousStructures do
ces:=[s];
c:=Filtered(D.classrange,i->
IdentificationPermGroup(D,D.classreps[i])=s);
a:=[[1..Length(c)]];
for z in cen do
t:=List(c,i->
CycleStructurePerm(
D.classreps[i]*
D.classreps[z]));
if Length(Set(t))>1 then
# improved result ?
fc:=[];
fs:=[];
for i in [1..Length(t)] do
p:=Position(fc,t[i]);
if p=fail then
Add(fc,t[i]);
p:=Length(fc);
fs[p]:=[];
fi;
Add(fs[p],i);
od;
fc:=[];
for i in a do
fc:=Concatenation(fc,Filtered(List(fs,j->Intersection(j,i)),
j->j<>[]));
od;
fc:=Set(fc);
if fc<>a then
Add(ces,z);
a:=fc;
fi;
fi;
od;
if Length(ces)>1 then
Add(cem,ces);
fi;
od;
D.centmulMults:=cem;
fi;
# fingerprint test
if IsTransitive(G,MovedPoints(G)) and
# otherwise lotsa representatives will mess up memory
Length(MovedPoints(G))<1500 then
# select moved points 1 and 2
fos:=MovedPoints(G);
D.p1:=fos[1];
D.p2:=fos[2];
fs := Stabilizer(G,D.p1);
fos := First(OrbitsDomain(fs,[1..D.permdegree]),o->D.p2 in o);
fr := List([1..D.permdegree],x->RepresentativeAction(G,x,D.p1));
fc:=[];
for s in ambiguousStructures do
c:=Filtered([1..D.klanz],i->IdentificationPermGroup(D,
D.classreps[i])=s);
f:=List(c,i->FingerprintPerm(D,
D.classreps[i],fos,fr));
if Length(Set(f))>1 then Add(fc,s);
fi;
od;
if Length(fc)>0 then
D.fingerprintCandidates:=fc;
D.fingerprintOrbitStabilizer:=fos;
D.fingerprintRepresentatives:=fr;
fi;
fi;
D.centmulCandidates:=Set(cem,i->i[1]);
fi;
fi;
D.ids:=[];
D.chids:=[];
D.rids:=[];
D.canreps:=[];
for i in [1..D.klanz] do
D.ids[i]:=D.identification(D,D.classreps[i]);
D.chids[i]:=D.cheapIdentification(D,D.classreps[i]);
D.rids[i]:=
D.rationalidentification(D,D.classreps[i]);
D.canreps[i]:=
TFCanonicalClassRepresentative(D.group,[D.classreps[i]])[1][2];
od;
# use canonical reps?
if Size(SolvableRadical(D.group))>1 then
D.usefitfree:=true;
D.ClassMatrixColumn:=TFClassMatrixColumn;
D.nocanonize:=[];
D.faclaimg:=[];
fs:=List(D.ids,ShallowCopy);
for i in [1..D.klanz] do
f:=Filtered([1..D.klanz],x->fs[x]=fs[i]);
if Length(f)=1 then
Add(D.nocanonize,fs[i]);
else
Add(D.faclaimg,[fs[i],f]); # store which classes images could be
Add(D.ids[i],D.canreps[i]);
fi;
od;
fi;
return D;
end);
[ Dauer der Verarbeitung: 0.32 Sekunden
(vorverarbeitet)
]
|
