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 trans.grp GAP transitive groups library Alexander Hulpke
##
##
#Y Copyright (C) 1997, Lehrstuhl D für Mathematik, RWTH Aachen, Germany
##
## This file contains the routines for the transitive groups library
##
#############################################################################
##
## tell GAP about the component
##
DeclareComponent("trans","1.0");
Unbind(TRANSGRP);
Unbind(TRANSPROPERTIES);
#############################################################################
##
#V TRANSGRP . . . . . . . . . generators and names of the transitive groups
## List contains one list per degree. Entries are lists itself
## for each group,starting with generators,then the name.
TRANSGRP := [[[(),"1 = C(1)"]],
[[(1,2),"C(2) = S(2) = 2"]],
[[(1,2,3),"C(3) = A(3) = 3"],[(1,3),(1,2),"S(3)"]],
[[(1,2,3,4),"C(4) = 4"],
[(1,4)(2,3),(1,2)(3,4),"E(4) = 2[x]2"],
[(1,2,3,4),(1,3),"D(4)"],
[(1,3,4),(2,3,4),"A(4)"],
[(1,4),(1,2),(2,3),"S(4)"]],
[[(1,2,3,4,5),"C(5) = 5"],
[(1,2,3,4,5),(1,4)(2,3),"D(5) = 5:2"],
[(1,2,3,4,5),(1,2,4,3),"F(5) = 5:4"],
[(1,4,5),(2,4,5),(3,4,5),"A(5)"],
[(1,5),(1,2),(2,3),(3,4),"S(5)"]],
[[(1,2,3,4,5,6),"C(6) = 6 = 3[x]2"],
[(1,3,5)(2,4,6),(1,4)(2,3)(5,6),"D_6(6) = [3]2"],
[(1,2,3,4,5,6),(1,4)(2,3)(5,6),"D(6) = S(3)[x]2"],
[(1,4)(2,5),(1,3,5)(2,4,6),"A_4(6) = [2^2]3"],
[(2,4,6),(1,4)(2,5)(3,6),"F_18(6) = [3^2]2 = 3 wr 2"],
[(3,6),(1,3,5)(2,4,6),"2A_4(6) = [2^3]3 = 2 wr 3"],
[(1,4)(2,5),(1,3,5)(2,4,6),(1,5)(2,4),"S_4(6d) = [2^2]S(3)"],
[(1,4)(2,5),(1,3,5)(2,4,6),(1,5)(2,4)(3,6),
"S_4(6c) = 1/2[2^3]S(3)"],
[(2,4,6),(1,5)(2,4),(1,4)(2,5)(3,6),"F_18(6):2 = [1/2.S(3)^2]2"],
[(2,4,6),(1,5)(2,4),(1,4,5,2)(3,6),"F_36(6) = 1/2[S(3)^2]2"],
[(3,6),(1,3,5)(2,4,6),(1,5)(2,4),
"2S_4(6) = [2^3]S(3) = 2 wr S(3)"],
[(1,2,3,4,6),(1,4)(5,6),"L(6) = PSL(2,5) = A_5(6)"],
[(2,4,6),(2,4),(1,4)(2,5)(3,6),
"F_36(6):2 = [S(3)^2]2 = S(3) wr 2"],
[(1,2,3,4,6),(1,2)(3,4)(5,6),"L(6):2 = PGL(2,5) = S_5(6)"],
[(1,5,6),(2,5,6),(3,5,6),(4,5,6),"A(6)"],
[(1,6),(1,2),(2,3),(3,4),(4,5),"S(6)"]],
[[(1,2,3,4,5,6,7),"C(7) = 7"],
[(1,2,3,4,5,6,7),(1,6)(2,5)(3,4),"D(7) = 7:2"],
[(1,2,3,4,5,6,7),(1,2,4)(3,6,5),"F_21(7) = 7:3"],
[(1,2,3,4,5,6,7),(1,3,2,6,4,5),"F_42(7) = 7:6"],
[(1,2,3,4,5,6,7),(1,2)(3,6),"L(7) = L(3,2)"],
[(1,6,7),(2,6,7),(3,6,7),(4,6,7),(5,6,7),"A(7)"],
[(1,7),(1,2),(2,3),(3,4),(4,5),(5,6),"S(7)"]]];
#############################################################################
##
#V TRANSPROPERTIES . . . . . . . . . property list for the transitive groups
##
## This list is in the same order as the groups generators. For each group,
## properties are stored as follows:
##
## <size>: Size of the group
## <primitive>: 1 indicates, that the group operates primitive
## <transitivity>: Transitivity
## <sign>: Sign
## <shapes>: List of all occurring shapes (except ()), sorted
## according to the ordering of the Partitions command
## <2Set>: Orbits on 2-Sets
## <2Seq>: Orbits on 2-Sequences
## <3Set>: Orbits on 3-Sets
## <special>: following entries mark special properties, which
## ... are coded as [type,description1,description2,...] .
## The list starts with orbit lengths:
##
## Types:
## 1 1-Set=Pts.
## 2 2-Set
## 3 3-Set
## 4 4-Set
## 5 5-Sets
## 6 i/2-Diff (only possible with even number of points)
## 8 Blocks
## 9 2Seq
## 0 Blockfingerprint
##
## 20+b alternating Subgroup on b
##
## 100*a+b factor group by operation on the b cosets of a
## type a stabilizer; description field gives the
## number of this factor group as TransitiveGroup
## 1000*a+10*b+c factor group by operation on the b cosets of
## a type a stabilizer operates on c:
## description fields are a list for each of the
## possible stabilizers
## 10000*a+10*b+c type a stabilizer of index b operation on c:
## description fields are a list for each of the
## possible stabilizers, split again for the
## (raw-split) due to the Orbits of <G> itself.
##
## All Orbit information is coded as a list in which each entry has
## the form
## SignOperation*( 1000*(number of orbits with this description-1)
## +length)
##
## Group theoretic information that cannot be used by the Galois
## determination routines is indicated by a negative sign:
##
## -50 Size of the derived subgroup
## -60 Size of the Frattini subgroup
## -70 Number of normal subgroups
##
## some special cases are not discriminated completely by this
## list. The program will deal with them separately.
TRANSPROPERTIES := [
[[1,1,1,1,[],0,0,0]],
[[2,1,2,-1,[true],[1],[-2],0]],
[[3,1,1,1,[false,true],[3],[1003],0],
[6,1,3,-1,[true,true],[-3],[-6],0]],
[[4,0,1,-1,[false,true,false,true],[-4,-2],[-2004],0],
[4,0,1,1,[false,true,false,false],[-2002],[2004],0],
[8,0,1,-1,[true,true,false,true],[-4,-2],[-4,8],0],
[12,1,2,1,[false,true,true,false],[6],[12],0],
[24,1,4,-1,[true,true,true,true],[6],[-12],0]],
[[5,1,1,1,[false,false,false,false,false,true],[1005],[3005],[1005]],
[10,1,1,1,[false,true,false,false,false,true],[1005],[-1010],[1005]],
[20,1,2,-1,[false,true,false,false,true,true],[-10],[-20],[-10],[29,[-1010]]],
[60,1,3,1,[false,true,true,false,false,true],[10],[20],[10]],
[120,1,5,-1,[true,true,true,true,true,true],[-10],[-20],[-10],[29,[20]]]],
[[6,0,1,-1,[false,false,true,false,false,true,false,false,false,true],
[-1006,3],[-4006],[-2006,-2]],
[6,0,1,-1,[false,false,true,false,false,true,false,false,false,false],
[-2003,-6],[-4006],[-2006,-2]],
[12,0,1,-1,[false,true,true,false,false,true,false,false,false,true],
[-1006,-3],[-6,1012],[-6,-2,12]],
[12,0,1,1,[false,true,false,false,false,true,false,false,false,false],
[3,12],[6,1012],[1004,1006]],
[18,0,1,-1,[false,false,true,true,false,true,false,false,false,true],
[-9,-6],[-1006,-18],[-18,-2]],
[24,0,1,-1,[true,true,true,false,false,true,false,false,false,true],
[3,12],[-6,1012],[-1006,8]],
[24,0,1,1,[false,true,false,false,false,true,false,true,false,false],
[-12,-3],[6,24],[-1004,12]],
[24,0,1,-1,[false,true,true,false,false,true,true,false,false,false],
[-12,-3],[-6,24],[8,12],[29,[6],[1012]]],
[36,0,1,-1,[false,true,true,true,false,true,false,false,false,true],
[-9,-6],[-18,12],[-18,-2]],
[36,0,1,1,[false,true,false,true,false,true,false,true,false,false],
[6,9],[-18,-12],[-18,-2]],
[48,0,1,-1,[true,true,true,false,false,true,true,true,false,true],
[-12,-3],[-6,24],[8,12],[29,[6],[24]]],
[60,1,2,1,[false,true,false,false,false,true,false,false,true,false],
[15],[30],[1010]],
[72,0,1,-1,[true,true,true,true,true,true,false,true,false,true],
[-9,-6],[-18,-12],[-18,-2]],
[120,1,3,-1,[false,true,true,false,false,true,true,false,true,true],
[15],[-30],[20],[23,[1010]]],
[360,1,4,1,[false,true,false,true,false,true,false,true,true,false],
[15],[30],[20]],
[720,1,6,-1,[true,true,true,true,true,true,true,true,true,true],
[15],[-30],[20],[23,[20]]]],
[[7,1,1,1,[false,false,false,false,false,false,false,false,false,false,
false,false,false,true],[2007],[5007],[4007]],
[14,1,1,-1,[false,false,true,false,false,false,false,false,false,false,
false,false,false,true],[-2007],[-2014],[-2007,-14]],
[21,1,1,1,[false,false,false,false,false,false,true,false,false,false,
false,false,false,true],[21],[1021],[21,1007]],
[42,1,2,-1,[false,false,true,false,false,false,true,false,false,false,
false,false,true,true],[-21],[-42],[-21,-14]],
[168,1,2,1,[false,true,false,false,false,false,true,false,true,false,
false,false,false,true],[21],[42],[7,28]],
[2520,1,5,1,[false,true,false,true,false,true,true,false,true,false,
true,false,false,true],[21],[42],[35]],
[5040,1,7,-1,[true,true,true,true,true,true,true,true,true,true,true,
true,
true,true],[-21],[-42],[35]]]];
# The following command converts the shape lists into Blists (binary
# lists), which allows for about 2/3 of memory saved
List([1..7],i->ForAll(TRANSPROPERTIES[i],j->IsBlist(j[5])));
# number of groups within each degree (stored up to 15)
TRANSLENGTHS := [ 1, 1, 2, 5, 5, 16, 7, 50, 34, 45, 8, 301, 9, 63, 104 ];
TRANSNONDISCRIM := [[],[],[],[],[],[],[],[],[],[],[],[[273,292]],[],
[[42,51]],[[37,58],[38,59],[57,67],[65,74],[66,74]]];
TRANSSELECT :=[];
TRANSSIZES :=[];
TRANSPARTNUM:=[];
InstallFlushableValue(TRANSSHAPEFREQS,[]);
if not IsBound(TRANSDEGREES) or TRANSDEGREES=0 then
TRANSDEGREES :=7;
HideGlobalVariables("dir","fnam");
dir:= DirectoriesLibrary( "trans" );
fnam:=Filename( dir, Concatenation("trans",String(TRANSDEGREES+1),".grp"));
while fnam<>fail and IsReadableFile(fnam) do
TRANSDEGREES:=TRANSDEGREES+1;
fnam:=Filename( dir, Concatenation("trans",String(TRANSDEGREES+1),".grp"));
od;
UnhideGlobalVariables("dir","fnam");
fi;
BIND_GLOBAL("TransGrpLoad",function(deg,nr)
local Tbak,Fbak,flg,sel,i,fname;
if IsBound(TRANSGRP[deg]) and (nr=0 or IsBound(TRANSGRP[deg][nr])) then
return;
fi;
if deg>TRANSDEGREES then
Error("transitive groups are known only of degree up to ",
TRANSDEGREES);
else
HideGlobalVariables("T","F");
BIND_GLOBAL("T",true);
BIND_GLOBAL("F",false);
fname:=Concatenation("trans",String(deg));
if deg>15 and not IsPrime(deg) then
if not IsBound(TRANSGRP[deg]) then
ReadGapRoot( Concatenation( "trans/", fname, ".grp" ) );
if nr=0 then
UnhideGlobalVariables("T","F");
return;
fi;
else
# the groups to be thrown away
sel:=Difference(Filtered([1..Length(TRANSGRP[deg])],
i->IsBound(TRANSGRP[deg])),TRANSSELECT[deg]);
if Length(TRANSSELECT[deg])>300 then
flg:=TRANSSELECT[deg]{[1..Length(TRANSSELECT[deg])-150]};
sel:=Union(flg,sel);
TRANSSELECT[deg]:=Difference(TRANSSELECT[deg],flg);
fi;
for i in sel do
Unbind(TRANSGRP[deg][i]);
Unbind(TRANSPROPERTIES[deg][i]);
od;
fi;
Append(fname,WordAlp("abcdefghijklmnopqrstuvwxyz",Int((nr-1)/300)+1));
fi;
IsString(fname);
ReadGapRoot( Concatenation( "trans/", fname, ".grp" ));
UnhideGlobalVariables("T","F");
if deg>15 and not IsPrime(deg) then
sel:=Difference(Filtered([1..Length(TRANSGRP[deg])],
i->IsBound(TRANSGRP[deg][i])),TRANSSELECT[deg]);
else
TRANSLENGTHS[deg]:=Length(TRANSGRP[deg]);
TRANSSIZES[deg]:=List(TRANSPROPERTIES[deg],i->i[1]);
sel:=[1..TRANSLENGTHS[deg]];
fi;
# make blists those which are
ForAll(TRANSPROPERTIES[deg]{sel},i->IsBound(i[5]) and IsBlist(i[5]));
fi;
for i in sel do
MakeImmutable(TRANSGRP[deg][i]);
MakeImmutable(TRANSPROPERTIES[deg][i]);
od;
TRANSPARTNUM[deg]:=NrPartitions(deg);
TRANSSHAPEFREQS[deg]:=[];
end);
BIND_GLOBAL("TRANSGrp",function(deg,nr)
if not IsBound(TRANSGRP[deg]) or not IsBound(TRANSGRP[deg][nr]) then
TransGrpLoad(deg,nr);
fi;
if deg>15 and not IsPrime(deg) then
AddSet(TRANSSELECT[deg],nr);
fi;
if nr>TRANSLENGTHS[deg] then
return "fail";
fi;
return TRANSGRP[deg][nr];
end);
BIND_GLOBAL("TRANSProperties",function(deg,nr)
local l;
if not IsBound(TRANSPROPERTIES[deg]) or
not IsBound(TRANSPROPERTIES[deg][nr]) then
TransGrpLoad(deg,nr);
fi;
if deg>15 and not IsPrime(deg) then
AddSet(TRANSSELECT[deg],nr);
fi;
if nr>TRANSLENGTHS[deg] then
return "fail";
fi;
l:=TRANSPROPERTIES[deg][nr];
if IsBound(l[5]) and IsString(l[5]) then
# translate string to blist
l:=ShallowCopy(l);
l[5]:=BlistStringDecode(l[5],TRANSPARTNUM[deg]-1);
MakeImmutable(l);
TRANSPROPERTIES[deg][nr]:=l;
fi;
return l;
end);
InstallGlobalFunction(NrTransitiveGroups, function(deg)
if deg=1 then
return 0;
fi;
if not(deg in [1..TRANSDEGREES]) then
return fail;
fi;
if not IsBound(TRANSLENGTHS[deg]) then
TransGrpLoad(deg,0);
fi;
return TRANSLENGTHS[deg];
end);
InstallGlobalFunction( TransitiveGroup, function(deg,num)
local gens,i,l,g,s;
if not(deg in [1..TRANSDEGREES]) then
Error("degree must be in [1..",TRANSDEGREES,"]");
fi;
if deg=1 then
return fail;
fi;
if not IsBound(TRANSLENGTHS[deg]) then
TransGrpLoad(deg,num);
fi;
if not (num in [1..TRANSLENGTHS[deg]]) then
Error("maximal number of groups of degree ",deg," is ",
TRANSLENGTHS[deg]);
fi;
# special case: Symmetric and Alternating Group
s:=Factorial(deg);
if TRANSProperties(deg,num)[1]=s then
if deg=1 then
g:=GroupByGenerators( [], () );
else
g:=SymmetricGroup(deg);
fi;
SetName(g,Concatenation("S",String(deg)));
elif TRANSProperties(deg,num)[1]*2=s then
g:=AlternatingGroup(deg);
SetName(g,Concatenation("A",String(deg)));
else
l:=TRANSGrp(deg,num);
s:=Length(l);
gens:=[];
for i in l{[1..s-1]} do
if IsPerm(i) then
Add(gens,i);
else
if Length(i)=2 then
Add(gens,TRANSGrp(i[1],i[2])[1]);
else
Add(gens,TRANSGrp(i[1],i[2])[i[3]]);
fi;
fi;
od;
g:= GroupByGenerators( gens, () );
if l[s]<>"" then
SetName(g,l[s]);
else
SetName(g,Concatenation("t",String(deg),"n",String(num)));
fi;
fi;
SetTransitiveIdentification(g,num);
return g;
end );
InstallFlushableValue(TRANSCOMBCACHE,[[0],[0],[0]]);
BindGlobal("TransCombinat",function(m,n)
local i,l;
for i in [1..3] do
if TRANSCOMBCACHE[i][1]=m and TRANSCOMBCACHE[i][2]=n then
return TRANSCOMBCACHE[i][3];
fi;
od;
TRANSCOMBCACHE[3]:=TRANSCOMBCACHE[2];
TRANSCOMBCACHE[2]:=TRANSCOMBCACHE[1];
l:=Combinations(m,n);
for i in l do MakeImmutable(i);od;
Sort(l);
IsSet(l);
TRANSCOMBCACHE[1]:=[m,n,l];
return l;
end);
InstallFlushableValue(TRANSARRCACHE,[[0],[0],[0]]);
BindGlobal("TransArrange",function(m,n)
local i,l;
for i in [1..3] do
if TRANSARRCACHE[i][1]=m and TRANSARRCACHE[i][2]=n then
return TRANSARRCACHE[i][3];
fi;
od;
TRANSARRCACHE[3]:=TRANSARRCACHE[2];
TRANSARRCACHE[2]:=TRANSARRCACHE[1];
l:=Arrangements(m,n);
for i in l do MakeImmutable(i);od;
Sort(l);
IsSet(l);
TRANSARRCACHE[1]:=[m,n,l];
return l;
end);
BindGlobal("CntOp",function(grp,orb,op)
local l,i,j,sgn;
l:=[];
for i in orb do
i:=Set(Immutable(i));
sgn:=1;
j:=1;
while sgn=1 and j<=Length(GeneratorsOfGroup(grp)) do
if SignPerm(Permutation(GeneratorsOfGroup(grp)[j],i,op))<0 then
sgn:=-1;
fi;
j:=j+1;
od;
Add(l,sgn*Length(i));
od;
l:=Collected(l);
for i in [1..Length(l)] do
l[i]:=SignInt(l[i][1])*(1000*(l[i][2]-1)+AbsInt(l[i][1]));
od;
Sort(l);
return l;
end);
BindGlobal("NumBol",function(b)
if b then return 1;
else return 0;
fi;
end);
BindGlobal("SetsOrbits",function(g,n)
local l,i;
l:=TransCombinat(MovedPoints(g),n);
for i in l do MakeImmutable(i);od;
Sort(l);
return OrbitsDomain(g,l,OnSets);
end);
BindGlobal("SeqsOrbits",function(g,n)
local l,i;
l:=TransArrange(MovedPoints(g),n);
for i in l do MakeImmutable(i);od;
Sort(l);
return OrbitsDomain(g,l,OnTuples);
end);
# the (undocumented) `cheap' parameter has the following function:
# not set -> proper test
# true -> return `fail' if not unique ID
# 1 -> ID list if no cheap unique ID
# 2 -> as 1, but do not compute classes (expensive if big!)
InstallMethod(TransitiveIdentification,"generic",true,[IsPermGroup],0,
function(ogrp)
local dom,p,s,t,a,cand,i,grp,deg,aiso,piso,co,cheap;
cheap:=ValueOption("cheap");
grp:=ogrp;
dom:=MovedPoints(grp);
if not IsTransitive(grp,dom) then
Error("Group must operate transitively");
fi;
deg:=Length(dom);
if not IsBound(TRANSLENGTHS[deg]) then
TransGrpLoad(deg,0);
fi;
s:=Size(grp);
if deg>15 then
cand:=Filtered([1..TRANSLENGTHS[deg]],i->TRANSSIZES[deg][i]=s);
else
cand:=Filtered([1..TRANSLENGTHS[deg]],i->TRANSProperties(deg,i)[1]=s);
fi;
if Length(cand)>1 and deg>4 then
co:=CntOp(grp,OrbitsDomain(grp,TransCombinat(dom,2),OnSets),OnSets);
cand:=Filtered(cand,i->TRANSProperties(deg,i)[6]=co);
if Length(cand)>1 then
co:=CntOp(grp,OrbitsDomain(grp,TransArrange(dom,2),OnTuples),OnTuples);
cand:=Filtered(cand,i->TRANSProperties(deg,i)[7]=co);
fi;
if Length(cand)>1 then
co:=CntOp(grp,OrbitsDomain(grp,TransCombinat(dom,3),OnSets),OnSets);
cand:=Filtered(cand,i->TRANSProperties(deg,i)[8]=co);
fi;
fi;
Pcgs(grp); # try to enforce solvable calculations further on.
# if Length(cand)>1 and IsSolvableGroup(grp)
# and not HasConjugacyClasses(grp) then
# t:=[];
# aiso:=IsomorphismPcGroup(grp);
# a:=Image(aiso,grp);
# for i in ConjugacyClasses(a) do
# s:=ConjugacyClass(grp,PreImagesRepresentative(aiso,Representative(i)));
# SetStabilizerOfExternalSet(s,PreImage(aiso,Centralizer(i)));
# Add(t,s);
# od;
# SetConjugacyClasses(grp,t);
# fi;
if Length(cand)>1 and cheap<>2 then
s:=List(CycleStructuresGroup(grp),i->i=1);
cand:=Filtered(cand,i->TRANSProperties(deg,i)[5]=s);
fi;
if Length(cand)>1 then
p:=List(cand,i->TransitiveGroup(deg,i));
# DerivedSubgroups + Frattini Subgroups
s:=Filtered([1..Length(cand)],i->
Size(DerivedSubgroup(p[i]))=Size(DerivedSubgroup(grp)));
if Length(Factors(Size(grp)))=1 then
s:=Filtered(s,i->
Size(FrattiniSubgroup(p[i]))=Size(FrattiniSubgroup(grp)));
fi;
cand:=cand{s};
p:=p{s};
fi;
if Length(cand)>1 then
# Blockl"angen
t:=List(p,i->Collected(List(AllBlocks(i),Length)));
s:=Collected(List(AllBlocks(grp),Length));
s:=Filtered([1..Length(cand)],i->s=t[i]);
cand:=cand{s};
p:=p{s};
fi;
if Length(cand)>1 then
# 4-sets
t:=[4,CntOp(grp,SetsOrbits(grp,4),OnSets)];
s:=Filtered([1..Length(cand)],i->t in TRANSProperties(deg,cand[i])
or ForAll(TRANSProperties(deg,cand[i]){
[9..Length(TRANSProperties(deg,cand[i]))]},j->j[1]<>4));
cand:=cand{s};
p:=p{s};
fi;
if Length(cand)>1 and cheap<>2 then
# As all computations, which follow involve only the groups, convert
# them to PcGroups if possible
if IsSolvableGroup(grp) then
s:=Filtered([1..Length(cand)],i->IsSolvableGroup(p[i]));
cand:=cand{s};
# aiso:=IsomorphismPcGroup(grp);
# grp:=Image(aiso,grp);
#
# piso:=List(p{s},IsomorphismPcGroup);
# p:=List([1..Length(s)],i->Image(piso[i],p[s[i]]));
p:=p{s};
List(p,Pcgs); # enforce Pcgs use
# else
# aiso:=IdentityMapping(grp);
# piso:=List(p,IdentityMapping);
fi;
# Klassen
t:=Collected(List(ConjugacyClasses(grp),
i->[CycleStructurePerm(Representative(i)),Size(i)]));
s:=Filtered([1..Length(cand)],i->Collected(List(
ConjugacyClasses(p[i]),
j->[CycleStructurePerm(Representative(j)),Size(j)]))=t);
cand:=cand{s};
p:=p{s};
fi;
# maximal subgroups
if cheap=fail and IsSolvableGroup(grp) and Length(cand)>1 then
t:=Collected(List(MaximalSubgroupClassReps(grp),
i->[Size(i),Collected(List(OrbitsDomain(i,MovedPoints(grp)),Length))]));
s:=Filtered([1..Length(cand)],k->
Collected(List(MaximalSubgroupClassReps(p[k]),
i->[Size(i),Collected(List(OrbitsDomain(i,MovedPoints(grp)),Length))]))=t);
cand:=cand{s};
p:=p{s};
if Length(cand)>1 then
a:=Filtered(t,i->i[2]<=5 and Length(i[1][2])=1 and i[1][2][1][2]=1);
a:=List(a,i->i[1][1]);
t:=Collected(List(Filtered(MaximalSubgroupClassReps(grp),
i->Size(i) in a and Length(OrbitsDomain(i,MovedPoints(grp)))=1),
x->TransitiveIdentification(x:cheap)));
s:=Filtered([1..Length(cand)],
k->Collected(List(Filtered(MaximalSubgroupClassReps(p[k]),
i->Size(i) in a and Length(OrbitsDomain(i,MovedPoints(p[k])))=1),
x->TransitiveIdentification(x:cheap)))=t);
cand:=cand{s};
p:=p{s};
fi;
fi;
if cheap=fail and Length(cand)>1 and not IsSolvableGroup(grp) then
# NormalSubgroups (some solvable groups have too many)
t:=Collected(List(NormalSubgroups(grp),Size));
s:=Filtered([1..Length(cand)],
i->Collected(List(NormalSubgroups(p[i]),Size))=t);
cand:=cand{s};
p:=p{s};
fi;
if cheap=fail and Length(cand)>1 and Size(grp)<3000 then
# Subgroups
Info(InfoWarning,2,"TransId: test Subgroups ",cand);
t:=Collected(List(ConjugacyClassesSubgroups(Group(GeneratorsOfGroup(grp))),
i->[Size(Representative(i)),Size(i)]));
s:=Filtered([1..Length(cand)],i->Collected(List(
ConjugacyClassesSubgroups(Group(GeneratorsOfGroup(p[i]))),
i->[Size(Representative(i)),Size(i)]))=t);
cand:=cand{s};
p:=p{s};
fi;
if cheap=fail and Length(cand)>1 then
# two special cases in degree 30
if Length(dom)=30 and 2230 in cand or 4335 in cand then
Info(InfoWarning,2,"TransId: Isomorphism Test",cand);
cand:=First(cand,i->IsomorphismGroups(grp,
TransitiveGroup(30,i):nogensyssearch:=true)<>fail);
return cand;
fi;
# now finally the hard test: Test for conjugacy
Info(InfoWarning,2,"TransId: Conjugacy Test",cand);
s:=SymmetricGroup(Maximum(dom));
# if IsSolvableGroup(grp) then
# grp:=PreImage(aiso,grp);
# p:=List([1..Length(p)],i->PreImage(piso[i],p[i]));
# fi;
grp:=AsSubgroup(s,grp);
p:=List(p,i->AsSubgroup(s,i));
s:=Filtered([1..Length(cand)],i->IsConjugate(s,grp,p[i]));
cand:=cand{s};
p:=p{s};
fi;
if Length(cand)=1 then
return cand[1];
elif cheap=true then
return cand;
elif cheap<>fail then
return cand;
else
Error("Uh-Oh, this should never happen ",cand);
fi;
end);
#############################################################################
##
#F SelectTransitiveGroups(arglis,alle) . . . . . selection function
##
BIND_GLOBAL("SelectTransitiveGroups",function(arglis,alle)
local i,j,a,b,l,p,deg,gut,g,grp,nr,f;
l:=Length(arglis)/2;
if not IsInt(l) then
Error("wrong arguments");
fi;
deg:=[2..TRANSDEGREES];
p:=Position(arglis,NrMovedPoints);
if p<>fail then
p:=arglis[p+1];
if IsInt(p) then
p:=[p];
fi;
if IsList(p) then
f:=not IsSubset(deg,p);
deg:=Intersection(deg,p);
else
f:=true;
deg:=Filtered(deg,p);
fi;
else
f:=true; #warnung weil kein Degree angegeben ?
fi;
gut:=[];
for i in deg do
if not IsBound(TRANSLENGTHS[i]) then
TransGrpLoad(i,0);
fi;
gut[i]:=[1..TRANSLENGTHS[i]];
od;
# special treatment for Size for degrees larger than 15
a:=Position(arglis,Size);
if a<>fail then
a:=arglis[a+1];
for i in Filtered(deg,i->i>15 and not IsPrime(i)) do
if IsFunction(a) then
gut[i]:=Filtered(gut[i],j->a(TRANSSIZES[i][j]));
elif IsList(a) then
gut[i]:=Filtered(gut[i],j->TRANSSIZES[i][j] in a);
else
gut[i]:=Filtered(gut[i],j->TRANSSIZES[i][j]=a);
fi;
od;
fi;
# find the properties we have not stored
p:=[];
for i in [1..l] do
if not arglis[2*i-1] in
[NrMovedPoints,Size,Transitivity,SignPermGroup,IsPrimitive] then
Add(p,arglis{[2*i-1,2*i]});
fi;
od;
for i in [1..l] do
a:=arglis[2*i-1];
b:=arglis[2*i];
# get all cheap properties first
if a=NrMovedPoints then
f:=false;
if IsInt(b) then
b:=[b];
fi;
if IsList(b) then
b:=Set(b);
if not IsSubset(deg,b) then
f:=true;
fi;
deg:=Intersection(deg,b);
else
# b is a function (wondering, whether anyone will ever use it...)
f:=true;
deg:=Filtered(deg,b);
fi;
elif a=Size or a=Transitivity or a=SignPermGroup then
if a=Size then
nr:=1;
elif a=Transitivity then
nr:=3;
else
nr:=4;
fi;
for i in deg do
gut[i]:=Filtered(gut[i],j->STGSelFunc(TRANSProperties(i,j)[nr],b));
od;
elif a=IsPrimitive then
b:=NumBol(b);
for i in deg do
gut[i]:=Filtered(gut[i],j->TRANSProperties(i,j)[2]=b);
od;
fi;
od;
if f then
Print("#W AllTransitiveGroups: Degree restricted to [2..",
TRANSDEGREES,"]\n");
fi;
# the rest is hard:
grp:=[];
for i in deg do
for nr in gut[i] do
g:=TransitiveGroup(i,nr);
if ForAll(p,i->STGSelFunc(i[1](g),i[2])) then
if alle then
Add(grp,g);
else
return g;
fi;
fi;
od;
od;
return grp;
end);
#############################################################################
##
#F AllTransitiveGroups( <fun>, <res>, ... ) . . . . . . . selection function
##
BIND_GLOBAL("AllTransitiveGroups",function ( arg )
return SelectTransitiveGroups(arg,true);
end);
#############################################################################
##
#F OneTransitiveGroup( <fun>, <res>, ... ) . . . . . . . selection function
##
BIND_GLOBAL("OneTransitiveGroup",function ( arg )
local sel;
sel:=SelectTransitiveGroups(arg,false);
if sel=[] then
return fail;
else
return sel;
fi;
end);
#############################################################################
##
#E